I'm new to linear programming and can't wrap my head around something.

Let P be a LP in standard form

$$\begin{array}{ll} \text{maximize} & t x\\ \text{subject to} & r x \leq s\\ & x \geq 0\end{array}$$

I figured that the dual program is

$$\begin{array}{ll} \text{minimize} & s y\\ \text{subject to} & r y \geq t\\ & y \geq 0\end{array}$$

However I'm unsure how to find what is a feasible solution for P and not for D and vice versa. Intuitively, if $s$ is positive P should have a feasible solution, but that seems to be wrong and/or incomplete as an answer.

  • 1
    $\begingroup$ That's canonical form $\endgroup$ – Eugene Feb 25 '17 at 22:06
  • $\begingroup$ I have no idea what you're asking. A feasible solution for P is an assignment for $x$ that satisfies the constraints, whereas a feasible solution for D is an assignment for $y$ that satisfies the constraints. If $x,y$ don't have the same dimensions, there is no "solution" that fits both P and D. $\endgroup$ – Yuval Filmus Feb 26 '17 at 3:39
  • $\begingroup$ Hint. If you have only one or two (three if you're feeling adventurous) variables in your LP, you can plot the feasible region. The feasible region is the set of feasible solutions. This should give you an understanding of how a feasible region looks like. $\endgroup$ – Auberon Feb 26 '17 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.