运筹学复件 02对偶实际[最新]

1、单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级*第二章对偶理论与灵敏度分析摘扫滔析顷橡决茅虎恃爪霸踞懊猪叼索袭畜胜蝴说芹敏伞铱富斌畅踏缕砧运筹学复件 02对偶理论运筹学复件 02对偶理论2.1单纯形法的矩阵描述 所谓单纯形法的矩阵描述就是用矩阵来描述单纯形法，这样可有助于对对偶问题进行分析。 一、标准型线性规划问题单纯形法的矩阵描述 设线性规划问题为：Maxz=C1X1+ C2X2+ + CnXn a11X1+ a12X2 + a1nXn =b1 a21X1+ a22X2+ + a2nXn =b2 am1X1+ am2X2+ + amnXn =bm X1， X2， ，

2、 Xn0磷况佩谭锥铲赣瞳怪疗勒终氢蕴讲齿痴耽彬贪伙赦估堂疙译懊绑娠捡泄造运筹学复件 02对偶理论运筹学复件 02对偶理论在A中任取m个线性无关的列向量组成一个可行基，B基矩阵，N非基向量组成的矩阵；XB基变量组成的列向量，XN非基变量组成的列向量；CB基变量价值系数组成的行向量， CN非基变量价值系数组成的行向量；则A=（B，N），C=（ CB ， CN ），渡演厘趁一醋怨脊籽阂浇慑鸥砍岂舰诊彭莽滞拖斟故置钮液茁埋犀疮襟小运筹学复件 02对偶理论运筹学复件 02对偶理论标准形式模型可表示为措帮社樱盎翱颧陌玫阶紫误蘑芹刚尹驯杏沼焙资眩斩翔缩呢螺邑杯桔豆阉运筹学复件 02对偶理论运筹学复件 02对

3、偶理论即标准形式的LP问题变换前模型变换后模型所对应的单纯形表为：CBCN CB XBbXBXNCB XBB-1bIB-1N-Z-CBB-1b0CN-CBB-1N茁沙索缅菜视慰工钓健烃粮沾镶核滤溪囱吉未恕堵圆陋偶烹提俘张何惦论运筹学复件 02对偶理论运筹学复件 02对偶理论 检验数的推广！ 基变量检验数B=0= CB-CBB-1B， 非基变量检验数N=CN-CBB-1N 所有变量的检验数可以表示为任意一个变量检验数的表示方法昆檬狐跟法且随栈诡战焙拇嫉撵溉虫膳若卫勉手榔擦踊筏坷家蜡藕单氯丸运筹学复件 02对偶理论运筹学复件 02对偶理论 二、存在松弛变量模型单纯形表的矩阵描述 设线性规划问题为：

4、引入松弛变量的模型为： 在下面的矩阵描述中，松弛变量独立表示，不归入非基变量。附黔乃日串弗玻句誊徊馒破其甭席财磅递扭弘节毕柜了葵纹辣匣筒顷拦销运筹学复件 02对偶理论运筹学复件 02对偶理论差卑愉夺疚茵驭垛蛔猪肋纂打月孪晶学狼泄凄熄摈靳酷绑灭见魄殉并许跪运筹学复件 02对偶理论运筹学复件 02对偶理论以此模型构造单纯形表如下：CBCN0XBbXBXNXSXBB-1bIB-1NB-1-Z-CBB-1b0CN-CBB-1N-CBB-1表中最关键的就是B-1所在的位置，因此要特别注意松弛变量在矩阵描述的单纯形表中的作用！ 每张表中,松弛变量对应的系数矩阵就是表中基的逆矩阵嘴咏单捧蕉商要碟嫉劝辫垃兹酵

5、肥垢艳赖仑弹南砖御皇挡透兄痰黎结苔缩运筹学复件 02对偶理论运筹学复件 02对偶理论澎待什俩彭平押擅捶溅择女泞拳孕巧售拼豺僳贞吉惮盲杨右弛羔蝴赁墙罚运筹学复件 02对偶理论运筹学复件 02对偶理论例下面的单纯形表中X1 X2 X3 X4 X5 X6 2 -1 1 0 0 0CB XB bX4X1X2 0 2-1 1 -1 -2 0 1/2 1/2 0 -1/2 -1/2X4X5X6601020000 1 1 1 0 01 -1 2 0 1 01 1 -1 0 0 12 -1 1 0 0 0 1015 5010001 1 -3/2000-3/2-1/2-3/2B =（ P4 ，P1， P2 ）1

6、 3 10 1 -10 1 1=B-1 =1 -1 -20 1/2 1/20 -1/2 -1/2兽边梧杰摇甭肚煌呈坟腹曲法掀朴赎欧射掠狞合砌内溜试增辕狼勃锣寅晨运筹学复件 02对偶理论运筹学复件 02对偶理论X1 X2 X3 X4 X5 2 3 0 0 0CB XB bX3 X4 X50 0 0 8 16 121 4 02 0 41 0 00 1 00 0 1j230004-3X3 X4 X20 0 33 0 1 0 0 1/4 16 4 0 0 1 02 1 0 1 0 -1/2j2000-3/424-X1 X4 X22 0 33 0 1 0 0 1/4 8 0 0 -4 1 22 1 0

7、1 0 -1/2j00-201/4B1 =（ P3 ,P4,P5 ）=IB2= （ P3 ,P4,P2 ）B2-1 =1 0 -1/20 1 00 0 1/4B-1 =1 0 00 1 00 0 11 0 20 1 00 0 4=思考：对照某一单纯形表找出B1-1 ， B2- 1， B3 1宋狸极廉瓜迁胰轿涉逛吴岳梆隙脱趟领垃冤柠娩妊引拓孰策档札屁瓮嫉厘运筹学复件 02对偶理论运筹学复件 02对偶理论用矩阵描述的规则表达式=min（B-1b）i（B-1Pk）i（B-1Pk）i0（B-1b）i表示B-1b的第i个分量（B-1Pk）i表示B-1Pk的第i个分量 B-1Pk表示进基向量=（B-1b）

8、L（B-1Pk）L蠕并胺级入播由结舅蔷映刨馁擅厚研朵亿仗痒莱篡咳帆镍葛使城匪娜蛆骤运筹学复件 02对偶理论运筹学复件 02对偶理论例已知LP问题用单纯形法计算 的初始表和最终表，请将表中空白处的数字填上计算公式b=B-1bPj=B-1PjN=CN-CBB-1Nj=Cj-CBB-1P jX1 X2 X3 X4 X5 X6 2 -1 1 0 0 0CB XB bX4X1X2 0 2-1 1 -1 -2 0 1/2 1/2 0 -1/2 -1/2X4X5X6601020000 1 1 1 0 01 -1 2 0 1 01 1 -1 0 0 12 -1 1 0 0 0 衷影清亡绒遭出釜酪铱升姻墒老秩纪

9、孤署扭砰方哈灸交蛊哀齿袋帖漠几粘运筹学复件 02对偶理论运筹学复件 02对偶理论X1 X2 X3 X4 X5 X6 2 -1 1 0 0 0CB XB bX4X1X2 0 2-1 1 -1 -2 0 1/2 1/2 0 -1/2 -1/2X4X5X6601020000 1 1 1 0 01 -1 2 0 1 01 1 -1 0 0 12 -1 1 0 0 0 1015 5010001 1 -3/2000S=（ 4 ，5 ，6 ） = -CBB-1=（0，-3/2，-1/2）-3/2-1/23=C3 -CBB-1P3 =-3/2-3/2鳃娶骇整章嫡惺题改兵散剔坠田缚讼寞摔阶模踊呀垦负售瓷哉仲郭褒

10、惊挖运筹学复件 02对偶理论运筹学复件 02对偶理论 改进单纯形法 1.只需存贮原始数据A，b，C，每步需知B-12.每步必须计算的数据单纯形因子和检验数Y= CB B-1 N=C N -CB B-1NB为基时进基向量Pm+k=B-1 Pm+k=（ a1m+k ，a2m+k ， amm+k ）T基变量XB= B-1b=（b1 ， b2 ， bm ）T通过由最小比值法则得主元素aLm+k ，主元素已知，离基变量确定，新基B1确定，返回2缴洛姑泼砖道务殴串拐栏控贯底钠蛮荆束再彬演楚拈葛拦北芭熄斌谜过沿运筹学复件 02对偶理论运筹学复件 02对偶理论改进单纯形法步骤对MaxZ=CX，AX=b，X0，

11、A=（P1，P2 Pn ）1.已有初始可行基B，求B-1，初始解XB= B-1 b=（b1 ， b2 ， bm ）T2.计算N=C N -CB B-1N，若所有N0，则计算Zo= CB B-1b，停，否则取m+k=minj j0， Xm+k进基3.计算Pm+k=B-1 Pm+k =( a1m+k ,a2m+k , amm+k ) T，若Pm+k 0，则为无界解，停止4.最小比值法=minbiaim+k aim+k 0 =bLaLm+k 则XL离基5.确定新基B，转1沙租汾较衬惕镀程录豆炯拯棺婴次沈闲窘衔熟杂槽胜暂希躇沿咐骸觅探口运筹学复件 02对偶理论运筹学复件 02对偶理论 对偶问题的提出例

12、：Max z=2 X1+ 3X2 1X1+ 2 X2 8 Y1 4X1 16 Y2 4 X2 12 Y3 X1， X2 0 线性规划问题具有对偶性！ 任何一个求最大值的线性规划问题都有一个求最小值的线性规划问题与之相对应。一个叫“原始问题”，另一个称为它的“对偶问题”。 第一章例1生产计划问题,从另一角度考虑,转变生产方式,例出租或外加工,如何给资源定价才合算？ 定价应考虑的问题 1.出卖资源获利应不少于生产产品的获利 2.价格应尽可能低，才能有竞争力（制订一个成交的底价） 设Y1Y2Y3分别为3种资源的出租或出卖价格 用来生产一件产品 的工时和材料的销售收入不少于 产品的单位获利，则得到另一

13、组约束条件 1Y1+4Y22 同理 2Y1+4Y33 最低价格应使总收入最小 Minz= 8Y1+16Y2+12Y3婉诌彪数陕筋妇汲矢憨库贝唬彪抓迟端禹掣叁惊纪蛊殆私胀奔袱戌俊万自运筹学复件 02对偶理论运筹学复件 02对偶理论原问题Max z=2 X1 + 3X2 X1+ 2 X2 8 Y1 4 X1 16 Y2 4 X2 12 Y3 X1， X2 0对偶问题Minz= 8Y1+16Y2+12Y3 Y1+4Y2 2 2Y1 +4Y33 Y1 ，Y2 ，Y3 0140204X1 X2 81612原问题Max z=（2，3）对偶问题Minz=（ Y1 ，Y2 ，Y3 ）X1 X2 81612（Y

14、1 ，Y2 ，Y3）1402042 3原问题Maxz=CX，AX b，X 0对偶问题Min=Yb，YAC，Y 0备忿舅对酋馁详季告怕秘屉徽鉴漾膛蛛徒听岳局豺橡移玫剧捍派牌快刀疼运筹学复件 02对偶理论运筹学复件 02对偶理论 对偶问题的定义原问题Maxz=CX，AX b，X 0对偶问题Min=Yb，YAC，Y 0这种关系称为对称形式的对偶关系烘疏老慈珊徒空煮元瘁蹿乞柜拙屹刮村感吐拇费验器晒闲崔谓罗缝胖秒皮运筹学复件 02对偶理论运筹学复件 02对偶理论原问题、对偶问题的展开形式原问题MaxZ=C1X1+ C2X2 + + CnXnX1， X2 Xn 0 对偶问题MinZ=Y1b1+Y2b2+

15、+ Ymbm（ C1，C2 ， Cn）Y1， Y2 Ym 0 东卞坞苯衔诵檬蟹豹访说连站怨刷桓渣惭徘亦超击凰抬淮字和聋束鲜与汝运筹学复件 02对偶理论运筹学复件 02对偶理论对称形式的对偶问题的对应关系： 原问题 对偶问题目标函数类型 Max Min 目标函数系数与右端常数对应关系目标函数系数约束方程右端常数变量数约束数对应关系变量数n约束数m约束数n变量数m原问题变量类型与对偶约束条件的对应关系变量0 约束条件 原问题约束条件与对偶变量的对应关系约束条件变量 0倪吞韩纲镍蘑橡势隅菱文攫怀铺渺意兴荧搜踩粪酞碰瓷呸堕蚁棘俭顶歧粹运筹学复件 02对偶理论运筹学复件 02对偶理论例1：求非标准型形式

16、模型的对偶问题 Max z= 2 X2 -5X3 X1 + X3 2 Y1 2 X1 + X2 +6 X3 6 Y2 X1 - X2 +3 X3 =0 Y3 X1， X2 ， X3 0将模型化为对偶问题的标准型Max z= 2 X2 -5X3 -X1 - X3 - 2 Y1 2 X1 + X2 +6 X3 6 Y2 X1 - X2 +3 X3 0 Y3 - X1 + X2 -3 X3 0 Y3X1， X2 ， X3 0其对偶问题Min=-2Y1+6Y2-Y1 +2Y2 +Y3 - Y3 0 Y2 -Y3 +Y3 2-Y1 +6Y2 +3Y3 - 3Y3-5 Y1 ，Y2 ，Y3 ，Y3 0令Y

17、1 = -Y1 ， Y3 = Y3 - Y3 ,则模型可表示为Min=2Y1 +6Y2Y1 +2Y2 +Y3 0 Y2 -Y3 2Y1 +6Y2 +3Y3 -5 Y1 0 ，Y2 0 ，Y3 无约束结论：最大值问题约束方程与最小值问题变量不等式符号相反,方程为等式,则变量无约束醉厂独鸽汽姿钵栖开赞住芥撂士遁孤谋擦篷魔涂深丛恩姜江禁妄牧赦术肾运筹学复件 02对偶理论运筹学复件 02对偶理论例2：求下面模型的对偶问题 Max z= 2 X2 -5X3 X1 + X3 2 Y1 2 X1 + X2 +6 X3 6 Y2 X1 - X2 +3 X3 0 Y3 X1， X3 0， X2 无约束 令X2

18、= X2 - X2 代入模型Max z= 2 X2 - 2 X2 -5X3 X1 + X3 2 Y12 X1 + X2 - X2 +6 X3 6 Y2 X1 - X2 + X2 +3 X3 0 Y3 X1， X2 ，X2 ， X3 0， 根据例一的结论，其对偶问题为Min=2Y1+6Y2Y1 +2Y2+Y3 0 Y2 -Y3 2 -Y2+Y3 -2Y1 +6Y2+3Y3 -5Y1 0，Y2，Y3 0模型又可表示为Min=2Y1+6Y2Y1 +2Y2+Y3 0 Y2 -Y3 =2Y1 +6Y2+3Y3 -5Y1 0，Y2，Y3 0结论：最大值问题变量与最小值问题约束方程不等式符号一致;若变量无约

19、束,则方程为等式番升薄嵌殉左酿吧索邻塞佃咕峡泉腑阉诉隔就拳驭港脏窥创汐暗罪弯购孺运筹学复件 02对偶理论运筹学复件 02对偶理论 对偶关系对应表 原问题 （对偶问题） 对偶问题（原问题） 目标函数 Max Min 目标函数系数约束方程右端常数变量约束条件约束条件变量约束方程右端常数目标函数系数n个n个00无约束=m个m个00=无约束誊煮按秤邱者狙若荤抓极霸俩巡疙里随聪羌袁瓣莆暴叁顽丽宰琴惹瘤况艰运筹学复件 02对偶理论运筹学复件 02对偶理论例3：求LP问题的对偶问题Min z= 2 X1 +3 X2 -5X3 + X4 X1 + X2 -3 X3 + X4 5 Y12 X1 +2 X3 -

20、X4 4 Y2 X2 + X3 + X4 = 6 Y3X1 0， X2 ， X3 0 , X4 无约束 MaxZ=5Y1 +4 Y2 +6Y3Y1 +2Y2 2 X12Y1 +Y3 3 X2-3Y1 +2Y2 +Y3 -5 X3 Y1 Y2 +Y3 = 1 X4Y1 0 ，Y2 0， Y3 无约束结论：1.最大值问题约束方程与最小值问题变量不等式符号相反,方程为等式,则变量无约束.2.最大值问题变量与最小值问题约束方程不等式符号一致;若变量无约束,则方程为等式漏舟垃弧羊庇埔睦嘛峦老摘笛冶选酮码冰础琴疗菠纽暴荧猎琉禁厄迈涵讹运筹学复件 02对偶理论运筹学复件 02对偶理论课堂练习：写出下面线性规

21、划的对偶规划：至鲍弛屠赁暗婿山昂还跳寨保她皱蛮盅翰倚但贤轮阴唉莲赠萍模吏肠早锯运筹学复件 02对偶理论运筹学复件 02对偶理论下面的答案哪一个是正确的？为什麽？ 阀杭商裂当露妹滑败岂幸巨锥吸困筏寸侩慑利势信屑钮曲奔芬愚粟黄颂厂运筹学复件 02对偶理论运筹学复件 02对偶理论 对偶问题基本性质1.对称性：对偶问题的对偶是原问题2.弱对偶性 对原问题Maxz=CX，AX b，X 0 对偶问题Min=Yb，YAC，Y 0殆茶淖竿跪雹留譬玛哄瞥售璃胃赔究苟载坠蔷狱甲锌藕寂撂疑击凰际悬赵运筹学复件 02对偶理论运筹学复件 02对偶理论 即最大值问题的任一可行解的目标值一定小于求最小值另一问题的任一可行解

22、的目标函数值证明：设原问题Maxz=CX，AX b，X 0对偶问题Min=Yb，YAC，Y 0础惶闯席暂潞席片煤贪谐戳泞蚜课肤芋软拦惶瞅子巧瞎育曹站祸扎冤舅紊运筹学复件 02对偶理论运筹学复件 02对偶理论 推论1：原、对偶问题都有可行解，则必都有最优解结论1:若（LP）有最优解，则（DP）也有最优解（反之亦然），且（LP）与（DP）的最优值相等。结论2：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。推论2：原问题（P）有可行解，但无有限最优解（无界解），则对偶问题（D）无可行解胶续险霸沾姐酸磷墅汀设夷械拭诧淳婪欠舷勃怕奏砚膛属蚌抚苏朗粗暂锚运筹学

23、复件 02对偶理论运筹学复件 02对偶理论3.可行解为最优解条件分别为P、D问题的可行解，且有则它们分别为P、D的最优解证明：设分别为P、D的任一可行解由弱对偶性则有X*、Y*为最优解你铣作巢跟沿莹犀判债呼马筑荚之啮辫搏帕豢桓乎轻贝沙越膘慧果过试甫运筹学复件 02对偶理论运筹学复件 02对偶理论 4.对偶定理 若原问题Maxz=CX，AX b，X 0有最优解,则对偶问题Min=Yb，YAC，Y 0也有最优解,且目标函数值相等. 珐妮冠死渗责住谨间棺睬染郑天平工问属添漾驰絮敬褒坪窑适情贸顺郁卫运筹学复件 02对偶理论运筹学复件 02对偶理论综上所述，一对对偶问题必然是以下的三种情况： 都存在最优

24、解，且最优的目标函数值相等 都无可行解 一个是无界，另一个无可行解盎第关填殉键河资世札叫飞舀醋派揣俘卜核扇辖启齿纠棒废寸裂充童铆黄运筹学复件 02对偶理论运筹学复件 02对偶理论 5.互补松弛定理 设原问题为Maxz=CX， AX+XS=b，X，XS 0 ， 对偶问题为Min=Yb， YA-YS=C，Y，YS0 ，若 X*、Y*分别为原、对偶问题的可行解，则Y*XS=0，YSX*=0，当且仅当X*、Y*分别为原对偶问题的最优解。证明： 若X* 、Y*分别为原、对偶问题的可行解 则AX*+XS=b，X*，XS 0 Y*A-YS=C，Y*，YS0,将C、b代入目标函数 Z=CX*=（Y*AYS）X

25、* =Y*AX*-YSX* =Y*b=Y*（AX*+XS）=Y*AX*+Y*XS 1.若X*、Y*为最优解,则CX*=Y*b,因此必有Y*XS=0,YSX*=0 2.若Y*XS=0,YSX*=0,则Y*b=Y*AX*=CX*因此由定理3知，X*、Y*为分别为P、D的最优解。六骗搬撇港尧芍购知娱勾佣率易淳舒贝萝掉符射城蘸纵望爸仕蟹怖手旋初运筹学复件 02对偶理论运筹学复件 02对偶理论例Max z=9 X1+ 5X2 + 8 X3 3X1+ X2 + X3 5 Y1 X1 + X2 + 8X3 1 Y2 X1， X2 0Y*XS=0,即对偶问题的决策变量与它所对应的原问题方程中的松弛变量至少有一

26、个变量为0。YSX*=0对偶方程中的松弛变量与该方程所对应的原问题决策变量至少有一个变量为0。Minz= 5Y1+Y2 3Y1+Y2 9 X1 Y1 +Y25 X2 Y1+8Y2 8 X3 Y1 ，Y2 0 Y1 . X4 =0， Y2 . X5 =0 Y3 .X1 =0， Y4 .X2 =0， Y5 .X3 =0差咐衷棠耍抹矢寂超责扫丫甸享劲疑脾般碎摸针筹椎搂崎质压猖尊繁熙稗运筹学复件 02对偶理论运筹学复件 02对偶理论例：Min =2 X1+ 3X2 + 5 X3 + 2 X4 + 3 X5 X1+X2 +2 X3 + X4 + 3 X5 4 Y1 2X1-X2 +3 X3 + X4 +

27、 X5 3 Y2 X1， X2 ， ， X5 0其对偶问题的解为Y1*=4/5，Y2 *=3/5，Z*=5，用对偶理论求原问题的最优解解：对偶问题为Max z=4Y1+3Y2 Y1+2Y2 2 X1 Y1 -Y2 3 X22Y1+3Y2 5 X3 Y1 + Y2 2 X43Y1+ Y2 3 X5 Y1 ，Y2 0将Y1*=4/5，Y2 *=3/5代入约束方程Y1 * +2Y2 * =2 X1 Y1 * -Y2 * = 1/53 X2 2Y1 * +3Y2 * = 17/55 X3 Y1 * + Y2 * = 7/52 X4 3Y1 * + Y2 * =3 X5 Y1 ，Y2 0可见最优解处 为

28、严格不等式（即松弛变量不等于0）飞茄窘僳剐徽匝盐蕊资扁兹墨眼惹霞难婉也它穆剧肤悲尘薛携臀廉赘搂帮运筹学复件 02对偶理论运筹学复件 02对偶理论Min =2 X1+ 3X2 + 5 X3 + 2 X4 + 3 X5 X1+X2 +2 X3 + X4 + 3 X5 4 Y12X1-X2 +3 X3 + X4 + X5 3 Y2 X1， X2 ， ， X5 0Max z=4Y1+3Y Y1+2Y2 2 X1 Y1 -Y2 3 X22Y1+3Y2 5 X3 Y1 + Y2 2 X43Y1+ Y2 3 X5 Y1 ，Y2 0续上页：由于最优解处 为严格不等式（即松弛变量不等于0），由互补松弛定理Ys

29、X*=0 ， Y * Xs=0 X2 * = X3 * =X4 * =0由于Y1*=4/50，Y2 *=3/5 0 ，（即 Y * 0 ） X6 = X7 =0即最优解处原问题约束应为严格等式X1 * +X2 * +2 X3 * + X4 * + 3 X5 * =4 2X1 * -X2 * +3 X3 * + X4 * + X5 * =3解方程组得X1 * =1， X5 * =1X*=（1，0，0，0，1）听睬锡壬怠锗礁管侧偶擎昧喂冷飞乃窖贝衍揩似皂抚挡用鸽佩糊勉尚砌广运筹学复件 02对偶理论运筹学复件 02对偶理论 6.设原问题Maxz=CX，AX b，X 0 对偶问题Min=Yb，YAC，

30、Y 0 则原问题单纯形表检验数反号以后对应对偶问题的一个基本解.孟筋袱仙蝗潜朽碘档许镐在亥汰罪烹洞笺徒竹情毛掸额弃苛成瞄卿票睫寥运筹学复件 02对偶理论运筹学复件 02对偶理论证明：设B为原问题的一个可行基 A=（B，N），C=（CB，CN），X=（XB，XN）T 则原问题模型为Maxz=CBXB+ CN XN+CS XS BXB+ NXN + XS=b， XB，XN1，XS0 XB决策变量中的基变量， XN决策变量中的非基变量 非基变量的检验数CN - CB B-1 N ，- CB B-1 对偶约束YA YS=C可表示为Y（B,N）-YS= （CB,CN） （ YB，YN） -（YS1 ，Y

31、S2 ） =（CB，CN） YB -YS1 = CB ， YN - YS2 = CN 将Y=CB B-1 代入上式 CB B-1B -YS1 = CB ， CB B-1N-YS2 = CN-YS1 = CB - CB B-1B=0 ， -YS2 =CN -CB B-1N ，而-Y =-CB B-1 原问题检验数行的检验数反号以后对应对偶问题一个基本解屿辟臼诸蝴顾轨贸郁匹貌虽驮储碗坯建咐闭卢籽抄筏抨孤皇撑遭唇屿鉴程运筹学复件 02对偶理论运筹学复件 02对偶理论XBXN1 XS0CN -CB B-1N-YS1-YS2- Y-CB B-1-YS1 = CB - CB B-1B=0 ， -YS2 =

32、CN -CB B-1N ，而-Y =-CB B-1 笋秤舅废蛹盟茹宙版菇链烤殷姥弟渤姨感刺色衬得窄堕郭懂商晕麻送编靖运筹学复件 02对偶理论运筹学复件 02对偶理论Max z=9 X1+ 5X2 + 8 X3 3X1+ X2 + X3 + X4 =5 Y1 X1+X2 +8X3+ X5 =1 Y2 X1， X2 0Minz= 5Y1+Y2 3Y1 + Y2- Y3 = 9 X1 Y1 + Y2 Y4 = 5 X2 Y1 +8Y2 Y5 = 8 X3 Y1 ，Y2 0X1 X2 X3 X4 X59 5 8 0 0CB XB bX4 X50 05 13 11 11 81 00 1j9 5 8 0

33、0X4 X10 92 1 0 11 0j0 -4 -64 0 -9 -2 1-23 8-3 1互补松弛定理 Y*XS=0，YSX*=0Y1 X4 =0,Y2 X5 =0 Y3 X1 =0,Y4X2 =0 ,Y5X3 =0 解的对应关系 1 2 3 4 5 Y3 Y4 Y5 Y1 Y2Y*=（0，9，0，4，64）肢灼促掸赠笛赐怀脸噎哗持康旗观递沙溜蛔骗样输冀簇碧帝爹求比滨袄鸭运筹学复件 02对偶理论运筹学复件 02对偶理论对偶单纯形法基本思路：单纯形法（1）始终保持原问题解的可行性（bi0）（2）通过迭代：原问题由基本可行解最优解（ j 0 ） 对偶问题由基本解基本可行解（Yj0 ） 对偶单纯

34、形法（1）始终保持对偶问题解的可行性（j 0 ）（2）通过迭代：对偶问题由基本可行解最优解（bi0） 原问题由非可行解基本可行解 对偶单纯形法适用条件：（1）b列中有负分量（原问题不可行）（2）检验数行所有检验数j 0 （对偶问题可行）辆疮钱犊浪产持拟袄闻茅样兑规诉笑萝梭云釜伏败禁扔喜旋夺至帽抓匀设运筹学复件 02对偶理论运筹学复件 02对偶理论 对偶单纯形法的计算步骤： 1.确定初始基，列初始表（要求全部j0 ） 2.最优解判断： 若B-1 b全0，停；否则取 MinB-1 b B-1 b0=（ B-1 b）L ，则令XL离基，检查XL行的系数alj ，若alj全部0，原问题无可行解，停止；

35、否则若有alj0，进行下一步。 3.确定进基变量4.迭代漱锰逸馅脆芬泊瘸葬治翼雨事挎腊逢焦卓卯虱莱椅蒙汉请刀炉语斥涎工耕运筹学复件 02对偶理论运筹学复件 02对偶理论例6：Min =2 X1+ 3X2 + 4 X3 X1+2X2 + X3 3 2X1-X2 +3 X3 4 X1， X2 ， X3 0将上面模型化成标准型Maxz=-2 X1- 3X2 - 4 X3 -X1-2X2 - X3 +X4 = -3 -2X1+X2 -3X3 +X5 = - 4 X1，X2 ，X3 0 们缝垢剃鳖尺涨环抄囤柄急井闺井用昨专雇笨沉篙扯逾涝莲迂杂常俩蚌馏运筹学复件 02对偶理论运筹学复件 02对偶理论CB

36、XB b X1 X2 X3 X4 X5-2 -3 -4 0 0 X4X500-3-4-1 -2 -1 1 0 -2* 1 -3 0 1 -2 -3 -4 0 0 X4X1 0-22 1 -1/2 3/2 0 -1/2-1 0 -5/2* 1/2 1 -1/2 0 -4 -1 0 -1 X2X1-3-2 2/5 0 1 -1/5 -2/5 1/511/5 1 0 7/5 -1/5 -2/5 0 0 -9/5 -8/5 -1/5 最优解为X*=（11/5，2/5，0 ，0，0）Y*=（8/5，1/5）Maxz=-2 X1- 3X2 - 4 X3 -X1-2X2 - X3 +X4 = -3 -2X1

37、+X2 -3X3 +X5 = - 4 X1， X2 ， X3 0浙摔来摆筹尼袜钞拐快涕闷咨状冰疾钥堂篷怀蓬哎卜先约阉嫩栋富丙鸽飘运筹学复件 02对偶理论运筹学复件 02对偶理论对偶问题的经济解释影子价格定义：在一对 P 和 D 中，若 P 的某种资源bi 增加一个单位时，所引起的目标函数最优值Z* 的变化量y*i （即对偶解），称为第 i 种资源的影子价格，又称为边际价格。 CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CNCB B-1NCB B-1XB =B-1b，Y= CB B-1 ， Z=CB B-1b 戍端道磺据耿眷宙翻旺侦善遇层囤乞谤戚陇谓烫种薄

38、幕迭蚜漱叙肩频鹤圭运筹学复件 02对偶理论运筹学复件 02对偶理论设B是问题 P的最优基， X*、Y*分别为原对偶问题的最优解，则最优解时目标值相等， Z*=CX* =CB B-1b =W*=Y*b即最优值与资源量的关系是Z*= Y1 * b1 + Y2 * b2 + + Ym* bmi第种资源量,Yi对偶解若把Z*看成b1 ， b2 ， ， bm的函数则对偶解Yi*含义是在现有条件下，最优目标值随资源数量变化的变化率， 反映bi的边际效益（成本）。显然Yi*是对第I种资源价值的一种估计，反映第i种资源 增加一个单位时，所引起的目标函数最优值Z* 的变化量，称为bi的影子价格，由于 Y=CB

39、B-1 ，当A、C、b变化，影子价格变化衬吧箍函救刮学倔筷浅蔚涪翠戒糜杯复眠皑膘蒜指慰胺苦形挨醉洱家籽曙运筹学复件 02对偶理论运筹学复件 02对偶理论例一生产计划问题的最终表为X1 X2 X3 X4 X5 2 3 0 0 0 CB XB bX1 X5 X24 4 22 0 31 0 00 0 1 0 -2 1/2 1/4 1/2 -1/80 10j00-1.5-1/80其对偶解为Y1 * = - 3 = 1.5，Y2 * = - 4 = 0.125 ， Y3 * = - 4 =0 说明在其它条件不变的情况下，若设备增加1台时，该厂按最优计划生产目标函数可增加1.5元，原材料A增加1kg可多获

40、利0.125元，原材料B增加1kg对获利无影响睦稳皱悄撼呼褪肩手荤瞅始对倒锌足后逆旅虏烫肪净狸旨晦念厕释呵强弃运筹学复件 02对偶理论运筹学复件 02对偶理论 X*=（4 . 2 . 0 . 0. 4）Y*=（3/2 . 1/8 . 0 ）01 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x1(4 2)(4 2.5)(4.25 1.875)开很沏涌完莽国弘酞届陶挡杠芒窝携爱肄材梳行投坯鹊萄恤蛤达吱砾蛤贫运筹学复件 02对偶理论运筹学复件 02对偶理论 可见，Yi *的值代表第i种资源的估价，这种估价不是资源市场价格，而是针对具体工厂、具体产品而存在的特殊价格，称为影子价格，上例：

41、第一种资源工时的影子价格为1.5，第二、三两种原材料资源的影子价格分别为0.125和0。 若某资源对偶解（影子价格）大于0，可增加该种资源，若某资源对偶解等于0，则不增加该种资源。 Y1 * = 1.5，Y2 * = 0.125 ， Y3 * =0 ，根据对偶解的定义，又说明当每设备台时的租金为1.5元，第二、三资源附加价格为0.125和0时，获得的利润和工厂按最优生产计划生产获得 的利润一样多。 影子价格以线性规划为基础，反映资源在最优配置状态下的一种价格估计。若目前市场上的原材料（工时）价格低于影子价格，则企业可购进扩大生产，否则企业可以卖掉部分原材料（工时）敢沈载患椽避肆镇得佳翱股序昌长

42、饶佣愁视夷啊牌先挚牌坏哎挣怀宝木法运筹学复件 02对偶理论运筹学复件 02对偶理论灵敏度分析 一、灵敏度分析的含义和内容 1、什麽是灵敏度分析？ 研究线性规划模型某些参数的变化对最优解的影响及其程度的分析过程称为灵敏度分析或（优化后分析）。 当模型的参数发生变化后，可以不必对线性规划问题重新求解，直接在原线性规划取得的最优结果的基础上进行分析或求解，既可减少计算量，又可事先知道参数的变化范围，及时对原决策作出调整和修正。兹村淄眉肛非厅雁虽刻滨炎益常立旱兼滥额博妈迟轿珍县厅耻报窃腋捞也运筹学复件 02对偶理论运筹学复件 02对偶理论2、灵敏度分析的内容： 目标函数的系数变化对最优解的影响；约束方

43、程右端系数变化对最优解的影响； 约束方程系数变化对最优解的影响 ； 回答两个问题： 见待扑朋杉昂蟹古心猴技掂死羡诸恕郁荒岿犊鳖疥砷毫纪沥福英讶环树灶运筹学复件 02对偶理论运筹学复件 02对偶理论这些系数在什麽范围内发生变化时，最优基不变或最优解不变？系数变化超出上述变化范围时，如何用最简便的方法求出新的最优解？ 二、 进行灵敏度分析的基本原则 1、在最优表格的基础上进行； 2、尽量减少附加计算工作量； 取绝竹膀各衔致摈彩嘉哭象肮弃树尸韵奋览克伦屑古蓖久兜壬聋赶遭沪讣运筹学复件 02对偶理论运筹学复件 02对偶理论基变量 X B 非基变量XN1 XSIB-1 N1B-1B-1 b 0CN1 -

44、 CB B-1 N1-CB B-1-CBB-1 b 1.将变化后的参数aij，bi，Cj通过重新计算，直接反映到最终表中 2.检查最终表是否符合最优表条件（检查原、对偶问题的可行性） 判断标准可行解条件：B-1 b 0最优解条件：CN - CB B-1 N0（对偶可行条件） 3.据检查结果进行计算三、灵敏度分析步骤：闲遇笆则射悸撩憨除舞眯拟戎旭妻聪趁皂来瀑藕着煞吝而啸签屑妆妓搔键运筹学复件 02对偶理论运筹学复件 02对偶理论参数变化后解的变化情况及处理方法原问题对偶问题结论及计算方法可行解B-1 b 0可行解j 0 表中解仍为最优可行解不可行解单纯形法迭代寻优不可行解可行解对偶单纯形法寻优非

45、可行非可行 引入人工变量，编新单纯形表塞痛疏耸涩贴商耿拍关擞蕊取挣凝拖淮耿滇娘宾靡涂忱樊簿密农觉寝央蛰运筹学复件 02对偶理论运筹学复件 02对偶理论一.价值系数Cj变化的灵敏度分析1.非基变量Cj变化为Cj由于j = （ Cj - CB B-1 Pj） N = （ CN - CB B-1 N） A= （ C - CB B-1 A）Max z=5X1+ 8X2 + 6 X3X1+ X2 + X3 12X1 +2X2 + 2X3 20 X1， X2 0 4 1 0 0 2 -1CB XB b X1 X2 X3 X4 X55 8 6 0 0 X4X50012201 1 1 1 0 1 2 2 0

46、1 5 8 6 0 0 X1X258 8 0 1 1 -1 1 0 0 -2 -2 -3 非基变量Cj变化，只影响自身检验数 ，若Cj变化后j仍0，则最优解不变例：已知生产计划问题，用甲、乙两种原材料，生产A、B、C三种产品，其模型及单纯形表（见右侧）若Cj变为Cj ，最优解有何变化犀搔岸圃购工称茫创迄楼嫉由硼剑珊剪湾洁粕秆硫最颖擎精侍哄仙敦隋傅运筹学复件 02对偶理论运筹学复件 02对偶理论 4 1 0 0 2 -1CB XB b X1 X2 X3 X4 X55 8 6 0 0 X4X50012201 1 1 1 0 1 2 2 0 1 5 8 6 0 0 X1X258 8 0 1 1 -1

47、 1 0 0 -2 -2 -3 最优基B-1= 2 -1-1 1解：由于j = （ Cj - CB B-1 Pj） 若C3变为C3 3 = C3- CB B-1 P3 = C3- （5，8）01= C3- 8 0即当C38 时最优解不变慷是付羽仪砰波臣载棠陨稗睡矢答案纂笛梳贷旱璃抽惫屑头痴贴浮艇栖停运筹学复件 02对偶理论运筹学复件 02对偶理论若C3由6变为10最优解有何变化3 = C3 - CB B-1 P3 = 10- （5，8）01= 20原最终表最优解变化，最终表变为X1X258 4 1 0 0 2 -1 8 0 1 1 -1 1 0 0 -2 -2 -3 CB XB b X1 X2

48、 X3 X4 X55 8 6 0 0 X1X258 4 1 0 0 2 -1 8 0 1 1 -1 1 0 0 -2 -3 CB XB b X1 X2 X3 X4 X55 8 0 0 102X1X3 510 4 1 0 0 2 -1 8 0 1 1 -1 1 0 -2 0 0 -5 澜隙罩啥面淬柞砌雌另撮度创歼榨儡萌孰朱蕉室卫立止令瞻辐咱的村蝴簧运筹学复件 02对偶理论运筹学复件 02对偶理论2.基变量Cj变化 基变量Cj变化CB变化，所有j 全发生变化 若Cj变化后j 全0则最优解不变上例： C1变化A= C - CB B-1 A=(1,2,3,4,5)=（ C1 8 6 0 0）-（ C1

49、 8）0 0 2 -10 1 1 -1 1 =（ 0 0 -2 -2C1+ 8 C1- 8 ）只要-2C1+ 8 0 C1- 8 0即4 C1 8时最优解不变若C1由5变为10，则 5=20，最优解变化，需基变换求新最优解 （见下页）X1X258 4 1 0 0 2 -1 8 0 1 1 -1 1 0 0 -2 -2 -3 CB XB b X1 X2 X3 X4 X55 8 6 0 0 原最终表软害了鼠喇傅末裁喘疼咬寓栖蟹垣窒症蓄酌搞壶墒幼析殆叫锯涤愿庙缮旨运筹学复件 02对偶理论运筹学复件 02对偶理论若C1由5变为10，最优解有何变化？由于A= C - CB B-1 A =（ 0 0 -2

50、 -2C1+ 8 C1- 8 ）当C1 =10 ，5=20，最优解变化 X1X28 4 1 0 0 2 -1 8 0 1 1 -1 1 0 0 CB XB b X1 X2 X3 X4 X58 6 0 0 1010-2-122X1X510 0 12 1 1 1 1 0 8 0 1 1 -1 1 0 -2 -4 -10 0 X1X258 4 1 0 0 2 -1 8 0 1 1 -1 1 0 0 -2 -2 -3 CB XB b X1 X2 X3 X4 X55 8 6 0 0 原最终表酵棺魂站泊底邦蜘亥宫捶猎盲寿速帚箍作夏洲盂除狭冉溃玫童姜班掣蠢赏运筹学复件 02对偶理论运筹学复件 02对偶理论二

51、、资源量变化的灵敏度分析 b变化只影响CBB-1 b 和B-1 b 1.bi变化，若B-1 b 0，最优基不变上例： b1改变B-1 b= 2 -1-1 1 b1200 2b1-20 0 -b1+20 0即当20 b1 10时，最优基不变2.b1改变， b1 =30B-1 b= 2 -1-1 1 3020= 40-10由于b2=-100，最优基变化（见下页）X1X258 4 1 0 0 2 -1 8 0 1 1 -1 1 0 0 -2 -2 -3 CB XB b X1 X2 X3 X4 X55 8 6 0 0 原最终表故解瑶俭持刮低委亮愤寸蜘磅斋讳耪棕土镑闷藤弹震照憎验蝶轿赂索辈敲运筹学复件

52、02对偶理论运筹学复件 02对偶理论当b1 =30B-1 b= 2 -1-1 1 3020= 40-10将数据填入最终表X1X258 4 1 0 0 2 -1 8 0 1 1 -1 1 0 0 -2 -2 -3 CB XB b X1 X2 X3 X4 X55 8 6 0 0 原最终表X1X2 5 81 0 0 2 -1 0 1 1 -1* 1 0 0 -2 -2 -3 CB XB b X1 X2 X3 X4 X55 8 6 0 0 40-10X1X450 20 1 2 2 0 1 10 0 -1 -1 1 -1 0 -2 -4 0 -5 编靡腿敌译昭软动制纺予坤桓诣乖疽伴垂旧盐暇恿帮舆秤洲壮禄

53、核雇颇豢运筹学复件 02对偶理论运筹学复件 02对偶理论三、技术系数变化的灵敏度分析有两种情况增加新产品（增加变量）工艺改变（系数aij改变）1.上例有一种新产品D，生产一个单位消耗原材料甲3，乙2，可得利润10，问生产D是否有利可以直接计算其检验数并检查 原最终表 X1 X2 X3 X4 X5CB XB b 5 8 6 0 0 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 1 00-2-2-3设生产D产品 X6 个单位6= C6 - CB B-1P6= 10 -（2，3） 3 2 最优解不变，生产D产品无利=-2寥蔑缩弦沏亲咬笆看殊氢彭硷遵仿掌弊再饯殖褪郴弱啦领沉特玩余

54、篷郁酱运筹学复件 02对偶理论运筹学复件 02对偶理论若C6 =15，最优解有何变化？ 原最终表 X1 X2 X3 X4 X5CB XB b 5 8 6 0 0 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 1 00-2-2-3设生产D产品 X6 个单位6= C6 - CB B-1P6= 15 -（2，3） 3 2 =+3最优解变化，P6 = B-1P6 = -1-1 1 3 2 = 4 -1 X1 X2 X3 X4 X5 CBXB b5 8 6 0 0 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 1 00-2-2-3 X6 15 4 -1 315

55、 X6 1 1/4 0 0 1/2 -1/4 1 8 X2 9 1/4 1 1 -1/2 3/4 0 -3/400-2-7/2-9/4在原最终表中增加一列铣呕度蠢雇之裙钙另媚贺耸寻踢墨火丑娜粳啊髓捶少第颅俩傈植莫痢淌循运筹学复件 02对偶理论运筹学复件 02对偶理论四、增加新约束的灵敏度分析增加1个约束条件：相当于单纯形表增加1行 首先将原最优解代入新增约束检查是否满足？是，则说明新增约束不影响最优解。否则再作下面的讨论： 将新增约束标准化，添加到原最优表格中（相当于单纯形表新增1行）； 进行规格化处理用矩阵的行变换将当前基变成单位矩阵；用适当方法（通常是对偶单纯形法）进行迭代求出新的最优解。

56、 亨峭度逆柴办严绍辅羌问耐驳丽泪肚恳闭凶机讶惰垒典鸦玫脉蓬丢历百济运筹学复件 02对偶理论运筹学复件 02对偶理论上例新增加电力约束，电力供应量为13，A、B、C产品每单位需电各2，1，3，问方案是否改变？新增约束条件2X1 + X2 +3 X3 13将原最优方案（决策变量X1 = 4 ，X2 = 8 ）代入该约束，若满足，最优解不变。代入方程1613，原方案改变，在约束中加入松弛变量2X1 + X2 +3 X3 + X6 =13加到最终表中（见下页）蜂盒环垮轧诀撂叠阴贷纤倒庸枣郧差掷函己审瀑敲酱词聪宙肌逆恰娶捷蜒运筹学复件 02对偶理论运筹学复件 02对偶理论X1 X2 X3 X4 X5CB

57、 XB b5 8 6 0 0 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 1 00-2-2-30 X6 13 2 1 3 0 0 100 5 X1 4 1 0 0 2 -1 0 8 X2 8 0 1 1 -1 1 0 00-2-2-3 0 X6 -3 0 0 2 -3 1 1 5 X1 2 1 0 4/3 0 -1/3 2/3 8 X2 9 0 1 1 /3 0 2/3 -1/3 -10/3-11/3 0 X6 1 0 0 -2 /3 1 -1/3 -1/3 -2/3砸知更素憾啦诣蔗锻善晾您醒凭授器唯另埂腑忻漏壤翌厨荫吧藏阿汇烂者运筹学复件 02对偶理论运筹学复件 02

58、对偶理论小结1.用矩阵表示的单纯形表以此模型构造单纯形表如下：CBCN0XBbXBXNXSXBB-1bIB-1NB-1-Z-CBB-1b0CN-CBB-1N-CBB-1化标准型腑纱躺挤陪惮攀叭闹缉骚溅莉诈沥臂燃誉眉寂妮酌锚碉症怠癌蜡凶旭枚行运筹学复件 02对偶理论运筹学复件 02对偶理论2.对偶问题及对偶理论（性质）对称性：对偶问题的对偶问题是原问题弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值 无界性：原问题无界，对偶问题无可行解对偶定理： （强对偶性）：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解

59、Y*=CBB-1互补松弛定理： 对偶问题的解 利用原问题的最优单纯形表求解对偶问题的最优解。对称型原、对偶问题，将原问题单纯形表检验数反号以后对应对偶问题的一个基本解. 3.对偶单纯形法 4.灵敏度分析市母脾盏棍讫躇平酞登樱妊愉扶猛蛹淹听酋葫橱惟娜柴靶蹬称容誉撅孝烷运筹学复件 02对偶理论运筹学复件 02对偶理论 一、判断下列说法是否正确 1.任一线性规划问题存在并具有唯一的对偶问题 2.对偶问题的对偶一定是原问题 3.根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解。反之，当对偶问题无可行解时，其原问题具有无界解 分别为标准形式的原、对偶问题的可行解，4.设X*，Y*分别为其最优解

60、，则恒有6/24/2022粟辆漏熊羡晾虹睬斥箔根仗壮裤读辗挫察疙硅吗琉麓湃雹揖挪剁墅脊太檬运筹学复件 02对偶理论运筹学复件 02对偶理论 6.已知Yi*为线性规划对偶问题的最优解，若Yi*0，说明在最优生产计划 中，第I种资源已完全耗尽。 7.已知Yi*为线性规划对偶问题的最优解，若Yi*=0，说明在最优生产计划 中，第I种资源一定有剩余。 8.若某种资源影子价格等于k，在其它条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k。 9.若线性规划问题中的bi，Cj同时变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解情况。 10.在线性规划问题的最优解中，若某