Өндірістік үрдістерде графтар теориясын қолдану

F(x)=c₁+x₁+c₂+x₂+...+c_nx_n= c_jx_j→min

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

                a₁₁x₁+a₁₂x₂+...+a_1nx_n≥b_1,

                        a₂₁x₁+a₂₁x₂+...+a_2nx_n≥b₂,

                ─ ─ ─ ─ ─ ─ ─ ─  ─ ─ ─

                a_m1x₁+a_m2x₂+...+a_mnx_n≥b_m,

 

   ал азық-түлік мөлшері теріс мән қабылдай алмайды:

              x_j≥0(j= )

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

               

     F(x)= c_ix_j→min                                                              (1.4)                                

              

      
        a_ij  x_j≥b_i(i= )                                                          (1.5)                       

   

 

   x_j≥0 (j= )                                                                            (1.6)                                     

 

Математикалық тұрғыдан бұл есепті былайша тұжырымдауға болады:

Берілген (1,4) мақсат функциясына минимум мән әперетін және (1,5) (1,6) теңсіздіктер жүйесін қанағаттандыратын x= (х₁,х₂,...х_n)  векторын табу қажет.  Берілген есептің мақсат функциясы мен шектеулер жүйесі сызықтық болғандықтан, бұл есепте сызықтық бағдарламалау есебіне жатады.

      Жоғарыда  қарастырған (1.1)-(1.3),(1.4)-(1.6) есептерін  матрица түрінде де жазуға болады. Ол үшін төмендегі белгілеулерді енгізейік:

         a₁₁ a₁₂ ... a_1n          - шектеуші шарттардағы белгісіздер

  A=   a₂₁ a₂₂ ...a_2n                  коэффиценттерінен құралған матрица;                                                                

           - - - - - - - -

a_m1 a_m2...a_mn        

          

     c=(с₁, с₂, ..., с_n) – мақсат функциясындағы белгісіздер    

                               коэффициенттерінен құралған матрица – қатар;

           x₁

 Х=     x₂      - белгісіздерден құралған матрица – баған

          ...

          x_n

          b₁           - шектеуші шарттар оң бөлігінен құралған матрица - баған

          b₂

B=     ...

          b_n

 

 

 Сонда  (1.1)-(1.3) есебінің  матрицалық түрде жазылуы төмедегідей  болады:

                     F(x)=c_*x→ max                                                     (1.7)                               

                        A_*X≤B,                                                              (1.8)                              

                         x≥0                                                                     (1.9)                              

Ал (1,4)-(1,6) есебінің матрицалық түрде жазылуы төмендегідей  болады:

                      F(x)=c_*x→min                                                     (1.10)

                          A_*X≥B                                                             (1.11)

                          x≥0                                                                   (1.12)

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

                     F(x)=c_*x →extr,                                                   (1.13)

                            AX=B,                                                            (1.14)

                             x≥0                                                                (1.15)

 

 

1.2. Материалды тиімді пішу туралы есеп.

      

       Белгілі бір бұйымды шығару үшін әрқайсында көлемі b_j –ге тең n партия материал бар делік. Әрбір бұйымды жасау үшін осы материалдардан s түрлі бөлшек дайындалу  саны р_к болуы керек. Ол бөлшектерді пішудің (дайындаудың)  т  түрлі тәсілі бар;  егер

і-партияның материал бірлігін j тәсілмен пішетін болса , онда а_ijk дана

 к-бөлшек алуға  болады. Қолда бар материалдардан  дайындалатын бұйым саны ең көп болатын пішу жоспарын табу керек.

   Шешуі: белгілеу енгізейік: x_ij-i партия материалдарының j – тәсіл бойынша пішілетін көлемі делік.

     Сонда   і-партия материалдарының j тәсілімен  пішкенде алынатын к-бөлшек саны: a_ijk*x_ij,

ал  і-партия материалдарын  барлық тәсілмен пішкенде алынатын

k-бөлшек саны:

    

 

                      a_{ijk *}x_ij

                  

Сонымен, барлық п партиядағы материалдарды барлық  m тәсілмен пішу кезінде дайын болатын к-бөлшек саны:

              

       F_k=  a_{ijk *} x_ij, (K=1,s)                                              (1.16)

             

Бір бұйым үшін қажетті К-бөлшек саны  Р_к  болғандықтан, дайын бұйым саны келесідей болуға тиіс:

                    

     F= min   ,   k=                                                         (1.17)

                   

немесе, (1.16) формуласы бойынша:

                   

                     a_ijk*x_ij

     F=min                             ,   k=                    (1.18)                  

                        P_k                                          

Әрбір  партиядан жұмсалынатын материал саны белгілі, сондықтан :

                    x_i1+x_i2+...+x_im =b_i, i=                      (1.19)

         Сонымен бірге: x_ij≥0                                          (1.20)

 

 

Сонымен  бұл есептің математикалық моделін былайша тұжырамдауға болады:  Берілген (1,18) мақсат функциясына  максимум мән әперетін және (1,19) –(1,20) шарттарын қанағаттандыратын х_ij –дің мәндерін табу керек. Бұл есепті кейде «максимин» есебі деп те атайды .

 

 

          1.3 Тапсырманы кәсіпорындарға бөлу туралы есеп.

 

         Өндіріс саласының жоспары бойынша белгілі бір Т уақытта А_i бұйымынан N_i дана (i = ) шығарылуға тиіс . Бұл бұйымдар m кәсіп орында шығарылады, бірақ  ешбір кәсіпорын бірмезгілде бірнеше түрлі бұйымды қатарынан шығара алмайды. Сонымен бірге a_ij –j кәсіпорында уақыт бірлігінде шығаратын. А_і бұйымның сан мөлшері, яғни a_ij әрбір кәсіпорынның еңбек өнімділігі. Ал b_ij –осы кәсіпорында шығарылған А_і бұйымның бір данасын а кеткен шығын. Шығарылатын барлық өнімге кететін шығын ең аз болатындай етіп тапсырманы кәсіпорындарға бөлу жоспарын жасау керек.

   Шешуі: берілген есептің математикалық моделін түзу үшін х_іj  деп А_і бұйымын шығаруға жұмсалатын j кәсіпорынның уақытын белгілейік. Сонда өндіріс кәсіпорындарының шығарылатын барлық өнімге жіберілетін шығыны төмендегі формуламен есептелінеді:

                  

              F= a_ij b_ij x_ij                                                                 (1.21)

                 

Сонымен бірге, әрбір кәсіпорынның жұмыс уақыты T-дан аспауға тиіс:

           x_1j+x_2j+...+x_nj ≤T,  j=                                                          (1.22)

Шығарылатын  өнім мөлшері  тапсырмаға сәйкес болуы керек:

              

a_ij   x₁+a_i2 x₂+... +a_im*х_m= N_i, i=                                                        (1.23)

     Бұған қосымша:

 

x_ij≥0(i= j= )                                                                                 (1.24)

    Сонымен, тапсырманы кәсіпорындарға бөлу есебінің математикалық моделін былайша тұжырамдауға болады: Берілген (1,21) максат функциясына минимум мән әперетін және (1,22) – (1,24) шарттарын қанағаттандыратын х_ij белгісіздердің мәндерін табукерек.

 

                                  

1.4. Тасымалдау есебі.

     

     Күнделікті өмірде сызықтық бағдармалаудың жиі кездесетін есептерінің бірі тасымалдау есебі. Жаңа шаруашылық жағдайында , шығындарды қысқартуда тасымалдау есебінің шешімін табу өте маңызды.

 Тасымалдау есебінің жалпы  түрін қарастырайық.

       Айталық , а_1, а_2,... ,а_m m жабдықтаушыда әрқайсысында көлемі сәйкесінше а_1, а_2,...,а_m – ге тең біркелкі жүк мөлшері бар делік. Осы жүктерді b_1, b_2,...,b_n  n  тұтынушыға әрқайсысына сәйкесінше

 в_1, в_2,...,в_nқажетті мөлшерінде тасымалдап жеткізу керек. Әрбір жабдықтаушыдан әрбір тұтынушыға  жүктің жеке бір бөлігін тасымалдаудың шығыны белгілі делік және ол с_ij –ға тең болсын.

      Барлық тұтынушылардың  қажеттіліктерін толығымен қанағаттандыратын,  барлық жабдықтаушылардағы  жүк толығымен тасымалданатын және тасымалдау шығыны ең аз болатын тасымалдау жоспарын құру керек.

       Шешуі: есептің математикалық моделін құру үшін a_і жабдық таушыдан b_j  тұтынушыға тасымалданатын жүк мөлшерін х_іj(і= ; j= ) деп белгілеп, есептің шартында берілген мәліметтерді жоспарлау кестесі деп аталатын мына төмендегі кестеге жазайық.

Жабдықтаушылар	Тұтынушылар			Жүк қ.
	b1	b2	...	b n
a1	c11  x11	c12 x12	...	х1n с1n          a1
a2	c21	c22	...	x2n                  a2
...	....	....	...	...            ...
am	c m1 x m 1	cm2 x m2	...	cmn                 am
Тұтынушылардың  қажеттілігі	b1	b2	...	bn

          Есептің шартын жоспарлау кестесі  арқылы жазу, оны шығару барысында  өте ыңғайлы екенін ескерте  кетейік және есепті түсіндірудің  ең оңай жолы болып табылады.

   Сонда і-жабдықтаушыдан  j-тұтынушыға дейін тасымалданатын  барлық жүк мөлшерінің шығынының бағасы ең аз болуы тиіс болғандықтан, тасымалдау есебінің мақсат функциясын мына түрде жазуға болады:

      F=c₁₁x₁₁+c₁₂x₁₂+...+c_1nx_1n+c₂₁x₂₁+c₂₂x₂₂+...+c_2nx_2n+...+c_m1x_m1

                                                       

+c_m2x_m2+...+c_mnx_mn= c_ij*x_ij →min                         (1.25)

                                      

Есептің шарты бойынша: а) барлық жабдықтаушылардағы жүк қоры толығымен тасымалдануы тиіс, яғни

 

x₁₁+x₁₂+...+x_1n=a₁

 x₂₁+x₂₂+...+x_2n=a₂

– – – – – –  – – –                                                             (1.26)                                                 

x_m1+x_m2+...+x_mn=a_m