3.3 Симплекс кесте

Сызықтық программалау есебін компьютердің көмегімен шығаратын жағдайда симплекс әдісінің алгоритмін пайдаланған ыңғайлы, ал мұндай есептер компьютерсіз шығарылатын болса, симплекс кестені пайдаланған ыңғайлы болып саналады.

Сызықтық программалау есебін симплекс кестемен шығару алгоритмі

Сызықтық программалау есебінің максимумын анықтау керек болсын.

1. Қосымша айнымалыларды енгізгеннен кейін теңдеулер жүйесін және сызықтық функцияны бір жүйеге жаза отырып кеңейтілген жүйе деп аталатын мына түрдегі жүйені аламыз:

Алынған жүйедегі енгізілген қосымша айнымалылардың таңбасы жүйенің оң жағындағы бос мүшелердің таңбасымен бірдей болсын деп ұйғарамыз, кері жағдайда М-әдісін (жасанды базис әдісін) пайдаланамыз.

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

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

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

3.1. Егер тиімділік критерийі орындалмаса (кестенің соңғы жолында теріс коэффициенттер бар болса), онда кестенің соңғы жолындағы модулі бойынша ең үлкен теріс коэффициент шешуші бағанды анықтайды.

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

1. егер мен таңбалары әр түрлі болса, онда -ке тең болады;

2. егер және болса, онда болады;

3. егер болса, онда болады;

4. егер мен және болса, онда 0-ге тең болады;

5. егер мен таңбалары бірдей болса, онда қатынасымен есептеледі.

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

4. Келесі симплекс кестеге көшу үшін төмендегі ережелерді пайдаланамыз:

1. кестенің сол жақ бағанына жаңа базисті жазамыз: негізгі айнымалының орнына - айнымалыны жазамыз;

2. негізгі айнымалыларға сәйкес келетін бағандарға нөлдер мен бірлерді жазамыз: жолдағы айнымалы мен бағандағы айнымалы бірдей болса 1 санын, ал осы бағандағы басқа торларға 0 санын жазамыз:

3. нөмірлі жаңа жолды алдыңғы кестедегі осы жолдың элементтерін шешуші элементке бөлу арқылы аламыз;

4. қалған элементтерін тіктөртбұрыш ережесімен есептейміз:,

, .

Әрі қарай алгоритмнің 3 қадамына көшеміз.

2.6-мысал.

Симплекс кестені пайдаланып

,

шектеулеріндегі

сызықтық функциясының максимум мәнін табу керек.

Шығарылуы. Қосымша айнымалыларды енгізе отырып шектеулер жүйесін канондық түрге келтіреміз және кенейтілген жүйені жазамыз:

Бірінші симплекс кестені толтырамыз.

1-кесте

Базис	Бос мүше	Айнымалылар							Бағалау қатынасы
	14	-1	2	1	0	0	0	0
	34	1	4	0	1	0	0	0	34
	13	1	1	0	0	1	0	0	13
	5	1	-1	0	0	0	1	0	5
	8	1	0	0	0	0	0	1	8
	0	-3	-2	0	0	0	0	0

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

Төртінші жол - шешуші жол (ол жол да ерекше белгіленген). Шешуші жол мен шешуші бағанның қиылысуында шешуші элемент орналасқан.

2-кестені алгоритмнің 4-қадамындағы ережелер бойынша толтырамыз.

1. кестенің сол жақ бағанына жаңа базисті жазамыз: негізгі айнымалының орнына - айнымалыны жазамыз;

2. негізгі айнымалыларға сәйкес келетін аттас айнымалылар орналасқан бағандарға нөлдер мен бірлерді жазамыз (мысалы, негізгі айнымалыға сәйкес жолдың және аттас бағанның қиылысында 1 санын жазамыз, осы бағанның басқа торларына нөлдерді жазамыз);

3. төртінші жаңа жолды бірінші кестедегі осы жолдың элементтерін шешуші элементке бөлу арқылы аламыз;

4. кестенің толтырылмаған бос торларын (жұмыс бөлігін) тіктөртбұрыш ережесімен есептеп толтырамыз ( , мұндағы , , мәндерін 1-кестеден аламыз, , ; мысалы кестенің үшінші жолымен екінші бағанның қиылысуындағы торды толтыру үшін: , , , , , , сонда , т.т.):

2-кесте

Базис	Бос мүше	Айнымалылар							Бағалау қатынасы
	19	0	1	1	0	0	1	0	19
	29	0	5	0	1	0	-1	0	29/5
	8	0	2	0	0	1	-1	0	4
	5	1	-1	0	0	0	1	0
	3	0	1	0	0	0	-1	1	3
	15	0	-5	0	0	0	3	0

Соңғы жолда бір теріс элемент бар, сондықтан алынған шешім тиімді емес. Осыдан екінші баған - шешуші баған болып табылады. Бағалау қатынасы орналасқан бағанды толтырамыз. Нәтижесінде бесінші жол – шешуші жол болатынына көзімізді жеткіземіз. Осылайша келесі кестені толтырамыз.

3-кесте

Базис	Бос мүше	Айнымалылар							Бағалау қатынасы
	16	0	0	1	0	0	2	-1	8
	14	0	0	0	1	0	4	-5	14/4
	2	0	0	0	0	1	1	-2	2
	8	1	0	0	0	0	0	1
	3	0	1	0	0	0	-1	1
	30	0	0	0	0	0	-2	5

Алдындағы кестелерді толтырған алгоритмді пайдалана отырып келесі кестеге көшеміз:

4-кесте

Базис	Бос мүше	Айнымалылар							Бағалау қатынасы
	16	0	0	1	0	0	2	-1	8
	14	0	0	0	1	0	4	-5	14/4
	2	0	0	0	0	1	1	-2	2
	8	1	0	0	0	0	0	1
	3	0	1	0	0	0	-1	1
	30	0	0	0	0	0	-2	5

5-кесте

Базис	Бос мүше	Айнымалылар							Бағалау қатынасы
	12	0	0	1	0	-2	0	3
	6	0	0	0	1	-4	0	-13
	2	0	0	0	0	1	1	-2
	8	1	0	0	0	0	0	1
	5	0	1	0	0	1	0	-1
	34	0	0	0	0	2	0	1

Соңғы жолда теріс элемент жоқ. Яғни тиімділік критерийі орындалады.

Жауабы: , .

Симплекс кестені пайдаланып сызықтық программалаудың минимизациялау есебін шығару барысында да максимизациялау есебін шығарғанымыздағыдай қадамдарды орындаймыз. Тек өзгешелігі – тиімділік критерийінде. Максимизациялау есебінде біз соңғы ( мақсат функциясы орналасқан) жолда теріс элементтерінің болмауын талап етсек, минимизациялау есебінде соңғы жолда оң элементтің болмауын талап етеміз.