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

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

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

(1).

m линейных алгебраических уравнений с n неизвестными и линейная форма.

(2).

относительно этих же производных.

Требуется среди всех неотрицательных решений заданной системы (1) выбрать такое, при котором форма F принимает наименьшее (или наибольшее) значение, то есть минимизируется (или максимизируется).

Определение 1. Система (1) называется системой ограничений данной задачи.

Замечание 1. В ряде задач неизвестные должны удовлетворять не только равенствам, но и неравенствам. Эти неравенства также называются ограничениями задачи.

Определение 2. Всякое решение, удовлетворяющее системе (1), назовем допустимым или опорным.

Определение 3. Допустимое решение системы (1), минимизирующее форму F, назовем оптимальным.

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

Обратимся теперь к изучению системы ограничений (1). Задача имеет смысл лишь в том случае, когда система (1) совместна, т. е. когда (согласно теореме Кронекера — Капелли) ранги основной и расширенной матриц системы совпадают. Как известно из линейной алгебры, этот общий ранг r не может превосходить числа n неизвестных. При r=n решение системы (1) единственно и находится, например, по теореме Крамера. Если это решение допустимо то оно, очевидно, и является оптимальным (так как никаких других решений нет). Если же среди чисел имеется хотя бы одно отрицательное, то задача не имеет решения. В самом деле, оптимального решения не существует потому, что оно по самому определению должно быть неотрицательным, а единственное имеющееся решение таковым не является.

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

Покажем, как это сделать.

1) Очевидно, что форма F достигает наибольшей величины при тех же самых значениях неизвестных, при которых форма достигает наименьшей величины. Следовательно, максимизация формы F равносильна минимизации формы Тем самым задача максимизации сводится к задаче минимизации.

Замечание 4. Ясно, что наибольшее значение формы F равно наименьшему значению формы, взятому с обратным знаком.

• 2) Допустим теперь, что среди ограничений задачи имеется некоторое неравенство. Его всегда можно записать в виде
• (3)

Введем новую, так называемую добавочную, неизвестную, связанную с неизвестными уравнением.

(4).

Очевидно, что условие неотрицательности величины эквивалентно выполнимости неравенства (3). Иными словами, если система неотрицательных значений переменных удовлетворяет уравнению (4), то система удовлетворяет неравенству (3). И обратно, если величины неотрицательны и удовлетворяют неравенству (3), то величина найденная из уравнения (4), окажется неотрицательной.

Итак, ограничение — неравенство (3) эквивалентно ограничению — равенству (4). Следовательно, ценою введения в задачу добавочных неизвестных удается все ограничения — неравенства заменить ограничениями — равенствами. При этом число добавочных неизвестных равно числу ограничений — неравенств в исходной задаче.

При решении системы ограничений могут возникнуть следующие случаи:

• 1) Система ограничений несовместна, поэтому отыскать опорное решение невозможно (рис. 1).
• 2) Система ограничений имеет неограниченное множество решений (рис. 2).
• 3) Система ограничений имеет ограниченное, замкнутое множество решений (рис. 3).
• 4) Система ограничений имеет бесчисленное незамкнутое множество решений (рис. 4).

рис. 1 рис. 2 рис. 3 рис. 4