运筹学答题题库2020

l.minz=2再+3马+天

再+4x2+2x3>8

3国+2尤2)6

再，入2，^.

解：大M法

z'=-z有maxz'=-min(-z')=-minz

化成标准形：

z

Maxz=-2xx-3x2-+0x4+0x5

S.T.

国+4%+2玉-%+x6=4

3国+2々-毛+毛=6

xl,x2,x3,x4,毛，毛，Xy>0

(单纯性表计算略)

线性规划最优解乂=(4/5,9/5,0,0,0,0尸

目标函数最优值minz=7

非基变量七的检验数％=。，所以有无穷多最优解。

2.已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见表，试将

空白处数字填上。

354000

Cj

b

XB天

cB再%%工6

58/32/3101/300

014/3-4/305-2/310

020/35/304-2/301

-1/304-5/300

15/418/41-10/41

-6/415/414/41

%3

-2/41-12/4115/41

X]

Cj-Zj

解:

354000

%

b

XBX]x

cB2%%

58/3

x2

014/3

%

020/3

%

Ci%

580/4101015/41

X?

450/41001-6/41

x3

344/41100-2/41

王

000-45/41

CjYj

3.已知线性规划问题

Maxz=2再+%+5犬3+6x4

s.t.2再+毛+/<8

2七+2%+七+2/412

>0,j=l,...4

对偶变量X，%，其对偶问题的最优解是y；=4,y；=l,试应用对偶问题

的性质，求原问题的最优解。

解：

对偶问题是：

Minw=8y+12%

s-t.2yx+2y2>2

2>1

X+%25

X+2%*

%，-o

互补松弛性可知，如文，户是原问题和对偶问题的可行解，那么，YXs=0

和

公文=0,当且仅当父，另是最优解。

设X,丫是原问题和对偶问题的可行解，松=(%，%，％，%)

有：

YXs=0;且与X=0

x5=x6=0,原问题约束条件取等号，X3=4；X4=4

最优解x=(0,0,4,4)「

目标函数最优值为44o

4.试用对偶单纯形法求解下列线性规划问题。

(1)minz=再+x2

2再+九2"

xl+7x2>7

x1,x2>0

(2)minz=3再+2x2+七+4%

2+4x2+5+x4>0

3%-9+7毛-2%>2

5X1+2X2+X3+10X4>15

再，%2，％3，X420

解：

(1)

w=-z,标准形式：

Maxw=-x1-x2+0x3+0x4

s.t.

-2再-9+玉二-4

-西-7x2+x4=-7

再，x2,x3,x4>0

单纯形法求解(略)：

最优解：

