Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Переход к двойственной задаче, теоремы двойственности.

Читайте также:
  1. C. Замену ручного труда машинным, переход от мануфактуры к фабрике
  2. I. ПОДГОТОВКА И ПЕРЕХОД К НОВОЙ СТРАТЕГИИ РЕФОРМ (1985-1987-1988 гг.)
  3. R закон перехода количественных изменений в качественные
  4. Актуальность перехода России на энергосберегающий тип развития экономики.
  5. Античная математика. Метод дедукции. Теоремы и аксиомы.
  6. Аффективно-экзальтированный тип – характеризуется легким переходом от состояния восторга к состоянию печали, бурным проявлением восторга и печали.
  7. Безусловный переход. Оператор выбора.
  8. Бил8. Воп.1.Психолого-педагогические проблемы перехода младших школьников в среднюю школу: диагностика, развивающая работа
  9. В активном режиме в переходах биполярного транзистора происходят процессы
  10. В период перехода к рыночной экономике

 

Во многих случаях вместо решения прямой задачи ЛП, можно решать двойственную ей задачу. Это выгодно в тех случаях, когда в исходной задаче количество ограничений намного превышает число переменных. Так как количество вычислений в основном зависит от числа ограничений. Сложность расчетов пропорциональна m^3, применяя двойственную задачу можем иметь значительный выигрыш по времени. На картинке — трансформация прямой задачи в двойственную.

 

Пояснения к табличке: двойственная задача получается путем симметричного структурного преобразования условий прямой задачи.

 

1. Каждому ограничению прямой задачи соответствует одна переменная двойственной задачи.

2. Каждой переменной прямой задачи соответствует ограничение двойственной задачи.

3. Коэффициенты при переменных, фигурирующие в ограничениях прямой задачи становятся коэффициентами левой части ограничений двойственной задачи.

4. Коэффициенты, стоящие при переменной в выражении целевой функции прямой задачи переходят в постоянные в правой части ограничений двойственной задачи.

 

 

Теорема двойственности 1.

 

Если одна из пары двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремумы их целевых функций совпадают. Следовательно если у одной задачи решение неограничено, то двойственная задача не имеет допустимых решений.

 

Теорема двойственности 2.

Для того, чтобы вектор х и лямбда необходимо и достаточно, чтобы решения удовлетворяли следующим равенствам:

Xj*(∑(i=1,m)ai,jлямбдаi*-cj)=0

Лямбдаi*=(∑(j=1,n)aijxj*-bi)=0

Это и есть формулы задачи Куна-Такера.

 

Теорема двойственности 3

 

Значения переменных лямбда в оптимальном решении двойственной задачи представляют собой оценки влияния исходной задачи на экстремальное значение ее целевой функции.

Решение двойственной задачи определяет чувствительность решения прямой задачи относительно ограничений.

При этом если лямбда — решение двойственно задачи, то все лямбдаi можно записать, как производные целевой функции по правым коэффициентам ограничений, которые определяют скорость изменения целевой функции.

 

Билет 11.

Целочисленное программирование (ЦП). Общая постановка задач ЦП.

Даны n неделимых предметов, каждый обладает m-характеристиками (полезностью), необходимо найти такой набор из этих предметов, который позволяет максимизировать их использование при наличии ресурсов по каждой характеристики.

 




Дата добавления: 2015-02-16; просмотров: 26 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав