6.3. Задачи линейного программирования

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

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

Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

• задача об оптимальном использовании ресурсов при производственном планировании;

• задача о смесях (планирование состава продукции);

• задача о нахождении оптимальной комбинации различных видов выпускаемой продукции

• транспортные задачи (перемещение грузов).

• анализ размещения социальных и производственных объектов (предприятий).

Рассмотрим общую постановку задач ЛП, некоторые схемы типичного применения и методы их решения.

6.3.1. Общая постановка задачи

Задача линейного программирования (ЛП) формулируется в общем виде следующим образом [7]: требуется найти экстремум (min/max) линейной функции n независимых переменных (проектных параметров) x₁, x₂, .., x_n :

при ограничениях, наложенных на переменные в виде линейных неравенств (или равенств), m>n :

Линейную функцию (6.4) – функцию цели принято называть линейной формой задачи ЛП.

Напомним, что множество параметров удовлетворяющих системе ограничений (6.5), называется областью допустимыми решениями задачи (ОДР ).

Допустимое решение , дающее экстремум функции цели (6.4), называется оптимальным решением.

Наряду с задачей ЛП (6.4-6.5), называемой стандартной, существуют и другие задачи ЛП, имеющие различные формы записи. Например, система неравенств (6.5) может быть смешанной, т.е. наряду с неравенствами система ограничений может содержать и равенства, или проектные параметры могут быть не все неотрицательны. И наконец, в ряде случаев требуется найти максимум линейной формы, Z_max. Любая из них может быть сведена путем несложных математических преобразований к эквивалентной ей задаче любого другого вида.

6.3.2. Геометрический смысл системы линейных неравенств

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

Случай двух проектных параметров.

Начнем с рассмотрения одного линейное неравенство с двумя параметрами х₁, х_{2 :}

_{Областью решения неравенства (6.6), является множество точек, удовлетворяющих этому неравенству, т.е. полуплоскость Р, ограниченная прямой} L:

Прямая L разбивает всю плоскость на 2-е полуплоскости. Для определения какую из двух полуплоскостей описывает неравенство (6.6), достаточно выбрать точку из одной из полуплоскостей. И если координаты этой точки удовлетворяют неравенству, то оно и описывает именно эту полуплоскость. Самою прямую L считаем принадлежащей этой полуплоскости

• Пример 6.1. Найти полуплоскость, определяемую неравенством:

Рассмотрим прямую , разбивающую всю плоскость на две полуплоскости. Выбрав точку М(0,0), легко убедиться, что координаты ее не удовлетворяют исходному неравенству. Это означает, что неравенство определяет полуплоскость, расположенную «выше» этой прямой и самою эту прямую (рис.6.5).

Рис.6.5. Область решения неравенства

Случай m (m>1) неравенств.

Предположим теперь, что задано не одно неравенство, а система из m неравенств:

Каждое неравенство определяет некоторую полуплоскость P_i, (i=1,2,..,m). Областью допустимых решений системы неравенств (6.7) является некоторая многоугольная область , полученная в результате пересечения конечного числа полуплоскостей, описываемых каждым отдельным неравенством. _{Если эта область ограничена, то ее называют многоугольником допустимых решений системы (6.7).}

Область решения системы (6.7) может быть замкнутой ограниченной (рис.6.6,а) или замкнутой неограниченной многоугольной областью (рис.6.6,б), а может быть и пустой (рис.6.6,в), когда система (6.7) противоречива.

a)	б)	в)

Рис.6.6. Области допустимых решений системы неравенств

Областью допустимых решений обладает важным свойство - она является выпуклой.

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

Рис. 6.7.а. Выпуклый многоугольник	Рис. 6.7.б. Невыпуклый многоугольник

Выпуклость многоугольника решений вытекает из способа его построения: он получен путем пересечения нескольких полуплоскостей.