 Criterion of StabilityF. P. Vasilyev and
A. Yu. Ivanitskiy
Chapter Chapter 4 in In-Depth Analysis of Linear Programming, 2001, pp 167-202 from Springer Abstract: Abstract Consider the general linear programming problem (4.1.1) % MathType!MTEF!2!1!+- % feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaWGMb % GaaiikaiaadIhacaGGPaGaeyypa0ZaaaWaaeaacaWGJbGaaiilaiaa % dIhaaiaawMYicaGLQmcacqGH9aqpdaaadaqaaiaadogadaWgaaWcba % GaaGymaaqabaGccaGGSaGaamiEamaaBaaaleaacaaIXaaabeaaaOGa % ayzkJiaawQYiaiabgUcaRmaaamaabaGaam4yamaaBaaaleaacaaIYa % aabeaakiaacYcacaWG4bWaaSbaaSqaaiaaikdaaeqaaaGccaGLPmIa % ayPkJaGaeyOKH4QaciyAaiaac6gacaGGMbGaaiilaiaaywW7caWG4b % Gaeyypa0ZaamWaaeaacaWG4bWaaSbaaSqaaiaaigdaaeqaaOGaaiil % aiaadIhadaWgaaWcbaGaaGOmaaqabaaakiaawUfacaGLDbaacqGHii % IZcaWGybGaaiilaaqaaiaaywW7caaMf8Uaamiwaiabg2da9iaacUha % caWG4bGaeyypa0ZaaeWaaeaacaWG4bWaaSbaaSqaaiaaigdaaeqaaO % GaaiilaiaadIhadaWgaaWcbaGaaGOmaaqabaaakiaawIcacaGLPaaa % caGG6aGaamiEamaaBaaaleaacaaIXaaabeaakiabgIGiolaadweada % ahaaWcbeqaaiaad6gadaWgaaadbaGaaGymaaqabaaaaOGaaiilaiaa % dIhadaWgaaWcbaGaaGOmaaqabaGccqGHiiIZcaWGfbWaaWbaaSqabe % aacaWGUbWaaSbaaWqaaiaaikdaaeqaaaaakiaacYcacaWG4bWaaSba % aSqaaiaaigdaaeqaaOGaeyyzImRaaGimaiaacYcaaeaacaaMf8UaaG % zbVlaaywW7caaMf8UaamyqamaaBaaaleaacaaIXaGaaGymaaqabaGc % caWG4bWaaSbaaSqaaiaaigdaaeqaaOGaey4kaSIaamyqamaaBaaale % aacaaIXaGaaGOmaaqabaGccaWG4bWaaSbaaSqaaiaaikdaaeqaaOGa % eyizImQaamOyamaaBaaaleaacaaIXaGaaiilaaqabaGccaaMf8Uaam % yqamaaBaaaleaacaaIYaGaaGymaaqabaGccaWG4bWaaSbaaSqaaiaa % igdaaeqaaOGaey4kaSIaamyqamaaBaaaleaacaaIYaGaaGOmaaqaba % GccaWG4bWaaSbaaSqaaiaaikdaaeqaaOGaeyypa0JaamOyamaaBaaa % leaacaaIYaaabeaakiaac2haaaaa!A4C5! $$ \begin{array}{l}f(x) = \left\langle {c,x} \right\rangle = \left\langle {{c_1},{x_1}} \right\rangle + \left\langle {{c_2},{x_2}} \right\rangle \to \inf ,\quad x = \left[ {{x_1},{x_2}} \right] \in X, \\\quad \quad X = \{ x = \left( {{x_1},{x_2}} \right):{x_1} \in {E^{{n_1}}},{x_2} \in {E^{{n_2}}},{x_1} \ge 0, \\\quad \quad \quad \quad {A_{11}}{x_1} + {A_{12}}{x_2} \le {b_{1,}}\quad {A_{21}}{x_1} + {A_{22}}{x_2} = {b_2}\} \\\end{array} $$ , where % MathType!MTEF!2!1!+- % feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqamaaBa % aaleaacaWGPbGaamOAaaqabaGccqGH9aqpdaGadaqaamaabmaabaGa % amyyamaaBaaaleaacaWGPbGaamOAaaqabaaakiaawIcacaGLPaaada % WgaaWcbaGaamOCaiaadYgaaeqaaOGaaiilaiaadkhacqGH9aqpdaqd % aaqaaiaaigdacaGGSaGaamyBamaaBaaaleaacaWGPbaabeaaaaGcca % GGSaGaamiBaiabg2da9maanaaabaGaaGymaiaacYcacaWGUbWaaSba % aSqaaiaadQgaaeqaaaaaaOGaay5Eaiaaw2haaaaa!4F1C! $$ {A_{ij}} = \left\{ {{{\left( {{a_{ij}}} \right)}_{rl}},r = \overline {1,{m_i}} ,l = \overline {1,{n_j}} } \right\} $$ , is a matrix of dimension % MathType!MTEF!2!1!+- % feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaSbaaSqaai % aadQgaaeqaaOGaaiilaiaadogadaWgaaWcbaGaamOAaaqabaGccqGH % 9aqpdaqadaqaaiaadogadaqhaaWcbaGaamOAaaqaaiaaigdaaaGcca % GGSaGaaiOlaiaac6cacaGGUaGaaiilaiaadogadaqhaaWcbaGaamOA % aaqaaiaad6gadaWgaaadbaGaamOAaaqabaaaaaGccaGLOaGaayzkaa % GaeyicI4SaamyramaaCaaaleqabaGaamOBamaaBaaameaacaWGQbaa % beaaaaGccaGGSaGaaGjbVlaadkgadaWgaaWcbaGaamyAaaqabaGccq % GH9aqpdaqadaqaaiaadkgadaqhaaWcbaGaamyAaaqaaiaaigdaaaGc % caGGSaGaaiOlaiaac6cacaGGUaGaaiilaiaadkgadaqhaaWcbaGaam % yAaaqaaiaad2gacaWGPbaaaaGccaGLOaGaayzkaaGaeyicI4Saamyr % amaaCaaaleqabaGaamyBamaaBaaameaacaWGPbaabeaaaaGccaGGSa % GaaGjbVlaadMgacaGGSaGaamOAaiabg2da9iaaigdacaGGSaGaaGOm % aiaacYcacaaMe8Uaam4yaiabg2da9maabmaabaGaam4yamaaBaaale % aacaaIXaaabeaakiaacYcacaWGJbWaaSbaaSqaaiaaikdaaeqaaaGc % caGLOaGaayzkaaGaaiilaiaaysW7caWGIbGaeyypa0ZaaeWaaeaaca % WGIbWaaSbaaSqaaiaaigdaaeqaaOGaaiilaiaadkgadaWgaaWcbaGa % aGOmaaqabaaakiaawIcacaGLPaaaaaa!7D07! $$ _j,{c_j} = \left( {c_j^1,...,c_j^{{n_j}}} \right) \in {E^{{n_j}}},\;{b_i} = \left( {b_i^1,...,b_i^{mi}} \right) \in {E^{{m_i}}},\;i,j = 1,2,\;c = \left( {{c_1},{c_2}} \right),\;b = \left( {{b_1},{b_2}} \right) $$ . Let X ≠ ∅, f * = inf x ∈X f(x) > -∞. Then, according to Theorem 2.1.1, the set X * = {x ∈ X: f(x) = f *} is nonempty. Assume that instead of the exact initial data A ij , c j , b i we are only given their approximations % MathType!MTEF!2!1!+- % feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamyqamaaBa % aaleaacaWGPbGaamOAaaqabaGccaGGOaGaeqiTdqMaaiykaiabg2da % 9maacmaabaWaaeWaaeaacaWGHbWaaSbaaSqaaiaadMgacaWGQbaabe % aakiaacIcacqaH0oazcaGGPaaacaGLOaGaayzkaaWaaSbaaSqaaiaa % dkhacaWGSbaabeaakiaacYcacaaMe8UaamOCaiabg2da9maanaaaba % GaaGymaiaacYcacaWGTbWaaSbaaSqaaiaadMgaaeqaaaaakiaacYca % caaMe8UaamiBaiabg2da9maanaaabaGaaGymaiaad6gadaWgaaWcba % GaamOAaaqabaaaaaGccaGL7bGaayzFaaGaaiilaiaaysW7caWGJbWa % aSbaaSqaaiaadQgaaeqaaOGaaiikaiabes7aKjaacMcacqGH9aqpca % GGOaGaam4yamaaDaaaleaacaWGQbaabaGaaGymaaaakiaacIcacqaH % 0oazcaGGPaGaaiilaiaac6cacaGGUaGaaiOlaiaacYcacaWGJbWaa0 % baaSqaaiaadQgaaeaacaWGUbWaaSbaaWqaaiaadQgaaeqaaaaakiaa % cMcacaGGSaGaaGjbVlaadkgadaWgaaWcbaGaamyAaaqabaGccaGGOa % GaeqiTdqMaaiykaiabg2da9iaacIcacaWGIbWaa0baaSqaaiaadMga % aeaacaaIXaaaaOGaaiikaiabes7aKjaacMcacaGGSaGaaiOlaiaac6 % cacaGGUaGaaiilaiaadkgadaqhaaWcbaGaamyAaaqaaiaad2gadaWg % aaadbaGaamyAaaqabaaaaOGaaiikaiabes7aKjaacMcacaGGPaaaaa!887A! $$ {A_{ij}}(\delta ) = \left\{ {{{\left( {{a_{ij}}(\delta )} \right)}_{rl}},\;r = \overline {1,{m_i}} ,\;l = \overline {1{n_j}} } \right\},\;{c_j}(\delta ) = (c_j^1(\delta ),...,c_j^{{n_j}}),\;{b_i}(\delta ) = (b_i^1(\delta ),...,b_i^{{m_i}}(\delta )) $$ such that (4.1.2) % MathType!MTEF!2!1!+- % feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaadaabda % qaaiaacIcacaWGHbWaaSbaaSqaaiaadMgacaWGQbaabeaakiaacIca % cqaH0oazcaGGPaGaaiykamaaBaaaleaacaWGYbGaamiBaaqabaGccq % GHsislcaGGOaGaamyyamaaBaaaleaacaWGPbGaamOAaaqabaGccaGG % PaWaaSbaaSqaaiaadkhacaWGSbaabeaaaOGaay5bSlaawIa7aiabgs % MiJkabes7aKjaacYcacaaMf8+aaqWaaeaacaWGJbWaa0baaSqaaiaa % dQgaaeaacaWGSbaaaOGaaiikaiabes7aKjaacMcacqGHsislcaWGJb % Waa0baaSqaaiaadQgaaeaacaWGSbaaaaGccaGLhWUaayjcSdGaeyiz % ImQaeqiTdqMaaiilaiaaywW7daabdaqaaiaadkgadaqhaaWcbaGaam % yAaaqaaiaadkhaaaGccaGGOaGaeqiTdqMaaiykaiabgkHiTiaadkga % daqhaaWcbaGaamyAaaqaaiaadkhaaaaakiaawEa7caGLiWoacqGHKj % YOcqaH0oazcaGGSaaabaGaaGzbVlaaywW7caaMf8UaaGzbVlaaywW7 % caWGYbGaeyypa0Zaa0aaaeaacaaIXaGaaiilaiaad2gadaWgaaWcba % GaamyAaaqabaaaaOGaaiilaiaaywW7caWGSbGaeyypa0Zaa0aaaeaa % caaIXaGaaiilaiaad6gadaWgaaWcbaGaamOAaaqabaaaaOGaaiilai % aaywW7caWGPbGaaiilaiaadQgacqGH9aqpcaaIXaGaaiilaiaaikda % aaaa!9054! $$ \begin{array}{l}\left| {{{({a_{ij}}(\delta ))}_{rl}} - {{({a_{ij}})}_{rl}}} \right| \le \delta ,\quad \left| {c_j^l(\delta ) - c_j^l} \right| \le \delta ,\quad \left| {b_i^r(\delta ) - b_i^r} \right| \le \delta , \\\quad \quad \quad \quad \quad r = \overline {1,{m_i}} ,\quad l = \overline {1,{n_j}} ,\quad i,j = 1,2 \\\end{array} $$ , where the quantity δ > 0 is an error in the assignment of the initial data. Keywords: Dual Problem; Linear Programming Problem; Conditional Stability; Canonical Problem; Conical Hull (search for similar items in EconPapers) There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it. Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-94-015-9759-3_4 Ordering information: This item can be ordered from DOI: 10.1007/978-94-015-9759-3_4 Access Statistics for this chapter More chapters in Springer Books from Springer |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.