- •1.Основные понятия и этапы са
- •2. Операция и ее составляющие. Этапы исо
- •Этапы операционного проекта
- •Виды математических моделей ио, примеры.
- •4. Состязательные задачи. Решение игры 2-х лиц
- •7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
- •В общем случае модель задачи лп имеет вид
- •Сбалансированная транспортная задача
- •8 Формы представления задач лп и способы приведения к ним
- •1. Каноническая форма задач лп
- •2. Стандартная форма задачи лп
- •9. Основные понятия лп. Свойства задач лп
- •10. Геометрия задач лп, базисные решения, вырожденность.
- •4.7. Выделение вершин допустимого множества
- •11. Понятие базиса. Переход от одного базисного решения к другому
- •12. Признак оптимальности. Определение начального базисного решения.
- •13. Алгоритм симплекс-метода
- •14. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.3. Запись двойственной задачи в общем случае
- •15.Экономическая интерпретация двойственной задачи
- •16. Теоремы двойственности
- •17. Двойственный и модифицированный симплекс-метод Модифицированный алгоритм
- •18. Параметрический анализ. Параметрирование вектора ограничениий
- •Параметрирование вектора ограничениий
- •19. Параметрирование коэффициентов линейной формы
- •20. Модели транспортных задач и их характеристика, условия разрешимости.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Транспортные задачи по критерию времени
- •21. Построение начального плана перевозок т-задачи
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •22.Обоснование метода потенциалов
- •5.2.3. Признак оптимальности
- •23. Алгоритм метода потенциалов.
- •24. Двойственная пара транспортных задач
- •25. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •26. Приведение открытой транспортной задачи к закрытой
- •27. Транспортные задачи в сетевой постановке (транспортные сети)
- •28. Задача о максимальном потоке
- •29. Метод декомпозиции Данцига - Вулфа
- •30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
- •32. Целочисленное программирование
- •7.1. Проблема целочисленности
- •33. Метод отсечений
- •Пример 7.1. Выведем условие отсечения для задачи
- •34. Метод ветвей и границ
- •35. Аддитивный алгоритм
- •36. Нелинейное программирование
- •Теорема
- •37. Квадратичное программирование
- •38. Сепарабельное программирование (сп) и дробно-линейное программирование
- •8.5. Задачи дробно-линейного программирования
- •39. Метод покоординатного спуска и Хука-Дживса Метод первого порядка
- •8.8. Многомерный поиск безусловного минимума
- •8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций) Метод первого порядка
- •Метод Хука-Дживса (метод конфигураций)
- •40. Симплексный метод поиска
- •41. Градиентные методы
- •Методы сопряженных направлений
- •43. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •44. Метод проектирования градиента
- •Метод проектирования градиента
- •45. Генетические алгоритмы
- •46. Метод штрафных функций и барьерных функций
- •Метод барьерных функций
- •47. Динамическое программирование
- •48. Распределение одного вида ресурса
- •49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
- •Задача с мультипликативным критерием.
- •52. Многомерные задачи динамического программирования
- •53. Снижение размерности с помощью множителей Лагранжа
- •56. Многокритериальные задачи: постановка, проблемы, осн. Понятия, методы
- •Многокритериальная задача математического программирования
- •Где искать оптимальное решение
- •Определения
- •Условия оптимальности
- •57. Многокритериальные задачи: функция полезности, лексикографический анализ
- •Методы первой группы
- •Функция полезности
- •Решение на основе лексикографического упорядочения критериев
- •58. Методы главного критерия, свертки, идеальной точки, целевого прогр. Метод главного критерия
- •Линейная свертка
- •Максиминная свертка
- •Метод идеальной точки
- •Целевое программирование (цп)
- •59. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
16. Теоремы двойственности
Между решениями прямой и двойственной задач существует тесная взаимосвязь, которая устанавливается теоремами двойственности. Эта связь позволяет по решению одной задачи двойственной пары получать решение другой. Основными являются две теоремы, первая из которых определяет связи критериев, а вторая условий и переменных. Мы сначала рассмотрим составляющие второй теоремы как самостоятельные теоремы, а затем приведем сводную. Аналогично поступим и с первой основной теоремой двойственности.
Теорема 1. Если в оптимальном решении прямой задачи условие выполняется как строгое неравенство
, (4.32)
то соответствующая двойственная переменная равна нулю, то есть
О боснование следует из смысла двойственных переменных. Неравенство (4.32) означает, что i-й ресурс используется не полностью, следовательно, малое изменение этого ресурса не повлияет на результат деятельности (критерий) и поэтому значение двойственной переменной равно нулю.
Следствие. Если дополнительная переменная в i-м условии прямой задачи больше нуля, то соответствующая двойственная переменная равна нулю.
Действительно, в этом случае i-е условие без дополнительной переменной будет заведомо строгим неравенством, что и оговорено в теореме.
Теорема 2. Если в единственном оптимальном решении прямой задачи условие выполняется как равенство, то есть
(4.33)
то соответствующая двойственная переменная будет заведомо не равна нулю.
Равенство (4.33) означает, что i-й ресурс полностью исчерпан, следовательно, малые изменения этого ресурса обязательно приведут к изменению критерия и поэтому его значимость не равна нулю.
Следствие. Если дополнительная переменная в i-м условии равна нулю, то двойственная переменная этого условия не равна нулю.
Н а рис.4.9 приведена геометрическая интерпретация рассмотренных теорем для случая единственного оптимального решения (вершина А). Здесь допустимое множество D образовано четырьмя условиями- неравенствами с ресурсами b1, b2, b3 и b4. В оптимальном решении по 1-му и 2-му ресурсам выполняется равенство и изменение любого из них (показано пунктиром для b1) приводит к перемещению оптимальной вершины и, следовательно, критерия. Поэтому значимость этих ресурсов или их двойственные переменные отличны от нуля. В то же время по 3-му и 4-му ресурсам имеем строгие неравенства и их изменения не влияют на оптимальное значение критерия, что соответствует нулевым дополнительным переменным.
Случай с неединственным оптимальным решением показан на рис.4.10. Линия оптимального значения критерия L* совпадает с границей по 2-му ресурсу. В оптимальном решении, соответствующем вершине А, первые два ресурса используются полностью. Однако изменение b1 не приводит к изменению критерия, тогда как любое изменение b2 отражается на оптимальном значении критерия. Поэтому оценки этих ресурсов разные: U1=0, U20.
Теоремы 1 и 2 легко трансформируются для двойственной задачи.
Теорема . Если в оптимальном решении двойственной задачи условие выполняется как строгое неравенство
(4.34) то соответствующая переменная прямой задачи равна нулю:
Интерпретация: если затраты превышают производимую стоимость, то производить такую продукцию невыгодно.
Теорема Если в единственном оптимальном решении двойственной задачи условие выполняется как равенство, то соответствующая переменная прямой задачи строго больше нуля:
. (4.35)
Так как производимая стоимость равна затратам, то производство такой продукции окупается.
Обобщением рассмотренных теорем является вторая основная теорема двойственности:
Для того чтобы векторы X* и U* являлись оптимальными решениями прямой и двойственной задач соответственно, необходимо и достаточно выполнение следующих условий:
(4.36)
Эта теорема учитывает и случай множественности оптимальных решений, когда равенству в одной задаче может сответствовать нулевая переменная в другой.
Теперь покажем на конкретном примере, как приведенные теоремы позволяют находить решение одной из задач двойственной пары по известному решению другой.
Пример 4.5. Рассмотрим задачу, которая решалась ранее графически и симплекс-методом.
-
Прямая задача (ПЗ)
L=7x1+5x2→max,
2x1+3x219,
2x1+x213,
3x212,
3x117,
x10, x20
Каноническая форма ПЗ
L=7x1+5x2→max,
2x1+3x2+x3=19,
2x1+x2+ x4=13,
3x2+x5=12,
3x1+x6=17,
xj0.
Оптимальное решение этой задачи:
Запишем модель двойственной задачи (ДЗ):
=19U1+13U2+12U3+17U4miin;
2U1+2U2+3U47;
3U1+U2+3U35;
Ui 0.
Получим ее решение на основе решения ПЗ и теорем двойственности.
Так как дополнительные переменные х5 и х6, входящие в третье и четвертое условия ПЗ, в оптимальном решении не равны нулю, то согласно следствию теоремы 1
.
Из первой группы условий (4.36) следует, что если исходная переменная ПЗ не равна нулю, то ограничение ДЗ будет выпополняться как равенство. Поэтому в нашем примере имеем:
Получили систему 2-х уравнений с двумя неизвестными. Ее решение:
.
Таким образом, мы нашли решение ДЗ без применения симплекс-метода. Как увидим ниже, равенство оптимальных значений критериев ПЗ и ДЗ не случайно. Разумеется, таким способом решать ДЗ нецелесообразно, так как в реальных случаях пришлось бы решать систему уравнений большой размерности. Пример только демонстрирует связь решений двойственной пары задач, а значения двойственных переменных легко получить из оптимальной симплекс-таблицы ПЗ. Они расположены в вспомогательной строке Z в столбцах начального базиса. Обратившись к симплекс-таблице 3 в разд.4.9.7, легко убедиться в справедливости этого способа нахождения двойственных переменных (см. в столбцах А3, А4, А5 и А6).
Следующая группа теорем определяет связь между критерими двойственной пары задач.
Теорема 3. Если X и U – допустимые решения прямой и двойственной задач соответственно, то
L(X) (U). (4.37)
Доказательство. Так как допустимость решений означает выполнение неравенств в ПЗ и в ДЗ, то очевидна цепочка соотношений
из которой следует справедливость теоремы.
Таким образом, для любых допустимых решений значение критерия прямой задачи не может превышать значение критерия двойственной.
Теорема 4. Если X* и U* - допустимые решения прямой и двойственной задач и L(X*)= (U*), то они являются оптимальными решениями двойственной пары задач.
Доказательство. Согласно теореме 3 для любого допустимого X справедливо неравенство
L(X) (U*).
И так как L(X*)= (U*) по условию теоремы, то L(X)L(X*). Следовательно, X*- оптимальное решение прямой задачи по определению.
Аналогично доказывается оптимальность U* для двойственной задачи.
Теорема 5. Для любых оптимальных X* и U* линейные формы прямой и двойственной задач равны:
L(X*)= (U*). (4.38)
Доказательство. В оптимальных решениях выполняются равенства (4.36). Суммируя первую группу по j , а вторую по i и сделав простые преобразования, получаем
Из равенства левых частей следует равенство правых и, значит, справедливость теоремы.
Теперь ясно, что совпадение значений критериев в приведенном примере не является случайным.
Теорема позволяет строго объяснить смысл двойственных переменных. Действительно, правомерна запись L*= *= . Отсюда имеем
(4.39)
Таким образом, в оптимальном решении двойственная переменная является производной оптимального значения критерия по правой части ограничения. Значит, как уже говорилось, оптимальная двойственная переменная показывает, как изменится оптимальное значение критерия при изменении ресурса на единицу (она равна этому изменению критерия).
Теорема 6. Если линейная форма одной из задач двойственной пары не ограничена, то условия другой противоречивы. (Обратное не всегда верно, возможна противоречивость в обеих задачах).
Доказательство проведем от противного. Допустим, что при неограниченности L(x) сверху в прямой задаче условия двойственной задачи непротиворечивы. Тогда существует допустимое решение ДЗ, на котором. значение ее критерия конечно. Но согдасно теореме 3 для допустимых решений должно выполняться неравенство L(x) (U), что при принятом допущении невозможно (L бесконечно, а конечно). Следовательно, ДЗ не может иметь допустимых решений, то есть ее условия противоречивы.
Аналогично доказывается 2-я часть теоремы для случая неограниченности снизу .
Обобщением теорем 3-5 является первая основная теорема двойственности:
Если одна из задач двойственной пары разрешима, то и другая задача разрешима, при этом оптимальные значения критериев равны; при неразрешимости одной из задач другая тоже неразрешима.▲
Что дает двойственность для решения задач ЛП помимо анализа? Во-первых, вместо решения исходной задачи можно решать двойственную. Это выгодно, если в ПЗ число условий существенно больше числа переменных (тогда в ДЗ будет меньше ограничений и потребуется меньше итераций). Кроме того, переход к ДЗ может уменьшить число искусственных переменных или исключить их совсем.
Во-вторых, теория двойственности породила такие методы как двойственный симплекс-метод и метод сокращения невязок или венгерский метод. В последнем используются неотрицательные оптимальные решения, при которых не выпоняются некоторые ограничения-равенства (имеются невязки), но от итерации к итерации невязки уменьшаются. Нулевые невязки являются признаком достижения допустимого оптимального решения. Метод применяется в основном для решения транспортных задач.