Смекни!
smekni.com

Линейное программирование, решение задач симплексным методом (стр. 2 из 8)

3.1.3. Задача третья:

На предприятии выпускают 3 вида изделий, при этом используют 3 вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице:

Виды сырья

Расход сырья на продукцию

Запасы сырья

1

2

3

1

2

3

7

1250

2

1

1

0

250

3

5

3

0

900

Прибыль

41

35

96

Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?

3.1.4. Задача четвертая:

Для изготовления 4 видов продукции используются 3 вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице:

Виды сырья

Расход сырья на продукцию

Запасы сырья

1

2

3

4

1

2

3

3

1

20

2

1

1

2

2

11

3

1

2

3

1

25

Прибыль

2

4

3

2

Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?

3. Заключение

4. Список литературы

Председатель цикловой комиссии /Баранов В.А.

Руководитель курсового проекта /Карпушкин А.Г.

Дата выдачи задания: Срок окончания:

« » 2007 г. « » 2007 г.

СИМПЛЕКСНЫЙ МЕТОД

Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако, еще в 1939 г. идеи метода были разработаны российским ученым

Л В.Канторовичем.

Симплексный метод, позволяющий решить любую задачу линейного программирования, универсален. В настоящее время он используется для компьютерных расчетов, однако несложные примеры с применением симплексного метода можно решать и вручную.

Для реализации симплексного метода — последовательного улучшения решения — необходимо освоить три основных

элемента:

• способ определения какого-либо первоначального допустимого

базисного решения задачи;

• правило перехода к лучшему (точнее, не худшему) решению;

• критерий проверки оптимальности найденного решения.

Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений.

Обыкновенные жордановы исключения

Рассмотрим систему из m линейных уравнений с n неизвестными

a11x1 + a12x2 + … + a1nxn = b1,

……………

am1x1 + am2x2 + … + amnxn = bm.

Запишем эту систему в виде таблицы

x1

xj

xn

b1 =

a11 … a1j … a1n

………………..

bi =

ai1 … aij … ain

………………..

bm =

am1 … amj … amn

Шагом обыкновенного жорданова исключения (ОЖИ), произведенным над данной таблицей с разрешающим элементом aij ≠ 0 с I разрешающей строкой и j разрешающим столбцом, назовем операцию решения уравнения

bi = ai1x1 + ai2x2 + … + aijxj + … + ainxn

относительно xj, подстановки этого решения в исходную систему и записи вновь полученной системы в виде новой таблицы.

Нетрудно проверить, что новая таблица будет иметь вид

x1

x2

bi

xn

b1 =

b11 b12 … a1j … b1n

b2 =

b21 b22 … a2j … b2n

………………..

xj

-ai1 –ai2 … 1 ... -ain

………………..

bm =

bm1 bm2 … amj … bmn

: aij,

где brs = arsaij - arjais (i ≠ r, j ≠ s),

причем все элементы таблицы нужно разделить на aij.

Таким образом, один шаг жорданова исключения (ШЖИ) переводит исходную таблицу в новую по схеме, состоящей из следующих 5 правил:

1) разрешающий элемент заменяется единицей

2) остальные элементы разрешающего столбца j остаются без изменения.

3) остальные элементы разрешающей строки i меняют лишь свои знаки.

4) остальные элементы brs вычисляются по формуле brs = arsaij - arjais

5) все элементы новой таблицы делятся на разрешающий элемент aij.

Пример 1. Для таблицы

X1

X2

X3

Y1 =

1

-2

3

Y2 =

-1

1

2

Y3 =

2

-1

-1

один шаг жорданова исключения с разрешающими 2-й строкой и 3-м столбцом приводим к таблице

X1

X2

Y2

Y1 =

5

-7

3

X3 =

1

-1

1

Y3 =

3

-1

-1

: 2

Жордановы исключения позволяют от случайно взятой декартовой системы координатных плоскостей перейти к новой системе, в которой координатами точек являются их уклонения

от более интересной для той или другой задачи системы плоскостей.

Модифицированные жордановы исключения

Если исходную систему уравнений ai1x1 + ai2x2 + … + ainxn = bi, где i = 1,m,

записать в виде –ai1(-x1) – ai2(-x2) - … - ain (-xn) = bi

и составить таблицу

-X1

-X2

…-Xn

b1 =

–a11

–a12

… –a1n

….

…………..

bm =

–am1

–am2

… –amn

то в этих случаях вместо ОЖИ пользуются МЖИ.

Один шаг МЖИ с разрешающим элементом “-ars”, означает переход к новой таблице

-X1

-Yr -Xn

b1 =

b11 ...

a1s b1n

….

…………………….

xs =

-ar1

1 … -arn

….

…………………….

bm =

bm1

ams bmn

: (-ars)