Методы преобразования ограничений к каноническому виду
-
Если есть ограничения
то вводятся дополнительные переменные
для того, что бы превратить неравенство
в уравнение
.
Эти переменные
можно сделать базисными в симплекс-методе. -
Если есть ограничения
то можно преобразовать уравнения к
виду
то есть что бы некоторые переменные
входили только в одно уравнение с
коэффициентом +1. Тогда их можно сделать
базисными.
Можно
ввести искусственные переменные
и записать
Тогда, делая их базисными, необходимо
найти минимум
После обращения переменных
в ноль получим начальное допустимое
решение для основной задачи (при этом
переводим в небазисные и их в дальнейшем
можно и нужно не рассматривать в
симплекс-таблице основной задачи).
3.
Если есть ограничения
вводим
переменные
для того, чтобы прервать неравенства в
уравнения
Эти переменные нельзя использовать в
качестве базисных. Поэтому уравнение
необходимо преобразовать так, чтобы
некоторые переменные входили в уравнения
только один раз с коэффициентом +1. Тогда
эти переменные можно сделать базисными.
А можно ввести искусственные переменные
и получить уравнения
сделать искусственные переменные
базисными и на первом этапе добиться
обращения их в ноль путем минимизации
функции
тем самым получить допустимое базисное
решение для исходной задачи, то есть
второго этапа.
Замечания
Часто ограничения можно чуть изменить, особенно, если незначительное увеличение ресурсов приводит к значительному изменению целевой функции. Это осуществляется с помощью анализа чувствительности – оценки влияния параметров на оптимальное решение.
В заключение приведем примеры типичных задач ЛП и методы их решения, а также рассмотрим такой вопрос, как двойственность задач ЛП.