3.1 Сызықтық программалау есебін шығарудың жалпы идеясы
Симплекс
әдістің аталуы ол алғашқы рет
шешімдер жиыны
кеңістікте симплексті (simplex
– латыншадан аударғанда қарапайым
деген мағынаны білдіреді) беретін
сызықтық программалау есебіне қатысты
дайындалды:
,
мұндағы
-
-өлшемді
вектор,
- бірлік вектор;
- нөлдік вектор.
Канондық түрде берілген кез келген сызықтық программалау есебін шығаруға мүмкін болғандықтан симплекс әдісі әмбебап әдіс болып табылады.
-өлшемді
бір жазықтықта жатпайтын
-
нүктенің дөңес қабықшасы (7-тарауды
қараңыз)
(
-өлшемді)
симплекс
деп аталады.
Басқаша
айтқанда, симплекс бұл –
төбесі бар
-өлшемді
дөңес көпжақ. Симплекстің кез келген
нүктесін оның төбесінің дөңес қабықшасы
ретінде беруге болады. Екіөлшемді
симплекс бұл – кесінді, үшөлшемді
симплекс – үшбұрыш, төртөлшемді симплекс
– тетраэдр. Бұл жерде симплекстің
өлшемділігі өзі орналасқан
-өлшемді
гипержазықтықтың өлшемділігі бойынша
емес, кеңістіктің өлшемділігі бойынша
анықталады.
,
нүктелері симплекстің төбелері болып
табылады.
Симплекс әдісінің негізгі идеясы қандай да бір тірек шешімнен бастап жүйенің тірек шешімдері бойымен біртіндеп тиімді тірек шешімге бағытталады. Осылайша тиімді тірек шешімге бағыттала отырып бір шешімнен бір шешімге көшу барысында максимум есебінде мақсат функциясының мәні кемімейді, минимум есебінде артпайды. Тірек шешімнің саны ақырлы болғандықтан қандай да бір қадамның ақырлы санынан кейін тиімді шешім табылады немесе есептің шешімінің жауабын аламыз.
Сызықтық программалау есебін симплекс әдіспен шығару алгоритмі
Жоғарыда айтылғандай, алдымен сызықтық программалау есебінің канондық түрде болуын тексереміз (кері жағдайда қосымша айнымалылар енгізе отырып осы түрге келтіреміз). Осыдан кейін кез келген сызықтық программалау есебін симплекс әдісімен шығара аламыз. Тек шектеулер жүйесінің бос мүшелері оң болатындығына көңіл аударуымыз керек.
Базистік шешімді табу үшін айнымалыларды негізгі және негізгі емес айнымалыларға бөлеміз. Бірінші қадамда, мүмкін болса негізгі айнымалылар ретінде ( - шектеулер жүйесіндегі теңдеулер мен теңсіздіктердің жалпы саны) айнымалыны таңдаймыз. Бұл айнымалылардың әрқайсысы шектеулер жүйесінің теңдеулерінің тек қана біреуіне енгізілуі тиіс, ал бұл мүмкін болмаса негізгі айнымалылардың анықтамасын пайдаланамыз.
Негізгі айнымалыларды негізгі емес айнымалылар арқылы өрнектейміз.
Негізгі емес айнымалыларды нөлге теңестіреміз. Алынған сызықтық теңдеулер жүйесін негізгі айнымалыларға қатысты шешіп, базистік шешімді табамыз.
Негізгі айнымалылар анықталған өрнектердегі бос мүшелердің теріс еместігіне көзімізді жеткізе отырып, негізгі айнымалылардың теріс еместігін тексереміз. Ал теріс бос мүше кездессе алгоритмнің екінші қадамына көшеміз де, айнымалыларды негізгі және негізгі емес айнымалыларға бөлудің басқа нұсқасын қарастырамыз (бұл қадам негізгі және негізгі емес айнымалыларға бірінші рет бөлгенде ғана орындалады).
Төртінші қадамды орындау нәтижесінде негізгі айнымалылар теріс емес болса, алынған базистік шешім тиімді болуы мүмкін. Сондықтан, мақсат функциясын негізгі емес айнымалылар арқылы өрнектейміз.
Негізгі емес айнымалылардың мәнін нөлге теңестіріп, табылған базистік шешімде мақсат функциясының мәнін есептейміз.
мақсат функциясының формуласында негізгі емес айнымалылардағы барлық коэффициенттер оң (теріс) болса, онда табылған базистік шешім минимал (максимал) болады да, есеп шешілген болып есептелінеді. Кері жағдайда, яғни негізгі емес айнымалылардағы коэффициенттердің таңбалары әр түрлі (оң және теріс коэффициенттер аралас) болып келсе, алгоритмнің келесі қадамына көшеміз.
Жаңа базиске енгізілетін және одан шығарылатын айнымалыларды анықтаймыз: егер мақсат функциясындағы негізгі емес айнымалылардың коэффициенттерінің барлығы бірдей оң (теріс) болмаса, онда мақсат функциясына енетін айнымалылардың коэффициенттерінің ішінен модулі бойынша ең үлкен болатындай теріс (оң) коэффициенті бар айнымалыны негізгі емес айнымалы ретінде таңдаймыз. Оны қандай да бір базистік айнымалы нөлге тең болғанша арттыра береміз (бұл кезде қалған негізгі емес айнымалылар өздерінің нөлдік мәнін сақтайды). Таңдап алынған негізгі емес айнымалыны келесі қадамда негізгі айнымалы ретінде, ал нөлге тең болған базистік айнымалыны жаңа негізгі емес айнымалы ретінде қарастырамыз.
Тиімді шешім табылғанша ( мақсат функциясындағы негізгі емес айнымалылардың коэффициенттерінің барлығы бірдей оң (теріс) болғанша), айнымалыларды негізгі және негізгі емес айнымалыларға жаңадан бөлуді пайдалана отырып алгоритмнің үшінші қадамына қайта ораламыз.
Осы алгоритмді пайдаланып әр түрлі жағдайдағы сызықтық программалау есептерін шығаруға болады.
2.1-мысал.
Симплекс әдісін пайдаланып
,
шектеулеріндегі
сызықтық функциясының максимум мәнін табу керек.
Шығарылуы. Қосымша айнымалыларды енгізе отырып шектеулер жүйесін канондық түрге келтіреміз.
Бірінші итерациялық қадам.
1.1. Базистік шешімді табу үшін айнымалыларды негізгі айнымалыларға (н.а.) және негізгі емес айнымалыларға (н.е.а.) бөлеміз.
н.а.
,
,
,
,
;
н.е.а. , .
1.2. Негізгі айнымалыларды негізгі емес айнымалылар арқылы өрнектейміз.
1.3. Негізгі емес айнымалыларды нөлге теңестіреміз:
,
.
1.2-қадамдағы алынған сызықтық теңдеулер жүйесін негізгі айнымалыларға қатысты шешіп, базистік шешімді табамыз.
.
1.4. Табылған базистік шешімнің компоненттері теріс емес, сондықтан ол жарамды.
1.5. мақсат функциясын негізгі емес айнымалылар арқылы өрнектейміз.
,
.
1.6. мақсат функциясының формуласында негізгі емес айнымалылардағы барлық коэффициенттер оң, сондықтан алынған базистік шешім тиімді емес (алгоритмнің 7-қадамы ).
Жаңа базиске енгізілетін және базистен шығарылатын айнымалыларды анықтаймыз. Берілген мысалда айнымалысының коэффициенті үлкен, сондықтан айнымалысы негізгі емес айнымалыдан негізгі айнымалыға көшіріледі.
1.7. (1.3-қадам бойынша, айнымалысы негізгі айнымалыға көшірілгендіктен нөлге тең емес)
(1.2-қадамда
есептелген жүйеге
мәнін қоямыз)
Айнымалылардың теріс еместік шартын ескерсек
1.8. Табылған 5 мәні 4-теңдеуге сәйкес келеді, яғни 4-теңдеу – шешуші теңдеу. негізгі айнымалыдан негізгі емес айнымалыға өтеді.
Екінші итерациялық қадам.
2.1. н.а. , , , , ;
н.е.а. , .
2.2.
2.3.
,
,
.
2.4. Базистік шешім жарамды.
2.5.
,
.
2.6. Мақсат функцияда тек қана айнымалысының коэффициенті оң болғандықтан, айнымалысы негізгі емес айнымалыдан негізгі айнымалыға көшіріледі.
2.7.
.
2.8. Бесінші теңдеу – шешуші теңдеу, айнымалысы негізгі айнымалыдан негізгі емес айнымалыға көшіріледі.
Үшінші итерациялық қадам.
3.1. н.а. , , , , ;
н.е.а. , .
3.2.
3.3.
,
,
.
3.4. Базистік шешім жарамды.
3.5.
,
.
3.6. Мақсат функцияда тек қана айнымалысының коэффициенті оң болғандықтан, айнымалысы негізгі емес айнымалыдан негізгі айнымалыға көшіріледі.
3.7. :
.
3.8. Бесінші теңдеу – шешуші теңдеу, айнымалысы негізгі айнымалыдан негізгі емес айнымалыға көшіріледі.
Төртінші итерациялық қадам.
4.1. н.а. , , , , ;
н.е.а. , .
4.2.
4.3.
,
.
.
4.4. Базистік шешім жарамды.
4.5.
,
.
4.6. Мақсат функцияда оң коэффициентті айнымалы жоқ, демек тиімділік критерийі орындалады. Алынған шешім тиімді.
Жауабы:
,
.
2.2-мысал.
Симплекс әдісін пайдаланып
,
шектеулеріндегі
сызықтық функциясының минимум мәнін табу керек.
Шығарылуы. Қосымша айнымалыларды енгізе отырып шектеулер жүйесін канондық түрге келтіреміз.
Бірінші
қадамда қолдануға болатын анықтама
бойынша негізгі айнымалылар –
,
.
Бұл жағдайда базистік шешім
- жарамды емес, себебі базистік шешім
ретінде қарастырып отырған шешімде екі
теріс компонент бар. Ал негізгі
айнымалыларға қойылатын талаптарды
ескерсек, әрбір теңдеуде бір рет
кездесетін айнымалыны негізгі айнымалы
ретінде алуға болады. Біздің мысалда
бірінші теңдеудегі
айнымалысы шектеулер жүйесінде бір рет
қана кездеседі, сондықтан,
айнымалысын негізгі айнымалы ретінде
қарастырамыз. Ал екінші теңдеуден
айнымалысын аламыз. Сонда негізгі
айнымалылар -
,
.
.
Базистік шешім жарамды емес, бір теріс компонент бар.
Базистік
шешім жарамды емес болған жағдайда
мақсат функциямен жұмыс істеуге болмайды.
Сондықтан екінші теңдеуден кез келген
оң коэффициентті айнымалыны (
)
негізгі айнымалы ретінде қарастырамыз.
Бірінші итерациялық қадам.
1.1. н.а. , ;
н.е.а.
,
,
,
,
.
1.2.
1.3.
,
,
,
,
;;
.
1.4. Базистік шешім жарамды.
1.5.
,
.
1.6. Мақсат функцияда теріс коэффициентті айнымалы жоқ, демек алынған шешім тиімді шешім болып табылатынын білдіреді.
Жауабы:
,
.