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

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

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

Задача

Найти X₁ и X₂ удовлетворяющие системе неравенств:

(37)

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

X1≥0, X2≥0,

(38)

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

R=C1X1+C2X2

(39)

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

Решение.

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

Рис.17

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

a_i1x₁+a_i2x₂≤b_i ,

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

a_i1x₁+a_i2x₂≥b_i .

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

a_i1x₁+a_i2x₂=b_i .

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

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

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

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

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

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

Рис.18

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

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

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

Рис.19

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

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

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

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

Пример.

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

(40)

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

X₁≥0, X₂≥0,

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

Решение.

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

Рис.20

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

Рис.21

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

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

Х₁ - Х₂ = -4 ,

X₁ + Х₂ = 8 .

Ответ: X₁=2, X₂ = 6, R_max=22.