De branch and bound-methode is. Cursuswerk: selectie van besturingsparameters met behulp van de dynamische programmeermethode en de branch and bound-methode

De ontwikkeling van de aanpak, de branch and bound-methode genoemd, begon met het werk van Land en Doig (1960). Dit is eerder niet eens een methode, maar een concept of procedurele schil, op basis waarvan oplossingsalgoritmen werden ontwikkeld gehele problemen van verschillende aard. De waarde van het voorgestelde idee werd vooral merkbaar na de verschijning van het eerste exacte algoritme voor het oplossen van het handelsreizigersprobleem, gebouwd volgens het branch-and-bound-schema (Little et al., 1963). De methode kan worden toegepast op zowel volledig als gedeeltelijk gehele getallenproblemen.

De essentie van het idee is vergelijkbaar met de beroemde grap over het vangen van een leeuw in de woestijn: we verdelen de woestijn in tweeën; als er geen leeuw is in de eerste helft, zoeken we ernaar in de tweede, die we in tweeën delen, enz. In tegenstelling tot de leeuw beweegt het optimale niet, en in die zin is onze taak gemakkelijker.

De methode bestaat uit het construeren van een boom van problemen, waarvan de wortel het oorspronkelijke probleem is, mogelijk zonder de voorwaarde van gehele getallen (IC). De onderliggende problemen worden op zo'n manier door de hogere problemen gegenereerd dat hun toelaatbare sets (AS) onsamenhangende subsets zijn van de DM van het bovenliggende probleem. De groei van de boom vindt plaats door veelbelovende takken. De vooruitzichten worden bepaald door criterium evaluatie terminaltaak van het filiaal V Endossier Z. terminaltaak van het filiaal Cijfer is de waarde van het criterium, die zeker niet slechter is dan het optimale, en Z

– de waarde van het criterium van het oorspronkelijke probleem dat tijdens het oplossingsproces is bereikt (een waarde die duidelijk slechter is dan optimaal kan als initiële waarde worden genomen). Dit betekent dat het probleem alleen generatief zal zijn als de schatting beter is dan het record. In dit geval doet het niveau waarop de taak zich bevindt er niet toe.

Het type beoordeling hangt af van de richting van het criterium: bij maximalisatie wordt de bovenste schatting gebruikt, bij minimalisering wordt de onderste schatting gebruikt. De daaropvolgende presentatie van de methode zal betrekking hebben op het maximale probleem.

Om branch-and-bound algoritmisch te implementeren, moeten twee fundamentele vragen worden beantwoord:

Hoe je een veelbelovende set in subsets kunt opsplitsen;

Hoe de bovenste schatting van een criterium op de set in kwestie te bepalen.

De antwoorden hierop zijn afhankelijk van het type probleem (gedeeltelijk of volledig geheel getal, heeft speciale eigenschappen of niet, met Booleaanse of niet-Booleaanse variabelen). Het algemene geval wordt hieronder besproken.

Laat het bereik van mogelijke waarden bekend zijn J e variabele

0  X J  D J ,

die in de continue optimale oplossing niet-geheel getal bleek te zijn en gelijk aan X J * . Dan kan de gehele waarde van deze variabele worden bereikt in het interval 0  X J 
, of in de tussentijd
+1 X J  D J, Waar
-hele deel (Afb. 7.6).

E komt dan overeen met een partitie van een continue set 22 zal slechter zijn dan het record of N in twee onsamenhangende deelverzamelingen 22 zal slechter zijn dan het record of 1 N En 22 zal slechter zijn dan het record of 2 N, waarvan de vereniging niet gelijk is 22 zal slechter zijn dan het record of N. Tegelijkertijd voldoet een dergelijke partitie van een gehele verzameling aan relaties (7.9). In dit geval worden gehele sets, zowel de originele als de gegenereerde, opgenomen in de overeenkomstige continue sets. Bijgevolg zal het zoeken naar een oplossing met gehele getallen op een continue verzameling hetzelfde resultaat opleveren als op een oplossing met gehele getallen. Het is gemakkelijk in te zien dat de bovenstaande selectie van subintervallen door één variabele leidt tot een verdeling van de oorspronkelijke set in twee subsets voor een willekeurig aantal variabelen.

Laten we nu verder gaan met de tweede vraag. Omdat een geheel getal een deelverzameling is van de overeenkomstige continue verzameling, optimale waarde het criterium voor een continue set zal altijd niet minder zijn dan voor een geheel getal. Daarom als bovengrens terminaltaak van het filiaal u kunt de optimale waarde van het criterium nemen L * continue taak.

De keuze van de initiële recordwaarde is afhankelijk van de situatie:

als er een gehele waarde bekend is, wordt het record gelijkgesteld aan het criterium in deze beslissing;

als alle coëfficiënten van het criterium positief zijn, kunnen we nemen nulwaarde dossier;

in andere gevallen wordt de initiële waarde van het record als volgt genomen: M, Waar M- het maximale aantal dat in een computer kan worden weergegeven.

Naarmate de partitie vordert, worden gegenereerde taken gevormd, die in de partitie worden geplaatst lijst met taken. De initiële lijst bevat slechts één taak: origineel probleem zonder gehele voorwaarden. En in de toekomst zal de lijst alleen doorlopende taken bevatten.

Dus, basisalgoritme, dat de branch and bound-methode implementeert, omvat de volgende stappen.

Het gegeven algoritme is eenvoudig, omdat het geen ondubbelzinnige regels bevat voor het selecteren van een taak uit een lijst en een vertakkingsvariabele. Voor problemen met gedeeltelijke gehele getallen worden continue variabelen uitgesloten bij het kiezen van een variabele om te vertakken.

Voorbeeld 7.3 . Laten we het branch-and-bound-algoritme op het probleem toepassen

L= 9X 1 + 5X 2  maximaal;

3X 1 - 6X 2  1;

5X 1 +2X 2  28;

 X J  0 , geheel.

Laten we de methode bekijken zoals toegepast op een lineair geheel getalprobleem. Hoewel er geen beperkingen zijn aan het aantal taken dat rechtstreeks door een veelbelovende taak wordt gegenereerd, gebruiken de algoritmen in de regel een verdeling in twee taken, dat wil zeggen dat er een binaire boom wordt gebouwd (Fig. 7.5). In dit geval gelden voor gehele sets de volgende relaties: Als we de getalvoorwaarde laten vallen, krijgen we een continue taak, die we in de lijst met taken plaatsen. Omdat de criteriumcoëfficiënten positief zijn, wordt de initiële waarde van het record gelijk aan nul gesteld. We nemen één probleem uit de lijst en lossen het op. We verkrijgen de optimale oplossing bij hoekpunt A (Fig. 7.7): X 1 * =4,72; X 2 * =2,19. We vertakken zich volgens de variabele X 1. Een beperking toevoegen aan een opgelost probleem X 1 4 vormen we probleem 2, en de optelling X 1 5 geeft probleem 3. De toelaatbare sets van nieuwe problemen worden getoond in Fig. 7.7. Deze taken plaatsen wij in de takenlijst. De oplossing voor probleem 2 wordt bereikt op punt B, en probleem 3 op punt C. Het hele proces van het oplossen van het oorspronkelijke probleem wordt weergegeven in de vorm van een beslisboom in figuur 2. 7.10. De volgorde van het oplossen van problemen uit de lijst wordt weergegeven door de iteratieteller k. Bij de derde iteratie (taak 4) werd een gehele oplossing verkregen met een criteriumwaarde van 41 (punt D in figuur 7.8). Daarom verandert het record: is de waarde van het criterium, die zeker niet slechter is dan het optimale, en=41. Probleem 6 heeft een niet-gehele oplossing (hoekpunt E in figuur 7.9), probleem 8 heeft een gehele oplossing in punt F. Als gevolg hiervan wordt het record na de zevende iteratie 50.

Uit de bovenstaande beslissingsboom blijkt dat het aantal taken in de lijst kleiner zou kunnen zijn als de taken in een andere volgorde zouden worden opgelost. Sterker nog, als eerst de problemen van de juiste tak met het record waren opgelost Z= 50, dan zou er na het oplossen van Probleem 2 geen vertakking zijn, omdat de bovenste schatting lager zou zijn dan het record ( V=L * =45,17<50).

E De vraag rijst natuurlijk: hoe kan de keuze van een andere variabele voor vertakking het aantal taken en de beslisboom beïnvloeden? Dus in ons voorbeeld vertakken we na de eerste iteratie volgens de variabele X 2, dan krijgen we de boom getoond in Fig. 7.11. Het bevat 2 taken meer dan in Fig. 7.10. Uiteraard kan het ook anders zijn als de problemen in een andere volgorde worden opgelost.

Het aantal op te lossen taken hangt dus aanzienlijk af van de keuze van de taak uit de lijst en de variabele voor vertakking.

Uit het gegeven algoritme en het gegeven voorbeeld volgt dat de vertakking om een van de volgende drie redenen wordt beëindigd:

onoplosbaarheid van het probleem;

het probleem heeft een geheeltallige oplossing;

de bovenste schatting is niet meer dan een record.

Nu zullen we een aantal opmerkingen maken over de branch-and-bound-methode. Zoals reeds opgemerkt specificeert het basisalgoritme niet de regels voor het selecteren van een taak en een variabele. De meeste software-implementaties van de methode gebruiken regels die zijn gebaseerd op heuristische beoordelingen van de vooruitzichten van taken en variabelen. Sommige pakketten, bijvoorbeeld ‘LP in ACS’, bieden verschillende opties voor het beheren van het oplossingsproces: van automatisch tot handmatig, waarbij de gebruiker zijn eigen keuze kan maken uit zowel de taak als de variabele. Bovendien kunnen algoritmen die zijn gebaseerd op de branch-and-bound-methode aanzienlijk verschillen vanwege de kenmerken van de klasse van problemen. Voor het handelsreizigersprobleem wordt het bepalen van de schatting bijvoorbeeld sterk vereenvoudigd (er is geen noodzaak om een continu lineair probleem op te lossen).

De branch and bound-methode heeft voordelen ten opzichte van de snijmethode:

de opeenstapeling van fouten is minder significant, omdat de oplossing langs verschillende takken gaat;

wanneer het oplossingsproces gedwongen wordt te stoppen, is de kans groot dat een geheel getal resultaat wordt verkregen, maar zonder de optimaliteit ervan vast te stellen;

Bij het oplossen van continue problemen nemen de afmetingen van simplextabellen niet toe.

Nadelen van de branch-and-bound-methode:

Het aantal problemen dat moet worden opgelost, is onmogelijk in te schatten. Hoe dichter de initiële waarde van het record van onderaf en de schatting van het criterium van het probleem van bovenaf ligt bij de gewenste optimale waarde van het criterium, hoe minder hoekpunten de beslissingsboom zal hebben, en dus hoe minder middelen worden uitgegeven. Het overschatten van de oorspronkelijke gegevens kan er echter toe leiden dat het probleem onoplosbaar wordt, wat altijd in gedachten moet worden gehouden.

Geen teken van optimaliteit. De optimale oplossing kan worden verkregen lang voordat het algoritme stopt, maar in het algemeen kan dit niet worden gedetecteerd. Optimaliteit komt pas tot stand als de lijst met taken is uitgeput.

Het is duidelijk dat de efficiëntie van de methode toeneemt met afnemende bereiken van variabele waarden en het aantal niet-gehele variabelen bij het oplossen van het eerste continue probleem.

Laten we het discrete programmeerprobleem in algemene vorm bekijken:

Vind -vector van onbekenden, D- eindig

de reeks toelaatbare waarden van deze vector, F(x), is de gegeven objectieve functie.

Het idee van de methode is om D in disjuncte deelverzamelingen Di te verdelen (deze procedure wordt vertakking genoemd) en de boven- en ondergrenzen van de objectieve functie op elk van de deelverzamelingen te berekenen. We zullen de ondergrens aangeven met H, en de bovengrens met E. Dienovereenkomstig, Hallo Eo, bevat deze deelverzameling niet het optimale punt en kan deze van verdere overweging worden uitgesloten. Als de bovengrens Ei H is, vervang dan H door min Hi. Als E=H, dan is het probleem opgelost, anders is het noodzakelijk om de vertakkingsprocedure voort te zetten en de boven- en ondergrenzen te berekenen. In dit geval kunnen alle of slechts enkele subsets bij de volgende stap worden gepartitioneerd totdat gelijkheid van de boven- en ondergrenzen is bereikt, en niet op een afzonderlijke subset, maar voor het toegestane gebied als geheel.

Het eenvoudige idee van de branch and bound-methode vereist extra berekeningen om de grenzen te bepalen. In de regel leidt dit tot de oplossing van een hulpoptimalisatieprobleem. Als deze aanvullende berekeningen een groot aantal bewerkingen vereisen, kan de effectiviteit van de methode laag zijn.

Het dynamische programmeerschema bij het verplaatsen van het startpunt naar het eindpunt (Fig. 5.1) kan worden weergegeven als een vertakkingsprocedure.

De verzameling van alle toegestane trajecten (een reeks stapsgewijze overgangen) is de initiële verzameling D, waarop we de onder- en bovengrenzen moeten vinden, evenals het traject waarop de objectieve functie de bovengrens bereikt en verklaart de overeenkomstige waarde van de doelfunctie als record. De constructie van de reeks toestanden verkregen na de eerste stap is de eerste tak.

Rijst. 5.1.

Nu zijn de subsets van Di sets trajecten, die elk door het overeenkomstige i-de punt gaan.

In daaropvolgende stappen, na het verwerpen van alle paden die naar een (i-oe) toestand leiden, behalve één, is de corresponderende subset dit resterende pad met al zijn geldige voortzettingen (Fig. 5.1). Voor elk van deze subsets moeten we op de een of andere manier de boven- en ondergrenzen vinden. Als de ondergrens de huidige recordwaarde overschrijdt, worden de overeenkomstige toestand en al zijn voortzettingen afgewezen. Als de bovengrens op een bepaald traject wordt bereikt en deze is lager dan de huidige recordwaarde, dan krijgen we een nieuw record.

De effectiviteit van deze aanpak hangt af van de nauwkeurigheid van de verkregen schattingen, d.w.z. van Ei - Hallo, en van de tijd besteed aan hun berekening.

In vereenvoudigde vorm hebben we deze methode zelfs al gebruikt bij het oplossen van het probleem van oppervlaktebescherming (paragraaf 4.6), toen we staten verwierpen waarvoor de huidige kosten de totale kosten voor de initiële benadering overschreden. In dit geval vormen de huidige kosten de ondergrens, als we uitgaan van nulkosten voor het gehele resterende pad, en zijn de totale kosten die overeenkomen met de initiële benadering een record. Met deze aanpak werd het record niet bijgewerkt, hoewel dit kon worden gedaan door een initiële benadering (bovengrens) voor het resterende pad te construeren op dezelfde manier als voor het gehele traject werd gedaan bij het construeren van de initiële benadering. De zonder berekeningen verkregen ondergrens komt overeen met nulkosten voor het gehele resterende traject en is een uiterst ruwe schatting, maar wordt “gratis” verkregen, d.w.z. zonder berekeningen.

We zullen laten zien hoe u nauwkeurigere schattingen kunt verkrijgen en gebruiken bij het oplossen van de hierboven besproken problemen en een aantal andere problemen. In dit geval zullen we ernaar streven om met een minimum aan berekeningen de meest nauwkeurige grenzen te verkrijgen.

Invoering

Een grote klasse van toegepaste optimalisatieproblemen reduceert zich tot gehele programmeerproblemen. Om deze problemen op te lossen, worden op grote schaal combinatorische methoden gebruikt, gebaseerd op een geordende zoektocht naar de meest veelbelovende opties. Combinatorische oplossingsmethoden kunnen in twee groepen worden verdeeld: dynamische programmeermethoden en branch-and-bound-methoden.

Bij het oplossen van multidimensionale optimalisatieproblemen wordt de gezamenlijke toepassing van branch-and-bound-methoden en dynamisch programmeren voorgesteld. In de eerste fase wordt het probleem opgelost met behulp van de dynamische programmeermethode, afzonderlijk voor elk van de beperkingen. De reeksen die worden verkregen als resultaat van het oplossen van de functionele vergelijking van dynamische programmering worden vervolgens gebruikt om de boven- (onder)grens van de objectieve functie te schatten. In de tweede fase wordt het probleem opgelost met behulp van de branch and bound-methode. Bij gebruik van deze methode wordt een methode bepaald om de gehele set haalbare opties in subsets te verdelen, dat wil zeggen een methode voor het construeren van een boom van mogelijke opties, en een methode voor het schatten van de bovengrens van de doelfunctie.

De geïntegreerde toepassing van dynamisch programmeren en branch-and-bound-methoden maakt het mogelijk om de efficiëntie van het oplossen van discrete optimalisatieproblemen te vergroten. Bij het oplossen van hoogdimensionale problemen worden aanvullende snijomstandigheden gebruikt om de voorwaarden van de optimale volgorde te beperken.

1. Historische achtergrond

De branch and bound-methode werd voor het eerst voorgesteld door Land en Doig in 1960 om een algemeen lineair programmeringsprobleem met gehele getallen op te lossen. De belangstelling voor deze methode, en in feite voor de ‘wedergeboorte’ ervan, houdt verband met het werk van Little, Murthy, Sweeney en Carell over het handelsreizigersprobleem. Sindsdien is er een groot aantal werken verschenen gewijd aan de branch and bound-methode en de verschillende wijzigingen ervan. Dit grote succes wordt verklaard door het feit dat de auteurs de eersten waren die aandacht schonken aan de breedte van de mogelijkheden van de methode, het belang opmerkten van het gebruik van de specifieke kenmerken van het probleem, en zelf voordeel haalden uit de specifieke kenmerken van het handelsreizigerprobleem.

Deze methode is de meest algemene van alle discrete programmeermethoden en kent geen fundamentele toepassingsbeperkingen. Het branch-and-bound-algoritme is een efficiënte procedure voor het opsommen van alle haalbare oplossingen met gehele getallen.

De branch and bound-methode is een van de combinatorische methoden. De essentie ervan ligt in een ordelijke selectie van opties en het overwegen van alleen die opties die volgens bepaalde criteria veelbelovend blijken te zijn, en het terzijde schuiven van weinig belovende opties.

2. Beschrijving van de methode

De branch and bound-methode is gebaseerd op het idee om de reeks haalbare oplossingen opeenvolgend in subsets te verdelen. Bij elke stap van de werkwijze worden de partitie-elementen gecontroleerd om te bepalen of een gegeven subset de optimale oplossing bevat of niet. Verificatie wordt uitgevoerd door een lagere schatting te berekenen voor de objectieve functie op een gegeven subset. Als de lagere schatting niet kleiner is dan dossier- de gevonden beste oplossing, waarna de subset kan worden weggegooid. De aangevinkte deelverzameling kan ook worden weggegooid als daarin de beste oplossing kan worden gevonden. Als de waarde van de doelfunctie op de gevonden oplossing kleiner is dan het record, verandert het record. Aan het einde van het algoritme is het record het resultaat van zijn werk.

Als het mogelijk is om alle elementen van de partitie weg te gooien, dan is het record de optimale oplossing voor het probleem. Anders wordt de meest veelbelovende gekozen uit de niet-weggegooide subsets (bijvoorbeeld met de laagste ondergrenswaarde) en wordt deze gesplitst. Nieuwe subsets worden opnieuw gecontroleerd, enz.

Wanneer de branch and bound-methode op elk specifiek probleem wordt toegepast, moeten allereerst de twee belangrijkste procedures worden bepaald: 1) het vertakken van de reeks mogelijke oplossingen; 2) berekening van onderste en bovenste schattingen van de objectieve functie.

2.1 Vertakkingsregels

Afhankelijk van de kenmerken van de taak wordt meestal een van de twee methoden gebruikt om vertakkingen te organiseren:

1. vertakking van de reeks haalbare oplossingen voor het oorspronkelijke probleem D;

2. vertakking van de verzameling D" verkregen uit D door de integriteitsvoorwaarde voor de variabelen te verwijderen.

De eerste vertakkingsmethode wordt meestal gebruikt voor programmeerproblemen met gehele getallen en bestaat uit het identificeren van subdomeinen van mogelijke oplossingen door de waarden van individuele componenten van optimalisatievariabelen met gehele getallen vast te leggen (Fig. 1). In afb. 1-a geeft een geometrische interpretatie van het gebied van toelaatbare oplossingen voor het gehele programmeringsprobleem, bepaald door twee lineaire beperkingen en voorwaarden voor de niet-negativiteit van variabelen, en de subregio's gevormd door vertakkingen, en in Fig. Figuur 1-b toont het overeenkomstige vertakkingsdiagram.

De tweede vertakkingsmethode is universeler dan de eerste. Om een bepaald gebied D i " op deze manier te vertakken naar D i " wordt een optimalisatieprobleem opgelost met de doelfunctie van het oorspronkelijke probleem en reële variabelen.

Vertakking wordt uitgevoerd als in de optimale oplossing de waarde van ten minste één gehele variabele in de oorspronkelijke formulering van het probleem niet geheel getal is. Van deze variabelen wordt er één geselecteerd, bijvoorbeeld j - i. Laten we de waarde ervan in de gevonden optimale oplossing x 0 [j] aangeven. Ze zeggen dat vertakkingen worden uitgevoerd door de variabele x[j]. De regio D i " is als volgt verdeeld in twee subregio's D i1 " en D i2 ":

waarbij ] het gehele deel is van de waarde x 0 [j]

In afb. 2 geeft conventioneel een geometrische interpretatie van een dergelijke vertakking.

Rijst. 2. Geometrische interpretatie van vertakkingen

Het is te zien dat in dit geval het deel tussen de vlakken van de nieuw geïntroduceerde beperkingen wordt verwijderd uit het domein D i ". Omdat de variabele x[j] volgens de voorwaarden van het domein van toelaatbare oplossingen van het oorspronkelijke probleem een geheel getal is , dan wordt vanuit het subdomein van toelaatbare oplossingen van het oorspronkelijke probleem, met een dergelijke uitzondering, geen beslissing uitgesloten.

2.2 Vorming van onderste en bovenste schattingen van de objectieve functie

Voordat we dit onderwerp gaan bespreken, moet gezegd worden dat het algemeen aanvaard is om de branch and bound-methode te gebruiken voor een probleem waarbij de optimalisatierichting wordt gereduceerd tot de vorm van minimalisatie. Om de verdere notatie en berekeningen compacter te maken, zullen we het discrete programmeerprobleem, waarvoor we de branch and bound-methode zullen gebruiken, in de volgende algemene vorm schrijven:

waarbij x een vector is van optimalisatievariabelen, waarvan sommige reëel zijn en andere geheeltallig; f(x) - in het algemene geval een niet-lineaire objectieve functie; D is het gebied van haalbare oplossingen voor een algemeen discreet programmeerprobleem.

