《2022年管理运筹学线性规划与运输问题》由会员分享,可在线阅读,更多相关《2022年管理运筹学线性规划与运输问题(8页珍藏版)》请在金锄头文库上搜索。
1、管理运筹学线性规划与运输问题线性规划某工厂在计划期内要安排、两种产品的生产,生产单位产品所需的设备台时及AB 两种原材料的消耗及资源的限制如下表:资源限制设备1 1 300 台时原料 A 2 1 400 原料 B 0 1 250 工厂每生产一单位产品可获利50 元,每生产一单位产品可获利100 元,为工厂应分别生产多少单位产品和产品才能使获利最多?解答:1、 建模:用变量X1 和 X2 来分别表示生产多少单位产品和产品,用X1 和 X2 的线性函数来表示工厂所要求的最大利润目标:MaxZ=50X1+100X2 其他约束条件为:X1+X2 300 2X1+X2 400 X2250 X10;X20
2、 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 产量件A1 6 4 6 200 A2 6 5 5 300 销量件150 150 200 应如何调
3、运,使得总运费最小?解答:1、 建模:通读题意可知,两个产地的总销量与三个销地的总销量相等,这是一个产销平衡的运输问题。设 Xij 表示从产地Ai 调运到 Bj 的运输量( i=1,2。j=1,2,3)如 X12 表示由A1 调运到B2 的物品的数量,现将安排的运输量安排如下:销地运费单价产地精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页,共 8 页B1 B2 B3 产量件A1 X11 X12 X13 200 A2 X21 X22 X23 300 销量件150 150 200 500 可作出约束条件为:满足产地产量的约束条件为: X11+X
4、12+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 的最短
5、路(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
6、 到 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,min(s12,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 的最短路
7、径中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,min(s26,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 还未标号,
8、说明从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 页管理运筹学之关键路径某公司装备一条新的生产线,其装配过正中的各个工序与其所需时间以及它们之间的相互衔接关系如图,求:完成此工序所需最少时间,关键路线及相应关键工
9、序,各工序的最早开始时间及结束时间和非关键工序不影响工程完成时间的前提下,其开始时间与结束时间可以推迟多久。工序代号工序内容所需时间 / 天紧前工序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 对于同
10、个工序: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 是关键工序,一般说关键按工序的时差为零。工序最早开始时间(ES )最晚开始时间(LS)最早完成时间(EF)最晚完成时间(LF)时差(LS-ES )是否为关键工序a 0 0 60 60 0 是
11、精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页,共 8 页b 60 90 105 135 30 否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 是精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页,共 8 页精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页,共 8 页