3.2单纯形法的矩阵计算ppt课件

1、;.3.1 单纯形法的矩阵描述单纯形法的矩阵描述3.2 单纯形法的矩阵计算单纯形法的矩阵计算3.3 对偶问题的提出对偶问题的提出3.4 线性规划的对偶理论线性规划的对偶理论3.5 影子价格影子价格3.6 对偶单纯形法对偶单纯形法3.7 灵敏度分析灵敏度分析;.Page 3Page 4 改进单纯形法又称为逆矩阵法或修正单纯形法改进单纯形法又称为逆矩阵法或修正单纯形法, ,是在原来单纯形法基础上是在原来单纯形法基础上加以改进加以改进. .改进单纯形法特点是用矩阵计算。改进单纯形法特点是用矩阵计算。 在每次迭代过程中不必要地计算了很多与迭代无关的数字在每次迭代过程中不必要地计算了很多与迭代无关的数字

2、, , 影响了计算影响了计算效率效率. . 单纯形法的迭代过程实质上是从一组基到另一组基的变换单纯形法的迭代过程实质上是从一组基到另一组基的变换. .而每次迭代而每次迭代中真正有用的数字是基变量列数字、基的逆矩阵、非基变量检验数以及最大中真正有用的数字是基变量列数字、基的逆矩阵、非基变量检验数以及最大正检验数所对应的非基变量系数列向量。正检验数所对应的非基变量系数列向量。 可以看在单纯形法中关键在于求可以看在单纯形法中关键在于求B B-1-1, ,3.2 单纯形法的矩阵计算单纯形法的矩阵计算Page 53.2 单纯形法的矩阵计算单纯形法的矩阵计算()()ljljlkljijijiklkaail

3、aaaaaila ,2ijljijljlkaaaaa 设设是是本本次次表表中中的的数数字字，是是迭迭代代后后表表中中数数字字，是是主主元元素素，由由第第 章章知知111211212mlllmmmmmaaaaaaaaa1111211212/0101/00/1klkmlllmlkmklkmmmmaaaaaaaaaaaaaa Page 63.2 单纯形法的矩阵计算单纯形法的矩阵计算11111(, ,)newllmBEBEeeee , , 其其中中111/1/kklklklkmklkmkaaaPaaaaa 主主元元素素这样就求得新基的逆矩阵。这样就求得新基的逆矩阵。 Page 7求解步骤：.42 .,

