T. I. Umarov s. I. Xudoyberdiyev iqtisodiy matematik usullar va

1	0
1
m+1	^N, - С		0	-5	-3	-4	1	0	0
m+2	^N, - С		-6	-3	-5	-3	-3	0	0

N 2	^-^С 2	= C6X 2	2 0 -
N 3	^-^С 3	= C6X 3	^-^0 3
N 4	^-С4	= OX 4	^-^0 4 ^:
N 5	^-^C5	= QX5 -	^-^05 ^:
N 6	1 С Os	= c6x 6	^- 06

-М • 0 - М -1 - (-М) = 0 + 0 • М

hisoblashlarni bajarib, N, - С, baholar ikkita qo’shiluvchilardan iborat hamda

M ning chiziqli funksiyasi ekanligini payqaymiz.

Hisoblashlarning qulayligi uchun (m+1) satrga chiziqli funksiyaning ozod hadini, (m+2) satrga esa M ning koeffitsentlarini yozamiz. (m+2) satrda manfiy sonlarning mavjudligi tayanch yechimning optimal emasligini bildiradi va uni yaxshilash mumkin bo’ladi. Jadvalning asosiy qismi (m+2) satrda manfiy sonlarning mavjudligi tayanch yechimning optimal emasligini bildiradi va uni yaxshilash mumkin bo’ladi. Jadvalning asosiy qismi (m+2) satrida eng kichik son (-5) A₂ vektor bahosi bo’lganligi uchun yo’naltiruvchi (kalit) ustun (A₂)

ustuni bo’ladi. min(j~,3j = 1, bo’lganligi uchun A₅ vektor satri yo’naltiruvchi

(kalit) satr, 3 ochuvchi (kalit) element bo’ladi. Demak, A₅ ni bazisdan chiqarib o’rniga A₂ vektorni bazisga kiritamiz. 2-simpleks jadvalni tuzamiz.

2. 
   
   simpleks jadval.
   

1	Bazislar	Bazis koeffi- siyent- lar Sb	A0	5	3	4	1	-M	-M
				A1	A2	A3	^A4	A5	^A6
1	A2	3	1	1/3	1	2/3	2/3	1/3	0
2	^A6	-M	1	1/3	0	-1/3	-1/3	-2/3	1
m+1	^N, - ^C,		3	-4	0	-2	3	1	0
m+2	^N, - ^C,		-1	-4/3	0	1/3	1/3	5/3	0

2. simpleks jadvalning (m+2) satri asosiy qismida (-4/3) manfiy son bo’lganligi uchun Aj vektor ustuni yo’naltiruvchi (kalit) ustun, A₆ vektor satri yo’naltiruvchi (kalit) satr, 4/3 ochuvchi (kalit) element bo’ladi. Bazisdan A₆ sun’iy vektorni chiqarib, A_j vektorni bazisga kiritib, 2-simpleks jadvaldagidek,

   
   

3. simpleks jadvalni hosil qilamiz:

   
   

3-simpleks jadval.

i	Bazislar	Bazis koeffi- siyent- lar Sb	Ao	5	3	4	1	-M	-M
				Ai	A2	A3	^A4	A5	^A6
1	A2	3	3/4	0	1	3/4	3/4	1/2	-1/4
2	Ai	5	3/4	1	0	-1/4	-1/4	-1/2	3/4
M+1	^N, - ^C,		6	0	0	-3	2	-1	3
M+2	^N, - ^C,		0	0	0	0	0	1	1

3. jadvalda (m+2) katrda sun’iy bazis baholaridan tashqari hamma baholar 0 ga teng bo’ladi:

   
   

M sonning tanlanishiga asosan A₅ va A₆ vektorlar endi bazisga tushmaydi, shuning uchun uni bundan keyin qaramasak ham bo’ladi, lekin, teskari

matritsani olish uchun uni saqlash mumkin.

2

X о = (3/ 4,3/ 4, 0, 0, 0, 0) tayanch yechim berilgan masalaning ham yechimi bo’ladi, lekin u optimal emas, chunki (m+1) satrda manfiy baho mavjud. Endi yechimni yaxshilash (m+1) satr bo’yicha olib boriladi. N₂ - C₂ =-3 < 0 bo’lganligi uchun A₃ vektor ustuni yo’naltiruvchi (kalit) ustun, A₂ vektor satri yo’naltiruvchi (kalit) satr, 3/4 ochuvchi (kalit) element bo’lib, m+2 katr endi hisobga olinmaydi. Yuqorida ko’rsatilgan usul bilan 4-simpleks jadvalni tuzamiz:

4-simpleks jadval.

i	Bazislar	Bazis koeffi- siyent- lar Sb	A0	5	3	4	1	-M	-M
				A1	A2	A3	^A4	A5	^A6
1	A3	4	1	0	4/3	1	1	2/3	-1/3
2	A1	5	1	1	1/3	0	0	-1/3	2/3
M+1	^N, - ^C,		9	0	4	0	5	1+M	2+M

4. simpleks jadvaldan qo’yilgan masalaning optimal yechimi X = (1, 0,1) bo’lib,

   
   

Z_max(X) = 9 bo’ladi. Birinchi va ikkinchi satrlarni o’zaro almashtirib, A₅ va A₆

vektorlar ustunida teskari matritsani hosil qilamiz.

Qaralgan misoldan ko’rinadiki, cheklash shartlarida birlik matritsa mavjud bo’lsa, m ta jadval, sun’iy bazis kiritilgan bo’lsa, taxminan 2m ta jadval tuziladi.

5. Aralash shartli masalalar.

   
   

Chiziqli dasturlash masalasi quyidagicha qo’yilgan bo’lsin:

^Z = ^C1 *1 + ^C2 ^X2 + ... + ^Cn^Xn

chiziqli funksiyaning

^ai1 ^X1 + ^ai2^X2 + ... + ^ain^Xn <

^a21 ^X1 + ^a22^X2 + ... + ^a2n^Xn < К

?

^ak1 ^X1 + ^ak 2 ^X2 + ... + ^akn^Xn < ^bk ^{, a}k₊1,1 ^X1 + ^ak+1,2 ^X2 + ... + ^ak₊1,n^Xn = ^bk₊1^,

?

^am1 ^X1 + ^am2^X2 + ... + ^amn^Xn = ^bm <sup>,

X</sup> > ⁰⁽ j = ^1,2,...^{, n)} cheklash shartlari sistemasini qanoatlantiruvchi minimal qiymatini toping.

