Questions on Simplex algorithms and Sensitivity analysis By

Questions on Simplex algorithms and Sensitivity analysis: By using simplex algorithm to solve a linear program with to be maximized, under which condition the problem has unique optima Assume by Simplex algorithm, we obtain the following two optimal solutions in two tableaus, how can you express all possible optimal solutions? 1^st optimal solution: x_1 = 2, x_2 = 0, x_3 = 6; and 2nd optimal solution: = 1.5,x_2 =3,x_3 = 2.6. For a linear program with objective to be maximized, under which condition the problem is unbounded? In sensitivity analysis, assume that the coefficient of a basic variable in the objective function changes within a range that the current basis remains optimal, will the optimal solution for decision variables change? How about the optimal objective value? (use the following formulations) In sensitivity analysis, when the right-hand-side (RHS) of a constraint changes, how can you find range for this RHS in which the current basis remains optimal? (use the following formulations)

Solution

2.1 In a simplex algorithm, for a linear problem to have a unique optimal solution, the value of maximum z in the tableau must be non negative.

2.2 In a simplex algorithm, for a linear problem the solution improves and finally comes to an optimal solution. Hence the optimal solution can be expressed only by making the z_j greater than 0, the corresponding basic variables gives the optimal solution.

2.3 A linear program is unbounded if the optimal solution is unbounded, i.e. it is either or .

2.4 Whether a tableau is feasible and optimal depends only upon the rhs of the constraints and the objective function coefficients of each variable in row 0.

Suppose we have solved an LP and have found the BV is an optimal basis. Use the following procedure to determine if any change in the LP will cause the BV to no longer be optimal.

Step 1 Determine how changes in the LP’s parameters change the right hand side row 0 of the optimal tableau (the tableau having BV as the set of basic variables).

Step 2 If each variable in row 0 has a nonnegative coefficient and each constraint has a nonnegative rhs, BV is still optimal. Otherwise, BV is no longer optimal. If BV is no longer optimal, find the new optimal solution to recreate the entire tableau for BV and then continuing the simplex algorithm with the BV tableau as your starting tableau.

2.5 The optimal basis remains unchanged as long as The resulting RHS in the final tableau are nonnegative.

Concept: In a constraint with a positive slack (or positive excess) in an LPs optimal solution, if we change the rhs of the constraint to a value in the range where the basis remains optimal, the optimal solution to the LP remains the same.