Математикалық және сызықтық программалаудың электронды оқулықтарын пайдалану арқылы білім беру деңгейін көтеру

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 50 бет
Таңдаулыға:

1 Математикалық және Сызықтық программалаудың электронды оқулықтарыН пайдалану арқылы білім беру деңгейін көтеру

1. 1 Сызықтық программалау мәселелерін ақпараттандыру және талдау жолдары

Жалпы сызықтық программалау терминін шарттары сызықтық өрнектермен анықталған экстрималды есептерді шешу әдістері деген мағынада түсінеміз.

Көздеген мақсатқа жеткендікті дәлелдейтін белгіні оптималдық критерии (оптималық принціпі) деп атайды. Әдетте оптималдық критери ретінде «ең көп (максимум) пайда», «ең аз (минималды) шығын», «максилалды рентабельдік» т. б. қарастырылады.

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

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

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

Белгісіздердің сан мәндерінің тізбегі жоспар деп аталады. Қойылған шектеулер жүйесін қанағаттандыратын кез келген жоспар жарамды жоспар деп аталады. Функционалға ізделінді максимум немесе минимум мәнін беретін мүмкін жоспар оптималды, яғни тиімді жоспар деп аталады. Демек қойылған экономикалық мәселені шешу жарамды шешімдердің ішінен оптимал шешімді табуды білдіреді. Барлық жарамды шешімдер математикалық программалу есебінің анықталу облысын құрайды.

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

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

Енді математикалық программалау әдістері мен шешілетін сызықтық оптималы мәселелерін қарастырайық.

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

Кәсіпорын m түрлі ресурс (мысалы, егістік, жұмысшы қолы, дән, жанар-жағармай, жем-шөп, т. б. ) қолданып, n түрлі өнім өндіреді делік в ₁ , в ₂ , . . . , в _m әрбір ресурстың кәсіпорында бар мөлшері. Әрбір өнімнің бірлік мөлшерін сатудан түсетін таза пайда-c ₁ , c ₂ , …, c _n және әрбір өнімнің бірлігін өндіруге жұмсалатын әрбір ресурсың мөлшері- a ₁₁ , a ₁₂ , …, a _1n , a _21, a ₂₂ , …, a _ij , …, a _mn -белгілі, мұндағы a _ij -j-ші өнімнің біреуіне жұмсалатын i-ші ресупс мөлшері (i=1, …, m, j=1, …, n) . Бұл санлар технологиялық коэффиценттер деп аталады.

Кәсіпорындардағы бар ресурстарды ұтымды пайдалану арқылы максимум пайда беретін өндірістің оптимал жоспатын Х, яғни әрбір өнім мөлшерін х ₁ , х _{2, . . . ,} x _n табу керек.

Есептің математикалық моделін құру үшін өндіру қажет өнімдердің шамаларын х _j (j=1, …, n) арқылы белгіледік.

Сонда барлық өнімдерді сатуден түсетін пайда

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

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

Эканомикалық мағынасына сәйкес әрбір белгісіз шама теріс сан болуы мүмкін емес, демек олар

x ₁ ≥0, …, xn≥0 шарттарын қанағаттандырулары тиіс.

Мал азығының рационын құру мәселесі [1] Шаруашылықта дайын n-түрлі мал азығы бар делік. Әр азақтың құрамында m - түрлі қоректі элементтері бар. Бір азақ өлшемінің i-элемен нормасы - және бір азақ өлшемінің өзіндік құны - белгілі. Рационда әрбір қоректік элемент мөлшері Р _і шамасынан кем болуға тиісті. Осы шартқа сәйкес зоотехниклық нормаларға сай нормаларға сай келетін өзіндік құны өте арзан рацион құру керек.

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

арқылы жазылады.

Рацион құрамындағы әрбір қоректік заттардың шамасы нормадан кем болмауы

шектеулер жүйесі арқылы жазылады.

Айнымалылардың теріс сан болмау талабы Equation. 3 Equation. 3 …, Equation. 3 Equation. 3 .

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

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

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

Сызықтық оптимал мәселелер теориясының жалпы есебі қысқаша төмендегіше жазылады:

(1. 1)

(1. 2)

(1. 3)

(1. 4)

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

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

Көптеген экономикалық есептерде берілгендер х ₁ , . . . , х _n техниканың станоктардың, т. б. бүтін объектілердің санын білдіреді, мұнда есептің шешімі бүтін сандардан тұруы керек. Сондықтан көптеген СОМ-лерде белгісіздерге қосымша бүтін сан болу шарты - және бүтін қойылады. Мұндай мәселелерді бүтін мәнді СОМ-лер (бүтін мәнді сызықты программалау) немесе дискретті СОМ-лер деп атайды.

Енді СОМ теориясында қолданылатын бірнеше маңызды анықтамаларды қарастырайық.

1-анықтама. Оптималдық критерий ретінде алынған (1. 1) сызықты функциясы - мақсат функциясы , (1. 2) - (1. 3) шарттары - есептің шектеулері, ал (1. 4) - белгісіздердің теріс емес шарттары деп аталады.

2-анықтама. (1. 3) - (1. 4) шарттары бойынша (1. 1) мақсат функциясының максимум мәнін анықтау есебі СОМ -лердің стандартты (симметриялық) есебі деп аталады. (m ₁ =0, n ₁ =n) .

3-анықтама. (1. 2) - (1. 4) шарттары бойынша (1. 1) мақсат функциясының максимум мәнін анықтау есебі СОМ-лердің канондық есебі деп аталады. (m ₁ =m, n ₁ =n)

4-анықтама. (1. 1) - (1. 4) шарттарын қанағаттандыратын Х= сандары СОМ-сінің жарамды шешімі (жоспары) деп, ал мақсан функциясының максимум немесе минимум мәнін қамтамасыз естетін Х ^* =( - оптимал жоспар деп аталады.

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

Жалпы есепті канондық түрге келтіру үшін теңсіздіктерге қосымша теріс емес айнымалалары енгізіледі. Сонда шектеулер теңдіктермен өрнектеледі:

Егер болса, онда есеп канондық түрге толыұ түрленген, ал жағдайында, яғни

есепті канондық түрге ауыстыру үшін айнымалысын

-теріс емес айнымалылардың айырмасымен ауыстырса болады.

мұндағы .

Енді берілген есепті канондық түрде жазуға мысалдар қарастырайық.

Канондық түрі:

1. 2-мысал.

Канондық түрі: белгілеулерін жасау арқылы

Қазіргі кезеңде СОМ-рді шешуді ең көп қолданатын әдістерінің бірі-симплекс әдісі. Ол алғашқы бір анықталған тірек шешімі деп аталатын жоспардан саны шектеулі алгебралық түрлендірулер арқылы оптимал шешімге детуге негізделген. Симпллекс әдісі канондық есепті шешуге арналған. m қатар, n бағанадан тұратын матрицасының жолдары n өлшемді вектр да, бағандары m өлшемді вектор болады.

=(а _1, а ₂ , . . . , а _n ) және =( в _1, в ₂ , . . . , в _n ) векторлары сәйкес компонеттері тең болған жағдайда ғана . a _j = в _j , (j=1, 2, . . . n) өзара тең вектор деп есептеледі.

және векторларының қосындысы деп + =(а _1, + в _1, а ₂ + в ₂ , . . . , а _n + в _n ) анықталған вектор аталады.

n өлшемді кеңістікте нөлдік вектор мен i-орта векторлары ерекше орын алады. Нөлдік вектордың барлық компонеттерінөлге тең : (0, 0, . . . , 0), оның геометриялық мағынасы координаттар бас нүктесі. Әрине, .

i-орт i-ші ортасында ғана 1 болып, қалған компонеттері нөл болатын вектор: =(0, . . . , 0, 1, 0, . . . , 0) . Геометриялық тұрғыда i-орт-i-ші остің бойындағы онымен бағыттас бірлік вектор.

векторларға векторына қарамы-қарсы вектор деп аталады, бұдан +(- ) = екендігі айтпаса да түсінікті.

+ = +(- ), яғни бір вектордан екінші векторды алу бірінші векторға екінші векторға қарама-қарсы векторды қосқанмен бірдей.

векторының λ санына көбейтіндісі деп λ =( ) арқылы анықталған векторларды айтады, Бұдан төмендегі теңдіктер шығады:

λ( ± ) =λ ±λ

(k±λ) =k ±λ

k(λ ) =(k λ)

Мұның салдары: 0* =0 (-1) * =- , λ* = .

Векторлық алгебрада екі вектордың скаляр көбейтіндісі деп анықталған: екі вектордың скаляр көбейтіндісі деп сәйкес компонеттердің көбейтінділерінің қосындысыны тең сан аталады: + =а ₁ в ₁ +а ₂ в ₂ +, . . . , +а _n в _n.

Мысылы, =(1, 3, 7, 12), =(2, 4, 1, 0) векторларының скаляр көбейтіндісі * =1*2+3*4+7*1+12*0=21

Сондай ақ * = а ₁ *0+а ₂ *0+ . . . , +а _n +*0=0

* = 0* в ₁ +0* в ₂ + . . . , +1* в _i +…+0*в _n = в _i

* =a ₁ ² +a ₂ ² +…+a _n ²

Векторлардың ұзындығы формуласын ескерсек

жалпы а ₁ х ₁ +а ₂ х ₂ +, . . . , +а _n х _{n. =} в түріндегі сызықтық теңдаудің сол жағын = (а _1, а _2, . . . , а _n )

= ( х ₁ , х ₂ , . . . , х _n ) векторларының скаляр көбейтіндісі деп түсінуге болады: * = в

3-анықтама: Егер векторлар үшін теңдігі орындалатын сандары табылса В векторы векторларының сызықтық комбинациясы деп аталады.

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

Мысылы, А ₁ =(2, 4, 3), А ₂ =(2, 3, 1), А ₃ =(5, 3, 2, ), А ₄ =(1, 7, 3) векторлары сызықтық тәуелді, себебі А ₁ +2А ₂ -А ₃ -А ₄ =0.

5-анықтама: n өлшемді векорлық кеңістіктің кезкелген векторын осы кеңістіктің базистік векторлардың сызықтық комбинациясы арқылы өрнектеуге болады.

Е ₁ =(1, 0, …, 0), Е ₂ =(0, 1, 0, …, 0), . . . , Е _n =(0, 0, …, 0, 1) - бірлік векторлар жүйесі n өлшемді векторлық кеңістіктің базисі бола алады.

Жиын тұйық болса тура шектелмеген, және керісінше, шектелген жиын болса тура тұйық емес болуы мүмкін.

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

Вейерштрасс теоремесы. Егер f( ) функциясы Х тұйыұ шектелген жиынында анықталған және үздіксіз болса, онда бұл функция осы жиында глобальды максимум және глобальды минимумына ие болады.

Енді сызықтық программалауды қолданылатын математикалық аппарат негізін құрайтын алгебралық түрлендірулерді қарастырайық.

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

Әдістемелік жүйенің функционалдық мүмкінділіктері туралы төменде айтып өтеміз.

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

Сызықтық программалау есептерін шешуге арналған визуалды зертханалық жұмыстар әдістемелік жүйе ретінде қарастырылған.

Мысал 1. Сызықтық программалау мәселесін жазу жолдары. Сызықтық оптимал мәселелер теориясының жалпы есебін орандауға берілген мысал.

Төмендегі берілген есепті канондық түрде жазуға мысалдар қарастырайық.

1-мысал:

Канондық түрі:

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

Төменде берілген теңдеулер жүйесін шешу керек:

Шешуі. Алдымен алғашқы Жордан кестесін құрастырамыз:

Кесте 3. 1. Жордан кестесі

-х ₁

-х ₂

-х ₃

: 0=

1: 6

-х1: 1

-х2: -1

-х3: 1

: 0=

1: 3

-х1: 2

-х2: 1

-х3: 2

: 0=

1: -5

-х1: -1

-х2: 3

-х3: 6

Кесте 3. 1 ге Жордан түрлендіруін қолданып кесте 3. 2 ге өтеміз; шешуші элемент а ₁₁ =1≠0 (r=1 -шешуші жол, s=1-шешуші бағана) . Демек х ₁ белгісізін базиске енгіземіз:

Кесте 3. 2. Түрленген Жордан кестесі

-х ₂

-х ₃

: Х ₁ =

1: 6

0: 1

-х2: -1

-х3: 1

: 0=

1: -9

0: 2

-х2: 3

-х3: 0

: 0=

1: 1

0: -1

-х2: 2

-х3: 7

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

Кесте 3. 2 ден шешуші эемент а ₂₂ =3≠0 (r=2 -шешуші қатар, s=2-шешуші бағана) таңдап, түрлендіру арқылы үшінші кестеге өтеміз:

Кесте 3. 3. Түрленген Жордан кестесі

-х ₃

: Х ₁ =

1: 3

0: 1/3

-х3: 1

: 0=

1: -3

0: 1/3

-х3: 0

: 0=

1: 7

0: -2/3

-х3: 7

Бұл кестеден шешуші элемент а ₃ =7≠0 арқылы түрлендіру соңғы кестені береді

Кесте 3. 4. Түрленеген соңғы кесте.

: Х ₁ =

1: 2

0: 1/7

: 0=

1: -3

0: 0

: 0=

1: 1

0: 1/7

Сонымен берілген теңдеулер жүйесінің шешімі х ₁ =2*1=2, х ₂ =-3*1=-3, , х ₃ =1*1=1 немесе шешім 1- бағанадағы мәндер.

Мысал 3. Сызықтық программалау есебін шешудің графиктік тәсіліне арналған екі өлшемді кеңістікте(жазықтықта) берілген есепті шығару.

Екі өнімді өндіруге жұмсалатын ресурс мөлшері мен өнімдердің біреуін сатудан пайда соммасы төмендегі кестеде берілген.

Кесте 3. 4. Екі өнімнің ресурс қоры.

Бір өнімге жұмсалатын ресурс

Ресурс қоры

1-өнім

2-өнім

Бір өнімге жұмсалатын ресурс:

Ресурс қоры:

: Пайда (ақша. бірлігі)

Бір өнімге жұмсалатын ресурс: 7

Ресурс қоры: 3

Максимум пайда түсетін өндіріс жоспарын анықтау керек.

Шешуі: Есептің математикалық моделін құру берілгендер енгіземіз: х ₁ -өндірілетін бір өнім мөлшері, х ₂ -екінші өнім мөлшері. Сонда мақсат функциясы - пайда:

Максимум пайда беретін х ₁ , х ₂ шамаларын табудың графиктік жолы.

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

Сурет 3. 1. Жазықтықтағы салынған тұйық көпбұрыш

ә) Графикте векторын анықтаймыз.

