Зертханалық жұмыс

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

Міне симплекс әдісі қалай жұмыс істейтініне шолу:

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

Стандартты пішінге түрлендіру: Мәселе әдетте стандартты пішінге түрлендіріледі, бұл барлық айнымалылар теріс емес болу үшін шектеледі және теңсіздіктер үшін теңдік шектеулері енгізіледі.

Инициализация: симплекс әдісі бастапқы орындалатын шешімнен басталады. Мұны әртүрлі әдістер арқылы алуға болады, мысалы, мәселенің «босаңсыған түрі» немесе жасанды айнымалылар.

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

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

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

Қайталау: 4-6 қадамдар оңтайлы шешімге жеткенше қайталанады. Әрбір итерация мақсат функциясының мәнін жақсартуы керек, ал алгоритм әрі қарай жақсарту мүмкін болмаған кезде тоқтатылады.

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

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