Masud Salimian's Operations Research Course - Solved Problems

Course: Operations Research
Subject: Revised Simplex
Problem^*

You may use MAPLE to check the accuracy of your matrix manipulation.

Consider the following problem.

, , ,

Use revised simplex method to find the optimal solution.

* Source: IEGR 440: Deterministic Models of Operations Research

SOLUTION

1. First Basis

Writing the standard form of the constraints. Our initial basis consists of S1, S2, and S3.

We have the following information:

Calculate

, and

are non basic variable, Check optimality conditions.
At this point we can either calculate

and

and use the results, or just calculate those elements associated with non-basic variable, namely,

and

. for

, and

. Note that we already know that

, and

are basic variables.

This basis is not optimal because of the presence of negative values in

and

(note that these two row vectors are the optimality condition for the LP). The most negative value is -5 corresponding to

, thus

is our entering variable. To identify the leaving variable we need to find the ratios of

elements to entering variable column elements,

, excluding the ratios for negative and zero elements of

Min Ratio = Min { 18/3, 20/2, 16/1 } = 6 corresponding to . Therefore, enters the basis and leaves the basis. We will set up the new basis and repeat the same steps.

2. Second Basis

Calculate

and

are non basic variable, Check optimality conditions.

This basis is not optimal because of the presence of negative values in

and

(note that these two row vectors are the optimality condition for the LP). The most negative value is -7/3 corresponding to

, thus

is our entering variable. To identify the leaving variable we need to find the ratios of

elements to entering variable column elements,

, excluding the ratios for negative and zero elements of

Min Ratio = Min { 6/(1/3), 8/(4/3), __ } = 6 corresponding to . Therefore, enters the basis and leaves the basis. We will set up the new basis and repeat the same steps.

3. Third Basis

Calculate

and

are non basic variable, Check optimality conditions. Remember that optimality check for

and

is through

which doen not contain any negative values (1/2, 7/4 and 0 calculated above)

This basis is not optimal because of the presence of a negative values in

and

. This value (-1/4 for

) indicates that

ie the entering variable. To identify the leaving variable we need to find the ratios of

elements to entering variable column elements,

, excluding the ratios for negative and zero elements of

Min Ratio = Min { 4/(3/4), __ , 12/(5/4) } = 16/3 corresponding to . Therefore, enters the basis and leaves the basis. We will set up the new basis and repeat the same steps.

4. Fourth Basis

Calculate

and

are non basic variable, Check optimality conditions. Optimality check for

and

is through

which doen not contain any negative values (2/3, 5/3 and 0 calculated above)

This basis is optimal since there in no negative value in

and

. This optimal solution is:

, , , and

This solution matches the one provided by LINDO.

	 LP OPTIMUM FOUND AT STEP      2

        OBJECTIVE FUNCTION VALUE

        1)      45.33333

  VARIABLE        VALUE          REDUCED COST
        X1         5.333333          0.000000
        X2         0.000000          0.333333
        X3         7.333333          0.000000
        X4         0.000000          3.666667


       ROW   SLACK OR SURPLUS     DUAL PRICES
        2)         0.000000          0.666667
        3)         0.000000          1.666667
        4)         5.333333          0.000000

 NO. ITERATIONS=       2