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

Қазақстан Республикасының білім және ғылым  министрлігі

 

 

 

 

 

 

 

 

КУРСТЫҚ ЖҰМЫС

 

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

 

 

 

 

Қабылдаған:_____________________

Орындаған:______________________

Тобы:___________________________

 

 

 

 

 

 

 

 

 

 

Түркістан – 2013

Жоспар

 

 

І. Кріспе.....................................................................................................................3

ІІ Негізгі бөлім

І  тарау . Өндірістік есептердің математикалық моделдерін құру.

1. Кәсіпорын өндірісін есепке алу...................................................................5
2. Материалдарды тиімді пішу туралы есеп .................................................9
3. Тапсырманы кәсіпорындарға бөлу туралы есеп .....................................10
4. Тасымалдау есебі .......................................................................................11

 

ІІ  тарау . Графтар теориясы және оны қолдану.

1. Графтар теориясының анықтамалары және негізгі теоремалары..........13
2. Графтың түрлері: толық, толық бағытталған граф, екі үлесті граф......14
3. Шыңдар дәрежесі. Графтың байланысуы.................................................16
4. Қабырғаларды жою, көпірлер....................................................................21
5. Ағаштар. Ағаштардың саналуы................................................................22
6. Жазық граф..................................................................................................24
7. Гомеоморфтық графтар..............................................................................27
8. Эйлер графы. Эйлер формуласы...............................................................27
9. Дирак теоремасы.........................................................................................29

 

III. Қорытынды.....................................................................................................31

 

IV. Пайдаланылған әдебиеттер..........................................................................32

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Кіріспе

 

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

           Сонымен, болашақта өндіріс тиімділігін арттыру мәселесін шешудің негізгі жолдарының бірі ғылымның соңғы жетістіктерін, оптимизациялау математикалық моделдеу әдістерін және  ЭЕМ  мен дербес компьютерді  қолдану болып табылады.

           Математикалық әдістерді экономикалық  зерттеулерде тәжірбие жүзінде қолдану 1951 жылдан басталды, ал 1955 жылдан бастап кеңінен қолданылатын болды.

           Математиканың экономикаға енуі  жоспарлау мен басқарудың қазіргі  кездегі ғылыми-техникалы революциясының  аса маңызды ерекшелігі  болып  табылады. Бұл процесс соңғы 30 жылда  бүкіл әлемде  қарцынды түрде жүргізілуде. Математикасын  әдіс мектептерінің АҚШ, Франция, Германия,  Англияда ашылуының обьективті себептері мол. ЭЕМ , оптимизациялау және математикалық моделдеу әдістерінің дамуы мен жылдам  таралуы бұл әдістердің қолдану ауқымының кеңеюіне және басқарудың  автоаттандырылған жүйелерінің құрылуына тікелей әсер еткені белгілі.

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

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

                 Бүгін таңда өз жұмысында оптимизациялау  және математикалық моделдеу  әдістері мен ЭЕМ, дербес компьютерді кеңінен қолдана білетін жоғары білікті мамандар дайындау кезек күттірмейтін мәселе болып отыр.

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

 

Графтар теориясын ХVII- ғасырдың ІІ-жартысымен  XVIII – ғасырдың І- жартысында пайда болған. Графтар теориясы туралы алғашқы ғылыми мақаланы 1736 – жылы Швецар математигі Э.Эйлер «Кюненcберг қаласындағы жеті көпір мәселесі». Бұл жұмыс Сант Петербург қаласындағы Университетте шығатын жұрналда жарияланған. Осыдан бастап Графтар теориясының тарихы басталады. ХІХ- ғасырда Графтар теориясы ғылыми жаңалықтардың ашылуына байланысты қарқынды дами бастады. ХХ- ғасырдың 50-жылдарында графтар теориясының негізіне екі бағыт пайда болды. Алгебралық және оптимизациялық. Соңғы бағыттың дамуы элекронды есептеу машинасымен байланысты болды. Осыған байланысты сызықтық программалаудың әдістерін пайдалана отырып негізінен экономикалық есептер шешілді. Жалпы айтқанда графтар нүктелерді сызықтармен байланыстыруды айтады. Сонымен жазықтықта нүктелерді және бағытталған сызықтармен көрсетуге болады.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

І-тарау. Өндірістік есептердің математикалық моделдерін құру

1.1. Кәсіпорын өндірісін есепке алу.

             

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

               Кәсіпорын әр-түрлі өнім шығарады делік. Шығарылатын өнімдердің түрлерін шартты түрде a₁ a₂ ... a_n деп белгілейік. Осы өнімдерді өндіру үшін кәсіпорын әр-түрлі шикізат қорын пайдаланады. Пайдаланылатын шикізат қорларының түрлерін шартты түрде b₁ b₂... b_м деп белгілейік. Төмендегі белгілеулерді енгізейік: a_ij (i=1,m; j=1,4)-  j-өнімнің бір данасы өндіруге жұмсалатын і-шикізат мөлшері.

