Графическое решение задач с двумя неизвестными, заданных линейными неравенствами ограничений.

Для представления задачи линейного программирования в геометрической форме для каждого i-го ограничения в n-мерном пространстве задается полуплоскость (или гиперплоскость) решений. В результате пересечения всех полуплоскостей, определяемых ограничениями, образуется выпуклый многогранник допустимых решений.

Целевую функцию в n-мерном пространстве геометрически можно интерпретировать как семейство параллельных полуплоскостей, положение каждой из которых определяется значением параметра F.

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

На рис. 1 показано геометрическое представление некоторой задачи линейного программирования в двумерном пространстве с четырьмя ограничениями и целевой функцией вида . Выпуклым многогранником допустимых решений является многогранник ABCDE. Координаты любой его точки удовлетворяют как систему ограничений, так и условие неотрицательности переменных, поскольку он находится в первой координатной полуплоскости.

В том случае, если в системе ограничений будет не две, а три переменных, то каждое ограничение геометрически будет определяться гиперполуплоскостью трехмерного пространства. Если же в системе ограничений количество переменных больше, чем три (х₁, х₂, … х_n), то каждое ограничение определяет гиперполуплоскость n-мерного пространства.

Заметим что, если область допустимых решений неограниченна, то минимум или максимум линейной функции может и не достигаться.

Рис. 1 . Геометрическая форма представления задачи линейного программирования

 

Графический метод решения задач линейного программирования базируется на ее геометрической интерпретации и применяется, как правило, при количестве переменных n = 2 и в отдельных случаях при n = 3 (трехмерное пространство). Ограниченное использование графического метода обусловлено сложностью построения многогранника решений в трехмерном пространстве (для задач с тремя переменными), а графическое изображение задачи с количеством переменных больше трех вообще невозможно. Однако графический метод позволяет выработать у студентов наглядные представления о линейном программирование и подтвердить справедливость некоторых его теорем. В дальнейшем мы будем рассматривать и решать задачи линейного программирования графическим методом только в двумерном пространстве.

Согласно геометрической интерпретацией задачи линейного программирования каждое i-е ограничение-неравенство определяет полуплоскость с граничной прямой (і = 1, 2, …, т). Если графически изобразить общую часть, или пересечение всех указанных полуплоскостей, то мы получим множество точек, координаты которых удовлетворяют одновременно все ограничения задачи, это множество точек называют многогранником допустимых решений. Условие неотрицательности переменных означает, что область допустимых решений задачи принадлежит первому квадранту системы координат двумерного пространства. Целевая функция геометрически интерпретируется как семья параллельных прямых.

Проиллюстрируем решение задачи линейного программирования графическим методом на примере системы ограничений с двумя переменными.

 

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

Решение: Сначала нам необходимо получить область допустимых решений. Неравенство определяет полуплоскость с граничной прямой . Строим эту прямую (рис. 3.2, прямая (1)) и определяем полуплоскость допустимых решений. С этой целью в неравенство подставляем координаты какой-то характерной точки, например . Убеждаемся, что эта точка принадлежит выбранной полуплоскости и иллюстрируем этот факт соответствующими направленными стрелками. Аналогичным образом строим полуплоскости для остальных неравенств из системы ограничений задачи. В результате пересечения этих полуплоскостей получаем область допустимых решений – многогранник ОABCD.

Вектор нормали (иногда его называют также как радиус-вектор) задает направление роста значений целевой функции F. Целевая функция определяет семейство параллельных прямых с₁х₁ + с₂х₂ = const, которые называются линиями уровня и каждая из которых соответствует определенному значению целевой функции F. Первая линия уровня проходит через начало координат, при этом F = 0. При увеличении F линии уровня смещаются в направлении вектора, а при уменьшении – в направлении, противоположном вектору . На рис.2 построена прямая F = 0, которая располагается перпендикулярно вектору нормали.

 

Рис. 2. Графическое представление задачи

 

Допустимыми базисными решениями данной задачи являются угловые точки многогранника ОABCD, а одна (в отдельных случаях – две) из этих точек придает максимального значения целевой функции. В этом примере максимального значения целевая функция достигнет в точке B, т.е. в вершине многогранника области допустимых решений, которая является наиболее отдаленной от начала координат, если двигаться в направлении вектора .

Координаты точки B находим, решив систему из уравнений прямых № 1 и № 2, на пересечении которых эта точка находится:

Имеем систему двух линейных уравнений с двумя неизвестными, которую можно решить методами Крамера, Гаусса и некоторыми другими.

По методу Крамера решениями этой системы будут значения:

; .

Таким образом оптимальным планом задачи линейного программирования, который обеспечивает максимум целевой функции является точка B (1, 54; 7, 68).

Значение целевой функции в этой точке: .

Минимального значения целевая функция достигает в точке D. Если мы движемся в направлении противоположном вектору нормали , то данная точка является последней вершиной многогранника ОABCD через которую проходит линия уровня F. Прямая (3) пересекает ось 0х1 при х₁ = 2, следовательно координаты точки D (2, 0).

Оптимальным планом задачи линейного программирования, который обеспечивает минимум целевой функции является точка D ( 2, 0).

Значение целевой функции в этой точке: .

 

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: