优化问题的数学模型
一. 管理科学的定义
管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策制定的一门学科.
(1) 定量因素(2) 科学的方法(3) 辅助决策制定 二.用管理科学的方法解决问题的基本步骤.
（1） 提出问题，并根据需要收录有关数据信息。管理科学工作者向管理者咨询、鉴别所
要考虑的问题以确定合理的目标，然后根据要求收集一些关键数据，并对数据作相应的分析。
（2） 建立模型，引入决策变量，确定目标函数（约束条件）。建模过程是一项创造性的
工作，在处理实际问题时，一般没有一个唯一正确的模型，而是有多种不同的方案。建模是一个演进过程，从一个初始模型往往需要不断的完善渐渐演化成一个完整的数学模型。
（3） 从模型中形成一个对问题求解的算法。要在计算机上运行数学程序对模型进行求
解，一般情况下能找到对模型求解的标准软件。例如，对线性规划问题已有Excel 、Cplex 、Lingo 等标准软件求解。有时要自己编写程序。
（4） 测试模型并在必要时修正。在模型求解后，需要对模型进行检验，以保证该模型能
准确反映实际问题，需要检验模型提供的解是否合理，所有主要相关因素是否已考虑，当有些条件变化时，解如何变化等。
（5） 应用模型分析问题以及提出管理建议。对模型求解并分析后，将相应的最优方案提
交给管理者，由管理者做出决策。管理科学工作者并不作管理决策，其研究只是对涉及的问题进行分析并向管理者提出建议。管理者还要考虑管理科学以外的众多因素才能做出决策。
（6） 帮助实施管理决策。建议被管理者采纳以后，一旦做出管理决策一般要求帮助监督
决策方案的实施。
新问题, 新模型, 新算法, 新应用.
三.优化问题的数学模型
1212max(min)(,,
,)
(,,)0..1,2,n j n Z f x x x g x x x s t j m
=≤??
=?
由于,j f g 是非线性函数时，此问题是非线性优化问题, 求解较复杂。我们主要讨论线性优化问题，常见的形式：混合整数规划
（1）
max 0 0
Z CX hY AX GY b X Y =++≤≥≥取整数
其中111,,,,m n m p m n p A G b C h ?????，不失一般性，我们假定,,,,C h A G b 都是整数矩阵。 当0p =时，（1）为纯整数规划，当0n =时，（1）为线性规划。
下图列出若干常见线性优化问题之间的关系，见Figure 1.1
3.1．1 Set packing 与Node packing （Set packing ）模型：
max 1
{0,1}
Z CX
AX x =≤??
∈? 其中A 是元素为0或1的矩阵
（Node packing ）模型：
max 1
{0,1}
Z CX
AX x =≤??
∈? 其中A 是元素为0或1的矩阵，且每行恰有两个1（没有重复行）
显然，Node packing 是Set packing 特例。
对于Set packing 问题，事实上是一个独立集问题，例如
1 0 0 01 1 0 01 0 1 00 1 1 1A ????
?
?=??????
我们按下列方式构造网络：每列对应于一个顶点，j x 对应于点j ，所以有四
个点，按行检查，对任意i 若1il ik a a ==，则在点l 与点h 之间有一条边相连。构成如图网络以后，可以看出约束1AX ≤相当于确定顶点使得被确定的顶点之间没有边相连；而目标系数C 相当于点的权重向量问题变为如何在网络确定若干个（独立的）顶点使得总权重最大的问题。而Node packing 问题中，A 是0－1矩阵（每行只有两个元素是1），事实上是一个网络的边点关联矩阵，最终也可以化为与上问题类似的问题。
Figure 1.2
3.2 背包问题
对于0-1背包问题（Knapsack ）一般模式：
max ..{0,1}
Z CX AX b s t x =≤??
∈? 事实上，它的求解很困难，我们不妨举个非常简单的例子。
1231231max 92860720..{0,1}
i Z x x x x x x b s t x =++++≤??
∈?
1x 的系数比1：9，2x 的系数比1：4，3x 系数比为1：3，从资源分配问题角度应依次考虑123,,x x x ，而事实上，最优解非常依赖于右端项1b 。
当17b <时，最优解为（1，0，0）； 当178b ≤<时，最优解为（0，1，0）； 当1820b ≤<时，最优解为（1，1，0）； 当12021b ≤<时，最优解为（0，0，1）； 没有体现1x 优先，不同于线性规划。
3．3 Matching （赋权图）匹配问题
在网络中，一个匹配是指一些边集使得没有两边相关联。最大赋权匹配问题，寻找一个匹配使得总权最大。最大基数匹配问题，（假定每条边权为1），找出边数最多的匹配。 指派问题－事实上是二部图的匹配问题。（注：二部图是指可以把图中顶点分为两个部分，每一部分之间没有连接）
一般模型 ()
max ..
1 {0,1}
e e
e E
e e i e Z C X s t X i V X δ
∈∈=≤?∈∈∑∑
其中()i δ表示关联顶点i 的边的集合。（3()O m 算法存在） 3．4 Linear Network Flow
,min(max)..0ij ij
i j
ij ij ij jh j
i
h ij Z x w x C s t x x s x =?
≤??-=???≥?
∑∑∑ 最大流问题，运输问题，最短路问题和指派问题均为其特例。网络单纯形法。
Fixed-charge Network flow 是指弧上费用固定，与流量无关。我们要确定走哪些弧（0－1变量）。一般模型为0－1混合整数规划。
,min(max)..0,{0,1}ij ij
i j
ij ij ij ij jh j
i
h ij ij Z y w x C y s t x x s x y =?
≤??-=???≥∈?
∑∑∑ 事实上，线性网络流（最小费用流）是上问题的特例：
在线性网络流中，ij w 是单位费用，将弧(,)i j v v （容量为ij C ）分解为ij C 条容量为1的弧即可。
3．5无容量限制的设备选址问题（uncapacitated facility location ）
一般模型：,min .. 0,{0,1}ij ij i i
i j
i
ij i i j
ij j i
ij i Z c x h y x a y i s t x b x y =+?≤???=???≥∈?
∑∑∑∑这是一种混合0－1规划问题。
3．6 Node Covering
给定图(,)G V E 和一个数k ，是否存在一个包含k 个顶点的子集1V V ?，使得图中每个边至少关联1V 中的一个顶点？（判定问题）k 的最小个数是多少？（优化问题） （若每点都有权，求一个子集1V V ?总权最小，且每个边至少关联1V 中的一个顶点）
Independent Set 独立集问题：给定网络图(,)G V E 和整数k ，是否存在包含k 个点的子集1V 使得1V 中任何两个点都不相邻（关联）？（判定问题）求最大的k 是优化问题。
其它问题：哈密顿圈，货郎担问题，中国邮递员问题，适定性问题
3．7各种问题的变形问题
最大容量路、最大容量树、瓶颈运输问题（指派问题）、约束最小生成树（度约束、hop 约束等）、多种物资流问题、带时间窗的最短路问题，最短路、树问题
实际应用的问题都是这些问题的变种形式，首先要判断所遇问题基本上属于哪类问题。
四. 单位模矩阵（么模矩阵）与整数解（Uni-modular ）
定义：一个整数方阵B ，若||1B =±，则称B 为单位模（么模）矩阵。一个m n A ?矩阵，若它的任何一个非奇异子方阵都是单位模的，则称A 为全单模的。
推论：A 是全单模的，则A 的任何r 阶子式（r m ≤）取值为0，1±。
由于线性规划的基本解*
1
||
B B X B b b B -==?（其中*B 为B 的伴随矩阵）
若b 是整数向量，则B X 也是整数向量。因此有
定理1：若A 是全单位模矩阵，对任何整数向量b 都有有界多面体
1(){|,0}
R A X A X b X ==
≥的所有顶点均为整数点，因此用单纯形法求出的最优解必为整数解。同样，可以证明当约束是不等式约束时，也有以上结论。
2(){|,0}R A X AX b X =≤≥
定 理2：当A 是全单位模矩阵，b 是整数向量时，2()R A 的所有顶点均为整数点。 定 理3：设()ij m n A a ?=，其中0,1ij a =±，如果A 的每一列的非零元素最多有两个，且A 的行可以划分为两个子集1I 和2I ，使得
(1) 若一列中两个非零元素的符号相同，则它们所有的行属于不同的集合1I 和2I
(2) 若一列中的两个非零元素的符号不同，则它们所在的行属于同一个集合则A 是全单位模 推论：
A 是一个有向图的点－弧关联矩阵或A 是一个无向二部图的点边关联矩阵，则A 是全单位模。 例：
Figure 1.3
点边关联矩阵12345
1 0 0 1 0 0 0 1 0 1 A= 0 1 1 1 0 1 1 0 0 1 e e e e e ??
???
???????
不是全单位模，因为2345e e e e 列形成的4阶子
式为－2。
事实上，我们有定理: 无向图的点边关联矩阵是全单位模的充要条件是该图为二部图。
关联矩阵（点弧）
123456
a a a a a a 1 1 0 0 1 0 -1 -1 1 0 0 1 A= 0 0 -1 1 0 0 0 0 0 -1 -1 -1 ?????
???????
Figure 1．4
定理：对于关联矩阵（点弧）n m A ?其秩为n-1（行的个数－1）。 应用举例：（线性规划中列向量是连续1的情形） 若线性规划
min ..0
Z CX AX b s t x =≥??
≥? 其中m n A ?是0－1矩阵，且满足每列中的元素是1的元素连续出现的情形，这类问题可以转化为网络最小费用流问题。现举例说明：
min 0 1 0 1 151 1 0 0 1121 1 1 0 0101 1 1 0 06Z CX
X =????????????
≥????????????
加剩余变量Y 变为（并增加一行000X Y ?+?=） 0 1 0 1 1 -1 0 0 051 1 0 0 1 0 -1 0 0121 1 1 0 0 0 0 -1 0101 1 1 0 0 0 0 0 -160 0 0 0 0 0 0 0 0X Y ??????????=????????????0????????????????
对A 作行变换（每行减去上一行）得
0 1 0 1 1 -1 0 0 051 0 0 -1 0 1 -1 0 00 0 1 0 -1 0 1 -1 00 0 0 0 0 0 0 1 -1-1 -1 -1 0 0 0 0 0 1X Y ??????????=????????????7246????????-??-????-??
此时() 0,1ij ij A a a ==±，每列恰有两个非零元素（一个1，一个－1）问题化为如下最小费用流问题：
发点第1点 发量－收量＝5
第2点 发量－收量＝7
收点第3，4，5点 分别为2，4，6
五. 算法复杂性
a) 多项式算法－问题算法的复杂性随着输入规模的增加而多项式地增加，或者有一个
多项式的上界。例如，问题的规模为n ，算法的复杂性为log n n 或3
n 等，指数算法2n
（复杂性，最坏的情况）。
问题的规模－输入时所需要的符号数目，例如线性规划问题中A ，B ，C 所需要的符号
数目。
b) 优化问题与判定问题
对于一个给定的最优化问题，可以定义一个密切相关的判定问题，即一个能用是或否回答的问题。例如覆盖问题、匹配问题等，线性规划问题转化为不等式是否存在可行解。 c) P 类问题
给定每个问题的实例，我们有多项式时间算法得出答案是是还是不是。 d) NP 问题
如果X 是判定问题的一个答案为“是”的实例，则存在一个对X 的一个多项式时间为界验证，使得能在多项式时间内验证这个证明的真实性；
例：求网络图中的最大团问题，(,)G V E 的图为V 的一个子集（其中任意两点完全连接），最大团问题是找出包含顶点数最多的团（clique ），这是一个优化问题。判定问题为：已知图(,)G V E 和整数k ，G 中有k 个点团吗？
由于还没有找到多项式时间算法求解此问题，所以不知道此问题是否在P 类问题中，
一个方法是找出所有k V C 个包含k 个顶点的子集，但是这是指数级算法，人们没有多项
式算法。但是此问题是NP 类，因为假定给定团的一个答案是“是”实例，我们很容易检验：首先看是否有k 个点，再看任意两点是否连接。 例：整数线性规划（略）
判定问题：已知m n ?整数矩阵A 和m 维整数向量，存在n 维整数向量X ，使AX b =及0X ≥吗？
显然判定问题是NP 的。
定理：P NP ?即P 是NP 的子集。（略） e) 多项式时间归纳法（转换）
两个判定问题12,A A ，如果1A 多项式归结到2A ，则当2A 有多项式算法时，1A 也有多项式时间算法。
f) NP －Complete （NP 完备类）
定义：一个判定问题A NP ∈称为是NP －完备，如果所有其他的NP 问题都能多项式地归纳到A 。
对于NP 完备类的问题A ，有一个令人生畏的性质，若A 有有效算法（多项式算法）则所有NP 问题也有有效算法。
要证明一个问题是NP －完备，必须证明
（1） 该问题是NP 问题（2）所有其它NP 问题可以多项式归纳到该问题。 g) 常见的NP －完备问题
有成千上万个NP －完备问题，如：整数线性规划、团、货郎担问题、适定性问题、点覆盖、独立集、哈密顿圈问题、0－1背包问题。事实上要证明一个问题是NP －完备的转化为要证明：
（1） 该问题是NP 的
（2） 有一个已知的NP －完备问题可以多项式时间转化为该问题。 h) NP －困难问题
有时我们能证明所有NP 问题多项式归结到某问题A ，但不能证明A NP ∈，此时称A 为NP 困难问题。
i) 纯整数规划问题有多项式时间算法，当且仅当0－1整数规划问题有多项式时间算
法。
?0－1规划是特例显然成立；?若0－1规划有多项式算法（充分性）
事实上，纯整数规划可以重新写为一个等价0－1规划，由于纯整数规划最优解分量i x 有界M ，令0
2
l
j
i ij j x x ==∑，[]log l M =，这样纯整数规划化为0－1规划问题。
j)
货郎担问题的整数规划模型
考虑1n +村庄的货郎担问题，分别用0，1，2,…，n,城市间距离为ij C ，对每一弧(,)i j 我们指定变量ij x ，当弧(,)i j 在环游线上时，ij x ＝1；当弧(,)i j 不在环游线上时，ij x ＝1。
,0
00
min s.t. 1 0,
, 1 1,
, 01 1,1n
ij ij
i j i j
n
ij i n
ij j ij i j ij Z c x
x j n x i n
x u u nx n i j n
=≠===
====≤≤-+≤-≤≠≤∑∑∑为整数
（,i j u u 无非负限制实变量）
Greedy 算法（每次挑最好的候选者，直到不能送为止）
最大权森林问题（森林是无圈子图） 最小支撑树问题 拟阵——用greedy 算法都能求出最优解。
k) Sterner 树问题
Sterner 树问题－最小生成树的变种。给定网络(,)G V E C ，，S V ?是一个顶点子集，我们希望找一个包含S 中所有顶点的最小费用树（不必是G 的支撑树）。该问题是NP 困难问题。
l) 成本效益均衡模型
许多优化问题是两个以上目标优化问题，如要求成本最低和效益最高，或回报高而风险低。一般是限制其中一个目标（作为约束条件）求另一个目标最优。类似地，有n 个目标时，限制n-1个目标（作为约束条件），求其中一个最优。 适定性问题（Satisfiability ）：布尔变量x 的真与假，逻辑运算“或”，“与”分别用“+”“?”表示，x 表示x 的否，布尔表达式是用算术运算符号连接起来的变量所构成的代数表示式。例1：3213()x x x x ++是一个布尔表示式。
给定每个变量x 一个值()t x ，与计算代数表达式一样，我们可以计算布尔表达式，例如若给定1()t x =“真”， 2()t x =“真”， 3()t x =“假”。（这样的一组值称为一个真值分配，那
么3213()x x x x ++式等于“真”。给定一个布尔表达式，如何存在一个真值分配，使得表达式取值为真，则这个布尔表达式称为可适定的。注意：不是所有的布尔表达式都是可适定的。 例2：231123123123()()()()()x x x x x x x x x x x x +++++++不是可适定的。
因为第一个句子（clauses ）表明123,,x x x 至少一个取“真”值，由2，3，4句子推出123,,x x x 必须都取“真”值，最后一个句子要求不可能都取“真”值。因此，布尔表达式是不可适定的。
适定性问题的一般形式为：给定包含12,,
,n x x x 的m 个句子1,,m C C （每个i C 都是
12,,,n x x x 的“或”和“否”的运算），布尔表达式12m C C C 是可适定的吗？
适定性问题是数理逻辑的中心问题，枚举所有可能的真值分配共有2n
种，不是有效算法。该问题可以描述为一个整数规划问题（0－1规划）。如果令“真”＝1，“假”＝0，1x x =-，那么要求每个句子C 取值为“真”等价于
(1)1x C
x C
x x ∈∈+-≥∑∑
例2转化为1231
223311231
(1)1
(1)1
(1)1
(1)(1)(1)1{0,1}
i x x x x x x x x x x x x x ++≥??+-≥??+-≥??+-≥??-+-+-≥?∈??
布尔表达式是由“与”连接起来的一些句子构成，则这个表示式称为“合取范式”（conjunctive Normal form ），目标函数可以变为123max y y x x x ≤++
3－Sat 问题
3－适定性问题是适定性问题的特例，可以证明适定性多项式变换到了3适定性，设
1
m F C C =，我们要构造一个新的'F 使得每个子句是三个文字，且F 是可适定的当且仅
当'
F 可适定的。对于F 的每个子句i C 分三种情况讨论：
（1） 若i C 有三个文字，则i C 不变。 （2） 若i C 有三个以上文字，即12 (3)i k C k λλλ=++
+>，我们把i C 换成
2
k -个
子
句123
12
1
3
()()
k k k x x x
x x
x λλλλλλ--++++++++其
中
12,
,
,k x x x
-
是新变量。
（3） 若i C λ=我们用y z λ++代替i C ，若'i C λλ=+，则用'y λλ++代替
i C ，然后我们给公式添加上一些子句
()()()()()()()
z z z y y y y αβαβαβαβαβαβαβ++++++++++++++其中,,,y z αβ都是新变量，添加部分迫使,z y 在任何适应'
F 的真值分配中都是假的，从而',λλλ+分别等价于它们的代替部分。
注意：以上转换适多项式转换，因为一个句子的文字个数至多为变量的总数n 个，所以k n ≤，m 个子句。
1、工作基础
在网络优化方面完成了一系列课题,具体总结如下:
(1) Optimal Traffic Counting Location Problem in Road Networks （与香港科技大学交通研究所合作项目, 2002-2004, 负责人: 杨超, 己完成）。
(2) 网络系统最优调整策略问题的研究（教育部优秀青年教师资助计划项目, 2001-2003, 负责人: 杨超, 己完成）。
(3) A Further Study on Inverse Optimization Problems （香港城市大学合作项目, 2000-2001, 负责人: 杨超, 已完成 ）。
(4) 农产品物流配送模式研究（教育部新世纪优秀人才支持计划项目, 2007-2009, 负责人: 杨超, 项目进行中）。
(5) 网络系统的多阶段容量扩张问题的研究（国家自然科学基金项目, 70071011，2001-2003, 负责人: 杨超, 已完成, 结题评为 “优”）。
(6) 网络系统工作站选址的两级优化模型研究（国家自然科学基金项目，70271027，2003-2005, 负责人: 杨超, 已完成, 结题评为 “良” ）。
(7) 网络扩张的成本效益均衡研究（国家自然科学基金项目，70471042, 2005－2007，负责人: 杨超, 已结题）。
（8）基于用户需求多元化的网络服务设施选址两级决策模型研究(国家自然科学基金项
目, 2008年新批, 负责人: 杨超)
(9) 鲜活农产品现代物流配送技术的研究与示范 (2005.7-2007.5, 河南省重大科技攻关计划项目, 负责人: 杨超, 已完成) 。
(10) 郑东新区道路交通网络优化投资方案研究 (2005, 负责人: 杨超, 已完成) 。 (11)巩义市交通网络布局及道路优化方案研究（2004，负责人: 杨超, 已完成）。 (12)武汉钢铁集团进口铁矿石物流系统优化研究（2005-2006，负责人: 杨超, 已完成）。
(13)河南高速公路网络优化投资方案(2006, 负责人: 杨超, 已完成) 。
2 主要论文
1) Yang C.,and Zhang J., Inverse Maximum Capacity Problem, OR.Spektrum,1998(20):97-100。
(SCI源刊)
2）Zhang J., Yang C. and Lin, Y., A Class of Bottleneck Expansion Problems, Computer & Operation Research, 2001(28): 505-519 。(SCI源刊)
3) Yang C., and Zhang J., Two General Methods for Inverse Problems, Applied Mathematics
Letter, 1999( 12 )No 2 : 69-72 。(SCI源刊)
4) Yang C., and Zhang J., A Constrained Capacity Expansion Problem on Network,
International Journal of Computer and Mathematics, 1998(70), No.2: 19-33。(SCI源刊) 5) Yang C., and Chen X., An Inverse Maximum Capacity Path Problem with Lower bound
Constraints, Acta Mathematica Scientia. 2002(22): 207-212。(SCI源刊)
6) Yang C., Zhang J and Ma, Z., Inverse Maximum Flow and Minimum Cut Problem,
Optimization, 1997(40): 147-170。(SCI源刊)
7) Zhang J, Ma, Z., and Yang C., A Column Generation Method for Inverse Shortest Path
Problem, Mathematical Method of Operation Research, 1995(41): 347-358。(SCI源刊) 8) Yang C., and Liu J., A Capacity Expansion Problem with Budget Constraint and
Bottleneck Limitation, Acta Mathematica Scientia 2001( 21) : 428-432。(SCI源刊)
9) Yang H., Yang C and Gan L., Model and Algorithm for the Screen Line-Based
Traffic-Counting Location Problem, Computer and Operation Research, 2006(33), 836-858。(SCI源刊)
10) Yang C., Hao C. and Zhang J., On the Optimum Capacity of Capacity Expansion Problem,
Mathematical Method of Operation Research, 2007 (66), 225-233。(SCI源刊)
11) Yang C., and Zhang J, On the Bottleneck Capacity Expansion in Network, Acta Mathematica
Scientia 2006B (2), 202-208 。(SCI源刊)
12）He B, Yang C. and Ren M. A Study on Decision Model of Bottleneck Capacity Expansion with Fuzzy Demand, Lecture Notes in Computer Science, Neural Information Processing, PT 3 Proceedings 4234 : 1055-1062, 2006。(SCI源刊)
13)He B, Yang C, and Zhang H. A Fuzzy Multi-objective Programming for Optimization of
Reverse Logistics for Solid Waste. Proceedings of ICM’2007. The 6th International Conference on Management. V ol 1, 59-65。
14) He B, Yang C, and Ren M.A Fuzzy Multi-objective Programming for Optimization of
Reverse Logistics for Solid Waste through Genetic Algorithms. Proceedings of FSKD’2007.The 4th international conference on Fuzzy Systems and Knowledge Discovery. V ol 3, 416-420.
15) Weng K., and Yang C., Two Artificial Intelligence Heuristics in Solving Multiple Allocation
Hub Maximal covering Problem. ICIC2006, Lecture Notes in Computer Science 2006 , 4113-4116 。(SCI源刊).
16) Yang J., and Yang C., Model and Algorithm for the pq-FIP with Two Kind of Facilities,
Proceedings of 2004 International Conference on Management Science & Engineering, 2004(1): 487-491。
17) Weng K., and Yang C., The Hub Location with Delivery Time Limitation, International
Conference on Management Science & Engineering, Inchon, R.Korea, 2005, 1: 380-383。18) Yang J., and Y ang C., The Retail Stroes’Competitive Location Problem with Retail Regional
Saturation. IEEE 2005 International Conference on Servieces Systems and Services Management, 2005, 2: 1511-1516。（EI，ISTP收录）
19) Ma Y., Yang C., and Zhang M., .A Genetic Algorithm for Time-Satisfaction-Based Set
Covering Location Problem. IEEE 2005 International Conference on Communications, Circuits and Systems Proceedings, Hong Kong, China, 2005, 2:1037-1041。
20) Yang J, Yang C and Ma Y,. Model and Algorithm for the Location of Survey Stations with
Intercepted Probability on a Network,Lecture Notes in Decision Science, 2004(4): 297-303 。
21) Wang.Q, and Yang C., Optimization on Sequence of Road Building on New urban District
Advances in Systems Science and Application，2007. 468-472。
22)Tang, K. and Yang, C., A Distribution Network Design Model for Deteriorating Item,
International Journal of Logistics Systems and Management, 2008(4): 366-383。
23)翁克瑞, 杨超. 顺应潮流的轴辐式物流网络, 物流技术, 2006, 7: 14-17。
24) 翁克瑞, 杨超. 多分配枢纽站最大覆盖选址问题, 工业工程与管理, 2007 (1) , 40-44。
25) 翁克瑞, 杨超，屈波。多分配枢纽站集覆盖问题及分散搜索算法实现, 系统工程,
2006(11) ，1-5。
26) 何波, 杨超，张华. 固体废弃物逆向物流网络优化设计, 系统工程，2006(8)，38-42。
27)何波，杨超，张华废弃物回收的多层逆向物流网络优化设计问题研究. 中国管理科学，
2007,15(3): 61-67。
28)何波，杨超，任鸣鸣. 废弃物处理站选址问题及多目标演化算法求解.系统工程理论与
实践，2007,11:72-78。(EI收录)
29)何波，杨超，任鸣鸣. 基于第三方物流的产品回收物流网络优化模型及算法. 计算机集
成制造系统2008,1 34-37。
30)何波，杨超，杨珺废弃物逆向物流网络设计的模糊多目标优化模型.工业工程与管
理.2007, 5: 43-46。
31)杨珺，杨超，张敏. 需求不确定情况下的服务站截流选址分配问题研究. 物流技术,
2005(8): 50-53。
32) 杨珺，杨超，马云峰. 带有双重容量限制的FIP问题研究. 中国公路学报, 2004(4): 85-88。(EI收录)
33) 张敏，杨超，杨珺.危险品集成物流管理系统选址-选线模型研究. 管理科学学报 2008,待发表。
34) 杨超, 马云峰, 杨珺. 一类带容量限制的服务站选址问题. 系统工程, 2004, 22(1):19-23。
35) 马云峰，杨超，张敏. 物流设施选址中的时间满意问题分析. 中国物流与采购, 2005, (17): 50-51。
36) 杨超, 陈新. 城市交通网络布局的AHP评价体系研究. 经济经纬, 2005(4):47-50。
37) 杨珺，杨超, DEA在网络容量扩张方案的决策与有效性评价中的应用, 系统工程理论方
法应用,
2005(4)：299-302。
38)唐凯，杨超，杨珺. 随机多阶段分销网络设计模型. 中国管理学报，2007(15): 98-104。
39)唐凯，杨超，杨珺. 带市场选择的联合库存选址模型. 工业工程与管理，2007(12):5-10。
40) 任鸣鸣, 杨超; 何波. 需求不确定状态下的工厂选址和规模决策的综合优化方法, 系
统工程, 2007, 25(6): 1-5。
41)郝春艳; 杨超, 网络容量扩张的成本效益均衡决策模型, 统计与决策, 2006, (5): 16～17。
42)郝春艳; 杨超, 一类网络容量和扩张的纯效益模型及算法研究, 武汉理工大学学报
数学建模路线优化问题
选路的优化模型 摘要: 本题是一个有深刻背景的NPC问题，文章分析了分组回路的拓扑结构，并构造了多个模型，从多个侧面对具体问题进行求解。最短树结构模型给出了局部寻优的准则算法模型体现了由简到繁，确保较优的思想而三个层次分明的表述模型证明了这一类问题共有的性质。在此基础上我们的结果也是比较令人满意的。如对第一题给出了总长为599.9，单项长为216的分组，第二题给出了至少分四组的证明。最后，我们还谈到了模型的优缺点及推广思想。 一、问题描述 “水大无情，人命关天”为考察灾情，县领导决定派人及早将各乡（镇），村巡视一遍。巡视路线为从县政府所在地出发，走遍各乡（镇），村又回到县政府所在地的路线。 1.若分三组巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2.假定巡视人员在各乡（镇）停留时间为T=2小时，在各村停留时间为t =1 小时， 汽车行驶速度为V=35公里/时，要在24小时内巡视完，至少分成几组；给出这 种分组下你认为最佳的巡视路线。 3.上述关于T，t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多 少？给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 4.巡视组数已定（如三组）要求尽快完成巡视，讨论T，t和V改变时最佳路线的 影响（图见附录）。 二、问题假设 1、乡（镇）村只考察一次，多次经过时只计算一次停留时间。 2、非本县村不限制通过。 3、汽车的行驶速度始终一致。 三、符号说明 第i 人走的回路Ti=vv i(i) v2(i)v n(i) Ti=00表示第i人在0点没移动 四、模型建立
在这一节里，我们将提出若干个模型及其特点分析，不涉及对题目的求解。 最简树结构模型 在这个模型中我们依靠利用最短树的特殊结构所给出的准则，进行局部寻优，在一个不大的图里，我们较易得到较优解。 (a)分片 准则1利用最短树的长度可大致的估算出路程长，在具体操作中，各片中 的最短路程长度不宜相差太大。 准则 2 尽可能将最短树连成一个回路，这可保证局部上路程是较短的。 (b)片内调整 a2 a3 a4 a5 a6假设a3 a4有路相连 细准1对于右图的最短树结构，最好的走法是a 若a3 a4 进去重复走的话，它与上述的走法路程差w(a3, a2)+w(a2 ,a5)+w(a4, a5)—w(a3, a4)。由两点间最小原则上式是大于0的优劣可见 细准2若有如图所示结构，一般思想是：将中间树枝上的点串到两旁树枝，以便连成回路。 五、模型求解 问题一该问题完全可以用均衡模型表述 用算法模型 1 经过局部优化手工多次比较我们能够给出的最佳结果为第一组路径为 0—P—28—27—26—N—24—23—22-17—16—1—15—1—18—K—21—20—25— M--0 长191.1 经5 镇6 村 第二组路径为 0—2—5—6—L—19—J—11--G—13—14—H—12—F—10—F—9—E—8—E—7—6—5—2—0 长216.5 经6 镇11 村第三组路径为O—2—3—D—4—D—3—C—B—1—A—34—35—33—31—32—30—Q—29 —R 长192.3 经6 镇11 村总长S=599.9 公里 由算法2 给出的为 1组0—P—29—R—31—33—A—34—35—32—30—Q—28—27—26—N—24—33—22—23—N—2 6—P—0 5 乡13 村长215.2 公里 2组0—M—25—21—K—17—16—I—15—I—18—K—21—25—20—L—19—J—11—G—13—14 —O 5 乡11 村长256.2 公里 3组 O—2—5—6—7—E—9--F—12--H--—12—F—10—F—9—E-8—4—0—7—6—M—5-2—3—L —13—1—0 8 乡11 村长256.3 公里 总长727.7 公里
优化问题的数学模型及基本要素
第1章 优化设计 Chapter 1 Optimization Design 1-1 优化设计 1-1-1 最优化 (optimize, optimization ) 所谓最优化，通俗地说就是在一定条件下，在所有可能的计划、设计、安排中找出最好的一个来。换句话说，也就是在一定的条件下，人们如何以最好的方式来做一件事情。(Optimization deals with how to do things in the best possible manner) 结论的唯一性是最优化的特点，即公认最好。(It is the best of all possibilities) 最优化的思想体现在自然科学、工程技术及社会活动的各个领域，最优化的方法在这些领域也得到了广泛地应用。(P1) 1-1-2 最优化方法 (Arithmetic ) 要从所有可能的方案中找出最优的一个，用“试”（try ）的办法是不可行的，需要采用一定的数学手段。二十世纪五十年代以前，用于解决最优化问题的数学方法仅限于古典的微分和变分(differential and variation)。数学规划法在五十年代末被首次用于解决最优化问题，并成为现代优化方法的理论基础。线性规划和非线性规划是数学规划的主要内容，它还包括整数规划、动态规划、二次规划等等。(Linear programming or Nonlinear programming, Integer, Dynamic, Quadratic ) 数学规划法与电子计算机的密切结合,改变了最优化方法多有理论研究价值,而少有实际应用的局面,使得解决工程中的优化问题成为可能。因此,我们现在所说的最优化方法，实际上包括了最优化理论和计算机程序二方面的内容。(Optimization theory plus computer program) 1-1-3 优化设计 下面以一个简单的问题为例来说明传统设计与优化设计这二个不同的设计过程。 例1-1 设计一个体积为5cm 3的薄板包装箱，其中一边的长度不小于4m 。要求使薄板耗 材最少，试确定包装箱的尺寸参数，即长a ，宽b 和高h 。 分析 包装箱的表面积s 与它的长a ，宽b 和高h 尺寸有关。因此，耗板最少的问题可以转化为表面积最小问题，故取表面积s 为设计目标。 传统设计方法: 首先固定包装箱一边的长度如)(4m a =。要满足包装箱体积为3 5m 的设计要求，则有以下多种设计方案: 如果包装箱的长度a 再取)(4m a >的其他值，则包装箱的宽度和高度还会有很多其他结果… 。 最后，从上面众多的可行方案中选择出包装箱表面积最小的方案来，这就是相对最好的设计方案。但由于不可能列出所有可能的设计方案，最终方案就不一定是最优的。 机械产品的传统设计通常需要经过：提出课题、调查分析、技术设计、结构设计、绘图
数学建模优化问题经典练习
1、高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳 万元，可使用的金属板有500t，劳动力有300人/月，机器有100台/月，此外，不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号为100万元，中号为150万元，大号为200万元，现在要制定一个生产计划，使获得的利润为最大， max=4*x1+5*x2+6*x3-100*y1-150*y2-200*y3; 2*x1+4*x2+8*x3<=500; 2*x1+3*x2+4*x3<=300; 1*x1+2*x2+3*x3<=100; @bin(y1); @bin(y2); @bin(y3); y1+y2+y3>=1; Global optimal solution found. Objective value: 300.0000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X1 100.0000 0.000000 X2 0.000000 3.000000 X3 0.000000 6.000000 Y1 1.000000 100.0000 Y2 0.000000 150.0000 Y3 0.000000 200.0000 Row Slack or Surplus Dual Price 1 300.0000 1.000000 2 300.0000 0.000000 3 100.0000 0.000000 4 0.000000 4.000000 5 0.000000 0.000000
关于电梯系统优化问题的数学模型
关于电梯系统优化问题 的数学模型 集团档案编码：[YTTR-YTPT28-YTNTL98-UYTYNN08]
关于电梯系统优化问题的数学模型 摘要 在高层商务楼里，电梯承担着将人和货物运送到各个楼层的任务。在当今社会，工作生活节奏愈发加快，因而电梯系统的运行效率对人们的生活的影响不可忽视。目前的高层商务楼等大多数高层建筑中，一般都使用单井道单轿厢或者单井道双轿厢两种模式的电梯，本文就结合这两种模式，根据实际情况将问题分为两种情况考虑，重点讨论了将电梯运行效率最大化的方法，建立了相关模型，并给出了相应的优化参数。 本文将电梯系统的优化分为高峰期和非高峰期两种时期进行讨论。高峰期时通过对问题的分析，发现可以设置电梯区间以尽可能减少目标层较高的乘客占用目标层较低的乘客的电梯资源，根据这一思想，我们将其简化为排队问题来考虑，并据此建立了排队模型，通过实地统计数据以及C语言的编程，能够较好地解出模型，得到在高峰期时将一部分电梯区间的顶层设为第14层左右的优化方案。非高峰期时通过对这一时期特点的分析，以每台电梯在无乘梯需求时自动停留的楼层为着眼点，采用枚举的方法编程求解，得到在非高峰期将电梯均匀分布在楼层中的优化方案。最后，我们对模型参数进行了灵敏度的分析，发现虽然模型对数据的依赖性较强，但最优方案不随参数的波动而变化，所以这个结果还是可信的。 本文提出的方案直观易行，且几乎不需额外的经济投入，可行性很强，具有较好的参考价值。 一问题重述 在高层商务楼里，电梯承担着将人和货物运送到各个楼层的任务。目前的高层商务楼等大多数高层建筑中，主要使用单轿厢和双轿厢两种电梯运行系统。单轿厢电梯在向上运行时，只有满足了所有“上行请求”时才会开始满足“下行请求”，反之亦然；而对于双轿厢电梯，乘客在进入轿厢前就通过按钮面板选择了要停靠的楼层，系统迅速整合分析接收到的流量数据，并调度合适的轿箱来应接乘客。 现有一座商务楼，设计地上层数为28层，地下停车楼2层，每层的建筑面积为1500平方米，楼内有6个用于客梯的电梯井道。电梯按照商务楼建筑面积15至20平方米每人的标准来设计。第1层的楼层高为4.8米，其余层均为3.2米，设计电梯的平均运行速度1.6米/秒。我们的任务是： 1．建立一个合适的单轿箱客梯系统的运行方案，使尽可能地提高电梯系统的运行效率； 2．分别在运行的高峰期与非高峰期，对双轿箱的电梯系统与单轿箱的电梯系统的运行效率等进行对比分析,评价两种方案的优劣性，估计双轿厢系统运行效率的提高率。 二基本假设 1．电梯载客量为13人，且不超载。13人载客量是国内最常见的一种电梯规格，并且为了乘梯安全，电梯不应超载。 2．电梯在每层停留的时间相等。在假设1成立的前提下，电梯乘客可以迅速有序地离开电梯，电梯停留时间受离开人数的影响可以忽略不计。
优化问题的数学模型
一. 管理科学的定义 管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策制定的一门学科. (1) 定量因素(2) 科学的方法(3) 辅助决策制定 二.用管理科学的方法解决问题的基本步骤. （1） 提出问题，并根据需要收录有关数据信息。管理科学工作者向管理者咨询、鉴别所 要考虑的问题以确定合理的目标，然后根据要求收集一些关键数据，并对数据作相应的分析。 （2） 建立模型，引入决策变量，确定目标函数（约束条件）。建模过程是一项创造性的 工作，在处理实际问题时，一般没有一个唯一正确的模型，而是有多种不同的方案。建模是一个演进过程，从一个初始模型往往需要不断的完善渐渐演化成一个完整的数学模型。 （3） 从模型中形成一个对问题求解的算法。要在计算机上运行数学程序对模型进行求 解，一般情况下能找到对模型求解的标准软件。例如，对线性规划问题已有Excel 、Cplex 、Lingo 等标准软件求解。有时要自己编写程序。 （4） 测试模型并在必要时修正。在模型求解后，需要对模型进行检验，以保证该模型能 准确反映实际问题，需要检验模型提供的解是否合理，所有主要相关因素是否已考虑，当有些条件变化时，解如何变化等。 （5） 应用模型分析问题以及提出管理建议。对模型求解并分析后，将相应的最优方案提 交给管理者，由管理者做出决策。管理科学工作者并不作管理决策，其研究只是对涉及的问题进行分析并向管理者提出建议。管理者还要考虑管理科学以外的众多因素才能做出决策。 （6） 帮助实施管理决策。建议被管理者采纳以后，一旦做出管理决策一般要求帮助监督 决策方案的实施。 新问题, 新模型, 新算法, 新应用. 三.优化问题的数学模型 1212max(min)(,, ,) (,,)0..1,2,n j n Z f x x x g x x x s t j m =≤?? =? 由于,j f g 是非线性函数时，此问题是非线性优化问题, 求解较复杂。我们主要讨论线性优化问题，常见的形式：混合整数规划 （1） max 0 0 Z CX hY AX GY b X Y =++≤≥≥取整数 其中111,,,,m n m p m n p A G b C h ?????，不失一般性，我们假定,,,,C h A G b 都是整数矩阵。 当0p =时，（1）为纯整数规划，当0n =时，（1）为线性规划。
数学建模面试最优化问题
C题面试时间问题 有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队(即在任何一个阶段4名同学的顺序是一样的)。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示(单位：分钟)： 这4名同学约定他们全部面试完以后一起离开公司．假定现在时间是早晨8:00问他们最早何时能离开公司? 面试时间最优化问题 摘要： 面试者各自的学历、专业背景等因素的差异，每个面试者在每个阶段的面试时间有所不同，这样就造成了按某种顺序进入各面试阶段时不能紧邻顺序完成，即当面试正式开始后，在某个面试阶段，某个面试者会因为前面的面试者所需时间长而等待，也可能会因为自己所需时间短而提前完成。因此本问题实质上是求面试时间总和的最小值问题，其中一个面试时间总和就是指在一个确定面试顺序下所有面试者按序完成面试所花费的时间之和，这样的面试时间总和的所有可能情况则取决于n 位面试者的面试顺序的所有排列数 根据列出来的时间矩阵，然后列出单个学生面试时间先后次序的约束和学生间的面试先后次序保持不变的约束，并将非线性的优化问题转换成线性优化目标，最后利用优化软件lingo变成求解。 关键词：排列排序0-1非线性规划模型线性优化 (1)
（一）问题的提出 根据题意，本文应解决的问题有： 1、这4名同学约定他们全部面试完以后一起离开公司。假定现在的时间是早晨8：00，求他们最早离开公司的时间； 2、试着给出此类问题的一般描述，并试着分析问题的一般解法。 （二）问题的分析 问题的约束条件主要有两个：一是每个面试者必须完成前一阶段的面试才能进入下一阶段的面试(同一个面试者的阶段次序或时间先后次序约束)，二是每个阶段同一时间只能有一位面试者(不同面试者在同一个面试阶段只能逐一进行)。 对于任意两名求职者P、Q，不妨设按P在前，Q在后的顺序进行面试，可能存在以下两情况： （一）、当P进行完一个阶段j的面试后，Q还未完成前一阶段j-1的面试，所以j阶段的考官必须等待Q完成j-1阶段的面试后，才可对Q进行j阶段的面试，这样就出现了考官等待求职者的情况。这一段等待时间必将延长最终的总时间。 （二）、当Q完成j-1的面试后，P还未完成j阶段的面试，所以，Q必须等待P完成j阶段的面试后，才能进入j阶段的面试，这样就出现了求职者等待求职者的情况。同样的，这个也会延长面试的总时间。 以上两种情况，必然都会延长整个面试过程。所以要想使四个求职者能一起最早离开公司，即他们所用的面试时间最短，只要使考官等候求职者的时间和求职者等候求职者的时间之和最短，这样就使求职者和考官的时间利用率达到了最高。他们就能以最短的时间完成面试一起离开公司。这也是我们想要的结果。 （三）模型的假设 1.我们假设参加面试的求职者都是平等且独立的，即他们面试的顺序与考官无关； 2.面试者由一个阶段到下一个阶段参加面试，其间必有时间间隔，但我们在这里假定该时间间隔为0； 3.参加面试的求职者事先没有约定他们面试的先后顺序； 4.假定中途任何一位参加面试者均能通过面试，进入下一阶段的面试。即：没有中途退出面试者； 5.面试者及各考官都能在8：00准时到达面试地点。 （四）名词及符号约束 1. aij （i=1,2，3，4；j=1,2,3)为求职者i在j阶段参加面试所需的时间 甲乙丙丁分别对应序号i=1，2,3，4 2.xij （i=1,2，3，4；j=1,2,3) 表示第i名同学参加j阶段面试的开始时间（不妨把早上8:00记为面试的0时刻） (2)
优化问题与规划模型
§3.6 优化问题与规划模型 与最大、最小、最长、最短等等有关的问题都是优化问题。 解决优化问题形成管理科学的数学方法：运筹学。运筹学主要分支：（非）线性规划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论。 6.1 线性规划 1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》 1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论. 1. 问题 例1 作物种植安排 一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为 110元, 75元, 60元. 如何规划经营使经济效益最大. 分析：以取得最高的产值的方式达到收益最大的目标. 1. 求什么？分别安排多少亩地种蔬菜、棉花、水稻？ x 1亩、 x 2 亩、 x 3 亩 2. 优化什么？产值最大 max f=10x 1+75x 2 +60x 3 3. 限制条件？田地总量 x 1+x 2 +x 3 ≤ 50 劳力总数 1/2x 1 +1/3x 2 +1/4x 3 ≤ 20 模型 I : 设决策变量：种植蔬菜 x 1亩, 棉花 x 2 亩, 水稻 x 3 亩， 求目标函数 f=110x 1+75x 2 +60x 3 在约束条件x 1+x 2 +x 3 ≤ 50 1/2x 1 +1/3x 2 +1/4x 3 ≤20 下的最大值 规划问题：求目标函数在约束条件下的最值, 规划问题包含3个组成要素: 决策变量、目标函数、约束条件。 当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题, 否则称为非线性规划问题。 2. 线性规划问题求解方法 称满足约束条件的向量为可行解,称可行解的集合为可行域, 称使目标函数达最值的可行解为最优解. 命题 1 线性规划问题的可行解集是凸集. 因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸多边形。 命题2 线性规划问题的最优解一定在可行解集的某个极点上达到. 图解法：解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各极点处的值，经比较后，取最值点为最优解。 命题3 当两个变量的线性规划问题的目标函数取不同的目标值时，构成一族平行直线,目标值的大小描述了直线离原点的远近。 于是穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点即为取的极值的极点—最优解。 单纯形法 : 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解
数学建模课程设计——优化问题
在手机普遍流行的今天，建设基站的问题分析对于运营商来说很有必要。本文针对现有的条件和题目的要求进行讨论。在建设此模型中，核心运用到了0-1整数规划模型，且运用lingo 软件求解。 对于问题一： 我们引入0-1变量，建立目标函数：覆盖人口最大数=所有被覆盖的社区人口之和，即max=15 1j j j p y =∑，根据题目要求建立约束条件，并用数学软件LINGO 对其模型求解，得到最优解。 对于问题二： 同样运用0-1整数规划模型，建立目标函数时，此处假设每个用户的正常资费相同，所以68%可以用减少人口来求最优值，故问题二的目标函数为：max=∑=15 1j j j k p 上述模型得到最优解结果如下： 关键字：基站; 0-1整数规划；lingo 软件
1 问题的重述．．．．．．．．．．．．．．．．．．．．．．．．．3 2 问题的分析．．．．．．．．．．．．．．．．．．．．．．．．．4 3 模型的假设与符号的说明．．．．．．．．．．．．．．．．．．．5 3.1模型的假设．．．．．．．．．．．．．．．．．．．．．． 5 3.2符号的说明．．．．．．．．．．．．．．．．．．．．．． 5 4 模型的建立及求解．．．．．．．．．．．．．．．．．．．．．. 5 4.1模型的建立．．．．．．．．．．．．．．．．．．．．．． 5 4.2 模型的求解．．．．．．．．．．．．．．．．．．．．．． 6 5 模型结果的分析．．．．．．．．．．．．．．．．．．．．．．．7 6 优化方向．．．．．．．．．．．．．．．．．．．．．．．．．．7 7 参考文献．．．．．．．．．．．．．．．．．．．．．．．．．．8 8、附录．．．．．．．．．．．．．．．．．．．．．．．．．．． 9
最优化问题的数学模型及其分类
最优化问题的数学模型及其分类 例1.1.1 产品组合问题 某公司现有三条生产线用来生产两种新产品，其主要数据如表1-1所示。请问如何生产可以让公司每周利润最大？ 表1-1 设每周生产的产品一和产品二 的产量分别为1x 和2x ，则每周的生产利润为：2153x x z +=。由于每周的产品生产受到三条生产线的可用时间的限制，因此1x ，2x 应满足以下条件： ?????? ?≥≤+≤≤0, 18231224212121 x x x x x x 故上述问题的数学模型为
2153max x x z += . .t s ?????? ?≥≤+≤≤0, 18231224212121 x x x x x x 其中max 是最大化（maximize ）的英文简称，??t s 是受约束于（subject to ）的简写。 例1.1.2 把一个半径为１的实心金属球熔化后，铸成一个 实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？ 设圆柱体的底面半径为r ，高为h ，则该问题的数学模型为： ??? ??=? ?+=ππππ3 422min 22 h r t s r rh S 其中min 是最小化（minimize ）的简写。 通过以上二例，可以看出最优化问题的数学模型具有如下结构： （１） 决策变量（decision variable ）：即所考虑问题 可归结为优选若干个被称为参数或变量的量 n x x x ,,,21 ，它们都取实数值，它们的一组值构 成了一个方案。 （２） 约束条件（constraint condition ）：即对决策
变量n x x x ,,,21 所加的限制条件，通常用不等式或等式表示为： ()(),,,2,1, 0,,,,,2,1, 0,,,2121l j x x x h m i x x x g n j n i ===≥ （３） 目标函数（objective function ）和目标：如使 利润达到最大或使面积达到最小，通常刻划为极大化（maximize ）或极小化（minimize ）一个实值函数()n x x x f ,,21 因此，最优化问题可理解为确定一组决策变量在满足约束条件下，寻求目标函数的最优。 注意到极大化目标函数()n x x x f ,,21相当于极小化 ()n x x x f ,,21-，因此，约束最优化问题的数学模型一般可 表示为： () ()()()?? ? ??===≥??l j x x x h m i x x x g t s x x x f n j n i n ,,2,1,0,,,1.1.1,,2,1,0,,,,,min 212121 若记()T n x x x x ,,21=，则（1.1.1）又可写成：
几个优化问题的数学建模
几个优化问题的数学建模 一、一个开放式基金投资问题
6、模型的评价 模型的主要优点是采用较为成熟的数学理论建立模型，利用数学软件计算，可信度比较高，便于推广。主要缺点是建立的模型是确定的而不是更符合实际情况的随机型模型。 二、结合人员分配的生产规划问题 1、问题 某公司要对四种产品（P1，P2，P3，P4）在五条生产线（L1到L5）上的生产进行规划。产品P1和P4的单位纯利润为7元，产品P2的单位纯利润为8元，产品P3的单位纯利润为9元。在规划期内这五条生产线各自可以进行生产的时间长度各不相同。L1到L5的最大可用生产时间分别为4500小时，5000小时，4500小时，1500小时和2500小时。表1列出了在每条生产线上生产每种产品一个单位所需要的时间。 （1）、假设生产是流水线作业，产品P1到P4各应生产多少才能使总利润最大？ （2）、如果在生产过程中允许在生产线之间进行人员转移（从而使工时也相应转移），如表2所示，则最大利润是多少？应转移多少个工时，如何转移？
（3）、如果生产不是流水线作业，模型应如何修改？ 表1 单位生产时间 表2 可以进行的人员转移 2、假设 （1）每条生产线可生产各种产品； （2）每个生产人员的工作效率相同，且熟练各条生产线的操作，可在各条生产线之间转移。 3、建模 3.1、问题(1) 设每种产品必须经过5条生产线才能生产出来，产品P i 的产量为x i ,单位纯利润为r i ,在生产线L j 上的单位生产时间为d ij 。生产线L j 的可用总工时数为c j ,则可得模型1： max 41 i =∑r i x i s.t. 41 i =∑ d ij x i ≤c j ，j=1，2，3，4，5 x i ≥0，i=1，2，3，4
数学建模_投资最优问题
数学建模一周论文课程设计题目：最优投资方案 1：吴深深学号：201420181013 2：许家幸学号：201420180422 3：王鑫学号：201420181220 专业软件工程 班级1421801Z
指导教师朱琳 2016 年 6 月9 日
摘要 本文主要研究银行投资受益最优问题，根据投资证券的种类、信用等级、到期年限、到期税前收益等的具体情况，根据线性规划的方法分析出数学模型，并且运用Lingo软件进行编码求解。 根据问题一、根据此模型能够得到具体的解决方案，问题二、三都是根据问题一的模型做具体约束条件的变化，从而求出最优解。 此模型适用于一般简单的银行投资问题。这个优化问题的目标是有价证券回收的利息为最高,要做的决策是投资计划。即应购买的各种证券的数量的分配。综合考虑：特定证券购买、资金限制、平均信用等级、平均年限这些条件，按照题目所求，将决策变量、决策目标和约束条件构成的优化模型求解问题便得以解决。 但是本模型不适合解决情况过于复杂的银行投资问题。 关键字：最优投资线性规划Lingo求解 一、问题重述 某银行经理计划用一笔资金进行有价证券的投资，可供购进的证券及其信用等级、到期年限、收益如下表所示。按照规定，市政证券的收益可以免税，其他证券的收益需按50%的税率纳税。此外还有以下限制： 政府及代办机构的证券总共至少要购进400万元，所购证券的平均信用等
级不超过1.4（数字越小，信用程度越高），所购证券的平均到期年限不超过5年。 二、模型假设 假设: 1.假设银行有能力实现5种证券仸意投资； 2.假设在投资过程中，不会出现意外情况，以至不能正常投资； 3.假设各种投资的方案是确定的； 4.假设证券种类是固定不变的，并且银行只能在这几种证券中投资； 5.假设各种证券的信用等级、到期年限、到期税前收益是固定不变的； 6.假设各种证券是一直存在的。 三、符号约定 符号含义 X i取1-5，表示从A..E中证券的投资额（百万）i
电梯系统优化问题的数学模型
电梯系统优化问题的数学 模型 Prepared on 22 November 2020
关于电梯系统优化问题的数学模型 摘要 在高层商务楼里，电梯承担着将人和货物运送到各个楼层的任务。在当今社会，工作生活节奏愈发加快，因而电梯系统的运行效率对人们的生活的影响不可忽视。目前的高层商务楼等大多数高层建筑中，一般都使用单井道单轿厢或者单井道双轿厢两种模式的电梯，本文就结合这两种模式，根据实际情况将问题分为两种情况考虑，重点讨论了将电梯运行效率最大化的方法，建立了相关模型，并给出了相应的优化参数。 本文将电梯系统的优化分为高峰期和非高峰期两种时期进行讨论。高峰期时通过对问题的分析，发现可以设置电梯区间以尽可能减少目标层较高的乘客占用目标层较低的乘客的电梯资源，根据这一思想，我们将其简化为排队问题来考虑，并据此建立了排队模型，通过实地统计数据以及C语言的编程，能够较好地解出模型，得到在高峰期时将一部分电梯区间的顶层设为第14层左右的优化方案。非高峰期时通过对这一时期特点的分析，以每台电梯在无乘梯需求时自动停留的楼层为着眼点，采用枚举的方法编程求解，得到在非高峰期将电梯均匀分布在楼层中的优化方案。最后，我们对模型参数进行了灵敏度的分析，发现虽然模型对数据的依赖性较强，但最优方案不随参数的波动而变化，所以这个结果还是可信的。 本文提出的方案直观易行，且几乎不需额外的经济投入，可行性很强，具有较好的参考价值。
一问题重述 在高层商务楼里，电梯承担着将人和货物运送到各个楼层的任务。目前的高层商务楼等大多数高层建筑中，主要使用单轿厢和双轿厢两种电梯运行系统。单轿厢电梯在向上运行时，只有满足了所有“上行请求”时才会开始满足“下行请求”，反之亦然；而对于双轿厢电梯，乘客在进入轿厢前就通过按钮面板选择了要停靠的楼层，系统迅速整合分析接收到的流量数据，并调度合适的轿箱来应接乘客。 现有一座商务楼，设计地上层数为28层，地下停车楼2层，每层的建筑面积为1500平方米，楼内有6个用于客梯的电梯井道。电梯按照商务楼建筑面积15至20平方米每人的标准来设计。第1层的楼层高为4.8米，其余层均为3.2米，设计电梯的平均运行速度1.6米/秒。我们的任务是： 1．建立一个合适的单轿箱客梯系统的运行方案，使尽可能地提高电梯系统的运行效率；
数学建模关于优化问题的论文
承诺书 我们仔细阅读了暑期数学建模竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的 资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规 则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B中选择一项填写）： A 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)：教练组 日期： 11 年 8 月 12 日评阅编号（由组委会评阅前进行编号）：
编号专用页评阅编号（由组委会评阅前进行编号）： 统一编号： 评阅编号：
多因素条件下作物施肥效果分析 摘要 本文是关于作物施肥数量与结构的优化问题，根据不同目标对施肥量与肥料搭配比例进行调整，达到各目标的最优。 首先，基于一元线性回归模型，以一种肥料作为自变量，另外两种肥料固定在第七水平，建立了六个一元回归方程，分别研究某一种肥料变化时，该肥料施肥量与产量的关系。根据散点图趋势，初步选取适当的一元函数，为了使散点图更直观准确，将原数据进行无量纲化处理，得到0到1间的值。利用eviews软件进一步对一元函数进行拟合，选取显著性最高的拟合结果，求解时，对非线性的回归方程，通过取对数将其线性化，得到结果后再将其转换成原函数形式，最终得到六个反映施肥量与产量关系的一元回归模型。为了提高六个回归方程整体的显著性，本文以三种肥料的施肥量同时作为自变量，建立三元二次回归模型，检验均通过，并具有高度的显著性，拟合效果较好。 其次，基于问题一中的一元线性回归模型与三元二次回归模型分别求解回归方程的最大值，即产量最大值。比较两个模型的结果，看出，由三元二次回归模型得到的产量更大，其中土豆与生菜产量的最大值分别为44.95t/ha，23.04t/ha。土豆对应的N、P、K肥料的施肥量分别为293.13kg/ha，250.0kg/ha，540.0kg/ha。生菜对应的N、P、K 肥料的施肥量分别为212.06kg/ha，426.91kg/ha，665.69kg/ha。 再次，考虑到施肥的经济性，以产值和施肥费用作为自变量，以总收益作为因变量，建立收益最大化模型。分别基于反映产量与施肥量关系的一元回归模型与三元二次回归模型，进行求解。由一元回归模型得到结果，当生菜K肥施肥量无穷大时，收益也趋近于无穷大，显然不合理，本文以一元二次函数对六个回归方程重新进行拟合，检验看出，显著性不高，但基于新的回归方程得到的结果更加合理，更符合实际情况，具有较高的实用性。基于三元二次回归模型进行求解时，通过（0,0,0,0）点的引入，增加了三种肥料交互影响产生的交叉项，避免了肥料搭配不合理造成的大量浪费。比较两种模型的结果看出，基于三元二次回归方程得到的收益更大，土豆与生菜的最大值分别为102500元/公顷，52023元/公顷。 再次，引入环保因素时，通过两种方法实现，一是基于收益最大化模型，将污染指数作为限制条件，以收益最大为目标，建立线性规划收益最大化模型。二是引入目标偏差变量，以偏差变量之和最小为目标，以污染指数，肥料搭配比例作为约束条件，建立多目标规划模型，以环境指数小于25为前提，追求收益尽量大。比较两种模型的结果看出，多目标规划的的结果更符合本问的要求，土豆与生菜的最大收益值分别为，环境指数为25，属于轻度污染， K肥施肥量超过满意值，但K肥适当增加能够增大收益，对土地没有造成污染，收益实际值与满意值相差不大，结果比较合理，符合本问的要求。 最后对模型应用效果作量化估计，难点在于如何对优化模型进行改进，得到评价模型。本文利用多目标规划结果中满意值与偏差值的差值占满意值的比例作为单目标的满意度，利用层次分析法得到单目标权重值，根据单目标的权重值与满意度求和可以得到多目标满意度，根据多目标总体的满意度对模型应用效果作量化估计。从而建立基于层次分析法与多目标规划的评价模型。最后对模型的推广作初步讨论，验证了模型较高的应用价值。
数学建模关于优化问题的论文
数学建模关于优化问题 的论文 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】
暑期数学建模竞赛 承诺书 我们仔细阅读了暑期数学建模竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的 资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和 参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规 则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B中选择一项填写）： A 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)：教练组 日期： 11 年 8 月 12 日评阅编号（由组委会评阅前进行编号）：
暑期数学建模竞赛 编号专用页评阅编号（由组委会评阅前进行编号）： 统一编号： 评阅编号：
多因素条件下作物施肥效果分析 摘要 本文是关于作物施肥数量与结构的优化问题，根据不同目标对施肥量与肥料搭配比例进行调整，达到各目标的最优。 首先，基于一元线性回归模型，以一种肥料作为自变量，另外两种肥料固定在第七水平，建立了六个一元回归方程，分别研究某一种肥料变化时，该肥料施肥量与产量的关系。根据散点图趋势，初步选取适当的一元函数，为了使散点图更直观准确，将原数据进行无量纲化处理，得到0到1间的值。利用eviews软件进一步对一元函数进行拟合，选取显着性最高的拟合结果，求解时，对非线性的回归方程，通过取对数将其线性化，得到结果后再将其转换成原函数形式，最终得到六个反映施肥量与产量关系的一元回归模型。为了提高六个回归方程整体的显着性，本文以三种肥料的施肥量同时作为自变量，建立三元二次回归模型，检验均通过，并具有高度的显着性，拟合效果较好。 其次，基于问题一中的一元线性回归模型与三元二次回归模型分别求解回归方程的最大值，即产量最大值。比较两个模型的结果，看出，由三元二次回归模型得到的产量更大，其中土豆与生菜产量的最大值分别为ha，ha。土豆对应的N、P、K肥料的施肥量分别为293.13kg/ha，250.0kg/ha，540.0kg/ha。生菜对应的N、P、K肥料的施肥量分别为212.06kg/ha，426.91kg/ha，665.69kg/ha。 再次，考虑到施肥的经济性，以产值和施肥费用作为自变量，以总收益作为因变量，建立收益最大化模型。分别基于反映产量与施肥量关系的一元回归模型与三元二次回归模型，进行求解。由一元回归模型得到结果，当生菜K肥施肥量无穷大时，收益也趋近于无穷大，显然不合理，本文以一元二次函数对六个回归方程重新进行拟
最优化问题的数学模型
第一章最优化问题的数学模型 数学模型是对实际问题的数学描述和概括，是进行最优化设计的基础。根据设计问题的具体要求和条件建立完备的数学模型是最优化设计成败的关键。这是因为最优化问题的计算求解完全是针对数学模型进行的。也就是说，最优化计算所得最优解实际上只是数学模型的解，至于是否是实际问题的解，则完全取决于数学模型与实际问题符合的程度。 工程设计问题通常是相当复杂的，欲建立便于求解的数学模型，必须对实际问题加以适当的抽象和简化。不同的简化方法得到不同的数学模型和计算结果，而且一个完善的数学模型，往往需要在计算求解过程中进行反复地修改和补充才能最后得到。由此可见，建立数学模型是一项重要而复杂的工作：一方面希望建立—个尽可能完善的数学模型，以求精确地表达实际问题，得到满意的设计结果；另一方面又要力求建立的数学模型尽可能简单，以方便计算求解。要想正确地协调这两方面的要求，就必须对实际问题及其相关设计理论和设计知识有深人的理解，并且善于将一个复杂的设计问题分解为多个子问题，抓住主要矛盾逐个加以解决。 本章通过几个简单的最优化设计简例，说明数学模型的一般形式、结构及其有关的基本概念。 1．1 设计简例 下面是3个最优化设计简例，可以看作几个复杂工程设计问题的子问题，虽然比较简单，但却具有一定的代表性。
例1—1 用一块边长3m的正方形薄板，在四角各裁去一个大小相同的方块，做成一 第3页个无盖的箱子，试确定如何裁剪可以使做成的箱子具有最大的容积。 解：设裁去的4个小方块的边长为x，则做成的箱子的容积为 f(x)＝x(3—2x)^2 于是，上述问题可描述为 求变量 x 使函数 f(x)＝x(3—2x)^2 极大化 这样就把该设计问题转化成为一个求函数f(x)最大值的数学问题。其中，I是待定的求解参数，称为设计变量；函数f(x)代表设计目标，称为目标函数。由于目标函数是设计变量的三次函数，并且不存在任何限制条件，故称此类问题为非线性无约束最优化问题。 根据一元函数的极值条件，令f′(x)＝0，解得x＝0．5，f(x)＝2．0，记作x*=0．5，f(x)=2．0，称为原设计问题的最优解。 例1—2 某工厂生产甲、乙两种产品，生产每种产品所需的材料、工时、用电量和可以获得的利润，以及每天能够提供的材料、工时、用电量见表1—1，试确定该厂两种产品每天的生产计划，以使得每天获得的利润最大。
数学建模优化问题
木材储运经营计划 摘要 本文针对某一木材储运公司在冬、春、夏、秋四季内进货价、出货价、储存费用、库存空间及最大销售量等预计数据进行分析，制定一个各季节的进货量和出货量计划使该公司的经营利润达到最大，可以把该问题归于将其归为求解利润最大化问题进行建模。 由于利润只直接与中间差价和销售量有关，并根据题目已知的预测量，建立一个木材储运最大利润模型，并通过运行LINGO软件编程来求解冬、春、夏、秋四季总最大利润为：5160万元。 上述木材储运最大利润模型: 是指冬、春、夏、秋前面的季节储存木材量可以在后面的季节卖，由于木材不宜久贮，所有库存木材应于每年秋末售完，反过来，后面季节的储存木材量元素不能放在前面的季节卖，因此可以把一个季节卖哪几个季节进的木材当成几个，建立一个横轴的元素和代表当前季节的木材销售量，竖轴的元素和该季节应该购进的木材量含十六个元素的二维数组，通过运用LINGO软件编程可以得到这个数组元素为： 储存量 冬/万m3春/万m3夏/万m3秋/万m3 销售量 冬100 ——— 春0 140 —— 夏20 0 180 — 秋0 0 0 160 通过简单的基本运算可以知道每个季节进货量和出货量既为该木材储运公司这年的大体经营计划。 关键词：LINGO 木材储运最大利润数组元素
一．问题重述 一个木材储运公司有很大的仓库用以储运出售木材。由于木材季度价格的变化，该公司于每季度初购进木材，一部分于本季度内出售，一部分储存起来以后。已知该公司仓库的最大储存量为20万m3，储存费用为() a+元/m3，式中7 bu a=，10 b=，u为储存时间（季度数）。已知每季度的买进卖出价及预计的销售量如下表所示： 表1. 季度买进价/元/m3卖出价/元/m3预计销售量/万m3 冬410 425 100 春430 440 140 夏460 465 200 秋450 455 160 由于木材不宜久贮，所有库存木材应于每年秋末售完。 根据上述条件建立一个模型制定一个该公司每个季节进木材量和销售木材量的大体经营计划，使这个公司获得最大的利润。 二．问题的简要分析 对于本文涉及到的问题，建立一个横方向的元素和代表当前季节的木材销售量，竖方向的元素和该季节应该购进的木材量含十六个元素的二维数组，由于冬、春、夏、秋前面的季节储存木材量可以在后面的季节卖，因此真正未知元素只有十个，而且这十个未知数的类型相同，更容易理解，如下： 表2. 冬/万m3春/万m3 夏/万m3秋/万m3储存量 销售量 冬Q11——— 春Q12Q22—— 夏Q13Q23Q33— 秋Q14Q24Q34Q44 由于假设的未知数都是销售量，因此在秋季末公司的仓库不存在储存的木材量，每个季度的进货量除了在本季度销售木材的量外，剩下的都是储存量，只要小于公司仓库的最大储存量，因此在约束条件考虑到即可。 然而市场上对该公司的需求是有限的，因此每个季度的销售量是有限，因此再在约束条件增加对每个季度的销售量的限制，然后通过数学软件编程求解即可。 三．模型的假设 1）假设公司预计销售量在各个季度几乎符合现实且预计销售量是是最大销售量； 2）假设各个季度木材的单位量的实际进价和销售价与预测价几乎符合； 3）假设每个月的库存量在该时期内的产品的单位量库存费用不变； 4）假设在该时期内储存费用大约不变； 5）假设人力财力等消耗的费用不在该问题中考虑；