De ontwikkeling van deze 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). Lagere problemen worden op zo'n manier door hogere problemen gegenereerd dat hun toelaatbare sets (AS) onsamenhangende subsets zijn van de EA 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.

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: OVER terminaltaak van het filiaal het is duidelijk dat als je bijv. 22 zal slechter zijn dan het record of D terminaltaak van het filiaal 22 =, de rechter tak breekt af (ze zeggen ook dat deze wordt gesondeerd). Als de beoordeling is de waarde van het criterium, die zeker niet slechter is dan het optimale, en, 22 zal beter zijn 22 zal slechter zijn dan het record of er vindt vertakking plaats: veel 22 is verdeeld in 2 subsets. De oplossing is voltooid wanneer alle vestigingen zijn voltooid

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 verdelen;

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 set aan relaties (7.9). In dit geval worden gehele sets, zowel origineel als gegenereerd, 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.

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: staalproblemen hebben geen haalbare oplossingen, dat wil zeggen dat de lijst met problemen uitgeput is en daarom stellen we dat we een optimale oplossing voor het oorspronkelijke probleem hebben verkregen, gelijk aan de oplossing voor het continue probleem 8.

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.

Laten we nu een paar 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 is de definitie van de schatting bijvoorbeeld sterk vereenvoudigd (het is niet nodig 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 wordt gedwongen 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.

Tak- en gebonden methode

De branch and bound-methode is ontwikkeld door Lytle, Murthy, Sweeney en Karel. Laten we de belangrijkste ideeën van deze methode eens bekijken. Allereerst wordt deze methode geassocieerd met een algemeen schema voor het aannemen en evalueren van alternatieven. Het schema voor het construeren van alternatieve aannames in het algemeen kan worden gepresenteerd zoals weergegeven in figuur 2. 3.9.

De hoekpunten in Fig. 3.9 komen, zoals voorheen, overeen met de toestand van het probleem. Uit elk hoekpunt komen slechts twee alternatieve richtingen naar voren, wat de algemeenheid van de overweging echter niet beperkt. Routebeschrijvingen zijn gemarkeerd met letters P met indexen. Identificatie R(b ik) er is een numerieke score toegewezen aan het hoekpunt b ik.

Over het algemeen is er geen grens aan de diepte van een boom, alhoewel duidelijk is dat er naar een minimale diepte moet worden gestreefd. Dit rechtvaardigt met name de keuze voor een of andere veronderstelling Pm: In de eerste plaats moet men ernaar streven een aanname te bewijzen waarvan de betrouwbaarheid het meest twijfelachtig is, of, omgekeerd, proberen een aanname te weerleggen waarvan de betrouwbaarheid het meest plausibel is, d.w.z. door te handelen volgens het principe van reductio ad absurdum, aangezien de kans op het verkrijgen van een tegenspraak hier het grootst is, kunt u het overeenkomstige alternatief bij zijn “bronnen” afsnijden, in plaats van nieuwe alternatieve aannames te bouwen.

Laat de staat gezocht worden B*, waarin R(b *) minimaal. Laten we verder aannemen dat er een huidige oplossing bekend is bx met het huidige record R(bx). Dan is het duidelijk dat elke staat b ik, waarin de best haalbare waarde R(b ik) ³ R(b x), kan worden verwijderd (het relevante deel van de zoekboom is gemarkeerd zoals weergegeven door het gearceerde gebied in Figuur 3.9).

Laten we het handelsreizigersprobleem in de volgende specifieke formulering bekijken. Laat er een set gegeven worden N van 4 steden verbonden door wegen. Wij zullen interpreteren N een netwerk waarin de hoekpunten overeenkomen met steden, en aan de bogen die de hoekpunten verbinden een gewicht wordt toegewezen met ij, rekening houdend met de kosten van de overstap van een handelsreiziger uit de stad i naar de stad J(Afb. 3.10a).

Wij geloven met ij ³ 0 En met ii = ¥, en dat is niet nodig met ij = met ji. We zullen het probleem coderen met de kostenmatrix C = [с ij ], weergegeven in Fig. 3.10, b.

In het handelsreizigersprobleem moet je een cyclus vinden met de minimale som van de kosten van de bogen waaruit deze bestaat, die niet vaker dan één keer rond elk hoekpunt gaat, met uitzondering van één hoekpunt van waaruit de cyclus “begint” en op waar het ‘eindigt’.

Laten we overwegen dit probleem op te lossen met behulp van de branch and bound-methode. De volgende twee omstandigheden zijn doorslaggevend.

A1) De oplossing voor het handelsreizigersprobleem komt overeen met de keuze van precies één element in elke rij van de kostenmatrix MET en precies één element in elke kolom van deze matrix, en de som van de geselecteerde elementen is minimaal en ze vormen een cyclus. De laatste opmerking is belangrijk. De elementen (1, 2), (2, 3), (3, 1), (4, 4) vormen bijvoorbeeld geen cyclus.

A2) Als u dezelfde constante van een willekeurige rij (kolom) aftrekt (optelt) 22 zal slechter zijn dan het record of en vervolgens de resulterende waarde MET* totale kosten in de optimale cyclus C* zal precies met dit bedrag afnemen (verhogen). 22 zal slechter zijn dan het record of.

Laten we eigenschap A2 gebruiken. Laten we de minimale elementen opschrijven h j in elke kolom J, waarna we ze aftrekken van de elementen van de overeenkomstige kolommen. Vervolgens schrijven we in de resulterende matrix de minimale elementen op Hoi in lijnen i. We verkrijgen de matrix getoond in Fig. 2.11, een. Trek de overeenkomstige waarde van elke regel af Hoi(Afb. 3.11, b).

Uit de matrix in afb. 3.11, b Het is gemakkelijk vast te stellen dat dit de minimaal mogelijke waarde is MET*(wat wij aangeven) wordt als volgt berekend

Nu zullen we aannames doen voor de gegeven kostenmatrix in figuur 2. 3.11, b.

Laten we aannemen dat de boog erbij hoort C*; de alternatieve aanname betekent dat . Als de boog is, dan gaan we ervan uit dat voor de boog 4,3 = ¥ is, en verwijderen we deze ook uit de kostenmatrix in Fig. 2.11, b rij 3 en kolom 4, wat uiteindelijk de matrix oplevert zoals weergegeven in Fig. 2.12, een. De gegeven matrix wordt getoond in figuur 2.12, b.

Voor de matrix in afb. 2.12, b vinden we . We vinden dus dat de lengte van de optimale cyclus die de boog bevat, is

Tegelijkertijd is de lengte van de cyclus 5+2+3+2=12, daarom concluderen we dat de boog niet is opgenomen in de optimale cyclus. Wij geloven met 3,4 = ¥. Laten we nu aannemen dat de boog . Nadat we soortgelijke berekeningen hebben uitgevoerd, stellen we vast dat de minimale totale kosten voor een cyclus met een boog 13 eenheden bedragen. Deze veronderstelling wordt derhalve eveneens verworpen, omdat het verbetert het huidige record niet. Wij geloven met 1,4 = ¥. Als gevolg hiervan wordt in kolom 4 van de matrix in Fig. 3.10, b Er blijft slechts één geldig element over met 2,4 = 2. Wij geloven. Deze aanname stelt ons in staat rij 2 en kolom 4 te verwijderen. Als resultaat verkrijgen we de gereduceerde matrix zoals weergegeven in figuur 1. 3.13, waarvoor C* gelijk aan 12. Laten we aannemen dat de boog dan automatisch volgt dat de boog . Laten we rij 4 en kolom 3 verwijderen: we krijgen de gereduceerde matrix getoond in Fig. 3.14, waaruit automatisch volgt dat de boog . Dus uitgaande van de initiële aanname dat de boog , stellen we de volgende optimale cyclus vast die de boog niet bevat: met totale kosten gelijk aan 2 + 3 + 2 + 5 = 12.

Invoering

Bij het overwegen van een aantal problemen is het noodzakelijk rekening te houden met de eis dat de gebruikte variabelen geheeltallig moeten zijn. Methoden voor het oplossen van lineaire programmeerproblemen garanderen niet de integriteit van de oplossing.

