Operatsioonianalüüs ja lineaarne planeerimine

Enamasti on näiteks koolimatemaatika ülesandel üksainus lahend. Vahel on lahendeid kaks (ruutvõrrandil näiteks); harva on ülesandel lahendeid rohkem. Mõnel ülesandel on aga palju erinevad lahendeid, mõnel koguni lõpmata palju erinevaid lahendeid.

Mida siis teha?.

Kõigi lahendite hulgas leidub tavaliselt üks või mitu sellist lahendit, mis mingit täiendavalt püstitatud lisatingimust (näiteks odavust) paremini rahuldab.

Sellist lahendit nimetatakse optimaalseks lahendiks.

Optimaalseid lahendeid otsitakse paljudes situatsioonides. Näiteks:

1. Kuidas korraldada tehases tootmist nii, et kasum oleks suurim?

Näiteks: ühtede ja samade algkomponentide baasil on keemiakombinaat võimeline tootma mitmeid erinevaid aineid. On teada algkomponentide hinnad ja erinevate lõpp-produktide hinnad. Kulutused tööjõule on samuti teada. Mida on kasulikum toota?

2. Kuidas peab juurdelõikaja märkima kangale lõiked, et jäägid oleksid vähimad?

3. Kuidas koostada nädala menüüd nii, et toit oleks tervislik ja odav?

4. Kuidas koostada koolis tunniplaani?

5. Kuidas katta mingi maakoht bussiliinidega?

6. Kuidas valida erinevate automarkide vahel ostjale kõige sobivamat?

7. Orienteeruja peab läbima metsas olevad kontrollpunktid, mille asukohad ja omavahelised kaugused on teada. Kontrollpunktide läbimise järjekord ei ole tähtis. Millise marsruudi peab valima orienteeruja, et läbitava trassi pikkus oleks minimaalne?

Kõik need on küsimused, kus tuleb valida paljude erinevate võimaluste hulgast optimaalne, s.o. kõige parem, kõige ökonoomsem lahend. Teadust, mis tegeleb optimaalsete lahendite otsimisega ja kasutab selleks matemaatilisi meetodeid nimetatakse operatsioonianalüüsiks.

Operatsioonianalüüs tekkis Teise maailmasõja päevil sõjalistel vajadustel. Pärast sõja lõppu hakati operatsioonianalüüsi meetodeid rakendama majanduses, transpordis, tootmise juhtimises, kaubanduses ja mitmel pool mujal.

Operatsioonianalüüsi abil töötatakse välja parimate lahenduste leidmise viisid, operatsioonianalüüs aitab otsustada.

Operatsioonianalüüsi alla kuulub ka matemaatiline planeerimine, mille üheks lihtsamaks osaks on lineaarne planeerimine.

Lineaarse planeerimise sissejuhatav näide

Väike tisleritöökoda “Aken ja Uks” toodab puidust aknaid ja uksi. Akna valmistamiseks kulub 4 m neljandilist höövelpuitu, 1,2 (m^2) klaasi ja 6 tundi tisleri tööaega. Ukse valmistamiseks kulub 20 m neljakandilist höövelpuitu ja 10 tundi tisleri tööaega. Töökojas on ühe kuu varu höövelpuitu - 1400 m ja ühe kuu varu klaasi - 90 (m^2). Selles kuus võib arvestada 900 tisleritöö tunniga. Peale töömeestele palga ja riigile maksude äramaksmist teenib töökoja omanik iga akna pealt 10 € kasumit, iga ukse pealt aga 30€ kasumit. Kui palju aknaid ja uksi tuleks valmistada, et töökoja omaniku kasum oleks maksimaalne?

Olgu toodetavate akende arv x ja ja uste arv y. Koondame ülesande andmed tabelisse.

({{Tooted, Valmistada (tk.), Höövelpuidu kulu(m), Klaasi kulu((m^2)), Tööaeg(h), Kasum (€)}, {Aken, x, 4, 1,2, 6, 10}, {Uks, y, 20, -, 10, 30}, {Varud,  , 1400, 90, 900,  }})

