3-5 iqtim 20 3- bosqich talabasi

0

250	4 1	1 200	2 50	5 6	4 3	-1
200	5 1	3 1	3 2	6 - 100	3 + 100	-1
300	3 100	4 3	4 50	3 8 +	5 - 150	1
Vj	2	2	3	7	4

2- босқич

Ишлаб чиқарув- чилар ва маҳсу- лот миқдори	Истеъмолчилар ва истеъмол миқдорлари						Ui
	200	200	100	100	250
100	2 100	5 2	3 3	2 2	6 4	0
250	4 1	1 200	2 50	5 1	4 3	-1
200	5 1	3 1	3 2	6 1	3 200	-1
300	3 100	4 3	4 50	3 100	5 50	1
Vj	2	2	3	2	4

Оптимал ечим ҳосил бўлди:
X₁₁ = 100; ­­X₂₂ = 200; ­­X₂₃= 50; ­­X₃₅ = 200
­­X₄₁ = 100; X₄₃ = 50; ­X₄₄ = 100; ­­X₄₅ = 50
F = 2100 + 1200 + 250 + 3200 + 3100 + 450 + 3100 + 550 = 2350
(пул бирлиги).
Очиқ моделли транспорт масаласи
Юқорида талаб ва таклифларнинг умумий миқдорлари тенг бўлганда масала «ёпиқ моделли транспорт масаласи» дейилади, деган эдик. Акс ҳолда масала очиқ моделли бўлиб унинг оптимал ечимини топиш учун ёпиқ моделга келтирилади ва потенциаллар усули қўлланилади.
Очиқ моделли масалани ёпиқ моделга келтириш учун қўшимча «сохта» таъминотчи ёки истеъмолчи киритилади, уларнинг заҳираси ёки талаб ҳажми
a_m+1 = b_j - a_i ёки b_n+1 = a_i - b_j бўлади. Сохта таъминотчидан реал истеъмолчиларга ёки реал таъминотчилардан сохта истеъмолчиларга амалда юк ташилмагани учун йўл харажатлари нолга тенг қилиб олинади (C_i,n+1 = 0; C_m+1,j = 0).
Натижада ёпиқ моделли масала ҳосил бўлади.
3-мисол: a_i > b_j – бўлган ҳол, учун масалани ечинг.

Таъминотчи-лар	Истеъмолчилар							Заҳира ҳажми
	B1	B2	B3	B4	B5	Bn+1
A1	10	7	4	1	4	0	100
A2	2	7	10	6	11	0	250
A3	8	5	3	2	2	0	200
A4	11	8	12	16	13	0	300
Талаб ҳажми	200	150	100	100	200	100

1.Transport masalasining matematik modeli
Yuklarni jo‘natish punktlaridan berilgan qabul qilish punktlariga tashib berishning optimal planini topish masalasiga transport masalasi deyiladi va u quyidagicha formulirovka qilinadi:
Aytaylik А₁,А₂,..,А_m punkitlarida ularga mos а₁,а₂,...,а_m miqdordagi bir jinsli yuklar joylashgan bo‘lsin. Bu А₁,А₂,..,А_m -larga jo‘natish punktlari deymiz. Bu yuklarni n-ta В₁,В₂,...,В_n punktlari qabul qilishi kerak bo‘lib va ularning talablari mos ravishda b₁,b₂,...,b_n bo‘lsin. Har bir x_ij -birlikdagi yukni i-chi jo‘natish punitidan j-chi qabul qilish punitiga olib borish narxi (xarajati) c_ij -ma'lum bo‘lsin. Bu yuklarni tashish planini shunday tuzishimiz kerakki talabgor punktlar maksimal qoniqish olsin va hamma yuklarni olib borish uchun ketgan xarakatlar yig‘indisi minimal bo‘lsin.
Transport masalasini shartli ravishda jadval ko‘rinishda beramiz. Jadvalda quyidagilar ko‘rsatiladi: qabul qilish punitlari, jo‘natish punktlari, yuk zapaslari, yukka bo‘lgan ehtiyoj va har bir i-chi jo‘natish punktidan j-chi qabul qilish punktiga yuboriladigan yuk birliklarining narxi (ya'ni tarif matritsasi) beriladi.

Jo‘natish	Qabul qilish punktlari					Yuk
punkitlari	B1	B2	. . . .	Bn	zapastlari
A1	с11 x11	c12 x12	. . . .	c1n x1n	a1
A2	с21 x21	c22 x22	. . . .	c2n x2n	a2
. . .	. . . .	. . . .	. . . .	. . . .	. . .
Am	сm1 xm1	cm2 xm2	. . . .	cmn xmn	an
Yukka bo‘lgan ehtiyoj	b1	b2	. . . .	bn	еai=еbj

Bu yerda C=c_ij} matritsasiga tarif matritsasi yoki transport xarajatlari deyiladi. X=x_ij} matritsaga esa transport masalasining plani deyiladi. Bu yerda x_ij- i-chi punktdan j-chi punktga yetkaziladigan yuklar hajmi (soni). Tashish plani bilan bog‘liq ketgan xarajatlarning umumiy yig‘indisi quyidagi maqsad funksiyasi orqali ifodalanadi.

