HARAMAYA UNIVERSITY

COLLEGE OF BUSINESS AND

ECONOMICS
DEPARTMENT OF ECONOMICS
Program Energy Economics
Assignment Of Decision Modeling
Summitted BY:- EBISA DIRIBI
ID No/ 937 /13
Summitted TO :-DR.GEMECHU MULATU

November 12/2021
Haramaya university
1. Write short notes on steps on Decision Modelling
Solution
1. Formulation
Translating a problem scenario from words to a mathematical model
2. Solution
Solving the model to obtain the optimal solution
3. Interpretation and Sensitivity Analysis
Analyzing results and implementing a solution
2, Discuss Assumptions of Linear Programming problem
Solution;
1. 1 Proportionality. - The contribution of each decision variable to the objective or
constraint is directly proportional to the value of the decision variable.
2. Additivity. - The contribution to the objective function or constraint for any variable is
independent of the values of the other decision variables, and the terms can be added
together sensibly.
3. Divisibility. - The decision variables are continuous and thus can take on fractional
values.
4. Deterministic. - All the parameters (objective function coefficients, right-hand side
coefficients, left-hand side, or technology, coefficients) are known with certainty.
3. Find solution using Simplex method
MAX Z = 5x1 + 7x2
subject to
x1 <= 6
2x1 + 3x2 <= 19
x1 + x2 <= 8
and x1,x2 >= 0
Solution: Problem is
The problem is converted to canonical form by adding slack, surplus and artificial variables as
appropiate
1. As the constraint-1 is of type '≤' we should add slack variable S1
2. As the constraint-2 is of type '≤' we should add slack variable S2
3. As the constraint-3 is of type '≤' we should add slack variable S3
After introducing slack variables
Max Z

x x S S S
= 5+ 7 + 0 + 0 + 0
1 2 1 2 3
subject to
x1 + S1 =6
2x1 + 3 x2 + S2 = 19
x1 + x2 + S3 = 8
and x1,x2,S1,S2,S3≥0
 Iteration-1 Cj 5 7 0 0 0

MinRatio
B CB XB x1 x2 S1 S2 S3
XBx2

S1 0 6 1 0 1 0 0 ---

S2 0 19 2 (3) 0 1 0 193=6.3333→

S3 0 8 1 1 0 0 1 81=8

Z=0 Zj 0 0 0 0 0

Zj-Cj -5 -7↑ 0 0 0
Negative minimum Zj-Cj is -7 and its column index is 2. So, the entering variable is x2.
Minimum ratio is 6.3333 and its row index is 2. So, the leaving basis variable is S2.
∴ The pivot element is 3.
Entering =x2, Departing =S2, Key Element =3
R2(new)=R2(old)÷3
R1(new)=R1(old)
R3(new)=R3(old) - R2(new)

Iteration-2 Cj 5 7 0 0 0

B CB XB x1 x2 S1 S2 S3 MinRatio

S1 0 6 1 0 1 0 0 61=6

x2 7 6.3333 0.6667 1 0 0.3333 0 6.33330.6667=9.5

S3 0 1.6667 (0.3333) 0 0 -0.3333 1 1.66670.3333=5→

Z=44.3333 Zj 4.6667 7 0 2.3333 0

Zj-Cj -0.3333↑ 0 0 2.3333 0

Negative minimum Zj-Cj is -0.3333 and its column index is 1. So, the entering variable
is x1.
Minimum ratio is 5 and its row index is 3. So, the leaving basis variable is S3.
 ∴ The pivot element is 0.3333.
Entering =x1, Departing =S3, Key Element =0.3333
R3(new)=R3(old)÷0.3333
R1(new)=R1(old) - R3(new)
R2(new)=R2(old) - 0.6667R3(new)

Iteration-3 Cj 5 7 0 0 0
 B CB XB x1 x2 S1 S2 S3 MinRatio

S1 0 1 0 0 1 1 -3

x2 7 3 0 1 0 1 -2

x1 5 5 1 0 0 -1 3

Z=46 Zj 5 7 0 2 1

Zj-Cj 0 0 0 2 1
Since all Zj-Cj≥0
Hence, optimal solution is arrived with value of variables as :
x1=5,x2=3
Max Z=46
B. Find solution using graphical method
MAX Z = 5x1 + 7x2
subject to
x1 <= 6
2x1 + 3x2 <= 19
x1 + x2 <= 8
and x1,x2 >= 0
Solution: Problem is
Max zx

x x
= 5+ 7
1 2
subject to
x1 ≤6
2x1 + 3 x2 ≤ 19
x1 + x2 ≤ 8
and x1,x2≥0;
1. To draw constraint x1≤6→(1),  x1=6
Here line is parallel to Y-axis, X1= (6,6), X2= (0, 1)
2. To draw constraint 2x1+3x2≤19→(2)

Treat it as 2x1+3x2=19, When x1=0 then x2=?

⇒2(0)+3x2=19, ⇒3x2=19, ⇒x2=193=6.33

When x2=0 then x1=? ⇒2x1+3(0)=19, ⇒2x1=19, ⇒x1=192=9.5, X1 = (0,9.5), X2 =
(6.33, 0)

3. To draw constraint x1+x2≤8→(3), x1+x2=8

When x1=0 then x2=? ⇒(0)+x2=8 ⇒x2=8, When x2=0 then x1=? ⇒x1+(0)=8 ⇒x1=8, X1

= (0, 8), X2 = ( 8, 0)

The value of the objective function at each of these extreme points is as follows:
Extreme Point
Objective function value
Coordinates Lines through Extreme Point
Z=5x1+7x2
(x1,x2)
O(0,0) 4→x1≥0 5(0)+7(0)=0
 5→x2≥0
1→x1≤6
A(6,0) 5(6)+7(0)=30
5→x2≥0
1→x1≤6
B(6,2) 5(6)+7(2)=44
3→x1+x2≤8
2→2x1+3x2≤19
C(5,3) 5(5)+7(3)=46
3→x1+x2≤8
2→2x1+3x2≤19
D(0,6.33) 5(0)+7(6.33)=44.33
4→x1≥0

The maximum value of the objective function Z=46 occurs at the extreme point (5,3).

Hence, the optimal solution to the given LP problem is : x1=5,x2=3 and max Z=46
C. Verify your answer using solver table on excel
MAX X1 X2      
DV 5 3 46    
OBJ 5 7 46 LHS RHS
CONST1 1 0   5 6
CONSTR2 2 3   19 19
CONST 3 1 1   8 8

4. Maximize Z = 5X1 + 2X2 +X3

Subject to; x1 +3x2 – x3 <= 6
X2 +x3 <= 4
3x1 +x2 <= 7
X1, x2, x3>= 0
Find solution using dual-simplex method
MAX Z = 5x1 + 2x2 + x3
subject to
x1 + 3x2 - x3 <= 6
x2 + x3 <= 4
3x1 + x2 <= 7
and x1,x2,x3 >= 0
Solution: Problem is
Max Z

x x x
= 5+ 2 +
1 2 3
subject to
x1 + 3 x2 - x3 ≤ 6
x2 + x3 ≤ 4
3x1 + x2 ≤7
and x1,x2,x3≥0;

The problem is converted to canonical form by adding slack, surplus and artificial
variables as appropriate
The problem is converted to canonical form by adding slack, surplus and artificial variables as
appropiate
1. As the constraint-1 is of type '≤' we should add slack variable S1
2. As the constraint-2 is of type '≤' we should add slack variable S2
3. As the constraint-3 is of type '≤' we should add slack variable S3
After introducing slack variables
Max Z

x x x S S S
= 5+ 2 + + 0 + 0 + 0
1 2 3 1 2 3
subject to
x1 + 3 x2 - x3 + S1 =6
x2 + x3 + S2 =4
3x1 + x2 + S3 = 7
and x1,x2,x3,S1,S2,S3≥0

Iteration-1 Cj 5 2 1 0 0 0

B CB x1 x2 x3 S1 S2 S3 RHS Ratio

0 S1 1 3 -1 1 0 0 6 ----

0 S2 0 1 1 0 1 0 4 -----

0 S3 3 1 0 0 0 1 7 -----

Z=0 Zj 0 0 0 0 0 0

Cj-Zj 5 2 1 0 0 0

Here not all Zj-Cj≥0. (BecauseZ1-C1=-5)

Solution using Simplex method
MAX Z = 5x1 + 2x2 + x3
subject to
x1 + 3x2 - x3 <= 6
x2 + x3 <= 4
3x1 + x2 <= 7
and x1,x2,x3 >= 0
The problem is converted to canonical form by adding slack, surplus and artificial variables as
appropiate
1. As the constraint-1 is of type '≤' we should add slack variable S1
2. As the constraint-2 is of type '≤' we should add slack variable S2
3. As the constraint-3 is of type '≤' we should add slack variable S3
After introducing slack variables
Max Z = 5x1 + 2x2 + x3 + 0S1 + 0S2 + 0S3
Subject to
X1 + 3x2 - x3 + S1 =6
X2 + x3 + S2 = 4
3x1 + x2 + S3 =7
X1, x2, x3, S1, S2, and S3 ≥0
Iteration-1
Cj 5 2 1 0 0 0
BV x1 x2 x3 S1 S2 S3 RHS MinRatio
0 S1 1 3 -1 1 0 0 6 6/1 = 6
0 S2 0 1 1 0 1 0 4 4/0 = ----
0 S3 (3) 1 0 0 0 1 7 7/3 =2.3333→
Zj 0 0 0 0 0 0
Cj-Zj 5↑ 2 1 0 0 0
Negative minimum Zj-Cj is -5 and its column index is 1. So, the entering variable is x1.
Minimum ratio is 2.3333 and its row index is 3. So, the leaving basis variable is S3.
∴ The pivot element is 3.
Entering =x1, Departing =S3, Key Element =3
Iteration-2
Cj
Bv X1 X2 X3 S1 S2 S3 RHS Ratio
0 S1 0 11/3 0 1 1 -1/3 11/3
0 S2 0 1 1 0 1 0 4
5 X1 1 1/3 0 0 0 1/3 7/3
Zj 5 5/3 1 0 1 5/3 47/3
Cj-Zj 0 1/3 0 0 -1 -5/3
Negative minimum Zj-Cj is -1 and its column index is 3. So, the entering variable is x3.
Minimum ratio is 4 and its row index is 2. So, the leaving basis variable is S2.
∴ The pivot element is 1.
Entering =x3, Departing =S2, Key Element =1
Iteration-3
Cj 5 2 1 0 0 0
B CB x1 x2 x3 S1 S2 S3 MinRatio
0 S1 7.6667 0 3.6667 0 1 1 -0.3333
1 x3 4 0 1 1 0 1 0 -----
5 x1 2.3333 1 0.3333 0 0 0 0.3333
Zj 5 2.6667 1 0 1 1.6667
Zj-Cj 0 0.6667 0 0 1 1.6667
Since all Zj-Cj≥0
Hence, optimal solution is arrived with value of variables as :
x1=2.3333,x2=0,x3=4
Max Z = 15.6667
5. Solve Linear Programming Problem Min Z = 25X1 + 30X2
St: 20X1 + 15X2 >= 100
2X1 + 3X2 >= 15
X1, X2>=0

a. Use graphical method

b. Use simplex method and verify your answer
c. Use big M-method and verify your answer
d. Use excel solver table and verify your answer
Solution
a. Graphical method
Solve the Linear programming problem using graphical method
Min Z = 25x1 + 30x2
Subject to:
20x1 + 15x2 >= 100
2x1 + 3x2 >= 15, X1, x2 >= 0
1. To draw constraint 20x1 + 15x2 ≥ 100→ Constr (1)
20x1 + 15x2=100, When x1=0 then x2=? ⇒2 0 (0) + 15x2=100 , ⇒ 15x2 = 100 ⇒
X2 =100/15 = 6.67,
When x2=0 then x1=? ⇒ 20x1+15(0) =100, ⇒ 20x1=100 ⇒
X1=100/20 =5, X1= (0, 5), x2= (6.67, 0)
2. To draw constraint 2x1 + 3x2 ≥ 15→ (2)
Treat it as 2x1 + 3x2 = 15
When x1=0 then x2=? ⇒ 2(0) + 3x2 = 15, ⇒ 3x2 = 15, ⇒ X2 = 15/3 = 5
When x2=0 then x1=? ⇒ 2x1 + 3(0) = 15, ⇒ 2x1 = 15, ⇒ X1 = 15/2 =7.5
X1 = (0, 7.5), X2 = (5, 0)
The value of the objective function at each of these extreme points is as follows:
Corner Point Lines through Extreme Point Objective function value
Z = 25X1 + 30X2
A (0, 6.67) 20x1+15x2≥100 25(0) +30(6.67) =200
B (2.5, 3.33) 20x1+15x2≥100 25(2.5) +30(3.33) =162.5
C (7.5, 0) 2x1+3x2≥15 25(7.5) +30(0) =187.5
The minimum value of the obje function Z=162.5 occurs at the extreme point (2.5, 3.33).
Hence, the optimal solutio to the given LP problem is: x1=2.5, x2=3.33 and min Z=162.5.
B. Solution for B-M Method
Min Z =25x1 + 30x2 + 0S1 + 0S2 + M A1 + MA2
Subject to:
20x1 + 15x2 - S1 + A1 = 100
2x1 + 3x2 - S2+ A2 = 15
X1, x2, S1, S2, A1, and A2 ≥ 0
Iteration-1
Cj 25 30 0 0 M M
B CB x1 x2 S1 S2 A1 A2 RHS MinRatio
A1 M (20) 15 -1 0 1 0 100 100/20 =5→
A2 M 2 3 0 -1 0 1 15 15/2 =7.5
Zj 115M 22M 18M -M -M M M
Cj- Zj 22M-25↑ 18M-30 -M -M 0 0
Positive maximum Zj-Cj is 22M-25 and column index is 1. So, the entering variable is x1.
R1 (New) = R1 (Old /20)
R2 (New) = R2 Old – 2R1 (New)
Iteration 2
Cj 25 30 0 0 M
BV X1 X2 S1 S2 A1 RHS Ratio
25 X1 1 -0.75 -0.05 0 0 5 5/0.75=6.67
M A1 0 (1.5) 0.1 -1 1 5 5/1.5=3.33
ZJ 25 1.5M+18.75 0.1M -M M
-1.25
CJ- 0 11.25-1.5M 1.25- -M 0
ZJ 0.1M

Posive Maximum CJ –ZJ = 11.25-1.5M and its column index is 2 so the intering variable is x2
The minmum ratio is 3.33
The pivot element is 1.5
Iteration 3
CJ
BV X1 X2 S1 S2 RHS
25 X1 1 0 -0.1 0.5 25
30 X2 0 1 0.66 -0.667 30
7
ZJ 25 30 -0.5 -7.5
CJ-ZJ 0 0 -0.5 -7.5
Since all cj - zj <= 0
Hence optimal solution is arrived with value of variable as x1= 2.5, x2 = 3.33
MIN Z = 162.5
C. Find simlex exell method
 min x1 x2      
decision variable 2.5 3.333333 162.5    
objective 25 30 162.5 LHS RHS
constrain1 20 15   100 100
constraint 2 2 3   15 15

6. A firm makes two types of furniture chairs and tables. The contribution for each product to
objective function is birr 20 per chair and birr 30 per table respectively. Both products are
processed on three Machines M1, M2 and M3. The time required (in hours) by each product and
total time available per week on each machine are as follows:
Machine Chair Table Available time
M1 3 3 36
M2 5 2 50
M3 2 6 60
How should the manufacturer schedule his production in order to maximize contribution?
Solution
✓ For M1= Total Possible in one week
36 ÷ 3 = 12
Total table possible in one week
36 ÷ 3 = 12
Total Profit per week
12 × 20 +12 × 30 = 600
✓ For M2
Total chairs possible in one week
50 ÷ 5 = 10
Total table possible in one week
50 ÷ 2 = 25
Total Profit per week
10 × 20 + 25 × 30 = 950
✓ For M3
Total chair possible in one week
60 ÷ 2 = 30
Total table possible in one week
60 ÷ 2 = 30
Total table possible in one week
60 ÷ 6 = 10
Total profit per week
30 × 20 + 10 × 30 = 900
Their fore manufacture used M2 for maximized contribution
7. Consider the transportation problem having the following parameter table:
Destination Supply
1 2
Source 1 8 5 4
2 6 4 2
Demand 3 4
North-West Corner (NWC) Method, Least Cost Method (LCM), and Vogel’s Approximation (or
penalty) Method (VAM, obtain the initial basic feasible solution and show the corresponding
total transportation cost.
Solution North-West Corner (NWC) Method,
Step 1
Destination
D1 D2 Supply
S1 8 (3) 5 (1) 4 1 0
S2 6 4 2
Ddummy 0 0 1

Demand 3 0 4 3

TC = 8 × 3 + 5 ×1 + 4 × 2 + 0 ×1 = 37
Find the least Cost Method
D1 D2 Supply
S1 8 (2) 5 (2) 4
S2 6 4 (2) 2

Ddummy 0 (1) 0 1
Demand 3 4

Vogel Approximation method or Penality

D1 D2 Supply Row Penality
S1 8 5 4 3 3--
S2 6 (2) 4 2 2 ---
Ddummy 0 (1) 0 1
Demand 3 4
Column 6 4
Penality -
Allocations in the original problem
D1 D2 Supply
S1 8(3) 5(1) 4
S2 6 4(2) 2
Ddummy 0 0(1) 1
Demand 3 4
The maximum profit =8×3+5×1+4×2+0×1=37
Here, the number of allocated cells = 4 is equal to m + n - 1 = 3 + 2 - 1 = 4
Total Minimization Cost is = 2 × 8 + 5×2 + 4 × 2 + 0 × 1 = 34
Reformulate this problem as a general linear programming problem.
Problem is Maximization, so convert it to minimization by subtracting all the elements from max
element
D1 D2 Supply
S1 0 3 4
S2 2 4 2
Ddummy 0 0 1
Demand 3 4
Table-1
 D1 D2 Supply Row Penalty
S1 0 3 4 3=3-0
S2 2 4 2 2=4-2
Sdummy 0 0 1 0
Demand 3 4
Column Penalty 2=2-0 1=4-3

Initial feasible solution is

D1 D2 Supply Row Penalty
S1 0(3) 3(1) 4 3| 3| 3| 3|
S2 2 4(2) 2 2 | 4 | 4 | -- |
Sdummy 8 8(1) 1 0 | 8 | -- | -- |
Demand 3 4
Colm Penlty 2 1
-- 1
-- 1
-- 1
3
Initial feasible solution is
The maximum penalty, 3, occurs in row S1.
The minimum cij in this row is c11=0.
The maximum allocation in this cell is min (4, 3) = 3.
It satisfy demand of D1 and adjust the supply of S1 from 4 to 1 (4 - 3=1).
Table-2
Solution
B. Reformulate this problem as a general linear programming problem.
D1 D2 Supply
S1 X11 8 X12 5 4
S2 X21 6 X22 4 2
Demand 3 4
Min Z = 8x11 + 5x12 +
6x21 + x31
Subject to:
Supply constraint ; X11 + x12 <= 4
X21 + X22 <= 2
Demand constraint; X11 + X21 <= 3
X12 + X22 <= 4
X11, X12, X21, X22 >= 0
8. Agricultural goods have to be transported from sources S1, S2 and S3 to destinations D1, D2 and
D3. The transportation cost per unit, capacities of the sources and requirements of the
destinations are given in the following table:
D1 D2 D3 Supply
S1 8 5 6 120
S2 15 10 12 80
S3 3 9 10 80
Demand 140 80 50
A. Using the North-West Corner (NWC) Method, Least Cost Method (LCM), and Vogel’s
Approximation (or penalty) Method (VAM, obtain the initial basic feasible solution,
a, Find Solution using North-West Corner method

D1 D2 D3 Supply

S1 8 5 6 120

S2 15 10 12 80

S3 3 9 10 80

Demand 140 80 50

Solution: TOTAL number of supply constraints : 3

TOTAL number of demand constraints : 3

D1 D2 D3 Supply
 S1 8 5 6 120

S2 15 10 12 80

S3 3 9 10 80

Demand 140 80 50

Here Total Demand = 270 is less than Total Supply = 280. So We add a dummy demand
constraint with 0 unit cost and with allocation 10.
Now, The modified table is

D1 D2 D3 Ddummy Supply

S1 8 5 6 0 120

S2 15 10 12 0 80

S3 3 9 10 0 80

Demand 140 80 50 10

The rim values for S1=120 and D1=140 are compared.

The smaller of the two i.e. min(120,140) = 120 is assigned to S1 D1
This exhausts the capacity of S1 and leaves 140 - 120=20 units with D1
Table-1

D1 D2 D3 Ddummy Supply

S1 8(120) 5 6 0 0

S2 15 10 12 0 80

S3 3 9 10 0 80

Demand 20 80 50 10

The rim values for S2=80 and D1=20 are compared.

The smaller of the two i.e. min(80,20) = 20 is assigned to S2 D1
 This meets the complete demand of D1 and leaves 80 - 20=60 units with S2
Table-2

D1 D2 D3 Ddummy Supply

S1 8(120) 5 6 0 0

S2 15(20) 10 12 0 60

S3 3 9 10 0 80

Demand 0 80 50 10

The rim values for S2=60 and D2=80 are compared.

The smaller of the two i.e. min(60,80) = 60 is assigned to S2 D2
This exhausts the capacity of S2 and leaves 80 - 60=20 units with D2
Table-3

D1 D2 D3 Ddummy Supply

S1 8(120) 5 6 0 0

S2 15(20) 10(60) 12 0 0

S3 3 9 10 0 80

Demand 0 20 50 10

The rim values for S3=80 and D2=20 are compared.

The smaller of the two i.e. min(80,20) = 20 is assigned to S3 D2
This meets the complete demand of D2 and leaves 80 - 20=60 units with S3
Table-4

D1 D2 D3 Ddummy Supply

S1 8(120) 5 6 0 0

S2 15(20) 10(60) 12 0 0

S3 3 9(20) 10 0 60
 Demand 0 0 50 10

The rim values for S3=60 and D3=50 are compared.

The smaller of the two i.e. min(60,50) = 50 is assigned to S3 D3
This meets the complete demand of D3 and leaves 60 - 50=10 units with S3
Table-5

D1 D2 D3 Ddummy Supply

S1 8(120) 5 6 0 0

S2 15(20) 10(60) 12 0 0

S3 3 9(20) 10(50) 0 10

Demand 0 0 0 10

The rim values for S3=10 and Ddummy=10 are compared.

The smaller of the two i.e. min(10,10) = 10 is assigned to S3 Ddummy
Table-6

D1 D2 D3 Ddummy Supply

S1 8(120) 5 6 0 0

S2 15(20) 10(60) 12 0 0

S3 3 9(20) 10(50) 0(10) 0

Demand 0 0 0 0

Initial feasible solution is

D1 D2 D3 Ddummy Supply

S1 8 (120) 5 6 0 120

S2 15 (20) 10 (60) 12 0 80

S3 3 9 (20) 10 (50) 0 (10) 80

 Demand 140 80 50 10

The minimum total transportation cost =8×120+15×20+10×60+9×20+10×50+0×10=2540

Here, the number of allocated cells = 6 is equal to m + n - 1 = 3 + 4 - 1 = 6
Least Cost Method (LCM)
Find Solution using Least Cost method

D1 D2 D3 Supply

S1 8 5 6 120

S2 15 10 12 80

S3 3 9 10 80

Demand 140 80 50

Solution: TOTAL number of supply constraints : 3

TOTAL number of demand constraints : 3

D1 D2 D3 Supply

S1 8 5 6 120

S2 15 10 12 80

S3 3 9 10 80

Demand 140 80 50

Here Total Demand = 270 is less than Total Supply = 280. So We add a dummy demand
constraint with 0 unit cost and with allocation 10.
Now, The modified table is

D1 D2 D3 Ddummy Supply

S1 8 5 6 0 120

S2 15 10 12 0 80

S3 3 9 10 0 80
 Demand 140 80 50 10

The smallest transportation cost is 0 in cell S1Ddummy

The allocation to this cell is min(120,10) = 10.
This satisfies the entire demand of Ddummy and leaves 120 - 10=110 units with S1
Table-1

D1 D2 D3 Ddummy Supply

S1 8 5 6 0(10) 110

S2 15 10 12 0 80

S3 3 9 10 0 80

Demand 140 80 50 0

The smallest transportation cost is 3 in cell S3D1

The allocation to this cell is min(80,140) = 80.
This exhausts the capacity of S3 and leaves 140 - 80=60 units with D1
Table-2

D1 D2 D3 Ddummy Supply

S1 8 5 6 0(10) 110

S2 15 10 12 0 80

S3 3(80) 9 10 0 0

Demand 60 80 50 0

The smallest transportation cost is 5 in cell S1D2

The allocation to this cell is min(110,80) = 80.
This satisfies the entire demand of D2 and leaves 110 - 80=30 units with S1
Table-3

D1 D2 D3 Ddummy Supply
 S1 8 5(80) 6 0(10) 30

S2 15 10 12 0 80

S3 3(80) 9 10 0 0

Demand 60 0 50 0

The smallest transportation cost is 6 in cell S1D3

The allocation to this cell is min(30,50) = 30.
This exhausts the capacity of S1 and leaves 50 - 30=20 units with D3
Table-4

D1 D2 D3 Ddummy Supply

S1 8 5(80) 6(30) 0(10) 0

S2 15 10 12 0 80

S3 3(80) 9 10 0 0

Demand 60 0 20 0

The smallest transportation cost is 12 in cell S2D3

The allocation to this cell is min(80,20) = 20.
This satisfies the entire demand of D3 and leaves 80 - 20=60 units with S2
Table-5

D1 D2 D3 Ddummy Supply

S1 8 5(80) 6(30) 0(10) 0

S2 15 10 12(20) 0 60

S3 3(80) 9 10 0 0

Demand 60 0 0 0

The smallest transportation cost is 15 in cell S2D1

The allocation to this cell is min(60,60) = 60.
 Table-6

D1 D2 D3 Ddummy Supply

S1 8 5(80) 6(30) 0(10) 0

S2 15(60) 10 12(20) 0 0

S3 3(80) 9 10 0 0

Demand 0 0 0 0

Initial feasible solution is

D1 D2 D3 Ddummy Supply

S1 8 5 (80) 6 (30) 0 (10) 120

S2 15 (60) 10 12 (20) 0 80

S3 3 (80) 9 10 0 80

Demand 140 80 50 10

The minimum total transportation cost =5×80+6×30+0×10+15×60+12×20+3×80=1960

Here, the number of allocated cells = 6 is equal to m + n - 1 = 3 + 4 - 1 = 6
Vogel’s Approximation (or penalty) Method (VAM,)
Find Solution using Voggel's Approximation method

D1 D2 D3 Supply

S1 8 5 6 120

S2 15 10 12 80

S3 3 9 10 80

Demand 140 80 50

Solution: TOTAL number of supply constraints : 3

TOTAL number of demand constraints : 3
 D1 D2 D3 Supply

S1 8 5 6 120

S2 15 10 12 80

S3 3 9 10 80

Demand 140 80 50

Here Total Demand = 270 is less than Total Supply = 280. So We add a dummy demand
constraint with 0 unit cost and with allocation 10.
Now, The modified table is

D1 D2 D3 Ddummy Supply

S1 8 5 6 0 120

S2 15 10 12 0 80

S3 3 9 10 0 80

Demand 140 80 50 10

Table-1

D1 D2 D3 Ddummy Supply Row Penalty

S1 8 5 6 0 120 5=5-0

S2 15 10 12 0 80 10=10-0

S3 3 9 10 0 80 3=3-0

Demand 140 80 50 10

ColumnPenty 5=8-3 4=9-5 4=10-6 0=0-0

The maximum penalty, 10, occurs in row S2.

The minimum cij in this row is c24=0.
 The maximum allocation in this cell is min(80,10) = 10.
It satisfy demand of Ddummy and adjust the supply of S2 from 80 to 70 (80 - 10=70).
Table-2

D1 D2 D3 Ddummy Supply Row Penalty

S1 8 5 6 0 120 1=6-5

S2 15 10 12 0(10) 70 2=12-10

S3 3 9 10 0 80 6=9-3

Demand 140 80 50 0

ColumnPenalty 5=8-3 4=9-5 4=10-6 --

The maximum penalty, 6, occurs in row S3.

The minimum cij in this row is c31=3.
The maximum allocation in this cell is min(80,140) = 80.
It satisfy supply of S3 and adjust the demand of D1 from 140 to 60 (140 - 80=60).
Table-3

D1 D2 D3 Ddummy Supply Row Penalty

S1 8 5 6 0 120 1=6-5

S2 15 10 12 0(10) 70 2=12-10

S3 3(80) 9 10 0 0 --

Demand 60 80 50 0

Column Penalty 7=15-8 5=10-5 6=12-6 --

The maximum penalty, 7, occurs in column D1.

The minimum cij in this column is c11=8.
 The maximum allocation in this cell is min (120, 60) = 60.
It satisfy demand of D1 and adjust the supply of S1 from 120 to 60 (120 - 60=60).
Table-4

D1 D2 D3 Ddummy Supply Row Penalty

S1 8(60) 5 6 0 60 1=6-5

S2 15 10 12 0(10) 70 2=12-10

S3 3(80) 9 10 0 0 --

Demand 0 80 50 0

Clmn Penalty -- 5=10-5 6=12-6 --

The maximum penalty, 6, occurs in column D3.

The minimum cij in this column is c13=6.
The maximum allocation in this cell is min (60, 50) = 50.
It satisfy demand of D3 and adjust the supply of S1 from 60 to 10 (60 - 50=10).
Table-5

D1 D2 D3 Ddummy Supply Row Penalty

S1 8(60) 5 6(50) 0 10 5

S2 15 10 12 0(10) 70 10

S3 3(80) 9 10 0 0 --

Demand 0 80 0 0

ClmnPenalty -- 5=10-5 -- --

The maximum penalty, 10, occurs in row S2.

The minimum cij in this row is c22=10.
 The maximum allocation in this cell is min (70, 80) = 70.
It satisfy supply of S2 and adjust the demand of D2 from 80 to 10 (80 - 70=10).
Table-6

D1 D2 D3 Ddummy Supply Row Penalty

S1 8(60) 5 6(50) 0 10 5

S2 15 10(70) 12 0(10) 0 --

S3 3(80) 9 10 0 0 --

Demand 0 10 0 0

CmnPnlty -- 5 -- --

The maximum penalty, 5, occurs in row S1.

The minimum cij in this row is c12=5.
The maximum allocation in this cell is min (10, 10) = 10.
It satisfies supply of S1 and demand of D2.
Initial feasible solution is

D1 D2 D3 Ddummy Supply Row Penalty

S1 8(60) 5(10) 6(50) 0 120 5| 1| 1| 1| 5| 5|

S2 15 10(70) 12 0(10) 80 10 | 2 | 2 | 2 | 10 | --
|

S3 3(80) 9 10 0 80 3 | 6 | -- | -- | -- | -- |

Demand 140 80 50 10

Column 5 4 4 0
Penalty 5 4 4 --
7 5 6 --
-- 5 6 --
 -- 5 -- --
-- 5 -- --

The minimum total transportation cost =8×60+5×10+6×50+10×70+0×10+3×80=1770

Here, the number of allocated cells = 6 is equal to m + n - 1 = 3 + 4 - 1 = 6
B. Formulate it as a Linear Programming Problem.
D1 D2 D3 Supply
S1 X11 8 X12 5 X13 6 120
S2 X21 15 X22 10 X23 12 80
S3 X31 3 X32 9 X33 10 80
Demand 140 80 50
Min Z = 8X11 + 5X12 + 6X13+15X21+ 10X22 + 12X23 + 3X31 + 9X32 + 10X33
Subject to
Supply constraint; X11 + X12 + X13 = 120
X21 + X22 + X23 = 80
X31 + X32 + X33 = 80
Demand constraint = X11 + X21 + X31 = 140
X12 + X22 + X32 = 80
X13 + X23 + X33 = 50
X11, X12, X13, X21, X22, X23, X31, X32, X33 >= 0
9 Harley’s Sand and Gravel Pit have contracted to provide topsoil for three residential housing
developments. Topsoil can Suppliefrom three different “farms” as follows:
Farm Weekly capacity (cubic yards)
A 100
B 200
C 200

Demand for the topsoil generated by the construction projects is:

Projecct Weekly demand(cubic yards)

1 50
 2 150
3 300

The manager of the sand and gravel pit has estimated the cost per cubic yard to ship over each of
the possible routes:
From/to Cost per cubic yard to
Project #1 Project #2 Project #3
Farm A Birr 4 Birr 2 Birr 8
Farm B 5 1 9
Farm C 7 6 3
Solution
A. arrange the information into a transportation table
From/to Cost per cubic yard to
Project #1 Project #2 Project #3 Wkly cpcity (cubic yards)

Farm A Birr 4 Birr 2 Birr 8 100

Farm B 5 1 9 200

Farm C 7 6 3 200

W/demand(cubic 50 150 300

yards)

B. Write the above transportation problem in the form of linear programming problem.
Min z = 4x11 + 2x12 +8x13 + 5x21 + 1x22 + 9x23 + 7x31 + 6x32 + 3x33
Subject to:
Weekly Capacity Constraint: 4x11 + 2x12 + 2x13 >= 100
5x22 + 1x22 + 9x23 >= 200
7x31 + 6x32 + 3x33 >= 200
Weekly demand Constraint: 4x11 + 5x21 + 7x31 >= 50
2x12 + 1x22 + 6x32 >= 150
 8x13 + 9x23 + 3x33 >= 300
C. Find the feasible solution using North-West Corner (NWC) Method, Least Cost Method
(LCM), and Vogel’s Approximation (or penalty) Method (VAM).
 North-West Corner (NWC) Method
Find Solution using North-West Corner method
Pro1 pro2 pro3 Supply
S1. 4 2 8 100
S2 5 1 9 200
S3 7 6 3 200
Demand 50 150 300
Solution:
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 3
Problem Table is
Proj1 proj2 pro3 Supply
S1 4 2 8 100
S2 5 1 9 200
S3 7 6 3 200
Demand 50 150 300
Problem is Maximization, so convert it to minimization by subtracting all the elements from max
element (9)
D1 D2 D3 Supply
S1 5 7 1 100
S2 4 8 0 200
S3 2 3 6 200
Demand 50 150 300

The rim values for S1=100 and D1=50 are compared.

The smaller of the two i.e. min(100,50) = 50 is assigned to S1 D1
This meets the complete demand of D1 and leaves 100 - 50=50 units with S1
Table-1
D1 D2 D3 Supply
S1 5(50) 7 1 50
S2 4 8 0 200
S3 2 3 6 200
Demand 0 150 300

The rim values for S1=50 and D2=150 are compared.

The smaller of the two i.e. min(50,150) = 50 is assigned to S1 D2
This exhausts the capacity of S1 and leaves 150 - 50=100 units with D2

Table-2
Proj1 2 D3 Supply
S1 5(50) 7(50) 1 0
S2 4 8 0 200
S3 2 3 6 200
Demand 0 100 300

The rim values for S2=200 and D2=100 are compared.

The smaller of the two i.e. min(200,100) = 100 is assigned to S2 D2
This meets the complete demand of D2 and leaves 200 - 100=100 units with S2
Table-3
Proj1 proj2 proj3 Supply
S1 5(50) 7(50) 1 0
S2 4 8(100) 0 100
S3 2 3 6 200
Demand 0 0 300

The rim values for S2=100 and D3=300 are compared.

The smaller of the two i.e. min(100,300) = 100 is assigned to S2 D3
This exhausts the capacity of S2 and leaves 300 - 100=200 units with D3
Table-4
Proj1 proj2 proj3 Supply
S1 5(50) 7(50) 1 0
S2 4 8(100) 0(100) 0
S3 2 3 6 200
Demand 00 200

The rim values for S3=200 and D3=200 are compared.

The smaller of the two i.e. min(200,200) = 200 is assigned to S3 D3
Table-5
Pro1 pro2 pro3 bSupply
S1 5(50) 7(50) 1 0
S2. 4 8(100) 0(100) 0
S3 2 3 6(200) 0
Demand 0 0 0
Initial feasible solution is
Pro1 pro2 pro3 Supply
S1 5 (50)7 (50) 1 100
S2 4 8 (100) 0 (100) 200
S3 2 3 6 (200) 200
Demand 50 150 300

Allocations in the original problem

Proj1 proj2. Pro3 Supply
S1 4 (50) 2 (50). 8 100
S2 5 1 (100) 9 (100) 200
S3 7 6 3 (200)200
Demand 50 150 300
The maximum profit =4×50+2×50+1×100+9×100+3×200=1900
 Here, the number of allocated cells = 5 is equal to m + n - 1 = 3 + 3 - 1 = 5
From/to Cost per cubic yard to
Project #1 Project #2 Project #3 Weekly capacity (cubic yards)

Farm A 4 2 8 100
Farm B 5 1 9 200

Farm C 7 6 3 200
W/ demand(cubic yards 50 150 300

 Least Cost Method (LCM)

Find Solution using Least Cost method
D1 D2 D3 Supply
S1 4 2 8 100
S2 5 1 9 200
S3 7 6 3 200
Demand 50 150 300
Solution:
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 3
Problem Table is
D1 D2 D3 Supply
S1 4 2 8 100
S2 5 1 9 200
S3 7 6 3 200
Demand 50 150 300
Problem is Maximization, so convert it to minimization by subtracting all the elements from max
element (9)
D1 D2 D3 Supply
S1 5 7 1 100
S2 4 8 0 200
 S3 2 3 6 200
Demand 50 150 300
The smallest transportation cost is 0 in cell S2D3
The allocation to this cell is min(200,300) = 200.
This exhausts the capacity of S2 and leaves 300 - 200=100 units with D3
Table-1
D1 D2 D3 Supply
S1 5 7 1 100
S2 4 8 0(200) 0
S3 2 3 6 200
Demand 50 150 100
The smallest transportation cost is 1 in cell S1D3
The allocation to this cell is min(100,100) = 100.
Table-2
D1 D2 D3 Supply
S1 5 7 1(100) 0
S2 4 8 0(200) 0
S3 2 3 6 200
Demand 50 150 0
The smallest transportation cost is 2 in cell S3D1
The allocation to this cell is min(200,50) = 50.
This satisfies the entire demand of D1 and leaves 200 - 50=150 units with S3
Table-3
D1 D2 D3 Supply
S1 5 7 1(100) 0
S2 4 8 0(200) 0
S3 2(50) 3 6 150
Demand 0 150 0
The smallest transportation cost is 3 in cell S3D2
The allocation to this cell is min(150,150) = 150.
Table-4
D1 D2 D3 Supply
S1 5 7 1(100) 0
S2 4 8 0(200) 0
S3 2(50) 3(150) 6 0
Demand 0 0 0

Initial feasible solution is

D1 D2 D3 Supply
S1 5 7 1 (100) 100
S2 4 8 0 (200) 200
S3 2 (50) 3 (150) 6 200
Demand 50 150 300
Allocations in the original problem
Proj 1 proj2 proj3 weekly capacity ( cubic yards)
S1 4 2 8 (100) 100
S2 5 1 9 (200) 200
S3 7 (50) 6 (150) 3 200
Demand 50 150 300
The maximum profit =8×100+9×200+7×50+6×150=3850
Here, the number of allocated cells = 4, which is one less than to m + n - 1 = 3 + 3 - 1 = 5

Cost per cubic yard to

Project/ farm Project #1 Project #2 Project #3 Weekly capacity (cubic yards)

Farm A 2 2 8 100

Farm B 5 1 9 200
Farm C 7 6 3 200

W/ deman(cubic yards 50 150 300

 Vogel’s Approximation (or penalty) Method (VAM)
D1 D2 D3 Supply
S1 4 2 8 100
S2 5 1 9 200
S3 7 6 3 200
Demand 50 150 300
Solution: TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 3
Problem Table is
D1 D2 D3 Supply
S1 4 2 8 100
S2 5 1 9 200
S3 7 6 3 200
Demand 50 150 300
Problem is Maximization, so convert it to minimization by subtracting all the elements from max
element (9)
D1 D2 D3 Supply
S1 5 7 1 100
S2 4 8 0 200
S3 2 3 6 200
Demand 50 150 300
Table-1
D1 D2 D3 Supply Row Penalty
S1 5 7 1 100 4=5-1
S2 4 8 0 200 4=4-0
S3 2 3 6 200 1=3-2
Demand 50 150 300
Colm Penlty 2=4-2 4=7-3 1=1-0
The maximum penalty, 4, occurs in row S2.
The minimum cij in this row is c23=0.
The maximum allocation in this cell is min(200,300) = 200.
It satisfy supply of S2 and adjust the demand of D3 from 300 to 100 (300 - 200=100).
Table-2
D1 D2 D3 Supply Row Penalty
S1 5 7 1 100 4=5-1
S2 4 8 0(200) 0 --
S3 2 3 6 200 1=3-2
Demand 50 150 100
Col Penalty 3=5-2 4=7-3 5=6-1
The maximum penalty, 5, occurs in column D3.
The minimum cij in this column is c13=1.
The maximum allocation in this cell is min(100,100) = 100.
It satisfy supply of S1 and demand of D3.
Table-3
D1 D2 D3 Supply Row Penalty
S1 5 7 1(100) 0 --
S2 4 8 0(200) 0 --
S3 2 3 6 200 1=3-2
Demand 50 150 0
Coln Penlty 2 3 --
The maximum penalty, 3, occurs in column D2.
The minimum cij in this column is c32=3.
The maximum allocation in this cell is min(200,150) = 150.
It satisfy demand of D2 and adjust the supply of S3 from 200 to 50 (200 - 150=50).
Table-4
Proj1 proj2 proj3 Supply Row Penalty
S1 5 7 1(100) 0 --
S2 4 8 0(200) 0 --
S3 2 3(150) 6 50 2
Demand 50 0 0
Colm Penlty 2 -- --
The maximum penalty, 2, occurs in row S3.
The minimum cij in this row is c31=2.
The maximum allocation in this cell is min(50,50) = 50.
It satisfy supply of S3 and demand of D1.
Initial feasible solution is
Proj1 proj2 proj3 Supply Row Penalty
S1 5 7 1(100) 100 4 | 4 | -- | -- |
S2 4 8 0(200) 200 4 | -- | -- | -- |
S3 2(50) 3(150) 6 200 1| 1| 1| 2|
Demand 50 150 300
C/ Penty 2 4 1
3 4 5
2 3 --
2 -- --
Allocations in the original problem
Proj1 proj2 proj3 Supply
S1 4 2 8 (100) 100
S2 5 1 9 (200) 200
S3 7 (50) 6 (150)3 200
Demand 50 150 300
The maximum profit =8×100+9×200+7×50+6×150=3850
Here, the number of allocated cells = 4, which is one less than to m + n - 1 = 3 + 3 - 1 = 5

10. A manager has prepared a table that shows the cost of performing each of four jobs by each
of four employees. According to this Table, Job 1 will cost $15 if done by Employee A, $20 if
it is done by Employee B, and so on. The manager has stated that his goal is to develop a set of
job assignments that will minimize the total cost of getting all four jobs done. It is further
required that the jobs Be performed simultaneously, thus requiring one job being assigned to
each employee. Although the manager recognizes that this Problem can be solved using the
simplex routine; he also knows that he can solve the problem by hand using the assignment
method.
Job Costs for Each Possible Pairing
Employees
A B C D
1 $15 20 18 24
2 12 17 16 15
Job 3 14 15 19 17
4 11 14 12 13
Required:
A. Formulate a linear Programming problem
B. Which salesperson should be assigned to each region to minimize total time? Identify the
optimal assignments and compute total minimum time. Use the Hungarian Method
Solution
A B C D Supply
1 15 20 18 24 1
2 12 17 16 15 1
3 14 15 19 17 1
4 11 14 12 13 1
Demand 1 1 1 1

Min C = 15 X11 + 20X12 + 18X13 + 24X14 + 12X21 + 17X22 + 16X23 + 15X24 + 14X31 +
15X32 + 19X33 + 17X34 + 11X41 + 14X42 + 12X43 + 13X44
Subject to;
Supply constraint; X11 + x12 + x13 + x14 >= 1
X21 + x22 + x23 + x24 = 1
X31 + X32 + X33 + X34 = 1
X41 + X42 + X43 + X44 = 1
Demand constraint; X11+ X21 + X31 + X44 = 1
B Find Solution of Assignment problem using Hungarian method
Work\Job 1 2 3 4
A 15 12 14 11
B 20 17 15 14
C 18 16 19 12
D 24 15 17 13

Solution: The number of rows = 4 and columns = 4

Step-1: Find out the each row minimum element and subtract it from that row

1 2 3 4 Row Mini
A 4 1 3 0 (-11)
B 6 3 1 0 (-14)
C 6 4 7 0 (-12)
D 11 2 4 0 (-13)

Step-2: Find out the each column minimum element and subtract it from that column.
1 2 3 4
A 0 0 2 0
B 2 2 0 0
C 2 3 6 0
D 7 1 3 0
Colm min (-4) (-1) (-1) (-0)

Iteration-1 of steps 3 to 6
Step-3: Make assignment in the opporunity cost table
Step-3: Make assignment in the opporunity cost table
(1) Rowwise cell (C,4) is assigned, so columnwise cell (A,4),(B,4),(D,4) crossed off.

(2) Rowwise cell (B,3) is assigned

(3) Columnwise cell (A,1) is assigned, so rowwise cell (A,2) crossed off.
Rowwise&columnwise assignment shown in table
 1 2 3 4
A [0] 0 2 0
B 2 2 [0] 0
C 2 3 6 [0]
D 7 1 3 0

Step-4: Number of assignments = 3, number of rows = 4

Which is not equal, so solution is not optimal.

Step-5: Draw a set of horizontal and vertical lines to cover all the 0
Step-5: Cover the 0 with minimum number of lines
(1) Mark(✓) row D since it has no assignment

(2) Mark(✓) column 4 since row D has 0 in this column

(3) Mark(✓) row C since column 4 has an assignment in this row C.

(4) Since no other rows or columns can be marked, therefore draw straight lines through the
unmarked rows A,B and marked columns 4

Tick mark not allocated rows and allocated columns

1 2 3 4
A [0] 0 2 0

B 2 2 [0] 0

C 2 3 6 [0] ✓(3)
D 7 1 3 0 ✓(1)
✓
(2)

Step-6: Develop the new revised opportunity cost table

Step-6: Develop the new revised table by selecting the smallest element, among the cells not
covered by any line (say k = 1)
Subtract k = 1 from every element in the cell not covered by a line.
Add k = 1 to every elment in the intersection cell of two lines.
 1 2 3 4
A 0 0 2 1
B 2 2 0 1
C 1 2 5 0
D 6 0 2 0

Repeat steps 3 to 6 until an optimal solution is obtained.

Iteration : 1

Iteration-2 of steps 3 to 6
Step-3: Make assignment in the opporunity cost table

(1) Rowwise cell (B,3) is assigned

(2) Rowwise cell (C,4) is assigned, so columnwise cell (D,4) crossed off.

(3) Rowwise cell (D,2) is assigned, so columnwise cell (A,2) crossed off.

(4) Rowwise cell (A,1) is assigned

Rowwise&columnwise assignment shown in table

1 2 3 4
A [0] 0 2 1
B 2 2 [0] 1
C 1 2 5 [0]
D 6 [0] 2 0
Step-4: Number of assignments = 4, number of rows = 4
Which is equal, so solution is optimal
Optimal assignments are
1 2 3 4
A [0] 0 2 1
B 2 2 [0] 1
C 1 2 5 [0]
D 6 [0] 2 0
Optimal solution is

Work Job Cost

A 1 15
B 3 15
C 4 12
D 2 15
Total 57

Tc 15+ 15 + 12 + 15 = 57
11. A firm makes air coolers of three types and markets these under the brand name
“Symphony”.
The relevant details are as follows:-
Product A (hrs. / Product B (hrs. / Product C (hrs,/ Total hrs.
unit) unit) unit) available
Designing 0 10 20 320
Manufacturing 60 90 120 1600
Painting 30 40 60 1120
Profit $300 $700 $900
Required:
Formulate a linear Programming problem
What Quantity of each product must be made to maximize the total profit of the firm? Use
simple procedure.
Solution
Formulate linear programing problem
Max z =300x1 + 700x2 + 900x3
Subject to:
Designing : 10x2 + 20X3 <= 320
Manufacturing : 60x1 + 90x2 + 120x3 <= 1600
Painting:. 30x1 + 40x2 + 60x3 <= 1120
What Qty. of each product must be made to maximize the total profit of the firm?
Let X1, X2, X3 denote the Qty. of each product made
Then: Maximize: 300 X1+ 700 X2 +900 X3
Subject to:
0 X1 +10 X2 + 20 X3 ≤ 320
60 X1 +90 X2 + 120 X3 ≤ 1600
30 X1 +40 X2 + 60 X3 ≤ 1120
Introducing slacks:
Maximize Z = 300X1 +700X2 + 900X3 +0S1+ 0S2+ 0S3
Subject to: 0X1 +10X2 + 20X3 +S1+ 0S2+ 0S3 =320
60X1 +90X2 + 120X3 +0S1+ S2+ 0S3 =1600
30X1 +40X2 + 60X3 +0S1+ 0S2+ S3 =11
X1, X2, X3, S1, S2, S3 >= 0
12. The Omega pharmaceutical firm has five salespersons, which the firm wants to assign to
five sales regions. Given their various previous contacts, the salespersons are able to cover the
regions in different amounts of time. The amount of time (days) required by each salesperson to
cover each city is shown in the following table.
Requerd;
Formulate a linear Programming problem
Which salesperson should be assigned to each region to minimize total time? Identify the optimal
assignments and compute total minimum time. Use the Hungarian Method
Solution: a.
b. Step 1
Region
Sales person A B C D E
1 6 1 6 7 9
2 1 0 7 0 3
3 0 7 5 6 1
4 3 1 1 9 6
5 2 3 0 6 0

b. Which salesperson should be assigned to each region to minimize total time? Identify the
optimal assignments and compute total minimum time. Use the Hungarian Method
Answer Row reduction:
A B C D E
1 7 0 5 6 10
2 3 0 7 0 5
3 0 5 3 4 1
4 4 0 0 8 7
5 4 3 0 6 2
Column reduction:
A B C D E
7 0 5 6 9
3 0 7 0 4
0 5 3 4 0
4 0 0 8 6
4 3 0 6 1

A B C D E

7 0 5 6 9
3 0 7 0 4
0 5 3 4 0
4 0 0 8 6
4 3 0 6 1
Final step is as follows:
A B C D E
6 0 5 5 4
3 1 8 0 8
0 6 4 4 0
4 0 0 7 5
3 3 0 5 0
B→1
C→4
A→3
D→2
E→5
Total= 51 days