运筹学课后习题答案__林齐宁版本__北邮出版社

运筹学部分课后习题解答P47 1.1用图解法求解线性规划问题min z=2x 3x24为6x2 _ 6st ]4x1+2x2>4X i,X2 _0解：由图1可知，该问题的可行域为凸集MABC,且可知线段BA上的点都为3最优解，即该问题有无穷多最优解，这时的最优值为％=2 - 3P47 1.3用图解法和单纯形法求解线性规划问题max z=10x1 5x213为4x2乞9a )s.t」5为+2x2兰8x1, x^ 0解：由图1可知，该问题的可行域为凸集OABCO且可知B点为最优值点,即严+4卷=9斗|人3，即最优解为x」1,3(5X1 +2X2 =8 & =2 I 2丿这时的最优值为Z max = 10 1 5 -2 2原问题化成标准型为max z=10x1 5x23\ 4x2 x3 = 9 s.t <5^+2x2 +x4 =8X i,X2,X3,X4 —0z所以有—1,3 ,Z max=10 1 5I 2 丿 2 2P78 2.4已知线性规划问题：max z =2x 4x2x3x4/+3X2+x4兰82咅+x2<6彳x2+X3 +x4兰6X,+ x2+ X3<9XZX, X4 一0求：(1)写出其对偶问题；(2)已知原问题最优解为X^(2,2,410)，试根据对偶理论，直接求出对偶问题的最优解。

解：(1)该线性规划问题的对偶问题为：min w =8y, 6y26y39y4\i+2y2 +y4 兰23yr H y<H yr H y^4彳y^y^iy i, y2,y3,y4—0(2)由原问题最优解为X* =(2,2,4,0)，根据互补松弛性得：y1 2y2 y4 = 23y1 y2 y a y^4I y a + yU把X* = (2,2,4,0)代入原线性规划问题的约束中得第四个约束取严格不等号，即 2 2 4 =8 < 9 - y4=0y1 2y2 =2从而有+y2 +y a =4L ya =1得Y1 ,Y2 ,Y a = 1,y4 = 05 5所以对偶问题的最优解为y* =(4,3,1,0)T，最优值为W min =165 5P79 2.7考虑如下线性规划问题:min z = 60x i 40x2 80x3” 3x i + 2x2 + X3 兰24x i + X2 + 3x^ > 42x i +2X2 +2x3 兰3x i,x?,x^ >0(1)写出其对偶问题；(2)用对偶单纯形法求解原问题;解：(1)该线性规划问题的对偶问题为:max w = 2% 4y2 3y33% +4y2 +2y3 W60』2% +y2 +2y3 玄40y i 3y2 2y3 — 80[y i,y2,y^0(2)在原问题加入三个松弛变量X4,X5,X6把该线性规划问题化为标准型max z = -60旨-40X2-80X3—3x i — 2x? — X3 + X4 = -2~4x<i — x? — 3X3 + X5 ——4-2 X i — 2 X2 — 2 X3 + = _3X j "j =1川,6x* 5,?,O)T,Z max =60 540 - 80 06 3 6 3 3P81 2.12某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见下表。

《运筹学》习题答案一、单选题1.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（）BA.任意网络B.无回路有向网络C.混合网络D.容量网络2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（）BA.非线性问题的线性化技巧B.静态问题的动态处理C.引入虚拟产地或者销地D.引入人工变量3.静态问题的动态处理最常用的方法是？BA.非线性问题的线性化技巧B.人为的引入时段C.引入虚拟产地或者销地D.网络建模4.串联系统可靠性问题动态规划模型的特点是（）DA.状态变量的选取B.决策变量的选取C.有虚拟产地或者销地D.目标函数取乘积形式5.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( )。

CA.降低的B.不增不减的C.增加的D.难以估计的6.最小枝权树算法是从已接接点出发，把( )的接点连接上CA.最远B.较远C.最近D.较近7.在箭线式网络固中，( )的说法是错误的。

DA.结点不占用时间也不消耗资源B.结点表示前接活动的完成和后续活动的开始C.箭线代表活动D.结点的最早出现时间和最迟出现时间是同一个时间8.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。

CA.1200B.1400C.1300D.17009.在求最短路线问题中，已知起点到A，B，C三相邻结点的距离分别为15km，20km,25km，则（）。

DA.最短路线—定通过A点B.最短路线一定通过B点C.最短路线一定通过C点D.不能判断最短路线通过哪一点10.在一棵树中，如果在某两点间加上条边，则图一定( )AA.存在一个圈B.存在两个圈C.存在三个圈D.不含圈11.网络图关键线路的长度( )工程完工期。

CA.大于B.小于C.等于D.不一定等于12.在计算最大流量时，我们选中的每一条路线( )。

CA.一定是一条最短的路线B.一定不是一条最短的路线C.是使某一条支线流量饱和的路线D.是任一条支路流量都不饱和的路线13.从甲市到乙市之间有—公路网络，为了尽快从甲市驱车赶到乙市，应借用（）CA.树的逐步生成法B.求最小技校树法C.求最短路线法D.求最大流量法14.为了在各住宅之间安装一个供水管道．若要求用材料最省，则应使用( )。

《运筹学》课后答案《运筹学》是一门研究如何在有限资源下做出最佳决策的学科，它涉及到数学、统计学、经济学等多个学科的知识。

掌握运筹学的方法和技巧对于解决实际问题具有重要意义。

下面是《运筹学》课后习题的答案：1. 什么是线性规划问题？线性规划问题是指在一组线性约束条件下，求解一个线性目标函数的最优值的问题。

线性规划问题具有优化的特点，即找到一组满足约束条件的解，使得目标函数取得最大（最小）值。

2. 线性规划问题的标准形式是什么？线性规划问题的标准形式是指将目标函数和约束条件都写成标准形式，即目标函数为最大化（最小化）一个线性函数，约束条件为一组线性不等式和线性等式。

3. 线性规划问题的解的存在性和唯一性是什么？线性规划问题的解的存在性和唯一性是由线性规划问题的特殊结构决定的。

如果线性规划问题有有界解（即目标函数有最大（最小）值），则存在解；如果线性规划问题的目标函数有最大（最小）值，且该最大（最小）值只有一个解，则解是唯一的。

4. 什么是单纯形法？单纯形法是一种解线性规划问题的常用方法，它通过迭代计算来逐步接近最优解。

单纯形法的基本思想是从一个初始可行解出发，通过一系列变换（包括基变换、基可行解的改进等）来逐步接近最优解。

5. 什么是对偶理论？对偶理论是线性规划问题的一个重要理论基础，它通过将原问题转化为对应的对偶问题来研究线性规划问题。

对偶理论可以帮助我们理解线性规划问题的性质和结构，并且可以通过对偶问题的解来得到原问题的解。

6. 什么是整数规划问题？整数规划问题是指在线性规划问题的基础上，将决策变量的取值限制为整数的问题。

整数规划问题具有更为复杂的性质，其解的搜索空间更大，求解难度更大。

7. 什么是分支定界法？分支定界法是解整数规划问题的一种常用方法，它通过将整数规划问题分解为一系列线性规划子问题，通过不断分支和约束来逐步缩小解的搜索空间，最终找到最优解。

8. 什么是动态规划？动态规划是一种解决多阶段决策问题的方法，它通过将问题分解为一系列子问题，并且利用子问题的解来构建整体问题的解。

运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题min z=2x1 3x2a4x1 6x2 6 ）2x2 4 st.. 4x1x1, x2 0解：由图 1 可知，该问题的可行域为凸集 MABCN，且可知线段 BA上的点都为最优解，即该问题有无量多最优解，这时的最优值为3z min =23 0 3 2P47 1.3 用图解法和纯真形法求解线性规划问题max z=10x1 5x 2a ）3x1 4x2 95x1 2x2 8st..x1, x2 0解：由图 1 可知，该问题的可行域为凸集OABCO，且可知 B 点为最优值点，3x1 4x2x1 1 T 9 3，即最优解为x*1,3即2x2 8x2 2 5x1 2这时的最优值为 z max =10 1 5 3 35 2 2纯真形法：原问题化成标准型为max z=10x15x23x1 4 x2x39st.. 5x12x2x48x1 , x2 , x3 ,x4 010 5 0 0c jC B X B b x1 x2 x3 x49 3 4 1 0x38 [5] 2 0 1x410 5 0 0C j Z j21/5 0 [14/5] 1 -3/5 x38/5 1 2/5 0 1/5 10x10 1 0 -2C j Z j53/2 0 1 5/14 -3/14 x21 1 0 -1/7 2/7 10x10 0 -5/14 -25/14C j Z j1,3 T1015335因此有 x*, zmax2 2 2P78 2.4 已知线性规划问题：max z 2 x1 4x2 x3 x4x1 3x2 x4 82x1 x2 6x2 x3 x4 6x1 x2 x3 9x1 , x2 , x3,x4 0求: (1) 写出其对偶问题；（2）已知原问题最优解为X* (2,2,4,0) ，试依据对偶理论，直接求出对偶问题的最优解。

解：（ 1）该线性规划问题的对偶问题为：min w 8 y1 6 y2 6 y3 9 y4y1 2 y2 y4 23y1 y2 y3 y4 4y3 y4 1y1 y3 1y1, y2 , y3 ,y4 0（2）由原问题最优解为X* ( 2,2,4,0) ，依据互补废弛性得：y1 2 y2 y4 23y1 y2 y3 y4 4y3 y4 1把 X * (2,2,4,0) 代入原线性规划问题的拘束中得第四个拘束取严格不等号，即 2 2 4 8 9 y4 0y1 2 y2 2进而有3y1 y2 y3 4y3 1得 y 4 , y2 3, y31, y 01 5 5 4( 4,3,1,0)T，最优值为w min16因此对偶问题的最优解为y*5 5P79 2.7考虑以下线性规划问题：min z 60x140x280x33x12x2x3 24x1x23x3 42x12x22x3 3x1, x2 , x30（ 1）写出其对偶问题；（ 2）用对偶纯真形法求解原问题；解：（ 1）该线性规划问题的对偶问题为：max w 2y1 4 y23y33y1 4 y2 2 y3602 y1 y22y340y13y22y380y1, y2 , y30（2）在原问题加入三个废弛变量x4 , x5 , x6把该线性规划问题化为标准型：max z 60x1 40x2 80x33x1 2x2 x3 x4 24x1 x2 3x3 x5 42 x1 2x2 2x3 x6 3x j 0, j 1, ,6c j-60 -40 -80 0 0 0 C B X B b x1 x2 x3 x4 x5 x6x4-2 -3 -2 -1 1 0 0x5-4 [-4] -1 -3 0 1 0x6-3 -2 -2 -2 0 0 1 C j Z j-60 -40 -80 0 0 0x41 0 -5/4 5/4 1 -1/12 080x11 1 1/4 3/4 0 -1/4 0x6-1 0 [-3/2] -1/2 0 -1/2 1C j Zj0 -25 -35 0 -15 0x411/6 0 0 5/3 1 1/3 -5/680x15/6 1 0 2/3 0 -1/3 1/640x22/3 0 1 1/3 0 1/3 -2/3C j Zj0 0 -80/3 0 -20/3 -50/3x* ( 5 , 2 ,0) T , z max 60 5 40 2 80 0 2306 3 6 3 3P81 2.12某厂生产A、B、C三种产品，其所需劳动力、资料等相关数据见下表。

运筹学（第2版）习题答案2第1章 线性规划 P36~40第2章 线性规划的对偶理论 P68~69 第3章 整数规划 P82~84 第4章 目标规划 P98~100 第5章 运输与指派问题 P134~136 第6章 网络模型 P164~165 第7章 网络计划 P185~187 第8章 动态规划 P208~210 第9章 排队论 P239~240 第10章 存储论 P269~270 第11章 决策论 Pp297－298 第12章 博弈论 P325~326 全书360页由于大小限制，此文档只显示第6章到第12章，第1章至第5章见《运筹学课后答案1》习题六6.1如图6－42所示，建立求最小部分树的0－1整数规划数学模型。

【解】边[i ，j ]的长度记为c ij ，设⎩⎨⎧=否则包含在最小部分树内边0],[1j i x ij数学模型为：,12132323243434364635365612132434343546562324463612132446362335244656121324354656m in 52,22,233344,510ij ijij i j ij Z c x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ==++≤++≤++≤++≤+++≤+++≤+++≤++++≤++++≤+++++≤=∑或,[,]i j ⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩所有边6.2如图6－43所示，建立求v 1到v 6的最短路问题的0－1整数规划数学模型。

图6－42【解】弧(i ，j )的长度记为c ij ，设⎩⎨⎧=否则包含在最短路径中弧0),(1j i x ij数学模型为：,1213122324251323343524344546253545564656m in 100,00110,(,)ijiji jij Z cx x x x x x x x x x x x x x x x x x x x x x i j =⎧+=⎪---=⎪⎪+--=⎪⎪+--=⎨⎪++-=⎪⎪+=⎪=⎪⎩∑或所有弧 6.3如图6－43所示，建立求v 1到v 6的最大流问题的线性规划数学模型。

第五版运筹学课后习题答案【篇一：运筹学课后习题答案林齐宁版本北邮出版社】>1、某织带厂生产a、b两种纱线和c、d两种纱带，纱带由专门纱线加工而工厂有供纺纱的总工时7200h，织带的总工时1200h。

(1) 列出线性规划模型，以便确定产品的数量使总利润最大；(2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？解：(1)设a的产量为x1，b的产量为x2，c的产量为x3，d的产量为x4，则有线性规划模型如下：max f(x)=(168?42)x1 +(140?28)x2 +(1050?350)x3 +(406?140)x4=126 x1 +112 x2 +700 x3 +266 x4?3x1?2x2?10x3?4x4?7200?s.t. ? 2x3?0.5x4?1200?xi?0, i?1,2,3,4?(2)如果组织这次生产有一次性的投入20万元，由于与产品的生产量无关，故上述模型只需要在目标函数中减去一个常数20万，因此可知对模型的解没有影响。

2、将下列线性规划化为极大化的标准形式minf(x)?2x1?3x2?5x3解：将约束条件中的第一行的右端项变为正值，并添加松弛变量x4，在第二行添加人工变量? x1? x2? x3??5 ???6x1?7x2?9x3?16 x5，将第三行约束的绝对值号打开，变为两s.t. ?|19x1?7x2?5x3|?13个不等式，分别添加松弛变量x6, x7，并令??x,x?0, x?不限3?12x3?x3??x3??，则有max[?f(x)]= {?2 x1 ?3 x2 ?5(x3??x3??)+0 x4 ?m x5+0 x6 +0 x7} ?? x3???x4?5 ?x1 ?x2 ?x3 ???6x?7x?9x??9x?? ?x?1612335????5x3?? ?x6?13 s.t. ? 19x1?7x2?5x3??19x?7x?5x??5x?? ?x7?131233??,x3??,x4,x5,x6,x7?0?x1,x2,x3?3、用单纯形法解下面的线性规划maxf(x)?2x1?5x2?3x3?3x1?2x2?x3?610??x?6x?3x?125 ?123s. t. ???2x1?x2?0.5x3?420?x1,x2,x3?0, ?解：在约束行1,2,3分别添加x4, x5, x6松弛变量，有初始基础可行解和单纯形答：最优解为x1 =244.375, x2 =0, x3 =123.125, 剩余变量x6=847.1875；最优解的目标函数值为858.125。

运筹学课后习题及答案运筹学是一门应用数学的学科，旨在通过数学模型和方法来解决实际问题。

在学习运筹学的过程中，课后习题是非常重要的一部分，它不仅可以帮助我们巩固所学的知识，还可以提升我们的解决问题的能力。

下面，我将为大家提供一些运筹学课后习题及答案，希望对大家的学习有所帮助。

1. 线性规划问题线性规划是运筹学中的一个重要分支，它旨在寻找线性目标函数下的最优解。

以下是一个线性规划问题的例子：Max Z = 3x + 4ySubject to:2x + 3y ≤ 10x + y ≥ 5x, y ≥ 0解答：首先，我们可以画出约束条件的图形，如下所示：```y^|5 | /| /| /| /|/+-----------------10 x```通过观察图形，我们可以发现最优解点是(3, 2)，此时目标函数取得最大值为Z = 3(3) + 4(2) = 17。

2. 整数规划问题整数规划是线性规划的一种扩展，它要求变量的取值必须是整数。

以下是一个整数规划问题的例子：Max Z = 2x + 3ySubject to:x + y ≤ 52x + y ≤ 8x, y ≥ 0x, y为整数解答：通过计算，我们可以得到以下整数解之一：x = 2, y = 3此时，目标函数取得最大值为Z = 2(2) + 3(3) = 13。

3. 网络流问题网络流问题是运筹学中的另一个重要分支，它研究的是在网络中物体的流动问题。

以下是一个网络流问题的例子：有一个有向图，其中有三个节点S、A、B和一个汇点T。

边的容量和费用如下所示：S -> A: 容量为2，费用为1S -> B: 容量为3，费用为2A -> T: 容量为1，费用为1B -> T: 容量为2，费用为3A -> B: 容量为1，费用为1解答：通过使用最小费用最大流算法，我们可以找到从源点S到汇点T的最小费用流量。

在该例中，最小费用为5，最大流量为3。

运筹学（第2版）习题答案2第1章 线性规划 P36~40第2章 线性规划的对偶理论 P68~69 第3章 整数规划 P82~84 第4章 目标规划 P98~100 第5章 运输与指派问题 P134~136 第6章 网络模型 P164~165 第7章 网络计划 P185~187 第8章 动态规划 P208~210 第9章 排队论 P239~240 第10章 存储论 P269~270 第11章 决策论 Pp297－298 第12章 博弈论 P325~326 全书360页由于大小限制，此文档只显示第6章到第12章，第1章至第5章见《运筹学课后答案1》习题六6.1如图6－42所示，建立求最小部分树的0－1整数规划数学模型。

【解】边[i ，j ]的长度记为c ij ，设⎩⎨⎧=否则包含在最小部分树内边0],[1j i x ij数学模型为：,12132323243434364635365612132434343546562324463612132446362335244656121324354656m in 52,22,233344,510ij ijij i j ij Z c x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ==++≤++≤++≤++≤+++≤+++≤+++≤++++≤++++≤+++++≤=∑或,[,]i j ⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩所有边6.2如图6－43所示，建立求v 1到v 6的最短路问题的0－1整数规划数学模型。

图6－42【解】弧(i ，j )的长度记为c ij ，设⎩⎨⎧=否则包含在最短路径中弧0),(1j i x ij数学模型为：,1213122324251323343524344546253545564656m in 100,00110,(,)ijiji jij Z cx x x x x x x x x x x x x x x x x x x x x x i j =⎧+=⎪---=⎪⎪+--=⎪⎪+--=⎨⎪++-=⎪⎪+=⎪=⎪⎩∑或所有弧 6.3如图6－43所示，建立求v 1到v 6的最大流问题的线性规划数学模型。

No .1 线性规划1、某织带厂生产A 、B 两种纱线和C 、D 两种纱带，纱带由专门纱线加工而成。

这四种产品的产值、成本、加工工时等资料列表如下： 产品 项目ABCD单位产值 (元) 168 140 1050 406 单位成本 (元) 42 28 350 140 单位纺纱用时 (h) 3 2 10 4 单位织带用时 (h)20.5工厂有供纺纱的总工时7200h ，织带的总工时1200h 。

(1) 列出线性规划模型，以便确定产品的数量使总利润最大；(2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？ 解：(1)设A 的产量为x 1，B 的产量为x 2，C 的产量为x 3，D 的产量为x 4，则有线性规划模型如下：max f (x )=(16842)x 1 +(14028)x 2 +(1050350)x 3 +(406140)x 4=126 x 1 +112 x 2 +700 x 3 +266 x 4s.t. ⎪⎩⎪⎨⎧=≥≤+≤+++4,3,2,1 ,012005.02 720041023434321i x x x x x x x i(2)如果组织这次生产有一次性的投入20万元，由于与产品的生产量无关，故上述模型只需要在目标函数中减去一个常数20万，因此可知对模型的解没有影响。

2、将下列线性规划化为极大化的标准形式解：将约束条件中的第一行的右端项变为正值，并添加松弛变量x 4，在第二行添加人工变量x 5，将第三行约束的绝对值号打开，变为两个不等式，分别添加松弛变量x 6, x 7，并令x x x 333='-''，则有max[f (x )]= {2 x 13 x 2 5('-''x x 33)+0 x 4M x 5+0 x 6 +0 x 7}s.t. 0,,,,,,,13 55719 13 55719 16 9976 5 7654332173321633215332143321≥'''=+''+'-+-=+''-'+-=+''+'-+-=+''-'+--⎪⎪⎪⎩⎪⎪⎪⎨⎧x x x x x x x x x x x x x x x x x x x x x x x x x x x x ⎪⎪⎩⎪⎪⎨⎧±≥≤+-=-+--≥-+++=不限321321321321321 ,0,13|5719|169765 ..532)(m in x x x x x x x x x x x x t s x x x x f3、用单纯形法解下面的线性规划⎪⎪⎩⎪⎪⎨⎧≥≤++-≤++-≤-+++= ,0,,4205.021********* ..352)(max 321321321321321x x x x x x x x x x x x t s x x x x f 解：在约束行1,2,3分别添加x 4, x 5, x 6松弛变量，有初始基础可行解和单纯形法迭代步骤如下：C j1 12 z jC j2 1/3 1/6 11/6 1/6 z j5/6 5/6 C j3/5 1/1011/107/20z j11/20 C jz j11/ 29/811/8答：最优解为x1 =244.375, x2 =0, x3 =123.125, 剩余变量x6 =847.1875；最优解的目标函数值为858.125。

No .2 两阶段法和大M 法 解：将原问题变为第一阶段的标准型⎪⎩⎪⎨⎧≥=+-+=+-+--⋅+⋅=0,,,,,753802 ..00)(max 654321642153216521x x x x x x x x x x x x x x t s x x x x x f答：最优解为x 1 =14，x 2 =33，目标函数值为254。

No .3 线性规划的对偶问题 3、用对偶单纯形法求下面问题⎪⎩⎪⎨⎧≥≥+≥++=0,753802 ..64)(min 21212121x x x x x x t s x x x f1、用两阶段法解下面问题：⎪⎩⎪⎨⎧≥≥+≥++=0,753802 ..64)(min 21212121x x x x x x t s x x x f答：最优解为x1 =14，x2 =33，目标函数值为254。

No.5 运输问题1、分别用西北角法、最低费用法和运费差额法，求下面运输问题(见表)的初始可行解，并计算其目标函数。

(可不写步骤)2、以上题中最低费用法所得的解为初始基础可性解，用表上作业法（踏石法）求出最优解。

（要求列出每一步的运费矩阵和基础可行解矩阵）OBJ ＝955 ⇓)4 (15) 4 -7 10 -7 -3 12 -6 -3 9 640 10 8 1 4 5 5 20 6 9 6答：x 13=5, x 14=15, x 24=30, x 32=15, x 33=25,x 41=25, x 43=5, x 45=30, OBJ=850。

习题课11、某工厂生产用2单位A 和1单位B 混合而成的成品出售，市场无限制。

A 和B 可以在该工厂的3个车间中的任何车间生产，生产每单位的A 和B 试建立使成品数量最大的线性规划模型。

解：设车间1生产x 1A 单位A 、生产x 1B 单位B ；设车间2生产x 2A 单位A 、生产x 2B 单位B ； 设车间3生产x 3A 单位A 、生产x 3B 单位B ； 则有生产安排最优化的模型如下：OBJ ＝850OBJ ＝850⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥++≥++≤+≤+≤+++=3,2,1,0,)(21005.15.112021002..)(max 321321332211321i x x x x x x x x x x x x x x t s x x x x f iB iA B B B A A A B A B A B A BB B 这是一个可分解的线性规划，这类问题就容易出现退化现象。

1.1 （1）无界解；（2）无解；（3）唯一最优解（15，8）；（4）无界解1.2 （1）令z z -='，444x x x ''-'=，则该问题的标准形式为 65443210055243max x x x x x x x z ++''+'-+-=' ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥'''=-''+'-++-=+''-'+-+=''-'+-+-0,,,,,,2321422224654432164432154432144321x x x x x x x x x x x x x x x x x x x x x x x x （2）令z z -='，11x x -='，333x x x ''-'=，则该问题的标准形式为 4332103322max x x x x x z +''+'-+'=' ⎪⎪⎩⎪⎪⎨⎧≥''''=+''+'-+'=''-'++'0,,,,62443321433213321x x x x x x x x x x x x x x 1.4 （1）顶点：O （0，0）；A （0，2.25）；B （1，1.5）；C （1.6，0）有唯一最优解（1，1.5），此时z=17.5；（2）顶点：A （0，0）；B （0，3）；C （3.75，0.75）；D （4，0） 有唯一最优解（3.75，0.75），此时z=8.251.51.6 由L 和分别解出其下界和上界214max :x x z L +=' 2163max :x x z L +='⎪⎪⎩⎪⎪⎨⎧≥≤+≤+0,1065853212121x x x x x x ⎪⎪⎩⎪⎪⎨⎧≥≤+≤+-0,1442122212121x x x x x x 由L '解出下界5/32___*=z ，由L ''解出上界21___*=z1.7 （1）有无界解；（2）有唯一最优解T x )0,0,3,0,2(*=；（3）有唯一最优解T x )0,1,5/9,5/2(*=；（4）1.8 0,2/3,5,5,0,1,3,2,2,4,2,3=-=======-====l k j i h g f e d c b a 1.9 证明：设)2()1()1(X X X αα-+=为)1(X和)2(X连线上任一点由已知，)2()2()1()1(CX z z CX===则])1([)2()1(X X C CX αα-+=)1()2()2()2()2()1(z z CX CX CX CX ===-+=αα1.10 证明：*0CX CX≥ ，0)(0*≤-∴X X C （1）又0***X C X C ≥，有0)(0**≥-X X C （2）)1()2(-得0))((0**≥--X X C C1.11 （1）先列出两个新的约束β99333)(431+=-+'x x x i β3333)(32+-=+-'x x ii以1x ，2x 为基列出初始单纯形表如下：（2）0=β时，43≤≤α时，最优基不变（3）3=α时，11≤≤-β时，最优基不变1.12 （1）*X 仍为最优解（2）除C 为常数向量外，一般*X 不再是问题的最优解 （3）最优解变为*X λ，目标函数值不变1.13 设选择五种饲料的公斤数分别为54321,,,,x x x x x ，则543218.03.04.07.02.0min x x x x x z ++++= ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥++++≥++++≥++++0,,,,1008.022.00.15.0305.022.05.07001862354325432154321543211x x x x x x x x x x x x x x x x x x x x 1.14 设654321,,,,,x x x x x x 分别代表于早上6：00，10：00，…，早上2：00开始上班的护士数，则654321min x x x x x x z +++++=⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧≥≥+≥+≥+≥+≥+≥+0,,30205060706061655443322116x x x x x x x x x x x x x x 1.15 用i =1，2，3分别代表商品A ，B ，C ，j =1，2，3分别代表前、中、后舱，ij x 为装于j 舱位的i 种商品的数量，目标函数为总运费收入最大，约束条件需分别考虑舱位载重限制，舱位容量限制，商品数量限制及各舱位载重的平衡限制。

运筹学》习题答案运筹学答案《运筹学》习题答案一、单选题1.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（）BA.任意网络B.无回路有向网络C.混合网络D.容量网络2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（）BA.非线性问题的线性化技巧B.静态问题的动态处理C.引入虚拟产地或者销地D.引入人工变量3.静态问题的动态处理最常用的方法是？BA.非线性问题的线性化技巧B.人为的引入时段C.引入虚拟产地或者销地D.网络建模4.串联系统可靠性问题动态规划模型的特点是（）DA.状态变量的选取B.决策变量的选取C.有虚拟产地或者销地D.目标函数取乘积形式5.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( )。

CA.降低的B.不增不减的C.增加的D.难以估计的6.最小枝权树算法是从已接接点出发，把( )的接点连接上CA.最远B.较远C.最近D.较近7.在箭线式网络固中，( )的说法是错误的。

DA.结点不占用时间也不消耗资源B.结点表示前接活动的完成和后续活动的开始C.箭线代表活动D.结点的最早出现时间和最迟出现时间是同一个时间8.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。

CA.1200B.1400C.1300D.17009.在求最短路线问题中，已知起点到A，B，C三相邻结点的距离分别为15km，20km,25km，则（）。

DA.最短路线—定通过A点B.最短路线一定通过B点C.最短路线一定通过C点D.不能判断最短路线通过哪一点10.在一棵树中，如果在某两点间加上条边，则图一定( )AA.存在一个圈B.存在两个圈C.存在三个圈D.不含圈11.网络图关键线路的长度( )工程完工期。

CA.大于B.小于C.等于D.不一定等于12.在计算最大流量时，我们选中的每一条路线( )。

CA.一定是一条最短的路线B.一定不是一条最短的路线C.是使某一条支线流量饱和的路线D.是任一条支路流量都不饱和的路线13.从甲市到乙市之间有—公路网络，为了尽快从甲市驱车赶到乙市，应借用（）CA.树的逐步生成法B.求最小技校树法C.求最短路线法D.求最大流量法14.为了在各住宅之间安装一个供水管道．若要求用材料最省，则应使用( )。

·No .1 线性规划1、某织带厂生产A 、B 两种纱线和C 、D 两种纱带，纱带由专门纱线加工而工厂有供纺纱的总工时7200h ，织带的总工时1200h 。

(1) 列出线性规划模型，以便确定产品的数量使总利润最大；(2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？解：(1)设A 的产量为x 1，B 的产量为x 2，C 的产量为x 3，D 的产量为x 4，则有线性规划模型如下：max f (x )=(168-42)x 1 +(140-28)x 2 +(1050-350)x 3 +(406-140)x 4=126 x 1 +112 x 2 +700 x 3 +266 x 4s.t. ⎪⎩⎪⎨⎧=≥≤+≤+++4,3,2,1 ,012005.02 720041023434321i x x x x x x x i(2)如果组织这次生产有一次性的投入20万元，由于与产品的生产量无关，故上述模型只需要在目标函数中减去一个常数20万，因此可知对模型的解没有影响。

2、将下列线性规划化为极大化的标准形式 解：将约束条件中的第一行的右端项变为正值，并添加松弛变量x 4，在第二行添加人工变量x 5，将第三行约束的绝对值号打开，变为两个不等式，分别添加松弛变量x 6, x 7，并令x x x 333='-''，则有max[-f (x )]= {-2 x 1 -3 x 2 -5('-''x x 33)+0 x 4 -M x 5+0 x 6 +0 x 7} s.t. 0,,,,,,,1355719 13 5571916 9976 5 7654332173321633215332143321≥'''=+''+'-+-=+''-'+-=+''+'-+-=+''-'+--⎪⎪⎪⎩⎪⎪⎪⎨⎧x x x x x x x x x x x x x x x x x x x x x x x x x x x x ⎪⎪⎩⎪⎪⎨⎧±≥≤+-=-+--≥-+++=不限32132********21 ,0,13|5719|169765 ..532)(min x x x x x x x x x x x x t s x x x x f3、用单纯形法解下面的线性规划⎪⎪⎩⎪⎪⎨⎧≥≤++-≤++-≤-+++= ,0,,4205.021********* ..352)(max 321321321321321x x x x x x x x x x x x t s x x x x f 解：在约束行1,2,3分别添加x 4, x 5, x 6松弛变量，有初始基础可行解和单纯形答：最优解为x 1 =244.375, x 2 =0, x 3 =123.125, 剩余变量x 6 =847.1875；最优解的目标函数值为858.125。

教材习题答案部分有图形的答案附在各章PPT文档的后面，请留意。

第1章线性规划第2章线性规划的对偶理论第3章整数规划第4章目标规划第5章运输与指派问题第6章网络模型第7章网络计划第8章动态规划第9章排队论第10章存储论第11章决策论第12章对策论习题一1.1 讨论下列问题：（1）在例1.1中，假定企业一周内工作5天，每天8小时，企业设备A有5台，利用率为0.8,设备B有7台，利用率为0.85,其它条件不变，数学模型怎样变化．（2）在例1.2中，如果设x j(j=1，2，…，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化．（3）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路．（4）在例1.4中，若允许含有少量杂质，但杂质含量不超过1％，模型如何变化．（5）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化．1.2 工厂每月生产A、B、C三种产品,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－22所示．310和130.试建立该问题的数学模型,使每月利润最大．【解】设x1、x2、x3分别为产品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 =++++≤⎧⎪++≤⎪⎪≤≤⎪⎨≤≤⎪⎪≤≤⎪≥⎪⎩ 1.3 建筑公司需要用6m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格及数量如表1－23所示：【解】设x j （j =1,2,…，14）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为14112342567891036891112132347910121314min 2300322450232400232346000,1,2,,14jj j 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 x x x x x j ==⎧+++≥⎪++++++≥⎪⎪++++++≥⎨⎪++++++++≥⎪⎪≥=⎩∑ 用单纯形法求解得到两个基本最优解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）余料最少数学模型为134131412342567891036891112132347910121314min 0.60.30.70.40.82300322450232400232346000,1,2,,14j 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 x x x x x x x x x j =+++++⎧+++≥⎪++++++≥⎪⎪++++++≥⎨⎪++++++++≥⎪⎪≥=⎩ 用单纯形法求解得到两个基本最优解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根 显然用料最少的方案最优。

运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题a）12121212min z=23466 ..424,0x xx xs t x xx x++≥⎧⎪+≥⎨⎪≥⎩解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为最优解，即该问题有无穷多最优解，这时的最优值为min 3z=23032⨯+⨯=P47 1.3 用图解法和单纯形法求解线性规划问题a）12121212max z=10x5x349 ..528,0x xs t x xx x++≤⎧⎪+≤⎨⎪≥⎩解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点，即112122134935282xx xx x x=⎧+=⎧⎪⇒⎨⎨+==⎩⎪⎩，即最优解为*31,2Tx⎛⎫= ⎪⎝⎭这时的最优值为max335z=101522⨯+⨯=单纯形法： 原问题化成标准型为121231241234max z=10x 5x 349..528,,,0x x x s t x x x x x x x +++=⎧⎪++=⎨⎪≥⎩ j c →105B CB X b 1x2x3x4x0 3x 9 3 4 1 0 04x8[5] 2 0 1 j j C Z -105 0 0 0 3x 21/5 0 [14/5] 1 -3/5 101x8/51 2/5 0 1/5 j j C Z -1 0 -2 5 2x 3/2 0 1 5/14 -3/14 101x11 0 -1/72/7j j C Z --5/14 -25/14所以有*max 33351,,1015222Tx z ⎛⎫==⨯+⨯= ⎪⎝⎭P78 2.4 已知线性规划问题：1234124122341231234max24382669,,,0z x x x x x x x x x x x x x x x x x x x =+++++≤⎧⎪+≤⎪⎪++≤⎨⎪++≤⎪≥⎪⎩求: (1) 写出其对偶问题；（2）已知原问题最优解为)0,4,2,2(*=X ，试根据对偶理论，直接求出对偶问题的最优解。