Transport masalasining boshlang’ich mumkin bo’lgan yechimlari

1.6.2 Eng kam xarajatlar usuli
Ta'rif: Eng kam xarajat usuli - bu transport muammosining dastlabki mumkin bo'lgan echimini olish uchun qo'llaniladigan yana bir usul. Bu erda ajratish minimal narxga ega bo'lgan hujayradan boshlanadi. Kam xarajatli katakchalar eng kam xarajatga ega bo'lish maqsadida yuqori xarajatli hujayradan tanlanadi.
Algoritm
1-qadam: Butun jadaval bo’yicha eng kichchik son aniqlanadi, u son joylashgan katakga unga mos talab va taklifning minimumi beriladi, ya’ni min(talab;taklif).
2-qadam: Birinchi qadamda quyidagi uchta holat bo’lishi mumkin:
a) Agar talab va taklif teng bo’lsa u holda minimum shu ikkala son o’ladi, bu sonlar tanlangan katakga taminlanadi natijada o’sha satr va ustundagi taklif va talab 0 ga aylanadi. O’sha satr va o’sha ustun o’chiriladi keyin qolgan jadval uchun yana 1-qadam takrorlanadi.
b) Agar talab taklifdan katta bo’lsa u holda min(talab;taklif)=taklif , tanlangan katakga taklif qiymati beriladi, tanlangan katakga mos taklif qiymati 0 ga, talab qiymati esa talab va taklif qiymatlari ayirmasiga o’zgaradi, taklif qiymati 0 ga aylangani uchun o’sha satr o’chiriladi qolgan jadval uchun 1-qadam takrorlanadi.
c) Agar taklif talabdan katta bo’lsa u holda min(talab;taklif)=talab, tanlangan katakga talab qiymati beriladi, tanlangan katakga mos talab qiymati 0 ga, taklif qiymati
esa taklif va talab qiymatlari ayirmasiga o’zgaradi, talab qiymati 0 ga aylangani uchun o’sha ustun o’chiriladi qolgan jadval uchun 1-qadam takrorlanadi.
3-qadam: Talab va takliflarning barcha qiymati 0 ga aylanguncha yuqoridagi qadanlar takrorlanadi va boshlang’ich mumkin bo’lgan yechim sifatida talab va takliflar taqsimlangan katakchalardagi sonlarning ularga mos talab yoki taklif qiymatlari ko’patmalarining yig’indisi olinadi.
Shimoliy -g'arb burchak usuli
Shimoli-g'arbiy burchak tushunchasini quyida keltirilgan transport muammosi orqali yaxshi tushunish mumkin:

	B1	B2	B3	Taklif
A1
A2
A3
Talab

Shimoli-g'arbiy burchakni quyida transport muammosi orqali yechish mumkin:

	B1	B2	B3	Taklif
A1	5	3	6	60
A2	4	4	7	35
A3	6	8	2	55
Talab	75	30	45

va uchun talab va takliflarning mos qiymatlari solishtiriladi. Ikkisining kichigi, ya'ni ga tayinlangan.
Bu quvvatini tugatadi va bilan 75 - 60=15 birlik qoldiradi
Jadval-1

	B1	B2	B3	Taklif
A1	5(60)	3	6	0
A2	4	4	7	35
A3	6	8	2	55
Talab	15	30	45

Vertikal harakatlaning, va uchun talab va takliflarning mos qiymatlari solishtiriladi. Ikkisining kichigi, ya'ni ga tayinlangan. Bu ning to'liq talabini qondiradi va bilan 35 - 15=20 birlik qoldiradi

Jadval-2

	B1	B2	B3	Taklif
A1	5(60)	3	6	0
A2	4(15)	4	7	20
A3	6	8	2	55
Talab	0	30	45

Gorizontal harakatlaning, va uchun talab va takliflarning mos qiymatlari solishtiriladi. Ikkisining kichigi, ya'ni ga tayinlangan. Bu sig'imini tugatadi va bilan 30 - 20=10 birlik qoldiradi
Jadval-3

	B1	B2	B3	Taklif
A1	5(60)	3	6	0
A2	4(15)	4(20)	7	0
A3	6	8	2	55
Talab	0	10	45

Vertikal harakatlaning, va uchun talab va takliflarning mos qiymatlari solishtiriladi. Ikkisining kichigi, ya'ni ga tayinlangan. Bu ning to'liq talabini qondiradi va bilan 55 - 10=45 birlik qoldiradi

