运筹学教程课件一 绪 论.pptVIP

三、求初始基础可行解（背景模型，MAX, ≤) * 设线性规划问题为 另设bi?0 (i=1,2,…,m)。标准化后，若对xj和aij重新编号，则约束方程可化为 变量x1，x2，…，xm作为初始基变量，其余变量作为初始非基变量，并令xm+1=xm+1=…=xn+m=0，则得初始本可行解 四、最优检验 * 对于标准化线性规划问题(2)，经过若干次迭代后，如果对xj及aij重新编号，则约束方程可化为 其中，b’i和a’ij表示经过若干次迭代后，当前的右端系数和技术系数，以便区别于原始的右端系数bi和技术系数aij。将上式代入（2）的目标函数后可得 机会成本 * 在一般情况下，目标函数值OBJ计算公式和机会成本计算公式可写成 四、最优检验 其中，I为基变量的下标集。最优检验条件为 其中，J表示非基变量的下标集。对于基变量的检验数为 因为基变量的技术系数满足： aij=1, 当i=j aij=0, 当i?j 五、 求另一个更好的基础可行解 * 若某一基础可行解经过最优检验表明不是最优解，则需要设法求得另一个更好的基础可行解。求另一个更好的基础可行解的主要步骤如下： 1、确定换入变量； 2、确定换出变量； 3、通过基变换或初等变换求得另一个更好的基础可行解。 我们已在前面例子中说明了这种初等变换方法的基础思路。下一小节我们将用单纯形表进一步说明这种初等变换方法。 * 1.3.4 单纯形法表及单纯形法 * 例 试列出下面线性规划问题的初始单纯型表 单纯形法步骤 * 1、求初始基础可行解 将线性规划模型标准化，建立初始单纯形表，求初始基础可行解。 2、最优检验：对任一基础可行解X，若其所有检验数 ?j =cj? zj?0，j?J 则X为最优解，即X*=X，计算最优解所对应的最优目标函数值f(X*)，算法停止。否则转3。 3、求另一个更好的基础可行解 1）确定入变量xk 若 则xk为换入变量； 2）确定换出变量xl* 计算 若?l为空集，则为无界解，算法停止。否则与右端系数b’l 同一行的基变量xl*为换出变量。转3） 3）初等变换，得到另一个更好的基础可行解 将入变量xk所在列k，出变量xl*所在行l的主元技术系数a’l k变换为1，主元a’l k 所在列的其余元变换为0。更换基变量（用入变量xk替换出变量xl*）及其价值系数，得到另一个更好的基础可行解。转2。 * 表1.2.4 例1.2.2 单纯型表的迭代过程 答：最优解为 x1=20, x2=20, x3=0, OBJ=1700 * 单纯型表中元素的几点说明 任何时候，各基变量对应的列都构成一个单位矩阵 当前表中的 b 列表示当前基变量的解值，通过变换 B ?1 b 得到 (资源已变成产品) 当前非基变量对应的向量可通过变换 B ?1 AN 得到， 表示第 j 个变量对第 i 行对应的基变量的消耗率 非基变量的机会成本为 * 1.4 单纯形法的进一步讨论1.4.1 人工变量法 上一节我们涉及的线性规划模型都是线性规划的背景模型，即目标函数为最大，每个约束方程都是“?”型，右端系数都是大于等于0。对于这样一类的线性规划，每个约束方程引入一个松弛变量将其标准化后，约束方程的系数矩阵含有单位矩阵，以此单位矩阵作为初始可行基，很容易得到一个初试基础可行解。但是，对于下面的线性规划，将其标准化后，其约束方程的系数矩阵不存在单位矩阵。因此无法直观和方便地得到一个初始基础可行解 例1.4.1 解 令g(x)= -f(x)，第1和2个约束方程分别减去一个剩余变量x4和x5，则可将上述线性规划转化为如下标准形线性规划。 1.4.1 人工变量法 * 变量x6称为人工变量。这样，变量x3和x6系数矩阵可构成一个单位矩阵，即可构成一个初始可行基，以变量x3和x6为初始基变量，其它变量为非基变量0，则可得一初始基础可行解 X(0) = (0，0，4，0，0，6)T 这种在约束方程中加人工变量来得到初始基础可行解的方法称为人工变量法。 * 我们知道，对于任何一个基础可行解，非基变量都是等于0，所以，人工变量在初始基础可行解中虽然不等于0，但如果在后面迭代过程中，能把所有人工变量转变为非基变量，则所有人工变量都将等于0，这样，原有的约束方程就不会被破坏。但如果在迭代过程中，已得到最优解（即满足最优解检验条件），而基变量中还有人工变量，或最优解时所有人工变量不全部等于0，则原线性规划无解，即不存在满足所有约束方程的可行解。 将人工变量从初始基础可行解中转变为非基变量