运筹学黄皮习题答案.pptx

运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 1 1November 1,2010November 1,2010同样适合第三版黄皮版运筹学教程（第二版）运筹学教程（第二版）习题解答习题解答电话：电话：5108157(H)，5107443(O)E-mail:Hongwen9509_安徽大学管理学院安徽大学管理学院安徽大学管理学院安徽大学管理学院洪洪 文文运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 3 3November 1,2010November 1,2010第二章习题解答第二章习题解答 2.1 写出下列线性规划问题的对偶问题。写出下列线性规划问题的对偶问题。运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 4 4November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 5 5November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 6 6November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 7 7November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 8 8November 1,2010November 1,2010 2.2 判断下列说法是否正确，为什么判断下列说法是否正确，为什么?(1)如果线性规划的原问题存在可行解，则其对偶如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；问题也一定存在可行解；答：不对！如原问题是无界解，对偶问题无可行答：不对！如原问题是无界解，对偶问题无可行解。解。(2)如果线性规划的对偶问题无可行解，则原问题如果线性规划的对偶问题无可行解，则原问题也一定无可行解；也一定无可行解；答：不对！道理同上。答：不对！道理同上。第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 9 9November 1,2010November 1,2010 (3)在互为对偶的一对原问题与对偶问题中，不管在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；一定不超过其对偶问题可行解的目标函数值；答：不对！如果原问题是求极小，结论相反。答：不对！如果原问题是求极小，结论相反。(4)任何线性规划问题具有惟一的对偶问题。任何线性规划问题具有惟一的对偶问题。答：结论正确！答：结论正确！第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 1010November 1,2010November 1,2010第二章习题解答第二章习题解答 2.3 已知某求极大化线性规划问题用单纯形已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。所示，求表中各括弧内未知数的值。解：解：l=1,k=0,h=-1/2,a=2,c=3,b=10,e=5/4,f=-1/2,d=1/4,g=-3/4,i=-1/4,j=-1/4运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 1111November 1,2010November 1,2010Cj322000CB基基bX1X2X3X4X5X60X1(b)1111000X215(a)120100X3202(c)1001CjZj 322000 0X45/400(d)(l)-1/4-1/43X125/410(e)03/4(i)2X25/201(f)0(h)1/2CjZj 0(k)(g)0-5/4(j)运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 1212November 1,2010November 1,2010 2.4 给出线性规划问题给出线性规划问题 (1)写出其对偶问题；写出其对偶问题；(2)用图解法求解对偶问题；用图解法求解对偶问题；(3)利用利用(2)的结果及根据对偶问题性质写出原问题最优的结果及根据对偶问题性质写出原问题最优解。解。第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 1313November 1,2010November 1,2010 (2)最优解是：最优解是：y1=-8/5,y2=1/5,目标函数值目标函数值-19/5。(3)由于由于 y1=-8/5,y2=1/5都不等于零，原问题中的约都不等于零，原问题中的约束取等号。又上面第束取等号。又上面第4个约束不等号成立，故个约束不等号成立，故x4=0，令，令x3=0就可以得到最优解：就可以得到最优解：x1=8/5,x2=1/5。第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 1414November 1,2010November 1,2010 2.5 给出线性规划问题给出线性规划问题 (1)写写出出其其对对偶偶问问题题；(2)利利用用对对偶偶问问题题性性质质证证明明原问题目标函数值原问题目标函数值z1。第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 1515November 1,2010November 1,2010 (2)y1=y3=0,y2=1时时对对偶偶问问题题的的一一个个可可行行解解，目目标标函数值为函数值为1，故原问题的目标函数值小于等于，故原问题的目标函数值小于等于1。第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 1616November 1,2010November 1,2010 试根据对偶问题性质证明上述线性规划问题目标试根据对偶问题性质证明上述线性规划问题目标函数值无界。函数值无界。2.6 已知线性规划问题已知线性规划问题 第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 1717November 1,2010November 1,2010 由于由于(1)和和(4)是矛盾约束，故对偶问题无可行解。是矛盾约束，故对偶问题无可行解。所以原问题目标函数值无界。所以原问题目标函数值无界。解：解：x1=1,x2=x3=0是原问题的可行解。原问题的对是原问题的可行解。原问题的对偶问题为：偶问题为：第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 1818November 1,2010November 1,2010 要求：要求：(1)写出其对偶问题；写出其对偶问题；(2)已知原问题最优解已知原问题最优解为为X*=(2，2，4，0)，试根据对偶理论，直接求出对偶，试根据对偶理论，直接求出对偶问题的最优解。问题的最优解。2.7 2.7 给出线性规划问题给出线性规划问题第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 1919November 1,2010November 1,2010 (2)已知原问题最优解为已知原问题最优解为X*=(2，2，4，0)，代入，代入原问题，第原问题，第4个约束不等式成立，故个约束不等式成立，故y4=0。有由于。有由于x1,x2,x3大于大于0，上面对偶问题前，上面对偶问题前3个约束取等号，故得个约束取等号，故得到最优解：到最优解：y1=4/5,y2,=3/5,y3=1,y4=0第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 2020November 1,2010November 1,2010 2.8 已知线性规划问题已知线性规划问题A和和B如下：如下：第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 2121November 1,2010November 1,2010 试分别写出试分别写出yi同同y*i(i1，2，3)间的关系式。间的关系式。第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 2222November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 2323November 1,2010November 1,2010 2.9 用对偶单纯形法求解下列线性规划问题。用对偶单纯形法求解下列线性规划问题。第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 2424November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 2525November 1,2010November 1,2010 要求：要求：(1)写出其对偶问题；写出其对偶问题；(2)用对偶单纯形法求用对偶单纯形法求解原问题；解原问题；(3)用单纯形法求解其对偶问题；用单纯形法求解其对偶问题；(4)对比对比(2)与与(3)中每步计算得到的结果。中每步计算得到的结果。2.10 考虑如下线性规划问题：考虑如下线性规划问题：第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 2626November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 2727November 1,2010November 1,2010 先用单纯形法求出最优解，再分析在下列先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。条件单独变化的情况下最优解的变化。解：最优解为解：最优解为x x1 1=6,x=6,x2 2=x=x3 3=0,Z=12=0,Z=12 2.11 已知线性规划问题：已知线性规划问题：第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 2828November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 2929November 1,2010November 1,2010 2.12 2.12 给出线性规划问题给出线性规划问题 用单纯形法求解得最终单纯形表见下表：用单纯形法求解得最终单纯形表见下表：第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 3030November 1,2010November 1,2010项项 目目23100CB 基基 bX1X2X3X4X52 X1 610-14-13 X2 1012-11CjZj00-3-5-1 试分析下列各种条件下最优解试分析下列各种条件下最优解(基基)的变化：的变化：第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 3131November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 3232November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 3333November 1,2010November 1,2010 2.13 分析下列线性规划问题中，当入变化时最优分析下列线性规划问题中，当入变化时最优解的变化，并画出解的变化，并画出Z(入入)对入的变化关系图。对入的变化关系图。第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 3434November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 3535November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 3636November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 3737November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 3838November 1,2010November 1,2010第二章习题解答第二章习题解答Cj325000CB基基bX1X2X3X4X5X62X25-1/4 101/2-1/4 05X3303/20101/200X610200-211CjZj-700-1-20运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 3939November 1,2010November 1,2010第二章习题解答第二章习题解答Cj325000CB基基 bX1X2X3X4X5X62X25-1/4 101/2-1/4 05X330+3/20101/200X610-3 200-211CjZj-700-1-20运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 4040November 1,2010November 1,2010第二章习题解答第二章习题解答Cj325000CB基基bX1X2X3X4X5X62X215-7/4 1/410001/45X330+3/20101/200X43/2-5-1001-1/2-1/2CjZj-700-1-20运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 4141November 1,2010November 1,2010第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 4242November 1,2010November 1,2010 2.14 2.14 某厂生产某厂生产A A，B B，C C三种产品，其所需劳动力、三种产品，其所需劳动力、材料等有关数据见材料等有关数据见下下表表：产品产品资源资源ABC可用量可用量（单位）（单位）劳动力劳动力63545材料材料34530产品利润产品利润（元（元/件）件）314第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 4343November 1,2010November 1,2010 要求：要求：(1)(1)确定获利最大的产品生产计划；确定获利最大的产品生产计划；答：最优生产计划为：答：最优生产计划为：x x1 1=5,x=5,x2 2=0,x=0,x3 3=3,Z=27=3,Z=27；第二章习题解答第二章习题解答项项 目目31400CB 基基 bX1X2X3X4X53 X1 51-1/301/3-1/34 X3 3011-1/52/5CjZj0-20-1/5-3/5运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 4444November 1,2010November 1,2010 (2)(2)产品产品A A的利润在什么范围内变动时，上述最优的利润在什么范围内变动时，上述最优计划不变；计划不变；答：产品答：产品A A的利润在的利润在2.42.4，4.84.8内变动，生产计内变动，生产计划不变划不变(-3/5(-3/5 9/5)9/5)；第二章习题解答第二章习题解答项项 目目3+1400CB 基基 bX1X2X3X4X53+X1 51-1/301/3-1/34 X3 3011-1/52/5CjZj0/3-20-/3-1/5/3-3/5运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 4545November 1,2010November 1,2010 (3)(3)如果设计一种新产品如果设计一种新产品D D，单件劳动力消耗为，单件劳动力消耗为8 8单位，材料消耗为单位，材料消耗为2 2单位，每件可获利单位，每件可获利3 3元，问该种产元，问该种产品是否值得生产品是否值得生产?答：增加新产品答：增加新产品D D，最优解为，最优解为x x1 1=0,x=0,x2 2=0,x=0,x3 3=5,=5,x x6 6=2.5 Z=27.5 =2.5 Z=27.5 第二章习题解答第二章习题解答项项 目目3140 0 3CB 基基 bX1X2X3X4 X5 X63 X1 51-1/301/3 -1/3 2 4 X3 3011-1/5 2/5 -4/5CjZj0-20-1/5 -3/5 1/5运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 4646November 1,2010November 1,2010 (4)(4)如果劳动力数量不增，材料不足时可从市场如果劳动力数量不增，材料不足时可从市场购买，每单位购买，每单位0.40.4元。问该厂要不要购进原材料扩大元。问该厂要不要购进原材料扩大生产，以购多少为宜。生产，以购多少为宜。答：由（答：由（1 1）可知材料的对偶价格是）可知材料的对偶价格是0.60.6元，大于元，大于市场价格。故应该购进原材料进行生产。当购进的原市场价格。故应该购进原材料进行生产。当购进的原材料达到材料达到1515时，利润达到最大值时，利润达到最大值3636。第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 4747November 1,2010November 1,2010 2.15 已知线性规划问题：已知线性规划问题：当当t1=t2=0时求解得最终单纯形表见下表：时求解得最终单纯形表见下表：第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 4848November 1,2010November 1,2010 (1)(1)确确定定c cl l，c c2 2，c c3 3，a allll，a a1212，a a1313，a a2l2l,a,a2222和和b b1 1,b,b2 2的值；的值；解：解：a a1111=0,=0,a a1212=1,=1,a a1313=2=2a a2121=3,=3,a a2222=-1,=-1,a a2323=1=1c c1 1=6,=6,c c2 2=-2,=-2,c c3 3=10=10项项 目目c1c2c300CB 基基 bX1X2X3X4X5c1 X4 5/201/211/20c2 X5 5/21-1/20-1/61/3CjZj0-40-4-2第二章习题解答第二章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 4949November 1,2010November 1,2010 (2)(2)当当t t2 2=0=0时时，t t1 1在在什什么么范范围围内内变变化化上上述述最最优优解解不变；不变；答：答：t t1 1在在-6,8-6,8之间变动时，最优解不变。之间变动时，最优解不变。(3)(3)当当t t1 1=0=0时时，t t2 2在在什什么么范范围围内内变变化化上上述述最最优优基基不变。不变。答：答：t t2 2在在-5/3,15-5/3,15之间变动时，最优基不变。之间变动时，最优基不变。第二章习题解答第二章习题解答