Given a system A x ≤ b of linear inequalities, describe a linear programming problem whose optimal solution immediately tells us which inequalities among A x ≤ b are always satisfied with equality.I wonder if I could use the theorem: assume both optima of max ( c T x | A x ≤ b ) = min ( y T b | y ≤ 0 , y T A = c T ) are finite, then x 0 and y 0 are optimum solutions iff if a component of y 0 is positive, the corresponding inequality in A x ≤ b is satisfied by x 0 with equality y 0 T ( b − A x 0 ) = 0.

Question

Given a system   A  x  ≤  b of linear inequalities, describe a linear programming problem whose optimal solution immediately tells us which inequalities among   A  x  ≤  b are always satisfied with equality.I wonder if I could use the theorem: assume both optima of   max      (          c      T        x      |    A    x    ≤    b    )    =  min      (          y      T        b      |    y    ≤    0    ,          y      T        A    =          c      T        )   are finite, then       x    0   and       y    0   are optimum solutions iff if a component of       y    0   is positive, the corresponding inequality in   A  x  ≤  b is satisfied by       x    0   with equality       y    0    T    (  b  −  A      x    0    )  =  0.

publyk65y0w · Accepted Answer

I think it runs down to look at  A  x  +  y  =  b    y  ≥  0where   y  ∈      K    m   is a slack variable. And then check y for zero components (equation) or positive components (inequality).This means we e.g. go from this problem                          min                  c          ⊤                x                                      w.r.t.                            A        x        ≤        b            to this problem                    x                            ↦                  x          ′                =        (                  x          ⊤                                  y          ⊤                          )          ⊤                ∈                  K                      n            +            m                                              A                            ↦                  A          ′                =        (        A                          I          m                )        ∈                  K                      m            ×            (            n            +            m            )                                              A        x        ≤        b                            ↦                  A          ′                          x          ′                =        b        ∧        y        =        (                  0                      m            ×            n                                            I          m                )                          x          ′                =        B                  x          ′                ≥        0                            c                            ↦                  c          ′                =        (                  c          ⊤                                  0          m          ⊤                          )          ⊤                ∈                  K                      n            +            m                              where       I    m   is the identity of       K          m      ×      m      ,       0          m      ×      n       is the zero of       K          m      ×      n       and       0    m   is the zero of       K    m  , thus                          min                  c                      ′            ⊤                                    x          ′                                              w.r.t.                                      A          ′                          x          ′                =        b                                  B                  x          ′                ≥        0

Given a system A x ≤ b of linear inequalities, describe a linear programm

Answered question

Answer & Explanation

New Questions in Algebra I