Тема 1. Задача линейного программирования (злп) і. Постановка задачи

Найти:

max F=(1.1)

X1,…,xn

при условиях:

a₁₁x₁ + a₁₂x₁ +...+a_1nx_n R₁ b₁;

a₂₁x₁ + a₂₂x₂ +...+a_2nx_n R₂ b₂;

……………………………………;

a_m1x₁ + a_m2x₂ +...+a_mnx_n R_m b_m; (1.2)

и

x₁x_{2 …}x_n (1.3)

Здесь R_i –один из знаков «», «», «=»;

С_j – коэффициенты целевой функции;

а_ij – коэффициенты ограничений

Іі. Основные определения

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

Значение целевой функции при любом из оптимальных решений называется оптимумом этой задачи. Если все R_i –представляют собой знак «=», т.е.

a₁₁x₁ + a₁₂x₁ +...+a_1nx_n = b₁;

a₂₁x₁ + a₂₂x₂ +...+a_2nx_n = b₂;

……………………………………; (1.4)

a_m1x₁ + a_m2x₂ +...+a_mnx_n = b_m;

x_j0 (j=1, 2, …,n),

то ЗЛП (1.4) называется канонической ЗЛП.

Введем обозначения:

С= (с₁, с₂, …, с_n),

Тогда каноническую ЗЛП можно записать в матричной форме:

(1.5)

Векторная форма:

; ;……;;

= (с₁, с₂, …, с_n), = (х₁, х₂, …, х_n),

Тогда (1.4.) примет вид:

(1.6)

Задача

(1.7)

Задача (1.7) называется симметричной, стандартной или естественной задачей ЛП.

Ііі. Геометрическая интерпретация злп

Рассмотрим пример:

Найти max(2x₁+5x₂)

При ограничениях

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

Рассмотрим теперь целевую функцию F(x₁, x₂)=2x₁+5x₂ .

Пусть F(x₁,x₂)=1000=Z. График уравнения2x₁+5x₂ =1000 представляет собой прямую с отрезками на осяхx₁=500 x₂=200.

При F(x₁,x₂)=1500, получим прямуюZ₂ , имеющую уравнение

Прямая Z₂ ||Z₁, но расположена выше ее. Двигая прямую вверх параллельно самой себе, приходим к такому положениюZ_max, когда прямая и множествоK будут иметь только одну общую точку А.Очевидно, что точка А(x₁=200, x₂=300) – оптимальное решение, т.к. она лежит на прямой с максимально возможным значениемZ_max. Заметим, что эта точка оказалась крайней точкой множестваК.

Нахождение решения задачи линейного программирования на основе ее геометрической интерпретации включает в себя следующие этапы:

1. Строят прямые, уравнения которых получаются в результате замены в ограничениях изнаков неравенств на знаки точных равенств.

2. Находят полуплоскости, определяемые каждым из ограничений задачи.

3. Находят многоугольник решений .

4. Строят вектор

5. Строят прямую c₁x₁+c₂x₂=h, проходящую через многоугольник решений (она перпендикулярна векторуF).

6. Передвигают прямую c₁x₁+c₂x₂=hв направлении вектораF, в результате чего, либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность сверху функции на множестве планов.

7. Определяют координаты точки максимума (минимума) и вычисляют значение целевой функции в этой точке.

Будем иметь ввиду, что оптимальные решения, если они существуют, достигаются в вершинах многогранника Ω.

При этом могут представиться следующие случаи:

min F=F(P₁); max F= F(P₂)

Решение задачи минимизации - координаты вершины Р₁, максимизации -координаты вершиныР₂.

min F=F(P₂); max F= F(P₁)

Решение задачи минимизации - координаты вершины Р₂, максимизации -координаты вершиныР₁.

рис.5

Пример:

Найти Fmах и Fmin :

F = х₁ + 1.5х₂,

2х₁ + Зх₂ 6

х₁ + 4х₂ 4

х₁0

х₂0

Уравнения границ многоугольника решений:

(1) 2х₁ + 3х₂ =6 (1)

Прямая F=0параллельна отрезкуР₁Р₂,minF достигается в каждой точке отрезкаР₁Р₂, уравнение которого

Итак, задача имеет бесчисленное множество точек минимума. Максимум достигается в точке P₃.

На рис. 4изображен случай неограниченности снизу линейной формыFна многограннике Ω.

На рис. 5 изображен случай несовместимости системы ограниченной задачи.

(II) x₁ + 4x₂ =4или(II)

(III) x₁ = 0 (III) x₁ = 0

(IV) x₂ = 0 (IV) x₂ = 0

Строим границы по закону соответствующего неравенства отмечаем штриховой полуплоскость - решение данного неравенства.

Далее строим нулевой уровень линейной формы F = x₁ +1,5х₂ =0, при этом gradF =(1; 1,5).

Fmin = F (P₁)

P₁ (0; 0)

Итак, точка минимума x₁ = 0, x₂ = 0.

Очевидно, (F=0)|| P₂P₃.

Задача имеет бесчисленное множество точек максимума.

Найдем координаты точки P₂ (x'₁, x'₂) и P₃ (x''₁, x''₂).

Точка Р₂лежит на пересечении прямых I и II. Решаем совместно эти уравнения.

2x₁ + 3x₂ = 6

x'₁ = 2,4; x'₂= 0,4

x₁ +4x₂ = 4

Точка P₃лежит на пересечении прямых I и IV.

2x₁ + 3x₂ = 6

x''₁ = 3; x''₂= 0

x₂ = 0

F max = F(P₂) = F(P₃) = F(P)

где Р -произвольная точка отрезкаP₂P₃

Fmax =x₁ +1,5х₂ =3

Пользуясь геометрической интерпретацией задачи линейного программирования, можно сделать выводы:

1. Если оптимальное решение задачи линейного программирования существует, то оно достигается в вершине многогранника решения Ω.

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

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