23. Линейное программирование. Задача линейного программирования.
Задачи линейного программирования (ЗЛП) - простейшей тип оптимизационных задач. Постановка данной задачи выглядит следующим образом. Имеется множество переменных X=(x1,x2,...,xn).Целевая функция линейно зависит от управляемых параметров:
Имеются
ограничения,
где
Задача линейного программирования формулируется так: определить максимум линейной формы F(x1,x2,...,xn) = max (c1x1+c2x2+...+cnxn) |
(3) |
при условии, что точка (x1,x2,...,xn) принадлежит некоторому множеству D, которое определяется системой линейных неравенств
|
(4) |
Любое множество значений (x1*,x2*,...,xn*) , которое удовлетворяет системе неравенств (4) задачи линейного программирования, является допустимым решением данной задачи. Если при этом выполняется неравенство
c10x10+c20x20+...+cn0xn0
c1x1+c2x2+...+cnxn
для всего множества значений x1,x2,...,xn, то значение x10,x20,...,xn0 является оптимальным решением задачи линейного программирования.
Задачу линейного программирования удобно представлять в векторной форме, тогда она будет выглядеть следующим образом:
Найти
max F(x) = max (c'x) при условии AX
P0
; X
0,
где c' = (c1,c2,..,cn) представляет собой
n-мерный вектор, составленный из
коэффициентов целевой функции, причем
c' - транспонированная вектор-строка; x
= (x1,x2,...,xn) - n мерный вектор переменных
решений;
P
- m мерный вектор свободных членов
ограничений, матрица
A размера (m x n) матрица, составленная
из коэффициентов всех линейных
ограничений:
24. Линейное программирование. Пример Задачи линейного программирования.
Пример задачи линейного программирования. Рассмотрим двухмерную задачу линейного программирования. Пусть требуется найти максимум линейной формы
maxF(x1,x2)=max(x1+2x2)
при условии
x1+x2 120
0 x1 100
0 x2 75
Изобразим область, описываемую совокупностью ограничений на плоскости x1o x2 (рисунок). Переменные x1 и x2 неотрицательные, поэтому множество точек (x1,x2), являющихся возможными решениями задачи, находятся в I квадранте . Заменим знак в x1+x2 120 на знак равенства , получим уравнение прямой: x1+x2=120 .
Эта прямая делит плоскость на две полуплоскости. Все точки одной полуплоскости удовлетворяют неравенству x1+x2>120, другой - неравенству x1+x2<120. Построив аналогичные прямые x1=100 и x2=75, получим многоугольник, множество точек которого (x1,x2) удовлетворяет всем неравенствам. Этот многоугольник и представляет собой область допустимых решений D.
Из множества точек (x1, x2) многоугольника необходимо выбрать такую, в которой функция F(x1, x2) = (x1+2x2)принимает максимальное значение. Для некоторого фиксированного значения F* линейная функция F*(x1,x2) =(x1+2x2) представляет собой прямую линию. Задаваясь различными значениями F*, получим семейство параллельных прямых. Увеличение значений линейной функции соответствует перемещению прямой параллельно самой себе вверх. Следовательно, как видно из рис.2.1, максимальное значение целевой функции на допустимом множестве точек соответствует прямой, проходящей через точку z пересечения прямых x1+ x2=120 и x2=75. Решив эту систему, получим x1=45. Тогда максимальное значение функции F= max(x1+2x2)=195.
