Példa a direkt és a duális feladatok szimplex módszerrel történő megoldására. Kettős szimplex módszer Egyenletek megoldása szimplex módszerrel

5.1. példa. Oldja meg a következő lineáris programozási feladatot szimplex módszerrel:

Megoldás:

én ismétlés:

x3, x4, x5, x6 x1,x2. Az alapváltozókat a szabad változókkal fejezzük ki:

A célfüggvényt a következő formába hozzuk:

A kapott probléma alapján elkészítjük a kezdeti szimplex táblát:

5.3. táblázat

Kezdeti szimplex tábla

Az alapmegoldás definíciója szerint a szabad változók egyenlőek nullával, az alapváltozók értéke pedig a szabad számok megfelelő értékeivel, azaz:

3. szakasz: az LLP korlátozási rendszere kompatibilitásának ellenőrzése.

Ennél az iterációnál (az 5.3. táblázatban) nem derült ki a kényszerrendszer (1. jellemző) inkonzisztenciájának előjele (azaz nincs olyan negatív szabad számmal rendelkező sor (kivéve a célfüggvénysort), amely ne tartalmazna legalább egy negatív elem (azaz .negatív együttható szabad változó esetén)).

Ennél az iterációnál (az 5.3. táblázatban) nem derült ki a célfüggvény határtalanságának előjele (2. jel) (azaz a célfüggvény sorában nincs negatív elemű oszlop (kivéve a szabad számok oszlopát). amelyben legalább egy pozitív elem lenne) .

Mivel a talált alapmegoldás nem tartalmaz negatív komponenseket, ez elfogadható.

6. szakasz: optimalitás ellenőrzése.

A talált alapmegoldás nem optimális, mivel az optimalitás kritériuma szerint (4-es jel) a célfüggvény sorában ne legyen negatív elem (ennek a sornak a szabad számát nem vesszük figyelembe ennek az előjelnek a figyelembevételekor ). Ezért a szimplex módszer algoritmusa szerint továbblépünk a 8. szakaszba.

Mivel a talált alapmegoldás elfogadható, a feloldó oszlopot a következő séma szerint fogjuk keresni: a célfüggvény sorában meghatározzuk a negatív elemű oszlopokat (kivéve a szabad számok oszlopát). Az 5.3. táblázat szerint két ilyen oszlop van: a " x1" és oszlop " x2". Az ilyen oszlopok közül az kerül kiválasztásra, amelyik a legkisebb elemet tartalmazza a célfüggvény sorában. Meg fogja oldani. " oszlop x2" tartalmazza a legkisebb elemet (-3) a " oszlophoz képest x1

A megengedő karakterlánc meghatározásához megtaláljuk a szabad számok pozitív becsült arányait a permisszív oszlop elemeihez képest, a legkisebb pozitív becsült aránynak megfelelő karakterláncot vesszük megengedettnek.

5.4. táblázat

Kezdeti szimplex tábla

Az 5.4 táblázatban a legkisebb pozitív értékelési arány a " sornak felel meg x5”, ezért ez megoldó lesz.

Az engedélyező oszlop és az engedélyező vonal metszéspontjában található elemet fogadja el engedélyezőnek. Példánkban ez az az elem, amely a " vonal metszéspontjában található x5» és oszlopok « x2».

A feloldó elem egy alap és egy szabad változót mutat, amelyeket fel kell cserélni a szimplex táblában ahhoz, hogy az új „javított” alapmegoldáshoz jussunk. Ebben az esetben ezek változók. x5És x2, az új szimplex táblában (5.5. táblázat) felcseréljük őket.

9.1. Elemátalakítás engedélyezése.

Az 5.4 táblázat megengedő eleme a következőképpen alakul:

A kapott eredményt egy hasonló cellába írjuk be az 5.5. táblázatba.

9.2. Karakterlánc-konverzió engedélyezése.

Az 5.4 tábla permisszív sorának elemeit felosztjuk ennek a szimplex táblának a permisszív elemével, az eredmények az új szimplex tábla (5.5 táblázat) hasonló celláiba illeszkednek. Az engedélyező karakterlánc elemeinek transzformációit az 5.5. táblázat tartalmazza.

9.3. Megengedő oszloptranszformáció.

Az 5.4 táblázat feloldó oszlopának elemeit elosztjuk ennek a szimplex táblának a feloldó elemével, és az eredményt ellentétes előjellel vesszük. A kapott eredmények az új szimplex táblázat hasonló celláiba illeszkednek (5.5. táblázat). A feloldó oszlop elemeinek átalakításait az 5.5. táblázat tartalmazza.

9.4. A szimplex tábla többi elemének átalakítása.

A szimplex tábla egyéb elemeinek (azaz a feloldó sorban és a feloldó oszlopban nem található elemek) átalakítása a "téglalap" szabály szerint történik.

Vegyük például egy olyan elem transzformációját, amely a karakterlánc metszéspontjában található x3" és a "" oszlopok feltételesen jelölje " x3". Az 5.4 táblázatban gondolatban rajzolunk egy téglalapot, amelynek egyik csúcsa abban a cellában található, amelynek értéke átalakul (azaz a cellában) x3”), a másik (átlós csúcs) pedig egy feloldóelemmel rendelkező cellában van. A másik két csúcs (a második átlóé) egyedileg meghatározott. Ezután a cella transzformált értéke" x3"egyenlő lesz ennek a cellának az előző értékével mínusz egy tört, amelynek nevezője a feloldó elem (5.4. táblázatból), a számlálóban pedig két másik nem használt csúcs szorzata, azaz:

« x3»: .

A többi cella értékeit hasonlóan konvertálják:

« x3 x1»: ;

« x4»: ;

« x 4 x 1»: ;

« x6»: ;

« x 6 x 1»: ;

«»: ;

« x1»: .

Ezen átalakítások eredményeként egy új szimplex táblát kaptunk (5.5 táblázat).

II ismétlés:

1. lépés: szimplex táblázat összeállítása.

5.5. táblázat

Simplex táblázatII iterációk

2. szakasz: az alapoldat meghatározása.

A szimplex transzformációk eredményeként egy új alapmegoldást kaptunk (5.5. táblázat):

Mint látható, ennél az alapmegoldásnál a célfüggvény értéke =15, ami több, mint az előző alapmegoldásnál.

Az 5.5. táblázat 1. jele szerinti korlátozási rendszer következetlenségét nem azonosították.

4. szakasz: a célfüggvény korlátosságának ellenőrzése.

A célfüggvény határtalansága az 5.5. táblázat 2. jele szerint nem derült ki.

5. szakasz: a megtalált alapmegoldás elfogadhatóságának ellenőrzése.

A 4. jellemzőnek megfelelő talált alapmegoldás nem optimális, mivel a szimplex tábla célfüggvényének sora (5.5. táblázat) negatív elemet tartalmaz: -2 (ennek figyelembevételekor ennek a sornak a szabad számát nem vesszük figyelembe funkció). Tehát folytassuk a 8. lépéssel.

