运筹学知识学习与考试指导

1、运筹学学习与考试指导模拟考试试题(一)一、单项选择题(从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。每小题2 分，共 10 分) B 2.C 3.A 4.D5.B1 线性规划具有唯一最优解是指() 。A. 不加入人工变量就可进行单纯形法计算B.最优表中非基变量检验数全部非零C.最优表中存在非基变量的检验数为零D.可行解集合有界2 .设线性规划的约束条件为x1 x2x332x12x2x44x1,x2,x40则基本可行解为()。A.(0,0,4,3)B.(3,4,0,0)C.(2,0,1,0)D.(3,0,4,0)3. min Z=3 Xi+4 X2, X1+X2K, 2

2、 xi+ X2<2, x1、X2 R ,贝 ()。A.无可行解B.有唯一最优解C.有多重最优解D.有无界解4互为对偶的两个线性规划问题的解存在关系(d ) 。A. 原问题无可行解，对偶问题也无可行解B.对偶问题有可行解，原问题也有可行解C.若最优解存在，则最优解相同D.一个问题有无界解，则另一个问题无可行解5 有 6 个产地 4 个销地的平衡运输问题模型具有特征（b ） 。A.有10个变量24个约束B.有24个变量10个约束C.有24个变量9约束D.有9个基变量10个非基变量二、判断题（你认为下列命题是否正确，对正确的打；错误的打“X”。每小题2分，共 20 分）1 若线性规划无最优解则

3、其可行域无界。（）2 凡基本解一定是可行解。（）3 线性规划的最优解一定是基本最优解。（）4可行解集非空时,则在极点上至少有一点达到最优值。（）5 原问题具有无界解，则对偶问题不可行。（）6 互为对偶问题，或者同时都有最优解，或者同时都无最优解。（）7 加边法就是避圈法。（）8 一对正负偏差变量至少一个大于零。（）9 要求不超过目标值的目标函数是minZ=d+ 。 （）10 求最小值问题的目标函数值是各分枝函数值的下界。（）x1 2x2 6x3 15x1 4x2 5x38x1 0, x2无约束,x3 0四、用图解法解下列目标规划(15 分)min Z= p1(d+3+d +4)+ P2d-1+

4、 P3d-2x1x2d 1d140x1x2d 2d260x1d3 d330x2d4 d420x1,x2,d i,d i 0(i1,2,4)五、用单纯形法解下列线性规划(15 分)max Z=3 x1+4 x2+x32x1 3x2 x31x1 2x2 2x33xj 0, j 1,2,3六、求下列运输问题（min ）的最优解（10 分）352C= 6481113121005015080 70150七、求下列指派问题6108514 122017C=810 979654min ）的最优解（10 分）八、简答下列问题（每小题5 分，共 10 分）1 什么是影子价格，怎样利用影子价格作经济活动分析2 线性

5、规划与目标规划有什么区别模拟考试试题（二）一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。每小题2 分，共 10 分）1. 线性规划无可行解是指（a ） 。A. 用大 M 法求解时,最优解中还有非零的人工变量B.进基列系数非正C.有两个相同的最小比值D.可行域无界2 .设线性规划的约束条件为x1 x2x332x12x2x44x1,x2,x40则可行解为（b ） 。A.（0,0,4,3）B.（1,1,1,0）C.（3,4,0,0）D.（3,0,4,0）3 . maxZ=4xi-X2, 4xi+3 X2<24, X2<5, xi、X2R,则（b

6、）。A.无可行解B.有唯一最优解C.有多重最优解D.有无界解4对偶单纯形法的最小比值规划则是为了保证（A. 使原问题保持可行B.逐步消除对偶问题不可行性C.使原问题有最优解D.使对偶问题保持可行5.要求不超过第一目标值、恰好完成第二目标值，目标函数是（c） 。A.minZ= p1d-1+ p2（d -2+ d+2）B.min Z= p1d+1 + p2（d-2-d+2）C.min Z=p1d+1+ p2（d-2+d+2）D.min Z= p1d-1+ p2（d-2-d+2）二、判断题（你认为下列命题是否正确，对正确的打；错误的打“X”。每小题2分，共 20 分）1 对偶问题无可行解，原问题具有

7、无界解。（ f ）2 对偶问题具有无界解，则原问题无最优解。（ t ）3 匈牙利法求解指派问题的条件是效率矩阵的元素非负。（ t ）4变量取0 或 1 的规划是整数规划。（ t ）5 . B一条增广链，则后向弧上满足流量f R。（ f ）6 一对正负偏差变量至少一个等于零。（ t ）7 要求至少到达目标值的目标函数是max Z= d+。 （ f ）8 .产地数为3,销地数为4的平衡运输中，变量组X11, X13, X22, X33, X34可作为一组基变量。 （ f ）9 .最大流量等于最大流。（f）10 . 若线性规划存在两个不同的最优解,则必有无穷个最优解。（ t ）三、写出下列线性规划的

8、对偶线性规划（10 分）min Z=2 X1 -X2+3 X3x1 2x2 10x1 3x2 x3 8x1,x2无约束，x3 0（15 分 ）min Z= p1d+ 1+ p2（d-2+ d+2）3x1 x2 d 1 d 13x1 x2 d 2 d 24x1,x2,d 1, d 1,d 2,d 20五、用对偶单纯形法求解（15 分 ）min Z=2 x1 + x2 +4 x3x1 x2 x31x1 2x2 4x3 4x1, x2 , x30六、求下列运输问题（min ）的最优解（10 分 ）5025303592C= 648511 13 12740201430七、求下列指派问题（min ）的最优

9、解（10 分 ）897101216 158C=38654798八、简答下列问题（每小题5 分，共 10 分）1 简述线性规划数学模型的三个要素及其特征。2 满足哪三个条件的流是可行流？模拟考试试题（三）、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者,该题不得分。每小题1 分，共 10 分）1 有 3 个产地 4 个销地的平衡运输问题模型具有特征（d ） 。,m )A. 有 7 个变量C.有6约束2 .线性规划可行域的顶点一定是（aA.基本可行解B.非基本解3 . X 是线性规划的基本可行解，则有（A. X 中的基变量非零，非基变量为零B. X 不一定满足约束条件C.

10、X 中的基变量非负，非基变量为零D. X是最优解4.线性规划最优解不唯一是指（d ）A. 可行解集合无界C.可行解集合是空集B.有12个约束D.有6个基变量）。C.非可行解D.最优解c ）。B.存在某个检验数Zk>0且aikW0（i=1,2, D.最优表中存在非基变量的检验数为零5.min Z=4 xi+6 X2, 4xi+3 X2W24 , X2>9, xi, x2>0 ,贝U ( a)。A. 无可行解B.有唯一最优解C.有无界解D.有多重解五、求解下列目标规划（15 分）6.原问题有5 个变量 3 个约束，其对偶问题（A. 有 3 个变量 3 个约束B.有5个变量3个约束

11、C.有3个变量5个约束D.有5个变量5个约束7 .下列错误的结论是（b ） 。A. 原问题没有最优解，对偶问题也没有最优解8 .对偶问题有可行解，原问题也有可行解C.原问题有最优解，对偶问题也有最优解D.原问题无界解，对偶问题无可行解9 .max Z=3 xi+2 X2,2xi+3X2W14,xi+0.5 X2<4.5,xi,X2R 且为整数，对应线性规划的最优解是（ 3.25 ， 2.5） ，它的整数规划的最优解是（） 。A （4， 1）B （4， 3）9 要求不低于目标值，其目标函数是（A max Z= d-B maxZ=d +10 单纯形法的最小比值规划则是为了（A. 使对偶问题保

12、持可行C（3， 2）D（2，4）c ）。Cmin Z=d-DminZ=d+b ）。B.使原问题保持可行C.尽快达到最优解D.寻找进基变量、判断题（你认为下列命题是否正确，对正确的打；错误的打“X”。每小题11 若原问题具有m 个约束，则它的对偶问题具有m 个变量。 （ t ）2 正偏差变量大于等于零，负偏差变量小于等于零。（ f ）3 要求不超过目标值的目标函数是min Z=d -。 （ f ）4 部分变量要求是整数的规划问题称为混合整数规划。（ t ）5 匈牙利法是求解最小值的分配问题。（ t ）6 线性规划的最优解是可行解。（ t）7 可行解是基本解。（ f ）8 运输问题一定存在最优解。

13、（ t）9 人工变量出基后还可能再进基。（ f ）10 求最大流问题就是在网络中找一条从起点到终点的路，使得这条路上通过的流量最大。 （ f ）三、写出下列线性规划的对偶线性规划（10 分）max Z=5 x1+4 x2-6 x3x1 2x2 8x3204x1 x2 x3 35x1, x2 , x30四、用对偶单纯形法求解下列线性规划（15 分）min Z=3 x1 +4 x2+5 x3x1 2x2 3x382x1 2x2 x3 10x1, x2 , x30模拟考试试题（四）min Z= pi(d-i+d+2)+p2d-3x1 x2 d i d i 12x1 2x2 d 2 d 2 46x1

14、4x2 d 3 d 3 36 x1,x2,d i,d i 0,i 1,2,3六、求解下列指派问题（min ） （10分）392615C= 94725437661032146七、求解下列运输问题min(15 分)96287450C= 10 91210586070 80 60100八、已知世界八大城市之间的距离（千公里）如下表，试建立一个因特网使总距离最短。（15分）两城市之间的距离（千公里）123456781121081213141329713111512313128101641179958576367148一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者,该题不得分。

15、每小题 1分，共10分）1 .线性规划具有无界解是指（ c ）。A.可行解集合无界B.有相同的最小比值C.存在某个检验数 兀0且aikW0 （i=1,2 ,m）D.最优表中所有非基变量的检验数非零2 .若线性规划存在可行解，则（ b ）。A. 一定有最优解B.可行域非空C.有多重解D.具有无界解3 .有4个产地5个销地的平衡运输问题模型具有特征（ c ）。A.有9个变量9个约束B.有9个变量20个约束C.有20个变量9个约束D.有9个基变量4 .互为对偶的两个线性规划问题的解存在关系（ d ）。A.若最优解存在，则最优解相同8 .原问题无可行解，对偶问题也无可行解C.一个问题无界，则另一个问题

16、也无解D.若最优解存在，则最优值相同5 在分枝定界法中（b ）A. 最大值问题的目标值是各分枝的下界B.最大值问题的目标值是各分枝的上界C.最小值问题的目标值是各分枝的上界D.以上结论都不对6 下例错误的说法是（c ） 。A.标准型的目标函数是求最大值B.标准型的目标函数是求最小值C.标准型的常数项非正D.标准型的变量一定要非负7 .设P是图G从vs到vt的最短路，则有（ c ）。A.P的最短路长等于vs到vt的最大流量8 .P的长度等于G的每条边的长度之和C.P的长度等于P的每条边的长度之和D.P 有 n 个点和 n-1 条边9 . min Z=3 xi+4 X2, xi + x2>4

