《运筹学部分课后习题解答-1》由会员分享，可在线阅读，更多相关《运筹学部分课后习题解答-1（20页珍藏版）》请在金锄头文库上搜索。
1、运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题a） 12121212min z=23466 . . 424 ,0xxxx stxx x x 解：由图 1 可知，该问题的可行域为凸集 MABCN，且可知线段 BA 上的点都为最优解，即该问题有无穷多最优解，这时的最优值为min3z=23 032 P47 1.3 用图解法和单纯形法求解线性规划问题a） 12121212max z=10x5x349 . . 528 ,0xx stxx x x 解：由图 1 可知，该问题的可行域为凸集 OABCO，且可知 B 点为最优值点，即，即最优解为1 121221349 35282xxx xxx*
2、31,2T x这时的最优值为max335z=10 1 522 单纯形法：原问题化成标准型为121231241234max z=10x5x349. . 528,0xxxstxxxx x x x jc 10500BCBXb1x2x3x4x0 3x934100 4x85201jjCZ105000 3x21/5014/51-3/510 1x8/512/501/5jjCZ010-25 2x3/2015/14-3/1410 1x110-1/72/7jjCZ00-5/14-25/14所以有* max33351,10 1 5222T xz P78 2.4 已知线性规划问题：123412412234123123
3、4max24382669,0zxxxxxxxxxxxxxxxx x x x 求: (1) 写出其对偶问题；（2）已知原问题最优解为，试根据对)0 , 4 , 2 , 2(*X偶理论，直接求出对偶问题的最优解。解：（1）该线性规划问题的对偶问题为：1234124123434131234min8669223411,0wyyyyyyyyyyyyyyyy yyy （2）由原问题最优解为，根据互补松弛性得：)0 , 4 , 2 , 2(*X12412343422341yyyyyyyyy 把代入原线性规划问题的约束中得第四个约束取严格不等号，)0 , 4 , 2 , 2(*X即4224890y从而有121
4、23322341yyyyyy 得123443,1,055yyyy所以对偶问题的最优解为，最优值为*4 3( ,1,0)5 5Ty min16wP79 2.7 考虑如下线性规划问题：123123123123123min6040803224342223,0zxxxxxxxxxxxxx x x （1）写出其对偶问题；（2）用对偶单纯形法求解原问题；解：（1）该线性规划问题的对偶问题为：123123123123123max24334260 2240 3280 ,0wyyyyyy yyy yyy y yy （2）在原问题加入三个松弛变量把该线性规划问题化为标准型：456,x x x12312341235
5、1236max604080322 434 2223 0,1,6jzxxxxxxx xxxx xxxx xj jc -60-40-80000BCBXb1x2x3x4x5x6x0 4x-2-3-2-11000 5x-4-4-1-30100 6x-3-2-2-2001jjCZ-60-40-800000 4x10-5/45/41-1/12080 1x111/43/40-1/400 6x-10-3/2-1/20-1/21jjCZ0-25-350-1500 4x11/6005/311/3-5/680 1x5/6102/30-1/31/640 2x2/3011/301/3-2/3jjCZ00-80/30-2
6、0/3-50/3* max5 252230( ,0) ,604080 06 3633TxzP81 2.12 某厂生产 A、B、C 三种产品，其所需劳动力、材料等有关数据见下表。要求：（a）确定获利最大的产品生产计划；（b）产品 A 的利润在什么范围内变动时，上述最优计划不变；（c）如果设计一种新产品 D，单件劳动力消耗为 8 单位，材料消耗为 2 单位，每件可获利 3 元，问该种产品是否值得生产？ （d） 如果劳动力数量不增，材料不足时可从市场购买，每单位 0.4 元。问该厂要不要购进原材料扩大生产，以购多少为宜。A B C可用量（单位）劳动力材 料6 3 53 4 54530产品利润（元/件
7、）3 1 4解：由已知可得，设表示第种产品，从而模型为：jxj123123123123max3463545 . . 34530 ,0zxxxxxx stxxx x x x a) 用单纯形法求解上述模型为：jc 31400产品资源消 耗 定 额BCBXb1x2x3x4x5x0 4x45635100 5x3034501jjCZ314000 4x153-101-14 3x63/54/5101/5jjCZ3/5-11/500-4/53 1x51-1/301/3-1/34 3x3011-1/52/5jjCZ0-20-1/5-3/5得到最优解为；最优值为*(5,0,3)Tx max3 54 327z b）
8、设产品 A 的利润为，则上述模型中目标函数的系数用替代并求31x3解得：jc 31400BCBXb1x2x3x4x5x3 1x51-1/301/3-1/34 3x3011-1/52/5jjCZ-20-1/5-3/5jjCZ0-2+/30-1/5-/3-3/5+/3要最优计划不变，要求有如下的不等式方程组成立解得：203 1053 3053 39 55从而产品 A 的利润变化范围为：,即393,355242, 455 C）设产品 D 用表示，从已知可得6x1 6661/5Bcc B P1 661128334122555PB P 把加入上述模型中求解得：6xjc 314003BCBXb1x2x3x
9、4x5x6x3 1x51-1/301/3-1/324 3x3011-1/52/5-4/5jjCZ0-20-1/5-3/51/53 6x5/21/2-1/601/6-1/614 3x52/513/151-1/154/150jjCZ-1/10-59/300-7/30-17/300从而得最优解；最优值为*(0,0,5,0,0,5/2)Tx max54 5327.5272z 所以产品 D 值得生产。d）P101 3.1 已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最优解及最小运费。表 3-35B1B2B3B4产量A1 A2 A310 12 22 7 1420 9 1611 20 18
10、15 25 5销量5151510解：由已知和最小元素法可得初始方案为B1B1B2B2B3B3B4B4产量产量A1A1 A2A2 A3A3515 015 0101515 2525 5 5销量销量5 5151515151010 检验：由于有两个检验数小于零，所以需调整，调整一：B1B1B2B2B3B3B4B4产量产量A1A1 A2A2 A3A3515 01510 01515 2525 5 5 销量销量5 5151515151010检验：产地销地产地销地产地销地由于还有检验数小于零，所以需调整，调整二：B1B1B2B2B3B3B4B4产量产量A1A1 A2A2 A3A355 10151001515
11、2525 5 5销量销量5 5151515151010 检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：min2 52 57 109 15 11 10 18 0335z 表 3-36B1B2B3B4产量A1 A2 A38 6 54 9 31 4 42 7 37 25 26销量10102015解：因为，即产大于销，所以需添加一个假想的销地，销34115855ij ijab量为 3，构成产销平衡问题，其对应各销地的单位运费都为 0。产地销地产地销地B1B1B2B2B3B3B4B4B5B5产量产量A1A1 A2A2 A3A38 6 54 9 31 4 42 7 30 0 07 7
12、2525 2626销量销量10101010202015153 3由上表和最小元素法可得初始方案为B1B1B2B2B3B3B4B4B5B5产量产量A1A1 A2A2 A3A39 1107 13 1537 7 2525 2626销量销量10101010202015153 3检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：min6 95 1 3 10 1 74 133 150 3193z 表 3-37 B1B1B2B2B3B3B4B4B5B5产量产量A1A1 A2A2 A3A38 5 66 M 33 8 97 4 65 7 82020 3030 3030销量销量2525252520
13、2010102020解：因为，即销大于产，所以需添加一个假想的产地，351180100ij ijab产量为 20，构成产销平衡问题，其对应各销地的单位运费都为 0。产地销地产地销地产地销地B1B1B2B2B3B3B4B4B5B5产量产量A1A1 A2A2 A3A3 A4A48 5 6 06 M 3 03 8 9 07 4 6 05 7 8 02020 3030 3030 2020 销量销量25252525202010102020由上表和最小元素法可得初始方案为B1B1B2B2B3B3B4B4B5B5产量产量A1A1 A2A2 A3A3 A4A4520252001015 52020 3030 3
14、030 2020 销量销量25252525202010102020检验：由于有两个检验数小于零，所以需调整，调整一：B1B1B2B2B3B3B4B4B5B5产量产量A1A1 A2A2 A3A3 A4A42052520010 5 152020 3030 3030 2020 销量销量25252525202010102020检验：产地销地产地销地产地销地由于还有检验数小于零，所以需调整，调整二：B1B1B2B2B3B3B4B4B5B5产量产量A1A1 A2A2 A3A3 A4A420 52520010 0 202020 3030 3030 2020 销量销量25252525202010102020 检验：从上表可以看出所有的检验数都大于零，即为最优方案最小运费为：min3 205 204 106 53 258 00 200 0305z P127 4.8 用割平面法求解整数规划问题。a） 12121212max7936735,0,zxxxxxxx x 且为整数解：该问题的松弛问题为：产地销地12121212max7936 735 ,0zxxxx xx x x 则单纯形法求解该松弛问题得最后一单纯形表为：jc 79
