熊伟编《运筹学》习题五详细解答

《运筹学》第五章习题及答案《运筹学》第五章习题1．思考题（1）试述动态规划的“最优化原理”及它同动态规划基本方程之间的关系。

（2）动态规划的阶段如何划分？（3）试述用动态规划求解最短路问题的方法和步骤。

（4）试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值函数、边界函数等概念。

（5）试述建立动态规划模型的基本方法。

（6）试述动态规划方法的基本思想、动态规划的基本方程的结构及正确写出动态规划基本方程的关键步骤。

2．判断下列说法是否正确（1）动态规划分为线性动态规划和非线性动态规划。

（2）动态规划只是用来解决和时间有关的问题。

（3）对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。

（4）在用动态规划的解题时，定义状态时应保证各个阶段中所做的决策的相互独立性。

（5）在动态规划模型中，问题的阶段等于问题的子问题的数目。

（6）动态规划计算中的“维数障碍”，主要是由于问题中阶段数的急剧增加而引起的。

3．计算下图所示的从A到E的最短路问题4．计算下图所示的从A到E的最短路问题5．计算从A到B、C、D的最短路线。

已知各线段的长度如下图所示。

6．设某油田要向一炼油厂用管道供应油料，管道铺设途中要经过八个城镇，各城镇间的路程如下图所示，选择怎样的路线铺设，才使总路程最短？7．用动态规划求解下列各题（1）．222211295m a x x x x x z-+-=；???≥≤+0,52121x x x x；（2）．33221m a x x x x z=???≥≤++0,,6321321x x x x x x；8．某人外出旅游，需将3种物品装入背包，但背包重量有限制，总重量不超过10千克。

物品重量及其价值等数据见下表。

试问每种物品装多少件，使整个背包的价值最大？913千克。

物品重量及其价值的关系如表所示。

试问如何装这些物品，使整个背包价值最大？10量和相应单位价值如下表所示，应如何装载可使总价值最大？303011底交货量，该厂的生产能力为每月600件，该厂仓库的存货能力为300件，又每生产100件产品的费用为1000元。

运筹学（第3版）习题答案P36 P74 P88 P105 P142 P173 P195 P218 P248 P277 P304 品P343 P371全书420页第1章 线性规划工厂每月生产A 、B 、C 三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示．产品 资源 A B C 资源限量 材料(kg) 4 2500 设备(台时) 3 1400 利润(元/件)101412310和130.试建立该问题的数学模型,使每月利润最大．【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量，则数学模型为123123123123123max 1014121.5 1.2425003 1.6 1.21400150250260310120130,,0Z x x x x x x x x x x x x x x x =++++≤⎧⎪++≤⎪⎪≤≤⎪⎨≤≤⎪⎪≤≤⎪≥⎪⎩ 建筑公司需要用5m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格及数量如表1－24所示：型号A 型号B 每套窗架需要材料长度（m ） 数量(根)长度(m) 数量(根)A 1：2 2B 1： 2 A 2：3 B 2：23需要量（套）300400问怎样下料使得（1）用料最少；（2）余料最少． 【解 方案 一 二 三 四 五 六 七 八 九 十 需要量 B1 2 1 1 1 0 0 0 0 0 0 800 B2 2 0 1 0 0 2 1 1 0 0 0 1200 A1 2 0 0 1 0 0 1 0 2 1 0 600 A2120 2 3 900 余料(m) 0 1 1 1 01设x j （j =1,2,…，10）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为10112342567368947910min 28002120026002239000,1,2,,10jj j Z x x x x x x x x x x x x x x x x x x j ==⎧+++≥⎪+++≥⎪⎪+++≥⎨⎪+++≥⎪⎪≥=⎩∑ （2）余料最少数学模型为2345681012342567368947910min 0.50.50.52800212002*********0,1,2,,10j Z x x x x x x x x x x x x x x x x x x x x x x x x j =++++++⎧+++≥⎪+++≥⎪⎪+++≥⎨⎪+++≥⎪⎪≥=⎩某企业需要制定1～6月份产品A 的生产与销售计划。

附录D判断题答案(把它下载到你的电脑，编辑，把字体放大就行了线性规划1.X不一定有最优解2.V3.X不一定4.V5.V6.X是非线性规划模型，但可以转化为线性规划模型7.V8.V9.X不一定是可行基，基本可行解对应的基是可行基10.V11.V12.V13.V14.X原问题可能具有无界解15.V16.V17.V18.V19.X应为|B|工020.X存在为零的基变量时，最优解是退化的；或者存在非基变量的检验数为零时，线性规划具有多重最优解线性规划的对偶理论21.V22.V23.X不一定24.V25.X对偶问题也可能无界26.( 1) X 应为CX*> Y*b ( 2) V (3) V ( 4) V (5) V (6) V27.V28.X应为对偶问题不可行29.X应为最优值相等30.X不一定31.X影子价格是单位资源对目标函数的贡献32.X用单纯形法计算；或原问题不可行对偶问题可行时用对偶单纯形法计算33.X原问题无可行解34.X求解原问题bi I c u - bi , c35.X应为max | ir 0 b r min | ir 0i ir ir36.V37.V38.X不一定39.V40.X同时变化时最优解可能发生变化整数规划41.X取整后不一定是原问题的最优解42.X称为混和整数规划43.V44.V45.V46.V47.V48.Vn49.X应是a ij x j b i—My ij 150.V目标规划51.X正负偏差变量全部非负52.V53.V54.X至少一个等于零55.V56.X应为min Z d57.V58.X—定有满意解59.V60.V运输与指派问题61.X 唯一62.X变量应为6个63.X—定有最优解64.V65.V66.有可能变量组中其它变量构成闭回路67.V68.X有mn个约束70.X(A) = m+n — 171.V72.V73.X应为存在整数最优解，但最优解不一定是整数74.X效率应非负。

习题五5.2用元素差额法直接给出表5-53及表5-54下列两个运输问题的近似最优解.表 5-53【解】表。

Objective Vallue = 824 (Minimization)表5-54 Z=495Objective Value = 495 (Minimization)^Eritering: Source 1 to Deslinator A Leading: Source 3 to Desti5.3求表5-55及表5-56所示运输问题的最优方案.(1)用闭回路法求检验数(表5-55)（2）用位势法求检验数（表5-56）【解】（1）5.4求下列运输问题的最优解(1) C i目标函数求最小值；(2) C2目标函数求最大值3 5 9 2 50 7 10 15 20 60C1 6 4 8 5 25 C 14 13 9 6 3011 13 12 7 30 5 8 7 10 9015 45 20 40 60 30 50 40⑶目标函数最小值，B i的需求为30W b i w 50, B2的需求为40, B3的需求为20< b3W 60,A i不可达A A , B4的需求为30.4 9 7 706 5 3 2 208 4 9 10 50(3)先化为平衡表5.5 (1)建立数学模型设X j (|=l,2,3;j=1,2)为甲、乙、丙三种型号的客车每天发往 Bi, B2两城市的台班数，则maxZ 40(80x 11 65x i 2 60夠 50冷2 50x 31 40x 32) 40x 11 40x 21 40x 31 400 40x 12 40x 22 40x 32600X 11X12 5 X 11 X2210X 31X3215Xj0(i 1,2,3; j1,2)(2)写平衡运价表132333为了平衡表简单，故表中运价没有乘以 ，最优解不变(3 )最优调度方案:Z=40 (5 >80+5 >60+5 X50+10 >40) =54000 (元)5.6 (1)设X j 为第i 月生产的产品第j 月交货的台数，则此生产计划问题的数学模型为31.45X 14M X 21 L1 2345 a i1 50 1565 2251030651 2 3 4 5a i 1 1 1.15 1.3 1.45 0 65 2 M 1.25 1.4 1.55 0 65 3 M M 0.87 1.02 0 65 4 M M M 0.98 0 65b j50 40 60 80305列是虚设销地费 (2 )化为运输问题后运价表(即生产费用加上存储费用)如下，其中第用为零，需求量为 30。

判断题判断正误，如果错误请更正第五章运输与指派问题1.运输问题中用位势法求得的检验数不唯一。

2.产地数为3,销地数围的平衡运输中，变量组{Xll, X13, X22, X33, X34}可作为一组基变量。

3.不平衡运输问题不一定有最优解。

4.m+n-1个变量构成基变量组的充要条件是它们不包含闭合回路。

5.运输问题中的位势就是其对偶变量。

6.含有孤立点的变量组不包含有闭回路。

7.不包含任何闭回路的变量组必有孤立点。

& 产地个数为m销地个数为n的平衡运输问题的对偶问题有m+n个约束。

9.运输问题的检验数就是对偶问题的松弛变量的值。

10.产地个数为m销地个数为n的平衡运输问题的系数矩阵为A,则有r(A)〈=m+nT。

11.用一个常数k加到运价C的某列的所有元素上，则最优解不变。

12.令虚设的产地或销地对应的运价为一任意大于0的常数C (00),则最优解不变。

13.若运输问题中的产量或销量为整数则其最优解也一定为整数。

14.运输问题中的单位运价表的每一行都分别乘以一个非0常数，则最优解不变。

15.按最小元素法求得运输问题的初始方案，从任一非基格出发都存在唯一一个闭回路。

16.在指派问题的效率表的某行乘以一个大于零的数最优解不变。

选择题在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。

第五章运输与指派问题1.下列变量组是一个闭回路的有A{x21,xll,xl2,x32,x33,x23} B{xll,xl2,x23,x34,x41,xl3} C {x21,xl3,x34,x41,xl2} D{xl2,x32,x33,x23,x21,xll} D{xl2,x22,x32,x33,x23,x21}2.具有M个产地N个销地的平衡运输问题模型具有特征A有MN个变量M+N个约束B 有M+N个变量MN个约束C有MN个变量M+N-1个约束D有M+N-1个基变量MN-M-N+1个非基变量E系数矩阵的秩等于M+N-13.下列说法正确的有A运输问题的运价表第r行的每个cij同时加上一个非0常数k, 其最优调运方案不变。

习题七7.2(1)分别用节点法和箭线法绘制表7-16的项目网络图，并填写表中的紧前工序。

(2) 用箭线法绘制表7-17的项目网络图，并填写表中的紧后工序表7-16表7-17【解】（1）箭线图：节点图：（2）箭线图：7.3根据项目工序明细表7-18：（1）画出网络图。

（2）计算工序的最早开始、最迟开始时间和总时差。

（3）找出关键路线和关键工序。

表7-18【解】(1)网络图(2)网络参数(3)关键路线：①→②→③→④→⑤→⑥→⑦；关键工序：A、C、D、G；完工期：48周。

7.4 表7-19给出了项目的工序明细表。

表7-19（2）在网络图上求工序的最早开始、最迟开始时间。

（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差。

（4）找出所有关键路线及对应的关键工序。

（5）求项目的完工期。

【解】(1)网络图（2）工序最早开始、最迟开始时间（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差工序t T ES T EF T LS T LF 总时差S 自由时差FA 8 0 89 1790B 5 0 50 500C 7 0 77 700D 12 8 2017 2999E 8 5 13 5 1300F 17 7 247 2400G 16 13 2913 2900H 8 29 3729 3700I 14 13 2733 472020J 5 13 1819 246 6K 10 37 4737 4700L 23 24 4724 4700M 15 47 6247 6200N 12 47 5950 623 3(4)关键路线及对应的关键工序关键路线有两条，第一条：①→②→⑤→⑥→⑦→○11→○12；关键工序：B,E,G,H,K,M 第二条：①→④→⑧→⑨→○11→○12；关键工序：C,F,L,M（5）项目的完工期为62天。

7.5已知项目各工序的三种估计时间如表7-20所示。

求：表7-20（1）绘制网络图并计算各工序的期望时间和方差。

运筹学答案（熊伟）下习题七7.2(1)分别用节点法和箭线法绘制表7-16的项目网络图，并填写表中的紧前工序。

(2)用箭线法绘制表7-17的项目网络图，并填写表中的紧后工序表7-16工序ABCDEFG－IC,E,F,HJD,GKC,ELIMJ,K,L紧前工序－－－ACAF、D、B、E表7-17紧后工序D,EGEGGG工序紧前工序A-B-C-DBEBFA,BGBHD,G紧后工序FE,D,F,GI,H,I,H,IIKJKJMLMM－【解】（1）箭线图：节点图：（2）箭线图：7.3根据项目工序明细表7-18：（1）画出网络图。

（2）计算工序的最早开始、最迟开始时间和总时差。

（3）找出关键路线和关键工序。

表7-18工序紧前工序A-BA6CA12DB,C19EC6FD,E7GD,E8工序时间（周）9【解】(1)网络图(2)网络参数工序A000B9156C990D21210E213413F40411G40400最早开始最迟开始总时差(3)关键路线：①→②→③→④→⑤→⑥→⑦；关键工序：A、C、D、G；完工期：48周。

7.4表7-19给出了项目的工序明细表。

表7-19工序紧前工序ABC--5-7D12E8F17GE16HD,G8IEJKLM15N12A,BBB,CEHF,JI,K,LF,J,L工序时间(天)81451023（1）绘制项目网络图。

（2）在网络图上求工序的最早开始、最迟开始时间。

（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差。

（4）找出所有关键路线及对应的关键工序。

（5）求项目的完工期。

【解】(1)网络图（2）工序最早开始、最迟开始时间（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差工序tTESTEFTLSTLF总时差S自由时差FA80891790B5050500C7077700D12820172999E851351300F1772472400G1613 29132900H82937293700I14132733472020J51318192466K103747374700L232 447244700M154762476200N124759506233(4)关键路线及对应的关键工序11→○12；关键工序：B,E,G,H,K,M关键路线有两条，第一条：①→②→⑤→⑥→⑦→○11→○12；关键工序：C,F,L,M第二条：①→④→⑧→⑨→○（5）项目的完工期为62天。

运筹学(第2版)习题答案1--3习题一1.1讨论下列问题：(1)在例1.2中，如果设X j(j=l , 2,…，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化.(2)在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路.(3)在例1.4中，若允许含有少量杂质，但杂质含量不超过1%,模型如何变化.(4)在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化.⑸在单纯形法中，为什么说当k o并且a ik 0(i 1,2,L ,m)时线性规划具有无界解。

1.2工厂每月生产A、B、C三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表 1 - 23所示.表1-23根据市场需求，预测三种产品最低月需求量分别是150、260和120，最高月需求是250、310和130 •试建立该问题的数学模型，使每月利润最大.【解】设X1、X2、X3分别为产品A、B、C的产量，则数学模型为maxZ 10 x-! 14x212x31.5x 11.2 X2 4x3 25003x1 1.6x21.2X3 1400150 % 250260 X2 310120 X3 130为，,x3 01.3建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架•两种窗架所需材料规格及数量如表1 —24所示：问怎样下料使得(1)用料最少；(2)余料最少. 【解】第一步：求下料方案，见下表。

第二步：建立线性规划数学模型设X j (j=1,2, ••,• 14)为第j 种方案使用原材料的根数，则 (1)用料最少数学模型为14min Zj X j12为 X 2 X 3 X 4 300X2 3X 5 2X 6 2X7 X8%X 10450 X 3 X 2x 8 X 3X 11 2X I 2 为3400X 2 X 3 2X 4 X 7 X 93X10 2X123X 13 4为4600X j 0,j 1,2 ,L ,14用单纯形法求解得到两个基本最优解X ⑴=(50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534X ⑵=(0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 );Z=534 (2)余料最少数学模型为minZ 0.6X 10.3X 3 0.7X 4L0.4X 13 0.8X i42X 1 X 2 X 3 X 4300X 2 3X 5 2X 6 2X 7 X X 9 X i0450X 3 X 6 2X 8 X 3X ii 2X 12X 13400X 2 X 3 2X 4 X 7 X 9 3X i0 2X123X134X 14 600X j 0, j 1,2,L ,14用单纯形法求解得到两个基本最优解X ⑴=(0 ,300 ,0 ,0,50 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料 550 根X (2)=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料 650 根 显然用料最少的方案最优。

运筹学（第2版）习题答案1--3习题一1.1 讨论下列问题：（1）在例1.2中，如果设x j (j=1，2，…，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化．（2）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路． （3）在例1.4中，若允许含有少量杂质，但杂质含量不超过1％，模型如何变化．（4）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化．(5)在单纯形法中，为什么说当00(1,2,,)k ik a i m λ>≤=并且时线性规划具有无界解。

1.2 工厂每月生产A 、B 、C 三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示．根据市场需求,试建立该问题的数学模型,使每月利润最大．【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量，则数学模型为1.3 建筑公司需要用6m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格及数量如表1－24所示：问怎样下料使得（1【解】 设x j （j =1,2,…，14）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为用单纯形法求解得到两个基本最优解X (1)=( 50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534 X (2)=( 0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 );Z=534 （2）余料最少数学模型为用单纯形法求解得到两个基本最优解X (1)=( 0 ,300 ,0 ,0,50 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料550根 X (2)=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料650根 显然用料最少的方案最优。

运筹学第五章课后习题答案运筹学第五章课后习题答案运筹学是一门研究如何进行有效决策和优化问题的学科。

在运筹学的学习过程中，课后习题是非常重要的一部分，通过解答习题可以帮助我们巩固所学的知识，并且加深对运筹学理论的理解。

本文将给出运筹学第五章的课后习题答案，希望对大家的学习有所帮助。

1. 线性规划问题是运筹学中最基本的问题之一。

以下是一道线性规划问题的习题：Maximize 2x + 3ySubject to:x + y ≤ 102x + y ≤ 15x, y ≥ 0解答：首先，我们需要将目标函数和约束条件转化为标准形式。

将目标函数改写为最小化形式，即 Minimize -2x - 3y。

然后，我们引入松弛变量，将不等式约束转化为等式约束，得到以下形式的线性规划问题：Minimize -2x - 3ySubject to:x + y + s1 = 102x + y + s2 = 15x, y, s1, s2 ≥ 0接下来，我们可以使用单纯形法或者图解法来求解这个线性规划问题。

通过计算或者画图，我们可以得到最优解为 x = 5, y = 5，目标函数的最大值为 25。

2. 整数规划是线性规划的一种扩展形式，其中变量的取值限制为整数。

以下是一道整数规划问题的习题：Maximize 3x + 2ySubject to:x + y ≤ 5x, y ≥ 0x, y 是整数解答：这是一个整数规划问题，我们需要找到满足约束条件的整数解，并求解出目标函数的最大值。

通过穷举法，我们可以得到以下整数解：当 x = 2, y = 3 时，目标函数的值为 13；当 x = 3, y = 2 时，目标函数的值为 12；当 x = 4, y = 1 时，目标函数的值为 11；当 x = 5, y = 0 时，目标函数的值为 10。

综上所述，目标函数的最大值为 13，对应的整数解为 x = 2, y = 3。

3. 0-1整数规划是整数规划的一种特殊形式，其中变量的取值限制为0或1。