3 Тақырып. Симплекс-әдісі
НЕГІЗГІ ТҮСІНІКТЕР
СП есептерінің шешімін табу үшін бірнеше әдістер қолданылады. Олардың ішінде кең тараған графиктік әдіс және симплекс әдісі.
Графиктік әдіс есептің геометриялық мәнінде негізделген және көбінесе екіөлшемді жазықтық есептерін шешуде қолданылады.
Симплекс әдісі – сызықты программалау есептерінің барлық өлшемді түрлерін есептеуге пайдаланатын әдіс. Егер де СП есебіне айнымалылар саны өтек өп болса, бұл жағдайда компьютерлік программалар арқылы есептің тиімді шешімін табады. Мысалы, Excel көмегімен.
Сызықтық программалау есептерінің ең тиімді жоспарын симплекс әдісімен табу үшін мына қадамдарды орындау қажет:
Есепті негізгі түрге келтіру.
Шектеулер жүйесінің теріс емес базисті шешімін анықтау.
Бос айнымалылардың бағаларын есептеу ∆j=∑cihij-cj, j=1,n, мұнда hij – бос айнымалылардың алдындағы коэффициенттер хj, ci- мақсатты функциядағы базисты айнымалылардың коэффициенттері, cj – мақсатты функциядағы бо айнымалының коэффициенті.
Табылған тірек шешімді тиімділік шартына тексеру:
А) егре барлық бағалар ∆j≥0, онда табылған шешім тиімді және есептің шешімі табылды деп айтуға болады
Б) егер де бір ғана баға ∆j<0, ал сәйкесінше айнымалының коэффициенттерінің ішінде оң сан болмаса, онда есептің тиімді шешімі жоқ деп айтуға болады
В) егер де бір ғана баға ∆j<0, ал сәйкесінше айнымалының коэффициенттерінің ішінде бір ғана оң сан болса, онда табылған шешім тиімді емес, және басқа базисты таңдап, оны жақсартуға болады. Егер де теріс бағалар бірнеше болса, онда базис ретінде бағалардың абсолютті мәні ең жоғары көрсеткіш арқылы айнымалыны таңдаймыз.
1. Ескерту. СПЕ минимумға ұмтылатын жағдайда тиімділік критериі ретінде бағалардың терістігі саналады.
2. Ескерту. СПЕ мақсатты функция максимумы және минимумы жалпы болып саналады.
Мысал 3.1
Берілген СП есебін симплекс әдісімен шешу.
F=2,4X1+1,6X2→max
0,8X1+1,6X2+X3=4,8
1,6X1+0,8X2+X4=6,4
X2+X5=2
X1,X2,X3,X4,X5≥0
Шешімі:
Теңдіктер жүйесін векторлық түрде жазамыз.
i=1,3
Х1,Х2,Х3,Х4,Х5 векторлар арасында 3 бірлік векторлар болғандықтан, есептің бастапқы тірек жоспарын жазуға болады.
Хт=(0;0;4,8;6,4;2)
Бастапқы тірек жоспарын тиімділік шарытан тексереміз, ол үшін бірінші симплекс кестені құрастырамыз:
1 кесте
Базис
|
Сб
|
В
|
Х1↓
|
Х2
|
Х3
|
Х4
|
Х5
|
Q
|
2,4
|
1,6
|
0
|
0
|
0
|
Х3
|
0
|
4,8
|
0,8
|
1,6
|
1
|
0
|
0
|
6
|
←Х4
|
0
|
6,4
|
1,6
|
0,8
|
0
|
1
|
0
|
4
|
Х5
|
0
|
2
|
0
|
1
|
0
|
0
|
1
|
-
|
∆j
|
0
|
-2,4
|
-1,6
|
0
|
0
|
0
|
|
Достарыңызбен бөлісу: |