换就是将一个二元乘积函数转换成分离的形式。例如，假设有函数： X1*X2, 增加线性约束： y1=(x1+X2)/2 y2=(x1-X2)/2 用y2-y22替换x1*X2。就是： X1*X3=y12-y22 这种替换的证明如下： y12-y22=(x2+2*X1*X2+X22)/4-(x2-2*x1*X2+X32)/4 =4*X1*X2/4=X1*X2 这个例子暗示：只要模型有两个变量的乘积项，你就可以通过增加两个新变量用变量的 平方和来替换变量的乘积项。如果你有n个原始变量，可能必须处理多达(n-1)/2个乘积项。 如果要将它们全部转换，建议你增加(n-1)个新变量来处理他们。事实上，在一定的条件下， 上面的想法可以公式化（利用Cholesky因子分解技术），这时只需要n个新变量。 6.3案例及参考解答 6-1.下面是著名的分离存储问题。一个饲料处理机要混合数量不等的四种原料，而这些 原料是分别存放在7个不同的仓库中。每一个仓库最多只能存放一种原料。原料存放在仓库 中会产生装卸成本。仓库的存储能力也是有限的。所以某种原料可能要被分别存储在不同的 仓库中。类似的问题在莫比尔石油公司用油罐车装卸燃料的过程中出现过。下面的表格给出 了这个问题相关的数据。 每吨原料装卸成本 仓库 原料 3 4 5 6 7 原料数量 A $1 $2 $2 $3$4 $5 $5 75吨 B 3 3 3 50吨 c 4 4 3 2 1 5 5 25吨 D 1 2 3 5 80吨 存储能力（吨） 25 25 40 60 80 100 100
换就是将一个二元乘积函数转换成分离的形式。例如，假设有函数： x1 * x2, 增加线性约束： y1 = (x1 + x2)/2 y2 = (x1 - x2)/2. 用 yl 2 - y2 2 替换 x1 * x2。就是： x1 * x2 = yl 2 - y2 2 这种替换的证明如下： yl 2 - y2 2 = (xl 2+ 2*x1 * x2 + x2 2 )/4 - (xl 2－2*x1 * x2 + x2 2 )/4 = 4 * x1 *x2/4 = x1 * x2 这个例子暗示：只要模型有两个变量的乘积项，你就可以通过增加两个新变量用变量的 平方和来替换变量的乘积项。如果你有 n 个原始变量，可能必须处理多达 n(n-1)/2 个乘积项。 如果要将它们全部转换，建议你增加 n(n-1)个新变量来处理他们。事实上，在一定的条件下， 上面的想法可以公式化(利用 Cholesky 因子分解技术)，这时只需要 n 个新变量。 6.3 案例及参考解答 6-1. 下面是著名的分离存储问题。一个饲料处理机要混合数量不等的四种原料，而这些 原料是分别存放在7个不同的仓库中。每一个仓库最多只能存放一种原料。原料存放在仓库 中会产生装卸成本。仓库的存储能力也是有限的。所以某种原料可能要被分别存储在不同的 仓库中。类似的问题在莫比尔石油公司用油罐车装卸燃料的过程中出现过。下面的表格给出 了这个问题相关的数据。 每吨原料装卸成本 仓库 原料 1 2 3 4 5 6 7 原料数量 A $1 $2 $2 $3 $4 $5 $5 75 吨 B 2 3 3 3 1 5 5 50 吨 C 4 4 3 2 1 5 5 25 吨 D 1 1 2 2 3 5 5 80 吨 存储能力（吨） 25 25 40 60 80 100 100
a)给出求解这类问题的模型。 b)对于这个特殊问题给出成本最小的解答。 c)如果增加只要仓库存有原料就会产生一笔固定成本，上面模型如何修改？ 参考解答： a Model: sets: a/1.7/:n;！n表示仓库的存储能力； b/1.4/:m;1m表示原料的数量； ba(b,a):p,y;p表示仓库存储某原料的价格，x表示仓库存储原料的实际数量，y是0-1 变量： endsets data: n=25 25406080100100: m=75 502580: p= 1223455 333 15 5 4 4321 55 1122355: enddata min=@sum(ba:x*p);!目标函数； efor(b(i):esum(a(j):x(i,j))=m(i));!原料要放进仓库； efor(ba:ebin(y));!0-1变量； @for(ba:x<100*y);!仓库有货时y=1: @for(a(i):@sum(b(j):y(j,i))<1):!仓库最多只能放一种原料： @for(a(i):esum(b(j):x(j,i))<n(i)):!存储能力限制： End b) Variable Value Reduced Cost
a) 给出求解这类问题的模型。 b) 对于这个特殊问题给出成本最小的解答。 c) 如果增加只要仓库存有原料就会产生一笔固定成本，上面模型如何修改？ 参考解答： a) Model: sets: a/1.7/:n;!n表示仓库的存储能力; b/1.4/:m;!m表示原料的数量; ba(b,a):p,x,y;!p表示仓库存储某原料的价格，x表示仓库存储原料的实际数量，y是0-1 变量; endsets data: n=25 25 40 60 80 100 100; m=75 50 25 80; p= 1 2 2 3 4 5 5 2 3 3 3 1 5 5 4 4 3 2 1 5 5 1 1 2 2 3 5 5; enddata min=@sum(ba:x*p);!目标函数; @for(b(i):@sum(a(j):x(i,j))=m(i));!原料要放进仓库; @for(ba:@bin(y));!0-1变量; @for(ba:x<100*y);!仓库有货时y=1; @for(a(i):@sum(b(j):y(j,i))<1);!仓库最多只能放一种原料; @for(a(i):@sum(b(j):x(j,i))<n(i));!存储能力限制; End b) Variable Value Reduced Cost