2022年管理运筹学线性规划与运输问题.docx
精选学习资料 - - - - - - - - - 治理运筹学线性规划与运输问题线性规划某工厂在方案期内要支配、两种产品的生产,生产单位产品所需的设备台时及 AB 两种原材料的消耗及资源的限制如下表：资源限制100 元,为工厂应分别生产多少设备1 1 300 台时原料 A 2 1 400 原料 B 0 1 250 工厂每生产一单位产品可获利50 元,每生产一单位产品可获利单位产品和产品才能使获利最多？解答：1、 建模：用变量X1 和 X2 来分别表示生产多少单位产品和产品,用X1 和 X2 的线性函数来表示工厂所要求的最大利润目标：MaxZ=50X1+100X2 其他约束条件为：X1+X2 300 2X1+X2 400 X2 250 X1 0；X2 0 2、 求解运算：通过图解法,可以算得当 X1=50,X2=250 时, Z=27500 ,这说明该厂生产产品 50 千克,产品 250 千克,既有最大利润,此时消耗设备台时 300,原料 A 350 千克,原料 B 250 千克；3、 电脑求解：名师归纳总结 - - - - - - -第 1 页,共 8 页精选学习资料 - - - - - - - - - 运输模型某公司从两个产地A1 、A2 将物品运往三个销地B1、B2、B3 ,各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表：运销B1 B2 B3 产量件费地6 4 6 200 单价产地A1 A2 6 5 5 300 销量件150 150 200 应如何调运,使得总运费最小？解答：1、 建模：通读题意可知,两个产地的总销量与三个销地的总销量相等,这是一个产销平稳的运输问题；设 Xij 表示从产地 Ai 调运到 Bj 的运输量（ i=1,2；j=1,2,3 ）如 X12 表示由 A1 调运到 B2 的物品的数量,现将支配的运输量支配如下：名师归纳总结 - - - - - - -第 2 页,共 8 页精选学习资料 - - - - - - - - - 运输销B1 B2 B3 产量件地产地量X11 X12 X13 200 A1 A2 X21 X22 X23 300 销量件150 150 200 500 可作出约束条件为：满意产地产量的约束条件为： X11+X12+X13=200 X21+X22+X23=300 满意销地销量的约束条件为： X11+X21=150 X12+X22=150 X13+X23=200 使运费最小,即 minf=6X11+4X12+6X13+6X21+5X22+5X23 模型如下 : X11+X12+X13=200 X21+X22+X23=300 X11+X21=150 X12+X22=150 X13+X23=200 Xij0 可通过电脑求解名师归纳总结 - - - - - - -第 3 页,共 8 页精选学习资料 - - - - - - - - - 治理运筹学图与网络问题最短路问题图表示 V1 到 V6 的最短路（1）给起始点 V1 标以（ 0,s）,表示从 V1 到 V2 的距离为 0,V1 是起始点；（2）这时已标定点集合,未标定点的集合 2, 3, 4, 5, 6,弧集合（,）|,（ 1, 2）,（ 1,V3）,（ 1,V4）,并有S12=l1+C12=0+3=3 ； S13=l1+C13=0+2=2 ； S14=l1+C14=0+5=5 ； min=S12,S13,S14=S13=2 名师归纳总结 - - - - - - -第 4 页,共 8 页精选学习资料 - - - - - - - - - 这时我们给弧（v1,v3）的终点 v3 标以（ 2,1）,表示从 v1 到 v3 的距离为 2,并在 v1 到 v3 的最短路径中 v3 的前面一个点是 v1. （3）这 时 I=v1 , v3 , J=v2 , v4 , v5 , v6 , 弧 集 合 （ vi , vj ） vi I , vj J=v1,v2,v1,v4,v3,v4, 并有S34=l3+c34=2+1=3,mins12,s14,s34=s12=s34=3 这样我们给弧（v1,v2）的终点 v2 标以（ 3,1）,表示从 v1 到 v2 的距离为 3,并且在 v1 到 v3 的最短路径中 v2 的前面的一个点是 v1,我们给弧（ v3,v4）的终点 v4 标以（ 3,3）,表示从v1 到 v4 的距离位 3,并且在 v1 到 v4 的最短路径中 v4 的前面一个点是 v3. （4）这 时 I=v1 , v2 , v3 , v4 , J=v5 , v6 , 弧 集 合 （ vi , vj ） vi I,vjJ=v2,v6,v4,v6 并有S26=l2+c26=3+7=10,S46=l4+c46=3+5=8,mins26,s46=S46=8 这样给点 v6 标以（ 8,4）,表示从 v1 到 v6 的距离是 8,并且在 v1 到 v6 的最短路径中 v6 的前面的一个点是 v4. （5）这时 I=v1 ,v2, v3,v4,v6 ,J=v5 ,弧集合 （vi, vj） vi I,vj J 为空集,运算结束；此时 J=v5, 即 v5 仍未标号,说明从 v1 到 v5 没有有向路；（6）得到最优结果,依据终点 v6 的标号（ 8,4 ）可知从 v1 到 v6 的距离是 8,其最短路径中 v6的前面一点是 v4,从 v4 的标号（ 3,3 ）可知 v4 的前面一点是 v3,从 v3 的标号（ 2,1 ）可知 v3 的前面一点是 v1,即此最短路径为 v1v3v4v6；（7）下面是电脑求解：名师归纳总结 第 5 页,共 8 页- - - - - - -精选学习资料 - - - - - - - - - 治理运筹学之关键路径某公司装备一条新的生产线,其装配过正中的各个工序与其所需时间以及它们之间的相互连接关系如 图,求：完成此工序所需最少时间,关键路线及相应关键工序,各工序的最早开头时间及终止时间和非关键工序不影响工程完成时间的前提下,其开头时间与终止时间可以推迟多久；工序代号工序内容所需时间 / 天紧前工序a 生产线设计60 / b 外购零配件45 a c 下料、锻件10 a d 工装制造 1 20 a e 木模、铸件40 a f 机械加工 1 18 c g 工装制造 2 30 d h 机械加工 2 15 d,e i 机械加工 3 25 g j 装配调试35 b,i,f,h 解答：对于每个工序：EF=ES+t 对于工序 a 来说,最早终止时间：EF=ES+t=0+60=60 对于工序 h 来说,最早终止时间：EF=ES+t=100+15=115 对于同个工序：LS=LF-t 对于工序 j 来说： LS=LF-t=170-35=135 对于工序 b 来说： LS=LF-t=135-45=90 对于每个工序：Ts=LS-ES=LF-EF 对于工序 b 来说,其实差：Ts=LS-ES=90-60=30 对于工序 g 来说,其实差：Ts=LS-ES=80-80=0 这也就是说工序 g 的提前与推迟开头（或终止）都会使整个工序最早终止时间提与推迟,这样可知工 序 g 是关键工序,一般说关键按工序的时差为零；工序最早开最晚开最早完最晚完时差是否为第 6 页,共 8 页始时间始时间成时间成时间（LS-关键工（ES）（LS）（EF）（LF）ES）序a 0 0 60 60 0 是名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - b 60 90 105 135 30 否第 7 页,共 8 页c 60 107 70 117 47 否d 60 60 80 80 0 是e 60 80 100 120 20 否f 70 117 88 135 47 否g 80 80 110 110 0 是h 100 120 115 135 20 否i 110 110 135 135 0 是j 135 135 170 170 0 是名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页,共 8 页
