单纯形解法与对偶解法.doc

2x1+2x21600x1400Z=400Z=1800Z=1200Z=26002004006008001000x15x1+2.5x225002004006008001000x2OABCDEFGH线性规划的单纯形解法例：一、建立初始基本可行解标准化：其中，x3,x4,x5为松驰变量。增广矩阵表示：初始可行基：基变量可用非基变量表示成：令非基变量x1=x2=0，得初始可行解：X=0,0,1600,2500,400，对应于可行域的O点。相应的Z值为0二、解的最优性检验规划判断的方法是检查目标函数中是否还有正的系数。Z=4x1+3x2+0因此，如果将这两个非基变量中的任意一个变成基变量，也就是使该变量的取值由零变为正值，都有可能使目标函数值增加，因此原来的解不是最优解。三、第一次迭代（基变换）1.确定换入变量一般选取价值系数大的那个为入基变量。这里选择x1为入基变量。2.确定换出变量确定入基变量，同时要确定换出变量，其原则是使得到的新的基本解同时是可行解。分析如下：令x2=0（x2仍为非基变量），得：随着x1的增加，x3, x4, x5的值就会逐渐变小，但始终应保持非负。因此，x1的增加是有限的。容易看出，该限制可以表示为：这就是说，当x1的值由零增加到400时，原来基变量x5的值最先变成0，而另外两个基变量仍然保持正值，因此，只要用x1代替x5成为基变量，而且x1的值不大于400，就能保证原来的基变量和的值都非负。于得，新的基变量为x3,x4,x1，非基变量为x5,x2。q1600/2=8002500/5=500400/1=400用矩阵表示如下：分子是b列，分母是换入变量（x1）所在列。3、求解对增广矩阵进行初等变换，得：令非基变量x2=x5=0，得到一组新基本解：X=400,0,800,500, 0，该点对应于D点，相应的Z16004、最优性检验Z=4x1+3x2=4(400-x5)+3x2=1600+3x2-4x5由于x2的系数大于零，所以其为非最优解。三、第二次迭代1.确定换入变量：x22.确定换出变量：由于x5=0，从而因此，换出变量为x4新的基变量为x3, x2, x1，非基变量为x4, x5。矩阵表示如下：q800/2=400500/2.5=2003、求解对增广矩阵进行初等变换，得：令非基变量x4=x5=0，得到一组新基本解：X=400,200,400,0, 0，该点对应于C点，相应的Z22004、最优性检验Z=4x1+3x2=4(400-x5)+3(200-0.4x4+2x5)=2200-1.2x4+2x5由于x5的系数大于零，所以其为非最优解。四、第三次迭代1.确定换入变量：x52.确定换出变量：由于x4=0，从而因此，换出变量为x3q400/2=200400/1=400新的基变量为x5,x2,x1，非基变量为x3,x4。矩阵表示如下：3、求解对增广矩阵进行初等变换，得：令非基变量x3=x4=0，得到一组新基本解：X=200,600,0,0, 200，该点对应于B点，相应的Z26004、最优性检验Z=4x1+3x2=4(200+0.5x3-0.4x4)+3(600-x3+0.4x4)=2600-x3-0.4x4由于x3、x4的系数均小于零，所以该解即为最优解。单纯形表对于一个基B，分块矩阵称为对应于基B的单纯形表。T（B）记录了基B的若干重要信息：（1）左下角这一块为11矩阵，即一个数，它是x取B的基础解时目标函数S的值；（2）左上角这一块是m1矩阵，这是x取B的基础解时基变量的值；（3）右下解这一块是1n矩阵。由于：因此，CBTB-1A-CT 0等价于CBTB-1R-CRT 0因此，若右下角的矩阵所有元素都大于0，则B是最优基。（4）右上角这一块是mn矩阵，其第j列为B-1Pj：因此，对于任意一个基B，只要算出它的单纯形表T(B)，即可判定它的最优性，同时还知道基本解及目标函数的值。单纯形表解法C43000qCBxBbx1x2x3x4x50x31600221001600/2=8000x4250052.50102500/5=5000x540010001400/1=400zjzj-cj(=j)000000-4-30000x38000210-2800/2=4000x450002.501-5500/2.5=2004x140010001zjzj-cj1600400040-30040x3400001-0.82400/2=2003x22000100.4-24x140010001400/1=400zjzj-cj22004301.2-20001.2-20x5200000.5-0.413x2600011-0.404x120010-0.50.40zjzj-cj26004310.400010.40对偶单纯形法：C-1600-2500-40000CBxBby1y2y3y4y50y4-4-2-5-1100y5-3-2-2.5001zjzj-cj(=j)0000001600250040000|1600/(-2)|=800|2500/(-5)|=500|400/(-1)|=400-400y34251-100y5-3-2-2.5001zjzj-cj-1600-800-2000-400400080050004000|800/(-2)|=400|500/(-2.5)|=200-400y3-2-201-12-2500y21.20.8100-0.4zjzj-cj-2200-1200-2500-40040020040000400200|400/(-2)|=200|400/(-1)|=400-1600y1110-0.50.5-1-2500y20.4010.4-0.40.4zjzj-cj-2600-1600-2500-20020060000200200600问题：有关对偶问题原问题转化成对偶问题比较容易解决时，如果存在最优解虽然可以知道解和检验数的值，只知道他们之间解和检验数总体对应关系，那么对偶问题最优解检验数与原问题解究竟如何一一对应情况？简单地说，原问题的决策变量对应于对偶问题的松驰变量，原问题的松驰变量，对应于对偶的决策变量。但在对应时一定要按顺序。例如，对于生产汽车的例子，原问题的决策变量为x1,x2，松驰变量为x3,x4,x5，对偶问题的决策变量为y1,y2,y3，松驰变量为y4,y5 。对应时应该如下：原问题的基变量：x5, x2, x1对偶问题的基变量：y1, y2原问题的最优解及检验数（P26）x1x2x3x4x5最优解20060000200检验数0010.40对偶问题的最优解及检验数（P41）y1y2y3y4y5最优解10.4000检验数00200200600可以看到，对偶问题最优解的检验数分别