Запись двойственной задачи в симметричном случае
Пример. Пусть некоторая фирма способна выпускать 3 вида продукции, используя 4 вида ресурсов. Известны произведенная стоимость единицы продукции Cj, норма расхода каждого вида ресурса на единицу продукции Aij, количество ресурсов bi. Модель прямой задачи: Модель ее двойственной задачи: L=C 1 x 1 +C 2 x 2 +C 3 x 3 ® max; U 1: A 11 x 1 +A 12 x 2 +A 13 x 3 £ b 1; A 11 U 1 +A 21 U 2 +A 31 U 3 +A4 1 U4³ C 1; U 2: A 21 x 1 +A 22 x 2 +A 23 x 3 £ b 2; A 12 U 1 +A 22 U 2 +A 32 U 3 +A4 2 U4³ C 2; U 3: A 31 x 1 +A 32 x 2 +A 33 x 3 £ b 3; A 13 U 1 +A 23 U 2 +A 33 U 3 +A4 3 U4³ C 3; U4: A4 1 x 1 +A4 2 x 2 +A4 3 x 3 £ b4; "Ui ³ 0. "xj ³0.
Правила, по которым составлена эта модель, включают 5 пунктов: 1. Если в прямой задаче целевая функция максимизируется, то в двойственной минимизируется, и наоборот. 2. Коэффициенты критерия двойственной задачи образуются из компонентов вектора ограничений прямой задачи. 3. Компоненты вектора ограничений двойственной задачи образуются из коэффициентов линейной формы (критерия) прямой задачи. 4. Матрица условий двойственной задачи образуется транспонированием матрицы условий прямой задачи. 5. Знаки неравенств двойственной задачи обратны знакам неравенств прямой. Для однозначной записи двойственной модели в прямой задаче на максимум все неравенства следует привести к виду “<=”, а в задаче на минимум – к виду “>=”. Первые 4 правила действуют как в симметричном, так и в общем случае, а пятое правило – только в случае симметрии. Число условий двойственной задачи = числу переменных прямой задачи, а число переменных двойственной задачи = числу условий прямой. Если для двойственной задачи построить двойственную, то получим прямую. Пример возникновения симметричной пары двойств. задач - игра 2 лиц с 0 ∑.
|
=b 1 U 1 +b 2 U 2 +b 3 U 3 +b4U4® min;
