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

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

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

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

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

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

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

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

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

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

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

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

f=x₁+x₂→max

Геометрический метод решения задачи ЛП - student2.ru -3x₁+2x₂≤6

x₁+2x₂≥2

0≤x₁≤3, x₂≥0

x₂

Геометрический метод решения задачи ЛП - student2.ru 3

Геометрический метод решения задачи ЛП - student2.ru 2

Геометрический метод решения задачи ЛП - student2.ru -2 -1 0 1 2 3 x₁

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

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

Геометрический метод решения задачи ЛП - student2.ru 3x₁+2x₁=6