Симплекс әдісінің геометриялық түсінігі

Пән: Математика, Геометрия
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 18 бет
Таңдаулыға:

Мазмұны

І
Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... ... ... 3

ІІ Симплекс әдісі
2.1 Симплекс әдісінің геометриялық түсінігі
... ... ... ... ... ... ... ... ... ... ... ... ... 5
2.2 Қысқаша симплекс әдісінің шығу тарихы
... ... ... ... ... ... ... ... ... ... ... ...9

ІІІ Симллекс әдісінің алгоритмі
3.1 Симплекс әдісінің мақсаты мен идеясы
... ... ... ... ... ... ... ... ... ... ... ... ... ..11
3.2 Тәжірибелік есептерді симплекс әдісімен шығару
... ... ... ... ... ... ... ... ... 19

ІV
Қорытынды ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... .26
V Пайдаланылған
әдебиеттер ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... 27

Кіріспе

Симплекс - ағылшын сөзі, кеңістікгегі қарапайым көпбұрышты көп жақты
бейне, оның бұрыштарының координаттары ізделініп отырған белгісіздердің
оптималды мәндеріне сәйкес.
Симплекс әдісінің негізгі мақсаты - егер мақсат фунция максимумге
ізделінсе, онда алғашқы табылған төбеден келесі тебеге жылжығанда кез
келген төбеге емес, мақсат функцияның мәні өсетін тебеге жылжуды қамтамасыз
ету. (Егер есеп минимумге ізделінсе, онда алғашқы мақсат функцияның
мәнінен кейінгі мәні кіші болуын қамтамасыз ету).
Симплекс әдісін қолданғанда бір төбеден екінші төбеге көшкенде белгілі
бір бағытта жоспарлы түрде көшіледі, бұл жағдайда кейбір керексіз
көпжақтының төбелері қарастырылмай қалып қалады да, есептің шешу жұмысы
ұтымды, жедел жүргізіледі.Симплекс әдісінің қарапайым гоеметериялық
интерпретациясы анық көрсетілген, егер оптималдық төбеге көрсетілген
стрелка бағытымен жылжысақ онда осы бағыттан тысқары қалған төбелер
қарастырылмайды. Симплекс әдісін графиктік жолмен іске асырғанда осы
айтылған жағдайларды графиктен көзбен көруге болады. Бірақ мұндай жұмыстар
белгісіздердің саны үштен көп болғанда қиындайды да, тіпті оларды орындау
мүмкін емес. Мұндай кездерде тек ойша тұжырымдарға ғана сүйенуге тура
келеді. Сонымен қатар графиктік жолмен шығатын есептердің тәжірбиелік
есептерге қарағанда мүмкіндіктері аз, маңызы және мәнісі төмен. Сондықтан
сызықты программалау есептерін симплекс әдісімен шешудің математикалық
алгоритмдерінің маңызы үлкен.
Курстық жобаның мақсаты: Симплекс әдісінің геометриялық әдістерін
қолданудың тиімді жолдары:
Зерттеу міндеттері: Универсал Симплекс әдісі теориясының есептеу
алгоритмі, қысқаша симплекс әдісінің шығу тарихы, симллекс әдісінің
алгоритмі, симплекс әдісінің мақсаты мен идеясы туралы толық мағлұмат беру.

Зерттеу объектісі: Универсал Симплекс әдістерін қолданып есептердің
алгоритмін тұрғызу жолдары.
Зерттеу пәні: Өндірістік және экономикалық процестерді модельдеу.
Зерттеу әдістері: Ғылыми әдістемелік оқулықтар, журналдар, жаңа
ақпараттық технологиялар.
Курстық жобаның құрылымы: Кіріспеден, негізгі бөлімнен, қорытындыдан,
қосымша және пайдаланылған әдебиеттерден тұрады.

ІІ Симплекс әдісі
2.1 Симплекс әдісінің геометриялық түсінігі

