Аннотация: Теория двойственности — это теория, изучающая взаимосвязь между исходной и двойственной задачами в линейном программировании.
Эта статья опубликована в сообществе HUAWEI CLOUD.«Теория двойственности и закон двойственной простоты», оригинальный автор: Jinggangshan _ Yangchun.
Линейное программирование (ЛП) — важная ветвь исследования операций с более ранними исследованиями, более быстрой разработкой, более широким применением и более зрелыми методами.Это математический метод, помогающий людям в научном управлении. Теория двойственности — это теория, изучающая взаимосвязь между исходной и двойственной задачами в линейном программировании.
1. Постановка двойственной задачи.
Двойственность — это одна и та же проблема, рассматриваемая под двумя разными углами, есть два квазипротивоположных выражения. Например, «отношение между площадью и периметром прямоугольника» имеет следующие два выражения:
-
Прямоугольник с определенным периметром и наибольшей площадью является квадратом;
-
Прямоугольник с заданной площадью и наименьшим периметром является квадратом.
Другим примером является проблема планирования производства.Как показано на рисунке 1, фабрике необходимо производить два вида продукции I и II, а сырье для производства — A и B соответственно, а также существуют ограничения на общее производственное оборудование.
Тогда, сколько произведено продукции I и II соответственно, может максимизировать выгоду от производства.Очевидно, что с точки зрения продавца с помощью линейного программирования получается оптимизационная модель M1:
где х1 и х2 – количество единиц, планируемых для производства продукции I и II соответственно. С другой точки зрения, с точки зрения покупателя, второй заключается в том, чтобы напрямую покупать сырье для производства, не покупая продукты.С точки зрения прибыльности, предполагая, что цена каждого производственного сырья составляет y1, y2 и y3, покупатель надеется получить купить по наименьшей стоимости. , поэтому существует следующая оптимизационная модель M2:
Выше приведены два примера, иллюстрирующие двойственную проблему. Таблица соответствия между основной проблемой и двойственной проблемой приведена непосредственно ниже:
Это соответствие может быть выведено из двойственности Лагранжа, которая здесь не будет вводиться.Ууху. Call.com/question/58….
2. Двойственная задача стандартной задачи ЛП
Стандартная задача ЛП:
Двойная проблема:
Сделайте несколько простых выводов для взаимосвязи между решением основной задачи и двойственной задачи:
где xB и xN соответствуют базовым переменным и небазисным переменным соответственно, B и N – матрицы, соответствующие базисным и небазисным переменным, а cB и cN соответствуют стоимостным коэффициентам. Из приведенного выше вывода видно, что решение двойственной задачи имеет соответствующую связь с номером теста исходной задачи, и эта связь очень важна для понимания двойственного симплекс-метода.
3. Природа двойственной проблемы
3.1 Симметрия
3.2 Слабая двойственность
Слабая двойственность показывает, что, пока найдено допустимое решение основной задачи и двойственной задачи, можно определить верхнюю и нижнюю границы друг друга. Из слабой двойственности можно вывести два важных следствия:
3.3 Сильная двойственность
3.4 Условие оптимальности
4. Метод двойной простоты
Прежде всего, из общей концепции, давайте разберемся с примитивным симплексным методом и двойным симплексным методом:
Далее выводится двойственный симплекс-метод.На самом деле основное отличие двойного симплекс-метода от симплекс-метода в том, что он отличается от стратегии входа и выхода из базиса.Вывод стратегии входа и выхода из базиса двойственного симплекс-метода описано ниже.Следует подчеркнуть, что предпосылка вывода двойственного симплекс-метода состоит в том, что начальное решение удовлетворяет двойственной допустимости (номер теста исходной задачи больше 0).
Наконец, даны конкретные шаги двойного симплекс-метода:
Нажмите «Подписаться», чтобы впервые узнать о новых технологиях HUAWEI CLOUD~