Ez a módszer egy lineáris programozási probléma referenciamegoldásának célirányos felsorolásának módszere. Lehetővé teszi, hogy véges számú lépésben vagy optimális megoldást találjunk, vagy megállapítsuk, hogy nincs optimális megoldás.

A szimplex módszer fő tartalma a következő:

1. Jelöljön meg egy módszert az optimális referenciamegoldás megtalálásához!
2. Jelölje meg az egyik referenciamegoldásból a másikba való átmenet módját, amelynél a célfüggvény értéke közelebb lesz az optimálishoz, pl. mutasson módot a referenciamegoldás javítására
3. Állítson be olyan kritériumokat, amelyek lehetővé teszik, hogy azonnal leállítsa a támogatási megoldások keresését az optimális megoldásnál, vagy következtetést vonjon le az optimális megoldás hiányáról.

A szimplex módszer algoritmusa lineáris programozási problémák megoldására

Egy probléma szimplex módszerrel történő megoldásához a következőket kell tennie:

1. Hozd a problémát kanonikus formába
2. Keresse meg a kezdeti támogatási megoldást „egységbázissal” (ha nincs támogatási megoldás, akkor a korlátrendszer összeférhetetlensége miatt a problémának nincs megoldása)
3. Számítsa ki a vektorbontások becsléseit a referenciamegoldás alapján, és töltse ki a szimplex módszer táblázatát!
4. Ha az optimális megoldás egyediségének kritériuma teljesül, akkor a probléma megoldása véget ér
5. Ha az optimális megoldások halmazának létezésének feltétele teljesül, akkor egyszerű felsorolással minden optimális megoldás megtalálható

Példa egy feladat megoldására szimplex módszerrel

26.1. példa

Oldja meg a problémát a szimplex módszerrel:

Megoldás:

A problémát kanonikus formába hozzuk.

Ehhez az első egyenlőtlenségi kényszer bal oldalára bevezetünk egy további x 6 változót +1 együtthatóval. Az x 6 változó nulla együtthatóval szerepel a célfüggvényben (azaz nincs benne).

Kapunk:

Megtaláljuk a kezdeti támogatási megoldást. Ehhez a szabad (feloldatlan) változókat nullával egyenlővé tesszük x1 = x2 = x3 = 0-val.

Kapunk referencia oldat X1 = (0,0,0,24,30,6) egységalapon B1 = (A4, A5, A6).

Kiszámoljuk vektorbontások becslései feltételek a referenciaoldat alapján a következő képlet szerint:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - a célfüggvény együtthatóinak vektora az alapváltozókra
• X k = (x 1k, x 2k, ..., x mk) - a megfelelő A k vektor kiterjesztési vektora a referenciamegoldás alapján
• C k a célfüggvény együtthatója az x k változóra.

A bázisban szereplő vektorok becslései mindig nullával egyenlőek. A referenciamegoldás, a kiterjesztési együtthatók és a feltételvektorok kiterjesztésének becslései a referenciamegoldás alapján a szimplex asztal:

A táblázat tetejére a becslések könnyebb kiszámíthatósága érdekében a célfüggvény együtthatóit írjuk. Az első "B" oszlopba a referenciamegoldás alapjában szereplő vektorokat írjuk. A vektorok felírásának sorrendje megfelel a kényszeregyenletekben megengedett ismeretlenek számának. A "C b" tábla második oszlopában az alapváltozókra vonatkozó célfüggvény együtthatói ugyanabban a sorrendben vannak beírva. A célfüggvény együtthatóinak helyes elrendezése esetén a "C b" oszlopban a bázisban szereplő egységvektorok becslései mindig nullával egyenlőek.

A táblázat utolsó sorában a Δ k becslésekkel az „A 0” oszlopban a Z(X 1) referenciamegoldás célfüggvényének értékeit írjuk.

A kezdeti támaszmegoldás nem optimális, mivel a maximumfeladatban az A 1 és A 3 vektorokra vonatkozó Δ 1 = -2, Δ 3 = -9 becslések negatívak.

A támaszmegoldás javítására vonatkozó tétel szerint, ha egy maximumfeladatban legalább egy vektor negatív becsléssel rendelkezik, akkor lehet olyan új támaszmegoldást találni, amelyen a célfüggvény értéke nagyobb lesz.

Határozzuk meg, hogy a két vektor közül melyik vezet nagyobb növekedéshez a célfüggvényben.

A célfüggvény növekményét a következő képlet határozza meg: .

A θ 01 paraméter értékeit az első és a harmadik oszlophoz a következő képlettel számítjuk ki:

l = 1 esetén θ 01 = 6, l = 1 esetén θ 03 = 3 (26.1. táblázat).

A célfüggvény növekményét akkor kapjuk meg, ha a bázisba bevisszük az első vektort ΔZ 1 = - 6*(- 2) = 12, és a harmadik vektort ΔZ 3 = - 3*(- 9) = 27.

Következésképpen az optimális megoldás gyorsabb megközelítéséhez az A3 vektort kell bevinni a referenciamegoldás bázisába az A6 bázis első vektora helyett, mivel a θ 03 paraméter minimumát az első sorban érjük el ( l = 1).

A Jordan transzformációt X13 = 2 elemmel végezzük, a második X2 = (0,0,3,21,42,0) referenciamegoldást B2 = (A3, A4, A5) bázissal kapjuk. (26.2. táblázat)

