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

Геометрический метод применяется для решения задач ЛП с двумя или тремя переменными, записанных в стандартной форме. Рассмотрим, например,

двумерную задачу ЛП:

Метод решения основан на том, что каждое ограничение , а также геометрически определяет на плоскости некоторую полуплоскость и, следовательно, множество всех допустимых планов является пересечением этих полуплоскостей. Множество есть выпуклое множество. Оно может быть пустым, если система ограничений несовместна, или выпуклым многоугольным множеством. Сторонами этого многоугольника являются прямые ( , , .

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

Чтобы решить задачу геометрически, необходимо:

1) построить множество допустимых планов , определяемое системой ограничений;

2) на множестве найти оптимальное решение – вершину многоуголь­ни­ка, если решение единственно, или целый отрезок – сторону многоугольника, если задача ЛП имеет бесконечное множество оптимальных решений.

Применим изложенный метод к решению следующей задачи:

(3.1)

(3.2)

Решение. Построим для этой задачи множество допустимых планов . Для этого проведём ограничительные прямые: (1) ,

(2) , (3) и штриховкой отметим те полуплоскости, которые определяются неравенствами (3.2). Заметим, что построение прямой значительно упрощается, если предварительно уравнение прямой привести к специальному виду (в отрезках на осях)

.

Здесь числа – величины отрезков, которые прямая отсекает на координатных осях . В этой связи уравнения прямых (1), (2) и (3) перепишем в виде:

(1) (2) (3) .

Отсюда находим отрезки, отсекаемые прямыми (1), (2) и (3) на координатных осях .

Чтобы пометить штриховкой полуплоскость, определяемую, например, неравенством , возьмем точку , не лежащую на прямой (1), и, подставив её координаты в неравенство, поучим . Неравенство выполняется, следовательно, точка принадлежит полуплоскости, определяемой неравенством ; эту полуплоскость отмечаем штриховкой (рис.1). Аналогично отмечаем штриховкой соответствующие полуплоскости, определяемые неравенствами и .

Неравенство определяет правую, а неравенство – верхнюю полуплоскость плоскости . Таким образом, множество допустимых планов есть пятиугольник (рис. 1).

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

Рис. 1

Её уравнение имеет вид:

.

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

,

и будем перемещать её параллельно самой себе в направлении вектора , поскольку известно, что именно в

этом направлении скорость возрастания функции будет наибольшей. Пере­­ме­щаем прямую параллельно самой себе до такого предельного поло­же­ния, при котором множество окажется по одну сторону от полученной преде­ль­ной прямой и хотя бы одна точка из всё ещё будет принадлежать этой прямой. Построенную таким образом предельную прямую назовём опорной для мно­же­ства . Точки , лежащие на этой опорной прямой, образуют множество оптимальных решений задачи ЛП. Из рис.1 видно, что опорной прямой является линия уровня, проходящая через вершину С и, следовательно, оптимальным решением будет точка . Поскольку эта точка находится на пересечении ограничительных прямых (2) и (3), то её координаты определяются следующей системой уравнений:

Решая систему, получаем решение , т.е. – оптимальный план задачи (3.1) – (3.2).

Далее находим максимальное значение функции в точке :

.

Отметим, что в случае решения задачи на минимум целевой функции на множестве допус­ти­мых планов , линию уровня следует перемещать в направ­лении, противоположном вектору .