Z= c₁₁x₁₁+c₁₂x₁₂+ . . . +c_1nx_1n+ c₂₁x₂₁+c₂₂x₂₂+ . . . +c_2nx_2n+ . . .
c_m1x_m1+c_m2x_m2+ . . . +c_mnx_mn .
Bu yerda x_ij-o‘zgaruvchilar yuk zapasi, yukga bo‘lgan ehtiyoj va manfiy bo‘lmaslik shartlarini (chegaralanishlarni) bajargan bo‘lishi kerak.
Yuqoridagilarni hisobga olgan holda transport masalasining matematik modelini quyidagicha yozish mumkin.

Transport masalasining matematik qo‘yilishi quyidagicha talqin qilinadi: Chegaraviy tizimlar, manfiy bo‘lmaslik sharti va maqsad funksiyasi berilgan deylik. Talab qilinadiki tizimning yechimlar to‘plamidan shunday manfiy bo‘lmagan yechimlarini (planini) topish kerakki, maqsad funksiyasi minimal qiymatga erishsin.
Transport masalasi ikki turga bo‘linadi, ochiq va yopiq turdagi. Agar yuk zapaslari yig‘indisi talab qilingan yuklar yig‘indisiga teng bo‘lsa, ya'ni

masala yopiq turdagi masala bo‘ladi
Agar yuk zapaslari yig‘indisi talab qilingan yuklar yig‘indisiga teng bo‘lmasa, ya'ni

masala ochiq turdagi masala bo‘ladi.


2.Transport masalasini yechish usullari

Transport masalasini yechish ikki bosqichdan iborat.

1.Boshlang‘ich tayanch planni topish.
2.Tayanch planlar ichidan optimal planni topish.
Tayanch planni tuzishning bir necha usullari mavjud: "Shimoliy-g‘arb burchak", "Kichik elementlar", "Fogel'" va boshqalar.


"Shimoliy-g‘arb burchak" usuli.
Yuklarni tashishning boshlang‘ich planni tuzishda "shimoliy-g‘arb burchak" usulidan foydalanish quyidagicha amalga oshiriladi:

1.Tarif jadvali tuziladi.

	b1	b2	. . . . .	bn
a1	с11	c12	. . . . .	c1n
a2	с21	c22	. . . . .	c2n
. . . . .	. . . . .	. . . . .	. . . . .	. . . . .
am	сm1	cm2	. . . . .	cmn

2.Chap tomondagi yuqoridagi burchak, ya'ni (shimoliy-g‘arb burchak) dan boshlab satr bo‘yicha yoki ustun bo‘yicha siljiymiz. (1,1) katakga a₁ va b₁ ning eng kichigini joylashtiramiz, ya'ni x₁₁=min(a₁,b₁).
3.Agar a₁>b₁ bo‘lsa x₁₁=b₁ ni beramiz, birinchi ustun shu bilan yopiladi, ya'ni x_i1=0 (i=2,m). (Birinchi qabul qiluvchining talabi to‘liq qanoatlantirildi).
4.Birinchi satr bo‘yicha siljiymiz (1;2) katakga, bu yerga a₁-b₁,b₂ ning eng kichigini joylashtiramiz, ya'ni x₁₂=min(a₁-b₁,b₂).
5.Agar b₁>a₁ bo‘lsa 1-chi satr yopiladi, ya'ni x_1j=0 (j=2,n).
6.Qo‘shni kataklarni to‘ldirishga o‘tamiz (2.1), ya'ni x₂₁=min(a₂,b₁-a₁).
7.Ikkinchi satr yoki ikkinchi ustun kataklarini to‘ldirishga o‘tamiz va hakazo.Bu jarayon toki resurslar tugamaguncha davom etadi.