Балашовский филиал

Теорема 3. Если в задаче линейного программирования целевая функция L(X) ограничена на допустимом множестве , то угловая точка,
в которой L(X) принимает наибольшее (наименьшее) значение среди всех угловых точек этого множества, является оптимальным решением данной задачи.
Эта теорема дает возможность разработать алгоритм, позволяющий решить ЗЛП методом перебора вершин. Для чего

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

Заметим, что реализация описанной процедуры связана с определенными трудностями (особенно, когда существует большое число угловых точек, а это часто имеет место, так как задачи реальной экономики порой содержат сотни неизвестных, уравнений и неравенств). Алгоритм должен быть способен по некоторой данной угловой точке определить последующий порядок перебора вершин таким образом, чтобы это был кратчайший путь к нахождению оптимального решения. Определение такого порядка перебора представляет собой самостоятельную задачу, решение которой будет предложено в § 3. Избежать полного перебора вершин позволяет графический метод решения ЗЛП.

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

Графический метод, как правило, применяется при решении ЗЛП, система ограничений которых содержит две (реже три) переменных. Одно из достоинств этого метода указано в § 1. К числу других следует отнести простоту и наглядность, а также то, что с его помощью становятся прозрачными идеи, заложенные в основе других методов решения ЗЛП.

1. Алгоритм решения ЗЛП с двумя переменными

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

Прежде, чем перейти к описанию указанного алгоритма, напомним одно понятие. Линией уровня функции f(x₁, x₂) называется множество всех точек пространства R², в которых функция принимает некоторое постоянное значение. Согласно этому определению, для целевой функции L(X) = c₁x₁ + c₂x₂+ c произвольная линия уровня L₀ — это прямая с вектором нормали (c₁, c₂).