Вычисления условия оптимальности свв- = (0, 0, 0, 0).
Ц " *,Ui - С*Л (Pi. Р.) - <*„ сг) = (-5, -4). Отсюда следует, что вводимым в базис вектором будет Р,. Вычисления условия допустимости
xe„ = (*з> *4> *6. e)r = (24> 6 *> 2)Г-В-Р, =(6, 1,-1, 0)г.
Следовательно,
х, =1шпру,-,- =min{4, 6,-,-}=4, и вектор Р3 определяется как исключаемый из базиса.
Результаты выполненных вычислений представим в виде знакомой симплекс-таблицы. Такое представление поможет сравнить модифицированный и обычный симплекс-методы.
Итерация 1
Х«, = (*,. *4> *5> *в) СВ, = (5> °> 0> 0)-
(6 О О ОЛ
В.-.Р,, Р5,Рв) =
110 0 -10 10 0 0 0 1,
Используя подходящий метод вычисления обратной матрицы В~ (в разделе А.2.7
приведен метод вычисления обратных матриц на основе их мультипликативного представления), находим
i 0 0 0Л
-110 0 6
i 0 1 о
0 0 0 1
Отсюда получаем
В~ Ь = (4, 2, 5, 2)\ 2 = Св Хв = 20.
Вычисления условия оптимальности
снв: = -,о,о,о
Ц " с)ггя = С„В-1 (Р2, Р3) - (с2, с3) = -,
Отсюда следует, что вводимым в базис будет вектор Р2. Вычисления условия допустимости
ВГР2=1т.т.г.1
2 4 5
Следовательно,
и вектор Р4 определяется как исключаемый из базиса. (Постройте симплекс-таблицу, отображающую результаты вычислений этой итерации.)
Итерация 2
Хв, = (*„ хг, х5, х/, Св, = (5, 4, 0, 0).
В2 = (Р„Р2,Р5,Р6) =
(Ь 4 0 0} 12 0 0 -1110 0 10 1
Находим
в;1 =
i \ 0 0
М 1 0
i л о i
Отсюда получаем
хв, = в2-ь=з,т,т.
z= СЯХЙ. -21.
Вычисления условия оптимальности
ад=(2.1, о, о].
izj - *,U« = С8;В2- (Р3, Р4) - (с3, с4) = , 1 Отсюда следует, что решение ХЛ оптимально. Вычисления заканчиваются. Оптимальное решение:
х. = 3. л:„ = 1.5. 2 = 21.
УПРАЖНЕНИЯ 7.2.2
1. В примере 7.2.1 представьте результаты вычислений, выполненных на первой и второй итерациях, в виде симплекс-таблиц.
2. Решите модифицированным симплекс-методом следующие задачи ЛП.
a) Максимизировать z = 6л:, - 2хг + Зх3 при ограничениях
2 л:, - х2 + 2х3 < 2, х1+4х3<4,
b) Максимизировать г = 2л:, + л:2 4- 2л:3 при ограничениях
4 л:, + Зл:2-1-8д:3< 12, 4 л:, + л:2 +12лг3<8, 4л:,-л:2 + 3л:3<8, л:,, л:2, х3>0.
c) Минимизировать z = 2jc, + л:2 при ограничениях
Зл:, 4- л:2 = 3, 4л:, 4-Зл:2 > 6, л:, 4-2л:2<3, л:,, jc2>0.
d) Минимизировать z = 5jc, - 4л:2 4- 6л:3 4- 8л:4 при ограничениях
л:, + 7л:2 4- Зл:3 4- 7л:4 < 46, Зл:, - л:24-л:34-2л:4<20, 2xl + 3x2-x3 + xi>18,
2 3* 4 ~ *
3. Решите следующую задачу ЛП с помощью модифицированного симплекс-метода, используя в качестве начального базиса вектор = (л:2, л:4, л:5)г.
Минимизировать z = 7х2 + 11л:3 - 10л:4 4- 26л:6 при ограничениях
хг-х3 + х, + хв = 6,
л:2 - л:3 л:4 4- Зл:6 - 8,
л:, 4- л:2 - Зл:3 4- л:4 4- л:5 = 12,
Х\> %2> 3> Ч 5 6 -
4. Используя модифицированный симплекс-метод в схеме вычислений двух-этапного метода с искусственными переменными, решите следующие задачи.
a) Задача из упражнения 2,с.
b) Задача из упражнения 2,d.