土 木 工 程 与 建 筑 学 院 教 师 备 课 纸 《线性规划的对偶理论与对偶单纯形法》（2课时）

【教学流程图】

举例引入

对偶问题与原问题的结构特点 线性规划的对偶问题的基本概念 对偶问题与原问题的解与单纯形表

线性规划的单纯形法求解实质

初始表 对偶单纯形法计算步骤 进基

出基

学生练习（结合例题讲解进行）

课堂小结

布置作业

【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生 的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果。

【教学内容】

一 、教学过程：

（三）举例引入对偶问题的基本概念：（5分钟）

第37页 ------------------------------------------------------------------------------------------------------------------------------------------------------

土 木 工 程 与 建 筑 学 院 教 师 备 课 纸

导入提问：线性规划的对偶问题与原问题的解是什么关系？ （二） 新课：

第四节 对偶单纯形法

一、对偶单纯形法的原理

LP与DP在求解迭代过程中有三种情形： LP的b列 LP的检验数?j 均≥0 均 ≤0 含义 则DP的检验数?i≤0且yi?0，这时 LP与DP均达到最优解。 均≥0 某个?j＞0 则DP的某个变量yj＜0，说明原问题可 行，对偶问题不可行。 某个bi＜0 全部?j≤0 则DP的检验数?i≤0且yi?0，说明原 问题不可行，对偶问题可行。 对于第二种情形用单纯形法求解，第三种情形用对偶单纯形法求解。 二、 对偶单纯形法求解过程 1、用实例引入： 例1-10

minW?3y1?9y2y1?y2?2 y1?4y2?3y1?7y2?3y1,y2?0

解 引入非负松弛变量y3?5?0，化为标准型；

第38页

------------------------------------------------------------------------------------------------------------------------------------------------------

土 木 工 程 与 建 筑 学 院 教 师 备 课 纸

maxZ??3y1?9y2y1?y2?y3?2y1?4y2?y4?3y1?7y2?y5?3y1?5?0

将三个约束式两边分别乘以-1，得

maxZ??3y1?9y2?y1?y2?y3??2 ?y1?4y2?y4??3

?y1?7y2?y5??3y1?5?0目标函数 决策变量 基变量 初 始 表 计 算 ←y3 y4 y5 Zj Cj -3 -9 0 0 0 y1↓ y2↓ y3 y4 y5 常数 yj 0 0 0 [-1] -1 1 0 0 -2 -1 -4 0 1 0 -3 -1 -7 0 0 1 -3 0 0 0 0 0 -3 -9 0 0 0 ?j ??min(?3/?1,?9/?1)?3 -3/-1 -9/-1 第一 y1 -3 0 0 1 1 -1 0 0 2 0 [-3] -1 1 0 -1 0 -6 -1 0 1 -1 次迭 ←y4 代 y5 Zj -3 -3 3 0 0 0 -6 -3 0 0 ?j 第39页

------------------------------------------------------------------------------------------------------------------------------------------------------

土 木 工 程 与 建 筑 学 院 教 师 备 课 纸

??min(?6/?3,?3/?1)?2 -6/-3 -3/-1 第二 次迭 代 y1 y2 y5 Zj -3 -9 0 1 0 -4/3 1/3 0 5/3 0 1 1/3 -1/3 0 1/3 0 0 1 -2 1 1 -3 -9 1 2 0 0 0 -1 -2 0 ?j 最优解为：Y=(5/3,1/3,0,0,1)

3、 总结对偶单纯形法求解过程：

由于用单纯形法求解极大化线性规划问题时，通过迭代直至所有检验数

?j≤0，这时所得最优基也是对偶问题的可行基，因此单纯形法的求解过程

是：在保持原始可行（即常数列保持≥0）的前提下，通过迭代实现对偶可行（全部?j≤0）。

换一个角度考虑线性规划的求解过程：能否在保持对偶可行（全部?j≤0）的前提下，通过迭代实现原始可行（即常数列保持≥0）？这就是对偶单纯形法的求解思路。

第一步：建立初始单纯形表，计算检验数行，当全部?j≤0（非基变量的?j＜0）时，如果常数项≥0，即得最优解。如常数项至少有一元素＜0，且检验数仍然非正，则转下一步。

第二步：将常数项＜0所在的约束条件两边同乘以-1，将常数列全变成非负，再使用原始单纯形法求解。如果上述处理过程中出现原始可行基不再是单位矩阵，可适当增加人工变量构造人造基，再用大M法求解。

第三步：进行基变换

第40页 ------------------------------------------------------------------------------------------------------------------------------------------------------