Mérlegeljük szimplex módszer lineáris programozási (LP) feladatok megoldására. Alapja az egyik referenciatervről a másikra való átmenet, amely során 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 kanonikus formává alakítjuk. A ≤ alakú egyenlőtlenségekhez további változókat vezetünk be (+), de ha ≥ alakú, akkor (-) elő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. A vektorok ki vannak írva P i 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 forrásadatok egy szimplex táblába kerülnek. 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 optimalitási jele, hogy a megoldás akkor optimális, ha benne van f– a sorban minden együttható pozitív. Az engedélyező oszlop megtalálásának szabálya - megtekintve f– egy karakterlánc és negatív elemei közül a legkisebb kerül kiválasztásra. Vektor P i 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 az a feloldóelem, amelyre nézve a szimplex tábla újraszámításra kerül. Az ezt az elemet tartalmazó sort engedélyezési sornak 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 folytatják az új szimplex tábla újraszámítását.
5. Új szimplex táblázat kitöltésének szabályai. A feloldó elem helyére egységet helyezünk, és a többi elemet egyenlőnek tekintjük 0 . A feloldó vektort hozzáadjuk a bázishoz, amelyből a megfelelő nulla vektort kizárjuk, és a fennmaradó bázisvektorokat változtatás nélkül írjuk. A felbontási karakterlánc elemeit felosztja a felbontási elemmel, a fennmaradó elemeket a téglalapszabály szerint újraszámolja.
6. Ez addig történik f– a karakterlánc minden eleme nem lesz pozitív.

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

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

Összeállítjuk a vektorokat:

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

:
Számoljuk ú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 sor egy negatív elemet tartalmaz – (-5/3), vektor P 1. Oszlopában egyetlen pozitív elemet tartalmaz, amely az engedélyező elem lesz. Számítsuk újra a táblázatot erre az elemre vonatkozóan:

Nincsenek negatív elemek f– a vonal azt jelenti, hogy megtaláltuk optimális terv:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. Lineáris programozás, M: Nauka, 1998,
• Ventzel E.S. Operations Research, M: Szovjet Rádió, 2001,
• Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Matematikai programozás, M: Higher School, 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

Az optimalizálási problémák megoldásának egyik módja ( általában a minimum vagy maximum megtalálásával járnak) lineáris programozásnak nevezzük. Simplex módszer magában foglalja a lineáris programozási problémák megoldására szolgáló algoritmusok és módszerek egész csoportját. Az egyik ilyen módszer, amely magában foglalja a forrásadatok rögzítését és egy speciális táblázatba történő újraszámítását, az úgynevezett táblázatos szimplex módszer.

Tekintsük a táblázatos szimplex módszer algoritmusát a megoldás példáján keresztül gyártási feladat, ami a maximális profitot biztosító termelési terv megtalálásában merül ki.

Bemeneti adatok a szimplex módszer problémájához

A cég 4 féle terméket gyárt, ezeket 3 gépen dolgozza fel.

A termékek gépi feldolgozásának időszabványait (perc/db) az A mátrix határozza meg:

A gép üzemidő alapja (min.) a B mátrixban van megadva:

Az egyes termékegységek értékesítéséből származó nyereséget (RUB/db) a C mátrix adja meg:

A termelési feladat célja

Készítsen termelési tervet, amely maximalizálja a vállalkozás nyereségét.

A feladat megoldása táblázatos szimplex módszerrel

(1) Jelölje X1, X2, X3, X4 az egyes típusok tervezett termékszámát. Aztán a kívánt terv:( X1, X2, X3, X4)

(2) Írjuk fel a terv kényszereit egyenletrendszer formájában:

(3) Ekkor a cél profit:

Vagyis a termelési terv teljesítéséből származó nyereségnek maximálisnak kell lennie.

