2015-10-16
1429
План.
5.1. Симплекс-метод.
5.2.Симплексные таблицы и алгоритм решения задач.
5.3. Применение симплексного метода в экономических задачах.
Симплекс-метод
Симплексный метод является универсальным, так как позволяет решать практически любую задачу линейного программирования, заданную в каноническом виде. Идея симплекс метода была разработана русским ученым Л.В. Канторовичем в 1939 г. На основе этой идеи американский ученый Д. Данцинг в 1949 г. разработал симплекс-метод, позволяющий решать любую задачу линейного программирования.
В настоящее время на основе этого метода разработан пакет программ для решения задач линейного программирования.
Идея симплексного метода (метода последовательного улучшения плана) заключается в том, что начиная с некоторого исходного опорного решения осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному. При этом перемещении значение целевой функции для задач на максимум не убывает. Так как число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение.
Симплексный метод состоит из трех основных элементов:
1) определения какого-либо первоначального допустимого базисного решения задачи;
2) правила перехода к лучшему решению;
3) проверки оптимальности допустимого решения.
Симплекс-метод состоит из двух вычислительных процедур:
- симплекс-метод с естественным базисом;
- симплекс-метод с искусственным базисом.
Выбор конкретной вычислительной процедуры осуществляется после приведения исходной задачи линейного программирования к каноническому виду.
Для применения симплекс-метода с естественным базисом ЗЛП в каноническом виде должна содержать единичную подматрицу порядка m, в этом случае очевиден первоначальный опорный план (неотрицательное базисное решение системы ограничений).
Симплексный метод с искусственным базисом применяется при отсутствии первоначального опорного плана исходной ЗЛП в каноническом виде. Такая ситуация возникает при наличии в исходном ограничении знаков «равно» либо «больше или равно».
