Hiperbolikus programozás

A hiperbolikus programozás a nemlineáris programozás része, mivel a hiperbolikus programozási feladatok célfüggvényei nem lineárisak, hanem törtlineárisak. Ezek a feladatok közvetlenül nem oldhatók meg a szimplex módszerrel, mivel az optimum nem biztos, hogy csúcspont; ehhez előbb vissza kell őket vezetni lineáris programozási feladatokra.

A hiperbolikus programozás alapfeladata:

$Ax\le b,$ $x\ge 0$

$d^{T}x+\beta >0$

$\frac{c^{T}x+\alpha }{d^{T}x+\beta }\to \mathrm{m}\mathrm{a}\mathrm{x}$

Visszavezetés a lineáris programozásra

A törtlineáris programozás alapfeladata lineáris programra vezethető vissza az $x=y/t$ helyettesítéssel, ahol feltesszük, hogy t szigorúan pozitív. Ha t-t úgy rögzítjük, hogy $d^{T}y+\beta t=1$ legyen, akkor az alapfeladat ekvivalens a

$Ay-bt\le 0,$ $y\ge 0,$ $t>0$

$d^{T}y+\beta t=1$

$c^{T}y+\alpha t\to \mathrm{m}\mathrm{a}\mathrm{x}$

lineáris programmal.

Az eredeti programban x az $x=y/t$ összefüggéssel számítható. Az átalakított feladat mindig megoldható, és az optimális megoldásából számított x és y az eredeti feladatnak is optimuma lesz.

Példa

$x_1+x_2\le 4,$ $x\ge 0,$

$x_1-x_2\le 2$

$\frac{2x_1+x_2-2}{x_1+x_2+1}\to \mathrm{m}\mathrm{a}\mathrm{x}$

átalakítva

$y_1+y_2-4t\le 0,$ $y\ge 0,$ $t>0$

$y_1-y_2-2t\le 0,$

$y_1+y_2+t=1$

$2y_1+y_2-2\to \mathrm{m}\mathrm{a}\mathrm{x}$

Források

• Alkalmazott operációkutatás
• Kalmár János: Operációkutatás