b_і(і= ) – кәсіпорын қоймасындағы  і-шикізат қорының мөлшері c_j(j= )- дайын j-өнімнің бір данасынан сатудан түседін пайда;

            Әдетте  есептің берілгенін төмендегі  1.1 кесте түрінде береді.

 

 

Шикізат түрлері	а1	Дара өнімге шаққандағы жұмсалынған  шикізат  мөлшері а2                                                                                      an		Шикізат қорының көлемі
В1	а2	а2                                                                                  a1n		b1
В2	а21	а22                                                                                  a2n		b2
Вm	аm1	аm2                                                                                 amn		bm
Пайдасы	с1	c2                                                                                    cn

               

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

         Шешуі: Ізделінді өндірілетін өнімдер шамасын xj (j= ) деп белгілейік. Сонда барлық өндірілген өнім түрлерін сатудан түсетін пайданың жалпы көлемі мына өрнекпен есептелінеді:

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

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

     

 

     a₁₁ x₁ +a₁₂ x_2+...+a_n x _n≤b₁

      a₂₁x₁+a ₂₂x₂+...+a_2nx_n≤b₂

       - - - - - - - - - - - - - - - - - - - - -

      a_m1 x₁+a_m2x₂+... +a_mnx_n≤b_m

     Ізделінді мәндердің экономикалық мағынасы  болу үшін олар теріс сан болмауға тиісті, басқаша айтқанда өндірілетін өнім мөлшері теріс мән қабылдай алмайды.  Егер, қайсыбір айнымалының мәні нөлге  тең болса , онда бұл өнімді  өндіру өндіріс үшін экономикалық тұрғыдан тиімді емес деген мағына береді. Сондықтан, кез келген есептің негізгі талаптарының бірі-айнымалылардың  мәні теріс сан болмауға тиісті:

      v_j. x_j=0, (j= )  

Есепті шығарудағы негізгі  мақсат - өнімдерді сату барысында  ең көп пайда табу болғандықтан F функциясы шах-ға зерттелінеді.

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

              

    F(x) = c_j x_j →mах (1.1)

                                                                                                                

        

   a _ij x_j≤b_i(i= )                                                                (1.2)                  

        

        x_j≥0 (j= )                                                                      (1.3)

1. түріндегі сызықтық Ғ функциясы деп аталады.
2. Түріндегі шарттар шектеулер жүйесі деп аталады
3. Түріндегі шарттар айнымалылардың теріс еместік шарты

       Математикалық  тұрғыдан бұл есепті  былайша  тұжырымдауға болады: Берілген (1.1) мақсат функциясына максимум мен әперетін және (1.2),(1.3) теңсіздіктер  жүйесін қанағаттандыратын x=(x₁x₂...x_n) векторын табу қажет. Берілген есептің мақсат функциясымен шектеулер жүйесі сызықтық болғандықтан бұл есеп  сызықтық бағдарламалау есеп-н жатады. (1.2) Азық құрамы (Рацион) туралы есеп.

    Күнделікті шаруашылықта  жиі кездесетін технологиялық  есептердің бір түрі дұрыс  рацион дайындау есебі болып  табылады. Енді осы есептің ауыл  шаруашылығында кездесетін бір  түрін қарастырайық.

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

   

 

   a_ij- жем -   шөптің j- түрінің құрамындағы нәрлі i-заттың мөлшері;

   b_i-нәрлі і – заттың қажет мөлшері;

   c_j (j= )- жем – шөптің j-түрінің дара мөлшерінің бағасы. Әдетте есептің берілгенін  төмендегі 1.2 кесте түрінде береді.

                                                         

 

                                                 

                                        1.2. кесте

Нәрлі заттар аты	Жем-шөптің 1 кг – дағы нәрлі заттың   мөлшері а1            а2                             аn		Нәрлі заттың қажет мөлшері
В1	а11            а12         а1n		b1
В2	а21            а22          а2n		b2
Вm	аm 1                                                   аmn		bm
жем-шөптің 1 кг-ның бағасы	с1 с2  сn

 

 

 

 

 

 

 

 

 

 

 

 

          Рационда  ондағы пайдалы, қоректік, нәрлі  заттардың әрқайсысы b_і-дан кем мөлшерде болмауға  тиіс.

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

    Шешуі: Ол үшін азық құрамына енетін азық-түлік түрлерінің мөлшерін x_j(j= ) деп белгілейік.  Сонда жалпы жұмсалынатын қаржы келесі формуламен анықталады.

 

                                             

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