完整word版运筹学课后习题解答 1

1、 运筹学部分课后习题解答 P47 1.1 用图解法求解线性规划问题xmin z=2x?3216x?x?64?21 ） a?4?2xts.4x?21?0?x,x?21上的点都为，且可知线段BA解：由图1可知，该问题的可行域为凸集MABCN3 最优解，即该问题有无穷多最优解，这时的最优值为3?z0=2?3min2 用图解法和单纯形法求解线性规划问题P47 1.3 5x?max z=10x219x?3x?4? 21 a）?8x?.t5x?2s?21?0x?x,?21点为最优值点，B解：由图1可知，该问题的可行域为凸集OABCO，且可知1?x?T9?4x?x31?3?21*? 即，即最优解为1,x?3

2、?5x?2x?8x?2?212?2335?5?=10z1 这时的最优值为max22 单纯形法： 原问题化成标准型为5xmax z=10x?219x?x?4x?3? 321?8?xx?2xs.t5?412?0x?x,x,x,?42310 5 0 10 ?c jxxxXx Cb 1432BB0 1 9 3 4 0 x 31 5 8 0 0 2 x 40 0 5 10 Z?C jj0 21/5 1 0 -3/5 14/5 x 31 0 8/5 10 1/5 2/5 x 10 -2 1 0 ZC? jj0 3/2 -3/14 5 1 5/14 x 21 1 2/7 0 10 -1/7 x 1-25/1

3、4 -5/14 0 0 Z?C jj T3353?*所以有?1?51,z?10?x? ? max222? P78 2.4 已知线性规划问题：xx?x?4x?2maxz?4123x?3?x?8x?241?6x?2x?21 ?6?x?x?x?423?9?x?x?x?3120x,x?xx,?4213*)02,4X,?(2,，试根据对偶）已知原问题最优解为2求: (1) 写出其对偶问题；（ 理论，直接求出对偶问题的最优解。 解：（1）该线性规划问题的对偶问题为：y6y?9w?8y?6y?min4213y2y?2?y?241?4?y?3y?y?y?4231 ?1y?y?43?1?yy?130?,y,y,

4、yy?4312 ）由根据互补松弛性得：（2*)0,4,X2?(2,，原问题最优解为y2y?2y?214? 4y?y3y?y?4123?1y?y?43*)4,0?(2,2,X代入原线性规划问题的约束中得第四个约束取严格不等号，把0y?4?8?9?22? 即4y2y?2?21?4y?y?3y 从而有 ?312?1y?33401,y?y?,y?y? 得 41325534T*16w?,1,0)(y?, ，最优值为所以对偶问题的最优解为 min55 P79 2.7 考虑如下线性规划问题： minz?60x?40x?80x3213x?2x?x?2?312? 4?3x4x?x?321?3?2xx?2x?2?

5、312?0?,xx,x?312（1）写出其对偶问题；（2）用对偶单纯形法求解原问题； 解：（1）该线性规划问题的对偶问题为： maxw?2y?4y?3y3123y?4y?2y?60? 312? 40?y?2y2y?321?80?2yyy?3?312?0?y,yy,?312 ：把该线性规划问题化为标准型（2）在原问题加入三个松弛变量xx,x,654x8040x?z?60x?max321x?x?x?3x?2?2?4231? 4?3x?x?4x?x?5312?x?2x?2x?x?32?3126?L,61,0,j?x?j?c j-60 -40 -80 0 0 0 C BX Bb x 1x 2x 3x

6、4x 5x 60 x 4-2 -3 -2 -1 1 0 0 0 x 5-4 -4 -1 -3 0 1 0 0 x 6-3 -2 -2 -2 0 0 1 C?Z jj-60 -40 -80 0 0 0 0 x 41 0 -5/4 5/4 1 -1/12 0 80 x 11 1 1/4 3/4 0 -1/4 0 0 x6-1 0 -3/2 -1/2 0 -1/2 1 ZC?jj0 -25 -35 0 -15 0 0 x411/6 0 0 5/3 1 1/3 -5/6 80 x15/6 1 0 2/3 0 -1/3 1/6 40 x 22/3 0 1 1/3 0 1/3 -2/3 ZC? jj0 0

7、 -80/3 0 -20/3 -50/3 2305252 T*?0?80?60z?x40?(,0)?, max33636 三种产品，其所需劳动力、材料等有关数据见C、B、P81 2.12 某厂生产A的利润在什么范围A（b）产品下表。要求：（a）确定获利最大的产品生产计划；，单件劳动力消耗为Dc）如果设计一种新产品内变动时，上述最优计划不变；（ ）（d每件可获利3元，问该种产品是否值得生产？ 8单位，材料消耗为2单位，元。问该厂要不0.4 如果劳动力数量不增，材料不足时可从市场购买，每单位 要购进原材料扩大生产，以购多少为宜。 产品消 耗 额定 资源 C B A 可用量（单位）劳动力 材 料5

8、3 6 5 3 4 45 30 产品利润（元/件）3 1 4 x 种产品，从而模型为：表示第解：由已知可得，设jjx?x4?3x?maxz31245x?x?5?6x3?312 ?30x?x?4x53s.t?312?0?x,x,x?312 a) 用单纯形法求解上述模型为： 0 0 4 1 3 ?c j xXxxxxCb 51B324B0 5 1 0 6 3 45 x41 0 5 30 3 0 4 x50 3 0 4 1 Z?C jj-1 3 -1 1 0 15 0 x 44/5 4 6 0 1 1/5 3/5 x3-11/5 0 3/5 0 -4/5 Z?C jj-1/3 1/3 0 1 -1/

9、3 3 5 x 12/5 -1/5 3 4 1 0 1 x 3-3/5 -1/5 0 0 -2 Z?C jjT*273?5?4?z?3? ；最优值为得到最优解为(5,0,3)?xmax?x替代并求，则上述模型中目标函数的系数用 b）设产品A的利润为?331 解得：?c j ?31 4 0 0 C BX Bb x 1x 2x 3x 4x 53 x 15 1 -1/3 0 1/3 -1/3 4 x 33 0 1 1 -1/5 2/5 ZC? jj? -2 0 -1/5 -3/5 ?ZC? jj0 ?/3 -2+0 ?-1/5-/3 ?-3/5+/3 要最优计划不变，要求有如下的不等式方程组成立 ?

10、2?0? 3?193? 解得：?0? 5535?3?0? 35?4293? ,的利润变化范围为：即从而产品A43,?2?,3? 5555? x 表示，从已知可得C）设产品D用61?51/P?cB?c 6B6611?2? 8?33?1'?P?BP? ?4?66?212? ?5? ?55?x 把加入上述模型中求解得：6?c jXx Cb 1BB0 0 -1 -8 0 C?Z jj0 0 4 x 4 M L 3 xx 20 1 x 30 4 41 0 x 56 0 -7 3 C B9 ZC?j X B7/2 x 2 jb 0 0 x 11 7/22 0 x 21/22 0 x 30 x 40

11、 -2 x 5-7 x 63 7 由上表可知该问题已经达到整数解了，所以该整数解就是原问题的最优解，即 x 19/2 x 15 1 1 -1/22 0 -1/3 3/22 0 1/3 0 -1/3 2 4 由于有两个检验数小于零，所以需调整，调整一： 0 表x 3由于有两个检验数小于零，所以需调整，调整一：-1/2 x 57-10 3 0 0 -7/22 0 1 -1/22 1 -1/5 1 2/5 -4/5 Z?C jj 销地 销地B2 B1 产地0 C?Z jj作业代号 A B 无 紧前作业 无 0 B1 B3 -28/11 0 C D B C -2 B2 B4 -15/11 E A,D

12、0 B3 F D A,D -1/5 B4 B5 0 G H E -3/5 产量 产量 I J G,H I 1/5 K G 3 9 x 63 x 25/2 0 1/2 0 1 -1/6 0 0 1/6 1 -1/6 1 4 7 x 332/7 x 15 1 2/5 0 0 13/15 1/7 1 -1/15 -1/7 4/15 0 Z?C jj11/7 0 0 x 3-1/10 1 0 -59/30 1/7 0 -7/30 -22/7 -17/30 0 5T*2)x(0,0,5,0,0,5?/?3?5?4?27.527?z；最优值为 从而得最优解 max2 值得生产。所以产品D ）d 已知运输问

13、题的产销量与单位运价如下表所示，用表上作业法求各题P101 3.1 的最优解及最小运费。3-35 表 销地 产量BBBB 产地4 1 2 3 15 10 11 20 A2 1 25 9 A7 12 20 2 5 16 18 2 A14 3 10 销量5 15 15 解：由已知和最小元素法可得初始方案为 销地 B1 B2 B3 B4 产量 产地15 15 A1 25 0 15 10 A2 5 0 A3 5 15 销量 15 10 5 检验： 产地15 A1 15 25 A2 15 0 10 5 A3 5 0 5 15 销量15 10 检验： 由于还有检验数小于零，所以需调整，调整二： 销地 产量

14、B3 B1 B2 B4 产地15 5 A1 10 25 A2 15 10 5 5 0 A3 5 10 销量 15 15 检验： 从上表可以看出所有的检验数都大于零，即为最优方案335?18?0?11?10?1552?5?2?7?10?9?z最小运费为： min 3-36表 销地 产量BBBB 产地4 1 3 2 7 8 A1 2 4 1 25 A6 4 9 7 2 26 3 3 A5 4 3 10 10 20 销量15 43?55?b?a58，即产大于销，所以需添加一个假想的销地，销解：因为ji1?1i?j 。，构成产销平衡问题，其对应各销地的单位运费都为量为30 销地 B4 产量B5 B1

15、B2 B3 产地7 A1 0 2 4 8 1 25 A2 0 7 9 4 6 26 A3 0 3 5 3 4 15 20 10 销量 10 3 由上表和最小元素法可得初始方案为 销地 B5 B4 产量B1 B2 B3 产地7 A1 7 25 9 13 3 A2 26 1 10 15 A3 10 10 15 20 销量 3 检验： 从上表可以看出所有的检验数都大于零，即为最优方案193?3?3?15?01310?1?3?1?7?4?9?z6?5最小运费为： min 3-37 表 销地 B5 B2 B1 B3 B4 产量 产地8 A1 6 3 7 20 5 5 4 30 A2 M 8 7 6 6

16、30 A3 83 9 25 10 20 销量20 25 53?100b?a80?，即销大于产，所以需添加一个假想的产地，产解：因为ji1ji?1? 020量为，构成产销平衡问题，其对应各销地的单位运费都为。 销地 B5 B1 B4 B2 B3 产量 产地20 A1 5 8 6 7 3 30 7 M 8 4 A2 5 30 9 8 A3 3 6 6 20 A4 0 0 0 0 0 25 25 10 销量 20 20 由上表和最小元素法可得初始方案为 销地 产量B3 B4 B5 B2 B1 产地20 20 A1 30 10 15 5 A2 30 25 5 A3 20 20 A4 0 25 20 2

17、5 20 10 销量 检验： 20 20 A1 30 20 A2 10 30 5 A3 25 20 15 5 A4 0 销量25 20 25 20 10 检验： 由于还有检验数小于零，所以需调整，调整二： 销地 B5 产量B2 B1 B3 B4 产地20 A1 20 30 10 A2 20 30 25 0 A3 5 20 0 A4 20 25 25 20 20 10 销量 检验： 从上表可以看出所有的检验数都大于零，即为最优方案3050?20?0?03?25?8?0?5102020?z3?5?4?6?最小运费为： min P127 4.8 用割平面法求解整数规划问题。x97x?maxz?216

18、x3?x?21 ）a?35?x?x7?21?且为整数0,xx?21 解：该问题的松弛问题为： maxz?7x?9x21?x?3x?6?21 ?35?x7x?21?0?,xx?21则单纯形法求解该松弛问题得最后一单纯形表为： 7 9 0 0 c? j xxxXxCb 41B23B9 7/2 0 1 7/22 1/22 x2-1/22 9/2 1 7 3/22 0 x 1-28/11 0 0 -15/11 C?Z jj(3?1/2)?x?(0?7/22)x?(0?1/22)x 割平面1为：432171711 ?xx?0?x?x?x?x?3 5434232222222222 从而有 0 0 9 0

19、7 ?c j x7)/?x1/(0?/?(447)x?7)(16为：割平面2514 461614 ?x?x?0?x?4?x?x?x?x? 6514455777777 3 0 7 9 0 0 ?c j XxxxxxxCb B153246B0 1 0 3 1 0 0 9 x20 32/7 0 1 7 0 -1/7 1/7 x10 0 0 1 -22/7 1/7 0 11/7 x 31 0 -4/7 0 0 0 -1/7 -6/7 x 60 0 -1 0 -8 0 ZC? jj9 0 0 0 1 3 0 1 x 27 0 1 0 1 0 4 -1 x 10 -4 0 0 1 1 1 0 x 3T?*

20、55?4?9?3z?7?4,3?x，最优值为 max 分析法求目标规划模型 P144 5.3 用图解- -+ +1dP d+ P（2ddmin Z = P）+ 421 1323 c） -+= 40 + x+ xdd - 12 11 +-= 40+10=50 dx+ x+ d - 22 1 2+-= 24 x - + dds.t. 3 3 1 +-= 30 - d x+ d 42 4 +- +- +-+ - 0dddddddxx、 d4321211234 由下图可知，满足目标函数的满意解为图中的:解点。A 求下图中的最小树P170 6.4 解：避圈法为： 得到最小树为： v 到各点的最短路。P1

21、71 6.7 用标号法求下图中点1 解：如下图所示： vvt的的标号算法求下图中所示各容量网络中从到P 173 6.14 用Ford-Fulkersonscf. ，括弧中为流量最大流，并标出其最小割集。图中各弧旁数字为容量ijij B) 标号得到解：对上有向图进行2F ，1即可以找到增广链，所以流量还可以调整，调整量为由于所有点都被标号了， 得 由图可知，标号中断，所以已经是最大流了，最大流量等于最小割的容量，最小 相交的弧的集合，即为割为与直线KK?)v,v),(v,vv,v),(v),(,v(v,),(vvv,),( 3tst42s25s13v*vf14?25?32?1?1的最大流为： 到

22、所以从 tsst C) 标号得到解：对上有向图进行2F 1，得由于所有点都被标号了，即可以找到增广链，所以流量还可以调整，调整量为 最小割为与直线标号中断，所以已经是最大流了，最大流量等于最小割的容量，由图可知，v?v)v),(v,v,),(v(,vv的最大流为：从到，所以KK相交的弧的集合，即为ts5s3s12*135?f?53? st P193 7.1 根据下表给定的条件，绘制PERT网络图。 表7-8 作业代号 a1 a2 a3 b1 b2 b3 c1 c2 c3 无 a1 a2 无 b1 b2 a1，b1 紧前作业 a2，b2，c1 a3，b3，c2 解： 网络图为：绘制的PERT 表

23、7-9 作业代号 A B C D E F G H I J K L M 无 紧前作业 无 无 A,B B B F,C B E,H E,H C,D,F,J K L,I,G 解：绘制的PERT网络图为： LJ,K 解：绘制的PERT网络图为： 都有自己的命运与节奏，岁月如歌的谱曲与纳词，一定是你。人生不如意十之八九，有些东西，你越是在意，越会失去。一个人的生活，快乐与否，不是地位，不是财富，季节中的花开花落， 不是美貌，不是名气，而是心境。 有时候极度的委屈，想脆弱一下，想找个踏实的肩膀依靠，可是，人生沧海，那个踏实肩膀的人，也要食人间烟火，也要面对自己的不堪与无奈。岁月告诉我：当生活刁难，命运困苦， 你的内心必需单枪匹马，沉着应战。有时候真想躲起来，把手机关闭，断了所有的联系，可是，那又怎样，该面对的问