Mexiko v dávné minulosti

Just another WordPress.com weblog

LINEÁRNÍ PROGRAMOVÁNÍ A ŘEŠENÍ NĚKTERÝCH ÚLOH SIMPLEXOVOU METODOU

Tenhle článek je spíše pro studující , kteří mají předmět lineární programování a zde bude názorně ukázán postup při výpočtu lineární optimalizace úlohy zejména simplexovou metodou . V jednoduchých případech také graficky .

Samozřejmě že však není účelné touto simplexovou metodou cokoliv řešit v posloupnosti simplexových tabulek , jelikož  v každém tabulkovém proscesoru je obsažen modul , např. ve starém  QUATRO PRO (i jeho verzi přenesené do Corel) je položka OPTIMIZER (popíšu ten samý příklad , jak jej zadat) .

Zde je výborný text , ze kterého lze tuto metodu dobře pochopit  (autora jsme měli  jako učitele na postgraduálním doktorandském studiu oboru inženýrská informatika , předmět se jmenoval operační výzkum) .

http://kix.fsv.cvut.cz/~demel/ped/opv1/ov1.pdf

Zadávání je velice jednoduché a lze v něm i modelovat  a sledovat, jak se bude výsledek lišit , když se bodou měnit omezení či zadání parametrů úlohy .

Samozřejmě , že v tom tabulkovém procesoru je řešení toho zlinearizovaného modelu úlohy naprogramované nejspíš iterací , neřeší se v něm přímo naprogramovaná simplexová tabulka .

To samozřejmě lze rovněž , ale většina tabulkových procesorů tento postup opomíjí .

Důvod, proč není vhodné tuto simpleovou metodu užít k řešení jen s tužkou na papíře tak  je dán především problémem, který vyvstane v okamžiku , kdy se nebude jednat o malé hodnoty , dané maximálně na jednu dvě platné číslice . Dokud se bude jednat o zadání , jaké bývá ve skriptech , tak to samozřejmě je snadno řešitelné.

Ale v obecném případě , kdy dojde při eliminaci koeficientů u neznámých , tak se bude jednat o konkrétní čísla z praxe daná maximálním počtem míst a při zaokrouhlování s tužkou v ruce by došlo např., při malé výpočetní stabilitě matice ke zkreslení výsledku .

Takže zde bude ukázána spíše pro její názornost a také proto , že se prostě z tradičních důvodů její znalost ve škole požaduje .

Samozřejmě , že není žádný problémtuto simplexovou metodu coby posloupnost simplexových tabulek  ji naprogramovat v jakémkoliv , třeba i jednoduchém programovacím jazyku  , třeba dokonce i v nějakém archaickém BASCICu , jaký býval v osmibitových počítačích .

Takže zde bude ukázán příklad , jaký je v např. učebních textech ČZU (Česká zemědělská universita) :

Příklad 1 :

Na 300 ha orné půdy se bude pěstovat pšenice, ječmen a řepka. K dispozici je 50 t NPK. Řepku je možno pěstovat na nejvýše 20 ha, ječmen alespoň na 100 ha.

Rozhodněte, na kolika ha kterou plodinu pěstovat, aby zisk byl maximální

 
Komodita

Pšenice

Ječmen

řepka

NPK(t/ha)

0.2

0.15

0.02

Zisk v 1000 PJ

1

1.5

3

 
 
 
 
 
 
 
 
 
Jako neznámé , proměnné označíme neznámé hledané množství , vyjadřující počet ha plochy s konkrétní komoditou . 
 
Sestrojíme tedy lineární model úlohy ve tvaru
 
max L(x) = 1*x1 + 1.5 *x2 + 3*x3
 
na prostoru řešení S , který je dán těmito nerovnicemi :
 
x1 + x2 + x3 <= 300
 
0.2 * x1 + 0.15 * x2 + 0.02 * x3 <= 50
 
x3  <= 20
 
x2 >= 100
 
———————————————————————————————–
Prostor řešení S je  tedy dán systémem , který je zlinearizovaným   modelem :
 
 A* X  <=> B
 
kde A je lineární model úlohy , daný maticí A(m,n) , X je vektor proměnných daný maticí X(n,1) , také neznámých (v tabulkových procesorech spíše jako proměnné)  jsou tzv. omezení daná vektorem B(n,1) ,  kde výraz  <=>  značí použitou  relaci  .
 
