Domov › Nastavení › Optimalizace metodou neurčitých Lagrangeových multiplikátorů. Lagrangeova multiplikační metoda. Ekonomický význam Lagrangeových multiplikátorů. Řešení soustavy nelineárních rovnic o dvou neznámých pomocí nástroje Najít řešení

Optimalizace metodou neurčitých Lagrangeových multiplikátorů. Lagrangeova multiplikační metoda. Ekonomický význam Lagrangeových multiplikátorů. Řešení soustavy nelineárních rovnic o dvou neznámých pomocí nástroje Najít řešení

Jeden z nejznámějších a důležité úkoly dopravní logistika (a třída optimalizačních problémů obecně) – problém cestujícího prodejce(Angličtina "Problém obchodního cestujícího", TSP). Bylo také nalezeno jméno " problém putujícího obchodníka" Podstata problému spočívá v nalezení optimální, tedy nejkratší cesty procházející určitými body jeden po druhém. Například problém cestujícího obchodníka lze použít k nalezení nejziskovější trasy, která vám umožní jednou objet určitá města se svým zbožím a vrátit se do výchozího bodu. Měřítkem ziskovosti trasy bude minimální časčas strávený na cestě, minimální cestovní náklady nebo v nejjednodušším případě minimální délka cesty.

Není známo, kdo a kdy poprvé začal studovat problém obchodního cestujícího, ale byl jedním z prvních, kdo navrhl řešení podobný problém vynikající matematik 19. století. – William Hamilton. Zde budeme zvažovat uzavřenou verzi problému (tj. takovou, kde se nakonec vrátíme k výchozímu bodu) a jeho řešení metoda větvení a vazby.

Obecný plán řešení problému obchodního cestujícího

Chcete-li vyřešit problém s cestujícím prodejcem pomocí metody pobočky a vazby, musíte provést následující: algoritmus(sekvence):

Konstrukce matice s počátečními daty.
Hledání minima po řádcích.
Redukce linky.
Hledání minima podle sloupců.
Redukce sloupců.
Výpočet skóre nulových buněk.
Redukce matice.
Pokud ještě nebyla nalezena úplná cesta, přejděte k bodu 2, pokud ji najdete, přejděte k bodu 9.
Výpočet konečné délky cesty a konstrukce trasy.

Tyto fáze řešení problému cestujícího obchodníka jsou podrobněji popsány níže.

Podrobná metodika řešení problému obchodního cestujícího

Pro lepší pochopení problému nebudeme pracovat s pojmy grafu, jeho vrcholy atd., ale s jednoduchými pojmy a co nejblíže realitě: vrcholy grafu se budou nazývat „města“, tj. hrany, které je spojují, se budou nazývat „silnice“.

Takže metoda řešení problému cestujícího prodejce:

1. Konstrukce matice s počátečními daty

Nejprve je třeba prezentovat délky silnic spojujících města ve formě následující tabulky:

V našem příkladu máme 4 města a tabulka ukazuje vzdálenost z každého města do 3 dalších v závislosti na směru jízdy (protože některé železniční tratě mohou být jednosměrné atd.).

Vzdálenost z města do stejného města je označena písmenem M. Používá se také znak nekonečna. To se děje tak, že tento segment cesty je podmíněně přijat jako nekonečně dlouhý. Pak nebude mít smysl volit pohyb z 1. města do 1., z 2. do 2. atd. jako úsek trasy.

2. Hledání minima po řádcích

Najděte minimální hodnotu v každém řádku ( di) a zapište jej do samostatného sloupce.

3. Redukce strun

Provedeme redukci řádku - od každého prvku v řádku odečteme odpovídající hodnotu nalezeného minima (di).

V důsledku toho bude mít každý řádek alespoň jedna nulová buňka.

4. Hledání minima po sloupcích

5. Redukce sloupu

Od každého prvku matice odečteme odpovídající dj.

V důsledku toho bude mít každý sloupec alespoň jedna nulová buňka.

6. Výpočet skóre nulových buněk

Pro každou nulovou buňku výsledné transformované matice najdeme „ Posouzení" Bude to součet minimálního prvku v řádku a minimálního prvku ve sloupci, ve kterém se nachází tato nulová buňka. To samotné se nebere v úvahu. Dříve nalezené di a dj se neberou v úvahu. Výsledný odhad zapíšeme vedle nuly do závorky.

A tak dále pro všechny nulové buňky:

7. Redukce matice

Vybereme nulovou buňku s nejvyšším skóre. Nahradíme ho výrazem " M" Našli jsme jeden z úseků cesty. Zapíšeme si to (z kterého města se stěhujeme, v našem příkladu od 4. do 2.).

Úplně přeškrtneme ten řádek a ten sloupec, kde byla vytvořena dvě „M“. V odpovídající buňce cesta zpět , vložte další písmeno „M“ (protože se nevrátíme).

8. Pokud ještě nebyla nalezena úplná cesta, přejděte k bodu 2, pokud byla nalezena, přejděte k bodu 9

Pokud jsme ještě nenašli všechny segmenty cesty, vrátíme se k 2 bod a znovu hledat minima v řádcích a sloupcích, provádět jejich redukci, vypočítat odhady nulových buněk atd.

Pokud byly nalezeny všechny segmenty cesty (nebo ještě nebyly nalezeny všechny segmenty, ale zbytek cesty je zřejmý), přejděte k bodu 9 .

9. Výpočet konečné délky cesty a konstrukce trasy

Po nalezení všech úseků cesty je zbývá jen spojit a vypočítat celkovou délku cesty (náklady na cestu po této trase, strávený čas atd.). Délky silnic spojujících města bereme z úplně první tabulky s výchozími údaji.

V našem příkladu je trasa následující: 4 → 2 → 3 → 1 → 4 .

Celková délka cesty: L=30.

Praktická aplikace problému obchodního cestujícího

Praktické aplikace problému obchodního cestujícího jsou poměrně rozsáhlé. Zejména jej lze použít k nalezení nejkratší cesty, když popová skupina objíždí města, nalezení sledu technologických operací, které zajistí nejkratší dobu pro dokončení celého výrobního cyklu atd.

Řešení problému obchodního cestujícího online

Galyautdinov R.R.

Metoda větvení a vazby je jednou z kombinatorických metod. Jeho podstata spočívá v uspořádaném výběru možností a zvažování pouze těch z nich, které se podle určitých kritérií ukáží jako slibné, a zavržení neperspektivních variant.

Metoda větvení a vazby je následující: set přípustná řešení(plány) se nějakým způsobem dělí na podmnožiny, z nichž každá je opět rozdělena na podmnožiny stejným způsobem. Proces pokračuje, dokud není získáno optimální celočíselné řešení původního problému.

Algoritmus řešení:

Zpočátku najdeme simplexní metoda nebo metoda umělý základ optimální plán problému bez zohlednění celočíselného počtu proměnných. Nechť je to plán X 0 . Pokud mezi složkami tohoto plánu nejsou žádná zlomková čísla, pak bylo nalezeno požadované řešení tohoto problému a

Pokud mezi složkami plánu X 0 jsou zlomková čísla, pak X 0 nesplňuje celočíselnou podmínku a je nutné provést uspořádaný přechod na nové plány, dokud se nenajde řešení problému. Ukažme si, jak to lze provést, nejprve si povšimněme, že F(X 0) F(X) pro jakýkoli následující plán X.

Za předpokladu, že nalezený optimální plán X 0 nesplňuje podmínku celočíselných proměnných, předpokládáme tedy, že mezi jeho složkami jsou zlomková čísla. Nechť například proměnná nabývá zlomkové hodnoty ve smyslu X 0. Pak v optimálním celočíselném plánu bude jeho hodnota alespoň buď menší nebo rovna nejbližšímu menšímu celému číslu, nebo větší nebo rovna nejbližšímu většímu celému číslu. Určením těchto čísel najdeme řešení dvou úloh pomocí simplexové metody lineární programování:

Pojďme najít řešení problémů lineárního programování (I) a (II). Je zřejmé, že je zde možný jeden z následujících čtyř případů:

1. Jeden z problémů je neřešitelný a druhý má celočíselný optimální plán. Pak tento plán a smysl Objektivní funkce na něm dávají řešení původního problému.
2. Jeden z problémů je neřešitelný a druhý má optimální plán, mezi jehož složkami jsou zlomková čísla. Poté uvažujeme druhý problém a v jeho optimálním plánu vybereme jednu ze složek, jejíž hodnota se rovná zlomkovému číslu, a sestrojíme dvě úlohy, podobně jako úkoly(I) a (II).
3. Oba problémy jsou řešitelné. Jeden z problémů má optimální celočíselný plán a optimální plán druhého problému má zlomková čísla. Poté vypočítáme hodnoty účelové funkce na těchto plánech a porovnáme je mezi sebou. Pokud je na celočíselném optimálním plánu hodnota účelové funkce větší nebo rovna její hodnotě na plánu, mezi jehož složkami jsou zlomková čísla, pak je tento celočíselný plán optimální pro původní problém a spolu s hodnota účelové funkce na něm, dává požadované řešení.

Pokud je hodnota účelové funkce větší v plánu, mezi jehož složkami jsou zlomková čísla, je třeba vzít jedno z těchto čísel a pro úlohu, jejíž plán se uvažuje, je nutné sestrojit dvě úlohy podobné jako (I) a (II).

4. Oba problémy jsou řešitelné a optimální plány pro oba problémy zahrnují zlomková čísla. Potom na těchto optimálních plánech vypočítáme hodnotu účelové funkce a uvažujeme problém, pro který je hodnota účelové funkce největší. V optimálním plánu této úlohy vybereme jednu ze složek, jejíž hodnota je zlomkové číslo, a sestrojíme dvě úlohy podobné (I) a (II).

Iterační proces popsaný výše lze tedy reprezentovat jako strom, na kterém odpovídá počáteční vrchol optimální plán X 0 problému (1)-(3) a každý vrchol s ním spojený větví odpovídá optimálním plánům problémů (I) a (II). Každý z těchto vrcholů má své vlastní větve. V tomto případě je v každém kroku vybrán vrchol, pro který je hodnota funkce největší. Pokud se v některém kroku získá plán, který má celočíselné složky a hodnota funkce na něm se ukáže být větší nebo rovna hodnotě funkce v jiných vrcholech, které je možné pro větvení, pak tento plán je optimální plán pro původní problém celočíselné programování a hodnota účelové funkce na něm je maximální.

Proces hledání řešení problému celočíselného programování (1)-(4) pomocí metody větví a vazeb tedy zahrnuje následující hlavní fáze:

1. Najděte řešení problému lineárního programování (1)-(3).
2. Make up dodatečná omezení pro jednu z proměnných, jejíž hodnota v optimálním plánu úlohy (1)-(3) je zlomkové číslo.
3. Najděte řešení problémů (I) a (II), které jsou získány z problému (1)-(3) v důsledku přidání dalších omezení.
4. V případě potřeby vytvořte další omezení pro proměnnou, jejíž hodnota je zlomková, formulujte problémy podobné problémům (I) a (II) a najděte jejich řešení. Iterační proces pokračuje, dokud není nalezen vrchol, který odpovídá celočíselnému plánu problému (1)-(3) a takový, že hodnota funkce v tomto vrcholu je větší nebo rovna hodnotě funkce v jiných možných vrcholech. pro větvení.

Výše popsaná metoda větvení a vazby má jednodušší logický obvod výpočty než Gomoriho metoda. Proto se ve většině případů tato metoda používá k nalezení řešení konkrétních problémů celočíselného programování pomocí počítače.

problém celočíselného programování cestovní prodavač batoh

5x 1 + 2x 2 ≤ 14
2x 1 + 5x 2 ≤ 16
x 1 , x 2 – celá čísla
Z = 3x 1 + 5x 2 → max
Řešení najdeme pomocí kalkulačky:
Vytvořme oblast proveditelných řešení, tzn. Vyřešme soustavu nerovnic graficky. K tomu sestrojíme každou přímku a definujeme poloroviny definované nerovnostmi (poloviny jsou označeny prvočíslem).

Hranice regionu proveditelných řešení
Průsečíkem polorovin bude oblast, jejíž bodové souřadnice splňují nerovnosti systému omezení problému.
Označme hranice oblasti polygonu řešení.

Uvažujme účelovou funkci úlohy F = 3x 1 +5x 2 → max.
Sestrojme přímku odpovídající hodnotě funkce F = 0: F = 3x 1 +5x 2 = 0. Tuto přímku posuneme rovnoběžně. Protože nás zajímá maximální řešení, posouváme tedy přímku až do posledního dotyku určené oblasti. Na grafu je tato přímka označena tečkovanou čarou.

Rovný F(x) = konst (1) A (2)
5x 1 + 2x 2 ≤14
2x 1 + 5x 2 ≤16

