Сызықтық бағдарламалау есебін симплекстік әдіспен шешу
жүктеу/скачать 26,54 Kb.
|
3 Симплекс
|
1.3 Сызықтық бағдарламалау есебін симплекстік әдіспен шешу Сызықтық бағдарламалау есебінің аналитикалық шешу әдісі деп симплекстік әдісті айтады. Оны қолдану үшін әр түрдегі сызықтық бағдарламалау есептерін канондық түрге келтіру керек. Сызықтық бағдарламалаудың канондық есебі деп келесі есепті айтады: f(Х)=c1x1+c2x2+…+cnxn тепе-теңдіктер түріндегі келесі шектеулері бар: m Мақсатты функцияны максималдандыру есебінен минималдандыру есебіне көшу үшін мақсатты функцияның барлық теріс таңбалы сj коэффициенттерін алып, алынған есепті максимумге шешу керек. Максимумы табылғаннан кейін мақсатты функцияның мәнін теріс таңбамен алу керек. Оңтайлы шешім бұрынғысынша қалады. «Кіші немесе тең» түріндегі шектеуден тепе-теңдікке өту үшін қосымша «қосу» таңбасымен теріс емес айнымалыны енгізу керек: ai1x1+…+aijxj+…+ainxn≤bi => ai1x1+…+aijxj+…+ainxn+xn+i=bi «Үлкен немесе тең» түріндегі шектеуден тепе-теңдікке өту үшін қосымша «алу» таңбасымен теріс емес айнымалыны енгізу керек:ai1x1+…+aijxj+…+ainxn≥ bi => ai1x1+…+aijxj+…+ainxn- xn+i=bi Сөйтіп әр теңсіздікке өзінің (n+i)-ші қосымша айнымалы енгізіледі. Теріс бос мүшелері бар барлық теңдіктер (-1)-ге бөлінеді. Егер әлдебір xj айнымалысына теріс еместік шарты қойылса, онда келесі айнымалыларды алмастырады xj=xj’-xj”, xj’ ≥0, xj” ≥0. Түрлендірген есепте барлық айнымалылар теріс емес. Кез-келген сызықтық бағдарламалау есебін канондық түрге келтіруге болады деген пікір бар. Сызықтық бағдарламалаудың канондық есебінің жоспары немесе мүмкін болатын шешімі деп шектеулерді қанағаттандыратын X = (х1,х2,..., xn) векторын айтады. Егер сызықтық бағдарламалау канондық есебінің шектеулер жүйесінің базистік шешімінің барлық компоненттері теріс емес болса, онда бұл шешім тірек шешімі немесе тірек жоспары деп аталады. Тірек жоспарының оң компоненттерінің саны m-нан аспау керек. Тірек жоспары m оң компоненттерінен құралса, туындалмаған деп аталады, әйтпесе туындалған деп аталады. СБЕ барлық жоспарлар жиыны (егер олар бар болса) дөңес көпжақ болып табылады. Шешімдер көпжағының әр бұрыштық (шеткі) нүктесіне тірек жоспары сәйкес келеді (теңдеулер жүйесінің теріс емес базистік шешімдері). Оңтайлы жоспарды табу үшін тек тірек жоспарларын қарастыружеткілікті. mжәне n үлкен мәндерінде оңтайлы жоспарды барлық тірек жоспарларын іріктеу арқылы табу өте қиын. Сондықтан бір тірек жоспарынан келесісіне ретпен өтуге мүмкіндік беретін үлгі (схема) болуы қажет. Мұндай схема симплекстік әдіс болып табылады, ол бойынша есептің белгілі тірек жоспарынан санаулы қадам арқылы оңтайлы жоспарды алуға көмектеседі. Әр қадам (немесе итерация) алдыңғы жоспардағыдан үлкенірек мақсатты функцияның мәні сәйкес келетін жаңа тірек жоспарын табудан тұрады. Симплекс-әдіс екі есептеу процедурасынан тұрады: табиғи базисті; жасанды базисті. Табиғи базисті симплекс-әдісін қолдану үшін СБ канондық есебінің m дәрежелі бірлік подматрицасы болу керек, сол кезде бастапқы тірек жоспары айқын болады (СБ канондық есебінің шектеулер жүйесінің теріс емес базистік шешімі). Жасанды базисті симплекс әдісі СБ бастапқы канондық есебінің тірек жоспары жоқ кезінде қолданылады. Мұндай жағдай алғашқы шектеуде «тең» немесе «үлкен немесе тең» таңбалары болғанда орын алады. Симплекс әдісінің алгоритмі Есепті канондық түрге келтіру. Шектеулер жүйесінің теріс емес базистік шешімін табу. Бос айнымалылардың бағаларын келесі формулалар арқылы есептеу: мұндағы аij – xjбос айнымалысынң коэффициенттері, ci – мақсатты функциядағы базистік айнымалылардың коэффициенттері, cj – мақсатты функциядағыбос айнымалылардың коэффициенттері. Табылған тірек шешімін оңтайлылыққа тексеру: а) егер барлық бағалар Δj ≥0, онда табылған шешім оңтайлы және есеп шешілді; б) егер тым болмағанда бір баға Δj<0, ал тиісті xj айнымалысының бірде-бір оң коэффициенті болмаса, онда есептің мақсатты функцияның шектеусіздігіне байланысты оңтайлы шешімі жоқ; в) егер тым болмағанда бір баға Δj<0, ал тиісті xj айнымалысының тым болмағанда бір оң коэффициенті болса, онда табылған шешім оңтайлы емес және оны жаңа базиске өту арқылы жақсартуға болады. Егер теріс бағалар бірнеше болса, онда базиске теріс бағаның абсолюттік шамасы ең үлкен айнымалыны енгізу қажет. Ескерту 1. СБЕ минимумге оңтайлылық критерийі бағалардың оң еместігі болып табылады, яғни Δj<0, j= . Ескерту 2. СБЕ мақсатты функцияның максимум мен миниммумы глабальды деп есептеледі. Табиғи базисті симплекс-әдісі қолданылатын есепті қарастырайық. жүктеу/скачать 26,54 Kb. Достарыңызбен бөлісу:
|