Басқару есептерін шешетін әдісті таңдау

Алматы Білім және Ғылым министрлігі

Алматы индустриалды колледжі

 

 

 

       

        Курстық  жұмыс

Тақырыбы:«____________________________________________________»

 

 

 

 

 

 

 

                                                                         Орындаған: 

                                                                         Қабылдаған:

 

 

 

                                                        Алматы  2013ж  

Мазмұны

Кіріспе

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

1.1Математикалық модельді  құру

1.2 Басқару есептерін шешетін  әдісті таңдау

2.1 Коммивояжер әдісі

2.2Литтл алгоритмі

2.3 Сандық түрдегі шешім

2.4  Программаның баяндалуы

Қорытынды

Қолданылған әдебиеттер

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

      Модель дегеніміз объектінің (жүйенің) белгілі бір өзара байланыстары бар және оның қызметі мен дамуын сипаттайтын элементтерт комплексінің шартты бейнесі. Модель үрдістің мағынасын жинақты түрде сипаттауға көмектеседі. Құрылған модельден зерттелетін үрдістердің мазмұнын көруге болады.

     Математикалық  модельдер. Математикалық модельдермен зерттелетін объекті мен үрдістің қасиеттері, ерекшеліктері және сипаттамалары теңдеулер жүйелері, теңсіздіктер және функция арқылы көрсетіледі.

Көптеген математикалық  модельдер универсалды болып  келеді, яғни әртүрлі жүйелерді зерттеуге  қолданылады. Математикалық модельдер  қарастырылатын құбылыстар мен үрдістердің  сандық заңдылықтарын анықтауға, сипатталатын факторлардың тәуелділігі мен өзара  байланысын табуға мүмкіндік береді. Математикалық модельдердің дамуына  өте күрделі есептеулерді жүргізетін электронды-есептегіш машиналарының  көбеюі зор ықпал етті.

     Көптеген математикалық  модельдер параметрлер мен айнымалылардан  тұратын теңдеулер мен теңсіздіктер  жүйелерінен тұрады. Айнымалы шамалар,  мысалы, өндірілген өнім көлемі, капитал жұмсау, тасымалдау т.с.с., ал параметрлер өнімді өндіруге  жұмсалған материал, уақыт, шикізат  шығынының мөлшерін көрсетеді.  Әрбір модельде айнымалылардың  екі тобын көрсетуге болады. 1) Сыртқы айнымалылар – олардың  мәндері модельден тыс және  берілген; 2) Ішкі айнымалылар, олардың  мәндері берілген модельді зерттеу  қорытындысында анықталады.

      Модельдеу  үрдісінің нақты алгоритмі жоқ,  бірақ модельдеу тәжірибесінде  басшылықққа алатын анықталған  принциптер бар. 

     Математикалық  модельдердің құрылымдық және  функционалдық түрлері бар. Құрылымдық  модельдер жүйелердің құрылымын  және оның элементерінің өзара  әсерін зерттейді. Функционалдық  модельдер жүйенің ішкі құрылысына  байланыссыз әртүрлі жағдайдағы  тәртібін талдайды.

Құрылымдық модельді оқып үйрену үстінде объектінің мазмұнын туралы, оның сыртқы жағдайларға әсері  туралы информацияларды алуға болады. Ал функционалдық модельді зерттегенде  объектінің әртүрлі реакцияларының сыртқы ортаға әсері туралы деректер алуға болады. Сонымен қатар объектінің құрылымын талдауға және құрылымдық модельдерді құруға мүмкіндіктер туады.

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

 

 

 

1.1Математикалық  модельді құру

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

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

Тәуелсіз айнымалылар – есептің негізгі шешімдерін табуға қолданылады. Олар тиімділік айнымалымен, қозғаушы күштермен байланысты. Математикалық модель мақсатты функция мен шектеулерден тұрады.

Мақсатты функция – деп max немесе mіn мәнін іздейтін функцияны айтады.

Шектеулер – ол тәуелсіз айнымалылар жиынтығының дәлдік шегін анықтайтын теңдеулер жүйесі.

         

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.2 Басқару есептерін шешетін әдісті таңдау

Бұл кезеңдегі жұмыстарды операцияны зерттеуші мен математика маманы бірігіп жасайды. Математикалық модельді келесі белгілермен жіктеуге болады:

1. Айнымалының саны бойынша бір өлшемді және көп өлшемді оптималдандыру есептерге бөлінеді.
2. Шектеулерге байланысты шартты және шартсыз есептерге бөлінеді.
3. Тәуелсіз айнымалының уақыттан функция болу болмауына байланысты статикалық, динамикалық оптималдандыру есептеріне бөлінеді.
4. Ескерілетін информармацияның дәрежелері бойынша детерминдік және стохастикалық оптималдандыру есептеріне бөлінеді және т.б.

Математикалық модельді жасаған соң мақсатты функциялар мен шектеулердің түрі бойынша қарастырған есепті қандай математикалық бағдарлау есептеріне жататынын қарастыру керек:

1. Сызықтық бағдарламалау – Егер мақсатты функция мен шектеулер сызықты түрде болса және тәуелсіз айнымалылар мәндер жиынының шекті мәндер қабылдаса.
2. Бейсызықты бағдарламалау – Егер математикалық функция немесе шектеулер бейтаныс түрде берілсе.
3. Дискретті бағдарламалау – Егер математикалық функция мен шектеулер  сызықты түрде болса, бірақ тәуелсіз айнымалылар мәндер жиынынан тек дискретті мәндер қабылдаса.
4. Динамикалық бағдарламалау – Егер тәуелсіз айнымалылар кейбір параметрден ( уақыт, қадам, кезең және т.б. ) функция болса.
5. Ойындар теориясына – Егер шешім активті немесе  пассивті қарсы әрекет жағдайында қабылданса.
6. Стохастикалық бағдарламалау – Егер тәуелсіз айнымалының бастапқы мәндері немесе мақсаты функцияның коэффициенттері толығымен белгісіз болса, т.б.