Ez a megoldás nem optimális, mivel az A2 vektor negatív becslése Δ2 = - 6. A megoldás javításához be kell vezetni az A2 vektort a referenciamegoldás alapjába.

Meghatározzuk a bázisból származtatott vektor számát. Ehhez kiszámítjuk a θ 02 paramétert a második oszlophoz, amely l = 2 esetén 7. Következésképpen a bázisból származtatjuk az A4 második bázisvektort. A Jordan-transzformációt x 22 = 3 elemmel végezzük, megkapjuk a harmadik referenciamegoldást X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (26.3. táblázat).

Ez a megoldás az egyetlen optimális, mivel minden, a bázisban nem szereplő vektorra a becslések pozitívak

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Válasz: max Z(X) = 201 X = (0,7, 10, 0,63).

Lineáris programozási módszer a közgazdasági elemzésben

Lineáris programozási módszer lehetővé teszi a legoptimálisabb gazdasági megoldás igazolását a termelésben felhasznált erőforrásokkal (befektetett eszközök, anyagok, munkaerő) kapcsolatos szigorú korlátozások körülményei között. Ennek a módszernek a közgazdasági elemzésben való alkalmazása elsősorban a szervezet tevékenységének tervezésével kapcsolatos problémák megoldását teszi lehetővé. Ez a módszer segít meghatározni a termékkibocsátás optimális mennyiségeit, valamint a szervezet rendelkezésére álló termelési erőforrások leghatékonyabb felhasználásának irányait.

Ezzel a módszerrel az ún. extrém problémákat oldjuk meg, ami abból áll, hogy szélsőértékeket, azaz változó mennyiségek függvényeinek maximumát és minimumát keressük.

Ez az időszak lineáris egyenletrendszer megoldásán alapul olyan esetekben, amikor a vizsgált gazdasági jelenségeket lineáris, szigorúan funkcionális függés köti össze. A lineáris programozási módszer a változók elemzésére szolgál bizonyos korlátozó tényezők jelenlétében.

Nagyon elterjedt az úgynevezett szállítási probléma megoldása lineáris programozási módszerrel. Ennek a feladatnak a tartalma a járművek meglévő korlátozások melletti üzemeltetésével kapcsolatban felmerülő költségek minimalizálása a járművek számát, teherbírását, üzemeltetési idejét illetően, amennyiben a maximális ügyfélszám kiszolgálására van szükség.

Ezenkívül ezt a módszert széles körben használják az ütemezési probléma megoldására. Ez a feladat egy olyan működési idő elosztásából áll egy adott szervezet személyi állománya számára, amely a legelfogadhatóbb lenne mind a személyzet tagjai, mind a szervezet ügyfelei számára.

Ez a feladat a rendelkezésre álló létszám és a munkaidő keret korlátozása mellett a kiszolgált ügyfelek számának maximalizálása.

A lineáris programozási módszer tehát igen elterjedt a különböző típusú erőforrások elhelyezésének, felhasználásának elemzésében, valamint a szervezetek tevékenységének tervezési és előrejelzési folyamatában.

Mindazonáltal a matematikai programozás azokra a gazdasági jelenségekre is alkalmazható, amelyek közötti kapcsolat nem lineáris. Erre a célra nemlineáris, dinamikus és konvex programozási módszerek használhatók.

A nemlineáris programozás a célfüggvény vagy a megszorítások nemlineáris természetére támaszkodik, vagy mindkettőre. A célfüggvény és az egyenlőtlenségi kényszerek formái ezekben a feltételekben eltérőek lehetnek.

A nemlineáris programozást a gazdasági elemzésben használják, különösen a szervezet tevékenységének hatékonyságát kifejező mutatók és e tevékenység volumene, a termelési költségek szerkezete, a piaci feltételek stb.

A dinamikus programozás döntési fa felépítésén alapul. A fa minden egyes szintje egy korábbi döntés következményeinek meghatározásához és az adott döntés nem hatékony lehetőségeinek kiküszöböléséhez szolgál. Így a dinamikus programozás többlépcsős, többlépcsős természetű. Ezt a fajta programozást a közgazdasági elemzésben használják, hogy optimális lehetőségeket találjanak egy szervezet fejlesztéséhez mind most, mind a jövőben.

A konvex programozás a nemlineáris programozás egyik fajtája. Az ilyen típusú programozás a szervezet tevékenységeinek eredményei és költségei közötti kapcsolat nemlineáris jellegét fejezi ki. A konvex (más néven konkáv) programozás konvex célfüggvényeket és konvex kényszerrendszereket (megvalósíthatósági pontokat) elemez. A konvex programozást a gazdasági tevékenységek elemzésében használják a költségek minimalizálása céljából, a konkáv programozást pedig azzal a céllal, hogy maximalizálják a bevételt a meglévő korlátozások mellett, amelyek a vizsgált mutatókat ellenkező módon befolyásolják. Következésképpen a szóban forgó programozási típusokkal a konvex célfüggvények minimálisra, a konkáv célfüggvények pedig maximalizálva vannak.

x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

≤ = ≥

≤ = ≥

≤ = ≥

×

Figyelem

Törli az összes cellát?

Bezárás Törlés

