第二章对偶问题课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第二章对偶问题课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 对偶 问题 课件
- 资源描述:
-
1、III每天可用能力每天可用能力设备设备A(h)设备设备B(h)调试工序(调试工序(h)06152115245利润(元)利润(元)21例1 0,52426155s.t.2max212121221xxxxxxxxxz设设y1,y2和和y3分别表示出让资源分别表示出让资源A,B和调试和调试工序的单价,则美佳公司同意出让的条件工序的单价,则美佳公司同意出让的条件将是将是同意出让生产产品同意出让生产产品I I的资源的资源同意出让生产产品同意出让生产产品IIII的资源的资源购买者希望用最少的代价获得这些资源购买者希望用最少的代价获得这些资源,因此因此2632 yy125321yyy32152415miny
2、yyz这样得到一个新的线性规划问题这样得到一个新的线性规划问题0,1252652415min32132132321yyyyyyyyyyyw称这一问题是原来的称这一问题是原来的LP问题的问题的对偶线性规对偶线性规划问题划问题或或对偶问题对偶问题,原来的,原来的LP问题也称为问题也称为原问题原问题。项目项目原原问题问题对偶问题对偶问题AbC目标函数目标函数约束条件约束条件决策变量决策变量约束条件系数矩阵约束条件系数矩阵约束条件右端项向量约束条件右端项向量目标函数系数向量目标函数系数向量max z=CX AXb X0约束条件系数矩阵转置约束条件系数矩阵转置目标函数的系数向量目标函数的系数向量约束条件
3、的右端项向量约束条件的右端项向量min w=YbAY CY 0原问题原问题max z对偶问题对偶问题min wn个决策变量个决策变量m个约束条件个约束条件n个约束条件个约束条件m个决策变量个决策变量约束条件约束条件“”型型决策变量决策变量0决策变量决策变量0约束条件约束条件“”型型对称形式的对应关系对偶问题的对偶是原问题,即对偶关系是对偶问题的对偶是原问题,即对偶关系是相互对称的关系相互对称的关系非对称形式下的对偶关系原问题原问题(对偶问题)(对偶问题)max z对偶问题对偶问题(原问题)(原问题)min wn个决策变量个决策变量m个约束条件个约束条件n个约束条件个约束条件m个决策变量个决策变
4、量约束条件约束条件“”型型约束条件约束条件“”型型约束条件约束条件“=”型型决策变量决策变量0决策变量决策变量0决策变量无约束决策变量无约束决策变量决策变量0决策变量决策变量0决策变量无约束决策变量无约束约束条件约束条件“”型型约束条件约束条件“”型型约束条件约束条件“=”型型0maxXbAXCXzNBNBCCCNBAXXX,00maxXbIXAXSXCXzsbBXBNXBIXbIXNXBXSNBSNB111原来添加松弛变量XS将XB的系数矩阵化为单位矩阵0, 00maxNBSNBXXCXCzXXbIXNXBXsNNBBCB CN 0XB XN XS0 XS bB N ICB CN 0CB C
5、N 0XB XN XSCB XB B-1bI B-1N B-10 CN CBB-1N CBB-1 初始单纯形表迭代后的单纯形表 在初始单纯形表中单位矩阵经过迭代后变为基矩阵B的逆 在初始单纯形表给出的解中基变量Xs=b,而在迭代后的表给出的解中基变量 XB=B-1b 系数矩阵的变化: A, IB-1A, I 在初始单纯形表中变量xj的系数为Pj经过迭代后变为Pj,并且Pj=B-1 Pj 若迭代后的单纯形表为最终表则该表也同时给出对偶问题的最优解项目原问题变量原问题松弛变量 x1 x2x3 x4 x5x3 15/2 0 01 5/4 15/2x1 7/2 1 00 1/4 -1/2x2 3/2
6、0 10 -1/4 3/2-j 0 00 1/4 1/2对偶问题剩余变量对偶问题变量 y4 y5y1 y2 y3项目对偶问题变量对偶问题剩余变量y1 y2 y3y4 y5y2 1/4-5/4 1 0-1/4 1/4 y3 1/215/2 0 1 1/2 -3/2j15/2 0 07/2 3/2原问题松弛变量原问题变量 x3 x4 x5x1 x2原问题最终单纯形表对偶问题最终单纯形表例1最大化问题检验数的相反数给出了对偶问题的解原本在对偶关系中,原问题的变量对应着对偶问题原本在对偶关系中,原问题的变量对应着对偶问题的约束条件,原问题的约束条件对应着对偶变量。的约束条件,原问题的约束条件对应着对偶
7、变量。但但在分别添加了松弛变量和剩余变量后,也可以建在分别添加了松弛变量和剩余变量后,也可以建立原问题变量与对偶问题变量之间的对应关系立原问题变量与对偶问题变量之间的对应关系原问题原问题对偶问题对偶问题第第i个约束条件中个约束条件中添加的松弛变量添加的松弛变量第第i个对偶变量个对偶变量第第j个变量个变量第第j个约束条件中个约束条件中添加的松弛变量添加的松弛变量注 上表中我们将松弛变量与剩余变量统称为松弛变量 弱对偶性原问题可行解的目标函数不超过对偶问题可行解的目标函数(1)原问题任一可行解的目标函数值是其对偶)原问题任一可行解的目标函数值是其对偶问题目标函数值的下界;反之对偶问题任一可行问题目
8、标函数值的下界;反之对偶问题任一可行解的目标函数值是原问题目标函数值的上界。解的目标函数值是原问题目标函数值的上界。(2)如原问题有可行解且目标函数无界(即原)如原问题有可行解且目标函数无界(即原问题为无界解),则对偶问题无可行解;反之对问题为无界解),则对偶问题无可行解;反之对偶问题有可行解且目标函数无界,则原问题无可偶问题有可行解且目标函数无界,则原问题无可行解。注意该推论的逆命题不成立。行解。注意该推论的逆命题不成立。(3)若原问题有可行解而对偶问题无可行解,)若原问题有可行解而对偶问题无可行解,则原问题目标函数无界;反之对偶问题有可行解则原问题目标函数无界;反之对偶问题有可行解而原问题
9、无可行解,则原问题目标函数无界。而原问题无可行解,则原问题目标函数无界。最优性若原问题一个可行解目标函数等于对偶问题的某个可行解的目标函数,则这两个可行解分别是原问题和对偶问题的最优解强对偶性若原问题和对偶问题都有可行解,则它们都有最优解,且最优解的目标函数值相等互补松弛性在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则其对应的约束条件取等式;反之若一个约束条件为严格的不等式,则其对应的对偶变量为零在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则该约束条件中松弛变量等于零;反之若一个约束条件中松弛变量非零,则其对应的对偶变量为零。例(p76.7)4 , 3
10、, 2 , 1, 096628342max321432214214321jxxxxxxxxxxxxxxxxzj4 , 3 , 2 , 1, 01143229668min314343214214321iyyyyyyyyyyyyyyyywi而由x1=20, 得22421yyy而由x2=20, 得434321yyyy而由x3=40, 得143 yy于是得到方程组0143224434321421yyyyyyyyyy得对偶问题最优解为0, 1,53,544321yyyy注:原问题与对偶问题最优目标函数值都是 z*=4+8+4=16式中bi是线性规划原问题约束条件的右端项,它代表第i种资源的拥有量;对偶变
11、量yi的意义代表在资源最优利用的条件下对第i种资源的估价。这种估价不是资源的市场价格,而是根据资源在生产中作出的贡献而作的估价,为区别起见,称为影子价格影子价格。*1*1*wybxczmiiinjjj设 和 分别是原问题和对偶问题的最优解,则由对偶性质,有), 1(*njxj), 1(*niyi 资源的影子价格随企业的生产任务、产品结构资源的影子价格随企业的生产任务、产品结构的改变而改变的改变而改变 影子价格是资源的影子价格是资源的边际价格边际价格 资源的影子价格也可视为一种资源的影子价格也可视为一种机会成本机会成本 在生产过程中若某种资源未得到充分利用则其在生产过程中若某种资源未得到充分利用
展开阅读全文