运筹学(对偶问题及性质).ppt
Chapter2 对偶理论(Duality Theory)线性规划的对偶模型线性规划的对偶模型对偶性质对偶性质对偶问题的经济解释影子价格对偶问题的经济解释影子价格对偶单纯形法对偶单纯形法 灵敏性分析灵敏性分析 本章主要内容：本章主要内容：本章主要内容：本章主要内容：线性规划的对偶模型v设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表：产品数据表产品数据表 设备产品ABCD产品利润（元件）甲 21402乙 22043设备可利用机时数（时）1281612问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？获得最大利润？1.对偶问题的现实来源对偶问题的现实来源对偶问题的现实来源对偶问题的现实来源v解：设甲、乙型产品各生产x1及x2件，则数学模型为：反过来问：若厂长决定不生产甲和乙型产品，决定出租机器反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么种机器的机时如何定用于接受外加工，只收加工费，那么种机器的机时如何定价才是最佳决策？价才是最佳决策？在市场竞争的时代，厂长的最佳决策显然应符合两条：（1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。（2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线性规划数学模型为：2.原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题原问题（对偶问题）（对偶问题）对偶问题对偶问题（原问题）（原问题）线性规划的对偶模型v（1）对称形式特点：目标函数求极大值时，所有约束条件为号，变量非负;目标函数求极小值时，所有约束条件为号，变量非负.已知已知(LP)，写出，写出(DP)单纯形法计算的矩阵描述单纯形法计算的矩阵描述(nm)项 目非基变量基变量XB XNXs0 Xs bB NIcj-zjCB CN0项 目基变量非基变量XBXN XsCB XB B-1bIB-1N B-1cj-zj0CN-CBB-1N -CBB-1v若初始矩阵中变量 xj的系数向量为Pj,迭代后为Pj,则有 Pj=B-1 Pjv当B为最优基时，应有v令Y=CBB-1,则项 目基变量非基变量XBXN XsCB XB B-1bIB-1N B-1cj-zj0-Ys1CN-CBB-1N -CBB-1-Ys2 -Yv例2.1 写出线性规划问题的对偶问题解：首先将原问题变形为对称形式解：首先将原问题变形为对称形式 (2)(2)非对称形式的对偶规划非对称形式的对偶规划 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面 的对应关系直接给出其对偶规划。（1）将模型统一为“max，”或“min，”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。1.1.线性规划对偶问题线性规划对偶问题线性规划的对偶模型原问题（或对偶问题）对偶问题（或原问题）约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项目标函数 max目标函数 min约束条件m个m个变量00=无约束变量n个n个约束条件00无约束=v例2.2 写出下列线性规划问题的对偶问题.解：原问题的对偶问题为解：原问题的对偶问题为对偶性质例例2.3 分别求解下列分别求解下列2个互为对偶关系的线性规划问题个互为对偶关系的线性规划问题分别用单纯形法求解上述分别用单纯形法求解上述2 2个规划问题，得到最终单纯形表如个规划问题，得到最终单纯形表如下表：下表：对偶性质XBb原问题的变量原问题的松弛变量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/20001/41/2XBb对偶问题的变量对偶问题的剩余变量y1y2y3y4y5y21/4-4/510-1/41/4y31/215/2011/2-3/215/2007/23/2原问原问题最题最优表优表对偶对偶问题问题最优最优表表对偶性质原问题与其对偶问题的变量与解的对应关系：在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。对偶问题的基本性质v(1)对称性：对偶问题的对偶是原问题;v(2)弱对偶性：若X是原问题的可行解，Y是对偶问题的可行解。则存在CXYb;v(3)无界性：若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解;v(4)可行解是最优解时的性质;v(5)对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等;v(6)互补松弛性;v(7)原问题检验数与对偶问题解的关系。对偶性质性质性质1 1(对称性对称性)：对偶问题的对偶是原问题：对偶问题的对偶是原问题 min W=Y bs.t.YA C Y 0max Z=C Xs.t.AXb X 0对偶性质性质性质2 2 (弱弱对偶性对偶性)设设 和和 分别是问题分别是问题(LP)(LP)和和(DP)(DP)的可行的可行解，则必有解，则必有推论推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。标函数值的上界。性质性质3(无界性无界性):在一对对偶问题（在一对对偶问题（P）和（）和（D）中，若其中一个）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；问题可行但目标函数无界，则另一个问题无可行解；反之不成立反之不成立。这也是对偶问题的无界性。这也是对偶问题的无界性。y1y2v从两图对比可明显看到原问题无界，其对偶问题无可行解对偶性质性质性质4(最优性定理最优性定理)如果如果 是原问题的可行解，是原问题的可行解，是其对偶是其对偶问题的可行解，并且问题的可行解，并且:则则 是原问题的最优解，是原问题的最优解，是其对偶问题的最优解。是其对偶问题的最优解。对偶性质性质5 (强对偶性)：若原问题具有最优解，则对偶问题也具有最优解，且它们最优解的目标函数值相等。性质性质6 (互补松弛性互补松弛性)：在线性规划问题的最优解中，如果对：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零量一定为零.即即Y*XS=0，YSX*=0对偶性质v例2.4已知线性规划的最优解是的最优解是X=(6,2,0)T,求其对偶问题的最优解求其对偶问题的最优解Y。解：写出原问题的对偶问题，即解：写出原问题的对偶问题，即标准化标准化v设对偶问题最优解为Y(y1，y2),因为因为X10，X20，所以由互补松弛性定理可知，所以由互补松弛性定理可知，对偶问题的第一、二个约束的松弛变量等于零，即对偶问题的第一、二个约束的松弛变量等于零，即y30，y40，带入方程中：，带入方程中：解此线性方程组得解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：从而对偶问题的最优解为：Y=(1,1)，最优值，最优值w=26。作业:第88-89页:3.3(1),(2)3.8思考题：3.2 3.4
