Общая постановка задачи
Симплексный метод решения задач ЛП
Симплексный метод – метод последовательного улучшения плана.
Метод является универсальным, так как позволяет решить практически любую задачу линейного программирования. Математическая модель задачи приводится к каноническому (стандартному) виду. Заполняется опорная симплекс – таблица с использованием коэффициентов целевой функции и системы ограничений. Решается задача по алгоритму.
Идея симплексного метода заключается в том, что начиная с некоторого исходного опорного решения осуществляется последовательно направленное перемещение по допустимым решениям к оптимальному. Значение целевой функции для задач на максимум не убывает. Так как число допустимых решений конечно, то через конечное число шагов получим оптимальное решение.
1.Математическую модель задачи привести к каноническому (стандартному) виду.
2. Построить начальную симплекс-таблицу исходя из стандартного вида.
|
|
3. Найти разрешающий столбец.
В строке коэффициентов ЦФ найти значение с самим маленьким отрицательным числом. Этот столбец и будет разрешающим.
4. Вычислить разрешающую строку и ведущий элемент.
Почленно разделить столбец свободных членов на элементы разрешающего столбца, за исключением строки ЦФ. Выбрать наименьшее из частных. Эта строка будет разрешающей. Ведущий элемент будет на пересечении разрешающего столбца и разрешающей строки.
5.Построить новую симплекс-таблицу-второй шаг.
При построении новой таблицы убрать из базиса строку с переменной разрешающей строки в предыдущей таблице. Ввести в базис строку с названием разрешающего столбца предыдущей таблицы.
-Построение ведущей строки в новой таблице.
Почленно поделить все элементы разрешающей строки на ведущий элемент.
-Построение других строк в новой таблице.
Почленно умножить ведущую строку на соответствующие этим строкам элементы разрешающего столбца из предыдущей таблицы и прибавить к соответствующим строкам в старой таблице.
6. Проверяем таблицу второго шага на оптимальность. Если в строке целевой функции нет отрицательных элементов, тогда таблица имеет оптимальный план, записать ответ. Если в строке ЦФ есть отрицательный элемент (элементы), тогда переходят к следующему (третьему) шагу, строят новую симплекс-таблицу в соответствии п.5 и затем проверяют ее на оптимальность. Построение таблиц заканчивается с нахождением оптимального плана.
Прямая задача на минимум решается следующим образом:
-Написать математическую модель двойственной задачи в стандартном виде
|
|
-Решить двойственную модель симплекс - методом
-Записать ответ.
Связь между задачами двойственной пары в том, что, решая симплексным методом одну из них, автоматически получаем решение другой.
Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач в последней симплекс-таблице.
Х1 | x2 | … | xn | S1 | S2 | … | Sm |
S1 | S2 | … | Sm | y1 | y2 | … | ym |