Avkortet gren og bundet metodeforskjell. Matematisk modell av problemet

Gren og bundet metode er basert på ideen om sekvensiell partisjonering av et sett tillatte løsninger i undergrupper. Ved hvert trinn i metoden utføres en sjekk for partisjonselementene for å bestemme om det gitte delsettet inneholder den optimale løsningen eller ikke. For å gjøre dette, beregne den nedre grensen objektiv funksjon på dette undersettet.

Hvis det laveste anslaget ikke er mindre enn posten (den beste løsningen funnet), kan det hende at undergruppen ikke lenger vurderes. Det sjekkede delsettet kan også forkastes hvis den beste løsningen finnes i det. Hvis verdien av målfunksjonen på den funnet løsningen er mindre enn posten, endres posten. På slutten av algoritmen er posten resultatet av arbeidet. Hvis det er mulig å forkaste alle elementene i partisjonen, er posten den optimale løsningen på problemet. Ellers, fra de ikke-forkastede undersettene, velges den mest lovende (for eksempel med den laveste verdien lavere estimat), og er delt. Nye undersett kontrolleres på nytt osv. Den nedre grenseberegningen er det viktigste elementet av denne ordningen.

For hver spesifikk oppgave heltallsprogrammering(med andre ord, diskret optimalisering) branch and bound-metoden implementeres på sin egen måte. Det er mange modifikasjoner av denne metoden.

La oss vurdere implementeringen av filial- og bundet-metoden for reiseselgerproblemet og ryggsekkproblemet.

La oss vurdere Littles algoritme (ved branch and bound-metoden) for reiseselgerproblemet. Ideen kan formuleres som følger. I hver rad i avstandsmatrisen blir minimumselementet funnet og trukket fra alle elementene i den tilsvarende raden. Resultatet er en matrise redusert rad for rad. Matrisen vises på samme måte av kolonner. Resultatet er en matrise vist i rader og kolonner. Ved å summere de minimale elementene under reduksjon får vi reduksjonskonstanten, som vil være den nedre grensen for settet av alle tillatte Hamiltonske konturer. Deretter blir gradene av null for den gitte matrisen funnet (summen av minimumselementene i raden og kolonnen som tilsvarer denne nullen) og buen velges som graden av nullelementet når maksimal verdi. Settet med alle Hamiltonske konturer er delt inn i to delsett, hvorav den ene inneholder buen , den andre inneholder ikke denne buen. Etter dette blir de resulterende matrisene for Hamiltonske konturer gitt, og de nedre grensene til en delmengde av Hamiltonske konturer sammenlignes for å velge settet med den mindre nedre grensen for ytterligere partisjonering. Prosessen med å dele opp sett i undersett er ledsaget av konstruksjonen av et grentre. Ved å sammenligne lengden på den Hamiltonske konturen med de nedre grensene til dinglende grener, velges en delmengde med en nedre grense som er mindre enn den resulterende konturen for videre forgrening til en rute med korteste lengde eller det blir ikke klart at en slik rute ikke finnes.



Eksempel.

La reiseselgerproblemet gis følgende matrise over reisekostnader

Vi finner minimumselementet i hver rad i matrisen og trekker det fra alle elementene i den tilsvarende raden. Vi får en matrise, redusert rad for rad, med elementer

.

Hvis matrisen, gitt rad for rad, inneholder kolonner som ikke inneholder null, reduserer vi den med kolonne. For å gjøre dette, velg minimumselementet i hver kolonne i matrisen og trekk det fra alle elementene i den tilsvarende kolonnen. La oss få matrisen

,

hver rad og kolonne som inneholder minst én null. En slik matrise kalles redusert med rader og kolonner.

Ved å summere elementene og får vi reduksjonskonstanten:

.

Vi finner potensene av null for matrisen gitt i rader og kolonner. For å gjøre dette, erstatt mentalt nullene i matrisen med et tegn og finn summen av minimumselementene i raden og kolonnen som tilsvarer denne nullen. Vi skriver det til høyre øverste hjørne celler:

.

Vi velger buen som graden av nullelementet når maksimalverdien for

Vi deler settet med alle gyldige ruter i to delsett:

– et undersett som inneholder buen ;

– en delmengde som ikke inneholder en bue

For å beregne kostnadsestimatet for ruter som inkluderer buen, krysser vi ut raden og kolonnen i matrisen og erstatter det symmetriske elementet med tegnet. Vi presenterer den resulterende matrisen og beregner summen av reduksjonskonstantene.

Gren og bundet metode er en av de kombinatoriske metodene. I motsetning til Gomori-metoden, er den anvendelig for både fullstendig og delvis heltallsproblemer.

Dens essens ligger i et ryddig utvalg av alternativer og vurdering av bare de av dem som, i henhold til visse kriterier, viser seg å være nyttige for å finne den optimale løsningen.

Idé gren og bundet metode er som følger: la et svekket problem løses uten en heltallsbegrensning, og er en heltallsvariabel hvis verdi i den optimale planen er brøk. Så intervallet

inneholder ikke gjennomførbare løsninger med heltallskoordinater . Derfor er den gyldige heltallsverdien må tilfredsstille

eller
, eller

Innføringen av disse forholdene i problemet genererer to ikke-relaterte problemer med samme objektive funksjon, men ikke-overlappende områder med tillatte verdier av variablene. I dette tilfellet sies oppgaven å være fork.

Åpenbart er ett av følgende fire tilfeller mulig.

    Ett av problemene er uløselig, og det andre har en heltallsoptimal plan. Da gir denne planen og verdien av den objektive funksjonen på den løsningen originalt problem.

    Ett av problemene er uløselig, og det andre har en optimal plan, blant komponentene som er brøktall. Deretter vurderer vi det andre problemet, og i dens optimale plan velger vi en av komponentene, hvis verdi er lik et brøktall, og vi konstruerer to problemer på nye begrensninger for denne variabelen, oppnådd ved å dele dens heltallsverdier nærmest til løsningen.

    Begge problemene er løsbare. Ett av oppgavene har en optimal heltallsplan, og den andre oppgavens optimale plan har brøktall. Deretter beregner vi verdiene til målfunksjonen på disse planene og sammenligner dem med hverandre. For bestemthetens skyld antar vi her og nedenfor at problemet med maksimum av den objektive funksjonen blir løst. Hvis på en heltallsoptimal plan er verdien av målfunksjonen større enn eller lik dens verdi på en plan hvis komponenter inkluderer brøktall, så er denne heltallsplanen optimal for det opprinnelige problemet og, sammen med verdien av målfunksjonen på det, gir ønsket løsning.

Hvis verdien av målfunksjonen er større i planen, blant komponentene som det er brøktall av, bør du ta ett av disse tallene og, for problemet hvis plan vurderes, forgrene deg langs brøkvariabelen og konstruere to nye problemer.

    Begge problemene er løsbare, og de optimale planene for begge problemene inkluderer brøktall. Deretter beregner vi verdien av målfunksjonen på disse optimale planene og vurderer problemet som verdien av målfunksjonen er størst for. I den optimale planen for dette problemet velger vi en av komponentene, hvis verdi er et brøktall, og forgrener oss til to nye problemer, og deler endringsområdet for denne variabelen i to, begrenset av heltall til høyre og venstre , henholdsvis.

Dermed kan prosessen med å konstruere flere og flere nye oppgaver representeres i figuren i form av et forgrenet tre, med toppunktet betegnet "oppgave 1" og grener som strekker seg fra dette toppunktet. Denne sekvensen av handlinger når du finner optimal løsning Problemet med heltallsprogrammering gjenspeiles i navnet på denne metoden.

Det opprinnelige toppunktet tilsvarer den optimale planen til det opprinnelige problemet 1, og hvert toppunkt koblet til det med en gren tilsvarer de optimale planene for nye problemer konstruert for nye restriksjoner på en av variablene som har en verdi i form av en brøk nummer i den optimale planen for oppgave 1.

Hvert av toppunktene har sine egne grener, og ved hvert trinn velges det toppunktet som verdien av målfunksjonen er størst for.

Hvis det på et eller annet trinn oppnås en plan med heltallsverdier, og verdien av funksjonen på den viser seg å være større enn eller lik verdien av funksjonen ved andre toppunkter som er mulig for forgrening, så er denne planen den optimale planen for det opprinnelige heltallsprogrammeringsproblemet og verdien av objektivfunksjonen på det er maksimal.

Eksempel. Finn en gren-og-bundet løsning på et heltallsprogrammeringsproblem

Løsning. Finne den optimale planen for det formulerte problemet simpleks metode uten å ta hensyn til variablenes heltall, nemlig løser vi oppgave 1.

Optimal plan for oppgave 1 lineær programmering

på
.

For det opprinnelige problemet, tatt i betraktning variablenes heltallsnatur, er den resulterende løsningen ikke optimal.

For å finne en heltallsoptimal løsning deler vi variasjonsintervallet til variabelen x 1 i to områder, nemlig x 1  og x 1 = 10, og la oss dele det gitt oppgave for to nye oppgaver.

Bunnlinjen lineær funksjon har ikke endret seg: Z 0 = 0. Vi løser en av oppgavene, for eksempel oppgave 3, ved hjelp av simpleksmetoden. Vi finner at betingelsene for problemet er motstridende.

Vi løser oppgave 2 ved hjelp av simpleksmetoden. Vi får den optimale heltallsplanen for oppgave 2, som også er den optimale planen for oppgave 1:

på
.

Derfor, som et resultat av en forgrening av problemet, ble den optimale løsningen funnet.

Nedenfor er tilstanden til problemet og tekstdelen av løsningen. Hele løsningen er doc-format i arkivet kan du laste ned. Noen tegn vises kanskje ikke på siden, men word-dokument alt vises. Flere eksempler på arbeid med EMMM kan sees

FORMULERING AV PROBLEMET

Forlagsselskapet må fullføre skrivearbeid innen en uke (antall dager m = 5) ved hjelp av arbeidere i n kategorier (høy, gjennomsnittlig, under middels, lav). Det er nødvendig å bestemme det optimale antallet ansatte etter kategori, som sikrer fullføring av arbeidet med minimale utgifter til lønnsfondet under gitte begrensninger. De første dataene er vist i tabell 1 og 2.

Tabell 1

tabell 2

Problemet må løses ved hjelp av heltalls lineær programmeringsmetode i Mathcad 2000/2001.

BYGGE EN MATEMATISK MODELL
LØSNINGEROPPGAVER

For å beregne det optimale antallet ansatte, som sikrer en minimumsutgift til lønnsfondet, kompileres en matematisk modell av heltalls lineær programmering, siden antall ansatte ikke kan være en brøkverdi.

Å løse et heltallsprogrammeringsproblem utføres i to trinn.

På det første trinnet utføres et lineært programmeringsproblem uten å ta hensyn til heltall.

På andre trinn er det laget trinn for trinn prosess erstatte ikke-heltallsvariabler med nærmeste øvre eller nedre heltallsverdier.

Først løses problemet uten å ta hensyn til heltallsbetingelsen.

Objektfunksjonen bestemmes av formelen:

Hvor Q- generelt lønnsfond for å utføre arbeid;

x 1 , x 2 , …, x n- antall ansatte etter kategori;

n - antall kategorier av arbeidere;

c 1 , c 2 ,…, c n- dagslønnssats for en ansatt etter kategori;

m- antall arbeidsdager per uke, m = 5.

Objektfunksjonen kan skrives i vektorform:

Når du løser problemet, må følgende begrensninger oppfylles. Øvre grense

x ≤ d (1)

angir maksimalt antall ansatte etter kategori, der d er en vektor som bestemmer antall ansatte etter kategori.

I begrensning

det tas hensyn til at det totale antallet ansatte ikke skal overstige k maks.

I begrensningen nedenfra

R× x≥P(3)

det gjenspeiles at alle arbeidere sammen må fullføre en gitt mengde arbeid R.

Som den siste begrensningen skrives betingelsen om ikke-negativitet til vektoren av variabler

x≥0 (4)

Matematisk modell løse problemet uten å ta hensyn til heltallsbetingelsen inkluderer følgende uttrykk:

x ≤ d

R× x≥P,

x ≥ 0 .

En heltallsprogrammeringsmodell må inkludere uttrykk (5), samt ytterligere restriksjoner som ikke-heltallsvariabler X erstattes med heltallsverdier. Spesifikke modelluttrykk med heltallsvariabler diskuteres i neste underavsnitt.

