最优化方法习题答案

1、习题一 1.1 利用图解法求下列线性规划问题： （1） 21 xxzmax 0 x,x 5x2x 2xx3 . t . s 21 21 21 解：根据条件，可行域为下面图形中的阴影部分， ，有图形可知，原问题在 A 点取得最优值， 最优值 z=5 （2） 21 x6xzmin 0 x,x 7xx 1xx2 . t . s 21 21 21 解：图中阴影部分表示可行域，由图可知原问题在点 A 处取得最优值，最优值 z=-6. （3） 21 x2x3zmax 0 x,x 4x2x 1xx . t . s 21 21 21 解 ： 如 图 所 示 ， 可 行 域 为 图 中 阴 影 部 分 ， 易

2、得 原 线 性 规 划 问 题 为 无 界 解 。 （4） 21 x5x2zmin 0 x,x 2xx 6x2x . t . s 21 21 21 解：由图可知该线性规划可行域为空，则原问题无可行解。 1.2 对下列线性规划问题，找出所有的基解，基可行解，并求出最优解和最优值。 （1） 4321 x6x3x2x5zmin 0 x,x,x,x 3x2xxx2 7x4x3x2x . t . s 4321 4321 4321 解： 易知 1 x的系数列向量 2 1 p1， 2 x的系数列向量 1 2 p2， 3 x的系数列向量 1 3 p3， 4 x的系数列向量 2 4 p4。 因为 21 p,p线

3、性无关，故有 4321 4321 x2x3xx2 x4x37x2x ，令非基变量为0 xx 43 ，得 3 11 x 3 1 x 2 1 ，所以得到一个基解)0 , 0 , 3 11 , 3 1 (x )1( 是非基可行解； 因为 31 p,p线性无关，可得基解)0 , 5 11 , 0 , 5 2 (x )2( ， 5 43 z2； 因为 41 p,p线性无关，可得基解) 6 11 , 0 , 0 , 3 1 (x )3( ，是非基可行解； 因为 32 p,p线性无关，可得基解)0 , 1 , 2 , 0(x )4( ，1z4； 因为 42 p,p线性相关， 42 x,x不能构成基变量； 因

4、为 43 p,p线性无关，可得基解) 1 , 1 , 0 , 0(x )6( ，3z6； 所以 )6()4()2( x,x,x是原问题的基可行解， )6( x是最优解，最优值是3z。 （2） 54321 xxx2xxzmax 5 , 4 , 3 , 2 , 1i , 0 x 4xx2x 1xxxx . t . s i 521 4321 解：易知 1 x的系数列向量 1 1 p1， 2 x的系数列向量 2 1 p2， 3 x的系数列向量 0 1 p3， 4 x的系数列向量 0 1 p4， 5 x的系数列向量 1 0 p5。 因为 21 p,p线性无关，故有 521 4321 x4x2x xx1x

5、x ，令非基变量为0 xxx 543 ，得 3 5 x 3 2 x 2 1 ，所以得到一个基解)0 , 0 , 0 , 3 5 , 3 2 (x )1( ，是非基可行解； 因为 31 p,p线性无关，可得基解)0 , 0 , 5 , 0 , 4(x )2( ，是非基可行解； 因为 41 p,p线性无关，可得基解)0 , 5 , 0 , 0 , 4(x )3( ，是非基可行解； 因为 51 p,p线性无关，可得基解)5 , 0 , 0 , 0 , 1 (x )4( ，4z4； 因为 32 p,p线性相关，得基解)0 , 0 . 1, 2 , 0(x )5( ，是非基可行解； 因为 42 p,p线

6、性无关，可得基解)0 , 1, 0 , 2 , 0(x )6( ，是非基可行解； 因为 52 p,p线性无关，可得基解)2 , 0 , 0 , 1 , 0(x )7( ，1z7； 因为 43 p,p线性相关， 43 x,x不能构成基变量； 因为 53 p,p线性无关，可得基解)4 , 0 , 1 , 0 , 0(x )9( ，6z9； 因为 54 p,p线性无关，可得基解)4 , 1 , 0 , 0 , 0(x )10( ，3z10； 所以原线性规划的基可行解是 )10()9()7()4( x,x,x,x，最优解是 )7( x，最优值是1z。 1.3 用单纯形法求解下列线性规划问题； （1）

7、21 x3x2zmax 0 x,x 2xx 5x3x . t . s 21 21 21 解：引入松弛变量 3 x，剩余变量 4 x和人工变量 5 x，把原问题化为规范式 521 Mxx3x2zmax 5.2 , 1i , 0 x 2xxxx 5xx3x . t . s i 5421 321 ，其中 M 无限大， 构造初始单纯形表并计算如下： 1 x 2 x 3 x 4 x 5 x 2+M 3+M 0 -M 0 3 x 1 3 1 0 0 5 5 x 1 1 0 -1 1 2 以 2 x作为换入基， 3 x作为换成基，计算得 1 x 2 x 3 x 4 x 5 x 1+ 3 2 M 0 -1-

8、3 M -M 0 2 x 3 1 1 3 1 0 0 3 5 5 x 3 2 0 3 1 -1 1 3 1 以 1 x为换入基， 5 x作为换出基有 1 x 2 x 3 x 4 x 5 x 0 0 2 1 2 3 M 2 3 -5.5 2 x 0 1 2 1 2 1 2 1 1.5 1 x 1 0 2 1 2 3 2 3 0.5 以 4 x换入， 2 x换出有 1 x 2 x 3 x 4 x 5 x 0 -3 -2 0 M3 -10 4 x 0 2 1 1 -1 3 1 x 1 3 1 0 0 5 根据单纯形表可知，原问题的最优解为)3 , 0 , 0 , 5(x*，最优值为10z* （2）

9、321 x2xxzmax 0 x,x,x 7xx4x 5xxx3 . t . s 321 321 321 解：引入松弛变量 4 x，剩余变量 5 x和人工 变量 6 x，把原问题规范化为 6321 Mxx2xxzmax 6.2 , 1i , 0 x 7xxxx4x 5xxxx3 . t . s i 65321 4321 1 x 2 x 3 x 4 x 5 x 6 x 1+M 1-4M -2+M 0 -M 0 4 x 3 1 -1 1 0 0 5 6 x 1 -4 1 0 -1 1 7 以 1 x作为换入基， 4 x作为换出基有 1 x 2 x 3 x 4 x 5 x 6 x 0 3 M13 3

10、 2 3 5 3 M4 3 M1 -M 0 1 x 1 3 1 - 3 1 3 1 0 0 3 5 6 x 0 3 13 3 4 3 1 -1 1 3 16 以 3 x为换入变量， 6 x为换出变量，得 所以原问题最优解为)4 , 0 , 3(x*，最优值为5z*。 （3） 321 xx3x2zmin 0 x,x,x 6x2x3 8x2x4x . t . s 321 21 321 解：引入剩余变量 4 x, 5 x和人工变量 6 x, 7 x,利用两阶段法得到辅助线性规划 76 xxwmax 321 xx3x2zmax 7.2 , 1i , 0 x 6xxx2x3 8xxx2x4x . t .

11、 s i 7521 64321 构造初始单纯形表，并计算 1 x 2 x 3 x 4 x 5 x 6 x 0 M4 4 19 0 12 1 4 5 4 M45 1 x 1 6 5 0 4 1 - 3 1 3 3 x 0 4 13 1 4 1 - 4 3 4 3 4 1 x 2 x 3 x 4 x 5 x 6 x 7 x z -2 -3 -1 0 0 0 0 w 4 6 2 -1 -1 0 0 6 x 1 4 2 -1 0 1 0 8 7 x 3 2 0 0 -1 0 1 6 以 2 x为换入变量， 6 x为换出变量，得 1 x 2 x 3 x 4 x 5 x 6 x 7 x z 4 5 0 2

12、 1 4 3 0 4 3 0 w 2 5 0 -1 2 1 -1 2 3 0 2 x 4 1 1 2 1 - 4 1 0 4 1 0 2 7 x 2 5 0 -1 2 1 -1 2 1 1 2 以 1 x为换入变量， 7 x为换出变量，得 1 x 2 x 3 x 4 x 5 x z 0 0 0 2 1 2 1 2 x 0 1 0.6 -0.3 0.1 1.8 1 x 1 0 -0.4 0.2 -0.4 0.8 从单纯行表中可知，原问题有无限多个最优解，其中一个为)0 , 8 . 1 , 8 . 0(x*，最优值为 7z*。 （4） 321 x12x15x10zmax 3 , 2 , 1j ,

13、0 x 5xxx2 15x15x6x5 9xx3x5 . t . s j 321 321 321 解：引入松弛变量 5, 4x x，剩余变量 , 6 x，人工变量 7 x，将原问题化为规范式 7321 Mxx12x15x10zmax 7,.,2 , 1j , 0 x 5xxxxx2 15xx15x6x5 9xxx3x5 . t . s j 76321 5321 4321 构造初始单纯形表并计算得 以 1 x为换入变量， 4 x为换出变量，得 以 1 x为换入变量， 4 x为换出变量 1 x 2 x 3 x 4 x 5 x 6 x 7 x z 10+2M 15+M 12+M 0 0 -M 0 4

14、 x 5 3 1 1 0 0 0 9 5 x -5 6 15 0 1 0 0 15 7 x 2 1 1 0 0 -1 1 5 1 x 2 x 3 x 4 x 5 x 6 x 7 x 进一步计算知道，0 x7，所以原问题没有可行解。 1.4 设目标函数极大化的线性规划问题的单纯形表如下，表中无人工变量，当待定常数 21121 c,c,b,a ,a为何值时，表中的解： （1）为唯一最优解， （2）为多重解， （3）有无界解， （4）为退化解。 解：当0c,c, 0b 211 ，为唯一最优解； 当0c, 0c0c, 0c , 0b 21211 或，为多重解； 当0c, 0c , 0a , 0b 21

15、21 ，具有无界解； 0c, 0a0c, 0b 2211 或，为退化的可行解。 1.5 某商店要制定某种商品第二季度的计划，已知该商店仓库容纳此种商品的容量不超过 600 件，3 月底已存货 200 件，以后每月初进货一次。假定各月份此种商品买进售出的单价 如下，问各月进货、售货各多少件才能使利润最大？假设进货时受到仓库容量的限制，售货 z 0 5 M 9 5 M3 10 5 M2 2 0 -M 0 1 x 1 0.6 0.2 0.2 0 0 0 1.8 5 x 0 9 16 1 1 0 0 24 7 x 0 -0.2 0.6 -0.4 0 -1 1 1.4 1 x 2 x 3 x 4 x 5

16、 x 6 x 1 c 0 2 c -9 0 0 0 z 2 x 1 a 1 2 a -1 0 0 7 5 x -1 0 -5 0 1 0 3 6 x 4 0 -2 1 0 1 1 b 时受到进货量的限制，不考虑货物存放在仓库的耗损与保管费用。 月份 买进单价/(元/件) 售出单价/(元/件) 4 17 18 5 16.5 18 6 17 19 解：设 i x表示每个月进货量， i y表示相应月份售货量，其中3 , 2 , 1i ，则有数学模型： 321321 x17x5 .16x17y19y18y18zmax 3 , 2 , 1i , 0y,x 200yxyxyx 200yxyx 200yx

17、200600 xyxyx 200600 xyx 200600 x . t . s ii 332211 2211 11 32211 211 1 经计算，当600y,600 x,600y,500 x,600y,400 x 332211 时，即四月份进货 400 件，售货 600 件，五月份进货 500 件，售货 600 件，六月份进货 600 件售货 600 件时， 最大利润为 6100 元。 1.6 设市场上可买到 n 种不同的食品，第 j 种食品的单位售价为 j c，每种食品含有 m 种基本 营养成分，第 j 种食品每一个单位含第 i 种营养成分为 ij a，每人每天对第 i 种营养成分的需

18、要量不少于 i b，试确定在保持营养成分要求条件下的最经济食谱。 解：设没人每天需要第 j 种食品的数量为 j x（j=1,2,.,n） ，建立数学模型为： n 1j jjx czmin n,.2 , 1j , 0 x m,.,2 , 1i ,bxa . t . s j n 1j ijij 1.7 A,B 两种产品都需要经过前、后两道工序加工，每一个单位产品 A 需要前道工序 1h 和后道工序 2h，每一个位产品 B 需要前道工序 2h 和后道工序 3h.可利用的前道工序有 11h， 后道工序有 17h。没加工一个单位产品 B 的同时，会产生 2 个单位的副产品 C，并且不需要 任何费用，产品

19、 C 一部分可出售盈利，其余的只能加以销毁。出售单位产品 A,B,C 的利润 分别为 3 元，7 元，2 元，每单位产品 C 的销毁费为 1 元。预测表明，产品 C 最多只能出 售 13 个单位。试建立总利润最大的生产计划数学模型。 解：设 21 x,x分别为产品 A,B 的产量， 3 x为副产品 C 的销售量， 4 x为副产品 C 的销毁量， 于是有 243 x2xx，z 为总利润，则数学模型如下： 4321 xx2x7x3zmax 0 x,x,x,x 13x 0 xxx2 17x3x2 11x2x . t . s 4321 3 432 21 21 习题二 2.1 写出下列线性规划问题的对偶

20、问题： （1） 321 xx5x10zmin 自由变量 231 2 321 321 x, 0 x,x 7x1 2x5x6x 10 x4x2x s.t. 解：原问题的对偶问题为： 4321 y7yy2y10wmax 0y,y,y, 0y 1y5y4 5yyy62y 10yy s.t. 4321 21 4321 21 （2） 4321 x4x3x2xzmax 自由变量 4321 4321 4321 4321 x, 0 x,x,x 5xx3x2x4 13x5xx2x 6x2xx5x s.t. 解：原问题的对偶问题是 321 y5y13y6wmin 0y, 0y,y 4yy5y2 3y3yy 2y2y

21、5y 1y4y2y s.t.2 321 321 321 321 321 无约束 2.2 证明下列线性规划为题为最优解 321 x2x2xzmin 自由变量 321 2 321 321 x, 0 x,x 7x1 2x3x2x 3x2xx2 s.t. 证明：原问题的对偶问题为 21 y2y3wmax 无约束 12 21 21 21 y, 0y 2y3y2 2y2y 1yy2 s.t. 易知该对偶问题无可行解，由定理知则原问题无最优解。 2.3 对线性规划问题 321 x18x6x4zmin 0 x,x,x 5x2x 3x3x s.t. 321 32 31 （1）写出该线性规划问题的对偶问题； （2

22、）已知对偶为题的最优解为（2,6） ，试用互补松弛定理求其原问题的最优解。 解： （1）原问题的对偶问题为： 21 y5y3wmax 0y,y 18y2y3 6y 4y s.t. 21 21 2 1 （2）根据互不松弛定理有 0 x) cyA( 则 0)6 , 2()5 , 3( 23 10 01 )x,x,x( 321 有 5x2x 3x3x 32 31 又因为cxby有 6 2 )5 , 3( 18 6 4 )x,x,x( 321 即：18x9x3x2 321 联立解得 1x 3x 0 x 3 2 1 即原问题的最优解为（0,3,1） 2.4 对线性规划问题 4321 x6x5xx2zma

23、x 0 x,x,x,x 12x2xx32x 8xxx2 s.t. 4321 4321 431 （1）写出该线性规划问题的对偶问题； （2）已知原问题的最优解为)4 , 4 , 0 , 0(，试用互补松弛定理求对偶问题的最优解。 解： （1）原问题的对偶问题为： 21 y12y8zmin 无约束 21 21 21 2 21 y, 0y 6y2y 5yy 13y 2y2y2 s.t. (2)利用互补松弛定理有0 x)cAy( 有 0 4 4 0 0 )6 , 5 , 1 , 2( 2132 1102 )y,y( 21 有 6y2y 5yy 21 21 即 1y 4y 2 1 所以对偶问题的最优解为

24、（4,1） 2.5 用对偶单纯形法求解下列线性规划问题： （1） 321 x5x4x2zmin 0 x,x,x 6xx- 1x3xx s.t. 321 21 321 解：利用对偶单纯形，添加松弛变量 54 x,x，原问题化为规范式 321 x5x4x2zmax 0 x,x,x,x,x 6xxx 1xx3xx s.t. 54321 521 4321 则有对偶单纯形表 1 x 2 x 3 x 4 x 5 x -2 -4 -5 0 0 4 x -1 -1 3 1 0 -1 5 x 1 -1 0 0 1 -6 以 2 x为换入量， 5 x为换出量有 1 x 2 x 3 x 4 x 5 x -6 0 -

25、5 0 -4 4 x -2 0 3 1 -1 5 2 x -1 1 0 0 -1 6 由表可知。原问题的最优解为（0,6,0） （2） 321 x2xxzmax 0 x,x,x 7x3x2x 10 x6x2x 4x3x5x s.t. 321 321 321 321 解：利用对偶单纯形，添加松弛变量 654 x,x,x，原问题化为规范式： 321 x2xxzmax 6 , 5 , 4 , 3 , 2 , 1i , 0 x 7xx3x2x 10 xx6x2x- 4xx3x5x s.t. i 6321 5321 4321 ，则有单纯形表 1 x 2 x 3 x 4 x 5 x 6 x -1 -1 -

26、2 0 0 0 4 x 1 -5 3 1 0 0 4 5 x -2 -1 -6 0 1 0 -10 6 x 1 -2 3 0 0 1 7 以 3 x为换入量， 5 x换出得 1 x 2 x 3 x 4 x 5 x 6 x -1/3 -2/3 0 0 -1/3 0 4 x 0 -11/2 0 1 1/2 0 -1 3 x 1/3 1/6 1 0 -1/6 0 5/3 6 x 0 -5/2 0 0 1/2 1 2 以 2 x为换入量， 4 x为换出量有 1 x 2 x 3 x 4 x 5 x 6 x -1/3 0 0 2/3 -3/11 0 2 x 0 1 0 -2/11 -1/11 0 2/11

27、 3 x 1/3 0 1 1/33 -5/33 0 54/33 6 x 0 0 0 -5/11 3/11 1 27/11 由表知原问题无最优解。 2.6 设有线性规划 321 xxx2zmin 0 x,x,x 20 xxx 10 x2xx 60 xxx3 s.t. 321 321 321 321 求出最优解，并进行以下分析 （1） 2 c在什么范围内变动而不影响最优解？ （2） 3 b从 20 变为 16，求最优解； （3） 3 x的系数变为) 1, 3 , 1 (,，其价值系数从 1 变为-5，试问最优解是否会发生变化？ （4）增加约束条件31xxx2 521 ，最优解有何变化？ 解：引入松

28、弛变量 654 x,x,x，将原问题化为规范行： 321 xxx2zmax 6.2 , 1i , 0 x 20 xxxx 10 xx2xx 60 xxxx3 s.t. i 6321 5321 4321 ， 1 x 2 x 3 x 4 x 5 x 6 x 列单纯形表有 以 1 x为换入变量， 5 x为换出变量有 以 2 x为换入变量， 6 x为换出变量有 所以原问题的最优解为（15,5,0,10,0,0） （1）因为 2 x是基变量，由书中（2.6）式有1) 2 1 2 1 max( ， 3 7 ) 2 1 2 3 , 2 3 2 7 min( 所以 3 7 c1 2 时，最优解不变，即 3 4

29、 c2 2 ，所以当2c 3 4 2 时，原问题最优 解不变。 2 -1 -1 0 0 0 4 x 3 1 1 1 0 0 60 5 x 1 -1 2 0 1 0 10 6 x 1 1 -1 0 0 1 20 1 x 2 x 3 x 4 x 5 x 6 x 0 1 -5 0 -2 0 4 x 0 4 -5 1 -3 0 30 1 x 1 -1 2 0 1 0 10 6 x 0 2 -3 0 -1 1 10 1 x 2 x 3 x 4 x 5 x 6 x 0 0 -7/2 0 -3/2 -1/2 4 x 0 0 1 1 -1 -2 10 1 x 1 0 1/2 0 1/2 1/2 15 2 x

30、0 1 -3/2 0 -1/2 1/2 5 （2） 2 2 8 4 0 0 2/12/10 2/12/10 211 bBb 1 所以 3 13 18 2 2 8 5 15 10 bbb 此时原问题的最优解为（13,3,0,18,0,0） （3）02 1 3 1 2/12/10 2/12/10 211 ) 11, 2(1pBcc 3 1 B33 所以原问题的最优解变。 （4）添加松弛变量 7 x，在原最终单纯形表中添加一行一列并计算有 以 3 x为换入量， 7 x为换出量有 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 0 -7/2 0 -3/2 -1/2 4 x 0 0 1 1

31、-1 -2 0 10 1 x 1 0 1/2 0 1/2 1/2 0 15 2 x 0 1 -3/2 0 -1/2 1/2 0 5 7 x 0 0 1 0 9 -3 2 -8 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 0 0 0 63/2 -12 13/2 4 x 0 0 0 1 -10 1 -2 18 1 x 1 0 0 0 -4 2 -1 19 2 x 0 1 0 0 13 -4 3 -7 以 6 x为换入量， 3 x为换出量有 得最优解为（41/3,11/3,0,46/3,0,8/3,0）,最优值为-71/3 2.7 某厂生产 321 A,A,A三种产品，需要 321

32、B,B,B三种设备加工，需要单位各种产品所需 要的设备台时、设备的现有加工能力及每件产品的预期利润如下表所示 台/h 1 A 2 A 3 A 设备能力 1 B 1 1 1 100 2 B 10 4 5 600 3 B 2 2 6 300 单位产品利润 10 6 4 （1）求获利最大的产品生产计划； （2）每件产品 3 A的利润增加到多大时，才值得安排生产？如果每件产品 3 A的利润增加到 50/6，求最优计划的变化； （3）产品 1 A的利润在多大范围变化时原最优计划保持不变？ （4）如设备 1 B的能力为10100，确定保持最优基不变的的变化范围； （5）如有一种新产品，加工一件需要设备 3

33、21 B,B,B的台时各为 1h,4h,3h 预期每件的利润 为 8 元，是否值得安排生产？ 3 x 0 0 1 0 9 -3 2 -8 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 0 -4 0 -9/2 0 -13/2 4 x 0 0 1/3 1 -7 0 1/3 46/3 1 x 1 0 -2/3 0 2 0 1/3 41/3 2 x 0 1 -4/3 0 1 0 1/3 11/3 6 x 0 0 -1/3 0 -3 1 -2/3 8/3 a) 如合同规定该厂至少生产 10 件 产品 3 A，试确定最优计划的变化。 解：设计划生产产品 321 A,A,A各 321 x,x,

34、x件，则有 321 x4x6x10zmax 0 x,x,x 300 x6x2x2 600 x5x4x10 100 xxx t . s 321 321 321 321 （1）构造单纯形表如下： 以 1 x为换入量， 5 x为换出量有 以 2 x为换入量， 4 x为换出量有 1 x 2 x 3 x 4 x 5 x 6 x 10 6 4 0 0 0 4 x 1 1 1 1 0 0 100 5 x 10 4 5 0 1 0 600 6 x 2 2 6 0 0 1 300 1 x 2 x 3 x 4 x 5 x 6 x 0 2 -1 0 -1 0 -600 4 x 0 3/5 1/2 1 -1/10 0

35、 40 1 x 1 2/5 1/2 0 1/10 0 60 6 x 0 6/5 5 0 -1/5 1 180 1 x 2 x 3 x 4 x 5 x 6 x 得最优生产计划，即)100, 0 , 0 , 0 , 3/200, 3/100(x*为最优解，获利 2200/3 元 （2）由 于 3 x为 非 基 变 量 ， 则 只 有0 才 值 得 生 产 ， 即 3/20c, 3/ 8c,c 333 即即时 3 A才值得生产。而当3/206/50c，此时最优 解发生变化，根据计算，当6/50c时，03/5 3 时，此时将 3 x作为换入变量， 6 x作 为换出变量，得 此时生产最优计划为（175/

36、6,275/6,25,0,0,0） (3）由于 1 x的生产量为基变量，则有4 6/1 3/2 , 6/1 3/8 max ，5 3/2 3/10 min ，即 5 , 4c1时，原最优生产计划保持不变。得15, 6c1 （4）若矩阵 122 0104 011 p,p,pB 321 ，其逆矩阵 102 06/13/2 06/13/5 B 1 ，为使最优基不发生 改变，根据（2.7）有 2 100 , 3/2 3/100 minb 3/5 3/200 max 1 ，50,40b1， 即5 , 4时，最优基不发生改变。 0 0 -8/3 -10/3 -2/3 0 -2200/3 2 x 0 1 5

37、/6 5/3 -1/6 0 200/3 1 x 1 0 1/6 -2/3 1/6 0 100/3 6 x 0 0 4 -2 0 1 100 1 x 2 x 3 x 4 x 5 x 6 x 0 0 0 -5/2 -2/3 -5/12 -2325/3 2 x 0 1 0 25/12 -1/6 -5/24 275/6 1 x 1 0 0 -7/12 1/6 -1/24 175/6 3 x 0 0 1 -1/2 0 1/4 25 （5）经计算 1 0 1 pB 7 1 ，6 1 0 1 )0 ,10, 6(pBc 7 1 B ，知 0268PBcc 7 1 B77 ,则此时最优解发生变化，且该产品值得

38、生产。 （6）原最优解不满足新的约束条件，10 x3，即10 x3，引入松弛变量 7 x，在原最 终单纯形表中增加一行或一列有： 将 7 x做为换出变量， 3 x作为换入变量，利用对偶单纯形有 得到此时最优生产计划)60, 0 , 0 ,10, 3/175, 3/95(x* 2.8 对所有 t 值，讨论以下参数线性规划问题最优解的变化范围； 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 0 -8/3 -10/3 -2/3 0 0 -2200/3 2 x 0 1 5/6 5/3 -1/6 0 0 200/3 1 x 1 0 1/6 -2/3 1/6 0 0 100/3 6 x 0

39、0 4 -2 0 1 0 100 7 x 0 0 -1 0 0 0 1 -10 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 0 0 -10/3 -2/3 0 -8/3 -22120/ 3 2 x 0 1 0 5/3 -1/6 0 5/6 175/3 1 x 1 0 0 -2/3 1/6 0 1/6 95/3 6 x 0 0 0 -2 0 1 4 60 7 x 0 0 0 1 0 0 -1 10 321 x) t10(x) t12(x) t27(zmax 0t , 0 x,x,x 30 xx22x 20 xxx s.t. 321 321 321 解：将上述问题转化为标准型有 32

40、1 x) t10(x) t12(x) t27(zmax 0t , 0 x,x ,x,x,x 30 xxx22x 20 xxxx s.t. 54321 5321 4321 令 t=0，用单纯法求解如下： j c 7 12 10 0 0 B C B X b 1 x 2 x 3 x 4 x 5 x 0 4 x 20 1 1 1 1 0 20 0 5 x 30 2 2 1 0 1 15 -z 0 7 12 10 0 0 0 4 x 5 0 0 1/2 1 -1/2 10 12 2 x 15 1 1 1/2 0 1/2 30 -z -180 -5 0 4 0 -6 10 3 x 10 0 0 1 2 -

41、1 12 2 x 10 1 1 0 -1 1 -z -220 -5 0 0 -8 -2 将 t 的变化直接反应到最终的单纯形表中 j c 7+2t 12+t 10-t 0 0 B C B X b 1 x 2 x 3 x 4 x 5 x 10-t 3 x 10 0 0 1 2 -1 5 12+t 2 x 10 1 1 0 -1 1 -z -220 T-5 0 0 3t-8 -2-2t T 开始增大，当 t8/3 时，首先出现 0 4 ，故当 3 8 t0时，得最优解（0，10,，10，0） 目标函数的最优值为) 3 8 t0(220zmax。 3 8 t 为第一临界点 0,5t 3 8 4 时当

42、， 4 x作为换入变量，由规则确定 3 x为换出变量，用单纯形法进行 迭代： j c 7+2t 12+t 10-t 0 0 B C B X b 1 x 2 x 3 x 4 x 5 x 0 4 x 5 0 0 1/2 1 -1/2 12+t 2 x 15 1 1 1/2 0 1/2 15 -z -180-15t T-5 0 4-3t/2 0 -6-t/2 由表可知，t 继续增大，当 t5 时首先出现0 1 ，故当5t 3 8 时，得最优解（0,15,0,5） 目标函数的最优值为 180+15t，t=5 为第二临界点。 当 t5 时，0 1 ， 1 x作为换入变量，由规则确定 2 x为换出变量，用

43、单纯形法进行迭 代： j c 7+2t 12+t 10-t 0 0 B C B X b 1 x 2 x 3 x 4 x 5 x 0 4 x 5 0 0 1/2 1 -1/2 7+2t 1 x 15 1 1 1/2 0 1/2 -z -105-30t 0 5-t 13/2-2t 0 -7/2-t 由表知 当 t 继续增大时，所有检验数都非正，所以当 t5 时，得最优解（15，0，0，5） 目标函数的最优值为 105+30t 2.9 考虑下列问题： 21 xx3zmax 0 x,x 4x2x 4xx s.t. 21 21 21 （1）用单纯形方法求出最优解； （2）将约束右端 4 4 b改变为)0

44、t ( 1 2 t 4 4 ，对 t 的所有值求出问题的最优解。 解： （1）引入松弛变量 43 x,x，把原问题化为标准形 21 xx3zmax 0 x,x,x,x 4xxx2 4xxx s.t. 4321 421 321 ，建立初始单纯形表 1 x 2 x 3 x 4 x 3 1 0 0 3 x 1 1 1 0 4 4 x 2 -1 0 1 4 以 1 x为换入变量， 4 x为换出变量，有 1 x 2 x 3 x 4 x 0 5/2 0 -3/2 3 x 0 1 1 -1/2 2 1 x 1 -1/2 0 1/2 2 以 2 x为换入变量， 3 x为换出变量有 1 x 2 x 3 x 4

45、x 0 0 -5/3 -2/3 2 x 0 1 2/3 -1/3 4/3 1 x 1 0 1/3 1/3 8/3 所以，原问题的最优解为（8/3 ，4/3） （2） 3/ t 3/ t 5 t t2 3/13/1 3/13/2 bBb 1 ，将其加在最终单纯表中有 1 x 2 x 3 x 4 x 0 0 -5/3 -2/3 2 x 0 1 2/3 -1/3 4/3-5t/3 1 x 1 0 1/3 1/3 8/3 -t/3 由表可知当 5 4 t0，问题的最优解为（8/3 -t/3，4/3-5t/3） 当 5 4 t 时，利用对偶单纯形有 1 x 2 x 3 x 4 x 0 -2 -3 /2/

46、3 4 x 0 -3 -2 1 5t-4 1 x 1 1 1 0 4-2t 由表可知当时，问题的最优解为（4-2t，0） ，当 t2 时，原问题无解。 习题三 3.1 用割平面法求解下列整数线性规划。 （1） 21- 2minxxz 且为整数0, 4x 13- s.t. 21 21 21 xx x xx 解：增加松弛变量 43,x x，将其化为标准形为 21 2-wminxx 且为整数0, 4x 13- s.t. 4321 421 321 xxxx xx xxx 先不考虑整数条件， 则对应线性规划单纯 形表如下 1 x 2 x 3 x 4 x w -2 1 0 0 3 x 1 -3 1 0 1

47、 4 x 1 1 0 1 4 以 4 x为换出基， 2 x为换入基，进一步得单纯形表 1 x 2 x 3 x 4 x w -3 0 0 -1 3 x 4 0 1 3 13 2 x 1 1 0 1 4 所以，原线性规划问题的最优解为)4 , 0(x*，是整数解所以也是原整数规划的整数解。 （2） 21 x9x12zmax 且为整数0 x,x 3x2x3 6x5x- 10 xx2 s.t. 21 21 21 21 解：增加松弛变量 543 x,x,x，将其化为标准形为： 21 x9x12zmax 且为整数0 x,x,x,x,x 3xx2x3 6xx5x- 10 xxx2 s.t. 54321 52

48、1 421 321 先不考虑整数条件，则对应线性规划单纯形表如下 1 x 2 x 3 x 4 x 5 x z -12 9 0 0 0 3 x 2 1 1 0 0 10 4 x -1 5 0 1 0 6 5 x 3 -2 0 0 1 3 以 2 x作为换入变量， 4 x为换出变量得 1 x 2 x 3 x 4 x 5 x z -51/5 0 0 -9/5 0 3 x 11/5 0 1 -1/5 0 44/5 2 x -1/5 1 0 1/5 0 6/5 5 x 13/5 0 0 2/5 1 27/5 所以线性规划的最优解为 （0,6/5,44/5,0,27/5）分量 44/5 取整后分数最大，考

49、虑单纯形表中该分量所对应的行约束 5 44 x 5 1 xx 5 11 431 ，则有割 平面方程0)x 5 4 x 5 1 ( 5 4 41 ，增加松弛变量 6 x，化为等式约束 5 4 xx 5 4 x 5 1 641 并加入上面最后的单纯形表中有： 1 x 2 x 3 x 4 x 5 x 6 x z -51/5 0 0 -9/5 0 0 利用对偶单纯形法有 由表可知最优解为（0,1）最优值为 9. 3.2 用分支定界法求解下列整数线性规划问题： （1） 21 x5xzmax 且为整数0 x,x 42x67x 11x4x3 s.t. 21 21 21 解： 先不考虑 1 x， 2 x为整数

50、的约束条件， 求的相应线性规划问题的最优解为)4/11, 0(x )0( , 目标函数的最优值为4/55z )0( ，由于4/32x )0( 1 ，构造两个线性规划子问题如下： 21 x5xzmax 3 x 11/5 0 1 -1/5 0 0 44/5 2 x -1/5 1 0 1/5 0 0 6/5 5 x 13/5 0 0 2/5 1 1 27/5 6 x -1/5 0 0 -4/5 0 1 -4/5 1 x 2 x 3 x 4 x 5 x 6 x z -203/20 0 0 0 0 -9/4 3 x 43/20 0 1 0 0 -1/4 9 2 x -4/25 1 0 0 0 1/4 1

51、 5 x 5/2 0 0 0 1 1/2 5 6 x -1/4 0 0 1 0 -5/4 1 ) 1 ( 0 x,x 2x 42x67x 11x4x3 s.t. 21 2 21 21 且为整数 和 21 x5xzmax )2( 0 x,x 3x 42x67x 11x4x3 s.t. 21 2 21 21 且为整数 先不考虑整数的约束条件，求解（1）所对应的线性规划子问题得到最优解)2 , 1 (x1，最优 值为11z1， （2） 所对应的线性规划子问题没可行解。 故原整数规划的最优解为)2 , 1 (x1， 最优值为11z1。 （2） 21 x2-x3zmin 且为整数0 x,x 9x4x 7

52、x2x s.t. 21 21 21 3.3 求解下列 01 规划问题： （1） 4321 x5x3xx2zmax 4 , 3 , 2 , 1j10 x 3xxxx 2x2x 1xxx3x s.t. j 4321 32 4321 ，或 解：利用隐枚举法，显然（0,1,1,0）是原问题的一个解，增加约束条件 4x5x3xx2 4321 则有表 点 条件 满足条件？ 是（）否（） Z 值 （0,0,0,0） 0 (0,0,0,1) -5 3 (0,0,1,0) 3 1 2 -1 (0,0,1,1) -2 (0,1,0,0) 1 (0,1,0,1) -4 (0,1,1,0) 4 -2 2 0 4 (0,1,1,1) -1 (1,0,0,0) -2 (1,0,0,1