Өндірістік және Экономикалық процестредің нұсқасын келтіру пәнінің жалпы мінездемесі

1.1-кесте

i

Базис

Cб

Р0

c1

c2

cr

cm

cm+1

ck

cn

P1

P2

Pr

Pm

Pm+1

Pk

Pn

1 2 r m

Р1 Р2 Pr Pm

с1 с2 ск cm

b1 b2 br bm

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

a1m+1 a2m+1 arm+1 amm+1

a1k a2k ark amk

a1n a2n arn amn

m+1

F0

0

0

0

0

1.2-кесте

i

Базис

Cб

Р0

c1

c2

cr

cm

cm+1

ck

cn

P1

P2

Pr

Pm

Pm+1

Pk

Pn

1 2 r m

Р1 Р2 Pr Pm

с1 с2 ск cm

1 0 0 0

0 1 0 0

0 0 0 1

0 0 1 0

m+1

F0

0

0

0

0

 

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

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

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

z_j мәні  P_j  векторының С_б=(c₁; c₂; ...; c_m) векторына скаляр көбейткіші ретінде табылады:

.

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

.

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

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

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

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

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

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

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

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

        (4)

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

       (5)

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

        (6)

,        (7)

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

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

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

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

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

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

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

1. Тірек жоспарды табады.
2. Симплексм-кесте құрады.
3. Бір теріс сан бар болуын анықтайды. Егер болмаса, табылған тірек жоспар оптималды. Егер сандар ішінде терісі бар болса, онда жаңа тірек жоспарға көшеді немесе есептің шешілмейтіндігі орнатылады.
4. Бағыттаушы баған мен жолды табады. Бағыттаушы баған  теріс санының абсолют шамасы бойынша үлкенін анықтайды, ал бағыттаушы жолды – Р₀ вектор  бағандарының компоненттері бағыттаушы бағанының оң компонеттеріне минималды арақатынасын анықтайды.
5. (4) – (7) формулалар бойынша жаңа тірек жоспарының оң компонеттерін, жаңа базис векторлары бойынша P_j векторының жіктелу коэффициенттерін және сандарын анықтайды. Барлық сандар жаңа симплекс-кестеде жазылады.

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

 

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

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

      (1)

        (2)

       (3)

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

    (4)

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

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

     (5)

       (6)

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

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

 

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

Модель деген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 модельдеуге болады.
2. Түпнұсқаның қасиеттерi мен өзара әсерi орасан зор болуы мүмкiн. Кейбiр жағдайларда адамды қызықтыратын объектiлердiң қасиеттерiн зерттеу үшiн, оның басқа қасиеттерi ескерiлмей жасалған модельдер түпнұсқаға қарағанда, оның қасиеттерiн зерттеуге тиiмдiрек болады. Объектiлердiң модельдерi ретiнде әдеби шығармалар, архитектуралық ғимараттардың кiшiрейтiлген көшiрмесi, мектептегi оқу жабдықтары болуы мүмкiн. Модель – күн жүйесiндегi планеталар моделi, сутегi атомы және тағы да басқалар. Өмiрдегi нақты бар дүниенi бейнелеуi мүмкiн.