对偶单纯形与线性规划模型.doc

第二章 对偶规划和灵敏度分析与实验第二章 对偶规划和灵敏度分析与实验2.1 对偶理论线性规划的对偶理论不仅在理论上而且在实践上都是十分重要的。 原问题与对偶问题的关系（原问题）s.t.定义对偶问题为s.t. 使用向量与矩阵表示形式为 对偶规划的要点：（1） min变成max；（2） 价值系数与右端向量互换； （3） 系数矩阵转置；（4） 按规则添上不等号。 使用下表归纳为从正面看是原问题，旋转为对偶问题如下： wi 原关系Max y对偶关系Min z 考虑标准形的线性规划 （） 把其中的等式约束变成不等式约束，可得其对偶问题是其中w1和w2分别表示对应约束Axb和-Ax-b的对偶变量组，令w=w1-w2，则上述问题可表示成为 () 线性规划的原问题和对偶问题的关系，其变换形式归纳为下表的对应关系原问题（或对偶问题）对偶问题（或原问题）目标函数min z目标函数max y变量 n个 m个约束条件00无约束=约束条件 m个 n个变量00=无约束约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项对偶问题的实际应用经济背景解释原问题和对偶问题的关系模型2.1 （营养问题） 某工厂所用的营养品由几种配料组成，要求这种营养品必须含有m种不同的营养成分，并且每份营养品中第i种营养成分的含量不能低于。已知每单位的第j种配料中所含第i种营养成分的量为，每单位的第j 种配料的价格为。试确定在保证营养需要的条件下，使工厂所配制的营养品费用最小的配方法。建立模型原问题解：设表示第j种配料的使用量，则为第j种配料含有第i种营养成份的数量。根据模型要求，营养品中第i种营养成份的含量不能低于，那么使用数学表达式来表示此约束为 , i=1，2,，m (2.1)并且考虑到非负约束为 , j=1，2,，n.分析目标函数，由于第j种配料单位的价格为，则为第j种配料总价格为。这样，营养品的总费用为 (2.2)综上所述，已得到工厂希望在保证营养价值的前提下，使营养品的费用最省的营养问题归结为下面的线性规划问题： s.t. , i=1，2,，m (2.3) , j=1，2,，n. 对偶问题的经济解释 假定某公司想把这m种营养成分分别制成单一的产品销售给工厂。显然，为了保证销路，价格不能太高，若含一个单位的第i种营养成分的产品定价为wi (wi0)，因为营养品中，第j种配料每单位的价格为cj，而它所含第i种营养成分的量为aij，现要用aij (i=1,m) 个单位的第i种产品才能代替它，因此为使工厂愿意采用产品来代替原来的营养品，必须使产品的价格满足下面的不等式。 。 由于每份营养品中必须含有bi个单位的第i种营养成分，因此这样一份代营养品的价格就是 。 对于工厂来说，问题是如何确定每种营养品的售价wi，使在满足价格的约束条件下，使y达到最大，从而使公司的利润最大，即对偶规划为 2.2 对偶问题的基本性质1对称性 对偶问题的对偶是原问题。2弱对偶性 设x和w分别是问题（P）和（D）的可行解，则 (2.4)3无界性 问题（P）和（D）同时有最优解的充分必要条件是它们同时有可行解。而且若其中有一个问题无界，则另一个问题无解。4强对偶性 设x*和w*分别为（P）和（D）的可行解，则它们分别为 （P）和（D）的最优解当且仅当 cTx*=(w*)Tb (2.5)5互补松弛性 设x*和w*分别为原问题（P）和对偶问题（D）的可行解，则它们分别为（P）和（D）的最优解当且仅当， ，；，。 (2.6) 使用矩阵形式，可得x*和w*的互补松弛性条件: w*(Ax*b)=0 ， (cw*A)x*=0 (2.6)归纳：一对对偶规划的最优解满足互补松弛性，如果将等式约束看成是起作用（临界）约束，把自由变量看成非起作用约束。那么有下面结论，设一对偶规划都有可行解，若原规划某一约束是某个最优解的非起作用（临界）约束，则它的对偶约束一定是对偶规划所有最优解的起作用约束。6唯一性 问题（P）有非退化的最优基本可行解，那么其对偶规划(D)有唯一的最优解。7对偶变量的经济解释 假定所讨论的是下面的线性规划问题 （P）其中b表示某工厂所拥有的m种资源的总量，aij表示生产每件第j种产品需消耗第i种资源的量，该问题的实际背景是在资源有限的条件下安排生产，以使效益最大。影子价格 设有一个工业系统，它拥有种不同生产工厂，生产种社会所需的产品。已知一年内社会对第种产品的最低需求量为，一年内一家第类生产工厂的运行成本为，生产第种产品的数量为，那么，在保证满足社会对种产品的需求量的前提下，每种类型工厂各应投入多少家运行，才能保证成本最小？设为投入运行的第类工厂数量，则设最优解为，对应的最优基，对偶最优解为，则最优值：若现在社会对第种产品的最低需求量出现变化，改变量为，且此时最优基解不变，即仍是最优基，不变，则z的增量为，那么当改变量趋于时，有即是增加一个单位时，必须增加的成本，亦即一个单位的的最低价格为，称为“影子价格”。若使用矩阵与向量形式来说明。设B是问题（P）的最优基，由最优值知 （记）, 则 (2.7)故可以看作当第i种资源从原来的量bi增加一个单位时，目标函数最优值的增加值。 经济学家通常把w*称为影子价格，也就是针对收益最大的产品生产安排，对资源所作的一种价格估计。即当某种资源的市场价格低于影子价格时，工厂买进该种资源安排生产将使收益增加；反之，工厂把该种资源卖出去将显得更为合适。例2.1某企业利用三种原料生产两种产品。三种原料的月供应量，生产一吨产品所消耗各种原料的数量及单位产品价格如下表所示。设生产的产品均可在市场销售，企业应如何安排月生产计划，使总收益最大。产品单位产品消耗原料原料月供应量（吨）单位产品价格（万元吨）2.4 1.8设计划生产产品的数量为（吨月），则所讨论的问题的数学模型为。如果另一个公司想从该企业购买这三种原料，那么这三种原料的价格应是多少，双方才能都是合理的呢？建立对偶模型：设原料的价格为（万元吨），显然，应有。由原问题的条件，生产一吨产品需消耗吨原料，吨原料，吨原料，可获得收益为2.4万元。因此若将生产一吨产品的这些原料卖出所得的收益为（万元）它必须不少于生产一吨产品所得的收益，对于该企业才是合算的。所以应有对于产品，可类似得到同时，若买方（公司）欲购买该工厂的全部原料，则应付出万元（这也是该工厂卖出全部原料的总收益）。从买方角度应使总支出尽可能的少。因此，可得到线性规划问题不难看出问题（P）与问题（D）互为对偶问题。问题（P）的第个约束对应于对偶变量，问题（D）的最优解称为原料的影子价格。为了理解影子价格的含义，先求解问题（P）。为此，先将问题（P）标准化，得问题（P）有初始可行基，由出发利用单纯形方法可求得问题（P）的最优基，对应的单纯形法列表表示，如下表所示。 由此可得，问题（P）的最优解和最优值表中松弛变量，表明原料还有42吨未被使用。同时，根据上表，立刻得到对偶问题（D）的最优解（单位：万元）和最优值(万元)这表明：只有当该企业出让这批原料所获总收益与利用这批原料生产产品所获得的总收益相等时，出让这批原料才是合理的。但应注意：“影子价格”并不是该原料的市场实际价格，而是在取得最大收益时，收益对于原料的边际收益值。实际上，由上表可得故上式亦可写成所以，当企业获最大收益时（这时，），有这表明：当增加一单位时，边际收益为零。这是因为原问题的最优解中，即原料尚有42吨未用完，再增加一单位（相当于减少原料的供应量一个单位）对总收益没有影响。但增加一单位时（这相当于原料的供应量由240（吨）减少到239（吨），总收益将减少0.12万元。或者说，当企业取得最大收益时，增加一单位原料的供应量，将使总收益增加0.12万元。对于原料可类似分析。以上分析对管理人员提供了十分有用的信息，例如，当原料的市场实际价格为0.1万元，低于影子价格万元时，企业管理者可购入原料以增加收益。同样，对于原料，尽管市场价格很便宜，但由于影子价格，也不应考虑再购入原料。由此看出，影子价格确实可为企业提供管理决策的参考信息。使用LINDO计算上述例。! Exampl 2.4!MAX 2.4X1 + 1.8X2 !SUBJECT TO!1) X1 + X2 = 1502) 2X1 + 3X2 = 2403) 3X1 + 2X2 = 300END 从LINDO菜单下选用SOLVE命令并进行灵敏度分析，可得解为：2.6 LINDO软件求解与灵敏度分析， 例2.2（工件加工任务分配问题） 某车间有两台机床甲和乙，可用于加工三种工件，假定这两台机床的可用台时数分别为700和800，三种工件的数量分别为300，500和400，且已知用不同机床加工单位数量的不同工件所属的台时数和加工费用（表2.1），问怎样分配机床的加工任务，才能既满足加工工件的要求，又使总加工费用最低？ 表2.1机床类型单位工件所需加工台时单位工件的加工费用可用工件I工件II工件III工件I工件II工件III台时数甲0.41.11.013910700乙0.51.21.311128800解：这三种工件既可在机床甲上加工，也可以在机床乙上加工，各种工件在机床甲和乙上的加工数量就是需要解决问题。 设在甲机床上加工的工件，和的数量分别为x1, x2和x3，在乙机床上加工工件,和的数量分别为x4, x5, x6，则根据这三种工件的数量限制，有再由机床甲和乙的可用总台时限制，有而总加工费用 综合上述各约束条件，可得该问题的数学模型如下： s.t. 此例的LINDO输入模型为：! Example ! MIN 13 X1 + 9 X2 + 10 X3 + 11 X4 + 12 X5 + 8 X6 !SUBJECT TO!1) X1 + X4 = 3002) X2 + X5 = 5003) X3 + X6 = 4004) 0.4 X1 + 1.1 X2 + X3 = 7005) 0.5 X4 + 1.2 X5 + 1.3 X6 = 800END !从LINDO菜单下选用SOLVE命令中若不进行灵敏度分析，则可得解为：从LINDO菜单下选用SOLVE命令并进行灵敏度分析，可得解为：从LINDO软件为此例编制的程序求解与进行灵敏度分析比较，可知灵敏度分析在此例中，可以获得更多的信息，更加充分地认识原问题和对偶问题的解在灵敏度分析中得重要作用。例23（厂址选择问题） 考虑A，B，C三地，每地都出产一定数量的原料，也消耗一定数量的产品（见表2.2），已知制成每吨产品需3吨原料，各地之间的距离为AB：150km，AC：100km，BC：200km。假定每万吨原料运输1km的运价是5000元，每万吨产品运输1km的运价是6000元。由于地区条件的差异，在不同地点设厂的生产费用也不同，问怎样在何处设厂，规模多大，才能使总费用最小？另外，由于其它条件限制，在B处建厂的规模（生产的产品数量）不能超过5万吨。表2.2地 点年产原料(万吨)年销产量(万吨)生产费用(万元/万吨)A207150B1613120C240100 解：令为由i地运到j地的原料数量（万吨），为由i地运往j地的产品数量（万吨），i,j=1,2,3（分别表示A，B，C三地），据题意有 由于，又因都是非负，从而有，这样可将此方程略去。若设为第i处的设厂规模（年产产品数量，万吨），则有 从而得到 将x11,x22和x33消去，并考虑y21+y225和变量非负条件，得约束条件如下：目标函数为（包括原材料运输费、产品运输费和生产费）：此例的LINDO输入模型为：! Exampl 2.2! MIN 75 X12 + 75 X21 + 50 X13 + 50 X31 + 100 X23 + 100 X32 +150 Y11 + 240Y12 +210 Y21 +120 Y22 + 160 Y31 + 220 Y32 !SUBJECT TO!1) 3 Y11 + 3 Y12 + X12 + X13 - X21 -X31 = 202) 3 Y21 + 3 Y22 - X12 + X21 + X23 -X32 = 163) 3 Y31 + 3 Y32 - X13 - X23 + X31 +X32 = 244) Y11 + Y21 + Y31 = 75) Y12 + Y22 + Y32 = 136) Y21 + Y22 = 5END !从LINDO菜单下选用SOLVE命令中若不进行灵敏度分析，可得解。从LINDO菜单下选用SOLVE命令并进行灵敏度分析，可得解。从LINDO软件为此例编制的程序求解与进行灵敏度分析比较，可知灵敏度分析在此例中，可以获得更多的信息，更加充分地认识原问题和对偶问题的解在灵敏度分析中得重要作用。例2.4 最佳连续投资方案 某部门在今后五年内考虑下列项目投资，已知项目1从第一年到第四年每年年初需要投资，并于次年末回收本利115%；项目2第三年年初需要投资，到第五年末能回收本利125%，但规定最大投资额不超过4万元；项目3第二年年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过3万元；项目4 五年内每年年初可购买公债，于每年末归还，并加利息6%。该部门现有资金10万元，问它应如何确定给这些项目每年的投资额。使到第 5年末拥有的资金的本利总额为最大？模型建立：这是一个与时间有关的连续投资问题，在此对该问题是将五年情况总体地静态考虑，不是按时间去动态地考虑。设表示第年年初投资给项目的资金额度（单位：万元），则各年的投资限制为第一年：第二年：年初拥有的资本额为，因此有；第三年：年初拥有的资金额为，因此有；同样的分析可得：第四年：；第五年：本问题是要制定投资方案使第五年末该部门拥有的资金额最大，即整理上述分析结果，本问题可表示为下面的数学问题满足约束条件上述模型中出现的函数都是线性函数，即为线性规划模型。此例的LINDO输入模型为： MAX 1.4Y23 + 1.25 Y32 + 1.15Y41 + 1.06Y54 SUBJECT TO 2) Y11 + Y14 = 10 3) Y11 -0.06Y14 +Y12 + Y23 + Y24 = 10 4) -0.15Y11-0.06Y14 + Y21 +Y23 -0.06Y24 + Y31 +Y32 +Y34 = 10 5) -0.15Y11-0.06Y14 -0.15Y21 +Y23 -0.06Y24 + Y31 +Y32 -0.06Y34+Y41+Y44 = 10 6) -0.15Y11-0.06Y14 -0.15Y21 +Y23 -0.06Y24 -0.15Y31 +Y32-0.06Y34+Y41-0.06Y44 +Y54= 10 7) Y23=3 8) Y32=4 END 从LINDO菜单下选用SOLVE命令并进行灵敏度分析，则可得解。2.7 投资的收益和风险组合问题98年全国大学生数学建模竞赛A题 介绍使用多目标规划来建立数学模型。此数学模型反映了可以通过数学转化成线性规划的模型。市场上有种资产（如股票、债券、）供投资者选择，某公司有数额为的一笔相当大的资金可用作一个时期的投资。公司财务分析人员对这种资产进行了评估，估算出在这一时期内购买的平均收益率为，并预测出购买的风险损失率为，考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的中最大的一个风险来度量。购买要付交易费，费率为，并且当购买额不超过给定值时，交易费按购买计算（不买当然无须付费）。另外，假定同期银行存款利率是，且既无交易费又无风险。） 当时的相关数据如下：(元)281103212198234.552256.540试给该公司设计一种投资组合方案，即用给定的资金，有选择的购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小。） 试就一般情