运筹学(胡运权第二版)习题答案(第二章)

运筹学教程（第二版）习题解答,第二章习题解答,2.1写出下列线性规划问题的对偶问题。,第二章习题解答,第二章习题解答,第二章习题解答,第二章习题解答,2.2判断下列说法是否正确，为什么?(1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；答：不对！如原问题是无界解，对偶问题无可行解。(2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解；答：不对！道理同上。,第二章习题解答,(3)在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；答：不对！如果原问题是求极小，结论相反。(4)任何线性规划问题具有惟一的对偶问题。答：结论正确！,第二章习题解答,第二章习题解答,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,2.4给出线性规划问题,(1)写出其对偶问题；(2)用图解法求解对偶问题；(3)利用(2)的结果及根据对偶问题性质写出原问题最优解。,第二章习题解答,(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。,第二章习题解答,2.5给出线性规划问题,(1)写出其对偶问题；(2)利用对偶问题性质证明原问题目标函数值z1。,第二章习题解答,(2)y1=y3=0,y2=1时对偶问题的一个可行解，目标函数值为1，故原问题的目标函数值小于等于1。,第二章习题解答,试根据对偶问题性质证明上述线性规划问题目标函数值无界。,2.6已知线性规划问题,第二章习题解答,由于(1)和(4)是矛盾约束，故对偶问题无可行解。所以原问题目标函数值无界。,解：x1=1,x2=x3=0是原问题的可行解。原问题的对偶问题为：,第二章习题解答,要求：(1)写出其对偶问题；(2)已知原问题最优解为X*=(2，2，4，0)，试根据对偶理论，直接求出对偶问题的最优解。,2.7给出线性规划问题,第二章习题解答,(2)已知原问题最优解为X*=(2，2，4，0)，代入原问题，第4个约束不等式成立，故y4=0。有由于x1,x2,x3大于0，上面对偶问题前3个约束取等号，故得到最优解：y1=4/5,y2,=3/5,y3=1,y4=0,第二章习题解答,2.8已知线性规划问题A和B如下：,第二章习题解答,试分别写出yi同y*i(i1，2，3)间的关系式。,第二章习题解答,第二章习题解答,2.9用对偶单纯形法求解下列线性规划问题。,第二章习题解答,第二章习题解答,要求：(1)写出其对偶问题；(2)用对偶单纯形法求解原问题；(3)用单纯形法求解其对偶问题；(4)对比(2)与(3)中每步计算得到的结果。,2.10考虑如下线性规划问题：,第二章习题解答,第二章习题解答,先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。解：最优解为x1=6,x2=x3=0,Z=12,2.11已知线性规划问题：,第二章习题解答,第二章习题解答,2.12给出线性规划问题,用单纯形法求解得最终单纯形表见下表：,第二章习题解答,试分析下列各种条件下最优解(基)的变化：,第二章习题解答,第二章习题解答,第二章习题解答,2.13分析下列线性规划问题中，当入变化时最优解的变化，并画出Z(入)对入的变化关系图。,第二章习题解答,第二章习题解答,第二章习题解答,第二章习题解答,第二章习题解答,第二章习题解答,第二章习题解答,第二章习题解答,第二章习题解答,2.14某厂生产A，B，C三种产品，其所需劳动力、材料等有关数据见下表：,第二章习题解答,要求：(1)确定获利最大的产品生产计划；答：最优生产计划为：x1=5,x2=0,x3=3,Z=27；,第二章习题解答,(2)产品A的利润在什么范围内变动时，上述最优计划不变；答：产品A的利润在2.4，4.8内变动，生产计划不变(-3/59/5)；,第二章习题解答,(3)如果设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产?答：增加新产品D，最优解为x1=0,x2=0,x3=5,x6=2.5Z=27.5,第二章习题解答,(4)如果劳动力数量不增，材料不足时可从市场购买，每单位0.4元。问该厂要不要购进原材料扩大生产，以购多少为宜。答：由（1）可知材料的对偶价格是0.6元，大于市场价格。故应该购进原材料进行生产。当购进的原材料达到15时，利润达到最大值36。,第二章习题解答,2.15已知线性规划问题：,当t1=t2=0时求解得最终单纯形表见下表：,第二章习题解答,(1)确定cl，c2，c3，all，a12，a13，a2l,a22和b1,b2的值；解：a11=0,a12=1,a13=2a21=3,a22=-1,a23=1c1=6,c2=-2,c3=10,第二章习题