线性规划 Linear Programming(LP) 第二章 线性规划的对偶理论与 灵敏度分析
1 线性规划 Linear Programming（LP） 第二章 线性规划的对偶理论与 灵敏度分析
线性规划 Linear Programming(LP) 线性规划对偶理论
2 线性规划 Linear Programming（LP） 线性规划对偶理论
线性规划 Linear Programming(LP) 线性规划的对偶理论 对偶理论是线性规划中最重要的理论之一,是深入了解线性规划问题 结构的重要理论基础。同时,由于问题提出本身所具有的经济意义,使得 它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么, 对偶问题是怎样提出的,为什么会产生这样一种问题呢? 且看下面详解 偶问题
3 线性规划 Linear Programming（LP） 线性规划的对偶理论 对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题 结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得 它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么， 对偶问题是怎样提出的，为什么会产生这样一种问题呢？ 且看下面详解……
线性规划 Linear Programming(LP) 线性规划的对偶理论 引例——俩家具制造商间的对话:唉我想租您的木工和油漆工 用。咋样?价格嘛…好说 家具生意还真赚钱,但 肯定不会让您兄弟吃亏讪。 是现在的手机生意这么好, 王老板做家具赚了 不如干脆把我的木工和油漆 大钱,可惜我老李有 工租给他,又能 高科技产品,却苦于没有 收租金又可做生意 足够的木工和油漆工 咋办?只有租咯。 价格嘛…好商量 好商量。只是 Hi:王老板,听说 近来家具生意好惨了, 也帮帮兄弟我哦 王老板 李老板
4 线性规划 Linear Programming（LP） 线性规划的对偶理论 引例——俩家具制造商间的对话：唉!我想租您的木工和油漆工一 用。咋样？价格嘛……好说， 肯定不会让您兄弟吃亏讪。 王老板做家具赚了 大钱，可惜我老李有 高科技产品，却苦于没有 足够的木工和油漆工 咋办？只有租咯。 Hi：王老板，听说 近来家具生意好惨了， 也帮帮兄弟我哦! 家具生意还真赚钱，但 是现在的手机生意这么好， 不如干脆把我的木工和油漆 工租给他，又能 收租金又可做生意。 价格嘛……好商量， 好商量。只是…... 王 老 板 李 老 板
线性规划 Linear Programming(LP) 线性规划的对偶理论 王老板的家具生产模型: 王老板的资源出租模型: x1、x2是桌、椅生产量 y1、y2单位木、漆工出租价格。 z是家具销售总收入(总利润)。W是资源出租租金总收入 maxz=50x,+ 30x2 minW=120y1+50y2 st.(4x1+3X2≤120(木工) s.t.(4y1 2y2 ≥50 2x1+x2≤50(油漆工) 3y+y2230 1,X2≥0 y 15y2 原始线性规划问题,记为(P) 对偶线性规划问题,记为(D)
5 线性规划 Linear Programming（LP） 线性规划的对偶理论 王老板的家具生产模型： x1 、x2是桌、椅生产量。 Z是家具销售总收入（总利润）。 max Z = 50x1 + 30x2 s.t. 4x1+3x2 ≤ 120（木工） 2x1+ x2 ≤ 50 （油漆工） x1，x2 ≥ 0 原始线性规划问题，记为（P） 王老板的资源出租模型： y1、 y2单位木、漆工出租价格。 W是资源出租租金总收入。 min W =120y1 + 50y2 s.t. 4y1+2y2 ≥ 50 3y1+ y2 ≥ 30 y1，y2 ≥ 0 对偶线性规划问题，记为（D）
线性规划 Linear Programming(LP) 线性规划的对偶理论 王老板按(D)的解y1、y2出租其拥有的木、漆工资源,既保证了自 己不吃亏(出租资源的租金收入并不低于自己生产时的销售收入),又使 得出租价格对李老板有极大的吸引力(李老板所付出的总租金W最少)。 按时下最流行的一个词,叫什么来着
6 线性规划 Linear Programming（LP） 线性规划的对偶理论 王老板按（D）的解 y1 、y2出租其拥有的木、漆工资源，既保证了自 己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使 得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。 按时下最流行的一个词，叫什么来着————
线性规划 Linear Programming(LP) 线性规划的对偶理论 例1第一章例1中美佳公司利用该公司资源生产两种家电产品时,其 线性规划问题为—将其称为原始问题,记为P 对应第一个约束条件 →对应第一个约束条件 (P) maxz=2X,+ X2 5X2≤15 对应第一个对偶变量y1 6X1+2X224---对应第二个对偶变量y2 X1+X2≤5 →对应第三个对偶变量y3 X 1
7 线性规划 Linear Programming（LP） 线性规划的对偶理论 例1 第一章例1中美佳公司利用该公司资源生产两种家电产品时，其 线性规划问题为——将其称为原始问题，记为P 对应第一个约束条件 对应第一个约束条件 （P） max Z = 2X1 + X2 5X2 ≤ 15 对应第一个对偶变量 y1 6X1 + 2X2 ≤ 24 对应第二个对偶变量 y2 X1 + X2 ≤ 5 对应第三个对偶变量y3 X1 ， X2 ≥ 0
线性规划 Linear Programming(LP) 线性规划的对偶理论 下面我们从另一角度提出一个新的问题。这个问题我们将其称为原始 问题的对偶问题,记为D (D) minw=15y1+24y2+5y3 6y2+y3 ≥2 5y1+2y2+y3≥1 y1,y2,y320 8
8 线性规划 Linear Programming（LP） 线性规划的对偶理论 下面我们从另一角度提出一个新的问题。这个问题我们将其称为原始 问题的对偶问题，记为D （D） min w = 15y1 + 24y2 + 5y3 6y2 + y3 ≥ 2 5y1 + 2y2 + y3 ≥ 1 y1， y2， y3 ≥ 0
线性规划 Linear Programming(LP) 线性规划的对偶理论 对称形式下对偶问题的一般形式 项目 原问题 对偶问题 A 约束系数矩阵 其约束系数矩阵的转置 约束条件的右端项向量 目标函数中的价格系数向量 目标函数中的价格系数向量约束条件的右端项向量 目标函数maxz=CX min wsyb 约束条件AX≤b AY≥c 决策变量X≥0 Y20 9
9 线性规划 Linear Programming（LP） 线性规划的对偶理论 ▪ 对称形式下对偶问题的一般形式 项目 原问题 对偶问题 A b C 目标函数 约束条件 决策变量 约束系数矩阵 约束条件的右端项向量 目标函数中的价格系数向量 max Z = CX AX ≤ b X ≥ 0 其约束系数矩阵的转置 目标函数中的价格系数向量 约束条件的右端项向量 min W = Y′b A′Y ≥ C′ Y ≥ 0
线性规划 Linear Programming(LP) 线性规划的对偶理论 非对称形式下对偶问题的一般形式一原始()对偶()关系表 项目 原问题(对偶问题)对偶问题(原问题) 目标函数类型 max min 目标函数系数与右边项的对应目标函数各变量系数对应约束条右边项的系数对应目标函数系 关系 件右边项的系数 数 变量个数与约束条件个数的对变量个数n 约束条件个数n 应关系 约束条件个数m 变量个数m 原问题变量类型与对偶问题约 0 束条件类型的对应关系 变量类型 ≤0 约束条件类型 自由 原问题约束条件类型与对偶问 ≤0 题变量类型的对应关系 约束条件类型 变量类型 ≥0 自由 10
10 线性规划 Linear Programming（LP） 线性规划的对偶理论 ▪ 非对称形式下对偶问题的一般形式 —原始（对偶）对偶（原始）关系表 项目 原问题（对偶问题） 对偶问题（原问题） 目标函数类型 max min 目标函数系数与右边项的对应 关系 目标函数各变量系数对应约束条 件右边项的系数 右边项的系数对应目标函数系 数 变量个数与约束条件个数的对 应关系 变量个数 n 约束条件个数 m 约束条件个数 n 变量个数 m 原问题变量类型与对偶问题约 束条件类型的对应关系 ≥0 变量类型 ≤0 自由 ≥ 约束条件类型 ≤ = 原问题约束条件类型与对偶问 题变量类型的对应关系 ≥ 约束条件类型 ≤ = ≤ 0 变量类型 ≥ 0 自由