б) немесе түзуін саламыз. Бұл түзу (0, 0) , (3, 7)

нүктесі арқылы өтеді.

в) Максимум f(x) анықтау үшін (f) түзуін векторының бағытымен оңға қарай өзіне параллель жылжытамыз, оны шешімдер жиынымен соңғы ортақ нүктесі -В нүктесі.

г) теңдеулер жүйесін шешу арқылы х ₁ =2, х ₂ =5 В нүктесінің координаттарын табамыз: В(2, 5) . Сонымен ең көп пайда табу үшін х ₁ =2, х ₂ =5 мөлшерінде өнім өндіру керек, (ақша бірлігі) .

Мысал 4. Сызықтық оптимал мәселені Симплекс әдісімен шешу. Алғашқы бір анықталған тірек шешім деп аталатын жарамды жоспардан бірнеше алгебралық түрлендірулер арқылы оптимал шешімге жету

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

Кесте 3. 5. Алғашқы симплекс-кесте

БА

-X ₁

-X ₂

-X ₃

: 1

TAБА:

1: 7

-X1: 2

-X2: 1

-X3: 3

: 2

TAБА:

1: -9

-X1: -4

-X2: 3

-X3: 2

: 3

TAБА:

1: 2

-X1: 1

-X2: 2

-X3: -1

: 4

TAБА: F

1: 0

-X1: -1

-X2: -4

-X3: -3

1-итерация; 1-алгоритм. 1-саты бойынша 3-қатарда нөлдік элемент бар , , , демек , .

Кесте 3. 6. Екніші симплекс-кесте.

БА

-X ₂

-X ₃

: 1

TAБА:

1: 3

0: -2

-X2: -3

-X3: 5

: 2

TAБА:

1: -1

0: 4

-X2: 11

-X3: -2

: 3

TAБА: Х ₁

1: 2

0: 1

-X2: 2

-X3: -1

: 4

TAБА: F

1: 2

0: 1

-X2: -2

-X3: -4

немесе нөлдік бағанды есепке алудың қажеті жоқ. Жоғарыдағы кестені шешу арқылы келесі кестені аламыз.

Кесте 3. 7. Үшінші симплекс -кесте.

БА

-X ₂

-X ₃

: 1

TAБА:

Equation. 3

1: 3

-X2: -3

-X3: 5

: 2

TAБА:

Equation. 3

1: -1

-X2: 11

-X3: -2

: 3

TAБА: Х ₁

1: 2

-X2: 2

-X3: -1

: 4

TAБА: F

1: 2

-X2: -2

-X3: -4

2-итерация .

1-саты. Базистік айнымалы бағанасында нөлдік қатар жоқ, 2-алгоритмге көшеміз.

1-итерация.

2-алгоритм.

1-саты бойынша бос мүше бағанасында -1<0, (t=2), демек Х=(2, 0, 0, 3, -1) жоспары - жарамсыз жоспар.

, демек есептің шешімі бар: шешуші бағана , демек , . Келесі кестені анықтайық.

Кесте 3. 8. Төртінші симплекс -кесте.

БА

-X ₂

-У ₂

: 1

TAБА:

Equation. 3

1: 0, 5

-X2: 24, 5

-У2: 2, 5

: 2

TAБА:

Equation. 3

1: 0, 5

-X2: -5, 5

-У2: -0, 5

: 3

TAБА: Х ₁

1: 2, 5

-X2: -3, 5

-У2: -0, 5

: 4

TAБА: F

1: 4

-X2: -24

-У2: -2

2-итерация . 2 алгоритм.

Бос мүше бағанасында теріс элемент жоқ, Х=(2, 5, 0, 0, 5, 0, 5, 0) - алғашқы тірек жоспары. Енді оптимал жоспарды анықтаймыз.

1-итерация . 3 алгоритм.

1-саты бойынша Ғ-қатарда екі теріс элемент: -24 және -2 бар -24<-2, демек (Х ₂ - базиске енді), , демек . Енді келесі кестені анықтаймыз.

Соңғы кестеде Ғ-қатарда теріс элемент жоқ, демек - оптимал шешім, және оптимал жоспар - жалғыз, себебі Ғ - қатарда ешбір нөл жоқ. .

Кесте 3. 9. Бесінші симплекс -кесте.

БА

-У ₁

-У ₂

: 1

TAБА: Х ₂

1: 1/49

-У1: 2/49

-У2: 5/49

: 2

TAБА: Х ₃

1: 30/49

-У1: 11/49

-У2: 3/49

: 3

TAБА: Х ₁

1: 36/14

-У1: 7/49

-У2: -2/14

: 4

TAБА: F

1: 220/49

-У1: 580

-У2: 272/49

1. 3. Сызықтық оптимал мәселелердің қарапайым математикалық модульдерін құру

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

n белгісізді m сызықтық теңдеулер жүйесі берілсін:

Берілген жүйені нөлдік теңдеулерарқылы қайта жазып

Жордан кестесі арқалы көрсетейік:

Кесте 1. Жордан кестесі

-х ₁

-х ₂

. . .

-х _j

…

-х _s

…

-х _n

---

…

a ₁₀

a ₂₀

_---

a _r0

_…

a _m0

-х1:

a ₁₁

a ₂₁

_---

a _r1

_…

a _m1

-х2:

a ₁₂

a ₂₂

a _r2

