运筹学复习教材课件学习资料

PAGE2一、填空题1、线性规划问题中，如果在约束条件中出现等式约束，我们通常用增加___的方法来产生初始可行基。2、线性规划模型有三种参数，其名称分别为价值系数、___和___。3、原问题的第1个约束方程是“=”型，则对偶问题相应的变量是___变量。4、求最小生成树问题，常用的方法有：避圈法和___。5、原问题的变量取值是0，则其对偶问题对应的约束条件是。6、目标规划单纯形法的最优性检验规则是。7、表上作业法包括有、、。8、目标规划克服了线性规划只能解个目标的问题。9、运输问题初始方案的确定的方法有、、10、在目标规划问题中，约束条件分为和。二、判断题：1、在互为对偶的一对原问题与对偶问题中，不管原问题是求极大还是极小，原问题可行解的目标函数值一定超过其对偶问题可行解的目标函数值。（）2、如线性规划问题存在可行域，则可行域一定包含坐标的原点。（）3、含n个变量m个约束的标准型线性规划问题，基解数恰好为个。（）4、若,分别是某一线性规划的最优解，则也是该线性规划问题的最优解，其中。（）5、如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解。（）6、任何线性规划问题具有唯一的对偶问题。（）7、单纯形法计算中选取最大正检验数对应的变量作为换入基的变量，将使迭代后的目标函数得到最快的增长。（）8、如果线性规划的对偶问题无可行解，则原问题也一定无可行解。（）9、原问题求最大值，第i个约束是“≥”，则该约束条件对应的对偶变量yi=010、对取值无约束的变量，通常令，其中，在用单纯形法求得的最优解中，有可能同时出现（）11、线性规划问题标准形式的数学模型的目标函数是求最小值。（）12、如线性规划问题存在可行域，则可行域是一个凸集。（）13、对偶单纯形法就是求解对偶问题的单纯形法。（）14、构成运输问题初始方案的基变量的个数是m个。（）15、如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解。（）16、运输问题中的非基变量的闭回路是存在而且是唯一的。（）17、在互为对偶的一对原问题与对偶问题中，如果一问题的变量取值非0，则其对偶问题的约束条件取严格的不等式。（）18、分配问题效率表中某一行元素分别加上（减去）一个常数，则最优解不变。（）19、原问题求最大值，某约束是“≥”约束，则该约束条件对应的对偶变量≤（）20、目标规划问题中的约束条件有刚性约束和柔性约束。（）21、完全图是既连通图，也是简单图。（）22、树图是部分图，也是子图。（）23、任何图中，点的次数之和等于边的2倍。（）24、图中任一个点i，若j是与i相邻点中距离最近的，则边[i,j]一定含在该图的最小部分树内。（）25、自由时差是指不影响它的各项紧后作业最早开工时间条件下，该项作业可以推迟的开工的最大时间限度。（）三、单项选择题：1、互为对偶的两个线性规划问题的解存在关系（）A.原问题具有无界解，则对偶问题无可行解B.对偶问题无可行解，原问题具有无界解C.若最优解存在，则最优解相同D.一个问题无可行解，则另一个问题也无可行解2、线性规划具有唯一最优解是指（）A.最优表中存在常数项为零B.最优表中非基变量检验数全部非零C.最优表中存在非基变量的检验数为零D.可行解集合有界3、原问题有6个变量4个约束，其对偶问题（）A.有4个变量6个约束B.有6个变量4个约束C.有6个变量6个约束D.有4个变量4个约束4、具有n个顶点的树的边数恰好为（）A.(n-1)条B.n条C.(n+1)条D.(n+2)条5、有4个产地5个销地的平衡运输问题模型具有特征（）A.有9个变量B.有20个约束C.有8约束D.有8个基变量6、X是线性规划的基本可行解则有（）A.X中的基变量非零，非基变量为零B.X不一定满足约束条件C.X中的基变量非负，非基变量为零D.X是最优解7、互为对偶的两个线性规划问题的变量存在关系（）A.在一个问题中是变量，则在另一问题中也是变量B.在一问题中是基变量，则在另一问题中也是基变量C.在一问题中是非基变量，则在另一问题中也是非基变量D.在一问题中是基解变量，则在另一问题中是非基解变量8、线性规划具有多个最优解是指（）A.可行解集合有界B.最优表中非基变量检验数全部非零C.最优表中存在常数项为零D.最优表中存在非基变量的检验数为零9、原问题有5个变量4个约束，其对偶问题（）A.有4个变量4个约束B.有5个变量5个约束C.有4个变量5个约束D.有5个变量4个约束10、μ是关于可行流f的一条增广链，则在μ上有（）A.对任意

B.对任意C.对任意

