• hjem
  •  > 
  • Systemprogrammer
  •  > 
  • Løs ved hjelp av branch and bound-metoden. Generell plan for å løse problemet med reisende selger

Løs ved hjelp av branch and bound-metoden. Generell plan for å løse problemet med reisende selger

Følgende problem må løses:

maks 2x 1 + x 2

5x 1 + 2x 2 10

3x 1 + 8x 2 13

Først, la oss løse dette problemet grafisk uten heltallsbegrensninger. Løsningen kan finnes enten ved hjelp av simpleksmetoden eller grafisk. La oss finne det grafisk (Figur 4). Koordinatene til det optimale punktet kan bli funnet ved å løse ligningssystemet: 5x 1 + 2x 2 = 10 x 1 = 27/17

3x 1 + 8x 2 = 13 x 2 =35/34

X G = (27/17; 35/34), z G = 143/34

Figur 4 - Grafisk løsning på problemet uten integritetsbegrensninger

La oss begynne å bygge et tre, hvis første toppunkt vil tilsvare hele ODP for ikke-heltallsproblemet (G), og dets estimat vil være lik z G (fig. 5).

Figur 5 - Diagram over gren og bundet metode

Den resulterende planen er ikke heltall, så vi tar dens vilkårlige ikke-heltallskomponent, for eksempel den første (x 1 Z; [x 1 ] = 1) og deler ODP i to deler som følger:

G 1 = (XG: x 1 1)

G 2 =(XG: x 1 2)

Dette betyr at regionen G 1 vil inkludere alle punkter fra G hvis abscisse ikke er mer enn 1, og i G 2 - hvor den ikke er mindre enn 2. Punkter med brøk abscisseverdier fra 1 til 2 er ekskludert fra vurdering.

La oss skildre disse områdene på en graf (Figur 6).

Fra figur 6 er det klart at G 2 representerer ett punkt X G 2 = (2;0), derfor er det optimale for problemet 4 ( 2 = 4) på ​​dette settet.

Planen X G 2 er heltall, derfor kan en løsning på heltallsproblemet allerede ha blitt funnet. Imidlertid må vi fortsatt finne et estimat for settet G 1 |. Det kan være minst 4 (men definitivt ikke mer enn 143/34). Hvis dette er tilfelle, må du sjekke om løsningen på problemet på G 1 er et heltall. Hvis det er et heltall, så er det en løsning på problemet, og hvis ikke, må løsningsprosessen fortsettes, splitting G 1

Figur 6 - Deling av settet i deler

På G 1 kan man finne det optimale punktet ved å løse ligningssystemet:

x 1 = 1 x 1 = 1

3x 1 + 8x 2 = 13 x 2 =5/4

X G 1 = (1; 5/4), z G = 13/4

Poengsummen er mindre enn 4, derfor er løsningen på problemet X * =X G 2 =(2;0),z * =4.

3.4 Løse et heltalls lineært programmeringsproblem ved å bruke branch-and-bound-metoden ved å bruke "Business Problem System"-undersystemet

ZTsLP kan løses ved å bruke applikasjonspakken "Quantitative Systems for Business" ("Business Problem System") . Det tilsvarende programmet startes av filen intlprog.exe. Det løser både delvise og fullstendige heltallsproblemer lineær programmering med opptil 20 variabler og begrensninger ved bruk av branch and bound-metoden. Dette inkluderer å løse problemer med boolske variabler (dvs. med variabler som kan ha en av to verdier - 0 eller 1; som for eksempel i oppgaveoppgaven). Som standard er alle variabler ikke-negative. Programmet lar deg legge inn heltallsgrenser for variabler uten å inkludere dem i det totale antallet grenser. Som standard er den nedre grensen 0 og den øvre grensen er 32000. Hvis grenser for ikke-heltall må angis, legges de inn som normale grenser.

Hvis et problem har flere optimale planer, blir bare én av dem funnet. Informasjon om tilstedeværelsen av flere løsninger vises ikke.

Modus 2 (gå inn i en ny oppgave) inkluderer tre stadier. På det første trinnet legges informasjon om dimensjonen til problemet, retningen til ekstremisering og variabelnavn inn (som standard XI, X2,..., Xn).

Det andre trinnet er å bestemme om alle variabler er heltall, om alle variabler er boolske, og om grenser vil bli introdusert for variablene. Hvis du svarer «nei» på det første spørsmålet eller «ja» på det tredje, vises en tabell (Figur 7):

Angi grense og grenser for variabler

(Standardverdier for nedre grense 0 og øvre grense 32000)

AC-nr. Navnegrense (I/C) Nedre Gr. Øvre gr.

1 x 1 <0 > <0 >

2 X 2 <0 > <0 >

Figur 7 - Definisjon av grenser og grenser

Ved å sette I (heltall) i Limit-kolonnen, pålegges variabelen en heltallsbegrensning. Ellers kan (C, kontinuerlig) variabelen også ta ikke-heltallsverdier, dvs. er kontinuerlig.

Grenseverdier er avrundet til hele tall. Hvis den nedre er større enn den øvre, vises en feilmelding.

På tredje trinn introduseres koeffisienter for variabler og tegn i restriksjoner.

I løsningsmenyen er det et alternativ for å rette heltallsfeilen (som standard er den 0,001).

Å løse problemet ved hjelp av branch and bound-metoden er ikke ledsaget av en grafisk illustrasjon (et bilde av et tre) i programmet, men for å forklare algoritmen presenterer vi en slik illustrasjon i figur 8.

Algoritmen til gren- og bundet-metoden implementert i dette programmet er noe forskjellig fra den som er diskutert ovenfor i retningslinjene og er mindre effektiv i den forstand at den kan kreve mer iterasjoner. Det er imidlertid nyttig å gjennomgå det for å tydelig illustrere forskjellen i tilnærminger. I tillegg, i mange lærebøker, er anvendelsen av gren- og bundet-metoden diskutert spesifikt ved å bruke denne modifikasjonen som et eksempel.

Hovedforskjellen er at den mest "lovende" undergruppen ikke velges på hvert trinn. Etter at neste delmengde er delt i to deler, beregnes ikke poengsummen til begge deler umiddelbart, men i stedet blir hver gren av treet sekvensielt vurdert til slutten. Den opprinnelige ODP er delt inn i delsett i henhold til den første ikke-heltallsvariabelen i den optimale planen for ikke-heltallsproblemet. Deretter vurderer de toppunktet som tegnet tilsvarer, deler opp den tilsvarende delmengden på samme måte som den opprinnelige ODP, vurderer igjen toppunktet som tegnet tilsvarer osv. til en heltallsplan er oppnådd, eller problemet viser seg å være uløselig. Først etter dette går de tilbake til å vurdere toppunktene som tegnet tilsvarte.

Samtidig, ved hver iterasjon, vises informasjon om gjeldende heltallsgrenser (som definerer delmengden som vurderes), den optimale planen for ikke-heltallsproblemet, om det er heltall, verdien av objektivfunksjonen (IF) på det, og verdiene til ZL eller ZU. For en oppgave vises verdien av den nedre grensen ZL som maksimum, og verdien for den øvre grensen ZU vises som minimum. Inntil en heltallsløsning er funnet, er ZL = -1*10 20 og ZU = 1*10 20.

Etter å ha funnet en heltallsplan, er det umulig å umiddelbart bedømme om den er optimal, siden ikke de mest lovende hjørnene ble vurdert. Men vi kan trygt si at ønsket maksimum ikke er mindre (og minimum er ikke større) enn verdien av målfunksjonen i heltallsplanen. Derfor endres verdiene til grensene ZL og ZU (med mindre en heltallsplan med en ikke mindre (ikke mer) verdi av den objektive funksjonen tidligere ble funnet).

Grener med en poengsum mindre enn ZL eller større enn ZU vurderes ikke. Planen som tilsvarer grensen huskes. Når alle delmengder har blitt vurdert eller ekskludert fra vurdering, kan denne planen anses som optimal.

La oss forklare dette med et eksempel (fig. 8):

maks 3x 1 + 2x 2

7x 1 + 5x 2 35

9x 1 + 4x 2 36

Ved den første iterasjonen ble en ikke-heltallsløsning X = (2,353; 3,706) funnet. Hele ODP (sett G) er delt inn i to delsett - G 1 og G 2 som følger:

G 1 = (XG: x 1 3)

G 2 = (XG: x 1 2).

Ved den andre iterasjonen løses problemet på delmengden G 1 . Den resulterende løsningen er også ikke-heltall. Deretter, i stedet for å vurdere en delmengde av G 2, fortsetter vi å vurdere G 1. I den aktuelle planen velger du den første ikke-heltallskomponenten (dette er x 2) og deler G 1 i G 3 og G 4. Ved tredje iterasjon vurderes G 3 - det er ingen tillatte planer på denne delmengden. Først etter dette, ved den fjerde iterasjonen, blir den andre grenen som kommer ut av G 1 - en delmengde av G 4 - vurdert. Ytterligere lignende.

Ved den femte iterasjonen ble det funnet en heltallsløsning på delmengden G 5, som tilsvarer verdien av objektivfunksjonen 12. Ved neste iterasjon tildeles denne verdien verdien ZL, som tidligere var lik -1*10 20. Den tilsvarende planen huskes - den kan vise seg å være optimal. Men ved den sjette iterasjonen ble en heltallsplan igjen oppnådd, objektiv funksjon hvor den er lik 13 (mer enn 12) - ZL endres igjen, den nye planen huskes.

Etter dette, ved den syvende iterasjonen, går de videre til å vurdere delmengden G 2, som er delt inn i G 7 og G 8.

Ved den trettende iterasjonen (delmengde G 14) blir en heltallsløsning X = (0; 7) funnet igjen, objektivfunksjonen på den er lik 14. ZL endres igjen og den tilsvarende planen huskes.

Planen funnet ved den fjortende iterasjonen er også et heltall, men den huskes ikke siden 13.<14 (ZL=14). План, найденный на пятнадцатой итерации, тоже, к сожалению, не запоминается, так как 1414, а программа ставит своей целью найти хотя бы одно решение.

Tilstedeværelsen av andre optimale planer ignoreres her.

Dermed ble løsningen X = (0; 7) oppnådd i 15 iterasjoner.

Merk at hvis en mer effektiv versjon av gren- og bundet-metoden ble brukt, hvis skjema er beskrevet i retningslinjene, vil det etter den andre iterasjonen være en direkte overgang til den syvende. Faktisk, hvis vi vurderer verdiene til den objektive funksjonen på de tilsvarende planene som et estimat av undergrupper, er estimatet av G 2 høyere. Derfor er iterasjoner fra 3 til 6 overflødige, og det totale antallet iterasjoner kan være 11.

Send ditt gode arbeid i kunnskapsbasen er enkelt. Bruk skjemaet nedenfor

Studenter, hovedfagsstudenter, unge forskere som bruker kunnskapsbasen i studiene og arbeidet vil være deg veldig takknemlig.

postet på http://www.allbest.ru/

1 . Beskrivelse av metodengrener og grenser

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 med mulige løsninger; 2) beregning av nedre og øvre estimater av målfunksjonen.

1 . 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 heltallsbetingelsen på variablene.

Den første forgreningsmetoden brukes vanligvis for heltallsprogrammeringsproblemer og består i å identifisere underdomener av mulige løsninger ved å fikse verdiene til individuelle komponenter av (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 å forgrene et bestemt område D i " på denne måten på D i " løses et 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 ] er heltallsdelen av verdien x 0 [j]

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

postet på http://www.allbest.ru/

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.

1 . 2 Dannelse av nedre og øvre estimater av den objektive funksjonen

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 linje) korrekt gjenspeiler forholdet mellom de faktiske minimumsverdiene til f(x) (koblet med en stiplet linje) for fire delsett av gjennomførbare løsninger D 1 , D 2, D 3, D 4.

En av de universelle måtene å beregne nedre grenser på er å 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.

1 .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 av den stoppes, siden de potensielle mulighetene for å finne en god løsning i denne delmengden (karakteriserer dem) viser seg å være dårligere enn verdien av den objektive funksjonen for den reelle gjennomførbare løsningen funnet på et gitt tidspunkt den opprinnelige oppgaven (den 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) ):

1 .4 Løse problemet ved å bruke gren- og bindingsmetoden

Til å begynne med finner vi den optimale planen for problemet ved å bruke simpleksmetoden eller den kunstige basismetoden 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. Så, i den optimale planen, vil verdien i det minste være enten mindre enn eller lik det nærmeste mindre heltall, eller større enn eller lik det nærmeste større heltall.

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

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

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.

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.

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.

Begge problemene er løsbare, og de optimale planene for begge problemene 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:

Vi finner en løsning på et lineært programmeringsproblem uten å ta hensyn til heltall.

Oppretter ytterligere begrensninger på brøkdelen av planen.

Vi finner løsninger på to problemer med restriksjoner på komponenten.

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

La oss finne en løsning på problemet

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

Vurder følgende par problemer:

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 1.1

Oppgave 1.2

Oppgave 1.2 er uløselig, og oppgave 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.

2. 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.

2.1 Problemstilling

La oss formalisere tilstanden i form av grafteori. Byene vil være toppunktene til grafen, og veiene mellom byene vil være de orienterte (rettete) kantene på grafen, på hver av disse er det spesifisert en vektfunksjon: vekten av kanten 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. Legg merke til at det er nok å vurdere spørsmålet om tilstedeværelsen av en Hamilton-syklus i en digraf som et spesielt tilfelle av det reisende selgerproblemet 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 være en komplett rettet graf og være en 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.

Det er mest hensiktsmessig å vurdere branch and bound-metoden for å løse problemet med reisende selger på bakgrunn av et spesifikt 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 følgende 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 tidligere valgte kanter.

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.

2.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

2.3 Matematisk modell av oppgaven

For å løse problemet vil vi tildele et spesifikt nummer til hvert punkt på ruten: 12. bygning - 1, Det hvite hus - 2, KRK "Premier" - 3, Administrasjon - 4 og 5. bygning - 5. Følgelig er det totale antallet av 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 tilleggsbegrensninger (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:

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

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 den første planen: . 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 D 12-undergruppen.

3) Analyse av delmengde D 13.

4) Analyse av delmengde D 14.

5) Analyse av delmengde 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 delmengde D 142.

8) Analyse av delmengde D 143.

9) Analyse av D 145-undergruppen.

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 D 1452-undergruppen.

grengrensemålalgoritme

12) Analyse av D 1453-undergruppen.

Optimal løsning: .

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

postet på http://www.allbest.ru/

Liste over bruktelitteratur

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. og andre Matematisk programmering: Lærebok. - 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.

Skrevet på Allbest.ru

...

Lignende dokumenter

    Formulering og løsning av diskrete optimaliseringsproblemer ved bruk av den diskrete programmeringsmetoden og branch and bound-metoden ved å bruke eksemplet med det klassiske reiseselgerproblemet. Stadier for å konstruere en gren og bundet algoritme og dens effektivitet, konstruere et graftre.

    kursarbeid, lagt til 11.08.2009

    Uttalelse av den reisende selgerproblemet. Finne den optimale løsningen ved hjelp av branch and bound-metoden. Det grunnleggende prinsippet for denne metoden, rekkefølgen på dens anvendelse. Bruke den øvre grensemetoden i prosedyren for å konstruere et tre med mulige alternativer.

    kursarbeid, lagt til 10.01.2009

    Funksjoner ved gren og bundet metode som en av de vanlige metodene for å løse heltallsproblemer. Dekomponering av et lineært programmeringsproblem i gren-og-bundet algoritme. Grafisk, simpleks metode for å løse lineære programmeringsproblemer.

    kursarbeid, lagt til 03.05.2012

    Simulering av maurbevegelse. Gren og bundet metode, nærmeste nabo. Begrensninger pålagt agenten i standardformuleringen av problemet med reisende selger. Bruk av synlighetsgrafen i mauralgoritmen. Ant algoritme datastruktur.

    avhandling, lagt til 02.07.2013

    Første og andre ordens gren og bundne metoder. Optimalt og passivt søk. Ulemper ved Newtons metode. Gyldent snitt metode. Eksempler på unimodale funksjoner. Dynamisk og lineær programmering. Jordan-Gauss-metoden. Løse problemet med reisende selger.

    kursarbeid, lagt til 20.07.2012

    Essensen av grafteori og nettverksmodellering. Velge den optimale banen og kostnaden for å flytte en reisende selger ved hjelp av filial og bundet metode. Utvikling av et program for å velge den mest lønnsomme ruten som går gjennom de angitte byene minst én gang.

    kursarbeid, lagt til 08.08.2013

    Optimalisering av problemløsningen ved hjelp av annealing-algoritmen. Analyse av optimaliseringsteori som objektiv funksjon. Gradient nedstigningsmetode. Variabler og beskrivelse av annealing-algoritmen. Representasjon av det reisende selgerproblemet gjennom en graf. Redusere problemet til variabler og løse det.

    kursarbeid, lagt til 21.05.2015

    Utsagn av et lineært heltallsproblem. Skjæreplanmetode. Fraksjonell algoritme for å løse heltallsproblemer. Effektiviteten av Gomori-skjæring. Sammenligning av beregningsevnene til skjæreplanmetoden og gren- og bundetmetoden.

    kursarbeid, lagt til 25.11.2011

    Ryggsekkproblemet som et kombinatorisk optimaliseringsproblem. Problem med lasting, ryggsekk, ryggsekk. Uttalelse og NP-fullstendighet av problemet. Klassifisering av metoder for å løse ryggsekkproblemet. Dynamisk programmering. Gren og bundet metode. Komparativ analyse av metoder.

    kursarbeid, lagt til 18.01.2011

    Finne øvre og nedre grenser for optimal verdi i underdomenet av gjennomførbare løsninger. Metoder og problemer for å løse ikke-lineære programmeringsproblemer. Skrive og feilsøke et program. Oppretting av et program for å løse problemet med reisende selger ved hjelp av en direkte algoritme.

Hei, Habr! Mens jeg implementerte forskjellige algoritmer for å finne den billigste Hamilton-syklusen, kom jeg over en publikasjon som tilbyr min egen versjon. Etter å ha prøvd det, fikk jeg feil svar:

Ytterligere søk på Internett ga ikke det forventede resultatet: enten en teoretisk beskrivelse som var vanskelig for ikke-matematikere, eller forståelig, men med feil.

Under kuttet finner du en korrigert algoritme og en online kalkulator.

Selve metoden, utgitt av Little, Murthy, Sweeney, Carel i 1963, er anvendelig på mange NP-komplette oppgaver, og er et svært teoretisk materiale som uten gode kunnskaper i engelsk og matematikk ikke umiddelbart kan brukes på vårt reisende selgerproblem. .

Kort om metoden - det er et fullstendig søk av alle mulige alternativer med eliminering av klart ikke-optimale løsninger.

Korrigert algoritme for å finne en virkelig minimal rute

Algoritmen består av to trinn:

Første etappe
Redusere kostnadsmatrisen og beregne det lavere anslaget for rutekostnaden r.
1. Beregn det minste elementet i hver rad (støpekonstant for raden)
2. Vi går videre til en ny kostnadsmatrise, og trekker reduksjonskonstanten fra hver rad
3. Beregn det minste elementet i hver kolonne (tvangskonstant for kolonnen)
4. Vi går videre til en ny kostnadsmatrise, og trekker reduksjonskonstanten fra hver kolonne.
Som et resultat har vi en kostnadsmatrise der hver rad og hver kolonne har minst ett nullelement.
5. Vi beregner grensen på dette stadiet som summen av reduksjonskonstanter for kolonner og rader (denne grensen vil være kostnaden under hvilken det er umulig å konstruere den nødvendige ruten)
Andre (hoved) trinn
1. Beregning av straffen for manglende bruk for hvert nullelement i den gitte kostnadsmatrisen.
Straffen for å ikke bruke et element med indeks (h,k) i matrisen betyr at denne kanten ikke er inkludert i ruten vår, noe som betyr at minimumskostnaden ved å "ikke bruke" denne kanten er lik summen av minimumselementene i rad h og kolonne k.

A) Vi ser etter alle nullelementene i den gitte matrisen
b) For hver av dem beregner vi straffen for ikke-bruk.
c) Velg elementet som tilsvarer maksimumsstraffen (hvis det er flere av dem)

2. Nå deler vi vårt sett S i sett - de som inneholder kanten med maksimal straff (S w) og de som ikke inneholder denne kanten (S w/o).
3. Beregning av kostnadsoverslag for ruter som inngår i hvert av disse settene.
a) For settet S u/o er alt enkelt: siden vi ikke tar den tilsvarende kanten med maksimumsstraffen (h,k), så er kostnadsestimatet for det lik kostnadsestimatet for settet S + straffen for ikke å bruke kanten (h,k)
b) Ved beregning av kostnadene for settet S w tar vi hensyn til at siden kanten (h,k) er inkludert i ruten, betyr det at kanten (k,h) ikke kan inkluderes i ruten, derfor i kostnadsmatrisen skriver vi c(k,h) =uendelig, og siden vi har "allerede igjen" fra punkt h, og vi har "allerede kommet" fra punkt k, så kommer ikke en eneste kant ut av h og ikke en eneste kant at k ikke lenger kan brukes, så vi krysser ut fra kostnadsmatrisen rad h og kolonne k. Etter dette reduserer vi matrisen, og da er kostnadsestimatet for S w lik summen av kostnadsestimatet for S og r(h,k), der r(h,k) er summen av reduksjonskonstantene for den modifiserte kostnadsmatrisen.
4. Fra alle av upartisjonerte sett, velges den med lavest poengsum.

Vi fortsetter på denne måten til det er en ukrysset rad og en ukrysset kolonne igjen i kostnadsmatrisen.

Liten optimalisering - legger til heuristikk

Ja, egentlig, hvorfor introduserer vi ikke heuristikk? Faktisk, i grenen og bundet algoritme bygger vi faktisk et tre, ved nodene som vi bestemmer oss for å ta kanten (h,k) eller ikke, og henge to barn - Sw(h,k) og Sw/o( h,k). Men vi velger det beste alternativet for neste iterasjon bare basert på evaluering. Så la oss velge den beste, ikke bare når det gjelder vurdering, men også når det gjelder dybde i treet, fordi... Jo dypere det valgte elementet er, jo nærmere slutten av tellingen er det. På denne måten kan vi endelig vente på svar.

Nå, faktisk, om feilene i den publikasjonen

Det var bare én feil - du bør velge å partisjonere settet med minimumsgrensen fra alle mulige stier, og ikke fra de to barna som ble oppnådd som et resultat av den siste partisjonen.

Bevis

La oss gå tilbake til bildet i begynnelsen av innlegget:


Og her er løsningen med den korrigerte algoritmen:

Svar: bane:3=>4=>2=>1=>5=>3 lengde: 41
Som du kan se, vil det være en feil å inkludere 5:2-kanten i løsningen. Q.E.D

Graf som sammenligner gren og bundet metode og tid brukt for en tilfeldig tabell fra 5x5 til 10x10:


Graf over maksimal og minimumstid brukt for matriser fra 5x5 til 66x66.


Du kan prøve med en detaljert løsning

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.

Gren og bundet metoden består av følgende: settet med gjennomførbare løsninger (planer) deles på en eller annen måte inn i delmengder, som hver igjen er delt inn i delmengder på samme måte. Prosessen fortsetter til den optimale heltallsløsningen på det opprinnelige problemet er oppnådd.

Løsningsalgoritme:

Til å begynne med finner vi den optimale planen for problemet ved å bruke simpleksmetoden eller den kunstige basismetoden uten å ta hensyn til hele antallet variabler. La det være plan X 0 . Hvis det ikke er noen brøktall blant komponentene i denne planen, er den ønskede løsningen på dette problemet funnet og

Hvis det blant komponentene i plan X 0 er brøktall, tilfredsstiller ikke X 0 heltallsbetingelsen, og det er nødvendig å gjennomføre en ryddig overgang til nye planer til en løsning på problemet er funnet. La oss vise hvordan dette kan gjøres, først og merke at F(X 0) F(X) for enhver påfølgende plan X.

