|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Элементы теории. Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменнымиГрафический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и целевой функции (ЦФ) задачи. Каждое из неравенств задачи линейного программирования определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством. Все вышесказанное относится и к случаю, когда система ограничений включает равенства. ЦФ при фиксированном значении представляет на плоскости прямую линию. Изменяя значения целевой функции L, получим семейство параллельных прямых, называемых линиями уровня. Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на осях координат, а угловой коэффициент прямой останется постоянным. Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L. Вектор с координатами из коэффициентов ЦФ перпендикулярен к каждой из линий уровня. Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора. Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки. Оптимальной считается точка, через которую проходит линия уровня, соответствующая наибольшему (наименьшему) значению функции. Оптимальное решение всегда находится на границе ОДР, например, в одной из вершин многоугольника ОДР, через которую пройдет линия постоянного значения от функции, или на всей его стороне. При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.
В рассматриваемом примере содержатся только две переменные x1 и x2, поэтому задачу можно решить графически. 1) На плоскости x1, x2 строим область допустимых значений переменных, определяемую ограничениями задачи:
x1 + 2x2 3 (А) 3x1 + 1x2 3 (Б) x1, x2 0.
Последнее ограничение определяет первый квадрант плоскости. Чтобы построить множество точек удовлетворяющих неравенству (А), нанесем на плоскость график прямой, определяющий границу этого множества: x1 + 2x2 = 3 (Б). Приведем это уравнение к виду: . А это уравнение прямой «в отрезках» и для построения этой прямой используются две точки (a, 0) и (0, b). (рис. 1.1)
Рис. 1.1 Запишем уравнение границы допустимой области из неравенства (А): .
Аналогично, из неравенства (Б) получим уравнение второй границы:
Построим обе прямые на плоскости. Множества точек, удовлетворяющие неравенствам (А) и (Б) будут полуплоскости, лежащие под соответствующими прямыми, а множество допустимых значений переменных будет пересечением (общей частью) этих полуплоскостей, лежащее в первом квадранте: четырехугольник ABCD (рис. 1.2). Рис. 1.2.
2) На множестве допустимых решений (ABCD) найдем точку, в которой целевая функция Z = 2x1 + x2 имеет максимальное значение. Для этого посмотрим линии уровня целевой функции. Линией уровня называется множество точек, на которых функция принимает постоянное значение:
Z = 2x1 + x2 = К,
где К - задаваемая постоянная. При К = 1 уравнение линии уровня будет:
2x1 + x2 = 1. или (в отрезках): . При К = 2, аналогично:
2x1 + x2 = 2,
или .
Нанеся линии уровня на область допустимых решений (рис. 1.3), получим, что при увеличении значения Z соответствующая линия уровня перемещается параллельно предыдущей вправо и вверх. Таким образом, точкой из многоугольника ABCD, в которой целевая функция Z имеет максимальное значение, будет вершина С. Эта точка и определяет решение задачи. Рис. 1.3.
3) Вычисление координат оптимальной точки (С).
Точка C лежит на пересечении прямых (А) и (Б), поэтому, чтобы определить ее координаты надо решить систему уравнений:
x1 + 2x2 = 3 (А) 3x1 + x2 = 3 (Б) Решение: x1* = 0,6; x2* = 1,2;
максимальное значение Z:
Z* = 2·0,6 + 1,2 = 2,4. Задание 2. Решение задачи ЛП в симплекс-таблицах. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.) |