运筹学试题库

一、多项选择题

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

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

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

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

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

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

(8）大M法与两阶段法的要点是什么?两者有什么共同点?有什么区别？ (9）松弛变量与人工变量有什么区别?试从定义和处理方式两方面分析。

（10）如何判定线性规划有唯一最优解，无穷多最优解和无最优解？为什么?

－

（11）如何在以B为基的单纯形表中，找出B1?该表是怎样由初始表得到的？ （12）对偶问题的构成要素之间，有哪些对应规律? （13）如何从原问题最优表中，直接找到对偶最优解? （14）叙述互补松弛定理及其经济意义。

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

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

三、模型建立题

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

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

(2）某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻井费用最小。若10个井位的代号为s1,s2,s3选择上要满足下列条件:

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

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

2

s10，相应的钻井费用为c1,c2,,c10，并且井位

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

四、计算及分析应用题

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

表4-1

合金品种 含铅％ 含锌% 含锡％ 单价(元/kg） 1 30 60 10 8.5 2 10 20 70 6。0 3 50 20 30 8.9 4 10 10 80 5.7 5 50 10 40 8。8 如何安排配方,使成本最低?

(2）某医院每天各时间段至少需要配备护理人员数量见表4—2 表4-2 班次 1 时间 6：00－10:00 最少人数 60 3

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

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

3 1.7 3

1.4 1.4

图4-1

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

(1) min z4x16x2(2) max z4x14x2 x12x21 2x13x210  4x13x21.5x1 x25

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

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

4

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

（6） 求出下列线性规划的所有基本解，并指出其中的基可行解和最优解。max z3x15x2x1 x3 48  2x2 x4 12 3x1 2x2 x518xj0, j1,,5

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

（2）

max z3x15x2max z2x14x22x1 8 x12x2 4  x2 6 3xx

1x2 11 2x218xx1,x201,x20（3)

（4）

max z2xx1x2x31xmax z22x23x1x2x36012x2 xxx1x22x310 121 x1,xx1x2x32020x10,x20,x30

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

5

max z3x12x2max z2x1x2x3x12x27xx12 1x1x22x1,x20（3）

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

（4)

max zx1x24x13x2123x16x2x32x4153xx 6 12  6x13x22x3x412 x 22x,x,x,x01234x1,x20（9） 对于问题

min zx13x24x33x4max 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 2 XB b 2 1 4 2 2 x1 x2 x3 1 —1 2a x4 2 1 —1 -1 x5 x6 —1 -2 -a+8 x5 x2 x1 σj （1）把表中缺少的项目填上适当的数或式子. (2)要使上表成为最优表，a应满足什么条件？ （3)何时有无穷多最优解? （4）何时无最优解？

（5）何时应以x3替换x1？

(11) 已知某线性规划的初始单纯形表和最终单纯形表如表4—3，请把表中空白处的

－

数字填上，并指出最优基B及B1。

6

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

表4-4

cj CB 0 1 -2 XB b 13/2 5/2 1/2 0 1 -2 0 0 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无约束

7

n(3) max zcjxjj1naijxjbi,i1,2,,m1j1naijxjbi,im11,,m2j1 naijxjbi,im21,,mj1xj0,j1,,n1xj无约束,jn11,,n2xj0,jn21,,nmn(4) min zcijxiji1j1nxijai i1,,m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b 1a 21x1a22x2a23x3b2x1,x2,x30(1）写出它的对偶问题;

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

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

8

试说明上面三个对偶问题是完全一致的。由此，可以得出什么样的一般结论？ （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）T，求对偶问题的最优解。 （18） 已知线性规划

max 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)T。

9

（1）写出对偶问题； （2）求对偶问题最优解。

(19) 设线性规划问题

max zcjxjj1n（1） naxb i1,2,,miijjj1x0, j1,2,,nj为y1*，y2*,…，ym*。

线性规划

n的m种资源的影子价格

max zcjxjj1n0a1jxjb1 j1（2） ni2,,maijxjbi j1x0, j1,2,,nj与（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

10

的最优单纯形表如表4—6所示。

表4—6 cj CB 2 0 XB b 6 10 2 —1 1 0 0 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，求新的最优解； (4)增加新变量x6，其系数列向量P6=1，价值系数c6=1，求新的最优解。 2（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单位，价格为2.5单位，求新的最优计划。;

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

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

11

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

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

（1）maxzx1x2 （2）maxz2x13x2

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

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

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

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

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

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

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

12

7910121312161715161415111215163887849102103297275

2356910

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

表4-8 单位:秒

仰 泳 蛙 泳 蝶 泳 自由泳 赵 钱 张 王 周 37.7 43。4 33。3 29。2 32。9 33。1 28.5 26。4 33.8 42.2 38。9 29.6 37.0 34.7 30.4 28。5 35.4 41.8 33。6 31。1 （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） 求下列网络图从起点到终点的最短路线及长度。

13

70

B1 40 C1 10 20 60 40 （1） 30 D1 30 A 40 B60 2 20 C2 30

30 10 40 30 D40

B3 10 2 C3 50 30 E1 4 10 F1 G1 9 B 3 3 12 10 （2） 2 13 5

A 8 E2 8 F5 10 2 G2 C 7 4 7 15 7 6 8 E3 F

6 3 8 G3 7 D （32）。用破圈法和避圈法求下图的最小生成树

V2 13 V3

5

12 11 16 19 7 V6 9 V4 7 V1

11 V8 8 21 V5

10 4

V7 7 V9

(33)求下列各图的最小生成树 ４ ５ ３ ３ ２ １ ９ ６ １８ ２ 1 ３

５ ４ ２ ７ １ ２ ４ ２ ３

４ ５ ３

６ （1）

（2）

E 14

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

V1

V6 V4 V5 V2

V2 V1 V3

V5 V3 (1)

(2)

V4 v到各顶点的最短距离 （35)用标号法求图4—2中从1

V2 2 V1

3 6 5 V3 7 5 2 V5 2 1 3 1 V6 4

4 3 V8 6 V9 7 3 4 8 V11

3 （36）已知8个村镇，相互间距离如下表所示,已知1号村镇离水源最近，为5公里，

V4 7 V10 V7 1

问从水源经1号村镇铺设输水管道将各村镇连接起来，应如何铺设使输水管道最短（为便于管理和维修,水管要求在各村镇处分开）.

图4—2

各村镇间距离 （单位：千米） 到 从 1 2 3 4 5 6 7 2 3 4 5 2.0 6 7 8 1.5 2。5 1.0 2.5 3。5 1。5 1.8 1.0 1.0 2。0 1.0 3。0 2.5 2.5 2。0 2。5 2.0 2。5 1.5 1.5 1。0 0。8 1.0 0.5 3.0 1。8 1.5

（37)用标号法求下面网络的最大流.

4

8 9 10 12 13 15

10 V1

15 10 15 6 Vt

2

8 3 3 4 Vt 5 2 V1 3

3 5 5 4

4 图4——3

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

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

(4,19) (8,2) (9,2) (10,5)

(2,3)

(1)

（2）

图4——4

(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

(1,1) Vt

16

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

2 2 T1 4 6 3 4 S2

T2

6 8 v2

图4——6

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

2

d a e 2

1 b d 5 5 f 6

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

1 b 3 f 5 （b）

c g 4

（c）

图4—7

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

17

a b c d e f g h － － － a c d d, b f，g,e a b c d e f g h － － a a a , b c c d , e , f

（43） 已知图4-8所示的网络图，计算各事项的最早与最迟时间。 a c 2 4 3

g b d e 1 3 4 5 5 3 4 6

f 10 图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 6 紧前工序 D,E C,F D,E G,H (45) 已知表4—15所列资料 工序 紧前工序 工序时工序 紧前工序 工序时工序 紧前工序 工序时 18

间（周） 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所示的网络图，计算各事项的最早时间和最迟时间，各工序的最早开始、最早结束、最迟开始及最迟结束时间，计算各工序的总时差和单时差，找出关键路线.

7 3 2 5 7

5 2 3

8 3 4 1 4 7 9

2 1 4 7

8 3 6 图4—10

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

表4—15

工序代号

紧前工序 工序时间（天） 需要人员数 19

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 0.7 0.7 0。3 1 0。3 1 作业时间(常数或期望值)(h） 25 6 4 3 4 6 2 紧后工序 B或F C或D G E C G — 20