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

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 disjunktné podmnožiny Di (tento postup sa nazýva vetvenie) a vypočítať hornú a dolnú hranicu objektívna funkcia na každej z podmnožín. Dolná hranica bude označená Н a horná hranica E. Podľa toho, Hi Eo, potom táto podmnožina neobsahuje optimálny bod a môže byť vylúčená z ďalšej úvahy. Ak je horná hranica Ei H, nahraďte H minim Hi. Ak E = H, potom je problém vyriešený, inak je potrebné pokračovať v postupe vetvenia a vypočítať hornú a dolnú hranicu. V tomto prípade môžu byť všetky alebo len niektoré z podmnožín rozložené v ďalšom kroku, kým sa nedosiahne rovnosť hornej a dolnej hranice, a nie na samostatnej podmnožine, ale pre realizovateľnú 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 tieto dodatočné výpočty vyžadujú veľký počet operácií, potom môže byť účinnosť metódy nízka.

Schéma dynamické programovanie pri prechode z počiatočného bodu do koncového bodu (obr. 5.1) možno chápať 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ú hranicu a deklarovať hodnota účelovej funkcie, ktorá jej zodpovedá ako záznamu. Budovanie množiny stavov 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 vedúcich k akémukoľvek (i-oe) stavu, okrem jedného, ​​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 rozšírenia sa zahodia. Ak sa na určitej trajektórii dosiahne horná hranica a je menšia ako aktuálna hodnota rekordu, dostaneme nový rekord.

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

V skutočnosti, v zjednodušenej forme, sme túto metódu už použili pri riešení problému ochrany povrchu (časť 4.6), keď sme zamietli štáty, pri ktorých bežné náklady prevyšovali celkové náklady na prvotnú aproximáciu. V tomto prípade sú prevádzkové náklady spodnou hranicou, ak predpokladáme, že náklady na celú zostávajúcu cestu sú 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 rovnakým spôsobom, 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. žiadne výpočty.

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

všeobecný popis

Všeobecnú myšlienku metódy možno opísať na príklade nájdenia minima funkcie na množine prípustných hodnôt premennej. Funkcia a premenná môžu mať ľubovoľnú povahu. Metóda vetvenia a väzby vyžaduje dva postupy: vetvenie a hľadanie odhadov (medzí).

Postup vetvenia spočíva v rozdelení množiny prípustných hodnôt premennej na subdomény (podmnožiny) menšie... Postup je možné aplikovať rekurzívne na podoblasti. Výsledné podoblasti tvoria strom tzv vyhľadávací strom alebo konáre stromov a hranice. Uzly tohto stromu sú vytvorené subdomény (podmnožiny množiny hodnôt premennej).

Postup zisťovanie odhadov je nájsť hornú a dolnú hranicu riešenia problému na subdoménach prípustných hodnôt premennej.

Metóda vetvenia a ohraničenia je založená na nasledujúcej myšlienke: ak je spodná hranica hodnôt funkcie v subdoméne vyhľadávacieho stromu väčšia ako horná hranica v niektorej predtým zobrazenej subdoméne, potom ju možno vylúčiť. z ďalších úvah ( pravidlo odpadnutia). Zvyčajne sa minimum získaných horných odhadov zapíše do globálnej premennej; ktorýkoľvek uzol vyhľadávacieho stromu, ktorého spodná hranica je väčšia ako hodnota, môže byť z ďalšieho posudzovania vylúčený.

Ak je spodná hranica pre uzol stromu rovnaká ako Horná hranica, potom je táto hodnota minimom funkcie a je dosiahnutá v zodpovedajúcej subdoméne.

Aplikácia

Metóda sa používa na riešenie niektorých NP-úplných problémov, ako napríklad:

pozri tiež

Poznámky (upraviť)

Nadácia Wikimedia. 2010.

Pozrite sa, čo je „metóda vetvenia a viazania“ v iných slovníkoch:

metóda vetvenia a väzby- - [Ya.N. Luginsky, M.S.Fezi Zhilinskaya, Y.S.Kabirov. Anglický ruský slovník elektrotechniky a elektroenergetiky, Moskva] Predmety elektrotechniky, základné pojmy EN obor a viazaná metóda ... Technická príručka prekladateľa

metóda- metóda: Metóda na nepriame meranie vlhkosti látok, založená na závislosti dielektrickej konštanty týchto látok na ich vlhkosti. Zdroj: RMG 75 2004: Štátny systém zabezpečenie jediného... Slovník-príručka termínov normatívnej a technickej dokumentácie

Optimálna cesta obchodného cestujúceho cez 15 najväčších miest Nemecka. Uvedená trasa je najkratšia zo všetkých možných trás 43 589 145 600. Problém s cestujúcim predajcom (TSP) (Wikipedia

Tento výraz má iné významy, pozri hrubá sila. Úplná hrubá sila (alebo metóda „hrubej sily“, eng. hrubou silou) metóda riešenia matematické problémy... Patrí do triedy metód na nájdenie riešenia vyčerpaním všetkých druhov ... ... Wikipedia

Príklad problému s chrbtom: do batohu je potrebné umiestniť krabice za predpokladu, že kapacita batohu je 15 kg, aby celková využiteľnosť vecí v batohu bola maximálna. Problém s batohom (angl. ... Wikipedia

Problém cestujúceho obchodníka (cestujúceho obchodníka) je jedným z najznámejších problémov kombinatorickej optimalizácie. Úlohou je nájsť najziskovejšiu trasu prechádzajúcu cez uvedené mestá aspoň raz z ... ... Wikipédie

Problém cestujúceho obchodníka (cestujúceho obchodníka) je jedným z najznámejších problémov kombinatorickej optimalizácie. Úlohou je nájsť najziskovejšiu trasu prechádzajúcu cez uvedené mestá aspoň raz z ... ... Wikipédie

Problém cestujúceho obchodníka (cestujúceho obchodníka) je jedným z najznámejších problémov kombinatorickej optimalizácie. Úlohou je nájsť najziskovejšiu trasu prechádzajúcu cez uvedené mestá aspoň raz z ... ... Wikipédie

V tomto článku chýbajú odkazy na zdroje informácií. Informácie musia byť overiteľné, inak môžu byť spochybnené a odstránené. Môžete ... Wikipedia

knihy

• Vývoj softvérového nástroja na nájdenie optimálneho portfólia veľkoobchodných nákupov obchodného podniku A. V. Mishchenko. V rámci tejto práce sme vyvinuli softvérový nástroj vyriešiť problém hľadania optimálneho portfólia veľkoobchodných nákupov podniku maloobchodné... V tomto prípade bola použitá metóda vetvenia a ...

Úvod

Pri zvažovaní množstva problémov je potrebné vziať do úvahy požiadavku, aby použité premenné boli celé číslo. Metódy riešenia problémov lineárne programovanie nezaručujú celočíselnú hodnotu riešenia.

Niekedy sa problémy celočíselného lineárneho programovania riešia približne. Na tento účel sa problém rieši bez zohľadnenia celočíselnej hodnoty premenných, potom sa v získanom optimálnom riešení výsledky zaokrúhlia na najbližšie celočíselné hodnoty. Použitie takýchto riešení je prípustné v situáciách, keď sú hodnoty premenných dostatočne veľké a chybu zaokrúhľovania je možné zanedbať. Ak sú hodnoty premenných malé, zaokrúhľovanie môže viesť k výraznému nesúladu s optimálnym riešením.

Jedna z rozšírených metód riešenia celočíselné problémy je metóda vetvenia a viazania, ktorú prvýkrát navrhli Land a Doig v roku 1960.

vetvové lineárne programovanie

Metóda vetvenia a väzby

Algoritmus vetvenia a väzby zabezpečuje rozklad pôvodný problém lineárne programovanie (LPP) pre postupnosť úloh obsahujúcich dodatočné obmedzenia na premenné, ktoré sa následne optimalizujú.

1. Proces začína riešením úlohy pomocou simplexnej resp graficky bez zohľadnenia požiadavky na celočíselné premenné. Táto úloha sa nazýva ZLP-0. Ak sú všetky premenné optimálneho návrhu celočíselné, potom je tento návrh optimálny aj pre problémy celočíselného programovania.

2. Ak niektorá premenná nezískala celočíselnou hodnotu, vykoná sa rozvetvenie na dve nové úlohy ZLP-1, ZLP-2. Jeden z úlohy LPP-1 je problém ZLP-0 doplnený o obmedzenie, kde - celá časťčísla. Druhý je vytvorený pridaním obmedzenia k problému ZLP-0. Je potrebné poznamenať, že výber celočíselnej premennej možno ľubovoľne určiť takto:

vzostupné alebo zostupné indexy;

premenná predstavuje dôležité rozhodnutie prijaté v rámci tejto úlohy;

koeficient v účelovej funkcii pre túto premennú výrazne prevyšuje všetky ostatné.

3. Úlohy ZLP-1 a ZLP-2 sa riešia samostatne. Vetva končí, ak je oblasť realizovateľných riešení prázdna alebo ak je optimálne riešenieúplne celé číslo. V opačnom prípade je potrebné odbočiť od bodu 2, pričom sa označujú nasledujúce čísla úloh ZLP v prirodzenom poradí ZLP-3, ZLP-4.

Proces riešenia možno znázorniť ako strom, v ktorom vrchol ZLP-0 zodpovedá počiatočnému plánu riešenia problému a každý z vrcholov, ktoré sú s ním spojené vetvou, zodpovedá optimálnemu plánu pre nasledujúci problém.

Zvážte nasledujúci príklad. Maximalizujte účelovú funkciu

s obmedzeniami

Na riešenie úlohy lineárneho programovania použijeme grafickú metódu.

1. Vyriešme pôvodný problém bez toho, aby sme brali do úvahy požiadavku, aby premenné boli celé číslo.

Tento problém označujeme ako lineárny Programovanie ZLP-0.

Na obrázku 1.1 je polygón riešení tohto problému zvýraznený šrafovaním. Maximálna hodnota sa dosiahne v bode Riešenie nie je celé číslo.

Ďalším krokom v metóde vetvenia a väzby je vetvenie cez jednu z celočíselných premenných, ktoré majú napríklad zlomkovú hodnotu. Za týmto účelom pridajte dve nové obmedzenia do problému ZLP-0 a Tieto obmedzenia vymažú interval =, v ktorom nie sú žiadne celočíselné hodnoty. V procese vetvenia tak vznikajú dve nové úlohy ZLP-1 a ZLP-2.

Obrázok 1.1 Riešenie problému ZLP-0

2. Vyriešme úlohu ZLP-1 graficky.

Obrázok 1.2 zobrazuje prípustnú oblasť problému ZLP-1. Maximálna hodnota je dosiahnutá v bode. Riešenie problému je neceločíselné.

Obrázok 1.2 Riešenie problému ZLP-1

3. Vyriešme úlohu ZLP-2 graficky.

V v tomto prípade množina realizovateľných riešení je prázdna (obrázok 1.2). Systém obmedzení je nejednotný a problém ZLP-2 možno vylúčiť z ďalšieho posudzovania.

Obrázok 1.3 Riešenie problému ZLP-2

Teraz budeme pokračovať v štúdiu problému ZLP-1, pretože hodnota nie je celé číslo. Urobme ešte jednu vetvu zavedením obmedzení a. V dôsledku toho získame dve nové úlohy ZLP-3 a ZLP-4.

Metódu vetvenia a väzby prvýkrát navrhli v roku 1960 Land a Doig ako aplikovanú na problém celočíselného lineárneho programovania. Táto práca však nemala výrazný priamy vplyv na vývoj diskrétneho programovania. V skutočnosti je „znovuzrodenie“ metódy vetvenia a viazania spojené s prácou Littlea, Murtyho, Sweeneyho a Carell na probléme obchodného cestujúceho; v tej istej práci bol prvýkrát navrhnutý dnes už všeobecne akceptovaný názov metódy „metóda vetvenia a viazania“. Od tohto momentu veľmi veľké číslo práce venované metóde vetvenia a väzby a jej rôznym modifikáciám. Takýto veľký úspech (a dokonca aj vo vzťahu ku „klasicky ťažkému“ problému obchodného cestujúceho) sa vysvetľuje skutočnosťou, že Little, Murtie, Sweeney a Carell si ako prví všimli šírku metódy vetvenia a viazania, pozn. dôležitosť využitia špecifickosti problému a túto špecifickosť veľmi úspešne využil. ...

V oddiele 1 tejto kapitoly sa uvádza Všeobecná myšlienka metóda vetvenia a väzby; v § 2 - Land a Doigov algoritmus pre problém celočíselného lineárneho programovania, v § 3 - metóda autorov Littlea a kol., pre problém obchodného cestujúceho.

§ 1. Myšlienka vetvy a viazanej metódy

1.1. Uvažujme problém diskrétneho programovania v nasledujúcej všeobecnej forme.

Minimalizovať

za podmienky

Tu je G nejaká konečná množina.

1.2. Metóda vetvenia a väzby je založená na nasledujúcich konštrukciách, ktoré v niektorých prípadoch umožňujú výrazne znížiť množstvo enumerácie.

I. Výpočet dolnej hranice (odhady).

Často je možné nájsť dolnú hranicu (odhad) účelovej funkcie na množine plánov (alebo na niektorej jej podmnožine, t.j. takom počte, že pre

(Podľa toho existuje rozdelenie na podmnožiny (vetvenie). Implementácia metódy je spojená s postupným rozdeľovaním množiny plánov do stromu podmnožín (vetvenie). K rozvetveniu dochádza podľa nasledujúcej viackrokovej schémy.

0. krok. Existuje množina Určitým spôsobom je rozdelená na konečnú početnú (zvyčajne disjunktnú) podmnožinu kroku.Existujú množiny, ktoré ešte neboli rozvetvené. Podľa nejakého pravidla (uvedeného nižšie) sa z nich vyberie množina a rozdelí sa na konečný počet podmnožín:

Sady ešte nie sú rozdelené

sú opätovne menovaní

Niekoľko krokov takéhoto sekvenčného procesu rozdeľovania je schematicky znázornených na obr. 10.1.1.

III. Prepočet známok. Ak súbor potom, samozrejme,

Preto rozdelenie niektorých množín do podmnožín v procese riešenia

V špecifických situáciách sa často ukáže, že je možné zlepšiť odhad, teda získať aspoň časť striktnej nerovnosti

IV. Výpočet plánov. Pre konkrétne úlohy možno špecifikovať rôzne cesty hľadanie plánov v postupne rozvetvených podmnožinách. Každá takáto metóda sa do značnej miery spolieha na špecifiká problému.

V. Kritérium optimálnosti. Nechať byť

a plán X patrí do nejakej podmnožiny Ak navyše

potom X je optimálny plán pre problém (1.1) - (1.2).

Dôkaz vyplýva priamo z definície odhadu.

Zvyčajne sa toto kritérium uplatňuje v určitom štádiu vetvenia (t. j. formálne povedané, pozri bod II).

Vi. Odhad presnosti približného riešenia. Nechať byť

Ak X je nejaký plán pôvodného problému (t.j.), potom

Aj tu dôkaz vyplýva bezprostredne z definície odhadu.

Je zrejmé, že ak je rozdiel malý (to znamená, že nepresahuje určité číslo zvolené pre daný problém), potom X možno brať ako približné riešenie, ako odhad presnosti aproximácie.

1.3. Načrtneme formálnu schému metódy vetvenia a väzby.

0. krok. Vypočítame skóre. Ak je zároveň možné nájsť plán X taký, že

potom X je optimálny plán.

Ak sa nenájde optimálny plán, nejakým spôsobom rozdelíme množinu na konečný počet podmnožín

a prejdite na krok.

1. krok. Vypočítame odhady Ak je v tomto prípade možné nájsť návrh X taký, že pre niektoré a

potom X je optimálny plán.

Ak sa nenájde optimálny plán, potom vyberieme ten „najsľubnejší“. ďalšie štiepenie nastaviť podľa nasledujúceho pravidla:

Množinu rozdelíme na niekoľko (zvyčajne nesúvislých) podmnožín.

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 z nich, ktoré sú z určitých dôvodov sľubné, a zavrhnutí neperspektívnych možností.

Metóda vetvenia a ohraničenia 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äť rozdelí na podmnožiny rovnakým spôsobom. Proces pokračuje, kým sa nezíska optimálne celočíselné riešenie pôvodného problému.

Algoritmus riešenia:

Spočiatku nájdeme simplexná metóda alebo metóda umelý základ 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 dizajnu nie sú žiadne zlomkové čísla, potom sa našlo požadované riešenie tohto problému a

Ak sú medzi zložkami 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ť, keď sme si predtým všimli, že F (X 0) F (X) pre akýkoľvek nasledujúci plán X.

Za predpokladu, že nájdený optimálny návrh X 0 nespĺňa podmienku, že premenné sú celé číslo, predpokladáme teda, že medzi jeho komponentmi sú zlomkové čísla. Napríklad, nech premenná nadobudne zlomkovú hodnotu v zmysle X 0. Potom v optimálnom návrhu celého čísla 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 nerozhodnuteľný a druhý má celočíselný optimálny návrh. 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ý, zatiaľ čo druhý má optimálny dizajn, medzi komponentmi 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é. Jedna z úloh má optimálny celočíselný návrh a optimálny návrh druhej má zlomkové čísla. Potom vypočítame hodnoty cieľovej funkcie na týchto plánoch a porovnáme ich navzájom. Ak na celočíselnom optimálnom pláne je 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 cieľovú funkciu 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é zostaviť dve podobné úlohy až (I) a (II).

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

Vyššie popísaný iteračný proces teda možno znázorniť vo forme nejakého stromu, kde pôvodný vrchol zodpovedá optimálnemu plánu X 0 úlohy (1) - (3) a každý vrchol spojený s ním vetvou zodpovedá optimálne plány problémov (I) a (II ). Každý z týchto vrcholov má svoje vlastné 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 s celočíselnými komponentmi 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é fázy:

• 1. Nájdite riešenie problému lineárneho programovania (1) - (3).
• 2. Ďalšie obmedzenia sú vytvorené 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 ďalšie 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 je taký, že hodnota funkcie v tomto vrchole je väčšia alebo rovná hodnote funkcie v iných vrcholoch. možné na vetvenie.

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

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