Matlab linprog 对有界模型产生无界结果

Question

clear
A=[-1 0 -1 0; 0 -1 0 -1; 1 1 0 0; 0 0 1 1];
b=[-50 -70 80 45];
f=[0.5; 0.6; 0.4; 0.55];
options = optimoptions('linprog','Algorithm','dual-simplex');
[x,fval,exitflag,output] = linprog(f,A,b,[],[],[],[],options);

上面显示的代码产生了一个无限的结果Problem is unbounded，其中 Lindo 和 Excel Solver 找到了最优的 objective 函数值，即 62.5

Answer 1

当我运行这个:

clear
A=[-1 0 -1 0; 0 -1 0 -1; 1 1 0 0; 0 0 1 1];
b=[-50 -70 80 45];
f=[0.5; 0.6; 0.4; 0.55];
options = optimoptions('linprog','Algorithm','simplex','display','iter');
x0=[0 0 0 0]'
[x,fval,exitflag,output] = linprog(f,A,b,[],[],[],[],x0,options);

我得到：

Phase 1: Compute initial basic feasible point.
      Iter            Infeasibility
       0                      120
       1                       70
       2                       40
       3                       -0

Phase 2: Minimize using simplex.
      Iter            Objective              Dual Infeasibility 
                        f'*x                   A'*y+z-w-f
       0                   63                    0.111803
       1                 62.5                        0.05
Exiting: The problem is unbounded; the constraints are not restrictive enough.

与您提到的解决方案相同。

但没有什么能阻止求解器增加 x

Answer 2

这是正确的行为 考虑到了 matlab 的 linprog 正在做什么。

进行此观察的原因如下：

linprog 假设变量是 free（（-inf，inf）如果没有给出界限）就像你的情况一样

您的解决方案（与 Lindo 一起观察）是您的 solution-vector 被限制为非负数的解决方案。

这可以通过约束或使用界限来表达。文档给出了以下示例：

Example: To specify that all x-components are positive, lb = zeros(size(f))
    # personal opinion: this should be called "nonnegative"

我不是 Matlab 用户，但使用我的工具，我可以验证：

没有 nonnegativity-constraint / or bounds 表示相同的问题是无界的
约束/边界问题的解决方案为62.5

备注： 许多 mathematical-programming 框架/求解器默认假定 solution-vector 是非负的，这与 linprog 不同正在做。前者是底层算法理论的结果。

Matlab linprog 对有界模型产生无界结果

Matlab linprog yields an unbounded result to a bounded model

matlab

linear-programming