![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Графический метод и анализ решения ЗЛП
Графическим методом целесообразно решать ЗЛП, содержащие не более двух переменных. Алгоритм графического метода рассмотрим применительно к задаче:
при x1 + 2x2 2x1 + x2 Р = x1+0, 8x2 -x1 + x2 x2 x1
Шаг 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. В случае максимизации
Рис. 2.3 Крайняя точка С – точка максимума x1 + 2x2 = 6 2x1 + x2 = 8. Откуда x*1 = 10/3; x*2 = 4/3 или Подставляя значения x*1 и x*2 в функцию max Замечания. 1. В случае минимизации 2. Если допустимая область решений Р представляет собой неограниченную область и прямая при движении в направлении вектора
Пример 2.5. Графическим способом решить ЗЛП max (2x1 + x2) при x1 - x2 x1 + 3x2 7x1 - x2 x1, 2 Шаг 1. Строим область Р (рис. 2.4). Она является неограниченной. Шаг 2. Строим вектор Шаг 3. Строим линию уровня функции Шаг 4. Передвигая линию уровня в направлении вектора
Рис. 2.4 Пример 2.6. Решить графическим методом ЗЛП. Найти
при ограничениях
2x1 + 3x2 x1 + 2x2 x1 0
Рис. 2.5 Из рис. 2.5 видно, что область допустимых решений пуста (Р= Задача не имеет решения.
|