Формы записи задачи линейного программирования

ФОРМЫ ЗАПИСИ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ИХ ЭКВИВАЛЕНТНОСТЬ И СПОСОБЫ ПРЕОБРАЗОВАНИЯ

Основные виды записи ЗЛП

Общей задачей линейного программирования называют задачу

(1.1)

при ограничениях: (1.2)

(1.3)

(1.4)

(1.5)

- произвольные (1.6)

где , , - заданные действительные числа; (1.1) – целевая функция;

(1.2)-(1.6) – ограничения; - переменные.

Симметричной формой записи ЗЛП называют задачу

(2.1)

≥ (2.2)

(2.3)

или задачу (2.4)

≤ (2.5)

(2.6)

В экономической практике задача (2.1)-(2.3) (или (2.4)-(2.6)) встречается наиболее часто.

Канонической формой записи ЗЛП или основной задачей линейного программирования (ОЗЛП) называют задачу

(3.1)

═ (3.2)

(3.3)

Рассмотрим ещё два употребительных вида записи – матричную и векторную. В модель (3.1)-(3.3) введём обозначения:

, , , ,

где — матрица-строка; — матрица системы уравнений; — матрица-столбец переменных; — матрица-столбец свободных членов.

Каноническая форма задачи примет вид:

;

= , ;

или , , .

Полезной является также векторная форма ЗЛП. Для столбцов матрицы введём обозначения:

, , …, , …, .

Тогда задача (3.1)-(3.3) в векторной форме записи примет вид:

;

, ,

где — скалярное произведение векторов и .

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

y

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

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

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

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

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

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

(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), то есть исходная задача и её каноническая формы эквивалентны.

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

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

Переход к симметричной форме записи

Пусть в ЗЛП имеются ограничения-равенства . Каждое такое ограничение-равенство эквивалентно системе неравенств , .

Неравенство вида умножением обеих частей на -1 превращается в неравенство вида , и наоборот.

Пример 1. Пример 2.

Привести задачу к каноническому виду. Привести задачу к каноническому виду.

. .

Каноническая форма задачи: Каноническая форма задачи:

. .