ltc运筹学作业题a.doc

（ 密 封 线 内 不 答 题 ） 教学中心： 专业层次： （ 密 封 线 内 不 答 题 ） 教学中心： 专业层次： 姓名： 学号： 座号： 教学中心： 专业层次： 教学中心： 专业层次： 姓名： 学号： 座号： 《 运筹学 》作业 1. 某工厂用ABCD四种原料生产甲乙两种产品，生产甲和乙所需的各种原料的数量及在一个计划期内各种原料的现有数量见下表。又知每单位产品甲乙分别可获利400元和600元，设一个计划期内生产甲种产品个单位，乙种产品个单位，试写出以总利润为目标的线性规划模型，并化为标准型。 产品 所需原料 A B C D 甲 乙 4 4 4 2 1 0 2 4 现有原料数量 28 20 32 24 答案： ， 2.某厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示： I II 总量 设备 1台时/件 2台时/件 8台时 原材料A 4 kg/件 0 kg/件 16kg 原材料B 0 kg/件 4 kg/件 12kg 每生产一件产品I可获利1元，每生产一件产品II可获利3元，如何安排生产计划使获利最大？（有多种方法选择您熟悉的一种）（10分） 解 ，由图解法求出可行域各顶点的值比较，得安排生产Ⅰ产品2件，、Ⅱ产品3件，获利最大为11元。或加松弛变量用单纯形表计算。 3、用单纯形法求解 解 先化为标准形式，再列单纯形表计算如下 1 2 1 0 0 CB 基XB 常数 0 15 2 -3 2 1 0 0 20→ 1/3 1 5 0 1 ，检 0 1 2↑ 1 0 0 0 75→ 3 0 17 1 3 0 20 1/3 1 5 0 1 ，检验数 -40 1/3↑ 0 -9 0 -2 0 25 1 0 17/3 1/3 1 0 35/3 0 1 28/9 -1/9 2/3 最优了，检验数 -145/3 0 0 -98/9 -1/9 -7/3 得到最优解为 4、写出线性规划问题的对偶问题 解 对偶问题为 5、已知线性规划问题 用单纯形法求解，得到最终单纯形表如下。试求出各待定常数的值。 0 0 CB 基XB 常数 3/2 1 0 1 1/2 -1/2 2 1/2 1 0 -1 2 检验数 -3 0 0 0 -4 解 从而 再由，从而 ，解得 6、已知线性规划问题，其对偶问题的最优解为，试用对偶问题的性质，求原问题的最优解。 解 原问题的对偶问题为，将代入第一、二个约束成为严格等式，由互补松弛性质得。又因，由互补松弛性质，进而可得，解之。原问题的最优解为，最优值为44。 7、已知世界6大城市：Pe，Pa，T，M，N，L。试在下表所示交通网络的数据中确定最小树。 Pe T Pa M N L Pe 13 51 77 68 50 T 13 60 70 67 59 Pa 51 60 57 36 2 M 77 70 57 20 55 N 68 67 36 20 34 L 50 59 2 55 34 解 将题设中的表用图表示 采用避圈法，寻找最小边的过程如下： 最后找到的构成最小支撑树如图所示 8、某厂使用一台设备，在每年初，您作为厂长就要决定是购置新的，还是继续使用旧的。若置新的，就支付一定的购置费用；若继续使用旧的，则要支付一定的维修费。问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少，以五年为一个计划期，若已知该设备在各年初的价格预计为： 第1年 第2年 第3年 第4年 第5年 21 21 22 23 24 　使用不同时间设备所需的维修费用为： 使用年数 0～1 1～2 2～3 3～4 4～5 维修费 5 6 9 14 21 显然不同的购置方案，有不同的结果，如何选择最佳方案？ 。 用Dijkstra 算法求：在点标，在点标，再算在标上，算在标上， 算在标上， 算在标上，最短路长32+42=74。 9.某单位秋天要决定冬季取暖用煤的储量问题。在正常的冬季要消耗15吨煤，在较暖与较冷的气温条件下要消耗10吨和20