运筹学绪论及第01章

《运筹学绪论及第01章》由会员分享，可在线阅读，更多相关《运筹学绪论及第01章（106页珍藏版）》请在金锄头文库上搜索。

1、运 筹 学,Operational Research ( OR ),夫运筹帷幄之中， 决胜千里之外。,运筹学定义,“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具”。大英百科全书 运筹学“用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案”中国大百科全书,运筹学定义,运筹学“主要研究经济活动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排，以达到较经济较有效

2、地使用人力物力”辞海 运筹学“应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理”。中国企业管理百科全书,运筹学定义,运筹学所研究的，通常是在必须分配稀缺资源的条件下，科学地决定如何最佳地设计和运营人机系统,对象：人机系统,条件：资源稀缺,方法：模型化，定量化,特点：最优化,目的：决策支持,运筹学简史,起源：古代战争、娱乐、建设 田忌赛马 丁渭修皇宫 学科产生：第二次世界大战 问题：合理利用稀缺战争资源保护自己、消灭敌人 1938年7月，波得塞雷达站的负责人罗伊用Operational Research命名防空作战系统

3、运行的研究 1940年9月英国成立了由物理学家布莱克特(Blackett)领导的第一个运筹学小组 l 942年美国和加拿大也都相继成立运筹学小组,运筹学简史,反潜艇战 库普曼(Koopmans)搜索论 肖克莱(Shockley) 对策论 商船编队和舰队护航 扩展：战后用于民用事业 成型：各个分支成熟 成熟：计算机、信息技术结合 发展：学科结合、渗透 应用广度和深度、方法和算法的完善,运筹学模型,特点：,系统的整体观念,多学科的综合,模型方法的应用,符号语言、便于交流,事前分析、减少失误,抽象反映实际、突出共性,优点：,确定目标，明确约束 抓主要矛盾、舍次要矛盾 选择模型、设定变量 描述约束和目

4、标、确定参数 选择求解方法、求解问题 灵敏度分析、评价 汇总、解释结果、报告,运筹学方法论,学科主要分支,规划理论 线性规划 非线性规划 运输问题 整数规划 动态规划 目标规划 图论与网络理论 排队论 存储论 决策论 对策论 冲突分析 可靠性理论 计划协调技术 图解协调技术,第一章线性规划及单纯形法,线性规划及单纯形法,线性规划问题及数学模型 图解法 单纯形法原理 单纯形法计算步骤 单纯形法进一步讨论 数据包络分析 其他应用例子,1线性规划问题,问题的提出 线性规划问题的数学模型 线性规划概念和模型,问题的提出,例1 美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A，B的台时、

5、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润为最大。 表1-1,数学模型,例1中先用变量x1和x2分别表示美佳公司制造家电和的数量。这时该公司可获取的利润为(2x1+x2)元，令z=2x1+x2，因问题中要求获取的利润为最大，即max z。 z是该公司能获取的利润的目标值，它是变量x1，x2的函数，称为目标函数。 x1，x2的取值受到设备A、B和调试工序能力的限制，用于描述限制条件的数学表达式称为约束条件。 由此例1的数学模型可表为：,数学模型,max: maximize的缩写， “最大化”， s.t. subj

6、ect to的缩写， “受限制于”,问题的提出,例2 捷运公司在下一年度的14月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。,数学模型,例2中若用变量xij表示捷运公司在第i(i=1,4)个月初签订的租借期为j(j=1,4)个月的仓库面积的合同。因5月份起该公司不需要租借仓

7、库，故x24，x33，x34，x42，x43，x44均为零。该公司希望总的租借费用为最小，故有如下数学模型：,min：minimize ， “最小化”,概念和模型,定义： 对于求取一组变量xj(j=1,2,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。,max（或min）,概念和模型,一般形式：,max（或min）,目标函数,约束条件,非负约束,称为决策变量,称为价值系数或目标函数系数,称为资源常数或约束右端常数,称为技术系数或约束系数,概念和模型,紧缩形式：,max（或min）,概念和模型,矩阵形式：,max（或min）,称为决策变量向量,称为

8、价值系数向量或目标函数系数向量,称为资源常数向量或约束右端常数向量,称为技术系数或约束系数矩阵,标准形式,标准型的主要特征： 目标最大； 约束等式； 变量非负； 右端非负。,标准型,标准型的紧缩形式：,标准型的矩阵形式：,标准型,标准型的向量形式：,其中：,标准化,把一般的LP化成标准型的过程称为线性规划问题的标准化 方法： 1 目标标准化 min Z 等价于 max ( - Z ) max Z=-cjxj 2 化约束为等式 加松弛变量、减剩余变量 3 变量非负化 做变换 或 4 右端非负,标准化,标准化举例（例3）：,线性规划及单纯形法,线性规划问题及数学模型 图解法 单纯形法原理 单纯形法

9、计算步骤 单纯形法进一步讨论 数据包络分析 其他应用例子,2图解法,1什麽是图解法？ 线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。 求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。,图解法,2. 图解法(例1),运用图解法，以求出最优生产计划（最优解）。,图解法,由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。,1.建立平面直角坐标系，标出坐标原点, 坐标轴的指向和单位长度。 2.对约束条件加以图解，找出可行域。 3.画出目标函数等值线。 4.结合目标函数的要求求出最优解。

10、,图 解 法,图解法,(a)可行域有界 (b)可行域有界 (c)可行域无界 唯一最优解 多个最优解 唯一最优解,(d)可行域无界 (e)可行域无界 (f)可行域为空集 多个最优解 目标函数无界 无可行解,线性规划及单纯形法,线性规划问题及数学模型 图解法 单纯形法原理 单纯形法计算步骤 单纯形法进一步讨论 数据包络分析 其他应用例子,3单纯形法原理,线性规划问题的解的概念 凸集及其顶点 几个基本定理,解 的 概 念,可行解： 变量满足所有约束条件的一组值 可行解集： 所有可行解构成的集合 可行域： 可行解集构成n维空间的区域,线性规划问题,解的概念,最优解： 使得目标函数达到最优的可行解 最优

11、值： 最优解对应的目标函数值 目的： 求最优解和最优值 求解方法： 单纯形法,解的概念,先研究AX=b 设 系数矩阵A是mn矩阵，秩为m， B是A中mm阶非奇异子矩阵（即|B|0），则称B是线性规划问题 的一个基。 B 是由m个线性独立的列向量组成,基向量,基变量,非基变量： 其余变量,解的概念,AX=BXB+NXN=b 令 非基变量XN=0 得BXB=b 和特解XB =B-1b 结合XN=0 称为对应于B的基本解； 基本解个数=基的个数Cnm 基可行解 可行的基本解 XB0 XN=0 可行基：对应于基可行解的基,A=（B | N）,解的概念,最优基： 对应的基本可行解也是最优 基本可行解个数

12、基的个数Cnm 基本可行解的非零分量均为正分量， 其正分量个数 m。 退化的基本可行解： 基本可行解的非零分量个数小于m时，也就是在基本可行解中一个或多于一个的基变量取零值时,凸 集 及 其 顶 点,1、基本概念： 凸集设K是n维欧氏空间的一个点集，若任意两点X（1）K，X（2）K的连线上的一切点： X（1）+（1-）X（2） K （01），则称K为凸集。,凸 集 的 概 念,顶点设K是凸集，XK；若K中不存在两个不同的点X（1） K，X（2） K 使 X=X（1）+（1-）X（2） （01） 则称X为K的一个顶点（也称为极点或角点）。,凸 集 的 概 念,凸集,凸集,不是凸集,顶点,基 本

13、定 理,若线性规划问题有最优解，一定存在一个基可行解（可行域顶点）是最优解。,定理1,引理,定理2,定理3,若线性规划问题存在可行解，则该问题的可行解集（即可行域）是凸集。,线性规划问题的可行解x(x1, x2, xn)为基可行解的充要条件是x的正分量所对应的系数列向量是线性独立的。,线性规划问题的基可行解x对应线性规划问题可行域(凸集)的顶点,解的几何意义,猜想1 线性规划的可行域是凸集； 猜想2 最优解若存在，则可以在可行域的顶点上得到； 猜想3 可行域的顶点的个数是有限的； 猜想4 若有两个最优解，则其连线上的点也是最优解，即最优解有无穷多个 猜想5 对于标准型的线性规划X是可行域顶点的

14、充分必要条件是X是基本可行解。,求解思路,求一个初始基本可行解 是 判断基本可行解是否最优 结 束 不是 求使目标得到改善的基本可行解,是否存在？ 如何得到？,是否唯一？,如何判断？,如何改善？ 如何判断没有有限最优解？,线性规划及单纯形法,线性规划问题及数学模型 图解法 单纯形法原理 单纯形法计算步骤 单纯形法进一步讨论 数据包络分析 其他应用例子,4 单纯形法 迭代原理,单纯形方法引例 单纯形法的一般描述 表格单纯形法 一般问题的处理 单纯形法矩阵描述 几点注意事项,单纯形方法引例,用单纯形法的思想求解线性规划问题：,单纯形方法引例,例,基本解（0，0，0，3，9）也是可行的,单纯形方法引

15、例,例,初始基本可行解X(0)=（0，0，0，3，9） 含义： 不生产任何产品，工时剩余为3，材料剩余为9，利润为 Z(0)=0 初始基本可行解是否最优解 ? 是否可以生产某种产品使目标提高？ 当x1（或x2 , x3）增加一个单位时，会使目标增加2（或3）单位,单纯形方法引例,例,初始基本可行解X(0)= （0，0，0，3，9） 当x1（或x2 , x3）增加一个单位时，会使目标增加2（或3）单位 考虑将x1（或x2 , x3）并为非零变量， x2 , x3价值系数加大，将x2变为基变量引入变量。,单纯形方法引例,例,初始基本可行解X(0)= （0，0，0，3，9） 当x2作为引入变量，为使

16、新解X(1)仍为基可行解，必须使,且使x4或x5中有一个等于零退出变量,（1-1）,单纯形方法引例,例,由(1-1)第四、第五式，得,为使新解X(1)为基可行解,此时，变为零， x5为退出变量 新的基可行解为X (1) =(0, 9/4, 0, 3/4, 0) 目标函数值Z(1)=27/4 Z(0),单纯形方法引例,例,系数列向量,此时，进一步分析引入x1或x3是否会更好？引入哪一个更好？,单纯形方法引例,首先考虑引入x1 ，由于,计算增加单位x1所创增的净经济价值,同理，可计算增加单位x3所创增的净经济价值,检验数,单纯形方法引例,例,基本可行解X (1) =(0, 9/4, 0, 3/4,