时 间：第三周第一次 授课方式：课堂教学 教学内容：
改进单纯形法（§2-3）
1. 单纯形表的矩阵描述 基变量 XB 检验数行 非基变量 XN1 BN1 ?1对应于松弛变量的 矩阵XS ?1I 0 B?1Bb?1 CN?CBBN1 ?1?CBB CBBb?1
2. 对于小型的线性规划模型用单纯形法，手工求解还是比较方便的，但我们也发现每次迭代都需计算很多无关的数字，对于大型的线性规划模型，不但手工解比较困难，就是借助计算机也会占用更多的空间和时间。为适应计算机计算的需要，提出一种改进的办法。
LP的计算机求解§2-4
介绍用Excel求解线性规划的方法、步骤和注意事项
案例分析§2-5
时 间：第三周第二次 授课方式：课堂教学 教学内容：
一、对偶问题的提出（§3-1）
1. 从经济意义上提出对偶问题：针对第一章中例1的实际生产问题从另一个角度提出，
并进行具体分析、建模； 2. 从数学模型上提出对偶问题：根据线性规划的矩阵描述和单纯形表的矩阵描述，从
数学上定义一个新的模型，这个模型同原模型不仅有同样的解值，而且有着一一晖映
的对应关系。
二、写对偶问题（§3-2）
1. 为便于叙述和记忆对偶问题，通常规定一个标准形式，一般规定原规划为“≤”约
束，对偶规划为“≥”约束，变量均≥0的对偶问题为标准形式。把它们之间的关系
用表格形式表示出来，可以写成表3-2的形式
xj yi 原关系 x1 x2 ┅ xn minw y1 y2 ┇ a11 a12 ┅ a1n a21 a22 ┅ a2n ┇ ┇ ┇ ≤ ≤ ┇ ≤ b1 b2 ┇ ym 对偶关系 am1 am2 ┅ amn ≥ ≥ ┅ ≥ bm maxz?minw maxz c1 c2 ┅ cn 2. 原问题模型于对偶模型之间的对应关系 原问题（或对偶问题） 目标函数maxz 资源条件（约束右端常数项） 价值系数（目标函数系数） 变 量 约束条件
n个变量 ≥0 ≤0 无约束 m个约束 ≤ ≥ ＝ 对偶问题（或原问题） 目标函数minw 价值系数（目标函数系数） 资源条件（约束右端常数项） 约束条件 变 量 n个约束 ≥ ≤ ＝ m个变量 ≥0 ≤0 无约束 时 间：第四周第一次 授课方式：课堂教学 教学内容：
一、对偶问题的性质：
1. 对称性：对偶问题的对偶是原问题。
2. 弱对偶性：若X是原问题的可行解，Y是对偶问题的可行解，则存在CX?Yb
??Y?b时，?是对偶问题的可行解，当CX?是原问题的可行解，Y3. 等值最优性：设X?,Y?分别是原问题和对偶问题的最优解。 X4. 对偶定理：若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。
?,Y?分别是原问题和对偶问题的可行解，X,Y分5. 互补松弛定理（松紧定理）：若Xss?为最优解时，有?与Y别是原问题和对偶问题的松弛变量，那么，当且仅当X??0和X?Y?0 。 XsYs6. 原问题的检验数对应对偶问题的一个解。
为了使学生掌握这些定理和性质，对上述性质进行必要的证明于说明，使学生能够真正理解其原理。
二、影子价格
影子价格是对偶规划问题的经济解释。
在单纯形法的的每一步迭代中，目标函数取值z=CBB－1b，和检验数CN－CBB－1N中都有乘子Y=CBB－1，
变量yi*的经济意义是在其他条件不便的情况下，单位资源变化所引起的目标函数的最优值的变化。
所以，yi*代表对第I种资源的价格估计，这种估计是针对具体工厂的具体产品而存在的一种特殊价格，称其为影子价格。
时 间：第四周第二次 授课方式：课堂教学 教学内容：
对偶单纯形法（§3-4）
对偶单纯形法并非将原问题写成对偶问题，再用单纯形表求解，而是利用对偶问题的性质求解线性规划模型，它提供了单纯形表的另一种用法。
在单纯形表中，b列对应于原问题的一个基本可行解，而检验数行则对应其对偶问题的一个基本解。在前面我们进行单纯形表的迭代中，始终保持原问题为基本可行解（即b列大于等于零），而对偶问题为基本非可行解（即检验数行含有正值），一旦检验数行有基本非可行解变为基本可行解，则原问题和对偶问题同时达到最优解。
根据对偶问题的对称性，单纯形表的迭代过程也可以反过来进行，即保持对偶问题始终是基本可行解（即保持??C?CBB?1A?0），而使原问题从基本非可行解逐步迭代到基本可行解，从而使原问题和对偶问题同时得到最优解。这种单纯形表的应用方法称为对偶单纯形法。
对偶单纯形法的解题步骤，用流程图表述如图3-1。
x以alk为主元素进行单纯形表迭代 所有?j?0? N 单纯形法迭代求解 问题无解停止 Y 所有a?0? ljN Y 列出初始单纯形表 引入人工变量 重列单纯形表 Y 所有b?0? iN 得最优解停止 所有?j?0? Y 确定出基变量 N minBbi|Bbi?0?Bbi???1???1????1?lx确定进基变量 ?cj?zj?c?zk??min?|alj?0??kjalk?alj?图3-1：对偶单纯形法流程图
时 间：第五周第一次 授课方式：课堂教学 教学内容：
习题课
系统总结第一章至第三章线性规划的所有内容，讲解重点习题的正确解法和思路，留出20分钟进行课堂答疑。