Как решить задачу линейного программирования с помощью двойственного симплекс-метода

В этом уроке мы научимся решать задачи линейного программирования с помощью метода двойственного симплекса. Примечание: Для использования двойственного симплекса не нужно записывать двойственную формулировку задачи. Двойственный симплекс — это решение двойственной задачи без фактического написания её двойственной формулировки. Иногда решение двойственной задачи более экономично (эффективно по времени), чем решение прямой задачи. Поскольку согласно теореме о двойственности значение прямой и двойственной задач в оптимальном решении одинаково, мы предпочитаем решать двойственную задачу вместо исходной. В общем, для решения задачи линейного программирования, предполагая, что правая часть больше или равна нулю, можно использовать: 1. Обычный симплекс, когда все ограничения находятся в пределах «меньше или равно». 2. Метод «Большого M» или двухфазный метод, когда существуют ограничения «равен» или «больше или равно». Задачи типа 2 также можно решить с помощью двойственного симплекса, если выполняются определённые условия: условие оптимальности и условие неразрешимости. Для решения задачи с помощью двойного симплекса необходимо выполнить два условия: Оптимальность: напомним, что оптимальным условием является ситуация, когда все значения в строке Z таблицы симплекса положительны или равны нулю для задачи на максимум, и когда все значения в строке Z таблицы симплекса отрицательны или равны нулю для задачи на минимум. Неразрешимость: это означает, что в правой части исходной таблицы должно быть хотя бы одно отрицательное значение. Таким образом, если хотя бы одно из двух вышеуказанных условий не выполняется, вы не можете использовать двойной симплекс для решения задачи. Вместо этого вы можете использовать метод «большого М» или двухфазный метод.