线性规划对偶理论

线性规划对偶理论

ID:43494720

大小:1.21 MB

页数:22页

时间:2019-10-08

线性规划对偶理论_第1页
线性规划对偶理论_第2页
线性规划对偶理论_第3页
线性规划对偶理论_第4页
线性规划对偶理论_第5页
资源描述:

《线性规划对偶理论》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、线性规划的对偶理论DualTheory§2.1对偶问题的提出例常山机器厂生产I、消耗设备III设备工时II两种产品。这两种产品工时限量都分别要在ABC三种不同设备上加工。按工艺规定,生设备A2212产每件产品的单位利润、消设备B4016耗三种设备的工时以及各种设备C0515设备工时的限额如表:利润(元)23如何安排生产才能使解:LP1maxz=2x1+3x2总的利润最大?2x+2x1212s.t.4x1165x152x0,x012假设另有四海机器厂想租借常山机器厂的全部可用资源进行生产。问:如何定位各设备的出租价格

2、,才能使得常山机器厂愿意出租设备,且四海机器厂所付租金最少。解:设A、B、C设备每小时出租的价格分别为y、y、y元,123则新的线性规划数学模型为:LP消耗设备III设备工时2工时限量minw12y16y15y123设备A22122yy1242设备B4016s..2ty5y3设备C051513yyy,,0利润(元)231231、基本概念对偶性是线性规划问题的最重要的内容之一。每一个线性规划(LP1)必然有与之相伴而生的另一个线性规划问题(LP2),即任何一个求maxz的LP1都有一个求minw的

3、LP2。将LP1称为“原问题”,记为P;将LP2称为“对偶问题”,记为D。原问题(P):对偶问题(D):max2zx3x12min12wy16yy1512322xx121224yy2124x161s.t.2yy53s.t.135x152yyy,,0123xx12,0原问题P对偶问题D原变量x1,x2对偶变量y1,y2,y3原目标z对偶目标w原约束对偶约束22xx12122yy42124x1612yy53135x152yyy1,2,3

4、0xx12,0变量约束2、基本形式对偶原问题Pmaxz=c1x1+c2x2+···+cnxns.t.a11x1+a12x2+···+a1nxnb1a21x1+a22x2+···+a2nxnb2···am1x1+am2x2+···+amnxnbmxj0,(j=1,2,···,n)对偶问题Dminw=b1y1+b2y2+···+bmyms.t.a11y1+a21y2+···+am1ymc1a12y1+a22y2+···+am2ymc2···a1ny1+a2ny2+···+amnymcnyi0,(i=1,2,

5、···,m)矩阵形式(P)maxz=CXT(D)minw=bYs.t.AXbs.t.ATTYCx0Y0其中Ccc(,c,,)12nx1baa1112a1ny11xX2b2aa2122a2nybAY2xnbaaamm1m2mnymTTTb,A,C为bAC,,的转置例:写出下列LP问题的对偶问题max5z6xx12xx2812416xst..1412x2xx,012解:对偶问题为:minw

6、8y16y12y123yy4512st..2y4y613yy,,y0123§2.2原问题与对偶问题1、基本形式的联系与区别(1)原目标求极大,对偶目标求极小;(2)原约束个数=对偶变量个数原变量个数=对偶约束个数原约束决定对偶变量原变量决定对偶约束;(3)原约束≤方向,对偶约束≥方向;(4)原目标的系数对应对偶约束的右端常数原约束的右端常数对应对偶目标的系数;(5)原系数矩阵与对偶系数矩阵互为转置;(6)原变量与对偶变量都是非负取值。2、互为对偶关系例将下列问题作为原问题,写出其对偶问题。min12

7、wy16yy1512324yy212s.t.2yy5313yyy,,0123解:先改写为原问题的基本形式:maxw12y16y15y1232yy4212s.t.25yy313yyy,,0123max12wy16yy1512324yy212s.t.2yy5313yyy,,0123最后简化得到已知问再对偶化:题的对偶问题:minz2x3xmaxz2x123x122xx122122xx12212

8、4x164x1611s.t.s.t.5x2155x215xx12,0xx12,0若LP2是LP1的对偶问题,则LP1是LP2的对偶问题。maxZ=CX对偶的定义minW=bTYs.t.ATY≥CTs.t.AX≤bY≥0X≥0改写改写minZ’=-CXma

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。