运筹学单纯形法第2部分.pptVIP

等式约束左端引入人工变量的目的 使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的B(i)列（即约束方程的右边常数）值正好就是基变量的取值。 （注意：用非基变量表示基变量的表达式） 单纯形法小结 求解思想－－ 顶点的逐步转移， 条件是 使目标函数值不断得到改善。 表格单纯形法求解步骤 计算机求解时的注意点 1、输入数据中的分数，需先化为小数再执行输入过程。 2、每一张迭代表格中由基变量列（Basic）和B(i)列（解答列）可以读出现行解及相应的目标函数值，同时显示进基变量和出基变量，从而很容易识别主元列、主元行和主元素。 3、最终表显示最优解、最优目标函数值及总的迭代次数。如遇该线性规划无可行解或无“有限最优解”，则屏幕将显示有关信息： NO feasible solution . 或 * * unbounded solution !!! * * 四、单纯形法的一般描述： ? 1、 初始可行解的确定 (1)初始可行基的确定 ? 观察法——观察系数矩阵中是否含有现成的单位阵？ ? LP限制条件中全部是“≤”类型的约束—— 将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵； 先将约束条件标准化，再引入非负的人工变量， 以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”； 然后用大M法或两阶段法求解； ? 线性规划限制条件都是“≥”或“=”类型的约束—— ①如果限制条件中既有“≤”类型的约束，又有“≥”或“=”类型的约束，怎麽办？ 构造“不完全的人造基”！ 讨 论 ②为什麽初始可行基一定要选单位阵？ b列正好就是基变量的取值，检验数行 和b列交叉处元素也正好对应目标函数值， 因此称b列为解答列 （2）写出初始基本可行解—— 根据“用非基变量表示基变量的表达式”，非基变量取0，算出基变量，搭配在一起构成初始基本可行解。 2、建立判别准则： （1）两个基本表达式的一般形式 就LP限制条件中全部是“≤”类型约束，新增的松弛变量作为初始基变量的情况来描述： 此时LP的标准型为 初始可行基 ： 初始基本可行解： 一般（经过若干次迭代），对于基B， 用非基变量表出基变量的表达式 为： 用非基变量表示目标函数的表达式： 若 是对应于基B的基本可行解， 是非基变量 的检验数，若对于一切非基变量的角指标j，均有 ≤0，则X(0)为最优解。 （2）最优性判别定理 （3）无“有限最优解”的判别定理 若 为一基本可行解，有一非基变量xk,其检验数 , 而对于i=1,2,…，m，均有 ，则该线性规划问题没有“有限最优解”。 证明思路——构造性证明： 依据用非基变量表示基变量的表达式构造一族可行解，其对应的目标函数值趋于无穷大。 几何意义：沿着无界边界前进的一族可行解 举例：用非基变量表示基变量的表达式 代表两个约束条件： x2对应的系数列向量P2=（1，3）T， 当前的换入变量是 X2，按最小比值原则确定换出变量： 要求： 于是： 如果x2的系数列变成P2’=（-1，0）T,则用非基变量表示基变量的表达式就变成； 可行性自然满足,最小比值原则失效,意即x2的值可以任意增大→原线性规划无“有限最优解”。 3、进行基变换 （1）选择进基变量——原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善（较快增大）； 进基变量对应的系数列称为主元列。 （2）出基变量的确定——按最小比值原则确定出基变量，为的是保持解的可行性； 出基变量所在的行称为主元行。 主元行和主元列的交叉元素称为主元素。 思考题 这样进行基变换后得到的新解对应的系数列向量是否线性独立？ 4、主元变换（旋转运算或枢运算） 按照主元素进行矩阵的初等行变换——把主元素变成1，主元列的其他元素变成0（即主元列变为单位向量） 写出新的基本可行解，返回最优性检验。 第一步：将LP化为标准型