Geriausios alternatyvos parinkimas. Vartiklis

Geriausios alternatyvos parinkimas
V. Gutenmakheris, Ž. Rabotas; Kvantas, 1999 m. lapkričio-gruodžio numeris

Aukštosiose mokyklose ir stojamuosiuose egzaminuose į universitetus studentams dažnai duodami uždaviniai, kuriuose reikia sudaryti lygtis. Studentui pirmiausia reikia pervesti uždavinio sąlygas į matematikos kalbą ir tada išspręsti gautas lygtis bei nelygybes. Uždavinyje aprašytoje situacijoje studentui reikia iš vienų skaitinių reikšmių gauti kitas skaitines reikšmes. Kaip pavyzdį, pateikiame pirmą ir paskutinį tipinių uždavinių aukštosios mokyklos uždavinyne sakinius:
Dvi mašininkės turi atspausdinti rankraštį... Kiek valandų prireiks kiekvienai mašininkei spausdinti rankraštį?
Motorlaivis išplaukia pasroviui iš upės prieplaukos... Kiek laiko reiks dviratininkui nuvažiuoti iš miesto iki turizmo centro?
Vario-cinko lydinys, kuriame buvo 5 kg cinko, sulydytas su 15 kg cinko.... kokia buvo pradinė lydinio masė?

Svarbu mokėti spręsti tokius uždavinius, kurie dažnai kyla pramonėje ir ekonomikoje, kai reikia paskaičiuoti ir sulyginti įvairius rodiklius, analizuoti įmonės veiklą ir pan. Tokios analizės padeda geriau suprasti esamą padėtį. Kitas natūralus žingsnis yra planuoti būsimą veiklą. O čia, aišku, yra galimos kelios alternatyvos, ir reikia pasirinkti geriausią iš jų.

Tokių uždavinių iškėlimas ir sprendimas yra matematinio programavimo dalis. Rusų matematikas L.V. Kantorovičius (1912-1986) buvo vienas pirmųjų, sprendęs tokio tipo praktinius uždavinius. 1939 m. jis išleido knygą „Gamybos planavimo ir organizavimo matematiniai metodai“. Jos pratarmėje rašoma:
„Yra du būdai, leidžiantys padidinti parduotuvės, fabriko ar visos pramonės šakos efektyvumą. Vienas jų – atnaujinti technologiją, t.y., mašinoms duoti naujas galimybes, modifikuoti technologinius procesus ar surasti naujas ir geresnes žaliavas. Kitas, vis dar per mažai panaudojamas būdas yra pagerinti gamybos proceso planavimą ir organizavimą. Užduočių paskirstymas gamyklos mašinoms, darbų paskirstymas tarp gamyklų ir įvairių medžiagų, pvz., kuro, paskirstymas patenka į šią kategoriją“.

Nuo knygos išleidimo praėjo daug metų, matematinis programavimas išsivystė į plačią matematikos šaką, kuri remiasi ekonominiais-matematiniais metodais ir plačiu kompiuterių panaudojimu.

Realiose planavimo ir valdymo situacijose vienu metu operuojama su labai dideliu kintamųjų kiekiu. Tačiau šiame straipsnelyje apsiribosime tik paprastais pavyzdžiais su mažu kintamųjų skaičiumi; tuos uždavinius galima išspręsti metodais, kurie žinomi netgi pirmus metus studijuojantiems algebrą, tokaiis, akip proporcijos, vieno tintamojo tiesinės funkcijos, nedidelio galimybių kiekio pilnas perrinkimas, sveikas protas.

Muilo miestelyje gyvena 100 gyventojų, o Rankšluosčio miestelyje – 50. pasirinkite vietą pirčiai prie miestelius jungiančio kelio taip, kad bendras visų 150 gyventojų vykimo į pirtį atstumas būtų mažiausias.

Suformuokime uždavinį matematikos kalba. Tegu atstumas tarp miestelių yra a km ir tegu pirtis būna x km atstumu nuo Muilo miestelio. Taigi 0 <= x <= a. Visi Muilo miestelio gyventojai vyks 100*x km iki pirties, o Rankšluosčio – 50*(a-x) km. Taigi bendras abiejų miestelių kelias iki pirties bus S=100*x+50*(a-x) km.

