资源描述
节节2.2 2.2 线性规划问题的解和单纯形法线性规划问题的解和单纯形法本节中，我们先通过一个只有两个决策变本节中，我们先通过一个只有两个决策变量的线性规划问题的图解，来分析线性规量的线性规划问题的图解，来分析线性规划问题解的特点，并在此基础上得出求解划问题解的特点，并在此基础上得出求解线性规划问题的单纯形方法，最后再讨论线性规划问题的单纯形方法，最后再讨论各种特殊解的情况。各种特殊解的情况。一、线性规划的图解法一、线性规划的图解法如果一个线性规划模型中的决策变量只有如果一个线性规划模型中的决策变量只有两个，那么可以用一种比较简便的图解法两个，那么可以用一种比较简便的图解法来解。来解。例例2.4 2.4 用图解法解以下线性规划。用图解法解以下线性规划。约束条件：约束条件：在以上的解题过程中可以看出在以上的解题过程中可以看出z的最优解总的最优解总是在可行域的顶点是在可行域的顶点A,B,C,D,E中某一点处出中某一点处出现。至于到底在哪个顶点出现最优解这决现。至于到底在哪个顶点出现最优解这决定于目标函数的斜率。我们把目标函数改定于目标函数的斜率。我们把目标函数改变时，最优解所对应的顶点和最优解也跟变时，最优解所对应的顶点和最优解也跟着变化的情况列表如着变化的情况列表如F(见表见表2.1)：表1.1仍以例仍以例l.4为例，将其化成标准形式如下：为例，将其化成标准形式如下：约束条件：约束条件：是松弛变量。增加这是松弛变量。增加这4个松弛变个松弛变量后，可行域中的每一点可以用变量量后，可行域中的每一点可以用变量来表示。来表示。表表2.2一般地，对一个有一般地，对一个有 个变量、个变量、个约束方个约束方程程()()的线性规划问题的线性规划问题约束条件：约束条件：对其约束条件方程组对其约束条件方程组 有一组解有一组解 且则称其为线性规划问题的可行解。如果可行解可则称其为线性规划问题的可行解。如果可行解可使目标函数达到最大，则称其为最优解，其对应使目标函数达到最大，则称其为最优解，其对应的目标函数最大值称为最优值。的目标函数最大值称为最优值。如果令其中的如果令其中的 个变量等于零，再个变量等于零，再解剩下的解剩下的 个变量那个方程的方程组而个变量那个方程的方程组而得到的一组解，称为线性规划问题的基本得到的一组解，称为线性规划问题的基本解。解。这这 个变量称为这个基本解的基变量，个变量称为这个基本解的基变量，所有基变量的集合称为这个基本解的基，所有基变量的集合称为这个基本解的基，而令为零的而令为零的 个变量称为非基变量。个变量称为非基变量。如果在这个基本解中，基变量取值均为非如果在这个基本解中，基变量取值均为非负，满足问题中的决策变量非负约束，则负，满足问题中的决策变量非负约束，则称这组解是基本可行解，否则称为不可行称这组解是基本可行解，否则称为不可行解。解。由此可见，一个线性规划问题解空间的极由此可见，一个线性规划问题解空间的极点完全是由其约束条件方程组的基本可行点完全是由其约束条件方程组的基本可行解来确定的。解来确定的。这样我们就从理论上得到了解一般线性规这样我们就从理论上得到了解一般线性规划问题的代数方法，即对约束方程组，依划问题的代数方法，即对约束方程组，依次选取次选取 个变量，令其为零，作为非个变量，令其为零，作为非基变量，求出基本解，如果基本解非负，基变量，求出基本解，如果基本解非负，即得一个基本可行解，否则舍去。即得一个基本可行解，否则舍去。这样最多可得这样最多可得 个基本可行解。比较这个基本可行解。比较这有限个基本可行解的目标函数值，选取最有限个基本可行解的目标函数值，选取最大的，即可得线性规划问题的最优解了。大的，即可得线性规划问题的最优解了。但是这样对有个但是这样对有个 未知数未知数 个方程个方程()的线性规划问题就要解的线性规划问题就要解 个方程组，而个方程组，而最优解要把这最优解要把这 个方程组的计算结果进个方程组的计算结果进行比较后才能得到。行比较后才能得到。如果如果 和和 比较大，方程组的个数就很多。比较大，方程组的个数就很多。例如当例如当 ，时有时有 个方程组。显然要解这么多的方程组是太个方程组。显然要解这么多的方程组是太麻烦了。麻烦了。事实上，这其中有许多方程组的解是不可行事实上，这其中有许多方程组的解是不可行的甚至不存在的。的甚至不存在的。例如在前面的例例如在前面的例1.41.4中方程组有中方程组有 ，个，其中只有个，其中只有5 5个是可行的极点，还有个是可行的极点，还有1010个是不可行或不存个是不可行或不存在的。因此根本用不着计算所有的方程组。在的。因此根本用不着计算所有的方程组。为了大大提高计算效率，避免计算那些不可为了大大提高计算效率，避免计算那些不可行解，或虽是基本可行解，但目标函数值显行解，或虽是基本可行解，但目标函数值显然不好的解，人们就研究出了解线性规划问然不好的解，人们就研究出了解线性规划问题的题的单纯形方法。单纯形方法。二、单纯形法二、单纯形法单纯形法是求解线性规划问题的一种十分单纯形法是求解线性规划问题的一种十分有效的算法。有效的算法。它的基本原理就是基于上面的分析，即在它的基本原理就是基于上面的分析，即在有限的基本可行解中，寻找使目标函数达有限的基本可行解中，寻找使目标函数达到最优的最优解。到最优的最优解。在具体计算上，它先要求用最简单的方法在具体计算上，它先要求用最简单的方法找到一个基本可行解，然后逐步改进，在找到一个基本可行解，然后逐步改进，在找下一个基本解时，每次只改变一个基变找下一个基本解时，每次只改变一个基变量，同时要求新得的基本解一定是非负可量，同时要求新得的基本解一定是非负可行的，而其对应的目标函数值不会比原来行的，而其对应的目标函数值不会比原来的差。的差。这样就可大大提高计算的效率，同时它又这样就可大大提高计算的效率，同时它又采用了一种特殊的表格形式，使计算更清采用了一种特殊的表格形式，使计算更清晰、简单。晰、简单。在用单纯形法解线性规划时，除允许目标在用单纯形法解线性规划时，除允许目标函数求最小值，其他条件必须都先化成标函数求最小值，其他条件必须都先化成标准形式。准形式。下面用例下面用例1.41.4的标准形式为例，来说明单纯的标准形式为例，来说明单纯形法的计算方法。形法的计算方法。在其约束条件方程组中，因松弛变量在其约束条件方程组中，因松弛变量的系数形成一个单位矩阵，因此可以看出，的系数形成一个单位矩阵，因此可以看出，如果令如果令 为非基变量，可立即为非基变量，可立即得到一个基本可行解，得到一个基本可行解，称为初始基本可行解。称为初始基本可行解。将目标函数写成将目标函数写成后，就可以把它和约束条件一起写在下面后，就可以把它和约束条件一起写在下面的单纯形表格中，如表的单纯形表格中，如表2.32.3所示。所示。表中表中“基基”栏写出目前所采用的基变量栏写出目前所采用的基变量 和和 。而。而“解解”栏则是目前基变量的取值，栏则是目前基变量的取值，即即 和和 。不出现在不出现在“基基”栏的非基变量栏的非基变量(在本例中现在在本例中现在是是 和和 )的值都是零。的值都是零。这组解使目标函数这组解使目标函数 的值等于零，写在的值等于零，写在“解解”栏的第一行。栏的第一行。显然目前的基本可行解，显然目前的基本可行解，和和 不是最优的。不是最优的。为了改进目标函数值我们要找一个较好的为了改进目标函数值我们要找一个较好的基本可行解。基本可行解。怎样找呢怎样找呢?方法是在目前的非基变量中挑选一个合适方法是在目前的非基变量中挑选一个合适的变量，把它的值增加到大于零，成为一的变量，把它的值增加到大于零，成为一个新的基变量，这个新加入的基变量称为个新的基变量，这个新加入的基变量称为调入变量。这样就可以改进目标函数值。调入变量。这样就可以改进目标函数值。但在本例中，一个极点要有两个数值为零但在本例中，一个极点要有两个数值为零的非基变量，现在有一个非基变量大于零的非基变量，现在有一个非基变量大于零了，那么就必须从原来的基变量中挑选出了，那么就必须从原来的基变量中挑选出一个来令它等零，并且要保证新的解是可一个来令它等零，并且要保证新的解是可行的。行的。这个从基变量中挑选出来的变量称为调出这个从基变量中挑选出来的变量称为调出变量。变量。怎样桃选调入变量呢怎样桃选调入变量呢?对一个最大化问题而对一个最大化问题而言，一般是挑选单纯形表格中目标方程这言，一般是挑选单纯形表格中目标方程这一行内有负系数的变量作为调入变量。一行内有负系数的变量作为调入变量。如果有几个变量的系数都是负的，通常就如果有几个变量的系数都是负的，通常就挑选负得最多的那个变量作为调入变量。挑选负得最多的那个变量作为调入变量。因为把这个变量放到目标方程右边的时候因为把这个变量放到目标方程右边的时候就是系数最大的，给这种变量一个大于零就是系数最大的，给这种变量一个大于零的值，很可能使目标函数值增加得最多。的值，很可能使目标函数值增加得最多。在本例中，目标方程这一行中在本例中，目标方程这一行中 和和 的系的系数数 都是负的，但都是负的，但 的系数的系数“-4-4”比比 的系数的系数“-3-3”负得更多，因此选负得更多，因此选 作为调作为调入变量，这样就符合前面所讲的最优性条入变量，这样就符合前面所讲的最优性条件的要求。件的要求。选好调入变量后怎样确定调出变量呢选好调入变量后怎样确定调出变量呢?确定调出变量的原则是确定调出变量的原则是保证所有基变量为非负，并且使一个调出保证所有基变量为非负，并且使一个调出的基变量为零。的基变量为零。要做到这两点就要考虑约束条件要做到这两点就要考虑约束条件由于由于 是调入变量，是调入变量，仍是非基变量，因仍是非基变量，因此约束条件就可以写成此约束条件就可以写成我们希望在保证变量我们希望在保证变量 和和 非非负的前提下，使负的前提下，使 的值能尽量增大。那么的值能尽量增大。那么 的值最多可以增大到多少呢的值最多可以增大到多少呢?需要找出需要找出 可以增大的最大值。可以增大的最大值。对于第一个约束条件，要使对于第一个约束条件，要使必须取必须取 。对于第二个约束条件，因为对于第二个约束条件，因为 前的系数前的系数-3 3是负数，所以是负数，所以 可以取任意非负值，保可以取任意非负值，保证证 。对于第三个约束条件，因为对于第三个约束条件，因为 前的系数前的系数为零，所以为零，所以 也可以取任意非负值，保也可以取任意非负值，保证证对于第四个约束条件，要使对于第四个约束条件，要使必须必须总之，要使，总之，要使，同时成立，同时成立，只有取只有取于是我们把于是我们把 增大到增大到2 2，同时使原来的基，同时使原来的基变量变量 。这个这个2 2是比值是比值 和和 中的最小中的最小值。值。当当 时，时，而其余变量保持非，而其余变量保持非负，因此确定负，因此确定 作为调出变量。作为调出变量。由此可见，要确定调出变量，只要算出各由此可见，要确定调出变量，只要算出各约束方程右边常数与该约束方程中调入变约束方程右边常数与该约束方程中调入变量前的正系数之比，把比值最小的基变量量前的正系数之比，把比值最小的基变量作为调出变量。作为调出变量。如果同时有几个这样的变量，则任选其中如果同时有几个这样的变量，则任选其中之一。这可从单纯形表中直接算出，即把之一。这可从单纯形表中直接算出，即把“解解”栏中的各个数字与栏中的各个数字与 栏下的同行正栏下的同行正数字相比，算出比值如表数字相比，算出比值如表2.42.4所示。所示。表表2.4表表2.5表表2.6表表2.7 得到解得到解 对应的点是图对应的点是图2.2中的中的C点。此时目标函数点。此时目标函数值值z9。由于目标方程中的系数已经全部是非负的，由于目标方程中的系数已经全部是非负的，所以这就是最优解。而所以这就是最优解。而z9就是目标函数就是目标函数的最优值。的最优值。在以上计算过程中我们只碰到三个可行的在以上计算过程中我们只碰到三个可行的极点就得到最优解，并不必要去计算所有极点就得到最优解，并不必要去计算所有的五个极点的五个极点A、B、C、D、E，更不必谈那，更不必谈那些不可行或不存在的极点了，通过这个例些不可行或不存在的极点了，通过这个例子可以看出用单纯形法解一个线性规划问子可以看出用单纯形法解一个线性规划问题的基本思想。题的基本思想。上面的例子是最大化问题。上面的例子是最大化问题。如果是最小化问题，那么在挑选调入变量如果是最小化问题，那么在挑选调入变量时，是选取目标函数中具有正的系数中最时，是选取目标函数中具有正的系数中最大的一个，而调出变量的选取则与最大化大的一个，而调出变量的选取则与最大化问题相同。问题相同。总之，在采用单纯形法时要牢牢掌握最优总之，在采用单纯形法时要牢牢掌握最优性和可行性这两个条件。性和可行性这两个条件。所谓最优性条件是对一个线性规划的最大所谓最优性条件是对一个线性规划的最大(小小)化问题，在只按非基变量表示的目标方化问题，在只按非基变量表示的目标方程中，在非基变量中挑选一个目标方程系程中，在非基变量中挑选一个目标方程系数具有最小负数数具有最小负数(最大正数最大正数)的变量作为调入的变量作为调入变量。变量。如有几个相同时可任选其一。当单纯形表如有几个相同时可任选其一。当单纯形表格中目标方程的系数全部是非负格中目标方程的系数全部是非负(非正非正)时得时得到最优解。到最优解。所谓可行性条件是把基变量的值和调入变所谓可行性条件是把基变量的值和调入变量中正的约束系数相比，选取比值最小的量中正的约束系数相比，选取比值最小的那那个基本量作为调出变量。个基本量作为调出变量。如有几个相同时可任选其一。如有几个相同时可任选其一。现在把用单纯形法解线性规划问题的计算现在把用单纯形法解线性规划问题的计算步骤归纳如下：步骤归纳如下：第第1步：把线性规划用标准形式表示并填入步：把线性规划用标准形式表示并填入规定格式的单纯形表格中。规定格式的单纯形表格中。第第2步：选定一个基本可行解，称为初始基步：选定一个基本可行解，称为初始基本可行解。这里有以下两种情况。本可行解。这里有以下两种情况。(1)如果约束方程的系数矩阵中含有一个单如果约束方程的系数矩阵中含有一个单位阵，或在添加松弛变量后有一个单位阵，位阵，或在添加松弛变量后有一个单位阵，那么可以把对应于这个单位阵的有关变量那么可以把对应于这个单位阵的有关变量作为基变量，得到一个基本可行解。作为基变量，得到一个基本可行解。(2)如果约束方程的系数矩阵或在添加松弛如果约束方程的系数矩阵或在添加松弛变量后的系数矩阵中都不含有一个单位阵，变量后的系数矩阵中都不含有一个单位阵，则可采用一种所谓则可采用一种所谓“人工变量方法人工变量方法”(见本见本节第三点节第三点)来得到一个基本可行解。来得到一个基本可行解。第第3步：应用最优件条件和可行件条件逐步步：应用最优件条件和可行件条件逐步产生新的基本可行解直到取得最优解为止。产生新的基本可行解直到取得最优解为止。当然这是以最优解存在并且是有限的为前当然这是以最优解存在并且是有限的为前提。提。对于可行解不存在或解无界的情况则在本对于可行解不存在或解无界的情况则在本节第四点中讨论。节第四点中讨论。例例2.5 解例解例2.1中所得到的线性规划问题。中所得到的线性规划问题。约束条件：约束条件：解：增加松弛变量解：增加松弛变量 后，得到初始后，得到初始表格如表表格如表2.8所示。所示。表表2.8表表2.9表表2.10三、人工变量方法三、人工变量方法单纯形法求解线性规划问题时，首先要找到一个单纯形法求解线性规划问题时，首先要找到一个初始基本可行解，而在一个线性规划问题的标准初始基本可行解，而在一个线性规划问题的标准形式中，并不总能很容易地得到一个初始基本可形式中，并不总能很容易地得到一个初始基本可行解，此时就要采用所谓行解，此时就要采用所谓“人工变量人工变量”来得到初来得到初始基变量，即对缺少初始基变量的约束方程，人始基变量，即对缺少初始基变量的约束方程，人为地增加一个变量作为初始基变量，下面通过例为地增加一个变量作为初始基变量，下面通过例子来说明采用人工变量的大子来说明采用人工变量的大M方法及其改进的二方法及其改进的二阶段方法。阶段方法。例例2.6 约束条件：约束条件：(2.1)解：这个问题在加入松弛变量后化为标准解：这个问题在加入松弛变量后化为标准形式如下：形式如下：约束条件：约束条件：(2.2)我们再增加两个非负的变量我们再增加两个非负的变量,使原来使原来的问题化为的问题化为 约束条件：约束条件：(2.3)这里这里M是一个很大的正数。是一个很大的正数。可以证明，如果式可以证明，如果式(2.2)有最优解，那么在有最优解，那么在式式(2.3)所得到的最优解中人工变量和一定所得到的最优解中人工变量和一定是零。是零。事实上，这个结论也可以直观地看出。事实上，这个结论也可以直观地看出。因为我们的目标是求的最小值，如果在最因为我们的目标是求的最小值，如果在最优解中优解中 或或 有一个不是零，或两个都不有一个不是零，或两个都不是零，那么由于是零，那么由于M是很大的正数，乘上是很大的正数，乘上 或或 后仍是一个很大的正数，这就不会使后仍是一个很大的正数，这就不会使z达到最小。达到最小。所以在式所以在式(2.2)有最优解的情况下，在式有最优解的情况下，在式(2.3)所得到的最优解中人工变量一定都是所得到的最优解中人工变量一定都是零。零。这样式这样式(2.3)的最优解也就是式的最优解也就是式(2.2)即式即式(2.1)的最优解。的最优解。现在我们用单纯形法来解式现在我们用单纯形法来解式(2.3)。为此，先把目标函数和约束条件填入单纯为此，先把目标函数和约束条件填入单纯形表中形表中(见表见表2.11)。表表2.11基基 右边右边 1-4-10-M-M0003101003043-1010601200013为了应用最优性条件，目标方程必须只用为了应用最优性条件，目标方程必须只用非基变量来表示，以便反映出这些变量对非基变量来表示，以便反映出这些变量对目标函数所起的作用。因此要把各个基变目标函数所起的作用。因此要把各个基变量在目标方程中的系数都变为零。量在目标方程中的系数都变为零。现在上面的表格中基变量现在上面的表格中基变量 和和 在目标在目标方程中的系数都是方程中的系数都是-M，这可通过行的变换，这可通过行的变换把它们化为零。即把它们化为零。即 新的目标方程老的目标方程新的目标方程老的目标方程+M 约约 束行的方程束行的方程+M 约束行的方程约束行的方程 这样得到表这样得到表2.12。表表2.12基基 右边右边 1-4+7M -1+4M -M 0009M 03101003043-1010601200013由于这是一个最小化问题，运用最优条件。由于这是一个最小化问题，运用最优条件。调入变量应该是目标方程中具有调入变量应该是目标方程中具有最大正系最大正系数数的变量，现在是的变量，现在是 。再由可行性条件知再由可行性条件知 是调出变量。于是通是调出变量。于是通过变换得到：过变换得到：在表在表2.12中，第一次迭代：调入中，第一次迭代：调入 和调和调出出 ，得表，得表2.13。表表2.13基基 右边右边 10(1+5M)/3-M(4-7M)/3004+2M011/301/3001005/3-1-4/3102005/30-1/3012第二次迭代：调入第二次迭代：调入 和和 调出调出,得表得表2.14。表表2.14基基 右边右边 1001/58/5-M-1/5-M018/50101/53/5-1/503/5001-3/5-4/53/506/500011-110在在2.14中，第三次迭代：调入中，第三次迭代：调入 和和 调出调出,得表得表2.15表表2.15基基 右边右边 10007/5-M-M-1/518/501002/50-1/53/50010-1/503/56/500011-110这样得到最优解这样得到最优解 而目标函数而目标函数 ，这也就是原来线性规，这也就是原来线性规划问题划问题(2.1)的最优解。的最优解。注意注意 对于最大化问题在添加人工变量后，对于最大化问题在添加人工变量后，目标函数中人工变量的系数应是目标函数中人工变量的系数应是“-M”。以上的人工变量大以上的人工变量大M方法虽然比较完善，但方法虽然比较完善，但有一个缺点，就是常数有一个缺点，就是常数M必须是一个很大的必须是一个很大的数，而一般变量数，而一般变量 的系数和它相比，的系数和它相比，显然很小。在电子计算机的计算中往往会显然很小。在电子计算机的计算中往往会由此而产生误差。由此而产生误差。为了克服这一缺点可以不用常数为了克服这一缺点可以不用常数M，而把原，而把原来的问题分成两个阶段来解称为来的问题分成两个阶段来解称为“两阶两阶段法段法”。这种方法的步骤如下所述。这种方法的步骤如下所述。第第1阶段：阶段：用人工变量的和来代替原来的目用人工变量的和来代替原来的目标函数，约束条件仍旧不变，作出一个新标函数，约束条件仍旧不变，作出一个新的线性规划问题。的线性规划问题。结论：如果原来的问题有可行解，那么新结论：如果原来的问题有可行解，那么新问题的目标函数最小值一定等于零，也就问题的目标函数最小值一定等于零，也就是所有人工变量都是零。是所有人工变量都是零。反之，如果所解出新问题的最小值大于零。反之，如果所解出新问题的最小值大于零。那就表明原来的问题没有可行解。那就表明原来的问题没有可行解。第第2阶段：阶段：把第把第1阶段所求得的最优基本解阶段所求得的最优基本解作为原问题的一个初始解，再应用通常的作为原问题的一个初始解，再应用通常的线性规划方法求出最优解。线性规划方法求出最优解。下面用两阶段法来解前面的例下面用两阶段法来解前面的例2.6。第第1阶段：作出新的目标函数是阶段：作出新的目标函数是 这里这里 和和 是人工变量，约束条件是人工变量，约束条件仍和前面相同。仍和前面相同。先填入单纯形表格中先填入单纯形表格中(见表见表2.16)。表表2.16基基 右边右边 1000-1-10003101003043-1010601200013 为了使目标方程只按非基变量来表示，通为了使目标方程只按非基变量来表示，通过行的变换得到下面的表格（见表过行的变换得到下面的表格（见表2.17）表表2.17基基 右边右边 174-1000903101003043-1010601200013在表在表2.17中，第一次迭代：调入中，第一次迭代：调入 和和 调出调出 ，得表，得表2.18。表表2.18基基 右边右边 105/3-1-7/3002011/301/3001005/3-1-4/3102005/30-1/3012第二次迭代：调入第二次迭代：调入 和调出和调出 ，得表，得表2.19。表表2.19基基 右边右边 1000-1-1000101/53/5-1/503/5001-3/5-4/53/506/500011-110 到这里目标方程中的系数全为非正，故得到这里目标方程中的系数全为非正，故得到最优目标值。到最优目标值。这表明原来的问题有可行解，于是进入第这表明原来的问题有可行解，于是进入第二阶段。二阶段。第第2阶段：首先用第阶段：首先用第2阶段的目标函数阶段的目标函数 来来代替第代替第1阶段的阶段的 。由于在表由于在表2.19中人工变量中人工变量 和和 不是不是基变量，因此可以从表格中删去，而得到基变量，因此可以从表格中删去，而得到初始表格如表初始表格如表2.20所示。所示。表表2.20基基右边右边1-4-10000101/503/5001-3/506/5000110为了使目标函数只用非基变量表示，在表为了使目标函数只用非基变量表示，在表2.20中把目标方程中中把目标方程中 和和 的系数化为的系数化为零，得到表零，得到表2.21。表表2.21基基右边右边1001/5018/50101/503/5001-3/506/5000110在表在表2.21中根据最优条件，中根据最优条件，是调入变是调入变量，并由可行性条件知量，并由可行性条件知 是调出变量，是调出变量，再一次迭代后得到表格如表再一次迭代后得到表格如表2.22所示。所示。表表2.22基基右边右边1000-1/518/50100-1/53/500103/56/5000100到这里目标方程中的系数都已非正，故得到这里目标方程中的系数都已非正，故得到最优解到最优解而而 ，这和前面用大，这和前面用大M方法所方法所计算的结果相同。计算的结果相同。四、几种特殊情况的解四、几种特殊情况的解 线性规划问题除一般情况有唯一最优解线性规划问题除一般情况有唯一最优解外。也可能存在一些持殊的情况，产生特外。也可能存在一些持殊的情况，产生特殊的解或无解。殊的解或无解。通常有以下几种：通常有以下几种：退化的解，无界的解可选择的解退化的解，无界的解可选择的解(即无穷即无穷多解多解)及不存在可行解等。及不存在可行解等。下面我们举例说明在单纯形法计算过程中，下面我们举例说明在单纯形法计算过程中，如何来判断及求出这些特殊情况的解。如何来判断及求出这些特殊情况的解。1退化的解退化的解对一个线性规划问题应用单纯形法进行迭对一个线性规划问题应用单纯形法进行迭代时，有时会遇到在某一次迭代后基变量代时，有时会遇到在某一次迭代后基变量中有一个或几个等于零的情况，我们称这中有一个或几个等于零的情况，我们称这种解是退化的。最优解。种解是退化的。最优解。当然，可能这个解是最优的那就称为退当然，可能这个解是最优的那就称为退化的最优解。化的最优解。也可能还不是最优的，而继续进行迭代时也可能还不是最优的，而继续进行迭代时这种退化消失了。这种退化消失了。最后得到非退化的最优解。最后得到非退化的最优解。还有一种情况是在继续进行迭代时到某一还有一种情况是在继续进行迭代时到某一步又重复出现前面的某一个单纯形表格而步又重复出现前面的某一个单纯形表格而形成一种循环现象，这样就得不到最优解。形成一种循环现象，这样就得不到最优解。对于这种情况虽然有几种处理的方法，但对于这种情况虽然有几种处理的方法，但由于在实际问题中很少碰到，这里就不谈由于在实际问题中很少碰到，这里就不谈了。了。下面举个例子来说明退化的最优解。下面举个例子来说明退化的最优解。例例2.7 约束条件：约束条件：解：填入单纯形表格后，得到初始表格如解：填入单纯形表格后，得到初始表格如表表2.23所示。所示。表表2.23基基右边右边1-3-9000014108012014表中是表中是 松弛变量。松弛变量。第一次迭代：调入第一次迭代：调入 和调出和调出 ，得表，得表2.24。表表2.24基基右边右边1-3/409/401801/411/40201/20-1/210第二次迭代：第二次迭代：调入调入 和调出和调出 ，得表，得表2.25。表表2.25基基右边右边1003/23/3180011/2-1/22010-120得到最优解得到最优解 ，和，和这是一个退化的最优解。这是一个退化的最优解。这个例子的解用图像表示如图这个例子的解用图像表示如图2.4所示。所示。在本例中，本来只要两个约束条件就可以在本例中，本来只要两个约束条件就可以确定一个极点，而现在确定一个极点，而现在和和这三个约束条件所对应的直线都经过最优这三个约束条件所对应的直线都经过最优解点解点(0，2)。实际上实际上 这个约束条件是多余的。这个约束条件是多余的。2无界的解无界的解这种情况发生在可行域是无界的时候，以这种情况发生在可行域是无界的时候，以致使目标函数值可以无限地增加。致使目标函数值可以无限地增加。但是一个无界的可行域并不一定总是产生但是一个无界的可行域并不一定总是产生无限的目标函数值，下面对这两种情况各无限的目标函数值，下面对这两种情况各举一个例子来说明。举一个例子来说明。例例2.8 约束条件：约束条件：解：增加松弛变量后，初始表格如表解：增加松弛变量后，初始表格如表2.26所示。所示。表表2.26基基右边右边1-2-100001-1101002-10140根据最优性条件在表根据最优性条件在表2.26中，应调入中，应调入和调出和调出 ，得到表，得到表2.27。表表2.27基基右边右边10-3202001-11010001-2120 在表在表2.27中，再调入中，再调入 和调出和调出 ，得到表得到表2.28。表表2.28基基右边右边100-4380010-1130001-2120到这里要调入，但它在约束方程中的系数到这里要调入，但它在约束方程中的系数都是负的，不满足可行性条件，因而得不都是负的，不满足可行性条件，因而得不到最优解。到最优解。事实上在初始表格中就可以看出，变量在事实上在初始表格中就可以看出，变量在目标方程中的系数也是负的，并且它在两目标方程中的系数也是负的，并且它在两个约束方程中的系数都是个约束方程中的系数都是“-1”，这就表明，这就表明它可以无限制的增加而不影响问题的可行它可以无限制的增加而不影响问题的可行性，也就是解是无界的。性，也就是解是无界的。在图像上表示如图在图像上表示如图2.5所示。所示。一般来说，在任何一次迭代中，如果任何一般来说，在任何一次迭代中，如果任何一个可以调入基的变量在各个约束条件中一个可以调入基的变量在各个约束条件中的系数都是负的或者是零，那么可以确定的系数都是负的或者是零，那么可以确定解是无界的。解是无界的。例例2.9 约束条件：约束条件：解解：这这个个问问题题在在增增加加松松弛弛变变量量后后的的初初始始表表格如表格如表2.29所示。所示。表表2.29基基右边右边1-6200002-11020100-14 在表在表2.29中，变量中，变量 在约束条件中的系在约束条件中的系数是数是“-1”和和“0”，这表明可行域是无界，这表明可行域是无界的。的。但它在目标方程中系数是正的，不能作为但它在目标方程中系数是正的，不能作为调入变量，因而仍可以得到最优解。调入变量，因而仍可以得到最优解。计算如下：计算如下：在表在表2.29中，调入中，调入 和调出和调出 ，得，得表表2.30。表表2.30基基右边右边10-130601-1/21/201001/2-1/213 在表在表2.30中，调入中，调入 ，和调出，和调出 ，得表得表2.31。表表2.31基基右边右边1002212010014001-126 得到最优解得到最优解 和和 。这个例子表明一个问题有无界的可行域，这个例子表明一个问题有无界的可行域，但最优解仍可能是有界的。但最优解仍可能是有界的。用图像表示如图用图像表示如图2.6所示。所示。3可选择的最优解可选择的最优解 这种情况发生在目标函数所表示的直线这种情况发生在目标函数所表示的直线和一个约束条件所表示的对应直线相互平和一个约束条件所表示的对应直线相互平行的时候。行的时候。此时，目标函数可以在不止此时，目标函数可以在不止个基本解处个基本解处取得同样的最优值，我们称这些解处可选取得同样的最优值，我们称这些解处可选择最优的基本解。择最优的基本解。并且最优基本解的任何加权平均数也可以并且最优基本解的任何加权平均数也可以得到同样的最优值，我们称这些解是可选得到同样的最优值，我们称这些解是可选择最优的非基本解。择最优的非基本解。总之，这种问题有无穷多个解，而每一个总之，这种问题有无穷多个解，而每一个解都得到相同的目标函数值。下面举个例解都得到相同的目标函数值。下面举个例子来说明。子来说明。例例2.10 约束条件：约束条件：解：解：这个问题的图像如图这个问题的图像如图2.7所示。所示。从上图中可以看出，目标方程从上图中可以看出，目标方程和第一个约束条件和第一个约束条件的斜率都是的斜率都是2/7，因此在可行域的极点，因此在可行域的极点B和和C处可以得到同样的目标函数值。处可以得到同样的目标函数值。如果用单纯形法计算则在增加松弛变量后，如果用单纯形法计算则在增加松弛变量后，可得到初始表格如表可得到初始表格如表2.32所示。所示。表表2.32基基右边右边1-4-1400002710210720121 在表在表2.32中，调入中，调入 和调出和调出 ，得表得表2.33。表表2.33基基右边右边100204202/711/703045/70-2/7115 得到最优解得到最优解 和和 。但是从最优表格表但是从最优表格表1.33中看非基变量中看非基变量 在目标方程中有一个零的系数，这表明存在目标方程中有一个零的系数，这表明存在着可选择的解。在着可选择的解。这个解是基本的，因为这个解是基本的，因为 可以做基变量。可以做基变量。计算如下：计算如下：在表在表2.33中，调入中，调入 和调出和调出 ，得表得表2.34。表表2.34基基右边右边10020420017/45-2/457/3010-2/457/457/3得到新的最优解是得到新的最优解是 和和 以上得到两个可选择的最优基本解以上得到两个可选择的最优基本解(0,3)和和(7/3，7/3)。它们的目标函数值它们的目标函数值 是相同的。是相同的。我们可以用这两个最优基本解的任何加权我们可以用这两个最优基本解的任何加权平均数产生无穷多个最优的非基本解。平均数产生无穷多个最优的非基本解。这只要设这只要设 ，而令，而令 和和即即 和和就可以了。就可以了。当当 时，就得到两个最优基本解，时，就得到两个最优基本解，而在而在 时，时，所得到的就是一族最优的非基本解，所得到的就是一族最优的非基本解，它们就是图它们就是图2.7中中BC线段上的各个点。线段上的各个点。一般地，一个线性规划问题如果有一般地，一个线性规划问题如果有P个可选个可选择的最优基本解择的最优基本解那么包括基本的和非基本的所有可选择解那么包括基本的和非基本的所有可选择解族是族是 这里这里 并且并且 。4不存在可行解不存在可行解 这种情况是在一个线性规划问题中没有一这种情况是在一个线性规划问题中没有一个点能满足所有约束条件时发生。个点能满足所有约束条件时发生。在图形上，没有可行解意味着可行域是空在图形上，没有可行解意味着可行域是空的。的。下面举个例子说明怎样应用单纯形法来看下面举个例子说明怎样应用单纯形法来看出这种情况。出这种情况。例例2.11 约束条件：约束条件：解：增加松弛变量和人工变量后，填入单解：增加松弛变量和人工变量后，填入单纯形表格如表纯形表格如表2.35所示。所示。表表2.35基解1-3-200M00210102034-10112在表在表2.35中将目标方程只按非基变量表示后，中将目标方程只按非基变量表示后，得到初始表格如表得到初始表格如表2.36。表表2.36基解1-3-3M-2-4MM00-12M0210102034-10112在表在表2.36中，调入中，调入 和调出和调出 ，得表得表2.37。表表2.37基解11+5M0M2+4M04-4M02101020-50-1-414 根据最优性条件，这个解是最优的，但在根据最优性条件，这个解是最优的，但在最优解中包括了一个正的人工变量最优解中包括了一个正的人工变量R，这表，这表明问题没有可行解。明问题没有可行解。因为一个正的因为一个正的R表示原来问题的第二个约束表示原来问题的第二个约束条件没有被满足，所得到的解实际上是表条件没有被满足，所得到的解实际上是表示另外一个问题。示另外一个问题。这个例子的图像如图这个例子的图像如图2.8所示。所示。从图从图2.8可以看出，这个问题没有可行域。可以看出，这个问题没有可行域。一个线性规划问题是否有可行解也可以用一个线性规划问题是否有可行解也可以用两阶段法中的第两阶段法中的第1阶段来检验。阶段来检验。
展开阅读全文