—————————————————–
 
Než začneme zapisovat první simplexovou tabulku ,  musíme ale provést nezbytnou úpravu .
 
Jelikož zde v příkladě tři nerovnice jsou dány omezením ve tvaru méně nebo rovno  a čtvrtá ve tvaru více nebo rovno , musíme se rozhodnout , jaký jednotný tvar budou mít.
Tak jestliže je převažující počet nerovnic , jako například zde , ve tvaru méně nebo rovno, tak musím čtvrtou nerovnici , jež je ve tvaru více nebo rovno, převést na tvar méně nebo rovno .
 
To zařídíme následující úvahou :
 
x2 >= 100 , tudíž když  k tomuto výrazu přidáme další pomocnou proměnnou x4 (číslujeme dalším nepoužitým indexem) , zajisté jejím odečtením lze zařídit , aby se výraz změnil  na x2 -x4 <= 100 .
Odečtením proto, že složky vektoru řešení, tj. proměnné , alias neznámé jsou čísla kladná , proto  nutno odečíst .
 
Dále musíme k systému nerovnic přidat další počet přídatných neznámých  ve tvaru kanonické báze , dané jednotkovou maticí, jež zařídí , že se tvar nerovností převede na tvar rovností .
 
Takže , přídatné proměnné (neznámé) , jež slouží jen na odstranění nerovnosti , se přidávají zásadně ve tvaru +xi , tj. vždy se přičítají  
Pomocná proměnná , jež má zařídit přeměnu výraz větší než na výraz menší než , se musí zásadně odečítat , tedy ve tvaru -xi .
 
Avšak pomocná proměnná , jež má zařídit přeměnu z tvaru méně nebo rovno na tvar více nebo rovno , se musí zásadně přičítat .
 
Tedy :
 
A* X´ = B , přičemž
 
systém A*X´  je nutno upravit na tvar :
 
A*X,E = B , kde X´= X,E
 
kde jednotková matice vyjadřuje počet přídatným neznámých , který je dán počtem výchozích rovnic,
 
tedy :
 
A(m,n) * XT(n,1)  <=> B(m,1) (XT – transponovaná matice , tedy zde řádkový vektor proměnných alias neznámých) . 
 
A(m,n+n´) * XT(n+n´,1)  = B(m,1)
 
 kde n je počet neznámých (proměnných) , včetně počtu případných pomocných proměnných na zajištění adekvátní  nerovnosti
a n´je počet přídatných proměnných tzv. basických , jež jsou zapsány v diagonále jednotkové matice  .
 
Zde konkrétně jsou původní neznámé x1 , x2 , x3 , dále x 4 je pomocná proměnná na dotvoření správmého tvaru nerovnosti a x5 , x6 , x7 , x8 jsou přídatné proměnné , jejichž počet je dán počtem rovnic .
 
Nyní můžeme zapsat  výchozí simplexovou tabulku .
 
 
  

1

a1

1.5

a2

3

a3

0

a4

0

a5

0

a6

0

a7

0

a8

 

b

0   a5

1

1

1

0

1

0

0

0

300

0  a6

0.2

0.15

0.02

0

0

1

0

0

50

0  a7

0

0

1

0

0

0

1

0

20

0  a8

0

1

0

-1

0

0

0

1

100

z – c

-1

-1.5

-3

0

0

0

0

0

0

 
 
 

Výpočet je založen na hledání klíčového prvku v každém kroku (pivot) , který je dán kdysi empiricky nalezenými pravidly .

Tato úloha nebyla v podstatě dlouhou dobu exaktně řešitelná , jelikož výpočetní čas roste s faktoriálem počtu všech možných kombinací     n  nad m  , tedy n!/(m!*(n-m)!) .                                                                         

Takže tato simplexová metoda není zase až tak stará záležitost a i když exaktní řešení by spočívalo v pouhém algoritmu , který by vyřešil jednu kombinaci po druhé a z nich vybral výsledek , kde optimalizační funkce nabývá svého extrému , tedy maxima či minima , tak ztroskotává i dnes na potřebném výpočetím času a proto se empiricky pokoušeli matematici odvodit postupy , které by automaticky vyřazovaly ze hry celé třídy řešení , nevedoucích očividně k cíli , což činí tato velmi jednoduchá metoda .