Adatbeviteli utasítások. A számok egész számok (például 487, 5, -7623 stb.), tizedesjegyek (pl. 67., 102,54 stb.) vagy törtek formájában kerülnek megadásra. A törtet a/b formában kell megadni, ahol a és b (b>0) egész vagy decimális szám. Példák 45/5, 6,6/76,4, -7/6,7 stb.

Simplex módszer

Példák a ZLP megoldására szimplex módszerrel

1. példa Oldja meg a következő lineáris programozási feladatot:

Az egyenletrendszer megszorításainak jobb oldala a következő alakú:

Jegyezzük fel az aktuális referenciatervet:

Ez a referenciaterv nem optimális, mert az utolsó sorban negatív elemek vannak. A modulusz legnagyobb negatív eleme (-3), ezért a vektor benne van a bázisban x nál nél . min(40:6, 28:2)=20/3 az 1. sornak felel meg. A vektor a bázisból jön ki x 3. Végezzünk Gauss-eliminációt az oszlopra x 2, mivel a vezető elem az 1. sornak felel meg. Állítsuk vissza ennek az oszlopnak az összes elemét, kivéve a vezető elemet. Ehhez adja össze a 2., 3., 4. sor sorait az 1. sorral, szorozva -1/3, 1/6, 1/2-vel. Ezután a vezető elemet tartalmazó sort elosztjuk a vezető elemmel.

Ez a referenciaterv nem optimális, mivel az utolsó sor negatív elemű (-3), ezért a bázis tartalmazza a vektort x 1 . Meghatározzuk, hogy melyik vektor jön ki a bázisból. Ehhez kiszámoljuk nál nél . min(44/3:11/3, 62/3:5/3)=4 a 2. sornak felel meg. A vektor a bázisból jön ki x 4. Végezzünk Gauss-eliminációt az oszlopra x 1, mivel a vezető elem a 2. sornak felel meg. Állítsuk vissza ennek az oszlopnak az összes elemét, kivéve a vezető elemet. Ehhez adja hozzá az 1., 3., 4. sorokat a 2. sor 1/11, -5/11, 9/11 szorzatával. Ezután a vezető elemet tartalmazó sort elosztjuk a vezető elemmel.

A szimplex táblázat a következő formájú lesz:

A jelenlegi referenciaterv optimális, hiszen a változók 4. sorában nincsenek negatív elemek.

A megoldást így írhatjuk fel: .

A célfüggvény értéke ezen a ponton: F(x)=.

Példa 2. Keresse meg egy függvény maximumát

Megoldás.

Alapvektorok x 4 , x 3 tehát minden elem oszlopban x 4 , x A vízszintes vonal alatti 3-nak nullának kell lennie.

Állítsa vissza az összes oszlopelemet nullára x 4, kivéve a vezető elemet. Ehhez adja hozzá a 3. sort az 1. sor 4-gyel szorozva. Állítsa vissza az oszlop összes elemét nullára x 3, kivéve a vezető elemet. Ehhez adja hozzá a 3. sort a 2. sor 1-gyel szorozva.

A szimplex táblázat a következő formában jelenik meg:

Ez a referenciaterv nem optimális, mivel az utolsó sor negatív elemű (-11), ezért a bázis tartalmazza a vektort x 2. Meghatározzuk, hogy melyik vektor jön ki a bázisból. Ehhez kiszámoljuk nál nél . Ezért a célfüggvény felülről korlátlan. Azok. a lineáris programozási probléma megoldhatatlan.

Példák a ZLP megoldására mesterséges bázis módszerrel

Példa 1. Keresse meg egy függvény maximumát

Megoldás: Mivel a bázisvektorok számának 3-nak kell lennie, hozzáadunk egy mesterséges változót, és a célfüggvényhez hozzáadjuk ezt a változót −M-mel szorozva, ahol M egy nagyon nagy szám:

Az egyenletrendszer együtthatómátrixának alakja:

A bázisvektorok ezért a vízszintes vonal alatti oszlopokban minden elemnek nullának kell lennie.

Állítsuk vissza az oszlop összes elemét, kivéve a vezető elemet. Ehhez adja hozzá az 5. sort a 3. sor -1-gyel szorozva.

A szimplex táblázat a következő formában jelenik meg:

Ez a referenciaterv nem optimális, mert az utolsó sorban negatív elemek vannak. A legnagyobb abszolút negatív elem (-5), ezért a vektor benne van a bázisban Meghatározzuk, hogy melyik vektor jön ki a bázisból. Ehhez kiszámoljuk nál nél A bázisból egy vektor jön ki. Tegyünk egy Gauss-kivételt az oszlopra, mivel a vezető elem a 3. sornak felel meg. Állítsuk vissza ennek az oszlopnak az összes elemét, kivéve a vezető elemet. Ehhez adja hozzá az 5. sort a 3. sor 1-gyel szorozva. Ezután ossza el a bevezető elemet tartalmazó sort a vezető elemmel.

A szimplex táblázat a következő formájú lesz:

Ez a referenciaterv nem optimális, mert az utolsó sorban negatív elemek vannak. A legnagyobb abszolút negatív elem (-3), ezért a vektor benne van a bázisban Meghatározzuk, hogy melyik vektor jön ki a bázisból. Ehhez kiszámoljuk nál nél az 1. sornak felel meg. A vektor a bázisból jön ki x 2. Végezzünk Gauss-eliminációt az oszlopra x 1 , mivel a vezető elem az 1. sornak felel meg. Állítsuk vissza ennek az oszlopnak az összes elemét, kivéve a vezető elemet. Ehhez adja össze a 2., 3., 4. sor sorait az 1. sorral, szorozva 3/2, -1/10, 3/2-vel. Ezután a vezető elemet tartalmazó sort elosztjuk a vezető elemmel.

A szimplex táblázat a következő formájú lesz:

Ez a referenciaterv nem optimális, mert az utolsó sorban negatív elemek vannak. A modulusz legnagyobb negatív eleme (-13/2), ezért a bázis tartalmazza a vektort x 3. Meghatározzuk, hogy melyik vektor jön ki a bázisból. Ehhez kiszámoljuk nál nél a 3. sornak felel meg. A vektor a bázisból jön ki x 5. Végezzünk Gauss-eliminációt az oszlopra x 3, mivel a vezető elem a 3. sornak felel meg. Állítsuk vissza ennek az oszlopnak az összes elemét, kivéve a vezető elemet. Ehhez adja össze az 1., 2., 4. sor sorait a 3. sorral, szorozva 5/3, 25/9, 65/9. Ezután a vezető elemet tartalmazó sort elosztjuk a vezető elemmel.

A szimplex táblázat a következő formájú lesz:

A jelenlegi referenciaterv optimális, mivel a 4-5. sor változói alatt nincsenek negatív elemek.

Az eredeti probléma megoldása a következőképpen írható fel:

2. példa Keresse meg az optimális tervet egy lineáris programozási feladathoz:

Az egyenletrendszer együtthatómátrixának alakja:

Alapvektorok x 4 , x 5 , x 6 ezért minden elem oszlopban x 4 , x 5 , x 6, a vízszintes vonal alatt nullának kell lennie.

Állítsa vissza az összes oszlopelemet nullára x 4, kivéve a vezető elemet. Ehhez adja hozzá a 4. sort az 1. sor -1-gyel szorozva. Állítsa vissza az összes oszlopelemet nullára x 5, kivéve a vezető elemet. Ehhez adja hozzá az 5. sort a 2. sor -1-gyel szorozva. Állítsa vissza az összes oszlopelemet nullára x 6, kivéve a vezető elemet. Ehhez adja hozzá az 5. sort a 3. sor -1-gyel szorozva.

A szimplex táblázat a következő formában jelenik meg:

Az 5. sorban a változóknak megfelelő elemeket x 1 , x 2 , x 3 , x 4 , x 5 , x A 6 nem negatív, és a szám egy adott sor és oszlop metszéspontjában található x 0 negatív. Ekkor az eredeti problémának nincs referenciaterve. Ezért eldönthetetlen.

Simplex módszer egy lineáris programozási probléma kényszerrendszerének egyik alapmegoldásából (a megoldási poliéder csúcsából) egy másik alapmegoldásba való szekvenciális átmenet módszere, amíg a célfüggvény optimális értéket (maximum vagy minimum) nem vesz fel.

A szimplex módszer egy univerzális módszer, amely bármelyiket megoldja lineáris programozási probléma, míg a grafikus módszer csak kétváltozós kényszerrendszerre alkalmas.

A szimplex módszert R. Danzig amerikai matematikus javasolta 1947-ben, azóta a lineáris programozási problémákat, változók ezreivel és korlátaival, gyakran ezzel a módszerrel oldják meg ipari igényekre.

Mielőtt rátérnénk a szimplex módszer algoritmusára, néhány definíció.

A kényszerrendszer bármely nem negatív megoldását hívjuk elfogadható megoldás .

Legyen rendszer m korlátozások tól n változók ( m n).

Megengedhető alapmegoldás tartalmú oldat m nem negatív fő- (alapvető ) változók és n - m nem mag . (nem alap, ill ingyenes ) változók. Az alapmegoldás kisebb változói nullával egyenlőek, de a fő változók általában nem nullák, azaz pozitív számok.

Bármi m rendszerváltozók m lineáris egyenletek -val n változókat nevezzük fő- , ha ezek együtthatóinak meghatározója nullától eltérő. Aztán a többit n - m változókat nevezzük nem mag (vagy ingyenes ).

Simplex módszer algoritmus

• 1. lépés. Csökkentse a lineáris programozási problémát kanonikus formára. Ehhez mozgassa a szabad tagokat a jobb oldalra (ha ezek között a szabad tagok között vannak negatívak is, akkor a megfelelő egyenletet vagy egyenlőtlenséget szorozzuk meg -1-gyel), és adjunk be további változókat minden kényszerbe (plusz előjellel, ha az eredeti egyenlőtlenség jele „kisebb vagy egyenlő”, és mínuszjellel, ha „nagyobb vagy egyenlő”).
• 2. lépés. Ha az így létrejövő rendszerben m akkor egyenletek m vegyük a változókat főnek, fejezzük ki a fő változókat a nem alapváltozókkal, és keressük meg a megfelelő alapmegoldást. Ha a talált alapmegoldás elfogadhatónak bizonyul, lépjen az elfogadható alapmegoldásra.
• 3. lépés. Fejezd ki a célfüggvényt egy elfogadható alapmegoldás nem alapváltozóival. Ha egy lineáris forma maximumát (minimumát) megtaláltuk, és a kifejezésében nincsenek negatív (pozitív) együtthatós nem alapváltozók, akkor az optimalitási kritérium teljesül, és a kapott alapmegoldás optimális - a megoldás kész. Ha egy lineáris forma maximumának (minimumának) megtalálásakor annak kifejezése egy vagy több nem alapváltozót tartalmaz negatív (pozitív) együtthatóval, akkor folytassuk az új alapmegoldást.
• 4. lépés. A lineáris formában szereplő, negatív (pozitív) együtthatós nem alapváltozók közül válassza ki azt, amelyik a legnagyobb (abszolút értékben) együtthatónak felel meg, és konvertálja át az alapváltozókra. Folytassák a 2. lépéssel.

Fontos feltételek

Néhány speciális esetet külön cikkek tárgyalnak: mikor a célfüggvény maximuma a végtelen, Amikor a rendszernek nincs megoldása, és mikor az optimális megoldás nem az egyetlen .

Ezután egy tipikus példát nézünk meg, amikor a kényszerrendszer együttes, és van egy végső optimum, és egy egyedi. A szimplex módszer egyik változata szállítási probléma megoldásának elosztási módja .

Szimplex módszer szimplex táblákkal

Simplex táblák készítésével a lineáris programozási feladat megoldása sokkal egyszerűbb, mint algebrai transzformációkkal, amit a következő bekezdésben mutatunk be. A szimplex táblázatok nagyon vizuálisak. A szimplex táblákkal való munkavégzéshez többféle szabály létezik. Megvizsgálunk egy szabályt, amelyet leggyakrabban vezető oszlop és vezető sor szabálynak neveznek.

Hasznos lenne új ablakban megnyitni a kézi Műveletek törtekkel: a szimplex módszerrel enyhén szólva is van belőlük elég.

Példa.

További nemnegatív változókat vezetünk be, és ezt az egyenlőtlenségi rendszert a megfelelő egyenletrendszerre redukáljuk

.

Ez a következő szabály betartásával történt: ha az eredeti kényszerben „kisebb vagy egyenlő” előjel van, akkor a további változót hozzá kell adni, ha pedig „nagyobb vagy egyenlő”, akkor a további változót ki kell vonni.

A bevezetett további változókat tekintjük főnek (alapváltozóknak). Ekkor és nem alap (ingyenes) változók.

A fő (alap)változókat nem alap (szabad) változókkal kifejezve megkapjuk

A célfüggvényt nem elsődleges (szabad) változókkal is kifejezhetjük:

Az (ismeretlen) változók együtthatóiból megszerkesztjük az első szimplex táblát.

Asztal 1
Alapvető ismeretlenek	Ingyenes tagok	Szabad ismeretlenek		Segéd együtthatók
		X1	X2
X3	-2	1	-2
X4	-4	-1	-1
X5	2	1	-1
X6	6	0	1
F	0	-1	-2

A táblázat utolsó sorát, amely a célfüggvényt és a benne lévő szabad változók együtthatóit tartalmazza, indexsornak nevezzük.

A kapott megoldás nem optimális, mivel az indexsorban a szabad változók együtthatói negatívak. Azaz az optimális megoldás az lesz, amelyben az indexsorban lévő szabad változók együtthatói nullánál nagyobbak vagy egyenlőek.

A következő táblázathoz való továbblépéshez keressük meg a legnagyobbat (modulo) az és a számok közül. Ez a szám 2. Ezért a vezető oszlop az az oszlop, amelyben

A vezető sor meghatározásához megtaláljuk a szabad tagok minimális arányát a vezető oszlop elemeihez viszonyítva, és ha a számláló pozitív szám, a nevező pedig negatív, akkor az arányt a végtelennel egyenlőnek tekintjük.

.

Ezért a vezető sor az, amelyikbe be van írva

A vezető elem tehát -2.

Összeállítjuk a második szimplex táblát.

Az első sorba beírjuk az új alapelemet, és abba az oszlopba, amelyben volt, egy új szabad változót

Töltse ki az első sort. Ehhez elosztjuk az 1. táblázat kezdő sorában lévő összes számot a vezető elemmel, és beírjuk a 2. táblázat első sorának megfelelő oszlopába, kivéve a bevezető oszlopban lévő számot, ahol a bevezető inverze. elemet írunk (azaz egyet elosztunk a vezető elemmel).

Töltse ki a segédegyütthatók oszlopát. Az 1. táblázat kezdő oszlopában erre a számra a vezető elem mellett ellentétes előjelekkel írunk a 2. táblázat segédegyütthatói oszlopába.

2. táblázat
Alapvető ismeretlenek	Ingyenes tagok	Szabad ismeretlenek		Segéd együtthatók
		X1	X3
X2	1	-1/2	-1/2
X4	-3	-3/2	-1/2	1
X5	3	1/2	-1/2	1
X6	5	1/2	1/2	-1
F	2	-2	-1	2

Aki még nem nyitotta meg új ablakban a kézi Műveletek törtekkel című részt, most megteheti, mert itt az ideje.

A 2. táblázat fennmaradó sorainak megszerzéséhez a táblázat első sorában már szereplő számokat megszorozzuk a kitöltendő sorban lévő segédegyütthatóval, és az eredményhez hozzáadjuk az 1. táblázatból származó számot, amely ugyanabban a sorban található. sor a megfelelő változóval.

Például, hogy megkapjuk a második sor szabad tagját, megszorozzuk az 1-et 1-gyel, és hozzáadjuk az 1. táblázatból a -4-et. -3-at kapunk. A második sorban megtaláljuk az együtthatót is: . Mivel az előző táblázatban nincs új szabad változót tartalmazó oszlop, ezért az új szabad változó oszlopában a második sor együtthatója (azaz az 1. táblázatból 0-t adunk hozzá, mivel az 1. táblából hiányzik a c oszlop).

Az indexsor is kitöltésre kerül:

Az így kapott megoldás ismét nem optimális, mivel az indexsorban a szabad változók együtthatói ismét negatívak.

A következő szimplex táblára lépéshez megkeressük az indexsorban a számok legnagyobbját (modulo), vagyis az együtthatók modulusait. Ez a szám 2. Ezért a vezető oszlop az az oszlop, amelyben .

A vezető sor megtalálásához megkeressük a szabad tagok minimális arányát a vezető sor elemeihez viszonyítva. Kapunk:

.

Ezért a vezető sor az, amelyben , a vezető elem pedig -3/2.

A harmadik szimplex tábla összeállítása

Az első sorba írjuk az új alapváltozót. Abba az oszlopba, amelyben , egy új szabad változót adunk meg.

Első sor:

Segéd együtthatók:

3. táblázat
Alapvető ismeretlenek	Ingyenes tagok	Szabad ismeretlenek		Segéd együtthatók
		X4	X3
X1	2	-2/3	1/3
X2	2	-1/3	-1/3	1/2
X5	2	1/3	-2/3	-1/2
X6	4	1/3	1/3	-1/2
F	6	-4/3	-1/3	2

A kapott megoldás ismét nem optimális, mivel az indexsorban lévő szabad ismeretlenek együtthatói ismét negatívak.

A negyedik szimplex táblához való lépéshez megtaláljuk a legnagyobb és számok közül a legnagyobbat. Ez a szám.

Ezért a vezető oszlop az, amelyben .

A szabad tagok és a vezető oszlop elemei közötti kapcsolatok minimális moduljai:

.

Ezért a vezető sor az, amelyben , a vezető elem pedig az 1/3.

A negyedik szimplex táblába az új alapváltozót írjuk első sorként. Az oszlopba ahol , írunk egy új szabad változót.

Első sor:

Segéd együtthatók:

4. táblázat
Alapvető ismeretlenek	Ingyenes tagok	Szabad ismeretlenek		Segéd együtthatók
		X5	X3
X4	6	3	-2
X1	6	2	-1	2/3
X2	4	1	-1	1/3
X6	2	-1	1	-1/3
F	14	4	-3	4/3

A fennmaradó sorok kiszámítása a második sor példájával:

A kapott megoldás szintén nem optimális, de már jobb, mint az előzőek, mivel az indexsorban lévő szabad változók egyik együtthatója nem negatív.

A terv javításához térjünk át a következő szimplex táblára.

Keressük meg a 4 és a számok közül a legnagyobbat. Ez a szám 4. Ezért a vezető oszlop a .

A vezetővonal megtalálásához megtaláljuk

.

Ezért a vezető sor az, amelyben . De már együtt voltak a szabad változók között. Ezért a következő változó szabadból alapszintűre való átviteléhez kiválasztunk egy másik vezető oszlopot - azt, amelyben .

A vezetővonal megtalálásához megtaláljuk

.

Ezért a kulcssor az, amelyben , a vezető elem pedig 1.

Az ötödik szimplex tábla első soraként az új alapváltozót írjuk. Az oszlopba ahol , írunk egy új szabad változót.

Első sor:

Segéd együtthatók:

5. táblázat
Alapvető ismeretlenek	Ingyenes tagok	Szabad ismeretlenek		Segéd együtthatók
		X5	X6
X3	2	-1	1
X4	10			2
X1	8			1
X2	6			1
F	20	1	3	3

Próbáljuk meg azonnal kideríteni, hogy a megoldás optimális-e. Ezért a fennmaradó sorokhoz csak a szabad tagokat számítjuk ki (hogy megtudjuk az alapváltozók értékét, ha a szabad változók nullával egyenlőek) és az indexsorban lévő szabad változók együtthatóit.

Ingyenes tagok:

A második sorban;

A harmadik sorban;

A negyedik sorban.

Indexsor:

Megnézzük az 5. szimplex táblát. Látjuk, hogy az optimális megoldást kaptuk, mivel az indexsorban lévő szabad ismeretlenek együtthatói nem negatívak.

Simplex módszer algebrai transzformációkkal

Oldjuk meg ugyanazt a példát, mint az előző bekezdésben, algebrai transzformációkkal. Megjegyzendő, hogy az ilyen típusú szimplex metódusok megoldása során jobb, ha nem a célfüggvényt alakba írjuk , hiszen könnyen meg lehet zavarodni a jelekben. De ebben az esetben az optimalitási kritériumot meghatározó algoritmus pontja a következőképpen módosul.

Ha egy lineáris forma maximumát (minimumát) megtaláltuk, és a kifejezésében nincsenek pozitív (negatív) együtthatós nem alapváltozók, akkor az optimalitási feltétel teljesül, és a kapott alapmegoldás optimális - a megoldás kész. Ha egy lineáris forma maximumának (minimumának) megtalálásakor annak kifejezése egy vagy több nem alapváltozót tartalmaz pozitív (negatív) együtthatóval, akkor folytassuk egy új alapmegoldással.

Példa. Keresse meg egy függvény maximumát korlátozások mellett

I. lépés: További nemnegatív változókat vezetünk be, és ezt az egyenlőtlenségrendszert az ekvivalens egyenletrendszerre redukáljuk

.

A bevezetett további változókat tekintjük főnek, mivel ebben az esetben könnyen megtalálható a rendszer alapmegoldása. Akkor és nem alapvető változók.

A fő változókat nem alapváltozókkal kifejezve azt kapjuk

Következésképpen a változóknak ez az alap- és nem-alapfelosztása megfelel az alapmegoldásnak , ami érvénytelen (két változó negatív), ezért nem optimális. Ettől az alapmegoldástól kezdve továbblépünk egy továbbfejlesztett megoldás felé.

Annak eldöntéséhez, hogy melyik változót vigyük át kisebbről fundamentálisra, vegyük figyelembe az utóbbi rendszer két elérhető egyenletét negatív szabad tagokkal, például a másodikat. Megmutatja, hogy és főváltozókká alakíthatók, mivel ebben az egyenletben pozitív együtthatókkal rendelkeznek (tehát ha növekednek, és ez megtörténik, ha bármelyiket főváltozóvá alakítjuk, akkor a változó növekszik).

Próbáljuk meg lefordítani a fő változóba. Annak megállapításához, hogy melyik változót kell alapról nem alapra konvertálni, a rendszer szabad tagjainak az együtthatókhoz viszonyított legkisebb arányának abszolút értékét kapjuk meg. Nekünk van. A harmadik egyenletből kapjuk, amely azt mutatja, hogy az eredeti alapmegoldásban pozitív változót nem alapváltozóvá kell konvertálni. Ebből következően a kapott alapmegoldás az eredetihez hasonlóan két negatív komponenst is tartalmaz, vagyis egy ilyen alapmegoldásra való átálláskor nem lesz javulás.

A cérnából, gombokból és anyagból háromféle inget készítenek. A cérna-, gomb- és szövetkészleteket, valamint egy ing varrásához felhasznált normákat a táblázat tartalmazza. Keresse meg a maximális profitot és az azt biztosító optimális termékgyártási tervet (találjon).

ing 1

ing 2

ing 3

Tartalékok

szálak (m.)

1

9

3

96

gombok (db)

20

10

30

640

textil (

1

2

2

44

Profit (r.)

2

5

4

A probléma megoldása

Modellépület

Az 1., 2. és 3. típusú, kiadásra szánt ingek száma és száma.

Ezután az erőforrás-korlátozások így fognak kinézni:

Ráadásul a feladat értelmének megfelelően

A kapott nyereséget kifejező objektív függvény:

A következő lineáris programozási problémát kapjuk:

Lineáris programozási probléma kanonikus formára redukálása

Csökkentsük a problémát kanonikus formára. Vezessünk be további változókat. Az összes további változót nullával egyenlő együtthatóval vezetjük be a célfüggvénybe. A korlátozások bal oldalára további változókat adunk, amelyeknek nincs preferált formája, és egyenlőségeket kapunk.

A feladat megoldása szimplex módszerrel

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

Mivel a feladatot maximálisan oldjuk meg, a negatív számok jelenléte az indexsorban a feladat maximális megoldása során azt jelzi, hogy nem kaptuk meg az optimális megoldást, és a 0. iteráció táblázatából át kell lépni a a következő.

Folytatjuk a következő iterációt a következőképpen:

vezető oszlop megfelel

A kulcssort a szabad tagok és a vezető oszlop tagjainak minimális aránya határozza meg (szimplex relációk):

A kulcsoszlop és a kulcssor metszéspontjában találjuk az engedélyező elemet, azaz. 9.

Most folytatjuk az 1. iteráció összeállítását: Az egységvektor helyett a vektort vezetjük be.

Az új táblázatban az engedélyező elem helyére 1-et írunk, a kulcsoszlop összes többi eleme nulla. A kulcskarakterlánc-elemek az engedélyezési elemre vannak osztva. A táblázat összes többi eleme a téglalapszabály alapján kerül kiszámításra.

Az 1. iteráció kulcsoszlopa megfelel a

A feloldó elem a 4/3 szám. A vektort a bázisból származtatjuk, és helyette bevezetjük a vektort. Megkapjuk a 2. iteráció táblázatát.

A 2. iteráció kulcsoszlopa megfelel a

Megtaláljuk a kulcssort, ehhez definiáljuk:

A feloldó elem a 10/3. A vektort a bázisból származtatjuk, és helyette bevezetjük a vektort. Megkapjuk a 3. iteráció táblázatát.

№

BP

c B

A o

x 1

x 2

x 3

x 4

x 5

x 6

Simplex

2

5

4

0

0

0

kapcsolat

0

x 4

0

96

1

9

3

1

0

0

32/3

x 5

0

640

20

10

30

0

1

0

64

x 6

0

44

1

2

2

0

0

1

22

F j - c j

0

-2

-5

-4

0

0

0

1

x 2

5

32/3

1/9

1

1/3

1/9

0

0

32

x 5

0

1600/3

170/9

0

80/3

-10/9

1

0

20

x 6

0

68/3

7/9

0

4/3

-2/9

0

1

17

F j - c j

160/3

-13/9

0

-7/3

5/9

0

0

2

x 2

5

5

-1/12

1

0

1/6

0

-1/4

--

x 5

0

80

10/3

0

0

10/3

1

-20

24

x 3

4

17

7/12

0

1

-1/6

0

3/4

204/7

F j - c j

93

-1/12

0

0

1/6

0

7/4

3

x 2

5

7

0

1

0

1/4

1/40

-3/4

x 1

2

24

1

0

0

1

3/10

-6

x 3

4

3

0

0

1

-3/4

-7/40

17/4

F j - c j

95

0

0

0

1/4

1/40

5/4

Az index sorban minden tag nem negatív, így a lineáris programozási feladatra a következő megoldást kapjuk (a szabad kifejezések oszlopából írjuk ki):

24 1. típusú inget, 7 2. típusú inget és 3 3. típusú inget szükséges varrni. Ebben az esetben a kapott nyereség maximális lesz, és 95 rubel lesz.

Egy lineáris programozási feladat megoldására van szükség.

Objektív funkció:

2x 1 +5x 2 +3x 3 +8x 4 →min

Korlátozó feltételek:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x1 -13x2 +10x3 +5x4 ≥6
3x 1 +7x 2 +x 3 ≥1

Hozzuk a megszorítások rendszerét kanonikus formába, ehhez az egyenlőtlenségektől az egyenlőségek felé kell elmozdulni, további változók hozzáadásával.

Mivel a mi problémánk egy minimalizálási probléma, át kell alakítanunk maximum keresési problémává. Ehhez a célfüggvény együtthatóinak előjeleit az ellenkezőjére változtatjuk. Az első egyenlőtlenség elemeit változatlanul írjuk, hozzáadunk egy további x 5 változót, és a „≤” jelet „=”-re változtatjuk. Mivel a második és a harmadik egyenlőtlenség „≥” előjelű, ezért együtthatóik előjelét az ellenkezőjére kell változtatni, és további x 6 és x 7 változókat kell bevinni beléjük. Ennek eredményeként egy ekvivalens problémát kapunk:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x1 +13x2 -10x3 -5x4 +x6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

Folytatjuk a kezdeti szimplex tábla kialakítását. Az ellentétes előjelű célfüggvény együtthatóit a táblázat F sorába írjuk be.

					Ingyenes tag
F
X5
X6
X7

Az általunk összeállított táblázatban a szabad tagok oszlopában vannak negatív elemek, ezek között találjuk a moduluszban kifejezett maximumot - ez az elem: -6, ez állítja be a vezető sort - X6. Ebben a sorban találjuk a maximális negatív elemet is modulusban: -10 ez az X3 oszlopban található, ami a vezető oszlop lesz. A bevezető sorban lévő változó kikerül a bázisból, a vezető oszlopnak megfelelő változó pedig bekerül a bázisba. Számoljuk újra a szimplex táblát:

	X1	X2	X6	X4	Ingyenes tag
F	0.8	8.9	0.3	6.5	-1.8
X5	4.6	0.8	-0.4	3	14.4
X3	0.4	-1.3	-0.1	0.5	0.6
X7	-2.6	-8.3	-0.1	0.5	-0.4

Az általunk összeállított táblázatban a szabad tagok oszlopában negatív elemek találhatók, ezek között találjuk a moduluszban kifejezett maximumot - ez az elem: -0,4, beállítja a vezető sort - X7. Ebben a sorban találjuk a modulusban mért maximális negatív elemet is: -8.3 az X2 oszlopban található, ami a vezető oszlop lesz. A bevezető sorban lévő változó kikerül a bázisból, a vezető oszlopnak megfelelő változó pedig bekerül a bázisba. Számoljuk újra a szimplex táblát:

	X1	X7	X6	X4	Ingyenes tag
F	-1.988	1.072	0.193	7.036	-2.229
X5	4.349	0.096	-0.41	3.048	14.361
X3	0.807	-0.157	-0.084	0.422	0.663
X2	0.313	-0.12	0.012	-0.06	0.048

Mivel a szabad kifejezések oszlopában nincsenek negatív elemek, ezért egy elfogadható megoldás született, az F sor negatív elemeket tartalmaz, ami azt jelenti, hogy a kapott megoldás nem optimális. Határozzuk meg a vezető oszlopot. Ehhez az F sorban megtaláljuk a maximális modulusú negatív elemet - ez -1,988 A vezető sor az lesz, amelynél a szabad tag és a vezető oszlop megfelelő elemének aránya minimális. A vezető sor X2, a vezető elem pedig: 0,313.

	X2	X7	X6	X4	Ingyenes tag
F	6.351	0.31	0.269	6.655	-1.924
X5	-13.895	1.763	-0.577	3.882	13.694
X3	-2.578	0.152	-0.115	0.577	0.539
X1	3.195	-0.383	0.038	-0.192	0.153

Mivel az F karakterláncban nincsenek negatív elemek, akkor
megtalálták az optimális megoldást. Mivel az eredeti feladat a minimum megkeresése volt, ezért az optimális megoldás az F karakterlánc ellentétes előjellel vett szabad tagja lesz. F=1,924
változó értékekkel egyenlő: x 3 = 0,539, x 1 = 0,153. Az x 2 és x 4 változók nem szerepelnek a bázisban, így x 2 =0 x 4 =0.

Hasonló cikkek