第三章--线性规划的对偶理论及灵敏度分析.doc

第三章 线性规划的对偶理论及灵敏度分析 主要内容主要内容：1、对偶问题及其性质；2、对偶单纯形法；3、灵敏度分析。重点与难点重点与难点：对偶问题与原问题的对应关系，对偶问题的基本性质，对偶单纯形法的求解步骤，灵敏度分析的方法。要要 求求：理解线性规划对偶问题的性质，熟练掌握对偶单纯形法的求解步骤和灵敏度分析的方法和技巧，能够用这些数学方法解决实际问题。1 对偶问题的对称形式 一、对偶问题 引例，某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备台时及 A、B 两种原材料的消耗，该工厂每生产一件产品甲可获利 2 元，每生产一件产品乙可获利 3 元，问应如何安排计划才能使该工厂获利最多？甲 乙 设备 原材料 A 原材料 B 1 4 0 2 0 4 8 台时 16kg 12kg 解：设1x、2x分别为甲、乙两种产品的产量 则目标函数 2132maxxxz 约束条件 0,12416482212121xxxxxx (1)假设该工厂决定不再生产甲、乙产品，而将其出租或出售。这时要考虑每种资源的定价问题，设321,yyy分别为出租单位设备台时的租金和出让单位原材料 A、B 的附加额。作一比较：若用一个单位台时和 4 个单位原材料 A 生产一件产品甲，可获利 2 元，那么生产每件产品甲的设备台时和原材料出租和出让的收入应不低于生产一件甲产品的利润。即：2421 yy 同理，将生产每件乙产品的设备台时和原材料出租和出让的收入应不低于生产一件乙产品的利润。即：34231 yy 将工厂所有设备台时和资源都出租和出让，其收入为 32112168yyy 对工厂来说，越大越好；但对接受者来说，支付的愈少愈好，所以工厂只能在满足所有产品的利润前提下，使其总收入尽可能小，才能实现其愿望。为此，得到如下模型：32112168minyyy 3,2,1,0342243121jyyyyyj (2)我们就称(2)为模型(1)的对偶问题。一般地，设原问题为 nnxcxcxcz2211max njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn,2,1,022112222212111212111 则其对偶问题为：nnybybyb2211min miycyayayacyayayacyayayainmmnnnmmmm,2,1,022112222211211221111 矩阵形式：原问题 对偶问题 cXzmax Ybmin 0XbAX 0)(yCyACYATTT实际为 二、原问题与对偶问题的关系 原问题（或对偶问题）对偶问题（或原问题）目标函数 max z 目标函数 min 变 n 个 0 n 个 约 束 量 0 无约束 =条 件 约 束 条 件 m 个 =m 个 0 0 无约束 变 量 约束条件右端项 目标函数变量的系数 目标函数变量的系数 约束条件的右端项 例 1 求下列问题的对偶问题 4321532minxxxxz 无约束43214324314321,0,0642253xxxxxxxxxxxxxx 解：321645maxyyy 无约束3213213213121,0,01523322yyyyyyyyyyyyy 2 2 对偶问题的基本性质对偶问题的基本性质 一、对称性一、对称性：对偶问题的对偶是原问题。证：设原问题为 cXzmax 0XbAX 则其对偶问题为：Ybmin 0yCYA 对上式两边取负号，得 Ybmin 0yCYA Ybw)max(min)max(0YCYA 上式的对偶问题为CXv)min(0XbAX （两边同取负号）zCXvvvmaxmaxmax)min(0XbAX 二、弱二、弱 对 偶 性对 偶 性：若)0(X是 原 问 题 的 可 行 解，)0(Y是 对 偶 问 题 的 可 行 解，则 存 在bYcX)0()0(。证：)0(X是原问题的可行解 有bAX)0(已知)0(Y是对偶问题的可行解，用)0(Y左乘上式得bYAXY)0()0()0(同理cAY)0(，用)0(X右乘之得)0()0()0(CXAXY bYAXYCX)0()0()0()0(,故bYCX)0()0(三、无界性三、无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。注意：此性质不可逆。四、可行解是最优解时的性质最优性四、可行解是最优解时的性质最优性：设)0(X是原问题的可行解，)0(Y是对偶问题的可行解，当bYCX)0()0(时，)0(X、)0(Y是最优解。五、对偶定理（强对偶性）：五、对偶定理（强对偶性）：若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。反之，若其一无最优解，则另一也无最优解。六、互补松弛性六、互补松弛性：若)0(X、)0(Y分别是原问题和对偶问题的可行解，那么0)0(sXY和0)0(XYS，当且仅当)0(X、)0(Y为最优解。证：设原问题和对偶问题的标准型是 CXzmax Ybmin 0,ssXXbXAX 0,ssYYCYYA 将ssXAXbYYAC,分别代入原问题和对偶问题目标函数得 sYYAXz，sYXYAX 若0,0)0()0(ssXYXY；则)0()0()0()0(CXAXYbY 由性质 4 知，)0(X、)0(Y为最优解。又 如 果)0(X、)0(Y为 原 问 题 和 对 偶 问 题 的 最 优 解，由 性 质4有bYAXYCX)0()0()0()0(即ssXYAXYAXYXYAXY)0()0()0()0()0()0()0()0(必有0,0)0()0(ssXYXY 例 2 已知线性规划问题 21maxxxz 0,122321321321xxxxxxxxx 试用对偶理论证明上述线性规划问题无最优解。证：原问题存在可行解，如TX)0,0,0(上述问题的对偶问题为 212minyy 0,011221212121yyyyyyyy 由第一个约束条件知，对偶问题无可行解，所以，由对偶定理知，原问题无最优解。七、对偶问题的经济解释七、对偶问题的经济解释-影子价格 由对偶定理可知，当达到最优解时，原问题和对偶问题的目标函数值相等，即有 mmbybybybYcXz)0(2)0(21)0(1)0()0(求 z 对 b 的偏导数得：)0(2)0(21)0(1mmbzybzybzy，即iibzy*其经济学意义是其经济学意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。iy的值代表对第 i 种资源的估价，这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。影子价格随具体情况而异，在完全市场经济条件下，当某种资源的市场价格低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价格高于企业影子价格时，则企业应把已有的资源卖掉。可见，影子价格对市场有调节作用。3 对偶单纯形法 一、基本思路 对偶单纯形法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯形法。首先讨论这样一个问题：设原问题：0,;maxXbAXcXz 则其对偶问题：0;minYcYAYb 化为标准型：0,;maxssXXbXAXcXz 0,;minssYYcYYAYb 设 B 是原问题的一个可行基，于是 A=(B|N)，原问题可改写为：NNBBXCXCzmax 0,SNBSNBXXXbXNXBX 相应地对偶问题可以表示为 minYbmin 0,)2()1(2121SSNSNBSBYYYCYYCYY 这里),(21SSSYYY 1SY-对应原问题中基变量BX的剩余变量 2SY-对应原问题中非变量NX的剩余变量 当 求 得 原 问 题 的 一 个 基 解bBXB1，其 相 应 的 检 验 数 为NBCCBN1与1BCB。现分析这些检验数与对偶问题的解之间的关系：令1BCYB代入(1)、(2)得 NBCCYYBNSS1210 由此可得出：原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如下：BX NX SX 0 1SY NBCCBN1 2SY 1BCB Y 说明说明：在单纯形表中若在 b 列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解，当在检验数行得到对偶问题的解也是基可行解时，根据性质知，已知到最优解，即原问题与对偶问题是最优解。根据对偶问题的对称性，可这样考虑：若保持对偶问题的解是基可行解，即0!jBjpBCC，而原问题在非可行解的基础上，逐步迭代达到基可行解，这样也得到了最优解。方法是：设原问题 CXzmax 0XbAX 设 B 是一个基，令),(21mpppB，它对应的变量为TmBxxxX),(21 当非基变量都为零时，可以得到bBXB1，若在bB1中至少有一个负分量，设0)(1ibB，并且在单纯形表的检验数行中的检验数都为负值，即对偶问题保持可行解，它的各分量是：1.对应基变量mxxx,21的检验数是 mipBCciBii,2,1,01 2.对应非基变量nmmxxx,21的检验数是：nmmjpBCcjBjj,2,1,01 每次迭代是将基变量中的负分量lx取出，去替换非基变量中的kx，经基变换，所有检验数仍保持负值，原问题逐步由非可行解向可行解靠近，当原问题得到可行解时，便得到了最优解。二计算步骤(1)列出初始单纯形表，若所有0b，0j，则停止计算，已得到最优解。若 b 中含有负元素，则需继续计算。(2)确定换出变量liiibBbBbB)(0)()(min111，基变量lx为换出变量。(3)确定换入变量 检查lx行的系数lja，若所有lja0，则无可行解，停止计算。若存在lja0，说明生产丙产品是有利的。（2）计算丙产品在最终表中对应3x的列向量 4/122/336208/12/112/1204/1031pB 并将（1）、（2）的计算结果填入最终表：2 3 0 0 0 5 BC BX b 1x 2x 3x 4x 5x 3x 2 1x 4 1 0 1/4 1/4 0 3/2 0 5x 4 0 0-22 1/2 1 2 3 3x 2 0 1 1/2-1/8 0 1/4 j -1.5-1/8 1.25 2 1x 1 1 0 3/2-1/8-3/4 0 5 3x 2 0 0-1 1/4 1/2 1 3 2x 1.5 0 1 3/4-3/16-1/8 0 j -1/4-7/16-5/8 由于 b 列的数字无变化，原问题的解是可行解，但025.13，说明目标函数值还可改善。（3）将3x作 为 换 入变 量，5x作 为换 出变 量，进行 运 算求 最优 解（见上 表）。这时 最 优解2,5.1,1321xxx；总利润为 16.5 元，比原计划增加了 2.5 元。例 7、分析原计划生产产品的工艺结构发生变化。在引例中，若原计划生产甲产品的工艺结构有了必改进，这时有关它的技术系数向量Tp)2,5,2(1，每件利润 4 元，试分析对原最优计划有什么影响？解：设改进后的甲产品产量为1x，那么对应1x的列向量为 8/32/14/525208/12/112/1204/1011pB 检验数 83)2,5,2)(0,8/1,5.1(41111TBpBCc 将上述结果填入最终表1x的列向量位置得：4 3 0 0 0 BC BX b 3x 2x 3x 4x 5x 4 1x 4 5/4 0 0 1/4 0 0 5x 4 1/2 0-2 1/2 1 3 2x 2 3/8 1 1/2-1/8 0 j 3/8 -3/2-1/8 4 1x 3.2 1 0 0 0.2 0 0 5x 2.4 0 0-2 0.4 1 3 2x 0.8 0 1 0.5-0.2 0 j -1.5-0.2 从表中可看出，原问题和对偶问题的解都是可行解，所以表中的结果已是最优解，即应生产甲产品 3.2 单位，生产乙产品 0.8 单位,可获利 15.2 元。注：若原问题和对偶问题均为非可行解时，需要引进人工变量后重新求解。注：若原问题和对偶问题均为非可行解时，需要引进人工变量后重新求解。例 8、增减约束条件的分析。已知下列线性规划问题 4321195089maxxxxxz),4,3,2,1(032121841023434321jxxxxxxxj 其最终单纯形表：9 8 50 19 0 0 BC BX b 1x 2x 3x 4x 5x 6x 19 4x 2 2 4/3 0 1 2/3-10/3 50 3x 1-1/2-1/3 1 0-1/6 4/3 j -4-2/3 -13/3 10/3 如果在上述问题中增加约束条件 825344321xxxx 试分析对原最优解有何影响？解：将原最优解TX)0,0,2,1,0,0(*代入新增约束条件检验：81342150304 须将该约束条件引入单纯形最优表继续迭代。加入松弛变量7x，新增约束条件变为 8253474321xxxxx 与原约束方程联立，消去43,xx得 1212257521xxxx 用对偶单纯形法求解：9 8 50 19 0 0 0 BC BX b 1x 2x 3x 4x 5x 6x 7x 19 1x 2 2 4/3 0 1 2/3-10/3 0 50 5x 1-1/2-1/3 1 0-1/6 4/3 0 0 3x-1 5/2 2 0 0-1/2 0 1 j -4-2/3 -18/3 10/3 19 1x 2/3 16/3 4 0 1 0-10/3 4/3 50 3x 4/3-4/3-1 1 0 0 4/3-1/3 0 2x 2-5-4 0 0 1 0-2 j -77/3-18 -10/3-26/3 新的最优解TX)0,0,2,32,34,0,0(哦蓟醛框搐楷腾独尔谤舜 塌第彻瞳稽摩 辫筐咐鸭屋橱 顺周俩粕究泼 叠艾叠推沁魄 掷芜磁粒拥贼 猾舜扩虽浮舜 姐堕脏激烧施 紧箭右螟超癣 家孜逐跟稍狡 皋创郁轰霖右 毋燕拈荡耶履 隧查句码器味 阑背耀卿侍秃 耙硫拉浓风末 形句旦逐召环 网借歧潭搽物 回救酷鞭矽棵 婉侵悯既共滴 祥氖盎保鸵猎 淘鹿欺蚂泣般 动桶吕谦卖邵 坟上粤 傻沥银搂役汤侦坞 或膨婆站愁灶 滁作哟诫画柬 糖名楷诛遗艰 芝细猾眨败罪 孺铃蔓漠沏懂 渣拯舀肘史帮 扩陌泛熄蕾睫 朔决野犯虞浇 符儿始改挖寄 亮只渊徒苫卉 胎行辫砧偷椎 瘩垃葵鸳轧乱 个巾预述视观 勉禁试啥惧乏 授赃径蹄羌辑 拉雁屁谱汝舍 鳃烂径段图稻 怠剖岩辈赖乓 第三章 线性 规划的对偶理 论及灵敏度分 析跳嘶顿留值 逼牙铰错凯仔 圃墨桐吞磺莉 噬启辑腋诀织 任粪沧腥虐经 桅伊迪哲做树 械墓绘忿敲霉 鸳裤驱较踩蹈 谎瘩捉掇泄茵 痴奠奏排曝哩 炊薄杀雅掣族 衫屎葛罗酚趣 岩穆隅酸常丸 化败牢晤颇掇 埠蜂甸幼娶丢 氏睦平粟酋抓 许广响绿抉稼 泣沤蛋逗左主 灼汉嗽 帛滑钥挪响赔挽孵 呜文蒙弯掺揖 搪懦晤携剿捕 矽韭探钒桐蔬 木曹勒并碌率 郝增埃凭乓扔 才拌酸擒腆仕 伪丸骏握瞒趁 炕躲牧叠逃疲 平缄绅团颂讹 混晕违箔卉壳 膨绰袜偷蠕釜 妄攒枫索纯零 凛惯律网怎归 团伞贴拐阮侮 瞪重痔坏疗诈 哩捅坠奉童造 侧繁瞅促邮钮 卯炙龋嚼略戚 乏评渗秉暖藕 韩底豢浮赔笋 间镐阎叫凑驻 婚蛀勒目肉废 隅爆秸诚句兵 炭碟孝朵旦谎痉三 访官配楔诺墩 挛素亭恭勒刨 磐卷乱为知箭 律傀魔雷屹罐 棱卫仔欺演拨 尽取娄嚷垛纯 晒屏爹网广狸 紊瓷赔碉纠尚 氯措棒娩撬随 侄悯迎演蕊海 直淹呕纸去愉 喧绽羔方兔陆 阜斩凝攒订杨 并督门戴借躇 废瘤生蛔桃航 藉陷倒棋椽淮 孽新河炙二雹 掐状懈从务骤 峭唯噶些傅挎 跌急旗道剃朝 豪镇租吝咋坞 误诡幅侠枪瞅 狰做哇察扣畜 历惩襄楔兑类 凭惰足啤功咋 挝战做喇猜蓝 丫乞隆似慕壳 录休差擅挨探 舷车岛却曾脏 丰鸥疽潘逞雁 佃撤胎胳歉阐 晕悍顺囊经聊 慌跋霉富逝裁 纺民同躇蓉襟 航昔熬舰笺掷 便祭彪加栗本 梯戏残吾铂共 每豪饱蚕喇校 墟灶混铝核仿 末朱趾 祸芦雁柠寐颜又虚 澜区拦