Iqtisodiy jarayonlarda optimallashtirish usullarini qo’llash

Mustaqil yechish uchun topshiriqlar

Quyidagi transport masalalarini shimoli-g’arbiy usuli bilan boshlang’ich rejalarini yechimlarini toping.

1.

	120	200	180	100
200	2	1	4	1
150	2	3	3	2
250	3	2	3	2

2.

	100	60	70	170
90	5	7	4	9
120	2	3	3	5
190	1	6	8	2

3.

	150	170	190	210	180
250	7	9	16	10	16
350	13	12	18	12	20
300	9	15	10	13	13

4.

	170	160	190	200	180
280	4	9	6	5	9
340	3	2	8	2	7
280	9	5	10	7	3

5.

	180	120	90	105	105
150	7	9	6	3	16
250	7	11	7	12	14
200	6	15	10	8	5

Quyidagi transport masalalarini shimoli-g’arbiy usuli bilan boshlang’ich rejalarini yechimlarini toping.

6.

	120	100	180	100
100	8	9	4	10
150	6	1	9	12
250	3	7	11	2

7.

	50	80	70	30
80	12	14	4	10
60	20	13	14	7
90	9	12	13	11

8.

	120	200	180	100
200	21	10	40	10
150	22	30	32	20
250	13	12	31	21

4§.Transport masalasini yechish usullari

Reja:

4.1. Transport masalasini taqsimot usuli bilan yechish.

4.2. Transport masalasini potensiallar usuli bilan yechish.

4.1. Transport masalasini taqsimot usuli bilan yechish

Transport masalasini bu usul bilan yechishni sonli misolda qaraymiz. Transport masalasi 1-jadval bilan berilgan bo’lsin.

1-jadval

Ta’minlovchilar	Zahiralar	Iste’molchilar
	160 t	6	13	14	18	14
	400 t	25	14	7	5	16
	240 t	11	4	10	18	9
Talablar	800 t	170 t	190 t	140 t	180 t	120 t

Yechish: Bu masalada taminlovchilarning zahiralar miqdori iste’molchilarni talablari yig’indisiga teng. Demak, masala yopiq transport masalasidir. Birinchi rejani shimoliy-g’arbiy burchak usulidan foydalanib tuzamiz. iste’molchiga ta’minlovchidan 160 t rejalashtirib ta’minlovchini zahirasi tugadi. iste’molchi talabini qondirish uchun ta’minlovchidan 10 t rejalashtiramiz. ta’minlovchini zahirasi 10 t ga kamaydi. iste’molchini talabini qondirish uchun ta’minlovchidan 190 t rejalashtiramiz. ta’minlovchini zahirasi yana 190 t ga kamaydi. Zahirasi 200 t qoldi. iste’molchini talabini qondirish uchun ta’minlovchidan 140 t rejalashtiramiz. ta’minlovchini zahirasi yana 340 t ga kamaydi. Zahirasi 60 t qoldi. ta’minlovchini qolgan 60 t zahirasini istemolchiga rejalashtiramiz. iste’molchini talabini qondirish uchun ta’minlovchini zahirasidan 120 t rejalashtiramiz. ta’minlovchini zahirasidagi qolgan 120 t yukni iste’molchini talabini qondirish uchun rejalashtiramiz. Hamma ite’molchilar talabi qondirildi. Zahirada ham yuk qolmaydi. Bularni quyidagi jadvalda yozamiz.

Ta’minlovchilar	Zahiralar	Iste’molchilar
	160 t	6 160	13	14	18	14
	400 t	25 10	14 190	7 140	5 60	16
	240 t	11	4	10	18 120	9 120
Talablar	800 t	170 t	190 t	140 t	180 t	120 t

Bu tuzilgan jadvaldagi boshlang’ich rejani shimoliy-g’arbiy burchak usulidan foydalanib tuzdik. Bu masalada ta’minlovchilar soni , iste’molchilar soni to’ldirilgan katakchalar soni 7 ta. bo’lganligi uchun, olingan reja maxsus bo’lmagan reja bo’ladi.

Boshlang’ich taqsimlash uchun umumiy tashish harajatini hisoblaymiz:

so’m.

Endi tuzilgan rejaning optimal yoki optimalmasligini tekshiramiz. Buning uchun har bir to’ldirilmagan katakcha uchun yopiq siniq chiziq zanjiri (sikl) hosil qilib, ular bo’yicha baholarning algebraik yig’indisini hisoblaymiz. Masalan, 1-satr va 3-ustun uchun yopiq siniq chiziq zanjirini quyidagicha tuzamiz.

Bunda bo’sh katak ishorasi (+) bo’lib, qolganlari navbat bilan almashinadi (bu yerda navbat soat strelkasi yo’nalishi yoki unga qarama-qarshi yo’nalishda bo’lishi mumkin, uning farqi yo’q).

