Linearno programiranje

  • Definicija. Linearni program (LP) je optimizacijski problem, kjer so ciljna funkcija in vsi pogoji linearni.

  • Primer.

Standardna oblika

  • Definicija. Linearni program je v standardni obliki, če

    • iščemo
    • so vsi pogoji
    • so vse spremenljivke

  • Trditev. Vsak linearni program lahko ekvivalentno zapišemo v standardni obliki.

  • Dokaz.

    • ;
    • ;
    • neomejena ;

Primer

Zapišimo prejšnji primer v standardni obliki.

Splošni zapis LP v standardni obliki

V splošnem lahko zapišemo linearni program v standardni obliki kot

Matrična oblika

  • Definirajmo:

  • Potem lahko zapišemo linearni program v matrični obliki:

Konveksnost

  • Definicija. Množica je konveksna, če za vsaka in vsak velja .

  • z je afina kombinacija točk ().

    • Afin prostor: "premaknjen" linearen prostor = afina kombinacija točk neke množice

  • z in () je konveksna kombinacija točk ().

  • Torej: množica je konveksna, če je vsaka daljica s krajišči v množici v celoti vsebovana v .

Primeri konveksnih množic

  • Konveksne množice v : intervali

  • Krogla v je konveksna, sfera pa ne

  • Polprostor v je konveksen:

    je tudi v polprostoru.

Lastnosti konveksnih množic

  • Trditev. Presek konveksnih množic je konveksen: () konveksne konveksna.

  • Dokaz. Preveriti moramo: za vsaka in vsak velja . To je res, ker so množice () konveksne.

  • Unija konveksnih množic ni nujno konveksna!

Konveksnost pri linearnih programih

  • Trditev. Naj bo linearni program. Potem velja:

    1. je konveksna množica.
    2. Množica optimalnih rešitev je konveksna množica.

  • Dokaz.

    1. je presek polprostorov (in hiperravnin), torej je konveksna množica.

    2. Če optimalnih rešitev ni, potem je množica optimalnih rešitev prazna, torej konveksna. Sicer naj bo optimalna vrednost. Potem je množica optimalnih rešitev enaka

      in je zato konveksna množica.

Grafično reševanje LP z dvema spremenljivkama

  • Primer.
  • je optimalna rešitev, je optimalna vrednost.

Politop dopustnih rešitev

  • Množica dopustnih rešitev je politop (lahko neomejen).
  • Množica optimalnih rešitev je lice tega politopa (oglišče, stranica, stranska ploskev, itd.).
  • Optimalna vrednost (če obstaja) je vedno dosežena (tudi) v oglišču.

Simpleksna metoda

Denimo, da imamo linearni program v standardni obliki

kjer velja

  • , ,
    • če velja , uporabimo dvofazno simpleksno metodo, ki jo bomo spoznali kasneje

Primer - kmetija

  • Dan je sledeči linearni program.

  • Ciljno funkcijo in omejitve lahko skaliramo brez vpliva na pomen spremenljivk:

Prvi slovar

  • Neenakosti spremenimo v enakosti z uvedbo novih nenegativnih spremenljivk.

  • Prvi slovar:

  • V zgornjem sistemu enačb nastopajo sledeče spremenljivke:

    • prvotne spremenljivke:
    • dopolnilne spremenljivke:
    • funkcional

Slovarji

  • Slovar je izražava izmed spremenljivk (bazne spremenljivke) in funkcionala z ostalimi izmed spremenljivk (nebazne spremenljivke).

  • V prvem slovarju velja:

    • nebazne spremenljivke so prvotne spremenljivke, in
    • bazne spremenljivke so dopolnilne spremenljivke.

  • Slovar je dopusten, če so konstantni koeficienti baznih spremenljivk nenegativni. Prvi slovar je dopusten zaradi predpostavke .

  • Dopusten slovar nam da bazno dopustno rešitev, ki jo dobimo tako, da nebaznim spremenljivkam dodelimo vrednost .

Vstopne in izstopne spremenljivke

  • Izberemo nebazno spremenljivko s pozitivnim koeficientom pri funkcionalu . Če je kandidatov več, izberemo poljubnega. Pogosto uporabljamo:

    • pravilo največjega koeficienta
    • pravilo najmanjšega indeksa
    • pravilo največjega povečanja

  • Izbrani spremenljivki pravimo vstopna spremenljivka.

  • Vrstici, ki izbrano vstopno spremenljivko najbolj omejuje, pravimo pivotna vrstica, pripadajoči bazni spremenljivki pa izstopna spremenljivka.

  • Če imamo več pivotnih vrstic (tj., več baznih spremenljivk najbolj omejuje vstopno spremenljivko), potem za izstopno spremenljivko izberemo poljubno izmed njih.

Pivotiranje

  • V našem primeru za vstopno spremenljivko izberemo (sta pa tudi in kandidata).

  • Edini kandidat za izstopno spremenljivko je .

Naslednji slovar

  • Vstopna spremenljivka vstopi v bazo, izstopna iz nje izstopi.

  • Rešimo enačbo za vstopno spremenljivko in vstavimo v enačbe za ostale bazne spremenljivke in funkcional :

Nadaljevanje metode

  • Če so vsi koeficienti pri funkcionalu nepozitivni, smo našli optimalno rešitev in se simpleksna metoda ustavi.
  • V nasprotnem primeru ponavljamo postopek.
  • Vsi slovarji, ki smo jih dobili tekom reševanja, so dopustni.
    • Če smo dobili kak nedopusten slovar, smo se zmotili (npr. izbrali napačno izstopno spremenljivko ali naredili računsko napako).

Kaj se lahko še zgodi?

  • Konstantni koeficient bazne spremenljivke je enak :

  • Vrednost v bazni dopustni rešitvi se ne poveča - izrojen korak.

Kaj se lahko še zgodi? (2)

  • Nobena vrstica na omejuje vstopne spremenljivke:

  • Tedaj je linearni program neomejen - končamo simpleksno metodo.

  • Neomejeno družino dopustnih rešitev dobimo tako, da vstopno spremenljivko pustimo kot nenegativen parameter brez zgornje meje, ostalim nebaznim spremenljivkam pa dodelimo vrednost .

Vse optimalne rešitve

Kako iz zadnjega slovarja za optimalni problem dobimo vse optimalne rešitve?

  • Nebaznim spremenljivkam z negativnim koeficientom dodelimo vrednost .
  • Nebazne spremenljivke z ničelnim koeficientom pustimo kot parametre (tj., jim ne dodelimo nujno vrednosti ).
  • Upoštevamo, da so vse bazne spremenljivke nenegativne.

Primer

  • Denimo, da imamo sledeči zadnji slovar.

  • Potem velja:
    • , torej
    • , torej
    • , torej
  • Optimalne rešitve so torej oblike , , , .

Končnost simpleksne metode

  • Ali se simpleksna metoda vedno ustavi? NE.

  • Možnih slovarjev je .

    • Če se simpleksna metoda ne ustavi, pomeni, da je prišlo do "ciklanja".
    • V tem primeru so vsi koraki v ciklu izrojeni.

  • Ciklanje je izjemno redko. Dokazati se da, da do ciklanja ne bo prišlo, če za vstopne in izstopne spremenljivke uporabimo pravilo najmanjšega indeksa (Blandovo pravilo).

Časovna zahtevnost simpleksne metode

  • Časovne zahtevnosti algoritmov:

    • "Hitri" algoritmi: uporabijo polinomsko mnogo operacij.
    • "Počasni" algoritmi: uporabijo eksponentno mnogo operacij.

  • Ali je simpleksna metoda hitra?

    • Tipično: korakov
    • Najslabši primer: simpleksna metoda ni polinomska

Klee-Mintyjeva kocka

  • Primer. (Klee-Minty) Za :

    • Če uporabimo pravilo največjega koeficienta, potrebujemo korakov.
    • Če uporabimo pravilo največjega povečanja, potrebujemo korak.

  • Obstajajo algoritmi za reševanje linearnih programov, ki so dokazljivo polinomski.

Dvofazna simpleksna metoda

Uporabljamo jo za linearne programe v standardni obliki, za katere ne velja .

  1. faza: ugotovi, ali je linearni program dopusten - če je, nam prva faza da dopusten začetni slovar za drugo fazo.
  2. faza: identična simpleksni metodi.

Primer

Imamo dve vitaminski tableti, Polivit in Oligovit, ki vsebujejo različne količine vitaminov A, B in C.

A B C cena za tableto
Polivit 1 4 1 12
Oligovit 1 1 2 10
dnevne potrebe 7 13 8

Kako najceneje zadostiti dnevnim potrebam?

Linearni program

  • Zapišimo kot linearni program.

  • Zapišimo še ekvivalentni linearni program v standardni obliki.

Pomožni problem prve faze

  • Ker v zgornjem linearnem programu velja , zapišimo še pomožni problem prve faze:

  • Pomožni problem je vedno dopusten ( mora biti dovolj velik).

  • Pomožni problem ima optimalno vrednost natanko tedaj, ko je prvotni problem dopusten.

Začetni slovar za prvo fazo

  • Zapišimo začetni slovar za prvo fazo - ta slovar ni dopusten:

  • V prvem koraku prve faze v bazo vstopi , izstopi pa spremenljivka z najmanjšim (najbolj negativnim) konstantnim členom - v našem primeru :

Nadaljevanje prve faze

  • Nadaljujemo enako kot pri osnovni simpleksni metodi.

  • V našem primeru po metodi največjega povečanja izberemo za vstopno spremenljivko in za izstopno spremenljivko.

Začetni slovar za drugo fazo

  • Optimalna vrednost pomožnega problema je - prvotni problem je torej dopusten.

  • Začetni slovar druge faze dobimo tako, da v zadnjem slovarju prve faze vzamemo in vstavimo prvotne bazne spremenljivke v funkcional :

Nadaljevanje druge faze

vstopi, izstopi:

Optimalna rešitev

Imamo zadnji slovar druge faze, preberemo optimalno rešitev:

  • tableti Polivit
  • tablet Oligovit
  • cena:

Kaj se lahko zgodi ob koncu prve faze?

Prva faza se vedno konča, ko ne moremo več izbrati vstopne spremenljivke (ker je problem omejen).

  • : prvotni problem je nedopusten, končamo.
  • , je nebazna spremenljivka v zadnjem slovarju prve faze: nadaljujemo z drugo fazo.
  • , je bazna spremenljivka v zadnjem slovarju prve faze: temu se izognemo s pravilom, da če lahko izstopi iz baze, jo izberemo za izstopno spremenljivko (ali pa naredimo izrojen korak, da izstopi).

Povzetek

Osnovni izrek linearnega programiranja

  • Če ima linearni program dopustno rešitev, ima bazno dopustno rešitev.
  • Če ima linearni program optimalno rešitev, ima bazno optimalno rešitev.
  • Za linearni program velja natanko ena od možnosti:
    • linearni program je nedopusten,
    • linearni program je neomejen, ali
    • linearni program je optimalen.

Dualnost pri linearnem programiranju

  • Naj bo linearni program

  • Iščemo zgornje meje za ciljno funkcijo:

Zgornja meja za ciljno funkcijo

  • Če velja

    potem

  • Hočemo čim manjšo zgornjo mejo.

Dualni linearni program

Prvotnemu linearnemu programu dodelimo dualni linearni program :

Definicija

Definicija. Za prvotni linearni program je njegov dualni linearni program , kjer je

  •

Dualnost

  • Trditev. .

  • Dokaz.

    • Zapišimo v standardni obliki.

    • Potem je sledeči LP:
    • Pretvorba v standardno obliko nam pokaže, da je .

Šibki izrek o dualnosti (ŠID)

  • Naj bo prvotni linearni program kot zgoraj in njegov dual.

  • Če je dopustna rešitev za in dopustna rešitev za , potem velja .

  • Dokaz.

Še en dokaz

Posledici

  • Posledica 1. Če sta in dopustni rešitvi za oziroma , za kateri velja , potem sta in optimalni rešitvi za oziroma .

  • Dokaz. je zgornja meja za , to zgornjo mejo dosežemo. je spodnja meja za , to spodnjo mejo dosežemo.

  • Opomba. S to posledico lahko preverimo optimalnost ponujenih dopustnih rešitev , , za kateri velja .

  • Posledica 2. Če je neomejen problem, je nedopusten problem.

  • Dokaz. Če je dopusten, imamo zgornjo mejo za ciljno funkcijo , protislovje.

Krepki izrek o dualnosti (KID)

  • Naj bo prvotni linearni program kot zgoraj in njegov dual.
  • Če je optimalna rešitev za , potem obstaja optimalna rešitev za in velja .

Problem kmetije

  • Zadnji slovar za problem kmetije:

  • Zadnji slovar za dual problema kmetije:

  • Videti je, da so koeficienti dopolnilnih spremenljivk v zadnjem slovarju ravno negacija optimalne rešitve dualnega problema.

Dokaz KID

  • Simpleksna metoda za se konča z zadnjim slovarjem z

    kjer velja () in , če je bazna spremenljivka.

  • Naj bo ().

  • Pokazali bomo, da je optimalna rešitev .

Dokaz KID (2)

Velja

Dokaz KID (3)

  • Ker velja , sledi

  • Ker velja () in (), je dopustna rešitev za .

  • Ker velja , je po Posledici 1 optimalna rešitev za .

Povzetek

  • ŠID: dopustni za

  • KID: optimalen optimalen z isto optimalno vrednostjo

  • Imamo torej sledeče možnosti:

    \ nedopusten neomejen optimalen
    nedopusten ✔ ✔ ✗ (KID)
    neomejen ✔ ✗ (ŠID) ✗ (KID/ŠID)
    optimalen ✗ (KID) ✗ (KID/ŠID) ✔

Primer: nedopustni LP in dual

  • Izrek. Za linearna programa in velja natanko ena od sledečih možnosti:

    • oba sta optimalna,
    • oba sta nedopustna, ali
    • eden je neomejen, drugi pa nedopusten.

Izrek o dualnem dopolnjevanju (IDD)

  • Naj bo prvotni linearni program kot zgoraj in njegov dual,
    ter naj bosta in dopustni rešitvi za oziroma .

  • Potem sta in optimalni rešitvi za oziroma natanko tedaj, ko velja

IDD - ekvivalentna oblika

Ekvivalentno: potem sta in optimalni rešitvi za oziroma natanko tedaj, ko velja

Dokaz IDD

  • Po Posledici 1 in KID sta optimalni za natanko tedaj, ko velja , kar je enakovredno

Primer

Pokaži, da je optimalna rešitev problema kmetije.

  • 1. korak: preverimo, da je ponujena rešitev dopustna.

  • 2. korak: za vsako neenakost, ki je izpolnjena z , pripadajoči dualni spremenljivki dodelimo vrednost .

Primer (2)

  • 3. korak: za vsako pozitivno vrednost v rešitvi postavimo enačaj v pripadajoči neenakosti.

  • 4. korak: rešimo sistem iz korakov 2 in 3 ter preverimo dopustnost rešitve.

    • Če je rešitev več (parametrična rešitev), zadostuje, da poiščemo tako vrednost parametrov, da bo dobljena rešitev dopustna.

Ekonomski pomen dualnih spremenljivk

  • Primer. Problem kmetije:

    ž€č€

  • Ne izplača se nam najeti več delovne sile ali vzeti kredita. Morda se nam izplača dokupiti dodatno zemljo.

Ekonomski pomen dualnih spremenljivk (2)

  • Izrek. Naj bo prvotni linearni program kot zgoraj z neizrojeno bazno optimalno rešitvijo (tj., v pripadajočem slovarju so vsi konstantni členi pri baznih spremenljivkah pozitivni), in njegov dual. Potem obstaja , da velja

    kjer je optimalna rešitev ter sta in spremembi desne strani in optimalne vrednosti.

  • V našem primeru: za . Zemljo se nam splača kupiti po ceni največ €/ha = €/ha.

  • Torej: optimalne vrednosti duala nam dajo "tržno"/"pošteno"/sprejemljivo ceno surovin.

Dual splošnega linearnega programa

Izrek. Naj bo linearni program v spodnji obliki. Potem je njegov dual :

IDD za splošni linearni program

  • Naj bosta in dopustni rešitvi za oziroma .

  • Potem sta in optimalni rešitvi za oziroma natanko tedaj, ko velja

  • Torej:

    • neenakost nenegativna spremenljivka
    • enakost neomejena spremenljivka

Primer

Splošni LP v standardni obliki

Dual splošnega linearnega programa - dokaz

Zapišimo še dual - ta je enakovreden našemu zapisu :