《[经管营销]1-3 单纯形法第2部分》由会员分享，可在线阅读，更多相关《[经管营销]1-3 单纯形法第2部分（52页珍藏版）》请在金锄头文库上搜索。
1、运筹学实践的具体安排,四、单纯形法的一般描述： 1、 初始可行解的确定 (1)初始可行基的确定 观察法观察系数矩阵中是否含有现成的单位阵？ LP限制条件中全部是“”类型的约束 将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；,先将约束条件标准化，再引入非负的人工变量， 以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”； 然后用大M法或两阶段法求解；, 线性规划限制条件都是“”或“=”类型的约束,等式约束左端引入人工变量的目的,使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的B(i)列（即约束方
2、程的右边常数）值正好就是基变量的取值。 （注意：用非基变量表示基变量的表达式）,如果限制条件中既有“”类型的约束，又有“”或“=”类型的约束，怎么办？ 构造“不完全的人造基”！,讨 论,为什么初始可行基一定要选单位阵？ b列正好就是基变量的取值，检验数行 和b列交叉处元素也正好对应目标函数值， 因此称b列为解答列,（2）写出初始基本可行解 根据“用非基变量表示基变量的表达式”，非基变量取0，算出基变量，搭配在一起构成初始基本可行解。,2、建立判别准则： （1）两个基本表达式的一般形式 就LP限制条件中全部是“”类型约束，新增的松弛变量作为初始基变量的情况来描述：,此时LP的标准型为,初始可行基
3、 ：,初始基本可行解：,一般（经过若干次迭代），对于基B， 用非基变量表示基变量的表达式 为：,用非基变量表示目标函数的表达式：,若干次迭代 列互换 p28 重新编号,若 是对应于基B的基本可行解， 是非基变量 的检验数，若对于一切非基变量的角标j，均有 0，则X(0)为最优解。,（2）最优性判别定理,（3）无“有限最优解”的判别定理,若 为一基本可行解，有一非基变量xk,其检验数 , 而对于i=1,2,，m，均有 ，则该线性规划问题没有“有限最优解”。,证明思路（ p29 ）构造性证明： 依据用非基变量表示基变量的表达式构造一组可行解，其对应的目标函数值趋于无穷大。 几何意义：沿着无界边界前
4、进的一组可行解,举例：用非基变量表示基变量的表达式,代表两个约束条件：,x2对应的系数列向量P2=（1，3）T， 当前的换入变量是 X2，按最小比值原则确定换出变量：,要求：,于是：,如果x2的系数列变成P2=（-1，0）T,则用非基变量表示基变量的表达式就变成；,可行性自然满足,最小比值原则失效,意即x2的值可以任意增大原线性规划无“有限最优解”。,3、进行基变换 （1）选择进基变量原则：正检验数（或最大正检验数）所对应的变量进基，目的是使目标函数得到改善（较快增大）； 进基变量对应的系数列称为主元列。 （2）出基变量的确定按最小比值原则确定出基变量，为的是保持解的可行性； 出基变量所在的行
5、称为主元行。 主元行和主元列的交叉元素称为主元素。,思考题,这样进行基变换后得到的新解对应的系数列向量是否线性独立？,4、主元变换（旋转运算或枢运算） 按照主元素进行矩阵的初等行变换把主元素变成1，主元列的其他元素变成0（即主元列变为单位向量） 写出新的基本可行解，返回最优性检验。,单纯形法小结,求解思想 顶点的逐步转移， 条件是 使目标函数值不断得到改善。,表格单纯形法求解步骤,第一步：将LP化为标准型，并加以整理。 引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。 （这一步计算机可自动完成） 确定初始可行基，写出初始基本可行解,第二步：最优
6、性检验,计算检验数，检查： 所有检验数是否 0？ 是结束，写出最优解和目标函数最优值； 还有正检验数检查相应系数列 0？ 是结束，该LP无“有限最优解”！ 不属于上述两种情况，转入下一步基变换。 确定是停止迭代还是转入基变换？,选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量为换入变量； 最小比值对应的行为主元行，主元行对应的基变量为换出变量。,第三步：基变换,确定进基变量和出基变量。,利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。,第四步 换基迭代（旋转运算、枢运算),完成一次迭代，得到新的基本可行解和
7、相应的目标函数值,该迭代过程直至下列情况之一发生时停止 检验数行全部变为非正值； （得到最优解）或 主元列 0 （最优解无界）,停止迭代的标志（停机准则）,依据：最优性检验的两个定理 最优性判别定理；无“有限最优解”判断定理,计算机求解时的注意点,1. 输入数据中的分数,需先化为小数再执行输入过程。 2.每一张迭代表格中由基变量列（Basic）和B(i)列（解答列）可以读出现行解及相应的目标函数值，同时显示进基变量和出基变量，从而很容易识别主元列、主元行和主元素。 3.最终表显示最优解、最优目标函数值及总的迭代次数。如遇该线性规划无可行解或无“有限最优解”，则屏幕将显示有关信息： NO fea
8、sible solution . 或 * * unbounded solution !,五、各种类型线性规划的处理 1、分类及处理原则： （1）类型一：目标要求是“Max”，约束条件是“”类型左边加上非负松弛变量变成等式约束（约束条件标准化），将引入的松弛变量作为初始基变量，则初始可行基是一个单位阵，用原始单纯形法求解。,（2）类型二：目标要求是“Max”，约束条件是“=”类型左边引入非负的人工变量，并将引入的人工变量作为初始基变量，则初始可行基是一个单位阵，然后用大M法或两阶段法求解。 （3）类型三：目标要求是“Max”，约束条件是“”类型约束条件标准化，左边减去非负的剩余变量，变成等式约束
9、，化为类型二。,（4）类型四：目标要求是“Min” 方法1化为极大化问题 方法2按照极小化问题直接在单纯形表格上计算处理，但 相应的原则要作改动。,2、处理人工变量的方法： （1）大M法在约束条件中人为地加入非负的人工变量，以便使它们对应的系数列向量构成单位阵。 问题：加入的人工变量是否合理？如何处理？ 在目标函数中，给人工变量前面添上一个绝对值很大的负系数-M（M0），迭代过程中，只要基变量中还存在人工变量，目标函数就不可能实现极大化惩罚！,大M法：,（1）大M法也叫惩罚法，在原来的约束矩阵中添加人工变量后，在其目标函数中给人工变量一个系数M（绝对值任意大的负数），形成新的LP问题。, 最优
10、表中，基变量不包含人工变量，则最优解就是原线性规划的最优解，不影响目标函数的取值； 最优表中，基变量中仍含有人工变量，表明原线性规划的约束条件被破坏，线性规划没有可行解，也就没有最优解！,结 果,问题,结果中求得的最优解是哪个线性规划的最优解？为什么？,大M法举例,例114 求解下面的线性规划问题。,第一步：标准化,标准化,由于系数矩阵中没有单位矩阵，但有一个单位向量。可以将两个约束条件对换一下，并在第一个约束中增加一个人工变量，化为下面的问题 ：,第二步：添加人工变量,用表格单纯形法求解该问题，其过程如下：,（2） 两阶段法 第一阶段：建立辅助线性规划并求解，以判断原线性规划是否存在基本可行
11、解。 辅助线性规划的结构：目标函数W为所有人工变量之和，目标要求是使目标函数极小化，约束条件与原线性规划相同。,原问题,辅助线性规划,求解结果 W最优值=0即所有人工变量取值全为0（为什么？），均为非基变量，最优解是原线性规划的一个基本可行解，转入第二阶段； W最优值=0但人工变量中有等于0的基变量，构成退化的基本可行解，可以转化为情况；如何转化？ 选一个不是人工变量的非基变量进基， 把在基中的人工变量替换出来,W最优值0至少有一个人工变量取值0,说明基变量中至少有1个人工变量,表明原问题没有可行解,讨论结束。,问题讨论,如果辅助线性规划的结构是：目标函数W为所有人工变量之和的相反数，目标要求
12、是使目标函数极大化，约束条件与原线性规划相同。这与上述的讨论是否矛盾？,试比较：,（1）,（2）,（1）式目标要求改为极大化（或（2）式目标要求改为极小化）行不行？,第二阶段： 将第一阶段的最优解作为初始可行解，目标函数换成原问题的目标函数，进行单纯形迭代，求出最优解。 问题讨论： 如何实施？需要重新建立初始单纯形表吗？,实施中，在第一阶段最优表格中划去人工变量列，将表头部分和CB列的价值系数换成原问题的价值系数(把目标函数换成原线性规划的目标函数)，继续迭代，直至求出最优解。, 在大M法中，当人工变量出基后能否立即划去该人工变量所在的系数列？,两阶段法举例,例:求解线性规划问题,解：对标准化
13、后的问题，增加人工变量，并构造第一阶段的目标：,约束系数矩阵,第二阶段：划去人工变量所在的列，得到原问题的初始基本可行解和约束条件的等价变形。现在回到原问题：,原问题,原问题的标准型,解出用非基变量表示基变量和目标函数的表达式：,最优解： 原问题最优值：,3、用表格单纯形法直接计算极小化线性规划时要修改哪些原则？ （初始表？最优解判别？换入变量？换出变量？旋转运算？引入人工变量？） 最优性判别：所有检验数非负 换入变量的选择原则：（最小）负检验数所对应的变量进基，以保证目标函数值（较快）减小； 用大M法求解时，在目标函数中人工变量的前面添上一个很大的正系数M；,六、迭代过程中可能出现的问题及处
14、理方法,1、为确定出基变量要计算比值，该比值=解答列元素/主元列元素。对于主元列的0元素或负元素是否也要计算比值？ （此时解的可行性自然满足，不必计算；如果主元列元素全部为0元素或负元素，则最小比值失效，线性规划无“有限最优解”）,2、出现若干个相同的最小比值怎么办？ （说明出现了退化的基本可行解，即非0分量的个数小于约束方程的个数。按照“摄动原理”所得的规则，从相同比值对应的基变量中选下标最大的基变量作为换出变量可以避免出现“死循环”现象） 3、选择进基变量时，同时有若干个正检验数，怎么选？,（最大正检验数或从左至右第1个出现的正检验数所对应的非基变量进基） 课堂练习1-5：直接按极小化问题求解下面的LP：,第三次作业 P49 ：10(2),(3)小题 下周 4交,由最优表得： 最优解为X*=（0，1，0，3，0）T, 相应的目标函数最优值为Zmin=2,若有时间,P44-45 选择题和判断题,
