规划数学对偶理论和灵敏度分析

关于规划数学对偶理论和灵敏度分析第1页，共40页，2022年，5月20日，5点57分，星期六第3讲对偶理论对偶问题的提出线性规划的对偶理论对偶单纯形法对偶问题的经济解释---影子价格重点：对偶理论，对偶单纯形法

难点：对偶理论基本要求：掌握对偶关系，理解对偶性质，掌握对偶单纯形法，会求影子价格，第2页，共40页，2022年，5月20日，5点57分，星期六引例：经营策略问题。甲工厂有设备和原料A、B这些设备和原料可用于Ⅰ、Ⅱ两种产品的加工，每件产品加工所需机时数，原料A、B消耗量，每件产品的利润值及每种设备的可利用的机时数如下表。现在乙厂和甲厂协商，打算租用甲厂的设备购买资源A和B。问甲厂采取哪种经营策略，是自己生产产品还是出租设备、出让原材料？如果出租设备、出让原材料，在和乙厂协商时出租设备和出让原材料A,B的底价应是多少？对偶问题的提出

Ⅰ

Ⅱ设

备原料A原料B140204

80台时

160kg120kg23盈利第3页，共40页，2022年，5月20日，5点57分，星期六自己生产：原问题引例分析：第4页，共40页，2022年，5月20日，5点57分，星期六设y1,y2和y3分别表示出租单位设备台时的租金和出让单位原材料A,B的附加额ω=80y1+160y2+120y3出售资源显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少目标函数min第5页，共40页，2022年，5月20日，5点57分，星期六例1它的对偶问题是：YA≥Cminω=YbY≥0Y=（y1，y2，y3）第6页，共40页，2022年，5月20日，5点57分，星期六1.5.1原问题与对偶问题的关系(对称形式)线性规划的对偶理论第7页，共40页，2022年，5月20日，5点57分，星期六第8页，共40页，2022年，5月20日，5点57分，星期六原关系minw对偶关系maxzxy原问题与对偶问题的对称形式第9页，共40页，2022年，5月20日，5点57分，星期六

标准(max,)型的对偶变换目标函数由max型变为min型对应原问题每个约束行有一个对偶变量yi，i=1,2,…,m对偶问题约束为型，有n

行原问题的价值系数C变换为对偶问题的右端项原问题的右端项b变换为对偶问题的价值系数原问题的技术系数矩阵A转置后成为对偶问题的技术系数矩阵原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义第10页，共40页，2022年，5月20日，5点57分，星期六原问题与对偶问题的结构关系原问题与对偶问题中的目标函数的优化方向相反（前者为极大，后者为极小）原问题的每个约束条件对应于对偶问题的一个决策变量，且约束条件的资源系数（右端的常数项）为相应决策变量的价值系数原问题的每个决策变量对应于对偶问题的一个约束条件，且决策变量的价值系数为相应约束条件的右端常数项对偶问题中的系数矩阵为原问题中的系数矩阵的转置原问题约束条件中的小于等于符号对应于对偶问题中的对偶变量取非负约束，原问题中决策的对偶问题非负约束在对偶问题中体现为相应的约束条件取大于等于符号第11页，共40页，2022年，5月20日，5点57分，星期六

非标准型的对偶变换第12页，共40页，2022年，5月20日，5点57分，星期六对偶变换的规则第13页，共40页，2022年，5月20日，5点57分，星期六maxω=5y1+4y2+6y3≥≤≤y1+2y2y1+y3-3y1+2y2+y3y1-y2+y3=23-5

1y1≥

0，y2≤0,y3无约束对偶问题例3写出线性规划问题的对偶问题minz=2x1+3x2-5x3+x4原问题

x1+x2-3x3+x4≥52x1+2x3-x4≤4x2+x3+x4=6x1

≤0,x2,x3≥0,x4无约束第14页，共40页，2022年，5月20日，5点57分，星期六（1）对称性：对偶的对偶就是原始问题minω’=-CXs.t.-AX≥-b X≥0maxz’=-Ybs.t.-YA≤-C Y≥0minω=Ybs.t.YA≥CY≥0maxz=CXs.t.AX≤bX≥0对偶的定义对偶的定义1.5.2对偶问题的基本性质

为了便于讨论，下面不妨总是假设第15页，共40页，2022年，5月20日，5点57分，星期六(2)弱对偶性:若是原问题的可行解，是对偶问题的可行解。则存在对偶问题(min)的任何可行解Y，其目标函数值总是不小于原问题(max)任何可行解X的目标函数值第16页，共40页，2022年，5月20日，5点57分，星期六弱对偶定理推论原问题的任何可行解目标函数值是其对偶问题目标函数值的下限；对偶问题的任何可行解目标函数值是原问题目标函数值的上限如果原(对偶)问题为无界解，则其对偶(原)问题无可行解如果原(对偶)问题有可行解，其对偶(原)问题无可行解，则原问题为无界解当原问题(对偶问题)为无可行解,其对偶问题(原问题)或具有无界解或无可行解第17页，共40页，2022年，5月20日，5点57分，星期六(3)强对偶性证：由弱对偶定理推论1，结论是显然的。

若是原问题的可行解，是对偶问题可行解，当 ,,分别是相应问题的最优解是使目标函数取最小值的解，因此是最优解

可行解是最优解的性质(最优性准则定理)第18页，共40页，2022年，5月20日，5点57分，星期六

(4)对偶定理

若原问题和对偶问题两者皆可行,则两者均有最优解,且此时目标函数值相等.第1部分:证明两者均有最优解证明分两部分由于原问题和对偶问题均可行,根据弱对偶性,可知两者均有界,于是均有最优解.第19页，共40页，2022年，5月20日，5点57分，星期六第2部分:证明有相同的目标函数值设为原问题的最优解它所对应的基矩阵是B，则其检验数满足CCBB1A0因此有对偶问题目标函数值而原问题最优解的目标函数值为显然

为对偶问题的可行解。证毕故由最优解准则定理可知

为对偶问题的最优解.第20页，共40页，2022年，5月20日，5点57分，星期六对偶定理推论根据对偶定理第2部分的证明,可以得出:若互为对偶的线性规划问题中的任一个有最优解,则另一个也有最优解,且目标函数值相等.综上所述,一对对偶问题的解必然是下列三种情况之一:原问题和对偶问题都有最优解一个问题具有无界解,另一个问题无可行解原问题和对偶问题都无可行解第21页，共40页，2022年，5月20日，5点57分，星期六(5)互补松弛定理证：由定理所设，可知有

设,

分别是原问题和对偶问题的可行解，为原问题的松弛变量的值，为对偶问题剩余变量的值。

,

分别是原问题和对偶问题最优解的充分必要条件是分别以左乘(1)式，以

右乘(2)式后，两式相减，得

根据最优解判别定理，分别是原问题和对偶问题最优解。反之亦然。证毕。（1）（2）第22页，共40页，2022年，5月20日，5点57分，星期六maxz=CXs.t. AX+XS=b X,XS≥0minw=Ybs.t.AY-YS=C Y,YS

≥0XYS=0YXS=0mn=YYSA-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数第23页，共40页，2022年，5月20日，5点57分，星期六原始问题和对偶问题最优解之间的互补松弛关系maxz=CX

s.t.AX+XS=bX,XS≥0minw=bYs.t.AY-YS=CY,YS≥0maxz=CXs.t.AX≤bX≥0minw=bYs.t.AY≥CY≥0对偶引进松弛变量引进松弛变量XYS=0YXS=0互补松弛关系X，XsY，Ys第24页，共40页，2022年，5月20日，5点57分，星期六y1

yiym

ym+1ym+jyn+m

x1xjxn

xn+1xn+ixn+m

对偶问题的变量原始问题的松弛变量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0原始问题的变量对偶问题的松弛变量第25页，共40页，2022年，5月20日，5点57分，星期六(6)原问题单纯形表检验数行与对偶问题解的关系原问题单纯形表检验数的相反数对应对偶问题的一个基解.显然,原问题最终单纯形表检验数的相反数对应对偶问题的一个基可行解0第26页，共40页，2022年，5月20日，5点57分，星期六证：标准化后的原问题和对偶问题的表达式为：若B是A中的一个基，A=（B，N）第27页，共40页，2022年，5月20日，5点57分，星期六原问题解为XB=B-1b，σN=CN-CBB-1N，Z=CBB-1b对偶问题的约束条件：0检验数：σB=CB-CBB-1B=0，σN=CN-CBB-1N，σS=CBB-1原问题单纯形表检验数行与对偶问题解的关系第28页，共40页，2022年，5月20日，5点57分，星期六结论：单纯形表中的检验数行和对偶问题的解仅差一个符号yi等于原问题的第i个方程中的松弛变量所对应的检验数的负数单纯形法迭代时，原问题解为基可行解，相应的检验数对应对偶问题的一个解，在原问题没有得到最优解之前，对偶问题的解为非可行解基可行解基可行解非可行解基可行解目标函数对偶问题原问题无可行解无界解第29页，共40页，2022年，5月20日，5点57分，星期六例4试用对偶理论证明该线性规划问题无最优解。证：该问题存在可行解，X=（0，0，0）；对偶问题为：由第一个约束条件可知对偶问题无可行解，因此，原问题有可行解，无最优解。第30页，共40页，2022年，5月20日，5点57分，星期六例5：试用对偶理论找出原问题的最优解。解：原问题的对偶问题为：已知其对偶问题的最优解为：第31页，共40页，2022年，5月20日，5点57分，星期六代入对偶问题的约束条件，得2,3,4式为严格不等式，由互补松弛性得因原问题的约束条件应取等式为：求解后得到原问题的最优解为:第32页，共40页，2022年，5月20日，5点57分，星期六原问题的最优解为:Z*=CBB-1b=CX*=Y*b对偶问题的经济解释---影子价格z=CX=CBB-1b+σNXN=CBB-1bσN=CN-CBB-1NY=CBB-1为单纯形乘子当b为变量的情况下,当bi发生变化:yi的经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化.yi是bi的一种估价,估价是有条件的替代方案.第33页，共40页，2022年，5月20日，5点57分，星期六1.5.3对偶单纯形法单纯形法原问题基可行解，对偶问题基解（非可行解）原问题基可行解，对偶问题基可行解….原问题基可行解，对偶问题基可行解原问题基解，对偶问题基可行