9. Понятие двойственности. Построение двойственных задач, их свойства.

Предположим, что некот. организация решила закупить ресурсы предпр-ия S₁, S₂…S_n. И необходимо уст-ть оптим. цены на эти ресурсы y₁,y₂…y_n. Очевидно, что покупатель заинтересован в том, чтобы затраты на все ресурсы в кол-вах b₁,b₂,..b_n по ценам были минимальны. С др. стороны предприятие продающее ресурсы, заинтер-о в том, что бы полученная выручка была не меньше той суммы, кот. предпр-е может получить при переработке ресурсов в готов. прод-ю. Поэтому для удовл-я требований затраты ресурсов, потребляемых при изготовлении ед-цы продукции д/б не меньше ее цены, т.е. , где а₁₁ – кол-во сырья 1ого вида на пр-во прод-ии 1ого вида и т.д. с_i – цена продукции.

Это мат. модель двойств. задачи, т.е. b'c→min; Ay≥c; y≥0.

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

Свойства:

Если исходная задача став-тся на макс-м, то двойств. ей задача ставится на мин-м, и наоборот.
Коэф-ты при перем-х в цел. ф-ии одной задачи явл. свободными членами в сис-е ограничений др. задачи.
Каждая из задач определена в станд. форме, причем в задаче макс-ии все неравенства опред-тся как ≤, а в зад-е миним-ии - ≥
Матрицы коэф-ов в сис-ах ограничений обеих задач явл. транспонированными по отношении. др. к др.
Число неравенств в сис-е ограничений 1ой задачи совпадает с числом перем-ых др. задачи
Условия не «-» присутствует в обеих задачах

2 задачи, обладающие указанными св-ми наз. симметричными взаимно двойственными задачами, или просто двойственными задачами.

10. Основные теоремы двойственности.

Теорема1.(Осн. неравенство теории двойств-ти)

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

Теорема2.(Существ-ие оптим. планов)

Для существ-я реше-ия ЗЛП н. и д. чтобы не были пустыми множества планов прямой и двойств. задач.

Теорема3.(Достат. признак оптим-ти)

Если для некоторых допуст. планов х* и у* пары двойств. задач вып-тся рав-во f(x*)=z(y*), то х* и у* явл. оптим. планами соответствующих задач.

Теорема4.(Осн. т. двойств-ти)

Если 1 из двойств-ых задач имеет оптим. решение, то и др. задача имеет оптим. решение, причем оптим. значения их цел. ф-ий совпадают. Эк. содержание – если прямая ЗЛП разрешима, то и разрешима двойств. ей задача, причем цена продукции, получ-я от реализации оптим. плана совпадает с суммарной оценкой ресурсов. Совпадение значений цел. функций дост-но для того, что бы соотв-ие планы пары двойств. задач были оценены.

Теорема5.(о дополняющей нежесткости)

Для того, чтобы планы х* и у* пары двойств. задач были оптим. н. и д. вып-ие условий. Эк-ки это значит, что, Если оптимальная оценка го ресурса не равна нулю , то в оптимальном плане этот ресурс используется полностью (); Если в оптимальном плане ресурс не используется полностью (), то его оценка равна нулю; Если ый продукт входит в оптимальный план , то в оптимальных оценках ресурсов он неубыточен (); если ый продукт в оптимальных оценках ресурсов убыточен (), то он не входит в оптимальный план .