运筹学第03章资料

1第三章第三章线性规划问题的线性规划问题的对偶与灵敏度分析对偶与灵敏度分析2本章内容重点本章内容重点线性规划的对偶问题的概线性规划的对偶问题的概念、理论及经济意义念、理论及经济意义线性规划的对偶单纯形法线性规划的对偶单纯形法线性规划的灵敏度分析线性规划的灵敏度分析3 一、一、对偶问题的提出：对偶问题的提出：若若第二章例第二章例2-1问题问题的设备都用的设备都用于外协加工，工厂收取加工费。试于外协加工，工厂收取加工费。试问：设备问：设备 A、B、C 每工时各如何收每工时各如何收费才最有竞争力？费才最有竞争力？设设 y1、y2、y3 分别为每工时设备分别为每工时设备 A、B、C 的收取费用。的收取费用。第一节第一节 线性规划对偶问题线性规划对偶问题4第一节 线性规划对偶问题线性规划对偶问题 例例3-1 某某工工厂厂拥拥有有A、B、C三三种种类类型型的的设设备备，生生产产甲甲、乙乙两两种种产产品品。每每件件产产品品在在生生产产中中需需要要占占用用的的设设备备机机时时数数，每每件件产产品品可可以以获获得得的的利利润润以以及及三三种种设设备备可可利利用用的的时数如下表所示。求获得最大利润的方案。时数如下表所示。求获得最大利润的方案。产品甲产品乙设备能力/h设备A3 32 26565设备B2 21 14040设备C0 03 37575利润/（元/件）15001500250025005Max z=1500 x1+2500 x2 原问题原问题s.t.3x1+2x2 65 2x1+x2 40 3x2 75 x1,x2 0Min f=65y1+40y2+75y3 对偶问题对偶问题s.t.3y1+2y2 1500（不少于甲产品的利润）（不少于甲产品的利润）2y1+y2+3y3 2500（不少于乙产品的利润）（不少于乙产品的利润）y1,y2,y3 06 二、二、对偶规划的形式对偶规划的形式 有有对称形式对称形式和和非对称形式非对称形式。对对称称形形式式的的对对偶偶规规划划之之间间具具有有下下面面的的对应关系：对应关系：(1)若若一一个个模模型型为为目目标标求求“极极大大”，约约束束为为“小小于于等等于于”的的不不等等式式，则则它它的的对对偶偶模模型型为为目目标标求求“极极小小”，约约束束是是“大于等于大于等于”的不等式。即的不等式。即 “max，”和和“min，”相对应。相对应。7(2)从从约约束束系系数数矩矩阵阵看看：一一个个模模型型中中为为，则则另另一一个个模模型型中中为为AT。一一个个模模型型是是m个个约约束束，n个个变变量量，则则它它的的对对偶模型为偶模型为n个约束，个约束，m个变量。个变量。(3)从从数数据据b、C的的位位置置看看：在在两两个个规规划模型中，划模型中，b和和C的位置对换。的位置对换。(4)两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。8 对称形式：对称形式：互为对偶互为对偶 (LP)Max z=cT x (DP)Min f=bT y s.t.Ax b s.t.AT y c x 0 y 0 “Max-”“Min-”9非非对对称称形形式式的的对对偶偶规规划划:对对非非对对称称形形式式，可以按照下面的对应关系直接给出其对偶规划可以按照下面的对应关系直接给出其对偶规划(1)将将模模型型统统一一为为“max，”或或“min，”的的形形式式，对对于于其其中中的的等等式式约约束束按按下下面面(2)、(3)中的方法处理；中的方法处理；(2)若若原原规规划划的的某某个个约约束束条条件件为为等等式式约约束束，则则在在对对偶偶规规划划中中与与此此约约束束对对应应的的那个变量取值没有非负限制；那个变量取值没有非负限制；(3)若若原原规规划划的的某某个个变变量量的的值值没没有有非非负负限限制制，则则在在对对偶偶问问题题中中与与此此变变量量对对应应的那个约束为等式。的那个约束为等式。13例例3-23-2 写出下面线性规划的对偶规划模写出下面线性规划的对偶规划模型型 14解解 先将约束条件变形为先将约束条件变形为“”形式形式15根据非对称形式的对应关系，直接写根据非对称形式的对应关系，直接写出对偶规划出对偶规划16定理定理3-1(弱对偶定理）弱对偶定理）若若X和和Y分别为原规划（分别为原规划（P）和对偶规划（和对偶规划（D）的可行解，那）的可行解，那么么cTx bTy。推论推论1 设设X0和和Y0分别为原规划分别为原规划（P）和对偶规划（）和对偶规划（D）的可行解，）的可行解，当当CX0=bTY0时，时，X0、Y0分别是两分别是两个问题的最优解。个问题的最优解。三、三、线性规划对偶问题线性规划对偶问题17推论推论2 若规划（若规划（P）有可行解，则）有可行解，则（P）有最优解的充分必要条件是规）有最优解的充分必要条件是规划（划（D）有可行解。）有可行解。推论推论3 若规划（若规划（D）有可行解，则）有可行解，则（D）有最优解的充分必要条件是规）有最优解的充分必要条件是规划（划（P）有可行解。）有可行解。定理定理 3-2 若原规划（若原规划（P）有最优解，则）有最优解，则对偶规划（对偶规划（D）也有最优解，反之亦）也有最优解，反之亦然。并且两者的然。并且两者的目标函数值相等目标函数值相等18例例3-3 求解下面线性规划问题，并求解下面线性规划问题，并根据最优单纯形表中的检验数，根据最优单纯形表中的检验数，给出其对偶问题的最优解。给出其对偶问题的最优解。19解得最优单纯形表解得最优单纯形表 最优解为最优解为(0,25,25)T，最优值为，最优值为250。表中松弛变量的检验数分别为表中松弛变量的检验数分别为-0.5，-2，可以验证可以验证(0.5,2)T为对偶规划的最优解。为对偶规划的最优解。x1x2x3x4x5-0.75100.75-0.51.2501-0.250.5-2.500-0.5-2cBxB3x2257x325-z-2504370020 可以用下面方法验证的对偶最优性。可以用下面方法验证的对偶最优性。原规划的对偶规划为原规划的对偶规划为(1/2,2)T为对偶可行解，并且目标值为为对偶可行解，并且目标值为f=250由定理由定理3.1的推论的推论1可以判断可以判断(1/2,2)T为对偶问为对偶问题的最优解。题的最优解。21 从本例的结论可以看到，对从本例的结论可以看到，对偶规划的最优解可以在原规划的偶规划的最优解可以在原规划的最优解的检验数中得到，最优解的检验数中得到，原规划原规划最优解的检验数最优解的检验数 的后的后m个分量个分量（松弛变量对应的检验数）的负（松弛变量对应的检验数）的负值，为对偶规划的最优解值，为对偶规划的最优解。对偶规划的最优解又称对偶规划的最优解又称对偶价格对偶价格221 1影子价格的概念影子价格的概念考虑互为对偶的线性规划考虑互为对偶的线性规划(P)(P)、(D)(D)设设y*=（y1*,，ym*)T为对偶规划为对偶规划(D)(D)的最优解，则的最优解，则yi*称为规划称为规划(P)(P)第第i个个约束对应的影子价格约束对应的影子价格(S(Shadow Price)。四、四、影子价格影子价格23影子价格的经济含义影子价格的经济含义(1)影影子子价价格格是是对对现现有有资资源源实实现现最最大大效效益时的一种估价。益时的一种估价。企企业业可可以以根根据据现现有有资资源源的的影影子子价价格格，对对资资源源的的使使用用有有两两种种考考虑虑：第第一一，是是否否将将设设备备用用于于外外加加工工或或出出租租，若若租租费费高高于于设设备备的的影影子子价价格格，可可考考虑虑出出租租设设备备，否否则则不不宜宜出出租租。第第二二，是是否否将将投投资资用用于于购购买买设设备备，以以扩扩大大生生产产能能力力，若若市市价价低低于于某某设设备备的的影影子子价价格格，可可考考虑虑买买进进该该设设备备，否否则则不不宜宜买买进进。24四、影子价格四、影子价格 (2)影影子子价价格格表表明明资资源源增增加加对对总总效效益益产产生生的的影影响响。根根据据推推论论，在在最最优优解解的的情情况下，有况下，有 因因此此，可可以以将将z*看看做做是是bi的的函函数数，对对bi求偏导数可得到求偏导数可得到 这这说说明明，如如果果右右端端常常数数增增加加一一个个单单位，则目标函数值的增量将是位，则目标函数值的增量将是y*。25 影影子子价价格格反反映映了了不不同同的的局局部部或或个个体体的的增增量量可可以以获获得得不不同同的的整整体体经经济济效效益益。如如果果为为了了扩扩大大生生产产能能力力，考考虑虑增增加加设设备备，就就应应该该从从影影子子价价格格高高的的设设备备入入手手。这这样样可可以以用用较较少少的的局局部部努努力力，获获得得较较大大的整体效益。的整体效益。需要指出，影子价格不是固定不变需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，时，有可能使影子价格发生变化。另外，影子价格的经济含义是指资源在一定范影子价格的经济含义是指资源在一定范围内增加时的情况，当某种资源的增加围内增加时的情况，当某种资源的增加超过了这个超过了这个“一定的范围一定的范围”时，总利润时，总利润的增加量则不是按照影子价格给出的数的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度值线性地增加。这个问题还将在灵敏度分析一节中讨论。分析一节中讨论。27第二节第二节 对偶单纯形法对偶单纯形法 一、一、对偶单纯形法的基本思想对偶单纯形法的基本思想 从从原原规规划划的的一一个个对对偶偶可可行行基基本本解解（检检验验数数非非正正）出出发发，然然后后检检验验这这个个对对偶偶可可行行基基本本解解是是否否可可行行，即即是是否否非非负负。如如果果有有小小于于零零的的分分量量，则则进进行行迭迭代代，求求另另一一个个对对偶偶可可行行基基本解本解（保持检验数非正）。（保持检验数非正）。281.建立初始对偶单纯形表建立初始对偶单纯形表,对应一个基本解对应一个基本解,所有检验数均非正所有检验数均非正,转转2；2.若若 b0,则得到最优解则得到最优解,停止停止;否则否则,若有若有bk0,则选则选k行的基变量为出基变量行的基变量为出基变量,转转33.若所有若所有akj0(j=1,2,n)，则原问题无可，则原问题无可行解行解,停止停止;否则否则,若有若有akj0,则选则选 =min j/akjakj0=r/akr那么那么,xr为进基变量为进基变量,转转4；4.以以akr为转轴元为转轴元,作矩阵行变换使其变为作矩阵行变换使其变为1,该列其他元变为该列其他元变为0,转转2。二、对偶单纯形法主要步骤二、对偶单纯形法主要步骤29例例3-43-4 求解线性规划问题：求解线性规划问题：Min f=2x1+3x2+4x3 s.t.x1+2x2+x3 3 2x1-x2+x3 4 x1,x2,x3 0解：解：Max z=-2x1-3x2 -4x3 s.t.-x1-2x2-x3+x4 =-3 -2x1+x2-3x3 +x5=-4 x1,x2,x3,x4,x5 0表格对偶单纯形法表格对偶单纯形法最优解为最优解为:x=(2.2,0.4,0,0,0)T,z=-5.6最优值最优值 f=5.6无可行解情况无可行解情况 线性规划问题可能出现不存在可线性规划问题可能出现不存在可行解的情况，这时，在对偶单纯形表行解的情况，这时，在对偶单纯形表中显示矛盾方程。中显示矛盾方程。例例3-5 Max z=x1 3x2 2x3 s.t.x1+2x2 +3x3+x4 =10 2x1+x2+5x3 +x5=20 3x1+2x2 x3 +x6 =12 x1,x2,x3,x4,x5,x6 0对偶单纯形表对偶单纯形表表中第表中第1行反映了一个矛盾约束：行反映了一个矛盾约束：x1+2x2+3x3+x4 =-10 即，若所有即，若所有akj0(j=1,n)，则原问，则原问题无可行解题无可行解,停止停止;33是是是是是是是是否否否否否否否否所有所有所有所有得到得到最优解最优解计算计算计算计算典典式式对对应应原原规规划划的的基本解是可行的基本解是可行的典典式式对对应应原原规规划划的的基基本解的检验数本解的检验数所有所有所有所有计算计算计算计算以为中心元素进行迭代以为中心元素进行迭代以为中心元素进行迭代以为中心元素进行迭代停停没没有有最最优优解解没没有有最最优优解解单纯形法单纯形法对偶单纯形法对偶单纯形法比较比较0 csMin j/asj asj0 br Min-bi/air air049上例上例最优单纯形表如下最优单纯形表如下 例例3-93-950 0 0.25 0 0 0.25 0 这里这里 B B-1-1=-2 0.5 1=-2 0.5 1 0.5-0.125 0 0.5-0.125 0 各列分别对应各列分别对应 b1、b2、b3 的单一变化的单一变化因此，设因此，设 b1 增加增加 4，则，则 x1、x5、x2分别变为：分别变为：4+04=4,4+(-2)4=-40,2+0.54=4用对偶单纯形法进一步求解，可得：用对偶单纯形法进一步求解，可得：51于是，于是，x*=(4,3,2,0,0)T,f*=1752讨论保持最优基不变的前提下，讨论保持最优基不变的前提下，b2的允许变化范围的允许变化范围 4+b2 0.25 0 b2 -16 4+b2 0.5 0 b2 -8 2+b2 (-0.125)0 b2 16于是于是 -8 b2 1653增加变量增加变量 xn+1,相应有相应有pn+1,cn+1。可计算出可计算出 B-1pn+1,n+1=cn+1-cri ari n+1 填入最优单纯形表：填入最优单纯形表：若若 n+1 0，则，则 最优解不变；最优解不变；否则，进一步用单纯形法求解。否则，进一步用单纯形法求解。四、增加新变量分析四、增加新变量分析54例例3-10 3-10 对前例对前例，增加，增加x6,p6=(2,6,3)T,c6=5用单纯形法进一步求解，可得：用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)T ,f*=16.555 首先，应把最优解代入新的约束首先，应把最优解代入新的约束 若满足，则最优解不变，停止；若满足，则最优解不变，停止；否则，引入一个新的非负变量（否则，引入一个新的非负变量（原约原约束若是小于等于形式可引入非负松弛变量，否则引束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量入非负人工变量），填入最优单纯形表作），填入最优单纯形表作为新的一行，并通过矩阵行变换把对应为新的一行，并通过矩阵行变换把对应基中的列向量变为单位向量。基中的列向量变为单位向量。进一步用对偶单纯形法求解。进一步用对偶单纯形法求解。四、四、增加一个约束条件增加一个约束条件56例例 3-11 上例上例增加增加 3x1+2x2 15，原最，原最优解不满足这个约束。于是优解不满足这个约束。于是 对表中新的一行利用矩阵初等行变对表中新的一行利用矩阵初等行变换进行处理，可得新的对偶单纯性表：换进行处理，可得新的对偶单纯性表：57经对偶单纯形法一步，可得最优解为经对偶单纯形法一步，可得最优解为（3.5,2.25,0,0,3,2)T，最优值为最优值为 13.75 58(只讨论只讨论 N 中某一列变化情况）中某一列变化情况）与增加变量与增加变量 xn+1 的情况类似，的情况类似，假设假设 pj 变化变化。那么，重新计算出。那么，重新计算出 pj=B-1pj j=cj-cri ari j 填入最优单纯形表，若填入最优单纯形表，若 j 0，则则最优解不变；否则，进一步用单纯最优解不变；否则，进一步用单纯形法求解。（例子从略）形法求解。（例子从略）五、五、A中元素发生变化中元素发生变化第四节第四节 线性规划应用线性规划应用百分之一百法则：百分之一百法则：对对于于所所有有变变化化的的目目标标函函数数中中的的决决策策变变量量系系数数，当当其其所所有有允允许许增增加加的的百百分分比比与与允允许许减减少少的的百百分分比比之之和和不不超超过过100%时时，最最优优解解不不变变；对对于于所所有有约约束束条条件件右右边边常常数数值值，当当其其所所有有允允许许增增加加的的百百分分比比与与允允许许减减少少的的百百分分比比之之和和不不超过超过100%时，对偶价格不变。时，对偶价格不变。59定理定理概念解释概念解释允许增加的百分比允许增加的百分比=增加量增加量/允许增加量允许增加量允许减少的百分比允许减少的百分比=减少量减少量/允许减少量允许减少量 其其中中，允允许许增增加加量量是是允允许许变变化化的的上上限限与与当当前前值值的的差差的的绝绝对对值值，在在Excel敏敏感感性性报报告告表表中中即即是是“允允许许的的增增量量”。增增加加量量即即是是实实际际量量值值（大大于于当当前前值值）与与当当前前值值的的差差的的绝绝对对值值。允允许许减减少少量量是是允允许许变变化化的的下下限限与与当当前前值值的的差差的的绝绝对对值值，在在Excel敏敏感感性性报报告告表表中中即即是是“允允许许的的减减量量”。减减少少量量即即是是实实际际量量值值（小小于于当当前值）与当前值的差的绝对值。前值）与当前值的差的绝对值。60 例例3-12 某某工工厂厂在在计计划划期期内内要要安安排排甲甲、乙乙两两种种产产品品的的生生产产，已已知知生生产产单单位位产产品品所所需需成成本本分分别别为为2千千元元和和3千千元元；根根据据产产品品特特性性，产产品品总总数数不不得得少少于于350件件，产产品品甲甲不不得得少少于于125件件；又又知知生生产产这这两两种种产产品品需需要要某某种种钢钢材材，产产品品甲甲、乙乙每每件件分分别别需需要要钢钢材材2t、1t，钢钢材材的的供供应应量量限限制制在在600t。问问题题：工工厂厂应应分分别别生生产产多多少少单单位位甲甲、乙乙产产品品才才能能使使总总成成本本最最低？低？61 在例中在例中，如果讨论如果讨论:(1)产产品品甲甲的的成成本本由由2千千元元增增为为2.4千千元元，产产品品乙乙的的成成本本由由3千千元元减减少少到到2.7千千元元，最最优优解解是否变化？是否变化？解解：产产品品甲甲成成本本的的允允许许增增加加量量为为1千千元元，增增加加量量为为2.4千千元元-2千千元元=0.4千千元元；产产品品乙乙成成本本的的允允许许减减少少量量为为1千千元元，减减少少量量为为3千千元元-2.7千元千元=0.3千元。于是千元。于是 0.4/1+0.3/1=0.7 100%定理定理3-2无法判断对偶价格是否变化。无法判断对偶价格是否变化。63在使用百分之一百法则进行灵敏度分析时，要注意：在使用百分之一百法则进行灵敏度分析时，要注意：1）当允许增加量（允许减少量）为无穷）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允许大时，则对任意增加量（减少量），其允许增加（减少）百分比均看增加（减少）百分比均看做做0；2）百分之一百法则是充分条件，但非）百分之一百法则是充分条件，但非必要条件；必要条件；3）百分之一百法则不能用于目标函数决）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化策变量系数和约束条件右边常数值同时变化的情况。这种情况下，只有重新求解。的情况。这种情况下，只有重新求解。64 例例3-13 3-13 考虑下列线性规划模型考虑下列线性规划模型 某某企企业业生生产产甲甲、乙乙、丙丙三三类类特特种种钢钢材材，每每吨吨甲甲、乙乙、丙丙钢钢材材需需要要加加入入材材料料A、B、C、D的的数数量量，材材料料限限制制及及每每吨吨甲甲，乙乙，丙丙钢钢材材的的利润如下表：利润如下表：寻求使得总利润最高的生产方案。寻求使得总利润最高的生产方案。65材料材料A/（kgt）材料材料B/（kgt）材料材料C/（kgt）材料材料D/（kgt）利润利润/(千千元元t)钢材甲钢材甲751212钢材乙钢材乙18659钢材丙钢材丙812510材料材料限制限制/kg630600708270进一步考虑下列问题：进一步考虑下列问题：a如果原料如果原料A、B、C、D可用相同的价格购可用相同的价格购买补充，你将优先请考虑哪一种，为什么买补充，你将优先请考虑哪一种，为什么？购买价格在什么范围内，企业可以接受？购买价格在什么范围内，企业可以接受？b当钢材甲的利润由当钢材甲的利润由12千元千元t变为变为10千元千元吨的同时，产品乙的利润由吨的同时，产品乙的利润由9千元千元t变为变为9.5千元千元t，这时原来的最优方案变不变？，这时原来的最优方案变不变？为什么？为什么？c当其当其他他材料的供应量不变时，材料材料的供应量不变时，材料A的供的供应量在什么范围内可以直接估计总利润的应量在什么范围内可以直接估计总利润的变化。为什么？变化。为什么？66d.原料原料 C 的对偶价格是什么，解释它的的对偶价格是什么，解释它的含义。含义。e.原料原料 A、D分别购进分别购进30kg、5kg后，总后，总利润是否可以利用求解结果直接计算利润是否可以利用求解结果直接计算出来？如果可以，总利润是多少？出来？如果可以，总利润是多少？67解：解：建立数学模型建立数学模型 设生产甲、乙、丙三类特种钢材分别为设生产甲、乙、丙三类特种钢材分别为 x1、x2、x3 t，得到下列线性规划模型得到下列线性规划模型 Max z=12x1+9x2+10 x3 S.t.7x1+x2+8x3 630 5x1+8x2+x3 600 x1+6x2+2x3 708 2x1+5x2+5x3 270 x1，x2，x3 0 利用计算机软件求解得到：利用计算机软件求解得到：68最优解最优解x1=87.273t，x2=19.091t，x3=0t；最优值；最优值z*=1219.091千元。千元。材料材料A、B、C、D的对偶价格分别为每公斤的对偶价格分别为每公斤1.273千千元、元、0千元、千元、0千元、千元、1.545千元。千元。目标函数决策变量系数的灵敏度信息：目标函数决策变量系数的灵敏度信息：决策变量决策变量 当前值当前值 允许的增量允许的增量 允许的减量允许的减量-x1 12.000 51.000 7.457 x2 9.000 21.000 7.286 x3 10.000 7.909 69 约束右端项的灵敏度信息：约束右端项的灵敏度信息：约束约束 当前值当前值 允许的增量允许的增量 允许的减量允许的减量-1 630.000 40.000 576.000 2 600.000 10.909 3 708.000 506.182 4 270.000 7.059 90.00070根据根据上面上面结果，得到题中需要考虑问题的解释：结果，得到题中需要考虑问题的解释：在在材材料料A、B、C、D的的数数量量限限制制范范围围内内，甲甲、乙乙、丙丙类类钢钢材材各各生生产产87.273t、19.091t和和0t（不不生生产产），可可获获得得的的总总利利润润为为 1219091 元。元。a如如果果原原料料A、B、C、D可可以以用用相相同同的的价价格格购购买买补补充充，我我们们将将优优先先考考虑虑材材料料D，因因为为D的的对对偶偶价价格格最最高高，即即同同样样购购买买1kg，可可获获得得增增加加的的利利润润最最多多。依依据据对对偶偶价价格格，购购买买价价格格不不超超过过被被公公斤斤1545元元，企企业可以接受。业可以接受。71 b当钢材甲的利润由当钢材甲的利润由12千元千元t变为变为10千元千元t的同时，产品乙的利润由的同时，产品乙的利润由9千元吨变为千元吨变为9.5千千元元t，根据百分之一百法则，根据百分之一百法则 (12-10)/51+(9.5-9)/7.286=0.107 100%由于百分之一百法则是充分条件，因此我们由于百分之一百法则是充分条件，因此我们 的答案应是无法判断是否可以。在这里，我们无的答案应是无法判断是否可以。在这里，我们无法估计总利润是多少。法估计总利润是多少。73