8. szakasz: az engedélyező elem meghatározása.

8.1. A felbontás oszlop definíciója.

A talált alapmegoldás elfogadható, a negatív elemű oszlopokat a célfüggvény sorában határozzuk meg (kivéve a szabad számok oszlopát). Az 5.5. táblázat szerint csak egy ilyen oszlop van: " x1". Ezért megengedett módon elfogadjuk.

8.2. Megengedő karakterlánc-definíció.

Az 5.6. táblázatban szereplő pozitív becsült arányok kapott értékei szerint a minimum a következő sornak megfelelő arány. x3". Ezért megengedett módon elfogadjuk.

5.6. táblázat

Simplex táblázatII iterációk

9. szakasz: a szimplex tábla átalakítása.

A szimplex tábla (5.6. táblázat) transzformációit az előző iterációval megegyező módon hajtjuk végre. A szimplex tábla elemeinek transzformációinak eredményeit az 5.7. táblázat mutatja be.

III ismétlés

Az előző iteráció szimplex transzformációinak eredményei alapján összeállítunk egy új szimplex táblát:

5.7. táblázat

Simplex táblázatIII iterációk

2. szakasz: az alapoldat meghatározása.

A szimplex transzformációk eredményeként egy új alapmegoldást kaptunk (5.7 táblázat):

3. szakasz: a korlátozási rendszer kompatibilitásának ellenőrzése.

Az 5.7. táblázat 1. jele szerinti korlátozási rendszer következetlenségét nem azonosították.

4. szakasz: a célfüggvény korlátosságának ellenőrzése.

A célfüggvény határtalansága az 5.7. táblázat 2. jele szerint nem derült ki.

5. szakasz: a megtalált alapmegoldás elfogadhatóságának ellenőrzése.

A 3. kritériumnak megfelelő talált alapmegoldás elfogadható, mivel nem tartalmaz negatív komponenseket.

6. szakasz: a megtalált alapmegoldás optimálisságának ellenőrzése.

A 4. jellemzőnek megfelelő talált alapmegoldás nem optimális, mivel a szimplex tábla célfüggvényének sora (5.7. táblázat) negatív elemet tartalmaz: -3 (ennek figyelembevételekor ennek a sornak a szabad számát nem vesszük figyelembe funkció). Tehát folytassuk a 8. lépéssel.

8. szakasz: az engedélyező elem meghatározása.

8.1. A felbontás oszlop definíciója.

A talált alapmegoldás elfogadható, a negatív elemű oszlopokat a célfüggvény sorában határozzuk meg (kivéve a szabad számok oszlopát). Az 5.7. táblázat szerint csak egy ilyen oszlop van: " x5". Ezért megengedett módon elfogadjuk.

8.2. Megengedő karakterlánc-definíció.

Az 5.8 táblázatban szereplő pozitív becsült arányok kapott értékei szerint a minimum a " sornak megfelelő arány". x4". Ezért megengedett módon elfogadjuk.

5.8. táblázat

Simplex táblázatIII iterációk

9. szakasz: a szimplex tábla átalakítása.

A szimplex tábla (5.8. táblázat) transzformációit az előző iterációval megegyező módon hajtjuk végre. A szimplex tábla elemeinek transzformációinak eredményeit az 5.9. táblázat mutatja be.

IV ismétlés

1. szakasz: új szimplex asztal építése.

Az előző iteráció szimplex transzformációinak eredményei alapján összeállítunk egy új szimplex táblát:

5.9. táblázat

Simplex táblázatIV iterációk

2. szakasz: az alapoldat meghatározása.

A szimplex transzformációk eredményeként új alapmegoldást kaptunk, az 5.9. táblázat szerint a megoldás a következő:

3. szakasz: a korlátozási rendszer kompatibilitásának ellenőrzése.

A korlátozási rendszer következetlensége az 5.9. táblázat 1. jellemzője szerint nem derült ki.

4. szakasz: a célfüggvény korlátosságának ellenőrzése.

A célfüggvény határtalansága az 5.9. táblázat 2. jele szerint nem derült ki.

5. szakasz: a megtalált alapmegoldás elfogadhatóságának ellenőrzése.

A 3. kritériumnak megfelelő talált alapmegoldás elfogadható, mivel nem tartalmaz negatív komponenseket.

6. szakasz: a megtalált alapmegoldás optimálisságának ellenőrzése.

A 4. jellemzőnek megfelelően talált alapmegoldás optimális, mivel a szimplex tábla célfüggvényének sorában (5.9. táblázat) nincsenek negatív elemek (ennek a sornak a szabad számát nem vesszük figyelembe a jellemző figyelembe vételekor) .

7. szakasz: az alternatív megoldás ellenőrzése.

A talált megoldás az egyetlen, mivel a célfüggvény sorában (5.9. táblázat) nincs nulla elem (ennek a sornak a szabad számát nem vesszük figyelembe, ha figyelembe vesszük ezt a tulajdonságot).

Válasz: a vizsgált probléma célfüggvényének optimális értéke =24, amelyet a következő időpontban érünk el.

Példa 5.2. Oldja meg a fenti lineáris programozási feladatot, feltételezve, hogy a célfüggvény minimalizált:

Megoldás:

én ismétlés:

1. szakasz: a kezdeti szimplex tábla kialakítása.

Az eredeti lineáris programozási feladat szabványos formában van megadva. Vigyük a kanonikus formára úgy, hogy minden egyenlőtlenségi kényszerbe bevezetünk egy további nemnegatív változót, pl.

Az így kapott egyenletrendszerben megengedett (alap)változókat veszünk x3, x4, x5, x6, akkor a szabad változók x1,x2. Az alapváltozókat a szabad változókkal fejezzük ki.

Szolgálati megbízás. A szolgáltatás lineáris programozási problémák (LPP) online megoldására szolgál szimplex módszerrel, az alábbi jelölési formákban:

• szimplex táblázat formájában (Jordan transzformációk módszere); alapnyilvántartási forma;
• módosított szimplex módszer; oszlop formájában; vonalas formában.

Utasítás. Válassza ki a változók számát és a sorok számát (korlátozások számát). A kapott megoldás Word és Excel fájlba kerül mentésre. Ugyanakkor ne vegye figyelembe az x i ≥0 típusú korlátozásokat. Ha néhány x i-re nincs korlátozás a feladatban, akkor az LLP-t KZLP-re kell redukálni, vagy ezt a szolgáltatást kell használni. A megoldás automatikusan meghatározza a felhasználást M-módszer(egyszerű módszer mesterséges alapon) és kétlépcsős szimplex módszer.

Ezzel a számológéppel a következők is használatosak:
Grafikus módszer az LLP megoldására
A közlekedési probléma megoldása
Mátrix játék megoldás
A szolgáltatás online használatával meghatározhatja egy mátrixjáték árát (alsó és felső határ), nyeregpontot kereshet, megoldást találhat egy vegyes stratégiára az alábbi módszerekkel: minimax, szimplex módszer, grafikus (geometriai) módszer, Brown módszere.
Két változó függvényének szélsőértéke
Dinamikus programozási problémák
Osszon el 5 homogén árutételt három piac között úgy, hogy értékesítésükből a lehető legnagyobb bevételt érje el. Az értékesítésből származó bevétel az egyes piacokon G(X) az X árucikk eladott tételeinek számától függ, és a táblázatban látható.

Szimplex módszer algoritmus a következő lépéseket tartalmazza:

1. Az első alapterv elkészítése. Áttérés a lineáris programozási probléma kanonikus formájára nemnegatív további mérlegváltozók bevezetésével.
2. A terv optimálisságának ellenőrzése. Ha legalább egy indexsor együtthatója kisebb, mint nulla, akkor a terv nem optimális, és javítani kell.
3. Vezető oszlopok és sorok meghatározása. Az indexsor negatív együtthatói közül az abszolút értékben a legnagyobb kerül kiválasztásra. Ezután felosztja a szimplex tábla szabad tagjait tartalmazó oszlopának elemeit a vezető oszlop azonos előjelű elemeire.
4. Új alapvonal felépítése. Az új tervre való áttérés a szimplex tábla Jordan-Gauss módszerrel történő újraszámításának eredményeként történik.

Extrémális megoldást a megvalósítható megoldások tartományának határán a sokszög sarokpontjainak egyik csúcsán, vagy két szomszédos sarokpont közötti szakaszon érünk el.

A lineáris programozás alaptétele. Ha az LLP célfüggvény valamikor szélsőséges értéket ér el a megvalósítható megoldások területén, akkor ezt az értéket veszi fel a sarokpontban. Ha az LLP célfüggvény egynél több sarokpontban ér el egy szélső értéket, akkor e pontok bármelyik konvex lineáris kombinációjában ugyanazt az értéket veszi fel.

A szimplex módszer lényege. Az optimális pontra való mozgás az egyik sarokpontról a másikra való mozgással történik, ami közelebb és gyorsabban viszi az X optot. A pontok ilyen felsorolási sémája, szimplex módszernek nevezzük, javasolta R. Danzig.
A sarokpontokat m alapváltozó jellemzi, így az egyik sarokpontból a szomszédosba való átmenet úgy végezhető el, hogy a bázisban csak egy alapváltozót változtatunk a nem bázisról változóra.
A szimplex módszer megvalósítása az LP-problémák különféle jellemzői és megfogalmazásai miatt különféle módosulásokkal rendelkezik.

A szimplex táblák felépítése az optimális megoldás eléréséig folytatódik.

Hogyan lehet szimplex táblát használni annak megállapítására, hogy egy lineáris programozási probléma megoldása optimális-e?
Ha az utolsó sor (objektív függvényértékek) nem tartalmaz negatív elemeket, akkor megkeresi az optimális tervet.

1. megjegyzés. Ha az egyik alapváltozó nulla, akkor az ilyen alapmegoldásnak megfelelő szélső pont degenerált. Degenerációról akkor beszélünk, ha kétértelmű a vezető sor kiválasztása. Lehet, hogy egyáltalán nem veszi észre a probléma elfajulását, ha másik sort választ útmutatásul. Kétértelműség esetén a legalacsonyabb indexű sort kell választani, hogy elkerüljük a hurkolást.

2. megjegyzés. Legyen egy szélső ponton minden szimplex különbség nemnegatív D k ³ 0 (k = 1..n+m), azaz. megkapjuk az optimális megoldást, és létezik olyan А k - nem alapvektor, amelyre D k = 0. Ekkor legalább két ponton elérjük a maximumot, azaz. van alternatív optimum. Ha ezt az x k változót bevisszük a bázisba, a célfüggvény értéke nem fog változni.

3. megjegyzés. A duális probléma megoldása az utolsó szimplex tablóban található. A szimplex különbségek vektorának utolsó m komponense (egyenlegváltozók oszlopaiban) a duális probléma optimális megoldása. A direkt és a duális feladatok célfüggvényeinek értéke az optimális pontokon azonos.

Megjegyzés 4. A minimalizálási feladat megoldása során a legnagyobb pozitív szimplex különbséggel rendelkező vektort vezetjük be a bázisba. Továbbá ugyanazt az algoritmust alkalmazzuk, mint a maximalizálási problémánál.

Ha a "Szükséges, hogy a III. típusú nyersanyagokat teljesen el kell fogyasztani" feltétel be van állítva, akkor a megfelelő feltétel egyenlőség.

Analitikus bevezetés a szimplex módszerbe

Tehát, ha az LLP-t kanonikus formában oldjuk meg, akkor a kényszerrendszer a szokásos lineáris egyenletrendszer. Az LP feladatok megoldása során lineáris egyenletrendszereket kapunk, amelyeknek általában végtelen sok megoldása van.

Például adott egy rendszer

Itt az egyenletek száma 2, az ismeretlenek száma pedig 3, kevesebb egyenlet van. Az x 1 és x 2 kifejezés x 3-mal:

Ez a rendszer általános megoldása. ha az x 3 változó tetszőleges számértéket kap, akkor konkrét megoldásokat fogunk találni a rendszerre. Például, x 3 =1 → x 1 =1 → x 2=6. Van (1, 6, 1) - egy adott megoldás. Hadd x 3 =2 → x 1 =-3, x 2 = 1, (-3, 1, 2) egy másik speciális megoldás. Végtelenül sok ilyen egyedi megoldás létezik.

Változók x 1 és x 2 alapnak nevezzük, és a változó x 3 - nem alap, ingyenes.

Változók halmaza x 1 és x 2 képezi az alapot: B (x 1 , x 2). Ha x 3 = 0, akkor a kapott konkrét megoldást (5, 11, 0) a bázisnak megfelelő alapmegoldásnak nevezzük. B (x 1 , x 2).

Az alapmegoldás a szabad változók nulla értékének megfelelő megoldás.
A többi változót alapváltozónak tekinthetjük: ( x 1 , x 3) vagy ( x 2 , x 3).
Hogyan lépjünk egy alapról B(x 1 , x 2) más alapra B(x 1 , x 3)?
Ehhez szükség van egy változóra x 3 az alapszintűvé alakításhoz, és x 2 - nem alapvető, azaz az egyenletekben szükséges x 3 express via x 2 és helyettesíti az 1-ben:

B(x 1 , x 3), értéke: (-19/5; 0; 11/5).

Ha most az alaptól B(x 1 , x 3) az alapra akarunk menni B(x 2 , x 3), akkor

Az alapnak megfelelő alapmegoldás B (x 2 , x 3): (0;19/4; 7/8).
A három talált alapmegoldás közül az alapnak megfelelő megoldás B (x 1 , x 3) - negatív x 1 < 0, нас в ЗЛП интересуют только неотрицательные решения.

Ha egy LP feladatnak van megoldása, akkor azt a kanonikus alakkényszerrendszer alapvető nemnegatív megoldásainak halmazán érjük el.

Ezért a szimplex módszer ötlete az egyik alapról a másikra történő szekvenciális átmenetből áll, ami a legjobb a célfüggvény értéke szempontjából.

Példa. Oldja meg az LP problémát.

Funkció F= x 2 - x 1 → min minimálisra kell csökkenteni egy adott kényszerrendszerhez:
-2x 1 + x 2 + x 3 = 2
x 1 + x 2 + x 5 = 5
x 1 - 2x 2 + x 4 = 12
x i ≥ 0, én = 1, 5

Ezek a megszorítások az egyenlőtlenségekből és a változókból származnak x 3 , x 5 , x 4 - kiegészítőként.
A korlátozásokat úgy írjuk le, hogy a változók közül bázist választunk B{ x 3 , x 4 , x 5 }:

Ez az alap megfelel az alap nem negatív megoldásnak
x 1 = 0, x 2 = 0, x 3 = 2, x 4 = 2, x 5 = 5 vagy (0, 0, 2, 2, 5).
Most ki kell fejeznünk F nem alapváltozókon keresztül, esetünkben ez már megtörtént: F= x 2 - x 1 .
Ellenőrizze, hogy a funkció elérte-e F minimális értéke. Ehhez az alapmegoldáshoz F= 0 - 0 = 0 - a függvény értéke 0. De csökkenthető, ha x 1 növekedni fog, mivel az at függvény együtthatója x 1 negatív. Emelkedéssel azonban x 1 változó érték x 4 , x 5 csökkenés (lásd a kényszerrendszer második és harmadik egyenlőségét). Változó x 1 nem növelhető 2-nél többre, ellenkező esetben x A 4 negatív lesz (a 2-es egyenlőség miatt), ellenkező esetben legfeljebb 5 lesz x 5 - negatív. Tehát az egyenlőségek elemzéséből az következik, hogy a változó x 1-et 2-re lehet növelni, ekkor a függvény értéke csökken.
Térjünk át egy új B 2 bázisra egy változó bevezetésével x 1 alapra helyette x 4 .
B 2 {x 1 , x 3 , x 5 }.
Fejezzük ki ezeket az alapváltozókat nem alapváltozókkal. Ehhez először kifejezzük x 1 a második egyenletből, és helyettesítse a többivel, beleértve a függvényt.

Az alapnak megfelelő alapmegoldás B 3 {x 1 , x 2 , x 3 ), kiírjuk (4, 1, 9, 0, 0), és a függvény felveszi az értéket F= -3. Vegye figyelembe, hogy az érték F csökkent, azaz javult a korábbi bázishoz képest.
A célfüggvény formáját tekintve , vegye figyelembe, hogy javítani, azaz csökkenteni az értéket F nem lehetséges és csak x 4 = 0, x 5 = 0 érték F= -3. amint x 4 , x 5 pozitívvá, értékké válik F csak növekedni fog, mivel az együtthatók a x 4 , x 5 pozitív. Tehát a funkció F elérte optimumát F* = -3. Tehát a legkisebb érték F, egyenlő -3, akkor érhető el x 1 * = 4, x 2 * = 1, x 3 * = 9, x 4 * = 0, x 5 * = 0.

Ez a példa nagyon jól szemlélteti a módszer gondolatát: fokozatosan haladva bázisról bázisra, miközben mindig figyelünk a célfüggvény azon értékeire, amelyeknek javulniuk kell, eljutunk arra az alapra, amelyben a célfüggvény értéke nem javítható, ez optimális. Vegyük észre, hogy véges számú bázis van, így a kívánt bázis eléréséhez megtett lépések száma véges.

Az LP problémák megoldásának univerzális módszerét szimplex módszernek nevezzük. Ennek a módszernek az alkalmazása és leggyakoribb módosítása - a kétfázisú szimplex módszer.

Az LP feladatok megoldásának grafikus módszerével tulajdonképpen az egyenlőtlenségrendszer megoldási halmazának határához tartozó csúcsok halmazából olyan csúcsot választottunk, amelynél a célfüggvény értéke elérte a maximumot (minimumot). Két változó esetén ez a módszer meglehetősen egyértelmű, és lehetővé teszi, hogy gyorsan megoldást találjon a problémára.

Ha három vagy több változó van a feladatban, és a valós gazdasági problémákban pontosan ez a helyzet, akkor nehéz elképzelni a korlátrendszer megoldási területét. Az ilyen feladatokat a segítségével oldják meg szimplex módszer vagy az egymást követő fejlesztések módszere. A módszer ötlete egyszerű, és a következőkből áll.

Egy bizonyos szabály szerint a kezdeti referenciaterv (a kényszerterület valamely csúcsa) megtalálható. Ellenőrzik, hogy a terv optimális-e. Ha igen, akkor a probléma megoldódott. Ha nem, akkor áttérünk egy másik javított tervre - egy másik csúcsra. a célfüggvény értéke ezen a terven (ezen a csúcson) minden bizonnyal jobb, mint az előzőben. Az átmenet algoritmusa valamilyen számítási lépés segítségével valósul meg, amelyet kényelmesen táblázatokba írunk, ún. szimplex táblázatok . Mivel véges sok csúcs van, véges számú lépésben jutunk el az optimális megoldáshoz.

Tekintsük a szimplex módszert a terv elkészítésének egy konkrét példáján.

Ismét megjegyezzük, hogy a szimplex módszer speciális formára redukált kanonikus LP-feladatok megoldására alkalmazható, azaz rendelkezik bázissal, pozitív jobb oldalakkal és nem alapváltozókkal kifejezett célfüggvénnyel. Ha a probléma nem redukálódik speciális formára, akkor további lépésekre van szükség, amelyeket később tárgyalunk.

Tekintsük a gyártási terv problémáját, miután korábban felépítettünk egy modellt, és speciális formára redukáltuk.

Feladat.

Termékek gyártásához AÉs BAN BEN a raktár legfeljebb 80 darab nyersanyagot tud kiadni. És a termék gyártásához A két egységet fogyasztanak el, és termékeket BAN BEN- egy egységnyi nyersanyag. A termelést úgy kell megtervezni, hogy a termékekből a legnagyobb haszon biztosítható legyen A legfeljebb 50 darabot és terméket kell előállítani BAN BEN- legfeljebb 40 db. Sőt, egy termék eladásából származó nyereség A- 5 rubel, és tól BAN BEN- 3 dörzsölje.

Készítsünk matematikai modellt, jelölve x 1 számú termék A szempontjából x 2 - termékek száma BAN BEN. akkor a kényszerrendszer így fog kinézni:

x 1 ≤50
x2 ≤40
2x1 +x2 ≤80
x 1 ≥0, x 2 ≥0
5x1 +3x2→max

A problémát a kanonikus formába hozzuk további változók bevezetésével:

x 1 + x 3 =50
x2 +x4 =40
2x1 +x2 +x5 =80
x 1 ≥0, x 2 ≥0
5x1 +3x2→max
-F = -5x 1 - 3x 2 → min.

