Бұрын қорлар мен сұраныстардың бір уақытта нөлге тең болатын жағдайы кездесетінін айтқан болатынбыз
Есептеу алгоритмі: ең кіші элементтер әдісі
Алдыңғы жағдайдағыдай жалпы түсініктемелерге толық тоқталмай, есептеу алгоритмін келтіреміз. Әдісті пайдалану тәртібі бұрын көрсетілген. Бұл әдістің ерекшелігі — әр ұяшықтағы тасымалдау құндары (шығындар) есепке алынады. Есептеу кезеңдерін Рим цифрларымен белгілейік.
Бастапқы көлік қатынасы кестесі
| Жіберуші | 1 | 2 | 3 | Қор (a) |
|---|---|---|---|---|
| 1 | 5 | 10 | 12 | 120 |
| 2 | 8 | 6 | 4 | 70 |
| 3 | 0 | 0 | 0 | 50 |
| Сұраныс (b) | 60 | 100 | 80 | — |
I кезең
Есепті ең кіші элементтер орналасқан ұяшықтарды анықтаудан бастаймыз.
Ең кіші элементтер (3,1), (3,2) және (3,3) ұяшықтарында орналасқан. Мысал ретінде (3,2) ұяшығын таңдаймыз.
Есептеу:
x32 = min{50, 100} = 50
a3 = 50 − 50 = 0
b′2 = 100 − 50 = 50
3-жол сарқылғандықтан, оны әрі қарай қарастырудан алып тастаймыз.
II кезең
Қалған ұяшықтардың ішінде ең кіші элемент (2,3) ұяшығында орналасқан.
Есептеу:
x23 = min{70, 80} = 70
a2 = 70 − 70 = 0
b′3 = 80 − 70 = 10
2-жол сарқылғандықтан, оны қарастырудан алып тастаймыз.
III кезең
Ең кіші элемент (1,1) ұяшығында.
Есептеу:
x11 = min{120, 60} = 60
a1 = 120 − 60 = 60
b′1 = 0
1-бағана қарастырудан алынады: 1-тұтынушының қажеттілігі өтелді.
IV кезең
Ең кіші элемент (1,2) ұяшығында.
Есептеу:
x12 = min{60, 50} = 50
a1 = 60 − 50 = 10
b′2 = 0
Ағымдағы кестеде бір ғана (1,3) ұяшығы қалады. 2-тұтынушының қажеттілігі толық өтелді.
V кезең
Соңғы (1,3) ұяшығын таңдаймыз.
Есептеу:
x13 = min{10, 10} = 10
a1 = 0, b′3 = 0
Кесте сарқылды. Есептеу аяқталды: барлық тұтынушылардың қажеттіліктері өтелді.
Тасымалдаудың жалпы құны
Табылған тасымал құны:
J = 60·5 + 50·10 + 10·12 + 70·4 + 50·0
J = 300 + 500 + 120 + 280 = 1200
Солтүстік-батыс бұрышы әдісімен салыстырғанда бастапқы жоспар 60 бірлікке арзандағанын көреміз. Алайда (3,1) орнына (3,2) ұяшығын таңдасақ, бастапқы жоспардың қымбаттауы мүмкін екеніне көз жеткізуге болады. Оны өз беттеріңізбен орындап көріңіз.
Туындыланған жағдай: қор мен сұраныс бір уақытта нөлге тең болғанда
Бұрын қорлар мен сұраныстардың бір уақытта нөлге тең болатын жағдайы кездесетінін айтқанбыз. Мұндай жағдай туындыланған (дегeнерацияланған) деп аталады. Нақты мысал арқылы туындыланған жағдайда бастапқы тасымалдау жоспары қалай анықталатынын қарастырайық.
Берілген көлік қатынасы кестесі
| Жіберуші | 1 | 2 | 3 | Қор (a) |
|---|---|---|---|---|
| 1 | 7 | 4 | 8 | 100 |
| 2 | 9 | 12 | 6 | 80 |
| 3 | 2 | 6 | 11 | 90 |
| Сұраныс (b) | 100 | 120 | 50 | — |
Солтүстік-батыс бұрышы әдісімен бастау
Солтүстік-батыс бұрышы — (1,1) ұяшығы.
Есептеу:
x11 = min{100, 100} = 100
a1 = 0, b′1 = 0
Бұл жерде қор да, сұраныс та бір уақытта сарқылды. Сондықтан бірден 1-жол мен 1-бағананы қарастырудан алып тастаймыз.
Назар аударыңыз: ұяшық санының жеткіліксіздігі
Әдісті сол күйі жалғастырсақ, нәтижесінде (m + n − 1) = 3 + 3 − 1 = 5 ұяшық толтырылуы керек болғанымен, тек 4 ұяшық алынуы мүмкін. Айқын болу үшін 1-тұтынушының сұранысы қанағаттандырылды деп есептеп, оны қарастырудан алып тастаймыз, ал 1-жіберушінің қоры нөлге тең деп қабылдаймыз.
Келесі қадам: нөлдік тасымалдауды енгізу
Кестемен бұрынғыша жұмыс жасаймыз. Солтүстік-батыс бұрышы ретінде (1,2) ұяшығы алынады және шамасы нөлге тең жүк бірлігі тасымалданады.
| Жіберуші | 1 | 2 | 3 |
|---|---|---|---|
| 1 | 0 | — | — |
| 2 | 80 | — | — |
| 3 | 90 | — | — |
| Сұраныс (b) | 100 | 120 | 50 |
Кесте 7-де толтырылған ұяшықтар саны бесеу болады.