运筹学中中的数学问题及模型.ppt

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

1、第一章 运筹学中的几个数学问题及模型,本章主要介绍运筹学中的几个数学问题及模型，即 线性规划问题、运输问题、图与网络优化技术等。学习 的重点是基本概念。 1.线性规划问题及其数学模型问题 2.运输问题 3.树和最小支撑树问题 4.最短路径问题 5.网络最大流问题 6.最小费用最大流问题 7.中国邮递员问题 8. NP-完备性,数学预备知识：矩阵的基本概念及初等运算 参考文献 1.运筹学教材编写组编，运筹学，清华大学出版社，2005年6月第3版 2. 田丰、马仲番编著，图与网络流理论，科学出版社，1987年 3. 刘振宏、 蔡茂城(译)，组合最优化：算法和复杂性，清华大学出版社,1988 年第1

2、版 4. C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Printice-Hall, 1982,运筹学的性质和特点,运筹学是一门应用科学，至今还没有统一且确 切的定义。在此提出以下几个定义来说明运筹学的 性质和特点： 定义1: 为决策机构在对其控制下的业务活动进 行决策时, 提供以数量化为依据的科学方法. 特点1: 该定义强调的是科学方法,以定量化为基 础,利用数学工具.但任何决策都包含定量和定性两个 方面,而定性方面又不能简单地用数学表示,如政治、 社会等

3、因素，只有综合多种因素的决策才是全面的。 运筹学工作者的职责是为决策者提供可以量化方面 的分析，并指出那些是定性因素。,定义2：运筹学是一门应用科学，它广泛应用现 有的科学技术知识和数学方法，解决实际中提出的 专门问题，为决策者选择最优决策提供定量依据。 特点2：该定义表明运筹学具有多学科交叉的特 点，如综合应用经济学、心理学、物理学和化学中 的一些方法。 特点3：由系统的观点研究功能关系。 综上所述，运筹学的定义可以提炼为： 定义3：运筹学就是利用计划的方法和多学科专 家组成的队伍，把复杂的功能关系表示成数学模型 ，其目的是通过定量分析为决策和揭露新问题提供 数量依据。,运筹学与计算机,计算

4、机是运筹学发展的基本因素，对任何实际问 题，没有现代计算机用来产生最终结果，大多数运筹 学技术是完全不能实现的。许多大规模运筹技术的应 用只需计算机几分钟的时间，而用人工则需要很长时 间。更为重要的是计算机能快速利用某些类型的管理 信息，而没有这些信息，许多运筹设计是没有意义。 计算机是运筹学不可分割的部分和不可缺少的工 具，而且计算机方法和运筹学方法是并行发展的。预 计今后运筹学和计算机方法的分界线将会消失，并将 组成更通用、更广泛的管理科学的形式。,运筹学的工作步骤,1. 提出和形成问题：要弄清问题的目标，可能的约束，问题的可控变量以及有关参数。 2. 建立模型：把问题中可控变量、参数和目

5、标与约束之间的关系用一定的模型表示出来。 3. 求解：用数学方法将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机,解的精度要求由决策者提出。 4. 解的检验：先检验求解步骤和程序有无错误，然后检查解是否反映现实问题。 5. 解的控制：通过控制解的变化过程决定对解是否要作一定的修改。 6. 解的实施：将解用到实际中去，必须考虑到实际的问题，如向实际部门讲清楚解的用法，在实施中可能产生的问题等。 以上过程应反复进行。,1.线性规划问题及其数学模型问题,例1：某工厂在计划期内安排生产、两 种产品，已知生产单位产品所需的设备台 时、A、B两种原材料的消耗及两种产品每 件可获利润见如

6、下表1-1所示：问如何安 排计划使该工厂获利最多？,表11,解：假设 x1、x2分别表示在计划期内生产产品I、II的数量，则该计划问题可用如下数学模型表示为： 目标函数 Max Z = 2x1 +3x2 约束条件 其最优解为x1=4, x2=2, 最优值为z=14。,例2:（营养问题）某养鸡场所用的混合饲料是由 n 种配料组成。要求这种混合饲料必须含有 m 种不同的营养成份，而且要求每单位混合饲料 中第i种营养成份的含量不能低于bi(i= 1,2,m） 。已知第i种营养成份在每单位的第 j 种配料中 的含量为 aij , j = 1,2, , n，每单位的第 j 种配 料的价格为 cj 。现在

7、要求在保证营养条件的前 提下，应采用何种配方，使混合饲料的成本最 小。,解：设 xj 表示在单位混合饲料中，第 j 种配料的含量（j = 1,2, , n）, 则有如下的数学模型： Min Z = c1x1 + c2x2 + + cnxn,以上两个例子，从数学上来讲,它们的共同 特征是: (1) 每个问题都用一组决策变量(x1 , x2 , , xn)表示某一方案 ,这组未知数的值就代表一个具体的方案,通常要求这些未知数取值是非负的。 (2) 存在一定的限制条件(称为约束条件)，这些条 件都可以用关于决策变量的一组线性等式或 不等式来表示。 (3) 都有一个目标要求,并且这个目标可表示为这 组

8、决策变量的线性函数(称为目标函数),按研 究问题的不同，要求目标函数实现最大化或 最小化。,满足以上三个条件的数学模型称为线性规划数学模型。其一般形式为(1.1)和(1.2)形式。 在该模型中，方程(1.1)称为目标函数， (1.2)称为约束条件。,线性规划问题的解法,1. 对于简单的线性规划问题(只有两个决策变量或等价于两个决策变量的线性规划问题)，我们通过图解法可以对它进行求解。 2. 图解法虽然有直观、简便等优点,但是在变量个数较多（如大于等于3）时，一般就无能为力了。美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法：单纯形算法 （一种代数的方法）。,例3. 求解线

9、性规划 min z=x1+2x2+x3-x4 s.t. 2x1+4x2+x3+x4 = 6 2x1 +x4+x5 = 3 x1-x2 +x5 = 1 x1, x2, x3, x4, x5 0 解：对原问题进行初等变换，得到,min z=x1+2x2+x3-x4 s.t. x1+3x2+x3 = 4 x1+x2 +x4 = 2 x1-x2 +x5 = 1 x1, x2, x3, x4, x5 0 即 min z=2 + x1 s.t. x1+3x2 4 x1+x2 2 x1-x2 1 x1, x2 0 然后用图解法求解。求出x1，x2最优解后， 再求出x3, x4, x5 ，就得到了原问题的最优

10、解。,线性规划问题的标准型,这里我们假设 bi 0 , i = 1,2,m, 否则两端同时乘以“-1”。用矩阵向量描述就是：,其中：c = ( c1, c2, , cn )T ，X = ( x1, x2, , xn )T ，b = ( b1, b2, , bm )T , A = ( P1, P2, , Pn ) ，Pj = ( a1j, a2j, , amj )T ，0 = ( 0, 0, , 0 )T , ( j = 1, 2, , n ) 。 我们称 A 为约束方程组的系数矩阵( mn阶),一般情况下 m n , m 和n 为正整数,分别表示约束条件的个数和决策变量的个数, C 为价值向量

11、, X 为决策向量, 通常aij , bi , cj为已知常数，这里 i = 1, 2, , m , j = 1, 2, , n。,对偶问题的提出 我们将简单叙述对偶线性规划。这里的对偶是指对同以事物（或问题）从不同的角度观察，有两种不同的表述。 例如：“平面中矩形的面积与周长的关系”有下面两种表述 周长一定时，面积最大的矩形式正方形； 面积一定时，周长最小的矩形式正方形。,在前面例1中，我们讨论了工厂生产计划模 型及其解法，现从另一个角度来讨论这个问题 。 假设该工厂的决策者决定不生产产品I、II， 而将其所有资源出租或出售。这时，工厂的决 策者就要考虑给每种资源进行定价的问题。 设用 y1

12、、 y2、 y3 分别表示出租单位设备台 时的租金和出让单位原材料 A、B 的附加费。,作决策时，需要如下的比较：若一个单位 设备台时和四个单位原材料 A可以生产一件产 品I，可获利2元，那么生产每件产品I的设备台 时和原材料出租和出让的所有收入应不低于生 产一件产品I的利润。这就有： y1 + 4y2 2 ； 对于产品II同理有： 2 y2 + 4y3 3； 把工厂所有设备台时和资源都出租和出让 ，其收入应为：w = 8y1 + 16y2 + 12y3 。,从工厂的决策者来看，当然希望 w 的值越大越好；但从接受者的角度来看，他支付的越少越好。所以工厂决策者只能在满足 所有产品的单位利润条件

13、下，使其总收入尽可能地小，才能实现工厂决策者的意愿。为此需要解如下的线性规划问题：,我们称这个线性规划问题为例1线性规划问题（称之为原问题）的对偶问题。,根据上述例题可见，对于形如如下形式的线性规划问题：,我们可以马上得出 它的对偶问题：,从以上的线性规划问题和其对偶问题中，我们 可以得出：原问题的约束条件的个数 m 就是对偶问 题的变量的个数；原问题的变量的个数 n 就是对偶 问题的约束条件的个数；若原问题的目标函数是 Max 型，则对偶问题的目标函数必是 Min 型。它们 二者的最优目标函数值相等。,例4 某工厂拟用用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润及托运所受限制如下表所

14、示。问两种货物各托运多少，可使获得利润最大？ 表1-2,解：设x1、x2分别为甲、乙两种货物的托运箱数，则得到整数线性规划： Max Z=20 x1+10 x2 5x1+4x2 24 2x1+5x2 13 x1, x2 0 x1,x2 为整数 解决此整数线性规划的松驰线性规划， 得到x1=4.8, x2=0, 目标值为Z=96。（用图象 法来说明）但是整数最优解为x1=4, x2=1, 目 标值为Z*=90。,2.运输问题,例1：(运输问题）假设有 m 个生产地点,可以 供应某种物资(以后称为产地)，用 Ai 表示，i = 1,2,m；有 n 个销售地，用 Bj 表示，j = 1,2, ,n；

15、产地的产量和销售地的销售量分别 为 ai 和 bj , i = 1,2,m, j = 1,2, ,n，从 Ai 到 Bj 运输单位物资的运价为 cij ，这些数据可汇 总于如下表2-1。,在假设产销平衡的条件下，即 要求得总运费最小的调运方案。 表2-1 产销平衡表与单位运价表,解:假设 xij 表示从 Ai 到 Bj 的运量,则所求的数学 模型为:,指派问题的数学模型,在生活中经常会遇到这样的问题，如某单 位需要指派 n 个人去完成 n 项任务，每个人只 做一项工作，同时，每项工作只由一个人完成 。由于各人的专长不同，每个人完成各项任务 的效率也不同。于是产生了应指派哪一个人去 完成哪一项任务，使完成 n 项任务的总效率最 高（如所用的时间为最少）。我们把这类问题 称之为指派问题或分派问题（Assignment Problem）。,例2 :有一份中文说明书,需要译成英、日、德、 俄四 种文字，分别记作 E、J、G、R 。现有 甲、乙、丙、丁四人，他们将中文说明书翻译 成不同文字说明书所 需要的时间如表2-2所示。 问应指派何人去完成哪一项工作，使所需的总 时间最少？,表2-2,类似的有：n 项加工任务，怎样指派到 n 台机 床上分别完成的问题；n 条航线，怎样指定 n 艘船 去航行的问题，等等。对应每个指派问题, 都有类 似表2-1那样的表格，我们称之为效率矩阵或