0

Let's suppose I have an inequality like $ax+by+cz<30$ with $1<x<3$, $2<y<3$, $3<z<4.$

For given $(a,b,c)$, how can I find the solutions $(x,y,z)$ that satisfy the inequality.

If I were to extend the unknown variables how would that affect the complexity of the problem?

Teddy38
  • 3,309

1 Answers1

1

This can be solved ( a feasible solution found), or determined infeasible, with any Linear Programming solver.

Here is an example using CVX under MATLAB. I have not specified an objective function, which means that any feasible solution can be returned. If an objective function ids required (by some other software, you can make it zero, or whatever you want). Note that all inequalities have been entered as non-strict if you really need strict inequalities, then use a small numbers, such as 1e-6 as buffer on the non-strict inequality; for example, a*x + b*y + c*z <= 30 - 1e-6

a = 10*rand, b = 10*rand,c = 10*rand % generate some random values of a, b, and c, for illustrative purposes
a =
   1.478174141816063
b =
   0.197646637288170
c =
   9.642917302995594

cvx_begin
variables x y z
1 <= x <= 3
2 <= y <= 3
3 <= z <= 4
a*x + b*y + c*z <= 30
cvx_end

Well, CVX says this is infeasible. Well, of course it is, because using the lower bound values of x = 1, y = 2, and z = 3, ax + by + c*z comes out to 30.802219325379188, which exceeds 30. Hence there is no feasible solution.

Let's try again with different values of a, b, c. We spin the wheel again and this time get a = 9.703729020133121, b = 1.238605071468197, c = 4.674100267744596. With these values, now the problem is feasible and CVX return a feasible solution x = 1.070403285879173, y = 2.414382097385889, z = 3.195428614106667 . Of course, there are infinitely many feasible solutions, and none of the constraints are close to the boundary, so any of x, y, and z can be perturbed somewhat from the provided solution, and still constitute a feasible solution.

Mark L. Stone
  • 4,496