2014-1-3运筹学64学时总复习.docVIP

运筹学总复习 2014.1.3 复习内容与要求： 1 建模方面：目标规划、动态规划、整数规划 2 计算方面：线性规划、对偶规划、运输问题、指派问题、割平面算法、最大流、网络计划、对策论、决策论。 【例题1】用单纯形法求解线性规划问题的解。 解：添加三个松弛变量，把上述规划化成标准型 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 基变量 b X1 X2 X3 X4 X5 X3 4 1 0 1 0 0 X4 6 0 1 0 1 0 X5 18 3 2 0 0 1 0 2 5 0 0 0 基变量 b X1 X2 X3 X4 X5 X3 4 1 0 1 0 0 X2 6 0 1 0 1 0 X5 6 3 0 0 -2 1 -30 2 0 0 -5 0 基变量 b X1 X2 X3 X4 X5 X3 2 0 0 1 2/3 -1/3 X2 6 0 1 0 1 0 X1 2 1 0 0 -2/3 1/3 -34 0 0 -5 -11/3 -2/3 最优解是（2，6）最优值是34 求：（1）线性规划问题的最优解；（2）求对偶问题的数学模型及其最优解；(3) 最优解不变的情况下，求产品A的利润允许变化范围；（4）假定能以10元的价格购进15单位的材料，这样做是否有利，为什么？（5）当可利用的资源增加到60单位时，求最优解。（6）当产品B的原材料消耗减少为2个单位时，是否影响当前的最优解，为什么？（7）增加约束条件2x1+x2+3x3≤20，对原最优解有何影响，对对偶解有何影响？ 解答：（1）线性规划问题的最优解 首先将问题标准化： cj 3 1 5 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5 45 30 6 3 3 4 5 【5】 1 0 0 1 9 6 3 1 5 0 0 0 5 x4 x3 15 6 3 3/5 -1 4/5 0 1 1 0 -1 1/5 0 -3 0 0 -1 最优解为X*=(x1,x2,x3,x4,x5)T=(0,0,6,15,0)T，最优目标值z*=30 （2）求对偶问题的数学模型及其最优解； y1*=0,y2*=1 (3) 最优解不变的情况下，求产品A的利润允许变化范围； 最优解不变的情况下， （4）假定能以10元的价格购进15单位的材料，这样做是否有利，为什么？ 有利 单位材料的影子价格是1元，10元钱购进15单位的材料的单位价格为2/3元，低于影子价格。同时，在保持最优基不变的情况下 购进15吨的原材料，最优基不变。该材料的影子价格仍为1元。 （5）当可利用的资源增加到60单位时，求最优解。 cj 3 1 5 0 0 CB XB b x1 x2 x3 x4 x5 0 5 x4 x3 -15 12 3 3/5 -1 4/5 0 1 1 0 【-1】 1/5 0 -3 0 0 -1 0 5 x5 x3 15 9 -3 6/5 1 3/5 0 1 -1 1/5 1 0 -3 -2 0 -1 0 最优解为X*=(x1,x2,x3,x4,x5)T=(0,0,9,0,15)T，最优目标值z*=45 （6）当产品B的原材料消耗减少为2个单位时，是否影响当前的最优解，为什么？ x2在最有表是非基变量，该产品的原材料消耗只影响x2的检验数。 （7）增加约束条件2x1+x2+3x3≤20，对原最优解有何影响，对对偶解有何影响？ 增加的约束条件，相当于增加了一个约束方程 cj 2 4 1 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 5 0 x4 x3 x6 15 6 20 3 3/5 2 -1 4/5 1 0 1 3 1 0 0 -1 1/5 0 0 0 1 0 -3 0 0 -1 0 0 5 0 x4 x3 x6 15 6 2 3 3/5 4/5 -1 4/5 -7/5 0 1 0 1 0 0 -1 1/5 -3/5 0 0 1 0 -3 0 0 -1 0 对原问题的最优解无影响，对对偶问题的最优解也无影响。 【例题3】已知如下线性规划问题： 已知其对偶问题的最优解为Y＊=(4,1)。试用对偶理论求出原问题的最优解。 解：对偶问题是：　　　　　　　　 设原问题最优解为X＊＝(x1，x2 ，x3，x4)T , 将Y＊带入对偶问题约束条件中，得(