运筹学作业题

华南理工大学网络教育学院。

2013–2014学年度第一学期。

运筹学》作业。

1. 某工厂用abcd四种原料生产甲乙两种产品，生产甲和乙所需的各种原料的数量及在一个计划期内各种原料的现有数量见下表。又知每单位产品甲乙分别可获利400元和600元，设一个计划期内生产甲种产品个单位，乙种产品个单位，试写出以总利润为目标的线性规划模型，并化为标准型。

答案：， 2.某厂在计划期内要安排生产ⅰ、ⅱ两种产品，已知生产单位产品所需的设备台时及a、b两种原材料的消耗，如下表所示：

每生产一件产品i可获利1元，每生产一件产品ii可获利3元，如何安排生产计划使获利最大？（有多种方法选择您熟悉的一种）（10分）

解，由**法求出可行域各顶点的值比较，得安排生产ⅰ产品2件，、ⅱ产品3件，获利最大为11元。或加松弛变量用单纯形表计算。

3、用单纯形法求解。

解先化为标准形式，再列单纯形表计算如下。

得到最优解为。

4、写出线性规划问题的对偶问题。

解对偶问题为。

5、已知线性规划问题。

用单纯形法求解，得到最终单纯形表如下。试求出各待定常数的值。解从而。

再由，从而。

解得。6、已知线性规划问题，其对偶问题的最优解为，试用对偶问题的性质，求原问题的最优解。

解原问题的对偶问题为，将代入第。

一、二个约束成为严格等式，由互补松弛性质得。又因，由互补松弛性质，进而可得，解之。原问题的最优解为，最优值为44。

7、已知世界6大城市：pe，pa，t，m，n，l。试在下表所示交通网络的数据中确定最小树。

解将题设中的表用图表示。

采用避圈法，寻找最小边的过程如下：

最后找到的构成最小支撑树如图所示。

8、某厂使用一台设备，在每年初，您作为厂长就要决定是购置新的，还是继续使用旧的。若置新的，就支付一定的购置费用；若继续使用旧的，则要支付一定的维修费。问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少，以五年为一个计划期，若已知该设备在各年初的**预计为：

使用不同时间设备所需的维修费用为：

显然不同的购置方案，有不同的结果，如何选择最佳方案？

用dijkstra 算法求：在点标，在点标，再算在标上，算在标上，算在标上，算在标上，最短路长32+42=74。

9.某单位秋天要决定冬季取暖用煤的储量问题。在正常的冬季要消耗15吨煤，在较暖与较冷的气温条件下要消耗10吨和20吨。

假定冬季时在较暖、正常、较冷的气候条件下每吨煤价分别为100元，150元和200元，又设秋季时煤价为每吨100元。秋季储煤多少吨为好？

这一储量问题可以看成是一个对策问题，把采购员当作局中人ⅰ，他有三个策略：在秋天时买10吨、15吨与20吨，分别记为

把大自然看作局中人ⅱ(可以当作理智的局中人来处理)，大自然有三种策略：出现较暖、正常与较冷的冬季，分别记为。

把该单位冬季取暖用煤实际费用(即秋季购煤时的用费与冬季不够时再补购的费用总和，例如： )作为局中人ⅰ的赢得，得矩阵如下：

故对策的解为，即秋季储煤20吨合理．

9.运用所学的对策论知识帮助单位秋天要决定冬季用煤的储量问题。在正常的冬季要消耗15吨煤，在较暖与较冷的气温条件下要消耗10吨和20吨。

假定冬季时在较暖、正常、较冷的气候条件下每吨煤价分别为100元，150元和200元，又设秋季时煤价为每吨100元。秋季储煤多少吨为好？

解这一储量问题可以看成是一个对策问题，把采购员当作局中人ⅰ，他有三个策略：在秋天时买10吨、15吨与20吨，分别记为

把大自然看作局中人ⅱ(可以当作理智的局中人来处理)，大自然有三种策略：出现较暖、正常与较冷的冬季，分别记为。

把该单位冬季取暖用煤实际费用(即秋季购煤时的用费与冬季不够时再补购的费用总和，例如： )作为局中人ⅰ的赢得，得矩阵如下：

故对策的解为，即秋季储煤20吨合理．

10. “二指莫拉问题”：甲乙两人游戏，每人出一个或两个指头，同时又把猜测对方所出的指数叫出来。

如果只有一个人猜测正确，则他所赢得的数目为两人所出的指数之和，否则重新开始，写出该对策中各局中人的策略集合及甲的赢得矩阵，并回答局中人是否存在某种出法比其他出法更为有利？

解甲乙两人的策略集合为。根据题意，甲的赢得矩阵为。

根据赢得矩阵，有。

因为，所以局中人是不存在某种出法比其他出法更为有利。