线性规划问题的解

《线性规划问题的解》由会员分享，可在线阅读，更多相关《线性规划问题的解（28页珍藏版）》请在金锄头文库上搜索。

1、1-4.线性规划问题的解v 一.解的基本概念对于标准型LP问题 可行解：可行解：满足约束条件（满足约束条件（1-131-13）和（）和（1-141-14） 的解称为可行解。的解称为可行解。基：基：A A中任何一组中任何一组mm个线性无关的列向量构个线性无关的列向量构 成的子矩阵成的子矩阵, ,称为该问题的一个基（称为该问题的一个基（basisbasis）, ,与与 中的这些列向量对应的变量称为基变量（中的这些列向量对应的变量称为基变量（ basic variablebasic variable）v最优解：若基本可行解又是最优解（也 称基本最优解），这个基就称为最优基 （optimal basi

2、s）。n n基本解：基本解：对于基对于基, ,令非基变量为零令非基变量为零, ,求得满足求得满足 （1-131-13）的解，称为基对应的基本解）的解，称为基对应的基本解（basic basic solutionsolution）。）。n n基本可行解：基本可行解：满足（满足（1-141-14）的基本解）的基本解 称为基本可行解（称为基本可行解（basic feasible solutionbasic feasible solution ）；）；基本可行解所对应的基称为可行基基本可行解所对应的基称为可行基 （feasible basisfeasible basis）。）。二.解的性质在右图中设线

3、段长度与之比为 ，由此得o线性规划问题的几个定理定理1-4 线线性规规划问题问题 有可行解,必有基本 可行解；有最优优解,必有基本最优优解。定理定理1-1 1-1 线线线线性性规规规规划划问题问题问题问题 的可行域是凸集的可行域是凸集 。定理定理1-21-2 A A为线为线为线为线 性性规规规规划划问题问题问题问题 可行域的可行域的 极点的充要条件是的极点的充要条件是的A A正分量正分量对应对应对应对应 的系的系 数列向量数列向量线线线线性无关。（性无关。（证证证证明从略）。明从略）。 定理定理1-3A1-3A是可行域的极点的充要条件是它是可行域的极点的充要条件是它 为基本可行解。（证明从略。

4、）为基本可行解。（证明从略。）综上所述,我们在理论上得到了线性规划问题的以 下结论：v线线性规规划问题问题 的可行域是一凸集（包括有界凸 集和无界凸集）；线线性规规划问题问题 的每个基本可 行解对应对应 着可行域的一个极点（顶顶点）；若线线 性规规划问题问题 有最优优解,必在可行域的某一极点上 得到。由此可见见,我们们只需在基本可行解中寻寻求 最优优解。如何有效地寻寻求最优优解,这这就是下节节 要介绍绍的单纯单纯 形法。 1-5 单纯形法v一、单纯形法的基本思路如果线性规划问题存在最优解，一 定有一个基本可行解是最优解。因此单纯 形法迭代的基本思路是：先找出一个基本 可行解，判断其是否为最优解

5、，如为否， 则转换到相邻的基本可行解，并使目标函 数值不断增大，一直找到最优解为止。 1、确定初始基可行解 max (1-17)在约束条件（1-18）式的变量的系数矩阵中总 会存在一个单位矩阵，不妨设为(1-20)式中 称为基向量,同其对应的决 策变量 称为基变量,模型中的其 它变量 称为非基变量。在(1-18) 式中令所有非基变量等于零,即可找到一个 解X=( ， )T=(b1,bm,0,0)T 因有b0,故X满足约束(1-19),是一个基本可 行解记为 又称初始基本可行解。 2、从一个基本可行解转换为相邻的基本可行 解 设初始基本可行解中的前m个为基变量,即经一系列变换得3、最优性检验和解

6、的判别v（1-24）式中因 , 所以只要 ,就v有 。 通常简写为 或 ,v它是对线性规划问题的解进行最优性检验的标志 二、单纯形法的矩阵描述在线性规划问题的标准型： Max 中，不妨设 是一个可行基，则系数矩阵可分块为 （，）。对应于的基变量为， ，非基变量为 ， 。并令 ，其中 为基变量 的系数列向量，N为非基变量的系数列向量。于是原问题 可化为v即 对约 束方程两边同左乘以 ， 得 = ，并代入目标函数，得令非基变量 =0得= , 从而相应的基本可行解为 目标函数取值为 又由于 ,故有 将 及Z的表达式又可写成令 ， ， 则又有 += +第四步：重复第二、三两步，一直到计算结束为止 。三

7、、单纯形法的计算步骤根据上节中讲述的原理根据上节中讲述的原理, ,单纯形法的计算步骤如下单纯形法的计算步骤如下 ：第一步：求初始基本可行解第一步：求初始基本可行解, ,列出初始单纯形表。列出初始单纯形表。第二步：最优性检验。第二步：最优性检验。第三步：从一个基本可行解转换到相邻的目标函第三步：从一个基本可行解转换到相邻的目标函数值更大的基本可行解，列出新的单纯形表数值更大的基本可行解，列出新的单纯形表 。一、 大M法在上一节例1-9中，化为标准形式后约束 条件的系数矩阵中含有单位矩阵，以此 作初始基，使求初始基可行解和建立初 始单纯形表都十分方便。但时常化为标 准形后的约束条件的系数矩阵中不存

8、在 单位矩 例1-10 用单纯形法求解线性 规划问题 1-6 .初始可行基的求法 解 先将其化成标准形有 MaxMaxMax这种情况下，可以通过添加两列单位向量，使连同 约束条件中的向量构成单位矩阵。是人为添加上去的，它相当于在上述问题的约 束条件（1-34）中添加变量，约束条件(1-35)中添加变 量，变量相应称为人工变量。由于约束条件（1-34） （1-35）在添加人工变量前已是等式为使这些等式得 到满足，因此在最优解中人工变量取值必须为零。为 此，令目标函数中人工变量的系数为任意大的负值， 用“-M”代表。7p“-M”称为“罚因子”，即只要人工变量取值大于零，目标 函数就不可能实现最优。

9、因而添加人工变量后，例1-10 的数学模型的标准形式就变为max该模型中与 对应的变量 为基变量 ，令非基变量等于零，即得到初始基可行解,并列出初始单纯形表。在单纯形法迭代运算中，M可当 作一个数学符号一起参加运算。检验数中含M符号的项 ，当M的系数为正时，该检验数为正，当M的系数为负 时，该项检验数为负。例1-10添加人工变量后，用单纯形法求解的过程见下页 表1-8。最优解为：二、 两阶段法用大M法处理人工变量，在用手工计算求解时不会碰 到麻烦。但用电子计算机求解时，对M就只能在计算 机内输入一个机器最大字长的数字。如果线性规划问 题中的或 等参数值与这个代表M的数相对比较接 近，或远远小于

10、这个数字，由于计算机计算时取值上 的误差，有可能使计算结果发生错误。为了克服这个 困难，可以对添加人工变量后的线性规划问题分两个 阶段来计算，称为两阶段法。表1-8-30100-M-M0-M-M419111100000111-1-11-200003-3-2M4M10-M004130211-10313-21-10-110660403-3100-M-3+6M04M+103M-4M01-1/21入基出基原则v首先是检验数 即单纯形表中系数 矩阵的第 列 的价值系数 减去第 列元 素乘以对应行所在的基的价值系数的和的差。v当目标函数是求max时， 大者对应的列所在 的变量为入基变量，如果有几个检验数一

11、样大 ，且是最大者，取脚标小的变量为入基变量； 当目标函数是求min时， 小者为入基变量。v由于续表 -3 1 1 0 2/3 0 1/2 -1/2 1/6 3/20 3 0 1 1/3 0 0 0 1/3 90 0 0 0 0 1 -1/2 1/2 -1/2 -0 0 3 0 3/2 -M-3/2 -M+1/21 3/2 3/2 0 1 0 3/4 -3/4 1/4 0 0 0 0 0 1 -1/2 1/2 -1/20 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