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

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

 

Область решений линейных неравенств.

 

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

Пример 3. Найти полуплоскость, определяемую неравенством .

► Строим прямую по двум точкам, например, по точкам пересечения с осями координат (0; 4) и (6; 0).

рис.1

 

Эта линия делит плоскость на две части, т.е. на две полуплоскости. Берем любую точку плоскости, не лежащую на построенной прямой. Если координаты точки удовлетворяют заданному неравенству, то областью решений является та полуплоскость, в которой находится эта точка. Если же получаем неверное числовое неравенство, то областью решений является та полуплоскость, которой эта точка не принадлежит. Обычно для контроля берут точку (0; 0).

Подставим и в заданное неравенство. Получим . Следовательно, полуплоскость «к нулю» является областью решений данного неравенства (заштрихованная часть). ◄

Пример 2. Найти полуплоскость, определяемую неравенством .

► Строим прямую , например, по точкам (0; 0) и (1; 3).

рис.2

 

Так как прямая проходит через начало координат, точку (0; 0), то нельзя брать ее для контроля. Возьмем, например, точку (– 2; 0) и подставим ее координаты в заданное неравенство. Получим . Это неверно. Значит, областью решений данного неравенства будет та полуплоскость, которой не принадлежит контрольная точка (заштрихованная часть). ◄

 

 

Область решений системы линейных неравенств.

Геометрическая интерпретация области допустимых решений

И целевой функции.

Пример 5. Найти область решений системы неравенств

► Находим область решений I-го неравенства (рис. 1) и II-го неравенства (рис. 2).

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

рис. 3

 

Если к заданной системе неравенств добавить условия и , то область решений системы неравенств будет находиться только в I координатной четверти (рис. 4).

рис.4

Принцип нахождения решения системы линейных неравенств не зависит от количества неравенств, входящих в систему. ◄

 

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

 

Пусть математическая формулировка ЗЛП имеет вид

при ограничениях

Тогда

· любое из неравенств системы ограничений на плоскости определяет некоторую полуплоскость;

· система неравенств определяет выпуклое множество (выпуклый многоугольник, неограниченную выпуклую многоугольную область, пустую область или точку), которое совпадает с многогранником решений ;

· уравнение при фиксированном значении определяет на плоскости прямую . При изменении получают семейство прямых, называемых линиями уровня;

· вектор коэффициентов целевой функции называется градиентом функции. Он перпендикулярен линиям уровня.

· Градиент функции показывает направление наибольшего возрастания целевой функции.

· Антиградиент показывает направление наибольшего убывания целевой функции.