Отсюда В Р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)

Отсюда В Р23 = (1/10, 0, 9/10f. Поскольку Хв = (р22, р , = (14/25, 1, 11/25)7 , из базисного решения следует исключить искусственную переменную х7.

Находим новый базис и новую обратную матрицу В 1 (проверьте!).

в =

Новое базисное решение равно

Хв = (Р22, Р , Р2/ = В-(40, 1, If = (23/45, 1, 22/45f, Св = (C2Y22, C.Y , C2Y23) = (50, 60, 5).

Итерация 4

Подзадача 1 (j = 1). wl = -2хг - 4х2 + 48. Получаем z* - с\ = wt = 0 . Подзадача 2 (j = 2). w2 = 0xt + 0х5 + 48 = 48.

Небазисная переменная хь. г5 - с5 = 1. Отсюда следует, что решение, полученное на третьей итерации, оптимально.

С помощью обратной подстановки вычисляем оптимальное решение исходной задачи, х; = (* */ = puYu = 1(0, 12f = (0, 12f, X, = (х3, х4) = P22Y22 + p23Y23 =

= - (50. Of +-(5, Of = (28, 0)T. 45 45

Все остальные переменные равны нулю. Оптимальное значение целевой функции получим путем прямой подстановки в ее выражение значений соответствующих переменных.

УПРАЖНЕНИЯ 7.4.1

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

х, + 2х2 < 6, 2х, + х2 < 8, -х, +х2< 1, *2<2, xv х2>0.

2х, + х2 < 2, Зх, + 4х2> 12, х х2>0.

х,-х2<10,

2х,<40,

х х2>0.

2. В примере 7.4.1 крайние точки подпространств {X, = b Х,>0) и {Х21 D2X2 = b2, Х2 > 0} можно найти графически. Используйте эту информацию, чтобы сформулировать в явном виде главную задачу. Затем покажите, что применение к главной задаче модифицированного симплекс-метода порождает такую же последовательность вводимых в базис переменных p.s, как и последовательное решение отдельных подзадач 1 и 2.

3. Дана следующая задача линейного программирования.

Максимизировать z = х, + Зх2 + 5х3 + 2х4

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

2х, + х2 < 9,

х, + 4х2 < 8,

5х, + Зх2 + 4х3 > 10,

х3 - 5х4 < 4,

х3 + х4<10,

Xj, Х2, Х3, Х4 0.

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

4. Решите задачу из предыдущего упражнения методом декомпозиции и сравните процесс решения при использовании разных алгоритмов.

5. Примените метод декомпозиции к следующей задаче.

Максимизировать z = 6х, + 7х2 + Зх3 + 5х4 + х5 + х6 при ограничениях

х, + х2 + х3 + х4 + х5 + х6 < 50,

х, + х2< 10,

х2<8,

5х3 + х4<12,

х5 + х6>5,

х5 + 5х6 < 50,

х х2, х3, х4, х5, х6 > 0.

6. Продумайте необходимые изменения в применении метода декомпозиции к задаче минимизации, затем решите следующую задачу.

Минимизировать z = 5х, + Зх2 + 8х3 - 5х4