Геометрический метод.

Областью решения линей­ного неравенства с двумя переменными

(15).

является полуплоскость. Для того чтобы определить, ка­кая из двух полуплоскостей соответствует этому нера­венству, нужно привести его к виду или . Тогда искомая полуплоскость в первом слу­чае расположена выше прямой , во вто­ром - ниже нее. Если , то неравенство (15) имеет вид ; в этом случае получим либо - правую полуплоскость, либо - левую по­луплоскость.

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

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

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

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

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

Положим функцию равной некоторому постоянному значению : . Это значение дости­гается в точках прямой, удовлетворяющих уравнению

(16).

При параллельном переносе этой прямой в положитель­ном направлении вектора нормали линейная функция будет возрастать, а при переносе прямой в противоположном направлении - убывать.

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

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

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

В заключение вернемся к рассмотренной ранее транспортной задаче . На рисунке изображен много­угольник допустимых решений. Он получен как пере­сечение полуплоскостей, описываемых неравенствами (12). Опорная прямая соответствует уравнению (14) при . Точка пересечения опорной прямой с многоугольником реше­ний дает минимум целевой функ­ции.

При дальнейшим параллель­ном переносе этой прямой вверх можем попасть в точку (опор­ная прямая ) и получить мак­симум целевой функции.