Operations research 1

Problem1
Upon Graduating from college, you have been offered a high paying position as president of the
logo foundation.
Your company produces chairs (each requiring 2 square blocks and one rectangular block) as
well as tables( each requiring two square blocks and 2 rectangular blocks) and has available
resources consisting of 8 rectangular blocks and 6 square ones. Assume chairs and tables each
sell for 5$ and 7$ respectively, and that your company sells all of what it produces. Set up an LP
whose objective is to maximize your company’s revenue.
Answer:
Products Square blocks x Rectangular Blocks y Price $
Chairs 2 1 5
Tables 2 2 7
8 6

Maximize Z = 8x + 6y
Subject to,
2X + Y <= 5
2X + 2Y <= 7

Problem2
Formulate the following as a linear programming problem. A green house operator plans to bid
for the job of providing flowers for city parks. He will use tulips, daffodils, and flowering shrubs
in three types of layouts. A type 1 layout uses 30 tulips,20 daffodils and 4 flowering shrubs. A
type 2 layout uses 10 tulips, 40 daffodils and 3 flowering shrubs. A type 3 layout uses 20 tulips,
50 daffodils and 2 flowering shrubs. The net profit is $50 for each type 1 layout,$30 for each type
2 layout, and $60 for type 3 layout. He has 1000 tulips, 800 daffodils and 100 flowering shrubs.
How many layouts of each type should be used to yield maximum profit?
Solutions:
Layouts Tulips X1 Daffodils X2 Flowering Shrubs
X3
1 30 20 4 50
2 10 40 3 30
3 20 50 2 60
 1000 800 100

Maximize Z = 1000 X1 + 800X2 + 100 X3

Subject to,
30X1 + 20 X2 + 4 X3 <= 50
10X1 + 40 X2 + 3X3 <= 30
20 X1 + 50 X2 + 2 X3 <= 60
Problem3
Write the LP in standard form
Objective Function:
Max z= X1+X2+3X3-X4+5X5
Subject To:
X1+X2-2X3+X4+2X3 =-3
-X1-2X2+3X3+X4-X5 ≥4
-X1+X2-X3+2X4+X5 ≤1
X1,X2 ≥0,X3urs,X4,X5≤0

Solution:
Max z= X1+X2+3X3-X4+5X5 – S1 + S2
Subject to,
-X1 – X2 + 2(X3’-X3”) – (X4’-X4”) - 2(X3’-X3”) = 3
- X1 – 2X2 + 3(X3’-X3”) + (X4’-X4”) – (X5’ – X5”) – S1 = 4
-X1 + X2 - (X3’-X3”) + 2(X4’-X4”) + (X5’ – X5”) + S2 = 1
X1,X2,X3’,X3”,X4’,X4”,X5’,X5”,S1,S2 >= 0
Problem4
Solve the problem using simplex algorithm
Max Z= 6X+6Y
S.T
X+3Y≤2
2X+2Y≤5
X,Y≥0
Solutions:
Max Z = 6X + 6Y + S1 + S2
Subject to,
X + 3Y + S1 = 2
2X + 2Y + S2 = 5
-6X – 6Y + Z = 0
X,Y >= 0
X Y S1 S2 Z C
1 3 1 0 0 2
2 2 0 1 0 5
-6 -6 0 0 1 0

X Y S1 S2 Z C Ratio
1 3 1 0 0 2 2
2 2 0 1 0 5 2.5
-6 -6 0 0 1 0 0

X Y S1 S2 Z C Ratio
1 3 1 0 0 2 2 R2 - 2R1
0 -4 -2 1 0 1 -1.5
-6 -6 0 0 1 0 0

X Y S1 S2 Z C Ratio
1 3 1 0 0 2 2 R3 + 6R1
0 -4 -2 1 0 1 -1.5
0 12 6 0 1 12 12

X Y S1 S2 Z C Ratio
1 0 1 0 0 2 2 C2 - 3C3
0 2 -2 1 0 1 -1.5
0 -6 6 0 1 12 12
X=2
2Y = -1.5 –Y = 2/3
12Z = 12 Z = 1
Problem5
Solve the following using big M and 2-phase simplex
Max Z = 2X1+5X2
S.T
3X1+2X2≥6
2X1+X2≤2
X1,X2≥0
Solution:
Z = 2X1 + 5X2 + 0S1 + 0S2 – Ma1
3X1 + 2X2 – S1 + a1 = 6
2X1 + X2 + S2 = 2
X1,X2,S1,S2,a1 >= 0
Now,

Cj 2 5 0 0 M (-) Ratio
Basis Cb Xb X1 X2 S1 S2 a1
a1 m (-) 6 3 2 -1 0 1 2
S2 0 2 2 1 0 1 0 1
-3M-2 -2M-5 M 0 0
Zj = -3M
Now S2 is our out going vector.
Key element is 2.
Cj 2 5 0 0 M (-) Ratio
Basis Cb Xb X1 X2 S1 S2 a1
a1 m (-) 3 3 2 -1 0 1 2
X1 2 1 1 1/2 0 1/2 0 1
 Cj 2 5 0 0 M (-) Ratio
Basis Cb Xb X1 X2 S1 S2 a1
a1 m (-) 3 0 1.5 -1 -1.5 1 1.5
X1 2 1 1 1/2 0 ½ 0 2
Delta j 0 -4- M 1 0
1.5M

Cj 2 5 0 0 M (-) Ratio
Basis Cb Xb X1 X2 S1 S2 a1
a1 m (-) 2 0 1 -0.66 -1 0.66 1.5
X1 2 1 1 1/2 0 ½ 0 2
Delta j 0 -4- M 1 0
1.5M

Cj 2 5 0 0 M (-) Ratio
Basis Cb Xb X1 X2 S1 S2 a1
X2 5 2 0 1 -0.66 -1 0.66 1.5
X1 2 0 1 0 1/3 1 -1/3 2
0 0 -8/3 -3 8/3+M
Zj = 10
Cj 2 5 0 0 M (-) Ratio
Basis Cb Xb X1 X2 S1 S2 a1
X2 5 2 0 1 -0.66 -1 0.66 -2
X1 2 0 1 0 1/3 1 -1/3 0

Cj 2 5 0 0 M (-) Ratio
Basis Cb Xb X1 X2 S1 S2 a1
S2 0 -2 0 -1 0.66 1 -0.66 -2
X1 2 2 1 1 -1/3 0 1/3 0
Del j 0 -3 -2/3 0 2/3+M

Zj = 4

Problem6
formulate the transportation problem and find a BFS for the problems
a. using northwest method
b. using min-cost method
c. using Vogel method
Cost per Unit Distributed
Destination (Product)
1 2 3 4 Supply
1 21 27 28 14 60
Source 40 19 50 33 70
2
3 47 30 37 21 20
Demand 50 40 20 40

C-Using Vogels Method,

Sources 1 2 3 4 Supply Row penality
1 21 27 28 14 60 6
2 40 19 50 33 70 14
3 47 30 37 21 20 9
Demand 50 40 20 40
C penalty 19 8 9 7

Sources 1 2 3 4 Supply Row penality

1 21 27 28 14 60 7
2 40 19 50 33 30 7
3 47 30 37 21 20 16
Demand 50 0 20 40
C penalty 19 0 9 7

Sources 1 2 3 4 Supply Row penality

1 21 27 28 14 60 7
2 40 19 50 33 30 7
3 47 30 37 21 0 0
Demand 50 0 20 20
C penalty 19 0 22 19

Sources 1 2 3 4 Supply Row penality

1 21 27 28 14 60 7
2 40 19 50 33 10 10
3 47 30 37 21 0 0
Demand 50 0 20 0
C penalty 19 0 22 0

Sources 1 2 3 4 Supply Row penality

1 21 27 28 14 60 7
2 40 19 50 33 0 0
3 47 30 37 21 0 0
Demand 40 0 20 0
C penalty 21 0 28 0

Sources 1 2 3 4 Supply Row penality

1 21 27 28 14 20 7
2 40 19 50 33 0 0
3 47 30 37 21 0 0
Demand 0 0 20 0
C penalty 0 0 28 0

Sources 1 2 3 4 Supply Row penality

1 21 27 28 14 0 0
2 40 19 50 33 0 0
3 47 30 37 21 0 0
Demand 0 0 0 0
C penalty 0 0 0 0
B- Using Min Cost Method

Sources 1 2 3 4 Supply
1 21 27 28 14 60
2 40 19 50 33 70
3 47 30 37 21 20
Demand 50 40 20 40

Sources 1 2 3 4 Supply
1 21 27 28 14 20
2 40 19 50 33 70
3 47 30 37 21 20
Demand 50 40 20 0

Sources 1 2 3 4 Supply
1 21 27 28 14 20
2 40 19 50 33 30
3 47 30 37 21 20
Demand 50 0 20 0

Sources 1 2 3 4 Supply
1 21 27 28 14 0
2 40 19 50 33 30
3 47 30 37 21 20
Demand 30 0 20 0

Sources 1 2 3 4 Supply
1 21 27 28 14 0
2 40 19 50 33 30
3 47 30 37 21 0
Demand 30 0 0 0

Sources 1 2 3 4 Supply
1 21 27 28 14 0
2 40 19 50 33 0
3 47 30 37 21 0
Demand 0 0 0 0

A- Using Northwest method

Sources 1 2 3 4 Supply
1 21 27 28 14 10
2 40 19 50 33 70
3 47 30 37 21 20
Demand 0 40 20 40
Sources 1 2 3 4 Supply
1 21 27 28 14 0
2 40 19 50 33 70
3 47 30 37 21 20
Demand 0 30 20 40

Sources 1 2 3 4 Supply
1 21 27 28 14 0
2 40 19 50 33 40
3 47 30 37 21 20
Demand 0 0 20 40

Sources 1 2 3 4 Supply
1 21 27 28 14 0
2 40 19 50 33 20
3 47 30 37 21 20
Demand 0 0 0 40

Sources 1 2 3 4 Supply
1 21 27 28 14 0
2 40 19 50 33 0
3 47 30 37 21 20
Demand 0 0 0 20

Sources 1 2 3 4 Supply
1 21 27 28 14 0
2 40 19 50 33 0
3 47 30 37 21 0
Demand 0 0 0 0