Читайте также:
|
|
Во многих случаях вместо решения прямой задачи ЛП, можно решать двойственную ей задачу. Это выгодно в тех случаях, когда в исходной задаче количество ограничений намного превышает число переменных. Так как количество вычислений в основном зависит от числа ограничений. Сложность расчетов пропорциональна 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 | Поможем написать вашу работу | Нарушение авторских прав |