Решение общей задачи линейного программирования

 

При решении общей задачи линейного программирования методом Штифеля мы должны проделать следующие шаги:

1) переместить нули из правого заглавного столбца, в верхнюю заглавную строку (при этом столбец, в верхнюю часть которого попадает ноль, вычеркивается);

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

3) добиться того, чтобы свободные члены, расположенные в последнем столбце таблицы, были неотрицательны (выйти в область планов) или доказать, что задача не имеет решения из-за отсутствия планов;

4) добиться того, чтобы оценки свободных переменных, расположенные в нижней строке таблицы, стали неотрицательными (найти оптимальный опорный план) или доказать, что задача не имеет решения из-за неограниченности функции цели.

Причем первый и второй этапы желательно проделать одновременно.

 

 

Пример 4.2. Найти максимум функции цели

 

z (X) = - 8 x ₁ + x ₂ + 6 x ₃ + x ₄ + 7 x ₅ ® max, (4.4)

при условии, что

– 2 x ₁ + x ₂ + 2 x ₃ - x ₄ + x ₅ £ – 4,

x ₁ + 4 x ₂ + x ₃ – 2 x ₄ – 2 x ₅ = – 8, (4.5)

– 3 x ₁ – x ₂ + 2 x ₃ + x ₄ + 3 x ₅ £ – 2,

x ₁, x ₃, x ₄, x ₅ ³ 0.

 

Решение. Перепишем систему ограничений (4.5) в виде:

 

2 x ₁ – x ₂ – 2 x ₃ + x ₄ – x ₅ – 4 = y ₁,

– x ₁ – 4 x ₂ – x ₃ + 2 x ₄ + 2 x ₅ – 8 = 0, (4.6)

3 x ₁ + x ₂ – 2 x ₃ – x ₄ – 3 x ₅ – 2 = y ₂,

x ₁, x ₃, x ₄, x ₅, y ₁, y ₂ ³ 0.

 

Решим данную задачу методом Штифеля:

 

– x 1

– x 2

– x 3

– x 4

– x 5

– x 1

– x 2

– x 3

– x 4

y 1

–2

–1

–4

y 1

–3/2

5/2

–2

–8

–2

–2

–8

x 5

–1/2

–2

–1/2

y 2

–3

–1

–2

y 2

–3/2

7/2

–2

–14

z

–1

–6

–1

–7

z

9/2

–15

–19/2

Табл. 4.7. Табл. 4.8.

 

На первом шаге (при переходе от табл. 4.7 к табл. 4.8) свободная переменная x ₅ меняется на базисную переменную 0. При попадании нуля на верх соответствующий столбец можно исключить из таблицы.

На втором шаге (при переходе от табл. 4.8 к табл. 4.9) свободная переменная x ₂ меняется на базисную переменную y ₂. После этого строку, соответствующую переменной x ₂, можно, предварительно запомнив, исключить из таблицы 4.9. Таким образом, мы приходим к таблице 4.10:

 

– x 1

– y 2

– x 3

– x 4

y 1

–0,6

–0,6

0,4

–0,8

0,4

– x 1

– y 2

– x 3

– x 4

x 5

–1,1

0,4

0,9

0,2

–1,6

y 1

–0,6

–0,6

0,4

–0,8

0,4

x 2

–0,3

0,2

0,7

–0,4

–2,8

x 5

–1,1

0,4

0,9

0,2

–1,6

z

–14

z

–14

Табл. 4.9. Табл. 4.10.

 

На данном этапе завершается упрощение задачи. Заметим, что упрощение задачи можно было сделать иначе. На первом же шаге можно было базисную переменную 0 заменить на свободную переменную x ₂. Тем самым, мы могли сэкономить один шаг.

До сих пор мы не следили за значениями функции цели и за оценками свободных и базисных переменных. На втором этапе обратим внимание на оценки базисных переменных y ₁ и x ₅, то есть на числа 0,4 и – 1,6 из последнего столбца таблицы 4. Среди этих чисел есть отрицательное
(–1,6). Просматривая другие элементы строки, соответствующей базисной переменной x ₅, находим среди них еще одно отрицательное –1.1 (если бы такого отрицательного числа не нашлось, то задача не имела бы решения из-за отсутствия планов). Вычислим минимальное симплексное отношение для первого столбца, в котором находится отрицательное число –1,1. В данном случае оно, очевидно, равно (–1,6):(–1,1) = 16/11, и разрешающим элементом является число –1,1. После очередного пересчета приходим к таблице:

 

	– x 5	– y 2	– x 3	– x 4
y 1	–6/11	–9/11	–1/11	–1/11	14/11
x 1	–10/11	–4/11	–9/11	–2/11	16/11
z					–14

Табл. 4.11.

 

Теперь обе оценки базисных переменных положительны и, следовательно, мы вышли в область планов. Так как все оценки свободных переменных неотрицательны, то данный план является оптимальным. Причем он является единственным оптимальным планом данной задачи, несмотря на наличие нулевых оценок. Действительно, при попытке заменить любую из свободных переменных x ₅ или x ₄, имеющую нулевую оценку на любую из базисных переменных, нам пришлось бы в качестве разрешающего элемента выбрать отрицательное число, и тем самым выйти из области планов задачи. Таким образом, оптимальным планом задачи (4.6) является план с компонентами:

То есть, . При этом .