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

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

 

 

 

 

 

 

 

 

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

 

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

 

 

 

 

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

Орындаған:______________________

Тобы:___________________________

 

 

 

 

 

 

 

 

 

 

Түркістан – 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= ) деп белгілейік.  Сонда жалпы жұмсалынатын қаржы келесі формуламен анықталады.