运筹学教案

《运筹学Ⅰ》教案课程名称：运筹学授课教师：孔造杰课程学时：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．线性规划的一般数学模型：掌握线性规划的构成形式及要素：决策变量、约束条件、目标函数。线性规划的一般模型为：目标函数：nnxcxcxcz2211max(min)约束条件：s.t.11212111),(bxaxaxann22222121),(bxaxaxannmnmnmmbxaxaxa),(22110,,,21nxxx3．线性规划解的概念：可行解——满足所有约束条件包括非负条件的解；最优解——使目标函数①达到最大值的可行解；基；基本解——非零分量的数目不大于方程数m，则称X为基本解；基本可行解——满足非负条件的基本解；可行基——对应于基本可行解的基。时间：第一周第二次授课方式：课堂教学教学内容：一、线性规划图解法（§1-3）1.用图解的方法解上一节提出的线性规划模型。通过图解，使学生较直观地看到线性规划模型的求解过程及其意义，掌握图解法的基本方法和技巧，清楚地认识到线性规划有解的条件和最优解可能存在的位置。2.通过图解法直观地认识线性规划解的集中特殊情况：当目标方程直线与某一约束直线平行时，最优值不唯一；有可行域，但无最优解，即目标函数的值z无可行解；当约束条件出现相互矛盾时，则没有可行域。二、线性规划的求解基础（§1-4）1.线性规划的标准式：nnxcxcxcz2211maxs.t.11212111bxaxaxann22222121bxaxaxannmnmnmmbxaxaxa22110,,21nxxx2.化一般模型为标准模型：分成三种情况：若问题的目标函数为最小化CXZmin；若约束条件为不等式；若某一决策变量kx无非负约束。3.从解线性方程组引申到解线性规划模型4.线性规划求解理论：凸集、凸组合、顶点、三个定理时间：第二周第一次授课方式：课堂教学教学内容：线性规划的应用§1-5分成人力资源问题、生产计划问题、套裁下料问题、配料生产问题、投资问题等若干方面进行实例分析，主要引导学生学习怎样从实际问题列出其规划模型。时间：第二周第二次授课方式：课堂教学教学内容：一、单纯形法及其计算步骤（§2-1）1.单纯形表的形式及其构成：在单纯形表中不仅反映增广系数矩阵，而且反映检验数、规则判定值，以及目标函数的取值。2.计算步骤：1)找出初始可行基，建立初始单纯形表，确定初始基本可行解。2)检查对应于非基变量的检验数j，若所有的)~1(,0nmjj，则当前解为最优解，停止迭代；否则转入下一步。3)在所有0j的列中，若有一个k所对应变量kx的系数列向量中的各分量均小于等于零，即0),,,(''2'1Tmkkkkaaap，则此问题无最优解，停止迭代；否则转下一步。4)根据kj)0max(，确定kx为进基变量；根据规则ikiilab(min│lklikaba)0，确定lx为出基变量。于是得到迭代主元素lka，转入下一步。5)以lka为主元素进行迭代运算（高斯消元法迭代），即把lka变为1，而把同列的其它元素变为零，得到新的基本可行解所对应的新的单纯形表。转入2。时间：第三周第一次授课方式：课堂教学教学内容：改进单纯形法（§2-3）1.单纯形表的矩阵描述基变量BX非基变量1NXSXI11NB1BbB1011NBCCBN1BCBbBCB12.对于小型的线性规划模型用单纯形法，手工求解还是比较方便的，但我们也发现每次迭代都需计算很多无关的数字，对于大型的线性规划模型，不但手工解比较困难，就是借助计算机也会占用更多的空间和时间。为适应计算机计算的需要，提出一种改进的办法。LP的计算机求解§2-4介绍用Excel求解线性规划的方法、步骤和注意事项案例分析§2-5检验数行对应于松弛变量的矩阵为基矩阵的逆阵时间：第六周第二次授课方式：课堂教学/答疑教学内容：一、运输问题提出与建模（§5-1）运输是社会经济生活中必不可少的一个环节，也是我们身边司空见惯的现象，例如，煤炭、粮食、木材等物资在全国各地的调运；企业生产所需原材料及产成品的运进运出；商业部门对销售网点的货物配送等等。若用ijx表示从产地iA运往销地jB的运输量，那么在产销平衡条件下，要求总运费最省的运输方案可表示为：miijnjijxcMinZ11满足条件：injijax1（i=1，…,m）jmiijbx1（j=1，…,n）0ijx解运输问题通常采用表上作业法，这一过程通常分为三个阶段：（1）给出初始可行方案；（2）判断是否最优方案；（3）调整方案。二、基变量与闭回路（§5-2）讲解求解运输问题模型的理论基础：基本量的个数，构成基变量应该满足的条件等。二、初始解的确定方法1最小元素法：最小元素法的基本思想就是就近供应。即从单位运价表中最小运价开始确定产销关系，依次类推，一直到给出初始方案为止。2伏格尔法（Vogel）伏格尔法（Vogel）是对最小元素法的改进，但相对要复杂些。（具体略）Vogel法是对最小元素法的改进，由Vogel法得到的初始方案一般更接近于最优方案。需注意的是用Vogel法所求得初始方案的过程中也可能遇到最小元素法所遇到的问题，以可以用同样的方法去解决。时间：第七周第一次授课方式：课堂教学教学内容：运输问题的单纯形方法：（§5-3）一初始方案的给出1最小元素法：最小元素法的基本思想就是就近供应。即从单位运价表中最小运价开始确定产销关系，依次类推，一直到给出初始方案为止。2伏格尔法（Vogel）伏格尔法（Vogel）是对最小元素法的改进，但相对要复杂些。（具体略）Vogel法是对最小元素法的改进，由Vogel法得到的初始方案一般更接近于最优方案。需注意的是用Vogel法所求得初始方案的过程中也可能遇到最小元素法所遇到的问题，以可以用同样的方法去解决。二、运输问题解的最优性判定1.闭回路法：在给出的初始方案计算表上，除了m+n-1个有数字格外，还有m×n-（m+n-1）个空格。从每一空格出发，沿水平或垂直方向前进，当遇到有数字格时可以任意转90度继续前进，也可以串过有数字格继续前进，直到回到起始点。这样总可以找到一个且只有一个闭回路。在这个闭回路中，除了起始点为空格外，其余角点都是有数字点。如果检验数为正，表明沿此闭回路的调整会使总费用增加；如果检验数为负，表明沿此闭回路的调整会使总费用减少。如果求得所有空格点的检验数都大于等于零，则当前运输方案为最优方案；如果还有空格的检验数小于零，则还要进一步调整当前运输方案。2.位势法：用闭回路法求检验数，思路很清晰简单，但当产销点较多时是十分麻烦的，而位势法是比较简单易行的。（1）在表5-13的右端增加一列，记为ui,i=1~m。在下面增加一行，记为vj，j=1~n。使其满足cij=ui+vj。（2）求出所有的空格的位势ui+vj，并将其填入表5-15中。（任一格的位势等于其行位势加列位势）（3）在表5-13的右端增加一列，记为ui,i=1~m。在下面增加一行，记为vj，j=1~n。使其满足cij=ui+vj。（4）由单位运价表中的每一数据cij减去位势表中对应格的位势，得到每个变量的检验数（如本例的表5-16所示）（注：对应基变量的检验数必为0，可以不写）。（5）判定：若所有检验数均大于等于零，则当前解为最优解；若有一个或一个以上的格为负数，则当前解为非最优解，还需进一步调整改进。三、案的调整：无论是用最小元素法还是用Vogel法给出的初始方案，也不论是用闭回路法还是用位势法进行最优性判定。当解为非最优解时，也就是存在负的检验数时，都要用闭回路法进行调整。运输问题的变体（§5-4）前面三节所述运输问题的理论与表上作业法的计算，都是以产销平衡为前提的。即各产地的总产出等于各销地的总销量。即：njjmiiba11但在实际的运输问题中，其产销往往是不平衡的，为了应用上述理论和表上作业法进行计算，就需要一定的技术措施，把产销不平衡的运输问题化为产销平衡的运输问题来处理。1.产大于销2.销大于产运输问题的应用§5-5时间：第七周第二次授课方式：课堂教学教学内容：一、整数规划的模型与特点（§6-1）在前面我们所讨论的线性规划模型中，一般情况下都限定决策变量X≥0。但在实际问题中往往会有其它限制，如决策变量只能取整数，只能取0、1两个值等等。若对原线性规划问题增加这种限制，则称之为整数规划问题。所以整数规划也是一种特殊的线性规划。整数规划有很现实的实际意义，因为在很多线性规划问题中，决策变量往往代表的是人数、机器台数等等，这时非整数解显然是不合要求的。整数规划有很现实的实际意义，因为在很多线性规划问题中，决策变量往往代表的是人数、机器台数等等，这时非整数解显然是不合要求的。对于处理这一类要求有整数解的线性规划问题，通常人们首先想到的是先不管整数条件的限制，直接使用单纯形法求解，然后将所得到的非整数解经四舍五入化为整数。但是这种办法往往是行不通的，这是因为由舍入化整所得的整数解不一定是可行解，即便是可行解，也不一定是最优解。目前，解整数规划问题通常采用的方法是分支定界法和割平面法。二、分枝定界法（§6-2）1.分枝定界法是以求相应的线性规划问题的最优解为出发点的。如果得到的线性规划问题的最优解不符合整数条件，就将原问题分解成两个或几个子问题，而每一子问题都是在原线性规划问题的基础上增加相应的整数约束条件，从而在其可行域的边界附近除去一部分原来的可行域，但所除去的可行域是不包含有整数解的。这样，可以使靠近可行域边界的整数点逐步地暴露在新可行域的边界上，在分解后的缩小了的可行域内继续求相应的线性规划问题，直到得到所要求的最优整数解。2.解体步骤：1．称原问题（整数规划）为A，称相应的线性规划（即不考虑整数条件）为B，解B。2．如果问题B没有可行解，则问题A也没有可行解。3．如果已得问题B的最优解，检查它是否合于整数条件。若是，则它就是原问题A的最优解；若否转入下步。4．在问题B的解中，任选一个不符合整数条件的变量jx，如果jx的值是bj，作两个后继问题，它们是对问题B分别各增加一个约束条件：a)jx（小于bj的最大整数）b)jx（大于bj的最小整数）不考虑整数条件，解这两个后继问题。5．在现有的、且还没有分解后继问题的各可行解中，选目标函数值为最优的问题，重新称这个问题为问题B，回到第3步。重复进行，直到得到整数最优解。时间：第八周第一次授课方式：课堂教学教学内容：割平面法（§6-3）一．解法思想：首先不考虑整数条件，解线性规划问题，若得整数解即为所求