Линейное программирование.

Задачи линейного программирования: Функция F – линейная , множество P есть множество решений конечной системы линейных неравенств.

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

В общей форме задача ЛП формулируется следующим образом: найти минимальное (максимальное) значение целевой функции Z(x₁, x₂, . . . , x_n ), линейно зависящей от n параметров при наложенных ограничениях в виде системы линейных неравенств и равенств. Различными приемами равенства можно преобразовать в неравенства и наоборот. В стандартной форме задачи ЛП ограничения рассматриваются в виде неравенств. В настоящее время единого алгоритма решения всего необычайно большого разнообразия задач ЛП не существует и все методы основаны на направленном переборе некоторых вариантов решения с его последовательным улучшением.

Для двух (и в какой-то мере трех) переменных возможен геометрический (графический) метод решения, который позволяет наглядно интерпретировать основные идеи при решении задач ЛП.

Пусть задана линейная целевая функция двух независимых параметров

Z= с₁x₁+с₂x₂

и ограничения в виде совместной системы линейных неравенств

a₁₁x₁+a₁₂x₂ b₁

a₂₁x₁+a₂₂x₂ b₂

. . . . . . . . . . . .

a_m1x₁+a_m2x₂ b_m

при условии неотрицательности переменных

x₁  0, x₂  0

Для определенности будем считать, что требуется найти значения x₁ и x₂ , доставляющие максимум целевой функции Z.

Областью решений системы неравенств и является многоугольник G, образуемый пересечением конечного числа полуплоскостей, описываемых этими неравенствами (Рис.1.). Граничными прямыми, отделяющими эти полуплоскости, являются равенства a_i1x₁+a_i2x₂ = b_i (i =1,2,…,n),

а условия неотрицательности определяют полуплоскости с граничными прямыми

x₁ = 0, x₂ = 0.

О

Рис.1. Поиск максимума

Для того, чтобы определить максимум целевой функции Z, необходимо изобразить графически ее линии уровня, т.е. линии, на которых функция Z имеет постоянные значения Z=const . При увеличении константы линия уровня будет перемещаться параллельно самой себе в направлении вектора нормали N к ней, при уменьшении – в противоположном направлении . Линия уровня, касающаяся многогранника G в одной точке, называется опорной прямой. Очевидно, что на опорная прямая, касающаяся многогранника в точке 3 и будет оптимальным решением (планом), т.к. функция Z этой прямой будет иметь максимальное значение.

12