Definitions:
Operations ResearchDefinitions:
- A feasible solution is the value of all points for which all constraints are satisfied.
- An optimal solution is a feasible solution, which maximizes or minimizes the objective function.
These terms can be interpreted in terms of the graphical representation. The feasible solution includes all the points within the permissible region (or solution space) including the boundary points.
REVIEW QUESTIONS
Solve Graphically
1. Maximize Z = 3x + 7y
Subject to x + 4y < 20 2x + y < 30 x + y < 8Â and x, y > 0
2. Maximize Z = 2x + 3y
Subject to -x + 2y < 16 x + y < 24 x + 3y > 45 -4x + 10y > 20 and x, y> 0
3. Maximize Z = 3x1 + 5x2
Subject to -3x1 + 4x2 < 12 2x1 -x2 > -2 2x1 + 3x2 > 12Â x1 < 4 x2 > 2 x1 > 0
4. Maximize Z = 4x1 + 6x2
Subject to x1 < 2 x2 < 4 x1 + x2 > 3 and x1, x2 >0
5. What are the four major types of allocation problems, which could be solved using linear programming technique? Briefly explain each one of them with an example.
b) Minimize Z = 4x1 + x2
Subject to 3x1 + 4x2 > 20 -x1 – 5x2 < -15 and x1, x2 > 0
- The standard weight of a brick is 5 kg, and it contains two basic ingredients B1 and B2.B1 costs Rs. 5/kg and B2 costs Rs. 8/kg Strength considerations dictate that the brick contains not more than 4 kg of B1 and a minimum of 2 kg of B2. Since the demand for the product is likely to be related to the price of the brick, find out graphically the minimum cost of the brick satisfying the above conditions.
- Solve by graphical method the following problem.
Minimize Z = 5x1 + 4x2 Subject to 4x1 + x2 > 40
2x1 + 3x2 > 90
x1 > 0, x2 > 0
b) Food A contains 20 units of vitamin x and 40 units of vitamin y per gram. Food B contains 30 units of each of vitamins x and y. The daily minimum human requirements of vitamin x and y are 900 units and 1200 units respectively. How many grams of each type of food should be consumed so as to minimize the cost, if food A costs 60 paise per gram and food B 80 paise per gram.
8. A company produces two types of products say type A and type B. Product A is of superior quality and product B is of a lower quality. Respective profits for the two types of products are Rs. 40/- and 30/-. The data on the resource required, availability of resources are given below:
Requirements Product A Product B
Raw materials 120 60 (kg) Machining time 5
8 (hrs/piece) Assembly 4
3 (man-hour)
SIMPLEX METHOD
Basic Properties
The simplex method is based on the following fundamental properties:
Property 1:
The collection of feasible solutions constitutes a convex set.
Property 2.
If a feasible solution exists, a basic feasible solution exists where the basic feasible solution corresponds to the extreme points (corner points) of the set of feasible solutions.
Property 3.
There exist only a finite number of basic feasible solutions.
Property 4.
If the objective function possesses a finite maximum or minimum, then at least one optimal solution is a basic feasible solution.
These properties can be easily verified for their plausibility with reference to the graphical representation. The reason for these properties can be attributed to the complete linearity of the linear programming model. We shall clarify the hypothesis of properties 2 and 4. The linear programming problem need not necessarily have any feasible solution. This will be so when the constraints have inconsistencies or contradictions.
In the above example the third constraint x + y < 60 is replaced by, say, x + y > 100. Then we cannot have a single solution space to offer solution space to have an infinitely high value subject to the restrictions rather than some finite number. This will be the case when in the example 2.5.1 the second and the third constraint have been deleted. Then the solution space and the solution are unbounded. As per this model the objective function will have Z = + âˆž as the feasible solution. Suppose there exists a feasible solution and that the optimal value of Z is finite, properties 2 and 3 indicate that the number of basic feasible solutions is strictly positive and finite. From the property 4 we infer that only this finite number of solutions namely the basic feasible solutions or the extreme points are to be investigated to find an optimal solution. Hence even though there exists an infinite number of feasible solutions, it is enough to find the value of the objective function for the basic feasible solutions. Hence we limit to only a few of the feasible solutions. Therefore we examine the value of the objective function at each of the corner points or basic feasible solutions and select the one with the largest value of Z in a maximization problem and the smallest value of Z in a minimization problem.
One more interesting fact can be inferred from the property 4 that an optimal solution need not be a basic feasible solution. This can take place if a number of feasible solutions yield the same maximum feasible value of Z, since the property 4 guarantees only that at least one of these will be a basic feasible solution. To illustrate, suppose that the objective function in the above example is changed to Z = 4x + 4y. Then not only the two basic feasible solutions (30, 30) , (40, 20) but also all the non-basic feasible solutions that lie on the line segment between the two points, numbering to infinity, would have been optimal solutions.
Simplex Procedure
The simplex method is an algebraic procedure involving a well-defined iterative process, which leads progressively to an optimal solution in a few numbers of finite steps. Dantzig introduced the method in 1947 and even today this seems to be the most versatile and powerful tool to solve linear programming problems. For routine linear programming problems, computer solution packages have been developed to use in an electronic digital computer. In the next section we describe what a simplex method does and how it solves a linear programming problem.
Example
Consider Z = 3x + 5y
Subject to x < 40, y < 30, x + y < 60, x, y > 0.
First step in the simplex method is to convert the linear programming model involving inequalities into strict equalities, by the use of “slack variables”. To illustrate the above idea, suppose we have the inequality x < 40. How can one replace this in equation by an equivalent equation? This inequality x < 40 implies the meaning that x can take a value of 40 or less. If the value of x is exactly 40, then this is the required equation. But since it also tells that x can take a value less than 40, it is necessary to add some positive value to x to make it up to 40. This additional non-negative variable is called the slack variable denoted by S1. We can then write x + S1 = 40Â so that the above is an equation. This has been achieved by the addition of a slack variable S1 to the left hand side of the in equation, which can take a value between 0 and 40 both inclusive. If S1 = 0, then x = 40 and if S1 = 40, then x = 0. Thus the slack variable is strictly non-negative.
So we conclude that the addition of a non-negative variable called slack variable converts the ‘less than equal to’ constraint into strict ‘equality constraint’.
The second inequality, y < 30 can also be converted into an equation by adding another slack variable S2 to the left hand side. Thus we haveÂ y + S2 = 30
Similarly the third constraint x + y < 60 is also converted with the addition of another slack variable S3 so that we have, x + y + S3 = 60
Thus an equivalent model alters the original linear programming model, Maximize Z = 3x + 5y
Subject to the restrictions, x + S1 = 40 (1) y + S2 = 30 (2) x + y +S3 = 60 (3) and x, y > 0
The above form of representation of a linear programming problem is much more convenient for algebraic manipulation and for identification of basic feasible solutions.
Referring to the restrictions in the above example, there are five variables x, y, S1, S2, and S3 all of them being non-negative and their values are to be determined to find an optimal solution. We have only three equations (1), (2) and (3) involving five variables. We cannot find a solution with the set of three equations in five unknowns. We must have al least five linearly independent equations to solve for all the five variables so that they will have unique values. Almost we can solve three variables in terms of the remaining two variables.
In general, if there are m equations in n variables (n > m), a basic solution is obtained by solving m variables in terms of the remaining variables and letting (n – m) variables equal to zero. This assumes that such a solution exists and is unique. A basic feasible solution is a basic solution where all m of these variables are nonnegative. A non-degenerate basic solution is a basic solution where these m variables are strictly > 0, (i.e.) positive. The m variables chosen from among n variables are called as “basic” variables or as the variables in the “basis”. The remaining (n – m) variables are termed as “non-basic” variables and their values are zero.
Now, considering the example above, we can choose any three variables and refer to as the basic variables and the remaining two as non-basic variables. A question may be asked at this juncture as to which three variables to choose from the five variables. This leads to a combinatorial problem of selecting any three variables from among five variables and we have 5 C3 (i.e.) 10 combinations. Ten such combinations can be listed and try with the objective function with the combination selected and we can choose the optimal solution. All of them will be basic solutions. But one or more of them may lead to the optimum objective function. But this is an exhaustive enumeration process, which is time consuming.
In the simplex method, it is customary that we select the slack variables viz. S1, S2 and S3 (in the example
cited) to form the initial basic variables, letting x and y as non-basic variables. We can rewrite the above equation as S1 = 40 – x S2 = 30 – y S3 = 60 – x – y
and the non-basic variables x and y are set equal to zero. Therefore, the initial basic feasible solution is x = 0 y = 0
S1 = 40 S2 = 30 S3 = 60 and automatically the value of Z = 3x + 5y becomes 0.
Thus we have an initial solution for the linear programming problem with Z = 0. Since the objective function is 0 the question now are any other solution that will be better than the current one. Thus we are forced to find the next basic feasible solution, which will give more profit. This requires selection of a new basic variable to
How are the leaving variable and entering variable selected?
The entering variable is chosen by examining the objective function to estimate the effect of each alternative. In our example the objective function is to maximize Z = 3x + 5y and if the value of any one of the variables x and y is changed from the present value of 0, to a positive, there is an increase in the objective function (as the coefficients of x and y are positive on the right hand side). Therefore either x or y, or, x and y would increase Z by entering into the basis. Now the question is which to select x or y, or both x and y. There are many alternatives. But clearly we see that the objective function will reach a greater value if we choose that variable that has more positive coefficient. In the example we have the coefficient of x as 3 and the coefficient of y as 5. Since x increases Z at the rate of 3 per unit increase in x and y increases Z at the rate of 5 per unit increase in y, y should be the entering variable, even though both are potential entering variables and the objective function is written as
Z – 3x – 5y = 0 in which case we have to choose the variable whose coefficient is more negative on the left hand side of equation.
Having decided to choose y to enter the basis, we have to select the variable leaving the basis. As we have only three equations but five unknowns, only three variables can be solved in terms of the other two.
To decide the candidate to be removed from the basis, we choose the variable whose value reaches zero first as the value of the entering variable is increased.
The equations involving the slack variables may be rewritten as
S1 = 40 â€“ x (1) S2 = 30 â€“ y (2) S3 = 60 – x â€“ y (3)
Referring to the above equations, as the value of y is increased, S1 will never become zero as the first equation does not involve y. This means that S1 will not leave the basis. The second equation indicates that S2 will be zero for the value of y = 30 and from the third equation we infer that S3 will be zero for the value of y = 60. So among the three candidates S1, S2 and S3, S2 will reach zero first as the value of y is increased to 30 from zero. Therefore S2 is chosen as the leaving variable.
Now, we have to find the values of the remaining basic variables. This is done by the use of the Gauss Jordan method of elimination in which the objective function is expressed only in terms of the non-basic variables.
The variable y enters the basis and S2 leaves the basis. So the variables in the new basis are y, S1 and S3. The new basic variable y has replaced S2 as th basic variable in equation (2). Gauss elimination process requires that y must now be eliminated from the other equations in which it appears. This is achieved by adding a suitable multiple of equation (2) to the other equations. Thus, the new equation (0) is the old equation (0) plus five times the equation (2)and the new equation (3) will be obtained by multiplying the equation (2) with -1 and adding to the old equation (3) which is entirely equivalent to the first set algebraically. So the second set of equations after manipulating the first set or original set of equations is presented below with the basic variables indicated bold.
Now we question whether the above second basic feasible solution is optimal or a still better solution is available. Can we still move up in the ladder of maximization? An answer is given be examining the objective function in the new set of equations. We are no longer using our original objective function. Examination of the objective function row reveals that x and S2 are the two non-basic variables and between them, if we choose x (since it has a negative coefficient) as a candidate for entering the basis, the objective function value further increases. S2 is not a candidate to enter the basis as it has a positive coefficient. Hence we have to include x in the new basis, thus x is the next candidate to enter the basis; As x is selected to enter the basis, one of the variables in the basis viz, S1, y, S3 has to leave the basis. We apply the criterion for selecting the leaving variable. As we assign the value for x in the equations (1) to (3), we observe that S1 will be zero for x = 40 and that S3 will be zero for x = 30. Since S3 will reach zero earlier as we assign values of x, S3 will be the next leaving variable from the basis. So we need to apply the elimination procedure once again to get a new solution. This means another iteration is required.
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.
Equation No. | Basic Variable | Z | x | Coefficient of y S1 | S2 | S3 | RHS | Ratio | |
0 | - | 1 | -3 | -5 | 0 | 0 | 0 | 0 | - |
1 | S1 | 0 | 1 | 0 | 1 | 0 | 0 | 40 | âˆž |
2 | S2 | 0 | 0 | 1 | 0 | 1 | 0 | 30 | 30 |
3 | S3 | 0 | 1 | 1 | 0 | 0 | 1 | 60 | 60 |
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
Virtual University of Pakistan Operations Research (MTH601) 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
Iteration I:
y enters the basis and S2 leaves the basis
Eqn. No. | Basic Variable | Z | x | Coefficient of y S1 S2 | S3 | RHS | Ratio | Solution | |||
0 | - | 1 | -3 | 0 | 0 | 5 | 0 | 150 | - | Z=150 | |
1 | S1 | 0 | 1 | 0 | 1 | 0 | 0 | 40 | 40 | S1=40 | |
2 | y | 0 | 0 | 1 | 0 | 1 | 0 | 30 | âˆž | y=30 | |
3 | S3 | 0 | 1 | 0 | 0 | -1 | 1 | 30 | 30 | S3=30 |
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
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.
Virtual University of Pakistan Operations Research (MTH601)
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) |
P1 | 4 | 5 | Rs. 10 |
P2 | 5 | 2 | Rs. 5 |
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.
Recent Comments