Nazvána byla simplexová proto , že řešení tvoří konvexní polyedr ve víerozměrném prostoru a my na tomto polyedru hledáme krajní bod řešení  kde má zmíněná účelovvá funkce své minimum či maximum a útvar je geometricky vzato simplex v n- rozměrém prostoru . 

Vlastně se při řešení , které se geometricky vzato odehrává v prostoru E(N) , kde N je počet neznámých (proměnných) , sestrojí konvexní polyedr a pomocí účelové funkce se nalezne krajní bod toho polyedru  , ve kterém má účelová funkce extrém , tedy maximum či minimum .

Takže obecně vzato se jedná o konvexní hypermnohostěn alias hyperpolyedr .

V prostoru E(1) je tímto hypermnohostěnem úsečka , jež leží přímo na souřadnicové ose x1

V prostoru E(2) je tímto hyperpolyedrem vlastně mnohoúhelník , jelikož hyprestěnami jsou úsečky.

V prostoru E(3) je tímto hyperpolyedrem přímo konkrétní mnohostěn , jak jej známe z obvyklého života , může to být třeba jehlan či kvádr či krychle , ale také třeba ve zvláštním případě platonské těleso i prostě jakýkoliv útvar , jehož povrch je omezený plochami v obvyklém slova smyslu .

V prostoru E(4) je jím pochopitelně úvar typu hyperkrychle , hyperjehlan a pod a jeho povrch je tvořen třírozměrnými útvary .

Takže v prostoru E(N) obecně je hyperpolyedr  těleso , jež má povrch tvořený útvary E(N-1) prostoru .

Pak účelová funkce je obecně hyperrovina , takže v E(2) jí byla přímka (jak ji známe) , v E(3) rovina (jak ji známe) a v E(4) ji tvoří třírozměrná hyperrrovina a tak lze postupovat stále do vyšších dimenzí .

.

Nyní uplatníme pravidlo pro výběr sloupce .

V řádku z-c vybereme tu hodnotu ze záporných čísel, jež má největší absolutní hodnotu . Tím obdržíme řídící sloupec.

Dále uplatníme pravidlo pro výběr řádku .

Učiníme (někde stranou) podíly bi/aij , kde j je j-tý vybraný sloupec .

Vybereme takový podíl,  který je nejmenší a ten se samozřejmě odehraje v příslušném řádku .

Takže v průsečíku řádku a sloupce leží klíčový prvek – pivot a vzhledem k tomuto budeme eliminovat ostatní řádky (nad ním i pod ním ležící tak , aby pod klíčovým prvkem byly samé nuly) .

To se provede naprosto stejným způsobem , jako při klasickém řešení třeba inversní matice či zjišťován í hodnosti matice, tedy

pomocí tzv. ekvivalentních úprav , jež spočívají v tom , že ke kterémukoliv řádku můžeme přičíst libovolnou lineární kombinaci ostatních řádků .

Pro matici obecně to lze samozřejmě uplatňovat i pro sloupce , zde ale jde o speciální případ, kdy budeme dělat i některé věci navíc. Tedy např. i upravovat řádek z-c a sloupec b a „přetahovat“  hodnoty ze záhlaví simpexové tabulky .

 Vidíme , že to bude prvek ze třetího sloupce a třetího řádku tedy a33 .

Nyní pomocí lineárních kombinací učiníme , aby ve sloupci byly nad a pod prvkem samé nuly .

Takže zde například odečtu od prvního řádku třetí  řádek a tím dostaneme nulu v prvku a13

Dále od 50* násobku druhého řádku odečtme zde řádek třetí a pak nezapomenem zpět řádek vydělit 50 .

Dále ve čtvrtém řádku jej již „zadarmo“ nula , tudíž nečiníme nic

Dále k poslednímu řádku, z-c , přičteme trojnásobek třetího řádku .

A zejména do sloupce zcela vlevo do třetího řádku „přetahneme“ hodnotu , zapsanou v záhlaví třetího sloupce .

Tím obdržíme následující simplexovou tabulku :

  

1

a1

1.5

a2

3

a3

0

a4

