Simplex Method Assignment Help

Solution of Linear Programming Problems - Simplex Method

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 =700x1+400x2

The constraints are:

2x1 + x2 ≤ 3000,

x1 + 2x2 ≤ 4000,

x1 + x2 ≤ 2500,

x1, x2 ≥0.

Adding slack variables to the problem,

Maximize, Z = 700x1 + 400x2 +0 S1 + 0 S2 + 0 S3

Subject to

2x1 + x2 + S1 = 3000,                  

Table: Initial Simplex Table

1628_initial simplex table.png

x1+ 2x2 + S2 = 4000,

x1 + x2 + S3 = 2500,

x1, x2, x3, S1, S2, S3, ≥0.

Where, S1, S2, and S3 are slack variables.

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

The highest element in the Index or (Cj - Zj) row is 700. Therefore, the x1 column becomes the key column and x1 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, 'S1' row is the key row and '2' is the key element. The variable S1 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 S1 is replaced by the entering variable x1.

Thus the values of the revised key row are:

 

1500

1

1/2

1/2

0

0

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 'S2' row are obtained as shown below.

'S2' row:

4000

1

2

0

1

0

- (Corresponding element, i.e. 1) × (value in the revised row):

1500

1

1/2

1/2

0

0

Table: Simplex Table

605_simplex table.png

 

The new 'S2' row is:

2500

0

3/2

-1/2

1

0

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

'S3' row:

2500

1

1

0

0

1

- (corresponding element, i.e. 1) × (value in the revised row):

1500

1

½

½

0

0

The new 'S3' row is:

1000

0

1/2

-1/2

0

1

These new values are shown in the Simplex Table I.

From the Simplex Table 1, the largest positive value in the (Cj - Zj) row is 50 and it lies in 'x2' column. So, 'x2' becomes the entering variable and the 'x2' 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 S2 row becomes the key row and the variable 'S2' becomes the departing variable. The key element is '3/2.'

Now, the departing variable, S2 is replaced by the entering variable x2 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,

5000/3

0

1

-1/3

2/3

0

The new 'x1' row can be developed as shown below.

Here, the corresponding element is 1/2.

'x1' row:

1500

1

1/2

1/2

0

0

-(corresponding element, i.e. 1/2 × corresponding value in the revised row)

2500/3

0

½

-1/6

1/3

0

The new 'x3' row:

2000/3

1

0

2/3

-1/3

0

The new 'S3' row is calculated as shown below.

'S3' row:

1000 0 1/2 -1/2 0

1

-(corresponding element, i.e. ½ × corresponding value in the revised row)
2500/3 0 1/2 -1/6 1/3

0

The new 'S3' row is:
500/3 0 0 -1/3 -1/3

1

These values are shown in Simplex Table.

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

x1 = 2000/3, x2 = 5000/3, and

The maximum value of the profit at this optimum solution is

Zmax = 700x1 + 400x2

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

= Rs. 11,33,333.

Table: Simplex Table

Cj

700

400

0

0

0

CB

Basic variables

Solution variables

x1

x2

S1

S2

 S3

700

x1

2000/3

1

0

2/3

-1/3

0

400

x2

5000/3

0

1

-1/3

2/3

0

0

S3

500/3

0

0

-1/3

-1/3

1

 

 

Zj

700

400

1000/3

100/3

0

 

 

(Cj-Zj)

0

0

-1000/3

-100/3

0                                          

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