Чизиқли дастурлаш масаласи

5.6.4. Chiziqli dasturlash masalasini yechishning Simpleks usuli

Ma’lumki, chiziqli dasturlash masalasi umumiy holda simpleks usulda echiladi. CHiziqli dasturlash masalasini simpleks usulda echish ikki bosqichdan iborat bo’lib, birinchi bosqichda masalaning tayanch echimi, ikkinchi bosqichda esa optimal echim topiladi.
Tayanch echimni topish qoidasi quyidagicha:

1. 
   (5.4.1)-(5.4.3) masalani quyidagi
   

z  с₁ x₁  с₂ x₂ ...  с_n x_n  max(min)
_ y₁  a₁₁ x₁  a₁₂ x₂ ...  a_1n x_n  a₁  0

y

 ₂
^  a x
_ 21 1
 a₂₂ x₂
...  a_{2 n} x_n
 a₂  0

_....................................................
^_ y_n  a_m1 x₁  a_{m 2} x₂ ...  a_mn x_n  a_m  0

x₁  0,
ko’rinishga keltiramiz.
x₂  0,..., x_n  0

2. 
   Yuqoridagi munosabatlardan quyidagi simpleks jadvalini tuzamiz:
   

	-x1	-x2	…	-xn	Ozod sonlar
y1 	^a11	^a12	…	^a1n	a1
y2 	^a21	^a22	…	^a2 n	a2
…	…	…	…	…	…
ym 	^am1	^am 2	…	^amn	am
z	c1	c2	…	cn

3. 
   Ozod sonlar ustunidagi manfiy sonlarni qaraymiz. Agar ushbu sonlarning hammasi musbat bo’lsa, u holda masalaning tayanch echimi topilgan hisoblanadi. Agar ozod sonlar orasida bir nechta manfiy sonlar mavjud bo’lsa, ulardan birini
   

tanlaymiz. Faraz qilaylik
^l - satrdagi
a_l  0
ozod sonni tanlab olaylik.

	- x1	- x2	…	- xk	^-^xk 1	…	- xn	Ozod sonlar
y1 	^a11	^a12	…	^a1k	^a1k 1	…	^a1n	a1
y2 	^a21	^a22	…	^a2 k	^a2k 1	…	^a2 n	a2
…	…	…	…	…	…	…	…	…
yl 	^al1	^al 2	…	^alk	^alk 1	…	^aln	al
^yl 1 ^	^al 11	^al 12	…	^al 1k	^al 1k 1	…	^al 1n	^al 1
…	…	…	…	…	…	…	…	…

y j 	^ajk	^aj 2	….	^ajk	^ajk 1	…	^ajn	a j
…	…	…	…	…	…	…	…	…
ym 	^amk	^am 2	….	^amk	^amk 1	…	^amn	am
z	c1	c2	…	ck	^ck 1	…	cn	0

4. 
   ^l - satrdagi manfiy sonlarni qaraymiz. Agar ushbu satrda manfiy sonlar bo’lmasa, masala echimga ega bo’lmaydi, agar manfiy sonlar bir nechta bo’lsa,
   

ulardan birini tanlaymiz. Masalan, ustun hal qiluvchi ustun deyiladi.
k - ustundagi
a_lk  0
sonni tanlab olaylik. k -

5. 
   Ozod sonlar va ^k -ustundagi mos koifisientlar juftliklarini qaraymiz. Agar
   

ularning ishoralari bir хil bo’lsa, ozod sonlarni mos koifisientlarga bo’lamiz.
^ a ^

6. 
   Hosil bo’lgan nisbatlarning eng kichigini tanlab olamiz: 
   

 min^{ i } .
^{ aik }i 1, p

Bu erda
p - tanlab olingan juftliklar soni.  ga mos keluvchi
k -ustundagi element

bosh element deyiladi. Agar bosh element
^j - satrga mos kelsa
^a _jk - bosh element

bo’ladi, j - satr hal qiluvchi satr deyiladi. Jadval quyidagi ko’rinishga keladi:

	- x1	- x2	…	- xk	^-^xk 1	…	- xn	Ozod sonlar
y1 	^a11	^a12	…	^a1k	^a1k 1	…	^a1n	a1
y2 	^a21	^a22	…	^a2 k	^a2k 1	…	^a2 n	a2
…	…	…	…	…	…	…	…	…
yl 	^al1	^al 2	…	^alk	^alk 1	…	^aln	al
^yl 1 ^	^al 11	^al 12	…	^al 1k	^al 1k 1	…	^al 1n	^al 1
…	…	…	…	…	…	…	…	…
y j 	^ajk	^aj 2	….	^ajk	^ajk 1	…	^ajn	a j
…	…	…	…	…	…	…	…	…
ym 	^amk	^am 2	….	^amk	^amk 1	…	^amn	am

z 

c1

c2

…

ck

^ck 1

…

cn

0

7. 
   a _jk
   

elementga nisbatan simpleks almashtirishlarini bajarib navbatdagi

jadvalni to’ldiramiz:

1. 
   Hal qiluvchi satr va ustundagi o’zgaruvchilar o’rni almashtiriladi;
   
