实用经济数学教学课件作者盛光进电子教案7线性规划及其应用课件.ppt

7.2 线性规划问题解的性质 【例4】 求解线性规划问题 解 在平面直角坐标系 中，画出半面 ，它在第一象限的部分表示为区域1；画出半平面 ，它在第一象限的部分表示为区域2。容易看出区域1与区域2没有公共部分，即该问题的可行域为空集，所以此问题没有可行解，当然也就没有最优解。 7.2 线性规划问题解的性质 二、线性规划问题解的性质 若线性规划问题的可行域不是空集，则可行域没有凹入部分，没有空洞，即任意两点连线上的点仍在可行域中，这样的点集称为凸集。 含两个变量的线性规划问题的解有下面四种情况： （1）有可行解且有惟一最优解，如例1； （2）有可行解且有无穷多最优解，如例2； （3）有可行解但无最优解，如例3； （4）无可行解，如例4。 7.2 线性规划问题解的性质 性质4 若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解）一定可以在基可行解(顶点)中找到． 线性规划问题解的性质如下： 性质1 求解线性规划问题时，解的情况有：惟一最优解、无穷多最优解、无界解、无可行解． 性质2 　若线性规划问题的可行域存在，则可行域是一个凸集． 性质3 　线性规划问题的基可行解 对应于可行域的顶点． 7.3 单纯形法 介绍初始基可行解的求法，最优性判定以及如何找到下一个基可行解。 【例1】用单纯形法求解7.1节例1对应的线性规划问题。 解 该问题的标准型为 一、典型线性规划的单纯形法 如果线性规划的标准型的系数矩阵中，含有一个单位子矩阵且约束条件右端常数均非负，则称此线性规划是典型线性规划。 则约束方程组（2）的系数矩阵 　　判断该基可行解是否为最优解？通过方程组（2）将基变量用非基变量表达为 取， 则 构成一个基，对应的基变量为 。令非基变量 ，可得一个基可行解 注1　由于中含有一个单位子矩阵 ，且右端常数非负，故可取该单位子矩阵作为初始基，得到一个初始基可行解。 7.3 单纯形法 代入目标函数（1），得 从目标函数（4）可以看出，非基变量 的系数都是正数，因此， 的值增大（目前取值为0）都可以使目标函数值增大。又因为目标函数中基变量的系数为零，虽然非基变量 增大会影响到基变量 的取值，但在满足约束条件时， 的改变不会造成目标函数值改变，所以，目标函数中该非基变量 的系数的符号就成了判断当前基可行解是否是最优解的准则。 注2　称消去基变量后的目标函数中非基变量 的系数为 的检验数，记为 ，若对于每一个非基变量　 均有 　 ，则当前基可行解即为最优解，否则不是最优解。 7.3 单纯形法 初始基可行解 对应的检验数 ，均大于0，所以当前基可行解不是最优解，又 的增大都能使目标函数得到改善，这时有不止一个非基变量可以增大而改善目标。单纯形法中每次只能选一个变量增大，一般可选择检验数最大的那个非基变量，如本例中 ，故选 。记 为 增大后的取值，则必须合理确定 的最大可能取值，使所产生的下一个解还是基可行解。根据基可行解的定义，如果 变为基变量，则 中必定有一个要变为非基变量，且需保证所有变量都是非负。所以，由条件 并结合式（3）可得 7.3 单纯形法 从式（5）中可以看出，应取 即 增大到3时， ，这就决定了用 去替换 ，得到下一个基可行解 注3　上述的 增大到3， 减少到0的过程，即从一个基可行解到另一个基可行解的过程称为换基过程。而在此过程中 称为进基变量， 称为出基变量。 7.3 单纯形法 对于新的基可行解 ，可以采用相同的原理进行最优性检验和换基，直到找到最优解。通过式（3）将基变量用非基变量表达为 代入目标函数（4），有 得 的检验数 。因 ，说明目标函数还有改善的空间，于是再用上述方法，确定 为进基变量，由（6）有 =2． 7.3 单纯形法 为出基变量，新的基可行解为 通过式（6）将基变量用非基变量表达为 代入目标函数（7）得