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

Теорема 4. Значения целевой функции L(X) в точках линии уровня L₀ возрастают, если линию уровня перемещать в направлении вектора нормали и убывают, если линию уровня перемещать в направлении, противоположном направлению вектора нормали.
Сформулированные теоремы позволяют представить алгоритм решения ЗЛП графическим методом:
Шаг 1. Находят область допустимых решений системы ограничений:

1. 
   Если ОДР = , то задача неразрешима. Конец.
   
2. 
   Если ОДР , то переходят к п. 2.
   

Шаг 2. Строят вектор (c₁, c₂).
Шаг 3. Проводят линию уровня L₀ так, чтобы она имела с ОДР общие точки.
Шаг 4. Перемещают линию уровня по направлению вектора для задачи на максимум и в направлении, противоположном , для задачи на минимум. Перемещение производится до линии уровня, которая является границей полуплоскости, целиком содержащей ОДР:

1. 
   Если такой линии не существует, то:
   

4.1.1. L_max= +∞ при решении ЗЛП с максимизационным критерием;
4.1.2. L_min= –∞ при решении ЗЛП с минимизационным критерием.
В обоих случаях задачу считают неразрешимой. Конец.

2. 
   Если же указанная линия уровня существует, то точка, в которой целевая функция достигает максимального (минимального) значения, находится на этой прямой, обозначаемой L₀⁺ (L₀^–):
   

4.2.1. Если линия уровня не параллельна ни одной из сторон ОДР, то это — угловая точка ОДР.
4.2.2. Если линия уровня параллельна одной из сторон ОДР, то
в этом случае возможны варианты: эта точка —
а) угловая точка ОДР или
б) любая точка соответствующей стороны.
Переходят к пункту 5.
Шаг 5. Находят координаты точек экстремума и значение целевой функции в них:
5.1. Если задача имеет единственное решение (случаи 4.2.1, 4.2.2а), то находят координаты точки экстремума и значение целевой функции в ней. Конец.
5.2. Если же имеет место случай 4.2.2б, то, говорят, что задача имеет альтернативный оптимум, и ее общее решение находится по формуле _опт = X₁+(1)X₂, где 0 λ 1, X₁, X₂ — оптимальные решения
в угловых точках ОДР (если такие, конечно, имеются). Конец.
Из рисунка, построенного в соответствии с указанным алгоритмом, всегда видно, разрешима ЗЛП или нет, а также существуют ли у ОДР вершины (см., например, Error: Reference source not found и комментарии к нему). ОДР без угловых точек может быть только двух видов: полуплоскостью (рис. 3б) или областью, ограниченной двумя параллельными прямыми (рис. 3в). Как правило, в задачах реальной экономики отсутствие вершины — явление, редко встречающееся.
Комментарии к рис. 5:
а) Максимального значения целевая функция достигает в точке А, минимального — в точке В. Записывают это обычно следующим образом: L_max= L(A), L_min= L(B).
б
) Максимального значения целевая функция достигает в любой точке отрезка AB, минимального — в точке D.
в) В любой точке луча, отмеченного на рисунке, целевая функция принимает максимальное значение. Из рисунка видно, что прямой L₀^–, характеристическим свойством которой является свойство «быть границей полуплоскости, целиком содержащей ОДР», не существует, поэтому L_min= –∞, и задача на минимум неразрешима.
г) L_max= +∞, следовательно, ЗЛП с максимизационным критерием
неразрешима. Минимальное значение целевая функция принимает в любой точке прямой L₀^–, одновременно являющейся стороной ОДР.
Так как множество всех оптимальных решений _опт является подмножеством линии уровня L₀⁺ (или L₀^–), то возможна следующая геометрическая интерпретация _опт. :

• 
  точка на прямой L₀⁺ (или L₀^–);
  
• 
  отрезок на прямой L₀⁺ (или L₀^–);
  
• 
  луч, все точки которого принадлежат прямой L₀⁺ (или L₀^–);
  
• 
  прямая L₀⁺ (или L₀^–).
  

Первый случай соответствует п. 4.2.1 и 4.2.2а, последние три —
п. 4.4.2б. Иллюстрацией может служить снова Error: Reference source not found.
Итак, графический метод решения ЗЛП действительно позволяет избежать полного перебора вершин: если из рисунка видно, что некоторая угловая точка является единственной точкой пересечения линии уровня
с ОДР, то нет необходимости вычислять координаты остальных вершин, так как указанная точка — единственное оптимальное решение.