Lagere schattingen van de doelwoorden kunnen, afhankelijk van de gekozen vertakkingsmethode, worden bepaald voor de deelgebieden D i D of voor de deelgebieden D i "D" (D i " en D" worden verkregen uit de overeenkomstige sets D i en D door het verwijderen van de integriteitsvoorwaarden voor discrete variabelen).
De lagere schatting van de objectieve functie f(x) op de verzameling Di (of Di ") zal de hoeveelheid zijn:

Bij het berekenen van de ondergrenzen in elk specifiek geval kan rekening worden gehouden met de kenmerken van het probleem dat wordt opgelost. Tegelijkertijd moeten schattingen, om hun functie zo effectief mogelijk te kunnen vervullen, zo groot mogelijk zijn, dat wil zeggen: zo dicht mogelijk bij de werkelijke waarden van min f(x) liggen. Dit is in de eerste plaats nodig zodat de lagere schattingen zo nauwkeurig mogelijk de werkelijke relatie min f(x) weerspiegelen op de deelverzamelingen die tijdens het vertakken worden gevormd en ons in staat stellen de richting van verder zoeken naar de optimale oplossing voor de vertakking nauwkeuriger te bepalen. origineel probleem.

In afb. Figuur 3 toont zo'n ideaal geval waarin de lagere schattingen (verbonden door een onderbroken stippellijn) correct de relaties weerspiegelen tussen de werkelijke minimumwaarden van f(x) (verbonden door een stippellijn) voor vier subsets van haalbare oplossingen D 1 , D2, D3, D4.

Een van de universele manieren om de ondergrenzen te berekenen is door het volgende probleem op te lossen:

O i op deze manier gedefinieerd is een lagere schatting van f(x) op Di (of Di "), aangezien Di D i ".

Als bij het oplossen van probleem (4) dit wordt vastgesteld, zullen we dat in het algemeen aannemen.

Het is noodzakelijk om één belangrijke eigenschap van lagere schattingen op te merken, namelijk dat hun waarden voor de subsets die tijdens het vertakken worden gevormd, niet lager kunnen zijn dan de lagere schatting van de objectieve functie op de set die aan vertakking wordt onderworpen.

Samen met de ondergrens gebruikt de branch and bound-methode bovengrenzen f(x). In de regel wordt slechts één waarde van de bovengrens berekend, die wordt gedefinieerd als de waarde van de doelfunctie voor de best gevonden haalbare oplossing voor het oorspronkelijke probleem. Deze bovenste schatting wordt soms een record genoemd. Als het, om het probleem op te lossen, mogelijk is om heel eenvoudig en nauwkeurig de bovengrenzen f(x) te verkrijgen voor individuele verzamelingen die tijdens het vertakken worden gevormd, dan moeten deze in de methode worden gebruikt om de rekencomplexiteit van het oplossingsproces te verminderen. Bij gebruik van een enkele bovengrens wordt doorgaans aangenomen dat de initiële waarde gelijk is aan oneindig (), tenzij er uiteraard op grond van a priori overwegingen geen haalbare oplossing voor het oorspronkelijke probleem bekend is. Bij het vinden van de eerste haalbare oplossing:

Vervolgens wordt bij het bepalen van een beter haalbare oplossing de bovengrens aangepast:

De waarde van de bovenste schatting kan dus alleen maar afnemen tijdens het oplossen van het probleem.

2.3 Branch en bound-algoritme

De basisregels van het algoritme kunnen als volgt worden geformuleerd:

1. Allereerst is de deelverzameling met het nummer dat overeenkomt met de laagste waarde van de lagere schatting van de objectieve functie onderhevig aan vertakking (I is de verzameling getallen van alle deelverzamelingen, (of) gelegen aan de uiteinden van de takken en waarvan de vertakking nog niet is stopgezet). Als de bovenstaande methode voor het vertakken van sets wordt geïmplementeerd, kan er onduidelijkheid ontstaan over de keuze van de component waarlangs de volgende vertakkingsstap moet worden uitgevoerd. Helaas is de vraag naar de ‘beste’ manier van een dergelijke keuze vanuit een algemeen perspectief nog niet opgelost, en daarom worden bij specifieke problemen enkele heuristische regels gebruikt.

2. Als voor een bepaalde i-de deelverzameling aan de voorwaarde is voldaan, moet de vertakking ervan worden gestopt, aangezien de potentiële mogelijkheden om een goede oplossing in deze deelverzameling te vinden (die ze kenmerkt) slechter blijken te zijn dan de waarde van de objectieve functie voor de werkelijk haalbare oplossing die op een bepaald moment voor de oorspronkelijke taak werd gevonden (die kenmerkend is).

3. Het vertakken van de deelverzameling stopt als de optimale oplossing gevonden in probleem (4) wordt gevonden. Dit wordt gerechtvaardigd door het feit dat er daarom geen beter haalbare oplossing bestaat dan in deze subset. In dit geval wordt de mogelijkheid van aanpassing overwogen.

4. Indien, waar, dan is voldaan aan de optimaliteitsvoorwaarden voor de best haalbare oplossing die op dit moment wordt gevonden. De reden hiervoor is dezelfde als paragraaf 2 van deze regels.

5. Nadat ten minste één haalbare oplossing voor het oorspronkelijke probleem is gevonden, kan de mogelijkheid om het algoritme te stoppen worden overwogen met een beoordeling van de nabijheid van de beste van de resulterende haalbare oplossingen tot de optimale (gebaseerd op de waarde van de doelfunctie ):

2.4 Het probleem oplossen met behulp van de branch and bound-methode

Geheel .

In eerste instantie vinden we het optimale plan van het probleem met behulp van de simplexmethode of de kunstmatige basismethode zonder rekening te houden met het gehele aantal variabelen.

Als er geen fractionele getallen voorkomen tussen de componenten van dit plan, dan is de gewenste oplossing voor dit probleem gevonden.

Als er fractionele aantallen onder de plancomponenten voorkomen, is het noodzakelijk om over te stappen op nieuwe plannen totdat er een oplossing voor het probleem is gevonden.

De branch-and-bound-methode is gebaseerd op de aanname dat ons optimale niet-gehele ontwerp een functiewaarde oplevert die groter is dan enig volgend vertakkingsontwerp.

Laat de variabele in het plan een gebroken getal zijn. In het optimale plan zal de waarde ervan dan op zijn minst kleiner zijn dan of gelijk zijn aan het dichtstbijzijnde kleinere gehele getal, of groter dan of gelijk zijn aan het dichtstbijzijnde grotere gehele getal.

Door deze getallen te bepalen, gebruiken we de simplexmethode om een oplossing te vinden voor twee lineaire programmeerproblemen

- geheel .

Geheel .

Er zijn vier mogelijke gevallen bij het oplossen van dit paar problemen:

1. Een van de problemen is onoplosbaar, en de andere heeft een optimaal plan met gehele getallen. Dan bieden dit plan en de waarde van de doelfunctie een oplossing voor het oorspronkelijke probleem.

2. Een van de problemen is onoplosbaar, en de andere heeft een niet-geheel optimaal plan. Vervolgens beschouwen we het tweede probleem en selecteren we in het optimale plan een van de componenten waarvan de waarde gelijk is aan een gebroken getal en construeren we twee problemen die vergelijkbaar zijn met de vorige.

3. Beide problemen zijn oplosbaar. Eén van de problemen heeft een optimaal geheeltallig plan, en het optimale plan van het andere probleem heeft breukgetallen. Vervolgens berekenen we uit de plannen de waarden van de doelfunctie en vergelijken deze met elkaar. Als op een geheel getal optimaal plan de waarde van de doelfunctie groter is dan of gelijk is aan de waarde ervan op een plan waarvan de componenten fractionele getallen bevatten, dan is dit geheel getal plan optimaal voor het oorspronkelijke probleem en geeft het de gewenste oplossing.

4. Beide problemen zijn oplosbaar, en de optimale plannen voor beide problemen omvatten breuken. Vervolgens bekijken we het probleem waarvoor de waarde van de doelfunctie het grootst is. En we construeren twee taken.

Bij het oplossen van het probleem verkrijgen we dus het volgende diagram:

1. Vind een oplossing voor het lineaire programmeringsprobleem zonder rekening te houden met integriteit.

2. Creëert aanvullende beperkingen op de fractionele component van het plan.

3. Zoek een oplossing voor twee problemen met beperkingen op het onderdeel.

4. Indien nodig construeren we aanvullende beperkingen op basis van de mogelijke vier gevallen, verkrijgen we een optimaal geheelplan of stellen we de onoplosbaarheid van het probleem vast.

Voorbeeld

Laten we een oplossing voor het probleem vinden

Geheel .

Oplossing. We vinden een oplossing zonder rekening te houden met de gehele waarde van het probleem met behulp van de simplexmethode.

Beschouw het volgende paar problemen:

Taak nr. 1

en taak nr. 2

Het eerste probleem heeft een optimaal plan

de tweede is onoplosbaar.

Wij controleren het plan van de eerste taak op integriteit. Aan deze voorwaarde is niet voldaan, dus construeren we de volgende taken:

Taak nr. 1.1

en taak nr. 1.2

Probleem nr. 1.2 is onoplosbaar, en probleem nr. 1.1 heeft een optimaal plan waarop de waarde van het objectief functioneert.

Als gevolg hiervan hebben we ontdekt dat het oorspronkelijke geheeltallige programmeerprobleem een optimaal plan heeft.

3. Het handelsreizigersprobleem oplossen met behulp van de branch and bound-methode

Laten we nu eens kijken naar de klasse van toegepaste optimalisatieproblemen. In veel daarvan wordt de branch-and-bound-methode gebruikt. Er wordt voorgesteld om een van de meest populaire problemen onder de loep te nemen: het handelsreizigersprobleem. Hier is de bewoording ervan. Er zijn verschillende steden die op de een of andere manier met elkaar verbonden zijn door wegen van een bepaalde lengte; er moet worden vastgesteld of er een pad bestaat waarlangs men elke stad slechts één keer kan bezoeken en tegelijkertijd kan terugkeren naar de stad waar het pad begon (“omweg van de handelsreiziger”), en, als zo’n pad bestaat, om stel de kortste van dergelijke paden vast.

3.1 Probleemstelling

Laten we de voorwaarde formaliseren in termen van grafentheorie. De steden zullen de hoekpunten van de grafiek zijn, en de wegen tussen steden zullen de georiënteerde (gerichte) randen van de grafiek zijn, op elk waarvan een gewichtsfunctie is gespecificeerd: het gewicht van de rand is de lengte van de overeenkomstige weg. Het pad dat moet worden gevonden is een georiënteerde, eenvoudige cyclus met minimaal gewicht in de digraph (denk eraan: een cyclus wordt overspannen genoemd als deze door alle hoekpunten van de grafiek gaat; een cyclus wordt eenvoudig genoemd als hij door elk van zijn punten gaat. hoekpunten slechts één keer; een cyclus wordt georiënteerd genoemd als het begin van elke volgende rand samenvalt met het einde van de vorige; het gewicht van de cyclus is uiteindelijk de som van de gewichten van zijn randen; bevat alle mogelijke randen); dergelijke cycli worden ook Hamiltoniaans genoemd.

Uiteraard bevat een volledige digraph cycli van het hierboven aangegeven type. Merk op dat het voldoende is om de kwestie van de aanwezigheid van een Hamiltoniaanse cyclus in een digraph te beschouwen als een speciaal geval van het handelsreizigerprobleem voor volledige digraphs. Als een gegeven digraph niet compleet is, kan deze tot volledigheid worden aangevuld met de ontbrekende randen en kan een gewicht ϐ worden toegekend aan elk van de toegevoegde randen, ervan uitgaande dat Ԑ “computer-oneindigheid” is, d.w.z. het maximum van alle mogelijke aantallen die in aanmerking worden genomen. Als we nu de lichtste Hamiltoniaanse cyclus vinden in de nieuw geconstrueerde volledige digraaf, dan kunnen we, als deze randen met gewicht heeft, zeggen dat er geen “reizigercyclus” in deze originele grafiek voorkomt. Als in een volledige digraph de lichtste Hamiltoniaanse cyclus eindig in gewicht blijkt te zijn, dan zal dit de gewenste cyclus in de originele grafiek zijn.

Hieruit volgt dat het voldoende is om het handelsreizigersprobleem op te lossen voor volledige digraphs met een gewichtsfunctie. Laten we dit nu in zijn definitieve vorm formuleren:

laat een volledig gerichte grafiek zijn en een gewichtsfunctie; zoek een eenvoudige, op spanning gerichte cyclus ("handelsreizigerscyclus") met een minimaal gewicht.

Laat de specifieke samenstelling van de reeks hoekpunten de gewichtsmatrix zijn van een gegeven digraph, d.w.z. , en voor iedereen.

Het is het handigst om de branch-and-bound-methode voor het oplossen van het handelsreizigersprobleem te beschouwen tegen de achtergrond van een specifiek voorbeeld. Met behulp van de hier geïntroduceerde notatie voeren we deze beschrijving uit in de volgende lezing.

Laten we enkele termen introduceren. Laat er een numerieke matrix zijn. Om een rij van deze matrix te verkleinen, betekent dit dat je het minimumelement in de rij selecteert (dit wordt de reductieconstante genoemd) en dit aftrekt van alle elementen van deze rij. Het is duidelijk dat als gevolg hiervan het minimumelement in deze regel nul zal zijn en dat alle andere elementen niet-negatief zullen zijn. De woorden “geef een matrixkolom” hebben een vergelijkbare betekenis.

De woorden matrix rij voor rij brengen betekent dat alle rijen van de matrix gegeven zijn. De woorden “een matrix verkleinen met kolommen” hebben een vergelijkbare betekenis.

Ten slotte betekenen de woorden ‘matrix verkleinen’ dat de matrix eerst wordt verkleind met rijen en vervolgens wordt verkleind met kolommen.

Het gewicht van een matrixelement is de som van de matrixreductieconstanten, die wordt verkregen uit een gegeven matrix door het betreffende element te vervangen door ϐ. Daarom betekenen de woorden zwaarste nul in de matrix dat het gewicht van elke nul in de matrix wordt berekend, en vervolgens wordt de nul met het maximale gewicht vastgesteld.

Laten we nu verder gaan met het beschrijven van de branch-and-bound-methode voor het oplossen van het handelsreizigersprobleem.

Eerste stap. We leggen de verzameling van alle traversals van de handelsreiziger vast (d.w.z. alle eenvoudig georiënteerde overspannende cycli). Omdat de grafiek compleet is, is deze set zeker niet leeg. Laten we er een getal aan associëren dat de rol van een waarde zal spelen in deze set van de evaluatiefunctie: dit getal is gelijk aan de som van de reductieconstanten van de gegeven matrix van gewichten van de grafiekranden. Als de verzameling van alle ronden van een handelsreiziger wordt aangegeven met G, dan wordt de som van de reductieconstanten van de gewichtsmatrix aangegeven met j(G). De gegeven matrix van gewichten voor deze grafiek moet onthouden worden; laten we het aangeven met M 1; Dus het resultaat van de eerste stap:

de verzameling G van alle ronden van de handelsreiziger wordt geassocieerd met het getal j(G) en de matrix M 1 .

Tweede stap. Laten we het zwaarste nulpunt in de matrix M 1 kiezen; laat hem in een kooi staan; We leggen een rand van de grafiek vast en verdelen de verzameling G in twee delen: een deel dat bestaat uit traversals die door de rand gaan, en een deel dat bestaat uit traversals die niet door de rand gaan.

Laten we de volgende matrix M 1,1 associëren met de verzameling: in de matrix M 1 vervangen we het getal in de cel door ϐ. Vervolgens schrappen we in de resulterende matrix rijnummer i en kolomnummer j, en behouden we de overige rijen en kolommen met hun oorspronkelijke nummers. Laten we ten slotte deze laatste matrix verkleinen en de som van de reductieconstanten onthouden. De resulterende gereduceerde matrix zal de matrix M 1,1 zijn; We voegen de som van de zojuist onthouden reductieconstanten toe aan j(G) en het resultaat, verder aangegeven met j(), is vergelijkbaar met de set.

Nu associëren we ook een bepaalde matrix M 1,2 met de verzameling. Om dit te doen, vervangen we in de matrix M 1 het getal in de cel door ϐ en presenteren we de resulterende matrix. Laten we de som van de reductieconstanten onthouden en de resulterende matrix aangeven met M 1,2. Laten we de herinnerde som van de reductieconstanten optellen bij het getal j(G) en het resulterende getal, verder aangegeven met j(), is vergelijkbaar met de verzameling.

Laten we nu tussen de sets diegene kiezen waarop de functie j minimaal is (dat wil zeggen de set die overeenkomt met het kleinste van de getallen j() en j()).

Laten we nu opmerken dat in de bovenstaande redenering slechts één feitelijk object als aanvankelijk object werd gebruikt: de gereduceerde matrix van gewichten van een gegeven digraph. Hiermee werd een bepaalde rand van de grafiek geïdentificeerd en werden nieuwe matrices geconstrueerd, waarop uiteraard hetzelfde kan worden toegepast.

Bij elke herhaalde toepassing wordt de volgende rand van de grafiek geregistreerd. Laten we het eens worden over de volgende actie: voordat we een rij en een kolom in de volgende matrix verwijderen, is het noodzakelijk om de getallen in al die cellen die overeenkomen met randen die duidelijk niet behoren tot de Hamiltoniaanse cycli die door de matrix gaan, te vervangen door ϐ. eerder geselecteerde randen.

We zullen hetzelfde herhalen voor de geselecteerde set met de bijbehorende matrix en het getal j, enzovoort, zolang dit mogelijk is.

Het is bewezen dat het resultaat een set zal zijn die bestaat uit een enkele ronde van de handelsreiziger, waarvan het gewicht gelijk is aan de volgende waarde van de functie j; er is dus voldaan aan alle voorwaarden die zijn besproken bij het beschrijven van de branch and bound-methode.

Hierna wordt het record verbeterd totdat het definitieve antwoord is verkregen.

3.2 Toestand van het probleem

Student Ivanov kreeg de taak enkele belangrijke documenten uit het 12e gebouw af te leveren. Maar het toeval wil dat hij hier heel weinig tijd voor heeft, en hij moet nog steeds terug. We moeten de kortste weg vinden. De afstanden tussen objecten staan in de tabel

3.3 Wiskundig model van het probleem

Om het probleem op te lossen, zullen we aan elk punt op de route een specifiek nummer toewijzen: 12e gebouw - 1, Witte Huis - 2, KRK "Premier" - 3, Administratie - 4 en 5e gebouw - 5. Dienovereenkomstig is het totale aantal punten. Vervolgens introduceren we alternatieve variabelen die de waarde 0 aannemen als de overgang van het i-de punt naar het j-de punt niet in de route is opgenomen, en anders 1. De voorwaarden voor aankomst op elk punt en vertrek uit elk punt worden slechts één keer uitgedrukt door gelijkheden (8) en (9).

Om de continuïteit van de route te garanderen, zijn aanvullende N variabelen en aanvullende beperkingen (10).

Totale routelengte F, dat moet worden geminimaliseerd, wordt in de volgende vorm geschreven:

In ons geval zullen deze voorwaarden in de volgende vorm worden geschreven:

3.4 Het probleem oplossen met behulp van de branch and bound-methode

taak reizende verkoper takgrens

1) Analyse van set D.

Laten we een lagere schatting zoeken N. Om dit te doen definiëren we een matrix van minimale afstanden per rij (1 waarbij de afstand minimaal is in een rij).

Op dezelfde manier definiëren we de matrix van minimale afstanden langs de kolommen.

Laten we het oorspronkelijke plan kiezen: . Dan is de bovengrens:

Uiteraard betekent 'waar' de overgang van het eerste punt naar het j-de punt. Laten we deze subsets in volgorde bekijken.

2) Analyse van deelverzameling D 12 .

3) Analyse van deelverzameling D 13 .

4) Analyse van deelverzameling D 14 .

5) Analyse van deelverzameling D 15 .

6) Het screenen van weinig belovende subgroepen.

Subsets D 13 en D 15 zijn niet veelbelovend. Omdat , maar dan zullen we de deelverzameling D 14 verder beschouwen.

7) Analyse van deelverzameling D 142 .

8) Analyse van deelverzameling D 143 .

9) Analyse van deelverzameling D 145 .

10) Het screenen van weinig belovende subgroepen

Deelverzameling D 143 is weinig belovend. Omdat , maar dan zullen we de deelverzameling D 145 verder beschouwen.

11) Analyse van deelverzameling D 1452 .

12) Analyse van deelverzameling D 1453 .

Optimale oplossing: .

Dus de route van de student: 12e gebouw - Administratie - 5e gebouw - Witte Huis - KRK Premier - 12e gebouw.

Referenties

1. Abramov L.A., Kapustin V.F. Wiskundig programmeren. - L.: Uitgeverij Leningrad State University, 1981. -328 p.

2. Alekseev O.G. Geïntegreerde toepassing van discrete optimalisatiemethoden. - M.: Nauka, 1987. -294 p.

3. Korbut AA, Finkelgein Yu.Yu. Discrete programmering. M.: Wetenschap. 1969. -240 sec

4. Kuznetsov Yu.N. en anderen. Wiskundig programmeren: leerboek. - 2e druk, herzien en aangevuld. - M.: Hogere School, 1980. -300 p.

5. Papadimitriou H., Steiglitz K. Combinatorische optimalisatie. Algoritmen en complexiteit. - M.: Mir, 1985. -213 p.

Soortgelijke documenten

Methoden voor het oplossen van problemen uit de hogere wiskunde met behulp van de grafentheorie, de essentie ervan en de oplossingsprocedure. Het hoofdidee van de branch and bound-methode, de praktische toepassing ervan op het probleem. Het verdelen van een reeks routes in subsets en de grafische weergave ervan.

taak, toegevoegd op 24-07-2009

Essentie en inhoud, basisconcepten en criteria van de grafentheorie. Concept en algemeen begrip van het handelsreizigersprobleem. Beschrijving van de branch and bound-methode, praktische toepassing. Een voorbeeld van het gebruik van deze filiaalmethode om het handelsreizigersprobleem op te lossen.

test, toegevoegd op 06/07/2011

Methoden voor het oplossen van het handelsreizigersprobleem. Wiskundig model van het handelsreizigersprobleem. Little's algoritme voor het vinden van de minimale Hamiltoniaanse contour voor een grafiek met n hoekpunten. Het probleem van de handelsreiziger oplossen met behulp van het Kruskal-algoritme en het 'houten'-algoritme.

cursuswerk, toegevoegd op 30-04-2011

De essentie van het handelsreizigersprobleem, de toepassing ervan. Algemene kenmerken van methoden om dit op te lossen: uitputtende zoekmethode, "hebzuchtige" methoden, genetische algoritmen en hun generalisaties. Kenmerken van de branch and bound-methode en bepaling van de meest optimale oplossing voor het probleem.

cursuswerk, toegevoegd op 18-06-2011

Wiskundig model van het probleem. Het transportprobleem oplossen met behulp van de potentiële methode. Objectieve functiewaarde. Een systeem bestaande uit 7 vergelijkingen met 8 onbekenden. Grafisch problemen oplossen. Het selecteren van het halve vlak dat overeenkomt met de ongelijkheid.

test, toegevoegd op 06/12/2011

Dynamische programmeertheorie. Het concept van een optimale onderbouw. Een onafhankelijke en volledig afhankelijke reeks hoekpunten. Het probleem van het vinden van de maximale onafhankelijke verzameling in een boom. Het Bron-Kerbosch-algoritme als een takgebonden methode voor het vinden van kliekjes.

samenvatting, toegevoegd 10/09/2012

Een duaal probleem oplossen met behulp van de eerste fundamentele stelling van de dualiteitstheorie, grafische en simplexmethoden. Wiskundig model van het transportprobleem, berekening van het referentietransportplan volgens de methoden van de noordwestelijke hoek en het minimumelement.

test, toegevoegd op 27-11-2011

Verklaring van het handelsreizigersprobleem en basisoplossingsalgoritmen. Routes en paden. Transportnetwerkconcepten. Het concept van een toenemende boog, ketting, snede. Floyd-Warshell-algoritme. Het probleem oplossen met behulp van de analytische methode. Een applicatie maken om een probleem op te lossen.

cursuswerk, toegevoegd 10/08/2015

Oplossing van het eerste probleem, de vergelijkingen van Poisson, de functie van Green. Randwaardeproblemen voor de Laplace-vergelijking. Verklaring van grenswaardeproblemen. Green's functies voor het Dirichlet-probleem: driedimensionale en tweedimensionale gevallen. Oplossing van het Neumann-probleem met behulp van de Green's-functie, implementatie op een computer.

cursuswerk, toegevoegd op 25-11-2011

Volgorde van het oplossen van een lineair grenswaardeprobleem. Kenmerken van de sweep-methode. Algoritme voor de eindige differentiemethode: een mesh construeren in een bepaald gebied, ter vervanging van de differentiaaloperator. SLAE's oplossen met behulp van de Gaussische methode, eindige differentievergelijkingen.

Hallo, Habr! Terwijl ik verschillende algoritmen implementeerde voor het vinden van de goedkoopste Hamiltoniaanse cyclus, kwam ik een publicatie tegen die mijn eigen versie aanbood. Na het uitproberen kreeg ik het verkeerde antwoord:

Verdere zoekopdrachten op internet leverden niet het verwachte resultaat op: een theoretische beschrijving die moeilijk was voor niet-wiskundigen, of begrijpelijk, maar met fouten.

Onder de snede vindt u een gecorrigeerd algoritme en een online calculator.

De methode zelf, gepubliceerd door Little, Murthy, Sweeney, Carel in 1963, is toepasbaar op veel NP-volledige problemen, en is een zeer theoretisch materiaal dat, zonder goede kennis van Engels en wiskunde, niet onmiddellijk kan worden toegepast op ons handelsreizigerprobleem. .

Kort over de methode - het is een volledige zoektocht naar alle mogelijke opties met de eliminatie van duidelijk niet-optimale oplossingen.

Gecorrigeerd algoritme voor het vinden van een werkelijk minimale route

Het algoritme bestaat uit twee fasen:

Eerste fase

Het verlagen van de kostenmatrix en het berekenen van de lagere schatting van de routekosten r.

1. Bereken het kleinste element in elke rij (gegoten constante voor de rij)
2. We gaan verder met een nieuwe kostenmatrix, waarbij we van elke rij de reductieconstante aftrekken
3. Bereken het kleinste element in elke kolom (dwangconstante voor de kolom)
4. We gaan verder met een nieuwe kostenmatrix, waarbij we van elke kolom de reductieconstante aftrekken.
Als gevolg hiervan hebben we een kostenmatrix waarin elke rij en elke kolom minimaal één nulelement bevat.
5. We berekenen de grens in dit stadium als de som van de reductieconstanten voor kolommen en rijen (deze grens zal de kosten zijn waaronder het onmogelijk is om de vereiste route te construeren)

Tweede (hoofd)podium

1. Berekening van de boete voor niet-gebruik voor elk nulelement van de gegeven kostenmatrix.
De boete voor het niet gebruiken van een element met index (h,k) in de matrix betekent dat deze rand niet is opgenomen in onze route, wat betekent dat de minimale kosten voor het “niet gebruiken” van deze rand gelijk zijn aan de som van de minimale elementen in rij h en kolom k.

A) We zoeken naar alle nulelementen in de gegeven matrix
b) Voor elk ervan berekenen we de boete voor niet-gebruik.
c) Selecteer het element dat overeenkomt met de maximale straf (elke, als er meerdere zijn)

2. Nu verdelen we onze set S in sets - sets die de voorsprong met de maximale straf bevatten (S w) en sets die deze voorsprong niet bevatten (S w/o).
3. Berekening van kostenramingen voor routes die in elk van deze sets zijn opgenomen.
a) Voor de verzameling S zonder is alles eenvoudig: aangezien we niet de overeenkomstige voorsprong met de maximale straf (h,k) nemen, is de kostenraming daarvoor gelijk aan de kostenraming van de verzameling S + de straf voor het niet gebruiken van de rand (h,k)
b) Bij het berekenen van de kosten voor de verzameling S w houden we er rekening mee dat aangezien de rand (h,k) in de route is opgenomen, dit betekent dat de rand (k,h) niet in de route kan worden opgenomen. in de kostenmatrix schrijven we c(k,h) =oneindig, en aangezien we “al vertrokken” zijn vanaf punt h, en we “al zijn aangekomen” vanaf punt k, verlaat geen enkele rand h en komt er geen enkele rand aan bij k kan niet meer worden gebruikt, dus schrappen we uit de kostenmatrix rij h en kolom k. Hierna reduceren we de matrix, en dan is de kostenraming voor S w gelijk aan de som van de kostenraming voor S en r(h,k), waarbij r(h,k) de som is van de reductieconstanten voor de gewijzigde kostenmatrix.
4. Van iedereen van niet-gepartitioneerde sets wordt degene met de laagste score geselecteerd.

Zo gaan we door totdat er nog één niet-doorgestreepte rij en één niet-doorgestreepte kolom over is in de kostenmatrix.

Kleine optimalisatie - toevoeging van heuristieken

Ja, echt waar, waarom introduceren we geen heuristieken? In het branch and bound-algoritme bouwen we feitelijk een boom, op de knooppunten waarvan we besluiten de rand (h,k) te nemen of niet, en twee kinderen op te hangen - Sw(h,k) en Sw/o( h,k). Maar we selecteren de beste optie voor de volgende iteratie alleen op basis van evaluatie. Laten we dus de beste kiezen, niet alleen qua beoordeling, maar ook qua diepte in de boom, want... Hoe dieper het geselecteerde element, hoe dichter het einde van de telling is. Zo kunnen we eindelijk wachten op een antwoord.

Nu eigenlijk over de fouten in die publicatie

Er was slechts één fout: je zou ervoor moeten kiezen om de set te partitioneren met de minimale grens van alle mogelijke paden, en niet van de twee kinderen die je hebt verkregen als resultaat van de laatste partitie.

Bewijs

Laten we terugkeren naar de afbeelding aan het begin van het bericht:

En hier is de oplossing met het gecorrigeerde algoritme:

Antwoord: pad:3=>4=>2=>1=>5=>3 lengte: 41
Zoals u kunt zien, zou het een vergissing zijn om de 5:2-rand in de oplossing op te nemen. QED

Grafiek waarin de branch- en bound-methode en de bestede tijd voor een willekeurige tabel van 5x5 tot 10x10 worden vergeleken:

Grafiek van de maximale en minimale tijd die is besteed aan matrices van 5x5 tot 66x66.

U kunt het proberen met een gedetailleerde oplossing

Door op de knop "Archief downloaden" te klikken, downloadt u het door u benodigde bestand geheel gratis.
Voordat u dit bestand downloadt, moet u nadenken over de goede samenvattingen, tests, scripties, proefschriften, artikelen en andere documenten die nog niet zijn geclaimd op uw computer. Dit is jouw werk, het moet bijdragen aan de ontwikkeling van de samenleving en mensen ten goede komen. Zoek deze werken en verzend ze naar de kennisbank.
Wij en alle studenten, promovendi en jonge wetenschappers die de kennisbasis gebruiken in hun studie en werk zullen je zeer dankbaar zijn.

Om een archief met een document te downloaden, voert u in het onderstaande veld een vijfcijferig nummer in en klikt u op de knop "Archief downloaden"

Soortgelijke documenten

Kenmerken van de branch and bound-methode als een van de gebruikelijke methoden voor het oplossen van integer-problemen. Ontleding van een lineair programmeerprobleem in het branch-and-bound algoritme. Grafische, simplex-methode voor het oplossen van lineaire programmeerproblemen.

cursuswerk, toegevoegd op 03/05/2012

Verklaring van het handelsreizigersprobleem. Het vinden van de optimale oplossing met behulp van de branch and bound-methode. Het basisprincipe van deze methode, de volgorde van toepassing. Gebruik van de bovengrensmethode in de procedure voor het samenstellen van een boom met mogelijke opties.

cursuswerk, toegevoegd 10/01/2009

De essentie en beschrijving van de simplexmethode en de verbeterde simplexmethode (inverse matrixmethode), de voor- en nadelen van hun gebruik bij lineair programmeren. Lijst en blokdiagram van een programma in Turbo Pascal voor het oplossen van een wiskundig probleem.

cursuswerk, toegevoegd op 30-03-2009

Organisatievorm van de belangrijkste productie met variabele stroom. Kenmerken van de gereedschapswisselaar als dynamisch programmeerprobleem. Algemene kenmerken van het algoritme voor het vormen van de branch and bound-methode. De essentie van het concept is combinatorische configuratie.

cursuswerk, toegevoegd op 20-12-2008

Verklaring van een lineair geheel getalprobleem. Snijvlakmethode. Fractionele algoritme voor het oplossen van volledig gehele problemen. Effectiviteit van Gomori-snijden. Vergelijking van de rekenmogelijkheden van de snijvlakmethode en de branch and bound-methode.

cursuswerk, toegevoegd op 25-11-2011

Formulering en oplossing van discrete optimalisatieproblemen met behulp van de discrete programmeermethode en de branch and bound-methode, waarbij gebruik wordt gemaakt van het voorbeeld van het klassieke handelsreizigerprobleem. Stadia van het construeren van een branch-and-bound-algoritme en de effectiviteit ervan, het construeren van een grafenboom.

cursuswerk, toegevoegd 11/08/2009

Overzicht van problemen opgelost door de dynamische programmeermethode. Een route van optimale lengte uitstippelen. Een keten van matrices vermenigvuldigen. "Trappen" probleem. Analyse van de noodzaak om speciale methoden voor probabilistisch dynamisch programmeren te gebruiken.

cursuswerk, toegevoegd op 28-06-2015