运筹学第2章part1教材课件.ppt

第第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+0y42”和和“2y1+2y2+0y3+4y43”成立资源价格最低资源价格最低为使资源成功出售和出租，希望价格越低越好，因此为使资源成功出售和出租，希望价格越低越好，因此:min W=12y1+8y2+16y3+12y4下一页返回上一页2.1 对偶问题的提出对偶问题的提出资源价格非负资源价格非负资源出售和出租的价格不能为负值，因此必须满足资源出售和出租的价格不能为负值，因此必须满足:y1，y2，y3，y4 0综上，可以获得一个新的数学模型综上，可以获得一个新的数学模型:模型模型(1-1)与模型与模型(2-2)互为对偶模型，可看出两者的参数之间存在对应互为对偶模型，可看出两者的参数之间存在对应关系返回上一页2.2 对偶问题的数学模型对偶问题的数学模型2. 2. 1常规线性规划模型的对偶形式常规线性规划模型的对偶形式原问题数学模型可用矩阵形式表达原问题数学模型可用矩阵形式表达:若原问题具有最优解，其检验数必定小于或等于零，即若原问题具有最优解，其检验数必定小于或等于零，即0或或C- CBB-1A0。

令令Y=CBB-1，则有不等式，则有不等式C-YA 0或或YAC成立由于松成立由于松弛变量弛变量XS对应价格向量对应价格向量CS = 0，则有不等式，则有不等式S=CS-CBB-1I 0或或CBB-10(即即Y 0)成立同时，希望资源价格成立同时，希望资源价格Y和数量和数量b的乘积越小越好，的乘积越小越好，即即min W=Yb，则对偶问题见数学模型，则对偶问题见数学模型(2-4)，本教材称模型，本教材称模型(2-3)和模和模型型(2-4)为常规形式为常规形式下一页返回2.2 对偶问题的数学模型对偶问题的数学模型2. 2. 2非常规线性规划模型的对偶形式非常规线性规划模型的对偶形式本教材定义本教材定义“约束条件为等式约束条件为等式”或或“决策变量取值无约束决策变量取值无约束”的模型为的模型为非常规模型非常规模型1)约束条件为等式约束条件为等式若原问题模型为若原问题模型为下一页返回上一页2.2 对偶问题的数学模型对偶问题的数学模型因因AX=bbAX 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分别是原问题和对偶问题的可行解，则必有分别是原问题和对偶问题的可行解，则必有CXYb .下一页返回上一页2.3对偶问题的性质对偶问题的性质证明证明:对于原问题和对偶问题模型对于原问题和对偶问题模型(2-3)和模型和模型(2-4)， X是原问题的可行解，则有是原问题的可行解，则有:AXb,X0;Y是对偶问题的可行解，则有是对偶问题的可行解，则有YAC,Y0。

在在“AXb”两端左乘两端左乘“Y”，有，有YAXYb;在在“YAC”两端两端右乘右乘“X”，有，有YAXCX因此，不等式因此，不等式CXAXYb”成立，即成立，即CXYb推论推论:原问题原问题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分别为原问题和对偶问题的可行解，则分别为原问题和对偶问题的可行解，则AXb,YAC.充分性如果充分性如果X和和Y分别为原问题和对偶问题的可行解，它们分别为原分别为原问题和对偶问题的可行解，它们分别为原问题和对偶问题最优解的充要条件是问题和对偶问题最优解的充要条件是:(C-YA)X=0与与Y(b-AX) =0 下一页返回上一页2.3对偶问题的性质对偶问题的性质互补松弛定理经常表示为互补松弛定理经常表示为: 该定理表明，该定理表明，性规划问题的最优解中，如果对应某一约束条件的对偶变量取值为非性规划问题的最优解中，如果对应某一约束条件的对偶变量取值为非零，则该约束条件为严格等式零，则该约束条件为严格等式;反之，如果原问题约束条件为严格不等反之，如果原问题约束条件为严格不等式，则其对应的对偶变量一定为零式，则其对应的对偶变量一定为零2. 3. 5对偶最优解定理对偶最优解定理最优解定理表达了原问题最终单纯形表中变量的检验数与对偶问题最最优解定理表达了原问题最终单纯形表中变量的检验数与对偶问题最优解之间的关系。

在原问题最终单纯形表中，松弛变量检验数的相反优解之间的关系在原问题最终单纯形表中，松弛变量检验数的相反数对应于对偶问题原变量的取值，原变量检验数的相反数对应于对偶数对应于对偶问题原变量的取值，原变量检验数的相反数对应于对偶问题松弛变量的取值这个定理与两个互为对偶问题的最优解有关，问题松弛变量的取值这个定理与两个互为对偶问题的最优解有关，因此本教材称其为因此本教材称其为“对偶最优解定理对偶最优解定理”下一页返回上一页2.3对偶问题的性质对偶问题的性质2. 3. 6影子价格影子价格(1)影子价格的提出影子价格的提出影子价格影子价格(Shadow Price)又称计算价格、预测价格、最优价格。