We zullen het probleem oplossen met behulp van een rekenmachine. Laten we als willekeurige route nemen:
X 0 = (1,2);(2,3);(3,4);(4,5);(5,1)
Dan F(X 0) = 90 + 40 + 60 + 50 + 20 = 260
Om de ondergrens van de set te bepalen, gebruiken we reductie operatie of het rij voor rij verkleinen van de matrix, waarvoor het nodig is om het minimumelement in elke rij van matrix D te vinden.
d ik = min(j) d ij

ik j	1	2	3	4	5	d ik
1	M	90	80	40	100	40
2	60	M	40	50	70	40
3	50	30	M	60	20	20
4	10	70	20	M	50	10
5	20	40	50	20	M	20

Vervolgens trekken we di af van de elementen van de betreffende rij. In dit opzicht zal er in de nieuw verkregen matrix ten minste één nul in elke rij staan.

ik j	1	2	3	4	5
1	M	50	40	0	60
2	20	M	0	10	30
3	30	10	M	40	0
4	0	60	10	M	40
5	0	20	30	0	M

We voeren dezelfde reductiebewerking uit langs de kolommen, waarvoor we in elke kolom het minimumelement vinden:
d j = min(i) d ij

ik j	1	2	3	4	5
1	M	50	40	0	60
2	20	M	0	10	30
3	30	10	M	40	0
4	0	60	10	M	40
5	0	20	30	0	M
dj	0	10	0	0	0

Na aftrekken minimale elementen we verkrijgen een volledig gereduceerde matrix, waarin de grootheden d i en d j worden genoemd constanten gieten.

ik j	1	2	3	4	5
1	M	40	40	0	60
2	20	M	0	10	30
3	30	0	M	40	0
4	0	50	10	M	40
5	0	10	30	0	M

De som van de reductieconstanten bepaalt de ondergrens van H:
H = ∑d ik + ∑d j
H = 40+40+20+10+20+0+10+0+0+0 = 140
De elementen van de matrix dij komen overeen met de afstand van punt i tot punt j.
Omdat er n steden in de matrix zitten, is D een nxn matrix met niet-negatieve elementen dij >=0
Elke geldige route vertegenwoordigt een cyclus waarin de handelsreiziger de stad slechts één keer bezoekt en terugkeert naar de oorspronkelijke stad.
De lengte van de route wordt bepaald door de uitdrukking:
F(Mk) = ∑d ij
Bovendien wordt elke rij en kolom slechts één keer in de route opgenomen met het element dij.
Stap 1.
Bepalen van de vertakkingsrand

ik j	1	2	3	4	5	d ik
1	M	40	40	0(40)	60	40
2	20	M	0(20)	10	30	10
3	30	0(10)	M	40	0(30)	0
4	0(10)	50	10	M	40	10
5	0(0)	10	30	0(0)	M	0
dj	0	10	10	0	30	0

d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
De grootste som van reductieconstanten is (40 + 0) = 40 voor de rand (1,4). Daarom wordt de set verdeeld in twee subsets (1,4) en (1*,4*).

H(1*,4*) = 140 + 40 = 180
We elimineren de rand (1,4) door het element d 14 = 0 te vervangen door M, waarna we de volgende reductie van de afstandsmatrix voor de resulterende deelverzameling (1*,4*) uitvoeren, als resultaat verkrijgen we een gereduceerde matrix.

ik j	1	2	3	4	5	d ik
1	M	40	40	M	60	40
2	20	M	0	10	30	0
3	30	0	M	40	0	0
4	0	50	10	M	40	0
5	0	10	30	0	M	0
dj	0	0	0	0	0	40

Het opnemen van rand (1,4) wordt uitgevoerd door alle elementen van de eerste rij en de vierde kolom uit te sluiten, waarbij het element d 41 wordt vervangen door M om de vorming van een niet-Hamiltoniaanse cyclus te elimineren.
Het resultaat is nog een gereduceerde matrix (4 x 4), die wordt onderworpen aan de reductiebewerking.

∑d ik + ∑d j = 10

ik j	1	2	3	5	d ik
2	20	M	0	30	0
3	30	0	M	0	0
4	M	50	10	40	10
5	0	10	30	M	0
dj	0	0	0	0	10

De ondergrens van de deelverzameling (1,4) is gelijk aan:
H(1,4) = 140 + 10 = 150 ≤ 180
Omdat de ondergrens van deze deelverzameling (1,4) kleiner is dan de deelverzameling (1*,4*), nemen we rand (1,4) op in de route met een nieuwe grens H = 150
Stap 2.
Bepalen van de vertakkingsrand en verdeel de gehele set routes ten opzichte van deze rand in twee subsets (i,j) en (i*,j*).
Voor dit doel vervangen we voor alle cellen van de matrix met nulelementen de nullen één voor één door M (oneindig) en bepalen voor hen de som van de resulterende reductieconstanten, deze staan ​​tussen haakjes.

ik j	1	2	3	5	d ik
2	20	M	0(20)	30	20
3	30	0(10)	M	0(30)	0
4	M	40	0(30)	30	30
5	0(30)	10	30	M	10
dj	20	10	0	30	0

d(2,3) = 20 + 0 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,3) = 30 + 0 = 30; d(5,1) = 10 + 20 = 30;
De grootste som van reductieconstanten is (0 + 30) = 30 voor de rand (3,5). Daarom wordt de set verdeeld in twee subsets (3,5) en (3*,5*).
De ondergrens voor Hamiltoniaanse cycli van deze deelverzameling is:
H(3*,5*) = 150 + 30 = 180
We elimineren de rand (3.5) door het element d 35 = 0 te vervangen door M, waarna we de volgende reductie van de afstandsmatrix voor de resulterende deelverzameling (3*,5*) uitvoeren, als resultaat verkrijgen we een gereduceerde matrix .

ik j	1	2	3	5	d ik
2	20	M	0	30	0
3	30	0	M	M	0
4	M	40	0	30	0
5	0	10	30	M	0
dj	0	0	0	30	30

Het opnemen van rand (3.5) wordt uitgevoerd door alle elementen van de 3e rij en 5e kolom uit te sluiten, waarbij het element d 53 wordt vervangen door M om de vorming van een niet-Hamiltoniaanse cyclus te elimineren.
Als resultaat verkrijgen we nog een gereduceerde matrix (3 x 3), die onderworpen is aan de reductiebewerking.
De som van de reductieconstanten van de gereduceerde matrix:
∑d ik + ∑d j = 10
Na de reductiebewerking ziet de gereduceerde matrix er als volgt uit:

ik j	1	2	3	d ik
2	20	M	0	0
4	M	40	0	0
5	0	10	M	0
dj	0	10	0	10

De ondergrens van de deelverzameling (3.5) is gelijk aan:
H(3,5) = 150 + 10 = 160 ≤ 180
Omdat de ondergrens van deze deelverzameling (3,5) kleiner is dan de deelverzameling (3*,5*), nemen we rand (3,5) op in de route met een nieuwe grens H = 160
Stap 3.
Bepalen van de vertakkingsrand en verdeel de gehele set routes ten opzichte van deze rand in twee subsets (i,j) en (i*,j*).
Voor dit doel vervangen we voor alle cellen van de matrix met nulelementen de nullen één voor één door M (oneindig) en bepalen voor hen de som van de resulterende reductieconstanten, deze staan ​​tussen haakjes.

ik j	1	2	3	d ik
2	20	M	0(20)	20
4	M	30	0(30)	30
5	0(20)	0(30)	M	0
dj	20	30	0	0

d(2,3) = 20 + 0 = 20; d(4,3) = 30 + 0 = 30; d(5,1) = 0 + 20 = 20; d(5,2) = 0 + 30 = 30;
De grootste som van reductieconstanten is (0 + 30) = 30 voor de rand (5,2). Daarom wordt de set verdeeld in twee subsets (5,2) en (5*,2*).
De ondergrens voor Hamiltoniaanse cycli van deze deelverzameling is:
H(5*,2*) = 160 + 30 = 190
We elimineren de rand (5,2) door het element d52 = 0 te vervangen door M, waarna we de volgende reductie van de afstandsmatrix voor de resulterende deelverzameling (5*,2*) uitvoeren, als resultaat verkrijgen we een gereduceerde Matrix.

ik j	1	2	3	d ik
2	20	M	0	0
4	M	30	0	0
5	0	M	M	0
dj	0	30	0	30

Het opnemen van rand (5.2) wordt uitgevoerd door alle elementen van de 5e rij en de 2e kolom uit te sluiten, waarbij het element d 25 wordt vervangen door M om de vorming van een niet-Hamiltoniaanse cyclus te elimineren.
Als resultaat verkrijgen we nog een gereduceerde matrix (2 x 2), die onderworpen is aan de reductiebewerking.
De som van de reductieconstanten van de gereduceerde matrix:
∑d ik + ∑d j = 20
Na de reductiebewerking ziet de gereduceerde matrix er als volgt uit:

ik j	1	3	d ik
2	20	0	0
4	M	0	0
dj	20	0	20

De ondergrens van de deelverzameling (5,2) is gelijk aan:
H(5,2) = 160 + 20 = 180 ≤ 190
Omdat de ondergrens van deze deelverzameling (5,2) kleiner is dan de deelverzameling (5*,2*), nemen we rand (5,2) op in de route met een nieuwe grens H = 180
In overeenstemming met deze matrix nemen we randen (2,1) en (4,3) op in de Hamiltoniaanse route.
Als resultaat vormen langs de vertakkende boom van de Hamiltoniaanse cyclus de randen:
(1,4), (4,3), (3,5), (5,2), (2,1),
De routelengte is F(Mk) = 180

Hieronder vindt u de toestand van het probleem en het tekstgedeelte van de oplossing. De hele oplossing is doc-formaat in het archief kunt u downloaden. Sommige tekens verschijnen mogelijk niet op de pagina, maar word document alles wordt weergegeven. Er kunnen meer voorbeelden van werk op het gebied van EMMM worden bekeken

FORMULERING VAN HET PROBLEEM

De uitgeverij moet het typewerk binnen een week (aantal dagen m = 5) voltooien met behulp van medewerkers van n categorieën (hoog, gemiddeld, ondergemiddeld, laag). Het is vereist om het optimale aantal werknemers per categorie te bepalen, wat de voltooiing van het werk garandeert met minimale uitgaven van het loonfonds onder bepaalde beperkingen. De initiële gegevens worden weergegeven in tabellen 1 en 2.

tafel 1

tafel 2

Het probleem moet worden opgelost met behulp van de gehele methode lineair programmeren in Mathcad 2000/2001.

EEN WISKUNDIG MODEL BOUWEN
OPLOSSINGENTAKEN

Om het optimale aantal werknemers te berekenen, wat een minimale uitgave van het loonfonds garandeert, wiskundig model lineaire programmering met gehele getallen, aangezien het aantal werknemers geen fractionele waarde kan zijn.

De oplossing van het probleem integer programmeren uitgevoerd in twee fasen.

In de eerste fase wordt een lineair programmeerprobleem uitgevoerd zonder rekening te houden met gehele getallen.

In de tweede fase wordt het gemaakt stap voor stap proces het vervangen van niet-gehele variabelen door de dichtstbijzijnde bovenste of onderste gehele waarden.

Ten eerste wordt het probleem opgelost zonder rekening te houden met de voorwaarde van gehele getallen.

De doelfunctie wordt bepaald door de formule:

Waar Q- algemeen salarisfonds voor het verrichten van werkzaamheden;

X 1 , X 2 , …, x n- aantal medewerkers per categorie;

N - aantal categorieën werknemers;

C 1 , C 2 ,…, cn- dagloon van één werknemer per categorie;

M- aantal werkdagen per week, M = 5.

De doelfunctie kan in vectorvorm worden geschreven:

Bij het oplossen van het probleem moet aan de volgende beperkingen worden voldaan. Bovengrens

X ≤ D (1)

specificeert het maximale aantal werknemers per categorie, waarbij d een vector is die het aantal werknemers per categorie bepaalt.

In beperking

er wordt rekening mee gehouden dat het totale aantal werknemers niet groter mag zijn k max.

In de beperking van onderaf

R× x≥P(3)

het komt tot uiting dat alle werknemers samen een bepaalde hoeveelheid werk moeten voltooien R.

Als laatste beperking de voorwaarde voor de niet-negativiteit van de vector van variabelen is geschreven

X≥0 (4)

Het wiskundige model voor het oplossen van het probleem zonder rekening te houden met de voorwaarde voor gehele getallen omvat de volgende uitdrukkingen:

X ≤ D

R× x≥P,

X ≥ 0 .

Het integer-programmeermodel moet zowel expressies (5) als bevatten aanvullende beperkingen, met behulp van welke niet-gehele variabelen X worden vervangen door gehele waarden. Specifieke modelexpressies met integer-variabelen worden in de volgende subsectie besproken.

HET OPTIMALISATIEPROBLEEM OPLOSSEN INMATHCAD

De brongegevens voor het voorbeeld worden gegeven in de tabel. 1 en 2.

Om het probleem op te lossen, gebruikt u het Mathcad-pakket met de functie Minimaliseren. Deze functie bepaalt de probleemoplossingsvector:

X:= Minimaliseren ( Q, X),

Waar Q- uitdrukking objectieve functie, die het minimumloonfonds bepaalt, X- vector van variabelen.

Ten eerste wordt het probleem opgelost zonder rekening te houden met de voorwaarde van gehele getallen. Deze oplossing wordt gegeven in bijlage 1. De eerste regel bevat nul beginwaarden van de vector X en objectieve functie Q(X) . Na het woord Gegeven en vóór de functie Minimaliseren worden beperkingen aangegeven. Als resultaat werd een niet-geheel optimaal getal per categorie verkregen:

X =

met salarisfonds Q= 135 cu. e.

Van deze beslissing Een geheeltallige oplossing wordt gevonden met behulp van de branch and bound-methode.

Eerst analyseert de resulterende oplossing de fractionele waarde x 4 =
= 1,143. Je kunt er twee gehele waarden voor instellen: x 4 = 1 en x 4 = 2. De constructie van een beslisboom begint (bijlage 2). Het initiële nulknooppunt wordt gereserveerd in de beslissingsboom. Het wordt vervolgens verbonden door het eerste knooppunt x4, en vanaf dit knooppunt worden twee takken getekend die overeenkomen met de beperkingen: x4 = 1 en x4 = 2.

Voor een tak met de beperking x 4 = 1 wordt het lineaire programmeringsprobleem uit bijlage 1 opgelost, rekening houdend met deze beperking.

Als gevolg hiervan werd een oplossing voor dit probleem verkregen. De variabele x 1 werd een geheel getal, maar de variabele x 2 werd een breuk x 2 = 0,9.

Om de vertakking voort te zetten, worden een knooppunt x 3 en een vertakking x 3 = 1 gemaakt. Het lineaire programmeerprobleem wordt opnieuw uitgevoerd met alle drie de beperkingen: x 4 = 1, x 2 = 1, x 3 = 1. Met deze beperkingen, het probleem heeft een oplossing x T =
= (1,938 1 1 1).

Om de vertakking voort te zetten, worden een knooppunt x 1 en een vertakking x 1 = 2 gemaakt. Het lineaire programmeerprobleem wordt opnieuw uitgevoerd met alle drie de beperkingen: x 4 = 1, x 2 = 1, x 3 = 1, x 1 = 2 Met deze beperkingen heeft het probleem een ​​oplossing x T = = (2 1 1 1).

Het proces van het construeren van een oplossingsboom en het uitvoeren van een lineair programmeerprobleem wordt herhaald totdat alle vertakkingen zijn geconstrueerd.

Bijlage 2 geeft een volledige boomstructuur van mogelijke geheeltallige oplossingen, waaruit volgt dat het probleem vier effectieve oplossingen heeft.

De beste wordt geselecteerd uit de effectieve oplossingen en wordt geaccepteerd als de optimale gehele oplossing van het hele probleem met de minimale waarde Q(X) . In ons geval hebben we twee optimale gehele oplossingen

Q(X) = 140,

xT = (2 1 1 1),

xT = (1 1 2 2).

Bijgevolg moet de uitgeversorganisatie twee hooggekwalificeerde werknemers inhuren voor het typen van tekst, één werknemer midden categorie, één werknemer onder de gemiddelde categorie en één werknemer uit de lage categorie. Een andere gelijkwaardige optie om werknemers aan te trekken is ook mogelijk: één werknemer uit de hoge categorie, één werknemer uit de middencategorie, twee werknemers uit de benedengemiddelde categorie en twee werknemers uit de lage categorie. Bij beide opties zullen de kosten minimaal zijn en 140 den bedragen. eenheden

Download de oplossing voor het probleem:

Bestandsnaam: 2.rar
Bestandsgrootte: 24,99 Kb

Als het downloaden van het bestand niet na 10 seconden begint, klikt u op

Definities

is een niet-lege eindige verzameling bestaande uit twee deelverzamelingen en . Eerste subset (hoekpunten) bestaat uit een reeks elementen. De tweede deelverzameling (bogen) bestaat uit geordende paren elementen van de eerste deelverzameling . Als de hoekpunten en zodanig zijn dat , dan zijn dit aangrenzende hoekpunten.

Route in de kolom

is een reeks hoekpunten die niet noodzakelijkerwijs paarsgewijs verschillend zijn, waar dan ook aangrenzend aan . Een route wordt een keten genoemd als alle randen paarsgewijs verschillend zijn. Als dan wordt de route gesloten genoemd. Gesloten circuit een cyclus genoemd.

Formulering van het probleem

De handelsreiziger moet reizen N steden. Om de kosten te drukken wil hij een route zo aanleggen dat hij precies één keer alle steden rondgaat en met een minimum aan kosten terugkeert naar de oorspronkelijke.

In termen van grafentheorie kan het probleem als volgt worden geformuleerd. Set N hoekpunten en matrix ( C ij), waar C ij ≥0 – lengte (of prijs) van de boog ( i , J),

. Onder handelsreizigerroute z laten we de cyclus begrijpen i 1 , i 2 ,…, i N , i 1 punten 1,2,…, n. Dus, route is een reeks bogen. Als tussen steden i En J er geen overgang is, dan wordt het “oneindigheids”-symbool in de matrix geplaatst. Het moet diagonaal worden geplaatst, wat betekent dat het verboden is terug te keren naar een punt waar je al doorheen bent gegaan handelsreizigerroute, routelengte l (z) is gelijk aan de som van de lengtes van de bogen in de route. Laten Z– de verzameling van alle mogelijke routes. Initiële piek i 1 – vast. We moeten een route z 0 О vinden Z, zoals dat l (z 0)= min l (z), z Î Z .

De oplossing van het probleem

Het hoofdidee van de branch and bound-methode is dat eerst een ondergrens φ wordt geconstrueerd op de lengtes van de set routes Z. Vervolgens wordt de set routes in twee subsets verdeeld, zodat de eerste subset

bestond uit routes die een boog (i, j) bevatten, en een andere subset bevatte deze boog niet. Voor elk van de subsets worden de ondergrenzen bepaald volgens dezelfde regel als voor de oorspronkelijke set routes. De resulterende ondergrenzen van de deelverzamelingen blijken niet minder te zijn dan de ondergrens van de verzameling van alle routes, d.w.z. φ(Z)≤ φ (), φ(Z) ≤ φ ().

Ondergrenzen vergelijken φ (

) En φ (), kunnen we de subset van routes selecteren waarvan de kans groter is dat deze een route met een minimale lengte bevat.

Dan een van de subsets

of, volgens een soortgelijke regel, is verdeeld in twee nieuwe en . Voor hen worden opnieuw ondergrenzen gevonden φ (), En φ () enz. Het vertakkingsproces gaat door totdat er één enkele route is gevonden. Het wordt het eerste record genoemd. Dan kijken ze door de gescheurde takken. Als hun ondergrenzen groter zijn dan de lengte van het eerste record, is het probleem opgelost. Als er records zijn waarvoor de ondergrenzen kleiner zijn dan de lengte van het eerste record, dan is de subset met de kleinste ondergrens ondergaat verdere vertakking totdat ze ervan overtuigd zijn dat het niet het beste bevat route .

Als er een wordt gevonden, gaat de analyse van de gebroken takken verder met betrekking tot de nieuwe waarde van de routelengte. Het wordt het tweede record genoemd. Het oplossingsproces eindigt wanneer alle subsets zijn geanalyseerd.

Voor praktische uitvoering De branch and bound-methode, zoals toegepast op het handelsreizigersprobleem, zal een techniek aangeven voor het bepalen van de ondergrenzen van subsets en het verdelen van de reeks routes in subsets (branching).

Om de ondergrens te vinden, gebruiken we de volgende overweging: als een bepaald getal wordt opgeteld of afgetrokken van de elementen van een rij van de matrix van het handelsreizigerprobleem (rij of kolom), dan zal de optimaliteit van het plan niet veranderen. wijziging. De lengte van eventuele handelsreizigerroute zal met dit bedrag veranderen.

Trek van elke regel een getal af dat gelijk is aan het minimumelement van deze regel. Trek van elke kolom een ​​getal af dat gelijk is aan het minimumelement van die kolom. De resulterende matrix wordt gereduceerd met rijen en kolommen genoemd. De som van alle afgetrokken getallen wordt de reductieconstante genoemd.

Als ondergrens voor de lengte van routes moet een werpconstante worden gekozen.

Een reeks routes opsplitsen in subsets

Om kandidaten te identificeren voor opname in de reeks bogen waarlangs vertakkingen worden uitgevoerd, beschouwen we in de gegeven matrix alle elementen gelijk aan nul. Laten we de graden Θ ij van de nulelementen van deze matrix vinden. Rang nul-elementΘ ij is gelijk aan de som van het minimumelement in de rij i en het minimumelement in de kolom J(bij het kiezen van deze minima C ij – er wordt geen rekening mee gehouden). Met de hoogste waarschijnlijkheid behoort de vereiste route tot bogen met een maximale graad van nul.

Om de betalingsmatrix van routes te verkrijgen, inclusief de boog ( i , J) schrappen we de rij in de matrix i en kolom J, en om de vorming van een cyclus in de route te voorkomen, vervangen we het element dat de huidige keten tot in het oneindige sluit.

Veel routes zonder boog ( i , J) wordt verkregen door het element te vervangen C ij tot oneindig.

Een voorbeeld van het oplossen van het handelsreizigersprobleem met behulp van de branch and bound-methode

Een handelsreiziger moet naar 6 steden reizen. Om de kosten te drukken wil hij een route zo aanleggen dat hij precies één keer alle steden rondgaat en met een minimum aan kosten terugkeert naar de oorspronkelijke. Bronstad A. De kosten van verplaatsing tussen steden worden weergegeven door de volgende matrix:

A	B	C	D	E	F
A	∞	26	42	15	29	25
B	7	∞	16	1	30	25
C	20	13	∞	35	5	0
D	21	16	25	∞	18	18
E	12	46	27	48	∞	5
F	23	5	5	9	5	∞

De oplossing van het probleem

Voor het gemak van de presentatie zullen we overal hieronder in de betalingsmatrix de namen van steden (A, B, ..., F) vervangen door de nummers van de overeenkomstige rijen en kolommen (1, 2, ..., 6).

Laten we de ondergrens vinden voor de lengtes van de verzameling van alle routes. Laten we van elke rij een getal aftrekken dat gelijk is aan het minimumelement van deze rij, en vervolgens van elke kolom een ​​getal aftrekken dat gelijk is aan het minimumelement van deze kolom, en zo een matrix in rijen en kolommen presenteren. Rijminima: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.

Nadat we ze regel voor regel hebben afgetrokken, krijgen we:

1	2	3	4	5	6
1	∞	11	27	0	14	10
2	6	∞	15	0	29	24
3	20	13	∞	35	5	0
4	5	0	9	∞	2	2
5	7	41	22	43	∞	0
6	18	0	0	4	0	∞

Kolomminima: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6.

Nadat we ze met kolommen hebben afgetrokken, krijgen we de volgende matrix:

1	2	3	4	5	6
1	∞	11	27	0	14	10
2	1	∞	15	0	29	24
3	15	13	∞	35	5	0
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞

Laten we de ondergrens vinden φ (Z) = 15+1+0+16+5+5+5 = 47.

Om kandidaten te identificeren voor opname in de reeks bogen waarlangs vertakkingen worden uitgevoerd, vinden we de graden Θ ij van de nulelementen van deze matrix (de som van de minima in de rij en kolom). Θ 14 = 10 + 0,
Θ 24 = 1 + 0, Θ 36 = 5+0, Θ 41 = 0 + 1, Θ 42 = 0 + 0, Θ 56 = 2 + 0, Θ 62 = 0 + 0,
Θ 63 = 0 + 9, Θ 65 = 0 + 2. De hoogste graad is Θ 14 = 10. We voeren vertakkingen uit langs de boog (1, 4).

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 wordt een controle uitgevoerd op de partitie-elementen om te bepalen of de gegeven subset deze bevat optimale oplossing of niet. Om dit te doen, wordt de lagere schatting van de objectieve functie op een gegeven subset berekend.

Als de lagere schatting niet minder is dan het record (de beste gevonden oplossing), mag de subset niet langer in aanmerking worden genomen. De gecontroleerde subset kan ook worden weggegooid als deze kan worden gevonden beste oplossing. 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 geselecteerd uit de niet-weggegooide subsets (bijvoorbeeld with laagste waarde lagere schatting) en wordt gesplitst. Nieuwe subsets worden opnieuw gecontroleerd, enz. De ondergrensberekening is het belangrijkste element van deze regeling.

Voor elk specifieke taak Bij integer programmeren (met andere woorden, discrete optimalisatie) wordt de branch-and-bound-methode op zijn eigen manier geïmplementeerd. Er zijn veel wijzigingen in deze methode.

Laten we eens kijken naar de implementatie van de branch and bound-methode voor het handelsreizigersprobleem en het knapzakprobleem.

Laten we het algoritme van Little eens bekijken (volgens de branch and bound-methode) voor het handelsreizigersprobleem. Het idee kan als volgt worden geformuleerd. In elke rij van de afstandsmatrix wordt het minimumelement gevonden en afgetrokken van alle elementen van de overeenkomstige rij. Het resultaat is een matrix die rij voor rij wordt verkleind. De matrix wordt op dezelfde manier weergegeven door kolommen. Het resultaat is een matrix weergegeven in rijen en kolommen. Door de minimale elementen tijdens de reductie op te tellen, verkrijgen we de reductieconstante, die de ondergrens zal zijn van de verzameling van alle toelaatbare Hamiltoniaanse contouren. Vervolgens worden de graden van nullen voor de gegeven matrix gevonden (de som van de minimale elementen van de rij en kolom die overeenkomen met deze nul) en wordt de boog geselecteerd waarvoor de graad van het nulelement de maximale waarde bereikt. De verzameling van alle Hamiltoniaanse contouren is verdeeld in twee deelverzamelingen, waarvan er één de boog bevat, de tweede deze boog niet. Hierna worden de resulterende matrices van Hamiltoniaanse contouren gegeven en worden de ondergrenzen van een subset van Hamiltoniaanse contouren vergeleken om de set met de kleinere ondergrens te selecteren voor verdere verdeling. Het proces van het opdelen van sets in subsets gaat gepaard met de constructie van een vertakkingsboom. Door de lengte van de Hamiltoniaanse contour te vergelijken met de ondergrenzen van de bungelende takken, wordt een subset met een ondergrens kleiner dan de resulterende contour geselecteerd voor verdere vertakking totdat een route met de kortste lengte wordt verkregen of het duidelijk wordt dat een dergelijke route bestaat niet.

Voorbeeld.

Geef het handelsreizigersprobleem de volgende matrix van reiskosten

We vinden het minimumelement in elke rij van de matrix en trekken dit af van alle elementen van de overeenkomstige rij. We verkrijgen een matrix, rij voor rij gereduceerd, met elementen

.

Als de matrix, rij voor rij gegeven, kolommen bevat die geen nul bevatten, dan verkleinen we deze per kolom. Om dit te doen, selecteert u het minimumelement in elke kolom van de matrix en trekt u dit af van alle elementen van de overeenkomstige kolom. Laten we de matrix pakken

,

elke rij en kolom die minstens één nul bevat. Zo'n matrix wordt gereduceerd door rijen en kolommen genoemd.

Door de elementen en op te tellen, verkrijgen we de reductieconstante:

.

We vinden de machten van nullen voor de matrix gegeven in rijen en kolommen. Om dit te doen, vervangt u mentaal de nullen in de matrix door een teken en vindt u de som van de minimale elementen van de rij en kolom die overeenkomen met deze nul. We schrijven het rechts bovenste hoek cellen:

.

We selecteren de boog waarvoor de graad van het nulelement de maximale waarde bereikt

We verdelen de set van alle geldige routes in twee subsets:

– een subset die de boog bevat;

– een subset die geen boog bevat

Om de kostenraming te berekenen voor routes waarin de boog voorkomt, schrappen we de rij en kolom in de matrix en vervangen we het symmetrische element door het bord. We presenteren de resulterende matrix en berekenen de som van de reductieconstanten.

5x 1 + 2x 2 ≤ 14
2x 1 + 5x 2 ≤ 16
x 1 , x 2 – gehele getallen
Z = 3x 1 + 5x 2 → max
We vinden de oplossing met behulp van een rekenmachine:
Laten we een regio met haalbare oplossingen construeren, d.w.z. Laten we het systeem van ongelijkheden grafisch oplossen. Om dit te doen construeren we elke rechte lijn en definiëren we de halve vlakken die worden gedefinieerd door de ongelijkheden (de halve vlakken worden aangegeven met een priemgetal).

Grenzen van de regio van haalbare oplossingen
Het snijpunt van halve vlakken zal een gebied zijn waarvan de puntcoördinaten voldoen aan de ongelijkheden van het systeem van beperkingen van het probleem.
Laten we de grenzen van het gebied van de oplossingspolygoon aangeven.

Beschouw de objectieve functie van het probleem F = 3x 1 +5x 2 → max.
Laten we een rechte lijn construeren die overeenkomt met de waarde van de functie F = 0: F = 3x 1 +5x 2 = 0. We zullen deze rechte lijn parallel verplaatsen. Omdat we geïnteresseerd zijn in de maximale oplossing, verplaatsen we daarom de rechte lijn tot de laatste aanraking van het aangewezen gebied. In de grafiek is deze rechte lijn aangegeven met een stippellijn.

Direct F(x) = constant (1) En (2)
5x 1 +2x 2 ≤14
2x 1 +5x 2 ≤16

Nadat we het stelsel vergelijkingen hebben opgelost, krijgen we: x 1 = 1,8095, x 2 = 2,4762
F(X) = 3*1,8095 + 5*2,4762 = 17,8095
De optimale waarde van de variabele x 1 =1,81 bleek geen geheel getal te zijn.
In de eerste wordt de voorwaarde x 1 ≥ 2 toegevoegd aan de voorwaarden van probleem 11, en de voorwaarde x 1 ≤ 1 wordt toegevoegd aan probleem 12.
Deze procedure heet vertakking door variabele x 1.

5x 1 +2x 2 ≤14	(1)
2x 1 +5x 2 ≤16	(2)
x 1 ≥2	(3)
x 1 ≥0	(4)
x 2 ≥0	(5)

Direct F(x) = constant snijdt het gebied op punt B. Omdat punt B wordt verkregen als resultaat van het snijpunt van lijnen (1) En (3) , dan voldoen de coördinaten ervan aan de vergelijkingen van deze lijnen:
5x 1 +2x 2 ≤14
x 1 ≥2

Waar vinden we het vandaan? maximale waarde objectieve functie:
F(X) = 3*2 + 5*2 = 16

De oplossing voor het probleem bleek een geheel getal te zijn.
De nieuwe waarde van het huidige record is F(X) = 16.
Omdat het gevonden punt het eerste is gehele oplossing, dan moeten deze en de bijbehorende CF-waarde worden onthouden. Het punt zelf wordt genoemd huidig ​​geheel getalrecord of gewoon een record, maar de optimale waarde geheel getal probleem - huidige recordwaarde. Deze waarde is de ondergrens optimale waarde origineel probleem Z*.

5x 1 +2x 2 ≤14	(1)
2x 1 +5x 2 ≤16	(2)
x 1 ≤1	(3)
x 1 ≥0	(4)
x 2 ≥0	(5)

Het gebied van haalbare oplossingen is een polygoon
Direct F(x) = constant (2) En (3) , dan voldoen de coördinaten ervan aan de vergelijkingen van deze lijnen:
2x 1 +5x 2 ≤16
x 1 ≤1

Nadat we het stelsel vergelijkingen hebben opgelost, krijgen we: x 1 = 1, x 2 = 2,8
Hoe kunnen we de maximale waarde van de doelfunctie vinden:
F(X) = 3*1 + 5*2,8 = 17

De optimale waarde van de variabele x 2 =2,8 bleek geen geheel getal te zijn.
We verdelen taak 12 in twee subtaken 121 en 122.
In de eerste wordt de voorwaarde x 2 ≥ 3 toegevoegd aan de voorwaarden van probleem 121, en de voorwaarde x 2 ≤ 2 wordt toegevoegd aan probleem 122.
Laten we probleem 121 grafisch oplossen als een LP-probleem.

5x 1 +2x 2 ≤14	(1)
2x 1 +5x 2 ≤16	(2)
x 1 ≤1	(3)
x 2 ≥3	(4)
x 1 ≥0	(5)
x 2 ≥0	(6)

Het gebied van haalbare oplossingen is een driehoek.
Direct F(x) = constant snijdt het gebied op punt C. Omdat punt C wordt verkregen als resultaat van het snijpunt van lijnen (2) En (4) , dan voldoen de coördinaten ervan aan de vergelijkingen van deze lijnen:
2x 1 +5x 2 ≤16
x 2 ≥3

Hoe kunnen we de maximale waarde van de doelfunctie vinden:
F(X) = 3*0,5 + 5*3 = 16,5

Laten we probleem 122 grafisch oplossen als een LP-probleem.

5x 1 +2x 2 ≤14	(1)
2x 1 +5x 2 ≤16	(2)
x 1 ≤1	(3)
x 2 ≤2	(4)
x 1 ≥0	(5)
x 2 ≥0	(6)

Het gebied van haalbare oplossingen is een polygoon
Direct F(x) = constant snijdt het gebied in punt D. Omdat punt D wordt verkregen als resultaat van het snijpunt van lijnen (3) En (4) , dan voldoen de coördinaten ervan aan de vergelijkingen van deze lijnen:
x 1 ≤1
x 2 ≤2

Nadat we het stelsel vergelijkingen hebben opgelost, krijgen we: x 1 = 1, x 2 = 2
Hoe kunnen we de maximale waarde van de doelfunctie vinden:
F(X) = 3*1 + 5*2 = 13

Het huidige record is Z=16≥13, dus we stoppen met vertakken vanaf dit hoekpunt

We hebben taak 121 opgesplitst in twee subtaken 1211 en 1212.
In de eerste wordt de voorwaarde x 1 ≥ 1 toegevoegd aan de voorwaarden van probleem 1211, en de voorwaarde x 1 = 0 wordt toegevoegd aan probleem 1212.
Laten we probleem 1211 grafisch oplossen als een LP-probleem.

Het probleem kent geen haalbare oplossingen. ODR is een lege set.

Probleem 1211 heeft geen oplossing, dus onderbreken we het vertakkingsproces ervoor.
Laten we probleem 1212 grafisch oplossen als een LP-probleem.

5x 1 +2x 2 ≤14	(1)
2x 1 +5x 2 ≤16	(2)
x 1 ≤1	(3)
x 2 ≥3	(4)
x 1 =0	(5)
x 1 ≥0	(6)
x 2 ≥0	(7)

Het gebied van haalbare oplossingen is een polygoon
Direct F(x) = constant snijdt het gebied in punt D. Omdat punt D wordt verkregen als resultaat van het snijpunt van lijnen (2) En (7) , dan voldoen de coördinaten ervan aan de vergelijkingen van deze lijnen:
2x 1 +5x 2 ≤16
x 1 =0

Hoe kunnen we de maximale waarde van de doelfunctie vinden:
F(X) = 3*0 + 5*3,2 = 16

De optimale waarde van de variabele x 2 =2,48 bleek geen geheel getal te zijn.
We verdelen taak 1 in twee subtaken 11 en 12.
In de eerste wordt de voorwaarde x 2 ≥ 3 toegevoegd aan de voorwaarden van probleem 11, en de voorwaarde x 2 ≤ 2 wordt toegevoegd aan probleem 12.
Deze procedure heet vertakking door variabele x 2.
Laten we probleem 11 grafisch oplossen als een LP-probleem.

5x 1 +2x 2 ≤14	(1)
2x 1 +5x 2 ≤16	(2)
x 2 ≥3	(3)
x 1 ≥0	(4)
x 2 ≥0	(5)

Het gebied van haalbare oplossingen is een driehoek.
Direct F(x) = constant snijdt het gebied op punt C. Omdat punt C wordt verkregen als resultaat van het snijpunt van lijnen (2) En (3) , dan voldoen de coördinaten ervan aan de vergelijkingen van deze lijnen:
2x 1 +5x 2 ≤16
x 2 ≥3

Nadat we het stelsel vergelijkingen hebben opgelost, krijgen we: x 1 = 0,5, x 2 = 3
Hoe kunnen we de maximale waarde van de doelfunctie vinden:
F(X) = 3*0,5 + 5*3 = 16,5

Laten we probleem 12 grafisch oplossen als een LP-probleem.

5x 1 +2x 2 ≤14	(1)
2x 1 +5x 2 ≤16	(2)
x 2 ≤2	(3)
x 1 ≥0	(4)
x 2 ≥0	(5)

Het gebied van haalbare oplossingen is een polygoon
Direct F(x) = constant snijdt het gebied op punt C. Omdat punt C wordt verkregen als resultaat van het snijpunt van lijnen (1) En (3) , dan voldoen de coördinaten ervan aan de vergelijkingen van deze lijnen:
5x 1 +2x 2 ≤14
x 2 ≤2

Nadat we het stelsel vergelijkingen hebben opgelost, krijgen we: x 1 = 2, x 2 = 2
Hoe kunnen we de maximale waarde van de doelfunctie vinden:
F(X) = 3*2 + 5*2 = 16

Het huidige record is Z=16≥16, dus we stoppen met vertakken vanaf dit hoekpunt
De optimale waarde van de variabele x 1 =0,5 bleek geen geheel getal te zijn.
We verdelen taak 11 in twee subtaken 111 en 112.
In de eerste wordt de voorwaarde x 1 ≥ 1 toegevoegd aan de voorwaarden van probleem 111, en de voorwaarde x 1 = 0 wordt toegevoegd aan probleem 112.
Laten we probleem 111 grafisch oplossen als een LP-probleem. Direct F(x) = constant snijdt het gebied in punt D. Omdat punt D wordt verkregen als resultaat van het snijpunt van lijnen (2) En (6) , dan voldoen de coördinaten ervan aan de vergelijkingen van deze lijnen:
2x 1 +5x 2 ≤16
x 1 =0

Nadat we het stelsel vergelijkingen hebben opgelost, krijgen we: x 1 = 0, x 2 = 3,2
Hoe kunnen we de maximale waarde van de doelfunctie vinden:
F(X) = 3*0 + 5*3,2 = 16

Het huidige record is Z=16≥16, dus we stoppen met vertakken vanaf dit hoekpunt
F(X) = 16
x1=2
x2=2

Probleem oplossingsboom