Simplex algorithm: Difference between revisions
No edit summary |
No edit summary |
||
| 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 | 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>. | ||
== Algorithmic Discussion == | == Algorithmic Discussion == | ||
There are two | There are two theorems in LP: | ||
# 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 | ||
| Line 41: | Line 41: | ||
\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 | 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. | ||
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: | ||
| Line 51: | Line 51: | ||
<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\}</math> | ||
Where | 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: | ||
<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 | 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</math> | ||
| Line 98: | Line 98: | ||
\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}{ | 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: | ||
<math> | <math> | ||
| Line 124: | Line 124: | ||
\end{array} </math> | \end{array} </math> | ||
Because there is one negative value in last row, the same processes should be performed again. The smallest value in the last row is in the third column. And in the third column, the second row has the smallest coefficients of <math> \frac{b_i}{ | Because there is one negative value in last row, the same processes should be performed again. The smallest value in the last row is in the third column. And in the third column, the second row has the smallest coefficients of <math> \frac{b_i}{x_3}</math> which is 1.2. Thus, the second row will be selected for pivoting. The simplex tableau is the following: | ||
<math> | <math> | ||
| Line 143: | Line 143: | ||
x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z & b \\ | x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z & b \\ | ||
\hline | \hline | ||
1 & 0.2 & 0 & 0.6 & -0.2 & 0 & 0 & 0.4 \\ | |||
0 & 0.6 & 1 & -0.2 & 0.4 & 0 & 0 & 1.2 \\ | 0 & 0.6 & 1 & -0.2 & 0.4 & 0 & 0 & 1.2 \\ | ||
0 & -0.1 & 0 & 0.2 & 0.6 & -1 & 0 & -4.2 \\ | 0 & -0.1 & 0 & 0.2 & 0.6 & -1 & 0 & -4.2 \\ | ||
| Line 150: | Line 150: | ||
\end{array} </math> | \end{array} </math> | ||
From the tableau above, <math>x_1</math>, <math> x_3</math> and <math>z</math> are basic variables since | There is no need to further conduct calculation since all values in the last row are non-negative. From the tableau above, <math>x_1</math>, <math> x_3</math> and <math>z</math> are basic variables since all rows in their columns are 0's except one row is 1.Therefore, the optimal solution will be <math>x_1 = 0.4</math>, <math>x_2 = 0</math>, <math>x_3 = 1.2</math>, achieving the maximum value: <math>z = 6.4</math> | ||
== Application == | |||
Simplex method can be used in many of programming problems since those will be converted to LP (Linear Programming) and solved by simplex method. Beside of mathematical way of using this method, many other industrial planning will use this method to maximize the profits or minimize the resources needed, especially in the field of agriculture, economics and chemical engineering | |||
=== Agriculture === | |||
=== Economics === | |||
=== Chemical Engineering === | |||
Revision as of 20:12, 18 November 2020
Author: Guoqing Hu (SysEn 6800 Fall 2020)
Steward: Allen Yang, Fengqi You
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[1]. Simplex algorithm has been proposed by George Dantzig, initiated from the idea of step by step downgrade to one of the vortices on the convex polyhedral[2]. "Simplex" could be possibly referred as the top vertex on the simplicial cone which is the geometric illustration of the constraints within LP problems[3].
Algorithmic Discussion
There are two theorems in LP:
- 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.[4]
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.
Consider the following expression as the general linear programming problem standard form:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \max \sum_{i=1}^n c_ix_i}
With the following constraints:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} s.t. \quad \sum_{j=1}^n a_{ij}x_j &\leq b_i \quad i = 1,2,...,m \\ x_j &\geq 0 \quad j = 1,2,...,n \end{align} }
The first step of the simplex method is to add slack variables and symbols which represent the objective functions:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \phi &= \sum_{i=1}^n c_nx_n\\ z_i &= b_i - \sum_{j=1}^n a_{ij}x_j \quad i = 1,2,...,m \end{align} }
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:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \phi &= \sum_{j=1}^n c_nx_n\\ x_{n+i} &= b_i - \sum_{j=1}^n a_{ij}x_{ij} \quad i=1,2,...,m \end{align} }
With the progression of simplex method, the starting dictionary (which is the equations above) switches between the dictionaries in seeking for optimal values. Every dictionary will have m basic variables which form the feasible area, as well as n non-basic variables which compose the objective function. Afterward, the dictionary function will be written in the form of:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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 \end{align} }
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} , 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.
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:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i = \bar{b_i} - \bar{a_{ik}}x_k \quad i \, \epsilon \, \{ 1,2,...,n \}}
Since the non-negativity of entering variables should be ensured, the following inequality can be derived:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bar{b_i} - \bar{a_i}x_k \geq 0 \quad i\,\epsilon\, \{1,2,...,n\}}
Where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_k} is immutable. The minimum Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i} should be zero to get the minimum value since this cannot be negative. Therefore, the following equation should be derived:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_k = \frac {\bar{b_i}}{\bar{a_{ik}}} }
Due the nonnegativity of all variables, the value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_k} should be raised to the largest of all of those values calculated from above equation. Hence, the following equation can be derived:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_k = \min_{\bar{a_{ik}}>0} \, \frac{\bar{b_i}}{\bar{a_{ik}}} \quad i=1,2,...,n}
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.[4]
Numerical Example
Considering the following numerical example to gain better understanding:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \max{4x_1+x_2+4x_3}}
with the following constraints:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 2x_1 + x_2 + x_3 &\leq 2 \\ x_1 + 2x_2 +3x_3 &\leq 4\\ 2x_1 + 2x_2 + x_3 &\leq 8 \\ x_1,x_2,x_3 &\geq 0 \end{align}}
With adding slack variables to get the following equations:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} z - 4x_1 - x_2 -4x_3 &= 0 \\ 2x_1 + x_2 + x_3 + s_1 &= 2 \\ x_1 + 2x_2 + 3x_3 + s_2 &= 4\\ 2x_1 + 2x_2 + x_3 + s_3 &= 8 \\ x_1,x_2,x_3,s_1,s_2,s_3 &\geq 0 \end{align} }
The simplex tableau can be derived as following:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{c c c c c c c | r} x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z & b \\ \hline 2 & 1 & 1 & 1 & 0 & 0 & 0 & 2 \\ 1 & 2 & 3 & 0 & 1 & 0 & 0 & 4 \\ 2 & 2 & 1 & 0 & 0 & 1 & 0 & 8 \\ \hline -4 & -1 & -4 & 0 & 0 & 0 & 1 & 0 \end{array} }
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 . 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:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{c c c c c c c | r} x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z & b \\ \hline 1 & 0.5 & 0.5 & 0.5 & 0 & 0 & 0 & 1 \\ 1 & 2 & 3 & 0 & 1 & 0 & 0 & 4 \\ 2 & 2 & 1 & 0 & 0 & 1 & 0 & 8 \\ \hline -4 & -1 & -4 & 0 & 0 & 0 & 1 & 0 \end{array} }
By performing the row operation still every other rows (other than first row) in column 1 are zeroes:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{c c c c c c c | r} x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z & b \\ \hline 1 & 0.5 & 0.5 & 0.5 & 0 & 0 & 0 & 1 \\ 0 & 1.5 & 2.5 & -0.5 & 1 & 0 & 0 & 3 \\ 0 & 1 & 0 & -1 & 0 & 1 & 0 & 6 \\ \hline 0 & 1 & -2 & 2 & 0 & 0 & 1 & 4 \end{array} }
Because there is one negative value in last row, the same processes should be performed again. The smallest value in the last row is in the third column. And in the third column, the second row has the smallest coefficients of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{b_i}{x_3}} which is 1.2. Thus, the second row will be selected for pivoting. The simplex tableau is the following:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{c c c c c c c | r} x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z & b \\ \hline 1 & 0.5 & 0.5 & 0.5 & 0 & 0 & 0 & 1 \\ 0 & 0.6 & 1 & -0.2 & 0.4 & 0 & 0 & 1.2 \\ 0 & 1 & 0 & -1 & 0 & 1 & 0 & 6 \\ \hline 0 & 1 & -2 & 2 & 0 & 0 & 1 & 4 \end{array} }
By performing the row operation to make other columns 0's, the following could be derived
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{c c c c c c c | r} x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & z & b \\ \hline 1 & 0.2 & 0 & 0.6 & -0.2 & 0 & 0 & 0.4 \\ 0 & 0.6 & 1 & -0.2 & 0.4 & 0 & 0 & 1.2 \\ 0 & -0.1 & 0 & 0.2 & 0.6 & -1 & 0 & -4.2 \\ \hline 0 & 2.2 & 0 & 1.6 & 0.8 & 0 & 1 & 6.4 \end{array} }
There is no need to further conduct calculation since all values in the last row are non-negative. From the tableau above, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_3} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z} are basic variables since all rows in their columns are 0's except one row is 1.Therefore, the optimal solution will be Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1 = 0.4} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_2 = 0} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_3 = 1.2} , achieving the maximum value: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z = 6.4}
Application
Simplex method can be used in many of programming problems since those will be converted to LP (Linear Programming) and solved by simplex method. Beside of mathematical way of using this method, many other industrial planning will use this method to maximize the profits or minimize the resources needed, especially in the field of agriculture, economics and chemical engineering