$\begin{array}{c}\hfill \text{maximize}\sum _{j=1}^{n}{c}_{j}{x}_{j}\hfill \\ \hfill \text{subject to}\hfill \\ \hfill \sum _{j=1}^{n}{a}_{\mathrm{ij}}{x}_{j}\le {b}_{i}\hfill \\ \hfill 0\le j\le n\text{and}1\le i\le m\hfill \\ \hfill {x}_{j}\ge 0\hfill \end{array}$ |

We shall assume the ${b}_{i}$are greater than or equal to $0$, so that the initial $x$ can be taken to be $0$. The Dual LP can be written in the form

$\begin{array}{c}\hfill \text{minimize}\sum _{i=1}^{m}{b}_{i}{y}_{i}\hfill \\ \hfill \text{subject to}\hfill \\ \hfill \sum _{j=1}^{m}{a}_{\mathrm{ij}}{y}_{i}\ge {c}_{j}\hfill \\ \hfill 0\le j\le n\text{and}1\le i\le m\hfill \\ \hfill {y}_{i}\ge 0\hfill \end{array}$ |

Now rewrite both the Primal and Dual in augmented form to turn the inequalities into equalities.

$\begin{array}{c}\hfill \text{maximize}\sum _{j=1}^{n}{c}_{j}{x}_{j}\hfill \\ \hfill \text{subject to}\hfill \\ \hfill \sum _{j=1}^{n}{a}_{\mathrm{ij}}{x}_{j}+{w}_{i}={b}_{i}\hfill \\ \hfill 0\le j\le n\text{and}1\le i\le m\hfill \\ \hfill {x}_{j}\ge 0\text{and}{w}_{i}\ge 0\hfill \end{array}$ |

$\begin{array}{c}\hfill \text{minimize}\sum _{i=1}^{m}{b}_{i}{y}_{i}\hfill \\ \hfill \text{subject to}\hfill \\ \hfill \sum _{j=1}^{m}{a}_{\mathrm{ij}}{y}_{i}-{z}_{j}={c}_{j}\hfill \\ \hfill 0\le j\le n\text{and}1\le i\le m\hfill \\ \hfill {y}_{i}\ge 0\hfill \end{array}$ |

There is a fundamental relationship between the ${x}_{*}$variables of the Primal and the ${z}_{*}$ variables of the Dual. We'll refer to these variables as dual to one another. There is a similar relationship between the variables ${y}_{i}$of the Dual and the ${w}_{i}$of the Primal. Again, refer to the variables as dual to one another. We can indicate the correspondence by a table.

$\begin{array}{cccccccc}\hfill \text{P}\hfill & \hfill {x}_{1}\hfill & \hfill .\hfill & \hfill .\hfill & \hfill {x}_{n}\hfill & \hfill {w}_{1}\hfill & \hfill .\hfill & \hfill {w}_{m}\hfill \\ \hfill \text{D}\hfill & \hfill {z}_{1}\hfill & \hfill .\hfill & \hfill .\hfill & \hfill {z}_{n}\hfill & \hfill {y}_{1}\hfill & \hfill .\hfill & \hfill {y}_{m}\hfill \end{array}$ |

Assuming the ${b}_{i}$are all nonnegative, we have a natural initial starting basic feasible solution for the Primal. We indicate this by a new table with an additional two rows to indicate which variables are basic (*) and which are non basic (no * ). We indicate basic for both Primal and Dual.

$\begin{array}{ccccccccccc}\hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill *\hfill & \hfill *\hfill & \hfill *\hfill & \hfill *\hfill \\ \hfill \text{P}\hfill & \hfill {x}_{1}\hfill & \hfill .\hfill & \hfill .\hfill & \hfill .\hfill & \hfill .\hfill & \hfill {x}_{n}\hfill & \hfill {w}_{1}\hfill & \hfill .\hfill & \hfill .\hfill & \hfill {w}_{m}\hfill \\ \hfill \text{D}\hfill & \hfill {z}_{1}\hfill & \hfill .\hfill & \hfill .\hfill & \hfill .\hfill & \hfill .\hfill & \hfill {z}_{n}\hfill & \hfill {y}_{1}\hfill & \hfill .\hfill & \hfill .\hfill & \hfill {y}_{m}\hfill \\ \hfill \hfill & \hfill *\hfill & \hfill *\hfill & \hfill *\hfill & \hfill *\hfill & \hfill *\hfill & \hfill *\hfill \end{array}$ |

Note that the variables that are basic in the Primal correspond to variables that are nonbasic in the Dual, and variables that are basic in the Dual correspond to variables that are nonbasic in the Primal. Now suppose we perform a pivot operation on the Primal. We get a new set of basic and nonbasic variables. To perform the corresponding pivot operation on the Dual one must select a pivot element such that this basic-nonbasic relationship between the Primal variables and corresponding Dual variables continues to hold. Hence if at some point during the simplex procedure one has a table with basic variable for the Primal indicated by $*$ then, after performing the corresponding pivot operation on the Dual, the basic variables for the Dual must be those whose corresponding Primal variables are nonbasic. This is indicated in the following table.

$\begin{array}{ccccccccccc}\hfill \hfill & \hfill \hfill & \hfill *\hfill & \hfill *\hfill & \hfill \hfill & \hfill \hfill & \hfill *\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill *\hfill \\ \hfill \text{P}\hfill & \hfill {x}_{1}\hfill & \hfill .\hfill & \hfill .\hfill & \hfill .\hfill & \hfill .\hfill & \hfill {x}_{n}\hfill & \hfill {w}_{1}\hfill & \hfill .\hfill & \hfill .\hfill & \hfill {w}_{m}\hfill \\ \hfill \text{D}\hfill & \hfill {z}_{1}\hfill & \hfill .\hfill & \hfill .\hfill & \hfill .\hfill & \hfill .\hfill & \hfill {z}_{n}\hfill & \hfill {y}_{1}\hfill & \hfill .\hfill & \hfill .\hfill & \hfill {y}_{m}\hfill \\ \hfill \hfill & \hfill *\hfill & \hfill \hfill & \hfill \hfill & \hfill *\hfill & \hfill *\hfill & \hfill \hfill & \hfill *\hfill & \hfill *\hfill & \hfill *\hfill \end{array}$ |

If one performs the simplex algorithm on the Primal and performs the corresponding pivot operation on the Dual ( as indicated above), then if the Primal becomes optimal, the Dual will become feasible. The feasibility of the Dual will be indicated by obtaining nonnegative values for the basic variables. Note that in the initial table above for the Dual, the basic variables for the Dual, the ${z}_{*}$are not feasible unless all of the ${c}_{j}$are nonpositive.

File translated from T

On 10 Oct 2007, 15:47.