Tootmist piiravad varud. Esitame need kitsendused matemaatiliselt. Kui toota x akent ja y ust, siis kulub höövelpuitu 4 x + 20 y. See kulu ei saa olla suurem varudest, seega

4 x + 20 y ⩽ 1400.

Ka klaasi ei saa kulutada rohkem, kui seda on, seega

1.2 x ⩽ 90.

Toota ei saa rohkem, kui tislerid jõuavad antud aja piires tööd teha, seega

6 x + 10 y ⩽ 900.

Et need kitsendused kehtivad üheaegselt, siis võime vaadelda neid võrratuste süsteemina

Tootmisest saadakse tulu 10x + 30y €, mille tähistame c - ga :

c = 10 x + 30 y.

Nüüd oleme taandanud majandusliku planeerimisülesande matemaatiliseks. Sõnastame selle:

Leia lineaarvõrratuste süsteemi

kus x ⩾0 ja y ⩾ 0,lahendite hulgast selline,mis annab suurima väärtuse avaldisele 
c=10x+30y.

Kahe muutujaga lineaarvõrratus. Selle graafiline lahendamine

Seost ax + by + c ⩾ 0 (või ax + by + c ⩽ 0), milles a, b ja c on reaalarvud, nimetatakse kahe muutujaga lineaarvõrratuseks. Tema lahenditeks on muutujate x ja y väärtuste sellised paarid, mille korral võrratus kehtib. Võrratuse graafiliseks lahendamiseks selgitame kõigepealt, kuidas sellist võrratust geomeetriliselt ette kujutada. 
Vaatleme näiteks võrratust  2x + 3y - 6 ⩾ 0.

Sirge 2x + 3y - 6 = 0 jaotab tasandi kaheks pooltasandiks, kusjuures seda sirget nimetatakse pooltasandite rajasirgeks. Tekkinud pooltasandeid võib nimetada tinglikult „ülemiseks" ja „alumiseks" (või „parempoolseks" ja „vasakpoolseks").

Võtame mõlemal pooltasandil mõned punktid, näiteks nn. „ülemisel" pooltasandil punktid (0; 3), (2; 2), (4; 3) ja (3; 1); „alumisel" pooltasandil võtame punktid (0; 0), ( - 1; 2), (1; 1), (2; 0) ja (3; - 1).

Asendades nende punktide koordinaadid võrratusse 2x + 3y - 6 ⩾ 0, saame ülemise pooltasandi punktide korral tõese võrratuse, alumise pooltasandi punktide korral aga väära võrratuse.

Võrratuse ax + by + c ⩾ 0 (või ax + by + c ⩽ 0) lahenditeks on ühe pooltasandi punktide koordinaadid. Pooltasandi rajasirge ax + by + c = 0 kuulub ka võrratuse lahendite hulka. Võrratuse ax + by + c ⩾ 0 (või 
ax + by + c ⩽ 0) graafiliseks lahendamiseks joonestame sirge ax + by + c = 0, mis eraldab kahte pooltasandit. Lahendite pooltasandi leidmiseks valime ühel pooltasandil väljaspool rajasirget mingi punkti P ((Subscript[x, 0]); (Subscript[y, 0])) ja kontrollime, kas selle punkti koordinaadid rahuldavad võrratust.Kui jah, siis on lahendite pooltasandiks see pooltasand, millelt valisime punkti P. Kui ei, siis on lahendite pooltasandiks see pooltasand, millel punkt P ei asu. Sagedasti võetakse kontrollitavaks punktiks koordinaatide alguspunkt. Näiteks võrratusi x ⩾ 1  ja  
x - 2y + 2 ⩽ 0 kujutavad piirkonnad on esitatud järgmistel joonistel.

Kahe muutujaga võrratusesüsteemi graafiline lahendamine

Sissejuhatuses toodud tisleritöökoja näites saime kahe muutujaga võrratusesüsteemi. Kuidas selliseid võrratusesüsteeme lahendada?

Võrratusesüsteemi lahendiks on selliste arvude hulk, mis rahuldab samaaegselt süsteemi iga võrratust. Järelikult koosneb süsteemi lahendite hulk süsteemi kõikide võrratuste ühiste lahendite hulgast. Kui lahendame võrratusesüsteemi, peame leidma kõigi võrratuste lahendihulgad ja seejärel nende hulkade ühisosa.

Kahest võrratusest koosneva süsteemi lahendamisel võib esineda kokku 4 võimalust. Esitame need joonisel:

Piirkond, milles olevad punktid rahuldavad ühte võrratust kahest, on ühekordse viirutusega. Piirkond, milles olevad punktid ei ole kummagi võrratuse lahendid, on viirutamata. Piirkond, mille punktid on süsteemi lahendid, on viirutatud kahekordselt.

Kahest võrratusest koosneva süsteemi lahendihulgaks võib olla nurk, riba, pooltasand või tühi hulk. Viimasel juhul on võrratused vastuolulised. Kolmandal juhul on üks võrratus liigne.

Kui meil on rohkem võrratusi, siis leitakse süsteemi lahendeid samal viisil kui kahe võrratusega võrratusesüsteemi korral. Lahendihulga kuju võib olla aga keerulisem. Näiteks, kolmest lineaarvõrratusest koosneva süsteemi lahendihulk võib moodustada järgmisi kujundeid:

Edaspidi nimetame süsteemi lahendite hulga poolt moodustatud kujundit (nii lõplikku kui ka lõpmatut) lahendite piirkonnaks.

Vaatleme neid lahendite piirkondi. Võttes suvalisest piirkonnast kaks vabalt valitud punkti, saame need punktid ühendada sirglõiguga, mis tervikuna kuulub samasse piirkonda. Kõiki selliseid piirkondi nimetatakse kumerateks piirkondadeks.

Punktihulka nimetatakse kumeraks hulgaks, kui selle hulga iga kahte punkti saab ühendada sirglõiguga, mis tervenisti kuulub samasse hulka. Kumerad hulgad on näiteks ring, pooltasand, kolmnurk. Ruumilistest kehadest püramiid, kera, korrapärane prisma. Kumerad hulgad ei ole näiteks rõngas, tähtviisnurk, 180° suurema kesknurgaga sektor jmt. Saab näidata, et iga kahe tundmatuga lineaarvõrratusesüsteemi lahendihulk on kumer.

Graafilise lineaarplaneerimise näited

Näide 1. Väike tisleritöökoda “Aken ja Uks” toodab puidust aknaid ja uksi. Akna valmistamiseks kulub 4 m neljakandilist höövelpuitu, 1,2 (m^2) klaasi ja 6 tundi tisleri tööaega. Ukse valmistamiseks kulub 20 m neljakandilist höövelpuitu ja 10 tundi tisleri tööaega. Töökojas on ühe kuu varu höövelpuitu - 1400 m ja ühe kuu varu klaasi - 90 (m^2). Selles kuus võib arvestada 900 tisleritöö tunniga. Peale töömeestele palga ja riigile maksude äramaksmist teenib töökoja omanik iga akna pealt 10 € kasumit, iga ukse pealt aga 30 € kasumit. Kui palju aknaid ja uksi tuleks valmistada, et töökoja omaniku kasum oleks maksimaalne?

Olgu toodetavate akende arv x ja ja uste arv y. Koondasime ülesande andmed tabelisse:

({{Tooted, Valmistada (tk.), Höövelpuidu kulu(m), Klaasi kulu((m^2)), Tööaeg(h), Kasum (€)}, {Aken, x, 4, 1,2, 6, 10}, {Uks, y, 20, -, 10, 30}, {Varud,  , 1400, 90, 900,  }})

Leia lineaarvõrratuste süsteemi

