# Can linear programming be used to solve Ax = b equations?

Assume that we have a system $$Ax = b$$ and we want to solve that with constraints.

Can linear programming be used to solve the $$x$$ from $$Ax = b$$?

Assume that we have the objective function

$$max : c^T x$$ With the constraints:

$$x \ge 0 \\ Ax \le b$$

This is on the standard form of linear programming.

What should $$c$$ vector be then? Should it be $$c = A^T b$$ ?

• I think the purpose of this exercise is to understand that any linear program can be written in standard form. Basic idea: maximize $0(x^+ - x^-)$ subject to $x^+ \geq 0, x^- \geq 0, A(x^+ - x^-) \leq b, -A(x^+ - x^-) \leq b$. – littleO Nov 21 '19 at 18:44
• @littleO Why x+ and x- ? – Daniel Mårtensson Nov 21 '19 at 18:45

Two hints:

1. Rewrite $$Ax=b$$ as $$Ax \le b$$ and $$-Ax\le -b$$.
2. Rewrite $$x$$ as $$x^+ - x^-$$, where $$x^+ \ge 0$$ and $$x^- \ge 0$$.

Explicitly: \begin{align} &\text{maximize} &0(x^+ - x^-) \\ &\text{subject to} &A(x^+ - x^-) &\le b \\ &&-A(x^+ - x^-) &\le -b \\ &&x^+ &\ge 0 \\ &&x^- &\ge 0 \end{align} Now this is standard form because all constraints are $$\le$$ and all variables are nonnegative. To recover $$x$$ after you solve, compute $$x=x^+ - x^-$$.

• So the constraints need to be $-Ax \le -b$ and x...? – Daniel Mårtensson Nov 21 '19 at 18:42
• Can you rewrite the whole objective function and its constraints? – Daniel Mårtensson Nov 21 '19 at 18:43
• Take $c=0$ for the objective. – Rob Pratt Nov 21 '19 at 18:51
• But that won't help me right? – Daniel Mårtensson Nov 21 '19 at 18:52
• @littleO wrote it out in a comment, except you need to change $b$ to $-b$ in the second constraint. – Rob Pratt Nov 21 '19 at 18:53

Here is a pratical answer. I'm using GNU Octave's linear programming tool: https://octave.org/doc/v4.4.1/Linear-Programming.html

>> A = [1 2; 1 -4]
A =

1   2
1  -4

>> b =  [2; 5]
b =

2
5

>> c = A'*b
c =

7
-16

>> x = glpk(c, A, b, [0;0], [], "UU", "CC", -1) % -1 is for maximize
x =

2
0

>>


The objective function is (and also need to be $$c^T = A^Tb$$)

$$max: A^T b x$$

And the constraints are

$$x \ge 0\\ Ax \le b$$

If I ignore the constraints and only do linear solving $$x = (A^TA)^{-1}A^Tb$$ Then the solution $$x$$ would be.

>> x = linsolve(A, b)
x =

3.00000
-0.50000

>>


I have created a C-function named linprog in EmbeddedLapack here. Very easy to use for embedded system if you need optimization there.

• @Rahul math is quite fuzzy and so are the questions as well. But read the question again. I'm talking about constraints. – Daniel Mårtensson Nov 22 '19 at 12:29
• @Rahul The reason why everyone else interpret this question differently is because they are reading the title. The main head question says that there is constraints included. :) Also to include, math becomes very fuzzy. I like to make it practical as possible and my "proofs" is to use software to compute :) – Daniel Mårtensson Nov 22 '19 at 15:36
• If everyone is misunderstanding your question, and you refuse to clarify your question, then all the best of luck to you my friend. – Rahul Nov 22 '19 at 17:12
• @Rahul Not sure if all misunderstanding my question. But all I say is to read the question, and not focus on the title only. – Daniel Mårtensson Nov 23 '19 at 1:44