JIMMA UNIVERSTY

JIT

FACULTY OF MECHANICAL ENGINEERING

OPERATIONAL RESEARCH ASSIGNMENT TWO

NAME IDNO

Alpha Dawit…………..RU3976/11

GROUP 2

SUB.TO: Mr. AHMED MOHAMMED

Sub.Date:25/12/2022
Name: Operations Research
Assignment 2: LPP modeling and Solution
Total marks: 5%

1. A company manufactures four products A, B, C, and D. The profits are Birr 13, Birr
15, Birr 14 and Birr 14.5 respectively. The firm has four machines and the required
processing time in minutes for each machine on each product is given below:
Products Machin
A B C D e
minute
1 4 3 5 - 2000
Machine 2 2 2 4 4 2500
s 3 - 2 5 2 1800
4 3 5 5 3 1500
Capacity 100≤A≤150 200 250 50

Machines 1, 2, 3 and 4 have 2000, 2500, 1800, and 1500 machine-minutes

respectively. The firm must manufacture at least 100 A’s, 200 B’s, 250C’s and 50 D’s
but not more than 150 A’s. Set up an LP model and also express it in a matrix form.

Soln.
Let; X1 represent product A's process time
X2 ..............................B
X3...............................C
X4...............................D
Max. Z = 13X1 + 15X2 + 14X3 + 14.5X4
Sub. to; 4 X1 + 3 X2 +5 X3 ≤ 2000
2 X1 +2 X2 +4 X3 +4X4 ≤ 2500
2 X2 +5 X3 +2X4 ≤ 1800
3 X1 +5 X2 +5 X3 +3X4 ≤ 1500
X1 ≤150
X1 ≥50
 X2 ≥200
X3 ≥250
X4 ≥50
X1 , X2 , X3 , X4 ≥ 0
Matrix form of the above equations let us use Simplex Method;
Max. Z = 13X1 + 15X2 + 14X3 + 14.5X4 +0S1+0S2+0S3+0S4+0S5+0S6+0S7+0S8 +0S9
Sub. to; 4 X1 + 3 X2 +5 X3 + S1 = 2000
2 X1 +2 X2 +4 X3 +4X4 + S2 = 2500
2 X2 +5 X3 +2X4 + S3 = 1800
3 X1 +5 X2 +5 X3 +3X4 + S4 = 1500
X1 + S5 = 150
X1 + S6 = 50
X2 +S7 = 200
X3 +S8 = 250
X4 +S9 = 50
X1 , X2 , X3 , X4 ≥ 0
S1, S2, S3,S4,S5,S6,S7,S8 ≥ 0
Initial Tableau
Cj 13 15 14 14. 0 0 0 0 0 0 0 0 0
5
BC BV X1 X2 X3 X4 S1 S2 S3 S4 S5 S6 S7 S8 S9 Q
0 S1 4 3 5 0 1 0 0 0 0 0 0 0 0 200
0
0 S2 2 2 4 4 0 1 0 0 0 0 0 0 0 250
0
0 S3 0 2 5 2 0 0 1 0 0 0 0 0 0 180
0
0 S4 3 5 5 3 0 0 0 1 0 0 0 0 0 150
0
0 S5 1 0 0 0 0 0 0 0 1 0 0 0 0 150
 0 S6 1 0 0 0 0 0 0 0 0 1 0 0 0 50
0 S7 0 1 0 0 0 0 0 0 0 0 1 0 0 200
0 S8 0 0 1 0 0 0 0 0 0 0 0 1 0 250
0 S9 0 0 0 1 0 0 0 0 0 0 0 0 1 50
Zj
Cj-Zj

2. A garment product producing firm has manufacturing plants in Wolkite, Agaro and Seqa.
The daily production of each of these manufacturing plants is found to be 500, 300, and 100
units per day respectively. Every day the firm must fulfill the needs of its two retailers
located in Addis Ababa and Jimma which have daily demands of 550 and 350 respectively.
The aggregate cost incurred as a result of the production and transportation of each unit of
the product is different from plant to plant and their value including the selling expenses per
unit at each of the retailing shop is shown in the table below. The selling price per unit is 100
Birr and 80 Birr in Addis Ababa and Jimma respectively. Use graphical method to determine
the amount of units of the product to be dispatched from each plant to be sold at each
retailing shop per day in order to maximize the total profit. Also find the total profit per day.
Sum of production, transportation and selling costs
Plants (Birr per unit)
Retailers
Addis Ababa Jimma
Wolkite 80 50
Agaro 60 70
Seqa 90 45

Soln.:
Let us subtract the cost from the selling price and construct a new table (profit table)
Wolkite to A.A = 100-80 = 20birr Wolkite to Jimma = 80-50= 30
Agaro to A.A = 100-60 = 40 Agaro to Jimma = 80-70= 10
Seqa to A.A = 100-90 = 10 Seqa to Jimma = 80-45= 35

Addis Ababa Jimma Supply

Wolkite 20 30 500
Agaro 40 10 300
Seqa 10 35 100
Demand 550 350
 Addis Ababa

X1 550-(x1+x2)
20 x2 40 10

Wolkite Agaro Seqa

30 300-x2 10 35
500-x1 350-(500-x1+300-x2)

Jimma

Solving:
Z= 3x1 +11x2 + 1450
x1 ≤ 500
x2 ≤ 300
x1 + x2 ≤ 550
x1 + x2 ≥ 450

Point A (150, 300); Z= 5200

Point B (250, 300); Z= 5500 ..........solution x1=250, x2=300
Point C (500, 50); Z= 3500
Point D (500, 0); Z= 2950
Point E (450, 0); Z= 2800
Product to be dispatched at Addis Ababa and Jimma
Addis Ababa Jimma Supply
Wolkite 250 250 500
Agaro 300 0 300
Seqa 0 100 100
Demand 550 350

Therefore, the total profit will be = 250*20+300*40+250*30+100*35 = 28,000 Birr

3. Apply the necessary steps and solve the following linear programming problems

a. Maximize Z = 4x1+5x2-3x3+50,
Subject to x1 + x2 + x3 = 10
x1 – x2 ≥1
2x1 + 3x2 + x3 ≤ 40,
x1, x2,x3 ≥0
Standard form

Leave the fixed cost and add it finally.

Z= 4X1+5X2-3X3+0S1+0S2-MA1-MA2

Subject to: X1+X2+X3+A1=10

X1-X2-S1+A2=1

2X1+3X2+X3+S2=40

Cj 4 5 -3 0 0 -M -M
BC X1 X2 X3 S1 S2 A1 A2 Q RR
-M A1 1 1 1 0 0 1 0 10 10
-M A2 1 -1 0 -1 0 0 1 1 1
0 S2 2 3 1 0 1 0 0 40 20
Zj -2M 0 -M M 0 -M -M -11M
Cj-Zj 4+2M 5 -3+M -M 0 0 0

Cj 4 5 -3 0 0 -M
BC X1 X2 X3 S1 S2 A1 Q RR
-M A1 0 2 1 1 0 1 9 4.5
4 X1 1 -1 0 -1 0 0 1 -1
0 S2 0 5 1 2 1 0 38 38/5
Zj 4 -2M-4 -M -M-4 0 -M -9M+4
Cj-Zj 0 9+2M -3+M M+4 0 0

Cj 4 5 -3 0 0
BC X1 X2 X3 S1 S2 Q RR
5 X2 0 1 1/2 1/2 0 4.5
4 X1 1 0 1/2 -1/2 0 5.5
0 S2 0 0 -3/2 -1/2 1 31/
2
Zj 4 5 4.5 0.5 1 44.
5
Cj-Zj 0 0 -7.5 -0.5 -1

There is no positive number in the Cj-Zj row. Implies the solution is optimum with value:

X1 = 5.5, X2 = 4.5, X3 = 0, S2 = 15.5 (surplus), and Z= 44.5+50 =94.5

b. Minimize Z = x1 – 3x2 + 2x3

Subject to 3x1 – x2 + 2x3 ≥ 7
-2x1 + 4x2 ≤ 12
-4x1 + 3x2 + 8x3 ≤ 10
where x1, x2, x3 ≥ 0

Standard form: Z=X1-3X2+2X3+0S1+0S2+0S3+MA1

Subject to: 3x1 – x2 + 2x3-S1+A1 =7
-2x1 + 4x2 +S2 =12
-4x1 + 3x2 + 8x3 +S3 =10

BC Cj 1 -3 2 0 0 0 M
x1 x2 x3 S1 S2 S3 A1 Q RR
M A1 3 -1 2 -1 0 0 1 7 7/3
0 S2 -2 4 0 0 1 0 0 12 -6
0 S3 -4 3 8 0 0 1 0 10 -5/2
Zj 3M -M 2M -M 0 0 M 7M
Cj-Zj 1-3M -3+M 2-2M M 0 0 0

BC Cj 1 -3 2 0 0 0
x1 x2 x3 S1 S2 S3 Q RR
1 X1 1 -1/3 2/3 -1/3 0 0 7/3 -7
0 S2 0 10/3 4/3 -2/3 1 0 50/3 5
0 S3 0 5/3 32/3 -4/3 0 1 58/3 58/5
 Zj 1 -1/3 2/3 -1/3 0 0 7/3
Cj-Zj 0 -8/3 4/3 1/3 0 0

BC Cj 1 -3 2 0 0 0
x1 x2 x3 S1 S2 S3 Q RR
1 X1 1 0 4/5 -2/5 1/10 0 4 -10
-3 X2 0 1 2/5 -1/5 3/10 0 5 -25
0 S3 0 0 10 -1 -1/2 1 11 -11
Zj 1 -3 -2/5 1/5 -4/5 0 -11
Cj-Zj 0 0 12/5 -1/5 4/5 0

===>this question has no feasible optimal solution. Because all the replacement ratio numbers
are negative, which is impossible.