Симплекс әдісі

Қазақстан Республикасы Білім және Ғылым министрлігі

Тараз политехникалық колледжі

 

 

 

 

 

 

 

 

 

Курстық жұмыс

 

 

 

 

Тақырыбы:Симплекс әдісі.

 

 

Орындаған:Ділдебаева Марал

Қабылдаған: Битөреева  С.Б.

Тобы: 4ПВТ-3

Қорғалған күні:____________

Бағасы:_____________

 

 

 

 

 

 

 

 

 

 

 

Тараз 2012ж

 

 

 

МАЗМҰНЫ

 

 

I. Кіріспе..............................................................................................................

II. Негізгі бөлім...................................................................................................

2.1.Симплекс әдісі......................................................................................

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

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

2.4. Симплекс әдісінің алгоритмі.......................................

2.5.Тәжірибелік есептерді  симплекс әдісімен шығару..........................

III.Тапсырмалар...................................................................................................

IY. Қорытынды....................................................................................................

Пайдаланылған әдебиеттер................................................................................

 Қосымшалар.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Симплекс әдісі.

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

 

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

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

Z=

Z-кез-келген тұрақты мәнінде п-өлшемді гипержазықтық.

Симплекс әдісінін мән-жайын тереңірек  түсіну үшін, алдыңғы тақырыптағы  кейбір белгілі қағидаларды тағы да еске түсірейік. Мысалға, егер Z-дің мәні  -∞ тен +∞ дейін өзгерсе, онда гипержазықтық өзіне-өзі параллель жылжи отырып, М дөңес көпжақтыға жетеді де, онымен бір нүктеде қиылысады, бұл нүкте ену нүктесі делінетіні алдыңғы тақырыпта айтылды.  Гипержазықтықты және өзіне-өзін параллель етіп, М аймағы бойынша жылжыта берсек, Z-дің бір мәнінде, ол гипержазықтық М аймағының соңғы нүктесімен жанасады да, осыдан кейін М аймағынан шығып кетеді.

Бұл түсініктерден кейін симплекс әдісінің геометриялық мағынасына қысқаша  тоқталайық.

 

 

 

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

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

Енді Z-дің алғышқы графигін тәжірибе жүзінде қалай құратынын түсіндірейік. Ол үшін екі белгісізі бар есепті қарастырайық:

Z=CX1+CX2

Егер Z=d=0 десек алдағы Z=CX1+CX2 теңдеудің графигі координат өсінің бас нүктесінен өтетінін байқаймыз. Бірақ бір нүкте арқылы шексіз теңдеулер жүргізуге болады деген геометриялық теорема бойынша олардың ішінен бізге қажетті біреуін ғана тауып алу қажет. Оны табу үшін, қарастырылып отырған түзу сызық X1 және X2 өстерімен қандай бұрыш жасайтынын анықтау керек, яғни Z(X1,X2) –функциясының градиентін іздеу қажет, сонымен қатар табылған градиент, осы түзу сызықтық бойынша алынған дербес туындылар.

Z(X1,X2) функциясының X1 және X2 белгісіздері бойынша сызықтық функция болғандықтан:

Z(X1,X2)/X1=C1,    Z(X1,X2)/X1=C2     деп есептеп, градиентті былай өрнектейік:

gradZ(X1,X2)=c1e1+c2e2

 

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

|gradZ(X1,X2)= (∂Z/∂X1)* (∂Z/∂X1)+ ( ∂Z/∂X2)*(∂Z/∂X2)=C1*C1+C2*C2

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

n(C1,C2)=n(∂Z/∂X1, ∂Z/∂X2)

               

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

Симплекс – ағылшын  сөзі, кеңістіктегі қарапайым көпбұрышты көпжақты бейне, оның бұрыштарының координаттары ізделініпотырған белгісіздердің оптималды мәндеріне сәйкес. Көп өлшемді геометрияда: Х1+Ч2+...+Хn=1, X1>=0, X1>=0,... Хn>0 шарттарын қөанағаттандыратын А(X1,X2,... Хn) нүктесінің геометриялық орны симплекс делінеді.

