《运筹学02对偶理论(1)线性规划的对偶模型,对偶性质》由会员分享，可在线阅读，更多相关《运筹学02对偶理论(1)线性规划的对偶模型,对偶性质（32页珍藏版）》请在金锄头文库上搜索。
1、Chapter 3 对偶理论 Dual Theory3.1 线性规划的对偶模型 Dual Model of LP3.2 对偶性质 Dual property 3.3 对偶单纯形法 Dual Simplex Method3.4 灵敏度与参数分析 Sensitivity and Parametric Analysis运筹学 Operations Research3.1 线性规划的对偶模型 Dual Model of LPChapter3 对偶理论 Dual Theory例3.1 (原例1.1)某工厂生产甲、乙两种产品。这些产品 分别要在A、B、C三种不同的设备上加工。企业决策者 应如何安排生产计划
2、，使企业总的利润最大？3.1 线性规划的对偶模型 Dual model of LPChapter3 对偶理论 Dual Theory解：设x1、x2分别为甲、乙两种产品的产量，Z为总利润，则数 学模型为：3.1 线性规划的对偶模型 Dual model of LP现在从另一个角度来考虑企业的决策问题。假如企业不考 虑自己生产产品，而将现有的资源标价出售， 问题：决策者应怎样给定资源一个合理的价格？Chapter3 对偶理论 Dual Theory设y1，y2，y3分别表示三种资源的单位增值价格(售价成本增值)，总增值最低可用min w=36y1+40y2+76y3表示。企业生产一件产品甲用了四
3、种资源的数量分别是3，5和9个单位，利润是32, 企业出售这些数量的资源所得的利润不能少于32，即同理，对产品 乙有3.1 线性规划的对偶模型 Dual model of LPChapter3 对偶理论 Dual Theory这是一个线性规划数学模型，称这一线性规划模型是前面生产计划模型的对偶线性规划模型, 这一问题称为对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。3.1 线性规划的对偶模型 Dual model of LP价格不可能小于零，即有yi0(i=1, ,4), 从而企业的资源价格 模型为Chapter3 对偶理论 Dual Theory注：以上两问题是同一组数据参数
4、，只是位置有所不同，所描述的问题实际上是从两个不同的角度去描述。原始线性规划问题考虑的是充分利用现有资源，以产品数量和单位产品的利润来决定企业的总利润，没有考虑资源的价格，实际上在构成产品的利润中，不同的资源对利润的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格。3.1 线性规划的对偶模型 Dual model of LPChapter3 对偶理论 Dual TheoryChapter3 对偶理论 Dual Theory线性规划问题(3.2)就是原线性规划问题(3.1)的对偶线性规划问题 ，反之，(3.2)的对偶问题就是(3.1)3.1 线性规划的对偶模型 Dual m
5、odel of LP原问题与对偶问题有如下关系(假设原问题 (3.1)： (1)原问题的约束个数(不含非负约束)等于对偶变量的个数(2)原问题的目标函数系数对应于对偶问题的右端项(3)原问题的右端项对应于对偶问题的目标函数系数 (4)原问题的约束矩阵转置就是对偶问题系数矩阵(5)原问题求最大，对偶问题是求最小(6)原问题不等式约束符号为“”,对偶问题不等式约束符号为“”Chapter3 对偶理论 Dual Theory【例3.2】写出下列线性规划的对偶问题【解】设Y=(y1，y2 )， 则有3.1 线性规划的对偶模型 Dual model of LP从而对偶问题为Chapter3 对偶理论 D
6、ual Theory【例3.3】 写出下列线性规划的对偶问题【解】该线性规划的对偶问题是求最小值，有三个变量 且非负, 有两个“ ” 约束,即3.1 线性规划的对偶模型 Dual model of LPChapter3 对偶理论 Dual Theory线性规划问题的规范形式(Canonical Form 或叫对称形式) ：定义：目标函数求极大值时，所有约束条件为号，变量非负；目标函数求极小值时，所有约束条件为号，变量非负。 3.1 线性规划的对偶模型 Dual model of LP注： (1)线性规划规范形式与标准型是两种不同形式，但可以相互转换。(2)规范形式的线性规划问题的对偶仍然是规范
7、形式Chapter3 对偶理论 Dual Theory原问题问题 (或对对偶问题问题 )对对偶问题问题 (或原问题问题 ) 目标标函数max 目标标函数系数(资资源限量) 约约束条件系数矩阵阵A(AT)目标标函数min 资资源限量(目标标函数系数) 约约束条件系数矩阵阵AT(A)变变 量n个变变量 第j个变变量0 第j 个变变量0 第j个变变量无约约束约约 束 n个约约束 第j个约约束为为 第j个约约束为为 第j个约约束为为=约约 束m个约约束 第i个约约束 第i个约约束 第i个约约束为为=变变 量m个变变量 第i个变变量0 第i个变变量0 第i个变变量无约约束3.1 线性规划的对偶模型 Du
8、al model of LP 问题：讨论一般形式的线性规划问题的对偶问题？方法：先将其转化为规范形式的线性规划问题，然后写出其对 偶问题，适当将其进行化简。3.2 对偶性质(了解)Dual property Chapter3 对偶理论 Dual Theory对偶问题是(记为DP)：这里A是mn矩阵, X是n1列向量, Y是1m行向量。【性质1】 对称性: 对偶问题的对偶是原问题。 设原问题是(记为LP)： 3.2 对对偶性质质 Dual property3.2.1 对偶性质【性质2】 弱对偶性: 设X*、Y*分别为LP(max)与 DP(min)的可行解，则 Chapter3 对偶理论 Dua
9、l Theory3.2 对对偶性质质 Dual property由这个性质可得到下面几个结论： (1)(LP) 的任一可行解的目标值是 (DP) 的最优值下 界；(DP)的任一可行解的目标是(LP)的最优值的上界；(2) 在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；(3) 若原问题可行且另一个问题不可行，则原问题具有无界解。 注意: 上述结论(2)及(3)的条件不能少。一个问题无可行解时，另一个问题可能有可行解(此时具有无界解) 也可能无可行解。Chapter3 对偶理论 Dual Theory例如：无可行解，而对偶问题有可行解，由结论(3)知必有无界解。3.2
10、对对偶性质质 Dual propertyChapter3 对偶理论 Dual Theory【性质3】最优准则定理: 设X*与Y*分别是(LP)与(DP) 的可行解，则X*、Y*是(LP)与(DP)的最优解当且仅当 C X*= Y*b .3.2 对对偶性质质 Dual property【性质4】对偶性：若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。另一结论：若(LP)与(DP)都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。【性质5】互补松弛定理: 设X*、Y*分别为 (LP) 与 (DP) 的可行解，XS和YS分别是它们的松弛变量的可行解，则
11、X*和Y*是最优解当且仅当 YSX*=0 和 Y*XS=0Chapter3 对偶理论 Dual Theory性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y*求X*或已知X*求Y*。 Y * XS = 0 和 YS X * = 0两式称为互补松弛条件。将互补松弛条件写成下式由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：3.2 对对偶性质质 Dual propertyChapter3 对偶理论 Dual Theory(1)当yi*0时， , 反之当 , 时yi*=0；利用上述关系，建立对偶问题(或原问题)的约束线性方程组，方程组的解即为最优解。【例
12、3.5】 已知线性规划的最优解是 , 求对偶问题的最优解。3.2 对对偶性质质 Dual propertyChapter3 对偶理论 Dual Theory【解】对偶问题是因为x10，x20，所以对偶问题的第一、二个约束的松弛变量等于零，即解此线性方程组得y1=1, y2=1, 从而对偶问题的最优解 为Y=(1，1)，最优值w =26。3.2 对对偶性质质 Dual propertyChapter3 对偶理论 Dual Theory【例3.6】 已知线性规划 的对偶问题的最优解为Y=(0，2)，求原问题的最优解 。【解】对偶问题是3.2 对对偶性质质 Dual propertyChapter3
13、 对偶理论 Dual Theory解方程组得：x 1=5, x 3=1, 所以原问题的最优解为X=(5，0，1)T，最优值 Z= 12。因为y20，所以原问题第二个松弛变量 =0，由 y1=0、y2=-2知，松弛变量 故x2=0，则原问题的约束条件为线性方程组： 3.2 对对偶性质质 Dual propertyChapter3 对偶理论 Dual Theory【例3.7】 证明该线性规划无最优解：【证】容易看出X=(4，0，0)是一可行解。对偶问题将三个约束的两端分别相加得 , 而第二个约束有y21,矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。 3.2 对对偶性质质 Dual
14、propertyChapter3 对偶理论 Dual Theory【性质6】LP(max)的检验数的相反数对应于DP(min)的一组基本解。 其中第j个决策变量xj的检验数的相反数对应于(DP)中第j个松弛变量 的解，第i个松弛变量 的检验数的相反数对应于第i个对偶变量yi的解。反之，(DP)的检验数(注意：不乘负号)对应于(LP)的一组基本解。3.2 对对偶性质质 Dual property注：应用性质6 的前提是线性规划为规范形式，而 性质1-5则对所有形式线性规划有效。Chapter3 对偶理论 Dual Theory【例3.8】 线性规划(1) 用单纯形法求最优解； (2) 写出每步迭
15、代对应对偶问题的基本解； (3) 从最优表中写出对偶问题的最优解； (4) 用公式Y=CBB-1求对偶问题的最优解。【解】(1) 加入松弛变量x4、x5后，单纯形迭代如表3-5所示。3.2 对对偶性质质 Dual propertyChapter3 对偶理论 Dual TheoryXBx1x2x3x4x5b 表 （1）x4 x52 11 02 41 00 12 4j62100表 （2）x1 x51 01/2 1/21 31/2 1/20 11 3j01530表 （3）x1 x21 00 14 60 11 24 6j001122表3-53.2 对对偶性质质 Dual property最优解X=(4，6，0)T，最优值Z=6426=12；Chapter3 对偶理论 Dual Theory(2) 设对偶变量为y1、y2, 松弛变量为y3、y4、y5 , Y=(y1、y2、y3、y4、y5)，由性质6得到对偶问题的基本解 (y1、y2、 y3、y4、y5)=(4,5,1,2,3)，即表25(1)中=(6，2，1，0，0)，则Y(1)=(0，0，-6，2，
