优化问题的数学模型

《优化问题的数学模型》由会员分享，可在线阅读，更多相关《优化问题的数学模型（13页珍藏版）》请在金锄头文库上搜索。

1、一. 管理科学的定义 管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策制定的一门学科. (1) 定量因素(2) 科学的方法(3) 辅助决策制定二.用管理科学的方法解决问题的基本步骤.（1） 提出问题，并根据需要收录有关数据信息。管理科学工作者向管理者咨询、鉴别所要考虑的问题以确定合理的目标，然后根据要求收集一些关键数据，并对数据作相应的分析。（2） 建立模型，引入决策变量，确定目标函数（约束条件）。建模过程是一项创造性的工作，在处理实际问题时，一般没有一个唯一正确的模型，而是有多种不同的方案。建模是一个演进过程，从一个初始模型往往需要不断的完善渐渐演化成一个完整的数学模型

2、。（3） 从模型中形成一个对问题求解的算法。要在计算机上运行数学程序对模型进行求解，一般情况下能找到对模型求解的标准软件。例如，对线性规划问题已有Excel、Cplex、Lingo等标准软件求解。有时要自己编写程序。（4） 测试模型并在必要时修正。在模型求解后，需要对模型进行检验，以保证该模型能准确反映实际问题，需要检验模型提供的解是否合理，所有主要相关因素是否已考虑，当有些条件变化时，解如何变化等。（5） 应用模型分析问题以及提出管理建议。对模型求解并分析后，将相应的最优方案提交给管理者，由管理者做出决策。管理科学工作者并不作管理决策，其研究只是对涉及的问题进行分析并向管理者提出建议。管理者

3、还要考虑管理科学以外的众多因素才能做出决策。（6） 帮助实施管理决策。建议被管理者采纳以后，一旦做出管理决策一般要求帮助监督决策方案的实施。新问题, 新模型, 新算法, 新应用.三.优化问题的数学模型 由于是非线性函数时，此问题是非线性优化问题, 求解较复杂。我们主要讨论线性优化问题，常见的形式：混合整数规划（1）其中，不失一般性，我们假定都是整数矩阵。当时，（1）为纯整数规划，当时，（1）为线性规划。下图列出若干常见线性优化问题之间的关系，见Figure 1.13.11 Set packing 与Node packing（Set packing）模型： 其中A是元素为0或1的矩阵（Node

4、packing）模型： 其中A是元素为0或1的矩阵，且每行恰有两个1（没有重复行）显然，Node packing 是Set packing特例。对于Set packing问题，事实上是一个独立集问题，例如我们按下列方式构造网络：每列对应于一个顶点，对应于点，所以有四个点，按行检查，对任意若，则在点与点之间有一条边相连。构成如图网络以后，可以看出约束相当于确定顶点使得被确定的顶点之间没有边相连；而目标系数C相当于点的权重向量问题变为如何在网络确定若干个（独立的）顶点使得总权重最大的问题。而Node packing 问题中，A是01矩阵（每行只有两个元素是1），事实上是一个网络的边点关联矩阵，最终

5、也可以化为与上问题类似的问题。Figure 1.23.2 背包问题对于0-1背包问题（Knapsack）一般模式：事实上，它的求解很困难，我们不妨举个非常简单的例子。的系数比1：9，的系数比1：4，系数比为1：3，从资源分配问题角度应依次考虑，而事实上，最优解非常依赖于右端项。当时，最优解为（1，0，0）；当时，最优解为（0，1，0）；当时，最优解为（1，1，0）；当时，最优解为（0，0，1）；没有体现优先，不同于线性规划。33 Matching（赋权图）匹配问题在网络中，一个匹配是指一些边集使得没有两边相关联。最大赋权匹配问题，寻找一个匹配使得总权最大。最大基数匹配问题，（假定每条边权为1）

6、，找出边数最多的匹配。指派问题事实上是二部图的匹配问题。（注：二部图是指可以把图中顶点分为两个部分，每一部分之间没有连接）一般模型 其中表示关联顶点的边的集合。（算法存在）34 Linear Network Flow 最大流问题，运输问题，最短路问题和指派问题均为其特例。网络单纯形法。Fixed-charge Network flow 是指弧上费用固定，与流量无关。我们要确定走哪些弧（01变量）。一般模型为01混合整数规划。事实上，线性网络流（最小费用流）是上问题的特例：在线性网络流中，是单位费用，将弧（容量为）分解为条容量为1的弧即可。35无容量限制的设备选址问题（uncapacitated

7、 facility location）一般模型：这是一种混合01规划问题。36 Node Covering 给定图和一个数，是否存在一个包含个顶点的子集，使得图中每个边至少关联中的一个顶点？（判定问题）的最小个数是多少？（优化问题）（若每点都有权，求一个子集总权最小，且每个边至少关联中的一个顶点）Independent Set 独立集问题：给定网络图和整数，是否存在包含个点的子集使得中任何两个点都不相邻（关联）？（判定问题）求最大的是优化问题。其它问题：哈密顿圈，货郎担问题，中国邮递员问题，适定性问题37各种问题的变形问题最大容量路、最大容量树、瓶颈运输问题（指派问题）、约束最小生成树（度约束

8、、hop约束等）、多种物资流问题、带时间窗的最短路问题，最短路、树问题实际应用的问题都是这些问题的变种形式，首先要判断所遇问题基本上属于哪类问题。四. 单位模矩阵（么模矩阵）与整数解（Uni-modular）定义：一个整数方阵B，若，则称B为单位模（么模）矩阵。一个矩阵，若它的任何一个非奇异子方阵都是单位模的，则称A为全单模的。推论：A是全单模的，则A的任何阶子式（）取值为0，。由于线性规划的基本解（其中为B的伴随矩阵）若b是整数向量，则也是整数向量。因此有定理1：若A是全单位模矩阵，对任何整数向量b都有有界多面体的所有顶点均为整数点，因此用单纯形法求出的最优解必为整数解。同样，可以证明当约束

9、是不等式约束时，也有以上结论。定 理2：当A是全单位模矩阵，b是整数向量时，的所有顶点均为整数点。定 理3：设，其中，如果A的每一列的非零元素最多有两个，且A的行可以划分为两个子集和，使得(1) 若一列中两个非零元素的符号相同，则它们所有的行属于不同的集合和(2) 若一列中的两个非零元素的符号不同，则它们所在的行属于同一个集合则A是全单位模推论：A是一个有向图的点弧关联矩阵或A是一个无向二部图的点边关联矩阵，则A是全单位模。例：Figure 1.3点边关联矩阵 不是全单位模，因为列形成的4阶子式为2。事实上，我们有定理: 无向图的点边关联矩阵是全单位模的充要条件是该图为二部图。关联矩阵（点弧）

10、Figure 14定理：对于关联矩阵（点弧）其秩为n-1（行的个数1）。应用举例：（线性规划中列向量是连续1的情形）若线性规划其中是01矩阵，且满足每列中的元素是1的元素连续出现的情形，这类问题可以转化为网络最小费用流问题。现举例说明： 加剩余变量Y变为（并增加一行）对A作行变换（每行减去上一行）得此时，每列恰有两个非零元素（一个1，一个1）问题化为如下最小费用流问题：发点第1点 发量收量5第2点 发量收量7收点第3，4，5点 分别为2，4，6五. 算法复杂性a) 多项式算法问题算法的复杂性随着输入规模的增加而多项式地增加，或者有一个多项式的上界。例如，问题的规模为n，算法的复杂性为或等，指数

11、算法（复杂性，最坏的情况）。问题的规模输入时所需要的符号数目，例如线性规划问题中A，B，C所需要的符号数目。b) 优化问题与判定问题 对于一个给定的最优化问题，可以定义一个密切相关的判定问题，即一个能用是或否回答的问题。例如覆盖问题、匹配问题等，线性规划问题转化为不等式是否存在可行解。c) P类问题 给定每个问题的实例，我们有多项式时间算法得出答案是是还是不是。d) NP问题 如果X是判定问题的一个答案为“是”的实例，则存在一个对X 的一个多项式时间为界验证，使得能在多项式时间内验证这个证明的真实性；例：求网络图中的最大团问题，的图为V的一个子集（其中任意两点完全连接），最大团问题是找出包含顶

12、点数最多的团（clique），这是一个优化问题。判定问题为：已知图和整数，G中有个点团吗？由于还没有找到多项式时间算法求解此问题，所以不知道此问题是否在P类问题中，一个方法是找出所有个包含个顶点的子集，但是这是指数级算法，人们没有多项式算法。但是此问题是NP类，因为假定给定团的一个答案是“是”实例，我们很容易检验：首先看是否有个点，再看任意两点是否连接。例：整数线性规划（略）判定问题：已知整数矩阵A和m维整数向量，存在维整数向量X，使及吗？显然判定问题是NP的。定理：即P是NP的子集。（略）e) 多项式时间归纳法（转换）两个判定问题，如果多项式归结到，则当有多项式算法时，也有多项式时间算法。f

13、) NPComplete（NP完备类）定义：一个判定问题称为是NP完备，如果所有其他的NP问题都能多项式地归纳到A。对于NP完备类的问题A，有一个令人生畏的性质，若A有有效算法（多项式算法）则所有NP问题也有有效算法。要证明一个问题是NP完备，必须证明（1） 该问题是NP问题（2）所有其它NP问题可以多项式归纳到该问题。g) 常见的NP完备问题有成千上万个NP完备问题，如：整数线性规划、团、货郎担问题、适定性问题、点覆盖、独立集、哈密顿圈问题、01背包问题。事实上要证明一个问题是NP完备的转化为要证明：（1） 该问题是NP的（2） 有一个已知的NP完备问题可以多项式时间转化为该问题。h) NP

14、困难问题有时我们能证明所有NP问题多项式归结到某问题A，但不能证明，此时称A为NP困难问题。i) 纯整数规划问题有多项式时间算法，当且仅当01整数规划问题有多项式时间算法。01规划是特例显然成立；若01规划有多项式算法（充分性） 事实上，纯整数规划可以重新写为一个等价01规划，由于纯整数规划最优解分量有界M，令，这样纯整数规划化为01规划问题。j) 货郎担问题的整数规划模型 考虑村庄的货郎担问题，分别用0，1，2,，n,城市间距离为，对每一弧我们指定变量，当弧在环游线上时，1；当弧不在环游线上时，1。（无非负限制实变量）Greedy算法（每次挑最好的候选者，直到不能送为止） 最大权森林问题（森

15、林是无圈子图） 最小支撑树问题拟阵用greedy算法都能求出最优解。k) Sterner树问题Sterner树问题最小生成树的变种。给定网络，是一个顶点子集，我们希望找一个包含中所有顶点的最小费用树（不必是的支撑树）。该问题是NP困难问题。l) 成本效益均衡模型许多优化问题是两个以上目标优化问题，如要求成本最低和效益最高，或回报高而风险低。一般是限制其中一个目标（作为约束条件）求另一个目标最优。类似地，有n个目标时，限制n-1个目标（作为约束条件），求其中一个最优。适定性问题（Satisfiability）：布尔变量的真与假，逻辑运算“或”，“与”分别用“”“”表示，表示的否，布尔表达式是用算术运算符号连接起来的变量所构成的代数表示式。例1：是一个布尔表示式。给定每个变量一个值，与计算代数表达式一样，我们可以计算布尔表达式，例如若给定“真”