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

59435
знаков
11
таблиц
13
изображений

1.1 Сызықтық программалау есептері.

Қәзіргі кездегі ғылымдардың даму ерекшеліктерінің бірі-олардың әртүрлі салаларын зерттеуде математикалық әдістер мен есептеуіш техникаларының кеңінен қолданылуында. Егер бұдан бұрынғы уақыттырда математикалық амалдар мен әдістер тек астрономия, физика, химия ғылымдарында қолданылып келсе, соңғы кезде бұл ғылыми жетістіктер медицина, лингвистика және экономика ғылымының көптеген процестері мен құбылыстарын зерттеуде ұтымды пайдаланып жүр. Мұның өзі ақиқатты танып білуде әртүрлі ғылымдар саласында диалектикалық бірліктің күшейіп және теориялық көзқарастың тереңдей түсуінен деуге болады.

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

Адамзат қоғамы дами бастауынан үнемділік, тиімділік деген мәселелер бірге жасасып келеді. Үнемділік, тиімділіктің математикалық түбірі функциялардың экстремум мәндерімен тығыз байланысты. Экономикалық есептердің алғашқы үлгісі гректерде кездеседі. Ұзындығы белгілі l доғамен шектеуге болатын ең үлкен ауданды табу керек. Ең үлкен және ең кіші мәндерді табу есептері экономикалық мәселелерде жиі кездеседі. Мұндай экономикалық есептерді экономикалық-математикалық мделдеу пәні қарастырады.

Экономикалық-математикалық моделдеу математикада қарастырылатын экстремалдық есептер курсының бөлімі болып табылады. Экономикалық есептер үш топқа бөлініп қарастырылады: сызықтық программалау есептері, сызықтық емес программалау есептері және динамикалық программалау есептері.

Бұл көптен бері құлаш жайып, дамып келе жатқан ғылым. Бұл салада алғашқылардың бірі совет экономисті А.Н.Толстой (1930ж) еңбектері. Венгер математигі Б.Эгервари (1931ж) “таңдау проблемасы” есебінің математикалық қойылымын қарастырып, сызықтық программалау есебінің шешімін тапқан. Бұл есепті шешу әдісі осы ғалым құрметіне венгер әдісі деп аталады. Совет ғалымдары Л.В.Канторович, В.С.Немчинов, В.В.Новожилов, А.Л.Луръе және т.б. математиктер мен экономистердің жұмыстарында сызықтық және сызықтық емес программалаудың математикалық теориясы экономикалық проблемаларды зерттеудің әдістері ретінде дамып отырды. Бұл салада тек совет ғалымдары емес сонымен қатар басқа елдер ғалымдарының да атқарған қызметі мол. Солардың ішінде америка ғалымы Хичкок (1941ж) транспорт есебінің берілуін қойды, Данциг (1949ж) сызықтық программалау есебін шығарудың симплекс әдісін жасады. Сызықтық және сызықтық емес программалау есептерінің шығару әдістері Форд, Фалкерсон, Кун, Ламке, Гасс, Чарнес, Бил еңбектерінде берілді. Толық зерттелген есептер сызықтық программалау есептері. Динамикалық программалау есептері үлкен қарқынмен өрістеп келеді.

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

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

Берілген

1.jpg (1.1.1)

мақсат функциясына минимал мән әперетін және мына теңсіздіктерді:

2.jpg (1.1.2)

3.jpg (1.1.3) қанағаттандыратын 4.jpg

векторын табу.

Бұл жердегі 5.jpgберілген тұрақты сандар, оның үстіне m < n

Жоғарыда келтірілген мысалдарға сәйкес, (1.1.2), (1.1.3) теңсіздіктерін есептің шектеуіш шарты деп, ал (1.1.1)сызықтық формасын есептің мақсат функциясы деп атайды.

Сызықтық программалау есептерінде барлық 6.jpg деп жорамалдауға болады, өйткені олардың ішінде теріс сандар кездесетін болса, онда сәйкес теңдеуді (-I) көбейту арқылы 7.jpgді оң санға айналдыруға болады.

Жеке мысалдарда есептің негізгі (1.1.2) щарты бірнеше түрде берілуі мүмкін. Мысалы, есептің негізгі теңсіздіктері тек қана 8.jpgтүрінде немесе 9.jpgтүрінде жазылуы мүмкін. Сол себептен,есептің негізгі теңсіздіктерініңформасына қарай сызықтық программалау есептерін бірнеше түрге бөлуге болады.

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

10.jpg (1.1.4)

11.jpg (1.1.5)

12.jpg (1.1.6)

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

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

13.jpg

14.jpg

12.jpg

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

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

16.jpg

Онда осы теңсіздікке 17.jpg белгісізін қосу арқылы оны теңдікке айналдырамыз, яғни

18.jpg

осы теңсіздікті теңдеуге айналдырушы 19.jpg белгісізін есептің қосымша белгісізі деп атайды.

Енді есептің негізгі шарты теңдеу түрінде берілсін:

20.jpg

онда осы теңдеуді екі теңсіздіктер түрінде жазуға болады, яғни

21.jpg

соңғы теңсіздіктердің екіншісін (-I) көбейтіп, кез-келген теңдеудің төмендегі екі теңсіздіктер түрінде жазылатынын көреміз:

22.jpg

сонымен есебіміз канон түрінде берілсе, онда оның әрбір теңдеуіне екі теңсіздікті сәйкес қою арқылы стандартты түрге көшіруге болатынын, ал стандартты түрден канон түріне қосымша белгісіздер ендіру арқылы көшіруге болатынын көрдік. Осы тұрғыда ескерте кететін тағы бір жағдай, ол 23.jpg пен 24.jpgтің эквивалент екендігінде.

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

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

25.jpg

26.jpg

27.jpg

Қосымша 28.jpg және 29.jpg белгісіздерін бірінші және екінші теңсіздіктердің оң жағына қосып жазып, мынадай канон есебін аламыз:

25.jpg

31.jpg

Егер сызықтық программалау есебінің негізгі шарты (1.1.5) теңдеулер системасы түрінде беріліп, ал белгісіздерінің кейбіреулері үшін (1.1.6) теңсіздігі орындалмайтын болса, онда ол мысал канон түріндегі есепке жатпайды. Осындай есептерді толық канон түріне келтіру үшін оның барлық белгісіздері (1.1.3) шартын қанағаттандыратындай жағдай жасау қажет.

1.2 Сызықтық программалаудың негізгі теоремалары.

Сызықтық программалаудың негізін құрайтын теоремалармен танысайық:

1-теорема. Сызықтық программалау есебінің шешімдерінің жиыны – дөңес.

Дәлелдеу. Сызықтық программалау есебінің шешімінің сызықтық комбинациясы да сол есептің шешімі болатынын дәлелдеу қажет. Ол үшін 32.jpg векторлары сызықтық программалау есебінің шешімдері делік. Олай болса

33.jpg , 34.jpg

және

35.jpg , 36.jpg

Енді осы жоспарлардың кез-келген сызықтық комбинациясын қарастыралық:

37.jpg , 38.jpg

Осы жоспардың есептің шешімі болатынын көрсетелік. Ол үшін мына амалдарды орындаймыз.

39.jpg

бұдан AX=Bекендігі шығады.

Жорамалымыз бойынша 40.jpg

болғандықтан 41.jpg. Демек теорема дәлелденді.

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

Дәлелдеу. Теореманың шарты бойынша сызықтық программалау есебінің анықталу облысын төбелерінің саны шекті көпжақ құрайды. Жазықтықта көпжақтың көпбұрыш болатыны белгілі. Теореманың дәлелдеуін жазықтықта қарастыралық. Көпбұрышты Д – деп, ал оның шет нүктелерін 42.jpgдеп белгілейік. Есептің оптимал шешімі 43.jpg болсын (сурет 1). Олай болса кез-келген X44.jpg үшін 45.jpg болады.

46.jpg

сурет 1

Егер 43.jpg шеткі нүкте болса, онда теорема дәлелденеді. Енді 43.jpg ішкі нүкте болған жағдайды қарастыралық. Онда ол нүкте көпбұрыштың бұрыш нүктелерінің (шет нүктелері) сызықтық комбинация арқылы өрнектеледі, яғни

49.jpg

бұл жердегі

50.jpg

бізде 51.jpg сызықтық функционал болған себепті:

52.jpg

Барлық 53.jpg ішіндегі ең кішісін тауып, оны m-ге тең делік. Ал барлық 53.jpg ішіндегі ең кіші мәні 55.jpg үшін орындалсын делік. Демек

56.jpg

Енді соңғы өрнектегі барлық 53.jpg- ді 58.jpgге ауыстырсақ, онда мынадай теңсіздік аламыз:

59.jpg

яғни

60.jpg

Теореманің шарты бойынша 43.jpg оптимал жоспар. Ал соңғы теңсіздік көпбұрыштың шеткі нүктесінде басқа оптимал шешім болатынын көрсетеді. Бұл қарама-қайшылық 62.jpgдің шет нүкте екенін дәлелдейді.

Енді осы теореманың екінші жартысын дәлелдейік. Ол үшін 63.jpg функциясы бірнеше нүктеде минимал мән қабылдайды делік. Ол нүктелерді біз 64.jpg деп белгілейік. Демек

65.jpg

Енді Xнүктесі осы нүктелердің дөңес сызықтық комбинациясы делік, яғни

66.jpg

функционалдың осы нүктедегі мәнін қарастырамыз:

67.jpg

Бұдан 64.jpg нүктелерінің дөңес сызықтық комбинациясының да есептің минимал мәнін беретінін көрдік. Теорема дәлелденді.

3-теорема. Егер k(k=n) өзара тәуелсіз векторлар системасы 69.jpg берілген болып, олар үшін 70.jpg теңдігі барлық 71.jpgтар үшін орындалса, онда 72.jpg векторы есептің анықталу облысын беретін көпжақтың шеткі нүктесі болады.

Дәлелдеу. 73.jpg нүктесі анықталу облысының ішкі нүктесі деп жорамалдайық. Олай болса ол нүкте сол облыстың екі шеткі 32.jpg нүктелерінің сызықтық комбинациясы түрінде бейнеленеді, яғни

37.jpg

76.jpg

Берілген 77.jpg векторының n-k компоненті нөлге тең болғандықтан, ал 32.jpg векторларының компоненттерінің теріс болуы мүмкін емес екенін және 0<79.jpg<1 екенін ескерсек, онда 32.jpg векторларының да n-k компоненттері нөлге тең болады. Демек

81.jpg

82.jpg

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

33.jpg

35.jpg

орындалады. Осы теңдіктерді векторлар түрінде жазсақ, онда:

85.jpg

86.jpg

осы екі теңдеудің айырымы:

87.jpg

теореманың шарты бойынша 69.jpg векторлар системасы сызықтық тәуелсіз. Демек соңғы теңдік тек қана

89.jpg

болғанда орындалады.

Бұдан

90.jpg

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

4-теорема. Егер 91.jpg шеткі нүкте болса, онда барлық оң

болатын 92.jpgтерге сәйкес келетін векторлар өзара сызықтық тәуелсіз.

Дәлелдеу. X векторының алғашқы компоненті нөлге тең емес делік. Олай болса алғашқы 93.jpg векторлары үшін

94.jpg

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

96.jpg (1.2.2)

теңдігі орындалады. Теореманың шарты бойынша

97.jpg

Кез-келген 98.jpg санын алып, оны (1.2.2) теңдеуіне көбейтеміз деодан шыққан қорытындыны 99.jpg теңдеуіне бірінші, қосу, сосын алу нәтижесінде мынадай теңдеулер аламыз:

100.jpg

101.jpg

Соңғы теңдеулер системасы 102.jpg теңдеуінің екі шешімі бар екенін және олардың

103.jpg

104.jpg

тең екенін көрсетеді. Бұл жерде барлық 105.jpg болғандықтан 106.jpgді 107.jpg және 108.jpg векторларының барлық компоненттері оң болатындай етіп таңдап алуға болады. Бұл жағдайда 107.jpg мен 108.jpg жоспар болады, ал

111.jpg

Демек X векторы басқа екі нүктенің сызықты комбинациясы түрінде бейнеленіп отыр. Бұл жағдай теореманың шартында айтылған, X шеткі нүкте деген шартқа қайшы келеді. Демек X шеткі нүкте (бұрыш нүктесі).

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

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

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

112.jpg

113.jpg (1.3.2)

114.jpg (1.3.3)

Жүйе (1.3.2), (1.3.3) үйлесімді, шешімдер көпбұрышы шектеулі делік. Әрбір теңсіздік (1.3.2), (1.3.3) жарты жазықтықты шеттік түзулерімен 115.jpg, 116.jpg, 117.jpg бірге анықтайды. Сызықтық функция (1.3.1) Z=h мәніндегі түзулерді береді; 118.jpg. Шектеулер жүйесінің шешімдер көпбұрышын (1.3.2) және сызықтық функцияның (1.3.1) Z=0 мәніндеі графигін тұрғызайық. Онда қойылған сызықтық программалау есебіне мынадай геометриялық мағына беріледі. 118.jpg тірек түзуі және мұнда функция Z min мәнін қабылдайтын шешімдер көпбұрышының нүктесін табу керек.

120.jpg мәндері N = (121.jpg) векторы бағытында өсетіндіктен, Z=0 түзуін N бағытында өзіне-өзін параллель жылжытамыз.

Сурет 1-ден шешімдер көпбұрышының екі тірек түзуі (А және С нүктелерінде) болатындығын, әрі min мәні қабылданатын 122.jpg нүктесінің координаталарын АB және AE түзулерінің теңдеулер жүйесін шешу арқылы табу керектігін көреміз.

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

1 – жағдай. 118.jpg түзуі N векторы бағытында немесе оған қарама-қарсы бағытта қозғала отырып шешімдер көпбұрышын кесіп отырады және бірде-бір нүктесінде оған тірек болмайды. Бұл жағдайда сызықтық функция шешімдер көпбұрышында жоғарыдан да, төменнен де шектеусіз (сурет 2).

2 – жағдай. Түзу қозғала отырып, шешімдер көпбұрышына тірек болады (сурет 3). Онда облыс түріне байланысты сызықтық функция жоғарыдан шектеулі және төменнен шектеусіз (сурет За), төменнен шектеулі және жоғарыдан шектеусіз (сурет 3б) немесе жоғарыдан да, төменнен де шектеулі (сурет 3в) болуы мүмкін.

124.jpg

125.jpg

126.jpg

сурет 3

Мысалдар.

1. Шикізатты пайдалану есебі.

Екі түрлі 127.jpg, Р2 өнім шығару үшін үш түрлі шикізат 128.jpg қолданылады. Шикізат қорлары, әрбір өнімнің бір өлшемі үшін жұмсалатын әрбір шикізат шамасы және өнімнің бір өлшемін өткізуден түсетін пайда шамасы кестеде көрсетілген. Өнімді max пайда алатындай етіп, ұйымдастыру қажет.

Шикізат

түрлері

Шикізат

Қоры

Өнім өлшемін жасауға жұмсалатын шикізат мөлшері

129.jpg

130.jpg

131.jpg

6

1

1

132.jpg

10

3

1

133.jpg

20

2

5

Өнім өлшемінен түсетін пайда

10

8

Шешуі. 129.jpg -ден 135.jpg, Р2 -ден х2 мөлшерінде өнімдер дайындалсын. Өнімнің бір өлшем шамасын дайындауда жұмсалатын шикізаттар мөлшерін жөне олардың қорларын: ескерсек келесі шектеулер жүйесін аламыз

136.jpg

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

Есептің мақсаты, өнімдерді өткізуден түсетін max пайданы, екі айнымалының 135.jpg және х2 функциясы деп қарастырамыз. P1 өнімінің х1 мөлшері өткізгенде 10х1, Р2 өнімінің х2 мөлшері өткізгенде 8х2, барлығы, қосындыда Z=10x1+8x2 (теңге) пайда келтіреді. Сонымен, шектеулер жүйесінің

138.jpg

сызықтық функция Z=10x1+8x2139.jpgmax мәнін қабылдайтын нақты 140.jpg шешімдерін табу керек. Шешімдер көпбұрышын шекаралық түзулер арқылы

141.jpg142.jpg, 143.jpg144.jpg145.jpg146.jpg147.jpg

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

148.jpg

N = (10; 8) = 2(5; 4) векторын және 149.jpg (Z) түзуін тұрғызамыз. (Z) түзуін өзіне-өзін параллель N векторы бағытында жылжыта отырып, шешімдер көпбұрышының В нүктесінде тірек түзуіне айналып, бұл нүктеде функция Zmax мәнін қабылдайтынын көреміз.

В нүктесі 150.jpg және 145.jpg түзулердің қиылысында жатқандықтан, оньң координаталарын тендеулер жүйесін

152.jpg

шешіп табамыз 153.jpg154.jpg. Есептің оптималдық шеімі 153.jpg154.jpg, Zmax157.jpg.

Сонымен 47,69т. көлеміндегі пайда келтіру үшін 158.jpg мөлшерінде 129.jpg, 160.jpg мөлшерінде Р2 өнімдерін шығаруды жоспарлау тиімді.

2.Рацион құру есебі.

Бордақылауда әрбір жануар күніне ең кемінде 10 өлшем S1, 8 өлшем S2 және 10 өлшем S3 қоректік заттарын қабылдауы тиіс. Рацион екі түрлі жемнен құрылады. Әрбір жемнің килограмындағы қоректік заттардың мөлшері және жемдердің бағалары кестеде берілген.

Қажетті қоректік заттары жеткілікті және жалпы шығын min-ды болатын күндік рацион құру керек.

Есептің математикалық моделін құрайық.

Қоректік заттар

1 кг жем қүрамындағы қоректік зат мөлшері

жем I

жем II

S1

2

1

S2

1

1

S3

1

4

Жем кг-ның бағасы

3

4

Күндік рациондағы жемдер тиісінше х1 және х2 кг десек, кестедегі цифрлар арқылы қоректілік сақталу үшін

161.jpg

теңсіздіктерінің орындалуы қажетті. Егер жем рационда қолданылмаса х1162.jpg 0 немссе х2162.jpg 0 болады, кері жағдайда 164.jpg немесе 165.jpg. Жалпы жағдайда, 166.jpg, 167.jpg шарттары орынды.

Есептің мақсаты күндік рационға min шығын жұмсау болғандықтан, рацион құнын 168.jpg сызықтық функциясы арқылы анықтап, осы функцияның min мәнін табу талап етіледі. Есеп көп шешімді, х1 және х2 шексіз көп мәндер қабылдауы мүмкін. Сонымен, теңсіздіктер жүйесінің

161.jpg

170.jpg167.jpg

сызықтық функцияға 172.jpg мәнін беретін шешімдерін табу керек.

Шешуі. 135.jpgО174.jpg координаталар жүйесінде шекаралық түзулерді

141.jpg176.jpg,

143.jpg178.jpg,

145.jpg180.jpg,

181.jpg182.jpg

және осы түзулерге қарағанда теңсіздіктер анықтайтын жарты жазықтықтар қиылысында шешімдер көпбұрышын тұрғызамыз. Нәтижесінде A,B,C,D бұрыштық нүктелері (төбелері) болатын, шектеусіз көпбұрышты облысты аламыз. N(3,4) векторын және 183.jpg (Z) түзуін тұрғызып, Z түзуін өзіне-өзін параллель N векторы бағытында жылжыта отырып, шешімдер көпбұрышының С нүктесінде алғаш тірек түзуіне айналатынын көреміз (сурет 5). Түзуді әрі қарай жылжыта берсек, сызықтық функцияның мәні шешімдер көпбұрышының нүктелерінде өсе бастайды. Демек С нүктесінде сызықтық функция min мәнін қабылдайды. Бұл нүкте 184.jpg145.jpg түзулердің қиылысында жатқандықтан

186.jpg

теңдеулер жүйесін шешу арқылы координаталарын 187.jpg , 188.jpg табамыз. Табылған мәндерді сызықтық функцияға қойсақ, 189.jpg аламыз.

Сонымен min шығын жұмсау үшін күндік рационды 190.jpg кг I – жемнен, 191.jpg II – жемнен құру қажет.

192.jpg

Жалпы графиктік әдіспен n-m=2 болатын сызықтық программалау есебін шеше аламыз. Мұндағы n – айнымалылар (белгісіздер) саны, m – сызықтық тәуелсіз тендеулер саны.

Сызықтық программалау есебін қарастырайық.

193.jpg

194.jpg

Бұндағы барлық теңдеулер сызықтық тәуелсіз және n-m=2 ұатынасы орындалсын.

Жордан – Гаусс әдісімен m жою барсында алғашқы m айнымалылар x1, x2, … , xm – базистік, ал соңғы екі айнымалы xm+1, xn – еркін айнымалыларға айналсын делік, яғни жоғарыда көрсетілген шектеулер мына түрге келтірілсін

195.jpg (1.3.4)

Түрленген жүйе (1.3.4) теңдеулері арқылы сызықтық функцияны тек еркін айнымалылармен өрнектейміз де, базистік айнымалыларды 196.jpg шығарып тастап, теңсіздіктермен берілген шектеулерге көшеміз. Ақырында келесі есепті аламыз.

197.jpg

198.jpg

бұл есепте екі айнымалы ғана болғандықтан графиктік әдіспен шеше аламыз. Оптималдық хm+1 және хn мәндерін тауып, (1.3.4)-ге қою арқылы, x1,x2,...,xm оптималдық мәндерін табамыз.

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

Сызықтық программалау есебінің оптималдық шешімі тірек шешімдерінің ішінен іздестіріледі, әрбір тірек шешімі берілген n векторлар 199.jpg жүйесіндегі m сызықтық тәуелсіз вектролармен анықталғандықтан, олардың саны 200.jpg терулерінің санынан аспайды.

m және n сандары жеткілікті үлкен болғанда оптималдық шешімді барлық тірек шешімдерін құру арқылы іздестру өте қиын.

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

201.jpg

202.jpg

есебін қарастырайық және мұндағы 203.jpg, 204.jpg болсын.

Шектеулер жүйесінің алғашқы m векторлары бірлік векторлар балсын делік. Онда есеп мына түрде қойылады

201.jpg (1.4.1)

206.jpg (1.4.2)

207.jpg (1.4.3)

Теңдеулер жүйесін (1.4.2) векторлық түрде жазайық

208.jpg (1.4.4)

мұндағы

209.jpg, 210.jpg, … , 211.jpg, 212.jpg, … , 213.jpg, 214.jpg

m-өлшемді кеңістіктің сызықтық тәуелсіз 215.jpg векторлары осы кеңістіктің базисін жасайтындықтан, (1.4.4) жіктелуіндегі 216.jpg айнымалыларын базистік деп, 217.jpg еркін айнымалыларын нөлге теңестірп, 218.jpg болғандықтан алғашқы

219.jpg (1.4.5)

шешімін аламыз. Осы шешімге сәйкес

220.jpg (1.4.6)

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

Бастапқы тірек шешімнен (1.4.5) келесі тірек шешімді қалай құратындығын қарастырайық. m-өлшемді кеңістіктің (1.4.4) өрнектегі әрбір векторы базистік 215.jpg векторлары арқылы бір ғана түрде былай жіктеледі

223.jpg, 224.jpg

Базиске енбеген, мысалы 225.jpg векторының,

226.jpg (1.4.7)

әйтеуір бір коэфифициенті 227.jpg оң таңбалы болсын делік. Әзірге белгісіз 228.jpg шамасына (1.4.7) теңдікті көбейтіп, (1.4.6) теңдіктен шегерсек,

229.jpg (1.4.8) теңдігін аламыз. Сонымен

230.jpg

Векторының компоненттері теріс таңбалы болмаса, шешімді береді. 228.jpg болғандықтан, 232.jpg- векторының теріс таңбалы 227.jpg-лер енетін компоненттері теріс таңбалы бола алмайды. Сондықтан кезкелген 234.jpg үшін

235.jpg (1.4.9) болатындай 228.jpg мәнін табу қажет. (1.4.9) теңсіздіктен

237.jpg

демек

238.jpg, (1.4.10)

234.jpg шартын орындайтын кезкелген 240.jpg үшін 232.jpg векторы есептің шешімін береді.

Тірек шешмінің m+1 оң таңбалы компоненті болмайтындықтан, 232.jpg шешімінің 243.jpg , 244.jpg , 245.jpg компоненттерінің кемінде біреуін нөлге айналдыру қажет. (1.4.10) теңсіздіктегі 246.jpg мәнін алсақ 232.jpg шешімінің min қабылдайтын компоненті нөлге айналады. Бұл компонент бірінші орындағы, яғни 248.jpg болсын делік. 249.jpg мәнін (1.4.8)-ге қойып

250.jpg

жіктелуін аламыз, бұл жаңа тірек шешімі

251.jpg

сәйкес. Мұндағы

252.jpg , 253.jpg254.jpg

240.jpg арқылы базистен векторды шығарып, орнына жаңа вектор енгізуді бізде Жордан – Гаусс әдісімен бір базистен екінші базиске көшу болғандықтан, 256.jpg векторлар жүйесі сызықты тәуелсіз және жаңа базисті береді. Жаңа тірек шешімді құру базиске енгізілетін векторды таңдаудан және базистен шығарылатын векторды анықтаудан тұрады. Симплекс әдісінің негізгі элементтерінің бірі базиске енгізілетін векторды анықтау белгісі. Егер 225.jpg базиске енгізілетін вектор ретінде анықталып, оның жіктелуіндегі (1.4.7) барлық

258.jpg

болса, онда (1.4.8) жіктелуінен бір векторды шығаратындай 228.jpg таңдау мүмкін емес. Бұл жағдайда 260.jpg шешімі m+1 оң таңбалы компонентті, ал

261.jpg

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

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

Мысал.

263.jpg

264.jpg

Тірек шешімін құрып, жаңа тірек шешіміне көшу керек.

Шешуі. Теңдеулер жүйесін векторлық түрде жазсақ

ЕСЕП ЖАЗ

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

265.jpg

266.jpg, 204.jpg

268.jpg , 224.jpg

есебінің шешімдері бар және әрбір тірек шешімі ұүнарлы делік. Онда

270.jpg

тірек шешіміне

220.jpg (1.4.11)

272.jpg (1.4.12)

273.jpg , 204.jpg

ал кезкелген 275.jpg векторына берілген 276.jpg базисінде

277.jpg (1.4.13)

278.jpg (1.4.14)

279.jpg

теңдіктері тиесілі.

Сызықтық функцияның 275.jpg векторына сәйкес коэффициентін 281.jpg деп белгілейміз. Онда келесі теорема орындалады.

