Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1.Компакт жиындар
Тиімділік есебін қарастырайық:
(1)
нүктесін және шамасын табу қажет. Егер онда екендігін байқаймыз.
Компакт жиындар. Мәселен қандай да бір тізбек болсын.Онда еске сала кететініміз: а) егер орындалатын тізбекшесі табылатын болса, онда нүктесі тізбегінің шекті нүктесі деп аталады; б) барлық үшін болатын саны табылса, онда тізбегін шектелген дейміз; в) егер барлық үшін орындалатын саны табылса, онда жиыны шектелген делінеді; г) егер нүктесінің кез келгек - аймағы (O(V, ) жиыны) U жиынының - дан өзге нүктелерін қамтыса, онда нүктесі U жиынының шекті нүктесі деп аталады; д) U жиынының кез келген шекті нүктесі үшін болатын тізбегі табылады; е) егер жиыны өзінің барлық шекті нүктелерін қамтыса, онда бұл жиын тұйық жиын деп аталады.
1 анықтама. Егер кез келген тізбегі ең болмағанда бір шекті нұктесін қамтыса және , онда жиыны компакт жиын деп аталады.
Бұл анықтама математикалық анализ курсындағы "кез келген шектелген, әрі тұйық жиын - компакт жиын" деген тұжырыммен мағыналас екендігін көреміз. Шынында да, Больцано-Вейерштрасс теоремасына сай кез келген шектелген тізбектің ең болмағанда бір шекті нүктесі бар (U жиыны шектелген), ал тиістілігінен U жиынының тұйықтығы шығады.
2.Вейерштрастың 1-теоремасы
1 теорема. функциясы компакт жиынында анықталған, ақырлы және төменнен жартылай үзіліссіз дейік. Онда
жиыны бос емес, компакт жиын және кез келген минимумдаушы тізбек жиынына жинақталады.
Дәлелі: кез келген минимумдаушы тізбек, яғни сандық тізбектің шегі . Мұндай минимумдаушы тізбек әрқашанда бар болатынын байқаймыз. - минимумдаушы тізбектің кез келген шекті нүктесі дейік. Демек, болатын тізбекшесі табылады. U жиыны компакт, сондықтан минимумдаушы тізбектің барлық шекті нүктелері U жиынында жатады. Төменгі мән және функциясының төменнен жартылай үзіліссіздігі анықтамасынан келесі теңсіздіктер шығады:
(2)
тізбегі шамасына жинақталатындықтан, оның кез келген тізбекшесі де шамасына жинақталады. Соңғы (2) теңсіздігінен алатынымыз: Демек., және . Осы тұжырым минимумдаушы тізбектің кез келген шекті нүктесі үшін әділ болғандықтан U - дағы кез келген минимумдаушы тізбек жиынына жинақталады. жиыны компакт екендігін көрсетейік.
- жиынынан алынған кез келген тізбек дейік. тиістілігінен шығатыны: . Ендеше, жиыны компакт болғандықтан нүктесіне жинақталатын тізбекшесі табылады. болғандықтан
Демек, минимумдаушы тізбек. Онда жоғарыдағы дәлелдеуден көретініміз: шекті нүкте. Сонымен, жиынының тұйықтығы дәлелденді. жиынының шектелгендігі тиістілігінен шығады. жиыныны компакт екендігі дәлелденді. Теорема дәлелденді.
Қолданбалы есептердің көбінде жиыны шектелмеген. Мұндай жағдайларда келесі теоремалардың көмегі тиеді.
3.Тиімділік есебінің қойылымы
4.Сызықтық программалау . 3-лемма.
Айталық . Егер ерекшеленбеген есептегі ұйғарымды векторының дәл m оң координаты болса, онда х - Х жиынындағы шеткі нүкте.
5.Сызықтық программалау. 4-лемма
Кез келген нүктесін жиынындағы шеткі нүктелердің дөңес сызықты комбинациясы ретінде өрнектеуге болады, яғни - жиынындағы шеткі нүктелер.
6.Сызықтық программалаудың негізгі есебі. Операциядарды зерттеудің классификациясына сай, егер ұйғарымды шешімдер жиыны – дөңес көпжақ, ал тиімділік критерийі жиынында анықталған сызықтық скаляр мақсат функциясы болса, онда біз сызықтық программалау есебін қарастырамыз. Бұл есептердің теориясы сызықтық программалау пәнін құрайды. Сызықтық программалау туралы сөз қозғағанда, біз операцияларды зерттеу есебінің өзі туралы емес, оның көрсетілген арнайы шарттарды қанағаттандыратын математикалық моделі туралы айтамыз. Назар аударарлық мәселе – операцияларды зерттеудің бір ғана есебін шығару үшін әр түрлі математикалық моделдер қолданылуы мүмкін.Сызықтық программалаудың жалпы есебі келесі түрде жазылады:
Мұндағы – берілген сандық параметрлер, ал жиындары жұптасып қиылыспайды және . Бұл есептегі басқарылатын айнымалылар немесе моделдің
айнымалылары деп аталатын белгісізі векторының кординаттарын білдіреді. Егер сызықтық программалау есебі
(2.5)
түрінде болса, онда сызықтық программалау есебі негізгі (стандарт) формада берілген дейміз.
Мұндағы
(2,6)
шектеуі ұйғарымды шешімдер жиынын анықтайды да, базистік шектеулерді көрсетеді. Яғни бұл жүйедегі теңдеулер саны оның матрицасының рангіне тең. Сонымен, (2.5) өрнегінде . Ал кезінде (2.6) жүйесі жалғыз шешімге ие және жиынының элементтерінің саны бірден аспайтындықтан, жалпы жағдайда
(2.7) деп қабылдаймыз.
Енді (2.1) мен (2.5) өрнектерін салыстыра отырып, егер моделдің айнымалаларының шектеулерінен басқа теңсіздік түріндегі барлық шектеулерге қосымша теріс емес айнымалылыр енгізу жолымен теңдік түріндегі шектеулер түрінде жаза алсақ, кез келген сызықтық программалау есебі канондық түрде өрнектелетінін көреміз.Теңсіздік түріндегі шектеулерді жаңа теріс емес айнымалылар енгізу арқылы теңдік түріндегі шектеулерге әкеле аламыз. Егер теңсіздік түріндегі шектеулер
,
түрінде болса, онда қосымша айнымалылыары арқылы оны келесі түрде жазамыз
.
7.Вейерштрастың 2-теоремасы.
функциясы бос емес тұйық жиынында анықталған, ақырлы және төменнен жартылай үзіліссіз болсын. Қандай да бір берілген нүктесі үшін Лебег жиыны шектелген дейік. Ендеше, , жиыны бос емес, компакт және кез келген минимумдаушы тізбек жиынына жинақталады.
Дәлелі. Лемманың барлық шарты орындалғандықтан, жиыны тұйық жиынының шектелгендігінен және тұйықтығынан оның компакттығы шығады. мұндағы әрі функциясы жиынында төменгі мәніне жетпейді. Бұдан соң жиынын компакт жиынына алмастырып, 1 теореманың дәлелденуі қайталанады. Теорема дәлелденді.
8-19.Сызықтық емес программалаудағы тиімділіктің қажетті шарты.
9.Сызықтық программалау. 6-лемма.
10.Тиімділік критерийі. жағдайындағы дөңес программалау есебі (4) - ке оралайық.
Теорема. Егер - еркін функция, U - дөңес жиын, Ø болса, онда кез келген , нүктесінде
(5)
теңсіздігі орындалады. Егер дөңес функция, U - дөңес жиын, Ø, онда кез келген нүктесінде (5) шарттың орындалуы қажетті және жеткілікті.
Дәлелі. Қажеттілігі. дейік. Кез келген функциясы үшін (5) өрнек орындалатынын көрсетейік, мұндағы U - дөңес жиын. (дербес жағдайда - U - дағы дөңес функция)
Мәселен, - еркін нүкте және . Онда мұндағы . Осыдан
әрі кезінде . Теңдіктің екі жағында - ға бөліп, кезіндегі шекке көшсек, (5) өрнекті аламыз. Қажеттілік дәлелденді.
Жеткіліктілігі. дөңес функция, U - дөңес жиын, Ø және (5) өрнек орындалсын. екенін көрсетейік. Мәселен, - еркін нүкте. Онда 2 - теоремаға сай («Тегіс функциялардың тиімділігінің баламасы» бөлімін қараңыз) алатынымыз барлық кезінде . Осыдан шығатыны: . Демек, . Теорема дәлелденді.
Салдар. Егер , U - дөңес жиын, Ø және , онда теңдігінің орындалуы қажет.
Шынында да, егер , онда барлық кезінде болатын кез келген үшін саны табылады. Сонда (5) - тен барлық кезінде де , . Осыдан алатынымыз: .
Осы (5) формула сызықсыз программалау есебі тиімділігінің қажетті шарты ретінде және дөңес программалау есебі тиімділігінің қажетті де жеткілікті шарты ретінде келесі лекцияларда қолданыс табады.
11.Жатық функциялар дөңестігінің критерийлері. Теорема 1
12.Лагранж функциясы. Негізгі теорема.
L (3)
функциясын (1), (2) есебінің Лагранж функциясы деп атайды.
1-анықтама. Егер L L L,. (4)
шарты орындалса, онда , яғни жұбы (3) -Лагранж функциясының қайқы нүктесі деп аталады. нүктесінде L функциясы жиынында минимумға жететінді-гін байқаймыз. Ал нүктесінде жиынындағы L функциясының максимумын аламыз. Лагранж функциясының анықталу облысы жиыны болып табылады.
Негізгі теорема. Егер жұбы (3) - Лагранж функциясының қайқы күктесі болса, онда векторы (1), (2) есебінің шешімі болады. Яғни .
Дәлелі. жұбы үшін (5), (6) шарттарының орындалаты-ны негізгі леммадан көрініп. Ендеше. Енді (5) теңсіздік былай жазылады:
. (9)
болғандықтан (9) теңсіздік дербес жағдайда барлық орындалады, яғни . (10)
Енді 2-шарттан аңғаратынымыз: егер онда және : демек кез келген үшін . Ескеретініміз , мұндағы . Ендеше (10)-нан шығатыны . Бұл нүктесінде функциясы U жиынындағы глобәлдік немесе абсолют минимумға жететіндігің білдіреді. Теорема дәлелденді.
13.Жиынның салыстырмалы ішкі нүктелері.
14.Жиынның шекаралық нүктелері
15.Дөңес функциялар. 1- теорема.
1 анықтама. - -дегі дөңес жиынында анықталған функция болып, кез келген нүктелері үшін барлық кезінде (1)
теңсіздігі орындалса, онда функциясы жиынындағы дөңес функция деп аталады.Егер (1) өрнектегі теңдік тек және кезінде ғана мүмкін болса, онда функциясы дөңес жиынындағы қатаң дөңес функция болғаны. Егер дөңес жиынында функциясы дөңес (қатаң дөңес) болса, онда – функциясы ойыс (қатаң ойыс) болғаны.
2 анықтама. дөңес жиынында анықталған функция болсын.
Егер кез келеген нүктелері үшін барлық кезінде
(2)
теңсіздігі орындалатын саны табылса, онда функциясы жиынында әлді дөңес функция делінеді.
1 теорема. Дөңес жиынында функциясы дөңес болуының қажетті де жеткілікті шарты:(4) Дәлелі. Кажеттілігі. дөңес дейік. Сонда (1) теңсіздігінен алатынымыз:
Осыдан, ақырлы өсімшелер формуласы негізінде жазатынымыз:
Бұл теңсіздіктің екі жағын да санға бөліп, кезде шекке көшіп, екендігін ескерсек (4) өрнегі шығады.Қажеттілік дәлелденді.
Жеткіліктілігі . Дөңес жиынындағы функциясы үшін (4) өрнегі орындалсын. Онда - да функциясының дөңестігін көрсетейік. дөңес болғандықтан: .
Ендеше (4) теңсіздігінен. Бірінші теңсіздікті - ға, ал екінші теңсіздікті санына көбейтіп, оларды қосамыз. Нәтижесінде алатынымыз: . Бұдан функциясының жиынында дөңестігі шығады. Теорема дәлелденді.
16.Дөңес программалау есебін шығару алгоритмі. (23)
есебі үшін екендігіне көз жеткізу керек. Ол үшін 1-3 тh (Вейерштрасс тh) қолданамыз.Дөңес программалау есебінің түріне байланысты Лагранж фун қайқы нүктесінің болатындығына кепілдік беретін шарттардың орындалуын тексереміз .Мысалы, егер есеп (1)-(2 түрінде болса, онда регуляр екендігін , егер есеп (8)-(9) түрінде болса, онда екендігін, ал (23)-(24) есебі үшін орындалатын нүктесі табылатындығын көрсетеміз. Анықталу аймағы Лагранж құрамыз, мұн. .
(26) шартынан (негізгі лемма) Лагранж фун қайқы нүктесін табамыз. а) 1-ші шарттан көретініміз функциясы жиынындағы минимумына нүктесінде жетеді. функциялары дөңес жиынындағы дөңес функциялар, ендеше -да дөңес. Егер , онда тиімділік баламасы бойынша және глобәлдік минимум туралы теоремадан (26)-дағы 1-ші шартты мынаған алмастырамыз: ; мұндағы . Енді (26) (27) түрінде жазылады. б) Егер сыртында , онда тиімділік баламасына сай (27) шартын келесі түрде өрнектейміз: (28) Соңғы (28) шарты алгебралық теңдеулер жүйесін білдіреді, белгісіздер саны: . Байқайтынымыз: егер Лагранж фун қайқы нүктесі бар болса, онда (28) - теңдеулер жүйесінің шешімі бар болғаны, әрі орындалу керек. (28)-шарт жағдайында қолданылады, дегенмен бұл жағдайда екендігіне көз жеткізу керек. Мәселен жұбы анықталады дейік. Онда нүктесі мен шамасы тиімділік есебінің шешімі
17.Кун-Таккер теорамасы қандай есепте қолданылады? Қандай шарттар орындалғанда Лагранж функциясы қайқы нүктеге ие болатындығын тағайындайтын теоремалар Кун-Таккер теоремалары деп аталады. Кейде бастапқы есептің шешімі бар болып (яғни , ), ал осы есеп үшін Лагранж функциясының қайқы нүктесі жоқ болуы мүмкін.
1-жағдай. Дөңес программалаудың келесі есебін қарастырайық
(1) (2) мұндағы - жиынында анықталған дөңес функциялар.
1 анықтама. Егер болатын нүктесі табылса, онда шектеуі жиынында регуляр делінеді. Егер барлық (2) шартындағы шарттары жиынында регуляр болса,онда U регуляр жиын деп аталады. (3)
орындалатын нүктесі бар болсын. Осы (3) шарты Слейтер шарты деп аталады.
1 теорема. Егер - дөңес жиынында анықталған функциялар, U жиыны регуляр және , онда әрбір нүктесі үшін жұбы Лагранж функциясының:
L қайқы нүктесін құратын Лагранж көбейткіштері табылуы қажетті. Теорема шартынан байқайтынымыз: дөңес программалау есебі (1), (2) үшін егер U жиыны регуляр болса ( шарты орындалғанда) Лагранж функциясы қайқы нүктеге ие болады екен.
II жағдай. Енді дөңес программалаудың келесі есебін қарастырайық: (8)
(9)
мұндағы - жиынша, жиын, -дөңес жиынында анықталған дөңес функция, берілген векторлар, берілген сандар. Осы (8), (9) есебі үшін Лагранж функциясын жазайы L
(10)
Егер функция сызықты болса, онда (8)-(9) есебі сызықты программалаудың жалпы есебі деп аталады. Мәселен делік. Жоғарыдағы (8)-(9) есебі үшін жазылған Лагранж функциясы (10) дөңес U жиынына қосымша ешқандай шарт қойылмаса да қайқы нүктеге ие болады екен.
2 теорема. Егер дөңес жиынындағы дөңес функция, және (8) - (9) есебі үшін болса, онда әрбір нүктесі үшін жұбы (10) - Лагранж функциясының жиынындағы қайқы нүктесін құратын Лагранж көбейткіштері табылуы қажет.
3-жағдай. Дөңес программалаудың неғүрлым жалпы есебін қарастырайық
(23) (24)
мұндағы дөңес жиынында анықталған дөңес функциялар, - берілген векторлар, берілген сандар. Осы (34)-(35) есебі үшін Лагранж функциясы:
(25)
3 теорема. Егер дөңес жиынындағы анықталған дөңес функциялар; (34)-(35) есебі үшін және орындалатын нүктесі табылса, онда әрбір нүктесі үшін жұбы жиынында (36)-Лагранж функциясының қайқы нүктесін құратын Лагранж көбейткіштері табылуы қажетті.
18.Операцияларды зерттеудің кезеңдері Операцияларды зерттеу – ұйымдастыру жүйелеріндегі тиімді басқарудың әдістерін жасап, оны іске асырумен айналысатын ғылым. Операцияларды зерттеу-дің мақсаты – ұйымдастыру жүйелерін басқаруда қабылданатын шешімдерді сандық түрде негіздеу.Белгілі бір мақсатқа жетуге бағышталған әрекеттердің мен шаралардың жиынтығын операция деп түсінеміз. «Операцияларды зерттеу» өзіндік зерттеу нысаны мен әдіснамасы бар кешенді ғылыми зерттеулердің қатарына жатады. Мәселені шешуге сан қилы міндеттерді (экономикалық, физикалық, биологиялық және басқа) позицияда талдайтын кешенді ғылыми-зерттеуші ұжымдар қатысады. Операциялық топтар құрамы түрлі білім салаларының мамандарынан: математиктерден, инженерлер-ден, экономистерден, әлеуметтанушылардан, психологтардан т.с.с. тұрады. Осындай топтарды құру мақсаты – проблеманы шешуге ықпалды барлық факторлар жиынын кешенді түрде зерттеу және әр алуан ғылымның идеялары мен әдістерін қолдану. ОЗ әдіснамасы-ның екінші ерекшелігі – моделдерді және есептеу техникасын қолдануы. Операциялық моделдердің құраушылары: а) жүйенің қызмет ету сапасын сипаттайтын критерий: мұндағы – басқарылатын айнымалылар, – басқарылмайтын айнымалылар;
б) басқарылатын айнымалылардың өзгеру межелерін анықтайтын теңдеулер мен теңдіктер түріндегі шектеулер.Есептің мағанасына қарай математикалық анализдің немесе экстремалдік есептерді шешудің әдістерін қолданып, берілген шарттар мен шектеулердегі сапа критерийін максимумдайтын немесе минимумдайтын тиімді шешімді табамыз. Зерттелінетін моделіміз нақты жүйені мейлінше дәл бейнелегенде ғана шешім нәтижесінде алынған айнымалылардың тиімді мәні жүйенің қызмет ету сапасы жақсаратындықтан, моделдің нақтылыққа сәйкестігін тексеріп, алынған шешімді бағалау қажет.
Ақырында, ОЗ мақсаты нақты жүйелердің қызметінің сапасын жақсартуды көздейтіндіктен, зерттеу нәтижелері қолданысқа енуі тиіс.Сонымен, кез келген операцияны зерттеу келесі кезеңдерден тұрады:1.мәселенің қойылуы; 2.моделді құру; 3.шешім алу; 4.моделді тексеру және шешімді бағалау;5.нәтижелерді қолданысқа енгізу.
20.Сызықтық программалаудың канондық есебін қай әдіспен шығарамыз?Канондық түрдегі сызықты программалау есебін қарастырайық: , (2.12)мұндағы - берілген векторлар, А- берілген ретті матрица. матрицасын
түрінде жазуға болады. Мұндағы векторы шарттар векторлары деп, ал - шектеулер векторлары деп аталады. Ендеше теңдеуі түрінде жазылады. Мына , жиындары аффиндік жиындар, яғни дөңес жиындар.
1 анықтама. Егер нүктесі
түрінде өрнектелмесе, онда ол шеткі (немесе бұрыштық) нүкте деп аталады.Осы анықтамадан шеткі нүкте жиынындағы кесінділердің ешқайсысының ішкі нүктесі болмайтындығын көреміз. 1 Лемма. Шеткі нүктенің оң координаттарының саны m - нен аспайды. 2 Лемма. Шеткі нүктенің оң координаттарына сай шарттар векторлары сызықты тәуелсіз.
2-анықтама. Егер ұйғарымды векторлардың оң координаттарының саны А матрицасының рангынан кем болмаса (яғни , тендеуіндегі нөлден ерекше қосылғыштар А матрицасының рангынан кем болмаса), онда (2.12) -түрдегі есеп сызықты программалаудың канондық түрдегі ерекшеленбеген есебі деп аталады.
3-лемма. Айталық . Егер ерекшеленбеген есептегі ұйғарымды векторының дәл m оң координаты болса, онда х - Х жиынындағы шеткі нүкте.
4-лемма. Кез келген нүктесін жиынындағы шеткі нүктелердің дөңес сызықты комбинациясы ретінде өрнектеуге болады, яғни - жиынындағы шеткі нүктелер.
21.Моделдеу принциптері
Моделдің сапасы операциялық топтардың творчестволық қабілетіне аса тәуелді. Сондықтан, нақты ОЗ есептерінің моделдерін құру шеберлігіне бүкіл үміткерлерді үйрететін нұсқау беру мүмкін емес. Моделдер құрудан жинақталған тәжірибелерге сүйеніп, ой өрісті кеңейтетін және творчестволық ізденіс бағытын тура таңдауға септігі тиетін кебір принциптерді атап кетелік:
1) Жүйе қызметіне тікелей талдау жасау. Бұл жүйе құрылымы мейлінше қарапайым кезінде, жүйені тексеріп барып, оны бейнелей алатын жүйе қызметінің заңдылықтары белгілі болғанда қолданылады.
2) Аналогты пайдалану. Мұны жүйенің құрылымы мейлінше айқын болғанымен, оны математикалық бейнелеу тәсілі ұғынықсыз жағдайда, ал кейде қарастырылып отырған жүйенің өзінен құрылымы анағұрлым қарапайым аналогиялық жүйемен ұқсастығын іске асыруға болатын ахуалдарда пайдаланамыз.
3) Мәліметтерді талдау («жұмбақ жәшік» принципі). Жүйе құрылымы айқын болмағанда оны жүйенің қызметін сипаттайтын мәліметтерге сүйеніп бейнелеуге тырысамыз. Жүйе құрылымы туралы қалыптасқан гипотезаны негізінде осы гипотеза құрылған мәліметтермен сай келмейтін басқа эксперименттік мәліметтерді пайдаланып тексеру қажет. Физика, химия, астрономия және басқа ғылым салаларындағы көптеген іргелі заңдар әуелі эксперименттік мәліметтер мен бақылау нәтижелеріне талдау жасау арқасында дүниеге келгені мәлім.
4) Жүйеге эксперимент жасау. Маңызды айнымалыларды айыруға, жекеленген айнымалылардың жүйе жұмысының сипатына ыпалын анықтауға мәліметтерге талдау жасау мүмкіндік бермегенде натура-эксперимент жүргізу қажеттігі шығады.
5) «Жасанды нақтылықты» қолдану. Жүйені сипаттаушы мәліметтер жоқ, немесе оларды алу мүмкін емес кезде, ал жүйеге эксперимент жасау ұзақ уақытты қалайтын немесе қымбатқа түсетін, кейде мүлде мүмкін емес, жағдайларда ең қиын ахуалға тап боламыз.
22.Оңтайлы ұстаным критерийлері
Анықталмағандық шарттарындағы оңтайлы ұстанымның төмендегідей критерийлері әдетте ШҚК өрелі ойлы қарсыласпен тайталаспағанда, яғни табиғи (пассив) анықталмағандықты есептерде қолданылады. Көңілге қонымды критерий құру үшін актив анықталмағандықты, мысалы мүдделері ШҚК мүддесіне сай келмейтін қарсыластың ұстанымын ескеруді қажет ететін ахуалдарда, арнаулы тәсіл керек. Мұндай даулы ахуалдарда ұстанымның тиімді стратегияларын қабылдау мәселелеріне ойындар теориясында тоқталамыз.
1) Лаплас критерийі. Бұл критерий жеткіліксіз негіздеу принципіне сүйенеді. нәтижелерін алу ықтималдығы белгісіз, ал бұл ықтималдықтар әр түрлі екендігін тағайындайтын ақпараттар жоқ ендеше, осы ықтималдықтар өзара тең, яғни стратегиясын таңдағанда барлық кезінде деп ұйғаруға болады. Сонымен, бастапқы есеп тәуекелмен шешім қабылдау есебіне (ықтималдықты есепке) келеді:
2) Вальд критерийі (максимин критерийі, немесе пессимист критерийі). Осы критериге сай ШҚК әр стратегия үшін пайдалылық мәні минимум деген писсимистік ұйғарымнан өз стратегиясын таңдайды. Бұл кездегі ШҚК оңтайлы қалпы келесі максимин есебінен анықталады:
3) Гурвиц (жалпыланған максимин) критерийі. Бұл жағдайда мақсат функциясына оптимизм көрсеткіші ретінде қарастыруға болатын параметрі енгізіледі:
.
Сонымен, ең кіші пайдалылық алуды ұйғаратын Вальд критерийінен мұндағы айырмашылық: ең кіші пайдалылық пен ең үлкен пайдалылық арасында жататын пайдалылыққа жету үміті оянады. Егер, , онда алдыңғы жағдайға (пессимист критерийіне) соқтырады, ал кезінде (нағыз оптимизмді сипаттайтын) максимакстік критерийге айналады. Аралық мән салиқалы оптимизмге сай келеді.
4) Сэвидж критериі (минимакс шығынды критерий). Пайдалылық функциясы алдын ала шығын функциясына (өкініш функциясына) түрлендіріледі, мұндағы . Сонымен, шығын матрицасының элементі ШҚК нәтиже қандай болатынын білгендегі пайдалылық пен әр ахуалдағы шын пайдалылықтардың айырмасын (яғни, ШҚК мүмкін «өкінішін») білдіреді. Одан әрі оңтайлы ұстанымды анықтау үшін келесі минимакс есебі қойылады:
23.Пайдалылықты өлшеу әдістері
Кез келген (ықтималдықты, детерминді және анықталмағандықты) типтегі ОЗ есептерінде мақсат функциясын таңдауда түрлі стратегияларды қолданғанда алынатын нәтижелер пайдалылығының бағасын білу ләзім. Бұл жерде біз нәтижелерді сандық бағалаудың түрлі әдістері туралы сөз қозғағанымызбен, олар обькетілерді, оқиғаларды, күйлерді және басқаларды Фон Нейман – Моргенштерн әдісі. Бұл әдіс бірге тең ықтималдықпен алынған нәтижесінің пайдалылығы болса, онда осы нәтижені ықтималдығымен жүзеге асырғанда оның пайдалылығы деген ұйғарымғы негізделген. Әуелі нәтижелерді басымдығының кему ретіне қарай реттейміз: . Одан соң нәтижелерін жұптастыра қарастырып, ықтималдығымен алынған нәтижесі бірге тең ықтималдықпен алынған нәтижесіне мәндес болатын санын анықтау қажет. нәтижесінің пайдалылығы 1-ге тең деп алынғандықтан нәтижесінің ықтималдығы , деп саналады, сондағы нәтиже пайдалылығы: (1.3)
Бұдан әрі барлық бұрын қарастырылмаған мүмкін жұптарды , салыстыра отырып, алынған пайдалылықтар бағаларының сенімділігін тексереміз. Мұнда да ықтималдығымен алынған нәтижесінің бірге тең ықтималдықпен алынған нәтижесіне эквивалент саны анықталады. Осы кезде мына қатынас орындалуы қажет . (1.4)
Кері жағдайда (1.3)-тегі пайдалылықтарының әуелгі бағаларына (1.4) өрнегі орындалатындай етіп түзету жасау керек. Черчмен – Акоф әдісі. Бұл келесі ұйғарымдарға негізделеді:
а) Әрбір нәтижесіне оның салыстырмалы пайдалылығының өлшемі – қайбір санын белгілі бір сәйкестікте қоямыз.
б) Егер, онда ; егер , онда .
в) Біріккен нәтиже пайдалылығының аддитивтілігі :
Үшінші ұйғарымнан шығатын салдарлар:
в') ,
в'') (нәтиже алу реті жалпы пайдалылықты өзгертпейді),
в''') .
Жоғарыдағы аталған ұйғарымдар Черчмен – Акоф әдісінің қолданылу аясын шектегенмен, практикада ол кең қолданылады.
Әуелі басымдылығының кемуіне қарай нәтижелерді қатарластырамыз: . нәтижесінің (бұл нәтиже салыстыру базисі болып табылады) пайдалылығы бірге тең деп қабылданады да қалған нәтижелерге олардың салыстырмалы пайдалылықтары телінеді
. (1.5)
Сосын, жұптап салыстыру есебін шеше отырып, алдын ала берілген бағалардың сенімділігіне тексеру жасаймыз.
Кестеде келтірілген салыстыру нұсқалары бірінші бағаннан бастап нәтижесінің басымдылығы өзімен салыстырылатын біріккен нәтиже басымдылығынан төмен яғни болғанша қарастырыла береді. Кері қатынас орындалса, немесе осы бағандағы соңғы өрнек қарастырылса, онда келесі бағанға көшеміз. Екінші бағандағы салыстыру операциялары дәл осылай болғанша жүзеге асады т.с.с. Бұл кезде барлық қарастырылған
түріндегі қатынастардың нәтижелерінің пайдалылы үшін тиісті теңсіздіктер орындалуы қажет:
(1.6)
24.Көп критерийлі есептер
Бас критерий әдісі. Мәселен, қарастырылатын критерийлерінің арасындағы өте маңызды (бастысы) болсын. Онда қалған критерийлердің мәндері қайбір берілген сандарынан кем болмауы қажет деген ұйғарымда осы критерийді максимумдау есебін қисындауға болады:
Критерийлер үйірткісі. Дербес критерийлерінің орнына аддитивті үйірткі жолымен алынатын жалпы жалғыз критерийді қарастыру ұсынылады: (1.6)
мұндағы салмақ коэффициенттері тиісті критерийдің маңыздылық дәрежесін сипаттайды .
Жалпыланған критерий мультипликативті үйірткі жолымен де қисындалуы мүмкін: (1.7)
Мультипликативті үйірткі (1.9) критерийлерді өлшеуде логарфмидік масштабты қолдану арқылы (1.8) аддитивті үйірткіге келетіндігін есте сақтаңыз.
Нормативті көрсеткіштер. Жоспарлау мен жобалаудың есептерінде қайбір нормативтер жүйесі өте жиі беріледі де, зерттелетін жүйенің параметрлері шектеулерін қанағаттандыруы талап етіледі. Мұндайда мақсат функциясы ретінде шарттарындағы мына өрнекті алған жөн (ең нашар көрсеткішті максимумдау)
«Идеалдар» әдісі. Мәселен, біз әрбір үшін бір критерийлі есептер жүйесін шештік те максимум мәндерін таптық дейік. Критерийлер кеңістігіндегі нүктесін «идеал» деп атаймыз. Енді мақсат ретінде «идеалдан» ауытқуды минимумдау есебін қойуға болады:
.
Біртіндеп көну әдісі. Әуелі критерийлерді маңыздылығының кемуіне қарай реттеп аламыз: .
Одан соң есебін шешіп, анағұрлым маңызды критерийдің максимум мәнін табамыз. Ымыра әдісі (Â.Парето). Жоғарыдағы көп критерийлі есептерді шешу тәсілдері жалпыланған бір критерийді таңдауға соқтырады, яғни бастапқы есеп басқа есеппен алмастырылады. Ал мұндай алмастыру өзін-өзі қаншалықты ақтайтындығы айтылмайды. Көп критерийлі есептерді талдауға өзге тұрғыдан келсек: қайбір нұсқалар бойынша басқа критерийлерге бәсекелесе алмайтын критерилерді жарамсыз деп тауып, салыстырылатын нұсқалар жиынын тарылтуға болады.
25.Түйіндес симплекс әдіс
Сызықтық программалаудың әрбір есебімен түйіндес деп аталатын сызықтық программалаудың басқа бір есебі тығыз байланысқан. Бастапқы есепті әуелгі дейміз. Әуелгі есеп пен түйіндес есеп арасындағы басты байланыс – олардың бірін тікелей шешу арқылы екіншісінің шешімдерін табуға болатындығында.
Түйіндес есепке көшу міндетті емес екенін, өйткені симплекс-кестені қарастырсақ бағандарда әуелгі есеп, ал бағандарда түйіндес есеп жазылғанын байқаймыз. Әрі әуелгі есептің жоспарының бағалары , ал түйіндес есептің жоспарының бағалары – . Сондықтан, түйіндес есептің тиімді жоспарын әуелгі есеп жазылған симплекс-кестеден, демек әуелгі есептің тиімді жоспарынан ала аламыз. Бұл әдіс түйіндес симплекс әдіс деп аталады.
Айталық жалпы түрде қойылған сызықты программалаудың әуелгі есебін шешу керек болсын:
,
, .
Онда түйіндес есеп мынаны білдіреді:
,
.
Мәселен, барлық векторлары үшін орындалатын, векторының кемінде бір компоненті (мысалы, ) теріс базисі таңдалсын дейік. Онда түйіндестік теоремасының негізінде алатынымыз: – түйіндес есептің жоспары. Бұл жоспар тиімді емес, өйткені бір жағынан таңдалған базисте теріс компонент қамтығандықтан әуелгі есептің тиімді жоспары бола алмайды, ал екінші жағынан түйіндес есептің бағасы теріс болмауы керек.
Сонымен, теріс компонентіне сай векторын базистен шығарып, ал теріс бағалауға сәйкес векторды түйіндес айнымалының базисіне енгізу қажет.
Әуелгі есептің базисіне енгізілетін векторды анықтау үшін -ші жолды қарастырамыз: егер онда қамстылмаса, онда түйіндес есептің сызықтық функциясы шешімдер облысында шектелмеген, ал бастапқы есептің шешімі жоқ. Егер де қайбір болса, онда осындай теріс мәндерді қамтитын бағандар үшін мәндерін есептейміз. Есеп минимумге шешілсе мәніне сай векторды анықтаймыз, ал есеп максимумге шешілсе, мәніне сай векторды анықтаймыз.
Осы вектор әуелгі есептің базисіне енгізіледі. Базистен шығарылатын вектор бағыттаушы жолдан анықталады.
Егер болса, онда жағдайында ғана шешуші элемент ретінде қабылданады. Шешуші элементті осылай таңдау бұл кезеңде векторының теріс компоненттері санының өсуіне соқтырмайды. Бұл процесс болғанша жалғаса береді. Бұл кезде түйіндес есептің тиімді жоспары, яғни түйіндес есептің де тиімді жоспары табылады.
Түйіндес симплекс әдіс алгоритмімен есептеулер жасағанда барлық жойылғанша шарптына назар аудармай, содан соң жай симплекс әдіспен тиімді жоспарды табамыз. Мұны барлық кезінде пайдаланған ыңғайлы. Онда бір итерацияда әуелгі есептің жоспарына көшу үшін өрнегі қолданылады. Бұл әдіс шектеулер жүйесінде түрлендірулер санын азайтуға, сонымен қатар симплекс-кесте өлшемін кішірейтуге мүмкіндік береді.
26.Шекаралар мен тармақтар әдісі
Шекаралар мен тармақтар әдісі – комбинаторика әдістерінің бірі. Оның мағанасы – нұсқаларды белгілі бір тәртіпте сұрыптауды және олардың арасындағы тиімді шешім табуға қандайда бір қесиеттері бойынша пайдалы ларын ғана қарастыруды білдіреді. Шекаралар мен тармақтар әдісінде бүтін емес ұйғарымды шешімдер жиыны қайбір тәсілмен бірнеше ішкі жиындарға тармақталады да, олардың әрқайсысы үшін бүтін санды шешім алуды көздейтін жаңа сызықтық программалау есебі шығарылады. Әрбір тармақта жаңа екі есеп алынады.Бұл кезеңде төмендегі төрт жағдайдың бірі орын алады.
Бастапқы төбе бастапқы 1-есептің тиімді жоспарына сай келеді, ал онымен тармақтар арқылы қосылған төбелер 1-есептің бөлшек санды қамтитын тиімді жоспарындағы бір айнымалы бойынша шектеулер үшін құрылған жаңа есептің тиімді жоспарын білдіреді.Әрбір төбенің өз тармағы бар. Және бұл кездегі әр қадамда мақсат функциясының мәні кіші болатын тармақ таңдалады. Егер қайбір қадамда бүтін сандық мәнге иеболатын жоспар алынып,ондағы мақсат функциясының мәні басқа тармақтардағы мақсат функция-сының мәнінен кіші немесе соған тең болса онда алынған жоспар бастапқы бүтін сандық программалау есебінің тиімді жоспары болады да, сондағы мақсат функциясының мәні минимум шаманы білдіреді. Бүтін сандық сызықтық программалау есебін қарастыралық:
(1) (2)
(3)
- бүтін (4)
27.Қысқа жол есебі. Дейкстра алгоритмі
Қысқа жол есебі транспорт желісіндегі берілген бастапқы пункт пен көзделген пункт арасындағы қысқа жолды анықтау үшін қолданы-лады. Мұндай моделдерді сан түрлі жағдайларда қолдануға болады. Енді осы есептің кейбір практикалық жағдайларына тоқталалық.
1-сурет. Жабдықты алмастыру есебі қысқа жол іздеу есебі ретінде
2-сурет. Желілік модель
3-сурет. Қысқа жол іздеу есебінің желілік моделі
4-сурет. Үш бидонмен бас қатыру – қысқа жол іздеу есебі.
Қысқа жолды анықтау алгоритмдеріне: Дейкстра, Флойд алгоритмдерін жатқызуға болады. Дейкстра алгоритмі бастапқы (1-ші) түйін мен кез-келген басқа түйін арасындағы ең қысқа арақашықтықты табуға арналған.Біз i түйінінен j түйініне жету үшін мынадай белгілеулерді қолданамыз: ui- 1-ші түйіннен i-ші түйінге дейінгі қысқа қашықтық. dij- (i, j) қабырғасының ұзындығы болсын делік, онда j түйінінің таңбасы келесідей анықталады:[uj, i] = [ui +dij, i], dij>= 0.Түйін таңбалары екі түрлі болады: уақытша және тұрақты.Уақытша таңбалар одан да қысқа жол табылғанда келесі уақытша таңбаға ауысады. Ең қысқа жол табылғанда уақытша таңба тұрақты таңбаға ауысады.Дейкстра алгоритмі: 0 кезең. Бастапқы 1 түйінге [0, -] таңбасы беріледі. i = 1 делік. i-ші кезең.а) i түйінінен шығатын барлық уақытша j түйіні үшін [ui + dij, i] таңбасы қарастырылады.Егер j түйінінде k түйінінен алған [uj, k] таңбасы болса және ui + dij< uj болса, онда [uj, k] таңбасы [ui + dij, i] таңбасына ауысады. б)Егер барлық түйіндер тұрақты болса есептеу тоқтатылады.1-ші түйін мен кез келген басқа түйін арасындағы жол (маршрут) ең соңғы түйіннен 1 түйінге дейін тұрақты таңбаларды алып тастап отырғанда дұрыс болса, сол жол шешім болады.
1-сурет. Дейкстра алгоритмі желісінің мысалы.
2-сурет. Дейкстра алгоритмін қолдану
28.Сызықтық программалаудағы түйіндестік
Сызықтық программалаудың әрбір есебімен түйіндес деп аталатын сызықтық программалаудың басқа бір есебі тығыз байланысқан. Бастапқы есепті әуелгі дейміз. Әуелгі есеп пен түйіндес есеп арасындағы басты байланыс – олардың бірін тікелей шешу арқылы екіншісінің шешімдерін табуға болатындығында. Кез келген сызықты программалау есебіне сәйкес түйіндес есеп қисындауға болатындығы белгілі. Мәселен жалпы түрдегі сызықты программалаудың әуелгі есебі берілсін
(3.1)
Мұнда үшін теңсіздік түріндегі шектеулер, ал үшін теңдік түріндегі шектеулер жазылған максимумделінетін мақсат функциясы берілген. айнымалалары теріс емес, қалған айнымалылар кез келген таңбалы мәндер қабылдайды. Сонымен қатар мұнда , (теңсіздік түріндегі шектеулер болмайтын), (теңдік түріндегі шектеулер болмайтын ) және (барлық айнымалылар кез келген таңба қабылдайтын), (бар айнымалылар теріс емес) жағдайлары да кездесуі мүмкін. Енді (1) есебіндегі шектеулер жүйесімен анықталатын ұйғарымды шешімдер жиынын арқылы белгілейміз. Сызықты программалаудың түйіндес есебі мына түрде жазылады:
(3.2)
29.Операцияларды зерттеудің типтік есептері
Таңдалған тиімділік принципін (жүйе қызметі сапасының критерийі) сипаттайтын мақсат функциясының түрі операцияларды зерттеу есептерінің типіне байланысты. ОЗ есептерін келесі типтерге бөлеміз:
1) Ықтималдықты есептер (тәуекелмен шешім қабылдау): қай бір стратегияны қабылдағанда мақсатқа жету ықтималдығы белгісіз түрлі нәтижелер алынады;
2) Детерминді есептер (толық анықталғандық шартында шешім қабылдау): әрбір таңдалған стратегия жалғыз нәтижеге соқтырады;
3) Анықталмағандықты есептер (дәлірек айтқанда, анықталмаған-дықта шешім қабылдау есебі): белгілі бір стратегияны қабылдағанда түрлі нәтижелер алынуы мүмкін болса да, мұның ықтималдықты есептерден айырмашылығы: мүмкін нәтижелердің ешқандай статистикалық сипаттарын білмейміз. Анықталмағандық қоршаған орта туралы ешқандай ақпараттартың жоқтығыған, сонымен қатар шешім қабылдау процесінде ескерілетін басқа кісілер (қарсыластар, бәсекелестер, серіктестер) ұстанымының алдын ала белгісіздігінен пайда болады .
Мақсат функциясын таңдау
Ықтималдықты есептерде
стратегиясын қолданғандағы нәтижесін алудың шартты ықтималдығын белгілі деп саналады. Бұл жағдайда мақсат функциясы ретінде
стратегияның күтілетін пайдалылығы , яғни мына түрдегі функция таңдалады:
Енді тәуекел жағдайында ұтымды ұстаным таңдау үшін тиімділік есебін шығарамыз:
Детерминдi есептерде
стратегиясын бірге тең ықтималдықпен таңдағанда нәтижесі алынады, сондықтан мақсат функциясы ретінде
түріндегі стратегияның пайдалылығын алып, ең жақсы стратегияны анықтаудың тиімділік есебін қойуға болады:
Анықталмағандықпен шешім қабылдау есептерінде оңтайлы ұстаным критерийлері қолданады.
30.Түйіндес айнымалылардың экономикалық мағанасы
Қорларды басқару есебінің түйіндес айнымалыларына экономикалық түсінік берейік . Әуелгі есептің жазылуы:
(1)
мұндағы –-ші өнім шығару көлемі, ; – ші өнім бірлігінен түскен кіріс ; –ші өнімнің бірлігін шығаруға -ші ресурстың жұмсалуы ; – қолдағы -ші ресурс қоры, .
Сызықты программалаудың тиісті түйіндес есебін құралық:
(2)
Мәселен, сызықты программалаудың әуелгі және түйіндес есептері тиісінше және шешімдеріне ие болсын, және түйіндестік теориясына сай мақсат функцияларының екі есептегі де мәндері бірдей: делік. Әуелгі (1) СП есебінде шектеулі ресурстар кезінде фирманың кірісін максимумдайтын өнім шығару жоспарын анықтау керек. Осындағы әуелгі есептің экономикалық кескіні түсінікті болғанымен, (2) СП түйіндес есебінің мағнасы соншалықты айқын емес. Түйіндес айнымылылыры мен шектеуінің қандай мағнасы бар?
Қайбір - ші ресурстың қорын 1 ге арттырайық: . Бұл түйіндес есептегі мақсат функциясының салмақ коэффициенттерін өзгеріске ұшыратқанымен, шектеулер қаз қалпында қалады (ұйғарымды шешімдер облысы өзгермейді). Бұл өзгерістер түйіндес есеп үшін мардымсыз, яғни ол мұндай өзгерістерді сезінбейді де бұрынғы шешім тиімді болып қалады дейік. Бұл кезде түйіндес есептегі мақсат функциясы өзгереді де мынаған тең болады . Түйіндестік теоремасына сай әуелгі есептегі мақсат функциясының тиімді мәні , яғни кіріс шамасына артады. Сонымен, түйіндес айнымалылар мынаны білдіреді: мәні - ші ресурсты 1 ге арттырғанда алынатын қосымша кіріске тең. Егер , онда бұл -ші ресурс артық болып кеткенін, бұдан былай оны өсіру қосымша кіріс алуға соқтырмайтынын көрсетеді. Шындығында да, егер -ші ресурс толық жұмсалмаса
, қатаң теңсіздік орындалады да , қатаңсыздықты толықтырушы шартынан .екендігі шығады Сонымен, СП (2) түйіндес есебін шығару арқылы, қандай ресурстар артық болатынын анықтауға, сонымен қатар қосымша кіріс алу тұрғысынан ресурстарды бағалауға, бірінші кезекте қай ресурс қорларын толықтыру жөнінде кеңес беруге болатындығына көз жеткіземіз.
Әуелгі (1) СП есебіндегі симплекс-әдістің әр қадамында есептелінетін бағалауын түрінде жазуға болатындығы белгілі. Сонымен, (2) СП түйіндес есебінің шарттарының орындалуы нақтысында тиімділік шартының қамтамасыз етілуін білдіреді. Енді қосындысын -ші өнім бірлігін шығаруға пайдаланылатын ресурстар бағасы ретінде көреміз. Егер жоспар әлі де тиімсіз болса, онда бағасы минимум индексін табамыз.