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 |
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 |
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 |
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 |
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 |
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
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 .
Stroj 1
|
Stroj 2
|
Zisk
|
|
A
|
80
|
20
|
30
|
B
|
2
|
2
|
30
|
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 |
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 |
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 |
– 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 |
-
Archiv
- Květen 2015 (1)
- Únor 2015 (1)
- Prosinec 2014 (1)
- Září 2014 (1)
- Červenec 2014 (1)
- Únor 2014 (1)
- Leden 2014 (1)
- Listopad 2013 (1)
- Říjen 2013 (3)
- Červenec 2013 (1)
- Červen 2013 (1)
- Květen 2013 (1)
-
Kategorie
-
RSS
Entries RSS
Comments RSS