Telekommunikatsiya texnologiyalari davlat toshkent axborot texnologiyalari universiteti nukis filiali

Uchinchi bosqich. dan ga o`tish qoidasiga binoan, matritsaning ikki marta (ikkilamchi) belgilangan elementlari, ga oshiriladi (ko`paytiriladi); matritsaning belgilanmagan elementlari, - ga kamayadi, bu iatritsaning qolgan elementlari esa avvalgi manolarini saqlab qoladi, bunda .
агар cij(k+1) > 0, унда xij(k+1) = 0;
^_агар c_ij(k+1) < 0, _унда xij(_{k+1) =} dij ; (4.5.11)

Oldingi bosqichda tuzish qoidasi bo`yicha (4.5.11) sharti ga muvofiq. Bu shartni induktsiya metodi (usuli) bilan isbotlaymiz. (4.4.11) tengsizligi bir necha uchun to`g`ri kelishini tasavvur qilamiz va uchun ham ular saqlanib qolishini isbotlaymiz.
Isbotlashning birinchi bo`limi.

matritsada element bo`lsin. Bunda, ko`rinib turibdiki, element bo`ladi. Agar bo`lsa, unda tasavvur bo`yicha , demak
(ham shunday) bo`ladi, sababi zanjirga kirmaydi.

Agar bo`lsa, unda bo`ladi, va belgilangan qator va ustunning kesilishmasida joylashgan bo`ladi. Bu faqat – axamiyatga ega emas (nesushestvenn<sub>ы</sub>y) nol bo`lganda, mumkin demak shunday qilib
kelib chiqadi.
Isbotlashning ikkinchi bo`limi.

Endi element bo`lsin. Shunda parametrini aniqlash qoidasi bo`yicha element . Agar bo`lsa, induktsiya metodi bo`yicha bo`ladi. Agar bo`lsa, unda bu nol belgilanmagan hisoblanadi,
sababi ga o`tishda u kamayadi. Demak, butun nol,. Shunday qilib bo`lganligidan, bo`ladi.
elementlari bo`lganligidan, ular zanjirga kirmaydi, va shuning
uchun o`zgarmaydi. Shunday qilib, (4.5.11) shart isbotlandi.
Endi birinchi bosqichning uchinchi yechimida masala shartlari nesovmestin to`g`ri kelmasligini isbotlaymiz.

- matritsaning ko`pchilik belgilangan pozitsiyalari bo`lsin (deylik) ( – ko`pchilik belgilanmagan pozitsiyalari). Agar, X – (4.5.6), (4.5.7) tengsizliklariga mos keluvchi xosila matritsa bo`lsa
m n t m r n
∑∑ x_ij = ∑ x_ij + ∑ x_ij ≤∑∑ x_ijµ i−1 j=1 (i, j)∈Е1 (ij)∈Е2 µ=1 i=1
_{t r} (4.5.12) d_ij ≤∑ b_jµ+∑ a_iλ+ ∑ d_ij ,
∈Е1 µ=1 λ=1 (i, j)∈Е2
Bunda - matritsadagi belgilangan qatorlarning raqami

- belgilangan poustunlarning raqami. Agar, matritsaning ikki marta belgilangan elementi bo`lsa unga bo`ladi. Unda ekanligini ko`rsatamiz. vaziyati uchun u isbotlandi, vaziyati uchun esa manosi birinchi bosqichdagi qatorlarni belgilash qoidasidan kelib chiqadi. Shunday qilib, matritsaning ikki marta belgilangan elementiga javob beradi.
Demak
t m r n t r b_jµ (4.5.13)
(i, j)∈Е1 µ=1 i=1 λ=1 j=1 µ=1

Agar matritsaning belgilanmagan elementi bo`lsa, unda bo`ladi (uchinchi yechimning sharti).

Induktsiya metodi bilan ekanligi isbotlandi. bo`lsa va elementi belgilanmasa, unda u butun nol,
Demak,
∑ x<sub>ij</sub><sup>(k)</sup> = ∑ d<sub>ij</sub> (4.5.14)
(i, j) ∈Е1 (i, j) ∈Е2
(4.5.12) – (4.5.14) o`zaro bog`liqlik tengsizlikka olib keladi.
m n m n
. (4.5.15)
i=1 j=1 (i, j) ∈Е1 (i, j) ∈Е2 i=1 j=1
Shart bo`yicha
∆_k = 2∑m a −∑ ∑ x (k ) > 0
 i 
va (4.5.15) tengsizlikga muvofiq
m n
∑ ∑ x_ij <∑ a_i , (4.5.16)
i=1 j=1 i
Demak, (4.5.16) shartlari xech qanday X reja bo`yicha tenglikga o`tib ketmaydi. Bu erda – (4.5.6) – (4.5.8) shartlariga to`g`ri keluvchi xoxlagan matritsa. (4.5.16) tengsizligi – masala shartlariga to`g`ri kelmasligini ko`rsatib turibdi, sababi (4.5.16) matritsada xoxlagan X reja uchun qat`iy tenglik bo`lishi kerak.