Metóda vetvenia a väzby stručne. Približné a heuristické metódy. Algoritmus pozostáva z dvoch fáz

Nižšie je uvedený stav problému a textová časť riešenia. Celé riešenie je úplne vo formáte doc v archíve si môžete stiahnuť. Niektoré znaky sa na stránke nemusia objaviť, ale wordový dokument všetko sa zobrazí. Ďalšie príklady práce na EMMM si môžete pozrieť

FORMULÁCIA PROBLÉMU

Vydavateľstvo musí do týždňa (počet dní m = 5) dokončiť prácu na stroji s pomocou pracovníkov n kategórií (vysoká, stredná, podpriemerná, nízka). Je potrebné určiť optimálny počet zamestnancov podľa kategórií, ktorý zabezpečí výkon práce s minimálnymi výdavkami mzdového fondu pri daných obmedzeniach. Počiatočné údaje sú uvedené v tabuľkách 1 a 2.

stôl 1

tabuľka 2

Problém by mal byť vyriešený celočíselnou metódou lineárne programovanie v Mathcade 2000/2001.

STAVENIE MATEMATICKÉHO MODELU
RIEŠENIAÚLOHY

Na výpočet optimálneho počtu zamestnancov, pri ktorom je zabezpečený minimálny výdaj mzdového fondu, sa zostavuje matematický model celočíselné lineárne programovanie, keďže počet zamestnancov nemôže byť zlomková hodnota.

Riešenie problému celočíselné programovanie sa vykonáva v dvoch etapách.

V prvej fáze sa problém lineárneho programovania vykonáva bez zohľadnenia celých čísel.

V druhej fáze je to tak krok za krokom proces nahradenie neceločíselných premenných najbližšími hornými alebo dolnými celočíselnými hodnotami.

Po prvé, problém je vyriešený bez zohľadnenia celočíselnej podmienky.

Účelová funkcia je určená vzorcom:

kde Q- všeobecný mzdový fond za výkon práce;

X 1 , X 2 , …, x n- počet zamestnancov podľa kategórie;

n - počet kategórií pracovníkov;

c 1 , c 2 ,…, c n- denná tarifnej sadzby jeden zamestnanec na kategóriu;

m- počet pracovných dní v týždni m = 5.

Cieľovú funkciu možno zapísať vo vektorovej forme:

Pri riešení problému musia byť dodržané nasledujúce obmedzenia. Horný limit

X ≤ d (1)

nastavuje maximálny počet zamestnancov podľa kategórie, kde d je vektor, ktorý určuje počet podľa kategórie.

V obmedzení

Zohľadnilo sa, že celkový počet zamestnancov by nemal prekročiť kmmax.

V spodnej hranici

R× x≥P(3)

odzrkadľuje sa, že všetci zamestnanci musia spoločne dokončiť dané množstvo práce R.

Ako posledné obmedzenie sa zapisuje podmienka nezápornosti vektora premenných

X≥0 (4)

Matematický model na riešenie problému bez zohľadnenia celočíselnej podmienky obsahuje nasledujúce výrazy:

X ≤ d

R× x≥P,

X ≥ 0 .

Celočíselný programovací model by mal obsahovať výrazy (5), ako aj ďalšie obmedzenia, ktorými neceločíselné premenné X sú nahradené celočíselnými hodnotami. Špecifické modelové výrazy s celočíselnými premennými sú diskutované v ďalšej podkapitole.

RIEŠENIE PROBLÉMU OPTIMALIZÁCIE VMATHCAD

Počiatočné údaje pre príklad sú uvedené v tabuľke. 1 a 2.

Na vyriešenie problému sa používa balík Mathcad s funkciou Minimize. Táto funkcia určuje vektor riešenia problému:

X:= Minimalizovať( Q, X),

kde Q- výraz objektívna funkcia, ktorým sa určuje fond minimálnej mzdy, X- vektor premenných.

Po prvé, problém je vyriešený bez zohľadnenia celočíselnej podmienky. Toto riešenie je uvedené v prílohe 1. Prvý riadok obsahuje nulové počiatočné hodnoty vektora X a objektívna funkcia Q(X) . Za slovom Dané a pred funkciou Minimize sú uvedené obmedzenia. V dôsledku toho sa získal neceločíselný optimálny počet kategórií:

X =

s výplatnou páskou Q= 135 cu e.

Od toto rozhodnutie celočíselné riešenie sa nájde pomocou metódy vetvenia a väzby.

Najprv vo výslednom riešení zlomková hodnota x 4 =
= 1,143. Pre ňu môžete nastaviť dve celočíselné hodnoty: x 4 = 1 a x 4 = 2. Začína sa konštrukcia rozhodovacieho stromu (Príloha 2). Počiatočný nulový uzol je vynesený do rozhodovacieho stromu. Potom je spojený prvým uzlom x 4 a z tohto uzla sa vytiahnu dve vetvy zodpovedajúce obmedzeniam: x 4 \u003d 1 a x 4 \u003d 2.

Pre vetvu s obmedzením x 4 = 1 je vyriešený problém lineárneho programovania uvedený v prílohe 1, berúc do úvahy toto obmedzenie.

Výsledkom bolo riešenie tohto problému. Premenná x 1 sa stala celým číslom, ale premenná x 2 sa stala zlomkom x 2 = 0,9.

Na pokračovanie vetvy sa vytvorí uzol x 3 a vetva x 3 = 1. Opäť sa úloha lineárneho programovania vykoná so všetkými tromi obmedzeniami: x 4 = 1, x 2 = 1, x 3 = 1. S týmito obmedzeniami , úloha má riešenie x T =
= (1,938 1 1 1).

Na pokračovanie vetvy sa vytvorí uzol x 1 a vetva x 1 = 2. Úloha lineárneho programovania sa opäť vykonáva so všetkými tromi obmedzeniami: x 4 = 1, x 2 = 1, x 3 = 1, x 1 = 2. S týmito obmedzeniami má úloha riešenie x T = = (2 1 1 1).

Proces vytvárania rozhodovacieho stromu a vykonávania problému lineárneho programovania sa opakuje, kým sa nevytvoria všetky vetvy.

V prílohe 2 je uvedený úplný strom možných celočíselných riešení, z ktorých vyplýva, že v úlohe sú 4 efektívne riešenia.

Vyberie sa najlepší výsledok a ten sa akceptuje ako optimálne celočíselné riešenie celej úlohy s minimálnou hodnotou Q(X) . V našom prípade máme dve optimálne celočíselné riešenia

Q(X) = 140,

x T = (2 1 1 1),

x T = (1 1 2 2).

Preto musí vydavateľská organizácia zapojiť dvoch zamestnancov vysokej kategórie na písanie, jedného zamestnanca strednej kategórie, jeden pracovník pod strednou kategóriou a jeden pracovník v nízkej kategórii. Je možná aj iná rovnocenná možnosť prilákania pracovníkov: jeden zamestnanec vysokej kategórie, jeden zamestnanec strednej kategórie, dvaja zamestnanci podpriemernej kategórie a dvaja zamestnanci nízkej kategórie. V oboch variantoch budú náklady minimálne a dosahujú 140 denov. Jednotky

Stiahnite si riešenie problému:

Názov súboru: 2.rar
Veľkosť súboru: 24,99 Kb

Ak sa nahrávanie súboru nespustí po 10 sekundách, kliknite

Zvážte problém diskrétneho programovania vo všeobecnej forme:

Nájsť -vektor neznámych, D-konečný

množina prípustných hodnôt tohto vektora, F(x) je daná účelová funkcia.

Myšlienkou metódy je rozdeliť D na nepretínajúce sa podmnožiny Di (tento postup sa nazýva vetvenie) a vypočítať hornú a dolnú hranicu cieľovej funkcie na každej z podmnožín. Dolná hranica bude označená H a horná hranica E. V súlade s tým, Hi Eo, táto podmnožina neobsahuje optimálny bod a môže byť vylúčená z ďalšej úvahy. Ak je horná hranica Ei H nahradená H min Hi. Ak E=H, potom je problém vyriešený, inak musíme pokračovať v postupe vetvenia a výpočtu hornej a dolnej hranice. V tomto prípade môžu byť všetky alebo len niektoré podmnožiny rozdelené v ďalšom kroku, kým horná a dolná hranica nebudú rovnaké, a nie na samostatnej podmnožine, ale na prípustnú oblasť ako celok.

Jednoduchá myšlienka metódy vetvenia a väzby vyžaduje ďalšie výpočty na určenie hraníc. Spravidla to vedie k riešeniu pomocného optimalizačného problému. Ak si tieto dodatočné výpočty vyžadujú Vysoké číslo operácií môže byť účinnosť metódy nízka.

schémy dynamické programovanie pri pohybe z počiatočného bodu do koncového bodu (obr. 5.1) možno znázorniť ako postup vetvenia.

Množina všetkých prípustných trajektórií (postupnosť prechodov krok za krokom) je počiatočná množina D, na ktorej musíme nájsť dolnú a hornú hranicu, ako aj trajektóriu, na ktorej cieľová funkcia dosiahne Horná hranica a deklarovať hodnotu účelovej funkcie, ktorá jej zodpovedá, ako záznam. Konštrukcia množiny stavov získaná po prvom kroku je prvou vetvou.

Ryža. 5.1.

Teraz sú podmnožiny Di množiny trajektórií, z ktorých každá prechádza cez príslušný i-tý bod.

V nasledujúcich krokoch, po odmietnutí všetkých ciest, ktoré vedú k akémukoľvek (i-oe) stavu, okrem jednej, je zodpovedajúcou podmnožinou táto zostávajúca cesta so všetkými jej prípustnými rozšíreniami (obr. 5.1). Pre každú z týchto podmnožín je potrebné nejako nájsť hornú a dolnú hranicu. Ak spodná hranica prekročí aktuálnu hodnotu záznamu, príslušný stav a všetky jeho pokračovania sa zahodia. Ak sa na nejakej trajektórii dosiahne horná hranica a tá je menšia ako aktuálna hodnota záznamu, tak dostaneme nový záznam.

Účinnosť tohto prístupu závisí od presnosti výsledných odhadov, t.j. od Ei - Ahoj, a od času stráveného ich výpočtom.

V zjednodušenej forme sme túto metódu už použili pri riešení problému povrchovej ochrany (kapitola 4.6), keď sme odmietli štáty, pri ktorých bežné náklady prevyšovali celkové náklady na počiatočnú aproximáciu. V tomto prípade sú aktuálne náklady spodnou hranicou, ak náklady na celú zostávajúcu cestu považujeme za nulové a celkové náklady zodpovedajúce počiatočnej aproximácii sú rekordné. Pri tomto prístupe sa záznam neaktualizoval, aj keď sa to dalo urobiť vytvorením počiatočnej aproximácie (horná hranica) pre zostávajúcu cestu, rovnako ako sa to urobilo pre celú trajektóriu pri zostavovaní počiatočnej aproximácie. Dolná hranica získaná bez výpočtov zodpovedá nulovým nákladom na celú zostávajúcu cestu a je to extrémne hrubý odhad, ale získaný „zadarmo“, t.j. bez výpočtov.

Ukážme si, ako získať a použiť presnejšie odhady pri riešení vyššie uvedených problémov a mnohých ďalších problémov. V tomto prípade sa budeme snažiť získať čo najpresnejšie hranice s minimom výpočtov.

Vývoj prístupu nazývaného metóda vetvenia a viazania bol iniciovaný prácou Landa a Doiga (1960). Nie je to ani metóda, ale koncept alebo procedurálny shell, na základe ktorého začali vyvíjať algoritmy riešenia celočíselné úlohy odlišná povaha. Hodnota navrhovanej myšlienky sa stala obzvlášť viditeľnou po objavení sa prvého presného algoritmu na riešenie problému obchodného cestujúceho, postaveného podľa vetvy a viazanej schémy (Little et al., 1963). Metódu je možné použiť na úplne aj čiastočne celočíselné problémy.

Podstata myšlienky je podobná známemu vtipu o chytaní leva na púšti: púšť delíme na polovicu; ak v prvej polovici nie je lev, hľadáme ho v druhej, ktorú rozdelíme na polovicu atď. Na rozdiel od leva sa optimum nehýbe av tomto zmysle je naša úloha jednoduchšia.

Metóda spočíva v zostavení stromu úloh, ktorého koreňom je pôvodná úloha, prípadne bez celočíselnej podmienky (Integer). Základné problémy sú generované prekrývajúcimi sa problémami tak, že ich prípustné množiny (DM) sú neprekrývajúce sa podmnožiny DM prekrývajúceho problému. Rast stromov sa vyskytuje vďaka sľubným vetvám. Perspektíva je určená hodnotiace kritérium pobočkový terminál úloha V A záznamZ. stupňa V je hodnota kritéria, ktorá rozhodne nie je horšia ako optimálna hodnota, a Z je hodnota kritéria pôvodného problému dosiahnutého v procese riešenia (za počiatočnú hodnotu možno považovať hodnotu, ktorá je zjavne horšia ako optimálna). To znamená, že problém sa bude generovať iba vtedy, ak je jeho odhad lepší ako záznam. V tomto prípade nezáleží na úrovni, na ktorej sa úloha nachádza.

Zvážte metódu aplikovanú na problém lineárneho celého čísla. Aj keď neexistujú žiadne obmedzenia na počet úloh priamo generovaných perspektívou, algoritmy spravidla používajú rozdelenie na dve úlohy, to znamená, že je zostavený binárny strom (obr. 7.5). V tomto prípade pre celočíselné množiny vzťahy

O Je zrejmé, že ak napr. V 22 bude horší ako rekord resp D 22 \u003d , pravá vetva sa zlomí (tiež hovoria, že bola sondovaná). Ak hodnotenie V 22 bude lepšia Z, rozvetvenie: nastav D 22 je rozdelená do 2 podskupín. Riešenie končí, keď všetky pobočky bude skúmaná.

Typ hodnotenia závisí od smeru kritéria: pri maximalizácii sa používa horný odhad, pri minimalizácii dolný odhad. Nasledujúca prezentácia metódy sa bude týkať maximálneho problému.

Pre algoritmickú implementáciu schémy vetvenia a väzby je potrebné vyriešiť dve základné otázky:

Ako rozdeliť množinu perspektív na podmnožiny;

Ako určiť hornú hranicu kritéria na posudzovanom súbore.

Odpovede na ne závisia od typu problému (čiastočne alebo úplne celé číslo, má alebo nemá špeciálne vlastnosti, s boolovskými alebo neboolovskými premennými). Všeobecný prípad je uvedený nižšie.

Nech je známy rozsah možných hodnôt j-tá premenná

0  X j  d j ,

ktoré sa v spojitom optimálnom riešení ukázalo ako neceločíselné a rovné X j * . Celú hodnotu tejto premennej potom možno dosiahnuť buď v intervale 0  X j 
, alebo v intervale
+1 X j  d j, kde
- celá časť (obr. 7.6).

E potom zodpovedá deleniu súvislej množiny D n do dvoch neprekrývajúcich sa podmnožín D 1 n A D 2 n, ktorej zväzok sa nerovná D n. Takéto rozdelenie celočíselnej množiny zároveň spĺňa vzťahy (7.9). V tomto prípade sú celé množiny, pôvodné aj vygenerované, zahrnuté do zodpovedajúcich súvislých množín. Preto hľadanie celočíselného riešenia na spojitej množine dá rovnaký výsledok ako na celočíselnej. Je ľahké vidieť, že vyššie uvedený výber podintervalov v jednej premennej vedie k rozdeleniu pôvodnej množiny na dve podmnožiny pre ľubovoľný počet premenných.

Teraz prejdime k druhej otázke. Keďže celočíselná množina je podmnožinou zodpovedajúcej spojitej, optimálna hodnota kritérium na spojitej množine nebude vždy menšie ako na celočíselnej. Preto ako horný odhad V môžeme vziať optimálnu hodnotu kritéria L * nepretržitá úloha.

Výber počiatočnej hodnoty záznamu závisí od situácie:

ak je známa akákoľvek celočíselná hodnota, potom sa záznam považuje za rovnaký ako kritérium v ​​tomto rozhodnutí;

ak sú všetky koeficienty kritéria kladné, môžeme vziať nulovú hodnotu záznamu;

v ostatných prípadoch sa berie počiatočná hodnota záznamu - M, kde M- maximálny počet, ktorý môže byť zastúpený v počítači.

V priebehu delenia sa vytvárajú generované úlohy, ktoré sa umiestňujú do zoznam úloh. Počiatočný zoznam obsahuje iba jednu úlohu − pôvodný problém bez celočíselných podmienok. A v budúcnosti bude zoznam obsahovať iba priebežné úlohy.

Základný algoritmus, ktorý implementuje metódu vetvenia a väzby, teda zahŕňa nasledujúce kroky.

Vyššie uvedený algoritmus je základný, pretože neobsahuje jednoznačné pravidlá pre výber úlohy zo zoznamu a vetviacej sa premennej. Pri problémoch s čiastočným celým číslom výber premennej na vetvenie eliminuje spojité premenné.

Príklad 7.3 . Aplikujme algoritmus vetvenia a väzby na problém

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

3X 1 - 6X 2  1;

5X 1 +2X 2  28;

 X j  0 , celý.

O zahodením podmienky počtu gólov dostaneme súvislú úlohu, ktorú zadáme do zoznamu úloh. Keďže koeficienty kritéria sú kladné, predpokladá sa, že počiatočná hodnota záznamu je nulová. Zoberieme jedinú úlohu zo zoznamu a vyriešime ju. Optimálne riešenie dostaneme pri vrchole A (obr. 7.7): X 1 * =4,72; X 2* = 2,19. Vetvenie sa vykonáva premennou X jeden . Pridanie obmedzenia k riešenému problému X 1 4, vytvoríme úlohu 2 a pridáme X 1 5 dáva úlohu 3. Prípustné súbory nových úloh sú znázornené na obr. 7.7. Tieto úlohy sú umiestnené v zozname úloh. Riešenie úlohy 2 sa dosiahne v bode B a úlohy 3 - v bode C. Celý priebeh riešenia pôvodného problému je prezentovaný vo forme rozhodovacieho stromu na obr. 7.10. Poradie riešení úloh zo zoznamu odráža počítadlo iterácií k. Pri 3. iterácii (úloha 4) sa získalo celočíselné riešenie s hodnotou kritéria 41 (bod D na obr. 7.8). Záznam sa teda mení: Z\u003d 41. Úloha 6 má neceločíselné riešenie (vrchol E na obr. 7.9), úloha 8 má v bode F celočíselné riešenie. Výsledkom je, že po 7. opakovaní je záznam 50.

O problémy s oceľou nemajú realizovateľné riešenia, to znamená, že zoznam problémov je vyčerpaný, a preto konštatujeme, že sme získali optimálne riešenie pôvodného problému, ktoré sa rovná riešeniu súvislého problému 8.

Z vyššie uvedeného rozhodovacieho stromu je vidieť, že počet úloh v zozname by mohol byť menší, ak by sa úlohy riešili v inom poradí. Vskutku, ak problémy pravej vetvy so záznamom Z= 50, potom by po vyriešení úlohy 2 nedošlo k rozvetveniu, pretože horný odhad by bol nižší ako záznam ( V = L * =45,17<50).

E Prirodzene vyvstáva otázka: ako môže výber ďalšej premennej na vetvenie ovplyvniť počet úloh a rozhodovací strom? Takže v našom príklade, ak po 1. iterácii vetvenie podľa premennej X 2, potom dostaneme strom znázornený na obr. 7.11. Obsahuje o 2 úlohy viac ako na obr. 7.10. Samozrejme, môže to byť aj iné v inom poradí riešenia problémov.

Počet úloh, ktoré sa majú riešiť, teda v podstate závisí od výberu úlohy zo zoznamu a premennej pre vetvenie.

Z algoritmu a vyššie uvedeného príkladu vyplýva, že vetva je ukončená z jedného z troch dôvodov:

neriešiteľnosť problému;

úloha má celočíselné riešenie;

najvyššie skóre nie je vyššie ako rekord.

Urobme teraz niekoľko poznámok o metóde vetvenia a väzby. Ako už bolo uvedené, základný algoritmus nešpecifikuje pravidlá pre výber úlohy a premennej. Vo väčšine softvérových implementácií metódy sa používajú pravidlá založené na heuristických odhadoch perspektív úloh a premenných. V niektorých balíkoch, napríklad „LP v ACS“, sa ponúka niekoľko možností riadenia procesu riešenia: od automatických po manuálne, v ktorých si používateľ môže sám zvoliť úlohu aj premennú. Okrem toho sa algoritmy založené na metóde vetvenia a väzby môžu výrazne líšiť v dôsledku špecifík triedy problémov. Napríklad pre problém obchodného cestujúceho je definícia odhadu značne zjednodušená (netreba riešiť súvislý lineárny problém).

Metóda vetvenia a väzby má výhody oproti metóde rezu:

hromadenie chýb je menej významné, pretože riešenie prechádza rôznymi vetvami;

keď je proces riešenia nútený zastaviť, pravdepodobnosť získania celočíselného výsledku je vysoká, ale bez stanovenia jeho optimality;

pri riešení súvislých úloh sa veľkosti simplexných tabuliek nezväčšujú.

Nevýhody metódy vetvenia a viazania:

Nie je možné odhadnúť počet úloh, ktoré bude potrebné vyriešiť. Čím je počiatočná hodnota záznamu zdola a odhad kritéria úlohy zhora bližšie k požadovanej optimálnej hodnote kritéria, tým menej vrcholov bude mať rozhodovací strom a tým aj náklady na zdroje. Preháňanie počiatočného záznamu však môže viesť k neriešiteľnosti problému, čo treba mať vždy na pamäti.

Absencia znaku optimality. Optimálne riešenie je možné získať dlho predtým, ako sa algoritmus zastaví, ale vo všeobecnom prípade sa to nedá zistiť. Optimalita nastane až po vyčerpaní zoznamu úloh.

Je zrejmé, že účinnosť metódy stúpa so znižovaním rozsahov hodnôt premenných a počtu neceločíselných premenných pri riešení prvého spojitého problému.

Metóda vetvenia a väzby patrí medzi kombinatorické metódy. Jeho podstata spočíva v usporiadanom vymenovaní možností a zvážení len tých, ktoré sa podľa určitých kritérií ukážu ako perspektívne, a zavrhnutí neperspektívnych možností.

Metóda vetvenia a väzby je nasledovná: množina realizovateľných riešení (plánov) sa nejakým spôsobom rozdelí na podmnožiny, z ktorých každá sa opäť rovnakým spôsobom rozdelí na podmnožiny. Proces pokračuje, kým sa nedosiahne optimálne celočíselné riešenie pôvodného problému.

Algoritmus riešenia:

Najprv pomocou simplexovej metódy alebo metódy umelej bázy nájdeme optimálny plán problému bez zohľadnenia celočíselných premenných. Nech je to plán X 0 . Ak medzi komponentmi tohto plánu nie sú žiadne zlomkové čísla, potom sa nájde požadované riešenie tohto problému a

Ak sú medzi komponentmi plánu X 0 zlomkové čísla, potom X 0 nespĺňa podmienku celého čísla a je potrebné vykonať usporiadaný prechod na nové plány, kým sa nenájde riešenie problému. Ukážme, ako sa to dá urobiť, najprv si všimnime, že F(X 0) F(X) pre akýkoľvek nasledujúci plán X.

Za predpokladu, že nájdený optimálny plán X 0 nespĺňa podmienku celočíselných premenných, predpokladáme teda, že medzi jeho komponentmi sú zlomkové čísla. Nech napríklad premenná nadobudne zlomkovú hodnotu v pláne X 0. Potom v optimálnom celočíselnom pláne bude jeho hodnota aspoň buď menšia alebo rovná najbližšiemu menšiemu celému číslu, alebo väčšia alebo rovná najbližšiemu väčšiemu celému číslu. Stanovením týchto čísel nájdeme simplexovou metódou riešenie dvoch problémov lineárneho programovania:

Poďme nájsť riešenie problémov lineárneho programovania (I) a (II). Je zrejmé, že je tu možný jeden z nasledujúcich štyroch prípadov:

• 1. Jeden z problémov je neriešiteľný a druhý má celočíselný optimálny plán. Potom tento plán a hodnota účelovej funkcie na ňom poskytujú riešenie pôvodného problému.
• 2. Jeden z problémov je neriešiteľný a druhý má optimálny plán, medzi zložkami ktorého sú zlomkové čísla. Potom zvážime druhý problém a v jeho optimálnom pláne vyberieme jednu zo zložiek, ktorej hodnota sa rovná zlomkovému číslu a zostrojíme dve úlohy podobné úlohám (I) a (II).
• 3. Oba problémy sú riešiteľné. Jeden z problémov má optimálny celočíselný plán a optimálny plán druhého problému má zlomkové čísla. Potom vypočítame hodnoty cieľovej funkcie na týchto plánoch a porovnáme ich navzájom. Ak je na celočíselnom optimálnom pláne hodnota cieľovej funkcie väčšia alebo rovná jej hodnote na pláne, medzi komponentmi ktorého sú zlomkové čísla, potom je tento celočíselný plán optimálny pre pôvodný problém a spolu s hodnotou účelová funkcia na ňom dáva požadované riešenie.

Ak je hodnota účelovej funkcie väčšia na pláne, medzi komponentmi ktorého sú zlomkové čísla, potom by sa malo vziať jedno z týchto čísel a pre úlohu, ktorej plán sa uvažuje, je potrebné zostrojiť dve úlohy podobné (I) a (II).

4. Oba problémy sú riešiteľné a medzi optimálnymi plánmi oboch problémov sú zlomkové čísla. Potom vypočítame hodnotu účelovej funkcie na týchto optimálnych plánoch a zvážime problém, pre ktorý je hodnota účelovej funkcie najväčšia. V optimálnom pláne tejto úlohy si vyberieme jednu zo zložiek, ktorej hodnota je zlomkové číslo a zostavíme dve úlohy podobné (I) a (II).

Vyššie opísaný iteračný proces teda možno znázorniť ako strom, na ktorom počiatočný vrchol zodpovedá optimálnemu plánu X 0 problému (1)-(3) a každý vrchol spojený s ním vetvou zodpovedá optimálnym plánom. úloh (I) a (II ). Každý z týchto vrcholov má svoje vetvy. V tomto prípade sa v každom kroku vyberie vrchol, pre ktorý je hodnota funkcie najväčšia. Ak sa v určitom kroku získa plán, ktorý má celočíselné zložky a hodnota funkcie na ňom sa ukáže byť väčšia alebo rovná hodnote funkcie v iných vrcholoch, ktoré je možné vetviť, potom je tento plán optimálnym plánom pôvodný problém celočíselného programovania a hodnota účelovej funkcie na ňom je maximálna .

Takže proces hľadania riešenia problému celočíselného programovania (1)-(4) metódou vetvenia a väzby zahŕňa tieto hlavné kroky:

• 1. Nájdite riešenie problému lineárneho programovania (1)-(3).
• 2. Zostavte dodatočné obmedzenia pre jednu z premenných, ktorej hodnota v optimálnom pláne úlohy (1)-(3) je zlomkové číslo.
• 3. Nájdite riešenie problémov (I) a (II), ktoré sa získajú z úlohy (1)-(3) ako výsledok pridania ďalších obmedzení.
• 4. V prípade potreby vytvorte dodatočné obmedzenia pre premennú, ktorej hodnota je zlomková, formulujte úlohy podobné úlohám (I) a (II) a nájdite ich riešenie. Iteračný proces pokračuje, kým sa nenájde vrchol, ktorý zodpovedá celočíselnému plánu problému (1)-(3) a taký, že hodnota funkcie v tomto vrchole je väčšia alebo rovná hodnote funkcie v iných možných vrcholoch. na vetvenie.

Vyššie opísaná metóda vetvenia a väzby má jednoduchšiu logickú schému výpočtu ako Gomoriho metóda. Preto sa vo väčšine prípadov táto metóda používa na hľadanie riešenia konkrétnych problémov celočíselného programovania pomocou počítača.

celočíselné programovanie úloha cestujúci obchodník batoh

Úvod

Veľká trieda aplikovaných optimalizačných problémov je zredukovaná na problémy celočíselného programovania. Na vyriešenie týchto problémov sa široko používajú kombinatorické metódy založené na usporiadanom vymenovaní najsľubnejších možností. Metódy kombinatorického riešenia možno rozdeliť do dvoch skupín: metódy dynamického programovania a metódy vetvenia a väzby.

Pri riešení problémov multidimenzionálnej optimalizácie sa navrhuje spoločná aplikácia vetvených a viazaných metód a dynamického programovania. V prvej fáze sa problém rieši metódou dynamického programovania samostatne pre každé z obmedzení. Postupnosti získané ako výsledok riešenia funkčnej rovnice dynamického programovania sa ďalej používajú na odhad hornej (dolnej) hranice cieľovej funkcie. V druhej fáze je problém vyriešený metódou vetvenia a väzby. Pri použití tejto metódy sa určí metóda na rozdelenie celej množiny platných možností do podmnožín, teda metóda na zostavenie stromu možných možností a metóda na odhad hornej hranice cieľovej funkcie.

Komplexná aplikácia metód dynamického programovania a vetiev a hraníc umožňuje zvýšiť efektivitu riešenia diskrétnych optimalizačných problémov. Pri riešení problémov s veľkými rozmermi sa na zníženie podmienok optimálnej sekvencie používajú dodatočné medzné podmienky.

1. Odkaz na históriu

Metódu vetvenia a väzby prvýkrát navrhli Land a Doig v roku 1960, aby vyriešili všeobecný problém celočíselného lineárneho programovania. Záujem o túto metódu a vlastne aj jej „znovuzrodenie“ sa spája s prácou Littlea, Murtyho, Sweeneyho a Karla, venujúcej sa problémom obchodných cestujúcich. Odvtedy sa objavilo veľké množstvo prác venovaných metóde vetvenia a väzby a jej rôznym modifikáciám. Takýto veľký úspech sa vysvetľuje tým, že autori ako prví venovali pozornosť šírke možností metódy, všímali si dôležitosť využitia špecifík problému a sami využili špecifiká problému obchodného cestujúceho.

Táto metóda je najvšeobecnejšia spomedzi všetkých metód diskrétneho programovania a nemá žiadne zásadné obmedzenia na jej aplikáciu. Algoritmus vetvenia a väzby je efektívny postup na výpočet všetkých možných celočíselných riešení.

Metóda vetvenia a väzby patrí medzi kombinatorické metódy. Jeho podstata spočíva v usporiadanom vymenovaní možností a zvážení len tých, ktoré sa podľa určitých kritérií ukážu ako perspektívne, a zavrhnutí neperspektívnych možností.

2. Popis metódy

Metóda vetvenia a väzby je založená na myšlienke postupného rozdeľovania množiny realizovateľných riešení do podmnožín. V každom kroku metódy sa kontrolujú prvky partície, aby sa zistilo, či daná podmnožina obsahuje optimálne riešenie alebo nie. Overenie sa vykonáva výpočtom dolného odhadu pre cieľovú funkciu na danej podmnožine. Ak nižšie uvedený odhad nie je menší ako záznam- nájdené najlepšie riešenie, potom môže byť podskupina vyradená. Testovanú podmnožinu je možné vyradiť aj v prípade, keď je možné v nej nájsť najlepšie riešenie. Ak je hodnota účelovej funkcie na nájdenom riešení menšia ako záznam, potom sa záznam zmení. Na konci algoritmu je záznam výsledkom jeho práce.

Ak je možné vyradiť všetky prvky oddielu, záznam je optimálnym riešením problému. V opačnom prípade sa z nevyradených podmnožín vyberie najsľubnejšia podmnožina (napríklad s najnižšou hodnotou dolnej hranice) a rozdelí sa. Opäť sa testujú nové podmnožiny atď.

Pri aplikácii metódy vetvenia a väzby na každý konkrétny problém treba v prvom rade určiť dva jeho najdôležitejšie postupy: 1) vetvenie množiny možných riešení; 2) výpočet dolných a horných odhadov cieľovej funkcie.

2.1 Pravidlá vetvenia

V závislosti od charakteristík úlohy sa na organizáciu vetvenia zvyčajne používa jedna z dvoch metód:

1. vetvenie množiny realizovateľných riešení pôvodného problému D;

2. vetvenie množiny D“ získané z D odstránením celočíselnej podmienky na premenných.

Prvá metóda vetvenia sa zvyčajne používa pri problémoch celočíselného programovania a spočíva vo výbere subdomén možných riešení zafixovaním hodnôt jednotlivých komponentov celočíselných optimalizačných premenných (obr. 1). Na obr. Obrázok 1-a poskytuje geometrickú interpretáciu domény uskutočniteľných riešení úlohy celočíselného programovania, ktorá je určená dvoma lineárnymi obmedzeniami a podmienkami pre nezápornosť premenných, a ktoré sú tvorené vetvením subdomén a na obr. 1-b znázorňuje zodpovedajúcu schému vetvenia.

Druhá metóda vetvenia je všestrannejšia ako prvá. Na realizáciu vetvenia nejakej oblasti D i "týmto spôsobom na D i " sa rieši optimalizačný problém s objektívnou funkciou pôvodného problému a reálnych premenných.

Vetvenie sa vykoná, ak v optimálnom riešení hodnota aspoň jednej celočíselnej premennej podľa pôvodnej formulácie úlohy nie je celočíselná. Z týchto premenných je vybraná jedna, napríklad j - i. Označme jej hodnotu v nájdenom optimálnom riešení x 0 [j]. Hovorí sa, že vetvenie sa uskutočňuje podľa premennej x[j]. Oblasť D i "je rozdelená na dve podoblasti D i1" a D i2" takto:

kde ] je celá časť x 0 [j]

Na obr. 2 podmienečne poskytuje geometrický výklad takéhoto vetvenia.

Ryža. 2. Geometrická interpretácia vetvenia

Je vidieť, že v tomto prípade je časť medzi rovinami novozavedených obmedzení odstránená z oblasti D i ". Pretože premenná x[j] je celočíselná podľa podmienok oblasti realizovateľných riešení pôvodného problému, potom zo subdomény realizovateľných riešení pôvodného problému.D i (D i D i ") v takejto výnimke nie je vylúčené žiadne rozhodnutie.

2.2 Tvorba dolných a horných odhadov účelovej funkcie

Pred začatím diskusie o tejto problematike je potrebné povedať, že je všeobecne akceptované používať metódu vetvenia a väzby pre problém, v ktorom je smer optimalizácie redukovaný na formu minimalizácie. Pre kompaktnosť ďalšieho zápisu a výpočtov napíšeme problém diskrétneho programovania, pre ktorý použijeme metódu vetvenia a väzby, v tejto zovšeobecnenej forme:

kde x je vektor optimalizačných premenných, z ktorých niektoré sú skutočné a niektoré sú celé; f(x) - vo všeobecnom prípade nelineárna účelová funkcia; D je oblasť realizovateľných riešení pre všeobecný problém diskrétneho programovania.

Nižšie odhady cieľovej dikcie v závislosti od zvolenej metódy vetvenia možno určiť buď pre subdomény D i D alebo pre subdomény D i "D" (D i "a D" sa získajú zo zodpovedajúcich množín Di a D odstránenie celočíselných podmienok pre diskrétne premenné).
Dolný odhad účelovej funkcie f(x) na množine D i (alebo D i ") je hodnota:

Výpočet nižších odhadov v každom konkrétnom prípade sa môže vykonať s prihliadnutím na špecifiká riešeného problému. Zároveň, aby odhady plnili svoju funkciu čo najefektívnejšie, mali by byť čo najväčšie, t.j. byť čo najbližšie k skutočným hodnotám min f(x). Je to potrebné predovšetkým preto, aby spodné hranice čo najpresnejšie odrážali reálny vzťah min f(x) na podmnožinách vzniknutých pri vetvení a umožnili nám presnejšie určiť smer ďalšieho hľadania optimálneho riešenia pôvodný problém.

Na obr. 3 je znázornený taký ideálny prípad, keď dolné hranice (spojené prerušovanou čiarou) správne odrážajú pomery medzi skutočnými minimálnymi hodnotami f(x) (spojené prerušovanou čiarou) pre štyri podmnožiny realizovateľných riešení D 1 , D 2, D3, D4.

Jedným z univerzálnych spôsobov výpočtu dolných hraníc je vyriešiť nasledujúci problém:

Takto definované o i je nižší odhad f(x) na D i (alebo D i "), pretože D i D i ".

Ak sa pri riešení úlohy (4) zistí, že, potom pre všeobecnosť budeme predpokladať, že.

Je potrebné poznamenať jednu dôležitú vlastnosť dolných hraníc, a to, že ich hodnoty pre podmnožiny vytvorené počas vetvenia nemôžu byť menšie ako dolná hranica cieľovej funkcie na množine podrobenej vetveniu.

Spolu s dolnou hranicou sa v metóde vetvenia a väzby používajú horné hranice f(x). Spravidla sa počíta len jedna hodnota horného odhadu, ktorá je definovaná ako hodnota účelovej funkcie pre najlepšie nájdené realizovateľné riešenie pôvodného problému. Takáto horná hranica sa niekedy nazýva záznam. Ak je pre riešený problém celkom jednoduché a presné získať horné odhady f(x) pre jednotlivé množiny vytvorené počas vetvenia, potom ich treba v metóde použiť na zníženie výpočtovej náročnosti procesu riešenia. Pri použití jednej hornej hranice sa zvyčajne predpokladá, že jej počiatočná hodnota sa rovná nekonečnu (), pokiaľ, samozrejme, nie je známe jediné možné riešenie pôvodného problému z apriórnych úvah. Pri hľadaní prvého možného riešenia:

Potom, keď sa určí lepšie realizovateľné riešenie, horný odhad sa opraví:

Hodnota horného odhadu sa teda môže v procese riešenia problému iba znižovať.

2.3 Algoritmus vetvenia a viazania

Základné pravidlá algoritmu možno formulovať takto:

1. V prvom rade sa vetveniu podrobí podmnožina s číslom zodpovedajúcim najmenšej hodnote dolného odhadu účelovej funkcie (I je množina čísel všetkých podmnožín, (alebo) umiestnených na koncoch vetiev a ktorých vetvenie ešte nebolo ukončené). Ak je implementovaný vyššie uvedený spôsob vetvenia množín, potom môžu vzniknúť nejasnosti pri výbere komponentu, pozdĺž ktorého je potrebné vykonať ďalší krok vetvenia. Bohužiaľ, otázka „najlepšieho“ spôsobu takéhoto výberu zo všeobecného hľadiska ešte nie je vyriešená, a preto sa v konkrétnych problémoch používajú niektoré heuristické pravidlá.

2. Ak je splnená podmienka pre niektorú i-tú podmnožinu, potom je potrebné zastaviť jej vetvenie, keďže potenciál nájsť dobré riešenie v tejto podmnožine (charakterizuje ich) je horší ako hodnota účelovej funkcie pre skutočné, v tomto časovom bode nájdené, realizovateľné riešenie pôvodného problému (charakterizuje).

3. Vetvenie podmnožiny sa zastaví, ak sa nájde optimálne riešenie v úlohe (4). Je to odôvodnené skutočnosťou, že neexistuje lepšie realizovateľné riešenie ako v tejto podskupine. V tomto prípade sa zvažuje možnosť úpravy.

4. Ak, kde, potom sú splnené podmienky optimálnosti pre doteraz najlepšie prípustné riešenie. Odôvodnenie je rovnaké ako v odseku 2 týchto pravidiel.

5. Po nájdení aspoň jedného realizovateľného riešenia pôvodného problému možno zvážiť možnosť zastavenia činnosti algoritmu s odhadom blízkosti najlepšieho zo získaných realizovateľných riešení k optimálnemu (o hodnotu objektívna funkcia):

2.4 Riešenie úlohy pomocou metódy vetvenia a väzby

celý .

Najprv pomocou simplexovej metódy alebo metódy umelej bázy nájdeme optimálny plán problému bez zohľadnenia celočíselných premenných.

Ak medzi komponentmi tohto plánu nie sú žiadne zlomkové čísla, potom sa nájde požadované riešenie tohto problému.

Ak sú medzi komponentmi plánu zlomkové čísla, potom je potrebné prejsť na nové plány, kým sa nenájde riešenie problému.

Metóda vetvenia a väzby je založená na predpoklade, že náš optimálny neceločíselný plán poskytuje funkčnú hodnotu väčšiu ako akýkoľvek nasledujúci plán prechodu.

Nech premenná v pláne je zlomkové číslo. Potom, optimálne, bude jeho hodnota aspoň buď menšia alebo rovná najbližšiemu menšiemu celému číslu, alebo väčšia alebo rovná najbližšiemu väčšiemu celému číslu.

Stanovením týchto čísel nájdeme simplexovou metódou riešenie dvoch problémov lineárneho programovania

- celý .

celý .

Pri riešení tejto dvojice problémov existujú štyri možné prípady:

1. Jeden z problémov je neriešiteľný a druhý má celočíselný optimálny plán. Potom tento plán a hodnota účelovej funkcie dávajú riešenie pôvodného problému.

2. Jeden z problémov je neriešiteľný a druhý má neceločíselný optimálny plán. Potom zvážime druhý problém a v jeho optimálnom pláne vyberieme jednu zo zložiek, ktorej hodnota sa rovná zlomkovému číslu, a zostrojíme dve úlohy podobné predchádzajúcim.

3. Oba problémy sú riešiteľné. Jeden z problémov má optimálny celočíselný plán a optimálny plán druhého problému má zlomkové čísla. Potom vypočítame hodnoty cieľovej funkcie z plánov a porovnáme ich navzájom. Ak je v celočíselnom optimálnom pláne hodnota cieľovej funkcie väčšia alebo rovná jej hodnote v pláne, medzi komponentmi ktorého sú zlomkové čísla, potom je tento celočíselný plán optimálny pre pôvodný problém a poskytuje požadované riešenie.

4. Oba problémy sú riešiteľné a medzi optimálnymi plánmi oboch problémov sú zlomkové čísla. Potom uvažujeme tú z úloh, pre ktoré je hodnota účelovej funkcie najväčšia. A staviame dve úlohy.

Pri riešení problému teda dostaneme schému:

1. Nájdeme riešenie problému lineárneho programovania bez zohľadnenia celočíselnej hodnoty.

2. Zavádza dodatočné obmedzenia pre zlomkovú zložku plánu.

3. Nájdeme riešenie dvoch problémov s obmedzeniami na komponente.

4. V prípade potreby vybudujeme ďalšie obmedzenia, podľa možných štyroch prípadov získame optimálny celočíselný plán alebo zistíme neriešiteľnosť problému.

Príklad

Poďme nájsť riešenie problému

celý .

Riešenie. Simplexovou metódou nájdeme riešenie bez zohľadnenia celočíselnej hodnoty úlohy.

Zvážte pár nasledujúcich problémov:

Úloha č.1

úloha číslo 2

Prvá úloha má optimálny plán

druhá je nerozpustná.

Skontrolujeme plán prvej úlohy na celé čísla. Táto podmienka nie je splnená, preto zostavujeme nasledujúce úlohy:

Úloha 1.1

a úloha číslo 1.2

Úloha č. 1.2 je neriešiteľná a úloha č. 1.1 má optimálny plán, na ktorom funguje hodnota cieľa.

V dôsledku toho sme zistili, že pôvodný problém celočíselného programovania má optimálny plán a.

3. Riešenie problému cestujúceho predajcu pomocou metódy pobočky a väzby

Uvažujme teraz o triede aplikovaných optimalizačných problémov. V mnohých z nich sa používa metóda vetvenia a väzby. Navrhuje sa zvážiť jeden z najpopulárnejších problémov - problém obchodného cestujúceho. Tu je jej znenie. Existuje niekoľko miest, ktoré sú nejakým spôsobom spojené cestami známej dĺžky; je potrebné zistiť, či existuje cesta, po ktorej je možné každé mesto navštíviť iba raz a zároveň sa vrátiť do mesta, odkiaľ cesta začala („obchvat obchodného zástupcu“), a ak existuje je taká cesta, zriadiť najkratšiu z takýchto ciest.

3.1 Vyjadrenie problému

Podmienku formalizujeme z hľadiska teórie grafov. Mestá budú vrcholmi grafu a cesty medzi mestami budú orientované (nasmerované) okraje grafu, na každom z nich je daná váhová funkcia: váha hrany je dĺžka zodpovedajúcej cesty. Cesta, ktorú treba nájsť, je smerovaný jednoduchý cyklus s minimálnou hmotnosťou v digrafe (pripomeňme si: cyklus sa nazýva preklenutie, ak prechádza všetkými vrcholmi grafu; cyklus sa nazýva jednoduchý, ak prechádza len každým z jeho vrcholov raz; cyklus sa nazýva riadený, ak sa začiatok každej nasledujúcej hrany zhoduje s koncom predchádzajúcej; váha cyklu je súčtom váh jeho hrán; nakoniec sa digraf nazýva úplný, ak obsahuje všetky možné okraje); takéto cykly sa nazývajú aj hamiltonovské.

Je zrejmé, že úplný digraf obsahuje cykly vyššie uvedeného typu. Všimnite si, že stačí zvážiť otázku, či digraf obsahuje hamiltonovský cyklus, ako konkrétny prípad problému obchodného cestujúceho pre úplné digrafy. V skutočnosti, ak daný digraf nie je úplný, potom ho možno doplniť na úplný s chýbajúcimi hranami a každej z pridaných hrán možno priradiť váhu Ґ za predpokladu, že Ґ je „počítačové nekonečno“, t.j. maximum zo všetkých možných čísel v úvahách. Ak teraz nájdeme najjednoduchší hamiltonovský cyklus v novovytvorenom úplnom digrafe, potom ak má hrany s hmotnosťou Ґ, bude možné povedať, že v tomto pôvodnom grafe nie je žiadny „cyklus predavača“. Ak sa v úplnom digrafe ukáže, že najľahší Hamiltonov cyklus má konečnú hmotnosť, potom to bude požadovaný cyklus v pôvodnom grafe.

To znamená, že na vyriešenie problému obchodného cestujúceho stačí pre kompletné digrafy s váhovou funkciou. Sformulujme to teraz v konečnej podobe:

nech je úplný orientovaný graf a je váhová funkcia; nájdite jednoduchý cyklus orientovaný na rozpätie ("cyklus obchodného zástupcu") s minimálnou hmotnosťou.

Nech konkrétne zloženie množiny vrcholov a je váhovou maticou daného digrafu, t.j. , a pre akékoľvek.

Najvhodnejšie je zvážiť metódu pobočky a väzby na riešenie problému obchodného cestujúceho na pozadí konkrétneho príkladu. Pomocou tu zavedenej notácie vykonáme tento popis v nasledujúcej prednáške.

Uveďme si niektoré pojmy. Nech existuje nejaká číselná matica. Vyliať riadok tejto matice znamená vybrať minimálny prvok v riadku (nazýva sa to redukčná konštanta) a odpočítať ho od všetkých prvkov tohto riadku. Je zrejmé, že v dôsledku toho bude v tomto riadku nula na mieste minimálneho prvku a všetky ostatné prvky budú nezáporné. Slová prinášajú maticový stĺpec majú podobný význam.

Slová priniesť maticu po riadkoch znamenajú, že sú dané všetky riadky matice. Slová prinášajú maticu po stĺpcoch majú podobný význam.

Nakoniec slová prinášajú maticu, čo znamená, že matica je najprv zmenšená o riadky a potom zmenšená o stĺpce.

Váha prvku matice je súčet redukčných konštánt matice, ktorý sa získa z danej matice nahradením diskutovaného prvku Ґ. Preto slová najťažšia nula v matici znamenajú, že váha každej nuly je vypočítaná v matici a potom je pevná nula s maximálnou hmotnosťou.

Prejdime teraz k popisu metódy vetvy a väzby na riešenie problému obchodného cestujúceho.

Prvý krok. Opravujeme množinu všetkých zájazdov obchodných cestujúcich (teda všetkých jednoducho orientovaných cyklov). Keďže je graf kompletný, táto množina určite nie je prázdna. Priraďme mu číslo, ktoré bude na tejto množine vyhodnocovacej funkcie hrať úlohu hodnoty: toto číslo sa rovná súčtu redukčných konštánt danej matice váh hrán grafu. Ak je množina všetkých zájazdov obchodného cestujúceho označená G, potom súčet redukčných konštánt váhovej matice je označený j(G). Redukovaná matica váh daného grafu by mala byť zapamätaná; označte ho M1; takže výsledok prvého kroku je:

množina G všetkých kôl obchodného cestujúceho je spojená s číslom j(G) a maticou M 1 .

Druhý krok. Z matice M 1 zvolíme najťažšiu nulu; nechajte ho stáť v klietke; opravíme okraj grafu a rozdelíme množinu G na dve časti: časť pozostávajúcu z obtokov, ktoré prechádzajú cez hranu, a časť pozostávajúcu z obtokov, ktoré cez hranu neprechádzajú.

Priraďte množinu k nasledujúcej matici M 1,1: v matici M 1 nahraďte číslo v bunke znakom Ґ. Potom vo výslednej matici vymažeme riadok číslo i a stĺpec číslo j a zvyšné riadky a stĺpce si ponechajú pôvodné čísla. Nakoniec túto poslednú maticu zredukujeme a zapamätáme si súčet redukčných konštánt. Výsledná redukovaná matica bude matica M 1,1 ; Pripočítame súčet redukčných konštánt práve zapamätaných k j(G) a výsledok, ďalej označený ako j(), je porovnateľný s množinou.

Teraz k množine priradíme aj určitú maticu M 1,2. Aby sme to dosiahli, v matici M 1 nahradíme číslo v bunke Ґ a predstavíme výslednú maticu. Súčet redukčných konštánt sa zapamätá a výslednú maticu označíme M 1,2. K číslu j(G) pripočítajme zapamätaný súčet redukčných konštánt a výsledné číslo, ďalej označované j(), je porovnateľné s množinou.

Teraz si vyberme medzi množinami a tou, na ktorej je funkcia j minimálna (teda tá z množín, ktorej zodpovedá menšie z čísel j() a j()).

Teraz si všimneme, že vo vyššie uvedenej úvahe bol ako počiatočný použitý iba jeden skutočný objekt - matica redukovanej váhy daného digrafu. Podľa nej sa vybrala určitá hrana grafu a skonštruovali sa nové matice, na ktoré sa dá samozrejme aplikovať to isté.

Pri každej takejto opakovanej aplikácii sa zafixuje ďalší okraj grafu. Dohodnime sa na nasledujúcej akcii: pred vymazaním riadku a stĺpca v ďalšej matici je potrebné ich nahradiť číslami Ґ vo všetkých tých bunkách, ktoré zodpovedajú hranám, ktoré zjavne nepatria k tým hamiltonovským cyklom, ktoré prechádzajú predtým vybraným hrany.

K vybranej množine s maticou a číslom j, ktoré je k nej priradené, opakujeme to isté atď., pokiaľ je to možné.

Je dokázané, že výsledkom je súbor pozostávajúci z jedného zájazdu obchodného cestujúceho, ktorého hmotnosť sa rovná ďalšej hodnote funkcie j; teda sú splnené všetky podmienky diskutované v popise metódy vetvenia a väzby.

Potom sa záznam zlepšuje až do prijatia konečnej odpovede.

3.2 Stav problému

Študent Ivanov dostal pokyn, aby niesol niektoré dôležité dokumenty z 12. budovy. Ale, žiaľ, má na to veľmi málo času a ešte sa musí vrátiť. Musíte nájsť najkratšiu cestu. Vzdialenosti medzi objektmi sú uvedené v tabuľke

3.3 Matematický model úlohy

Na vyriešenie problému prideľujeme každému bodu trasy konkrétne číslo: 12. budova - 1, Biely dom - 2, KRK "Premier" - 3, Administratíva - 4 a 5. budova - 5. Podľa toho celkový počet bodov . Ďalej zavedieme alternatívne premenné, ktoré nadobúdajú hodnotu 0, ak prechod z i-teho bodu do j-tého nie je zahrnutý v trase a 1 inak. Podmienky príchodu do každého bodu a výstupu z každého bodu iba raz sú vyjadrené rovnosťami (8) a (9).

Na zabezpečenie kontinuity trasy prídavné n premenné a dodatočné obmedzenia (10).

Celková dĺžka trasy F, ktorý je potrebné minimalizovať, bude napísaný v nasledujúcom tvare:

V našom prípade budú tieto podmienky napísané v nasledujúcom tvare:

3.4 Riešenie úlohy pomocou metódy vetvenia a väzby

obchodný cestujúci hranica úlohy

1) Analýza súboru D.

Nájdeme odhad zdola H. Na tento účel určíme maticu minimálnych vzdialeností v riadkoch (1, kde je vzdialenosť minimálna v rade).

Podobne definujeme maticu minimálnych vzdialeností po stĺpcoch.

Vyberme si počiatočný plán: . Potom je horná hranica:

Je zrejmé, že kde znamená prechod z prvého bodu do j-tého. Zoberme si tieto podmnožiny v poradí.

2) Analýza podskupiny D 12 .

3) Analýza podskupiny D 13 .

4) Analýza podskupiny D 14 .

5) Analýza podskupiny D 15 .

6) Eliminácia neperspektívnych podmnožín.

Podskupiny D 13 a D 15 nie sú sľubné. Pretože , ale potom budeme ďalej uvažovať o podmnožine D 14 .

7) Analýza podskupiny D 142 .

8) Analýza podskupiny D 143 .

9) Analýza podskupiny D 145 .

10) Vylúčenie neperspektívnych podskupín

Podskupina D 143 nie je perspektívna. Pretože , ale potom budeme ďalej uvažovať o podmnožine D 145 .

11) Analýza podskupiny D 1452 .

12) Analýza podskupiny D 1453 .

Optimálne riešenie: .

Teda cesta študenta: 12. budova - Administratíva - 5. budova - Biely dom - KRK Premier - 12. budova.

Bibliografia

1. Abramov L.A., Kapustin V.F. Matematické programovanie. - L.: Vydavateľstvo Leningradskej štátnej univerzity, 1981. -328 s.

2. Alekseev O.G. Komplexná aplikácia diskrétnych optimalizačných metód. - M.: Nauka, 1987. -294 s.

3. Korbut A.A., Finkelgein Yu.Yu. Diskrétne programovanie. M.: Veda. 1969. -240 s

