Kvadratikus programozás

A Wikipédiából, a szabad enciklopédiából

A kvadratikus programozás 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; ehhez előbb vissza kell őket vezetni lineáris programozási feladatokra.

A kvadratikus programozás alapfeladata:

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[szerkesztés]

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

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[szerkesztés]

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

1. Megadunk egy lehetséges megoldást szimplex módszerrel

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

3. Elkészíjük ezt a lineáris programot:

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 és , vagy és .

6. Álljunk meg, ha a célfüggvény értéke nulla. Ekkor x a kvadratikus alapfeladatnak is optimuma lesz.

Források[szerkesztés]