高等教育运筹学课程--线性规划(2).ppt

《高等教育运筹学课程--线性规划(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划（2）单纯形解法（SimplexMethod）1、单纯形方法基本思路从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），以改进初始解。继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。（1）消去法例1：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？解：数学模型maxS=6

2、x1+4x2s.t.2x1+3x21004x1+2x2120x1,x20解：引进松弛变量x3,x40数学模型标准形式：maxS=6x1+4x2s.t.2x1+3x2+x3=1004x1+2x2+x4=120x1,x2,x3,x40约束条件的增广矩阵为：2310100（Ab)=4201120显然r(A)=r(Ab)=2<4,该问题有无穷多组解。令A=（P1，P2，P3，P4）=23104201X=（x1,x2,x3,x4)A=（P1，P2，P3，P4）=23104201X=（x1,x2,x3,x4)B=(P3，P4）=1001P3，P4线性无关，x3

3、,x4是基变量，x1,x2,是非基变量。用非基变量表示的方程：x3=100-2x1-3x2x4=120-4x1-2x2(I)S=6x1+4x2称(I)为消去系统，若b=(100,120)t0则称为正消去系统。令非基变量（x1,x2）t=（0，0）t得基础可行解：x(1)=(0,0,100,120)t且：S1=0经济含义：不生产产品甲乙，利润为零。分析：S=6x1+4x2分别增加单位产品甲、乙，目标函数分别增加6、4，即利润分别增加6百元、4百元。增加单位产品对目标函数的贡献，这就是检验数的概念。增加单位产品甲（x1）比乙对目标函数的贡献大（检验数最大），把

4、非基变量x1换成基变量，称x1为进基变量，而把基变量x4换成非基变量，称x4为出基变量。（在选择出基变量时，一定保证消去系统为正消去系统）（最小比值原则）x3=100-2x1≥0x4=120-4x1≥0确定了进基变量x1，出基变量x4以后，得到新的消去系统：x3=40-2x2+（1/2）x4x1=30-（1/2）x2-（1/4）x4(II)S=180+x2-（3/2）x4令新的非基变量（x2，x4）=（0，0）t得到新的基础可行解：x(2)=(30,0,40,0)tS2=180经济含义：生产甲产品30个，获得利润18000元。这个方案比前方案优，但是否是最优

5、？分析：S=180+x2-（3/2）x4非基变量x2系数仍为正数，确定x2为进基变量。在保证常数项非负的情况下，确定x3为出基变量。得到新的消去系统：x3=40-2x2≥0x1=30-（1/2）x2≥0x1=20+（1/4）x3-（3/8）x4x2=20-（1/2）x3+（1/4）x4(III)S=200-（1/2）x3-（5/4）x4令新的非基变量（x3,x4）t=（0,0）t得到新的基础可行解：x(3)=(20,20,0,0)tS3=200经济含义：分别生产甲乙产品20个，可获得利润20000元。分析：S=200-（1/2）x3-（5/4）x4目标函数中

6、的非基变量的系数无正数，S3=200是最优值，x(3)=(20,20,0,0)t是最优解。该企业分别生产甲乙产品20个，可获得最大利润20000元。（2）已知初始可行基求最优解线性规划标准型的矩阵形式(3)：MaxS=CX(1-17)s.t.AX=b(1-18)X0(1-19)a11a12….a1nb1A=a21a22….a2nb=b2…………………………………………am1am2….amnbnc1x10c2x20Ct=X=0=……………..cnxn0并且r(A)=m

7、=(CB,CN)由（1-17）（1-18）S=(CB,CN)(XB,XN)t=CBXB+CNXNs.t.（B,N）(XB,XN)t=BXB+NXN=b因为B为一个基,det(B)<>0有XB=B-1b-B-1NXNS=CBB-1b+(CN-CBB-1N)XN令非基变量XN=0则:Xt=(XB,XN)=（B-1b,0）为基础解，其目标函数值为S=CBB-1b只要XB=B-1b0,Xt=（B-1b,0）0X为基础可行解,B就是可行基。另外，若满足CN-CBB-1N0则对任意的x0有S=CXCBB-1b即对应可行基B的可行解x为最优解。定理1-5（最优解

8、判别准则）对于可行基B,若C-CBB-1A0则对应