Сызықты программалау есебін сиплекс әдісімен шешу
КІРІСПЕ
1 Сызықты программалау есебін сиплекс әдісімен шешу.
1.1 Тірек жоспарлар құру: симплексті программалау есебі берілсін.
1.2 Тиімді жоспар іздеу тиімділік шарты
1.3 Симплекс әдісінің алгоритмі
2 Есептің қойылымы
Қорытынды
Қолданылған әдебиеттер
1 Сызықты программалау есебін сиплекс әдісімен шешу.
1.1 Тірек жоспарлар құру: симплексті программалау есебі берілсін.
1.2 Тиімді жоспар іздеу тиімділік шарты
1.3 Симплекс әдісінің алгоритмі
2 Есептің қойылымы
Қорытынды
Қолданылған әдебиеттер
Симплекс әдісі. Бұл әдістің мағынасы мынада әуелі 2,3 шарттарды қанағаттандыратын қандай да бір шешімді табамыз. Одан кейін белгілі тиімділік критериді пайдаланып, берілген есептің тиімді шешімін табамыз. Басқаша айтқанда есеп итерациялық әдіспен шешіледі. Яғни бір итерациядан 2-ші итерацияға көшкенде функцияның мәні кішірейе береді. Нәтижесінде есептің тиімді шешімі алынады. Шешімнің тиімділігі симплекс кесте арқылы тексеріледі.
Жүйелер теориясы әдістері-халық шаруашылығын тиімді басқару қажеттілігінен туған түрлі экономикалық, инженерлік есептерді шешуге бейімделген курс.
Әдетте экономикалық есептер қандай да болмасын кейбір өнімдерді, шикізаттарды үлестірумен байланысты болып келеді. Өнімдерді түрлі әдістермен бөлуге болады. Әдістер бір-бірінен тиімділігімен ажыратылады. Сондықтан экономикалық есептердің көп шешімдерінің ішінен жақсысын таңдау проблемалары туады. Үлестірудің ең жақсы варианты- тиімді аталады.
Осы сияқты есептер халық шаруашылығының әр саласында көптеп кездеседі. Химиялық өндіріс қалдықтарын тиімді пайдалану, өндіріс материалдарын тиімді шешу, кадрлары дайындау мен оларды орналастырудың тиімді жоспары және т.б.
Экономикалық есептерді экстремум анықтайтын математикалық есептермен байланыстыруға болады. Математикалық есептің шешімі- экономикалық есептің шешімі болады.1Қоғамдағы экономикалық процестердің математикалық аппарат (теңдеулер, теңсіздіктер) арқылы сипатталуы-экономика-математикалық модель деп аталады.Экономикалық процестерді сипаттайтын математикалық есептердің шешіміне талдау арқылы біз экономикалық жүйені зерттейміз.
Есептің шарттарын өзгерте отырып, экономикалық жүйенің түрлі шешімдерін алып, олардың ішінен ең пайдалысын таңдаймыз.
Экстременальды есептер мен оның шығару әдістері қолданбалы математиканың “математикалық программалау” деп аталатын саласында қарастырылады.
Жүйелер теориясы әдістері-халық шаруашылығын тиімді басқару қажеттілігінен туған түрлі экономикалық, инженерлік есептерді шешуге бейімделген курс.
Әдетте экономикалық есептер қандай да болмасын кейбір өнімдерді, шикізаттарды үлестірумен байланысты болып келеді. Өнімдерді түрлі әдістермен бөлуге болады. Әдістер бір-бірінен тиімділігімен ажыратылады. Сондықтан экономикалық есептердің көп шешімдерінің ішінен жақсысын таңдау проблемалары туады. Үлестірудің ең жақсы варианты- тиімді аталады.
Осы сияқты есептер халық шаруашылығының әр саласында көптеп кездеседі. Химиялық өндіріс қалдықтарын тиімді пайдалану, өндіріс материалдарын тиімді шешу, кадрлары дайындау мен оларды орналастырудың тиімді жоспары және т.б.
Экономикалық есептерді экстремум анықтайтын математикалық есептермен байланыстыруға болады. Математикалық есептің шешімі- экономикалық есептің шешімі болады.1Қоғамдағы экономикалық процестердің математикалық аппарат (теңдеулер, теңсіздіктер) арқылы сипатталуы-экономика-математикалық модель деп аталады.Экономикалық процестерді сипаттайтын математикалық есептердің шешіміне талдау арқылы біз экономикалық жүйені зерттейміз.
Есептің шарттарын өзгерте отырып, экономикалық жүйенің түрлі шешімдерін алып, олардың ішінен ең пайдалысын таңдаймыз.
Экстременальды есептер мен оның шығару әдістері қолданбалы математиканың “математикалық программалау” деп аталатын саласында қарастырылады.
1. И.Л. Акулич “Математическое программирование в примерах и задачах”. Издательство “Высшая школа” 1986
2.Ә.У. Қалижанова, Қ.Қ. Мустафина, Р.С. Алғожаева
Қаз ҰТУ 2003
3. Дж. Данциг. Линейное программирование, его обобщения и применение.- М.:Прогресс,1966.
4. Калихман И.Л Линейная алгебра и линейное программирование. – М.: Высшая школа, 1967.
2.Ә.У. Қалижанова, Қ.Қ. Мустафина, Р.С. Алғожаева
Қаз ҰТУ 2003
3. Дж. Данциг. Линейное программирование, его обобщения и применение.- М.:Прогресс,1966.
4. Калихман И.Л Линейная алгебра и линейное программирование. – М.: Высшая школа, 1967.
КІРІСПЕ
Симплекс әдісі. Бұл әдістің мағынасы мынада әуелі 2,3 шарттарды
қанағаттандыратын қандай да бір шешімді табамыз. Одан кейін белгілі
тиімділік критериді пайдаланып, берілген есептің тиімді шешімін табамыз.
Басқаша айтқанда есеп итерациялық әдіспен шешіледі. Яғни бір итерациядан 2-
ші итерацияға көшкенде функцияның мәні кішірейе береді. Нәтижесінде есептің
тиімді шешімі алынады. Шешімнің тиімділігі симплекс кесте арқылы
тексеріледі.
Жүйелер теориясы әдістері-халық шаруашылығын тиімді басқару
қажеттілігінен туған түрлі экономикалық, инженерлік есептерді шешуге
бейімделген курс.
Әдетте экономикалық есептер қандай да болмасын кейбір өнімдерді,
шикізаттарды үлестірумен байланысты болып келеді. Өнімдерді түрлі
әдістермен бөлуге болады. Әдістер бір-бірінен тиімділігімен ажыратылады.
Сондықтан экономикалық есептердің көп шешімдерінің ішінен жақсысын таңдау
проблемалары туады. Үлестірудің ең жақсы варианты- тиімді аталады.
Осы сияқты есептер халық шаруашылығының әр саласында көптеп
кездеседі. Химиялық өндіріс қалдықтарын тиімді пайдалану, өндіріс
материалдарын тиімді шешу, кадрлары дайындау мен оларды орналастырудың
тиімді жоспары және т.б.
Экономикалық есептерді экстремум анықтайтын математикалық есептермен
байланыстыруға болады. Математикалық есептің шешімі- экономикалық есептің
шешімі болады.1Қоғамдағы экономикалық процестердің математикалық аппарат
(теңдеулер, теңсіздіктер) арқылы сипатталуы-экономика-математикалық модель
деп аталады.Экономикалық процестерді сипаттайтын математикалық есептердің
шешіміне талдау арқылы біз экономикалық жүйені зерттейміз.
Есептің шарттарын өзгерте отырып, экономикалық жүйенің түрлі шешімдерін
алып, олардың ішінен ең пайдалысын таңдаймыз.
Экстременальды есептер мен оның шығару әдістері қолданбалы
математиканың “математикалық программалау” деп аталатын саласында
қарастырылады.
1 Сызықты программалау есебін сиплекс әдісімен шешу.
Сызықты программалау есебінің тиімді шешімі шешімдер көп жағынының бұрыштық
нүктелерімен, яғни әр қайсысы А...А векторлар жүйесінің m сызықты
тәуелсіз векторларымен анықталатын тірек жоспарларымен байланысты. Бұл
есептегі тірек жоспарларының саны С анық. m және n үлкен сандар
болғанда тірек жоспарларының барлығын тексеріп шығу өте қиын, сондықтан
тірек жоспарларының бірінен – екіншісіне белгілі бір тәртіппен ауысып
отыратын схема құру қажет. Симплекс әдісі осындай бір тірек жоспарларынан
бастап ақырлы есептеу қадамдарынан кейін тиімді жоспарларға әкелетін схема
болып табылады. Әр қадам сызықты функцияға оның алдынғы жоспардағы мәнге
қарағанда кіші ( үлкен ) мән беретін жоспарын анықтау болып табылады.
Есептеу процессі тиімді жоспар табылғанға дейін жалғаса береді. Есепті шешу
барысында симплекс әдісі есептің шешімі жоқ екендігін немесе шешімдер көп
бұрышында сызықты функцияның шектелмегендігін анықтап береді.
1. Тірек жоспарлар құру: симплексті программалау есебі берілсін.
Z = C X + ... C X (1)
(2)
(3)
Табу керек ең кіші ең үлкен мәнін.
Шектеулер жүйесінің алдыңғы m векторын бірлік векторлар деп есептейміз,
одан сызықты функцияны
(4)
Табу керек ең кіші ең үлкен мәнін.
(4) – і формуланың векторлық түрде жазылуы.
(5)
мұндағы:
, , , , ,
векторлары m өлшемді кеңістіктің сызықты тәуелсіз бірлік векторлары
сондықтан базистық айнымалылар ретінде таңдап бас айнымалылары
бірлік векторларын ескерсек алғашқы
(6)
жоспарын аламыз. Бұл жоспарға (7)
жіктеуі сәйкес. Мұндағы сызықты тәуелсіз демек құрылған алғашқы жоспар
тірек жоспар болып саналады. Алғашқы (6) жоспары екінші тірек жоспарға
өтетіндігін тексереміз векторы m өлшемді кеңістікте базис құрайды (5)
жүйедегі әр векторды базис векторларына бір жолмен жіктеуге болады. Яғни
(8)
Базиске кірмейтін векторы үшін
(9)
Жіктеудегі коэффициентінің ең болмаса 1 – і оң болсын (9) жіктеудің 2
жағында кез келген көбейтіп нәтижені (7) – ден мүшелеп алып тастасақ
онда
(10)
Егер ком – рі теріс болмаса ;
векторлары жоспар болып құрамына теріс таңбамен енетін
векторының компоненттері болғандықтан оң сандар болады. Сондықтан
құрамында тек оң үшін (11) орындалатындай
табу керек
(11) = шартын қанағат – н кез келген есептердің жоспарлары болады
демек жаңа тірек жоспарларын алу процессі базиске енетін векторды таңдап
базистен шығарылатын векторды анықтау керек. Базиске енгізетін векторды
анықтау үшін қолданылатын кретерии симплекс әдісінің негізгі элементі болып
саналады.
2. Тиімді жоспар іздеу тиімділік шарты
Сызықты программалау есебі (1) – (5) жоспарлары бар және оның әр жоспары
тәуелсіз онда (6) тірек жоспары үшін
(12)
(13)
, ал осы жоспарға сәйкес кез келген базис векторына жалғыз
ғана жіктелуі бар.
(14)
(15)
Мұндағы вектордың базис векторына j векторына жіктелуіндегі сәйкес
коэффициенттерді қойғаннан кейінгі сызықты функцияның мәні.
арқылы векторына сәкес сызықты функцияның коэффициентін
белгілесек мынадай теорема аламыз.
Теорема: Егер кез келген векторы үшін онда жоспары тиімді
емес шарты орындалатындай х жоспарын құруға болады.
Теорема: Егер кез келген онда тиімді емес шарты
орындалатындай х жоспарын құруға болады.
3. Симплекс әдісінің алгоритмі
(1)
(2)
(3)
№ базис С
базис ... ...
... ... 1
1 0 ... 0 0 ... 2
0 1 ... 0 0 ... l 0
0 ... 1 0 ... M 0 0 ... 0 1
...
M+1 0 0 0 ... 0 0
...
1. Бастапқы тірек (немесе базистік) жоспарын құрамыз қосымша теріс емес
айнымалылар енгізіп, теңсіздіктер жүйесіне теңдіктер жүйесіне көшеміз.
Қосымша теріс емес айнымалылары базистік болып табылады, себебі
(4),(5) теңдеулер жүйесінің коэффициентін құрылған мақсаттық соңғы М
бағанда сызықты тәуелсіз бірлік матрица демек осы бағандарға сәйкес келетін
теріс емес айнымалыларда базистік айнымалылар бағандарына бақлау
қосындыларын және тұратын симплекстік кесте құрамыз. Ол индекстік
деп аталады. Симплекс кестенің соңғы жолы қарама – қарсы таңбалармен
алынған сызықты форма коэфф толтырылады.
2. Құрылған жоспарға тиімділік шартының орындалуын тексереміз.
жоспары тиімді болу үшін индекстік жолдың барлық ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Симплекс әдісі. Бұл әдістің мағынасы мынада әуелі 2,3 шарттарды
қанағаттандыратын қандай да бір шешімді табамыз. Одан кейін белгілі
тиімділік критериді пайдаланып, берілген есептің тиімді шешімін табамыз.
Басқаша айтқанда есеп итерациялық әдіспен шешіледі. Яғни бір итерациядан 2-
ші итерацияға көшкенде функцияның мәні кішірейе береді. Нәтижесінде есептің
тиімді шешімі алынады. Шешімнің тиімділігі симплекс кесте арқылы
тексеріледі.
Жүйелер теориясы әдістері-халық шаруашылығын тиімді басқару
қажеттілігінен туған түрлі экономикалық, инженерлік есептерді шешуге
бейімделген курс.
Әдетте экономикалық есептер қандай да болмасын кейбір өнімдерді,
шикізаттарды үлестірумен байланысты болып келеді. Өнімдерді түрлі
әдістермен бөлуге болады. Әдістер бір-бірінен тиімділігімен ажыратылады.
Сондықтан экономикалық есептердің көп шешімдерінің ішінен жақсысын таңдау
проблемалары туады. Үлестірудің ең жақсы варианты- тиімді аталады.
Осы сияқты есептер халық шаруашылығының әр саласында көптеп
кездеседі. Химиялық өндіріс қалдықтарын тиімді пайдалану, өндіріс
материалдарын тиімді шешу, кадрлары дайындау мен оларды орналастырудың
тиімді жоспары және т.б.
Экономикалық есептерді экстремум анықтайтын математикалық есептермен
байланыстыруға болады. Математикалық есептің шешімі- экономикалық есептің
шешімі болады.1Қоғамдағы экономикалық процестердің математикалық аппарат
(теңдеулер, теңсіздіктер) арқылы сипатталуы-экономика-математикалық модель
деп аталады.Экономикалық процестерді сипаттайтын математикалық есептердің
шешіміне талдау арқылы біз экономикалық жүйені зерттейміз.
Есептің шарттарын өзгерте отырып, экономикалық жүйенің түрлі шешімдерін
алып, олардың ішінен ең пайдалысын таңдаймыз.
Экстременальды есептер мен оның шығару әдістері қолданбалы
математиканың “математикалық программалау” деп аталатын саласында
қарастырылады.
1 Сызықты программалау есебін сиплекс әдісімен шешу.
Сызықты программалау есебінің тиімді шешімі шешімдер көп жағынының бұрыштық
нүктелерімен, яғни әр қайсысы А...А векторлар жүйесінің m сызықты
тәуелсіз векторларымен анықталатын тірек жоспарларымен байланысты. Бұл
есептегі тірек жоспарларының саны С анық. m және n үлкен сандар
болғанда тірек жоспарларының барлығын тексеріп шығу өте қиын, сондықтан
тірек жоспарларының бірінен – екіншісіне белгілі бір тәртіппен ауысып
отыратын схема құру қажет. Симплекс әдісі осындай бір тірек жоспарларынан
бастап ақырлы есептеу қадамдарынан кейін тиімді жоспарларға әкелетін схема
болып табылады. Әр қадам сызықты функцияға оның алдынғы жоспардағы мәнге
қарағанда кіші ( үлкен ) мән беретін жоспарын анықтау болып табылады.
Есептеу процессі тиімді жоспар табылғанға дейін жалғаса береді. Есепті шешу
барысында симплекс әдісі есептің шешімі жоқ екендігін немесе шешімдер көп
бұрышында сызықты функцияның шектелмегендігін анықтап береді.
1. Тірек жоспарлар құру: симплексті программалау есебі берілсін.
Z = C X + ... C X (1)
(2)
(3)
Табу керек ең кіші ең үлкен мәнін.
Шектеулер жүйесінің алдыңғы m векторын бірлік векторлар деп есептейміз,
одан сызықты функцияны
(4)
Табу керек ең кіші ең үлкен мәнін.
(4) – і формуланың векторлық түрде жазылуы.
(5)
мұндағы:
, , , , ,
векторлары m өлшемді кеңістіктің сызықты тәуелсіз бірлік векторлары
сондықтан базистық айнымалылар ретінде таңдап бас айнымалылары
бірлік векторларын ескерсек алғашқы
(6)
жоспарын аламыз. Бұл жоспарға (7)
жіктеуі сәйкес. Мұндағы сызықты тәуелсіз демек құрылған алғашқы жоспар
тірек жоспар болып саналады. Алғашқы (6) жоспары екінші тірек жоспарға
өтетіндігін тексереміз векторы m өлшемді кеңістікте базис құрайды (5)
жүйедегі әр векторды базис векторларына бір жолмен жіктеуге болады. Яғни
(8)
Базиске кірмейтін векторы үшін
(9)
Жіктеудегі коэффициентінің ең болмаса 1 – і оң болсын (9) жіктеудің 2
жағында кез келген көбейтіп нәтижені (7) – ден мүшелеп алып тастасақ
онда
(10)
Егер ком – рі теріс болмаса ;
векторлары жоспар болып құрамына теріс таңбамен енетін
векторының компоненттері болғандықтан оң сандар болады. Сондықтан
құрамында тек оң үшін (11) орындалатындай
табу керек
(11) = шартын қанағат – н кез келген есептердің жоспарлары болады
демек жаңа тірек жоспарларын алу процессі базиске енетін векторды таңдап
базистен шығарылатын векторды анықтау керек. Базиске енгізетін векторды
анықтау үшін қолданылатын кретерии симплекс әдісінің негізгі элементі болып
саналады.
2. Тиімді жоспар іздеу тиімділік шарты
Сызықты программалау есебі (1) – (5) жоспарлары бар және оның әр жоспары
тәуелсіз онда (6) тірек жоспары үшін
(12)
(13)
, ал осы жоспарға сәйкес кез келген базис векторына жалғыз
ғана жіктелуі бар.
(14)
(15)
Мұндағы вектордың базис векторына j векторына жіктелуіндегі сәйкес
коэффициенттерді қойғаннан кейінгі сызықты функцияның мәні.
арқылы векторына сәкес сызықты функцияның коэффициентін
белгілесек мынадай теорема аламыз.
Теорема: Егер кез келген векторы үшін онда жоспары тиімді
емес шарты орындалатындай х жоспарын құруға болады.
Теорема: Егер кез келген онда тиімді емес шарты
орындалатындай х жоспарын құруға болады.
3. Симплекс әдісінің алгоритмі
(1)
(2)
(3)
№ базис С
базис ... ...
... ... 1
1 0 ... 0 0 ... 2
0 1 ... 0 0 ... l 0
0 ... 1 0 ... M 0 0 ... 0 1
...
M+1 0 0 0 ... 0 0
...
1. Бастапқы тірек (немесе базистік) жоспарын құрамыз қосымша теріс емес
айнымалылар енгізіп, теңсіздіктер жүйесіне теңдіктер жүйесіне көшеміз.
Қосымша теріс емес айнымалылары базистік болып табылады, себебі
(4),(5) теңдеулер жүйесінің коэффициентін құрылған мақсаттық соңғы М
бағанда сызықты тәуелсіз бірлік матрица демек осы бағандарға сәйкес келетін
теріс емес айнымалыларда базистік айнымалылар бағандарына бақлау
қосындыларын және тұратын симплекстік кесте құрамыз. Ол индекстік
деп аталады. Симплекс кестенің соңғы жолы қарама – қарсы таңбалармен
алынған сызықты форма коэфф толтырылады.
2. Құрылған жоспарға тиімділік шартының орындалуын тексереміз.
жоспары тиімді болу үшін индекстік жолдың барлық ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz