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

《对偶单纯形与线性规划模型》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第二章对偶规划和灵敏度分析与实验第二章对偶规划和灵敏度分析与实验§2.1对偶理论线性规划的对偶理论不仅在理论上而且在实践上都是十分重要的。原问题与对偶问题的关系（原问题）s.t.定义对偶问题为s.t.使用向量与矩阵表示形式为对偶规划的要点：（1）min变成max；（2）价值系数与右端向量互换；（3）系数矩阵转置；（4）按规则添上不等号。使用下表归纳为从正面看是原问题，旋转为对偶问题如下：第59页第二章对偶规划和灵敏度分析与实验wi原关系Maxy对偶关系Minz考虑标准形的线性规划（）把其中的等式约束变成不等式约束，可得其对偶问题是其中w1和w2分

2、别表示对应约束Ax≥b和-Ax≥-b的对偶变量组，令w=w1-w2，则上述问题可表示成为()第59页第二章对偶规划和灵敏度分析与实验线性规划的原问题和对偶问题的关系，其变换形式归纳为下表的对应关系原问题（或对偶问题）对偶问题（或原问题）目标函数minz目标函数maxy变量n个m个约束条件≥0≥≤0≤无约束=约束条件m个n个变量≤≥0≥≤0=无约束约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项对偶问题的实际应用经济背景解释原问题和对偶问题的关系模型2.1（营养问题）某工厂所用的营养品由几种配料组成，要求这种营养品必须含有m种不同的

3、营养成分，并且每份营养品中第i种营养成分的含量不能低于。已知每单位的第j种配料中所含第i种营养成分的量为，每单位的第j种配料的价格为。试确定在保证营养需要的条件下，使工厂所配制的营养品费用最小的配方法。建立模型原问题解：设表示第j种配料的使用量，则为第j种配料含有第i种营养成份的数量。根据模型要求，营养品中第i种营养成份的含量不能低于，那么使用数学表达式来表示此约束为,i=1，2,…，m(2.1)第59页第二章对偶规划和灵敏度分析与实验并且考虑到非负约束为,j=1，2,…，n.分析目标函数，由于第j种配料单位的价格为，则为第j种配料总价格为。这样

4、，营养品的总费用为(2.2)综上所述，已得到工厂希望在保证营养价值的前提下，使营养品的费用最省的营养问题归结为下面的线性规划问题：s.t.,i=1，2,…，m(2.3),j=1，2,…，n.对偶问题的经济解释假定某公司想把这m种营养成分分别制成单一的产品销售给工厂。显然，为了保证销路，价格不能太高，若含一个单位的第i种营养成分的产品定价为wi(wi≥0)，因为营养品中，第j种配料每单位的价格为cj，而它所含第i种营养成分的量为aij，现要用aij(i=1,…,m)个单位的第i种产品才能代替它，因此为使工厂愿意采用产品来代替原来的营养品，必须使产品

5、的价格满足下面的不等式。。由于每份营养品中必须含有bi个单位的第i种营养成分，因此这样一份代营养品的价格就是第59页第二章对偶规划和灵敏度分析与实验。对于工厂来说，问题是如何确定每种营养品的售价wi，使在满足价格的约束条件下，使y达到最大，从而使公司的利润最大，即对偶规划为§2.2对偶问题的基本性质1．对称性对偶问题的对偶是原问题。2．弱对偶性设x和w分别是问题（P）和（D）的可行解，则(2.4)3．无界性问题（P）和（D）同时有最优解的充分必要条件是它们同时有可行解。而且若其中有一个问题无界，则另一个问题无解。4．强对偶性设x*和w*分别为（P

6、）和（D）的可行解，则它们分别为（P）和（D）的最优解当且仅当cTx*=(w*)Tb(2.5)5．互补松弛性设x*和w*分别为原问题（P）和对偶问题（D）的可行解，则它们分别为（P）和（D）的最优解当且仅当，，；，。(2.6)使用矩阵形式，可得x*和w*的互补松弛性条件:w*(Ax*–b)=0，(c–w*A)x*=0(2.6’)第59页第二章对偶规划和灵敏度分析与实验归纳：一对对偶规划的最优解满足互补松弛性，如果将等式约束看成是起作用（临界）约束，把自由变量看成非起作用约束。那么有下面结论，设一对偶规划都有可行解，若原规划某一约束是某个最优解的非

7、起作用（临界）约束，则它的对偶约束一定是对偶规划所有最优解的起作用约束。6．唯一性问题（P）有非退化的最优基本可行解，那么其对偶规划(D)有唯一的最优解。7．对偶变量的经济解释假定所讨论的是下面的线性规划问题（P）其中b表示某工厂所拥有的m种资源的总量，aij表示生产每件第j种产品需消耗第i种资源的量，该问题的实际背景是在资源有限的条件下安排生产，以使效益最大。影子价格设有一个工业系统，它拥有种不同生产工厂，生产种社会所需的产品。已知一年内社会对第种产品的最低需求量为，一年内一家第类生产工厂的运行成本为，生产第种产品的数量为，那么，在保证满足社会

8、对种产品的需求量的前提下，每种类型工厂各应投入多少家运行，才能保证成本最小？设为投入运行的第类工厂数量，则第59页第二章对偶规划和灵敏度