线性规划对偶理论

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

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