The Main Theorems of Linear Programming

F. P. Vasilyev and A. Yu. Ivanitskiy
Additional contact information
F. P. Vasilyev: Moscow State University
A. Yu. Ivanitskiy: Chuvash State University

Chapter Chapter 2 in In-Depth Analysis of Linear Programming, 2001, pp 79-118 from Springer

Abstract: Abstract Recall that the general problem of linear programming can be formulated as follows: (2.1.1) % MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later! % MathType!MTEF!2!1!+- % feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaWGMb % GaaiikaiaadIhacaGGPaGaeyypa0ZaaaWaaeaacaWGJbGaaiilaiaa % dIhaaiaawMYicaGLQmcacqGH9aqpdaaadaqaaiaadogadaWgaaWcba % GaaGymaaqabaGccaGGSaGaamiEamaaBaaaleaacaaIXaaabeaaaOGa % ayzkJiaawQYiaiabgUcaRmaaamaabaGaam4yamaaBaaaleaacaaIYa % aabeaakiaacYcacaWG4bWaaSbaaSqaaiaaikdaaeqaaaGccaGLPmIa % ayPkJaGaeyOKH4QaciyAaiaac6gacaGGMbGaaiilaiaadIhacqGH9a % qpdaqadaqaaiaadIhadaWgaaWcbaGaaGymaaqabaGccaGGSaGaamiE % amaaBaaaleaacaaIYaaabeaaaOGaayjkaiaawMcaaiabgIGiolaadI % facaGGSaaabaGaamiwaiabg2da9maaceaabaGaamiEaiabg2da9maa % bmaabaGaamiEamaaBaaaleaacaaIXaaabeaakiaacYcacaWG4bWaaS % baaSqaaiaaikdaaeqaaaGccaGLOaGaayzkaaGaaiOoaiaadIhaaiaa % wUhaamaaBaaaleaacaaIXaaabeaakiabgIGiolaadweadaahaaWcbe % qaaiaad6gacaaIXaaaaOGaaiilaiaadIhadaWgaaWcbaGaaGOmaaqa % baGccqGHiiIZcaWGfbWaaWbaaSqabeaacaWGUbGaaGOmaaaakiaacY % cacaWG4bWaaSbaaSqaaiaaigdaaeqaaOGaeyyzImRaaGimaiaacYca % aeaacaWGbbWaaSbaaSqaaiaaigdacaaIXaaabeaakiaadIhadaWgaa % WcbaGaaGymaaqabaGccqGHRaWkcaWGbbWaaSbaaSqaaiaaigdacaaI % YaaabeaakiaadIhadaWgaaWcbaGaaGOmaaqabaGccqGHKjYOcaWGIb % GaaiilaiaadgeadaWgaaWcbaGaaGOmaiaaigdaaeqaaOGaamiEamaa % BaaaleaacaaIXaaabeaakiabgUcaRiaadgeadaWgaaWcbaGaaGOmai % aaikdaaeqaaOGaamiEamaaBaaaleaacaaIYaaabeaakiabg2da9maa % ciaabaGaamOyamaaBaaaleaacaaIYaaabeaaaOGaayzFaaaaaaa!96D8! $$ \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 ,x = \left( {{x_1},{x_2}} \right) \in X, \\X = {\left\{ {x = \left( {{x_1},{x_2}} \right):x} \right._1} \in {E^{n1}},{x_2} \in {E^{n2}},{x_1} \ge 0, \\{A_{11}}{x_1} + {A_{12}}{x_2} \le b,{A_{21}}{x_1} + {A_{22}}{x_2} = \left. {{b_2}} \right\} \\\end{array} $$ where A ij are m i × n j matrices, c j ∈ Enj, bi ∈E mi , i,j = 1,2. As before, we denote f * = inf x∈X f(x) assuming that X ∈ Ø. For the case where f * > -∞ we introduce a set % MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later! % MathType!MTEF!2!1!+- % feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiwamaaBa % aaleaacaGGQaaabeaakiabg2da9maacmaabaGaamiEaiabgIGiolaa % dIfacaGG6aGaamOzaiaacIcacaWG4bGaaiykaiabg2da9iaadAeada % WgaaWcbaGaaiOkaaqabaaakiaawUhacaGL9baaaaa!44FC! $$ {X_*} = \left\{ {x \in X:f(x) = {F_*}} \right\} $$ . Recall that problem (2.1.1) is solvable if X* ≠ Ø; every point x* ∈ X* is a solution of this problem.

Date: 2001
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-94-015-9759-3_2

Ordering information: This item can be ordered from
http://www.springer.com/9789401597593

DOI: 10.1007/978-94-015-9759-3_2

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().