Simplex algorithm - Revision history

Apoorv12345 at 12:26, 5 October 2021

2021-10-05T12:26:44Z

← Older revision		Revision as of 08:26, 5 October 2021
Line 1:		Line 1:
	Author: Guoqing Hu (SysEn 6800 Fall 2020~~),Apoorv Lal (CHEME6800, Fall 2021~~)		Author: Guoqing Hu (SysEn 6800 Fall 2020)

	== Introduction ==		== Introduction ==

Apoorv12345 at 03:21, 2 October 2021

2021-10-02T03:21:34Z

← Older revision		Revision as of 23:21, 1 October 2021
Line 1:		Line 1:
	Author: Guoqing Hu (SysEn 6800 Fall 2020)		Author: Guoqing Hu (SysEn 6800 Fall 2020),Apoorv Lal (CHEME6800, Fall 2021)

	== Introduction ==		== Introduction ==

Wc593 at 11:28, 21 December 2020

2020-12-21T11:28:03Z

← Older revision		Revision as of 07:28, 21 December 2020
Line 1:		Line 1:
	Author: Guoqing Hu (SysEn 6800 Fall 2020)		Author: Guoqing Hu (SysEn 6800 Fall 2020)

	~~Steward: Allen Yang, Fengqi You~~

	== Introduction ==		== Introduction ==

502356864 at 00:44, 1 December 2020

2020-12-01T00:44:38Z

← Older revision		Revision as of 20:44, 30 November 2020
Line 55:		Line 55:
	<math> x_k = \frac {\bar{b_i}}{\bar{a_{ik}}} </math>		<math> x_k = \frac {\bar{b_i}}{\bar{a_{ik}}} </math>

	Due the nonnegativity of all variables, the value of <math>x_k</math> should be raised to the largest of all of those values calculated from above equation. Hence, the following equation can be derived:		Due to the nonnegativity of all variables, the value of <math>x_k</math> should be raised to the largest of all of those values calculated from above equation. Hence, the following equation can be derived:

	<math> x_k = \min_{\bar{a_{ik}}>0} \, \frac{\bar{b_i}}{\bar{a_{ik}}} \quad i=1,2,...,n+m</math>		<math> x_k = \min_{\bar{a_{ik}}>0} \, \frac{\bar{b_i}}{\bar{a_{ik}}} \quad i=1,2,...,n+m</math>
Line 102:		Line 102:
	\end{array} </math>		\end{array} </math>

	In the last row, the column with the smallest value should be selected. Although there are two smallest values, the result will be the same no matter of which one is selected first. For this solution, the first column is selected. After the least coefficient is found, the pivot process will be conducted by searching for the coefficient <math> \frac{b_i}{x_1} </math>. Since the ~~value for~~ the first row is 1 and second row ~~is 4. Thus~~, the first row should be pivoted. And following tableau can be created:		In the last row, the column with the smallest value should be selected. Although there are two smallest values, the result will be the same no matter of which one is selected first. For this solution, the first column is selected. After the least coefficient is found, the pivot process will be conducted by searching for the coefficient <math> \frac{b_i}{x_1} </math>. Since the coefficient in the first row is 1 and 4 for the second row, the first row should be pivoted. And following tableau can be created:

	<math>		<math>

502356864 at 00:41, 1 December 2020

2020-12-01T00:41:40Z

Show changes

502356864 at 00:06, 1 December 2020

2020-12-01T00:06:58Z

← Older revision		Revision as of 20:06, 30 November 2020
Line 37:		Line 37:

	<math> \begin{align}		<math> \begin{align}
	\phi &= \bar{\phi} + \sum_{j=1}^n \bar{~~c_n~~}~~x_n~~\\		\phi &= \bar{\phi} + \sum_{j=1}^n \bar{c_j}x_j\\
	x_{i} &= \bar{b_i} - \sum_{j=1}^n \bar{a_{ij}}x_{ij} \quad i=1,2,...,n+m		x_{i} &= \bar{b_i} - \sum_{j=1}^n \bar{a_{ij}}x_{ij} \quad i=1,2,...,n+m
	\end{align} </math>		\end{align} </math>

	Where the variables with bar suggest that those corresponding values will change accordingly with the progression of simplex method. The observation could be made that there will specifically one variable goes from non-basic to basic and one acts oppositely. As this kind of variable is referred as ''entering variable''. Under the goal of increasing <math>\phi</math>, the entering variables are selected from the set {1,2,...,n}. As long as there are no repetitive entering variables can be selected, the optimal values will be found. The decision of which entering variable should be selected at first place should be made based on the consideration that there usually are multiple constraints (n>1). For Simplex algorithm, the coefficient with least value is preferred since the major objective is maximization.		Where the variables with bar suggest that those corresponding values will change accordingly with the progression of simplex method. The observation could be made that there will specifically one variable goes from non-basic to basic and one acts oppositely. As this kind of variable is referred as ''entering variable''. Under the goal of increasing <math>\phi</math>, the entering variables are selected from the set {1,2,...,n}. As long as there are no repetitive entering variables can be selected, the optimal values will be found. The decision of which entering variable should be selected at first place should be made based on the consideration that there usually are multiple constraints (n>1). For Simplex algorithm, the coefficient with least value is preferred since the major objective is maximization.
Line 60:		Line 60:

	Once the leaving-basic and entering-nonbasic variables are chosen, reasonable row operation should be conducted to switch from current dictionary to the new dictionary, as this step is referred as ''pivot.''<ref name=":1" />		Once the leaving-basic and entering-nonbasic variables are chosen, reasonable row operation should be conducted to switch from current dictionary to the new dictionary, as this step is referred as ''pivot.''<ref name=":1" />

			As in the pivot process, the coefficient for the selected pivot element should be one, meaning the reciprocal of this coefficient should be multiplied to every element within this row. Afterward, multiplying this specific row with corresponding coefficients and adding this to different rows, one should get 0 values for all other entries in this pivot element's column.

			If there are any negative variables after the pivot process, one should continue finding the pivot element by repeating the process above. At once there are no more negative values for basic and non-basic variables. The optimal solution is found.<ref>Evar D. Nering and Albert W. Tucker, 1993, ''Linear Programs and Related Problems'', Academic Press. (elementary)</ref><ref>Robert J. Vanderbei, ''Linear Programming: Foundations and Extensions'', 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. <nowiki>ISBN 978-0-387-74387-5</nowiki>.</ref>

	== Numerical Example ==		== Numerical Example ==

502356864 at 22:29, 30 November 2020

2020-11-30T22:29:44Z

502356864: /* Algorithmic Discussion */

2020-11-30T22:15:02Z

Algorithmic Discussion

← Older revision		Revision as of 18:15, 30 November 2020
Line 12:		Line 12:
	# For any LP, there is only one extreme point of the LP's feasible region regarding to every basic feasible solution. Plus, there will be at minimum of one basic feasible solution corresponding to every extreme point in the feasible region.<ref name=":1">Vanderbei, R. J. (2000). ''Linear programming: Foundations and extensions''. Boston: Kluwer.</ref>		# For any LP, there is only one extreme point of the LP's feasible region regarding to every basic feasible solution. Plus, there will be at minimum of one basic feasible solution corresponding to every extreme point in the feasible region.<ref name=":1">Vanderbei, R. J. (2000). ''Linear programming: Foundations and extensions''. Boston: Kluwer.</ref>
	[[File:Geometric Illustration of LP problem.png\|thumb\|Geometric Illustration of LP problem]]		[[File:Geometric Illustration of LP problem.png\|thumb\|Geometric Illustration of LP problem]]
	Based on two theorems above, the geometric illustration of the LP problem could be depicted. Each line of this polyhedral will be the boundary of the LP constraints, in which every vertex will be the extreme points according to the theorem. Simplex method is the way to ~~reasonably sort out~~ the ~~shortest path~~ to the ~~optimal solutions~~.		Based on two theorems above, the geometric illustration of the LP problem could be depicted. Each line of this polyhedral will be the boundary of the LP constraints, in which every vertex will be the extreme points according to the theorem. Simplex method is the way to adjust the nonbasic variables to travel to different vertex till the optimum solution is found.<ref>Sakarovitch M. (1983) Geometric Interpretation of the Simplex Method. In: Thomas J.B. (eds) Linear Programming. Springer Texts in Electrical Engineering. Springer, New York, NY. <nowiki>https://doi.org/10.1007/978-1-4757-4106-3_8</nowiki></ref>

	Consider the following expression as the general linear programming problem standard form:		Consider the following expression as the general linear programming problem standard form:

502356864 at 21:05, 30 November 2020

2020-11-30T21:05:56Z

← Older revision		Revision as of 17:05, 30 November 2020
Line 4:		Line 4:

	== Introduction ==		== Introduction ==
	Simplex algorithm (or Simplex method) is a widely-used algorithm to solve the Linear Programming(LP) optimization problems. Simplex algorithm can be thought as one of the elementary steps for solving the inequality problem, since many of those will be converted to LP and solved via Simplex algorithm.<~~sup~~>[1]</~~sup~~> Simplex algorithm has been proposed by [[wikipedia:George_Dantzig\|George Dantzig]], initiated from the idea of step by step downgrade to one of the vertices on the convex polyhedral.<~~sup~~>[2]</~~sup~~> "Simplex" could be possibly referred as the top vertex on the simplicial cone which is the geometric illustration of the constraints within LP problems.<~~sup~~>~~[3]~~</~~sup~~>		Simplex algorithm (or Simplex method) is a widely-used algorithm to solve the Linear Programming(LP) optimization problems. Simplex algorithm can be thought as one of the elementary steps for solving the inequality problem, since many of those will be converted to LP and solved via Simplex algorithm.<ref name=":0">[http://www-personal.umich.edu/~murty/books/linear_complementarity_webbook/lcp-complete.pdf Linear complementarity, linear and nonlinear programming Internet Edition].</ref> Simplex algorithm has been proposed by [[wikipedia:George_Dantzig\|George Dantzig]], initiated from the idea of step by step downgrade to one of the vertices on the convex polyhedral.<ref>Dantzig, G. B. (1987, May). [https://apps.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf Origins of the simplex method].</ref> "Simplex" could be possibly referred as the top vertex on the simplicial cone which is the geometric illustration of the constraints within LP problems.<ref>Strang, G. (1987). Karmarkar’s algorithm and its place in applied mathematics. ''The Mathematical Intelligencer,'' ''9''(2), 4-10. doi:10.1007/bf03025891.</ref>

	== Algorithmic Discussion ==		== Algorithmic Discussion ==
Line 10:		Line 10:

	# The feasible region for any LP problem is a convex set (Every linear equation's second derivative is 0, implying the monotonicity of the trend). Therefore, if an LP has an optimal solution, there must be an extreme point of the feasible region that is optimal		# The feasible region for any LP problem is a convex set (Every linear equation's second derivative is 0, implying the monotonicity of the trend). Therefore, if an LP has an optimal solution, there must be an extreme point of the feasible region that is optimal
	# For any LP, there is only one extreme point of the LP's feasible region regarding to every basic feasible solution. Plus, there will be at minimum of one basic feasible solution corresponding to every extreme point in the feasible region.<~~sup~~>~~[4]~~</~~sup~~>		# For any LP, there is only one extreme point of the LP's feasible region regarding to every basic feasible solution. Plus, there will be at minimum of one basic feasible solution corresponding to every extreme point in the feasible region.<ref name=":1">Vanderbei, R. J. (2000). ''Linear programming: Foundations and extensions''. Boston: Kluwer.</ref>
	[[File:Geometric Illustration of LP problem.png\|thumb\|Geometric Illustration of LP problem]]		[[File:Geometric Illustration of LP problem.png\|thumb\|Geometric Illustration of LP problem]]
	Based on two theorems above, the geometric illustration of the LP problem could be depicted. Each line of this polyhedral will be the boundary of the LP constraints, in which every vertex will be the extreme points according to the theorem. Simplex method is the way to reasonably sort out the shortest path to the optimal solutions.		Based on two theorems above, the geometric illustration of the LP problem could be depicted. Each line of this polyhedral will be the boundary of the LP constraints, in which every vertex will be the extreme points according to the theorem. Simplex method is the way to reasonably sort out the shortest path to the optimal solutions.
Line 59:		Line 59:
	<math> x_k = \min_{\bar{a_{ik}}>0} \, \frac{\bar{b_i}}{\bar{a_{ik}}} \quad i=1,2,...,n</math>		<math> x_k = \min_{\bar{a_{ik}}>0} \, \frac{\bar{b_i}}{\bar{a_{ik}}} \quad i=1,2,...,n</math>

	Once the leaving-basic and entering-nonbasic variables are chosen, reasonable row operation should be conducted to switch from current dictionary to the new dictionary, as this step is referred as ''pivot.''<~~sup>[4]<~~/~~sup~~>		Once the leaving-basic and entering-nonbasic variables are chosen, reasonable row operation should be conducted to switch from current dictionary to the new dictionary, as this step is referred as ''pivot.''<ref name=":1" />

	== Numerical Example ==		== Numerical Example ==
Line 156:		Line 156:

	=== Mathematical Problem ===		=== Mathematical Problem ===
	Simplex method is commonly used in many programming problem. Due to the heavy load of computation on non-linear problem, many of non-linear problem (NLP) cannot be solved effectively. Consequently, many NLP will rely on the LP solver, namely simplex method, to do some of the work in finding the solution (for instance, the upper or lower bound of the feasible solution), or in many cases, those NLP will be wholly linearized to LP and solved from simplex method.<~~sup>[1]<~~/~~sup~~> Other than solving the problems, simplex method can also be used reliably to support the LP's solution from other theorem, for instance the [[wikipedia:Farkas'_lemma#:~:text=Farkas'%20lemma%20is%20a%20solvability,the%20Hungarian%20mathematician%20Gyula%20Farkas.&text=Farkas'%20lemma%20belongs%20to%20a,two%20systems%20has%20a%20solution.\|Farkas' theorem]] in which Simplex method proves the suggested feasible solutions.<sup>[1]</sup> Beside of solving the problems, Simplex method can also enlighten the scholars with the ways of solving other problems, for instance, Quadratic Programming (QP).<~~sup~~>~~[5]~~</~~sup~~> For some of QP problems, they have linear constraints to the variables which can be solved analogous to the idea of Simplex method.		Simplex method is commonly used in many programming problem. Due to the heavy load of computation on non-linear problem, many of non-linear problem (NLP) cannot be solved effectively. Consequently, many NLP will rely on the LP solver, namely simplex method, to do some of the work in finding the solution (for instance, the upper or lower bound of the feasible solution), or in many cases, those NLP will be wholly linearized to LP and solved from simplex method.<ref name=":0" /> Other than solving the problems, simplex method can also be used reliably to support the LP's solution from other theorem, for instance the [[wikipedia:Farkas'_lemma#:~:text=Farkas'%20lemma%20is%20a%20solvability,the%20Hungarian%20mathematician%20Gyula%20Farkas.&text=Farkas'%20lemma%20belongs%20to%20a,two%20systems%20has%20a%20solution.\|Farkas' theorem]] in which Simplex method proves the suggested feasible solutions.<sup>[1]</sup> Beside of solving the problems, Simplex method can also enlighten the scholars with the ways of solving other problems, for instance, Quadratic Programming (QP).<ref>Wolfe, P. (1959). The simplex method for quadratic programming. ''Econometrica,'' ''27''(3), 382. doi:10.2307/1909468</ref> For some of QP problems, they have linear constraints to the variables which can be solved analogous to the idea of Simplex method.
	=== Industrial Application ===		=== Industrial Application ===
	The industries from different field will use simplex method to plan under the constraints. With considering that it is usually the case that the constraints or tradeoffs and desired outcomes are linearly related to the controllable variables, many people will develop the models to solve the LP problem via simplex method, for instance, the agricultural and economic problems		The industries from different field will use simplex method to plan under the constraints. With considering that it is usually the case that the constraints or tradeoffs and desired outcomes are linearly related to the controllable variables, many people will develop the models to solve the LP problem via simplex method, for instance, the agricultural and economic problems

	Farmers usually need to rationally allocate the existed resources to obtain the maximum profits. The potential constraints are raised from multiple perspectives including: policy restriction, budget concerns as well as farmland area. Farmers may incline to use the simplex-method-based model to have the better plan, as those constraints may be constant in many scenarios and the profits are usually linearly related to the farm production, thereby forming the LP problem. Currently, there is existing plant-model which can accept inputs such as price, farm production and return the optimal plan to maximize the profits with given information<~~sup~~>[6]</~~sup~~>.		Farmers usually need to rationally allocate the existed resources to obtain the maximum profits. The potential constraints are raised from multiple perspectives including: policy restriction, budget concerns as well as farmland area. Farmers may incline to use the simplex-method-based model to have the better plan, as those constraints may be constant in many scenarios and the profits are usually linearly related to the farm production, thereby forming the LP problem. Currently, there is existing plant-model which can accept inputs such as price, farm production and return the optimal plan to maximize the profits with given information.<ref>Hua, W. (1998). [https://shareok.org/bitstream/handle/11244/12005/Thesis-1998-H8735a.pdf?sequence=1 Application of the revised simplex method to the farm planning model].</ref>

	Beside of the agricultural purposes, simplex method can also be used by enterprises to make the profits. The rational sale-strategy will be indispensable to the successful practice of marketing. Since there are so many enterprises from international wide, the marketing strategy from enamelware are selected for illustration. After widely collecting the data of the quality of varied products manufactured, cost of each and popularity among the customers, the company may need to determine which kind of products will worth the investment and continue making profits as well as which won't. Considering the cost and profit factors are linearly dependent on the production, economists will suggest a LP model which can be solved via simplex method.<~~sup~~>~~[7]~~</~~sup~~>		Beside of the agricultural purposes, simplex method can also be used by enterprises to make the profits. The rational sale-strategy will be indispensable to the successful practice of marketing. Since there are so many enterprises from international wide, the marketing strategy from enamelware are selected for illustration. After widely collecting the data of the quality of varied products manufactured, cost of each and popularity among the customers, the company may need to determine which kind of products will worth the investment and continue making profits as well as which won't. Considering the cost and profit factors are linearly dependent on the production, economists will suggest a LP model which can be solved via simplex method.<ref>Nikitenko, A. V. (1996). Economic analysis of the potential use of a simplex method in designing the sales strategy of an enamelware enterprise. ''Glass and Ceramics,'' ''53''(12), 367-369. doi:10.1007/bf01129674.</ref>

	The above professional fields are only the tips of the iceberg to the simplex method application. Many other fields will use this method since LP problem is gaining the popularity in recent days and simplex method plays crucial roles in solving those problems.		The above professional fields are only the tips of the iceberg to the simplex method application. Many other fields will use this method since LP problem is gaining the popularity in recent days and simplex method plays crucial roles in solving those problems.

	== Conclusion ==		== Conclusion ==
	It is indisputable to acknowledge the influence of Simplex method to the programming, as this method won the 'National Medal of Science' to its inventor, George Dantzig<~~sup~~>~~[8]~~</~~sup~~>. Not only for its wide usage in the mathematic models and industrial manufacture, Simplex method also provides new perspective in solving the inequality problems. As its contribution to the programming substantially boosts the advancement of the current technology and economy from making the optimal plan with the constraints. Nowadays, with the development of technology and economics, simplex method is substituted with some more advanced solvers which can solve the problems with faster speed and handle larger amount of constraints and variables, but this innovative method marks the creativity at that age and continuously offer the inspiration to the upcoming challenges.		It is indisputable to acknowledge the influence of Simplex method to the programming, as this method won the 'National Medal of Science' to its inventor, George Dantzig.<ref>Cottle, R., Johnson, E. and Wets, R. (2007). George B. Dantzig (1914–2005). ''Notices Amer. Math. Soc.'' 54, 344–362.</ref> Not only for its wide usage in the mathematic models and industrial manufacture, Simplex method also provides new perspective in solving the inequality problems. As its contribution to the programming substantially boosts the advancement of the current technology and economy from making the optimal plan with the constraints. Nowadays, with the development of technology and economics, simplex method is substituted with some more advanced solvers which can solve the problems with faster speed and handle larger amount of constraints and variables, but this innovative method marks the creativity at that age and continuously offer the inspiration to the upcoming challenges.

	== References ==		== References ==
			<references />
	~~# Murty, K. G. (1997). [http:~~/~~/www-personal.umich.edu/~murty/books/linear_complementarity_webbook/lcp-complete.pdf LINEAR COMPLEMENTARITY LINEAR AND NONLINEAR PROGRAMMING Internet Edition].~~
	~~# Dantzig, G. B. (1987, May). [https://apps.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf ORIGINS OF THE SIMPLEX METHOD].~~
	~~# Strang, G. (1987). Karmarkar’s algorithm and its place in applied mathematics. ''The Mathematical Intelligencer,'' ''9''(2), 4-10. doi:10.1007/bf03025891~~
	~~# Vanderbei, R. J. (2000). ''Linear programming: Foundations and extensions''. Boston: Kluwer.~~
	~~# Wolfe, P. (1959). The Simplex Method for Quadratic Programming. ''Econometrica,'' ''27''(3), 382. doi:10.2307/1909468~~
	~~# Hua, W. (1998). [https://shareok.org/bitstream/handle/11244/12005/Thesis-1998-H8735a.pdf?sequence=1 APPLICATION OF THE REVISED SIMPLEX METHOD TO THE FARM PLANNING MODEL].~~
	# Nikitenko, A. V. (1996). Economic analysis of the potential use of a simplex method in designing the sales strategy of an enamelware enterprise. ''Glass and Ceramics,'' ''53''(12), 367-369. doi:10.1007/bf01129674
	~~# Cottle, R., Johnson, E. and Wets, R. (2007). George B. Dantzig (1914–2005). ''Notices Amer. Math. Soc.'' 54, 344–362.~~

502356864 at 20:48, 30 November 2020

2020-11-30T20:48:05Z

← Older revision		Revision as of 16:48, 30 November 2020
Line 4:		Line 4:

	== Introduction ==		== Introduction ==
	Simplex algorithm (or Simplex method) is a widely-used algorithm to solve the Linear Programming(LP). Simplex algorithm can be thought as one of the elementary steps for solving the inequality problem, since many of those will be converted to LP and solved via Simplex algorithm.<sup>[1]</sup> Simplex algorithm has been proposed by [[wikipedia:George_Dantzig\|George Dantzig]], initiated from the idea of step by step downgrade to one of the ~~vortices~~ on the convex polyhedral.<sup>[2]</sup> "Simplex" could be possibly referred as the top vertex on the simplicial cone which is the geometric illustration of the constraints within LP problems<sup>[3]</sup>.		Simplex algorithm (or Simplex method) is a widely-used algorithm to solve the Linear Programming(LP) optimization problems. Simplex algorithm can be thought as one of the elementary steps for solving the inequality problem, since many of those will be converted to LP and solved via Simplex algorithm.<sup>[1]</sup> Simplex algorithm has been proposed by [[wikipedia:George_Dantzig\|George Dantzig]], initiated from the idea of step by step downgrade to one of the vertices on the convex polyhedral.<sup>[2]</sup> "Simplex" could be possibly referred as the top vertex on the simplicial cone which is the geometric illustration of the constraints within LP problems.<sup>[3]</sup>

	== Algorithmic Discussion ==		== Algorithmic Discussion ==

← Older revision		Revision as of 18:29, 30 November 2020
Line 26:		Line 26:
	The first step of the simplex method is to add slack variables and symbols which represent the objective functions:		The first step of the simplex method is to add slack variables and symbols which represent the objective functions:

	<math> \begin{align} \phi &= \sum_{i=1}^n ~~c_nx_n~~\\		<math> \begin{align} \phi &= \sum_{i=1}^n c_ix_i\\
	z_i &= b_i - \sum_{j=1}^n a_{ij}x_j \quad i = 1,2,...,m \end{align} </math>		z_i &= b_i - \sum_{j=1}^n a_{ij}x_j \quad i = 1,2,...,m \end{align} </math>

	The new introduced slack variables may be confused with the original values. Therefore, it will be convenient to add those slack variables to the end of the list of ''x''-variables with the following expression:		The new introduced slack variables may be confused with the original values. Therefore, it will be convenient to add those slack variables <math> z_i </math> to the end of the list of ''x''-variables with the following expression:

	<math> \begin{align} \phi &= \sum_{j=1}^n ~~c_nx_n~~\\		<math> \begin{align} \phi &= \sum_{i=1}^n c_ix_i\\
	x_{n+i} &= b_i - \sum_{j=1}^n a_{ij}x_{ij} \quad i=1,2,...,m \end{align} </math>		x_{n+i} &= b_i - \sum_{j=1}^n a_{ij}x_{ij} \quad i=1,2,...,m \end{align} </math>

Line 37:		Line 37:

	<math> \begin{align}		<math> \begin{align}
	\phi &= \bar{\phi} + \sum_{j=1}^n \bar{c_n}x_n\\		\phi &= \bar{\phi} + \sum_{j=1}^n \bar{c_n}x_n\\
	x_{n+i} &= \bar{b_i} - \sum_{j=1}^n \bar{a_{ij}}x_{ij} \quad i=n+1,n+2,...,n+m		x_{i} &= \bar{b_i} - \sum_{j=1}^n \bar{a_{ij}}x_{ij} \quad i=1,2,...,n+m
	\end{align} </math>		\end{align} </math>

	Where the variables with bar suggest that those corresponding values will change accordingly with the progression of simplex method. The observation could be made that there will specifically one variable goes from non-basic to basic and one acts oppositely. As this kind of variable is referred as ''entering variable''. Under the goal of increasing <math>\phi</math>, the entering variables are selected from the set {1,2,...,n}. As long as there are no repetitive entering variables can be selected, the optimal values will be found. The decision of which entering variable should be selected at first place should be made based on the consideration that there usually are multiple constraints (n>1). For Simplex algorithm, the coefficient with least value is preferred since the major objective is maximization.		Where the variables with bar suggest that those corresponding values will change accordingly with the progression of simplex method. The observation could be made that there will specifically one variable goes from non-basic to basic and one acts oppositely. As this kind of variable is referred as ''entering variable''. Under the goal of increasing <math>\phi</math>, the entering variables are selected from the set {1,2,...,n}. As long as there are no repetitive entering variables can be selected, the optimal values will be found. The decision of which entering variable should be selected at first place should be made based on the consideration that there usually are multiple constraints (n>1). For Simplex algorithm, the coefficient with least value is preferred since the major objective is maximization.
Line 45:		Line 45:
	The ''leaving variables'' are defined as which go from basic to non-basic. The reason of their existence is to ensure the non-negativity of those basic variables. Once the entering variables are determined, the corresponding leaving variables will change accordingly from the equation below:		The ''leaving variables'' are defined as which go from basic to non-basic. The reason of their existence is to ensure the non-negativity of those basic variables. Once the entering variables are determined, the corresponding leaving variables will change accordingly from the equation below:

	<math> x_i = \bar{b_i} - \bar{a_{ik}}x_k \quad i \, \epsilon \, \{ 1,2,...,n \}</math>		<math> x_i = \bar{b_i} - \bar{a_{ik}}x_k \quad i \, \epsilon \, \{ 1,2,...,n+m \}</math>

	Since the non-negativity of entering variables should be ensured, the following inequality can be derived:		Since the non-negativity of entering variables should be ensured, the following inequality can be derived:

	<math> \bar{b_i} - \bar{a_i}x_k \geq 0 \quad i\,\epsilon\, \{1,2,...,n\}</math>		<math> \bar{b_i} - \bar{a_i}x_k \geq 0 \quad i\,\epsilon\, \{1,2,...,n+m \}</math>

	Where <math>x_k</math> is immutable. The minimum <math>x_i</math> should be zero to get the minimum value since this cannot be negative. Therefore, the following equation should be derived:		Where <math>x_k</math> is immutable. The minimum <math>x_i</math> should be zero to get the minimum value since this cannot be negative. Therefore, the following equation should be derived:
Line 57:		Line 57:
	Due the nonnegativity of all variables, the value of <math>x_k</math> should be raised to the largest of all of those values calculated from above equation. Hence, the following equation can be derived:		Due the nonnegativity of all variables, the value of <math>x_k</math> should be raised to the largest of all of those values calculated from above equation. Hence, the following equation can be derived:

	<math> x_k = \min_{\bar{a_{ik}}>0} \, \frac{\bar{b_i}}{\bar{a_{ik}}} \quad i=1,2,...,n</math>		<math> x_k = \min_{\bar{a_{ik}}>0} \, \frac{\bar{b_i}}{\bar{a_{ik}}} \quad i=1,2,...,n+m</math>

	Once the leaving-basic and entering-nonbasic variables are chosen, reasonable row operation should be conducted to switch from current dictionary to the new dictionary, as this step is referred as ''pivot.''<ref name=":1" />		Once the leaving-basic and entering-nonbasic variables are chosen, reasonable row operation should be conducted to switch from current dictionary to the new dictionary, as this step is referred as ''pivot.''<ref name=":1" />