运筹学学习与考试指导.doc

运筹学学习与考试指导模拟考试试题（一）一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。每小题2分，共10分）1线性规划具有唯一最优解是指（ ）。A.不加入人工变量就可进行单纯形法计算B.最优表中非基变量检验数全部非零C.最优表中存在非基变量的检验数为零D.可行解集合有界2.设线性规划的约束条件为则基本可行解为( )。A.(0,0,4,3)B.(3,4,0,0)C.(2,0,1,0)D.(3,0,4,0)3minZ=3x1+4x2, x1+x24, 2x1+x22, x1、x20，则（ ）。A.无可行解B.有唯一最优解C.有多重最优解D.有无界解4互为对偶的两个线性规划问题的解存在关系（ ）。A.原问题无可行解，对偶问题也无可行解B.对偶问题有可行解，原问题也有可行解C.若最优解存在，则最优解相同D.一个问题有无界解，则另一个问题无可行解5有6个产地4个销地的平衡运输问题模型具有特征（ ）。A.有10个变量24个约束B.有24个变量10个约束C.有24个变量9约束D.有9个基变量10个非基变量二、判断题（你认为下列命题是否正确，对正确的打“”；错误的打“”。每小题2分，共20分）1若线性规划无最优解则其可行域无界。（ ）2凡基本解一定是可行解。（ ）3线性规划的最优解一定是基本最优解。（ ）4可行解集非空时,则在极点上至少有一点达到最优值。（ ）5原问题具有无界解，则对偶问题不可行。（ ）6互为对偶问题，或者同时都有最优解，或者同时都无最优解。（ ）7加边法就是避圈法。（ ）8一对正负偏差变量至少一个大于零。（ ）9要求不超过目标值的目标函数是minZ=d+。（ ）10求最小值问题的目标函数值是各分枝函数值的下界。（ ）三、写出下列线性规划的对偶线性规划（10分）maxZ=x1+5x2-7x3四、用图解法解下列目标规划（15分）minZ=p1(d+3+d+4)+P2d-1+P3d-2五、用单纯形法解下列线性规划（15分）maxZ=3x1+4x2+x3六、求下列运输问题（min）的最优解（10分）10050150C= 150 80 70七、求下列指派问题（min）的最优解（10分）C=八、简答下列问题（每小题5分，共10分）1什么是影子价格，怎样利用影子价格作经济活动分析？2线性规划与目标规划有什么区别？模拟考试试题（二）一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。每小题2分，共10分）1.线性规划无可行解是指（ ）。A.用大M法求解时,最优解中还有非零的人工变量B.进基列系数非正C.有两个相同的最小比值D.可行域无界2.设线性规划的约束条件为则可行解为（ ）。A.(0,0,4,3)B.(1,1,1,0)C.(3,4,0,0)D.(3,0,4,0)3maxZ=4x1-x2, 4x1+3x224, x25, x1、x20，则（ ）。A.无可行解B.有唯一最优解C.有多重最优解D.有无界解4对偶单纯形法的最小比值规划则是为了保证（ ）。A.使原问题保持可行B.逐步消除对偶问题不可行性C.使原问题有最优解D.使对偶问题保持可行5.要求不超过第一目标值、恰好完成第二目标值，目标函数是（ ）。A.minZ=p1d-1+p2(d-2+d+2)B.minZ=p1d+1+p2(d-2-d+2)C.minZ=p1d+1+p2(d-2+d+2)D.minZ=p1d-1+p2(d-2-d+2)二、判断题（你认为下列命题是否正确，对正确的打“”；错误的打“”。每小题2分，共20分）1对偶问题无可行解，原问题具有无界解。（ ）2对偶问题具有无界解，则原问题无最优解。（ ）3匈牙利法求解指派问题的条件是效率矩阵的元素非负。（ ）4变量取0或1的规划是整数规划。（ ）5是一条增广链，则后向弧上满足流量f 0。（ ）6一对正负偏差变量至少一个等于零。（ ）7要求至少到达目标值的目标函数是maxZ=d+。（ ）8产地数为3，销地数为4的平衡运输中，变量组x11, x13, x22, x33, x34可作为一组基变量。（ ）9.最大流量等于最大流。（ ）10.若线性规划存在两个不同的最优解,则必有无穷个最优解。（ ）三、写出下列线性规划的对偶线性规划（10分）minZ=2x1-x2+3x3四、图解下列目标规划(15分)minZ=p1d+1+p2(d-2+d+2)五、用对偶单纯形法求解(15分)minZ=2x1+x2+4x3六、求下列运输问题（min）的最优解(10分)502530C=40 20 14 30七、求下列指派问题（min）的最优解(10分)C=八、简答下列问题（每小题5分，共10分）1简述线性规划数学模型的三个要素及其特征。2满足哪三个条件的流是可行流？模拟考试试题（三）一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。每小题1分，共10分）1有3个产地4个销地的平衡运输问题模型具有特征（ ）。A.有7个变量B.有12个约束C.有6约束D.有6个基变量2.线性规划可行域的顶点一定是（ ）。A.基本可行解B.非基本解C.非可行解D.最优解3. X是线性规划的基本可行解，则有（ ）。A. X中的基变量非零，非基变量为零B. X不一定满足约束条件C. X中的基变量非负，非基变量为零D. X是最优解4.线性规划最优解不唯一是指（ ）。A.可行解集合无界B.存在某个检验数k>0且aik0(i=1,2,m)C.可行解集合是空集D.最优表中存在非基变量的检验数为零5.minZ=4x1+6x2，4x1+3x224，x29，x1，x20，则（ ）。A.无可行解B.有唯一最优解C.有无界解D.有多重解6.原问题有5个变量3个约束，其对偶问题（ ）。A.有3个变量3个约束B.有5个变量3个约束C.有3个变量5个约束D.有5个变量5个约束7.下列错误的结论是（ ）。A.原问题没有最优解，对偶问题也没有最优解B.对偶问题有可行解，原问题也有可行解C.原问题有最优解，对偶问题也有最优解D.原问题无界解，对偶问题无可行解8.maxZ=3x1+2x2,2x1+3x214,x1+0.5x24.5,x1,x20且为整数，对应线性规划的最优解是（3.25，2.5），它的整数规划的最优解是（ ）。A(4，1)B(4，3)C(3，2)D(2，4)9要求不低于目标值，其目标函数是（ ）。AmaxZ=d-BmaxZ=d+CminZ=d-DminZ=d+10单纯形法的最小比值规划则是为了（ ）。A.使对偶问题保持可行B.使原问题保持可行C.尽快达到最优解D.寻找进基变量二、判断题（你认为下列命题是否正确，对正确的打“”；错误的打“”。每小题1分，共10分）1若原问题具有m个约束，则它的对偶问题具有m个变量。（ ）2正偏差变量大于等于零，负偏差变量小于等于零。（ ）3要求不超过目标值的目标函数是minZ=d-。（ ）4部分变量要求是整数的规划问题称为混合整数规划。（ ）5匈牙利法是求解最小值的分配问题。（ ）6线性规划的最优解是可行解。（ ）7可行解是基本解。（ ）8运输问题一定存在最优解。（ ）9人工变量出基后还可能再进基。（ ）10求最大流问题就是在网络中找一条从起点到终点的路，使得这条路上通过的流量最大。（ ）三、写出下列线性规划的对偶线性规划（10分）maxZ=5x1+4x2-6x3四、用对偶单纯形法求解下列线性规划（15分）minZ=3x1+4x2+5x3五、求解下列目标规划（15分）minZ=p1(d-1+d+2)+p2d-3六、求解下列指派问题（min）（10分）C=七、求解下列运输问题（min）（15分）5060100C=70 80 60八、已知世界八大城市之间的距离（千公里）如下表，试建立一个因特网使总距离最短。（15分）两城市之间的距离（千公里）123456781121081213141329713111512313128101641179958576367148模拟考试试题（四）一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。每小题1分，共10分）1线性规划具有无界解是指（ ）。A.可行解集合无界B.有相同的最小比值C.存在某个检验数k0且aik0（i=1,2，,m）D.最优表中所有非基变量的检验数非零2若线性规划存在可行解，则（ ）。A.一定有最优解B.可行域非空C.有多重解D.具有无界解3有4个产地5个销地的平衡运输问题模型具有特征（ ）。A.有9个变量9个约束B.有9个变量20个约束C.有20个变量9个约束D.有9个基变量4互为对偶的两个线性规划问题的解存在关系（ ）。A.若最优解存在，则最优解相同B.原问题无可行解，对偶问题也无可行解C.一个问题无界，则另一个问题也无解D.若最优解存在，则最优值相同5在分枝定界法中（ ）。A.最大值问题的目标值是各分枝的下界B.最大值问题的目标值是各分枝的上界C.最小值问题的目标值是各分枝的上界D.以上结论都不对6下例错误的说法是（ ）。A.标准型的目标函数是求最大值B.标准型的目标函数是求最小值C.标准型的常数项非正D.标准型的变量一定要非负7设P是图G从vs到vt的最短路，则有（ ）。A.P的最短路长等于vs到vt的最大流量B.P的长度等于G的每条边的长度之和C.P的长度等于P的每条边的长度之和D.P有n个点和n-1条边8minZ=3x1+4x2，x1+x24，2x1+x22，x1、x20，则（ ）。A无可行解B有唯一最优解C有多重最优解D有无界解9下列结论错误的有（ ）。A任意一个运输问题不一定存在最优解B任何运输问题都存在可行解C产量和销量均为整数的运输问题必存在整数最优解Dm+n1个变量组构成基变量的充要条件是它不包括任何闭回路10minZ=x1-x2，2x1+x21，x1+4x24，x1，x2=0或1，最优解是（ ）。A(0,0）B(0,1）C(1,0）D(1,1)二、判断题（你认为下列命题是否正确，对正确的打“”；错误的打“”。每小题1分，共10分）1线性规划可行域无界,则具有无界解。（ ）2整数规划的可行解集合是离散型集合。（ ）3线性规划的最优解一定是基本最优解。（ ）4可行解集有界非空时,则在极点上至少有一点达到最优解。（ ）5m+n1个变量构成基变量组的充要条件是它们不包含闭回路。（ ）6目标规划没有系统约束时，不一定存在满意解。（ ）7互为对偶问题，原问题有最优解，对偶问题可能无最优解。（ ）8匈牙利法是对指派问题求最小值的一种求解方法。（ ）9在最大流问题中，最大流是唯一的。（ ）10目标约束一定是等式约束。（ ）三、写出下列线性规划的对偶问题（10分）minZ=-x1+2x2+4x3四、求解下列线性规划（15分）minZ=-x1+2x2+3x3五、求解下列目标规划（15分）minZ=p1(d-1+d+2)+p2(d-3+d+3)+p3d-2六、求下列指派问题（min）的最优解（15分）C=七、求解下列运输问题（min）（15分）905060C=60 80 60八、求下图v1到v8最短路及最短路长。（10分）模拟考试试题参考答案模拟考试试题（一）参考答案一、单项选择题1B 2.C 3.A 4.D 5.B二、判断题1. 2. 3. 4. 5. 6. 7. 8. 9. 10.三、对偶线性规划minw=15y1+8y2四、图形为满意解：X（30，20）五、标准型maxZ=3x1+4x2+x3单纯性表：XBx1x2x3x4x5bx42311011/3x51220133/2j341000x22/311/31/301/31/2x5-1/304/3-2/317/3Mj1/30-1/3-4/30-4/3x113/21/21/201/2x501/23/2-1/215/2j0-1/2-1/2-3/203/2最优解X（1/2，0，0）；Z3/2六、用最小元素法得到初始解X=检验数，12 =0, 21=4, 23=7, 23=2，所有检验数非负，初始解也是最优解：X=，最优值Z2140七、行列分别减去最小数后：C，得到两个最优解：X1=及X2=，最优值Z=30八、1.影子价格就是对偶变量的最优解，其含义是某种资源增加一单位时目标函数的改变量；如果目标函数是利润，则当影子价格大于零时表示增加该资源能增加利润，当某种资源有剩余，影子价格一定等于零。2（1）线性规划的目标函数由决策变量构成，目标规划的目标函数由偏差变量构成；（2）线性规划求最优解，目标规划求满意解；（3）线性规划模型只有系统约束，目标规划模型可以有系统约束和目标约束；（4）性规划求最大值或最小值，目标规划只求最小值。模拟考试试题（二）参考答案一、单项选择题1A 2.B 3.B 4.D 5.C二、判断题1. 2. 3. 4. 5. 6. 7. 8. 9. 10.三、写出下列线性规划的对偶线性规划maxw=10y+8y2四、图形如下满意解为X（0，3）。五、化为等式后在第一个等式两边同乘以（1）：minZ=2x1+x2+4x3对偶单纯性表如下：XBx1x2x3x4x5bx4-1-1-110-1x5124014j21400x2111-101x5-102212j10320最优解X=（0，1，0），Z=1.六、用最小元素法求得初始解12=4,13=5,23=1,24=0,32=4,34=-3。x34进基x31出基，调整运量得到12=4,13=2,23=-2,24=0,31=3,32=7，x23进基x21出基，调整运量得到12=2,13=2,21=2,24=2,31=5,32=5，检验数全部非负，得到最优解：X=，最优值Z520七、行列分别减去最小数后：C没有被直线覆盖的元素减“1”，直线交叉的元素加“1”，其余元素不变，得到最优分配方案：X=；Z=25八、1三个要素是决策变量、目标函数及约束条件，特征如下：（1）解决问题的目标函数是多个决策变量的线性函数，求最大值或最小值；（2）解决问题的约束条件是一组多个决策变量的线性不等式或等式。2满足三个条件的流是：（1）0fijcij所有弧（i，j）（2）=所有中间点vm（3）v= =发点vs流出的总流量等于流入收点vt的总流量模拟考试试题（三）参考答案一、单选题1D 2.A 3.C 4.D 5.A 6.C 7.B 8.A 9.C 10.B二、判断题1. 2. 3. 4. 5. 6. 7. 8. 9. 10.三、对偶规划为minw=20y1+35y2四、将约束条件化为等式后两边同乘以(-1)minZ=3x1+4x2+5x3对偶单纯形表基X1X2X3X4X5bX4-1-2-310-8X5-2-2-101-10检验数34500X40-1-5/21-1/2-3X1111/20-1/25检验数017/203/2X2015/2-11/23X110-21-12检验数00111最优解X=（2，3）；最优值Z=18五、图形为满意解X（2,0）六、行列分别减去最小数或有两个最优解：X1=；X2=；Z3+1+3+2+211七、用最小元素法求得初始解11=2,12=6,22=3,23=4,得到最优解。最优解如下表B1B2B3产量A15050A26060A3108010100销量708060总运费为Z1380八、属于最小树问题，用加边法得到总长度为：8+7+8+7+3+5+6=44模拟考试试题（四）参考答案一、单选题1C 2.B 3.C 4.D 5.B 6.C 7.C 8.A 9.A 10.B二、判断题1. 2. 3. 4. 5. 6. 7. 8. 9. 10.三、对偶规划为maxw=10y1+20y2四、单纯形法标准型maxZ=x1+2x2+3x3单纯形表：XBX1X2X3X4X5bX42211088X5124011010/4j123000X47/43/201-1/422/411/3X31/41/2101/410/45j1/41/200-3/4X27/6103/2-1/611/3X3-1/301-1/31/32/3j-1/300-1/32/3最优解：X=（11/3，2/3，0，0，5/2）；最优值Z28/3五、图形为满意解X=(3/2,1/2)六、行列分别减去最小数最优解X=，Z=33七、用最小元素法求得初始解21=3,22=-4,31=5,33=11，x22进基x12出基,得到下表12=4,21=3,31=1,33=7；检验数全部非负，得到最优解：X=，最优值Z1810八、最短路的标号计算如下图所示：最短路为P18=v1,v3,v7,v8,最短路长为19。