2015-04-20
231
/ 2 /, c. 27 – 30; /3 /, c. 26 – 29, 53 – 56.
АЛГОРИТМ ГРАФИЧЕСКОГО РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Рассмотрим задачу линейного программирования
; (1)
(2)
(3)
1. Строим область допустимых решений, которая является пересечением полуплоскостей, определяемых неравенствами системы ограничений вида 
Известно, что прямая 
делит плоскость на две полуплоскости, причем для любой точки 
одной полуплоскости 
, а для любой точки 
другой полуплоскости 
. Другими словами, решением неравенства
является одна из полуплоскостей, ограниченная прямой 
.
Чтобы уточнить, какая полуплоскость является решением неравенства, достаточно подставить координаты какой-нибудь точки из одной полуплоскости: если числовое неравенство верно, то эта полуплоскость является решением неравенства, если нет – то другая.
2. Строим вектор 
наискорейшего возрастания целевой функции – вектор градиентного направления.
3. Проводим линию нулевого уровня 
перпендикулярно вектору 
.
4. Перемещаем линию нулевого уровня в направлении вектора .Точка (точки) входа в область Ω определяет (определяют) 
, точка (точки) выхода из области Ω – 
.
|
|
|
5. Находим оптимальные планы
и 
и экстремальные значения целевой функции
и 
.
