Basic terms involved in simplex procedure
We shall introduce certain terms which all are relevant for solving a linear programming problem through simplex procedure.
1. Standard Form. A linear programming in which all of the constraints are written as equalities. The optimum solution of the standard form of a linear programming is the same as the optimum solution of the original formulation of the linear programmer.
2. Slack Variable. A variable added to the left-hand side of is less-than or equal to constraint to convert the constraint into equality. The value of this variable can usually be interpreted as the amount of unused resource.
3. Surplus Variable. A variable subtracted from the left-hand side of a greater-than or equal-to constraint to convert the constraint into equality. The value of this variable can usually be interpreted as the amount over and above the required minimum level.
4. Basic Solution. For a general linear program with n variable and m constraints a basic solution may be found by setting (n-m) of the variables equal to zero and solving the constraint equations for the values of the values of the other m variables. If a unique solution exists it is a basic solution.
5. Basic Feasible Solution. A basic solution which is also in the feasible region (i.e., it satisfies the non-negativity requirement). A basic feasible solution corresponds to a corner point of the feasible region.
6. Tableau Form. The form in which a linear program must be written prior to setting up the initial simplex table. When a linear program is written in this form, its matrix contains m unit columns corresponding to basic variables, and the values of these basic variables given by the quantity column. A further requirement is that entries in the quantity column be greater than or equal to zero. The requirement provides us with a basic feasible solution.
7. Simplex Table. A table used to keep track of the calculations made at each iteration when the simplex solution method is employed.
8. Product Mix. A column in the simplex table that contains all of the variables in the solution.
9. Basis. The set of variables which are not restricted to equal zero in the current basic solution and are listed in the product mix column. The variables make up the basis are termed basic variables, and the remaining variables are called non-basic variables.
10. Iteration. an iteration of the simplex method consists of the sequence of steps performed in moving from one basic feasible solution to another.
11. Zj Row. The row containing the figures for gross profit or loss given up by adding one unit of a variable into the solution.
12. Cj Zj or Net Evaluation or Index Row. The row containing the net profit or loss that will result from introducing one unit of the variable indicated in that column in the solution. Numbers in index row are also known as the shadow prices or accounting prices. Thus a positive (or negative) number in the index row indicates an algebraic reduction (or increment) in the objective function if one unit of the variables at the head of that column were introduced in the basis (solution).
13. Pivot or Key Column. The column with the largest positive number in the Cj -Zj row of a maximization problem or the largest negative Cj Zj value in a minimization problem. It indicates which variable will enter the solution next.
14. Pivot or Key Row. The row corresponding to the variable that will leave the basis in order to make room for the entering variables (as indicated by the new key column). The departing variable will correspond to the smallest positive ratio found by dividing the quantity column values by the key column values for each row.
15. Pivot or Key Element. The element at the intersection of the key row and key column.
16. Current solution. While carrying out the Simplex Method the current solution refers to the current basic feasible solution (extreme point)
Remark. Adding New Variables. Variables are entered for only two reasons.
(i) To convert an equality to an inequality, or
(ii) To provide an initial feasible solution.
These types of variables may be added to accomplish these objectives:
(a) Slack Variables (S1),
(b) Surplus Variables (-S2) or
(c) Artificial Variables (A1).
To prevent any possible confusion, the addition of new variables to constraint equations is summarized as follows:
Type of Variable and Reason for Use
Type of Constraint Convert inequality Initial Feasible Value in
Into equality Solution Variable Objective function
Less-than or- Slack Variable Slack Variable Slack Variable: 0
Equal to (<) S1 : < to = (S1)
Greater-than-or Surplus Variables Artificial Variable Surplus Variable:
Equal-to (>) -S2 : > to = able (A1) 0
Equal to (=) None Required Artificial Variable Artificial Variable:
(A2) max. - M
Min. + M
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 - Basic terms involved in simplex procedure Assignment Help, Basic terms involved in simplex procedure Homework Help, Basic terms involved in simplex procedure Assignment Tutors, Basic terms involved in simplex procedure Solutions, Basic terms involved in simplex procedure Answers, Simplex Method Assignment Tutors