运筹学试题三
一.单项选择（在每小题的 4 个备选答案中，选出一个最合适的答案。将所选择的答案前 的字母填在括号内。每小题 2 分，共 12 分） 1.线性规划可行域的顶点一定 A.是最优解 C.是基可行解 （ ）
B.能表示为可行域其它两点的凸组合 D.不是基可行解
* *
2.已知一线性规划问题的第 3 种资源影子价格为 Y3 ( Y3 >0),则( A. 第 3 种资源是一种短缺资源. B. 第 3 种资源增加△b3，目标函数的净增量△Z= Y3*△b3. C. 如果该种资源的市场价格低于 Y3*，则应大量买进. D. 如果该种资源的市场价格高于 Y3*，则应将该种资源全部卖出.
第 5页
共 7页
六..(10)某公司打算在 A，B，C 三个不同的地区共设置 6 个销售点，每个地区至少设置 1 个销售点。根据市场预测部门估计，在不同的地区设置不同数量的销售店，每月可得到的 利润如下表所示。试问在各地区应如何设置销售点，才能使每月获得的总利润最大？ 销售店 地区 A B C
0 0 0 0
初 始 表
CB 0 0 0 21
XB X6 X7 X8 X5 X7 X4
最 终 表
0 20
-0.5 0.5 -1.5 0.5 -0.5 -0.5
Cj – Zj
-3
-1
-2
0
0
-1
0
-10
分析下列问题并给出答案： 1、 写出该问题的对偶最优解。 2、 为增加 2 个单位的利润，买入哪种资源的买入量最小，最小买入量是多少？ 3、 由于价格的变化,产品的单位利润发生变化,如果已知第四,第五种产品的单位利润不 变,问第一、二、三种产品利润在什么范围内同时变化,现在得到的最优解不变? 最优 值是否变化? 如果各产品的产量需要取整数, 试用割平面法求出整数最优解。
*
26 ，生成两个新分枝其数学模型分别 7
） 。停止分枝的 ， 它 ） 。 们 是
是（ 条 （ 件 有
）和（ 三 个
4.用动态规划方法解决实际问题，所选择的状态变量必须具有（ 这样建立的动态规划基本方程是一个（ 方程。
） 。 ）
5.目标规划中目标约束通过（ ）化成等式。 要求恰 好达到目标值的目标约束应将（ ）引入到总目标中，总目标是 求最小值。用单纯形法求解目标规划问题, 非基变量进基的条件是 （ ）并且（ ） 6．某线性规划问题，其中 xk 无符号限制，令 xk xk xk ，化成标准形式，用单纯形法
第 7 页 共 7 页
树林 1 1 2 3 4 5 6 7 8 0 1.3 2.1 0.9 1.7 1.8 2.3 1.5 2 1.3 0 0.9 1.8 1.2 2.6 2.3 1.1
两片树林之间的距离 3 2.1 0.9 0 2.6 1.7 2.5 1.9 1.0 4 0.9 1.8 2.6 0 0.7 1.6 1.5 0.9 5 1.7 1.2 1.7 0.7 0 0.9 1.7 0.8 6 1.8 2.6 2.5 1.6 0.9 0 0.6 1.0 7 2.3 2.3 1.9. 1.5 1.7 0.6 0 0.4 8 1.5 1.1 1.0 0.9 0.8 1.0 0.4 0
管理者现在需要确定哪些树林之间需要铺路，使得连接所有树林的路的总长度最短。
第 3页
共 7页
四． （10 分)今有某娱乐场设计了一种娱乐项目。娱乐场的机器作为博弈的一方，不公开地 给出一张红 3 或黑 4 的牌，参加游戏者作为一方，在手持的红 2 和黑 3 中选择一张。选择 后,公开机器给出的牌。若两人出牌的颜色相同，游戏者赢；若颜色不同，则游戏者输。 输，赢的值为两人牌上的点数和。 (钱的单位为百元) 试回答： 1． 写出游戏者的策略集，赢得矩阵。 2． 游戏者是否有最优纯策略？如果没有，写出双方的混合策略所满足的两组不等式。
第 4页
共 7页
五．(10 分) 沃斯泰克公司决定要生产三种新的产品.现在公司所属的五个工厂拥有生产余 力来进行新产品的生产.在工厂１,２,３,４,５,中第一种产品的单位生产成本为３6 美元,２ ９美元,３２美元,２８美元和２4 美元. 第二种产品的单位生产成本为 3５美元,４１美元, ４６美元, ４２美元, 4３ 美元.第三种产品只能在工厂１ ,２,３中进行生产 ,工厂４和５ 没有生产这种产品的能力 .第三种产品在工厂１ ,２,３中的单位生产成本为３８美元 ,３５ 美元,４０美元.销售预测表明,产品１,２,３每天必须分别生产 ６００, 3００, ８００个单 位.不管是单一产品还是产品组合,工厂１,２,３,４,５每天最多可以生产４００, ６００, 5 ００,3００, １００单位.假设拥有生产这些新产品能力的工厂可以在生产能力范围内生产 任何数量任何组合的产品.管理人员希望知道怎样安排这些新产品的生产才能使总生产成 本最小. 试用最小元素法给出一个初始生产方案并判断是否最优,如果不是最优,调整一次.
/ //
求 得 的 每 一 个 可 行 解 ， 都 一 定 有 xk xk = （
/ / /
）， 这 是 因 为 ）
（
第 2页
共 7页
三． (10 分) 瓦尔毫斯 （Wirehouse） 木材公司不久将在一大片区域的八片树林中砍伐树木。 因此，它必须建设一个土路系统，使得每一个树林都能达到其他任何一片树林，每两片树 林间的距离（单位：英里）如下所示。
1 8 12 10
2 13 14 16
3 20 19 18
4 28 24 26
1．建立该问题动态规划数学模型 2．求解
七． （10 分）某化工厂欲用新工艺代替原工艺生产。取得新工艺有两种途径，一种是自行 研究，但成功的可能性是 0.6，无论成功与否均须投入 30 万元；第二种是买专利，估计买 专利谈判成功的可能性是 0.7，谈判费用 5 万元，如果成功须再花费 40 万元购买专利。不 论研究成功或谈判成功，生产规模都可考虑两种方案，一是产量不变，二是增加产量。如 果增加产量，还须投入 10 万元。如果先自行研究失败，则再考虑买专利谈判。如果先谈 判失败，则再考虑自行研究。如果研究和谈判都失败，则只能采用原生产工艺并保持产量 不变。根据市场预测，估计今后该产品跌价的可能性是 0.2，涨价的可能性是 0.5，原价 的可能性是 0.3。通过计算，得到各个方案在不同价格情况下的收益值如表所示。试根据 期望收益最大准则，用决策树的方法进行决策。 收益 值 价格 状态 跌价（0.2） 涨价（0.5） 原价（0.3） -100 80 10 方案 按原工 艺生产 买专利成功（0.7） 产量不变 -300 240 100 产量增加 -500 300 200 自行研究成功（0.6） 产量不变 -200 200 80 产量增加 -400 280 160
j
aij
6.任意矩阵对策（ A.一定存在最优混合策略 C. 一定不存在最优纯策略
） B. 不一定存在最优混合策略 D.一定存在最优纯策略
第 1页 共 7页
二.填空(每空 1 分,共 l6 分) 1．线性规划的可行域非空，则一定是一个（ 应的系数列向量线性（ ） 。 ）集，其基本可行解中基变量对
2．不含人工变量,目标函数求最大值的线性规划问题,用单纯形法求解,当单纯形表中,常 数 项 b>0,( )时,有多个最优 解 ;( ) 时 , 为无界解 ; 检验数σ j ≤ 0,j=1，2….n;非基变量的检验数都<0,但表中 有 一 列 系 数 aik ≤ 0,i=1,2,...,m ; 则 该 线 性 规 划 问 题 一 定 （ ) . 3.用分枝定界法解整数规划问题 max Z CX ， AX b ， X 0 ，且为 整数时，不考虑整数限制，得到一个最优解为 xk
（
）
5 ． 不 确 定 性 决 策 问 题 ， 方 案 Ai 在 j 状 态 下 的 收 益 值 用 aij 表 示 ， 其 机 会 损 失 值
bij =（
A． max aij aij
j
） B． max aij aij
i
C． a m ax a ij ij
i
D． a m ax ij
第 6页
共 7页
八．案例分析 (12 分) 某企业生产五种产品,消耗三种资源,设第 j 种产品产量为 xj ，单位利润为 cj，建立 了使总利润最大的线性规划模型. 各约束条件均为小于等于的约束条件，加上松弛变量, 化成标准形式,用单纯形法求解,其初始表与最优表如下： Cj 28 B 10 22 21 10 0.5 0.5 X1 1 2 3 1 10 X2 1 1 1 1 30 X3 2 1 3 2 20 X4 0 3 2 0 0 1 21 X5 1 2 2 1 0 0 0 X6 1 0 0 1 1 -1 0 X7 0 1 0 0 1 0 X8 0 0 1 0 -1.5 0.5 0
)
3.无人工变量，目标函数求最大的非退化的线性规划问题的最终单纯形表中， k 0 ，
aik 0 ， i=1，2，…，m，则该线性规划问题一定有（
A. 无界解 C. 只有两个最优解 B. 无穷多个最优一定 A．存在基可行解 C．存在最优解 B．目标函数值无界 D．是有界闭凸集