Online metóda umelej bázy s podrobným riešením. Riešenie úloh lineárneho programovania metódou umelej bázy

x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

≤ = ≥

≤ = ≥

≤ = ≥

×

Varovanie

Vymazať všetky bunky?

Zavrieť Vymazať

Pokyny na zadávanie údajov.Čísla sa zadávajú ako celé čísla (príklady: 487, 5, -7623 atď.), desatinné čísla (napr. 67., 102,54 atď.) alebo zlomky. Zlomok je potrebné zadať v tvare a / b, kde a a b (b> 0) sú celé čísla alebo desatinné čísla... Príklady 45/5, 6,6 / 76,4, -7 / 6,7 atď.

Simplexná metóda

Príklady riešenia simplexnej metódy LPP

Príklad 1. Vyriešte nasledujúci problém lineárne programovanie:

Pravá časť Obmedzenia sústavy rovníc majú tvar:

Zapíšme si aktuálny základný plán:

Tento základný plán nie je optimálny, keďže v posledný riadok existujú negatívne prvky. Najväčší záporný prvok v absolútnej hodnote (-3), preto základ zahŕňa vektor X pri . min(40: 6, 28: 2) = 20/3 zodpovedá riadku 1. Vektor vychádza zo základu X 3. Urobme pre stĺpec Gaussovu elimináciu X 2, berúc do úvahy, že pivot zodpovedá riadku 1. Vynulujme všetky prvky tohto stĺpca okrem pivota. Ak to chcete urobiť, pridajte riadky 2, 3, 4 s riadkom 1 vynásobeným -1/3, 1/6, 1/2. Ďalej čiaru s pivotom rozdelíme pivotom.

Tento základný plán nie je optimálny, pretože posledný riadok obsahuje záporný prvok (-3), preto základ zahŕňa vektor X 1. Určte, ktorý vektor opúšťa základ. Aby sme to dosiahli, vypočítame pri ... min (44/3: 11/3, 62/3: 5/3) = 4 zodpovedá riadku 2. Zo zákl. X 4. Urobme pre stĺpec Gaussovu elimináciu X 1, za predpokladu, že pivot zodpovedá riadku 2. Vynulujte všetky prvky v tomto stĺpci, okrem pivota. Za týmto účelom pridajte riadky 1, 3, 4 s riadkom 2 vynásobeným 1/11, -5/11, 9/11. Ďalej čiaru s pivotom rozdelíme pivotom.

Simplexná tabuľka bude vyzerať takto:

Aktuálny základný plán je optimálny ako v riadkoch 4 pod premennými žiadne negatívne prvky.

Riešenie možno napísať takto: .

Hodnota účelovej funkcie v danom bode: F(X)=.

Príklad 2. Nájdite maximum funkcie

Riešenie.

Základné vektory X 4 , X 3, teda všetky položky v stĺpcoch X 4 , X 3 nižšie horizontálna čiara by mala byť nula.

Nastavte všetky prvky stĺpca na nulu X 4, s výnimkou otočného prvku. Ak to chcete urobiť, pridajte riadok 3 s riadkom 1 vynásobeným 4. Vynulujte všetky prvky stĺpca X 3, s výnimkou otočného prvku. Za týmto účelom pridajte riadok 3 k riadku 2 krát 1.

Simplexná tabuľka bude mať tvar:

Tento základný plán nie je optimálny, pretože posledný riadok obsahuje záporný prvok (-11), preto základ zahŕňa vektor X 2. Určte, ktorý vektor opúšťa základ. Aby sme to dosiahli, vypočítame pri ... Preto je účelová funkcia zhora neobmedzená. Tie. problém lineárneho programovania je neriešiteľný.

Príklady riešenia LPP metódou umelej bázy

Príklad 1. Nájdite maximum funkcie

Riešenie. Keďže počet základných vektorov by mal byť 3, pridáme umelú premennú a in cieľová funkcia pridajte túto premennú vynásobenú −M, kde M je veľmi veľké číslo:

Matica koeficientov sústavy rovníc má tvar:

Bázové vektory, preto všetky prvky v stĺpcoch pod vodorovnou čiarou musia byť nulové.

Vynulujte všetky prvky v stĺpci okrem pivota. Ak to chcete urobiť, pridajte riadok 5 s riadkom 3 vynásobeným -1.

Simplexná tabuľka bude mať tvar:

Tento základný plán nie je optimálny, pretože v poslednom riadku sú negatívne prvky. Najväčší záporný prvok v absolútnej hodnote (-5), preto vektor vstupuje do bázy. Určte, ktorý vektor opúšťa bázu. Aby sme to dosiahli, vypočítame pri zodpovedá riadku 3. Vektor opúšťa základ Urobme pre stĺpec Gaussovu elimináciu, berúc do úvahy, že prvok pivot zodpovedá riadku 3. Vynulujte všetky prvky tohto stĺpca okrem pivotu. Ak to chcete urobiť, pridajte riadky riadok 5 s riadkom 3 vynásobeným 1. Ďalej rozdeľte riadok s pivotom pivotom.

Simplexná tabuľka bude vyzerať takto:

Tento základný plán nie je optimálny, pretože v poslednom riadku sú negatívne prvky. Najväčší záporný prvok v absolútnej hodnote (-3), preto vektor vstupuje do základu. Určte, ktorý vektor opúšťa základ. Aby sme to dosiahli, vypočítame pri zodpovedá riadku 1. Vektor vychádza zo základu X 2. Urobme pre stĺpec Gaussovu elimináciu X 1, za predpokladu, že pivot zodpovedá riadku 1. Vynulujte všetky prvky v tomto stĺpci okrem pivota. Za týmto účelom pridajte riadky 2, 3, 4 s riadkom 1 vynásobeným 3/2, -1/10, 3/2. Ďalej čiaru s pivotom rozdelíme pivotom.

Simplexná tabuľka bude vyzerať takto:

Tento základný plán nie je optimálny, pretože v poslednom riadku sú negatívne prvky. Najväčší záporný prvok v absolútnej hodnote (-13/2), preto základ zahŕňa vektor X 3. Určte, ktorý vektor opúšťa základ. Aby sme to dosiahli, vypočítame pri zodpovedá riadku 3. Vektor vychádza zo základu X 5. Urobme pre stĺpec Gaussovu elimináciu X 3, berúc do úvahy, že pivot zodpovedá riadku 3. Vynulujme všetky prvky tohto stĺpca okrem pivota. Ak to chcete urobiť, pridajte riadky 1, 2, 4 s riadkom 3 vynásobeným 5/3, 25/9, 65/9. Ďalej čiaru s pivotom rozdelíme pivotom.

Simplexná tabuľka bude vyzerať takto:

Aktuálny východiskový plán je optimálny, pretože pod premennými v riadkoch 4-5 nie sú žiadne záporné položky.

Riešenie pôvodný problém dá sa napísať takto:

Príklad 2. Nájdite optimálny plán pre problém lineárneho programovania:

Matica koeficientov sústavy rovníc má tvar:

Základné vektory X 4 , X 5 , X 6, teda všetky položky v stĺpcoch X 4 , X 5 , X 6, pod vodorovnou čiarou by mala byť nula.

Nastavte všetky prvky stĺpca na nulu X 4, s výnimkou otočného prvku. Ak to chcete urobiť, pridajte riadok 4 k riadku 1 vynásobenému -1. Nastavte všetky prvky stĺpca na nulu X 5, s výnimkou otočného prvku. Ak to chcete urobiť, pridajte riadok 5 k riadku 2 vynásobenému -1. Nastavte všetky prvky stĺpca na nulu X 6, s výnimkou otočného prvku. Ak to chcete urobiť, pridajte riadok 5 s riadkom 3 vynásobeným -1.

Simplexná tabuľka bude mať tvar:

Na riadku 5 prvky zodpovedajúce premenným X 1 , X 2 , X 3 , X 4 , X 5 , X 6 sú nezáporné a číslo na priesečníku daného riadka a stĺpca X 0 je záporné. Potom pôvodný problém nemá základnú líniu. Preto je nerozpustný.

+

			x 1	-	2	x 2	+		S 1							=	2
		2	x 1	3	x 2				-		S 2				=	4
	-	2	x 1	+		x 2							+		S 3	=	2

Premenná sa nazýva základná pre danú rovnicu, ak vstupuje do danej rovnice s koeficientom jedna a nevstupuje do zostávajúcich rovníc (za predpokladu, že na pravej strane rovnice je kladné číslo).
Ak je v každej rovnici základná premenná, potom sa hovorí, že systém má základ.
Premenné, ktoré nie sú základné, sa nazývajú voľné premenné. (pozri systém nižšie)

Myšlienkou simplexovej metódy je prejsť z jedného základu na druhý, pričom sa získa hodnota funkcie, aspoň nie väčšia ako dostupná (každá základňa zodpovedá jedinej hodnote funkcie).
Je zrejmé, že počet všetkých možných základov pre akýkoľvek problém je konečný (a nie príliš veľký).
Preto skôr či neskôr dostane odpoveď.

Ako prebieha prechod z jedného základu na druhý?
Výhodnejšie je riešenie zaznamenať vo forme tabuliek. Každý riadok je ekvivalentný rovnici systému. Zvýraznený riadok pozostáva z koeficientov funkcie (porovnajte sami). Odpadá tak potreba zakaždým prepisovať premenné, čo výrazne šetrí čas.
Vo zvýraznenom riadku vyberte najmenší záporný koeficient. Je to potrebné na získanie hodnoty funkcie, aspoň nie vyššej ako je dostupná hodnota.
Stĺpec vybratý.
Pre kladné koeficienty zvoleného stĺpca zvážte pomer Θ a zvoľte najmenšiu hodnotu. Je to potrebné, aby stĺpec voľných členov zostal po transformácii kladný.
Vybratý riadok.
Následne bol určený prvok, ktorý bude základný. Potom počítame.

+

x 1

-

2

x 2

+

S 1

=

2

2

x 1

3

x 2

-

S 2

+

R 1

=

4

-

2

x 1

+

x 2

+

S 3

=

2

x 1 = 0 x 2 = 0 S2 = 0 S1 = 2 S3 = 2 R1 = 4

=> W = 4

Krok 1

x 1	x 2	S 1	S 2	S 3	R 1	St. členom	Θ
1	-2	1	0	0	0	2
2	3	0	-1	0	1	4	4: 3 ≈ 1,33
-2	1	0	0	1	0	2	2: 1 = 2
-2	-3	0	1	0	0	W - 4
1	-2	1	0	0	0	2
2/3	1	0	-1/3	0	1/3	4/3
-2	1	0	0	1	0	2
-2	-3	0	1	0	0	W - 4
7/3	0	1	-2/3	0	2/3	14/3
2/3	1	0	-1/3	0	1/3	4/3
-8/3	0	0	1/3	1	-1/3	2/3
0	0	0	0	0	1	W - 0

+

7/3

x 1

+

S 1

-

2/3

S 2

=

14/3

2/3

x 1

+

x 2

-

1/3

S 2

=

4/3

-

8/3

x 1

1/3

S 2

+

S 3

=

2/3

4. Nájdenie najmenšej hodnoty funkcie F.
Krok 1

x 1	x 2	S 1	S 2	S 3	St. členom	Θ
7/3	0	1	-2/3	0	14/3	14/3: 7/3 = 2
2/3	1	0	-1/3	0	4/3	4/3: 2/3 = 2
-8/3	0	0	1/3	1	2/3
-7/3	0	0	5/3	0	F - 20/3
1	0	3/7	-2/7	0	2
2/3	1	0	-1/3	0	4/3
-8/3	0	0	1/3	1	2/3
-7/3	0	0	5/3	0	F - 20/3
1	0	3/7	-2/7	0	2
0	1	-2/7	-1/7	0	0
0	0	8/7	-3/7	1	6
0	0	1	1	0	F - 2

S1 = 0 S2 = 0 x 1 = 2 x 2 = 0 S 3 = 6

=> F - 2 = 0 => F = 2

Medzi vybranými riadkovými koeficientmi nie sú žiadne záporné koeficienty. Preto sa nájde najmenšia hodnota funkcie F.

Metóda umelý základ(M-problém).

Pre mnoho problémov lineárneho programovania, napísaných vo forme hlavného problému a majúcich referenčné plány, medzi Pj vektormi nie je vždy m jednotkových vektorov.

Zvážte nasledujúci problém:

Nech je potrebné nájsť maximum funkcie

F = c 1 X 1 + c 2 X 2 + ……+ c n X n (1)

za podmienok

……………………………………… (2)

kde b i  0 ( i= l, m), m<.>n a medzi vektormi P1, P2, ..., Pn nie je m jednotkových vektorov.

Definícia... Úloha určiť maximálnu hodnotu funkcie

F= c 1 X 1 + c 2 X 2 + ……+ c n X n -MX n +1 - ... - MX n + m (3)

za podmienok

……………………………………… (4)

kde M je nejaké dostatočne veľké kladné číslo, ktorého konkrétna hodnota zvyčajne nie je špecifikovaná, sa nazýva rozšírený problém (M-problém) vzhľadom na problém (1) - (2).

Rozšírený problém má základnú líniu

X = (0; 0; ...; 0; b1; b 2 ; ...; b m).

určená sústavou jednotkových vektorov P n +1; R n + 2 , … R n + t , tvoriaci základ m-ro vektorového priestoru, ktorý je tzv umelé. Samotné vektory, ako aj premenné X n + i ( i= l, m), sa volajú umelé. Keďže rozšírený problém má základný plán, jeho riešenie možno nájsť pomocou simplexnej metódy.

Veta Ak v optimálnom pláne X * = ( X * 1 , X* 2 , ...; X* n , X* n +1 ; ...; X* n + m) rozšírená úloha (3) - (4) hodnoty umelých premenných X* n + i = 0 ( i=1, m), potom X * = ( X * 1 , X* 2 , ...; X* n) je optimálny plán úloh (1) - (2).

Ak sa teda v nájdenom optimálnom pláne rozšíreného problému hodnoty umelých premenných rovnajú nule, získa sa optimálny plán pôvodného problému.

Hodnoty riadku indexu ∆ 0, ∆ 1,…, ∆ n pozostávajú z dvoch častí, z ktorých jedna závisí od M, a druhý nie. Vyplňte simplex – tabuľku, ktorá obsahuje o jeden riadok viac ako bežná simplexná tabuľka. V tomto prípade (m + 2) riadok obsahuje koeficienty M, a v (m + 1) - termínoch, ktoré neobsahujú M. Pri prechode z jedného referenčného plánu do druhého sa do základu zavedie vektor zodpovedajúci najväčšiemu v absolútnej hodnote záporné číslo(m + 2) riadok. Umelý vektor vylúčený z bázy nie je zaznamenaný v ďalšej simplexnej tabuľke. Prepočet simplexných tabuliek pri prechode z jedného základného plánu do druhého sa vykonáva podľa všeobecné pravidlá simplexná metóda.

Iteračný proces pozdĺž čiary (m + 2) -a pokračuje, kým:

buď nebudú zo základu vylúčené všetky umelé vektory;

alebo nie sú vylúčené všetky umelé vektory, ale (m + 2) riadok už neobsahuje žiadne záporné prvky v indexoch ∆ 1,…, ∆ n.

V prvom prípade základ zodpovedá nejakému základnému plánu pôvodného problému a určovanie jeho optimálneho plánu pokračuje v (m + 1) rade.

V druhom prípade, ak je hodnota ∆ 0 záporná, pôvodný problém nemá riešenie; ak ∆ 0 = 0, potom nájdený plán podpory pôvodného problému je degenerovaný a základ obsahuje aspoň jeden z vektorov umelej bázy.

Fázy hľadania riešenia problému (1) - (2)

metóda na umelom základe:

Rozšírený problém (3) - (4) je vytvorený.

Nájdite základný plán rozšírenej úlohy.

Zvyčajné výpočty simplexovej metódy vylučujú umelé premenné zo základu. V dôsledku toho sa buď nájde základný plán pôvodného problému (1) - (2), alebo sa zistí jeho nerozhodnuteľnosť.

Pomocou nájdeného podporného plánu problému (1) - (2) sa buď nájde optimálny plán pôvodného problému simplexovou metódou, alebo sa stanoví jeho nerozhodnuteľnosť.

Príklad.

Nájdite minimum funkcie F= - 2X 1 + 3X 2 - 6X 3 - X 4

NS S obmedzeniami:

2x 1 + x 2 -2x 3 + x 4 = 24

x 1 + 2x 2 + 4x 3 ≤22

x 1 - x 2 + 2 x 3 ≥ 10

X i ≥0, i=1,4

Riešenie.

Napíšme túto úlohu vo forme hlavnej úlohy: nájdite maximálnu funkciu F= 2X 1 - 3X 2 + 6X 3 + X 4

s obmedzeniami:

2x 1 + x 2 -2x 3 + x 4 = 24

x 1 + 2 x 2 + 4 x 3 + x 5 = 22

x 1 - x 2 + 2 x 3 - x 6 = 10

X i ≥0, i=1, 6

V sústave rovníc poslednej úlohy uvažujeme vektory z koeficientov pri neznámych:

Medzi vektormi P1, R 2 , … P 6 iba dve singly (P 4 a P 5). Preto v ľavá strana tretej rovnice systému obmedzení úlohy pridáme ďalšiu nezápornú premennú x 7 a zvážte rozšírený problém maximalizácie funkcie

F= 2X 1 - 3X 2 + 6X 3 + X 4 - Мх7

s obmedzeniami:

2x 1 + x 2 -2x 3 + x 4 = 24

x 1 + 2 x 2 + 4 x 3 + x 5 = 22

x 1 - x 2 + 2 x 3 - x 6 + x 7 = 10

Rozšírený problém má základnú líniu X = (0; 0; 0; 24; 22; 0; 10), určenú systémom troch jednotkových vektorov: P 4, P 5, P 7.

Koncept duálneho (konjugovaného) problému lineárneho programovania.

Stavebné pravidlá dvojitá úloha.

S každým problémom lineárneho programovania (LPP), ktorý sa nazýva duálny problém (alebo adjoint) vzhľadom na pôvodný problém, ktorý sa nazýva priamy.

Duálny problém je konštruovaný vo vzťahu k priamemu problému, napísaný v štandardnom tvare:

F = c 1 x 1 + c 2 x 2 +… + c n x n  max (3,6)

a 11 x 1 + a 12 x 2 +… + a 1n x n ≤ b 1,

a 21 x 1 + a 22 x 2 +… + a 2n x n ≤ b 2,

………………………………

a k1 x 1 + a k2 x 2 +… + a kn x n ≤ = b k, (3.7)

a k + 1,1 x 1 + a k + 1,2 x 2 +… + a k + 1, n x n = b k + 1,

………………………………

a m1 x 1 + a m2 x 2 +… + a mn x n = b m,

x j ≥ 0,, l≤ n (3,8)

Problém nájdenia minimálnej hodnoty funkcie

L = b 1 y 1 + b 2 y 2 +… + b m y m (3,9)

za podmienok

a 11 y 1 + a 12 y 2 +… + a m1 y m ≥ c 1

a 21 r 1 + a 22 r 2 +… + a m2 r m ≥ c 2

………………………………

1 l y 1 + a 2 l y 2 +… + a m l y m ≥ c l (3.10)

a l+1,1 r 1 + a l+1,2 y 2 + ... + a l+ 1, m y m = c l + 1

………………………………

a m1 y 1 + a m2 y 2 +… + a mn y m = c m

y i ≥ 0,, k ≤ m (3.11)

sa nazýva duálny vzhľadom na problém (3.6) - (3.8).

Pravidlá pre konštrukciu duálneho problému sú uvedené v tabuľke:

Štrukturálne charakteristiky ZLP	Problém lineárneho programovania
		Dvojaký
1. Objektívna funkcia	Maximalizácia (max.)	Minimalizácia (min)
2. Počet premenných	n premenných	Rovná sa počtu obmedzení priameho problému (3.7), y i, t.j. m
3. Počet obmedzení	m obmedzenia	Rovná sa počtu premenných priamej úlohy x j, teda n
4. Matica koeficientov v systéme obmedzení
5. Koeficienty premenných v účelovej funkcii	c 1, c 2, ..., c n	b 1, b 2, ..., b m
6. Pravá strana systému obmedzení	b 1, b 2, ..., b m	c 1, c 2, ..., c n
7. Značky v systéme obmedzení	a) x j ≥ 0- podmienka nezápornosti	j-té obmedzenie má znamienko "≥"
	b) premenná x j nepodlieha podmienke nezápornosti	j-té obmedzenie má znamienko "="
	v) i-té obmedzenie má znamienko "≤".	premenná y i ≥0
	d) i-té obmedzenie má znamienko "="	premenná y i nepodlieha podmienke nezápornosti

Poznámka

Priamy problém na maximum a duálny na minimum sú vzájomne duálne problémy. Preto môžeme problém (3.9) - (3.11) považovať za priamy LPP a problém (3.6) - (3.8) za jeho duálny problém. V tomto prípade ostávajú pravidlá pre budovanie duálneho LPP v platnosti len s tá zmenaže za minimálny problém sa považuje počiatočný.

Ak je pôvodný problém vyriešený pri max (min) a v systéme obmedzení) i-e ( j-f) obmedzenie má znamienko "≤" ("≥"), potom na zostavenie duálneho problému je potrebné:

a) buď vynásobte obe časti i th ( j-th) nerovnosť o (-1) a zmeňte znamienko na "≤" ("≥")

b) buď priniesť i-e ( j-f) obmedzenie rovnosti zavedením ďalšej premennej x n + i ≥0

Metódu umelej bázy (alebo metódu „M“) možno použiť na vyriešenie problému LP, ak má jej systém obmedzení okrem významových nerovností „≤“ význam nerovností „≥“ alebo striktné rovnosti. Zvážte problém LP v jeho najvšeobecnejšej forme.

Nájdite extrém funkcie

Algoritmus metódy "M".

1. Zo sústavy nerovníc prejdeme k sústave rovníc, pričom uvedieme ďalšie nezáporné premenné:

2. V obmedzeniach, v ktorých sa dodatočné nezáporné premenné zadávajú so znamienkom mínus alebo nevstupujú vôbec, sa zavádzajú takzvané umelé premenné:

3. Súčet umelých premenných sa zavedie do lineárneho tvaru (1.26) s koeficientom M > 0. Aby umelé premenné neboli obsiahnuté v optimálnom pláne pôvodného problému, koeficient M je priradený ľubovoľne veľký význam v porovnaní s kurzami lineárna forma(1,26). V tomto prípade pri maximalizácii cieľovej funkcie (1,26) berieme (-M), pri minimalizácii (+ M).

4. Zostrojíme rozšírenú úlohu M - LP:

nájdite extrém lineárneho tvaru

za nasledujúcich obmedzení:

Nájdeme počiatočný plán M - úloh.

Pretože ďalšie nezáporné premenné a fiktívne premenné sú zahrnuté v obmedzeniach s kladnými jednotkovými koeficientmi, ktoré tvoria systém lineárne nezávislých vektorov ako stĺpcov matica identity, potom budú uvedené premenné základné a všetky ostatné budú voľné, t.j.

Potom bude počiatočný základný plán vyzerať takto:

6. Na nájdenie optimálneho plánu pre rozšírený M - problém zostavte simplexnú tabuľku, ktorá je o jeden riadok viac ako obyčajná. V tomto (m + 2) riadku indexu sú zapísané zodpovedajúce koeficienty na M, zahrnuté v účelovej funkcii s opačným znamienkom.

Skontroluje sa indikátor optimality pre (m + 2) -tý riadok a určí sa premenná, ktorá sa má zahrnúť do základu. Simplexný postup na indexovej čiare (m + 2) sa vykonáva dovtedy, kým nie je pre túto čiaru splnené kritérium optimálnosti. Potom proces hľadania optimálneho plánu pokračuje pozdĺž indexovej čiary (m + 1).

7. Rozoberáme optimálny plán M - úlohy. Ak sa v tomto smere všetky umelé premenné rovnajú nule, t.j. potom plán X (x 1, x 2,…, x n) je optimálny plán pre pôvodný problém. Ak sa v optimálnom pláne M - úlohy aspoň jedna umelá premenná nerovná nule, t.j. potom pôvodný problém nemá riešenie.

Ak v procese riešenia M - problému zistíme jeho neriešiteľnosť, potom je neriešiteľný aj pôvodný problém.

Riešenie testovacieho prípadu.

Nájdite minimum funkcie

za nasledujúcich obmedzení:

1. Zo sústavy nerovníc prejdeme k sústave rovníc, pričom do 1. a 2. obmedzenia vložíme ďalšie nezáporné premenné x 4 a x 5. Prepíšeme tretiu rovnicu bez zmeny:

2. Do 2. a 3. rovnice zavedieme umelé premenné y 1 a y 2:

3. Do lineárneho tvaru L (X) zavedieme súčet y 1 + y 2 s faktorom M. Keďže úloha je nastavená na minimum, vezmeme faktor M so znamienkom „+“.

4. Zostavte M - problém. Nájdite minimum lineárneho tvaru

za nasledujúcich obmedzení:

5. Tento problém riešime simplexnou metódou. Keďže x 4, y 1, y 2 sú základné premenné, vyjadríme ich voľnými a dosadíme do funkcie L (X):

6. Zostavíme simplexnú tabuľku, ktorá má dva indexové riadky: v prvom sú ako obvykle zapísané koeficienty Cj s opačným znamienkom a v druhom zodpovedajúce koeficienty pri faktore M (aj s opačným znamienkom). podpísať, okrem voľného termínu).

Kontrola vlastnosti optimality podľa (m + 2) indexového riadku. Keďže úloha je na minime, funkcia nie je splnená, pretože stĺpec x 2 obsahuje kladný prvok 4. Označte tento kľúčový stĺpec šípkou a ako obvykle vyberieme kľúčovú líniu. Pri výbere kľúčového radu sa získali dve rovnaké najnižšie hodnoty θ. Aby sme sa vyhli zacykleniu, použijeme Crecovo pravidlo. Riadky x 1 a y 1 delíme zodpovedajúcimi prvkami kľúčového stĺpca 2 a 4. Výsledky odčítavame z delenia zľava doprava a ako kľúčový sa zvolí ten riadok, kde sa ako prvé stretne menšie číslo, tzn.

Označte čiaru y 1šípku a nájdeme všeobecný prvok 4. Potom vykonáme zvyčajný simplexový postup a získame druhú tabuľku (tabuľka 1.2.), v ktorej opäť analyzujeme (m + 2) tý riadok indexu a vyberieme stĺpec x 3 pre kľúčový .

Zostrojením tretej tabuľky (tabuľka 1.2.) získame optimálny plán pre rozšírenú úlohu pretože kritérium optimality je splnené pre obe indexové čiary.

Vzhľadom na to, že všetky umelé premenné sú odvodené od základu, optimálnym plánom pôvodného problému je plán a

Pre uvažovaný problém je možné vytvoriť druhý optimálne riešenie s rovnakou hodnotou L min = 24 (tabuľka 1.2.). Preto má problém veľa optimálnych plánov kde

Tabuľka 1.2.

Počet tabuliek	Základné premenné	Voľní členovia	X 1	X 2	X 3	X 4	X 5	å	Q
	X 4				-4
Y 1		-1		-2		-1
Y 2								-
L (X)		-1	-2	-2			-5	Min
		4			-1		-
	X 4		7/2		-3		1/2		-
X 2		-1/4		-1/4		-1/4		-
Y 2
L (X)		-3/2		-3		-1/2		Min
			2
	X 3		1/2					15/2
X 2						-1/4	27/4	-
X 4						1/2	49/2	18/5
L (X)						-1/2	47/2	Min
	X 3	21/5			-1/10		-1/20	101/20
X 2						-1/4	27/4
X 4	18/5			1/5		-1/10	49/10
L (X)						-1/2	47/2	min