Двоїсті задачі лінійного програмування. Двоїстий симплекс-метод

Понятие двойственности в линейном программировании представляет значительный интерес в отношении совер­шенствования методов планирования и управления отдель­ными звеньями народного хозяйства. Например, решение различных задач оптимального планирования и организа­ции производства связано с затратами определенных ресур­сов и выпуском некоторой продукции. В этом случае теория двойственности устанавливает связь между оптимальным распределением ресурсов н некоторой системой оценок на эти ресурсы.

Основные теоретические положения двойственности по­зволили построить эффективный алгоритм решения задачи линейного программирования, названный двойственным симплекс-методом.

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

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

Определим двойственную задачу по отношению к общей задаче линейного программирования следующего вида:

при условиях

Определение: Задача, состоящая в нахожде­нии минимального значения целевой функции

приусловиях

называется двойственной по отношению к задаче (2.32) — (2.34), которую назовем прямой.

Прямая задача (2.32) — (2.34) и двойственная (2.35) — (2.37) являются взаимно двойственными, т. е. если задачу (2.35)— (2.37) рассматривать как прямую, то задача (2.32) — (2.34) к ней — двойственная задача. Эти задачи образуют пару двойственных задач.

Из сравнения приведенных задач следует, что двойствен­ная задача получается путем симметричного структур­ного преобразования условий прямой задачи в соответствии со следующими правилами.

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

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

3. Матрицы, составленные из коэффициентов при неиз­вестных в системах ограничений (2.33) прямой задачи и (2.36) двойственной задачи взаимно транспонированы.

4. Коэффициенты при неизвестных в целевой функции (2.36) двойственной задачи являются свободными членами в системе ограничений (2.33) прямой задачи, а правыми час­тями в соотношениях системы (2.36) двойственной задачи — коэффициенты при неизвестных в целевой функции (2.32) прямой задачи, и наоборот.

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

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

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

Рассмотрим пару двойственных задач, образованную канонической задачей линейного программирования и двой­ственной к ней.

Прямая задача:

Двойственная задача:

Зависимость между решениями прямой и двойственной задач определяется следующими теоремами двойствен­ности.

ТЕОРЕМА 1 (первая теорема двойственности).

1. Если одна из пары двойственных задач (2.38) — (2.40) или (2.41) — (2.42) имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций для их оптимальных планов равны между собой, т. е.

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

ТЕОРЕМА 2 (вторая теорема двойственности). План X* = (х1,..., х_п) задачи (2.38) — (2.40) и план Y* = (y1,…,ym)задачи (2.41) — (2.42) являются оптималь­ными планами этих задач тогда и только тогда, когда для любого выполняется равенство

или для любого выполняется равенство

С учетом внутренней связи пары двойственных задач построен алгоритм двойственного симплекс-метода. В идей­ном отношении алгоритм двойственного симплекс-метода имеет много общего с алгоритмом прямого симплекс-метода. По сравнению с прямым симплекс-методом в двойственном симплекс-методе роль строк играют столбцы, а роль столб­цов — строки. Поэтому если в прямом симплекс-методе вы­числения начинаются с таблицы, в которой элементы опор­ного плана (нулевого столбца) неотрицательны, то в двойст­венном — с таблицы, в которой элементы нулевой строки неотрицательны. В прямом методе сначала определяется разрешающий столбец, а затем разрешающая строка; в двойственном методе — наоборот: сначала разрешающая строка, а затем разрешающий столбец. Признак оптималь­ности для обоих методов одинаков: неотрицательность эле­ментов нулевого столбца и элементов нулевой строки.

Итак, для формулировки алгоритма двойственного симплекс-метода рассмотрим задачу в канонической форме, приведенной к единичному базису, нулевое приведенное уравнение которой не содержит отрицательных коэффици­ентов:

В данном случае X = (b1, b_г;...; b_т; 0;...; 0) — базис­ное решение системы уравнений (2.44). Однако это решение не является опорным планом задачи (2 43) — (2.45), так как среди его компонент имеются отрицательные числа.

Определение: Базисное решение X = (b1;......; b_m; 0;...; 0) системы уравнений (2.44) называется псевдопланом задачи (2.43) — (2.45), если для любого .

ТЕОРЕМА 3. Если в псевдоплане есть хотя бы одно отрицательное число b_i < 0 такое, что все , то задача (2.43) — (2.45) вообще не имеет опорных пла­нов.

ТЕОРЕМА 4. Если в псевдоплане X имеются отрица­тельные числа b_i < 0 такие, что для любого из них сущест­вует хотя бы одно , то можно перейти к новому псевдоплану.

Сформулированные теоремы дают основание для пост­роения алгоритма двойственного симплекс-метода, который включает в себя следующие основные шаги.

1. Построение псевдоплана в канонической форме зада­чи и заполнение таблицы, аналогичной симплекс-таблице.

2. Выбор разрешающей строки, для которой b j< 0. Если все bj 0, то псевдоплан является оптимальным опор­ным планом, т. e. найдено решение задачи.

3.Выбор разрешающего столбца по наименьшему по абсолютной величине отношению элементов нулевой строки к соответствующим отрицательным элементам разрешающей строки.

На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент .

4. Пересчет элементов таблицы по формулам Жордана — Гаусса

В результате определяется новый псевдоплан и все действия повторяются, начиная с п. 2.