Matlab 中用于线性规划的单纯形法问题（linprog 函数）

Question

我正在使用 Matlab 中的 linprog 函数来解决一组大型线性规划问题。我有 2601 个决策变量，51 个不等式约束，71 个等式约束，所有变量的下限均为 0。

objective函数中的系数和约束因问题而异。我正在使用 单工法 （当我尝试 active-set 和 interior-point 时程序永远不会停止运行，只要我已经等待超过几个小时）。

对于某些问题，单纯形法收敛得非常快，对于其中一些问题（也非常快）显示此消息：

Exiting: The constraints are overly stringent; no feasible starting point found.

然而，即使对于那些有那个消息的人，它仍然提供了一个满足约束的解决方案。我可以忽略该消息并使用解决方案，还是该消息很重要但解决方案可能不是最优的？

更新：事实证明，内点法解决了其中一些问题，但没有解决其他问题。所以在下面的代码中，我使用 interior-point method 来处理它，而 simplex method 来处理其余的。

clc; clear;

%distances
t1 = readtable('t.xlsx', 'ReadVariableNames',false);
ti = table2array(t1);
sz = size(ti);
tiv = reshape(ti, [1,sz(1)*sz(2)]);

%crude oil production and attraction
A = readtable('A.xlsx', 'ReadVariableNames',false);
Ai = table2array(A);
P = readtable('P.xlsx', 'ReadVariableNames',false);
Pi = table2array(P);

%others
one1 = readtable('A Matrix.xlsx', 'ReadVariableNames',false);
one = table2array(one1);
two1 = readtable('Aeq Matrix.xlsx', 'ReadVariableNames',false);
two = table2array(two1);
zero = zeros(sz(1), sz(1));
infin = inf(sz(1), sz(1));
zerov = reshape(zero, [1,sz(1)*sz(2)]);
infinv = reshape(infin, [1,sz(1)*sz(2)]);

%OF
f = (tiv).^1;

%linear program 
%x = linprog(f,A,b,Aeq,beq,lb,ub)
options1 = optimoptions('linprog','Algorithm','interior-point');
options2 = optimoptions('linprog','Algorithm','simplex');
x1999 = vec2mat(linprog(f,one,Pi(1,1:end),two,Ai(1,1:end),zerov,infinv,zerov,options2),sz(1));
x2000 = vec2mat(linprog(f,one,Pi(2,1:end),two,Ai(2,1:end),zerov,infinv,zerov,options1),sz(1));
x2001 = vec2mat(linprog(f,one,Pi(3,1:end),two,Ai(3,1:end),zerov,infinv,zerov,options1),sz(1));
x2002 = vec2mat(linprog(f,one,Pi(4,1:end),two,Ai(4,1:end),zerov,infinv,zerov,options1),sz(1));
x2003 = vec2mat(linprog(f,one,Pi(5,1:end),two,Ai(5,1:end),zerov,infinv,zerov,options1),sz(1));
x2004 = vec2mat(linprog(f,one,Pi(6,1:end),two,Ai(6,1:end),zerov,infinv,zerov,options1),sz(1));
x2005 = vec2mat(linprog(f,one,Pi(7,1:end),two,Ai(7,1:end),zerov,infinv,zerov,options1),sz(1));
x2006 = vec2mat(linprog(f,one,Pi(8,1:end),two,Ai(8,1:end),zerov,infinv,zerov,options1),sz(1));
x2007 = vec2mat(linprog(f,one,Pi(9,1:end),two,Ai(9,1:end),zerov,infinv,zerov,options2),sz(1));
x2008 = vec2mat(linprog(f,one,Pi(10,1:end),two,Ai(10,1:end),zerov,infinv,zerov,options2),sz(1));
x2009 = vec2mat(linprog(f,one,Pi(11,1:end),two,Ai(11,1:end),zerov,infinv,zerov,options2),sz(1));
x2010 = vec2mat(linprog(f,one,Pi(12,1:end),two,Ai(12,1:end),zerov,infinv,zerov,options2),sz(1));
x2011 = vec2mat(linprog(f,one,Pi(13,1:end),two,Ai(13,1:end),zerov,infinv,zerov,options2),sz(1));
x2012 = vec2mat(linprog(f,one,Pi(14,1:end),two,Ai(14,1:end),zerov,infinv,zerov,options1),sz(1));
x2013 = vec2mat(linprog(f,one,Pi(15,1:end),two,Ai(15,1:end),zerov,infinv,zerov,options2),sz(1));
x2014 = vec2mat(linprog(f,one,Pi(16,1:end),two,Ai(16,1:end),zerov,infinv,zerov,options2),sz(1));
x2015 = vec2mat(linprog(f,one,Pi(17,1:end),two,Ai(17,1:end),zerov,infinv,zerov,options2),sz(1));
x2016 = vec2mat(linprog(f,one,Pi(18,1:end),two,Ai(18,1:end),zerov,infinv,zerov,options1),sz(1));

Answer 1

如果有人想知道问题出在哪里，我发现对于那些有错误的程序，实际上没有可行的点，错误说的是正确的。我通过运行相同的线性程序找到了 objective 函数系数的零向量，并得到相同的错误（Matlab 手册推荐的方法）。

Matlab 中用于线性规划的单纯形法问题（linprog 函数）

Issues with Simplex method for linear programming in Matlab (linprog funcion)

matlab

linear-programming

simplex-algorithm