单纯形法

单纯形法内容修正单纯形法原理计算逆的乘积形式变量有界的情形基本可行解概念的推广基本可行解的改进(原理)计算求初始基本可行解修正单纯形法修正单纯形法-原理1111ˆ运用单纯形方法时，如果知道可行基的逆，就能利用和原始数据计算基变量的取值及判别数。因此在整个计算过程中，只要保存原始数据和现行基的逆即可。修正单纯形法的基本思想就是给定初始基本可行解后，通过修改旧基的逆来获得新基的逆，进而完成单纯形法其他运算。BBBB121212-1-1-112rˆ=(,,,,,),ˆ=(,,,,,).,,,,,,,,,,,,,,,,,,ˆrmmrmBBBBBBkBBBBBkrmkky由修改获得：主元消去前，可行基为主元消去后，新的可行基为设初始单纯形表中，系数矩阵是(),其中作为初始基，当作为基矩阵时，系数矩阵转化为(),当作为基矩阵时，应以作为主BBBppppBpppppppppIIBeeeeyBB-112ˆˆ,,,,,,,,,ˆ,,ˆrBmrikijijrjrkrjrjrkybbbirybby元，消去，把化为单位矩阵，即()由上面两式可知：BeeyeeB减少单纯形表中需要保存的数据量，减少在计算机中的存储量。修正单纯形法-计算123451234513452345min23..325,262301,,5.jxxxxxstxxxxxxxxxxxxxxj≤≤，≤，≥，解：123451234561345723458min23..325,262301,,8.jxxxxxstxxxxxxxxxxxxxxxxxj==，=，≥，约束方程的系数矩阵12345678678311(,,,,,,,)31112100520111010,6.012110013=(,,),(5,6,3),TB取初始可行基，组成下表AppppppppbBpppIbBbw=cBwBcb1Bb单纯形乘子目标函数值11223344551144.2,1,1,3,1:(111).jjjjTkkzcczczczczczc对于每个非基变量，计算判别数计算主列wpyBpyBp0000678xxx100010001563代入数值：修正单纯形法-计算把主列置于逆矩阵表的右边，组成下列表：wBcb1Bbkxkkzcky代入数值：0000678xxx1000100015634x311103018648xxx110010011116924=1y以为主元，经主元消去得：12max{}0.min04kkjjkkkkkirikrkikrkzczczcbbyryyy0第次迭代，重复上面的计算过程：（1）由单纯形乘子计算判别数，选取主列如果≤，则停止计算，现行基本可行解是最优解，否则进行下一步；（2）计算主列若≤，则停止计算，问题不存在有限最优解，否则进行下一步；（3）按最小比值确定主行，令，行为主行，以为主元进行主元消去。经过次这wyBpy12345678min076.jjzcxxxxxxxxf样的迭代过程，得到所有判别数≤，达到最优解为（,,,,,,,）=（0,0,9,26,11）目标函数最优值修正单纯形法-逆的乘积形式逆的乘积形式是指可行基的逆用初等矩阵的乘积来表达，这样可以大大减少在计算机中的存储量。11-111-1-1-1-1(,,,,),,ˆ(,,,,)(,,,,)(,,,,),ˆ==.rmrmBBBkBBkBkmkm设有基矩阵其逆已知，假设在迭代中用系数矩阵的非基列替换原来的基列得到新基则BpppBppBpppBeByBeBeyeBTBTBEB1122-1-1-112111100100010010,00000100010011===kkrkkkrkrkrkmkmkrkyyyyyyyyyyy则有初等矩阵完全由主列元素确定。若在第次迭代中，基的逆，那么第2次迭代中，，在第TEEBIBEBE-1121=.tttt次迭代中，基的逆BEEE11tiBtr存储时，只需存储个初等矩阵，而存储每个初等矩阵，只需存储它的非单位向量列和该列在初等矩阵中的位置。E修正单纯形法-逆的乘积形式121212111112=(,,,)1000=(,,,)(,,,,,,),01,1.=(,,,)mmmriirmimiikrkrrkTmmcccggccccccgccggyyirgymaaa分析如何利用这些初等矩阵计算单纯形方法中所需要的数（1）用初等矩阵右乘一个维行向量，则其中（2）用初等矩阵左乘一个维列向量，则EccEEpE1111112211112111000ˆ=001==((())).=(rrrrrrrmmmmBtBttktktaggaaggaagaaggaag，（3）计算单纯形乘子：计算主列：pa+gwcBcEEEyBpE1211111(())).==().kttt计算右端列：EEpbBbEBbr列修正单纯形法-逆的乘积形式12312312323min2..8,22401,2,3.jxxxstxxxxxxxxxj≤≤，≤，≥，解：12312341235236min2..8,22401,,6.jxxxstxxxxxxxxxxxxj==，=，≥，111100=111010012001系数矩阵AB1114152631111111222233333381==2,480=2,=0.400,(0,0,0)1,1,2,max.BNBjjxxxxxxfzcczcczcczczc第次迭代：在现行基本可行解处，目标函数值bBbxxwcBwpwpwp3131313133361131:1841,8,2.122min033111,3222.kkiikkikTbbyybbyyyxr计算主列则,因此为离基变量。则初等矩阵的非单位向量列出现在的位置，即的第列，由主列得到此列在计算机中存储，用它描述初等矩阵yyBpEEyggE修正单纯形法-逆的乘积形式1121141523621333111111222266662=()4,2604,0,20()0224,==(0,0,2)(0,0,1),1,2,BNBxxxxxxffbzczcczcczcc第次迭代：bBbEBbxxwcEEwpwpwp6222212121224221.max{}2,13221111(1),2201122min{0}.=1jjiiizczcxbbyyyxr因此为进基变量。因此第一个变量为离基变量，初等矩阵的非单位向量列出现在的位置，由主列得到yEpEgy122221543632221211(,,).13333236041=()=4462,322413402,0,40()Txxxxxxffzcb，存储第次迭代：BNggbEBbExx2121111144446666123min42412,41=(1,0,2)(,0,),337,34,31,30,12.Bjjzcczcczcczcxxxf所有≤，得到最优解(,)=(0,4,4).目标函数最优值wcEEEEwpwpwp变量有界的情形变量有界的情形-基本可行解概念的推广mins.t.=,.≤≤cxAxblxu(0)(0)(0)=mn-m基本解：设是的一个解，若的个分量（基变量）所对应的的列线性无关，其余个分量（非基变量）取上界或下界。基本可行解：中基变量取值介于上下界之间（包括等于上或下界）。xAxbxAx1211221212-1-1-112===BNNBBBABbBB，，，对应取下界的非基变量，对应取上界的非基变量，则基本可行解表达式，且≤≤NNNNBNNNNNlNuxxxlxulxu12112212112211221-1-1-1(0)12(0)(0)(0)(0)(0)(0)(0)0-1-11-12-1===(,,).()()()(BNNBBNNNNBBNBNBjjjjRfzclz基本可行解，在处的目标函数值NNBNNNNNNBbBNlBNuxxxlxuccccxcxcxcxcBbcBNclcBNcucBb212-1-1-112),1=,jjjjRkBcunmx令个非基变量固定不变，仍取下界或上界数值，而令一个非基变量改变，使目标函数值减小。约束方程=的任意解，有NNAxbxxBbBNxBNx变量有界的情形-基本可行解的改进1122112212-1-1-112-112++()()()().00BBNNBBNBNBjjjjjjjRjRjjjjjjfzcxzcxjRzcxjRzcx在处的目标函数值在改变非基变量的取值时，取下界数值的只能增大，取下界数值的只能减小。当时，若，则随着的增大目标函数值减小；当时，若，则随着的减小目标NNNNxcxcxcxcBbcBNcxcBNcxcBb21212,max{}min{}max{}max{max{},max{}}.kjjjjjjjRjRjRjjjjjRjRxzczcczzcczk函数值减小；为选择最有利于目标函数值减小的应从和-中选择最大值：如果该最大值大于零，则相应下标；否则现行基本可行解即最优解。选择下标k变量有界的情形-基本可行解的改进rkBxx假设这个最大值大于零，确定的取值及选择离基变量121111112(0)011=,=ˆ=,ˆ=.().ˆ=ˆˆˆmin0,=.irkkkBNNkkkkBkkkkBkkBkkBkiBrBikikrkkkRxlffzcblblyyy0设则需满足下列条件：（1）≥≤，应取≤，，≤xBbBNlBNuBPbybxxbylybly，223123ˆ=,ˆ,ˆˆmin0,=.=.=min{,,}.irBkkBkkBkBiBrikikrkkkkkkkububyyyxul0（2）≤≤应取≤，，≥（3）不越上限，则≤为保持可行性且使目标函数值尽可能减小，令xbyuyuby变量有界的情形-基本可行解的改进20123123=,0.ˆ=+,+(),ˆˆmin0,=.ˆˆmin0,=.=,=min{,,}.irirkkkkBkkkkkiBrBikikrkkBiBrikikrkkkkkkRxuffzcblblyyyu