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

При рассмотрении геометрического метода решения задачи линейного программирования ограничимся рассмотрением совместной системы линейных неравенств с двумя и тремя переменными. Пусть, кроме того, задана линейная функция L = c₁x₁ + c₂x₂ + c₀. Найдем среди множества точек (x₁, x₂) из области решений совместной системы неравенств такие, которые придают линейной функции L = c₁x₁ + c₂x₂ + c₀ наименьшее (наибольшее) значение. Для каждой точки плоскости функция L принимает фиксированное значение L = L₁. Множество таких точек есть прямая c₁x₁ + c₂x₂ + c₀ = L₁, расположенная нормально к вектору С(с₁,с₂), выходящему из начала координат. Если эту прямую передвигать параллельно самой себе в положительном направлении вектора С, то линейная функция L = c₁x₁ + c₂x₂ + c₀ будет возрастать, а в обратном направлении – убывать. Пусть при движении прямой L в положительном направлении вектора С она впервые встретится с многоугольником решений в его вершине, тогда в этом положении L₁ прямая L становится так называемой опорной, и на этой прямой функция L принимает наименьшее значение. При дальнейшем движении в том же направлении (положительном) прямая L пройдет через другую вершину многоугольника решений, выходя из области решений, и станет так же опорной прямой L₂; ней функцияна L принимает наибольшее значение среди всех значений L, принимаемых на многоугольнике решений.

Таким образом, минимизация и максимизация линейной функции L = c₁x₁ + c₂x₂ + c₀ на многоугольнике решений достигаются в точках пересечения этого многоугольника с опорными прямыми L = c₁x₁ + c₂x₂ + c₀, нормальными к вектору С(с₁,с₂). Это пересечение опорной прямой может быть в одной точке (вершине многоугольника) или в бесконечном множестве точек (это множество есть сторона многоугольника).

Аналогично, линейная функция L = c₁x₁ +c₂x₂ +c₃x₃ +c₀ Принимает постоянное значение на плоскости, нормальной к вектору С(с₁,с₂,с₃). Наименьшее и наибольшее значения этой функции на многограннике решений достигается в точках пересечения этого многогранника с опорными плоскостями, нормальными к вектору С(с₁,с₂,с₃). Пересечение многогранника с опорной плоскостью может происходить или в одной точке (вершине многогранника), или в бесконечном множестве точек (ребро или грань многогранника).

§ Пример

Максимизировать линейную форму L = 2x₁ +2x₂ при ограничениях:

Решение.

Заменив знаки неравенств знаками точных равенств, построим область решений по уравнениям прямых: 3x₁ -2x₂ + 6 = 0, 3x₁ +x₂ – 3 = 0, x₁ = 3.

Область решения – треугольник.

Построим вектор С (2,2). Тогда опорная прямая будет при выходе из треугольника решений проходить через точку P(3, 7.5). Следовательно, линейная функция L = 2x₁ +2x₂ в точке P(3, 7.5) будет иметь наибольшее значение, т.е. максимизируется, и L_max = 21.