Proof of Strong Duality Theorem

Let (P) be

\begin{array}{rcl} \max z&=&\mathbf c^T\mathbf{x}\\\mbox{subject to }A\mathbf{x} &\leq&\mathbf{b}\\\mathbf x &\geq& 0\end{array}

Then (D) is

\begin{array}{rcl}\min w&=&\mathbf b^T\mathbf y\\\mbox{subject to } A^T \mathbf{y}&\geq&\mathbf c\\\mathbf y &\geq&0\end{array}

The theorem states: Suppose B is an optimal basis for the primal (P).  Then \mathbf c_B B^{-1} is an optimal solution to the dual.  Also z^*=w^* where * indicates optimal value.

Proof

Step 1

Use the fact that B is an optimal basis for the primal to show that \mathbf c_B B^{-1} is dual feasible.

Let B be an optimal basis for the primal, and define \mathbf c_B B^{-1}=[y_1,y_2,\cdots,y_m]  Thus for the optimal basis B, y_i is the i-th element of \mathbf c_B B^{-1}.  B is optimal for the primal, so the coefficient of each variable in row 0 of B’s primal tableau must be nonnegative.  The coefficient of x_j in row 0 of the B tableau (\bar c_j) is given by

\begin{array}{rcl}\bar c_j &=& \mathbf c_B B^{-1}\\\mathbf a_j-c_j&=&[ \begin{matrix}y_1&y_2&\cdots&y_m\end{matrix}]\left[\begin{matrix}a_{1j}\\a_{2j}\\\vdots\\a_{mj}\end{matrix}\right]-c_j\\&=&y_1a_{1j}+y_2a_{2j}+\cdots+y_ma_{mj}-c_j\end{array}

But we know that \bar c_j\geq0, so for j=1,2,\cdots n,

y_1a_{1j}+y_2a_{2j}+\cdots+y_ma_{mj}-c_j\geq0

Thus, \mathbf c_B B^{-1} satisfies each of the n dual constraints.

Because B is an optimal basis for the primal, we know that each slack variable has a nonnegative coefficient in the B primal tableau.  The coefficient of s_i in B’s row 0 is y_i, the i-th element of \mathbf c_B B^{-1}.  Thus, y_i \geq0 for i=1,2,\cdots,m.  The definition of dual (D), \mathbf c_B B^{-1} satisfies all n constraints and elements are nonnegative.  Thus \mathbf c_B B^{-1} is dual feasible.

Step 2

Show that the optimal primal object function value equals the dual objective function for \mathbf c_B B^{-1}.

The primal objective function value for basis B is \mathbf c_B B^{-1}\mathbf b  The dual objective function value for the dual feasible solution \mathbf c_B B^{-1} is

b_1y_1+b_2y_2+\cdots+b_my_m=[\begin{matrix}y_1&y_2&\cdots&y_m\end{matrix}]\left[\begin{matrix}b_1\\b_2\\\vdots\\b_m\end{matrix}\right]=\mathbf c_B B^{-1}\mathbf b

Thus, step 2 is shown as required.

Step 3

Given that we have found a primal feasible solution and a dual feasible solution that have equal objective values, we can conclude that \mathbf c_B B^{-1} is optimal for the dual, and z^*=w^*

\Box


Bookmark and Share

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: