数学实验 9：整数规划
玛丽莲梦兔
706次浏览
2021年01月30日 01:32
最佳经验
本文由作者推荐
环境保护作文-read的过去式
实验
9
：整数规划
习题
9
：
（原油采购与加工）某公司用两种原油（
A
和
B
）混合加 工成两种汽油（甲
和乙）
，
甲、
乙两种汽油含原油
A
的最低 比例分别为
50%
和
60%
，
每吨售价分别为
4800元和
5600
元。该公司现有原油
A
和
B
的库存量分 别为
500t
和
1000t
，还
可以从市场上买到不超过
1 500T
的原油
A
。
原油
A
的市场价为：
购买量不 超过
500t
时单价为
10000
元
/t
；
购买量 超过
500t
但是不超过
1000t
时，
超过
500t的部分
8000
元
/t
；购买量超过
1000t
时，超 过
1000t
的部分
6000
元
/t
。该公司应该如
何安排原油的采购和加工？用连续规划和证书规划分别求解这个问题。
1
．
模型建立
研究该公司原油的采购和加工过程，需要对两个过程中的各个参数设置变量：
a1,a2
A
原油分别用来制造甲、乙两种产品的质量
(t)
b1,b2
B
原油分别用来制造甲、乙两种产品的质量
(t)
y1,y2,y3
购买的
A
原油质量：< br>y1
为
<500t
部分，
y2
为
>500t
且
<1000t
部分
,y3
为
>1000t
部分
(t)
cost
购买原油
A
所需要的总花销
(
元
)
问如何规划投 资和生产，实际上就是问如何将利润最大化，根据题目中给出的约束条件
建立优化模型的基本形式：
max
s
..
t
4800(
a
1
b
1)
5600(
a
2
b
2 )
Cost
a
1/(
a
1
b
1)
50%
a
2
/(
a
2
b
2)
60%
a
1
a
2
500
y
1
y
2
y
3
b
1
b
2
1000
Cost
10000*
y
1
8000*
y
2
6000*
y
3
(
y
1
500)*y
2
0
(
y
2
500)*
y
3
0
y
1,
y
2,
y
3< br>
500
其中，约束条件的
1
、
2
行为对 两种产品含原油
A
比例的最低限定条件；
3
、
4
行的意义< br>是用来制造产品的原料不能大于库存和购买来的原料总量；
Cost
为总花销；
6
、
7
、
8
行实现
了
y1
、
y2
、
y3
的意义。
2
．
程序设计：
应用
Lingo
软件实现以上的程序：
max
=(a1+b1)*4800+(a2+b2)*5600-cost;
0.5*a1-0.5*b1>0;
0.4*a2-0.6*b2>0;
a1+a2-(y1+y2+y3)<500;
b1+b2<1000;
cost=10000*y1+8000*y2+6000*y3;
(y1-500)*y2=0;
!
注意此处需要写成乘法的形势
(y2-500)*y3=0;
y1<500;
y2<500;
y3<500;
@gin
(y1);
！整数规划约束，连续规划时不需要
@gin
(y2 );
@gin
(y3);
@gin
(a1);
@gin
(a 2);
@gin
(b1);
@gin
(b2);
@gin
( cost);
end
3
．
运行结果：
1
）连续规划：
Global optimal solution found at iteration: 178
Objective value: 5000000.
Variable Value Reduced Cost
A1 0.000000 900.0000
B1 0.000000 0.000000
A2 1500.000 0.000000
B2 1000.000 0.000000
COST 9000000. 0.000000
Y1 500.0000 0.000000
Y2 500.0000 0.000000
Y3 0.1490116E-04 0.000000
Row Slack or Surplus Dual Price
1 5000000. 1.000000
2 0.000000 -2600.000
3 0.000000 -3500.000
4 0.000000 7000.000
5 0.000000 3500.000
6 0.000000 -1.000000
7 0.000000 -6.000000
8 0.000000 -0.6710886E+08
9 0.000000 0.000000
10 0.1490116E-04 0.000000
11 500.0000 0.000000
2
）整数规划：
Global optimal solution found at iteration: 682
Objective value: 5000000.
Variable Value Reduced Cost
A1 0.000000 800.0000
B1 0.000000 800.0000
A2 1500.000 0.000000
B2 1000.000 0.000000
COST 9000000. 0.3000000
Y1 500.0000 0.000000
Y2 500.0000 0.000000
Y3 0.000000 -1400.000
Row Slack or Surplus Dual Price
1 5000000. 1.000000
2 0.000000 0.000000
3 0.000000 0.000000
4 0.000000 5600.000
5 0.000000 5600.000
6 0.000000 -0.7000000
7 0.000000 -2.800000
8 0.000000 0.000000
9 0.000000 0.000000
10 0.000000 0.000000
11 500.0000 0.000000
两种 方法最终得到的都是同样的最优解，即：购买
1000tA
原油，将全部的原料按
A: B=3:2
的比例混合制造乙产品，最终可以获得最大利润（全局最优解）五百万元。
由影子价格
Dual Price
的数值可以看出约束条件
a1+a2-(y1+y2+y3)<500;
b1+b2<1000;
对结果的影响很大
,
即原料供应量增长
1
个 单位，理论上可以使得利润增加
5600
元，实际上，如果把
L5
约束改为< br>b1+b2<1001
，目标函数的最大值增加为
5004800
，并不完全< br>符合影子价格，但是其仍然可以很好的反应目标函数对于各个约束条件的敏感性
;
；Slack or
Surplus
给出了松弛（或剩余）变量的值，当该值为
0
时，表示该约束其作用，可以看到本题的
约束条件基本上都是有作用的。
比较两种规划方式的区别，
可以看到整数规划得到全局最优解所需的迭代次数明显的多
于连续规划，这是由整数规划的复杂性决定的。
习题
11
：
钢管下料问题：
某零售商从钢管厂 进货，
将钢管按照顾客的要求切割后出售，
从钢管厂进货时得到的原料钢管长度是
18 50mm.
现有一客户要
15
根
290mm
、
28
根
315mm
、
21
根
350mm
和
30
根
455mm
的钢管。为了简化生产过程，规定所使用
的切割模式种类不能超过
4
种，
使用频率最高的一种切割模式按照一个原料钢管
价值的
1/10增加费用，
使用频率次之的切割模式按照一个原料钢管价值的
2/10
增加费用， 以此类推，且每种切割模式下最多生产
5
根产品。此外，为了减少余
料浪费，每种切割 模式下的余料浪费不能超过
100mm
，为了使得总费用最小，应
该如何下料。
1.
模型建立
钢管下料问题，
本题由于 可能用到的切割模式很多，
若采用枚举法工作量很大，
因此按
照书上
9.1. 2
的普遍性方法建模
设采用了四种模式切割钢管，第
j
种模式可以制造第
i
种钢管
(
按题目顺序
)
的数量为
rij
，
xi
表示采用第
i
种模式切割的原料钢管数。
以总费用最小为目标，
由于没有给出每中方案的具体花费，
所以将使用原料 钢管总根数
等价于花费，并且需要考虑切割模式的花费：
min x1+x2+x3+x4+0.1*y1+0.2*y2+0.3*y3+0.4*y4
（
1
）
不妨设
,x1>=x2>=x3>=x4,yi< br>为第
i
种方案是否被采用的零一变量，满足：
1,
x
i
0
y
i
,
i
1,
2,3,
4
0,
x
i
0
（
2
）
制造的各种钢管应该至少满足客户的需求：
x1*r11+x2*r12+x3*r13+x4*r14>15;
x1*r21+x2*r22+x3*r23+x4*r24>28;
x1*r31+x2*r32+x3*r33+x4*r34>21;
x1*r41+x2*r42+x3*r43+x4*r44>30;
i=1,2,3,4
（
4
）
（
5
）
（
3
）
每一种切割模式必须可行、合理，按题目要求，钢管成品必 然不能超过１８５０ｍｍ，
且余量不
能大于１００ｍｍ，于是有：
1750<290*r1i+315*r2i+350*r3i+455*r4i<1850;
r1i+r2i+r3i+r4i<5;
i=1,2,3,4
本题还规定了所使用的每种切割模式下最多生产
5
根产品，有：
最后，需要对之前用到的所有参数进行非负整数约束。
综合
1
到
5
式便得到了本题完整的规划模型。
2.
程序设计
min
=x1+0.1+x2+0.2*y2+x3+0.3*y3+x4+0.4*y4;
@bin
(y2);
@bin
(y3);
@bin
(y4) ;
m=999999;
x2
x3
!
设置
0-1
变量
(x1
必然
>0,
不需要
)
！给出一个充分大的数
m
!
实现约束条件（
2
）