3.3.2 Построение прямой уровня
Возьмем произвольную точку, принадлежащую области допустимых решений четырехугольнику ОАВС, например, точку М с координатами (100; 100). Подставим координаты точки М в функцию F.
F(100; 100) = 2*100+4*100 = 600.
Прямая уровня будет иметь следующий вид: 2x1 + 4х2 = 600
Построим полученную прямую. Для этого необходимо найти координаты двух произвольных точек этой прямой. Одна точка у нас уже есть - это точка М(100; 100). Найдем еще одну точку. Пусть х2=0, тогда х1=300. Следовательно, координаты дополнительной точки (300; 0). Отметим полученные точки и построит прямую уровня (на рисунке 1 она обозначена (3')).
Значения функции F будут возрастать по мере того, как прямая уровня удаляется от начала координат в положительном квадранте. Направление возрастания функции F будет совпадать с вектором, координаты которого являются коэффициентами при переменных х1 и х2 функции F. На рисунке - это вектор а{2; 4}, отложенный от точки М.
Примечание. Обратите внимание, что вектор а, определяющий направление возрастания функции F, всегда будет перпендикулярен прямой уровня.
рис.2.1
3.3.3 Максимизация целевой функции f
Для нахождения точки, в которой функция F достигнет своего максимального значения, необходимо перемещать прямую уровня по направлению вектора а до пересечения этой прямой с граничной точкой области допустимых решений. На нашем рисунке - это точка В.
Найдем координаты точки В. Данная точка расположена на пересечении двух прямых (1') и (2'), поэтому, чтобы найти ее координаты необходимо решить следующую систему уравнений:
Из второго уравнения выразим х1.
И подставим полученное значение в первое уравнение.
(300; 200) - точка, соответствующая оптимальному решению задачи, следовательно, максимальная прибыль составляет 2*300+4*200 = 1400 дол. в неделю. Значит, чтобы получить максимальную прибыль, фирме необходимо выпускать в неделю триста полок модели А и двести полок модели В.
3.3.4 Алгоритм решения задачи двумерного линейного программирования графическим методом.
1. Строим область допустимых решений функции F.
Для этого в ограничениях знаки неравенства заменяем знаками равенства и строим полученные прямые. Затем определяем те полуплоскости, которые соответствуют данным ограничениям и получаем область допустимых решений, лежащую на пересечении всех полуплоскостей.
2. Строим прямую уровня
Для этого берем произвольную точку М, принадлежащую области допустимых решений функции F и, подставив координаты этой точки в функцию, получаем прямую уровня. Затем от выбранной точки М, откладываем вектор а, координаты которого - это коэффициенты при целевой функции F.
3. Максимизируем (минимизируем) целевую функцию F.
Для максимизации (минимизации) функции F передвигаем прямую уровня по направлению (в обратном направлении относительно) вектора и до пересечению с граничной точкой области допустимых решений. Полученная точка является оптимальным решением, в котором функция достигает свой максимум (минимум). Находим координаты этой точки и подставляем их в функцию F.
При решении двумерных задач линейного программирования возможны следующие ситуации (ОДР - область допустимых решений)
