中南大学现代远程教育平台—运筹学课程作业答案.doc

《运筹学》作业答案

作业一

一、是非题：
1.图解法与单纯形法虽然求解的形式不同,但从几何上理解，两者是一致的。（√）
2。线性规划问题的每一个基解对应可行解域的一个顶点.（╳）
3。如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得.（√）
4.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量.(√）
5.单纯形法计算中，如果不按最小比值规划选出基变量,则在下一个解中至少有一个基变量的值为负。（√）
6。线性规划问题的可行解如为最优解，则该可行解一定是基可行解.（╳）
7.若线性规划问题具有可行解，且可行解域有界，则该线性规划问题最多具有有限个数的最优解.（╳）
8。对一个有n个变量,m个约束的标准型线性规划问题，其可行域的顶点数恰好为个。（╳）
9.一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。（√)
10。求Max型的单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。（√）

二、线性规划建模题：
1。某公司一营业部每天需从A、B两仓库提货用于销售，需提取的商品有:甲商品不少于240件,乙商品不少于80台，丙商品不少于120吨。已知：从A仓库每部汽车每天能运回营业部甲商品4件，乙商品2台，丙商品6吨，运费200元/每部;从B仓库每部汽车每天能运回营业部甲商品7件，乙商品2台,丙商品2吨,运费160元/每部。问：为满足销售量需要，营业部每天应发往A、B两仓库各多少部汽车，并使总运费最少？
解：设营业部每天应发往A、B两仓库各x1，x2部汽车，则有：

2。现有一家公司准备制定一个广告宣传计划来宣传开发的新产品,以使尽可能多的未来顾客特别是女顾客得知.现可利用的广告渠道有电视、广播和报纸，根据市场调查整理得到下面的数据：
项目
电 视
广播
报纸
一般时间
黄金时间
每个广告单元的费用(元）
每个广告单元所接触的顾客数（万人）
每个广告单元所接触的女顾客数(万人）
4000
40
30
7000
90
40
3000
50
20
1500
20
10
该企业计划用于此项广告宣传的经费预算是80万元，此外要求：
①至少有200万人次妇女接触广告宣传;②电视广告费用不得超过50万元,
③电视广告至少占用三个单元一般时间和两个单元黄金时间，
④广播和报纸广告单元均不少于5个单元而不超过10个单元。
解：设电视一般时间、黄金时间、广播和报纸各投放广告单元数为x1，x2，x3，x4，有：

三、计算题：
对于线性规划模型
1。用图解法求出其所有基本解，并指出其中的基本可行解和最优解。
2.三个方程中分别添加松驰变量x3,x4，x5后把模型化成标准型，用单纯形法寻求最优解。并与1题中图解法中对照,单纯形表中的基可行解分别对应哪些顶点.
3。若直接取最优基,请用单纯形表的理论公式进行计算对应基B的单纯形表，并与第2题最优单纯形表的计算结果比较是否一致.(附单纯形表的理论公式：非基变量xj的系数列向量由Pj变成基变量的值为，目标函数的值为,检验数公式）。
解：（1)图解如下：

所有基本可行解：O(0,0）,Q1（6，0），Q2（4,2），Q3（2，3）,Q4（0,3）共五个基可行解。
从上图知：最优解为点Q2(4,2），目标函数值为Z＝20.
(2）模型标准化为

单纯形法表迭代过程如下表示：
cj
3 4 0 0 0

CB
XB
x1 x2 x3 x4 x5
b
θ
0
0
0
x3
x4
x5
［1] 1 1 0 0
1 2 0 1 0
0 1 0 0 1
6
8
3
6 出基
8
—
－Z
3 4 0 0 0
0

3
0
0
x1
x4
x5
1 1 1 0 0
0 [1] —1 1 0
0 1 0 0 1
6
2
6
2
3
3
－Z
0 1 -3 0 0
－18

3
4
0
x1
x2
x5
1 0 2 -1 0
0 1 -1 1 0
0 0 1 —1 1
4
2
1

－Z
0 0 -2 —1 0
—20

从上表知：表一中的基可行解(0，0，6,8，3)对应坐标原点O，表二中的基可行解为（6,0,0,2,3）对应图中的Q1点，表三中的基可行解为(4,2,0，0，1）对应图中的Q2点,得到最优解。
(3）若取基,基变量为x1,x2,x5，刚好是最优表中的对应基变量，可算出(从第三个单纯形表也可找到B－1），由单纯形表计算公式计算非基变量的系数列向量、检验数及基解等.
，，.
，
与迭代的第三个单纯形表计算结果一致。

四、写出下列线性规划问题的对偶问题。

解：设三个方程的对偶变量分别为y1，y2,y3,有:

五、有一个Max型的线性规划问题具有四个非负变量,三个“≤”型的条件，其最优表格如下表，请写出其对偶问题的最优解及目标函数值。
XB
x1 x2 x3 x4 x5 x6 x7
b
x4
x6
x1
0 1 2/3 1 2/3 0 -1/3
0 2 —1 0 0 1 0
1 1 1/3 0 1/3 0 1/3
14/3
4
10/3
-Z
0 —2 —4/3 0 —4/3 0 -1/3
-34/3

解：该问题的松驰变量为x5，x6，x7,由对偶规划的性质知三个对偶变量的值分别为x5，x6，x7检验数的负值，目标函数值与原问题相等.故， W＝34/3.
六、求下列运输问题的解：
销 地
产 地
B1
B2
B3
供应量
A1
6
4
2
4
A2
8
5
7
5
需求量
3
3
3

用表上作业法求解此问题的最优解.（要求用行列差值法给初始解，用位势法求检验数。)

解:（1）这是一个产销平衡的运输问题，用行列差值法给初始解:
销 地
产 地
B1
B2
B3
行差值
供应量
A1
6(1
4(╳）
2（3）
2,2
4
A2
8（2）
5（3）
7（╳）
2，3
5
列差值
2，2
1，1
5

需求量
3
3
3

(2)用位势法求检验数：对基变量有：，并令u1=0，求出行列位势，如下表。
销 地
产 地
B1
B2
B3
行位势vi
供应量
A1
6(1）
4(╳）
2（3）
u1=0
4
A2
8（2）
5(3）
7（╳）
u2=2
5
列位势vj
v1=6
v2=3
v3=2

需求量
3
3
3

各非基变量的检验数分别为：R12=4－(3+0）=1，　R23=7－（3+2）=2,即基变量的检验数都大于0,当前方案为最优调运方案。

作业二

一、用隐枚举法求解下面0－1型整数规划问题：

解：问题为求极大型，需所有的变量前的价值系数变为负号，故令，模型变为:
，
用目标函数值探索法求最大值:

x1’
x2’
x3
是否满足约束方程

Z
(1）
(2）
(3)
(4)
0
1
0
0
0
1
0
0
╳
√

√

√

√
3
2
从表中可以看出,当时具最大目标函数值,即，Zmax＝2。
二、某服装厂有五项工作需要分给五个技工去完成，组成分派问题,各技工完成各项工作的能力评分如下表所示。请问应如何分派，才能使总得分最大？
工作
评分
人员
B1

平车
B2

考克
B3

卷边
B4

绷缝
B5

打眼
A1
1.3
0。8
0
0
1。0
A2
0
1。2
1。3
1。3
0
A3
1.0
0
0
1.2
0
A4
0
1。05
0
0。2
1。4
A5
1。0
0.9
0.6
0
1.1

解：（1）效率矩阵为:

，问题是求极大，转化为求极小问题，设,

构造以bij为系数的矩阵，

（2)对bij矩阵进行系数变换，使每行每列出现0元素，

（3）进行试分配：
，

（4）作最少的直线覆盖所有的0元素：

(5）在没有被覆盖的部分中找出最小数0。1，则第四、五行减去这个最小数0。1，同时第五列加上这个最小数，其他元素不变，目的是增加0元素的个数。

（6）试分配:
，此时，所有的0都已打括号或划掉,且打括号的0元素（独立的0元素)个数刚好为5个，得到了问题的最优解，问题的解矩阵为:

，即A1做平车，A2做卷边，A3做绷缝,A4做打眼，A5做考克，总得分为6.1.

三、某厂从国外引进一台设备，由工厂A至G港口有多条通路可供选择，其路线及费用如图1所示。现要确定一条从A到G的使总运费最小的路线，请将该问题描述成一个动态规划问题，然后求其最优解。
0
70
C1
B1

D11

30
60
20

40
G

C2
40
A

10
30
D21
30

0

50
C3
B2

第四阶段
第三阶段
第二阶段
第一阶段

图1

解:把问题分为4个阶段，如图1示。
设Sk为每一阶段的起点，xk为第k阶段的决策变量,状态转移方程为：SK+1＝xk(Sk）。k=1，2,3，4。
阶段指标函数为Sk到xk(Sk）的距离值，最优指标函数fk(Sk)为第k阶段状态为Sk时，从Sk到终点G的最短距离值。指标函数递推方程:，k=3,2,1
边界方程为:。
下面列表计算如下：
x4
S4

x4

G
D1
30
30
G
D2
40
40
G
k=4时：

k=3时：
x3
S3

x4

D1
D2
C1
0+30
－
30
D1
C2
40＋30
30＋40
70
D1或D2
C3
－
0＋40
40
D2
k=2时:
x2
S2

x4

C1
C2
C3
B1
70+30
60+70
－
100
C1
B2

10＋70
50＋40
80
C2
k=1时：
x1
S1

x4
B1
B2
A
20+100
30＋80
110
B2
最优路线有两条：A→B2→C2→D1→G或A→B2→C2→D2→G,最短距离值为110。

四、某公司打算在三个不同的地区设置4个销售点，根据市场预测部门估计，在不同的地区设置不同数量的销售店，每月可得到的利润如表1所示。试问在各个地区应如何设置销售点,才能使每月获得的总利润最大?其值是多少
表1
销售店
利润
地区
0
1
2
3
4
1
0
16
25
30
32
2
0
12
17
21
22
3
0
10
14
16
17
解：设给每一个地区设置一个销售点为一个阶段,共三个阶段。
xk为给第k个地区设置的销售点数;Sk 为第k阶段还剩余的销售点数，S1＝4
状态转移方程为：Sk+1=Sk－xk dk(xk)为在第k个地区设置xk个销售点增加利润
最优指标函数fk（Sk）为第k阶段把Sk个销售点时分给第k、k+1,…3个销售点获取的最大收益.
指标函数递推方程：，k=2，1
边界方程为：。
逆推计算如下:
k=3时：S3=x3
x3
S3

x3
0
1
2
3
4
0
0

0
0
1

10

10
1
2

14

14
2
3

16

16
3
4

17
17
4
k=2时:S3= S2－x2
x3
S3

x2

0
1
2
3
4
0
0

0
0
1
0＋10
12+0

12
1
2
0+14
12+10
17+0

22
1
3
0+16
12+14
17+10
21+0

27
2
4
0+17
12+16
17+14
21+10
22+0
31
2或3
k=1时:S2= S1－x1
x1
S1

x2
0
1
2
3
4
4
0＋31
16＋27
25＋22
30＋12
32＋0
47
2

最优决策方案为：第一个地区设置2个销售点，第二个地区设置1个销售点，第三个地区设置1个销售点，每月可获总利润为47。

五、某厂生产一种产品，该产品在未来三个月中的需要量分别为3，4,3万件，若生产准备费为3万元/次，每件成本为1元,每件每月存储费为0.7元,假定1月初和4月初存货为0，并每月产量不限。试求该厂未来三个月内的最优生产计划?要求用解：这是个动态决策问题，下面用动态规划求解.
解:这是个动态决策问题,下面用动态规划求解,建立如下动态规划数学模型。
需求量： D1=3 D2=4 D3=3
1月
3月
4月
2月

①阶段（月份)n： 1 2 3 4
②状态变量Sn：每月初库存,有 S1={0｝，S2=｛0,1,2,3, 4,5，6，7｝,S3={0，1,2，3}， S4=｛0}。
③决策变量Xn：每月的生产量 X1：
据题意有决策变量的允许范围：3≤x1≤10， 0≤x2≤7, 0≤x3≤3 。
④状态转移方程： Sn+1 = Sn +Xn－D n
⑤阶段指标函数（成本):成本=生产费用＋存储费用
rn(Xn)=
3＋1·Xn ， Xn＞0
0 ， Xn＝0

＋0.7Sn

⑥指标函数递推方程：
，

下面利用表格进行计算，从最后一个阶段开始：
n=3时: 此时 S3+X3－DD3=0，即X3=3－S3
X3
S3
r3（X3）
f3(S3)
X3＊
0
1
2
3
0

6+0=6
6
3
1

5+0.7=5。7

5.7
2
2

4+1。4=5.4

5.4
1
3
0+2.1=2。1

2.1
0

n=2时: 此时 S2+X2≥D2=4，即X2≥4－S2；S3 = S2 +X2－D2，即S3 = S2 +X2－4
X2
S2
r2（X2）+ f3 （S3）
f2 (S2)
X2
0
1
2
3
4
5
6
7
0

7+6
8+5.7
9+5.4
10+2.1
12。1
7
1

6.7+6
7。7+5.7
8。7+5。4
9。7+2。1

11。8
6
2

6。4+6
7。4+5。7
8。4+5.4
9。4+2。1

11.6
5
3

6.1+6
7。1+5.7
8。1+5。4
9.1+2。1

11.2
4
4
2。8+6
6.8+5.7
7.8+5。4
8。8+2。1

8。8
0
5
3。5+5.7
7.5+5。4
8.5+2。1

9.2
0
6
4.2+5.4
8.2+2.1

9.6
0
7
4.9+2.1

7
0
n=1时： X1≥3－S1；S2 = S1 +X1－D1,即S2 = S1 +X1－3
X1
S1
r1(X1)+ f2 （S2）
f1 (S1)
X1*
0
1
2
3
4
5
6
7
0

6+12.1
7+11.8
8+11。6
9+11。2
10+8。8
18。1
3
由此可知：S1=0，此时X1＊=3； S2 = S1+X1*－3=0＋3－3=0，此时X2＊=7；
S3 = S2+X2＊－4=0＋7－4=3，此时X3＊=0。
最优策略为：X＊={x1*，x2＊，x3＊}={3，7，0} Z*=f1*(S1）=18。1
即第一个月生产3万件,第二个月生产7万件，第三个月生产0万件，可使总成本最低为18。1万元。

作业三（图与网络分析、存贮论部分)

一、 判断题：
1。图论中的图不仅反映了研究对象之间的关系,而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意。（╳）
2.在任一图G中，当点集V确定后,树图是G中边数最少的连通图。(√）
3.如图中某点vi有若干个相邻点，与其距离最远的相邻点为vj，则边[vi,vj]必不包含在最小支撑树内。╳)
4.在任一连通图G中,点数为N,则保证这N点相互连通且任意两点间仅有一条链相通的图一定含有N－1条边。(√）
5.求网络最大流问题可归结为求解一个线性规划问题。(√)
6.订购费为每订一次货所发生的费用，它同每次订货的数量无关。(√）
7。在同一存贮模型中，可能既发生存贮费用，又发生短缺费用。(√)
8.在允许缺货发生短缺的存贮模型中,订货批量的确定应使由于存贮量的减少带来的节约能抵消缺货时造成的损失。（√）
9。当订货数量超过一定的值允许打折扣的情况下,打折扣条件下的订货批量要大于不打折扣时的订货批量。(√）
10。在其他费用不变的情况下,随着单位存贮费用的增加，最优订货批量也相应增大。（╳）

二、求图1中的最小树5
v1
v2
v3
v4
v6
v7
v8
v5
6
5
4
5
6
2
7
8
3
3
3
4
4
1
图1
：

解：用破圈法求得的最小部分树为：
v1
v2
v3
v4
v6
v7
v8
v5
4
2
3
3
3
1
5

最小部分树的权为：1＋3+3＋3+2＋4+5＝21.

三、求图2中从点v1到其余各点的最短路：
4
3
v1
v3
v5
v7
3
2
5
1
3
8

2
7
3
6
图2
v4
v2

8

0

5
2

解：用T、P标号算法:
1。给v1点标P标号，其他点标T标号，为＋∞。
2。从v1点出发,修改v2、v3点的T标号,并把其中最小者改为P标号.
T(v2）=3，T(v3）=2＝P（v3）。
3。从刚刚获得P标号的点v3出发，可达v2,v4，v5,修改T标号，并把最小者改为P标号。
4。依此类推，各点的P标号如图2所示。从v1到v7的最短路为：v1 →v3→v5→v7，距离为8.
四、求图3中网络的最大流、最大流的流量和最小割.
v2
v5
v7
v1
v3
v6
v4
5
8
4
3
4
4
2
8
8
9
8
图3
6

v2
v5
v7
v1
v3
v6
v4
5,5
8,8
4,4
3,3
4,4
4,4
2,2
8,3
8,8
9,9
8,8
6,2
解：最大流如图示:

0,∞

仅有起点v1可标号，最小割为，最大流流量为17。

五、计算题:
1.设需要某物品12件/天，不允许缺货，存贮费率为0.02元/件一天。为满足需要，可以采取订购或自行组织生产。有关数据如下：

订购
自行生产
提前期或生产准备期
8天
13天
物品单位
11元/件
9。6元/件
每次订购费或准备费
20元
90元
补充速率
∞
25件/天
试决定经济的物品供应来源：订购或自行生产?你决定的来源比另一来源费用节约比率？经济订购批量与存贮水平是多少？
解：(1)若订购，计算一天的总费用(含物品费用)：
Ch＝0。02（元/件·天)，CO＝20(元/次），R＝12（件/天）

一天的费用：F＝物品本身的费用＋总存贮费
F＝12×11＋3.1＝135。1(元/天）
订购批量：＝155(件/次）
存贮水平：
（2）若自行生产，计算一天的总费用（含物品费用）：
Ch＝0。02（元/件·天),Cp＝90(元/次），R＝12（件/天）

一天的费用:F＝物品本身的费用＋总存贮费
F＝12×9.6＋4.74＝119.94(元/天)
生产批量：＝456（件/次）
存贮水平：

2.某商店拟购进一种应时商品出售.经估算,在未来旺季中每出售一箱可净得利润5000元，如旺季过后则只能削价出售，每箱要赔本2000元。这种商品的需求情况经统计分析，具有以下的分布规律：
需求量（箱)
0
1
2
3
4
5
概率P(R)
0。05
0。1
0。25
0.35
0。15
0.1
现商店经理需作出订购该商品多少箱的决策，其最优决策是订购多少箱？获利期望值为多大？最小损失期望值又是多大？
解：由题意有：α＝5000元，β＝2000元

由表1的累计概率可知：　 最优决策是订购3箱。
获利期望值：E［C（Q）］＝－2000×3×0。05＋(5000－2000×2)×0。1＋(5000×2－2000×1）×0。25＋5000×3×0.6
＝10800元。
同理可计算出最小损失期望值为2950元。

15