Файл қосу
Сызықты программалаудың қосжақты есебі
|ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ |
|СЕМЕЙ ҚАЛАСЫНЫҢ ШӘКӘРІМ АТЫНДАҒЫ МЕМЛЕКЕТТІК УНИВЕРСИТЕТІ |
|3 деңгейлі СМК құжаты |ПОӘК |ПОӘК |
| | |042-18-12.1.117/03-2013 |
|«Экономикалық-математикалық|№5 басылым | |
|модельдеу» пәнінің |18.09.2013ж | |
|оқу-әдістемелік кешені | | |
«Экономикалық-математикалық модельдеу»
пәнінен оқу-әдістемелік кешен
5В050703- «Ақпараттық жүйелер» мамандығына арналған
ОҚУ-ӘДІСТЕМЕЛІК МАТЕРИАЛДАР
Семей
2013
мазмұны
1. Глоссарий
2. Дәрістер
3. Практикалық және лабораториялық сабақтар
4. Студенттің өздік жұмысы
1. глоссарий
Бұл ОӘМ-да келесі терминдер және оларға түсініктемелер қолданылған:
1.1. Базистік шешім — шешілетін облыс төбесінде орналасқан сызықты
программалау есебін шешудің қолайлы шешімі.
1.2. Қолайлы жоспар — шексіздіктер жүйесін қанағаттандыратын шешім.
1.3. Динамикалық программалау — шешімді табу процесі көпэтапты болып
табылатындай есеп шешімінің әдісі.
1.4. Ойын – бұл ойынға қатысушылардың арасындағы іс-әрекеті немесе
формальды жанжалы.
1.5. Ойыншы — ойын моделіне қатысушы.
1.6. Итерация — алгоритмді өндіру сатысы.
1.7. Сызықты шектеулер коэффициенті — ресурстарды шығындау ресурстары.
1.8. Сызықты программалау (СП)— шектеулер мен мақсат функция сызықты
болатын есепті шешу әдісі.
1.9. Модель —зерттеуді жеңілдету үшін құрылған объектінің шартты
образы.
1.10. Шектеулер — ресурстар үшін тәуелділікті орнататын теңсіздік.
1.11. Оптималды шешім — қабылданған критерий ең жақсы мәнді
қабылдайтын вариант.
1.12. Айнымалы — әр түрлі мәндерді қабылдайтын шама.
1.13. Төлемдік матрица — тікбұрышты кесте.
1.14. Ойын ережесі — қандайда бір мақсатқа жетуге бағытталған
ойыншылардың іс-әрекеті.
1.15. Симплекс-әдіс — сызықты программалау есебін шешу әдісі.
1.16. Стратегия — ойын процесінде қалыптасқан жағдайларға байланысты
әрбір қадамда ойыншының мінезін анықтайтын ережелер жүйесі.
1.17. Транспорт есебі — біртекті жүктерді бір пункттен берілген
сұраныс бойынша екінші пунктке тасымалдаудың экономды жоспары туралы есеп.
1.18. Ойыншы қадамы —іс-әрекеттің қарастырылған ережелерінің біреуін
таңдау және жүзеге асыру.
1.19. Мақсат функция — қабылданатын шешім (пайда максимумы, шығын
минимумы) сапасын сипаттайтын белгі, оптимизация критерийі.
1.20. Экономикалық-математикалық әдістер — 60-шы жж. басында академик
В.С. Немчиновпен енгізілген экономикалық және математикалық пәндер
кешенінің атауы.
1.21. Экономикалық-математикалық модель — бұл зерттелетін эономикалық
процесс немесе объекті математикалық сипаттау.
1.22. Экономикалық-математикалық модельдеу — экономикалық-
математикалық модель құру процесі.
2. Дәрістер
Дәріс сабағының құрылымы:
Дәріс №1.
Тақырып: Экономикалық-математикалық модельдеуге кіріспе.
Сызықты программалау есебін жазудың үш формасы.
Дәріс сұрақтары:
• Модельдеудің негізгі түсініктері.
• Модельдің негізгі типтері.
• Сызықты программалау есебін жіктеу.
• СП есебін жазудың жалпы формасы.
• СП есебін жазудың стандартты формасы.
• СП есебін жазудың негізгі (канондық) формасы.
• Жазудың бір формасынан екіншісіне көшу.
Қазiргi кезеңдегi ғылымдардың даму ерекшелiктерiнiнiң бiрi-олардың әр
түрлi салаларын зерттеуде математикалық әдiстер кең қолданылуда. Осы
курстың негізгі түсінігі болып математикалық модель саналады. Қазіргі
уақытта бір-бірінен анықтамасы бойынша айырмашылығы көп "модель" түсінігі
көптеп кезігеді. Жалпы жағдайда модель сөзі – бұл нақты объектінің бейнесі.
Мұндай бейне ретінде сызбаны, фотографины және т.б. алуға болады.
Сонымен, модель-зерттеуге тиімді болу үшін алынған объектінің шартты
образы. Экономикалық-математикалық модельдеу дегеніміз-зерттегелі отырған
эономикалық процесстерді немесе құбылысты белгілі бір математикалық
өрнектер түрінде бейнелеу немесе сипаттау. Бұл модель экономикалық процесс
заңдылықтарын математикалық қатынастардың көмегімен абстрактілі түрде
өрнектеу. Экономикалық-математикалық модельдеу процесі-экономикалық
математикалық моделдеу (ЭММ) деп аталады.
Әрине, экономикалық объектіні моделдеу және математикалық моделін құру
өндірістік процесстердің экономикалық талдауын математикалық анализге
әкеліп, және тиімді шешім қабылдауға мүмкіндік береді.
Модельдер екiге бөлiнедi:
• Ақыл-ой моделi: үй схемасы, масштабы т.б.
• Физикалық модель: самолет макеті, үй макеті және т.б.
Экономикалық модельді құру.
Зерттеудің мақсаты мен заты талданады.
Қарастырылып отырған экономикалық жүйеде берілген мақсатқа сәйкес келетін
құрылымдық немесе функционалдық элементтер бөлініп, осы элементтердің өте
қажет сапалы мінездемелері айқындалады.
Модель элементтерінің арасындағы өзара байланыс сөзбен, сапалы түрде
сипатталады.
Экономикалық объекттердiң алынған мінездемелеріне символдық белгілеулер
енгізіп, олардың арасында өзара байланыстың қаншалықты болуын пішіндеу.
Осылайша математикалық модель құру.
Математикалық модель бойынша есептеулер мен алынған шешімнің талдауы
жүргізіледі.
Өндірісті талдау мен жоспарлауда қолданылатын барлық экономика-
математикалық модельдерді екi топқа бөлуге болады. Бiрiншi топты мазмұны
жеке шаруашылықтағы экономикалық талдау мен жоспарлаудан тұратын
микроэкономикалық модельдер құрайды, ал екінші топты экономикалық талдаудың
мәселелерін шешіп, қарастырудан тұратын макроэкономикалық модельдер
құрайды.
Экономико-математикалық моделдерді сонымен қатар уақыт факторының
есебіне байланысты былай бөледі: статистикалық (барлық тәуелділіктер бір
уақыт мезетіне жатқызылады) және динамикалықе (дамудағы экономикалық жүйені
сипаттайды); нақты және жуық; математикалық аппарат түріне байланысты:
матрицалық, сызықтық, сызықтық емес, корреляция-регрессиялық және т.б.
Сызықтық программалалаудың жалпы және негізгі есебі.
Шектеулі ресурстарды тиімді бөлу есептері. Осы топқа жататын
экономикалық есептерді математикалық өрнектер түрінде бейнелеу үшін дара
өнімді шығаруға қажет әр ресурстың шығыны мен ресурстардың жалпы шектеулі
көлемі, дайын өнімдердің жеке өлшемінің бағасы берілуі тиіс.
Мысал. Екі түрлі Р1 және Р2 өнімдерін шығару үшін S1, S2, S3, S4 төрт
түрлі ресурс пайдаланатын бір кәсіпорынды алайық. Ресурс ретінде шикізат,
ақша, құрал-жабдық, жұмыс күші және т.б. алынады. Өнімнің дара түріне
жұмсалатын ресурс мөлшері, ресурс көлемі, өнім бірлігінен алынатын пайда
төмендегі кестеде берілген.
|Ресурс |Ресурстың |Өнім бірлігін дайындауға жұмсалған |
|түрлері |жалпы қоры |ресурс бірлігінің саны |
| | |P1 |P2 |
|S1 |18 |1 |3 |
|S2 |16 |2 |1 |
|S3 |5 |0 |1 |
|S4 |21 |3 |0 |
|Өнім бірлігінен алынатын |2 |3 |
|пайда, сом | | |
Өнімді сатқанда пайда максималды болатындай сол өнімді шығару жоспарын
құрыңыз.
Шешуі. Есептің экономикалық-математикалық моделін құрамыз.Ол үшін шартты
белгілеу енгіземіз. х1, х2-шығарылатын Р1 және Р2 өнімдерінің саны.
Өнімдерді дайындауға [pic] ресурсының [pic] бірлігі, [pic]-ң [pic]
бірлігі, [pic]-ң [pic] бірлігі, [pic][pic] бірлігі кетеді. Өнімді шығару
барысында жұмсалатын ресурстар қоры есепте берілген қордан аспау керек,
яғни қор 18, 16, 5, 21. Соңында мынадай теңсіздіктер жүйесін алуға болады:
[pic] (1.1)
және есеп мағынасы бойынша
[pic]. (1.2)
Сомалық пайда F Р1 өнімін сатқанда 2х1 және Р2 өнімін сатқанда 3х2 сом,
яғни
[pic] (1.3) - мақсат функция
Сонымен есептің экономикалық-математикалық моделі (3) мақсатты
функцияға максималды мән әперетін және (1) теңсіздік пен (2) шартты
қанағаттандыратын [pic]өнімді шығару жоспарын табу керек.
Есептің жалпы түрі. [pic]айнымалысы бар [pic]сызықты теңдеулер жүйесі
[pic] (1)
және сызықты функция
[pic]. (2)
[pic], (3)
берілген. [pic] (2) сызықты функциясына оптималды мән әперетін (яғни
максималды немесе минималды) (1) теңсіздік пен (3) шартты қанағаттандыратын
[pic] оптималды жоспарын табу керек.
(1) жүйе шектеулер жүйесі, ал функция [pic] - сызықты функция,
мақсатты функция деп аталады.
Сызықты программалау есебінің оптимальды шешімі (немесе оптимальды
жоспары) деп [pic] (2) сызықты функциясына оптималды мән әперетін (яғни
максималды немесе минималды) (1) теңсіздік пен (3) шартты қанағаттандыратын
[pic] шешімі аталады.
"Шешім" және "жоспар" – синонимдер, бірақ бірінші жиі қолданылады.
([pic]) теріс емес шарты орындалып, (1) шектеулер жүйесі тек
теңсiздiктерден тұрса, онда ондай есеп стандартты деп аталып, ал тек
теңдіктер жүйесінен тұратын шектеулер жүйесі канондық, яғни негізгі есеп
деп аталады. Жоғарыда келтірілген есеп стандартты есеп.
Сызықты программалаудың кез-келген есебін жалпы, стандартты, канондық
түрге келтіруге болады. Келесі мынадай теореманы қарастырайық.
Теорема 1.1. [pic]
(4)
теңсіздігінің кез келген [pic] әрбір шешіміне
[pic]
(5)
мұндағы [pic], (6) теңдеуінің анықталған әрбір шешімі сәйкес келеді
және керісінше (5) теңдеудің және (6) теңсіздіктің [pic] шешіміне (4)
теңсіздіктің [pic] әрбір шешімі сәйкес келеді.
Осы теореманы пайдаланып, стандартты есепті канондық түрге
келтірейік. Ол үшін теңсіздіктер жүйесін теңдіктер жүйесіне ауыстырамыз.
Яғни қосымша [pic]айнымалыларын енгіземіз. Онда теңсіздік белгісі ( болса,
айнымалы қосылады, ( болса, алынады. Сонда жүйе:
[pic] (1.4)
Осылайша, (1.1) стандартты есеп канондық түрде: (1.4) жүйесін және
(1.2) шартын қанағаттандыратын, (1.3) функциясын максималды мән әперетін .
[pic] шешімді табу керек.
Бақылау сұрақтары:
1. Есептің математикалық моделі дегеніміз не?
2. Экономикалық есептің математикалық моделі дегеніміз
не және ол қалай тұрғызылады?
3. Сызықты программалаудың жалпы есебін талдаңыз.
4. СПЕ шектеулердің қандай түрлері бар?
5. СПЕ жазудың жалпы формасы.
6. СПЕ жазудың стандартты формасы.
7. СПЕ жазудың негізгі (канондық) формасы.
8. Бір теңсіздіктен теңдікке қалай ауысуға болады?
9. Қосымша айнымалы дегеніміз не?
10. Максимумнен минимумге ұмтылатын функцияға қалай
көшуге болады?
Дәріс № 2
Тақырып: Сызықты программалау есебін шешудің графикалық әдісі
Дәріс сұрақтары:
• Графикалық әдісті пайдалану облысы.
• Сызықты программалау есептерін графикалық әдіспен шешудің
алгоритмі.
• Графикалық әдіспен есептерді шешу кезіндегі мүмкін жағдайлар.
Сызықты программалаудың есептерінің мүмкін болатын шешімдер жиыны
дөңес көпбұрышты (немесе дөңес көпбұрыш облысын) құрайды, ал есептің
оптималды шешімі шешімдер көпбұрышының 1 бұрыштық нүктесінде болады. Екі
белгісізі бар сызықты программалаудың стандартты есебінің мысалын
қарастырайық.
[pic]
Сызықтық программалау есебін графиктік әдіспен шешудің алгоритмі
Түзулердің графигін салу. Түзулердің теңдеуі шектеулік белгісін тура теңдік
белгісіне ауыстыру арқылы алынады.
[pic]
Сызықты программалаудың оптималды шешімі дөңес беттің шегінде болады.
Есептің шектеулер жүйесінен анықталатын жарты жазықтықты табу.
Шешімдердің көпбұрышын табу керек.
Мүмкін болатын шешімдердің векторы
[pic] табу.
Шешімдер көпбұрышы арқылы өтетін [pic] ([pic] - кез келген сан), түзуін
салу.
[pic] түзуін [pic] бағытымен перпендикуляр вектор бағытында жылжыту керек.
Нәтижесінде мақсатты функция не максимум немесе мимнимум мәнге жететін
нүктелерді, не шексіздікке жететінін анықтау.
Функция максимумының координат нүктелерін анықтап, мақсатты функцияның сол
нүктедегі мәнән есептеу.
Бақылау сұрақтары:
1. СПЕ шешудің графикалық әдісін қандлай жағдайларда пайдалануға болады?
2. Математикалық программалау есебінің жеткілікті шешімі мен жеткілікті
шешім облысы дегеніміз не?
3. СП есебінің геометриялық интерпретациясы неден тұрады?
4. СПЕ шешудің графикалық әдісінің негізгі сатылары қандай?
5. СП есебінің оптималды шешімі дегеніміз не?
6. СП есебін шешу кезінде қандай жағдайлар болуы мүмкін?
7. Шешімнің көпбұрышының қандай нүктесінде СП есебінің сызықты функциясы
өзінің оптималды мәніне жетеді?
8. Суреттен СПЕ шешімі бар немесе оның оптимумы [pic] жатқандығын қалай
анықтауға болады?
Дәріс № 3,4
Тақырып: Сызықты программалау есептері. Сызықты программалау есептерін
шешудің симплекс әдісі.
Дәріс сұрақтары:
• Симплекс-әдістің қолданылу облысы.
• Симплекс әдістің алгоритмі.
• Тірек жоспар құру.
• Оптималдылық белгісі.
Сызықты программалау есебін шешудің Симплекс әдісі бір тірек жоспарын
екіншісіне ауыстыруға негізделген, осы кезде мақсат функцияның мәні өседі.
Егер қандай да бір тірек жоспар белгілі болса, көрсетілген көшіру мүмкін
болады.
[pic]
[pic]
шарттарын қанағаттандыратын
[pic]
функциясының максималды мәнін табу керек болсын.
Мұндағы [pic]және [pic]- берілген тұрақты сандар ([pic]және [pic]).
Берілген есептің векторлық формасы келесідей түрде болады:
[pic] (1)
[pic], (2)
шартын қанағаттандыратын
[pic]
(3)
функциясының максимумын табу керек.
Мұндағы
[pic]; [pic]; ...; [pic];
[pic]; ... ; [pic]; [pic].
Өйткені [pic] болғандықтан, онда [pic] тірек жоспардың анықтамасы
бойынша берілген есептің тірек жоспары болып табылады. Бұл жоспар m-өлшемді
кеңістіктің базисін құрайтын [pic] бірлік векторлар жүйесін анықтайды.
Теорема 1.1. (тірек жоспарының оптималдылық белгісі). Егер кез келген
j [pic] үшін [pic]болса, (1)-(3) есептердің [pic]тірек жоспары оптималды
болып табылады.
Теорема 1.2. Егер қандай да бір j=k үшін [pic] және [pic] [pic]
сандар ішінде оң сан жоқ болса, онда (1)-(3) есептердің (1) мақсат
функциясы оның жоспарларының жиынымен шектелмеген.
Теорема 1.3. Егер (1)-(3) есептердің Х тірек жоспары көрсетілмесе және
[pic] болса, бірақ [pic] сандарының ішінде оң сандар бар болса, онда[pic]
сияқты Х1 тірек жоспары бар болады.
Жоғарыдағы теоремалар табылған тірек жоспары оптималды болатынын
тексеруге мүмкіндік береді және жаңа тірек жоспарға ауысуды мақсатқа
лайықты көрсету.
|i |Базис |Cб |
| | |Р1 |Р2 |
|S1 |18 |1 |3 |
|S2 |16 |2 |1 |
|S3 |5 |- |1 |
|S4 |21 |3 |- |
Р1 және Р2 өнімдерінің бірлігінен алынатын пайда сәйкесінше 2 және 3
теңге. Оны өндіруден пайда максималды болатындай өнімді өндірудің жоспарын
құру керек.
[pic]
[pic]
[pic] [pic] [pic] [pic] [pic] [pic] [pic]
[pic]
|i |Базис |Сб |
| |А |В |С | |
|І |18 |15 |12 |360 |
|ІІ |6 |4 |8 |192 |
|ІІІ |5 |3 |3 |180 |
|Бір бұйымның |9 |10 |16 | |
|бағасы (тн) | | | | |
Бақылау сұрақтары:
1. Симплекс-әдістің мәні неде?
2. СП есебінің моделі қандай түрде жазылу керек?
3. Бірінші базистік шешімді қалай құруға болады? Ол қандай жағдайда СП
есебінің тірек шешімі болады?
4. Бір тірек шешімнен екіншісіне көшу неше сатыдан тұрады?
5. Егер бастапқы жоспар оптималды болып табылмаса, базиске қосу үшін
вектор қалай анықталады?
6. Базистен шығарып тастауға жататын векторды қалай анықтауға болады?
7. Қандай элемент шешуші болып табылады?
8. Симплекс-әдісте СП есебін шешуде оптималды критерий болып не табылады?
9. Кестеден мақсат функцияның ағымды мәні қалай анықталады?
10. СПЕ шешу кезінде симплекс-әдіс алгоритмін тәжірибе жүзінде өндірудің
тізбектелген сатысын талдаңыз.
Дәріс № 5,6
Тақырып: Сызықты программалау есептері. Сызықты программалау есептерін
шешудің М-әдісі (жасанды базис әдісі)
Дәріс сұрақтары:
• Әдістің қолданылу облысы.
• Кеңейтілген есеп құру.
• Сызықты программалау есептерін жасанды базис әдісімен шешу
алгоритмі.
Жасанды базис әдісін пайдалану үшін алдымен есеп сызықты программалаудың
негізгі есебі түрінде жазылуы тиіс. Ол былайша жазылады:
[pic] (1.1)
[pic] (1.2)
[pic] (1.3)
Көпшілік жағдайда берілген сызықты программалаудың негізгі есебінің
шектемелері – теңдеулер жүйесінің (1.2) негізгі матрицасынан рангы m-ге тең
бірлік матрицаны бөліп алуға мүмкіндік бермейді. Мұндай жағдайда жасанды
базис әдісі қолданылады.
Айталық, (1.1)-(1.3) сызықты программалаудың негізгі есебі берілсін
және оның базисі анықталмаған болсын. Берілген есепті шешудің жасанды
базис әдісі бойынша қосымша айнымалылар [pic] және өте үлкен сан М
енгізіледі. Мұндағы [pic].
Енді берілген (1.1)-(1.3) есебінің орнына «кеңейтілген» есеп (немесе
М-есебі) қарастырылады:
[pic] (1.4)
[pic] (1.5)
[pic] (1.6)
Бұл есептің (1.4)-(1.6) тірек жоспары бірден анықталады:
[pic] (1.7)
Мұндағы [pic] жасанды базисті құрайды, ал [pic] - еркін айнымалылар
болады.
Алғашқы (1.1)-(1.3) және «кеңейтілген» (1.4)-(1.6) есептерінің
арасындағы байланысты келесі теорема анықтайды.
Теорема. Егер кеңейтілген есептің (1.4)-(1.6) тиімді шешіміндегі жасанды
айнымалылар нөлге тең болса, онда алғаш берілген есептің (1.1)-(1.3)
тиімді шешімі де сол болады.
Осы теореманың тұжырымы бойынша алдымен кеңейтілген есеп (1.4)-(1.6)
есебі симплекс тәсілімен шешілуге тиіс және алған шешімдегі жасанды
айнымалылар нөлге тең болуы керек. Егер жасанды айнымалының ең болмағанда
біреуі нөлге тең болмаса, онда ол есептің тиімді шешімі болмайды.
Егер кеңейтілген есептің алғашқы тірек шешімін (1.7) қарастырсақ, онда
оның мақсат функциясының мәні былайша табылады:
[pic]
ал [pic] мәндері:
[pic] (1.8)
Осы формула бойынша [pic] екі бөлімнен тұрады: біріне М кірсе, екіншісі
бос болады. Сондықтан кеңейтілген есепті шешу кезінде симплекс кестесінде
екі индексті жол болады: m+1-ге [pic]-дың бос мүшесі, ал М-нің коэффициенті
m+2-ге жазылады.
Кеңейтілген есепті шешу кезінде итерация m+2-ші жол бойынша
анықталады. Ол итерация екі түрлі жағдайға дейін қайталанады:
а) барлық жасанды айнымалылар базистен түгел шығарылғанша;
б) жасанды айнымалылар түгел шығарылмай, бірақ m+2-ші жолда теріс
элементтер болмағанға дейін;
Егер а) жағдайы орындалса, онда итерация m+1-ші жол бойынша
жалғастырылады.
Егер б) жағдайы орындалса, онда да екі түрле вариантболуы мүмкін:
І. егер m+2-ші жолдың В1 орналасқан тік жолының элементі теріс болса,
онда берілген есептің шешуі болмайды;
ІІ. егер ол нөлге тең болса, онда берілген есептің табылған тірек шешімі
аайныған болады және базисте ең болмағанда бір жасанды айнымалы болады.
Сонымен, сызықты программалаудың негізгі есебін жасанды базис әдісімен
шешу келесі тәртіп бойынша орындалуға тиіс:
1. кеңейтілген есепті құрастыру (1.4)-(1.6)
2. кеңейтілген есептің тірек шешімін табу
3. Симплекс әдісімен жасанды айнымалылар базистен шығарылады, осының
нәтижесі бойынша алғашқы берілген есептің тірек шешімі табылады немесе оның
шешілмейтіндігі дәлелденеді.
4. табылған тірек шешім бойынша алғашқы берілген есептің шешуі
ізделінеді.
Ескерту: Егер берілген есепте бірлік векторлар бар болса, олар базиске
енгізілуге тиіс.
Мысалдар қарастырайық.
Бақылау сұрақтары:
1. СП есебін шешу үшін қандай жағдайда жасанды базис әдісі пайдаланылады?
Бұл симплекс-әдіс модификациясының мәні неде?
2. М-есеп қалай тұрады?
3. Қандай айнымалы жасанды деп аталады?
4. М дегеніміз не?
5. М-есеп қалай есептеледі?
6. М-есепті шешу бойынша бастапқы есеп шешімі қалай анықталады? Мүмкін
жағдайларды атаңыз.
7. Кеңейтілген есептің оптималды жоспары қай уақытта бастапқы есептің
оптималды жоспары болып табылады?
8. Жасанды базисті пайдалану кезінде базиске енгізуге жататын вектор
қалай анықталады?
Дәріс №7
Тақырып: Сызықты программалау әдісі. Сызықты программалаудың қосжақты
есебі.
Дәріс сұрақтары:
• Қосжақтылық түсінігі.
• Қосжақты есептерді құру ережелері.
• Симметриялы, симметриялы емес және аралас жұптар.
Сызықты программалау есебін қарастыру кезінде оған басқа сызықты
программалау есебін сәйкестендіруге болатын мүмкіндік бар екен. Ондай
қасиетті қосжақтылық деп атайды. Алғашқы есеп пен онымен қосжақтылық
құрайтын есеп арасындағы байланыс оларды шешуді жеңілдетіп, сонымен бірге
шешімдерге экономикалық талдау жасауда белгілі қорытындыларға келтіреді.
1) Қосжақтылық туралы түсініктері
Сызықты программалау есебі қарастырылсын:
[pic] (1)
Келесі шарттар бойынша:
[pic]
Бұл есепті алғашқы деп, оған сәйкес келесі есепті қарастырайық:
[pic] (5)
Келесі шарттар бойынша:
[pic]
Онда бұл (5)-(8) есебі алғашқы (1)-(4) есебіне қосжақты деп
есептелінеді. Бұл екі есеп қосжақтылық жұбын құрайды.
Осылардың қорытындысы бойынша қосжақты есепті алу үшін келесі
амалдарды орындау қажет:
а) В(b1, b2,…, bm) және C(c1, c2,…, cn) векторлардың орнын ауыстыру;
б) А матрицасын транспонирлеу;
в) максимумның орнына минимумды табу;
г) егер xj>0 болса, онда j-ші шарт (6) түріндегі теңсіздік болады; ал xj
кез келген мәнді қабылдайтын болса, онда j-ші шарт (7) түріндегі теңдеу
болып жазылады. Егер і-ші (2) түріндегі теңсіздік болса, онда [pic], ал
уі<0 болса, онда ол кез келген мән қабылдайды.
Қосжақты есептердің жұбы симметриялы және симметриялы емес болуы
мүмкін.
Мысалы, симметриялы есептер:
[pic] (9)
[pic] (10)
[pic] (11)
[pic] (12)
[pic] (13)
[pic] (14)
Симметриялы емес есептер:
[pic] (15)
[pic] (16)
[pic] (17)
[pic] (18)
[pic] (19)
Мысалы: Үш түрлі А, В және С өнімдерін шығару үшін шикізаттың үш түрі
пайдаланылады. Шикізат түрінің әрбіреуі 180, 210 және 244 кг. кем емес
көлемде пайдалануы мүмкін.
|Шикізат түрі |Шикізат шығынының нормасы |
| |А |В |С |
|І |4 |2 |1 |
|ІІ |3 |1 |3 |
|ІІІ |1 |2 |5 |
|Өнім бірлігінің |10 |14 |12 |
|бағасы | | | |
Өнімді шығару кезінде оның максималды бағасын қамтамасыз ететін жоспарды
анықтау керек.
Шешуі:
[pic]
[pic]; [pic]
С=(10; 14; 12); B=(180; 210; 244)
[pic]
2) Алғашқы және оның қосжақты есебінің шешімдерінің арасындағы байланысты
анықтау үшін келесі лемма мен теореманы қарастырайық. Мысал ретінде (9)-
(11) және (12)-(14) есептерін алайық. Олардың алғашқысы өндірісті жоспарлау
туралы есептің математикалық моделінен табылған есеп.
Лемма. Егер (9)-(11) және (12)-(14) есептерінің шешімдері болатын
болса, онда Ғ мақсат функциясының мәні Z функциясының мәнінен үлкен
болмайды:
[pic] (20)
Теорема. Егер қосжақтылық есептердің бірінің тиімді шешімі болса,
онда екіншісінің де шешімі болады; ал егер біреуінің мақсат функциясы
шектелмеген болса, екіншісінің шешімі болмайды; қосжақтылық жұбының
есептерінің мақсат функцияларының экстремал мәндері үшін келесі теңдік
орындалады:
[pic] (21)
Бақылау сұрақтары:
1. Қосжақты есеп жұбының математикалық моделін жазыңыз.
2. Қосжақты есеп жұбының экономикалық интерпретациясын беріңіз.
3. Қосжақты есепті бастапқы есепке құру ережесін талдау.
4. Сызықты программалауда қосжақтылықтың мәні неде?
5. Бастапқы есеп шикізатты оптималды пайдаланудан тұрады дейік. Қосжақты
есепке экономикалық интерпретациясын беріңіз.
6. СП қандай есебі симметриялық емес және симметриялыққа жатады, олардың
айырмашылығы неде?
Дәріс №8
Тақырып: Қосарластың негізгі теоремаларызадач. Қосалқылықтың негізгі
теоремаларыҚо. Қосарлас есептің экономикалық интерпретациясы.
Дәріс сұрақтары:
• Қосарластың бірінші теоремасы.
• Қосарластың екінші теоремасы.
• Қосарластың үшінші теоремасы.
Бақылау сұрақтары:
1. Қосарластың бірінші теоремасын талдаңыз және оның дәлелдеңіз.
2. Қосарластың екінші теоремасын талдаңыз және оның дәлелдеңіз.
3. Қосарластың үшінші теоремасын талдаңыз.
4. Қосарластың бірінші теоремасының экономикалық интерпретациясын
түсіндіріңіз.
5. Қосарластың екінші теоремасының экономикалық интерпретациясын
түсіндіріңіз.
6. Қосарлас бағаның экономикалық мәні неде?
Дәріс №9,10
Тақырып: Сызықты программалаудың арнайы есептері. Тасымалдау есебі.
Дәріс сұрақтары:
• Тасымалдау есебінің моделін құру.
• Есептің ашық және жабық моделі.
• Тірек жоспарды солтүстік-батыс бұрыш әдісімен табу.
• Тірек жоспарды минималды элемент әдісімен табу.
• Тірек жоспарды Фогель аппроксимациясы әдісімен табу
1) Тасымалдау есебінің жалпы қойылымы.
n-қойманың А1, А2,..., Аn әрқайсысында а1, а2,..., аn көлемінде жүк бар.
Бұл жүкті m пайдаланушыға В1, В2,..., Вm қажетті мөлшерде b1, b2,..., bm
жеткізуге тиіс және жұмсалатын қаржы берілген:
[pic]
Бұл есептерде 2 критерий қарастырылады:
1. ең аз тасымалдауға жұмсалатын уақыт
2. ең аз тасымалдауға жұмсалатын қаржы
[pic] (1)
[pic] (2)
[pic] (3)
Осы есептің математикалық моделін қарастырған кезде, келесі жағдай болуы
мүмкін.
1. [pic]. Бұл жағдайда математикалық модель жабық деп аталады.
2. [pic]. Бұл жағдайда математикалық модель ашық деп аталады. Есептеген
кезде жалған пайдаланушыны қосамыз.
3. [pic]. Бұл жағдайда да математикалық модель ашық. Есептеген кезде
жалған қоймаларды қосамыз.
Есептегенде толтырылған клеткалар саны r=m+n-1 рангке тең болу керек.
m – пайдаланушылар саны
n – қоймалар саны
Егер толтырылған клеткалар саны рангке тең болмаса, онда жоспар – ерекше
деп аталады.
2) Тасымалдау есептерінің бастапқы жоспарын анықтау үшін солтүстік-батыс
бұрыш әдісі, ең кіші элемент әдісі және Фогель аппроксимациясы әдісі, ал
оптималды жоспарды анықтау үшін потенциал әдісі қолданылады.
Мысалы: Қоймада 300, 250, 200 көлемінде үш түрлі А1, А2, А3 тауар бар.
Бұл тауарды бес берілген В1, В2, В3, В4, В5 дүкендерге 210, 150, 120, 135,
135 көлемінде жеткізу керек. Жүкті тасымалдау үшін жұмсалатын қаржы:
[pic]
Оптималды жоспарды анықтау керек.
Шешуі:
1. математикалық моделі
[pic]
[pic]
[pic]
2. Бастапқы жоспар
Тасымалдау есебін кестеде есептеуге ыңғайлы.
а) Бұл тәсіл бойынша тасымалдау есебінің үлестіру кестесі оның жоғарғы
сол жақ бұрышынан бастап толтырыла бастайды.
|қойма |пайдаланушылар |Қоры |
| |В1 |B2 |В3 |B4 |B5 | |
|А1 |4 |8 |13 |2 |7 |300 |
| |210 |90 | | | | |
|А2 |9 |4 |11 |9 |17 |250 |
| | |60 |120 |70 | | |
|А3 |3 |16 |10 |1 |4 |200 |
| | | | |65 |135 | |
|Қажеттілігі |210 |150 |120 |135 |135 |750 |
1) математикалық модель жабық;
2) r=m+n-1; r=5+3-1=7
Бұл жоспарды орындауға жұмсалатын қаржы мөлшері былайша анықталады:
Ғ=4*210+8*90+4*60+11*120+9*70+1*65+4*135=4355
[pic]
б) Ең кіші элемент әдісі. Бұл әдісте кестенің толтырылуы ең кіші тарифтен
басталады.
|қойма |пайдаланушылар |Қоры |
| |В1 |B2 |В3 |B4 |B5 | |
|А1 |4 |8 |13 |2 |7 |300 |
| |145 |20 | | |135 | |
|А2 |9 |4 |11 |9 |17 |250 |
| | |130 |120 | | | |
|А3 |3 |16 |10 |1 |4 |200 |
| |65 | | |135 | | |
|Қажеттілігі |210 |150 |120 |135 |135 |750 |
Ғ=4*145+8*20+7*135+4*130+11*120+3*65+1*135=3855
[pic]
в) Фогель аппроксимациясы әдісімен есептеу
Енді тасымалдау есебінің ашық моделін жабық түрге келтіру жолдарын
қарастырайық.
Мысал: Келесі тасымалдау есебі берілсін:
A=(200; 175; 225); B=(100; 110; 80; 190; 90)
[pic]
Шешуі:
1. математикалық моделі
[pic]
[pic]
[pic]
Теңсіздіктер санына байланысты қосымша белгісіздер енгізіледі:
[pic]
Қосымша айнымалы шамаларды енгізудің экономикалық мәні мынандай: келесі
мөлшерде жүк алатын жалған жүк алушы Вф енгізіледі.
[pic]
Ал жүк бірлігін жалған жүк алушыға жеткізу құны нөлге тең деп
есептелінеді:
[pic]
Себебі жалған жүк алушының алатын х16 жүк мөлшері жүк берушілерде қалады.
Онда есептің жабық моделінің кестесі келесі түрде болады:
|қойма |пайдаланушылар |Қоры |
| |В1 |B2 |В3 |B4 |B5 |Bф | |
|А1 |5 |7 |4 |2 |5 |0 |200 |
|А2 |7 |4 |3 |1 |10 |0 |175 |
|А3 |2 |3 |6 |8 |7 |0 |225 |
|Қажеттілігі |100 |110 |80 |190 |90 |30 |600 |
Енді бұл есепті алдыңғы есеп сияқты шешуге болады.
Бақылау сұрақтары:
1. Сызықты программалаудың тасымалдау есебін талдаңыз және оның
математикалық моделін жазыңыз.
2. Тасымалдау есебінің қандай моделі ашық деп аталады?
3. Тасымалдау есебінің қандай моделі жабық деп аталады?
4. Тасымалдау есебінің ашық моделінен жабыққа қалай көшуге болады?
5. Бастапқы тірек жоспар құрудың қандай әдістері бар?
6. Тірек жоспарды анықтау әдістерінің артықшылықтары мен кемшіліктері.
Дәріс №11,12
Тақырып: Транспорт есебінің оптималды жоспарын потенциалдар әдісімен табу.
Дәріс сұрақтары:
• Потенциал әдісінің алгоритмі.
• Тасымалдаудың оптималды емес жоспарын жақсарту.
• Қойылымын күрделендіретін транспорт есебі: Тасымалдауды рұқсат
етпеу.
• Қойылымын күрделендіретін транспорт есебі: Жүктің қандайда бір
санын жеткізу.
• Қойылымын күрделендіретін транспорт есебі: Жүктің берілгеннен
кем емес санын тасымалдау.
• Қойылымын күрделендіретін транспорт есебі: Жүктің берілгеннен
көп емес санын тасымалдау.
Тасымалдау есебінің тірек жоспарын анықтау үшін бұрын қарастырылған
әдістердің ішінен бірін пайдаланамыз. Бұл әдістер n+m-1 берілген жоспарды
алуды қамтамасыз етеді.
Теорема. Егер тасымалдау есебінің қандайда бір [pic] [pic] тірек жоспары
үшін [pic] сандары [pic] болған кезде [pic] (1)
[pic] болған кезде [pic] (2) барлық [pic] және [pic] үшінбар болса, онда
[pic] - тасымалдау есебінің оптималды жоспары.
Анықтама. [pic] сандары жіберу пункті мен белгіленген пунктке сәйкес
потенциалдар деп аталады.
Тасымалдау есебінің шешімін табу алгоритмі:
Әрбір жіберу пункті мен белгіленген пункт үшін [pic] потенциалдарын
анықтаймыз. Бұл сандарды келесі теңдеулер жүйесі арқылы табамыз:
[pic] (1)
[pic] - кестелердің толтырылған торлары тұрған тарифтер.
Толтырылған торлар саны n+m-1 тең болса, онда n+m белгісіздері бар
жүйеде n+m-1 теңдеуі бар, өйткені белгісіздер саны теңдеулер санынан көп,
белгісіздердің ішінен біреуін тұрақты санға теңестіруге болады, мысалы
[pic], ары қарай жүйені шешуге болады. Бұл жүйені шешіп болғаннан кейін,
яғни [pic] потенциалдарын тапқаннан кейін [pic] (2) теңсіздік жүйесін
анықтаймыз.
Егер [pic] ішінде оң сандар жоқ болса, онда оптималды жоспар табылды,
егер қандайда бір бос тор [pic] болса, онда жоспар оптималды емес және оны
жақсарту қажет. Ол үшін барлық [pic] үшін бос торларды қарастырамыз,
олардың ішінен максималдысын таңдаймыз.
Цикл – тұйықтылған көп бұрыш, онда: 1) барлық жақтары жолдар мен
бағандарда жатады, 2) барлық бұрыштары түзу, 3) барлық төбелері толтырылған
торларда жатады.
Төбелер саны оң сандар және «оптималды емес» тор циклдің кез келген
төбесінде орналасуы мүмкін. Тасымалданатын жүкті цикл бойынша жылжытамыз.
Осы тасымалданатын жүктің төбесін анықтау үшін мыналарды қоямыз:
|Қойма |пайдаланушылар |қоры |
| |В1 |В2 |В3 |В4 | |
|А1 |1 |2 |3 |4 |120 |
| |100 | |20 | | |
|А2 |2 |1 |5 |3 |80 |
| | |70 |10 | | |
|А3 |8 |6 |3 |1 |40 |
| | | |20 |20 | |
|қажеттілікт|100 |70 |50 |20 |240 |
|ері | | | | | |
Ең кіші элемент әдісімен тірек жоспарды табамыз.
F=1*100+3*20+1*70+5*10+3*20+1*20=360
Толтырылған торлар үшін
[pic]
Бос торлар үшін
[pic]
(2,1) торы үшін жоспар оптималды емес, ешдеше оны жақсарту қажет.
[pic]. Осы санды «-» торлардан алып тастаймыз және «+» торларына қосып,
жаңа тірек жоспарды аламыз.
|Қойма |пайдаланушылар |қоры |
| |В1 |В2 |В3 |В4 | |
|А1 |1 |2 |3 |4 |120 |
| |90 | |30 | | |
|А2 |2 |1 |5 |3 |80 |
| |10 |70 | | | |
|А3 |8 |6 |3 |1 |40 |
| | | |20 |20 | |
|қажеттілікт|100 |70 |50 |20 |240 |
|ері | | | | | |
Ғ2=350. алдыңғыға қарағанда жақсы, тағы да потенциалдар әдісімен
тексереміз.
Толтырылған торлар үшін
[pic]
Бос торлар үшін
[pic]
Екі шарт та орындалды, демек табылған жоспар оптималды.
F=1*90+3*30+2*10+1*70+3*20+1*20=350
Бақылау сұрақтары:
1. Тасымалдау кестесінде неше бос емес торлар тасымалдаудың тірек
жоспарына сай келеді? Немен түсіндіріледі?
2. Цикл дегеніміз не?
3. Бір тірек жоспардан екіншісіне қалай көшуге болады?
4. Потенциалдар әдісімен тасымалдау есебін шешу кезінде оптималдылық
критерийі қалай анықталады?
5. Потенциалдар әдісінің алгоритмін сипаттаңыз.
Дәріс №13,14
Тақырып: Ойындар теориясы.
Дәріс сұрақтары:
• Ойындар теориясының негізгі түсініктері.
• Ойын классификациясы.
• Ойынның жоғарғы және төменгі бағасын анықтау.
• Ойын есептерінің геометриялық интерпретациясы.
• Ойындар теориясы есептерін сызықты программалау есептеріне
теңестіру.
1) Практикалық есептерде белгісіз шарттар арқылы шешім қабылдау керек.
Ондай шарттарды «ситуация» деп атаймыз. Ондай ситуациялар келесі ойындарда
болуы мүмкін: шахмат, шашка, домино және т.б., ал экономикада ол банк пен
клиент, сатушы мен сатып алушы және т.с.с. Әрбір ойында ережелер беріледі.
Егер ойынға қатысушылар екеу болса, онда ойын «жұп» деп аталады. Егер көп
болса, «көптік» ойын деп аталады. Есептерде ойын төлем матрицасы арқылы
беріледі. Әрбір матрицаның бағасы болады: [pic] - төменгі баға, [pic] -
жоғарғы баға.
Анықтама 1. [pic] ойынның төменгі бағасы немесе максимин, ал оған сәйкес
стратегия (жол) – максиминді деп аталады.
Анықтама 2. [pic] ойынның жоғарғы бағасы немесе минимакс, ал оған сәйкес
ойыншы стратегиясы (баған) – минимаксті деп аталады.
Анықтама 3. Егер [pic]болса, онда [pic]ойынның таза бағасы деп аталады.
Егер таза бағасы [pic] табыса, онда есеп «таза стратегия» арқылы есептеледі
деп саналады.
Мысалы:
[pic] Ойынның бағасын анықтау керек. Төлем матрицасы берілген.
| |В1 |В2 |В3 |[pic|
| | | | |] |
| А1 |0,5 |0,6 |0,8 |0,5 |
|А2 |0,9 |0,7 |0,8 |0,7 |
|А3 |0,7 |0,6 |0,6 |0,6 |
|[pic|0,9 |0,7 |0,8 | |
|] | | | | |
[pic]
2) Егер матрицамен берілген ойында шешуші нүктесі жоқ болса, онда оның
шешімін табу үшін аралас стратегия пайдаланылады. Ойын теориясында аралас
стратегияны қолдану үшін төлем матрицаның көлемі 2х2 болуы керек.
Бірінші ойыншының аралас стратегиясын [pic] векторы ретінде, ал екінші
ойыншының - [pic] векторы ретінде белгілейік, мұндағы [pic] ([pic]), [pic]
([pic]), [pic], [pic].
Егер [pic] - бірінші ойыншының оптималды стратегиясы, ал [pic] -
екінші ойыншының оптималды стратегиясы болса, онда [pic] саны ойын бағасы
болып табылады. Мұндағы [pic].
Теорема. Ойынның бағасы [pic], ал [pic] және [pic] - оптималды
стратегиялар болу үшін төмендегі теңсіздіктердің орындалуы қажетті және
жеткілікті:
[pic] ([pic]) және [pic] ([pic]).
Теорема. Егер ойыншының біреуі оптималды аралас стратегия пайдаланса,
онда оның ұтысы [pic] ойын бағасына тең болады.
Мысал 1: Матрицамен берілген ойынның шешімін табу және геометриялық
интерпретациясын беру керек.
[pic]
Шешуі:
| |В1 |В2 |[pic|
| | | |] |
| А1 |2 |5 |2 |
|А2 |6 |4 |4 |
|[pic|6 |5 | |
|] | | | |
[pic]
А ойыншыға стратегия [pic] векторымен берілсін.
[pic]
[pic] мен [pic] қатысты екі жазылған теңдеуден тыс [pic] мен [pic]
жиіліктерін байланыстыратын теңдеуді қосамыз:
[pic]
[pic]
[pic]; [pic] [pic]
Енді В ойыншыға оптималды стратегияны табу керек. Берілген ойыншыға
стратегия [pic] векторымен берілсін. Сонда
[pic]
[pic][pic]
Демек, ойынның шешімі аралас стратегиялар [pic] және [pic], ал ойынның
бағасы [pic] болып табылады.
Енді берілген ойын шешімінің геометриялық интерпретациясын берейік.
Мысал 2:
[pic] матрицасымен берілген ойынның матрицасын табу керек.
Шешуі:
[pic]
Енді В ойыншыға оптималды стратегияны табу керек. Берілген ойыншыға
стратегия [pic] векторымен берілсін. Сонда
[pic]
[pic]
[pic]
[pic]
[pic]
Демек, ойынның шешімі аралас стратегиялар [pic] және [pic], ал ойынның
бағасы [pic] болып табылады.
Ойын тоериясы есептерін сызықты программалау есептеріне келтіру
А матрицасымен анықталатын берілген ойынның шешімін табу үшін келесі
қосжақты есеп жұбын және оның шешімін табу керек.
Түзу есеп: [pic] шартын қанағаттандыратын [pic] функциясының максималды
мәнін табу керек.
Қосжақты есеп: [pic] шартын қанағаттандыратын [pic] функциясының
минималды мәнін табу керек.
Стратегияны және ойын бағасын анықтау үшін келесі формуланы
пайдаланамыз:
[pic],
[pic]
Мысал:
[pic] матрицасымен анықталатын ойынның шешімін табу керек.
1. Түзу есеп:
[pic] табу керек.
2 Қосжақты есеп:
[pic]
Түзу және қосжақты есептің оптималды жоспарын табу керек.
|i |Базис |Сб |Р0 |1 |1 |1 |0 |0 |0 |
| | | | |Р1 |Р2 |Р3 |Р4 |Р5 |Р6 |
|1 |Р4 |0 |1 |1 |2 |0 |1 |0 |0 |
|2 |Р5 |0 |1 |1 |0 |1 |0 |1 |0 |
|3 |Р6 |0 |1 |2 |1 |0 |0 |0 |1 |
|m+1 | | |0 |-1 |-1 |-1 |0 |0 |0 |
|1 |Р4 |0 |1 |1 |2 |0 |1 |0 |0 |
|2 |Р3 |1 |1 |1 |0 |1 |0 |1 |0 |
|3 |Р6 |0 |1 |2 |1 |0 |0 |0 |1 |
|m+1 | | |1 |0 |-1 |0 |0 |0 |0 |
|1 |Р2 |1 |1/2 |1/2 |1 |0 |1/2 |0 |0 |
|2 |Р3 |1 |1 |1 |0 |1 |0 |1 |0 |
|3 |Р6 |0 |1/2 |3/2 |0 |0 |-1/2 |0 |1 |
|m+1 | | |3/2 |1/2 |0 |0 |1/2 |1 |0 |
Оптималды жоспар [pic]
Ал қосжақты есептің оптималды жоспары [pic].
[pic].
Ойыншылардың оптималды стратегиялары
[pic]
Бақылау сұрақтары:
1. Ойындар теориясының негізгі түсінігін беріңіз.
2. Ойындар теориясымен шешілетін экономикалық есептерге мысал келтіріңіз.
3. Қандай жұптық есептер матрицалық деп аталады? Төлемдік матрицаны
құруға мысал келтіріңіз.
4. Матрицалық ойынның жоғарғы және төменгі бағасын қалай анықтауға болады
және олардың арасында қандай қатынас бар?
5. Ойынды жеңілдететін қандай әдістер бар?
6. Матрицалық ойын мен сызықты программалау есебінің байланысы неге
негізделген?
Дәріс №15
Тақырып: Динамикалық программалау
Дәріс сұрақтары:
• Динамикалық программалаудың негізгі түсініктері.
• Беллман оптималдылығының принципі.
• Динамикалық программалау әдісінің идеясы.
Динамикалық программалау оптимизациялық әдіс деп саналады. Шешім
қабылданған болуы мүмкін сондықтан бұл операциялар көп қадамды деп аталды.
Әрбір есеп итерацияға бөлінеді. Әрбір итерацияның мақсат функцияның мәні
мах ұмтылу керек. Динамикалық программалау мынадай есептерде қолданылады.
1. Қор-р мен басқару ережелерде
2. Ремонт жасаған кезде
3. Оптимальды жоспарды анықтаған кезде және т.б.
xr-басқармалар
S-жүйенің күйі
Егер бірнеше жүйе қарастырылса, онда былай жазылады: S1, S2,...Sn
Динамикалық есептерде басқармалары беріледі. Бұл басқармалар жүйенің
күйін бір күйден екіншіге ауысады
S0 S1
График түрінде жүйе былай беріледі
х1 х2 хn
хn+1 хk
Мақсат функциясы әффективті критерий бойынша былай жазылады:
F=F(Sk, X)
Динамикалық моделінің ерекшеліктері
1. Экономикалық жүйенің бір күйден екінші күйге ауысуы- Марковтың процесі
деп аталады.
2. Процесс белгілі қадамға созылады, әрбір қадамда бір басқару таңдап
алынады да, сол арқылы жүйе бір күйден екінші күйге ауысады.
3. Әрбір қадам эффективті критерий бойынша оптимальды деп саналады.
4. Мақсат функциясы әрбір қадамның мақсат функцияның қосындысы деп
алынады
2. Динамикалық программалау есебі Бэллман теңдеуі арқылы шығарылады.
Бэллман теңдеуі оптимальды принцип деп аталады. Ең алғашқы рет оптимальды
принципін 1953жылы ұсынған
Zr (Sk-1) max xk tk (Sk+1; xk)+Zk+1 (Sh)
|X |20 |40 |60 |80 |100 |
|k1 |7 |21 |32 |44 |58 |
|k2 |9 |11 |37 |42 |54 |
|k3 |9 |23 |41 |51 |61 |
|k4 |11 |21 |39 |49 |78 |
[pic]х=20 n=5 t=4
[pic]1 (х)= max S1 (x)
[pic]2 (х)= max S2 (x)2+[pic]1 (х-x2)
… … … … … …
[pic]n (х)= max Sn (xn-2)+[pic]n-2 (х-x2)
Бақылау сұрақтары:
1. Динамикалық программалау әдісімен шешілетін қандайда бір есепке мысал
келтіріңіз.
2. Оның математикалық моделін құрыңыз. Бұл модель СП моделі болып
табылады ма?
3. Беллман оптималдылығының принципі неден тұрады?
4. Беллманның (функционалды теңдеу) негізгі рекурентті қатынасы.
5. Динамикалық программалау әдісімен есепті шешудің сатыларын сипаттаңыз.
3. ПРАКТИКАЛЫҚ САБАҚТАР
Тақырып: Экономикалық-математикалық модельдеуге кіріспе
Сызықты программалау есебін жазудың үш формасы.
Сабақтың мақсаты
Білулері керек:
• Қарапайым экономикалық есептердің математикалық моделін құру;
• СП есебі қандай формада жазылғандығын анықтау керек;
• СП есептерін жазудың бір формасынан екіншісіне көшу.
Тапсырма: {1} 41 б. № 47
{2} 66 б. № 4
Тақырып: Сызықты программалау есептерін шешудің графикалық әдісі.
Сабақтың мақсаты:
Білулері керек:
• функцияның мүмкін мәндерінің облысын анықтау және графигін құру;
• есептің оптималдық шешімін табу немесе графикалық әдіспен мақсат
функцияның шексіздігі үшін шешімнің жоқтығы;
• Стандартты, жалпы және негізгі формада жазылған СП есебін шешу.
Тапсырма: {1} 50 б. № 63 (1, 2, 4, 9 10)
Тақырып: Сызықты программалау есептерін шешудің симплекс әдісі
Сабақтың мақсаты:
Білулері керек:
• СП қай есебін симплекс-әдісімен анықтауға болады;
• тірек шешімдер құру керек;
• симплекс-кесте құру және оны шешу керек;
• оптималды шешімді табу керек.
Тапсырма: {1} 65 б. № 88 (3, 4, 5)
{2}66 б. № 4
Тақырып: Сызықты программалау есептерін шешудің М-әдісі
Сабақтың мақсаты:
Білулері керек:
• СП қай есебін жасанды базис әдісімен анықтауға болады;
• бастапқыға кеңейтілген есепті құру керек;
• оптималды шешімді табу керек.
Тапсырма: {1} 65 б. № 88 (1, 2, 9)
Тақырып: Сызықты программалаудың қосарлас есебі.
Сабақтың мақсаты:
Білулері керек:
• бастапқыға қосарлас есеп құру керек;
• симметриялық, симметриялық емес және аралас жұпты анықтау керек;
Тапсырма: {1} 71 б. № 93
Тақырып: Қосарластың негізгі теоремаларызадач. Қосалқылықтың негізгі
теоремаларыҚо. Қосарлас есептің экономикалық интерпретациясы.
Сабақтың мақсаты:
Білулері керек:
• қосарлас есептің жұбын графикалық әдістің біреуімен табу;
• қосарлас есептің жұбын симплекс әдісімен табу;
Тапсырма: {1} 72 № 94(1, 2), 77 б. № 103 (1), 80 б. № 109
Тақырып: Транспорт есебі. Транспорт есебінің тірек жоспарын табу
Сабақтың мақсаты:
Білулері керек:
• транспорт есебінің моделін құру;
• транспорт есебінің ашық немесе жабық моделін анықтау;
• солтүстік-батыс бұрыш әдісімен тірек жоспарды табу;
• минималды элемент әдісімен тірек жоспарды табу;
• Фогель аппроксимациясы әдісімен тірек жоспарды табу.
Тапсырма: {1} 89 б. № 120, 104 б. № 145
Тақырып: Потенциалдар әдісі. Қосымша шарттары бар транспорт есебі.
Сабақтың мақсаты:
Білулері керек:
• потенциалдар әдісімен транспорт есебінің оптималды шешімін табу;
• жүкті оптималды емес етіп бөлуден екіншісіне көшу;
• өткізгіштік мүмкіндігі бойынша шектеулермен транспорт есебін
шешу.
Тапсырма: {1} 89 б. № 120(1, 2), 104 б. № 145 (1, 2), 116 б. № 159 (1).
Тақырып: Ойындар теориясы.
Сабақтың мақсаты:
Білулері керек:
• төлем матрицасын құру және жеңілдету;
• оның жоғарғы және төменгі бағасын анықтау;
• берілген матрицаны (2 х 2), (2 х n) және (m х 2) графикалық
әдіспен шешу;
• ойындар теориясы есебін СП есебіне келтіру және оны шешу.
Тапсырма: {1} 172 б. № 260, 174 б. № 261, 178 б. № 267 (1, 2, 6, 7)
Тақырып: Динамикалық программалау
Сабақтың мақсаты:
Білулері керек:
• ресурстарды бөлу есебін шешу;
Тапсырма: Өнімді өндірудің жалпы өсімі максималды болатындай төрт кәсіпорын
арасында 100 мың теңгені бірдей бөлуді анықтау керек.
|Сомма (мың теңге) |[pic] |[pic] |[pic] |[pic] |
|20 |14 |12 |11 |16 |
|40 |26 |28 |24 |21 |
|60 |40 |39 |43 |36 |
|80 |51 |47 |51 |49 |
|100 |68 |69 |68 |72 |
4. студенттің өздік жұмысы
4.1.Өздік жұмысты ұйымдастыру бойынша әдістемелік нұсқаулар: студенттің
өздік жұмысы (СӨЖ) реферат түрінде орындалады және студенттердің өздік
жұмысын қойлатын талаптарға сәйкес тапсырылады.
Өздік жұмысты бақылау келесі формада өтуі мүмкін:
– жасалған жұмысты көрсету;
– өздік меңгерген тақырып бойынша баяндама;
– аудиториялық сабақтарды немесе ОБСӨЖ-де ауызша сұрау;
– жазбаша орындалған тапсырмаларды қорғау.
Өздік жұмысының нәтижелерін тапсырмаған студент қорытынды аттестацияға
жіберілмейді.
Өз бетімен меңгерген материал оқытушумен бірге меңгерілген материалмен
қоса қорытынды бақылауға шығарылады.
4.2.Өздік жұмыс тақырыптары:
1. Экономикалық-математикалық әдістер мен модельдер
классификациясы.
2. Сызықты программалау есебінің экономикалық-математикалық моделін
құру: Диета туралы есеп.
3. Сызықты программалау есебінің экономикалық-математикалық моделін
құру: Сұйық ұнтақ құру есебі.
4. Сызықты программалау есебінің экономикалық-математикалық моделін
құру: қиындыны минимизациялау туралы есеп.
5. Жордан-Гаусс әдісімен сызықты теңдеулер жүйесін шешу.
6. Графикалық әдіс негізінде модельді сезімталдыққа анализдеу.
7. Симплекс әдісі негізінде модельді сезімталдыққа анализдеу.
8. Қосарлы симплекс-әдіс.
9. Транспорт есебінің оптималды жоспарын табудың дифференциалданған
рента әдісі.
10. Динамикалық программалау әдісімен шешілетін экономикалық
есептер.
-----------------------
[pic]
B2
B1
[pic]
[pic]
0
z
u
+
-
[pic]
А1
А2
М
[pic]
Sk
Sn
S1
S0
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz