2014 dxdy logo

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

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




 
 MIP, MILP
Сообщение18.02.2014, 03:26 
Помогите пожалуйста, разобраться. Сроки горят, а я так и не понял сути метода. Речь идет о методе решения задач в смешанном целочисленном программировании.
Итак, имеем смешанную задачу вида
$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