Ennek a problémának speciális formája van (alappal, a jobb oldalak nem negatívak). Simplex módszerrel megoldható.

énszínpad. Feladat írása szimplex táblába. Egy az egyhez megfeleltetés van a (3.10) feladat kényszerrendszere és a szimplex tabló között. Ahány sor van a táblázatban, annyi egyenlőség van a kényszerrendszerben, és annyi oszlop, ahány szabad változó. Az alapváltozók az első oszlopot, a szabad változók a táblázat felső sorát töltik ki. Az alsó sort indexvonalnak nevezzük; ez tartalmazza a célfüggvény változóinak együtthatóit. A jobb alsó sarokba kezdetben 0 kerül, ha nincs szabad tag a függvényben; ha van, akkor ellenkező előjellel írjuk. Ezen a helyen (jobb alsó sarokban) lesz a célfüggvény értéke, aminek a modulo-t kell növelnie, amikor egyik tábláról a másikra lépünk. Tehát a korlátozási rendszerünk megfelel a 3.4 táblázatnak, és továbbléphetünk a megoldás második szakaszába.

3.4. táblázat

IIszínpad. Az alapterv optimálisságának ellenőrzése.

Ez a 3.4. táblázat a következő alapállapotnak felel meg:

(x 1 , x 2 , x 3 , x 4 , x 5) = (0, 0, 50, 40, 80).

Szabad változók x 1 , x 2 értéke 0; x 1 = 0, x 2 = 0. És az alapváltozók x 3 , x 4 , x 5 vegye fel az értékeket x 3 = 50, x 4 = 40, x 5 = 80 - a szabad tagok oszlopából. Az objektív függvény értéke:

-F = - 5x 1 - 3x 2 = -5 0 - 3 0 = 0.

Feladatunk annak ellenőrzése, hogy az adott alapterv optimális-e. ehhez meg kell nézni az indexsort - a célfüggvény sorát F.

Különféle helyzetek lehetségesek.

1. Az indexben F-stringnek nincsenek negatív elemei. Tehát a terv optimális, ki tudjuk írni a probléma megoldását. A célfüggvény elérte optimális értékét, amely megegyezik a jobb alsó sarokban lévő számmal, ellenkező előjellel. Térjünk át a IV. szakaszra.

2. Az index sorban van legalább egy negatív elem, amelynek oszlopában nincs pozitív elem. Ezután arra a következtetésre jutunk, hogy a célfüggvény F→∞ korlátlanul csökken.

3. Az indexsorban van egy negatív elem, amelynek oszlopa legalább egy pozitív elemet tartalmaz. Ezután áttérünk a következő III. újraszámolja a táblázatot, javítva az alapvonalat.

IIIszínpad. Az alapterv javítása.

Az index negatív elemei közül F-sorok közül kiválasztjuk a legnagyobb modulot, a hozzá tartozó oszlopot feloldónak nevezzük és megjelöljük "".

Egy feloldó sor kiválasztásához ki kell számítani a szabad tagok oszlopának elemeinek arányait csak Nak nek pozitív engedély oszlop elemei. Válassza ki a kapott arányok közül a minimumot. A megfelelő elemet, amelynél a minimumot elérjük, feloldó elemnek nevezzük. Egy négyzettel kiemeljük.

Példánkban a 2. elem megengedő. Az ennek az elemnek megfelelő karakterláncot feloldásnak is nevezik (3.5. táblázat).

3.5. táblázat

A feloldó elem kiválasztása után a táblázatot a szabályok szerint újraszámoljuk:

1. Az előzővel megegyező méretű új táblában a feloldó sor és oszlop változók felcserélődnek, ami megfelel az új bázisra való átállásnak. Példánkban: x 1 szerepel az alapban, helyette x 5 , amely elhagyja a bázist, és most ingyenes (3.6. táblázat).

3.6. táblázat

2. A 2 feloldóelem helyére írjuk a reciprok számát ½.

3. Ossza el a megengedő egyenes elemeit a megengedő elemmel!

4. A feloldó oszlop elemeit elosztjuk a feloldó elemmel, és ellentétes előjellel írjuk.

5. A 3.6 táblázat többi elemének kitöltéséhez a téglalapszabály szerint újraszámolunk. Tegyük fel, hogy az elemet 50-ben szeretnénk megszámolni.

Ezt az elemet gondolatban összekapcsoljuk a feloldóval, megkeressük a szorzatot, kivonjuk a kapott téglalap másik átlóján elhelyezkedő elemek szorzatát. A különbséget elosztjuk a feloldó elemmel.

Így, . 10-et írunk oda, ahol 50 volt. Hasonlóan:
, , , .

3.7. táblázat

Új 3.7-es táblánk van, az alapváltozók mostantól változók (x 3 ,x 4 ,x 1 ). A célfüggvény értéke -200 lett, azaz. csökkent. Ennek az alapmegoldásnak az optimálisságának ellenőrzéséhez vissza kell mennünk a II. A folyamat nyilvánvalóan véges, a megállítási kritérium a II. szakasz 1. és 2. pontja.

Végezzük el a probléma megoldását. Ehhez leellenőrizzük az indexsort, és látva benne a -½ negatív elemet, a hozzá tartozó oszlopot feloldónak nevezzük, és a III. szakasz szerint újraszámoljuk a táblázatot. Miután elkészítettük az arányokat, és közülük a minimum = 40-et választottuk, meghatároztuk az 1. feloldóelemet. Most az újraszámítást a 2-5. szabályok szerint hajtjuk végre.

3.8. táblázat

A táblázat újraszámítása után meggyőződünk arról, hogy az index sorban nincsenek negatív elemek, így a probléma megoldva, az alapterv optimális.

IVszínpad. Az optimális megoldás kiírása.

Ha a szimplex módszer a II. szakasz 1. pontja szerint leállt, akkor a feladat megoldását a következőképpen írjuk ki. Az alapváltozók a szabad tagok oszlopának értékeit veszik fel. Példánkban x 3 = 30, x 2 = 40, x 1 = 20. A szabad változók 0, x 5 = 0, x 4 = 0. A célfüggvény a szabad tagok oszlopának utolsó elemének értékét veszi fel ellentétes előjellel: - F = -220 → F= 220, példánkban a függvényt min-re vizsgáltuk, és kezdetben F→ max, tehát a jel valójában kétszer változott. Így, x* = (20, 40, 30, 0, 0), F* = 220. Válasz a feladatra:

A kibocsátási tervben 20 ilyen típusú terméket kell szerepeltetni A, 40 B típusú termék, míg a nyereség maximális lesz, és 220 rubel lesz.

A szakasz végén bemutatjuk a szimplex módszer algoritmusának blokkdiagramját, amely pontosan megismétli a lépéseket, de néhány olvasó számára talán kényelmesebb lesz a használata, mivel a nyilak egyértelmű cselekvési irányt mutatnak.

