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

Жоспар
Кіріспе

1.1 Сызықтық программалау мәселелерін ақпараттандыру және талдау жолдары
1.2 СОМ теориясында қолданылатын маңызды анықтамалар
1.3. Сызықтық оптимал мәселелердің қарапайым математикалық модульдерін құру
3.2.Өзіндік қолданыстағы алгоритм
3.3. Алгаритмдердің эквиваленттілігі.
3.4. Алгоритмдер композициясы
2 ПРОГРАММАЛАУ ТЕХНОЛОГИЯСЫНДА ЭЛЕКТРОНДЫ ОҚУЛЫҚТЫ ҚҰРУДЫ ҰЙЫМДАСТЫРУ
2.1 Оқытудың программалық технологиясын және әдістемесін жасау
2.2 Сызықтық теңдеулер жүйесін өңдеу технологиялары және құруды қолдайтын аспаптық құралдары
2.3 Сызықтық программалау әдістерінің алгоритмдерін және программаларын құру
2.4 Компьютерлік жүйемен пайдаланушының қатынас интерфейсін құру

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кәсіпорын m түрлі ресурс (мысалы, егістік, жұмысшы қолы, дән, жанар-
жағармай, жем-шөп, т.б.) қолданып, n түрлі өнім өндіреді делік
в1,в2,...,вm әрбір ресурстың кәсіпорында бар мөлшері. Әрбір өнімнің бірлік
мөлшерін сатудан түсетін таза пайда-c1,c2,...,cn және әрбір өнімнің бірлігін
өндіруге жұмсалатын әрбір ресурсың мөлшері-
a11,a12,...,a1n,a21,a22,...,aij,...,amn -белгілі, мұндағы aij –j-ші өнімнің
біреуіне жұмсалатын i-ші ресупс мөлшері (i=1,...,m, j=1,...,n). Бұл санлар
технологиялық коэффиценттер деп аталады.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1.1)

(1.2)

(1.3)

(1.4)

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

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

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

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

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

2-анықтама. (1.3)- (1.4) шарттары бойынша (1.1) мақсат функциясының
максимум мәнін анықтау есебі СОМ –лердің стандартты (симметриялық) есебі
деп аталады.(m1=0, n1=n).

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

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

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

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

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

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

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

мұндағы .

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

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

1.2-мысал.

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

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

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

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

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

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

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

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

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

λ(±)=λ±λ

(k±λ)=k±λ

k(λ )=(k λ)

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

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

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

Сондай ақ *= а1*0+а2*0+...,+аn+*0=0

*= 0*в1+0*в2+...,+1*вi+...+0*вn=вi

*=a12+a22+...+an2

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

жалпы а1 х1+а2х 2+,...,+аnх n.=в түріндегі сызықтық теңдаудің сол жағын
= (а1,а2,...,аn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1-мысал:

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

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

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

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

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

1 -х1 -х2 -х3
0= 6 1 -1 1
0= 3 2 1 2
0= -5 -1 3 6

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

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

1 0 -х2 -х3
Х1= 6 1 -1 1
0= -9 2 3 0
0= 1 -1 2 7

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

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

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

1 0 -х3
Х1= 3 13 1
0= -3 13 0
0= 7 -23 7

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

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

1 0
Х1= 2 17
0= -3 0
0= 1 17

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

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

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

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

Бір өнімге жұмсалатын ресурс Ресурс қоры
1-өнім 2-өнім
А 5 2 20
В 4 4 36
Пайда 7 3
(ақша.бірлігі)

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

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

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

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

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

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

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

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

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

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

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

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

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

TA 1 -X1 -X2 -X3
БА
1 7 2 1 3
2 -9 -4 3 2
3 2 1 2 -1
4 F 0 -1 -4 -3

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

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

TA 1 0 -X2 -X3
БА
1 3 -2 -3 5
2 -1 4 11 -2
3 Х1 2 1 2 -1
4 F 2 1 -2 -4

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

Кесте 3.7. Үшінші симплекс –кесте.

TA 1 -X2 -X3
БА
1 3 -3 5
2 -1 11 -2
3 Х1 2 2 -1
4 F 2 -2 -4

2-итерация.

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

1-итерация.

2-алгоритм.

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

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

Кесте 3.8. Төртінші симплекс –кесте.

TA
БА 1 -X2 -У2
1 0,5 24,5 2,5
2 0,5 -5,5 -0,5
3 Х1 2,5 -3,5 -0,5
4 F 4 -24 -2

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

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

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

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

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

Кесте 3.9. Бесінші симплекс –кесте.

1 -У1 -У2
TA
БА
1 Х2 149 249 549
2 Х3 3049 1149 349
3 Х1 3614 749 -214
4 F 22049 580 27249

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

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

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

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

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

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

1 -х1 -х2 ... -хj ... -хs ... -хn
0= a10 a11 a12 ... a1j ... a1s ... a1n
0= a20 a21 a22 ... a1j ... a2s ... a2n
--- --- --- ---- --- --- --- --- --- ---
0= ar0 ar1 ar2 ... arj ... ars ... arn
... ... ... ... ... ... ... ... ... ...
0= am0 am1 am2 ... amj ... ams ... amn

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

1. Шешуші элемент өзіне кері шамамен ауыстырылады: .

2. Шешуші қатардың қалған элементтері шешуші элементке бөлінеді:

3. Шешуші бағананың қалған элементтері шешуші элементке бөлініп, қарама-
қарсы таңбаман жазылады:

4. Кестенің қалған элементтері формуласымен есептеледі (i≠r,j≠s)

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

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

1 0 ... 0 -хr+1 ... -хn
х1= в10 в11 ... в1r в1r+1 ... в1n
... ... ... ... ... ... ... вrn
хr= вr0 вr1 ... вrr вrr+1 ... ---
0= вr+10 вr+11 ... вr+1r 0 ... 0
... ... ... ... ... ... ... ...
0= вm0 вm1 ... вmr 0 ... 0

Кесте 2 ден

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

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

х1=в10, х2=в20,...,х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)
H2 өзіндік емес алгоритмі ол өзінің жазбасында ғана жұмыс істейді.
4 5
5 5
a→b; b→bb; → b→b; b→bb → bb→b; b→bb → bbb→b; b→bb → ... (5)
Айталық, қолданылуы алгоритмге байланысты, сонымен қатар сөзге де
байланысты болса, онда өзіндік қолданыс тек қана алгоритмга байланысты
болады. Сол себепті бұл алгоритм корректілі сөзге қолданылады, ал өзінің
меншікті жазбасына берілген алгоитмі бойынша анықтайды.
3 мысал.
Өзіндік емес қолданыста МҚА – де құрып, оны кез ке,лген {a,b}
алфавитіндегі сөзге қолданамыз.
Шешімі:
Шешімі:
Ізделініп отырған МҚА – ны а және b символдарынан тұратын барлық сөзде
қолданамыз. Мұнда МҚА өзіндік қолданыстағы алгоритм болуы тиіс, ал *
символы алгоритмнің бастырмасы ретінде шығуы керек және осы символда МҚА
қайталануы керек. Мұндай алгоритмдерді көптеп ойлап табуға болады, бірақ
ішіндегі ең қарапайымы келесі алгоритм болып табылады:
* → *
4 мысал.
Бәрімізге белгілі өзіндік қолданыстағы алгоритмнің қиындығы алгоритмдік
түрде шешілмеуі. Сонымен қатар барлық алгоритмді анықтайтын жаопыға бірдей
тәсілі жоқ. Бірақ жеке мәселелерде бұл проблема шешілуі мүмкін. Мысалға бір
формуладан тұратын өзіндік қолданыстағы МҚА – ны шешуге болады. Бұл
тұжырымдаманы дәлелдеу керек.
Дәлелдеу:
МҚА мынадай түрде болсын делік: αβ немесе α→β. Мұнда келесі өзіндік
қолданыстағы алгоритмнің тексеруін жүргізе аламыз: егер жалғыз формула
қорытынды формула болса, немесе бұл қарапайым формулада α келесі оң жағына
өтпесе МҚА өзіндік қолданыстағы алоритм болып табылады, егнр ерісінше орын
алса онда өзіндік қолданыстағы алгоритм емес.

3.3. Алгаритмдердің эквиваленттілігі.

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

Алгоритмдердің эквиваленттілігінің нақты анықтамасы төмендегідей: Н1 және
Н2 алгоритмдері А алфавитіне қатысты эквиваленті, егер қолданылатын Н1 және
Н2 облыстары сәйкес А алфавитіне қатысты кез-келген Р сөзі үшін осы
облыстан Н1(Р)=Н2(Р) теңдігі орындалады.
Бұл анықтамада эквиваленттілік қайсысына орнатылса, сол алфавит
маңызды. Мысалы,
Н1: Н2:
Алгоритмдері алфавиті қатысты эквивалентті және алфавиті қатысты
эквиваленті немесе алфавитті сөздері олар ауыстырмайды, біранқ егер
кіретін немесе кіріс сөздерге тек в символы кіретін болса, онда Н1
тоқтайды, ал Н2 циклденеді.
5-мысал.
Келесі НАМ жұптары алфавитіне қатысты эквивалентті екенін анықтау:
1) Н1: Н2:

2) Н3: Н4:

3) Н5: Н6:
Шешуі:
Алгоритмдерді эквиваленттілікке тексеру кезінде олардың қолданылу облыстары
сәкес келетін тексеру керек. Н1 және Н2 алгоритмдер жағдайында. Бірінші
кіру символы а,в-ға өзгертілсе, бұл шарт орындалмайды. Н1-ді а және в
символдарынан барлық сөздерге қолданайық, ал Н2 құоамында а символы жоқ
сөздерге циклденеді, яғни Н1 және Н2 алгоитмдері эквиваленті емес.
Егер де қолдану облыстары сәйкес келсе, онда бірдей сөздер берілген
облыстардан, бұл алгоритмдер бірдей шешім беретінін көрсету керек.
Н3 және Н4 алгоритм жұптарында қолдану облысы бірдей ол тек бір ғана бос
сөзден құралған. Бос емес сөздерге бұл алгоритмдер әртүрлі циклденеді: Н3
әркезде а-ны в-ға, ал в-ны а-ға ауыстырады, онда Н4 барлық уақытта жаңа а
нмесе в символын қосады. Бірақ та циклдену кезінде мұндай әр түрлі тәртіп
алгоритмдердің эквиваленттілігін анықтау ешқандай роль атқармайды. Тоқтау
жағдайында алгоритмдер бірдей шығу сөздерін беру маңызды болып табылады. Н3
және Н4 жұптары үшін бұл шарт орындалады: олар қолданылатын жалғыз (бос)
сөзде, олар 1 және сол жауапты – бос сөзді береді. Яғни Н3 және Н4
алгоритмтдері эквивалентті.
Енді Н5 және Н6 алгоритм жұптарын қарастырамыз. Олар бір ғана қолданылу
облысы бұл алфавитердегі барлық көптеген сөздер. Бірақ та
эквиваленттің 2-ші шарты (бастапқы бірдей берілгендерде бірдей нәтижелер)
орындалмайды. Мұны дәлелдеу үшін бір ғана сөзді келтіру жеткілікті.
Алгоритмдер әртүрлі жауап беретін, мұндай сөзге мысалы аааа сөзі болуы
мүмкін:

Н5:

Н6:

Сонымен, Н5 және Н6 алгоритмдері эквивалентті емес.
3.4. Алгоритмдер композициясы

Нәтижеден белгілі болғандай бір функцияны басқа функцияларға
қолдануға болады, мысалы: sin(ctq x). Осыған сәйкес бірінші алгоритм Н1-дің
шығу сөзін басқа алгоритм Н2-ге беруге болады. Мұндай тізбектелген, яғни
бірінші Р1 алгоритмнің орындалуы, одан соң Н2 алгоритмінің орындалуы осы
алгоритмдердің композициясы деп аталады. Осылайша осы алгоритмдердің кез
келгені тұрақтылынып қалатынын ескеріп, оның композицизиясы да
тұрақталынады.
Бұл ұғынулар келесі әрекеттерден кейін анықталады:
Салыстырмалы А алфавитіндегі Н1 және H2 алгоритмдерінің композициясы деп
келесідей алгоритмдерді айтамыз, яғни алфавиттегі кез келген Р сөзіне
келесі А алгоритмінің қасеттері орындалса:
1) егер Н1 алгоритмі Р – ға тәуелді болса, онда Н – та Р – ға тәуелді
болады;
2) егер Н1 алгоритмі Р – ға тәуелді болса, онда Н2 Р – ға және оның сөзіне
тәуелді болады;
3) егер Н1 алгоритмі Р – ға тәуелді болса, онда Н2 Р – ға және оның сөзіне
тәуелді болса, онда мына теңсіздік орныдалады: Н(Р)=H2(H1(P));
Кезк елген қалыпты Н1 және H2 алгоритмдері үшін келесі теорема
орынды, қалыпты Н алгоритмі анықталады, яғни Н1 және H2 – нің
композициялары.
6 мысалы
Н алгоритмін тұрғызайық, берілген Н1 және H2 алгоритмнің командалары
болып табылады, (ав) алфавитіне тиісті.

Н1: H2:

Шешуі:
Ортақ жағдайда Н композициясын қарапайым жолмен, яғни Н1 және H2
алгоритмдерін өойп есептеп шығаруға болмайды. Мысалы: егер, ең алдымен Н1-
дің формуласын есептеп шығарсақ, содан кейін H2- ні есептеп шығарсақ, онда
Н12 алгоритмін аламыз, ал ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.