0

a5

0

a6

0

a7

0

a8

 

b

0   a5

1

1

0

0

1

0

-1

0

280

0  a6

0.2

0.15

0

0

0

1

-0.02

0

49.6

3  a3

0

0

1

0

0

0

1

0

20

0  a8

0

1

0

-1

0

0

0

1

100

z – c

-1

-1.5

0

0

0

0

3

0

60

 
 
 
 
 
 
 
 
 
Z tabulky je dobře vidět, že musí pro kontrolu korespondovat naznačené součiny v levém sloupci s hodnotou v pravém dolním rohu , tedy v řádku z-c :
 
tedy : 0*280 + 0 * 49.6 + 3 * 20 + 0 * 100 = 60 a to je současně i hodnota v posledním sloupci v řádku z-c .
Dále prvek , který byl pivotem je zárove bazickou jedničkou , ostatní se zachovají a musíme dohlednout, aby po případných eliminačních úpravách byly řádky na tuto jedničku redukovány a samozřejmě i tento pivot .
 
Nyní postup zopakujeme , tedy v řádku z-c má větší absolutní hodnotu prvek ve sloupci druhém a učiníme podíly
bi/aij , tedybi/ai2
klíčový prvek – pivot se bude nacházet ve druhém sloupci a čtvrtém řádku , tedy a42 .
 
Takže po úpravách obdržíme následující tabulku :
 
  

1

a1

1.5

a2

3

a3

0

a4

0

a5

0

a6

0

a7

0

a8

 

b

0   a5

1

0

0

1

1

0

-1

-1

180

0  a6

4/3

0

0

1

0

20/3

-2/15

-1

692/3

3  a3

0

0

1

0

0

0

1

0

20

1.5 a2

0

1

0

-1

0

0

0

1

100

z – c

-1

0

0

-1.5

0

0

3

1.5

     210
 
 
 
 
 
 
 
 
 
 
 Třetí řádek jsme jen opsali, byla v něm zadarmo nula,
první řádek jsme obdrželi tím ,že jsme od něj odečetli čtvrtý řádek ,
Druhý řádek jsme obdrželi tím , že jsme jej vydělili 0.15 a od něj odečetli čtvrtý  řádek
Řádek z-c jsme vydělili 1.5 a přičetli k němu čtvrtý řádek .
A dále jsme , jelikož došlo vlivem eliminačních úprav k pozměnění bazické jedničky a 26 na hodnotu 20/3 , tak jsme celý tento řádek touto hodnotou 20/3 vydělili a obdrželi následující tabulku
a samozřejmě nezapomeneme do čtvrtého řádku prvního sloupce přetahnout výraz 1.5 a2
 
 
 
  

1

a1

1.5

a2

3

a3

0

a4

0

a5

0

a6

0

a7

0

a8

 

b

0   a5

1

0

0

1

1

0

-1

-1

180

0  a6

0.2

0

0

3/20

0

1

-0.02

0

34.6

3  a3

0

0

1

0

0

0

1

0

20

1.5  a2

0

1

0

-1

0

0

0

1

100

z – c

-1

0

0

-1.5

0

0

3

1.5

     210
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Opět je dobře vidět , jak pro kontrolu výpočet koresponduje , tj.
 
0*180 + 0*4.6 + 3*20 +  1.5*100 = 210 , což je také hodnota v posledním sloupci řádku z-c .
 
Opět postupujeme obdobně ,
 
Ze záporných hodnot opět vybereme tu  s větší abs. hodnotou , což je sloupec čtvrtý a v něm druhý řádek dává nejmenší podíl . Podílu , kde by vyšel záporný výsledek (100/-1) ,  si nevšímáme .
Takže klíčový prvek , pivot bude  a 14 a výsledkem bude opět další simplexová tabulka :
 
 
 
  

1

a1

1.5

a2

3

a3

0

a4

0

a5

0

a6

0

a7

0

a8

 

B

0   a5

1

0

0

1

1

0

-1

-1

    180
0  a6

0.05

0

0

0

-0.15

1

0.13

0

7.6

3  a3

0

0

1

0

0

0

1

0

20

1.5 a2        1

1

0

0

1

0

-1

0

280

z – c

0.5

0

0

0

1.5

0

1.5

0

     480

První řádek pouze opíšeme

Druhý  řádek získáme nejprve vydělením číslem 3/20 a odečteme od něj první řádek  , tím samým číslem jej po eliminaci opět vynásobíme

Třetí řádek rovněž pouze opíšeme, obsahuje zadarmo nulu

Čtvrtý řádek obdržíme přičtením prvního  řádku ke stávajícímu čtvrtému řádku

 Řádek z-c vydělíme číslem 1.5 a přičteme k němu první  řádek , tím samým číslem pak po eliminaci jej zpětně vynásobíme .

Takže toto je výsledná simplexová tabulka :

 
 
  

1

a1

1.5

a2

3

a3

0

a4

0

a5

0

a6

0

a7

0

a8

 

B

0   a4

1

0

0

1

1

0

-1

-1

    180
0  a6

0.05

0

0

0

-0.15

1

0.13

0

7.6

3  a3

0

0

1

0

0

0

1

0

20

1.5 a2        1

1

0

0

1

0

-1

0

280

z – c

0.5

0

0

0

1.5

0

1.5

0

     480
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Takže výsledkem řešení je krajní bod konvexního polyedru o souřadnicích
 
X =
x1= 0
x2= 280
x3= 20
x4= 180
x5 = 0
x6 = 7.6
x7 = 0
x8 = 0
 
Hledané maximum je vlastně již vypočteno v řádku z-c ve sloupci b , tedy 1*x1+1.5*x2+3*x3 = 1*0+1.5*280+3*20 = 480 .
 
 
 
Po dosazení do výchozích nerovnic je vidět, že výsledek koresponduje .
 
Tj. :
x1+x2+x3 = 0 + 280 + 20 = 300  <= 300 
 
0.2*x1+0.15*x2+0.02*x3 = 0 + 42 + 0.4 = 42.4  <= 50
 
x3 = 20 <= 20
 
x2 = 280 >= 100
 
tedy po úpravě jsme převedením z tvaru více nebo rovno obdrželi tvar :
 
x2 – x4 = 280 – 180 = 100 <= 100
 
výraz x6 = 7.6 vyjadřuje rezervu v NPK , kde mělo být méně nebo rovno 50 , vyšlo 42.6 a zbývá k dobru 7.6 ,
přičemž formálním dosazením do rovnice včetně kanonického tvaru , tj, bazické neznáné , kterou tato neznámá x6 je, obdržíme :
 
0.2*x1+015*x2+0.02*x3+x6 = 0 + 42 + 0.4 + 7.6 = 42.6 + 7.6 = 50 a jelikož je zde tedy tvar převeden s pomocí bazických neznámých na exaktní rovnost , výraz daný druhou rovnicí početně souhlasí  .
 
 
 
 Výpočetní algoritmus končí ve chvíli , kdy již nejsou žádné záporné hodnoty v řádku z-c  .
 
Toto však je v případě , kdy se bude jednat o úlohu , kde bude jednoznačně omezení ve tvaru méně nebo rovno nebo jen ve tvaru více nebo rovno .
 
Problém nastane , když je relace smíšená a pak je nutno , jako zde , převést na společný tvar a přidávat další pomocnou neznámou a další problém nastává , když v účelové funkci jsou stejné koeficienty .
Pak nelze rozhodnout , který sloupce zvolit jako řídící .
 
O tom příště .
 

Příklad 2 :

Podnik vyrábí dva druhy výrobků

Výrobku A může být nejvýše o dva kusy více,  než dvojnásobek množství výrobku B
Výrobku B může být nejvýše o dva kusy více , než dvojnásobek množství výrobku A
Výroku A i B může být nejvýš 5 kusů

Určete počet kusů výrobku A , B , aby zisk 2*x1 + 3*x2 byl maximální

Řešení :

hledáme max L(x) = 2*x1 + 3*x2

na prostoru řešení S , daném rovnicemi :

 x1 – 2*x2 <=2

-2*x1 + x2 <= 2

x1 + x2 <= 5

Dále také samozřejmě požadujeme , aby x1,x2 bylo >=0

Řešení je v posloupnoti simplexových tabulek

  2 3 0 0 0  
  a1 a2 a3 a4 a5 b