A folyamatábra dobozai feletti hivatkozások megmutatják, hogy a megfelelő átalakításcsoport melyik lépéshez vagy alelemhez tartozik. a kezdeti alapvonal megállapításának szabálya a 3.7. bekezdésben kerül megfogalmazásra.

Példa. Oldja meg a következő LP feladatot kanonikus formában szimplex módszerrel!
f(x)=x1 +9x2 +5x3 +3x4 +4x5 +14x6 → min
x1 +x4 =20
x2 +x5 =50
x 3 + x 6 =30
x 4 + x 5 + x 6 = 60
x i ≥ 0, i = 1,…,6
Egy LP-problémáról azt mondjuk, hogy kanonikus alakja van, ha minden kényszer (kivéve a változók nem-negativitásának feltételeit) egyenlőségformájú, és minden szabad tag nem negatív. Tehát kanonikus formában van egy problémánk.
A szimplex módszer ötlete a következő. Először is meg kell találni a megengedett megoldások poliéderének (kezdeti) csúcsát (kezdeti elfogadható alapmegoldás). Ezután ellenőriznie kell ezt a megoldást az optimálisság szempontjából. Ha optimális, akkor a megoldás megtalálható; ha nem, akkor menjen a poliéder másik csúcsára, és ismét ellenőrizze az optimálisságot. Tekintettel a poliéder csúcsainak végességére (az LP probléma megszorításainak végességének következménye), véges számú "lépésben" találjuk meg a kívánt minimum vagy maximum pontot. Meg kell jegyezni, hogy az egyik csúcsból a másikba való mozgás során a célfüggvény értéke csökken (minimális feladatban) vagy nő (maximális feladatban).
Így a szimplex módszer ötlete az LP probléma három tulajdonságán alapul.
Megoldás. Egy kezdeti megvalósítható alapmegoldás megtalálásához, pl. az alapváltozók meghatározásához az (5.6) rendszert "átlós" formára kell redukálni. A Gauss-módszert (az ismeretlenek egymást követő kiküszöbölésének módszere) alkalmazva az (5.6)-ból kapjuk:
x 2 + x 1 + x 3 \u003d 40
x4+x1=20
x5 -x1 -x3 =10
x6+x3=30
Ezért a változók alapvetőek x 2 , x 4 , x 5 , x 6 , a megfelelő sorok szabad tagjaival egyenlő értékeket adunk nekik: x 2 = 40, x 4 = 20, x 5 = 10, x 6 = 30,. Változók x 1És x 3 nem alapvetőek: x 1 \u003d 0, x 3 = 0.
Alkossunk egy kezdeti elfogadható alapmegoldást
x 0 = (0,40, 0,20, 10,30) (5,9)
A talált megoldás optimálisságának ellenőrzésére x0 ki kell zárni az alapváltozókat a célfüggvényből (az (5.8) rendszer segítségével), és egy speciális szimplex táblát kell készíteni.
A változók kiiktatása után célszerű a célfüggvényt a következő formában írni:
f(x) = -7x1 - 14x3 +880 (5,10)
Most az (5.8) -(5.10) használatával összeállítjuk a kezdeti szimplex táblát:

A nulla sor a célfüggvény megfelelő változóinak ellentétes előjelű együtthatóit tartalmazza. Optimalitási kritérium (minimális keresési probléma esetén): elfogadható alapmegoldás( x0) akkor optimális, ha a nulla sorban egyetlen szigorúan pozitív szám sincs (nem számítva a célfüggvény (880) értékét). Ez a szabály a következő iterációkra (táblázatokra) is vonatkozik. A nulla sor elemeit oszlopbecsléseknek nevezzük.
Tehát a kezdeti elfogadható alapmegoldás (5.9) nem optimális: 7>0, 14>0 .
A nulla oszlop az alapváltozók értékeit tartalmazza. Szükségszerűen nem negatívnak kell lenniük (lásd az (5.7) egyenletet). Az elsőtől a negyedik sorig az (5.8) rendszerből származó változók együtthatói íródnak.
Mert x0 nem optimális, akkor át kell lépni a megengedhető megoldások poliéderének egy másik csúcsára (új d.b.r. megalkotása). Ehhez meg kell találnia a vezető elemet, és végre kell hajtania egy bizonyos transzformációt (szimplex transzformáció).
Először megkeressük a táblázat vezető elemét, amely a vezető oszlop (a legmagasabb pozitív pontszámú oszlop) és a vezető sor (a nulla oszlop elemeinek minimális arányának megfelelő sor) metszéspontjában található. a vezető oszlop megfelelő elemei (szigorúan pozitívak).
Az 1. táblázatban a vezető oszlop a harmadik oszlop, a vezető sor pedig a negyedik sor. (min(40/1,30/1)=30/1) nyilak jelzik, a vezető elem pedig be van karikázva. A vezető elem azt jelzi, hogy az alapváltozó x6 nem alapra kell cserélni x 3. Ekkor az új alapváltozók lesznek x 2 , x 3 , x 4 , x 5 ,, és nem alapvető - x 1, x 6,. Ez a megengedhető megoldások poliéderének új csúcsára való átmenetet jelenti. Egy új megvalósítható alapmegoldás koordinátaértékeinek megtalálása x00 fel kell építeni egy új szimplex táblát, és elemi átalakításokat kell végrehajtania benne:
A) ossza el a vezető sor összes elemét a vezető elemmel, ezáltal a vezető elemet 1-re fordítja (a számítás megkönnyítése érdekében);
b) a vezető elem (egyenlő 1) használatával a vezető oszlop összes elemét nullává kell tenni (hasonlóan az ismeretlenek kiküszöbölésének módszeréhez);
Ennek eredményeként az új alapváltozók értékeit a nulla oszlopban kapjuk meg x 2 , x 3 , x 4 , x 5 ,(lásd 2. táblázat) - az új felső alapelemei x00(nem alapvető összetevők x 1 \u003d 0, x 6 = 0,).

Ahogy a 2. táblázat mutatja, az új alapmegoldás x00 =(0,10,30,20,40,0) nem optimális (a nulla sorban van egy nem negatív becslés 7). Ezért az 1. vezető elemmel (lásd 2. táblázat) egy új szimplex táblát konstruálunk, azaz. új, elfogadható alapmegoldást konstruálunk

A 3. táblázat az elfogadható alapmegoldásnak felel meg x000 =(10,0,30,10,50,0)és ez optimális, mert a nulla vonalban nincsenek pozitív jelek. Ezért f(x000)=390 a célfüggvény minimális értéke.
Válasz: x000 =(10, 0, 30, 10, 50, 0)- minimum pont, f(x000)=390.

Feltételesen standard lineáris programozási probléma

1. Keresse meg az optimális tervet a közvetlen problémára:
   a) grafikus módszer;
   b) szimplex módszerrel (a kezdeti referenciaterv elkészítéséhez a mesterséges bázis módszer alkalmazása javasolt).