4. Kuznecov Yu.N. atď. Matematické programovanie: Učebnica. - 2. vydanie, prepracované a dodatočné. - M.: Vyššia škola, 1980. -300 s.

5. Papadimitriou H., Steiglitz K. Kombinatorická optimalizácia. Algoritmy a zložitosť. - M.: Mir, 1985. -213 s.

Podobné dokumenty

Technika riešenia úloh vyššej matematiky s využitím teórie grafov, jej podstata a poradie riešenia. Hlavná myšlienka metódy vetvenia a väzby, jej praktická aplikácia na problém. Rozdelenie množiny trás na podmnožiny a jej grafické znázornenie.

úloha, pridané 24.07.2009


Podstata a obsah, základné pojmy a kritériá teórie grafov. Koncept a všeobecná myšlienka problému obchodného cestujúceho. Opis metódy vetvenia a väzby, praktická aplikácia. Príklad použitia tejto metódy pobočky na vyriešenie problému cestujúceho predajcu.

test, pridané 06.07.2011


Metódy riešenia problému obchodného cestujúceho. Matematický model problému obchodného cestujúceho. Littleov algoritmus na nájdenie minimálneho Hamiltonovho obrysu pre graf s n vrcholmi. Riešenie problému obchodného cestujúceho pomocou Kruskalovho algoritmu a "dreveného" algoritmu.

semestrálna práca, pridaná 30.04.2011


Podstata problému obchodného cestujúceho a jeho aplikácia. Všeobecná charakteristika metód na jej riešenie: vyčerpávajúce vyhľadávanie, "chamtivé" metódy, genetické algoritmy a ich zovšeobecnenia. Vlastnosti metódy vetvenia a väzby a určenie najoptimálnejšieho riešenia problému.

semestrálna práca, pridaná 18.06.2011


Matematický model problému. Riešenie transportného problému metódou potenciálov. Hodnota účelovej funkcie. Systém pozostávajúci zo 7 rovníc s 8 neznámymi. Riešenie problémov grafickou metódou. Výber polroviny zodpovedajúcej nerovnosti.

kontrolné práce, doplnené 6.12.2011


Teória dynamického programovania. Koncept optimálnej spodnej stavby. Nezávislá a úplne závislá množina vrcholov. Problém nájdenia maximálnej nezávislej množiny v strome. Bron-Kerboshov algoritmus ako metóda vetiev, hranice pre hľadanie klikov.

abstrakt, pridaný 10.09.2012


Riešenie duálnej úlohy pomocou prvej hlavnej vety teórie duality, grafických a simplexových metód. Matematický model dopravnej úlohy, výpočet základného dopravného plánu metódami severozápadného rohu a minimálneho prvku.

test, pridaný 27.11.2011


Vyjadrenie problému cestujúceho obchodníka a základné algoritmy riešenia. Trasy a cesty. Koncepcie dopravnej siete. Koncept rastúceho oblúka, reťaze, rezu. Floyd-Warshallov algoritmus. Riešenie úlohy analytickou metódou. Vytvorenie aplikácie na vyriešenie problému.

semestrálna práca, pridaná 10.08.2015


Riešenie prvej úlohy, Poissonova rovnica, Greenova funkcia. Okrajové úlohy pre Laplaceovu rovnicu. Výrok hraničných problémov. Greenove funkcie pre Dirichletov problém: trojrozmerný a dvojrozmerný prípad. Riešenie Neumannovej úlohy pomocou Greenovej funkcie, počítačová implementácia.

ročníková práca, pridaná 25.11.2011


Postupnosť riešenia lineárnej okrajovej úlohy. Vlastnosti metódy zametania. Algoritmus metódy konečných rozdielov: konštrukcia mriežky v danej oblasti, nahradenie diferenciálneho operátora. Riešenie SLAE Gaussovou metódou, konečne-diferenčné rovnice.