Numerical Methods and Optimization

286 Numerical Methods and Optimization: An Introduction

We can write (12.4) as an equivalent maximization problem,

maximize

m



i=1

(−b

i

)y

i

subject to

m



i=1

(−a

ij

)y

i

≤−c

j

,j=1,...,n

y

1

,...,y

m

≥ 0

(12.5)

and then form its dual:

minimize

n



j=1

(−c

j

)x

j

subject to

n



j=1

(−a

ij

)x

j

≥−b

i

,i=1,...,m

x

1

,...,x

n

≥ 0.

(12.6)

Representing (12.6) as an equivalent maximization problem,

maximize

n



j=1

c

j

x

j

subject to

n



j=1

a

ij

x

j

≤ b

i

,i=1,...,m

x

1

,...,x

n

≥ 0,

(12.7)

we obtain an LP that is identical to the original primal LP (12.3).

Given an LP P,letLPD be its dual. Then the dual of D is given by P.

Taking into account that the dual of the dual gives the primal LP, we

have the following summary of