0
$\begingroup$

Let's consider a generic linear programming problem. Is it possible that the decision variables of the objective function assume (at the optimal solution) irrational values?

Also, is it possible that some entries of the $A$ matrix are irrational?

$\endgroup$
4
  • $\begingroup$ When you are working with numerical algorithms the goal is to attain your goals within a prescribed precision/accuracy. So the rationals suffice. $\endgroup$
    – Cesareo
    Jul 13 '18 at 8:36
  • $\begingroup$ How do i assure that the objective function will have only rational variables in its solutions ? $\endgroup$
    – Qwerto
    Jul 13 '18 at 8:56
  • $\begingroup$ This is a totally different question. If you only have rational inputs, you will have rational outputs (as rational are a field and the linear programming only uses additions multiplications and their reciprocal). If you have irrational inputs, well maybe it balances, maybe not. However, what good will it do to know that the result is rational? 1/3 is rational but is not exactly modeled in a computer representation... $\endgroup$ Jul 13 '18 at 9:07
  • $\begingroup$ My prof told us that a difference beetween Linear Programming and Integer linear Programming is that in Linear Programming variables has fractional values while in Integer linear Programming certain variables can have only integer values... $\endgroup$
    – Qwerto
    Jul 13 '18 at 9:20
7
$\begingroup$

If the problem is described with rational data, there is always a rational optimal solution. I don't have any reference immediately, but it is a standard result. Search on rational data linear program, polynomial complexity etc, and you will find a lot of material.

Edit: I see my answer was a bit unclear. If the solution to the rational LP is unique, it is rational. If it is non-unique, you can always generate an irrational solution by taking a linear combination of two rational solutions $\alpha x_1 + (1-\alpha)x_2$ where $\alpha$ is an irrational number between $0$ and $1$.

$\endgroup$
2
  • 1
    $\begingroup$ The standard result follows trivially from revised simplex with Cramer's rule. If multiple optimal solutions exist, there is always an irrational one. $\endgroup$
    – LinAlg
    Jul 13 '18 at 11:40
  • $\begingroup$ Yes, that is a simple proof $\endgroup$ Jul 13 '18 at 12:02
3
$\begingroup$

Yes.

$$\min x$$ subject to $$\sqrt{2}x=1$$ is a valid linear programming instance.

$\endgroup$

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.