运筹学-第01章

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是可行域顶点的充分必要条件是X是基本可行解。,求解思路

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

15、，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作为引入变量，为使新解X(1)仍为基可行解，必须使,且使x4或

16、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, 0) 取x1进基，同样，,此时，为x4退出

17、变量。新的基可行解为 X (2) =(1, 2, 0, 0, 0) 目标函数Z(2)=2+6=8 27/4 =Z(0) 此时非基变量检验数均为负，解最优,单纯形法一般步骤,1.初始基本可行解的确定（观察法）；,单纯形法一般步骤,1.初始基本可行解的确定（观察法）；,基,基本可行解,单纯形法一般步骤,2.从约束中解出基变量；,单纯形法一般步骤,3.代入目标消去基变量，得到非基变量xj的检验数 j；,单纯形法一般步骤,3.代入目标消去基变量，得到非基变量xj的检验数 j；,单纯形法一般步骤,4.判断最优； 最优性判别定理：若 是对应于B的基本可行解， j是用非基变量表示目标函数的表达式 中非基变量

18、xj的检验数，若对于一 切非基变量的角指数j均有j 0 则当前基本可行解为最优解。,对于任意可行解X，,对于基本可行解X0，,单纯形法一般步骤,5.没有有限最优解的判断； 无最优解判别定理：若 是对应于B的基本可行解， 非基变量x k的检验数k 0 , 且对于i=1,2,m 均有aik 0, 则问题没有有限最优解。,单纯形法一般步骤,6.改进目标 若k 0，则选xk进基; 用最小比值法确定xk的最大值， 使基变量xl取0值，其它基变量非负；,即xl出基，目标改善k，换基过程 若不存在, 则Z，没有有限最优解。,单纯形法一般步骤,7.主元变换（枢变换或旋转变换） xk进基， xl出基，解出新的基

19、变量,5表格单纯形法,标准型：,表格单纯形法,标准型：,表格单纯形法,表格单纯形法,基变量,检验数,最小比值列,基变量系数,右端常数,解：,表1-7,表1-9中所有j=0,且基变量中不含人工变量，最优解 X=(7/2, 3/2, 15/2, 0, 0) ; 最优值 Z=17/2.,练习1：求解线性规划,表格单纯形法,向右迭代一步,练习2：求解线性规划,表格单纯形法,没有有限最优解,算法思路,求一个初始基本可行解 是 判断基本可行解是否最优 结 束 不是 求使目标得到改善的基本可行解,是否存在？ 如何得到？,是否唯一？,如何判断？,如何改善？ 如何判断没有有限最优解？,5单纯形法进一步讨论,处理

20、方法一 大法,人造基 添加人工变量造成基 去掉人工变量,5单纯形法进一步讨论,原问题的可行解 新问题的可行解 目标值,结论：新问题的最优解中，如果人工变量均为零，则得到的解也是原问题的最优解，否则原问题无可行解,例6 大M法,最优解:X=(0,5/2,3/2,0,0,0,0) 最优值： Z= 3/2,大M法举例,所有检验数0 已经是最优解 x5=2 人工变量不为零, 表示原问题无可行解 参照图解法结果,5单纯形法进一步讨论,处理方法二 两阶段法,人造基 添加人工变量造成基 去掉人工变量,两阶段法,如果线性规划问题中的aij、bi或cj等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由

21、于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。,5单纯形法进一步讨论,第一阶段,第一阶段最优解中: 如果Z0, 则原问题没有基本可行解; 如果Z=0, 则若人工变量全为非基变量,则得到原问题的基本可行解. 否则基本可行解退化,继续迭代就可以得到基本可行解.,5单纯形法进一步讨论,第二阶段,以第一阶段最优基作为初始基本可行解,继续迭代.,第一阶段,例 6 两阶段法,第一阶段：,请注意: 第一阶段的最优解不是唯一的,第二阶段,单纯形法矩阵描述,单纯形法矩阵描述,单纯形法矩阵描述,几点注意事项,检验数的计算； 进基变量的选取；若有不止一个变量可以进基时,只取一个； 最小比值；若有不止一个最小比值时，只能选取其中之一行对应的基变量出基 ； 没有有限最优解的情况 ； 最优解是否唯一 ； 最优表中非基变量检验数等于零时,可能最优解不唯一。,线性规划及单纯形法,线性规划问题及数学模型 图解法 单纯形法原理 单纯形法计算步骤 单纯形法进一步讨论 数据包络分析 其他应用例子,数据包络分析 (Data Envelopment Analysis,DEA),6数据包络分析,根据多项投入指标和多项产出指标,利用线性规划的