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\leq b,$ $x\geq 0$

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

${\frac {c^{T}x+\alpha }{d^{T}x+\beta }}\rightarrow \mathrm {max}$

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\leq 0,$ $y\geq 0,$ $t>0$

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

$c^{T}y+\alpha t\rightarrow \mathrm {max}$

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}\leq 4,$ $x\geq 0,$

$x_{1}-x_{2}\leq 2$

${\frac {2x_{1}+x_{2}-2}{x_{1}+x_{2}+1}}\rightarrow \mathrm {max}$

átalakítva

$y_{1}+y_{2}-4t\leq 0,$ $y\geq 0,$ $t>0$

$y_{1}-y_{2}-2t\leq 0,$

$y_{1}+y_{2}+t=1$

$2y_{1}+y_{2}-2\rightarrow \mathrm {max}$

Források

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