Maximize Linear Programming using linprog Problem is unbounded?

Dear friends,

what is my mistake about the problem?

Your help would be highly appreciated!

clc,clear;
objectiveFunction = -1 * [2 -1 2];
A = [-1 -1 -1; 2 0 -1;0 -2 1];
b = [-6;-2;0];
lb = [0 0 0];
ub = [Inf Inf Inf];
%%Solution 
linprog(objectiveFunction, A,b,[],[],lb,ub)

Problem is unbounded.


ans =

     []

Answer 1

[John D'Errico]

Look carefully at the problem you have posed. Is there some direction we can move infinitely far out, and still obey those constraints?

Your objective function is of the form:

A = [-1 -1 -1; 2 0 -1;0 -2 1];
b = [-6;-2;0];
lb = [0 0 0];

You have linear inequality constraints of the form A*x <= b.

You wish to maximize an objective of the form dot(f,x), where f is the vector

f = [2 1 2];

Does a feasible point exist? We can actually find one by simply changing all of your constraints to equalities. Does a trivially feasible solution exist?

xfeas = (A\b)'

xfeas = 1×3

0.7500 1.7500 3.5000

Happily, it even obeys your bound constraints, since x1,x2,x3 are all positive. So xfeas is indeed a feasible solution to the problem.

format rat
f = [2 -1 2];
dot(f,xfeas)

ans = 
      27/4     

The probem is, there exists a direction we can move which will increase the objective as large as we wish, yet still remains feasible always. That is the meaning of unbounded.

dx = [1 1 2];
syms t
dot(f,xfeas + dx*t)

ans = 

Of course, when t == 0, we get the original point. And for any value of t>0, 5*t+27/4 is always greater then 27/4.

A*(xfeas + dx*t).' - b

ans = 

So as t grows, the constraints are still maintained. And for all positive t, the bound constraints are also maintained.

xfeas + dx*t

ans = 

Linprog is correct. Your problem is unbounded. Could I have spent some time writing out the dual to this problem, and explaining how that would have helped in this analysis? Probably. But that would have required I explain what the dual is and why it would help.

I spent some time writing out a lot of explanations abut linear programming, and unbounded problems, etc., here:

https://www.mathworks.com/matlabcentral/answers/1847898-linprog-failed-to-work-why-did-i-do-something-wrong?s_tid=srchtitle

Answer 2

[Torsten]

For M >= 4, choose

x1 = 0, x2 = M/2 , x3 = M

Then x = [x1,x2,x3] is feasible and the value of the objective is 3/2*M which can be made as big as you like.