Szimplex módszer megoldására lineáris programozási feladatok
Nehéz lenne túlbecsülni a jelentőségét lineáris programozási feladatok a mai gazdaság és az ipar. Azonban a grafikus módszerrel, bár van az egyszerű, nem lehet használni az alkalmazásokat, mert a maga korlátai. Ezért a szimplex módszer vált népszerűvé. amely lehetővé teszi, hogy megoldja a problémákat, a komplexitás és a méret.
Köszönet olvasásra, és megossza másokkal
Az eredete a szimplex módszer és a lényeg
Szimplex módszer megoldására lineáris programozási feladatok által kifejlesztett amerikai matematikus George Dantzig. Szintén egy nagy hozzájárulása a fejlesztési tette a tudósok Kuhn és Tucker, jobban ismert a fejlesztések terén a nem-lineáris programozás.
A lényege a szimplex módszer a következő: a maximális (vagy minimalizálására) egy kritérium egymásra helyezett lineáris megkötöttség. Ez a kritérium lehet egy bruttó jövedelem értékesítéséből származó termékek, a működési költségek a termékek és így tovább.
Ugyanakkor változók, amelyek befolyásolják az érték a kritérium, egymásra lineáris megkötöttség formájában egyenletek vagy egyenlőtlenségek. Lényegében a szimplex módszer - a fejlett grafikus metodresheniya LP problémák többdimenziós térben.
Csakúgy, mint egy grafikus módszer keresi az optimális a sokszög csúcsai a szimplex módszer, az optimális kérik a csúcsai n-dimenziós poliéder, úgynevezett simplex (lásd sematikus ábra simplex ;. vörös azt az utat a referenciapont az optimális pontot).
Algoritmus szimplex módszer
Eljárás a következőképpen foglalható össze:
- restrikciós rendszer transzformációval vezet, hogy szükség, úgynevezett bázis, formában;
- az úgynevezett összehasonlító oldat szolgáló „kiindulási pont”;
- végigmegy a csúcsot. Ha ezen a ponton nagyobb, mint a kritérium értéke (vagy kisebb), mint az előző, akkor a folyamat folytatódik. Ha azt a kritériumot értéket nem lehet javítani, akkor megoldást nem találnak.
Azaz, a jelentése a szimplex módszer a következő: minden lineáris egyenlőtlenségek, amelyek a többdimenziós térben megfelelnek a félsíkra, korlátozhatják simplex. Ebben az esetben, a leíró egyenletet optimalizált kritérium megegyezik a hipersík. Most már csak meg kell találni a tetején a simplex, mind tartozó hipersíkot, amelynek koordinátáit maximalizálja (minimalizálni) a kritériumot. Ezért a kiválasztott alap és a hegyével haladunk egyik csúcsa a másikra, amíg meg nem találjuk az optimális pontot.
Egy gyakorlati példa alkalmazásának egy szimplex módszer
Szimplex módszer megoldja a problémát. Maximalizálása funkció $$ L = X + Z \ rightarrow \ max $$ alatti megszorítások $$ \ bal \<\begin Y-X+Z=1,\\ X-2Z+T=2. \end \right. $$ У нас есть четыре переменные – $X, Y, Z, T$ – причем критерий зависит лишь от двух переменных. Примем $Т$ и $Y$ за базисные переменные и выразим их через остальные две свободные переменные. Получим:
Amikor X $ $, és $ Z $ nullával egyenlő, az alapvető változók $ Y = 1, T = 2 $. Criterion értéke $ L = 0 $. Tehát a lényeg $ (1,0,0,2) $ egy alap. Kezdjük válogatás a csúcsot. Nagyítás kritérium növelhető $ Z $ egységet. Ezután a $ Z = 1, X = 0 $ alapváltozó értékeket vehetnek $ Y = 0, T = 4 $. Az új lehetséges megoldás - egy pont $ (0,0,1,4) $ kritérium $ L = 1 $.
Most kifejezetten a $ Z $ és $ T $ a $ Y $ és $ X $:
Nagyítás $ L $ csak úgy növelhető $ X $. Azonban $ X $ növelhető a végtelenségig, az eredeti egyenletrendszert. Következésképpen a kritérium $ L $ lesz végtelenül nagy értéket, a probléma megoldásának a szimplex módszer nem létezik. Ebben az esetben azt mondjuk, hogy az eset egy végtelen simplex.
Egyéb példák megoldása lineáris programozási feladatok megtalálhatók a következő részben: lineáris programozási feladatok megoldásokkal (tíz példát!).
Köszönet olvasásra, és megossza másokkal