运筹学第6讲线性规划的对偶理论和灵敏度分析2

1、运 筹 学（Operations Research）上 海 海 事 大 学 20131009任课教师：邓 伟邮 箱：影子价格影子价格1.影子价格的概念 考虑一对对称形式的对偶规划问题设 为对偶规划(D)的最优解，则称 为规划(P)的第i个约束对应的影子价格(Shadow Price).注: 是对第i中资源(设备台时)的一种估价，这个价格不是市场价格，而是针对具体企业在一定时期内存在的一种特殊价格，它蕴含在求最大利润的生产计划模型中。max( )0zCXAXbPXmin()0TTTwb YA YCDY*12(,)TmYyyy*iy*iy影子价格影子价格下面讨论影子价格的几种经济含义，这些经济含义

2、对于企业经营活动分析是具有重要作用的。2.影子价格的经济含义(1)影子价格是对现有资源实现最大效益时的一种估价。 根据现有资源的影子价格，对资源的使用有两种考虑： 第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。 第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。影子价格影子价格(2)影子价格表明资源增加对总效益产生的影响。根据对偶定理，在最优解的情况下，有关系式1122mmzfb yb yb y因此可以将 看作是 的函数，对z,1, 2,ib im,1,2,ib im求偏导数得到,1,2,i

3、izy imb这说明，如果右端常数bi增加一个单位，则目标函数的增量将是,1,2,iy im根据这一含义，可以知道那种资源的增加可以给企业带来较大的效益。影子价格影子价格注: 1.影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益，如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。2.影子价格不是固定不变的，当约束条件、利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义是指资源在一定范围内增加时的情况，当某种资源的增加超出了这个“一定范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。影子价

4、格影子价格影子价格的应用：例6.1 某外贸公司准备购进A1，A2。购进每件产品A1，需要10元，占用5m3的空间，待每件A1卖出后，可获纯利润3元；购进每件产品A2，需要15元，占用3m3的空间，待每件产品A2卖出后，可获纯利润4元。公司现有资金1400元，有430m3的仓库空间可存放产品。根据这些条件，可以建立求最大利润的线性规划模型：12121212max341015140053430,0zxxxxxxx x影子价格影子价格求解后，得到最优单纯形表：基变量 011/9-2/96010-1/151/35000-11/45-1/9-390最优方案是，购进两种产品分别为50和60，公司的最大利润

5、是390元。影子价格影子价格现在公司有另外一笔资金585元，准备用于投资。这笔资金如果用来购买产品A1，A2，当然可以使公司获得更多的利润；如果用来增加仓库的容量，也可以使公司获得更多的利润。这是因为，产品A1，A2的单位利润不同，占据的空间也不同，由于仓库容量增加了，可以使购买产品A1，A2的数量比例发生变化，仍有可能使公司的利润增加。下面利用影子价格来分析，应如何进行投资，使公司获得更多的利润。影子价格影子价格由最优表可看出，仓库的影子价格y2=1/9，即增加1m3的仓库空间，公司可多获得利润1/9元。现在已知，增加1m3的仓库空间需要0.8元，也就是说，如果将投资用于增加仓库空间，则每投

6、资0.8元，可多获利润1/9元。即，每1元投资可多获10/72元，近似为0.14元。再来看用于购买产品的资金的影子价格y2，由最优表可看出，y1=11/45，即每增加1元购买产品，可多获利润11/45元，近似为0.24元。经过比较分析，应将投资用于购买产品A1，A2，而不用于增加仓库容量，这样可获得更多的利润。影子价格影子价格将585元进行此投资之后，最大利润的增量为再这一增量值，可通过改变约束条件的新模型的求解结果，得到验证。新模型为：最优解为x1=11,x2=125,即购买两种产品分别为11件和125件。585y1=58511/45=143元12121212max3410151985534

7、30,0zxxxxxxx x影子价格影子价格将585元进行此投资之后，最大利润的增量为再这一增量值，可通过改变约束条件的新模型的求解结果，得到验证。新模型为：最优解为x1=11,x2=125,即购买两种产品分别为11件和125件。总利润为533元。利润增加量为533-390=143。两者结果相同。585y1=58511/45=143元12121212max341015198553430,0zxxxxxxx x影子价格影子价格如果不按此决策进行投资，而采用其他方案，其利润增加量只能比143少。例如，考虑在585元资金中，将510元用于购买产品A1，A2，将75元用于增加仓库空间，75元可增空间为

8、93.75m3，得到的模型为：12121212max341015191053523.75,0zxxxxxxx x影子价格影子价格经求解可知，此模型的最优解为 x1=47.25,x2=95.85最大利润为525.15元，增量为525.15-390=135.15元。显然小于143元。 对偶单纯形法对偶单纯形法对偶单纯形法是求解原规划的一种方法，它采用了单纯形法和对偶的思想。 1.对偶单纯形法的基本思想： 对偶单纯形法从原规划的一个基本解出发，此基本解不一定可行，对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解(检验数非正)，所以也可以说是从一个对偶可

9、行解出发，然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解(检验数非正)，如果得到的基本解的分量皆非负，则该基本解为最优解。 对偶单纯形法对偶单纯形法注: 对偶单纯形法在迭代过程中始终保持对偶解的可行性(即检验数非正)，使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。 对偶单纯形法对偶单纯形法2.对偶单纯形法的主要步骤 (1) 根据线性规划的典式形式，建立初始对偶单纯形表，此表对应原规划的一个基本解。此表要求：检验数行各元素一定非正，原规划的基本解可以有小于零的分量

10、。 (2)若基本解的所有分量皆非负。则得到原规划的最优解，停止计算；若基本解中有小于零的分量 ，并且 所在行各系数 ，则原规划没有可行解，停止计算； 若 ，并且存在 ，则确定 为出基变量，并计算0lblb0lja0lb0lja lxmin|0jkljljlkaaa确定 为进基变量。若有多个 ，则选择其中最小的进行分析计算。kx0ib 对偶单纯形法对偶单纯形法若有多个 ，则选择其中最小的进行分析计算。0ib 上面求最小值的式子称为对偶 规则，它保证在经过迭代后得到的新表中，检验数行各元素非正。 (3)以 alk 为中心元素，按照与单纯形法类似的方法，在表中进行迭代计算，返回上一步。对偶单纯形法对

11、偶单纯形法例6.2 用对偶单纯形法求解下面线性规划 1212121212min323343632,0fxxxxxxxxx x解 引入松弛变量化为标准形，并在约束等式两侧同乘-1，得到1212312412512345max323343632,0zxxxxxxxxxxxx x x x x 对偶单纯形法对偶单纯形法松弛变量构成基变量，上式即为典式形式，并且检验数皆非正，因此可构造初始对偶单纯形表。 对偶单纯形法对偶单纯形法继续迭代： 对偶单纯形法对偶单纯形法在最后的单纯形表中，右侧列各元素皆非负，所以得到原规划的最优解为X=(3/5,6/5,0,0,11/5)T。注: 用对偶单纯形法求解此问题，只经

12、过两次迭代便得到了最优解。如果仍然采用单纯形法求解的话，在化成标准形式后，为得到初始基本可行解，需要加入3个人工变量，这样，为了得到问题的最优解，至少要迭代3次，让人工变量出基，显然，计算量将大大增加。对偶单纯形法对偶单纯形法例6.3 用对偶单纯形法求解下面线性规划12123124max221120,1,2,3,4jzxxxxxxxxxj 解 构造对偶单纯形表进行迭代，从最后的表中可以看到，右侧列元素有-20，并且-2所在行各元素解非负，因此，原规划没有可行解。对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法3.对偶单纯形法的适用范围对偶单纯形法适合于解如下形式的线性规划问题：11min,1,2,0,1,2,njjjnijjijjfc xa xb imxjn注1: 在引入松弛变量