运筹学第2章对偶规划(硕士)

《运筹学第2章对偶规划(硕士)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、管理运筹学汪贤裕2009.08第2章线性规划的对偶理论及应用2.1线性规划的对偶问题2.1.1对偶规划问题的提出2单位产品用料桌子椅子可用资源木工4小时3小时120油漆工2小时1小时50单位产品利润50元/个30元/个例1.1生产计划问题求下列数据下家俱厂生产计划，使利润最大。解：设生产桌子x1个，生产椅子x2个线性规划模型为：maxz=50x1＋30x2s.t.4x1＋3x21202x1＋x250x10,x20.3例2.1（续）设有另一个企业，缺少木工和油漆工，它向家俱厂提出租用木工和油漆工。问该企业提出什么样的租用

2、价格。解：设它提出的木工和油漆工的租用工时价分别为y1和y2.Minw=120y1＋50y2s.t.4y1＋2y2≥503y1＋y2≥30y1≥0,y2≥0.4序号食品名称热量（kcal）蛋白质（g）钙（mg）价格（元)1猪肉100050400142鸡蛋8006020063大米9002030034白菜200105002营养需求300055800例1.2营养配餐问题要求配餐中至少应有热量3000kcal,蛋白质55g，钙300mg。问应怎样配餐成本最低？5解：设每天购入猪肉x1千克、鸡蛋x2千克、大米x3千克、白菜x4千克。（决

3、策变量）则配餐问题的线性规划模型如下：Minz=14x1＋6x2＋3x3＋2x4（目标函数)s.t.1000x1＋800x2＋900x3＋200x4300050x1＋60x2＋20x3＋10x455400x1＋200x2＋300x3＋500x4800xi0i=1,2,3,4.（s.t.后全是约束条件）6例2.2（续）现有一个企业生产人造营养品：热量、蛋白质、钙，并卖给营养配方管理者。它应对生产的人造营养品定价，以获取更多的收入。解：设它对三种人造营养品定价分别为y1、y2、y3。有线性规划模型：Maxw=3000y1＋

4、55y2＋800y3s.t.1000y1＋50y2＋400y3≤14800y1＋60y2＋200y3≤6900y1＋20y2＋300y3≤3200y1＋10y2＋500y3≤2y1≥0,y2≥0,y3≥0.72.1.2.线性规划对偶问题的定义对称形式：互为对偶(LP)Maxz=cTx(DP)Minf=bTys.t.Ax≤bs.t.ATy≥cx≥0y≥0“Max--≤”“Min--≥”8对称形式的对偶规划(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“

5、max，≤”和“min，≥”相对应。(2)从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、c的位置看：在两个规划模型中，b和c的位置对换。(4)两个规划模型中的变量皆非负。9非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。（1）将模型统一为“max，≤”或“min，≥”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某

6、个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。10下面对关系（2）作一说明。对于关系（3）可以给出类似的解释。设原规划中第一个约束为等式：a11x1+…+a1nxn=b1等价这样，原规划模型可以写成11此时已转化为对称形式，直接写出对偶规划这里，把y1看作是y1=y1’-y1’’，于是y1没有非负限制，关系（2）的说明完毕。关系（3）则是这一过程的逆过程。12例2.3写出下面线性规划的对偶规划模型解:先将约束条件

7、变形为“≤”形式13再根据非对称形式的对应关系，直接写出对偶规划142.2线性规划的对偶理论定理2.1（对称性定理）对偶问题的对偶是原问题。定理2.2（弱对偶定理）设x，y分别是（LP）和（DP）的可行解，则cxyb定理2.3（对偶定理）若x*和y*分别是(LP)和(DP)的可行解，则x*和y*分别为(LP)和(DP)的最优解的充分必要条件是：cx*=y*b。152.3对偶解的经济解释对偶解和影子价格若x*,y*分别为（LP）和（DP）的最优解，那么，cTx*=bTy*。根据z*=cTx*=bTy*=b1y1*+b2y2*+

8、+bmym*可知z*/bi=yi*yi*表示bi变化1个单位对目标z产生的影响，称yi*为bi的影子价格。影子价格是对系统内部资源的一种客观评价。它是一种虚拟的价格，而不是真实的价格。16影子价格的几个特点:（1）影子价格是对现有资源实现最大效益时的一种最优估价。（2）