Simplex method maximization case
The solution steps of the simplex method can be summarized as follows.
Step 1. Formulation of the Mathematical Model.
(a) Formulate a linear programming model of the real-word problem i.e., obtain a mathematical representation of the problem s objective function and constraints.
(b) Express the mathematical model of L.P. problem in the standard form by adding slack variables in the left hand side of the constraints and assign a zero coefficient to these in the objective function.
Sept 2. Set up the Initial Solution. The initial basic feasible solution is obtained by assigning zero value to all the decision variables just to initiate the solution procedure from the origin. This solution is summarized in the initial simplex table. Complete the initial table by adding two final rows Cj and Cj-Zj . These two rows provide the important economic information including the total profit and the answer as to whether the current solution is optimum or not.
Sept 3. Test the solution for optimality. Examine the index row of the above simplex table. If all the elements in the index row are negative then the current solution is optimum. If there exists some positive number the current solution can be further improved by removing one basic variable from the basis and replacing it by some non-basic one.
Sept 4. (a) Determine which variable to enter in to the solution mix next one way of doing this is by identifying the column (and hence the variable) with the largest positive number in the Cj -Zj row of the previous table. The value of Cj -Zj row of the previous table. The value of Cj-Zj tells the amount by which the value of the objective function will increase for every unit of Xj introduced into the solution. The column so identified is called the pivot or key or optimum column. Suppose Xj column is the key column with entries aij a2j .......amj....
b. Determine the departing variable or variable to be replaced. Next we proceed to determine which variable must be removed from the basis to pave way for the entering variable. This is accomplished by dividing each number in the quantity (XB) column by the corresponding number in the key column selected in (a) i.e., we compute the ratio b1/a2j......bm/amj (only for those aij 's' i=1, 2, ...., m which are strictly positive). The row corresponding to the minimum of these rations is the key row (or pivotal row) and the corresponding to the basic variable will leave the basis. Left the minimum of { b1/a2j......bm/amj ; aij > 0} be bk/akj; then sk will be termed as outgoing variable in the next table to be constructed just after we put an arrow of type - to the right of k th row of the simplex table 1.
Step 5. Identify the key Element. The number that lies at the intersection of the intersection of the key column and key row of the given table is called the key or pivot element. It is always a non-zero positive number.
Step 6. Evaluate (update) the New Solution.
(a) Compute new value for the key or pivot row. To do this, simply divide every number in the key row by the key element.
(b) Compute new value for each remaining rows All remaining row (s) for the second simplex table can be calculated by the formula:
New row numbers = (Number in old rows)
Number above or X corresponding number
Below key number in the row replaced in (a)
= (old row number) - (corresponding number in the key row x corresponding new value in the key row in the same column)
(C) New entries in the CB column and XB column are entered in the new table of the current solution.
(d) Test for optimality. Compute the Zj and Index (Cj - Zj) rows as previously demonstrated in the initial simplex table. If all numbers in the index row are zero or negative an optimum solution has been reached, i.e., there is no variables which can be introduced in the solution to case the objective function to increase.
Step 6. Revise the Solution. if any of the numbers in the index (Cj - Zj) row are positive, repeat the entire step 5 again until an optimum solution has been obtained.
Remarks 1. Simplification of calculation. It is possible to simplify the calculation process by following few rules:
1. Any variable in the variable column will have a I where the row of that variable intersects with the column of that variable, and all other figures in the column of that variable will be zero.
2. If there is a zero in the key column that the row in which that zero appears will remain unchanged in the subsequent table.
3. If there is a zero in the key row, than the column in which that zero appears will remain unchanged in the subsequent table.
By observing the above three rules, the number of items for which derived number are to be calculated will be greatly reduced. Where a simplex solution has to be worked by manual methods, the saving in time and effort is significant. When computers are used, it is desirable to allow the normal procedure to be followed.
1 Rules for Ties. In choosing the key column and key row, whenever there is a tie between two numbers the following rules may be adopted.
1. Select the column farther to the left, whenever there is a tie between two number in the index row.
2. Select the ratio (o) nearest to the top whenever there is a tie between two replacement rations in a matrix.
3. Schematic Diagram of the Simplex Method. The computational procedure for determining the optimal solution to a general L.P. can conveniently represented in the following diagram.
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.
ExpertsMind.com - Simplex Method Steps, Assignment Help, Simplex Method Homework Help, Formulation of Mathematical Model.