运筹学习题答案

运筹学部分课后习题解答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、由图可得：最优解为2、用图解法求解线性规划： Min z=2x 1+x 2⎪⎪⎩⎪⎪⎨⎧≥≤≤≥+≤+-01058244212121x x x x x x解：由图可得：最优解x=1.6,y=6.4Max z=5x 1+6x 2⎪⎩⎪⎨⎧≥≤+-≥-0,23222212121x x x x x x解：由图可得：最优解Max z=5x 1+6x 2, Max z= +∞Maxz = 2x 1 +x 2⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤0,5242261552121211x x x x x x x由图可得：最大值⎪⎩⎪⎨⎧==+35121x x x ， 所以⎪⎩⎪⎨⎧==2321x xmax Z = 8.1212125.max 23284164120,1,2maxZ .jZ x x x x x x x j =+⎧+≤⎪≤⎪⎨≤⎪⎪≥=⎩如图所示，在（4，2）这一点达到最大值为26将线性规划模型化成标准形式：Min z=x 1-2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≥-=++-≥+-≤++无约束321321321321,0,052327x x x x x x x x x x x x解：令Z ’=-Z,引进松弛变量x 4≥0，引入剩余变量x 5≥0，并令x 3=x 3’-x 3’’,其中x 3’≥0,x 3’’≥0Max z ’=-x 1+2x 2-3x 3’+3x 3’’⎪⎪⎩⎪⎪⎨⎧≥≥≥≥≥≥-=++-=--+-=+-++0,0,0'',0',0,05232'''7'''5433213215332143321x x x x x x x x x x x x x x x x x x x7将线性规划模型化为标准形式Min Z =x 1+2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≤-=--≥++-≤++无约束，321321321321,00632442392-x x x x x x x x x x x x解：令Z ’ = -z ，引进松弛变量x 4≥0,引进剩余变量x 5≥0,得到一下等价的标准形式。

运筹学部分课后习题解答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 →10 5B CB Xb 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 ，试根据对偶理论，直接求出对偶问题的最优解。

《运筹学》习题答案一、单选题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.4 分别用图解法和单纯型法求解下列线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。

（1）Max z=2x 1+x 2St.⎪⎩⎪⎨⎧≥≤+≤+0,24261553212121x x x x x x 解：①图解法：由作图知，目标函数等值线越往右上移动，目标函数越大，故c 点为对应的最优解，最优解为直线⎩⎨⎧=+=+242615532121x x x x 的交点，解之得X=(15/4,3/4)T 。

Max z =33/4. ② 单纯形法：将上述问题化成标准形式有： Max z=2x 1+x 2+0x 3+0x 4St. ⎪⎩⎪⎨⎧≥≤++≤++0,,,242615535421421321x x x x x x x x x x其约束条件系数矩阵增广矩阵为：P 1 P 2 P 3 P 4⎥⎦⎤⎢⎣⎡241026150153 P 3,P 4为单位矩阵，构成一个基，对应变量向，x 3,x 4为基变量，令非基变量x 1,x 2为零，找到T 优解，代入目标函数得Max z=33/4.1.7 分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题，并指出属哪一类。

（3）Min z=4x 1+x 2⎪⎪⎩⎪⎪⎨⎧=≥=++=-+=+)4,3,2,1(0426343342132121j xj x x x x x x x x 解：这种情况化为标准形式： Max z ＇=-4x 1-x 2⎪⎪⎩⎪⎪⎨⎧=≥=++=-+=+)4,3,2,1(0426343342132121j xj x x x x x x x x 添加人工变量y1,y2Max z ＇=-4x 1-x 2+0x 3+0x 4-My 1-My 2⎪⎪⎩⎪⎪⎨⎧≥=≥=++=+-+=++0,).4,3,2,1(04263433214112321121y y j xj x x x y x x x y x x(2) 两阶段法： Min ω=y 1+y 2St.⎪⎪⎩⎪⎪⎨⎧≥=≥=++=+-+=++0,).4,3,2,1(04263433214112321121y y j xj x x x y x x x y x x第二阶段，将表中y 1,y 2去掉，目标函数回归到Max z ＇=-4x 1-x 2+0x 3+0x 4第二章 线性规划的对偶理论与灵敏度分析（作业）2.7给出线性规划问题：Max z=2x 1+4x 2+x 3+x 4⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤++≤++≤+≤++)4,3,2,1(096628332143221421j x x x x x x x x x x x x j要求：（1）写出其对偶问题；（2）已知原问题最优解为X *=(2,2,4,0),试根据对偶理论，直接求出对偶问题的最优解。

运筹学部分课后习题解答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 →10 5B 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 ，试根据对偶理论，直接求出对偶问题的最优解。

习题参考答案第二章 习 题1.线性规划模型为：⎪⎪⎩⎪⎪⎨⎧≥≤++≤++≤++++0,,1800231200214002..453max 321321321321321x x x x x x x x x x x x t s x x x 2. 标准形式为：⎪⎪⎩⎪⎪⎨⎧≥=-++-=++=++---+-0,,,,,,1002333800120035.15.1..322min 87654328325473262543254x x x x x x x x x x x x x x x x x x x t s x x x x 3.（1）最优解为（2,2），最优值为8.（2）根据等式约束得：213--6x x x =代入规划等价于：⎪⎩⎪⎨⎧≥≥+≤+++0,3-6..62max 21212121x x x x x x t s x x 先用图解法求线性规划⎪⎩⎪⎨⎧≥≥+≤++0,3-6..2max 21212121x x x x x x t s x x 得最优解为（0,6）代入原规划可得最优解为（0,6,0）最优值为18.4.（1）以21,x x 为基变量可得基可行解（3,1,0），对应的基阵为：⎪⎪⎭⎫⎝⎛1101 以31,x x 为基变量可得基可行解（2,0,1），对应的基阵为：⎪⎪⎭⎫ ⎝⎛2111 （2）规划转化为标准形式：⎪⎩⎪⎨⎧≥=++=++--0,,,55623..34min 432142132121x x x x x x x x x x t s x x 以32,x x 为基变量可得基可行解（0,1,4,0），对应的基阵为：⎪⎪⎭⎫⎝⎛0512 5. 以432,,x x x 为基变量可得基可行解（0,2,3,9），对应的典式为：32192231412=+=+=x x x x x 非基变量1x 的检验数为21-。

6. (1) a=0,b=3,c=1,d=0;(2) 基可行解为(0,0,1,6,2) （3）最优值为3.7.（1）最优解为（1.6,0,1.2），最优值为-4.4；（2）令11-=x y ，则0≥y ，11+=y x ，在规划中用1+y 替代1x ，并化标准形式。

《运筹学》习题答案一、单选题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、Nash均衡的定义是：
A、每位参与者的行为均达到最佳利益的状态
B、每位参与者的行为均达到得到最大胜利的状态
C、每位参与者的行为均达到合作的最佳状态
D、每位参与者的行为均达到合作的最大胜利的状态
答案：A
2、决策就是参与者用来实现选择的：
A、计划
B、机构
C、程序
D、工具
答案：D
3、运筹学可以分为：
A、组合数学
B、运动学
C、博弈论
D、概率论
答案：A、B、C、D
4、非线性规划有：
A、分支定界法
B、梯度下降法
C、基于格法的解法
D、对偶法
答案：A、B、C、D
5、关于迭代法,下列表述正确的有：
A、可以求解非凸优化问题
B、单次迭代过程简单
C、收敛性较好
D、用于非线性规划
答案：A、B、C
二、填空题：
1、博弈论是研究__参与者之间的__的科学。

答案：多，竞争。

教材习题答案部分有图形的答案附在各章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根 显然用料最少的方案最优。