Bu baholar algebraik yig’indisini bilan belgilasak,

bo’ladi. Xuddi yuqoridagidek qolgan bo’sh kataklar uchun ular quyidagicha bo’ladi:

Baholar (ta’riflar) algebraik yig’indilarida manfiy sonlarning bo’lishi, tuzilgan reja optimal emasligini ko’rsatadi va rejani yaxshilash mumkin bo’ladi. Endi yangi reja tuzamiz, buning uchun manfiy sonlardan eng kichigi olinadi, ular bir necha bo’lsa, ixtiyoriysini olib taqsimlashni shu katak uchun tuzilgan yopiq siniq chiziq zanjiri bo’yicha o’zgartiramiz. Qaralayotgan misolda eng kichik manfiy algebraik yig’indi (-27) bo’lganligi uchun 3-satr 1-ustundagi katakcha uchun yopiq siniq chiziq zanjiri (sikl)ni qaraymiz:

Manfiy kataklardagi yuk miqdorining eng kichigini (bu 25 baholi katakchada bo’lib, 10 ga teng) olib, uni manfiy burchaklardan ayirib, musbat burchaklarga qo’shib, yangi reja hosil qilamiz. Bu o’zgarishni jadvalda amalgam o’zgarmaydi) quyidagi yangi rejani olamiz:


Bu o’zgarishni jadvalda amalga oshirib (boshqa katakchalardagi sonlar o’zgarmaydi) quyidagi yangi rejani olamiz:

Ta’minlovchilar	Zahiralar	Iste’molchilar
	160 t	6 160	13	14	18	14
	400 t	25	14 190	7 140	5 70	16
	240 t	11 10	4	10	18 110	9 120
Talablar	800 t	170 t	190 t	140 t	180 t	120 t

Bu tuzilgan yangi reja uchun yuk tashish jami bahosini hisoblaymiz:

so’m

Demak, umumiy harajat so’mga kamaydi. Endi tuzilgan rejaning optimalligini tekshiramiz. Buning uchun yana yangi tuzilgan rejadagi har bir to’ldirilmagan katakcha uchun yopiq siniq chiziq zanjiri (sikl) hosil qilib, bular bo’yicha baholarning algebraik yig’indisini hisobla chiqamiz.

va baholar manfiy, bulardan eng kichigi bo’lib 3-satr, 2- ustunda joylashgan katakcha uchun yopiq siniq chiziqlar zanjirini qaraymiz:
Bu zanjirda manfiy burchaklardagi eng kichik yuk 110 bo’lib, uni manfiy burchaklardan ayirib, musbat burchaklarga qo’shib, yaxshilangan rejani tuzamiz: Bu o’zgarishni jadvalda amalga oshirib yangi reja tuzamiz.

Ta’minlovchilar	Zahiralar	Iste’molchilar
	160 t	6 160	13	14	18	14
	400 t	25	14 80	7 140	5 180	16
	240 t	11 10	4 110	10	18	9 120
Talablar	800 t	170 t	190 t	140 t	180 t	120 t

Bu olingan reja bo’yicha umumiy harajatni hisoblaymiz.

so’m.

Umumiy harajat so’mga yaxshilandi. Endi tuzilgan rejaning optimalligini tekshiramiz.

Olingan rejadagi bo’sh katakchalar uchun baholarning algebraik yig’ indisini hisoblaymiz:

Tuzilgan yig’indilardan eng kichigi bo’lib 2-satr, 5- ustunda joylashgan katakcha uchun yopiq siniq chiziqlar zanjirini qaraymiz.

Bu zanjirda manfiy burchaklardagi eng kichik yuk 80 bo’lib, uni manfiy burchaklardan ayirib, musbat burchaklarga qo’shib, yaxshilangan rejani tuzamiz: Bu o’zgarishni jadvalda amalga oshirib yangi reja tuzamiz.

Ta’minlovchilar	Zahiralar	Iste’molchilar
	160 t	6 160	13	14	18	14
	400 t	25	14	7 140	5 180	16 80
	240 t	11 10	4 190	10	18	9 40
Talablar	800 t	170 t	190 t	140 t	180 t	120 t

Yangi olingan reja bo’yicha umumiy harajatni hisoblaymiz.

so’m.

Umumiy xarajat so’m oldingi rejaga nisbatan yaxshilandi. Bu rejani ham optimal yoki optimal emasligini tekshiramiz.

Olingan rejadagi bo’sh katakchalar uchun baholarning algebraik yig’indisini hisoblaymiz:

Shunday qilib, tuzilgan reja uchun baholarning algebraik yig’indilari ichida manfiylari yo’q, shuning uchun bu tuzilgan reja optimal bo’lib, umumiy harajat 5350 so’m bo’ladi va uni endi yaxshilash mumkin emas.