Monday, June 18, 2012

Cost Minimization Problem


Problem Definition


On-site support and allocation is one of the critical activities in a software outsourcing companies. In order to continue the business with the clients, the company has to support the clinets even after developing and deplyoing the software at the customer site. So as a business strategy, the software companies are adding the onsite support in their project road map.
In most of the cases, the support has to be provided at the customer locations and hence a lot of travelling and allowances will be required.  So, reducing the travelling cost and allowance cost will be a major task for such type of companies for increase their revenue.
Here we will discuss an example in which a software outsourcing company is using “decision making techinique” to reduce the number of people to be allocated to each site in order to reduce the cost of onsite support.

Activities at the customer site are supported by Project Managers, Project Leader and Developers based on the requirement and criticality of the projects. So the company has to send diffent number of peoples to different sites.
In order to handle all the operations and activities, the customer locations are divided based on the regions like Asia Pacefic, Erupre, US, Africa-Middle East and Latin America. Based on the number of projects and number of customers in each region, the number of peoples is allocated. The people allocations are as follows:

Region
Min
Max
Asia Pacefic (AP)
100
300
Europe (EU)
170
300
United States (US)
20
100
Africa - Middle East (A-ME)
10
100
Latin America (LA)*
~
5

*Since there are no active projects in Latin America and company is trying to get new business in this reagion, the company is planned to send only Project Managers and decided to keep 5 Project Managers for this quarter.

When people are travelling to the customer sites, the company has to provide additional allowances to meet their extra expenses at the sites.Per day allowance for different kind of job profiles are different. In this case, the per-day allowance allocated by the company is as follows:

Designation
Project Manager
Project Leader
Developer
Allowance
$100
$75
$50



 To minimise the number of people to be allocated to different sites with minimal allowance cost.
  

Formulation


Minimise:           
$100 * PM + $75 * PL + $50 * Dev
Subject to:
1PM + 2PL + 4Dev >= 100
1PM + 2PL + 2Dev >= 170
1PM + 1PL + 1Dev >= 20
1PL + 1Dev >= 10
1PM = 5
1PM + 2PL + 4Dev <= 300
1PM + 2PL + 2Dev <= 300
1PM + 1PL + 1Dev <= 100
1PL + 1Dev <= 100
PM,PL,Dev >=0 (Non negativity)



Solution



Project Manager
Project Leader
Developer



Cost Per Day
$100
$75
$50



Number of People
5
17.5
65
5062.5









Constraints






AP Min
1
2
4
300
>=
100
EU Min
1
2
2
170
>=
170
US Min
1
1
1
87.5
>=
20
A-ME Min
0
1
1
82.5
>=
10
LA Min
1
0
0
5
=
5
AP Max
1
2
4
300
<=
300
EU Max
1
2
2
170
<=
300
US Max
1
1
1
87.5
<=
100
A-ME Max
0
1
1
82.5
<=
100




LHS
Sign
RHS

Answer Report

Target Cell (Min)





Cell
Name
Original Value
Final Value



$F$6

5062.5
5062.5
















Adjustable Cells





Cell
Name
Original Value
Final Value



$C$6
PM
5
5



$D$6
PL
17.5
17.5



$E$6
Deve
65
65
















Constraints





Cell
Name
Cell Value
Formula
Status
Slack

$F$9
AP Min
300
$F$9>=$H$9
Not Binding
200

$F$10
EU Min
170
$F$10>=$H$10
Binding
0

$F$11
US Min
87.5
$F$11>=$H$11
Not Binding
67.5

$F$12
A-ME Min
82.5
$F$12>=$H$12
Not Binding
72.5

$F$13
LA Min
5
$F$13=$H$13
Not Binding
0

$F$14
AP Max
300
$F$14<=$H$14
Binding
0

$F$15
EU Max
170
$F$15<=$H$15
Not Binding
130

$F$16
US Max
87.5
$F$16<=$H$16
Not Binding
12.5

$F$17
A-ME Max
82.5
$F$17<=$H$17
Not Binding
17.5

Sensitivity Report

Adjustable Cells








Final
Reduced
Objective
Allowable
Allowable

Cell
Name
Value
Cost
Coefficient
Increase
Decrease

$C$6
PM
5
0
100
1E+30
1E+30

$D$6
PL
17.5
0
75
1E+30
25

$E$6
Deve
65
0
50
25
1E+30








Constraints








Final
Shadow
Constraint
Allowable
Allowable

Cell
Name
Value
Price
R.H. Side
Increase
Decrease

$F$9
AP Min
300
0
100
200
1E+30

$F$10
EU Min
170
50
170
25
17.5

$F$11
US Min
87.5
0
20
67.5
1E+30

$F$12
A-ME Min
82.5
0
10
72.5
1E+30

$F$13
LA Min
5
62.5
5
25
5

$F$14
AP Max
300
-12.5
300
35
130

$F$15
EU Max
170
0
300
1E+30
130

$F$16
US Max
87.5
0
100
1E+30
12.5

$F$17
A-ME Max
82.5
0
100
1E+30
17.5


Interpreting the Result

The optimal solution is found to be 5 Project Managers, 17.5 Project Leaders and 65 Developers. With this numbers, the total onsite allowance expenditure can be minimised to $5062.5. As the number of Project Leaders is turned out to have a fractional value, the number will be rounding up to 18 as adding one additional Project Leader will not change the optimal solution.


Answer Report Analysis

From the report, the final value of the objective function is $5062.5 and the final values of the decision variables are 5 for Project Managers, 17.5 for Project Leaders and 65 for Developers.

Status and Slack of Constraints

Out of the nine constraints, EU Min and AP Max are binding and hence don’t have any slack. For LA Min the slack is seems to be zero eventhough the constraints are not binding. This is because of the sign of the constraint. A binding constraint, which is satisfied with equality, will always have a slack of zero.
In an answer report, a slack value shows the difference between the final value and the lower or upper bound imposed by that constraint. In other words, the slack value gives the number persons un-used and which can be used without changing the final optimal solution. In our case, the slack values of different constraints are as follows:

Constraints
Final Value
Slack
Status
AP Min
300
200
Not Binding
EU Min
170
0
Binding
US Min
87.5
67.5
Not Binding
A-ME Min
82.5
72.5
Not Binding
LA Min
5
0
Not Binding
AP Max
300
0
Binding
EU Max
170
130
Not Binding
US Max
87.5
12.5
Not Binding
A-ME Max
82.5
17.5
Not Binding

From the above report, we can get the slack values of each constraint. For AP Min, the slack value is 200 and it can be used up without changing the final optimal solution. Similarly, for the other constraints we can increase the number of people without any change in final solution.


Sensitivity Report Analysis

Objective Coefficient

Objective coefficient of Project Manager, Project Leader and Developer are $100, $75 and $50 respectively. The optimal solution will remain same if the objective coefficient of Project Manager is changed from $100 - (1E+30) to $100 + (1E+30). Similarly for Prject Leaders and Developers, the range of allowable increase and allowable decrease are $75 + (1E+30), $75 - 25 and $50 + 25, $50 - (1E+30) respetively without changing the optimal solution.



The range of optimality for the function coeficients are:


Range of Optimality
Objective Coefficinet
Min
Max
Poject Manager
-∞
Project Leader
50
Developer
75
-∞

Reduced Cost

The reduced cost of a variable is the smallest change in the objective function coefficient needed to arrive at a solution in which the variable takes on a positive value when you solve the problem. In other words, the reduced cost in the objective function coefficient of the original variable and in this case since all the variables are basic at optimum, the objective function coeficnet are zero.

Constraint R.H. Side

The range of feasibility associated with the RHS of a constraint is the range of values within which we can vary the RHS without changing the set of constraints that are binding at the optimal solution.
To determine the binding constraints at the current solution we compare the Final Value (LHS) of a constraint to its RHS.  For the current solution, EU Min and AP Max are binding, rest all are non binding. From the report we can see the allowable incerease and allowable decrease of RHS of each constraint. And, the optimal solution will not change if the RHS of these constraints vary within those ranges.
The range feasibility of RHS of constraints is:

Name
Constraint RH Side
Allowable Range
Status
Max
Min
AP Min
100
300
-
Not Binding
EU Min
170
175
152.5
Binding
US Min
20
87.5
-
Not Binding
A-ME Min
10
82.5
-
Not Binding
LA Min
5
30
0
Not Binding
AP Max
300
335
170
Binding
EU Max
300
170
Not Binding
US Max
100
87.5
Not Binding
A-ME Max
100
82.5
Not Binding



Shadow Price of Constraints

Shadow Price is the magnitude of the change in objective function value for a unit increase in RHS of a constraint.
From the report, we could see that the shadow prices of most of the constrainsts are 0. That means, if we increase or decrease the slack of those contraints within the allowable range, there will not be any impact on the final cost of the problem.
For EU Min, the shadow price is $50. That means any unit increasein the RHS of this constraint upto 195 (170+25) will increase the profit by $50 and any unit decrease upto 152.5 (170-17.5) will decrease the cost by $50. Similary for LA Min, the shadow price is $62.5. That means any unit change in the RHS of LA Min within the allowable rage (30, 0) will affect the cost by $62.5.
In case of AP Max, the shadow price is a negative value. So, any increase in the corresponding slack variable results in a decreased cost. i.e; a unit increase in the AP Max slack upto 335 will decrease the total cost by -$12.5. Likewise the total cost will increase by $12.5 for each unit decrease upto 170.
The validity range of shadow price is follows:

Name
Shadow Price
Allowable Range
Max
Min
AP Min
0
300
-
EU Min
50
175
152.5
US Min
0
87.5
-
A-ME Min
0
82.5
-
LA Min
62.5
30
0
AP Max
-12.5
335
170
EU Max
0
170
US Max
0
87.5
A-ME Max
0
82.5

Alternate Optimal Solution

For this current optimal solution, there are no alternate solutions possible since the allowable increase or allowable decrease is non-zero values. There is no solution possible by ignoring any of the variables and hence this solution is unique.