Симплекс-метод решения задачи линейного программирования
В индексной строке табл. 1 есть отрицательный элемент - 15/4, а над ним в таблице нет ни одного положительного. Следовательно, в данной задаче целевая функция не ограничена сверху на множестве планов задачи и оптимального плана не существует. Значит, не существует оптимального плана и в исходной задаче.
Пример 2. Решить симплекс-методом следующую задачу ЛП:
Основная задача не является канонической, так как во втором уравнении системы нет базисного неизвестного и, значит, система не является канонической. Составим вспомогательную задачу, введя искусственное базисное неизвестное z1 только во второе уравнение системы (19), так как в первом уравнении уже есть базисное неизвестное х1.
Первый этап. Вспомогательная задача.
Применив к задаче алгоритм симплекс-метода получим последовательность симплексных таблиц вида
Из индексной строки табл. 2 видим, что вспомогательная задача решена, причём минимальное значение вспомогательной функции jmin = 8 > 0. Так как jmin > 0, то можно сделать вывод, что исходная основная задача вообще не имеет ни одного плана, и для неё не существует равносильной канонической задачи. В таком случае исходная задача не имеет оптимального плана.
Парой симметричных двойственных задач называются две, тесно связанные между собой задачи ЛП, которые удобно записать схематически (см. ниже).
Задача ЛП, в которой целевая функция максимизируется, а все неравенства "типа £", называется стандартной задачей максимизации; если целевая функция минимизируется, а все неравенства "типа ³" - стандартной задачей минимизации. Пара симметричных двойственных задач состоит из стандартной задачи максимизации и стандартной задачи минимизации, причем эти задачи обладают рядом особенностей, которые хорошо видны в схеме и позволяют сформулировать правила составления двойственных задач.
Правила составления пары симметричных двойственных задач.
1. Одна из задач является стандартной задачей максимизации, другая - стандартной задачей минимизации.
2. Количество неизвестных в одной из задач равно количеству основных ограничений в другой задаче.
3. Матрица коэффициентов при неизвестных в неравенствах одной задачи получается транспонированием матрицы коэффициентов другой задачи.
4. Свободные члены неравенств одной задачи совпадают с коэффициентами целевой функции другой задачи.
Если решить одну из двойственных задач, то на основании теорем двойственности можно сделать вывод о существовании или отсутствии решения другой задачи. При этом возможны три случая.
Три случая при решении пары двойственных задач
Результат решения задачи 1 |
Выводы для задачи 2 |
1. Задача 1 имеет оптимальный план. |
1. Задача 2 также имеет оптимальный план. |
2. В задаче 1 планы есть, но целевая функция не ограничена сверху на множестве планов, значит, оптимального плана не существует. |
2. В задаче 2 вообще нет планов, а значит, нет и оптимального плана. |
3. В задаче 1 вообще нет планов, а значит, нет и оптимального плана. |
3. В задаче 2 или нет планов, или целевая функция не ограничена снизу на множестве планов, но в обоих случаях оптимального плана не существует. |