604 Integer Programming
When this constraint is added to the tableau above, we obtain the following:Basic Coefficients of variables
variables x 1 x 2 y 1 y 2 −f s 2 bix (^110113636100112)
x 2 0 1 − 121 121 0 0 92
−f (^0012712510692)
s 2 0 0 121 − 121 0 1 −^12
Step 3: Apply the dual simplex method to find a new optimum solution. Since−^12 is the
only negativebiterm, the pivot operation has to be done ins 2 row. Further,aij
corresponding toy 2 column is the only negative coefficient ins 2 row and hence
pivoting has to be done on this element,− 121. The result of pivot operation is
shown in the following tableau:
Basic Coefficients of variables
variables x 1 x 2 y 1 y 2 −f s 2 bi
x (^110130013163)
x 2 0 1 0 0 0 1 4
−f 0 0 1 0 1 5 32
y 2 0 0 − 1 1 0 − 12 6
This tableau gives the desired integer solution as
x 1 = 512 , x 2 = 4 , y 2 = 6 , y 1 = 0 , s 2 = 0 , and fmin= − 32
10.4 Balas’ Algorithm for Zero–One Programming Problems
When all the variables of a LP problem are constrained to take values of 0 or 1 only, we
have a zero–one (or binary) LP problem. A study of the various techniques available
for solving zero–one programming problems is important for the following reasons:
1.As we shall see later in this chapter (Section 10.5), a certain class of integer
nonlinear programming problems can be converted into equivalent zero–one
LP problems,
2.A wide variety of industrial, management, and engineering problems can be for-
mulated as zero–one problems. For example, in structural control, the problem
of selecting optimal locations of actuators (or dampers) can be formulated as a
zero–one problem. In this case, if a variable is zero or 1, it indicates the absence
or presence of the actuator, respectively, at a particular location [10.31].
The zero–one LP problems can be solved by using any of the general integer LP
techniques like Gomory’s cutting plane method and Land and Doig’s branch-and-bound