LINEAR PROGRAMMING –SIMPLEX METHOD

Objectives

Formulate the standardized LPP

b. Identify the use of slack, surplus and artificial variables

c. Identify the solving method

d. Formulate the initial simplex table

e. Calculate the tables for each iteration

f. Calculate the shadow costs/profits

Example-1

The LPP is maximize Z = 6x1 + 4x2

Subject to the constraints

Solution:

Introducing slack variables, the above problem becomes,

Maximize z = 4x1 + 3x2 + 0S1 + 0S2 + 0S3

Subject to

 

Example-2

                Maximize Z = 6x1 + 4x2

Subject to the constraints

Solution:

Convert inequality constraints into equality constraints by introducing slack

Variables.

 The LPP is

Max. Z = 6x1 + 4x2 + 0.S1 + 0.S2 + 0.S3

subject to

2x1 + x2 + S1 = 390

3x1 + 3x2 + S2 = 810

X2 + S3 = 200

x1, x2, S1, S2, S3 0

 

Example:3

Solve the following linear programming problem by simplex method.

Minimize Z = 16x1 + 16x2

Subject to

Solution:

Convert inequality constraints into equality constraints by introducing surplus and

artificial variables.

The LPP is minimize Z = 16x1 + 16x2 + 0.S1 + 0.S2 + MA1 + MA2

Subject to

2x1 + 4x2 – S1 + A1 = 3

3x1 + 2x2 – S2 + A2 = 4

x1, x2, S1, S2, A1, A2 0

from the following table we can conclude  that all the Zj – Cj 0.

With Min Z =22

 x1 =5/4,;

x2 =1/8

 

Previous University Examination Questions:

1)     Define a feasible region.

2)    Define a feasible solution

3)     What is a redundant constraint

4)    Define optimal solution

5)    What is the difference between feasible solution and basic feasible solution

6)    Define the following:
(a) Basic solution
(b) non-degenerate solution
(c) degenerate solution.
(a) Basic solution

7)    Define unbounded solution

8)    What are the two forms of a LPP?

        

    

9)      When does the simplex method indicate that the LPP has unbounded solution?

10)  What is meant by optimality?

11)  How will you find whether a LPP has got an alternative optimal solution or not, from the optimal simplex table?

12)  What are the methods used to solve an LPP involving artificial variables?

13)  Define artificial variable.

14)  When does an LPP possess a pseudo-optimal solution?

15)  What is degeneracy?                                       

16)  Solve Graphically Following LPP

Related Topics
Linear Programming Problem
Linear Programming: Graphical Method