运筹学基础复习二.ppt

第五章、目标规划,目标规划(Goal programming)是在线性规划基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个运筹学分支。,一、目标规划的基本概念,1.目标值和正、负偏差变量,d超出目标的差值，称正偏差变量；,d未达到目标的差值，称负偏差变量；,2.绝对约束与目标约束,3.目标规划的目标函数达成函数,4. 目标的优先级与权系数,5. 满意解,二、目标规划的数学模型及建模步骤,目标规划问题的一般数学模型可表述为,目标规划问题建立模型的步骤为：,1. 根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；,2.可根据决策者的需要将某些或全部绝对约束转化为目标约束，这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可；,3.给各自目标赋予相应的优先因子Pk（k=1,2,K）变量即可；,4. 对同一优先等级中的各偏差变量，若需要，可按其重要程度不同，赋予相应的权系数。,5.根据决策者需求，按下列三种情况：,a.恰好达到目标值，取,c.不允许超过目标值，取,b.允许超过目标值，取,将正、负偏差变量列入达成函数中去。,例 1,4x1 16 4x2 12,minZ= P1 d1-,目标规划,x1x2 +d2-d2+ =0,2x1 +2x2 +d3- d3+ =12,+ P2(d2- + d2+),x1 +2x2 +d4- d4+ =8,+3 P3(d3- + d3+) + P3d4+,x1, x2 ，di-,di+ 0,利润不得低于12，列为第一优先级,生产量保持1:1的比例，列为第二优先级,设备A、B尽量不超负荷工作，列为第三,2x1 +3x2 +d1- d1+ =12,现假定引例2中企业最重要的目标是利润，不得低于12，列为第一优先级，其次目标是,产品的生产量尽量保持1:1的比例，列为第二优先级：再次是设备A、B尽量不超负荷工作，列为第三优先级。在第三级中中设备A的重要性比设备B大三倍，因此目标函数中在设备A的偏差变量前冠以权系数3。对其编号目标规划模型为：,C和D为贵重设备，严格禁止超时使用,三、目标规划的图解法,和线性规划问题一样，图解法虽然只适用于两个决策变量的目标规划问题，但其操作简便，原理一目了然，并且有助于理解一般目标规划问题的求解原理和过程。,图解法解题的步骤为：,1.确定各约束条件的可行域，即将所有约束条件(包括目标约束和绝对约束，暂不考虑正负偏差变量)在坐标平面上表示出来；,2.在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；,3.求满足最高优先等级目标的解；,4.转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；,5.重复4，直到所有优先等级的目标都已审查完毕为止；,6.确定最优解或满意解。,下面通过例子来说明目标规划图解法的原理和步骤。,例1 用图解法求解目标规划问题：,E,D,F,3x1-4x2=0 x1+2x2=8 得x1=3.2，x2=2.4,例 2、用图解法求解线性规划模型,于是，确定D点的坐标x1=60，x2=58.3为所求的满意解。即 D(60, 58.3),练习：用图解法求解下列目标规划问题,(2),(3),(4),(1),C,D,结论：有无穷多最优解。C（2，4），D（10/3，10/3）,2、用图解法求解下列目标规划问题：,满意解为由x1 =（3， 3）, x2 =（3.5，1.5） 所连线段。,3、用图解法解下列目标规划模型,x1=400, x2=0, Z=80p3,0,100 200 300 400 500,100 200 300 400,x2,x1,4,四、目标有优先级的目标规划解法-加权法,练习、用EXCEL求解下列目标规划问题：,x =（10，20，10）,练习、用EXCEL解以下目标规划模型。,5、x1=12, x2=10, =14, Z=14p4,第六章 图论方法,图是反映对象之间关系的一种工具。是在纸上用点和线画出的各种各样的示意图。,首先介绍涉及到的基本概念,一、“树”图和“最小部分树”,二、最短线路问题,三、最大流量问题,四、最小费用流问题,一、树图和图的最小部分树,树：一个无圈的连通图称为树。,最小树杈：是关于在一个网络中，从一个起点出发到所有点，找出一条或几条路线，以使在这样一些路线中所采用的全部支线的总长度是最小的，或铺设费用最少。,求图的最小树杈问题的方法有“破圈法”和“避圈法”。,树的性质,破圈法(克鲁斯喀尔法),例：已知连接五个城市的公交线路图，在要在五个城市间架设电话线，为了便于维修要求电话线必须沿公路架设，并且电话线总长度最小。,此为最小树杈，最小线路长度为 20+15+10+9=54,破圈法：任选一个圈，从圈中去掉杈最大的一条边。在余下的图中重复这个步骤，直到得到一连通的不含圈的图为止。,避圈法(普赖姆法),避圈法：开始选一条杈最小的边，以后每一步中，总从未被选取的边中选一条杈尽可能小，且与已选边不构成圈的边。,此为最小树杈，最小线路长度为 20+15+10+9=54,练习：求最小树杈,2,5,3,1,2,2,3,4,5,3,3,2,3,2,2,2,6.3 最短线路问题,当通过网络的各边所需时间、距离或费用为已知时，找出从入口到出口所需的最少时间、最短距离或最少费用的路径问题，称做网络的路线问题。 本节主要介绍最短路线问题。方法以是从终点开始逐步逆向推算,100,300,9-10,6-9-10,500,4-6-9-10,650,1-4-6-9-10,150,8-10,375,7-8-10,400,5-8-10,600,2-6-9-10,600,3-5-8-10,4,1,6,9,10,最短路线为650,用EXCEL求最短路线问题,三、最大流量问题,当以物体、能量或信息等作为流量流过网络时，怎样使流过网络的流量最大，或者使流过网络的流量费用或时间最小。通常把设计为样的流量模型问题，叫做网络的流量问题。 本节主要讨论最大流量问题。即在一定条件下，要求流过网络的流量为最大。,在有一个起点和一个终点的网络中，最大流量问题是企图找出，在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量。,1、确定网路最大流的标号法,(1) 网路的最大流的相关概念,定义网路上支路的容量为其最大通过能力,记为 cij ,支路上的实际流量记为 fij,图中规定一个发点s，一个收点t,(cij , fij )或 cij( fij ),容量限制条件：0fij cij,平衡条件：,满足上述条件的网路流称为可行流，总存在最大可行流,当支路上 fij = cij，称为饱和弧，否则称为不饱和弧,（2）标号法的基本算法,从任一个初始可行流出发。,若在当前可行流下找不到增广链，则已得到最大流,增广链是从发点到收点的一条链，该链上所有指向为st的前向弧，存 在fc；所有指向为ts的后向弧，存在f0，这样的链叫增广链。,基本算法：找一条从 s 到 t 点的增广链。,增广过程：前向弧 fij=fij+, 后向弧 fij=fij ,增广后仍是可行流,增广值,最大流最小截的标号法步骤,第一步：标号过程，找一条增广链,1、给源点 s 标号s+,q(s)=，表示从 s 点有无限流出潜力,2、找出与已标号节点 i 相邻的所有未标号节点 j，若,(1) (i, j)是前向弧且饱和，则节点 j 不标号； (2) (i, j)是前向弧且未饱和，则节点 j 标号为i+,(j)，表示从节点 i 正向流出，可增广 (j)=min(i), cijfij ； (3) (j, i)是后向弧，若 fji=0，则节点 j 不标号； (4) (j, i)是后向弧，若 fji0，则节点 j 标号为i, (j)，表示从节点 j 流向 i，可增广 (j)=min(i), fji ；,3、重复步骤 2，可能出现两种情况：,(2)节点 t 获得标号，找到一条增广链，由节点 t 标号回溯可找出该增广链；到第二步,(1) 节点 t 尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流 v(f) 就是最大流；所有获标号的节点在 V 中，未获标号节点在 中，V 与 间的弧即为最小截集；算法结束,最大流最小截的标号法步骤,第二步：增广过程 1、对增广链中的前向弧，令 f=f+q(t)，q(t) 为节点 t 的标记值 2、对增广链中的后向弧，令 f=fq(t) 3、非增广链上的所有支路流量保持不变 第三步：抹除图上所有标号，回到第一步 一次只找一条增广链，增广一次换一张图 最后一次用广探法，以便找出最小截集,最大流最小截集的标号法举例,(s+,),(s+,2),(2-,2),(1+,2),(3-,1),(4+,1),第一条链：(s+,)(s+,2) (2-,2) (1+,2) (3-,1) (4+,1),q = 1,前向弧 fij=fij+,后向弧 fij=fij ,(s+, ),(s+, 1),(2-, 1),(1+, 1),第二条链：(s+,)(s+,1) (2-,1) (1+,1)截止,最大流量为5+914,最小截集,练习,=7,=5,=2,截止，最大流量9+514,练习,练习：求最大流量,用EXCEL求最大流量问题,第七章 计划评审方法和关键线路法,一、网络图的分类,箭线式网络图,以箭线代表作业(活动)，以事件代表作业的开始和完成。需要引进虚作业(以虚线表示)，其特点是布图明朗，应用广泛。,结点式网络图,以结点代表作业(活动)，以箭线表示各之间的待后承接关系。不需要引进虚作业，但其特点是线条纵横交错，不一目了然，应用不广泛。,箭线式网络图例,1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,A,B,D,E,F,G,H,C,I,J,K,L,M,N,O,P,Q,箭线代表作业,事件代表作业的开始和完成,结点（事件）式网络图例,始,B,A,C,D,E,F,G,H,I,J,K,M,N,O,L,P,Q,x,二、箭线式网络图的构成,箭线式网络图是由作业、事件和线路三个部分组成。,1. 作业,指任何消耗人力、物力或时间等资源的相对独立的作业过程，又称作业或工序。在网络图中作业用箭线“” 表示。,2. 事件,事件（也叫结点），是相邻作业的分界点，标志着作业的开始或结束。一般用圆圈“”来表示，每个事件编上顺序号；,3. 线路,线路是指从最初事件开始，顺着箭线的方向，由各项作业连贯组成的，到达最终事件的一条路。从最初事件到最终事件可以有不同的路。,4.关键路线,在所有的线路中，总作业时间最长的线路就是关键路线。或叫主要矛盾线。关键线路决定整个网络计划的完工时间。,三、绘制网络图,某一工程的作业时细表,要求：给出的作业明细表绘制网络图,第一步：先画出无紧前作业的A、B，给网络始点编号为,第二步：用一条斜线“”消去已画入网络图的作业A、B， 在A后面，画出紧前作业为A的作业E；在B后面，画出紧前作业为B的作业D；给新增的事件编号为、，在A与B后面，画出紧前作业为A、B的作业C；画作业C时要引进虚作业，为新增的事件编号为。,第三步：用一条斜线“”消去已画入网络图的作业C 将F画在紧前作业C之后；为新增的事件编号为。,第四步：用一条斜线“”消去已画入网络图的作业D、E、F 将G画在紧前作业E、F之后；将H画在紧前作业D、F之后，引入虚作业,第五步：再用一条斜线“”消去已画入网络图的作业G、H 以此类推，最后得出网络图,某工程的网络图,A,B,E,D,C,F,G,H,I,J,1,3,5,7,9,11,13,15,17,19,21,练习：,练习1：,练习2：,答案,F,A,C,D,E,B,答案,F,A,C,D,B,E,四、网络时间的计算,网络时间的计算有三种计算方法：图上计算法、表格计算法和矩阵计算法。,图上计算法要用的有关符号,图上计算法要用的有关符号,作业最早开始符号。在长方形符号中标以作业最早开始时间值，该符号放在箭线的上方，靠近前事件i的右上角。,作业最迟完成符号。在三角形符号中标以作业最迟完成时间值，该符号放在箭线的好方，靠近后事件j的左好角。,作业时间的完整计算：,作业的最早开始时间、最早完成时间与事件的最早开始时间是顺着箭线的方向，逐个计算；,作业的最迟完成时间、最迟开始时间与事件的最迟完成时间是逆着箭线的方向，逐个计算；,0,0,2,2,3,3,3,7,10,10,10,10,17,23,完工时间28,28,23,17,17,15,15,10,10,10,7,3,3,3,3,0,关键线路,28,五、时差与关键路线,时差,又称机动时间或宽裕时间，是指在不影响如期完成任务的条件下，各道工序可以机动使用的一段时间。,1、事件时差,Si=LFiESi,2、作业时差,作业的总时差Ri,j,Ri,j=LFi,jEFi,j,= LFi,jTi,jESi,j,作业的自由时差Fi,j,Fi,j=ESj,kEFi,j, ESj,kTi,jESi,i,3、线段时差,R总=max(Ri,j、 Rj,k、 、 Rl,q),4、线路时差,书上规定的各时间的计算及标注方法,tLF(i,j),t(i,j),tES(i,j),R(i,j),要求：1、会求关键线路,2、会进行线路优化,例2如例1中列出的各