Симплексный метод решения ЗЛП (стр. 4 из 5)

-x₁+x₃+x₄≤5; (2.5)

-3x₁+5x₄≤7.

Требуется минимизировать линейную функцию

Z=5x₁-2x₃

Приводя неравенства к стандартному виду (≥0) и вводя добавочные переменныеy₁,y₂,y₃переходим к условиям-равенствам:

y₁=5x₁+x₂-2x₃+2

y₂=x₁-x₃-x₄+5 (2.5)

y₃=3x₁-5x₄+7

Число переменных (n = 7) на 4 превышает число уравнений (т = 3). Значит, четыре переменные могут быть выбраны в качестве свободных.

Пусть в качестве свободных переменных выступаютx₁,x₂,x₃,x₄. Положим их равными нулю и получим опорное решение:

x₁=x₂=x₃=x₄=0;

y₁=2, y₂=5, y₃=7.

При этих значениях переменных Z= 0.

Это решение не оптимально, поскольку в линейной функции Z коэффициент приx₃отрицателен. Значит, увеличиваяx₃можно уменьшить Z.

Попробуем увеличиватьx₃.Из выражений (2.5) видно, что вy₁и y₂переменнаяx₃входит с отрицательным коэффициентом, значит, при увеличенииx₃соответствующие переменные могут стать отрицательными.

Определим, какая из этих переменных (y₁илиy₂)раньше обратится в нуль при увеличенииx₃Очевидно, что этоy₁она станет равной нулю приx₃=1, а величинаy₂— только приx₃= 5.

Выбирается переменная у, и вводится в число свободных вместоx₃Чтобы разрешить систему (2.5) относительноx₃, y₂, y₃поступим следующим образом. Разрешим первое уравнение (2.5) относительно новой базисной переменнойx₃:

x₃=5/2*x₁+1/2*x₂-1/2*y₁+1

Это выражение подставляется вместоx₃во второе уравнение:

x₃=5/2*x₁+1/2*x₂-1/2y₁+1;

y₂=-3/2*x₁-1/2*x₂+1/2*y₁-x₄+4; (2.6)

y₃=3x₁-5x₄+7.

Что касается третьего уравнения, то оно, как не содержащееx₃не изменится. Система (2.2) приведена к виду со свободными переменнымиx₁, x₂, y₁, x₄и базиснымиx₃, y₂, y₃.

Положим теперь свободные переменные равными нулю. Функция приобретает значение Z=-2, что меньше (лучше), чем прежнее значение Z= 0.

Это решение все еще не оптимально, так как коэффициент приx₂в выражении (2.7) отрицателен, и переменнаяx₂может быть увеличена. Это увеличение, как это видно из системы (2.6), может сделать отрицательнойy₂(в первое уравнениеx₂входит с положительным коэффициентом, а в третьем — отсутствует).

Поменяем местами переменныеx₂ и y₂— первую исключим

из числа свободных, а вторую — включим. Для этого разрешим второе уравнение (2.6) относительноx₂и подставимx₂в первое уравнение. Получим следующий вид системы (2.5):

x₃=x₁-y₂-x₄+5

y₂=-3x₁-2y₂+y₁-2x₄+8 (2.7)

y₃=3x₁-5x₄+7

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

Z=3x₁+2y₂-y₁+2x₄-8+y₁-2=3x₁+2y₂+2x₄-10 (2.8)

Полагаяx₁=y₁=y₂=x₄=0 , получим Z = -10.

Это решение является оптимальным, так как коэффициенты при всех свободных переменных в выражении (2.8) неотрицательны. Итак, оптимальное решение ОЗ найдено (2.9):

x₁^*=0, x₂^*=8, x₃^*=5, x₄^*=0, y₁^*=0, y₂^*=0, y₃^*=7. (2.9)

При таких значениях переменных линейная функция Z принимает минимальное значение (2.10):

Z_min=-10 (2.10)

Заметим, что в рассмотренном примере нам не пришлось искать опорное решение: оно сразу же получилось, когда мы положили свободные переменные равными нулю. Это объясняется тем, что в уравнениях (2.5) все свободные члены были неотрицательны и, значит, первое же попавшееся решение оказалось опорным. Если это окажется не так, можно будет прийти к опорному решению с помощью такой же процедуры обмена местами некоторых базисных и свободных переменных, повторно решая уравнения до тех пор, пока свободные члены не станут неотрицательными

2.4 Двойственная задача

Использование идей двойственности в сочетании с общей идеей симплекс-метода позволило разработать еще один метод решения задач ЛП - двойственный симплекс-метод. Впервые этот метод был предложен Лемке в 1954г. Решение задачи ЛП двойственным симплекс-методом сводится к отысканию оптимального плана прямой задачи последовательным переходом от одного базиса к другому.

Задача ЛП в канонической форме имеет вид:
максимизировать L(x) = сумма от j=1 до n (сjчj)
при условиях:
сумма от j=1 до n (аjXj)=bv, (v=1,2,....m)
или
сумма от j=1 до n (АjXj)=b, xj>=0, j=1,2,...n