Mums reikia išspręsti uždavinį: rasti mažiausią S=50*x+50*a reikšmę esant sąlygai 0 <= x <= a, kur a yra nekintantis dydis.

Uždavinys labai lengvas. Tiesiog pastebėkime, kad S mažėja, kai x mažėja, tad galime paimti mažiausią įmanomą x reikšmę, t.y. x=0, kas reiškia, kad pirtis turi būti pastatyta Muilo miestelyje!

O dabar aptarkim rezultatą. Beveik visi, kurių klausėme, atsakė, kad pirtis turėtų būti pastatyta vietoje, esančioje dukart toliau nuo Rankšluosčio nei nuo Muilo. Atrodo, kad jie naudojo tokį fizikinį modelį: sūpuokles, su dviem žmonėm jų galuose, kurių vienas dukart sunkesnis.

Jei pirtis būtų pastatyta a/3 km atstumu nuo Muilo, jo gyventojai iki pirties vyktų tiek pat kilometrų kaip ir Rankšluosčio gyventojai, t.y. 100*a/3 = 50*2*a/3. Tai neabejotinai atrodo sąžiningiau, jei ieškotume “pusiausvyros taško”. Tačiau tada būtų sprendžiama visai kitas matematinis uždavinys: Kokia yra x, tokio, kad 0 <= x <= a reikšmė, kad dydis f=|100x-50(a-x)| būtų mažiausias?

Tampa aišku, kad išsireiškimas „geriausia alternatyva“ gali būti išaiškinama skirtingai. Kad jai priskirtume konkrečią prasmę, mes priskiriame tikslo funkciją. Mūsų uždavinyje tai buvo funkcija S=50*x+50*a, o kitame uždavinyje f=|100x-50(a-x)|. Reikšmės x, kuriai tikslo funkcija įgauna mažiausią reikšmę, suradimas duoda geriausią sprendinį.

Aišku, kad Rankšluosčio gyventojai gali nesutikti nė su vienu tų sprendinių ir tikėtina pateikti svarius argumentus. Pavyzdžiui, gali būti, kad Rankšluostyje yra daugiau pagyvenusių žmonių ir vaikų nei Muile, kad Rankšluostyje mažiau automobilių, kad Rankšluostyje geresnis vandens tiekikas ir t.t. Jei atsižvelgtumėm į visus šiuos argumentus, gautume kitą matematinį uždavinį arba, kitais žodžiai, kitą matematinį modelį.

Tikimės, kad mįslingas uždavinio su pirtimi pavyzdys nesuklaidins skaitytojų. Panašios problemos kyla rimtu atveju: parinkti vietą valgyklai didelėje gamykloje, turinčioje kelis cechus. Kaip geriausia suderinti tvarkaraštį darbininkų pietums?

Šiuo atveju tikslo funkcijos parinkimas yra aiškus (minimizuoti pietų trukmę). Tačiau optimalus planas priklauso ne tik nuo darbuotojų skirtinguose cechuose, bet ir gamybos proceso specifikos bei kitų veiksnių.

Smitas turi kuo galima greičiau atvykti į stotį. Jis gali iškviesti taksi, kuris atvyks po 24 min. ir jie važiuotų į stotį 30 km/val. greičiu; arba jis gali eiti pėsčiomis 6 km/val. greičiu. Kuris variantas geresnis, jei atstumas iki stotie yra a) 2 km; b) 3 km; c) 5 km?

Norint geriau palyginti pėsčiojo ir automobilio judėjimus, įtraukime trečiąjį asmenį, tarkim, Smito žmoną. Tarkim, kad Smitas išėjo į stotį, o tada žmona iškart pastebėjo, kad jis namuose paliko bilietą. Ji nedelsdama iškvietė taksi, sulaukė jo, ir nusivijo vyrą.

Paskaičiuokime laiką, reikalingą jį pavyti. Praėjus laikui t nuo išėjimo, Smitas bus 6t atstumu nuo namų. Jei t > 24 min. = 2/5 val., taksi važiuos 30*(t-2/5) km atstumą. Taksi pavys Smitą, kai 6t=0*(t-2/5), t.y., kai t=1/2 val. Jei ėjimas iki stoties trunka mažiau nei 1/2 val., žmona nepavys Smito. Per 1/2 val. Smitas nueina 3 km. Tad pasiekiame tokią išvadą: jei atstumas iki stoties mažesnis už 3 km (atvejis a), Smitui geriau eiti pėsčiomis, jei lygiai 3 km, nesvarbu, kurį variantą rinktis, o jei stotis toliau nei 3 km, geriau imti taksi. Taxi vs Foot

