Reja: va φ vektorlar ustun koordinatalari orasidagi boђlanish

R₁=a₁₁ x₁ + a₁₂ x₂ + ... +a_1n x_n ≥o,
R₂=a₂₁ x₁ + a₂₂ x₂ + ... +a_2n x_n≥ o, (S)
. . . . . . .
R_m=a_m1 x₁ + a_m2 x₂ + ... +a_mn x_n≥ o,
tengsizliklar sistemasi
R_m=a_m1 x₁ + a_m2 x₂ + ... +a_mn x_n≥ o. (1)
tengsizlik berilgan bœlib, u (S) sistemaning natijasi bœlsin.
Teorema(Minkovskiy teoremasi). (S) bir jinsli chizišli tengsizliklar sistemasining ќar bir natijasi bu sistemaning manfiymas koeffitsientli chizišli kombinatsiyasidan iboarat bœladi.
Bu teoremani isbotlash uchun šuyidagi teoremani isbotsiz keltiramiz:
Teorema. CHizišli tengsizliklar sistemasi ќamjoysiz bœlishi uchun bu tengsizliklar sistemasining biror chizišli kombinatsiyasi ziddiyatli tengsizlik bœlishi zarur va etarli.
Misol. Ushbu sistemaning ќamjoysiz ekanligini kœrsating.
(S) (T)
ziddiyatli tengsizlik. U ќolda yušoridagi teoremaga asosan berilgan sistema ќamjoysiz sitema bœladi.
Taъrif. CHizišli tengsizliklar sistemasidan nomaъlumlar sonini bittaga kamaytirib tuzilgan yangi sistemani berilgan sistemaga yœldosh sistema deyiladi.
(S) sistemadan
(T)
sistemani ќosil šilamiz. Bundan

sistemani ќosil šilamiz.
Lemma.Yœldosh sistemaning ќar bir tengsizligi berilgan tengsizliklar sistemasining chizišli kombinatsiyasi bœladi.
Isboti. (S) (T); (S^I) yœldosh sistemaning tengsizliklari va tengsizliklardan tuzilgan. Bu tengsizliklar (S) sistema tengsizliklarini musbat songa kœpaytirishdan ќosil bœladi. R_S≥0 esa (S) sistema tengsizliklaridan iborat bœladi. Demak, (S^I) sistema tengsizliklari (S) sistema tengsizliklarining chizišli kombinatsiyasidan iborat bœladi.
Minkovskiy teoremasining isboti. s>0 bœlganda R+s<0 ќam (S) ning natijasi bœladi, chunki (1) ni šanoatlantiruvchi ќar bir echim R+s>0 ni ќam šanoatlantiradi, u ќolda sistema ќamjoysiz bœladi. (S) ning istalgan echimi R+s>0 uchun ќam echim bœlgani uchun
R₁≥0, R₂≥0 , ... ,R_m≥0, -R-s≥0 (2)
sistema ќamjoysiz bœladi. Ikkinchi teoremaga asosan k₁≥0, k₂≥0, ... ,k_m≥0, k≥0 sonlar uchun (2) ning chizišli kombinatsiyasi
k₁P₁+k₂P₂+ ... +k_mP_m+(-P-c)k≥0,
0^.x₁+0^.x₂+ ... +0^.x_m+b=0+b=b≥0 (b<0)
ziddiyatli tengsizlikni ifodalaydi. SHunday šilib ushbu
k₁P₁+k₂P₂+ ... +k_mP_m-kP-kc=0+b
tenglik bajariladi. R₁, R₂, ... ,R_m, P – bir jinsli ifoda bœlgani uchun –kc-b=0 tenglik ќosil bœladi.
b<0 va c>0 dan k>0 ќosil bœladi. Demak,
k₁P₁+k₂P₂+ ... +k_mP_m-kP=0 bœlib, bundan
(3)
tenglik kelib chišadi.
(3) da , chunki k>0 va k_i≥0.
(3) ga asosan (1) tengsizlik (S) sistemaning manfiymas chizišli kombinatsiyasidan iborat bœladi.

Tekshirish savollari

1. 
   Minkovskiy teoremasini bayon šiling.
   
2. 
   CHTS ning ќamjoysizlik alomatini bayon šiling.
   

Tayanch tushunchalar

1. 
   Maydon.
   
2. 
   Sistema natijasi.
   
3. 
   CHTS ning chizišli kombinatsiyasi.
   
4. 
   Ziddiyatli tengsizlik.
   
5. 
   Yœldosh sistema.
   

17-Maъruza

Simpleks metod (2 soat)

Reja:

1. 
   Simpleks metod ќašida tushuncha.
   
2. 
   Simpleks jadvallar.
   

Adabiyot

