运筹学(胡运权第四版及答案)精编版ppt课件.ppt
《运筹学(胡运权第四版及答案)精编版ppt课件.ppt》由会员分享,可在线阅读,更多相关《运筹学(胡运权第四版及答案)精编版ppt课件.ppt(241页珍藏版)》请在三一办公上搜索。
1、,管理运筹学,主讲:谢先达2014.09,联系方式办公室:QL643 87313663手机: 13600512360邮箱: ,绪 论,绪论,什么是运筹学?运筹学发展历史运筹学主要内容运筹学的基本特征与基本方法,绪论,什么是运筹学?定义:为决策机构在对其控制下业务活动进行决策时,提供以数量化为基础的科学方法。西蒙:管理就是决策 决策,定性,管理者的判断和经验,定量,运筹学,绪论,运筹学发展历史古代运筹思想:田忌赛马、丁渭修皇宫 二战期间的Operational Research 研究成果被应用到生产、经济领域,且研究不断深化,逐步形成“运筹学”,绪论,绪论,运筹学的主要内容有哪些?,线性规划运输
2、问题整数规划目标规划动态规划图与网络模型,排序与统筹方法存储论排队论对策论决策分析预测,绪论,运筹学研究的基本特征系统的整体观念多学科的综合模型方法的应用,绪论,运筹学研究的基本方法分析和表述问题建立模型求解模型和优化方案测试模型及对模型进行必要的修正建立对解的有效控制方案的实施,第一章:线性规划及单纯形法,第一章:线性规划及单纯形法,线性规划问题及其数学模型线性规划图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论,第一章:线性规划及单纯形法,例题:某工厂在计划期内要安排、两种产品的生产,生产单位产品所需的设备台时及A、两种原材料的消耗以及资源的限制如表所示 工厂每生产一单位产品可获利5
3、0元,每生产一单位产品可获利100元,问工厂应分别生产多少单位产品 和产品才能获利最多?,第一章:线性规划及单纯形法,线性规划问题的数学模型 目标函数: maxz=50 x1+100 x2 x1+x2300 2x1+x2400 x2250 x10 ,x2 0 概念:可行解、最优解、最优值,约束条件:,非负约束:,第一章:线性规划及单纯形法,500万m3,练习:靠近某河流有两个化工厂,流经第一化工厂的河流流量为每天500万m3,在两个工厂之间有一条流量为每天200万m3支流,第一化工厂每天排放含有某种有害物质的工业污水2万m3 ,第二化工厂每天排放这种工业污水1.4万m3 。从第一化工厂排出的工
4、业污水流到第二化工厂以前,有20%可自净化。根据环保要求,河流中工业污水的含量应不大于0.2%,这两个工厂都需各自处理一部分工业污水,第一化工厂处理工业污水的成本是1000元/万m3 。第二化工厂处理污水的的成本是800元/万m3 。现问在满足环保要求的条件下,每厂各应处理多少工业污水,使这两个工厂总的处理工业污水费用最小。,200万m3,工厂1,工厂2,第一章:线性规划及单纯形法,线性规划问题的数学模型目标函数:minz=1000 x1+800 x2约束条件: (2-x1)/5000.2% 0.8(2-x1) +(1.4-x2)/700 0.2% x1 2 x21.4非负约束: x10 ,x
5、2 0,线性规划的一般模式目标函数:max(min)Z=c1x1+c2x2+c3x3+cnxn约束条件:a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn (= )b2 am1x1+am2x2+am3x3+amnxn (= )bn非负性约束:x1 0,x2 0,xn 0,第一章:线性规划及单纯形法,解得: 最大利润:27500 X1=50 X2=250代入得: 设备台时:300 原料A:350 原料B:250概念:松弛变量 剩余变量,第一章:线性规划及单纯形法,线性规划的标准型 maxZ=c1x1+c2x2+cnxn a11x1+a12
6、x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0 j=1,2,n,第一章:线性规划及单纯形法,标准型的四个标准:求最大值、约束条件为等式、bj 0. xj 0,化非标准形线性规划为标准形式minz=x1+2x2+3x3 -2x1+x2+x3 9 -3x1+x2+2x3 400 4x1-2x2-3x3=-6 x1 0,x2 0, x3取值无约束,第一章:线性规划及单纯形法,练习:将下面线性规划问题化为标准形式 minz=2x1-2x2+3x3 -x1+x2+x3 = 4 -2x1+x2-x3 6 x1 0,x2 0, x3取值无
7、约束,第一章:线性规划及单纯形法,第一章:线性规划及单纯形法,线性规划问题及其数学模型线性规划图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论,400,200,100,100,200,300,400,300,0,x1,x2,第一章:线性规划及单纯形法,2x1+x2=400,x2=250,x1+x2=300,目标函数: maxz=50 x1+100 x2约束条件: x1+x2300 2x1+x2400 x2250非负约束: x10 ,x20,400,200,100,100,200,300,400,300,0,x1,x2,2x1+x2=400,x2=250,x1+x2=300,第一章:线性规
8、划及单纯形法,可行域,400,200,100,100,200,300,400,300,0,x1,x2,2x1+x2=400,x2=250,x1+x2=300,Z=0=50 x1+100 x2,Z=1000=50 x1+100 x2,Z=20000=50 x1+100 x2,Z=27500=50 x1+100 x2,第一章:线性规划及单纯形法,等值线,线性规划问题解的几种情况线性规划存在唯一最优解线性规划存在有无穷多个最优解的情况线性规划可能存在无界解线性规划存在无可行解的情况,第一章:线性规划及单纯形法,练习:P43:1.1(1) (2),第一章:线性规划及单纯形法,第一章:线性规划及单纯形法
9、,线性规划问题及其数学模型线性规划图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论,基本概念:,可行解最优解基基解基可行解可行基,第一章:线性规划及单纯形法,解的几何意义,例: 线性规划问题基本可行解的意义:,第一章:线性规划及单纯形法,解的几何意义,第一章:线性规划及单纯形法,解的几何意义,第一章:线性规划及单纯形法,解的几何意义,第一章:线性规划及单纯形法,解的几何意义,第一章:线性规划及单纯形法,解的几何意义,第一章:线性规划及单纯形法,解的几何意义,第一章:线性规划及单纯形法,算法思路,求一个初始基本可行解 是 判断基本可行解是否最优 结 束 不是 求使目标得到改善的基本可行解,
10、是否存在?如何得到?,是否唯一?,如何判断?,如何改善?如何判断没有有限最优解?,第一章:线性规划及单纯形法,基本定理,定理1 若线性规划问题存在可行解,则该问题的可行解集(即可行域)是凸集。定理2 线性规划问题的基可行解x对应线性规划问题可行域(凸集)的顶点定理3 若线性规划问题有最优解,一定存在一个基可行解(可行域顶点)是最优解,如果在几个顶点上都出现最优解,则这些顶点的每个凸组合上也达到最优。,第一章:线性规划及单纯形法,凸集的概念,1、基本概念: 凸集设K是n维欧氏空间的一个点集,若任意两点X(1)K,X(2)K的连线上的一切点:X(1)+(1-)X(2) K(01),则称K为凸集。,
11、第一章:线性规划及单纯形法,凸集的概念,凸组合设X(1) ,X(2) ,X(k) 是n维欧氏空间中的K个点,若存在k个数1, 2 , k ,满足0i1, i=1,2, ,k; 则称X=1X(1)+2X(2)+kX(k)为X(1), ,X(2) ,X(k)的凸组合。顶点设K是凸集,XK;若K中不存在两个不同的点X(1) K,X(2) K 使 X=X(1)+(1-)X(2) (01) 则称X为K的一个顶点(也称为极点或角点)。,第一章:线性规划及单纯形法,凸集的概念,凸集,凸集,不是凸集,顶点,第一章:线性规划及单纯形法,表格单纯形法,基变量,检验数,基变量系数 右端常数 最小比值列,第一章:线性
12、规划及单纯形法,表格单纯形法,基变量,检验数,基变量系数 右端常数 最小比值列,第一章:线性规划及单纯形法,表格单纯形法,第一章:线性规划及单纯形法,表格单纯形法,第一章:线性规划及单纯形法,表格单纯形法,第一章:线性规划及单纯形法,1、人工变量法(大法)2、两阶段法,第一章:线性规划及单纯形法,单纯形法的进一步讨论:,第一章:线性规划及单纯形法,人工变量法 目标函数: maxz=-3x1+ x3 x1+x2+ x3 4 -2x1+x2- x3 1 3x2+ x3 =9 x1,x2,x3 0,约束条件:,第一章:线性规划及单纯形法,化成标准形式: 目标函数: maxz=-3x1+ x3+0 x
13、4+0 x5 x1+x2+ x3 +x4 =4 -2x1+x2- x3 -x5 =1 3x2+ x3 =9 x1,x2,x3 ,x4,x5 0,约束条件:,第一章:线性规划及单纯形法,添加人工变量: 目标函数:maxz=-3x1+ x3+0 x4+0 x5-Mx6-Mx7 x1+x2+ x3 +x4 =4 -2x1+x2- x3 -x5 +x6 =1 3x2+ x3 + x7 =9 x1,x2,x3 ,x4,x5,x6,x7 0,约束条件:,第一章:线性规划及单纯形法,两阶段法: 目标函数:maxw=x6+x7 x1+x2+ x3 +x4 =4 -2x1+x2- x3 -x5 +x6 =1 3
14、x2+ x3 + x7 =9 x1,x2,x3 ,x4,x5,x6,x7 0,约束条件:,第三章 运输问题,例1:某公司从两个产地A1,A2将物品运往三个销地B1,B2,B3,各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如表所示,第三章 运输问题,例1:某公司从两个产地A1,A2将物品运往三个销地B1,B2,B3,各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如表所示,minf=6x11+4x12+6x12+6x21+5x22+5x23 x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=
15、200 xij(i=1,2;j=1,2,3),第三章 运输问题,解:产销平衡问题: 总产量 = 总销量设xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表。,第三章 运输问题,一般运输模型:产销平衡 A1、 A2、 Am 表示某物资的m个产地; B1、B2、Bn 表示某物质的n个销地;si 表示产地Ai的产量; dj 表示销地Bj 的销量; cij 表示把物资从产地Ai运往销地Bj的单位运价。设 xij 为从产地Ai运往销地Bj的运输量,得到下列一般运输量问题的模型: m n Min f = cij xij i = 1 j = 1 n xij = si i = 1,2,m j = 1
16、m xij = dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n),第三章 运输问题,变化: 1)有时目标函数求最大。如求利润最大或营业额最大等; 2)当某些运输线路上的能力有限制时,在模型中直接加入约束条件(等式或不等式约束); 3)产销不平衡时,可加入假想的产地(销大于产时)或销地(产大于销时)。,第三章 运输问题,例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?解:增加一个虚设的销地运输费用为0,第三章 运输问题,例3、
17、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?解:增加一个虚设的产地运输费用为0,第三章 运输问题,第三章 运输问题,产销不平衡问题 石家庄北方研究院有三个区,即一区、二区、三区,每年分别需要生活用煤和取暖用煤3000 T,1000T,2000T,由河北临城、山西盂县两处煤矿负责供应,这两处煤矿的价格相同,煤的质量也基本相同,两处煤矿能供应北方研究院的煤的数量,山西盂县为4000T,河北临城为1500T,由煤矿至北方研究院的单位运价(百元/T)如表所示。 由于需大于供,经院研
18、究决定一区供应量可减少0-300吨,二区必须满足需求量,三区供应量不少于1500吨,试求总费用为最低的调运方案。,第三章 运输问题,解: 根据题意,作出产销平衡与运价表:这里 M 代表一个很大的正数,其作用是强迫相应的 x31、 x33、 x34取值为0。,例设有三个化肥厂供应四个地区的农用化肥,假定等量的化肥在这些地区使用效果相同,各化肥厂年产量、各地区年需求及各化肥厂到各地区运送单位化肥的运价如表所示,试求出总的运费最节省的的化肥调拨方案。,第三章 运输问题,解: 根据题意,作出产销平衡与运价表:,第三章 运输问题,最低要求必须满足,因此把相应的虚设产地运费取为 M ,而最高要求与最低要求
19、的差允许按需要安排,因此把相应的虚设产地运费取为 0 。对应 4”的销量50 是考虑问题本身适当取的数据,根据产销平衡要求确定 D的产量为 50。,求解结果如下:,第三章 运输问题,第三章 运输问题,生产与储存问题例某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货,每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下,使该厂全年生产总费用为最小的决策方案。,第三章 运输问题,第三章 运输问题,某公司承担4条航线的运输任务,已知:(1)各条航线的起点城市与终点
20、城市及每天的航班数(见下表1);(2)各城市间的航行时间(见下表2);(3)所有航线都使用同一船只,每次装船和卸船时间均为1天。问该公司至少应配备所少条船才能满足所有航线运输的需要? 表1:,第三章 运输问题,某公司承担4条航线的运输任务,已知:(1)各条航线的起点城市与终点城市及每天的航班数(见下表1);(2)各城市间的航行时间(见下表2);(3)所有航线都使用同一船只,每次装船和卸船时间均为1天。问该公司至少应配备所少条船才能满足所有航线运输的需要?表2:,表上作业法按某种规则找出一个初始基可行解;对现行解作最优性判断,即求各非基变量的检验数,判别是否达到最优解,如已是最优解,则停止计算,
21、如不是最优解,则进行下一步骤;在表上对初始方案进行改进,找出新的基可行解,再按第二步进行判别,直至找出最优解。,第三章 运输问题,图:运输问题求解思路图,第三章 运输问题,初始基本可行解的确定甲、乙两个煤矿供应A、B、C三个城市用煤,各煤矿产量及各城市需煤量、各煤矿到各城市的运输单价见表所示,求使总运输费用最少的调运方案。,第三章 运输问题,有关信息表,450,200,150,100,日销量(需求量),250,75,65,80,乙,200,100,70,90,甲,日产量(供应量),C,B,A,运距 城市煤矿,第三章 运输问题,西北角法不是优先考虑具有最小单位运价的供销业务,而是优先满足运输表中
22、西北角(左上角)上空格的供销要求,用西北角法确定初始调运方案,100,100,100,50,50,200,200,得到初始调运方案为: x11=100,x12=100,x22=50,x23=200,最小元素法:从运价最小的格开始,在格内的标上允许取得的最大数。然后按运价从小到大顺序填数。若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去。如此进行下去,直至得到一个基本可行解。,用最小元素法确定初始调运方案,150,100,100,100,100,100,100,得到初始调运方案为: x11=100,x13=100,x22=150,x23=100,最优性检验根据最小元素法或西北角法求得
23、运输问题的初始基可行解之后,按照表上作业法的第二步,下面需对这个解进行最优性判别,看它是否为本运输问题的最优解.,以xij空格为第一个奇数顶点,沿闭回路的顺(或逆)时针方向前进,对闭回路上的每个折点依次编号;那麽,该非基变量xij的检验数:,现在,在用最小元素法确定例2初始调运方案的基础上,计算非基变量X12的检验数 :,闭回路法,初始调运方案中以X12(X21)为起点的闭回路,非基变量X12的检验数:,非基变量X21的检验数:,=(c12+c23)-(c13+c22) =70+75-(100+65)=-20,,=(c21+c13)-(c11+c23)=80+100-(90+75)=15。,经
24、济含义:在保持产销平衡的条件下,该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。,位势法,检验数公式: 分别表示前m个约束等式对应的对偶变量; 分别表示后n个约束等式对应的对偶变量。,初始调运方案对偶变量对应表,2、位势法,以初始调运方案为例,设置对偶变量 和 , 然后构造下面的方程组:,在式中,令u1=0,则可解得v1=90,v3=100,u2=-25,v2=90,于是12=c12-(u1+v2)=70-(0+90)=-2021=c21-(u2+v1)=80-(-25+90)=15与前面用闭回路法求得的结果相同。,在式中,令u1=0,则可解得v1=90,v3=100,u2=-25
25、,v2=90,于是12=c12-(u1+v2)=70-(0+90)=-2021=c21-(u2+v1)=80-(-25+90)=15与前面用闭回路法求得的结果相同。,位势法计算非基变量xij检验数的公式 ij=cij-(ui+vj),复习比较检验数计算的两种方法,思考:试解释位势变量的含义(提示:写出运输问题的对偶问题),解的改进如检验出初始解不是最优解,即某非基变量检验数为负,说明将这个非基变量变为基变量时运费会下降。根据表上作业法的第三步,需对初始方案进行改进。,解的改进步骤为: 1(如存在多个非基变量的检验数为负时,以最小负检验数所在空格对应的变量)为换入变量,找出它在运输表中的闭回路;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 胡运权 第四 答案 精编 ppt 课件
链接地址:https://www.31ppt.com/p-1445070.html