第二章 线性规划 山大刁在筠 运筹学讲义.doc

第二章 线性规划教学重点：线性规划可行区域的几何结构，基本可行解及可行区域的基本定理，单纯形方法，两阶段法，对偶和对偶理论，灵敏度分析。教学难点：线性规划可行区域的几何结构，基本可行解及可行区域的基本定理，单纯形方法，两阶段法，对偶性，灵敏度分析。教学课时：24学时主要教学环节的组织：首先通过各种形式的例子归纳出线性数学规划的一般形式，然后在详细讲解主要内容的基础上，尽可能以图形和例题的形式给以形象的说明，使学生对知识点有更直观、具体的认识。再通过大量习题巩固知识，也可以应用软件包解决一些实际问题。第一节 线性规划问题教学重点：线性规划问题的实例，线性规划的一般形式、规范形式和标准形式教学难点：线性规划一般形式转换成标准形式。教学课时：2学时主要教学环节的组织：首先通过几个实例总结出线性规划问题的一般形式，再介绍如何将一般形式转换成标准形式。1、线性规划问题举例生产计划问题某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的生产计划单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000单位产品的利润（千元）354可控因素(所求变量)：设每天生产3种产品的数量分别为.目标：使得每天的生产利润最大，就是使得利润函数： 达到最大.受制条件：每天原料的需求量不超过可用量：原料： 原料：原料：蕴含约束：产量为非负数模型 s.t. 运输问题一个制造厂要把若干单位的产品从两个仓库发送到零售点，仓库 能供应的产品数量为，零售点 所需的产品的数量为。假设供给总量和需求总量相等，且已知从仓库 运一个单位产品往的运价为。问应如何组织运输才能使总运费最小？求解设表示从仓库 运往零售点 的产品数量。模型：min s.t. 2、线性规划模型为待定的决策变量，为价值向量，为价值系数，为右端向量，矩阵为系数矩阵线性规划模型的概念可行解（或可行点）：满足所有约束条件的向量可行集（或可行域）：所有的可行解的全体最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体称为最优解集合最优值：最优解的目标函数值线性规划解的情况：无解或不可行 无界 但目标函数在可行域上无界有最优解 且目标函数在D上有有限的现象规划模型的规范形式和标准形式：规范形式：标准形式：形式转换一般形式转换成规范式：等式化成不等式： 自由变量化成非负变量：令自由变量，其中为非负变量 或 目标函数的最大问题向最小问题的转换例：将下述问题转换成标准形式：解：第二节 可行域与基本可行解教学重点：线性规划问题的图解法，可行区域的几何结构和线性规划基本定理。教学难点：线性规划的基本定理。教学课时：4学时主要教学环节的组织：首先通过图解法求出两个变量时可行区域的结构和最有点的位置，再进行一般情况下可行区域的结构进行讨论，得到线性规划的基本定理。1、图解法对于只有两个变量的线性规划问题可以用图解法求解：变量用直角坐标系中的点表示，约束条件用坐标系中的半空间或直线的交表示，可行区域是一个凸多面体，目标函数用一组等值线表示，沿着增加或减少的方向移动，与可行域最后的交点就是最优解。例1、最优解（1，4） 例2、若将例2.2.1中的目标函数改为求的最小值当目标函数改变后，等值线的方向会发生改变，如果等值线与某个约束对应的函数直线平行，则该函数值线上的所有可行解都是最优解最优解（1，4） 目标函数值可能出现的情况：1、可行域是空集；2、可行域无界无最优解；3、最优解存在且唯一，则一定在顶点上达到；4、最优解存在且不唯一，一定存在顶点是最优解。从图解法的几何直观易得：线性规划的可行域是若干个半平面的交集，它形成了一个有界或无界的凸多边形。对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。2、可行区域的结构定义2.2.1：设是维欧氏空间的点集，若对任意的和任意都有就称是一个凸集。定理2.2.1：线性规划的可行域是凸集证明：略。定理2.2.2：任意多个凸集的交还是凸集定义2.2.2：超平面 半空间 ；定义2.2.3：多面凸集 定义2.2.4：设 为凸集，如果对任意和，都有,则称x为S的顶点。基本可行解令，其中为A的一个满秩子方阵，=(,)。 分块 左乘 即 =0 定义2.2.5：设是秩为的约束矩阵的一个 阶满秩子方阵，则称为一个基（或基阵）；中 个线性无关的列向量称为基向量，变量 中与之对应的 个分量称为基变量，其余的变量为非基变量，令所有的非基变量取值为0，得到的解称为相应于的基本解。当则称基本解为基本可行解，这时对应的基阵为可行基。如果则称该基可行解为非退化的，如果一个线性规划的所有基可行解都是非退化的则称该规划为非退化的。定理2.2.3 可行解 是基本可行解的充要条件是它的正分量所对应的矩阵中列向量线性无关。证明：不妨设.若是基本可行解，则取正值的变量对应的列向量，为基向量，故线性无关.反之，若线性无关，则有.若，则有为基.为基可行解；若，则可从其余个列向量中再挑选列向量与组成基，易知，为基可行解.定理2.2.4 是基本可行解的充要条件是 是可行域 的顶点。定理2.2.5 一个标准的LP问题如果有可行解，则至少有一个基本可行解证明：设.是任意一个可行解，则有.不妨设；后个向量为0.若 线性无关，则由定理2.2.3知是基本可行解；否则存在不全为零的，使得，补充得，满足.定理2.2.6 一个标准的LP问题如果有有限的最优值，则一定存在一个基本可行解是最优解。证明：设是一个最优解，如果是基本可行解，则问题得证；否则按定理2.2.5的证明可得到和，由和知，故有.按照定理2.2.5的证明方法迭代，最终可得到基本可行解，满足.第三节 单纯型方法教学重点：单纯形算法和单纯形表。教学难点：单纯形算法，单纯形表。教学课时：4学时主要教学环节的组织：首先给出单纯形算法，然后给出单纯形算法的一种实现手段，单纯形表。1、单纯型方法考虑标准形式的线性规划问题其中，并且假定且可行域，系数矩阵是行满秩的，即。给定一个非退化的基本可行解，对应的可行基为，则等式约束AX=b可以变为： -典式或 此时令，则. 所以.目标函数令，则规划等价于 定理2.3.1（最优性准则）如果，则基可行解为原问题的最优解。证：设为原问题的任一可行解。由于，而，所以.从而.定理2.3.2 如果向量的第个分量，而向量，则原问题无界。证明：令，其中是第个分量为1，其余分量为0的维向量.因为，所以有，而对于充分大的正数，观察向量，此时有它所对应的目标函数值为由于，而可任意的大，故原问题目标函数无下定理2.3.3 对于非退化的基本可行解，若向量的第个分量，而向量至少有一个正分量，则可以找到一个新的基本可行解使得。证明：只需将具体的找出来.令满足 令下面证明，当适当选取后，即为所求.显然，为使，则要求，所以令定理2.3.3的一些说明:1、检验数向量：,它的每个分量称为检验数。2、第k列称为进入基列，第k个变量称为进基变量；第i列称为退出基列，第i个变量称为离基变量。定理2.3.4 对于任何非退化的LP问题，从任何基本可行解开始，经过有限多次迭代，或得到一个基本可行的最优解，或作出该LP问题无界的判断。单纯型方法的算法步骤：step1 找一个初始可行基；step2 求出典式和检验数；step3 求；step4 如果，停止，已找到最优解及最优值 ；step5 如果，停止，原问题无界；step6 求step7 以替代得到一个新的基，转st22、单纯形表一般假设当前的基对应的单纯形表为 1 1 1 如果为入基变量，为出基变量，则经过变换单纯形表为 1 0 1/ 1 1 0 其中，。目标函数等价于由于，所以。把Z看成变量在单纯形表中加上一列，同时加上一行描述方程，则可以得到新的单纯形表：Z 1 0 0 0 1 1 1 当进行转换时只需要把转换成0对应其它位置等价变换即可。 1 0 -/ 0 0 1 0 1/ 1 1 0 其中；。例2.3.1 求解问题：解：以、和为基变量就可以得到初始基可行解，其对应的单纯形表为 1 -21 -2 1 1 -3 11 -1 1212由于，所以该基可行解不是最优解，同时系数矩阵该列有大于0的元素，所以取为入基变量。计算，所以取第二个约束对应的基变量为出基变量，就可以得到一个新的基可行解，在上表中把对应的列变成单位向量，系数矩阵第2行对应的元素为1，则可以得到该基可行解的单纯形表 0 1 -1-11 0 -5 21 -3 10 2 -1 1411由于，所以该基可行解不是最优解，同时系数矩阵该列有大于0的元素，所以取为入基变量。计算，所以取第3个约束对应的基变量为出基变量，就可以得到一个新的基可行解，在上表中把对应的列变成单位向量，系数矩阵第3行对应的元素为1，则可以得到该基可行解的单纯形表： 0 0 -1/2 -1/2-3/21 0 -5 -1/2 5/21 0 -1/2 3/20 1 -1/2 1/213/25/21/2由于检验数都小于等于0，所以该基可行解就是最优解，对应的最优解为，最优值为-3/2。注：1. 该算法在实际应用中非常有效，被广泛采用，但在理论上不是多项式时间算法。2. 现在还有待解决的问题是如何给出初始基可行解以及出现退化的时候如何处理。第四节 初始解教学重点：两阶段算法的思想。教学难点：两阶段算法的思想。教学课时：4学时主要教学环节的组织：给出两阶段算法的思想，并用单纯形表进行求解。两 阶 段 法基本思想 第一阶段：通过求解辅助问题的最优基可行 解得到原问题的初始基可行解。 第二阶段：求原问题的最优解设原问题为 不妨假设，如果某一个元素小于0，该方程两边乘于-1后则可以使右端数变成正数。考虑如下辅助问题： 其中。首先用单纯形法解这个辅助问题。1. 显然如果原问题( 2.4.1)有可行解，则辅助规划( 2.4.2)的最优值为0，反之亦然。2由于，所以以为基变量，就可以得到规划（2.4.2）的初始基可行解。3规划（2.4.2）有可行解，同时，所以。即辅助问题的目标函数有下界，所以该问题一定有最优解。4因此我们可以首先求规划( 2.4.2)的最优基可行解，如果最优值为0，则，所以是问题( 2.4.1)的可行解。由于是规划（2.4.2）的基可行解，所以其非零分量对应系数矩阵的列向量线性无关。所以的非零分量对应的系数矩阵的列向量也线性无关，所以是问题( 2.4.1)的基可行解。在规划（2.4.2），我们称为人工变量。1且为非基变量，则此时是问题( 2.4.1)的基可行解，且基变量不变。在最优基可行解的单纯形表里删除 对应的列，同时计算出检验数就可以得到原问题的单纯形表。2且中有部分变量为基变量，此时是问题( 2.4.1)的基可行解，不同的是基变量会有些改变。3，则原问题没有可行解。例2.4.1求解如果以、为基变量，则可以得到该问题的基解，不是可行解，而其第一个基可行解不能直接给出。首先引入人工变量，考虑问题以和为基变量可得其第一个基可行解，其对应的单纯形表为 -5 -2102 8 -1 -1 31 -1 6 -1 11 1 2 -1 121由于，所以该基可行解不是最优解，同时系数矩阵该列有大于0的元素，所以取为入基变量。计算，所以取第1个约束对应的基变量为出基变量，就可以得到一个新的基可行解，在上表中把对应的列变成单位向量，系数矩阵第1行对应的元素为1，则可以得到该基可行解的单纯形表 -3/2 -7/2 -7/2 21/672/3 4/3 1/3 -1 -4/3 1/31/6 -1/6 1 -1/6 1/62/3 4/3 1/3 -1 -1/3 11/31/3由于，所以该基可行解不是最优解，同时系数矩阵该列有大于0的元素，所以取x2为入基变量。计算，所以取第2个约束对应的基变量为出基变量，就可以得到一个新的基可行解，在上表中把x2对应的列变成单位向量，系数矩阵第2行对应的元素为1，则可以得到该基可行解的单纯形表 1/4 -21/8 -21/8 21/8 21/863/8 -1 -101/4 1 -1/8 -1/8 1/8 1/81/2 1 1/4 -3/4 -1/4 3/43/81/4由于检验数都小于等于0，所以对应的基可行解就是辅助问题的最优解，最优值为0，且人工变量都是非基变量，所以得到原问题的基可行解，对应的基变量为x2和x3，对应的单纯形表为 1/4 -21/8 -21/8 63/81/4 1 -1/8 -1/8 1/2 1 1/4 -3/4 3/81/4由于，所以该基可行解不是原问题最优解，同时系数矩阵该列有大于0的元素，所以取x1为入基变量。计算，所以取第2个约束对应的基变量x2为出基变量，就可以得到一个新的基可行解，在上表中把x1对应的列变成单位向量，系数矩阵第2行对应的元素为1，则可以得到该基可行解的单纯形表 -1/2 -11/4 -9/4 31/4 -1/2 1 -1/4 1/4 1 2 1/2 -3/2 1/41/2由于检验数都小于等于0，所以对应的基可行解就是原问题的最优解，最优值为31/4，对应的最优解为。第五节 对偶和对偶单纯形方法教学重点：对偶性，对偶理论，对偶单纯形方法。教学难点：对偶性，互补松紧条件，对偶单纯形方法。教学课时：6学时主要教学环节的组织：首先给出对偶性，然后通过对偶理论得到互补松紧条件，最后介绍对偶单纯形方法。定义2.5.1给定一个一般形式的LP问题，称它为原始LP问题，它的对偶问题定义如下：原始（） 对偶（） 标准形式线性规划的对偶规划考虑线性规划的标准形式 () 其中。根据单纯形理论，若是最优基可行解，其对应的基阵为B则其检验数为，同时，最优值为。如果令，则有，。同时是下列规划的可行解 ()对于规划()的任意可行解x和规划()的任意可行解，由于所以有由此可知是规划()的最优解，反之亦然。两个规划的最有解之间存在着密切的关系，通过一个规划可以得到另一个规划的最优解。同时从形式上两者之间也有本质的相似，给定后两个规划相伴而存在，因而称两个规划互为对偶规划。规范形式的线性规划（P） 其对偶规划为 （D）对于一般形式的线性规划通过把其转化为标准形式同样可以得到其对偶规划为：例 ：写出下列规划的对偶规划：其对偶规划为 2、对偶理论定理2.5.1如果一个线性规划有最优解，则其对偶规划也有最优解，且它们的最优值相等。证明：对于标准形式的线性规划()的任意可行解和它的对偶规划()的任意可行解，由于所以有 若是()的最优基可行解，其对应的基阵为B. 令，则是()的可行解. 根据上面的不等式可知：()有最优解。同时又有，所以它们的最优值相等。推论2.5.1 若和 分别是原规划和对偶规划的可行解，则 和 分别是原规划和对偶规划的最优解的充要条件是定理2.5.2线性规划的对偶规划的对偶规划是原始规划。证明： 定理2.5.3 给定一个原规划和对偶规划，则下面三种情况必有其一(具体见教科书上表2.5.1)：1.都有最优解2.都无可行解3.一个有可行解另一个无界定理2.5.4(互补松紧性) 若和 分别是原规划和对偶规划的可行解，则 和分别是原规划和对偶规划的最优解的充要条件是： 例题 ：考虑在例2.5.1给出的原始问题和其对偶问题。由于原始问题是标准形式，故互补松紧条件（2.5.13）自动满足。在例2.4.1中，已求出这个原始LP问题的最优解为，其中所以（2.5.14）变为即对偶问题最优解必使第一个和第三个约束取等式，有由此可解出，其对应的目标函数值为，由定理2.5.4知，此为对偶问题的最优解。对偶问题与原问题，一个线性规划的规模较大时或许改为求解它的对偶问题反而比较适当。对偶单纯形方法的步骤第1步 列出初始单纯形表（它含有原问题的一个基本解和对偶问题的一个可行解）；第2步 求第3步 若，停止。已找到原始问题最优解及最优值；第4步 若，则原始问题无可行解，停止；第5步 求；第6步 以为转轴元做一次旋转变换，转到第2