2.1线性规划的对偶问题(经典运筹学)ppt课件

第2章线性规划的对偶理论及其应用,线性规划最重要的理论之一进行经济分析的重要工具,1,2.1线性规划的对偶问题,一、对偶问题的提出二、原问题与对偶问题的对应关系三、原问题与对偶问题的数学模型,2,一、对偶问题的提出,3,例1：大众家电厂家利用现有资源生产两种产品，有关数据如下表：,设产量产量,问如何安排生产，使获利最多？,4,例2.1*有一个企业家接到一批加工定单，需用到设备A,B,C,有意租用大众家电厂的三种设备，问该企业家应如何出价，才能使家电厂觉得有利可图肯把设备出租，又使自己付出的租金最少？,企业家,付出的代价最小,出让代价应不低于用同等数量的资源自己生产的利润。,对方能接受,厂家,5,厂家能接受的条件：收购方的意愿：,出让代价应不低于用同等数量的资源自己生产的利润。,设：设备Ay1元时,设备By2元时,设备Cy3元时,6,对偶问题,原问题,企业家,厂家,一对对偶问题,7,例2.2假定一个成年人每天需要从食物中获取3000kcal的热量、55g蛋白质和800mg的钙。如果市场上只有四种食品可供选择，问如何选择才能在满足营养的前提下使购买食品的费用最小？,8,例2.2*有一个厂商生产三种可代替食品中热量、蛋白质、钙的营养素，问该厂商应如何制定每种营养素单位营养量的价格，使其获得最大的收益？,9,消费者：,经营者：,原问题,对偶问题,一对对偶问题,10,3个约束2个变量,2个约束3个变量,一般规律,二、原问题与对偶问题的对应关系,11,对偶问题：,原问题：,3个约束,4个变量,4个约束,3个变量,12,三、原问题与对偶问题的数学模型,1、对称型对偶问题,2、标准型对偶问题,3、混合型对偶问题,13,定义：设原线性规划问题为：,则称下列线性规划问题：,bi无正负限制,1、对称型对偶问题,为其对偶规划，,（P）,（D）,一对对偶问题,互为对偶,14,所求对偶问题为：,15,所求对偶问题为：,16,对称型对偶问题的矩阵形式：,17,2、标准型对偶问题,设原问题（P）为标准型：,化为对称型,18,所求对偶问题为：,19,所求对偶问题为：,所求对偶问题为：,20,所求对偶问题为：,与对称型对偶问题比较：,规则：,若原问题（P）的约束方程为“=”约束,则对偶原问题（D）的变量无符号限制,21,因此若原问题（P）为标准型：,则对偶问题（D）为：,22,3、混合型对偶问题,化为对称型,23,化为对称型,24,25,对偶规划问题（D）为,26,对偶规划问题（D）为,对偶规划问题（D）为：,27,对偶规划问题（D）为：,原问题（P）,对偶问题（D）,变量约束：,方程约束：,变量,方程,变量无限制,方程=,变量,方程,方程约束：,变量约束：,方程=,变量无限制,方程,变量,方程,变量,结构与对称型相似,28,（P）与(D)的关系对应表：,目标函数max,目标函数min,目标函数系数,约束方程常数列,约束方程常数列,目标函数系数,变量个数n,约束方程个数n,约束方程个数m,变量个数m,约束方程,变量0,0,=,无符号约束,变量0,约束方程,0,无符号约束,=,系数矩阵A,=-3,29,（P）与(D)的关系对应表：,目标函数max,目标函数min,目标函数系数,约束方程常数列,约束方程常数列,目标函数系数,变量个数n,约束方程个数n,约束方程个数m,变量个数m,约束方程,变量0,0,=,无符号约束,变量0,约束方程,0,无符号约束,=,系数矩阵A,=-3,30,练习：,（P）与(D)的关系对应表：,目标函数max,目标函数min,目标函数系数,约束方程常数列,约束方程常数列,目标函