 Simplex MethodF. P. Vasilyev and
A. Yu. Ivanitskiy
Chapter Chapter 1 in In-Depth Analysis of Linear Programming, 2001, pp 1-77 from Springer Abstract: Abstract The general linear programming problem can be formulated as follows: minimize the function (1.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-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOzaiaacI % cacaWG4bGaaiykaiabg2da9iaadogadaahaaWcbeqaaiaaigdaaaGc % caWG4bWaaWbaaSqabeaacaaIXaaaaOGaey4kaSIaam4yamaaCaaale % qabaGaaGOmaaaakiaadIhadaahaaWcbeqaaiaaikdaaaGccqGHRaWk % caGGUaGaaiOlaiaac6cacqGHRaWkcaWGJbWaaWbaaSqabeaacaWGUb % aaaOGaamiEamaaCaaaleqabaGaamOBaaaaaaa!4AB8! $$ f(x) = {c^1}{x^1} + {c^2}{x^2} + ... + {c^n}{x^n} $$ under the conditions (1.1.2) % MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later! % MathType!MTEF!2!1!+- % feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamiEamaaCa % aaleqabaGaam4AaaaakiabgwMiZkaaicdacaGGSaGaam4AaiabgIGi % olaadMeadaWgaaWcbaGaey4kaScabeaaaaa!3F96! $$ {x^k} \ge 0,k \in {I_+ } $$ , (1.1.3) % MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later! % MathType!MTEF!2!1!+- % feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaiGaaqaabe % qaaiaadggadaWgaaWcbaGaaGymaiaaigdaaeqaaOGaamiEamaaCaaa % leqabaGaaGymaaaakiabgUcaRiaadggadaWgaaWcbaGaaGymaiaaik % daaeqaaOGaamiEamaaCaaaleqabaGaaGOmaaaakiabgUcaRiaac6ca % caGGUaGaaiOlaiaac6cacqGHRaWkcaWGHbWaaSbaaSqaaiaaigdaca % WGUbaabeaakiaadIhadaahaaWcbeqaaiaad6gaaaGccqGHKjYOcaWG % IbWaaWbaaSqabeaacaaIXaaaaOGaaiilaaqaaiaac6cacaGGUaGaai % Olaiaac6cacaGGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6cacaGG % UaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6 % cacaGGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6cacaGGUaGaaiOl % aiaac6cacaGGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6cacaGGUa % GaaiOlaiaac6cacaGGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6ca % aeaacaWGHbWaaSbaaSqaaiaad2gacaaIXaaabeaakiaadIhadaahaa % WcbeqaaiaaigdaaaGccqGHRaWkcaWGHbWaaSbaaSqaaiaad2gacaaI % YaaabeaakiaadIhadaahaaWcbeqaaiaaikdaaaGccqGHRaWkcaGGUa % GaaiOlaiaac6cacqGHRaWkcaWGHbWaaSbaaSqaaiaad2gacaWGUbaa % beaakiaadIhadaahaaWcbeqaaiaad6gaaaGccqGHKjYOcaWGIbWaaW % baaSqabeaacaWGTbaaaOGaaiilaaaacaGL9baaaaa!8469! $$ \left. \begin{array}{l}{a_{11}}{x^1} + {a_{12}}{x^2} + .... + {a_{1n}}{x^n} \le {b^1}, \\........................................... \\{a_{m1}}{x^1} + {a_{m2}}{x^2} + ... + {a_{mn}}{x^n} \le {b^m}, \\\end{array} \right\} $$ (1.1.4) % MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later! % MathType!MTEF!2!1!+- % feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaiGaaqaabe % qaaiaadggadaWgaaWcbaGaamyBaiabgUcaRiaaigdacaGGSaGaaGym % aaqabaGccaWG4bWaaWbaaSqabeaacaaIXaaaaOGaey4kaSIaamyyam % aaBaaaleaacaWGTbGaey4kaSIaaGymaiaacYcacaaIYaaabeaakiaa % dIhadaahaaWcbeqaaiaaikdaaaGccqGHRaWkcaGGUaGaaiOlaiaac6 % cacqGHRaWkcaWGHbWaaSbaaSqaaiaad2gacqGHRaWkcaaIXaGaaiil % aiaad6gaaeqaaOGaamiEamaaCaaaleqabaGaamOBaaaakiabgsMiJk % aadkgadaahaaWcbeqaaiaad2gacqGHRaWkcaaIXaaaaOGaaiilaaqa % aiaac6cacaGGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6cacaGGUa % GaaiOlaiaac6cacaGGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6ca % caGGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6cacaGGUaGaaiOlai % aac6cacaGGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6cacaGGUaGa % aiOlaiaac6cacaGGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6caca % GGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaa % c6cacaGGUaGaaiOlaiaac6cacaGGUaGaaiOlaiaac6cacaGGUaGaai % Olaiaac6cacaGGUaaabaGaamyyamaaBaaaleaacaWGZbGaaGymaaqa % baGccaWG4bWaaWbaaSqabeaacaaIXaaaaOGaey4kaSIaamyyamaaBa % aaleaacaWGZbGaaGOmaaqabaGccaWG4bWaaWbaaSqabeaacaaIYaaa % aOGaey4kaSIaaiOlaiaac6cacaGGUaGaey4kaSIaamyyamaaBaaale % aacaWGZbGaamOBaaqabaGccaWG4bWaaWbaaSqabeaacaWGUbaaaOGa % eyizImQaamOyamaaCaaaleqabaGaam4CaaaaaaGccaGL9baaaaa!979F! $$ \left. \begin{array}{l}{a_{m + 1,1}}{x^1} + {a_{m + 1,2}}{x^2} + ... + {a_{m + 1,n}}{x^n} \le {b^{m + 1}}, \\........................................................... \\{a_{s1}}{x^1} + {a_{s2}}{x^2} + ... + {a_{sn}}{x^n} \le {b^s} \\\end{array} \right\} $$ where % MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later! % MathType!MTEF!2!1!+- % feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaam4yamaaCa % aaleqabaGaamOAaaaakiaacYcacaWGIbWaaWbaaSqabeaacaWGPbaa % aOGaaiilaiaadggadaWgaaWcbaGaamyAaiaadQgaaeqaaOGaaiilai % aadMgacqGH9aqpdaqdaaqaaiaaigdacaGGSaGaam4CaaaacaGGSaGa % amOAaiabg2da9maanaaabaGaaGymaiaacYcacaWGUbaaaaaa!4891! $$ {c^j},{b^i},{a_{ij}},i = \overline {1,s} ,j = \overline {1,n} $$ are given numbers, I + is the given subset of indices from the set {1,2,... , n}. The function (1.1.1) is known as an objective function, conditions (1.1.3) are constraints of the type of inequalities, conditions (1.1.4) are constraints of the type of equalities. Conditions (1.1.2) of nonnegativity of the variables are, of course, also constraints of the type of inequalities, but it is customary to consider them separately. Problem (1.1.1)-(1.1.4) may include cases where % MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later! % MathType!MTEF!2!1!+- % feaaguart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamysamaaBa % aaleaacqGHRaWkaeqaaOGaeyypa0JaeyybIySaam4BaiaadkhacaWG % jbWaaSbaaSqaaiabgUcaRaqabaGccqGH9aqpcaGG7bGaaGymaiaacY % cacaaIYaGaaiilaiaac6cacaGGUaGaaiOlaiaacYcacaWGUbGaaiyF % aaaa!47BE! $$ {I_ + } = \emptyset or{I_ + } = \{ 1,2,...,n\} $$ it is also possible that problem (1.1.1)-(1.1.4) may not contain constraints of the type of inequalities or equalities. We call the point x = (x 1, ..., x n ) which satisfies all conditions (1.1.2)–(1.1.4) an admissible point of problem (1.1.1)–(1.1.4) or simply an admissible point. Keywords: Extreme Point; Linear Programming Problem; Auxiliary Variable; Simplex Method; Nonbasic Variable (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_1 Ordering information: This item can be ordered from DOI: 10.1007/978-94-015-9759-3_1 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.