Spręsdami šį uždavinį aiškiai įvardijome kai kurias prielaidas: kad pėstysis ir taksi visąlaik juda tuo pačiu greičiu, taksi iškvietimas ir išvykimas įvyksta akimirksniu (realiame pasaulyje taip nėra) ir pan. Be to, mes tarėme, kad svarbiausias resursas Smitui buvo laikas. Tačiau atveju b) turime dvi vienodas laiko atžvilgiu alternatyvas. Renkantis tarp jų turime įtraukti kitą sąlygą: arba kelionės kainą (šiuo atveju Smitas rinktųsi ėjimą) arba patogumą (šiuo atveju galėtų važiuoti taksi).

Broliai Tomas ir Dikas nori aplankyti senelę, gyvenančią už 40 km. Jie turi vieną dviratį, ant kurio sudėjo savo daiktus. Tomas gali eiti 6 km/val. greičiu ir važiuoti dviračiu 20 km/val. greičiu. Dviratis gali būti paliktas be priežiūros kelyje. Koks greičiausias būdas abiem nukakti pas senelę?

Tarkime, kad abu broliai pas senelę atvyksta vienu metu, ir paskaičiuokime tam reikiamą laiką. Tada parodysime, kad kitu variantu kuris nors jų kelyje užtruks ilgiau.

Tarkime, kad Tomas važiuoja x km ir eina 40-x km, o Dikas atvirkščiai. Tada Tomas kelyje praleidžia x/20+(40-x)/6 val., o Dikas x/4 + (40-x)/30 val. Jei jie atvyksta vienu metu, šie dydžiai lygūs, t.y.
x/20+(40-x)/6 = x/4 + (40-x)/30

Iš čia randame, kad x=16 km, o kelyje abu užtrunka 4,8 val.
Šį sprendinį galima realizuoti taip: Tomas išvažiuoja dviračiu, nuvažiuoja 16 km, palieka dviratį ir senelę pasiekia pėsčiomis. Dikas išeina pėsčiomis, randa dviratį ir juo atvažiuoja pas senelę.

O dabar patikrinkime, kad negalima greičiau atvykti pas senelę. Jei Tomas nuvažiuos daugiau nei 16 km, Dikui reiks eiti ilgesnį kelią ir kelyje jis užtruks ilgiau. Jei Tomas važiuos mažiau, jam teks eiti ilgiau.

Šiame uždavinyje paprasčiausia praktinė prielaida davė optimalų sprendinį: broliai turi pas senelę atvykti vienu metu. Aišku, jei broliai stabtels pailsėti, tai tik pailgins jų kelią.

Šiame uždavinyje mes vėl turime kelis variantus, užtikrinančius minimalų kelionės laiką: broliai gali palikti dviratį po kelis kartus, svarbu, tik, kad Tomas pėsčiomis eitų 16 km, o Dikas – 24 km. Jie patys gali nuspręsti, kas jiems labiausiai priimtina.

Laboratorijoje turime tris lydinius. Pirmajame yra 40% vario ir 60% nikelio; antrajame 60% vario ir 40% kobalto, o trečiajame 60% kobalto ir 40% nikelio. Bandymams reikia 1 kg naujo lydinio, kuriame būtų 40 kobalto ir kiek įmanoma mažiau vario. Kaip tai pasiekti?

Sudarykime matematinį uždavinio modelį. Imkime x kg pirmo lydinio, y kg antro lydinio ir z kg trečio lydinio. Uždavinio sąlyga yra, kad x+y+z=1. Naujajame lydinyje bus 0.4*y+0.6*z kobalto, o taip pat 0.4*x+0.6*y vario.

Tad sukonstruotas toks matematinis uždavinio modelis: rasti neneigiamus skaičius x, y, z. Tenkinančius tokią lygčių sistemą:

x+y+z=1

0.4*y+0.6*z=0.4

Ir sieksime, kad m=0.4*x+0.6*y įgautų mažiausią reikšmę.

Joje x ir z išreikšime per y, ir pakeisime juos m lygtyje; tada ieškosime gautos funkcijos minimumo pagal y. Iš antros lygties gauname z = 2/3 – 2/3*y. Šią išraišką įstatę į pirmą lygtį gauname x = 1/3 – 1/3 * y. Tad m=2/15+7/15 * y.

Matome, kad kuo mažesnė y reikšmė, tuo mažesnė atitinkama m reikšmė. Minimali y reikšmė yra 0, o tada m=2/15, o x=1/3, z=2/3. Taigi turime imti 1/3 kg pirmojo lydinio ir 2/3 kg trečiojo lydinio. O antrojo lydinio visai nenaudojame.

Atkreipkite dėmesį, kad šiame uždavinyje vėl turime tiesinę funkciją m=2/15+7/15 * y, įgaunančią minimumą (šiuo atveju, kai y=0). Jei būtume išreiškę m per x ar z vietoje y, būtų sunkiau rasti intervalą, kuriame reiktų ieškoti minimumo. Kintamojo, kuris naudojamas tikslo funkcijoje, parinkimas yra labai svarbus.

Galėjome apsieiti ir be šių manipuliacijų, jei būtume pastebėję vieną aplinkybę. Tam, kad lydinys turėtų 40% kobalto ir kuo mažiau vario, jame turėjo būti kuo daugiau nikelio. Todėl antrąjį lydinį, kuris gali pasirodyti labiau priimtinas, nes jau turi 40% kobalto, geriau atmesti, nes jame išvis nėra nikelio (žr. lentelę). Tad mums reikia rinktis tik pirmą ir trečią lydinius. Jei imsime a kg pirmojo lyginio, tada turime imti (1-a) kg trečiojo lydinio. Naujajame lydinyje bus 0.6 * (1-a) kg kobalto. Tada pareikalaukime, kad 0.6 * (1-a)=0.4, o iš čia a=1/3, kas duoda ieškomą atsakymą.

Turime 100 dolerių eglutės papuošimams, kurie parduodami rinkiniais. Rinkinys iš 20 žaisliukų ikainuoja 4 dolerius, iš 35 – 6 dolerius, o iš 50 – 9 dolerius. Kokius rinkinius reikia nupirkti, kad turėtume daugiausia eglutės papuošimų?

Kiekvienas žaisliukas pirmame rinkinyje kainuoja 1/5 dolerio, antrame – 2/15 dolerio, o trečiame 9/50 dolerio. Išdėliokime šias kainas didėjimo tvarka: 2/15 < 9/50 < 1/5. Iš čia matome, kad pigiausi papuošimai yra antrame rinkinyje, o brangiausi – pirmame

Tad tam, kad nusipirktume kuo daugiau papuošimų už 100 dolerių, tikriausiai turime pirkti kuo daugiau pigiausių papuošimų. Taip mes galime nupirkti 16-a antrojo tipo rinkinių už 96 dolerius. Už likusius 4 dolerius mes galime dar nupirkti vieną pirmo tipo rinkinį – ir viso turėsime 16*35+20 = 580 papuošimų.

Tai atrodo esantis geriausias pasirinkimas. Kad tuo įsitikintumėm, patikrinkim kitą variantą. Jei nupirktumėm 15 antrojo tipo rinkinių, mums liktų 10 dolerių, kuriuos galėtume išleisti vienam 9 dolerius kainuojančiam trečiam rinkiniui arba dviem 4 dolerius kainuojantiems rinkiniams. Abiem atvejais bendras papuošalų kiekis būtų mažesnis už 580.

Taigi, geriausiu sprendiniu yra nupirkti 16-a antrojo tipo rinkinių ir 1-ą pirmo tipo rinkinį, įsigyjant 580 papuošalų. Šį sprendimą gavome paprasto samprotavimo dėka – kuo pigesnis papuošimas, tuo daugiau jų galima nusiprirkti.

Mūsų samprotavimas atrodo labai teisingu. Tačiau iš kur žinome, ar reikalai nepagerėtų, jei nusipirktume tik 14 pigiausių rinkinių? Taigi pateikiame griežtesnį sprendimą.

Tegu x yra I tipo rinkinių kiekis, y - antro tipo, o z - trečio tipo. Turime rasti tokius neneigiamus x, y ir z skaičius, kad 4x+6y+9z<=100 ir kiekis S=20x+35y+50z būtų pats didžiausias.

