Графический метод решения

Графическим методом можно решать задачи линейного программирования с двумя переменными, представленные в неканоническом виде, или сводящиеся к ним. Рассмотрим следующую задачу: найти экстремум функции

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

х₁³0, х₂³0.

Решение задачи начинают с построения области допустимых решений. При этом возможны следующие случаи:

1. Область допустимых решений - пустое множество. В этом случае задача линейного программирования не имеет оптимального решения из-за несовместности системы ограничений.

2. Область допустимых решений - единственная точка. Тогда задача линейного программирования имеет единственное и оптимальное решение.

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

Существует и другой способ, который позволяет сразу найти графически угловую точку, соответствующую оптимальному решению.

Пусть с₀ - некоторое число. Прямая является линией уровня целевой функции. В каждой точке этой прямой целевая функция принимает одно и то же значение, равное с₀. Вектор - градиент целевой функции

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

, .

4. Область допустимых решений - выпуклая неограниченная область.

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

Алгоритм графического метода

1. Построить область допустимых решений.

2. Построить вектор-градиент целевой функции .

3. Построить семейство линий уровня, перпендикулярных вектору , проходящих через область допустимых решений.

4. Выбрать линию уровня, проходящую через область допустимых решений и наиболее удаленную в направлении вектора (или в противоположном вектору направлении - в задаче на минимум). Определить угловые точки области, через которые она проходит.

5. Найти координаты точек экстремума и значение целевой функции в этих точках.