1. 
   Nazarov R.N., Toshpœlatov B.T., Dœsumbetov A.D. Algebra va sonlar nazariyasi. I šism. T.: Œšituvchi. 1993 y. (298-313 betlar).
   
2. 
   Kulikov L.YA. Algebra i teoriya chisel. M.: Vыssh. shkola. 1979 g. (str. 335-345).
   

CHizišli programmalash masalasini echishning muќim usuli simpleks usulidir. Simpleks usul šuyidagi jarayonni ifodalaydi:

CHeklanish tenglamalar sistemasini
x ₁=b₁-(a_1r+1x_r+1+ ... +a_1nx_n),
x₂=b₂-(a_2r+1x_r+1+ ... +a_2nx_n),
------------------------------- (1)
x_r=b_r-(a_rr+1x_r+1+ ... +a_rnx_n)
kœrinishga (bunda b₁≥0, ... ,b_r≥0) va berilgan chizišli formadagi x₁,...,x_r larni (1) oršali ifodalab, uni
(2)
kœrinishga keltiramiz va bu formaning minimumini topish masalasini šœyamiz.
(2) dagi x₁, ... ,x_r nomaъlumlar tœplami chizišli programmalash masalasining bazisi deyiladi va u M={ x₁, ... ,x_r} kœrinishda belgilanadi. x₁, ... ,x_r larni bazis nomaъlumlar, x_r+1, ... ,x_r larni ozod nomaъlumlar deb ataymiz. Agar x_r+1= ... =x_n=0 bœlsa, (1) dan x₁=b₁≥0, ... ,x_r=b_r≥0 larni ќosil šilamiz. SHunday šilib,
(b₁, b₂, ... ,b_r, 0, 0, ... 0) (3)
echim ќosil bœladi. f ning bu echimdagi šiymati ga teng bœladi.
Šuyidagi ikki ќol rœy berishi mumkin:

1. 
   (2) da ќamma bœlsin. U vaštda f forma x_r+1= ... =x_n=0 shartda minimum šiymatga erishadi.
   
2. 
   (2) da sonlar orasida manfiylari bor bœlsin.
   

Masalan, deylik. U vašta x_r+1= ... =x_j= ... =x_n=0 va x_j>0 deb olib, x_j ning šiymatini orttira borishi ќisobiga ning šiymatini kamaytirish mumkin, lekin bu ishda eќtiyotkorlik kerak, chunki bu ќolda (1) lardan kelib chišadigan
(4)
tenglamalardagi x₁, ... ,x_r larning ќech šaysisi manfiy bœlib šolmasin.
Bu erda ќam šuyidagi ikkita ќol rœy beradi:
A. (4) da ќamma a_1j, ... ,a_rj sonlar musbatmas. U vaštda x_j>0 uchun bœlganidan ga asosan x₁≥b₁≥0,...,x_r≥b_r≥0 bœladi. Demak, da va bœlgani sababli x_j ni cheksiz orttirma berish bilan min f=-∞ ga kelamiz. Bundan esa f formaning minimumga erishmasligi kœrinadi.
B. (4) da a_1j ,a_ij, ... ,a_rj sonlar orasida musbatlari bor. Masalan, a_kj>0 bœlsin. U ќolda x_k=b_k-a_kjx_j da x_j ga dan ortiš šiymat berish mumkin emas, chunki aks ќolda x_k<0 bœlib šoladi. Bunda ≥0 ekanligi ravshan. Bunday kasrlar orasida eng kichigi bœlsin. Bunda a_ij>0 son ќal šiluvchi element deyiladi.
Šisšalik uchun = belgilash kiritaylik. (4) da x_j ni gachagina orttira olamiz, chunki aks ќolda x_j<0 bœlishini kœrdik.
Ozod nomaъlumlarga
x_r+1=...=x_j-1=0, x_j= , x_j+1=...=x_n=0 (5)
šiymatlarni berib, bazis nomaъlumlarni anišlaymiz:
(6)
Endi šuyidagi yangi bazisga œtamiz:
x₁, .. ,x_i-1, x_j, x_i+1, ... ,x_r.
Bunga mos bazis echim (6) va (5) lardan tuziladi, (1) sistema va (2) formani yangi bazisga moslab yozamiz. Buning uchun (1) dagi
x_i=b_i-(a_ir+1x_r+1+...+a_ijx_j+...+a_inx_n)
tenglamani x_j ga nisbatan echamiz, yaъni

