![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Двойственный симплексный метод
Рассмотрим базисное недопустимое решение
Для этого решения
Двойственная задача может быть решена симплекс-методом без применения аппарата искусственного базиса.
Если симплексный метод – метод последовательного улучшения плана (улучшаются планы
Условия применимости двойственного симплекс-метода: · в матрице условий задачи, записанной в канонической форме, должна быть единичная подматрица, при этом правые части ограничений не обязаны быть положительными. · все оценки должны быть неотрицательны, если задача на максимум, и неположительны, если задача на минимум.
Итерации в двойственном симплекс-методе выполняются по следующим правилам: · определяется переменная · определяется свободная переменная
Это правило гарантирует, что новое базисное решение будет псевдо-планом. · далее выполняются операции однократного замещения (как и в симплекс-методе) с разрешающим элементом · процесс повторяется до тех пор, пока очередное базисное решение не станет допустимым. Замечание: если в разрешающей строке нет отрицательных элементов, то область допустимых решений пуста.
Пример:
1. Содержательное описание. Целлюлозно-бумажный комбинат (ЦБК) на берегу озера Байкал может работать по двум технологическим режимам. По первому режиму в течение смены расходуется 100 м3 древесины, производится 50 тонн целлюлозы, 60 центнеров лигнитов (вещества, используемые в химической промышленности) и сбрасывается в озеро 10 кг отравляющих веществ. По второму режиму в течение смены расходуется 120 м3 древесины, производится 75 тонн целлюлозы, 30 центнеров лигнитов, сбрасывается в озеро 25 кг отравляющих веществ. Годовой план производства составляет 15000 тонн целлюлозы, 1200 тонн лигнитов. Предельные годовые нормы выброса отравляющих веществ составляют 5 тонн. Определить годовой план работы ЦБК, требующий минимального расхода древесины.
2. Математическая модель. 2.1 Управляемые параметры.
2.2 Ограничения.
3. Формулировка цели.
Получили следующую задачу линейного программирования
Приведем её к каноническому виду
Обеспечим условия применения двойственного симплекс-метода. Сменим знаки левых и правых частей первых двух уравнений
![]() Занесем данные в симплекс-таблицу. Видим, что оценки переменных в последней строке первой симплекс-таблицы не положительны, то есть базисное решение
На первой итерации выбирается первая разрешающая строка (-15000< 0) и второй разрешающий столбец (120/75< 100/50). Выполняются операции однократного замещения. Получаем следующее приближение к области. На второй итерации разрешающая строка вторая (-6000, 0), разрешающий столбец первый (20/40=0.5< 8/5: 2/5=4). Следующее решение
Экономическая интерпретация полученного решения: для обеспечения минимального расхода древесины нужно работать 150 смен по первой технологии, 100 смен по второй технологии, при этом расход древесины будет составлять 27000 м3. Производство целлюлозы и лигнитов совпадает с плановым (так как x 3= x 4=0), выброс отравляющих веществ на 1000 кг меньше предельно-допустимых норм выброса.
Построим двойственную задачу. Для применения правил построения двойственных задач необходимо согласовать знаки неравенств с типом критерия:
Введем переменные двойственной задачи:
Тогда двойственная задача запишется в виде
Найдем оптимальное решение двойственной задачи из оптимальной симплекс-таблицы прямой задачи:
Казалось бы, полученное решение опровергает теорию получения оптимального решения двойственной задачи из оптимальной симплекс-таблицы прямой. Полученное решение Действительно, (5) – это не оптимальное решение задачи (4), двойственной к задаче (3). Вектор Хотя задачи (2) и (3) эквивалентны, имеют совпадающие области допустимых решений, но формы представления задач разные и двойственные к ним задачи будут отличаться не только формой, но и значением оптимальных решений. Однако оптимальные решения этих задач легко могут быть получены друг из друга.
Построим двойственную задачу к задаче (2):
После замены переменных задача (6) обращается в задачу (4). Таким образом, если из симплекс-таблицы получено оптимальное решение
Экономический смысл двойственных переменных:
Полученные оценки влияния рассмотренных параметров на оптимальное значение критерия справедливы в области устойчивости двойственных оценок.
|