Šakų ir rėžių metodas sveikaskaičiui programavimo uždaviniui spręsti

Kaip ir Gomori metodu, procesas pradedamas optimalaus plano suradimu simpleks – metodu, ar dirbtinės bazės metodu. Jei pasekoje gautas planas ne tenkina sveikaskaitiškumo sąlygos (***), tai tikslo funkcijos 0 = f (x0) reikšmė duoda ieškomam sprendiniui reikšmę (rėžį), t.y. z = 0.
Tegul kažkoks kintamasis plane ne gavo sveikaskaitės reikšmės. Sveikaskaičiame plane reikšmę reikia sumažinti, bent iki [] , arba padidinti, bent iki [] + 1.
Jei pakeitimo rėžiai iš anksto ne duoti, tai juos galima gauti išsprendus 2 pagalbinius tiesinio programavimo uždavinius. Šitie uždaviniai susideda iš minimizavimo arba maksimizavimo, su sąlygomis (*) ir (**).
Toliau sprendžiamas tiesinio programavimo uždavinys (***), su papildomis sąlygomis , arba , kur reiškia sveiką dalį . Surastas optimalus sprendinys vėl tikrinamas dėl sveikaskaitiškumo sąlygos (***).
Šitą sprendimo procesą galima galima pavaizduoti šakų pavidale, kuriame viršunė 0 atitinka planui , o kiekviena iš sujungtų su ja viršunių šakų atitinka optimaliam planui : optimizuoti z su sąlygomis (*), (**) ir papildomis sąlygomis, kad kintamąjam duota reikšmė , arba , kur - sveikas skaičius. Kiekvienai tokiai viršunei priskiriama reikšmė  = ( i0, k), kuri yra lygi min z su pateiktais apribojimais. Akivaizdu, 0 = ( i0, k), su visais k.
Jeigu gauti uždavinio optimalus planai tenkina sveikaskaitiškumo sąlygas, tai planas su minimalia reišme bus optimaliu uždavinio planu. Priešingu atveju reikia tęsti šakojimosi procesą. Be to,...

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!