Operations Research

<<< Previous Linear Programming:PRESENTATION IN TABULAR FORM - (SIMPLEX TABLE) Next >>>

Operations Research (MTH601)
118
Now a question may arise whether the above solution constitutes the best or optimal solution.
Examining the objective function
Z + 2 S2 + 3 S3 = 240,
we observe that the coefficients of the non-basic variables S2 and S3 are positive on the left hand side and this is the
indication to stop the iteration. Hence we conclude that Z = 240 will be the maximum value of Z and the solution set
can be written as
Z* =240
x = 30
y = 30
S1 = 40
S2 = 0
S3 = 0
PRESENTATION IN TABULAR FORM - (SIMPLEX TABLE)
The relevant information of first example may be presented in a concise form as what we call 'Simplex
table' instead of writing down th set of equations in full symbols for the variables in each of the equations. The given
linear programming problem is expressed in a standard form including slack variables. Then we write the
coefficients of the variables and the right hand side in the table.
The above example is presented in the following tabular form. This is the initial table.
RHS
Ratio
Equation
Basic
Coefficient of
S2
S3
No.
Variable
Z
x
y
S1
0
-
1
-3
-5
0
0
0
0
-
1
0
1
0
1
0
0
40
S1
2
0
0
1
0
1
0
30
30
S2
3
0
1
1
0
0
1
60
60
S3
Solution:
Z = 0, S1 = 40, S2 = 30, S3 = 60, x = y = 0
The basic procedure when using the simplex table is the same as before. We give below the steps of the
simplex method that would be applied to prepare the next table from the initial table.
STEP 1
To select the entering basic variable: Consider the first row corresponding to the equation 0 of the table. If the
problem is one to maximize the effectiveness (profit), the variable with the most negative coefficient is selected as
118
Operations Research (MTH601)
119
the new entering basic variable. The column corresponding to the most negative coefficient -5 is 'y' and the same
is marked as a key column indicating that y is the new entering basic variable.
STEP 2
To select the leaving basic variable: Now consider all the rows except the first row. Formulate the ratio in each
row by taking right hand side of each row and dividing by the corresponding element of the key column. The ratios
in this example are 40/0 = , 30/1 = 30, 60/1 = 60. Select the least non-negative ratio. In this example the minimum
non-negative ration corresponds to the row 2 indicating that S2 is the leaving basic variable and this row containing
S2 as the basic variable is marked as a key row. The element at the intersection of key column and key row is called
the key number or pivot number. In this example the key number is 1. If this is not 1, the same can be made 1 by
dividing the same row suitably.
STEP 3
Elimination of coefficients in the key column: Gauss Jordan elimination requires that all the elements in the key
column except the key row should vanish. Suitably multiplying coefficients of the key row and adding the same to
the corresponding coefficients of the other rows achieve this result.
In this example, multiply the key row by 5 and add this resulting row to the row 0. To get rid of the coefficient of y
in the second row, next multiply the key row by 0 and add to the row 1 and similarly multiply the key row by -1 and
add to the row 3 to eliminate the coefficient of y in the third row. So all the key column elements are thus made 0 in
all the rows except the key row. The resulting table is presented. Note that y has entered the basis and S2 has left.
This is the first iteration
y enters the basis and S2 leaves the basis
Iteration I:
RHS
Ratio
Solution
Eqn.
Basic
Coefficient of
S1   S2
S3
No.
Variable
Z
x
y
0
-
1
-3
0
0
5
0
150
-
Z=150
1
0
1
0
1
0
0
40
40
S1=40
S1
2
0
0
1
0
1
0
30
y=30
y
3
0
1
0
0
-1
1
30
30
S3=30
S3
STEP 4
Further improvement of solution: After every iteration, look at the objective function row (row 0). Scan if there is
any negative coefficients among variables in this row for a maximization problem. If there is a negative coefficient,
this is a clear indication that the problem has not reached the maximum value. Still there is a scope of improving the
existing solution. In this example, we have the coefficient of x in the objective function row as -3 (a negative)
indicating that x can be selected as the new entering basic variable. Mark this column as key column and another
iteration is required. So find the ratio in each of the rows 1, 2 and 3. We have, the ratios 40, and 30 as indicated in
the table under the column ratio. Select the row corresponding to least non-negative value (i.e.) 30, (row 3). So S3 is
the leaving variable and this key row is marked and the same procedure of eliminating the coefficients of x in the
119
Operations Research (MTH601)
120
key column is performed by multiplying the key row by 3, -1 and 0 and adding to the row 0, 1 and 2
respectively. The result is presented in the table below.
STEP 5
Stopping rule: The row 0 has all coefficients of the variables as non-negative. If there is no negative coefficient in
this row, this is an indication that the problem has reached the maximum value and this is the optimal solution to the
linear programming problem.
Note: If the problem is one of minimization subject to constraints of < sign, the criterion for selecting the entering
variable is to pick the variable in the objective row with the most positive coefficient. It all of them are negative or
0, this suggests that the present solution is the optimum.
120
Operations Research (MTH601)
121
REVIEW QUESTIONS
1.
A manufacturer has two products P1 and P2 both or which are produced in two steps by machines
M1 and M2. The process times per hundred for the products on the machines are:-
Products
M1
M2
Contribution
(per 100 units)
4
5
Rs. 10
P1
5
2
Rs. 5
P2
Available hrs
100
80
The manufacturer is in a market upswing and can sell as much as he can produce of both products.
Formulate the mathematical model and determine optimum product mix using simplex method.
2.
The ABC company, a manufacturer of test equipment has three major departments for its
manufacture of X-10 model and X-20 model. Monthly capacities are given as follows:-
Time required
per unit
Hours available
X-10 Model
X-20 Model
this month
Main Frame
4.0
2.0
1,600
Department
Electrical Wiring
2.5
1.0
1,200
Department
Assembly Department
4.5
1.5
1,600
The contribution of the X-10 model is Rs. 40/- each and the contribution of the X-20 model is Rs. 10/- each.
Assuming that the company can sell any quantity of either product due to favorable conditions, find:
(i) the optimal output for both models with the help of simplex method
(ii) the highest possible contribution for this month.
(iii) the slack time in the three departments.
3.
A manager produces three items A, B and C. He has the possibility of applying two strategies -
produce all the three items or any two of them. Products A and C pass through shops I and II, whereas B is
further processed in shop III. Each shop has limited available hours. Hours available in shops I, II and III
are 162 hours, 189 hours and 5 hours respectively. Profit per unit from A, B and C is Rs. 27/-, Rs. 29/- and
Rs. 25/- respectively. The following table gives the processing time of different items in different shops.
Items
Shops
A
B
C
I
27
12
12
II
27
15
25
121
Operations Research (MTH601)
122
III
0
3
0
Find the optimum production of A, B and C so as to maximize profit.
4.
The ABC manufacturing company can make two products P1 and P2. Each of the products requires
time on a cutting machine and a finishing machine.
Product
P1
P2
Cutting hours (per unit)
2
1
Finishing hours (per unit)
3
3
Profit per unit
Rs. 6
Rs. 4
Maximum sales (unit per week)
-
200
The number of cutting hours available per week is 390 and number of finishing hours available per week is
810. How much should be produced of each product in order to achieve maximum profit for the company?
5.
A manufacturer can produce three products A, B and C which pass through different machines M1,
M2 and M3. Available machines for each product and the requirement of machine time for each product is
given in the matrix below.
Machine time
Products
Available time
in hours
A
B
C
in hours
1
2
2
1,900
M1
3
2
4
2,100
M2
3
2
-
1,500
M3
If the profit of each unit of A, B and C is respectively Rs. 5, Rs. 4 and Rs. 6, find how many units of each
product should be produced so that the profit will be maximum.
6.
A firm produces 3 products A, B and C using same type of materials L, M, and N. The specific
consumption of each material for unit production is given in the table. The profits of A, B and C are
respectively Rs. 70, Rs. 50 and Rs. 60.
Material
Quantity required per unit
Available
of production
Material
2
1
3
80
L
4
4
1
240
M
3
4
2
160
N
122
Operations Research (MTH601)
123
(a)
Find the suitable production programme so as to maximize the profit.
(b)
What type of surplus material would be available? Can you utilize materials?
(c)
Find the production pattern (revised) and profit theorem.
7.
A material manufacturing firm has discontinued production of a certain unprofitable product line.
This created considerable excess production capacity. Management is considering to devote this excess
capacity to one or more of three products; call them products 1, 2 and 3. The available capacity on the
machines which limit output is summarized in the following table.
Available time
Machine type
(in machine-hour per week)
Milling machine
250
Lathe
150
Grinder
50
The number of machine-hours required for each unit of the respective products is given below.
Productivity (in machine hours per unit)
Machine type
Product 1  Product 2
Product 3
Milling machine
8
2
3
Lathe
4
3
0
Grinder
2
-
1
The unit profit would be Rs. 20, Rs. 6 and Rs. 8 respectively for products 1, 2 and 3. Find how much of
each product the firm should produce in order to maximize profit.
8.
A factory produces three products, which are processed through three different stages. The time
required to manufacture one unit of each of the three products and the daily capacity of the stages are given
in the following table.
Time per unit in minutes
Stage capacity
Stage
Product 1  Product 2  Product 3
(minutes)
1
1
2
1
430
2
3
-
2
460
3
1
4
-
420
Profit per
3
2
5
unit (Rs.)
(i)
Set the data in a simplex table.
(ii)
Find the table of optimum solution.
(iii)
State from the tale-maximum profit, production pattern and surplus capacity of any stage.
123
Operations Research (MTH601)
124
(iv)
What is the meaning of the shadow price? Where is it shown in the table? Explain it in respect
of resources of stages having
(v)
How many units of other resources will be required to completely utilize the surplus resource?
9.
Solve the following problem using simplex method:
Maximize
x0 = 2x1 + 3x2 + 4x3
Subject to
2x1 + x2 + 2x3 50
x1 + 3x2 + x3 25
x1 + 2x2 + x3 26
x2 , x3 0
x1 ,
10.
A furniture company can produce four types of chairs. Each chair is first made in the carpentry
shop and then varnished, waxed and polished in the finishing shop. Manhours required in each shop are:
Chair type
1
2
3
4
Carpentry shop
4
9
7
10
Finishing shop
1
1
3
40
Contribution per
12
20
18
40
chair-Rs.
Total number of man-hours available per month in carpentry and finishing shops are 6000 and 4000
respectively. Assuming abundant the number of chairs of different type produced so that profit is
maximized using the simplex method.
11.
A stereo equipment manufacturer can produce two models A and B of 40 and 80 watts total music
power each. Each model passes through three different manufacturing divisions 1, 2 and 3 where model A
takes 4, 2.5 and 4.5 hrs each and model B takes 2, 1 and 1.5 hrs each. The three divisions have a maximum
of 1600, 1200 and 1600 hours every month respectively. Model A gives a contribution of Rs. 400 each and
B gives Rs. 100 each. Assuming abundant product demand, find out the optimum product mix and the
maximum contribution through simplex method.
12.
A company produces three products P, Q and R form three raw materials A, B and C. One unit of
product P requires 2 units of A and 3 units B. A unit of product Q requires 2 units of B and 5 units of C and
one unit of product R requires 3 units of A, 2 units of B and 4 units of C. The company has 8 units of
material A, 10 units of material B and 15 units of material C available to it. Profits per unit of products P, Q
and R are Rs. 3, Rs. 5 and Rs. 4 respectively.
a) Formulate the problem mathematically.
b) How many units of each product should be produced to maximize profit?
13.
A pharmaceutical company has 100 kg of A, 180 kg of B and 120 kg of C available per month.
They can use these materials to make three products namely 5-10-5, 20-5-10, where the numbers in each
124
Operations Research (MTH601)
125
case represent the percentage by weight of A, B and C respectively in each of the product. The cost of
the raw materials are given below.
Ingredient
A
B
C
Inert Ingredient
Cost per Kg (Rs.)
80
20
50
20
Selling price of these products are Rs. 40.5, Rs. 43 and Rs. 45/kg respectively. There is a capacity
restriction that the product 5-10-5 cannot be produced more than 30 kg per month. Determine how much of
each product they should product they should to maximize their monthly profit.
125
Operations Research (MTH601)
126
14.
Consider the following linear programming problem:
Maximize
x0 = 3x1 + 2x2 + 5x3
Subject to
x1 + 2x2 + 2x3 8
3x1 + 2x2 + 6x3 12
2x1 + 3x2 + 4x3 12
x3 0
x1 ,
x2 ,
(i)
Solve this problem by simplex method.
(ii)
Does this problem have an alternative optimal solution?
(iii)
The validity of one of the steps in simplex method becomes questionable as you work out this
problem. What is this step?
15.
An aviation fuel manufacturer sells two types of fuel, A and B. Type A fuel is 25 per cent grade I
petrol, 25 per cent grade II petrol and 50 per cent grade III petrol. Type B fuel is 50 per cent grade III
petrol. Type B fuel is 50 per cent grade II petrol and 50 percent grade III petrol. Available for production
are 2000 liters/hour of grade I and 800 liters/hour of grade II and III. The cost of petrol is Rs. 3 per litre for
grade I, Rs. 6 per litre for grade II and Rs. 5 per litre for grade III. Type A can be sold for Rs. 7.5 per litre
and type B for Rs. 9.00 per litre. How much of each fuel should be made?
16.
A manufacturer uses three raw products a, b, c priced at 30, 50 and 120 rupees per kg respectively.
He can make three different products A, B and C, which can be sold at 90, 100 and 120 rupees per kg
respectively. The raw products can be obtained only in limited quantities, namely 20, 15 and 10 kg per day.
Given 2 kg of a plus 1 kg of b plus 1 kg c will yield 4 kg of A, 3 kg of a plus 2 kg of b plus 2 kg of c will
yield 7 kg of B, 2 kg of b plus 1 kg of c will yield 3 kg of C.
Make a production plan, assuming the order and cost are not influenced by the choice among the
alternatives. Solve the problem by simplex method.
126