Rendszeroptimalizálás, 2. tétel

A VIK Wikiből
A lap korábbi változatát látod, amilyen Unknown user (vitalap) 2012. október 22., 11:44-kor történt szerkesztése után volt. (Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel2}} <style> ol { margin-top: 0px; } </style> ==!! A lineáris programozás alapfeladata, kétváltozós feladat grafikus megoldása…”)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)

Ez az oldal a korábbi SCH wikiről lett áthozva.

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: Értelmezés sikertelen (ismeretlen „\begin{array}” függvény): {\displaystyle \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) }
  2. Ha A első oszlopa csak nemnegatív számokat tartalmaz (azaz A- 0 soros), az egyenlőtlenségrendszer pontosan akkor megoldható, ha A0x' ≤ b0 megoldható. x1-et elegendően kicsinek kell választani.
  3. Ha A első oszlopa csak nempozitív számokat tartalmaz, elegendően nagy x1 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 (ai+aj)x' ≤ bi+bj, A0x' ≤ b0 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.