运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题a）12121212min z=23466 ..424,0x xx xs t x xx x++≥⎧⎪+≥⎨⎪≥⎩解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为最优解，即该问题有无穷多最优解，这时的最优值为min 3z=23032⨯+⨯= P47 1.3 用图解法和单纯形法求解线性规划问题a）12121212max z=10x5x349 ..528,0x xs t x xx x++≤⎧⎪+≤⎨⎪≥⎩解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点，即112122134935282xx xx x x=⎧+=⎧⎪⇒⎨⎨+==⎩⎪⎩，即最优解为*31,2Tx⎛⎫= ⎪⎝⎭这时的最优值为max335z=101522⨯+⨯=单纯形法： 原问题化成标准型为121231241234max z=10x 5x 349..528,,,0x x x s t x x x x x x x +++=⎧⎪++=⎨⎪≥⎩ j c →105B CB X b 1x2x3x4x0 3x 9 3 4 1 0 04x8[5] 2 0 1 j j C Z -105 0 0 0 3x 21/5 0 [14/5] 1 -3/5 101x8/51 2/5 0 1/5 j j C Z -1 0 -2 5 2x 3/2 0 1 5/14 -3/14 101x11 0 -1/72/7j j C Z --5/14 -25/14所以有*max 33351,,1015222Tx z ⎛⎫==⨯+⨯= ⎪⎝⎭P78 2.4 已知线性规划问题：1234124122341231234max24382669,,,0z x x x x x x x x x x x x x x x x x x x =+++++≤⎧⎪+≤⎪⎪++≤⎨⎪++≤⎪≥⎪⎩求: (1) 写出其对偶问题；（2）已知原问题最优解为)0,4,2,2(*=X ，试根据对偶理论，直接求出对偶问题的最优解。
解：（1）该线性规划问题的对偶问题为：1234124123434131234min8669223411,,,0w y y y y y y y y y y y y y y y y y y y =+++++≥⎧⎪+++≥⎪⎪+≥⎨⎪+≥⎪≥⎪⎩（2）由原问题最优解为)0,4,2,2(*=X ，根据互补松弛性得：12412343422341y y y y y y y y y ++=⎧⎪+++=⎨⎪+=⎩把)0,4,2,2(*=X 代入原线性规划问题的约束中得第四个约束取严格不等号，即4224890y ++=<⇒=从而有12123322341y y y y y y +=⎧⎪++=⎨⎪=⎩得123443,,1,055y y y y ====所以对偶问题的最优解为*43(,,1,0)55T y =，最优值为min 16w =P79 2.7 考虑如下线性规划问题：123123123123123min 6040803224342223,,0z x x x x x x x x x x x x x x x =++++≥⎧⎪++≥⎪⎨++≥⎪⎪≥⎩（1）写出其对偶问题；（2）用对偶单纯形法求解原问题； 解：（1）该线性规划问题的对偶问题为：123123123123123max 2433426022403280,,0w y y y y y y y y y y y y y y y =++++≤⎧⎪++≤⎪⎨++≤⎪⎪≥⎩（2）在原问题加入三个松弛变量456,,x x x 把该线性规划问题化为标准型：123123412351236max 60408032243422230,1,,6j z x x x x x x x x x x x x x x x x j =------+=-⎧⎪---+=-⎪⎨---+=-⎪⎪≥=⎩*max (,,0),604080063633T x z ==⨯+⨯+⨯=P81 2.12 某厂生产A 、B 、C 三种产品，其所需劳动力、材料等有关数据见下表。
要求：（a ）确定获利最大的产品生产计划；（b ）产品A 的利润在什么范围内变动时，上述最优计划不变；（c ）如果设计一种新产品D ，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？ （d ） 如果劳动力数量不增，材料不足时可从市场购买，每单位0.4 元。
问该厂要不要购进原材料扩大生产，以购多少为宜。
解：由已知可得，设j x 表示第j 种产品，从而模型为：123123123123max 3463545..34530,,0z x x x x x x s t x x x x x x =++++≤⎧⎪++≤⎨⎪≥⎩a) 用单纯形法求解上述模型为：得到最优解为*(5,0,3)T x =；最优值为max 354327z =⨯+⨯=b ）设产品A 的利润为3λ+，则上述模型中目标函数1x 的系数用3λ+替代并求解得：要最优计划不变，要求有如下的不等式方程组成立20310533053λλλ⎧-+≤⎪⎪⎪--≤⎨⎪⎪-+≤⎪⎩解得：3955λ-≤≤ 从而产品A 的利润变化范围为：393,355⎡⎤-+⎢⎥⎣⎦,即242,455⎡⎤⎢⎥⎣⎦C ）设产品D 用6x 表示，从已知可得16661/5B c c B P σ-=-='1661128334122555P B P -⎡⎤-⎡⎤⎢⎥⎡⎤⎢⎥===⎢⎥⎢⎥⎢⎥-⎣⎦⎢⎥-⎣⎦⎢⎥⎣⎦把6x 加入上述模型中求解得：从而得最优解*(0,0,5,0,0,5/2)T x =；最优值为max 45327.5272z =⨯+⨯=> 所以产品D 值得生产。
P101 3.1已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。
表3-35B 1 B 2 B 3 B 4 产量 A 1 A 2 A 3 10 12 2 2 7 14 20 9 16 11 20 18 15 25 5 销量5151510产地 销地解：因为∑∑===4131j j i i b a ，即产销平衡.所以由已知和最小元素法可得初始方案为B1 B2 B3 B4 产量 A1A2 A3 5 15 0 15 0 10 15 25 5 销量5151510检验：由于有两个检验数小于零，所以需调整，调整一：B1 B2 B3 B4 产量 A1 A2 A3 5 15 0 15 10 0 15 25 5 销量5151510检验：由于还有检验数小于零，所以需调整，调整二：产地 销地产地销地B1 B2 B3 B4 产量 A1A2 A3 5 5 10 15 10 0 15 25 5 销量5151510检验：从上表可以看出所有的检验数都大于零，即为最优方案 最小运费为：min 25257109151110180335z =⨯+⨯+⨯+⨯+⨯+⨯=表 B 1 B 2 B 3 B 4 产量 A 1 A 2 A 3 8 6 5 4 9 3 1 4 4 2 7 3 7 25 26 销量10102015解：因为34115855i j i j a b ===>=∑∑，即产大于销，所以需添加一个假想的销地，销量为3，构成产销平衡问题，其对应各销地的单位运费都为0。
B1 B2B3B4B5 产量 A1A2 A3 8 6 54 9 31 4 42 7 30 0 0 7 25 26 销量 10 10 20 153由上表和最小元素法可得初始方案为产地 销地产地 销地 产地 销地B1 B2 B3 B4 B5 产量 A1A2 A3 9 1 10 7 13 15 3 7 25 26 销量101020153检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：min 69513101741331503193z =⨯+⨯+⨯+⨯+⨯+⨯+⨯=表3-37B1 B2 B3 B4 B5 产量 A1A2 A3 8 5 6 6 M 3 3 8 9 7 4 6 5 7 8 20 30 30 销量2525201020解：因为351180100i j i j a b ===<=∑∑，即销大于产，所以需添加一个假想的产地，产量为20，构成产销平衡问题，其对应各销地的单位运费都为0。
B1 B2 B3 B4 B5 产量 A1A2 A3 A4 8 5 6 0 6 M 3 0 3 8 9 0 7 4 6 0 5 7 8 0 20 30 30 20 销量2525201020产地 销地产地 销地产地 销地由上表和最小元素法可得初始方案为 B1 B2 B3 B4 B5 产量 A1A2 A3 A4 5 20 25 20 0 10 15 5 20 30 30 20 销量2525201020检验：由于有两个检验数小于零，所以需调整，调整一：B1 B2 B3 B4 B5 产量 A1 A2 A3 A420 5 25 20 0 10 5 15 20 30 30 20 销量 25 25201020检验：产地 销地产地销地由于还有检验数小于零，所以需调整，调整二： B1 B2 B3 B4 B5 产量 A1 A2 A3 A420 5 25 20 0 10 0 20 20 30 30 20 销量 2525201020检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：min 320520410653258002000305z =⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯=P127 4.8 用割平面法求解整数规划问题。
a ） 12121212max 7936735,0,z x x x x x x x x =+-+≤⎧⎪+≤⎨⎪≥⎩且为整数解：该问题的松弛问题为：12121212max 7936735,0z x x x x x x x x =+-+≤⎧⎪+≤⎨⎪≥⎩则单纯形法求解该松弛问题得最后一单纯形表为：产地销地割平面1为：234(31/2)(07/22)(01/22)x x x +=++++3421713022222x x x ⇒--=-≤34571122222x x x ⇒+-=割平面2为：145(44/7)(01/7)(16/7)x x x +=+++-+451541640777x x x x ⇒--=--≤456164777x x x ⇒+-=()*4,3Tx =，最优值为max 749355z =⨯+⨯=P144 5.3 用图解分析法求目标规划模型c ）解:由下图可知，满足min d 1-的满意解为区域X2CDX1；满足min d 2+的满意解为闭区域BCDEB ； 满足min 2d 3-的满意解为图中的A 点,满足min d 4-的满意解为图中的A 点，所以该问题的满意解为图中的点A （24，x 1 + x 2 + d 1- - d 1+= 40x 1 + x 2 + d 2- - d 2+= 40+10=50 x 1 + d 3- - d 3+= 24 x 2 + d 4- - d 4+= 30min Z = P 1 d 1-+ P 2 d 2++ P 3（2d 3- +1d 4-）s.t.x 1 、x 2 、d 1+、d 1-、d 2+、d 2- 、d 3+、d 3- 、d 4+、d 4- ≥ 026） 。