0
$\begingroup$

This is what my lecturer says on standard and canonical forms: "Two particular forms of the linear programming problem are of interest for m equations in n unknowns. These are called the standard form, i.e. minimise $\underline{c}^T\underline{x}$ subject to $A\underline{x} ≥ \underline{b}$, $\underline{x} ≥ \underline{0}$ and the canonical form, i.e. minimise $\underline{c}^T\underline{x}$ subject to $A\underline{x} = \underline{b}$, $x ≥ 0$."

The question says: Put the following LP into canonical form (do not try to solve) Minimise $z=x_1+2x_2+3x_3$ subject to $$3x_1+4x_3\leq5$$ $$5x_1+x_2+6x_3 \leq 7$$ $$8x_1+9x_3\geq2$$ With all vairables non-negative.

So I started off by trying to convert it to standard form and adding in the slack and surplus variables so I have $$3x_1+4x_3+s_1=5$$ $$5x_1+x_2+6x_3+s_2= 7$$ $$8x_1+9x_3-s_3=2$$

but I'm confused about what the vectors $\underline{x}, \underline{c}, \underline{b}$ and the matrix $A$ is.

I read another a question where the answer suggested that $$\underline{x}=\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}, \underline{c}= \begin{pmatrix} 1\\ 2\\ 3 \end{pmatrix}, \underline{b}=\begin{pmatrix} 5\\ 7\\ 2 \end{pmatrix}, A= \begin{pmatrix} 3 & 0 & 4 \\ 5 & 1 & 6 \\ 8 & 0 & 9 \end{pmatrix}$$ but I don't see where the slack and surplus variables come into play.

$\endgroup$
2
$\begingroup$

Your $\underline{b}$ is correct. The rest should be: $$\underline{x} = \begin{pmatrix}x_1\\x_2\\x_3\\s_1\\s_2\\s_3 \end{pmatrix},\ \underline{c} = \begin{pmatrix}1\\2\\3\\0\\0\\0 \end{pmatrix},\ A = \begin{pmatrix}3 &0 &4 &1 &0 &0\\ 5 &1 &6 &0 &1 &0\\ 8 &0 &9 &0 &0 &-1 \end{pmatrix}$$

$\endgroup$
  • $\begingroup$ oh okay thank you! I got $\underline{c}$ and $A$ before but I didn't realize you had to add $s_1$, $s_2$ and $s_3$ to $\underline{x}$ so I assumed they were wrong. $\endgroup$ – hiling99 Oct 5 '19 at 22:24

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.