Книги по разным темам Pages:     | 1 |   ...   | 6 | 7 | 8 |

Базис x1 x2 xxчлен 6 -310 6/3= x35 7 1 0 1 35/1=xf 0 -7 -fx < 0, fx < fx x2 вводим в базис, 2 2 min{6 3 = 2, 35 1 = 35}= 2 x3 `выводим из базиса.

Таким образом, Б1 = {x2, x4}. В результате приходим к табл. 10.2.

Таблица 10. Своб.

Базис x1 x2 x3 xчлен 1 2 1 x3 22 1 33 3 33 0 x- = 3 3 22 f 18 -Из табл. 10.2 следует, что ДБР1 = (х2 = 2, х4 = 33). ДБРне является оптимальным ( fx = -10 < 0), задача разрешима (в столбце x1 есть положительный коэффициент). Находим Б2 :

fx < 0 x1 вводим в базис, x4 выводим из базиса.

Таким образом, Б2 = {x1, x2}. В результате приходим к табл. 10.3.

Таблица 10.Своб.

Базис x1 x2 xxчлен 1 1 x4 2 22 1 x2 2 22 6 f 63 0 2 11 1, Из табл. 10.3 следует, что ДБР2 = x1 = 4, x2 = 2 ДБР2 является оптимальным решением.

1 Таким образом, задача L0 имеет решение х(0) =, 3, 2 при этом f (х(0)) = 63.

Поскольку x(0) не является целочисленным, то выполняем 1-й этап.

Первый этап Определяем первое правильное отсечение. Производящими являются 1-я и 2-я строки итоговой симплекс-таблицы задачи L0.

1 Поскольку {b1} = и {b2} =, то первое правило не по2 зволяет выбрать производящую строку для построения отсечения. Используем второе правило выбора производящей строки.

Вычисляем d1 и d2 :

1 21 3 11 1 7 1 d1 = + =, d2 = + =.

2 22 22 24 2 22 22 Поскольку d1 < d2, то для построения 1-го правильного отсечения выбираем 2-ю строку итоговой симплекс-таблицы задачи L0. 2-й строке соответствует равенство 7 1 0 x 0 x = 3 +.

(1 + 0)x2 + + + + 3 22 22 Следовательно, 1-е правильное отсечение имеет вид 7 1 - x3 - x4 + u1 = -.

22 22 Составляем задачу L1:

L0, 7 1 L1 x3 - x4 + u1 = -, 22 22 u1 0.

Решаем задачу L1 двойственным симплекс-методом.

В качестве базисных выберем переменные x1, x2, u1. Таким образом, Б0 = {x1, x2, u1}. В результате приходим к табл. 10.4.

Таблица 10. Своб.

Базис x1 x2 x3 x4 uчлен 1 1 10 x4 2 22 1 017 x2 22 1 7 00 u1 - - 2 22 6 f 63 0 0 2 11 Из табл. 10.4 следует, что начальное базисное решение БР1 1. БР0 не является допустимым, по= x1 = 4, x2 = 3, u1 = - 2 2 скольку в столбце свободных членов есть отрицательный коэф Pages:     | 1 |   ...   | 6 | 7 | 8 |    Книги по разным темам