Составим двойственную задачу по условиям прямой задачи и определим области допустимых решений ДП:
Прямая задача Двойственная задача

maxZ=x₁-3x₃-3x₄-MR₁-MR₂

y₁: x₁+2x₃-2x₄+x₅=4

y₂: 3x₁-4x₃+4x₄+R₁=11

y₃: x₁+x₃-x₄-x₆+R₂=0

minW=4y₁+12y₂

x₁: y₁+3y₂+y₃≥1

x₃: 2y₁-4y₂+y₃≥-3

-2y₁+4y₂-y₃≤3(1)

X₄: -2y₁+4y₂-y₃≥3 (2)

X₅: y₁≥0

X₆: -y₃≥0 => y₃≤0

R₁: y₂≥-M

R₂: y₃≥-M
Итак, получено: y₁≥0,y₂≤≥0 ,y₃≤0.

2. Приведём запись двойственной задачи к канонической форме. На основании полученных ОДР двойственных переменных введём необходимые подстановки:y₂=y₄-y₅; y₃=-ỹ_3; ỹ₃,y₄,y₅≥0
Для удобства решения свернём ограничения (1) и (2) в одно со знаком равенства, а также введем в ограничения и целевую функцию избыточные, остаточные и искусственные переменные.

minW=4y₁+12y₄-12y₅+MR₁+MR₂

y₁+3y₄-3y₅-ỹ₃-y₆+R₁=1 (3)

-2y₁+4y₄-4y₅+ỹ₃+R₂=3 (4)

3. Решим ДЗ симплекс методом:
Из (3) выразим: R₁=1-y₁-3y₄+3y₅+ỹ₃+y₆
Из (4) выразим:R₂=3+2y₁-4y₄+4y₅-ỹ₃

W+y₁(-4-M)+y₄(-12+7M)+y₅(12-7M)-My₆=4M

Создаём симплекс-таблицы:

Таблица 2.2 – симплекс-таблица №1

W	y1	y4	y5	ỹ3	y6	R1	R2	ПЧ
W	1	-4-M	7M-12	12-7M	0	-M	0	0	4M
R1	0	1	3	-3	-1	-1	1	0	1
R2	0	-2	4	-4	1	0	0	1	3

B^-1(0)=

B(0)=

Таблица 2.3 – симплекс-таблица №2

W	y1	y4	y5	ỹ3	y6	R1	R2	ПЧ
W	1	-10/3M	0	0	7/3M-4	4/3M-4	-7/3M+4	0	5/3M+4
y4	0	1/3	1	-1	-1/3	-1/3	1/3	0	1/3
R2	0	-10/3	0	0	7/3	4/3	-4/3	1	5/3

B^-1(1)=

B(1)=

Таблица 2.4 – симплекс-таблица №3

W	y1	y4	ỹ5	ỹ3	y6	R1	R2	ПЧ
W	1	-40/7	0	0	0	-12/7	-7/3M+4	-M+12/7	48/7
y4	0	-1/7	1	-1	0	-1/7	1/3	1/7	4/7
ỹ3	0	-10/7	0	0	1	4/7	-4/3	-3/7	5/7

Симплекс-таблица №3 – оптимальная, т. к. коэффициенты приНБП≥0
minW=48/7, maxZ=minW=48/7,

y₁^*=0, y₂^*=y₄^*-y₅^*=4/7, y₃^*=-5/7

Двухфазовый симплекс метод, иначе называют методом искусственного базиса:

Если в условии задачи линейного программирования не все ограничения представлены неравенствами типа «≤», то далеко не всегда нулевой вектор будет допустимым решением. Однако каждая итерация симплекс-метода является переходом от одной вершины к другой, и если неизвестно ни одной вершины, алгоритм вообще не может быть начат.

Процесс нахождения исходной вершины не сильно отличается от однофазного симплекс-метода, однако может в итоге оказаться сложнее, чем дальнейшая оптимизация. Из изложенного выше не прозвучало отчетливо почему если ограничения отличается от <= не всякий 0-вектор будет допустимым решением. В самом деле пусть i - уравнение имеет вид Ai1X1+...AinXn>=Bi но просто можно изменить знаки записав -Ai1X1- ... AinXn<=-Bi и тем самым привести все неравенства к канонической форме. Это было бы нельзя сделать если бы на вектор B было наложено условие неотрицательностиBi>=0 Но в формулировке выше ограничения вектор B отсутствуют. (это очевидная неточность для теоретической статьи в энциклопедии, где все предпосылки должны формулироваться полно) Если бы все было так просто и легко, непонятно зачем изобретали двухфазный метод... Кроме того по этой же причине классический симплекс метод не годится для решения задачи Min F (точнее не годится в случае положительности всех коэфф целевой функции, т.к. тогда метод не сделает ни одной итерации).