Simplexová metóda umelých premenných. Riešenie úloh lineárneho programovania metódou umelej bázy

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

Pre mnohé úlohy lineárneho programovania napísané vo forme hlavného problému a so základnými plánmi nie je medzi vektormi Pj vždy m jednotkových vektorov.

Zoberme si nasledujúcu úlohu:

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 P 1, P 2, …, P n nie je m jednotkových jednotiek.

Definícia. Problémom je 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) vo vzťahu k problému (1) - (2).

Rozšírená úloha má základnú líniu

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

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

Veta Ak optimálne 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á simplexová tabuľka. V tomto prípade sú koeficienty pri M, a v (m + 1)-tých výrazoch, 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 zápornému číslu (m + 2) riadku v absolútnej hodnote. Umelý vektor vylúčený z bázy sa nezapisuje do ďalšej simplexovej tabuľky. Prepočet simplexných tabuliek pri prechode z jedného referenčného plánu do druhého sa vykonáva podľa všeobecné pravidlá simplexná metóda.

Iteračný proces pozdĺž línie (m + 2) sa vykonáva, kým:

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

alebo nie sú vylúčené všetky umelé vektory, ale (m+2)-tý 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 v definovaní jeho optimálneho plánu sa pokračuje pozdĺž (m + 1) riadku.

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 báza obsahuje aspoň jeden z umelých bázových vektorov.

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

metóda na umelom základe:

Napíšte rozšírenú úlohu (3) - (4).

Nájdite základňu pre rozšírenú úlohu.

Pomocou bežných výpočtov simplexovej metódy sú umelé premenné vylúčené zo základu. V dôsledku toho sa buď nájde referenčný plán pôvodného problému (1) - (2), alebo sa zistí jeho neriešiteľnosť.

Pomocou nájdeného referenčného plánu problému (1) - (2) buď simplexová metóda nájde optimálny plán pôvodného problému, alebo zistí jeho neriešiteľnosť.

Príklad.

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

P ri obmedzenia:

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

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

x 1 - x 2 + 2 x 3 ≥ 10

X i ≥0, i=1,4

Riešenie.

Poďme si zapísať túto úlohu v podobe hlavného problému: nájsť maximum funkcie F= 2X 1 - 3X 2 + 6X 3 + X 4

s obmedzeniami:

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

x1 +2x2 +4x3 +x5 =22

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

X i ≥0, i=1, 6

V systéme rovníc posledného problému zvážte vektory z koeficientov neznámych:

Medzi vektormi P1, R 2 , ... P 6 iba dve samostatné (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

x1 +2x2 +4x3 +x5 =22

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

Rozšírený problém má referenčný plán X=(0; 0; 0; 24; 22; 0; 10) určený systémom troch jednotkových vektorov: P4, P5, R7.

Koncept duálneho (adjungovaného) problému lineárne programovanie.

Stavebné pravidlá duálny problém.

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, sa nazýva priamy problém.

Duálny problém je konštruovaný s ohľadom na priamy problém 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)

Úloha nájsť minimálnu hodnotu funkcie

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

za podmienok

a 11 r 1 + a 12 r 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 r 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. Cieľová 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 priamych problémových premenných x j , , t.j. n
4. Matica koeficientov v systéme obmedzení
5. Koeficienty pre premenné v účelovej funkcii	c 1 , c 2, …, c n	b1,b2, …,b m
6. Pravá časť obmedzovacích systémov	b1,b2, …,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 "="
	c) i-té obmedzenie má znamienko "≤"	premenná y i ≥0
	d) i-té obmedzenie má znamienko "="	premenná y i nepodlieha podmienke nezápornosti

Poznámka

Problém priameho maxima a problém duálneho minima sú vzájomne duálne problémy. Preto môžeme problém (3.9)–(3.11) považovať za priamy LLP a problém (3.6)–(3.8) za jeho duálny problém. Zároveň sú zachované pravidlá pre budovanie duálneho LLP, len s tá zmenaže za minimálny problém sa považuje počiatočný.

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

a) alebo vynásobte obe strany i-th ( j th) nerovnosť o (-1) a zmeňte znamienko na "≤" ("≥")

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

Nevyhnutnou podmienkou pre aplikáciu simplexovej metódy je prítomnosť referenčného plánu, teda prijateľného základného riešenia kanonickej sústavy rovníc. Na to musia byť splnené nasledujúce podmienky:

• systém musí mať kanonickú (stupňovitú) štruktúru;
• existujú iba obmedzenia rovnosti;
• pravé časti obmedzení sú kladné;
• premenné úlohy sú pozitívne.

Bez týchto podmienok nemôžete získať základný plán. Nie vždy sú však tieto podmienky v reálnych problémoch splnené.

Existuje špeciálna metóda, nazývaná umelý základ, ktorá vám umožňuje získať počiatočný základný plán v akomkoľvek probléme lineárneho programovania.

Nechajte problém lineárneho programovania zredukovať na štandardnú formu:

Nechať všetkých /? > 0, ale niektoré alebo všetky základné premenné sú negatívne, X; 0. Preto neexistuje základná línia.

Obmedzovacie rovnice dopĺňame umelými premennými (predpokladáme, že všetky xj j - 1, P).

Poďme sa predstaviť t premenné (podľa počtu rovníc): x 1M t, ktorý nový systém bude základný a negatívny X-

Výsledkom je nasledujúci ekvivalentný problém.

Tu sú premenné xn+i nemajú nič spoločné s pôvodným problémom lineárneho programovania. Slúžia len na získanie referenčného plánu a nazývajú sa umelé premenné. A to nové

účelová funkcia /(.t) sa tvorí pre úplnosť problému.

V optimálnom referenčnom dizajne by fiktívne premenné mali byť nulové. V opačnom prípade bude porušená podmienka pôvodného problému.

V počiatočnom referenčnom návrhu sú umelé premenné základné, to znamená, že sa nerovnajú nule a v optimálnom návrhu by sa umelé premenné mali rovnať nule. To znamená, že umelé premenné by sa mali optimálne uvoľniť. Tento preklad je hlavnou myšlienkou metódy: preklad umelých premenných zo základných premenných na voľné. Zoberme si mechanizmus takéhoto prekladu pomocou príkladu.

Prepíšme LLP do štandardnej formy. Aby sme to dosiahli, zavádzame ďalšie premenné x), x A, x 5, x 6 a napíšte úlohu kanonickej podobe.

Voľné premenné x, X 2 = 0, zatiaľ čo základné premenné budú nadobúdať hodnoty x 3 \u003d -5, x 4 \u003d -5, x 5 \u003d 7, x 6 \u003d 9. Keďže niektoré základné premenné sú záporné, neexistuje základná línia. Aby sme získali počiatočný referenčný plán, zavedieme premenné x 7 , x 8 do prvých dvoch obmedzujúcich rovníc a sformulujeme pomocnú úlohu:

Počiatočný základ je teda

Simplexné tablo s umelým základom

	X4

Zapíšme si postupnosti základných plánov.

Pre prvé tri prírastky A to sú vypočítané iba umelými premennými, ktoré sú zahrnuté v umelom objektívna funkcia/(X) = x 7 + x 8 s koeficientom c, = 1.

V treťom kroku sú vylúčené umelé premenné, pretože všetky A to sú pozitívne.

Simplexová metóda so zavedením umelých premenných teda zahŕňa dve fázy.

Tvorba a riešenie pomocnej úlohy LP so zavedením umelých premenných. Falošné premenné v počiatočnej základnej línii sú základné. Umelá objektívna funkcia zahŕňa iba umelé premenné. Po prijatí susedných referenčných plánov prenášame umelé premenné zo základných na voľné. Výsledkom bol optimálny plán podpory pre pomocnú úlohu f(x) = 0.

Optimálna základná línia pomocnej úlohy LP je počiatočná základná línia hlavnej úlohy LP. Úloha sa rieši pre pôvodnú účelovú funkciu /(x) obvyklou simplexnou metódou.

Poznámky

• 1. Zavedenie umelých premenných sa vyžaduje v dvoch prípadoch:
  • množstvo základných premenných x v kanonickom tvare je záporných;
  • ak je ťažké ho zredukovať na kanonickú formu, potom jednoducho pridáme umelú premennú do akejkoľvek obmedzujúcej rovnice.
• 2. Vyskytujúce sa v praxi automatické ovládanieúlohy lineárneho programovania obsahujú od 500 do 1500 obmedzení a viac ako 1000 premenných. Je jasné, že problémy tohto rozmeru sa dajú riešiť len pomocou počítača a špeciálu softvér. Zložitosť algoritmu spočíva v tom, že:
  • PPP vyžaduje kánonickú formu;
  • SPP pre problémy tohto rozmeru vyžaduje použitie sálové počítače(a paralelné výpočty), pretože simplexná metóda ukladá celú tabuľku.
• 3. Výpočtovú účinnosť simplexovej metódy možno odhadnúť pomocou nasledujúcich ukazovateľov:
  • počet krokov (susedné referenčné plány);
  • náklady na strojový čas.

Existujú také teoretické odhady pre štandardná úloha lineárne programovanie s t obmedzenia a ""premenné:

• priemerný počet krokov * 2 t a leží v dosahu