ления вводимых крайних точек Yy,t.. Такой подход не требует определения всех крайних точек всех п выпуклых множеств. После того как требуемая крайняя точка определена, нетрудно определить все элементы вектора Р . На основе этой информации мы можем определить исключаемую переменную. Далее с помощью модифицированного симплекс-метода вычисляем следующую обратную матрицу В 1.

Пример 7.4.1

Решим с помощью метода декомпозиции следующую задачу ЛП.

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

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

х, + х2 + х3 + х4 < 40, 5x, + x2<12, х3 + х4> 5, х3 + 5х4 < 50, Х, х2, х3, х4 - 0.

Данную задачу можно разбить на две подзадачи, которым будут соответствовать следующие множества переменных:

X, = (xv х2) , Х2 = (х3, х4) .

Основную задачу можно записать следующим образом.

Отметим, что дополнительная переменная х5 введена для преобразования общего ограничения к виду равенства

jCj + х2 + х3 + х4 + хь = 40.

Эта переменная не входит ни в одну подзадачу, ее значение находится как часть решения главной задачи. Другие переменные в начальном базисе, хе и х7, являются искусственными переменными.

Итерация 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)