Consider the following linear programming problem P:

Maximize z = 6x₁ + 4 x₂

Subject to x₁ + x₂ 8 (1)

2x₁ -2 x₂ 8 (2)

x₁ - x₂ 2 (3)

____________________________________

x₁ 0

x₂ unconstrained in sign

Let the slack of constraint (1) and (2) be x₃ and x₄, respectively, and the surplus of constraint (3) be x₅. Answer the following independent questions:

1 Solve the problem graphically:

(i) Identify the feasible region by its corner points (coordinates x₁ and x₂ ) and shade it.

(ii) Find the optimal point(s) on the graph and write the optimal values of all the variables and z below.

x1 =

x2 =

x3 =

x4 =

x5 =

z=

2 Determine the optimal solution(s), if instead of maximization the objective was minimization.

3 For each one of the three points given by their coordinates (x₁, x₂) below, determine if the point is feasible or infeasible. If feasible, find out if any constraints are active (binding) at that point. If infeasible, indicate the violated constraint(s). Justify your answer by checking each constraint.

(4, 3)

(3, -1)

(4, 1)

4 Consider varying the right-hand side of constraint (3) from its current value (b₃ = 2). Determine

1. its lowest value below which the problem becomes redundant and

(b) its highest value beyond which the problem becomes infeasible.

5 What is the optimal solution if both x₁ and x₂ are unconstrained in sign?

6 What is the optimal solution, if

(i) constraint (3) is removed from the formulation?

.

(ii) constraint (2) is removed from the formulation?

7 Construct the initial basic solution by adding artificial variables and making the necessary variable transformations so that you can apply the Big-M method to Problem P. Set up the iteration (0) tableau. Indicate the entering and leaving variable and perform a single iteration. Write the resulting basic solution of iteration (1) and indicate whether it is feasible or infeasible to Problem P. Indicate on the graph the point this solution corresponds to and state whether it is a corner point of the feasible region of Problem P or not. Do not perform more than one iteration!