Kvantitatiivsed meetodid majandusteaduses (0)

KVANDI EKSAM
Lineaarsed planeerimisülesanded:
Mõisted:

• Matemaatilised meetodid võimaldavad majandusprobleeme formaliseerida ja neid lahendada. Tegelevad optimaalsete lahendite väljatöötamisega
  
• Lineaarne planeerimisülesanne – ülesanne leida tundmatutele sellised mittenegatiivsed väärtused mis kajastaksid sihifunktsiooni optimaalset väärtust, rahuldades kõiki kitsendusi.
  
• Lubatav lahend ehk plaan - sellised lahendid , mis rahuldavad kõiki kitsendusi ja tingimussüsteemi mittenegatiivsuse nõuet
  
• Optimaalne lahend – tundmatute väärtused, mis muudavad sihifunktsiooni kas maksimaalseks või minimaalseks
  
• Optimaalsuskriteerium – juhtimiseesmärgi kvantitatiivne hinnang( sihifunktsioon )
  
• Optimeerimine – vastavalt sihifunktsioonile ja kitsendustele parima lahendi leidmine
  

Max põhikujuline ülesanne:
Ülesanne on max põhikujuline, kui sihifunktsioonile otsitakse maksimaalset väärtust, kitsenduste süsteemis on märk väiksem võrdne ja tundmatud on mittenegatiivsed.
Min põhikujuline ülesanne:
Ülesanne on min põhikujuline, kui sihifunktsioonile otsitakse minimaalset väärtust, tundmatud on mittenegatiivsed ja kitsendussüsteemis on märk suurem võrdne.
Max kanooniline põhiikuju:
Ülesanne on max kanooniline , kui kitsendussüsteemi märk on võrdusmärk, sihifunktsiooni väärtus on maksimaalne ja tundmatud on kõik mittenegatiivsed
Min kanooniline põhikuju:
Ülesanne on min kanooniline, kui kitsendussüsteemi märk on võrdusmärk ja sihifunktsioonile otsitakse minimaalset väärtust ja tundmatud on mittenegatiivsed.
Ülesande kuju:
c0
 sihifunktsiooni kordajad
c0 -- sihifunktsiooni vabaliige;
aij -- kitsenduste süsteemi kordajad,
(i = 1, 2, ... , m; j = 1, 2, ..., n);
bi -- kitsendussüsteemi vabaliikmed (i = 1, 2, ...,m).
Lineaarse planeerimisülesande saamiseks tuleb teha järgmist:

Defineerida majandusprobleem ( mida tahetakse saavutada)

Defineerida sihifunktsioon

Selgitada ressursside olemasolevad suurused ja kulunormid ( kitsendussüsteem)

Esitada majandusprobleemi matemaatiline mudel

Kontrollida saadud ülesannet
Graafiline lahendamine:
Graafilise lahendamise korral pole vajalik viia LPÜd max põhikujule. Tundmatud peavad vastama kõikidele kitsendustele
Kuidas lahendada:

Tingimustele vastavate piirsirgete määramine

Piirsirgete kandmine joonisele

Lubatava pooltasandi määramine

Lubatavate lahendite piirkonna leidmine

Sihifunktsiooni samakõrgusjoone leidmine

Samakõrgusjoone liigutamine kindlaksmääratud suunas

Optimaalse lahendi leidmine

Optimaalse punkti koordinaatide välja arvutamine
Lahendite hulk :

• Üks optimaalne lahend – üks tipp
  
• Lõpmata palju lahendeid – Samakõrgusjoon on paralleelne lubatava lahendihulga külje või kiirega
  
• Puuduvad lahendid – pole rahuldatud kõiki kitsendusi, piirkond on tühihulk, ülesanne on piiramata
  

Duaalne planeerimisülesanne:
Olgu antud esialgne ülesanne max-põhikujul:
Vastav duaalne ülesanne on:



Duaalse ülesande lahendamine:

Esialgse ülesande m tingimusele vastavad duaalsed tundmatud yi ( y1, y2, ..., ym).

Esialgse ülesande n tundmatule xj (x1 , x2 ,…, xn) seada vastavusse sama arv tingimusi.

Duaalse ülesande sihifunkt­siooni kordajateks võtta esialgse ülesande tingimustesüsteemi vabaliikmed bi (b1 , b2 , … , bm).

Duaalse ülesande tingimustesüsteemi vabaliikmeteks võtta esialgse ülesande sihifunkt­siooni kordajad cj ().

