运筹学黄皮版第二章习题答案

习题参考答案第二章 习 题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 ，并化标准形式。

习题2.1某厂利用A 、B 两种原料生产甲、乙、丙三种产品，已知单位产品所需的原料、利润及有关数据如表2—3所示。

表2—3 两种原料生产三种产品的有关数据产品甲 产品乙 产品丙 拥有量 原料A 6 3 5 45 原料B 3 4 5 30 单位利润 4 1 5 请分别回答下列问题：（1） 求使该厂获利最大的生产计划。

（2） 若产品乙、丙的单位利润不变，当产品甲的单位利润在什么范围内变化时，最优解不变？（3） 若原料A 市场紧缺，除拥有量外一时无法购进，而原料B 如数量不足可去市场购买，单价为0.5，问该厂是否应该购买，且以购进多少为宜？解：（1）设产品甲的产量为x 1，产品乙的产量为x 2，产品丙的产量为x 3. 目标函数为:Max z =4 x 1 + x 2+5 x 3约束条件：s.t.{ 6x 1+3x 2+5x 3≤45；3x 1+4x 2+5x 3≤30；x 1,x 2,x 3≥0；该线性规划模型为：答：该厂获利最大的生产计划为产品甲产量为5，产品乙产量为0，产品丙产量为3，总利润为35。

（2）敏感性报告为：答：如数据显示，产品甲的单位利润变化范围为：[3，6]。

（3）敏感性报告为：由敏感性报告显示原料B允许的增量为15，其影子价格为0.667，又因为市场上原料B单价为0.5，此时，总利润为37.5。

答：该厂可购买15。

习题2.3已知某工厂计划生产三种产品，各产品需要在设备A、B、C上加工，有关数据如表2—5所示。

表2—5 生产三种产品的有关数据产品A产品B产品C每月设备有效台时设备A8210300设备B1058400设备C21310420单位利润（千元）32 2.9请分别回答下列问题：(1)如何充分发挥设备能力，才能使生产盈利最大？(2)为了增加产量，可借用其他工厂的设备B，若每月可借用60台时，租金为1.8万元，问借用设备B是否合算？(3)若另有两种新产品（产品4和产品5），其中生产每件新产品4需用设备A、B、C各12、5、10台时，单位赢利2.1千元；生产每件新产品5需用设备A、B、C各4、4、12台时，单位赢利1.87千元。

运筹学习题集（第二章）判断题判断正误，如果错误请更正第二章线形规划的对偶理论1.原问题第i个约束是<=约束,则对偶变量yi>=0.2.互为对偶问题,或则同时都有最优解,或则同时都无最优解.3.原问题有多重解,对偶问题也有多重解.4.对偶问题有可行解,原问题无可行解,则对偶问题具有无界解.5.原问题无最优解,则对偶问题无可行解.6.设X,Y分别为｛minZ=CX｜AX>=b,X>=0｝和｛maxw=Yb｜YA<=C,Y>=0｝的可行解,则有(1)CX<=Yb;(2)CX是w的上界;(3)当X,Y为最优解,CX=Yb;(4)当CX=Yb 时,有YXs+YsX=0;(5)X为最优解且B是最优基时,则Y=C B B-1是最优解;(6)松弛变量Ys的检验数是λs,则X=-λs是基本解,若Ys是最优解, 则X=-λs是最优解.7.原问题与对偶问题都可行,则都有最优解.8.原问题具有无界解,则对偶问题可行.9.若X,Y是原问题与对偶问题的最优解.则X=Y.10.若某种资源影子价格为0,则该资源一定有剩余.11影子价格就是资源的价格.12.原问题可行对偶问题不可行,可用对偶单纯形法计算.13.对偶单纯形法比值失效说明原问题具有无界解.14.对偶单纯形法是直接解对偶问题的一种解法.15.减少一个约束,目标值不会比原来变差.16.增加一个约束,目标值不会比原来变好.17增加一个变量, 目标值不会比原来变差.18.减少一个非基变量, 目标值不变.19.当Cj(j=1,2,3,……，n)在允许的最大范围内同时变化时，最优解不变。

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

第二章线性规划的对偶理论1.如果决策变量数列相等的两个线规划的最优解相同，则两个线性规划A约束条件相同B目标函数相同C最优目标函数值相同D以上结论都不对2.对偶单纯形法的最小比值规则是为了保证A使原问题保持可行B 使对偶问题保持可行C逐步消除原问题不可行性D逐步消除对偶问题不可行性3.互为对偶的两个线性规划问题的解存在关系A若最优解存在，则最优解相同B原问题无可行解，则对偶问题也无可行解C对偶问题无可行解，原问题可能无可行解D一个问题无界，则另一个问题无可行解E一个问题无可行解，则另一个问题具有无界解4.已知规范形式原问题（max）的最优表中的检验数为（λ1，λ2，……λn），松弛变量的检验数为（λn+1,λn+2,……λn+m）,则对偶问题的最优解为A—（λ1，λ2，……λn）B （λ1，λ2，……λn）C —（λn+1,λn+2,……λn+m）D （λn+1,λn+2,……λn+m）5.原问题与对偶问题都有可行解，则A原问题有最优解，对偶问题可能没有最优解B原问题与对偶问题可能都没有最优解C可能一个问题有最优解，另一个问题具有无界解D原问题与对偶问题都有最优解计算题线性规划问题和对偶问题2.1 对于如下的线性规划问题min z = 3x1 + 2x2 +x3s.t. x1 + x2+ x3 ≤ 15 (1)2x1 - x2+ x3≥ 9 (2)-x1 + 2x2+2x3≤ 8 (3)x1 x2x3 ≥ 01、写出题目中线性规划问题的对偶问题；2、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；解答：1、写出题目中线性规划问题的对偶问题；解：max w = 15y1 + 9y2 + 8y3s.t. y1 + 2y- y3 ≤ 3 (1)y1 - y2+ 2y3≤ 2 (2)y1 + y2+ 2y3≤ 1 (3)y1≤0、y2 ≥0、y3 ≤02、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；解：先将原问题化成以下形式，则有mi n z = 3x1 + 2x2 + x3s.t. x1 + x2+ x3+ x4= 15 (1)-2x1 + x23+ x5= -9 (2)-x1 + 2x2+2x3+x6= 8 (3)原始问题的最优解为（X 1 X 2 X 3 X 4 X 5 X 6）=（2，0，5，8，0，0），minz=11 对偶问题的最优解为（y 1 y 2 y 3 y 4 y 5 y 6）=（0，7/5，-1/5，0，19/5，0），maxw=112.2 对于以下线性规划问题max z = -x 1 - 2x 2s.t. -2x 1 + 3x 2 ≤ 12 (1) -3x 1 + x 2 ≤ 6 (2) x 1 + 3x 2 ≥ 3 (3) x 1 ≤ 0，x 2 ≥ 01、写出标准化的线性规划问题；2、用单纯形表求出这个线性规划问题的最优解和最优的目标函数值；3、写出这个（极大化）线性规划问题的对偶问题；4、求出对偶问题的最优解和最优解的目标函数值；5、第（2）个约束右端常数b 2=6在什么范围内变化，最优解保持不变。

2.1 用图解法求解下列线性规划问题，并指出各问题具有唯一最优解、无穷多最优解、无界解还是无可行解。

（1）⎪⎪⎩⎪⎪⎨⎧≥≤-≤+≤++=0,84821234..2max 2121212121x x x x x x x x t s x x z解：首先划出平面直角坐标系4 x 1 +3x 2X 1⎩⎨⎧=+=-1234842121x x x x 解：⎪⎩⎪⎨⎧=14921x x 所以：2111492max =+⨯=z 所以有唯一解(2)⎪⎪⎩⎪⎪⎨⎧≥≤-≤+≤+-+=0,414234223max 2121212121x x x x x x x x x x 解：2=41⎩⎨⎧=+=+-1423422121x x x x 解得：⎪⎪⎩⎪⎪⎨⎧==4132521x x 所以:144132253max =⨯+⨯=z 因为直线02321=+x x 与直线142321=+x x 平行， 所以有无穷多最优解，max z=14（3） ⎪⎩⎪⎨⎧≥≤+-≤-+=0,432..32max 21212121x x x x x x t s x x z 解：（4）⎪⎩⎪⎨⎧≥-≤-≥-+=0,330..max 21212121x x x x x x t s x x z解：2.2将下列线性规划问题化为标准形式(1) s.t.⎪⎩⎪⎨⎧≥≤≤-+-=++-+-=无约束321321321321,0,0624322min x x x x x x x x x x x x z (2)⎪⎪⎩⎪⎪⎨⎧≤≥-=-+-≤+-≥--+=0,0232132..23min 3213213132321x x x x x x x x x x t s x x x z 无约束， 解：（1）令011≥-=x x )0'','('''33333≥-=x x x x x则上述形式可化为：)'''(32'2m ax 3321x x x x z --+=⎪⎩⎪⎨⎧≥=+--+=-++0,'',',,'6)'''('24)'''('..43321433213321x x x x x x x x x x x x x x t s（2）⎪⎪⎩⎪⎪⎨⎧≤≥-=-+-≤+-≥--+=0,0232132..23min 3213213132321x x x x x x x x x x t s x x x z 无约束， 解：令33'x x -= )0','','(322≥x x x 则上述形式可化为：')'''(23m ax 3221x x x x z ----=⎪⎪⎩⎪⎪⎨⎧≥=---=+--=+---0,,','',',2')'''(321')'''(3')'''(2..543221322153224322x x x x x x x x x x x x x x x x x x t s 2.3. 在下列线性规划问题中，找出所有基解，指出哪些是基可行解并分别代入目标函数，比较找出最优解。

习题2.1某厂利用A、B两种原料生产甲、乙、丙三种产品，已知单位产品所需的原料、利润及有关数据如表2—3所示。

产品甲产品乙产品丙拥有量原料A63545原料B34530单位利润415（1）求使该厂获利最大的生产计划。

（2）若产品乙、丙的单位利润不变，当产品甲的单位利润在什么范围内变化时，最优解不变？（3）若原料A市场紧缺，除拥有量外一时无法购进，而原料B如数量不足可去市场购买，单价为0.5，问该厂是否应该购买，且以购进多少为宜？解：（1）设产品甲的产量为x1，产品乙的产量为x2，产品丙的产量为x3.目标函数为:Max z=4 x1 + x2+5 x3约束条件：s.t.该线性规划模型为：答：该厂获利最大的生产计划为产品甲产量为5，产品乙产量为0，产品丙产量为3，总利润为35。

（2）敏感性报告为：答：如数据显示，产品甲的单位利润变化范围为：。

（3）敏感性报告为：由敏感性报告显示原料B允许的增量为15，其影子价格为0.667，又因为市场上原料B单价为0.5，此时，总利润为37.5。

答：该厂可购买15。

习题2.3已知某工厂计划生产三种产品，各产品需要在设备A、B、C上加工，有关数据如表2—5所示。

产品A产品B产品C每月设备有效台时设备A8210300设备B1058400设备C21310420单位利润（千元）32 2.9请分别回答下列问题：(1)如何充分发挥设备能力，才能使生产盈利最大？(2)为了增加产量，可借用其他工厂的设备B，若每月可借用60台时，租金为1.8万元，问借用设备B是否合算？(3)若另有两种新产品（产品4和产品5），其中生产每件新产品4需用设备A、B、C各12、5、10台时，单位赢利2.1千元；生产每件新产品5需用设备A、B、C各4、4、12台时，单位赢利1.87千元。

如果设备A、B、C台时不增加，分别回答这两种新产品的投资在经济上是否合算？(4)对产品工艺重新进行设计，改进构造。

改进后生产每件产品1，需用设备A、B、C各9、12、4台时，单位赢利4.5千元，问这对原生产计划有何影响？解：（1）设每月产品A的产量为x1,产品B的产量为x2，产品C的产量为x3。

第二章作业的参考答案73P 4、将下面的线性规划问题化成标准形式⎪⎪⎪⎩⎪⎪⎪⎨⎧≤≤-≤≤≤-+≥+-+-613032632..2max 21321321321x x x x x x x x t s x x x解：将max 化为 min ，3x 用54x x -代替，则⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≤≤-≤≤≤--+≥-+---+-0,61303)(26)(32..)(2min 5421542154215421x x x x x x x x x x x x t s x x x x令122+='x x ，则⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≤'≤≤≤≤---'+≥-+-'----'+-0,70303)()1(26)(3)1(2..)(21min 5421542154215421x x x x x x x x x x x x t s x x x x将线性不等式化成线性等式，则可得原问题的标准形式⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥'=+'=+=++-'+=--+'--+-'+-0,,,,,,,73424332..122min 98765421928175421654215421x x x x x x x x x x x x x x x x x x x x x x t s x x x x73P 5、用图解法求解下列线性规划问题：（1）⎪⎪⎩⎪⎪⎨⎧≥≤≤≥++212620..3min212121x x x x t s x x解：图2.1的阴影部分为此问题的可行区域。

将目标函数的等值线c x x =+213（c 为常数）沿它的负法线方向T），（31--移动到可行区域的边界上。

于是交点T），（812就是该问题的最优解，其最优值为36。

74P 12、对于下面的线性规划问题，以),,(632A A A B =为基写出对应的典式。

⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=+++-=++-=++-+-6,,1,010 83412 427 23..2min 63215214321321 j x x x x x x x x x x x x t s x x x j 解：先将方程组中基变量632,,x x x 的系数向量化成单位向量⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧=≥-=+---=++-=++++-6,,1,039 47 4 2253 41 21581 21 45..2min 65415215431321 j x x x x x x x x x x x x t s x x x j 利用线性方程组的典式，把32,x x 用541,,x x x 表示，再带入目标函数，则可得原问题相应于基),,(632A A A B =的典式⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧=≥-=+---=++-=++++---6,,1,039 47 4 2253 41 21581 21 45..8321451min 65415215431541 j x x x x x x x x x x x x t s x x x j75P 16、用单纯形法求解下列线性规划问题：(1)⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤-+≤+-≤+++--=3,2,1,020102603..2min 321321321321j x x x x x x x x x x t s x x x z j解：将此问题化成标准形式⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=+-+=++-=++++--=6,5,4,3,2,1,020102603..2min 632153214321321j x x x x x x x x x x x x x t s x x x z j以654,,x x x 为基变量，可得第一张单纯形表为以1x 为以2x 为进基变量，6x 为离基变量旋转得 解为Tx )0,5,15(*=，最所以最优优值为-35。

1．某人根据医嘱，每天需补充A 、B 、C 三种营养，A 不少于80单位，B 不少于150单位，C 不少于180单位．此人准备每天从六种食物中摄取这三种营养成分．已知六种食物每百克的营养成分含量及食物价格如表2-22所示．（1）试建立此人在满足健康需要的基础上花费最少的数学模型；（2）假定有一个厂商计划生产一中药丸，售给此人服用，药丸中包含有A ，B ，C 三种营养成分．试为厂商制定一个药丸的合理价格，既使此人愿意购买，又使厂商能获得最大利益，建立数学模型．表2-22【解】（1）设x j 为每天第j 种食物的用量，数学模型为 ⎪⎪⎩⎪⎪⎨⎧≥≥++++≥+++++≥++++++++++=01801034217181501512253092480118401425132.03.09.08.04.05.0min 65432154321654321654321654321x 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 Z 、、、、、（2）设y i 为第i 种单位营养的价格，则数学模型为12312312312312312312123m ax 801501801324180.525970.41430210.84025340.9812100.311150.5,,0w y y y y y y y y y y y y y y y y y y y y y y y =++++≤⎧⎪++≤⎪⎪++≤⎪++≤⎨⎪++≤⎪⎪++≤⎪≥⎩2．写出下列线性规划的对偶问题 （1）⎪⎩⎪⎨⎧≥≤+-≤+-+-=0,451342max 21212121x x x x x x x x 【解】12121212m in 42354,0w y y y y y y y y =-+-+≥-⎧⎪+≥⎨⎪≥⎩（2）⎪⎩⎪⎨⎧≥≥+--=++-=0,8310232min 32132121321x x x x x x x x x x x Z 无约束， 【解】121212212m ax 108223130w y y y y y y y y y =+-=⎧⎪-=-⎪⎨≤⎪⎪≥⎩无约束；（3）⎪⎪⎩⎪⎪⎨⎧≤≥≤++-≥--+=--+-++=无约束43214321432143214321,0,0,66841052678410342max x x x x x x x x x x x x x x x x x x x x Z 【解】123123123123123123m in 8106107416822644530,0w y y y y y y y y y y y y y y y y y y =++++≥⎧⎪+-≥⎪⎪--+≤⎨⎪--+=-⎪≤≥⎪⎩无约束； （4）12341234134123411234m ax 236732696562225100,,,Z x x x x x x x x x x x x x x x x x x x x =-++--+-=⎧⎪+-≥⎪⎪-+-+≤-⎨⎪≤≤⎪≥⎪⎩无约束【解】123412341341234111234m ax 236732696562225100,,,Z x x x x x x x x x x x x x x x x x x x x x =-++--+-=⎧⎪+-≥⎪⎪-+-+≤-⎪⎨≥⎪⎪≤⎪≥⎪⎩无约束对偶问题为： 12345123451212312312345m in 962+510362223566270,000w y y y y y y y y y y y y y y y y y y y y y y x =--+--+-≥-⎧⎪-+=⎪⎪--=⎨⎪-++=-⎪≤≥≤≥⎪⎩无约束；，，， 3．考虑线性规划⎪⎪⎩⎪⎪⎨⎧≥≥+≥+≥++=0,73225442012min 2121212121x x x x x x x x x x Z(1)说明原问题与对偶问题都有最优解；(2)通过解对偶问题由最优表中观察出原问题的最优解； (3)利用公式C B B －1求原问题的最优解； (4)利用互补松弛条件求原问题的最优解． 【解】(1)原问题的对偶问题为123123123m ax 427212453200,1,2,3jw y y y y y y y y y y j =++⎧++≤⎪++≤⎨⎪≥=⎩容易看出原问题和对偶问题都有可行解，如X ＝(2，1)、Y ＝(1，0，1)，由定理2.4知都有最优解。