《运筹学Ⅰ》教案
课程名称：运筹学 授课教师：孔造杰 课程学时：64
开课时间：第三学年第一学期
授课方式：课堂教学为主，实验教学为辅
2011年1月
时间安排：周学时4，共16周，总学时64，
授课方式：课堂教学与实验教学结合，以课堂教学为。初步安排课堂教学52学时左右，实验教学8-10学时，实验课以上机为主，辅以习题课。
时 间：第一周第一次 授课方式：课堂教学 教学内容：
一、绪论
1． 运筹学的起源与发展：?起源于二次大战的一门边缘交叉学科?由于战争的需要而
产生与发展；战后在经济、管理和机关学校及科研单位继续研究；我国于1982
年加入IFORS，并于1999年8月组织了第15届大会。
2． 运筹学的特点及研究对象：运筹学是一门边缘性的、综合性的应用科学。它是以应
用数学为主要技术手段，综合应用经济、军事、心理学、社会学、物理学、化学以及工农业生产的一些理论和方法，对实际问题找出最优的或满意的解决方案的一门科学。
3． 运筹学解决问题的方法步骤：?明确问题?建立模型?设计算法?整理数据?求解模型?
评价结果?实施控制 4． 运筹学的主要内容
5． 运筹学的主要应用领域
二、第一章：线性规划基础——§1-1问题的提出，§1-2LP模型与解的概念
1． 问题的提出：从两个生产与经济问题的实例出发，引导学生认识实际问题同数学模
型之间的联系，认识规划模型同一般的数学方程、数学函数之间的区别，认识用数学方法解决实际问题的基本思维模式和方法途径。
2． 线性规划的一般数学模型：掌握线性规划的构成形式及要素：决策变量、约束条件、
目标函数。 线性规划的一般模型为：
目标函数：max(min)z?c1x1?c2x2???cnxn 约束条件：s.t.
a11x1?a12x2???a1nxn?(?,?)b1 a21x1?a22x2???a2nxn?(?,?)b2
? ? ?
am1x1?am2x2???amnxn?(?,?)bm
x1,x2,?,xn?0
3．线性规划解的概念：可行解——满足所有约束条件包括非负条件的解；最优解——使目标函数①达到最大值的可行解；基；基本解——非零分量的数目不大于方程
数m，则称X为基本解；基本可行解——满足非负条件的基本解；可行基——对应于基本可行解的基。
时 间：第一周第二次 授课方式：课堂教学 教学内容：
一、线性规划图解法（§1-3）
1. 用图解的方法解上一节提出的线性规划模型。通过图解，使学生较直观地看到线性
规划模型的求解过程及其意义，掌握图解法的基本方法和技巧，清楚地认识到线性规划有解的条件和最优解可能存在的位置。
2. 通过图解法直观地认识线性规划解的集中特殊情况：当目标方程直线与某一约束直
线平行时，最优值不唯一；有可行域，但无最优解，即目标函数的值z???无
可行解；当约束条件出现相互矛盾时，则没有可行域。
二、线性规划的求解基础（§1-4）
1. 线性规划的标准式：
maxz?c1x1?c2x2???cnxn
s.t. a11x1?a12x2???a1nxn?b1
a21x1?a22x2???a2nxn?b2
? ?
am1x1?am2x2???amnxn?bm x1,x2,?xn?0
2. 化一般模型为标准模型：分成三种情况：若问题的目标函数为最小化minZ?CX；
若约束条件为不等式；若某一决策变量xk无非负约束。 3. 从解线性方程组引申到解线性规划模型
4. 线性规划求解理论：凸集、 凸组合、顶点、三个定理
时 间：第二周第一次 授课方式：课堂教学 教学内容：
线性规划的应用§1-5
分成人力资源问题、生产计划问题、套裁下料问题、配料生产问题、投资问题等若干方面进行实例分析，主要引导学生学习怎样从实际问题列出其规划模型。
时 间：第二周第二次 授课方式：课堂教学 教学内容：
一、单纯形法及其计算步骤（§2-1）
1. 单纯形表的形式及其构成：在单纯形表中不仅反映增广系数矩阵，而且反映检验数?、?规则判定值，以及目标函数的取值。 2. 计算步骤：
1) 找出初始可行基，建立初始单纯形表，确定初始基本可行解。
2) 检查对应于非基变量的检验数?j ，若所有的?j?0,(j?m?1~n)，则当前解为
最优解，停止迭代；否则转入下一步。
3) 在所有?j?0的列中，若有一个?k所对应变量xk的系数列向量中的各分量均小于
''T,?,amk)?0，则此问题无最优解，停止迭代；否则转下等于零，即pk?(a1'k,a2k一步。
?j?0)??k，确定xk为进基变量；根据?规则?l?min(4) 根据max(ibi│aikaik?0)?bl，确定xl为出基变量。于是得到迭代主元素alk，转入下一步。 alk5) 以alk为主元素进行迭代运算（高斯消元法迭代），即把alk变为1，而把同列的其它
元素变为零，得到新的基本可行解所对应的新的单纯形表。转入2。
三、人工变量的处理（§2-2） 大M求解法
在“≥”、“=”约束中，为了构造单纯形表的初始基，一般就需要加入人工变量。人工变量是实际问题模型中没有的人为的虚拟变量，所以这些变量在最终解中不能为基变量，而必须是非基变量（以确保其等于零），为确保这一点，就需采取一定的措施，大M法就是措施之一。
为确保人工变量从基中退出，以不影响目标函数的取值，在目标函数中给每一个人工变量设定一个很大的负系数?M（M为任意大的正数），这样，只要人工变量没有退出基，目标函数就不可能取到最大值。此即所谓大M法。 两阶段法
第一阶段：判断原问题是否有解。为此，需要建立一个辅助线性规划，并求解。辅助问题是这样的：目标函数取成所有的人工变量之和，并取其极小化；约束条件为加入人工变量后的原约束。
第二阶段：求原问题的最优解。对于上述第一种情况，在当前基中不含有人工变量，将目标函数变为原问题的目标函数，在单纯形表中将价值系数行换为原问题的价值系数。划去人工变量所在的列即得到原问题的初始单纯形表。然后重新求检验数，继续迭代，直到求得原问题的最优解。