Геометрический метод решения задачи ЛП

Пусть задача ЛП задана в стандартной форме. Геометрически ОДР образуется пересечением m множеств, каждое из них определяется неравенством: a_i1x₁+a_i2x₂+...+a_inx_n≥b_i и представляет собой полупространство, лежащее по одну сторону от гиперплоскости a_i1x₁+a_i2x₂+...+a_inx_n=b_i

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

Линии уровня c₁x₁+c₂x₂+...+c_nx_n=const образуют семейство параллельных гиперплоскостей.

Вектор нормали к этим плоскостям c={c₁, c₂,…,cn}^T перпендикулярен этим параллельным плоскостям и определяет направление возрастания линейной формы.

 

Задача Задача имеет Задача имеет Задача

неразрешима единственное решение множество решений неограничена

 

Рис.4.1. Иллюстрация существования решений задачи ЛП.

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

Следует иметь в виду, что оптимум задачи ЛП достигается только в ограниченной точке допустимого множества. В отличии от задач нелинейного программирования в задаче ЛП оптимум всегда является глобальным.

 

Графическое решение задачи линейного программирования:

 

Геометрический метод применяется для решения задачи ЛП двух переменных, т. к. только в этом случае можно построить наглядно ОДР на плоскости. Метод состоит из двух этапов. На первом строится ОДР как пересечение полуплоскостей, каждая из которых задана неравенством – ограничением. После второго строится прямая c₁x₁+c₂x₂=a, где a -произвольное число. Мысленно сдвигаем эту прямую параллельно самой себе вправо – вверх, если мы максимизируем целевую функцию и влево – вниз, если минимизируем. Движение продолжается до тех пор, пока прямая ещё будет принадлежать ОДР. Точное решение получаем из решения системы двух уравнений, задающих соответствующие прямые, пересечение которых даёт решение на графике. Пример: решить графически задачу ЛП:

 

f=x₁+x₂→max

 

-3x₁+2x₂≤6

x₁+2x₂≥2

0≤x₁≤3, x₂≥0

 

 

x₂

А

 

 

 

 

 

 

 

 

 

3

 

 

2

 

 

 

 

-2 -1 0 1 2 3 x₁

 

 

Для графического решения задачи построим по двум точкам прямые 2x₂-3x₁=6; x₁+2x₂=2; x₁=3. После этого штрихуем те полуплоскости, которые удовлетворяют неравенствам (на рис. серыми линиями)и строим ОДР как пересечение заштрихованных полуплоскостей. Затем рисуем линию уровня x₁+x₂=2 (вместо цифры 2 можно было подставить любую).

Так как задача ставится на максимум целевой функции, мысленно сдвигаем прямую, соответствующую целевой функции, вверх-вправо, пока она еще будет принадлежать области, ограниченной серыми линиями. Очевидно, решение находится в точке А. Для нахождения точного решения нужно решить систему из двух уравнений:

3x₁+2x₁=6

x₁=3

Точное решение: x₁=3; x₂=7,5

 

Задания к лабораторным работам по теме "Линейное программирование"

Решить графическим методом следующие задачи линейного программирования:

 

1. f=x₁+x₂®max 2. f=x₁-2x₂®min

-3x₁+2x₂£6 x₁-x₂£1

x₁+2x₂³2 x₁+x₂³2

0£x₁£3 x₁-2x₂£2

x₂³0 x₁³0; x₂³0

 

3. f=x₁+2x₂®min 4. f=6x₁+7x₂®max

x₁³2 x₁-1³0

x₁+3x₂£3 x₂-1³0

x₁-x₂+1£0 x₁+x₂-3³0

-6x₁-7x₂+42³0

 

5. f=3x₁+2x₂®max 6. f=x₁+2x₂®max

x₁+x₂£1 x₁-x₂£1

3x₁+4x₂£12 x₁-2x₂£1

x₁³0; x₂³0 x₁³0; x₂³0

 

7. f=4x₁+5x₂®max 8. f=x₁+x₂®min

2x₁+3x₂£6 5x₁-2x₂£4

-x₁+x₂³3 -x₁+2x₂£4

x₁³0; x₂³0 x₁+x₂³4

 

9. f=2x₁+3x₂®max 10. f=x₁+3x₂®min

8x₁+5x₂£11 3x₁-x₂³0

-x₁+3x₂£1 2x₁-x₂£6

2x₁+7x₂³7 x₁+x₂£0; x₁£2

x₁³0; x₂³0 3x₁-x₂³-4

 

11. f=3x₁+x₂®min 12. f=x₁+x₂®max

0£x₁£2 0,5£x₁+x₂£1

x₁+x₂-2³0 x₁-2x₂£1

x₁-x₂+1£0 3x₁+2x₂£3

x₁³0; x₂³0

 

13. f=x₁+x₂®max 14. f=2x₁+x₂®min

x₁+x₂-5³0 2x₁-x₂³-2

x₁-x₂-5³0 x₁-x₂³-2

x₁£7 x₁£1; 2x₁-x₂³3