如何用GLPK/MathProg线性化多店铺产品销售规划的非线性约束？

核心思路 #

通过重构变量定义+大M法线性化，彻底解决变量相乘的非线性错误，同时实现“未售出时约束不生效”的业务逻辑。

1. 变量定义调整 #

将原来的一维quantities[PRODUCTS]改为二维矩阵quantity{PRODUCTS, SHOPS}，表示产品p售往店铺s的具体数量。这样利润计算直接是线性表达式，无需与二元变量相乘：
总利润 = sum{p in PRODUCTS, s in SHOPS} (PRICES[p,s] - 1) * quantity[p,s]
（注：运输成本与销量成正比系数为1，因此每单位利润=单价-运输成本）

2. 线性化条件MIN/MAX约束 #

引入二元变量sellToShop{PRODUCTS, SHOPS}（1表示产品p售往店铺s，0表示不售往），通过大M法实现条件约束：

• 上限约束：quantity[p,s] ≤ MAXQUANTITY[p] * sellToShop[p,s]
  当sellToShop[p,s]=0时，quantity[p,s]必须为0；当sellToShop[p,s]=1时，quantity[p,s]不超过产品最大销量。
• 下限约束：quantity[p,s] ≥ MINQUANTITY[p] * sellToShop[p,s]
  当sellToShop[p,s]=0时，quantity[p,s]≥0（结合上限约束即等于0）；当sellToShop[p,s]=1时，quantity[p,s]不低于产品最小销量。
• 非负约束：quantity[p,s] ≥ 0（线性规划变量基本要求）

3. 产品盈利约束 #

针对每个产品p，要求其在所有店铺的总利润≥0（无亏损）：
sum{s in SHOPS} (PRICES[p,s] - 1) * quantity[p,s] ≥ 0

完整多店铺代码示例 #

# 集合定义
set PRODUCTS;
set SHOPS;

# 参数定义
param PRICES{PRODUCTS, SHOPS} >= 0;  # 产品p在店铺s的单价
param MINQUANTITY{PRODUCTS} >= 0;    # 产品p的最小销量（若售往某店铺）
param MAXQUANTITY{PRODUCTS} >= MINQUANTITY{PRODUCTS};  # 产品p的最大销量

# 变量定义
var quantity{PRODUCTS, SHOPS} >= 0;  # 产品p售往店铺s的数量
var sellToShop{PRODUCTS, SHOPS} binary;  # 是否售往该店铺

# 目标函数：按需调整，这里为最大化总利润；若需最小化运输成本，改为sum{p,s} quantity[p,s]
maximize TotalProfit:
   sum{p in PRODUCTS, s in SHOPS} (PRICES[p,s] - 1) * quantity[p,s];

# 约束条件
subject to QuantityUpperBound{p in PRODUCTS, s in SHOPS}:
   quantity[p,s] <= MAXQUANTITY[p] * sellToShop[p,s];

subject to QuantityLowerBound{p in PRODUCTS, s in SHOPS}:
   quantity[p,s] >= MINQUANTITY[p] * sellToShop[p,s];

subject to ProductProfitNonNegative{p in PRODUCTS}:
   sum{s in SHOPS} (PRICES[p,s] - 1) * quantity[p,s] >= 0;

# 数据段示例
data;
set PRODUCTS := P1 P2;
set SHOPS := S1 S2;
param PRICES:
   S1  S2 :=
P1 10  12
P2 15  18;
param MINQUANTITY := P1 5 P2 3;
param MAXQUANTITY := P1 20 P2 15;
end;

关键说明 #

• 彻底消除非线性：所有约束和目标函数均为线性，符合GLPK的求解要求
• 大M法合理性：直接使用产品的最大销量作为M值，贴合业务逻辑，无需额外设定过大的虚值
• 目标函数灵活调整：若需求为最小化运输成本，只需将目标函数改为minimize TotalTransportCost: sum{p in PRODUCTS, s in SHOPS} quantity[p,s];，保留盈利约束即可

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