X=(21/13,10/13,0,Of

目标函数最优值为31/13。

(2)令：w=-z,转化为标准形式：

Maxw=-3再-2%2-毛-4%4+0%5+0x6+0毛

s.t.

-2-4%2-5%3-九4+毛二0

-3再+%-7毛+2%+%=-2

-5再-2%2-%3-6%4+%7=-15

西，x2,x3,x49x5,x69x7>0

单纯形法略

原问题最优解：

X=(3,0,0,0,6,7,0)r

目标函数最优值为9。

5.（2006年西北工业大学）已知线性规划：

maxz=3芯+2x2

一玉+2X2<4

3%+2々V12

s.t.<

玉一%2V3

x^x2>0

（1）用单纯形法求解该线性规划问题的最优解和最优值；

（2）写出线性规划的对偶问题；

（3）求解对偶问题的最优解和最优值。

解题分析：本题考察了线性规划与对偶问题的知识，要求读者熟知对偶理论。

-17

解题过程：%*=---00

_555_

maxz=12,有无穷多解。

对偶问题为：

minw=4yl+12y2+3y3

f+3%+为»3

s.t.<2%+2y2-%22

,%，%，%20

r=[010]w=z*=12

6.用表上作业法求给出运输问题的最优解（M是任意大正数）

（1）

肖地甲乙丙T产量

产地

137645

224322

343853

销量3322

解：

（1）①计算出各行和各列的次最小运费和最小运费的差额，填入该表的最

右列和最下列。

②从行差额或者列差额中找出最大的，选择它所在的行或者列中的最

小元素，丙列中的最小元素为3,由此可以确定产地2的产品应先供应丙的需要，

而产地2的产量等于丙地的销量，故在（2,丙）处填入0,同时将运价表中的

丙列和第二行的数字划去，得到：

肖地甲乙丙T产量

产地

13745

22

34353

销量332

③对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额,

填入该标的最右列和最下行，重复步骤①②，直到求出初始解为止。得到下表:

肖地甲乙丙T产量

产地

1325

2202

3033

销量3322

使用位势法进行检验：

①上表中，数字格处填入单位运价并增加一行一列，在列中填入%（i=l,

2,3）,在行中填入,（j=l,2,3,4）,先令%+匕=与（i,jeB,B为基，下

同）来确定附和匕，得到下表:

肖地甲乙丙T

Uj

产地

1340

232-2

3431

3254

匕

②由0=%-（%+匕）（i,j为非基，下同）计算所有空格的检验数，并在

yJ

每个格的右上角填入单位运价，得到下表

肖地甲乙丙T

产地

137640

0510

22432-2

1400

343851

0020

3254

匕

由上表可以看出,所有的非基变量检验数NO,J比问题达到最4忧解。

又因为%4=0，此问题有无穷多最优解。

总运费minz=3*3+3*3+2*3+2*4=32

(2)

肖地甲乙丙T产量

产地

11067124

21610599

35410104

销量5246

解：（2）①计算出各行和各列的次最小运费和最小运费的差额，填入该表

的最右列和最下列。

②从行差额或者列差额中找出最大的，选择它所在的行或者列中的最

小元素，甲列是最大差额列，甲列的最小元素是5,所以产地3的产品先供应甲

的需求，同时将运价表中产地3所在行的数字划去。

③对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额,

填入该标的最右列和最下行，重复步骤①②，直到求出初始解为止。得到下表:

肖地甲乙丙T产量

产地

11214

2369

344

销量5246

使用位势法进行检验：

①上表中，数字格处填入单位运价，并增加一行一列，在列中填入对（i=l,

2,3）,在行中填入,（j=l,2,3,4）,先令%=0,由%+匕=与（i,jeB,B

为基，下同）来确定“，和匕.

②由%=%-（%+匕）（i,jeN）计算所有空格的检验数，并在每个格的右

上角填入单位运价，得到一;表

肖地甲乙丙T

产地

11067120

01

2161059-2

8600

3541010-5

0384

106711

匕

由上表可以看出，所有的非基变量检验数三0,J比问题达到最《尤解。

此问题有唯一最优解。

总运费minz=118

(3)

7肖地甲乙丙T戊产量

产证、

1102059105

221083066

312071042

4863759

销量44624

解：（3）此问题是一个产销不平衡的问题，产大于销。增加一个假象销售

地己，令单位运价为0。销量为2。这样就达到了产销平衡。

用伏格尔法求初始解：

①计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列

和最下列。

②从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元

素，产地1所在的行是最大差额行，最小元素0,说以一产地的产品应该优先供

应己的需要，同时划掉己列的数字。

③对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额,

填入该标的最右列和最下行，重复步骤①②，直到求出初始解为止。得到下表:

7肖地甲乙丙T戊己产量

产证、

1325

2426

322

44329

销量446242

使用位势法进行检验：

①上表中，数字格处填入单位运价，并增加一行一列，在列中填入"，（i=l,

2,3,4）,在行中填入匕（j=l,2,3,4,5,6）,先令％=0,由"，+匕』（i,

jeB,B为基,下同）来确定/和匕.

②由4=%-（%+匕）（i,jeN）计算所有空格的检验数，并在每个格的右

上角填入单位运价。

由上表可以看出，所有的非基变量检验数三0,此问题达到最优解。

又因为巧4=。，此问题有无穷多最优解。

总运费minz=90

7.使用单纯形法求解下列目标规划问题。

(1)minz=P]d~+P2d；+月(54+3d；)+《d：

s.t.

国+%+4-d：=80

西+&+d；-d；=90

%+4■-d；=70

/+-d：—45

,*^2'd、，d]，d2，d?，,d42。

(2)minz=Pxd；+P、d；

s.t.再+2%2+4-4+=10

10再+12%2+2：-a=62.4

+2x2<8

Xj9%29d、，4,d?9d?N0

(3)minz=P1(+d；)+gd~

s.t.xx+x2~^d~-=1

2%+2冗2+d；-d；=4

6%-4%+d；-d；=50

9*^2'd、，d]9，d?，(^3，20

解：

(1)把原问题转化为：

Minz=P、d；+P、d；+旦d~

S.T.

x1+2x2+d~-=10

10%1+12%2+6?2--^2-62.4

2再+%2+%3=8

Xj,%2，%3，4，4,d-2，d?20

x3是松弛变量

单纯形法计算得：

0000

Cj2Pi64

b

XBXiX?&d~d：d~d；

cB

101[2]01-1005

d~

62.410120001-15.2

Rd~

0821100008

-10-1200002

旦-1-200100

迭代…

原问题最优解西=0,々=5.2,非基变量的的检验数是0,所以有多重解;

继续迭代得到：

%!=0.6,%=4.7也是满意解

(2)

使用单纯形法计算：

%!=70,=20

(3)满意解是

%1=1,^=0

8.有四个工人，指派他们完成4种工作，每人做各种工作所消耗的时间如下表,

问指派哪个人去完成哪种工作，可以使得总耗时最小？

壬务ABCD

人员

甲15182124

乙19232218

丙26171619

T19212317

解：系数矩阵C为:

15182124

19232218

26172619

19212317

①系数矩阵的每行元素减去该行的最小元素得矩阵B

②B矩阵的每列元素减去该列的最小元素得到矩阵A

此时，细数矩阵的每行每列都有元素0.

先给勺加圈，然后给如加圈，划掉%4。给?2加圈，划掉?3得：

'0269一

1440

10003

_2360

此时，画圈的数目是3,少于4个，所以指派不成功，进入下一步，

给第四行打J号，给第四列打J号，给第二行打J号，将第一，第三行画一横线，

将第四列画纵线，变换矩阵得到

'02610-

0330

10004

1250

给第一，第四列打J号，对第一，第二，第四行打J号，给第一，第四列画一纵

线，第三行画一横线，变换矩阵得到

甲乙丙丁

'00410-

0111

12006

1030

得到最优指派方案为：甲一B；乙一A;丙一C；T—Do

所消耗的总时间是70.

9.（2005年南京大学）现要在5个工人中确定4个人来分别完成四项工作中的

一项工作。由于每个工人的技术特长不同，他们完成各项工作所需的工时也

不同。每个工人完成每项工作所需工时如表5—1所示。

表5—1

所需工0?\］作

ABcD

I9437

II4656

III5475

IV7523

V10674

试找出一个工作分配方案，使总工时最少。

解题分析：本题属“不平衡”指派问题，故应先虚拟一项工作，使其平衡，再按

常规求解即可。

解题过程：虚拟一项工作E,设每人完成E所需时间都是“0”，从而转化为五个

人完成五项工作的分配问题，再用匈牙利法求解。

最优解为：I—C,II—A,III—B,IV—D,V—E,即应安排工人I、

n、ni、W分别完成工作C、A、B、D,此时所用时间最少，为3+4+4+3=14。

10解：已知线性规划

maxZ=3再+4x2+5x3

玉+2X2-X3<10

<2玉一%+3%3-5

Xj>0,7=1,2,3

（1）求原问题和对偶问题的最优解；（2）求最优解不变时C/的变化范围

（1）化标准型2分

maxZ=3芯+4x2+5x3

xl+2X2-x3+x4=10

<2再-x2+3X3+x5=5

Xj>Q,j=1,2,,5

（2）单纯形法5分

CBXB为莅吊羽怎b

4苞1100.60.27

5吊1010.20.44

C(j)-Z(j)-600-3.4-2.848

(3)最优解X=(0,7,4)；Z=48(2分)

(4)对偶问题的最优解丫=(3.4,2.8)(2分)

qe(—oo,9),c,>——,c3>—1

3

(5)Aci<6,AC2>-17/2,AC3>-6,贝!](4分)

11.求下列指派问题（min）的最优解（10分）

5685

12152018

C=

91097

9656

解:

01300030

03860286

=>

23202220

41014001（5分）

1

X=,Z=30

1

1

（5分）

12.求下图VI到V8的最短路及最短路长（10分）

vl到v8的最短路有两条：尸18={vl,v3,v6,”8}及P18={vl,v3,v7,v6,v8},最短路长为21。（3分）

13.某公司要将一批货从三个产地运到四个销地，有关数据如下表所示。

供

销地应

BB

Bi2B34量

产地

56

A17379

0

40

A226511

0

75

A36425

0

32244838

需求量

0000

现要求制定调运计划，且依次满足：

(1)B3的供应量不低于需要量；

(2)其余销地的供应量不低于85%；

(3)A3给B3的供应量不低于200；

(4)A?尽可能少给Bi；

(5)销地B2、B3的供应量尽可能保持平衡。

(6)使总运费最小。

试建立该问题的目标规划数学模型。

13.设殉为A,•到B/的运量，数学模型为

minz=《4+£(&+4+〃4)+g"5+g",+月("7+。；)+纭。；

再3+々3+*33+4——480员保证供应

再］+%2i+%31+d?-d；—2744需求的85%

Xj2+%22+”32+4-d；—204为需求的85%

%14+X24+%34+Z—d；=323息需求的85%

X33+4_d；—200人1寸员

s.t.<%21-逋=。4对与

2X11+2%21+2%31—%12—*22—*32+"7—=0为与员的平衡

34

ZX-公=。运费最小

i=lj=l

Xtj>0(z=1,2,3；J=1,2,3,4);

“d：>0(z=l,2,...,8);

14、用分枝定界法求解下列整数规划问题：(提示:可采用图解法)

maxZ=40xi+90x2

pXj+7x2456

s.tS7x,+20x2470

1%,X220且为整数

Xx

15、A、B两个煤矿负责供应甲、乙、丙三个城市煤炭。已知A、B两矿年产量、三个城市

的需求量以及从两煤矿至各城市煤炭运价如下表。由于供不应求，经协商，甲城市必要时可

少供应0—30万吨，乙城市需求须全部满足，丙城市需求不少于270万吨。试求：将甲、乙

两矿煤炭全部分配出去，满足上述条件又使总运费最低的调运方案。(15分)

7^甲乙丙产量

A151822400

B212516450

销量(T)320250350

解：(1)依题意得产销平衡表如下：

甲，甲”乙丙，丙”产量

A1515182222400

B2121251616450

CM0MM070

销量(T)2903025027080

(2)做初始的调运方案(伏格尔法)

产甲，甲，，乙丙，丙”产量

销

A1515182222400

150250

B2121251616450

1403027010

CM0MM070

70

销量(T)2903025027080

(3)用位势法进行检验

产甲，甲”乙丙，丙”U

销

A1515182222

0001212-6

B2121251616

001000

CM0MM0

M-5-5M-80-16

V2121241616

(4)做闭回路调整

调整后为：

产甲，甲”乙丙，丙”产量

销

A1515182222400

150250

B2121251616450

14027040

CM0MM070

3040

销量(T)2903025027080

(5)进行进一步检验

产甲，甲”乙丙，丙”U

销

A1515182222

0001212-6

B2121251616

051000

CM0MM0

M-50M-8M0-16

V2116241616

(6)调整后的方案为最优方案

最低费用=150X15+250X18+140X21+270X16+40X16+30X0+40X0=14650

16、分配甲、乙、丙、丁四人去完成5项任务。每人完成各项任务时间如下表所示。由于任

务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项，试确定总花

费时间最少的指派方案。（15分）

ABCDE

甲2529314237

乙3938262033

丙3427284032

T2442362345

解：假设增加一个人戊完成各项工作的时间取A、B、C、D、E最小值。

得效率矩阵为：

ABCDE

甲「2529314237

乙3938262033

丙3427284032

T2442362345

戊2427262032

各行减最小值，各列减最小值：得

ABCDE

_4_5_J7_7

乙19185)8

两力~0~~1丁中

T11912317

戊475力7

变换得

ABCDE

甲「（45187

乙1317407

西-(T飞~14^

Tq1811J16

戊2646

进一步

ABCDE

甲「001183

乙1813003

丙1100180

T0147012

戊32002

最有指派方案

ABCDE

甲「01000

乙00010

丙00001

T10000

戊00100

甲——B,乙——C,D,丙——E,T——A

最低费用=29+26+20+32+24=131

17.石油输送管道铺设最优方案的选择问题：如图所示，其中A为出发点，E为

目的地，B、C、D分别为三个必须建立油泵加压站的地区，其中的Bi、B2、B3；。、

C2、C3Q1、D2分别为可供选择的各站站点。图中的线段表示管道可铺设的位置，

线段旁的数字为铺设管线所需要的费用，问如何铺设管道才使总费用最小？

解：

第四阶段：Di—E3；D2—E4；

第三阶段:Ci—Di一E5；C2—D2—E8；Cs—Di一E8；Cs—D2一E8；

第二阶段：Bi—Ci一Di一E11；Bi-C2—D2—E11；B2—Ci一Di一E8；

Bs—Ci—Di—E9；Bs—C2—D2—E9；

第一阶段：A—Bi—Ci—Di—E14；A—Bi—C2—D2—E14；

A—B2—Ci—Di—E13；A—B3—Ci—Di—E13；

A—B3—C2—D2—E13；

最优解：A—Bs-Ci-Di—E；A—Ba-Ci-Di—E；A—B3-C2—D2—E

最优值：13

18.某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如图所示,

图中V1,……，V7表示7个学院办公室，图中的边为可能联网的途径，边上的所赋权数为这

条路线的长度，单位为百米。请设计一个网络能联通7个学院办公室，并使总的线路长度为最

短。

解：①在G中找到一个圈(Vi,V7,V6,VO，并知在此圈上边[Vi,V6]的权

数10为最大，在G中去掉边[Vi,V目得图Gi,如上图所示

②在G1中找到一个圈(V3,V4,V5,V7,V3),去掉其中权数最大的边[V4,V5],

得图G2,如上图所不

③在G2中找到一个圈(V2,V3,V5,V7,V2),去掉其中权数最大的边

[Vs>V7],得图G3,如上图所不

④在G3中找到一个圈(V3,V5,V6,V7,V3),去掉其中权数最大的边

[V5,Ve]»得图G4,如上图所不

⑤在G4中找到一个圈(V2,V3,V7,V2),去掉其中权数最大的边

[V3,V7],得图Gs，如上图所不

⑥在G5中已找不到任何一个圈了，可知G5即为图G的最小生成树。

这个最小生成树的所有边的总权数为3+3+3+1+2+7=19

19.某电力公司要沿道路为8个居民点架设输电网络，连接8个居民点的道路图如图

所示，其中Vi,……，V8表示8个居民点，图中的边表示可架设输电网络的道路，

边上的赋权数为这条道路的长度，单位为公里，请设计一个输电网络，联通这8个居

民点，并使总的输电线路长度为最短。

①在图中找到一个圈(Vl,V2,V5,V3)，并知在此圈上边［Vl,V2］和

［V3,V5］的权数4为最大，在图中去掉边［V1,V2］；

②在图中找到一个圈(V3,V4,V8,V5,V3,V1),去掉其中权数最大的边

［V4,V8］；

③在图中找到一个圈(V3,V4,V5,V3),去掉其中权数最大的边［V4,V5］；

④在图中找到一个圈(V5,V2,V6,V7,V5),去掉其中权数最大的边

［V2,V6］；

⑤在图中找到一个圈(V5,V7,V8,V5),去掉其中权数最大的边［V5,V8］o

⑥在图中已找不到任何一个圈了，可知此即为图G的最小生成树。

这个最小生成树的所有边的总权数为2+2+4+2+3+3+2=18

20矩阵对策的最优纯策略

甲乙乒乓球队进行团体对抗赛，每对由三名球员组成，双方都可排成三种不同的

阵容，每一种阵容可以看成一种策略，双方各选一种策略参赛。比赛共赛三局，

规定每局胜者得1分，输者得-1分，可知三赛三胜得3分，三赛二胜得1分，三

赛一胜得-1分，三赛三负得-3分。甲队的策略集为Si={3,a2,a3},乙队的策略

集为Sl={01,彷，加},根据以往比赛得分资料，可得甲队的赢得矩阵为A,如下：

3-13

试问这次比赛各队应采用哪种阵容上场最为稳妥。

解：甲队的6,a2,a3三种策略可能带来的最少赢得，即矩阵A中每行的最小元

素分别为：1,-3,-1,

在这些最少赢得中最好的结果是1,即甲队应采取策略③，无论对手采用什么

策略，甲队至少得1分。而对乙队来说，策略国，刖，的可能带来的最少赢得，

即矩阵A中每列的最大因素(因为两人零和策甲队得分越多，就使得乙队得分越

少)，分别为：3,1,3,

其中乙队最好的结果为甲队得1分，这时乙队采取囱策略，不管甲队采用什么

策略甲队的得分不会超过1分（即乙队的失分不会超过1）。这样可知甲队应采用

ai策略，乙队应采取叫策略。把这种最优策略ai和俄分别称为局中人甲队、乙

队的最优纯策略。这种最优纯策略只有当赢得矩阵A=（aij）中等式

maxmina”=minmaxa.

ijji

成立时，局中人才有最优纯策略，并把（ai,[32）称为对策G在纯策略下的解，

又称（ai,廿2）为对策G的鞍点。

21矩阵对策的混合策略

解：首先设甲使用6的概率为Xi',使用a2的概率为X*并设在最坏的情况下

（即乙出对其最有利的策略情况下），甲的赢得的平均值等于V。这样我们建立以

下的数学关系：

1.甲使用ai的概率Xi'和使用a2的概率X2’的和为1,并知概率值具有非负性，

即Xi'+X2'=1,且有Xi'三0,X2‘叁0.

2.当乙使用Pi策略时，甲的平均赢得为：5Xi'+8X2’,此平均赢得应大于等于V,

即5XI'+8X2'叁V

3.当乙使用p2策略时，甲的平均赢得为：9Xi'+6X2,此平均赢得应大于等于V,

即9XI'+6X2'叁V

第二步，我们来考虑V的值，V的值与赢得矩阵A的各因素的值是有关的，如

果A的各元素的值都大于零，即不管甲采用什么策略，乙采用什么策略，甲的赢

得都是正的。这时的V值即在乙出对其最有利的策略时甲的平均赢得也显然是正

的。因为A的所有元素都取正值，所以可知V>0.

第三步，作变量替换，令Xi=/（i=1,2）

考虑到V>0,这样把以上5个数量关系式变为：

X1+X=—,X1叁0,X220,

2V

5Xi+8X2叁1

9Xi+6X2叁1

对甲来说，他希望V值越大越好，也就是希望（的值越小越好，最后，我们就

建立起求甲的最优混合策略的线性规划的模型如下：

minXu-X2

约束条件：5XI+8X2

9Xi+6X2叁1

X1叁0,X2叁0

同样求出乙最优混合策略，设y“y2’分别为乙出策略01,02的概率，V为甲出

对其最有利的策略的情况下，乙的损失的平均值。

同样我们可以得到：

y>+y2'=1,

5yi+9y2=V

8yi+6y2=V

yf叁0,y2‘叁0.

同样作变量替换，令yi=/(i=1,2)

得关系式：yi+y2=?

5yi+9y2=1

8yi+6y2=1

yi叁0,y2Mo.

乙希望损失越少越好，即V越小越好而(越大越好，这样我们也建立了求乙的

最优混合策略的线性规划的模型如下：

maxyn-y2

约束条件：5yi+9y2

8yi+6y2=1

yi叁0,y2叁0.

22.考虑下列线性规划(20分)

MaxZ=2Xi+3X2

r2Xi+2X2+X3=12

XI+2X2+X4=8

J4Xi+X5=16

4X2+X6=12

、XjN0(j=l,2,...6)

其最优单纯形表如下：

基变量XIX2X3X4X5X6

X30001-1-1/40

XI410001/40

X64000-21/21

X220101/2-1/80

°j000-3/2-1/80

当C2=5时，求新的最优解

解当C2=5时

o4=—5/2

o