Linear programming excercise

Question

I want to solve a following problem: $$x_1+2x_2+3x_3\to \text{min}$$ $$x_1+3x_3\geq3$$ $$-x_1+x_2+3x_3\leq 4$$ $$x_!+2x_2-3x_3\leq -6$$ $$x_1\geq0$$ $$x_2\geq0$$ $$x_3\geq0$$ I tried using simplex method but it lead me to a solution that is not in the feasible region. Any ideas on how to solve this problem?

Answer 1

Unfortunately your problem has no solution. Let's look at your constraints,

\begin{align} x_1 + 3x_3 \ge 3 \\ -x_1 + x_2 + 3x_3 \le 4 \tag{1} \\ x_1 + 2x_2 - 3x_3 \le -6 \tag{2} \end{align}

Adding up (1) and (2) we get

$$ 3x_2 \le -2 \quad\Rightarrow x_2 \le -2/3 $$

Which clearly contradicts the constraint $x_2 \ge 0$

Answer 2

You could try to solve it using the python scipy stack: scipy.optimization.linprog

You will discover that there is no solution to your problem - it is infeasible. This can be seen by adding together your second and third inequality constraints, as pointed out by @caverac

Here is an example python script to show this:

#!/usr/bin/env python

from scipy.optimize import linprog

def main():
    print('\n')
    print('*********************************')
    print('Infeasible Example:')
    print('  http://math.stackexchange.com/questions/2011787/linear-programming-excercise/')
    print('*********************************')
    print('Minimize: [1;2;3] * x')
    print('Subject to:')
    print(    'x1 + 3*x3 >= 3')
    print(    '-x1 + x2 + 3*x3 <= 4')
    print(    'x1 + 2*x2 - 3*x3 <= -6')
    print(    'x1 >= 0')
    print(    'x2 >= 0')
    print(    'x3 >= 0')
    c = [1, 2, 3]  # objective function
    # Inequality constraint matrix. Note that first inequality is negated.
    A = [[-1,0,-3], [-1, 1, 3], [1,2,-3]]
    b = [-3, 4, -6]
    x0_bnd = (0, None)
    x1_bnd = (0, None)
    x2_bnd = (0, None)
    print('Solving...')
    result = linprog(c, A_ub=A, b_ub=b, bounds=(x0_bnd, x1_bnd, x2_bnd),
                  options={"disp": True})
    print('Result:')
    print(result)

if __name__ == "__main__":
    main()

The output is:

Minimize: [1;2;3] * x
Subject to:
x1 + 3*x3 >= 3
-x1 + x2 + 3*x3 <= 4
x1 + 2*x2 - 3*x3 <= -6
x1 >= 0
x2 >= 0
x3 >= 0
Solving...
Optimization failed. Unable to find a feasible starting point.
Result:
     fun: 2.0
 message: 'Optimization failed. Unable to find a feasible starting point.'
     nit: 2
  status: 2
 success: False
       x: nan