4、. 4. ,)()(0)()()(min ,)(0)(max . 3., 0. 2,. 111111111步直到求出结果重复的求出此得到新的出基行对应的则若入基则若基变换否则转下一步则得最优解若求取可行基BBBxlPBbBPBPBbBxNBCCBBllklikikiikkNjNjBNNPage 8n 改进单纯形法的步骤：改进单纯形法的步骤：（1 1）据）据LPLP问题的标准型，确定初始基变量和初始可行基。求逆矩阵问题的标准型，确定初始基变量和初始可行基。求逆矩阵-1-1，得初始基本可行解得初始基本可行解 （2 2）计算单纯形乘子）计算单纯形乘子 和目标函数值和目标函数值（3 3）计算非基变量检

5、验数）计算非基变量检验数, ,若若，则已得最优解，停止计算；否则转下一步。，则已得最优解，停止计算；否则转下一步。（4 4）据，确定为换入变量，计算）据，确定为换入变量，计算, ,若若 0 0，则问，则问题没有有限最优解，停止计算，否则转下一步。题没有有限最优解，停止计算，否则转下一步。-1B=C B-1NNBN=C -C B N=C -N-1BZ=C B b=b-1BNX =B b,X0jjkmax / 0 =kx-1kB P-1kB PN0Page 9（5 5）据）据 ，确定，确定 为换出变量。为换出变量。 （6 6）用替代）用替代 得新基得新基1 1，由变换公式，由变换公式 计算计算1

6、1-1-1，求出新的基本，求出新的基本可行解。可行解。 其中为变换矩阵，构造方法：其中为变换矩阵，构造方法：将换入变量将换入变量 对应的系数列向量对应的系数列向量 做如下变形，主元素做如下变形，主元素 （应在主对角线（应在主对角线上）取倒数，其他元素除以主元素上）取倒数，其他元素除以主元素 并取相反数。然后用它替换单位矩阵出并取相反数。然后用它替换单位矩阵出发，把换出变量发，把换出变量 在基在基B B中的对应列的单位向量。中的对应列的单位向量。重复（重复（2 2）（）（6 6）直至求得最优解。）直至求得最优解。 -1-1-1iki-1-1kik(B b)(B b)min/(B P ) 0 =(

7、B P )(B P )llxlPlkP-1-11k BE Blk Elkal-1kB PxlkxkalPage 10例用改进单纯形法求解第1章第1节例1123451231425max2300028416412zxxxxxxxxxxxx Page 11解：第解：第1步步(1)确定初始基和初始基变量：确定初始基和初始基变量：034503451( ,) ,1;1TBXx x xBPPP（2）计算非基变量的检验数，确定换入变量）计算非基变量的检验数，确定换入变量。012( ,)TNXx x10111B 000100012(,)NNBCC B NNP P 121001 22,3(0,0,0) 0104

8、02,3,0010 4x x Page 122 改进单纯形法改进单纯形法 表示选择表示选择0的元素的元素(3) 确定换出变量确定换出变量 101021025min0812min, ,324iiB bB PB Px （4）基变换）基变换新基1342,BPPP2121/ 2001/44P ；Page 132 改进单纯形法改进单纯形法1111011/ 21101/ 21010101/41001/4BE B（5）计算非基变量的系数矩阵）计算非基变量的系数矩阵115(,)TNXxx 1111111/ 2111/ 241044011/4101/4NB N Page 142 改进单纯形法改进单纯形法（6）计

9、算）计算RHS1111/ 2821016161/4123B b 第第1步计算结束后的结果步计算结束后的结果),(),(C,CC;x ,xX;x ,x ,xX;P,P,PBNBTNTB023001111512432431价值系数非基变量基变量基Page 152 改进单纯形法改进单纯形法第第2步：重复第步：重复第1步的步骤。步的步骤。（2）计算非基变量的检验数。计算非基变量的检验数。11111111515(,)101/21 02,0(0,0,3) 0104 0001/40 1(2, 3/4),NNBCC B NNP Px x对应换入变量注：115( , )TNXx xPage 162 改进单纯形法

10、改进单纯形法（3）确定换出变量）确定换出变量 111111113min02 16 3min,2140iiB bB PB Px （4）由此得到新的基。）由此得到新的基。 2142,BP P P 12011440P 主主元元素素Page 172 改进单纯形法改进单纯形法11221100101/ 2101/ 2410010412001001/4001/4BE B （4）计算）计算RHS 。 12101/ 282412168001/4123B b Page 182 改进单纯形法改进单纯形法第2步计算结束后的结果),(),(C,CC;x,xX;x,x,xX;P,P,PBNBTNTB00302222253

11、2412412价值系数非基变量基变量基Page 192 改进单纯形法改进单纯形法第第3步：重复第步：重复第2步的步骤。步的步骤。(2)计算非基变量的检验数。计算非基变量的检验数。235(,)TNXxx (3)确定换出变量确定换出变量 121251254min0283min,41/ 2 2 1/4iiB bB PB Px 22212223535(,)101/ 21 00,0(2,0,3)4130 0001/40 12,1/4,NNBCC B NNP Pxx Page 20(5)由此得到新的基由此得到新的基 3152,;BP P P 31/41/ 21/8 125101/ 201/ 2412000

12、1/411/42B P 1133211/40101/ 201/ 2041201/81001/401/4021/ 211/ 21/80BE B 5x入入量量的的系系 向向量量是是Page 212 改进单纯形法改进单纯形法计算非基变量的检验数计算非基变量的检验数 333133334(,)01/401 00,0(2,0,3)21/ 210 11/ 21/800 03/ 2,1/8NNBCC B NNP P 已无正的检验数已无正的检验数33,4()TNXx x Page 222 改进单纯形法改进单纯形法最优解为1*153201/48421/ 21641/ 21/8122xXxB bx 最优值为 3*1

13、342,0,34142BzC B b Page 232 算例算例max z = 5x1+2x2+3x3x4+x5 x1+2x2+2x3+x4 = 8 3x1+4x2+x3+x5 = 7 x1, x2, x3, x4, x5 0 1） 101430122154321pppppA系数矩阵：系数矩阵：78b常数项：常数项：11325c价值系数：价值系数：1001540ppB7878100110540bBxxXB 403122325 143221113253210N x3 入基入基41728minmin31010PBbB x4 出基出基Page 242） 101430122154321pppppA系数矩阵：系数矩阵：78b常数项：常数项：11325c价值系数：价值系数：1102531ppB347812/102/111531bBxxXB 241164125 04312112/102/1131254211N x1 入基入基562/532/14minmin11111PBbB x5 出基出基Page 253） 3112131ppB5/65/17785/25/15/15/312132bBxxXB5259526 1040125/25/15/15/3531125422N最优解：最优解：X*