2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 MIP, MILP
Сообщение18.02.2014, 03:26 


29/11/10
107
Помогите пожалуйста, разобраться. Сроки горят, а я так и не понял сути метода. Речь идет о методе решения задач в смешанном целочисленном программировании.
Итак, имеем смешанную задачу вида
$z = c_{1}x + c_{2}y \mapsto \min$
при условиях
$A_{1}x + A_{2} y \geqslant b$
$x,y \geqslant 0, y \equiv 0 (\mod 1)$
Для заданного значения y задача (1) примет следующий вид
$c_{1}x \mapsto \min$
При условиях
$A_{1}x \geqslant b - A_{2}y$
$x \geqslant 0$
Выпишем двойственную задачу к (2)
$u (b - A_{2}y)$
$uA_{1} \leqslant c_{1}, u \geqslant 0$
На этом этапе при разборе примера из учебника http://publ.lib.ru/ARCHIVES/H/HU_T/_Hu_T..html у меня возник ступор и я не знаю как из него выйти. А надо. Пример следующий:

$5x + 2 y_{1} + 2y_{2} \mapsto \min$
$x + 3y_{1} + 5 y_{2} \geqslant 5$
$4x - y_{1} + y_{2} \geqslant 7$
$2x + y_{1} - y_{2} \geqslant 4$
$x, y_{1}, y_{2} \geqslant 0, y_{1} \equiv y_{2} (\mod 1)$
Следуя по описанной выше схеме получаем
$5x \mapsto \min$
$ \begin{bmatrix} 1 \\ 4 \\ 2 \end{bmatrix} x\geqslant \begin{bmatrix} 5 & -3y_{1} & -2y_{2} \\ 7 & 1y_{1} & -1y_{2} \\ 4 & -1y_{1} & 1y_{2} \end{bmatrix}$

Двойственная к ней задача имеет вид
$(u_{1}, u_{2}, u_{3}) \begin{bmatrix} 5 & -3y_{1} & -2y_{2} \\ 7 & 1y_{1} & -1y_{2} \\ 4 & -1y_{1} & 1y_{2} \end{bmatrix} \mapsto \max$
$u_{1} + 4 u_{2} + 2_{5} \leqslant 5$
$u_{1}, u_{2}, u_{3} \geqslant 0$

По каким правилам $(u_{1}, u_{2}, u_{3}) \begin{bmatrix} 5 & -3y_{1} & -2y_{2} \\ 7 & 1y_{1} & -1y_{2} \\ 4 & -1y_{1} & 1y_{2} \end{bmatrix} $ приводится к классическому виду? Т.е. условия, при которых требуется максимизировать функцию ясны, как они получены тоже ясно, неясно главное -- что максимизировать? как?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group