2. Симплексті алгоритмдер

   1. Қарапайым симплекс-әдіс

n айнымалылардың кеңістіктегі симплексі деп төбесі бар, дөңес көп жақты денені айтады. Екі айнымалы кеңістікте ол – үшбұрыш, үш айнымалы кеңістікте – тетраэдр. Қарапайым симплекс әдісте дұрыс симплекс (барлық қабырғалары тең) қолданылады.

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

1. Симплекстің бір төбесі координаттар басына орналасады, ал қалған төбелері

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

1-сурет.

Жалпы жағдайда симплекс төбелерінің координаттары матрица көмегімен анықталады:

3. Симплекс ортасы координаттар басына орналасады, ал ші төбеосіне орналасады. Қалған төбелер координат осьтеріне қатысты симметриялы орналасады. Екі өлшемді жағдай үшін төбелердің координаттары келесідей болады:

2-сурет.

Жалпы жағдайда симплекс төбелерінің координаталары матрица көмегімен анықталады:

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

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

Нәтижесінде жаңа симплекс пайда болады, оның үстінежәнеекі нүктедегі мақсатты функцияның мәндері белгілі. Сондықтаннүктесіндегі функция мәні есептелінеді және барлық төбелер ішінен «ең нашар» мәнді төбе ізделінеді. Бұл төбе тағы да қарсы шектің ортасы арқылы кескінделіп, барлық процедура қайталанады. Іздеудің соңының белгісі шырғалану процесі болып табылады. Яғни, қайта кескінделген төбе «ең нашар» төбе болып шыққан кезде. Бұл жағдайда берілген дәлдікке қол жеткізілмесе (дәлдік симплекс қабырғасы ұзындығымен анықталады), симплекс көлемін кішірейту қажет. Процедура симплекс қабырғасының ұзындығы берілген дәлдіктен кем болғанша қайталана береді.

Жалпы n-өлшемді жағдай кезінде, симплекстің кескінделетін төбесін деп, ал қалған төбелеріндеп, кескінделген төбесіндеп белгілесе, кескінделу жүргізілетін шектің ауырлық ортасының координаттары келесі формуламен есептелінеді:

ал кескінделген төбеден (4.1)

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