9-10. Mavzu. Transport masalasining optimal yechimlarini topish Reja

9-10.Mavzu. Transport masalasining optimal yechimlarini topish


Reja:

1. Optimal yechimlarni topish usullari.

2. Potensiallar usulining mohiyati.
3. Optimal usulni yechishning algoritmi.

Transport masalasini optimal yechimini topishning 2 xil usuli mavjud:

1. 
   Taqsimot yoki Gomori usuli.
   

2. 
   Potensiallar usuli.
   

Taqsimlash usulida bo`sh kataklarga nisbatan berk sikl tuziladi.

Berk sikl deb, transport jadvalining qatori va ustunidagi 2 ta katakni o`zaro birlashtirib turuvchi va ohiri boshlanish katagiga mos tushadigan chiziqqa aytiladi. Taqsimot usuli Simpleks usuliga o`xshash bo`lib, barcha bo`sh kataklarga yuk tashlash imkoniyati tekshirib chiqiladi. Bu jarayon anchagina murakkabdir. Shuning uchun potensiallar usuli keng qo`llaniladi.

Potensiallar usulining mohiyati quyidagichadir: tayanch reja topilgandan so`ng jo`natuvchi punktlarga U_i, qabul qiluvchi punktlara V_j belgisini kiritamiz. Bu belgilashlar potensiallar deyiladi. potensiallar yig`indisi kataklarning tariflariga teng bo`ladi. Agarda tayanch reja bazis yechim bo`lsa, ya’ni band kataklar soni r = m+n-1 ga teng bo`lsa, hamda band kataklar uchun berk siklni topish imkoni bo`lmasa, band va bo`sh kataklar uchun tenglamalar sistemasi tuziladi. Tenglamalar sistemasidagi o`zgaruvchilar soni m+n ga teng bo`ladi va tenglamalar soni r ga teng bo`ladi. Shuning uchun band kataklarga nisbatan tuzilgan tenglamalar sistemasining ixtiyoriy o`zgaruvchisiga 0 qiymati berilib, U_i va V_j ning qiymatlari aniqlanadi. Bu qiymatlar bo`sh kataklar uchun tuzilgan tenglamalar sistemasiga qo`yiladi.

Agarda bu sistemada shart bajarilsa, optimal yechim topilgan hisoblanadi. Aks holda bajarilgan bo`sh katakka yuk tashlanadi. Qaysi band katakka yuk tashlash bo`sh katakka nisbatan tuzilgan berk sikl orqali aniqlanadi. Berk siklda faqatgina uning bitta tuguni bo`sh katakda yotadi, qolganlari esa band katakda yotishlari zarur. Toq sonli kataklar “+”, juft katakdagi sonlar esa “-” deb belgilanadi. “-” ishorali eng kichik yuk hajmi topilib, unga nisbatan o`zgartirish amalgam oshiriladi.