The following refer to a primal-dual (min-max) pair P and D of linear programming problems in...

 

Transcribed Image Text:

The following refer to a primal-dual (min-max) pair P and D of linear programming problems in canonical form. Provide a brief explanation with your answers. a. If a basic solution to the primal is infeasible and has an objective value less than the optimal value, then the associated complementary dual basic solution is feasible. True or False? b. For the linear program Minimize (x₁: 2x₁ - x₂ ≥ 0, -2x₂ + 3x₂ 2-6, x>0}, consider the basic feasible solution with a basis comprised of the columns of x, and the slack variable in the second constraint. Give the associated complementary dual basic solution. What can you say about this pair of primal-dual basic solutions? c. If P has alternative optimal solutions and if w* is any optimal basic feasible solution for D, then we must be degenerate. True or False? d. Let z* be the common (finite) optimal value of P and D. Suppose that x is a basic infeasible solution to P whose complementary dual basic solution is feasible. It is possible that the common objective value of this pair of primal-dual basic solutions is z? e. If P is unbounded, it is possible to change its right-hand-side and make it have a finite optimum. True or False? f. Referring to Figure 6.4a, suppose that -e is aligned along -A₁. Consider the basic solution with basis B = (a, a, ag]. Comment on the corresponding pair of complementary primal and dual basic solutions with respect to feasibility, optimality, and degeneracy. shows the optimal solution of a linear x2 *4 = 0 *5 = 0 *2 = 0 -A2 Case (a) }} X1 The following refer to a primal-dual (min-max) pair P and D of linear programming problems in canonical form. Provide a brief explanation with your answers. a. If a basic solution to the primal is infeasible and has an objective value less than the optimal value, then the associated complementary dual basic solution is feasible. True or False? b. For the linear program Minimize (x₁: 2x₁ - x₂ ≥ 0, -2x₂ + 3x₂ 2-6, x>0}, consider the basic feasible solution with a basis comprised of the columns of x, and the slack variable in the second constraint. Give the associated complementary dual basic solution. What can you say about this pair of primal-dual basic solutions? c. If P has alternative optimal solutions and if w* is any optimal basic feasible solution for D, then we must be degenerate. True or False? d. Let z* be the common (finite) optimal value of P and D. Suppose that x is a basic infeasible solution to P whose complementary dual basic solution is feasible. It is possible that the common objective value of this pair of primal-dual basic solutions is z? e. If P is unbounded, it is possible to change its right-hand-side and make it have a finite optimum. True or False? f. Referring to Figure 6.4a, suppose that -e is aligned along -A₁. Consider the basic solution with basis B = (a, a, ag]. Comment on the corresponding pair of complementary primal and dual basic solutions with respect to feasibility, optimality, and degeneracy. shows the optimal solution of a linear x2 *4 = 0 *5 = 0 *2 = 0 -A2 Case (a) }} X1

Answer rating: 100% (QA)

a False A basic solution to the primal is infeasible if and only if the corresponding complementary dual basic solution is infeasible The objective va... View the full answer