第三章 对偶理论与灵敏度分析.ppt

第三章对偶理论与灵敏度分析 1单纯形法的矩阵描述 2改进单纯形法 3对偶问题的提出 4线性规划的对偶理论 5对偶问题的经济解释 影子价格 6对偶单纯形法 7灵敏度分析 1单纯形法的矩阵描述 设线性规划问题 设B是一个可行基 令 A I B N I 则 1 检验数的矩阵描述 B CB CBB 1B 0 N CN CBB 1N S CBB 1 min B 1b i B 1Pk i B 1Pk i 0 B 1b l B 1Pk l 3 单纯形表的矩阵描述 C CBB 1A 2 的矩阵描述 2改进单纯形法 用改进单纯形法求解线性规划问题的计算步骤 1 确定初始可行基B1 求出B1 1 2 计算非基变量的检验数 N 若 N 0已求的最优解 停止计算 否则进行下一步 3 确定换入变量xk 4 计算B1 1b B1 1Pk及 若 0那么无最优解 停止计算 否则进行下一步 5 确定换出变量xl 6 计算B2 1 7 重复2 7步 例 用改进单纯形法求解 解 3对偶问题的提出 例 x1 min x2 x1 x2 y1 y2 y3 当该问题达到最优时有 z的上界为无限大 所以只存在最小值 于是得到另一个线性规划问题 对线性规划问题 对偶问题 原问题 4线性规划的对偶理论 4 1原问题与对偶问题的关系 原问题 对偶问题 对偶问题 原问题 例 2 3 5 1 4 2对偶问题的性质1 对称性对偶问题的对偶是原问题 2 弱对偶性若X 是原问题的可行解 Y 是对偶问题的可行解 则存在CX Y b证设原问题及对偶问题为maxz CX AX b X 0min Yb YA CY 0 若X 是原问题的可行解 Y 是对偶问题的可行解 AX bY A C Y AX Y bY AX CX CX Y AX Y b CX Y b 3 无界性若原问题 对偶问题 为无界解 则其对偶问题 原问题 无可行解 4 可行解是最优解的性质设X 是原问题的可行解 Y 是对偶问题的可行解 当CX Y b时 X Y 是最优解 5 对偶定理若原问题有最优解 则对偶问题也有最优解 且目标函数相等 6 互补松驰性若X 是原问题的可行解 Y 是对偶问题的可行解 那么Y Xs 0 YsX 0 当且仅当X Y 为最优解 6 互补松驰性若X 是原问题的可行解 Y 是对偶问题的可行解 那么Y Xs 0 YsX 0 但且仅当X Y 为最优解 证 设原问题及对偶问题的标准型是maxz CX AX XS b X XS 0min Yb YA YS CY YS 0z YA YS X YAX YSX Y AX XS YAX YXS X 是原问题的可行解 Y 是对偶问题的可行解 z Y AX YSX Y AX Y XS当Y Xs 0 YsX 0时z 则X Y 是最优解 当X Y 是最优解时z 则Y Xs 0 YsX 0 例 已知线性规划问题 max 其对偶问题的最优解为 试用对偶理论求原问题的最优解 解 7 设原问题及对偶问题的标准型是maxz CX AX XS b X XS 0min Yb YA YS CY YS 0则原问题单纯形表的检验数行对应其对偶问题的一个基解 对应关系如下表 证 CBB 1A 0 CN CBB 1N CBB 1 B N 0 CN CBB 1N CB CN C 5对偶问题的经济解释 影子价格 设B是线性规划问题的一可行基 这目标函数为 所以变量yi的经济意义是在其他条件不变的情况下 单位资源变化所引起的目标函数值的变化 yi的值代表对第i种资源的估价 这种估价是针对具体工厂的具体产品而存在的一种特殊价格 称它为 影子价格 Q2 4 2 Q1 4 0 Q3 2 3 Q4 0 3 O Q4 Q2 Q3 A增加4 利润增加4 1 8 1 2 设备增加2 利润增加2 3 2 3 Q 5 3 2 Q 4 3 6对偶单纯形法 0 变为 0 变为 0 0 单纯形法 对偶单纯形法 对偶单纯形法的计算步骤 1 确定初始的基 使非基变量的检验数小于等于零 2 若b 0 则已求得最优解 停止计算 否则进行下一步 3 确定换出变量 计算min B 1b i B 1b i 0 B 1b l则xl为换出变量 4 确定换入变量 若所有aij 0 则无可行解 停止计算 否则计算 min j alj alj 0 k alk则xk为换入变量 5 以alk为主元素进行迭代 6 重复2 5步 例 2 3 400 3 1 2 110 4 21 301 10 5 21 21 1 2 21 1 23 20 1 2 2 501 1 5 2 51 5 11 5107 51 5 2 5 0 4 10 1 00 3 5 8 5 1 5 1 34 3 0 8 5 202 7灵敏度分析 灵敏度分析的内容 1 当决定线性规划问题的参数aij bi cj有一个或几个发生变化时 已求得的线性规划问题的最优解会有什么变化 2 当决定线性规划问题的参数aij bi cj在什么范围内变化时 线性规划问题的最优解或最优基不变 7 1资源数量变化的分析设b变化为b b 这时最终单纯形表变为 当B 1 b b 0时 最优基不变 当B 1 b b 中有负分量时 可利用对偶单纯形法求解 例 第一章例1中 若该厂又从别处抽出4台时用于生产 求这时该厂生产的最优方案 解 计算B 1 b 41001 40 2001 1 4 1 2 301001 4 17000 1 2 3 4 3 4 1 40 0 8 2 4 44 例 第一章例1中 资源A在什么范围内变化最优基不变 解 资源A的变化量 b满足下式时最优基不变 7 2目标函数中价值系数cj的变化1 若cj是非基变量xj的系数 则当CN变化 CN后 最终单纯形表的检验数行变为 当CN CN CBB 1N 0时 最优解不变 当CN CN CBB 1N中有正分量时 可利用单纯形法求解 2 若cj是基变量xj的系数 则当CB变化 CB后 最终单纯形表的检验数行变为 当非基变量检验数 0时 最优解不变 当非基变量检验数中有正分量时 可利用单纯形法求解 CB 例 第一章例1中 基变量x2在目标函数中的系数c2在什么范围内变化最优解不变 解 基变量x2在目标函数中的系数c2的变化量 c2满足下式时最优解不变 00 3 2 1 8 0 c2 2 c2 8 c2 2 c2 例 第一章例1中 出售资源A可获利1 2元 这是最优解发生什么变化 解 当 c4 1 2时 单纯形表为 1 2 3 8 168 16 21020 1 2 800 412 30100 1 4 170000 3 4 7 3技术系数aij的变化1 增加一列Pn 1 则最终单纯形表增加一列B 1Pn 1 检验数为 n 1 cn 1 CBB 1Pn 1例 第一章例1中 该厂开发一种新产品 已知生产新产品 每件需消耗原材料A B各为6kg 3kg 使用设备2台时 每件可获利5元 问该厂是否应该生产该产品和生产多少 解 计算 5 4 8 328 1103 2 1 8 3 40 200 11 41 21 3 2013 4 3 16 1 80 16 500 1 4 7 16 5 80 3 221 4 2 改变一列Pj 若Pj变为Pj 则最终单纯形表增加一列B 1Pj 检验数为 j cj CBB 1Pj 删除一列Pj 例 第一章例1中 该厂生产产品 的工艺结构有了改进 已知生产产品 每件需消耗原材料A B各为5kg 2kg 使用设备2台时 每件可获利4元 试分析对原最优计划有什么影响 解 计算 3 8 16 51001 50 12 500 22 51 4 5011 2 1 50 15 200 3 2 1 50 5 41 23 8 4 例 第一章例1中 该厂生产产品 的工艺结构有了改进 已知生产产品 每件需消耗原