CASE 1. Maximization case (All Constraints of the type <)
Example1. An electronics firm is undecided as to the most profitable mix for its products. The products now manufactured are transistors, resistors and electron tubes with a profit (per 100 untis) of Rs. 100, Rs 60 and Rs, 40 respectively. To produce a shipment of transistors containing 100 units requires 1 hour of engineering services, 10 hours of direct labour and 2 hours of administrative service. To produce 100 resistors are required 1 hour 4 hours and 2 hours of engineering direct labour and administrative time respectively. To produce one shipment of the electron tubes (100 units) requires 1 hours of engineering, 5 hours of direct labour and 6 hours of administration. There are 100 hours of engineering services, 600 hours of direct and 300 hours of administration available with the firm. What is the most profitable mix?
Solution. step 1. Formulation of the Mathematical Model. Let x1 x2 be the number of units (in hundred) of transistors, resistors and electron tubes to be manufactured respectively. The data of the given problem can be summarized as below.
|
Department
|
Products (in’000 units)
Transistors Resistors Electron tubes
(x1) (x2) (x3)
|
Available
capacity
|
|
Engineering
|
1 1 1
|
100
|
|
Labour
|
10 4 5
|
600
|
|
Administration
|
2 2 6
|
300
|
|
Profit (per’000units) Rs
|
100 60 40
|
|
The problem is to determine the optimum number of three products in order to maximize total profit. The complete linear programming model can be stated as follows:
Maximize Z = 100 x1 + 60 x2 + 40 x3
Subject to the constraints:
X1 + x2 + x3 < 100
10 x1 + 4x2 + 5x3 < 600
2 x1 + 2 x2 + 6x3 < 300
X1 > 0, x2 > 0, x3 > 0
Step 2. Converting the Constraints to Equations. The next step is to convert every inequality constraint in the LP problem into an equality constraint so that the problem can be written in a standard form. This can be accomplished by adding a slack variable to each constraint. Each slack variable corresponds to the amount of unused capacity (or resources) for the constraint to which it is added. The symbol‘s’ is generally used represent the slack variables. Slack variables are always added to the less than type of constraints to make it equality. These slack variables must be non-negative otherwise; the capacity utilized will exceed the total available capacity. The constraints for the given problem can now be rewritten with slack variables to form the equalities as given below:
X1 + x2 + x3 + s1 = 100
10x1+ 4x2 + 5x3 + s2 = 600
2x1+ 2x2 + 6x3 + s3 = 300
X1 > 0, x2 > 0, x3 > 0, s1 > 0, s2 > 0, s3 > 0
Since slack variables represent unused resources, their contribution in the objective function is zero. Including these slack variables in the objective function,
We get max Z= 100 x1 + 60x2 + 40x3 + O. s1 + O.s2 + O.s3
Step 3. Setup the Initial Solution. The logic of the simplex method is based on the fact that only the corner points of the feasible solution region can give unique optimum solution. The search starts with a solution at the origin indicating nothing can be produced and therefore the values of decision variables are zero, i.e., x1 = 0 x2 = 0 and x3 = 0. When we are not producing anything obviously we are left with unused capacity of s1 = 100, s2 = 600 and s3 = 300 we note the current solution has three variables (slack variables s1, s2 and s3) with non-zero values. Variables with non-zero solution values are called basic variables. We can observe that there will always be the same number of basic variables as there and the number of constraints provide the constraints are not redundant and that a basic feasible solution exists. Solutions with basic variables are called basic solutions. The basic solution can further be divided into two categories. Feasible and infeasible. The basic feasible solutions are those that satisfy all the constraints. the simplex procedure searches for basic feasible solutions only at the corner point of the feasible solution region.
Step 4. Develop Initial Simplex Table. The initial decision can easily be summarized in a tabular form known as simplex Table on simplex Matrix, an explanation of its parts how it is derived is given as follows;
TABLE 1: PARTS OF INITIAL SIMPLEX TALBE
Profit basic values of real variables slack variables
Per unit variables basic variables column column
Column column column
Cj basic soluation 100 60 40 0 0 0 profit
Variables values x1 x2 x3 x4(=s1) x5(=s2) x6(=s3) variab
Cb B b(=Xb) bie row
0 S1 100 1 1 1 1 0 0 rows
0 S2 600 10 4 5 0 1 0 illustrai
0 S3 300 2 2 6 0 0 1 ing
Constri
Ant
Body matrix Identiy matrix
Costing of consisting of
Coefficients of coefficients of
Real product slack variables
Variables
Starting from left-hand side of the above table the column Cj indicates the contribution per unit for the slack variables s1 s2. Since profits are not made on unused time the contribution per unit for s1 s2 and s3 is shown as zero.
The number in the Zj row under each variable represents the total contribution of outgoing profit when one unit of non-basic variable is introduced into the basic in place of a basic variable. Zj values in various variables columns are calculated by multiplying the coefficients of basic variables in the CB column with coefficients (aij) in each variable column and then add up the products sQ obtained. For example Zj value in the x1 column be will be:
Zj= 0 (Cj of S1) X 1 (coefficient of x1in s1row, i.e.,a11)
+ 0 (Cj of s2) X 10 (coefficient of x1in S2 row, i.e., a21)
+ 0 (Cj of s3) X 2 (coefficient of x1 in S3 row, i.e., a31)
= 0 x1+0x10+0x2=0
Following the same procedure Zj for all other variable column will be computed as shown in the table 2 on next page 3.12
The number in Cj - Zj (index or Net Evaluation Row) row represent the net profit i.e., the profit gained minus the profit give up that will result from introducing 1 unit of each base variable into the solution and can be computed by simply subtracting the Zj total for each column from the Cj value in the very top of that variable column. For example, Cj- Zj value in the x1 column will be Ci - Zj = 100 – 0= 100 and so on. The values of Cj-Zj are always zero under the basic variables.
The value of the objective function in the current solution is obtained by multiplying the
Elements in the then adding these products, i.e., Z= 100 x 0 + 600 x 0 + 300 x 0 =0.
Remark. By examining the numbers in the Cj-Zj (index or NER) row of table. 2, we find that profit can be increased by Rs. 100 for each unit of x1 added to the solution mix or by Rs. 60 for each unit of x2 each added to the a solution mix and by Rs. 400 for each unit of X3 added to the solution mix. Thus a positive number the Cj Zj row indicates that profits can be improved if one unit of the variable heading that column were added to the solution. Thus the optimum solution is reached when no positive numbers are left in the Cj-Zj row.
Step 5. Test for Feasibility. After the initial simplex table is set up the next step is to determine whether any improvement is possible. The computational procedure is as follows.
(a) Choosing the entering variables. Since the net increase of profit per unit of each product is represented by number in Cj - Zj row the product to be introduced first will be largest positive value of Cj-Zj it may be noticed in table 2 that the largest positive value of Cj-Zj in index row is 100 under the column x1. The indicates that x1(transistors) be produced first in order to increase total profit at the fastest rate since each unit of x1 added into the solution mix will contribute Rs. 100 to the overall profit. The variable x1 which is to be brought into the basis in the second simplex table is known as entering variable and the column corresponding to entering variable is termed as key or pivot column.
(b) Choosing the departing variable. Since we have decided to enter one variable as the basic variable into the solution basis we must replace one of the existing basic variables to depart from the solution basis. the variable to depart is identified by forming the ratios of solution values to physical rates of substitution of entering variable i.e., we divide each number in the quantity columns i.e., 100,600 and 300 by the corresponding numbers in the key column i.e., 1,10and 2.
Thus for s1 row, ratio = 100/1 = 100
For s2 row, ratio = 600/10 = 60
For s3 row, ratio = 300/2 = 150
The one with the minimum positive ratio (s2) represents the variables to depart from the solution basis. Thus s2 is the departing variable. The row corresponding to be departing variable is called key row or the pivot row or replaced row. The element on the intersection of key row and key column is called the key element and is denoted by making a (*) in the simplex table.
Step 6. Developing Second Simplex Table. In order to obtain the next solution let us refer to table 3 and follow the following steps:
(a) Computer new values for the row. To revise the key row divide all values in key row (s2) by the value of the key element (i.e., 10) and replace departing variable (s2) by the entering variable (x1). Also replace the new values in Cj column accordingly. Put all other values so obtained at the appropriate places. In our example, this new row becomes:
60 1 2/5 1\2 0 1/10 0
(b) Compute new values (derived numbers) for each remaining row. For other non-key rows, new values can be obtained by using the formula:
New row value = old row value – (corresponding old value in the key row x corresponding new value in the revised key row.)
Thus the values of s1- row can be obtained as follows:
Old s1 row 100 1 1 1 1 1 0 0
-{ corresponding
Element {=1}
X {new value in
Key row } 60 1 2/5 1\2 0 1/10 0
= New s1 row 40 0 3/5 1\2 1 - 1/10 0
Next we revise the s3- row as follows.
Old s3 row 300 2 2 2 6 0 0 1
-{corresponding
Element (=2)}
X {New value
In key row} 120 2 4/5 1 0 1/5 0
= New s3 row 180 0 6/5 5 0 -1/5 1
The values of Cj and (cj-zj) rows are calculated in the same way as discussed earlier. The value of the objective function is calculated by substituting the value of the variables in the objective function. For example, in the improved solution. Z= 0 x 40 +100 x60 + 0 x 180 = 6000
Step 7. Proceeding in the same manner we notice that variable x2 will enter into the solution and variable s1will depart. The key element is 3/5.
Since all entries in the index row (Cj-Zj row) of the above table are negative this indicates no sign of further improvement in the contribution. Thus it follows that an optimum solution has been arrived at and the solution values are given by:
X1= 100/3, x2 = 200/3, x3 =0 and max Z= Rs. 22,000/3
The solution can be interpreted as follows: The maximum profit of Rs. 22,000/3 is obtained when company manufactures 100x100/3 units of transistors 200x100/3 units of resistors and no units of election tube. The solution also indicated that 100 man-hours of administration are still remained unutilized as shown by s3 = 100 in the column XB in table 5.
Remarks 1. Since it is always possible to make an arithmetical error when one is going through the numerous simplex steps and iterations.
Simplex Method-Linear Programming Tutoring - Assignment Help
Our online expert tutor's team at www.expertsmind.com is passionate & professional experienced people who are providing their precious time by online simplex method linear programming assignment help, techniques of operation research homework help services which give the best quality answers of subject questions on time given by students. Instant operation research tutors can help you in solving your toughest and complex operation research questions and they can make easy learning subject. We at Expertsmind.com offers instant tutoring sessions in operation research.