4. МНОГОМЕРНЫЙ ПОИСК.

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ [l,2]

 

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

Задача

Найти  X1 и X2 удовлетворяющие системе неравенств:

(37)

условиям неотрицательности:

    X1≥0, X2≥0,

(38)

для которых функция:

R=C1X1+C2X2

(39)

достигает максимума.

 

Решение.

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

Рис.17

 

Эта прямая делит плоскость Х1ОХ2 на две полуплоскости, для координат X1, X2 любой точки А одной полуплоскости выполняется неравенство:

ai1x1+ai2x2bi ,

а для координат X1, X2 любой точки В другой полуплоскости противоположное неравенство:

ai1x1+ai2x2bi .

Координаты любой точки граничной прямой удовлетворяют уравнению:

ai1x1+ai2x2=bi .

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

Неравенствам X1≥0 и X2≥0 также соответствуют полуплоскости, расположенные справа от оси ординат и над осью абсцисс.

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

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

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

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

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

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

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

Рис.18

 

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

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

Для всех точек, лежащих на одной из прямых, функция R принимает одно определенное значение, поэтому указанные прямые называются линиями уровня для функции R (рис.19).

Рис.19

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

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

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

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

 

Пример.

Найти X1 и X2 , удовлетворяющие системе неравенств:

(40)

условиям неотрицательности:

X1≥0, X2≥0,

для которых функция R=2X1+3X2 достигает максимума.

 

Решение.

1.Заменим каждое из неравенств равенством и построим граничные прямые (рис.20)

Рис.20

 

2.Определим полуплоскости, соответствующие данным неравенствам (40) путем "испытания" точки (0,0). Покажем направления полуплоскостей штриховкой (рис .21). С учетом неотрицательности X1 и Х2 получим область допустимых ре­шений данной задачи в виде вы­пуклого многоугольника ОАВДЕ.

 

Рис.21

 

3.В области допустимых решений находим оптимальное решение, строя вектор , который показывает направление возрастания R (рис.21).

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

Х1 - Х2 = -4 ,

X1 + Х2 = 8 .

Ответ: X1=2, X2 = 6, Rmax=22.