《运筹学》试题A卷(09-10.2)

重庆邮电大学2009~2010学年2学期 《运筹学》试卷（期末）（A卷）（闭卷）

一、（25分）已知某线性规划问题如下，要求：

MaxZ?2x1?3x2?5x3?x1?x2?5x3?7 ?s.t.?2x1?5x2?x3?10?x，x，x?0?123（1）写出下列线性规划模型的对偶问题；（5分） （2）用大M法求解下列线形规划问题；（15分）

（3）求b1的对偶价格，以及令对偶价格不变的b1的范围。（5分） 二、（15分）已知某运输问题3个产地到3个销售地的单位运价如下表所示，试用表上

作业法求解最优调运方案。 销地 产地 A1 A2 A3 销量 B1 5 1 8 20 B2 4 6 3 5 B3 2 7 9 15 产量 15 25 20 三、（20分）某工程建设项目拟指派甲等人完成A、B、C、D四项工作，已知甲可以承担两项，乙必须承担一项，丙、丁每人最多承担一项，每个人完成各项工作的利润矩阵如下表所示，试用匈牙利法求解利润最高的指派方案。

甲 乙 丙 丁 A 4 7 3 6 B 6 5 9 3 C 3 2 5 4 D 8 6 7 4 四、（20分）现有一个可装5千克的背包，装入无数量限制的A、B、C三种物品，其

单位重量和价值如下表所示。试用动态规划方法求解价值最高的装入方案。

A B C

单位重量 2 3 1 单位价值 65 80 30 五、（20分）试用图与网络模型所学的方法求解A点至T点的最短路径。

A B C D E 6 3 4

F K 2 2 3 1 9 5 G L 3 9 2 5 7 7 H M 2 8 1 9 6 2 I N 9 5 3 5 6 4 J O

P 4 Q 6 R 7 S 4 T

重庆邮电大学2011~2012学年2学期 《运筹学》试卷（期末）（A卷）（闭卷）

一、已知线性规划问题：

minf?2x1?3x2?x3?x1?4x2?2x3?8 ?st.?3x1?2x2?6?x,x,x?0?123（1） 试用单纯形法求解上述线性规划问题（15分） （2） 对b1做灵敏度分析（10分）

二、某公司有甲、乙、丙三个产地和A、B、C三个销地，其产地与销地之间单位运价（万元）及产销量如下表所示：但是如果没有完全满足销地的需求，则A、B、C三个销地每吨将分别损失5、9、2万元。用表上作业法求解最优调运方案（20分）

单位运费 甲 乙 丙 销量（吨） A 5 6 3 75 B 1 4 8 20 C 7 6 5 15 产量（吨） 10 80 15

三、某企业拟将5台设备分配给甲、乙、丙三个厂，各厂获得设备后利润如

下，试用动态规划的方法求总利润最大的方案（15分）

0 1 2 3 4 5 甲 0 3 7 9 12 13 乙 0 5 10 11 11 11 丙 0 4 6 11 12 13

四、现有甲、乙、丙三人去完成A、B、C、D四项工作其所花时间的效率矩阵如下：要求甲做0～2项工作，乙做1～2项工作，丙做1项工作。试用匈牙利法求解最高效率的分配方案。（25分）

效率 A B C D 甲 5 3 2 6 乙 2 1 7 4 丙 6 8 7 2

五、利用最大流最小割定理求解下列网络的最大流量；其中点1为发点，点5为收点；弧上权重分别为容量和实际流量（15分）

2 (6，2) 1 (7，4) (4，1) (8，5) (3，3) 3 (2，1) (4，2) 4 (7，0) 5

重庆邮电大学2010~2011学年2学期 《运筹学》试卷（期末）（B卷）（闭卷）

一、（25分）某工厂生产甲、乙、丙三种产品，已知有关数据如下表所示，试分别回答下列问题： 产品 原料 A B 单件利润（元） 甲 6 3 4 乙 3 4 1 丙 5 5 5 原料拥有量 （千克） 45 30 （1）建立线性规划模型，求使该厂获利最大的生产计划；（15分）

（2）若产品乙、丙的单件利润不变，则产品甲的利润在什么范围内变化时，上述最优解不变？（5分）

（3）若有一种新产品丁，其原料消耗定额：A为5个单位，B为2个单位，单件利润为2.5元，那么该种产品是否值得安排生产？（5分） 二、（10分）写出下列线性规划问题的对偶问题：

nmaxz??cj?1jxj?n??aijxj?bi(i?1,?,m1)?j?1?n??aijxj?bi(i?m1?1,?,m2)?j?1?nst.?aijxj?bi(i?m2?1,?,m)??j?1?xj?0(j?1,?,n1)??xj?0(j?n1?1,?,n2)??xj无约束(j?n2?1,?,n)?

三、（20分）已知某运输问题的产销平衡表与单位运价表如下表所示，试运用表上作业法求解其最优调拨方案。 销地 产地 A 10 2 1 3 B 20 10 20 5 C 5 10 7 4 D 9 30 10 6 E 10 6 4 3 产量 9 4 8 甲 乙 丙 销量

四、6人完成4项工作，所得利润矩阵估计如下，规定每人只能做一项工作，每项工作只能有一人完成，试用匈牙利法求解利润最大的指派方案（15分） 1 2 3 4 5 6 1 3 6 8 10 12 13 2 5 7 9 10 11 12 3 4 6 8 9 10 11 4 5 8 10 11 12 13

五、公司对某型号产品的A、B、C三种部件的进行改进，由于资金不足三种部件失败的概率分别为0.40，0.60，0.80，有一种部件失败，则产品改进将失败；后增加拨款2万元以提高其成功率，关系如下表，试用动态规划的方法求解成功概率最高的资金分派方案（15分）

0 1万元 2万元 VS

A 0.40 0.20 0.15 B 0.60 0.40 0.20 C 0.80 0.50 0.30 六、试用最大流最小割定理求解下面网络的最大流量（15分） V1 （5，5）

（7，3）

V4

（3，2） （10，8）

（8，5） （5，3）

Vt （3，0） V2 （3，0） （6，3） （2，0）

V3

（9，3）

V5

（5，3）

本文来源：https://www.bwwdw.com/article/4epa.html