《对偶单纯形与线性规划模型》由会员分享，可在线阅读，更多相关《对偶单纯形与线性规划模型（21页珍藏版）》请在金锄头文库上搜索。
1、最优化模型与实验第 40 页第二章第二章 对偶规划和灵敏度分析与实验对偶规划和灵敏度分析与实验2.1 对偶理论对偶理论线性规划的对偶理论不仅在理论上而且在实践上都是十分重要的。原问题与对偶问题的关系原问题与对偶问题的关系（原问题）0,min2121212112221112112211nmmmnmmnnnnxxxbbbxxxaaaaaaaaaxcxcxcLMM LMOMMLLL定义对偶问题为0,max2121211222111211212211nmmnmmnnmmmwwwcccaaaaaaaaawwwbwbwbwLLLMOMMLLLL使用向量与矩阵表示形式为0s.t.max)(0s.t.min)
2、(wcAwbwDxbAxxcPTTTT对偶规划的要点对偶规划的要点：（1）min 变成 max；（2）价值系数与右端向量互换； （3）系数矩阵转置；（4）按规则添上不等号。使用下表归纳为从正面看是原问题，旋转为对偶问题如下：90s.t.s.t.第二章 对偶规划和灵敏度分析与实验第 41 页wi jxnxxx 21原关 系Max y1w2wmwmnmmnnaaaaaaaaaLMOMMLL211222111211mbbbM21对偶关 系LyzmaxminMin zncccL21考虑标准形的线性规划（） P0s.t.minxbAxxcT把其中的等式约束变成不等式约束，可得0s.t.min xbbxA
3、AxcT其对偶问题是0s.t.max212121 wwcAAwwbbwwTTTT其中 w1和 w2分别表示对应约束 Axb和-Ax-b的对偶变量组，令w=w1-w2，则上述问题可表示成为() DTTTcAwbws.t.max线性规划的原问题和对偶问题的关系，其变换形式归纳为下表的对最优化模型与实验第 42 页应关系原问题（或对偶问题）对偶问题（或原问题） 目标函数 min z目标函数 max yn 个 m 个 0 0变量无约束=约束条件m 个 n 个 0 0约束条件 =无约 束变量约束条件右端项目标函数变量的系数 目标函数变量的系数约束条件右端项对偶问题的实际应用对偶问题的实际应用经济背景经济
4、背景解释原问题和对偶问题的关系模型模型 2.1 （营养问题） 某工厂所用的营养品由几种配料组成，要求这种营养品必须含有 m 种不同的营养成分，并且每份营养品中第i 种营养成分的含量不能低于。已知每单位的第 j 种配料中所含第ibi 种营养成分的量为，每单位的第 j 种配料的价格为。试确定在ijajc保证营养需要的条件下，使工厂所配制的营养品费用最小的配方法。建立模型原问题解：建立模型原问题解：设表示第 j 种配料的使用量，则为第 j 种jxjijxa配料含有第 i 种营养成份的数量。根据模型要求，营养品中第 i 种营养成份的含量不能低于，那么使用数学表达式来表示此约束为ib, i=1，2,，m
5、 njiiijbxa1第二章 对偶规划和灵敏度分析与实验第 43 页(2.1)并且考虑到非负约束为, j=1，2,，n.0jx分析目标函数，由于第 j 种配料单位的价格为，则为第 j 种配jcjjxc料总价格为。这样，营养品的总费用为jjxc(2.2) njjjxcz1综上所述，已得到工厂希望在保证营养价值的前提下，使营养品的费用最省的营养问题归结为下面的线性规划问题：jnjjxcz 1mins.t. , i=1，2,，m (2.3) njijijbxa1, j=1，2,，n.0jx对偶问题的经济解释对偶问题的经济解释 假定某公司想把这 m 种营养成分分别制成单一的产品销售给工厂。显然，为了保
6、证销路，价格不能太高，若含一个单位的第 i 种营养成分的产品定价为 wi (wi0)，因为营养品中，第 j 种配料每单位的价格为 cj，而它所含第 i 种营养成分的量为 aij，现要用 aij (i=1,m) 个单位的第 i 种产品才能代替它，因此为使工厂愿意采用产品来代替原来的营养品，必须使产品的价格满足下面的不等式。 njcwajmiiij, 1,1L 由于每份营养品中必须含有 bi个单位的第 i 种营养成分，因此这样最优化模型与实验第 44 页一份代营养品的价格就是。ywbmiii 1对于工厂来说，问题是如何确定每种营养品的售价 wi，使在满足价格的约束条件下，使 y 达到最大，从而使公
7、司的利润最大，即对偶规划为miwnjcwawbyijmiiijmiiiLL, 1, 0, 1,s.t.max112.2 对偶问题的基本性质对偶问题的基本性质1对称性对称性 对偶问题的对偶是原问题。2弱对偶性弱对偶性 设 x 和 w 分别是问题（P）和（D）的可行解，则(2.4)bwxcTT3无界性无界性 问题（P）和（D）同时有最优解的充分必要条件是它们同时有可行解。而且若其中有一个问题无界，则另一个问题无解。4强对偶性强对偶性 设 x*和 w*分别为（P）和（D）的可行解，则它们分别为 （P）和（D）的最优解当且仅当cTx*=(w*)Tb (2.5)5互补松弛性互补松弛性 设 x*和 w*分
8、别为原问题（P）和对偶问题（D）的可行解，则它们分别为（P）和（D）的最优解当且仅当，；，。 nijiijiwxab1*0)(mj, 2 , 1L mjijijjxwac1*0)(ni, 2 , 1L第二章 对偶规划和灵敏度分析与实验第 45 页(2.6) 使用矩阵形式，可得 x*和 w*的互补松弛性条件:w*(Ax*b)=0 ， (cw*A)x*=0 (2.6)归纳：归纳：一对对偶规划的最优解满足互补松弛性，如果将等式约束看成是起作用（临界）约束，把自由变量看成非起作用约束。那么有下面结论，设一对偶规划都有可行解，若原规划某一约束是某个最优解的非起作用（临界）约束，则它的对偶约束一定是对偶规
9、划所有最优解的起作用约束。6唯一性唯一性 问题（P）有非退化的最优基本可行解，那么其对偶规划(D)有唯一的最优解。7对偶变量的经济解释对偶变量的经济解释 假定所讨论的是下面的线性规划问题（P）0s.t.maxxbAxxcT其中 b 表示某工厂所拥有的 m 种资源的总量，aij表示生产每件第j 种产品需消耗第 i 种资源的量，该问题的实际背景是在资源有限的条件下安排生产，以使效益最大。影子价格影子价格 设有一个工业系统，它拥有 种不同生产工厂，生产n种社会所需的产品。已知一年内社会对第 种产品的最低需求量mi为，一年内一家第 类生产工厂的运行成本为，生产第 种产ibjjci品的数量为，那么，在保
10、证满足社会对种产品的需求量的前ijam提下，每种类型工厂各应投入多少家运行，才能保证成本最小？设为投入运行的第 类工厂数量，则jxj最优化模型与实验第 46 页njxmibxaxczjnjijijnjjj,2, 1,0,2, 1,s.t.min11LL设最优解为，对应的最优基，对偶最优解为，则最优值：*xB*w miiiwbz1*若现在社会对第 种产品的最低需求量出现变化，改变量为，iibib且此时最优基解不变，即仍是最优基，不变，则 z 的增量为，B*wz那么当改变量趋于 时，有ib0* i iwbz即是增加一个单位时，必须增加的成本，亦即一个单位的的最ib*zib低价格为，称为“影子价格”
11、 。若使用矩阵与向量形式来说明。设 iB 是问题（P）的最优基，由最优值知 （记bwbBczB*1）, 则1*BcwB(2.7)*1wBcbzB故可以看作当第 i 种资源从原来的量 bi增加一个单位时，目标* iw函数最优值的增加值。经济学家通常把 w*称为影子价格影子价格，也就是针对收益最大的产品生产安排，对资源所作的一种价格估计。即当某种资源的市场价格低于影子价格时，工厂买进该种资源安排生产将使收益增加；反之，工厂把该种资源卖出去将显得更为合适。第二章 对偶规划和灵敏度分析与实验第 47 页例例 2.1 某企业利用三种原料生产两种产品。三种原料321,BBB21, AA的月供应量，生产一吨
12、产品所消耗各种原料的数量及单位产品21, AA价格如下表所示。设生产的产品均可在市场销售，企业应如何21, AA安排月生产计划，使总收益最大。产品单位产品消耗 原料1A2A原料月供应量 （吨）321BBB233211300240150单位产品价格（万元吨）2.4 1.8设计划生产产品的数量为（吨月） ，则所讨论的问iAix2,1i题的数学模型为。 0, 03002324032150)(8 . 14 . 2max2121212121xxxxxxxxKxxz如果另一个公司想从该企业购买这三种原料，那么这三种原料的价格应是多少，双方才能都是合理的呢？建立对偶模型：设原料的价格为（万元吨） ，321,
13、BBB321,yyy显然，应有。由原问题的条件，生产一吨产品需消3,2,1,0iyi1A耗吨原料，吨原料，吨原料，可获得收益为 2.4 万元。1B2B3B因此若将生产一吨产品的这些原料卖出所得的收益为1A（万元）32132yyy最优化模型与实验第 48 页它必须不少于生产一吨产品所得的收益，对于该企业才是合算的。1A所以应有4 . 232321yyy对于产品，可类似得到2A8 . 123321yyy同时，若买方（公司）欲购买该工厂的全部原料，则应付出万元（这也是该工厂卖出全部原料的总收益） 。从321300240150yyy买方角度应使总支出尽可能的少。因此，可得到线性规划问题0, 0, 08
14、 . 1234 . 232)(300240150min321321321321yyyyyyyyyDyyyf不难看出问题（P）与问题（D）互为对偶问题。问题（P）的第个约束对应于对偶变量，问题（D）的最优解i3,2,1, iyi称为原料的影子价格。为了理解影子价格的含义，321,yyy321,BBB先求解问题（P） 。为此，先将问题（P）标准化，得 5,2,1, 03002324032150)(8 . 14 . 2max52142132121LjxxxxxxxxxxPxxzj问题（P）有初始可行基，由出发利用单纯形方法可),(5431PPPB 1B求得问题（P）的最优基，对应的单纯形法列表表示，
15、如下表所示。B1x2x3x4x5x第二章 对偶规划和灵敏度分析与实验第 49 页z8 .24472. 012. 0000321xxx8424426 . 04 . 0001 4 . 06 . 0010 2 . 02 . 0100由此可得，问题（P）的最优解和最优值8 .244; 004224,84max54321zxxxxx，表中松弛变量，表明原料还有 42 吨未被使用。423x同时，根据上表，立刻得到对偶问题（D）的最优解（单位：万元）72. 0;12. 0,0321yyy和最优值(万元)8 .24472. 030012. 02400150minf这表明：只有当该企业出让这批原料所获总收益与利用这批原料生产产品所获得的总收益相等时，出让这批原料才是合理
