AMERICAN 
UNIVERSITY 
OF 
BEIRUT 


Suliman 
S. 
Olayan 
School 
of 
Business 
DCSN 
205 
– 
Managerial 
Decision 
Making 
Spring 
2009-2010 
Midterm 
Exam 
20 
April 
2010 


This 
exam 
is 
administered 
in 
full 
observance 
of 
the 
Olayan 
School 
of 
Business 
Honor 
Code 
and 
the 
penalties 
it 
sets 
for 
violations 
of 
the 
standard 
of 
academic 
conduct. 
You 
are 
required 
to 
fully 
understand 
the 
code 
and 
to 
strongly 
adhere 
to 
it. 
In 
particular, 
mobile 
telephones 
and 
computers 
of 
any 
shape 
or 
size 
are 
not 
allowed. 
No 
questions, 
no 
comments, 
no 
borrowing, 
and 
no 
disturbance 
of 
the 
peace 
of 
any 
kind 
will 
be 
permitted 
or 
tolerated. 
You 
are 
required 
to 
stop 
working 
on 
the 
exam 
and 
hand 
it 
immediately 
when 
a 
proctor 
instructs 
you 
to 
do 
so. 
Any 
cheating 
or 
attempted 
cheating 
will 
subject 
the 
oender 
to 
a 
zero 
on 
the 
exam 
and 
a 
referral 
to 
the 
Student 
Aairs 
Committee 
for 
further 
penalties. 
Please, 
sign 
the 
following 
pledge. 


\I 
fully 
understand 
and 
strongly 
adhere 
to 
the 
School 
of 
Business 
Honor 
Code. 
I 
vow 
to 
complete 
the 
exam 
on 
my 
own 
without 
giving 
or 
receiving 
help 
from 
anyone, 
and 
to 
adh
ere 
to 
the 
academic 
integrity 
standards 
re
ected 
in 
the 
AUB 
student 
code 
of 
conduct.” 


Your 
Signature: 


Your 
Name 
and 
ID: 


Select 
Your 
Section: 


Instructor 
Section 
Days 
and 
Times 
Selection 
Lama 
Moussawi-Haidar 
1 
MWF 
9:00-9:50 
Lama 
Moussawi-Haidar 
2 
MWF 
10:00-10:50 
Lama 
Moussawi-Haidar 
3 
MWF 
14:00-14:50 
Walid 
Nasr 
4 
MWF 
13:00-13:50 
Walid 
Nasr 
5 
MWF 
12:00-12:50 
Neil 
Yorke-Smith 
9 
TTh 
11:00-12:15 


• 
This 
exam 
has 
4 
exercises, 
for 
a 
total 
of 
100 
points. 
You 
have 
2 
hours 
to 
complete 
it. 
• 
Write 
your 
answers 
in 
the 
spaces 
provided. 
Be 
concise 
and 
follow 
the 
instructions 
closely. 
If 
you 
run 
out 
of 
room 
for 
an 
answer, 
continue 
on 
the 
back 
of 
the 
page. 
• 
Your 
understanding 
of 
the 
questions 
is 
part 
of 
the 
exam. 
No 
questions 
will 
be 
answered 
by 
instructors. 
If 
in 
doubt, 
write 
your 
assumptions 
and 
continue 
solving. 
• 
Do 
not 
start 
the 
exam 
(do 
not 
turn 
to 
the 
next 
page) 
until 
instructed 
to 
do 
so. 
• 
Once 
you 
begin, 
it 
is 
your 
responsibility 
to 
check 
that 
your 
paper 
contains 
19 
pages. 

Exercise 
1 


Oliver 
owns 
a 
small 
newspaper 
stand 
in 
downtown 
Beirut. 
Recently, 
Oliver 
installed 
three 
rows 
of 
shelves 
near 
the 
stand 
to 
promote 
the 
sale 
of 
impulse 
items 
like 
soft 
drinks, 
cookies, 
and 
like 
items. 
In 
the 
two 
months 
since 
the 
shelves 
has 
been 
installed 
Oliver 
has 
experimented 
with 
dierent 
items 
on 
the 
shelves 
and 
with 
dierent 
placements. 
As 
marketing 
courses 
teach, 
he 
found 
the 
top 
shelf 
attracted 
the 
most 
attention 
and 
the 
bottom 
shelf 
the 
least. 
Shelf 
size 
limitations 
mean 
that 
no 
more 
than 
three 
items 
can 
be 
placed 
on 
a 
single 
shelf. 
A 
product 
is 
assigned 
to 
at 
most 
one 
shelf 
and 
cannot 
appear 
more 
than 
once. 
Based 
on 
the 
above 
observations, 
Oliver 
was 
able 
to 
estimate 
the 
net 
weekly 
prot 
from 
a 
product 
based 
on 
its 
shelf 
location, 
as 
follows: 


Product 
Shelf 
1 
Shelf 
2 
Shelf 
3 
A 
$79 
$46 
$45 
B 
$76 
$62 
$43 
C 
$73 
$47 
$42 
D 
$69 
$52 
$32 
E 
$66 
$53 
$30 
F 
$56 
$38 
$24 
G 
$51 
$35 
$20 


1. 
Formulate 
a 
LP 
model 
to 
advise 
Oliver 
in 
deciding 
which 
products 
to 
carry 
on 
the 
new 
shelves 
and 
on 
which 
shelf 
should 
they 
be 
carried. 
Dene 
your 
variables 
clearly. 
Solution: 
Decision 
Variables 
[2]: 
Xi;j 
is 
1 
if 
product 
i 
is 
assigned 
to 
shelf 
j 
and 
0 
otherwise, 
for 
i 
= 
A, 
B, 
C, 
D, 
E, 
F, 
G 
and 
j 
=1, 
2, 
3. 


Objectve 
Function 
[2]: 
max 
79XA;1 
+46XA;2+45XA;3 
+76XB;1 
+62XB;2 
+43XB;3 
+ 
::. 


Constraints: 


S.T.: 


Shelf 
capacity 
constraints: 
[3] 
XA;1 
+ 
XB;1 
+ 
XC;1 
+ 
XD;1 
+ 
XE;1 
+ 
XF;1 
+ 
XG;1 
= 
3 
XA;2 
+ 
XB;2 
+ 
XC;2 
+ 
XD;2 
+ 
XE;2 
+ 
XF;2 
+ 
XG;2 
= 
3 


XA;3 
+ 
XB;3 
+ 
XC;3 
+ 
XD;3 
+ 
XE;3 
+ 
XF;3 
+ 
XG;3 
= 
3 
Product 
constraints: 
[3] 
XA;1 
+ 
XA;2 
+ 
XA;3 
= 
1 


XB;1 
+ 
XB;2 
+ 
XB;3 
= 
1 
XC;1 
+ 
XC;2 
+ 
XC;3 
= 
1 
XD;1 
+ 
XD;2 
+ 
XD;3 
= 
1 
XE;1 
+ 
XE;2 
+ 
XE;3 
= 
1 
XF;1 
+ 
XF;2 
+ 
XF;3 
= 
1 


XG;1 
+ 
XG;2 
+ 
XG;3 
= 
1 
[equality 
constraints 
are 
okay] 


Page 
2 
of 
19 



2. 
You 
are 
assisting 
Oliver 
to 
implement 
his 
LP 
model 
in 
a 
spreadsheet. 
Brie
y 
explain 
one 
objective 
of 
a 
good 
spreadsheet 
layout 
when 
implementing 
such 
a 
model. 
Page 
3 
of 
19 



Solution: 
See 
textbook 
section 
3.7 
for 
examples: 
communication, 
reliability, 
aud
itability, 
modiability; 
or 
any 
other 
sensible 
objective. 
Does 
not 
need 
to 
be 
formally 
named: 
e.g., 
\add 
comments 
to 
constraints” 
speaks 
to 
communication. 
Although 
it 
doesn't 
directly 
address 
the 
question 
asked, 
accept 
also 
any 
steps 
in 
spreadsheet 
implementation: 
data, 
variable 
cells, 
objective 
function, 
constraint 
LHS 
formula 
cells 
and 
RHS 
coecients. 


3. 
Oliver 
has 
entered 
into 
a 
sales 
agreement 
with 
the 
manufacturer 
of 
products 
D 
and 
E, 
and 
into 
a 
second 
sales 
agreement 
with 
the 
manufacturer 
of 
product 
B. 
His 
sales 
targets 
are 
100 
units 
of 
products 
D 
and 
E 
(in 
total) 
per 
month, 
and 
65 
units 
of 
product 
B 
per 
month, 
respectively. 
He 
receives 
a 
bonus 
if 
he 
reaches 
sales 
of 
100 
units 
of 
products 
D 
and 
E 
(otherwise 
no 
bonus 
for 
these 
products), 
and 
a 
separate 
bonus 
if 
he 
reaches 
65 
units 
of 
product 
B 
(otherwise 
no 
bonus 
for 
product 
B). 
Consider 
this 
part 
of 
the 
exercise 
to 
be 
independent 
and 
separate 
from 
part 
1. 
Write 
a 
goal 
programming 
LP 
formulation 
that 
models 
Oliver's 
two 
sales 
agreements. 
Dene 
all 
your 
variables 
and 
your 
objective 
function 
clearly. 


+ 


..- 


- 
=0 
[1]w 
= 
w 
+ 


+ 


- 


- 


+ 


+ 


+ 


+ 


+ 


Solution: 
Let 
Yi 
be 
the 
number 
of 
units 
of 
product 
i 
that 
Oliver 
sells 
per 
month 
on 
average 
[1]. 
Let 
di 
and 
di 
be 
deviational 
variables 
[1]. 
Let 
ti 
be 
sales 
targets. 


1 


min 
(wd- 
wd) 
[3]

i 
i 
ii

ti

i=B;DE 


s:t. 
YB 
+ 
dB 
- 
dB 
= 
tB 
= 
65 
[1] 
YD 
+ 
d+ 
- 
d+ 
YE 
= 
tDE 
= 
100 
[1]
DE 
E 


B 
DE 


Fine 
to 
have 
D 
and 
E 
combined 
or 
separately. 
Any 
GP 
objective 
function 
(weighted 
sum, 
weighted 
percentage 
deviation, 
minimax, 
etc) 
is 
acceptable. 
Min
us 
one 
mark 
for 
omitting 
wB 
= 
wDE 
= 
0. 


Page 
4 
of 
19 



Exercise 
2 


1. 
A 
gas 
distribution 
network 
is 
modelled 
by 
the 
following 
linear 
program, 
which 
has 
an 
objective 
function 
that 
describes 
the 
cost 
of 
gas 
shipment 
across 
the 
network. 
Let 
us 
call 
it 
model 
1. 
Draw 
the 
network 
that 
the 
LP 
models. 
min 
20XAD 
+ 
15XAE 
+ 
5XBA 
+ 
35XBE 
+ 
10XCD 
+ 
10XDE 
(1) 
s.t. 
XBA 
- 
XAD 
- 
XAE 
= 
25 
(2) 
- 
XBA 
- 
XBE 
= 
..40 
(3) 
- 
XCD 
= 
..30 
(4) 
XAD 
+ 
XCD 
- 
XDE 
= 
50 
(5) 
XAE 
+ 
XBE 
+ 
XDE 
= 
40 
(6) 
XBA 
= 
25, 
XDE 
= 
30, 
8i, 
j 
: 
Xij 
= 
0 
(7) 


Solution: 
Draw 
a 
graph 
with 
nodes: 
A,B,C,D,E 
[1] 


six 
edges 
[1]: 
AD 
weight 
20; 
AE 
weight 
15; 
BA 
weight 
5, 
bounds 
[0,25); 
BE 
weight 
35; 
CD 
weight 
10; 
DE 
weight 
10, 
bounds 
[0,30) 
[1 
point 
for 
each 
edge; 
no 
penalty 
if 
bounds 
omitted] 
supply: 
A 
+25, 
B 
-40, 
C 
-30, 
D 
+50, 
E 
+40 
[3] 


Page 
5 
of 
19 



2. 
Model 
1 
does 
not 
account 
for 
leakage 
from 
the 
pipes. 
An 
estimate 
is 
that 
10% 
of 
gas 

ow 
is 
lost 
along 
each 
pipe. 
Modify 
model 
1 
to 
account 
for 
this. 
Let 
us 
call 
this 
revised 
LP 
model 
2. 
Solution: 
Modify 
each 

ow 
constraint 
to 
have 
a 
factor 
of 
aij 
=0:9 
for 
all 
edges 
(i, 
j) 
[1]. 
Hence 
constraints 
for 
A, 
D, 
E 
change 
to 
have 
0.9 
in 
front 
of 
Xij 
terms 
that 
have 
positive 
sign 
— 
or 
any 
equivalent 
reformulation. 


[4 
marks 
for 
correct 
constraints, 
-1 
for 
each 
error. 
3 
marks 
for 
correct 
revised 
diagram 
but 
no 
revised 
constraints 
written 
out] 


3. 
Model 
1 
does 
not 
account 
for 
a 
regulatory 
condition: 
if 
any 

ow 
occurs 
out 
from 
node 
A, 
then 
the 
volume 
of 
out
ow 
from 
node 
A 
must 
be 
at 
least 
30 
units. 
Modify 
Page 
6 
of 
19 



model 
1 
to 
account 
for 
this. 
Let 
us 
call 
this 
revised 
LP 
model 
3. 


Solution: 
Add 
binary 
variable 
YA 
[1]. 
Add 
side 
constraints: 


30 
* 
YA 
= 
Xi 
= 
M 
* 
YA 
[2]


ows 
i 
from 
node 
A 


where 
M 
is 
a 
large 
constant 
(at 
least 
as 
large 
as 
upper 
bound 
on 
total 

ows 
from 
node 
A). 
[1] 


[1 
mark 
for 
XAD 
+ 
XAE 
= 
30] 


4. 
Which 
of 
models 
1, 
2, 
and 
3 
do 
you 
expect 
to 
have 
integral 
values 
for 
the 

ows, 
and 
Page 
7 
of 
19 



which 
do 
you 
not 
expect 
to 
have 
integral 
values 
for 
the 

ows? 
Justify 
your 
answer. 


Solution: 
Model 
1: 
yes, 
because 
network 

ow 
where 
lower 
and 
upper 
bound 
and 
supplies 
are 
all 
integer. 
[1] 
Model 
2: 
no, 
because 
generalized 
network 

ow. 
[1] 
Model 
3: 
no, 
because 
arbitrary 
IP. 
[1] 


Page 
8 
of 
19 



Exercise 
3 


A 
food 
component 
is 
manufactured 
by 
rening 
raw 
oils 
and 
blending 
them 
together. 
The 
raw 
oils 
come 
in 
two 
categories: 
vegetable 
oil 
(VEG1, 
VEG2) 
and 
non-vegetable 
oil 
(OIL1, 
OIL2, 
OIL3). 
The 
nal 
product 
sells 
at 
$180 
per 
ton. 
The 
prices 
for 
buying 
each 
oil 
are 
given 
below 
(in 
$/ton): 


OilVEG1VEG2OIL1OIL2OIL3
Price115128132109114
Vegetable 
oils 
and 
non-vegetable 
oils 
require 
dierent 
production 
lines 
for 
rening. 
It 
is 
not 
possible 
to 
rene 
more 
than 
210 
tons 
of 
vegetable 
oils 
and 
more 
than 
260 
tons 
of 
non-vegetable 
oils. 
There 
is 
no 
loss 
of 
weight 
in 
the 
rening 
process 
and 
the 
cost 
of 
rening 
may 
be 
ignored. 
There 
is 
a 
technical 
restriction 
relating 
to 
the 
acidity 
percentage 
of 
the 
nal 
product. 
The 
acidity 
percentage 
of 
the 
nal 
product 
must 
lie 
between 
3.5% 
and 
6.2%. 
It 
is 
assumed 
that 
the 
acidity 
percentage 
blends 
linearly 
and 
the 
acidity 
of 
the 
raw 
oils 
is 
as 
follows: 


Oil 


VEG1 
VEG2 
OIL1 
OIL2 
OIL3 


Acidity 


8.8% 
6.2% 
1.9% 
4.3% 
5.1% 


Your 
task 
is 
to 
determine 
what 
raw 
oils 
to 
buy 
and 
how 
to 
blend 
them 
so 
that 
the 
company 
maximizes 
its 
prot. 


1. 
Formulate 
the 
above 
problem 
as 
a 
linear 
program. 
Solution: 
Let 
xi 
be 
the 
number 
of 
tons 
of 
oil 
of 
type 
i 
used 
(i=1,...,5) 
[2] 


max180(x1+ 
x2+ 
x3+ 
x4+ 
x5) 
- 
115x1 
- 
128x2 
- 
132x3 
- 
109x4 
- 
114x5 
[3] 


s:t. 
x1+ 
x2 
= 
210 
x3+ 
x4+ 
x5 
= 
260 
(8:8x1+6:2x2+1:9x3+4:3x4+5:1x5)=(x1+ 
x2+ 
x3+ 
x4+ 
x5) 
= 
3:5 
(8:8x1+6:2x2+1:9x3+4:3x4+5:1x5)=(x1+ 
x2+ 
x3+ 
x4+ 
x5) 
= 
6:2 
xi 
= 
0 
[9 
points, 
2 
for 
each 
constraint 
and 
1 
point 
for 
non-negativity] 


Page 
9 
of 
19 



Page 
10 
of 
19 



2. 
The 
following 
extra 
conditions 
are 
imposed 
on 
the 
manufacturing 
problem 
stated 
above, 
as 
a 
result 
of 
the 
production 
process 
involved: 
• 
the 
nal 
product 
may 
never 
be 
made 
up 
of 
more 
than 
three 
raw 
oils 
• 
if 
either 
of 
VEG1 
or 
VEG2 
are 
used 
then 
OIL2 
must 
also 
be 
used 
• 
if 
OIL3 
is 
used 
then 
OIL2 
cannot 
be 
used 
Modify 
the 
LP 
model 
to 
account 
for 
these 
new 
extra 
conditions. 
Clearly 
dene 
any 
new 
variables 
you 
introduce. 


Solution: 
Let 
yi 
= 
1 
if 
we 
use 
any 
of 
oil 
i 
(i=1,...,5), 
0 
otherwise 
[4 
for 
new 
variables 
and 
linking 
constraints:] 


x1 
= 
210y1 
x2 
= 
210y2 
x3 
= 
260y3 
x4 
= 
260y4 
x5 
= 
260y5 


y1+ 
y2+ 
y3+ 
y4+ 
y5 
= 
3 
[2] 
y4 
= 
y1 
and 
y4 
= 
y2 
[2] 
y5+ 
y4 
= 
1 
[2] 


Page 
11 
of 
19 



Exercise 
4 


City 
Burger 
is 
a 
new 
chain 
of 
fast-food 
establishments 
planning 
to 
expand 
to 
suburban 
and 
downtown 
locations 
in 
northern 
Italy. 


The 
company 
has 
e 
27 
million 
available 
for 
the 
expansion. 
Each 
suburban 
location 
requires 
a 
e 
2 
million 
investment 
and 
each 
downtown 
location 
requires 
a 
e 
6 
million 
investment. 
Forecasts 
project 
that, 
after 
expenses, 
the 
net 
weekly 
prot 
generated 
by 
suburban 
locations 
will 
average 
e 
12,000 
per 
restaurant. 
The 
projections 
for 
downtown 
locations 
indicate 
that 
net 
weekly 
prots 
will 
average 
e 
20,000 
per 
restaurant. 


City 
Burger 
wishes 
to 
open 
at 
least 
two 
restaurants 
in 
downtown 
locations. 
The 
company 
currently 
employs 
19 
managers 
to 
run 
its 
restaurants. 
Each 
suburban 
location 
will 
require 
three 
managers, 
whereas 
the 
company 
feels 
it 
can 
get 
by 
with 
just 
one 
manager 
for 
each 
downtown 
location. 


1. 
Assuming 
fractional 
values 
are 
allowed, 
formulate 
a 
LP 
to 
determine 
how 
many 
restaurants 
City 
Burger 
should 
open 
in 
suburban 
and 
downtown 
locations 
in 
order 
to 
maximize 
its 
total 
weekly 
net 
prots. 
Solution: 
X1: 
number 
of 
suburban 
locations 
to 
open, 
X2: 
number 
of 
downtown 
locations 
[1] 


max12, 
000X1 
+ 
20, 
000X2 
[1] 


s:t. 
2X1+6X2 
= 
27 
[1] 
X2 
= 
2 
[1] 
3X1+ 
X2 
= 
19 
[1] 
X1;X2 
= 
0 
[1] 
Page 
12 
of 
19 



2. 
Solve 
graphically 
the 
model 
in 
part 
1 
and 
report 
the 
optimal 
solution. 
Solution: 
X1= 
5 
7/16 
and 
X2 
= 
2 
11/16. 
Optimal 
weekly 
prot 
= 
e 
119,000. 


[4 
points 
for 
the 
feasible 
region, 
2 
for 
the 
level 
curve, 
2 
for 
the 
optimal 
solution 
and 
2 
for 
the 
optimal 
prot] 


Page 
13 
of 
19 



Page 
14 
of 
19 



3. 
Find 
the 
optimal 
solution 
if 
the 
number 
of 
managers 
currently 
employed 
increases 
from 
19 
to 
21. 
What 
is 
the 
shadow 
price 
of 
the 
number 
of 
employees 
constraint? 
Solution: 
New 
optimal 
solution 
(graphically) 
is 
X1=6.18 
and 
X2=2.43, 
optimal 
prot=e 
123,000 
[2]. 
Shadow 
price=(123,000-119,000)/2= 
e 
2000 
[2] 


[For 
the 
second 
part: 
1 
mark 
for 
denition 
of 
SP 
only, 
no 
computation 
of 
its 
value] 


Now 
consider 
the 
integer 
linear 
program 
(ILP) 
that 
corresponds 
to 
the 
LP 
problem 
formulated 
in 
part 
1; 
let 
us 
refer 
to 
it 
as 
the 
ILP. 


4. 
Round 
up 
the 
optimal 
solution 
of 
the 
LP. 
Report 
whether 
the 
new 
solution 
is 
optimal 
Page 
15 
of 
19 



to 
the 
ILP. 
Explain. 


Solution: 
Round 
up 
we 
get 
X1=6, 
X2=3, 
which 
is 
infeasible. 
[2] 
(Rounding 
down, 
we 
get 
X1=5, 
X2=2 
which 
is 
feasible 
but 
not 
optimal.) 


5. 
Solve 
graphically 
for 
the 
optimal 
solution 
of 
the 
ILP. 
Solution: 
From 
the 
graph, 
(4,3) 
is 
the 
optimal 
integer 
solution 
[2], 
and 
optimal 
prot 
e 
108,000 
[2] 


Page 
16 
of 
19 



6. 
Now 
consider 
again 
the 
optimal 
solution 
of 
the 
LP 
and 
round 
it 
down. 
Report 
whether 
the 
new 
solution 
is 
optimal 
to 
the 
ILP. 
Calculate 
the 
resulting 
prot 
of 
the 
rounded 
solution. 
What 
do 
you 
conclude? 
Solution: 
Rounding 
down 
gives 
(5,2) 
and 
prot=e 
100,000 
[1]. 
While 
this 
is 
feasible 
for 
the 
ILP, 
it 
is 
not 
optimal 
[1]. 
We 
conclude 
that 
rounding 
will 
either 
give 
an 
infeasible 
or 
suboptimal 
solution. 
[1] 


7. 
After 
comparing 
the 
optimal 
solutions 
of 
the 
LP 
and 
ILP, 
could 
you 
nd 
an 
ILP 
Page 
17 
of 
19 



solution 
better 
than 
the 
LP 
solution? 
Justify 
your 
answer. 


Solution: 
The 
optimal 
solution 
of 
the 
relaxed 
LP 
is 
always 
better 
than 
that 
of 
the 
ILP. 


Page 
18 
of 
19 



8. 
Now 
suppose 
e 
28 
million 
is 
available 
for 
the 
expansion. 
Does 
the 
optimal 
ILP 
solution 
change? 
If 
so, 
what 
is 
the 
new 
integer 
solution? 
Solution: 
Yes, 
constraint 
shifts 
upward 
and 
new 
optimal 
integer 
solution 
is 
X1=5, 
X2=3 
[2]. 
Optimal 
prot 
= 
e 
120,000 
[1] 


Page 
19 
of 
19