运筹学试题

浙江工业大学 / 学年

第一学期期终试卷( )

课程 《运筹学》 姓名 班级 学号 题序 一 二 计分 三 四 五 六 七 八 九 十 总评

一、判断题（共20分，每小题2分）

1．线性规划问题的最优解一定是基础最优解。 （ ） 2．线性规划问题如果有最优解，一定有基础最优解。 （ ） 3．如果线性规划原问题和对偶问题都有可行解，则原问题和对偶问题一定具有有限最优解。 （ ） 4．若线性规划的原问题有无穷多个最优解，则其对偶问题也一定有无穷多个最优解。（ ） 5．已知yi*为线性规划的对偶问题的最优解，若yi* = 0，说明在最优生产计划中第i种资源

一定有剩余。 （ ） 6．在任一图G中，当点集V确定后，树图是G中边数最少的连通图。 （ ） 7．求网络最大流的问题可归结为求解一个线性规划模型。 （ ） 8．整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函数值。 （ ） 9．矩阵对策的对策值相当于进行若干次对策后局中人I的平均赢得值或局中人II的平均损失值。 （ ） 10．在运输问题中，只要给出一组含（m+n-1）个非零的{Xij}，且满足?Xij = ai，?Xij

j?1nmi?1= bj，就可以作为一个初始基可行解。 （ ）

二、计算题（20分）某公司制造三种产品A、B、C，需要两种资源（劳动力和原材料），要求确定总利润最大的最优生产计划。该问题的线性规划模型如下： max Z = 3X1 + X1 + 5X1

s．t． 6X1 + 3X2 + 5X3 ? 45 （劳动力） 3X1 + 4X2 + 5X3 ? 30 （原材料）

X1 ，X2 ，X3 ? 0

其中X1 ，X2 ，X3 分别是产品A、B、C的产量。这个线性规划问题的最终单纯形表如下：

CB 3 5 Ci XB X1 X3 Cj - Zj b 5 3 3 2 5 0 0 X1 X2 X3 X4 X5 1 -1/3 0 1/3 -1/3 0 1 1 -1/5 2/5 0 -3 0 0 -1 （1） 求出使得最优解不变的产品A的单位利润变化范围，并问当C1=2时最优解变不变？ （2） 假定能以10元的代价增加15个单位的材料，这样做法是否有利？ （3） 求出使劳动力对偶价格不变的b2的变化范围。

（4） 由于技术上的突破，每单位产品B原材料的需要量减少为2个单位，这时是否需要

改变生产计划？ （5） 假如这时，又试制成新产品D，生产一个单位新产品D需要劳动力4单位，原材料

3单位，而每单位的新产品D的利润为3元。请问这时生产计划是否要进行修改？

如要修改，新生产计划是什么？

三、计算题（本题20分）下表是某一个产销平衡运输问题的产销平衡表和单位运价表，表中给出了各产地和各销地的供应量和需求量，以及各产地至各销地的单位运价（单位：百元/吨） 销地 单位运价 产地 A1 A2 A3 销量（吨） B1 5 3 9 30 B2 13 11 6 60 B3 5 4 12 50 B4 12 10 7 60 产量（吨） 70 40 90 200 200 （1） 已知：X13 = 40，X14 = 30，X21 = 30，X23 = 10，X32 = 60，X34 = 30，其它 Xij = 0。试问该调运方案是否为最优调运方案？若不是，请给出最优调运方案。

（2） 若产地A2 减少15吨的供应量，并且设销地B2 需求量必须保证满足，此时销地B1 、

B3 、B4 的需求量相应地受产地A2 供应量减少的影响。试写出此时该运输问题的产

销平衡表和单位运价表（不必求解）。

四、计算题（20分）

