Здавалка
Главная | Обратная связь

Двойственные задачи и их экономическая интерпретация. Метод одновременного решения прямой и двойственной задач линейного программирования.

Понятие двойственности рассмотрим на примере задачи оптимального использования сырья. Пусть на предприятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья т видов в объемах bi единиц (i = ). Из этих отходов, учитывая специализацию предприятия, можно наладить выпуск п видов неосновной продукции. Обозначим через aij норму расхода сырья i-го вида на единицу j-й (j= ) продукции, сj — цена реализации единицы j-й продукции (реализация обеспечена). Неизвестные величины задачи: хj — объемы выпуска j-й продукции, обеспечивающие предприятию максимум выручки.

Математическая модель задачи:

F= c1x1 + c2x2 +…+ cnxn (max) (1)

(2)

xj 0 (j = ). (3)

 

Предположим далее, что с самого начала при изучении вопроса об использовании отходов основного производства на предприятии появилась возможность реализации их некоторой организации. Необходимо установить прикидочные оценки (цены) на эти отходы. Обозначим их у1, y2, ...., yт. Оценки должны быть установлены исходя из следующих требований, отражающих несовпадающие интересы предприятия и организации: 1) общую стоимость отходов сырья покупающая организация стремится минимизировать; 2) предприятие согласно уступить отходы только по таким ценам, при которых оно получит за них выручку, не меньшую той, что могло бы получить, организовав собственное производство. Эти требования формализуются в виде следующей ЗЛП.

Требование 1 покупающей организации — минимизация покупки:

f = b1y1 + b2y2 +…+ bmym (min) (4)

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

a11y1 + a21y2 +…+ am1ym ≥ c1,

где левая часть означает выручку за сырье, идущее на единицу продукции первого вида; правая — ее цену.

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

(5)

По смыслу задачи оценки должны быть неотрицательными:

y10, y2 0, …, ym0 (6)

Переменные уi (i= ) называются двойственными оценками или объективно обусловленными оценками. В зарубежной литературе их еще называют теневыми ценами.

Задачи (1) — (3) и (4) — (6) называются парой взаимно двойственных ЗЛП. Так как задачи (1) — (3) и (4) — (6) записаны в симметричной форме, их принято называть парой симметричных двойственных задач.

Пара взаимно двойственных симметричных задач в виде конечных сумм имеет вид:

прямая задача двойственная задача
max F = (7) min f = (10)
(8) (11)
xj ≥ 0 (j= ), (9) yi ≥ 0 (i= ) (12)

или в матричной форме:

max Z = CXT; min f = BTY;
AXT B, ATYT ≥ C,
X ≥ 0; Y ≥ 0.

 

Можно показать, что если в качестве прямой принять задачу (4) — (6) об определении оптимальных оценок на сырье, то двойственной к ней будет задача (1) — (3) об определении оптимального плана выпуска продукции.

Из моделей (1) — (3) и (4) — (6) непосредственно видно, что, имея математическую модель одной из этих задач, можно легко построить модель двойственной к ней задачи. Сопоставляя модели (1) — (3) и (4) — (6) пары двойственных задач, можно установить следующие взаимосвязи.

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

2. Коэффициенты сj целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.

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

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

5.Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа ≤. Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа ≥.

6.Число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной — числу переменных прямой.

7.Все переменные в обеих задачах неотрицательны.





©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.