运筹学课后习题解答-1
运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题 a） 解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为最优解，即该问题有无穷多最优解，这时的最优值为P47 1.3 用图解法和单纯形法求解线性规划问题 a） 解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点，即，即最优解为这时的最优值为单纯形法：原问题化成标准型为10500b09341008520110500021/5014/51-3/5108/512/501/5010-253/2015/14-3/1410110-1/72/700-5/14-25/14所以有P78 2.4 已知线性规划问题：求: (1) 写出其对偶问题；（2）已知原问题最优解为，试根据对偶理论，直接求出对偶问题的最优解。解：（1）该线性规划问题的对偶问题为：（2）由原问题最优解为，根据互补松弛性得：把代入原线性规划问题的约束中得第四个约束取严格不等号，即 从而有 得所以对偶问题的最优解为，最优值为P79 2.7 考虑如下线性规划问题：（1） 写出其对偶问题；（2）用对偶单纯形法求解原问题；解：（1）该线性规划问题的对偶问题为：（2）在原问题加入三个松弛变量把该线性规划问题化为标准型：-60-40-80000b0-2-3-2-11000-4-4-1-30100-3-2-2-2001-60-40-80000010-5/45/41-1/12080111/43/40-1/400-10-3/2-1/20-1/210-25-350-150011/6005/311/3-5/6805/6102/30-1/31/6402/3011/301/3-2/300-80/30-20/3-50/3 P81 2.12 某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见下表。要求：（a）确定获利最大的产品生产计划；（b）产品A的利润在什么范围内变动时，上述最优计划不变；（c）如果设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？ （d） 如果劳动力数量不增，材料不足时可从市场购买，每单位0.4 元。问该厂要不要购进原材料扩大生产，以购多少为宜。消耗定额产品资源AB C可用量（单位）劳动力材料6 3 53 4 54530产品利润（元/件）3 1 4解：由已知可得，设表示第种产品，从而模型为：a) 用单纯形法求解上述模型为：31400b0456351003034501314000153-101-1463/54/5101/53/5-11/500-4/5351-1/301/3-1/343011-1/52/50-20-1/5-3/5得到最优解为；最优值为 b）设产品A的利润为，则上述模型中目标函数的系数用替代并求解得：1400b351-1/301/3-1/343011-1/52/5-20-1/5-3/50-2+/30-1/5-/3-3/5+/3要最优计划不变，要求有如下的不等式方程组成立解得：从而产品A的利润变化范围为：,即C）设产品D用表示，从已知可得把加入上述模型中求解得：314003b351-1/301/3-1/3243011-1/52/5-4/50-20-1/5-3/51/535/21/2-1/601/6-1/61452/513/151-1/154/150-1/10-59/300-7/30-17/300从而得最优解；最优值为所以产品D值得生产。d）P101 3.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。表3-35产地销地B1B2B3B4产量A1A2A31012227142091611201815255销量5151510解：由已知和最小元素法可得初始方案为产地销地B1B2B3B4产量A1A2A351501501015255销量5151510检验：由于有两个检验数小于零，所以需调整，调整一： 产地销地B1B2B3B4产量A1A2A351501510015255销量5151510 检验：由于还有检验数小于零，所以需调整，调整二：产地销地B1B2B3B4产量A1A2A355101510015255销量5151510检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：表3-36产地销地B1B2B3B4产量A1A2A386549314427372526销量10102015解：因为，即产大于销，所以需添加一个假想的销地，销量为3，构成产销平衡问题，其对应各销地的单位运费都为0。产地销地B1B2B3B4B5产量A1A2A386549314427300072526销量101020153由上表和最小元素法可得初始方案为产地销地B1B2B3B4B5产量A1A2A3911071315372526销量101020153检验： 从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：表3-37 产地销地B1B2B3B4B5产量A1A2A38566M3389746578203030销量2525201020解：因为，即销大于产，所以需添加一个假想的产地，产量为20，构成产销平衡问题，其对应各销地的单位运费都为0。产地销地B1B2B3B4B5产量A1A2A3A485606M3038907460578020303020销量2525201020由上表和最小元素法可得初始方案为产地销地B1B2B3B4B5产量A1A2A3A4520252001015520303020销量2525201020检验： 由于有两个检验数小于零，所以需调整，调整一：产地销地B1B2B3B4B5产量A1A2A3A4205252001051520303020销量2525201020 检验：由于还有检验数小于零，所以需调整，调整二：产地销地B1B2B3B4B5产量A1A2A3A4205252001002020303020销量2525201020检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：P127 4.8 用割平面法求解整数规划问题。a） 解：该问题的松弛问题为：则单纯形法求解该松弛问题得最后一单纯形表为：7900b97/2017/221/2279/210-1/223/2200-28/11-15/11割平面1为：从而有79000b97/2017/221/22079/210-1/223/2200-1/200-7/22-1/22100-28/11-15/1109301001732/71001/7-1/7011/70011/7-22/7000-1-8割平面2为：7
