线性规划的对偶问题.doc

教案五 线性规划的对偶问题教学内容 第四节 线性规划的对偶问题1线性规划的对偶问题2对偶单纯形法3线性规划的灵敏度分析4线性规划在卫生管理中的应用教学学时 7学时教学目标 1理解对偶问题的基本概念2掌握对偶单纯形法3掌握线性规划的灵敏度分析4掌握线性规划在卫生管理中的应用重点难点 重点是对偶问题的基本概念、对偶单纯形法线、灵敏度分析、线性规划在卫生管理中的应用。难点是对偶问题的基本概念和线性规划的灵敏度分析教学手段 教师与学生互动 使用多媒体课件教学过程 一、复习巩固 1单纯形法的基本原理（见课件）2单纯形解法（见课件）3大法（见课件）二、讲授新课1线性规划的对偶问题（1）对偶问题的基本概念（见课件）对偶现象 每一个线性规划都伴随着另一个线性规划，两者有密切关系，互为对偶其中一个问题称为原问题，另一个问题称为其对偶问题两者间只要得到其中一个问题的解，那么也就得到了另一个问题的解下面通过一个实例来解释对偶线性规划的概念例2-12 以例2-1为例，我们讨论了一个制药厂的生产计划的数学模型及其解法现在假定该制药厂决定在计划期内不生产药品、，而将生产设备的有效台时全部租给某公司，那么该公司应对设备每小时付多少租金，才能使成本最小，而又能为制药厂所接受？从租用设备的公司的角度考虑，一是所付的租金越低越好；二是所付的租金总额能使制药厂接受，即租金应不低于制药厂自己生产该两种药品所得利润，否则，制药厂宁可自己生产，而不租给公司设公司租用该制药厂四种设备的租金（元/小时）分别为、和在考虑租用设备的定价时，能使该制药厂接受的条件是：公司租用该制药厂用以生产每千克药品所需四种设备的台时的租金不应少于200元，即 同样，公司租用该制药厂用以生产每千克药品所需四种设备的台时的租金不应少于300元，即 公司在考虑自身利益时，其目标是使付出的租金总额为最小，即 于是，上面的问题可以用下列线性规划的数学模型表示： 若把制药厂利润最大的线性规划问题称为原问题，则想租用四种设备的公司的租金最小的线性规划问题称为原问题的对偶问题（dual problem）；反之，若把租用四种设备的公司的租金最小的线性规划问题称为原问题，则制药厂利润最大的线性规划问题称为原问题的对偶问题影子价格 一般地，我们称对偶问题的最优解为原问题约束条件的影子价格，即对偶问题的解称为第种资源的影子价格它并不是某种资源在市场上的价格，而是代表单位资源在最优利用的条件下所产生的经济效果为了和市场价格相区别，我们才称它为影子价格它在经济上是一个很有意义的数据，通过它我们可以知道，当增加某种资源时，可以使利润增长的大小另外，影子价格还给出了是否应当购进某种资源以增加生产量，而获得更多利润的价格标准（2）对称的对偶线性规划（见课件）如果一个线性规划具备下面两个条件，则称它具有对称形式：所有的变量都是非负的；所有的约束条件都是不等式，而且在目标函数是求极大值的情况，不等式具有小于和等于（）的符号，在目标函数是求极小值的情况，不等式具有大于和等于（）的符号对称形式的原问题和对偶问题叫做对称的对偶线性规划原问题和对偶问题在形式上的对比 如果我们把线性规划 称为原问题，则必同时存在另一线性规划问题，我们称为对偶问题： 而且 用简缩形式表示：原问题为 对偶问题为 ; 矩阵形式表示：原问题为 对偶问题为 Min WYb 其中， 原问题与对偶问题之间的关系1）原问题是求目标函数的最大值，对偶问题是求目标函数的最小值2）原问题约束条件的右端项变成对偶问题目标函数的系数原问题目标函数中的系数变成对偶问题约束条件的右端项3）原问题约束条件是“”，对偶问题的约束条件则是“”4）原问题约束条件的每一行正好对应于对偶问题的每一列，所以原问题中约束条件的数目等于对偶问题中变量的数目5）原问题中约束条件的每一列正好对应于对偶问题的每一行，所以原问题中变量的数目正好等于对偶问题中的约束条件的数目6）对偶问题的对偶规划正是原问题例2-13 设原问题为： 试写出它的对偶问题解 （3）非对称的对偶线性规划（见课件）对于我们经常遇到的非对称形式的线性规划，我们可首先将其化为等价的对称形式的线性规划问题，然后再按对称的对偶线性规划原问题与对偶问题之间的对应关系，将其化为对偶问题实际上，我们在考虑对称的对偶线性规划或非对称的对偶线性规划（dual of a nonnormal LP）时，也可以按表2-13原问题与对偶问题之间的对应关系，直接进行变换，得到原问题或对偶问题表2-13 原问题与对偶问题间的转换原问题（或对偶问题）对偶问题（或原问题）目标函数目标函数 约束条件数：个对偶变量数：个第个约束条件为“”对偶变量0第个约束条件为“”对偶变量0第个约束条件为“=”对偶变量无非负条件变量的数目：个约束条件数：个变量0第个约束条件为“”变量0第个约束条件为“”变量无非负条件第个约束条件为“”限定向量成本或利润向量成本或利润向量限定向量系数矩阵系数矩阵例2-14 原问题为： ，符号不限可按表2-13的原则，将原问题直接转化成对偶问题： ，符号不限（4）对偶问题的基本性质（见课件）1）对偶问题的对偶是原问题（对称性质）2）若和分别是原问题和对偶问题的可行解，则（弱对偶性质）3）设和分别是原问题和对偶问题的可行解，当两者目标函数值相等，即时，分别是原问题和对偶问题的最优解（可行解是最优解的性质）4）若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等（对偶性质）5）若和分别是原问题和对偶问题的可行解，则和为原问题及对偶问题最优解的充分条件为： 0和0其中，, 是原问题的松弛变量，（）, 是对偶问题的剩余变量（松弛互补性质）此性质在线性规划中有广泛应用如从已知的原问题最优解（或对偶问题最优解）求取对偶问题最优解（或原问题最优解）；验证原问题的可行解是否最优解等等6）原问题的检验数对应于对偶问题的一个基本解由对偶性质可知，在求解原问题的过程中，利用单纯形表每一次迭代所得的检验数与对偶问题的基本解仅仅相差一个符号，于是原问题获得最优解时对应的单纯形表中检验数的相反数，即为对偶问题的最优解例2-15 设原问题为： 已知其对偶问题的最优解为*1.2，*0.2，相应的目标函数最小值*28，试利用对偶性质求该问题的最优解解 原问题的对偶问题为： 由松弛互补性质可知，在最优条件下，0和0，即*0，*0，*0，*0，*0，*0；这里*（），*（）分别为原问题的松弛变量及对偶问题的剩余变量由* 1.20，可以推出* =0；由* 0.20，可推出* =0由对偶约束*+2* =1.61，知* 0,于是* =0；同理，由2*+* =2.62，知* 0,于是* =0根据上述结果，原约束可以转化成二元一次线性方程组： * +* =20 * +* =20解方程得* =* =4综上所得，原问题的最优解为* =，相应的目标函数最优值为* =28由对偶性质还可以推论：1）若原问题可行，但有无界解（或称无有限最优解），则对偶问题不可行；若对偶问题可行，但有无界解（或称无有限最优解），则原问题不可行；2）若原问题可行，而对偶问题不可行，则原问题有无界解（或称无有限最优解）；若对偶问题可行，而原问题不可行，则对偶问题有无界解（或称无有限最优解）2对偶单纯形法前面已叙述原问题与对偶问题的解之间的对应关系在用单纯形法进行迭代时，在列中得到的是原问题的基本可行解，而在检验数（）行得到的是对偶问题基本解的相反数通过逐步迭代，当在检验数行得到的对偶问题的解也是可行解时，原问题和对偶问题都达到了最优解所以，单纯形法的特点是保持原问题解的可行性，通过逐步迭代，使对偶问题的解由基本解变成基本可行解，这时原问题和对偶问题都达到了最优解那么根据对偶问题的对称性，我们也可以这样来处理：保持对偶问题的解是可行解（即），而原问题则从非可行解开始，通过迭代，逐步达到基本可行解这样，也使原问题和对偶问题都达到了最优解事实上，对偶单纯形法（dual simplex method）并不是解对偶问题的单纯形法，而是应用对偶原理来求解原问题的最优解的一种方法（1）对偶单纯形法的要点（见课件）例2-16 用对偶单纯形法求解下列线性规划问题 解 此问题可用大法去解，但用大法求解很麻烦，现在用对偶单纯形法求解先将原问题化为标准 形式，为此引入剩余变量，令，得 然后将约束条件等式的两边都乘以（-1），得到 建立这个问题的初始单纯形表，见表2-14：表2-14 对偶单纯形法求解例2-16（1）-1600-2500-40000 0-2-5-110-40-2001-3-1600-2500-40000=0在这个初始单纯形表中，、是基本变量，初始单纯形表所对应的基本解为，它是一个不可行解而全部检验数，即所对应的对偶问题的一个基本解也是一个可行解, ，下面的迭代是在保持检验数小于等于零的条件下，逐步使，为了满足上面要求，迭代的要点是：1）首先确定换出变量：选择具有负数的基本变量中绝对值最大的基本变量为换出变量2）确定换入变量：用换出变量那一行具有负值的系数分别去除同列的检验数，取最小商数所对应的变量为换入变量；如果换出变量那一行无负值的系数，则原问题无可行解3）把换出变量的那一行除以枢元位置的系数，使枢元位置变为14）进行行变换，使除枢元外的其他枢列位置变为05）进行最优解检查如果所得的基本解都是非负的，则此解即为最优解如果基本解中还有负的数值，则重复第1步继续迭代，直到所有基本变量为非负的数值为止（2）表解形式的对偶单纯形法（见课件）按上述迭代的要点，对表2-14继续运算，见表2-15表2-15 对偶单纯形法求解例2-16（2）-1600-2500-40000 0-2-5-110-40-2001-3-1600-2500-40000=0800500400-400251-1040-2001-3-800-5000-4000=-1600400200-400-201-12-2-2500100-40000-400-200=-2200200400-160010-11-25000100-200-200-600=-2600表2-15中列数字全为非负，检验数全为非正，故问题的最优解为* =，最优值* 2600若对应两个约束条件的对偶变量分别为和，则对偶问题的最优解为* =，最优值2600（3）对偶单纯形法的优点及用途（见课件）1）初始解可以是非可行解，当检验数都是小于等于零时，就可以进行基变换，这样就避免了增加人工变量，使运算简化2）对变量较少，而约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形法求解，简化计算3）用于灵敏度分析3线性规划的灵敏度分析在上述讨论线性规划问题时，假定，都是精确的数据，然而在大多数实际问题中，这些系数往往是估计值和预测值，而且它们也随着某些条件的变化而变化因此很自然会想到，当这些系数中的一个或几个发生变化时，已求得的规划问题的最优解会发生什么变化？如果最优解发生了变化，又怎样用最简单的方法找到新的最优解？这就是线性规划灵敏度分析（sensitivity analysis of LP）的任务（1）单纯形法的矩阵表达式（见课件）设有一线性规划问题，用矩阵表示为 式中，为矩阵，为1行向量，为1列向量，为1列向量，0为1列向量现引入松弛变量化为标准型 ，其中，是阶单位矩阵，约束条件也可写成和 ，0有个元素如果我们把系数矩阵分为两块，也称基矩阵（即原始系数矩阵中对应于基本变量的列所组成的矩阵），对应于的变量是基本变量，用向量表示，其他的变量则为非基本变量，于是将也分为两块： 向量也可分为两块，其中是目标函数中基本变量向量的系数行向量，是目标函数中非基本变量向量的系数行向量所以于是线性规划问题可以写成 在单纯形法的每次迭代中，是用行变换的方法将基矩阵变成单位矩阵用矩阵方法，则将上述约束方程的两边乘以基矩阵的逆矩阵,于是可得 （2-9）即: （2-10）所以 （2-11）将式（2-11）代入目标函数可得 （2-12）或者 （2-13）从式（2-9）可知，在单纯形表每次迭代后,每个变量的系数列向量是的逆阵乘以该变量的原始列向量而得到的，右端常数的列向量是的逆阵乘以右端常数的原始列向量而得到的从式（2-10）可见，其松弛变量的系数矩阵正好是基矩阵的逆阵更一般地理解，在任一单纯形表中相应于初始基本变量的那些列给出了相应于该表格的基矩阵的逆阵例如第二章第三节的例2-8中，表2-4、表2-5、表2-6和表2-7给出了单纯形法的计算过程，其中表2-7为最优解单纯形表，其基本变量是,，和对应于表2-7的基矩阵 所以对应于表2-7的列向量是 式中为原始单纯形表中对应于的列向量.对应于表2-7的列向量是式中为原始单纯形表中对应于的列向量.对应于表2-7的列向量是式中为原始单纯形表中右端列向量.对应于表2-7的非基本变量的检验数是，松弛变量的检验数是（2）系数变化的灵敏度分析（见课件）系数变化的灵敏度分析是在决策变量和约束条件数目不变时，研究各种系数的变化对最优解的影响它主要考虑两种情况：一是这些系数在什么范围内变化时，已得到的最优解保持不变，或者最优解的基本变量保持不变（但数值有所改变）；二是如果某些系数的变化引起最优解的变化，如何用最简便的方法求出新的最优解目标函数中变化范围的确定 假设其他参数不变，仅目标函数中的系数变成，现求不改变最优解的的大小这分两种情况：1）是非基本变量的成本或利润系数因为 （） （式中是基本变量的成本或利润系数）所以改变非基本变量的成本或利润系数，Zj不变，但变为新的检验数：要想保持极大化问题最优解不变，即，则：2）是基本变量的成本或利润系数因为 要保持极大化问题最优解不变，则对于基本变量检验数总为零，而对于非基本变量，因，所以要求检验数小于等于0变为：例2-17 以例2-8的最终计算表（表2-7）为例设基本变量在目标函数中的系数变化了；这时表2-7的最终计算表便成为表2-16所示表2-16 基本变量利润系数变化的灵敏度分析20030000000001-1002001000040000-214300010020000=14002这时要保持最优解不变，则必须满足下列不等式：-150-=-150-0-=-0 即可在0,400间变动，不影响原来的生产计划安排，但制药厂收益变化了在约束条件中变化范围的确定 初始单纯形表中的变化，除了影响最优解的数值之外，不影响最终单纯形表中的其他系数所以只要保证最后的解仍是可行解，那么它仍然是最优解即式中，为右端常数变化后，最终单纯形表右端常数向量；为右端常数未变化时，最终单纯形表右端常数向量例2-18 在例2-8中，如果第三个约束条件发生变化，变化量为，为了使最后的解仍为可行解，应满足下列不等式：所以在8,0之间变动时（即的变化范围在8,16时），原来最优解的基本变量不变，但最优解的值发生变化例如，为2时（即14），则最优解*，最优值*1375，见表2-17表2-17 右端常数变化后的最优解20030000000001-10200100000000-2133000100000-1500=1375如果的变化超出了8,0的范围，这时最优解的基本变量就发生变化在这种情况下要用对偶单纯形法继续求出新的最优解例如为2时（即18），则则最终单纯形表变为表2-18表2-18 右端常数变化后的对偶单纯形法求解20030000000001-10200100000000-2153000100000-1500=142515050000-44102200101-10040002-401430001100200-50-10000=1400新的最优解*，最优值Z*1400矩阵A中的系数改变对最优解的影响 当对应于的变量为非基本变量的系数时，它的变化不会改变基矩阵和它的逆阵，所以只需修改单纯形表中所对应的列就可以了若极大化问题0,则得到的还是新问题的最优单纯形表，最优解和最优值不变，否则可用单纯形法求解当对应于的变量为基本变量的系数时，它的变化会改变基矩阵和它的逆阵，所以会影响到最终单纯形表的右端向量和非基本变量对应的列下面就举例讨论此种基本变量的系数变化情况例2-19 以例2-1为例，若计划生产的药品的工艺结构有了改进，相应地生产单位药品所需设备的台时改为（3,2,5,2），它的利润也提高到每千克400元试分析已求得的最优计划有何变化？解 当的系数列向量变化后,原最终单纯形表（表2-7）中的系数列向量变成: =原最终单纯形表变成表2-19：表2-19 决策变量系数改变对最优解的影响（1）4003000000001-10040000004000-2143001002由的系数列向量可知，到此尚未完成行变换，所以需继续使的系数列向量变成单位列向量，于是得到表2-20表2-20 决策变量系数改变对最优解的影响（2）40030000000001-10400100000000-213000100000-150-200=1520因为0，所以新的最优解，最优值*1520元.4线性规划在卫生管理中的应用（1）放射科的业务安排（见课件）医院放射科可以开展线平片检查和检查业务，现拟购买磁共振仪，以增设磁共振检查业务为此医院收集了有关