Sveikaskaitis programavimas. Uždavinio formulavimas ir sprendimas

Dažnai optimizavimo uždaviniuose nežinomieji turi būti sveikieji skaičiai. Tai yra taikoma sprendžiant uždavinius, kur ieškomi dydžiai yra pavyzdžiui traktoriai, automobiliai, gyvuliai, staklės ir t. t.
Formuluojant tokius uždavinius būtina pridėti sveikųjų kintamųjų sąlygą. Pridėjus tokią sąlyga gausime sveikaskaičio programavimo uždavinį. Jis gali būti tiek tiesinis, tiek ir netiesinis. Apžvelgsime tiesinių uždavinių sprendinį.
Optimalus planas, surastas paprastu simplekso metodu paprastai nėra sveikaskaitis. Paprasčiausias būdas yra suapvalinti gautus rezultatus iki artimiausių sveikų skaičių. Tačiau toks suapvalinimas daugumoje atvejų duoda mums planą, toli gražų ne geriausią iš sveikaskaičių (t.y. ne optimaliausią). Kartais toks suapvalinimas duoda mums rezultatus netenkinančius sisteminius apribojimus. Taip dažnai atsitinka, kai nežinomųjų reikšmės išreiškiamos mažais skaičiais. Todėl sveikaskaičiams uždaviniams spręsti sukurti kitokie metodai.
Iš pradžių į sveikųjų skaičių sąlyga nekreipiama dėmesio. Optimalus sprendinys surandamas simplekso metodu. Jeigu surastas sprendinys nesveikaskaitis, sudaromas papildomas tiesinis apribojimas, kurį tenkina bet koks sveikaskaitis sprendinys, bet netenkina surastas nesveikaskaitis. Po šito apribojimo įvedimo į uždavinį, surastas sprendinys tampa nebegalimas, ir tęsiamas optimumo suradimas. Jei naujas optimalus sprendinys irgi bus nesveikaskaitis, vėl formuluojamas papildomas apribojimas, ir vėl surandamas optimumas ir t. t.
Geometriškai papildomam apribojimui atitinka hiperplokštuma, kuri atskiria nuo stačiakampio sprendinių kažkurią tai dalį kartu su gautąja nesveikaskaičia viršūne. Visi taškai su sveikaskaitėmis koordinatėmis lieka naujajame stačiakampyje, taigi po kelių veiksmų toks taškas atsiranda ant ribos ir optimalus sprendinys tampa sveikaskaitis.
z= p1x1+p2x2+…+pnxn (1)
išpildant apribojimus:
a11x1 + a12x2+...+ a1jxj+...+a1nxn  a1,
...............................................................
ai1x1 + ai2x2+.....+aijxj+...+ainxn  ai, (2)
...............................................................
am1x1 +am2x2+...+ amjxj+...+amnxn  am.
Kintamųjų neneigiamumo sąlyga gali būti ir nebūti, bet visi kintamieji turi būti išreikšti sveikais skaičiais.
Jei sistemoje (2) koeficientai aij ir ai yra trupmininiai racionalieji skaičiai, tai kiekvienoje nelygybėje subendravardiklinsim juos ir padauginsim nelygybe iš šito bendrojo vardiklio. Nuo šito nelygybės reikšmė nepasikeis, o visi koeficientai taps sveikais. Taigi galima laikyti visus koeficientus iš sistemos (2) sveikais skaičiais.
Darome su sistema (2) tolesnius veiksmus :
y1=a11(-x1)+a12(-x2)+…+a1j(-xj)+…+a1n(-xn)+a1  0,
…………………………………………………………
yi=ai1(-x1)+ai2(-x2)+…+aij(-xj)+…+ain(-xn)+ai  0, (3)
…………………………………………………………
ym=am1(-x1)+am2(-x2)+…+amj(-xj)+…+amn(-xn)+am  0.
Kadangi sistemoje (3)...

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!