1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linear Programming double inequalities

  1. Sep 6, 2011 #1

    zcd

    User Avatar

    1. The problem statement, all variables and given/known data
    Find the dual of
    [tex]-d \leq Ax-b \leq d[/tex]
    [tex] x \geq 0; c \cdot x = min[/tex]
    where A is mxn matrix and [tex] x,d,b \in \mathbb{R}^n[/tex]

    2. Relevant equations
    dual of canonical is of the form
    maximize [tex]b \cdot y[/tex]
    [tex]A^{T}y \leq [/tex]
    where [tex] y \in \mathbb{R}^m[/tex]
    3. The attempt at a solution
    I tried converting it to the canonical LP and then applying transpose to A, but it turned out to be a huge mess; is there a simpler way?
     
  2. jcsd
  3. Sep 6, 2011 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Do you know how to write the dual of an LP of the form
    [tex] \min \; c \cdot x [/tex]
    s.t.
    [tex]F x \geq f [/tex]
    [tex] x \geq 0 ? [/tex]
    Just re-write your LP in that form and use what you already know.

    RGV
     
  4. Sep 6, 2011 #3

    zcd

    User Avatar

    How would I combine two separate matrix inequalities to one?
    [tex]Ax \geq b-d[/tex]
    [tex]-Ax \geq -b-d[/tex]
     
    Last edited: Sep 6, 2011
  5. Sep 6, 2011 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You've just done it. Can't you see what the matrix F is?

    RGV
     
  6. Sep 6, 2011 #5

    zcd

    User Avatar

    My guess would be to make a block matrix on the left with A and -A vertically and a block vector with b-d and -b-d on the right. Could it be this simple?
     
  7. Sep 7, 2011 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Yes.

    RGV
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Linear Programming double inequalities
  1. Linear programming (Replies: 2)

  2. Linear Programming (Replies: 10)

  3. Linear programming (Replies: 2)

  4. Linear Programming (Replies: 0)

  5. Linear Programming (Replies: 0)

Loading...