2023年第四版运筹学部分课后习题解答

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐第四版运筹学部分课后习题解答运筹学部分课后习题解答P471.1用图解法求解线性规划问题

a）

12

12

12

12

minz=23

466..424

,0

xx

xx

stxx

xx

+

+≥

?

?

+≥

?

?≥

?

解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为

最优解，即该问题有无穷多最优解，这时的最优值为

min3

z=2303

2

?+?=

P471.3用图解法和单纯形法求解线性规划问题

a）

12

12

12

12

maxz=10x5x

349..528

,0

xx

stxx

xx

+

+≤

?

?

+≤

?

?≥

?

解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点，

即

1

12

122

1

349

3

528

2

x

xx

xxx

=

?

+=

??

?

??

+==

??

?

，即最优解为*

3

1,

2

T

x

??

=?

??

这时的最优值为

max

335

z=1015

22

?+?=

单纯形法：原问题化成标准型为

121231241234

maxz=10x5x349

..528,,,0xxxstxxxxxxx+++=??

++=??≥?jc→

10

5

BC

BXb1x

2x

3x

4x

03x934100

4x

8

[5]201jjCZ-

10

50003x21/50[14/5]1-3/510

1x

8/5

12/501/5jjCZ-

10-

252x3/2015/14-3/1410

1x

1

10-1/7

2/7

jjCZ-

-5/14-25/14

所以有*max33351,,1015222T

xz??

==?+?=???

P782.4已知线性规划问题：

1234

12

4122341231234max

24382669,,,0

zxxxxxxxxxxxxxxxxxxx=+++++≤??+≤??

++≤?

?++≤?≥??

求:(1)写出其对偶问题；（2）已知原问题最优解为)0,4,2,2(*=X，试按照对偶理论，直接求出对偶问题的最优解。解：（1）该线性规划问题的对偶问题为：

1234

12

4123434131234min

86692234

11,,,0

wyyyyyyyyyyyyyyyyyyy=+++++≥??+++≥??

+≥?

?+≥?≥??

（2）由原问题最优解为)0,4,2,2(*=X，按照互补松弛性得：

12

412343422341yyyyyyyyy++=??

+++=??+=?

把)0,4,2,2(*=X代入原线性规划问题的约束中得第四个约束取严格不等号，即4224890y++=所以产品D值得生产。

P1013.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。表3-35

B1B2B3B4产量A1A2A31012227142091611201815255销量

5

15

15

10

产地销地

解：由于∑∑===4

1

31

jjiiba，即产销平衡.所以由已知和最小元素法可得初始计划为

B1B2B3B4产量A1

A2A351501501015255销量

5

15

15

10

检验：

因为有两个检验数小于零，所以需调节，调节一：

B1B2B3B4产量A1A2A351501510015255销量

5

15

15

10

检验：

因为还有检验数小于零，所以需调节，调节二：

产地销地

产地

销地

B1B2B3B4产量A1

A2A355101510015255销量

5

15

15

10

检验：

从上表可以看出全部的检验数都大于零，即为最优计划最小运费为：min25257109151110180335z=?+?+?+?+?+?=

表3-36

B1B2B3B4产量A1A2A386549314427372526销量

10

10

20

15

解：由于3

4

1

1

5855ijijab===>=∑∑，即产大于销，所以需添加一个假想的销地，销

量为3，构成产销平衡问题，其对应各销地的单位运费都为0。B1B2

B3

B4

B5产量A1

A2A3865

493

144

273

00072526销量10102015

3

由上表和最小元素法可得初始计划为

产地销地

产地销地产地销地

B1B2B3B4B5产量A1

A2A3911071315372526销量

10

10

20

15

3

检验：

从上表可以看出全部的检验数都大于零，即为最优计划

最小运费为：min69513101741331503193z=?+?+?+?+?+?+?=

表3-37

B1B2B3B4B5产量A1

A2A38566M3389746578203030销量

25

25

20

10

20

解：由于3

5

1

1

80100ijijab===<=∑∑，即销大于产，所以需添加一个假想的产地，产

量为20，构成产销平衡问题，其对应各销地的单位运费都为0。B1B2B3B4B5产量A1

A2A3A485606M3038907460578020303020销量

25

25

20

10

20

产地销地

产地销地

产地销地

由上表和最小元素法可得初始计划为

B1B2B3B4B5产量A1

A2A3A4520252001015520303020销量

25

25

20

10

20

检验：

因为有两个检验数小于零，所以需调节，调节一：

B1B2B3B4B5产量A1A2A3A4

205252001051520303020销量2525

20

10

20

检验：

产地销地

产地

销地

因为还有检验数小于零，所以需调节，调节二：B1B2B3B4B5产量A1A2A3A4

205252001002020303020销量25

25

20

10

20

检验：

从上表可以看出全部的检验数都大于零，即为最优计划

最小运费为：min320520410653258002000305z=?+?+?+?+?+?+?+?=

P1274.8用割平面法求解整数规划问题。

a）12

121212

max7936

735,0,zxxxxxxxx=+-+≤?

?

+≤??≥?且为整数

解：该问题的松弛问题为：

12121212

max7936735,0zxxxxxxxx=+-+≤??

+≤??≥?

则单纯形法求解该松弛问题得最后一单纯形表为：

产地

销地

jc→

7

9

BCB

Xb

1x

2x

3x

4x

92x7/2017/221/22

7

1x

9/21

0-1/223/22jjCZ-

-28/11-15/11

割平面1为：234(31/2)(07/22)(01/22)xxx+=++++

3421713022222xxx?

--=-≤34571122222xxx?+-=从而有

jc→

79000BCB

Xb

1x2x3x4x5x

92x7/2017/221/22071x9/210-1/223/22

5x

-1/20

0-7/22-1/221jjCZ-

00-28/11-15/11092x3

100171x32/71001/7-1/70

3x

11/70

011/7-22/7jjCZ-

-1

-8

割平面2为：145(44/7)(01/7)(16/7)xxx+=+++-+

451541640777

xxxx?

--=--≤456164777xxx?+-=

jc→

7

9

3

BC

B

Xb1x

2x

3x

4x

5x

6x

92x3

010010

71x32/71001/7-1/7003x11/70011/7

-22/70

6x

-4/70

00-1/7-6/71jjCZ-

000-1-8092x301001071x41000-1103x10010-410

4x

4

00016-7jjCZ-

-2

-7

由上表可知该问题已经达到整数解了，所以该整数解就是原问题的最优解，即

()*4,3T

x=，最优值为max749355z=?+?=

P1445.3用图解分析法求目标规划模型

c）

解:由下图可知，满足mind1-的惬意解为区域X2CDX1；

满足mind2+的惬意解为闭区域BCDEB；满足min2d3-的惬意解为图中的A点,

满足mind4-的惬意解为图中的A点，所以该问题的惬意解为图中的点A（24，

x1+x2+d1--d1+=40

x1+x2+d2--d2+=40+10=50x1+d3--d3+=24x2+d4--d4+=30

minZ=P1d1-

+P2d2++P3（2d3-+1d4-）s.t.

x1、x2、d1+、d1-、d2+、d2-、d3+、d3-、d4+、d4-≥0

26）。

用图解分析法求目标规划模型

??

?????=≥≥=-++=-+-=-++-++=+-+

-+

-+-+

++3,2,10;0,824242min213321222111212

33211iddxxddxxddxxddxxdPdPdPzii、

的惬意解。

解：由下图可知，满足1mind+的惬意解为区域CDOA；满足3mind+的惬意解为闭区域MCDOM；

满足2mind+的惬意解为图中的阴影部分，即为图中的凸多边形OABCDO。

P1706.4求下图中的最小树

解：避圈法为：

得到最小树为：

P1716.7用标号法求下图中点1v到各点的最短路。

解：如下图所示：

P1736.14用Ford-Fulkerson的标号算法求下图中所示各容量网络中从

s

v到

t

v的

最大流，并标出其最小割集。图中各弧旁数字为容量ijc，括弧中为流量ijf.

B)

解：对上有向图举行2F标号得到

因为全部点都被标号了，即可以找到增广链，所以流量还可以调节，调节量为1，得

由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小割为与直线KK相交的弧的集合，即为

{}345