Сызықты программалау есебін шешудің М-әдісі (Жасанды базис әдісі)

1.1-кесте

1.2-кесте

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

Бұл кестенің Р0 бағанында шығарылатын тірек жоспардың оң компонеттерін жазады, осында есептеу нәтижесі  тірек жоспардың оң компонеттерін алады.

1.1-кестеде бірінші m жолы есептің берілген мәліметтерін анықтайды, ал (m+1)-ші жол көрсеткіші есептелінеді. Бұл жолдың Р0 векторының бағанында  мақсат функцияның мәні, ал  Pj  векторының бағанында - мәні жазылады.

zj мәні  Pj  векторының Сб=(c1; c2; ...; cm) векторына скаляр көбейткіші ретінде табылады:

.

Ғ0 мәні Р0 векторының Сб векторына скаляр көбейткішіне тең:

.

1.1-кестені толтырғаннан кейін шығарылған тірек жоспарды оптималдылыққа тексереді. Ол үшін кестенің (m+1)-ші жолының элементтері қаралады. Нәтижесінде төмендегі үш жағдайдың біреуі орын алуы мүмкін:

1) үшін . Сондықтан берілген жағдайда саны 1-ден n-ге дейінгі барлық j   үшін;

2) қандай да бір j үшін ;

3) қандай да бір j индексі үшін .

Бірінші жағдайда оптималдылық белгісіне негізделсек, шығарылған тірек жоспар оптималды болып табылады. Екінші жағдайда мақсат функция көптеген жоспарларға жоғарыда шектелмеген, ал үшінші жағдайда шығарылған жоспардан жаңа тірек жоспарға көшу, осы кезде мақсат функция мәні өседі. Осы бірінші тірек жоспардың екіншісіне көшуі векторлардан қандай да бір шығарылған базистен алып тастау және оған жаңа вектор енгізумен жүзеге асырылады. Базисқа енгізілетін векторлар ретінде  қандай да бір үшін j  индексі бар кез келген Pj векторын алуға болады.Мысалы, және базиске Pk векторын енгізу керек болсын.

Базистан шығаруға жататын векторды анықтау үшін барлық үшін табады. Бұл минимум i=r кезінде жету керек болсын. Онда базистан Pr векторы алынады, ал ark саны шешуші элемент деп аталады.

Баған мен жолдың қиылысуында тұрған шешуші элемент бағыттаушы деп аталады.

Бағыттаушы жол мен бағыттаушы бағанды белгілеп алғаннан кейін жаңа тірек жоспарды және жаңа тірек жоспарға сәйкес келетін жаңа базистің векторы арқылы Pj векторының жіктелу коэффициентін табады. Егер Жордан-Гаусс әдісін пайдаланатын болсақ, бұны жетілдіру өте оңай. Сонымен қатар жаңа тірек жоспарының оң компонеттерін төмендегі формулалар бойынша есептеуге болатының көрсетуге болады:

                                                                                                                (4)

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

                                                                                                  (5)

мен есептелгеннен кейін (4) және (5) формулаларға  сәйкес олардың мәні 1.2-кестеге енгізіледі. Бұл кестенің (m+1)-ші жол элементтері төмендегі формулалар арқылы да есептелінуі мүмкін:

                                                                                                                (6)

,                                                                                                                (7)

немесе олардың анықтамалары негізінде есептелінуі мүмкін.

Бір тірек жоспарынан екіншісіне көшу бір симплекс-кестінен екіншісіне көшумен сәйкес келеді. Жаңа сиплекс-кестесінің элементтерін (5)-(7) рекурентті формулалар көмегімен шешуге болады.

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

Вектор  жазылған жаңа симплекс-кесте жолында P0 және Pj вектор элементтері кестедегі берілген жолдың элементтерінен шешуші элемент шамасын оларға бөлумен алынады. Енгізілетін вектор жолындағы Сб бағанына сk шамасын қояды, мұндағы k – енгізілетін вектор индексі.

Жаңа симплекс-кесте жолының P0 және Pj векторлар бағандарының қалған  элементтерін төртбұрыштар әдісімен шешеді.

Жаға симплекс-кесені толтырғаннан кейін (m+1)-ші жол элементтері қарастырылады. Егер барлық болса, онда жаңа тірек жоспар оптималды болып табылады. Егер де көрсетілген сандардың ішінде теріс сандар болса, онда жаңа тірек жоспарды табады. Бұл процесс есептің оптималды жоспары табылғанша жалғаса береді.

Сонымен, симплекс әдісімен оптималды жоспарды табу келесі этаптардан тұрады:

1.      Тірек жоспарды табады.

2.      Симплексм-кесте құрады.

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

4.      Бағыттаушы баған мен жолды табады. Бағыттаушы баған  теріс санының абсолют шамасы бойынша үлкенін анықтайды, ал бағыттаушы жолды – Р0 вектор  бағандарының компоненттері бағыттаушы бағанының оң компонеттеріне минималды арақатынасын анықтайды.

5.      (4) – (7) формулалар бойынша  жаңа тірек жоспарының оң компонеттерін, жаңа базис векторлары бойынша Pj векторының жіктелу коэффициенттерін және сандарын анықтайды. Барлық сандар жаңа симплекс-кестеде жазылады.

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

1.3 Сызықты программалау есебін шешудің М-әдісі (Жасанды базис әдісі)

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

                                                                                    (1)

                                                                                                                (2)

                                                                                                  (3)

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

                                                        (4)

мұндағы М – кез келген оң сан.

Егер есеп max зерттелетін болса +М, min зерттелетін болса –М алынады. Осылайша түрлендірген есеп кеңейтілген түрі деп аталады және мынадай түрде алынады.

                                                                                                  (5)

                                                                                                                              (6)

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

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

1.1. Нұсқасын келтіру түсінігі

Модель дегенiмiз – нақты объектiнi, процестi немесе құбылысты ықшам әрi шағын түрде бейнелеп көрсету. Модельдеу дегенiмiз – объектiлердi, процестердi және құбылыстарды зерттеу мақсатында олардың модельдерiн жасау.

Түпнұсқаның өзiн зерттемей, оның моделiн жасаудың қандай пайдасы бар деген сұраққа жауап берейiк:

1.      Модельдеу арқылы шын мәнiнде жоқ немесе бұрын болып жойылып кеткен объектiнi зерттеуге болады. Модельдеу үшiн уақыт ешқандай кедергi жасамайды. Белгiлi деректерге сүйене отырып, гипотеза немесе ұқсастық әдiсiмен өте ерте замандағы жағдайлар мен табиғи катаклизмдердi модельдеуге болады.