Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Топ:
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Интересное:
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Дисциплины:
2017-05-16 | 355 |
5.00
из
|
Заказать работу |
|
|
Теорема двойственности. Если из пары двойственных задач одна имеет оптимальный план, то и вторая тоже имеет оптимальный план, причем оптимальные значения целевых функций обеих задач равны между собой:
.
При этом . Отсюда следует, что двойственная переменная yi является коэффициентом при bi и, следовательно, показывает, как изменится целевая функция при изменении i- го ресурса на единицу. В литературе двойственные переменные часто называют двойственными оценками.
Теорема равновесия. План прямой задачи и план соответствующей двойственной задачи являются оптимальными при выполнении следующих условий:
- если при подстановке компонент оптимального плана в систему ограничений исходной задачи i-е ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю.
- если i-я компонента оптимального плана двойственной задачи положительна, то i-е ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство.
Таким образом, в парах соотношений
из знака строгого неравенства во одном соотношении каждой пары следует знак строгого равенства в другом.
Условия теоремы равновесия часто записывают в виде
и называют условиями дополняющей нежесткости.
Из рассмотренных теорем можно сделать следующие выводы:
А) Всякий раз, когда i-е ограничение прямой задачи обращается в строгое неравенство, i-я компонента решения двойственной задачи обращается в 0.
Аналогично, всякий раз, когда i-е ограничение двойственной задачи выполняется как строгое неравенство, j-ая компонента оптимального плана обращается в ноль.
Б) Обратно, если i-я компонента оптимального плана двойственной задачи положительна, i -е ограничение исходной задачи выполняется как строгое равенство. Верно и для двойственной задачи.
|
Отсюда следует:
а) Если двойственная оценка yi * = 0, то сырье i-го вида не полностью используется при производстве продукции.
б) Если j-е ограничение двойственной задачи выполняется как строгое неравенство, то j-ый вид продукции выпускать экономически нецелесообразно, хj =0 (т.е. в двойственной задаче цена всех ресурсов больше прибыли)
в) Если yi ¹ 0, то сырье i-го типа полностью используется при производстве.
Значения двойственных оценок можно определить по симплексной таблице решения прямой задачи следующим образом: -(), где j-номера столбцов единичных векторов из исходной симплекс-таблицы (на начальной итерации); -окончательные оценки из последней симплекс-таблицы, соответствующие этим векторам. При этом индексы двойственных оценок определяются номером ограничения, которому они соответствуют.
Необходимо заметить, что если в качестве канонической формы рассматривается задача максимизации, то сумма берется без знака “-“.
Двойственный симплекс-метод
Пусть необходимо решить задачу линейного программирования, записанную в канонической форме
Рассмотрим начальную симплекс-таблицу этой задачи. Очевидно, что в ее столбцах записана прямая задача, а в строках — двойственная. Оценками плана исходной задачи является — сj, а оценками плана двойственной задачи bi.
Решим двойственную задачу по симплекс-таблице исходной задачи. Найдем решение двойственной задачи, а вместе с ним опорный план исходной задачи. Этот метод называется двойственным симплекс-методом.
Особенностью двойственного симплекс-метода является то, что его можно применять при решении задач линейного программирования. правые части ограничений которых являются отрицательными числами.
Алгоритм двойственного симплекс-метода.
1. (выбор ведущей строки l)
2. Если в ведущей строке l , то исходная задача не имеет решения. Если есть , то выбирается ведущий столбец.
|
- если исходная задача на максимум, то ‘-‘.
3. Пересчет элементов c-таблицы осуществляется по правилу симплекс метода.
4. - признак оптимальности решения(когда все правые части неотрицательны)
|
|
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!