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

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

1. Многогранник ограничен, максимум и минимум есть (рисунок 1).

Рис. 1

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

Рис. 2

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

Рис. 3

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

Рис. 4

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

Решение. Строим на чертеже в определенном масштабе область решения задачи. Так как оптимум находится вращением разрешающей прямой вокруг начала координат, сразу можно сказать, что экстремальными точками будут вершины A и C.

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

(1)

(2)

(3)

(4)

Определим, где будет минимум, а где максимум.

Выразим из целевой функции :

Угловой коэффициент разрешающей прямой

Ищем производную:

Так как производная при любом z положительна, функция возрастающая, с увеличением z угловой коэффициент увеличивается. Это соответствует вращению прямой против часовой стрелки. Следовательно, в вершине С значение функционала будет наименьшим (минимум). При дальнейшем вращении прямой получим, что пересечение прямых уходит в бесконечность, т.е. мы получили асимптотический максимум. Практически же дело обстоит гораздо проще. Определим по рисунку экстремальные точки, из решения соответствующих уравнений получим их координаты, которые так или иначе необходимы. В нашем случае это одна точка С(6,2). Затем вычисляем нужные нам значение функционала в этой точке:

Поскольку мы получили асимптотический максимум, искать его будем следующим образом:

Выражаем x₁ из прямой (1) и находим предел . Получаем: