运筹学所有内容.ppt
《运筹学所有内容.ppt》由会员分享,可在线阅读,更多相关《运筹学所有内容.ppt(486页珍藏版)》请在三一办公上搜索。
1、运 筹 学(Operations Research),运筹学简述,运筹学(Operations Research)系统工程的最重要的理论基础之一,在美国有人把运筹学称之为管理科学(Management Science)。运筹学所研究的问题,可简单地归结为一句话:“依照给定条件和目标,从众多方案中选择最佳方案”故有人称之为最优化技术。,运筹学简述,运筹学的历史,“运作研究(Operational Research)小组”:解决复杂的战略和战术问题。例如:如何合理运用雷达有效地对付德军德空袭对商船如何进行编队护航,使船队遭受德国潜艇攻击时损失最少;在各种情况下如何调整反潜深水炸弹的爆炸深度,才能增
2、加对德国潜艇的杀伤力等。,运筹学的主要内容,数学规划(线性规划、整数规划、目标规划、动态规划等)图论存储论排队论对策论排序与统筹方法决策分析,本课程的特点和要求,先修课:高等数学,基础概率、线性代数特点:系统整体优化;多学科的配合;模型方法的应用运筹学的研究的主要步骤:,运筹学在工商管理中的应用,运筹学在工商管理中的应用涉及几个方面:生产计划 运输问题 人事管理 库存管理 市场营销 财务和会计另外,还应用于设备维修、更新和可靠性分析,项目的选择与评价,工程优化设计等。,运筹学在工商管理中的应用,Interface上发表的部分获奖项目,“管理运筹学”软件介绍,“管理运筹学”2.0版包括:线性规划
3、、运输问题、整数规划(0-1整数规划、纯整数规划和混合整数规划)、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法,共15个子模块。,Chapter1 线性规划(Linear Programming),LP的数学模型 图解法 单纯形法 单纯形法的进一步讨论人工变量法 LP模型的应用,本章主要内容:,线性规划问题的数学模型,1.规划问题,生产和经营管理中经常提出如何合理安排,使人力、物力等各种资源得到充分利用,获得最大的效益,这就是规划问题。,线性规划通常解决下列两类问题:,(1)当任务或目标确定后,如何统筹兼顾,合理安排
4、,用最少的资源(如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标,(2)在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多、利润最大.),线性规划问题的数学模型,例1.1 如图所示,如何截取x使铁皮所围成的容积最大?,线性规划问题的数学模型,例1.2 某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定,单件产品在不同设备上加工所需要的台时如下表所示,企业决策者应如何安排生产计划,使企业总的利润最大?,线性规划问题的数学模型,解:设x1、x2分别为甲、乙两种产品的产量,则数学模型为:,线性规划问题的数学模型,2.线
5、性规划的数学模型由三个要素构成,决策变量 Decision variables 目标函数 Objective function约束条件 Constraints,其特征是:(1)问题的目标函数是多个决策变量的线性函数,通常是求最大值或最小值;(2)问题的约束条件是一组多个决策变量的线性不等式或等式。,怎样辨别一个模型是线性规划模型?,线性规划问题的数学模型,目标函数:,约束条件:,3.线性规划数学模型的一般形式,简写为:,线性规划问题的数学模型,向量形式:,其中:,线性规划问题的数学模型,矩阵形式:,其中:,线性规划问题的数学模型,3.线性规划问题的标准形式,特点:(1)目标函数求最大值(有时求
6、最小值)(2)约束条件都为等式方程,且右端常数项bi都大于或等于零(3)决策变量xj为非负。,线性规划问题的数学模型,(2)如何化标准形式,目标函数的转换,如果是求极小值即,则可将目标函数乘以(-1),可化为求极大值问题。,也就是:令,可得到上式。,即,若存在取值无约束的变量,可令 其中:,变量的变换,线性规划问题的数学模型,约束方程的转换:由不等式转换为等式。,称为松弛变量,称为剩余变量,变量 的变换,可令,显然,线性规划问题的数学模型,例1.3 将下列线性规划问题化为标准形式,用 替换,且,解:()因为x3无符号要求,即x3取正值也可取负值,标准型中要求变量非负,所以,线性规划问题的数学模
7、型,(2)第一个约束条件是“”号,在“”左端加入松驰变量x4,x40,化为等式;(3)第二个约束条件是“”号,在“”左端减去剩余变量x5,x50;(4)第3个约束方程右端常数项为-5,方程两边同乘以(-1),将右端常数项化为正数;(5)目标函数是最小值,为了化为求最大值,令z=-z,得到max z=-z,即当z达到最小值时z达到最大值,反之亦然;,线性规划问题的数学模型,标准形式如下:,线性规划问题的数学模型,4.线性规划问题的解,线性规划问题,求解线性规划问题,就是从满足约束条件(2)、(3)的方程组中找出一个解,使目标函数(1)达到最大值。,线性规划问题的数学模型,可行解:满足约束条件、的
8、解为可行解。所有可行解的集合为可行域。最优解:使目标函数达到最大值的可行解。基:设A为约束条件的mn阶系数矩阵(mn),其秩为m,B是矩阵A中m阶满秩子矩阵(B0),称B是规划问题的一个基。设:,称 B中每个列向量Pj(j=1 2 m)为基向量。与基向量Pj 对应的变量xj 为基变量。除基变量以外的变量为非基变量。,线性规划问题的数学模型,基解:某一确定的基B,令非基变量等于零,由约束条件方程解出基变量,称这组解为基解。在基解中变量取非0值的个数不大于方程数m,基解的总数不超过 基可行解:满足变量非负约束条件的基本解,简称基可行解。可行基:对应于基可行解的基称为可行基。,线性规划问题的数学模型
9、,例1.4 求线性规划问题的所有基矩阵。,解:约束方程的系数矩阵为25矩阵,r(A)=2,2阶子矩阵有10个,其中基矩阵只有9个,即,图解法,线性规划问题的求解方法,一 般 有两种方法,图 解 法单纯形法,两个变量、直角坐标三个变量、立体坐标,适用于任意变量、但必需将一般形式变成标准形式,下面我们分析一下简单的情况 只有两个决策变量的线性规划问题,这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。,图解法,max Z=2X1+X2 X1+1.9X2 3.8 X1-1.9X2 3.8s.t.X1+1.9X2 10.2 X1-1.9X2-3.8 X
10、1,X2 0,例1.5 用图解法求解线性规划问题,图解法,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1-1.9X2=-3.8(),X1+1.9X2=10.2(),4=2X1+X2,20=2X1+X2,17.2=2X1+X2,11=2X1+X2,Lo:0=2X1+X2,(7.6,2),D,max Z,min Z,此点是唯一最优解,且最优目标函数值 max Z=17.2,可行域,max Z=2X1+X2,图解法,max Z=3X1+5.7X2,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1-1.9X2=-3.8(),X1+1.9
11、X2=10.2(),(7.6,2),D,L0:0=3X1+5.7X2,max Z,(3.8,4),34.2=3X1+5.7X2,蓝色线段上的所有点都是最优解这种情形为有无穷多最优解,但是最优目标函数值max Z=34.2是唯一的。,可行域,图解法,min Z=5X1+4X2,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1+1.9X2=10.2(),D,L0:0=5X1+4X2,max Z,min Z,8=5X1+4X2,43=5X1+4X2,(0,2),可行域,此点是唯一最优解,图解法,2,4,6,x1,x2,2,4,6,无界解(无最优解),max Z=x1+
12、2x2,例1.6,x1+x2=4(),x1+3x2=6(),3x1+x2=6(),max Z,min Z,x1,x2,O,10,20,30,40,10,20,30,40,50,50,无可行解(即无最优解),max Z=3x1+4x2,例1.7,图解法,学习要点:1.通过图解法了解线性规划有几种解的形式(唯一最优解;无穷多最优解;无界解;无可行解)2.作图的关键有三点:(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动,单纯形法基本原理,凸集:如果集合C中任意两个点X1、X2,其连线上的所有点也都是集合C中的点,称C为凸集。,单纯形法基本原理,定理1:若线性
13、规划问题存在可行解,则该问题的可行域是凸集。定理2:线性规划问题的基可行解X对应可行域(凸集)的顶点。定理3:若问题存在最优解,一定存在一个基可行解是最优解。(或在某个顶点取得),单纯形法的计算步骤,单纯形法的思路,找出一个初始可行解,是否最优,转移到另一个基本可行解(找出更大的目标函数值),最优解,是,否,循环,核心是:变量迭代,结束,单纯形法的计算步骤,单纯形表,单纯形法的计算步骤,例1.8 用单纯形法求下列线性规划的最优解,解:1)将问题化为标准型,加入松驰变量x3、x4则标准型为:,单纯形法的计算步骤,2)求出线性规划的初始基可行解,列出初始单纯形表。,检验数,单纯形法的计算步骤,3)
14、进行最优性检验,如果表中所有检验数,则表中的基可行解就是问题的最优解,计算停止。否则继续下一步。,4)从一个基可行解转换到另一个目标值更大的基可行解,列出新的单纯形表,确定换入基的变量。选择,对应的变量xj作为换入变量,当有一个以上检验数大于0时,一般选择最大的一个检验数,即:,其对应的xk作为换入变量。确定换出变量。根据下式计算并选择,选最小的对应基变量作为换出变量。,单纯形法的计算步骤,用换入变量xk替换基变量中的换出变量,得到一个新的基。对应新的基可以找出一个新的基可行解,并相应地可以画出一个新的单纯形表。5)重复3)、4)步直到计算结束为止。,单纯形法的计算步骤,换入列,bi/ai2,
15、ai20,40,10,换出行,将3化为1,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5/3,0,4/3,乘以1/3后得到,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1,单纯形法的计算步骤,例1.9 用单纯形法求解,解:将数学模型化为标准形式:,不难看出x4、x5可作为初始基变量,列单纯形表计算。,单纯形法的计算步骤,20,x2,2,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,9,0,2,25,60,x1,1,1,0,17/3,1/3,1,25,0,1,28/9,-1/9,2/3,35/3,0,0,-98/9
16、,-1/9,-7/3,单纯形法的计算步骤,学习要点:1.线性规划解的概念以及3个基本定理2.熟练掌握单纯形法的解题思路及求解步骤,单纯形法的进一步讨论人工变量法,人工变量法:前面讨论了在标准型中系数矩阵有单位矩阵,很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵,为了得到一组基向量和初基可行解,在约束条件的等式左端加一组虚拟变量,得到一组基变量。这种人为加的变量称为人工变量,构成的可行基称为人工基,用大M法或两阶段法求解,这种用人工变量作桥梁的求解方法称为人工变量法。,单纯形法的进一步讨论人工变量法,例1.10 用大M法解下列线性规划,解:首先将数学模型化为标准形式,系数矩阵中不存
17、在单位矩阵,无法建立初始单纯形表。,单纯形法的进一步讨论人工变量法,故人为添加两个单位向量,得到人工变量单纯形法数学模型:,其中:M是一个很大的抽象的数,不需要给出具体的数值,可以理解为它能大于给定的任何一个确定数值;再用前面介绍的单纯形法求解该模型,计算结果见下表。,单纯形法的进一步讨论人工变量法,单纯形法的进一步讨论人工变量法,解的判别:1)唯一最优解判别:最优表中所有非基变量的检验数非零,则线 规划具有唯一最优解。2)多重最优解判别:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解(或无穷多最优解)。3)无界解判别:某个k0且aik(i=1,2,m)则线性规划具有无界解。4)
18、无可行解的判断:当用大M单纯形法计算得到最优解并且存在Ri0时,则表明原线性规划无可行解。5)退化解的判别:存在某个基变量为零的基本可行解。,单纯形法的进一步讨论人工变量法,单纯性法小结:,A,线性规划模型的应用,一般而言,一个经济、管理问题凡是满足以下条件时,才能建立线性规划模型。,要求解问题的目标函数能用数值指标来反映,且为线性函数 存在着多种方案 要求达到的目标是在一定条件下实现的,这些约束可用线性等式或不等式描述,线性规划在管理中的应用,人力资源分配问题,例1.11 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示:,设司机和乘务人员分别在各时间段开始时上班,并连续工
19、作8小时,问该公交线路应怎样安排司机和乘务人员,即能满足工作需要,又使配备司机和乘务人员的人数减少?,线性规划在管理中的应用,解:设xi表示第i班次时开始上班的司机和乘务人员人数。,此问题最优解:x150,x220,x350,x40,x520,x610,一共需要司机和乘务员150人。,线性规划在管理中的应用,2.生产计划问题,某厂生产、三种产品,都分别经A、B两道工序加工。设A工序可分别在设备A1和A2上完成,有B1、B2、B3三种设备可用于完成B工序。已知产品可在A、B任何一种设备上加工;产品可在任何规格的A设备上加工,但完成B工序时,只能在B1设备上加工;产品只能在A2与B2设备上加工。加
20、工单位产品所需工序时间及其他各项数据如下表,试安排最优生产计划,使该厂获利最大。,线性规划在管理中的应用,线性规划在管理中的应用,解:设xijk表示产品i在工序j的设备k上加工的数量。约束条件有:,线性规划在管理中的应用,目标是利润最大化,即利润的计算公式如下:,带入数据整理得到:,线性规划在管理中的应用,因此该规划问题的模型为:,线性规划在管理中的应用,3.套裁下料问题,例:现有一批某种型号的圆钢长8米,需要截取2.5米长的毛坯100根,长1.3米的毛坯200根。问如何才能既满足需要,又能使总的用料最少?,解:为了找到一个省料的套裁方案,必须先设计出较好的几个下料方案。其次要求这些方案的总体
21、能裁下所有各种规格的圆钢,以满足对各种不同规格圆钢的需要并达到省料的目的,为此可以设计出4种下料方案以供套裁用。,线性规划在管理中的应用,设按方案、下料的原材料根数分别为xj(j=1,2,3,4),可列出下面的数学模型:,线性规划在管理中的应用,4.配料问题,例:某人每天食用甲、乙两种食物(如猪肉、鸡蛋),其资料如下:问两种食物各食用多少,才能既满足需要、又使总费用最省?,线性规划在管理中的应用,解:设Xj 表示Bj 种食物用量,Chapter2 对偶理论(Duality Theory),线性规划的对偶模型对偶性质对偶问题的经济解释影子价格对偶单纯形法,本章主要内容:,线性规划的对偶模型,设某
22、工厂生产两种产品甲和乙,生产中需4种设备按A,B,C,D顺序加工,每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表:,产品数据表,问:充分利用设备机时,工厂应生产甲和乙型产品各多少件才能获得最大利润?,1.对偶问题的现实来源,线性规划的对偶模型,解:设甲、乙型产品各生产x1及x2件,则数学模型为:,反过来问:若厂长决定不生产甲和乙型产品,决定出租机器用于接受外加工,只收加工费,那么种机器的机时如何定价才是最佳决策?,线性规划的对偶模型,在市场竞争的时代,厂长的最佳决策显然应符合两条:(1)不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则,便构成
23、了新规划的不等式约束条件。(2)竞争性原则。即在上述不吃亏原则下,尽量降低机时总收费,以便争取更多用户。,设A、B、C、D设备的机时价分别为y1、y2、y3、y4,则新的线性规划数学模型为:,线性规划的对偶模型,把同种问题的两种提法所获得的数学模型用表2表示,将会发现一个有趣的现象。,原问题与对偶问题对比表,线性规划的对偶模型,2.原问题与对偶问题的对应关系,原问题(对偶问题),对偶问题(原问题),线性规划的对偶模型,(1)对称形式,特点:目标函数求极大值时,所有约束条件为号,变量非负;目标函数求极小值时,所有约束条件为号,变量非负.,已知P,写出D,线性规划的对偶模型,例2.1 写出线性规划
24、问题的对偶问题,解:首先将原问题变形为对称形式,线性规划的对偶模型,线性规划的对偶模型,(2)非对称型对偶问题,若给出的线性规划不是对称形式,可以先化成对称形式再写对偶问题。也可直接按教材表2-2中的对应关系写出非对称形式的对偶问题。,线性规划的对偶模型,线性规划的对偶模型,例2.2 写出下列线性规划问题的对偶问题.,解:原问题的对偶问题为,对偶性质,例2.3 分别求解下列2个互为对偶关系的线性规划问题,分别用单纯形法求解上述2个规划问题,得到最终单纯形表如下表:,对偶性质,原问题最优表,对偶问题最优表,对偶性质,原问题与其对偶问题的变量与解的对应关系:在单纯形表中,原问题的松弛变量对应对偶问
25、题的变量,对偶问题的剩余变量对应原问题的变量。,对偶性质,性质1 对称性定理:对偶问题的对偶是原问题,对偶性质,性质2 弱对偶原理(弱对偶性):设 和 分别是问题(P)和(D)的可行解,则必有,推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值的下届;反之,对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。,推论2:在一对对偶问题(P)和(D)中,若其中一个问题可行但目标函数无界,则另一个问题无可行解;反之不成立。这也是对偶问题的无界性。,对偶性质,推论3:在一对对偶问题(P)和(D)中,若一个可行(如P),而另一个不可行(如D),则该可行的问题目标函数值无界。,性质3 最优性
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 所有 内容
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-5319895.html