Сондықтан, қарастырып отырған есеп қандай математикалық бағдарламалау есептеріне келісетінін қарастырып, есепті шешетін әдістер тобын табамыз. Топ шінде нақты шешім әдісін табу – ол есептеу алгоритмінін тиімділігіне байланысты жүзеге асырылады. Оптималдандырудың барлық таңдалған сандық әдістері есептеу алгоритміне дейін нақтыланады.

 

 

 

 

2.1 Коммивояжер әдісі

 

Коммивояжер n пунктке (қалаға) минималды жолмен бір-бір ретпен ғана кіріп, алғашқы пунктке қайта  кіру керек. Қалалар арасында жол  құны                     матрицасымен беріледі.

Коммивояжер туралы есептің математикалық  моделі:

 

 

1- Егер  Коммивояжер   і-ші қаладан кейін  j-ші қалаға  барса,

0- қарсы жағдайда.

 

     Цикл деп – реттелген қалалар жиынтығын айтады. Егер ол әрбір қаладан тек бір – бір  реттен өтсе.

 

 

Сонда Коммивояжердың жалпы  жол шығыны t циклына мынадай болады:

 

 

     Циклда С  матицасының әрбір жолының және  әрбір бағанының бір элементінен  немесе j-ші бағанның әрбір элементінен  минималын алсақ, онда келтірілген  матрицаны табамыз. Келтіру процессінде  (рәсімінде) табылған минималды  элементтерінің қосындысы – ол  келтірілген константа болады  .

  h- келтіру рәсімінің  немесе итерация нөмері

  k- келтірілген константа

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.2Литтл алгоритмі

 

  к=1

 Келтірілген матрицаны табу

 

     Ол үшін  әрбір жолдың оң жағына ең  кіші (минималды) элементті жазып,  жолдың әрбір элементінен алып  тастаймыз. Содан соң матрицаның  төмен жағына әрбір бағанның  минималды элементін жазып, бағанның  әрбір элементінен алып тастаймыз.

 

 Келтірілген константаны  табу

 

     

 

 Тарауға үміткерлер жұбын  таңдау

     Тарауға тек  -шісі  0-ге тең жұптарын қарастырамыз.

 

 

 Үміткерлер үшін бағаларын  анықтау

 

 

 Барлық бағалардың (Q (i, j)) ішінде  ең үлкенін аламыз

Q ( k, l ) =max Q(i, j)

 

 

 

 Максималды бағасы бар  жұпты матрицадан сызып тастаймыз  (к -жол,         l- бағанды)  және l, k элементтерінің  орнына шексіздік қоямыз.

 

 

 Алынған матрицаның шамасы 2х2 болса, екі жұп тарауға  таңдалады. Егер матрица шамасы 2х2 болмаса, онда 10-шы қадамға  көшу

 

  Келтіру рәсімі жасалады,    есептелінеді,

есептелінеді   k= k+1.  -ші қадамға көшу.

 

 

Мысал 1:

 

	1    2     3     4     5
1 2 3 4 5	х    4    10    9     4 2     х     9     7     6 8     5     х     5     9 5     8    10    х     7 1     5     4     8     х		4 2 5 5 1
	1    2     3     4     5
1 2 3 4 5	х     0     6     5     0 0     х     7     5     4 3     0     х     0     4 0     3     5     х     2 0     4     3     7     х
0     0     3     0     0

 

 

	1    2     3     4     5
1 2 3 4 5	х     0     3     5     0 0     х     4     5     4 3     0     х     0     4 0     3     2     х     2 0     4     0     7     х

 

 

 

	1    2     3     5
1 2 4 5	х     0     3     0 0     х     4     4 0     3     х     2 0     4     0     х

 

 

 

 

 

 

 

 

	2     3     5
1 4 5	0     3     0 3     х     2 4     0     х		0 2 0

 

	2     3     5
1 4 5	х     3     0 1     х     0 4     0     х
1     0     0

 

	2     3     5
1 4 5	х     3     0 0     х     0 3     0     х

 

 

	2     5
1 4	х     0 0     0		0 0
0     0

 

 

 

 

 

 

 

 

2.3 Сандық түрдегі шешім

 

C_ij – тасымалдау құны.

Х_{ij –} тасымалдаудың өнім көлемі.

 

Қарапайым актілер:

1. Мұнай шығындарын минималдандыру.
2. Операцияның орындалуындағы ең жақсы жүйелігін қанағаттандыру.

Жалпы түрдегі мақсатты функция:

 

                                          

 

Мақсатты функция:

 

Z = 3X₁₂ + 2X₁₃ + 5X₁₄+6X₂₁ +4X₂₅+3X₂₄+2X₃₁+2X₃₂+

X₃₄+4X₄₁+6X₄₂+5X₄₃        min

 

X₁₂+ X₁₃+ X₁₄=1

X₂₁+ X₂₃ + X₂₄=1

X₃₁+ X₃₂+ X₃₄=1

X₄₁+ X₄₂+ X₄₃=1

X₂₁+ X ₃₁+ X₄₁=1

X₁₂+ X₃₂+ X₄₂=1

X₁₃+ X₂₃+ X₄₃=1

X₁₄+ X₂₄+ X₃₄=1

 

	1	2	3	4
1	x	3	2	5	2
2	6	x	4	3	3
3	2	2	x	1	1
4	4	6	5	x	4