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

Прямая задача: 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 – переменные двойственной задачи или, просто, двойственные переменные.

Правила (для общего и симметричного случая):

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

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

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

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

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

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