Definition: Standard form of the Linear Programming problem is to debtermine a solution of a set of equations.
\[Ax=b\]
Where
\(x=\{x_1,x_2,\cdots,x_n\}^T\), \(A=\{a_{ij}\}, i=1,\cdots,m, j=1,\cdots,n\),\(b=\{b_1,\cdots,b_m\}^T\).
And
\(x_j\geq 0, j=1,\cdots,n\)
That minimizes the function
\[z=cx\]
Slack variables:
Assume we have the condition:
\[x_i\leq b_i\]
Which is equivalent to:
\[\begin{cases}x_i+\tilde{x}_i=b_i\\ \tilde{x}_i\geq 0\end{cases}\]
Similarly, the condition:
\[x_i\geq b_i\]
is equivalent to:
\[\begin{cases}x_i-\tilde{x}_i=b_i\\ \tilde{x}_i\geq 0\end{cases}\]
There is another condition is different from the previous two: \(x_i\) is unrestrict, which is equivalent to:
\[\begin{cases}x_i=x_i'-x_i''\\ x_i',x_i''\geq 0\end{cases}\]
The variables added are called slack variables.
Standard form(minimization):
\[ \begin{gathered} \min z=cx\\ s.t. \quad Ax= b,\quad x_j\geq 0, j=1,\cdots,n \end{gathered} \]
Standard form(maximization):
\[ \begin{gathered} \max z=cx\\ s.t. \quad Ax= b,\quad x_j\geq 0, j=1,\cdots,n \end{gathered} \]
Canonical form(minimization):
\[ \begin{gathered} \min z=cx\\ s.t. \quad Ax\geq b,\quad x_j\geq 0, j=1,\cdots,n \end{gathered} \]
Canonical form(maximization):
\[ \begin{gathered} \max z=cx\\ s.t. \quad Ax\leq b,\quad x_j\geq 0, j=1,\cdots,n \end{gathered} \]
This item is reference by (Bazaraa, Jarvis, and Sherali 2011) - Linear Programming and Network Flows-Fourth Edition, page 7.
Canonical Form (Thie and Keough 2011) - Ref: An Introduction to Linear Programming and Game Theory, page 64-66
Definition: A system of \(m\) equations and \(n\) unknowns, with \(m \leq n\), is in canonical form with a distinguished set of \(m\) basic variables if each basic variable has coefficient \(1\) in one equation and \(0\) in the others, and each equation has exactly one basic variable with coefficient \(1\).
In the canonical form, one particular solution is:
\[ \begin{gathered} \text{non-basic variables} = 0\\ \text{basic variables} = R.H.S \end{gathered} \]
The solution obtained by the rules above is called Basic Solution. If this basic solution is non-negative, we call it a basic feasible solution.
(Remark: There are many basic solution and not all basic solution are feasible)
Definition: The standard linear programming problem is in canonical form with a distinguished set of basic variables if:
Degenerate: A basic solution with some basic variables equal to zero is said to be degenerate. \(\rightarrow\) Trouble maker.
We will consider the following part based on the Definition Item 5.
Step:
Summarize:
Assume that LP is in canonical form with \(m\) constraints and \(n\) variables. With the first \(m\) variables as basic variables. The problem is:
\(\min z\) where:
\[ \begin{array}{llllllllrll} x_1&+&\quad&\quad&\cdots&+&a_{1,m+1}x_{m+1}&+\cdots+&a_{1n}x_n&=&b_1\\ \quad&+&x_2&+&\cdots&+&a_{2,m+1}x_{m+1}&+\cdots+&a_{2n}x_n&=&b_2\\ \quad&\quad&\quad&\ddots&\quad&\quad&\quad&\quad&\quad&\quad&\ \\ \quad&\quad&\quad&\quad&x_m&+&a_{m,m+1}x_{m+1}&+\cdots+&a_{mn}x_n&=&b_m\\ \quad&\quad&\quad&\quad&\quad&\quad&c_{m+1}x_{m+1}&+\cdots+&c_{n}x_n&=&z_0+z \end{array} \] and \(x_1,\cdots,x_n\geq 0\)
\(a_{ij},b_i,c_i\) are constants, and since the associated basic solution is feasible, \(b_i\geq 0,i=1,\cdots,m\).
Theorem 1(Optimality criterion): For the linear programming problem of above, if \(c_j\geq 0,j=m+1,\cdots,n\), then the minimal value of the objective function is \(-z_0\) and is attained at the point \((b_1,\cdots,b_m,0,\cdots,0)\)
Proof: \(z=c_{m+1}x_{m+1}+\cdots+c_nx_n-z_0\), since any feasible solution to the constraints has nonnegative coordinates, the smallest possible value for the sum \(c_{m+1}x_{m+1}+\cdots+c_nx_n\) is zero. Thus the mininal possible value for \(z\) is \(-z_0\). and this value is assumed at the point \((b_1,\cdots,b_m,0,\cdots,0)\).
End proof.
The problem is resolved if all the \(c_j\) are nonnegative. Assume now that at least one \(c_j\), say \(c_s\), is negative. Then we attempt to enter the variable \(x_s\) into the basis. In order to determine what basic variable to replace, we consider the constraint set with all the nonbasic variables except \(x_s\) equal to zero. Then we have \(m\) conditions below(left one or right one):
\[ \begin{gathered} x_1+a_{1s}x_s=b_1\\ x_2+a_{2s}x_s=b_2\\ \vdots\\ x_m+a_{ms}x_s=b_m \end{gathered} \]
\[ \begin{gathered} x_1=b_1-a_{1s}x_s\geq 0\\ x_2=b_2-a_{2s}x_s\geq 0\\ \vdots\\ x_m=b_m-a_{ms}x_s\geq 0 \end{gathered} \]
Theorem 2(unboundary): For the linear programming problem above, if there is an index \(s\), \(m+1\leq s\leq n\), such that \(c_s<0\) and \(a_{i,s}\leq 0\) for all \(i=1,2,\cdots,m\), then the objective function is not bounded below.
Proof:
Case 1: If \(a_{is}<0\), from condition \(i\), we can get:
\[x_i=b_i-a_{is}x_s\geq 0\]
Since \(a_{is}\) is negative, then:
\[x_s\geq \frac{b_i}{a_{is}}\]
The R.H.S is negative, so the inequality is always ok. Replace \(x_i\) with \(x_s\). Then our object function is turn to:
\[z=c_{m+1}x_{m+1}+\cdots+c_sx_s+\cdots+c_nx_n-z_0\]
As \(x_s\rightarrow +\infty\), \(z\rightarrow -\infty\).
Case 2: If \(a_{is}=0\), then we have \(x_i=b_i\geq 0\), always ok.
Same as Case 1, as \(x_s\rightarrow +\infty\), \(z\rightarrow -\infty\).
End Proof
Assume \(c_s<0\) and that at least one \(a_{is}>0\).
Then the i-th equation \(x_i+a_{is}x_s=b_i\Leftrightarrow x_i=b_i-a_{is}x_s\geq 0\Rightarrow x_s\leq \frac{b_i}{a_{is}}\).
Our goal is to replace in the basis one of the basic variables \(x_1,\cdots,x_m\) with the variable \(x_s\).
Since \(c_sx_s\) is in the expression for the objective function, the value of \(z\) at this new basic feasible solution hopefully will be reduced.
In fact, for \(x_i\) to remain nonnegative, we must have \(b_i-a_{is}x_s\geq 0\). That is \(x_i\leq \frac{b_i}{a_{is}}\) for \(a_{is}>0\). We need to find the smallest ratio(s) say \(\frac{b_r}{a_{rs}}\)
\[\frac{b_r}{a_{rs}}=\min \{\frac{b_i}{a_{is}}:a_{is}>0\}\]
The largest possible value for \(x_s\) is \(\frac{b_r}{a_{rs}}\).
Letting \(x_s=\frac{b_r}{a_{rs}}\) will give \(x_i\geq 0\) for \(i=1,\cdots,m\) and \(x_r=b_r-a_{rs}\frac{b_r}{a_{rs}}=0\).
\(x_s\) should replace \(x_r\) in the basis. And keep our problem in canonical form by proviting operation at the \(a_{rs}x_s\).
Theorem 3(M: convergence of simplex for non-degenerate LP): In the problem above, assume that there is an index \(s\) such that \(c_s<0\) and that at least one \(a_{is}>0,i=1,\cdots,m\). Suppose:
\[\frac{b_r}{a_{rs}}=\min \{\frac{b_i}{a_{is}}:1\leq i\leq m\ \text{and}\ a_{is}>0\}\]
Then the problem can be put into canonical form with basic variables:
\[x_1,x_2,\cdots,x_{r-1},x_{r+1},\cdots,x_m,x_s\]
The value of the objective function at the associated basic feasible solution is:
\[-z_0+\frac{c_sb_r}{a_{rs}}\]
Obs:
\(c_s<0,b_r\geq 0,a_{rs}>0\) \[ \begin{cases} b_r >0& z \downarrow \ \text{strickly}\\ b_r=0& z\ \text{remains the same} \text{( degenerate)} \end{cases} \]
Proof:
Consider the problem above under the assumption of the theorem. The coefficient \(a_{rs}>0\). And the term \(a_{rs}x_s\) of the \(r\)-th equation can be used as the pivot term in the pivot operation applied to the \(m+1\) equations. (\(m\) conditions and \(1\) objective function).
By pivoting here, the system of constraints will be expressed in canonical form with bascis variables\(x_1,x_2,\cdots,x_{r-1},x_{r+1},\cdots,x_m,x_s\). The constant terms, \(b_i^*\) say i=\(1,\cdots,m\), on the right side of the equations, become:
\[ \begin{cases} b_i^*=b_i-a_{is}\frac{b_r}{a_{rs}} & i\neq r\\ b_i^*=\frac{b_r}{a_{rs}}& i =r \end{cases} \]
It’s clearly \(b_i^*\geq b_i\geq 0\), if \(a_{is}\leq 0\).
If \(a_{is}>0\) and \(i\neq r\), by the choice of \(r\), \(\frac{b_i}{a_{is}}\geq \frac{b_r}{a_{rs}}\) and so \(b_i\geq {a_{is}}\frac{b_r}{a_{rs}}\).
Hence \(b_i^*\geq 0\). Therefore the basic solution associated with these basic variables is feasible.
The original objective function have the form:\(c_{m+1}x_{m+1}+\cdots+c_nx_n=z_0+z\). This equation will be effect by the pivot operation. The \(x_s\) in this equation will be eliminate, producting the equation:
\[ c_r^*x_r+c_{m+1}^*x_{m+1}+\cdots+c_{s-1}^*x_{s-1}+c_{s+1}^*x_{s+1}+\cdots+c_n^*x_n=z_0^*+z \]
With \(z_0^*=z_0-c_s\frac{b_r}{a_{rs}}\).
Thus the objective function is expressed in terms of only the new nonbasic variables and the value of this funciton at the new basic feasible solution is \(-z_0^*=-z_0+c_s\frac{b_r}{a_{rs}}\).
End Proof.
For non-degenerate case, there are two cases:
For case 1, use the Theorem 2(unbounded) — stop. For case 2, use the Theorem 3(Convergence), \(z\) will strictly decrease each step.
\(\# \text{basic solutions}\leq \# \text{choices of basic variables}=C_m^n=\frac{n!}{m!(n-m)!}\)
To determine the row of the pivot term, find that row, say row \(r\), such that:
\[\frac{b_r}{a_{rs}}=\min \{\frac{b_i}{a_{is}}:a_{is}>0\}\]
If the minimum of these ratios is attained in several rows, a simple rule such as choosing the row with the smallest index can be used to determine the pivoting row.
If the problem contains degenerate basic feasible solutions, proceed as above. These steps should still be adequate to drive the problem to completion.
Consider the standard linear programming problem:
\[ \begin{gathered} \min z=cx\\ s.t. Ax=b\ \text{and}\ x_i \geq 0, i=1,\cdots,n\\ \end{gathered} \]
Assure all \(b_j,j=1,\cdots,m\) are nonnegative, if necessary, multiplication of an equation by \((-1)\).
Now introduce the system of constrains \(m\) new variables, \(x_{n+1},\cdots,x_{n+m}\), called aritificial variables, one to each variables. Then the shape of corresponding \(A\) is \([m,m+n]\), \(x\) is \([n+m,1]\).
\[\begin{array}{llll} a_{11} x_{1}+a_{12} x_{2}+\ldots+a_{1 n} x_{n}+x_{n+1}&\ &\ &=b_1\\ a_{21} x_{1}+a_{22} x_{2}+\ldots+a_{2 n} x_{n} & +x_{n+2}&\ &=b_2\\ \quad \vdots \qquad\quad \vdots \qquad\ldots\qquad\quad \vdots &\ &\ &\ \\ a_{m 1} x_{1}+a_{m 2} x_{2}+\ldots+a_{m n} x_{n} & &+x_{m+n}&=b_{m} \end{array}\]
This system is in canonical form with basic variables \(x_{n+1},\cdots,x_{n+m}\), and that the associated basic solution is feasible, since we have assumed that the \(b_i\) are nonnegative.
Now consider the problem of determining the minimal value of the function \(w=x_{n+1}+x_{n+2}+\cdots+x_{n+m}\) on the set of all nonnegative solutions to the system of equations of equations above. \(w\geq 0\).
\(w=0\), if any feasible solution to the system above in which all the artificial variables are at zero level. Thus the simplex method applied to this function should replace the artificial variables as basic variables with the variables from the original problem and will hopefully drive the system above into canonical form with basic variables from the original set \(x_j, j=1,\cdots,n\). The value of \(w\) at the associated basic feasible solution would be zero, its minimal value, and the simplex method could then be initiated on the original problem.
Furthermore, if the system above must have feasible solutions in which all the artificial variables equal zero. In this case the minimal value of \(w\) would be \(0\). Thus, when applying the simplex method to the function \(w\) is greater than zero, we can conclude that the original problem has no feasible solutions.
Remark: The function \(w\) need to express in terms of only the nonbasic variables. Using function \(w\) subtract each constraining equation which containing an artificial variable.(In general problem above, artificial variables have been introduced into every constraint. However, this need not always be the case. In some instances, some of the original problem variables may be used in the initial basic variable set.)
\[\begin{array}{rcrlllll} a_{11} x_{1}&+&a_{12} x_{2}&+\ldots+a_{1 n} x_{n}&+x_{n+1}&\ &\ &=b_1\\ a_{21} x_{1}&+&a_{22} x_{2}&+\ldots+a_{2 n} x_{n}& & +x_{n+2}&\ &=b_2\\ \quad \vdots &\ &\ &\ \\ a_{m 1} x_{1}&+&a_{m 2} x_{2}&+\ldots+a_{m n} x_{n}& & &+x_{m+n}&=b_{m}\\ c_{1} x_{1}&+&c_{2} x_{2}&+\ldots+c_{n} x_{n}& & & &=z\\ d_{1} x_{1}&+&d_{2} x_{2}&+\ldots+d_{n} x_{n}& & & &=w_0+w \end{array}\]
We now summarize the procedure for driving a linear programming problem in standard form to a problem in canonical form.
Start with canonical form:
\[\tag{I} \begin{array}{llllllll} x_1&\quad&\quad&+a_{1,m+1}x_{m+1}&+\cdots+a_{1n}x_n&=&b_1\\ &\ddots& & & & &\\ &\qquad&x_m&+a_{m,m+1}x_{m+1}&+\cdots+a_{mn}x_n&=&b_m\\ & & &\quad c_{m+1}x_{m+1}&+\cdots+c_nx_n&=&z_0+z \end{array} \] s.t. \(x_1,\cdots,x_n\geq 0\)
If problem \((\text{I})\) is non-degenerate \(\Rightarrow\) convergence is proved.
Denote \(a_{ij}^*,b_i^*,c_i^*\) as coefficients after pivot.
Lemma A:
Lemma B:
Assume at lease one \(b_i\neq 0\), and there is a sequence of pivot steps that solves the problem above. Then, if we replace all \(b_i=0\), the same pivot sequence can be used to solve it.
Theorem 4(Convergence of Simplex method): For linear problem in canonical form(problem above), these exists a sequence of pivot step, that solves the problem. i.e. (we can apply either Thm O or Thm U)
Recall:
Thm O: All \(c_i^*\geq 0\Rightarrow z_{min}=-z_0^*\)
Thm U: For some \(c_k^*<0\) and \(a_{ik}^*\leq 0\), \(\forall \ i,\Rightarrow z_{min}\rightarrow -\infty\)
Proof Theorem 4:(Mathematical induction)
By induction, on \(m=\# equations\)
Base case: \(m=1\), only one equation in problem above
\[ \begin{array}{llll} x_1+&a_{1,m+1}x_{m+1}+\cdots+a_{1n}x_n&=&b_1\\ &\quad c_{m+1}x_{m+1}+\cdots+c_nx_n&=&z_0+z \end{array} \]
If \(b_1\neq 0\), by Lemma A \(\Rightarrow b_i^*\neq 0 \Rightarrow\) non-degenerate \(\Rightarrow\) simplex converges
If \(b_1=0\), by Lemma B \(\Rightarrow\) same sequence of pivot will solve it.
Induction step: Assume statement holds for \(m-1\) or less equations, Need to prove it for \(m\) equations
Case A:
Assume among \(m\) equations, at least one \(b_i\neq 0\)
Step 1: Apply simplex, untill we can’t pivot further to reduce \(z\).
Let \(r=\#\text{of zero}\ b_i\). By Lemma A, \(\Rightarrow r<m\).
Step 2: Rearrange equations/indices.
s.t. \[ \begin{cases} b_i^*=0&\text{for}\ 1\leq i\leq r\\ b_i^*>0& \text{for}\ r+1\leq i\leq m \end{cases} \]
Then we have the following problem:
\[\tag{II} \begin{array}{lllllllllll} x_1& & & &\cdots& &+& a_{1,m+1}^*x_{m+1}&\cdots& a_{1n}^*x_n &= 0\\ &\ddots& & & & & & & &\\ & &x_r& &\cdots& &+&a_{r,m+1}^*x_{m+1}&\cdots&a_{rn}^*x_n&=0\\ &\cdots& &x_{r+1}&\cdots& &+&a_{r+1,m+1}^*x_{m+1}&\cdots& a_{r+1,n}^*x_n &= b_{r+1}^*\\ & & & &\ddots& & & & &\\ &\cdots& & & &x_{r+m}&+& a_{r+m,m+1}^*x_{m+1}&\cdots&a_{r+m,n}^*x_n&=b_m^*\\ & & & & & & & c_{m+1}x_{m+1}+&\cdots&+c_nx_n&=z_0+z \end{array} \]
Extract the first \(r\) equations as Equations \((*)\). And the last Equation as \((0)\).
Step 3: Consider \((*) +(0)\Rightarrow\) Canonical form with \(r\) equations,where \(r\leq m-1\).
By induction assumption, we have a sequence of pivot that solve it.
Step 4: Apply the same sequence of pivot on \((\text{II})\).
\(z_0^*\) is unchanged.
There are two cases
All \(c_j^*\geq 0 \Rightarrow\) Thm O \(\Rightarrow z_{min}=-z_0^*\). Done
For some \(c_k^*<0\) , we have \(a_{ik}^* \leq 0,1\leq i\leq r\)
Step 5: Repeat step 1-4, multiple times.
Each time, either complete the solution or reduce \(z\) values.
\(\Rightarrow\) Finitely many times \(\Rightarrow\) statements holds.
By induction, Thm holds for all m
Case B: Finally, if all \(b_i=0\), by Lemma B, the same sequence will solve it.
End Proof
Remark:
Corollary 4-1: If a LP has feasible solution and the objective function is bounded, then there exists at least one basic solution at which \(z\) ****attains its min.
Definition (max problem): A linear programming problem stated in the following form is said to be in max form.
\[ \begin{gathered} \max z=cx\\ s.t.\ Ax\leq b, x\geq 0 \end{gathered} \]
Definition (min problem): A linear programming problem stated in the following form is said to be in min form.
\[ \begin{gathered} \min z=cx\\ s.t.\ Ax\geq b, x\geq 0 \end{gathered} \]
Where \(A\) is \(m\times n\) matrix, \(x\in \mathbb{R^n}\). There are no restrictions on the signs of the coefficients \(a_{ij}\), constant terms \(b_i\) and \(c_j\).
Definition (dual problem): The dual of the max problem above is the following linear programming problem:
\[ \begin{gathered} \min v=by\\ s.t.\ A^Ty\geq c, y\geq 0 \end{gathered} \]
Where \(y\in \mathbb{R}^m\).
In summary, we have the following:
Max problem: \(\max z=cx\ s.t.\ Ax\leq b,x\geq 0\)
Dual problem: \(\min v=by\ s.t.\ A^Ty\geq c,y\geq 0\)
Consider the dual problem of the max problem, which is equivalent to the problem:
\[ \begin{gathered} \max v=-by\\ s.t.\ -A^Ty\leq -c, y\geq 0 \end{gathered} \]
Then according to definition, its dual problem is:
\[ \begin{gathered} \min z=-cx\\ s.t.\ (-A^T)^Tx\geq -b, x\geq 0 \end{gathered} \]
Which is equivalent to the proble:
\[ \begin{gathered} \max z=cx\\ s.t.\ Ax\leq b, x\geq 0 \end{gathered} \]
The dual of the dual is the original problem.
Summary:
\[ \begin{array}{lcl} \hline \text {Max Problem} & \leftarrow \text {dual} \rightarrow &\text {Min Problem} \\ \hline i\text { th}(\leq) \text { inequality } & &i \text { th nonnegative variable } \\ i \text { th}(=) \text { constraint } & &i \text { th unrestricted variable } \\ j \text { th nonnegative variable } & &j \text { th}(\geq)\text{ inequality } \\ j \text { th unrestricted variable } & &j \text { th}(=) \text { constraint } \\ \text {Objective function coefficients } & &\text {Constant terms of constraints } \\ \text {Constant terms of constraints } & &\text {Objective function coefficients } \\ \text {Coefficient matrix of constraints} A & &\text {Coefficient matrix of constraints } A^T \\ \hline \end{array} \]
remark: For an equation, \(a\leq b\), we can rewrite it as \(a\geq b\ \text{and}\ a\leq b\).
Max problem: \(\max z=cx\quad s.t.\ Ax\leq b,x\geq 0\)
Dual problem: \(\min v=by\quad s.t.\ A^Ty\geq c,y\geq 0\)
Theorem 5: Suppose \(x_0\) is a feasible solution to the max problem and \(y_0\) is a feasible solution to the dual problem. Then:
\[ cx_0\leq by_0 \]
Proof:
We have:
\[ \begin{cases} Ax_0\leq b&x_0\geq 0\\ A^Ty_0\geq c&y_0\geq 0 \end{cases} \]
Define the slacks:
\(u=b-Ax_0\geq 0\) and \(v=A^Ty_0-c\geq 0\)
Then we have:
\(b=u+Ax_0\) and \(c=v+A^Ty_0\)
\(\Rightarrow\), \(by_0=y_0^Tb=y_0^T(u+Ax_0)=y_0^Tu+y_0^TAx_0\)
And \(y_0^Tb\) is a number, so \((y_0^TAx_0)^T=x_0^TA^Ty_0=y_0^TAx_0\)
Then:
\[ \begin{aligned} by_0\ &=y_0^Tb\\ &=y_0^Tu+x_0^TA^Ty_0\\ &=y_0^Tu+x_0^T(v+c)\\ &\geq x_0^Tc=cx_0 \end{aligned} \]
End Proof.
Corollary 5-1: Suppose \(x_0\) is a feasible solution to the max problem and \(y_0\) is a feasible solution to the dual problem. Then:
\[by_0-cx_0=uy_0+vx_0, u=b-Ax_0\ \text{and}\ v=A^Ty_0-c\]
Proof: Same as Theorem’s proof. End Proof.
Corollary 5-2: Under the assumption above, if \(cx_0=by_0\), then \(z_{max}=cx_0=by_0=v_{min}\). And \(x_0\) and \(y_0\) are optimal solution points for their respective problems.
Proof: Suppose \(x_0'\) is any feasible solution to the max problem, then we have \(cx_0'\leq by_0\Rightarrow cx_0'\leq cx_0\).
Thus, the maximum value of the function \(z=cx\) is \(cx_0\).
Suppose \(y_0'\) is any feasible solution to the dual problem, then we have \(by_0'\geq cx_0\Rightarrow by_0'\geq by_0\).
Thus, the maximum value of the function \(v=by\) is \(by_0\).
Corollary 5-3: If the objective function \(z\) of the max problem is not bounded above \(\Rightarrow\) the min problem has no feasible solutions. Similarly, if the objective function \(v\) of the min problem is not bounded below \(\Rightarrow\) the max problem has no feasible solution.
Proof: T.B.A
Theorem 6(Duality Theorem): If either (max) or (min) problem has a bounded optimal solution, so dose the other problem, and the optimal values of the objective functions are equal, that is:
\[\max z=\min v\]
Proof: Assume (max) problem has a optimal solution at \(x_0\) and \(Ax_0\leq b, x_0\geq 0\). And we have \(cx\leq cx_0\). Rewrite (max) problem into standard form and multiply the objective function by \(-1\), then we have the following problem (III):
\[\tag{III} \begin{array}{llll} \text{Minimizing } -c_1x_1-c_2x_2-\cdots-c_nx_n=-z& & & \\ \text{subject to} & & &\\ a_{11} x_{1}+a_{12} x_{2}+\ldots+a_{1 n} x_{n}+x_{n+1}&\ &\ &=b_1\\ a_{21} x_{1}+a_{22} x_{2}+\ldots+a_{2 n} x_{n} & +x_{n+2}&\ &=b_2\\ \quad \vdots \qquad\quad \vdots \qquad\ldots\qquad\quad \vdots &\ &\ &\ \\ a_{m 1} x_{1}+a_{m 2} x_{2}+\ldots+a_{m n} x_{n} & &+x_{m+n}&=b_{m}\\ x_j\geq 0, 1\leq j\leq n+m & & & \end{array} \]
Assume, \(b_i\geq0,i=1,\cdots,m\). (we can do some tricks to make it satisfy.) Then the problem above is in canonical form with basic variables \(x_{n+1},\cdots,x_{n+m}\).
From Theorem 4(Convergence of Simplex method)\(\Rightarrow\exists\) finitely many pivot steps that solve it.
This is the initial tableaux:
\[ \begin{array}{c|ccccccc|c} \hline & x_{1} & x_{2} & \ldots & x_{n} & x_{n+1} & \ldots & x_{n+m} & \\ \hline x_{n+1} & a_{11} & a_{12} & \ldots & a_{1 n} & 1 & 0 & \ldots & b_{1} \\ x_{n+2} & a_{21} & a_{22} & \ldots & a_{2 n} & 0 & 1 & \ldots & b_{2} \\ \vdots & & & & & & & & \\ x_{n+m} & a_{m 1} & a_{m 2} & \ldots & a_{m n} & 0 & \ldots & 1 & b_{m} \\ \hline & -c_{1} & -c_{2} & \ldots & -c_{n} & 0 & 0 & 0 & 0 \\ \hline \end{array} \]
And the final tableaux would assume the form:
\[ \begin{array}{l|ccccccc|c} \hline & x_{1} & x_{2} & \ldots & x_{n} & x_{n+1} & \ldots & x_{n+m} & \\ \hline & & & & & & & & \\ \hline & r_{1} & r_{2} & \ldots & r_{n} & s_{1} & \ldots & s_{m} & c \cdot x_{0} \\ \hline \end{array} \] Since our concern will be only the bottom row of this last tableau. As shown below:
\[ r_1x_1+\cdots+r_nx_n+s_1x_{n+1}+\cdots+s_mx_{n+m}=cx_0+z \]
We have minimal \(z=-cx_0\). Let \(y_0\) be the column vector \((s_1,s_2,\cdots,s_m)^T\), we will show that:
\(y_0\geq 0\) is obviously. The equation above represents the result of all the pivot operations on the initial equation for the objective function:
\[ -c_1x_1-c_2x_2-\cdots-c_nx_n=0+(-z) \]
Just some linear combination of the original constraining equations was added to the initial objective function. Thus there exist \(m\) constants, \(t_i,1\leq i\leq m\). Then we have the following Equations Pivot-Equations:
\[\begin{array}{rcrlllll} t_1(a_{11} x_{1}&+&a_{12} x_{2}&+\ldots+a_{1 n} x_{n}&+x_{n+1}&\ &\ &=b_1)\\ t_2(a_{21} x_{1}&+&a_{22} x_{2}&+\ldots+a_{2 n} x_{n}& & +x_{n+2}&\ &=b_2)\\ \quad \vdots &\ &\ &\ \\ t_m(a_{m 1} x_{1}&+&a_{m 2} x_{2}&+\ldots+a_{m n} x_{n}& & &+x_{m+n}&=b_{m})\\ (-c_{1} x_{1}&-&c_{2} x_{2}&-\ldots-c_{n} x_{n}& & & &=-z) \end{array}\]
Add together the results as shown below:
\[ r_1x_1+\cdots+r_nx_n+s_1x_{n+1}+\cdots+s_mx_{n+m}=cx_0+(-z) \]
Obviously, \(s_i=t_i,1\leq i\leq m\), comparing the coefficients of \(x_j\) for any \(1\leq j\leq n\), we have:
\[ s_1a_{1j}+s_2a_{2j}+\cdots+s_ma_{mj}-c_j=\sum_{i=1}^ms_ia_{ij}-c_j=r_j\geq 0 \]
(Remark: for optimal solution, each coefficient are large than zero, if not which is contradict to the optimal assumption.)
From the expression above, we can easily conclude that \(A^Ty_0\geq c\).
Since \(s_i=t_i\), from the Equations above, we must have \(\sum_{i=1}^mt_ib_i=\sum_{i=1}^ms_ib_i=cx_0\).
Then we have \[by_0=cx_0\]
Since \(y_0\geq 0\) and \(A^Ty_0\geq c\), the point \(y_0\) is a feasible solution to the min problem. The value of the objective function \(v\) at \(y_0\) ,\(by_0\) is equal to the value of the objective function \(z\) at \(x_0\). Thus from Corollary 5-2, the minimal value of \(v\) is \(by_0\), so the optimal values of both problems are equal.
End Proof
Corollary 6-1: If both the (max) and (min) problems have feasible solutions, then both objective function have optimal solutions and \(\max z=\min v\).
Proof: Since both problems have feasible solutions, by Theorem 5 that the objective function \(z\) is bounded above and \(v\) is bounded below. From Corollary 4-1(after Convergence), both objective functions can attain their optimal values, By Theorem 6(Duality Theorem), we conclude \(z_{max}=v_{min}\).
End Proof.
Theorem 7(Complementary Slackness Theorem): Suppose \(x^*=(x_1^*,\cdots,x_n^*)\) is a feasible solution to the max problem of:
\[ \max z=cx,\ s.t.\ Ax\leq b,x\geq 0 \]
and \(y^*=(y_1^*,\cdots,y_m^*)\) is a feasible solution to the dual problem of:
\[ \min v=by,\ s.t.\ A^Ty\geq c, y\geq 0 \]
Then \(x^*\) and \(y^*\) are optimal solution points to their respective problems iff:
\[ (b-Ax^*)y^*+(A^Ty^*-c)x^*=0 \]
(Remark: the equation above is equivalent to:
\[ \begin{cases} (b-Ax^*)y^*=0\\ (A^Ty^*-c)x^*=0 \end{cases} \]
Proof:
Since \(x^*\) is a feasible solution to the max problem and \(y^*\) is a feasible solution to the dual problem. According to the Corollary 5-1, we have:
\[ by^*-cx^*=(b-Ax^*)y^*+(A^Ty^*-c)x^* \]
(Sufficiency): If \(x^*\) and \(y^*\) satisfy the complementary slackness hypothesis, then \(by^*=cx^*\), from Corollary 5-2, \(x^*\) and \(y^*\) are optimal solution points for their respective problems.
(Necessary): If \(x^*\) and \(y^*\) are optimal solution points for their respective problems, then we have:
\[ by^*-cx^*=(b-Ax^*)y^*+(A^Ty^*-c)x^*=0 \]
that is, the points \(x^*\) and \(y^*\) satisfy the complementary slackness conditions.
End Proof
Bazaraa, Mokhtar S, John J Jarvis, and Hanif D Sherali. 2011. Linear Programming and Network Flows. John Wiley & Sons.
Thie, Paul R, and Gerard E Keough. 2011. An Introduction to Linear Programming and Game Theory. John Wiley & Sons.