2. 
   Bosh element o’rniga unga teskari sonni yozamiz;
   
3. 
   Hal qiluvchi satr elementlarini bosh elementga bo’lib, mos kataklarga yozamiz;
   
4. 
   Hal qiluvchi ustun elementlarini bosh elementga bo’lib, ishorasini qarama- qarshisiga o’zgartiramiz va mos kataklarga yozamiz;
   
5. 
   Qolgan kataklar to’rtburchak qoidasi bo’yicha to’ldiriladi. Masalan, (2.2) katakni to’ldirish uchun quyidagi hisoblash bajariladi:
   

a
_{1 } ^a jk ^{ a}22 ^{ a}2k ^{ a} j 2 _.
22 _a
jk


Natijada jadval quyidagi ko’rinishga keladi:

	- x1	- x2	…	yi	^-^xk 1	…	- xn	Ozod sonlar
y1 	a'11	a'12	…	^a1k ^ajk	^a^'1k 1	…	a'1n	a'1
y2 	a'21	a'22	…	^a2 k ^ajk	^a^'2 k 1	…	a'2 n	a'2
…	…	…	…	…	…	…	…	…
yl 	a'l1	a'l 2	…	^alk ^ajk	^a^'lk 1	…	a'ln	a'l
^yl 1 ^	^a^'l 11	^a^'l 12	…	^al 1k ^ajk	^a^'l 1k 1	…	^a^'l 1n	^a^'l 1
…	…	…	…	…	…	…	…	…
xk 	^ai1 ^ajk	^ai 2 ^ajk	…	1 ^ajk	^aik 1 ^ajk	…	^ain ^ajk	ai ^ajk
…	…	…	…	…	…	…	…	…

ym 	a'mk	a'm 2	…	^amk ^ajk	^a^'mk 1	…	a'mn	a'm
z 	c'1	c'2	…	ck ^ajk	^c^'k 1	…	c'n	^z^'max

8. 
   So’ngra 3)-6) punktlar barcha ozod sonlar musbat bo’lguncha yoki masalaning echimi mavjud emasligi aniqlangunga qadar takrorlanadi.
   

Tayanch echim topilgach optimal echimni topishga o’tish mumkin. Buning uchun quyidagi amallar bajariladi:

1. 
   z satrdagi manfiy sonlar qaraladi. Agar manfiy sonlar bo’lmasa, optimal
   

echim topilgan hisoblanadi va 1 - ustundagi
x o’zgaruvchilar va
z ularga mos

ozod sonlarga, 1- satrdagi x o’zgaruvchilar esa nolga tenglashtiriladi. Agar z
satrda bir nechta manfiy sonlar bo’lsa, ulardan eng kichigi tanlanadi. Masalan eng

kichik manfiy koifisient
c'₂
bo’lsin.

	- x1	- x2	…	yi	^-^xk 1	…	- xn	Ozod sonlar
y1 	a'11	a'12	…	a'1k	^a^'1k 1	…	a'	a'1
y2 	a'21	a'22	…	a'2 k	^a^'2 k 1	…	a'2 n	a'
…	…	…	…	…	…	…	…	…
yl 	a'l1	a'l 2	…	a'lk	^a^'lk 1	…	a'ln	a'l
^yl 1 ^	^a^'l 11	^a^'l 12	…	^a^'l 1k	^a^'l 1k 1	…	^a^'l 1n	^a^'l 1
…	…	…	…	…	…	…	…	…
xk 	a'i1	a'i 2	…	a'ik	^a^'ik 1	…	a'in	a'i
…	…	…	…	…	…	…	…	…
ym 	a'mk	a'm 2	…	a'mk	^a^'mk 1	…	a'mn	a'm
z 	c'1	c'2	…	c'k	^c^'k 1	…	c'n	^z^'max

2. 
   2- ustundagi musbat sonlarni tanlaymiz. Agar ushbu ustunda musbat sonlar bo’lmasa, masalaning optimal echimi cheksizlikka intiladi. Agar ustunda
   

musbat sonlar bo’lsa, ularga mos ozod sonlarni bo’lib, eng kichik nisbatni tanlab
 _a 

olamiz: 
 min^{ 2 }
. Bu erda
^k - tanlab olingan juftliklar soni.

a
 
^{ j 2 } j 1,k

3. 
   Eng kichik nisbatga mos element bosh element hisoblanadi va unga nisbatan simpleks almashtirishlari bajariladi.
   
4. 
   1)-3) punktlar z qatordagi barcha sonlar musbat bo’lguncha yoki
   

masalaning echimi yuqoridan chegaralamaganligi aniqlanguncha davom ettiriladi.

Agar maqsad funksiyasida
z  с₁ x₁  с₂ x₂ ...  с_n x_n  min
bo’lsa, u holda masala

koifisientlar ishoralari o’zgartirilib, maksimumga keltiriladi:

z  с₁ x₁  с₂ x₂  ...  с_n x_n  max

va masala yuqoridagi usul bilan echiladi. Natijada
^zmin ^{ -z}max
bo’ladi.