运筹学试题库

1、下面命题正确的是（ ）。

A、线性规划的标准型右端项非零； B、线性规划的标准型目标求最大；

C、线性规划的标准型有等式或不等式约束； D、线性规划的标准型变量均非负。

2、下面命题不正确的是（ ）。

A、线性规划的最优解是基本解； B、基本可行解一定是基本解； C、线性规划有可行解则有最优解； D、线性规划的最优值至多有一个。 3、设线性规划问题（P），它的对偶问题（D），那么（ ）。

A、若（P）求最大则（D）求最小；B、（P）、（D）均有可行解则都有最优解；

C、若（P）的约束均为等式，则（D）的所有变量均无非负； D、（P）和（D）互为对偶。

4、课程中讨论的运输问题有基本特点（ ）。

A、产销平衡； B、一定是物品运输的问题； C、是整数规划问题； D、总是求目标极小。 5、线性规划的标准型有特点（ ）。

A、右端项非零； B、目标求最大； C、有等式或不等式约束； D、变量均非负。 6、下面命题不正确的是（ ）。

A、线性规划的最优解是基本可行解；B、基本可行解一定是基本解； C、线性规划一定有可行解； D、线性规划的最优值至多有一个。 7、线性规划模型有特点（ ）。

A、所有函数都是线性函数； B、目标求最大； C、有等式或不等式约束； D、变量非负。 8、下面命题正确的是（ ）。

A、线性规划的最优解是基本可行解；B、基本可行解一定是最优； C、线性规划一定有可行解； D、线性规划的最优值至多有一个。 9、一个线性规划问题（P）与它的对偶问题（D）有关系（ ）。 A、（P）有可行解则（D）有最优解；B、（P）、（D）均有可行解则都有最优解；

C、（P）可行（D）无解，则（P）无有限最优解；D、（P）（D）互为对偶。 10、运输问题的基本可行解有特点（ ）。 A、有m＋n－1个基变量； B、有m+n个位势； C、产销平衡； D、不含闭回路。

二、简答题

（1）微分学求极值的方法为什么不适用于线性规划的求解

（2）线性规划的标准形有哪些如何把一般的线性规划化为标准形式 （3）图解法主要步骤是什么从中可以看出线性规划最优解有那些特点

（4）什么是线性规划的可行解，基本解，基可行解引入基本解和基可行解有什么作用

（5）对于任意基可行解，为什么必须把目标函数用非基变量表示出来什么是检验数它有什么作用如何计算检验数

（6）确定换出变量的法则是什么违背这一法则，会发生什么问题 （7）如何进行换基迭代运算

（8）大M法与两阶段法的要点是什么两者有什么共同点有什么区别 （9）松弛变量与人工变量有什么区别试从定义和处理方式两方面分析。 （10）如何判定线性规划有唯一最优解，无穷多最优解和无最优解为什么 （11）如何在以B为基的单纯形表中，找出B该表是怎样由初始表得到的 （12）对偶问题的构成要素之间，有哪些对应规律 （13）如何从原问题最优表中，直接找到对偶最优解 （14）叙述互补松弛定理及其经济意义。

（15）什么是资源的影子价格它在经济管理中有什么作用

（16）对偶单纯形法有哪些操作要点它与单纯形法有哪些相同，哪些地方有区别 （17）灵敏度分析主要讨论什么问题分析的基本思路是什么四种基本情况的分析要点是什么

三、模型建立题

（1）某厂生产A，B，C三种产品，每件产品消耗的原料和设备台时如表3-1所示： 表3-1 产品 原料单耗 机时单耗 利润 －1

A 2 10 B 3 3 14 C 5 6 20 资源数量 2000 2600 另外，要求三种产品总产量不低于65件，A的产量不高于B的产量。试制定使总利润最大的模型。

（2）某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻井费用最小。若10个井位的代号为s1,s2,s3Ls10，相应的钻井费用为c1,c2,L,c10，并且井位选择上要满足下列条件：

①或选择s1和s7，或选择钻探s8；

②选择了s3或s4就不能选s5，或反过来也一样；

③在s5,s6,s7,s8中最多只能选两个；试建立这个问题的整数规划模型。

（3）某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址代号及其能覆盖的居民小区编号如表3–2所示，问为覆盖所有小区至少应建多少所小学，要求建模并求解。

表3–2 备选校址代号 覆盖的居民小区编号 A B C D E F 1，5，7 1，2，5 1，3，5 2，4，5 3，6， 4，6， （4）一货船，有效载重量为24吨，可运输货物重量及运费收入如表3-3所示，现货物2、4中优先运2，货物1、5不能混装，试建立运费收入最多的运输方案。

表3-3 货物 重量（吨） 1 5 2 9 4 3 8 4 4 7 3 5 10 5 6 23 7 收入（万元） 1 （5） 运筹学中著名的旅行商贩（货朗担）问题可以叙述如下：某旅行商贩从某一城市出发，到其他几个城市推销商品，规定每个城市均需到达且只到达一次，然后回到原出发城市。已知城市i和城市j之间的距离为dij问商贩应选择一条什么样的路线顺序旅行，使总的旅程最短。试对此问题建立整数规划模型。

四、计算及分析应用题

（1）某公司打算利用具有下列成分（见表4-1）的合金配制一种新型合金100公斤，新合金含铅，锌，锡的比例为3：2：5。

表4-1 合金品种 含铅% 含锌% 含锡% 单价（元/kg） 1 30 60 10 2 10 20 70 3 50 20 30 4 10 10 80 5 50 10 40 如何安排配方，使成本最低

（2）某医院每天各时间段至少需要配备护理人员数量见表4-2 表4-2

班次 1 2 3 4 5 6 时间 6:00－10:00 10:00－14:00 14:00－18:00 18:00－22:00 22:00－2:00 2:00－6:00 最少人数 60 70 60 50 20 30 假定每人上班后连续工作8小时，试建立使总人数最少的计划安排模型。能否利用初等数学的视察法，求出它的最优解

（3）某工地需要30套三角架，其结构尺寸如图4-1所示。仓库现有长6.5米的钢材。如何下料，使消耗的钢材最少

3 3 图4-1

（4）用图解法求下列线性规划的最优解：

(1) min z4x16x2 x12x21 4x3x1.5 12 x12x24x1,x20(3) max z6x19x2 2x13x22x x12  4x15x2 x2x1,x20

（5） 把下列线性规划化为标准形式：

(2) max z4x14x2 2x13x210x x512  x12x28x1,x20

22406

(4) max zx13x24x13x212  x x112x,x012(1) min zx12x2x3x3x41 x1 2x xx 2 123 3x1 x2x3x41x10,x2,x30x4无约束

(2) max z2x13x2x12x28x x 1 12  2x1 x10,x2无约束（6） 求出下列线性规划的所有基本解，并指出其中的基可行解和最优解。

max z3x15x2 x3 48x1  2x2 x4 12   x5183x1 2x2 xj0, j1,,5

（7） 求下列线性规划的解： （1）

（2）

max z3x15x2

82x1  x2 6  3x1 2x218x1,x20

max z2x14x2

 x12x2 4 x1x2 1x,x012

（3） （4）

max z2x1x2

max z2x1x2x3

x12x22  x1x21x,x0123x1x2x360xx2x10 123 x1x2x320x10,x20,x30

（8） 利用大M法或两阶段法求解下列线性规划： （1）

（2）

max z3x12x2

max z2x1x2x3

x12x27xx12 1x1x22x1,x20

3x12x2x3182xx 4 12 x1x2x35x1,x2,x30（3） （4）

max zx1x2

4x13x2123xx 6 2 1x2 2 x1,x20min zx13x24x33x4

3x16x2x32x415  6x13x22x3x412x,x,x,x01234（9） 对于问题

max zCXAXb X0*（1）设最优解为X，当C改为C时，最优解为X，则(CC)(XX)0。

*

（2）如果X1，X2均为最优解，则对于α∈[0，1]，αX1+（1－α）X2均为最优解。

(10). 表4-2是一个求极大值线性规划的单纯形表，其中x4，x5，x6是松弛变量。 表4-2

cj CB XB b 2 1 4 2 2 x1 x2 x3 1 x4 2 1 -1 -1 x5 x6 -1 x5 2 x2 x1 σj -1 2a -2 -a+8 （1）把表中缺少的项目填上适当的数或式子。 （2）要使上表成为最优表，a应满足什么条件 （3）何时有无穷多最优解 （4）何时无最优解 （5）何时应以x3替换x1

(11) 已知某线性规划的初始单纯形表和最终单纯形表如表4-3，请把表中空白处的数字填上，并指出最优基B及B。

表4-3

－1

cj CB 0 0 0 2 -1 1 0 0 0 XB b x1 3 x2 1 -1 1 -1 x3 1 2 -1 1 x4 1 0 0 0 x5 0 1 0 0 -1 x6 0 0 1 0 -2 1/2 1/2 x4 x5 x6 σj 1 1 2 0 2 -1 x4 x1 x2 σj 10 15 5 1/2 -1/2 (12). 某个线性规划的最终表是表4-4 表4-4

cj CB 0 1 -2 0 1 -2 0 0 XB b 13/2 5/2 1/2 x1 1 0 0 0 x2 0 1 0 0 x3 0 0 1 0 x4 -1/2 -1/2 -1/2 -1/2 x5 5/2 3/2 1/2 -1/2 x1 x2 x3 σj 初始基变量是x1，x4，x5。 （1）求最优基B=（P1，P2，P3）； （2）求初始表。

(13). 写出下列线性规划的对偶问题：

(1) max z3x1x2x3x12x2x34x2x4x1 123 x1x23x31x10,x20,x3无约束(2) min z2x1x23x3x4x12x2x3x44xx2x 2 123 x32x412x1 x10,x20,x3,x4无约束(3) max zcjxjj1nnaijxjbi,i1,2,,m1j1naijxjbi,im11,,m2 j1n axb,im1,,mijji2j1xj0,j1,,n1xj无约束,jn11,,n2x0,jn1,,n2j(4) min zcijxiji1j1mnni1,,mxijai j1 m xijbj j1,,ni1xij0i1,,m j1,,n(14) 已知线性规划

min zc1x1c2x2c3x3a11x1a12x2a13x3b1  a21x1a22x2a23x3b2x,x,x0123（1）写出它的对偶问题；

（2）引入松弛变量，化为标准形式，再写出对偶问题； （3）引入人工变量，把问题化为等价模型：

max zc1x1c2x2c3x3M(x6x7)b1a11x1a12x2a13x3x4 x6  a21x1a22x2a23x3 x5 x7b2x,,x071再写出它的对偶问题。

试说明上面三个对偶问题是完全一致的。由此，可以得出什么样的一般结论 (15) 利用对偶理论说明下列线性规划无最优解：

max zx12x2x3x1x2x34  2x1x22x33x0,x0,x0231(16). 已知表4-5是某线性规划的最优表，其中x4，x5为松弛变量，两个约束条件

为≤型。

表4-5

cj CB XB b 5/2 3/2 x1 0 1 0 x2 1/2 -1/2 -4 x3 1 0 0 x4 1/2 -1/6 -4 x5 0 1/3 -2 x3 x1 σj （1）求价值系数cj和原线性规划； （2）写出原问题的对偶问题； （3）由表4-5求对偶最优解。 (17) 已知线性规划问题

min z8x16x23x36x4x12x2 x433x1x2x3x46  x3x42x x3 21xj0,j1,2,3,4（1）写出对偶问题；

（2）已知原问题的最优解为X=（1，1，2，0），求对偶问题的最优解。 (18) 已知线性规划

*

Tmax zx14x23x32x13x25x323xx6x1 123 x1x2x34x1,x20,x3无约束的最优解为X=（0，0，4）。 （1）写出对偶问题； （2）求对偶问题最优解。

(19) 设线性规划问题

*Tmax zcjxjj1n naxb i1,2,,miijjj1x0, j1,2,,nj种资源的影子价格为y1，y2，…，ym。

*

*

*

（1） 的m线性规划

max zcjxjj1nn0a1jxjb1 j1 ni2,,maijxjbi j1x0, j1,2,,nj （2）

与（1）是等价的，两者有相同的最优解，请说明（2.）的m种资源的影子价格为（y1/

*

λ，y2，…，ym），并指出这一结果的经济意义。

*

*

(20). 已知线性规划

min z12x18x2x32x42x12x2x3x43 3x1x2x32x44x,x0,x,x03412（1）写出对偶问题，用图解法求最优解；

（2）利用对偶原理求原问题最优解。 (21) 线性规划

max z2x1x2x3x1x2x36 x12x24x,x,x0123的最优单纯形表如表4-6所示。 表4-6

cj CB 2 0 2 -1 1 0 0 XB b 6 10 x1 1 0 0 x2 1 3 -3 x3 1 1 -1 x4 1 1 -2 x5 0 1 0 x1 x5 σj （1）x2的系数c2在何范围内变化，最优解不变若c2=3，求新的最优解； （2）b1在何范围内变化，最优基不变如b1=3，求新的最优解； （3）增加新约束 －x1+2x3≥2，求新的最优解；

1（4）增加新变量x6，其系数列向量P6=2，价值系数c6=1，求新的最优解。

(22) 某厂生产甲、乙、丙三种产品，有关资料如表4-7所示。 表4-7 消 耗 定 原 料 额 产 品 甲 乙 丙 原料数量 A B 产品价格 6 3 4 3 4 1 5 5 5 45 30 （1）建立使总产值最大的线性规划模型； （2）求最优解，并指出原料A，B的影子价格； （3）产品甲的价格在什么范围内变化，最优解不变

（4）若有一种新产品，其原料消耗定额为：A为3单位，B为2单位，价格为单位，求新的最优计划。；

（5）已知原料B的市场价为单位，可以随时购买，而原料A市场无货。问该厂是否应购买B，购进多少为宜新的最优计划是什么

（6）由于某种原因，该厂决定暂停甲产品的生产，试重新制定最优生产计划。 (23) 分析下列参数规划中，当t变化时，最优解的变化情况。

(1) max z(32t)x1(5t)x2 4x1  2x212 3x12x218x1,x20

(24)用分支定界法求解下列整数规划问题

(2) max z2x1x25x2 15 6x2x24t 2 1 x1x2 5x1,x20（1）maxzx1x2 （2）maxz2x13x2

951xx1142145x17x2351 4x19x230 2x1x23x,x0且为整数12x1,x20且为整数(25)用割平面法求解下列整数规划问题

（1）maxz4x16x22x3 （2）maxz11x14x2

54x14x21x12x24x6x5x2x1651122  xxx52xx432121x1,x20且为整数x1,x2,x30且为整数

(26)用隐枚举法解下列0–1规划问题

（1）maxz3x12x25x32x43x5 （2）maxz2x1x25x33x44x5

x1x2x32x4x543x12x27x35x44x567x3x4x3x83451 x1x22x34x42x50 3x43x53x0或1j=1,2L511x16x2jxj0或1j=1,2L5

(27)用匈牙利法求解下列指派问题，已知效率矩阵分别如下：

387910128713121617  151614158411121516910

2103297275

2356910(28)已知下列五名运动员各种泳姿的运动成绩（各为50米）如表4-8所示，请问如何从中选择一个参加200米混合泳的接力队，使预期比赛成绩最好。

表4-8 仰 泳 蛙 泳 蝶 泳 自由泳 赵 钱 张 单位：秒 王 周 (29)分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表4-9

所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。

表4-9 人 任务 甲 乙 丙 丁 A 25 39 34 24 B 29 38 27 42 C 31 26 28 36 D 42 20 40 23 E 37 33 32 45 (30) 从甲、乙、丙、丁、戊五个人中挑选四人完成四项工作。已知每人完成各项工作的时间如表4-10所示。规定每项工作只能由一个人单独去完成，每个人最多承担一项任务。又假定对甲必须保证分配一项任务，丁因某种原因决定不同意承担第4项任务，在满足上述条件下，如何分配工作，使完成四项工作总的花费时间最少。

表4–10 工作 人 1 2 3 4 甲 乙 丙 丁 戊 10 5 15 20 2 10 5 15

3 15 14 13 15 2 7 6 9 4 15 8 (31) 求下列网络图从起点到终点的最短路线及长度。 （1）

60 70

10 40

30

C2 30

40

20 A

40 30 30 B2 20 10 40 10 60 D1 E 30 D2 B3 50 C3 30 10 12

E1 （2）

3 8 7 3 4 F1 13 G1 9 5 10 10 B A E2 2 4 8 F2 7 6 5 G2 15 8 C 7 E3 6 F3 8 G3 7 D (32). 用破圈法和避圈法求下图的最小生成树

V2 12 11 9 V1

V4 21

（33）求下列各图的最小生成树

４ ３ ２ ２ ５ ４ ６

（1）

（2）

２ １

９ ４ ３

３ １ ２ ４ ５ ５ ６ ３ ８ ７ ３ ２ 1 １ V5

13 16

V3 5 19 7

7 11

10

V7

7 8 4 V9

V6

V8

（34）写出下面各图中的顶点数、边数及顶点的次数，哪些是简单图。

V6

V5 V1

V V2

V2

V1 V3

V5 V3 (1)

(2)

V4

（35）用标号法求图4—2中从v1到各顶点的最短距离

V2 2 V1

3 6 5 V3 7 5 2 3 1 V6 3

4 V5 2 1 4 3 V8 6 V9 3

7 4 8 V11

V4 1 V10 ,已知1号村镇离水源最近，7 V7 （36）已知8个村镇，相互间距离如下表所示为5公里，问从水源经1号村镇铺设输水管道将各村镇连接起来，应如何铺设使输水管道最短（为图4—2 便于管理和维修，水管要求在各村镇处分开）。

各村镇间距离 （单位：千米） 到 2 从 1 2 3 4 5 6 7 8 3 4 5 6 7

(37)用标号法求下面网络的最大流. V 1 V1

2 4 5 4 3 4 图4——3

5 3 3 3 2 5 Vt

8 4

10 15 8

6 8

图4——3 12

14

10 9

12 10

18 13 8

15

6 Vt

(38)求下列网络的最小费用最大流.括号内的两个数字,前一个是单位流量的费用,后一个是该弧的流量.

(6,6) V1 (5,1) (10,5(7,4) (2,3) (8,2) Vt

V1

(9,2) (5,6) (3,2)

(3,4)

(4,1)

(4,19

(1,1)

（2）

(39)求解图4—5中所示的中国邮递员问题（A点是邮局所在地）

3 2 4 A

2 2 2 2 4 4

2

3 5 5 2 2 3 2 4

图4—5

(40)如图4—6，发点S1，S2分别可供应10和15个单位，收点T1和T2可接收10个和25个单位，求最大流，边上的数为cij。

3 S1

2 2 4 3 S2

6 4 T2

8 6 v1 7 T1

v2 图4——6

(41) 指出图4—7中所示网络图的错误，若能够改正，试予以改正。

2 d e d 55 a 1 2 b 3 f 6 a c 1 b c a 4 1 3 2 e （a） 6 g 8 f d 3 e 7 f （b） 5 b c

g 4 （c） 图4—7

(42) 根据表4—11表4—12，所示的作业明细表，绘制网络图。 表4—11 表4——12 工序 紧前工序 － － －

工序 紧前工序 － － a b c d e f g h a b c d e f g h a a a , b c c d , e , f a c d d , b f ,g ,e (43) 已知图4—8所示的网络图，计算各事项的最早与最迟时间。

a 4 2 c 3 1 b 4 3 d 5 4 10 e 3 5 g 6 6 f 图4—8

(44) 试画出表4—13、表4—14的网络图，并为事项编号。

表4—13

工序 工时（d） 紧前工序 工序 工时（d） A B C D E

表4—14 工序 A B C D E F 工时（d） 紧前工序 3 2 5 4 7 8 － － － A B C 工序 G H I J K L 工时（d） 紧前工序 6 2 4 5 2 6 D，B E G，H E，F E，F I，J 15 10 10 10 5 － － A，B A，B B F G H I 5 20 10 15 紧前工序 D，E C，F D，E G，H (45) 已知表4—15所列资料

工序时工序 紧前工序 间（周） A B C D — — A L 3 4 4 3 E F G H B H C，B G，M 工序 紧前工序 间（周） 4 5 2 2 I K L M H，L F，I，E B，C B 工序时工序 紧前工序 间（周） 2 6 7 6 工序时要求：（1）绘制网络图；

（2）计算各工序的最早开工、最早完工、最迟开工、最迟完工时间及总时差，并指出关键工序。

（3）若要求工程完工时间缩短2天，缩短哪些工序时间为宜。

（46） 设有如图4—9的网络图，计算时间参数，并求出关键路线。 18 20 5 8 2 15 14 10 10 6 5 11 25 12 18 6 11 9 1 3 15 15 7 25 19 10 7 10 4

图4—9

(

47）如图4—10所示的网络图，计算各事项的最早时间和最迟时间，各工序的最早开始、最早结束、最迟开始及最迟结束时间，计算各工序的总时差和单时差，找出关键路线。

3 1 8 4 3 2 7 4 2 3 5 7 7 5 9

（48）某项工程各工序的工序时间及所需人数如表4—15所示，现有人数为10人，试确定工程完工时间最短的各工序的进度计划。

表4—15 工序代号 A B C D E F G H 紧前工序 — — — — B C F，D E，G 工序时间（天） 4 2 2 2 3 2 3 4 需要人员数 9 3 6 4 8 7 2 1 （49）已知下列网络图有关数据如表4—16，设间接费用为15元／天，求最低成本日程。

表4—16

正常时间 工序代号 工时（天） 费用（元） 工时（天） 费用（元） 特急时间 ①→② ②→③ ②→④ ③→④ ③→⑤ ④→⑥ ④→⑦ ⑤→⑧ ⑥→⑧ ⑦→⑧ 6 9 3 0 7 8 2 1 4 5 100 200 80 0 150 250 120 100 180 130 4 5 2 0 5 3 1 1 3 2 120 280 110 0 180 375 170 100 200 220 （50）生产某种产品，生产过程所经过的工序及作业时间如表4—17所示，作业时间按常数和均值计算，试绘制这一问题的随机网络图，并假设生产过程经过工序G 即为正品，试计算产品的成品率与产品完成的平均时间。

表4—17 工序 A B C D E F G

概率 1 1 1 作业时间（常数或期望值）（h） 25 6 4 3 4 6 2 紧后工序 B或F C或D G E C G —