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

445-0,955x464,78=1,12; 0,95-0,955x1,06=-0,06; 0-0,955x0=0; 0,955-0,955x1=0; 1-0x0,955=1; -0,05-0,955х0,14=-0,18; 0-0,955х0,7=-0,67. Мақсат функцияның жолы мына формула бойынша есептеледі: Ғ+284,25х3:47250+464,78x284,25=179366; -182,5+1,06x284,25=118,8; 0+0x284,25=0; 284,25+1x284,25=0; 0+0x284,25=0;

№	Базис	bi	X1	X2	X3	X4	X5	X6	Q
1	X3	464,788	1,06	0	1	0	0,14	0,7	3000
2	X2	114,08	0,002	1	0	0	0,044	-0,03	465,9
3	X4	1,12	-0,06	0	0	1	-0,18	-0,67	464,8
4	F	179366	118,8	0	0	0	57,3	199

17,5+284,25x0,14=57,3; . 0+0,7x284,25=199.     4-кесте

Соңғы кесте  бойынша оңтайлы шешім оңтайлы жоспарға сәйкес келеді:

Х₁=0, Х₂=114,08, Х₃=464,78, Х₄=1,12, Х₅=0, Х6=0, Ғ_mах=179366 тг.

Үшінші симплекс кестенің индекстік жолында теріс сандардың болмауы осы жоспардың оңтайлы екенін айғақтайды. Оған қызылша мен көкөністің егістіктері кірді, осы шаруашылық жағдайында 1 га-дан 200 теңге пайда алу үшін дәнді дақыл егу пайдасыз болып табылады, х₄ базистік айнымалы 1,12 га егістіктің пайдаланылмаганын көрсетеді. хі баған бойынша индекстік жолдың коэффициенттерінің оң белгісі бар. Олар дэнді дақылдардың бір гектары егістігінен түсетін таза кірістің сомасы қаншаға кемитінін көрсетеді. Қосымша белгісіздер бағандары х₅ жэне х₆ бойынша индекстік жолдың коэффициенттері 1 адам-күн (57,3 теңгеге) және 1 центнер тыңайтқыш (199 теңгеге) толық пайдаланылмаса, таза кірістің жалпы сомасы қаншаға кемитінін көрсетеді.

 

 

 

 

 

 

 

 

 

 

 

2.3. ЖАСАНДЫ БАЗИСТІҢ СИМПЛЕКС ӘДІСІ

Шектеулері (>=) таңбалы теңсіздіктермен берілген есептерде қосымша белгісіздер теріс бірлік коэффициенттермен енгізіледі, сондықтан олар табиғи базис құра алмайды. Осындай есеп эдебиетте М-әдіс деген атаумен кездесетін жасанды базистің көмегімен шешіледі. Жасанды базис әдісімен қатаң шектеулері, берілген теңсіздіктері бар есептер де шешіледі.

Шешім алгоритмін нақты мәселе мысалында  талдауға болады.

Есеп. Фирмада екі түрлі шикізаттан төрт түрлі өнім шығарылады. Мұның өзінде осы фирманың жағдайында ресурстың бірінші түрінің шығыны 9,4 бірліктен артық жұмсалынуы мүмкін, ал екінші түрді 987 көлемде толықтай пайдалану қажет. Бұл ретте сұраныс өнімнің бірінші түріне - 2,5 бірліктен, ал төртінші түрге - 5 бірлік. Өнім түрлері бойынша ресурстардың шығыны және оның өзіндік құны 5-кестенің мына деректерімен сипатталады.

5-кесте

Өнім	1-шикізат	2-шикізат	Өнім бірлігінің өзіндік құны
№1	1	100	3
№2	0,2	14	0,5
№3	0,12	9	1,4
№4	0,5	79	2,0

х₁, х₂, х₃, х₄ деп өнімнің түрлерін белгілейміз. Сонда есептің математикалық моделі теңдеулер мен теңсіздіктердің төмендегі жүйесімен жазылады:

Х₁+0,2х₂+0,12х₃+ 0,5х₄>= 9.4

100х₁+14х₂+ 9х₃+ 79х₄ = 987

Х₁<=2,5

х₄ <= 5.

Барлық  белгісіздер теріс емес болуға және сызықтық функция минимумға ұмтылады:

F_min = Зх₁+0,5х₂+1,4х_з+2х₄.

Есепте х₅, x_б, х₇ қосымша айнымалылардың көмегімен канондық түрге келтіріледі:

Х₁+0,2х₂+0,12х_з+ 0,5х₄ - х₅= 9.4 100х₁+14х₂ + 9х₃+ 79х₄ = 987

Х₁ + х₆ = 2,5

х₄ + х₇ = 5

Есепті шешу үшін аталмыш жүйенің табиғи базисі жоқ, сонымен бірге х₅ коэффициенті теріс, сондықтан ол базистік белгісіз ретінде бола алмайды, өйткені бұл жағдайда бастапқы жоспарда (-х₅) = 9,4 немесе х₅ = -9,4, ал белгісіз теріс бол-ғандықтан былай мүмкін емес. Екінші теңдеуде осы теңдеуге ғана тиесілі осындай айнымалы жоқ.

Бастапқы базистік шешім алу үшін осы теңдеулерге  бірлік оң коэффициенті бар у₁ және у₂ жасанды белгісіздер, ал мақсат функцияға - үлкен М бағамен енгізеді. Есеп максимумға шешілгенде ол теріс белгімен, ал минимумға шешілгенде оң белгімен енгізіледі. Осындай баға жоспарда жасанды белгісіздердің болуының пайдасын жоққа шығарады және олардың базистен шығарылуына ықпал етеді. Жасанды белгісіздер енгізілуіне байланысты модель мынадай болады.

x₁+0,2х₂+0,12х₃+ 0,5х₄ - х₅ + у₁=9.4 100х₁+14х₂+ 9х₃+ 79х₄ +у₂ =987

x₁ + х₆=2.5

х₄ +х₇ = 5

Барлық  белгісіздер теріс емес болуға тиіс, ал жазбаның сызықтық формасының түрі төмендегідей болады

F_min = 3х₁+0,5х₂+1,4хз+2х₄ +0х₅ + 0х_б + 0х₇ + Му₁ +Му₂.

Бірінші симплекс кестені жасаймыз. Бірінші  кестеде шек-теулер (>=) таңбада берілген жолдар бойынша базиске жасанды айнымалылар, ал (<=) шектеулері бар жолдарға қосымша айнымалылар енгізіледі.

Қолайлы болу үшін индекстік жол мына екі қатарға: m+1 және m+2 жазылады. Жоғарғы катарда функция коэффициенттері бағалары, ал төменгі М-бағалар болады. Бірінші кестеде m+2 жол бағандар коэффициенттерінің жолдары бойынша сәйкес келетін М-бағалардың көбейтінділерінің сомасы ретінде анықталады, m+1 жолға теріс белгісі бар функция коэффициенттері енгізіледі (6-кесте)

6-кесте

№	Базис	Ві	х1	х2	xз	х4	х5	х6	х7	у1	у2	Q
1	У1	9,4	1	0,2	0,12	0,5	-1	0	0	1	0	9,4
2	У2	987	100	14	9	79	0	0	0	0	1	9,87
3	Х6	2,5	1	0	0	0	0	1	0	0	0	2,5
4	х7	5,0	0	0	0	1	0	0	1	0	0
m+1	F	0	-3	-0.5	-1.4	-2	0	0	0	0	0
m+2		996.4М	101М	14.2М	9,12М	79,5М	-М	0	0	0	M	М

Жасанды базисі бар есепті шешу алгоритмі  табиғи базисі бармен бірдей болады. Тек бағыттаушы баған m+2 жол бойынша, яғни, индекстік жолдың төменгі қатары бойынша анықталады. Есеп  максимумға  шешілгенде  де  бағыттаушы  баған  теріс

мәндердің ішіндегі ең үлкен теріс мәні бойынша, ал минимумға  шешілгенде - ең үлкен оң мәні бойынша  анықталады. Табиғи базистегідей бағыттаушы жол еркін мүшелерді бағыттаушы бағанның сәйкес оң коэффициенттеріне бөлуден бастап ең аз бөлінді бойынша таңдалады. Қайта есептеудің барлығы табиғи базисі бар шешім алгоритміндегідей ережеге сәйкес жүргізіледі. m+1 және m+2 жолдар жеке есептеледі.

Оларды есептеудің дұрыстығы Ғ_j –С_j ретінде жалпы ережеге сәйкес m+1 бойынша, ал m+2 жол бойынша - М-бағалар бар жолдар бойынша баған коэффициентгерінің қосындысы бойынша анықталады.

Есептеу базистен жасанды белгісіздер толық  алып тасталғанға дейін жүргізіледі, сонда m+2 жолда барлық бағандар бойынша мәндері нөлге теңеледі, немесе минимумда m+2 жолының барлық мәндері теріс болады, ал максимумда оң болады.

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

Барлық  жасанды айнымалылар базистен шығарылғанда, сондай-ақ m+2 жолы бойынша нөлдік мәндері алынғанда негізге алынатын немесе оңтайлы жоспар есептеледі. m+1 жолдың элементтері оңтайлылық көрсеткіштері болады. Егер минимумда m+1 жолда оң мәндер, ал максимумда - теріс мәндер болса, онда бастапқы есептің негізге алынатын жоспары алынды деуге болады және оны табиғи базисі бар есепті шешкендегідей кәдімгі әдіспен жақсарту қажет.

Барлық  жасанды айнымалылар базистен шығарылған, m+2 жол бойынша нөлдер алынған, максимумда m +1 жолда нөлдер мен теріс мәндер алынған, ал минимумда - нөлдер мен оң мәндер алынған жағдайда жоспар оңтайлы болады.

6-кестеде х1 - бағыттаушы баған, ал үшінші  жол -бағыттаушы жол болады. Сондықтан екінші симплекс кестеде Х₆ базистен шығады, ал хі базиске енеді. 7-кесте табиғи базисі бар сияқты толтырылады.

7-кесте

№	базис	Ві	x1	x2	х3	х4	Х5	х6	х7	У1	У2	Q
1	Х1	2,5	1	0	0	0	0	1	0	0	0	-
2	х7	5	0	0	0	1	0	0	1	0	0	5
3	У1	6,9	0	0,2	0,12	0,5	-1	-1	0	1	0	13,8
4	У2	737	0	14	9	79	0	-100	0	0	1	9,3
m+1	F	7,5	0	-0,5	-1,4	-2	0	3	0	0	0
m+2		743,9М	0	14,2М	9,12М	79,5М	-м	-101M	0	0	0

3-кестенің m+2 индекстік жолының мәндері жоспарды одан әрі жақсартуға болатынын жэне базиске x₄ енгізу, ал x₇ шығару қажет екенін растайды.

8-симплекс кестеде  бағыттаушы баған - х₂, ал бағыттаушы жол - үшінші. Демек, базистен у₁ шығарылуға, ал оның орнына х₂ енгізілуге тиіс. У₁ базистен шығарылуына байланысты, у₁ баған келесі кестеде есептелмейді.

8-кесте

№	базис	Ві	Х1	х2	х3	х4	х?	х6	Х7	У1	У2	Q
1	х4	5	0	0	0	1	0	0	1	0	0	-
2	Хі	2,5	1	0	0	0	0	1	0	0	0	-
3	Уі	4,4	0	0,2	0,12	0	-1	-1	-0,5	0,5	0	22
4	У2	342	0	14	9	0	0	-100	-79	0	1	24,4
m+1	F	17,5	0	-0,5	-1,4	0	0	3	2	0	0
m+2		346,4М	0	14,2М	9,12М	0	-м	-101M	-79.5М	0	0