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

Ответ: Геометрическая интерпретация задачи позволяет наглядно определить структуру, выявить особенности и открыть пути исследования более сложных свойств. Задачи линейного планирования с двумя переменными можно решить графически. В трехмерном пространстве графическое решение усложняется, а в n –мерном пространстве графическое решение невозможно. Случай двух переменных не имеет особого практического значения, однако его рассмотрение проясняет свойства общей задачи линейного планирования, приводит к идее ее решения, делает геометрически наглядными способы решения и пути их практической реализации. Пусть дана задача: определить параметры Х₁ ≥ 0, X₂ ≥ 0, обеспечивающие максимум целевой функции и удовлетворяющие условиям ограничений

max Z = c₀ + c₁x₁ + c₂x₂; (5.10) a₁₁x₁ + a₁₂x₂ ≤ b₁, a₂₁x₁ + a₂₂x₂   b₂, ………………………. (5.11)

a_m1x₁ + a_m2x₂ ≥ b_m. Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (5.11) задаёт на плоскости х₁Ох₂ некоторую полуплоскость. Полуплоскость – выпуклое множество. Пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (5.10) – (5.11) есть выпуклое множество. Представим на рис. 5.1 возможные ситуации, когда область допустимых решений (ОДР) задачи линейного планирования (ЗЛП): а) выпуклый многоугольник; б) неограниченная выпуклая многоугольная область; в) единственная точка; г) луч; д) отрезок; е) пустое множество 

Рис.5.1

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП – непустое множество, например многоугольник АВСДЕ (рис.5.2). Выберем произвольное значение целевой функции Z = Z_o. Получим с₀ + с₁х₁ + с₂х₂ = Z₀. Это уравнение прямой линии. В точках прямой MN целевая функция сохраняет одно и то же постоянное значение Z₀. Считая в равенстве (5.12) Z параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

Рис.5.2

Возникает вопрос: как установить направление возрастания (убывания) целевой функции? Найдём частные производные целевой функции по х₁ и х₂:

 Z/   x₁ = c₁,   Z/   x₂= c₂. (5.12)

Частные производные (5.12) функции показывают скорость ее возрастания вдоль осей. Следовательно, с₁ и с₂ – скорость возрастания Z соответственно вдоль осей Ох₁ и Ох₂. Вектор G = (с₁;с₂) называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции: G= (   Z/   x₁,   Z/   x₂). Вектор – G показывает направление наискорейшего убывания целевой функции. Его называют антиградиентом. Вектор G= (с₁;с₂) перпендикулярен к прямым Z = const семейства с₀+с₁х₁+с₂х₂=Z. Из геометрической интерпретации элементов ЗЛП следует порядок её графического решения. 1. С учетом системы ограничений строим область допустимых решений. 2. Строим вектор G= (с₁;с₂) наискорейшего возрастания целевой функции – вектор градиентного направления. 3. Проводим произвольную линию уровня Z = Z₀ (проще всего провести линию Z = c₀, перпендикулярную к вектору G ). 4. При решении задачи на максимум перемещаем линию уровня Z = Z₀ в направлении вектора G так, чтобы она касалась ОДР в её крайнем положении (крайней точке) (на рис. – до точки Д). В случае решения задачи на минимум линию уровня Z = Z₀перемещаем в направлении антиградиента (на рис. – до точки В). 5. Определяем оптимальное решение, т.е. значения Х^* = (х₁^*; х₂^*) и экстремальное значение целевой функции Z^* = z( x^*). Из геометрической интерпретации условий ограничений и целевой функции возможно выявить особенности решения ЗЛП, а именно (см. рис.5.3):

Рис.5.3

1)оптимальное решение единственное: линия уровня и область допустимых решений в соответствующем положении имеют одну общую точку (рис.5.3, а); 2)оптимальных решений бесконечное множество: в соответствующем положении линия уровня проходит через сторону области допустимых решений (рис.5.3, б); 3)целевая функция не ограничена: линия уровня, сколько бы ее ни перемещали, не может занять соответствующего положения (рис.5.3, в,г); 4)область допустимых решений состоит из единственной точки, где целевая функция достигает одновременно и максимального, и минимального значений (рис. 5.3, д); 5)задача не имеет решения: область допустимых решений – пустое множество, т.е. система ограничений несовместна (рис.5.3, е). При количестве переменных более трех ЗЛП теряет геометрическую наглядность, но идея получения решения (графического) сохраняет смысл и для случая многомерного пространства.