kus x ⩾0 ja y ⩾ 0,lahendite hulgast selline,mis annab suurima väärtuse avaldisele 
c=10x+30y.

Näide 2. Väike keemiatehas „Smell” toodab kahte liiki värve: sisetöödeks (S) ja välistöödeks (V). Mõlemad värvid segatakse kokku kahest lähteainest A ja B. Ööpäevas võib tuua lattu 7 t komponenti A ja 8 t komponenti B. Sisetööde värv koosneb ühest osast A-st ja kahest osast B-st. Välistööde värv koosneb kahest osast A-st ja ühest osast B-st. Tonni sisetööde värvi müügi pealt saab tehas 2000$ kasumit. Tonn välistööde värvi annab 4000$ kasumit. On teada, et välistööde värvi ei osteta kunagi sisetööde värvist päevas üle 2 tonni rohkem. Kui palju tuleks toota sisetööde värvi ja kui palju välistööde värvi, et kogukasum oleks suurim?

Esitame osa ülesande tingimustest tabelina.

Kui sisetööde värvi toota x tonni päevas ja välistööde värvi y tonni päevas, siis peavad kehtima võrratused

Et välistööde värvi ei osteta kunagi päevas üle kahe tonni sisetööde värvist rohkem, siis kehtib ka võrratus

y - x ⩽ 2.

Toodang annab kasumit 2000 x + 4000 y $. Seega peame leidma lineaarvõrratuste süsteemi

kus x⩾0 ja y⩾0, lahendite hulgast sellise arvupaari, mille korral avaldisel c = 2000 x + 4000 y on maksimaalne väärtus.

Saab näidata, et kui lineaarplaneerimisülesande lahendihulk eksisteerib ja on otsitavas suunas tõkestatud (ei moodusta lõpmatusse ulatuvat piirkonda), siis on planeerimisülesanne lahenduv ja optimaalsete lahendite arvu kohta võib öelda järgmist :

a) kui sihifunktsiooniga määratud sirged ei ole paralleelsed piirkonna ühegi rajajoone lõiguga, siis on ainult üks optimaalne lahend;
  b) kui sihifunktsiooniga määratud sirged on paralleelsed piirkonna optimaalset tippu läbiva lõiguga, siis on lahendeid lõpmata palju ja lahenditeks sobivad kõik selle rajajoone lõigu punktid.

Keemiatehase näites on piirkonna üheks rajasirgeks x + 2 y = 7. See sirge on paralleelne sirgega y = -(1/2) x ja ühtlasi kõigi sihifunktsioonidega mis on kujul c = 2000 x + 4000 y.

Seega saab keemiatehas maksimaalse kasumi 14 000 $, kui toodetavad sisetööde ja välistööde värvi kogused x ja y on seotud võrdusega x + 2 y = 7 ja võrratusega 1⩽ x ⩽ 3. (Need kaks tingimust koos annavad meile lõigu BC punktid.)

Kuidas peaks toimima tehase direktor, kui tal on valida lõpmatu hulga optimaalsete variantide hulgast? Kas valima juhuslikult ühe punkti sellest lõigust? Ei, sugugi mitte. Kogenud tehasedirektor mõistab kohe, et see mudel, mille meie koostasime, ei ole küllalt põhjalik, sest see mudel arvestab ainult värvi müügist saadavat tulu.

Tootmises on aga palju muid piiravaid tingimusi : erinev tööviljakus erinevate toodete valmistamisel, kulutused töötasule, kuidas toota nii, et tooraine kulu oleks vähim jne.

Kui direktor seab eesmärgiks toota nii, et komponente A ja B jääks võimalikult palju järele, siis ta näeb, et kui toota 3 t sisetööde värvi ja 2 t välistööde värvi, siis kulutame me ära kogu lähtetooraine hulga :

Kui aga toota 1 t sisetööde värvi ja 3 t välistööde värvi, siis jääb 3 t lähteainet B üle :

