1
$\begingroup$

A linear program is said to be in canonical form if it has the following format: Maximize $c^Tx$ subject to $Ax ≤ b$, $x ≥ 0$ where $c$ and $x$ are n-dimensional real vectors, $A$ is an $m × n$ matrix with real entries, and $b$ is an m-dimensional real vector.

Maximize $x + y$ subject to

$x − y ≤ 3$

$2x + y ≤ 12$

$0 ≤ x ≤ 4$

$0 ≤ y ≤ 6$

Is this program already in canonical form as defined here? I am having trouble understanding the definition and how it relates to a program like this one. Thanks in advance.

$\endgroup$
3
$\begingroup$

You're probably mixing two things : the $x$, as it is in the definition of the canonical form, and the $x$ as a variable. Let's call $X$ the $x$ in the definition.

Note that you can transform $0 ≤ x ≤ 4$ and $0 ≤ y ≤ 6$ in $x \geq 0, x ≤ 4, y \geq 0$ and $ y ≤ 6$.

Then, $X = \pmatrix{x \cr y}, A = \pmatrix{1 & -1 \cr 2 & 1 \cr 1 & 0 \cr 0 & 1}, b = \pmatrix{3 \cr 12 \cr 4 \cr 6}$ and $c = \pmatrix{1 \cr 1}$.

$\endgroup$
  • $\begingroup$ x >= 0 and x <= 4 must be stated explicitly as different constraints in order to satisfy the definition? $\endgroup$ – shinobutime Oct 29 '14 at 8:00
  • $\begingroup$ Anyway, $0 \leq x \leq 4$ is two different constraints. They are just stated together here. But yes, you're right. $x \leq 4$ is a constraint cointained in $AX \leq b$ and $x \geq 0$ is a constraint contained in $X \geq 0$. $\endgroup$ – Traklon Oct 29 '14 at 8:12
  • $\begingroup$ $x\geq0$ is implicit in this standard form, $x\leq4$ is not. It turns out that many (most?) solvers for LP actually internally do not do this, and instead will keep it as $0\leq x\leq4$ for efficiency reasons. $\endgroup$ – IainDunning Oct 29 '14 at 13:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.