American University in Cairo – School of Science and Engineering

Mechanical Engineering Dept.

MENG 4440 - Engineering Operations Research – Fall 2018
Solutions to selected LP formulation problems

Problem 10, page 55

Decision variables:
X1 : Number of boxes of Grano to be shelved daily
X2 : Number of boxes of Wheatie to be shelved daily

Objective function:
Minimize total profit Z = X1 + 1.35 X2

Constraints:
(1) Available shelf space in ft2:
0.2 X1 + 0.4 X2 ≤ 60 (1)

(2) Maximum daily demand for both types of cereals

X1 ≤ 200 (2)
X2 ≤ 120 (3)

(3) Non-negativity constraints

X1, X2 ≥ 0 (4)

Problem 4, page 60

Decision variables:
X1 : hours of work in store 1 per week
X2 : hours of work in store 2 per week

Objective function:
Minimize total stress Z = 8 X1 + 6 X2

Constraints:
(1) Must work at least 20 hours a week:
X1 + X2 ≥ 20 (1)

(2) Range for work hours in store 1

X1 ≥ 4.5 (2.1)
X1 ≤ 12 (2.2)

(3) Range for work hours in store 2

X2 ≥ 5.5 (3.1)
X2 ≤ 10 (3.2)

(4) Non-negativity constraints

X1, X2 ≥ 0 (apparently redundant)
Problem 4, page73

Decision variables:
St : Money invested in insured savings at the beginning of year t = 1,2,…10
It : Money invested in 6-year investment bonds at the beginning of year t = 1,2,3,4,5
Mt : Money invested in 9-year municipal bonds at the beginning of year t =1,2

Objective function:
Maximize total sum of available money at the end of the 10th year
Maximize Z
Constraints:
Cash balance constraints for the 10 years which are formulated as follows:

Note that the total money that can be invested at the beginning of each year equals the total
money available at the beginning of the year from all prior investments in addition to the
money that is planned to be invested in each year. We assume that the money that is planned
to be invested in each year is available at the beginning of the year.

S1 + I1 + M1 = 2000
S2 + I2 + M2 = 2000 + 1.075 S1 + (0.079/0.98) I1 + (0.085/1.02) M1
S3 + I3 = 2500 + 1.075 S2 + (0.079/0.98) I1 + (0.079/0.98) I2 + (0.085/1.02) M1 + (0.085/1.02)
M2
S4 + I4 = 2500 + 1.075 S3 + (0.079/0.98) I1 + (0.079/0.98) I2 + (0.079/0.98) I3 + (0.085/1.02)
M1 + (0.085/1.02) M2
S5 + I5 = 3000 + 1.075 S4 + (0.079/0.98) I1 + (0.079/0.98) I2 + (0.079/0.98) I3 + (0.079/0.98)
I4 + (0.085/1.02) M1 + (0.085/1.02) M2
S6 = 3500 + 1.075 S5 + (0.079/0.98) I1 + (0.079/0.98) I2 + (0.079/0.98) I3 + (0.079/0.98) I4 +
(0.079/0.98) I5 + (0.085/1.02) M1 + (0.085/1.02) M2
S7 = 3500 + 1.075 S6 + (0.079/0.98) I1 + I1 + (0.079/0.98) I2 + (0.079/0.98) I3 + (0.079/0.98)
I4 + (0.079/0.98) I5 + (0.085/1.02) M1 + (0.085/1.02) M2
S8 = 4000 + 1.075 S7 + (0.079/0.98) I2 + I2 + (0.079/0.98) I3 + (0.079/0.98) I4 + (0.079/0.98)
I5 + (0.085/1.02) M1 + (0.085/1.02) M2
S9 = 4000 + 1.075 S8 + (0.079/0.98) I3 + I3 + (0.079/0.98) I4 + (0.079/0.98) I5 + (0.085/1.02)
M1 + (0.085/1.02) M2
S10 = 5000 + 1.075 S9 + (0.079/0.98) I4 + I4 + (0.079/0.98) I5 + (0.085/1.02) M1 + M1 +
(0.085/1.02) M2

Z = 1.075 S10 + (0.079/0.98) I5 + I5 + M2

Non-negativity constraints
St, It, Mt ≥ 0 for all t = 1,2,…12 whenever applicable
Problem 7, page74

Decision variables:
St : Money deposited at the beginning of month t in regular savings account
Rt : Money invested at the beginning of month t in 3-month certificate
Xt : Money invested at the beginning of month t in 6-month certificate

Objective function:
Maximize total return for the year,
12
0.04 0.055 0.07
Maximize Z =  St + Rt + Xt
t =1 12 4 2

Constraints:

Cash balance constraints for the 12 months which are formulated as follows:

Assuming that the $1000 are set aside at the beginning of each month and the bills are due at
the end of each month. The total money that can be invested at the beginning of each month
equals the total money available at the beginning of the month after paying all due bills.

S1 + R1 + X1 = 1000
S2 + R2 + X2 = 1000 + (1+0.04/12) S1 – 800
S3 + R3 + X3 = 1000 + (1+0.04/12) S2 – 1200
S4 + R4 + X4 = 1000 + (1+0.04/12) S3 + (1+0.055/4) R1 – 400
S5 + R5 + X5 = 1000 + (1+0.04/12) S4 + (1+0.055/4) R2 – 700
S6 + R6 + X6 = 1000 + (1+0.04/12) S5 + (1+0.055/4) R3 – 600
S7 + R7 + X7 = 1000 + (1+0.04/12) S6 + (1+0.055/4) R4 + (1+0.07/2) X1 – 900
S8 + R8 + X8 = 1000 + (1+0.04/12) S7 + (1+0.055/4) R5 + (1+0.07/2) X2 – 1500
S9 + R9 + X9 = 1000 + (1+0.04/12) S8 + (1+0.055/4) R6 + (1+0.07/2) X3 – 1000
S10 + R10 + X10 = 1000 + (1+0.04/12) S9 + (1+0.055/4) R7 + (1+0.07/2) X4 – 900
S11 + R11 + X11 = 1000 + (1+0.04/12) S10 + (1+0.055/4) R8 + (1+0.07/2) X5 – 1100
S12 + R12 + X12 = 1000 + (1+0.04/12) S11 + (1+0.055/4) R9 + (1+0.07/2) X6 – 1300

At the end of the last month, the total money available should cover the total bills.

(1+0.04/12) S12 + (1+0.055/4) R10 + (1+0.07/2) X7 ≥ 1600

Non-negativity constraints
St, Rt, Xt ≥ 0 for all t = 1,2,…12
Problem 1, pages 79-80

a) The LP formulation is provided as follows:

Decision variables:
Xi,m : Weekly production quantity for product i using production method m, where
i  {w, c} where:
w → wrenches
c → chisel
m  {r, o, s} where:
r → regular production
o → overtime production
s → subcontracting

Objective function:
Minimize total production costs
Minimize Z =  
i{ w,c} m{r ,o , s}
pi ,m X i ,m

Where pi,m is the production cost per unit for product i using method m. The values of pi,m are
provided in the following table

i m r o s
w 2 2.8 3
c 2.1 3.2 4.2
Constraints:
(1) Demand satisfaction and inventory balance:
 X i,m  Di
m{r ,o , s }
for all i {w, c}

Where Di is the weekly demand for product i, where Dw = 1570 and Dc = 1250

(2) Ratio of chisels to wrenches is at least 2:1

 X c ,m  X w ,m  2
m{r ,o ,s } m{r ,o ,s }

Or, 
m{r ,o , s}
X c ,m − 2 
m{ r ,o , s}
X w ,m  0

(3) Production capacity limit on each method of production

X i ,m  Li ,m for all i  {w, c} and m  {r, o, s}
Where Li,m is the maximum allowable production level for product i using method m. The
values of pi,m are provided in the following table

i m r o s
w 500 300 10000
c 620 280 10000

(4) Non-negativity constraints

X i ,m  0 for all i  {w, c} and m  {r, o, s}
b) The validity of the presented model in part (a) can be established by proving that the
value of Xi,o cannot be greater than zero unless Xi,r reaches its maximum limit (i.e. Xi,r
= Li,r), and similarly the value of Xi,s cannot be greater than zero unless Xi,o reaches its
maximum limit (i.e. Xi,o = Li,o). The structure of the presented model can satisfy these
conditions without adding any other constraints.

Proof. (by contradiction). Suppose that Xi,r = Li,r - v and Xi,o = v in an optimal solution
where v is an arbitrary value that is greater than zero. The cost associated with this
solution = pi,r (Li,r - v) + pi,o v = pi,r Li,r + (pi,o - pi,r) v. Since pi,o > pi,r there is a better
solution with less cost in which v = 0. Therefore, this solution cannot be optimal.
Similar logic can be applied for overtime and subcontracted productions.


Accordingly, the definition of the objective function along with the constraints
provided in part (a) are sufficient to generate valid solutions in which regular time
production has to be fully satisfied before considering over time production, and over
time production has to be fully satisfied before considering subcontracted production.
Problem 4, page 81

Decision variables:
Qi,t : Number of 20-gallon cartons purchased from supplier i (i = 1, 2) in month t (t = 6,7,8)
It : Inventory (number of 20-gallon cartons) at the end of month t

Objective function:
Minimize total purchasing and inventory costs
8
 2  I + I 
Minimize Z =    pi ,t Qi ,t + 5  t −1 t  
t =6  i =1  2 
Where pi,t is the price per carton from supplier i in month t
Assuming initial inventory equals zero, i.e. I5 = 0

Constraints:

(1) Demand satisfaction and inventory balance:

Q1,t + Q2,t + I t −1 − Dt = I t for all t = 6, 7, 8
Where Dt is the demand of cartons in month t.

(2) Limit on supply quantity

Q1,t  400 for all t = 6, 7, 8
Q2,t  400 for all t = 6, 7, 8

(3) Non-negativity constraints

Q1,t , Q2,t , I t  0 for all t = 6, 7, 8

Problem 2, page 85

Decision variables:
Yi : Number of volunteers starting at hour i {1,…13} where hour 1 is 8:00AM, hour 2 is
9:00AM,… hour 13 is 8:00PM.

Objective function:
Minimize total number of volunteers
13
Minimize Z = Y
i =1
i

Constraints:
Satisfying the minimum number of volunteers needed at each hourly interval:
13

a
i =1
Y ≥ dt
i ,t i for t = {1,2,…14}

Where dt is the minimum number of volunteers needed in time interval t and ai,t =1 if
the volunteers who start at hour i are available in time interval t and zero otherwise.

Based on the given data, the values of ai,t and dt are given as follows
 t 1 2 3 4 5 6 7 8 9 10 11 12 13 14
i 8-9 9-10 10-11 11-12 12-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8 8-9 9-10
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
2 0 1 1 1 0 0 0 0 0 0 0 0 0 0
3 0 0 1 1 1 0 0 0 0 0 0 0 0 0
4 0 0 0 1 1 1 0 0 0 0 0 0 0 0
5 0 0 0 0 1 1 1 0 0 0 0 0 0 0
6 0 0 0 0 0 1 1 1 0 0 0 0 0 0
7 0 0 0 0 0 0 1 1 1 0 0 0 0 0
8 0 0 0 0 0 0 0 1 1 1 0 0 0 0
9 0 0 0 0 0 0 0 0 1 1 1 0 0 0
10 0 0 0 0 0 0 0 0 0 1 1 1 0 0
11 0 0 0 0 0 0 0 0 0 0 1 1 1 0
12 0 0 0 0 0 0 0 0 0 0 0 1 1 1
13 0 0 0 0 0 0 0 0 0 0 0 0 1 1
dt 5 5 8 8 6 6 4 4 8 8 6 6 6 6

Since d13 and d14 are not given, their values are assumed to be 6.

Non-negativity constraints Yi ≥ 0 and integer

Problem 5, page 90

Decision variables:
x1 = number of single-family housing units (homes) to be built
x2 = number of double-family housing units (homes) to be built
x3 = number of triple-family housing units (homes) to be built

Objective function:
Maximize profit (Z) = net return – total water service connection cost
Max. Z = 12,000 x1 + 15,000 x2 + 18,000 x3
- (1000 x1 + 1200 x2 + 1400 x3 + 800 × (x1 + 2 x2 + 3 x3) / 220)

Constraints:
(1) The total number of acres available is 800:
2 x1 + 3 x2 + 5 x3 + (x1 + 2 x2 + 3 x3) / 220  0.85 × 800

(2) Single family homes accounts for at least 50% of the total:
x1 / (x1 + x2 + x3) ≥ 0.5
or, x1 ≥ 0.5 (x1 + x2 + x3)

(3) Water consumption limit of 220,000 gallons per day

400 x1 + 600 x2 + 840 x3 + 450 × (x1 + 2 x2 + 3 x3) / 220  220,000

(4) The minimum charge for the project’s water connection

1000 x1 + 1200 x2 + 1400 x3 + 800 × (x1 + 2 x2 + 3 x3) / 220 ≥ 120,000

(5) Non-negativity constraints:

x1, x2 and x3 ≥ 0
Problem 7, pages 95-96

Decision variables:
xi = total tons of product i to be produced weekly where i  {m, b, w, p}
si = total tons of product i to be sold weekly where i  {m, b, w, p}
m → molasses
b → brown sugar
w → white sugar
p → powder sugar

Objective function:
Maximize profit (Z) = 
i{m ,b , w, p}
ri si

Where ri is the profit per tone of product i, which is given as:

rm = $150, rb = $200, rw = $230, rp = $35,

Constraints:
(6) Weekly production capacity for brown sugar:
xb  0.3 × 4000

(7) Weekly production capacity for molasses:

xm  0.1 × 4000

(8) The production quantity for molasses is the same as the selling quantity:
sm = xm

(9) Relationships between tons of brown sugar and tons of white sugar:
sb = xb – (1/0.8) xw

(10) Relationships between tons of white sugar and tons of powder sugar:
sw = xw – (1/0.98) xp

(11) The production quantity for powder sugar is the same as the selling quantity:
sp = xp

(12) Minimum delivery requirements for all products:

si ≥ 25 for all i  {m, b, w, p}

(13) Non-negativity constraints: [They are clearly redundant due to constraints (7)]
xi, si ≥ 0 for all i  {m, b, w, p}