下载文档原格式
习题21图解法解下列目标规划问题：1122334min (2)f Pd P d P d d -+--=+++..s t 121140x x d d -+++-=122250x x d d -+++-=13324x d d -++-=1244430x x d d -+++-=120,0;,0,1,2,3,4i i x x d d i -+≥≥≥=P 1:AD 直线上侧，P 2:四边形ABCD,P 3:四边形ABEF ，P 4:四边形ABEF 。
故该问题的满意解为四边形ABEF 内的点，所有目标都达到了。
2用单纯形法求解以下目标规划问题的满意解：（1）1122334min (53)f Pd P d P d d -+--=+++..s t 121180x x d d -+++-=122290x x d d -+++-=13370x d d -++-=24445x d d -++-=120,0;,0,1,2,3,4i i x x d d i -+≥≥≥=（2）1122234min ()f P d d P d P d -+--=+++..s t 12114580x x d d -+++-=12224248x x d d -+++-=123381080x x d d -+++-=1445x d d -++-=120,0;,0,1,2,3,4i i x x d d i -+≥≥≥=5案例练习（1)某厂生产甲、乙两种产品，每件利润分别为20、30元。
这两种产品都要在A 、B 、C 、D 四种设备上加工，每件甲产品需，而这4种设备正常生产能力依次为每天12、8、16、12机时。
此外，A 、B 两种设备每天还可加班运行。
试拟订一个满足下列目标的生产计划： 1P ：两种产品每天总利润不低于120元；2P ：两种产品的产量尽可能均衡；3P ：A 、B 设备都应不超负荷，其中A 设备能力还应充分利用（A 比B 重要3倍）。
习 题 11 用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。
⎪⎩⎪⎨⎧≥≥+≥++=0x x 42x 4x 66x 4x 3x 2x minz )a (21212121， ⎪⎩⎪⎨⎧≥≥+≤++=0x ,x 124x 3x 2x 2x 2x 3x maxz )b (21212121⎪⎩⎪⎨⎧≤≤≤≤≤++=8x 310x 512010x 6x x x maxz )c (212121⎪⎩⎪⎨⎧≥≤+-≥-+=0x ,x 23x 2x 2x 2x 6x 5x maxz )d (21212121 答案： (a)唯一解3*,)5.0,75.0(*==z X T); (b)无可行解;(c)唯一解16*,)6,10(*==z X T); (d)无界解）2 用单纯形法求解下列线性规划问题。
⎪⎩⎪⎨⎧≥≤+≤++=0x ,x 82x 5x 94x 3x 5x 10x maxz )a (21212121 ⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+=0x ,x 5x x 242x 6x 155x x 2x maxz )b (212121221 答案：(a)唯一解5.17*,)5.1,1(*==z X T)，对偶问题5.17*,)786.1,357.0(*==w Y T; (b)唯一解5.8*,)5.1,5.3(*==z X T），5.8*,)5.0,25.0,0(*==w Y T3 用大M 法和两阶段法求解下列线性规划问题，并指出属于哪一类解。
⎪⎪⎩⎪⎪⎨⎧≥≥-≥+-≥+++-=0x x x 0x 2x 2x 2x 6x x x 2x x 2x maxz )a (3,2,13231321321 ⎪⎩⎪⎨⎧≥≥+≥++++=0x ,x ,x 62x 3x 82x 4x xx 3x 2x minz )b (32121321321答案：(a)无界解；(b)唯一解8*,)0,8.1,8.0(*==z X T)，对偶问题8*,)0,1(*==w Y T4已知线性规划问题的初始单纯形表（如表1-54所示）和用单纯形法迭代后得到的表（如表1-55所示）如下，试求括弧中未知数a ～l 的值。
习 题 11 用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。
⎪⎩⎪⎨⎧≥≥+≥++=0x x 42x 4x 66x 4x 3x 2x minz )a (21212121， ⎪⎩⎪⎨⎧≥≥+≤++=0x ,x 124x 3x 2x 2x 2x 3x maxz )b (21212121⎪⎩⎪⎨⎧≤≤≤≤≤++=8x 310x 512010x 6x x x maxz )c (212121⎪⎩⎪⎨⎧≥≤+-≥-+=0x ,x 23x 2x 2x 2x 6x 5x maxz )d (21212121 答案： (a)唯一解3*,)5.0,75.0(*==z X T); (b)无可行解;(c)唯一解16*,)6,10(*==z X T); (d)无界解）2 用单纯形法求解下列线性规划问题。
⎪⎩⎪⎨⎧≥≤+≤++=0x ,x 82x 5x 94x 3x 5x 10x maxz )a (21212121 ⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+=0x ,x 5x x 242x 6x 155x x 2x maxz )b (212121221 答案：(a)唯一解5.17*,)5.1,1(*==z X T)，对偶问题5.17*,)786.1,357.0(*==w Y T; (b)唯一解5.8*,)5.1,5.3(*==z X T），5.8*,)5.0,25.0,0(*==w Y T3 用大M 法和两阶段法求解下列线性规划问题，并指出属于哪一类解。
⎪⎪⎩⎪⎪⎨⎧≥≥-≥+-≥+++-=0x x x 0x 2x 2x 2x 6x x x 2x x 2x maxz )a (3,2,13231321321 ⎪⎩⎪⎨⎧≥≥+≥++++=0x ,x ,x 62x 3x 82x 4x x x 3x 2x minz )b (32121321321 答案：(a)无界解；(b)唯一解8*,)0,8.1,8.0(*==z X T)，对偶问题8*,)0,1(*==w Y T4已知线性规划问题的初始单纯形表（如表1-54所示）和用单纯形法迭代后得到的表（如表1-55所示）如下，试求括弧中未知数a ～l 的值。
习 题 11 用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。
⎪⎩⎪⎨⎧≥≥+≥++=0x x 42x 4x 66x 4x 3x 2x minz )a (21212121， ⎪⎩⎪⎨⎧≥≥+≤++=0x ,x 124x 3x 2x 2x 2x 3x maxz )b (21212121⎪⎩⎪⎨⎧≤≤≤≤≤++=8x 310x 512010x 6x x x maxz )c (212121⎪⎩⎪⎨⎧≥≤+-≥-+=0x ,x 23x 2x 2x 2x 6x 5x maxz )d (21212121 答案： (a)唯一解3*,)5.0,75.0(*==z X T); (b)无可行解;(c)唯一解16*,)6,10(*==z X T); (d)无界解）2 用单纯形法求解下列线性规划问题。
⎪⎩⎪⎨⎧≥≤+≤++=0x ,x 82x 5x 94x 3x 5x 10x maxz )a (21212121 ⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+=0x ,x 5x x 242x 6x 155x x 2x maxz )b (212121221 答案：(a)唯一解5.17*,)5.1,1(*==z X T)，对偶问题5.17*,)786.1,357.0(*==w Y T; (b)唯一解5.8*,)5.1,5.3(*==z X T），5.8*,)5.0,25.0,0(*==w Y T3 用大M 法和两阶段法求解下列线性规划问题，并指出属于哪一类解。
⎪⎪⎩⎪⎪⎨⎧≥≥-≥+-≥+++-=0x x x 0x 2x 2x 2x 6x x x 2x x 2x maxz )a (3,2,13231321321 ⎪⎩⎪⎨⎧≥≥+≥++++=0x ,x ,x 62x 3x 82x 4x xx 3x 2x minz )b (32121321321答案：(a)无界解；(b)唯一解8*,)0,8.1,8.0(*==z X T)，对偶问题8*,)0,1(*==w Y T4已知线性规划问题的初始单纯形表（如表1-54所示）和用单纯形法迭代后得到的表（如表1-55所示）如下，试求括弧中未知数a ～l 的值。
运筹学第三版课后习题答案运筹学是一门研究如何在有限资源下做出最优决策的学科。
它涉及到数学、统计学、经济学等多个学科的知识，可以应用于各个领域，如物流管理、生产调度、供应链优化等。
而《运筹学》第三版是一本经典的教材，它系统地介绍了运筹学的基本概念、方法和应用。
本文将针对该教材的课后习题进行解答，帮助读者更好地理解和掌握运筹学的知识。
第一章：线性规划1. 习题1.1：求解线性规划问题的常用方法有哪些？答：求解线性规划问题的常用方法包括单纯形法、对偶理论、整数规划等。
其中，单纯形法是最常用的方法，它通过迭代寻找目标函数值最小（或最大）的解。
2. 习题1.2：什么是线性规划的对偶问题？如何求解线性规划的对偶问题？答：线性规划的对偶问题是指通过原始问题的约束条件构造一个新的问题，该问题的目标是最大化（或最小化）原始问题的目标函数值。
求解线性规划的对偶问题可以使用对偶理论，通过将原始问题转化为对偶问题的等价形式，再利用对偶问题的特性进行求解。
第二章：整数规划1. 习题2.1：什么是整数规划问题？与线性规划问题有何不同？答：整数规划问题是指决策变量的取值必须为整数的线性规划问题。
与线性规划问题相比，整数规划问题的解空间更为有限，求解难度更大。
整数规划问题在实际应用中常常涉及到资源的离散分配、路径选择等问题。
2. 习题2.2：列举几个整数规划问题的应用场景。
答：整数规划问题的应用场景包括生产调度、物流路径优化、设备配置等。
例如，在生产调度中，需要确定每个生产批次的数量和时间，以最大化产能利用率和最小化生产成本。
第三章：动态规划1. 习题3.1：什么是动态规划？它的基本思想是什么？答：动态规划是一种通过将问题划分为多个子问题，并保存子问题的解来求解原问题的方法。
其基本思想是利用子问题的解构建全局最优解，从而避免重复计算和提高求解效率。
2. 习题3.2：动态规划在哪些问题中有应用？答：动态规划在最短路径问题、背包问题、序列比对等问题中有广泛的应用。
第7章网络计划7.1(1)分别用节点法和箭线法绘制表7-16的项目网络图，并填写表中的紧前工序。
(2) 用箭线法绘制表7-17的项目网络图，并填写表中的紧后工序表7-16工序 A B C D E F G紧前工序－－－ A A、C －B、D、E、F紧后工序D,E G E G G G －表7-17工序 A B C D E F G H I J K L M 紧前工序- - - B B A,B B D,G C,E,F,H D,G C,E I J,K,L 紧后工序F E,D,F,G I,K H,J I,K I H,J I L M M M－【解】（1）节点图：箭线图：（2）节点图：箭线图：7.2根据项目工序明细表7-18：（1）画出网络图。
（2）计算工序的最早开始、最迟开始时间和总时差。
（3）找出关键路线和关键工序。
表7-18工序 A B C D E F G 紧前工序- A A B,C C D,E D,E 工序时间（周）9 6 12 19 6 7 8【解】(1)网络图(2)网络参数工序 A B C D E F G最早开始0 9 9 21 21 40 40最迟开始0 15 9 21 34 41 40总时差0 6 0 0 13 1 0(3)关键路线：①→②→③→④→⑤→⑥→⑦；关键工序：A、C、D、G；完工期：48周。
7.3表7-19给出了项目的工序明细表。
表7-19工序 A B C D E F G H I J K L M N 紧前工序- - - A,B B B,C E D,G E E H F,J I,K,L F,J,L 工序时间(天) 8 5 7 12 8 17 16 8 14 5 10 23 15 12 （1）绘制项目网络图。
（2）在网络图上求工序的最早开始、最迟开始时间。
（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差。
（4）找出所有关键路线及对应的关键工序。
（5）求项目的完工期。
【解】(1)网络图（2）工序最早开始、最迟开始时间（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差 工序 tT EST EFT LST LF 总时差S 自由时差F A 8 0 8 9 17 9 0 B 5 0 5 0 5 00 C 7 0 7 7 7 0 0 D 12 8 20 17 29 9 9 E 8 5 13 5 13 0 0 F 17 7 24 7 24 0 0 G 16 13 29 13 29 0 0 H 8 29 37 29 37 0 0 I 14 13 27 33 47 20 20 J 5 13 18 19 24 6 6 K 10 37 47 37 47 0 0 L 23 24 47 24 47 0 0 M154762 47 62 0 0 N 12 47 59506233(4)关键路线及对应的关键工序关键路线有两条，第一条：①→②→⑤→⑥→⑦→○11→○12；关键工序：B,E,G ,H,K,M 第二条：①→④→⑧→⑨→○11→○12；关键工序：C,F,L,M （5）项目的完工期为62天。
7、求下列线性规划的对偶问题
121212
12121max =6050240
26..25,20z x x x x x x s t x x x x ++≤⎧⎪-+≤-⎪⎨
+≤⎪⎪≥⎩（） 12
121
2122max =24284648
9..7,0
z x x x x x s t x x x ++=⎧⎪≤⎪
⎨≤⎪⎪≥⎩（） 1234
14123413234
12343min =2632520..465223230
,,0,z x x x x x x x x x x s t x x x x x x x x x +--+≤⎧⎪
+++=⎪⎪+≥⎨⎪≤++≤⎪⎪≥⎩（）无非负要求
8、用对偶单纯形法求解
12121212
min =201056..228,0z x x x x s t x x x x ++≥⎧⎪+≥⎨⎪≥⎩
9、现有线性规划问题（共6小题）
123
123123123123max =2322153..4,,0
z x x x x x x x x x s t x x x x x x -+-+≤⎧⎪--≥-⎪⎨-+≤⎪⎪≥⎩ （1）用单纯形法求最优解和资源1、2、3的影子价格。
（2）如果
12315203442b b b ⎧⎫⎧⎫⎧⎫
⎪⎪⎪⎪⎪⎪
⎨⎬⎨⎬⎨⎬⎪⎪⎪⎪⎪⎪
⎩⎭
⎩⎭⎩⎭由变成，求最优解； （3）如果3x 的价值系数由1变为2，最优解该如何变化？ （4）如果1x 的价值系数由2变为3，最优解该如何变化？ （5）如果3x 的系数
3132333c 14231211a a a ⎧⎫⎧⎫⎧⎫
⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪
⎨⎬⎨⎬⎨⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪
⎪⎪⎪⎩⎭⎩⎭⎩⎭由变成，最优解该如何变化？
（6）如果增加一个新的约束条件1232+260x x x +≤，问最优解该如何变化？
10、某木器厂生产椅子和桌子两种产品，已知售出每把椅子可获利15元，售出一张桌子可获利30元。
在生产过程中有两个关键工序：精刨和装配，已知每只椅子需要4小时的精刨
和2小时的装配，每张桌子需要5小时的精刨和4小时的装配。
已知该厂精刨的生产能力是200小时，装配的能力是240小时。
根据市场预测椅子的最大需求量是40把，桌子的最大需求量是28张，经理希望最大产量不超过需求量。
（1）试用线性规划模型求解该厂最佳生产计划安排。
（2）假设最新市场预测表明椅子可以销售30把，桌子35张。
这样是否会改变最优生产计划安排（变化后若为小数，需运用分支定界法进一步求解）。
11、一个木材储运公司有很大的仓库用以储运出售木材。
由于木材季度价格的变化，该公司于每季度初购进木材，一部分于本季度内出售，一部分储存起来以后出售。
已知该公司
仓库的最大储存量为3
20万米，储存费用为+u （70100）元/3
万米，式中u 为储存时间（季度
数）。
已知每季度的买进卖出价及预计的销售量如表9-5所示。
由于木材不宜久储，所有库
存木材应于每年秋末售完，试建立这个问题的线性规划模型。
12、用最小费用法建立下列运输规划的初始方案，并求最优解和最小运费。
i s
20 30 50
j d 25 50 25
13、求解下列运输规划问题。
下列表中的数据是某公司的甲、乙、丙三个分厂向公司所属四个门市部运送单位产品的运费，以及甲、乙、丙三个分厂的生产量和四个门市部（1、2、3、4）的需求量。
请给出总运费最低的运输方案及最低的运费值。
14、用表上作业法求以下运输问题的最优解。
15.整数规划问题：用分支定界法求解整数规划
12
121212max 503061370
..5233
,0,z x x x x s t x x x x =++≤⎧⎪
+≤⎨⎪≥⎩且是整数。
第三章
1.计算如图9—1所示的从A 到E 的最短路线及其长度。
2.有一部货车每天沿着公路的四个零售店卸下6箱货物，如果各零售店因出售该货物所得的利润如表9—10，试求在各零售店各卸下几箱，能使获得总利润最大？其值是多少？
区设置不同数量的销售店，每月可得到的利润如表9—11所示。
试问在各个地区应如何设置销售店，才能使每月获得的总利润最大？其值是多少？
3.用破圈法或避圈法求下面图9—2的最小生成树。
图9—2
4.求解下图的最小生成树，画出该最小生成树，并给出该最小生成树的权值。
边旁的数字为该边的权值。
6.试求下面网络从S 到T 的最短路（图上数字表示距离）。
见图9-3、9-4。
图
9-3
图9-4
7.求下列网络的最大流。
图
9-5
中边上的数字为（ij f ，ij c ）。
图9-5
第一章
16. 有四个工人，要指派他们分别完成四项工作，每人做各项工作所消耗的时间如下表。
问如何分配工作可使总的消耗时间为最少？
17. 现有4台机器要安装四个不同的位置，每台机器装在不同位置的费用如下表，请制定一个总费用最少的安装计划。
第三章
1.计算下图所示的从A到E的最短路线及其长度。
2.有一部货车每天沿着公路的四个零售店卸下6箱货物，如果各零售店因出售该货物所得的利润如下表，试求在各零售店各卸下几箱，能使获得总利润最大？其值是多少？
第四章
1. 用破圈法或避圈法求图1的最小生成树。
图1
2. 求解图2的最小生成树，画出该最小生成树，并给出该最小生成树的权值。
边旁的数字为该边的权值。
图2
3. 试求下面网络从S 到T 的最短路（图上数字表示距离）。
见图3、4。
图3
图4
4.求下列网络的最大流。
图5中边上的数字为（ij f ，ij c ）。
(1)
(2)
图5。
