ZeePedia

Linear Programming:The Two Phase Method, First Iteration

<< Linear Programming:ARTIFICIAL VARIABLE TECHNIQUE
Linear Programming:VARIANTS OF THE SIMPLEX METHOD >>
img
Operations Research (MTH601)
136
Z* = 185/11
x1 = 40/11
x2 = 25/11
The Two Phase Method
A difficulty is being encountered in the use of M technique in that there is a possible computational error
that could result from giving a very large value of M. By this the objective coefficients of the variables x and y are
now too small compared with the large numbers created by the multiples of M. The solution may become insensitive
to the relative value of the original coefficients of the decision variables x and y due to the round off error which is
inherent in any digital computer. The result could be that both may have equal coefficients in the objective function.
To overcome this difficulty another method namely two phase method is presented below. This method involves two
phase which are:
Phase 1:Replace the original objective problem by the sum of the artificial variables to formulate a new problem.
Then this new objective function is then minimized subject to the constraints of the original problem. If the problem
has a feasible solution, the minimum value of the objective function will be zero which shows that all the artificial
variables are zero. Then proceed to phase II. Otherwise, if the minimum value is greater than zero, we conclude that
the problem has no feasible solution.
Phase II:
Use the optimum basic solution of phase I as a starting solution for the original problem. Now the
original objective function has to be expressed in terms of the non-basic variables only. This can be achieved by
adding suitable multiples of the constraint equations involving artificial variables.
Example
Consider the problem
Maximize
Z = 2x + 5y
Subject to
x  < 40
y  < 30
x + y > 60
x, y > 0
Solution:
We try to solve this problem by the two-phase method.
Introduce slack variables S1 and S2 for the first two constraints respectively. Subtract a slack variable S3 and
add an artificial variable A for the third constraint so that the third constraint is changed into x + y - S3 + A = 60. In
this problem we have the new objective function expressed as minimization of the sum of artificial variables. We
have only one artificial variable.
Phase I
Minimize
(0)
Z=A
Subject to
x + S1 = 40
(1)
y + S2 = 30
(2)
136
Operations Research (MTH601)
137
x + y - S3 + A = 60
(3)
Note that the objective function is always of the minimization irrespective of whether the original problem
is maximization or minimization of the objective function.
We prepare the initial table as follows:
137
img
Operations Research (MTH601)
138
RHS
Eqn.
Basic
Coefficient of
No.
variable
S2
S3
A
Z
x
y
S1
0
-
1
0
0
0
0
0
-1
0
1
0
1
0
1
0
0
0
40
S1
2
0
0
1
0
1
0
0
30
S2
3
0
1
1
0
0
-1
1
60
A
In the above table the objective function has the coefficient of the basic variable A. To eliminate the same,
we multiply the equation 3 involving the basic variable A by 1 and add to objective row. Hence the revised table his
shown below.
RHS
Ratio
Eqn.
Basic
Coefficient of
No.
variable
S2
S3
A
Z
x
y
S1
0
-
1
1
1
0
0
-1
0
60
1
0
1
0
1
0
0
0
40
40
S1
2
0
0
1
0
1
0
0
30
S2
3
0
1
1
0
0
-1
1
60
60
A
Solution:
Z = 60, S1 = 40, S2 = 30, A = 60, x = y = S3 = 0
First Iteration:
x or y can enter the basis as they have the same positive coefficients. Choose any one, say x, and hence S1
leaves the basis.
RHS
Ratio
Eqn.
Basic
Coefficient of
No.
variable
S2
S3
A
Z
x
y
S1
0
-
1
0
1
-1
0
-1
0
20
1
0
1
0
1
0
0
0
40
x
2
0
0
1
0
1
0
0
30
30
S2
3
0
1
1
-1
0
-1
1
20
20
A
Second Iteration:
y enters and A leaves the basis.
RHS
Eqn.  Basic
Coefficient of
No.
variable
S2
S3
A
Z
x
y
S1
0
-
1
0
0
0
0
0
-1
0
1
0
1
0
1
0
0
0
40
x
2
0
0
0
1
1
1
-1
10
S2
138
img
Operations Research (MTH601)
139
3
0
1
1
-1
0
-1
1
20
y
From the above table we see that the objective function Z = 0 and A has left the basis. Hence A becomes a
non-basic variable. This is the indication that the problem has a feasible solution and we can proceed to phase II,
which is explained below.
In the phase II, a table is prepared with the objective function and the set of constraints tabulated
Phase II:
in the final table of Phase I omitting the column of the artificial variable, as it is non-basic.
In preparing the table the objective function has to be expressed in terms of the non-basic variables only. In other
words, the coefficients of the basic variables must be zero.
Eqn.
Basic
Coefficient of
RHS
No.
variable
S2
S3
Z
x
y
S1
0
-
1
-2
-5
0
0
0
0
1
0
1
0
1
0
0
40
x
2
0
0
0
1
1
1
10
S2
3
0
0
1
-1
0
-1
20
y
In the above table, x and y are basic variables and their coefficients are -2 and -5 respectively. Hence the
objective function must be rearranged to make the coefficients of x and y as 0. This is obtained by multiplying the
equation (1) by 2 and the equation (3) by 5 and adding this to the objective row. We have the following starting table
with the revised objective function.
RHS
Ratio
Eqn.
Basic
Coefficient of
No.
variable
S2
S3
Z
x
y
S1
0
-
1
0
0
-3
0
-5
180
1
0
1
0
1
0
0
40
x
2
0
0
0
1
1
1
10
10
S2
3
0
1
1
-1
0
-1
20
-20
y
The original problem is one of maximization and hence in the first iteration S3 enters and S2 leaves the basis.
First Iteration:
RHS
Eqn.
Basic
Coefficient of
No.
variable
S2
S3
Z
x
y
S1
0
-
1
0
0
2
5
0
230*
1
0
1
0
1
0
0
40
x
2
0
0
0
1
1
1
10
S3
3
0
0
1
0
1
0
30
y
We get the optimum value of Z in the above table as no negative coefficient is present in the objective
function row.
139
Operations Research (MTH601)
140
Solution:
Z = 230, x = 40, y = 30, S3 = 10, S1 = S2 = 0.
REVIEW QUESTIONS
1.
An animal feed manufacturer has to produce 200 kg of a feed mixture consisting of two
ingredients x1 and x2. x1 costs Rs. 6 per kg and x2 costs Rs. 16 per kg Not more than 80 kg of x1 can be used
and atleast 60 kg of x2 must be used. Using simplex method, find how much of each ingredient should be
used in the mix if the company wants to minimize cost. Also determine the cost of the optimum mix.
2.
A marketing manager wishes to allocate his annual advertising budget of Rs. 20000. in two media
vehicles A and B, The unit of a message in media A is Rs. 1000 and that of B is Rs. 1500. Media A is a
monthly magazine and not more than one insertion is desired in one issue. At least 5 messages should
appear in media B. The expected effective audience for unit messages in the media A is 40000 and for
media B is 55000.
(i) Develop a mathematical model.
(ii) Solve it for maximizing the total effective audience.
3.
A pension fund manager is considering investing in two shares A and B. It is estimated that,
(i) Share A will earn a divided of 12% per annum and share B 4% per annum.
(ii) Growth in the market value in one year of share A will be 10 paise per Re. 1 invested and in B 40 paise
per Re. 1 invested.
He requires investing minimum total sum which will give
* dividend income of at least Rs. 600 per annum and
*growth in one year of atleast Rs. 1000 on the initial investment.
Your are required to
(i) State the mathematical formulation of the problem.
(ii) Compute the minimum sum to be invested to meet the manager's objective by using simplex method.
4.
A company possesses two manufacturing plants each of which can produce three products x, y, z
from a common raw material. However the proportions in which the products are produced are different in
each plant and so are the plant's operating costs per hour. Data on production per hour and costs are given
below together with current orders in hand for each product.
Product
Operating
x
y
z
cost/hr (Rs.)
Plant A
2
4
3
9
140
img
Operations Research (MTH601)
141
Plant B
4
3
2
10
Orders
50
24
60
on hand
You are required to use the simplex method to find the number of production hours needed to fulfill the
order on hand at minimum cost.
5.
Maximize
x0 = 2x1 + x2 + x3
Subject to
2x1 + 3x2 - x3 < 9
2x2 + x3 > 4
x1  +  x3 = 6
x1,  x2, x3 > 0
6.
Minimize
Z = 3x1 + 2.5 x2
Subject to
2x1 + 4x2 > 40
3x1 + 2x2 > 50
x1 , x2 > 0
7.
The following table gives the protein, fats and carbohydrates available in 50 grams of food items
F1, F2, F3 and F4.
Food items
Protein
Fats (gms)
Carbohydrate
(gms)
(gms)
2.4
0.3
15.8
F1
2.3
9.4
0.9
F2
8.4
2.1
0.0
F3
1.6
3.7
18.0
F4
The price of 50 grams of each of the four items is as follows:
F1
F2
F3
F4
Item
5
12
20
20
Price in paise
The hospital has recommended that it is necessary to consume atleast 75 grams of protein 90 grams of fat
and 300 grams of carbohydrate.
Solve the problem to find the minimum food bill.
8.
Solve using the two-phase technique.
141
Table of Contents:
  1. Introduction:OR APPROACH TO PROBLEM SOLVING, Observation
  2. Introduction:Model Solution, Implementation of Results
  3. Introduction:USES OF OPERATIONS RESEARCH, Marketing, Personnel
  4. PERT / CPM:CONCEPT OF NETWORK, RULES FOR CONSTRUCTION OF NETWORK
  5. PERT / CPM:DUMMY ACTIVITIES, TO FIND THE CRITICAL PATH
  6. PERT / CPM:ALGORITHM FOR CRITICAL PATH, Free Slack
  7. PERT / CPM:Expected length of a critical path, Expected time and Critical path
  8. PERT / CPM:Expected time and Critical path
  9. PERT / CPM:RESOURCE SCHEDULING IN NETWORK
  10. PERT / CPM:Exercises
  11. Inventory Control:INVENTORY COSTS, INVENTORY MODELS (E.O.Q. MODELS)
  12. Inventory Control:Purchasing model with shortages
  13. Inventory Control:Manufacturing model with no shortages
  14. Inventory Control:Manufacturing model with shortages
  15. Inventory Control:ORDER QUANTITY WITH PRICE-BREAK
  16. Inventory Control:SOME DEFINITIONS, Computation of Safety Stock
  17. Linear Programming:Formulation of the Linear Programming Problem
  18. Linear Programming:Formulation of the Linear Programming Problem, Decision Variables
  19. Linear Programming:Model Constraints, Ingredients Mixing
  20. Linear Programming:VITAMIN CONTRIBUTION, Decision Variables
  21. Linear Programming:LINEAR PROGRAMMING PROBLEM
  22. Linear Programming:LIMITATIONS OF LINEAR PROGRAMMING
  23. Linear Programming:SOLUTION TO LINEAR PROGRAMMING PROBLEMS
  24. Linear Programming:SIMPLEX METHOD, Simplex Procedure
  25. Linear Programming:PRESENTATION IN TABULAR FORM - (SIMPLEX TABLE)
  26. Linear Programming:ARTIFICIAL VARIABLE TECHNIQUE
  27. Linear Programming:The Two Phase Method, First Iteration
  28. Linear Programming:VARIANTS OF THE SIMPLEX METHOD
  29. Linear Programming:Tie for the Leaving Basic Variable (Degeneracy)
  30. Linear Programming:Multiple or Alternative optimal Solutions
  31. Transportation Problems:TRANSPORTATION MODEL, Distribution centers
  32. Transportation Problems:FINDING AN INITIAL BASIC FEASIBLE SOLUTION
  33. Transportation Problems:MOVING TOWARDS OPTIMALITY
  34. Transportation Problems:DEGENERACY, Destination
  35. Transportation Problems:REVIEW QUESTIONS
  36. Assignment Problems:MATHEMATICAL FORMULATION OF THE PROBLEM
  37. Assignment Problems:SOLUTION OF AN ASSIGNMENT PROBLEM
  38. Queuing Theory:DEFINITION OF TERMS IN QUEUEING MODEL
  39. Queuing Theory:SINGLE-CHANNEL INFINITE-POPULATION MODEL
  40. Replacement Models:REPLACEMENT OF ITEMS WITH GRADUAL DETERIORATION
  41. Replacement Models:ITEMS DETERIORATING WITH TIME VALUE OF MONEY
  42. Dynamic Programming:FEATURES CHARECTERIZING DYNAMIC PROGRAMMING PROBLEMS
  43. Dynamic Programming:Analysis of the Result, One Stage Problem
  44. Miscellaneous:SEQUENCING, PROCESSING n JOBS THROUGH TWO MACHINES
  45. Miscellaneous:METHODS OF INTEGER PROGRAMMING SOLUTION