СЫЗЫҚТЫҚ ПРОГРАММАЛАУ ЕСЕПТЕРІ

Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 29 бет
Таңдаулыға:

$C:\Users\ЦОС\Downloads\LOGO VARIANT 10.08 ver 16 burgundy.jpg$ «ТҰРАН-АСТАНА» УНИВЕРСИТЕТІ

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

РЕФЕРАТ

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

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

ТОБЫ: УСД-ИС-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ж) сызықтық программалау есебін шығарудың симплекс әдісін жасады. Сызықтық және сызықтық емес программалау есептерінің шығару әдістері Форд, Фалкерсон, Кун, Ламке, Гасс, Чарнес, Бил еңбектерінде берілді. Толық зерттелген есептер сызықтық программалау есептері. Динамикалық программалау есептері үлкен қарқынмен өрістеп келеді.

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

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

Берілген

$f\left( \overline{X} \right) = c_{1}x_{1} + c_{2}x_{2} + \ \ldots\ + c_{n}x_{n}$ (1. 1. 1)

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

$\left\{ \begin{array}{r} a_{11}x_{1} + a_{12}x_{2} + \ \ldots\ + a_{1n}x_{n} \geq b_{1} \\ a_{21}x_{1} + a_{22}x_{2} + \ \ldots + a_{2n}x_{n} \geq b_{2} \\ \begin{matrix} \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots \\ a_{m1}x_{1} + a_{m2}x_{2} + \ \ldots + a_{mn}x_{n} \end{matrix} \geq b_{m} \end{array} \right. \$ (1. 1. 2)

$x_{j} \geq 0, j = 1, 2, \ \ldots\, n$ (1. 1. 3) қанағаттандыратын $X = \left( x_{1}, x_{2}, \ldots, x_{n} \right)$

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

Бұл жердегі $a_{ij}, b_{i}, c_{j} -$ берілген тұрақты сандар, оның үстіне m < n

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

Сызықтық программалау есептерінде барлық $b_{i} \geq 0, \ (i = 1, 2, \ \ldots, m)$ деп жорамалдауға болады, өйткені олардың ішінде теріс сандар кездесетін болса, онда сәйкес теңдеуді (-I) көбейту арқылы $b_{i} -$ ді оң санға айналдыруға болады.

Жеке мысалдарда есептің негізгі (1. 1. 2) щарты бірнеше түрде берілуі мүмкін. Мысалы, есептің негізгі теңсіздіктері тек қана $( \leq ) -$ түрінде немесе $( \geq ) -$ түрінде жазылуы мүмкін. Сол себептен, есептің негізгі қарай сызықтық программалау есептерін бірнеше түрге бөлуге болады.

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

$f\left( \overline{X} \right) = c_{1}x_{1} + c_{2}x_{2} + \ \ldots + c_{n}x_{n} \rightarrow \min$ (1. 1. 4)

$\left\{ \begin{array}{r} a_{11}x_{1} + a_{12}x_{2} + \ \ldots + a_{1n}x_{n} = b_{1} \\ a_{21}x_{1} + a_{22}x_{2} + \ \ldots + a_{2n}x_{n} = b_{2} \\ \begin{matrix} \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots \\ a_{m1}x_{1} + a_{m2}x_{2} + \ \ldots + a_{mn}x_{n} = b_{m} \end{matrix} \end{array} \right. \$ (1. 1. 5)

$x_{j} \geq 0\, \ j = 1, 2, \ \ldots\, n$ (1. 1. 6)

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

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

$f\left( \overline{X} \right) = c_{1}x_{1} + c_{2}x_{2} + \ \ldots + c_{n}x_{n} \rightarrow \max$

$\left\{ \begin{array}{r} a_{11}x_{1} + a_{12}x_{2} + \ \ldots + a_{1n}x_{n} \leq b_{1} \\ \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots \\ a_{m1}x_{1} + a_{m2}x_{2} + \ \ldots + a_{mn}x_{n}b_{m} \end{array} \right. \$

$x_{j} \geq 0\, \ j = 1, 2, \ \ldots\, n$

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

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

$a_{i1}x_{1} + a_{i2}x_{2} + \ \ldots + a_{in}x_{n} \leq b_{i}$

Онда осы теңсіздікке $x_{n + 1} \geq 0$ белгісізін қосу арқылы оны теңдікке айналдырамыз, яғни

$a_{i1}x_{1} + a_{i2}x_{2} + \ \ldots + a_{in}x_{n} + x_{n + 1} = b_{i}$

осы теңсіздікті теңдеуге айналдырушы $x_{n + 1}$ белгісізін есептің қосымша белгісізі деп атайды.

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

$a_{i1}x_{1} + a_{i2}x_{2} + \ \ldots + a_{in}x_{n} = b_{i}$

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

$\left\{ \begin{array}{r} a_{i1}x_{1} + a_{i2}x_{2} + \ \ldots + a_{in}x_{n} \leq b_{i} \\ a_{i1}x_{1} + a_{i2}x_{2} + \ \ldots + a_{in}x_{n} \geq b_{i} \end{array} \right. \$

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

$\left\{ \begin{array}{r} a_{i1}x_{1} + a_{i2}x_{2} + \ \ldots + a_{in}x_{n} \leq b_{i} \\ {- a}_{i1}x_{1} - a_{i2}x_{2} - \ \ldots - a_{in}x_{n} \leq - b_{i} \end{array} \right. \$

сонымен есебіміз канон түрінде берілсе, онда оның әрбір теңдеуіне екі теңсіздікті сәйкес қою арқылы стандартты түрге көшіруге болатынын, ал стандартты түрден канон түріне қосымша белгісіздер ендіру арқылы көшіруге болатынын көрдік. Осы тұрғыда ескерте кететін тағы бір жағдай, ол $\max{f\left( \overline{X} \right) }$ пен $\min{( - f\left( \overline{X} \right) }) -$ тің эквивалент екендігінде.

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

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

$f\left( \overline{X} \right) = 3x_{1} + 2x_{2} + 4x_{3} \rightarrow \max$

$\left\{ \begin{array}{r} 2x_{1} + x_{2} - 3x_{3} \leq 8 \\ 3x_{1} + 2x_{2} + x_{3} \leq 12 \\ x_{1} + 2x_{2} - x_{3} = 2 \end{array} \right. \$

$x_{j} \geq 0\, \ j = 1, 2, 3.$

Қосымша $x_{4} \geq 0$ және $x_{5} \geq 0$ белгісіздерін бірінші және екінші теңсіздіктердің оң жағына қосып жазып, мынадай канон есебін аламыз:

$f\left( \overline{X} \right) = 3x_{1} + 2x_{2} + 4x_{3} \rightarrow \max$

$\left\{ \begin{array}{r} 2x_{1} + x_{2} - 3x_{3} + x_{4} \leq 8 \\ 3x_{1} + 2x_{2} + x_{3}{+ x}_{5} \leq 12 \\ x_{1} + 2x_{2} - x_{3} = 2 \end{array} \right. \$

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

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

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

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

Дәлелдеу. Сызықтық программалау есебінің шешімінің сызықтық комбинациясы да сол есептің шешімі болатынын дәлелдеу қажет. Ол үшін $X_{1}, X_{2}$ векторлары сызықтық программалау есебінің шешімдері делік. Олай болса

${AX}_{1} = B$ , $X_{1} \geq 0$

және

${AX}_{2} = B$ , $X_{2} \geq 0$

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

$X = \alpha X_{1} + (1 - \alpha) X_{2}$ , $0 \leq \alpha \leq 1$

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

$AX = A\left\lbrack \alpha X_{1} + (1 - \alpha) X_{2} \right\rbrack = \alpha\left( AX_{1} \right) + (1 - \alpha) {(AX}_{2}) = \alpha B + \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + (1 - \alpha) B = B$

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

Жорамалымыз бойынша $x_{1} \geq 0\, \ x_{2} \geq 0\, \alpha \geq 0$

болғандықтан $X \geq 0$ . Демек теорема дәлелденді.

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

Дәлелдеу. Теореманың шарты бойынша сызықтық программалау есебінің анықталу облысын төбелерінің саны шекті көпжақ құрайды. Жазықтықта көпжақтың көпбұрыш болатыны белгілі. Теореманың дәлелдеуін жазықтықта қарастыралық. Көпбұрышты Д - деп, ал оның шет нүктелерін $X_{1}\, \ X_{2}\, \ \ldots, \ X_{p} - \$ деп белгілейік. Есептің оптимал шешімі $X_{0}$ болсын (сурет 1) . Олай болса кез-келген X $\epsilon Д$ үшін $f\left( X_{0} \right) \leq f(X)$ болады.

$C:\Users\user\AppData\Local\Temp\FineReader11.00\media\image1.png$

сурет 1

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

$X_{0} = \sum_{i = 1}^{p}{\alpha_{i}X_{i}}$

бұл жердегі

$\alpha_{i} \geq 0, i = 1, 2, \ldots, p, \sum_{i = 1}^{p}\alpha_{i} = 1$

бізде $f\left( \overline{X} \right)$ сызықтық функционал болған себепті:

$f\left( X_{0} \right) = f\left( \sum_{i = 1}^{p}{\alpha_{i}X_{i}} \right) = f\left( \alpha_{1}x_{1} + \alpha_{2}x_{2} + \ \ldots + \alpha_{p}x_{p} \right) = \alpha_{1}f\left( X_{1} \right) + \alpha_{2}f\left( X_{2} \right) + \ \ldots + \alpha_{p}f\left( X_{p} \right) = \sum_{i = 1}^{p}{\alpha_{i}f\left( X_{i} \right) }$

Барлық $f\left( X_{i} \right)$ ішіндегі ең кішісін тауып, оны m-ге тең делік. Ал барлық $f\left( X_{i} \right)$ ішіндегі ең кіші мәні $X_{k}$ үшін орындалсын делік. Демек

$\min_{i}\left\{ f\left( X_{i} \right) \right\} = f\left( X_{k} \right) = m$

Енді соңғы өрнектегі барлық $f\left( X_{i} \right)$ - ді $m -$ ге ауыстырсақ, онда мынадай теңсіздік аламыз:

$f\left( X_{0} \right) \geq \sum_{i = 1}^{p}{\alpha_{i}m} = m = f\left( X_{k} \right) \, \ \sum_{i = 1}^{p}\alpha_{i} = 1$

яғни

$f\left( X_{0} \right) \geq \ f\left( X_{k} \right)$

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

Енді осы теореманың екінші жартысын дәлелдейік. Ол үшін $f(X)$ функциясы бірнеше нүктеде минимал мән қабылдайды делік. Ол нүктелерді біз $X_{1}, \ X_{2}, \ \ldots, \ X_{q}$ деп белгілейік. Демек

$f\left( X_{1} \right) = f\left( X_{2} \right) = \ . . . = f\left( X_{q} \right) = m$

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

$X = \sum_{i = 1}^{q}{\alpha_{i}x_{i}\, }\alpha_{i} \geq 0\, \ \sum_{i = 1}^{q}\alpha_{i} = 1\$

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

$f(X) = f\left( \sum_{i = 1}^{q}{\alpha_{i}x_{i}\ } \right) = \sum_{i = 1}^{q}{\alpha_{i}{f(X}_{i}) } = \sum_{i = 1}^{q}\alpha_{i}m = m.$

Бұдан $X_{1}, \ X_{2}, \ \ldots, \ X_{q}$ нүктелерінің дөңес сызықтық комбинациясының да есептің минимал мәнін беретінін көрдік. Теорема дәлелденді.

3-теорема. Егер k(k=n) өзара тәуелсіз векторлар системасы $A_{1}, \ A_{2}, \ \ldots, \ A_{k}$ берілген болып, олар үшін $\sum_{}^{}A_{i}x_{i} = B$ теңдігі барлық $x_{i} \geq 0 -$ тар үшін орындалса, онда $X = \left( x_{1}\, \ x_{2}\, \ldots, \ x_{k}\, \ 0\ldots, \ 0 \right)$ векторы есептің анықталу облысын беретін көпжақтың шеткі нүктесі болады.

Дәлелдеу. $\ X$ нүктесі анықталу облысының ішкі нүктесі деп жорамалдайық. Олай болса ол нүкте сол облыстың екі шеткі $X_{1}, \ X_{2}$ нүктелерінің сызықтық комбинациясы түрінде бейнеленеді, яғни

$X = \alpha X_{1} + (1 - \alpha) X_{2}$

$0 < \alpha < 1$

Берілген $X$ векторының n-k компоненті нөлге тең болғандықтан, ал $X_{1}, \ X_{2}$ векторларының компоненттерінің теріс болуы мүмкін емес екенін және 0< $\ \alpha$ <1 екенін ескерсек, онда $X_{1}, \ X_{2}$ векторларының да n-k компоненттері нөлге тең болады. Демек