a5.pdf
-
Upload
bacaoanu-veronica -
Category
Documents
-
view
217 -
download
0
Transcript of a5.pdf
ŞTIINŢĂ MILITARĂ
REVISTA ACADEMIEI FORŢELOR TERESTRE NR. 3 (43)/ 2006 1
REZOLVAREA PROBLEMELOR DE TRANSPORT SPECIFICE DOMENIULUI MILITAR
Slt. Paul TUDORACHE
Teoria grafurilor, care este un capitol distinct al cercetării operaţionale, s-a dezvoltat recent, având aplicaţii multiple în activitatea de planificare şi analiză economică, industrială, militară etc. Cu ajutorul acesteia s-au realizat modele matematice care permit o reprezentare completă a fenomenelor analizate, care pot fi de următoarea natură: organizarea reţelelor de transport (rutier, feroviar, naval) în care nodurile sunt localităţi sau staţii, posturi de radio emisie-recepţie, circulaţia informaţiilor într-un sistem (reţele informatice), fluxul operaţiilor într-o activitate (industrială, economică, militară etc).
Domeniul militar reprezintă un câmp larg de aplicabilitate a teoriei grafurilor, în scopul soluţionării unor probleme cum sunt transporturile şi organizarea unor activităţi în câmpul tactic (transmisiuni, stabilirea itinerariului de deplasare etc).
O problemă de transport, echilibrată are forma: (1) ( )⎪ xf (2) ⎪
⎪ ≤≤=∑=
miaxj
,
( ) (3) ⎪
ji
(4)
⎪⎪ ∑ ab ij
numită şi forma standard.
( )⎪⎪⎪
⎪
⎩
⎪⎪
⎪⎪
⎨
⎧
∀≥
=
≤≤=
=
∑
∑
∑∑
==
=
= =
jix
njbx
cX
PT
ij
n
j
m
i
m
ij
i
n
ij
m
i
n
jijij
,0
1,
1
min
:
11
1
1
1 1
În cazul în care avem ,atunci introducem coloana (m+1)–
a cu
∑∑==
<n
ii
m
ij ab
11
( ) ;10şi 1,11
1 nicbab mi
m
jj
n
jim ≤≤∀=−= +
==+ ∑∑
ŞTIINŢĂ MILITARĂ
REVISTA ACADEMIEI FORŢELOR TERESTRE NR. 3 (43)/ 2006 2
iar în cazul în care introducem linia (n+1)–a cu ∑∑==
>n
ji
m
ij ab
11
( ) .10 si ,111
1 mjcabb jn
n
ii
m
jjn ≤≤∀=−= +
==+ ∑∑
Din (2) şi (3) avem relaţii cu nm + nm ⋅ necunoscute. Din (4) rezultă că între ecuaţiile (2) şi (3) mai există cel puţin o relaţie, şi atunci rangul matricei sistemului (2) + (3) este cel mult 1−+ nm .
Definiţia 1. Dacă rangul matricei sistemului (2) + (3) este 1−+ nm , iar un program de bază are exact 1−+ nm componente pozitive (restul nule), atunci programul se numeşte nedegenerat.
Pentru început vom prezenta două metode specifice pentru obţinerea unui program de bază; în cazul unui exemplu concret:
1* – Metoda colţului N-V (nord-vest) 2* – Metoda elementului minim pe linie sau coloană. Aplicaţie: Trei unităţi militare şi sunt alimentate cu
carburant de la depozitele teritoriale şi . Costurile unitare de transport, disponibilul ( şi necesarul
21,UU 3U
21, DD 3D)D ( )N sunt date în tabelul de mai jos:
Uj Di 1U 2U 3U ( )D
1D 2 5 3 100 2D 4 2 1 120 3D 7 8 3 70
( )N 80 90 100 290 Observăm că problema este echilibrată. Metoda 1 Metoda colţului N-V (nord-vest) se trece
Deoarece necesarul s-a epuizat, se trece 0 (sau se lasă libere, sau se haşurează) la celelalte căsuţe de pe prima coloană, iar devine
{ } { } .8080,100min,min 11 ==ND 1N
1D 2080100 =− . Obţinem tabelul:
Uj Di 1U 2U 3U ( )D
1D 80 20
2D ///////////
120
ŞTIINŢĂ MILITARĂ
REVISTA ACADEMIEI FORŢELOR TERESTRE NR. 3 (43)/ 2006 3
3D ///////////
70 ( )N 110 100 290
Cu coloanele C şi rămase procedăm la fel. În colţul N-V (căsuţa (1,2) din tabel) înscriem
2 3C{ } { } .20110,20min,min 21 ==ND Deoarece
disponibilul s-a epuizat, se trece 0 în restul căsuţelor de pe prima linie, iar necesarul a devenit
1D2N 9020110 =− . Obţinem tabelul: Uj
Di 1U 2U 3U ( )D
1D 80 20 ///////////
2D ///////////
120
3D ///////////
70 ( )N 90 100 290
Cu căsuţele rămase libere se procedează ca mai sus şi se obţine, în final, programul de bază:
Uj Di 1U 2U 3U ( )D
1D 80 20 0 100 2D 0 90 30 120 3D 0 0 70 70
( )N 80 110 100 290 care este nedegenerat (are 1−+ nm componente; în cazul de faţă
). 3,3 == nmMetoda 2 Metoda minimului pe linie Căutăm costul minim din prima linie; îl găsim pe poziţia .211 =c În
căsuţa respectivă, trecem { } { } 80100,80min,min 11 ==DN . Deoarece s-a epuizat haşurăm celelalte căsuţe ale coloanei ; iar a devenit 100–20 = 80.
1N1C 1D
ŞTIINŢĂ MILITARĂ
REVISTA ACADEMIEI FORŢELOR TERESTRE NR. 3 (43)/ 2006 4
Tabelul s-a transformat în:
Uj Di 1U 2U 3U ( )D
1D 80 20
2D ///////////
120
3D ///////////
70 ( )N 110 100 290
În tabelul rămas, compus din coloanele şi căutăm din nou cel mai mic cost de pe prima linie: găsim
2C 3C313 =c . În căsuţa corespunzătoare
trecem { } { } .20100,20min,min 31 ==ND Deoarece s-a epuizat, haşurăm căsuţele libere din prima linie, iar a devenit 100–20 = 80. Obţinem tabelul:
1D3N
Uj
Di 1U 2U 3U ( )D
1D 80 /////////// 20
2D ///////////
120
3D ///////////
70 ( )N 110 100 290
În continuare procedăm la fel şi obţinem programul de bază:
Uj Di 1U 2U 3U ( )D
1D 80 0 20 100 2D 0 110 10 120 3D 0 0 70 70
( )N 80 110 100 290
ŞTIINŢĂ MILITARĂ
REVISTA ACADEMIEI FORŢELOR TERESTRE NR. 3 (43)/ 2006 5
care este diferit de cel obţinut prin metoda colţului N-V. Lucrurile se petrec la fel dacă căutăm costul minim de transport de pe o coloană.
Pornind de la soluţia iniţială de bază obţinută, vom arăta în continuare cum se verifică optimalitatea ei prin metoda distributivă, modificată de G.B. Dantzig, Charnes şi Cooper.
Considerăm toate costurile ce corespund celor ( )ijc 1−+ nm valori care constitue o soluţie de bază. 0>ijx
Observăm că pentru fiecare se pot determina câte două numere,
, astfel, încât: , ijc
ji vu , ijji cvu =+ ( )njmi ,...,2,1;,...,2,1 == . ( ) 5Sistemul conţine ( )5 ( 1)−+ nm ecuaţii şi ( )nm + necunoscute; el este
deci nedeterminat şi admite o infinitate de soluţii. Va fi suficient să luăm o valoare arbitrară (de exemplu 0=iu ).
Folosind soluţiile sistemului ( )5 , se determină costurile: jiij vuc += ( )6
pentru toate valorile 0=ijx din soluţia de bază. Se poate arăta că dacă ijij cc ≥ , ( )njmi ,...,2,1;,...,2,1 == ,
soluţia este optimă şi conduce la un minim. Condiţia ca X să fie optim revine la faptul că , pentru
nebazici. 0≤−+ ijji cvu
ijxNotând 0ijcşi ∆=−=+ ijijji ccvu , condiţia ca să fie optim devine
, pentru nebazici. Dacă nu toţi X
00 ≥∆ ijx 00 ≥∆ pentru nebazici, se trece la îmbunătăţirea programului:
ijx
Se alege ( )
{ }0min 00,<∆∆=−
jiijrs cc .
Variabila corespunzătoare, nebazică se introduce în bază. Pe linia rsxr , dintr-un bazic trebuie scăzut un , pentru a nu modifica disponibilul
rkx rsx
rD şi atunci pe coloana k, la un bazic trebuie adăugat pentru a nu modifica necesarul , şi în consecinţă, pe linia p la un trebuie scăzut pentru a nu modifica disponibilul .
pkx rsx
kN psx
rsx sDNotând θ=rsx , se formează astfel un ciclu:
ŞTIINŢĂ MILITARĂ
REVISTA ACADEMIEI FORŢELOR TERESTRE NR. 3 (43)/ 2006 6
θθ
θθ
−→↑
+←−
rk
pkps
x
xx
Alegând { }rkps xx ,min=θ ,se obţine o nouă soluţie de bază. Se calculează din nou 0, ∆ijc ş.a.m.d., până în momentul în care nu mai avem
. 00 <∆Toate aceste rezultate se pun într-un tabel specific pe care îl prezentăm
în contextul problemei-exemplu anterioare.
În caseta avem programul de bază determinat cu metoda colţului N-V. Corespunzător acestuia, sistemul
0X0=−+ ijji cvu devine:
0X ijc
vj ui
1v 2v 3v vjui
2 5 4 0∆ Ciclul
1u 80 20 0 /// /// 4 -1 θ−20 θ
2u 90 30 -3 -1 /// /// 5 θ+90
θ+30
3u 70 -1 1 4 /// 6 4
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
=+=+=+=+=+
31252
33
32
22
21
11
vuvuvuvuvu
Punând obţinem 01 =u 1,3,4,5,2 32321 −=−==== uuvvv valori, pe care le-am trecut în prima coloană, respectiv prima linie din caseta ijc . Apoi căsuţele din această casetă, corespunzătoare programului de bază se haşurează, iar celelalte se completează cu valorile ijc corespunzătoare. Se calculează valorile ijij cc −=∆0 , care au fost trecute în căsuţele corespunzătoare.
ŞTIINŢĂ MILITARĂ
REVISTA ACADEMIEI FORŢELOR TERESTRE NR. 3 (43)/ 2006 7
Observăm că 0113 <−=∆ , deci nu este soluţie optimă şi trebuie îmbunătăţită.
0X
Formăm ciclul cu θ şi găsim { }.30,20min=θ Scriem un nou tabel cu noua soluţie găsită pe care am notat-o . 1X
Am obţinut nebazici, deci soluţia este optimă. Observăm că ea coincide cu soluţia de bază determinată cu ajutorul metodei costului minim pe linie.
( )∀>∆ 00 ji, 1X
0X ijc
vj ui
1v 2v 3v vjui
2 4 3 0∆ Ciclul
1u 80 20 0 /// 4 4 /// 1 /// θ−20 θ
2u 110 10 -2 0 /// /// 4 /// θ+90 θ+30
3u 70 0 2 4 /// 5 4 ///
Bibliografie 1. Gibbons, A., Algorithmic Graph Theory, Cambridge University, 1985 2. Gross, L., Yellen, J., Graph Theory and its Applications, CRC Press LLC,1998 3. Rădescu, Nicolae, Rădescu, Eugenia, Probleme de teoria grafurilor, Craiova, Editura
Scrisul Românesc, 1982 4. Voss, Hans-Jurgen, Cycles and Bridges in Graphs. Mathematics and Applications, East
European Series, vol. 49. Kluwer, 1991.