 |
|
Модераторы: Poseidon |
 
|
|
[ЛП] Двойственная задача, помогите разобраться 
| Bangladesh |
|
|||
 AsBest  Профиль Группа: Завсегдатай Сообщений: 1089 Регистрация: 4.9.2004 Где: Калининград Репутация: нет Всего: 17 |
завтра зачет по линейному программированию. голова вообще не варит
 , поэтому прошу помощи. в сети нашел массу алгоритмов по составлению двойственной задачи, но никак не могу вкатить в них. там объясняется все в общем виде, а я вообще не настроен абстрактно мыслить сейчас. мог бы кто-нибудь объяснить мне алгоритм на пальцах на примере простой задачи ЛП? Например, такой: Алгоритм 1. Если целевая функция f исходной задачи максимизируется, то целевая функция двойственной минимизируется и наоборот. 2. Кол-во ограничений m исходной задачи равно кол-ву переменных двойственной задачи и наоборот. 3. Каждой переменной Xi ставится в двойственной задаче <= если Z -> max и >= если Z -> min. 4. Каждой переменной Xj не ограниченной по знаку соответствует ограничение вида /какого вида не написано почему-то/. 5. Свободные члены ограничений Bi в двойственной задаче являются коэффициентами перед переменными Yi в целевой функции, а коэффициенты Cj при переменных ij в целево функции исходной задачи являются свободными членами ограничений в двойственной задаче. 6. Матрица A коэффициентов в двойственной задаче транспонируется. помощь очень необходима. -------------------- ок |
|||
|
||||
Загрузка ...
| MagicPRO |
|
|||
 Бывалый Профиль Группа: Участник Сообщений: 200 Регистрация: 4.10.2006 Где: Kremencity Репутация: нет Всего: нет |
ну лично я такое задание решал графическим методом и симплекс методом. если надо скажи каким метод я решу. Решение днем напишу
--------------------
smile=iwashere |
|||
|
||||
| Bangladesh |
|
|||
|
AsBest Профиль Группа: Завсегдатай Сообщений: 1089 Регистрация: 4.9.2004 Где: Калининград Репутация: нет Всего: 17 |
MagicPRO, не решение нужно. решение известно. надо найти двойственную задачу к той, что я привел.
-------------------- ок |
|||
|
||||
| MagicPRO |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 200 Регистрация: 4.10.2006 Где: Kremencity Репутация: нет Всего: нет |
А звеняй, не в курсе....
--------------------
smile=iwashere |
|||
|
||||
| Aloha |
|
||||||||||
|
. Профиль Группа: Участник Клуба Сообщений: 351 Регистрация: 14.5.2006 Репутация: 97 Всего: 165 |
Действуем по алгоритму:
в нашем случае в исходной задаче целевая функция f минимизируется, следовательно, в двойственной задаче целевая функция g максимизируется: g → max
Количество ограничений исходной задачи равно 2: 7 x¹ + 2 x² > 14 4 x¹ + 5 x² > 20 (здесь ¹ и ² не степени, а индексы) следовательно, число переменных целевой функции g двойственной задачи равно 2: g = a y¹ + b y²
Т.к. в двойственной задаче (как мы уже выяснили) g → max, то ограничения в двойственной задаче будут вида: что-то < чего-то.
Свободные члены ограничений исходной задачи: 7 x¹ + 2 x² > 14 4 x¹ + 5 x² > 20 являются коэффициентами целевой функции двойственной задачи: g = 14 x¹ + 20 x² Т.к. целевая функция f исходной задачи имеет вид: f = 3 x¹ + 2 x² то коэффициенты 3 и 2 будут свободными членами ограничений в двойственной задаче: a¹ x¹ + b¹ x² < 3 a² x¹ + b² x² < 2
В исходной задаче ограничения имеют вид: 7 x¹ + 2 x² > 14 4 x¹ + 5 x² > 20 Следовательно, матрица A коэффициентов исходной задачи такая: || 7 2 || || 4 5 || Чтобы получить ограничения в двойственной задаче эту матрицу надо транспонировать: || 7 4 || || 2 5 || Окончательно для двойственной задачи получим: g = 14 y¹ + 20 y² → max 7 y¹ + 4 y² < 3 2 y¹ + 5 y² < 2 y¹ > 0 y² > 0 Это сообщение отредактировал(а) Aloha - 11.1.2007, 19:52 |
||||||||||
|
|||||||||||
| Bangladesh |
|
|||
|
AsBest Профиль Группа: Завсегдатай Сообщений: 1089 Регистрация: 4.9.2004 Где: Калининград Репутация: нет Всего: 17 |
Aloha, =) плюс уже поставил. вопрос решен.
-------------------- ок |
|||
|
||||
|
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.1038 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |