Maximize Linear Programming using linprog Problem is unbounded?

Question

0 个投票

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 =

     []

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

请先登录再关注

Answer 1

John D'Errico 2022-11-10

编辑：John D'Errico 2022-11-12

在 MATLAB Online 中打开

0 个投票

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