Алгоритм вычислительной реализации этих трех элементов рассмотрим на следующем примере

Пример 2.5.

Решить задачу симплексным методом:

z=18 y₁+16y₂+5y₃+21y₄ →min

при ограничениях:

y₁+2y₂+3y₄≥2

3y₁+y₂+y₃≥3

y₁, y₂, y₃, y₄≥0

Шаг 1:

Введем дополнительные переменные y₅, y₆ со знаком «-», т. к. «≥» получим систему уравнений в канонической форме:

y₁+2y₂+3y₄-y₅=2

3y₁+y₂+y₃-y₆=3

Если на первом шаге в качестве основных переменных взять дополнительные переменные y₅, y₆, тогда:

y₁=y₂=y₃=y₄=0, => y₅=-2; y₆=-3.

У₁=(0,0,0,0,-2,-3) – недопустимое базисное решение.

Шаг 2:

В данном случае в качестве основных удобно взять переменные y₃, y₄ в соответствии с правилом выбора основных переменных, сформулированным выше.

0 3 ≠0

1 0

y₃, y₄ - основные переменные.

y₁=y₂=y₆=y₅=0 неосновные переменные;

Выразим основные переменные через неосновные:

y₃=3-3y₁-y₂+y₆

y₄=2/3-y₁/3-2/3y₂+y₅/3

y₃=3, y₄=2/3;

Базисное решение У₂=(0,0,3,2/3,0,0) – допустимое решение.

Выражаем линейную функцию через неосновные переменные:

z=18y₁+16y₂+5(3-3y₁+y₆-y₂)+21(2/3-y₁/3-2/3y₂+y₅/3)= 29-4y₁-3y₂+7y₅+5y₆

Критерии оптимальности не выполняются, т.к. имеются отрицательные коэффициенты при y₁ и y₂, поэтому Z₁ =29 – не является минимальным.

Так как функцию Z можно уменьшить за счет перевода в основные любой из переменных у₁ и у₂, имеющих в выражении для Z отрицательные коэффициенты. Так как у имеет больший по абсолютному значению коэффициент, то начнем с этой переменной.

Шаг 3:

y₁, y₄ - основные переменные.

y₂, y₃, y₅, y₆=0 – неосновные переменные;

После преобразований:

y₁=1- 1 y₂ - 1 у₃+ 1 у₆;

3 3 3

y₄= 1 - 5 у₂+ 1 у₃+ 1 у₅- 1 у₆;

3 9 9 3 9

z=25- 5 y₂+ 1 у₃+ 1 у₅- 1 у₆;

3 9 3 9

y₃=(1;0;0;1/3;0;0) – допустимое базисное решение.

Z(y₃)=25 – не является min, так как имеется отрицательный коэффициент при y₂, поэтому переменную y₂ переводим в основную.

Шаг 4:

y₁,y₃ – основные переменные.

y₃, y₄, y₅, y₆=0 – неосновные переменные.

у₁= 4 - 2 у₃+ 5 у₄- 1 у₅+ 2 у₆

5 3 3 5 5

y₂= 3 + 1 у₃- 9 у₄+ 3 у₅- 1 у₆

5 5 5 5 5

y₃= (4/5;3/5;0;0;0;0) – допустимое базисное решение

z=24+y₃+3y₄+6y₅+4y₆→min

Решение оптимальное, так как в выражении нет отрицательных коэффициентов при неосновных переменных.

Z(y₄)=24=min

Дата добавления: 2014-01-06