Engineering Optimization: Theory and Practice, Fourth Edition

10.3 Gomory’s Cutting Plane Method 603

SOLUTION

Step 1: Solve the LP problem by simplex method by neglecting the integer requirement.
This gives the following optimal tableau:

Basic Coefficients of variables

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

x (^11011363610112)
x 2 0 1 − 121 121 0 92
−f (^001271251692)
The noninteger solution given by this tableau is
x 1 = 512 , x 2 = 412 , y 1 =y 2 = 0 ,andfmin= − 3412.
Step 2: Formulate a Gomory constraint. Sincex 2 is the only variable that is restricted
to take integer values, we construct the Gomory constraint forx 2. From the
tableau of step 1, we obtain
x 2 =b 2 −a 21 y 1 −a 22 y 2
where
b 2 =^92 , a 21 = − 121 , nda a 22 = 121
According to Eq. (10.3), we writeb 2 asb 2 =bˆ 2 +β 2 wherebˆ 2 = and 4 β 2 =^12.
Similarly, we write from Eq. (10.10)
a 21 =a+ 21 +a 2 − 1
a 22 =a+ 22 +a 2 − 2
where
a 2 + 1 = 0 , a− 21 = − 121 ( inces a 21 is negative)
a 2 + 2 = 121 , a 2 − 2 = 0 (sincea 22 is nonnegative)
The Gomory constraint can be expressed as [from Eq. (10.26)]:
s 2 −

∑^2

j= 1

a+ 2 jyj+

β 2

β 2 − 1

∑^2

j= 1

a 2 −jyj= −β 2

wheres 2 is a slack variable that is not required to take integer values. By

substituting the values ofai+j,a−ij, andβi, this constraint can be written as

s 2 + 121 y 1 − 121 y 2 = −^12