6/26/2025第3章线性规划的对偶理论1
目录6/26/20253.1线性规划的对偶问题3.2对偶理论3.3对偶理论的应用3.4对偶单纯形法3.5灵敏度分析CONTENTS2
3.1线性规划的对偶问题
在第2章的例1.1中，我们讨论了如下的生产计划模型：假定现有一公司想把该工厂的生产资源收购过来，那么它至少应付出多大的代价，才能使该工厂愿意放弃生产活动，出让自己的资源？现在从另一个角度来讨论这个问题：6/26/20253.1.1对偶问题的提出例1.1生产计划问题问产品A,B各生产多少,可获最大利润?AB备用资源钢材（吨）1230劳动力（工时）3260特种设备（台时）0224利润（元/件）40504
设用y1,y2,y3分别表示钢材、劳动力和特种设备这三种资源的单位定价。因为用1个单位的钢材和3个单位的劳动力可以生产一件产品A，从而获得40元利润。那么生产每件产品A的资源出让所得应不低于生产一件产品A的利润，即y1+3y2≥40同理，将可以生产每件产品B的资源出让的所得应不低于生产一件产品B的利润，即2y1+2y2+2y3≥506/26/20253.1.1对偶问题的提出5
要把所有的资源都收购需付出：W=30y1+60y2+24y3当然收购公司希望用最小的代价把工厂的全部资源收买过来，故有：minW=30y1+60y2+24y3s.t.y1+3y2≥402y1+2y2+2y3≥50y1,y2,y3≥0对偶问题(DUAL)6/26/20253.1.1对偶问题的提出6
问最经济的配食方案是什么？维生素的销售商换个角度?例1.2混合配料问题饲料ABC每单位成本饲料14102饲料26125饲料31716饲料42538每天维生素12148的最低需求维生素/mg3.1.1对偶问题的提出6/26/20257
“对称型”对偶问题minw=bTyATy?cy?0A矩阵y,b列向量c列向量maxz=cTxAx?bx?0A矩阵x,b列向量c列向量原问题6/26/20253.1.2线性规划原问题与对偶问题的表达形式8
6/26/2025原始问题maxz=cTxs.t.Ax≤b x≥0对偶问题minw=bTys.t.ATy≥cy≥0≤maxbAcTmncATbT≥minmn3.1.2线性规划原问题与对偶问题的表达形式9
minz’=-cTxs.t.-Ax≥-b x≥0maxw=-bTys.t.-ATy≤-c y≥0minw=bTys.t.ATy≥cy≥0maxz=cTxs.t.Ax≤b x≥0对偶的定义对偶的定义对偶问题的对偶就是原始问题！6/26/20253.1.2线性规划原问题与对偶问题的表达形式10
“非对称型”3.1.2线性规划原问题与对偶问题的表达形式
3.1.2线性规划原问题与对偶问题的表达形式012
对偶关系对应表 （P） （D） 目标函数maxmin目标系数Cb约束右端bC系数矩阵AAT函数约束与变量约束第k个约束?第k个变量约束个数=变量个数（非）规范约束?非负（正）变量等式约束?自由变量6/26/2