Solution Problem A.

1. Decision Variables:
P = Number of Laptops to be allocated to Production dept (units = no. of Laptops)
M = Number of Laptops to be allocated to Marketing dept (units = no. of Laptops)
F = Number of Laptops to be allocated to Finance dept (units = no. of Laptops)
2. Objective function:
Maximize Z = 0.05*P+0.04*M+0.02*F (Allocate the new laptops so as to maximize
the total percent increase in productivity)
3. Constraints:
P+M+F = 23 (All of the new Laptops must be allocated)
M ≥ 4 (Marketing must get at least 4 Laptops)
P ≥ 4 (Production must get at least 4 Laptops)
F ≥ 5 (Finance must get at least 5 Laptops)
F ≥ 0.5*P (Finance must get at least half of Laptops given to Production dept)
F ≥ 0.5*M (Finance must get at least half of Laptops given to Marketing dept)
P ≥ 4+M (Production is adamant about getting at least four more of laptops than
Marketing dept)
M ≤ 0.5*P + 0.5*F (Marketing must not get more than half of all laptops given to
both Production and Finance depts)
P ≥ 0 (Non-Negativity)
M ≥ 0 (Non-Negativity)
F ≥ 0 (Non-Negativity)
4. From step 1 to 3, it is evident from objective function and all constraints that it is
Linear Program.
5. It is an Integer Linear Programming problem, because number of Laptops allocation
cannot be in fraction.

1|Page
6. Lingo Input:

Lingo Output:

2|Page
7. The best allocation of 23 new Laptops is allocating 12 Laptops to Production Dept, 5
Laptops to Marketing Dept and 6 Laptops to Finance Dept in order to increase the
productivity about 92%.
8. The slack and surplus involved in optimal solution is 0.92 which is showing that the total
productivity increase by these allocations is 92%. In Row 3 it is showing surplus of 1 in
constraint 2 (M ≥ 4) as M is decided to be 5. Similarly, in Row 4 it is showing surplus of 8
in constraint 3 (P ≥ 4) as P is decided to be 12. In Row 7 it is showing surplus of 3.5 in
constraint 6 (F ≥ 0.5*M) as F is 6 and 0.5*M is 5. In Row 8 it is showing surplus of 3 in

3|Page
 constraint 7 (P ≥ 4+M) as P is 12 and 4+M = 9. In Row 9 it is showing slack of 4 in
Constraint 8 (M ≤ 0.5*P + 0.5*F) which is (5≤6+3). In Row 10,11,12 these slack or surplus
are actual allocation values of P,M and F respectively subjected to Non-Negativity
Constraints.
9. To determine the ranges of optimality on the productivity gain per new laptop for
each department, we need to formulate objective function manually for the solved
values of allocation in each department.
Z = 0.05*P+0.04*M+0.02*F
Z = 0.05*12+0.04*5+0.02*6
Therefore, the range of optimality for each department is as follows:
Production department: 0.05*12 = 0.6 or 60%
Marketing department: 0.04*5 = 0.2 or 20%
Finance department: 0.02*6 = 0.12 or 12%
This means that for every new laptop allocated to the Production department, the
productivity gain per laptop should be at least 5% and maximum 60%. Similarly, for
the Marketing department, the productivity gain per laptop should be at least 4% and
maximum 20%, and for the Finance department, the productivity gain per laptop
should be at least 2% and maximum 12%, to be considered optimal.
10. The specific methodology used to solve the given problem is mixed integer linear
programming (MILP).

4|Page
Solution Problem B.
11. Decision Variables:

According to transshipment diagram we define the following 12 decision variables Xij

all with the units of (number of components shipped from node i to node j).
X13, X14, X23, X24, X34, X35, X36, X37, X43, X45, X46, X47
where, Manhattan = 1, Atlanta = 2, Philadelphia = 3, Knoxville = 4, Memphis = 5,
New Orleans = 6, El Paso = 7
12. Objective function:
Minimize Z = 3*X13 + 2*X14 + 2*X23 + 3*X24 + 2*X34 + 4*X35 + 4*X36 + 4*X37 +
2*X43 + 3*X45 + 2*X46 + 2*X47
(ship all the components in order to minimize total shipping cost)
13. Constraints:
X13 + X14 ≤ 900 (Total number of components supplied from node 1 to node 3 and 4
must not exceed 900)
X23 + X24 ≤ 900 (Total number of components supplied from node 2 to node 3 and 4
must not exceed 900)
X13 + X23 + X43 = X34 + X35 + X36 + X37 (Total number of components entering to node
3 must be equal to components leaving node 3)
X14 + X24 + X34 = X43 + X45 + X46 + X47 (Total number of components entering to node
3 must be equal to components leaving node 3)
X35 + X45 ≥ 450 (Demand at node 5 is 450 must be fulfilled)
X36 + X46 ≥ 500 (Demand at node 6 is 500 must be fulfilled)
5|Page
 X37 + X47 ≥ 620 (Demand at node 7 is 620 must be fulfilled)
All non-negativity constraints:
X13 ≥ 0
X14 ≥ 0
X23 ≥ 0
X24 ≥ 0
X34 ≥ 0
X35 ≥ 0
X36 ≥ 0
X37 ≥ 0
X43 ≥ 0
X45 ≥ 0
X46 ≥ 0
X47 ≥ 0
14. From step 11 to 13, it is evident from objective function and all constraints that it is
Linear Program.
15. It is a Transshipment Linear Programming problem, because number of components
are being transported from node 1,2 and there are two transshipment nodes 3,4 from
where then the components are supplied to node 5,6,7.
16. a. It is an unbalanced problem
b. Keeping in view the transshipment nodes 3,4 the left side has total of 1800
components coming 900 each from node 1 and 2 while in right side the node 5 has
capacity of 450, node 6 with 500 and node 7 with 620 components capacity. There is
overall capacity of 1570 components.

6|Page
17. a. Lingo Input:

b. Lingo Output:

7|Page
18. The routes which are used in our solution are: X14, X24, X45, X46, X47.
19.
8|Page
 Units Shipped Cost of shipment ($)
X14 = 900 900*2 =1800
X24 = 670 670*3 =2010
X45 = 450 450*3 =1350
X46 = 500 500*2 =1000
X47 = 620 620*2 =1240
20. Total cost of shipping = 1800+2010+1350+1000+1240 = $7400
21. a. In row 3 there is slack of 230 components in constraint 2 (X23 + X24 ≤ 900) where
X24 = 670 and X23 = 0. In row 10,12,18,19,20 there is surplus of 900,670,450,500,620
components showing the exact values of X14, X24, X45, X46, X47 respectively for the
non-negativity constraints.
b. All demands have satisfied.
22. Numerical values of each and every slack represents in specific context of problem:

Numerical values of Interpretation

Units shipped
X14 = 900 From node 1 to node 4, 900
components are shipped
X24 = 670 From node 2 to node 4, 670
components are shipped
X45 = 450 From node 4 to node 5, 450
components are shipped
X46 = 500 From node 4 to node 6, 500
components are shipped
X47 = 620 From node 4 to node 7, 620
components are shipped

9|Page
Solution Problem C.
23. Given problem is a type of network flow problem specifically called shortest path
problem.
24. a. Starting from node 1 we have three paths ahead (Note: The figures are not drawn to
scale):

b. The shortest path of them was to join node 1 with node 3 as following:

c. Then the shortest available path is to join node 3 with node 7 as following:

d. Then the shortest available path is to join node 7 with node 6 as following:

10 | P a g e
e. Then the shortest available path is to join node 1 with node 2 as following:

f. Then the shortest available path is to join node 6 with node 5 as following:

g. Then the shortest available path is to join node 5 with node 4 as following:

11 | P a g e
h. Then the shortest available path is to join node 7 with node 8 as following:

i. Then the shortest available path is to join node 8 with node 9 as following:

12 | P a g e
25. The final network diagram showing only the routes selected is with a total length of
20-meter cable to join all 9 computers:

26. Given problem is a type of network flow problem specifically called shortest path
problem.
27. a. Considering node 1 is the server that we have to connect with all other PCs, then
we have three direct possible paths ahead:(Note: The figures are not drawn to scale)

b. The shortest and unique path of them was to join node 1 with node 3 as following:

c. Then the shortest and unique available path is to join node 3 with node 7 as
following:

13 | P a g e
d. Then the shortest and unique available path is to join node 7 with node 6 as
following:

e. Then the shortest and unique available path is to join node 1 with node 2 as
following:

f. Then the shortest and unique available path is to join node 6 with node 5 as
following:

14 | P a g e
g. Then the shortest and unique available path is to join node 5 with node 4 as
following:

h. Then the shortest and unique available path is to join node 7 with node 8 as
following:

i. Then the shortest and unique available path is to join node 8 with node 9 as
following:

15 | P a g e
28. The final network diagram showing only the routes selected is with a total length of
20-meter cable to join all 9 computers:

16 | P a g e