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

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

КІРІСПЕ

Симплекс әдісі . Бұл әдістің мағынасы мынада әуелі 2, 3 шарттарды қанағаттандыратын қандай да бір шешімді табамыз. Одан кейін белгілі тиімділік критериді пайдаланып, берілген есептің тиімді шешімін табамыз. Басқаша айтқанда есеп итерациялық әдіспен шешіледі. Яғни бір итерациядан 2-ші итерацияға көшкенде функцияның мәні кішірейе береді. Нәтижесінде есептің тиімді шешімі алынады. Шешімнің тиімділігі симплекс кесте арқылы тексеріледі.

Жүйелер теориясы әдістері-халық шаруашылығын тиімді басқару қажеттілігінен туған түрлі экономикалық, инженерлік есептерді шешуге бейімделген курс.

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

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

Экономикалық есептерді экстремум анықтайтын математикалық есептермен байланыстыруға болады. Математикалық есептің шешімі- экономикалық есептің шешімі болады. 1Қоғамдағы экономикалық процестердің математикалық аппарат (теңдеулер, теңсіздіктер) арқылы сипатталуы-экономика-математикалық модель деп аталады. Экономикалық процестерді сипаттайтын математикалық есептердің шешіміне талдау арқылы біз экономикалық жүйені зерттейміз.

Есептің шарттарын өзгерте отырып, экономикалық жүйенің түрлі шешімдерін алып, олардың ішінен ең пайдалысын таңдаймыз.

Экстременальды есептер мен оның шығару әдістері қолданбалы математиканың “математикалық программалау” деп аталатын саласында қарастырылады.

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

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

\[{\mathcal{N}}\]

векторлар жүйесінің m сызықты тәуелсіз векторларымен анықталатын тірек жоспарларымен байланысты. Бұл есептегі тірек жоспарларының саны С

\[\begin{array}{l}{{m}}\\ {{n}}\end{array}\]

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

Тірек жоспарлар құру: симплексті программалау есебі берілсін.

Z = C

\[\left|\sum\right|\]

\[\left\vert\mathbf{\varepsilon}\right\vert\]

+ … C

\[{\mathcal{N}}\backslash\]

(1)

(2)

\[X_{j}^{}\;_{j}^{}\;^{3}\;0\qquad\left(j=\overline{{{1,n}}}\right)\]

(3)

Табу керек ең кіші ең үлкен мәнін.

Шектеулер жүйесінің алдыңғы m векторын бірлік векторлар деп есептейміз, одан сызықты функцияны

\[\begin{array}{l}{{\displaystyle\sum x_{1}+a_{1},\ldots+a_{1n}\ x_{m+1}+\ldots+a_{1n}\ x_{n}=b_{1}}}\\ {{\displaystyle\frac{1}{2}\cdot\cdot\cdot a_{2}\cdot\ldots+a_{2n}\ x_{n}=b_{2}}}\\ {{\displaystyle\frac{1}{2}\sim\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot-\cdot\ -\ -\ -\ \cdot\ -\ -\ -\ -\ -\ -\ -\ -\ -\ -\ -\ -\ -\ -\ -\ -\ -\ -}}\\ {{\displaystyle\frac{1}{2}x_{m}+a_{m},_{m+1}\ x_{m+1}+\ldots+a_{m n}\ x_{n}=b_{n}}}\end{array}\]

(4)

\[x_{j}\,^{3}\,0\quad\left(j{\overline{{1}}},{\overline{{1}}}\right)\]

Табу керек ең кіші ең үлкен мәнін.

(4) - і формуланың векторлық түрде жазылуы.

\[{x_{1}\;}{A_{1}}+{x_{2}\;}{A_{2}}+\ldots+{x_{m}}\;A_{m}+{x_{m+1}}\;A_{m+1}+\ldots+{x_{n}}\;A_{n}=A_{0}\]

(5)

мұндағы:

\[\begin{array}{c}{{\frac{\alpha\mathbf{d}}{\mathbf{c}}\frac{\partial}{\mathbf{c}}}}\\ {{A_{1}={\boldsymbol{\nabla}}{\boldsymbol{0}}^{\frac{\omega}{\lambda}}}}\\ {{\mathbf{g}}}\\ {{\mathbf{A}_{1}={\frac{\mathbf{C}}{\mathbf{Q}}}{\mathbf{J}}{\boldsymbol{\Big)}}}}\end{array}\]

\[\begin{array}{r l}{{\frac{\mathrm{d}0}{\mathrm{G}}}{\frac{\mathrm{d}}{\mathrm{T}}}}\\ {A_{m}=\mathrm{G}^{\mathrm{G}}{\frac{\mathrm{i}}{\mathrm{M}}}}\\ {\mathbf{G}}&{{}}\\ {{\hat{\mathrm{g}}}{\hat{\mathrm{T}}}}\end{array}\]

\[\begin{array}{c c}{{\mathrm{ze}a_{1},\ m+\bar{\ldots}}}&{{\bar{\infty}}}\\ {{\nabla}}&{{\nabla}}\\ {{\bar{\zeta}}}&{{\bar{\zeta}}}\\ {{\bar{\zeta}}}&{{\cal{M}}}\\ {{\bar{\zeta}}}&{{\bar{\zeta}}}\\ {{\bar{\zeta}}}&{{\bar{\zeta}}}\end{array}\]

\[\begin{array}{c}{{\frac{\mathrm{d}D}{\mathrm{C}}_{1n}\ \frac{\mathrm{d}}{\mathrm{S}}}{\mathrm{S}}}\\ {{\mathrm{}}}\\ {{A_{n}=\underbrace{\mathrm{C}}{\mathrm{S}}_{\mathrm{}}\ {\frac{\mathrm{d}}{\mathrm{}}}_{\mathrm{}}}}\\ {{\mathrm{}}}\\ {{\hat{\mathrm{}}}}\\ {{\hat{\mathrm{}}}}\\ {{\hat{\mathrm{}}}}\\ {{\hat{\mathrm{}}}}\end{array}\]

\[\begin{array}{c}{{\frac{\alpha b}{\mathrm{g}}b,\quad\quad}}\\ {{A_{0}={\frac{\mathrm{g}}{\mathrm{g}}}\frac{\omega}{\mathrm{g}}}}\\ {{\bar{\mathrm{g}}b,\quad\quad}}\end{array}\]

\[A_{1\dots}\,A_{n}\]

векторлары m өлшемді кеңістіктің сызықты тәуелсіз бірлік векторлары сондықтан базистық айнымалылар ретінде

\[\mathcal{N}_{1}\triangleright\circ\circ\circ\gamma~\mathcal{N}_{D}\]

таңдап

\[X_{m+1}\cdot\quad\mathcal{X}_{m+2}\cdot\quad\mathcal{X}_{n}\]

бас айнымалылары

\[0=A_{1}\cdot\cdot A_{m}\]

бірлік векторларын

\[b_{i}\geq0\]

ескерсек алғашқы

\[x_{0}=\left(x_{1}=b_{1},\ \ x_{2}=b_{2},...,x_{m}=b_{m},\ \ x_{m+1}=0,...,x_{n}=0\right)\]

(6)

жоспарын аламыз. Бұл жоспарға

\[{x_{1}\,A_{1}+x_{2}\,A_{2}+....+x_{m}A_{m}=A_{0}}\]

(7)

жіктеуі сәйкес. Мұндағы сызықты тәуелсіз демек құрылған алғашқы жоспар тірек жоспар болып саналады. Алғашқы (6) жоспары екінші тірек жоспарға өтетіндігін тексереміз

\[A_{1}\ldots A_{m}\]

векторы m өлшемді кеңістікте базис құрайды (5) жүйедегі әр векторды базис векторларына бір жолмен жіктеуге болады. Яғни

(8)

Базиске кірмейтін

\[\ A_{m+1}\]

векторы үшін

(9)

Жіктеудегі

\[{\mathcal{X}}_{i}\cdot\ m+1\]

коэффициентінің ең болмаса 1 - і оң болсын (9) жіктеудің 2 жағында кез келген

\[{\boldsymbol{\theta}}>0\]

көбейтіп нәтижені (7) - ден мүшелеп алып тастасақ онда

(10)

Егер ком - рі теріс болмаса

\[x_{1}={\big(}x_{1}-{\theta}~x_{1},\dots_{1}{\big)}\]

;

векторлары жоспар болып құрамына

\[{\mathcal{X}}_{i}\cdot\ m+1\]

теріс таңбамен енетін

\[\textstyle{X_{1}}\]

векторының компоненттері

\[{\boldsymbol{\theta}}>0\]

болғандықтан оң сандар болады. Сондықтан құрамында тек оң

\[{\mathcal{X}}_{i}\cdot\ m+1\]

\[\geq0\]

үшін

\[X_{i}-\theta\ X_{i},\ _{m+1}\ \geq0\]

(11) орындалатындай

\[{\boldsymbol{\theta}}>0\]

табу керек

(11) =>

\[q\pounds\Xi\frac{x_{i}}{x_{i},\,m\!+\!1}\;\;\;\;\tilde{a}\hat{a}\hat{a}\hat{a}\hat{e}\;\;\;\;\;x_{l}\;\;0\ \Xi\theta\;\le\mathrm{in}\frac{x_{i}}{x_{i},\,m\!+\!1}\]

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

Тиімді жоспар іздеу тиімділік шарты

Сызықты программалау есебі (1) - (5) жоспарлары бар және оның әр жоспары тәуелсіз онда (6) тірек жоспары үшін

\[{\cal X}_{1}\,{\cal A}_{1}+{\cal X}_{2}\,{\cal A}_{2}+...+{\cal X}_{n}\,{\cal A}_{n}={\cal A}_{0}\]

(12)

\[x_{1}\,c_{1}+x_{2}\,c_{2}+\ldots+x_{n}\,c_{n}=z(x_{0})\]

(13)

\[x_{i}\gg0\]

, ал

\[z(x_{a})\]

осы жоспарға сәйкес кез келген

\[{\cal A}_{j}\ \left({\cal A}_{1},\ast...\,{\cal A}_{m}\right)\]

базис векторына жалғыз ғана жіктелуі бар.

\[\begin{array}{l}{{X_{1j}~\ A_{j}\dag\chi_{2j}~\lambda_{1j}\dag\ast_{**}\rightarrow\zeta_{m j}~\Lambda_{j}\rightarrow\Omega_{0}~\Lambda_{j}\rightarrow\Delta_{0}~\mathrm{cl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~\mathrm{sl}~}}\end{array}\]

(14)

\[{\mathcal{X}}_{1j}\,C_{j}+{\mathcal{X}}_{2j}\,C_{j}+\dots+{\mathcal{X}}_{m j}\,C_{j}={\mathcal{Z}}_{j}\]

(15)

Мұндағы

\[{\mathcal{Z}}_{j}\]

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

\[C_{j}\]

арқылы

\[A_{j}\]

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

Теорема : Егер кез келген

\[A_{j}\]

векторы үшін

\[{{\mathcal{L}}_{j}}\,^{\cdot\,}\,C_{j}>0\]

онда

\[{\mathcal{X}}_{0}\]

жоспары тиімді емес

\[z(x) шарты орындалатындай х жоспарын құруға болады.

Теорема : Егер кез келген

\[{{\mathcal{L}}_{j}}\,-\,{{\mathcal{L}}_{j}}\,\ll\,0\]

онда

\[{\mathcal{X}}_{0}\]

тиімді емес

\[z(x)>z(x_{0})\]

шарты орындалатындай х жоспарын құруға болады.

Симплекс әдісінің алгоритмі

\[\bigl(x\bigr)=C_{0}+\sum_{j=1}^{n}C_{j}\;x_{j}\]

(1)

(2)

\[x_{j}\ {}^{3}\ 0\qquad\qquad\left(j=\overline{{{1,n}}}\right)\]

(3)

№

базис

\[A_{0}\]

\[\bar{N}_{1}\]

\[C_{2}\]

. . .

\[\bigcap_{1}\]

\[C_{m}\]

\[C_{m+1}\]

. . .

\[\bar{N}_{j}\]

\[\widehat{A}_{1}\]

\[\mathbf{A}_{2}\]

. . .

\[\widehat{A}_{l}\]

\[A_{m}\]

\[A_{m+1}\]

. . .

\[A_{j}\]

№: 1

базис:

\[\mathbb{A}_{1}\]

Сбазис:

\[\bar{N}_{1}\]

\[{\mathcal{X}}_{1}\]

: 1

: 0

. . .: . . .

: 0

\[X_{1j m+1}\]

. . .: . . .

\[{\mathcal{X}}_{1j}\]

№: 2

базис:

\[\textstyle A_{2}\]

Сбазис:

\[\bar{N}_{2}\]

\[X_{2}\]

: 0

: 1

. . .: . . .

: 0

\[X_{2j m+1}\]

. . .: . . .

\[{\mathcal{X}}_{2j}\]

№: l

базис:

\[\widehat{A}_{l}\]

Сбазис:

\[\bar{N}_{l}\]

\[\textstyle{X_{I}}\]

: 0

. . .: . . .

: 1

: 0

. . .: . . .

№: M

базис:

\[A_{m}\]

Сбазис:

\[\bar{N}_{m}\]

\[X_{m}\]

: 0

. . .: . . .

: 0

: 1

. . .: . . .

№: M+1

базис:

\[{\mathcal{L}}_{j}-C_{j}\]

Сбазис:

\[{\mathcal{Z}}_{0}\]

: 0

. . .: . . .

: 0

\[Z_{m+1}\]

\[C_{m+1}\]

. . .: . . .

\[{\mathcal{Z}}_{j}\]

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

Қосымша теріс емес айнымалылары базистік болып табылады, себебі (4), (5) теңдеулер жүйесінің коэффициентін құрылған мақсаттық соңғы М бағанда сызықты тәуелсіз бірлік матрица демек осы бағандарға сәйкес келетін теріс емес айнымалыларда

\[x_{n+1}\mathbf{\delta}0\ \left(\left(-1{\mathrm{,}}m\right)\right)\]

базистік айнымалылар бағандарына бақлау қосындыларын және

\[\theta\]

тұратын симплекстік кесте құрамыз. Ол индекстік деп аталады. Симплекс кестенің соңғы жолы қарама - қарсы таңбалармен алынған сызықты форма коэфф толтырылады.

Құрылған жоспарға тиімділік шартының орындалуын тексереміз. жоспары тиімді болу үшін индекстік жолдың барлық коэффициенті (- н басқалары ) сызықты программалау есебінmaxшешкенде теріс емесminоң емес болса жеткілікті. Егер тиімділік шарты орындалса есеп шешіледі. Базистік айнымалылар және бос мүшелер бағандарында сәйкесінше құрылған тиімді жоспарлар компоненттері, индекстік жолмен бос мүшелер бағанының қиылысындасызықты формуланың экстрималды мәні орналасқан.
Егер тиімділік шарты орындалса онда есептімахшешкенде индекстік жолдың теріс коэффициенттік обсолюттік шамаларының үлкенін, алminиндекс жолдың оң коэффициент ең кішісін таңдаймыз. Таңдалған ең үлкен коэффициент сәйкес бағанда шешуші деп аталады. Шешуші баған қандай айнымалының базиске кіретінін көрсетеді.
Бос мүшелер бағана элементтерінің шешуші бағанының тек оң элементіне қатнасын есептейді. Егер ондай элементтер жоқ болса сызықты программалау есебінің шешімі жоқ және олардыбағанына жазады. бағанының барлық элементтер ішінен ең кішісін таңдайды. - ң ең кіші мәніні ие симплекс кестенің жолын шешуші деп айтады. Шешуші жол қандай айнымалының базистен шығатынын көрсетеді. Шешуші баған мен жол қиылысқан жерде бас элемент тұрады.
Сиплекс кестесін келесі тәртібіне толтырамыз:

а) Шешуші бағанға сәйкес бос айнымалыны базистік айнымалыға енгіземіз АМ шешуші жолға сәйкес базистік айнымалыны бос айнымалыларға ауыстырамыз.

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

в) Шешуші бағанға сәйкес бос айнымалыны базиске көшіру үшін оны бағыттаушы жолдан басқа барлық жолдардан алып тастау қажет. Ол үшін алдынғы кестені шешуші бағанына сәйкес бағанның қалған барлық ұяшықтарына Гаус әдісімен 0 - дер жинаймыз. Симплекс кестелерінде есептеулерді симплекс белгісі орындалғанша жалғастырамыз.

2 Есептің қойылымы

Параметрлік программалау есебін Cимплекс әдісі бойынша шешу.

F=(2+t) x ₁ -(3-t) x ₂ +3(2+4t) x ₅ max

x ₁ , x ₂ , …, x ₅

\[\underline{{\gg}}\]

Шешімі: есепті стандарты түрде келтіреміз:

F=(2+t) x ₁ -(3-t) x ₂ +3(2+4t) x ₅

\[\frac{\kappa_{\geq}}{\phi^{\beta}}\]

max

\[\begin{array}{c}{{\mathbf{i}\ x_{1}+2x_{2}=4+6t}}\\ {{\mathbf{i}^{\mathrm{T}}\cdot x_{1}+3x_{2}\mathbf{\delta}=9-12}}\\ {{\mathbf{i}\vec{x}_{1}-\ x_{2}\mathbf{\delta}=8+9t}}\end{array}\]

. 3

x ₁ , x ₂

\[\underline{{\gg}}\]

_{. 3} 0

1-ші симплекс таблицаны құрамыз:

... жалғасы

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