Telekommunikatsiya texnologiyalari davlat toshkent axborot texnologiyalari universiteti nukis filiali

Uchinchi bosqich. Bu bosqichda matritsaning ekvivalent matritsaga o`zgarishi roy beradi.
Birinchi bosqich ikkinchi xolat bilan tugadi deylik. Minimal elementni belgilaymiz:
h <sub>=</sub> min{h<sup>'</sup> ,h<sup>''</sup> }, (4.5.5)
Bu erda matritsaning belgilanmagan polojitel`n_ыy elementlari ichida eng minimali C_k ; h^'' - matritsaning ikki martadan belgilangan maxfiy elementlari orasida eng minimali.

Belgilanmagan qatorda joylashgan matritsa elementlaridan h – ni olib tashlaymiz (olamiz) va belgilangan ustunda joylashgan elementiga qo`shamiz matritsa olinadi. Agar ikki martadan belgilangan (otritsatel`n_ыy) matritsa elementi noliga aylansa (stanovitsa), unda ustun ustidagi belgilangan belgi yo`qotiladi, element o`zi esa yulduzcha bilan belgilanadi. Qolgan belgilarni esa, shuningdek nolntng barcha (turlarini) belgilarini matritsadan matritsaga o`tkaziladi.

Keyin, ni ga almashtirib yana belgini yana birinchi bosqichni o`tiladi. Agar birinchi bosqich yana ikkinchi natija bilan yakunlansa, unda yana uchinchi bosqichga qaytaradi. Birinchi va uchinchi bosqichlardan iborat tsikllarni, ularni oxirgisi 1-chi yoki 3-chi natija (yo`l) bilan tuguguncha qadar o`tkaziladi. Birinchi natijada (yo`lda pexod), iteratsiyani tugatib, 2-chi bosqichga o`tiladi, uchinchi natijada (yo`lda) esa, ularning shartlarining sig`maganligi (kelishmaganligi) tufayti masalaning echilmasligi haqida xulosa chiqariladi.
4.5.1. Misol. Quyidagi shartlari bilan belgilangan – masalani Venger metodi (usuli) bilan yechish.

1 4 2 5
a2 a3 b1 b2 b3 b4
C =32 12 41 13 P = 6; 3; 3; 4; 2; 4; 2_;
-
Oldingi (predvaritel`n<sub>ы</sub>y) bosqich. matritsani tuzamiz:
1 4 2 5 0 3 1 4
C =2 1 4 1 →C = 1 0 3 0=C <sup>'</sup> =C<sub>0</sub> .
3 2 1 3 2 1 0 2
Keyin D matritsani hisobga olib matritsani tuzamiz: a<sub>i</sub> δ<sub>i</sub>
ai δi
6 3 x11(0) = mina1 , b1 , d11 = d11 = 3;
3 0 0 0<sup> </sup>
0 1 0 23 0 x22(0) = mina2 , b2 , d 22 = d 22 =1;
X 0 =0 0 1 03 2 x33(0) = d33 =1; b<sub>j</sub> 4 2 42
δj 1 1 3 0 x24 = mina2 − x22(0) , b2 , d 24 = d 24 = 2.
matritsaning – butun emas nollari tepasini bitta nuqta qo`yib belgilab chiqamiz. (nolli emas bog`lanmasliklar) Nol emas bog`lanishga to`g`ri keladigan matritsaning qatorlarini “x” belgisi bilan belgilaymiz.
Birinchi iteratsiya

+
−1 2 0 4
×−

1. 
   3 1 4(1)−
   

C0 =− −→C0 =0 −1 2 0=C1

2. 
   0 3 0⁻_'
   

×2 1 0 2 h =11 0 −1 2
3 0 03 0 0 0^δ3ⁱ
X ₀ =0 1 0→ X ₁ = 0 1 0 20
1
0 0↑ 1θ₁ =10 1 1 0 δ_j 1 0 3 0
∆₁ = 8