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

Геометрическим методом может быть решена задача в стандартной форме с двумя переменными. К такой форме может быть сведена и каноническая задача, когда n-m=2, где n – число переменных, а m – число уравнений.

Линейная функция является прямой. Пусть F=а. Прямая, вдоль которой линейная функция F сохраняет постоянное значений F=a, называется линией уровня, которая имеет вид .

При увеличении или уменьшении значений постоянной а линия уровня будет перемещаться вдоль многогранника решений. Направление возрастания значений линейной функции определяется вектором - градиентом функции F: .

Передвигая линию уровня  в направлении вектора определяется оптимальное решение в точке «входа»  в многогранник решений в задаче минимизации функции F и в точке «выхода» в задаче максимизации F.

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

1. построить ОДР
2. Построить вектор нормали целевой функции (указывает на направление возрастания целевой функции)
3. Построить верхнюю и нижнюю опорные прямые, т.е. крайние линии уровня целевой функции, имеющие общие точки с О.Д.Р.
4. определить координаты экстремальных точек (пересечение опорных прямых с О.Д.Р.)

Замечание:

1. Если О.Д.Р. пустое множ., то задача не имеет решения, ввиду несовместности системы ограничений
2. Если О.Д.Р.
   неограниченна по направлению вектора n то сама целевая функция неограниченна сверху в этой области. (в противном случае зеркально).

Пример. Найти наибольшее и наименьшее значения линейной функции в области решений системы:

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

1. Построим многоугольник решений заданной системы неравенств (рис. 1).

Рис. 1

Множество точек треугольника АВС образуют область решений данной системы.

2. Найдем наибольшее и наименьшее значения функции на треугольнике решений системы неравенств.

Рассмотримпрямую L, построенную по линейной функции при условии, что F= a, где a – заданное число.

По уравнению строим прямую L следующим образом:

Сначала построим вектор нормали . Координаты вектора определяются по коэффициентам при и в уравнении .

Следовательно, .

Если начало вектора поставить в начало координат, то конец вектора определяется координатами точки (3;4).

Проведем прямую L через начало координат перпендикулярно вектору (в этом случае уравнение принимает вид , где ).

Будем передвигать прямую L параллельно самой себе в направлении, указанном вектором , до треугольника АВС и найдем точки «входа» и «выхода» области.

Точка «входа» прямой L - точка А, а точка «выхода» – точка B. Стрелка вектора показывает направление роста значения функции .

Точки и А и С определяются при решении систем линейных уравнений.

Точка А – это пересечение прямых (1) и (3). Решая систему уравнений,

8х2 = 80 =gt; х2= 10, тогда х1 = 7.

Получим точку А(7; 10).

Точка В– это пересечение прямых (1) и (2). Решим систему уравнений

  =gt; 

8х2 = 112 =gt; х2 = 14, тогда    х1 = 11.

Точка В (11;14).

Таким образом, в точке функция Fпринимает наименьшее значение , в точке - наибольшее .