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	0  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	0  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