Danzig-Wolfe nedbrytning
Danzig-Wolfe-sönderdelningsmetoden är en specialiserad version av simplexmetoden .
År 1960 utvecklade George Dantzig och Philip Wolf en nedbrytningsmetod för att lösa högdimensionella problem med en speciell restriktionsmatrisstruktur [1] .
Denna metod visade sig vara den mest effektiva för att lösa problem vars begränsningsmatris har en blockdiagonal form med ett litet antal variabler. Men som ytterligare studier visade är metoden även tillämpbar på linjära programmeringsproblem med en generell matris. Motsvarande metod föreslogs av D. B. Yudin och E. G. Holstein och kallas blockprogrammering .
Ett utmärkande drag för nedbrytningsmetoden är användningen av ett koordinerande problem , som jämfört med det ursprungliga har ett litet antal rader och ett stort antal kolumner.
Kolumngenereringsmetod
Det är väsentligt att lösningen av det koordinerande problemet inte kräver explicit specifikation av alla kolumner. De genereras i processen med att använda simplexmetoden. Detta tillvägagångssätt kallas kolumngenereringsmetoden .
Det räcker med att kunna generera en kolumn och ha en procedur som väljer en kolumn att lägga in i underlaget.
Ofta reduceras en sådan procedur till att lösa ett specifikt delproblem (inte nödvändigtvis linjär programmering).
Principen för nedbrytning
Lemma Låta vara en icke-tom sluten avgränsad mängd i det euklidiska rummet och ha ett ändligt antal extrempunkter, som kommer att betecknas här . Då kan vilken punkt som helst i mängden representeras som en konvex kombination av extrempunkter i mängden R, dvs. för det finns icke-negativa tal med en totalsumma av ett ( ) och sådant
(1) .
Låt uppgiften
Maximera
(2)
![{\displaystyle c[N]x[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8f39a3783ff9ce0c714b5c386dcbb8645450b41)
under restriktioner
(3)
![{\displaystyle A[M_{1},N]x[N]=b[M_{1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1b41d485314717f6828acabea7f81e40db588cb)
(fyra)
![{\displaystyle A[M_{2},N]x[N]=b[M_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f77d1a8e72eaab9f95aff0f126214e712747d57)
(5)
![{\displaystyle x[N]\geq 0[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0d587a473a0d8aeabbd1bbaf81a17102464efa7)
Restriktioner (3) definierar en simplex S, låt vara dess extrempunkter.
![{\displaystyle z[K]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/407407bf4c3265b42db39d78a0ad6c9929a486fc)
Låt x vara en tillåten lösning Med lemma
![{\displaystyle x=z[N,K]\cdot \delta [K]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ce77314a217ce5b71eb2efb3b9ba8cf8976c516)
Låt oss ersätta det sista uttrycket med (2) och (3).
Uppgiften kommer att ta formen
Maximera (6)
![{\displaystyle (c[N]\cdot z[N,K])\cdot \delta [K]=g[K]\cdot \delta [K]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad9788b15edce688ff47503ee8797231e5454ff1)
under restriktioner
(7)
![{\displaystyle (A[M_{1},N]\cdot z[N,K])\cdot \delta [K]=D[M_{1},K]\cdot \delta [K]=b[M_ {ett}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fcbe04bd91812a7dd8c401ef285aafe0d72a9331)
(8) .
![{\displaystyle \delta [K]\cdot 1[K]=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cc2cbcaf5f02733258d47e20cb72f5e1598db2b)
Denna uppgift är likvärdig med den ursprungliga (2)-(5) och kallas den koordinerande uppgiften .
Den har bara rader med begränsningar jämfört med raderna i det ursprungliga problemet, och ett mycket stort antal kolumner lika med antalet extrempunkter i uppsättningen . För att inte lagra alla dessa kolumner i datorns minne kommer vi att ta emot dem efter behov, med metoden att generera kolumner.
Algoritm
Vi löser problem (6)-(8) med simplexmetoden med kolumngenereringsmetoden.
För enkelhetens skull antar vi att någon tillåten grundlösning redan är känd.
Beteckna med begränsning (8), då är de dubbla variablerna vektorn .
![{\displaystyle d[M_{1}\cup {\delta }]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9c4385be3f461c4e756c35e03bb354f3afebf02)
För att komma in i grunden är det nödvändigt att hitta , sådan att
![{\displaystyle z[N,m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abbaa1f16dd5284a4ca1c3118b5c29aaf45c398b)
![{\displaystyle d[M_{1}]D[M_{1},K]+d[\delta ]<g[m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05ef56c0e442aef4a57e0284457848fc9021f078)
Det räcker alltså att hitta m där miniminivån uppnås
(9)
![{\displaystyle d[M_{1}]A[M_{1},N]\cdot z[N,m]+d[\delta ]-c[N]z[N,m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7263bf53749a620940f37ae0081e6df5081384f5)
vilket motsvarar att lösa problemet
minimera (10)
![{\displaystyle (d[M_{1}]A[M_{1},N]-c[N])\cdot x[N])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00d8941fb3428c7f181453fd6049699acf3bca9d)
under begränsningar (4) och (5).
Om det hittade minimumet inte är större än , är problemet löst.
![{\displaystyle -d[\delta ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/456783f5de64643a1d183ee91adb264ac9c2b679)
Annars läggs kolumnen som motsvarar den hittade lösningen in i basen.
![{\displaystyle D[M_{1},k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95050bd3310696fb6bb0e8688f2dc15a87b65a11)
Blockera uppgifter
Låt begränsningar (4) ha en blockstruktur
![{\displaystyle {\begin{pmatrix}A[M_{1},N_{1}]&0[M_{1},N_{2}]&\cdots &0[M_{1},N_{n}]\\ 0[M_{2},N_{1}]&A[M_{2},N_{2}]&\cdots &0[M_{2},N_{n}]\\\cdots &\cdots &\cdots & \cdots &\\0[M_{n},N_{1}]&0[M_{n},N_{2}]&\cdots &A[M_{n},N_{n}]\\\end{pmatrix }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b69fa29383fcd7fc23ee19cd0885b2361689ec0b)
Uppgift (10),(4),(5) är uppdelad i separata deluppgifter
Hitta minimum
(elva)
![{\displaystyle (d[M_{k}]A[M_{k},N_{k}]-c[N_{k}])z[N_{k}]+d[\delta ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/545fa59651a0d0bb246db9f151fc5b5affa29d70)
under förhållanden
(12)
![{\displaystyle A[M_{k},N_{k}]z[N_{k}]=b[M_{k}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28e084307c7621be089fab91f7545840ff39c987)
Anteckningar
- ↑ George B. Dantzig; Philip Wolf. Nedbrytningsprincip för linjära program (obestämd) // Operations Research. - 1960. - T. 8 . - S. 101-111 .
Litteratur
- Hemdy A. Taha. Kapitel 3. Den enkla metoden // Introduction to Operations Research = Operations Research: An Introduction. - 7:e uppl. - M . : "Williams" , 2007. - S. 95-141. — ISBN 0-13-032374-8 .
- Holstein E. G., Yudin D. B. Nya riktningar inom linjär programmering .. - M . : Sovjetisk radio, 1966.
- Yudin D. B., Goldstein E. G. Linjär programmering (teori, metoder och tillämpningar). - M . : Nauka, 1969.
| Optimeringsmetoder _ | |
|---|---|
| En-dimensionell |
|
| Noll ordning | |
| Första beställning | |
| andra beställning | |
| Stokastisk | |
| Linjära programmeringsmetoder _ | |
| Icke -linjära programmeringsmetoder | |