Симплекс әдісінің негізгі  мақсаты, егер мақсат функциясы максимумге ізденілсе, онда алғашқы табылған төбеден  келесі төбеге жылжығанды кез-келген төбеге емес, мақсат функциясының мәні өсетін төбеге жылжуды қамтамасыз ету.

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

Жалпы математикалық  бағдарламалау пәні-өмірдің қателігінен  пайда болған қолданбалы математиканың  ең негізгі бөлімі. Жоғарыда айтылғандай, математикалық бағдарламалаудың ішіндегі барлық халық шаруашылығына көп  таралғаны, әртүрлі әдістері терең зерттелген бөлімі сызықтық бағдарламалау әдістері болып есептелінеді. Математикалық бағдарламалау пәнінің ең негізгі бөлімі сызықтық бағдарламалау есептері дүние жүзінде бірінші рет 1930 жылдары жарық көрді. Сызықтық бағдарламалау есептері басқа тәжірибелік есептерге қарағанда өте қарапайым , зерттеуге ыңғайлы.

Сызықтық бағдарламалаудың дербес есебінің бірі- қатынас есебінің дербес түрі 1931 жылы Венгрияда басылып  шықты, бұл мақаланың авторы математик  Эгервари болатын. Кейінерек келе, бұл  мақаланың негізінде бірнеше еңбектер жазылды. Бұған мысал үшін 1951 және 1956 жылдары жарыққа шыққан Х.В.Кун және В.Таккер еңбектерін, 1957 жылы жазылған Х.Р.Форд және Д.Р.Фалкерсон еңбектерін алуға болады. Бұл еңбектерде қатынас есептерін шешуге арналған әдістер көрсетілген, кейін келе әдебиеттерде бұл әдісті қатынас есептерін шешудегі Венгер әдісі дейтін болады.

Сызықтық бағдарламалау атты термин алғаш рет 1940 жылы АҚШ-та қолданылды. Сызықтық бағдарламалау әдісінің арнгайы есептерінің бірі 1941 жылы АҚШ-та басылып шықты, оның авторы Ф.Л. Хичкок болатын.

1939 жылы бұл әдісті  біртіндеп жақсарту әдісінен айырмашылығы өте аз болатын. Өкінішке қарай, бұл әдісті Л.В.Канторович бұрын ұсынса да көптеген әдебиеттерде, оқулықтарда симплекс әдісін Дж.Данциг әдісі деп атайды.

 

 

 

 

Симплекс әдісінің алгоритмі.

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

       а11X1+а12X12+...+а1nXn<=b1

       а21X1+а22X2+...+а2nXn<=b2

       аr1X1+аr2X2+...+аmXn<=br

        аm1X1+аm2X2+...+аmnXn<=bm

 

Мына мақсат функциясының  ең үлкен (оптималдық) мәнін табу керек делік:

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

(4.3)  және  (4.4)  теңсіздіктер берідгендіктен, математика тілінде  есептің анықталу  аймағы берілді деп есептейміз.  Ал енді  бізге оптималдық төбеге қарай  жылжу үшін, ең алдымен есептің барлық шектеуші  шарттарын орындайтын  алғашқы шешуді табу керек. Ол үшін (4.3) теңсіздіктердің  әрқайсысының сол жағына уі, (і=1,2,…,m) санын қосып, теңдікке айналдырамыз.

       а11X1+а12X12+...+а1кXк+ а1nXn+у1=b1

       а21X1+а22X2+...+а2кXк+ а1nXn+у1<=b2

       аr1X1+аr2X2+...+а1кXк+ а1nXn+у1<=br

        аm1X1+аm2X2+...+а1кXк+ а1nXn+у1<=bm