Duaalse ülesande tingimustesüsteemi kordajate maatriksi saamiseks transponeerida esialgse ülesande tingimustesüsteemi tundmatute kordajate maatriks , seega

a11 a12 … a1n

A = a21 a22 … a2n

………………………

am1 am2 … amn

a11 a21 … am1

A’ = a12 a22 … am2

………………………

a1n a2n … amn

Duaalse ülesande sihifunktsiooni väärtusele w nõuda miinimumi, kui esialgse ülesande sihifunktsiooni väärtusele z nõutakse maksimumi; ja vastupidi.

Duaalse ülesande j-nda tingimuse märk ( ≤ ,  või = ) määratakse esialgse ülesande vastavale tundmatule (s.t. xj-le) kehtestatud nõude alusel (vt. tabelist).

Märkus: Max-põhikujulise ülesandega duaalse ülesande kõik kitsen­­­dused on -tüüpi

võrratused.

Duaalse ülesande tundmatule yi kehtestatav nõue (≤ ,  või märgi poolest kitsendamata) fikseeritakse esialgse ülesande vastava (s.t. i-nda tingimuse märgi alusel (vt. tabelist).

Märkus: Max-põhikujulise ülesandega duaalse ülesande kõikidelt tundmatutelt nõu­takse mittenegatiivsust (yi  0).

Lahendid:

Duaalse ülesande lahendid saab optimaalse simplekstabeli sihifunktsiooni reas, abitundmatute veergudes. Kui tegemist on kasumi maksimeerimise piiratud ressursside tingimustes, siis duaalse ülesande tundmatute väärtused väljendavad täiendavat kasumit, mida oleks võimalik saada, kui i-ndat ressurssi oleks ühe ühiku võrra rohkem. Sel juhul duaalset tundmatut yi nimetatakse ka ressursi fiktiivseks hinnaks, s.t. tegemist on maksimaalse hinnaga, mida tootja võiks iga täiendava ressursiühiku eest maksta. Selle hinnaga (või kallimalt) võiks tootja ka ressurssi (toorainet) müüa. Näiteks minimaalselt selle hinnaga on otstarbekas maad välja rentida või maksimaalselt selle hinnaga maad juurde rentida.

Simplekstabel:

Eeldused ülesande püstitamiseks:

Kõik ülesande tingimused peavad olema esitatud võrranditena

Tingmustesüsteem peab omama ühikmaatriksit

Kõik vabaliikmed peavad olema mittenegatiivsed

Sihifunktsioon peab olema maksimeeritav

Kõigi ühikmaatriksi kordajad peavad omama sihifunktsioonis väärtust 0

Ülesande püstitamine:

Ülesande formuleerimine ja teisendamine nõutavale kujule

Sihifunktsiooni teisendamine viies kõik peale vabaliikme teisele poole

Algsimplekstabeli koostamine
x1
x2
...
xn
xn+1
xn+2
…
xn+m
z
Vabaliige
z
c1
c2
...
cn
0
0
…
0
1
c0
1. rida
2. rida
...
m. rida
a11
a21
...
am1
a12
a22
...
am2
...
…
…
…
a1n
a2n
...
amn
1
0
…
0
0
1
…
0
…
…
…
…
0
0
…
1
0
0
…
0
b1
b2
...
bm

Optimaalsuse kontroll: kui sihifunktsiooni reas tundmatute korda­jate hulgas esineb kasvõi üksainus negatiivne arv (-cj  0), siis pole lahend optimaalne; kui kõik tundmatute kordajad on mitte­negatiivsed (-cj  0), siis on jõutud optimaalse lahendini ja simpleksmeetodi rakendamine on lõppenud.

Juhtveeru valimine. Juhtveeruks valida veerg , milles sihi­funktsiooni kordaja on negatiivne. Kui selliseid veerge on mitu, siis juhtveeruks valitakse see veerg, milles sihifunktsiooni kordaja on väikseim negatiivne arv.

Juhtrea valimine. Juhtrea kindlaksmääramiseks jagatakse tingi­mus­tesüsteemi vabaliikmed bi väljavalitud juhtveeru positiivsete nullist erinevate kordajatega aij ja saadud jagatistest valitakse väikseim, millele vastav rida osutubki juht­reaks

Juhtelemendi leidmine. Juhtelement asub juhtrea ja juhtveeru ristumiskohal.

Uue tabeli väärtuste arvutamine ehk uue lubatava lahendi leidmine toimub simpleksteisendustega, mille aluseks on Gauss- Jordani elimineerimisvõte. Selleks:

• kõik juhtrea elemendid jagatakse juhtelemendiga, mille tulemusena uues tabelis juhtelement saab väärtuseks +1 ;
  
• ülejäänud ridadele liidetakse teisendatava rea juhtveerus asuva kordaja vastandarvuga korrutatud juhtrida.
  

Uues simplekstabelis varem valitud juhtveeru kõik elemendid peale juhtelemendi (see on +1) muutuvad nullideks ning see veerg on muutunud ühikveeruks ehk vastav tundmatu baasitundmatuks.
Lahendid:

Need tundmatud, mille veerud ei ole ühikveerud, on baasivälised ehk vabad tundmatud ja nad võrduvad nullidega, baasitundmatute väärtused asuvad vabaliikmete veerus (vastava tundmatuga tähistatud reas).
üks optimaalne lahend - kõik sihifunktsiooni reas olevad tundmatute kordajad on mittenegatiivsed ning nende nullilised väärtused kuuluvad ühikveerule

puudub optimaalne lahend - valitud juhtveerus pole ühtegi positiivset nullist erinevat elementi, sellisel juhul on sihifunktsiooni väärtus tõkestamata

rohkem kui üks optimaalne lahend – optimaalses simplekstabelis sihifunktsiooni reas esineb kasvõi üksainus nullilise väärtusega element baasivälistele tundmatutele vastavates veergudes

TRANSPORDIÜLESANDED

Probleemi püstitus.

Olgu tegemist kauba vedamisega hankijatelt (ladudest/tehastest) tarbijatele (kauplustele, vahendajatele jne.). Tarbijate arv n ja hankijate arv m, kusjuures hankijatel on kauba varud vastavalt: ühikut ehk koguses ai (). Kaubaga varustatakse n tarbijat , kusjuures tarbijate vajadused on vastavalt ühikut ehk bj (). Veokulud i-ndalt hankijalt j-ndale tarbijale vedamisel kaubaühiku kohta moodustavad cij. Tuleb leida sellised veetavad kaubakogused xij mis toimetatakse i-ndalt hankijalt j-ndale tar­bijale nii, et transpordikulud kujuneksid vähimateks.

Probleemi matemaatiline mudel vastab tingimustele:

1) iga hankija juures olev kaubakogus tuleb välja vedada

