Identifikatsiyalash

2.1.1.Transport masalasining tayanch rejasini topish usullari


Transport jadvalini tuzish. Chiziqli programmalashtirish amaliyotga tadbiqlaridan biri transport masalasidir. Transport masalasining qoʻyilishi quyidagicha: m ta joʻnatish punkti mavjud boʻlib, ularga mos ravishda miqdorli bir jinsli tovar mavjud boʻlsin. Shuningdek n ta qabul qilish punkti mavjud boʻlib, ularga mos ravishda tovarga talablar boʻlsin. Bunda

shart bajarilsin. Shuningdek bir birlik tovarni joʻnatish harajati ma’lum boʻlsin . Talab qilinadi, 1-barcha talablar bajarilsin, 2-bunda tashish harajati minimal boʻlsin. Bu masalaga matematik koʻrinish beramiz. Buning uchun i dan j qabul qilish punktiga olib boriladigan yukning hajmini deb belgilaymiz. Bunda . Shu asosida tenglamalar sistemasi tuziladi: joʻnatish punktiga nisbatan:
,
qabul qilish punktiga nisbatan esa:
.
Maqsad funksiyani olamiz:

Chiziqli programmalashtirishdan bu masalaning farqi shundaki: 1-dan, chegaraviy shartlar tenglama sifatida beriladi. 2-dan, oʻzgaruvchilarning koeffitsientlari 1 ga teng.
Bu masalani echishda transport jadvali tuzib olinadi.

	B1		B2		... ... ...	Bn		Zahira
A1		C11		C12			C1n	a1
A2		C21		C22			C2n	a2
... ... ...								... ... ...
Am		Cm1		Cm2			Cmn	am
Talab	b1		b2		... ... ...	bn

Transport masalasini echish 3 bosqichdan iborat:

1. 
   Transport jadvalini tuzish.
   
2. 
   Tayanch rejani aniqlash.
   
3. 
   Optimal rejani aniqlash.
   

Tayanch rejani topishning 3 xil usuli mavjud:

1. 
   Shimoli-Gʻarbiy burchak usuli.
   
2. 
   Minimal elementlar usuli.
   
3. 
   Fogel usuli.
   

Shimoli-gʻarbiy burchak usuli. (Shgʻb). Shgʻb qoidasi moxiyati quyidagilardan iborat: TJ tuziladi, keyin chap yuqori (Shgʻ) burchakdan boshlab qator boʻyicha oʻnga yoki ustun boʻyicha pastga qarab (1,1) katakka a₁ va b₁ sonlardan kichigini kiritamiz, ya’ni (a₁b₁).
Agar a₁>b₁, boʻlsa x₁₁=b₁ va birinchi ustun yopilpdi. Qolgan kataklarni esa qilib olinadi. Bu esa birinchi talabgar (QQP) toʻliq ta’minlangan xisoblanadi. Va ikkinchi ustinnig birinchi katagiga (1,2) esa a₁-b₁ va b₂ sonlardan kichigini ya’ni ni kichigini kiritamiz.
Agar b₁=a₁, boʻlsa x₁₁=a₁ va birinchi qatorning birinchi kataklari x_1k=0 K=2, n qilib olinadi. Va keyingi qatorning birinchi katagiga (2,1) boʻladi. Ikkinchi katakni toʻldirgandan keyin (1,2) yoki (2,1) keyingi 3-katakka oʻtiladi yoki qator, yoki ustun boʻyicha jarayon to xamma yukni taqsimlanib tugaguncha davom etadi.

1.