运筹学基础及应用第五版.pptx

2024/8/11 周日1运筹学运筹学OPERATIONS RESEARCH2024/8/11 周日2第一章第一章 线性规划及单纯形法线性规划及单纯形法(Linear Programming,LP)n线性规划模型线性规划模型n图解法图解法n单纯形法原理单纯形法原理n单纯形法计算步骤单纯形法计算步骤n单纯形法的进一步讨论单纯形法的进一步讨论n数据包络分析数据包络分析2024/8/11 周日31 1 一般线性规划问题的数学模型一般线性规划问题的数学模型1.1 1.1 引例引例 例例1、生产计划问题、生产计划问题 能力能力 设备设备A 2 2 12 设备设备B 4 0 16 设备设备C 0 5 15 利润利润 2 3，各生产多少各生产多少,可获最大利润可获最大利润?2024/8/11 周日4 2x1+2x2 12 12 4x1 16 5x2 15 x1，x2 0注意模型特点注意模型特点 max Z=2x1+3x2解解:设产品设产品,产量分别为变量产量分别为变量x1，x22024/8/11 周日5线性规划模型特点线性规划模型特点n决策变量：向量决策变量：向量X=(x1 xn)T 决策人要考虑决策人要考虑和控制的因素，非负和控制的因素，非负n约束条件：关于约束条件：关于X的线性等式或不等式的线性等式或不等式n目标函数：目标函数：Z=(x1 xn)为关于为关于X 的线性函数，的线性函数，求求Z极大或极小极大或极小2024/8/11 周日61.2 线性规划问题的数学模型三个组成要素：三个组成要素：1.决策变量决策变量:是决策者为实现规划目标采取的是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。方案、措施，是问题中要确定的未知量。2.目标函数目标函数:指问题要达到的目的要求，表指问题要达到的目的要求，表示为决策变量的函数。示为决策变量的函数。3.约束条件约束条件:指决策变量取值时受到的各种可指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或用资源的限制，表示为含决策变量的等式或不等式。不等式。2024/8/11 周日7一般线性规划问题的数学模型：一般线性规划问题的数学模型：目标函数：目标函数：约束条件：约束条件：2024/8/11 周日8简写形式：简写形式：2024/8/11 周日9矩阵形式表示为：矩阵形式表示为：其中：其中：2024/8/11 周日101.3 线性规划问题的标准形式标准形式：标准形式：标准形式特点：标准形式特点：4.决策变量取值非负。决策变量取值非负。1.目标函数为求极大值；目标函数为求极大值；2.约束条件全为等式；约束条件全为等式；3.约束条件右端常数项全为非负；约束条件右端常数项全为非负；2024/8/11 周日11一般线性规划问题如何化为标准型：一般线性规划问题如何化为标准型：1.目标函数求极小值：目标函数求极小值：令：令：，即化为：，即化为：2024/8/11 周日122.约束条件为不等式：约束条件为不等式：（1）当约束条件为）当约束条件为“”时时如：如：可令：可令：，显然显然（2）当约束条件为）当约束条件为“”时时如：如：可令：可令：，显然显然 称为称为松弛变量。松弛变量。称为称为剩余变量剩余变量。2024/8/11 周日13松弛变量和剩余变量统称为松弛变量松弛变量和剩余变量统称为松弛变量（3）目标函数中松弛变量的系数）目标函数中松弛变量的系数 由于松弛变量和剩余变量分别表示未被充分利由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利用的资源以及超用的资源，都没有转化为价值和利润，因此润，因此在目标函数中系数为零在目标函数中系数为零。2024/8/11 周日143.取值无约束的变量取值无约束的变量 如果变量如果变量 x 代表某产品当年计划数与上代表某产品当年计划数与上一年计划数之差，显然一年计划数之差，显然 x 的取值可能是正也的取值可能是正也可能是负，这时可令：可能是负，这时可令：其中：其中：令令4.变量变量 xj0，显然，显然2024/8/11 周日15例例.将下述线性规划模型化为标准型将下述线性规划模型化为标准型2024/8/11 周日16解：解：令令得标准形式为：得标准形式为：2024/8/11 周日17求解线性规划问题：求解线性规划问题：就是从满足约束方程组和约束不等式的决策变量取就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。值中，找出使得目标函数达到最大的值。1.4 线性规划问题的解的概念2024/8/11 周日18 可行解：可行解：满足约束条件的解称为满足约束条件的解称为可行解可行解，可行解的集，可行解的集合称为合称为可行域可行域。最优解：最优解：使目标函数达到最大值的可行解。使目标函数达到最大值的可行解。基基：约束方程组的一个满秩子矩阵称为规划问题的一：约束方程组的一个满秩子矩阵称为规划问题的一个个基基，基中的每一个列向量称为，基中的每一个列向量称为基向量基向量，与基向量对应，与基向量对应的变量称为的变量称为基变量基变量，其他变量称为，其他变量称为非基变量非基变量。基解：基解：在约束方程组中，令所有非基变量为在约束方程组中，令所有非基变量为0，可以，可以解出基变量的唯一解，这组解与非基变量的解出基变量的唯一解，这组解与非基变量的0共同构成共同构成基解基解。基可行解：基可行解：满足变量非负的基解称为满足变量非负的基解称为基可行解基可行解可行基：可行基：对应于基可行解的基称为对应于基可行解的基称为可行基可行基2024/8/11 周日19例：考察下述线性规划问题：例：考察下述线性规划问题：2024/8/11 周日20（1）可行解，如可行解，如或或满足约束条件，所以是可行解。满足约束条件，所以是可行解。（2）基基系数矩阵系数矩阵A：其中其中 或或 都构成基。而都构成基。而 不构成基。不构成基。2024/8/11 周日21（3）基向量、基变量）基向量、基变量是对应于基是对应于基的三个基向量，而的三个基向量，而是对应于这三个基向量的基变量。是对应于这三个基向量的基变量。（4）基解、基可行解、可行基）基解、基可行解、可行基是对应于基是对应于基的一个基解、基可行解。的一个基解、基可行解。是对应于基是对应于基的一个基解、基可行解。的一个基解、基可行解。均是可行基均是可行基。练习：练习：P14，例例42024/8/11 周日22 为了便于建立为了便于建立 n 维空间中线性规划问题的概念及维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。先介绍图解法。求解下述线性规划问题：求解下述线性规划问题：2 2 线性规划问题的图解法线性规划问题的图解法2024/8/11 周日23画出线性规划问题的可行域：画出线性规划问题的可行域：目标函数等值线2024/8/11 周日241、可行域：、可行域：约束条件所围成的区域约束条件所围成的区域。2、基可行解：、基可行解：对应对应可行域的顶点。可行域的顶点。3、目标函数等值线：、目标函数等值线：4、目标函数最优值、目标函数最优值:最大截距所对应的最大截距所对应的 。目标函数等值线有无数条，且平行。（观察规律目标函数等值线有无数条，且平行。（观察规律)2024/8/11 周日25解的几种情况解的几种情况：(2)2)无穷多最优解无穷多最优解(1)唯一最优解唯一最优解若目标函数改为：若目标函数改为：约束条件不变，则约束条件不变，则:目标函数等值线此时，线段此时，线段上所有点都是最优上所有点都是最优值点。值点。2024/8/11 周日26解的几种情况解的几种情况：(4)4)无界解无界解(3)无可行解：无可行解：当可行域为空集时，无可行解。当可行域为空集时，无可行解。若目标函数不变，将若目标函数不变，将约束条件约束条件1和和3去掉，则可行域及解的去掉，则可行域及解的情况见下图。情况见下图。目标函数等值线此时，目标函数等此时，目标函数等值线可以向上无穷值线可以向上无穷远处平移，远处平移，Z值无值无界。界。2024/8/11 周日27几点说明：几点说明：1、图解法只能用来求解含有两个决策变量的线性规划问、图解法只能用来求解含有两个决策变量的线性规划问 题。题。2、若最优解存在，则必在可行域的某个顶点处取得。、若最优解存在，则必在可行域的某个顶点处取得。3、线性规划问题的解可能是：唯一最优解、无穷多最优、线性规划问题的解可能是：唯一最优解、无穷多最优解、无最优解、无界解。解、无最优解、无界解。2024/8/11 周日2833单纯形法原理单纯形法原理凸集：凸集：如果集合如果集合 C 中任意两个点中任意两个点 ，其连线上的所有点，其连线上的所有点也都是集合也都是集合C 中的点。中的点。上图中（上图中（1）（）（2）是凸集，（）是凸集，（3）（）（4）不是凸集）不是凸集顶点：顶点：如果对于凸集如果对于凸集 C 中的点中的点 X，不存在，不存在C 中的任意其它两中的任意其它两个不同的点个不同的点 ，使得，使得 X 在它们的连线上，这时称在它们的连线上，这时称 X 为凸为凸集的顶点。集的顶点。3.1 预备知识 2024/8/11 周日293.2 线性规划问题基本定理定理定理1:1:若线性规划问题存在可行解，则问题的可行域是凸集。若线性规划问题存在可行解，则问题的可行域是凸集。证明证明:设设 是线性规划的任意两个可行解，则是线性规划的任意两个可行解，则于是对于任意的于是对于任意的 ，设，设 ，则，则 所以所以 也是问题的可行解，即可行域是凸集。也是问题的可行解，即可行域是凸集。2024/8/11 周日30引理引理:线性规划问题的可行解线性规划问题的可行解 X为基可行解的充要条件是为基可行解的充要条件是X的的正分量所对应的系数列向量线性无关。正分量所对应的系数列向量线性无关。证明证明:设设 （1 1）必要性显然。必要性显然。（2 2）设设 A A 的秩为的秩为m m。可行解。可行解 X X 的前的前 k k 个分量为正，且它们对应个分量为正，且它们对应的系数列向量的系数列向量 线性无关，则线性无关，则 。当当 时，时，恰好构成一组基，而恰好构成一组基，而 就是这组基对应的基可行解。就是这组基对应的基可行解。当当 时，在时，在 基础上从其余列向量中可以找出基础上从其余列向量中可以找出个线性无关的向量，恰好构成一组基，而个线性无关的向量，恰好构成一组基，而 X 就是这组基对应的基可行解。就是这组基对应的基可行解。2024/8/11 周日31定理定理2:线性规划问题的基可行解线性规划问题的基可行解 X 对应线性规划问题可行对应线性规划问题可行 域（凸集）的顶点。域（凸集）的顶点。证明证明:问题即是要证明问题即是要证明:X是基可行解是基可行解 X是可行域顶点，也即要证明是可行域顶点，也即要证明其逆否命题：其逆否命题：X不是基可行解不是基可行解 X不是可行域顶点不是可行域顶点。（1 1）X不是基可行解不是基可行解 X不是可行域顶点。不是可行域顶点。假设假设X是可行解，但不是基可行解，是可行解，但不是基可行解，X 的前的前 k 个分量为正个分量为正,其余分量为其余分量为0，则有则有又又X不是基可行解，所以由引理知，正分量对应的列向量不是基可行解，所以由引理知，正分量对应的列向量线性相关。即存在一组不全为零的数线性相关。即存在一组不全为零的数 ，使得，使得2024/8/11 周日32用非零常数用非零常数 乘以上式得：乘以上式得：（1）+（3）得：）得：（1）-（3）得：）得：令令选择合适的选择合适的 ，使得所有的，使得所有的于是于是 均是可行解，并且均是可行解，并且 ，所以，所以 X 不是可行不是可行域顶点。域顶点。2024/8/11 周日33（2）X不是可行域顶点不是可行域顶点 X不是基可行解不是基可行解。设设 不是可行域的顶点，因而可以找到可行域内不是可行域的顶点，因而可以找到可行域内另两个不同的点另两个不同的点 ，使得使得 ，用分量表示即为：用分量表示即为：易知，当易知，当 时，必有时，必有 所以所以所以所以于是（于是（1）-（2）得）得而而 不全为零，于是知不全为零，于是知 线性相关，线性相关，X不是基可行解。不是基可行解。2024/8/11 周日34定理定理3:若线性规划问题有最优解，一定存在一个基可行解是若线性规划问题有最优解，一定存在一个基可行解是 最优解。最优解。引理：引理：有界有界 凸集中的任何一点均可表示成顶点的凸组合。凸集中的任何一点均可表示成顶点的凸组合。证明证明:假设假设 是可行域顶点，是可行域顶点，不是可行域顶点不是可行域顶点，且目标函，且目标函数在数在 处达到最优，即处达到最优，即 。由引理知：由引理知：可表示为可表示为 的凸组合，即的凸组合，即因此因此假设假设 是所有是所有 中最大者，则中最大者，则2024/8/11 周日35而而 是目标函数的最大值，所以是目标函数的最大值，所以 也是最大值，也是最大值，也即，目标函数在可行域的某个顶点达到了最优。也即，目标函数在可行域的某个顶点达到了最优。从上述三个定理可以看出，要求线性规划问题的最从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点对应的目优解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我们所要求的最优解。标函数值即可，最大的就是我们所要求的最优解。2024/8/11 周日363.3 确定初始基可行解寻求最优解的思路：寻求最优解的思路：线性规划问题的最优解一定会在线性规划问题的最优解一定会在基可行解中取得，我们先找到一个初始基可行解。然基可行解中取得，我们先找到一个初始基可行解。然后设法转换到另一个基可行解，并使得目标函数值不后设法转换到另一个基可行解，并使得目标函数值不断增大，直到找到最优解为止。断增大，直到找到最优解为止。设给定线性规划问题：设给定线性规划问题：2024/8/11 周日37因此约束方程组的系数矩阵为：因此约束方程组的系数矩阵为：添加松弛变量得其标准形为：添加松弛变量得其标准形为：2024/8/11 周日38由于该矩阵含有一个单位子矩阵，因此，这个单位阵就是一组由于该矩阵含有一个单位子矩阵，因此，这个单位阵就是一组基，就可以求出一个基可行解：基，就可以求出一个基可行解：说明：说明：如果约束条件不全是如果约束条件不全是 形式，如含所有形式，如含所有 形式，形式，则无法找到一个单位阵做为一组基，这时需要添加人工变量。则无法找到一个单位阵做为一组基，这时需要添加人工变量。后面的内容介绍。后面的内容介绍。称其为初始基可行解。称其为初始基可行解。2024/8/11 周日393.4 从初始基可行解转换为另一个基 可行解 思路：思路：对初始基可行解的系数矩阵进行初等行变换，构造对初始基可行解的系数矩阵进行初等行变换，构造出一个新的单位矩阵，其各列所对应的变量即为一组新的基出一个新的单位矩阵，其各列所对应的变量即为一组新的基变量，求出其数值，就是一个新的基可行解。变量，求出其数值，就是一个新的基可行解。设有初始基可行解设有初始基可行解 ，并可设前，并可设前m 个个 分量非零，即分量非零，即 ，于是，于是2024/8/11 周日40 由构造初始可行基的方法知前由构造初始可行基的方法知前m 个基向量恰好是一个单位个基向量恰好是一个单位阵，所以约束方程组的增广矩阵为阵，所以约束方程组的增广矩阵为由于由于任意系数列向量任意系数列向量均可由均可由基向量组基向量组线性表示，则非基向量线性表示，则非基向量中的中的 用用基向量组基向量组线性表示为：线性表示为：2024/8/11 周日41设有设有 ，则，则（1）+（2）得：）得：由此式可知，我们找到了满足约束方程组的另一个解由此式可知，我们找到了满足约束方程组的另一个解 ，要使其成为要使其成为可行解可行解，只要对所有，只要对所有i=1,2,m ，下式成立，下式成立要使其成为要使其成为基可行解基可行解，上面，上面m个式中至少有一个取个式中至少有一个取零。零。（基可行解中非零分量的个数不超过（基可行解中非零分量的个数不超过m 个。）个。）（与（与 比较）比较）2024/8/11 周日42只要取只要取于是前于是前m个分量中的第个分量中的第l个变为零，其余非负，第个变为零，其余非负，第j个分量为个分量为正，于是非零分量的个数正，于是非零分量的个数 ，并可证得，并可证得线性无关，所以线性无关，所以 是新的基可行解。是新的基可行解。2024/8/11 周日433.4 最优性检验和解的判别设有基可行解设有基可行解比较两者对应的目标函数值，哪一个更优？比较两者对应的目标函数值，哪一个更优？2024/8/11 周日442）若对所有的）若对所有的 ，则，则 ，就是最优解。就是最优解。是判断是否达到最优解的标准，是判断是否达到最优解的标准，称为称为检验数。检验数。1）当）当 时，时，目标函数值得到，目标函数值得到了改进，了改进，不是最优解，需要继续迭代。不是最优解，需要继续迭代。易知易知2024/8/11 周日451.当所有当所有 时，现有顶点对应的基可行解即为最优时，现有顶点对应的基可行解即为最优解。解。2.当所有当所有 时，又对某个非基变量时，又对某个非基变量 有有 则该线性规划问题有无穷多最优解。则该线性规划问题有无穷多最优解。3.如果存在某个如果存在某个 ，又，又 向量的所有分量向量的所有分量 ，对任意对任意 ，恒有，恒有 ，则存在无界，则存在无界解。解。结论结论2024/8/11 周日464 单纯形法的计算步骤单纯形法的计算步骤 Max(min)Z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b b1 1a21x1+a22x2+a2nxn=b b2 2 am1x1+am2x2+amnxn=b bm mxj j 0(0(j=1,n)设有线性规划问题：设有线性规划问题：2024/8/11 周日47(1)(1)找到初始可行基，建立初始单纯形表找到初始可行基，建立初始单纯形表.(4)(4)重复重复二、三两步，直至找到最优解二、三两步，直至找到最优解。4 单纯形法的计算步骤单纯形法的计算步骤(2)(2)进行最优性检验。进行最优性检验。计算检验数，若所有计算检验数，若所有 0 则得最优解，结束则得最优解，结束.否则转下步否则转下步.若某若某 0 0 而而 0 0，则最优解无界，结束，则最优解无界，结束.否则转下步否则转下步.(3)(3)从一个可行解转换到另一个目标函数值更大的从一个可行解转换到另一个目标函数值更大的基可行解。基可行解。由最大增加原则确定进基变量；由最小比值原则选择出基变由最大增加原则确定进基变量；由最小比值原则选择出基变量；以量；以 为主元素进行换基迭代。为主元素进行换基迭代。2024/8/11 周日48(1)(1)找到初始可行基，建立初始单纯形表找到初始可行基，建立初始单纯形表.00是初始基。是初始基。2024/8/11 周日49(2)(2)进行最优性检验进行最优性检验计算检验数，若所有计算检验数，若所有 0 则得最优解，结束则得最优解，结束.否则转下步否则转下步.若某若某 0 0 而而 0 0，则最优解无界，结束，则最优解无界，结束.否则转下步否则转下步.检验数的计算方法：检验数的计算方法：基变量的检验数一定为基变量的检验数一定为0。判断是否达到最优时，只要考虑。判断是否达到最优时，只要考虑非基变量检验数。非基变量检验数。2024/8/11 周日50(3)(3)从一个可行解转换到另一个目标函数值更大的从一个可行解转换到另一个目标函数值更大的基可行解。基可行解。由最小比值原则选择出基变量；由最小比值原则选择出基变量；进基变量由最大增加原则确定进基变量：由最大增加原则确定进基变量：当某些非基变量的检验数当某些非基变量的检验数 时，为使目标函数值时，为使目标函数值增加地更快，一般选择增加地更快，一般选择正检验数中最大者正检验数中最大者对应的非基变对应的非基变量进基量进基 ，成为新的基变量。，成为新的基变量。为确保新的基可行解的非零分量非负，按下述规则求得最小为确保新的基可行解的非零分量非负，按下述规则求得最小比值比值 ，其所对应的原基变量中的，其所对应的原基变量中的 出基。出基。于是，新的一组基是：于是，新的一组基是：2024/8/11 周日51以以 为主元素进行换基迭代：为主元素进行换基迭代：即利用初等行变换将进基变量即利用初等行变换将进基变量 所在的系数列变为单位所在的系数列变为单位列向量，而列向量，而 变为变为1 1。这样原来基矩阵中的。这样原来基矩阵中的 就不再就不再是单位向量，取而代之的是是单位向量，取而代之的是 ，这样就找到了一组新的，这样就找到了一组新的基。基。(4)(4)重复重复二、三两步，直至找到最优解二、三两步，直至找到最优解。说明：说明：若目标函数是求最小，可以不必将其转变为求若目标函数是求最小，可以不必将其转变为求 最大，但在使用单纯形法求解时，确定进基变最大，但在使用单纯形法求解时，确定进基变 量，应找量，应找负检验数中最小者，负检验数中最小者，并应以并应以检验数检验数 全部为正全部为正作为判别最优的条件。作为判别最优的条件。2024/8/11 周日52 maxZ=3x1+5 x2+0 x3+0 x4+0 x5 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5 =36 x1，x2，x3，x4，x5 0解解 将将模型标准化模型标准化例例 maxZ=3x1+5x2 x1 8 2x2 12 3x1+4x2 36 x1，x2 02024/8/11 周日53Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9作出单纯形表，进行迭代作出单纯形表，进行迭代检验数最大比值最小2024/8/11 周日54检验数检验数 j81010060101/2012300-21x3x2x505030300-5/208-4Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=92024/8/11 周日55Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010060101/2012300-21x3x2x505030300-5/208-4检验数检验数 j40012/3-1/360101/204100-2/31/3x3x2x105342000-1/2-1最优解最优解 :X*=(4,6,4,0,0)T，Z*=422024/8/11 周日56n特殊情况：（1）出现两个或两个以上相同的最大出现两个或两个以上相同的最大 ，此，此时可任选一个时可任选一个 所对应的变量作为进基变量。所对应的变量作为进基变量。（2）利用利用 规则决定出基变量时，出现两个或规则决定出基变量时，出现两个或两个以上的最小比值两个以上的最小比值 ，则迭代后，会出现一，则迭代后，会出现一个或几个基变量等于零的情况，我们称此为退化个或几个基变量等于零的情况，我们称此为退化现象。进而可能会出现迭代过程的循环，致使永现象。进而可能会出现迭代过程的循环，致使永远达不到最优解。远达不到最优解。出现退化现象时，可考虑采用出现退化现象时，可考虑采用“勃兰特勃兰特”规则规则决决定进基变量和出基变量的选择。定进基变量和出基变量的选择。2024/8/11 周日575.1 5.1 人工变量人工变量 n用单纯形法解题时，需要有一个单位阵作为初用单纯形法解题时，需要有一个单位阵作为初始基。始基。n当约束条件都是当约束条件都是“”时，加入松弛变量就形时，加入松弛变量就形成了初始基。成了初始基。n但实际存在但实际存在“”或或“”型的约束，没有现型的约束，没有现成的单位矩阵。成的单位矩阵。n采用人造基的办法：添加采用人造基的办法：添加人工变量人工变量，构造单位，构造单位矩阵矩阵5 5 单纯形法的进一步讨论单纯形法的进一步讨论 2024/8/11 周日58 人工单位矩阵的构造方法人工单位矩阵的构造方法 在在“”的不等式约束中减去一个剩余变量后可变为的不等式约束中减去一个剩余变量后可变为等式约束，但此剩余变量的系数是（等式约束，但此剩余变量的系数是（-1-1），所以再加入），所以再加入一个人工变量，其系数是（一个人工变量，其系数是（+1+1），因而在系数矩阵中可），因而在系数矩阵中可得到一个相应的单位向量，以便构成初始单位阵，即初得到一个相应的单位向量，以便构成初始单位阵，即初始基矩阵。始基矩阵。在原本就是在原本就是“=”的约束中可直接添加一个人工变量，的约束中可直接添加一个人工变量，以便得到初始基矩阵。以便得到初始基矩阵。注意：注意：人工变量是在等式中人为加进的，只有它等于人工变量是在等式中人为加进的，只有它等于0 0时，时，约束条件才是它本来的意义。约束条件才是它本来的意义。求解带人工变量的线性规划有两种方法：求解带人工变量的线性规划有两种方法：大大M M法法 两阶段法两阶段法2024/8/11 周日595.2 5.2 大大M M法法 没有单位矩阵，不符合构造初始基的条件，需加入人工变没有单位矩阵，不符合构造初始基的条件，需加入人工变量量 。人工变量最终必须等于人工变量最终必须等于0 0才能保持原问题性质不变。为保证才能保持原问题性质不变。为保证人工变量为人工变量为0 0，在目标函数中令其系数为（，在目标函数中令其系数为（-M-M）。）。（求最小值问题中，人工变量系数取（求最小值问题中，人工变量系数取M M）M M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解就没有可行解，当然亦无最优解。2024/8/11 周日60例例解线性规划解线性规划解解化为标准型化为标准型此时无单位矩阵作为初始基。此时无单位矩阵作为初始基。2024/8/11 周日61添加人工变量，构造初始基：添加人工变量，构造初始基：（求最小值问题中，人工变量系数取（求最小值问题中，人工变量系数取M）2024/8/11 周日62-30100-M-Mx1x2x3x4x5x6x71111000-21-10-1100310001初始单纯形表：初始单纯形表：CCBXBb0 x44-Mx61-Mx79-3-2M4M10-M0041330211-10-21-10-11060403-311-10 x430 x21-Mx76-3+6M01+4M03M-3M02024/8/11 周日63-30100-M-Mx1x2x3x4x5x6x7CCBXBb00303/2-M-3/2-M+1/2-33/20001-1/21/2-1/2011/30001/3102/301/2-1/21/60 x400 x23-3x11-3/2000-3/4-M+3/4-M-1/40 x400 x25/21x33/20001-1/21/2-1/2-1/2100-1/41/41/43/20103/4-3/41/42024/8/11 周日64此时人工变量全部出基，并已达最优条件。此时人工变量全部出基，并已达最优条件。最优解为最优解为，最优值为，最优值为注意：注意：计算机上使用大计算机上使用大M法时，需要用机器最大字长的数字法时，需要用机器最大字长的数字代替代替M，但当某些系数与之较接近时，还是可能会出错。，但当某些系数与之较接近时，还是可能会出错。另外一种求解带人工变量的线性规划问题的方法不会出现这种另外一种求解带人工变量的线性规划问题的方法不会出现这种问题问题-两阶段法两阶段法。2024/8/11 周日65maxZ=3x1-x2-2 x3 3x1+2 x2-3 x3=6 x1 -2 x2+x3=4 x1,x2,x3 0S.t.例例解线性规划解线性规划 maxZ=3x1 -x2 -2 x3-M x4-M x5 3x1+2 x2-3 x3 +x4 =6 x1 -2 x2+x3 +x5=4 x1,x2,x3,x4,x5 0解解按大按大M法构造人造基，引入人工变量法构造人造基，引入人工变量x4,x5 的辅助问题如下：的辅助问题如下：2024/8/11 周日66作出单纯形表，进行迭代作出单纯形表，进行迭代Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53-1-2-M-M632-31041-21013+4M-1-2-2M00 x4x5-M-M24检验数检验数 j212/3-11/3020-8/32-1/310-3-8M/3 1+2M-1-4M/30 x1x53-M2024/8/11 周日67检验数检验数 j212/3-11/3020-8/32-1/310-3-8M/3 1+2M-1-4M/30 x1x53-M-1检验数检验数 j31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-2最优解最优解 :X*=(3,0,1)T，Z*=72024/8/11 周日685.3 5.3 两阶段法两阶段法 第一阶段：第一阶段：构造目标函数只含人工变量的线构造目标函数只含人工变量的线 性规划问题，求解后判断原线性性规划问题，求解后判断原线性 规划问题是否有基本可行解，若规划问题是否有基本可行解，若 有，则进行第二阶段有，则进行第二阶段 ；第二阶段：第二阶段：将第一阶段的最终单纯形表所对将第一阶段的最终单纯形表所对 应的解，去掉人工变量，作为第应的解，去掉人工变量，作为第 二阶段的初始单纯形表的初始基二阶段的初始单纯形表的初始基 可行解，进行单纯形法的迭代。可行解，进行单纯形法的迭代。2024/8/11 周日69 解解（1）化标准型、并添加人工变量得：化标准型、并添加人工变量得：Min f=2x1+3 x2 （此处未将目标变为（此处未将目标变为MAX）s.t.x1+x2 x3 +x6 =350 x1 -x4 +x7 =125 2 x1+x2 +x5 =600 x1 ,x2,x3,x4,x5,x6,x7 0 例：例：目标函数：目标函数：Min f=2x1+3 x2 约束条件约束条件：s.t.x1+x2 350 x1 125 2 x1+x2 600 x1 ,x2 0 2024/8/11 周日70（2）构造第一阶段问题：）构造第一阶段问题：Min z=x6+x7 (Max z=-x6-x7)s.t.x1+x2 x3 +x6 =350 x1 -x4 +x7 =125 2 x1+x2 +x5 =600 x1 ,x2,x3,x4,x5,x6,x7 0 说明：说明：原问题目标函数无论是求原问题目标函数无论是求MAXMAX还是求还是求MINMIN，构造的，构造的 第一阶段问题目标函数都是第一阶段问题目标函数都是求最小求最小MINMIN。2024/8/11 周日71求解第一阶段问题：求解第一阶段问题：2024/8/11 周日72此时所得可行解目标函数值为此时所得可行解目标函数值为0 0，故原规划问题有基可行，故原规划问题有基可行解。转入第二步。解。转入第二步。2024/8/11 周日73（3）去掉人工变量，得到第二阶段的单纯形表，在此）去掉人工变量，得到第二阶段的单纯形表，在此 基础上继续求解。基础上继续求解。最优解为：最优解为：2024/8/11 周日745.4 5.4 关于解的不同情况的判别关于解的不同情况的判别 1 1、无穷多最优解、无穷多最优解例：例：解：解：将问题化为标准型：将问题化为标准型：2024/8/11 周日752024/8/11 周日76从上表中可知，已达最优解，为从上表中可知，已达最优解，为 ，而而 ，若将，若将 选为进基变量迭代后，可得另一最优选为进基变量迭代后，可得另一最优解解 。上述两最优解分别对应两个顶点，而两点连线上的点均上述两最优解分别对应两个顶点，而两点连线上的点均是最优解，故有无穷多最优解。是最优解，故有无穷多最优解。判别无穷多最优解的方法：判别无穷多最优解的方法：单纯形表的检验数行已达最单纯形表的检验数行已达最有性条件（全部小于或等于零），且有一个非基变量的有性条件（全部小于或等于零），且有一个非基变量的检验数为零，此时有无穷多最优解。检验数为零，此时有无穷多最优解。2024/8/11 周日77 2 2、无可行解、无可行解 例例 用单纯形表求解下列线性规划问题用单纯形表求解下列线性规划问题解：化为标准型：解：化为标准型：2024/8/11 周日78基变基变量量CB20 30 0 0 0 -Mbx1 x2 s1 s2 s3 a1s1s2a100-M3 10 1 0 0 01 0 0 1 0 01 1 0 0 -1 115030401540cj-zj20+M 30+M 0 0 -M 0-40M单纯形表求解线性规划问题单纯形表求解线性规划问题2024/8/11 周日791x2s2a1300-M3/10 1 1/10 0 0 0 1 0 0 1 0 07/10 0 -1/10 0 -1 11530255030250/7cj-zj11+7/10M 0 -3-M/10 0 -M 0 2x2x1a13020-M0 1 1/10 -3/10 0 01 0 0 1 0 00 0 -1/10 -7/10 -1 1 6304cj-zj0 0 -3-M/10 -11-7M/10 -M 0迭迭代代次次数数基基变变量量CBx1 x2 s1 s2 s3 a1b比值比值20 30 0 0 0 -M单纯形法的最终表里单纯形法的最终表里有人工变量大于零有人工变量大于零，则此线性规划，则此线性规划无可行解。无可行解。2024/8/11 周日80 3 3、无界解、无界解例例 用单纯形表求解下面线性规划问题。用单纯形表求解下面线性规划问题。解解2024/8/11 周日81 迭迭代代次次数数基基变变量量CBx1 x2 s1 s2b比值比值1 1 0 00s1s2001 -1 1 0-3 2 0 1161cj-zj1 1 0 001x1s2101 -1 1 0 0 -1 3 119cj-zj0 2 -1 01此时此时 的检验数仍为正，但系数列全为负，此时可的检验数仍为正，但系数列全为负，此时可判断这个线性规划问题是无界的，即目标函数值可以判断这个线性规划问题是无界的，即目标函数值可以取得无限大。取得无限大。2024/8/11 周日82 事实上，此从事实上，此从1 1次迭代的单纯形表中，得到约束方程：次迭代的单纯形表中，得到约束方程：移项可得：移项可得：由此可知，目标由此可知，目标函数可以任意大，函数可以任意大，即无界。即无界。2024/8/11 周日83练习：用大M法求解下列线性规划问题1、2、2024/8/11 周日84解1：将模型化为标准型得：建立单纯形表并计算如下2024/8/11 周日85显然，检验数已全部非正，已达最优解，但非基变量显然，检验数已全部非正，已达最优解，但非基变量X X2 2的的检验数为检验数为0 0，故知此问题有无穷多最优解。，故知此问题有无穷多最优解。2024/8/11 周日86解2：将模型化为标准型得：建立单纯形表并计算如下2024/8/11 周日872024/8/11 周日88最优解为（4，4）2024/8/11 周日89小结小结 表格单纯形表的使用表格单纯形表的使用（1 1）化线性规划模型为标准型，建立初始单）化线性规划模型为标准型，建立初始单纯形表。纯形表。（2 2）根据单纯形表按照最大增加原则选择进）根据单纯形表按照最大增加原则选择进基变量；基变量；（3 3）按照最小比值原则选择换出变量；）按照最小比值原则选择换出变量；（4 4）实施矩阵的初等变换进行换基迭代；）实施矩阵的初等变换进行换基迭代；（5 5）建立新的单纯形表；）建立