linprog求解小麦运输线性规划结果非最优，求问题排查

问题背景 #

从城市1调出10吨小麦运往城市2、3、4、5，每条运输边标注每吨运输成本，各城市三角框内为对应需求量，目标是找到最低成本的运输策略。

建模思路 #

定义变量x_{i,j}为通过边(i,j)运输的小麦吨数，目标函数为：

f = 50*x_{1,2} + 20*x_{1,4} + 40*x_{2,3} + 30*x_{2,5} + 40*x_{4,3} + 10*x_{4,5} + 50*x_{5,3}

约束规则：每个顶点的流入量 - 流出量 = 对应需求量/供应量，同时所有x_{i,j} ≥ 0。

原代码问题分析 #

原MATLAB代码的核心错误是城市4的流量平衡约束行写错，导致模型约束不符合实际逻辑：

变量顺序对应 #

目标函数f的向量顺序为：x_{1,2}, x_{1,4}, x_{2,3}, x_{2,5}, x_{4,3}, x_{4,5}, x_{5,3}

错误约束点 #

城市4是中转点（无需求无供应），正确的流量平衡约束应为：x_{1,4} - x_{4,3} - x_{4,5} = 0，但原代码中第三行Aeq写成了[1 0 0 0 -1 -1 0]，错误地将x_{1,2}的系数设为1，而非x_{1,4}的系数1。

修正后的代码 #

% 修正城市4的流量平衡约束行
Aeq = [1 1 0 0 0 0 0; 
       1 0 -1 -1 0 0 0; 
       0 1 0 0 -1 -1 0;  % 修正：x14的系数为1，x12系数为0
       0 0 1 0 1 0 1;
       0 0 0 1 0 1 -1;];

beq = [10; 1; 0; 6; 3;];

f = [50; 20; 40; 30; 40; 10; 50;];

% 求解线性规划，目标为最小化成本
[x,fval] = linprog(f,[],[],Aeq,beq,zeros(7,1));

disp('最优运输量：');
disp(x);
disp('最低成本：');
disp(fval);

验证结果 #

修正后运行得到的最优运输策略为：
x_{1,2}=1, x_{1,4}=9, x_{2,3}=0, x_{2,5}=0, x_{4,3}=6, x_{4,5}=3, x_{5,3}=0
计算总成本：50*1 + 20*9 + 40*6 +10*3 = 50 + 180 + 240 +30 = 500，与理论最优值一致。

内容的提问来源于stack exchange，提问作者Dimitris Papadimitriou