Ф-жоокб-01/018 Қазақстан республикасы білім және ғылым министрлігі

Жоғарыда қарастырылған тәсіл боынша үйлестіру тасымалдауға жұмсалынатын қаржыны есепке алмайды. Ол үшін ең кіші элементи тәсілін пайдалануға болады. Ең кіші элемент тәсілі бойынша кестеден ең кіші элемент орналасқан кереге көзді толтырудан бастаймыз; ал қалғандары жоғарыда көрсетілген тәсілден шаррдың орындалуын қамтамасыз етуге тиіс. Жоғарыдағы мысалды қарастырайық.

Бұл есептегі ең кіші элемент 2-ге тең; ол үш рет кездеседі; олардың кез- келгенінен бастауға болады. Біз бірінші жолда орналасқаннан бастайық. Кестенің осы кереге көзіне 110 санын жазамыз, немесе екінші пайдаланушы В₂ өзіне қажетті барлық жүкті бірініші қоймадан ең арзщан қаржы жұмсап алады, немесе х₁₂ = 110; ол басқа қоймадан жүк алмайды.

х₂₁ = х₃₂ = 0 .

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

х₁₁ = 100; х₁₂ = 110; х₁₃ = 0; х₁₄ = 40; х₁₅ =0;

х₂₁ = 100; х₂₂ = 0; х₂₃ = 10; х₂₄ = 0; х₂₅ = 130;

х₃₁ = 0; х₃₂ = 0; х₃₃ = 80; х₃₄ = 60; х₃₅ = 0;

F = 2 ∙ 110 + 3 ∙40 + 2 ∙ 100 + 4∙10 + 2 ∙80 + 4∙60 + 6∙130 = 1760

Ескерту. Тасымалдау кестесін толтыру кезінде толтырылған (х_1j≠0) кереге көздер саны n+m -1- ге тең болуы керек.

а) Жүк қоймалары мен оны алушылардың потенциалдарын енгізейік

U₁ ,U₂ ,U₃ , . . . , U_n және V₁, V₂ ,V₃ , . . . ,V_m

б) Тасымалдау есеп кестесінің әрбір толтырылған кереге көзі үшін U₁ (1=1, n) және V_j (J=1, m) белгісіздері бойынша , n+ m-1 теңдеулер жүйесін құрастыру керек:

V_j - U₁ -С_1j = 0, (8.1)

в) Осы құрастырылған теңдеулер жүйесін шешу арқылы U₁ және V_j белгісіздерінің мәндері анықталады.

г) Кестенің толтырылмаған кереге көздері үшін келесі шарттың орындалуы тексеріледі.

V_j - U₁ -С_1j ≤ 0, (8.2)

Егер осы (8.2) шарт барлық кереге көздер үшін орындалса, онда есептің шешімі тиімді болғаны; ал керісінше жағдайда тиімді болмайды.

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

Бұл кесте үшін қарастырылатын теңдеулер жүйесі былайша жазылады:

V₁- U₁ – 8 = 0

V₂- U₁ – 2 = 0

V₂- U₂ – 8 = 0

V₃- U₂ – 4 = 0

V₄- U₂ – 7 = 0

V₄- U₃ – 4 = 0

V₅- U₃ – 8 = 0 (8.3)

Мұндағы белгісіздер саны теңдеулер санынан бірге артық. Сондықтан белгісіздердің біріне кез-келген мән беру арқылы осы жүйенің шешімін табуға болады. Мысалы:

U₁ = 0; V₁= 8; V₂ = 2; U₁ = -6; (8.4)

V₃ = -2; V₄= 1; U₃ = -3; V₅ = 5

Енді (8.2.) шарттың орындалуын тексерейік. Ол үшін кестенің бос кереге көздерін (х_1j =0) қарастырамыз; олар үшін келесі өрнектердің мәндерін анықтаймыз

V₃- U₁ – 8 = -10

V₄- U₁ – 3 = -2

V₅- U₁ – 6 = -1

V₁- U₂ – 2 = 12

V₅- U₂ – 6 = -5

V₁- U₃ – 4 = 7

V₃- U₃ – 2 = -1 (8.5)
Осы қарастырылып от ырған есептің солтүстік-батыс бұрыш тәсілі бойынша табылған шешімі тиімді еместігі дәлелденді.

Оның себебі, (8.5) өрнектеріндегі үш мән оң немесе тиімді шартына (8.2) қарама қайшы.