改进单纯形法

单纯形法的矩阵描述设线性规划问题：给这个线性规划问题的约束条件加入松弛变量6.2.6改进单纯形法得到标准型设B是一个可行基，若将系数矩阵（A，I）分为（B，N），N是非基变量的系数矩阵。对应于B的变量是基变量，用向量表示。其他为非基变量。将C分为于是，约束方程组用矩阵表示为：目标函数为：这时可将线性规划标准型改写为矩阵形式：将约束方程移项，得：左乘后，得到的表达式代入目标函数，得到：令非基变量得到一个基可行解目标函数值：1、非基变量的系数就是检验数令称为单纯形乘子2、用矩阵描述时，规则的表达式是：3、单纯形表当确定为基变量时，经过基变换，可得到：用矩阵表示为：

单纯形法的迭代过程实质上是从一组基到另一组基的变换，每当基变量确定后，只要把这个基在初始单纯形表中相应列的系数矩阵的逆矩阵求出来，则单纯形表上的其它列的数字也随着确定。而为了确定一组新的基，关键是要找出换入变量和换出变量。找换入变量是通过求所有非基变量列的检验数，从中找出最大的正检验数来确定。在找出换入变量后，根据

规则确定换出变量。而每次迭代中真正有用的数字是基变量列数字,基变量的逆矩阵，非基变量的检验数以及最大正检验数对应的非基变量的系数列向量。计算表Ⅰ非基变量基变量icBxBbx1x2x3x4x5x60x31222100012/20x481201008/20x516400010－0x61204*000112/4z

230000

计算表Ⅱ非基变量基变量ibx1x6x3x4x5x20x362-1/210006/20x421-1/201002/10x51600001016/43x2341/40001－j2-3/40000

计算表Ⅲ非基变量基变量ibx4x6x3x1x5x20x32-21/210002/0.52x121-1/20100－0x53-4200108/23x2301/400013/0.25j-21/40000

计算表VI非基变量基变量

bx4x5x3x1x6x20x30-1-1/41000

2x1401/40100

0x64-21/20010

3x221/2-1/30001

j-1.5-1/80000

改进单纯形法求解线性规划的计算步骤然后计算单纯形乘子

第二步：计算非基变量xN的检验数j，j=m+1,…,n。若j≤0，已得到最优解，可停止计算。若还存在j＞0，转下步。第一步：根据给出的线性规划问题，在加入松弛变量或人工变量后得到初始基变量。求初始基矩阵B的逆矩阵B-1。于是可以求出初始解。第三步：根据所对应的非基变量，确定为换入变量。计算B-1PK，若B-1PK≤0，那么问题无解，停止计算。否则转入下一步。第四步：根据

规则，求出和它对应的基变量xl，确定xl为换出变量。于是可给出一组新的基变量以及新的基矩阵B1。第五步：计算新的基矩阵的逆矩阵,求出及。重复第二步到第五步。6.3灵敏度分析一、系数变化范围的确定的最优解。要求保持已求得最优解不变的条件下，确定aij,bi,cj这些系数变化的范围。1．目标函数中cj的变化范围的确定。设cj是变量xj在目标函数中的系数。若在其它参数不变的情况下，cj变化了cj。可以分别就cj是非基变量和基变量的系数这两种情况来讨论。设已求得了线性规划问题（1）若cj是非基变量xj的系数。这时它在计算表中所对应的检验数是当cj变化cj后，要保证在最终计算表中这个检验数仍然小于或等于零；即其中，单纯形乘子（2）若系数cr是基变量xr在目标函数中的系数。当cr变化cr，那么在最终计算表中对应基变量xr的检验数是

当cr没有变化，这时在最终计算表中xr的检验数

因为cr是属于cB中的一个数。所以当cr变化了cr时，就引起cB发生变化，这时是基变量xr在最终计算表中所在行的各系数值。（j=1,2,…,n），cr可以变化的范围是若要求原最优解不变，即必须满足，于是可以得到当当2．在约束条件中bi的变化范围的确定。若第r个约束条件的br变化了br，并假设规划问题的其它