СЫЗЫҚТЫҚ ПРОГРАММАЛАУ ЕСЕПТЕРІ | Скачать Материал

БИЗНЕС ЖӘНЕ АҚПАРАТТЫҚ ТЕХНОЛОГИЯЛАР ФАКУЛЬТЕТІ

РЕФЕРАТ

Тақырыбы: СЫЗЫҚТЫҚ ПРОГРАММАЛАУДЫҢ НЕГІЗГІ ЕСЕПТЕРІ

Пәні: Алгоритмдер, берілгендер құрылымы және бағдарламалау

ТОБЫ: УСД-ИС-18-1

Қабылдаған: __________________

Орындаған: Мақан Нұргүл Арысланқызы

Астана, 2018 ж.

МАЗМҰН:
1.Сызықтық программалаудың негізгі есептері.

1. СЫЗЫҚТЫҚ ПРОГРАММАЛАУДЫҢ НЕГІЗГІ ЕСЕПТЕРІ … … … … … ..3
1.1. СЫЗЫҚТЫҚ ПРОГРАММАЛАУ ЕСЕПТЕРІ … … … … … … … … … … … .3
1.2 Сызықтық программалаудың негізгі теоремалары … … .6
1.3 Сызықтық программалау есептерін шешудің графиктік әдісі … … … … … … … .. … … … … … … … … … … … … … … … … … … … … … … ..10
1.4 Сызықтық программалау есебін шешудің симплекс әдісі … … … … … … … .. … … … … … … … … … … … … … … … … … … … … … … ..16

1.Сызықтық программалаудың негізгі есептері.
1.1 Сызықтық программалау есептері.
Қәзіргі кездегі ғылымдардың даму ерекшеліктерінің бірі-олардың әртүрлі салаларын зерттеуде математикалық әдістер мен есептеуіш техникаларының кеңінен қолданылуында. Егер бұдан бұрынғы уақыттырда математикалық амалдар мен әдістер тек астрономия, физика, химия ғылымдарында қолданылып келсе, соңғы кезде бұл ғылыми жетістіктер медицина, лингвистика және экономика ғылымының көптеген процестері мен құбылыстарын зерттеуде ұтымды пайдаланып жүр. Мұның өзі ақиқатты танып білуде әртүрлі ғылымдар саласында диалектикалық бірліктің күшейіп және теориялық көзқарастың тереңдей түсуінен деуге болады.
Соңғы жылдар бедерінде халық шаруашылығын тиімді басқаруда математикалық әдістер мен есептеуіш техникалары жиі қолданылуда. Осының негізінде еліміздің экономикасын жоспарлы түрде дамытып, еңбек тиімділігін арттырудың жаңа мүмкіндіктері пайда болды. Осы ретте қол жеткен мүмкіндіктерді қысқаша ғана атап айтсақ, олар: экономиканың даму жоспары; шаруашылықты басқару шешімдерінің нақтылығы мен дәлелділігінің артуы; жоспарді іс жүзінде асыру барысында жасалынатын бақылау процестеріне ерекше жылдамдық беру, т.б.
Адамзат қоғамы дами бастауынан үнемділік, тиімділік деген мәселелер бірге жасасып келеді. Үнемділік, тиімділіктің математикалық түбірі функциялардың экстремум мәндерімен тығыз байланысты. Экономикалық есептердің алғашқы үлгісі гректерде кездеседі. Ұзындығы белгілі l доғамен шектеуге болатын ең үлкен ауданды табу керек. Ең үлкен және ең кіші мәндерді табу есептері экономикалық мәселелерде жиі кездеседі. Мұндай экономикалық есептерді экономикалық-математикалық мделдеу пәні қарастырады.
Экономикалық-математикалық моделдеу математикада қарастырылатын экстремалдық есептер курсының бөлімі болып табылады. Экономикалық есептер үш топқа бөлініп қарастырылады: сызықтық программалау есептері, сызықтық емес программалау есептері және динамикалық программалау есептері.
Бұл көптен бері құлаш жайып, дамып келе жатқан ғылым. Бұл салада алғашқылардың бірі совет экономисті А.Н.Толстой (1930ж) еңбектері. Венгер математигі Б.Эгервари (1931ж) «таңдау проблемасы» есебінің математикалық қойылымын қарастырып, сызықтық программалау есебінің шешімін тапқан. Бұл есепті шешу әдісі осы ғалым құрметіне венгер әдісі деп аталады. Совет ғалымдары Л.В.Канторович, В.С.Немчинов, В.В.Новожилов, А.Л.Луръе және т.б. математиктер мен экономистердің жұмыстарында сызықтық және сызықтық емес программалаудың математикалық теориясы экономикалық проблемаларды зерттеудің әдістері ретінде дамып отырды. Бұл салада тек совет ғалымдары емес сонымен қатар басқа елдер ғалымдарының да атқарған қызметі мол. Солардың ішінде америка ғалымы Хичкок (1941ж) транспорт есебінің берілуін қойды, Данциг (1949ж) сызықтық программалау есебін шығарудың симплекс әдісін жасады. Сызықтық және сызықтық емес программалау есептерінің шығару әдістері Форд, Фалкерсон, Кун, Ламке, Гасс, Чарнес, Бил еңбектерінде берілді. Толық зерттелген есептер сызықтық программалау есептері. Динамикалық программалау есептері үлкен қарқынмен өрістеп келеді.
Өндірістік процестерді зерттеуде кеңінен қолданылатын тәсілдердің бірі-сызықтық программалау. Сызықтық программалау дегеніміз өндірістің негізгі мақсаты мен шарты белгілі бір сызықтық өрнектер (теңдеулер) түрінде берілген жағдайда, сол процесті зерттеу үшін қолданылатын математикалық тәсіл. Математика тілімен айтқанда, сызықтық программалау дегеніміз белгісіздеріне сызықтық теңсіздіктер түрінде шарт қойылған, сызықтық функцияның ең үлкен немесе ең кіші мәндерін табатын ғылым.
Сызықтық программалау есептерінің жалпы түрі былай жазылады.
Берілген
fX=c1x1+c2x2+ … +cnxn (1.1.1)
мақсат функциясына минимал мән әперетін және мына теңсіздіктерді:

