Maruza mashg’ulotlari

Download 1,74 Mb. bet 44/56 Sana 01.01.2022 Hajmi 1,74 Mb. #280729

Bog'liq
Mavzular

Bu sahifa navigatsiya:

• Maxsulotga bo‘lgan talab

		Xm1	Xm2	...
Xmn
Am	am	Cm1	Cm2		Cmn
Maxsulotga bo‘lgan talab		b1	b2	...	bn

Shunday qilib, masala va uning shartlarini jadval ko‘rinishida juda sodda, aniq va ixcham xolda ifodaladik. Endi bu masalani matematika tilida ifodalaymiz, ya’ni matematik modelini tuzamiz.

Masalanining matematik modelini tuzishimiz uchun, har bir ishlab chiqarish punktini iste’mol punktlariga shunday moslab qo‘yish kerakki, birinchidan, har bir ishlab chiqarish punktidagi maxsulotlar to‘la taqsimlansin. Bu shartni tenglamalar sistemasi orqali qo‘yidagicha yozish mumkin:

(15.1)

Ikkinchidan, har bir iste’mol qiluvchi punktning talabi to‘la qondirilsin. Bu shart quyidagi ko‘rinishda yoziladi.

(15.2)

Uchinchidan, maxsulotlarni tashish uchun sarf qilinadigan jami harajat eng kam bo‘lsin. Bu shartni quyidagi chiziqli funksiya orqali ifodalaymiz.

Z=S₁₁X₁₁+ S₁₂X₁₂+…+ S_1nX_1n+

+ S₂₁X₂₁+ S₂₂X₂₂+…+ S_2nX_2n+

+ ………………………… + (15.3)

+ S_m1X_m1+ S_m2X_m2+…+ S_mnX_mn

IQtisodiy nuqtai nazardan, bu masalaning echimlari manfiy bo‘lmasligi kerak, ya’ni:

Xij  0, (i = 1,2,...,m , j = 1,2,...,n ) (15.44)

1. 
   – (4) ifodalarni yig‘indi ko‘rinishida quyidagicha yozish mumkin:
   

(15.5)

Z = (15.6)

Shunday qilib (15.5) –(15.6) ifodalar birgalikda transport masalasining matematik modeli deb ataladi. Demak, (15.5) shartni qanoatlantiruvchi shunday echimlarni tanlashimiz kerakki, natijada (15.6) maqsad funksiya eng kichik qiymatga erishsin

Agar ishlab chiqarilgan maxsulotlarning umumiy miqdori ularga bo‘lgan talabning miqdoriga teng bo‘lsa, ya’ni

(15.7)

bo‘lsa,u xolda bu masalani yopiq modelli transport masalasi deb ataymiz.

Teorema. Ixtiyoriy yopiq modelli transport masalasi echimga ega.

Isbot. Teoremani isbotlash uchun, berilgan shartlar asosida, masalaning hech bo‘lmaganda bitta echimi mavjudligini va maqsad funksiyaning echimlari to‘plamida chegaralanganligini ko‘rsatish kifoya. Teoremaning shartiga ko‘ra (15.7) tenglik o‘rinlidir, u holda

Xij = , (i = 1,...,m ; j = 1,...,n) (15.8)

ifoda berilgan transport masalasining echimi bo‘ladi, chunki u (15.6) cheklanish shartlarini qanoatlantiradi. Xaqiqatdan ham,

X_ij =  0, chunki a_i0, b_j0, M>0.

Maqsad funksiyaning echimlar to‘plamida chegaralanganligini ko‘rsatish uchun S_ij qiymatlarini ichidan eng kattasini tanlab olib, uni S=max S_ij deb belgilaymiz va (15.6) maqsad funksiyaning barcha kooffisentlarini S¹ga almashtiramiz; u xolda (15.5) ning birinchisiga va (15.8) ga asosan quyidagicha ega bo‘lamiz:

Endi C_ij qiymatlarining ichidan eng kichigini tanlab olib, uni S``=minC_ij deb belgilaymiz va (15.6) maqsad funksiyaning barcha koeffisientlarini S'' ga almashtiramiz; u xolda (15.5) ning birinchisiga va (15.8) ga asosan quyidagiga ega bo‘lamiz.

Ikkita oxirgi tengsizliklarni birlashtirib, ularni quyidagi ko‘rinishda yozamiz

S``M z S`M

Demak, maqsad funksiya transport masalasining echimlari to‘plamida chegaralangan ekan.

Misol. A_1, A₂ va A₃ omborlarda mos ravishda 90 t , 70 t va 50 t un saqlanadi. Bu unlarni V₁, V₂, V₃ va V₄ magazinlarga ularning talablariga ko‘ra, mos ravishda 80 t, 60 t, 40 t, va 30 t dan etkazib berish kerak bo‘lsin. A₁ ombordan 1 t unni V₁ ,V₂, V₃ va V₄ magazinlarga etkazib berish uchun sarf qilinadigan transport xarajati mos ravishda 2; 1; 3; va 2 so‘mni A₂ ombordan – 2; 3; 3; va 1 so‘mni va A₃ ombordan esa - 3,3,2 va 1 so‘mni tashkil qilsa, barcha unni tashishda sarf qilingan umumiy transport xarajati eng kam bo‘ladigan echim topilsin . Bu transport masalasining matematik modeli tuzilsin.

Echish : A_i (i = 1,2,3) omborlardan Bj ( j = 1,2,3,4) magazinlarga etkazib beriladigan unning miqdorini Xij, bilan Ai omborlarda saqlanayotgan unning miqdorini a_i (bunda a₁= 90 t, a₂ = 70t, a₃ =50 t) bilan, Bj magazinlarning unga bo‘lgan talabini bj ( bunda b₁ = 80 T, b₂ = 60 T, b₃ = 40 T, b₄ = 30 T) bilan belgilasak , har bir omborlardagi uning to‘la taqsimlanish shartini

ko‘rinishda, har bir magazinlarning unga bo‘lgan talabini to‘la qondirish shartini

ko‘rinishda yozish mumkin.

A_i omborlardan B_j magazinlarga bir tonna unni etkazib berish uchun sarf qilingan transport xarajatini S_ij bilan belgilasak , unni tashish uchun sarf qilinadigan jami xarajatning miqdorini aniqlaydigan chiziqli funksiya quyidagicha bo‘ladi:

Z=2X₁₁ + X₁₂ + 3X₁₃ + 2X₁₄ + 2X₂₁ + 3X₂₂ + 3X₂₃ + X₂₄ + 3X₃₁ + 3X₃₂+2X₃₃+X₃₄

IQtisodiy nuqtai nazardan, transport masalasining echimlari manfiy bo‘lmaslik shartlarini hisobga olib, quyilgan transport masalasining matematik modelini quyidagicha ifodalash mumkin:

Z=2X₁₁ + X₁₂ + 3X₁₃ + 2X₁₄ + 2X₂₁ + 3X₂₂ + 3X₂₃ + X₂₄ + 3X₃₁ + 3X₃₂+2X₃₃+X₃₄

chiziqli maqsad funksiyaning quyidagi:

X_ij  0, i=1,3; j=1,4

cheklanish tenglamalari sistemasini qanoatlantiradigan minimumi topilsin.

Transport masalalarini echish uchun qo‘llaniladigan birinchi aniq usul, potensiallar usuli 1949 yilida olimlar L.V Kantorovich va M.K Gavurin tomonidan taklif qilingan. Bu usulning asosiy g‘oyasi, chiziqli dasturlashtirish masalalarini echish usullariga bog‘liq bo‘lmagan xolda, transport masalasiga moslashtirilgani simpleks usulidan iboratdir.

Boshqa chiziqli dasturlashtirish masalalari singari transport masalasini potensiallar usuli yordamida echish jarayoni ham boshlang‘ich bazis echimini topishdan boshlanadi. Bu usul yordami bilan boshlang‘ich bazis echimdan boshlab, optimal echimga yaqinroq bo‘lgan yangi bazis echimlarga o‘ta borib, chekli sondagi qadamdan so‘ng masalaning optimal echimi topiladi.

Shuning uchun, potensiallar usulining asosiy maxiyatini bayon qilishdan oldin, transport masalasining boshlang‘ich bazis echimini topish uchun qo‘llaniladigan usullardan biri – shimoli – g‘arb burchak usuli bilan tanishamiz:

1. Shimoli – g‘arb burchak usuli. Faraz qilaylik, transport masalasining shartlari 1 – jadvaldagidek ko‘rinishda berilgan bo‘lsin.

Shimoli – g‘arb burchak usulning asosiy mohiyati quyidagilardan iborat: dastavval masalaning echimlaridan tuzilgan jadvallarning shimoli g‘arbida joylashgan noma’lum X₁₁ ning qiymati aniqlanadi. X₁₁= min (a₁, v₁). Agar a₁ v₁ bo‘lsa, X₁₁= a₁ va x_1j =0 (j=2,3,...,n) bo‘lib, a₁=0 va v₁=v₁-a₁ ga o‘zgaradi, agar a₁  v₁ bo‘lsa, X₁₁= v₁ va x_i1 =0 (i=2,m) bo‘lib, a₁=a₁-v₁ va v₁=0 ga o‘zgaradi.

Faraz qilaylik, ikkinchi xol bajarilsin. Bu xolda 1 – qadamdan so‘ng masalaning echimlaridan tuzilgan jadval 2 – jadval ko‘rinishda bo‘ladi. Endi jadvalning shimoli – g‘arbida joylashgan X₁₂ ning qiymati aniqlanadi: agar a₁-a₁>v₂ bo‘lsa, X₁₂= v₂ va x_2j =0 (i=2,...,m) bo‘lib, a₁-v₁=a₁- v₁- v₂ va v₂=0 ga o‘zgaradi. Agar a₁-v₁2 bo‘lsa, X₁₂= a₁- v₁ va x_1j =0 (j=3,...,n) bo‘lib,

a₁- v₁=0 va v₂=v₂-a₁+v₁ ga o‘zgaradi.

Aytaylik, yangi jadval uchun birinchi hol bajarilsin, u holda 2 – qadamdan so‘ng masalaning echimlaridan tuzilgan jadval 3-jadval ko‘rinishda bo‘ladi.

1 – jadval

Ishlab chiqarish punktlari	Ishlab chiqarilgan maxsulotlar	Iste’mol punktlari.
		V1	V2	V3	…	Vn
A1	a1-v1	b1	X12	X13	…	X1n
A2	A2	0	X22	X23	…	X2n
…	…	…	…	…	…	…
Am	am	0	Xm2	Xm3	…	Xmn
Maxsulotga bo‘lgan talab		0	b2	b3	…	bn

2- jadval.

Ishlab chiqarish punktlari	Ishlab chiqarilgan maxsulotlar	Iste’mol punktlari.
		V1	V2	V3	…	Vn
A1	a1-v1-v2	b1	b2	X13	…	X1n
A2	A2	0	0	X23	…	X2n
…	…	…	…	…	…	…
Am	am	0	0	Xm3	…	Xmn
Maxsulotga bo‘lgan talab		0	0	b3	…	bn

3 – jadval.

Ishlab chiqarish punqtlari	Ishlab chiqarilgan maxsulotlar	Iste’mol punktlari.
		V1	V2	V3	…	Vn
A1	0	b1	b2	a1-v1-v2	…	0
A2	a2	0	0	X23	…	X2n
…	…	…	…	…	…	…
Am	am	0	0	Xm3	…	Xmn
Maxsulotga bo‘lgan talab		0	0	b3-a1-v1+v2	…	bn

2 – jadvalning shimoli – g‘arbidagi noma’lum X₁₃ ning qiymatini topaylik. Faraz qilaylik, bu xolda a₁-v₁-v₂< b₃ bo‘lsin. Demak, X₁₃=a₁-v₁-v₂ va X_1j = 0 (j=4,...,n) bo‘lib, a₁-v₁-v₂=0 va b₃= b₃- a₁-v₁+v₂ ga o‘zgaradi. (3 – jadvalga qarang) va x.k.

Xuddi shu yul bilan davom etib, har bir qadamda jadvalning shimoli – g‘arbiy burchagida joylashgan X_ij ning qiymati X_ij – min(a_i,b_i) topiladi, bunda a_i,b_i nolga o‘zgaradi. Bu jarayon barcha a_i va b_i lar nollarga aylangunga qadar davom ettiriladi.

Download 1,74 Mb.

Do'stlaringiz bilan baham: