Primal Dual Relationship

1 Primal Dual Relationship

I describe the relationship between the pivot operations of the simplex method on the Primal LP and the corresponding operations on the Dual LP. So given a sequence of pivot operations on the Primal LP, these is a corresponding sequence of pivot operations on the Dual LP. We assume we start with the Primal LP in standard form.

\begin{matrix} maximize \sum_{j = 1}^{n} c_{j} x_{j} \\ subject to \\ \sum_{j = 1}^{n} a_{ij} x_{j} \leq b_{i} \\ 0 \leq j \leq n and 1 \leq i \leq m \\ x_{j} \geq 0 \end{matrix}

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{matrix} minimize \sum_{i = 1}^{m} b_{i} y_{i} \\ subject to \\ \sum_{j = 1}^{m} a_{ij} y_{i} \geq c_{j} \\ 0 \leq j \leq n and 1 \leq i \leq m \\ y_{i} \geq 0 \end{matrix}

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

\begin{matrix} maximize \sum_{j = 1}^{n} c_{j} x_{j} \\ subject to \\ \sum_{j = 1}^{n} a_{ij} x_{j} + w_{i} = b_{i} \\ 0 \leq j \leq n and 1 \leq i \leq m \\ x_{j} \geq 0 and w_{i} \geq 0 \end{matrix}

\begin{matrix} minimize \sum_{i = 1}^{m} b_{i} y_{i} \\ subject to \\ \sum_{j = 1}^{m} a_{ij} y_{i} - z_{j} = c_{j} \\ 0 \leq j \leq n and 1 \leq i \leq m \\ y_{i} \geq 0 \end{matrix}

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{matrix} P & x_{1} & . & . & x_{n} & w_{1} & . & w_{m} \\ D & z_{1} & . & . & z_{n} & y_{1} & . & y_{m} \end{matrix}

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{matrix} * & * & * & * \\ P & x_{1} & . & . & . & . & x_{n} & w_{1} & . & . & w_{m} \\ D & z_{1} & . & . & . & . & z_{n} & y_{1} & . & . & y_{m} \\ * & * & * & * & * & * \end{matrix}

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{matrix} * & * & * & * \\ P & x_{1} & . & . & . & . & x_{n} & w_{1} & . & . & w_{m} \\ D & z_{1} & . & . & . & . & z_{n} & y_{1} & . & . & y_{m} \\ * & * & * & * & * & * \end{matrix}

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_EX by T_TM, version 3.72.
On 10 Oct 2007, 15:47.