a11x1+a12x2+ … +a1nxn=b1a21x1+a22x2+ …+a2nxn=b2 … … … … … .. … … … … .am1x1+am2x2+ …+amnxn=bm (1.1.2)
xj=0,j=1,2, … ,n (1.1.3) қанағаттандыратын X=x1,x2,…,xn
векторын табу.
Бұл жердегі aij,bi,cj-берілген тұрақты сандар, оның үстіне m n
Жоғарыда келтірілген мысалдарға сәйкес, (1.1.2), (1.1.3) теңсіздіктерін есептің шектеуіш шарты деп, ал (1.1.1) сызықтық формасын есептің мақсат функциясы деп атайды.
Сызықтық программалау есептерінде барлық bi=0, i=1,2, …,m деп жорамалдауға болады, өйткені олардың ішінде теріс сандар кездесетін болса, онда сәйкес теңдеуді (-I) көбейту арқылы bi-ді оң санға айналдыруға болады.
Жеке мысалдарда есептің негізгі (1.1.2) щарты бірнеше түрде берілуі мүмкін. Мысалы, есептің негізгі теңсіздіктері тек қана =-түрінде немесе =-түрінде жазылуы мүмкін. Сол себептен,есептің негізгі теңсіздіктерініңформасына қарай сызықтық программалау есептерін бірнеше түрге бөлуге болады.
Егер сызықты программалау есептері мына түрде берілсе:
fX=c1x1+c2x2+ …+cnxn--min (1.1.4)

a11x1+a12x2+ …+a1nxn=b1a21x1+a22x2+ …+a2nxn=b2 … … … … … … … … … … … ..am1x1+am2x2+ …+amnxn=bm (1.1.5)
xj=0 , j=1,2, … ,n (1.1.6)
онда бұндай мысалды сызықтық программалау есебінің канон түрі деп атайды.
Егер сызықтық программалау есептері мына түрде берілсе:
fX=c1x1+c2x2+ …+cnxn--max
a11x1+a12x2+ …+a1nxn=b1 … … … … … .. … … … … … …am1x1+am2x2+ …+amnxnbm
xj=0 , j=1,2, … ,n
онда мұндай мысалды сызықтық программалау есебінің стандартты түрі деп атайды.
Сызықтық программалау мысалдары әр түрде берілгенімен, олар бір-біріне эквивалентті, өйткені, канон түрінде берілген есеп стандартты түрде оңай түрленеді, немесе керісінше, стандартты түрде берілген есеп канон түріне оңай келтіріледі. Енді осы жағдайларды қарастыралық. Мысалы сызықтық программалау есебінің негізгі шарты мына түрде берілсін:
ai1x1+ai2x2+ …+ainxn=bi
Онда осы теңсіздікке xn+1=0 белгісізін қосу арқылы оны теңдікке айналдырамыз, яғни
ai1x1+ai2x2+ …+ainxn+xn+1=bi
осы теңсіздікті теңдеуге айналдырушы xn+1 белгісізін есептің қосымша белгісізі деп атайды.
Енді есептің негізгі шарты теңдеу түрінде берілсін:
ai1x1+ai2x2+ …+ainxn=bi
онда осы теңдеуді екі теңсіздіктер түрінде жазуға болады, яғни
ai1x1+ai2x2+ …+ainxn=biai1x1+ai2x2+ …+ainxn=bi
соңғы теңсіздіктердің екіншісін (-I) көбейтіп, кез-келген теңдеудің төмендегі екі теңсіздіктер түрінде жазылатынын көреміз:
ai1x1+ai2x2+ …+ainxn=bi-ai1x1-ai2x2- …-ainxn=-bi
сонымен есебіміз канон түрінде берілсе, онда оның әрбір теңдеуіне екі теңсіздікті сәйкес қою арқылы стандартты түрге көшіруге болатынын, ал стандартты түрден канон түріне қосымша белгісіздер ендіру арқылы көшіруге болатынын көрдік. Осы тұрғыда ескерте кететін тағы бір жағдай, ол maxfX пен min(-fX)-тің эквивалент екендігінде.
Енді сызықтық программалау есептерін бір түрден екінші түрге көшіруге мысал қарастыралық.
Берілген мысалды сызықтық программалаудың канон түріне келтір.
fX=3×1+2×2+4×3—max
2×1+x2-3×3=83×1+2×2+x3=12×1+2×2- x3=2
xj=0 , j=1,2,3.
Қосымша x4=0 және x5=0 белгісіздерін бірінші және екінші теңсіздіктердің оң жағына қосып жазып, мынадай канон есебін аламыз:
fX=3×1+2×2+4×3—max
2×1+x2-3×3+x4=83×1+2×2+x3+x5=12x 1+2×2-x3=2
Егер сызықтық программалау есебінің негізгі шарты (1.1.5) теңдеулер системасы түрінде беріліп, ал белгісіздерінің кейбіреулері үшін (1.1.6) теңсіздігі орындалмайтын болса, онда ол мысал канон түріндегі есепке жатпайды. Осындай есептерді толық канон түріне келтіру үшін оның барлық белгісіздері (1.1.3) шартын қанағаттандыратындай жағдай жасау қажет.

1.2 Сызықтық программалаудың негізгі теоремалары.
Сызықтық программалаудың негізін құрайтын теоремалармен танысайық:
1-теорема. Сызықтық программалау есебінің шешімдерінің жиыны — дөңес.
Дәлелдеу. Сызықтық программалау есебінің шешімінің сызықтық комбинациясы да сол есептің шешімі болатынын дәлелдеу қажет. Ол үшін X1,X2 векторлары сызықтық программалау есебінің шешімдері делік. Олай болса
AX1=B , X1=0
және
AX2=B , X2=0
Енді осы жоспарлардың кез-келген сызықтық комбинациясын қарастыралық:
X=αX1+1-αX2 , 0=α=1
Осы жоспардың есептің шешімі болатынын көрсетелік. Ол үшін мына амалдарды орындаймыз.
AX=AαX1+1-αX2=αAX1+1-α(AX2)=αB+ +1-αB=B
бұдан AX=B екендігі шығады.
Жорамалымыз бойынша x1=0 , x2=0 ,α=0
болғандықтан X=0. Демек теорема дәлелденді.
2-теорема.Сызықтық программалау есебінің мақсат функциясы өзінің оптимал шешімін дөңес көпжақтың шеткі нүктесінде қабылдайды. Егер сызықтық функция өзінің оптимал шешімін бірнеше шеткі нүктеде қабылдаса, онда сол нүктелердің дөңес сызықтық комбинациясы да есептің оптимал шешімі болады.
Дәлелдеу. Теореманың шарты бойынша сызықтық программалау есебінің анықталу облысын төбелерінің саны шекті көпжақ құрайды. Жазықтықта көпжақтың көпбұрыш болатыны белгілі. Теореманың дәлелдеуін жазықтықта қарастыралық. Көпбұрышты Д — деп, ал оның шет нүктелерін X1 , X2 , …, Xp- деп белгілейік. Есептің оптимал шешімі X0 болсын (сурет 1). Олай болса кез-келген XϵД үшін fX0=fX болады.

сурет 1

Егер X0 шеткі нүкте болса, онда теорема дәлелденеді. Енді X0 ішкі нүкте болған жағдайды қарастыралық. Онда ол нүкте көпбұрыштың бұрыш нүктелерінің (шет нүктелері) сызықтық комбинация арқылы өрнектеледі, яғни
X0=i=1pαiXi
бұл жердегі
αi=0,i=1,2,…,p,i=1pαi=1
бізде fX сызықтық функционал болған себепті:
fX0=fi=1pαiXi=fα1×1+α2×2+ …+αpxp=α1fX1+α2fX2+ …+αpfXp=i=1pαifXi
Барлық fXi ішіндегі ең кішісін тауып, оны m-ге тең делік. Ал барлық fXi ішіндегі ең кіші мәні Xk үшін орындалсын делік. Демек
minifXi=fXk=m
Енді соңғы өрнектегі барлық fXi- ді m-ге ауыстырсақ, онда мынадай теңсіздік аламыз:
fX0=i=1pαim=m=fXk , i=1pαi=1
яғни
fX0= fXk
Теореманің шарты бойынша X0 оптимал жоспар. Ал соңғы теңсіздік көпбұрыштың шеткі нүктесінде басқа оптимал шешім болатынын көрсетеді. Бұл қарама-қайшылық X0-дің шет нүкте екенін дәлелдейді.
Енді осы теореманың екінші жартысын дәлелдейік. Ол үшін fX функциясы бірнеше нүктеде минимал мән қабылдайды делік. Ол нүктелерді біз X1, X2, …, Xq деп белгілейік. Демек
fX1=fX2= …=fXq=m
Енді X нүктесі осы нүктелердің дөңес сызықтық комбинациясы делік, яғни
X=i=1qαixi ,αi=0 , i=1qαi=1
функционалдың осы нүктедегі мәнін қарастырамыз:
fX=fi=1qαixi =i=1qαif(Xi)=i=1qαim=m.
Бұдан X1, X2, …, Xq нүктелерінің дөңес сызықтық комбинациясының да есептің минимал мәнін беретінін көрдік. Теорема дәлелденді.
3-теорема. Егер k(k=n) өзара тәуелсіз векторлар системасы A1, A2, …, Ak берілген болып, олар үшін Aixi=B теңдігі барлық xi=0-тар үшін орындалса, онда X=x1 , x2 ,…, xk , 0…, 0 векторы есептің анықталу облысын беретін көпжақтың шеткі нүктесі болады.
Дәлелдеу. X нүктесі анықталу облысының ішкі нүктесі деп жорамалдайық. Олай болса ол нүкте сол облыстың екі шеткі X1, X2 нүктелерінің сызықтық комбинациясы түрінде бейнеленеді, яғни
X=αX1+1-αX2
0α1
Берілген X векторының n-k компоненті нөлге тең болғандықтан, ал X1, X2 векторларының компоненттерінің теріс болуы мүмкін емес екенін және 0 α1 екенін ескерсек, онда X1, X2 векторларының да n-k компоненттері нөлге тең болады. Демек
X1=x’1,x’2 , …, x’k ,0,0…,0
X2=x21,x22 , …, x2k ,0,0…,0
Жорамалдауымыз бойынша осы екі нүкте есептің анықталу облысында жатыр. Демек олар үйлесімді жоспарлар. Олар үшін мынадай теңдіктер:
AX1=B
AX2=B
орындалады. Осы теңдіктерді векторлар түрінде жазсақ, онда:
A1x’1+A2x’2+ …+Akx’k=B
A1x21+A2x22+ …+Akx2k=B
осы екі теңдеудің айырымы:
A1x’1-x21+A2x’2-x22+ …+Akx’k-x2k=0
теореманың шарты бойынша A1,A2, …,Ak векторлар системасы сызықтық тәуелсіз. Демек соңғы теңдік тек қана
x’1-x21=0 , x’2-x22=0 , …,x’k-x2k=0
болғанда орындалады.
Бұдан
x’1=x21 ; x’2=x22 ;…;x’k=x2k
екені шығады. Басқа сөзбен айтқанда, X нүктесін екі шеткі нүктенің сызықтық комбинациясы түрінде бейнелеуге болатынын аламыз. Бұрыш нүктесінің (шет нүктенің) анықтамасын еске түсірсек, онда X нүктесінің шет нүкте екенін аламыз. Сонымен теорема дәлелденді.
4-теорема. Егер X=(x1 , x2 ,…, xn) шеткі нүкте болса, онда барлық оң
болатын xi-терге сәйкес келетін векторлар өзара сызықтық тәуелсіз.
Дәлелдеу. X векторының алғашқы компоненті нөлге тең емес делік. Олай болса алғашқы A1 , A2 , …, Ak векторлары үшін
i=1kAixi=B (1.2.1)
Осы теңдікті қанағаттандыратын векторлар системасы өзара сызықтық тәуелді делік. Олай болса, бәрі бірдей нөлге тең емес d1 , d2 , …, dk сандары табылып олар үшін
A1d1+A2d2+ …+Akdk=0 (1.2.2)
теңдігі орындалады. Теореманың шарты бойынша
A1x1+A2x2+ …+Akxk=B (1.2.3)
Кез-келген ε0 санын алып, оны (1.2.2) теңдеуіне көбейтеміз деодан шыққан қорытындыны (1.2.3) теңдеуіне бірінші, қосу, сосын алу нәтижесінде мынадай теңдеулер аламыз:
A1x1+εd1+A2x2+εd2+ …+Akxk+εdk=B
A1x1-εd1+A2x2-εd2+ …+Akxk-εdk=B
Соңғы теңдеулер системасы (1.2.1) теңдеуінің екі шешімі бар екенін және олардың
x1=x1+εd1, x2+εd2, …, xk+εdk
x2=x1-εd1, x2-εd2, …, xk-εdk
тең екенін көрсетеді. Бұл жерде барлық xi=0 болғандықтан ε-ді X1 және X2 векторларының барлық компоненттері оң болатындай етіп таңдап алуға болады. Бұл жағдайда X1 мен X2 жоспар болады, ал
X=12×1+12×2
Демек X векторы басқа екі нүктенің сызықты комбинациясы түрінде бейнеленіп отыр. Бұл жағдай теореманың шартында айтылған, X шеткі нүкте деген шартқа қайшы келеді. Демек X шеткі нүкте (бұрыш нүктесі).

1.3 Сызықтық программалау есептерін шешудің графиктік әдісі.
Графиктік әдіс сызықтық программалау есебінің геометриялық мағынасына негізделіп, көбіне екі өлшемді кеңістік есептерін және үш өлшемді кеңістіктің кейбір есептерін шешуде қолданылады, себебі жартылай кеңістіктердің қиылысынан тұратын шешімдер көпжағын құрудың жеткілікті ауыртпалығы бар. Үштен жоғары өлшемді кеңістік есебін геометриялық түрде кескіндеу мүмкін емес.
Сызықтық программалау есебі екі өлшемді кеңістікте берілсін, яғни шектеулері екі айнымалыдан болсын
Z=C1x1+C2x2—min (1.3.1)
a11x1+a12x2=b1a21x1+a22x2=b2—— ——am1x1+am2x2=bm (1.3.2)
x1=0, x2=0 (1.3.3)

Жүйе (1.3.2), (1.3.3) үйлесімді, шешімдер көпбұрышы шектеулі делік. Әрбір теңсіздік (1.3.2), (1.3.3) жарты жазықтықты шеттік түзулерімен ai1x1+ai2x2=bi, i=1, m, x1=0, x2=0 бірге анықтайды. Сызықтық функция (1.3.1) Z=h мәніндегі түзулерді береді; C1x1+C2x2=const. Шектеулер жүйесінің шешімдер көпбұрышын (1.3.2) және сызықтық функцияның (1.3.1) Z=0 мәніндеі графигін тұрғызайық. Онда қойылған сызықтық программалау есебіне мынадай геометриялық мағына беріледі. C1x1+C2x2=const тірек түзуі және мұнда функция Z min мәнін қабылдайтын шешімдер көпбұрышының нүктесін табу керек.
Z=C1x1+C2x2 мәндері N = (C1;C2 ) векторы бағытында өсетіндіктен, Z=0 түзуін N бағытында өзіне-өзін параллель жылжытамыз.
Сурет 1-ден шешімдер көпбұрышының екі тірек түзуі (А және С нүктелерінде) болатындығын, әрі min мәні қабылданатын Аx1; x2 нүктесінің координаталарын АB және AE түзулерінің теңдеулер жүйесін шешу арқылы табу керектігін көреміз.
Егер шешімдер көпбұрышы шекеусіз облыс болса, екі жағдай мүмкін.
1 — жағдай. C1x1+C2x2=const түзуі N векторы бағытында немесе оған қарама-қарсы бағытта қозғала отырып шешімдер көпбұрышын кесіп отырады және бірде-бір нүктесінде оған тірек болмайды. Бұл жағдайда сызықтық функция шешімдер көпбұрышында жоғарыдан да, төменнен де шектеусіз (сурет 2).
2 — жағдай. Түзу қозғала отырып, шешімдер көпбұрышына тірек болады (сурет 3). Онда облыс түріне байланысты сызықтық функция жоғарыдан шектеулі және төменнен шектеусіз (сурет За), төменнен шектеулі және жоғарыдан шектеусіз (сурет 3б) немесе жоғарыдан да, төменнен де шектеулі (сурет 3в) болуы мүмкін.

сурет 3
Мысалдар.
Шикізатты пайдалану есебі.
Екі түрлі P1, Р2 өнім шығару үшін үш түрлі шикізат S1, S2, S3 қолданылады. Шикізат қорлары, әрбір өнімнің бір өлшемі үшін жұмсалатын әрбір шикізат шамасы және өнімнің бір өлшемін өткізуден түсетін пайда шамасы кестеде көрсетілген. Өнімді max пайда алатындай етіп, ұйымдастыру қажет.
Шикізат
түрлері
Шикізат
Қоры
Өнім өлшемін жасауға жұмсалатын шикізат мөлшері

Р1
Р2
S1
6
1
1
S2
10
3
1
S3
20
2
5
Өнім өлшемінен түсетін пайда
10
8

Шешуі. Р1 -ден x1, Р2 -ден х2 мөлшерінде өнімдер дайындалсын. Өнімнің бір өлшем шамасын дайындауда жұмсалатын шикізаттар мөлшерін жөне олардың қорларын: ескерсек келесі шектеулер жүйесін аламыз
x1+x2=63×1+x2=102×1+5×2=20
Теңсіздіктер жұмсалатын шикізаттар қордағы барынан аспайтындығын көрсетеді.
Есептің мақсаты, өнімдерді өткізуден түсетін max пайданы, екі айнымалының x1 және х2 функциясы деп қарастырамыз. P1 өнімінің х1 мөлшері өткізгенде 10х1, Р2 өнімінің х2 мөлшері өткізгенде 8х2, барлығы, қосындыда Z=10×1+8×2 (теңге) пайда келтіреді. Сонымен, шектеулер жүйесінің
x1+x2=63×1+x2=102×1+5×2=20×1=0, x2=0
сызықтық функция Z=10×1+8×2 — max мәнін қабылдайтын нақты x1=0, x2=0 шешімдерін табу керек. Шешімдер көпбұрышын шекаралық түзулер арқылы
l1 x1+x2=6, l2 3×1+x2=10, l3 2×1+5×2=20, x1=0, x2=0
тұрғызамыз. Ол үшін кезкелген нүктені, мысалы координаталар бас нүктесін алып, теңсіздік қай жарты жазықтықты беретінін анықтаймыз. Теңсіздік жарты жазықтығын белгілеу арқылы, шешімдер көпбұрышын ОАВС құрамыз.

N = (10; 8) = 2(5; 4) векторын және 10×1+8×2=0 (Z) түзуін тұрғызамыз. (Z) түзуін өзіне-өзін параллель N векторы бағытында жылжыта отырып, шешімдер көпбұрышының В нүктесінде тірек түзуіне айналып, бұл нүктеде функция Zmax мәнін қабылдайтынын көреміз.
В нүктесі l1 және l3 түзулердің қиылысында жатқандықтан, оньң координаталарын тендеулер жүйесін
3×1+x2=102×1+5×2=20
шешіп табамыз x1= 3013, x2= 4013. Есептің оптималдық шеімі x1= 3013, x2= 4013, Zmax=10∙ 3013+ 8 ∙ 4013 ≈47,69.
Сонымен 47,69т. көлеміндегі пайда келтіру үшін 3013 мөлшерінде Р1, 4013 мөлшерінде Р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 кг десек, кестедегі цифрлар арқылы қоректілік сақталу үшін
2×1+x2=10×1+x2=8×1+4×2=10
теңсіздіктерінің орындалуы қажетті. Егер жем рационда қолданылмаса х1= 0 немссе х2 = 0 болады, кері жағдайда x10 немесе x20. Жалпы жағдайда, x1=0, x2=0 шарттары орынды.
Есептің мақсаты күндік рационға min шығын жұмсау болғандықтан, рацион құнын Z=3×1+4×2 сызықтық функциясы арқылы анықтап, осы функцияның min мәнін табу талап етіледі. Есеп көп шешімді, х1 және х2 шексіз көп мәндер қабылдауы мүмкін. Сонымен, теңсіздіктер жүйесінің
2×1+x2=10×1+x2=8×1+4×2=10
x1=0, x2=0
сызықтық функцияға Z=3×1+4×2—min мәнін беретін шешімдерін табу керек.
Шешуі. x1Оx2 координаталар жүйесінде шекаралық түзулерді
l1 2×1+x2=10,
l2 x1+x2=8,
l3 x1+4×2=10,
x1=0, x2=0
және осы түзулерге қарағанда теңсіздіктер анықтайтын жарты жазықтықтар қиылысында шешімдер көпбұрышын тұрғызамыз. Нәтижесінде A,B,C,D бұрыштық нүктелері (төбелері) болатын, шектеусіз көпбұрышты облысты аламыз. N(3,4) векторын және 3×1+4×2=0 (Z) түзуін тұрғызып, Z түзуін өзіне-өзін параллель N векторы бағытында жылжыта отырып, шешімдер көпбұрышының С нүктесінде алғаш тірек түзуіне айналатынын көреміз (сурет 5). Түзуді әрі қарай жылжыта берсек, сызықтық функцияның мәні шешімдер көпбұрышының нүктелерінде өсе бастайды. Демек С нүктесінде сызықтық функция min мәнін қабылдайды. Бұл нүкте l1 , l3 түзулердің қиылысында жатқандықтан
x1+x2=8×1+4×2=10
теңдеулер жүйесін шешу арқылы координаталарын x1= 223 , x2= 23 табамыз. Табылған мәндерді сызықтық функцияға қойсақ, Zmin=3∙223+4∙23=743=2423 аламыз.
Сонымен min шығын жұмсау үшін күндік рационды 223 кг I — жемнен, 23 II — жемнен құру қажет.

Жалпы графиктік әдіспен n-m=2 болатын сызықтық программалау есебін шеше аламыз. Мұндағы n — айнымалылар (белгісіздер) саны, m — сызықтық тәуелсіз тендеулер саны.
Сызықтық программалау есебін қарастырайық.
Z=j=1nCjxj—min
a11x1+a12x2+ …+a1nxn=b1a21x1+a22x2+ …+a2nxn=b2—————am1x1+am2 x2+ …+amnxn=bmxj=0, j=1,n
Бұндағы барлық теңдеулер сызықтық тәуелсіз және n-m=2 ұатынасы орындалсын.
Жордан — Гаусс әдісімен m жою барсында алғашқы m айнымалылар x1, x2, … , xm — базистік, ал соңғы екі айнымалы xm+1, xn — еркін айнымалыларға айналсын делік, яғни жоғарыда көрсетілген шектеулер мына түрге келтірілсін
x1+a’1, m+1xm+1+a’1nxn=b’1×2+a’2, m+1xm+1+a’2nxn=b’2—————xm +a’m, m+1xm+1+a’m,nxn=b’mxj=0, j=1,n (1.3.4)
Түрленген жүйе (1.3.4) теңдеулері арқылы сызықтық функцияны тек еркін айнымалылармен өрнектейміз де, базистік айнымалыларды xj=0, j=1,n шығарып тастап, теңсіздіктермен берілген шектеулерге көшеміз. Ақырында келесі есепті аламыз.
Z=C’m+1xm+1+C’nxn--min
a’1, m+1xm+1+a’1nxn=b’1a’2, m+1xm+1+a’2nxn=b’2————-a’m , m+1xm+1+a’mnxn=b’mxm+1=0,xn=0
бұл есепте екі айнымалы ғана болғандықтан графиктік әдіспен шеше аламыз. Оптималдық хm+1 және хn мәндерін тауып, (1.3.4)-ге қою арқылы, x1,x2,…,xm оптималдық мәндерін табамыз.
1.4 Сызықтық программалау есебін шешудің симплекс әдісі.
Сызықтық программалау есебінің оптималдық шешімі тірек шешімдерінің ішінен іздестіріледі, әрбір тірек шешімі берілген n векторлар жүйесіндегі m сызықтық тәуелсіз вектролармен анықталғандықтан, олардың саны терулерінің санынан аспайды.
m және n сандары жеткілікті үлкен болғанда оптималдық шешімді барлық тірек шешімдерін құру арқылы іздестру өте қиын.
Симплекс әдісі белгілі тірек шешімінен келесі жақсартылған трек шешіміне көшіріп отырады, санаулы қадымнан соң оптималдық шешімге келтіріледі; есептің шешімі жоқ немесе сызықтық функциясы шектеусіз болса, оны да көрсетеді.

есебін қарастырайық және мұндағы , болсын.
Шектеулер жүйесінің алғашқы m векторлары бірлік векторлар балсын делік. Онда есеп мына түрде қойылады
(1.4.1)
(1.4.2)
(1.4.3)
Теңдеулер жүйесін (1.4.2) векторлық түрде жазайық
(1.4.4)
мұндағы
, , … , , , … , ,
m-өлшемді кеңістіктің сызықтық тәуелсіз векторлары осы кеңістіктің базисін жасайтындықтан, (1.4.4) жіктелуіндегі айнымалыларын базистік деп, еркін айнымалыларын нөлге теңестірп, болғандықтан алғашқы
(1.4.5)
шешімін аламыз. Осы шешімге сәйкес
(1.4.6)
жіктелуіндегі векторлары сызықтық тәуелсіз, демек құрылған алғашқы шешім есептің тірек шешімін береді.
Бастапқы тірек шешімнен (1.4.5) келесі тірек шешімді қалай құратындығын қарастырайық. m-өлшемді кеңістіктің (1.4.4) өрнектегі әрбір векторы базистік векторлары арқылы бір ғана түрде былай жіктеледі
,
Базиске енбеген, мысалы векторының,
(1.4.7)
әйтеуір бір коэфифициенті оң таңбалы болсын делік. Әзірге белгісіз шамасына (1.4.7) теңдікті көбейтіп, (1.4.6) теңдіктен шегерсек,
(1.4.8) теңдігін аламыз. Сонымен

Векторының компоненттері теріс таңбалы болмаса, шешімді береді. болғандықтан, — векторының теріс таңбалы -лер енетін компоненттері теріс таңбалы бола алмайды. Сондықтан кезкелген үшін
(1.4.9) болатындай мәнін табу қажет. (1.4.9) теңсіздіктен

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

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

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