Графиктік әдіс сызықты программалау есептері тек екі белгісізден ғана
құрылғанда қолданылады, ал есеп үш белгісізден асса, онда мұндай есептерді
графиктік жолмен шешу қиынға соғады. Теория жүзіндө екі және үш белгісізі
бар есептерді графиктік жолмен шешкен сияқты кез келген белгісізі бар
есептер де графиктік жолмен шешіледі деп қарастыруға болады. Өйткені егер
белгісіздің саны екеу болса, есептің анықталу аймағы жазықтықта жатқан
дөңес көп бұрышты береді. Егер белгісіздің саны үшеу болса, онда есептің
анықталу аймағы кеңістікте жатқан үш өлшемді дөңес көп жақтыны береді. Егер
шектеуші шарттар мынадай белгісізден тұрса:

онда осы шектеулер арқылы құрастырылған М аймағын, 1-ширектегі n - өлшемді
кеңістіктегі өлшемі n болатын дөңес көпжақты деп қарастыруға болады. Бұл
жағдайда мақсат функциясы

Z-дің кез-келген тұрақты мәнінде n - өлшемді гипержазықтық.
Симплекс әдісінің мән-жайын тереңірек түсіну үшін алдыңғы тақы-рыптағы
кейбір белгілі қағидаларды тағы да еске түсірейік. Мысалға, егер Z-дің мәні
-∞ тен +∞ дейін өзгерсе, онда гипержазықтық өзіне-өзі параллель жылжи
отырып, М дөңес көпжақтыға жетеді де, онымен бір нүктеде (немесе бір
қабырғасының үстіне түседі) қиылысады, бұл нүкте ену нүктесі делінетіні
алдыңғы тақырыпта айтылды. Гипержазықтықты және өзіне - өзін параллель
етіп, М аймағы бойынша жылжыта берсек
Z-дің бір мәнінде, ол гипержазықдық М аймағы соңғы нүктесімен жанасады да
(бұл нүкте "шығу" нүктесі делінетіні белгілі), осыдан кейін М аймағынан
шығып кетеді. Бұл түсініктерден кейін симплекс әдісінің геометриялық
мағынасына қысқаша тақталайық. Біріншіден, алдыңғы тақырыптарда
айтылғандай егер сызықты программалау есептерінің оптималды шешімі
болса,ол шешім дөңес көпжақты М аймағының төбелерінің біріңде жатады деген
теорема белгілі. Екіншіден, мақсат функцияның графигін құрғанда, Z=d деп
қарастырдық, бұл жағдайда (-∞ + ∞) d-нің мәніне байланысты гипертүзу
(гипержазықтық), яғни есептің анықталу аймағы М дөңес көпбұрышынан әлде
қайда алыста жатуы мүмкін. Тәжірибелік есептерді шешкенде мұндай жағдай көп
қосымша есептеулер жүргізуді қажет етеді. Сондықтан бұл екі тұжырымды
(шешім қабылдауды) тереңірек талқылайық.
Талқылауды екінші ұғымнан бастайық. Мақсат функцияның жылжу бағыты
оның алғашқы құрылуына байланысты, өйткені кейінгілері сол бұрынғы графикке
параллель болып келеді. Егер Z-дің алғашқы графигі дұрыс құрылмаса, тікелей
өзіне-өзін параллель жылжытудың нәтижесінде нақтылы олтималды шешім ала
алмауымыз мүмкін.
Енді Z-дің алғашқы графигін тәжірибе жүзінде қалай құратынын
түсіндірейік. Ол үшін екі белгісізі бар есепті қарастыралық:

Егер Z = d = 0 десек теңдеудің графигі координат осінің бас
нүктесінен өтетінін байқаймыз. Бірақ бір нүкте арқылы шексіз түзулер
жүргізуге болады деген геометриялық теорема бойынша олардың ішІнен бізге
қажетті біреуін ғана тауып алу қажет. Оны табу үшін қарастырылып отырған
түзу сызықХ1 және Х2өстерімен қандай бұрыш жасайтынын анықтау керек, яғни
Z(х1, х2) - функциясының градиентін іздеу қажет, сонымен қатар табылған
градиент осы түзу сызықтың жылжу бағытын көрсететіні 3-бөлімде айтылды.
Берілген функция үшіy Z(Х1, X2) = С1Х1+ С2 X2 оның градиенті мына
формуламен есептелінеді

мұндағы сәйкес
остердегі бағыттаушы бірлік векторлар,ал
- функцияның Х1жәнө Х 2 бойынша сызықты дербес туындылары.
Z(Х1, Х2) - функцияның Х1және Х 2 белгісіздері бойынша сызықты функция
болғандықтан:

деп есептеп градиентті былай өрнектейік:

Градиенттің ұзындығы мына формуламен есептелінеді:

Сонымең бағыттаушы векторы n десек, онда:

1 – сурет.

Енді 1-теоремадағы ұғымды қайта еске түсірелік. Теореиа бойынша Z
мақсат функцияның оптималды мәнін табу үшін М-дөңес көпбұрыштарының барлық
төбелерін қарастыру керек, ол ушін әр кезде бір төбеден екінші төбеге
жылжып отыру қажет. Кейде Z - түзуі өзіне-өзі параллель жылжьіғанда кейбір
төбеден өтпей қалуы да мүмкін. Бір төбеден келесі төбеге жедел көше
отырып, оптималды мән беретін төбене іздеп табу қажет. Сөйтіп осы
баяндалған геометриялық әрекеттер симплекс әдісінің негізін құрайды.
Симплекс - ағылшын сөзі, кеңістікгегі қарапайым көпбұрышты көп жақты
бейне, оның бұрыштарының координаттары ізделініп отырған белгісіздердің
оптималды мәндеріне сәйкес. Көп өлшемді геометрияда

шарттарын қанағаттандыратын нүктесінің геометриялық орны симплекс
делінеді.
Симплекс әдісінің негізгі мақсаты - егер мақсат фунция максимумге
ізделінсе, онда алғашқы табылған төбеден келесі тебеге жылжығанда кез
келген төбеге емес, мақсат функцияның мәні өсетін тебеге жылжуды қамтамасыз
ету. (Егер есеп минимумге ізделінсе, онда алғашқы мақсат функцияның
мәнінен кейінгі мәні кіші болуын қамтамасыз ету).
Сонымен, симплекс әдісін қолданғанда бір төбеден екінші төбеге
көшкенде белгілі бір бағытта жоспарлы түрде көшіледі, бұл жағдайда кейбір
керексіз көпжақтының төбелері қарастырылмай қалып қалады да, есептің шешу
жұмысы ұтымды, жедел жүргізіледі.Симплекс әдісінің қарапайым
гоеметериялық интерпретациясы анық көрсетілген, егер оптималдық төбеге
көрсетілген стрелка бағытымен жылжысақ онда осы бағыттан тысқары қалған
төбелер қарастырылмайды. Симплекс әдісін графиктік жолмен іске асырғанда
осы айтылған жағдайларды графиктен көзбен көруге болады. Бірақ мұндай
жұмыстар белгісіздердің саны үштен көп болғанда қиындайды да, тіпті оларды
орындау мүмкін емес. Мұндай кездерде тек ойша тұжырымдарға ғана сүйенуге
тура келеді. Сонымен қатар графиктік жолмен шығатын есептердің тәжірбиелік
есептерге қарағанда мүмкіндіктері аз, маңызы және мәнісі төмен.Сондықтан
сызықты программалау есептерін симплекс әдісімен шешудің математикалық
алгоритмдерінің маңызы үлкен.
Осы алгоритмдерді қарастырмас бұрын симплекс әдісіне
байланысты аздаған қысқаша тарихи мәліметтерге тоқталайық.

2.2 Қысқаша симплекс әдісінің шығу тарихы

Жалпы математикалық программалау пәні өмірдің қажеттілігінен
пайда болған қолданбалы математиканың негізгі бөлімі. Жоғарыда
айтылғандай математикалық программалаудың ішіндегі барлық халық
шаруашылығына көп таралғаны, әртүрлі әдістері терең зерттелген бөлім
сызықты программалау әдістері болып есептелінеді. Математикалық
программалау пәнінің ең негізгі бөлімі сызықты программалау есептерді дүние
жүзінде бірінші рет 1930 жылдары жарық көрді.Сызықты программалау есептері
басқа тәжрибелік есептерге қарағанда өте қарапайым, зерттеуге ыңғайлы.
Сызықты программалаудың дербес есебінің бірі-қатынас есебінің
дербес түрі 1931жылы Венгрияда басылып шықты, бұл мақаланың авторы
математик Эгервари болатын. Кейінірек келе бұл мақаланың негізінде бірнеше
еңбектер жазылады. Бұған мысал үшін 1951 және 1956 жылдары жарыққа шыққан
КунХ.В.жәнеТаккерА,В 1957ж. жазылған Форд Х.Р. және Фалкерсон Д. Р.
еңбектерін алуға болады. Бұл еңбектерде қатынас есептерін шөшуге арналған
әдістер көрсетілген кейін келе әдебиетерде бұл әдісті қатынас есептерін
шешудегі Венгер әдісі дейтін болды.
Сызықты программалау атты термин алғаш рет 1940 жылдары АҚШ-та
қолданылды. Сызықты программалау әдісінің арнайы есептерінің бірі 1941 жылы
АҚШ-та басылып шықты, оның авторы Хичкок Ф. Л. бопатын.
Бұрынғы Кеңестер Одағында сызықты программалау әдісінің негізін
қалаушы академик Л. В. Канторович болды. Себебі оның көптеген сызықтық
программалау әдістеріне арналған дербес есептері 1930 жылдардан бастап
жарыққа шыға бастады. 1956 жылы Дж. Данциг, X. Р. Форд және Д. Р. Фалкерсон
Венгер әдісінің негізінде сызықты программалаудың есептерін шешуге
арналған, Л. В. Канторович ұсынған потенциал әдісіне өте сәйкес әдіс
ұсынды. Ал 1947 жылы Дж. Б. Данциг сызықтық программалау әдістерінің
ішіндегі әмебап симплекс әдісін жарыққа шығарды. Бірақ бұл әдістің Л. В.
Канторовичтың 1939 ж. ұсынған, біртіндеп жақсарту әдісінен айырмашылығы өте
аз болатын. Өкінішке орай бұл әдісті Л. В. Канторович бұрын үсынса да
көптеген әдебиеттерде, оқулықтарда симплекс әдісін Дж. Данциг әдісі деп
атайды.

ІІІ бөлім. Симллекс әдісінің алгоритмі
3.1 Симплекс әдісінің мақсаты мен идеясы

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

(3)

(4)

Мына мақсат функцияның ең үлкен (оптималдық) мәнін табу керек делік:
(5)
Біз жоғарыда симплекс әдісінің геометриялық мағынасын қарастырғанда, ең
алдымен және шектеуші шарттар бойынша М дөңес көпжақтысын құрып, оның бір
төбесін (есептің алғашқы базистік шешуін) тауып, сол төбедөн градиент
арқылы мақсат функция кемімейтіндей (егер есеп ең кіші мәнге берілсе мақсат
функция артпайды) етіп жылжыта отырып, ең үлкен мән беретін төбеге жетеміз
деген едік. Міне осы идеяны матиматика түрінде қарастырамыз.
және

теңсіздіктер берілгендіктен математика тілінде есептің анықталу аймағы
берілді деп есептейміз. Ал енді біз оптималдық төбеге қарай жылжу үшін ең
алдымен есептің барлық шектеуші шарттарын орындайтын алғашқы ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.