Po vyřešení soustavy rovnic dostaneme: x 1 = 1,8095, x 2 = 2,4762
F(X) = 3*1,8095 + 5*2,4762 = 17,8095
Optimální hodnota proměnné x 1 =1,81 se ukázala jako neceločíselná.
V prvním z nich se k podmínkám problému 11 přidá podmínka x 1 ≥ 2 a k problému 12 se přidá podmínka x 1 ≤ 1.
Tento postup se nazývá větvení podle proměnné 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)

Rovný F(x) = konst protíná oblast v bodě B. Protože bod B je získán jako výsledek průsečíku přímek (1) A (3) , pak jeho souřadnice splňují rovnice těchto přímek:
5x 1 + 2x 2 ≤14
x 1 ≥2

Jak zjistíme maximální hodnotu účelové funkce:
F(X) = 3*2 + 5*2 = 16

Řešením problému se ukázalo být celé číslo.
Nová hodnota aktuálního záznamu bude F(X) = 16.
Protože nalezený bod je první celočíselné řešení, pak by si měl pamatovat on a odpovídající hodnotu CF. Samotný bod se nazývá aktuální celočíselný záznam nebo jednoduše záznam a optimální hodnota celočíselného problému je aktuální rekordní hodnota. Tato hodnota je spodní hranicí optimální hodnotu původní problém 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)

Oblast možných řešení je mnohoúhelník
Rovný F(x) = konst (2) A (3) , pak jeho souřadnice splňují rovnice těchto přímek:
2x 1 + 5x 2 ≤16
x 1 ≤ 1

Po vyřešení soustavy rovnic dostaneme: x 1 = 1, x 2 = 2,8
Jak zjistíme maximální hodnotu účelové funkce:
F(X) = 3*1 + 5*2,8 = 17

Optimální hodnota proměnné x 2 =2,8 se ukázala jako neceločíselná.
Úkol 12 rozdělíme na dva dílčí úkoly 121 a 122.
V prvním z nich se k podmínkám problému 121 přidá podmínka x 2 ≥ 3 a k problému 122 se přidá podmínka x 2 ≤ 2.
Vyřešme úlohu 121 graficky jako úlohu LP.

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)

Oblastí možných řešení je trojúhelník.
Rovný F(x) = konst protíná oblast v bodě C. Protože bod C je získán jako výsledek průsečíku přímek (2) A (4) , pak jeho souřadnice splňují rovnice těchto přímek:
2x 1 + 5x 2 ≤16
x 2 ≥3

Jak zjistíme maximální hodnotu účelové funkce:
F(X) = 3*0,5 + 5*3 = 16,5

Vyřešme úlohu 122 graficky jako úlohu LP.

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)

Oblast možných řešení je mnohoúhelník
Rovný F(x) = konst protíná oblast v bodě D. Protože bod D je získán jako výsledek průsečíku přímek (3) A (4) , pak jeho souřadnice splňují rovnice těchto přímek:
x 1 ≤ 1
x 2 ≤ 2

Po vyřešení soustavy rovnic dostaneme: x 1 = 1, x 2 = 2
Jak zjistíme maximální hodnotu účelové funkce:
F(X) = 3*1 + 5*2 = 13

Aktuální záznam je Z=16≥13, takže přestaneme větvit z tohoto vrcholu

Úkol 121 jsme rozdělili na dva dílčí úkoly 1211 a 1212.
V prvním z nich se k podmínkám problému 1211 přidá podmínka x 1 ≥ 1 a k problému 1212 se přidá podmínka x 1 = 0.
Vyřešme úlohu 1211 graficky jako úlohu LP.

Problém nemá žádná proveditelná řešení. ODR je prázdný soubor.

Problém 1211 nemá řešení, takže pro něj přerušíme proces větvení.
Vyřešme úlohu 1212 graficky jako úlohu LP.

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)

Oblast možných řešení je mnohoúhelník
Rovný F(x) = konst protíná oblast v bodě D. Protože bod D je získán jako výsledek průsečíku přímek (2) A (7) , pak jeho souřadnice splňují rovnice těchto přímek:
2x 1 + 5x 2 ≤16
x 1 = 0

Jak zjistíme maximální hodnotu účelové funkce:
F(X) = 3*0 + 5*3,2 = 16

Optimální hodnota proměnné x 2 =2,48 se ukázala jako neceločíselná.
Úkol 1 rozdělíme na dva dílčí úkoly 11 a 12.
V prvním z nich se k podmínkám problému 11 přidá podmínka x 2 ≥ 3 a k problému 12 se přidá podmínka x 2 ≤ 2.
Tento postup se nazývá větvení podle proměnné x 2.
Vyřešme úlohu 11 graficky jako úlohu LP.

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

Oblastí možných řešení je trojúhelník.
Rovný F(x) = konst protíná oblast v bodě C. Protože bod C je získán jako výsledek průsečíku přímek (2) A (3) , pak jeho souřadnice splňují rovnice těchto přímek:
2x 1 + 5x 2 ≤16
x 2 ≥3

Po vyřešení soustavy rovnic dostaneme: x 1 = 0,5, x 2 = 3
Jak zjistíme maximální hodnotu účelové funkce:
F(X) = 3*0,5 + 5*3 = 16,5

Vyřešme úlohu 12 graficky jako úlohu LP.

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

Oblast možných řešení je mnohoúhelník
Rovný F(x) = konst protíná oblast v bodě C. Protože bod C je získán jako výsledek průsečíku přímek (1) A (3) , pak jeho souřadnice splňují rovnice těchto přímek:
5x 1 + 2x 2 ≤14
x 2 ≤ 2

Po vyřešení soustavy rovnic dostaneme: x 1 = 2, x 2 = 2
Jak zjistíme maximální hodnotu účelové funkce:
F(X) = 3*2 + 5*2 = 16

Aktuální záznam je Z=16≥16, takže přestaneme větvit z tohoto vrcholu
Optimální hodnota proměnné x 1 =0,5 se ukázala jako neceločíselná.
Úkol 11 rozdělíme na dva dílčí úkoly 111 a 112.
V prvním z nich se k podmínkám problému 111 přidá podmínka x 1 ≥ 1 a k problému 112 se přidá podmínka x 1 = 0.
Vyřešme úlohu 111 graficky jako úlohu LP. Rovný F(x) = konst protíná oblast v bodě D. Protože bod D je získán jako výsledek průsečíku přímek (2) A (6) , pak jeho souřadnice splňují rovnice těchto přímek:
2x 1 + 5x 2 ≤16
x 1 = 0

