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

В стандартной форме прямая задача (1) линейного программирования записывается следующим образом. Необходимо определить n - мерный вектор неотрицательных переменных , при котором достигается максимум целевой функции:

, (1.1)

или:

, (1.2)

с учетом ограничений: (1)

, (1.3)

или:

(1.4)

Чтобы сформулировать условия двойственной задачи, проведем симметричное структурное преобразование условий прямой задачи в соответствии с правилами:

1) каждому ограничению прямой задачи соответствует переменная двойственной задачи;

2) каждой переменной прямой задачи соответствует ограничение двойственной задачи;

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

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

, (2.1)

или:

, (2.2)

с учетом ограничений: (2)

, (2.3)

или:

(2.4)

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

1. Число переменных y_i в двойственной задаче равно числу ограничений в прямой задаче, i =1,…, m. Каждому ограничению исходной задачи соответствует переменная двойственной задачи (номер переменной равен номеру ограничения). Число ограничений двойственной задачи равно числу переменных x_j исходной задачи j =1,…, n.

2. Матрица коэффициентов системы ограничений двойственной задачи получается из матрицы коэффициентов системы ограничений прямой задачи путем транспонирования. Матрица коэффициентов в исходной задаче имеет размерность m * n (m строк, n столбцов); в двойственной задаче рассматривается транспонированная матрица размерностью n * m (n строк, m столбцов).

3. Система ограничений двойственной задачи записывается в виде неравенств, противоположного смысла неравенствам системы ограничений прямой задачи.

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

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

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

7. Если переменная прямой задачи x_j ≥ 0, то j -е условие системы ограничений двойственной задачи является неравенством, если x_j – любое число, неограниченное по знаку, то j -е условие системы ограничений двойственной задачи представляет собой уравнение.

8. Если i -е условие системы ограничений прямой задачи является неравенством, то соответствующая оценка i -го ресурса – переменная y_i ≥ 0, если i -е условие представляет собой уравнение, то переменная двойственной задачи y_i – любое число, неограниченное по знаку.

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

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

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

Существует определенная связь между решением исходной и двойственной задачи (для симметричных двойственных задач), определяемая несколькими теоремами.

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

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

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

Переменные прямой задачи (заголовок симплекс-таблицы)	x ₁, x ₂,..., x_n основные	S ₁, S ₂,..., S_m дополнительные
Переменные двойственной задачи (их значения расположены в индексной строке оптимальной симплекс-таблицы)	↕ ↕ ↕ V ₁, V ₂,..., V_n дополнительные	↕ ↕ ↕ y ₁, y ₂,..., y_m основные

Первая теорема двойственности определяет условия существования решения в каждой из пар взаимодвойственных задач. В каждой из задач имеет место один из взаимоисключающих случаев:

а) исходная и двойственная задачи имеют оптимальное решение; при этом значения целевых функций на оптимальных решениях совпадают: ;

б) в исходной задаче допустимое множество не пусто, а целевая функция не ограничена сверху, в двойственной задаче – пустое допустимое множество;

в) в двойственной задаче допустимое множество не пусто, а целевая функция не ограничена снизу, в исходной задаче – пустое допустимое множество;

г) обе из рассматриваемых задач имеют пустые допустимые множества.

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

Пусть – допустимое решение исходной (прямой) задачи, а – допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответствующих задач, необходимо выполнение следующих условий:

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

Если y_i >0, то если y_i = 0, то

Если x_j >0, то , если , то x_j = 0.

Из первой теоремы двойственности можно определить соотношения, позволяющие найти оптимальное решение двойственной задачи по известному оптимальному решению прямой задачи

Если X* =[ x₁*; x₂*;..., x_n* ] – оптимальный план прямой задачи (вектор-столбец, размерностью n *1), а – Y* =[ y₁*, y₂*,..., y_m ] – система оптимальных оценок ресурсов (вектор-строка размерностью 1* m), то

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

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

Тогда в матричной форме можно записать систему ограничений исходной задачи в виде:

Умножим обе части выражения на матрицу, обратную к (A*), и после преобразований получим выражение для оптимального решения исходной задачи:

, где D – матрица, обратная к матрице A*.

Подставим оптимальный план в выражение для целевой функции:

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

;

причем в вектор-строку С* включены коэффициенты, относящиеся к базисным переменным оптимального плана.

Приведенные соотношения показывают, каким образом можно получить оптимальный план двойственной задачи, если найден оптимальный план прямой задачи. Отметим, что матрица расположена в первых m строках оптимальной симплекс-таблицы в j -ых столбцах, начиная с j = n +1 до j = n + m. Тогда нет необходимости определять оптимальный план двойственной задачи умножением C* на D, поскольку компоненты этого плана совпадают с соответствующими элементами индексной строки для тех же столбцов.