数学建模之规划2——非线性规划（01规划、整数规划、动态规划）
术语解释整数规划：规划中的变量（全部或部分）限制为整数，称为整数规划。（很多的单位是不能拆分成小数的）0-1规划：决策变量仅取值0或1的异类特殊的整数规划。（决策变量要么取0，要么取1）（可以解决快递员问题、协作效率最优化问题、解决流程化问题效果很多好）非线性规划：目标函数或约束条件中至少有一个是非线性函数的最优化问题。多目标规划：研究多于一个目标函数在给定区域上的最优化。动态规划：是...
术语解释
- 整数规划：规划中的变量（全部或部分）限制为整数，称为整数规划。（很多的单位是不能拆分成小数的）
- 0-1规划：决策变量仅取值0或1的异类特殊的整数规划。（决策变量要么取0，要么取1）（可以解决快递员问题、协作效率最优化问题、解决流程化问题效果很多好）
- 非线性规划：目标函数或约束条件中至少有一个是非线性函数的最优化问题。
- 多目标规划：研究多于一个目标函数在给定区域上的最优化。
- 动态规划：是运筹学的一个分支，是求解决策过程最优化的数学方法。
整数规划及0-1规划模型
概述
- 首先0-1其实也是整数规划。
- 整数规划指的是决策变量为非负整数值的一类线性规划。
- 在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法。
- 在整数规划问题中，0-1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0-1型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。
例题1：原油采购与加工
目标：你现在要使收益最大，如何安排原油的采购和加工。
- 市场上可买到不超过1500t的原油A：
- 购买量不超过500t时的单价为10000元/t；
- 购买量超过500t但不超过1000t时，超过500t的部分8000元/t；
- 购买量超过1000t时，超过1000t的部分6000元/t.
问题分析：
- 利润：销售汽油的收入-购买原油A的支出。
- 难点：原油A的购价与购买量关系复杂。
- 决策变量：支出 = 原油A的购买量
- M a x = 4.8 ( x 11 + x 21 ) + 5.6 ( x 12 + x 22 ) − c ( x ) Max \space \space = 4.8(x_{11}+x_{21})+5.6(x_{12}+x_{22})-c(x) Max =4.8(x11+x21)+5.6(x12+x22)−c(x)
- c(x)~购买原油A的支出
- c ( x ) = { 10 x ( 0 ≤ x ≤ 500 ) 8 x + 1000 ( 500 ≤ x ≤ 1000 ) 6 x + 3000 ( 1000 ≤ x ≤ 1500 ) c(x) = \begin{cases} 10x&(0\leq x\leq 500)\\8x+1000&(500\leq x\leq 1000)\\ 6x+3000&(1000\leq x \leq 1500)\end{cases} c(x)=⎩⎪⎨⎪⎧10x8x+10006x+3000(0≤x≤500)(500≤x≤1000)(1000≤x≤1500)
- 原油供应
- x 11 + x 12 ≤ 500 + x x_{11}+x_{12}\leq 500+x x11+x12≤500+x 库存500t
- x 21 + x 22 ≤ 1000 x_{21}+x_{22}\leq 1000 x21+x22≤1000 库存1000t
- x ≤ 1500 x\leq 1500 x≤1500不能卖超过1500
- x 11 x 11 + x 21 ≥ 0.5 \frac{x_{11}}{x_{11}+x_{21}}\geq 0.5 x11+x21x11≥0.5，A要大于50%。
- x 12 x 12 + x 22 ≥ 0.6 \frac{x_{12}}{x_{12}+x_{22}}\geq 0.6 x12+x22x12≥0.6，B要大于60%。
- 目标函数c(x)不是线性函数，是非线性规划。
- 对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解。
模型求解
- x 1 , x 2 , x 3 x_1,x_2,x_3 x1,x2,x3以价格10，8，6（千元/t）采购A的吨数。这对于任何一种情况都成立。
- 于是有 x = x 1 + x 2 + x 3 , c ( x ) = 10 x 1 + 8 x 2 + 6 x 3 x = x_1+x_2+x_3,\space c(x) = 10x_1+8x_2+6x_3 x=x1+x2+x3, c(x)=10x1+8x2+6x3
- M a x = 4.8 ( x 11 + x 21 ) + 5.6 ( x 12 + x 22 ) − 10 x 1 + 8 x 2 + 6 x 3 Max \space \space = 4.8(x_{11}+x_{21})+5.6(x_{12}+x_{22})-10x_1+8x_2+6x_3 Max =4.8(x11+x21)+5.6(x12+x22)−10x1+8x2+6x3
- 然而只有当 x 1 = 500 x_1 = 500 x1=500的时候， x 2 x_2 x2才能有值，同理当 x 1 + x 2 ≥ 1000 x 2 = 500 x_1+x_2\geq 1000 x_2=500 x1+x2≥1000x2=500时， x 3 x_3 x3才能有值
- 所以约束等价于 ( x 1 − 500 ) ∗ x 2 = 0 (x_1-500)*x_2 = 0 (x1−500)∗x2=0【这个太牛逼了】
- 同理 ( x 2 − 500 ) x 3 = 0 (x_2-500)x_3 = 0 (x2−500)x3=0
- 0 ≤ x 1 , x 2 , x 3 ≤ 500 0\leq x_1,x_2, x_3\leq 500 0≤x1,x2,x3≤500
求解代码
Model:
Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*x2 - 6*x3;
x11+x12 < x + 500;
x21+x22 < 1000;
x11 - x21 > 0;
2*x12 - 3*x22 > 0;
x=x1+x2+x3;
(x1 - 500) * x2=0;
(x2 - 500) * x3=0;
x1 < 500;
x2 < 500;
x3 < 500;
end
最终结果
Local optimal solution found.
Objective value: 4800.000
Total solver iterations: 14
Variable Value Reduced Cost
X11 500.0000 0.000000
X21 500.0000 0.000000
X12 0.000000 0.2666667
X22 0.000000 0.000000
X1 0.000000 0.4000000
X2 0.000000 0.000000
X3 0.000000 0.000000
X 0.000000 0.000000
这里分段函数的处理非常经典，需要反复仔细看。
分派问题（0-1规划）
- 若干项任务分给一些候选人来完成，每人的专长不同,完成每项任务取得的效益或需要的资源不同，如何分派任务使获得的总效益最大，或付出的总资源最少?
- 若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出抉择，使得收益最大或成本最小?
- 指派(Assignment)问题：有若干项任务, 每项任务必有且只能有一人承担，每人只能承担一项，不同人员承担不同任务的效益(或成本)不同，怎样分派各项任务使总效益最大(或总成本最小)?一般情况分为三种
- 人员数量与任务数量相等
- 人员数量大于任务数量(本例)
- 人员数量小于任务数量 ?
0-1规划数学模型
M
a
x
(
M
i
n
)
z
=
c
1
x
1
+
x
2
x
2
+
.
.
.
.
.
+
c
n
x
n
Max(Min)z = c_1x_1+x_2x_2+.....+c_nx_n
Max(Min)z=c1x1+x2x2+.....+cnxn
{
a
11
x
1
+
a
12
x
2
+
.
.
.
a
1
n
x
n
≤
(
≥
,
=
)
b
1
a
21
x
1
+
a
22
x
2
+
.
.
.
a
2
n
x
n
≤
(
≥
,
=
)
b
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
m
1
x
1
+
a
m
2
x
2
+
.
.
.
a
m
n
x
n
≤
(
≥
,
=
)
b
2
x
1
,
x
2
,
.
.
.
.
.
.
,
x
n
=
0
∣
1
\begin{cases} a_{11}x_1+a_{12}x_2+...a_{1n}x_n\leq (\geq ,=)b_1 \\a_{21}x_1+a_{22}x_2+...a_{2n}x_n\leq (\geq ,=)b_2 \\.............. \\a_{m1}x_1+a_{m2}x_2+...a_{mn}x_n\leq (\geq ,=)b_2 \\x_1,x_2,......,x_n = 0|1\end{cases}
⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧a11x1+a12x2+...a1nxn≤(≥,=)b1a21x1+a22x2+...a2nxn≤(≥,=)b2..............am1x1+am2x2+...amnxn≤(≥,=)b2x1,x2,......,xn=0∣1
案例：混合泳接力队的选拔
- 问题：如何选拔队员组成4*100混合泳接力队？
- 讨论:丁的蛙泳成绩退步到1‘15’‘2；戊的自由泳成绩进步到57’‘5 , 组成接力队的方案是否应该调整？
- 若选择队员i参加泳姿j的比赛，记 x i j = 1 x_{ij} = 1 xij=1，否则记 x i j = 0 x_{ij} = 0 xij=0。
- 这里面的约束相当复杂，队员只能游一种泳姿，并且每种泳姿也只能由一名队员游。
- 目标函数： m i n Z = ∑ j = 1 4 ∑ i = 1 5 c i j x i j min\space Z = \sum^4_{j=1}\sum^5_{i=1}c_{ij}x_{ij} min Z=j=1∑4i=1∑5cijxij
- 约束条件：
∑
j
=
1
4
x
i
j
≤
1
,
i
=
1
,
.
.
.
,
5
（
1
）
\sum^4_{j=1}x_{ij}\leq 1,i = 1,...,5 \space \space \space \space \space \space \space \space \space \space \space \space \space （1）
j=1∑4xij≤1,i=1,...,5 （1）
∑ i = 1 5 x i j = 1 , j = 1 , . . . , 4 （ 2 ） \sum^5_{i=1}x_{ij} = 1,j = 1,...,4\space \space \space \space \space \space \space \space \space \space \space \space \space （2） i=1∑5xij=1,j=1,...,4 （2） - 一式：每人最多入选泳姿。
- 二式：每种泳姿有且只有一个人。
模型求解代码Lingo
MODEL:
sets:
person/1..5/;
position/1..4/;
link(person,position): c, x;
endsets
data:
c= 66.8, 75.6, 87, 58.6,
57.2, 66, 66.4, 53,
78, 67.8, 84.6, 59.4,
70, 74.2, 69.6, 57.2,
67.4, 71, 83.8, 62.4;
enddata
min=@sum(link: c*x);
@for(person(i):
@sum(position(j):x(i,j))<=1;);
@for(position(i):
@sum(person(j):x(j,i))=1;);
@for(link: @bin(x));
END
案例2 选课策略（0-1多目标复杂规划）
- 要求至少选两门数学课、三门运筹学课和两门计算机课
- 为了选修课程门数最少，应学习哪些课程？
- 选修课程最少，且学分尽量多，应学习哪些课程？
决策变量
- x i = 1 x_i = 1 xi=1~选课好i的课程，0为不选，1为选择。
目标函数
- 选修课程总数最少: m i n Z = ∑ i = 1 9 x i min\space Z = \sum^9_{i=1}x_i min Z=i=1∑9xi
约束条件1：至少选两门数学课、三门运筹学课和两门计算机课
-
最少2门数学课： x 1 + x 2 + x 3 + x 4 + x 5 ≥ 2 x_1+x_2+x_3+x_4+x_5\geq 2 x1+x2+x3+x4+x5≥2
-
3门运筹学课： x 3 + x 5 + x 6 + x 8 + x 9 ≥ 3 x_3+x_5+x_6+x_8+x_9\geq 3 x3+x5+x6+x8+x9≥3
-
2门计算机课： x 4 + x 6 + x 7 + x 9 ≥ 2 x_4+x_6+x_7+x_9\geq 2 x4+x6+x7+x9≥2
-
要有最优化方法、那么必须要学微积分和线性代数， x 3 ≤ x 1 , x 3 ≤ x 2    ⟺    2 x 3 − x 1 − x 2 ≤ 0 x_3\leq x_1, x_3\leq x_2 \iff2x_3-x_1-x_2\leq 0 x3≤x1,x3≤x2⟺2x3−x1−x2≤0
-
要选数据结构，必须选计算机编程， x 4 ≤ x 7    ⟺    x 4 − x 7 ≤ 0 x_4\leq x_7\iff x_4-x_7\leq 0 x4≤x7⟺x4−x7≤0
-
要选应用统计，必须学微积分和线性代数， x 5 ≤ x 1 , x 5 ≤ x 2    ⟺    2 x 5 − x 1 − x 2 ≤ 0 x_5\leq x_1, x_5\leq x_2 \iff2x_5-x_1-x_2\leq 0 x5≤x1,x5≤x2⟺2x5−x1−x2≤0
-
要选预测理论，必选引用统计， x 7 − x 8 ≤ 0 x_7-x_8\leq 0 x7−x8≤0
-
要选数学实验，必选微积分、线性代数 x 9 ≤ x 1 , x 9 ≤ x 2    ⟺    2 x 9 − x 1 − x 2 ≤ 0 x_9\leq x_1, x_9\leq x_2 \iff2x_9-x_1-x_2\leq 0 x9≤x1,x9≤x2⟺2x9−x1−x2≤0
-
基本的方法论就是把约束条件转化为不等式
约束条件2：课程最少、学分尽量多
m i n Z = ∑ i = 1 9 x i min\space \space Z = \sum^9_{i = 1}x_i min Z=i=1∑9xi m a x W = 5 x 1 + 4 x 2 + 4 x 3 + 3 x 4 + 4 x 5 + 3 x 6 + 2 x 7 + 2 x 8 + 3 x 9 max\space \space W = 5x_1+4x_2+4x_3+3x_4+4x_5+3x_6+2x_7+2x_8+3x_9 max W=5x1+4x2+4x3+3x4+4x5+3x6+2x7+2x8+3x9
- 目标加权组合
- ※※双目标规划方法可转化为 m i n { Z , − W } min\{Z,-W\} min{Z,−W}，这样可以转化成单目标优化
- 把一个目标作为约束，解另一个目标的规划
- 先以课程最少为目标，不管学分多少，最优解已经可以通过上面的不等式算出，6门课程，总学分21。
- 以学分最多，不管课程最多 → \rightarrow →肯定是选完所有的课程。
- 先求出一个作为约束条件，课程最小一定是6，我们把它作为约束条件，再来看怎么选学分最高。
总结
- 用0-1变量表示策略选择是常用的方法
- “要选甲 (x1)必选乙 (x2)” 可用 x 1 ≤ x 2 x1\leq x2 x1≤x2描述.
- “要选甲 (x1)必不选乙 (x2)” 怎样描述?
- “甲乙二人至多选一人” 怎样描述?
- “甲乙二人至少选一人” 怎样描述?
- 双(多)目标规划的处理方法
- 加权组合成一个新目标, 化为单目标规划.
- 一个目标作为约束, 解另一个目标的规划.
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
25
0- 0
已为社区贡献2条内容
所有评论(0)