Soms worden lineaire programmeerproblemen met gehele getallen bij benadering opgelost. Om dit te doen, lost u het probleem op zonder rekening te houden met de gehele waarden van de variabelen, waarna in de resulterende optimale oplossing de resultaten worden afgerond op de dichtstbijzijnde gehele waarden. Het gebruik van dergelijke oplossingen is toegestaan ​​in situaties waarin de waarden van de variabelen groot genoeg zijn en de afrondingsfout kan worden verwaarloosd. Als de waarden van de variabelen klein zijn, kan afronding leiden tot een aanzienlijke discrepantie met de optimale oplossing.

Een van de meest gebruikte methoden voor het oplossen van gehele getallenproblemen is de branch and bound-methode, voor het eerst voorgesteld door Land en Doig in 1960.

lineaire programmering van vertakkingsgrenzen

Tak- en gebonden methode

Het branch-and-bound-algoritme omvat het ontleden van het oorspronkelijke lineaire programmeerprobleem (LPP) in een reeks problemen die aanvullende beperkingen op variabelen bevatten, die vervolgens worden geoptimaliseerd.

1. Het proces begint met het oplossen van het probleem met behulp van een simplex of grafische methode, zonder rekening te houden met de vereiste voor de integriteit van variabelen. Dit probleem wordt ZLP-0 genoemd. Als alle variabelen van het optimale plan gehele getallen zijn, dan is dit plan ook optimaal voor de problemen integer programmeren.

2. Als een variabele geen geheel getalwaarde heeft ontvangen, wordt er een vertakking gemaakt in twee nieuwe taken ZLP-1, ZLP-2. Een van de ZLP-1-problemen is het ZLP-0-probleem, aangevuld met de beperking waar het gehele deel van het getal ligt. De tweede wordt gevormd door een beperking toe te voegen aan het ZLP-0-probleem. Opgemerkt moet worden dat de keuze van een integer-variabele als volgt willekeurig kan worden bepaald:

stijgende of dalende indexen;

de variabele vertegenwoordigt een belangrijke beslissing die is genomen binnen het kader van een bepaald probleem;

coëfficiënt in objectieve functie waarbij deze variabele aanzienlijk groter is dan alle andere.

3. De taken van ZLP-1 en ZLP-2 worden onafhankelijk opgelost. Een vertakking eindigt als het gebied met haalbare oplossingen leeg is of als de optimale oplossing volledig geheel is. Anders is het nodig om af te wijken van punt 2, waarbij de volgende aantallen ZLP-taken worden aangewezen in de natuurlijke volgorde van ZLP-3, ZLP-4.

Het oplossingsproces kan worden weergegeven als een boom waarin het hoekpunt ZLP-0 overeenkomt met het oorspronkelijke plan voor het oplossen van het probleem, en elk van de hoekpunten die ermee zijn verbonden door een vertakking, overeenkomt met het optimale plan voor het volgende probleem.

Beschouw het volgende voorbeeld. Maximaliseer de objectieve functie

onder beperkingen

Laten we de grafische methode gebruiken om het lineaire programmeerprobleem op te lossen.

1. Laten we het oorspronkelijke probleem oplossen zonder rekening te houden met de vereiste van gehele variabelen.

Laten we dit lineaire programmeerprobleem aanduiden als ZLP-0.

In figuur 1.1 wordt de polygoon met oplossingen voor dit probleem gearceerd weergegeven. De maximale waarde wordt bereikt op het punt. De oplossing is geen geheel getal.

De volgende stap van de branch and bound-methode is het vertakken langs een van de integer-variabelen die een fractionele waarde hebben, b.v. Om dit te doen, voegen we twee nieuwe beperkingen toe aan het ZLP-0-probleem en deze beperkingen verwijderen het interval = waarin er geen gehele waarden zijn. Tijdens het vertakkingsproces worden dus twee nieuwe taken ZLP-1 en ZLP-2 gecreëerd.

Figuur 1.1 Oplossing van het ZLP-0-probleem

2. Laten we probleem ZLP-1 grafisch oplossen.

Figuur 1.2 toont het haalbare domein van het ZLP-1-probleem. De maximale waarde wordt op het punt bereikt. De oplossing voor het probleem is niet-geheel getal.

Figuur 1.2 Oplossing van het ZLP-1-probleem

3. Laten we het ZLP-2-probleem grafisch oplossen.

In dit geval is de reeks haalbare oplossingen leeg (Figuur 1.2). Het systeem van beperkingen is inconsistent en het ZLP-2-probleem kan van verdere overweging worden uitgesloten.

Figuur 1.3 Oplossing van het ZLP-2-probleem

Laten we nu doorgaan met onze studie van het ZLP-1-probleem, aangezien de waarde niet geheel getal is. Laten we nog een vertakking maken door beperkingen in te voeren en. Als resultaat krijgen we twee nieuwe problemen ZLP-3 en ZLP-4.

Veel onderzoekers kwamen op het idee van de branch-and-bound-methode, maar Little en zijn co-auteurs ontwikkelden op basis van deze methode een succesvol algoritme voor het oplossen van probleemproblemen en droegen daarmee bij aan de popularisering van de aanpak. Sindsdien is de branch-and-bound-methode met succes toegepast op veel problemen, en zijn er verschillende andere wijzigingen van de methode bedacht om het probleem op te lossen, maar de meeste leerboeken concentreren zich op Little's baanbrekende werk.

Het algemene idee is triviaal: je moet het enorme aantal opties dat je uitprobeert in klassen verdelen en schattingen krijgen (van onderaf - in het minimalisatieprobleem, van bovenaf - in het maximalisatieprobleem) voor deze klassen om te kunnen Gooi opties niet één voor één weg, maar in hele klassen. De moeilijkheid is om een ​​zodanige indeling in klassen (branches) en zodanige schattingen (grenzen) te vinden dat de procedure effectief is.

Tabel 2

Tabel 3

Tabel 4

Laten we het algoritme van Little presenteren met behulp van voorbeeld 1 uit de vorige sectie. Laten we de matrix herschrijven:

Het zal voor ons handiger zijn om C ij te interpreteren als de reiskosten van stad i naar stad j. Laten we aannemen dat de goede burgemeester van stad j een decreet heeft uitgevaardigd om elke handelsreiziger die de stad binnenkomt $ 5 te betalen. Dit betekent dat elke tour $ 5 goedkoper wordt, omdat voor elke tour stad j moet worden bezocht. Maar omdat alle tours gelijkmatig in prijs zijn gedaald, zal de vorige minimumtour nu het minst kosten. De goede daad van de burgemeester kan worden weergegeven als een afname van alle getallen in de j-de kolom van matrix C met 5. Als de burgemeester handelsreizigers uit de j-de stad wil wegsturen en een beloning wil instellen voor het vertrek in de j-de stad, bedrag van 10 dollar, dit zou kunnen worden uitgedrukt door 10 af te trekken van alle elementen jde van die lijn. Dit zou opnieuw de kosten van elke tour veranderen, maar de minimumtour zou minimaal blijven. Het volgende lemma is dus bewezen.

Door een constante af te trekken van alle elementen van een rij of kolom van matrix C, laten we de minimale tour als minimum.

Voor het algoritme zal het handig zijn om meer nullen in de matrix C te krijgen, zonder daar echter negatieve getallen te krijgen. Om dit te doen, trekken we van elke rij het minimumelement af (dit wordt rijreductie genoemd, zie tabel 3), en trekken vervolgens van elke kolom van de rijgewijze matrix het minimumelement af, waardoor een kolomgewijze reductiematrix ontstaat, zie tabel . 4).

Diagonale streepjes betekenen dat je niet van stad i naar stad i kunt lopen. Merk op dat de som van de reductieconstanten in rijen 27 is, de som in kolommen 7 en de som van de sommen 34.

De tour kan worden gedefinieerd door een systeem van zes onderstreepte (gemarkeerd in een andere kleur) elementen van bijvoorbeeld matrix C, zoals weergegeven in de tabel. 2. Een element onderstrepen betekent dat ze in de ronde van het i-de element naar het j-de element gaan. Voor een zesstedentocht moeten er zes onderstreepte elementen zijn, aangezien er bij een zesstedentocht zes randen zijn. Elke kolom moet precies één onderstreept element bevatten (de handelsreiziger is elke stad één keer binnengegaan), elke rij moet precies één onderstreept element bevatten (de handelsreiziger heeft elke stad één keer verlaten); bovendien moeten de onderstreepte elementen één enkele ronde beschrijven in plaats van meerdere kleinere cycli. De som van de getallen van de onderstreepte elementen zijn de kosten van de rondleiding. Op tafel 2 de kosten bedragen 36, dit is de minimale ronde die wordt verkregen door lexicografisch zoeken.

