Запись двойственной задачи в симметричном случае

Рассмотрим пример. Пусть некоторая фирма способна выпускать 3 вида продукции, используя 4 вида ресурсов.

Известны произведенная стоимость единицы продукции Cj, норма расхода каждого вида ресурса на единицу продукции Aij и количество ресурсов bi.

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

L=C1x1+C2x2+C3x3 ® max;

U1: A11x1+A12x2+A13x3£ b1;

U2: A21x1+A22x2+A23x3£ b2;

U3: A31x1+A32x2+A33x3£ b3;

U4: A41x1+A42x2+A43x3£ b4;

"xj ³0.

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

=b1U1+b2U2+b3U3+b4U4® min;

A11U1+A21U2+A31U3+A41U4³ C1;

A12U1+A22U2+A32U3+A42U4³ C2;

A13U1+A23U2+A33U3+A43U4³ C3;

"Ui ³ 0.

Здесь – критерий двойственной задачи, Ui – переменные двойственной задачи или, просто, двойственные переменные.

Правила, по которым составлена эта модель, включают 5 пунктов:

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

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

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

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

5. Знаки неравенств двойственной задачи обратны знакам неравенств прямой.

Для однозначной записи двойственной модели в прямой задаче на максимум все неравенства следует привести к виду “меньше или равно”, а в задаче на минимум – к виду “больше или равно”.

Первые 4 правила действуют как в симметричном, так и в общем случае, а пятое правило – только в случае симметрии.

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

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

Дата добавления: 2014-01-11