| [Besøgende (112.0.*.*)]svar [Kinesisk ] | Tid :2022-06-24 |  Forgreningsafgrænsning er en klassisk metode til løsning af optimale løsninger til heltal lineær programmering.
Definition:
Korrekt søgning i systemet efter alle mulige løsningsrum for et begrænset optimeringsproblem, hvis mulige løsning er et begrænset tal, er, hvad forgrening og afgrænsning handler om. Det er almindeligt gentagne gange at opdele hele løsningsrummet i mindre og mindre delmængder, kaldet grene; Og sættet af løsninger inden for hver delmængde beregnes som et mål nedre grænse (for minimumsproblemet), som kaldes afgrænsning. Hvis målværdien for et kendt gennemførligt løsningssæt efter hver gren ikke når den aktuelle grænse, afrundes delmængden. På denne måde overvejes mange delmængder ikke, hvilket kaldes beskæring. Dette er ideen om forgreningsmetoden.
Baggrund:
Den forgreningsbundne metode kan bruges til at løse rene heltals- eller blandede heltalsprogrammeringsproblemer. Det blev foreslået i 1960'erne af blandt andre Land Doig og Dakin. Fleksibel og nem at løse med computere, denne metode er med succes blevet brugt til at løse produktionsplanproblemer, rejsende sælgerproblemer, fabriksplaceringsproblemer, rygsækproblemer og distributionsproblemer.
Ideer:
Der er et maksimeret heltalsprogrammeringsproblem A og dets tilsvarende lineære programmeringsproblem B. Ud fra løsningen af problem B, hvis dens optimale løsning ikke opfylder heltalsbetingelsen for A, skal den optimale objektive funktion af B være den øvre grænse for den optimale objektive funktion af A z *, betegnet z ̄; Den objektive funktionsværdi af enhver gennemførlig løsning på z ville være en nedre grænse z_ z. Forgreningsmetoden er metoden til at opdele det mulige felt B i underregioner. Gradvist falde z og øge z_. Endelig få z *. |
|