Nu gaan we redeneren vanuit de gegeven matrix in de tabel. 2. Als het mogelijk is om een ​​correct systeem van onderstreepte elementen te construeren, d.w.z. systeem dat voldoet aan de drie hierboven beschreven vereisten, en deze onderstreepte elementen alleen maar nullen zullen zijn, dan is het duidelijk dat we voor deze matrix een minimale rondleiding zullen krijgen. Maar het zal ook minimaal zijn voor de oorspronkelijke matrix C, alleen om de juiste kosten van de tour te krijgen, moet je alle reductieconstanten weer optellen, en de kosten van de tour zullen veranderen van 0 in 34. Dus, de minimale tour mag niet minder zijn dan 34. We kregen voor alle rondes een lagere beoordeling.

Laten we nu beginnen met vertakken. Om dit te doen, zullen we de stap van het schatten van nullen uitvoeren. Beschouw de nul in cel (1,2) van de gereduceerde matrix. Het betekent dat de kosten voor het verhuizen van stad 1 naar stad 2 nul zijn. Wat als we niet van stad 1 naar stad 2 gaan? Dan dient u nog stad 2 in te vullen voor de prijzen aangegeven in de tweede kolom; goedkoper voor slechts 1 (vanaf stad 6). Vervolgens dient u nog steeds stad 1 te verlaten voor de prijs aangegeven in de eerste regel; de goedkoopste optie is om voor 0 naar stad 3 te gaan. Als we deze twee minima samenvatten, hebben we 1+0=1: als je niet “nul” gaat van stad 1 naar stad 2, dan moet je minimaal 1 betalen Dit is de schatting van nul. De schattingen van alle nullen staan ​​in de tabel. 5 naar rechts en boven nul (nulscores gelijk aan nul werden niet gegeven).

Laten we het maximum van deze schattingen kiezen (in het voorbeeld zijn er verschillende schattingen die gelijk zijn aan één, laten we de eerste kiezen, in cel (1,2)).

De nulflank (1,2) wordt dus geselecteerd. Laten we alle tours in twee klassen verdelen: degenen die de rand bevatten (1,2) en degenen die de rand niet bevatten (1,2). Voor de tweede klasse kunnen we zeggen dat je er 1 meer moet betalen, dus rondleidingen in deze klasse kosten 35 of meer.

Wat de eerste klasse betreft, moeten we rekening houden met de matrix in de tabel. 6 met de eerste regel en de tweede kolom doorgestreept.

Tabel 5

Tabel 7

Bovendien is er in de gereduceerde matrix een verbod in cel (2,1), omdat rand (1,2) is geselecteerd en het is onmogelijk om de tocht voortijdig af te sluiten met rand (2,1). De gereduceerde matrix kan in de eerste kolom met 1 worden verminderd, zodat elke ronde die ermee overeenkomt minstens 35 euro kost. Het resultaat van onze vertakkingen en het verkrijgen van schattingen wordt getoond in figuur 1. 6.

De cirkels vertegenwoordigen klassen: de bovenste cirkel is de klasse van alle ronden; linksonder - klasse van alle tochten inclusief rand (1,2); rechtsonder - de klasse van alle tours die geen edge bevatten (1,2). De cijfers boven de cirkels zijn schattingen van onderaf.

Laten we doorgaan met vertakken in de positieve richting: links - beneden. Om dit te doen schatten we de nulpunten in de gereduceerde matrix C in de tabel. 7. De maximale score in cel (3,1) is 3. De score voor het hoekpunt rechtsonder in Fig. 7 is 35+3=38. Om het hoekpunt linksonder in Fig. 7, moet u nog een rij 3 en kolom 1 uit matrix C verwijderen, waardoor de matrix C[(1,2), (3,1)] in de tabel wordt verkregen. 8. In deze matrix moet je een verbod in cel (2,3) plaatsen, omdat er al een fragment van de tour is opgebouwd uit randen (1,2) en (3,1), d.w.z. en voortijdige sluiting moet worden verboden (2.3). Deze matrix wordt kolom per 1 gegeven (Tabel 9), dus elke tour van de overeenkomstige klasse (d.w.z. een tour met randen (1,2) en (3,1)) kost 36 of meer.

