Kvadratikus programozás

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

A kvadratikus programozás alapfeladata:

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

$p^{T}x+x^{T}Cx\to \mathrm{m}\mathrm{i}\mathrm{n},$

ahol a C mátrix pozitív szemidefinit. Feltehető, hogy szimmetrikus is, mivel a kvadratikus alak megegyezik a szimmetrikus résszel alkotott kvadratikus alakkal.

Visszavezetés a lineáris programozásra

A kvadratikus programozás alapfeladata a következő lineáris programra vezethető vissza:

$Ax+y=b,$ $x,y,v,u\ge 0$

$-Cx+v-A^{T}u=p$

$x^{T}v+y^{T}u=0$

Ha a kvadratikus alapfeladat megoldható, akkor ez a lineáris program is megoldható, és a belőle kapott x a kvadratikus alapfeladatnak is megoldása lesz.

A feladat megoldása

A lineáris programozási feladat nem tudja garantálni az optimumot, ezért azt bonyolultabb megkapni.

1. Megadunk egy lehetséges $x^{\prime }$ megoldást szimplex módszerrel.

2. Elkészítjük az F mátrixot, aminek oszlopai

$f_j=\mathrm{s}\mathrm{g}\mathrm{n}(C(e_j^T{x}^{\prime }+p))e_j$

3. Elkészítjük a következő lineáris programot:

$Ax+y=b,$

$x,y,v,u,z\ge 0$

$-Cx+v-A^{T}u+Fz=p$

$t=\sum z_i\to \mathrm{m}\mathrm{i}\mathrm{n}$ $(i=1\dots n)$

4. Keressük ennek egy olyan bázismegoldását, amiben u és v is nullvektor.

5. Innen elindulva megoldjuk ezt a rendszert úgy, hogy a bázisban egy j-re se legyen bent egyszerre $x_j$ és $v_j$, vagy $y_j$ és $u_j$.

6. Álljunk meg, ha a $t=\sum z_i\to \mathrm{m}\mathrm{i}\mathrm{n}$ célfüggvény értéke nulla. Ekkor x a kvadratikus alapfeladatnak is optimuma lesz.

Források

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