LØSE OPTIMERINGSPROBLEMET IMATHCAD

Kildedataene for eksemplet er gitt i tabell. 1 og 2.

For å løse problemet, bruk Mathcad-pakken med Minimize-funksjonen. Denne funksjonen bestemmer problemløsningsvektoren:

X:= Minimer ( Q, x),

Hvor Q– uttrykk for den objektive funksjonen som bestemmer minstelønnsfondet, X- vektor av variabler.

Først løses problemet uten å ta hensyn til heltallsbetingelsen. Denne løsningen er gitt i vedlegg 1. Den første linjen inneholder null begynnelsesverdier av vektoren X og objektiv funksjon Q(x) . Etter ordet gitt og før minimer-funksjonen, er restriksjoner angitt. Som et resultat ble et ikke-heltall optimalt antall etter kategori oppnådd:

X =

med lønnsfond Q= 135 cu. e.

Fra denne avgjørelsen plassert heltallsløsning gren og bundet metode.

Først analyserer den resulterende løsningen brøkverdien x 4 =
= 1,143. Du kan sette to heltallsverdier for det: x 4 = 1 og x 4 = 2. Konstruksjonen av et beslutningstre begynner (vedlegg 2). Den innledende nullnoden settes til side på beslutningstreet. Den kobles så sammen med den første noden x4, og fra denne noden tegnes to grener tilsvarende begrensningene: x4 = 1 og x4 = 2.

For en gren med begrensningen x 4 = 1 løses det lineære programmeringsproblemet gitt i vedlegg 1, og tar denne begrensningen i betraktning.

Som et resultat ble en løsning på dette problemet oppnådd. Variabelen x 1 ble et heltall, men variabelen x 2 ble brøk x 2 = 0,9.

For å fortsette grenen opprettes en node x 3 og en gren x 3 = 1. Det lineære programmeringsproblemet utføres igjen med alle tre begrensningene: x 4 = 1, x 2 = 1, x 3 = 1. Med disse begrensningene, problemet har en løsning x T =
= (1,938 1 1 1).

For å fortsette grenen opprettes en node x 1 og en gren x 1 = 2. Det lineære programmeringsproblemet utføres igjen med alle tre begrensninger: x 4 = 1, x 2 = 1, x 3 = 1, x 1 = 2 Med disse begrensningene har problemet en løsning x T = = (2 1 1 1).

Prosessen med å konstruere et løsningstre og utføre et lineært programmeringsproblem gjentas til alle grener er konstruert.

Vedlegg 2 gir et komplett tre over mulige heltallsløsninger, hvorfra det følger at problemet har 4 effektive løsninger.

Den beste velges blant de effektive, og den aksepteres som den optimale heltallsløsningen for hele problemet med minimumsverdien Q(x) . I vårt tilfelle har vi to optimale heltallsløsninger

Q(X) = 140,

x T = (2 1 1 1),

x T = (1 1 2 2).

Derfor må en forlagsorganisasjon ansette to høykategoriarbeidere, en mellomkategoriarbeider, en lavere-middelkategoriarbeider og en lavkategoriarbeider for å skrive tekst. Et annet tilsvarende alternativ for å tiltrekke seg arbeidstakere er også mulig: en arbeidstaker i høy kategori, en arbeidstaker i middels kategori, to arbeidstakere i kategorien under gjennomsnittet og to arbeidere i lav kategori. I begge alternativene vil kostnadene være minimale og utgjøre 140 den. enheter

Last ned løsningen på problemet:


Filnavn: 2.rar
Filstørrelse: 24,99 Kb

Hvis filnedlastingen ikke starter etter 10 sekunder, klikk


Introduksjon

En stor klasse av anvendte optimaliseringsproblemer reduseres til heltallsprogrammeringsproblemer. For å løse disse problemene er kombinatoriske metoder basert på et ordnet søk etter de mest lovende alternativene mye brukt. Kombinatoriske løsningsmetoder kan deles inn i to grupper: metoder dynamisk programmering og gren- og bundede metoder.

Ved løsning av flerdimensjonale optimaliseringsproblemer foreslås felles anvendelse av gren- og bundne metoder og dynamisk programmering. På det første trinnet løses problemet ved å bruke den dynamiske programmeringsmetoden separat for hver av begrensningene. Sekvensene oppnådd som et resultat av å løse den dynamiske programmeringsfunksjonelle ligningen blir deretter brukt til å estimere den øvre (nedre) grensen til objektivfunksjonen. På det andre trinnet løses problemet ved hjelp av branch and bound-metoden. Når du bruker denne metoden, bestemmes en metode for å dele opp hele settet med gyldige alternativer i undersett, det vil si en metode for å konstruere et tre mulige alternativer, og en metode for å estimere den øvre grensen for den objektive funksjonen.

Den integrerte applikasjonen av dynamisk programmering og branch-and-bound-metoder gjør det mulig å øke effektiviteten ved å løse diskrete optimaliseringsproblemer. Når vi løser høydimensjonale problemer, for å redusere vilkårene for den optimale sekvensen, bruker vi tilleggsbetingelser klipping.

1. Historisk referanse

Gren og bundet metode ble først foreslått av Land og Doig i 1960 for å løse felles oppgave heltalls lineær programmering. Interessen for denne metoden, og faktisk dens "gjenfødelse", er assosiert med arbeidet til Little, Murthy, Sweeney og Carell med det reisende selgerproblemet. Fra dette øyeblikket dukket det opp stort antall arbeider viet branch and bound-metoden og dens ulike modifikasjoner. En slik stor suksess forklares med det faktum at forfatterne var de første som trakk oppmerksomheten til bredden av muligheter ved metoden, la merke til viktigheten av å bruke spesifikasjonene til problemet, og selv benyttet seg av detaljene ved det reisende selgerproblemet.

Denne metoden er den mest generelle blant alle diskrete programmeringsmetoder og har ingen grunnleggende restriksjoner på anvendelse. Gren-og-bundet algoritme er en effektiv prosedyre for å telle opp alle mulige heltallsløsninger.

Gren og bundet metode er en av de kombinatoriske metodene. Dens essens ligger i et ryddig utvalg av alternativer og vurdering av bare de av dem som viser seg å være lovende i henhold til visse kriterier, og forkaste lite lovende alternativer.

2. Beskrivelse av metoden

Forgrenings- og bundet-metoden er basert på ideen om å dele settet med gjennomførbare løsninger sekvensielt i delsett. Ved hvert trinn i metoden kontrolleres partisjonselementene for å bestemme om et gitt delsett inneholder den optimale løsningen eller ikke. Verifikasjon utføres ved å beregne et lavere estimat for målfunksjonen på en gitt delmengde. Hvis det lavere anslaget ikke er mindre enn ta opp- den beste løsningen funnet, så kan delsettet forkastes. Det sjekkede delsettet kan også forkastes hvis den beste løsningen finnes i det. Hvis verdien av målfunksjonen på den funnet løsningen er mindre enn posten, endres posten. På slutten av algoritmen er posten resultatet av arbeidet.

Hvis det er mulig å forkaste alle elementene i partisjonen, er posten den optimale løsningen på problemet. Ellers velges den mest lovende fra de ikke-forkastede undergruppene (for eksempel med den laveste nedre grenseverdien), og den deles. Nye undersett kontrolleres på nytt osv.

Når du bruker forgrening og bundet metode på hvert spesifikke problem, må først og fremst de to viktigste prosedyrene bestemmes: 1) forgrening av settet mulige løsninger; 2) beregning av nedre og øvre estimater av målfunksjonen.

2.1 Forgreningsregler

Avhengig av egenskapene til oppgaven, brukes vanligvis en av to metoder for å organisere forgrening:

1. forgrening av settet med gjennomførbare løsninger til det opprinnelige problemet D;

2. forgrening av settet D" oppnådd fra D ved å fjerne integeritetsbetingelsen på variablene.

Den første forgreningsmetoden brukes vanligvis for heltallsprogrammeringsproblemer og består i å identifisere underdomener av mulige løsninger ved å fikse verdier individuelle komponenter (fig. 1). I fig. 1-a gir en geometrisk tolkning av området med tillatte løsninger på heltallsprogrammeringsproblemet, bestemt av to lineære begrensninger og betingelser for ikke-negativiteten til variabler, og underregionene dannet ved forgrening, og i fig. Figur 1-b viser det tilsvarende forgreningsdiagrammet.

Den andre forgreningsmetoden er mer universell enn den første. For å utføre forgrening av noe område D i " på denne måten på D i " er det løst optimaliseringsproblem med målfunksjonen til det opprinnelige problemet og reelle variabler.

Forgrening utføres hvis i den optimale løsningen verdien av minst en heltallsvariabel i henhold til den opprinnelige formuleringen av problemet ikke er heltall. Blant disse variablene velges en, for eksempel j - i. La oss angi verdien i den funnet optimale løsningen x 0 [j]. De sier at forgrening utføres av variabelen x[j]. Regionen Di " er delt inn i to underregioner D i1 " og D i2 " som følger:

Hvor ] - hele delen verdier x 0 [j]

I fig. 2 gir konvensjonelt en geometrisk tolkning av slik forgrening.

Ris. 2. Geometrisk tolkning av forgrening

Det kan sees at i dette tilfellet fjernes delen mellom planene til de nylig introduserte restriksjonene fra regionen D i ". Siden variabelen x[j] i henhold til betingelsene i området for tillatte løsninger av det opprinnelige problemet er heltall, så fra underdomenet av tillatte løsninger av det opprinnelige problemet. D i (D i D i ") med et slikt unntak, er ingen avgjørelse utelukket.

2.2 Dannelse av nedre og øvre estimater av målfunksjonen

Før man starter en diskusjon av denne problemstillingen, må det sies at det er generelt akseptert å bruke branch and bound-metoden for et problem der optimaliseringsretningen reduseres til form av minimering. For å gjøre ytterligere notasjon og beregninger mer kompakte, vil vi skrive det diskrete programmeringsproblemet, som vi vil bruke gren og bundet metode for, i følgende generaliserte form:

hvor x er en vektor av optimaliseringsvariabler, hvorav noen er reelle og noen er heltall; f(x) - i det generelle tilfellet, en ikke-lineær objektiv funksjon; D er regionen med gjennomførbare løsninger på et generelt diskret programmeringsproblem.

Lavere estimater av måldiksjonen, avhengig av den valgte forgreningsmetoden, kan bestemmes enten for delområdene D i D eller for delområdene D i "D" (D i " og D" hentes fra de tilsvarende settene D i og D ved å fjerne integeritetsbetingelsene på diskrete variabler).
Det laveste estimatet av objektivfunksjonen f(x) på settet Di (eller D i ") vil være mengden:

Beregningen av nedre grenser i hvert enkelt tilfelle kan utføres under hensyntagen til egenskapene til problemet som skal løses. Samtidig, for at estimater mest effektivt skal oppfylle sin funksjon, må de være så store som mulig, dvs. være så nær som mulig de faktiske verdiene for min f(x). Dette er nødvendig, først og fremst, slik at de lavere estimatene reflekterer så nøyaktig som mulig den faktiske relasjonen min f(x) på delmengdene dannet under forgrening og lar oss mer nøyaktig bestemme retningen for videre søk etter den optimale løsningen til originalt problem.

I fig. Figur 3 viser et slikt ideelt tilfelle når de lavere estimatene (koblet med en stiplet stiplet linje) reflekterer relasjonene mellom de virkelige minimumsverdier f(x) (koblet sammen med en stiplet linje) for fire delsett av gjennomførbare løsninger D 1, D 2, D 3, D 4.

En av universelle metoderÅ beregne nedre grenser innebærer å løse følgende problem:

O i definert på denne måten er et lavere estimat av f(x) på Di (eller D i "), siden D i D i ".

Hvis det ved løsning av problem (4) blir fastslått at, så vil vi for generalitet anta det.

Det er nødvendig å merke seg en viktig egenskap ved lavere estimater, som er at verdiene deres for undergruppene som dannes under forgrening, ikke kan være mindre enn det lavere estimatet av den objektive funksjonen på settet som er utsatt for forgrening.

Sammen med den nedre grensen bruker gren- og bindingsmetoden øvre grense f(x). Som regel beregnes kun én verdi av den øvre grensen, som er definert som verdien av objektivfunksjonen for den best funnet gjennomførbare løsningen på det opprinnelige problemet. Dette øvre anslaget kalles noen ganger en rekord. Hvis det for problemet som skal løses er mulig å ganske enkelt og nøyaktig oppnå øvre grenser f(x) for individuelle sett dannet under forgrening, må de brukes i metoden for å redusere beregningskompleksiteten til løsningsprosessen. Når du bruker en enkelt øvre grense, antas dens startverdi vanligvis å være lik uendelig (), med mindre selvfølgelig, fra a priori betraktninger, ingen mulig løsning på det opprinnelige problemet er kjent. Når du finner den første gjennomførbare løsningen:

Deretter, når man bestemmer en bedre gjennomførbar løsning, justeres den øvre grensen:

Dermed kan verdien av det øvre estimatet bare reduseres i prosessen med å løse problemet.

2.3 Gren og bundet algoritme

De grunnleggende reglene for algoritmen kan formuleres som følger:

1. Først og fremst er delmengden med tallet som tilsvarer den laveste verdien av det nedre estimatet av målfunksjonen gjenstand for forgrening (I er settet med tall for alle delmengder, (eller) plassert i enden av grenene og hvis forgrening ennå ikke er stoppet). Hvis metoden ovenfor for forgreningssett implementeres, kan det oppstå tvetydighet angående valg av komponent som det neste forgreningstrinn må utføres langs. Dessverre er spørsmålet om den "beste" måten for et slikt valg fra et generelt synspunkt ennå ikke løst, og derfor brukes noen heuristiske regler i spesifikke problemer.

2. Hvis betingelsen er oppfylt for en i-te delmengde, må forgreningen stoppes, siden de potensielle mulighetene for å finne Bra valg i denne delmengden (karakteriserer dem) viser seg å være dårligere enn verdien av den objektive funksjonen for den virkelige funnet av akkurat nå tid, en tillatt løsning på det opprinnelige problemet (det karakteriserer).

3. Forgrening av delsettet stopper hvis den optimale løsningen funnet i oppgave (4) blir funnet. Dette begrunnes med at det derfor ikke er noen bedre gjennomførbar løsning enn i denne undergruppen. I dette tilfellet vurderes muligheten for justering.

4. Hvis, hvor, så er optimalitetsbetingelsene tilfredsstilt for den best mulige løsningen funnet i dette øyeblikk. Begrunnelsen er den samme som paragraf 2 i disse reglene.

5. Etter å ha funnet minst én gjennomførbar løsning på det opprinnelige problemet, kan muligheten for å stoppe algoritmen vurderes med en vurdering av nærheten til den beste av de resulterende gjennomførbare løsningene til den optimale (basert på verdien av objektivfunksjonen) ):

2.4 Løsning av problemet ved hjelp av branch and bound-metoden

Hel .

Til å begynne med finner vi å bruke simpleksmetoden eller metoden kunstig grunnlag optimal plan for problemet uten å ta hensyn til hele antallet variabler.

Hvis det ikke er noen brøktall blant komponentene i denne planen, er den ønskede løsningen på dette problemet funnet.

Hvis det er brøktall blant plankomponentene, er det nødvendig å flytte til nye planer til en løsning på problemet er funnet.

Gren-og-bundet-metoden er basert på antakelsen om at vår optimale ikke-heltallsdesign produserer en funksjonsverdi som er større enn noen påfølgende grendesign.

La variabelen i planen være et brøktall. Da, i den optimale planen, vil dens verdi være iht i det minste enten mindre enn eller lik nærmeste mindre heltall, eller større enn eller lik nærmeste større heltall.

Ved å bestemme disse tallene finner vi løsningen på to lineære programmeringsproblemer ved bruk av simpleksmetoden

- hel .

Hel .

Det er fire mulige tilfeller når du løser dette paret med problemer:

1. Ett av problemene er uløselig, og det andre har en heltallsoptimal plan. Da gir denne planen og verdien av målfunksjonen en løsning på det opprinnelige problemet.

2. Ett av problemene er uløselig, og det andre har en optimal plan uten heltall. Deretter vurderer vi det andre problemet, og i den optimale planen velger vi en av komponentene hvis verdi er lik et brøktall og konstruerer to problemer som ligner de foregående.

3. Begge problemene er løsbare. Ett av oppgavene har en optimal heltallsplan, og den andre oppgavens optimale plan har brøktall. Deretter beregner vi verdiene til målfunksjonen fra planene og sammenligner dem med hverandre. Hvis på en heltallsoptimalplan verdien av målfunksjonen er større enn eller lik dens verdi på en plan hvis komponenter inkluderer brøktall, så er denne heltallsplanen optimal for det opprinnelige problemet og gir den ønskede løsningen.

4. Begge oppgavene er løsbare, og de optimale planene for begge oppgavene inkluderer brøktall. Deretter tar vi for oss problemet der verdien av målfunksjonen er størst. Og vi konstruerer to oppgaver.

Når vi løser problemet, får vi derfor følgende diagram:

1. Finn en løsning på det lineære programmeringsproblemet uten å ta hensyn til integeritet.

2. Oppretter ytterligere begrensninger på brøkdelen av planen.

3. Finn en løsning på to problemer med begrensninger på komponenten.

4. Om nødvendig konstruerer vi ytterligere begrensninger, i henhold til de fire mulige tilfellene får vi en optimal heltallsplan eller fastslår problemets uløselighet.

Eksempel

La oss finne en løsning på problemet

Hel .

Løsning. Vi finner en løsning uten å ta hensyn til heltallsverdien til problemet ved hjelp av simpleksmetoden.

La oss vurdere neste par oppgaver:

Oppgave nr. 1

og oppgave nr. 2

Det første problemet har en optimal plan

den andre er uløselig.

Vi sjekker planen for den første oppgaven for integritet. Denne betingelsen er ikke oppfylt, så vi konstruerer følgende oppgaver:

Oppgave nr. 1.1

og oppgave nr. 1.2

Oppgave nr. 1.2 er uløselig, og problem nr. 1.1 har en optimal plan hvor verdien av objektivet fungerer.

Som et resultat fant vi ut at det opprinnelige heltallsprogrammeringsproblemet har en optimal plan og.

3. Løsning av reiseselgerproblemet ved hjelp av filial og bundet metode

La oss nå vurdere klassen av anvendte optimaliseringsproblemer. Gren og bundet metoden brukes i mange av dem. Det foreslås å vurdere et av de mest populære problemene - det reisende selgerproblemet. Her er ordlyden. Det er flere byer forbundet på en eller annen måte med veier av en viss lengde; det er påkrevd å fastslå om det er en sti langs hvilken man kan besøke hver by bare én gang og samtidig returnere til byen som stien startet fra («omreisende selgeromvei»), og, hvis en slik sti finnes, for å etablere den korteste av slike veier.

3.1 Problemstilling

La oss formalisere tilstanden i form av grafteori. Byer vil være toppunktene på grafen, og veiene mellom byer vil være de orienterte (rettede) kantene på grafen, på hver av disse en gitt vektfunksjon: Vekten av en kant er lengden på den tilsvarende veien. Banen som må finnes er en orientert spennende enkel syklus med minimumsvekt i digrafen (husk: en syklus kalles spenner hvis den går gjennom alle toppunktene i grafen; en syklus kalles enkel hvis den går gjennom hver av sine toppunkter bare én gang; en syklus kalles orientert hvis hvis begynnelsen av hver påfølgende kant faller sammen med slutten av den forrige; vekten av en syklus er summen av vektene av kantene; til slutt kalles en digraf komplett hvis den inneholder alle mulige kanter); slike sykluser kalles også Hamiltonian.

Åpenbart inneholder en komplett digraf sykluser av typen angitt ovenfor. Merk at det er nok å vurdere spørsmålet om tilstedeværelsen av en Hamilton-syklus i en digraf som spesielt tilfelle reisende selger problemer for komplette digrafer. Faktisk, hvis en gitt digraf ikke er fullstendig, kan den kompletteres til fullstendighet med de manglende kantene og en vekt Ґ kan tildeles hver av de ekstra kantene, med tanke på at Ґ er "datamaskinens uendelighet", dvs. det maksimale av alle mulige tall i betraktning. Hvis vi nå finner den letteste Hamiltonske syklusen i den nylig konstruerte komplette digrafen, så hvis den har kanter med vekt Ґ kan vi si at det ikke er noen "reisende selgersyklus" i denne originale grafen. Hvis den letteste Hamilton-syklusen i en fullstendig digraf viser seg å være endelig i vekt, vil det være den ønskede syklusen i den opprinnelige grafen.

Det følger av dette at det er tilstrekkelig å løse det reisende selgerproblemet for komplette digrafer med vektfunksjon. La oss nå formulere dette i sin endelige form:

la den være full rettet graf og - vektfunksjon; finne en enkel spennorientert syklus ("reisende selgersyklus") med minimumsvekt.

La den spesifikke sammensetningen av settet med toppunkter og være vektmatrisen til en gitt digraf, dvs. , og for hvem som helst.

Betraktning av filial og bundet metode for å løse problemet med reisende selger utføres mest hensiktsmessig mot bakgrunnen konkret eksempel. Ved å bruke notasjonen som er introdusert her, utfører vi denne beskrivelsen i neste forelesning.

La oss introdusere noen begreper. La det være en numerisk matrise. Å redusere en rad i denne matrisen betyr å velge minimumselementet i raden (det kalles reduksjonskonstanten) og trekke det fra alle elementene i denne raden. Åpenbart, som et resultat, på denne linjen vil minimumselementet være null, og alle andre elementer vil være ikke-negative. Ordene "gi en matrisekolonne" har en lignende betydning.

Ordene bringer matrise rad for rad betyr at alle rader i matrisen er gitt. Ordene "redusere en matrise med kolonner" har en lignende betydning.

Til slutt betyr ordene "reduser matrise" at matrisen først reduseres med rader og deretter reduseres med kolonner.

Vekten til et matriseelement er summen av matrisereduksjonskonstanter, som oppnås fra en gitt matrise ved å erstatte det aktuelle elementet med Ґ. Derfor betyr ordene tyngste null i matrisen at vekten av hver null i matrisen beregnes, og så er null med maksimal vekt fast.

La oss nå fortsette med å beskrive gren- og bundet-metoden for å løse problemet med reisende selger.

Første skritt. Vi fikser settet med alle traverseringer til den reisende selgeren (dvs. alle enkle orienterte spennsykluser). Siden grafen er komplett, er dette settet absolutt ikke tomt. La oss assosiere med det et tall som vil spille rollen som en verdi på dette settet av evalueringsfunksjonen: dette tallet er lik summen av reduksjonskonstantene til den gitte matrisen av vektene til grafkantene. Hvis settet med alle rundene til en reisende selger er merket med G, er summen av reduksjonskonstantene til vektmatrisen merket med j(G). Den gitte matrisen med vekter for denne grafen bør huskes; la oss betegne det med M 1; Dermed er resultatet av det første trinnet:

settet G av alle runder av den reisende selgeren er assosiert med tallet j(G) og matrisen M 1 .

Andre trinn. La oss velge den tyngste null i matrisen M 1; la ham stå i et bur; vi fikser en kant av grafen og deler settet G i to deler: en del som består av traverseringer som går gjennom kanten, og en del som består av traverseringer som ikke går gjennom kanten.

La oss assosiere følgende matrise M 1,1 med mengden: i matrisen M 1 erstatter vi tallet i cellen med Ґ. Så i den resulterende matrisen krysser vi ut radnummer i og kolonnenummer j, og beholder de resterende radene og kolonnene med sine opprinnelige tall. Til slutt, la oss redusere denne siste matrisen og huske summen av reduksjonskonstantene. Den resulterende reduserte matrisen vil være matrisen M 1,1; Vi legger summen av reduksjonskonstanter som nettopp er husket til j(G), og resultatet, ytterligere betegnet med j(), er sammenlignbart med mengden.

Nå knytter vi også en viss matrise M 1,2 til settet. For å gjøre dette, i matrisen M 1 erstatter vi tallet i cellen med Ґ og presenterer den resulterende matrisen. La oss huske summen av reduksjonskonstantene, og angi den resulterende matrisen med M 1,2. La oss legge til den huskede summen av reduksjonskonstanter til tallet j(G) og det resulterende tallet, ytterligere betegnet med j(), er sammenlignbart med mengden.

La oss nå velge mellom settene den der funksjonen j er minimal (dvs. settet som tilsvarer det minste av tallene j() og j()).

La oss nå merke seg at i resonnementet ovenfor ble bare ett faktisk objekt brukt som det første - den reduserte matrisen av vekter til en gitt digraf. Ved å bruke den ble en viss kant av grafen identifisert og nye matriser ble konstruert, som selvfølgelig det samme kan brukes på.

Med hver slik gjentatt applikasjon vil neste kant av grafen bli registrert. La oss bli enige om neste handling: før du sletter en rad og en kolonne i neste matrise, er det nødvendig å erstatte med Ґ tallene i alle de cellene som tilsvarer kanter som åpenbart ikke tilhører de Hamiltonske syklusene som går gjennom de tidligere valgte kantene.

Vi vil gjenta det samme for det valgte settet med matrisen og tallet j knyttet til det, og så videre, så lenge dette er mulig.

Det er bevist at resultatet er et sett som består av en enkelt runde av den reisende selgeren, hvis vekt er lik den neste verdien av funksjonen j; dermed er alle vilkårene som er diskutert ved beskrivelsen av gren- og bindingsmetoden oppfylt.

Etter dette forbedres posten til det endelige svaret er oppnådd.

3.2 Tilstanden til problemet

Student Ivanov fikk i oppgave å levere noen viktige dokumenter fra den 12. bygningen. Men heldigvis har han veldig lite tid til dette, og han må fortsatt tilbake. Vi må finne den korteste veien. Avstandene mellom objekter er gitt i tabellen

3.3 Matematisk modell av oppgaven

For å løse problemet tildeler vi hvert rutepunkt spesifikt nummer: 12. bygning - 1, Det hvite hus - 2, KRK "Premier" - 3, Administrasjon - 4. og 5. bygning - 5. Følgelig totalt antall poeng. Deretter introduserer vi alternative variabler som tar verdien 0 dersom overgangen fra i-te punkt til j-te ikke er inkludert i ruten og 1 ellers. Betingelsene for ankomst til hvert punkt og utgang fra hvert punkt uttrykkes kun én gang ved likheter (8) og (9).

For å sikre rutekontinuitet, tillegg n variabler og ytterligere restriksjoner (10).

Total rutelengde F, som må minimeres, skrives i følgende form:

I vårt tilfelle vil disse betingelsene bli skrevet i følgende form:

3.4 Løsning av problemet ved hjelp av branch and bound-metoden

oppgave omreisende selger grengrense

1) Analyse av sett D.

