Симплекс ұғымы.
Сызықтық бағдарламалауда к.к. есебін шешетін Симплекс әдісі болып табылады. Қазіргі кезде қиын емес есептерді симплекс тәсілімен қолмен есептеп шығаруға болады. Симплекс тәсілінің негізінде берілген көпбұрыштығ төбелері тізбекті өтуде. Көпбұрыштың төбелерінің өтуі шектеулер жүйесі көмегімен жүзеге асырылады. Симплекс әдісінің алгоритмі:\
Егер шектеулер жүйесі теңсіздік түрінде берілсе, онда оны теңдік түріне келтіреміз.
Базисті және базисті емес айнымалыларды тандаймыз. Мақсатты функцияда айнымалылары бар айнымалыларды базисті емес деп атаймыз. Басқалар базисті.
1-нші Симплекс кестені толтырамыз. Шектеулер жүйесінің коэфиценттері өз таңбасымен, ал мақсатты функцияның коэфиценттері қарама-қарсы таңбамен енгізіледі.
F(x)=2X1+3X2
F(x)=-2X1+3X2
Тиімді критерий бойынша кестені бағалаймыз.Егер мақсатты функция жолында теріс элементтер жоқ болса, онда функция экстремумына жетті деп санаймыз және табылған шешімді тиімді деп санаймыз да есептеулерді тоқтатамыз.
Тиімді критерий орындалмаса, онда шешуші бағанды табамыз. Ол үшін мақсатты фнукцияның коэфицентінен ең үлкен абсолютті санды табамыз. Сол баған шешуші баған болып табылады.
Шешуші баған бойынша бағалау қатынастарды есептейміз. Ол үшін бос мүшенің шешуші бағаның сәйкес келетін элементеріне бөлеміз. Шыққан сандардан ең кіші оң санын табу керек. Сол жол шешуші жол болып табылады.
Шешуші бағанмен жолдың қиылысында тұрған элементті шешуші элемент деп атаймыз. Оны 1-ге келтіреміз. Шешуші бағанның бойында тұрған басқа элементерді 0-ге келтіреміз. Кейінгі 4 қадамға ораламыз.
Тиімдік критерий орындалған кезде тиімді шешімді табамыз. Базисті емес айнымалыларды 0-ге теңейміз. Базисті айнымалырадың мәні 1-ге сәйкес келетін бос мүшенің мәніне тең.
Мысал: F(x)=2x1+3x2->max
X1+3X2≤18
2X1+X2≤16
X2≤5
3X1≤21
x
1+3x2+x3=18
Базисті
емес = x1,x2
2x1+x2+x4=16 Базисті = x3,x4,x5,x6
x2+x5=5
3x1+x6=21
Базисті |
Бос мүше |
Айнымалылар |
Бағалау қатынастары |
|||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
||
x3 |
18 |
1 |
3 |
1 |
0 |
0 |
0 |
16/3=6 |
x4 |
16 |
2 |
1 |
0 |
1 |
0 |
0 |
16/1=16 |
x5 |
5 |
0 |
1 |
0 |
0 |
0 |
0 |
5/1=5 |
x6 |
21 |
3 |
0 |
0 |
0 |
0 |
0 |
21/0=∞ |
F |
0 |
-2 |
-3 |
0 |
0 |
0 |
0 |
|
Базисті |
Бос мүше |
Айнымалылар |
Бағалау қатынастары |
|||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
||
x3 |
3 |
1 |
0 |
1 |
0 |
-3 |
0 |
3/1=3 |
x4 |
10 |
2 |
0 |
0 |
1 |
-1 |
0 |
11/2=5,5 |
x5 |
5 |
0 |
1 |
0 |
1 |
1 |
0 |
5/0=∞ |
x6 |
21 |
3 |
0 |
0 |
0 |
0 |
1 |
21/3=7 |
F |
15 |
-2 |
0 |
0 |
0 |
3 |
0 |
|