(4) Az eredményül kapott feltételes szélsőségprobléma megoldásához az egyenlőtlenségrendszert egy lineáris egyenletrendszerre cseréljük úgy, hogy további nemnegatív változókat viszünk be ( X5, X6, X7).

(5) Fogadjuk el a következőket referenciaterv:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Írjuk be az adatokat szimplex asztal:

Az utolsó sorba írjuk be a célfüggvény együtthatóit és magát az értékét ellenkező előjellel;

(7) Válassza ki az utolsó sorban legnagyobb (modulo) egy negatív szám.

Számoljunk b = N / A_kiválasztott_oszlop_elemei

A b számított értékei közül választunk legkevésbé.

A kiválasztott oszlop és sor metszéspontja adja a feloldó elemet. A bázist a feloldó elemnek megfelelő változóra változtatjuk ( X5-től X1-ig).

• Maga a feloldó elem 1-re változik.
• A felbontási vonal elemeinél – a ij (*) = a ij / RE ( azaz minden elemet elosztunk a feloldó elem értékével és új adatokat kapunk).
• A felbontás oszlop elemei esetében egyszerűen nullázódik.
• A táblázat többi elemét a téglalapszabály segítségével újraszámoljuk.

a ij (*) = a ij – (A * B / RE)

Amint látható, az aktuális újraszámítás alatt álló cellát és a feloldó elemet tartalmazó cellát vesszük. A téglalap ellentétes sarkait alkotják. Ezután megszorozzuk ennek a téglalapnak a másik 2 sarkának celláiból származó értékeket. Ez a munka ( A * B) ossza el a feloldóelemmel ( RE). És ki kell vonni az aktuális újraszámítás alatt álló cellából ( a ij) mi történt. Új értéket kapunk - a ij (*).

(9) Ellenőrizze újra az utolsó sort ( c) bekapcsolva negatív számok jelenléte. Ha nincsenek ott, akkor az optimális tervet megtaláltuk, továbblépünk a probléma megoldásának utolsó szakaszába. Ha van, akkor a terv még nem optimális, és a szimplex táblát újra kell számolni.

Mivel ismét negatív számok vannak az utolsó sorban, elkezdjük a számítások új iterációját.

(10) Mivel az utolsó sorban nincsenek negatív elemek, ez azt jelenti, hogy megtaláltuk az optimális gyártási tervet! Nevezetesen: azokat a termékeket gyártjuk, amelyek az „Alap” oszlopba kerültek - X1 és X2. Ismerjük az egyes kibocsátási egységek előállításából származó nyereséget ( C mátrix). Marad az 1. és 2. termék talált gyártási mennyiségét megszorozzuk 1 darabonkénti haszonnal, megkapjuk a végső ( maximális! ) adott termelési terv nyeresége.

VÁLASZ:

X1 = 32 db, X2 = 20 db, X3 = 0 db, X4 = 0 db.

P = 48 * 32 + 33 * 20 = 2196 dörzsölje.

Galyautdinov R.R.

© Az anyagok másolása csak akkor megengedett, ha közvetlen hiperhivatkozás van rá

Egy példa egy probléma megoldására szimplex módszerrel, valamint egy példa egy kettős probléma megoldására.

Tartalom

Problémás állapot

Három árucsoport értékesítéséhez egy kereskedelmi vállalkozás háromféle korlátozott anyagi és pénzforrással rendelkezik b 1 = 240, b 2 = 200, b 3 = 160 egység összegben. Ugyanakkor 1 árucsoport értékesítéséhez 1 ezer rubelért. áruforgalom, az első típusú erőforrást a 11 = 2 egység, a második típusú erőforrást a 21 = 4 egység, a harmadik típusú erőforrást a 31 = mennyiségben fogyasztanak el. 4 egység. 2 és 3 árucsoport eladásához 1 ezer rubelért. a forgalom az első típusú erőforrás szerint a 12 = 3, a 13 = 6 egység, a második típusú erőforrása a 22 = 2, a 23 = 4 egység, a 23 = 4 egység a harmadik típus a 32 = 6, a 33 = 8 egység mennyiségben. Nyereség három árucsoport eladásából 1 ezer rubelért. a forgalom rendre c 1 = 4, c 2 = 5, c 3 = 4 (ezer rubel). Határozza meg a kereskedelmi forgalom tervezett volumenét és szerkezetét úgy, hogy a kereskedelmi vállalkozás profitja maximalizálva legyen.

A forgalomtervezés közvetlen problémájára, szimplex módszerrel oldják meg, komponálni kettős probléma lineáris programozás.
Telepítés konjugált változópárok közvetlen és kettős problémák.
Konjugált változópárok szerint a direkt probléma megoldásából kapjuk a kettős probléma megoldása, amelyben előállítják erőforrás felmérés, áru eladására költött.

A feladat megoldása szimplex módszerrel

Legyen x 1, x 2, x 3 az eladott áruk száma ezer rubelben, 1, 2, 3 csoportból. Ekkor a probléma matematikai modelljének alakja a következő:

F = 4 x 1 + 5 x 2 + 4 x 3 ->max

0)))(~)" title="delim(lbrace)(mátrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Megoldjuk a szimplex módszert.

További x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 változókat vezetünk be, hogy az egyenlőtlenségeket egyenlőséggé alakítsuk.

Vegyünk alapul x 4 = 240-et; x 5 = 200; x 6 = 160.

Beírjuk az adatokat szimplex asztal

Simplex táblázat 1. sz

Objektív funkció:

0 240 + 0 200 + 0 160 = 0

A becsléseket a következő képlet alapján számítjuk ki:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Mivel negatív becslések vannak, a terv nem optimális. Legalacsonyabb pontszám:

Bevezetjük az x 2 változót a bázisba.

Az alapból kilépő változót definiáljuk. Ehhez megtaláljuk a legkisebb nem negatív arányt az x2 oszlophoz.

= 26.667

Legkisebb nem negatív: Q 3 = 26,667. Az x 6 változót a bázisból származtatjuk

Osszuk el a 3. sort 6-tal.
Az 1. sorból vonjuk ki a 3. sort, megszorozzuk 3-mal
A 2. sorból vonjuk ki a 3. sort, megszorozzuk 2-vel

Kiszámoljuk:

Kapunk egy új táblázatot:

Simplex táblázat 2. sz

Objektív funkció:

0 160 + 0 440/3 + 5 80/3 = 400/3

A becsléseket a következő képlet alapján számítjuk ki:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

Mivel van negatív becslés Δ 1 = - 2/3, a terv nem optimális.

Az x 1 változót bevisszük a bázisba.

Az alapból kilépő változót definiáljuk. Ehhez megtaláljuk az x 1 oszlop legkisebb nem negatív arányát.

Legkisebb nemnegatív: Q 3 = 40. Az x 2 változót a bázisból származtatjuk

Osszuk el a 3. sort 2/3-dal.
A 2. sorból vonja ki a 3. sort, szorozva 8/3-mal

Kiszámoljuk:

Kapunk egy új táblázatot:

Simplex táblázat 3. sz

Objektív funkció:

0 160 + 0 40 + 4 40 = 160

A becsléseket a következő képlet alapján számítjuk ki:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1

Mivel nincs negatív értékelés, a terv optimális.

Megoldás a problémára:

x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160

Vagyis az első típusú árut 40 ezer rubel értékben kell eladni. A 2. és 3. típusú termékeket nem kell értékesíteni. Ebben az esetben a maximális nyereség F max = 160 ezer rubel lesz.

A kettős probléma megoldása

A kettős probléma formája a következő:

Z = 240 év 1 + 200 év 2 + 160 év 3 -> perc

Title="delim(lbrace)(mátrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

További y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 változókat vezetünk be, hogy az egyenlőtlenségeket egyenlőséggé alakítsuk.

A direkt és duális problémák konjugált változópárjai a következő formájúak:

A direkt probléma utolsó szimplex táblájából 3. találjuk meg a megoldást a duális feladatra:

Z min = Fmax = 160;
y 1 = A 4 ​​= 0; y2=A5=0; y3=A6=1; y4 = Δ1 = 0; y5 = Δ2 = 1; y6=A3=4;

Y 1 = 0; y2 = 0; y 3 = 1; Z min = 160;

11.4. DUAL SIMPLEX MÓDSZER

Az előző bekezdések eredményeiből az következik, hogy az eredeti probléma megoldásához áttérhetünk a kettősre, és annak optimális tervére vonatkozó becslések segítségével meghatározhatjuk az eredeti probléma optimális megoldását.

A duális feladatra nem szükséges áttérni, hiszen ha az első szimplex táblát tekintjük egységnyi többletbázissal, akkor könnyen észrevehető, hogy az eredeti feladat az oszlopokba, a duális pedig a sorokba kerül.

Amint látható, egy közvetlen probléma megoldása során bármely iterációnál a különbség, azaz nagyságrendű -a változó együtthatója, egyenlő a duális probléma megfelelő kényszerének jobb és bal oldala közötti különbséggel. Ha egy direkt probléma maximalizált célfüggvénnyel történő megoldása során az iteráció nem vezet optimális megoldáshoz, akkor legalább egy változóra és csak az összesre optimálisan különbség .

Ezt a feltételt figyelembe véve a kettősséget figyelembe véve írhatunk

.

Így ha, Azt . Ez azt jelenti, hogy ha a közvetlen probléma megoldása szuboptimális, akkor a kettős probléma megoldása nem kivitelezhető. A másik oldalon at . Ebből következik, hogy a közvetlen probléma optimális megoldása a kettős probléma elfogadható megoldásának felel meg.

Ez lehetővé tette a lineáris programozási problémák megoldására egy új módszer kidolgozását, amely először egy elfogadhatatlan, de „az optimálisnál jobb” megoldást ad (a szokásos szimplex módszernél először elfogadható, De szuboptimális megoldás). Az új módszer, az ún kettős szimplex módszer, biztosítja a megoldás optimálisságának feltételeinek teljesülését és szisztematikus „közelítését” a megvalósítható megoldások régiójához. Amikor a kapott megoldás megvalósíthatónak bizonyul, az iteratív számítási folyamat véget ér, mivel ez a megoldás is optimális.

A duális szimplex módszer lehetővé teszi olyan lineáris programozási problémák megoldását, amelyeknek a kényszerrendszerei pozitív alapon bármilyen előjelű szabad tagokat tartalmaznak. Ezzel a módszerrel csökkenthető a kényszerrendszer transzformációinak száma, valamint a szimplex tábla mérete. Tekintsük a duális szimplex módszer alkalmazását egy példán keresztül.

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

korlátozások alatt

.

Térjünk át a kanonikus formára:

korlátozások alatt

A kezdeti szimplex tábla alakja

Alapvető változók	x 1	x 2	x 3	x 4	x 5	Megoldás
x 3 x 4 x 5	–3 –4	–1 –3				–3 –6
	–2	–1

Kezdeti alap megoldásoptimális, de nem elfogadható.

A szokásos szimplex módszerhez hasonlóan a vizsgált megoldási módszer is az elfogadhatósági és optimalitási feltételek alkalmazásán alapul.

Elfogadhatósági feltétel. Kizárt változóként a legnagyobb abszolút értékű negatív alapváltozó kerül kiválasztásra (ha vannak alternatívák, a választás tetszőlegesen történik). Ha az összes bázisváltozó nem negatív, a számítási folyamat véget ér, mivel a kapott megoldás megvalósítható és optimális.

Állapot optimalitás. A bázisban szereplő változót a nem alapváltozók közül választjuk ki az alábbiak szerint. A bal oldali együtthatók arányait számítjuk ki-egyenletek a kizárt változóhoz tartozó egyenlet megfelelő együtthatóihoz. A pozitív vagy nulla nevezővel rendelkező arányokat a rendszer nem veszi figyelembe. A minimalizálási feladatban a bemeneti változónak a megadott arányok közül a legkisebbnek, a maximalizálási feladatban pedig annak az aránynak kell megfelelnie, amelyik abszolút értékben a legkisebb (ha vannak alternatívák, a választás tetszőlegesen történik). Ha az összes arány nevezője nulla vagy pozitív, akkor a problémának nincs megvalósítható megoldása.

A bázisban szereplő és a következő megoldáshoz kizárt változók kiválasztása után a szimplex tábla sorainak szokásos konvertálási műveletét hajtjuk végre.

Ebben a példában a kizárt változó az. Az új bázisváltozó meghatározásához számított arányokat a következő táblázat tartalmazza:

Változók	x 1	x 2	x 3	x 4	x 5
Egyenlet x 4 - egyenlet	–2 –4	–1 –3
Hozzáállás

A benne foglalt változó ki van választva x 2. A következő karakterlánc-konverzió egy új szimplex táblát eredményez:

Alapvető változók	x 1	x 2	x 3	x 4	x 5	Megoldás
x 3 x 2 x 5						–1 –1

Új megoldás szintén optimális, de még mindig elfogadhatatlan. Új kizárt változóként választjuk (tetszőlegesen) x 3. Határozzuk meg a felvenni kívánt változót.

Változók	x 1	x 2	x 3	x 4	x 5
Egyenlet x 4 - egyenlet
hozzáállás

Fő egy szimplex módszer ötlete a problémák megoldására a ZLP támogató megoldásainak következetes fejlesztéséből áll.

A szimplex metódus írásának többféle formája van.

1. A szimplex módszer rögzítésének alapformája;
2. Simplex módszer szimplex táblázat formájában;
3. Módosított szimplex módszer;
4. Szimplex módszer oszlopos formában;
5. Simplex módszer vonalas formában.

Határozzuk meg az F(X) = 3x 1 +5x 2 +4x 3 célfüggvény maximális értékét a következő kényszerfeltételek mellett.
0,1x1 +0,2x2 +0,4x3 ≤1100
0,05x1 +0,02x2 +0,02x3 ≤120
3x 1 +x 2 +2x 3 ≤8000

Az első referenciaterv elkészítéséhez az egyenlőtlenségrendszert egyenletrendszerré redukáljuk további változók bevezetésével (átmenet a kanonikus formára).
0,1x1 + 0,2x2 + 0,4x3 + 1x4 + 0x5 + 0x6 = 1100
0,05x1 + 0,02x2 + 0,02x3 + 0x4 + 1x5 + 0x6 = 120
3x 1 + 1x 2 + 2x 3 + 0x 4 + 0x 5 + 1x 6 = 8000

A szimplex módszer rögzítésének alapformája

A megoldást úgy hajtjuk végre, hogy az alapvető változókat nem alapváltozókkal fejezzük ki: x 0 = 3x1 +5x2 +4x3 x 4 = 1100-0,1 x 1 - 0,2 x 2 - 0,4 x 3 x 5 = 120-0,05x1 -0,02x2 -0,02x3 x 6 = 8000-3x 1 -x 2 -2x 3

Simplex módszer szimplex táblázat formájában

A megoldást szimplex táblázat formájában mutatjuk be. Az űrlap számítógépes számításokhoz készült. Mesterséges alap használatakor speciális M számot használnak (általában 10000).

Terv	Alap	IN	x 1	x 2	x 3	x 4	x 5	x 6	min
1	x4	1100	0.1	0.2	0.4	1	0	0	5500
	x5	120	0.05	0.02	0.02	0	1	0	6000
	x6	8000	3	1	2	0	0	1	8000
Indexsor	F(X1)	0	-3	-5	-4	0	0	0	0
2	x2	5500	0.5	1	2	5	0	0	11000
	x5	10	0.04	0	-0.02	-0.1	1	0	250
	x6	2500	2.5	0	0	-5	0	1	1000
Indexsor	F(X2)	27500	-0.5	0	6	25	0	0	0
3	x2	5375	0	1	2.25	6.25	-12.5	0	11000
	x1	250	1	0	-0.5	-2.5	25	0	250
	x6	1875	0	0	1.25	1.25	-62.5	1	1000
Indexsor	F(X3)	27625	0	0	5.75	23.75	12.5	0	0

Módosított szimplex módszer

Együtthatómátrix A = a ij Mátrix b. Iteráció #1. = (4, 5, 6) Mátrix c. c = (-3, -5, -4, 0, 0, 0) c B = (0, 0, 0) c N = (-3, -5, -4) Kiszámoljuk: A B -1 mátrixot algebrai összeadásokkal számítjuk ki. u = c B B -1 = (0, 0, 0)

Szimplex módszer oszlopos formában

Térjünk át a szimplex módszer oszlopos alakjára. Fejezzük ki az egyes változókat a nem alapvető változókkal. x 0 = 0-3 (-x 1) -5 (-x 2) -4 (-x 3) + 0 (-x 4) + 0 (-x 5) + 0 (-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x1)-1(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6) x 3 = 0+0(-x1)+0(-x2)-1(-x3)+0(-x4)+0(-x5)+0(-x6) x 4 = 1100+0,1 (-x 1) + 0,2 (-x 2) + 0,4 (-x 3) + 1 (-x 4) + 0 (-x 5) + 0 (-x 6) x 5 = 120+0,05 (-x 1) + 0,02 (-x 2) + 0,02 (-x 3) + 0 (-x 4) + 1 (-x 5) + 0 (-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) Ez a rendszer a T 0 táblázatnak felel meg. 0 -1 0 0 0 0 -1 0 0 0 0 -1 1100 0.1 0.2 0.4 120 0.05 0.02 0.02 8000 3 1 2 0 -3 -5 -4

Simplex módszer soros formában

Kezdő megengedhető bázisként B 0 =-t vehetünk fel<4, 5, 6>. A következő táblázat megfelel majd ennek. 1100 0.1 0.2 0.4 1 0 0 120 0.05 0.02 0.02 0 1 0 8000 3 1 2 0 0 1 0 -3 -5 -4 0 0 0

A rendszer együtthatóiból felépített Q mátrixot ún szimplex asztal, amely a B bázisnak felel meg. A szimplex tábla ún elfogadható, vagy közvetlenül elfogadható, ha q i0 ≥ 0. A Q szimplex tábla utolsó sorának q i0 elemeit ún. relatív becslések.

Megoldási formák mesterséges bázis módszerrel

A célfüggvénybe bevitt mesterséges változók használatára úgynevezett M büntetést szabnak ki, ami egy nagyon nagy pozitív szám, amelyet általában nem adnak meg.
A kapott bázist mesterségesnek, a megoldási módszert pedig mesterséges bázismódszernek nevezzük.
Ráadásul a mesterséges változók nem kapcsolódnak a probléma tartalmához, hanem lehetővé teszik egy kiindulási pont megalkotását, és az optimalizálási folyamat arra kényszeríti ezeket a változókat, hogy nulla értéket vegyenek fel, és biztosítsák az optimális megoldás elfogadhatóságát.

Megoldási formák mesterséges bázis módszerrel:

1. M-módszer (szimplex táblázat);
2. kétlépcsős vagy kétfázisú szimplex módszer (Alap rögzítési forma, Módosított szimplex módszer, Szimplex módszer oszlopos formában, Simplex módszer vonalas formában).