2) iga tarbija vajadus tuleb rahuldada ( vedusid tuleb teostada vastavalt nõudlusele, s.t. vastavalt tellimustele)

3) veetavad kaubakogused ei saa olla negatiivsed (tundmatute mittene­gatiivsuse nõue)

Transpordiülesande põhikuju detailsem esitus:

kitsendustel:

hankijate kogused:

tarbijate vajadused:

, , .

Transpordiülesannet nimetatakse kinniseks, kui kõigi hankijate kogused (e. ressursid kokku) ja tarbijate kogunõudmi­ne on tasakaalus.

Transpordiülesanne on lahtine , kui hankijate olemasolevad kaubakogused ja tarbijate koguvajadus ei ole tasakaalus (hankijate ressursid on suuremad kui koguvajadus ja vastupidi)

Transpordiülesande lahendusalgoritm on välja töötatud kinnise esitus­kuju jaoks. Seega enne transpordiülesande lahendamist tuleb kontrollida, kas ülesanne on lahtine või kinnine .

Lahtine trans­pordiülesanne tuleb teisendada kinniseks:

• Kui , siis tuuakse sisse fiktiivne tarbija
  

Veokulude suurused kauba vedamiseks igalt hankijalt fiktiivsele (olematule) tarbijale võib võtta nullideks, sest sisuliselt vedu ei toimu ja seetõttu ka kulutusi ei tehta.

• Kui , siis tuuakse sisse fiktiivne hankija
  

Formaalselt on see kaubakogus, mille võrra tarbijate vajadused ületavad hankijate võimalusi. Seega on see kaubakogus, mis jääb tarbijatel saamata ja järelikult tuleb hankida ülesande-väliselt. Vastavad veokulud võib võtta võrdseks kas nulliga või suvalise arvuga.

• Varude puudujäägi () korral võib esitada näiteks järgmised nõuded:
  

kõigil tarbijatel jääks saamata võrdselt kaupa;

kõigil tarbijatel jääks saamata nende vajadusega võrdeline kogus kaupa;

vähendada kõige väiksema/suurema vajadusega tarbija nõudmist;

vähendada ühe või teise konkreetse tarbija või tarbijate grupi nõudmist

• Varude ülejäägi () korral võib esitada järgmised nõuded:
  

a) kõigil hankijatel jääks üle võrdne kogus kaupa;

kõigil hankijatel jääks üle nende varudega võrdeline kogus kaupa;

kaup jätta alles sellele hankijale, kelle pakkumine on kõige väiksem/suurem;

kaup jätta alles sellele hankijale, kelle turvameetmed on kõige paremad;

kaup jätta alles sellele hankijale, kelle hoiutingimused on kõige paremad;

Transporditabeli üldkuju on järgmine:

b1

b2

...

bn

a1

c11

c12

...

c1n

a2

c21

c22

...

c2n

...

...

...

...

...

am

cm1

cm2

...

cmn

Hankijad – a

Tarbijad - b

Lubatav lahend - transpordiülesande lahend, mis rahul­dab hankijate ja tarbijate vajadustega esitatud tingi­musi.

Optimaalne veoplaan - lubatava lahendi väärtused, mis kindlustavad sihifunktsioonile ( summaarsed veokulud) vähima väär­tuse.

Baasitabel- transporditabel, milles on välja toodud baas.

Baasiruudud - ruutu (m  hankijate arv, n  tarbijate arv). Kui baasiruudud ühendada horisontaalsete ja vertikaalsete lõigukestega, siis ei teki kinniseid kontuure ega tsükleid.

Baasitundmatud - baasiruutudele vastavaid tundmatud

Vabad tundmatud - üle­jäänud tundmatud

Lahenduskäik:

Majandusprobleemi formuleerimine transpordiülesandena.

Transpordiülesande kinnisuse kontroll. Vajadusel lahtise ülesande teisendamine kinniseks.

Lubatava baasitabeli ja sellele vastava lubatava lahendi leidmine.

Lubatava baasitabeli ja sellele vastava lahendi optimaalsuse kontroll.

Lahendi optimeerimine ehk uue ja parema lubatava baasitabeli leidmine.

Stabiilsuse analüüs

Transpordiülesandel on alati lahend leitav, kusjuures lahendamise käigus sihifunktsiooni väärtus järjest kahaneb ning baasitundmatute (nullist erinevate väär¬tustega tundmatute) arv lahendis ei ole suurem kui m + n – 1.

Lahendsmidr võimalused:

• Loodenurga reegel - saadud lubatav lahend erineb optimaalsest tava­liselt üsna palju, sest ei ole arvestatud veokulude suurusega ja summaarsed veokulud on tavaliselt suuremad kui teiste meetodite abil leitud lubatavate veoplaanide korral.
  
• Vogeli meetod - vedu tuleb teostada marsruudil, mille korral hinnalt järgmine marsruut tooks kaasa kõige suurema kahju. Selle reegli rakendamiseks arvutatakse transpordiülesande veokulude tabelis iga rea ja veeru jaoks kõige ökonoomsemast viisist järgmisel viisil vedamisega kaasneva “kahju” suuruse. Selle “kahju” suuruse saame, vastava rea (või veeru) kõige väiksema veokulu (min cij lahutamisel temale selles reas (või veerus) suuruselt järgmisest veokulust. Kõigist sellisel viisil leitud “kahjudest” valitakse välja kõige suurem ning temale vastavas reas (või veerus) kõige väiksema veokuluga ruutu teostatakse kaubakanne. Langeb välja kas rida või veerg (või mõlemad) olenevalt sellest, kas toimus tarbija vajaduste täielik rahuldamine või hankija ressursside täielik ammendumine . Kui langeb välja rida, s.t. hankija ressursid on ammendatud , tuleb arvutada uued “kahjud” kõigis olemasolevates veergudes ja uuesti saadud “ kahjude ” hulgast valida suurim jne. “Kahjude” arvutamise juures fiktiivset tarbijat või hankijat ei arvestata. Mitme suurima “kahju” esinemisel valitakse neist üks suvaliselt.
  
• Vähima elemendi reegel - arvestatakse veokulude suurusega. Kauba vedu on otstarbekas teostada marsruudil, kus veokulud on vähimad, kusjuures fiktiivne tarbija või hankija tuleb arvesse viimases järjekorras.
  

Optimaalsuse kontroll:

Transporditabel on optimaalne siis, kui baasi­ruutudes olevate veokulude teisendamisel nullideks kõik ülejäänud veokulud teisenevad mittenegatiivseteks Trans­porditabeli veokuludele võib liita (või lahutada) ridade ja veergude kaupa potentsiaale nii, et lubatava lahendi elementidele vastavad veokulud muutuvad nullideks. Kui teisendatud veokulude seas on negatiivseid arve, siis saab leida uue, parema lahendi. Kui aga teisendatud veokulude hulgas pole negatiivseid, siis on optimaalne lahend leitud.

Tähistame ridade potentsiaalid i ja veergude potent­siaalid j. Seejärel koostame võrrandisüsteemi potentsiaalide i ja j leidmiseks, lähtudes lubatava lahendi baasitundmatutele ( koormatud ruutudele) vastavatest veokuludest.

Leitud potentsiaalid lahutatakse transporditabelis kõigist veokuludest ja saadakse teisendatud veokulud cij’ : cij’ = cij - i - j

Lahendi optimeerimine:

Transpordiülesande lahendi parandamiseks tuleb teostada kaubaülekanne teisendatud veokuludega transporditabelis negatiivse veokuluga ruutu. Mitme negatiivse arvu esinemisel on otstarbekas eelistada väikseimat negatiivset arvu.

Moodustada ajutiselt laiendatud baasi (negatiivse veokulu ümbritseme ringikesega).

Moodustame laiendatud baasiruutudest kinnise ahela ehk tsükli, alustades ringikesega ümbritsetud negatiivse veokuluga ruudust ning liikudes vaheldumisi horisontaalselt ja vertikaalselt, muutes liikumissuunda vaid koormatud ruutudes. Ahelasse kuuluvate ruutude arv on alati paarisarv (minimaalselt kuulub ahelasse 4 ruutu ja maksimaalselt m + n – 1) .

Saadud kinnise murdjoone tippudele vastavatesse ruutudesse kirjutatakse mööda murdjoont liikudes kordamööda märgid “+” ja “”alustades ringikesega ümbritsetud negatiivse veo­kuluga ruudust, kuhu märgime “+”, naaberruutu “-“ jne.

Leiame ülekantava kaubakoguse, milleks on “” märgiga ruutudes asuva­test veokogustest vähim. Ülekantava kaubakoguse liidame “+”-märgiga tähistatud ruudus olevale kogusele ja lahutame “” märgiga tähistatud ruudus olevast kaubakogusest.

Leitud uues transporditabelis üks ruut (just see, mis on märgistatud “-“-märgiga ja kus oli vähim kaubakogus), langeb baasiruutude hulgast välja (kriipsutame ringikese läbi).

Alternatiivne lahend:

Alternatiivse lahendi olemasolust annab tunnistust transporditabelis sellise nullilise teisendatud veokulu olemasolu, mis ei kuulu lahendielemendile ehk nn. “vaba nulli” olemasolu.

Et seda leida moodustatakse ahel analoogiliselt lahendi parandamiseks moodustatava ahelaga, seega ahela moodustamist alustatakse koormamata ruudus olevast nullilisest veokulust ning selle alusel leitakse uus lahend.

Kõdunud lahend:

Kui lubatud lahendis on lahendielementide arv väiksem kui . Kõdunud lahend võib tekkida kahes erinevas olukorras:

• lubatava lahendi leidmisel;
  
• lahendi optimeerimisel.
  

NB! Et kontrollida lahendi optimaalsust ja/või lahendit parandada, peab lahendis lahendielemente (baasitundmatuid) aga olema täpselt m + n – 1.

Lubatava lahendi leidmise korral tekib kõdunud lahend siis, kui la­hendielemendi leidmisel üheaegselt saavad otsa hankija ressursid ning täielikult sai rahuldatud tarbija vajadus. Sellisel juhul võib kohe vastavasse ritta või veergu ühte vabasse ruutu lisada nullilise lahendielemendi, seejuures tuleb jälgida, et lahendielementidele vastavad ruudud ei moodustaks tsüklit. Kui peale nullilise lahendielemendi lisamist jätta alati vaatluse alt välja nii tühjaks saanud hankijale vastav rida kui täielikult rahuldatud tellimusega tarbijale vastav veerg, siis tsüklit ei teki. Teine võimalus on jätkata lubatava lahendi leidmist ning kui saadud lahendis on baasitundmatuid vähem kui , siis tabeli sellesse ritta või veergu, mis korraga tabelist eemaldati, lisada nulliline kaubakogus nii, et baasiruutudest (st koormatud ruutudest) ei moodustuks kinnist ahelat.

Lahendi optimeerimise käigus võib selguda, et ahela mitmes „-“ -märgiga tähistatud ruudus on üks ja seesama vähim ringipaigutatav (ära antav) kaubakogus ning ümberpaigutamise järel tuleb mõnesse koormatud ruutu kaubakogus 0.