《线性规划问题的解》由会员分享，可在线阅读，更多相关《线性规划问题的解（28页珍藏版）》请在金锄头文库上搜索。
1、1-4.线性规划问题的解,一.解的基本概念对于标准型LP问题,可行解：满足约束条件（1-13）和（1-14）的解称为可行解。基：A中任何一组m个线性无关的列向量构成的子矩阵,称为该问题的一个基（basis）,与中的这些列向量对应的变量称为基变量（basic variable）,最优解：若基本可行解又是最优解（也称基本最优解），这个基就称为最优基（optimal basis）。,基本解：对于基,令非基变量为零,求得满足（1-13）的解，称为基对应的基本解（basic solution）。,基本可行解：满足（1-14）的基本解称为基本可行解（basic feasible solution）；基本可
2、行解所对应的基称为可行基（feasible basis）。,二.解的性质,在右图中设线段长度与之比为 ，由此得,o,线性规划问题的几个定理,定理1-4 线性规划问题有可行解,必有基本可行解；有最优解,必有基本最优解。,定理1-1 线性规划问题的可行域是凸集。,定理1-2 A为线性规划问题可行域的极点的充要条件是的A正分量对应的系数列向量线性无关。（证明从略）。,定理1-3A是可行域的极点的充要条件是它为基本可行解。（证明从略。）,综上所述,我们在理论上得到了线性规划问题的以下结论：,线性规划问题的可行域是一凸集（包括有界凸集和无界凸集）；线性规划问题的每个基本可行解对应着可行域的一个极点（顶点
3、）；若线性规划问题有最优解,必在可行域的某一极点上得到。由此可见,我们只需在基本可行解中寻求最优解。如何有效地寻求最优解,这就是下节要介绍的单纯形法。,1-5 单纯形法,一、单纯形法的基本思路如果线性规划问题存在最优解，一定有一个基本可行解是最优解。因此单纯形法迭代的基本思路是：先找出一个基本可行解，判断其是否为最优解，如为否，则转换到相邻的基本可行解，并使目标函数值不断增大，一直找到最优解为止。,1、确定初始基可行解 max (1-17)在约束条件（1-18）式的变量的系数矩阵中总会存在一个单位矩阵，不妨设为(1-20),式中 称为基向量,同其对应的决策变量 称为基变量,模型中的其它变量 称
4、为非基变量。在(1-18)式中令所有非基变量等于零,即可找到一个解X=( ， )T=(b1,bm,0,0)T 因有b0,故X满足约束(1-19),是一个基本可行解记为 又称初始基本可行解。 2、从一个基本可行解转换为相邻的基本可行解 设初始基本可行解中的前m个为基变量,即,经一系列变换得,3、最优性检验和解的判别,（1-24）式中因 , 所以只要 ,就有 。 通常简写为 或 ,它是对线性规划问题的解进行最优性检验的标志,二、单纯形法的矩阵描述,在线性规划问题的标准型： Max,中，不妨设 是一个可行基，则系数矩阵可分块为 （，）。对应于的基变量为， ，非基变量为 ， 。并令 ，其中 为基变量
5、的系数列向量，N 为非基变量的系数列向量。于是原问题可化为,即 对约束方程两边同左乘以 ， 得 = ，并代入目标函数，得,令非基变量 =0得= , 从而相应的基本可行解为 目标函数取值为 又由于 ,故有,将 及Z的表达式又可写成令 ， ， 则又有 += +,第四步：重复第二、三两步，一直到计算结束为止。,三、单纯形法的计算步骤,根据上节中讲述的原理,单纯形法的计算步骤如下：,第一步：求初始基本可行解,列出初始单纯形表。,第二步：最优性检验。,第三步：从一个基本可行解转换到相邻的目标函数值更大的基本可行解，列出新的单纯形表。,一、 大M法在上一节例1-9中，化为标准形式后约束条件的系数矩阵中含有
6、单位矩阵，以此作初始基，使求初始基可行解和建立初始单纯形表都十分方便。但时常化为标准形后的约束条件的系数矩阵中不存在单位矩 例1-10 用单纯形法求解线性规划问题,1-6 .初始可行基的求法,解 先将其化成标准形有 Max,Max,这种情况下，可以通过添加两列单位向量，使连同约束条件中的向量构成单位矩阵。是人为添加上去的，它相当于在上述问题的约束条件（1-34）中添加变量，约束条件(1-35)中添加变量，变量相应称为人工变量。由于约束条件（1-34）（1-35）在添加人工变量前已是等式为使这些等式得到满足，因此在最优解中人工变量取值必须为零。为此，令目标函数中人工变量的系数为任意大的负值，用“
7、-M”代表。,“-M”称为“罚因子”，即只要人工变量取值大于零，目标函数就不可能实现最优。因而添加人工变量后，例1-10的数学模型的标准形式就变为max该模型中与 对应的变量 为基变量，令非基变量等于零，即得到初始基可行解,并列出初始单纯形表。在单纯形法迭代运算中，M可当作一个数学符号一起参加运算。检验数中含M符号的项，当M的系数为正时，该检验数为正，当M的系数为负时，该项检验数为负。,例1-10添加人工变量后，用单纯形法求解的过程见下页表1-8。最优解为：二、 两阶段法用大M法处理人工变量，在用手工计算求解时不会碰到麻烦。但用电子计算机求解时，对M就只能在计算机内输入一个机器最大字长的数字。
8、如果线性规划问题中的或 等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称为两阶段法。,表1-8,-3,0,1,0,0,-M,-M,0,-M,-M,4,1,9,1,1,1,1,0,0,0,0,0,1,1,1,-1,-1,1,-2,0,0,0,0,3,-3-2M,4M,1,0,-M,0,0,4,1,3,0,2,1,1,-1,0,3,1,3,-2,1,-1,0,-1,1,0,6,6,0,4,0,3,-3,1,0,0,-M,-3+6M,0,4M+1,0,3M,-4M
9、,0,1,-1/2,1,入基出基原则,首先是检验数 即单纯形表中系数矩阵的第 列 的价值系数 减去第 列元素乘以对应行所在的基的价值系数的和的差。 当目标函数是求max时， 大者对应的列所在的变量为入基变量，如果有几个检验数一样大，且是最大者，取脚标小的变量为入基变量；当目标函数是求min时， 小者为入基变量。 由于,续表,-3 1 1 0 2/3 0 1/2 -1/2 1/6 3/2,0 3 0 1 1/3 0 0 0 1/3 9,0 0 0 0 0 1 -1/2 1/2 -1/2 -,0 0 3 0 3/2 -M-3/2 -M+1/2,1 3/2 3/2 0 1 0 3/4 -3/4 1/
10、4,0 0 0 0 0 1 -1/2 1/2 -1/2,0 5/2 -1/2 1 0 0 -1/4 1/4 1/4,-9/2 0 0 0 -3/4 -M+3/4 -M-1/4,两阶段法的第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数（一般取1），够成新的目标函数，在保持原问题约束条件不变的情况下求这个目标函数极小化时的解。显然在第一阶段中，当人工变量取值全为0时，目标函数值也为0。这时候的最优解就是原线性规划问题的一个基本可行解。如果第一阶段求解结果最优解的目标函数值不为0，即最优解的基变量中含有非零的人工变量，表明原线性规划问题无可行解。 当第一阶段求解结果表明问题有可行解时，第二阶段是在原问题中去除人工变量，并从此可行解（即第一阶段的最优解）出发，继续寻找问题的最优解。见34页例9，表1-7，1-8,
