对偶理论PPT课件

运筹学一师惠平，1，第二章对偶理论，2.1对偶问题，2.2灵敏度分析，2.3对偶单纯形法，运筹学一师惠平，2，2016/3/23，2.1对偶理论，1，对偶问题的命题2，本原问题和对偶问题的变换规则3，对偶问题的性质，1，对偶问题的命题，解：设x1为每周生产的产品数；X2是每周生产的二号产品的数量。线性规划模型为：生产线1时限，生产线2时限，生产线3时限。运筹学史惠平，4，2016/3/23。一家公司用2号和3号生产线生产产品，最低利润为500元。从另一个角度来看，它出售资源而不生产。解决方案是将y1、y2和y3设置为生产线1、2和3每周的单位时间销售成本。应满足Y1、y2和y3。这家资源收购公司希望以最低成本收购一家公司的三条以上生产线。因此，使用生产线1和3生产产品1的公司的最低利润是300元和总成本(100元)。注：在建立对偶问题的过程中，每个对偶变量都与原问题的一个约束条件相关。运筹学一师惠平，5，2016/3/23，原始问题和对偶问题，运筹学一师惠平，6，2016/3/23，原始问题和对偶问题的比较，原始问题和对偶问题在经济意义和数学形式上都是紧密联系的。从经济学的角度来看，最初的问题是找到最佳的生产计划，以便获得最大的收入。二元性问题是寻找总成本最小化的最佳价格。从数学模型的形式来看，它们也是相关的。它的一般形式是。运筹学史惠平，7，2016/3/23，原始问题与对偶问题的标准形式比较。运筹学史惠平，2016年3月8日，原始问题与对偶问题的标准形式比较。运筹学史惠平，9，2016/3/23。第二，线性规划原始问题和对偶问题的变换规则。运筹学I师惠平，10，2016/3/23，例如：写二元规划的下列线性规划。运筹学一史惠平，11，2016/3/23，解：线性规划有3个变量 3个约束：x1，x2变量0 1，2个约束,x3变量无约束3个约束=，3个约束3个变量：1个约束 1个变量0，2个约束 1个约束运筹学一史惠平，12，2016/3/23，3。线性规划对偶问题的基本性质(理论)(7)，1)对称性线性规划对偶问题的对偶问题正是原始问题。2)弱对偶假设X是原规划(P)的任何可行解，Y是对偶规划(D)的任何可行解，那么CTXbTY3)无界如果原问题(对偶问题)是无界解，那么它的对偶问题(原问题)没有可行解(逆命题不成立)。4)可行解是最优解的性质(最优性)设X是原问题的可行解，Y是对偶问题的可行解。当CTX=bTY时，x和y都是最优解。运筹学师惠平，13，2016/3/23，5)强对偶(对偶定理)如果原规划有最优解，那么对偶规划也有最优解，且其最优解的最优值是相同的。可以证明(p)和(d)的解一般有以下三种情况：两个问题都有有限的最优解；(2)任何一个问题都没有可行的解决办法；(3)一个问题有无界解，而另一个问题没有可行解。运筹学一师惠平，2016年3月14日。运筹学，石惠平，15，2016/3/23，双重约束。对于问题p和问题d，我们可以在它们的每个m-n约束中建立对偶关系：ailxlai2x2.ainxn bi且yi 0 (I=1，2，m)称为一对双重约束。Xj0且aljy1a2jy2.amjym CJ (j=1，2，n)也被称为一对对偶约束。如果每个最优解都能使约束相等，则约束条件称为紧约束。不是严格约束的约束是松散约束。运筹学一师惠平，16，2016/3/23，原始问题和对偶问题的对偶约束，运筹学一师惠平，17，2016/3/23，原始问题和对偶问题的对偶约束，maxz=5x1 x2-3x32x 12 x2-x31x 1-3x24x 3102 x12x 2 x3=5x10x 20x 3无约束，Minw=y 110y 25y 32y 1 y2y 352 y1-3y 2y 31-y 144运筹学史惠平，18，2016/3/23，6)线性规划问题最优解中的互补松弛，如果一个约束条件对应的对偶变量值是非零的，那么该约束条件取一个严格的方程；另一方面，如果约束条件取严格不等式，其对应的对偶变量必须为零。让XJ * (j=1，n)，Yi * (i=1，m)是线性规划问题的最优解。如果yi * 0，则有ailxl * ai2x2 *.ainxn *=bi，即xsi *=0if ailxl * ai2x2 *.ainxn * 0，则有yi *=0(当互补松弛应用于其对偶问题时，类似地可用：如果xj * 0，则有aljyl * a2jy2 *.amjym *=CJif aljyl * a2jy2 *.amjym * CJ，然后xj)，方程I的松弛变量，运筹学师惠平，19，2016/3/23，互补松弛：y1 *=0y2 *=3/2y3 *=1，x142x2=123x12x2=18、x14x2=6x1=2，运筹学师惠平，20，2016/3/23，和7)测试基元问题的单纯形表中的测试数对应于但不满足非负约束)，最后测试下表、单纯形表、最终表，基本解Y1=0，Y2=5/2，Y3=0对应对偶问题，最优解Y1 *=0，Y2 *=3/2，Y3 *=1对应对偶问题。 运筹学一师惠平，21，2016/3/23，双重变量与影子价格的经济意义，影子价格是双重问题中的资源价格，在原问题中，即最后表中检验放松变量的个数。(对偶问题的最优解是影子价格)(1)如果影子价格大于零，增加一个单位的资源将影子价格贡献给目标函数；(2)影子价格等于零，增加一个单位的资源不会有助于目标函数。(3)如果影子价格小于零并且增加了一个单位的资源，对于目标函数，影子价格将被降低。运筹学一师惠平，2016年3月22日，影子价格分析，资源1的影子价格为0；将资源增加一个单位对目标函数没有贡献。资源2的影子价格是3/2；增加一个单位的资源2对目标函数有3/2的贡献；资源3的影子价格是1；将资源增加3个单位有助于实现目标函数。目标函数maxz=3x 15 x20x 30 x40x 5约束x1 x3=42x2x2x 4=123 x12x 5=18x 1，x2，x3，x4，x50，资源从45目标函数不变，资源从1213目标函数增加3/2，资源从1819目标函数增加1，运筹学史惠平，23，2016年3月23日，影子价格的有效范围和影子价格的有效范围(这个问题在敏感性中讨论).运筹学史惠平，2016年3月24日，例：某企业需要消耗一种原材料甲和一种劳动力乙来生产两种产品。生产消耗参数如下表所示。询问企业如何生产才能使销售利润最大化。注：a产品的利润为23-(25，110)=3(元)，b产品的利润为40-(35，210)=5(元)。运筹学一师惠平，2016年3月25日，方案1:(成本直接反映在目标函数中)。如果每天生产x1和x2件A和B产品，并且每天消耗x3单位的原材料A和劳动力B达x4小时，则数学规划模型为，总利润=收入-成本，每天生产A和B消耗的原材料A为x3单位，每天生产A和B消耗的劳动力B为x4小时，每天材料A、每天劳动力B，决策变量的非负约束，最优解：x1=5，x2=5，x3=25，X4=15最佳值z=40。双重价格y=(6，11，1，1)，资源：原材料a和劳动力b的影子价格：6，11。系统中原料甲的实际价值为6元，比成本高1元，即每增加一个单位甲，公司净收益为1元。系统中劳动力B的实际价值为11元，比成本高1元，即每增加一个单位，公司的净收入为1元。运营研究一师惠平，2016年3月26日，解决方案2:(成本隐含地反映在目标函数中)。假设每天生产x1和x2个A和B产品，数学程序双重价格Y=(1，1)。如果加入原料甲，劳务乙公司可以分别获得1元和1元的净利润。运筹学一师惠平，2016年3月27日，对偶问题的基本要求，要求掌握原始问题与其对偶问题之间的对应关系，并能熟练、准确地写出一般线性规划的对偶问题。根据原线性规划的最优解，可以得到对偶问题的最优解。运筹学一，石惠平，28，2.2敏感性分析一，资源量变化分析二，价值系数变化分析三，新增变量分析四，约束矩阵变化分析五，新增约束条件分析五。运筹学I师惠平，29，2016/3/23，敏感性分析又称敏感性分析，它主要研究c，b，a波动对最优解的影响程度，包括以下两个方面：1 .当参数在什么范围内变化时，原始最优解或最优基不会改变。2.当模型改变时(增加或减少约束、变量、参数改变)，原始最优解或最优基如何改变，以及如何以最简单的方式获得最优解。定义：灵敏度分析是指当一个或多个分析系数发生变化时，所得到的线性规划问题的最优解的变化。或者在这些系数变化的范围内，线性规划问题的最优解或最优基保持不变。运筹学一，石惠平，30，2016/3/23，敏感性分析步骤。1.参数的变化反映在最终的单纯形表中。具体计算方法是根据公式计算最终单纯形表中相关数据的变化。2.检查最终单纯形表的原问题和对偶问题是否仍然是可行的解决方案，并根据不同情况按照下表采取相应的步骤。运筹学一师惠平，31，2016/3/23，灵敏度分析可按下表处理：运筹学一师惠平，32，2016/3/23，对称形式线性规划问题的矩阵表达式加松弛变量x，运筹学一师惠平，33，2016/3/23，用单纯形法计算的矩阵描述(初始单纯形表和最优单纯形表)，1。用初始单纯形法计算时，以I为初始基的相应基变量为Xs。2.迭代之后，新的基变量是XB。3.对偶问题的最优解Y*=CBB-1，所以最优解的值可以在最终的单纯形中找到。此时的基础称为最佳基础。初始基本变量，基本解，测试数，运筹学，史惠平，34，2016/3/23，生产调度计划模型：(数据，初始单纯形表，最终单纯形表)，3 c=c1，12 b=b2，增加x6，3 a31=a31，运筹学，史惠平，35，2016/3/23，初始单纯形表：A，I，B，运筹学，史惠平资源数量bi变化分析：bi变化分析反映了资源的变化。在原始最优单纯形表的右边再取一次值，此时最优基数不变。此时，最优解发生了变化，最优值也发生了变化。运筹学一师惠平，38，2016/3/23，二。价值系数变化分析(如C1):价值系数的变化只影响测试数字的变化。在原始最优单纯形表上重新计算测试数。如果所有的测试数都小于或等于零，则最佳基不变。此时，最优解不变，但最优值发生了变化。运筹学史惠平，39，2016/3/23，3。添加新变量xj的分析：添加新变量xj实际上反映为添加新产品。使用原始最优单纯形表来计算检验数(即，对应于新添加变量的检验数)。如果检验数小于或等于零，则最佳基准不会改变。此时，添加产品对企业没有好处。当测试次数大于零时，原来的最优基不再是最优基。这时，增加产品的产量对企业是有益的，但必须继续使用单纯形法来寻找最优解。运筹学史惠平，40，2016/3/23，4。约束矩阵共同执行活动的变化分析：约束矩阵共同执行活动的变化反映在(1) xj是一个非基本变量，可称为“xj加新变量分析”；(2) XJ是一个基本变量，那么共同执行活动的变化将改变相应的B and B-1，而原来的问题和双重问题都可能是不可行的解决办法。首先需要引入人工变量将其转化为可行解，然后用单纯形法求解。添加约束分析：添加约束相当于在实际工作中添加一个过程。(1)将原问题的最优解代入新增加的约束条件，如果满足，说明新增加的约束条件没有起到限制作用，原最优解保持不变。(2)新添加的约束直接反映在最终的单纯形表中，以供进一步分析。如果解(指原问题)仍然可行，则用单纯形法迭代求解。如果解不可行且对偶问题的解是可行的，则用对偶单纯形法迭代求解。运筹学师惠平，41，2016/3/23，数学模型，P6案例1.1解法：设x1为我每周生产的产品数量；X2是每周生产的二号产品的数量。线性规划模型是。运筹学史惠平，42，2016/3/23，敏感性分析。原问题的可行基础是：slackC1，x2，x1。从计算结果可以看出，目标函数系数的变化范围和权值(资源限制值)的变化范围为0C17.5；2C2；2B1；6B218；12b324 .(注意：奇点可能发生在临界点)，在此范围内，最佳基础保持不变。在这些范围内，约束的双重价格不会改变。Cj“最佳解决方案范围”:指最佳解决方案(最佳基础也保持不变)保持不变的范围。目标函数的系数可行允许上下界，可行允许等式右边的上下界。运筹学史惠平，43，2016/3/23，什么是成本降低？当第二资源的上限是24时，非基变量x1的降低成本是-4.5。运筹学一师惠平，44，2016/3/23，例1:一家工厂计划生产两种产品a和b(假设产品销售良好)。单位产品的利润和所需的劳动力、设备时间和原材料消耗如下表所示。如何安排生产以使工厂获得最大利润？当最佳基保持不变时，也计算目标函数c2和右侧项b3的变化