La oss finne et lavere anslag N. For å gjøre dette definerer vi en matrise med minimumsavstander for rad (1 hvor avstanden er minimal i en rad).

På samme måte definerer vi matrisen med minimumsavstander langs søylene.

La oss velge første plan: . Da er den øvre grensen:

Åpenbart, hvor betyr overgangen fra første punkt til j-te. La oss vurdere disse delmengdene i rekkefølge.

2) Analyse av delmengde D 12 .

3) Analyse av delmengde D 13 .

4) Analyse av delmengde D 14 .

5) Analyse av undergruppe D 15 .

6) Siling ut lite lovende undergrupper.

Delsett D 13 og D 15 er lite lovende. Fordi , men så vil vi videre vurdere delmengden D 14.

7) Analyse av undergruppe D 142 .

8) Analyse av undergruppe D 143 .

9) Analyse av delmengde D 145 .

10) Siling ut lite lovende undergrupper

Delsett D 143 er lite lovende. Fordi , men så vil vi videre vurdere delmengden D 145.

11) Analyse av undergruppe D 1452 .

12) Analyse av undergruppe D 1453 .

Optimal løsning: .

Dermed studentens rute: 12. bygning - Administrasjon - 5. bygning - Det hvite hus - KRK Premier - 12. bygning.

Bibliografi

1. Abramov L.A., Kapustin V.F. Matematisk programmering. - L.: Leningrad State University Publishing House, 1981. -328 s.

2. Alekseev O.G. Integrert bruk av diskrete optimaliseringsmetoder. - M.: Nauka, 1987. -294 s.

3. Korbut A.A., Finkelgein Yu.Yu. Diskret programmering. M.: Vitenskap. 1969. -240 s

4. Kuznetsov Yu.N. etc. Matematisk programmering: Opplæringen. - 2. utg., revidert og supplert. - M.: Høyere skole, 1980. -300 s.

5. Papadimitriou H., Steiglitz K. Kombinatorisk optimalisering. Algoritmer og kompleksitet. - M.: Mir, 1985. -213 s.

Lignende dokumenter

    Metoder for å løse problemer i høyere matematikk ved hjelp av grafteori, dens essens og prosedyre for oppløsning. Hovedideen med gren og bundet metode er praktisk bruk til oppgaven. Deling av et sett med ruter i delsett og dens grafiske representasjon.

    oppgave, lagt til 24.07.2009

    Essens og innhold, grunnleggende begreper og kriterier for grafteori. Konsept og generell idé om reisende selgerproblemet. Beskrivelse av gren og bundet metode, praktisk anvendelse. Eksempel på bruk denne metoden filialer for å løse problemet med reisende selger.

    test, lagt til 06.07.2011

    Metoder for å løse det reisende selgerproblemet. Matematisk modell av det reisende selgerproblemet. Littles algoritme for å finne minimumskonturen til Hamilton for en graf med n toppunkter. Løse problemet med reisende selger ved å bruke Kruskal-algoritmen og "tre"-algoritmen.

    kursarbeid, lagt til 30.04.2011

    Essensen av det reisende selgerproblemet, dets anvendelse. generelle egenskaper metoder for å løse det: uttømmende søkemetode, "grådige" metoder, genetiske algoritmer og deres generaliseringer. Funksjoner av grenen og bundet metode og bestemmelse av den mest optimale løsningen på problemet.

    kursarbeid, lagt til 18.06.2011

    Matematisk modell av problemet. Løsning transportproblem ved den potensielle metoden. Objektiv funksjonsverdi. Et system som består av 7 ligninger med 8 ukjente. Problemløsning grafisk metode. Velge halvplanet som tilsvarer ulikheten.

    test, lagt til 06/12/2011

    Dynamisk programmeringsteori. Konseptet med optimal underbygning. Et uavhengig og fullstendig avhengig sett med hjørner. Problemet med å finne det maksimale uavhengige settet i et tre. Bron-Kerbosch-algoritmen som en grenbundet metode for å finne klikker.

    sammendrag, lagt til 10.09.2012

    Løsning dobbelt problem ved å bruke det første grunnleggende teoremet til dualitetsteori, grafiske og simpleksmetoder. Matematisk modell av transportproblemet, utregning referanseplan transport ved hjelp av metodene til det nordvestlige hjørnet og minimumselementet.

    test, lagt til 27.11.2011

    Uttalelse av den reisende selgerproblemet og grunnleggende løsningsalgoritmer. Ruter og stier. Transportnettkonsepter. Konseptet med en økende bue, kjede, kutt. Floyd-Warshell-algoritme. Løsningen på problemet analytisk metode. Opprette en applikasjon for å løse et problem.

    kursarbeid, lagt til 10.08.2015

    Løsning av det første problemet, Poissons ligninger, Greens funksjon. Grenseverdiproblemer for Laplace-ligningen. Uttalelse av grenseverdiproblemer. Greens funksjoner for Dirichlet-problemet: tredimensjonale og todimensjonale tilfeller. Løsning av Neumann-problemet ved hjelp av Greens funksjon, implementering på en datamaskin.

    kursarbeid, lagt til 25.11.2011

    Sekvens for å løse et lineært grenseverdiproblem. Funksjoner av sveipemetoden. Algoritme for endelig forskjellsmetode: meshing inn gitt område, utskifting av differensialoperatøren. Løse SLAEer ved hjelp av Gauss-metoden, endelige forskjellsligninger.

