Линейное программирование.
Задачи линейного программирования: Функция F – линейная , множество P есть множество решений конечной системы линейных неравенств.
Линейное программирование (ЛП) относится к классу оптимизационных задач с ограничениями и вызвано потребностью решения задач, связанных с экономикой, планированием и организацией производства (составлением графиков, проблемами запасов, размещением оборудования, составлением смесей, транспортными задачами и т.п.).
В общей форме задача ЛП формулируется следующим образом: найти минимальное (максимальное) значение целевой функции Z(x1, x2, . . . , xn ), линейно зависящей от n параметров при наложенных ограничениях в виде системы линейных неравенств и равенств. Различными приемами равенства можно преобразовать в неравенства и наоборот. В стандартной форме задачи ЛП ограничения рассматриваются в виде неравенств. В настоящее время единого алгоритма решения всего необычайно большого разнообразия задач ЛП не существует и все методы основаны на направленном переборе некоторых вариантов решения с его последовательным улучшением.
Для двух (и в какой-то мере трех) переменных возможен геометрический (графический) метод решения, который позволяет наглядно интерпретировать основные идеи при решении задач ЛП.
Пусть задана линейная целевая функция двух независимых параметров
Z= с1x1+с2x2
и ограничения в виде совместной системы линейных неравенств
a11x1+a12x2 b1
a21x1+a22x2 b2
. . . . . . . . . . . .
am1x1+am2x2 bm
при условии неотрицательности переменных
x1 0, x2 0
Для определенности будем считать, что требуется найти значения x1 и x2 , доставляющие максимум целевой функции Z.
Областью решений системы неравенств и является многоугольник G, образуемый пересечением конечного числа полуплоскостей, описываемых этими неравенствами (Рис.1.). Граничными прямыми, отделяющими эти полуплоскости, являются равенства ai1x1+ai2x2 = bi (i =1,2,…,n),
а условия неотрицательности определяют полуплоскости с граничными прямыми
x1 = 0, x2 = 0.
О Рис.1. Поиск максимума
Для того, чтобы определить максимум целевой функции Z, необходимо изобразить графически ее линии уровня, т.е. линии, на которых функция Z имеет постоянные значения Z=const . При увеличении константы линия уровня будет перемещаться параллельно самой себе в направлении вектора нормали N к ней, при уменьшении – в противоположном направлении . Линия уровня, касающаяся многогранника G в одной точке, называется опорной прямой. Очевидно, что на опорная прямая, касающаяся многогранника в точке 3 и будет оптимальным решением (планом), т.к. функция Z этой прямой будет иметь максимальное значение.