Ең кіші элемент әдісін пайдаланып алғашқы базисті табу

Алдыңғы жағдайдағыдай жалпы түсініктемелерге толық тоқталмай-ақ есептеу алгоритмдерін келтіреміз. Әдісті пайдаланып, шығару жолы бұрын келтірілген. Сонымен, бұл әдістегі ерекшелік әрбір ұяшықтардағы тасымалдау құндарының есепке алынатындығы. Әр есептеу кезеңдерін Рим цифрларымен белгілейік. Алдымен көлік қатынасы кестесін қайтадан құрамыз.

Кесте 4

I.   Есепті шығаруды ең кіші элементтер орналасқан ұяшықтарды анықтаудан
бастаймыз.

1 .   Ең кіші элементтер (3, 1), (3, 2) жэне (3, 3) ұяшықтарында орналасқан.
Мысалы: (3, 2) ұяшығын таңдап алайық.

2.        x₃₂ =тіп{50,100}=50

1. а₃ =50-50 = 0,               Ь’₂ =100-50 = 50
2. 3-ші жолды қарастырудан ойша алып тастаймыз. (3, 2) ұяшығын тұтас
   сызықпен, жолдың қалған ұяшықтарын пунктир сызықтармен ерекшелейміз.

II.   1.   Қалған  кесте  ұяшықтарының  ішінен  —  (2,   3)  -те  ең  кіші  элемент
орналасқандығы көрініп тұр.

1. x₂₃ =шіп {70,80} =70
2. а₂=70-70 = 0,            Ь’₃ =80-70 = 10
3. Сарқылуына байланысты екінші жолды қарастырудан алып тастаймыз.

III.  1. Ең кіші элемент (1, 1) ұяшығында.

1. х_п =шіп{і20,60} =60
2. а[ = 120-60 = 60,*; =0.
3. Бірінші бағананы қарастырудан ойша шығарамыз. 1-ші тұтынушының
   қажеттілігі өтелді.

IV.   1. Ең кіші элемент (1,2) ұяшығында.

2.         x₁₂ =шіп{б0,50}=50

1. а[ =60-50 = 10,Ь’₂ =0.
2. Ағымдағы кестеде бір ғана (1,3) ұяшығы қалады. 3 -ші тұтынушының
   қажеттілігі өтелді. (1, 2) ұяшығын тұтас сызықпен ерекшелейміз.

V.  1. Соңғы (1,3) ұяшығын таңдаймыз.

1. x₁₃ =шіп{Ю,10}=10
2. а[=Ь’₃=0
3. Кесте сарқылды. Есептеу аяқталды. Барлық тұтынушылар қажеттіліктері
   өтелді.

Табылған тасымал құны

/^жэ = 60 • 5 + 50 • 10 +10 • 12 + 70 • 4 + 50 • 0 = 300 + 500 +120 + 280 = 1200

Алдыңғы «солтүстік -батыс» бұрышы эдісімен салыстырғанда 60 бірлікке алғашқы жоспардың кемігенін көреміз.

Бірақ, (3, 1) орнына (3, 2) -ұяшығын алсақ, алғашқы жоспардың алдыңғы жағдайға қарағанда қымбатқа түсетініне көз жеткізуге болады. Оны өз беттеріңмен орындауға ұғынамыз.

Бұрын қорлар мен сұраныстардың бір уақытта нөлге тең болатын жағдайы кездесетінін айтқан болатынбыз. Ол жағдай туындыланған деп аталады. Нақты мысал қарастыру арқылы туындыланған жағдайда алғашқы тасымалдау жоспарының қалай анықталатындығына тоқталайық. Көлік қатынасы кестесі келесі түрде берілсін.

Кесте 5

«Солтүстік -батыс» бұрышы әдісін пайдаланайық.

1. «с — б» бұрышы — (1, 1)
2. х_и =тіп{Ю0,100}=100
3. а_х =0,*і =0.

Қор да, қажеттілік те бір уақытта сарқылды.

Сонда бірден 1 -ші жол мен бағананы қарастырудан алып тастаймыз. Әдісті пайдалануды жалғастырсақ, онда нәтижесінде келесі кестеге келеміз.

Кесте 6

(т+п-1) = 3+3-1 =5 -ұяшық шығу орнына 4 үяшық алынып тұр. Сондықтан айқын болу үшін 1- ші тұтынушының сұранысы қанағаттанды деп, оны қарастырудан алып тастаймыз. Ал, 1 -ші жіберушінің шамасы нөлге тең қоры бар деп есептейміз.Келесі Кесте -3-ке келеміз. Кестемен бұрыңғыша жұмыс жасаймыз. «Солтүстік -батыс» бұрышы -(1,2). Шамасы нөлге тең жүк бірлігі тасымалданады.

Кесте  7

  Кесте -7 -те толтырылған ұяшықтар саны бесеу