va bu ifodani (1) ga šœyib, ќosil bœlgan yangi sistemani
(7)
kœrinishda yoza olamiz. Bu bazisning ifodalarini ga šœyib, uni
(8)
kœrinishga keltiramiz. Bu bilan jarayonning birinchi šadami tugaydi. Keyingi šadam yana shu birinchi šadamni, yaъni (8) va (7) larga nisbatan I yoki II ќolni, undan keyin IIA yoki IIB ni takrorlashdan iborat bœladi va ќ.š.
Misol.
sistema uchun f=1+4x₃+2x₄ formaning minimumi topilsin.
Echish. x₁, x₂- bazis nomaъlumlar, x₃, x₄ esa ozod nomaъlumlar. x₃=x₄=0 da x₁=2, x₂=1 bœladi. SHunday šilib, M bazisning œrinli (2,1,0,0) echimiga ega bœlamiz.
f formaning bu echimga mos šiymati f=1 bœldi. Endi, f da bœlgani uchun I ќolga ega bœlamiz. SHu sababli, f ning minimumi f=1 bœlib, unga mos (2,1,0,0) echim optimaldir.
Biror masalaning echimini simpleks usul yordamida topish bir šancha bosšichlardan iborat ekanligi bizga maъlum. SHu bosšichlarning ќammasini simpleks jadvallar yordamida bajarish mumkin. Buni šuyidagi misolda kœrish mumkin:

sistemaning manfiymas echimlari orasida
f=x₄-x₅
formaga minimum šiymat beruvchi echim topilsin.
Echish.
x ₁+x₄-2x₅=1,
x₂-2x₄+x₅=2,
x₃+3x₄+x₅=3,
f-x₄+x₅=0
sistema tuzamiz.

Bazis nomaъlumlar	Ozod ќadlar	x1	x2	x3	x4	x5
x1	1	1	0	0	1	-2
x2	2	0	1	0	-2	(1)
x3	3	0	0	1	3	1
f forma	0	0	0	0	-1	1

1-jadval
f formaga minimum šiymat beruvchi optimal echimni topish uchun {x₁,x₂,x₃} bazisdan boshša bazisga œtamiz.

a) 1-jadvalda f ga mos keluvchi oxirgi satrda 1>0 element bor. Bu ustunda 1>0, 1>0 elementlar mavjud. Bu elementlar mos ravishda 2,3 satrlarda joylashgan;
b) ajratilgan 1>0, 1>0 elementlar bilan bitta satrda joylashgan ozod ќadlarning shu 1, 1 larga nisbatlarini olamiz, yaъni bœladi;
v) bu nisbatlar eng kichigining maxraji 1 ќal šiluvchi element bœladi. U 1-jadvalda belgilangan.
g) ќal šiluvchi element turgan ustun elementlarini (œzidan boshšalari) nolga aylantiramiz. Buning uchun ќal šiluvchi elementni 2, -1, -1 larga kœpaytirib, mos ravishda 1,3,4 satrlarga šœshamiz. Buning natijasida x₂ joylashgan ustunning tœrtinchi satrda –1 ќosil bœlgani uchun x₂ ni bazisdan chišarib, œrniga x₅ kiritib šuyidagi 2-jadvalni tuzamiz:

Bazis nomaъlumlar	Ozod ќadlar	x1	x2	x3	x4	x5
x1	5	1	2	0	-3	0
x5	2	0	1	0	-2	1
x3	1	0	-1	1	(5)	0
f forma	-2	0	-1	0	1	0

2-jadval

2-jadvalda kœrsatilgandek {x₁, x₅, x₃} yangi bazis ќosil bœladi. 2-jadvalning oxirgi satrida 1>0 element mavjud bœlib, u x₄ joylashgan ustundadir. Bu ustunda 5>0 element bœlib, u ќal šiluvchi element bœladi. Uchinchi satrni 5 ga bœlib, ќosil bœlgan 1>0 elementdan foydalanib, shu element turgan ustun elementlarini nollarga aylantiramiz (œzidan boshša). Natijada šuyidagi 3-jadvalni ќosil šilamiz:

Bazis nomaъlumlar	Ozod ќadlar	x1	x2	x3	x4	x5
x1		1			0	0
x5		0			0	1
x4		0			1	0
f forma		0			0	0

3-jadval

3-jadvalda yangi bazis {x₁,x₅,x₄} bœladi. 3-jadvalning oxirgi satrida birorta ќam musbat element šolmadi. Demak, topilgan ( , 0,0, , ) echim optimal echim bœlib, unga mos keluvchi f formaning minimumi ga, yaъni min f= bœladi.
Tekshirish savollari

1. 
   Simpleks usulni bayon šiling.
   
2. 
   Simpleks jadvallarni misollar oršali tushuntiring.
   

Tayanch tushunchalar.

1. 
   CHizišli tengsizliklar sistemasi.
   
2. 
   CHizišli formaning minimumi.
   
3. 
   Bazis.
   
4. 
   Optimal echim.