【数学建模算法】（5）整数规划应用实例：生产与销售计划问题

2019-08-07 本文已影响2人热爱学习的高老板

之前的几篇番外，我们介绍了运筹学软件Lingo的用法，之后对于规划问题的处理，如无特殊说明，均视为采用Lingo求解。

例1 生产与销售问题
某公司用两种原油（ A 和 B ）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油的最低比例分别为 50％和 60％，每吨售价分别为 4800 元和 5600 元。该公司现有原油 A 和 B 的库存量分别为 500 吨和 1000 吨，还可以从市场上买到不超过 1500吨的原油 A 。原油 A 的市场价为：购买量不超过 500 吨时的单价为 10000 元/吨；购买量超过 500 吨单不超过 1000 吨时，超过 500 吨的部分 8000 元/吨；购买量超过 1000 吨时，超过 1000 吨的部分 6000 元/吨。该公司应如何安排原油的采购和加工。

1.问题分析

安排原油采购、加工的目标是利润最大，题目中给出的是两种汽油的售价和原油 A的采购价，利润为销售汽油的收入与购买原油 A 的支出之差。这里的难点在于原油 A 的采购价与购买量的关系比较复杂，是分段函数关系，能否及如何用线性规划、整数规划模型加以处理是关键所在。

2.模型建立

设原油 $A$ 的购买量为 $x$ （单位：吨）。根据题目所给数据，采购的支出 $c(x)$ 可表示为如下的分段线性函数（以下价格以千元/吨为单位）
$c(x)=\left\{\begin{array}{cc}{10 x,} & {0 \leq x \leq 500} \\ {1000+8 x,} & {500 \leq x \leq 1000} \\ {3000+6 x,} & {1000 \leq x \leq 1500}\end{array}\right.$
设原油 $A$ 用于生产甲，乙两种汽油的数量分别为 $x_{1 1}$ 和 $x_{1 2}$ ，原油 $B$ 用来生产两种汽油的数量分别是 $x_{2 1}$ 和 $x_{2 2}$ ，则总的输入为 $4.8\left(x_{11}+x_{21}\right)+5.6\left(x_{12}+x_{22}\right)$ （千元）。于是本例的目标函数（利润）为：
$\max \quad z=4.8\left(x_{11}+x_{21}\right)+5.6\left(x_{12}+x_{22}\right)-c(x)$
（此处 $c(x)$ 代表一个非线性分段函数）
约束条件包括两种汽油用的原油 $A$ ， $B$ 的库存限制，原油 $A$ 购买量的限制，原油 $A$ 的比例限制。

$x_{11}+x_{12} \leq 500+x$
$x_{21}+x_{22} \leq 1000$
$x \leq 1500$
$\frac{x_{11}}{x_{11}+x_{21}} \geq 0.5$
$\frac{x_{12}}{x_{12}+x_{22}} \geq 0.6$
$x_{11}, x_{12}, x_{21}, x_{22}, x \geq 0$
现在问题在于，目标函数中的c(x)是一个非线性函数

3.模型求解

下面介绍三种解法：
(1)解法一：
一个自然的想法是将原油A采购量的x分为三个量，用 $x_{1}$ ， $x_{2}$ ， $x_{3}$ 分别表示10千元每吨，8千元每吨，6千元每吨采购的原油A的吨数，总支出为

$c(x)=10 x_{1}+8 x_{2}+6 x_{3}$

且：

$x=x_{1}+x_{2}+x_{3}$

此时目标函数变为线性函数：

$\max z=4.8\left(x_{11}+x_{21}\right)+5.6\left(x_{12}+x_{22}\right)-\left(10 x_{1}+8 x_{2}+6 x_{3}\right)$

如何把分段的限制条件加入呢？
注意到，只有当以10千元每吨的价格购买 $x_{1}=500$ 吨时，才能以8千元/吨的价格购买 $x_{2}$ ，这个条件可以表示为：

$\left(x_{1}-500\right) x_{2}=0$

同理，用同样的条件来限制 $x_{2}$ 和 $x_{3}$ ：

$\left(x_{2}-500\right) x_{3}=0$

此外，还有 $x_{1}, x_{2}, x_{3}$ 本身的取值范围：

$0 \leq x_{1}, x_{2}, x_{3} \leq 500$

综合以上所有条件，得到最终的程序：

model:
sets:
var1/1..4/:y; !这里y(1)=x11,y(2)=x21,y(3)=x12,y(4)=x22;
var2/1..3/:x,c;
endsets
max=4.8*(y(1)+y(2))+5.6*(y(3)+y(4))-@sum(var2:c*x);
y(1)+y(3)<@sum(var2:x)+500;
y(2)+y(4)<1000;
0.5*(y(1)-y(2))>0;
0.4*y(3)-0.6*y(4)>0;
(x(1)-500)*x(2)=0;
(x(2)-500)*x(3)=0;
@for(var2:@bnd(0,x,500));
data:
c=10 8 6;
enddata
end

运行得到全局最优解：购买1000吨原油 $A$ ，与库存的500吨原油A与1000吨原油B一起，共产生2500吨汽油乙，利润为5000（千元）。

（2）解法二
引入0-1变量 $z_{1}，z_{2}，z_{3}$

$500 z_{2} \leq x_{1} \leq 500 z_{1}$
$500 z_{3} \leq x_{2} \leq 500 z_{2}$
$x_{3} \leq 500 z_{3}$
$z_{1}, z_{2}, z_{3}=0或1$

model:
sets:
var1/1..4/:y; !这里y(1)=x11,y(2)=x21,y(3)=x12,y(4)=x22;
var2/1..3/:x,z,c;
endsets
max=4.8*(y(1)+y(2))+5.6*(y(3)+y(4))-@sum(var2:c*x);
y(1)+y(3)<@sum(var2:x)+500;
y(2)+y(4)<1000;
0.5*(y(1)-y(2))>0;
0.4*y(3)-0.6*y(4)>0;
@for(var1(i)|i #lt# 3:500*z(i+1)<x(i);x(i)<500*z(i));
x(3)<500*z(3);
@for(var2:@bin(z));
@for(var2:@bnd(0,x,500));
data:
c=10 8 6;
enddata
end

(3)解法三
直接处理分段线性函数 $c(x)$ 。
记分断点
$b_{1}=0, b_{2}=500, \quad b_{3}=1000$
当 $x$ 处于第一个小区间 $\left[b_{1}, b_{2}\right]$ ，记 $x=w_{1} b_{1}+w_{2} b_{2}$ ， $w_{1}+w_{2}=1, \quad w_{1}, w_{2} \geq 0$ 因为 $c(x)$ 在 $\left[b_{1}, b_{2}\right]$ 上是线性的。
$c(x)=w_{1} c\left(b_{1}\right)+w_{2} c\left(b_{2}\right)$

分段函数
同理，当处于第二个小区间时，
，，

当 $x$ 处于第三个小区间 $\left[b_{3}, b_{4}\right]$ 时 $x=w_{3} b_{3}+w_{4} b_{4}, \quad w_{3}+w_{4}=1, \quad w_{3}, w_{4} \geq 0$ ， $c(x)=w_{3} c\left(b_{3}\right)+w_{4} c\left(b_{4}\right)$

为了表示 $x$ 在哪个区间内，引入0-1变量 $z_{k}(k=1,2,3)$ ，当 $x$ 在第 $k$ 个小区间时， $z_{k}=1$ ，否则， $z_{k}=0$ ，这样 $w_{1}, w_{2}, w_{3}, w_{4}, z_{1}, z_{2}, z_{3}$ 应满足：
$w_{1} \leq z_{1}, \quad w_{2} \leq z_{1}+z_{2}, \quad w_{3} \leq z_{2}+z_{3}, \quad w_{4} \leq z_{3}$
$w_{1}+w_{2}+w_{3}+w_{4}=1, \quad w_{k} \geq 0 \quad(k=1,2,3,4)$
$z_{1}+z_{2}+z_{3}=1, z_{1}, z_{2}, z_{3}=0或1$

此时可将 $c(x)$ 和x统一表示。
$x=w_{1} b_{1}+w_{2} b_{2}+w_{3} b_{3}+w_{4} b_{4}=500 w_{2}+1000 w_{3}+1500 w_{4}$
$\begin{aligned} c(x) &=w_{1} c\left(b_{1}\right)+w_{2} c\left(b_{2}\right)+w_{3} c\left(b_{3}\right)+w_{4} c\left(b_{4}\right) \\ &=5000 w_{2}+9000 w_{3}+12000 w_{4} \end{aligned}$
此时又是一个线性规划模型。

endsets
data:
b=0,500,1000,1500;
c=0,5000,9000,12000;
z=,,,0; !增加的虚拟变量z(4)=0;
enddata
max=4.8*(y(1)+y(2))+5.6*(y(3)+y(4))-@sum(var:c*w);
y(1)+y(3)<@sum(var:b*w)+500;
y(2)+y(4)<1000;
0.5*(y(1)-y(2))>0;
0.4*y(3)-0.6*y(4)>0;
w(1)<z(1);
@for(var(i)|i #ne# 1:w(i)<z(i-1)+z(i));
@sum(var:z)=1;
@sum(var:w)=1;
@for(var:@bin(z));
End

【数学建模算法】（5）整数规划应用实例：生产与销售计划问题

1.问题分析

2.模型建立

3.模型求解

猜你喜欢

热点阅读