运筹学试卷一
一.单项选择(在每小题的4个备选答案中,选出一个最合适的答案。将所选择的答案前的字母填在括号内。每小题2分,共14分) 1.线性规划可行域的顶点一定( )
A.是最优解 B.能表示为可行域其它两点的凸组合 C.是基可行解 D.不是基可行解
2.已知一线性规划问题的第3种资源影子价格为Y3( Y3>0),则( ) A. 第3种资源是一种短缺资源.
B. 第3种资源增加△b3,目标函数的净增量△Z= Y3*△b3. C. 如果该种资源的市场价格低于Y3*,则应大量买进.
D. 如果该种资源的市场价格高于Y3*,则应将该种资源全部卖出.
3.无人工变量,目标函数求最大的非退化的线性规划问题的最终单纯形表中,k0,
*
*
aik0, i=1,2,…,m,则该线性规划问题一定有( )
A. 无界解 B. 无穷多个最优解 C. 只有两个最优解 D. 两个最优基可行解 4.如果线性规划的可行域非空,则一定( ) A.存在基可行解 B.目标函数值无界 C.存在最优解 D.是有界闭凸集
5.不确定性决策问题,方案Ai在j状态下的收益值用aij表示,其机会损失值bij=( )
A.maxaijaij B.maxaijaij
j
i
C.amaxa D.amax
ijijij
i
j
aij
6.任意矩阵对策( )
A.一定存在最优混合策略 B. 不一定存在最优混合策略 C. 一定不存在最优纯策略 D.一定存在最优纯策略
二.填空(每空1分,共l6分)
1.线性规划的可行域非空,则一定是一个( )集,其基本可行解中基变量对应的系数列向量线性( )。
2.不含人工变量,目标函数求最大值的线性规划问题,用单纯形法求解,当单纯形表中,常数项b>0,( )时,有多个最优解;( )时,为无界解;检验数σj≤0,j=1,2….n;非基变量的检验数都
3.用分枝定界法解整数规划问题maxZCX,AXb,X0,且为 整数时,不考虑整数限制,得到一个最优解为xk
*
26
,生成两个新分枝其数学模型分别7
是( )和( )。停止分枝的条件有三个,它们是( )。
4.用动态规划方法解决实际问题,所选择的状态变量必须具有( )。这样建立的动态规划基本方程是一个( )方程。
5.目标规划中目标约束通过( )化成等式。要求恰好达到目标值的目标约束应将( )引入到总目标中,总目标是求最小值。
6.某线性规划问题,其中xk无符号限制,令xkxkxk ,化成标准形式,用单纯形法求得的每一个可行解,都一定有xkxk=( ),这是因为( ),( )。( ) 三.(10分) 用标号法求下面网络图的最大流及最小割集.弧旁数字是cij,fij。
/
//
/
//
v2 (4, 3) v5
vt
四.(13分)今有某娱乐场设计了一种娱乐项目。娱乐场的机器作为博弈的一方,不公开地给出一张红3或黑4的牌,参加游戏者作为一方,在手持的红2和黑3中选择一张。选择后,公开机器给出的牌。若两牌颜色相同,游戏者赢;若颜色不同,则游戏者输。若游戏者出红2,按两牌点数差的绝对值付钱,若游戏者出黑3,按两人牌上点数和付钱。试回答:(钱的单位为10元)
(1) 游戏者是否有最优纯策略?
(2) 如果没有,写出双方的混合策略所满足的两组不等式。
五.(15分) 设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量,各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示。试求出总的运费最节省的化肥调拨方案。(用最小元素法给出初始方案,并判断是否最优,如果不是最优,调整一步。)
六.(10分)某厂生产一种产品,未来12个月的需求量为dk(k=1,2,3….12)件,生产该产品的准备费用为ak元,存贮费用bk元,每件生产费用为ck元,该厂第k月份的生产能力为gk件(k=1,2,3….12)。各月产品满足需求后的剩余部分可放到仓库存贮起来,供以后需求。已知仓库最大库存量为H件。该产品1月初库存量为10件,12月末库存量为20件。求该厂未来12个月的生产方案,使得在满足需求的条件下,生产与存贮的总费用最少。(要求建立该问题动态规划数学模型,不求解。)
七.(12分)新兴化肥公司考虑是否把一种新产品推向全国市场,公司认为把产品推向市场之前先在区域内试销是一种谨慎做法。因此,首先要决策是否要开辟试销市场。公司估计,开辟试销市场的净费用为5万元。如果开辟试销市场,那么他必须等待试销市场结果,根据试销的状况可以决定是否将产品推向全国市场。另一方面,也可以做出不经试销,直接考虑是否将产品推向全国市场。公司估计新产品在全国市场中能畅销的概率为0.6,不畅销的概率为0.4。如果推向全国市场能够畅销可以实现120万元的收益,若不畅销则要承担50万元的损失。
公司根据以往经验估计,推向全国市场能够畅销的产品试销时会受欢迎的概率为0.9,不受欢迎的概率为0.1;推向全国市场不畅销的产品试销时受欢迎的概率只有0.2,不受欢迎的概率为0。8。
试用决策树的方法、期望收益最大准则为该公司制定决策,并求出样本(试销市场)信息的价值。
八.案例分析 (10分)
某企业生产五种产品,消耗三种资源,设第j种产品产量为xj ,单位利润为cj,建立了使总利润最大的线性规划模型. 各约束条件均为小于等于的约束条件,加上松弛变量,化成标准形式,用单纯形法求解,其初始表与最优表如下:
分析下列问题并给出答案:
1、 写出该问题的对偶问题数学模型及对偶最优解。
2、 为增加3个单位的利润,买入哪种资源的买入量最小,最小买入量是多少? 3、 由于价格的变化,产品的单位利润发生变化,如果已知第四,第五种产品的单位利润不
变,问第一、二、三种产品利润在什么范围内同时变化,现在得到的最优解不变? 最优值是否变化?
4、 如果各产品的产量需要取整数, 试用割平面法求出整数最优解。
运筹学试卷一
一.单项选择(在每小题的4个备选答案中,选出一个最合适的答案。将所选择的答案前的字母填在括号内。每小题2分,共14分) 1.线性规划可行域的顶点一定( )
A.是最优解 B.能表示为可行域其它两点的凸组合 C.是基可行解 D.不是基可行解
2.已知一线性规划问题的第3种资源影子价格为Y3( Y3>0),则( ) A. 第3种资源是一种短缺资源.
B. 第3种资源增加△b3,目标函数的净增量△Z= Y3*△b3. C. 如果该种资源的市场价格低于Y3*,则应大量买进.
D. 如果该种资源的市场价格高于Y3*,则应将该种资源全部卖出.
3.无人工变量,目标函数求最大的非退化的线性规划问题的最终单纯形表中,k0,
*
*
aik0, i=1,2,…,m,则该线性规划问题一定有( )
A. 无界解 B. 无穷多个最优解 C. 只有两个最优解 D. 两个最优基可行解 4.如果线性规划的可行域非空,则一定( ) A.存在基可行解 B.目标函数值无界 C.存在最优解 D.是有界闭凸集
5.不确定性决策问题,方案Ai在j状态下的收益值用aij表示,其机会损失值bij=( )
A.maxaijaij B.maxaijaij
j
i
C.amaxa D.amax
ijijij
i
j
aij
6.任意矩阵对策( )
A.一定存在最优混合策略 B. 不一定存在最优混合策略 C. 一定不存在最优纯策略 D.一定存在最优纯策略
二.填空(每空1分,共l6分)
1.线性规划的可行域非空,则一定是一个( )集,其基本可行解中基变量对应的系数列向量线性( )。
2.不含人工变量,目标函数求最大值的线性规划问题,用单纯形法求解,当单纯形表中,常数项b>0,( )时,有多个最优解;( )时,为无界解;检验数σj≤0,j=1,2….n;非基变量的检验数都
3.用分枝定界法解整数规划问题maxZCX,AXb,X0,且为 整数时,不考虑整数限制,得到一个最优解为xk
*
26
,生成两个新分枝其数学模型分别7
是( )和( )。停止分枝的条件有三个,它们是( )。
4.用动态规划方法解决实际问题,所选择的状态变量必须具有( )。这样建立的动态规划基本方程是一个( )方程。
5.目标规划中目标约束通过( )化成等式。要求恰好达到目标值的目标约束应将( )引入到总目标中,总目标是求最小值。
6.某线性规划问题,其中xk无符号限制,令xkxkxk ,化成标准形式,用单纯形法求得的每一个可行解,都一定有xkxk=( ),这是因为( ),( )。( ) 三.(10分) 用标号法求下面网络图的最大流及最小割集.弧旁数字是cij,fij。
/
//
/
//
v2 (4, 3) v5
vt
四.(13分)今有某娱乐场设计了一种娱乐项目。娱乐场的机器作为博弈的一方,不公开地给出一张红3或黑4的牌,参加游戏者作为一方,在手持的红2和黑3中选择一张。选择后,公开机器给出的牌。若两牌颜色相同,游戏者赢;若颜色不同,则游戏者输。若游戏者出红2,按两牌点数差的绝对值付钱,若游戏者出黑3,按两人牌上点数和付钱。试回答:(钱的单位为10元)
(1) 游戏者是否有最优纯策略?
(2) 如果没有,写出双方的混合策略所满足的两组不等式。
五.(15分) 设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量,各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示。试求出总的运费最节省的化肥调拨方案。(用最小元素法给出初始方案,并判断是否最优,如果不是最优,调整一步。)
六.(10分)某厂生产一种产品,未来12个月的需求量为dk(k=1,2,3….12)件,生产该产品的准备费用为ak元,存贮费用bk元,每件生产费用为ck元,该厂第k月份的生产能力为gk件(k=1,2,3….12)。各月产品满足需求后的剩余部分可放到仓库存贮起来,供以后需求。已知仓库最大库存量为H件。该产品1月初库存量为10件,12月末库存量为20件。求该厂未来12个月的生产方案,使得在满足需求的条件下,生产与存贮的总费用最少。(要求建立该问题动态规划数学模型,不求解。)
七.(12分)新兴化肥公司考虑是否把一种新产品推向全国市场,公司认为把产品推向市场之前先在区域内试销是一种谨慎做法。因此,首先要决策是否要开辟试销市场。公司估计,开辟试销市场的净费用为5万元。如果开辟试销市场,那么他必须等待试销市场结果,根据试销的状况可以决定是否将产品推向全国市场。另一方面,也可以做出不经试销,直接考虑是否将产品推向全国市场。公司估计新产品在全国市场中能畅销的概率为0.6,不畅销的概率为0.4。如果推向全国市场能够畅销可以实现120万元的收益,若不畅销则要承担50万元的损失。
公司根据以往经验估计,推向全国市场能够畅销的产品试销时会受欢迎的概率为0.9,不受欢迎的概率为0.1;推向全国市场不畅销的产品试销时受欢迎的概率只有0.2,不受欢迎的概率为0。8。
试用决策树的方法、期望收益最大准则为该公司制定决策,并求出样本(试销市场)信息的价值。
八.案例分析 (10分)
某企业生产五种产品,消耗三种资源,设第j种产品产量为xj ,单位利润为cj,建立了使总利润最大的线性规划模型. 各约束条件均为小于等于的约束条件,加上松弛变量,化成标准形式,用单纯形法求解,其初始表与最优表如下:
分析下列问题并给出答案:
1、 写出该问题的对偶问题数学模型及对偶最优解。
2、 为增加3个单位的利润,买入哪种资源的买入量最小,最小买入量是多少? 3、 由于价格的变化,产品的单位利润发生变化,如果已知第四,第五种产品的单位利润不
变,问第一、二、三种产品利润在什么范围内同时变化,现在得到的最优解不变? 最优值是否变化?
4、 如果各产品的产量需要取整数, 试用割平面法求出整数最优解。