1、1管理运筹学复习（1）某工厂在计划期内要安排,两种产品的生产.生产单位产品所需的设备台时及 A,B两种原材料的消耗以及资源的限制如下表所示: 资源限制设备 1 1 300 台时原料 A 2 1 400kg原料 B 0 1 250kg工厂每生产一单位产品可获利 50 元，每生产一单位产品可获利 100 元，问工厂应分别生产多少单位产品和产品才能使获利最多？解： max z=50X1+100X2 ；满足约束条件： X1+X2300，2X1+X2400，X2250，X10,X20。（2）：某锅炉制造厂，要制造一种新型锅炉 10 台，需要原材料为63.54mm 的锅炉钢管，每台锅炉需要不同长度的锅炉钢
2、管数量如下表所示：规格/mm 需要数量/根 规格/mm 需要数量/根2640 8 1770 421651 35 1440 1库存的原材料的长度只有 5500mm 一种规格，问如何下料，才能使总的用料根数最少？需要多少根原材料？解：为了用最少的原材料得到 10 台锅炉，需要混合使用 14 种下料方案1 2 3 4 5 6 7 8 9 10 11 12 13 1426402 1 1 1 0 0 0 0 0 0 0 0 0 017700 1 0 0 3 2 2 1 1 1 0 0 0 016510 0 1 0 0 1 0 2 1 0 3 2 1 014400 0 0 1 0 0 1 0 1 2 0
3、1 2 3合计52804410429140805310519149805072486146504953474245314320剩余220 109012091420190 309 520 428 639 850 547 758 969 1180设按 14 种方案下料的原材料的根数分别为 X1,X2,X3,X4,X5,X6 ,X7,X8,X9,X10,X11,X12,X13,X14, 可列出下面的数学模型：min fX 1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11+X12+X13+X14满足约束条件： 2X1X 2X 3X 4 80X23X 52X 62X 7X 8X 9X
4、10 420X3X 62X 8X 93X 11X 12X 13 350X4X 7X 92X 10X 122X 133X 14 10X1，X 2，X 3，X 4，X 5，X 6，X 7，X 8，X 9，X 10，X 11，X 12，X 13，X 14 02（3）某公司从两个产地 A1、A 2 将物品运往三个销地 B1、B 2、B 3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：B1 B2 B3 产量/件A1 6 4 6 200A2 6 5 5 300销量 /件 150 150 200应如何调运，使得总运输费最小？解： 此运输问题的线性规划的模型如下min f =6X1
5、1+4X12+6X13+6X21+5X22+5X23约束条件 ： X11+X12+X13=200X21+X22+X23=300X11+X21=150X12+X22=150X13+X23=200Xij0(i=1,2;j=1,2,3)(4) 某公司从两个产地 A1、A 2 将物品运往三个销地 B1、B 2、B 3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：B1 B2 B3 产量/件A1 6 4 6 300A2 6 5 5 300销量 /件 150 150 200 500 600应如何组织运输，使得总运输费为最小？解：这是一个产大于销的运输问题，建立一个假想销地 B4，
6、得到产销平衡如下表：B1 B2 B3 B4 产量/件A1 6 4 6 0 300A2 6 5 5 0 300销量 /件 150 150 200 100 600 600（5）某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2 、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运输单价如下表所示：B1 B2 B3 产量/件A1 6 4 6 200A2 6 5 5 300销量 /件 250 200 200 650 500解：这是一个销大于产的运输问题，建立一个假想销地 A3，得到产销平衡如下表：B1 B2 B3 产量/件A1 6 4 6 200A2 6 5 5 3003A3
7、0 0 0 150销量 /件 250 200 200 650 650（6）某公司在三个地方有三个分厂，生产同一种产品，其产量分别为 300 箱、400 箱、500 箱。需要供应四个地方的销售，这四地的产品需求分别为 400 箱、250 箱、350 箱、200 箱。三个分厂到四个销地的单位运价如下表所示：甲 乙 丙 丁1 分厂 21 17 23 252 分厂 10 15 30 193 分厂 23 21 20 22 应如何安排运输方案,使得总运费为最小? 如果 2 分厂的产量从 400 箱提高到了 600 箱,那么应如何安排运输方案,使得总运费为最小? 如果销地甲的需求从 400 箱提高到 550
8、 箱,而其他情况都同, 那该如何安排运输方案,使得运费为最小?解:此运输问题的线性规划的模型如下minf=21X11+17X12+23X13+25X14+10X21+15X22+30X23+19 X24+23X31+21X32+20X33+22X34约束条件 ： X11+X12+X13 +X14=300X21+X22+X23+X24=400X31+X32+X33+X34=500X11+X21+X31=400X12+X22+X32=250X13+X23+X33=350X14+X24+X34=200Xij0(i=1,2,3;j=1,2,3,4)解：这是一个产大于销的运输问题，建立一个假想销地戊，得
9、到产销平衡如下表：甲 乙 丙 丁 戊 产量/箱1 分厂 21 17 23 25 0 3002 分厂 10 15 30 19 0 （400） 6003 分厂 23 21 20 22 0 500销量/箱 400 250 350 200 200 1400 1400解：这是一个销大于产的运输问题，建立一个假想销地 4 分厂，得到产销平衡如下表：甲 乙 丙 丁 产量/箱1 分厂 21 17 23 25 3002 分厂 10 15 30 19 4003 分厂 23 21 20 22 5004 分厂 0 0 0 0 150销量/箱 550 250 350 200 1350 13504（7）整数规划的图解法某
10、公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如下表所示：货物 每件体积/立方英尺 每件重量/百千克 每件利润/百元甲 195 4 2乙 273 40 3托运限制 1365 140甲种货物至多托运 4 件，问两种货物各托运多少件，可使获得利润最大？解：设 X1,X2 分别为甲、乙两种货物托运的件数，其数学模型如下所示：max z=2X1+3X2约束条件： 195X1+273X2 1365，4X1+40X2 140 ，X1 4，X1, X20，X1, X2 为整数。（8）指派问题有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表
11、所示：问应如何指派工作，才能使总的消耗时间为最少？A B C D甲 15 18 21 24乙 19 23 22 18丙 26 17 16 19丁 19 21 23 17解：引入 01 变量 Xij ，并令1，当指派第 i 人去完成第 j 项工作时；Xij =0，当不指派第 i 人去完成第 j 项工作时；此整数规划的数学模型为：min z=15X11+18X12+21X13+24X14+19X21+23X22+22X23+18 X24+26X31+17X32+16X33+19X34 +19X41+21X42+23X43+17X44约束条件： X 11+X12+X13 +X14=1（甲只能干一项工
12、作）X21+X22+X23+X24=1（乙只能干一项工作）X31+X32+X33+X34=1（丙只能干一项工作）5X41+X42+X43+X44=1（丁只能干一项工作）X11+X21+X31+X41=1（A 工作只能一个人干）X12+X22+X32+X42=1（B 工作只能一个人干）X13+X23+X33+X43=1（C 工作只能一个人干）X14+X24+X34+X44=1（D 工作只能一个人干）Xij 为 01 变量，(i=1,2,3，4;j=1,2,3,4)(9)有优先权的目标规划的图解法一位投资商有一笔资金准备购买股票，资金总额为 90000 元，目前可选的股票有 A、B 两种（可以同时
13、投资于两种股票） ，其价格以及年收益率和风险系数如下表所示：股票 价格/元 年收益/（元/年） 风险系数A 20 3 0.5B 50 4 0.2从表可知：股票 A 的收益率为（3/20）100%=15%,股票 B 的收益率为（4/50）100%=8%,A 的收益率比 B 大，但同时 A 的风险也比 B 大，这符合高风险高收益的规律。试求一种投资方案，使得一年的总投资风险不高于 700，且投资收益不低于 10000 元。解：设 X1、X 2 分别表示投资商所购买的股票 A 和股票 B 的数量。1.针对优先权最高的目标建立线性规划建立线性规划模型如下：min d1+约束条件：20X 1+50X2
14、900000.5X1+0.2X2-d1+d1- =7003X1+4X2-d2+d2- =10000X1 , X2 , d1+ , d2- 02.针对优先权次高的目标建立线性规划建立线性规划模型如下：min d2-约束条件： 20X 1+50X2 900000.5X1+0.2X2-d1+d1- =7003X1+4X2-d2+d2- =10000d1+=0X1 ， X2 ，d 1+ ，d 1- ，d 2+，d 2- 03.目标规划模型的标准化0.5X1+0.2X2 =70020X1+50X2 900000 50003000200010001000200030004000 40004000X1X12
15、0X1+50X2 900001000 500040003000200001000200030004000X26对于两个不同优先权的目标单独建立线性规划进行求解，为方便，把他们用一个模型来表达：min P1(d1+)+P2(d2-)约束条件： 20X 1+50X2 90000 ，0.5X1+0.2X2-d1+d1- =700，3X1+4X2-d2+d2- =10000，X1 ， X2 ，d 1+ ，d 1- ，d 2+，d 2- 0。（10）某工厂试对产品 A、B 进行生产，市场需求并不是很稳定，因此对每种产品分别预测了在销售良好和销售较差时的预期利润，这两种产品都经过甲、乙两台设备加工，已知产
16、品 A 和 B 分别在甲和乙设备上的单位加工时间，甲、乙设备的可用加工时间以及预期利润如表所示，要求首先是保证在销售较差时，预期利润不少于 5 千元，其次是要求销售良好时，预期销售利润尽量达到 1 万元。试建立目标规划模型。A B 可用时间甲 4 3 45乙 2 5 30销售良好时的预期利润（元/件） 8 6 100销售较差时的预期利润（元/件） 5 5 50解：设工厂生产 A 产品 X1 件，生产 B 产品 X2 件。按照生产要求，建立如下目标规划模型:min P1(d1+)+P2(d2-)约束条件：4X1+3X2 45 ，2X1+5X2 305X1+5X2-d1+d1- =50，8X1+6
17、X2-d2+d2- =100，X1 ， X2 ，d i+ ，d i- 0.i=1,2(11)动态规划石油输送管道铺设最优方案的选择问题：如图所示，其中 A 为出发点，E 为目的地，B 、C、D 分别为三个必须建立油泵加压站的地区，其中的B1、B 2、B 3;C1、C 2、C 3;D1、D 2 分别为可供选择的各站站点。图中的线段表示管道可铺设的位置，线段旁的数字为铺设管线所需要的费用，问如何铺设管道才使总费用最小？6 2 3 3 5 7 44235 3 5AB1B2 B3C1C2C3D1D2E74 44 1 5 45 解：第四阶段：D 1E 3；D 2E 4；第三阶段：C 1D1E 5；C 2
18、D2E 8；C 3D1E 8；C 3D2E 8；第二阶段：B 1C1D1E 11；B 1C2D2E 11；B 2C1D1E 8；B3C1D1E 9 ；B 3C2D2E 9；第一阶段：AB 1C1D1E 14；AB 1C2D2E 14；AB2C1D1E 13；AB 3C1D1E 13；AB3C2D2E 13；最优解：A B 2C 1D 1E；A B 3C 1D 1E；AB 3C 2D 2E最优值：13（12）最小生成树问题 某大学准备对其所属的 7 个学院办公室计算机联网，这个网络的可能联通的途径如图所示，图中 V1， ，V7 表示 7 个学院办公室，图中的边为可能联网的途径，边上的所赋权数为这
19、条路线的长度，单位为百米。请设计一个网络能联通 7 个学院办公室，并使总的线路长度为最短。584723431031V7 V4V5V6V1V2 V3G 5847234331V7 V4V5V6V1V2 V3G1 解：在 G 中找到一个圈（V 1，V 7，V 6，V 1）,并知在此圈上边 V1，V 6的权数 10 为最大，在 G 中去掉边V 1，V 6得图 G1 ，如上图所示85472343131V7 V4V5V6V1V2 V3G2 472343131V7 V4V5V6V1V2 V3G3 在 G1 中找到一个圈（V 3，V 4，V 5，V 7，V 3） ，去掉其中权数最大的边 V4， V5，得图 G
20、2 ，如上图所示在 G2 中找到一个圈（V 2，V 3，V 5，V 7，V 2） ，去掉其中权数最大的边V5， V7，得图 G3 ，如上图所示72343131V7 V4V5V6V1V2 V3G47233131V7 V4V5V6V1V2 V3G5在 G3 中找到一个圈（V 3，V 5，V 6，V 7，V 3） ，去掉其中权数最大的边V5， V6，得图 G4 ，如上图所示在 G4 中找到一个圈（V 2，V 3， V7，V 2） ，去掉其中权数最大的边V3， V7，得图 G5 ，如上图所示在 G5 中已找不到任何一个圈了，可知 G5 即为图 G 的最小生成树。这个最小生成树的所有边的总权数为 3+3
21、+3+1+2+7=19(13)某一个配送中心要给一个快餐店送快餐原料，应按照什么路线送货才能使送货时间最短。下图给出了配送中心到快餐店的交通图，图中 V1， ，V7 表示 7 个地名，其中 V1 表示配送中心，V7 表示快餐店，点之间的联线表示两地之间的道路，边所赋的权数表示开车送原料通过这段道路所需要的时间（单位：分钟）V4（16,2）（0,S）5V26V26V28V27V22V212V216V218V24V2V1 V7（快餐店）（配送中心）V5V3V6V2解： 给起始点 V1 标号为（0，S）I=V 1,J= V2，V 3，V 4，V 5，V 6 ,V7 ，边的集合 Vi，V j V i，
22、V j 两点中一点属（18,3）（4,1）（24,3）（25,4）（27,5）9于 I,而另一点属于 J= V1，V 2， V1，V 3，并有S12=L1+C12=0+4=4 ； S13=L1+C13=0+18=18min (S12,S13)= S12 =4给边 V1，V 2中的未标号的点 V2 标以（4 ，1） ，表示从 V1 到 V2 的距离为 4，并且在 V1 到 V2 的最短路径上 V2 的前面的点为 V1.这时 I=V1 ，V 2,J=V3，V 4，V 5，V 6 ,V7，边的集合V i，V j V i，V j 两点中一点属于 I,而另一点属于 J= V1，V 3， V2，V 3，
23、V 2，V 4，并有S23=L2+C23=4+12=16 ；S 24=L2+C24=4+16=20 ；min (S 23,S24 , S13)= S23 =16给边 V2，V 3中的未标号的点 V3 标以（16 ，2）这时 I=V1 ，V 2 ，V 3,J=V4，V 5，V 6 ,V7，边的集合V i，V j V i，V j 两点中一点属于 I,而另一点属于 J= V2，V 4， V3，V 4， V 3，V 5，并有S34=L3+C34=16+2=18 ； S35=L3+C35=16+6=22 ； S24=L2+C24=4+16=20min (S34,S35,S24)= S34 =18给边 V
24、3，V 4中的未标号的点 V4 标以（18 ，3）这时 I=V1 ，V 2 ，V 3 ，V 4,J=V5，V 6 ,V7，边的集合V i，V j V i，V j 两点中一点属于 I,而另一点属于 J= V4，V 6， V4，V 5， V3，V 5，并有S46=L4+C46=18+7=25 ； S45=L4+C45=18+8=26 ；min (S 46,S45 ,S35)= S35 =24给边 V3，V 5中的未标号的点 V5 标以（24 ，3）这时 I=V1 ，V 2 ，V 3 ，V 4 ，V 5 ,J= V6 ，V 7，边的集合V i，V j V i，V j两点中一点属于 I,而另一点属于
25、J= V5，V 7， V4，V 6 ，并有S57=L5+C57=22+5=27 ；min (S57,S46)= S46 =25给边 V4，V 6中的未标号的点 V6 标以（25 ，4）这时 I=V1 ，V 2 ，V 3 ，V 4 ，V 5 ，V 6 ,J= V7，边的集合V i，V j V i，V j两点中一点属于 I,而另一点属于 J= V5，V 7， V6，V 7 ，并有S67=L6+C67=25+6=31 ；min (S57,S67)= S57 =27给边 V5，V 7中的未标号的点 V7 标以（27 ，5）此时 I=V1 ，V 2 ，V 3 ，V 4 ，V 5 ，V 6 ，V 7,J=
26、空集，边集合V i，V j V i， Vj 两点中一点属于 I,而另一点属于 J=空集，计算结束。得到最短路。从 V7 的标号可知从 V1 到 V7 的最短时间为 27 分钟。即：配送路线为： V1 V 2 V 3 V 5 V 7（14）最小生成树问题某电力公司要沿道路为 8 个居民点架设输电网络，连接 8 个居民点的道路图如图所示，其中 V1，V 8 表示 8 个居民点，图中的边表示可架设输电网络的道路，边上的赋权数为这条道路的长度，单位为公里，请设计一个输电网络，联通这 8 个居民点，并使总的输电线路长度为最短 。10275623432524V8V7V6V5V4V3V1V2G在图中找到一个
27、圈（V 1，V 2，V 5，V 3）,并知在此圈上边V 1，V 2和V3， V5的权数 4 为最大，在图中去掉边V 1，V 2 ；在图中找到一个圈（V 3，V 4，V 8 ，V 5 ，V 3, V1） ，去掉其中权数最大的边V4， V8；在图中找到一个圈（V 3，V 4， V5，V 3） ，去掉其中权数最大的边 V4，V 5；在图中找到一个圈（V 5，V 2，V 6，V 7 ，V 5） ，去掉其中权数最大的边V2， V6；在图中找到一个圈（V 5，V 7， V8，V 5） ，去掉其中权数最大的边 V5，V 8。在图中已找不到任何一个圈了，可知此即为图 G 的最小生成树。这个最小生成树的所有边的总权数为 2+2+4+2+3+3+2=18（15）最大流问题某地区的公路网如图所示，图中 V1，V 6 为地点，边为公路，边上所赋的权数为该段公路的流量（单位为千辆/小时） ，请求出 V1 到 V6 的最大流量。 65125641066V6V5V2V4V1V38解：第一次迭代：选择路为 V1 V 3 V 6 。弧（V 3 ，V 6）的顺流流量为 5，决定了 pf=5，改进的
