Математическая модель задачи линейного программирования

Решение

Экономическая интерпретация.

Прямая задача: сколько единиц продукции П_j надо произвести, чтобы при заданной прибыли от единицы продукции, объемах имеющихся ресурсов и нормах расходов максимизировать прибыль от всей выпущенной продукции?

Двойственная задача: какова должна быть оценка единицы каждого из ресурсов , чтобы при заданной прибыли от единицы продукции, объемах имеющихся ресурсов и нормах расходов минимизировать общую оценку затрат на все ресурсы?

В примере 1.6 было получено решение прямой задачи графическим методом. Это , .

Для нахождения решения двойственной задачи запишем обе задачи в канонической форме:

Между переменными двойственных задач существует следующее соответствие:

Определим из канонической формы прямой задачи, какие переменные равны нулю в оптимальном плане и из приведенного соответствия определим отличные от нуля двойственные переменные. Так

,

,

,

,

.

Для нахождения отличных от нуля двойственных переменных и решим систему уравнений, полученную из системы ограничений канонической формы двойственной задачи:

Откуда . Таким образом, , или для двойственной задачи в симметричной форме . Причем .

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

Т. к. и отличны от нуля, то второй и третий ресурсы (сырье и электроэнергия) являются дефицитными. При этом , следовательно, наиболее дефицитным является второй ресурс (сырье). Поскольку , то ресурс первого вида (время работы оборудования) является избыточным. При увеличении сырья на 1 кг прибыль от всей выпущенной продукции увеличится на 3 руб., а при увеличении электроэнергии на 1 кВтч прибыль от всей выпущенной продукции увеличится на 1 руб.

Правила построения двойственной задачи

1) Если прямая задача на максимум, то двойственная к ней - на минимум, и наоборот.

2) Если прямая (двойственная) задача на максимум, то ограничения-неравенства системы представляются в виде неравенств типа , если на минимум, то ограничения-неравенства системы представляются в виде неравенств типа .

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

4) Матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием.

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

6) Если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение-неравенство, если же нет, то как ограничение-равенство.

7) Если какое-либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.

Пример 1.24

Составить задачу, двойственную к ЗЛП:

;

Решение

Воспользовавшись правилами построения двойственной задачи, получим следующую пару двойственных ЗЛП:

Пример 1.25

Составить задачу, двойственную к ЗЛП, рассмотренной в примере 1.8 (на максимум), т. е.

Из решения прямой задачи (пример 1.8) найти решение двойственной задачи.

Решение

Построим пару двойственных ЗЛП:

В примере 1.8 было получено решение прямой задачи графическим методом. Это , .

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

Между переменными двойственных задач существует следующее соответствие:

Определим из канонической формы прямой задачи, какие переменные равны нулю в оптимальном плане и из приведенного соответствия определим отличные от нуля двойственные переменные. Так

,

,

,

,

.

Для нахождения отличных от нуля двойственных переменных и решим систему уравнений, полученную из системы ограничений канонической формы двойственной задачи:

Откуда . Таким образом, , или для двойственной задачи в симметричной форме . Причем .

Пример 1.26

Составить задачу, двойственную к ЗЛП примера 1.22, т. е.

Из решения прямой задачи симплексным методом (пример 1.22) найти решение двойственной задачи.

Решение

Построим пару двойственных ЗЛП:

Для нахождения решения двойственной задачи запишем обе задачи в канонической форме:

Между переменными двойственных задач существует следующее соответствие:

Для нахождения оптимального плана двойственной задачи воспользуемся симплексной таблицей, в которой найден оптимальный план прямой задачи (табл. 1.18). Двойственные переменные, соответствующие базисным переменным прямой задачи будут равны нулю, а соответствующие свободным переменным - будут равны абсолютной величине оценок этих столбцов. Так , , - базисные переменные, следовательно, соответствующие им двойственные переменные , , будут равны нулю, т.е. , , . Найдем значения двойственных переменных, соответствующих свободным переменным прямой задачи:

,

,

.

Таким образом, , или для двойственной задачи в симметричной форме . Причем .

Размещено на Allbest.ru