7. Теорема о связи решений прямой и двойственной задачи.

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

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

Fmax=Zmin или Fmin=Zmax

Замечание. Если линейная форма одной из двойственных задач не ограничена, то условия другой задачи противоречивы.

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

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

Из теорем 1 и 2 следует вывод, что, решив одну из взаимно двойственных задач, т.е. найдя её оптимальное решение и оптимум линейной формы, мы можем записать оптимальное решение оптимум линейной формы другой задачи.

2 вариант ответа:

Первая (основная) теорема двойственности

Теорема: Если одна из сопряженных задач имеет оптимальное решение , то и вторая имеет оптимальное решениепри этом

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

Вторая теорема двойственности (о дополнительной нежесткости)

Теорема: Для того чтобы два допустимых решения ипары двойственных задач были их оптимальными решениями необходимо и достаточно, чтобы они удовлетворяли системе уравнений

                (1)              

Замечание: Теорема верна для симметричной двойственной пары, для задач в канонической и общей форме соотношения (1) верны только для ограничений в виде неравенств и для неотрицательных переменных.   

8. Метод северо-западного угла.

Метод «северо-западного угла» — метод (правило) получения допустимого начального решения транспортной задачи. 

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

Шаг 0. Условие транспортной задачи задают в виде транспортной таблицы.

Шаг 1. Проверяют выполнение условия баланса. Если условие баланса не выполняется, т.е. задача открытая, то ее сводят к закрытому типу.

Шаг 2. Создают таблицу плана перевозок, в которой заполнены только объемы производства и объемы потребления. Далее начинают заполнять таблицу перевозок с левого верхнего (северо-западного) угла. При заполнении двигаются по строке вправо и по столбцу вниз.

Процесс про­должают до тех пор, пока не исчерпаются предложения и полностью не удовлетворится спрос.