管理运筹学线性规划与运输问题

1、管理运筹学线性规划与运输问题线性规划某工厂在计划期内要安排i、n两种产品的生产，生产单位产品所需的设备台时及ab两种原材料的消耗及资源的限制如下表：In资源限制设备11300台时原料A21400 kg原料B01250 kg工厂每生产一单位产品I可获利50元，每生产一单位n产品可获利100元，为工厂应分别生产多少单位产品I和产品n才能使获利最多？解答：1、建模：用变量 X1和X2来分别表示生产多少单位产品I和产品n,用 X1和X2的线性函数来表 示工厂所要求的最大利润目标：MaxZ=50X1 + 100X2其他约束条件为：X1+X2 3002X1+X2 400X2 0; X2 02、 求解计算：

2、通过图解法，可以算得当X仁50,X2=250时，Z=27500，这说明该厂生产产品I50千克，产品n 250千克，既有最大利润，此时消耗设备台时300,原料A 350千克，原料 B 250千克。3、电脑求解：嬪结果输出IBfx厳除*5|（球案水*：#*球察* *索車*案重*4（眞优解?口下宣嵬*耳案* *案* *京* *除*除*除*球器函数戟助礦畀相訓300嬲艮Er唱上ko2- rLO3- 305050050目标函数来數范国卞限当前值上限u0对偶析格50250 松弛/剌余变量Ml釣束黑10x250审数项数范围.约束下限50100100无上限当前值上限运输模型某公司从两个产地 A1、A2将物品运

3、往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表：运销费；地rB1B2B3产量/件A1646200A2655300销量/件150150200应如何调运，使得总运费最小? 解答：1、建模：通读题意可知，两个产地的总销量与三个销地的总销量相等，这是一个产销平衡的运输问 题。设Xij表示从产地 Ai调运到Bj的运输量（i=1,2。j=1,2,3 ）如X12表示由A1调运到B2的物品的 数量，现将安排的运输量安排如下：运销输地B1B2B3产量件A1X11X12X13200A2X21X22X23300销量件150150200500可作出约束条件为：满足产地产

4、量的约束条件为:X11+X12+X13=200X21+X22+X23=300满足销地销量的约束条件为：X11+X2仁 150X12+X22=150X13+X23=200使运费最小，即 mi nf=6X11+4X12+6X13+6X21+5X22+5X23 模型如下：X11+X12+X13=200X21+X22+X23=300X11+X21=150X12+X22=150X13+X23=200 Xij 0可通过电脑求解管理运筹学图与网络问题一一最短路问题图表示V1到V6的最短路(1) 给起始点V1标以(0, s),表示从V1到V2的距离为0, V1是起始点。(2) 这时已标定点集合I =V1,未标

5、定点的集合J =V2,V 3,V 4,V 5, V 6，弧集合(Vi,Vj) |Vil,Vjj = (V1 , V 2 ),(V 1,V3),(V 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这时我们给弧(vl, 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),(

6、v1,v4),(v3,v4),并有S34=l3+c34=2+仁 3,mi n(s12,s14,s34)=s12=s34=3这样我们给弧(vi , v2)的终点v2标以(3,1)，表示从vi到v2的距离为3,并且在vi 到v3的最短路径中v2的前面的一个点是 vi,我们给弧(v3, v4)的终点v4标以(3,3)，表示从 vi到v4的距离位3,并且在vi到v4的最短路径中v4的前面一个点是 v3.(4) 这时 I=vi , v2 , v3 , v4 , J=v5 , v6，弧集合( vi , vj )| vi I,vj J=(v2,v6),(v4,v6)并有S26=l2+c26=3+7=i0,S

7、46=l4+c46=3+5=8,mi n( s26,s46)=S46=8这样给点v6标以(8,4),表示从vi到v6的距离是8,并且在vi到v6的最短路径中v6的前面 的一个点是v4.(5) 这时 I=vi , v2 , v3, v4, v6 , J=v5，弧集合 (vi, vj )| vi I,vj J为空集，计算结 束。此时J=v5,即v5还未标号，说明从 vi到v5没有有向路。(6) 得到最优结果，根据终点 v6的标号(8,4 )可知从vi到v6的距离是8,其最短路径中 v6 的前面一点是 v4,从v4的标号(3,3 )可知v4的前面一点是 v3 ,从v3的标号(2,i )可 知v3的前

8、面一点是 vi ,即此最短路径为 vi t v3t v4t v6o(7) 下面是电脑求解：管理运筹学之关键路径某公司装备一条新的生产线，其装配过正中的各个工序与其所需时间以及它们之间的相互衔接关系如 图，求：完成此工序所需最少时间，关键路线及相应关键工序，各工序的最早开始时间及结束时间和 非关键工序不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。工序代号工序内容所需时间/天紧前工序a生产线设计60/b外购零配件45ac下料、锻件10ad工装制造120ae木模、铸件40af机械加工118cg工装制造230dh机械加工215d,ei机械加工325gj装配调试35b,i,f,h解答：对

9、于每个工序：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是关键工序，一般说关键按工序的时差为零。最早开最晚开最早完最晚完时差是否为工序始时间始时间成时间成时间(LS-关键工（ES）（LS）（EF）（LF）ES序a0060600是b609010513530否c601077011747否d606080800是e608010012020否f701178813547否g80801101100是h10012011513520否i1101101351350是j1351351701700是0606060607000100110135工序安排