Tenk på følgende heltalls lineære programmeringsproblem. Maksimer under begrensninger

I fig. 1 er rommet av mulige løsninger på det lineære heltallsprogrammeringsproblemet representert ved punkter. Det tilsvarende innledende lineære programmeringsproblemet (vi betegner det som LP0) oppnås ved å forkaste heltallsbetingelsen. Dens optimale løsning vil være =3,75, =1,25, z=23,75.

Figur 1.

Siden den optimale løsningen på LP0-problemet ikke tilfredsstiller heltallsbetingelsen, modifiserer branch and bound-metoden løsningsrommet til det lineære programmeringsproblemet slik at den optimale løsningen på det lineære heltallsprogrammeringsproblemet til slutt oppnås. For å gjøre dette, velg først en av heltallsvariablene, hvis verdi i den optimale løsningen av LP0-problemet ikke er heltall. For eksempel ved å velge (=3,75), legger vi merke til at området 3? ?4 av plassen med tillatte løsninger på LP0-problemet inneholder ikke heltallsverdier av variabelen og kan derfor utelukkes fra vurdering som lite lovende. Dette tilsvarer å erstatte det opprinnelige problemet LP0 med to nye lineære programmeringsproblemer LP1 og LP2, som er definert som følger:

Space of admissible solutions LP1 = space of admissible solutions LP0 + (), space of admissible solutions LP2 = space of admissible solutions LP0 + ().

Figur 2 viser plassene til tillatte løsninger på oppgavene LP1 OG LP2. Begge plassene inneholder alle mulige løsninger på det opprinnelige CLP-problemet. Dette betyr at problemer LP1 og LP2 "ikke vil miste" løsninger innledende oppgave LP0.

Fig.2.

Hvis vi fortsetter å intelligent ekskludere områder som ikke inneholder heltallsløsninger (som f.eks.) ved å innføre passende restriksjoner, vil vi til slutt oppnå et lineært programmeringsproblem hvis optimale løsning tilfredsstiller heltallskravene. Med andre ord vil vi løse CLP-problemet ved å løse en sekvens av kontinuerlige lineære programmeringsproblemer.

De nye restriksjonene utelukker hverandre, så problemene LP1 og LP2 må betraktes som uavhengige lineære programmeringsproblemer, som vist i fig. 3. Dikotomisering av LP-problemer er grunnlaget for forgreningsbegrepet i branch and bound-metoden. I dette tilfellet kalles det en grenvariabel.

Fig.3.

Den optimale løsningen på CLP-problemet ligger i rommet med gjennomførbare løsninger enten i LP1 eller i LP2. Derfor må begge delproblemene løses. Vi velger først problem LP1 (valget er vilkårlig), som har en ekstra begrensning?3.

Maksimer under begrensninger

Den optimale løsningen på problem LP1 er, og. Den optimale løsningen på oppgave LP1 tilfredsstiller kravet om at variablene og er heltall. I dette tilfellet sier de at oppgaven er undersøkt. Dette betyr at oppgave LP1 ikke lenger skal sonderes, siden den ikke kan inneholde beste løsningen TsLP oppgaver.

I denne situasjonen kan vi ikke evaluere kvaliteten på heltallsløsningen oppnådd ved å vurdere problem LP1, fordi løsning av problem LP2 kan føre til en bedre heltallsløsning (med stor beslutning i objektivfunksjonen z). Foreløpig kan vi bare si at verdien er den nedre grensen for den optimale (maksimum) verdien av objektivfunksjonen til det opprinnelige CLP-problemet. Dette betyr at ethvert uoverveid delproblem som ikke kan føre til en heltallsløsning med stor verdi av objektivfunksjonen, må utelukkes som lite lovende. Hvis et uoverveid delproblem kan føre til en bedre heltallsløsning, bør den nedre grensen justeres på riktig måte.

Ved verdien av den nedre grensen undersøker vi LP2. Siden i problemer LP0 optimal verdi objektivfunksjonen er lik 23,75 og vekten av koeffisientene er heltall, da er det umulig å få en heltallsløsning på LP2-problemet som vil være bedre enn den eksisterende. Som et resultat forkaster vi deloppgave LP2 og anser den som undersøkt.

Implementeringen av branch and bound-metoden er fullført, siden begge deloppgavene LP1 og LP2 er undersøkt. Derfor konkluderer vi med at den optimale løsningen på CLP-problemet er løsningen som tilsvarer den nedre grensen, nemlig og.

Hvis vi hadde valgt en variabel som forgreningsvariabel, ville forgreningen og hastigheten for å finne den optimale løsningen vært annerledes Fig. 4.

Fig.4. Bransjebeslutningstre