0
$\begingroup$

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$ ?

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – littleO Nov 21 at 18:44
  • $\begingroup$ @littleO Why x+ and x- ? $\endgroup$ – Daniel Mårtensson Nov 21 at 18:45
1
$\begingroup$

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

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

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.

https://github.com/DanielMartensson/EmbeddedLapack

$\endgroup$
  • $\begingroup$ @Rahul math is quite fuzzy and so are the questions as well. But read the question again. I'm talking about constraints. $\endgroup$ – Daniel Mårtensson Nov 22 at 12:29
  • $\begingroup$ @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 :) $\endgroup$ – Daniel Mårtensson Nov 22 at 15:36
  • $\begingroup$ If everyone is misunderstanding your question, and you refuse to clarify your question, then all the best of luck to you my friend. $\endgroup$ – Rahul Nov 22 at 17:12
  • $\begingroup$ @Rahul Not sure if all misunderstanding my question. But all I say is to read the question, and not focus on the title only. $\endgroup$ – Daniel Mårtensson Nov 23 at 1:44

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.