优化问题的数学模型
- 格式：doc
- 大小：1001.00 KB
- 文档页数：13
一. 管理科学的定义
管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策制定的一门学科.
(1) 定量因素(2) 科学的方法(3) 辅助决策制定
二.用管理科学的方法解决问题的基本步骤.
（1） 提出问题，并根据需要收录有关数据信息。管理科学工作者向管理者咨询、鉴别所要考虑的问题以确定合理的目标，然后根据要求收集一些关键数据，并对数据作相应的分析。
（2） 建立模型，引入决策变量，确定目标函数（约束条件）。建模过程是一项创造性的工作，在处理实际问题时，一般没有一个唯一正确的模型，而是有多种不同的方案。建模是一个演进过程，从一个初始模型往往需要不断的完善渐渐演化成一个完整的数学模型。
（3） 从模型中形成一个对问题求解的算法。要在计算机上运行数学程序对模型进行求解，一般情况下能找到对模型求解的标准软件。例如，对线性规划问题已有Excel、Cplex、Lingo等标准软件求解。有时要自己编写程序。
（4） 测试模型并在必要时修正。在模型求解后，需要对模型进行检验，以保证该模型能准确反映实际问题，需要检验模型提供的解是否合理，所有主要相关因素是否已考虑，当有些条件变化时，解如何变化等。
（5） 应用模型分析问题以及提出管理建议。对模型求解并分析后，将相应的最优方案提交给管理者，由管理者做出决策。管理科学工作者并不作管理决策，其研究只是对涉及的问题进行分析并向管理者提出建议。管理者还要考虑管理科学以外的众多因素才能做出决策。
（6） 帮助实施管理决策。建议被管理者采纳以后，一旦做出管理决策一般要求帮助监督决策方案的实施。
新问题, 新模型, 新算法, 新应用.
三.优化问题的数学模型
1212max(min)(,,,)(,,)0..1,2,njnZfxxxgxxxstjm
由于,jfg是非线性函数时，此问题是非线性优化问题, 求解较复杂。我们主要讨论线性优化问题，常见的形式：混合整数规划
（1）max
0
0ZCXhYAXGYbXY取整数
其中111,,,,mnmpmnpAGbCh，不失一般性，我们假定,,,,ChAGb都是整数矩阵。
当0p时，（1）为纯整数规划，当0n时，（1）为线性规划。 下图列出若干常见线性优化问题之间的关系，见Figure 1.1
Mixed-integerprogrammmingPure-integerprogrammingMixed 0-1programminglinear programmmingIntegerknapsack0-1programmingUncapacitatedfacilitylocationFixed-changenetworkflow0-1knapsackSet coveringSet packingLinearnetworkflowTravelingsalesmanNode packingMatchingTransportationShortestpathAssignmentFigure 1.1
3.1．1 Set packing 与Node packing
（Set packing）模型：
max1{0,1}ZCXAXx 其中A是元素为0或1的矩阵
（Node packing）模型：
max1{0,1}ZCXAXx 其中A是元素为0或1的矩阵，且每行恰有两个1（没有重复行）
显然，Node packing 是Set packing特例。
对于Set packing问题，事实上是一个独立集问题，例如
1 0 0 01 1 0 01 0 1 00 1 1 1A我们按下列方式构造网络：每列对应于一个顶点，jx对应于点j，所以有四个点，按行检查，对任意i若1ilikaa，则在点l与点h之间有一条边相连。构成如图网络以后，可以看出约束1AX相当于确定顶点使得被确定的顶点之间没有边相连；而目标系数C相当于点的权重向量问题变为如何在网络确定若干个（独立的）顶点使得总权重最大的问题。而Node packing 问题中，A是0－1矩阵（每行只有两个元素是1），事实上是一个网络的边点关联矩阵，最终也可以化为与上问题类似的问题。
1234
Figure 1.2
3.2 背包问题
对于0-1背包问题（Knapsack）一般模式：
max..{0,1}ZCXAXbstx
事实上，它的求解很困难，我们不妨举个非常简单的例子。
1231231max92860720..{0,1}iZxxxxxxbstx
1x的系数比1：9，2x的系数比1：4，3x系数比为1：3，从资源分配问题角度应依次考虑123,,xxx，而事实上，最优解非常依赖于右端项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}eeeEeeieZCXstXiVX
其中()i表示关联顶点i的边的集合。（3()Om算法存在）
3．4 Linear Network Flow
,min(max)..0ijijijijijijjhjihijZxwxCstxxsx
最大流问题，运输问题，最短路问题和指派问题均为其特例。网络单纯形法。
Fixed-charge Network flow 是指弧上费用固定，与流量无关。我们要确定走哪些弧（0－1变量）。一般模型为0－1混合整数规划。
,min(max)..0,{0,1}ijijijijijijijjhjihijijZywxCystxxsxy
事实上，线性网络流（最小费用流）是上问题的特例：
在线性网络流中，ijw是单位费用，将弧(,)ijvv（容量为ijC）分解为ijC条容量为1的弧即可。
3．5无容量限制的设备选址问题（uncapacitated facility location）
一般模型：,min
..
0,{0,1}ijijiiijiijiijijjiijiZcxhyxayistxbxy这是一种混合0－1规划问题。
3．6 Node Covering
给定图(,)GVE和一个数k，是否存在一个包含k个顶点的子集1VV，使得图中每个边至少关联1V中的一个顶点？（判定问题）k的最小个数是多少？（优化问题）
（若每点都有权，求一个子集1VV总权最小，且每个边至少关联1V中的一个顶点） Independent Set 独立集问题：给定网络图(,)GVE和整数k，是否存在包含k个点的子集1V使得1V中任何两个点都不相邻（关联）？（判定问题）求最大的k是优化问题。
其它问题：哈密顿圈，货郎担问题，中国邮递员问题，适定性问题
3．7各种问题的变形问题
最大容量路、最大容量树、瓶颈运输问题（指派问题）、约束最小生成树（度约束、hop约束等）、多种物资流问题、带时间窗的最短路问题，最短路、树问题
实际应用的问题都是这些问题的变种形式，首先要判断所遇问题基本上属于哪类问题。
四. 单位模矩阵（么模矩阵）与整数解（Uni-modular）
定义：一个整数方阵B，若||1B，则称B为单位模（么模）矩阵。一个mnA矩阵，若它的任何一个非奇异子方阵都是单位模的，则称A为全单模的。
推论：A是全单模的，则A的任何r阶子式（rm）取值为0，1。
由于线性规划的基本解*1||BBXBbbB（其中*B为B的伴随矩阵）
若b是整数向量，则BX也是整数向量。因此有
定理1：若A是全单位模矩阵，对任何整数向量b都有有界多面体1(){|,0}RAXAXbX的所有顶点均为整数点，因此用单纯形法求出的最优解必为整数解。同样，可以证明当约束是不等式约束时，也有以上结论。
2(){|,0}RAXAXbX
定 理2：当A是全单位模矩阵，b是整数向量时，2()RA的所有顶点均为整数点。
定 理3：设()ijmnAa，其中0,1ija，如果A的每一列的非零元素最多有两个，且A的行可以划分为两个子集1I和2I，使得
(1) 若一列中两个非零元素的符号相同，则它们所有的行属于不同的集合1I和2I
(2) 若一列中的两个非零元素的符号不同，则它们所在的行属于同一个集合则A是全单位模
推论：
A是一个有向图的点－弧关联矩阵或A是一个无向二部图的点边关联矩阵，则A是全单位模。
例： 1432e1e2e3e4e5
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 eeeee 不是全单位模，因为2345eeee列形成的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
定理：对于关联矩阵（点弧）nmA其秩为n-1（行的个数－1）。
应用举例：（线性规划中列向量是连续1的情形）
若线性规划
min..0ZCXAXbstx
其中mnA是0－1矩阵，且满足每列中的元素是1的元素连续出现的情形，这类问题可以转化为网络最小费用流问题。现举例说明： 1432a4a3a5a6a2
