Приведение ЗЛП к канонической форме

Методические указания к проведению лекционного занятия

Тема № 9.2. Теория двойственности

План:

1. Приведение ЗЛП к канонической форме.

2. Опорное решение ЗЛП.

3. Переход к новому опорному решению.

4. Выражение целевой функции через свободные переменные. Оценки свободных переменных.

5. Признаки неограниченности целевой функции.

6. Признаки оптимальности опорного решения.

7. Симплексный метод.

8. Двойственные задачи.

9. Основные теоремы двойственности.

10. Двойственный симплексный метод.

Приведение ЗЛП к канонической форме

Рассмотрим теоретические положения, позволяющие решить ЗЛП симплексным методом.

Пусть ЗЛП задана в общем виде, а её требуется представить в канонической форме. В этом случае в левую часть каждого неравенства системы ограничений вводят дополнительную переменную по следующим правилам.

1) Если в системе ограничений общей ЗЛП содержится неравенство вида

,

то в левую часть этого неравенства добавляют положительную переменную х _n+1. Тем самым получают уравнение

.

2) Если в системе ограничений общей ЗЛП содержится неравенство вида

,

то от левой части этого неравенства вычитают дополнительную положительную переменную х _n+1. Тем самым получают уравнение

.

Дополнительные переменные вводятся в целевую функцию с нулевыми коэффициентами, поэтому не влияют на её значение.

Если ЗЛП имеет произвольно меняющиеся переменные, то каждую из них заменяют разностью двух неотрицательных переменных:

Если в ЗЛП необходимо перейти от нахождения минимума к нахождению максимума или наоборот, то достаточно изменить знаки всех коэффициентов целевой функции на противоположные, а в остальном задачу оставить без изменения. Полученные таким образом оптимальные решения задач на максимум и минимум совпадают, а значения целевой функции при оптимальных решениях отличаются только знаком.

Пример 1. Представить ЗЛП

F (Х) = max,

.

в канонической форме.

Решение. В системе ограничений есть два неравенства, заменим их на равенства. Для этого в левую часть первого неравенства добавим (поскольку знак «») положительную переменную х ₄, получим уравнение . От левой части второго неравенства вычтем (поскольку знак «») положительную переменную х ₅, получим уравнение . Тогда ЗЛП можно представить в канонической форме следующим образом:

F (Х) = max,

.