CPU COLLEGE

COLLEGE OF BUSINESS AND TECHNOLOGY

MASTERS OF BUSINESS ADMINISTRATION

Group assignment for the course of Analytical Decision

Modeling for Business Decisions

Submitted To: Dr. Hailemichael M.

Submited by Id. No.

Abeba Beferdu EMBA/632/13
Habtamu Degwale EMBA/013/13
Mekdes Mihretu EMBA/203/13
Yesewzer Andualem EMBA/047/13
Zerihun Yezihalem EMBA/605/13

July 2021

Addis Ababa, Ethiopia

Contents

1. Solution...............................................................................................................................................1
a) Formulate linear programming model.............................................................................................1
b) Solve using graphical solution method............................................................................................1
c) Solve using simplex method............................................................................................................2
2. Solution...............................................................................................................................................4
a) Formulate the linear programming model........................................................................................4
b) Solve by using graphical solution method.......................................................................................4
c) Solve by using Simplex method......................................................................................................6
3. Solution...............................................................................................................................................8
a) Formulate the linear programming model........................................................................................8
b) Solve by using graphical solution method.......................................................................................8
c) Solve by using simplex method.......................................................................................................9
4. Solution.............................................................................................................................................10
a) Formulate the linear programming model......................................................................................10
b) Solve by using graphical solution methods....................................................................................11
c) Solve by using simplex method.....................................................................................................11
5. Solution.............................................................................................................................................12
a) Formulate the linear programming model......................................................................................12
b) Solve using graphical solution method..........................................................................................13
c) Solve by using simplex method.....................................................................................................14
6. Solution.............................................................................................................................................15
a) Formulate the linear programming model......................................................................................15
b) Solve by using graphical solution methods....................................................................................15
c) Solve by using simplex methods....................................................................................................17
7. Solution.............................................................................................................................................18
a) Formulate the linear programming model......................................................................................18
b) Solve the problem by using graphical solution..............................................................................19
c) Solve the problem by simplex method...........................................................................................20
8. Solution.............................................................................................................................................22
a) Formulate the linear programming Model.....................................................................................22
b) Solve by using graphical solution method.....................................................................................22

i
 c) Solve by using simplex methods....................................................................................................23
9. Solution.............................................................................................................................................25
a) Formulate the linear programming model......................................................................................25
b) Solve by using graphical solution..................................................................................................25
c) Solve by using simplex method.....................................................................................................26
10. Solution.........................................................................................................................................28
a) How should the cars be assigned to the customer so as to minimize the distance traveled? Using
Hungarian Method.................................................................................................................................28
b) What the total cost of optimum assignment...................................................................................29
11. Solution.........................................................................................................................................29
a) Find an initial feasible solution using VAM and Least cost Method.............................................29
b) Find the optimal solution using MODI method based on least cost...............................................30

ii
1. SOLUTION

Maximize Z=10X1+15X2
Subject to
2X1+X2≤26
2X1+4X2≤56
X1, X2≥0
a) Formulate linear programming model

Maximize Z=10X1+15X2
Subject to: 2X1+X2≤26
2X1+4X2≤56
X1, X2≥0
b) Solve using graphical solution method

Step 1: Formulate linear programming model

Maximize Z=10X1+15X2
Subject to: 2X1+X2≤26
2X1+4X2≤56
X1, X2≥0
Step 2: Convert constraints inequalities into equality
2X1+X2=26
2X1+4X2=56
The first constraint 2X1+X2 ≤26 can be represented as follows. We set 2X1+X2=26When X1=0 in
the above constraint, we get,0+X2=26 then X2=26. Similarly when X2=0 in the above constraint,
we get, 2X1+0=26 then X1=26/2=13.The second constraint 2X1+4X2≤56 can be represented as
follows. We set 2X1+4X2=56When X1=0 in the above constraint, we get, 0+4X2=56 then
X2=56/4=14. Similarly when X2=0 in the above constraint, we get, 2X1+0=56 then X1=56/2=28.
Step 3: Draw a graph including all the constraints and identify the feasible region (FR)
2X1+X2=26 (13, 0) and (0, 26)
2X1+4X2=56 (28, 0) and (0, 28)

X2

26

2X1+X2=26

14

FR
2X1+4X2=56

X1

1
 13 28
Step 4: Find feasible region
Hence any point in the shaded area (including its boundary) is a feasible solution to the given
Linear Programming Problem.
Step 5: Find the coordinate of corner point of feasible region A, B, C &D
Coordinate
Points Value of Z=10X1+15X2
(X1,X2)
A (0,0) 0
B (13,0) 130
C (8,10) 230
D (0,14) 210

Step 6: Identify the optimal point

Hence from above table maximum value of Z = 230 because maximum value of Z is attained at
the corner point C (8, 10).
Step 7: Interpret the result
8 unit of product X1 and 10 unit of product X2 should be produced in order to gate 230 unit of
profit.
c) Solve using simplex method

Step1: Formulate LPP model

Maximize Z=10X1+15X2
Subject to: 2X1+X2≤26
2X1+4X2≤56
X1, X2≥0
Our 1st step is to classify the problem. Clearly, we are going to maximize our objective function,
all are variables are nonnegative, and our constraints are written with our variable combinations
less than or equal to a constant. So this is a standard maximization problem and we know how to
use the simplex method to solve it.
Step2: Standardize the problem
We need to write our initial simplex tableau. Since we have two constraints, we need to
introduce the two slack variables S1 and S2. This gives us the equalities.
We rewrite our objective function as -10X1-15X2+Z=0 and from here obtain the system of
equations:
Max. Z=10X1+15X2+0S1+0S2
2X1+X2 +S1+0S2=26
2X1+4X2+0S1+S2=56
X1, X2, S1, S2≥0
Step3: Obtain the initial simplex tabula
First assumption, no production implies X1=0 and X2=0

2
Step4: Construct the 1st simplex table
Cj 10 15 0 0
SV X1 X2 S1 S2 Q
0 S1 2 1 1 0 26
0 S2 2 4 0 1 56
Zj 0 0 0 0 0
Cj-Zj 10 15 0 0

Step 5: Choose the entering variable (column) with maximum positive number in Cj-Zj row here
this is 15 and choosing the leaving variable
Cj 10 15 0 0
SV X1 X2 S1 S2 Q
0 S1 2 1 1 0 26 26/1 = 26
0 S2 2 4 0 1 56 56/4 = 14S2 is leaving variable
Zj 0 0 0 0 0
Cj-Zj 10 15 0 0
X2 entry variable
To find the pivot row, divide each entry in the constant column by the entry in the corresponding
in the pivot column. In this case, we’ll get 26/1 as the ratio for the first row and 56/4 for the ratio
in the second row. The pivot row is the row corresponding to the smallest ratio, in this case 14.
So our pivot element is the in the second column, second row, hence is 4.

New X2 1/2 1 0 1/4 14

New S1= Old S1-NewX2
Old S1 2 1 1 0 26
New S1 3/2 0 1 - 1/4 12
Step6: Construct the2ndsimplex table
Cj 10 15 0 0
SV X1 X2 S1 S2 Q
0 S1 3/2 0 1 -1/4 12 8 S1is Leaving variable
1
X2 ½ 1 0 1/4 14 28
5
Zj 15/2 15 0 15/4 210
Cj-Zj 5/2 0 0 -15/4
X1 is entering variable

Choose the entering variable (column) with maximum positive number in Cj-Zj row here this is
5/2. So X1 is entering variable.
Choosing the leaving variable. S1 is leaving variable.
Our pivot element is the in the first column, first row, hence is 3/2.
3
 2/
New X1 1 0 -1/6 8
3
New X2= Old X2-NewX1
Old X2 1/2 1 0 1/4 14

New X1 1 0 2/3 - 1/6 8 (1/2)

1/2 0 1/3 -1/12 4

New X2 0 1 - 1/3 1/3 10

rd
Step6: Construct the 3 simplex table
Cj 10 15 0 0
SV X1 X2 S1 S2 Q
10 X1 1 0 2/3 - 1/6 8
15 X2 0 1 - 1/3 1/3 10
Zj 10 15 5/3 10/3 230
Cj-Zj 0 0 -5/3 -10/3

Since all the Cj-Zj≤0 optimal solution is reached at.

Therefore, X1=8, X2=10 and Max Z=230

2. SOLUTION

Min Z=3X1+2X2
St. 5X1+X2≥10
X1+X2≥6
X1+4X2≥12
X1, X2≥0
a) Formulate the linear programming model

Min Z=3X1+2X2
St. 5X1+X2≥10
X1+X2≥6
X1+4X2≥12
X1, X2≥0
b) Solve by using graphical solution method

Step 1: Formulate LPP

Min Z=3X1+2X2St. 5X1+X2≥10
X1+X2≥6
X1+4X2≥12
X1, X2≥0

4
Step 2: Convert constraints inequalities into equality
5X1+X2=10
X1+X2=6
X1+4X2=12
Step 3: Draw a graph including all the constraints and identify the feasible region (FR)
5X1+X2=10 (2, 0) and (0, 10)
X1+X2=6 (6, 0) and (0, 6)
X1+4X2=12(12, 0) and (0, 3)
X2

10

6
FR

X1
2 6 12
5X1+X2=10 X1+X2=6 X1+4X2=12

Hence any point in the shaded area (including its boundary) is a feasible solution to the given
Linear Programming Problem.

Step 5: Find the coordinate of corner point of feasible region A, B, C& D

Coordinate Value of
Points
(X1,X2) Z=3X1+2X2
A (12,0) 36
B (4,2) 16
C (1,5) 13
D (0,10) 20

Step 6: Identify the optimal point

X1=1 and X2=5
Here is optimal point at Z=13 minimal cost
Step 7: Interpret the result

5
1 unit of product X1 and 5 unit of product X2should be produced in order to gate minimize the
cost.

c) Solve by using Simplex method

Step 1: Formulate LPP model

Min Z=3X1+2X2
St.: 5X1+X2≥10
X1+X2≥6
X1+4X2≥12
X1, X2≥0
Step 2: Standardize the problem
Min Z=3X1+2X2+0S1+0S2+0S3+MA1+MA2+MA3
St.: 5X1+X2-S1+MA1=10
X1+X2+-S2+MA2=6
X1+4X2-S3+MA3=12
X1, X2, S1, S2, S3, A1, A2, and A3≥0
Step 3: Construct the 1st simplex table
Cj 3 2 0 0 0 M M M
SV X1 X2 S1 S2 S3 A1 A2 A3 Q
A1 is leaving
M A1 5 1 -1 0 0 1 0 0 10 2 variable
M A2 1 1 0 -1 0 0 1 0 6 6
M A3 1 4 0 0 -1 0 0 1 12 12
Zj 7M 6M -M -M -M M M M 28M
Cj-Zj 3-7M 2-6M M M M 0 0 0
X1 is entering variable
Step 4: Construct the 2nd simplex table
New X1=Old A1 divide by 5
New X1: 1 1/5 -1/5 0 0 0 0 2
New A2: Old A2-New X1*1
New A2: 0 4/5 1/5 -1 0 1 0 4
New A3: Old A3-New X1*1

6
New A3: 0 19/5 1/5 0 -1 0 1 10

Cj 3 2 0 0 0 M M
SV X1 X2 S1 S2 S3 A2 A3 Q
3 X1 1 1/5 -1/5 0 0 0 0 2 10
M A2 0 4/5 1/5 -1 0 1 0 4 5
M A3 0 19/5 1/5 0 -1 0 1 10 50/19 A3 is leaving variable
Zj 3 3/5 + 23M/5 -3/5+2M/5 -M -M M M 6+14M
Cj-Zj 0 7/5-23M/5 3/5-2M/5 M M 0 0
X2 is entering variable

Step 5: Choose the entering variable-X2 is entering variable

Step 6: Choose the leaving variable-A3 is leaving variable
Step 7: Construct the 3rdsimplex table
NewX2=OldX2multiplying by 5/19
NewX2: 0 1 1/19 0 -5/19 0 50/19
NewX1: Old X1-New X2*PE
NewX1: 1 0 -4/9 0 1/19 0 28/19
New A2: Old A1-New X2*PE
New A2: 0 0 3/19 -1 4/19 1 36/19

Cj 3 2 0 0 0 M
SV X1 X2 S1 S2 S3 A2 Q
3 X1 1 0 -4/19 0 1/19 0 28/19
M A2 0 0 3/19 -1 4/19 1 36/19 A2 is leaving
variable
2 X2 0 1 1/19 0 -5/19 0 50/19
Zj 3 2 3M/19-10/19 -M 4M/19-7/19 M 36M+184/19
Cj-Zj 0 0 -3M/19+10/19 M -4M/19+7/19 0
S3 is entering variable
S3 is entering variable and A2 is leaving variable.

New S3=Old S3*19/4

0 0 ¾ -19/4 1 9
New X1=Old X1-New S3*1/19
1 0-1/4 ¼ 0 1

7
New X2=Old X2-New S3*1/19
01 1/4 -5/4 0 5

Cj 3 2 0 0 0
SV X1 X2 S1 S2 S3 Q
3 X1 1 0 -1/4 1/4 0 1
0 S3 0 0 3/4 -19/4 1 9
2 X2 0 1 1/4 -5/4 0 5
Zj 3 2 -1/4 -7/4 0 13
Cj-Zj 0 0 1/4 7/4 0
Now we reach at the optimal solution that is Cj-Zj ≥0
i.e. Min Z=3X1+2X2
Z=3(1)+2(5)=13
So X1=1 and X2=5 in order to minimize the cost in 13.

3. SOLUTION

Max Z = 6X1-4X2
St. X1+X2≤1
X1+X2≥3
X1+X2≥2
X1, X2≥0
a) Formulate the linear programming model

Max Z = 6X1-4X2
St. X1+X2≤1
X1+X2≥3
X1+X2≥2
X1, X2≥0
b) Solve by using graphical solution method

Step 1: Formulate LPP model

Max Z = 6X1-4X2
St. X1+X2≤1
X1+X2≥3
X1+X2≥2
X1, X2≥0
Step 2: Convert in to equality

8
 Max Z = 6X1-4X2
St. X1+X2=1
X1+X2=3
X1+X2=2
X1, X2≥0
Step 3: Draw the graph by using intercepts
X1+X2=1 (0, 1) and (1, 0)
X1+X2=3 (0, 3) and (3, 0)
X1+X2=2 (0, 2) and (2, 0)
X2
3

X1
1 2 3
X1+X2=1 X1+X2=2 X1+X2=3
In the above graph there is no common point in the shaded area. So the problem is infeasible
solution to the problem and all constraints cannot be satisfied simultaneously.
c) Solve by using simplex method

Step 1: Formulate LPP model

Max Z = 6X1-4X2
St. X1+X2≤1
X1+X2≥3
X1+X2≥2
X1, X2≥0
Step 2: Standardize the problem
Max Z = 6X1-4X2+0S1+0S2+0S3-MA2-MA3
X1+X2+S1=1
X1+X2-S2+MA2=3
X1+X2-S3+MA3=2
X1, X2, S1, S2, S3, A1,A2, and A3≥0

9
Step 3: Construct 1st simplex table
Cj 6 -4 0 0 0 -M -M
SV X1 X2 S1 S2 S3 A2 A3 Q
0 S1 1 1 1 0 0 0 0 1
-M A2 1 1 0 -1 0 0 0 3
-M A3 1 1 0 0 -1 0 1 2
Zj -2M -2M 0 M M -M -M -5M
Cj-Zj 6+2M -4+2M 0 -M -M 0 0

Step 4: Construct 2nd simplex table

New X1: 1 1 10 0 0 0 1
New A2: Old A2-New X1*PE
: 0 0 -1 -1 0 1 0 2
New A3: Old A2-New X1 *PE
: 0 0 -1 0 -1 0 0 2
Cj 6 -4 0 0 0 -M -M
SV X1 X2 S1 S2 S3 A2 A3 Q
6 X1 1 1 1 0 0 0 0 1
-M A2 0 0 -1 -1 0 1 0 2
-M A3 0 0 -1 0 -1 0 1 1
Zj 6 6 6+2M M M -M -M 6-3M
Cj-Zj 0 -10 -6-2M -M -M 0 0

No optimal solution the Cj-Zj≤0 before removes the artificial variable. So the solution is
infeasible.

4. SOLUTION

Max Z=3X1+2X2
st. 2X1+4X2≤4
4X1+8X2≥16
X1, X2≥0
a) Formulate the linear programming model

Max Z=3X1+2X2
10
 st. 2X1+4X2≤4
4X1+8X2≥16
X1, X2≥0
b) Solve by using graphical solution methods

Step 1: Formulate LPP model

Max Z=3X1+2X2
st. 2X1+4X2≤4
4X1+8X2≥16
X1, X2≥0
Step 2: convert in to equality
Max Z=3X1+2X2
st. 2X1+4X2=4
4X1+8X2=16
X1, X2≥0
Step 3: Draw the graph by using intercepts
2X1+4X2=4 (2, 0) and (0, 1)
4X1+8X2=16 (4, 0) and (0, 2)
X2

X1
2 4

2X1+4X2=44X1+8X2=16
Here there is no feasible region for the two constraints. So the problem is infeasible solution.
c) Solve by using simplex method

Step 1: Formulate LPP model

Max Z=3X1+2X2
st. 2X1+4X2≤4
4X1+8X2≥16
X1, X2≥0

11
 Step 2: Standardize the problem
Max Z=3X1+2X2+0S1+0S2-MA2
st. 2X1+4X2+S1=4
4X1+8X2-S2+MA2=16
X1, X2, S1, S2, A2≥0
Step 3: Construct 1st simplex table
Cj 3 2 0 0 -M
SV X1 X2 S1 S2 S3 Q
0 S1 2 4 1 0 0 4
-M A2 4 8 0 -1 1 16
Zj 4M -8M 0 M -M -16M
Cj-Zj 3+4M 2+8M 0 -M 0
So X2is entering variable and S1 is leaving variable.
New X2=Old X2*1/4
½ 1 ¼ 0 0 1
New A2=Old A2-New X2*PE
0 0 -2 -1 1 8
Step 3: Construct 2nd simplex table
Cj 3 2 0 0 -M
SV X1 X2 S1 S2 A2 Q
2 X2 ½ 1 1/4 0 0 4
-M A2 0 0 -2 -1 1 16
Zj 1 2 1/2+2M M -M -16M
[
Cj-Zj 2 0 -1/2-2M -M 0
So the solution is infeasible b/c we reach optimal solution that means Cj-Zj≤0 before removing
the artificial variable the SV/BV. i.e. The solution is infeasible solution.

5. SOLUTION

Max Z=5X1+3X2
St. 3X1+5X2≤15
5X1+2X2≤10
X1, X2, ≥0
a) Formulate the linear programming model

Max Z=5X1+3X2
St. 3X1+5X2≤15
5X1+2X2≤10

12
 X1, X2, ≥0
b) Solve using graphical solution method

Step 1: Formulate linear programming

Max Z=5X1+3X2
St. 3X1+5X2≤15
5X1+2X2≤10
X1, X2, ≥0
Step 2: convert to inequality
Max Z=5X1+3X2
St. 3X1+5X2=15
5X1+2X2=10
X1, X2, ≥0
Step 3: Draw the graph by using intercepts
3X1+5X2=15 (5, 0) and (0, 3)
5X1+2X2=10(2, 0) and (0, 5)
X2
5

F
R
X3
2 5
3X1+5X2=15 5X1+2X2=10
Step 4: Identify the feasible region
Step 5: Identify the corner point

Coordinate
Points Value of Z=53X1+3X2
(X1, X2)
A (0,0) 0
B (2,0) 10
C (20/9,45/19) 235/19

13
 D (0,3) 9

Step 6: Identify the optimal solution

The optimal solution is 12.37
Step 7: Interpret the result
20/19 unit of X1& 45/19 unit of X2 should be produced in order to get 12.37 profit.
c) Solve by using simplex method

Step 1: Formulate LPP model

Max Z=5X1+3X2
St. 3X1+5X2≤15
5X1+2X2≤10
X1, X2, ≥0
Step 2: Standardize the problem
Max Z=5X1+3X2+0S1+0S2
St. 3X1+5X2+S1=15
5X1+2X2=10
X1, X2, ≥0
Step 3: Construct the simplex table
Cj 5 3 0 0
SV X1 X2 S1 S2 Q
0 S1 3 5 1 0 15
0 S2 5 2 0 1 10
Zj 0 0 0 0 0
Cj-Zj 5 3 0 0
So X1 is entering variable and S2 is leaving variable
New X1=Old X1*1/5
1 2/5 0 1/5 2
New S1=Old S1-New X1*PE
0 19/5 1 -3/5 9
Step 4: Construct the 2ndsimplex table
Cj 5 3 0 0
SV X1 X2 S1 S2 Q
0 S1 0 19/5 1 -3/5 9
5 X1 1 2/5 0 1/5 2
Zj 5 2 0 1 10
Cj-Zj 0 1 0 -1
14
Step 5: choose the entering variable and the leaving variable
X2 is entering variable S1 leaving variable
Step 6: Construct the 3rd simplex table
New X2=Old X2*5/19
0 1 5/19 -3/19 45/19
New X1=Old X1-New X2*PE
1 0 -2/5 5/9 20/19
Cj 5 3 0 0
SV X1 X2 S1 S2 Q
3 X2 0 1 5/19 -3/19 45/19
5 X1 1 0 -2/19 5/19 20/19
Zj 5 3 5/19 1 235/19
Cj-Zj 0 0 -5/19 -1

Step 7: Since all the Cj-Zj≤0 optimal solution is reached.

Therefore, X1=20/19, X2=45/19 and Max Z=235/19

6. SOLUTION

Min Z = 4X1+3X2
st.X1+2X2≥40
3X1+4X2≥30
4X1+3X2≥60
X1, X2≥0
a) Formulate the linear programming model

Min Z = 4X1+3X2
st. X1+2X2≥40
3X1+4X2≥30
4X1+3X2≥60
X1, X2≥0
b) Solve by using graphical solution methods

Step 1: Formulate LPP model

Min Z = 4X1+3X2
st. X1+2X2≥40
3X1+4X2≥30
4X1+3X2≥60
X1, X2≥0
15
Step 2: Convert in to equality
Min Z = 4X1+3X2
st. X1+2X2=40
3X1+4X2=30
4X1+3X2=60
X1, X2≥0
Step 3: Draw the graph by using intercepts
X1+2X2=40 (40, 0) and (0, 20)
3X1+4X2=30 (10, 0) and (0, 15/2)
4X1+3X2=60 (15, 0) and (0, 20)

X2
20

FR

15/2

X1
10 15 40
3X1+4X2=30 4X1+3X2=60 X1+2X2=40

Step 4: Identify the feasible region

Step 5: Identify corner points
Coordinate Value of
Points
(X1, X2) Z = 4X1+3X2
A (40, 0) 160
[
B (0, 20) 60

Step 6: Identify the optimal point

Here is optimal point at Z=60 minimal cost
Step 7: Interpret the result
0 unit of product X1 and 20 unit of product X2should beproduced in order to gate minimize the
cost.
16
c) Solve by using simplex methods

Step 1: Formulate LPP model

Min Z=4X1+3X2
St. X1+2X2≥40
3X1+4X2≥30
4X1+3X2≥60
X1, X2≥
Step 2: Standardize the problem
Min Z=4X1+3X2+0S1+0S2+0S3+MA1+MA2+MA3
St. X1+2X2-S1+MA1=40
3X1+4X2-S2+MA2=30
4X1+3X2-S3+MA2=60
X1, X2, S1, S2, S3, M1, M2, M3 ≥ 0
Step 3: Construct 1stsimplex table
Cj 4 3 0 0 0 M M M
SV X1 X2 S1 S2 S3 A1 A2 A3 Q
M A1 1 2 -1 0 0 1 0 0 40 20
M A2 3 4 0 -1 0 0 1 0 30 15/2
M A3 4 3 0 0 -1 0 0 1 40 20
Zj 8M 9M -M -M -M M M M 130M
Cj-Zj 4-8M 3-9M M M M -M -M -M
X2 is entering variable
A2 is leaving variable
Step 4: Construct 2nd simplex table
New X2=Old X2*1/4
= 3/4 1 0 -1/4 0 0 0 15/2
New A1=Old A1+New X2*PE
= -1/2 0 -1 -1/2 0 1 0 25
New A3=Old A3+New X2*PE
= 7/4 0 0 3/4 -1 0 1 75/2
Construct 2nd simplex table
Cj 4 3 0 0 0 M M M
17
 SV X1 X2 S1 S2 S3 A1 A2 A3 Q
M A1 1/2 0 -1 1/2 0 1 -1/2 0 25
3 X2 3/4 1 0 -1/4 0 0 1/4 0 15/2
M A3 7/4 0 0 3/4 -1 0 -3/4 1 75/2
Zj -5M/4 + 9/4 3 -M 5M/4 - 3/4 -M M 3/4-5M/4 M 125M/2 + 45/2
-
Cj-Zj -5M/4 + 7/4 0 M -5M/4 + 3/4 M 0
3/4+9M/4
0

S2 is entering variable andA3 is leaving variable

Construct 3rd simplex table
Cj 4 3 0 0 0 M M M
SV X1 X2 S1 S2 S3 A1 A2 A3 Q Ratio
M A1 -5/3 0 -1 0 2/3 1 0 - 2/3 0 0
3 X2 4/3 1 0 0 -1/3 0 0 1/3 20 60
0 S2 5/3 0 0 1 -4/3 0 1 4/3 50 75/2
Zj 4-5M/3 3 -M 0 -1+2M/3 M 0 1-2M/3 60
Cj-Zj 5M/3 0 M 0 1-2M/3 0 M -1+1M/3

S3is entering variable andA1 is leaving variable

Cj 4 3 0 0 0 M M M
SV X1 X2 S1 S2 S3 A1 A2 A3 Q
0 S3 -5/2 0 -3/2 0 1 3/2 0 -1 0
3 X2 1/2 1 - 1/2 0 0 1/2 0 0 20
0 S2 -1 0 -2 1 0 2 -1 0 50
Zj 3/1 3 -3/2 0 0 3/2 0 0 60
Cj-Zj 5/2 0 3/2 0 0 M-3/2 M M

Now we reach at optimal solution at 1unit of X2 and no any unit of X1

i.e. Min Z=4X1+3X2
Z=4(0)+3( 20)=60
So X1=0 and X2=20 in order to minimize the cost in 60.

7. SOLUTION

Late X1=Power transformers X2=Traction Transformer

a) Formulate the linear programming model

Max Z=50000X1+10000X2
St. 75X1+15X2≤1000
160X1+30X2≤1500

18
 45X1+10X2≤750
X1, X2≥0
b) Solve the problem by using graphical solution

Step 1: Formulate LPP model

Max Z=50000X1+10000X2
St. 75X1+15X2≤1000
160X1+30X2≤1500
45X1+10X2≤750
X1, X2≥0
Step 2: Convert in to equality
Max Z=50000X1+10000X2
St. 75X1+15X2=1000
160X1+30X2=1500
45X1+10X2=750
X1, X2≥0

Step 3: Draw the graph by using intercepts

75X1+15X2=1000 (40/3, 0) and (0, 200/3)
160X1+30X2=1500 (75/8, 0) and (0, 50)
45X1+10X2=750 (50/3, 0) and (0, 75)
X2
75

200/3

50

FR
X1
75/8 40/3 50/3

Step 4: Identify feasibility region

19
Step 5: Identify Corner point
Corner Co-ordinate Max Z=50000X1+10000X2
A (0, 0) 0
B (75/8, 0) 468,750
C 0, 50 500,000
Step 6: Interpret the result in order to maximize the company profit to 500,000 it should be
produce 50 unit of traction transformer.
c) Solve the problem by simplex method

Step1: Formulate LPP model

Max Z=50000X1+10000X2
St. 75X1+15X2≤1000
160X1+30X2≤1500
45X1+10X2≤750
X1, X2≥0
Step2: Standardize the equality
Max Z=50000X1+10000X2+0S1+0S2+0S3
St. 75X1+15X2+S1=1000
160X1+30X2+S2=1500
45X1+10X2+S3=750
X1, X2, S1, S2, and S3≥0
Step 3: Draw the 1st simplex table
Cj 50000 10000 0 0 0
Q
SV X1 X2 S1 S2 S3
13.33
75 15 1 0 0 1000
0 S1 3
0 S2 160 30 0 1 0 1500 9.375
16.66
45 10 0 0 1 750
0 S3 7
Zj 0 0 0 0 0
Cj-Zj 50000 10000 0 0 0

So X1 is entering variable and S2 leaving variable

New X1=Old S2*1/160
1 3/16 0 1/160 0 75/8

20
New S1=Old S1-New X1(PE)
0 15/16 1 -15/32 0 2375/8
New S3=Old S3-New X1(PE)
0 25/16 0 -9/32 1 2625/8
Step 4: Construct 2nd simplex table
Cj 50000 10000 0 0 0
Q
SV X1 X2 S1 S2 S3
316.6
0 15/16 1 -15/32 0 2375/8
0 S1 7
50000 X1 1 3/16 0 1/160 0 50 50
0 S3 0 25/16 0 -9/32 1 2625/8 210
Zj 50000 9375 0 625/2 0 468750
Cj-Zj 0 625 0 -625/2 0
So X2 is entering variable and X1 leaving variable
New X2=Old X1*16/3
16/3 1 0 1/10 0 50
New S1=Old S1-New X2*15/16
-5 0 1 -1/2 0 250
New S3=Old S3-New X2*25/16
-25/3 0 0 -1/3 1 250
Cj 50000 10000 0 0 0
Q
SV X1 X2 S1 S2 S3
316.
-5 0 1 -1/2 0 250
0 S1 67
10000 X2 16/3 1 0 1/30 0 50 50
0 S3 -25/3 0 0 -1/3 1 250 210
160000/
10000 0 1000/3 0 500000
Zj 3
Cj-Zj -10000/3 0 0 -1000/3 0

Now we are reach at a maximum point that is profit 500000 only produce 10000 unit of X2.

21
8. SOLUTION

Let X1=Product X and X2=Product Y

a) Formulate the linear programming Model

Max Z=50X1+30X2
2X1+X2≥18
X1+X2≥12
3X1+2X2≤34
X1, X2≥0
b) Solve by using graphical solution method

Step 1: Formulate LPP model

Max Z=50X1+30X2
2X1+X2≥18
X1+X2≥12
3X1+2X2≤34
X1, X2≥0
Step 2: Change in to equality
Max Z=50X1+30X2
2X1+X2=18
X1+X2=12
3X1+2X2=34
X1, X2≥0
Step 3: Draw the graph by using intercepts
2X1+X2=18 (9, 0) and (0, 18)
X1+X2=12 (12, 0) and (0, 12)
3X1+2X2=34 (34/3, 0) and (0, 17)
X2

18
17

12
FR

9 34/3 12 X1

22
Step 4: Identify FR
Step 5: Identify corner Point
Coordinate Value of
Points Z=50X1+30X2
(X1,X2)
A (6, 6) 480
B (10, 2) 560
C (2,14) 520

Step 6: Interpret the result

In order to maximize the profit in to 560 it should be produce 10 units of X1 and 2 unit of X2.
c) Solve by using simplex methods

Step 1: Formulate the linear programming model

Max Z=50X1+30X2
2X1+X2≥18
X1+X2≥12
3X1+2X2≤34
X1, X2≥0
Step 2: Standardize the equation
Max Z=50X1+30X2+0S1+0S12+0S3-MA1-MA2
2X1+X2-S1+A1=18
X1+X2-S2-A2=12
3X1+2X2+S3≤34
Where S1, S2 –Surplus
S3–Slack
A1, A2–Artificial variable
Step 3: Construct the 1st simplex table
Cj 50 30 0 0 0 -M -M
SV X1 X2 S1 S2 S3 A1 A2 Q
-M A1 2 1 -1 0 0 1 0 18 9
-M A2 1 1 0 -1 0 0 1 12 12
0 S3 3 2 0 0 1 0 0 34 34/3
Zj -3M -2M M M 0 -M -M -30M
Cj-Zj 50+3M 30+3M -M -M 0 0 0

X1 entering variables & A1 is leaving variable.

New X1=Old A1*1/2
23
 1 1/2 -1/2 0 0 0 9
New A2=Old A2-New X1*1
0 1/2 1/2 -1013
New S3=Old S3-New X1*3
0 1/2 3/2 0 1 0 7
Step 4: Construct the 2nd simplex table
Cj 50 30 0 0 0 -M
SV X1 X2 S1 S2 S3 A2 Q
|-
X1 1 1/2 -1/2 0 0 0 9
50 18|
-M A2 0 1/2 1/2 0 0 1 3 6
14/
S3 0 1/2 3/2 1 1 0 7
0 3
-
Zj 50 25-M/2 0 0 -M 450-3M
25+M/2
Cj-Zj 0 5+M/2 25+M/2 0 0 0

S1 is entering variable & S3 is leaving variable.

New S1=Old S3*2/3
0 1/3 1 0 2/3 0 14/3
New X1=Old X1-New S1*-1/2
1 12/3 0 0 1/3 0 34/3
New A2=Old A2-New S1*-1/2
0 1/3 0 -1 -1/3 1 2/3
Construct the 3rd simplex table
Cj 50 30 0 0 0 -M
SV X1 X2 S1 S2 S3 A2 Q
50 X1 1 2/3 0 0 1/3 0 34/3 17
-M A2 0 1/3 0 -1 -1/3 1 2/3 18
0 S1 0 1/2 1 0 2/3 0 14/3 28/3
Zj 50 100/3-M/3 0 M 50/3+M/3 M 1700/3-2M/3
[[
Cj-Zj 0 -10/3+M/3 0 -M -50/3-M/3 0

Step 5: X2entering variable and A2 leaving variable.

New X2=Old A2*3
0 1 0 -3 -1 2

24
New X1=Old X1-New X2*2/3
1 0 0 2 1 10
NewS1=Old S1-New X2*1/3
0 0 1 1 1 4
Cj 50 30 0 0 0
SV X1 X2 S1 S2 S3 Q
50 X1 1 0 0 2 1 10
30 X2 0 1 0 -3 -1 2
0 S1 0 0 1 1 1 4
Zj 50 30 0 10 20 560
Cj-Zj 0 0 0 -10 -20

Now we reach at optimal Solution that means all Cj-Zj≤0 i.e. we should produce 10 unit of X1& 2
unit of X2 to maximize the profit 560.

9. SOLUTION

Let X1=liquid product and X2=dry product

a) Formulate the linear programming model

Min Z=3X1+2X2
St. 5X1+X2≥10
2X1+2X2≥12
X1+4X2≥12
X1, X2≥0
b) Solve by using graphical solution

Step 1: Formulate LPP model

Min Z=3X1+2X2
St. 5X1+X2≥10
2X1+2X2≥12
X1+4X2≥12
X1, X2≥0
Step 2: Change in to equality
Min Z=3X1+2X2
St. 5X1+X2=10
2X1+2X2=12
X1+4X2=12
X1, X2≥0

25
Step 3: Draw the graph by using intercept.
5X1+X2=10 (2, 0) and (0, 10)
2X1+2X2=12 (6, 0) and (0, 6)
X1+4X2=12 (12, 0) and (0, 3)
X
2

10

FR
6

2 6 12 X1
Step 4: Find the feasible region
Step 5: Identify the corner point
Coordinate Value of
Points Z=3X1+2X2
(X1,X2)
A (12, 0) 36
B (4, 2) 16
C (1, 5) 13
[
D (0, 10) 20

Step 6: Interpret the result

In order to minimize the cost in to 13 we should be produce 1 unit of X1 and 5 unit of X2
c) Solve by using simplex method

Formulate LPP model

Min Z=3X1+X2
St. 5X1+X2≥10
2X1+3X2≥12
X1+4X2≥12

26
X1, X2≥0
Step 2: Standardize the problem
Min Z=3X1+X2+0S1+0S2+0S3+MA1+MA2+MA3
St. 5X1+X2-S1+MA1=10
2X1+3X2-S2+MA2=12
X1+4X2-S3+MA3=12
X1, X2, 0S1, S2, S3, A1, A2 and A3≥0
Step 3: Construct 1st simplex table
Cj 3 2 0 0 0 M M M
SV X1 X2 S1 S2 S3 A1 A2 A3 Q
M A1 5 1 -1 0 0 1 0 0 10 2
M A2 2 2 0 -1 0 0 1 0 12 6
1
A3 1 4 0 0 -1 0 0 1 12
M 2
Zj 8M 7M -M -M -M M M M 34M
Cj-Zj 3-8M 2-7M M M M 0 0 0
X1 is entering variable and A1 is leaving variable
Construct 2nd simplex table
Cj 3 2 0 0 0 M M M
SV X1 X2 S1 S2 S3 A1 A2 A3 Q
3 X1 1 1/5 -1/5 0 0 1/5 0 0 2 10
M A2 0 8/5 2/5 -1 0 -2/5 1 0 8 5
50/1
A3 0 19/5 1/5 0 -1 -1/5 0 1 10
M 9
Zj 3 3/5+27M/5 3M/5-3/5 -M -M 3/5-3M/5 M M 6+18M
Cj-Zj 0 7/5-27M/5 3/5+-3M/5 M M -3/5+8M/5 0 0
X2 entering variable and A3 is leaving variable.
Construct 3rd simplex table.
Cj 3 2 0 0 0 M M M
SV X1 X2 S1 S2 S3 A1 A2 A3 Q
3 X1 1 0 -4/19 0 1/19 4/19 0 -1/19 28/19 28
M A2 0 0 6/19 -1 8/19 -6/19 1 -8/19 72/19 9
2 X2 0 1 1/19 0 -5/19 -1/19 0 5/19 50/19 -10
Zj 3 2 -10/19+6M/19 -M -7/19+8M/19 10/19-6M/19 M 7/19-8M/19 184/19+72M/19
Cj-Zj 0 0 10/19-6M/19 M 7/19-8M/19 10/19+2M/19 0 -7/19+27M/19
S3 is entering variable and A2 is leaving variable

27
Construct 4th simplex table
Cj 3 2 0 0 0 M M M
SV X1 X2 S1 S2 S3 A1 A2 A3 Q
3 X1 1 0 -1/4 1/8 0 1/4 -1/8 0 1 1
0 S3 0 0 3/4 -19/8 1 -3/4 19/8 -1 9 9
2 X2 0 1 1/4 -5/8 0 -1/4 5/8 0 5 5
Zj 3 2 -1/4 -7/8 0 -1/4 7/8 0 13 13
Cj-Zj 0 0 1/4 7/8 0 M-1/4 M-7/8 M
Now we reach at optimal solution at 1unit of X1 and 5 unit of X2 i.e. Min Z=3X1+X2
Z=3(1)+1( 5)=13
So X1=1 and X2=5 in order to minimize the cost in 13.

10. SOLUTION

a) How should the cars be assigned to the customer so as to minimize the distance
traveled? Using Hungarian Method.

A B C D E
A 160 130 175 190 200 130
B 135 120 130 160 175 120
C 140 110 155 170 185 110
D 50 50 90 80 110 50
E 55 35 70 80 105 35

A B C D E

A 30 0 45 60 70

B 15 0 10 40 55

C 30 0 45 60 75

D 0 0 40 30 60

E 20 0 35 45 70

0 0 10 30 55
A B C D E
A 30 0 35 30 15
B 15 0 0 10 0
C 30 0 35 30 20

28
 D 0 0 30 0 5
E 20 0 25 15 15

A B C D E
A 15 0 20 15 0
B 15 15 0 10 0
C 15 0 20 15 5
D 0 15 30 0 5
E 5 0 10 0 0

A B C D E
A 15 0 20 15 0
B 15 15 0 10 0
C 15 0 20 15 5
D 0 15 30 0 5
E 5 0 10 0 0

b) What the total cost of optimum assignment

D=A, B=C, E=D, C=B and A=E

TOTAL COST=110+200+50+130+80=570

11. SOLUTION

a) Find an initial feasible solution using VAM and Least cost Method

W1 W2 W3 ss
1 8 9
15
F1 0 15 0
5 2 2 3 20
F2 0 0
6 7 4 35
F3 30 0
7 6 8 35
F4 25 6 4 4
2 26 49
100/100
D 5
0 6 19

0 15

W1 W2 W3 ss

29
 1 8 9
15
F1 0 15 1 1 1 1 9 -
2
F2 5 2 0
3 20 1 - - - - -
F3 6 7 4 30 35 2 2 - - - -
F4 7 25 6 6 8 4 35 1 1 1 2 8 8
2 26 49
100/100
D 5
1 4 1
1 1 4
3 2 1
- 2 1
- - 1
- - 8
TC =7*25+2*20+9*15+4*30+6*6+8*4=538
b) Find the optimal solution using MODI method based on least cost

8 7 9
W1 W2 W3 Capacity
1 8 9 1
0 15
F1 X X 5
5 2 2 3
20
F2 X 0 X
6 7 4 3
30
F3 25 X 0
F4 7 25 6 6 8 4 35
2 4
100/100
D 25 6 9
We calculate Raw & Column index for occupied cell
R1=is always zero
C13=R1+K3 9=0+K3 K3=9
C22=R2+K2 2=R2+7 R2=-5
C33=R3+K3 4=R3+9 R3=-5
C41=R4+K1 7=-1+K1 K1=8
C42=R4+K2 6=-1+K2 K2=7
C43=R4+K3 8=R4+9 R4=-1
Cell evaluation for unoccupied cell
CE11=C11-R1-K1 =10-0-8=2
CE12=C12-R1-K2=8-0-7=1

30
CE21= C21-R2-K1=5+5-7=2
CE23= C23-R2-K3=3-+5-9=-1
CE31= C31-R3-K1=6+5-8=3
CE32= C32-R3-K2=7+5-7=5
At C23 there is penalty, so it is not optimal solution. We check it using stepping stone. W add 4
to positive cell and minus from negative cell.
Capaci
W1 W2 W3 ty
F 1 8 9 1
0 15
1 X X 5
F 5 2 2 - 3 X +
20
2 X 0
F 6 7 4 3
30
3 X X 0
F 7 2 6 + 8
35
4 5 6 4 -
D 2 2 4 4 100/10
D 5 6 9 9 0

New modified matrix

9 8 9
Capacit
W1 W2 W3 y
1 8 9 1
0 15
0 F1 X X 5
5 2 1 3 4
20
-6 F2 X 6
6 7 4 3
30
-5 F3 X X 0
7 2 1 8
6 35
-2 F4 5 0 X
D 2 4
100/100
D 25 6 9
We calculate Raw & Column index for modified cell
C13=R1+K3 9=0+K3 K3=9
C22=R2+K2 2=-6+K2 K2=8
C23=R2+K3 3=R2+9 R2=-6

31
C41=R4+K1 7=-2+K1 K1=9
C33=R3+K3 4=R3+9 R3=-5
C42=R4+K2 6=R4+8 R4=-2
We calculate cell for unoccupied
CE11=C11-R1-K1 =10-0-9=1
CE12=C12-R1-K2=8-0-8=0
CE21= C21-R2-K1=5+5-9=2
CE31= C31-R2-K1=6+5-9=2
CE32= C32-R2-K3=7+5-8=4
CE43= C43-R4-K3=8+2-9=1
Now we arrive at optimal solution because all values are positive
9 8 9
Capacit
W1 W2 W3 y
1 8 9 1
0 15
0 F1 1 0 5
5 2 1 3 4
20
-6 F2 2 6
6 7 4 3
30
-5 F3 2 4 0
7 2 6 1 8
35
-2 F4 5 0 1
D 4
100/100
D 25 26 9
Therefore solution
TOTAL COST=(9*15)+(16*2)+(4*3)+(4*30)+(3*25)+(6*10)
= 135+32+12+120+175+60=534

32