水资源系统分析第2章线性规划与单纯形法

1、.1 1 第二章 线性规划 . 2 1 一般数学模型 1.1 问题的提出 4例例1 1 长度长度100100米的钢材，需要截成米的钢材，需要截成3 3 米、米、8 8米、米、1111米短材。如何截取使剩料米短材。如何截取使剩料 最少？要求：最少？要求：3 3米的最少米的最少2 2根，最多根，最多9 9根；根； 8 8米的最少米的最少4 4根，根，1111米的最少米的最少1 1根，最多根，最多 8 8根。根。 . 3 4例例2 2 某灌区在年初估算可供水量为某灌区在年初估算可供水量为360360万万m m3 3, , 计划灌溉小麦、玉米两种计划灌溉小麦、玉米两种. .总面积总面积1000hm10

2、00hm2 2, , 两种作物的毛灌溉定额及灌溉净效益如表两种作物的毛灌溉定额及灌溉净效益如表， 问该年两种作物的种植计划如何安排可使问该年两种作物的种植计划如何安排可使 灌溉总净效益最大？灌溉总净效益最大？ 作物作物毛灌溉定额毛灌溉定额 （m3/hm2） 灌溉净效益灌溉净效益 （元（元/ hm2） 小麦小麦 6000 600 玉米玉米 3000 450 . 4 模型模型 0, 3606 . 03 . 0 1000. . 6 . 045. 0max 21 21 21 21 xx xx xxts xxZ . 5 . 6 例例3 3 甲、乙两水库给甲、乙两水库给A A、B B、C C三座城市供三座

3、城市供 水水, ,甲库可供水量甲库可供水量2020万万mm3 3/d,/d,乙库为乙库为2525万万 mm3 3/d/d。 A.B.CA.B.C需水为需水为1010万万mm3 3/d,15/d,15万万mm3 3/d,20/d,20 万万mm3 3/d. /d. 已知输水费用（标），求满足已知输水费用（标），求满足 三个城市用水需要费用最小的输水方案。三个城市用水需要费用最小的输水方案。 . 7 ABC 甲甲 9070100 C1aC1bC1c 乙乙 806580 C2aC2bC2c ABC 甲甲x1ax1bx1c 乙乙x2ax2bx2c 成本表成本表 . 8 Obj. minf(x)=c1a

4、x1a+c1bx1b+c2cx2c S.t x1a+x2a10 x1b+x2b15 x1c+x2c20 x1a+x1b+x1320 x21+x22+x2325 x11,x12x230 城市需水量约束城市需水量约束 水库供水量约束水库供水量约束 . 9 规划模型的要素规划模型的要素 4决策变量：决策变量：规划的措施、方案，是需要规划的措施、方案，是需要 确定的未知变量。确定的未知变量。 4目标函数：目标函数：规划的目的和用要求规划的目的和用要求 4约束条件：约束条件：决策变量的取值范围决策变量的取值范围 线性目标和约束组成线性目标和约束组成线性规划模型线性规划模型 1.2 数学模型 . 10 4

5、产生和发展 19世纪，法国科学家Fourier提出线性规划。 1939年苏联数学家康托维奇：机器负荷分配、 原材料的合理利用等生产组织问题。 二战期间开始应用于军事规划 (英、美)。1947年， Dantzig 美国空军-斯坦福大学教授， 提出了单纯形法求解线性规划问题。 “线性规划之父”。 . 11 Dantzig 配餐问题配餐问题 4美国空军为了保证士兵的营养，规定每餐的食 品中，要保证一定的营养成份，例如蛋白质、 脂肪、维生素等等，都有定量的规定。 4这些营养成份可以由各种不同的食物来提供 (例如牛奶提供蛋白质和维生素，黄油提供蛋 白质和脂肪，胡萝卜提供维生素，等等)。 4由於战争条件的

6、限制，食品种类有限，又要尽 量降低成本，於是在一盒套餐中，如何决定各 种食品的数量，使得既能满足营养成份的需要， 又可以降低成本-最佳的配餐方案。 . 12 线性规划一般形式线性规划一般形式: ob. Max(min) Z=c1x1+c2x2+cnxn (1.1) s.t. a11x1+a12x2+a1nxn(,=)b1 a21x1+a22x2+a2nxn (,=)b2 . am1x1+am2x2+amnxn (,=)bm x1,x2,.xn0 . 13 简写形式 0 , 1),( max(min) 1 1 ij n j jjij n j jj x mibxa xcz )( 1n cc C m

7、j j j a a a . 2 1 jP mb b b . 2 1 b . 14 向量形式 0 ),( max(min) 1 X b CX n j jj xP z )( 1n cc C T n bb)( 1 b T n xx)( 1 X T mjj aa)( 1 j P m n mn n mm b b x a a x a a x a a 11 2 1 12 1 1 11 . 15 矩阵形式: ob. Max(min) Z=c1x1+c2x2+cnxn (1.1) s.t. a11x1+a12x2+a1nxn(,=)b1 a21x1+a22x2+a2nxn (,=)b2 . am1x1+am2x

8、2+amnxn (,=)bm x1,x2,.xn0 0X bAX),( . 16 njx mibxa xcz j n j ijij n j jj , 10 , 1 max 1 1 1.3 线性规划的标准型 . 17 4目标函数为求极小值目标函数为求极小值 4变量变量X X小于等于小于等于0 0 X=0 X=0 c.c. 变量变量X X无约束无约束 X=X-X; X,X=0;X=X-X; X,X=0; CXzminCX z max . 18 d. d. 约束条件为不等式约束条件为不等式 1232 21 xx 123 3 2312 0 xxx x 0710 21 xx 0 0710 4 421 x

9、 xxx x x3 3,x,x4 4称为松弛变量；在目标函数里系数称为松弛变量；在目标函数里系数 为零为零 . 19 4将下面的模型化为标准型将下面的模型化为标准型 无约束 321 321 321 321 321 , 0, 0 6323 423 92 32min xxx xxx xxx xxx xxxz 例4 . 20 无约束 321 321 321 321 321 , 0, 0 6323 423 92 32min xxx xxx xxx xxx xxxz 0, 0, 0 63323 4223 92 332 3321 3321 3321 3321 3321 xxxx xxxx xxxx xxx

10、x xxxxzMax 0, 63323 4223 92 00332 543321 3321 53321 43321 543321 xxxxxx xxxx xxxxx xxxxx xxxxxxzMax . 21 将下列将下列LP问题化为标准型问题化为标准型 Ob. Min Z=2x1+3x2 s.t. 课堂练习 无约束321 321 321 321 , 0, 523 2 7 xxx xxx xxx xxx . 22 Max z=-2x1-3x2+0 x4-0 x5+0 x6+0 x7 课堂练习答案 12456 12457 1245 , 124567 7 2 3225 ,0 xxxxx xxxxx

11、 xxxx x x x x x x . 23 1.4 线性规划问题的解 4可行解可行解 4最优解最优解 njx mibxa xcz j n j ijij n j jj , 10 , 1 max 1 1 . 24 mnmmm nm aaa aaa 1 1111 A 4基基 B B为为A A的一个的一个mm阶的满秩矩阵，则为一阶的满秩矩阵，则为一 个基。个基。 P Pj j， ，基向量； 基向量；x xj j，基变量，其他非，基变量，其他非 基变量。基变量。 )( 1 111 m1 PPB mmm m aa aa m n mn n m mm m mm b b x a a x a a x a a x

12、 a a 111 2 1 12 1 1 11 . 25 4基解基解 令非基变量令非基变量x xm+1 m+1=x =xm+2 m+2=x =xn n=0,=0,因因 |B|B|！=0=0 根据克莱姆法则，可以解出根据克莱姆法则，可以解出mm个约个约 束方程的束方程的mm个基变量的唯一解个基变量的唯一解X=(xX=(x1 1 x x2 2 x xm m ), ),加上非基变量得到一个基解加上非基变量得到一个基解 X=(xX=(x1 1 x x2 2 x xm m 0 00)0) . 26 4基可行解基可行解 满足非负约束的基解。满足非负约束的基解。 4可行基可行基 对应基可行解的基。对应基可行解

13、的基。 4满意解满意解 可行不最优的解。可行不最优的解。 . 27 例5 4下面问题中，什么是基，基变量，基解，基可下面问题中，什么是基，基变量，基解，基可 行解和可行基。行解和可行基。 0 1240 1604 82 1222 000032max 621 521 421 321 654321 i x xxx xxx xxx xxx xxxxxxz . 28 100040 010004 001021 000122 A 1000 0100 0010 0001 )( 6543 PPPP 0 1240 1604 82 1222 000032max 621 521 421 321 654321 i x

14、xxx xxx xxx xxx xxxxxxz 系数矩阵系数矩阵 基基 . 29 4令非基变量令非基变量x xm+1 m+1=x =xm+2 m+2=x =xn n=0,=0,解出解出m个约束个约束 方程的方程的 m个基变量的唯一解个基变量的唯一解X=(x1 x2 xm )T,加加 上非基变量得到一个基解上非基变量得到一个基解X=(x1 x2 xm 00)T 0 120*40*0 160*00*4 80*20 120*20*2 6 5 4 3 i x x x x x . 30 4令令x1=x2=0,得基解：得基解： X=(0 0 12 8 16 12)T 4此解为基可行解此解为基可行解 P=（

15、p3 p4 p5 p6）为可行基）为可行基 . 31 找出下面模型的一个基，求基解，判断是找出下面模型的一个基，求基解，判断是 否可行基。否可行基。 Max z=x1-2x2+3x4-3x5+0 x6+0 x7 课堂练习 0 52 2 7 5 2 4 21 321 ix xx xxx xxx . 32 课堂练习答案 10020 01011 00111 0 52 2 7 52 421 3 21 ix xx xxx xxx 100 010 001 系数矩阵系数矩阵= 基基)( 543 ppp T )52700(x 基可行解基可行解 . 33 2 图解法 4在坐标系上画出约束条件在坐标系上画出约束条

16、件 4画出目标函数画出目标函数 4确定最优解确定最优解 4简单直观，只适用于两个变量的情况简单直观，只适用于两个变量的情况 . 34 求解的直观原理 4在只有两个决策变量的情况下目标函数在只有两个决策变量的情况下目标函数 可以简化成：可以简化成： x x2 2=f(x=f(x1 1)+g(z) )+g(z) Z Z相当与坐标轴上的截距，不同的相当与坐标轴上的截距，不同的Z Z值值 组成一组平行线，同时对应组成一组平行线，同时对应X1X1，X2X2的不的不 同取值范围。同取值范围。 . 35 ob: max z=2 x1+3 x2 s.t x1+2 x2 8 4x116 , 4x212 2x1+

17、2x2 12 x10, x20 以例3说明 . 36 O x1 x2 X1+2x2=8 4x1=16 4x2=12 2x1+2x2=12 ob: max z=2 x1+3 x2 x2=-2/3x1+z/3 s.t x1+2 x2 8 4x116 , 4x212 2x1+2x2 12 x10, x20 x2=-(2/3) X1+z/3 唯一解唯一解(x1,x2)=(4,2) z=14(x1,x2)=(4,2) z=14 . 37 O x1 x2 4x1=16 4x2=12 x2=-(2/4) X1+z/3 无穷多解无穷多解 . 38 无界解无界解 O x1 x2 4x1=16 x2=-(2/3)

18、 X1+z/3 . 39 无解:无可行域 O x1 x2 x2+x14 . 40 4图解法练习图解法练习 课堂练习 0, 4 1 102 . 3max 21 2 21 21 21 xx x xx xx ts xxZ . 41 课堂练习答案 x1 x2 X1+2x2=10 x2=4 X1+x2=1 X1+3x2=Z (2,4) o x2=-(1/3)x1-Z/3 Z=14 . 42 3 单纯形法原理 3.1 预备知识：凸集和顶点 凸集：凸集：如何集合如何集合C C内任意两个点内任意两个点X X1 1，X X2 2的连的连 线上的所有点都在集合内部，则线上的所有点都在集合内部，则C C为凸集。为凸

19、集。 X= X1+(1-)X2C 01 . 43 顶点：顶点：C中点中点X，若不在，若不在C中任何其他两点中任何其他两点 的连线上，则为顶点。的连线上，则为顶点。 A 不存在不存在 X= X1+(1-)X2 01 有界凸集中的点都可由顶点的凸组合表示有界凸集中的点都可由顶点的凸组合表示 . 44 扩展到n维 0, 1 i21 2211 n nn CXXXX 0, 1 i21 2211 n nn XXXX n个顶点，任一点个顶点，任一点 或者说，点集或者说，点集 是凸集是凸集 . 45 3.2 几个基本定理 4定理定理1 ：若线性规划问题存在可行解，可：若线性规划问题存在可行解，可 问题的可行域

20、是凸集。问题的可行域是凸集。 n j j jj n j j n j j j 1 21 1 2 1 1 )1 ( bxP xxx bxPbxP j jj 证明：证明： . 46 n j jj xx 1 21 )1 ( j P n j j n j j xx 1 2 1 1 bPbP jj n j n j jj n j j xxx 11 2 2 1 1 jjj PPP bbbb 证明： . 47 4引理引理 可行解可行解X=（x1,xn）为基本可行解的充）为基本可行解的充 要条件是要条件是X的正分量对应的系数列向量是线性的正分量对应的系数列向量是线性 独立的。独立的。 证明：证明：（1）必要性）必要

21、性 基本可行解基本可行解 X的正分量对应的系数列的正分量对应的系数列 向量是线性独立的。向量是线性独立的。 （2）充分性）充分性 X的正分量对应的系数列向量是线性独立的的正分量对应的系数列向量是线性独立的 基本可行解基本可行解 . 48 mnmmm nm aaa aaa 1 1111 A 4基可行解基可行解 满足非负约束的的基解。满足非负约束的的基解。 由于非基变量为由于非基变量为0，所以基可行解（，所以基可行解（x1xm） 中正分量集合不超过中正分量集合不超过m，其对应系数列向量也，其对应系数列向量也 不超出（不超出（p1pm） （p1pm）线性独立，其子集必然线性独立。）线性独立，其子集必

22、然线性独立。 ).( )( 1 1 111 m mmm m xx aa aa m1 PPB （1）必要性）必要性 . 49 P1,P2,Pk线性独立，若线性独立，若P的秩为的秩为m，k=m， 恰构成一个基，恰构成一个基，X为基可行解。为基可行解。 （2 2）充分性：）充分性： 可行解可行解X的正分量对应的系数列向量的正分量对应的系数列向量 P1,P2,Pk是线性独立的是线性独立的 X=（x1， x2xk,xm，00）基本可行解。基本可行解。 若若k0) jjj zyx)1 ( . 55 x有有r个正分量个正分量 线性相关 不全为 r1 j jjjj jj pp p bppbpp bpp )(0

23、)( 1 1111 11 jj r j jj n j r j jj n j r j jj n j r j jj zyzy zzyy xx X不是基可行解不是基可行解 . 56 定理定理3 若线性规划问题存在最优解，一定若线性规划问题存在最优解，一定 存在一个基可行解是最优解。存在一个基可行解是最优解。 证明：证明： )( 00 2 0 1 )0( n xxxx 的直线上在过 是顶点，必有：不是基可行解，也不能若 0 0 0 , 0 0 0 是最大值 0 xxx x cxz 设设是最优解是最优解 . 57 )()( )( )( 00 0 0 xccxxc ccxcx ccxcx cx ccxxc

24、 ccxxc 0 00 00 0 0 0 为最大值 0 , 0 xx 代入目标函数：代入目标函数： 同为最优解同为最优解 可能有一个顶点，若仍不是顶点，可继续做下可能有一个顶点，若仍不是顶点，可继续做下 去，直到达到顶点，为最优解。去，直到达到顶点，为最优解。 . 58 0 x1 x2 可行域是凸集；可行域是凸集； 基可行解对应顶点；基可行解对应顶点； 基可行解中存在最有解；基可行解中存在最有解； . 59 3.3 确定初始基可行解 4方法：方法：先找到一个基可行解，如果不是先找到一个基可行解，如果不是 最优解，再转到另一个基可行解，是目最优解，再转到另一个基可行解，是目 标函数不断优化，直到

25、最优解。标函数不断优化，直到最优解。 4步骤：步骤：1 1、找到一个基，求出可行解、找到一个基，求出可行解 2 2、判优、判优 3 3、有向基可行解的转化、有向基可行解的转化 . 60 举例说明： ob: max z=2 x1+3 x2 s.t 2x1+2 x2 12 x1+2 x2 8 4x116 4x212 x10, x20 . 61 标准型：标准型： Max Z=2x1+3x2+0 x3+0 x4+0 x5+0 x6 (1.11) 2x1+2x2+x3 =12 x1+2x2 +x4 =8 4x1 +x5 =16 (1.12) 4x2 +x6 =12 x1, x2, x3, x4, x5

26、,x60 100040 010004 001021 000122 A 1000 0100 0010 0001 ),( 654 pppp3B . 62 （一）选择初始基可行解（一）选择初始基可行解 4B初始基初始基 用非基变量表示基变量用非基变量表示基变量 x3=12-2x1-2x2 ; x4=8-x1-2x2 x5=16-4x1 ; x6 =12-4x2 当当x1=x2=0时时, 得初始解得初始解: x(0)=(0,0,12,8,16,12)T 代入目标函数式得代入目标函数式得 : Z=2x1+3x2=0 (1.13) . 63 （二）最优检验（二）最优检验 从从Z=2Z=2* *0+30+3

27、* *0+0+看出看出: :非基变量非基变量x x1 1,x,x2 2 均是正的，均是正的，x x1 1,x,x2 2, ,只要变成大于只要变成大于0 0的基变的基变 量量,Z,Z将增加将增加. . （三）确定换入变量及其值（三）确定换入变量及其值 从非基变量中选一个作为换入变量，从非基变量中选一个作为换入变量， 成为基变量。一般选价值系数大的变量成为基变量。一般选价值系数大的变量 maxcmaxcj j. .选选x x2 2。 . 64 （四）确定换出变量（四）确定换出变量 由于基变量个数的约束（由于基变量个数的约束（mm），必须），必须 将一个大于将一个大于0 0的基变量变为等于的基变量变

28、为等于0 0的非基的非基 变量。变量。 从从Z Z最大的角度出发，希望换入变量最大的角度出发，希望换入变量 x x2 2的值尽量大，但有约束。的值尽量大，但有约束。 . 65 x3=12-2x1-2x2 0 x4=8-x1-2x2 0 x5=16-4x1 0 x6=12-4x2 0 当非基变量当非基变量x1=0, 得得: x3=12-2x20 x4=8-2x2 0 x5=16 0 x6=12-4x2 0 由上式得由上式得 x2=min(12/2,8/2,16,12/4)=3 当当x2=3时时, x6=0,并使并使x3,x4,x5 0 故用故用x2换换x6 基变量为基变量为x2 x3,x4,x5

29、，非基变量为，非基变量为x1,x6. . 66 （五）求另一个更好的基可行解（五）求另一个更好的基可行解 x3=12-x1-2x2 x3=6-x1 + x6 /2 x4=8-x1 -2x2 x4=2-x1 + x6 /2 x5=16-4x1 x5=16-4x1 4x2=12-x6 x2=3-x6 /4 当当x1,x6=0=0时时, , x(1)=(0,3,6,16,0)T 代入目标得代入目标得: Z=2x1+3x2=9 一次寻优迭代结束。一次寻优迭代结束。 (1.16) . 67 （六）求另一个更好的基可行解（六）求另一个更好的基可行解 X X1 1为换入变量。为换入变量。 x x1 1=mi

30、n(-,6,2,4)=2=min(-,6,2,4)=2 故用故用x x1 1换换x x4 4, ,得得 x x(2) (2)=(2,3,2,0,8,0) =(2,3,2,0,8,0)T T 再一次迭代再一次迭代x x(3) (3)=(4,2,0,0,0,4) =(4,2,0,0,0,4)T T此时此时 得到得到Z=14maxZ=14max . 68 3.最优性检验的判别最优性检验的判别 经过若干次迭代后，基变量与非基变量经过若干次迭代后，基变量与非基变量 aij,bi表示迭代后的系数，以便区别于原表示迭代后的系数，以便区别于原 系数。系数。 其目标函数如何呢？其目标函数如何呢？ 代入目标函数代

31、入目标函数,整理后：整理后： )2, 1( 1 mij n mj ijii xabx . 69 步骤1：初始基可行解的确定 方法方法1:观察法观察法 方法方法2: 当当 时时,加松弛变量加松弛变量,化标准型化标准型. X1 +a1,m+1xm+1+a1,nxn=b1 x2+a2,m+1xm+1+a2,nxn=b2 Xm+am,m+1xm+1 + +am,nxn=bm (1.20) (1.21) b x p j n j j 1 (1.22) 则得则得:B=(P1,P2,Pm), 移项得移项得: . 70 X 1=b1-a1,m+1x m+1 - -a1nxn x2=b2-a2,m+1 1x m+

32、1 - -a2n,xn xm=bm-am.m+1xm+1- -amnxn 令非基变量令非基变量xm+1=xm+2=xn=0 xi=bi(i=1,2,m) x=(x1,x2,xm,00)T(b1,b2,0,.0)T (1.23) . 71 （方法（方法3）: 约束是约束是形式，人造基形式，人造基 大大M法，两阶段法法，两阶段法 . 72 步骤2：基可行解的转换 )( )( 00 2 0 1 )0( 00 2 0 1 )0( m n xxx xxx x x bp m i ii x 1 0 ii m i bx b b xxx m 0 1 000 1 1 0 1 0 0 1 设有初始基可行解设有初始基

33、可行解 基矩阵可以是单位矩阵形式基矩阵可以是单位矩阵形式 . 73 mnmjmmm njm njm baaa baaa baaa ,1, 2, 2, 21, 2 1, 1, 11, 1 10 0 00 01 bppppp nj1mm1 0 11 m i ijj m i ijj aa ii pppp bp m i ii x 1 0 由于由于 0)(,0 1 m i ijj a i pp bppp ji n jmk k m i iji ax , 11 0 0*)( ) 00 ,( 0 1 0 1 ) 1 ( mjmj axaxx lj l ij ij i a x a a x i 0 0 0|min

34、 . 74 步骤3 最优性检验 代入目标函数和将 )1()0( xx jjj m i ijij m i jijii m i ii zzcz accz caxcz xcz )0()0( 1 )0( 1 0)1( 1 0)0( )( 如果，如果，j j0,00)=k k 3) 若有一个若有一个m+k0,对一切对一切i=1,2,m,有有ai,m+k0, 无界解无界解(或无最优解或无最优解). . 76 4 单纯形表 4目标函数目标函数 4系数矩阵：基向量，非基向量系数矩阵：基向量，非基向量 4检验数检验数 4换入、换出变量换入、换出变量 4迭代迭代 . 77 cjc1cmcm+1 cni cBxBb

35、x1xmxm+1 xn c1x1b110a1m+1a1n1 c2x2b200a2m+1a2n2 cmxmbm01amm+1amnm -z00 1 1 1 im m i im acc i m i ib c 1 in m i in acc 1 . 78 1求初始基可行解，建立初始单纯形表求初始基可行解，建立初始单纯形表 2最优性检验。若非基变量检验数最优性检验。若非基变量检验数 则则 停止迭代计算，否则转入下一步。停止迭代计算，否则转入下一步。 3求另一个更好的基可行解。求另一个更好的基可行解。 (1)确定换入变量，确定换入变量，xk为换入变量。为换入变量。 (2)确定换出变量确定换出变量 ，xl

36、为换入为换入 变量。变量。 0 1 m i ijijj acc kj )0max( lk l ik ik i a b a a b ) 0min( 主要步骤：主要步骤： . 79 4 若换入变量若换入变量xk所在列的系数所在列的系数aik均小于等均小于等 于于0，原线性规划无界，停止计算，否则，原线性规划无界，停止计算，否则 转入下一步。转入下一步。 5 初等变换，求另一个单位矩阵对应的基初等变换，求另一个单位矩阵对应的基 可行解。将主元素可行解。将主元素alk变换为变换为1，所在列，所在列 的其余元素变为的其余元素变为0，得到新的单纯形表。，得到新的单纯形表。 . 80 Max Z=2x1+3

37、x2+0 x3+0 x4+0 x5 x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5 =12 x1, x2, x3, x4, x5 0 例题5： . 81 (1)x3, x4, x5,为基变量为基变量,初始基可行解初始基可行解:x0=(0,0,8,16,12), 初始单纯形表如下：初始单纯形表如下： cj23000i cBxBbx1x2x3x4x5 12100 40010 04001 -z0 m i ijijj acc 1 lk l ik ik i a b a a b )0min( x3 x4 x5 0 0 0 8 16 12 23000 4 - 3 . 82 (2) 进行初等

38、行变换，在进行初等行变换，在xB列中用列中用x2换换x5 ，得到新，得到新 的基解的基解x1 =(0,3,2,16,0), z=9. cj23000i cBxBbx1x2x3x4x5 0 x321010-1/2 0 x41640010 3x2301001/4 -z-9 2 000-3/4 2 4 - . 83 (3)重复上述计算过程重复上述计算过程, x5换出换出x4变量。变量。 cj23000i cBxBbx1x2x3x4x5 2x121010-1/2- 0 x4800-4124 3x2301001/412 -z-1300-201/4 . 84 (4)重复上述计算过程重复上述计算过程:最优解

39、最优解x* =(4,2,0,0,4), z=14. cj23000i cBxBbx1x2x3x4x5 2x141001/40 0 x5400-21/21 3x22011/2-1/80 -z-1400-1.5-1/80 . 85 课堂练习 0, 12002 1000 . . 6 . 045. 0max 4321 421 321 21 xxxx xxx xxx ts xxZ . 86 第一步 cj0.450.600 i cBxBbx1x2x3x4 0 x3100011101000 0 x412001201600 -z00.450.600 . 87 第二步 cj0.450.600 i cBxBbx1

40、x2x3x4 0 x34001/201-1/2800 0.6x26001/2101/21200 -z-3600.1500-0.3 . 88 第三步 cj0.45 0.600 i cBxBbx1x2x3x4 0.45x1800102-10 0.6x220001-110 -z- 480 00-0.3-0.15 . 89 1.5 单纯形法的进一步讨论 1.5.1 1.5.1 人工变量法人工变量法 模型约束方程模型约束方程“”型，引入松弛变型，引入松弛变 量标准化后，系数矩阵含有单位阵，容量标准化后，系数矩阵含有单位阵，容 易得到初始基可行解。对于一些标准化易得到初始基可行解。对于一些标准化 后的问题

41、，系数矩阵不含单位阵，无法后的问题，系数矩阵不含单位阵，无法 直观地得到初始基可行解。直观地得到初始基可行解。 . 90 Min Z=10 x1+8x2+7x3 2x1+2x2 6 x1+x2 +x3 4 x1, x2, x30 Max Z=-10 x1-8x2-7x3+ 0 x4+ 0 x5 2x1+2x2 -x4 = 6 x1+x2 +x3 - x5= 4 x1, x2, x3 , x4 , x5 0 标准化 . 91 系数矩阵为系数矩阵为 无法得到初始基可行解。当取无法得到初始基可行解。当取x x4 4和和x x5 5为初始基变为初始基变 量，当其它非基变量等于量，当其它非基变量等于0

42、0时，时， x x4 4=-6=-6， x x5 5=-4=-4， 不是可行解。为从不是可行解。为从A A中得到可行基，在中得到可行基，在A A中加上中加上 一列，变为一列，变为 10111 01012 A 010111 101012 A 6 4 . 92 即将标准形线性规划的约束方程化为：即将标准形线性规划的约束方程化为： 2x1+2x2 -x4 + x6= 6 x1+x2 +x3 - x5 = 4 x1, x2, x3 , x4 , x5 , x6 0 变量变量x x6 6 称为人工变量。 称为人工变量。 x x3 3和和x x6 6构成初始构成初始 可行基，令其它非基变量为可行基，令其它

43、非基变量为0 0，则可得一初，则可得一初 始基可行解始基可行解x x0 0=(0,0,4,0,0,6)=(0,0,4,0,0,6)。 . 93 4标准化后，第一个约束方程已严格为标准化后，第一个约束方程已严格为 “=”=”，左边加入人工变量，左边加入人工变量x x6 6后，可能后，可能 破坏约束。但如果人工变量破坏约束。但如果人工变量x x6 6= = 0 0，则不，则不 会破坏。会破坏。 4人工变量在初始基可行解中不为人工变量在初始基可行解中不为0 0，但，但 如果在后面的迭代过程中，如能把所有如果在后面的迭代过程中，如能把所有 人工变量转变为非基变量，则人工变量人工变量转变为非基变量，则人

44、工变量 都为都为0 0，这样，原有约束方程不会被破，这样，原有约束方程不会被破 坏。坏。 . 94 4如果已得到最优解如果已得到最优解( (满足最优检验条件满足最优检验条件) )， 而基变量中还有人工变量而基变量中还有人工变量( (人工变量不全人工变量不全 为为0)0)，则无解，不存在满足所有约束方，则无解，不存在满足所有约束方 程的可行解。程的可行解。 4将人工变量从初始基可行解中转变为非将人工变量从初始基可行解中转变为非 基变量的方法有基变量的方法有 (1)(1)大大MM法法(2)(2)两阶段法。两阶段法。 . 95 例7 0,., 93 12 4 003max 0, 93 12 4 3m

45、ax 51 32 5321 4321 5431 321 32 321 321 31 xx xx xxxx xxxx xxxxz xxx xx xxx xxx xxz 标准化标准化 . 96 0 93 12 4 0003 732 65321 4321 7654321 i x xxx xxxxx xxxx MxMxxxxxxZMax 1000130 0110112 0001111 p4p6p7 增加人工变量 . 97 cj-30100-M-M CBxmbx1x2x3x4x5x6x7 0 x441111000 -Mx61-21-10-110 -Mx790 310001 -Z -3- 2M 4M10-

46、M 00 . 98 cj-30100-M-M CBxmbx1x2x3x4x5x6x7 0 x4330211-10 0 x21-21-10-110 -Mx766 0403-31 -Z 6M -3 0 4M +1 03M -4M 0 . 99 cj-30100-M-M CBxmbx1x2x3x4x5x6x7 0 x400001-1/2 1/2-1/2 0 x23011/30001/3 -3x11102/301/2-1/2 1/6 -Z 00303/2 -M +3/2 -M -1/2 (x1,x2,x3,x4,x5)=(0,5/2,3/2,0,0) Z=3/2 . 10 0 cj-30100-M-M

47、 CBxmbx1x2x3x4x5x6x7 0 x400001-1/2 1/2-1/2 0 x25/2-1/2 100-1/4 1/41/4 1x33/23/2 0103/4-3/4 1/4 -Z3/2 -9/2 000-3/4 -M +3/4 -M -1/4 (x1,x2,x3,x4,x5)=(0,5/2,3/2,0,0) Z=3/2 . 10 1 课堂练习 0, 12002 1000 . 6 .045.0max 21 21 21 21 xx xx xx ts xxZ . 10 2 0, 12002 1000 . . 06 . 045. 0max 54321 521 4321 54321 xx

48、xxx xxx xxxx ts MxMxxxxZ 标准型标准型 . 10 3 cj0.450.60-M-Mi cBxBbx1x2x3x4x5 -Mx4100011-110 1000 -Mx5120012001600 0.4+2M 0.6+3M -M . 10 4 cj0.450.60-M-Mi cBxBbx1x2x3x4x5 -Mx44000.50-11-0.5 800 0.6x26000.51000.5 120 0 cj-zj 0.15+ 0.5M 0-M 0-0.3- 1.5M 0.45X180010-22-1 - 0.6x2200011-11200 cj-zj0 0 0.3-0.3- M

49、 -0.15- M . 10 5 cj0.450.60-M-Mi cBxBbx1x2x3x4x5 0.45X1120012001 - 0 x3200011-11- cj-zj0-0.30-M-0.45- M Z=0.45*1200+0*200=540 人工变量是人工变量是 非基变量非基变量 . 10 6 5.2 两阶段法 4大大MM法不利于计算机计算法不利于计算机计算 4两阶段法两阶段法 4构造合适目标函数找出一组可行基构造合适目标函数找出一组可行基 4构造构造Z=-xZ=-x1 1-x-x2 2 ；也能换出人工变量。 也能换出人工变量。 . 10 7 4Z Z达到最大值达到最大值0 0， x

50、 x1 1，x x2 2为为0 0，有两种可，有两种可 能能: 1: 1、 x x1 1，x x2 2成为非基变量。得到不包成为非基变量。得到不包 含人工变量的初始可行基。进入下一阶含人工变量的初始可行基。进入下一阶 段。段。 2 2、 x x1 1或或x x2 2是基变量，但为零。退化。是基变量，但为零。退化。 Z Z达到最大但不是达到最大但不是0 0，说明起码不可能将，说明起码不可能将 人工变量完全换出，问题无解。人工变量完全换出，问题无解。 . 10 8 0 93 12 4 003 732 65321 4321 76 54321 i x xxx xxxxx xxxx xxzMax xxx

51、xxzMax . 10 9 cj00100-1-1 CBxmbx1x2x3x4x5x6x7 0 x441111000 -1x61-21-10-110 -1x790 310001 -Z -2400-100 第一阶段1： . 11 0 cj00000-1-1 CBxmbx1x2x3x4x5x6x7 0 x4330211-10 0 x21-21-10-110 -1x766 0403-31 -Z 6 0 4 03-40 第一阶段2： . 11 1 cj00000-1-1 CBxmbx1x2x3x4x5x6x7 0 x400001-1/2 1/2-1/2 0 x23011/30001/3 1x111 0

52、2/301/2-1/2 1/6 -Z0 00000-1-1 第一阶段3： . 11 2 cj-30100 CBxmbx1x2x3x4x5 0 x400001-1/2 0 x23011/300 -3x111 02/301/2 -Z 003 0 3/2 第二阶段1： . 11 3 cj-30100 CBxmbx1x2x3x4x5 0 x400001-1/2 0 x25/2-1/2 100-1/4 1x33/23/2 0103/4 -Z -9/200 0 -3/4 第二阶段2： . 11 4 5.3 解的判别 (1) (1) 无界解无界解 目标函数为最大，如换入变量目标函数为最大，如换入变量x xk

53、 k所所 在列所有技术系数均小于等于在列所有技术系数均小于等于0 0，即，即 a aik ik 0(i=1,2m), 0(i=1,2m), 则利用最小规则无则利用最小规则无 法得到一个换出变量。法得到一个换出变量。 . 11 5 (2) 退化解退化解 一般情况，基可行解中非一般情况，基可行解中非0分量个数分量个数 等于约束方程的个数等于约束方程的个数m。如果某一基可。如果某一基可 行解中非行解中非0分量个数小于分量个数小于m，即，即 一些基变一些基变 量值等于量值等于0，该基解为退化解。，该基解为退化解。 . 11 6 按按 规则确定换出变量时规则确定换出变量时, ,同时存在两个以同时存在两个

54、以 上相同的最小比值上相同的最小比值, ,在下一次迭代中就有一个在下一次迭代中就有一个 或几个基变量等于零或几个基变量等于零, ,这就出现了退化解这就出现了退化解, ,继续继续 迭代迭代, ob, ob值不变值不变, ,造成死循环。造成死循环。 判别判别: :当当b bi i中有一个以上为中有一个以上为0 0时时, ,就称为退化就称为退化. . 避免避免: :摄动法摄动法, ,词典序法词典序法,”,”勃兰特勃兰特”法法 . 11 7 (2) (2) 无穷多解无穷多解 非基变量检验数等于非基变量检验数等于0 0，表示换入，表示换入 换出一样，所以有无穷多解。换出一样，所以有无穷多解。 . 11

55、8 小结小结 确定初始基可行解确定初始基可行解 检查是否为最优解检查是否为最优解 求最优解目标函数求最优解目标函数 确定改善方向确定改善方向 求新的基可行解求新的基可行解 Y 化标准型化标准型 . 11 9 1.6 对偶理论与对偶单纯形法对偶理论与对偶单纯形法 4例例2 2 某灌区在年初估算可供水量为某灌区在年初估算可供水量为360360 万万m m3 3, ,计划灌溉小麦、玉米两种计划灌溉小麦、玉米两种. .总面总面 积积1000hm1000hm2 2, ,两种作物的毛灌溉定额及两种作物的毛灌溉定额及 灌溉净效益如表灌溉净效益如表，问该年两种作物的问该年两种作物的 种植计划如何安排可使灌溉总

56、净效益种植计划如何安排可使灌溉总净效益 最大？最大？ . 12 0 作物作物毛灌溉定额毛灌溉定额 （m3/hm2） 灌溉净效益灌溉净效益 （元（元/ hm2） 小麦小麦 6000 600 玉米玉米 3000 450 . 12 1 模型模型 480 0, 3606 . 03 . 0 1000. . 6 . 045. 0max 21 21 21 21 Z xx xx xxts xxZ . 12 2 4如果灌区不种植，土地出租，水资源卖如果灌区不种植，土地出租，水资源卖 掉，各自该卖什么价格。掉，各自该卖什么价格。 4卖出的获利不能低于自己生产的获利，卖出的获利不能低于自己生产的获利， 也就是所谓的机会成本。也就是所谓的机会成本。 . 12 3 作物作物毛灌溉定额毛灌溉定额 （m3/hm2） 灌溉净效益灌溉净效益 （元（元/ hm2） 小麦小麦 6000 600 玉米玉米 3000 450 0, 45.03.0 6.06.0