Module 2. Linear programming problem

Lesson 4

SIMPLEX METHOD

4.1 Introduction

In the previous chapter we considered the formulation of linear programming problems and the graphic method of solving them. Although the graphical approach to the solution of such problems is an invaluable aid to understand its basic structure, the method is of limited application in industrial problems as the number of variables occurring there is often considerably large. The Simplex Method provides an efficient technique which can be applied for solving linear programming problems of any magnitude-involving two or more decision variables. The Simplex Method is the name given to the solution algorithm for solving LP problems developed by George B. Dantzig in 1947. It is iterative procedure having fixed computational rules that leads to a solution to the problem in a finite number of steps. By using this one is capable of solving large LP problems efficiently.

4.2 Principle of Simplex Method

As the fundamental theorem of LP problem tells us that at least one basic feasible solution of any LP problem must be optimal, provided the optimal solution of the LP problem exists. Also, the number of basic feasible solutions of the LP problem is finite and at the most ⁿC_m (where, n is number of decision variables and m is the number of constraints in the problem). On the other hand, the feasible solution may be infinite in number. So it is rather impossible to search for optimal solutions from amongst all feasible solutions. Furthermore, a great labour will also be required in finding out all the basic feasible solutions and select that one which optimizes the objective function. In order to remove this difficulty; a simple method was developed by Dantzig (1947) which is known as Simplex Algorithm. Simplex Algorithm is a systematic and efficient procedure for finding corner point solutions and taking them for optimality. The evaluation of corner points always starts from the point of origin. This solution is then tested for optimality i.e. it tests whether an improvement in the objective function is possible by moving to adjacent corner point of the feasible function space. This iterative search for a better corner point is repeated until an optimal solution if it exists, is determined.  

4.3  Basic Terms Involved in Simplex Procedure

The following terms relevant for solving a linear programming problem through simplex procedure are given below:

4.3.1  Standard form of linear programming problem

The standard form of LP problem is to develop the procedure for solving general LP problem. The optimal solution of the standard form of a LP problem is the same as original LP problem. The characteristics of standard form are given in following steps:

Step 1. All the constraints should be converted to equations except for the non-negativity restrictions which remain as inequalities (≥0).

Step 2. The right side element of each constraint should be made non-negative.

Step 3. All variables must have non-negative values.

Step 4. The objective function should be of maximization form.

4.3.2 Slack variables

If a constraint has less than or equal sign, then in order to make it on equality we have to add something positive to the left hand side. The non-negative variable which is added to the left hand side of the constraint to convert it into equation is called the slack variable. For example, consider the constraints.

3X₁ + 5X₂ ≤ 2, 7X₁ + 4X₂ ≤ 5, X₁, X₂ ≥ 0                

We add the slack variables S₁ ≥ 0, S₂ ≥ 0 on the left hand sides of above inequalities respectively to obtain

3X₁+5X₂+S₁ = 2

7X₁+4X₂+S₂ = 5

X₁, X₂, S₁, S₂ ≥ 0

4.3.3 Surplus variables

If a constraint has greater than or equal to sign, then in order to make it an equality we have to subtract something non-negative from its left hand side. The positive variable which is subtracted from the left hand side of the constraint to convert it into equation is called the surplus variable.

For example, consider the constraints.

3X₁ + 5X₂ ≥ 2, 2X₁ + 4X₂ ≥ 5, X₁, X₂ ≥0      

We subtract the surplus variables S₃ ≥0, S₄ ≥ 0 on the left hand sides of above inequalities respectively to obtain

3X1+5X2 -S3 = 2

2X1 + 4X2 -S4 = 5

X1, X2, X3, X4 ≥0

4.3.4 Solution to LPP

Any set X = {X₁, X₂, X₃,…, X_n+m} of variables is called a solution to LP problem, if it satisfies the set of constraints only.

4.3.5 Feasible solution (FS)

Any set X = {X₁, X₂, X₃,……,X_n+m} of variables is called a feasible solution of L.P. problem, if it satisfies the set of constraints as  well as non-negativity restrictions.

4.3.6 Basic solution (BS)

For a system of m simultaneous linear equations in n variables (n>m), a solution obtained by setting (n-m) variables equal to zero and solving for the remaining variables is called a basic solution. Such m variables (of course, some of them may be zero) are called basic variables and remaining (n-m) zero-valued variables are called non-basic variables.

4.3.7 Basic feasible solution (BFS)

A basic feasible solution is a basic solution which also satisfies the non-negativity restrictions, that is all basic variables are non-negative. Basic solutions are of two types

(a) Non-degenerate BFS: A non-degenerate basic feasible solution is the basic feasible solution which has exactly m positive X_j (j=1, 2,…,m). In other words, all basic m variables are positive, and the remaining (n –m) variables will be all zero.

(b) Degenerate BFS: A basic feasible solution is called degenerate, if one or more basic variables are zero-valued.

4.3.8 Optimum basic feasible solution

A basic feasible solution is said to be optimum, if it also optimizes (maximizes or minimizes) the objective function.

4.3.9 Unbound solution

If the value of the objective function Z can be increased or decreased indefinitely, such solutions are called unbounded solutions.

4.4 Computational Aspect of Simplex Method for Maximization Problem

Step 1: Formulate the linear programming model. If we have n-decision variables X₁, X₂, X_n and m constraints in the problem , then mathematical formulation of L P problem is

Maximize Z=C₁X₁+ C₂X₂+…+C_nX_n

Subject to the constraints:

a₁₁ X₁+ a₁₂ X₂+ … +a_1n X_n ≤ b₁

a₂₁ X₁+ a₂₂ X₂ + … + a_2n X_n ≤ b₂

_…

a_m1 X₁+ a_m2 X₂ + … + a_mn X_n ≤ b_m

X₁, X₂, … X_n ≥ 0

Step 2: Express the mathematical model of LP problem in the standard form by adding slack variables in the left–hand side of the constraints and assign zero coefficient to these variables in the objective function.Thus we can restate the problem in terms of equations as follows:

Maximize Z=C₁X₁+ C₂X₂ +…+ C_nX_n +0X_n+1  +0X_n+2+…+0X_n+m                          

Subject to the constraints:

a₁₁ X₁+ a₁₂ X₂+ …+ a_1n X_n +X_n+1  = b₁

a₂₁ X₁+ a₂₂ X₂+…+ a_2n X_n +X_n+2  = b₂

.

a_m1 X₁+ a_m2X₂+…+a_mn X_n +X_n+m = b_m

X₁, X₂, … ,X_n, X_n+1,X_n+2 ,…, X_n+m ≥0

Step 3: Design the initial feasible solution .An initial basic feasible solution is obtained by setting  X₁=X₂=… =X_n =0. Thus, we get X_n+1=b₁, X_n+2 =b₂ ,…, X_n+m =b_m.

Step 4: Construct the starting (initial) simplex tableau. For computational efficiency and simplicity, the initial basic feasible solution, the constraints of the standard LP problem as well as the objective function can be displayed in a tabular form, called the Simplex Tableau as shown below.

Table 4.1  Initial simplex tableau

Cj (contribution per unit) →				c1	c2	…	cn	0	0	…	0	Minimum Ratio*
Cb	Basic Variables		Value of Basic Variables	Coefficient Matrix				Identify Matrix
	B		b(=XB)	X1	X2	…	Xn	Xn+1	Xn+2	…	Xn+m
0	s1		b1	a11	a12	…	a1n	1	0	…	0
0	s2		b2	a21	a22	…	a2n	0	1	…	0
.	.		.	.	.	…	.
.	.		.	.	.	…	.
.	.		.	.	.	…	.
0	sm		bm	am1	am2	…	amn	0	0	…	1
Contribution loss per unit:				0	0	…	0	0	0	…	0
Net contribution per units:				c1	c2	…	cn	0	0	…	0

* Negative ratio is not to be considered.

The interpretation of the data in the above ‘Tableau’ is given as under. Other simplex tableau will have similar interpretations.

(i) The first row, called the objective row of the simplex table indicates the values of C_j (j subscript refer to the column number) which are the coefficients of the (m + n) variables in the objective function. These coefficients are obtained directly from the objective function and the value C_j would remain the same in the succeeding tables. The second row of the table provides the major column headings for the table and these column headings remain unchanged in the succeeding tables of the Simplex Method.

(ii) The first column labelled C_B, also known as objective column, lists the coefficient of the current basic variables in the objective function. The second column labelled ‘Basic variables’ points out the basic variables in the basis, and in the initial simplex tableau these basic variables are the slack variables. The third column labelled ‘Solution values’ (= x_B), indicates the resources or the solution values of the basic variables.

(iii) The body matrix (under non-basic variables) in the initial simplex tableau consists of the coefficients of the decision variables in the constraint set.

(iv)The identity matrix in the initial simplex tableau represents the coefficient of the slack variables that have been added to the original inequalities to make them equation. The matrix under non-basic variables in the simplex tableau is called coefficient matrix. Each simplex tableau contains an identity matrix under the basic variables.

(v) To find an entry in the Z_j row under a column, we multiply the entries of that column by the corresponding entries of C_B – column and add the products, i.e., Z = .

The Z_j entry under the “Solution column” gives the current value of the objective function.

(vi) The final row labeled ∆_{j =} Z_j - C_j called the index (or net evaluation) row, is used to determine whether or not the current solution is optimal. The calculation of Z_j - C_j row simply involves subtracting each Z_j value from the corresponding C_j value for that column, which is written at the top of that column. Each entry in the ∆_j row represents the net contribution (or net marginal improvement) to the objective function that results by introducing one unit of each of the respective column variables.

Step 5: Test the Solution for Optimality. Examine the index row of the above simplex tableau. If all the elements in the index row are positive then the current solution is optimal. If there exist some negative values, the current solution can further be improved by removing one basic variable from the basis and replacing it by some non-basic one.

Step 6: Revision of the Current Simplex Tableau. At each iteration, the Simplex Method moves from the current basic feasible solution to a better basic feasible solution. This involves replacing one current basic variable (called the departing variable) by a new non-basic variable (called the entering variable).

(a) Determine which variable to enter into the solution-mix net. One way of doing this is by identifying the column (and hence the variable) with the most negative number in the ∆_j row of the previous table.

(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 (or solution values) column by the corresponding number in the pivot column selected in (a), i.e., we compute the respective ratios b₁/a_1j, b₂/a_2j, …, b_m/a_mj (only for those a_ij’s; i=1,2,…, m which are strictly positive). These quotients are written in the last column labelled ‘Minimum Ratio’ of the simplex tableau. The row corresponding to smallest of these non-negative ratios is called the pivot (or key) row and the corresponding basic variable will leave the basis. Let the minimum of { b₁/a_1j, b₂/a_2j, …, b_m/a_mj ; a_ij > 0} be b_k/a_kj , then corresponding variables in the pivot row s_k will be termed as outgoing (or departing) variable in the next tableau to be constructed just after we put an arrow → of type to right of k^th row of the simplex tableau 1.

(c) Identify the pivot number. The non-zero positive number that lies at the intersection of the pivot column and pivot row of the given table is called the pivot (or key) number. We place a circle around the number.

Step 7: Evaluate (update) the new solution. After identifying the entering and departing variable, find the new basic feasible solution by constructing a new simplex tableau from the current one by using the following steps:

(a) Compute new values for the pivot row by simply dividing every element of the pivot row by the pivot number.

(b) New entries in the C_B column and X_B column are entered in the new table of the current solution

(c) Compute new values for each of the remaining rows by using the following formula

New row numbers=Number in old rows-{(corresponding number above or below pivot number) x (corresponding number in the row replaced in (a))}

(d) Test for optimality. Compute the Z_j and index rows as previously demonstrated in the initial simplex tableau. If all numbers in the index row are either zero or positive, an optimal solution has been made attained. i.e., there is no variable which can be introduced in the solution to cause the objective function value to increase.

4. Revise the solution. If any of the numbers in the index (∆_j = Z_j - C_j) row are negative, repeat the entire steps 5 & 6 again until an optimal solution has been obtained.

The above procedure is illustrated through the following example.

Example 1

A firm produces three products A, B, and C each of which passes through three different departments fabrication, finishing, packaging. Each unit of product A requires 3, 4 and 2 hours respectively, B requires 5, 4 and 4 hours respectively and C requires 2, 4 and 5 hours respectively in 3 departments respectively. Every day 60 hours are available in fabrication department, 72 hours in finishing and 100 hours in packaging department. If unit contribution of unit A is Rs. 5, Rs. 10 for B and Rs. 3 for C. Then determine number of units of each product so that total contribution to cost is maximized and also determine if any capacity would remain unutilized.

Solution:        

Step 1: Formulate this as LPP.  Let X₁, X₂ and X₃ be the number of units produced of the products A, B and C respectively.

Objective function:        Max Z = 5X₁ + 10X₂ + 3X₃

Subject to constraints:    3X₁ + 5X₂ + 2X₃ ≤ 60

4X₁ + 4X₂ + 4X₃ ≤ 72

2X₁ + 4X₂ + 5X₃ ≤ 100         X_1, X_2, X₃ ≥ 0

Step 2: Now converting into standard form of LPP

                  Max Z= 5X₁ + 10X₂ + 3X₃ + 0S₁ + 0S₂ + 0S₃

                  3X₁ + 5X₂ + 2X₃ + S₁ = 60

                  4X₁ + 4X₂ + 4X₃ + S₂ = 72

                  2X₁ + 4X₂ + 5X₃ + S₃ = 100                   X₁, X₂, X₃, S₁, S₂, S₃ ≥ 0

where S₁ ,S₂ and S₃ are slack variables.

Step 3: Find the initial feasible solution .An initial basic feasible solution is obtained by setting   X₁ =0, X₂ = 0 and X₃ = 0. Thus, we get S₁ = 60, S₂ = 72 and S₃ =100.

Step 4: Construct the starting (initial) simplex tableau.

			Cj  →	5	10	8	0	0	0
	B.V.	CB	XB	X1	X2	X3	S1	S2	S3	Minimum Ratio
R1	S1	0	60	3	(5)	2	1	0	0	60/5=12
R2	S2	0	72	4	4	4	0	1	0	72/4=18
R3	S3	0	100	2	4	5	0	0	1	100/4=25
			Zj	0	0	0	0	0	0
				−5	−10	−8	0	0	0

Step 5: The most negative value of ∆_j is −10 hence X₂ is the incoming variable (↑) and the least positive minimum ratio is 12 hence S₁ is the outgoing variable (⟶). The element under column X₂ and row R₁   is the key element i.e. 5 so divide each element of row R₁ by 5 (i.e. ). Subtract appropriate multiples of this new row from the remaining rows, so as to obtain zeros in the remaining positions. Performing the row operations
we get the second Simplex tableau as   

			Cj →	5	10	8	0	0	0
	B.V.	CB	XB	X1	X2	X3	S1	S2	S3	M.R.
	X2	10	12	3/5	1	2/5	1/5	0	0	12/2/5=30
	S2	0	24	8/5	0	12/5	−4/5	1	0	24/12/5=10
	S3	0	52	-2/5	0	17/5	−4/5	0	1	52/17/5=15.294
			Zj	6	10	4	2	0	0
				1	0	−4	2	0	0

Step 6:  The most negative value of ∆_j is -4 hence X₃ is the incoming variable (↑) and the least positive minimum ratio is 10 hence S₂ is the outgoing variable (®). The element under column X₂ and row

R₁   is the key element i.e. 5 so divide each element of row R₂^b by 12/5 (i.e. R^c → R^b * 5/12). Subtract appropriate multiples of this new row from the remaining rows, so as to obtain zeros in the remaining positions. Performing the row operations .

We get the third Simplex tableau as

		Cj  →	5	10	8	0	0	0
B.V.	CB	XB	X1	X2	X3	S1	S2	S3
X2	10	8	1/3	1	0	1/3	−1/6	0
X3	8	10	2/3	0	1	−1/3	5/12	0
S3	0	18	−8/3	0	0	1/3	−17/12	1
		Zj	26/3	10	8	2/3	5/3	0
		j	11/3	0	0	2/3	5/3	0

It is apparent from this table that all ∆_j =Z_j − C_j are positive and therefore an optimum solutions is reached . So X₁ = 0, X₂ = 8, X₃ = 10

Z = 5X₁ + 10X₂ + 8X₃ = 160

And  also as S₃ is coming out to be 18 so there are 18 hours unutilized in finishing department.

In case the objective function of the given LP problem is to be minimized, then we convert it into a problem of maximization by using

Min. Z* = − Max. (−Z). The procedure of finding optimal solution using Simplex Method is illustrated through the following example:

Example 4.2

Minimize the objective function Z: X₁ – 3X₂ + 2X₃

Subject to constraints    3X₁ – X₂ + 3 X₃ ≤ 7

−2X₁ + 4X₂ ≤12

−4X₁ + 3X₂ + 8X₃ ≤10

                       X₁, X₂, X₃ ≥0

Solution

Converting this minimization problem into maximization problem

Objective function Max Z^#: −X₁ – 3X₂ + 2X₃ + 0S₁ + 0S₂ + 0S₃

Constraints 3X₁ – X₂ + 3 X₃ + S₁ = 7

−2X₁ + 4X₂ + S₂ = 12

−4X₁ + 3X₂ + 8X₃ + S₃ = 10

X₁, X₂, X₃, S₁, S₂, S₃ ≥0

Starting Simplex Table

		Cj	−1	3	−2	0	0	0
B.V.	CB	XB	X1	X2	X3	S1	S2	S3	Min. Ratio
S1	0	7	3	−1	3	1	0	0	-
S2	0	12	−2	4	1	0	1	0	3    →
S3	0	10	−4	3	8	0	0	1	10/3
		j	1	−3	2	0	0	0

Now performing the row operations

		Cj	−1	3	−2	0	0	0	Min. Ratio
B.V.	CB	XB	X1	X2	X3	S1	S2	S3
S1	0	10	5/2	0	3	1	1/4	0	4  →
X2	3	3	−1/2	1	0	0	1/4	0	-
X3	0	1	−5/2	0	8	0	−3/4	1	-
		j	−1/2	0	2	0	3/4	0

Now performing the row operations

↑		Cj	−1	3	−2	0	0	0
B.V.	CB	XB	X1	X2	X3	S1	S2	S3
X1	−1	4	1	0	6/5	2/5	1/10	0
X2	3	5	0	1	3/5	1/5	3/10	0
S3	0	11	0	0	11	1	−1/2	1
		∆j	0	0	13/5	1/5	4/5	0

Now all ∆_j are positive. Therefore, Optimal Solution is reached  

Therefore, X₁ = 4, X₂ = 5 & X₃ = 0 & Max Z^# = −14 + 35 = 11 Or Minimum Z = −Z^# = −11