Simpeks metod

Г^а11^х 1 + a 12 ^x 2 ^ ^ ^ ^bi


a 2


+a 22 ^x 2 + - - - + a ^ b ,

1 1 2 n n


(1)


L^a m1^X 1 + ^am 2 ^X 2 ^ ^ ^amn ^Xn ^ ^Ь.

X1 ^ 0, X2 ^ 0, Xn ^ 0,


(2)

^Ymax C1X1 + C2X2+ . ^ + CnXn (3)

Bu masalaga Xn+i> 0, Xn+2 > 0, xn+m > 0 qo‘shimcha o‘zgaruvchilar

kiritilsa, quyidagi kegaytirilgan masala hosil bo‘ladi:

^Га 11 ^X1 + ^^X 2 + - - - + ^ ^Xn +1 = b






_a 21 ^X 1 +^a 22 ^X 2 + - - - + a 2„Xl + ^Xn +2 = b 2


(4)


a „,1^1 + _{a X} + _{- - -} + _{a X} + X — b_m

^{m1 1 a}m 2 ^X 2 + ^a mn ^Xn ⁿ+^{m m}

X1 > 0, X2 > 0, Xn > 0, Xn+m > 0,

(5)

Ymin = - 01x1 - 02x2 - . - Gnxn + 0(xn+1 +,.+ xn+m)

(6)

Bu holda Pn+i, Pn+2,^, Pn+m vektorlar bazis vektorlar va
Xn+i,Xn+2,^,Xn+m o‘zgaruvchilar «bazis o‘zgaruvchilar» deb qabul
qilinadi.

Agar berilgan masala quyidagi ko‘rinishda bo‘lsa:

^ra11^X1 + ^a12 ^X 2 + + ^a1n ^Xn = ^b1


<1 ^a 21^X 1


21^X 1 +^a 22 ^X 2 + + ^a 2 n ^Xn = ^b2


^a m1^X 1 + ^am 2 ^X 2 + + ^amn ^Xn = ^Ь.


(6)



X1 > 0, X2 > 0, Xn > 0,

Ymin = ClXl + C2X2+ ^ + CnXn


(8)

(9)


bu masalaga sun’iy Xn+i,Xn+2,^,Xn+m o‘zgaruvchilar kiritib quyidagi kengaytirilgan masala hosil qilinadi:


^ai1 ^X1 + ^a12 ^X2 ^ ^ ^a1n ^Xn + ^Xn+1


^b1






1^X1 22 ^X 2 + - - - + a = b

2 n n n +2 2


(10)


^am1^X1 + ^am 2 ^X 2 +


+ X = b.


X1 > 0, X2 > 0, Xn > 0, Xn+1>0,^, Xn+m > 0, (11)

Ymin c1x1 - c2x2 - ^ " cnxn + M(xn+1 +,^+ xn+m) (12)

bu yerda: M - yetarlicha katta musbat son.

Sun’iy bazis o‘zgaruvchilariga mos keluvchi Pn+i, Pn+2,^, Pn+m vektorlar «sun’iy bazis vektorlar» deb ataladi.

Berilgan (7)-(9) masalaning optimal yechimi quyidagi teoremaga asoslanib topiladi.

Teorema: Agar kengaytirilgan (10)-(12) masalaning optimal

yechimida sun’iy bazis o‘zgaruvchilari nolga teng bo‘lsa, ya’ni:

Xn+i =0 (i=1,^,m)

tenglik o‘rinli bo‘lsa, u holda bu yechim berilgan (7)-(9) masalaning ham optimal yechimi bo‘ladi.

Kengaytirilgan masalaning optimal yechimida kamida bitta sun’iy bazis o‘zgaruvchi noldan farqli bo‘lsa, unda masala yechimga ega bo‘lmaydi.

1- Misol. Masalani sun’iy bazis usuli bilan yeching

X + 3x + 2x + 2x = 3


xj > ^0,


2x + 2x + X + X = 3

(j=1, 2,^, 4)

Zmax = 5x1 +3x2 + 4x3 - x4

Yechish. Masalaga sun’iy xj>0 X6> 0 o‘zgaruvchilar kiritamiz va
uni normal ko‘rinishga keltiramiz.


X + 3x + 2x + 2x + X = 3


[2 X + 2x + X + X + X = 3

xj > 0, (j=1, 2,_, 6)

Zmin = -5x1 -3x2 -4x3 + x4+M(x5 + x6)

Hosil bo‘lgan masalani simpleks jadvalga joylashtirib, uni simpleks usul bilan yechamiz.


+ ^amn ^Xn

i	Bazi s vekt.	^Cbaz	P0	-5	-3	-4	1	M	M
				Pi	P2	P3	P4	P5	P6
1	P5	M	3	1	3	2	2	1	0
2	Рб	M	3	2	2	1	1	0	1
^AJ			6M	3M+ 5	5M+ 3*	3M+4	3M-1	0	0
1	P2	-3	1	1/3	1	2/3	2/3	1/3	0
2	Рб	M	1	4/3	0	-1/3	-1/3	-2/3	1
^AJ			M 3	4/3M +4*	0	1/3M +2	I/3M- 3	-5/3M- 1	0
1	P2	-3	3/4	0	1	3/4	3/4	1/2	-1/4
2	Pi	-5	3/4	1	0	-1/4	-1/4	-1/2	3/4
Aj			-6	0	0	3*	-2	1-M	-3-M
1	Рз	-4	1	0	4/3	1	1	2/3	-1/3
2	Pi	-5	1	1	1/3	0	0	-1/3	2/3
^Ai			9	0	-4	0	-5	-1-M	-2-M

Shunday qilib, simpleks usul bo‘yicha 4-ta qadamdan iborat yaqinlashishda optimal yechim topildi. Aj < 0. Optimal yechim

x=(1;0;1;0;0;0), Ymin=-9.

Kengaytirilgan masalaning optimal yechimidagi sun’iy o‘zgaruvchilar 0 ga teng (x5=0, x6=0). Shuning uchun (3-teoremaga asosan) berilgan masalaning optimal yechimi:

Х=(1;0;1;0); Zmin=-9; Zmax=9; bo‘ladi.

Ma’lumki, chiziqli dasturlash usullari va jumladan, simpleks usul iqtisodiy masalalarning eng yaxshi (optimal) yechimini topishga yordam beradi. Lekin buning o‘zi kifoya emas. Optimal yechim topilgandan so‘ng iqtisodiy ob’ektlar (zavod, fabrika, firma) boshliqlari oldida quyidagiga o‘xshash muammolarni yechishga to‘g‘ri keladi:

1. 
   Xom- ashyolarning ba’zilarini oshirib, ba’zilarini qisqartirib sarf qilinsa optimal yechim qanday o‘zgaradi?
   
2. 
   Optimal yechimni o‘zgartirmasdan xom-ashyolar sarfini qanday darajaga o‘zgartirish (kamaytirish) mumkin?
   

xom-ashyo	Texnologiyalar			xom- ashyolar zapasi
	T1	T2	T3
Ish kuchi (ishchi/soat)	15	20	25	1200
Birlamchi xom-ashyo (t)	2	3	2,5	150
Elektr energiya (KVT/ch)	35	60	60	3000
Texnologiyaning unumdorligi	300	250	450
Texnologiyalarni ishlatish rejalari	X1	X2	X3	Z ^max