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

Date: 2015-10-07; view: 524.

Общая задача линейного программирования имеет вид:

(1)

(2)

(3)

Система m линейных уравнений и неравенств с n неизвестными (1) называется системой ограничений; условие (2) — условием неотрицательности переменных, оно вытекает из экономического смысла вводимых переменных.

Если система ограничений (1) содержит линейные неравенства и уравнения, то задача называется общей, если только уравнения — основной. Частным случаем основной задачи является задача каноническая, определение которой будет дано ниже. Любая задача линейного программирования (ЛП) может быть записана в одной из трех форм: общей, основной или канонической.

Вектор , удовлетворяющий системе ограничений (1) и условию неотрицательности (2), называется планом задачи.

Оптимальным называется такой план , при котором линейная функция (3) принимает оптимальное (максимальное или минимальное) значение, т.е.

для ; для .

Функция называется целевой функцией.

Решение задачи ЛП заключается в нахождении оптимального плана Х^* и вычислении значения целевой функции на этом плане .

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

При n =2 задача ЛП имеет вид:

(4)

(5)

(6)

Каждое линейное неравенство системы (4) на плоскости определяет полуплоскость с границей, задаваемой прямой ; условия неотрицательности (5) определяют две полуплоскости с границами .

Если система (4)—(5) совместна, то пересечение полуплоскостей образует выпуклый многоугольник, внутренние и граничные точки которого образуют множество планов. (Напомним, что область называется выпуклой, если она полностью включает в себя отрезок, соединяющий любые две точки области). Этот многоугольник может быть ограниченным или представлять собой бесконечную выпуклую область.

В случае несовместности системы (4)—(5) множество планов пусто.

Линейная функция является функцией двух переменных. Из теории известно, что градиент функции — вектор, координатами которого являются частные производные , т.е. — в каждой точке перпендикулярен линии уровня и указывает направление наискорейшего возрастания функции.

Линиями уровня является множество параллельных прямых =С (где С— произвольная постоянная); вектор grad F= перпендикулярен к ним и направлен в сторону наибольшего возрастания функции.

Решение задачи (4) — (5) сводится к отысканию такой точки Х^* области планов, через которую проходит та из прямых , которая соответствует наибольшему (наименьшему) значению функции .

Построив прямую , параллельным переносом ее перемещают по области планов в направлении grad F, если или в противоположном направлении, если .

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

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

Пример. Решить задачу ЛП:

.

.

Поскольку задача содержит 2 переменные, решение можно найти графически.

Построим область планов задачи, определяемую системой ограничений и условиями неотрицательности переменных. Каждое из неравенств определяет полуплоскость с границей, задаваемой прямой. Выпишем соответствующие уравнения прямых, пронумеруем их. Прямую однозначно можно провести через любые две точки, в качестве которых удобно выбирать точки пересечения с осями координат. Координаты первой точки получим при подстановке в уравнение х₁=0, откуда легко вычисляется х₂; координаты второй точки — при подстановке в уравнение х₂=0, откуда находим х₁.

Проведем по двум точкам прямые (1) — (4), прямые (5) и (6) совпадают с осями координат х₂ и х₁ (рис.1).

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

х₂ (5)

(2)

6 F(X^*) =F_min

А= X^*

3 F(Х)=0

В=X^* (4)

F(Х^*)=F_max

-2 0 4 5 9 (6) х₁

(3) (1)

-2

grad F(X)

Рис.1.

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

Подставим в первое неравенство х₁=0 и х₂=0, получим неравенство . Это верно, следовательно, начало координат — точка (0;0) — принадлежит полуплоскости решений; помечаем стрелками нижнюю от прямой (1) полуплоскость.

При подстановке точки (0;0) во второе неравенство получаем: 0 –8. Это верно, поэтому помечаем полуплоскость, содержащую начало координат.

Для третьего неравенства при подстановке координат пробной точки получаем неверное утверждение 0 12, следовательно, решением данного неравенства будет полуплоскость, не включающая начало координат.

Подстановка координат точки (0;0) в четвертое неравенство приводит к верному неравенству 0 10; решение содержит начало координат.

Условия неотрицательности определяют полуплоскости справа от прямой х₂=0 и вверх от прямой х₁=0.

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

Найдем максимальное и минимальное значения целевой функции на области планов. Рассмотрим произвольную линию уровня, например, . Прямую построим по точкам (0;0) и (3;1). Направление наискорейшего возрастания указывает вектор grad F(X)=(1;–3).

Для определения максимума целевой функции на области планов нужно параллельным переносом сдвигать прямую в направлении grad F(X). По рисунку можно определить, что целевая функция максимальна в точке В, т.е. F_max=F(X*)=F(B). Точка В образована пересечением прямых (4) и (6); ее координаты В(5;0). На оптимальном плане Х^*=(5;0) достигается F_max=F(X*)= =5.

Для определения наименьшего значения на области планов нужно параллельным переносом сдвигать прямую в направлении, противоположном grad F(X). Наименьшее значение целевой функции достигается в точке А, являющейся пересечением прямых (1) и (2), т.е. F_min=F(X^*)=F(A) . Координаты точки А найдем, решив систему уравнений:

Умножим первое уравнение на 2 и вычтем из него второе:

11х₂= 44, х₂= 4. Тогда х₁=1/2(18 – 12)= 3. Координаты точки А(3;4). Оптимальным является план Х^*=(3;4), на котором оптимальное значение целевой функции F_min=F(X^*)=F(A)= .

Если количество переменных системы (1.1)—(1.2.) больше двух, задача не допускает наглядного графического решения.