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

Барлық осы  сандар жаңа симплекс кестеде жазылады.

6)Табылған жаңа базистің оңтайлылығын тексеру. Егер жоспар оңтайлы болмай, жаңа оңтайлы жоспарға көшу қажет болса, онда 4) кезеңге қайта оралады, ал оңтайлы жоспар алынған жағдайда, есептің шешімі қабылданады.

 

СИМПЛЕКС  ӘДІСІМЕН ЕСЕП ШЫҒАРУ

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

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

Есептің мақсаты. Дәнді дақылдардың, қант қызылшасының және күнбағыс егістіктерінің қандай үйлесімі фермерге пайда әкелетінін анықтау қажет.

Есептің шешуі. Бастапқы деректер 1-кестеде келтірілген.

1-кесте

Ауыл шаруашылығы  дақылдары	Еңбек шығындары, адам-күн тыңайтқыш ц.		1 га-дан түсетін  пайда, а.б
Дәнді дақылдар                     Қызылша Күнбағыс	1 20 0,9	1,7 4 1,6	200 350 300

 

Есептің шешімі экономикалық – математикалық модельді құрудан  басталады. Бұл үшін экономикалық терминдерде  қалыптастырылған есептің шартын математикалық  формада жазамыз.       Төмендегі белгілерді енгіземіз:

Х₁-дәнді дақылға бөленген егістік көлемі, га

Х₂-қызылшаға бөлінген егістік көлемі, га

Х₃-күнбағысқа бөлінген егістік көлемі, га

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

                                    

 

                                             

Мақсат функциясы  ауыл шаруашылығы дақылдарын сатудан  түсетін жалпы пайданың максимумы  болып табылады.

Z_min=200Х₁+350Х₂+300Х₃, (5.16)

сондай-ақ мәселенің экономикалық мағынасынан олардың айнымалылардың теріс емес шарты керсетіледі, яғни,

 

Х, 0, Х2 0, Х3                      (5.17)

Шектеулер  жүйесіне   (5.15)-(5.17)  теріс  емес   қосымша  айнымалылар енгізе отырып, канондық түрге айналдырамыз

                                                 

                                                   

                                                                (5.18)

 

Х₄, Х₅, Х₆ қосымша айнымалылар - егістіктің (Х₄), еңбек ресурстарының (Х5) және тыңайтқыштардың (Х6) экономикалық жағынан сәйкес толықтай пайдаланбағанын білдіреді.

Толықтай пайдаланылмаған  ресурстар ешқандай кіріс әкелмейді және сондықтан қосымша айнымалылар мақсат функцияға нөлдік коэффициенттермен енгізіледі:

Z_mах=200Х₁+350Х₂+300Х_з+0Х₄+0Х₅+0Х₆

Симплекс әдіс бірінші (бастапқы) базистік шешімді  тапқанда да, сондай-ақ басқа базистік шешімдерге көшкенде де белгілі алгоритм қолданылады.

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

Қарастырылған есептің бірінші базистік шешімін  табамыз.   Нөлге тең 6-3=3 айнымалысы бар шешімді табу қажет. Қосымша айнымалылардың коэффициенттері бірлік матрица құрайтынына назар аударамыз. Сондықтан негізгі айнымалылардың мәндерін нөлге тең (х₁=0, х₂=0, х₃=0) деп қабылдасақ, онда бірінші базистік жоспарды аламыз: х₄=580, х₅=2700, х₆=1200, Ғ=0.

Осы жоспар өнім шығарылмайтын, ресурстар пайдаланылмайтын және пайданың мөлшері нөлге тең жағдайға сәйкес келеді. Бұдан жоспардың пайдасыз екені анық көрінеді. Пайда алу үшін жоспарға қосымшалардың орнына оңтайлы шешім алынғанға дейін негізгі айнымалыларды енгізу қажет.

Есептеулер  жүргізуге қолайлы болу үшін есептің  моделі кестеде біршама өзгертілген түрде ұсынылған. Одан арғы шешімді 2-кесте түрінде ұсынамыз.

2-кесте

№	базис	bi	X1	X2	X3	X4	X5	X6	Q
1	X4	580	1	1	1	1	0	0	580
2	X5	2700	1	20	0.9	0	1	0	135
3	X6	1200	1.7	4	1.6	0	0	1	300
4	F	0	-200	-350	-300	0	0	0

 

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

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

Ғ – 200х₁, - 350х₂ – З00х_з - 0х₄- 0х₅- 0х₆ =0

Соңғы жол бағалау немесе индекстік болып табылады. Екінші бағанда базистік айнымалылардың атаулары жазылады. Үшінші бағанда базистік айнымалылардың өздері, яғни жоспардың өзі орналасады. Негізгі айнымалылардың коэффициенттері – ресурстар шығынының нормасы. Қосымша айнымалылардың коэффициенттері бірлік матрица құрайды. Базиске кіретін айнымалыларға коэффициенттер матрицасында әрқашан баған векторлар сәйкес келетінін атап өту қажет.

Есеп максимумге шешкенде индекстік жолда теріс  сандардың болмауы жоспардың  оңтайлылығының белгісі болып табылады. Ал есеп минимумге шешкенде индекстік жолда оң сандар болмауға тиіс.

Бірінші симплекс кестенің индекстік жолында теріс коэффициенттер бар. Демек, жоспар оңтайлы емес, оны жақсарту қажет.

Жаңа базистік жоспарға көшу симплекстік жаңарту деп аталады.

