运筹学胡运权第五版课件(第二章).ppt

《运筹学胡运权第五版课件(第二章).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划的对偶理论DualTheory§2.1对偶问题的提出例常山机器厂生产I、II两种产品。这两种产品都分别要在ABC三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如表：如何安排生产才能使总的利润最大？消耗设备工时III设备工时限量设备A设备B设备C240205121615利润（元）23解：maxz=2x1+3x22x1+2x2124x1165x215x10，x20s.t.LP1假设另有四海机器厂想租借常山机器厂的全部可用资源进行生产。问：常山机器厂应该如何给这些资源定出一个合理的租金，既使四海机器厂愿

2、意租借，又使本厂能得到自己组织生产这些产品时所能获得的最大收益。解：设A、B、C设备每小时出租的价格分别为y1、y2、y3元，则新的线性规划数学模型为：LP2对偶性是线性规划问题的最重要的内容之一。每一个线性规划（LP1）必然有与之相伴而生的另一个线性规划问题（LP2），即任何一个求maxz的LP1都有一个求minw的LP2。将LP1称为“原问题”，记为P；将LP2称为“对偶问题”，记为D。原问题（P）：对偶问题（D）：1、基本概念原问题P对偶问题D原变量x1,x2对偶变量y1,y2,y3原目标z对偶目标w原约束对偶约束变量约束2、一般形式原问题Pmaxz=c1x1+c

3、2x2+···+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,···,m)其中例：写出下列LP问题的对偶问题解：对偶问题为：§2.2原问题与对偶问题（max的基本形式）（min的基本

4、形式）1、基本形式的联系与区别（1）原目标求极大，对偶目标求极小；（2）原约束个数=对偶变量个数原变量个数=对偶约束个数原约束决定对偶变量原变量决定对偶约束；（3）原约束≤方向，对偶约束≥方向；（4）原目标的系数对应对偶约束的右端常数原约束的右端常数对应对偶目标的系数；（5）原系数矩阵与对偶系数矩阵互为转置；（6）原变量与对偶变量都是非负取值。例将下列问题作为原问题，写出其对偶问题。解：先改写为原问题的基本形式：再对偶化：最后简化得到已知问题的对偶问题：2、基本形式的表格比较3、互为对偶关系若LP2是LP1的对偶问题，则LP1是LP2的对偶问题。minZ’=-CXs.

5、t.-AX≥-bX≥0minW=bTYs.t.ATY≥CTY≥0maxZ=CXs.t.AX≤bX≥0对偶的定义对偶的定义maxW’=-bTYs.t.-ATY≤-CTY≥0改写改写例写出下列问题的对偶问题。解：第一步改写为min的基本形式第二步对偶化第三步简化为已知问题的对偶问题：比较原问题和对偶问题：基本形式非基本形式4、原问题与对偶问题的互化原问题（或对偶问题）对偶问题（或原问题）目标函数max（基本）目标函数min（基本）约束条件m个m个变量≤（基本）≥0（基本）≥≤0=无约束变量n个n个约束条件≥0（基本）≥（基本）≤0≤无约束=约束条件的右端项目标函数的系数目标

6、函数的系数约束条件的右端项例直接写出下列线性规划问题的对偶问题。练习写出下列问题的对偶问题。解：对偶问题为：§2.3对偶问题的基本性质在本节中设原问题和对偶问题如下：1、弱对偶性（弱对偶原理）：设和分别是问题P和D的可行解，则必有证明：2、最优性：若X*和Y*分别是P和D的可行解且CX*=bTY*，则X*，Y*分别是问题P和D的最优解。证明：3、无界性若原问题有无界解，则对偶问题无可行解。若对偶问题有无界解，则原问题无可行解。证明：注：逆定理不成立。即“如果原问题无可行解，那么对偶问题有无界解”不成立。此时，对偶问题可能有无界解，也可能无可行解。4、强对偶性（对偶定

7、理）若原问题有最优解，则对偶问题一定有最优解，且zmax=wmin.证：设X*是原问题的最优解，则所有检验数都非正。即=C-CBB-1A0∴CBB-1AC令CBB-1=Y*T，有Y*TAC,转置得ATY*CT-----------------------①又因为S′=-CBB-1=-Y*T0，所以Y*=-（S′）T0------②由①②知Y*是对偶问题的可行解，而CX*=CBb′，其满足:CX*=CB(B-1b)=CBB-1b=Y*Tb=bTY*由最优性(性质2)，∴Y*是对偶问题的最优解。注意：若原问题有最优解，则在最