Tabel 9

Tabel 11

Nu evalueren we de nullen in de gegeven matrix C[(1,2), (3,1)] de nul met een maximale score van 3 staat in cel (6,5). De negatieve optie heeft een score van 38+3=41. Om een ​​beoordeling van de positieve optie te krijgen, verwijdert u regel 6 en kolom 5 en plaatst u een verbod in cel (5,6), zie tabel. 10. Deze matrix is ​​irreduceerbaar. De score van de positieve optie stijgt dus niet (Fig. 8).

Evaluatie van de nullen in de matrix in de tabel. 10, we krijgen vertakkingen op basis van de keuze van rand (2,6), de negatieve optie krijgt een score van 36+3=39, en om een ​​score te krijgen voor de positieve optie, schrappen we de tweede rij en de zesde kolom, de matrix in de tabel krijgen. 11.

Aan de matrix in cel (5.3) moet een verbod worden toegevoegd, omdat er al een fragment van de rondreis is opgebouwd en voortijdige terugkeer verboden moet worden (5.3). Nu we nog een 2x2-matrix over hebben met diagonale beperkingen, voltooien we de tour met randen (4,3) en (5,4). Het was niet voor niets dat we naar positieve opties zijn gegaan. Nu hebben we een rondleiding ontvangen: 1>2>6>5>4>3>1 met een kostprijs van 36. Toen we onderaan de zoekboom kwamen, werd de klasse van rondleidingen teruggebracht tot één rondleiding, en de schatting van hieronder omgezet in de exacte kosten.

Dus alle klassen met een score van 36 en hoger, beste rondleiding bevatten niet. Daarom zijn de overeenkomstige hoekpunten doorgestreept. Hoekpunten waarvan beide afstammelingen worden verwijderd, worden ook verwijderd. We hebben de totale zoekopdracht enorm verminderd. Het blijft de vraag of de klasse die overeenkomt met de matrix C geen betere tour bevat, d.w.z. gegeven matrix C met een verbod in cel 1,2, verminderd met 1 in kolom (wat de score 34+1=35 opleverde). De evaluatie van nullen geeft 3 voor de nul in de cel (1,3), dus de evaluatie van de negatieve optie 35+3 overschrijdt de waarde van de reeds ontvangen ronde 36 en de negatieve optie wordt afgesneden.

Om een ​​schatting te krijgen van de positieve optie sluiten we de eerste rij en de derde kolom uit de matrix, stellen we een verbod in (3.1) en verkrijgen we een matrix. Deze matrix wordt in de vierde rij gegeven door 1, de klassescore bereikt 36 en de cirkel is doorgestreept. Omdat beide kinderen van het hoekpunt “iedereen” worden gedood, wordt deze ook gedood. Er zijn geen hoekpunten meer, de zoektocht is voorbij. We ontvingen dezelfde minimale rondleiding, die in de tabel onderstreept is weergegeven. 2.

Er zijn geen bevredigende theoretische schattingen van de prestaties van het Little-algoritme en aanverwante algoritmen, maar de praktijk leert dat moderne computers ze stellen je vaak in staat probleemproblemen op te lossen met n = 100. Dit is een enorme verbetering vergeleken met uitputtend zoeken. Bovendien zijn algoritmen zoals branch en bound effectieve heuristische procedures als ze niet kunnen worden voltooid.

Laten we het discrete programmeerprobleem in algemene vorm bekijken:

Vind -vector van onbekenden, D- eindig

veel aanvaardbare waarden van deze vector is F(x) 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 bij de volgende stap alle of slechts enkele subsets 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 dit vereisen groot aantal operaties kan de effectiviteit van de methode laag zijn.

Schema dynamische programmering 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 van 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 ondergrens de huidige waarde van het record overschrijdt, worden de overeenkomstige status 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.