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