Файл қосу
Математикалық модельдеу негіздері
|ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БIЛIМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛIГI |
|СЕМЕЙ ҚАЛАСЫНЫҢ ШӘКӘРIМ АТЫНДАҒЫ МЕМЛЕКЕТТIК УНИВЕРСИТЕТI |
|3-деңгейлi СМЖ құжаты |ПОӘК | |
| | |ПОӘК |
| | |042-18-11.1.20.46/03-201|
| | |3 |
|ПОӘК | №1 баспа | |
|«Басқарудың моделдері мен |26.08.2013 ж. | |
|әдістері» пәнінен | | |
|оқу-әдістемелік материалдар | | |
«Басқарудың моделдері мен әдістері» пәнінен
ОҚУ -ӘДІСТЕМЕЛІК КЕШЕНІ
050704 Есептеу техникасы және программалық қамсыздандыру
мамандығы үшiн
ОҚУ-ӘДІСТЕМЕЛІК МАТЕРИАЛДАР
Семей
2013
Мазмұны
|1 |Глоссарий |3 |
|2 |Дәрістер |5 |
|3 |Практикалық сабақтар |30 |
|4 |Өздік жұмыстар |32 |
1 Глоссарий
Сигнал- ақпаратты беруге арналған физикалық процесс
Интерфейс – бұл ақпаратты кескіндеу түрі және машина мен адам арасында
диалог жүргізу.
Қолданушы интерфейсі- қолданушының компьютермен байланысын жүргізетін
программалық және аппараттық жабдықтар жиынтығы.
Диалог дегеніміз ақиқат уақыт масштабында жүргізілетін және нақты бір
есепті шешуге бағытталған адам мен компьютер арасындағы ақпарат алмасу.
Хабарлама- ақпарат алмасуға қатысатын ақпарат бөлігі.
Формалар- қолданушы интерфейсін құрастырушы блоктар.
Процедуралық негізделген интерфейстер- «процедура» және «операция»
ұғымдарына негізделген қолданушымен әсерлесудің моделі.
Нысандық негізделген интерфейстер- белгілі-бір облыстағы нысандарды
басқаруға арналған.
Примитивті интерфейс деп қолдануышмен консольдық режимде қарым-қатынас
жүргізуді айтады.
Ақпараттық терезе- бұл екі түрде болады: хабарлама терезесі және көмек
терезесі.
Пиктограмма дегеніміз онымен байланысқан буфер мазмұнын көрсететін
графикалық кескіні бар кішкене терезе.
Метафора – бірінщіге ұқсас түрде, бірінщі нысанның қасиетін басқаға ойша
түрде тасымалдау.
Нысан-Мәліметтер қолданушыны ақпаратпен жабдықтайды.
Кестелер- мәліметтерді тұрақты сақтауға аранлған.
Сұраулар- ары қарай өңдеу үшін белгілі-бір шаблон бойынша кестеден
мәліметтер шақыру.
Формалар- мәліметтерді ыңғайлы түрде кіргізу және қарау үшін.
Сигнал- ақпаратты беруге арналған физикалық процесс
ІІ Дәрістер
1 Автоматты басқарудың модельдері туралы жалпы түсініктер
Кіріспе
Әлемнің барлық дамыған елдерінде математикалық әдістерді жеке
тәжірибелік есептермен қатар, әлеуметтік-экономикалық құбылыстар мен
транспорт жүйесінде теориялық зерттеулер үшін кеңінен қолданылады. XXI
ғасырдың басындағы негізгі қаржы және тауар ағымдары АҚШ – Еуропа –
Оңтүстік-Шығыс Азия және Қытай Республикасы үшбұрышына жинақталатындығын
көрсетіп отыр. Сонымен қатар, көліктік құрам 50120 млрд.доллар шамасында
ауытқып отырады, ал оның әр жыл сайынғы өсімі таяу келешекте жылына 6%-тен
кем болмайды. Қазіргі күннің өзінде жүкті Еуропадан Азияға және керісінше
тасымалдау көкейкесті мәселеге айналып отыр.
Инвестицияларды жоспарлау туралы шешімдер қабылдаған кездері осындай
жағдайларды есепке алу қажет. Бұл пікірді Қазақстан Республикасының
Президенті Н.Ә.Назарбаев та қолдап отыр. Ол 2004 жылдың қарашасында: «Тек
қана ішкі нарықты игеріп қоймай, сондай-ақ Орта Азияға, Қытайға Ресейдің
ірі экономикалық аймақтарына шығып, орныға алатындай қызмет көрсету
салаларын және бағыттарды барынша дамыту біздің міндетіміз болып табылады»
деп мәлімдеген болатын. Осыған байланысты геосаяси тұрғыдан тиімді
орналасқан Қазақстан «Еуропа – Азия аймақтарын біріктіретін көпір»
ретіндегі өзінің көліктік-транзиттік әлеуетін іске асыруы, көлік
инфрақұрылымын барынша оңтайландыруы тиіс.
Математикалық және құралдық әдістер жаңашыл компьютерлік және
ақпараттық технологиялардың дамуында транспорттық мәселелерді зерттеуде
ерекше бағалы орын иеленеді. Транспорттық мәселелерді шешудегі қолданылатын
экономикалық зерттеулердің әдістері тақырыбымның зерттеу өзектілігі,
экономикалық мәселелерді, оның ішінде «Қазақстан темір жолы» акционерлік
қоғамының мысалында транспорт моделінің әдістерін көрсету. Сонымен қатар
бұл жердегі ең басты өзектілігі экономиканың даму болжауы мен нақты талдау
мәселелерін зерттеуде қолданылатын экономикалық процестердің әдістері мен
модельдерді қолдану облысы болып табылады.
Қазіргі транзиттік жүктер үлкен қашықтыққа тасылған жағдайда
тасымалдаудың құны өте жоғары болатын және қауіп-қатері мол болатын
экономикалық жағдай қалыптасып отыр. Осы айтылғандардың бәрін есепке
алғанда республикадағы темір жол көлігі мен транзиттік жүк тасымалдаудың
жағдайын және оның дамуын, әлемдік көліктік жүйеге интеграциялануы
кезіндегі мәселелерін зерттеудің көкейкестілігі күмән тудырмайды.
Транспорт моделінің әдістерін өңдеуде көптеген әлемдік ғалымдар өз
үлесін қосты. Н.Ш.Кремердің, Х.Таханың, М.С.Красстың, Б.П.Чупрыновтың
ғылыми еңбектерінде транспорт моделінің экономикалық зерттеулерге қолдануы
ерекше көрініс алды.
Дәрістің мақсаты транспорттық әдістер мен модельдерді Қазақстандағы
транзиттік жүк тасымалдарының дамытуына қолдану болып табылады. Осы
мақсатты орындау үшін томендегідей міндеттер алға қойылып отыр:
▪ халықаралық практиканы және алдағы кезеңдегі даму бағыттарын есепке ала
отырып, транзиттік жүк тасымалдарының жағдайын жүйелі түрде талдап
зерттеуге сүйене отырып, оның теориялық негіздерін анықтау;
▪ темір жол көлігімен транзиттік жүк тасымалдарын жүргізетін елдерді
анықтау;
▪ жүк тасымалдарының алдағы кезеңдегі болуы мүмкін болжамдық көлемдерін
анықтаудың экономикалық-математикалық моделін дайындау;
▪ темір жол көлігіндегі транзиттік тасымалдардың қалыптасу принциптерін
анықтау;
▪ транзиттік жүк тасымалдарының жүк ағымдарын жетілдірудің
ұйымдастырушылық-экономикалық фактор ретіндегі әлеуетін ашу.
2 Автоматтандырылған жүйелерге қатысты заңдылықтарды меңгеру.
Математикалық модельдеу негіздері
Ақпараттық-коммуникациялық технологияны пайдалану қажеттігі өмір
талабынан туындап, математикалық модельдер құра алу және құрылған модель
негізінде алға қойылған есепті шеше алу мүмкіндіктерін дамыту қазіргі
кезеңде ерекше маңызды мәселелердің бірі болып отыр. Құбылыстар мен
процестерді оқып үйренуде, өндіріс пен ғылымда есептеу техникасының кеңінен
қолданылуы модельдей білу іскерлігі мен дағдыларын қалыптастыру қажеттігін
туғызуда[1]. Сондықтан қазіргі кезде есептің математикалық моделін құру,
яғни нобайлай алу мәселелері көкейкесті мәселелердің бірі болып табылады.
Математикалық модельдер кез-келген жүйенің құрылымдық өзгерістерін
сандық түрде нақты көрсете алатындықтан ғылым мен тежірибеде кеңінен
қолданылады. Мұндай модельдер білім беру жүйелерінің тиімді жұмыс істеуін
бағалауда, сонымен қатар оның дамуын болжалдау мен жобалауға да қажетті.
Алайда, таным процесінің мәнісі модельдеумен тығыз байланысты екеніне
қарамастан олар оқу үрдісінде әлі де орнымен пайдаланыла алмай келеді.
Модель, оны нобай деп баламалап атап та жүр, шын мәнісінде, кез-келген
кәсіптік танымдық жүйе, үрдіс немесе құбылысты танудың басты әмбебап ұғымы.
Модель мен модельдеу- нақты мәселеден (есептен )оның шешішіне апаратын
негізгі ұстын (көпір). Математикалық модель модельденуші жүйенің құрылымы
мен ішкі логикасына бойлап енуге мүмкіндік береді.
Модель-обьект немесе обьектінің сипаттамасы, басқаша айтқанда белгілі
бір жүйені оның қандайда бір қасиеттерін зерттеу үшін басқа жүйемен
алмастыру. Кез-келген модель белгілі бір гипотезалар, шарттылықтар
негізінде құрылады. Обьектіні матетатикалық жүйемен көрсете отырып,
обьектінің математикалық моделін аламыз. Модельдер нысанына қарай танымдық,
прагматикалық және құралдық болып табылады.
Танымдық модель- білімді үйлестіру мен таныту, ескі мен жаңа білімді
ұштастыру құралы. Ол, әдетте шындыққа лайықталған теориялық модель.
Прагматикалық модель- нақты іс-әрекеттерді ұйымдастыру тәсілі, жүйені
басқару үшін мақсаттарды айқындау. Шындық қандай да бір прагматикалық
модельге лайықталады. Прагматикалық модель қолданбалы болып табылады.
Құралдық модель- танымдық немесе прагматикалық модельдерді құру,
зерттеу және пайдалану тәсілі.
Танымдық модельдер ақиқаттағы болмысты көрсетсе, ал прагматикалық,
ақиқатта болмаса да қажетті, орындалуы мүмкін қатынастар мен байланыстарды
танытады.
Модельдеу деңгейіне қарай:
-эмпирикалық - эмпирикалық фактілер, бағыныштылықтар негізінде ;
-теориялық - математикалық сипаттау негізінде ;
-аралас, жартылай эмпирикалық- эмпирикалық бағыныштылық пен
математикалық сипаттаудан құралған болуы мүмкін;
Модельдеу (нобайлау) мәселесі үш сатыдан тұрады :
1. Модельді құру (бұл саты модель құрудың нақты алгоритмі болмағандықтан,
мейлінше формальдығының төмендігімен сипатталады).
2. Модельді зерттеу (бұл саты формальданған, әртүрлі модельдерді зерттеу
әдістері бар).
3. Модельді қолдану (құрылымдылығымен қатар нақтылығымен сипатталады ).
Қазіргі кезде ғылыми және педагогикалық зерттеулер жүргізуде, яғни
зерттеу объектілерін оқып үйренуде, оларды біліп тану үрдісінде
математикалық модельдерді қолданудың ролі артып отыр[2]. Табиғаттағы
шындық процестердің сызықтық емес жүйелерін модельдеу арқылы ақиқатты тану,
таным үрдісінің кеңеюіне және білім берудің артуына мүмкіндік береді.
Модельдеудің негізгі типтерін келтірейік :
Статикалық модель. Статикалық модельде уақыт мөлшері қолданылмайды. Ол
уақыттың әрбір үздігіндегі қалыпты көрсетеді. Мысалы, Ньютонның екінші заңы
Ғ=ma. Бұл заң салмағы m болатын материалдық нүктенің а үдеуімен
қозғалысының статикалық моделі. Бұл модель уақыт өлшеміне тәуелсіз.
Динамикалық модель. Бұл модельде параметрлер арасында уақыт өлшемі
есептеледі. Мысалы, S=gt2/ 2 формуласы дененің еркін түсуіндегі жолының
динамикалық моделі.
Дискреттік модель. Бұл модельде уақыттың дискретті сәттеріндегі
зерттелінетін құбылыстың сипаттамасы көрсетіледі. Мысалы, S=gt2/ 2
формуласымен t=0,1,2,…,10 (сек) уақыттарындағы жолдарды есептесек, онда
S0=0, S1=g/2, S2=2g,…, S10=50g моделі, мәндері алынады. Демек,
t=0,1,2,…,10 (сек ) мәндерінде S t=gt2/2 моделі, S0=0, S1=g/2,
S2=2g,…,S10=50g сандық реттілігі, дененің еркін құлауының дискреттік
моделі болып табылады.
Үздіксіз модель. Бұл модель белгілі бір уақыт аралығындағы уақыттың
барлық сәттеріндегі жүйенің өзгеруін сипаттайды. Мысалы, S=gt2/ 2 ,0=" болса, айнымалы теңсіздікке +1 коэффициентімен
енгізіледі; егер "<=" болса, -1 коэффициентімен.
Сонымен қатар, кейбір жағдайларда теңдеуде базистік айнымалы болмаған
жағдайда базистік теріс қосымша айнымалы жасау үшін барлық теңдеуді (-1)-ге
көбейтуге болады.
3.2. Векторлық анализ
Векторлық анализде әрбір айнымалы үшін векторлар құрылады: n-өлшемді
(n-жүйенің теңдеулерінің саны) вектордың координаталарын құраушылар ретінде
сәйкес теңдеулердегі айнымалының коэффициенттері алынады.
Жоғарыда айтылып кеткендей, бірлік коэффициент тек бір теңдеуде ғана
болатын, ал нольдік коэффициенттер басқаларында болатын вектор базистік
деп аталады. Каноникалық жүйеде әрбір теңдеуге тура бір базистік айнымалы
сәйкес келеді. Барлық шектеулерді тексергеннен кейін каноникалық түрдегі
жүйе алынады және бастапқы симплекс-кестені толтыру мүмкіндігі туады.
3.3. Жасанды айнымалылар тәсілі
Кейде базистік айнымалылар саны теңдеулердің санынан аз болады, яғни
бірнеше теңдеулерде базситік айнымалылар болмайды. Осындай жағдайда
базистік айнымалылар қосу үшін жасанды айнымалылар тәсілін қолданады.
Енгізілген айнымалылар СП-дың есебінің шартына қатысы болмайтындықтан,
жасанды айнымалылардың нольге ұмтылуына қол жеткізуіміз керек. Осыны екі
кезеңді симплекс тәсілімен жүргізуге болады:
1 кезең. Симплекс-тәсілінің көмегімен минимизацияланатын, жасанды
айнымалылардың қосындысына тең жасанды мақсаттық функция қарастырылады.
Басқаша айтқанда, жасанды айнымалыларды жою (шығару) іске асырылады. Егер
көмекші есептің минималды мәні нолге тең болса, барлық жасанды айнымалылар
нолге барады және бастапқы есептің мүмкін болатын базистік шешімі алынады.
Ары қарай 2 кезең іске асырылады. Егер көмекші есептің минималды оң болса,
кем дегенде бір жасанды айнымалы оң болады, бұл бастапқы есепке қайшы
келеді де есептеу аяқталады.
2 кезең. Бірінші кезеңде табылған, мүмкін болатын базистік шешім
симплекс-тәсілінің негізінде СП-ң бастапқы есебінің мақсаттық функциясына
қрай жақсартылады. Яғни, 1 кезеңнің оптималды кестесі 2 кезеңнің бастапқы
кестесіне айналады және мақсаттық функция ауысады.
3.4. Симплекс-кесте құру
Бастапқы мүмкін болатын базистік шешімді таңдаймыз. Базистік шешім
деп, базисті емес айнымалылардың xi=0, i=m+1,...,n , нольдік жағдайларында
алынған шешімді айтады. Егер құрамына кіретін базистік айнымалылар теріс
емес, яғни xj = bj >=0, j=1,2,...,m болса базистік шешім мүмкін болатын
базистік шешім деп аталады. Бұд жағдайда мақсаттық функция келесі түрге
келеді: S = cb* xb = c1* b1 + c2* b2+...+cm* bm . Бастапқы симплекс-
тәсілінің кестесін толтырайық:
Кесте 2.3
|cb |xb |c1 |c2 |... |cm |cm+1 |
|2000|4 |5 |6 |1 |0 |0 |
|1770|8 |6 |4 |0 |1 |0 |
|1600|6 |4 |5 |0 |0 |1 |
Базис:
Базистік вектор №1: P4(x4)
Базистік вектор №2: P5(x5)
Базистік вектор №3: P6(x6)
Кеңейтілген мақсаттық функция:
S max = 4*x1+5*x2+6*x3+0*x4+0*x5+0*x6
Бірінші кестені толтырамыз:
Кесте №1
|№ |Bas|CBa|P0|4 |5 |
| |e |se | | | |
|0 |175|180|45|0 |0 |
Мақсаттық функция:
S max = 4*0+5*175+6*180
Нәтижесінде:
S max = 1955;
Есеп шешілді:
4. Қосарланған есеп
4.1. СП-дың қосарланған есебі
4.2. ОҚосарланған есепті құру сұлбасы
4.3. Қосарланған есепті құру мысалы
4.1. СП-ң қосарланған есебі туралы ұғым
СП-ң каноникалық есебі берілсін
[pic] (4.1)
Егер мақсаттық функция f(x) = cx D жиынында максималды мәнге жетсе,
онда оған жоғарғы бағаны қалай құру керек деген сұрақ орынды болады. Егер,
m-өлшемді векторды и арқылы белгілесек, онда
cx = cx+u(-Ax+b) = (c-uA)x+bu
и -ды иА ≥ с болатындай етіп таңдасақ, онда х≥0 келесі теңсіздік
орындалады:
сх≤bи (4.2)
(4.2) жақсартылған бағаны алуға ұмтылу үшін, кейбір мағынада (4.1)
есебімен логикалық қиылысқан және қосарланған есеп деп аталатын жаңа
экстремалды есептің қойылуына келеміз.
Егер СП-ң каноникалық есебі берілсе
[pic] (4.3)
онда СП есебі
[pic] (4.4)
оған қатысты қосарланған деп аталады. Осыған сәйкес, (D, f) есебі (D*,
f*) есебіне қатысты тура (бастапқы) деп аталады.
4.2. Қосарланған есепті құрудың жалпы сұлбасы
Жоғарыдағы есептің анықтамасы сызықты программалаудың жалпы есебінің
жағдайына қолданыла алады.
Егер СП-ң жалпы есебі берілсе
[pic] (4.5)
мұндағы D теңдеулер және теңсіздіктер жүйесімен анықталады
[pic]
онда оған қатысты қосарланған деп СП-ң жалпы есебі аталады
[pic] (4.6)
мұндағы D* теңдеулер және теңсіздіктер жүйесімен анықталады
[pic]
СП-ң тура есебінен қосарланған есебіне көшу:
1. Оптимум типі қарама-қарсынікіне ауысады, яғни максимум минимумға, және
керісінше
2. Мақсаттық функцияның коэффициенттерінің векторы с және шектеулер
бағанасы b орындарын бір-бірімен ауыстырады.
3. Есептің шектеулер матрицасы А транспонируется.
4. Тура есептегі теріс еместік шарты (мысалы, хj≥0 или ui≥0) қойылған
айнымалылардың индекстерінің жиыны қосарланған есепте теңсіздік
формасындағы(аjи≥сj немесе aix≤bi).
5. Тура есептегі теңсіздіктер формасындағы (мысалы, aix≤bi немесе аjи≥сj)
шектеулер номерлерінің жиыны қосарланған есептегі теріс еместік белгісі
қойылған (ui≥0 инемесе хj≥0) айнымалылардың индекстерінің жиынын анықтайды.
Келтірілген анықтамадан маңызды қасиет шығады – қосарлылық қатынасының
симметриялығы, яғни қосарланған есепке қатысты қосарланған есеп бастапқы
тура есеппен сәйкес келеді:
((D*)*, (f*)*)≡(D, f),
Осымен бір-біріне қатысты қосарланған есеп жұбы туралы айту орынды
болады.
Матрицалық формада сызықты программалаудың қосарланған жалпы есебінің
жұбы келесі түрде жазылады:
[pic] (4.7)
және
[pic] (4.8)
4.3. Қосарланған есепті құру мысалы
Қосарланған есепті құру процесін нақыт мысалмен қарстырайық. СП-ң
жалпы есебі берілсін
fmax(x)= 5x1 -2x2 +7x3 +4x4 -3x5
D={xcR5 |
4x1 +x2 -x3 +x4 ≤2,
5x2 +x3 -6x4 +2x5 =4,
2x1 +3x2 +6x3 +x4 -3x5≤5,
x2, x5≥0 }
онда оған келесі есеп қосарланған болады
f*min(u)= 2u1 +4u2 +5u3
D={ucR3 |
4u1 +2u3=5,
u1 +5u2 +3u3≥ -2,
-u1 + u2 +6u3=7,
u1 -6u2 + u3=4,
2u2 -3u3≥ -3,
u1, u3≥0 }
5. Транспорттық есеп
5.1. Есебінің қойылуы матрицалық түрдегі транспорттық есеп және
қасиеттері
5.2. Транспорттық есептегі бастапқы мүмкін жоспарды құру
5.3. Баланстандырылмаған есеп
5.4. Транспорттық есеп үшін потенциалдар тәсілінің алгоритмі
5.5. Транспорттық есепті шешу мысалы
5.1. Есебінің қойылуы матрицалық түрдегі
транспорттық есеп және қасиеттері
Электронды есептеуіш машинаның шығуымен байланысты жаңа ғылыми-
техникалық революция ғылымның жаңа даму бағытын орнатты. Осындай
бағыттардың бірі – операцияны зерттеу ғылымы.
Операция дегеніміз – белгілі мақсатқа жеткізетін және нақты ниетпен
біріктірілген шаралар жиынтығы. Операциялар: басқарылатын және
басқарылмайтын болады.
Операцияны зерттеу дегеніміз – автоматтандырылған басқару жүйесіндегі
басқару есептерін шешуге қолданатын ғылыми тәсіл. Операцияны зерттеу
методологиясы негізгі мына топтарға бөлінеді:
- анықтамалар, кезеңдер, принциптер, есептер;
- операцияны зерттеудің математикалық әдістері. Оған сызықтық
бағдарламалау, транспорттық, дискреттік бағдарламалау, бейсызықтық
бағдарламалау, динамикалық бағдарламалау, ойындар теориясы кіреді;
- АБЖ жобалау кезіндегі операцияларды зерттеудің әдістерін қолдану. Онда
АБЖ-ң алгоритмін қамтамасыз ету, информациямен АБЖ-ны қамтамасыз ету,
техникалық қамтамасыз ету керек.
Сызықтық программалау, практикаға маңызды сызықтық функцияның, сызықтық
теңсіздіктер немесе теңдеулер түріндегі шектеулердің бар болу кезіндегі
максимумын (минимумын) табу, экстремумдық есептерді шешудің классикалық
әдістері қажет болмай қалған есебін зерттейді.
Қазіргі уақытқа дейін сызықтық программалаудың ең қарапайым есептерінің
бірі, кең тарағаны – транспорттық есеп. Яғни, жүктердің жіберу пункттерінен
олардың бару пункттеріне біріктірудің, жүкті тасымалдаудың шығын бағасы
минимиза-цияланатын есеп. Оны шешу үшін сызықтық программалау есептерінің
барлығына ортақ симплекс әдісінен кішірек болатын сызықтық программалаудың
арнайы әдістері қолданылады. Транспорттық есепті шешудің ең танымал
әдістеріне потенциал, солтүстік-батыс, минимал элемент әдістері жатады.
Бұл есеп мақсаттық функцияны минималдандырып
[pic] (5.1), мүмкін болатын жоспарлар жиынында [pic]
(5.2),
бірқатар өнімді өндіруші пункттен тұтынушы пунктіне (||xi,j||mxn)
жеткізу жоспарын анықтаудан тұрады.
Ол баланстық шартты орындауды қажет етеді
[pic] (5.3)
[pic] (5.4)
Транспорттық есеп сызықты программалаудың негізгі есебінің класы болып
табылады және сондықтан сызықты оптималдандырылған есептердің барлық
сапаларына ие.
Егер транспорттық есепті СП-ң есебінің каноникалық формасына
келтірсек, онда есептің матрицасының өлшемі (m+n)mn болады. (5.2) және
(5.3) шектеулеріндегі теңдеулер жүйелерінің матрицаларының m және n тең
рангтері бар. Бірақ, егер, бір жағынан, (5.2) теңдеуді m –ға қосып, басқа
жағынан теңдеуін n –ге қосып, бірдей мән аламыз. Осыдан, (5.2)-(5.3)
теңдеулер жүйесінің біреуі келесісінің сызықты комбинациясы болады.
Сондықтан, транспорттық есептің матрицасының рангі m+n -1 тең, және оның
әлі туындамаған базистік жоспары m+n -1 нольдік емес коэффициенттерден
туруы қажет. Транспорттық есептің шешу процесін 6.1 суретте көрсетілгендей
кестелер түрінде шығаруға болады.
Транспорттық кестенің жолдарына өндіру пункттері (әрбір жолдың соңғы
клеткасына өнім қорының көлемі ai жазылады), ал бағаналарға – тұтыну
пункттері (әрбір бағананың соңғы клеткаларына қажеттіліктер bj ) жазылады.
Кестенің барлық клеткалары (соңғы жолда және оң бағанадағылардан басқалары)
i пункттен j пунктке тасымалдау туралы ақпараттан тұрады: сол жақтағы
жоғары бұрышта өнімнің бірлігінің тасымалдау құны жазылады, оң жақтағы
төменгі бұрышта – берілген пункттерге жеткізілетін жүк көлемінің мәні
жазылады. Нольдік тасымалдаулардан (xi,j=0) тұратын клеткалар бос, нольдік
еместері бос емес (xi,j>0) деп аталады.
|C1,1 |C1,2 |…… |C1,n | |
|X1,1 |X1,2 |…… |X1,n |A1 |
|C2,1 |C2,2 |…… |C2,n | |
|X2,1 |X2,2 |…… |X2,n |A2 |
|…. |…. |…. |…. |…. |
|Cm,1 |Cm,2 |…… |Cm,n | |
|Xm,1 |Xm,2 |…… |Xm,n |Am |
|B1 |B2 |…. |Bn | |
Сурет 5.1
5.2. Транспорттық есептегі бастапқы мүмкін болатын жоспарды құру
Сызықты программалаудың басқа да есептері сияқты транспорттық есепті
шешу мүмкін болатын базистік жоспарды құрудан басталады. Оны анықтаудың ең
оңай тәсілі солтүстік-батыс бұрыш тәсілі. Тәсілдің мәні бірінші, екінші
және басқа да тұтыну пункттері бойынша бірінші, екінші және басқа өндіру
пункттеріндегі барлық қорларды біртіндеп таратудан тұрады. Әрбір тарату
қадамы кезекті өндіру орнындағы қорларды толығымен жұмсау, немесе кезекті
тұтыну пунктіндегі қажеттілікті толығымен өтеу әрекетіне келтіріледі. q
әрбір қадамында ағымдағы таратылмаған қорлардың шамалары аi(q) , ал
қажетіліктері қанағаттандырылмаған қорлардың шамалары bj(q) белгіленеді.
Солтүстік-батыс бұрышы бойынша мүмкін болатын бастапқы жоспарды құру
транспорттық кестенің сол жақ жоғарғы бұрышынан басталады, мұнда аi(0)=
аi, bj(0)= bj деп жорамалдаймыз. І жолында және j бағанасында орналасқан
кезекті тор үшін i өндіріс орнындағы таратылмаған қор және j тұтыну
орнындағы қанағаттандырылмаған қажеттілік қарастырылады. Олардың ішінен
минималдысы таңдалып, хi,j=min{аi(q), bj(q)} пункттері арасындағы
тасымалдау көлемі ретінде тағайындалады: Одан кейін таратылмаған қормен,
қанағаттандырылмаған қажеттілік шамалары келесі шамаға азаяды:
аi(q+1)= аi(q) - xi,j, bj(q+1)= bj(q) - xi,j
Көріп отырғанымыздай, әрбір қадамда келесі теңдіктердің біреуі
орындалады: аi(q+1)= 0 немесе bj(q+1)= 0. Егер біріншісі ақиқат болса, ол i
өндіру пунктінің барлық қоры жұмсалғанын және i+1өндіру пунктіндегі қорды
жұмсауға көшу, яғни бағана бойынша төменгі келесі торға көшу керектігін
білдіреді. Егер bj(q+1) = 0 болса, ол j пунктінің қажеттілігі толығымен
өтелгендігін және одан кейін жол бойынша оң жақта тұрған торға көшу
қажеттігін білдіреді. Жаңа таңдалған тор ағымдағы болып табылады да оған
барлық жоғарыда айтылған операциялар орындалады.
Қорлар мен қажеттіліктер балансының шартына сүйеніп, қадамдардың соңғы
санында біз мүмкін болатын жоспарды алуға болатынын дәлелдеуге болады. Осы
шартқа орай алгоритм қадамдарының саны m+n-1–ден үлкен болмауы тиіс,
сондықтан әрқашан mn-(m+n-1) торлары бос (нольдік) болып қалады. Осыдан
алынған жоспар базистік болып табылады. Бірқатар аралық қадамда ағымдағы
таратылмаған қор ағымдағы қанағаттандырылмаған қажеттілікке тең болуы да
мүмкін (аi(q)=bj(q)). Мұндай жағдайда келесі торға көшу диагональды бағытта
жүреді (ағымдағы өнідіріс және тұтыну орындары бір мезетте ауысады), бұл
жоспардағы бір нольге тең емес (нольдік емес) компоненттің «жоғалғандығын»,
немесе басқаша айтқанда құрылған жоспардың туындағанын білдіреді.
Солтүстік-батыс бұрыш тәсілімен құрылған мүмкін болатын жоспардың
ерекшелігі, мақсаттық функция оптималдыдан алыс мән қабылдайды. Бұл, оның
құрылуы кезінде ci,j мәнінің ескерілмейтіндігінен болады. Осыған орай
практика жүзінде бастапқы жоспарды алу үшін минималды элемент тәсілі
қолданылады. Онда тасымалдау көлемдерін тарату кезінде алдымен, төмен
бағалар жазылған торлар толтырылады.
5.3. Баланстандырылмаған есеп
Егер өндірушілердің тауар бірліктерінің суммасы тұтынушылардың тауар
бірліктерінің суммасына тең болмаса, есеп баланстандырылмаған (ашық),
әйтпесе баланстандырылған (жабық) болады.
Егер, есеп баланстандырылмаған болған жағдайда, жаңа өндіру және
тұтыну пункттерін қосамыз. Жаңа пункттің тауар бірлігінің санын сұраныс
және ұсыныс мәндерін жабумен анықтаймыз. Осы пункт тасымалдау жоспарының
жалпы құнына қатыспауы тиіс, сондықтан осы пункттегі/пункттен тасымалдау
құны нольге тең болуы тиіс.
5.4. Транспорттық есеп үшін потенциалдар тәсілінің алгоритмі
Есептің алгоритмі бірқатар мүмкін болатын базистік жоспарды таңдаудан
басталады (мысалы, алдында солтүстік-батыс бұрыш тәсілі бойынша алынған
алғашқы тасымалдау жоспары). Егер осы жоспар туындамаған болса, онда ол m+n-
1 нольге тең емес базистік тордан тұрады, және оған қарап, әрбір базистік
тор үшін (яғни xi,j > 0 торлар үшін)
vj-ui=ci,j, если xi,j>0, (5.5)
шарты орындалатындай ui и vj потенциалдарын анықтауға болады.
ui айнымалыларын өндіру орындарының потенциалдары деп, ал vj – тұтыну
орнының потенциалдары деп талады.
Ол үшін vj-ui=ci,j тасымалдау жоспарының толтырылған (!) клтекалары
үшін жүйе құру қажет, мұндағы ci,j – i пунктінен j пунктіне тасымалдау
құны.
(6.5) жүйесі m+n-1 теңдеуден және m+n белгісізден тұратындықтан,
потенциалдардың біреуін ойша беруге болады (мысалы, v1 немесе u1 нольге
теңестіріп).
Одан кейін қалған vj және ui белгісіздері анық табылады.
Оптималдылық критериі.
Транспорттық есептің мүмкін болатын жоспары xi,j оптималды болуы үшін,
vj-ui=ci,j, егер xi,j>0,
vj-ui≤ci,j, егер xi,j=0 орындалатын ui, vj потенциалдары табылуы қажет
және жеткілікті.
Жоспардың толтырылмаған (!) торлары үшін құндардың өзгеру
коэффициентін анықтайық: dci,j = vj - ui - ci,j;
Есте сақтаңыз: егер барлық dci,j теріс болса, онда алынған жоспар
оптималды болады. Егер dci,j кем дегенде біреуі оң болса, ары қарай [i,j]
(dci,j>0 болғанда) торы жетекші (тіректі) болады.
Тасымалдаудың жаңа жоспарын анықтау үшін қайта санау циклін құрастыру
қажет.
Қайт санау циклі соңдары толтырылған торларда жастқан, горизонталь
және вертикаль сызықтардан тұратын тұйық үзілген қисық. Сынған сызық
тіректі тордан басталады және аяқталады. Тіректі жоспардағы түйін оң боп
саналады, келесісі теріс болып саналады және ары қарай кезектесе береді.
Барлық теріс торларда мән алынады, ал оң торларда қосылады. Осымен, жаңа
тасымалдау жоспарын алдық.
Цикл барлық dci,j теріс болмайынша, оптималды жоспар алынғанша
жалғаса береді.
5.5. Транспорттық есепті шешу мысалы (1)
Есеп:
Транспорттық есепті шешу қажет:
Өндіру- Тұтынушылар және сұраныстары Өндірушілер қуаты
шілер 1 2 3 4
33 13 27 17
1 14 (27) 28 21 28 27
2 10 (6) 17 (13) 15(1) 24 20
3 14 30 25(26) 21(17) 43
Бастапқы жоспар слотүстік-батыс бұрыш тәсілімен алынды.
Есептің шарты бойынша тасымалдау жоспарының кестесі:
|Өндірушілер және олардың ресурстары |Тұтынушылар және сұраныс |
| |B1 |B2 |B3 |B4 |
| | | | | |
| | | | | |
| | | | | |
| |33 |13 |27 |17 |
| | | | | |
|A1 |14 |28 |21 |28 |
| | | | | |
| | | | | |
| | | | | |
|27 |27 |0 |0 |0 |
| | | | | |
|A2 |10 |17 |15 |24 |
| | | | | |
| | | | | |
| | | | | |
|20 |6 |13 |1 |0 |
| | | | | |
|A3 |14 |30 |25 |21 |
| | | | | |
| | | | | |
| | | | | |
|43 |0 |0 |26 |17 |
| | | | | |
Есептің шешуі.
Алғашқы тасымалдау жоспары.
Есеп баланстандырылған (жабық).
Кесте 1
|Өндірушілер және |Тұтынушылар және сұраныс |
|олардың ресурстары| |
| |B1 |B2 |B3 |B4 |
| | | | | |
| | | | | |
| | | | | |
| |33 |13 |27 |17 |
| | | | | |
|A1 |14 |28 |21 |28 |
| | | | | |
| | | | | |
| | | | | |
|27 |27 |0 |0 |0 |
| | | | | |
|A2 |10 |17 |15 |24 |
| | | | | |
| | | | | |
| | | | | |
|20 |6 |13 |1 |0 |
| | | | | |
|A3 |14 |30 |25 |21 |
| | | | | |
| | | | | |
| | | | | |
|43 |0 |0 |26 |17 |
| | | | | |
Осы жоспар бойынша тасымалдау құны: 1681
Есепті потенциалдар тәсілін қолданып, шешеміз.
1. alfa және betta өндіру және тұтыну пункттерінің потенциалдарын
санаймыз. Ол үшін тасымалдау жоспарының толтырылған торлары үшін жүйе
құрастырамыз: betta[j] - alfa[i] = C[i,j]; мұндағы C – i пунктінен j
пунктіне тасымалдау құны. Есепті alfa[1]=0 деп жорамалдап, шешеміз
2. dC[i,j] =betta[j] - alfa[i] - C[i,j] жоспарының толтырылмаған
торлары үшін құнның өзгеру коэффициентін ( dC[i,j] ) анықтаймыз:
Кесте 2
|Өндірушілер және |Тұтынушылар және сұраныс |alf|
|олардың ресурстары | |a |
| |B1 |B2 |B3 |B4 | |
| | | | | | |
| | | | | | |
| | | | | | |
| |33 |13 |27 |17 | |
| | | | | | |
|A1 |14 |28 |21 |28 |0 |
| | | | | | |
| | | | | | |
| |0 |-7 |-2 |-13 | |
|27 |27 |0 |0 |0 | |
| | | | | | |
|A2 |10 |17 |15 |24 |4 |
| |[-6] | |[+6] | | |
| | | | | | |
| |0 |0 |0 |-13 | |
|20 |6 |13 |1 |0 | |
| | | | | | |
|A3 |14 |30 |25 |21 |-6 |
| |[+6] | |[-6] | | |
| | | | | | |
| |6 |-3 |0 |0 | |
|43 |0 |0 |26 |17 | |
| | | | | | |
|betta |14 |21 |19 |15 | |
Осы жоспар бойынша тасымалдау құны: 1681. alfa және betta
потенциалдарын аламыз. Тасымалдау құнының өзгеру коэффициенттерін
есептейік. Қайта есептеу циклін құрастырайық:
Тіректік тор: (3:1), одан кейін (3:3) [-6], (2:3) [+6], (2:1) [-6].
Жоспардың өзгеру бірліктерінің саны: 6 потенциалдар, коэффициенттер және
қайта санау циклі 2 кестеде көрсетілген. Келесі тасымалдау жоспарын алайық
(3 кесте).
Кесте 3
|Өндірушілер және |Тұтынушылар және сұраныс |alfa |
|олардың ресурстары| | |
| |B1 |B2 |B3 |B4 | |
| | | | | | |
| | | | | | |
| | | | | | |
| |33 |13 |27 |17 | |
| | | | | | |
|A1 |14 |28 |21 |28 |0 |
| |[-20] | |[+20] | | |
| | | | | | |
| |0 |-1 |4 |-7 | |
|27 |27 |0 |0 |0 | |
| | | | | | |
|A2 |10 |17 |15 |24 |10 |
| | | | | | |
| | | | | | |
| |-6 |0 |0 |-13 | |
|20 |0 |13 |7 |0 | |
| | | | | | |
|A3 |14 |30 |25 |21 |0 |
| |[+20] | |[-20] | | |
| | | | | | |
| |0 |-3 |0 |0 | |
|43 |6 |0 |20 |17 | |
| | | | | | |
|betta |14 |27 |25 |21 | |
Осы жоспар бойынша тасымалдау құны: 1645.
alfa және betta потенциалдарын аламыз. Тасымалдау құнының өзгеру
коэффициенттерін есептейік. Қайта есептеу циклін құрастырайық:
Тіректік тор: (1:3), одан кейін (1:1) [-20], (3:1) [+20], (3:3) [-20]
Жоспардың өзгеру бірліктерінің саны: 20 потенциалдар, коэффициенттер және
қайта санау циклі 3 кестеде көрсетілген. Келесі тасымалдау жоспарын алайық
(4 кесте).
Кесте 4
|Өндірушілер және |Тұтынушылар және сұраныс |alfa |
|олардың ресурстары| | |
| |B1 |B2 |B3 |B4 | |
| | | | | | |
| | | | | | |
| | | | | | |
| |33 |13 |27 |17 | |
| | | | | | |
|A1 |14 |28 |21 |28 |0 |
| | | | | | |
| | | | | | |
| |0 |-5 |0 |-7 | |
|27 |7 |0 |20 |0 | |
| | | | | | |
|A2 |10 |17 |15 |24 |6 |
| | | | | | |
| | | | | | |
| |-2 |0 |0 |-9 | |
|20 |0 |13 |7 |0 | |
| | | | | | |
|A3 |14 |30 |25 |21 |0 |
| | | | | | |
| | | | | | |
| |0 |-7 |-4 |0 | |
|43 |26 |0 |0 |17 | |
| | | | | | |
|betta |14 |23 |21 |21 | |
Осы жоспар бойынша тасымалдау құны: 1565.
alfa және betta потенциалдарын аламыз. Тасымалдау құнының өзгеру
коэффициенттерін есептейік.
Потенциалдар және коэффициенттер 4 кестеде көрсетілген. Алынған жоспар
оптималды, өйткені құнның барлық өзгеру крэффициенттері (dC[i,j]) теріс
немесе нольге тең.
3 Практикалық сабақтар
Практикалық сабақтарға тапсырмалар оқытушының нұсқауымен математикалық
программалау тәсілдері жүргізілетін жоғарғы оқу орындарына арналған
оқулықтың (Акулич И.Л. Математическое программирование в примерах и
задачах: учебное пособие для вузов. – М.: Высшая шк., 1986 – 319 с., ил.)
осы пәнге сәйкес тақырыптарына орай арнайы тапсырмаларынан студенттерге
вариант бойынша беріледі.
Практикалық жұмыс тақырыптары:
№1 Сызықты программалаудың жалпы және негізгі есептері
№2 Сызықты программалау есептерінің геометриялық тұжырымдары
№3 Сызықты программалау есептерінің шешімін табу. Симплекс тәсілі
№4 Жасанды базис тәсілі
№5 Қосарланған симплекс тәсілі
№6 Транспорттық есеп. Есептің тіректі жоспарын анықтау. Тәсілдері
№7 Транспорттық есеп. Есептің тіректі жоспарын анықтау. Солтүстік-батыс
тәсілі
№8 Транспорттық есеп. Есептің тіректі жоспарын анықтау. Минималды элемент
тәсілі
№9 Транспорттық есеп. Есептің тіректі жоспарын анықтау. Фогель
аппроксимациясы тәсілі
№10 Транспорттық есеп. Есептің оптималды жоспарын анықтау. Потенциалдар
тәсілдері
№11 Транспорттық есеп. Есептің оптималды жоспарын анықтау. Потенциалдар
тәсілдері
№12 Транспорттық есеп. Есептің оптималды жоспарын анықтау. Дифференциалды
рента тәсілі
№13 Сызықты программалаудың нақтысанды есептері. Блоктық программалау
есептері. Ойын теориялары есептері
№14 Экономикалық және геометриялық интерпретация. Лагранждың көбейткіштер
тәсілі. Градиенттік тәсіл
№15 Динамикалық программалау есептерінің жалпы сипаттамасы, экономикалық
және геометриялық интерпретациясы.
4 Студенттің өздік жұмысы
1. Автоматты жүйелер және жүйелік техникалар (мәселелері, маңыздылығы,
әдістері) теориясы.
2. Операцияларды зерттеу жабдықтары, операциялар модельдері және
модельдер түрлері.
3. Операциялардың детерминирленген модельдері.
4. Жалпы түсініктер. Сызықты программалау (СП) есептерінің мысалдары.
5. Сызықты программалаудың жалпы және негізгі есептері. СП негізгі
есебінің қасиеттері.
6. СП есептерінің шешімін анықтау.
7. СП-ң қосарланған есебі.
8. Сызықты программалаудың арнайы есептері. Транспорттық есеп. Оның
тіректік жоспарын анықтаудың негізгі тәсілдері.
9. Транспорттық есептің оптималды жоспарын анықтау тәсілдері.
10. Сызықты программалаудың нақтысанды есептері
11. Блоктық программалау есептері
12. Ойын теориялары есептері
13. Экономикалық және геометриялық интерпретация
14. Лагранждың көбейткіштер тәсілі. Градиенттік тәсіл
15. Динамикалық программалау есептерінің жалпы сипаттамасы, экономикалық
және геометриялық интерпретациясы.
16. Есептердің шешімін динамикалық программалау көмегімен шешу
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz