Question

(Operation Research II Industrial Engineering)

Consider the following LP:

Minimize z = x₁ + 2x₂

Subject to x₁ + x₂ >= 1

-x₁ + 2x₂ <= 3

x₂ <= 5

x₁,x₂ >= 0

(a) Convert the LP given above to the standard form. Determine all the basic feasible solutions (bfs) of the problem. Give the values of both basic and nonbasic variables in each bfs.

(b) Identify the adjacent basic feasible solutions of each extreme point of the feasible region. Using the graphical solution technique, solve the problem. Which constraints are active (binding) in the optimal solution? Which constraint(s) is(are) redundant?

(c) To have alternative optimal solutions on the first constraint, what should be the objective function coefficient of the variable x₁?

(d) Using the big-M simplex method, solve the LP where the constraint -x₁ + 2x₂ <= 3 is replaced by -x₁ +2x₂ = 3.

(e) Using the two phase method, solve the LP.

Answer 1

We have to convert the given LP in standard form

Minimize z = x1 + 2x2

Subject to x1 + x2 >= 1

-x1 + 2x2 <= 3

x2 <= 5

x1,x2 >= 0

Let us first turn the objects into max and constrains into equalities as follows:

Max z = -x1 – 2x2

Subject to x1 + x2 - s1 = 1

                  -x1 + 2x2 + s1 = 3

                  x2 <= 5, x1,x2 >= 0, s1>0. s2>0

In the last step we convert the non restricted variable x1 into two non negative variables: x1= x1’-x2’

Max z = x1’ – x2’ - 2x2

Subject to x1’ – x2’ + x2 –s1 = 1

                 -x1’ + x2’ + 2x2 + s1 = 3

                 x1’> 0, x2’ > 0, x2 <= 5, x1, x2>= 0, s1>=0, s2 >= 0

Thus the LP is converted into standard form.