Замена неравенств уравнениями

Способы преобразования

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

То же самое имеет место и в случае функции переменных: максимизация некоторой функции при заданной совокупности ограничений эквивалентна минимизации функции при той же системе ограничений.

Итак, если в задаче ЛП требуется найти максимум линейной функции , то такая задача сводится к ОЗЛП путём изменения знака на противоположный.

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

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

(4.1) (4.2)

В результате получаем линейное уравнение, содержащее переменных:

. (4.3)

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

(4.4) (4.5)

Получим . (4.6)

Таким образом, если система ограничений задачи содержит неравенства, то, вводя в каждое из них свою неотрицательную дополнительную переменную, её можно преобразовать в систему уравнений.

При этом в целевую функцию каждая дополнительная переменная входит с коэффициентом, равным нулю.

Пусть исходная задача имеет вид (5.1)

; (5.2)

. (5.3)

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

Получим задачу: (6.1)

(6.2)

, . (6.3)

Задачи (5.1)-(5.3) и (6.1)-(6.3) тесно связаны между собой: каждому допустимому решению задачи (5.1)-(5.3) соответствует единственное допустимое решение задачи (6.1)-(6.3), и наоборот, каждому допустимому решению задачи (6.1)-(6.3) соответствует допустимое решение задачи (5.1)-(5.3).

Так как дополнительные переменные входят в целевую функцию с коэффициентами, равными 0, то значения функций и при соответствующих допустимых решениях одинаковы. Отсюда следует, что целевые функции на множестве соответствующих допустимых решений достигают экстремального значения одновременно. Оптимальному решению задачи (5.1)-(5.3) соответствует оптимальное решение задачи (6.1)-(6.3), то есть исходная задача и её каноническая формы эквивалентны.

Отметим экономический смысл дополнительных переменных. Они в каждой задаче прямо связаны с её экономическим содержанием. Например, в задаче о наилучшем использовании ресурсов дополнительная переменная показывает величину неиспользованного ресурса. В задаче о смесях дополнительная переменная показывает потребление соответствующего питательного вещества в оптимальном плане сверх нормы.

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