某公司职工因工作需要购置了一台摩托车。他可以连续使用或于任一年末将旧车卖掉换一辆新的车，下表中列出了于第i年末购置或更新的车至第j年末的各项费用的累计（含更新所需费用，运行费及维修费），试据此确定该人最佳的更新策略，使从第1年末至第5年末的各项费用的累计和为最小。 （单位：万元）

1 2 0.4 3 0.54 0.43 4 0.98 0.62 0.48 5 1.37 0.81 0.71 0.49 2 3 4 （1） 把这个问题化成一个最短路问题。 （2） 用标号法求解最优更新方案。

五、计算题（20分）

某小区两家超市相互竞争，超市A有4个广告策略，超市B也有4个广告策略。已经算出当双方采取不同的广告策略时，A方所占的市场份额增加的百分数如下：

α1 α2 α3 α4 β1 3 0 4 -5 β2 0 6 -2 -1 β3 4 -1 3 8 β4 -2 -3 5 7 （1） 写出此对策问题的三要素。

（2） 请将此对策问题对策双方的最优策略表示为一个互为对偶的线性规划模型。

运筹学试卷5答案

一、判断题（共20分，每小题2分）

1． X 2． √ 3． √ 4． √ 5． √ 6． √ 7． √ 8． √ 9． X 10． X 二、（本题20分，每小题4分）

（1） 产品A的单位利润变化范围为：3 ? C1 ? 6；当C1 = 2时，最优解不变。 （2） 增加的原材料单位价格为10/15 = 2/5 < 影子价格 = 1，这样做是有利的。 （3） b2 的变化范围为：22.5 ? b2 ? 45. （4） ?2 = 3 – (3,5)??1/3??1/5?1/3??1/5?1/3??3????= -1 < 0，不需要改变生产计划。 2/5??2??1/3??4????= 1 > 0，此时生产计划需要修改。 2/5??3?（5） ?6 = 3 – (3,5)?

三、（本题20分）

（1） 该调运方案不是最优调运方案，最优调运方案为：X13 = 50，X14 = 20，X21 = 30，X24 = 10，X32 = 60，X34 = 10，Xij = 0。 （10分）

（2）此时的产销平衡表与单位运价表为： （10分） 销地 单位运价 产地 A1 A2 A3 A4（虚拟） 销量（吨） B1 5 3 9 0 30 B2 13 11 6 M 60 B3 5 4 12 0 50 B4 12 10 7 0 60 产量（吨） 70 25 90 15 200 200 四、（本题20分）

（1） 本问题可以化成如下等价的求节点v1到v5的最短路问题。 （10分）

（2） 最优更新方案是第一年年初和第2年年购置新的牵引车，总费用为1.21万元，最省。

（10分）

五、（本题20分）

（1）对策问题的三要素为局中人、策略集、赢得矩阵，即（10分） G = { I，II，S1，S2，A}

其中：I 为局中人超市A；II 为局中人超市B；

S1 ={α1 ，α2 ，α3 ，α4 }；

S2 = {β1，β?3?0A???4???52 ，β3 ，β4}；

06?2?14?138?2???3?。 5??7?（2）局中人I的最优混合策略为X =（x1，x2，x3，x4）/v，它是如下线性规划问题的解：

（5分）

min v =（x1 + x2 + x3 + x4） s．t．3x1 + x3 - 5x4 ? 1 6x2 - 2x3 - x4 ? 1

4x1 - x2 + 3x3 + 8x4 ? 1 -2x1 - 3x2 + 5x3 + 7x4 ? 1 x1 ，x2 ，x3 ，x4 ? 0

局中人II的最优混合策略为Y =（y1，y2，y3，y4）/w，它是如下线性规划问题的解：（5分） min w =（y1 + y2 + y3 + y4） s．t．3y1 + y3 - 2y4 ? 1 6y2 - y3 - 3y4 ? 1 4y1 - 2y2 + 3y3 + 5y4 ? 1 - 5y1 - y2 + 8y3 + 7y4 ? 1 y1 ，y2 ，y3 ，y4 ? 0

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