Tiesinio diskrečiojo programavimo uždaviniai

Paskaitos, turėjusios vykti 2020-04-01 medžiaga.
Diskrečiojo programavimo esmė ir uždavinių klasifikavimas. Iki šiol daugiausia nagrinėjome tokias situacijas, kuriose planuojamų dydžių reikšmės galėjo būti ir sveikos, ir trupmeninės. Tačiau labai dažnai praktikoje tenka susidurti su objektais, kurių dydžiai gali būti matuojami tik sveikais skaičiais arba skaičiais iš tam tikros diskrečios (baigtinių ar suskaičiuojamų reikšmių) aibės. Pavyzdžiui, galima statyti tik baigtinį namų skaičių, maršruto linija gali kursuoti tik sveikas autobusų skaičius, iš detalių komplektuojant gaminį, komplektų skaičius taip pat turi būti tik sveikas skaičius.
Tiesinio programavimo uždavinys, kurio visi arba dalis nežinomųjų gali įgyti reikšmes tik iš baigtinės ar suskaičiuojamos reikšmių aibės, vadinamas tiesinio diskrečiojo programavimo uždaviniu. Jo atskiras ir dažniausia pasitaikantis atvejis yra tiesinio sveikaskaitinio programavimo uždavinys, kurio nežinomųjų reikšmės privalo būti sveiki skaičiai. Jei tik dalies nežinomųjų reikšmės turi būti sveiki skaičiai, uždavinį vadiname dalinai sveikaskaitiniu.
1. Transporto tipo uždaviniai. Šiuose uždaviniuose, kaip buvo parodyta ankstesnėse paskaitose, visada yra optimalių sveikaskaitinių planų, jei pradiniai duomenys – sveiki skaičiai. Taigi šiuos uždavinius galima spręsti įprastais metodais, specialiai nesirūpinant, kad gautas sprendinys būtų sveikaskaitinis. Paskyrimų uždavinys, kurį nagrinėsime toliau, yra tokio tipo uždavinio pavyzdys.
2. Nedalių objektų programavimo uždaviniai. Tai uždaviniai, kuriuose planuojami objektai, matuojami tik sveikais skaičiais (pavyzdžiui, namai, transporto priemonės, komplektai ir pan.). Optimalūs planai, surasti įprastais metodais, dažnai nėra išreiškiami sveikais skaičiais, todėl reikalinga taikyti specialius sprendimo metodus.
3. Kombinatoriniai uždaviniai. Šiuose uždaviniuose su kiekvienu tam tikros grupės objektų pertvarkiu siejama tam tikra nauda ar sąnaudos. Reikia rasti geriausią iš galimų pertvarkių (geriausią maršrutą per žinomus punktus, geriausią darbų atlikimo tvarką, geriausią įrengimų priskyrimo darbams būdą ir pan.).
4. Uždaviniai su neiškiliomis arba nesusijusiomis leistinų planų aibėmis ir uždaviniai su netolydžiomis tikslo funkcijomis. Šių uždavinių pradiniame formulavime sveikaskaitinių nežinomųjų gali ir nebūti, tačiau jie atsiranda kaip pagalbinė šios grupės uždavinių sprendimo priemonė.
Be abejo, gali būti ir uždavinių, turinčių iš karto kelių grupių bruožus. Paskyrimų uždavinys,...

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!