Engineering Optimization: Theory and Practice, Fourth Edition

598 Integer Programming

Here

cj

−arj

=

7

12

×

36

11

=

21

11

for columny 1

=

5

12

×

36

1

=15 for columny 2.

Since^2111 is minimum out of^2111 and 15, the pivot element will be−^1136. The

result of pivot operation is given in the following tableau:

Basic Coefficients of variables

variables x 1 x 2 y 1 y 2 −f s 1 bi

bi/ais

forais> 0

x 1 1 0 0 0 0 1 5

x 2 0 1 0 111 0 − 113 5111

−f (^0001141211136911)
y 1 0 0 1 111 0 −^36111811
The solution given by the present tableau isx 1 = , 5 x 2 = 4117 ,y 1 = 1117 , and
f=− 33116 , in which some variables are still nonintegers.
Step 4:Generate a new Gomory constraint. To generate the new Gomory constraint,
we arbitrarily selectx 2 as the variable having the largest fractional value (since
there is a tie betweenx 2 andy 1 ). The row corresponding tox 2 gives
x 2 =^5111 − 111 y 2 + 113 s 1
From this equation, the Gomory constraint [Eq. (10.9)] can bewritten as
s 2 − 111 y 2 + 113 s 1 = − 117
When this constraint is added to the previous tableau, we obta in the following
tableau:
Basic Coefficients of variables
variables x 1 x 2 y 1 y 2 −f s 1 s 2 bi
x 1 1 0 0 0 0 1 0 5
x 2 0 1 0 111 0 − 113 0 5111
y 1 0 0 1 111 0 −^361101811
−f (^00011412111036911)
s 2 0 0 0 − 111 0 113 1 − 117
Step 5: Apply the dual simplex method to find a new optimum solution. To carry the
pivot operation, the pivot row is selected to correspond to the most negative
value ofbi. This is thes 2 row in this case.