1
$\begingroup$

Given this problem for instance:

$$\begin{array}{ll} \text{maximize} & 0 x_1 + 0 x_2 + 0 x_3\\ \text{subject to} & x_1 + 3x_2 + 2x_3 = 3\\ & 2x_1 + 7x_2 + x_3 = 4\\ & 3x_1 + x_2 + 2x_3 = 5\\ & x_1, x_2, x_3 \geq 0\end{array}$$

I know how to use Simplex in general using tableau method to solve standard linear programming problems. How would I set up my initial tableau here, if my objective function is zero?

$\endgroup$
  • 3
    $\begingroup$ If you are saying the objective function is identically zero, then the only issue is whether the constraints are feasible or not. Please have a look at the introduction to posting mathematical notation and make an effort to express yourself more clearly. Equality constraints(?) are easily solved by elimination rather than by the simplex method. $\endgroup$ – hardmath Apr 27 '18 at 23:10
  • $\begingroup$ Assuming the constraints are feasible. I understand this could be solve by standard elimination, but I am working with very large numbers with many rows and columns (and is underdetermined), and I must find a nonnegative solution. Simplex has been suggested by other forums, and they say to maximize objective function with 0x1 +..+0xn. I just dont know how to set up this up $\endgroup$ – AznBoyStride Apr 27 '18 at 23:12
  • $\begingroup$ If you are just asking about how to plug into a numerical algorithm that would ordinarily use an input vector $[f_1, f_2, ..., f_n]$ to maximize $\sum_{i=1}^n f_i x_i$, just use input vector $[0, 0, ..., 0]$. $\endgroup$ – Michael Apr 27 '18 at 23:14
  • 2
    $\begingroup$ If you don't have time to learn the MathJax syntax, you may try the online WYSIWYG equation editor. In any case, there's no excuse for not typesetting math in MathJax on Math.SE. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Apr 27 '18 at 23:22
  • 2
    $\begingroup$ This boils down to finding the reduced row-echelon form of the augmented matrix $$ \left[\begin{array}{ccc|c} 1&3&2&3\\ 2&7&1&4\\ 3&1&2&5 \end{array}\right] $$ which is $$ \left[\begin{array}{ccc|c} 1&0&0&8/7\\ 0&1&0&1/7\\ 0&0&1&5/7 \end{array}\right]. $$ $\endgroup$ – Math1000 Apr 28 '18 at 1:33
1
$\begingroup$

Using CVXPY to solve the linear program:

>>> from cvxpy import *
>>> x1 = Variable()
>>> x2 = Variable()
>>> x3 = Variable()
>>> objective = Maximize(0)
>>> constraints = [  x1 + 3*x2 + 2*x3 == 3, 
                   2*x1 + 7*x2 +   x3 == 4,
                   3*x1 +   x2 + 2*x3 == 5, 
                   x1 >= 0, x2 >= 0, x3 >= 0]
>>> prob = Problem(objective, constraints)
>>> prob.solve()
-0.0
>>> prob.status
'optimal'

A feasible solution is

>>> x1.value
1.142857142857143
>>> x2.value
0.14285714285714277
>>> x3.value
0.7142857142857143

Using SymPy to perform Gaussian elimination on the augmented matrix:

>>> from sympy import *
>>> M = Matrix([[1,3,2,3],
                [2,7,1,4],
                [3,1,2,5]])
>>> M.rref()
(Matrix([
[1, 0, 0, 8/7],
[0, 1, 0, 1/7],
[0, 0, 1, 5/7]]), [0, 1, 2])

which is a nonnegative $3$-vector and, thus, admissible. Note that this solution is unique.

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