运筹学第2章教材课件学习资料

第2章对偶规划2.1对偶问题的提出2.2对偶问题的数学模型2.3对偶问题的性质2.4对偶单纯形法2.5灵敏度分析与参数分析返回2.1对偶问题的提出【例2-1】某厂拟在计划期(如一周)内安排生产甲、乙两种产品，经预测，生产每单位产品所消耗的原材料、设备工时以及所获利润情况如表2-1所示。假设所生产的产品能全部售出，问:该厂在计划期内如何安排生产才能获得最大的利润?为保持利润水平不降低，资源出售或出租的最低价格应是多少?解:这是一个已知资源、求利润最大化的生产计划问题，根据题意，可设甲、乙产品的产量分别为x1和x2，则该线性规划问题数学模型为下一页返回上一页2.1对偶问题的提出同时，也可以将A,B,C,D四种资源出售或出租以获得利润，假设出售材料A和B及出租设备C和D所得单位利润分别为y1,y2,y3和y4(千元)，为解决上述问题需要同时满足以下三个条件:①保持利润水平不降低。用于生产两种产品的资源若将其出售和出租，应不低于自行生产带来的利润，于是有“2y1+y2+4y3+0y4≥2”和“2y1+2y2+0y3+4y4≥3”成立。②资源价格最低。为使资源成功出售和出租，希望价格越低越好，因此:minW=12y1+8y2+16y3+12y4。下一页返回上一页2.1对偶问题的提出③资源价格非负。资源出售和出租的价格不能为负值，因此必须满足:y1，y2，y3，y4≥0。综上，可以获得一个新的数学模型:模型(1-1)与模型(2-2)互为对偶模型，可看出两者的参数之间存在对应关系。返回上一页2.2对偶问题的数学模型2.2.1常规线性规划模型的对偶形式原问题数学模型可用矩阵形式表达:若原问题具有最优解，其检验数必定小于或等于零，即σ≤0或C-

CBB-1A≤0。令Y=CBB-1，则有不等式C-YA≤0或YA≥C成立。由于松弛变量XS对应价格向量CS=0，则有不等式σS=CS-CBB-1I≤0或CBB-1≥0(即Y≥0)成立。同时，希望资源价格Y和数量b的乘积越小越好，即minW=Yb，则对偶问题见数学模型(2-4)，本教材称模型(2-3)和模型(2-4)为常规形式。下一页返回2.2对偶问题的数学模型2.2.2非常规线性规划模型的对偶形式本教材定义“约束条件为等式”或“决策变量取值无约束”的模型为非常规模型。(1)约束条件为等式。若原问题模型为下一页返回上一页2.2对偶问题的数学模型因AX=b<=>b≤AX≤b，原模型可转化为根据模型(2-3)和模型(2-4)可转化为对偶形式，化简过程如下:下一页返回上一页2.2对偶问题的数学模型最终得到非常规线性规划问题的对偶模型为(2)决策变量取值无约束。已知线性规划模型:令X=X′-X″，模型转化过程如下:下一页返回上一页2.2对偶问题的数学模型即2.2.3原问题与对偶问题模型对应关系通过对常规和非常规对偶模型的推导，可得出原问题与对偶问题模型的对应关系，如表2-2所示。根据表中对应关系，不仅可以快速写出一般线性规划问题模型的对偶形式，也可以求出特殊线性规划问题(如运输问题)模型的对偶形式。返回上一页2.3对偶问题的性质2.3.1对称性定理对称性定理:对偶问题的对偶是原问题。[2-9]证明模型(2-4)是模型(2-3)的对偶形式。证明:首先对模型(2-4)做出如下处理:目标函数等式两端同乘以“-1”，则“min(-W)=Y(-b)”成立。约束条件两端同乘以“-1”则“Y(-A)≤(-C)”成立，则模型(2-4)变为下一页返回2.3对偶问题的性质令W′-W，则模型(2一9)变为设对偶变量为X,Z′=-Z，写出其对偶形式目标函数等式两端同乘“-1"，约束不等式两端同乘“-1"，模型(2-11)变为下一页返回上一页2.3对偶问题的性质显然，模型(2-12)与模型(2-3)相同。证毕。对称性定理说明，原问题的对偶形式对应于对偶问题，对偶问题的对偶形式是原问题。对于两个互为对偶的问题，可以将其中任何一个问题当作原问题，另外一个则是对偶问题。2.3.2弱对偶定理弱对偶定理:设X和Y分别是原问题和对偶问题的可行解，则必有CX≤Yb.下一页返回上一页2.3对偶问题的性质证明:对于原问题和对偶问题模型(2-3)和模型(2-4)，

X是原问题的可行解，则有:AX≤b,X≥0;Y是对偶问题的可行解，则有YA≥C,Y≥0。在“AX≤b”两端左乘“Y”，有YAX≤Yb;在“YA≥C”两端右乘“X”，有YAX≥CX。因此，不等式"CX≤AX≤Yb”成立，即CX≤Yb。证毕。推论:原问题P和对偶问题D有最优解的充要条件是它们同时具有可行解。证明:①必要条件:若P和D有最优解，则它们同时有可行解。下一页返回上一页2.3对偶问题的性质②充分条件:若P和D同时有可行解，那么它们有最优解。2.3.3强对偶定理强对偶定理可以有三种表述形式:第一种:原问题P(max)有最优解的充要条件是对偶问题D(min)有最优解，且两个问题的最优目标函数值相等。证明:必要性。若原问题有最优解，则对偶问题有最优解。①存在性。②相等性。充分性可由对称性定理得到证明。证毕。下一页返回上一页2.3对偶问题的性质第二种:对于原问题P(max)和对偶问题D(min)，若P无界，则D不可行;若D无界，则P不可行。该定理可由弱对偶定理证明。需要注意的是:该定理的逆不成立。因为，当P无可行解时，其对偶问题或者无可行解，或者具有无界解。第三种:若X和Y分别是P(max)和D(min)的可行解，则它们分别为原问题和对偶问题最优解的充要条件是CX*=Y*b。强对偶定理表明，当原问题(或对偶问题)达到最优时，对偶问题(或原问题)也一定达到最优，且两者对应的最优目标函数值相等。下一页返回上一页2.3对偶问题的性质2.3.4互补松弛定理互补松弛定理:如果x和Y分别为原问题和对偶问题的可行解，它们分别为原问题和对偶问题最优解的充要条件是:(C-YA)X=0与Y(b-AX)=0。证明:必要性。若X和Y分别为原问题和对偶问题最优解，则(C-YA)X=0与Y(b-AX)=0同时成立。X和Y分别为原问题和对偶问题的可行解，则AX≤b,YA≥C.充分性。如果X和Y分别为原问题和对偶问题的可行解，它们分别为原问题和对偶问题最优解的充要条件是:(C-YA)X=0与Y(b-AX)=0。下一页返回上一页2.3对偶问题的性质互补松弛定理经常表示为:该定理表明，在线性规划问题的最优解中，如果对应某一约束条件的对偶变量取值为非零，则该约束条件为严格等式;反之，如果原问题约束条件为严格不等式，则其对应的对偶变量一定为零。2.3.5对偶最优解定理最优解定理表达了原问题最终单纯形表中变量的检验数与对偶问题最优解之间的关系。在原问题最终单纯形表中，松弛变量检验数的相反数对应于对偶问题原变量的取值，原变量检验数的相反数对应于对偶问题松弛变量的取值。这个定理与两个互为对偶问题的最优解有关，因此本教材称其为“对偶最优解定理”。下一页返回上一页2.3对偶问题的性质2.3.6影子价格(1)影子价格的提出。影子价格(ShadowPrice)又称计算价格、预测价格、最优价格，是荷兰经济学家詹恩·丁伯根在20世纪30年代末首次提出来的，并将其定义为“在均衡价格的意义上表示生产要素或产品内在的或真正的价格”。萨缪尔逊认为，“影子价格反映资源在得到最佳使用时的价格”。联合国把影子价格定义为“一种投入(比如资本、劳动力和外汇)的机会成本或它的供应量减少一个单位给整个经济带来的损失”。影子价格是运用线性规划的数学模型计算得出的，是反映社会资源获得最佳配置的一种价格。下一页返回上一页2.3对偶问题的性质关于影子价格，存在着不同的表述:影子价格是资源和产品在完全自由竟争市场中的供求均衡价格;影子价格是没有市场价格的商品或服务的推算价格，它代表着生产或消费某种商品的机会成本;影子价格为商品或生产要素的边际增量所引起的社会福利的增加值。

(2)影子价格的含义。下面以生产计划问题为例，说明影子价格的含义。在线性规划问题模型中，右端项表示资源的限制使用量，当某一项资源增加一个数值后，目标函数得到新的最大值时，目标函数最大值的增量与资源的增量的比值，就是这项资源的影子价格。也就是说，影子价格是在其他条件不变的情况下，单位资源变化所引起的目标函数最优值的变化，即单位资源对目标函数值的贡献。下一页返回上一页2.3对偶问题的性质影子价格可以直接利用对偶模型求得。然而，在线性规划中，有限资源的配置与价格互为对偶问题，从经济意义上看，有限资源的配置与价格则是同一问题的两个方面，所以既能解决有限资源最佳配置问题，也能解决最优价格一影子价格问题。当使用单纯形法求解线性规划问题时，对偶问题的最优解就是影子价格。求影子价格时可不用求解原问题的对偶问题，根据对偶最优解定理，只需要将原问题最终单纯形表中的松弛变量的检验数乘以“-1”，就得到了对偶问题的最优解，也就是原问题约束条件右端常数项所对应资源的影子价格。这种方法通常用于求解影子价格。

(3)影子价格的经济解释。下一页返回上一页2.3对偶问题的性质日常生活中，影子的大小随光线的不同而不同。影子价格就如同市场价格的影子，可以高于或低于市场价格。当影子价格低于市场价格时，说明某项资源用于生产所带来的收益小于用于出售获得的收益，应优先考虑出售资源;当影子价格高于市场价格时，说明某项资源用于生产所带来的收益大于用于出售获得的收益，应将资源用于生产。因此，影子价格是一种机会成本，可为生产管理者、决策者提供决策依据。在市场经济条件下，当某种资源的市场价格低于影子价格时，可以买进这种资源，扩大生产;相反地，当市场价格高于影子价格时，可卖出这种资源来获取更大的利润。下一页返回上一页2.3对偶问题的性质当然随着资源的买卖，它的影子价格也将随之发生变化，直到影子价格与市场价格相等时，即可停止资源的买卖。(4)影子价值与影子价格。事实上，价值和价格是两个不同的概念，因此影子价值不同于影子价格。影子价值含义比较广泛，既包括影子价格，也包括影子利润。因此，在解决实际问题时，应对影子价值和影子价格进行区分:若原问题求利润最大，则对偶问题最优解就是影子利润;若原问题求产值最大，则对偶问题最优解就是影子价格。影子价格和影子利润存在以下关系:影子价格=资源成本+影子利润(2-13)返回上一页2.4对偶单纯形法2.4.1原理与特点

(1)定义与原理。对偶单纯形法是用对偶性质求解线性规划问题的一种方法。不要误解为专门用于求解对偶问题的单纯形法。通过对普通单纯形法和对偶单纯形法的比较可以找到对偶单纯形法的求解思路。普通单纯形法:在迭代过程中，在保持原问题可行(XB=B-1b≥0)的条件下，向对偶问题可行(YA≥C)的方向迭代，从而实现σ=C-CBB-1A≤0(C-YA≤0或YA≥C)。与此相反，对偶单纯形法的思路是在保持对偶问题可行(C-CBB-1A≤0)的条件下，向原问题可行(B-1b≥0)的方向迭代，最终实现XB≥0。下一页返回2.4对偶单纯形法(2)特点。对偶单纯形法具有以下优点:①初始解是非可行解时，无须引入人工变量，可以简化计算;②若约束方程个数(m)较少时，计算更加方便。2.4.2求解步骤对偶单纯形法求解步骤如下:①将原问题的数学模型标准化。②列出初始单纯形表。③判优。下一页返回上一页2.4对偶单纯形法若所有B-1bi非负，且所有检验数非正，最优;否则，进行以下步骤:④按法则:，确定出基变量。⑤按法则:，确定入基变量。⑥以alk为主元素进行迭代(方法同普通单纯形法)，得到新的基可行解。⑦重复上述(2)~(6)步，直至获得最优解。可见，对偶单纯形法擅长解决决策变量多、约束条件少的线性规划问题，计算步骤少、简单。返回上一页2.5灵敏度分析与参数规划线性规划研究的是一定条件下的最优化问题，但实际的资源环境和技术条件是可变的，而且基础数据往往是测算估计的数值。灵敏度分析又称敏感性分析或优化后分析，用于研究基础数据发生波动后对最优解的影响，或者说研究最优解对数据变化的敏感程度，即最优解在多大的范围内波动才不影响最优基。因此，灵敏度分析要解决的问题包括两个方面:参数在什么范围变化而最优解或最优基不变?已知参数的变化范围，考查最优解(最优基)是否改变?具体为:①可用资源的数量发生变化，会使得右边限制常数bi发生变化。②由于市场条件发生变化，会使得价值系数cj发生变化。③由于生产工艺的改进，会使得单耗(约束条件系数或叫技术系数)aij，发生变化。下一页返回2.5灵敏度分析与参数规划④为使资源得到充分利用，增加生产项目，会增加变量个数。⑤为提高产品质量，增加资源种类，会增加约束条件个数。因此，灵敏度分析主要是指各类因素发生变化对原规划问题最优解(原最优决策方案)的影响分析，即这些因素在什么范围内变化时，原规划问题最优解或最优基不变。各类因素发生变化可以分为以下两种情况。第一种情况:多种因素同时发生变化，原最优解可能发生变化，一般从头开始迭代计算，求出新最优解。第二种情况:单种因素单方面发生变化，原最优解可能发生变化，此时不必从头开始迭代计算，只要在原最优表中进行分析计算，即可求出新最优解。下一页返回上一页2.5灵敏度分析与参数规划2.5.1价值系数的灵敏度分析价值系数的灵敏度分析的研究内容是:cj在什么范围内变化时，最优解不变。

(1)求非基变量系数CN的变化范围。设非基变量系