运筹学期末复习题

学院 班级 姓名 学号

题号 得分 一 二 三 四 五 六 七 八 九 总分 一、填空题

以下是关于目标函数求最大值的单纯行表的一些结论，请根据所表述的意思判断解的情况：

1.所有的检验数非正，这时的解是 。

2.有一个正检验数所对应的列系数均非正，这时线性规划的解 。 3.非基变量检验数中有一个为零时，线性规划的解 。

4.在两阶段法中，如果第一阶段的最优表中的基变量中有人工变量，则该线性规划 。

6.基变量取值为负时的解为 。

7.最优表中的非基变量检验数的相反数就是 。

8.已知一个线性规划两个最优解是：（3，2），和（5，9），请写出其他解： 9.线性规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种。 10.在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明 如果在该空格中增加一个运量运费将增加4 。

11.“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错 12.如果某一整数规划：

MaxZ=X1+X2

X1+9/14X2≤51/14 -2X1+X2≤1/3 X1,X2≥0且均为整数

所对应的线性规划（松弛问题）的最优解为X1=3/2，X2=10/3，MaxZ=6/29，我们现在要对X1进行分枝，应该分为 X1≤1 和 X1≥2 。

13.在用逆向解法求动态规划时，fk(sk)的含义是： 从第k个阶段到第n个阶段的最优解 。

14. 假设某线性规划的可行解的集合为D，而其所对应的整数规划的可行解集合为B，那么D和B的关系为 D 包含 B

15. 已知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“≤”型不等式）其中X3,X4,X5为松驰变量。 XB b X1 X2 X3 X4 X5 X4 3 0 0 -2 1 3 X1 4/3 1 0 -1/3 0 2/3 X2 1 0 1 0 0 -1 Cj-Zj 0 0 -5 0 -23 321-1

问：（1）写出B=1/3.02/3

001(2)对偶问题的最优解： Y＝（5，0，23，0，0）T

16. 线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有___某一个非基变量的检验数为0______；

17. 极大化的线性规划问题为无界解时，则对偶问题_ 无解_____； 18. 若整数规划的松驰问题的最优解不符合整数要求，假设Xi=bi不符合整数要求，INT（bi）是不超过bi的最大整数，则构造两个约束条件：Xi≥INT（bi）＋1 和 Xi≤INT（bi） ，分别将其并入上述松驰问题中，形成两个分支，即两个后继问题。

19. 知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“≤”型不等式）其中X4,X5,X6为松驰变量。 XB b X1 X2 X3 X4 X5 X6 X1 2 1 1 0 2 0 1 X3 2/3 0 0 1 1 0 4 X5 1 0 -2 0 1 1 6 Cj-Zj 0 0 0 -4 0 -9 T问：(1)对偶问题的最优解： Y＝(4,0,9,0,0,0) （2）写出B-1=

20. 线性规划问题MaxZ=CX；AX=b，X≥0（A为kxl的矩阵，且l>k）的基的最多个数为___，基的可行解的最多个数为_____.

21.指派问题的最优解的性质________________________________

___________________________________________________________________________.

22.线性规划问题的所有可行解构成的集合是__________,它们有有限个______________________,线性规划问题的每个基可行解对应可行域的___________,若线性规划问题有最优解，必在______________得到。

23.影子价格的经济含义______.在完全市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应_____该资源，而当某种资源的市场价格高于影子价格时，则企业应___该资源，可见影子价格对市场有____作用。

24. 运输问题的产销平衡表中有m个产地n个销地，其决策变量的个数有____个，其

数值格有____个

二、不定项选择题(每小题2分，共6分) 1．线性规划的标准型有特点（ ）。

A、右端项非零； B、目标求最大； C、有等式或不等式约束； D、变量均非负。

2．一个线性规划问题（P）与它的对偶问题（D）有关系（ ）。

A、（P）无可行解则（D）一定无可行解； B、（P）、（D）均有可行解则都有最优解；

C、（P）的约束均为等式，则（D）的所有变量均无非负限制； D、若（D）是（P）的对偶问题，则（P）是（D）的对偶问题。 3．关于动态规划问题的下列命题中（ ）是错误的。

A、动态规划阶段的顺序与求解过程无关；B、状态是由决策确定的； C、用逆序法求解动态规划问题的重要基础之一是最优性原理；

D、列表法是求解某些离散变量动态规划问题的有效方法。 4.最早运用运筹学理论的是（ ）

A 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署 B 美国最早将运筹学运用到农业和人口规划问题上

C 二次世界大战期间，英国政府将运筹学运用到政府制定计划 D 50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上5.下列哪些不是运筹学的研究范围（ ）

A 质量控制 B 动态规划 C 排队论 D 系统设计 6.对于线性规划问题，下列说法正确的是（ ）

A线性规划问题可能没有可行解

B 在图解法上，线性规划问题的可行解区域都是“凸”区域 C 线性规划问题如有最优解，则最优解可在可行解区域顶点上到达 D 上述说法都正确

7.下面哪些不是线性规划问题的标准形式所具备的（ ）

A 所有的变量必须是非负的 B 所有的约束条件（变量的非负约束除外）必须是等式

C 添加新变量时，可以不考虑变量的正负性 D 求目标函数的最小值

8.在求解运输问题的过程中运用到下列哪些方法（ ）

A 西北角法 B 位势法 C 闭回路法 D 以上都是 三、判断题

1．若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k个单位。 （ ） 2．如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。 （ ） 3．运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解。 （ ） 4．用割平面法求解纯整数规划问题时，要求包括松弛变量在内的全部变量必须取整数值。 （ ） 5．如图中某点vi有若干个相邻点，与其距离最远的相邻点为vj，则边[i,j]必不包含在最小支撑树内。 （ ） 6.用两阶段法求解线性规划时，如果第一阶段的最终表中基变量出现人工变量，则该问题一定无解。【√ 】

7.运输问题一定存在有限的最优解；

【√ 】

8. 如果某种资源的影子价格等于零，说明该种资源一定已经用完 。 【× 】 9. 单纯形法只适合求解线性规划，对偶单纯形法只适合求解对偶规划 【× 】 10.分枝定界法求解最大化问题中，如果某个分支的目标值少于已经得到整数解的目标值，则这一分支将被减去而不再往下求解 。 【√ 】 11. 运输问题表上作业法的最优判别标准是所有的检验数应该小于等于0。【× 】 12.分枝定界法和割平面法一样适用于线性规划的求解 。 【× 】 13.如果原规划无可行解，则其对偶规划也必将无可行解 【× 】 14.如果原问题最优解的某个分量非零，则其对偶规划对应的约束条件一定是等式

【√ 】

15.如果某种资源的影子价格为4，而该资源的市场价格为3。则应买进该资源投入生产 【√ 】

16.最优表中如果某个非基变量检验数为零，说明该问题有多重解 【√ 】 17.对偶单纯形法应用的前提是对偶问题可行，原规划不可行 【√ 】 18.线性规划问题的解只有唯一最优解、无解和无界解几种情况 【× 】

19.连通且有n-1条边的图一定是树 【√ 】

20.线性规划原问题和对偶问题都有可行解，则该线性规划问题一定有唯一最优解

【√ 】

21.运输问题表上作业法的最优判别标准是所有的检验数应该大于等于0。【√ 】 22.用两阶段法求解线性规划时，如果该线性规划问题存在最优解，则第一阶段最终表中的基变量中一定不会出现人工变量。 【√ 】

23.求解整数规划的分枝定界法中的“定界”的目的是加快解的搜索速度。【 】 24. 用闭回路法计算的检验数如果等于3，表明沿该闭回路调整一个单位运量可以节约3个单位成本。 【 】

四、表中给出的是某极大化问题的单纯型表，试根据下面的问题，确定表中

的值或取值范围。

（1） 计算a2的值。 （2） 计算目标函数值。

（3） 已知初始，求d的值。

（4） 该线性规划问题具有无界解，则a1, C1的取值范围是多少？ （5） 表中解为无穷多最优解之一，则表中C1等于多少？ （6） 写出对偶规划的解和第二种资源的影子价格。

表1

CB 2 3 0 σXB X1 X3 X4 j 2 x1 4 1 d 1 0 0 0 1 x2 -5 -7 a1 C1 3 x3 0 1 0 0 0 x4 0 0 1 0 0 x5 2 1 0 -4 0 X6 a2 0 4 -2 五、考虑下列线性规划： 其最优单纯形表为：

0 5 -Z 6 4 -20 2 1 -2 0 1 0 -1 1 -4 1 0 0 -2 1 -5 1、写出此线性规划的最优解、最优值； 2、求线性规划的对偶问题的最优解；

3、试求c2在什么范围内，此线性规划的最优解不变； 4、若b114变为9，最优解及最优值是什么？

例：设线性规划

求：1.最优解;

2.确定c1,c2,c3的范围,使最优解不变; 取c350,求最优解; 6 3.确定b1,b2,b3的范围,使最优基不变, 取b1100,求最优解; 4.引入x7,P71,4,3,c78求最优解; 解 1.由单纯形方法得

T2200100200,,0,z. 即,原问题的最优解为X333T8202.因x3为非基变量,故当c33时,即c3时, 最优解不变;

33 x1,x2为基变量,由公式,当4c15,2c24,最优解不变, 即

6c115,4c210时,最优解不变.

50208135现对c3,最优解改变,此时3,原最优表为

63333xcx2x1x6x11001000100x2610001000x2x1x3x325356164530010x405323210325127121252Tx5016160231616023x6000105241241451220031003100220032756175625

232532325175275,,25,z. 即相应的最优解为X6363.此时

得40b150,200b2400,100b3,最优基不变.即

60b1150,400b21000,b3200,最优基不变.

当b110050,最优解改变,此时 此时最优表为

即最优解为X0,150,0,z900. 4.此时

T11027cBB1P7c7,,0486820,故最优解改变.

333532P7B1P7321061110,相应的最优表为

0461301六、下述线性规划问题 ：

以y1,y2为对偶变量写出其对偶问题。

七、某公司下属的2个分厂A1、A2生产质量相同的工艺品，要运输到B1、B2、B3，3个销售点，分厂产量、销售点销量、单位物品的运费数据如下表：

A1 A2 销量 B1 23 18 20 B2 11 16 10 B3 20 17 20 产量 25 25 用伏格尔法给出近似最优解。

七、有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D不同的工作，每人做各项工作所消耗的时间如下表所示：

甲 乙 丙 丁 A 7 13 15 11 B 9 12 16 12 C 10 15 14 15 D 12 17 15 16 问：应该如何指派，才能使总的消耗时间为最少？ 八、某公司生产三种产品，各产品的重量和利润关系如下：

产品 重量（t） 利润（元） Ⅰ 4 8 Ⅱ 5 11 Ⅲ 6 13 现将三种产品运往市场出售，运输能力为总重量不超过10t，如何安排运输使总利润最

大。试建立此问题的动态规划模型（只建模，不求解）。

九、某旅游者要从A地出发到终点F，他事先得到的路线图如下：

9 B1 C1 1 D1 4 E1 6 5 5 各点之间的距离如上图所示数值，旅游者沿着箭头方向行走总能走到2 3 F地，试找出A4 →F间的最短路线及距离。 8 1 5 3 4 ，可用逆向追踪“图上标号法”解决A 解：此为动态规划之“最短路问题”B2 D2 C2 F 9 6 2 如下： 5 4 1 B14 1 3 B3 9 5 B2 5 7 4 9 4 C3 1 C1 5 4 2 8 5 D3 E2 7 D4 1 5 4 2 6 D2 7 E2 7 9 2 1 E1 1 14 A 0 F 3 5 C2 14 4 6 4 1 B3 12 7 4 C3 8 2 D3 7 5 2 最佳策略为：A→B2→C1→D1→E2→F 此时的最短距离为5+4+1+2+2=14