Engineering Optimization: Theory and Practice, Fourth Edition

10.3 Gomory’s Cutting Plane Method 597

betweenx 1 andx 2 , let us selectx 1 as the basic variable having the largest

fractional value. From the row corresponding tox 1 in the last tableau, we can

write

x 1 =^112 −^1136 y 1 − 361 y 2 (E 1 )

wherey 1 andy 2 are used in place ofx 3 andx 4 to denote the nonbasic variables.

By comparing Eq. (E 1 ) with Eq. (10.2), we find that

i= 1 , b 1 =^112 , bˆ 1 = 5 , β 1 =^12 , a 11 =^1136 ,

aˆ 11 = 0 , α 11 =^1136 , a 12 = 361 , aˆ 12 = 0 , and α 12 = 361

From Eq. (10.9), the Gomory constraint can be expressed as

s 1 −α 11 y 1 −α 12 y 2 = −β 1 (E 2 )

wheres 1 is a new nonnegative (integer) slack variable. Equation (E 2 ) can be

writtenas

s 1 −^1136 y 1 − 361 y 2 = −^12 (E 3 )

By introducing this constraint, Eq. (E 3 ), into the previous optimum tableau,

we obtain the new tableau shown below:

Basic Coefficients of variables

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

bi/ais

forais> 0

x (^110113636100112)
x 2 0 1 − 121 121 0 0 92
−f (^0012712510692)
s 1 0 0 −^1136 − 361 0 1 −^12
Step 3: Apply the dual simplex method to find a new optimum solution. For this, we
select the pivotal rowrsuch thatbr= inm (bi< 0 )=−^12 corresponding tos 1
in this case. The first columnsis selected such that
cs
−ars
= min
arj< 0

(

cj

−arj

)