对偶理论2.ppt

运筹学课件 对偶理论 对偶问题对偶理论对偶单纯形算法 对偶问题的提出 例 设某企业有m种资源 用于生产n种不同的产品 各种资源的拥有量为bi i 1 2 m 又知生产单位第j种产品 j 1 2 n 消费第i种资源aij单位 产值为cj元 若用xj表示第j种产品的生产量 求产值最大 LP模型为 任意线性规划问题都存在一个与之伴随的对偶问题 现从另一角度提出问题 假设此企业拥有资源但未生产 而另一企业预将上述企业拥有的资源买过来 至少应付出多少代价 才能使前一企业愿意放弃生产活动 出让资源 若设yi表示收买该企业一单位i种资源时付出的代价 则另一线性规划问题为 收买的企业付出的代价是该商品的价格吗 若不是 它和原本的价格是什么关系 收购资源的企业能赚钱吗 怎么赚 原问题与对偶问题对应关系 实例 对偶问题的基本性质 以下各性质基于如下假设 原问题 对偶问题 若 是原问题的可行解 是其对偶问题的可行解 则恒有 证明 性质1 弱对偶性 若 是原问题的可行解 是其对偶问题的可行解 且有 则 是原问题的最优解 是其对偶问题的最优解 性质2 最优性 性质2证明 又因为 则 性质3 无界性 若原问题 对偶问题 有无界解 则其对偶问题 原问题 无可行解 性质4 强对偶性 对偶定理 若原问题有最优解 则其对偶问题也一定有最优解 且maxz minw 在线性规划问题的最优解中 若对应某一约束条件的对偶变量值为非零 则该约束条件取严格等式 反之若约束条件取严格不等式 则其对应的对偶变量一定为零 即 另外说法 分别是原问题和对偶问题的 可行解 则 为最优解的充分必要条件是 性质5 互补松弛性 性质5证明 化原问题和对偶问题为标准形式 原问题 对偶问题 若 则 则 为最优解 为最优解 则 所以 设原问题和对偶问题为 原问题 对偶问题 性质6 变量对应关系 则 原问题单纯形表的检验数行对应其对偶问题的一个基解 对应关系见表 性质6证明 设B是原问题的一个可行基 所以 相应的对偶问题为 若求得原问题的以解 检验数为 和 令 将它代入 得 对偶问题性质的趣味应用 最优单纯形表 影子价格随具体情况而异 在完全市场经济条件下 当某种资源的市场价格低于影子价格时 企业应该买进该资源用于扩大生产 当某种资源的市场价格高于影子价格时 企业应该把该资源卖掉 所以 影子价格具有市场调节作用 对偶单纯形算法 基本思想算法过程算例 原问题 对偶问题 基本思想 单纯形算法 对偶单纯形 算例 例 用对偶单纯形法求解 解 将问题化为下式 以得到对偶问题的初始可行基 否 算法框图 初始正则解 是则停止 得最优解 选出基变量 检查是否无可行解 是则停止 否 无最优解 选入基变量 计算检验数 灵敏度分析 灵敏度分析研究的问题 单纯行表中基的位置 为清楚起见 把新单纯行表中的基对应的初始单纯行表中的那些向量抽出来单独列一块 记为B 初始单纯行表为 单纯行法的迭代过程实际上是对约束方程的系数矩阵实施行的初等变换 由线代知道 对矩阵 实施行的初等变换时 当B变为I时 I将变为 则 上述矩阵将变为 新单纯行表写为 灵敏度分析的步骤 1 将参数的改变计算反应到最终单纯形表上 具体方法是 按下列公式计算由参数 的变化而引起的最终单纯形表上有关数字的变化 2 检查原问题是否仍为可行解 3 检查对偶问题是否仍为可行解 4 按下表所列情况得出结论和决定继续计算的步骤 将cj的改变反应到最终单纯形表上 只能出现上页表中所示的前两种情形 例 已知LP问题 用单纯形法求解得最终单纯形表如下 表1 试确定 a 当目标函数变为 最优解会如何变化 b 当目标函数变为 求 的变化范围 使最优解不变 a 将cj的改变反应到最终单纯形表 1 上 得表 2 表2 表 2 中变量x5的检验数为正 继续迭代得表 3 表3 即新解为 b 将cj的改变反应到最终单纯形表 1 上 得表 4 表4 二 分析bi变化的影响 bi的变化在实际问题中表明可用资源的数量发生变化 将bi的改变反应到最终单纯形表上 只引起基变量列数字变化 所以灵敏度分析的步骤为 1 按公式 算出 将其加到基变量列的数字上 2 因为其对偶问题仍为可行解 故只需检查原问题是否为可行解 例 上例中 a 当第二个约束条件的右端项增大到32 最优解会如何变化 b 当第二个约束条件变为 求 的变化范围 使表中基为最优基 解 a 将其加到表 1 的最终单纯形表的基变量b这一列数字上得表 5 表5 表 5 中原问题为非可行解 故用对偶单纯形法继续计算得表 6 表6 即新解为 解 b 将其加到表 1 的最终单纯形表的基变量b这一列数字上得表 7 表7 表中基为最优基的条件为 所以有 三 增加一个变量的分析 增加一个变量在实际问题中表明增加一种新产品 灵敏度分析的步骤为 1 计算 2 计算 3 若 只需将 和 的值直接反映到最终 单纯形表中 原最优解不变 若 则按单纯形表继续迭代计算 例 在前例中 若增加一个变量x6 有 试分析最优解的变化 解 将其反映到表 1 的最终单纯形表中 得表 8 表8 所以 用单纯形法继续计算 得表 9 表9 即新解为 四 分析aij变化的影响 假如xj在最终表中为基变量 则aij的变化将使最终表中的B 1变化 因此 有可能出现原问题与对偶问题均为非可行解的情况 例 在前例中 若x2系数向量p2变为 试分析最优解的变化 解 先将其作为一个新的变量x2 列入最终单纯形表中 得表 10 表10 因x2已变化为x 2 故用单纯形法算法将x 2替换出基变量中的x2 并在下一个表中不再保留x2 得表 11 表11 因表 11 中原问题与其对偶问题均为非可行解 所以通过引入人工变量 将原问题转化为可行解 再用单纯形法继续计算 表 11 的第一行可写成 因为 右端项为负值 故先将等式两端乘 1 再加上人工变量x6 得 将上式替换表 11 的第一行 得表 12 表12 用单纯形法迭代 得表 13 表13 即新解为 五 增加一个约束条件的分析 增加一个约束条件 在实际问题中相当于增添一道工序 分析的方法是先将原问题的最优解变量取值代入这个新增的约束条件中 如满足 说明新增约束未起到限制作用 原最优解不变 否则 将新增约束直接反映到最终单纯形表中 再进行分析 例 前例中增添一个约束条件 试分析最优解变化 解 先将原问题最优解变量值代入 因为有 故 将约束条件写成 并取x6 为基变量 直接反映到最终单纯形表中 得表 14 表14 迭代 得表 15 表15 为使x1 x2列系数变换为单位向量 对表 14 进行行的变换 表 15 中1 2 3行同表 14 中1 2 3行不变 表 15 中第4行由初等行变换 4行 3 2行 2 3行 得到 用对偶单纯形法计算 得表 16 表16 即新解为 参数线性规划 灵敏度分析研究 1 当模型中参数aij bi cj改变到某一数值时对最优解的影响 2 这些参数在什么范围内变化时最优解不变 参数线性规划研究 当这些参数超出这个范围时 最优解将怎么变化 例 前例中 第三个约束条件的右端项不断增大时 分析最优解将怎么变化 解 令 则问题等价于 参数线性规划求解步骤 1 令 求解 得最终单纯形表 表0 表0 2 将参数的变化反映到最终单纯形表中 表1 反映到最终单纯形表得 表1 3 让 值逐渐增大 观察原问题与对偶问题的变化 看哪一个首先出现非可行解 本例中当 时 基变量 时 基变量 将取负值 所以表 1 中解为最优解的条件为 当 时