Amaliy matematika va informatika ta’lim yo’nalishi 2-oliy ta’lim 4-bosqish talabasi

6 § _Сhiziqli programmalash masalalari uchun egizak masalalar
Bu yerda chiziqli programmalash masalalari nazariyasida muhim o’rin egallagan egizak masalalar tushunchasida to’xtalamiz va ularning iqtisodiy ma’nosini tahlil qilamiz. ChPM umumiy ko’rinishini esga olsak (2 §).


n
∑a_ij x _j ≤ b_i ,i =1,2,...,m (2.1) j=1


x _j ≥ 0, j =1,2,...,n

n

L(x₁,x₂,...,x_n ) =∑c _j x_i → max (2.2)

j=1
Shartlarga ko’ra x₁,x₂ ,...x_n larni topish talab qilinar edi. Masala tarkibidagi har bir koeffitsiyentga o’z vaqtida izoh berilgan edi. Aynan shu koeffitsiyentlar yordamida quyidagi masalani tuzamiz.


n
∑a_ij y _j ≥ C _j , i =1,2,...,n (6.1) i=1




m

Q(y₁, y₂,..., y_m ) = ∑b_i ⋅ y_i → min (6.2)

j=1
Hosil bo’lgan (6.1) – (6.2) masala (2.1) – (2.2) ChPM ga nisbatan egizak masala deyiladi. Agar (2.1) – (2.2) masala yechimi mavjud bo’lsa (6.1) – (6.2) masala yechimi ham mavjud bo’lar ekan. Shu bilan birga bu yechimlar, yani optimal yechimlar uchun



tenglik o’rinli bo’lar ekan. Bu holat ba’zi murakkab ChPM lar uchun egizak masala yordamida tahlil o’tkazishga imkoniyat beradi. E’tibor bersak (2.1) – (2.2) va (6.1) – (6.2) masalalar aynan bir xil koeffitsiyent orqali ifodalanishi hamda ularning yechimlari ham bir xilligi bu masalalarni “ egizak masalalar ” deb atalishiga sabab bo’lgan.

Tahlil va xulosalarni soddalashtirish uchun avvalgi paragraflarda keltirilgan masalalardan foydalanamiz. Xususan § 1 da ko'rilgan (1.1) – (1.2) masalani olsak

uning to’la tahlili va yechimi § 1 da keltirilgan. Unga ko’ra optimal reja c (30;90)

nuqtada bo’lib, bunda bo’lib ekanligini ko’rgan edik. Yuqorida keltirilgan tartibga ko’ra (1.1) – (1.2) masala uchun egizak masala tuzamiz.

(6.3)
(6.4)

Hosil bo’lgan (6.3) – (6.4) egizak masalani geometrik usulda yechish uchun uni kanonik ko’rinishga keltiramiz. chizmada ifodalasak, egizak masala uchun ham MBES qavariq soha bo’lishini ko’ramiz. Bu holat barcha egizak masalalar uchun o’rinli bo’lar ekan. (6.3) – (6.4) masala shartlariga mos mumkin bo’lgan yechimlar sohasi MBES chizmada keltirilgan

tekisliklardan yuqoridagi soha bo’ladi. Bu qavariq sohaning chegaralaridagi uchlari
M1 _, M2 _, M3 _, M4 _, M5 nuqtalarida bo’ladi. Optimal yechimni aynan shu nuqtalardan birida izlash kerak. Chizmadan ko’rinadiki M1 (10000; 0; 0), M2 (0; 7000; 0), M3 (0;0;14000), M4 (2000; 0; 8000), M5 (1231; 3846; 0). Bu yerda M4 _, M5 nuqtalar koordinatalari (6.3) sistemadan deb topilgan. Optimal yechimni
Q (Y1,Y2, Y3 ) qiymatlarini taqqoslash orqali topamiz.

Q(M1) = 300000 ; Q(M2) = 315000 ; Q(M3) = 168000 ; Q(M4) = 156000 ; Q(M5) = 170775. Bu yerdan M4 nuqtada eng kichik qiymat bo’lishini ko’ramiz. Haqiqatdan ham

bo’lar ekan.

Egizak masala yechimini simpleks usulda asosiy masala bilan birgalikda bir yo’la topish mumkin ekan. Buni bevosita amaliy masalani yechish jarayonida namoyish qilamiz.

masala uchun egizak masala

Geometrik usulda asosiy masala uchun OX1X2 koordinat tekisligida MBES ni chizib tayanch yechimlar M1(8;0) , M2(0;5), M3(5;4) nuqtalarda bo’lib, bu nuqtalarda maqasad funksiya qiymatlari L1 = 2400, L2 = 2400, L3 = 5 · 300 + 4 · 480 = 3420 . Taqqoslash natijasida optimal yechim M3(5;4) nuqtada bo’lib, bu nuqtada ekanligini ko’ramiz. Shuningdek egizak masala uchun OY1 Y2 tekisligida MBES ni tuzib tayanch yechimlar M1(160;0), M2(0;300), M3( 60;60) nuqtada bo’lishini ko’ramiz. Bu nuqtalardagi tayanch yechim qiymatlari Q1 =5120, Q2 = 7500, Q3 = 3420 larni taqqoslab min Q = 3420 ekanligini va bu qiymatga bo’lgan M3 nuqtada erishilishini ko’ramiz. Shu masalani simpleks usulda yechimini topish jarayonini keltiramiz.

Sun’iy basis larni kiritib 1 – simpleks jadvalni ifodalaymiz.

				300	480	0	0
1	300		5	1	0
2	480		4	0	1
			3420	0	0	60	60

Bu jadvalga mos barcha . Demak, jadvaldan ekanligini ko’ramiz. Sun’iy bazislarga mos ustunlardan esa, lar qatorida ekanligi kelib chiqadi. Bu yechimlar geometrik usulda topilgan yechimlar bilan bir xil ekanligini ko’ramiz. Egizak masalaning iqtisodiy ma’nosi. Agar asosiy masalada daromadlarni maksimal bo’lishini ta’minlaydigan reja izlangan bo’lsa, egizak masalada harajatlarni minimal bo’lishini ta’minlaydigan qiymatlar izlanar ekan. Bu yerda Y1, Y2 larni mos ravishda 1- va 2- homashyolarning bir birligi narxi deb tushunish mumkin. Egizak masala tushunchasi nisbiy bo’lib, agar (6.1) – (6.2), ya’ni Yi larga nisbatan masalani asosiy desak, Xj larga nisbatan (2.1) – (2.2) masala egizak masala bo’ladi. Mustaqil ishlash uchun masalalar.
Berilgan ChPM uchun egizak masala tuzilsin va uning yechimi geometrik usulda topilsin.

6.1

6.2


6.3


6.4


6.5



http://fayllar.org