第二章 图解法与单纯形法改

1、第二章线性修正图的解法和简单形解法，1线性修正图问题的解法线性修正图的基本性质线性修正图简单形法的原理和修正阶梯线性修正图简单形法的进一步讨论线性修正图特例输送问题，2.1线性修正图问题的解法，解法作为图的方法解线性修正图问题，一般只能适用于具有两个决定变量的线性修正图问题。 根据描绘步骤1正交坐标系的步骤2制约条件描绘可执行区域的步骤3描绘坐标原点的目标函数线步骤4决定目标函数的增大方向的步骤5使目标函数向增大方向平行移动，与可执行区域交叉，具有最大目标函数值的顶点是线性修正图像问题的最佳解。 求解z=15、2.1线性校正像素问题的解法在本例中是我们用解法得到的问题的最佳解，其中z=15、2

2、.1线性校正像素问题的解法是我们用解法得到的问题的最佳解。 然而，在线性校正像素问题的校正计算中，解的情形可能出现下面的： 1无限最佳解。 当将本例的目标函数变更为时，目标函数的图表正好与(1)平行。 因此，该线性校正像素问题具有无限多个最佳解，也被称为具有多个最佳解。 2.1线性修正画问题的解法，2 .无界解(有可行解但没有有界最佳解)。 在本例中，如果制约条件只剩下(2)和(4)，则不考虑其他的条件(1)、(3)。 用图解法解，可知变量的可取值无限大，目标函数的值也无限大。 在这种情况下，问题没有边界解或没有最佳解。 这是因为在制作实际问题的数学模型时缺少了一些必要的资源限制。 2.1线性

3、修正计划问题的解法，3 .没有可行解。 用图解法解的话，找不到满足所有制约条件的共同范围，这种情况下问题是不能解的线性修正图模型。 这是因为模型本身有错误，制约之间有矛盾，应该检查修改。 虽然图解仅可用于解决仅具有两个变量的线性校正像素问题，但是该解题构思和几何直观获得的概念确定在解决一般线性校正像素问题的简单形法(下文描述)中具有较大启发：线性校正像素的基本性质以及凸集对c中的任意两个点都是集合c中的点由于下一个链路可以表示为，所以凸集的数学表示对于任何一个凸集都可以将c称为凸集。 如果在、线性修正像素的基本性质、定理1线性修正像素问题中存在可执行区域，则该可执行区域一定是凸集。 将引起线性

4、校正像素问题的可执行解X=(x1，x2，xn)T设为基本可执行解的充分条件是对应于x的正分量的系数列向量是线性独立的。 定理2线性修正画问题的基本可执行解对应于可执行领域的顶点。 定理3如果线性修正画问题有最佳解，那么必定存在一个基本可执行解是最佳解。 从可执行区域中的一个基本可执行解判定该解是否已经是最佳解，否则，寻找下一个基本可执行解并同时努力改善目标函数，直到找到最佳解或确定该问题不可解为止。基本思想：2.2线性修正图像单纯形法的原理和修正计算步骤、【例2】使用单纯形法求出以下的线性修正图像的最佳解，单纯形法的修正计算步骤：步骤1 :求出初始基础可执行解，列举初始单纯形表。 对非标准形式

5、的线性修订计划问题首先定为标准形式。 由于可设法在约束方程式的系数矩阵中包含一个单位矩阵P1、P2、Pm，因此能够据此求出问题的一个初始基本可执行解。必须是标准形式，【解】首先成为标准形式，加上缓和变量x3、x4，标准形式存在系数矩阵a及可执行基B1，r(B1)=2，B1以单位矩阵为初始基，x3、x4为基变量，x1、x1，如果存在，则在问题上无界解。 计算完毕。 否则，进入下一步。 步骤31将基本可执行解转换为大于相邻目标函数的基本可执行解，并且列出新的简单形式表。 步骤4重复步骤2和3直到修正计算结束。基列、基行、bi /ai2、ai20、I、表1-4、基变量、1、10、0、0、1/3、0、

6、1/3通过查找或构建m阶单位矩阵作为初始可执行基础来创建初始简单形式表。 对各非基底变量xj的校验数j进行修正，如果是所有的j0，则问题得到最佳解而停止修正运算，否则前进到下一步骤。 如果从大于0的检测的常数中的对应于某k的系数列向量Pk0，则该问题是无界解，并且如果不停止校正计算，则前进到下一步骤。 根据maxjj0=k的原则，确定xk是调换变量(调换基础变量)，按照规则进行修正：=minbi/aik| aik0=bl/aik确定调换变量。 创建一个新的简单表，其中基本变量xk替换xl的位置。 以aik为主要要素进行反复，设与xk对应的列向量为单位列向量，即aik为1、同列的其他要素为0，进

7、入步骤。 2.2线性修正图简单形法的原理和修正算法步骤、简单形法的修正算法中，可能出现以下2种情况：出现2种以上，原则上可以取任何对应的替换基的变量的相互对立。 换句话说，相同最小值出现两个或更多个。 可选择基变量的任意一个作为替换变量。 然而，为了防止循环现象，提出了几种方法。 /布兰特法词典序法扰动法。 (1个检查数中下标最小的非基底变量作为替换变量(用2个规则修正时，出现2个以上的最小比例时，下标最小的基底变量作为替换变量)。简单形法的修正运算、单纯形法解线性修正图像问题：例3、最佳解的判别定理、定理1最佳解的判别定理、定理2无限多最佳解的判别定理、单纯形法的修正运算、单纯形法解线性修正

8、图像问题：例4、最佳解的判别定理多重最佳解的判断：最佳表中存在非基本变量的校验数为零无界解的判断：或AIJ (I=1，2，m )在线性修正像素中有无界解，【练习1】用单纯形法求解，表15，1/3，1，51/9，2/3，35/3，0，98/9，1/9，7/3，最佳解x=(表15，1/3，1，51/9，2/3，35/3，0，98/9，1/9，7/3 【练习3】解除线性修正图像，【解】:为标准，用单纯形法如下表那样修正时，表(3)的j不全部为正的话，最佳解为：表(3)的非基变量x3的检查数为3=0单纯形法修正算的矩阵记述、单纯形法修正算的矩阵记述、单纯形法修正算的矩阵记述、单纯形法修正算的矩阵记述、

9、单纯形法修正算的矩阵记述、人工变量法人工变量法的基本想法是，如果原来的线性修正画问题的系数矩阵中没有单位向量，则可以通过在各制约方程式上加上人工变量来在系数矩阵中形成单位向量。 2.3线性修正像素单纯形法的进一步研究、线性修正像素求解的人工变量法、线性修正像素求解的人工变量法，由于以单位阵列为基础阵列，所以将加入的人工变量作为基础变量。 并且，通过基底变换，使基底变量中不包含非零的人工变量。 如果最终的单纯形表中存在非零人工变量，这意味着没有可执行的解。大m法、二阶段法对人工变量赋予大的负价值系数m(m是任意大的正数)，以免加上人工变量后的线性修订问题的最佳目标函数值受到影响。 线性修正图求解

10、的大m法、线性修正图求解的大m法，由于人工变量对目标函数有较大的负面影响，因此单纯形法的优化机制会自动将人工变量排除在基外，找到原问题的可行基础。 这种方法一般称为大m法。 【例6】用大m法求解下一个线性修正图像，用线性修正图像求解的大m法的例子【解】首先将数学建模为标准形式，式中x4是剩馀的佗变量，x5是缓和变量，x5是一个基本变量，在第一、三限制上分别加上人工变量x6、x7、目标函数，得到最佳解x (31/3，3 ) 最佳值Z152/3，注意：m是一个大的抽象数，不需要给出具体的数值，可以理解为大于给定的任何确定值，【练习】、【线性修正像求解的二阶段法、线性修正像求解的二阶段法、第二阶段、

11、单纯形法求解原问题第一阶段修正算得到的最终单纯形表？ 用两阶段简单形法求解例【6】的线性修正图像。 【解】标准类型是在第一、三约束方程式上加上人工变量x6、x7后，第一阶段问题用简单形法解，得到第一阶段问题的修正算表如下，最佳解是最佳值w=0。 第一阶段的最后的最佳表找出原问题的一组基本可执行解，把它作为初始基本可执行解，求出原问题的最佳解，即第二阶段的问题，用简单形法修正，得到下表，得到最佳解x (31/3，13，19/3，0，0 ) t最佳值Z152/3 【解】第一阶段的问题，用简单形法如下表那样进行修正：j0，得到第一阶段的最佳解x=(2，0，0，0，2 ) t，因为最佳目标值w=20，

12、x5还在基变量中，原来的问题，解的判断，唯一最佳解的判断：最佳表中的所有非基线性校正像素具有唯一的最佳解，如果在多重最佳解的判定：最佳表中不存在零个非基变量的校验，则线性校正像素具有多重最佳解。 无界解的判断：某k0且aik (I=1，2，m )表明线性修正图像有无界解，没有可执行解的判断： (1)如果用大m单纯形法修正后最终单纯形表中存在非零的人工变量，则原来的线性修正图像问题没有可执行解。 (2)在第一阶段的最佳值w0的情况下，原来的问题不能解决。 【练习题1】原料问题。 某钢铁公司要求的成分标准是锡在28%以上，锌在15%以下，铅正好在10%，镍在35U%之间，其他成分是不允许的。 钢铁公司计划从5种不同等级的矿石进行冶炼，各矿物的成分含量和价格如表1.4所示。 矿石杂质在冶炼过程中被废弃，现在要求的是每吨合金成本最低的矿物数量。 假定矿石在冶炼过程中合金含量没有变化。表1.4矿石的金属含量，练习问题，解：以XJ (j=1，2，2，5 )为第j种矿石数量，得到以下线性修正模型，注意矿石在实际冶炼时金属含量的变化，建模时应该考虑这种变化，可能存在非线性关系的原料问题是