Jadval-4

	B1	B2	B3	Taklif
A1	5(60)	3	6	0
A2	4(15)	4(20)	7	0
A3	6	8(10)	2	45
Talab	0	0	45

Gorizontal harakatlaning, va uchun talab va takliflarning mos qiymatlari solishtiriladi. Ikkisining kichigi, ya'ni ga tayinlangan.
Jadval-5

	B1	B2	B3	Taklif
A1	5(60)	3	6	0
A2	4(15)	4(20)	7	0
A3	6	8(10)	2(45)	0
Talab	0	0	0

Dastlabki mumkin bo'lgan yechim

	B1	B2	B3	Taklif
A1	5(60)	3	6	60
A2	4(15)	4(20)	7	35
A3	6	8(10)	2(45)	55
Talab	75	30	45

Minimal umumiy transport xarajatlari =5×60+4×15+4×20+8×10+2×45=610

Bu erda ajratilgan hujayralar soni = 5 m + n - 1 = 3 + 3 - 1 = 5 ga teng.
Eng kam xarajat usuli
Eng kam xarajat usuli shimoli-g'arbiy burchakdan ko'ra maqbulroq natijalar beradi deb hisoblanadi, chunki u taqsimlashda yuk narxini hisobga oladi, shimoliy-g'arbiy burchak usuli esa faqat mavjudligi va ta'minot talabini hisobga oladi va taqsimlash o'ta chap burchakdan boshlanadi, etkazib berish narxidan qat'i nazar.
Keling, quyida keltirilgan muammo orqali eng kam xarajat usuli tushunchasini tushunib olaylik:

	B1	B2	B3	Taklif
A1	5	3	6	60
A2	4	4	7	35
A3	6	8	2	55
Talab	75	30	45	150

Yechim: Ta'minot cheklovlarining umumiy soni: 3

Talab cheklovlarining umumiy soni: 3
Muammo jadvali

	B1	B2	B3	Taklif
A1	5	3	6	60
A2	4	4	7	35
A3	6	8	2	55
Talab	75	30	45

Eng kichik transport xarajati yacheykasida 2 ta Ushbu katakchaga taqsimlanish Bu ning to'liq talabini qondiradi va bilan 55 - 45 = 10 birlik qoldiradi.

Jadval-1

	B1	B2	B3	Taklif
A1	5	3	6	60
A2	4	4	7	35
A3	6	8	2(45)	10
Talab	75	30	0

Eng kichik transport xarajatlari katagida 3 ta Ushbu katakchaga taqsimlanish . Bu ning barcha talabini qondiradi va bilan 60 - 30 = 30 birlik qoldiradi.

Jadval-2

	B1	B2	B3	Taklif
A1	5	3(30)	6	30
A2	4	4	7	35
A3	6	8	2(45)	10
Talab	75	0	0

Eng kichik transport xarajati katagida 4 ta Ushbu katakchaga taqsimlanish Bu quvvatini tugatadi va bilan 75 - 35=40 birlik qoldiradi

Jadval-3

	B1	B2	B3	Taklif
A1	5	3(30)	6	30
A2	4(35)	4	7	0
A3	6	8	2(45)	10
Talab	40	0	0

Eng kichik transport xarajati katagida 5 ga teng. Ushbu katakchaga taqsimlanish Bu quvvatini tugatadi va bilan 40 - 30=10 birlik qoldiradi

Jadval-4

	B1	B2	B3	Taklif
A1	5(30)	3(30)	6	0
A2	4(35)	4	7	0
A3	6	8	2(45)	10
Talab	10	0	0

Eng kichik transport xarajati yacheykasida 6 ga teng. Ushbu katakchaga taqsimlanish
Jadval-5

	B1	B2	B3	Taklif
A1	5(30)	3(30)	6	0
A2	4(35)	4	7	0
A3	6(10)	8	2(45)	0
Talab	0	0	0

Dastlabki mumkin bo'lgan yechim

	B1	B2	B3	Taklif
A1	5(30)	3(30)	6	60
A2	4(35)	4	7	35
A3	6(10)	8	2(45)	55
Talab	75	30	45

Minimal umumiy transport xarajatlari =5×30+3×30+4×35+6×10+2×45=530

Bu erda ajratilgan hujayralar soni = 5 m + n - 1 = 3 + 3 - 1 = 5 ga teng.