运筹学第一章1.4大M法和两阶段法.pptVIP

要求：1于是：2如果x2的系数列变成P2’=（-1，0）T,则用非基变量表示基变量的表达式就变成；3可行性自然满足,最小比值原则失效,意即x2的值可以任意增大→原线性规划无“有限最优解”。4进行基变换选择进基变量——原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善（较快增大）；进基变量对应的系数列称为主元列。出基变量的确定——按最小比值原则确定出基变量，为的是保持解的可行性；出基变量所在的行称为主元行。主元行和主元列的交叉元素称为主元素。主元变换（旋转运算或枢运算）按照主元素进行矩阵的初等行变换——把主元素变成1，主元列的其他元素变成0（即主元列变为单位向量）写出新的基本可行解，返回最优性检验。例1.8的表格单纯形法计算过程：表格单纯形法求解步骤确定初始可行基，写出初始基本可行解（这一步计算机可自动完成）系数阵中有一个单位阵。量，使约束条件化为等式，并且约束方程组的引入适当的松驰变量、剩余变量和人工变将LP化为标准型，并加以整理。EDCBAF最优性检验01计算检验数，检查：?所有检验数是否≤0？是——结束，写出最优解和目标函数最优值；?还有正检验数——检查相应系数列≤0？是——结束，该LP无“有限最优解”！?不属于上述两种情况，转入下一步—基变换。确定是停止迭代还是转入基变换？02选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量为换入变量；最小比值对应的行为主元行，主元行对应的基变量为换出变量。确定进基变量和出基变量。第三步：基变换利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。第四步换基迭代（旋转运算、枢运算)完成一次迭代，得到新的基本可行解和相应的目标函数值该迭代过程直至下列情况之一发生时停止?检验数行全部变为非正值；（得到最优解）或最优性判别定理；无“有限最优解”判断定理依据：最优性检验的两个定理?主元列≤0（最优解无界）010203040506停止迭代的标志（停机准则）各种类型线性规划的处理分类及处理原则：类型一：目标要求是“Max”，约束条件是“≤”类型——左边加上非负松弛变量变成等式约束（约束条件标准化），将引入的松弛变量作为初始基变量，则初始可行基是一个单位阵，用原始单纯形法求解。类型二：目标要求是“Max”，约束条件是“=”类型——左边引入非负的人工变量，并将引入的人工变量作为初始基变量，则初始可行基是一个单位阵，然后用大M法或两阶段法求解。类型三：目标要求是“Max”，约束条件是“≥”类型——约束条件标准化，左边减去非负的剩余变量，变成等式约束，化为类型二。处理人工变量的方法：大M法——在约束条件中人为地加入非负的人工变量，以便使它们对应的系数列向量构成单位阵。问题：加入的人工变量是否合理？如何处理？在目标函数中，给人工变量前面添上一个绝对值很大的负系数-M（M0），迭代过程中，只要基变量中还存在人工变量，目标函数就不可能实现极大化——惩罚！观察法—系数矩阵中是否含有现成的单位阵？将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；始可行解的确定LP限制条件中全部是“≤”类型的约束初始可行基的确定单纯形法的一般描述：先将约束条件标准化，再引入非负的人工变量，以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”；然后用大M法或两阶段法求解；线性规划限制条件都是“≥”或“=”类型的约束——等式约束左端引入人工变量的目的使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的B(i)列（即约束方程的右边常数）值正好就是基变量的取值。01(注意:用非基变量表示基变量的表达式)02①如果限制条件中既有“≤”类型的约束，又有“≥”或“=”类型的约束，怎麽办？构造“不完全的人造基”！讨论②为什麽初始可行基一定要选单位阵？b列正好就是基变量的取值，检验数行和b列交叉处元素也正好对应目标函数值，因此称b列为解答列logo（2）写出初始基本可行解——根据“用非基变量表示基变量的表达式”，非基变量取0，算出基变量，搭配在一起构成初始基本可行解。2、建立判别准则：（1）两个基本表达式的一般形式LP限制条件中全部是“≤”类型约束，新增的松弛变量作为初始基变量的情况来描述：此时LP的标准型为非基变量 基变量初始可行基：初