2. Kettős probléma felépítése.
3. Keresse meg a duális feladat optimális tervét az egyenes grafikus megoldásából a komplementer lazaság feltételeivel!
4. Keresse meg a duális probléma optimális tervét az első dualitástétel segítségével a direkt probléma megoldásával kapott végső szimplex tabló segítségével (lásd 1b. fejezet). Ellenőrizze az állítást "egy kettős feladatpár célfüggvényeinek értékei az optimális megoldásukon megegyeznek."
5. Oldja meg a duális feladatot szimplex módszerrel, majd a duális feladat végső szimplex táblájával keresse meg a direkt probléma optimális tervét az első dualitástétel segítségével. Hasonlítsa össze az eredményt a grafikus módszerrel kapott eredménnyel (lásd az 1a bekezdést).
6. Keresse meg az optimális egész megoldást:
   a) grafikus módszer;
   b) Gomory-módszer.
   Hasonlítsa össze az egész és nem egész számú megoldások függvényértékeit

Kérdések az önkontrollhoz

1. Hogyan épül fel egy szimplex tábla?
2. Hogyan jelenik meg a bázis változása a táblázatban?
3. Fogalmazzon leállási kritériumot a szimplex módszerhez!
4. Hogyan kell megszervezni a táblázat újraszámítását?
5. Melyik sorból célszerű elkezdeni a táblázat újraszámítását?

Fontolgat szimplex módszer a lineáris programozás (LP) problémáinak megoldására. Alapja az egyik referenciatervről a másikra való átmenet, amelyben a célfüggvény értéke nő.

A szimplex módszer algoritmusa a következő:

1. Az eredeti problémát további változók bevezetésével fordítjuk kanonikus formára. Egy ≤ alakú egyenlőtlenséghez további változókat vezetünk be (+), de ha ≥ alakú, akkor (-) jellel. További változók kerülnek be a célfüggvénybe a megfelelő előjelekkel egyenlő együtthatóval 0 , mert a célfüggvénynek nem szabad megváltoztatnia a gazdasági jelentését.
2. Vektorokat adnak ki Pi a változók együtthatóiból és a szabad tagok oszlopából. Ez a művelet határozza meg az egységvektorok számát. A szabály az, hogy annyi egységvektor legyen, ahány egyenlőtlenség van a kényszerrendszerben.
3. Ezt követően a kiindulási adatok bekerülnek a szimplex táblába. Az egységvektorokat bevezetjük a bázisba, és ezeket a bázisból kizárva megtaláljuk az optimális megoldást. A célfüggvény együtthatóit ellentétes előjellel írjuk.
4. Az LP probléma optimálissági kritériuma, hogy a megoldás akkor legyen optimális, ha be f– sor minden együttható pozitív. Engedélyezési oszlop keresési szabály – Megtekintve f egy karakterlánc és negatív elemei közül a legkisebbet választjuk. Vektor Pi tartalma megengedővé válik. A feloldó elem kiválasztásának szabálya - összeállítják a feloldó oszlop pozitív elemeinek és a vektor elemeinek arányát P 0és a legkisebb arányt adó szám lesz a feloldóelem, amelyhez képest a szimplex tábla újraszámításra kerül. Az ezt az elemet tartalmazó karakterláncot engedélyezési karakterláncnak nevezzük. Ha a felbontás oszlopban nincsenek pozitív elemek, akkor a problémának nincs megoldása. A feloldó elem meghatározása után egy új szimplex tábla újraszámítására lépnek.
5. Új szimplex tábla kitöltésének szabályai. A feloldó elem helyére az egyiket letesszük, a többi elemet egyenlőnek tételezzük fel 0 . A feloldó vektort hozzáadjuk a bázishoz, amelyből a megfelelő nulla vektort kizárjuk, és a fennmaradó bázisvektorokat változatlanul írjuk. A megengedő vonal elemeit elosztjuk a megengedő elemmel, a fennmaradó elemeket a téglalapok szabálya szerint újraszámoljuk.
6. Ez addig történik, amíg a f– a karakterlánc minden eleme nem lesz pozitív.

Tekintsük a probléma megoldását a fenti algoritmus segítségével.
Adott:

A problémát a kanonikus formába visszük:

Vektorokat állítunk össze:

Töltse ki a szimplex táblázatot:

:
Számítsa újra a vektor első elemét P 0, amelyhez számokból téglalapot készítünk: és kapjuk: .

Hasonló számításokat végzünk a szimplex tábla összes többi elemére:

A kapott tervben f– a karakterlánc egy negatív elemet tartalmaz – (-5/3), vektorokat P1. Az oszlopában az egyetlen pozitív elemet tartalmazza, amely a feloldó elem lesz. Számoljuk újra a táblázatot ehhez az elemhez:

A negatív elemek hiánya f- a karakterlánc azt jelenti, hogy megtalálható optimális terv:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. Lineáris programozás, M: Nauka, 1998,
• Wentzel E.S. Operations Research, M: Szovjet Rádió, 2001,
• Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Matematikai programozás, M: Felsőiskola, 1986

Egyedi lineáris programozási megoldás

Honlapunkon bármilyen feladatot megrendelhet ebben a tudományágban. Fájlokat csatolhat és határidőket adhat meg a címen

Ha a feladat feltételében vannak ≥ előjelű megszorítások, akkor ezek az egyenlőtlenség mindkét részét -1-gyel megszorozva ∑a ji b j alakra redukálhatók. Bevezetünk m további változót x n+j ≥0(j =1,m ) és transzformáljuk a megszorításokat egyenlőségek alakjába

(2)

Tegyük fel, hogy az x 1 , x 2 ,..., x n feladat minden kezdeti változója nem alapváltozó. Ekkor a további változók alapváltozók lesznek, és a kényszerrendszer adott megoldásának formája van

x 1 = x 2 = ... = x n = 0, x n+ j = b j , j = 1, m . (3)

Mivel ebben az esetben a célfüggvény értéke F 0 = 0, az F(x)-t a következőképpen ábrázolhatjuk:

F(x)=∑c i x i + F 0 =0 (4)

A kezdeti szimplex tábla (1. szimplex tábla) a (2) és (4) egyenletek alapján kerül összeállításra. Ha a további x n+j változók előtt a „+” jel szerepel, mint a (2)-ben, akkor az x i változók előtti összes együttható és a b j szabad tag változtatás nélkül bekerül a szimplex táblába. A célfüggvény együtthatói annak maximalizálása során ellentétes előjellel kerülnek be a szimplex tábla alsó sorába. A szimplex táblában a szabad tagok határozzák meg a feladat megoldását.

A probléma megoldásának algoritmusa a következő:

1. lépés. Megjelenik a szabad tagok oszlop elemei. Ha mindegyik pozitív, akkor egy elfogadható alapmegoldást találtunk, és tovább kell lépni az algoritmus 5. lépésére, amely megfelel az optimális megoldás megtalálásának. Ha a kezdeti szimplex tablóban negatív szabad kifejezések vannak, akkor a megoldás nem érvényes, és folytassa a 2. lépéssel.