Saab näidata, et sellise lahenduse korral (1 t sisetöödeks ja 3 t välistöödeks) on lähteainete ülejääk suurim. Seega — seni kuni turg ei ole „üle küllastatud” välistööde värvist ja nõudlus püsib, on kasulik toota 1 t sisetööde värvi ja 3 t välistööde värvi päevas.

Näide 3. Broileritibu vajab iga päev vähemalt 15 ühikut vitamiini B1 ja vähemalt 15 ühikut vitamiini B2. Ta saab neid segudest H ja K. Segu H 1 g sisaldab 1 ühiku B1, 5 ühikut B2 ja maksab 1 sent. Segu K 1 g sisaldab 5 ühikut B1, 1 ühiku B2 ja maksab 3 senti. Koostame päevase toiduratsiooni segudest H ja K nii, et broileri vitamiinivajadus oleks rahuldatud ja kulutused oleksid minimaalsed.

Tähistame otsitavad ainehulgad x ja y-ga (loomulik on, et x ⩾ 0 ja y ⩾ 0). Ülesande tingimused märgime tabelisse:

Vitamiinivajaduse rahuldamiseks peab kehtima võrratusesüsteem

Selleks, et kulud oleksid vähimad, leiame selle võrratusesüsteemi need lahendid, mille korral avaldise 
c = x + 3 y väärtus oleks vähim.

Näide 4. Tammesalu ja Viljaanni jahuveskid jahvatavad 250 ja 350 tonni jahu kuus. Neist veskitest veetakse jahu kolme leivatehasesse. Rukkivere tehas vajab 150 tonni, Ahjusaare tehas 240 tonni ja Leivamäe tehas 210 tonni jahu kuus. Kuidas korraldada jahu vedu veskitest nii, et kõik tehased saaksid oma koguse jahu kätte ja veokulud oleksid minimaalsed? Kaugused veskite ja tehaste vahel on järgnevas tabelis olevate arvude kordsed.

Veetagu Tammesalust Rukkiverre x tonni ja Ahjusaarde y tonni jahu.

Et Rukkivere vajab 150 t, siis Viljaannilt peab ta saama (150 - x) t jahu.

Et Ahjusaare vajab 240 tonni, siis Viljaannilt peab ta saama veel juurde (240 - y) tonni jahu.

Et Tammesalu suudab toota 250 tonni jahu kuus ja Rukkiverre ning Ahjusaarde kokku veetakse sellest x + y tonni, siis Tammesalust veetakse Leivamäele (250 - x - y) t jahu.

Ülejäänud 210 - (250 - x - y) = x + y - 40 tonni saab Leivamäe Viljaannilt.

Seega näeks vedude plaan välja nii:

Et leida vedude kogumaksumust, selleks tuleb korrutada selles tabelis olevad arvud eelmises tabelis olevate vastavate arvudega ja tulemused liita. Saame avaldise

c = 4x + 3y + 5(250 - x - y) + 5(150 - x) + 6(240 - y) + 4(x + y - 40) = - 2x - 4y + 3280.

Selle avaldise minimaalseid väärtusi otsime lahendite piirkonnast. Et veskist leivatehasesse veetava vilja kogus ei saa olla negatiivne, siis saame võrratused:

x ⩾ 0, y ⩾ 0, 250 - x - y ⩾ 0, 150 - x ⩾ 0, 240 - y ⩾ 0, x + y - 40 ⩾ 0.

Nende võrratuste poolt määratud tasandiosa ongi selle ülesande lahendihulgaks:

Arvutades avaldise - 2x - 4y + 3280 väärtuse selle piirkonna tippudes, saame 
c(0; 40) = 3120,   c(40; 0) = 3200,   c(0; 240) = 2320, 
c(150; 0) = 2980, c(150; 100) = 2580, c(10; 240) = 2300.

Saadud väärtustest on vähim 2300, see saadakse, kui x = 10 ja y = 240. 
Asendades x ja y väärtused viimasesse tabelisse, saame optimaalse vedude korralduse plaani: