运筹学习题答案(第三章)

运筹学第三章习题答案详细运筹学是一门研究如何有效地做出决策的学科，它运用数学和逻辑的方法来解决实际问题。

在运筹学的学习中，习题是非常重要的一部分，通过解答习题可以加深对知识的理解和应用。

本文将详细解答运筹学第三章的习题，帮助读者更好地掌握该章节的内容。

第一题是关于线性规划的基本概念和性质的。

线性规划是运筹学中的重要分支，它的目标是在一组约束条件下，找到使目标函数最大或最小的变量值。

这个问题可以用一个线性规划模型来描述，其中包括决策变量、目标函数和约束条件。

在解答这个问题时，我们需要先确定决策变量、目标函数和约束条件，然后使用线性规划的方法求解最优解。

具体的计算过程可以通过线性规划的算法来完成。

第二题是关于线性规划的图解法的。

线性规划的图解法是一种直观的解法，它通过绘制变量的可行域和目标函数的等高线图来求解最优解。

在解答这个问题时，我们需要先将约束条件转化为直线或者曲线的形式，然后绘制出这些直线或曲线，并确定它们的交点。

最后，我们需要在可行域内找到使目标函数取得最大或最小值的点，这个点就是线性规划的最优解。

第三题是关于整数规划的应用的。

整数规划是线性规划的一种特殊形式，它要求决策变量取整数值。

在解答这个问题时，我们需要先确定整数规划的模型，包括决策变量、目标函数和约束条件。

然后，我们可以使用整数规划的算法来求解最优解。

在实际应用中，整数规划可以用来解决很多实际问题，比如生产计划、运输调度等。

第四题是关于线性规划的灵敏度分析的。

灵敏度分析是线性规划中的一种重要技术，它用来分析目标函数系数、约束条件右端常数和决策变量上下界的变化对最优解的影响。

在解答这个问题时，我们需要计算目标函数系数、约束条件右端常数和决策变量上下界的变化对最优解的影响程度，并进行相应的调整。

通过灵敏度分析，我们可以了解到线性规划模型对参数变化的敏感性，从而做出更加准确的决策。

第五题是关于线性规划的对偶问题的。

线性规划的对偶问题是线性规划的一个重要概念，它可以用来求解原始问题的最优解。

《运筹学教程》第三章习题答案1.影子价格是根据资源在生产中作出的贡献而做的估价。

它是一种边际价格，其值相当于在资源得到最有效利用的生产条件下，资源每变化一个单位时目标函数的增量变化。

又称效率价格。

影子价格是指社会处于某种最优状态下，能够反映社会劳动消耗、资源稀缺程度和最终产品需求状况的价格，是社会对货物真实价值的度量。

只有在完善的市场条件下才会出现，然而这种完善的市场条件是不存在的，因此现成的影子价格也是不存在的。

市场价格是物品和服务在市场上销售的实际价格，是由供求关系决定的。

