Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Графический метод и анализ решения ЗЛП
Графическим методом целесообразно решать ЗЛП, содержащие не более двух переменных. Алгоритм графического метода рассмотрим применительно к задаче: 3x1 + 2x2 (2.50) при x1 + 2x2 6 (а) 2x1 + x2 8 (б) Р = x1+0, 8x2 5 (в) (2.51) -x1 + x2 1 (г) x2 2 (д) x1 0, x2 0 (е)
Шаг 1. Строим область допустимых решений (2.51) – область Р, т.е. геометрическое место точек, в котором одновременно удовлетворяются все ограничения ЗЛП. Каждое из неравенств (а)–(д) системы ограничений (2.51) задачи геометрически определяет полуплоскость соответственно с граничными прямыми:
x1 + 2x2 = 6 (а) 2x1 + x2= 8 (б) x1+0, 8x2= 5 (в) -x1 + x2= 1 (г) x2= 2 (д)
Условия неотрицательности переменных (е) ограничивают область допустимых решений первым квадратом. Области, в которых выполняются соответствующие ограничения (2.51) в виде неравенств, указываются стрелками, направленными в сторону допустимых значений переменных (рис. 2.1).
Рис. 2.1 Если система неравенств (2.51) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Полученная таким образом область допустимых решений Р – планов ЗЛП (см. рис. 2.1) есть многоугольник ABCDEF – замкнутое, ограниченное, выпуклое множество с шестью крайними, или угловыми, точками: A, B, C, D, E, F. Шаг 2. Строим вектор-градиент линейной функции , указывающий направления возрастания функции . Шаг 3. Строим прямую с1x1 + c2x2 = const – линию уровня функции , перпендикулярную вектору-градиенту : 3x1 + 2x2 = const (рис.2.2).
Рис. 2.2 Шаг 4. В случае максимизации передвигают прямую 3x1 + 2x2 = const в направлении вектора до тех пор, пока она не покинет область Р. Крайняя точка (определение 2.12) (или точки) области, в которой линия уровня покидает допустимую область, и является решением задачи (рис. 2.3).
Рис. 2.3 Крайняя точка С – точка максимума , С = лежит на пересечении прямых (а) и (б). Для определения ее координат решим систему уравнений: x1 + 2x2 = 6 2x1 + x2 = 8. Откуда x*1 = 10/3; x*2 = 4/3 или = (10/3; 4/3). Подставляя значения x*1 и x*2 в функцию , найдем max = = 3 . 10/3 + 2 . 4/3 = 38/3. Замечания. 1. В случае минимизации прямую c1x1 + c2x2 = const надо перемещать в направлении (- ), противоположном . 2. Если допустимая область решений Р представляет собой неограниченную область и прямая при движении в направлении вектора (или противоположном ему) не покидает Р, то в этом случае не ограничена сверху (или снизу), т.е. (или ).
Пример 2.5. Графическим способом решить ЗЛП max (2x1 + x2) при x1 - x2 2 (1) x1 + 3x2 3 (2) 7x1 - x2 2 (3) x1, 2 0. (4) Шаг 1. Строим область Р (рис. 2.4). Она является неограниченной. Шаг 2. Строим вектор . Шаг 3. Строим линию уровня функции = 2x1 + x2 = const. Шаг 4. Передвигая линию уровня в направлении вектора , убеждаемся в неограниченном возрастании функции , то есть .
Рис. 2.4 Пример 2.6. Решить графическим методом ЗЛП. Найти x1 + 3x2 при ограничениях
2x1 + 3x2 6 (1) x1 + 2x2 5 (2) x1 4 (3) 0 x2 3 (4)
Рис. 2.5 Из рис. 2.5 видно, что область допустимых решений пуста (Р= ). Задача не имеет решения.
|