596 Integer Programming
SOLUTION
Step 1: Solve the LP problem by neglecting the integer requirement of the variables
xi, i= 1 to 4, using the regular simplex method as shown below:Basic Coefficients of variables
variables x 1 x 2 x 3 x 4 −f bi bi/aisforais> 0
x 3 3 − 1 1 0 0 12
x 4 3 11 0 1 0 66 6 ←
Pivot
element
−f − 3 − 4 0 0 1 0
↑
Most negativecjResult of pivoting:x 3 3611 0 1 111 0 18 112 ←Smaller
Pivot one
element
x 2 113 1 0 111 0 6 22
−f −^211100114124
↑
Most negativecjResult of pivoting:x (^11011363610112)
x 2 0 1 − 121 121 0 92
−f (^001271251692)
Since all the cost coefficients are nonnegative, the last tableau gives the opti-
mum solution as
x 1 =^112 , x 2 = 29 , x 3 = 0 , x 4 = 0 , fmin= −^692
which can be seen to be identical to the graphical solution obt ained in
Section 10.2.
Step 2: Generate a Gomory constraint. Since the solution above is noninteger, a
Gomory constraint has to be added to the last tableau. Since there is a tie