中国大学运筹学_23答案(慕课2023完整答案)

点击查看答案

第一章 线性规划与单纯形法

第一章单元测试

1、中国整答线性规划模型不包括下列（ ）要素。大学
A、运筹目标函数；
B、学答约束条件；
C、案慕案决策变量；
D、课完状态变量

2、中国整答线性规划模型中增加一个约束条件，大学可行域的运筹范围一般将（ ）。
A、学答增大；
B、案慕案缩小；
C、课完不变；
D、中国整答不定；

3、大学关于线性规划模型的运筹可行域，下面（ ）的叙述正确。
A、可行域内必有无穷多个点；
B、可行域必有界；
C、可行域内必然包括原点；
D、可行域必是凸的

4、下列关于可行解，基本解，基可行解的说法错误的是（ ）
A、可行解中包含基可行解；
B、可行解与基本解之间无交集；
C、线性规划问题有可行解必有基可行解；
D、满足非负约束条件的基本解为基可行解

5、线性规划问题有可行解，则（ ）
A、必有基可行解；
B、必有唯一最优解；
C、无基可行解；
D、无唯一最优解

6、若目标函数为求max，一个基可行解比另一个基可行解更好的标志是（ ）
A、使Z更大；
B、使Z更小；
C、Z绝对值更大
D、Z绝对值更小

7、在单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中（ ）
A、不影响解的可行性；
B、至少有一个基变量的值为负；
C、找不到出基变量；
D、找不到进基变量

8、用单纯形法求解极大化线性规划问题中，若某非基变量检验数为零，而其他非基变量检验数全部<0，则说明本问题（ ）。
A、有惟一最优解；
B、有多重最优解；
C、无界；
D、无解

9、在约束方程中引入人工变量的目的是（ ）
A、表现变量的多样性；
B、不等式为等式；
C、目标函数为最优；
D、成一个单位阵

10、求目标函数为极大的线性规划问题时，若全部非基变量的检验数≤O，且基变量中有人工变量且不为0时该问题有（ ）
A、无界解；
B、无可行解；
C、唯一最优解；
D、无穷多最优解

11、当线性规划问题存在可行域时，对应的正确答案为（）
A、存在唯一最优解
B、存在最优解，不一定唯一
C、可能无可行解
D、可能出现无界解

12、线性规划可行域的顶点对应的解为（）
A、基解
B、最优解
C、基可行解
D、可行解

13、一个求目标函数最小化的线性规划问题，若增加一个新的约束条件，其目标函数的最优值将（）
A、可能增大
B、一定不变
C、可能减小
D、以上均有可能

14、一个极大化的线性规划问题，判别出现无界解的准则为（）
A、
B、
C、
D、

15、用图解法求解线性规划时，以下选项中正确的有（）
A、对于表示两个变量的坐标轴的单位长度必须一致
B、如存在可行域，坐标原点一定包含在可行域内
C、如存在最优解，最优解一定是可行域的某个顶点
D、以上说法均不正确或不确切

16、一个有m个约束，n个变量的线性规划问题基可行解的个数一定（）
A、
B、
C、
D、

17、线性规划具有无界解指（）
A、可行解集合无界
B、有相同的最小比值
C、
D、最优表中所有非基变量的检验数非零

18、线性规划具有多重最优解指（）
A、目标函数系数与某约束系数对应成比例
B、最优表中存在非基变量的检验数为0
C、可行解集合无界
D、存在基变量等于0

19、当线性规划的可行解集合非空时一定（）
A、包含原点
B、有界
C、无界
D、是凸集

20、线性规划的退化基本可行解是指（）
A、基本可行解中存在为0的基变量
B、非基变量为零
C、非基变量的检验数为零
D、最小比值为零

21、线性规划无可行解指（）
A、进基列系数非正
B、有两个相同的最小比值
C、第一阶段最优目标函数值等于零
D、用大M法求解时，最优解中还有非零的人工变量

22、若线性规划存在可行解，则（）
A、一定有最优解
B、可能无可行解
C、可能具有无界解
D、全部约束是小于等于的形式

23、线性规划可行域的顶点是（）
A、非可行解
B、非基本解
C、基本可行解
D、最优解

24、图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。

25、线性规划问题的每一个基解对应可行域的一个顶点。

26、一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。

27、若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解。

28、线性规划问题的可行解如为最优解，则该可行解一定是基本可行解。

29、若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解。

30、用单纯形法求解标准型式的线性规划问题时，与检验数大于0对应的变量都可以被选作入基变量

31、如线性规划问题存在可行域，则可行域一定包含坐标的原点。

32、线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。

33、对一个有n个变量，m个约束的标准型的线性规划问题，其可行域顶点恰好是个。

34、单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。

35、线性规划问题的任一可行解都可以用全部可行解的线性组合表示。

36、对于目标函数求极大值的线性规划问题，单纯形法的迭代计算过程是从一个基可行解转到目标函数值更大的另一个基可行解。

37、线性规划可行域的某一顶点若其目标函数值优于其它所有顶点的目标函数值，则该顶点处的目标函数值达到最优。

38、线性规划目标函数中系数最大的变量在最优解中总是取正的值。

39、一个线性规划问题求解时的迭代工作量主要取决于变量数的多少，与约束条件的数量关系较少。

40、

41、

42、

43、

44、

45、任何线性规划一定有最优解。

46、若线性规划有最优解，则一定有基本最优解。

47、线性规划可行域无界，则具有无界解。

48、在基本可行解中非基变量一定为0。

49、

50、可行解集非空时，则在极点上至少有一个点达到最优值。

51、基本解对应的是可行基。

52、任何线性规划总可用大M单纯形法求解。

53、任何线性规划总可用两阶段单纯形法求解。

54、若线性规划存在两个不同的最优解，则必有无穷多个最优解。

55、两阶段法中第一阶段问题最优解中基变量全部非人工变量，则原问题有最优解。

56、人工变量一旦出基就不会再进基。

57、普通单纯形法比值规则失效说明问题无界。

58、最小比值规则是保证从一个可行基得到另一个可行基。

59、

60、当最优解中存在为0的基变量时，则线性规划具有最多重最优解。

第一章单元作业

1、图解下列线性规划并指出解的形式（15分）

2、用单纯形法求解下列线性规划（20分）

3、用大M法求解下列线性规划（25分）

第二章 对偶理论和灵敏度分析

第二章 单元测试

1、线性规划与其对偶问题的解，以下叙述中正确的有
A、前者有可行解时后者必有可行解
B、前者无可行解时后者也无可行解
C、前者存在无界解后者也存在无界解
D、前者有最优解后者也有最优解

2、
A、
B、
C、
D、

3、由原问题直接写出对偶问题时，下列叙述中正确的是（ ）。
A、两个问题具有相同的变量数
B、
C、
D、ABC都不正确

4、
A、第i种资源已耗尽
B、第i种资源还有剩余
C、A和B均有可能
D、其他情况

5、灵敏度分析时，当线性规划目标函数的系数cj发生变化时，将其反映到最终单纯形表中有可能出现的关系有（ ）。
A、原问题为可行解，对偶问题为非可行解
B、原问题为非可行解，对偶问题为可行解
C、两者均为非可行解
D、ABC三种情况均有可能

6、灵敏度分析时，当线性规划最优解中某个基变量的系数aij发生变化时，将其反映到最终单纯形表中有可能的情况有（ ）。
A、原问题为可行解，对偶问题为非可行解
B、原问题为非可行解，对偶问题为可行解
C、原问题和对偶问题均为可行解或非可行解
D、ABC三种情况均有可能

7、灵敏度分析时，若在线性规划模型中增加一个约束条件，并将其直接反映到最终单纯形表中并经变换后有可能出现的情况有（ ）。
A、原问题与对偶问题均为可行解或非可行解
B、原问题为可行解，对偶问题为非可行解
C、原问题非可行解，对偶问题可行解
D、ABC三种情况均有可能

8、若某种资源的影子价格为k，则在其他资源数量不变条件下，该资源增加t个单位后，相应目标函数值将增加的情况为（ ）。
A、
B、
C、
D、ABC三种情况均有可能

9、
A、
B、
C、
D、

10、
A、
B、
C、
D、原问题不存在最优解

11、如果决策变量数相等的两个线性规划的最优解相同，则两个线性规划（ ）。
A、约束条件相同
B、目标函数相同
C、最优目标函数值相等
D、以上结论都不对

12、对偶单纯形法的最小比值规划是为了保证（ ）。
A、使原问题保持可行
B、使对偶问题保持可行
C、逐步消除原问题不可行性
D、逐步消除对偶问题不可行性

13、互为对偶的两个线性规划问题的解存在关系（ ）。
A、若最优解存在，则最优解相同
B、原问题无可行解，对偶问题也无可行解
C、对偶问题有可行解，原问题可能无可行解
D、一个问题无可行解，则另一个问题具有无界解

14、当非基变量xi的系数ci波动时，最优表中引起变化的有( )。
A、该非基变量的检验数
B、基变量的值
C、目标函数值
D、第i列系数

15、某个常数bi波动时，最优表中引起变化的有( )。
A、
B、
C、
D、

16、在保持最优解不变的前提下，基变量价值系数的变化范围可由解不等式( )求得。
A、
B、
C、
D、

17、
A、
B、
C、
D、

18、
A、
B、
C、
D、

19、原问题与对偶问题都有可行解，则（ ）。
A、原问题有最优解，对偶问题可能没有最优解
B、原问题与对偶问题可能都没有最优解
C、可能一个问题有最优解，另一个问题具有无界解
D、原问题与对偶问题都有最优解

20、任何线性规划问题存在并具有惟一的对偶问题。

21、对偶问题的对偶问题一定是原问题。

22、根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。

23、若原问题有可行解，则其对偶问题也一定有可行解

24、若原问题有最优解，其对偶问题也一定有最优解

25、若线性规划的对偶问题无可行解，则原问题也一定无可行解

26、在互为对偶的一对原问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值

27、原问题决策变量与约束条件数量之和等于其对偶问题的决策变量与约束条件数量之和

28、原问题变量的个数等于对偶问题约束条件的个数

29、原问题的约束条件的个数不等于对偶问题变量的个数

30、在对偶问题中，原问题的技术系数矩阵转置后为对偶问题系数矩阵

31、线性规划的原问题（或对偶问题）的变量无约束，则对应的对偶问题（原问题）的约束条件取严格等式

32、线性规划的原问题（或原问题）约束条件的右端项是相应的对偶问题（或原问题）的目标函数的变量的系数

33、某线性规划的原问题有n个变量，则原问题的对偶问题有n+1个约束条件

34、

35、

36、

37、

38、某中资源的影子价格越大，说明这种资源相对紧缺，影子价格越小，说明这种资源相对不紧缺。

39、

40、

41、

42、

43、

44、互为对偶问题，或者同时都有最优解，或者同时都无最优解。

45、对偶问题有可行解，原问题无可行解，则对偶问题具有无界解。

46、原问题无最优解，则对偶问题无可行解。

47、

48、

49、

50、

51、

52、原问题与对偶问题都可行，则都有最优解。

53、原问题具有无界解，则对偶问题有可行解。

54、

55、若某种资源影子价格为零，则该资源一定有剩余。

56、影子价格就是资源的价格。

57、原问题可行对偶问题不可行时，可用对偶单纯形法计算。

58、对偶单纯形法比值失效说明原问题具有无界解。

59、对偶单纯形法是直接解对偶问题的一种方法。

60、减少一个约束，目标值不会比原来变差。

61、增加一个约束，目标值不会比原来变好。

62、增加一个变量，目标值不会比原来变差。

63、减少一个非基变量， 目标值不变。

64、

65、

第二章 单元作业

1、

2、

3、

第三章 运输问题

第三章单元测试

1、1． 含个变量、个约束条件的产销平衡的运输问题的数学模型中，基变量的个数为（）
A、(m+n）个
B、
C、恰好为个
D、个

2、
A、
B、
C、
D、

3、运输问题是一类特殊的线性规划问题，因而求解结果为（）
A、可能出现唯一最优解、无穷多最优解、无界解或无可行解四者之一
B、只可能出现唯一最优解
C、可能出现唯一最优解或无穷多最优解
D、出无可行解外，其他三种结果均可能出现

4、下列说法正确的是（）
A、第i行的位势Ui是第i个对偶变量
B、运输问题的对偶问题不一定存在最优解
C、平衡运输问题的对偶问题的变量非负
D、平衡运输问题的对偶问题的约束条件为大于等于约束

5、
A、ac
B、bd
C、ad
D、bc

6、对产销平衡的运输问题，错误的阐述为（）
A、若产量和销量均为整数，一定存在整数最优解
B、个变量组构成基变量的充要条件是变量组内不构成任何闭回路
C、用位势法判断一个解是否为最优时，得出的位势值存在且唯一
D、用最小元素法给出的某一初始解是运输问题可行域凸集的一个顶点

7、下列变量组是一个闭回路的有（）
A、
B、
C、
D、

8、m个产地n个销地的平衡运输问题模型不具有特征（）
A、
B、
C、
D、

9、下列说法正确的有（）
A、运输问题的运价表第r行的每个Cij同时加上一个非零常数k，其最优调运方案不变
B、运输问题的运价表的第p列的每个Cij同时乘以一个非零常数k，其最优调运方案不变
C、运输问题的运价表的所有Cij同时乘以一个非零常数k，其最优调运方案变化
D、不平衡运输问题不一定存在最优解

10、下列结论错误的有（）
A、任意一个运输问题不一定存在最优解
B、任何运输问题都存在可行解
C、产量和销量均为整数的运输问题必存在整数最优解
D、运输单纯形法（表上作业法）的条件是产量等于销量的平衡问题

11、有6个产地7个销地的平衡运输问题模型的对偶模型不具有特征（）
A、有42个约束
B、有13个约束
C、是线性规划模型
D、有13个变量

12、运输问题的数学模型属于（）
A、线性规划模型
B、整数规划模型
C、0-1整数规划模型
D、不属于以上任何一种模型

13、
A、1,2,3,2,6 ； 4,1,-2,2
B、1,2,3,3,6；4,1,2,2
C、1,2,3,2,6 ； 4,3,2,2
D、1,1,3,3,6；4,1,3,2

14、运输问题中用位势法求得的检验数不唯一

15、

16、不平衡运输问题一定有最优解

17、

18、运输问题中的位势就是其对偶变量

19、含有孤立点的变量组不包含有闭回路

20、不包含任何闭回路的变量组必有孤立点。

21、

22、运输问题的检验数就是对偶问题的松弛变量的值。

23、

24、用一个常数k加到运价矩阵C的某列的所有元素上，则最优解不变。

25、令虚设的产地或销地对应的运价为一任意大于零的常数c(c>0),则最优解不变。

26、若运输问题中的产量和销量为整数则其最优解也一定为整数

27、运输问题的单位运价表的每一行都分别乘以一个非零常数，则最优解不变。

28、按最小元素法求得运输问题的初始方案，从任一非基格出发都存在唯一一个闭回路。

29、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解、无界解、无可行解；

30、

31、表上作业法实质上就是求解运输问题的单纯形法；

32、产销平衡的运输问题中含（m+n）个约束条件，但其中总有一个是多余的；

33、使用表上作业法求解运输问题时，确定初始方案一般采用最小元素法和Vogel法得到一个基本可行解，计算检验数一般采用闭回路法和位势法

34、m个产地n个销地且产销平衡的运输问题具有（mn）个变量，（m+n）个约束，（m+n+1）个基变量

35、运输问题n+m-1个变量构成基变量的充要条件是不包含任何闭回路

36、对效率矩阵画线覆盖零元素，当最少直线数等于m时存在m个不同行不同列的零元素

37、平衡运输问题的系数矩阵的秩等于（m+n-1）

38、运输问题有5个产地6个销地，其对偶问题有11个变量，32个约束

39、

第三章 单元作业

1、

2、

3、

第四章 目标规划

第四章单元测试

1、作为目标规划的目标函数，正确的表达式为（ ）。
A、
B、
C、
D、

2、目标规划的满意解不可能出现（ ）
A、
B、
C、
D、

3、用图解法求解目标规划问题，满意解在图中只能是（ ）
A、一个点
B、一个线段
C、一个区域
D、A、B、C之一

4、用单纯形法求解目标规划问题，得到满意解的判别准则为（ ）
A、
B、
C、
D、A、B、C均不对

5、以下叙述中正确的有（ ）
A、目标规划中，正偏差变量应取正值，负偏差变量应取负值
B、目标规划模型的约束中含绝对约束和目标约束两类
C、目标规划模型的目标函数既含决策变量，又含偏差变量
D、目标规划中优先级较之重要程度要大数倍至数十倍

6、以下叙述中不正确的有（ ）
A、目标规划适用于有多个目标的数学规划问题。
B、线性规划问题求取最优解，目标规划问题寻求满意解。
C、目标规划中，正偏差变量取正值，负偏差变量取负值。
D、目标规划模型用单纯形法求解时，有的时候也可能需要添加人工变量。

7、要求不超过第一目标值，恰好完成第二目标值，目标函数是（ ）
A、
B、
C、
D、

8、下列线性规划与目标规划之间不正确的关系是（ ）
A、线性规划的目标函数由决策变量构成，目标规划的目标函数由偏差变量构成
B、线性规划模型不包含目标约束，目标规划模型不包含系统约束
C、线性规划求最优解，目标规划求满意解
D、线性规划模型只有系统约束，目标规划模型可以有系统约束和目标约束

9、
A、第一和第二目标恰好达到目标值，第三目标不超过目标值
B、第一、第二和第三目标值同时不超过目标值
C、首先第一和第二目标同时不超过目标值，然后第三目标不超过目标值
D、首先第一和第二目标同时不低于目标值，然后第三目标不低于目标值

10、使第一目标恰好完成，第二目标尽可能超额完成的目标规划的目标函数是
A、
B、
C、
D、

11、正偏差变量应取正值，负偏差变量应取负值。

12、目标规划模型中，可以不包括系统约束（绝对约束）但必须包括目标约束。

13、

14、目标规划的目标函数中既包含决策变量，又包含偏差变量。

15、只含目标约束的目标规划模型一定存在满意解。

16、目标规划模型中的目标函数按问题性质要求分别表示为求min或求max。

17、

18、

19、系统约束中最多含有一个正或负的偏差变量。

20、目标约束一定是等式约束。

21、一对正负偏差变量至少一个大于零。

22、一对正负偏差变量至少一个等于零。

23、

24、

25、目标规划没有系统约束时，不一定存在满意解。

26、超出目标的差值称为正偏差。

27、未到达目标的差值被称为负偏差。

28、目标规划中优先级较之重要程度要大数倍至数十倍。

29、目标规划模型(若模型只有目标约束，没有绝对约束)用单纯形法求解时，不需要添加人工变量。

30、线性规划求最优解，目标规划求满意解。

31、用图解法求解目标规划问题，满意解在图中只能是一个点。

32、线性规划目标函数可求极大或极小，目标规划的目标函数通常是求极小值。

33、线性规划求解可能出现无穷多最优解，目标规划也一样。

34、线性规划中不含目标约束，目标规划中不含系统约束。

35、线性规划问题求解结果可能无可行解，而目标规划（只有目标约束时）则不会出现无可行解。

36、线性规划求最大值或最小值，目标规划只求最大值。

37、线性规划模型只有系统约束，目标规划模型只能有目标约束。

38、

39、

40、

第四章 单元作业

1、

2、

3、

第五章 整数规划

第五章 单元测试

1、
A、(4, 1)
B、(4, 3)
C、(3, 2)
D、(2, 4)

2、下列说法正确的是 ( )
A、整数规划问题最优值优于其相应的线性规划问题的最优值。
B、用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解。
C、用分支定界法求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪支。
D、分支定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分支迭代求出最优解。

3、
A、(0,0)
B、(0,1)
C、(1,0)
D、(1,1)

4、匈牙利法的条件是 ( )
A、问题求最小值
B、人数与工作数不相等
C、效率矩阵的元素非正
D、问题求最大值

5、下列说法错误的是 ( )
A、将指派（分配）问题的效率矩阵每行分别乘以一个非零数后最优解不变。
B、将指派问题的效率矩阵每行分别加上一个数后最优解不变。
C、将指派问题的效率矩阵每个元素同时减去一个非零数后最优解不变。
D、指派问题的数学模型是整数规划模型。

6、用匈牙利法求解分配问题时，以下叙述中正确的有 ( )
A、当人数多于任务数时，可添加虚报任务数,其在效率矩阵中对应的效率必须填写为0
B、当任务数多于人数时，可添加虚报人数，其在效率矩阵中对应的效率必须填写为0
C、只能出现唯一的最优解
D、ABC均不正确

7、设和是某整数规划问题的最优解，则有 ( )
A、和连线上所有点也是最优解
B、a也为最优解,0≤a≤1
C、+也为最优解
D、ABC均不正确

8、一个求目标函数极大值的线性规划问题中，限定一个或多个变量取整数值后,可能出现的结果有 ( )
A、问题的可行域不发生变化
B、问题的最优解将增大
C、模型只含两个变量时，仍可用图解法求解
D、模型只含两个变量时可用分枝定界法求解

9、用分支定界法求解整数规划问题时，以下叙述中正确的有 ( )
A、寻找替代问题时，要求替代问题随盖原问题解集，且易于求解
B、进行分支时，各分支解的和不必包含原问题解集
C、在各分支中任意保留一个含可行解分枝，删除其余的
D、分支定界法找出的解不一定是问题最优解

10、分配问题的效率矩阵中，下列变换将不改变问题的最优解的正确答案为( ) a. 矩阵中所有元素乘以常数k b. 第m行元素乘以k加到第n行上 c. 第t列元素乘以k加到第s列上 d. 矩阵中所有元素加上常数k e. 以上均不正确
A、a,d
B、b,c
C、a,b
D、e

11、下列说法中,其中错误的为 ( )
A、分配问题可用求解运输问题的表上作业法求解
B、分配问题可用隐枚举法求解
C、分配问题可用分支定界法求解
D、分配问题可用割平面法求解

12、
A、
B、
C、
D、

13、
A、a,d
B、b,c
C、a,b
D、e

14、求解指派问题的可选常用方法有 ( ) a.分支定界法 b. 匈牙利算法 c.运输单纯形法 d.割平面法
A、a,d
B、b,c
C、a,b
D、b,d

15、分支界定法中 ( ) a. 最大值问题的目标值是各分支的下界 b. 最大值问题的目标值是各分支的上界 c. 最小值问题的目标值是各分支的上界 d. 最小值问题的目标值是各分支的下界 e. 以上均不正确
A、a,d
B、b,d
C、a,c
D、e

16、整数规划的最优解是先求相应的线性规划的最优解然后取整得到。

17、部分变量要求是整数的规划问题称为纯整数规划。

18、求最大值问题的目标函数值是各分支函数值的上界。

19、求最小值问题的目标函数值是各分支函数值的下界。

20、变量取0或1的规划是0-1型整数规划。

21、整数规划的可行解集合是离散型集合。

22、0-1规划的变量有n个，则有个可行解。

23、

24、

25、高莫雷约束是将可行域中一部分非整数解切割掉。

26、一个规划问题中要求部分或全部决策变量是整数，则这个规划称为混合整数规划。

27、指派问题求最大值时，是将目标函数乘以“-1”化为求最小值，再用匈牙利法求解。

28、匈牙利法是求解最小值分配问题的一种方法。

29、指派问题的数学模型属于混合整数规划模型。

30、在指派问题的效率表的某行加上一个非零数最优解不变。

31、在指派问题的效率表的某行乘以一个大于零的数最优解不变。

32、整数规划的最优解是求松弛问题最优解后取整得到。

33、决策变量全部取0或1的规划称为0-1整数规划。

34、一个整数规划问题中，如果模型是线性的则称为整数线性规划。

35、线性规划数学模型无法描述的问题，其他数学模型也无法解决。

36、对于复杂的模型，完全枚举法不是有效的算法。

37、分支定界法求解整数规划要比单纯形法求解线性规划复杂得多。

38、割平面法的关键是怎样找到适当的割平面。

39、求解纯整数规划的两种方法是分支界定法和隐枚举法。

40、匈牙利法可直接求解极大化的指派问题。

41、整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函数值。

42、用分支定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题最优目标函数值的下界。

43、用分支定界法求解一个极大化的整数规划问题，当得到多于一个可行解时通常可任取其中一个作为下界值，再进行比较剪枝。

44、用割平面法求解整数规划时,构造的割平面有可能切去一些不属于最优解的整数解。

45、用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。

46、指派问题效率矩阵的每个元素都乘上同一常数k(k>0)，将不影响最优指派方案。

47、指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。

48、求解0-1规划的隐枚举法比穷举法的计算更简化。

49、分支定界法在需要分支时必须满足:一是分支后的各子问题必须容易求解。二是各子问题解的集合必须覆盖原问题的解。

50、一个整数规划问题如果存在两个以上的最优解，则该问题一定有无穷多最优解。

51、整数规划模型不考虑变量的整数约束得到的相应的线性规划模型，如该模型有无穷多最优解，则整数规划模型也一定有无穷多最优解。

52、匈牙利法求解指派问题的条件是效率矩阵非负。

第五章 单元作业

1、某商业公司计划开办五家新商店B1，B2，B3，B4，B5。为了尽早建成营业，商业公司通知了五个建筑公司A1，A2，A3，A4，A5，以便让每家新商店由一个建筑公司承建。建筑公司对新商店的建造费用的投标均见下表。商业公司应当对五家建筑公司怎样分配建造任务，才能使总建筑费用最少？

2、用分支定界法求解

3、用Gomory切割法求解整数规划

第六章 图与网络优化

第六章单元测试

1、已知图中各点的次分别如下,其中为树图的有（ ）。
A、4,1,1,2,2,2
B、6,1,1,1,2,2,1
C、4,2,2,1,1,2
D、5,1,1,1,2,1,1

2、连通图G有n个点，其支撑树是T,则有（ ）。
A、T有n个点n条边
B、T的长度等于G的每条边的长度之和
C、T有n个点n-1条边
D、T有n-1个点n条边

3、设P是图G从Vs到Vt的最短路，则有（ ）。
A、P的最短路长等于Vs到Vt的最大流量
B、P的长度等于G的每条边的长度之和
C、P的长度等于P的每条边的长度之和
D、P有n个点n-1条边

4、求最大流的计算方法有（ ）。
A、Dijkstra算法
B、Floyd算法
C、加边法
D、Ford-Fulkerson算法

5、下列错误的结论是（ ）。
A、容量不超过流量
B、流量非负
C、容量非负
D、发点流出的合流等于流入收点的合流

6、下列正确的结论是（ ）。
A、最大流等于最大流量
B、可行流是最大流当且仅当存在发点到收点的增广链
C、可行流是最大流当且仅当不存在发点到收点的增广链
D、调整量等于增广链上点标号的最大值

7、
A、
B、
C、
D、

8、以下有关图的叙述中正确的有（ ）。
A、任意图可用G=(V,E)表示，V是边的集合，E是点的集合
B、任意图中奇点有奇数个，偶点有偶数个
C、一个不含圈不含多重边的图称为简单图
D、目前图论被广泛应用于管理科学、计算机科学、物理、化学、心理学等学科领域的研究

9、以下树图的概念中正确的有（ ）。
A、任一图G中，当点集V确定后，树图是G中边数最多的连通图
B、树图中去掉任意一条边，图将不连通
C、重要的网络系统一般采用树状结构
D、任何含n个点(n-1)条边的图一定是树图

10、以下说法中正确的有（ ）。
A、网络的最大流就是其最大流量
B、用Ford-Fulkerson算法,在找出网络最大流同时也找到了该网络的最小割
C、求网络最大流时，如存在多条增广链，则各条增广链之间不可能包含相同的弧
D、一个含有多个发点和多个收点的求最大流问题应拆分为若干个只含一个发点和一个收点的问题进行求解

11、一个图能一笔画出,其始点和终点可以不同，其条件为（ ）。
A、图中所有点是奇点
B、奇点数不超过偶点数
C、图中含两个奇点，其余都为偶点
D、奇点数不超过4个

12、图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直都要严格注意。

13、在任一图G中,当点集V确定后,树图是G中边数最少的连通图。

14、

15、如图中从v至各点均有唯一的最短路,则连接v至其他各点后,恰好构成该图的最小支撑树。

16、任一图中奇点的个数可能为奇数个,也可能为偶数个。

17、任何含n个节点(n-1)条边的图一定是树图。

18、

19、

20、

21、最小支撑树可以直接用作图的方法求解，常用的有破圈法与避圈法。

22、树是一个无圈并且连通的无向图。

23、树的边数等于顶点数减2。

24、树的任意两个顶点之间有且只有一条初等链。

25、在树中不相邻的两个点间添上一条边，恰好得到一个圈。

26、在无向图中，所有点的次数之和是边数的两倍。

27、任一可行流的流量大于任一截集的容量。

28、从一个树中去掉任意一条边，则余下的图是不连通的。

29、在树中不相邻的两个点间添上一条边，恰好得到一个圈。

30、Dijkstra算法可适用所有情况，弧的权可以大于0，也可以小于0。

31、求最短路的递推算法可适用所有情况，弧的权可以大于0，也可以小于0。

32、

33、是否能找出发点到收点的增广链。若能，则可行流不是最大流；若不能，则可行流就是最大流。

34、在最短路问题中，起点到终点的最短路长是唯一的。

35、最大流问题是找一条从发点到收点的路，使得通过这条路的流量最大。

36、可行流是最大流的充要条件是不存在发点到收点的增广链。

37、可行流的流量等于每条弧上的流量之和。

38、避圈法(加边法)是：去掉图中所有边，从最短边开始添加，加边的过程中不能形成 圈，直到有n条边(n为图的点数)。

39、连通图一定有支撑树。

40、最大流量等于最大流。

41、连通图G的支撑树是取图G的点和G的所有边组成的树。

42、弧的流量是指单位时间内弧的最大通过能力。

第六章 单元作业

1、

2、求下图所示网络的最大流，并找出网络的最小截集。

3、

第七章 动态规划

第七章单元测试

1、下述有关动态规划的叙述中不正确的有
A、动态规划数学模型由阶段、状态、决策与策略,状态转移方程及指标函数等构成。
B、动态规划将一个多阶段的决策问题转化为一个具有递推关系的单阶段的决策问题。
C、动态规划求解的思路基于利·贝尔曼提出的最优化原理。
D、动态规划不能用于求解同时间顺序无关的静态问题。

2、以下叙述中错误的结论有
A、动态规划建模中阶段的划分是主要难点。
B、对于一个动态规划问题，应用顺序解法或逆序解法能得到相同的结果。
C、当变量和约束条件数相同时，用动态规划求解线性或非线性规划的计算量差别不大。
D、用动态规划方法可求解整数规划问题。

3、用动态规划方法求解货郎担问题时，主要难点在于
A、阶段的划分
B、状态的确定
C、决策与策略的确定
D、指标函数的确定

4、一个含5个变量、3个约束的线性规划问题，用动态规划建模时应
A、三个阶段，每个阶段状态用5维向量表示。
B、分5个阶段，每个阶段状态用3维向量表示。
C、(A)和(B)均可行。
D、(A)和(B)均不可行。

5、下列运筹学问题不能用动态规划方法求解的有
A、运输问题
B、分配问题
C、在有向图中求网络最短路
D、求网络最大流

6、有关动态规划的下列叙述中正确的有
A、问题分阶段顺序不同，则结果不同。
B、状态对决策有影响。
C、状态的选取不用满足无后效性
D、动态规划求解过程均可用列表方式实现。

7、下列有关动态规划的叙述中不正确的有
A、动态规划中状态的选取必须满足无后效性原则。
B、采用顺序解法与逆序解法可能得出不同的结果。
C、对结构基本雷同的线性与非线性规划问题，用动态规划方法求解时计算量不会有太大差别。
D、动态规划求解的基本思路是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段决策问题。

8、应用动态规划求解生产与存储问题中，以下叙述正确的有
A、状态变量是存储量，决策变量是生产量
B、状态变量是生产量，决策变量是存储量
C、阶段指标函数是从第k阶段到第n阶段的总成本
D、最优指函数是从第k阶段到第n阶段的总成本

9、下列错误的结论是
A、给定某一阶段的状态，则在这一阶段以后过程的发展不受这一阶段以前各个阶段状态的影响，而只与当前状态有关，与过程过去的历史无关。
B、动态规划是求解多阶段决策问题的一种算法策略，当然也是一种算法。
C、动态规划是一种将问题分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
D、动态规划数学模型由阶段、状态、决策与策略、状态转移方程及指标函数5个要素组成。

10、用动态规划方法求背包问题时
A、将装载的物品品种数作为阶段数。
B、将背包的容量作为决策。
C、将背包的容量作为阶段数。
D、将装载的物品品种数作为决策。

11、下列说法正确的是
A、状态是指每个阶段最终所处的自然状况。
B、指标函数是衡量状态优劣的数量指标。
C、最优指函数是从第k阶段到第n阶段的总成本。
D、策略是由每个阶段的决策组成的决策函数序列。

12、关于动态规划问题的下列命题中错误的是
A、动态规划分阶段顺序不同，则结果不同。
B、状态对决策有影响。
C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性。
D、离散型动态规划求解时可以用列表形式实现。

13、动态规划不适用于解决
A、排队问题
B、背包问题
C、资源分配问题
D、生产存储问题

14、采用动态规划策略求解问题的显著特征是满足最优性原理,其含义是
A、当前所作决策不会影响后面的决策。
B、原问题的最优解包含其子问题的最优解。
C、对前面的决策所形成的状态而言，余下的诸策略不一定是最优策略。
D、每次决策必须是当前看来的最优决策才可以找到最优解。

15、下列哪个不是动态规划的适用条件
A、最优化原理。
B、无后效性。
C、阶段可划分。
D、子问题之间互不独立。

16、动态规划的研究对象是
A、单阶段决策问题
B、多阶段决策问题
C、基本方程
D、最优决策序列

17、关于最优性原理，下面那个叙述是正确的
A、子策略一定是最优的?。
B、子策略不是最优的。
C、子策略是否最优和前面决策有关。
D、子策略是否最优与后面策略有关。

18、迭代方法是诸多求解最优化问题的核心思想，除下列哪项之外
A、线性规划
B、动态规划
C、非线性规划
D、排队优化?

19、关于动态规划方法，下面的说法错误的是
A、到目前为止，没有一个统一的标准模型可供应用。
B、应用存在局限性。
C、非线性规划方法比动态规划方法更易获得全局最优解?。
D、能利用经验，提高求解的效率。

20、在动态规划模型中，问题的阶数等于问题中的子问题的数目。

21、动态规划中,定义状态时应保证在各个阶段中所做决策的相互独立性。

22、动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策。

23、对一个动态规划问题,应用顺推或逆推解法可能会得出不同的最优解。

24、假如一个线性规划问题含有5个变量和3个约束,则用动态规划方法求解时将划分为3个阶段,每个阶段的状态将由一个5维的向量组成。

25、一个动态规划问题若能用网络表达时,节点代表各阶段的状态值,各条弧代表了可行的方案选择。

26、动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题。

27、在动态规划基本方程中,凡子问题具有叠加性质的,其边界条件取值均为零,子问题为乘积型的,边界条件取值均为1。

28、一个线性规划问题若转化为动态规划方法求解时,应严格按变量的下标顺序来划分阶段,如将决定的值作为第一阶段,决定的值作为第二阶段等。

29、建立动态规划模型时,阶段的划分是最关键和最重要的一步。

30、设是动态规划模型中第k阶段的状态,的取值仅取决于(k-1)阶段的状态和决策,而同(k-1)阶段之前的状态和决策无关。

31、动态规划是用于求解多阶段优化决策的模型和方法,这里多阶段既可以是时间顺序的自然分段,也可以是根据问题性质人为地将决策过程划分成先后顺序的阶段。

32、动态规划的基本方程保证了各阶段内决策的独立进行,可以不必考虑这之前和之后决策的如何进行。

33、动态规划是求解多阶段决策问题的一种思路,同时也是一种算法。

34、用动态规划求解一般线性规划问题是将约束条件数作为阶段数,变量作为状态。

35、定义状态时应保证各个阶段中所做的决策相互独立。

36、第1阶段开始到最后阶段全过程的决策构成的序列称为策略。

37、过程指标函数是阶段指标函数的函数。

38、最优指标函数是k阶段状态为时到下一阶段的最优指标值。

39、决策变量记为是所在状态的函数。

40、状态转移方程是确定过程由一个状态到另一个状态的演变过程。

41、用来衡量所实现过程优劣的一种数量指标，称为指标函数。

42、动态规划的关键在于正确的写出基本的递推关系式和恰当的边界条件。

43、在多阶段决策过程中，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。

44、一个最优策略的子策略总是最优的。

45、对于某些静态的问题，也可以人为的引入时间因素，把它看作是按阶段进行的一个动态规划问题。

第七章 单元作业

1、某公司计划在 3 个不同地区设置 4 个销售点，根据市场预测部门估计，在不同地区设置不同数量的销售点每月可得利润如下表所示。现考虑在A、B、C地区如何设置销售点，可是每月所获得的总利润最大？其值是多少？

2、

3、用逆推解法求解下列非线性规划

第八章 网络计划

第八章单元测试

1、如果A,B两项工作的最早开始时间分别为第6天和第7天，他们的而持续时间分别为4天和5天，则他们共同紧后工作C的最早开始时间为第（ ）天。
A、10
B、11
C、12
D、13

2、在某工程的网络计划中，如果工作X的总时差和自由时差分别为8天和4天，监理工程师检查实际进度时发现，该工作的持续时间延长了两天，则说明工作X的实际进度（ ）。
A、既影响总工期，也影响其后续工作
B、不影响总工期，但其后续工作的最早开始时间将延迟2天
C、影响总工期,总工期拖延2天
D、既不影响总工期，也不影响其后续工作

3、在网络计划中，若某项工作的拖延使得总工期要延长，那么为了保证工期符合原计划，（ ）。
A、应调整该工作的紧后工作
B、应调整该工作的平行工作
C、应调整该工作的紧前工作
D、应调整所有工作

4、在工程网络计划中，判别关键工作的条件是该工作（ ）。
A、最迟开始时间与最早结束时间差值最小
B、与其紧前工作之间的时间间隔为零
C、与其紧后工作之间的时间间隔为零
D、最迟开始时间与最早开始时间的差值最小

5、事件j的最早时间是指
A、以事件j为开工事件的工序最早可能开工时间
B、以事件j为完工事件的工序最早可能结束时间
C、以事件j为开工事件的工序最迟必须开工时间
D、以事件j为完工事件的工序最迟必须结束时间

6、事件j的最迟时间是指
A、以事件j为开工事件的工序最早可能开工时间
B、以事件j为完工事件的工序最早可能结束时间
C、以事件j为开工事件的工序最迟必须开工时间
D、以事件j为完工事件的工序最迟必须结束时间

7、工序（i，j）的最迟必须结束时间等于
A、
B、
C、
D、

8、工序（i，j）的总时差R（i，j）等于
A、
B、
C、
D、

9、绘制网络图时，需遵循规则有（ ）
A、只能有一个起点和多个终点
B、节点i，j之间不允许有两项以上工作
C、虚工作时间可为某个常数
D、某项工作可连接多项虚工作

10、网络图中关键路线的概念正确的为（ ）
A、从网络始点至终点用时最长的路线
B、任意网络图中只可能存在一条关键路线
C、任何虚工作不可能包含在关键路线中
D、因网络图中工作时间的变化，关键路线一定会发生变化

11、网络中工作（i，j）的有关时间计算的规则错误的有（ ）
A、（i，j）的最早开工时间是其所有紧前作业全部完成的最早时间
B、（i，j）的最迟完成时间应保证整体任务如期完成的最迟的完成时间
C、（i，j）最早可能完工时间是其最早开工时间加上完成（i，j）所需的时间
D、（i，j）的最迟开工时间是其最迟完工时间加上完成（i，j）所需时间

12、关于时差的概念其中叙述正确的有（ ）
A、工作（i，j）的总时差是在不影响任务总工期条件下可以延迟开工的最大幅度
B、工作（i，j）的单时差是指不影响紧前工作最早开工条件下该工作可以延迟其开工时间的最大幅度
C、某项工作的总时差为零时，其单时差不一定为零
D、某项工作的单时差为零时，其总时差一定为零

13、以下说法中其中正确的有（ ）
A、网络图的关键路线一定只有一条
B、总时差为零的工序构成的路线是网络图的关键路线
C、一项关键路线上工作在其最早开工与最迟完工时间内仍有一定机动性
D、若一项工作的自由时差为8h，说明在不影响工期的条件下，该工作的安排上有8h机动时间

14、用a，m，b三点估计一项工作完成时间时，以下叙述中正确的有（ ）
A、m是完成该项工作的期望时间
B、a为完成该项工作的最悲观时间
C、b是完成该项工作一定能实现的时间
D、

15、网络图中只能有一个始点和一个终点

16、网络图中因虚工作的时间为零，因此在各项时间参数的计算中可将其忽略

17、网络图中关键线路的延续时间相当于求图中从起点到终点的最短路

18、网络图中从一个事件出发如果存在多项作业，则其中用时最长的一项作业必包含在该网络的关键路线内

19、一项非关键路线上的作业在其最早开始与最迟结束的时间段内均可任意安排

20、若一项作业的总时差为10天，说明任何情况下该项作业从开始到结束之间总有10天的机动时间

21、一个网络只存在唯一的关键路线

22、为了在最短时间内完成项目，其关键路线上作业的开始或结束时间不允许有任何的延迟

23、网络关键路线上的所有作业，其总时差和自由时差均为零

24、任何非关键路线上的作业，其总时差和自由时差均不为零

25、总时差为零的各项作业必能连成从网络起点到终点的链

26、若一项作业的总时差为零，其自由时差也必为零

27、若一项作业的自由时差为零，则其总时差必为零

28、当作业时间用a，m，b三点估计时，m等于完成该项作业的期望时间

29、网络计划中的总工期等于各工序时间之和

30、在网络计划中，总时差为零的工序称为关键工序

31、在网络图中，允许工序有相同的开始和结束事件

32、在网络图中，从始点开始一定存在到终点的有向路

33、在网络图中，关键路线一定存在

34、PERT是针对随机工序时间的一种网络计划编制方法，注重计划的评价和审查

35、后续工序是紧后工序

36、虚工序是虚设的，不需要时间，费用和资源，并不表示任何关系的工序

37、若将网络中的工序时间看做距离，则关键路线就是网络起点到终点的最长路线

38、如果工序（i，j）是关键线路上的关键工序，则有

39、网络计划中有

40、工序时间是随机的，期望值等于3种时间的算术平均值

第八章 单元作业

1、

2、

3、

学习通运筹学_23

---

运筹学是一门涉及数学、统计学、经济学、计算机科学等多学科交叉的综合性科学，主要研究在资源有限的情况下，如何做出最优决策，以达到目标最大化。在现代社会中，运筹学在工业、商业、等各个领域都有广泛的应用。

在学习通的运筹学课程中，第23章主要介绍了网络流的概念、算法和应用。网络流是指在网络中从一个点到另一个点的最大/最小流量。网络流的应用非常广泛，例如传输问题、货物运输问题、电力分配问题等。

网络流模型

将一个问题转化成网络流模型，需要确定网络中的节点、边、容量和费用。节点代表问题中的各种要素，边代表它们之间的关系，容量代表限制条件，费用代表权值。

假设有一个n个人的任务分配问题，每个任务需要一定的时间，不同的人分配任务的效率也不同。这个问题可以转化成一个网络流模型，其中源点S表示任务的起点，汇点T表示任务的终点，每个人表示一个节点，每条边表示某个人可以完成某项任务的效率。容量为1，表示每个任务只能被一个人完成；费用为每个人完成该任务所需的时间，表示完成该任务所需要的代价。

最大流算法

最大流是指在网络中从源点到汇点的最大可行流量。最大流算法主要有：Ford-Fulkerson算法、Edmonds-Karp算法和Dinic算法。其中最常用的是Dinic算法，它是一种基于分层图的增广路算法。

Dinic算法的核心思想是通过层次图和残留网络来寻找增广路，即从源点到汇点的路径上，不断寻找可行流量的最小值，直到不再存在增广路。通过不断寻找增广路，最终得到从源点到汇点的最大流量。

最小费用最大流算法

在网络流问题中，最小费用最大流算法可以求出在满足最大流量的情况下，使费用最小的流量分配方案。最小费用最大流算法主要有：贪心算法、Bellman-Ford算法和Dijkstra算法。其中，Dijkstra算法是最常用的算法，它是一种基于最短路径的贪心算法。

Dijkstra算法的核心思想是通过维护一个距离数组和一个顶点数组，依次从源点向汇点扩展最短路径，每次选择距离源点最小的未访问节点，并更新距离和顶点数组。通过不断寻找最短路径，最终得到在满足最大流量的情况下，费用最小的流量分配方案。

总结

网络流是运筹学中的重要概念，应用广泛。学习通的运筹学课程中，第23章主要介绍了网络流的概念、算法和应用。其中，最大流算法和最小费用最大流算法是网络流问题中的两个重要算法，它们为我们解决实际问题提供了有力的工具。