Simplex algoritem
Iz E-študij, proste zakladnice študentskega znanja
Primer naloge
Pekarna, ki je tik pred zaprtjem, dela preste in bureke. Zadnjo delovno noč ima v skladišču 900g moke in 48g soli (ostalega ima dovolj). Za burek rabi 50g moke in 2g soli, za presto pa 30g moke in 3g soli. Cena bureka je 90 tolarjev, cena preste je 70 tolarjev. Pek lahko naredi v eni noči le 20 kosov peciva. Koliko prest in koliko burekov naj speče, da bo imel čim večji zaslužek?
Postavimo enačbe:
x - burek
y - presta
Maksimiziramo funkcijo 90x + 70y.
Postopek reševanja
Podatke vnesemo v tabelo in izberemo 1. stolpec z leve strani, ki ima v spodnji vrstici pozitivno število (pivotni stolpec).
| x | y | b |
|---|---|---|
| 50 | 30 | 900 |
| 2 | 3 | 48 |
| 1 | 1 | 20 |
| 90 | 70 | 0 |
Izračunamo kvociente tako, da elemente v stolpcu b delimo z elementi v pivotnem stolpcu in izberemo vrstico (pivotna vrstica) v kateri je kvocient najmanjši.
| x | y | b | kvocienti | |
|---|---|---|---|---|
| 50 | 30 | 900 | 18 | |
| 2 | 3 | 48 | 24 | |
| 1 | 1 | 20 | 20 | |
| 90 | 70 | 0 |
Element na preseku pivotnega stolpca in vrstice imenujemo pivot. V nadaljevanju na mesto pivota zapišemo 1 / pivot. Ostale elemente v pivotni vrstici pomnožimo z 1 / pivot, ostale elemente v pivotnem stolpcu pa z − 1 / pivot. Ostali elementi tabele pa so: stara_vrednost-[(element, ki je v istem stolpcu kot iskani in hkrati v novi pivotni vrstici) * (element v isti vrstici kot iskani in hkrati v starem pivotnem stolpcu)]. Spremenljivka v pivotnem stolpcu "preskoči" v pivotno vrstico.
| y | b | ||
|---|---|---|---|
| 0,02 | 0,6 | 18 | x |
| − 0,04 | 1,8 | 12 | |
| − 0,02 | 0,4 | 2 | |
| − 1,8 | 16 | − 1620 |
Ker imamo v spodnji vrstici še vedno pozitiven element, nadaljujemo z istim postopkom tako da izberemo stolpec z pozitivnim elementom in izračunamo kvociente.
| y | b | kvocient | ||
|---|---|---|---|---|
| 0,02 | 0,6 | 18 | x | 30 |
| − 0,04 | 1,8 | 12 | ~6,67 | |
| − 0,02 | 0,4 | 2 | 5 | |
| − 1,8 | 16 | − 1620 |
Izračunamo vrednosti v novi tabeli:
| b | |||
|---|---|---|---|
| 0,32 | − 1,5 | 15 | x |
| 0,86 | − 4,5 | 3 | |
| − 0,5 | 2,5 | 5 | y |
| 6,2 | − 40 | − 1700 |
Ker v spodnji vrstici ni nobenega pozitivnega elementa več, smo s postopkom zaključili. Rešitev je torej x = 15 in y = 5 oz. povedano z besedami je najbolj optimalno če v pekarni spečejo 15 burekov in 5 prest.