Экономикалық  мағынада У1, У2, ..., Уm-дер сәйкес 1,2,...  және m-ші қордың қолданылмаған (өндіріске түспеген)  мөлшерін береді. Егер есепті шешу нәтижесінде Y1=0, Y1=0, Ym=0  болса, онда барлық қорлар толығымен өндірісте  қолданылған.  Бірақ іс жүзінде барлық  қордың берілген мөлшері бірден толық пайдаланылмауы да мүмкін. Ал Y1, Y2,.. Ym – пайдаланылмаған қордың мөлшерін беретіндіктен, өндіріске еш пайда келтірмейді, демек мақсат функциясында олардың (Y1, Y2,.. Ym) коэффициенттері нөлге тең болады, яғни:

Z(X1, X2, …,Xn)=C1X1+C2X2+…+CnXn+0Y1+0Y2+…+0Ym

Сонымен есеп (4.3) және (4.4)  шарттар  орындалған жағдайдағы (4.5) функцияның  ең үлкен мәнін беретін шешуді іздеуге  бағытталған. Егер (4.3) теңдікті  У1(1=1,2,..., m)  арқылы шешетін болсақ:

 

Мұндағы   Y1, Y2,.. Ym      белгісіздері  математика тілінде базизтік белгісіздер деп, ал Х1, Х2,.. Хп -  базистік емес белгісіздер деп аталады. Демек, базистік белгісіздер (векторлар)  базистік емес белгісіздер арқылы өрнектеледі. Олай болса, геометриялық мағынадағы симплекс әдісінің мақсаты бір төбеден екінші төбеге көшу дегеніміз бір базистік белгісізден екінші базистікбелгісізге көшу керек  деген ұғыммен сәйкес.  Егер Х1=0, Х2=b2,…Ym=bm   шығады.

Экономикалық мағынасы bi, (1=1,2,..., m) қолда бар қордың мөлшері болғандықтан, әрқашанда bi>=0,  (1=1,2,..., m), ендеше  Yi>=0, Yj>=0, Yi=bi>=0 деген жағдай (4.3) және (4.4) теңдеулерінің шешімін береді, бұл жағдайда мақсат функциясының мәні нолге тең (Z=0), өйткені әлі ешқандай өнім өндірілген жоқ. Олай болса, Хj=0, Yi= bi>0 шешу жағдайы есептің алғашқы шешімі бола алады. Демек, алғашқы төбе табылды, енді мақсат функциясының мәні кемімейтін келесі төбеге көшу керек. Бұл идеяны математикалық жолмен түсіндіру біраз қиынға түседі, ол үшін біз оны кесте түрінде түсіндірелік. Негізінде, сызықтық бағдарламалау есептерінің бір кестеден екінші кестеге, одан үшіншіге т.б. кестелерге көшу арқылы табылады. Латынша мұндай әрекетті Итерация , яғни бір әрекетті қайта-қайта қайталау дейді.

Ақырғы теңдеулер арқылы симплекс-кесте құрылады. Кестеде 1-ші жолға әр тік графаларға негізгі айнымалылардың белгілері және соғңы тік графаға бос мүшелердің белгісі жазылды. Сонымен қатар бірінші жолдың сол жағындағы бірінші торджа № белгісімен әр Итерацияның графаларға базистік айнымалылардың белгілері, ал ақырғы жазық графаға мақсат функциясының белгісі жазылды. Кесте айнымалыларының коэффициенттерімен, бос мүшелермен толтырылады, яғни өздерінің орындарына сәйкес торларға жазылады. Симплекс кестесінің ақырғы жолын индекстік немесе мақсат функциясының жолы деп аталады.

 

№i	X 1	X 2	…	X k	X k+1	…	X n	bi
y 1	a11	a12	…	a1k	a 1k+1	…	a1n	b1
Y 2	a21	a22	…	a2k	a2k+1	…	a2n	b2
…	…	…	…	…	…	…	…	…
Y m	am1	am2	…	amk	amk+1	…	a mn	bm
mZ	-C1	-C2	…	-Ck	-Ck+1	…	-Cn	0