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

Если задача линейного программирования имеет две переменные x ₁ и x ₂, то ее можно решить графически.

Решение задачи происходит в два этапа.

На первом этапе необходимо на плоскости изобразить допустимое множество, а на втором найти оптимальную точку, если она существует, в противном случае убедиться в неразрешимости задачи.

Этап 1. Построение допустимого множества.

Каждое неравенство в рассматриваемой задаче представляет собой полуплоскость, а допустимое множество – пресечение этих полуплоскостей. Если неравенства в задаче заменить уравнениями, то получим уравнения прямой. Каждую прямую можно построить по двум точкам. Для того чтобы выделить необходимую полуплоскость, надо взять точку, не лежащую на прямой, и подставить ее координаты в левую часть неравенства, если неравенство выполнено, то выбираем полуплоскость, содержащую данную точку, в противном случае другую полуплоскость.

Так как в ограничениях присутствуют ограничения неотрицательности переменных, то рассматриваем только первый координатный угол.

Если правая часть не равна нулю, то в качестве пробной точки удобнее всего выбрать начало координат (0,0).

Алгоритм

Шаг 1: Выделение первого координатного угла.

Шаг 2: .

Шаг 3: i -е неравенство записывается как уравнение

Шаг 4: Полагаем находим из уравнения

Шаг 5: Полагаем находим из уравнения

Шаг 6: Через точку и проводится прямая.

Шаг 7: В левую часть неравенства подставляется точка с координатами . Если неравенство выполнено, то выбирается полуплоскость содержащая начало координат, в противном случае противоположная полуплоскость.

Шаг 8: Если , то , переходим к шагу 3, иначе шаг 9.

Шаг 9: Допустимое множество получено. Если оно непустое (), то выписывается ответ: Задача несовместна, иначе переход к этапу 2.

Этап 2: Поиск оптимальной точки

Рассмотрим градиент функции . Т.к. функция линейна, то ее градиент есть постоянный вектор с координатами .

Известно, что движение в направлении градиента увеличивает значение функции.

Прямая перпендикулярная вектору – градиенту называется линией уровня, т.к. значения функции в любой точке этой прямой одинаковы.

Алгоритм

Шаг 1: Строится вектор градиент .

Шаг 2: Кладется линейка перпендикулярно вектору – градиенту.

Шаг 3: Линейка сдвигается параллельно самой себе по направлению вектора градиента, пока хотя бы одна точка соответствующей прямой принадлежит допустимому множеству.

Шаг 4: Если при любом положении линейки перпендикулярно вектору градиенту имеются точки допустимого множества, то выписывается ответ: Задача неразрешима из-за неограниченности целевой функции переход к шагу 10. Иначе шаг 5.

Шаг 5: Находится последняя точка допустимого множества, лежащая на соответствующей линии уровня.

Шаг 6: Если эта точка неединственная, то выбирается точка, которая является пересечением двух прямых, ограничивающих допустимое множество.

Шаг 7: Выписывается система двух уравнений с двумя неизвестными.

Шаг 8: Из системы уравнений находится оптимальная точка .

Шаг 9: Находится оптимальное значение целевой функции .

Шаг 10. Конец.

Пример 1.4.1. Решить задачу линейного программирования графически.

, (1.4.1)

, (1.4.2)

, (1.4.3)

Решение. Строим допустимое множество в соответствии с первым этапом алгоритма. В результате получаем ограниченную многогранную область.

Рис. 1.4.1

В таблице 1.4.1 заданы точки, по которым строятся прямые (1.4.1)-(1.4.3).

Таблица 1.4.1

	(1.4.1)	(1.4.2)	(1.4.3)
				-9
					-10

 

В качестве пробной кочки выбираем начало координат (0, 0).

Для (1.4.1) (Верно: выбирается полуплоскость содержащая начало координат.)

Для (1.4.2) (Верно: выбирается полуплоскость содержащая начало координат.)

Для (1.4.3) (Верно: выбирается полуплоскость содержащая начало координат.)

На этапе 2 находим .

Сдвигаясь по линии уровня в направлении вектора-градиента, получаем оптимальную точку А, находим ее координаты. Так как она является точкой пересечения прямых (1.4.1) и (1.4.3), то решаем систему уравнений

Таким образом, оптимальной точкой является точка .

Находим оптимальное значение целевой функции, подставляя значение в функцию:

.

Пример 1.4.2. Решить графически следующую задачу:

,

,

,

,

.

Решение. Построение допустимого множества выполняется также как и в предыдущей задаче. В результате получаем неограниченную мно­гогранную область.

Рис. 1.4.2.

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

Пример 1.4.3. Решить задачу

(1.4.4)

(1.4.5)

.

.

Решение. Допустимое множество в данной задаче имеет вид

Рис. 1.4.3.

Из рисунка видно, что допустимое множество неограниченно, однако оптимальное решение существует, им является луч, выходящий из точки . Линии уровня целевой функции параллельны прямой , соответствующей пер­вому ограничению. Перемещая линии уровня в направлении вектора-градиента, получаем, что линия уровня с максимально возможным значением целевой функции совпадает с прямой . Таким обра­зом, целевая функция достигает своего максимального значения во всех точках луча, выходящего из точки . Задача имеет бесчис­ленное множество решений. Для того чтобы выписать решение в общем ви­де, возьмем на луче еще одну точку . Уравнение луча записывает­ся следующим образом: . Таким образом, любое решение данной задачи записывается в виде .

Пример 1.4.4. Решить графически задачу

.

Решение. Допустимое множество данной задачи пусто. Это видно из следующего рисунка.

Рис. 1.4.4.

Поэтому данная задача несовместна.