(Operation Research II Deterministic Problems Industrial Engineering) Consider t
ID: 3282254 • Letter: #
Question
(Operation Research II Deterministic Problems Industrial Engineering)
Consider the following LP:
Minimize z = x1 + 2x2
Subject to x1 + x2 >= 1
-x1 + 2x2 <= 3
x2 <= 5
x1,x2 >= 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 x1?
(d) Using the big-M simplex method, solve the LP where the constraint -x1 + 2x2 <= 3 is replaced by -x1 +2x2 = 3.
(e) Using the two phase method, solve the LP.
Explanation / Answer
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.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.