Linárne programovanie - Simplexový algrotimus
Patrícia Lukoťková
1.6.2022
Motivácia
Lineárne programovanie je matematická metóda riešenia úloh. Vo všeobecnosti môžeme takéto úlohy charakterizovať tak, že máme určiť optimálnu hodnotu lineárnej funkcie, ktorá spĺňa lineárne ohraničenia. K úlohám tohto typu vedú mnohé praktické problémy. Prvú takúto úlohu sformuloval v roku 1939 ruský matematik Leonid Vitaljevič Kantorovič. V roku 1947 George Bernard Danzig pri riešení problémov logistiky v americkej armáde navrhol simplexovú metódu riešenia všeobecnej úlohy LP a je považovaný za zakladateľa lineárneho programovania. Odvtedy sa lineárne programovanie stalo jednou z najpoužívanejších metód riešenia úloh z mnohých oblastí. V základných úlohach vieme riešenie nájsť aj jednoduchu graficky, pri iných nám pomôžu rôzne algotimy ako napríklad Simplexový algoritmus
Lineárne programovanie
Úloha lineárneho programovania je optimalizačný problém, ktorá má nasledujúci tvar:
\[\color{red}{opt}\ z = c_1x_1+c_2x_2+...+c_nx_n\] ak platí: \[a_{1,1}x_1+a_{1,2}x_2+...+a_{1,n}x_n \ \color{red}{?_1}\ b_1\] \[a_{2,1}x_1+a_{2,2}x_2+...+a_{2,n}x_n \ \color{red}{?_2}\ b_2\] \[.\] \[.\] \[.\]
\[a_{m,1}x_1+a_{m,2}x_2+...+a_{m,n}x_n \ \color{red}{?_m}\ b_m\]
Pričom \(\color{red}{opt}\) je buď max alebo min, symbol \(\color{red}{?}\) je buď \(=\) alebo \(\le\) alebo \(\ge\). \(x_1,..,x_n\) sú premenné; \(c_1,..,c_n , a_{1,1}\ ,\ ...,a_{m,n}\ ,\ b_1,..,b_n\) sú čísla.
Prípustné riešenie úlohy lineárneho programovania je taká n-tica premenných, ktorá spĺňa všetky obmedzenia.
Pre maximalizačný (minimalizačný) problém je optimalne riešenie také, ktoré je prípustné, a spomedzi všetkých prípustných riešení práve v tomto nadobúda účeová funkcia najväčšiu (najmenšiu) hodnotu.Kanonický tvar
Simplexový algoritmus rieši úlohu lineárneho programovania v kanonickom tvare.Pre kamonický tvar platí, že účelová funkcia musí byť maximalizačná, obmedzenia musia byť rovnosti a zároveň ich pravé strany musia byť nezáporné, v podmienke musí byť znamienko \(\ge\).
Každá úloha lineaŕneho programovania sa dá transformovať na ňou ekvivaletnú úlohu v kanonickom tvare, pričom stačí použiť štyri pravidlá:
Zmena problému na maximalizačný
ak máš úlohu \(min\ z = c_1x_1+c_2x_2+\ ...\ +c_nx_n\), nahraď to \(max(-z) = (-c_1)x_1+(-c_2)x_2+\ ...\ +(-c_n)x_n\)Zmena nerovníc na rovnice
Do každej nerovnice pridaj rôznu novú premennú.
ak máš ohraničenie \(a_{i,1}x_1+\ ...\ + a_{i,n}x_n\ge b_i\) nahraď to \(a_{i,1}x_1+\ ...\ + a_{i,n}x_n-v_1= b_i\), \(v_i \ge 0\)
ak máš ohraničenie \(a_{i,1}x_1+\ ...\ + a_{i,n}x_n\le b_i\) nahraď to \(a_{i,1}x_1+\ ...\ + a_{i,n}x_n+v_i= b_i\), \(v_i \ge 0\)Zmena koeficinetov na pravej strane na nezáporné
Ak je niektorý z koeficientov na pravej strane záporný, prenásob príslušnú rovnicu konštantou \((-1)\)Zmena premenných na nezáporné
Ak môže premenná \(x_i\) može nadobúdať aj záporné hodnoty (vidíme to z podmienky),tak každý jej výskyt v úlohe nahradíme výrazom \((x_i^+-x_i^-)\) a do podmienky pridáme \(x_i^+ \ge 0\) a \(x_i^- \ge 0\)
Simplexový algoritmus
Simplexový algoritmus rieši úlohu lineáreho programovania.
Krok 0:
Úlohu lineárneho programovania prevedenie na úlohu v kanonickom tvare. Všetky koeficienty zapíšeme do tabuľky. Premenné na ľavej strane nazývame bázické, pretože tvoria bázu súčasného riešenia.
Krok 1:
Ak je súčasné riešenie optimálne, skončíme. Inak nájdeme v tabuľke jeden koeficient, ktorý nazývame pivot, a elimináciou zodpovedajúceho stĺpca zostrojíme novú tabuľku. Potom znova opakujeme krok 1.
Test optimálnosti:
Skontrolujeme koeficienty v tabuľke v strednej časti posledného riadku.Ak sú všetky nezáporné, tak je súčasné riešenie optimálne, a teda na pravej strane posledného riadku vidíme optimálnu hodnotu účelovej funkcie.
Hladanie pivota:
Ak súčasné riešenie nie je optimálne, zvolíme si jeden zo stĺpcov, v ktorom sa nacháza najmenšia záporná hodnota. Teraz nájdeme minimum zo zlomkov \(\frac{b_i}{(hodnota\ v\ i-tom\ riadku\ zvoleného\ stĺpca)}\) z nájdutého minima vyberiem menovateľa, ktorého vyzačím v tabuľke, tento koeficient nazývamé pivot. Premennú ktorá leží v riadku kde je pivot nahradíme za premennú, ktorá je v stĺpci kde sa nachadza náš pivot.
Eliminácia:
Gaussovou eliminačnou metódou upravíme tabuľku tak, aby pivot = 1 a prvky nad a pod ním = 0
Príklad
ZADANIE:
Podnik vyrába dva typy výrobkov A a B za účelom ďalšieho predaja. Na výrobu výrobku A sú potrebné 4 hodiny montáze a výrobok B sa zmontuje za 10 hodín. Po montáži sa oba výrobky testujú, pričom výrobok A sa testuje 2 hodiny a výrobok B len 1 hodinu. Oba tieto výrobky sú umiestnené v sklade s plochou po 1 m2. K dispozícii je 100 montánych hodin, 22 hodín na testovanie a 13 m2 skladovacích priestorov. Zisk z predaja jednotkového množstva výrobku A je 60 Eur a vyrobku B je 50 Eur. Určite optimálne množstvo výrobkov A a B, ktoré má podnik vyrobit’ tak, aby zisk z predaja bol maximálny.
RIEŠENIE:
x1……….výrobok A
x2……….výrobok B
MATEMATICKÝ MODEL:
účelová funkcia:
\[max\ z = 60x_1+50x_2\] obmedzenia:
\[\color{red}{4x_1+10x_2 \le 100}\ \ \ (montáž) \] \[\color{green}{2x_1+1x_2 \le 22}\ \ \ (testovanie) \] \[\color{blue}{1x_1+1x_2 \le 13}\ \ \ (skladovanie)\]
podmienka:
\[x_1,x_2 \ge 0\]
GRAFICKY:
Ak máme v úlohe lineárneho programovania len dve premenné, potom vieme túto úlohu jenoducho vyriešiť aj graficky.
v grafe možeme farebne vidieť zobrazené všetky zadané obmedzenia. Oblasť, ktorá tvorí pripustné riešenia vznikne ako prienik všetkých obmedzeni. V našom prípade je táto oblast tvorená bodmi \(A=(0,0)\), \(B=(11,0)\), \(C=(9,4)\), \(D=(5,8)\), \(E=(0,10)\). Našu úlohu vyriešime, keď zostrojíme priamku rovnobežnú s účelovou funkciou(\(0=60x_1+50x_2\)), ktorá “z vonka” dotýka oblasti prípustného riešenia. Bod dotyku je potom optimálnym riešením. Riešenie môžeme nájsť teda aj tak, že všetky súradníce vrcholov oblasti dosadíme do účelovej funkcie, a následne zistíme, v ktorom z nich je hodnota najvačsia. V našom príklad je to bod \(C=(x_1=9,x_2=4)\) pričom optimálna hodnota účelovej funkcie je \(z=740\)
library(ggplot2)
library(tidyverse)## Warning: package 'tidyverse' was built under R version 4.1.3## Warning: package 'readr' was built under R version 4.1.3## Warning: package 'forcats' was built under R version 4.1.3montaz<-function(x) {return(-2/5*x+10)}
testovanie<-function(x) {return(-2*x+22)}
skladovanie<-function(x) {return(-x+13)}
ucelova<-function(x) {return(-60/50*x)}
ggplot(data.frame(x1=c(0,11)),aes(x=x1))+
ylab("x2")+
stat_function(fun=montaz,color="red")+
annotate(geom="text",label="Montáž",x=10,y=7,size=3,color="red")+
geom_ribbon(aes(ymin=0,ymax = montaz(x1)), fill = rgb(1,0,0,0.2))+
stat_function(fun=testovanie,color="green")+
annotate(geom="text",label="Testovanie",x=4,y=17,size=3,color="green")+
geom_ribbon(aes(ymin=0,ymax = testovanie(x1)), fill = rgb(0,1,0,0.2))+
stat_function(fun=skladovanie,color="blue")+
annotate(geom="text",label="Skladovanie",x=1,y=14,size=3,color="blue")+
geom_ribbon(aes(ymin=0,ymax = skladovanie(x1)), fill = rgb(0,0,1,0.2))+
stat_function(fun=ucelova)+
annotate(geom="text",label="Úcelová funkcia",x=3,y=-5,size=3)+
geom_point(aes(x=0,y=0))+
annotate(geom="text",label="A",x=0,y=1,size=4)+
geom_point(aes(x=11,y=0))+
annotate(geom="text",label="B",x=11,y=1,size=4)+
geom_point(aes(x=9,y=4))+
annotate(geom="text",label="C",x=9,y=5,size=4)+
geom_point(aes(x=5,y=8))+
annotate(geom="text",label="D",x=5,y=9,size=4)+
geom_point(aes(x=0,y=10))+
annotate(geom="text",label="E",x=0,y=11,size=4)+
annotate(geom="text",label="prípustné riesenia",x=3,y=5,size=4,color=rgb(0,0,0,0.5))
KANONICKÝ TVAR:
keďže náš príklad je maximalizačný, účelovú funkciu máme v správnom tvare, obmedzenia upravíme podľa postupu, ktorý je vysvetletný vyššie. Kanonický tvar pre danú úlohu je nasledovný:
\[max\ z = 60x_1+50x_2\] obmedzenia:
\[\color{red}{4x_1+10x_2+v_1 = 100}\ \ \ (montáž) \] \[\color{green}{2x_1+1x_2 +v_2 =22}\ \ \ (testovanie) \] \[\color{blue}{1x_1+1x_2 +v_3 = 13}\ \ \ (skladovanie)\]
podmienka:
\[x_1,x_2,v_1,v_2,v_3\ge 0\]
Teraz si kanonický tvar prepíšeme do tabuľky, čím získame úvodnú simplexovú tabuľu.
dat <- tibble::tibble(
" "=c("$v_1$","$v_2$","$v_3$","$z$"),
"$x_1$" = c(4,2,1,-60),
"$x_2$" = c(10, 1, 1, -50),
"$v_1$" = c(1, 0, 0, 0),
"$v_2$"= c(0, 1, 0, 0),
"$v_3$" =c(0,0,1,0),
" "=c(100,22,13,0)
)
dat %>%
knitr::kable(format = "html",caption="úvodná simplexová tabuľka") %>%
kableExtra::column_spec (c(1,6), border_right = T)%>%
kableExtra::column_spec (7, bold=T)%>%
kableExtra::column_spec (2, background =rgb(1,0,0,0.5))%>%
kableExtra::row_spec (4, bold=T)%>%
kableExtra::kable_styling(full_width = F)| \(x_1\) | \(x_2\) | \(v_1\) | \(v_2\) | \(v_3\) | ||
|---|---|---|---|---|---|---|
| \(v_1\) | 4 | 10 | 1 | 0 | 0 | 100 |
| \(v_2\) | 2 | 1 | 0 | 1 | 0 | 22 |
| \(v_3\) | 1 | 1 | 0 | 0 | 1 | 13 |
| \(z\) | -60 | -50 | 0 | 0 | 0 | 0 |
Z testu optimálnosti vidíme že tabuľka nezobrazuje optimálne riešenie. zvolíme si jeden zo stĺpcov, v ktorom sa nacháza najmenšia záporná hodnota.Pre tento príklad je to číslo \(-60\) a teda stĺpec, v ktorom hladáme pivota má premennú \(x_1\). Teraz nájdeme minimum zo zlomkov(presnejší postuput tvorby zlomkov je spomenutý vyššie) \(min( \frac{13}{1} , \mathbf{\frac{22}{2}} , \frac{100}{4} )\) Minimálnu hodnotu vidíme v druhom zlomku a podľa teórie vieme že pivot bude číslo \(2\). podľa postupu teraz premennú \(v_2\) nahradíme premennou \(x_1\) a použíjeme nasledujúcie eliminačné operácie: 2. riadok vydelíme číslo \(2\). k 3. riadku pripočítame \((-4)\) násobok 2. riadku. k 3. riadku pripočítame \((-1)\) násobok 2. riadku. k 4. riadku pripočítame \(+60\) násobok 2. riadku.
dostaneme nasledujúcu tabuľku:
dat <- tibble::tibble(
" "=c("$v_1$","$x_1$","$v_3$","$z$"),
"$x_1$" = c(0,1,0,0),
"$x_2$" = c(8, 1/2, 1/2, -20),
"$v_1$" = c(1, 0, 0, 0),
"$v_2$"= c(-2, 1/2, -1/2, 30),
"$v_3$" =c(0,0,1,0),
" "=c(56,11,2,660)
)
dat %>%
knitr::kable(format = "html") %>%
kableExtra::column_spec (c(1,6), border_right = T)%>%
kableExtra::column_spec (7, bold=T)%>%
kableExtra::column_spec (3, background =rgb(1,0,0,0.5))%>%
kableExtra::row_spec (4, bold=T)%>%
kableExtra::kable_styling(full_width = F)| \(x_1\) | \(x_2\) | \(v_1\) | \(v_2\) | \(v_3\) | ||
|---|---|---|---|---|---|---|
| \(v_1\) | 0 | 8.0 | 1 | -2.0 | 0 | 56 |
| \(x_1\) | 1 | 0.5 | 0 | 0.5 | 0 | 11 |
| \(v_3\) | 0 | 0.5 | 0 | -0.5 | 1 | 2 |
| \(z\) | 0 | -20.0 | 0 | 30.0 | 0 | 660 |
Z testu optimálnosti vidíme že tabuľka nezobrazuje optimálne riešenie. Postup teda opakujeme.zvolíme si jeden zo stĺpcov, v ktorom sa nacháza najmenšia záporná hodnota.Pre tento príklad je to číslo \(-20\) a teda stĺpec, v ktorom hladáme pivota má premennú \(x_2\). Teraz nájdeme minimum zo zlomkov(presnejší postuput tvorby zlomkov je spomenutý vyššie) \(min( \frac{56}{8} , \frac{11}{0.5} , \mathbf{\frac{2}{0.5}} )\) Minimálnu hodnotu vidíme v treťom zlomku a z teórie vieme že pivot bude číslo \(0,5\). podľa postupu teraz premennú \(v_3\) nahradíme premennou \(x_2\) a použíjeme nasledujúce eliminačné operácie aby bol pivot=1 a prvky nad a pod ním=0: 3. riadok vynásobíme číslom \(2\). k 1. riadku pripočítame \((-8)\) násobok 3. riadku. k 2. riadku pripočítame \((-0.5)\) násobok 3. riadku. k 4. riadku pripočítame \(+20\) násobok 3. riadku.
dat <- tibble::tibble(
" "=c("$v_1$","$v_2$","$x_2$","$z$"),
"$x_1$" = c(0,1,0,0),
"$x_2$" = c(0, 0, 1, 0),
"$v_1$" = c(1, 0, 0, 0),
"$v_2$"= c(6, 1, -1, 10),
"$v_3$" =c(-16,-1,2,40),
" "=c(24,9,4,740)
)
dat %>%
knitr::kable(format = "html") %>%
kableExtra::column_spec (c(1,6), border_right = T)%>%
kableExtra::column_spec (7, bold=T)%>%
kableExtra::row_spec (4, bold=T)%>%
kableExtra::kable_styling(full_width = F)| \(x_1\) | \(x_2\) | \(v_1\) | \(v_2\) | \(v_3\) | ||
|---|---|---|---|---|---|---|
| \(v_1\) | 0 | 0 | 1 | 6 | -16 | 24 |
| \(v_2\) | 1 | 0 | 0 | 1 | -1 | 9 |
| \(x_2\) | 0 | 1 | 0 | -1 | 2 | 4 |
| \(z\) | 0 | 0 | 0 | 10 | 40 | 740 |
Z testu optimálnosti vidíme že tabuľka už zobrazuje optimálne riešenie: \(x_1=9\) –> výrobok A \(x_2=4\) –> výrobok B \(z=740\) –> zisk
Podnik musí vyrobiť 9ks výrobkov A a 4ks výrobkov B aby bol zisk z predaja maximálny a to 740eur.Zhrnutie
Cieľom mojej práce bolo oboznámiť. čitateľa s lineárnym programovaním a algoritmom na jeho riešenie, čo som následne ukázala aj na jednoduchom príklade pričom som spravila aj grafickú ilistráciu jeho riešenia.
Referencie
M. Knor, Linearna a nelinearna optimalizacia, Slovenska Technicka Univerzita, Bratislava, 2009 http://www.svf.stuba.sk (ISBN 978-80-227-3102-7). /skripta/