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

Мұндағы а_1j, b₁ соңғы симплекс кестесінен алынған коэффициенттер мен бос мүшелер; d белгісі санның бөлшек бөлігін көрсетеді, немесе d(а_1j) және d (b₁) дегеніміз жаңаша көрсетілген сандардың бөлшек бөліктері.

Осыдан кейін (7.5) шарты (7.2) шартына қосылып, сызықтық бағдарламалаудың (7.1) және (7.3) есебі симплекс әдісімен шешіледі.

Осыдан Гомори әдісімен есептің тиімді шешімін табудың келесі кезеңдерден тұратынын көруге болады:

1. 
   Симплекс әдісін пайдаланып, (7.1) - (7.3) есебінің шешімін табу.
   
2. 
   Табылған шешімдегі мәні бүтін болуға тиіс айнымалылардың бөлшек бөлігі ең үлкенін таңдап, сол үшін қосымша шектеме құрастыру қажет.
   
3. 
   Қосжақты симплекс әдісін пайдаланып, (7.1) - (7.3) есебінің шешімін қосымша (7.5) шектемені еске ала отырып табу қажет.
   
4. 
   Қажет болса тағы бір қосымша шектеме құрып итерациялық процесті жалғау керек; ол процесс (7.1) - (7.4) есебінің тиімді шешімі табылғанша немесе оның шешімі болмайтындығы дәлелденгенше жалғанады.
   

Есеп. Үш түрлі шикізатты пайдаланып, екі түрлі бұйым шығаруды жоспарлау туралы есепті қарастырайық. Барлық мәліметтер келесі кестеде келтірілген:

Шешуі:

4 х₁ + 5 х₂ ≤ 35

4 х₁ + 3 х₂ ≤30 х_j ≥ 0, J =1,2
Қосымша х₃ , х₄ , х₅ ≥ 0 айнымалыларын енгізіп, СБНЕ-ні аламыз:
F (Х) = 6 х₁ + 8 х₂ + 0 ∙ х₃ + 0 ∙ х₄ + 0 ∙ х₅  max
2 х₁ + 3х₂ + х₃ = 20

4 х₁ + 5 х₂ + х₄ = 35

Сонымен тиімді шешімі былай жазылады:

Х₁ = (2,5; 5) ; F₁ =55

Бірақ бұл шешім бойынша Х₁ бүтін мән қабылдамайды немесе есептің шарты толық орындалмаған. Сондықтан қосымша шектеме құрастыру керек. Ол үшін соңғы симплекс кестесінен (7.5) формуласына сәйкес теңсіздік жазылады:

d (1) ∙ х₁ + d (0) ∙ х₂ + d (-5/2) ∙ х₃ + d (3/2) ∙ х₄ + d (0) ∙ х₅ ≥ d (5/2)
Бөлшек бөліктерін тауып, мынадай теңсіздікке келтіруге болады:

Х₀ = (5; 3) ; F_max =54

Есептің шешуін көрнекті етіп көрсету үшін оның графикалық әдіспен шешуін көрсетейік:

***********

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

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

1.7. 1. Потенциалдар әдісінің алгоритмінің негізгі кезеңдері
Бұл әдіс бойынша алдымен жүк қоймалары мен оны пайдаланушылар потенциалдары деген түсінік енгізіледі. Жүк қоймаларының потенциалын

U₁ ,U₂ ,U₃ , . . . , U_n деп, пайдаланушылар потенциалын V₁, V₂ ,V₃ , . . . ,V_m деп белгілейік.

Әдістің алгоритмінің негізгі кезеңдері мынадай:

1. 
   Алғашқы таяныш шешімді табу.
   
2. 
   Табылған шешімнің тиімді екендігін тексеру.
   
3. 
   Бір шешімнен екінші шешімге өту
   

Егер екінші кезеңде тиімді шарттар орындалған жағдайда есепті шешу процесі тоқтатылады;ал ол шарттар орындалмаса, онда үшінші кезең орындалуға тиіс. Екінші және үшіінші кезеңдердің әрбір қайталануын итерация деп атайды. Ырғақты қайталама саны алдын-ала белгілі болмайды; ол тиімді шешім табылғанша немесе оның болмайтындығына көз жеткізгенше қайталанады.

Алгоритмнің осы кезеңдерін қарастырайық.

Ескерту. Есептің әрбір шешімін тасымалдау жоспары деп қарастыру керек.

а) солтүстік-батыс бұрыш

б) ең кіші элемент тәсілдері.

Осы тәсілдердің қолдану тәртібін қарастырайық.

Бұл тәсіл бойынша тасымалджау есебінің үлестіру кестесі оның жоғарғы сол жақ бұрышынан бастап толтырыла бастайды. Мұндағы негізгі тәртіп – формулаларға сәйкес тік жолдар мен жатық жолдардағы сандардың қосындыларының b_j мен a₁ - ге тең болуы.

Айтылған тұжырымдар түсінікті болу үшін мысал қарастырайық.

Есеп.

Бұл тасымалдау кестесінің толтырылу тәртібі мынадай. Алдымен ең жоғарғы сол жақтағы бұрыштағы кереге көзге 100 деген сан жазылады; оның себебі А₁ қоймасында 150 мөлшерінде жүк қоры болса, ал В₁ пайдаланушыға қажеті 100; сондықтан х₁₁ = 100. Одан артылған 50 мөлшердегі жүк екінші пайдаланушыға беріледі, немесе х₁₂ = 50, апл қалғандары бірінші қоймадан жүк алмайды, немесе х₁₃ = х₁₄ = х₁₅ =0. Сонымен қатар бірінші пайдаланушы В₁ өз қажеттілігін толық қамтамасыз еткендіктен басқа қоймадан жүк алмайды, немесе х₂₁ = х₃₁ = 0.

Осыдан кейін келесі толтырылатын кереге көз екінші жатық жол мен екінші тік жолдың қиылысында орналасқан. Мұнда екінші пайдаланушыға В₂ қажетті 60 мөлшердегі жүк берілуге тиіс немесе х₂₂ = 60. Сонда ол өз қажеттілігін түгел қамтамасыз етеді; немесе х₃₂ = 0.

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

х₁₁ = 100; х₁₂ = 50; х₁₃ = 0; х₁₄ = 0; х₁₅ =0;

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

х₃₁ = 0; х₃₂ = 0; х₃₃ = 0; х₃₄ = 10; х₃₅ = 130;
Бұл жорспарды орындауға жұмсалатын қаржы мөлшері былайша анықталады:

F = 8 ∙ 100 + 2 ∙50 + 8 ∙ 60 + 4∙90 + 7 ∙90 + 4∙10 + 8∙130 = 3450