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

I	C j Ci			20	15	30	25
		Baz	A0	A1	A2	A3	A4	Ө
1	15	A2	2	1	1	0	2
2	30	A3	1	1/3	0	1	2 − 3
		∆ j		5	0	0	-15

Bu jadvaldan ko'rinadiki, tanlangan bazisga mos tayanch yechim optimal emas ekan, chunki ∆ ₄ =₋15  0bo'layapti. Rejani yaxshilash ychun bazisni almashtirish kerak. Buyog'i simpleks usul davom ettirilishi mumkin.

4. CHPM shartlari tanlangan bazisga moslashtirilsin. Shu bazisdagi tayanch yechim optimallikka tekshirilsin.














§ 5. Transport masalasi
Chiziqli programmalash masalalaridan bir turi “transport masalasi” nomi bilan ma'lum bo'lgan matematik masalalarga keltiriladigan iqtisodiy masalalardan iborat bo'ladi. Ma'lumki, ishlab chiqaruvchi bilan iste'molchi orasidagi mol almashinuvi ya'ni ishlab chiqarilgan mahsulot yoki tayyrolangan homashyoni korxonalarga yetkazib berish transport vositalari va ularga sarflanadigan moliyaviy harajatlar bilan bog'liq. Bu harajatlarni minimallashtiruvchi variantlarni tanlash transport masalasining asosiy muammosi hisoblanadi.
Transport masalasining matematik modelini ifodalashda umumiyatni cheklamagan holda sxematik tarzda quyidagi muammoni tahlil qilamiz. Faraz qilaylik ma'lum homashyo turi zaxiralari saqlanuvchi yoki tayyorlanuvchi n ta punkt bo'lsin. Bu punktlardagi homashyo miqdorlari mos ravishda b₁ , b₂ , …, b_n birliklardan iborat bo'lsin. Bu yerda homashyo turiga ko'ra ma'lum bir o'lchov birligi (tonna, metr, …) tanlangan bo'ladi. Shuningdek, keltirilgan homashyo asosida ishlaydigan m ta korxona bo'lib, bu korxonalarning shu homashyoga bo'lgan extiyojlari mos ravishda d₁ , d₂ , … d_m birliklardan iborat bo'lsin. Shuningdek homashyo punktlari hamda korxonalar orasidagi yo'l sifati va masofasiga ko'ra homashyoni yetkazish uchun ketadigan yo'l harajatlari koeffisintlari ma'lum bo'lsin. Ularni C ₌ (C_ij ) 1_≤ i _≤ m, 1_≤ j _≤ m; matritsa ko'rinishida ifodalaymiz. Bunda matritsaning har bir elementi C_ij mos ravishda i- korxonaga j ₋punktdan bir birlik homashyo yetkazish uchun ketadigan transport harajatlarini ifodalaydi. Aksariyat hollarda ishlab chiqarish korxonalari va homashyo yetkazib beruvchi punktlar muqobil, ya'ni moslashtirilgan holda ishlaydi deb hisoblanadi. Homashyo zaxiralari va korxonalarning bu homashyoga bo'lgan ehtiyojlari bir-biriga to'la mos keladi. Matematik tarzda bu shart

n m
∑b _j =∑d_i (1)


j=1 i=1
ko'rinishda ifodalanadi. Ayrim juz'iy chetlashishlarni hisobga olmaganda korxonalar to'liq quvvat bilan ishlaganda homashyolar to'liq sarflanadi. Faqat bu homashyolarni korxonalarga yetkazib berish kerak.
Masalaning matematik modelini ifodalash uchun yuqorida keltirilgan barcha shartlarni matematik munosabatlar bilan ifodalaymiz. Avvalo topilishi kerak bo'lgan optimal reja komponentlari j ₋punktdan i ₋korxonaga yetkazilishi kerak bo'lgan homashyo miqdorini X _ij deb belgilaymiz. Shartga ko'ra i ₋korxonaga yetkaziladigan barcha homashyo miqdori korxona ehtiyoji b_i ga teng bo'lishi kerak. Bu shartni

n
∑ X _ij = b_i i ₌1 , 2 , … , m (2)


j=1 ko'rinishda ifodalash mumkin, ya'ni barcha m ta korxona uchun bu shart bajarilishi kerak. Bunday shartni homashyo punktlari uchun ham ifodalash mumkin, ya'ni j - homashyo punktidan chiqarilgan jami homashyo miqdori d _j ga teng bo'lishi kerak.
Bu shart matematik tarzda


m
∑ x_ij = d _j j ₌1, 2 , …, n (3)


i=1 ko'rinishini oladi. Bu shartlar bajarilgan holda shunday x_ij larni topish kerakki jami yo'l harajatlari minimal bo'lsin. Keltirilgan normativlarga ko'ra i ₋korxonaga j ₋punktdan x_ij birlik homashyo keltiriladigan bo'lsa, yo'l xarajatlari bir birlik homashyo miqdori uchun C_ij ga teng ekanligi ma'lum bo'lgani uchun jami C_ij × x_ij pul birligiga teng bo'ladi. Bu xarajatlarni barcha korxonalar va homashyo bazalari bo'yicha qo'shib chiqsak jami xarajatlar kelib chiqadi va u quyidagicha ifodalanadi.

m n

L(x₁₁ , x₁₂ ,…, x_mn ) ₌∑∑C_ij ×x_ij → min (4)