Iš 4x+6y+9z = 2/15*S + 4/7*x + 3/7*z >= 2/15*S
randame, kad 2/15*S <= 100
iš ko seka, kad S <= 583 1/3

Kadangi S yra sveikas skaičius, kuris dalus iš 5, gauname, kad S <= 580.
Kai x=1, y=16, z=0, uždavinio sąlygos patenkintos ir S=580.

Šis uždavinys priklauso sveikųjų skaičių programavimui, kuris yra sudėtingiausia matematinio programavimo dalis.

1. Trys parduotuvės darbuotojai, Džiordžas, Jokūbas ir Leo, priskirti trim parduotuvės skyriams: elektronikos, fotografijos ir muzikos instrumentų. Vedėjas paprašė psichologo padėti juos paskirstyti geriausiu būdu. Psichologas ištyrė darbuotojų žinias ir polinkius kiekvienai sričiai ir rezultatus įvertino taškais, parodytais lentelėje.

	Elektronika	Fotografija	Muzika
Džiordžas	5
Jokūbas	6	7	3
Leo	8	11	2

Kaip turėtų vedėjas paskirstyti darbuotojus, kad būtų pasiektas bendras didžiausias taškų kiekis?

2. Į keptuvę telpa du avienos kepsniai. Kiekvieną jų šoną galima apkepti per 10 min. Koks greičiausias būdas iškepti 3 kepsnius?

3. Taškai A ir B randasi toje pačioje tiesės pusėje. Kur tiesėje turi būti ilgio A atkarpa MK, kad AMKB būtų trumpiausio ilgio?

4. Trys broliai nusipirko dviratį. Jiems reikia jį parvaryti į namus, esančius už 30 km nuo parduotuvės. Kiekvienas brolių eina 4 km/val. greičiu ir važiuoja dviračiu 20 km/val. greičiu. Per kokį trumpiausią laiką jie gali pasiekti namus (dviratis gali būti paliktas be priežiūros kelyje)?

5. Nilas gali suvalgyti pyragaitį per 10 min., indelį uogienės per 8 min. ir išgerti pieno pakelį per 4 min. Karlsonas via tai gali padaryti dukart greičiau. Per kokį trumpiausią laiką jie gali sudoroti pusryčius iš pyragaičio, uogienės indelio ir pieno?

6. Į kiekvieną iš 4 indų telpa po 1 l vandeniu atskiestos rūgšties. Juose rūgšties atitinkamai yra 10%, 30%, 60% ir 80%. Laboratorijos asistentas turi paruošti 50% stiprumo tirpalą. Koks didžiausią tokio stiprumo tirpalo kiekį galima gauti iš turimų tirpalų?

7. Reikia paruošti lydinį, kuriame būtų 40% alavo. Turimi trys lydiniai, kuriuose yra po 60%, 10% ir 40% alavo. Jų 1 kg kainos atitinkamai yra 4,30, 5.80 ir 5.50. Kokius lydinius ir kokiomis proporcijomis reikia naudoti naujo lydinio pagaminimui už mažiausią kainą?

8. Iš dviejų tipų statybinių elementų galima sukonstruoti tris gyvenamųjų blokų tipus. 12-os butų bloko pastatymui reikia 70 pirmo tipo elementų ir 100 antro tipo elementų; 16-os butų blokui reikia atitinkamai 110 ir 150 elementų, o 21-o buto blokui reikia atitinkamai 150 ir 200 elementų. Turima 900 pirmo tipo elementų ir Warehouse and Shops

1300 antro tipo element7. Kiek ir kokių blokų reikia iš jų pastatyti, kad gautume didžiausią butų kiekį?

9. Turime tris sandėlius ir tris parduotuves, kurias jungia žiedinis kelias ir atstumas tarp dviejų gretimų objektų yra 1 km. Piešinyje parodyta prekių kiekiai (tonomis) sandėliuose (su plius ženklu) ir jų poreikis parduotuvėse (su minuso ženklu). Reikia parengti efektyviausią planą prekių išvežiojimui į parduotuves – tokį, kad tonkilometrių suma būtų mažiausia.

	-300
+200		+50
+550		-100
	-400