Danzig-Wolfe bomlás
A Danzig-Wolfe dekompozíciós módszer a szimplex módszer speciális változata .
1960-ban George Dantzig és Philip Wolf kidolgozott egy dekompozíciós módszert nagydimenziós problémák megoldására speciális kényszermátrix szerkezettel [1] .
Ez a módszer bizonyult a leghatékonyabbnak olyan problémák megoldására, amelyek kényszermátrixának blokk-átlós alakja van, kevés változóval. Amint azonban a további vizsgálatok kimutatták, a módszer általános mátrixú lineáris programozási problémákra is alkalmazható. A megfelelő módszert D. B. Yudin és E. G. Holstein javasolta, és blokkprogramozásnak nevezik .
A dekompozíciós módszer megkülönböztető jellemzője egy koordinációs probléma alkalmazása , amely az eredetihez képest kevés sorból és sok oszlopból áll.
Oszlopgenerálási módszer
Lényeges, hogy a koordinációs probléma megoldásához ne legyen szükség minden oszlop explicit megadására. Ezeket a szimplex módszer segítségével állítják elő. Ezt a megközelítést oszlopgenerálási módszernek nevezik .
Elég, ha tud egy oszlopot generálni, és rendelkezik egy eljárással, amely kiválasztja az oszlopot, amelyet beírhat a bázisba.
Az ilyen eljárás gyakran egy adott részprobléma megoldására redukálódik (nem feltétlenül lineáris programozás).
A dekompozíció elve
Lemma Legyen egy nem üres zárt korlátos halmaz az euklideszi térben, és véges számú szélső pontja van, amelyeket itt jelölünk . Ekkor a halmaz bármely pontja ábrázolható az R halmaz szélsőpontjainak konvex kombinációjaként, azaz. mert vannak nem negatív számok , amelyek összösszege egy ( ) és olyan
(1) .
Hagyja a feladatot
Maximalizálás
(2)
![{\displaystyle c[N]x[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8f39a3783ff9ce0c714b5c386dcbb8645450b41)
korlátozások alatt
(3)
![{\displaystyle A[M_{1},N]x[N]=b[M_{1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1b41d485314717f6828acabea7f81e40db588cb)
(négy)
![{\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)
A (3) megszorítások egy S szimplexet határoznak meg, legyenek a szélső pontjai.
![{\displaystyle z[K]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/407407bf4c3265b42db39d78a0ad6c9929a486fc)
Legyen x egy megengedhető megoldás A lemma szerint
![{\displaystyle x=z[N,K]\cdot \delta [K]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ce77314a217ce5b71eb2efb3b9ba8cf8976c516)
Helyettesítsük be az utolsó kifejezést (2)-be és (3)-ba.
A feladat formát ölt
Maximalizálás (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)
korlátozások alatt
(7)
![{\displaystyle (A[M_{1},N]\cdot z[N,K])\cdot \delta [K]=D[M_{1},K]\cdot \delta [K]=b[M_ {egy}]}](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)
Ez a feladat megegyezik az eredeti (2)-(5) feladattal, és koordinációs feladatnak nevezzük .
Csak sorok korlátozásai vannak az eredeti probléma soraihoz képest, és nagyon sok oszlopa van, amely megegyezik a halmaz szélső pontjainak számával . Annak érdekében, hogy ezeket az oszlopokat ne tároljuk a számítógép memóriájában, szükség szerint fogadjuk őket, oszlopgenerálás módszerével.
Algoritmus
A (6)-(8) feladatot szimplex módszerrel oldjuk meg az oszlopgenerálás módszerével.
Az egyszerűség kedvéért feltételezzük, hogy néhány elfogadható alapmegoldás már ismert.
Jelölje megkötéssel (8), ekkor a kettős változó a vektor .
![{\displaystyle d[M_{1}\cup {\delta }]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9c4385be3f461c4e756c35e03bb354f3afebf02)
Az alap megadásához meg kell találni , olyat, hogy
![{\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)
Így elegendő megtalálni azt az m-t, amelyen elérjük a minimumot
(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)
ami egyenértékű a probléma megoldásával
minimalizálni (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)
(4) és (5) megszorítások mellett.
Ha a talált minimum nem nagyobb, mint , a probléma megoldódott.
![{\displaystyle -d[\delta ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/456783f5de64643a1d183ee91adb264ac9c2b679)
Ellenkező esetben a megtalált megoldásnak megfelelő oszlop kerül be a bázisba.
![{\displaystyle D[M_{1},k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95050bd3310696fb6bb0e8688f2dc15a87b65a11)
Feladatok blokkolása
Legyen a (4) kényszerek blokkszerkezetűek
![{\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{pmátrix }}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b69fa29383fcd7fc23ee19cd0885b2361689ec0b)
A (10), (4), (5) feladat külön részfeladatokra oszlik
Találd meg a minimumot
(tizenegy)
![{\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)
feltételek mellett
(12)
![{\displaystyle A[M_{k},N_{k}]z[N_{k}]=b[M_{k}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28e084307c7621be089fab91f7545840ff39c987)
Jegyzetek
- ↑ George B. Dantzig; Farkas Fülöp. Lineáris programok bontási elve (határozatlan) // Operációkutatás. - 1960. - T. 8 . - S. 101-111 .
Irodalom
- Hemdy A. Taha. 3. fejezet A szimplex módszer // Bevezetés az operációkutatásba = Operations Research: An Introduction. - 7. kiadás - M . : "Williams" , 2007. - S. 95-141. — ISBN 0-13-032374-8 .
- Holstein E. G., Yudin D. B. Új irányok a lineáris programozásban .. - M . : Szovjet rádió, 1966.
- Yudin D. B., Goldstein E. G. Lineáris programozás (elmélet, módszerek és alkalmazások). - M . : Nauka, 1969.
| Optimalizálási módszerek | |
|---|---|
| Egydimenziós |
|
| Nulla sorrend | |
| Első rendelés | |
| másodrendű | |
| Sztochasztikus | |
| Lineáris programozási módszerek | |
| Nemlineáris programozási módszerek | |