Теорема 1. Егер әйтеуір бір 275.jpg векторына 283.jpg шарты (белгісі) орындалса, онда 284.jpg шешімі оптималды емес және 285.jpgтеңсіздігі орындалатын Х шешімін құруға болады.

Дәлелдеуі. (1.4.13) және (1.4.14) теңдіктерін 228.jpg -ға көбейтіп, (1.4.11) және (1.4.12) теңдіктерінен шегереміз

287.jpg, (1.4.15)

288.jpg (1.4.16)

Теңдіктің екі жағына да 289.jpg қосылған. Бұл теңдіктердегі 290.jpg, 291.jpg , сондықтан 292.jpg - лер түгелімен дерлік оң таңбалы болатындай 228.jpg- ны табуға болады. Демек, есептің жаңа шешімін

294.jpg

және оған (1.4.16)- шы өрнек бойынша тиісті сызықтық функцияның

295.jpg

мәнін аламыз. Теорема шартында 296.jpg және 228.jpg , онда

285.jpg.

Салдар. Егер әйтеуір бір шешім 284.jpg-дің базисінде барлық 275.jpg, 279.jpg векторларының жіктеулеріне

302.jpg (1.4.17)

шарты (белгісі) орындалса, онда шешім 284.jpg- оптималды.

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

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

Сызықтық программалаудың сызықтық функция max –мын мәнін табу есебі үшін келесі теорема орынды.

Теорема 2. Егер әйтеуір бір 275.jpg векторына 302.jpg шарты (белгісі) орындалса, онда 284.jpg шешімі оптималды емес және 308.jpg болатын Х шешімін құруға болады.

Дәлелдеуі. Теорема 1 –дегідей.

Салдар. Егер әйтеуір бір шешім 309.jpg-дің базисінде барлық 310.jpg, 311.jpg векторларының жіктеулеріне

312.jpg (1.4.18)

Шарты (белгісі) орындалса, онда шешім 309.jpg оптималды.

(1.4.18) теңсіздіктері сызықтық функцияның max мәнін табу есебінің оптималдық шарты (белгісі).

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

д

Сызықтық программалаудың транспорт есебі транспорт пен өнеркәсіп және өндірістің түрлі мәселелерінің теориялық зерттеулерінде және практикада жиі қолданылады. Әсіресе өнеркәсіп пен ауылшаруашылық өнімдерін жеткізуді рационализациялауда, сондай – ақ жүк айналымдарын оптималды жоспарлауда және транспорттың басқа да әртүрлі жұмыстарында ерекше маңызы бар. Барлығы m ұсынушыда, 314.jpg-де 315.jpg, 316.jpg,жинақталған біртекті заттарды, барлығы n тұтынушыға, 317.jpg-де 318.jpg, 319.jpg жеткізу керек. Бірлік жүкті і - ұсынушыдан j-тұтынушыға тасымалдау бағасы 320.jpg белгілі.

Тұтынушылар сұранысын толық қанағаттандыратын және бағасы минималды болатын, барлық жүкті тасымалдау жоспарын құру қажет.і - ұсынушыдан j-тұтынушыға тасымалдауға жоспарланған жүкті 321.jpg деп белгілеп, есептің шартын жоспарлау матрицасы аталатын кестемен жазуға болады.

Ұсынушылар

Тұтынушылар

Қорлар

322.jpg

323.jpg

324.jpg

A1

325.jpg

326.jpg

x11

327.jpg

328.jpg

329.jpg

330.jpg

331.jpg

А2

c21

x21

c22

х22

c2n

x2n

332.jpg

...

Ат

cm1

xm1

cm2

xm2

cmn

xmn


333.jpg

Сұраныстар

334.jpg

335.jpg

336.jpg

337.jpg

Есептің математикалық моделін құрайық .

i-ұсынушыдан j-тұтынушыға тасымалданатын жүк xij, оның тасымал бағасы Cijxij. Барлық жүкті тасымалдау бағасы

338.jpg

Шектеулер жүйесін есептің келесі шарттарынан аламыз:

1) Барлық жүк тасымалдануы керек, яғни

339.jpg

(бұл теңдеулер кестенің жолдарынан алынады).

2) Сұраныстар түгелімен қанағаттандырылуы керек, яғни

340.jpg

(бұл теңдеулер кестенің бағандарынан алынады).

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

Сызықтық функцияның

338.jpg

ең кіші мәнін келесі шектеулерде

342.jpg

343.jpg

344.jpg

табу керек.

Қарастырып отырған моделде қорлар қосындысы сұраныстар қосындысына тең деп есептелінеді.

345.jpg

Бұндай модель тұйықталған (жабық) деп аталады.

Теорема.

Қорларының қосындысы сұраныстарының қосындысына тең болатын кез-келген транспорт есебінің шешімі бар.

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

Дәлелдеуі.

346.jpg

делік , онда:

347.jpg

шамалары (2.1.1), (2.1.2) шектеулер жүйелерін қанағаттандыратындықтан, есептің шешімі болады. Шындығында да, 321.jpg мәндерін (2.1.1) және (2.1.2)-ке қойсақ, табамыз

349.jpg

350.jpg

351.jpg мәнін алып, сызықтық функцияны бағаласақ, (2.1.2) теңдік арқылы мынаны аламыз

352.jpg

Дәл сол сияқты 353.jpg мәнін қолдансақ

354.jpg

Соңғы екі теңсіздікті біріктіріп қарастырсақ 355.jpg теңсіздігін аламыз, яғни сызықтық функция транспорт есебі шешімдерінің жиынында шектеулі.

2.2 Алғашқы таяныш жоспарын құру әдісі.

Оптималдық шешімге бастапқы тірек шешімін құрумен жуықтайды.

Шектеулер жүйесінің (2.1.1)-(2.1.2) m, n белгісіздері, m+n тендеулерімен берілген, сондай-ақ (2.1.3) қатынаспен байланысты.

Жүйенің (2.1.1) және (2.1.2) бөліктерінің теңдеулерін өз алдыларына қосса, бірдей екі тендеу алынады. Бұл жүйенің сызықты тәуелділігін көрсетеді, егер біреуін шығарып тастасақ, онда шектеулер жүйесінің m + n – l сызықты тәуелсіз теңдеулері қалады. Сонымен, транспорт есебінің құнарлы тірек шешімінің m + n – l оң таңбалы компоненті немесе тасымалы бар, яғни (321.jpg), 357.jpg матрицасының m + n – l элементі ғана оң таңбалы да, қалғандары нөлге тең.

Транспорт есебінің шарты және тірек шешімі кестеде жазылса үлес бөлінген клетка бос емес, үлес бөлінбегені бос клетка деп аталады. Құнарлы тірек шешімінде m + n – l бос емес клетка базистік айнымалыларға тән. Шектеулер (2.1.1), (2.1.2) түрінде жазылса, тірек шешіміне енген базистік айнымалыларға сызықты тәуелсіз векторлар жүйесі тән. Транспорт есебі кесте түрінде жазылса, үлестірулер тірек шешімін береді, егер ациклды болса, яғни төбелері бос емес клеткалардан тұйық цикл құруға болмаса.

Бір бағанда немесе бір жолда көрші екі клеткасы ғана орналасатын, сондай-ақ соңғы клеткасы бірінші клеткасымен бір жолда немесе бір бағанда жататын 358.jpg клеткалар жиынтығы цикл деп аталады.

Циклды құру кезкелген бос емес клеткадан басталады. Бағанмен (жолмен) келесі бос емес клеткаға, одан тік бұрылып жолмен (бағанмен) келесі бос емес клеткаға, тағы сол сияқты көшулермен бастапқы клеткаға оралуға тырысады. Қайта оралу мүмкін болса цикл алынғаны, үлестіру тірек шешімі емес. Тік бұрылатын клеткалар циклдың төбелерін анықтайды. Кері жағдайда үлестіру тірек шешімі болады.

Транспорт есебінің бос емес клеткалары m + n – l – ден артық кез-келген үлестіруі тірек шешімі бола алмайды, себебі оған сызықты тәуелді векторлар жүйесі тән. Бұндай үлестіруде, кестеде, кез келген уақытта бос емес клеткалар санын m + n – l -ге дейін кемітуге көмектесетін тұйық цикл құруға болады.

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

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

Солтүстік-батыс бұрыш әдісі.

Жүк бірінші тұтынушыға сұранысы орындалғанша түгелдей бірінші ұсынушыдан, жетпегені екіншісінен, ол да жетпесе үшіншісінен, т.с.с., жасалады.

Егер бірінші ұсынушының қоры сұраныстан артық болса, қалғаны екінші тұтынушыға, одан қалғаны үшіншіге, т.с.с., барлық қоры біткенше тасымалданады.

Қалған тұтынушылар мен ұсынушылар арасындағы тасымал да осы тізбекпен жалғасады. Тасымалдау тізбегі транспорт есебі кестесінің солтүстік-батыс бұрышынан басталып, оңтүстік-шығыс бұрышында аяқталады.

Мысал.

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

Ұсынушылар

Тұтынушылар

Қорлар

359.jpg

360.jpg

361.jpg

362.jpg

363.jpg

2

4

7

9

200

364.jpg

5

1

8

12

270

365.jpg

11

6

4

3

130

Сұраныстар

120

80

240

160

600

Шешуі. 366.jpg367.jpg – ұсынушыдан 368.jpg – тұтынушыға тасымал көлемі болсын. Барлық жүкті тасымалдау бағасы

369.jpg

болатындай келесі шектеулер жүйесінің шешуін табу керек

370.jpg

371.jpg

Ұсынушылар

Тұтынушылар

Қорлар

359.jpg

360.jpg

361.jpg

362.jpg

363.jpg

2

120

4

80

7

9

200

364.jpg

5

1

8

240

12

30

270

365.jpg

11

6

4

3

130

130

Сұраныстар

120

80

240

160

600

Бірінші ұсынушының қоры 379.jpg= 200 тұтынушының сұранысы 380.jpg= 120, 381.jpg клеткасына 120 тасымалданып, бағаннің басқа клеткалары сызылады, қалдық 382.jpg екінші тұтынушыға тасылады. Екінші тұтынушы сұранысы 383.jpg384.jpg қалдығымен жабылады, сонымен 385.jpg клеткасына 80 тасымалданып, 360.jpg бағанының қалған клеткалары сызылады. Үшінші тұтынушының сұранысы 387.jpg екінші ұсынушының қорынан 388.jpg кем, сұраныс түгелімен орындалып, 361.jpg бағанының қалған клеткалары сызылады, қалдық 390.jpg келесі сұраушыға 362.jpg өтеді. Төртінші тұтынушының сұранысы үшінші 365.jpg ұсынушының қоры 393.jpg және 390.jpg қалдығымен орындалады.

Құрылған тасымалдың жалпы құнының үлестері бар клеткалардың бұрыштарындағы сандар көбейтінділерінің қосындысынан аламыз:

395.jpg

Осы тасымал жоспарының есептің тірек шешімі екндігіне көз жеткізейік. Бос емес клеткаларды бағандар және жолдармен байланыстырып, тұйық цикл, яғни кез келген бос емес клеткадан бастап қозғалып, осы клеткаға оралатын бос емес клеткалар тізбегін құру мүмкін емес. Ол түгілі 381.jpg клеткасынан баған бойымен келесі бос емес клеткаға да бара алмаймыз. Демек, бұл тасымал тірек шешімін, бос емес клеткалар саны m + n – l = 6 санынан кем болғандықтан құнарсыз тірек шешімін береді. Бос емес клеткалар саны 5.

Бұл үлестіру тасымалдау бағалары ескерілмей орындалғандықтан оптималды шешімнен алшақ болуы мүмкін. Осы бағалар ескерілетін кейбір әдістерді қарастырайық.

Бұндай әдістердің бірі кіші құн әдісі болып табылады.

Кестедегі ең кіші құн жазылған (397.jpg) клеткасына 398.jpg сандарының кішісі жазылып, қоры түгелдей тасылған ұсынушы жолы, немесе сұранысы түгелденген тұтынушы бағаны, немесе 399.jpg болса жол да, баған да сызылады.

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

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

400.jpg

циклқұрумүмкінемесүлестіруіналамыз. Мұндағыm + n – l саныүлестірулерсанынатең, яғниқұнарлытірекшешіміалынғаны.

Ұсынушылар

Тұтынушылар

Қорлар

359.jpg

360.jpg

361.jpg

362.jpg

363.jpg

2

120

4

7

80

9

200

364.jpg

5

1

80

8

30

12

160

270

365.jpg

11

6

4

130

3

130

Сұраныстар

120

80

240

160

600

Тасымалдың жалпы құны

408.jpg

Солтүстік-батыс бұрыш әдісімен алынған сандағыдан артық, оптималдық шешімнен алшақтай түскен.

Әрбір бағанның ең кіші құн орналасқан клеткаларына V белгісі қойылып, дәл осылай белгілеу әрбір жолдың клеткаларына да қайталанады. Нәтижесінде қос VV белгісі бар клеткалар шығады. Тасымалдау әуелі қос VVбелгілі клеткаларға, әрі қарай кіші құн әдісімен жасалады. Ұсынушы қоры түгесілсе-жол, тұтынушы сұранысы орындалса-баған сызылып отырады. Бұндай әдіс қос мүмкіндік әдісі болып табылады.

Жоғарыда келтірілген есепті қос мүмкіндік әдісімен де қарастырайық.

Ұсынушылар

Тұтынушылар

Қорлар

409.jpg

410.jpg

411.jpg

412.jpg

413.jpg

VV 2

120

4

7

80

9

200

414.jpg

5

VV 1

80

8

160

12

30

270

415.jpg

11

6

V 4

VV 3

130

130

Сұраныстар

120

80

240

160

600

Алдымен 416.jpg клеткаларын толтырамыз. 417.jpg клеткасы түгесілген қорға байланысты 418.jpg жолымен бірге сызылады. Кестенің қалған бөлігін кіші құн әдісімен толтырамыз: 419.jpg. Тасымалдау нәтижесінде

420.jpg

Құнарлы тірек шешімін алдық. Оның құны

421.jpg

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

2.3 Потенциялдар әдісі.

Теорема – 1.

Транспорт есебінің шешуі 423.jpg оптималды болса, онда оған

424.jpg, егер 425.jpg және

424.jpg, егер 427.jpg

428.jpg429.jpg

Шарттарын қанағаттандыратын, барлығы m + n 430.jpg және 431.jpg сандарының жүйесі сәйкес. Сандар 430.jpg және 431.jpg тиісінше ұсынушылар және тұтынушылар потенциалдары деп атайды.

Дәлелдеуі.

434.jpg

435.jpg

436.jpg, 428.jpg429.jpg

Транспорт есебін сызықық программалаудың қайсыбір бастапқы есебіне қосалқы деп қарастырсақ, онда бастапқы есеп

439.jpg

440.jpg428.jpg429.jpg

түрінде беріледі.

443.jpg - қосалқы есептің оптималды шешуі, сондықтан

444.jpg бастапқы есептің шешуі, қосалқылық теоремасына сәйкес 445.jpg немесе

446.jpg447.jpg.

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

448.jpg449.jpg

450.jpg451.jpg

Сонымен, бастапқы тірек шешімі оптималды болу үшін, келесі шарттардың орындалуы қажетті:

а) үлесті клетка үшін потенциалдар қосындысы тасымалдау бағасына тең, яғни

452.jpg ( * )

б) үлессіз клетка үшін потенциалдар қосындысы тасымалдау бағасынан аспауы қажет, яғни

453.jpg ( ** )

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

Потенциялдар жүйесін құрып, шешімді оптималдылыққа тексереді. Әдіс алгоритімын мысалмен қарастырайық. Транспорт есебінің кестесіне потенциялдар жазылатын бір жол және бір баған қосылады.

Потенциалдар жүйесін құрып көрейік.

Құнарлы тірек шешімінің бос емес (үлесті) клеткаларына белгісіздерінің саны m+n сызықты тәуелсіз m+n – 1 теңдеулер жүйесі

454.jpg ( * )

428.jpg456.jpg

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

457.jpg потенциалы белгілі десек, онда 459.jpg;

егер460.jpg потенциалы белгіліболса, онда 461.jpg.

Сонымен, белгісіз потенциал үлесті клетканың 462.jpg шамасынан белгілі потенциалды шегерумен табылады.

Кесте 1

Тұтынушылар

463.jpg

464.jpg

465.jpg

466.jpg

Ұсынушылар

467.jpg

457.jpg

469.jpg=2

470.jpg=4

471.jpg=11

472.jpg=15

Қорлар

473.jpg

474.jpg=0

2

120

4

475.jpg476.jpg -

80

7

477.jpg


4

9

478.jpg479.jpg480.jpg +

6

200

481.jpg

482.jpg=-3

5

1

483.jpg +

0

8

240

12

-

30

270

484.jpg

485.jpg=-12

11

6

4

3

130

130

Сұраныстар

120

80

240

160

Кесте 1 – де тірек шешімі құнарсыз, бір үлесті клетка жетіспейді (m+n-1=6, үлес саны 5 ). Сондықтан, үлесті клеткаларының саны ең көп жолды, 473.jpg

немесе 481.jpgжолын таңдаймыз да, 474.jpg=0 ( немесе 482.jpg=0) деп аламыз. 474.jpg=0 мәніне байланысты 491.jpg мәндері табылады:

492.jpg493.jpg

473.jpg жолы, 495.jpg бағандары арқылыбасқа потенциалдарды табу мүмкін емес. Бұл үзіліс бастапқы тірек шешімінің құнарсыздығынан. Құнарсыздықты нөлді үлестіріп жоюға болады. Нөл бөлінетін клеткалар жалған үлесті деп аталады.

Жалған үлесті клетканы 496.jpg жолдарының әйтеуір бір бос клеткасына нөлді бөліп, ендірміз. Сызықтық функцияны минимизмциялау есебі қарастырылып отырғандықтан, жалған үлесті етіп, тасымал құны ең кіші клетканы алу тиімді.

496.jpg жолдарындағы бос клеткалардың 498.jpg орналасқан 499.jpg клеткасына нөлді жазып, үлесті етеміз. Бұл клетка 500.jpg потенциалын 501.jpg потенциалымен, 502.jpg клеткасы 503.jpg потенциалын 504.jpg потенциалымен, 505.jpg клеткасы 503.jpg потенциалын 507.jpg потенциалымен, 508.jpg клеткасы 509.jpg потенциалын 510.jpgпотенциалымен байланыстырады.

Потенциалдар жүйесі құрылды. Әрбір үлесті клеткада

454.jpg ( * )

шарты орындалса, жүйенің дұрыстығы; кері жағдайда жүйені қайта құру немесе ( * ) шарты орындалатындай етіп өзгерту керек.

Бос емес ( үлессіз ) клеткаларда оптималдық шартының орындалуын тексеру:

Жолдардың әрбір үлессіз клеткасында ( ** ) шартының орындалуын тексереміз, яғни қиылысында бос клетка жататын жол мен баған потенциалдарын қосып, осы клеткадағы тасымалдау құнымен салыстырамыз.

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

Кесте 1 – де үлессіз клеткаларды аламыз:

515.jpg жолында 516.jpg: 517.jpg518.jpg519.jpg

520.jpg жолында 521.jpg;

522.jpg жолында 523.jpg524.jpg

516.jpg, 526.jpg клеткаларында отималдық шарты орындалмайды, айырымдарды клетканың сол жақ төменгі бөліктеріне жазып қоямыз.

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

Үлесті клеткаларды базистік векторларға балап, үлессіздерін-қалған векторларға баласақ, сызықтық программалаудың жалпы есебінде базиске 527.jpg мәніне сәйкес келетін вектор енгізетіндіктен, транспорт есебінде 528.jpg мәні 529.jpg потенциалдар қосындысына баланып, үлес жіберілетін клетка ретінде 530.jpg мәніне сәйкес клетка таңдалады. Қарастырылып отырған мысалда 531.jpg мәні тиісті 526.jpg клеткасын үлесті ету қажет. Ол үшін қанша жүк үлесі бөлінетіндігін алдынала анықтаймыз.

Цикл құру және айналымдық жүкті анықтау.

Үлесті ету қажет клетканы “+” таңбасымен белгілеп, бос емес клеткалар қатарына қосамыз. Енді кестедегі үлесті клеткалар саны m+n болғандықтан, бір төбесінен басқа төбелері түгел үлесті клеткалардан тұратын цикл құрылады. Циклды тауып “+” таңбалы клеткасынан кейінгі төбелерін кезекпен “–” және “+” таңбаларымен белгілеп шығамыз да, 533.jpg мәнін анықтаймыз. Мұндағы 534.jpg-лер циклдың “–” белгілі төбелеріндегі үлестер, 535.jpg- цикл бойынша айналымға түсетін үлес шамасын анықтайды. Енді 535.jpg- мәнін “+” таңбасымен белгіленген үлесті ету қажет клеткасына жазамыз да, цикл бойымен жылжи “+” белгілі клеткалар үлестеріне қосып, “–” белгілі клеткалар үлестерінен шегеріп шығамыз. Егер 535.jpg- бірнеше минималды үлеске тән болса, шегеруден шыққан нөлдік үлестерді жаңадан алынған тірек шешімінің бос емес ( үлесті ) клеткаларының саны m+n – 1 болатындай етіп қалдырамыз.

Үлесті ету клеткасы 526.jpg “+” таңбасымен белгіленіп, кесте 1- де пунктирмен көрсетілген цикл құрылады да, 539.jpg анықталып, цикл бойымен тиісті өзгерістер енгізіледі.

Кесте 2

Тұтынушылар

463.jpg

464.jpg

465.jpg

466.jpg

Ұсынушылар

467.jpg

457.jpg

2

4

11

-

546.jpg15 9

Қорлар

473.jpg

0!

2

120

4

548.jpg549.jpg -

50

7

+550.jpg551.jpg552.jpg

4

9

30

200

481.jpg

-3

5

1

554.jpg +

30

8

-

240

12

270

484.jpg

556.jpg +

12

-6

11

6

4

557.jpg

558.jpg1

3

130

130

Сұраныстар

120

80

240

160

535.jpg-ді айналымға түсіріп, жаңа тірек шешімі, кесте 2 алынды, бұл шешімде оптималдыққа тексеріледі. Потенциалдар жүйесін қайтадан құрып, әрбір бос клеткада оптималдық шартының орындалуын тексеруге болады.

Алынған шешім оптималды бомаса 4-кезеңдегі әрекеттер қайталанады. Процесс барлық бос клеткаларда (**) шарты орындалғанша жалғасады

534.jpg,457.jpg,467.jpg мәндерін, сондай-ақ “+” , “–” таңбаларын қаламмен жазып, өшіріп отыру арқылы оптималды шешімді бір ғана кестені пайдалана отырып іздестіруге болады.

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

Потенциадар жүйесін өзгерту:

Жаңа тірек шешімінде (клетка 2) бұрынғы потенциалдар жазылған, 526.jpgүлесті клеткасында, 564.jpg шарты орындалмайды, 565.jpg. Сондықтан не 566.jpg- ді, не 472.jpg- ті алтыға шегеруіміз қажет. Нәтижесінде азғана потенциалдар өзгеретін потенциал кемітіледі. 472.jpg потенциалын кемітіп, 566.jpg- ді қарастырсақ бір ғана 570.jpg потенциалы өзгереді. Кері жағдайда барлық потенцилдар өзгерілер еді. Потенциал 566.jpg- ді “!” белгісімен, 472.jpg- ті “–”, 472.jpg пен байланысты 570.jpg- ті “+” бнлгісімен таңбалап, өзгерістер енгізілетін тізбекті құрамыз. Осы тізбектегі “–” таңбалы потенциалды кемітеміз, “+” таңбалы потенциалды өсіреміз, “!” таңбалы потенциалды өзгеріссіз қалдырамыз. Сонда барлық бос емес клеткаларда (*) шарты орындалады.

Потенциал 472.jpg кемітілгендіктен бұл бағандағы бос клеткаларда оптималдық шарты орындалмауы мүмкін емес. Оптималдық шарты орындалмайтын бос клеткалар потенциалы өсірілген жолда (бағанда) ғана пайда болуы мүмкін. Потенциал 570.jpg алтыға өсірілді, 522.jpg жолының бос клеткаларын оптиамалдыққа тексереміз: -4<11; -2<6; 5>4.

Клетка 578.jpg бұл шартты қанағаттандырмайды. Сондай-ақ бұл шарт 516.jpg клеткасында орындалмағанлықтан 580.jpg айырымдарын сол жақ төменгі бұрыштарына жазамыз.

581.jpg келесі үлесті ету клеткасын 516.jpg анықтайды, бұл клеткаға “+” белгісін қойып, циклды құрып, төбелерін “–” және “+” белгілерімен алма–кезек таңбалап, 583.jpg мәнін табамыз. Цикл бойымен 535.jpg мәнін айналымға түсіріп, 516.jpg клеткасының үлесіне 50-ді бөлу арқылы жаңа тірек шешімін (кесте 3) аламыз.

Соңғы жуықтау арқылы шешім 200-ге жақсара түсті. Бұл 516.jpg клеткасындағы 587.jpg айырымын, осы клеткаға бөлінген үлестің 50 көбейтіндісінен анықталды.

Тұтынушылар

Қорлар

463.jpg

464.jpg

465.jpg

466.jpg

Ұсынушылар

467.jpg

457.jpg

2

594.jpg -

4 0

595.jpg -

-11 7

9

473.jpg

0!

2

120

4

7

50

9

30

200

597.jpg481.jpg

+

-3 1

5

1

80

8

190

12

270

484.jpg

-6

11

6

4

3

130

130

Сұраныстар

120

80

240

160

Соңғы алынған кесте 3 тірек шешімінде потенциалдар жүйесін өзгертіп, оптималдыққа тексереміз. Құрылған потенциалдар жүйесі алынған шешімнің оптималды екендігін көрсетеді. Тасымалдау құны 2850.

Ескерту. Цикл өзін-өзі қиып өтетін де болуы мүмкін.


Информация о реферате «Сызықтық программалаудың негізгі есептері»
Раздел: Математика
Количество знаков с пробелами: 59435
Количество таблиц: 11
Количество изображений: 13

Похожие материалы

Скачать
52998
0
6

... 1171;аны сканердің жұмысына байланысты болады – оның жұмысы тоқтатылады немесе келесі лексеманы орындайды. (алгоритмнің бірінші қадамына өту жүріп жатыр). Лексикалық анализатордың құрылу автоматизациясы (LEX программасы). Лексикалық танушылар (сканерлер) – бұл компилятордың маңызды бөлігі &# ...

0 комментариев


Наверх