4.
МНОГОМЕРНЫЙ
ПОИСК.
ЛИНЕЙНОЕ
ПРОГРАММИРОВАНИЕ
[l,2]
4.2.
Графический
метод
решения
задач
линейного
программирования
Задача
Найти X1 и X2 удовлетворяющие
системе
неравенств:
|
(37) |
условиям
неотрицательности:
X1≥0,
X2≥0, |
(38) |
для которых
функция:
R=C1X1+C2X2 |
(39) |
достигает
максимума.
Решение.
Построим
в системе
прямоугольных
координат Х1ОХ2
область
допустимых
решений
задачи. Для
этого,
заменяя
каждое из
неравенств (37)
равенством,
строим соответствующую
ему
граничную прямую
ai1x1+ai2x2≤bi (i=1,2,…,r) (рис.17).
Рис.17
Эта прямая
делит
плоскость Х1ОХ2 на
две
полуплоскости,
для
координат X1, X2 любой
точки А одной
полуплоскости
выполняется
неравенство:
ai1x1+ai2x2≤bi ,
а для
координат X1, X2 любой
точки В другой
полуплоскости
противоположное
неравенство:
ai1x1+ai2x2≥bi .
Координаты
любой точки
граничной
прямой удовлетворяют
уравнению:
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.