Переход к канонической форме.

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

При необходимости задачу максимизации можно заменить задачей минимизации, и наоборот. Для функции одной переменной это утверждение очевидно. В самом деле, если x* — точка минимума функции y = f ( x ), то для функции y = – f ( x ) она является точкой максимума, так как графики функций f ( x ) и – f ( x ) симметричны относительно оси абсцисс (рис. 2.1).

рис. 2.1

Итак,

min f ( x* ) = – mаx ( – f ( x* )).

То же самое имеет место и в случае функции n переменных:

min f ( x₁* , ..., x_n* ) = – mаx ( – f ( x₁* , ..., x_n* )).

Таким образом, если в исходной ЗЛП целевая функция максимизируется,

т. е. , (2.27)

то выполнив замену Z₁=–Z, получаем новое выражение

(2.28)

и эквивалентную ЗЛП.

Как следует из примеров задач линейного программирования, в них большинство ограничений задается неравенствами. Для перехода к канонической форме необходимо заменить все неравенства на строгие равенства.

Пусть исходная ЗЛП имеет вид

, (2.29)

, (2.30)

, (2.31)

. (2.32)

Преобразуем ее к каноническому виду. Введем m дополнительных (балансовых) неотрицательных переменных x_n+i  0 ( i = ). Для того чтобы неравенства типа  (2.30) преобразовать в равенства, к их левым частям прибавим дополнительные переменные x_n+i  (i = ), после чего система неравенств (2.30) примет вид

. (2.33)

Для того чтобы неравенства типа   (2.31) преобразовать в равенства, из их левых частей вычтем дополнительные переменные x_n+i  ( i = ) . Получим

. (2.34)

Систему уравнений (2.33), (2.34) с условием неотрицательности дополнительных переменных называют эквивалентной системе неравенств (2.30), (2.31).

Дополнительные переменные x_n+i  ( i = ) в целевую функцию вводятся с коэффициентами, равными нулю. Получим задачу:

; (2.35)

, (2.36)

, (2.37)

. (2.38)

Задача (2.35)—(2.38) имеет каноническую форму. Задачи (2.29)—(2.32) и (2.35)—(2.38) тесно связаны между собой.

Т е о р е м а 1. Каждому допустимому решению задачи (2.29)—(2.32) соответствует вполне определенное допустимое решение задачи (2.35)—(2.38), где x_n+i  0 (i = ), и наоборот, каждому допустимому решению задачи (2.35)—(2.38) соответствует допустимое решение решению задачи (2.29)—(2.32).

Д о к а з а т е л ь с т в о. Пусть — допустимое решение задачи (2.29)—(2.32). Для условий (2.30) обозначим

, (2.39)

для условий (2.31) —

. (2.40)

Из условий (2.39) и (2.40) следуют условия (2.36)—(2.38). Отсюда x⁰ =  есть определенное допустимое решение задачи (2.35)—(2.38).

Аналогично доказывается обратное утверждение. Теорема доказана.

Так как дополнительные переменные входят в целевую функцию (2.35) с коэффициентами, равными нулю, то значения целевых функций (2.29) и (2.35) при соответствующих допустимых решениях и одинаковы. Отсюда следует, что целевые функции (2.29) и (2.35) на множестве соответствующих допустимых решений достигают экстремального значения одновременно. Оптимальному решению задачи (2.29)— (2.32) соответствует оптимальное решение задачи (2.35)—(2.38), т. е. исходная задача и ее каноническая форма эквивалентны.

Отметим экономический смысл дополнительных переменных. Они в каждой задаче прямо связаны с ее экономическим содержанием.

Например, для задачи о наилучшем использовании ресурсов

, (2.41)

т. е. дополнительная переменная показывает величину неиспользованного ресурса. Для задачи о смесях

, (2.42)

т. е. дополнительная переменная показывает потребление соответствующего питательного вещества в оптимальном плане сверх нормы.

В ряде производственно-экономических ситуаций не на все переменные налагаются условия неотрицательности. В подобных ситуациях, даже если ограничения представлены в виде равенств, задача не будет канонической. Для представления такой задачи в каноническом виде каждую из переменных x_k , на которые не наложено условие неотрицательности, заменим разностью двух неотрицательных переменных и , т. е. , где . Очевидно, что при этом мы получим эквивалентную задачу.

И, наконец, рассмотрим два последних признака того, что ЗЛП представлена в каноническом виде. Это наличие в системе ограничений исходного базиса при неотрицательности всех свободных элементов данной системы; другими словами, наличие в системе ограничений выделенного исходного опорного решения.

Ï ð è ì å ð  1.  Привести к канонической форме следующую задачу линейного программирования:

Р е ш е н и е . 

1) Минимизируем целевую функцию задачи путем введения новой функции Z₁ : .

2) В системе ограничений ЗЛП перейдем к строгим равенствам, для чего введем неотрицательные «балансовые» переменные x₄ и x₅ в левые части неравенств со знаками минус и плюс (в зависимости от знака неравенства). В результате ЗЛП запишется в следующем виде:

3) Перейдем к преобразованию условий неотрицательности. Данное условие не наложено только на одну переменную x₁ (назовем ее произвольной). Исключим эту переменную из задачи, выполнив следующую замену переменных:

где .

При этом получаем следующее:

4) Выделяем в системе ограничений базис при неотрицательных свободных членах.

Таким образом, получаем окончательно следующую каноническую форму для данной задачи линейного программирования: