运筹学作业题

《运筹学作业》第1页（共8页）华南理工大学网络教育学院2013–2014学年度第一学期《运筹学》作业1.某工厂用ABCD四种原料生产甲乙两种产品，生产甲和乙所需的各种原料的数量及在一个计划期内各种原料的现有数量见下表。又知每单位产品甲乙分别可获利400元和600元，设一个计划期内生产甲种产品1x个单位，乙种产品2x个单位，试写出以总利润为目标的线性规划模型，并化为标准型。产品所需原料ABCD甲乙44421024现有原料数量28203224答案：12121211212max400600442822203224240,0Zxxxxxxxxxxx，1212312415126123456max40060044282220322424,,,,,0Zxxxxxxxxxxxxxxxxxxx2.某厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示：III总量设备1台时/件2台时/件8台时原材料A4kg/件0kg/件16kg原材料B0kg/件4kg/件12kg每生产一件产品I可获利1元，每生产一件产品II可获利3元，如何安排生产计划使获利最大？（有多种方法选择您熟悉的一种）（10分）教学中心：专业层次：姓名：学号：座号：（密封线内不答题）教学中心：专业层次：姓名：学号：座号：x2x18O2321446《运筹学作业》第2页（共8页）解12121212max328416412,0Zxxxxxxxx，由图解法求出可行域各顶点的z值比较，得安排生产Ⅰ产品2件，、Ⅱ产品3件，获利最大为11元。或加松弛变量用单纯形表计算。3、用单纯形法求解123123123123max22321515203,,0Zxxxxxxxxxxxx解先化为标准形式1231234123512345max22321515203,,,,0Zxxxxxxxxxxxxxxxx，再列单纯形表计算如下jc12100CB基XB常数1x2x3x4x5x04x152-321005x20→1/31501201，检jjCZ012↑10004x75→30171305x201/31501752031/3，检验数-401/3↑0-90-204x251017/31/3105x35/30128/9-1/92/3最优了，检验数-145/300-98/9-1/9-7/3得到最优解为3514525,,0,0,0,max33TXZ《运筹学作业》第3页（共8页）4、写出线性规划问题1234123412413341234max23543253274..23460;,0;Zxxxxxxxxxxxstxxxxxxxx无符号限制的对偶问题解对偶问题为12312312313123123min54+64y322233..3452710;0;wyyyyyyyystyyyyyyyy无符号限制5、已知线性规划问题1122331311121123452321222max10010,1,2,3,4,5jZcxcxcxaaabxxxxxaaabxj用单纯形法求解，得到最终单纯形表如下。试求出各待定常数的值。jc1c2c3c00CB基XB常数1x2x3x4x5x3c3x3/21011/2-1/22c2x21/210-12检验数jjCZ-3000-4解11132321/21/21/21/241,,,121221BPPBPP1111213122122233/210121/210baaaBbaaa从而11112132212223413/210189/2142121/21055/212baaabaaa再由113211/21/2,0,0,3,0,41/212NNBCCBNccc，从而《运筹学作业》第4页（共8页）13232321113,0,24222ccccccc，解得2314,8,7ccc6、已知线性规划问题12341341123421234max25628..22212,,,0Zxxxxxxxystxxxxyxxxx对偶变量，其对偶问题的最优解为**124,1yy，试用对偶问题的性质，求原问题的最优解。解原问题的对偶问题为12122121212min81222221..5260,0wyyyyystyyyyyy，将**124,1yy代入第一、二个约束成为严格等式，由互补松弛性质得**120,0xx。又因**120,0yy，由互补松弛性质，进而可得34348212xxxx，解之**344xx。原问题的最优解为*0,0,4,4TX，最优值为44。7、已知世界6大城市：Pe，Pa，T，M，N，L。试在下表所示交通网络的数据中确定最小树。PeTPaMNLPe1351776850T1360706759Pa516057362M7770572055N6867362034L505925534解将题设中的表用图表示采用避圈法，寻找最小边的过程如下：[,][,][,][,][,]21320345012345|LPaPeTNMLNPeL最后找到的[,],[,],[,],[,],[,]LPaPeTNMLNPeL构成最小支撑树如图所示68552777067595136605720345013PeTPaMLN13503420576036515967707725568NLMPaTPe《运筹学作业》第5页（共8页）135034202NLMPaTPe213503420119WT8、某厂使用一台设备，在每年初，您作为厂长就要决定是购置新的，还是继续使用旧的。若置新的，就支付一定的购置费用；若继续使用旧的，则要支付一定的维修费。问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少，以五年为一个计划期，若已知该设备在各年初的价格预计为：第1年第2年第3年第4年第5年2121222324使用不同时间设备所需的维修费用为：使用年数0～11～22～33～44～5维修费5691421显然不同的购置方案，有不同的结果，如何选择最佳方案？12131321526,215632,21569411616215691455,21569142176ww2324252621526,215632,2156941,21569145534353622527,225633,225694245465623528,235634,24529。用Dijkstra算法求：在点1v标0,0，在点2v标1,26v，再算min32,,262632在3v262627282932415534324155764233v6v1v2v3v4v5334276554132345541322928272626v1v6v2v3v4v5《运筹学作业》第6页（共8页）标上1(,32)v，算min3227,2632,4141在4v标上1(,41)v，算min2641,3233,4128,5555在5v标上1(,55)v，算min2655,3242,4134,5529,7674在6v标上3(,74)v，最短路长32+42=74。(0,0)(v3,74)(v1,55)(v1,41)(v1,32)(v1,26)262627282932415534324155764233v6v1v2v3v4v59.某单位秋天要决定冬季取暖用煤的储量问题。在正常的冬季要消耗15吨煤，在较暖与较冷的气温条件下要消耗10吨和20吨。假定冬季时在较暖、正常、较冷的气候条件下每吨煤价分别为100元，150元和200元，又设秋季时煤价为每吨100元。秋季储煤多少吨为好?这一储量问题可以看成是一个对策问题，把采购员当作局中人Ⅰ，他有三个策略：在秋天时买10吨、15吨与20吨，分别记为把大自然看作局中人Ⅱ(可以当作理智的局中人来处理)，大自然有三种策略：出现较暖、正常与较冷的冬季，分别记为把该单位冬季取暖用煤实际费用(即秋季购煤时的用费与冬季不够时再补购的费用总和，例如：1750=10100+15-10150)作为局中人Ⅰ的赢得，得矩阵如下：冷常暖321201510321200020002000250015001500300017501000200020002000250015001500300017501000200025003000min200015001000max2000maxminminmax33aaaijijjiji33()，《运筹学作业》第7页（共8页）故对策的解为，即秋季储煤20吨合理．9.运用所学的对策论知识帮助单位秋天要决定冬季用煤的储量问题。在正常的冬季要消耗15吨煤，在较暖与较冷的气温条件下要消耗10吨和20吨。假定冬季时在较暖、正常、较冷的气候条件下每吨煤价分别为100元，150元和200元，又设秋季时煤价为每吨100元。秋季储煤多少吨为好?解这一储量问题可以看成是一个对策问题，把采购员当作局中人Ⅰ，他有三个策略：在秋天时买10吨、15吨与20吨，分别记为把大自然看作局中人Ⅱ(可以当作理智的局中人来处理)，大自然有三种策略：出现较暖、正常与较冷的冬季，分别记为把该单位冬季取暖用煤实际费用(即秋季购煤时的用费与冬季不够时再补购的费用总和，例如：1750=10100+15-10150)作为局中人Ⅰ的赢得，得矩阵如下：故对策的解为，即秋季储煤20吨合理．10.“二指莫拉问题”：甲乙两人游戏，每人出一个或两个指头，同时又把猜测对方所出的指数叫出来。如果只有一个人猜测正确，则他所赢得的数目为两人所出的指数之和，否则重新开始，写出该对策中各局中人的策略集合及甲的赢得矩阵，并回答局中人是否存在某种出法比其他出法更为有利？解甲乙两人的策略集合为{出1猜1，出1猜2，出2猜1，出2猜2}。根据题意，甲的赢得矩阵为0230200330040340A根据赢得矩阵，有冷常暖321201510321200020002000250015001500300017501000200020002000250015001500300017501000200025003000min200015001000max2000maxminminmax33aaaijijjiji33()，《运筹学作业》第8页（共8页）出1猜1出1猜2出2猜1出2猜2minijja出1猜102-30-3出1猜2-2003-2出2猜1300-4-4出2猜20-340-3maxijia3243因为maxmin2,minmax2,maxminminmaxijijijijjjjjiiiiaaaa，所以局中人是不存在某种出法比其他出法更为有利。