《运筹学》胡运权清华版-2-02单纯形算法的矩阵表

单纯形法的矩阵描述编辑pptC0基系数基列常数列XXS0XSbAIcj-

zjC0初始单纯形表线性规划问题：标准型：一、初始单纯形表编辑ppt二、迭代后的单纯形表（当前可行基——B）

基列常数列XXSXB？？？cj-

zj？？？则表结构编辑ppt分析：初始表迭代后任一表初等行变换初等行变换左乘一个适当矩阵SS＝？编辑pptA、X、C可根据基B分块

现求基B所对应的基可行解与目标值：左乘B-1令非基变量XN，XS＝0基解目标值编辑ppt基列常数列XXSXBB-1b？？cj-

zj-CBB-1b？？迭代后表基列常数列XXSXSbAIcj-

zj0C0对比初始表B-1AB-1C-CBB-1A-CBB-1B-1×第1行-CBB-1×第1行＋第2行编辑ppt三、其他形式的初始表与迭代后单纯形表基列常数列XBXNXSXSbBNIcj-

zj0CBCN0基列常数列XBXNXSXBB-1bIB-1NB-1cj-

zj-CBB-1b0CN-CBB-1N-CBB-1单纯形乘子编辑ppt初始表基列常数列x1...xj...xnXSXSbP1

...Pj...PnIcj-

0基列常数列x1...xj...xnXS

XBB-1bB-1P1

...B-1Pj

...B-1Pn

B-1

cj-

zj-CBB-1b

...cj-CBB-1Pj...迭代后单纯形表检验数σj编辑ppt例已知初始表和最优表如下，请将表中空白处数字填上。cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x41-1-22x101/21/2-1x20-1/21/2cj-zj.............................................................编辑ppt解：cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x41-1-22x101/21/2-1x20-1/21/2cj-zj.............................................................B-1B=（P4，P1，P2）编辑ppt解：cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x41-1-22x101/21/2-1x20-1/21/2cj-zj.............................................................B-1B-1b?10155编辑ppt解：cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x4101-1-22x11501/21/2-1x250-1/21/2cj-zj.............................................................B-1B-1P3?11/2-3/2010001编辑ppt解：cj2-11000CBXBbx1x2x3x4x5x60x4603111000x5101-120100x62011-1001cj-zj2-110000x4100011-1-22x115101/201/21/2-1x2501-3/20-1/21/2cj-zj00-3/20-3/2-1/2.............................................................编辑ppt四、最优表基列常数列XXSXBB-1bB-1AB-1cj-

zj-CBB-1bC-CBB-1A

-CBB-1若B是最优基，则下表是最优表根据最优性判定定理即：记Y=CBB-1YYY是对偶问题的可行解，目标值w=Yb=CBB-1b=maxz◆Y是一般型意义下对偶问题可行解，仅由决策变量取值组成（m维）编辑ppt结论：当采用单纯形法求得原问题的一个最优解的时候，检验行上同时得到对偶问题的一个可行解，且两者具有相同的目标值。利用对偶性质，可以证明这个对偶问题的解也为最优解。编辑ppt例、以求解下面LP问题以及它的对偶问题过程为例，验证前述结论对偶问题原问题编辑ppt

21000

01505100

0

24620100511001

21000表1：初始表B-1原问题编辑ppt

21000

01505100

2

412/601/600104/60-1/61

01/30-1/30表2：迭代中B-1原问题编辑ppt

21000

015/20015/4-15/2

2

7/21001/4-1/213/2010-1/43/2000-1/4-1/2表3：最优表B-1原问题编辑ppt基列常数列1/41/2-5/410-1/41/415/2011/2-3/2cj-zj-15/200-7/2-3/2

基列常数列15/27/23/20015/4-15/21001/4-1/2010-1/43/2cj-zj000-1/4-1/2对偶问题最优表原问题最优表对偶问题最优解Y=（y1,y2,y3）=(0,1/4,1/2)松弛变量决策变量剩余变量决策变量原问题最优解X=(x1,x2)T=(7/2,3/2)T编辑ppt两个问题作一比较:1.两者的最优值相同2.从任一个问题的最优表，可以直接找到另一个问题的最优解，对应关系原问题决策变量原问题松弛变量对偶问题剩余变量对偶问题决策变量编辑ppt例2、用单纯形表求解LP问题所得最优表如下，试直