The Main Theorems of Linear Programming

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.