i=1 j=1
Tabiiy, barcha chiziqli programmalash masalalarida bo'lganidek, bu yerda ham x_ij ≥ 0 bo'lishi kerakligi qayd etiladi.
Shunday qilib (1), (2), (3) shartlar bajarilgan holda (4) maqsad funksiyasining minimal qiymatini ta'minlovchi plan matritsasi X=( x_ij ) ni topish masalasi transport masalasi deyiladi. Bu yerda b₁ , b₂ , …, b_m , d₁ , d₂ , …, d_n berilgan miqdorlar ; C=(C_ij ) ham ma'lum matritsa. C(mxn) to'g'ri to'rtburchakli matritsa ham ma'lum matritsa deb hisoblanadi. Aksariyat hollarda x_ij noma'lumlar soni m×n shartlar soni m+n dan katta bo'lib, (1), (2), (3) shartlar bilan berilgan chiziqli algebraik tenglamalar sistemasi cheksiz ko'p yechimga ega bo'ladi. Ana shu cheksiz ko'p yechimlar orasidan (4) maqsad funksiyasining minimumini ta'minlovchi variant, ya'ni optimal plan (reja)ni tanlashni talab qilinadi.
Keltirilgan transport masalasining matematik modeli (1) – (4) ko'rinishiga qarab ortiqcha tafsilotlarsiz shuni qayd etishimiz mumkinki, kommunikatsion tizimlar : ular avtomabil, poyezd yo'li bo'ladimi, gaz yoki suv yetkazuvchi quvurlar bo'ldimi, elektr quvvatini yetkazuvchi yuqori kuchlanishli elektr uzatish tizimlari bo'ladimi barchasida shartli ravishda yetkazuvchi, iste'molchi va “transport” harajatlarini kiritish mumkin. Bu holda ham aynan (1) – (4) ko'rinishdagi optimallashtirish masalasini hosil qilishimiz mumkin.
Transport masalasi ifodalanishiga ko'ra nisbatan soddadek tuyulishi mumkin. Haqiqatdan ham barcha shartlar koeffitsientlari faqat birlardan iborat tenglamalar bo'ladi. Transport masalasining murakkabligi noma'lumlarni ko'pligida bo'lib unga odatdagi oddiy simpleks usulini tatbiq qilish ham imkoniyat darajasidan ancha yuqori bo'lib ketar ekan. Masalan n=10 , m=10 bo'lgan holda ham noma'lumlar soni n×m=100, shartlar soni esa m+n-1=19ta bo'lib, shartlar matritsasining rangi 19 bo'lgan holda (1) – (3) shartlar bo'yicha kelib chiqadigan tayanch yechimlar soni C₁₀₀¹⁹ ta bo'ladi. Simpleks usul esa tayanch yechimlaridan optimal yechimni ajratishga imkoniyat beradi. Bu holda simpleks usul bo'yicha necha qadam qo'yilishi kerak, buni tasavvur qilish ham qiyin. Agar transport masalasini biror tuman (miqyosida, masshtabida) qaralganda ham yetarlicha murakkab bo'ladi. Viloyat yoki respublika (miqyosida, masshtabida) qaraladigan bo'lsa masala yanada murakkablashib ketishi aniq.
Biz bu yerda transport masalasi ham odatdagi ChPM ekanligini, hamda unga ham simpleks usulni tatbiq qilish mumkinligini namoyish qilish maqsadida oddiy bir masalani ko'rib chiqamiz va tahlil qilamiz. Faraz qilaylik 2ta g'isht zavodi bo'lib ularning ishlab chiqarish quvvatlari mos ravishda 35 mashina va 45 mashina g'ishtga teng bo'lsin. Shuningdek bu g'ishtlarga talabgor 2 ta qurilish bo'lib, ularga mos ravishda 30 mashina va 50 mashina g'isht kerak bo'lsin. Talab va taklif muvozanati saqlangan. Agar 1 – qurilishga 1 – zavoddan 1 mashina keltirish narxi (yo'l xarajati) 15ming so'm, 2 – zavoddan keltirish narxi esa 12ming so'm; shuningdek 2 – qurilishga 1-, 2-zavoddan 1 mashina g'isht keltirish narxi mos ravishda 20ming va 18 ming so'm bo'lsin. Zavodlardan qurilishlarga g'isht yetkazib berish shunday rejasini tuzingki, transport harajatlari minimal bo'lsin. Transport masalasining shartlarini jadval ko'rinishida ifodalash tahlil uchun qulay bo'lganligi uchun odatda ularni jadval ko'rinishida ifodalagan ma'qul. Xususan yuqorida keltirilgan masala shartlarini quyidagi jadval ko'rinishida ifodalash mumkin.

zav
	1	2	Σ
1	15 x1	12 x2	30
2	20 x3	18 x4	50
Σ	35	45	80

jadvaldagi raqamlar masala mohiyatini aks ettiradi. So'nggi qatorda zavodlar quvvatlari, so'nggi ustunda esa qurilishlar ehtiyojlari aks etgan. Ichki kataklar tepa burchagida yo'l harajatlari koeffitsienti aks etgan. Bu yerda qulaylik uchun noma'lumlarni x₁ , x₂ , x₃ , x₄ deb belgilangan, aslida x₁₁ , x₁₂ , x₂₁ , x₂₂ bo'lishi kerak edi.

Bu yerda maqsad, masalani simpleks usulga tushirish qulay bo'lishi uchun shu yo'l tanlangan. Shartlarning matematik ifodasiga o'tamiz. x₁ +x₂ =30 1 x₃ +x₄ =50 2 x₁ +x₃ =35 3 x2 +x4 =45 4