2.证明：当原问题约束条件右端变为b i′时，原问题变为： maxz=∑C i X js.t. ∑a ij X i≤b i′(i=1,2,3,……,m)X j≥0 (j=1,2,3,……,n)对偶问题为： minp=∑b i′y is.t. ∑a ij y i≥C iy i≥0(i=1,2,3,……,m) (j=1,2,3,……,n) 设，当b i变为b i′原问题有最优解（X1′X2′X3′……X n-1′X n′）时，对偶问题的最优解为（y1′y2′y3′……y n-1′y n′）,则有：又因为当原问题有最优解时，对偶问题也有最优解，且相等，则有：所以3（1）.minp=6y1 + 2y2s.t. -y1+2y2≥-33y1+3y2≥4y1,y2≥0(2)解：令X2=X2′-X2〞，X4= X4′-X4〞，X2′，X2〞，X4′，X4〞≥0 ，原式化为：maxz=2X1 +2X2′-2X2〞-5X3 +2X4′-2X4〞s.t. 2X1 -X2′+X2〞+3X3 +3X4′-3X4〞≤-5-2X1 +X2′-X2〞-3X3 -3X4′+3X4〞≤5-6X1 -5X2′+5X2〞+X3 -5X4′+5X4〞≤-610X1 -9X2′+9X2〞+6X3 +4X4′-4X4〞≤12X1, X2′，X2〞，X3, X4′，X4〞≥0则对偶规划为：.minp= -5y1′+ 5y1〞-6y2 + 12y3s.t. 2y1′-2y1〞-6y2 + 10y3≥2-y1′+y1〞-5y2 -9y3≥2y1′-y1〞+5y2 + 9y3≥-23y1′-3y1〞+y2 + 6y3≥-53y1′-3y1〞-5y2 + 4y3≥2-3y1′+3y1〞+5y2 -4y3≥-2即：minp= -5y1′+ 5y1〞-6y2 + 12y3s.t. 2y1′-2y1〞-6y2 + 10y3≥2-y1′+y1〞-5y2 -9y3=23y1′-3y1〞+y2 + 6y3≥-53y1′-3y1〞+5y2 + 4y3=2令 y1〞- y1′= y1，得：minp= 5y1 -6y2 + 12y3s.t. -2y1-6y2 + 10y3≥2y1-5y2 -9y3=2-3y1+y2 + 6y3≥-5-3y1-5y2 + 4y3=24、试用对偶理论讨论下列原问题与他们的对偶问题是否有最优解。

一、选择题1. 2. 3. 4. 5. 6. 7.二、判断题1. 2. 3. 4. 5. 6. 7. 8. 9.三、表上作业法 3. 解：可知，有初始基本可行解1112132122230,10,20,10,35,0x x x x x x ======用闭回路法计算非基变量的检验数：1123(56)(84)10(98)(67)40σσ=+-+=-<=+-+=>因为110σ<，该解并不是最优解。

进行换基迭代，让11x 进基，考虑上述闭回路，调整量min(10,10)10θ==，调整后得到新的调运方案：A2 4 0645945销量10 45 20计算非基变量的检验数得：1223(84)(56)10(95)(47)30σσ=+-+=>=+-+=>故此方案为最优方案，最优解为：11121321222310,0,20,0,45,0x x x x x x ======最优值min 105207456460Z =⨯+⨯+⨯=用电子表格模型求解进行验算：4. 解：用西北角法求得初始基本可行解：1112131421222324313233344,0,0,0;1,2,4,2;0,0,0,4;x x x x x x x x x x x x ============ 用位势法计算检验数：1111212121131322214142233131324323243433333106()210167()861012()9455()12194()731010()47u u v u v v u v u v u u v u v v u v u v v u v u v v u v u v u σσσσσσ=⎧+==-+=⎧⎧⎪=⎪⎪⎪+==-+=⎪⎪⎪=⎪⎪++=-+=⎪⎪⇒=⇒⎨⎨⎨+==-+=-⎪⎪=-⎪⎪+==-+=-=⎪⎪+==-+=⎪⎪⎩=⎩⎪⎪⎪⎪⎪⎩因为3132,σσ小于0，该解不是最优解。

判 断 题判断正误，如果错误请更正第三章 整数数列 1.整数规划的最优解是先求相应的线形规划的最优解然后取整得到。

2.部分变量要求是整数的规划问题称为纯整数规划。

3.求最大值问题的目标函数值是个分支函数值的上界。

4.求最小值问题的目标函数值是个分支函数值的下界。

5.变量取0或1的规划是整数规划。

6.整数规划的可行解集合是离散型集合。

7. 高莫雷约束是将可行域中一部分非整数解切割掉。

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