2. lépés. A megvalósítható megoldás megtalálása során el kell dönteni, hogy a nem alapváltozók közül melyiket vegyük be a bázisba, és melyiket vonjuk ki a bázisból.

Asztal 1.

Ehhez válasszuk ki a szabad tagok oszlopának bármelyik negatív elemét (legyen b 2 vezető, vagy engedélyező. Ha a negatív szabad taggal rendelkező sorban nincsenek negatív elemek, akkor a korlátozások rendszere inkonzisztens, ill. a problémának nincs megoldása.

Ugyanakkor az a változó, amelyik elsőként vált előjelet a kiválasztott NP x l növekedésével, ki van zárva az ÜT-ből. Ez x n+r lesz, amelynek r indexét a feltétel határozza meg

azok. az a változó, amelyik a szabad tag legkisebb arányának felel meg a kiválasztott vezető oszlop eleméhez viszonyítva. Ezt a kapcsolatot úgy hívják szimplex reláció. Csak a pozitív szimplex összefüggéseket kell figyelembe venni.

Az x n+r változónak megfelelő karakterláncot hívjuk vezet, vagy megenged. Az a rl szimplex tábla elemét, amely a vezető sor és a vezető oszlop metszéspontjában van, vezető vagy feloldó elemnek nevezzük. A vezető elem megtalálása minden következő szimplex tablóval lezárja a munkát.

3. lépés. Egy új szimplex tábla számítására kerül sor, melynek elemeit az előző lépés szimplex tábla elemeiből újraszámítjuk és prímmel jelöljük, azaz. b" j , a" ji , c" i , F" 0 . Az elemek újraszámítása a következő képletekkel történik:

Először az előző szimplex táblában vezető sor és oszlop kerül kitöltésre az új szimplex táblában. Az (5) kifejezés azt jelenti, hogy a vezető elem helyén lévő a "rl elem egyenlő az előző szimplex tábla elemének reciprokával. Az a ri sor elemeit elosztjuk a vezető elemmel, és a az a jl oszlopot is elosztjuk a vezető elemmel, de ellentétes előjellel vesszük. A b" r és c" l elemeket ugyanezen elv szerint számítjuk.

A többi képlet könnyen felírható a segítségével.

A téglalapot a régi szimplex táblázat szerint építjük fel úgy, hogy egyik átlóját az újraszámított (a ji) és a vezető (a rl) elemek alkotják (1. ábra). A második átló egyedileg meghatározott. Új elem megtalálásához a "ji, az ellentétes átló elemeinek szorzatát, osztva a vezető elemmel, kivonjuk az a ji elemből (ezt a jel jelzi" - "a cellánál). Hasonlóképpen a b elemeket" j, (j≠r) és c" i újraszámításra kerül, (i≠l).

4. lépés. Egy új szimplex tábla elemzése az algoritmus 1. lépésével kezdődik. Az akció addig folytatódik, amíg egy megvalósítható alapmegoldást nem találnak, azaz. a szabad tagok oszlop minden elemének pozitívnak kell lennie.

5. lépés. Úgy gondoljuk, hogy sikerült egy elfogadható alapmegoldást találni. Megnézzük az F(x) célfüggvény egyenesének együtthatóit. A szimplex tábla optimalitásának jele az F-sorban lévő nem alapváltozók együtthatóinak nem-negativitása.

Rizs. 1. Téglalap szabály

Ha az F-sor együtthatói között vannak negatívak (a szabad tag kivételével), akkor egy másik alapmegoldáshoz kell menni. A célfüggvény maximalizálása során a bázis tartalmazza a nem alapváltozókét (például x l), amelyek oszlopa a szimplex tábla alsó sorában a c l negatív együttható maximális abszolút értékének felel meg. Ez lehetővé teszi annak a változónak a kiválasztását, amelynek növelése a célfüggvény javulásához vezet. Az x l változónak megfelelő oszlopot vezető oszlopnak nevezzük. Ugyanakkor kikerül a bázisból az az x n+r változó, amelynek r indexét a minimális szimplex arány határozza meg:

Az x n+r-nek megfelelő sort vezető sornak, a szimplex tábla a rl elemét, amely a vezető sor és a vezető oszlop metszéspontjában van, pedig az ún. vezető elem.

6. lépés. 3. lépésben meghatározott szabályok szerint. Az eljárás mindaddig folytatódik, amíg meg nem találják az optimális megoldást, vagy arra a következtetésre nem jutnak, hogy az nem létezik.

Ha a megoldás optimalizálása során a vezető oszlopban minden elem nem pozitív, akkor a vezető sor nem választható ki. Ebben az esetben a feladat megengedett megoldásainak tartományában a függvény felülről nem korlátos és F max ->&∞.

Ha a szélsőérték keresésének következő lépésében az egyik alapváltozó nulla lesz, akkor a megfelelő alapmegoldást degeneráltnak nevezzük. Ebben az esetben az úgynevezett hurokolás következik be, amelyet az a tény jellemez, hogy a BP ugyanaz a kombinációja bizonyos gyakorisággal ismétlődik (az F függvény értéke ebben az esetben megmarad), és nem lehet átváltani. új, elfogadható alapmegoldás. A szimplex módszer egyik fő hátránya a hurkok, de viszonylag ritka. A gyakorlatban ilyen esetekben általában megtagadják annak a változónak a bázisba vételét, amelynek oszlopa a célfüggvény negatív együtthatójának maximális abszolút értékének felel meg, és véletlenszerűen választanak egy új alapmegoldást.

Példa 1. Probléma megoldása

max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤ 7; x 1 + 4x 2 ≥ 8; x 2 ≤ 4; x 1,2 ≥ 0)

Szimplex módszer, és adja meg a megoldási folyamat geometriai értelmezését.

A feladat megoldásának grafikus értelmezése az ábrán látható. 2. A célfüggvény maximális értékét a koordinátákkal ellátott ODZP tetején érjük el. Oldjuk meg a problémát szimplex táblák segítségével. Szorozza meg a második megszorítást (-1)-gyel, és vezessen be további változókat, hogy az egyenlőtlenségeket egyenlőségek alakjába hozza, majd

Az x 1 és x 2 kezdeti változókat nem alapváltozónak vesszük, a további x 3 , x 4 és x 5 változókat pedig alapvetőnek tekintjük, és összeállítunk egy szimplex táblát (2. szimplex tábla). A szimplex táblának megfelelő megoldás. 2, nem érvényes; a vezető elem körvonalazása és kiválasztása a fenti algoritmus 2. lépése szerint történik. A következő szimplex lap. A 3. ábra egy elfogadható alapmegoldást határoz meg; 2 A vezető elem körvonalazása és kiválasztása a feladatmegoldó algoritmus 5. lépése szerint történik. Tab. A 4 a feladat optimális megoldásának felel meg, ezért: x 1 = x 5 = 0; x 2 \u003d 4; x 3 \u003d 3; x 4 = 8; F max = 20.

Rizs. 2. A feladat grafikus megoldása