Есеп максимумге шешілгендіктен, дақылдар егістігінің жоспарына  барынша көп пайда түсіретін дақылдарды енгізген орынды. Бүл үшін индекстік жолда абсолюттік шамасы бойынша барынша үлкен теріс санды табамыз. Бұл сан - 350 жэне ол х₂ бағанда орналасқан. Ол егістік жоспарына қызылшаны енгізу 1 га-дан 350 теңге пайда түсетінін көрсетеді. Базиске енгізу қажет х₂ айнымалы бар баған бағыттаушы (рұқсат беруші, жетекші, бас, негізгі, өзекті және т.б.) деп аталады.

Енді қызылшаның егістігі қандай көлемде қарастырылуы мүмкін екенін анықгау қажет. Бұл ресурстар мөлшері мен шығын нормативіне байланысты болады. Бос мүше бағанын (ресурстар көлемі) бағыттаушы бағанның сәйкес оң коэффициенттеріне бөлеміз:

580/1=580га;     2700/20=135 га;     1200/4=300 га. (5.19)

Қатынастар (5.19) симплексті деп аталады. Олардың барынша аз шамасы қызылшаның егістігін 135 га-дан аспайтын мөлшерде жоспарлауға болатынын көрсетеді. Еңбек ресурстары қызылша егістігінің мөлшерін шектейтін «осал» жері болып табылады.

х₂ айнымалыны базистік айнымалының бірі нөлге тең болатындай етіп жоспарлау қажет (базистен х2-ге орын босату керек).

Егер 135 га қызылша егілсе, онда еңбек ресурстары толықтай пайдаланылады, х₅ нөлге теңеледі және оны базистен шығару қажет. Сөйтіп, барынша аз симплекстік арақатынас еркін болатын айнымалыны анықтаймыз. Оған сәйкес жол бағыттаушы деп аталады. Олардың түйісуіндегі элемент бағыттаушы деп аталады. Кестеде ол ерекшеленеді.

Енді екінші симплекс кестені, яғни екінші базистік жоспар құруға көшеміз. Басында х₅ орнына базистік айнымалылар қатарына х₂ енгіземіз, ал қалған базистік айнымалылар өзгермейді. Жоспардың жаңа нұсқасына көшкенде базиске тек қана бір айнымалыны енгізуге және оған сэйкес біреуін шығаруға болады.

Теңдеулер жүйесін  енгізілетін х₂ айнымалының бірлік баған векторы болатындай етіп түрлендіру қажет. Бұл үшін алдымен енгізілетін айнымалының жолын былай есептейміз. Ол бірінші симплекс кестенің бағыттаушы жолынан оның барлық элементтерін бағыттаушы элементке, яғни 20 санына бөлу аркылы алынады.

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

2700:20=135;   1:20=0,05;   20:20=1;   0,9:20=4,045;   0:20=0; 1:20=0,05;    0:20=0.

Кейінгі кестедегі  бағыттаушы баған бойынша рұксат беруші элементтің орнына бір, ал басқа  элементтердің орнына нөлдер қойылады. Барлық калған коэффициенттер былай  есептеледі:

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

Мысалы, х₄ жол х₄-х₂^н формула бойынша толтырылады, сонда төмендегі аламыз:

580-135=445;   1-0,05=0,95;  1-1=0;   1-0,045=0,955;   1-0=1;

0-0,05= -0,05; 0-0=0.

Ал х₆ жолды х_б-4х₂^н формуласы бойынша аламыз,

1200-4x135=660;   1,7-4x0,05=1,5; 4-4=0;   1,6-4x0,045=1,42; 0-0;

0-4х0,05=-0,2;    1-4x0=1.

Мақсат функцияның жолы Ғ+350х₂ формула бойынша толтырылады; сонда 0+135x350=47250 аламыз; -200+350x0,05=--182,5; -350+350x1=0;    -300+350х0,045=-284,25; 0+350x0=0; 0+350x0,05=17,5; 0-0=0. Алынған коэффициенттерді 3-кестеде

жазамыз.

3-кесте

 

№	базис	bi	X1	X2	X3	X4	X5	X6	Q
1	X4	135	0,05	1	0,045	0	0,05	0	3000
2	X5	445	0,95	0	0,.955	1	-0,05	0	465,9
3	X6	660	1,5	0	1,42	0	-0,2	1	464,8
4	F	47250	-182,5	0	-284,25	0	17,5	0

 

 

Оны жасағаннан кейін жоспардың оңтайлылығы тексеріледі. Индекстік жолда теріс сандардың болуы шешімнің оңтайлы еместігін - оны жақсарту қажет екенін айғақтайды. Бү_л үшін бірінші кестеден екіншіге көшкенде әзірленген есептеу тәртіптемесі қайталанады.

Бағыттаушы баған мен бағыттаушы жол тағы да іздестіріледі, содан кейін үшінші симплекс 4-кесте есептеледі. х₃ (-284,25) бағыттаушы баған жэне х₆ (464,8) бағыттаушы жол болып табылады.

Мысалы, Хз жол былай есептеледі: х₆:1.42, сонда төмендегіні аламыз

660: 1,42 =464,788; 1,5:1,42=1,06; 0:1,42=0; 1,42:1,42=1; 0:1,42=0;    -0,2:1,42=-0,14;    1:1,42=0,7.

Ал х₂ жолды х₂-0,045х₃ формула бойынша аламыз:

135-464,78x0,045=114,08;    0,05-1,06x0,045=0,002;     1-0x0,045=1;

0,045-1x0,045=0; 0-0x0,045=0; 0,05-0,14x0,045=0,044; 0-0,7х0,045=-0,03. х₄ жолды х₄-0,955х₃ формуласы бойынша есептеп, төмендегіні аламыз: