ИССО-для ГОСов / Двойственные задачи линейного программирования

Двойственные задачи линейного программирования.

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

Алгоритм составления двойственной задачи.

1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум целевой функции, то все неравенства системы ограничений привести к виду “”, а если минимум – к виду “”. Для этого неравенства, в которых данное требование не выполняется, умножить на –1.

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

3. Найти матрицу , транспортную к матрице А₁.

4. Сформулировать двойственную задачу на основании полученной матрицы и условия неотрицательности переменных.

Пример 1.

Составить двойственную задачу

Решение

1. Приводим все неравенства системы ограничений исходной задачи к одному смыслу

2. Составляем расширенную матрицу

3. Транспонируем матрицу

4. Формулируем двойственную задачу

Исходная (прямая) задача	Двойственная задача

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

переменная у_i двойственной задачи представляет стоимость единицы ресурса i. В литературе по исследованию операций переменные у_i двойственной задачи часто называют двойственными ценами. Кроме того, иногда их именуют теневыми ценами и симплексными мультипликаторами.

    Аналогично для любой пары допустимых решений прямой и двойственной задач неравенство f < z можно интерпретировать следующим образом:

Доход < Общая стоимость ресурсов

    Это соотношение показывает, что до тех пор, пока суммарный доход от всех видов деятельности строго меньше суммарной стоимости всех используемых ресурсов, решение как прямой, так и двойственной задачи не может быть оптимальным. Оптимум (максимальный доход) может быть достигнут только тогда, когда все потребляемые ресурсы использованы полностью.

Большой практический интерес представляет экономическая интерпретация второй теоремы двойственности, а также ее следствия  о дополняющей нежесткости.

            1. Если суммарная оценка  i-го ресурса положительна

                                                          

то этот ресурс в соответствии с оптимальным планом  х* используется полностью

                                  

            2. Если i-й ресурс используется не полностью

                                  

то его оптимальная оценка нулевая    и i-е ограничение несущественно.

            3. Если в соответствии с оптимальным планом х* j-я продукция производится

                                                

то это производство эффективно, так как цена единицы j-й продукции

                                                          

равна затратам на ее производство в единицах

                                  

                                  

            4. Если производство j-й продукции убыточно (приведенные издержки ненулевые

                                  

то в соответствии с оптимальным планом эта продукция не производится

                                  

Таким образом, двойственные оценки связаны с оптимальным планом прямой задачи. Всякое изменение исходных данных прямой задачи оказывает влияние на ее оптимальный план и систему двойственных оценок. В свою очередь двойственные оценки служат инструментом анализа и принятия правильных решений в условиях меняющихся коммерческих ситуаций.