Алгоритм Келтірілген алгоритмге сәйкестік



МАЗМҰНЫ
КІРІСПЕ
1. СТОХАСТИКАЛЫҚ БАҒДАРЛАМАЛАУ НЕГІЗДЕРІ
1. 1. Стохастикалық программалаудың екі жақтылық әдісі
1.2. Стохастикалық программалаудың «солтүстік -батыс»
1.3. Ең кіші элемент әдісін пайдаланып
2.СЫЗЫҚТЫ ЖӘНЕ СЫЗЫҚТЫ ЕМЕС МОДЕЛІ
2.1. Ағымдағы жоспарды тиімділікке тексеру мысалдары
2.2. Қорларды басқарудың стохастикалық үлгілеулері
3.ҚОРЫТЫНДЫ
4.ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ
5.ҚОСЫМША
КІРІСПЕ
Модель дегеніміз - нақты объектіні, процессті немесе
Модельдеу – объектілерді, процесстерді немесе құбылыстарды зерттеу мақсатында
Модель – көрнекі түрде жазбаша жоспар, сызба ретінде
Модельдерді қасиеттеріне қарай мынадай топтарға жіктейді:
1. Қолдану аймағы.
2. Модельде уақыт факторын
3. Білім саласына қарай
4. Модельді көрсету тәсіліне
Қолдану аймағына қарай модель не үшін және қандай
Оқу моделі – көрнекі оқу құралдары, әр түрлі
Тәжірбиелік модель – жобалау объектісінің кішірейтілген немесе өте
Ғылыми-техникалық модельдер – процесстер мен құбылыстарды зерттеу мақсатында
Модельді уақыт факторына байланысты динамикалық және статистикалық деп
Динамикалық модель – уақыт барысындағы объектінің қасиеттерінің өзгерісін
Экономика – математикалық модельдеуде көптеген есептер
Экономикалық есептердің көптеген кластары
Осы курстық жобада, стохастикалық
1 СТОХАСТИКАЛЫҚ БАҒДАРЛАМАЛАУ НЕГІЗДЕРІ.
1.1. Стохастикалық бағдарламалаудың өзара екі жақтылық
Математиканың көптеген салаларында екі жақтылық теоремалары деп аталатын
Өзара екі жақтылық есебін сипаттайық. Бастапқы немесе І-ші
a11х1+а12х2+...
а21-х1+а22-х2+...
п белгісізді т теңсіздікте жүйесі мен сызықты форма
f = с1х1+с2х2+... + с„х„ (2)
берілсін.
(1)-ші жүйенің барлық теріс емес шешімдерінің ішінен (2)-ші
а х + а
… … …
a x + a
a x + a
… … …
a x + a x
және стохастикалық форма
cр = b1у1+b2у2+... + bтут
түрінде жазылады.
(Г) жүйесінің барлық теріс емес шешімдерінің ішінен
максимумдейтінін таңдап алу керек. Бұл есепті (П) -
Екі есепті салыстыру арқылы мынаны байқауға болады.
1. Бастапқы есептегі белгісіздер жанындағы
Әр есептің шектеулер жүйесінің оң жағында екінші есептің
Бастапқы есептегі теңсіздіктер > - типті, і- формасының
табылу керек те, ал екі жақтылық есебіндегі шектеулерде
яғни қарама-қарсы мағыналы, ал ср
мағыналы мэн қабылдайды.
Біреуінің белгісіздерінің саны, екіншісінің шектеулер санына тең.
Осы бес шартты қанағаттандыратын стохастикалық бағдарлау есебі симметриялы
Стохастикалық бағдарлау есептерінде симметриялы екі жақты парлармен
а) Негізгі есеп: Теңдік сақталады:
а х + а
… … …
a x + a
a x + a
… … …
a x + a x
б) Екі жақтылық есебі:
а у + а
… … …
a у + a
a у + a
… … …
a у + a у
Бұл есептер симметриялы
(3) - (4)-ші есептердегі шектеулер теңдікпен берілген.
(3')-(4')-есептерінде уn айнымалыларының \і =
белгілері жоқ.
2. Сонымен қатар, екі жақтылық есебіндегі стохастикалық форма
mах ср = -min(- ср)
- болатынын көрсетуге болады. Олай болса, екіншісі үшін
Екі жақтылық теоремасы. Егер бастапқы есептің тиімді шешімі
тіп / = тах ф.
Егер бастапқы есепте стохастикалық форма төменнен шектелмеген болса,
Екі жақтылық әдісі
Екі жақтылық теоремасымен бағдарлау есебін шығарудың әдістерінің бірі
Стохастикалық бағдарлау есебі теңсіздік түріндегі шектеулермен берілсін. Оны
Сәйкестік былай орнатылады:
Х1
. .
Ут+1'" Ут+п У .
Осылай тұжырымдау нәтижесінде (II) есебінің шешімі табылады. Екі
Мысал 1. ф = -ух - 2у2 -
- у, + 2у7 -Зу. 1
2у -у2-у3-1
2x1 - x2 > -2
- 3x1 - x2 > -3
Енді бұл форма мен шектеулердің қалай алынғанын түсіндірейік.
ІІ есепте айнымалылар саны үшеу және де: сх
ср = Ьх -ух +Ь2 -у2+... + Ът
Салыстыру арқылы bх =\, b2 =-2, bъ =-3-
ап =-1, а2Х =2, аъх
-екендіктеріне көз жеткіземіз.
Осы айтылғандарды пайдаланып І-есепті құрамыз.
/ = сх-хх +с2-х2+... + сп -х„(2)
және (1)-ді табамыз. т = 3 - болғандықтан
сх = 1, с2 = -2 - болып
/ = \-хх +(-\)-х2=хх-х2.
Енді (1)-ші шектеулерді жазайық
х2>-1 (=bХ) (2)-х1+(-\)-х2>-2 (=b2) (-3)-х1+(-1)-х2>-3 (=b3)
x1 + 2x2 >-1
2x1 - x2 > -2
3x1 - x2 > -3
F = x1 -х2.
Шектеулер жүйесі және мақсатты функция алынды. Екі жақтылы
түрде жазуға болады.
1-ші есеп.
- x1 + 2x2 - x3 = -1
-х5=-3
Минимумдеу
/ = x1 - x2 + 0 •
- және барлық
айнымалылары теріс болмауы тиіс.
Есепті симплекс-әдіспен шығаруға болады.
x2 =2 + 2x4 - x5,
x2 = 2 + 2x1 - x4,
f= x 4 — x1
(II) - екінші қарастырылған есептің
Ресурстары bг \і = \,т) өндіріс орны, бұл
пайдаланады және оны өткізеді. Мұндағы қойылатын мақсат ресурстарды
Ах0 (і = \^п)
Сонда екі жақтылық белгісі негізгі есеппен жаңадан қойылған
Негізгі есептің үлгісі Жаңадан қойылған есептің үлгісі
1. f =>mах cр=>mіп
2. Шектеулер жүйесі < - типті Шектеулер жүйесі
3. С} -лер мақсатты
4. bг - бос мүшелер bг -лер
5. Шектеулер
Осы екі жақты есеп болудың бес белгісі бізде
І - тура есеп, ІІ - оған екі
Егер осы есептердің біреуінің стохастикалық функциясы шектеусіз болса,
Екі жақтылықтың екінші теоремасы:
Теорема 2 . Егер тура есептегі стохастикалық
Мысал 1.
Тура есеп.
f = 6x1 + 4x2 -» mах
2x1 + 4x2 < 8
2x1 + x2 < 6 Екі жақтылық есебі.
ср = 8x + 6x2 —> mіп
2y + 2y2 > 6
4у, +2у2 >4
х2>0."
Екі жақтылық есебін құрудың мысалдары.
Мысал 1. Стохастикалық программалау есебі қойылған: cызықты функция
Ғ = 14x1 +10х2 +14х3 +11х4
келесі шектеулермен берілген.
4x1 + 2x2 + 2x4 + 3x4 0
Тиімділік шарты (3, 3) - ұяшығында орындалмай тұр.
Қадам -3. Тасымалдау жоспарын жетілдіру^
1. Тиімділік (3, 3) ұяшығында
Кесте 10
120 60 50 10
70
70
50
50-0 +0
60 100 80
3-ші жіберушіден 5+0 -жүк бірлігі кетті. Ол қордан
Кесте 11
у-шілер Жібер Жіберушілердегі қор
1 2 3 4
100 250 50 10
1 200 5 8 9 1
2 190 3 7 9 2
3 100 5 8 3 9
Шешуі: Есептің шешуін де кесте түрінде келтіреміз.
Кесте 12
№ Алгоритм Келтірілген алгоритмге сәйкестік
Орнату
1 Жіберушілердің қорларының
Т Ү^аг = 200+199+100 =490
қосындысын анықтаймыз: ^а.
і=\ і=\
2 Барлық қажеттіліктердің
П Ү^Ъ} = 100+250+50+10 = 410
қосындысын ^ Ъ} -ді анықтау керек
3 Алынған нэтижелерді салыстыру. т
Ү^аг> ү^Ъ}( 490 > 410)
4 Егер жіберушілердегі қорлардың
жиынтығы қажеттіліктен артық
т
болса К = ^ а. - ^ Ъ}.
есептеу керек.
5 Қажеттілігі К -ге тең,
тұтынушу енгіземіз. номермен, қажеттілігін 80 -ге тең
етш енгіземіз.
6 Кестеге жаңа бағана
керек.
7 Жаңа бағанадағы
құныны нөлге
(Сгу =0) теңеп аламыз.
8 Жаңа кесте құру керек. Нәтиже төмендегі 2
келтірілген.
Кесте 13
Жіберу-шілер Қорлар Тұлынушылар және олардың қажеттілігі
1 2 3 4 5
100 250 50 10 80
1 200 5 8 9 1 0
2 190 3 7 9 2 0
3 100 5 8 3 9 0
Мысал 2.
Өз бетінше жұмыс жасауға келесі кестеде келтірілген ашық
Кесте 14
Қорлар Тұтынушылар және олардың қажеттілігі
1 2 3
60 60 50
1 50 5 8 9
2 70 3 7 9
3 60 5 8 3
Мысал 3. Берілген ашық көлік қатынасы
Кесте 15
Жіберу-шілер- Түтынушылар жэне олардың қажеттілігі
1 2 3 4
дің қорлары 50 50 40 60
1 30 5 4 6 4
2 70 4 5 5 8
3 70 7 3 4 7
Шешуі: Есептің шешу жолын келесі кестеде келтіреміз.
Кесте 16
№ Алгоритм Келтірілген алгоритмге сәйкестік орнату
1 Жіберушілердің қорларының
т
қосындысын анықтау: ^аг
і=\ Т
£аг = 30+70+70 = 170
г=1
2 Барлық сұраныстардың
п
қосындысын ^ Ъ} -ді анықтау. ҮЪ} = 50+50+40+60
3 Алынған нәтижелерді салыстыру. ^аг


Ұқсас жұмыстар
Екі жақтылық есебі
Алгоритмдер теориясы және берілгендер құрылымы
«Компьютер көмегімен есеп шығару технологиясын математикалық білім сапасын жақсартуда пайдалану ерекшеліктері»
Алгоритмдер және деректер структурасы
Алгоритмдік тіл және программалау тілі
Статикалық идентификация әдісі
Іздеу есептерінің шешілімі. Іздеу: қайтару арқылы теріп алу
АЛГОРИТМНІҢ ПРАКТИКАЛЫҚ АСПЕКТІЛЕРІ. АВТОМАТТАР ТЕОРИЯСЫ
Жанармай станциясының жұмысын модельдеу».
Алгоритм қасиеттері