17、 , 2xi + X2W2, xi、X2R0,贝U （）。A.无可行解B.有唯一最优解 C.有多重最优解D.有无界解10 下列结论错误的有（a ） 。A.任意一个运输问题不一定存在最优解11 任何运输问题都存在可行解C.产量和销量均为整数的运输问题必存在整数最优解D m+n 1 个变量组构成基变量的充要条件是它不包括任何闭回路10. minZ=xi-X2, 2xi+X2>1 , xi+4x244, xi, X2=0 或1,最优解是(A (0,0)B(0,i )C (i,0)D (i,i)二、判断题（你认为下列命题是否正确，对正确的打；错误的打“x”。每小题1分，共 i0 分）1 线性规划

18、可行域无界,则具有无界解。（f）2 整数规划的可行解集合是离散型集合。（ t ）3 线性规划的最优解一定是基本最优解。（ f ）4 可行解集有界非空时,则在极点上至少有一点达到最优解。（ t ）5 m+ n 1 个变量构成基变量组的充要条件是它们不包含闭回路。（ t ）6 目标规划没有系统约束时，不一定存在满意解。（ f ）7 互为对偶问题，原问题有最优解，对偶问题可能无最优解。（ f ）8 匈牙利法是对指派问题求最小值的一种求解方法。（ t ）9 在最大流问题中，最大流是唯一的。（ f ）10 目标约束一定是等式约束。（ t ）三、写出下列线性规划的对偶问题（10 分）min Z=- x1

19、+2 x2+4 x3x1 x2 6x3 10x1 x2 x3 20x1 , x2 0无限制四、求解下列线性规划（15 分）min Z=- x1 +2 x2+3 x32x1 2x2 x3 8x1 2x2 4x3 10x1,x2,x3 0无限制五、求解下列目标规划（15分）min Z= p1（d-1+d+2）+p2（d-3+x1x2d1d11x1x2d2d22x1x2d3d31x1,x2,d i,d i 0,i 1,2,3六、求下列指派问题（min ）4101618581217C=791514611198七、求解下列运输问题（min141813C=854761260 80 60d+3）+p 3d-

20、2的最优解（15分）（15 分）905060八、求下图V1到V8最短路模拟考试试题()参考答案、单项选择题二、判断题1 .X 2.X 3.X 4.X 5.V 6.V 7.V 8.X 9.V 10.V三、对偶线性规划min w=15 yi+8yyi V2 12yi 4y2 5-6% 5y2 -7yi 0, y2无约束四、图形为模拟考试试题参考答案max Z=3 xi+4 X2+X3满意解：X= (30, 20)五、标准型2x1 3x2 x3 x41x1 2x22x3x53xj 0,j 1,2 ,5单纯性表:Xbx1x2x3x4x5bex42311011/3x51220133/2为341000x2

21、2/311/31/301/31/2x5-1/304/3-2/317/3M无1/30-1/3-4/30-4/3x113/21/21/201/2x501/23/2-1/215/20-1/2-1/2-3/203/2最优解 X= ( 1/2 , 0, 0); Z=3/2六、用最小元素法得到初始解3070X=50120 30检验数，入 12 =0,屹1=4,3=7, 223=2 ,所有检验数非负，初始解也是最优解:3070Z = 2140X=50,最优值120 30七、行列分别减去最小数后：2 075人口，得到两个取优解:1 01 0153005208510C1320035210421111X1=及 X

22、2=，最优值Z=301111八、 1. 影子价格就是对偶变量的最优解，其含义是某种资源增加一单位时目标函数的改变量；如果目标函数是利润，则当影子价格大于零时表示增加该资源能增加利润，当某种资源有剩余，影子价格一定等于零。（ （ 1 ）线性规划的目标函数由决策变量构成，目标规划的目标函数由偏差变量构成；（ 2）线性规划求最优解，目标规划求满意解；（ 3）线性规划模型只有系统约束，目标规划模型可以有系统约束和目标约束；（ 4）性规划求最大值或最小值，目标规划只求最小值。模拟考试试题（二）参考答案一、单项选择题1 . A 2.B 3.B 4.D 5.C二、判断题1.X 2.V 3.V4.V 5.X

23、6.V 7.X 8.X 9. X 10. V三、写出下列线性规划的对偶线性规划max w=10 y+8 yyiV2 22yi 3y21y23yi无约束，y20四、图形如下满意解为X= （0, 3）。五、化为等式后在第一个等式两边同乘以（1）：Xi X2 X3 X4 x1 2x2 4x3 x54Xi,X2,决 0对偶单纯性表如下:XbXiX2X3X4X5bX4-i-i 1-ii0-iX5i240i4j2i400X2iii-i0iX5-i022i2ji0320最优解 X= (0, i, 0), Z=i.六、用最小元素法求得初始解FfutnToBiBiHiSupplyAi35925020JOAz64

24、S525520出11J31273015"15Demand403015Zi2=4,杷=5, ?23 = 1,m4=0, ?32=4,%4=-3 。 X34进基X31出基，调整运量得到FfufflToBiBiSupplyAiJ592如15ISAi64s52S5*2011J312?3015ISDemand和301530Zi2=4,杷=2,屹3=-2, ?24=0, ?3i =3, ?32=7 , X23 进基 X2I 出基，调整运量得到FrutnToBi由SupplyAiJ592*44)wAi64s5255As1112?301020Demand4015a2=2, ?13=2,为1=2,抽4

25、=2,拈1=5,入32=5 ,检验数全部非负，得到最优解:4010X=205,最优值 Z = 52010 20七、行列分别减去最小数后:1203487005320354没有被直线覆盖的元素减1”，直线交叉的元素加“ 1”，其余元素不变，得到2004456002200044最优分配方案:X=； Z=2511八、 1 三个要素是决策变量、目标函数及约束条件，特征如下：1 ）解决问题的目标函数是多个决策变量的线性函数，求最大值或最小值；2）解决问题的约束条件是一组多个决策变量的线性不等式或等式。2 满足三个条件的流是：(1) OwfijWcj 所有弧i， j）Vm3) v=fimfmjVm所有中间点

26、vmfit发点Vs流出的总流量等于流入收点 Vt的总流量VsVi模拟考试试题（三）参考答案参考答案、单选题1 D 2.A3.C4.D 5.A 6.C 7.B 8.A9.C 10.B二、判断题1.V 2.X3.x4.V 5.V 6.V 7. X8.V 9. x 10. x三、对偶规划为min w=20 y1 +35 y2Vi 4y252yi V248Vi V26Vi 0, V2 0四、将约束条件化为等式后两边同乘以(-1)min Z=3 xi+4 X2+5 X3Xi2x，2 3X3X42Xi 2x2 X3 X510Xi,X2,X3,X4,X5对偶单纯形表基XiX2X3X4X5bX4-i-2-3i

27、0-8X5-2-2-i0i-i0检验数34500X40-i-5/2i-i/2-3Xiiii/20-i/25检验数0i7/203/2X20i5/2-ii/23Xii0-2i-i2检验数00iii最优解X= (2, 3);最优值Z=18五、图形为满意解X= (2,0)六、行列分别减去最小数17 0 156 15 6 69 4 7 10 36 1 47 0:5 114 3 107 4 0 2 41111有两个最优解：X1=1 ; X2=1 ；1111Z=3+1+3+2+2=11七、用最小元素法求得初始解FromTobiHiSuppJyAi745030Ai10g12ao60Ai10510010ROD em and70RO60柏=2,为2=6,欣=