IE 400: Principles of Engineering Management

Study Set 3 Solutions

Fall 2021

Question 1.

(a) Parameters:
fi = fixed cost of plant i, i = 1, . . . , 4

cij = cost of producing car j at plant i i = 1, . . . , 4, j = 1, 2, 3

Decision
( Variables:
1 if plant i is used i = 1, . . . , 4
yi =
0 o.w
(
1 if car j is produced at plant i i = 1, . . . , 4, j = 1, 2, 3
xij =
0 o.w
Model:
4
X 4 X
X 3
min fi yi + cij xij
i=1 i=1 j=1
3
X
s.t. xij ≤ 1 i = 1, 2, 3, 4 (1)
j=1
4
X
xij = 1 j = 1, 2, 3 (2)
i=1
y3 + y4 ≤ 1 + y1 (3)
xij ≤ yi i = 1, 2, 3, 4 j = 1, 2, 3
xij ∈ {0, 1} i = 1, 2, 3, 4 j = 1, 2, 3
yj ∈ {0, 1} j = 1, 2, 3

1
 Constraint (1): Each plant can produce one type of car.
Constraint (2): The total production of each type of car must be at a
single plant; that is, for example, if any Tauruses are made at plant 1,
then all Tauruses must be made there.
Constraint (3): If plants 3 and 4 are used, then plant 1 must also be
used.

(b)

either y1 + y2 ≤ 1 (*)
or y3 + y4 ≥ 1 (**)

In order to linearize the constraint, add the following decision variable:

(
1 if constraint (*) holds +(1-w) M thus when w=1 "y1+y2<=1"
w= which is the original constraint
0 if constraint (**) holds
when w=0 "y1+y2<=large value" which
Then add the following constraints to the model: is redundant as y1+y2 can be at most 2

y1 + y2 ≤ 1w − (1 − w)M
y3 + y4 ≥ 1(1 − w) + M w
-Mw thus when w=0 "y3+y4>=1" which is the
w ∈ {0, 1}
original constraint
when w=1 "y3+y4>=-large value" which is
where M is a sufficiently large number. redundant as y3+y4 must be at least 0

(For w = 1, the constraint (*) holds and (**) becomes redundant. For
w = 0, the constraint (**) holds and (*) becomes redundant.)

highlighted terms are not wrong but not necessary. If they confuse you, please ignore.
We control the constraints by M terms.

Depending on w;

- M term will take value 0 meaning that the original form of the constraint must be satisfied

- or will take value M for <= constraints (-M for >= constraints) thus the constraint will be redundant.
(LHS is always less than M 'greater than -M' hence the constraint gives no restriction to problem

2
Question 2.

Decision Variables:
(
1 if astronaut i is assigned to post j i = 1, 2, 3, 4, j = 1, 2, 3, 4
xij =
0 o.w
Model:

4 X
X 4
max pij xij
i=1 j=1
4
X
s.t. xij = 1 j = 1, 2, 3, 4 (1)
i=1
X4
xij = 1 i = 1, 2, 3, 4 (2)
j=1

xij ∈ {0, 1} i = 1, 2, 3, 4 j = 1, 2, 3, 4

ˆ Constraint (1) indicates that each post should have a single astronaut.

ˆ Constraint (2) indicates that each astronaut should be assigned to a

single post.

3
Question 3.

Parameters: As given in the question

Decision Variables: As given in the question

Model:
M
X
min xi
i=1
XM
s.t. yik = dk k = 1, · · · , n
i=1
n
X
yik · lk ≤ l · xi i = 1, · · · , M
k=1
xi ∈ {0, 1} i = 1, · · · , M
yik ≥ 0 i = 1, · · · , M k = 1, · · · , n
yik integer i = 1, · · · , M k = 1, · · · , n

Question 4. (a) Parameters:

wj = weight capacity of compartment j (in tons)

sj = space capacity of compartment j (in cubic meters)

wti = weight of cargo i (in tons)

vi = weight of cargo i (in cubic meters/ton)

pi = profit gained from cargo i (TL/ton)

Decision Variables:
xij = amount of cargo i distributed to compartment j in tons

4
 4 X
X 3
max pi xij
i=1 j=1
3
X
s.t. xij ≤ wti i = 1, 2, 3, 4 (1)
j=1
4
X
vi xij ≤ sj j = 1, 2, 3 (2)
i=1
X4
xij ≤ wj j = 1, 2, 3 (3)
i=1
P4 P4 P4
i=1 xi1 i=1 xi2 i=1 xi3
= = (4)
w1 w2 w3
xij ≥ 0 i = 1, 2, 3, 4 j = 1, 2, 3

(b) Replace constraint (4) with

P4 P4
i=1 xi1 i=1 xi2
− ≤ 0.1
w1 w2
P4 P4
i=1 xi1 i=1 xi3
− ≤ 0.1
w1 w3
P4 P4
i=1 xi2 i=1 xi3
− ≤ 0.1
w2 w3

You need to linearize these constraints before adding to the model:

P4 P4
i=1 xi1 xi2
− 0.1 ≤ − i=1 ≤ 0.1
w1 w2
P4 P4
i=1 xi1 xi3
− 0.1 ≤ − i=1 ≤ 0.1
w1 w3
P4 P4
x i2 xi3
− 0.1 ≤ i=1 − i=1 ≤ 0.1
w2 w3

(c) (b) is more likely to have a larger optimal value since the feasible region
in (b) includes the feasible region in (a).

5
 (d) Decision Variables:
xij = amount of cargo i distributed to compartment j in tons
(
1 if cargo i is shipped in compartment j
yij =
0 o.w
Model: All constraints in (b) +

xij ≤ wj yij i = 1, 2, 3, 4 j = 1, 2, 3
3
X
yij ≤ 1 i = 1, 2, 3, 4
j=1

yij ∈ {0, 1} i = 1, 2, 3, 4 j = 1, 2, 3
xij integer i = 1, 2, 3, 4 j = 1, 2, 3

Question 5. (a) Formulate the model to determine which trucks to use

so as to minimize the cost of delivering to all the customers.
Decision Variables:

(
1 if truck k is used k = 1, . . . , 7
xk =
0 o.w
(
1 if customer j is visited by truck k j = 1, . . . , 20 k = 1, . . . , 7
yjk =
0 o.w

zjk =Amount of good is carried by truck k for customer j

j = 1, . . . , 20 k = 1, . . . , 7

6
Model:

7
X
min q k xk
k=1
X7
s.t. zjk = dj j = 1, . . . , 20
k=1
20
X
zjk ≤ Ck xk k = 1, . . . , 7
j=1

zjk ≤ dj yjk j = 1, . . . , 20 k = 1, . . . , 7
yjk ≤ xk j = 1, . . . , 20 k = 1, . . . , 7
xk ∈ {0, 1} k = 1, . . . , 7
yjk ∈ {0, 1} j = 1, . . . , 20 k = 1, . . . , 7
zjk ≥ 0 j = 1, . . . , 20 k = 1, . . . , 7

7
(b) Add the following requirements to your model:

– A single truck cannot deliver to more than six customers.

20
X
yjk ≤ 6 k = 1, . . . , 7
j=1

– Customer 1 and customer 7 cannot be visited by the same truck.

y1k + y7k ≤ 1 k = 1, . . . , 7

– Both customer 2 and customer 12 should be visited by the same

truck(s).
y2,k = y12,k k = 1, . . . , 7
– If a truck visits customer 4 then it has to visit customer 19 or
customer 20. (Assume demands of these customers do not exceed
truck capacities.)

y4,k ≤ y19,k + y20,k k = 1, . . . , 7

– Either at least two of the customers 5, 6 and 7 or at most three

of customers 11, 12, 13 and 14 should be visited by truck 4.

either y5,4 + y6,4 + y7,4 ≥ 2 (1)

or y11,4 + y12,4 + y13,4 + y14,4 ≤ 3 (2)

In order to linearize the constraint, add the following decision

variable:
(
1 if constraint 1 holds
w=
0 if constraint 2 holds
Then add the following constraints to the model:

y5,4 + y6,4 + y7,4 ≥ 2w − (1 − w)M

y11,4 + y12,4 + y13,4 + y14,4 ≤ 3(1 − w) + M w
w ∈ {0, 1}

8
Question
( 6. Decision Variables:
1 if constraint i is satisfied
yi =
0 o.w
(
1 if at least one of 7,8,9 is satisfied
z1 =
0 o.w
(
1 if at least two of 10,11,12,13 are satisfied
z2 =
0 o.w
Model:

min 0
Xn
s.t. aij xj ≤ bi + M (1 − yi ) i = 1, . . . , 20 (1)
j=1
Xn
aij xj ≥ bi − M yi i = 1, . . . , 20 (2)
j=1
20
X
yi ≥ 10 (3)
i=1
y1 ≤ y4 (4)
y2 + y3 ≤ 1 (5)
y5 = y6 (6)
y7 + y8 + y9 ≥ z1 (7)
y10 + y11 + y12 + y13 ≥ 2z2 (8)
z1 + z2 ≥ 1 (9)
z1 , z2 ∈ {0, 1} (10)
yi ∈ {0, 1} i = 1, . . . , 20 (11)

where M is a sufficiently large number. Observe that we minimize zero, which

means that the model is a feasibility problem. If a feasible solution is found
for the above model, the objective will take value 0.

9
 Let’s take a closer look at constraints (1) and (2):

ˆ If yi = 1:
Pn
Constraint (1) becomes j=1 aij xj ≤ bi which means that the con-
straint i is satisfies.
Constraint (2) becomes nj=1 aij xj ≥ bi −M . This makes the constraint
P
redundant as −M is a really small number.

ˆ If yi = 0:
Constraint (1) becomes nj=1 aij xj ≤ bi +M which makes the constraint
P
redundant as M is a really
Pnlarge number.
Constraint (2) becomes j=1 aij xj ≥ bi . This means constraint is not
satisfied.

(3): Point x should satisfy at least 10 of the 20 constraints.

(4): If point x satisfies constraint 1, then it should also satisfy constraint 4.
(5): If point x satisfies constraint 2, then it should not satisfy constraint 3.
(6): If point x satisfies either both of the constraints 5 and 6 or neither of
them.
(7)-(8)-(9): Point x should satisfy either at least one of the constraints 7,8,9
or at least two of constraints 10,11,12,13.

10
Question 7. Decision Variables:

xi : Number
( of workers employed on line i i = 1, 2
1 if line i is used i = 1, 2
yi =
0 o.w
Model:

min 1000y1 + 2000y2 + 500x1 + 900x2

s.t. 20x1 + 50x2 ≥ 120
30x1 + 35x2 ≥ 150
40x1 + 45x2 ≥ 200
x1 ≤ 7y1
x2 ≤ 7y2
x1 , x2 ≥ 0
y1 , y2 ∈ {0, 1}

11
 Question 8

a) Construct standard form of LP.

minimize x1 − 2x2 (1)

x1 + x2 − x3 = 2 (2)

−x1 + x2 − x4 = 1 (3)

x2 + x5 = 3 (4)

x1 , x2 , x3 , x4 , x5 ≥ 0 (5)

b) Construct the Big - M Artificial LP. Construct the tableau which is ready
to apply Simplex during Big - M Method. Is this an optimal solution? If not,
solve until optimality.

z x1 x2 x3 x4 x5 x6 x7 RHS
z 1 -1 2 0 0 0 −M −M 0
x6 0 1 1 -1 0 0 1 0 2
x7 0 -1 1 0 -1 0 0 1 1
x5 0 0 1 0 0 1 0 0 3
Multiply Row 1 and Row 2 by M and add to Row 0 to convert the tableau
to proper format to be able to apply simplex method.

z x1 x2 x3 x4 x5 x6 x7 RHS
z 1 -1 2M + 2 −M −M 0 0 0 3M
x6 0 1 1 −1 0 0 1 0 2
x7 0 −1 1 0 −1 0 0 1 1
x5 0 0 1 0 0 1 0 0 3
You should perform the following pivot operations by applying ratio test to
obtain the optimal tableau. x2 enters x7 leaves, x1 enters x6 leaves, x4 enters
and x1 leaves, x3 enters and x5 leaves. The optimal tableau is:

z x1 x2 x3 x4 x5 x6 x7 RHS
z 1 -1 0 0 0 -2 −M −M -6
x4 0 1 0 0 1 1 0 -1 2
x2 0 0 1 0 0 1 0 0 3
x3 0 -1 0 1 0 1 -1 0 1

2
The optimal point (0,3) is reached with objective -6.

c) Move to Phase 2. Solve until optimality.

The starting basic feasible solution (x1 , x2 ) =(1/2, 3/2). We can start Phase
II starting from the extreme point (1/2, 3/2) and the original objective is mini-
mized.

We can disregard the artificial variables from the table.

Multiply Row 1 and Row 2 by 1 and -2 respectively and add to Row 0.

z x1 x2 x3 x4 x5 RHS
z 1 0 0 1/2 3/2 0 -5/2
x1 0 1 0 -1/2 1/2 0 1/2
x2 0 0 1 -1/2 -1/2 0 3/2
x5 0 0 0 1/2 1/2 1 3/2

x4 enters and x1 leaves

z x1 x2 x3 x4 x5 RHS
z 1 -3 0 2 0 0 -4
x4 0 2 0 -1 1 0 1
x2 0 1 1 -1 0 0 2
x5 0 -1 0 1 0 1 1
x3 enters, x5 leaves

z x1 x2 x3 x4 x5 RHS
z 1 -1 0 0 0 -2 -6
x4 0 1 0 0 1 1 2
x2 0 0 1 0 0 1 3
x3 0 -1 0 1 0 1 1
Since row 0 of all non-basic variables are ≤ 0, the optimal point (0, 3) with
objective −6 is obtained.

3
 Question 9

a) Construct the Big - M Artificial LP. Construct the tableau which is ready to
apply Simplex during Big -M Method.

Minimize − x1 − x2 + M a1 + M a2 (6)
subject to

x1 − x2 − x3 + a 1 = 1 (7)

−x1 + x2 + 2x3 − x4 + a2 = 1 (8)

x1 , x2 , x3 , x4 , a1 , a2 ≥ 0 (9)

z x1 x2 x3 x4 a1 a2 RHS
z 1 1 1 0 0 −M −M 0
a1 0 1 -1 -1 0 1 0 1
a2 0 -1 1 2 -1 0 1 1

b) Does it correspond to an optimal table? If not, solve by simplex method.

Multiply Row 1 and Row 2 by M and add to Row 0 to convert it to proper

format.

z x1 x2 x3 x4 a1 a2 RHS
z 1 1 1 M −M 0 0 2M
a1 0 1 -1 -1 0 1 0 1
a2 0 -1 1 2 -1 0 1 1
x3 enters the basis and a2 leaves.
z x1 x2 x3 x4 a1 a2 RHS
−1 −1
z 1 1 + 21 M 1 − 12 M 0 2 M 0 2 M
3
2M
a1 0 1/2 -1/2 0 -1/2 1 1/2 3/2
a2 0 -1/2 1/2 1 -1/2 0 1/2 1/2
x1 enters the basis and a1 leaves.
z x1 x2 x3 x4 a1 a2 RHS
z 1 0 2 0 1 −M − 2 −M − 1 -3
x1 0 1 -1 0 -1 2 1 3
x3 0 0 0 1 -1 1 1 2

4
 c) What can you say about the problem after solving by the Big-M method?

After a sequence of simplex iterations x3 enters a2 leaves; and x1 enters a1

leaves we reach the final tableau above. Now, the most positive Row 0 coeffi-
cient corresponds to x2; therefore it is the entering variable. However, the min
ratio test cannot be applied. Therefore the big-M LP is unbounded. Since there
are no artificial variables in the basis in the final tableau, the original LP is also
unbounded.

Question 10

The given tableau corresponds to:

z x RHS
1 cB B −1 A − c cB B −1
xB 0 B −1 A B −1 b

where B = [a3 , a2 , ae2 ].

Since we are given B −1 A (with A the constraint matrix in the big-M LP) and
B, we can get A by doing the multiplication BB −1 A. So
  
1 1 0 0 0 1 1 0 0 −1
BB −1 A = 1 −1 −1  1 1 0 0 0 0 1 (10)
0 1 0 −3 0 0 1 1 −1 −2

We obtain  
1 1 1 1 0 0 0
A = 2 −1 1 0 −1 1 0
1 1 0 0 0 0 1

Since we need the original LP in 3 variables, we shall take the columns corre-
sponding to x1 , x2 , and x3 . Then we need to calculate the objective coefficient
values by cB = (cx3 , cx2 , ce2 ) = (cx3 , cx2 , 0) since we know that the objective
coefficient of the surplus variable e2 is zero.
 
0 0 1 1 0 0 −1
cB B −1 A−c = (cx3 , cx2 , 0)  1 1 0 0 0 0 1 −(cx1 , cx2 , cx3 , cs1 , ce2 , ca2 , ca3 )
−3 0 0 1 1 −1 −2

= (1, 0, 0, 1, 0, M, M + 3)

cB B −1 A − c = (cx2 − cx1 , 0, 0, cx3 , 0, M, M + cx2 − cx3 ) = (1, 0, 0, 1, 0, M, M + 3)

5
 Therefore,
cx1 = 3, cx2 = 4, cx3 = 1
Finally, we need to construct the right hand side vector now. Since we know
BB −1 b, we can find right hand side vector b by doing the calculating BB −1 b.
So,
  
1 1 0 40
BB −1 b = 1 −1 −1 10
0 1 0 15
 
50
b = 15
10

Thus our original LP can be reconstructed as follows:

maximize 3x1 + 4x2 + x3

subject to
x1 + x2 + x3 ≤ 50
2x1 − x2 + x3 ≥ 15
x1 − x2 = 10
x1 , x2 , x3 ≥ 0

6
 Question 11

a) Solve Phase II.

To begin Phase II, you need to get rid of artificial variables and insert the
given objective in Row 0 format, i.e.,

Basis z x1 x2 x3 s1 e2 RHS
z 1 −3 −3 −4 0 0 0
e2 0 −3 0 0 1 1 15
x3 0 0 0 1 1 0 40
x2 0 1 1 0 0 0 10

Note that this tableau is not in proper format for simplex to start since some
of the basic variables have zero components in Row 0. To fix this, add 3 times
x2 row and 4 times x3 row to the objective row to get the following tableau in
proper format:
Basis z x1 x2 x3 s1 e2 RHS
z 1 0 0 0 4 0 190
e2 0 −3 0 0 1 1 15
x3 0 0 0 1 1 0 40
x2 0 1 1 0 0 0 10
Now, we see that we do not have to iterate anymore since the tableau is optimal.

b) Since there exists a nonbasic variable in row 0 with zero coefficient, and
since the ratio test if x1 enters is nonzero, and since it is a finite value (namely
10), we get an alternate optimal bfs vector.

Set of optimal solutions is

        
 x1 x1 0 10 
x2  : x2  = λ 10 + (1 − λ)  0  where λ ∈ [0, 1]
x3 x3 40 40
 

all with optimal value 190.