Rendszeroptimalizálás, 2. tétel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

<style> ol { margin-top: 0px; } </style>

!! A lineáris programozás alapfeladata, kétváltozós feladat grafikus megoldása. Lineáris egyenlőtlenségrendszer megoldása Fourier-Motzkin eliminációval.

LP alapfeladata

• LP alapfeladata*: adott A valós mátrix, b valós oszlopvektor, c valós sorvektor. Keressük a Ax≤b lineáris egyenlőtlenségrendszer azon x megoldását, amire cx maximális. Röviden: max{cx:Ax≤b}
• Ha az egyik egyenlőtlenség ≥-vel szerepel, vesszük a -1-szeresét.
• Ha egyenlet is szerepel a feladatban, helyettesítjük egy ≤ és egy ≥ egyenlőtlenséggel.
• Nyílt egyenlőtlenségekkel (< vagy >) nem foglalkozunk.
• Ha minimumot kell keresni, cx minimuma helyett a (-c)x célfüggvénynek keressük a maximumát.

• Kérdések*:

1. Van-e Ax≤b-nek megoldása?
2. A megoldások halmazán cx korlátos-e?
3. Melyik x-re maximális cx?

Kétváltozós feladat grafikus megoldása

• Egy kétváltozós egyenlőtlenség egy zárt félsíkot határoz meg.
• Ha a félsíkok metszete véges, akkor egy konvex sokszög.
• A sokszög csúcsait c irányvektor szerint sorbarendezzük, a megoldás az utolsó csúcs lesz.

Fourier-Motzkin elimináció

1. Az egyenlőtlenségrendszeren ekvivalens átalakítást végzünk, ha a sorait beszorozzuk egy pozitív konstanssal úgy, hogy az első oszlop összes eleme 0, 1 vagy -1 legyen. Írjuk fel az egyenlőtlenségrendszert Ax≤b alakban a következő csoportosításban: [math] \left( \begin{array}{c|@{\hspace{2em}}c@{\hspace{2em}}} 1 & \\ \vdots & A_+ \\ 1 \\ \hline -1 & \\ \vdots & A_- \\ -1 \\ \hline 0 & \\ \vdots & A_0 \\ 0 & \end{array} \right) \cdot \left( \begin{array}{c} x_1 \\ \hline x' \end{array} \right) \le \left( \begin{array}{c} b_+ \\ \hline b_- \\ \hline b_0 \end{array} \right) [/math]
2. Ha A első oszlopa csak nemnegatív számokat tartalmaz (azaz A_- 0 soros), az egyenlőtlenségrendszer pontosan akkor megoldható, ha A₀x' ≤ b₀ megoldható. x₁-et elegendően kicsinek kell választani.
3. Ha A első oszlopa csak nempozitív számokat tartalmaz, elegendően nagy x₁ választása mellett ugyanez a megoldhatóság feltétele.
4. Általános esetben pontosan akkor van megoldás, ha A₊ és A_- összes <i,j> sorpárját összeadva az (a_i+a_j)x' ≤ b_i+b_j, A₀x' ≤ b₀ egyenlőtlenségrendszer megoldható. Tehát gyakorlatilag összeadjuk páronként a -1 -es és a +1 -es sorokat, ezáltal az első oszlop mindig kiesik, így egyre kisebb lesz a mátrix(horizontálisan, vertikálisan nagyra is nőhet közben).
5. Mikor csak triviális eset marad, akkor ha nem kapunk ellentmondást egyik sorra sem, akkor megoldható, egyébként nem. Triviális eset, amikor nem marad x valamelyik sorban.

• Megjegyzés*: az algoritmus exponenciális futásidejű.

-- Peti - 2006.12.30.