《运筹学》模拟试题及参考答案

《运筹学》模拟试题及参考答案

一、判断题（在下列各题中，你认为题中描述的内容为正确者，在题尾括号

内写“J”，错误者写“义”。）

1.图解法提供了求解线性规划问题的通用方法。（）

2.用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数C-Z.

》0,则问题达到最优。（）

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

4.满足线性规划问题所有约束条件的解称为基本可行解。（）

5.在线性规划问题的求解过程中，基变量和非基变量的个数是固定的。（）

6.对偶问题的目标函数总是与原问题目标函数相等。（）

7.原问题与对偶问题是一一对应的。（）

8.运输问题的可行解中基变量的个数一定遵循m+n-l的规则。（）

9.指派问题的解中基变量的个数为m+n。（）

10.网络最短路径是指从网络起点至终点的一条权和最小的路线。（）

11.网络最大流量是网络起点至终点的一条增流链上的最大流量。（）

12.工程计划网络中的关键路线上事项的最早时间和最迟时间往往不相等。（）

13.在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔

时间比订购模型的间隔时间长。（）

14.单目标决策时，用不同方法确定的最佳方案往往是一致的。（）

15.动态规划中运用图解法的顺推方法和网络最短路径的标号法上是一致的。

（）

二、简述题

1.用图解法说明线性规划问题单纯形法的解题思想。

2.运输问题是特殊的线性规划问题，但为什么不用单纯形法求解。

3.建立动态规划模型时，应定义状态变量，请说明状态变量的特点。

三、填空题

1.图的组成要素；“

2.求最小树的方法有、。

3.线性规划解的情形有、、、

4.求解指派问题的方法是o

5.按决策环境分类，将决策问题分为、、

6.树连通，但不存在。

四、下列表是线性规划单纯形表（求ZmaJ，请根据单纯形法原理和算法。

1.计算该规划的检验数

C—A32000

J

CiXBbxxxX

lX,34、

1

3X,310-10

12

2X340111/20

z.33.52-20

C.—Z.

JJ

2.计算对偶问题的目标函数值

3.确定上表中输入，输出变量

五、已知一个线性规划原问题如下,请写出对应的对偶模型

S=6x+x

max12

x+x<7

12

2x+3犬>16

12

x,x>0

112

六、下图为动态规划的一个图示模型，边上的数字为两点间的距离，请用逆推

法求出S至F点的最短路径及最短路长。

七、自己选用适当的方法，对下图求最小（生成）树。

八、用标号法求下列网络Vi-V7的最短路径及路长。

九、下图是某一工程施工网络图（统筹图），图中边上的数字为工序时间（天）,

请求出各事项的最早时间和最迟时间，求出关键路线，确定计划工期。

十、某企业生产三种产品A1、ArA3O每种产品在销售时可能出现销路

好（SJ,销路一般（SJ和销路差（SJ三种状态，每种产品在不同销售状态的获利情

况（效益值）如表1所示，请按乐观法则进行决策，选取生产哪种产品最为合适。

M态

-―或益值\sS

,2S3

Ai3010-6

2012

A29

A3151312

俵1)

十一、已知运输问题的运价表和发量和收量如表2所示，请用最小元素法求出

运输问题的一组可解释。

B3

B2Bq

A\291279

13524

A2

A3104265

3546

（表2）

十二下列表3是一个指派问题的效率表（工作时间表），其中A.为工作人员（i=l,

2,3,4）、Bj为工作项目（j=l,2,3,4）,请作工作安排，使总的工作时间最小。

B3B4

B2

A\4174

2235

A2

A35643

A46324

参考答案

一、判断题

⑴X⑵J⑶J(4)X(5)V(6)X(7)V(8)V(9)X(10)V

(11)X(12)X(13)7(14)X(15)X

二、简述题

1、在可行域内先确定一个基本可行解，然后通过迭代计算，逐步使目标函数增大(求2,皿)，

求出新解，计算出方案机会成本后，得出相应检验数，当所有的CjZjWO时即得最优解。

2、运输问题可以用单纯形求解，但由于虚设的变量多，运算复杂，十分不合算，所以不用

单纯形法求解，而用简单的表上作业法求解。

3、由于动态规划的求解过程是一个多段决定过程，其状态变量必须满足无后效性和可知性

的特征要求。

三、填空题

1.树

2.破圈法和避圈法

3.可行解、退化解、无界解、多重解

4.匈牙利法

5.确定性决策，不确定性决策，风险性决策。

6.圈。

四.

c.-320000

CXbX,X,X*XX.X

1n0123445A6

M一I一x］a一-1--------«------------uo---------1------------u------------ux

⑵X240111/2-10

Z327/2-2-23/2

C-Z00(-7/2)(2)2-3/2

3.X〈输入，玉输出。

五、Zm—x+l6y2

'-兀+2y24

'一片+3y24I

六、吊？

(16)

s—A—B—c—F32

七、

s,

S2S3

A\3010-6

20129

A2

A3151312

选方案A1

十一、

.12...

2...(§)..।

(1)•••3•,,(5…&3

3

10-④,,•②…6

b.3746

J

B1B,B,%B；

,,⑪•••6•••

A14①74N

A3

2②235一©•6

A3564③J••3

63②士=8••i…。…2

俵3）

《运筹学》试题参考答案

••

一、填空题（每空2分，共10分）

1、在线性规划问题中，若存在两个最优解时，必有相邻的顶点是最优解。

2、树图中，任意两个顶点间有且仅有一条链。

3、线性规划的图解法适用于决策变量为两个线性规划模型。

4、在线性规划问题中，将约束条件不等式变为等式所引入的变量被称为松弛变

量。

5、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡

的标准形式。

6、运输问题中求初始基本可行解的方法通常有最小费用法与西北角法两

种方法。

7、称无圈的连通图为树，若图的顶点数为p,则其边数为p—l。

二、(每小题5分，共10分)用图解法求解下列线性规划问题：

1)maxz=6X]+4x,⑴

2x+x<10(2)

12

x+x<8(3)

*12

〈2

x<7(4)

2

⑸、⑹

2)minz=2x,+x、⑴

12

-%+4%<24(2)

I2

(3)

5<x<10⑷、

X0

2-(6)

解：

从上图分析，可行解域为abcde,最优解为e点。

由方程组

[%+x—8

解出X]=5,X=3

[x=52

(x)

.•.X*=1=(5,3)T

1%

minz=Z*=2x5+3=13

三、（15分）一家工厂制造甲、乙、丙三种产品，需要三种资源一一技术服务、劳

动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以

及这三种资源的储备量如下表所示：

技术服务劳动力行政管理单位利润

甲110210

乙1426

丙1564

资源储备量100600300

1）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）

2）用单纯形法求该问题的最优解。（10分）

解：1）建立线性规划数学模型：

设甲、乙、丙三种产品的生产数量应为％、x2>x3,则％、x2>x3^0,设z

是产品售后的总利润，则

maxz=10x,+6Xc+4x.

123

s.t.

%+x+x<100

123

10%+4x+5%<600

《123

2x+2x+6x<300

123

x,x,x>0

l123

2）用单纯形法求最优解：

加入松弛变量X，，x,x,得到等效的标准模型：

456

maxz=10x,+6x^+4x+0x+0x+0x,

123456

X+x+%+x=10()

1234

10%+4x+5%+x-600

1235

2x+2x+6%+x=300

1236

%20,j=1,2,…6

i/

列表计算如下:

1064000

CXbe

BBXXXXXXL

123456

X

04100111100100

0X60045010

5(10)60

0X300226001

6150

000000

10f64000

X1/2

04400(3/5)1-1/100200/3

10X

16012/51/201/100150

0X18006/5501

6-1/5150

1045010

02t-10-10

6X015/65/3-1/60

2200/3

10X100/3101/6-2/31/60

1

X

06100004-201

220010620/310/32/30

3

00-8/3-10/3-2/30

・V(100200c\(\(\i(\r\\

..X*=(__，___,0,0,0,100)T

33

...maxz=10X122+6X92200

333

四、（10分）用大M法或对偶单纯形法求解如下线性规划模型:

minz=540X]+450x2+720x3

3x+5x+9x>70

123

<9x+5x+3x>30

123

x,x,x>0

1123

解：用大M法，先化为等效的标准模型：

maxz/=-540X|-450x^—720x3

s.t.

3%+5%+9%-%=70

1234

49%+5%+3%-x=30

I235

y>0,j=1,2,...,5

ij

增加人工变量相、x7,得到：

maxz/=-540x,—450x、-720x「Mx「Mx〃

12367

3x+5x+9x-x+x=70

12346

49%+5%+3%-％++x=30

I2357

%>0,j=1,2,...,5

ij

大M法单纯形表求解过程如下:

-540-450-72000-M-M

Xb0

cBBL

XXXXXXX

1234567

-MX70359-1010

670/3

-MX30(9)530-101

730/9=10/3

-12M—10M-12MMM-M-M

12M-540t10M-45012M-720-M-M00

-MX60010/3(8)-11/31-1/3

6

10/3/1/3

-540X10/315/91/30-1/901/9

1=10

-300+10/3M-8M-180-M-M/3+60-MM/3-60

0-150+10/3M8M-540tMM/3-600-M/3+60

15/2/5/12

-720X15/205/121-1/81/241/8-1/24

3=18

5/6/5/12

-540X5/61(5/12)01/24-1/8-1/241/8

1=2

-540-572-720-135/2475/12-135/2-75/2

0125t0135/2-475/12135/2-M75/2-M

-720X20/3-1011/61/61/6-1/6

3

—450X

2212/5101/10-3/10-1/103/10

-360-450-7207515-75-15

-5700

-18000-75-1575-M15-M

20

，该对偶问题的最优解是x*=(0,2,3’0,0)T

最优目标函数值minz=—(-5700)=5700

五、（12分）给定下列运输问题：（表中数据为产地A,到销地耳的单位运费）

B2B3B4s.

1

AI2011865

A]5910210

1874115

d.331212

j

1）用最小费用法求初始运输方案，并写出相应的总运费；（4分）

2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）

解：用“表上作业法”求解。

1）先用最小费用法（最小元素法）求此问题的初始基本可行解:

...初始方案:

Z=2OX3+11X2+2X10+7X1+4X12+1X2=159

•••选七作为入基变量迭代调整。

②用表上闭回路法进行迭代调整：

费\销

BB3B

1B24Si

20-121186-1

A

15

X32X

59-110-52

A

210

3XX7

18-147041

A15

3

XX105

\30

331212

430\

调整后，从上表可看出，所有检验数bW0,已得最优解。

•••最优方案为:

最小运费Z=11X3+8X2+5X3+2X7+4X10+1X5=123

六、（8分）一个公司经理要分派4个推销员去4个地区推销某种商品。4个推销员各有不同的

经验和能力，因而他们在每一地区能获得的利润不同，其估计值如下表所示：

7D2D3D4

甲35272837

乙28342940

丙35243233

T24322528

问：公司经理应怎样分派4个推销员才使总利润最大？

解：用求极大值的“匈牙利法”求解。

效率矩阵表示为:

<35272837、’513123、

M—C行约简

283429402126110

〉N

35243233516871

M=40

(24322528JJ681512,

c2106(0)、

(21090、

126110二12680*

0)110*2所画()0元素少于n(n=4),

°1132

18074j18(0)44,

未得到最优解,需要继续变换矩阵(求能覆盖所有0元素的最少数直线集合):

(2106J(0)>

1268J0*

11

w；11T2

\一\一44

未被直线覆盖的最小元素为Cij=2,在未被直线覆盖处减去2,在直线交叉处加上2。

"(0)840*、

0840]标号

1046(0)

10460]>

011040*11(0)4

8046,<8(0)46>

J00o'

得最优解：0001

0010

、0100,

...使总利润为最大的分配任务方案为:

甲一Dj乙一D小丙一D3，丁—D,

此时总利润W=35+40+32+32=139

七、(6分)计算下图所示的网络从A点到M点的最短路线及其长度。

解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下:

最佳策略为：A-C-FfG-M

此时的最短距离为8+8+5+5=26

八、（8分）用P-T标号法求下图从至的最短路。（需写出最短路线）

VV

2

5V

8

13

解：此为网络分析之“最短路问题”，可用顺向追踪“TP标号法”解决如下:

□□E

%到V］的最短路线是：叫一v°fv〈fv°fv&fV”，最短距图2+1+1+7+9=20。

1/1ZDyo11

九、（10分）用找增广链的方法求如下网络的最大流。（需写出相应的增广链）（弧

旁的数字为该弧容量）

解：此为网络分析之“寻求网络最大流问题”，可用“寻求网络最大流的标号法（福

特-富克尔逊算法)”解决如下：

㈠标号过程：

1、给VS标上(0,8)；

2、检查v,在弧(v,v,)上，f>0,C=4,f<C,给匕标号(s,B(v)),其

ss1sisisisi11

中P(v)=min(v),(C-f)}=min{t-oo,4-o}=4>

Issisi

(s,4)

(s,10)

R］理,给V标号(S,B(v)),其中p(u)=min{|3(u),(C-f)}=minVoo,10-0)=10>

222ss2s2

3、检查v,在弧(v,v)上，f=0,C=3,fvC,给v标号(LB(v)),其

1131313131333

中B(u)=min{p(v),(C-f)}=minU,3-o)=3,

311313

(s,4)(3,3)

检查v,同理，给v标号(3,B(v)),其中)=min4e),(C-f)}=min&4-。}=3，

344433434

检查v，同理，给V标号(2,B(V)),其中p(v)=min{p(v),(C-f)}=min{10,4-oL4，

255522525

4、检查v,,在弧(v,v)上，f=0,C=7,f<C,给v标号(4,B(v)),其中

3(v)=min{p(v),(C-f)}=min6,7-()}=3/V得到标号,标号过程结束。

t44t4fI

(s,4)(3,3)

㈡调整过程：从