| [Apmeklētājs (112.0.*.*)]Atbildes [Ķīniešu ] | Laiks :2022-06-24 |  Sazarojuma norobežošana ir klasiska metode, kā atrisināt optimālus risinājumus veselu skaitļu lineārai programmēšanai.
Definīcija:
Pareizi meklējot sistēmā visas iespējamās risinājumu vietas ierobežotai optimizācijas problēmai, kuras iespējamais risinājums ir ierobežots skaitlis, ir tas, par ko ir sazarošana un norobežošana. Parasti ir atkārtoti sadalīt visu šķīduma telpu mazākās un mazākās apakškopās, ko sauc par zariem; Un risinājumu kopums katrā apakškopā tiek aprēķināts kā mērķa apakšējā robeža (minimālajai problēmai), ko sauc par norobežošanu. Pēc katra zara, ja zināma iespējamā risinājuma kopas mērķa vērtība nesasniedz pašreizējo robežu, apakškopa tiek noapaļota. Tādā veidā daudzas apakškopas netiek ņemtas vērā, ko sauc par atzarošanu. Tā ir sazarošanas metodes ideja.
Fons:
Sazarojuma saistīto metodi var izmantot, lai atrisinātu tīra vesela skaitļa vai jaukta veselu skaitļu programmēšanas problēmas. To 1960. gados cita starpā ierosināja Land Doig un Dakin. Elastīga un viegli atrisināma ar datoriem, šī metode ir veiksmīgi izmantota, lai atrisinātu ražošanas grafika problēmas, ceļojošo pārdevēju problēmas, rūpnīcas atrašanās vietas problēmas, mugursomas problēmas un izplatīšanas problēmas.
Idejas:
Pastāv maksimizēta vesela skaitļa programmēšanas problēma A un tai atbilstošā lineārā programmēšanas problēma B. Sākot ar problēmas B risinājumu, ja tā optimālais risinājums neatbilst A veselā skaitļa stāvoklim, tad optimālajai B objektīvajai funkcijai jābūt A z* optimālās objektīvās funkcijas augšējai robežai, kas apzīmēta ar z ̄; Jebkura iespējama risinājuma objektīvā funkcijas vērtība z būtu apakšējā robeža z_ z. Sazarošanas metode ir metode, kā sadalīt iespējamo B lauku apakšreģionos. Pakāpeniski samaziniet z un palieliniet z_. Beidzot dabūt z*. |
|