第三章 整数规划1. maxZ=3x1+2x2,2x1+3x2<=14,x1+0.5x2<=4.5,x1,x2>=0且为整数，对应线性规划的最优解是（3.25，2.5），它的整数规划的最优解是 A （4，1）B （4，3）C （3，2）D （2，4）2. 下列说法正确的是 A 整数规划问题最优值优于其相应的线性规划问题的最优值 B 用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解 C 用分支定界法求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，在进行比较减支 D 分支定界法在求解整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对个变量的整数要求限制，从而把原整数规划问题通过分支迭代求出最优解。

3. x1是要求是非负整数，它的来源行是x1-5/3x4+7/3x5=8/3,高莫雷方程是 A -1/3x4-1/3x5<=-2/3 B -x4-x5<=-2 C x4+x5-s=2 D -1/3x4-1/3x5+s=-2/3 Ex4+x5+s=24. 分支定界法中 A 最大值问题的目标值是个分支的下界 B 最大值问题的目标值是个分支的上界 C 最小值问题的目标值是个分支的上界 D 最小值问题的目标值是个分支的下界5. maxZ=3x1+x2,4x1+3x2<=7,x1+2x2<=4,x1,x2=0或1，最优解是 A （0，0） B （0，1）C （1，0） D （1，1）计算题3.1 用分支定界法求以下纯整数规划问题：max z = 3x 1 + 7x 2s.t. x 1 + 3/2x 2 ≤ -1/5x 1 +1/5 x 2 ≤ x 1 x 2 ≥ 0x 1, x 2 为整数则整数最优解为X1=1，X2=3，最优值为maxZ=24 3.2用割平面法求以下纯整数规划问题。

第一章 线性规划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,得到一下等价的标准形式。

