Lineaarne planeerimisülesanne
Lineaarseks planeerimisülesandeks nimetatakse järgmist ülesannet:
leida tundmatutele sellised väärtused, mis
1° annavad etteantud lineaarsele funktsioonile - sihifunktsioonile, ekstreemumväärtuse (maksimumi või miinimumi)
2° rahuldavad kõiki etteantud lineaarseid võrrandeid ja võrratusi - kitsendusi.
Kitsendusi, mis määravad tundmatute mittenegatiivsuse või mittepositiivsuse, nimetatakse tundmatute lisatingimusteks.
Lineaarsed planeerimisülesanded jagunevad maksimumülesanneteks ja miinimumülesanneteks.
Näide lineaarsele maksimumülesandele vastava üldise matemaatilise mudeli kohta:
leida tundmatutele sellised väärtused, mis
1° annavad etteantud lineaarsele funktsioonile - sihifunktsioonile, ekstreemumväärtuse (maksimumi või miinimumi)
2° rahuldavad kõiki etteantud lineaarseid võrrandeid ja võrratusi - kitsendusi.
Kitsendusi, mis määravad tundmatute mittenegatiivsuse või mittepositiivsuse, nimetatakse tundmatute lisatingimusteks.
Lineaarsed planeerimisülesanded jagunevad maksimumülesanneteks ja miinimumülesanneteks.
Näide lineaarsele maksimumülesandele vastava üldise matemaatilise mudeli kohta:
Tundmatute väärtuste komplekti, mis rahuldab kõiki kitsendusi, nimetatakse planeerimisülesande lahendiks ehk plaaniks. Lahendit, mis annab sihifunktsioonile otsitava ekstreemumväärtuse, nimetatakse planeerimisülesande optimaalseks lahendiks ehk optimaalseks plaaniks.
Praktikas esineb sageli ülesandeid, kus osade tundmatute või kõikide tundmatute väärtused peavad olema täisarvud. Selliseid ülesandeid nimetatakse vastavalt osaliselt täisarvulisteks või täisarvulisteks planeerimisülesanneteks.
Planeerimisülesannete lahendamisega on seotud kaks probleemi:
1. Planeerimisülesande esitamine matemaatilises keeles, s.t. vastava matemaatilise mudeli koostamine;
2. Matemaatilise mudeliga esitatud ülesande lahendamine matemaatiliste meetoditega.
NÄITED
Praktikas esineb sageli ülesandeid, kus osade tundmatute või kõikide tundmatute väärtused peavad olema täisarvud. Selliseid ülesandeid nimetatakse vastavalt osaliselt täisarvulisteks või täisarvulisteks planeerimisülesanneteks.
Planeerimisülesannete lahendamisega on seotud kaks probleemi:
1. Planeerimisülesande esitamine matemaatilises keeles, s.t. vastava matemaatilise mudeli koostamine;
2. Matemaatilise mudeliga esitatud ülesande lahendamine matemaatiliste meetoditega.
NÄITED
Näide 1
Leida x1 ja x2 sellised väärtused, mis annavad sihifunktsioonile z = -x1 + 2x2 maksimaalse väärtuse ja mis rahuldavad järgmisi kitsendusi:
Leida x1 ja x2 sellised väärtused, mis annavad sihifunktsioonile z = -x1 + 2x2 maksimaalse väärtuse ja mis rahuldavad järgmisi kitsendusi:
Selline planeerimisülesanne esitatakse järgmisel kujul:
Näide 2
Kahte tüüpi toodete valmistamiseks on 80 kg toorainet ja 6 tundi aega. Esimest tüüpi toote valmistamisel on toorainekulu 2 kg ja ajakulu 0,1 tundi, teist tüüpi toote valmistamisel on toorainekulu 1 kg ja ajakulu 0,12 tundi. Leida tootmisplaan, mis võimaldab saada suurimat tulu, kui esimest toodet tuleb valmistada mitte rohkem kui 30 tk ja teist toodet mitte rohkem kui 40 tk ning esimest tüüpi toote müügist saadakse 50 € tulu ja teist tüüpi toote müügist saadakse 30 € tulu.
Tähistame:
x - esimest tüüpi toodete arv,
y - teist tüüpi toodete arv,
z - toodete müügist saadav kogutulu.
Ülesande tingimuste põhjal on toodete müügist saadav kogutulu z = 50x + 30y,
materjali kogukulu 2x + y
ja kogu tootmise ajakulu 0,1x + 0,12y.
Kasutades materjali- ja ajakulu ning toodete arvu kohta kehtestatud piiranguid, saame ülesande esitada järgmise matemaatilise mudeliga:
Kahte tüüpi toodete valmistamiseks on 80 kg toorainet ja 6 tundi aega. Esimest tüüpi toote valmistamisel on toorainekulu 2 kg ja ajakulu 0,1 tundi, teist tüüpi toote valmistamisel on toorainekulu 1 kg ja ajakulu 0,12 tundi. Leida tootmisplaan, mis võimaldab saada suurimat tulu, kui esimest toodet tuleb valmistada mitte rohkem kui 30 tk ja teist toodet mitte rohkem kui 40 tk ning esimest tüüpi toote müügist saadakse 50 € tulu ja teist tüüpi toote müügist saadakse 30 € tulu.
Tähistame:
x - esimest tüüpi toodete arv,
y - teist tüüpi toodete arv,
z - toodete müügist saadav kogutulu.
Ülesande tingimuste põhjal on toodete müügist saadav kogutulu z = 50x + 30y,
materjali kogukulu 2x + y
ja kogu tootmise ajakulu 0,1x + 0,12y.
Kasutades materjali- ja ajakulu ning toodete arvu kohta kehtestatud piiranguid, saame ülesande esitada järgmise matemaatilise mudeliga:
Näide 3
Varrastest, mille pikkus on 80 mm, tuleb valmistada 25 mm, 30 mm ja 35 mm pikkuseid polte mitte vähem kui vastavalt 100 tk,
150 tk ja 75 tk. Koostada varraste tükeldamise matemaatiline mudel, mille korral kuluks vardaid minimaalne arv.
Koostame võimalike tükelduste tabeli vaadeldes vaid neid tükeldusi, kus materjal maksimaalselt ära kasutatakse.
Varrastest, mille pikkus on 80 mm, tuleb valmistada 25 mm, 30 mm ja 35 mm pikkuseid polte mitte vähem kui vastavalt 100 tk,
150 tk ja 75 tk. Koostada varraste tükeldamise matemaatiline mudel, mille korral kuluks vardaid minimaalne arv.
Koostame võimalike tükelduste tabeli vaadeldes vaid neid tükeldusi, kus materjal maksimaalselt ära kasutatakse.
Tähistame:
xi - i-nda tükelduse kasutuste arv,
z - kasutatud varraste arv.
Kuna iga tükeldusega kaasneb ühe varda kasutamine, siis
z = x1 + x2 + x3 + x4 + x5 + x6
Poltide arv vastavalt nende pikkustele on järgmine:
25 mm poltide arv avaldub seosega 3x1 + 2x2 + x3,
30 mm poltide arv avaldub seosega x2 + 2x4 + x5,
35 mm poltide arv avaldub seosega x3 + x5 + 2x6.
Kasutades poltide arvu kohta kehtestatud tingimusi, saame ülesande esitada järgmise matemaatilise mudeliga:
xi - i-nda tükelduse kasutuste arv,
z - kasutatud varraste arv.
Kuna iga tükeldusega kaasneb ühe varda kasutamine, siis
z = x1 + x2 + x3 + x4 + x5 + x6
Poltide arv vastavalt nende pikkustele on järgmine:
25 mm poltide arv avaldub seosega 3x1 + 2x2 + x3,
30 mm poltide arv avaldub seosega x2 + 2x4 + x5,
35 mm poltide arv avaldub seosega x3 + x5 + 2x6.
Kasutades poltide arvu kohta kehtestatud tingimusi, saame ülesande esitada järgmise matemaatilise mudeliga:
Näidete lahendamise kohta vt lehelt Lahendamine Solveriga.