_…

a _m2

. . .:

…

---

…

-хj:

a _1j

_---

a _rj

_…

a _mj

…:

…

---

…

-хs:

a _1s

a _2s

_---

a _rs

_…

a _ms

…:

…

---

…

-хn:

a _1n

a _2n

---

a _rn

…

a _mn

Әдістің мағынасы: кесте 1-де а _rs ≠0 элементін таңдап, оның шешуші элемент деп атаймыз, сонда r-қатар-шешуші жол, s-бағана -шешуші бағана деп аталады. Одан кейін төмендегі тәртіп бойынша 1-кестені келесі кестеге түсіреміз.

Шешуші элемент өзіне кері шамамен ауыстырылады:.
Шешуші қатардың қалған элементтері шешуші элементке бөлінеді:
Шешуші бағананың қалған элементтері шешуші элементке бөлініп, қарама-қарсы таңбаман жазылады:
Кестенің қалған есептеледі (i≠r, j≠s)

Бұл амалдар Жорданның жетілдірілген тұрлендіруі (ЖЖТ) деп аталады. Алғашқы r түрлендіруден кейінгі кесте кесте 2 арқылы көрсетілген, әр түрлендіруде x _s белгісізі r-қатардағы 0 мен орын ауыстырады(r<n) . [1]

Кесте 2. Түрленген Жордан кестесі

. . .

-х _r+1

…

-х _n

х ₁ =

…

х _r =

…

в ₁₀

_…

в _r0

в _r+10

_…

в _m0

в ₁₁

_…

в _r1

в _r+11

_…

в _m1

. . .:

…

в _1r

_…

в _rr

в _r+1r

_…

в _mr

-хr+1:

в _1r+1

_…

в _rr+1

_…

…:

…

-хn:

в _1n

в _rn

---

…

Кесте 2 ден

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

Мұндағы х ₁ , . . . , х _r - айнымалылары базистік, х _r+1 , . . . , х _n - тәуелсіз айнымалылар деп аталады. Егер тәуелсіз айнымалыларға нөл меншіктесек базистік шешім деп аталатын дербес шешім аламыз:

х ₁ =в _10, х ₂ =в ₂₀ , . . . , х _r =в _r

Теріс емес базистік шешім сызықтық программалау теориясында ерекше орын аладыжәне тірек шешім деп аталады.

Кесте 2-де r=n болса берілген жүйенің бір ғана шешімі бар

3. 2. Өзіндік қолданыстағы алгоритм.

Бірінші өзіндік қолданыстың алгоритмі деп - өзіне өзі қолданылатын алгоритмді айтамыз. Бірақ та бұл корректірлі анықтама емес, себебі МҚА не сөздер ғана кіреді, Ал МҚА ондайға жатпайды. Сондықтан да бұл анықтаманы корректілі ету үшін, МҚА - дегі сызықты сызу керек. Бұл үшін алгоритмге жазба сөзі енгізіледі. МҚА - нің жазбасы деп - тізбектелген нүкте, үтір арқылы жазылған формалар жатады. Осылай бола тұра нүкте мен үтір формулаға енбейді. Мысалы келесі алгоритм:

#a → # (1) a → b (4) (1)

H1 # (2) H2 b → bb (5)

→ # (3)

Мұнда H1 алгоритмі сөз болып табылады.

#a→#; # ; → # (2)

H2 алгоритм жазбасы - сөз.

a→b; b →bb (3)

Бір сөз алгоритм сөзінің жазбасын анықтайды немесе керісінше. Алгоритм жазбасы сз болғандықтан, оны алгоритм шығаруына қолданылады. Нәтижесінде келесі өздік қолданыстағы алгоритмнің корректілі анықтамасын аламыз. Өзіндік қолданыстағы алгоритм деп атаймыз егер де ол өзінің жазбасына қолданылса. Мысалы H1 өзіндік қолданыстағы алгоритмі өз жазбасымен жұмыста шығу сөзі ретінде бастайды және тоқтаумен аяқтайды:

1 2

#a→#; # ; →# → #→#; # ; →# →#; # ; →# (4)