0 a3 1 -2 1 0 0 2
0 a4 -2 1 0 1 0 2
0 a5 1 1 0 0 1 5
z-c -2 -3 0 0 0 0
 
 
  2 3 0 0 0  
  a1 a2 a3 a4 a5 b
0 a3 3 0 1 2 0 6
3 a2 -2 1 0 1 0 2
0 a5 3 0 0 -1 1 3
z-c -8 0 0 3 0 6
 
 
  2 3 0 0 0  
  a1 a2 a3 a4 a5 b
0 a3 0 0 1 3 0 8
3 a2 0 1 0 1/3 2/3 4
2 a1 1 0 0 -1/3 1/3 1
z-c 0 0 0 1/3 8/3 14

Touto tabulkou výsledek končí ,

vektor řešení je :

 X

x1=1

x2=4

x3=8

x4=0

x5=0

Formálním dosazením do výchozích nerovnic je vidět , že výsledek koresponduje :

x1 – 2*x2 <=2 , tedy 1-2*4 = -7 <=2

-2*x1 + x2 <= 2 , tedy -2*1 + 4 = 2 <=2

x1 + x2 <= 5 , tedy 1 + 4 = 5 <=5

Hledané maximum je vlastně již vypočteno v řádku z-c ve sloupci b , tedy 2*x1+3*x2 = 2*1+3*4 = 14 .
 

Další příklad příště , bude např. na optimální sestavení směn , řezného plánu , perfektní párování , optimální výrobní program a další ukázky , včetně grafického odvození v případě dvou neznámých . 

 

 

Příklad 3 :

Příklad na optimální výrobní program při výrobě směsí :

Podnik vyrábí tři druhy leteckého benzínu B1 , B2 , B3  a na jeho výrobu jsou třeba čtyři složky – výchozí surovina

alkin , izopentan , krakovací benzín a destilovaný benzín .

Disponibilní množství složky

S1 = 400 000 l 

S2 = 250 000 l

S3 = 350 000 l

S4 = 100 000 l 

Složky jsou obsaženy

v benzínu B1 v poměru 2 : 3 : 5 : 2

v benzínu B2 v poměru 3 : 1 : 2 : 1

v benzínu B3 v poměru 2 : 2 : 1 : 3

Odbytová cena těchto benzínů je

pro benzín  B1 = 120 000 PJ ,

pro benzín B2 = 100 000 PJ ,

pro benzín  B3 = 150 000 PJ

Cílem je stanovit takový výrobní program , aby zisk byl maximální .

Řešení :

Abychom obdrželi koeficienty matice modelu úlohy A , nejprve provedeme úpravu :

bi/[b] každé poměrové číslo vydělíme součtem všech a pro kontrolu musí dávat jedničku

Takže obdržíme výchozí tabulku :

Obsahuje samozřejmě jednotkovou matici, jež odpovídá počtu výchozích rovnic a samozřejmý požadavek nezápornosti neznámých (proměnných)

 

120

a1

100

a2

150

a3

0

a4

0

a5

0

a6

0

a7

 

b

 

 

0  a4

0.1666

0.4285

0.25

1

0

0

0

400

   
0  a5

0.25

0.14285

0.25

0

1

0

0

250

 

0  a6

0.4166

0.2857

0.125

0

0

1

0

350

 

0  a7      0.1666

0.1428

0.3

0

0

0

1

100

 

z – c

-120

-100

-150

0

0

0

0

0

    
 
 
 

Nyní známým způsobem uplatníme

pravidlo pro výběr sloupce , vidíme , že max. abs hodnota v řádku z-c je v třetím sloupci , dále

pravidlo pro výběr řádku , vidíme , že min. podíl bj/ai je v řádku čtvrtém , takže klíčový prvek je a4,3

Vůči tomuto prvku budeme provádět příslušné eliminace , tj. aby nad ním a pod ním se ocitly nuly .

A jelikož se zde jedná o obecné koeficienty , tak již spíše , než v předchozích příkladech , důsledně tak , že klíčovým prvkem zredukujeme celý řádek , takže obdržíme místo něj jedničku a ostatní řádky zredukujeme prvkem , jenž je ve stejném sloupci jako klíčový prvek, tedy nad ním či pod ním a celý řádek  , obsahující  klíčový prvek , vektorově odečteme a pak samozřejmě opět vynásobíme tím , čím jsme redukovali a nezapomeneme přetahovat koeficienty z horních dvou řádků nad klíčovým prvkem do sloupce vlevo v řádku, který odpovídá řádku , kde je klíčový prvek .

Takže po úpravách obdržíme následující simplexovou tabulku :

 

120

a1

100

a2

150

a3

0

a4

0

a5

0

a6

0

a7

b

 

0  a4

0.05555

0.33333

0.00

1

0

0

-0.6666

333.33333

   
0  a5

0.13888

0.04761

0.00

0

1

0

-0.66666

183.333

 

0  a6

0.36111

0.23809

0.00

0

0

1

-0.33333

316.666

 

150  a3   0.44444

0.38092

1

0

0

0

2.6666

266.666

 

z – c

-53.3333

-42.8571

0.00

0

0

0

400

40000

  

Opět provedeme výběr sloupce , vidíme , že max. abs hodnota je v prvním sloupci , dále provedem výběr řádku , vidíme , že nejmenší podíl bj/ai je v řádku druhém , takže klíčový prvek je a4,1

 

120

a1

100

a2

150

a3

0

a4

0

a5

0

a6

0

a7

b

 

0  a4

0

0.28571

-0.125

1

0

0

-1

300

   
0  a5

0

-0.07142

-0.3125

0

1

0

-1.5

100

 

0  a6

0

-0.07142

-0.8125

0

0

1

-2.5

100

 

120 a3        1

0.85714

2.25

0

0

0

6

600

 

z – c

0

2.85717

120

0

0

0

720

72000

  

 Toto je výsledná simplexová tabulka a výpočet končí .

Výpočetní algorutmus byl ukončen v tomto případě , jelikož v prvních třech sloupcích v řádku z-c zmizely v tomto kroku algoritmu záporné prvky a objevily se větší , případně rovny nule .

 Tudíž bodem řešení je
X = (x1 , x2 , x3 , x4 , x5 , x6)
 
x1 = 0
x2 = 0 
x3 = 600
x4 = 300
x5 = 100
x6 = 100
x7 = 0
 
Vidíme, že výsledek účelové funkce koresponduje se siplexovou tabulkou , jelikož je vidět , že součet součinů 0*a4 + 0 * a5 + 0*a6 + 120*a3 = 120*600 = 72000 . 
 
Sestavil jsem v archaickém Basicu program , který tuto posloupnost simplexových tabulek vypočte včetně zadávání a ukládání , až budu mít čas , pokusím se jej dát jako spustitelný soubor na web  a mohl by jít ještě pod W XP. Program má tu výhodu , že ukazuje při každém provedeném kroku aktuální stav tabulek .
To z programů , jež jsou součástí programových balíků , jako třeba wordperfect , není bohužel patrné .
 
Příště přidám další příklady na všechny možné způsoby užití .
 
Příklad 4 :
 
Optimální výrobní program :
 
Výrobky A a B se zpracovávají na dvou strojích .
 
Výrobku A je zapotřebí vyrobit alespoň 14 kusů .
 
Kapacita orvního stroje je 3000 provozních hodin
 
Kapacita druhého stroje je 1000 provozních hodin .
 
Požadavky výrobků na provozní hodiny jsou v následující tabulce .
 
 
 

 
    Stroj 1  
      Stroj 2
      Zisk
    A
     80
       20
       30
   B
      2
        2   
       30
 
  
Řešení :
 
Nejprve sestavíme zlinearizovaný model úlohy .
 
Neznámé (proměnné) zde budou představovat neznámý počet , samozřejmě nezáporný  .
 
Takže :
 
x1  >= 14
 
80 x1 + 2 x2 <= 3000
 
20 x1 + 2 x2 <= 1000
 
a samozřejmá podmínka nezápornosti
 
x1 , x2  >= 0
 
Účelová funkce :
 
max L(X) = 30 x1 + 30 x2
 
Nejprve , jelikož převažuje počet nerovnic tvaru méně nebo rovno , převedeme první nerovnici na tvar :
 
x1 – x3  <=  14
 
Systém nerovnic nyní převedeme na rovnice , takže obdržíme :
 
x1                          – x3 + x4                   = 14 
 
