Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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




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

Модель прямой задачи: Модель ее двойственной задачи:

L=C1x1+C2x2+C3x3® max; =b1U1+b2U2+b3U3+b4U4® min;

U1: A11x1+A12x2+A13x3£ b1; A11U1+A21U2+A31U3+A41U4³ C1;

U2: A21x1+A22x2+A23x3£ b2; A12U1+A22U2+A32U3+A42U4³ C2;

U3: A31x1+A32x2+A33x3£ b3; A13U1+A23U2+A33U3+A43U4³ C3;

U4: A41x1+A42x2+A43x3£ b4; "Ui ³ 0.

"xj ³0.

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

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

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

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

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

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

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

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

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

Пример возникновения симметричной пары двойств. задач - игра 2 лиц с 0 ∑.







Дата добавления: 2015-04-19; просмотров: 155. Нарушение авторских прав


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2019 год . (0.001 сек.) русская версия | украинская версия