运筹学习题6

一、一、多重选择判断（共5小题，每小题4分，共20分）

下面5小题，每题有（a） (b) (c) (d)四项，你认为正确的打√，不正确的打×。答对者记1分，答错者扣1分，不答者不记分。以小题为单位，每小题最高四分，最低0分，不记负分。

1.形法求解标准型的线性规划问题时

(a)当所有检验数cj-zj≤0时，即可判定表中解即为最优解；

(b)为使目标函数值最快增长，必须选取与最大正检验数（ck-zk）对应变量xk为换为基的变量；

(c)按最小比值原则确定换出基的变量是为了保证迭代计算后的解仍为基本可行解； (d)若存在σj=cj-zj>0，且该列系数PJ≤0，则线形问题最优解不存在（无界解） 2.线性规划的原问题与其对偶问题之间存在如下关系 (a) (a) 对偶问题的对偶问题是原问题；

(b) (b) 原问题存在可行解，其对偶问题必存在可行解； (c) (c) 原问题可行解，其对偶问题必无可行解；

(d) (d) 原问题有无穷多最优解，其对偶问题也有无穷多最优解。 3.已知线性规划问题

（A）max z=

cxjj1nj （B）max z=

cxjj1nj

(对偶变量）naxby1jj1j1naxbz2jj2j1(j1,,n)xj0  对偶变量n2ax2by'1jj1j1n1ax1b2jj222j1(j1,,n)xj0

′

′

则有（A）、（B） 的两对偶问题，各自最优解y* z*与y*, z* 间关系

1′′′′

(a) y*= y*, z*= z* (b) y*=2y*, z*=2z*

1′′

(c) y*=2y*, z*=2z* (d) (a) (b) (c)以外其他关系

4.满足下面条件的简单图G（V，E）是树图

（a）无圈且连通； （b）有n个点和恰好（n-1）条边； （c）图中任意两点间存在唯一的链； （d）G无圈，但只要加一条边即得唯一的圈。 5．在目标线性规划问题中

（a） （a） 正偏差变量取正值，负偏差变量取负值； （b） （b） 目标函数可以是求min。也可以求max；

（c） （c） 目标函数中的优先级P1，P2，P3…之间表明数量上的重要性差别，如

P1比P2级重要10倍或20倍等；

（d） （d） 模型可以含系统约束（刚性约束），也可以不含。 6．判断下列说法是否正确：

（a） （a） 线性规划问题的基本解对应可行域的顶点；

（b） （b） 若X1，X2是某线性规划问题的可行解，则X=λ1X1+λ2X2（其中λ1+

λ2=1）也必是该问题的可行解；

（c） （c） 线性规划问题若存在可行解，其可行解集合为凸集；

（d） （d） 若X1，X2是某线性规划问题的最优解，则X=λ1X1+（1+λ）X2(0≤

λ≤1)也是该问题的最优解。

三、形规划问题

max z= -x1+18x2+c3x3+c4x4

x12x23x34x4153x14x25x36x45x0(j1,,4)j(本题20分，每小题5分)

要求 （a）以x1,x2为基变量，列出单纯形表（当λ=0时）

（b）若x1,x2为最优基，确定问题最优解不变时c3,c4的变化范围； （c）保持最优基不变时的λ的变化范围；

23（d）增加一个新变量，其约束条件中系数向量为，目标函数中系数为ck，

求问题最优解不变时ck取值范围。

四、已知运输问题的产销平衡表、单位运价表及某一调运方案如下（20分） 产销平衡表及调运方案

要求：（a）以该调运方案对应的变量 x11、x12、x23、x31、x33为基变量，列出该运输问题用

单纯形法求解时的单纯形表（8分）。

（b）在单纯形表上判断方案是否最优？若否，用单纯形法继续迭代求出最优（8分）。 （c）利用单纯形表判断A3→B3运费c33在什么范围内变化，最优解不变（4分）。

五、由800万元，分别用于3个项目的投资，按规定每个项目至少投资200万元，最多投资400万元，各项目得到不同投资时的预期效益如下表所示，要求确定使投资效益最大的各项目投资数（20分）。

要求：（a）建立动态规划模型，列出递推关系式（基本方程），并说明方程中各符号的意义（10分）；

（b）建立网络模型，画出网络图，简要说明图中点、线和权术的意义（10分）。