1

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.

shinobutime
  • 43

1 Answers1

3

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}$.

Traklon
  • 2,838
  • x >= 0 and x <= 4 must be stated explicitly as different constraints in order to satisfy the definition? – shinobutime Oct 29 '14 at 08:00
  • 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$. – Traklon Oct 29 '14 at 08:12
  • $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. – IainDunning Oct 29 '14 at 13:14