2015-06-30
826
Найти максимум функции 
при условиях
Решение. Систему уравнений задачи запишем в векторной форме:
где
Так как среди векторов 
имеется три единичных вектора, то для данной задачи можно непосредственно найти опорный план. Таковым является план Х= (0, 0, 20, 24; 0; 18). Составляем симплексную таблицу (табл. 10) и проверяем, является ли данный опорный план оптимальным.
Таблица 10
| i | Базис | Сб | Р 0 | -6 | |||||
| P 1 | P 2 | P 3 | p 4 | p 5 | Р 6 | ||||
| p 3 P 4 p 6 | 20 24 18 | -2 -1 -2 | -2 -1 | -12 -5 |
Как видно из табл. 10, исходный опорный план не является оптимальным. Поэтому переходим к новому опорному плану. Это можно сделать, так как в столбцах векторов P 1 и p 5, 4-я строка которых содержит отрицательные числа, имеются положительные элементы. Для перехода к новому опорному плану введем в базис вектор p 5 и исключим из базиса вектор p 4. Составляем таблицу II итерации.
Таблица 11
| i | Базис | Сб | Р 0 | -6 | |||||
| P 1 | P 2 | P 3 | p 4 | p 5 | Р 6 | ||||
| p 3 P 5 p 6 | -5/3 -1/3 -1 -11/3 | 5/3 -2/3 -9 8/3 | -1/3 1/3 5/3 |
Как видно из табл. 11, новый опорный план задачи не является оптимальным, так как в 4-й строке столбца вектора P 1стоит отрицательное число -11/3. Поскольку в столбце этого вектора нет положительных элементов, данная задача не имеет оптимального плана.
|
|
|
Прямая и двойственная задача линейного программирования. Геометрическая интерпретация двойственной задачи.
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей, как мы уже знаем, в нахождении максимального значения функции
(32)
при условиях
(33)
(34)
