Решение

Построим в системе прямоугольных координат область допустимых решений задачи (рис.11). Для этого, заменяя каждое из неравенств (5.5) равенством, строим соответствующую ему граничную прямую (i = 1, 2, …, r)

Рис. 11

Эта прямая делит плоскость на две полуплоскости. Для координат любой точки А одной полуплоскости выполняется неравенство , а для координат любой точки В другой полуплоскости - противоположное неравенство . Координаты любой точки граничной прямой удовлетворяют уравнению .

Для определения того, по какую сторону от граничной прямой располагается полуплоскость, соответствующая заданному неравенству, достаточно «испытать» одну какую-либо точку (проще всего точку О (0;0)). Если при подстановке её координат в левую часть неравенства оно удовлетворяется, то полуплоскость обращена в сторону к испытуемой точке, если же неравенство не удовлетворяется, то соответствующая полуплоскость обращена в противоположную сторону. Направление полуплоскости показывается на чертеже штриховкой. Неравенствам и соответствуют полуплоскости, расположенные справа от оси ординат и над осью абсцисс.

На рисунке строим граничные прямые и полуплоскости, соответствующие всем неравенствам.

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

При построении области допустимых решений в зависимости от конкретного вида системы ограничений (неравенств) на переменные может встретиться один из следующих четырех случаев:

Рис. 12. Область допустимых решений пустая, что соответствует несовместности системы неравенств; решения нет.

Рис. 13. Область допустимых решений изобра- жается одной точкой А, что соответствует единственному решению системы.

Рис. 14. Область допустимых решений ограниченная, изображается в виде выпуклого многоугольника. Допустимых решений бесконечное множество.

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

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

Вектор градиента , перпендикулярный к линиям уровня, показывает направление возрастания R.

Задача отыскания оптимального решения системы неравенств (5.5), для которого целевая функция R (5.7) достигает максимума, гео­метрически сводится к определе­нию в области допустимых реше­ний точки, через которую пройдет линия уровня, соответствую­щая наибольшему значении пара­метра R

.

Рис. 16

Если область допустимых решений есть выпуклый многоугольник, то экстремум функции R достигается, по крайней мере, в одной из вер­шин этого многоугольника.

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

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