Итерация 0
Х„ = (*5, хе, х7)т = (40, 1, if, Св = (0, -М, -М), В = В 1 = I.
Итерация 1
Подзадача 1 (j = 1). Имеем
z,-c,=CeB-
0.1)
-с,х,=
= (о,-м,-м)
-(3.5)
= -Зх, - 5х, - М.
Таким образом, соответствующая задача ЛП имеет следующий вид.
Минимизировать ш, - -Здс, - 5хг - М
при ограничениях
5*, +х2< 12, д:2>0.
Решив эту задачу (обычным симплекс-методом), получаем
yu = (o, i2f, z;-c; = w;=-6o-m.
Подзадача 2 (j - 2). Соответствующая задача ЛП имеет следующий вид.
Минимизировать г, -с, =С6В
(0,-М,-М)
С,Х, =
-(1.1)
= ~хъ ~хА-М.
при ограничениях
х3 + х4> 5, х3 + 5х4 < 50 ж„ 4S0.
Находим оптимальное решение этой задачи.
Y21 = (50,0f, z;-c;=-50-Af.
Поскольку главная задача - задача максимизации и z* - с < г* - с2, а также г,*-с*<0, следовательно, переменная (3U, соответствующая крайней точке Y,,, должна быть введена в базисное решение.
Для определения исключаемой переменной запишем
f (О"
Р„ =
A,Y„ 1 О
12} 1
Отсюда В"РП = (12, 1, 0)т. Имея Хв = (х6, х6, х7)т = (40, 1, 1)г, делаем вывод, что из базисного решения следует исключить переменную х6 (искусственную переменную).
Новый базис получается путем удаления из базиса вектора, соответствующего переменной х9, и введения в базис вектора Р„. Получим (проверьте!)
(\ 12 0\
1 О О 1
-12 0} 1 о
0 1
и новое базисное решение
Хв = (х„ рп, х/ = В-(40, 1, 1)г = (28, 1, 1)т, Св = (0, C.Y,,, -М) = (0, 60, -М).
Итерация 2
Подзадача 1 (j = 1). Вы должны проверить, что соответствующая задача ЛП останется такой же, как и на первой итерации (это простое совпадение, а не общее правило). Ее оптимальное решение дает г,* -с\ = wt = 0 . Отсюда следует, что никакая из
оставшихся крайних точек пространства решений подзадачи 1 не может улучшить решение главной задачи. (Оптимальным решением этой подзадачи будет крайняя точка Y,,, которой соответствует переменная (Зп, уже входящая в состав базиса. Именно поэтому z -с[ = 0 .)
Подзадача 2 (j = 2). Снова вы должны проверить, что соответствующая задача ЛП такая же (опять совпадение), как и на первой итерации. Ее оптимальное решение
Y22 = (50, Of, z;-c;=-50-Af.
Отметим, что точка Y22 фактически совпадает с крайней точкой Y21, но мы используем нижний индекс 2, чтобы показать, что эта точка соответствует второй итерации.
Из решений обеих подзадач следует, что zj - с\ < 0 . Это указывает на то, что переменная р22, соответствующая крайней точке Y22, должна войти в базисное решение. Для определения исключаемой переменной запишем
р,, =
(1,1)
Отсюда В"Р22 = (50, 0, if. Поскольку Хв = (х5, рп, х7)т - (28, 1, if, из базисного решения следует исключить переменную х5.
Находим новый базис и новую обратную матрицу В"1 (проверьте!)
Новое базисное решение равно
Хв = (р22, рп, х7)т = В",(40, 1, If = (14/25, 1, 11/25), Св = (C2Y22, C,YU, -М) - (50, 60, -М).
Итерация 3
Подзадача 1 (j = 1). Вы должны проверить, что на этой итерации целевая функция для данной подзадачи имеет следующий вид.
(М А (М Л \2М ло
Минимизировать w=\--2 \х, + \--4 j,---1-48.
{50 ) 1 1.50 ) - 50
Соответствующее оптимальное решение дает
Y13 = (o,of, z;-c; =
12 М 50
•48.
Подзадача 2 (j = 2). Здесь целевая функция имеет следующий вид (проверьте!).
Минимизировать w1=-(xi+xi)-M.
Находим оптимальное решение:
Y23 = (5,0f, .-с\=~
Небазисная переменная хь. Исходя из вида главной задачи, разность z; - cj для переменной л:й необходимо вычислять отдельно.
M+As-~m\uo,o)t-o=iA
{ 50 50 Г 50
Отсюда вытекает, что переменная хь не может улучшить решение.
Из приведенных вычислений следует, что вводимой в базис будет переменная Р23, соответствующая крайней точке Y23. Для определения исключаемой переменной вычисляем следующее.
Р2з =
(1,1)