80 *x1 + 2 *x2                    + x5         = 3000
 
20 *x1 + 2* x2                             + x6 = 1000
 
Systém nerovnic jsme převedli na systém rovnic s využitím kanonické báze , která odpovídá počtu omezení , takže obdržíme výchozí simplexovou tabulku :
 
  30 30 0 0 0 0  
  a1 a2 a3 a4 a5 a6 b
0*a4 1 0 -1 1 0 0 14
0*a5 80 2 0 0 1 0 3000
0*a6 20 2 0 0 0 0 1000
z-c -30 -30 0 0 0 0 0
Další a konečná simplexová tabulka :
 
  30 30 0 0 0 0  
  a1 a2 a3 a4 a5 a6 b
0*a4 1 0 -1 1 0 0 14
0*a5 60 0 0 0 1 0 2000
0*a6 10 1 0 0 0 .5 500
z-c 270 0 0 0 0 0 15000
Jelikož byly koeficienty účelové funkce stejné hodnoty , tak vybrat řídící sloupec je v tomto případě na rozhodnutí konkrétního uživatele .
Ve svém programu mám zadáno , aby se pro případ stejné hodnoty v řádku z-c , tedy vybral sloupec s nejvyšším indexem .
Ale není problém zařídit , jak učinit , aby vybraný klíčový sloupce byl ten první , stačí jen přehodit sloupce , prostě první za druhý a naopak nebo udělat v programu možnost interaktivního rozhodnutí a ovlivnit to osobně .
 
Výsledkem výpočtu je bod X (x1,x2,x3,x4,x5,x6) , tedy:
 
x1 = 0
x2= 500
x3 = 0
x4 = 14
x5 = 2000
x6 = 0
 
Formálním dosazením do rovnic je vidět , že výsledek koresponduje .
 
Výsledek lze tedy interpretovat tak , že se výrobek  A  nevyplatí vyrábět vůbec a druhý tedy v počtu 500 kusů .
 
 
 

Příklad  5 :
 
Dopravní úloha :
 
 
Metodou lineárního programování lze též řešit docela efektivně i dopravní úlohy .
 
Pokud se  řeší tzv. vyvážená úloha , čímž se rozumí , že výchozí rovnice budou ve tvaru rovno  , tedy A*X = B , není třeba zavádět přídatné proměnné , tedy formou jednotkové matice , tvořící kanonickou bázi .
 
Řešení se samozřejmě provede simplexovou metodou , přičemž účelová funkce je ve tvaru min L(X) = a1*x1 + a2*x2 + …ai*xi
 
 
 
což lze také převést na tvar max -L(X) = – a1*x1 -a2*x2 …. – ai*xi
 
Nyní výchozí tabulka :
 
máme 2 dodavatele , 2 odběratele  , a dále matici sazeb , tedy hodnot , představujících dopravní náklady , může být zapsáno  i jakékoliv vhodné podobě , jako schéma či tabulka .
 
Například takto :
 
Dodavatel Di / Spotřebitel Sj     S1 S2 Kapacity dodavatelů    
D1     1  1.50 40    
D2     2 0.75 60    
Požadavky spotřebitelů      50 50 kontrolní součet = 100    
 
 
Účelová funkce je min L(X) = 1*x1 + 1.5*x2 + 2*x3 + 0.75*x4 a tuto se snažíme minimalizovat , což znamená nalézt takové řešení , kdy budou dopravní náklady minimální .
 
 
 
Dále rozepíšeme zlinearizovaný model formou rovnic  :
 
x1 + x2 = 40
x3 + x4 = 60
x1 + x3 = 50
x2 + x4 = 50
 
Nyní zapíšeme posloupnost simplexových tabulek :
 
S0 :
 
 
   –  1.50   –  1.50   –  1.50   –  1.50   
  a1 a2 a3 a4 b
u1 1 1 0 0 40
u2 0 0 1 1 60
u3 1 0 1 0 50
u4 0 1 0 1 50
z-c  –  1.00  –  1.50   –  2.00  –  0.75 0
  
 
 
 
 
 
Úloha řezného plánu : (příště)
 
 
 
 
 
  
 
Reklamy

Únor 9, 2012 Posted by | Geometrie vícerozměrných prostorů | Napsat komentář