- •080500 Менеджмент
- •Рекомендовано к изданию методической комиссией экономического факультета
- •Цель и задачи Цель: Освоить методику решения задач линейного программирования графическим методом.
- •2 Методика решения задачи линейного программирования графическим методом
- •2.1 Построение области допустимых решений задачи
- •2.2 Построение целевой функции
- •Нахождение оптимального решения
- •3 Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Библиографический список
2.2 Построение целевой функции
Для этого присвоить целевой функции Z значение нуль и построить прямую
Z = Х1 - 3Х2 = 0.
Эта прямая, проходящая через начало координат, строится следующим образом. Легко заметить, что в левой части данного уравнения стоит скалярное произведение двух векторов:
N = (с1, с2) = (1, -3) и Х = (х1, х2).
Скалярное произведение равно нулю когда векторы перпендикулярны.
Построим вектор N – вектор нормали. Он проходит через начало координат и точку (1, -3). Перпендикулярно ему через начало координат проведем прямую. Это и будет прямая целевой функции Z = 0.
В ектор N всегда показывает направление возрастания (максимизации) значения целевой функции, а противоположный ему вектор (- N ) – направление убывания (минимизации) значения целевой функции.
П ередвигая прямую Z = 0 по области допустимых решений параллельно самой себе в направление вектора N, значения целевой функции будут возрастать. Передвижение ее в направлении вектора ( - N ) дает убывание целевой функции.
П ередвижение на графике прямой Z = 0 равносильно изменению значения b в уравнении Х1 - 3Х2 = b. Каждому значению b соответствует прямая. Полученные прямые параллельны между собой и называются линиями уровня. Особенность линии уровня состоит в том, что целевая функция принимает на ней одинаковые значения, т.е. подставив координаты любой точки линии уровня в целевую функцию, ее значение изменяться не будет.
Нахождение оптимального решения
Оптимальному решению рассматриваемой задачи соответствует точка В, которая лежит на пересечении прямых (2) и (4):
-X1 + X2 = 3
X1 + X2 = 10 .
Для определения координат точки В решим систему двух линейных уравнений с двумя неизвестными. В результате получим, что минимум целевой функции достигается в точке В:
1 1 7 13
Х1* = 3—, Х2* = 6-- , Zmin = --- -- 3--- = - 16.
2 2 2 2
3 Вопросы для самоконтроля
1. Какие задачи линейного программирования можно решить графическим методом?
2. Какую область образуют допустимые решения задачи линейного программирования и что она собой представляет?
3. Какое множество называется выпуклым?
Что такое угловая точка?
Где целевая функция задачи линейного программирования достигает своего экстремального значения?
Какая зависимость существует между областью определения задачи и ее решением?
Какие возможны исходы при решении задачи линейного программирования?
Что показывает направляющий вектор N?
Что показывает направляющий вектор -N?
Что такое линии уровня?