Suppose that we are given a subroutine which, given a system of linear inequalities A x ≤ b, x ∈ R n , either produces a solution or decides that no solution exists.Construct an algorithm that uses a single call of this subroutine and which returns an optimal solution (if it exists) to the following linear programming problem: minimize c T x subject to: A x = b x ≥ 0 Well, I think I should take a look at the dual problem.The dual is: maximize p T b subject to: A T p ≤ c Then I would call the subroutine for the matrix A T and to the vector c to find a dual feasible point y.I tried to use complementary slackness to construct a primal solution and to decide if y is optimal but it didn't work .

Question

Suppose that we are given a subroutine which, given a system of linear inequalities   A  x  ≤  b,   x  ∈        R    n  , either produces a solution or decides that no solution exists.Construct an algorithm that uses a single call of this subroutine and which returns an optimal solution (if it exists) to the following linear programming problem:                    minimize                               c          T                x                                        subject to:                     A        x                    =                    b                                  x                    ≥                    0            Well, I think I should take a look at the dual problem.The dual is:                    maximize                               p          T                b                                        subject to:                               A          T                p                    ≤                             c            Then I would call the subroutine for the matrix       A    T   and to the vector   c to find a dual feasible point   y.I tried to use complementary slackness to construct a primal solution and to decide if   y is optimal but it didn&#039;t work .

candelo6a · Accepted Answer

Simply combine all your primal and dual constraints and let dual objective value be less than or equal to that of primal (only holds if solution is optimal). Solve the resulting system of equality and inequalities using the subroutine.

Suppose that we are given a subroutine which, given a system of linear inequalities A x &#x22

Answered question

Answer & Explanation

New Questions in Algebra I