Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel2}} ==!! A lineáris programozás alapfeladata, kétváltozós feladat grafikus megoldása…”

2012-10-22T09:44:21Z

Ú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…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel2}}

<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.==

__TOC__

===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*:
# Van-e Ax≤b-nek megoldása?
# A megoldások halmazán cx korlátos-e?
# 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ó===

<ol>
<li>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>

<li>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.
<li>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.
<li>Á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).
<li>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.
</ol>

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

-- [[PallosPeter|Peti]] - 2006.12.30.

[[Category:Infoszak]]

Rendszeroptimalizálás, 2. tétel - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel2}} ol { margin-top: 0px; } ==!! A lineáris programozás alapfeladata, kétváltozós feladat grafikus megoldása…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel2}} ==!! A lineáris programozás alapfeladata, kétváltozós feladat grafikus megoldása…”