§1单纯形法的基本思路和原理 般来说判断一个基是否是可行基,只有在求出其基本解以后,当其基本解 所有变量的解都是大于等于零,才能断定这个解是基本可行解,这个基是可行 基。那么我们能否在求解之前,就找到一个可行基呢?也就是说我们找到的一个 基能保证在求解之后得到的解一定是基本可行解呢?由于在线性规划的标准型中 要求b都大于等于零,如果我们能找到一个基是单位矩阵,或者说一个基是由单位 矩阵的各列向量所组成(至于各列向量的前后顺序是无关紧要的事)例如, 100 010 那么显然所求得的基本解一定是基本可行解,这个单位矩阵或由单位矩阵各列向 量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个b或等 于零 管理蓦
管 理 运 筹 学 6 一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解 所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行 基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个 基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中 要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位 矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如， 那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向 量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj或等 于零。 0 1 0 1 0 0 0 0 1 §1 单纯形法的基本思路和原理
§1单纯形法的基本思路和原理 在本例题中我们就找到了一个基是单位矩阵 100 B,=010 001 在第一次找可行基时,所找到的基或为单位矩阵或为由单位矩阵的各 列向量所组成,称之为初始可行基,其相应的基本可行解叫初始基本可行 解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行 基,我们将构造初始可行基,具体做法在以后详细讲述。 管理蓦
管 理 运 筹 学 7 在本例题中我们就找到了一个基是单位矩阵。 在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各 列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行 解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行 基，我们将构造初始可行基，具体做法在以后详细讲述。 = 0 0 1 0 1 0 1 0 0 B2 §1 单纯形法的基本思路和原理
§1单纯形法的基本思路和原理 二、最优性检验 所谓最优性检验就是判断已求得的基本可行解是否是最优解 1.最优性检验的依据一检验数σ; 般来说目标函数中既包括基变量,又包括非基变量。现在我们要求 只用非基变量来表示目标函数,这只要在约束等式中通过移项等处理就可 以用非基变量来表示基变量,然后用非基变量的表示式代替目标函数中基 变量,这样目标函数中只含有非基变量了,或者说目标函数中基变量的系 数都为零了。此时目标函数中所有变量的系数即为各变量的检验数,把变 量x的检验数记为σ;。显然所有基变量的检验数必为零。在本例题中目标 函数为50x1+100x2。由于初始可行解中x1,x2为非基变量,所以此目标函 数已经用非基变量表示了,不需要再代换出基变量了。这样我们可知 01=50,0,=100,02=0,04=0,05=0
管 理 运 筹 学 8 二、 最优性检验 所谓最优性检验就是判断已求得的基本可行解是否是最优解。 1. 最优性检验的依据——检验数σj 一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求 只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可 以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基 变量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系 数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变 量xi的检验数记为σi。显然所有基变量的检验数必为零。在本例题中目标 函数为50x1 +100x2。由于初始可行解中x1，x2为非基变量，所以此目标函 数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知 σ1 =50，σ2 =100，σ3 =0，σ4 =0，σ5 =0。 §1 单纯形法的基本思路和原理
§1单纯形法的基本思路和原理 2.最优解判别定理 对于求最大目标函数的问题中,对于某个基本可行解, 如果所有检验数≤0σ则这个基本可行解是最优解。下面 我们用通俗的说法来解释最优解判别定理。设用非基变量 表示的目标函数为如下形式 由于所有的ⅹ的取值范围为大于等于零,当所有的σ都小 于等于零时,可知∑σx是一个小于等于零的数,要使z 的值最大,显然∑叮只有为零。我们把这些x取为非基 变量(即令这些x的值为零),所求得的基本可行解就使目标 函数值最大为z0 *对于求目标函数最小值的情况,只需把≤0改为∝0
管 理 运 筹 学 9 §1 单纯形法的基本思路和原理 • 2.最优解判别定理 对于求最大目标函数的问题中，对于某个基本可行解， 如果所有检验数 ≤0，则这个基本可行解是最优解。下面 我们用通俗的说法来解释最优解判别定理。设用非基变量 表示的目标函数为如下形式 由于所有的xj的取值范围为大于等于零，当所有的 都小 于等于零时，可知 是一个小于等于零的数，要使z 的值最大，显然 只有为零。我们把这些xj取为非基 变量(即令这些xj的值为零)，所求得的基本可行解就使目标 函数值最大为z0。 **对于求目标函数最小值的情况，只需把 ≤0改为 ≥0 j 0 j j j J z z x = + j j j j J x j j j J x j j
§1单纯形法的基本思路和原理 基变换 通过检验,我们知道这个初始基本可行解不是最优解。下面介绍如何进 行基变换找到一个新的可行基,具体的做法是从可行基中换一个列向量,得 到一个新的可行基,使得求解得到的新的基本可行解,其目标函数值更优 为了换基就要确定换入变量与换出变量 1.入基变量的确定 从最优解判别定理知道,当某个σ;>0时,非基变量x;变为基变量不取 零值可以使目标函数值增大,故我们要选基检验数大于0的非基变量换到基 变量中去(称之为入基变量)。若有两个以上的σ;>0,则为了使目标函数 增加得更大些,一般选其中的σ·最大者的非基变量为入基变量,在本例题 中σ2=100是检验数中最大的正数,故选x2为入基变量。 管理蓦 10
管 理 运 筹 学 10 §1 单纯形法的基本思路和原理 三、 基变换 通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进 行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得 到一个新的可行基，使得求解得到的新的基本可行解，其目标函数值更优。 为了换基就要确定换入变量与换出变量。 1. 从最优解判别定理知道，当某个σj＞0时，非基变量xj变为基变量不取 零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基 变量中去（称之为入基变量）。若有两个以上的σj＞0，则为了使目标函数 增加得更大些，一般选其中的σj最大者的非基变量为入基变量，在本例题 中σ2 =100是检验数中最大的正数，故选x2为入基变量