7第七章习题及答案

1、习 题 71.一工厂利用三种原料能生产五种产品，其有关数据如下表：每万件产品所用原料数产品现在原料（ kg）a bcde数（ kg）甲1210110原料乙1013224丙1222221每万件产品利润（万元）8201020211求最优生产方案.2对目标函数系数c1、c4 分别作灵敏度分析.(3) 对约束条件的常数项b1、b2 分别作灵敏度分析.(4) 假如引进新产品f，已知生产f1 万件要用原材料甲、乙、丙分别为1、2、1 公斤，问f 的利润多少时才有利于投产？假如每万件f 可得到利润12 万元，问f 是否有利于投产？解：设用(5) 假如新增加煤耗不答应超过10 吨的限制，而生产每万件a、b 、

2、c、d、e 产品分别需要煤3、2、1、2、1 吨，问原最优方案是否需要转变？假如转变，应如何转变？x1 , x 2 , x 3 , x 4 , x 5 分别表示方案生产产品a 、b 、c、d、e 的单位数量（万件）模型为：max f8 x 120x 210 x 320 x 421 x 5x1x1s.t.x12x 2x32x 2x 33 x 42 x 3x52x 52 x 410242x521x1 , x 2 , x 3 , x4 ,x 50标准形：minff8 x 120x 210x 320x 421x 5x1x1s.t.x12x 2x32x 2x 33 x 42 x 3x52x 52 x 4

3、x 6x 72x51024x 821x1 , x 2 , x 3 , x4 ,x 5 , x 6 ,x 7 , x 80(1) 基 ba 6 ,a 7 , a 8 对应的初始单纯形表.x1x 2x3x 4x 5x 6x 7x8f8201020210000x 61210110010x 71013201024x 81222200121换基迭代x1x 2x 3x4x 5x 6x7x 8f-2002011-1000-100x21/211/201/21/2005x71013201024x800121-10111连续x 1x2x 3x 4x5x 6x 7x8f-3-2-1100-10-10-220x 51

4、210110010x 71/2-1-10011-3/25/2x 4-1/2-1010-101/21/2所 以 x0,0,0,12 ,10t , f220即 d 生产 1/2 万件， e 生产 10 万件，获得最大利润220 万元 .(2) 对 c1 作灵敏度分析记 c1c18就 f2203 x 12 x 211x 3x 610 x 8x1 （由最优基对应）任 以 ba 5 , a 7 , a 4 为最优基x 1x2x 3x 4x5x 6x 7x8f-3-2-1100-10-10-220x 51210110010x 71/2-1-10011-3/25/2x 4-1/2-1010-101/21/2

5、如要原最优解不变，应满意条件：30 ，3就 x1 的价值系数0c111 时，最优解最优值不变.对 c4 作同样的灵敏度分析任 以 ba 5 , a 7 , a 4 为最优基x 1x2x 3x 4x 5x 6x7x 8f2 -3-2-1100-10-10-2-220-x 51210110010x 71/2-1-10011-3/25/22x 4-1/2-1010-101/21/2如要原最优解不变，应3202020101，所以 0c421，最优值变为2202 .102(3) 对 b1 作灵敏度分析设 b1b1b110b1100最优基 ba 5 , a7 , a 4 213，就新的基解x bb1bb1

6、b202所 以 x b10b1 5b121b12令 x b0 得 到 - 5 2b112 ，即 15 2b121 2 时，最优基不变；对 b4 作灵敏度分析可以得到b 2- 52 ， 即 b143 2 时，最优基不变；(4) 设生产新产品f x9 万件，每单位的利润为c9 万元minff8 x 120 x 210 x 320 x 421x 5c9 x 9x1x1s.t .x12x 2x 32x 2x 33 x42x 3x 52x 52 x 4x 9x62x 9x 72x 5x 91024x821x1 , x2 , x 3 , x 4 ,x 5 , x 6 , x 7 , x8 , x90原最优

7、解x0,0,0, 12 ,10,0, 52 ,0t是该问题的一个可行解；任 取 ba 5 , a 7 , a 4 为基，1c b bac21010020113 2101 21211131222121211820102021000c9=3211001010c911所以c911时， b 不是最优基，x 9 可取非0 值，从而支配生产f 有利；c912111a1p9b9113 223 211 211 2检验数为：1c b bac8201020210001x 1x 2x3x 4x 5x6x 7x 8x 9f-3-2-1100-10-101-220x 512101100110x 71/2-1-10011

8、-3/23/25/2x 4-1/2-1010-101/2-1/21/2变为x1f10431333x 9x 523x 2x38533x 4x5x 650031013x 7x 82-9032103220 53253x 7122333x 414133322500-113332141000333x0004 325 30005 3 t即每万件f 可得利润12 万元时，应生产d 为 43 万件， e 为 253 万件， f 为 53 万件；(5) 新增约束条件3 x12 x2x 32 x 4x 510标准形minff8 x120 x210 x 320 x 421x 5x1 x1s.t .x12 x 2x

9、32 x 2x33 x42x 3x 52 x 52 x 4x 6x 72 x 5x810242113 x 1x1 ,2 x 2x 3, x902 x 4x5x910将（ 1）添入原最优基b a 5 , a7 ,a 4 对应的单纯形表x 1x 2x 3x 4x 5x6x 7x 8x9f-3-2-1100-10-100-220x 512101100010x 71/2-1-10011-3/205/2x 4-1/2-1010-101/201/2x 932121000110*b a5 , a 7 ,a 4 ,a 9 为对偶可行基对偶单纯形法x1x 2x3x 4x 5x6x 7x 8x9f-33-22-1

10、100-1100-10-210x 512101100010x 7-4-4-100-1/210-3/24x 410010-1/2001/20x 8-3-2000-101-11所以最优解x0000100410，即转变为只生产e 为 10 万件；t3.求解以下线性规划问题的对偶问题：（ 2）minf2 x1x 2x33 x 4（3）minf3 x12 x23 x 34x 4x12 x2s.t .x12 x 23 x 33 x 34x414 x 423s.t .x 1x 22x12 x 23x 33x 23 x34 x47 x 34 x 4354x42x1 , x20x 10, x40, x 2 ,

11、x3 无约束解(1) 对偶问题：max gy12 y23 y3y12 y1y322 y21s.t .3 y23 y314 y14 y23y1无约束 , y20,y30(2) 对偶问题：max g3 y15 y22 y3s.t .y12 y13 y14 y1y2 3 y24 y22 y332 y327 y334 y34y10, y20, y3 无约束 , ,3.判定以下说法是否正确，为什么？（ 1）假如线性规划的原问题存在可行解，就其对偶问题也肯定存在可行解.（ 2）假如线性规划的对偶问题无可行解，就其原问题也肯定无可行解.（ 3）假如线性规划的原问题和对偶问题都具有可行解，就其原问题和对偶问题

12、肯定具有有限最优解 .（ 4）已知线性规划问题maxfcx , axb, x0 ，如 x 是它的一个基解，y 是其对偶问题的基解，就恒有cxyb .解：1. ×；如原问题是无界解，就对偶问题无可行解；p167 th3 ；2. ×；（ 1）的逆否命题；3. ； p167 thm44. ×；原问题对偶问题如x , y 为可行解maxfcxmin gyb就 有 cxya xybaxbs.t .x0s.t.yac y0但如 x , y 为基解，就不肯定6.已知线性规划问题minf3x 12 x2 ,x 13 x1s.t .2 x242 x 214x 1x 23x 1 ,

13、x 20（ 1）写出它的对偶问题；（ 2）应用对偶理论证明原问题和对偶问题都存在最优解.解：对偶问题max g4 y114 y23 y3s.t .y12 y13 y22 y2y33y32y1 , y2 , y30（ 1）原问题明显有可行解x0,1 2 t对偶问题可行解y0,0,1 t就由 thm4（ p167）得原问题和对偶问题都有最优解8.某文具用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品；该厂现有工人100 人，每月白坯纸供应量为3 万公斤；已知工人的劳动生产率为：每人每月可生产原稿纸30 捆，或生产日记本30 打，或练习本30 箱；已知原材料消耗为：每捆原稿纸用白坯纸10 3

14、公斤，每打日记本用白坯纸40 3 公斤，每箱练习本用白坯纸80 3 公斤； 又知每生产一捆原稿纸可获利润2 元，生产一打日记本获利3 元，生产一箱练习本获利1 元，试确定：（ 1）现有生产条件下获利最大的方案；（ 2）如白坯纸的供应数量不变，当工人数不足时可招收暂时工，暂时工工资支出为每人每月40 元，就该工厂要不要招收暂时工，招收多少暂时工合适？解：设每月生产原稿纸x 1 捆，日记本x 2 打，练习本x 3 箱标准形minf2 x 13 x 2x 3x1s.t. 10x1 ,x 23 x 1x 340, x 5x43 x 2080 3 x33000x 530000以 ba4a 5为基的初始单纯形表0231003000111103000010 340 380 301变为-9000-10-2-30300011110-10000-10040 340 31对偶单纯形法-80000010 35 31 102000017 31000104 31 31 1 104 31 10所以最优解为x100020000 t ，最优值f8000，最优基ba 2a 1 原问题的对偶问题的最优解y5 3 ,1 10对偶问题min g100 y130000 y211s.t.130 y130 y130 y110 3