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

 

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

Для этого выбираем свободные переменные, например х₁ и х₂. Остальные переменные будут являться базисными. Их можно выразить через свободные переменные следующим образом:

Значения свободных переменных х₁ и х₂ откладываются по осям Ох₁ и Ох₂. Эти переменные не могут быть отрицательными, поэтому допустимые значения этих свободных переменных могут лежать только выше оси Ох₁ и правее оси Ох₂ (см. рис.1).

 

 

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

 

Базисные переменные также должны быть неотрицательными, т.е.

 

Пусть х₃ = 0, т.е.

.

Это уравнение прямой, которую можно построить в системе координат х₁Ох₂.

Прямая х₃ = 0 проходит таким образом, что по одну сторону от этой прямой лежат точки, соответствующие х₃ > 0, а по другую – соответствующие х₃ > 0. Поэтому х₃ = 0 делит всю область переменных х₃ на две полуплоскости – допустимых и запрещенных значений (см. рис.1).

Таким же образом строятся и все остальные ограничивающие прямые: х₄ = 0, х₅ = 0, … х_n = 0. Штриховкой отмечается допустимая область.

Каждая прямая соответствует обращению в 0 одной из переменных. В точках пересечения в 0 будут обращаться две переменные. Число (n - m) определяет число свободных переменных. Их обращение в 0 соответствует базисному решению. Все переменные в совокупности ограничивают область допустимых решений (ОДР), которая представляет собой выпуклый многоугольник (рис.2).

 

 

Рис. 2. Выделение области допустимых решений

 

Цель задачи заключается в нахождении оптимального решения, которое обращает линейную функцию цели при n – m = в min (max). Этой задаче можно дать геометрическую интерпретацию. Для этого подставим в уравнение целевой функции значения базисных переменных. Получим

,

где - свободный член (его в первоначальном виде не было, но он может появиться при переходе к переменным х₁ и х₂).

Допустим, что

.

Тогда получаем уравнение прямой на плоскости х₁Ох₂. Угловой коэффициент этой прямой равен . На оси ординат эта прямая отсекает отрезок, равный .

При изменении величины Q угловой коэффициент прямой не изменится. Изменяется только начальная ордината, т.е. прямая перемещается параллельно самой себе, образуя линии равного уровня целевой функции.

Если , то поученная прямая проходит через начало координат (рис. 3).

 

 

Рис. 3. Образование линий равного уровня целевой функции

 

Направление, в котором должна двигаться основная прямая, чтобы величина Q убывала, зависит от знаков коэффициентов . Если оба коэффициента положительны, то прямая будет двигаться вниз и влево (рис. 4а) и т. д. Направление движения прямой при различных коэффициентах показаны на рис. 4.

 

 

Рис. 4. Направления убывания Q линий равного уровня целевой функции при различных коэффициентах:

а - ; б - ; в - ; г - .

Функция цели L достигает максимального значения, когда прямая будет проходить через крайнюю точку области допустимых решений, наиболее удаленную от начала координат. Координата этой точки (х₁, х₂) определяет оптимальное решение задачи линейного программирования.

Для примера найдем максимальное значение функции цели

F= 4x₁ + 3x₂

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

Решим эту задачу графически. Сначала построим область допустимых значений для двух ограничений: х₁>5 и x₂>15 (рис. 5).

 

Рис. 5. Область допустимых значений для х₁>5 и х₂>15

 

Область допустимых значений для х₁ будет располагаться справа от прямой х₁=5, а для х₂ – сверху от прямой х₂ = 15.

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

Найдем оптимальное решение задачи. Пусть

F= 4x₁ + 3x₂ = Q.

Если Q=0, то прямая F проходят через начало координат. С увеличением значения Q прямая будет перемещаться в направления, указанном на рис. 6.

 

 

Рис. 6. Направление движения прямой F при увеличения значений Q

 

Максимальное значение целевой функции приходится на одно из крайних положений прямой F в пределах области допустимых значений. Оптимальное решение считается найденным, если точка пересечения прямой F с наиболее удаленной (по ходу F) вершиной выпуклого многогранника ABCDE. В нашем примере такой точкой будет точка D(30, 20) (рис. 7).

 

 

 

Рис. 7. Оптимальное решение задачи

 

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

F= 4x₁ + 3x₂ = 4∙30+3∙20=180.

Если увеличить число переменных таким образом, что n – m = 3, то для геометрической интерпретации необходимо пространственное построение объемной области допустимых решений. Область допустимых решений (если она существует) представляет собой выпуклый многоугольник (рис. 8).

 

 

 

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

в случае n – m=3.

 

Вместо прямой постоянного уровня целевой функции для n – m = 2, в случае n – m = 3 возникает поверхность постоянного уровня целевой функции. Ее уравнение

.

Если количество свободных переменных х₁, х₂, х₃ больше 3, то решение задачи линейного программирования можно осуществлять геометрическим построением выпуклого многогранника допустимых решений в неотрицательном октанте n-мерного функционального пространства.

 

Проверьте себя.

Найдите геометрическим способом оптимальное решение задачи

F=20x₁+35x₂ ® min

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