Forutsatt at den funnet optimale planen X 0 ikke tilfredsstiller betingelsen til heltallsvariabler, antar vi dermed at det blant dens komponenter er brøktall. La for eksempel variabelen få en brøkverdi i form av X 0. Så, i den optimale heltallsplanen, vil verdien i det minste være enten mindre enn eller lik det nærmeste mindre heltall, eller større enn eller lik det nærmeste større heltall. Ved å bestemme disse tallene bruker vi simpleksmetoden for å finne en løsning på to lineære programmeringsproblemer:

La oss finne en løsning på lineære programmeringsproblemer (I) og (II). Åpenbart er ett av følgende fire tilfeller mulig her:

  • 1. 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 på det opprinnelige problemet.
  • 2. 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 som ligner på oppgavene (I) og (II).
  • 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 på disse planene og sammenligner dem med hverandre. Hvis på en heltallsoptimal plan er verdien av målfunksjonen større enn eller lik dens verdi på planen, blant komponentene som det er brøktall av, så er denne heltallsplanen optimal for det opprinnelige problemet, og det, sammen med verdien av den objektive funksjonen på den, gir den ønskede løsningen.

Hvis verdien av målfunksjonen er større i planen, blant komponentene som det er brøktall av, bør ett av disse tallene tas, og for problemet hvis plan vurderes, er det nødvendig å konstruere to problemer som ligner på (I) og (II).

4. Begge oppgavene er løsbare, og de optimale planene for begge oppgavene 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 konstruerer to problemer som ligner på (I) og (II).

Dermed kan den iterative prosessen beskrevet ovenfor representeres i form av et tre der det opprinnelige toppunktet tilsvarer den optimale planen X 0 av problem (1)-(3), og hvert toppunkt koblet til det med en gren tilsvarer optimale planer for problemer (I) og (II). Hvert av disse hjørnene har sine egne grener. I dette tilfellet, ved hvert trinn, velges toppunktet der funksjonsverdien er størst. Hvis det på et eller annet trinn oppnås en plan som har heltallskomponenter, 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.

Så prosessen med å finne en løsning på heltallsprogrammeringsproblemet (1)-(4) ved bruk av branch and bound-metoden inkluderer følgende hovedstadier:

  • 1. Finn en løsning på det lineære programmeringsproblemet (1)-(3).
  • 2. Lag ytterligere restriksjoner for en av variablene, hvis verdi i den optimale planen for oppgave (1)-(3) er et brøktall.
  • 3. Finn en løsning på oppgavene (I) og (II), som er hentet fra oppgave (1)-(3) som et resultat av å legge til ytterligere begrensninger.
  • 4. Om nødvendig, lag ytterligere begrensninger for en variabel hvis verdi er brøk, formuler problemer som ligner på oppgavene (I) og (II), og finn løsningen. Den iterative prosessen fortsetter til et toppunkt er funnet som tilsvarer heltallsplanen for problem (1)-(3) og slik at verdien av funksjonen ved dette toppunktet er større enn eller lik verdien av funksjonen ved andre mulige toppunkter for forgrening.

Gren og bundet metoden beskrevet ovenfor har et enklere logisk beregningsskjema enn Gomori-metoden. Derfor brukes denne metoden i de fleste tilfeller til å finne løsninger på spesifikke heltallsprogrammeringsproblemer ved å bruke en datamaskin.

heltall programmering problem reise selger ryggsekk

Nedenfor er tilstanden til problemet og tekstdelen av løsningen. Du kan laste ned hele løsningen, i doc-format i et arkiv. Noen tegn vises kanskje ikke på siden, men alt er synlig i Word-dokumentet. 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.

Det andre trinnet involverer en trinnvis prosess for å erstatte ikke-heltallsvariabler med de nærmeste øvre eller nedre heltallsverdiene.

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- daglig lønnssats for en ansatt etter kategori;

m- antall virkedager 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)

Den matematiske modellen for å 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 løsningen finner man en heltallsløsning ved bruk av branch and bound-metoden.

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 arbeidere 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