D.对任意11、关于树的性质，不正确的有（）A.树图是连通图B.具有n个顶点的树图的边数恰好为（n-1）条C.具有n个顶点的树图的边数恰好为n条D.任何树图中必存在次为1的点12、有4个产地4个销地的平衡运输问题模型具有特征（）A.有8个变量B.有16个约束C.有4个约束D.有7个基变量13、互为对偶的两个线性规划若存在最优解，则存在关系（）A.Z>W

B.Z=WC.Z≥WD.Z≤W14、线性规划的约束条件为则初始基可行解为（）A.(0,2,3,2)B.(3,0,-1,0)C.(0,0,5,6)

D.(2,0,1,2)15、（）A.无可行解B.有唯一最优解C.有多重最优解D.有无界解16、X是线性规划的基本可行解则有（）A.X中的基变量非零，非基变量为零B.X不一定满足约束条件C.X中的基变量非负，非基变量为零D.X是最优解17、使用人工变量法求解极大化线性规划问题时，当所有的检验数在基变量中仍含有非零的人工变量，表明该线性规划问题（）A.有唯一的最优解B.有无穷多最优解C.为无界解D.无可行解18、对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（）A.b列元素不小于零B.检验数都大于零C.检验数都不小于零D.检验数都不大于零19、已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为（）A.3B.2C.1D.以上三种情况均有可能20、如果要使目标规划实际实现值不超过目标值，则相应的偏离变量应满足（）A.d+›0B.d+=0C.d-=0D.d-›0,d+›021、在运输方案中出现退化现象，是指数字格的数目（）A.等于m+nB.等于m+n-1C.小于m+n-1D.大于m+n-122、关于线性规划的原问题和对偶问题，下列说法正确的是（）A.若原问题为元界解，则对偶问题也为无界解B.若原问题无可行解，其对偶问题具有无界解或无可行解C.若原问题存在可行解，其对偶问题必存在可行解D.若原问题存在可行解，其对偶问题无可行解23、下列说法正确的是（）A.线性规划问题的基本解对应可行域的顶点B.若是某线性规划问题的可行解，则（其中）也必是该问题的可行解C.单纯形法解标准的线性规划问题时，当所有检验时，即可判定表中解为最优解D.单纯形法解标准的线性规划问题时，按最小比值原则确定换出基变量是为了保证迭代计算后的解仍为基本可行解四、简答题：1、简述单纯形法的基本思路。2、简述对偶单纯形法的基本思路。3、简述运输问题求解的基本思路。4、写出下列线性规划问题的对偶问题。5、将下列线性规划问题化为标准形式五、计算题：1、有份说明书，要分别译成英、日、德、俄四种文字，交给甲、乙、丙、丁四个人去完成，应如何分配，使四个人分别完成这四项任务总的时间为最小？人甲乙丙丁工作译英21097译日154148译德13141611译俄4151392、请用破圈法或避圈法求下图的最小部分树。基变量X1X2X3X4X5X33/2001-1/8-1/4X25/20103/8-1/4X11100-1/41/2σj000-3/4-1/2已知线性规划MaxZ=3X1+4X2X1+X2≤52X1+4X2≤12其最优解为：3X1+2X2≤8X1,X2≥0写出该线性规划的对偶问题。若C2从4变成5，最优解是否会发生改变，为什么？若b2的量从12上升到15，最优解是否会发生变化，为什么？如果增加一种产品X6，其P6=(2,3,1)T，C6=4该产品是否应该投产？为什么？4、已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。销地产地B1B2B3产量A159215A231711A362820销量1812165、某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，试在总费用最小的条件下确定各个项目的承包者，总费用为多少？各承包商对工程的报价如表2所示：项目投标者ABCD甲15182124乙19232218丙26171619丁19212317求解下列线性规划问题。7、用匈牙利法求解下列分配问题。8、用标号法算法求下图中s至t的最大流量，并找出该网络的最小割。（每弧旁的数字是（cij,（fij））。9、请用破圈法或避圈法求下图的最小部分树。10、已知运输问题的产销地的供需量与单位运价表（如表所示），试用表上作业法求出其最优解。BjAiB1B2B3B4B5产量A1572415A2913567A3248136需量225451811、用图解法求解下列线性规划问题。12、将下列线性规划模型的一般形式转化为标准形式。13、用普通单纯形法求解下列线性规划问题。14、已知下列线性规划问题，已知其对偶问题的最优解为。试用对偶性质求解原问题。15、已知下列线性规划问题，求出其最优解，并求的变化范围，使得最优解不变。已知线性规划问题利用对偶理论证明其目标函数值无界。用图解法求解下列线性规划问题，并指出问题具有唯一最