运筹学复习习题

模拟考试试题(一)

一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分.每小题2分，共10分）

1。 博弈论中，局中人从一个博弈中得到的结果常被称为（ ）: A. 效用； B. 支付； C. 决策; D。 利润。 2。设线性规划的约束条件为

x1x2x332x12x2x44x,x,,x0412A。（0,0,4，3) A.无可行解

C.（2,0，1,0) C。有多重最优解

D.（3，0，4,0) D。有无界解

则基本可行解为（ ）。

B.（3,4,0，0） B.有唯一最优解

3．minZ=3x1+4x2， x1+x2≥4, 2x1+x2≤2， x1、x2≥0，则( ）。 4．互为对偶的两个线性规划问题的解存在关系（ ）. A.原问题无可行解，对偶问题也无可行解 B。对偶问题有可行解，原问题也有可行解 C.若最优解存在，则最优解相同

D。一个问题有无界解,则另一个问题无可行解

5．下列图形中阴影部分构成的集合是凸集的是( ）：

二、判断题（你认为下列命题是否正确，对正确的打“√\";错误的打“×”。每小题2分，共20分）

1. 线性规划问题的每一个基本可行解对应可行域的一个顶点.（ )

2。 如果在单纯形表中，所有的检验数都为正,则对应的基本可行解就是最优解。（ ) 3. 在可行解的状态下，原问题与对偶问题的目标函数值是相等的. 4．可行解集非空时,则在极点上至少有一点达到最优值。( ） 5．原问题具有无界解,则对偶问题不可行。（ ）

6．互为对偶问题,或者同时都有最优解，或者同时都无最优解。（ ） 7．加边法就是避圈法.（ )

8．一对正负偏差变量至少一个大于零.（ ） 9．要求不超过目标值的目标函数是minZ=d+。( ）

1

10．求最小值问题的目标函数值是各分枝函数值的下界.（ ） 三、填空(1分/空，共5分）

1．原问题的第1个约束方程是“=”型，则对偶问题相应的变量是 变量。 2．若原问题可行，但目标函数无界，则对偶问题 .

3. 若X和Y分别是线性规划的原问题和对偶问题的最优解，则有CX Yb. 4．可以作为表上作业法的初始调运方案的填有数字的方格数应为 个(设问题中含有m个供应地和n个需求地)

5。 物资调运问题中，有m个供应地,Al,A2…，Am,Aj的供应量为ai（i=1，2…，m)，n个需求地B1，B2，…Bn，Bj的需求量为bj(j=1，2，…，n),则供需平衡条件为 .

四、写出下列线性规划的对偶线性规划（10分） maxZ=x1+5x2—7x3

﹡

﹡

﹡

﹡

x12x26x315 x14x25x38x0,x无约束,x0231五、用图解法解下列目标规划（15分） minZ=p1（d+3+d+4）+P2d1+P3d-2

—

x1x2d1d140x1x2d2d260 x1d3d330xd4d4202x1,x2,di,di0 (i1,2,,4)六、用单纯形法解下列线性规划（15分) maxZ=3x1+4x2+x3

2x13x2x31x12x22x33 x0,j1,2,3j七、求下列运输问题（min）的最优解(10分)

5 23 

4 8C=6 13 1211 150 80 70

100 50 150

八、求下列指派问题（min）的最优解(10分）

2

10 8 56 14 12 20 17 C=8 10 9 76 5 49 3

模拟考试试题（二)

一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分.每小题2分，共10分）

1．如果某种资源的影子价格大于其市场价格，则说明（ ）。

A．该资源过剩 B．该资源稀缺 C．企业应尽快处理该资源 D．企业应充分利用该资源，开僻新的生产途径

2。 运输问题中分配运量的格所对应的变量为 （ ）。

A基变量 B 非基变量 C 松弛变量 D 剩余变量 3．maxZ=4x1—x2， 4x1+3x2≤24, x2≤5， x1、x2≥0，则（ ）。 A。无可行解

B.有唯一最优解 D。有无界解

B。逐步消除对偶问题不可行性 D.使对偶问题保持可行 B。minZ=p1d+1+p2（d—2—d+2) D。minZ=p1d—1+p2(d-2—d+2)

C。有多重最优解 A.使原问题保持可行 C。使原问题有最优解 A.minZ=p1d-1+p2（d-2+d+2) C。minZ=p1d+1+p2(d-2+d+2） 分，共20分)

1．对偶问题无可行解，原问题具有无界解。（ ） 2．对偶问题具有无界解，则原问题无最优解。（ ）

3．匈牙利法求解指派问题的条件是效率矩阵的元素非负。（ ） 4．变量取0或1的规划是整数规划.（ ） 5．图解法提供了求解线性规划问题的通用方法。 6．一对正负偏差变量至少一个等于零。( ） 7．要求至少到达目标值的目标函数是maxZ=d+.( )

8．产地数为3,销地数为4的平衡运输中，变量组{x11， x13, x22， x33, x34}可作为一组基变量。（ ）

9。 在单纯形表中，基变量对应的系数矩阵往往为单位矩阵.

10。若线性规划存在两个不同的最优解,则必有无穷个最优解。( ） 三、填空(1分/空，共5分）

1. 调运方案的调整是要在检验数出现 的点为顶点所对应的闭回路内进行运量的调整。

2．用分枝定界法求极大化的整数规划问题时,任何一个可行解的目标函数值是该问题目

4．对偶单纯形法的最小比值规划则是为了保证（ ）。

5.要求不超过第一目标值、恰好完成第二目标值，目标函数是（ ）。

二、判断题(你认为下列命题是否正确，对正确的打“√”；错误的打“×”.每小题2

4

标函数值的 .

3．在0 — 1整数规划中变量的取值可能是 。 4。 分枝定界法一般每次分枝数量为 个。 5。 在博弈中参加对策的每一方称为 。 四、写出下列线性规划的对偶线性规划（10分） minZ=2x1-x2+3x3

x12x210x13x2x38 x1,x2无约束,x30五、图解下列目标规划(15分） minZ=p1d+1+p2（d-2+d+2）

3x1x2d1d13xd2d1x224 x1,x2,d1,d1,d2,d20六、用对偶单纯形法求解（15分） minZ=2x1+x2+4x3

x1x2x31x12x24x34 x1,x2,x30七、求下列运输问题（min)的最优解（10分)

3 5 9 250 C=6 4 8 5

25 11 13 12 730

40 20 15 30

八、求下列指派问题（min）的最优解(10分)

8 9 7 10C=12 16 15 83 8 6 5 4 7 9 8

5

模拟考试试题（三）

一、单项选择题（从下列各题四个备选答案中选出一个正确答案,答案选错或未选者，该题不得分。每小题1分，共10分）

1。 线性规划模型不包括下列( ）要素。

A．目标函数 B．约束条件 C．决策变量 D．状态变量 2.在约束方程中引入人工变量的目的是（ ）。

A 体现变量的多样性 B 变不等式为等式 C 使目标函数为最优 D 形成一个单位阵 3。 求目标函数为极大的线性规划问题时，若全部非基变量的检验数≤O，且基变量中有人工变量时该问题有（ ）.

A无界解 B无可行解 C 唯一最优解 D无穷多最优解 4.线性规划最优解不唯一是指( ）。 A。可行解集合无界

k〉0

B.存在某个检验数λ且aik≤0（i=1,2,…,m) C.可行解集合是空集 A。无可行解

B.有唯一最优解

D.最优表中存在非基变量的检验数为零 C。有无界解

D.有多重解

5.minZ=4x1+6x2，4x1+3x2≤24，x2≥9，x1，x2≥0，则（ ). 6.原问题有5个变量3个约束，其对偶问题( )。 A.有3个变量3个约束 C。有3个变量5个约束 7.下列错误的结论是（ ）。

A.原问题没有最优解，对偶问题也没有最优解 B.对偶问题有可行解，原问题也有可行解 C.原问题有最优解，对偶问题也有最优解 D。原问题无界解，对偶问题无可行解

8.maxZ=3x1+2x2，2x1+3x2≤14，x1+0.5x2≤4。5，x1,x2≥0且为整数，对应线性规划的最

B。有5个变量3个约束 D.有5个变量5个约束

优解是（3.25，2.5），它的整数规划的最优解是（ ）。

A．(4,1) A．maxZ=d-

B．(4，3) B．maxZ=d+

C．(3，2) C．minZ=d B.使原问题保持可行

D.寻找进基变量

—

D．(2，4) D．minZ=d+

9．要求不低于目标值，其目标函数是( ）。 10．单纯形法的最小比值规划则是为了（ ）。 A.使对偶问题保持可行 C。尽快达到最优解 分,共10分）

1．若原问题具有m个约束，则它的对偶问题具有m个变量。( ) 2．动态规划只是用来解决和时间有关的问题。（ ）

6

二、判断题（你认为下列命题是否正确，对正确的打“√”；错误的打“×”。每小题1

3. 线性规划问题的最优解一定在可行域的顶点达到.( ）

4。 如果一个线性规划问题有可行解，那么它必有最优解。( ）

5。 用单纯形法求解一般线性规划时，当目标函数求最大值时，若所有的检验数Cj-Zj≤0，则问题达到最优。（ ）

6．线性规划的最优解是可行解。（ ）

7．目标约束一定是等式约束。（ ） 8．运输问题一定存在最优解。（ ） 9．人工变量出基后还可能再进基。（ ）

10．对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。（ ） 三、填空（1分/空，共5分）

1．线性规划闯题中，如果在约束条件中出现等式约束,我们通常用增加 的方法来产生初始可行基。

2．目标规划总是求目标函数的 值，且目标函数中没有线性规划中的价值系数，而是在各偏差变量前加上级别不同的优先因子。

3。 若线性规划问题有最优解,则最优解一定可以在可行域的 达到。

4．对于目标函数极大值型的线性规划问题，用单纯型法求解时，当基变量检验数 时，当前解为最优解。

5. 如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为 。 四、写出下列线性规划的对偶线性规划（10分） maxZ=5x1+4x2-6x3

x12x28x3204x1x2x335 x,x,x0123五、用对偶单纯形法求解下列线性规划（15分） minZ=3x1+4x2+5x3

x12x23x382x12x2x310 x,x,x0123六、求解下列目标规划（15分） minZ=p1（d1+d+2)+p2d

—

—

3

7

x1x2d1d112x12x2d2d24 6x14x2d3d336x,x,di,di0,i1,2,312七、求解下列指派问题(min)（10分)

9 2 3 73 6 1 5 6 67 10 3 C=9 4 2 5 4 2 14 69 6 2 

八、求解下列运输问题（min）（15分)

8 7 4

12C=10 9 810 5 70 80 60

50 60 100

模拟考试试题（四）

一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。每小题1分，共10分）

1．线性规划具有无界解是指（ )。 A。可行解集合无界 B.有相同的最小比值

C.存在某个检验数λk＞0且aik≤0(i=1,2,…,m） D。最优表中所有非基变量的检验数非零 2．若线性规划存在可行解，则（ ）。 A。一定有最优解 C。有多重解

B.可行域非空 D.具有无界解

B.有9个变量20个约束 D.有9个基变量

3．有4个产地5个销地的平衡运输问题模型具有特征（ )。 A。有9个变量9个约束 C.有20个变量9个约束 A.若最优解存在,则最优解相同 B.原问题无可行解,对偶问题也无可行解 C。一个问题无界，则另一个问题也无解

8

4．互为对偶的两个线性规划问题的解存在关系（ ）.

D。若最优解存在，则最优值相同 5．在分枝定界法中（ ）。

A。最大值问题的目标值是各分枝的下界 B.最大值问题的目标值是各分枝的上界 C。最小值问题的目标值是各分枝的上界 D。以上结论都不对

6．下例错误的说法是( ）. A.标准型的目标函数是求最大值 C。标准型的常数项非正

7．表上作业法中初始方案均为( ).

A 可行解 B 非可行解 C 待改进解 D 最优解 8．minZ=3x1+4x2,x1+x2≥4,2x1+x2≤2，x1、x2≥0，则（ ）. A．无可行解

B．有唯一最优解

C．有多重最优解

D．有无界解

B。标准型的目标函数是求最小值 D.标准型的变量一定要非负

9. 下列方法中用于求解分配问题的是（ ）。

A．单纯形表B．分枝定界法C．表上作业法D．匈牙利法

10．minZ=x1—x2，2x1+x2≥1,x1+4x2≤4,x1,x2=0或1，最优解是（ ）. A．(0,0） 分，共10分）

1．线性规划可行域无界，则具有无界解。（ ）

2. 对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定 有最优解。( )

3. 表上作业法实质上就是求解运输问题的单纯形法.（ ) 4. 指派问题的解中基变量的个数为m＋n.( ) 5。 整数规划的可行解集合是离散型集合。（ ）

6. 在解静态规划模型时，线性与非线性规划中约束条件的个数,相当于动态规划中状态变量的维数。( )

7. 一个博弈中，直接决定局中人支付的因素是信息。（ )

8. 在层次分析法中只需要比较n—1次就可以构造判断矩阵。( ）

9．在解目标规划时，若某一较高级别目标未满足，则其后较低级别目标也不能满足。（ ）

10．在用割平面法求解整数规划时，经过有限次迭代一定可以割出极点为整数的点.（ ）

三、填空（1分/空,共5分）

6。 若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX Yb。 7．如果线性规划的原问题增加一个约束条件，相当于其对偶问题增加一个 。

9

B．（0，1） C．(1,0） D．(1,1)

二、判断题（你认为下列命题是否正确，对正确的打“√”；错误的打“×”.每小题1

8．按照表上作业法给出的初始调运方案，从每一空格出发可以找到且仅能找到条闭回路。

9。 对于一个有n项任务需要有n个人去完成的分配问题,其解中取值为1的变量数为 个。

10。经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数为动态规划的 。

四、写出下列线性规划的对偶问题（10分） minZ=-x1+2x2+4x3

x1x26x310x1x2x320 x1,x20无限制五、求解下列线性规划(15分) minZ=-x1+2x2+3x3

2x12x2x38x12x24x310 x1,x2,x30无限制六、求解下列目标规划（15分) minZ=p1(d—

1+d+2）+p2（d—

3+d+3)+p3d

—

2

x1x2d1d11x1x2d2d22x1 x12d3d3x1,x2,di,di0,i1,2,3七、求下列指派问题（min）的最优解（15分）

4 10 16 18C=5 8 12 177 9 15 14 6 11 19 8八、求解下列运输问题（min）（15分）

90 C=14 18 138 5 4

50 7 6 1260

60 80 60

10

模拟考试试题参考答案

模拟考试试题（一）参考答案

一、单项选择题

1．B 2.C 3。A 4.D 5.A 二、判断题

1. √ 2。× 3。× 4.× 5.√ 6。√ 7。√ 8。× 9。√ 10.√ 三、1.自由， 2。不可行， 3。=, 4。m+n—1， 5。 四、对偶线性规划 minw=15y1+8y2

mnabii1j1j

y1y212y4y512 -6y5y-712y10,y2无约束五、图形为

满意解：X＝（30，20) 六、标准型 maxZ=3x1+4x2+x3

2x13x2x3x41x12x22x3x53 x0,j1,2,5j单纯性表:

XB x4 x5 x1 2 1 3 ［2/3］ x2 ［3] 2 4 1 x3 1 2 1 1/3 x4 1 0 0 1/3 x5 0 1 0 0 b 1 3 0 1/3 θ 1/3 3/2 1/2 λj x2 11

x5 -1/3 0 4/3 —2/3 1 7/3 λj 1/3 0 —1/3 -4/3 0 —4/3 x1 1 3/2 1/2 1/2 0 1/2 x5 0 1/2 3/2 -1/2 1 5/2 λj 0 -1/2 —1/2 -3/2 0 3/2 最优解X＝（1/2,0，0）；Z＝3/2 七、用最小元素法得到初始解

 70X=30  50

30120 检验数，λ12 =0, λ21=4， λ23=7, λ23=2，所有检验数非负，初始解也是最优解：30 70X=  50，最优值Z＝2140

 30120八、行列分别减去最小数后：

1 5 3 00 5 2 0C→2 0 8 51 0 7 51 3 2 0→0 3 1 ，得到两个最优解： 5 2 1 004 2 1 01 1X 11=

 及1 1X2=1，最优值Z=30  1 1

M 12

模拟考试试题（二）参考答案

一、单项选择题

1．B 2. A 3。B 4.D 5.C 二、判断题

1.× 2.√ 3.√ 4。√ 5。× 6.√ 7。× 8。× 9. √ 10.√ 三、1。负值， 2.下界， 3.0或1, 4。2, 5. 局中人 四、写出下列线性规划的对偶线性规划 maxw=10y+8y2

y1y222y3y112 y32y1无约束，y20五、图形如下

满意解为X＝（0，3）。

六、化为等式后在第一个等式两边同乘以（－1）: minZ=2x1+x2+4x3

x1x2x3x41x12x24x3x54 x,x,,x0512对偶单纯性表如下：

XB x4 x5 λj x1 —1 1 2 x2 ［—1］ 2 1 x3 —1 4 4 x4 1 0 0 x5 0 1 0 b -1 4 13

x2 x5 λj 1 —1 1 1 0 0 1 2 3 -1 2 2 0 1 0 1 2 最优解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,检验数全部非负，得到最优解：

1040 ,最优值Z＝520

20 5X=  10 20 

14

八、行列分别减去最小数后：

2 0 3  1 0 0 31 4 4 6 8 7 07 0→ C→0 5 3 20 3 3 20 3 5 40 1 5 4没有被直线覆盖的元素减“1\"，直线交叉的元素加“1”，其余元素不变,得到

2 0 0 4 4 5 6 00 2 2 0 0 0 4 4最优分配方案：

 1X= 1；Z=25  1 1

模拟考试试题（三）参考答案

一、单选题

1．D 2。 D 3. B 4.D 5.A 6。C 7。B 8。A 9。C 10。B 二、判断题

1.√ 2.× 3。× 4. × 5。√ 6.√ 7。 √ 8。√ 9.×三、1。人工变量,2。最小,3。顶点(极点）,4. δj≤0，5.等式 四、对偶规划为 minw=20y1+35y2

y14y252y1y24y 81y26y10,y20五、将约束条件化为等式后两边同乘以(—1) minZ=3x1+4x2+5x3

。× 15

10 x12x23x3x482x12x2x3x510 x,x,x,x,x012345对偶单纯形表

基 X1 —1 —2 3 0 1 0 0 1 0 X2 —2 —2 4 -1 1 1 1 0 0 X3 —3 -1 5 -5/2 1/2 7/2 5/2 —2 1 X4 1 0 0 1 0 0 -1 1 1 X5 0 1 0 -1/2 —1/2 3/2 1/2 —1 1 b -8 —10 —3 5 3 2 X4 X5 检验数 X4 X1 检验数 X2 X1 检验数 最优解X=（2，3)；最优值Z=18 六、图形为

满意解X＝（2,0） 七、行列分别减去最小数

3 9 2 3 76 1 5 6 69 4 7 10 32 5 4 2 19 6 2 4 61 51 7 0 5 0 4 5 56 1 4 7 01 4 3 1 07 4 0 2 40 7 0 0 50 7 0 0 54 0 4 4 54 0 4 4 55 1 4 6 0或5 1 4 6 0 0 4 3 0 00 4 3 0 01 41 46 4 0 6 4 0  1 1 1 1 1；X2= 1； 有两个最优解：X1= 1 111  Z＝3+1+3+2+2＝11

八、用最小元素法求得初始解

16

λ11=2,λ12=6,λ22=3，λ23=4,得到最优解。

最优解如下表

A1 A2 A3 销量 B1 60 10 70 B2 80 80 B3 50 10 60 产量 50 60 100 总运费为Z＝1380

模拟考试试题（四）参考答案

一、单选题

1．C 2。B 3。C 4。D 5。B 6.C 7. A 8。A 9. D 10.B 二、判断题

1。× 2.√ 3。 √ 4. × 5.√ 6.√ 7。× 8. × 9.× 10.√ 三、1. ≤,2. 变量，3. 1， 4. n， 5。 阶段数 四、对偶规划为 maxw=10y1+20y2

y1y21yy211 6yy421y1无限制，y20五、单纯形法 标准型

maxZ=x1+2x2+3x3

2x2x3x48x12x14x1x110 x,x,,x0512

17

单纯形表:

XB X4 X5 λj X4 X3 λj X2 X3 λj X1 2 1 1 7/4 1/4 1/4 7/6 -1/3 -1/3 X2 2 2 2 ［3/2］ 1/2 1/2↑ 1 0 0 X3 1 [4］ 3↑ 0 1 0 0 1 0 X4 1 0 0 1 0 0 3/2 —1/3 —1/3 X5 0 1 0 -1/4 1/4 —3/4 —1/6 1/3 2/3 b 8 10 0 22/4 10/4 11/3 2/3 θ 8 10/4 11/3 5 最优解：X=(11/3,2/3,0，0,5/2）；最优值Z＝28/3 六、图形为

满意解X=(3/2，1/2） 七、行列分别减去最小数

12 140 4 5 120 6 0 3 7 0 121 0 10→ 0 2 8 70 0 1 50 5 13 20 3 5 01 1，Z=33 最优解X= 1 1八、用最小元素法求得初始解

18

λ21=3,λ22=—4，λ31=5，λ33=11，x22进基x12出基，得到下表

λ12=4，λ21=3,λ31=1,λ33=7；检验数全部非负,得到最优解：

X=60 30 20 30,最优值Z＝1810

 60

19