第三章作业的参考答案
99P 3、用Gomory 割平面法求解下面的ILP 问题.
⎪⎪⎩⎪⎪⎨⎧=≥≥-≤+-=.2,1,0482..5min 212121i x x x x x t s x x z i 整数， 解：将原问题标准化
⎪⎪⎩⎪⎪⎨⎧=≥=--=++-=.
4,3,2,1,0482..5min 42132121i x x x x x x x t s x x z i 整数， 将第二个等式乘以)1(-加到第一个等式，可得线性方程组的典式
⎪⎪⎩⎪⎪⎨⎧=≥=--=++-=.4,3,2,1,0443..5min 42143221i x x x x x x x t s x x z i 整数，
所以，其松驰问题（P0）的第一张单纯形表为
把零行化成检验行，得
1x 2x 3x 4x RHS z
3x 1x
以2x 为进基变量，3x 为离基变量，旋转得
所以，松驰问题（P0）的最优解为T x )0,0,3
4,316(
0=， 它不是整数向量。

所以由第一行生成的割平面条件为 31313143≥+x x .
对应的割平面为
313131143-=+--s x x .
把它加入到松驰问题（P0）的最优单纯形表中，得到改进的松弛问题（P1）的
1x 2x 3x 4x RHS z 2x 1x
利用对偶单纯形方法求解. 以1s 为离基变量，3x 为进基变量，旋转得
所以，松弛问题（P 1）的最优解为T x )0,0,1,1,5(1=。

因此，原问题的最优解为T x )1,5(*=,最优值为0. 1x 2x 3x 4x 1s RHS z
2x 1x 3x。

3.1（1）解：, 53351042..715min 212112121≥≥+≥≥++=y y y y y y y t s y y ω（2）解：无限制32132131323213121,0,0 2520474235323..86max y y y y y y y y y y y y y y y t s y y ≤≥=++≤-=+≥+--≤++=ω3.4解：例3原问题6,,1,0603020506070..min 166554433221654321 =≥≥+≥+≥+≥+≥+≥++++++=j x x x x x x x x x x x x x t s x x x x x x z j对偶问题：6,,1,0111111..603020506070max 655443322161654321 =≥≤+≤+≤+≤+≤+≤++++++=j y y y x y y y y y y y y y t s y y y y y y j ω3.5解：（1）由最优单纯形表可以知道原问题求max ，其初始基变量为54,x x ，最优基的逆阵为⎪⎪⎪⎪⎭⎫ ⎝⎛-=-31610211B 。

由P32式（2.16）（2.17）（2.18）可知b B b 1-='，5,,1,,1 ='-=='-j P C c P B P j B j j j j σ，其中b 和j P 都是初始数据。

设⎪⎪⎭⎫ ⎝⎛=21b b b ，5,,1,21 =⎪⎪⎭⎫⎝⎛=j a a P j j j ，()321,,c c c C =，则⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎪⎭⎫ ⎝⎛-⇒='-25253161021211b b b B b ，即⎪⎩⎪⎨⎧=+-=2531612521211b b b ，解得⎩⎨⎧==10521b b ⎪⎪⎪⎪⎭⎫⎝⎛-=⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎪⎭⎫⎝⎛-⇒='-0211121031610212322211312111a a a a a a P B P j j ，即 ⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧=+-=-=+-==+-=03161121213161212113161021231313221212211111a a a a a a a a a ，解得⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==-====121130231322122111a a a a a a()()()⎪⎪⎪⎪⎭⎫⎝⎛---=---⇒'-=31612102121,0,0,2,4,4132c c c P C c j B j j σ，即 ⎪⎪⎪⎩⎪⎪⎪⎨⎧-=--=+--=+-2314612142121113132c c c c c c ，解得⎪⎩⎪⎨⎧==-=6102132c c c所以原问题为：,, 10352..1026max 32132132321≥≤+-≤++-=x x x x x x x x t s x x x z 对偶问题为：, 102263..105min 212121221≥≥+-≥-≥+=y y y y y y y t s y y ω（2）由于对偶问题的最优解为()()()2,4,,5454*=-=-=σσσc c C Y IB IB3.6解：（1）因为3x 的检验数0353≤⨯-c ，所以3c 的可变范围是153≤c 。

目标函数值为2×30＋5×10＋1×10＋5×10＋3×25＋7×5＋6×20＋10×40＝800目标函数值为2×30＋5×10＋1×10＋5×10＋3×25＋7×5＋6×20＋10×40＝800（2）最小元素法：先从311=c 开始分配先从325=c 开始分配，需迭代4次，具体见QM 的迭代 逼近法（结果同最小元素法——先从313=c 开始分配）vj2 2 0 u i1 2 3 产量 0 1 2 10 7 2 8 × 7 × 2 1 2 3 2 1 0 × 2 2 4 1 3 11 3 8 8 × 3 7 × 3 2 4 4 9 2 1 5 × 5 6 -2 5 0 0 0 4 0 × 2 × 4销量757目标函数值为33。

4.5第一种解法（求最大）A B C 产量 甲 18 16 21 180 乙 16 18 22 250 丙 19 14 19 320 销量 250300200用QM 解得玩 具利 润工人第二种解法（求最小）A B C产量甲526449180乙546248250丙516651320销量250300200用QM解得即甲工人做C玩具180个，乙工人做B玩具250个，丙工人做A玩具250个，做B玩具50个，做C玩具20个。

最大利润为：70×250＋80×300＋70×200－41390＝14110元甲乙丙产量A151822400B212516450最低需求290250270最高需求320250350甲1甲2乙丙1丙2产量A1515182222400B2121251616450C M0M M070需求2903025027080用QM解得玩具费用工人地区运费厂家地区运费厂家即A厂供给甲地区化肥150万吨，供给乙地区化肥250万吨；B厂供给甲地区化肥140万吨，供给丙地区化肥310万吨，总运费为14650万元。

第3章训练题一．基本能力训练求解下列整数线性规划问题1．2194m in x x z --= 2．2m in x z -=为整数21212121,0,70207567 9xxx x x x x x ≥≤+≤+ 为整数,0,,,0236234321421321≥=++-=++x x x x x x x x x x3．5432134523m in x x x x x z --++= 4．21114m ax x x z +=5,4,3,2,1,1053361153437025421543154321==≤++-≤+++-≤+-+--j x x x x x x x x x x x x x x j 或 为整数2121212121,0,421652142x x x x x x x x x x ≥≤+-≤+≤-5．2143m ax x x z += 6．213m in x x z -=为整数21212121,0,16351149x x x x x x x x ≥≤-≤+ 为整数2121212121,0,52105433x x x x x x x x x x ≥≤+≥+≥+-7．215m in x x z +-= 8．21m in x x z --=为整数21212121,0,482x x x x x x x x ≥≤+-≤+ 10,20546212121或=≤+≤+x x x x x x9．321345min x x x z ++= 10．321161017m ax x x x z ++=10,,1334435232132321321或=≥+≥++≤+-x x x x x x x x x x x ⎪⎪⎪⎩⎪⎪⎪⎨⎧==≤++≤+-≤++≤+)3,2,1(107325732462562432132132132j x x x x x x x x x x x x j 或11．21m ax x x z += 12． 2132m ax x x z +=⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤+-≤+且为整数0,3121451149212121x x x x x x ⎪⎩⎪⎨⎧≥≤+≤+且为整数0,36943575212121x x x x x x 13． 21m ax x x z += 14．2197m ax x x z +=⎪⎩⎪⎨⎧≥≤+≤+且为整数0,30561652212121x x x x x x ⎪⎩⎪⎨⎧≥≤+≤+-且为整数0,35763212121x x x x x x 15． 2154m in x x z += 16．321264m ax x x x z ++=⎪⎪⎩⎪⎪⎨⎧≥≥+≥+≥+且为整数0,235472321212121x x x x x x x x ⎪⎪⎩⎪⎪⎨⎧≥≤++-≤+-≤-且为整数0,,5565443213212121x x x x x x x x x x 17．21411m ax x x z += 18．5432132523m ax x x x x x z +--+=⎪⎪⎩⎪⎪⎨⎧≥≤-≤+≤+-且为整数，04216254221212121x x x x x x x x ⎪⎪⎩⎪⎪⎨⎧==≥-+-≤+-+≤++++)5,,1(1033361183437425421543154321 j x x x x x x x x x x x x x x j 或 19．543214352m ax x x x x x z +-+-= 20．5432157428m ax x x x x x z ---+=⎪⎩⎪⎨⎧==≤+-+-≤+-+-），，（或511002426457235432154321 j x x x x x x x x x x x j ⎪⎩⎪⎨⎧==≤+--+≤++++），，（或51104235432335432154321 j x x x x x x x x x x x j21．2123m ax x x z += 22．211020m ax x x z +=为整数21212121,0,921432x x x x x x x x ≥≤+≤+ ⎪⎪⎩⎪⎪⎨⎧≤+-≤-≤++-皆是非负整数32132132321,,32323442x x x x x x x x x x x23．2197m ax x x z += 24．32133m ax x x x z ++=⎪⎩⎪⎨⎧≥≤+≤+-为整数且12121210,35763x x x x x x x ⎪⎪⎩⎪⎪⎨⎧≥≤+-≤-≤++-为整数且3132132132321,,0,,32323442x x x x x x x x x x x x x 25．5432198765m ax x x x x x z ++++= 26．321523m ax x x x z +-=⎪⎪⎩⎪⎪⎨⎧==≥+++--≥+--+≥-++-)5,4,3,2,1(,10230223223543215432154321j x x x x x x x x x x x x x x x x j 或 ⎪⎪⎪⎩⎪⎪⎪⎨⎧=≤+≤+≤++≤-+10,,64344223213221321321或x x x x x x x x x x x x x 27．2175m ax x x z += 28．2158m ax x x z +=⎪⎩⎪⎨⎧≥≤+≤+且为整数0,182384247212121x x x x x x ⎪⎩⎪⎨⎧≥≤-≤+且为整数0,621232212121x x x x x x 27．最优解为34,)2,4(*=z T。