Bu cheklash shartlari k ta tengsizliklar (1 < k < m) va m-k ta tenglamalardan iborat bo’lib, m tartibli, birlik matritsaga ega emas. Bunday cheklash shartlari mavjud bo’lgan chiziqli dasturlash masalasiga chiziqli dasturlashning aralash shartli masalasi deyiladi. Bunday masalalarning bazisi qo’shimcha va sun’iy bazis vektorlaridan iborat bo’ladi.

Aralash shartlar sistemasida d ta tenglamalar bo’lsin. Boshlang’ich tayanch yechimni olish uchun d dan ko’p bo’lmagan sun’iy o’zgaruvchilar kiritish kerak bo’ladi.

1. misol. z = -Xj - 2x₂ + x₃ chiziqli funksiyaning

   
   

- X1 + 4x₂ - 2 X3 < 6,

Xj + x₂ + 2x₃ > 6,

2Xj - x₂ + 2x₃ = 4, x, > 0 (j = 1,2,3)

cheklash shartlarini qanoatlantiruvchi minimal qiymatini toping.

Yechish. Bu masalada tengsizliklardan tenglamalarga o’tsak, ikkita sun’iy o’zgaruvchi kiritishga to’g’ri keladi. Bunday qilmaslik uchun, ikkinchi tengsizlikni 2 ga bo’lib, keyin uni tenglamaga aylantiramiz va hosil bo’lgan tenglamani uchinchi tenglamadan ayiramiz, hamda 3-tenglamaga sun’iy o’zgaruvchi kiritamiz: natijada ushbu chiziqli dasturlash masalasini hosil qilamiz: