Simplex Method

The simplex method was developed by George Dantzig in 1949. This method overcomes the limitation of the graphical method and can be applied to problems where the number of decision variables is more than two. The algorithm for the simplex method is iterative in nature and solves a problem in a systematic manner to determine the optimum solution for a problem.

However, the following points should be kept in mind before solving any problem:

• The value of the constraint in the right-hand side of each of the constraints should be non-negative. If not, it should be converted into a non-negative value.

• Each decision variable of the problem should be non-negative.

• Slack variables are introduced in each constraint equation as an idle source to convert inequalities to equalities.

Several operations managers prefer the simplex method because of its advantages:

• The algorithm of the simplex method moves from one extreme point to a better (or at least equally good) extreme point, by skipping many sub-optimal extreme points. Thus, the problem checks only a limited number of points to determine the optimal solution. This saves the time and computing effort.

• The simplex method finds the point where the problem has to be stopped and thereby reduces the effort of verifying for optimality at each and every step.

• The algorithm detects whether the problem is infeasible, unbounded or has multiple solutions.

• The simplex algorithm can be easily computerized as the method involves simple mathematical calculations.

The simplex method is explained below in Problem.

Problem 

Solve the linear programming problem formulated in Table 4.3 by using the Simplex method.

Solution:

The objective of the problem is to maximize the function, Z =700x₁+400x₂

The constraints are:

2x₁ + x₂ ≤ 3000,

x₁ + 2x₂ ≤ 4000,

x₁ + x₂ ≤ 2500,

x₁, x₂ ≥0.

Adding slack variables to the problem,

Maximize, Z = 700x₁ + 400x₂ +0 S₁ + 0 S₂ + 0 S₃

Subject to

2x₁ + x₂ + S₁ = 3000,                  

Table: Initial Simplex Table

x₁+ 2x₂ + S₂ = 4000,

x₁ + x₂ + S₃ = 2500,

x₁, x₂, x₃, S_1, S₂, S₃, ≥0.

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

The initial simplex table is developed as shown in Table 4.5.

The highest element in the Index or (C_j - Z_j) row is 700. Therefore, the x₁ column becomes the key column and x₁ is called the entering variable. The ratios are obtained by dividing the solution variables with the corresponding elements of the key column.

The row with minimum ratio is called the key row and the intersection element of the key row and the key column becomes the key element. Here, 'S₁' row is the key row and '2' is the key element. The variable S₁ is called the departing variable.

Now, the new simplex table is developed by using the following procedure.

All the values in the key row are divided by the key element to obtain the new values and the departing variable S₁ is replaced by the entering variable x₁.

Thus the values of the revised key row are:

The new values for each remaining row (other than the key row) are computed by using the formula:

New row value = Old row value - (Corresponding value in the key row × Corresponding value in the revised key row).

Thus the new values of 'S₂' row are obtained as shown below.

'S₂' row:

Table: Simplex Table

Similarly, the new 'S₃' row is calculated as shown below.

'S₃' row:

These new values are shown in the Simplex Table I.

From the Simplex Table 1, the largest positive value in the (C_j - Z_j) row is 50 and it lies in 'x₂' column. So, 'x₂' becomes the entering variable and the 'x₂' column becomes the key column.

The ratios obtained by dividing the solution variables with the values in the key column are 3000, 5000/3 and 2000. Here, 5000/3 is the minimum ratio. Therefore, the S₂ row becomes the key row and the variable 'S₂' becomes the departing variable. The key element is '3/2.'

Now, the departing variable, S₂ is replaced by the entering variable x₂ and the revised key row is obtained by dividing all the values in the key row with the key element.

The revised key row is,

The new 'x₁' row can be developed as shown below.

Here, the corresponding element is 1/2.

'x₁' row:

The new 'S₃' row is calculated as shown below.

'S₃' row:

These values are shown in Simplex Table.

Since there is no positive value in the (C_j - Z_j) row of the Simplex Table 2, further simplex table cannot be developed. Therefore, the optimum solution is

x₁ = 2000/3, x₂ = 5000/3, and

The maximum value of the profit at this optimum solution is

Z_max = 700x₁ + 400x₂

= 700(2000/3) + 400 (5000/3)

= Rs. 11,33,333.

Table: Simplex Table

Email based Operations Management assignment help - homework help at Expertsmind

Are you searching Operations Management expert for help with Simplex Method questions? Simplex Method topic is not easier to learn without external help?  We at www.expertsmind.com offer finest service of Operations Management assignment help and Operations Management homework help. Live tutors are available for 24x7 hours helping students in their Simplex Method related problems. We provide step by step Simplex Method question's answers with 100% plagiarism free content. We prepare quality content and notes for Simplex Method topic under Operations Management theory and study material. These are avail for subscribed users and they can get advantages anytime.

Why Expertsmind for assignment help

1. Higher degree holder and experienced experts network
2. Punctuality and responsibility of work
3. Quality solution with 100% plagiarism free answers
4. Time on Delivery
5. Privacy of information and details
6. Excellence in solving Operations Management questions in excels and word format.
7. Best tutoring assistance 24x7 hours