运筹学部分课后习题解答P47 1、1 用图解法求解线性规划问题a) 12121212min z=23466..424,0x x x x s t x x x x ++≥⎧⎪+≥⎨⎪≥⎩解:由图1可知,该问题的可行域为凸集MABCN,且可知线段BA 上的点都为最优解,即该问题有无穷多最优解,这时的最优值为min3z =23032⨯+⨯=P47 1、3 用图解法与单纯形法求解线性规划问题a)12121212max z=10x 5x 349..528,0x x s t x x x x ++≤⎧⎪+≤⎨⎪≥⎩ 解:由图1可知,该问题的可行域为凸集OABCO,且可知B 点为最优值点,即112122134935282x x x x x x =⎧+=⎧⎪⇒⎨⎨+==⎩⎪⎩,即最优解为*31,2Tx ⎛⎫= ⎪⎝⎭这时的最优值为max 335z =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 =------+=-⎧⎪---+=-⎪⎨---+=-⎪⎪≥=⎩L*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的利润变化范围为:39 3,355⎡⎤-+⎢⎥⎣⎦,即242,455⎡⎤⎢⎥⎣⎦C)设产品D用6x表示,从已知可得16661/5Bc c B Pσ-=-='1661128334122555P B P-⎡⎤-⎡⎤⎢⎥⎡⎤⎢⎥===⎢⎥⎢⎥⎢⎥-⎣⎦⎢⎥-⎣⎦⎢⎥⎣⎦把6x加入上述模型中求解得:jc→ 3 1 4 0 0 3 BCBX b1x2x3x4x5x6x31x5 1 -1/3 0 1/3 -1/3 [2]43x3 0 1 1 -1/5 2/5 -4/5j jC Z-0 -2 0 -1/5 -3/5 1/536x5/2 1/2 -1/6 0 1/6 -1/6 143x5 2/5 13/15 1 -1/15 4/15 0j jC Z--1/10 -59/30 0 -7/30 -17/30 0从而得最优解*(0,0,5,0,0,5/2)Tx=;最优值为max45327.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 515 0 15 0 10 15 25 5 销量5151510检验:产地 销地 产地 销地B1 B2 B3 B4 产量A1A2A35 1515 1015255销量 5 15 15 10检验:B1 B2 B3 B4 产量A1A2A35 51015 1015255 销量 5 15 15 10 检验:产地销地产地销地从上表可以瞧出所有的检验数都大于零,即为最优方案 最小运费为: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 107 13 1537 25 26 销量1010 2015 3检验:产地 销地 产地 销地产地 销地从上表可以瞧出所有的检验数都大于零,即为最优方案最小运费为: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 202520 01015 520 30 30 20 销量25 25 20 10 20检验:产地 销地产地 销地产地 销地B1 B2 B3 B4 B5 产量A1A2A3A420525 2010 51520303020 销量25 25 20 10 20B1 B2 B3 B4 B5 产量A1A2A3A420525 2010 02020303020 销量25 25 20 10 20产地销地产地销地从上表可以瞧出所有的检验数都大于零,即为最优方案最小运费为: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 =+-+≤⎧⎪+≤⎨⎪≥⎩:j c →7 9 0 0 B C B Xb1x 2x 3x 4x9 2x 7/2 0 1 7/22 1/2271x9/2 10 -1/22 3/22 j j C Z --28/11 -15/11割平面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 +=+++-+451541640x x x x ⇒--=--≤456164x x x ⇒+-=4x4 0 0 0 1 6 -7j jC Z-0 0 0 0 -2 -7,即()*4,3Tx=,最优值为max749355z=⨯+⨯=P144 5、3 用图解分析法求目标规划模型c)解:由下图可知,满足min d1-的满意解为区域X2CDX1;满足min d2+的满意解为闭区域BCDEB;满足min2d3-的满意解为图中的A 点,满足min d4-的满意解为图中的 A 点,所以该问题的满意解为图中的点A(24,26) 。