线性规划问题的解

线性规划问题的解第一页，共二十八页，2022年，8月28日最优解：若基本可行解又是最优解（也称基本最优解），这个基就称为最优基（optimalbasis）。基本解：对于基,令非基变量为零,求得满足（1-13）的解，称为基对应的基本解（basicsolution）。基本可行解：满足（1-14）的基本解称为基本可行解（basicfeasiblesolution）；基本可行解所对应的基称为可行基（feasiblebasis）。第二页，共二十八页，2022年，8月28日

二.解的性质

在右图中设线段长度与之比为，由此得

o第三页，共二十八页，2022年，8月28日第四页，共二十八页，2022年，8月28日线性规划问题的几个定理定理1-4线性规划问题有可行解,必有基本可行解；有最优解,必有基本最优解。定理1-1线性规划问题的可行域是凸集。定理1-2A为线性规划问题可行域的极点的充要条件是的A正分量对应的系数列向量线性无关。（证明从略）。

定理1-3A是可行域的极点的充要条件是它为基本可行解。（证明从略。）第五页，共二十八页，2022年，8月28日综上所述,我们在理论上得到了线性规划问题的以下结论：线性规划问题的可行域是一凸集（包括有界凸集和无界凸集）；线性规划问题的每个基本可行解对应着可行域的一个极点（顶点）；若线性规划问题有最优解,必在可行域的某一极点上得到。由此可见,我们只需在基本可行解中寻求最优解。如何有效地寻求最优解,这就是下节要介绍的单纯形法。

第六页，共二十八页，2022年，8月28日§1-5单纯形法一、单纯形法的基本思路如果线性规划问题存在最优解，一定有一个基本可行解是最优解。因此单纯形法迭代的基本思路是：先找出一个基本可行解，判断其是否为最优解，如为否，则转换到相邻的基本可行解，并使目标函数值不断增大，一直找到最优解为止。

第七页，共二十八页，2022年，8月28日1、确定初始基可行解

max(1-17)

在约束条件（1-18）式的变量的系数矩阵中总会存在一个单位矩阵，不妨设为

(1-20)第八页，共二十八页，2022年，8月28日式中称为基向量,同其对应的决策变量称为基变量,模型中的其它变量称为非基变量。在(1-18)式中令所有非基变量等于零,即可找到一个解

X=(，)T=(b1,…,bm,0,…,0)T因有b≥0,故X满足约束(1-19),是一个基本可行解记为又称初始基本可行解。2、从一个基本可行解转换为相邻的基本可行解设初始基本可行解中的前m个为基变量,即第九页，共二十八页，2022年，8月28日经一系列变换得第十页，共二十八页，2022年，8月28日3、最优性检验和解的判别第十一页，共二十八页，2022年，8月28日（1-24）式中因,所以只要,就有。通常简写为或,它是对线性规划问题的解进行最优性检验的标志第十二页，共二十八页，2022年，8月28日第十三页，共二十八页，2022年，8月28日二、单纯形法的矩阵描述在线性规划问题的标准型：Max

第十四页，共二十八页，2022年，8月28日中，不妨设是一个可行基，则系数矩阵Ａ可分块为（Ｂ，Ｎ）。对应于Ｂ的基变量为，，非基变量为，Ｎ＝。并令，其中为基变量的系数列向量，N为非基变量的系数列向量。于是原问题可化为第十五页，共二十八页，2022年，8月28日即对约束方程两边同左乘以，得 =，并代入目标函数，得第十六页，共二十八页，2022年，8月28日令非基变量=0得=,从而相应的基本可行解为目标函数取值为又由于,故有第十七页，共二十八页，2022年，8月28日将及Z的表达式又可写成令，，则又有+=+第十八页，共二十八页，2022年，8月28日第四步：重复第二、三两步，一直到计算结束为止。

三、单纯形法的计算步骤根据上节中讲述的原理,单纯形法的计算步骤如下：第一步：求初始基本可行解,列出初始单纯形表。第二步：最优性检验。第三步：从一个基本可行解转换到相邻的目标函数值更大的基本可行解，列出新的单纯形表。

第十九页，共二十八页，2022年，8月28日一、大M法

在上一节例1-9中，化为标准形式后约束条件的系数矩阵中含有单位矩阵，以此作初始基，使求初始基可行解和建立初始单纯形表都十分方便。但时常化为标准形后的约束条件的系数矩阵中不存在单位矩例1-10用单纯形法求解线性规划问题

§1-6.初始可行基的求法

第二十页，共二十八页，2022年，8月28日解先将其化成标准形有MaxMax第二十一页，共二十八页，2022年，8月28日 这种情况下，可以通过添加两列单位向量，使连同约束条件中的向量构成单位矩阵。

是人为添加上去的，它相当于在上述问题的约束条件（1-34）中添加变量，约束条件(1-35)中添加变量，变量相应称为人工变量。由于约束条件（1-34）（1-35）在添加人工变量前已是等式为使这些等式得到满足，因此在最优解中人工变量取值必须为零。为此，令目标函数中人工变量的系数为任意大的负值，用“-M”代表。7p第二十二页，共二十八页，2022年，8月28日“-M”称为“罚因子”，即只要人工变量取值大于零，目标函数就不可能实现最优。因而添加人工变量后，例1-10的数学模型的标准形式就变为max 该模型中与对应的变量为基变量，令非基变量等于零，即得到初始基可行解,并列出初始单纯形表。在单纯形法迭代运算中，M可当作一个数学符号一起参加运算。检验数中含M符号的项，当M的系数为正时，该检验数为正，当M的系数为负时，该项检验数为负。第二十三页，共二十八页，2022年，8月28日

例1-10添加人工变量后，用单纯形法求解的过程见下页表1-8。最优解为：

二、

两阶段法 用大M法处理人工变量，在用手工计算求解时不会碰到麻烦。但用电子计算机求解时，对M就只能在计算机内输入一个机器最大字长的数字。如果线性规划问题中的或等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称为两阶段法。第二十四页，共二十八页，2022年，8月28日表1-8-30100-M-M0-M-M4191111000001[1]1-1-11-200003-3-2M4M10-M004130211-10313-21-10-1106[6]0403-3100-M-3+6M04M+103M-4M01-1/21第二十五页，共二十八页，2022年，8月28日入基出基原则首先是检验数即单纯形表中系数矩阵的第列的价值系数减去第列元素乘以对应行所在的基的价值系数的和的差。当目标函数是求max时，大者对应的列所在的变量为入基变量，如果有几个检验数一样大，且是最大者，取脚标小的变量为入基变量；当目标函数是求min时，小者为入基变量。由于第二十六页，共二十八页，2022年，8月28日续表

-3110[2/3]01/2-1/21/63/203011/30001/39000001-1/21/2-1/2-00303/2-M-3/2-M+1/213/23/20103/4-3/41/4000001-1/21/2-1/205/2-1/2100-1/41/41/4-9/2000-3/4-M+3/4-M-1/4第二十七页，共二十八页，2022年，8月28日两阶段法的第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数（一般取1），够成新的目标函数，在保持原问题约束条件不变的情况下求这个目标