# 4 Integer Programming

 Page 2/4 Date 11.10.2016 Size 299.78 Kb. #8
1   2   3   4

Define variables yj as the number of times the j-th pattern is cut. In addition, denote by v1, v2, & v3 the number of 8 ft, 5 ft, and 3 ft rods that are purchased.
Min z = 1y1 + 1y2 + 1.5y3 + 1.5y4 + 0.5y5 + 0.5y6 + 1y7 +

1.5y8 + 2v1 + 1.5v2 + 1.1v3.
s.t. y1 + y2 + y3 + y4 ≤ 20. (1)

y5 + y6 + y7 + y8 ≤ 25. (2)

(supply constraints)
y1 + y5 + v1 ≥ 60. (3)

2y2 + 1y3 + 2y6 + 1y7 + v2 ≥ 40. (4)

1y1 + 2y3 + 4y4 + 1y7 + 3y8 + v3 ≥ 75. (5)

(demand constraints)
y1, y2, …, y8; v1, v2, v3 ≥ 0 and integer.
Optimal solution: = 2, = 0, = 0, = 18, = 5, = 0, and = 0, as well as = 53, = 0, & = 1. No rods are left over, the demand is exactly satisfied.
2-dimensional cutting stock problems: same formulation, cutting plans are more difficult to set up.

Material usage: pattern 1: 34/40 sq ft = 85%,

pattern 2: 32/40 sq ft = 80%.
However: pattern 1 requires frequent machine adjustments. Also: guillotine cuts.

4.2.2 Diet Problem Revisited
Two foodstuffs, one nutrient.
Min z = 3x1 + 4x2

s.t. x1 + 2x2  5

x1, x2  0.
plus: “if food 1 is in the diet, then food 2 should not be included.
Define logical variables y1 (and y2) as one, if food 1 (food 2) is included in the diet, and zero otherwise.

 y1 y2 OK? 0 0  0 1  1 0  1 1 No

A formulation that allows the first three cases & prohibits the last case is
y1 + y2  1.

y1, y2 = 0 or 1.
Adding these constraints to the formulation is not sufficient, though, as it allows the continuous variables x1 & x2 to change independent of y1 and y2. We need linking constraints. Here,
x1My1 &

x2My2,
with M >> 0 (but not too large, scaling).
Validity: If y1 = 1 (the food is included in the diet), then the constraint reads x1M, &, given that M is sufficiently large, the constraint is redundant.
On the other hand, if y1 = 0 (the food is not included in the diet), the constraint reads x1 ≤ 0, &, since x1 ≥ 0, x1 = 0 follows. In other words, if a food is not in the diet, its quantity is zero.
Different additional (conditional) constraint:
if food 1 is included in the diet, then food 2 must be included in the diet as well.”

 y1 y2 OK? 0 0  0 1  1 0 No 1 1 

Here, the additional constraint
y1y2
together with the linking constraints will do.
4.2.3 Land Use
Two choices for a parcel of land: harvest or protect (but not both). Define variables y1= 1, if we harvest & 0 otherwise, & y2 = 1, if we protect, & 0 otherwise.

 y1 y2 OK? 0 0  0 1  1 0  1 1 No

Again, the additional constraint is y1 + y2 ≤ 1. (There are no other variables, so that there is nothing to link).
Allow 3 options: Harvest (y1), build a sanctuary (y2), or allow the building of a municipal well (y3).
 y1 y2 y3 OK? 0 0 0  0 0 1  0 1 0  1 0 0  0 1 1  1 0 1 No 1 1 0 No 1 1 1 No

Formulate: y1 + y2 ≤ 1 (eliminates the solutions in the last two rows of the decision table), & the constraint

y1 + y3 ≤ 1 (eliminates the solution in the third row from the bottom of the table).

4.2.4 Modeling Fixed Charges

Manufacture a combination of three Operations Research texts:
Gabby and Blabby (GB),

Huff, Fluff, and Stuff (HFS), &

Real OR” (ROR).

There are
3 printing machines are available (only 1 is needed),

2 binding machines (again, only one is needed).
Processing times for printing and binding machines

 P1 P2 P3 GB 3 6 4 HFS 2 3 3 ROR 4 5 5

 B4 B5 GB 10 10 HFS 12 11 ROR 15 14