Po vyřešení soustavy rovnic dostaneme: x 1 = 0, x 2 = 3,2
Jak zjistíme maximální hodnotu účelové funkce:
F(X) = 3*0 + 5*3,2 = 16

Aktuální záznam je Z=16≥16, takže přestaneme větvit z tohoto vrcholu
F(X) = 16
x 1 = 2
x 2 = 2

Strom řešení problému

Úvod

Velká třída aplikovaných optimalizačních problémů se redukuje na problémy celočíselného programování. K řešení těchto problémů se široce používají kombinatorické metody založené na uspořádaném vyhledávání nejslibnějších možností. Metody kombinatorického řešení lze rozdělit do dvou skupin: metody dynamické programování a větvené a vázané metody.

Při řešení vícerozměrných optimalizačních problémů je navržena společná aplikace větvených a vázaných metod a dynamického programování. V první fázi je problém řešen pomocí metody dynamického programování zvlášť pro každé z omezení. Posloupnosti získané jako výsledek řešení funkční rovnice dynamického programování jsou následně použity k odhadu horní (dolní) hranice účelové funkce. Ve druhé fázi je problém řešen pomocí metody větví a vazeb. Při použití této metody je určena metoda pro rozdělení celé sady platných voleb do podmnožin, tedy metoda pro konstrukci stromu možné možnosti a způsob pro odhadování horní meze účelové funkce.

Integrovaná aplikace dynamického programování a metod větvení a vazeb zvyšuje efektivitu řešení diskrétní problémy optimalizace. Při řešení vysokorozměrných problémů, abychom snížili členy optimální sekvence, používáme dodatečné podmínky výstřižek.

1. Historický odkaz

Metodu větvení a vazeb poprvé navrhli Land a Doig v roce 1960 k vyřešení společný úkol celočíselné lineární programování. Zájem o tuto metodu a vlastně i její „znovuzrození“ je spojen s prací Littlea, Murthyho, Sweeneyho a Carell na problému obchodního cestujícího. Od této chvíle se to objevilo velké číslo práce věnované metodě větvení a vázanosti a jejím různým modifikacím. Tak velký úspěch je vysvětlen tím, že autoři jako první upozornili na šíři možností metody, upozornili na důležitost využití specifik problému a sami využili specifika problému obchodního cestujícího.

Tato metoda je nejobecnější ze všech metod diskrétního programování a nemá žádná zásadní omezení aplikace. Algoritmus metody větví a vazeb je efektivní postup výčet všech možných celočíselných řešení.

2. Popis metody

Metoda větvení a vazby je založena na myšlence postupného rozdělení množiny proveditelných řešení do podmnožin. V každém kroku metody se kontrolují prvky oddílu, aby se určilo, zda daná podmnožina obsahuje optimální řešení nebo ne. Ověření se provádí výpočtem nižšího odhadu pro cílovou funkci na dané podmnožině. Pokud spodní odhad není menší než záznam- nalezeno nejlepší řešení, pak může být podmnožina vyřazena. Zaškrtnutou podmnožinu lze také zahodit, pokud ji lze najít nejlepší řešení. Pokud je hodnota účelové funkce na nalezeném řešení menší než záznam, pak se záznam změní. Na konci algoritmu je záznam výsledkem jeho práce.

Pokud je možné vyřadit všechny prvky oddílu, pak je záznam optimálním řešením problému. Jinak se z nevyřazených podmnožin vybere ta nejslibnější (například s nejnižší hodnotou nižší odhad), a je rozdělena. Nové podmnožiny jsou znovu kontrolovány atd.

Při aplikaci metody větvení a vazby na každý konkrétní problém je třeba nejprve určit její dva nejdůležitější postupy: 1) větvení množiny možné řešení; 2) výpočet dolních a horních odhadů účelové funkce.

2.1 Pravidla větvení

V závislosti na vlastnostech úlohy se k organizaci větvení obvykle používá jedna ze dvou metod:

1. větvení množiny proveditelných řešení původního problému D;

2. větvení množiny D“ získané z D odstraněním podmínky celočíselnosti u proměnných.

První metoda větvení se obvykle používá pro problémy s celočíselným programováním a spočívá v identifikaci subdomén možných řešení fixováním hodnot. jednotlivé komponenty celočíselné optimalizační proměnné (obr. 1). Na Obr. 1-a podává geometrickou interpretaci oblasti přípustných řešení úlohy celočíselného programování, určené dvěma lineárními omezeními a podmínkami pro nezápornost proměnných, a podoblastí tvořenými větvením a na Obr. Obrázek 1-b ukazuje odpovídající schéma větvení.

Druhá metoda větvení je univerzálnější než první. Pro větvení určité oblasti D i " tímto způsobem na D i " je řešen optimalizační problém s cílovou funkcí původní úlohy a reálných proměnných.

Větvení se provádí, pokud v optimálním řešení hodnota alespoň jedné celočíselné proměnné podle původní formulace úlohy není celočíselná. Z těchto proměnných je vybrána jedna, například j - i. Označme jeho hodnotu v nalezeném optimálním řešení x 0 [j]. Říká se, že větvení se provádí pomocí proměnné x[j]. Oblast D i " je rozdělena do dvou podoblastí D i1 " a D i2 " takto:

kde ] je celá část hodnoty x 0 [j]

Na Obr. 2 obvykle poskytuje geometrickou interpretaci takového větvení.

Rýže. 2. Geometrická interpretace větvení

Je vidět, že v tomto případě je z oblasti D i odstraněna část mezi rovinami nově zavedených omezení. Protože proměnná x[j] podle podmínek oblasti přípustných řešení původní úlohy je celé číslo, pak ze subdomény přípustných řešení původní úlohy D i (D i D i ") s takovou výjimkou není vyloučeno žádné rozhodnutí.

2.2 Tvorba dolních a horních odhadů účelové funkce

Před zahájením diskuse o této problematice je třeba říci, že je obecně přijímáno použití metody větví a vazeb pro problém, ve kterém je směr optimalizace redukován na formu minimalizace. Aby byl další zápis a výpočty kompaktnější, napíšeme problém diskrétního programování, pro který použijeme metodu větvení a vazby, v následujícím zobecněném tvaru:

kde x je vektor optimalizačních proměnných, z nichž některé jsou reálné a některé jsou celočíselné; f(x) - in obecný případ nelineární účelová funkce; D je oblast proveditelných řešení obecného problému diskrétního programování.

Nižší odhady cílové dikce v závislosti na zvolené metodě větvení lze určit buď pro podoblasti D i D nebo pro podoblasti D i "D" (D i " a D" se získávají z odpovídajících množin D i a D odstraněním podmínky integerity na diskrétních proměnných).
Dolní odhad účelové funkce f(x) na množině D i (nebo D i ") bude veličina:

Výpočet dolních odhadů v každém konkrétním případě lze provést s přihlédnutím k charakteristikám řešeného problému. Zároveň, aby odhady co nejefektivněji plnily svou funkci, musí být co největší, tzn. být co nejblíže skutečným hodnotám min f(x). To je nutné především proto, aby spodní odhady co nejpřesněji odrážely skutečný vztah min f(x) na podmnožinách vzniklých při větvení a umožnily nám přesněji určit směr dalšího hledání optimálního řešení. původní problém.

Na Obr. Obrázek 3 ukazuje takový ideální případ, kdy spodní odhady (propojené přerušovanou tečkovanou čarou) správně odrážejí vztahy mezi skutečnými minimální hodnoty f(x) (spojeno čárkovanou čarou) pro čtyři podmnožiny proveditelných řešení D 1, D 2, D 3, D 4.

Jeden z univerzální metody Výpočet dolních hranic zahrnuje řešení následujícího problému:

O i definované tímto způsobem je nižší odhad f(x) na D i (nebo D i "), protože D i D i ".

Pokud se při řešení problému (4) zjistí, že, pak pro obecnost budeme předpokládat, že.

Je třeba poznamenat jednu věc důležitý majetek nižších odhadů, což spočívá v tom, že jejich hodnoty pro podmnožiny vzniklé při větvení nemohou být menší než spodní odhad objektivní funkce na větveném souboru.

Společně s dolní hranicí používá metoda větvení a vazby horní hranice f(x). Zpravidla se počítá pouze jedna hodnota horní meze, která je definována jako hodnota účelové funkce pro nejlépe nalezené proveditelné řešení původního problému. Tento horní odhad se někdy nazývá záznam. Pokud je pro řešený problém možné zcela jednoduše a přesně získat horní meze f(x) pro jednotlivé množiny vzniklé při větvení, pak je třeba je použít v metodě ke snížení výpočetní náročnost rozhodovací proces. Při použití jediné horní hranice se obvykle předpokládá, že její počáteční hodnota je rovna nekonečnu (), pokud ovšem z apriorních úvah není známo žádné proveditelné řešení původního problému. Při hledání prvního možného řešení:

Poté, při určování lepšího proveditelného řešení, se horní mez upraví:

Hodnota horního odhadu tak může v procesu řešení problému pouze klesat.

2.3 Větvící a vázaný algoritmus

Základní pravidla algoritmu lze formulovat takto:

1. Nejprve podmnožina s číslem odpovídajícím nejmenší hodnotu dolní odhad účelové funkce (I je množina čísel všech podmnožin, (nebo) umístěných na koncích větví a jejichž větvení se ještě nezastavilo). Pokud je implementován výše uvedený způsob větvení sad, pak může vzniknout nejednoznačnost ohledně výběru komponenty, podél které musí být proveden další krok větvení. Bohužel otázka „nejlepšího“ způsobu takové volby z obecného hlediska dosud není vyřešena, a proto v r. konkrétní úkoly Používají se některá heuristická pravidla.

2. Je-li pro nějakou i-tou podmnožinu splněna podmínka, pak je nutné její větvení zastavit, protože potenciální možnosti nalezení dobré rozhodnutí v této podmnožině (charakterizuje je) se ukáže být horší než hodnota účelové funkce pro reálnou zjištěnou momentálněčas, přípustné řešení původního problému (charakterizuje).

3. Větvení podmnožiny se zastaví, pokud je nalezeno optimální řešení nalezené v problému (4). To je odůvodněno skutečností, že proto neexistuje lepší proveditelné řešení než v této podmnožině. V tomto případě se zvažuje možnost úpravy.

4. Pokud, kde, pak jsou splněny podmínky optimality pro nejlepší možné řešení nalezené v tuto chvíli. Odůvodnění je stejné jako v odstavci 2 těchto pravidel.

5. Po nalezení alespoň jednoho proveditelného řešení původního problému lze zvážit možnost zastavení algoritmu s posouzením blízkosti nejlepšího z výsledných proveditelných řešení k optimálnímu (na základě hodnoty účelové funkce ):

2.4 Řešení úlohy metodou větvení a vazby

Celý .

Zpočátku najdeme optimální plán problému pomocí simplexové metody nebo metody umělé báze bez zohlednění celočíselného počtu proměnných.

Pokud mezi složkami tohoto plánu nejsou žádná zlomková čísla, pak bylo nalezeno požadované řešení tohoto problému.

Pokud jsou mezi složkami plánu zlomková čísla, je nutné přejít na nové plány, dokud se nenajde řešení problému.

Metoda větvení a vazby je založena na předpokladu, že náš optimální neceločíselný návrh vytváří funkční hodnotu větší než jakýkoli následující návrh větvení.

Nechť proměnná v plánu je zlomkové číslo. Pak v optimálním plánu bude jeho hodnota alespoň buď menší nebo rovna nejbližšímu menšímu celému číslu, nebo větší nebo rovna nejbližšímu většímu celému číslu.

Určením těchto čísel najdeme řešení dvou úloh lineárního programování pomocí simplexní metody

- Celý .

Celý .

Při řešení této dvojice problémů existují čtyři možné případy:

1. Jeden z problémů je neřešitelný a druhý má celočíselný optimální plán. Pak tento plán a hodnota účelové funkce poskytují řešení původního problému.

2. Jeden z problémů je neřešitelný a druhý má neceločíselný optimální plán. Poté zvážíme druhý problém a v jeho optimálním plánu vybereme jednu ze složek, jejíž hodnota se rovná zlomkovému číslu, a sestrojíme dvě úlohy podobné předchozím.

3. Oba problémy jsou řešitelné. Jeden z problémů má optimální celočíselný plán a optimální plán druhého problému má zlomková čísla. Poté vypočítáme hodnoty účelové funkce z plánů a porovnáme je mezi sebou. Jestliže na celočíselném optimálním plánu je hodnota účelové funkce větší nebo rovna její hodnotě na plánu, jehož složky zahrnují zlomková čísla, pak je tento celočíselný plán optimální pro původní problém a poskytuje požadované řešení.

4. Oba problémy jsou řešitelné a optimální plány pro oba problémy zahrnují zlomková čísla. Potom uvažujeme problém, pro který je hodnota účelové funkce největší. A postavíme dva úkoly.

Při řešení problému tedy získáme následující schéma:

1. Najděte řešení problému lineárního programování bez zohlednění celých čísel.

2. Vytváří další omezení pro dílčí složku plánu.

3. Najděte řešení dvou problémů s omezeními na komponentu.

4. V případě potřeby zkonstruujeme další omezení podle možných čtyř případů, získáme optimální celočíselný plán nebo určíme neřešitelnost problému.

Příklad

Pojďme najít řešení problému

Celý .

Řešení. Najdeme řešení bez zohlednění celočíselné hodnoty úlohy pomocí simplexní metody.

Uvažujme další párúkoly:

Úkol č. 1

a úkol č. 2

První problém má optimální plán

druhá je neřešitelná.

Kontrolujeme integritu plánu prvního úkolu. Tato podmínka není splněna, proto zkonstruujeme následující úlohy:

Úkol č. 1.1

a úkol č. 1.2

Úloha č. 1.2 je neřešitelná a úloha č. 1.1 má optimální plán, na kterém funguje hodnota cíle.

V důsledku toho jsme zjistili, že původní problém celočíselného programování má optimální plán a.

3. Řešení problému obchodního cestujícího pomocí metody větve a vazby

Podívejme se nyní na třídu aplikovaných optimalizačních problémů. V mnoha z nich se používá metoda větvení a vazby. Navrhuje se zvážit jeden z nejpopulárnějších problémů - problém cestujícího prodejce. Zde je jeho znění. Existuje několik měst, které jsou nějakým způsobem propojeny silnicemi určité délky; je třeba zjistit, zda existuje cesta, po které lze každé město navštívit pouze jednou a zároveň se vrátit do města, ze kterého cesta začala („objížďka obchodního cestujícího“), a pokud taková cesta existuje, vytvořit nejkratší z těchto cest.

3.1 Problémové prohlášení

Formalizujme podmínku z hlediska teorie grafů. Města budou vrcholy grafu a silnice mezi městy budou orientovanými (nasměrovanými) okraji grafu, na každém z nich je specifikována váhová funkce: hmotnost hrany je délka odpovídající silnice. Cesta, kterou je třeba najít, je orientovaný překlenující jednoduchý cyklus o minimální hmotnosti v digrafu (připomeňme: cyklus se nazývá překlenutí, pokud prochází všemi vrcholy grafu; cyklus se nazývá jednoduchý, pokud prochází každým z jeho vrcholy pouze jednou cyklus se nazývá orientovaný, jestliže se začátek každé následující hrany shoduje s koncem předchozího, nakonec se digraf nazývá úplným; obsahuje všechny možné hrany); takové cykly se také nazývají hamiltonovské.

Je zřejmé, že úplný digraf obsahuje cykly výše uvedeného typu. Všimněte si, že stačí zvážit otázku přítomnosti hamiltonovského cyklu v digrafu jako speciální případ problémy cestujícího obchodníka pro úplné digrafy. Pokud totiž daný digraf není úplný, lze jej doplnit do úplnosti chybějícími hranami a každé z přidaných hran lze přiřadit váhu Ґ, uvážíme-li, že Ґ je „počítačové nekonečno“, tj. maximum ze všech možných čísel. Pokud nyní najdeme nejlehčí Hamiltonův cyklus v nově sestrojeném úplném digrafu, pak pokud má hrany s váhou Ґ, můžeme říci, že v tomto původním grafu není žádný „cyklus cestovního obchodníka“. Pokud se v úplném digrafu ukáže, že nejlehčí hamiltonovský cyklus je hmotnostně konečný, pak to bude požadovaný cyklus v původním grafu.

Z toho vyplývá, že pro kompletní digrafy s váhovou funkcí stačí vyřešit problém obchodního cestujícího. Pojďme si to nyní zformulovat v konečné podobě:

nechť je úplný orientovaný graf a je váhová funkce; najít jednoduchý cyklus orientovaný na překlenutí („cyklus obchodního cestujícího“) s minimální hmotností.

Nechť konkrétní složení množiny vrcholů a je váhovou maticí daného digrafu, tzn. a pro kohokoli.

Zvažování metody pobočky a vazby pro řešení problému obchodního cestujícího se nejpohodlněji provádí na pozadí konkrétní příklad. Pomocí zde představeného zápisu provedeme tento popis v další přednášce.

Pojďme si představit některé pojmy. Nechť existuje nějaká číselná matice. Zmenšit řádek této matice znamená vybrat minimální prvek v řádku (říká se mu redukční konstanta) a odečíst jej od všech prvků tohoto řádku. Je zřejmé, že v důsledku toho bude v tomto řádku minimální prvek nula a všechny ostatní prvky budou nezáporné. Slova „dát maticový sloupec“ mají podobný význam.

Slova přinést matici řádek po řádku znamenají, že jsou uvedeny všechny řádky matice. Slova „zmenšit matici o sloupce“ mají podobný význam.

Konečně slova „redukovat matici“ znamenají, že matice je nejprve zmenšena o řádky a poté o sloupce.

Váha prvku matice je součtem redukčních konstant matice, který se získá z dané matice nahrazením příslušného prvku Ґ. Slova nejtěžší nula v matici tedy znamenají, že se vypočítá váha každé nuly v matici a poté se zafixuje nula s maximální váhou.

Nyní přistoupíme k popisu metody větvení a vazby pro řešení problému obchodního cestujícího.

První krok. Opravujeme množinu všech průchodů obchodního cestujícího (tj. všechny jednoduché orientované cykly). Vzhledem k tomu, že je graf kompletní, tato množina rozhodně není prázdná. Přidružme k němu číslo, které bude na této množině vyhodnocovací funkce hrát roli hodnoty: toto číslo je rovno součtu redukčních konstant dané matice vah hran grafu. Je-li množina všech kol obchodního cestujícího označena G, pak součet redukčních konstant matice hmotnosti je označen j(G). Danou matici vah pro tento graf je třeba si zapamatovat; označme to M 1; Takže výsledek prvního kroku:

množina G všech kol obchodního cestujícího je spojena s číslem j(G) a maticí M 1 .

Druhý krok. Zvolme nejtěžší nulu v matici M 1; nechte ho stát v kleci; zafixujeme hranu grafu a množinu G rozdělíme na dvě části: část skládající se z přechodů, které procházejí hranou, a část skládající se z přechodů, které hranou neprocházejí.

Porovnejme sestavu následující matrice M 1,1: v matici M 1 nahradíme číslo v buňce Ґ. Poté ve výsledné matici proškrtneme číslo řádku i a číslo sloupce j a zbývající řádky a sloupce ponecháme s původními čísly. Nakonec tuto poslední matici zredukujme a zapamatujeme si součet redukčních konstant. Výsledná redukovaná matice bude matice M 1,1; K j(G) přičteme součet právě zapamatovaných redukčních konstant a výsledek, dále označovaný j(), je srovnatelný s množinou.

Nyní k množině přiřadíme i určitou matici M 1,2. Za tímto účelem v matici M 1 nahradíme číslo v buňce Ґ a představíme výslednou matici. Zapamatujme si součet redukčních konstant a výslednou matici označme M 1,2. Připočtěme zapamatovaný součet redukčních konstant k číslu j(G) a výsledné číslo, dále označované j(), je srovnatelné s množinou.

Nyní si mezi množinami vybereme tu, na které je funkce j minimální (tedy množinu, která odpovídá menšímu z čísel j() a j()).

Poznamenejme nyní, že ve výše uvedené úvaze byl jako výchozí použit pouze jeden aktuální objekt - redukovaná matice vah daného digrafu. Pomocí něj byla identifikována určitá hrana grafu a byly sestrojeny nové matice, na které lze samozřejmě aplikovat totéž.

S každou takovou opakovanou aplikací bude zaznamenán další okraj grafu. Pojďme se dohodnout další akce: před smazáním řádku a sloupce v další matici je nutné nahradit Ґ čísla ve všech těch buňkách, které odpovídají hranám, které zjevně nepatří k těm hamiltonovským cyklům, které procházejí dříve vybranými hranami.

Totéž zopakujeme pro vybranou množinu s maticí as ní spojeným číslem j atd., dokud to bude možné.

Je dokázáno, že výsledkem je množina skládající se z jednoho kola obchodního cestujícího, jehož váha je rovna další hodnotě funkce j; tím jsou splněny všechny podmínky diskutované při popisu metody větvení a vazby.

Poté je záznam vylepšován, dokud není získána konečná odpověď.

3.2 Stav problému

Student Ivanov byl pověřen, aby některé zničil důležité dokumenty z 12. budovy. Ale jako štěstí má na to velmi málo času a stále se musí vracet. Musíme najít nejkratší cestu. Vzdálenosti mezi objekty jsou uvedeny v tabulce

3.3 Matematický modelúkoly

Abychom problém vyřešili, přiřadíme každému bodu trasy konkrétní číslo: 12. budova - 1, Bílý dům - 2, KRK "Premier" - 3, Administrativa - 4. a 5. budova - 5. Podle toho celkový počet bodů. Dále zavedeme alternativní proměnné, které nabývají hodnoty 0, pokud přechod z i-tého bodu do j-tého není zahrnut v trase a 1 jinak. Podmínky příjezdu do každého bodu a výstupu z každého bodu jsou vyjádřeny pouze jednou rovností (8) a (9).

Aby byla zajištěna kontinuita trasy, další n proměnné a další omezení (10).

Celková délka trasy F, který je třeba minimalizovat, bude zapsán v následujícím tvaru:

V našem případě budou tyto podmínky sepsány v následující podobě:

3.4 Řešení úlohy metodou větvení a vazby

úkol travelling salesman branch boundary

1) Analýza souboru D.

Najdeme nižší odhad N. Za tímto účelem definujeme matici minimálních vzdáleností po řádku (1, kde je vzdálenost v řadě minimální).

Podobně definujeme matici minimálních vzdáleností podél sloupců.

Zvolme počáteční plán: . Pak je horní hranice:

Je zřejmé, že kde znamená přechod z prvního bodu do j-tého. Zvažme tyto podmnožiny v pořadí.

2) Analýza podmnožiny D 12 .

3) Analýza podmnožiny D 13 .

4) Analýza podmnožiny D 14 .

5) Analýza podmnožiny D 15 .

6) Vyřazení neperspektivních podskupin.

Podmnožiny D 13 a D 15 jsou neperspektivní. Protože , ale pak budeme dále uvažovat podmnožinu D 14.

7) Analýza podmnožiny D 142 .

8) Analýza podmnožiny D 143 .

9) Analýza podmnožiny D 145 .

10) Vylučování neperspektivních podskupin

Podmnožina D 143 je neperspektivní. Protože , ale pak budeme dále uvažovat o podmnožině D 145.

11) Analýza podmnožiny D 1452 .

12) Analýza podmnožiny D 1453 .

Optimální řešení: .

Cesta studenta: 12. budova - Administrativa - 5. budova - Bílý dům - KRK Premier - 12. budova.

Bibliografie

1. Abramov L.A., Kapustin V.F. Matematické programování. - L.: Nakladatelství Leningradské státní univerzity, 1981. -328 s.

2. Alekseev O.G. Integrovaná aplikace diskrétních optimalizačních metod. - M.: Nauka, 1987. -294 s.

3. Korbut A.A., Finkelgein Yu.Yu. Diskrétní programování. M.: Věda. 1969. -240 s

4. Kuzněcov Yu.N. atd. Matematické programování: Tutorial. - 2. vyd., přepracováno a doplněno. - M.: postgraduální škola, 1980. -300 s.

5. Papadimitriou H., Steiglitz K. Kombinatorická optimalizace. Algoritmy a složitost. - M.: Mir, 1985. -213 s.

Podobné dokumenty

Metody řešení problémů vyšší matematiky s využitím teorie grafů, její podstata a postup řešení. Hlavní myšlenkou metody větvení a vazby je praktické využití k úkolu. Rozdělení množiny tras na podmnožiny a její grafické znázornění.

úkol, přidáno 24.07.2009

Podstata a obsah, základní pojmy a kritéria teorie grafů. Koncepce a hlavní myšlenka o problému obchodního cestujícího. Popis větvené a vázané metody, praktická aplikace. Příklad použití tato metoda pobočky k vyřešení problému cestujícího prodejce.

test, přidáno 06.07.2011

Metody řešení problému obchodního cestujícího. Matematický model problému obchodního cestujícího. Littleův algoritmus pro nalezení minimální hamiltonovské kontury pro graf s n vrcholy. Řešení problému obchodního cestujícího pomocí Kruskalova algoritmu a „dřevěného“ algoritmu.

práce v kurzu, přidáno 30.04.2011

Podstata problému obchodního cestujícího, jeho aplikace. obecné charakteristiky metody jeho řešení: metoda úplné vyhledávání, "chamtivé" metody, genetické algoritmy a jejich zobecnění. Vlastnosti metody větví a vazeb a určení nejoptimálnějšího řešení problému.

