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

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

Рис.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

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