《对偶单纯形影子价格1ppt课件》由会员分享，可在线阅读，更多相关《对偶单纯形影子价格1ppt课件（22页珍藏版）》请在金锄头文库上搜索。
1、第三第三节 对偶偶单纯形法形法n 对偶单纯形法的根本思绪对偶单纯形法的根本思绪n用对偶原理求解原问题的一种用对偶原理求解原问题的一种方法，而不是求解对偶问题解的方法，而不是求解对偶问题解的单纯形法单纯形法n 对偶单纯形法的计算步骤对偶单纯形法的计算步骤前往前往前往前往继续继续返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题n书：定理书：定理4n 假设假设B是原规划的最优基，那么最优单纯形是原规划的最优基，那么最优单纯形乘子乘子n Y=CBB-1是其对偶规划的最优解。是其对偶规划的最优解。返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题基变量基变量非基变量非基变量当基变量
2、为当基变量为 时，新的单纯形表时，新的单纯形表当前检验数当前检验数当前基解当前基解返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题对对偶偶偶偶单纯单纯形法的根本思形法的根本思形法的根本思形法的根本思绪绪单纯形法的根本思形法的根本思绪：原原问题基可行解基可行解 最最优解判解判别对偶问题的可行解对偶问题的可行解对偶问题对偶问题最优解判别最优解判别对对偶偶偶偶单纯单纯形法形法形法形法根本思根本思根本思根本思绪绪C-CBB-1A0本本本本质质：保：保：保：保证证原原原原问题问题可行的条件下可行的条件下可行的条件下可行的条件下向向向向对对偶偶偶偶问题问题可行的方向迭代可行的方向迭代可行的方向
3、迭代可行的方向迭代返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题对偶偶单纯形法的形法的计算步算步骤n线性规划问题 无妨设 为对偶初始可行基，即 。 假设 ，即表中原问题和对偶问题均为最优解，否那么换基。对偶偶问题的的解可行解可行返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题确定换出基变量 对应变量 为换出基的变量确定换入基变量 为主元素， 为换入基变量返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题初始可行基例、用例、用例、用例、用对对偶偶偶偶单纯单纯形法求解形法求解形法求解形法求解线线性性性性规规划划划划问题问题：可作为可作为初始可行基初始可行基返回返
4、回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题例、用例、用例、用例、用对对偶偶偶偶单纯单纯形法求解形法求解形法求解形法求解线线性性性性规规划划划划问题问题：换入入 换出换出换出返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题例、用例、用例、用例、用对对偶偶偶偶单纯单纯形法求解形法求解形法求解形法求解线线性性性性规规划划划划问题问题：返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题最优解最优解例、用例、用例、用例、用对对偶偶偶偶单纯单纯形法求解形法求解形法求解形法求解线线性性性性规规划划划划问题问题：返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题n
5、n对偶偶单纯形法的形法的优点：点：n n不需求人工不需求人工变量；量；n n当当变量多于量多于约束束时，用，用对偶偶单纯形形法可减少迭代次数；法可减少迭代次数；n n在灵敏度分析中，有在灵敏度分析中，有时需求用需求用对偶偶单纯形法形法处置置简化。化。n n对偶偶单纯形法缺陷：形法缺陷：n n对初始初始单纯形表方式要求形表方式要求较严厉在在对偶偶问题可行的前提下，普遍可行的前提下，普遍适用性适用性较差。差。n n 因此，因此，对偶偶单纯形法普通不形法普通不单独独运用。运用。前往前往前往前往继续继续第四节 影子价钱在单纯形法的每步迭代中，目的函数取值 ，和检验数 中都有乘子 ，那么它的经济意义是什
6、么？ 返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题n书：定理书：定理4n 假设假设B是原规划的最优基，那么最优单纯形是原规划的最优基，那么最优单纯形乘子乘子n Y=CBB-1是其对偶规划的最优解。是其对偶规划的最优解。返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题n 当线性规划原问题求得最优解n时，其对偶问题也得到最优解 n，且代入各自的目的函数后有：是线性规划原问题约束条件的右端项，它代表第 种资源的拥有量；3返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题 对偶变量 的意义代表在资源最优利用条件下对单位第 种资源的估价，这种估价不是资源的市场价钱，
7、而是根据资源在消费中作出的奉献而作的估价，为区别起见，称为影子价钱shadow price)。影子价影子价钱的定的定义返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题n1资源的市场价钱是知数，相对比较稳定，而它的影子价钱那么有赖于资源的利用情况，是未知数。由于企业消费义务、产品构造等情况发生变化，资源的影子价钱也随之改动。影子价影子价钱的的经济意意义市场价钱影子价钱市场企业返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题影子价影子价钱的的经济意意义n2影子价钱是一种边沿价钱。n 在3式中， 。 n 阐明 的值相当于在资源得到最优利用的消费条件下， 每添加一个单位时目的函
8、数 的增量。返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题引例数学模型对偶偶问题最最优解解返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题n几何解几何解释：引例：引例图解法分析。解法分析。3，315/4，5/4,z=8.757/2，3/2，z=8.5返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题影子价影子价钱的的经济意意义3资源的影子价钱实践上又是一种时机本钱. 在纯市场经济条件下,当第2种资源的市场价钱低于1/4时，可以买进这种资源；相反当市场价钱高于影子价钱时，就会卖出这种资源。随着资源的买进卖出，它的影子价钱也将随之发生变化，不断到影子价钱与市场价钱坚持同等程度时，才处于平衡形状。返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题n4从影子价钱的含义上调查单纯形表的n 检验数的经济意义。4第j种产品的利润消费第j中产品所耗费各项资源的影子价钱的总和。即隐含本钱可可见，产品品产值隐含本含本钱 可消可消费该产品；品；否那么，不安排消否那么，不安排消费。检验数的数的经济意意义返回返回返回返回上上上上页页下下下下页页对对偶偶偶偶问问题题影子价影子价钱的的经济意意义n5普通说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解那么是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。经济学研讨如何管理本人的稀缺资源