práce v kurzu, přidáno 18.06.2011

Matematický model problému. Řešení dopravní problém potenciální metodou. Hodnota objektivní funkce. Systém sestávající ze 7 rovnic s 8 neznámými. Řešení problému grafická metoda. Výběr poloroviny odpovídající nerovnosti.

test, přidáno 6.12.2011

Teorie dynamického programování. Koncept optimální spodní stavby. Nezávislá a zcela závislá množina vrcholů. Problém najít maximum nezávislá sada ve stromě. Bron-Kerboschův algoritmus jako metoda větvení pro hledání klik.

abstrakt, přidáno 10.09.2012

Řešení duální problém pomocí první základní věty teorie duality, grafických a simplexových metod. Matematický model dopravní úlohy, výpočet referenční plán způsoby dopravy severozápadní roh a minimální prvek.

test, přidáno 27.11.2011

Vyjádření problému obchodního cestujícího a základní algoritmy řešení. Cesty a cesty. Koncepty dopravní síť. Koncept rostoucího oblouku, řetězu, řezu. Floyd-Warshellův algoritmus. Řešení problému analytická metoda. Vytvoření aplikace k vyřešení problému.

práce v kurzu, přidáno 10.8.2015

Řešení prvního problému, Poissonovy rovnice, Greenova funkce. Okrajové úlohy pro Laplaceovu rovnici. Výrok okrajových úloh. Greenovy funkce pro Dirichletův problém: trojrozměrné a dvourozměrné případy. Řešení Neumannovy úlohy pomocí Greenovy funkce, implementace na počítači.

práce v kurzu, přidáno 25.11.2011

Posloupnost řešení lineární okrajové úlohy. Vlastnosti metody sweep. Algoritmus metody konečných rozdílů: síťování dané oblasti, výměna diferenciálního operátoru. Řešení SLAE Gaussovou metodou, konečně-diferenční rovnice.

Úvod

Při zvažování řady problémů je nutné vzít v úvahu požadavek, aby použité proměnné byly celočíselné. Metody řešení problémů lineárního programování nezaručují integritu řešení.

Někdy se problémy celočíselného lineárního programování řeší přibližně. Chcete-li to provést, vyřešte problém bez zohlednění celočíselných hodnot proměnných a ve výsledném optimálním řešení jsou výsledky zaokrouhleny na nejbližší celočíselné hodnoty. Použití takových řešení je přípustné v situacích, kdy jsou hodnoty proměnných dostatečně velké a zaokrouhlovací chybu lze zanedbat. Pokud jsou hodnoty proměnných malé, pak zaokrouhlení může vést k výraznému rozdílu od optimálního řešení.

Jedna z nejpoužívanějších metod řešení celočíselné problémy je metoda větví a vazeb, poprvé navržená Landem a Doigem v roce 1960.

lineární programování na hranici větve

Metoda větvení a vazby

Algoritmus větvení a ohraničení zahrnuje rozklad původního problému lineárního programování (LPP) na sekvenci problémů obsahujících další omezení proměnných, které jsou následně optimalizovány.

1. Proces začíná řešením úlohy pomocí simplexní nebo grafické metody bez zohlednění požadavku na celočíselnou hodnotu proměnných. Tento problém se nazývá ZLP-0. Pokud jsou všechny proměnné optimálního plánu celá čísla, pak je tento plán optimální i pro problémy celočíselného programování.

2. Pokud některá proměnná neobdržela celočíselnou hodnotu, provede se větvení do dvou nových úloh ZLP-1, ZLP-2. Jeden z Úkoly ZLP-1 představuje problém ZLP-0 doplněný o omezení, kde je celá část čísla. Druhý je tvořen přidáním omezení k problému ZLP-0. Je třeba poznamenat, že výběr celočíselné proměnné lze libovolně určit takto:

vzestupné nebo sestupné indexy;

proměnná představuje důležité rozhodnutí učiněné v rámci daného problému;

koeficient v účelové funkci pro tuto proměnnou výrazně převyšuje všechny ostatní.

3. Úlohy ZLP-1 a ZLP-2 jsou řešeny samostatně. Větev končí, pokud je oblast možných řešení prázdná nebo její optimální řešení je celé celé číslo. V opačném případě je potřeba odbočit z bodu 2 a označit následující počty úkolů ZLP v přirozeném pořadí ZLP-3, ZLP-4.

Proces řešení lze znázornit jako strom, ve kterém odpovídá vrchol ZLP-0 k původnímu plánuřešení problému a každý z vrcholů s ním spojených větví odpovídá optimálnímu plánu pro další problém.

Zvažte následující příklad. Maximalizujte objektivní funkci

pod omezeními

Použijme grafickou metodu k vyřešení problému lineárního programování.

1. Pojďme se rozhodnout původní problém bez zohlednění požadavku celočíselných proměnných.

Označme tento lineární problém Programování ZLP-0.

Na obrázku 1.1 je mnohoúhelník řešení tohoto problému zvýrazněn stínováním. Maximální hodnota je dosaženo v bodě Řešení není celé číslo.

Dalším krokem metody větvení a vazby je větvení podél jedné z celočíselných proměnných, které mají zlomkovou hodnotu, např. K tomu přidáme dvě nová omezení k problému ZLP-0 a Tato omezení odstraní interval =, ve kterém nejsou celočíselné hodnoty. V procesu větvení tak vznikají dvě nové úlohy ZLP-1 a ZLP-2.

Obrázek 1.1 Řešení problému ZLP-0

2. Vyřešme problém ZLP-1 graficky.

Obrázek 1.2 ukazuje platná oblastÚkoly ZLP-1. V bodě je dosaženo maximální hodnoty. Řešení problému je neceločíselné.

Obrázek 1.2 Řešení problému ZLP-1

3. Vyřešme problém ZLP-2 graficky.

V v tomto případě sada možných řešení je prázdná (obrázek 1.2). Systém omezení je nekonzistentní a problém ZLP-2 lze z dalšího uvažování vyloučit.

Obrázek 1.3 Řešení problému ZLP-2

Nyní pokračujme ve studiu problému ZLP-1, protože hodnota není celá. Udělejme ještě jednu větev zavedením omezení a. Výsledkem jsou dva nové problémy ZLP-3 a ZLP-4.

Oblíbené v kategorii: