Descompunerea Danzig-Wolfe
Metoda de descompunere Danzig-Wolfe este o versiune specializată a metodei simplex .
În 1960, George Dantzig și Philip Wolf au dezvoltat o metodă de descompunere pentru rezolvarea problemelor de dimensiuni mari cu o structură matriceală de constrângeri specială [1] .
Această metodă s-a dovedit a fi cea mai eficientă pentru rezolvarea problemelor a căror matrice de constrângeri are o formă bloc-diagonală cu un număr mic de variabile. Cu toate acestea, după cum au arătat studiile ulterioare, metoda este aplicabilă și problemelor de programare liniară cu o matrice generală. Metoda corespunzătoare a fost propusă de D. B. Yudin și E. G. Holstein și se numește programare în bloc .
O caracteristică distinctivă a metodei de descompunere este utilizarea unei probleme de coordonare care, în comparație cu cea inițială, are un număr mic de rânduri și un număr mare de coloane.
Metoda de generare a coloanelor
Este esențial ca soluția problemei de coordonare să nu necesite specificarea explicită a tuturor coloanelor. Ele sunt generate în procesul de utilizare a metodei simplex. Această abordare se numește metoda de generare a coloanei .
Este suficient să poți genera o coloană și să ai o procedură care selectează o coloană pentru a intra în bază.
Adesea o astfel de procedură se reduce la rezolvarea unei anumite subprobleme (nu neapărat programare liniară).
Principiul descompunerii
Lema Fie o mulțime mărginită închisă nevidă în spațiul euclidian și să aibă un număr finit de puncte extreme, care vor fi notate aici . Atunci orice punct al multimii poate fi reprezentat ca o combinatie convexa de puncte extreme ale multimii R, i.e. căci există numere nenegative cu o sumă totală de unu ( ) și astfel încât
(1) .
Lasă sarcina
Maximizați
(2)
![{\displaystyle c[N]x[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8f39a3783ff9ce0c714b5c386dcbb8645450b41)
sub restricții
(3)
![{\displaystyle A[M_{1},N]x[N]=b[M_{1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1b41d485314717f6828acabea7f81e40db588cb)
(patru)
![{\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)
Constrângerile (3) definesc un S simplex, fie punctele sale extreme.
![{\displaystyle z[K]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/407407bf4c3265b42db39d78a0ad6c9929a486fc)
Fie x o soluție admisibilă După lemă
![{\displaystyle x=z[N,K]\cdot \delta [K]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ce77314a217ce5b71eb2efb3b9ba8cf8976c516)
Să substituim ultima expresie în (2) și (3).
Sarcina va lua forma
Maximizați (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)
sub restricții
(7)
![{\displaystyle (A[M_{1},N]\cdot z[N,K])\cdot \delta [K]=D[M_{1},K]\cdot \delta [K]=b[M_ {unu}]}](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)
Această sarcină este echivalentă cu originalul (2)-(5) și se numește sarcina de coordonare .
Are doar rânduri de restricții în comparație cu rândurile problemei inițiale și un număr foarte mare de coloane egal cu numărul de puncte extreme ale mulțimii . Pentru a nu stoca toate aceste coloane în memoria computerului, le vom primi după nevoie, folosind metoda de generare a coloanelor.
Algoritm
Rezolvăm problema (6)-(8) prin metoda simplex folosind metoda generării coloanelor.
Pentru simplitate, presupunem că o soluție de bază admisibilă este deja cunoscută.
Se notează prin constrângere (8), atunci variabilele duale sunt vectorul .
![{\displaystyle d[M_{1}\cup {\delta }]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9c4385be3f461c4e756c35e03bb354f3afebf02)
Pentru a intra în bază, este necesar să găsiți , astfel încât
![{\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)
Astfel, este suficient să găsim m pe care se atinge minimul
(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)
ceea ce echivalează cu rezolvarea problemei
minimiza (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)
sub constrângerile (4) și (5).
Dacă minimul găsit nu este mai mare decât , problema este rezolvată.
![{\displaystyle -d[\delta ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/456783f5de64643a1d183ee91adb264ac9c2b679)
În caz contrar, în bază se introduce coloana corespunzătoare soluției găsite.
![{\displaystyle D[M_{1},k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95050bd3310696fb6bb0e8688f2dc15a87b65a11)
Blocați sarcini
Fie constrângerile (4) să aibă o structură de bloc
![{\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)
Problema (10),(4),(5) este împărțită în subsarcini separate
Găsiți minimul
(unsprezece)
![{\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)
in conditii
(12)
![{\displaystyle A[M_{k},N_{k}]z[N_{k}]=b[M_{k}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28e084307c7621be089fab91f7545840ff39c987)
Note
- ↑ George B. Dantzig; Philip Wolf. Principiul de descompunere pentru programe liniare (nedefinit) // Cercetare operațională. - 1960. - T. 8 . - S. 101-111 .
Literatură
- Hemdy A. Taha. Capitolul 3. Metoda Simplex // Introducere în Cercetarea operațională = Cercetarea operațională: o introducere. - Ed. a VII-a. - M . : „Williams” , 2007. - S. 95-141. — ISBN 0-13-032374-8 .
- Holstein E. G., Yudin D. B. Noi direcții în programarea liniară .. - M .: Radio sovietică, 1966.
- Yudin D. B., Goldstein E. G. Programare liniară (teorie, metode și aplicații). - M .: Nauka, 1969.
| Metode de optimizare | |
|---|---|
| Unidimensional |
|
| Comanda zero | |
| Prima comanda | |
| a doua comanda | |
| Stochastic | |
| Metode de programare liniară | |
Metode de programare neliniară | |