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

1、第2章 线性规划的 对偶理论及其应用线性规划最重要的理论之一进行经济分析的重要工具2.1 线性规划的对偶问题一、对偶问题的提出一、对偶问题的提出二、原问题与对偶问题的对应关系二、原问题与对偶问题的对应关系三、原问题与对偶问题的数学模型三、原问题与对偶问题的数学模型一、对偶问题的提出一、对偶问题的提出例例1：大众家电厂家利用现有资源生产两种：大众家电厂家利用现有资源生产两种 产品，产品，有关数据如下表：有关数据如下表：设备设备A 设备设备B 设备设备C 利润（百元）利润（百元）0612521115时时24时时 5时时产品产品产品产品D设设 产量产量 产量产量问如何安排生产，使获利最多？问如何安排

2、生产，使获利最多？例2.1*有一个企业家接到一批加工定单，需用到 设备 A,B,C,有意租用大众家电厂的三种设备，问该企业 家应如何出价，才能使家电厂觉得有利可图肯把设 备出租，又使自己付出的租金最少？企企业业家家 付出的代价最小付出的代价最小出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。对方能接受对方能接受厂厂家家 设备设备A 设备设备B设备设备C利润（百元）利润（百元）0612521115时时24时时 5时时D厂家能接受的条件：厂家能接受的条件：收购方的意愿：收购方的意愿：出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己

3、生产的利润。自己生产的利润。设：设备设：设备A yA y1 1元时元时,设备设备B B y2元时元时,设备设备Cyy3 3元时元时对对偶偶问问题题原原问问题题企企业业家家厂厂家家一对对偶问题一对对偶问题例2.2 假定一个成年人每天需要从食物中获取3000kcal的热量、55g蛋白质和800mg的钙。如果市场上只有四种食品可供选择，问如何选择才能在满足营养的前提下使购买食品的费用最小？食品热量kcal蛋白质g钙mg价格元猪肉10005040014鸡蛋 800602006大米900203003白菜200105002每天需求300055800例2.2*有一个厂商生产三种可代替食品中热量、蛋白质、钙的

4、营养素，问该厂商应如何制定每种营养素单位营养量的价格，使其获得最大的收益？食品热量kcal蛋白质g钙mg价格元猪肉10005040014鸡蛋 800602006大米900203003白菜200105002每天需求300055800消费者：经营者：原问题对偶问题一对对偶问题一对对偶问题3 3个约束个约束2 2个变量个变量2 2个约束个约束 3 3个变量个变量原问题原问题对偶问题对偶问题一般规律二、原问题与对偶问题的对应关系二、原问题与对偶问题的对应关系对偶问题：原问题：3个个约约束束4个个变变量量4个个约约束束3个个变变量量三、原问题与对偶问题的数学模型三、原问题与对偶问题的数学模型1、对称型对

5、偶问题2、标准型对偶问题3、混合型对偶问题 定义：设原线性规划问题为：则称下列线性规划问题：bi无正负限制1、对称型对偶问题为其对偶规划，（P）（D）一对对偶问题一对对偶问题互为对偶所求对偶问题为：所求对偶问题为：对称型对偶问题的矩阵形式：2、标准型对偶问题设原问题（P）为标准型：化为对称型所求对偶问题为：所求对偶问题为：所求对偶问题为：所求对偶问题为：与对称型对偶问题比较：规则：若原问题（P）的约束方程为“=”约束则对偶原问题（D）的变量无符号限制因此若原问题（P）为标准型：则对偶问题（D）为：3、混合型对偶问题化为对称型化为对称型对偶规划问题（D）为对偶规划问题（D）为对偶规划问题（D）为

6、：对偶规划问题（D）为：原问题（P）对偶问题（D）变量约束：方程约束：变量方程变量无限制方程=变量方程方程约束：变量约束：方程=变量无限制方程变量方程变量结构与对称型相似（P）与(D)的关系对应表：原问题 对偶问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列 目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程变量00=无符号约束变量0约束方程0无符号约束=系数矩阵A=-3（P）与(D)的关系对应表：原问题 对偶问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列 目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程变量00=无符号约束变量0约束方程0无符号约束=系数矩阵A=-3练习：（P）与(D)的关系对应表：原问题 对偶问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列 目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程变量00=无符号约束变量0约束方程0无符号约束=系数矩阵A