运筹学详细教案

河北科技大学教案用纸第页1第1次课2学时注：本页为每次课教案首页上次课复习：本次课题（或教材章节题目）：绪论、第一章线性规划与单纯形法第一节线性规划的基本概念教学要求：掌握运筹学发展历史、主要分支及工作步骤；掌握线性规划一般形式特点及图解法。重点：运筹学的工作步骤、线性规划一般形式、图解法。难点：线性规划一般形式及特点、线性规划图解法。教学手段及教具：多媒体教学。讲授内容及时间分配：一、运筹学简史25分钟二、运筹学的主要分支10分钟三、运筹学的工作步骤10分钟第一章线性规划与单纯形法第一节线性规划的基本概念一、线性规划的数学模型20分钟二、图解法25分钟课后作业P373、（1）、（3）参考资料《运筹学》于春田李法朝主编科学出版社《运筹学教程》胡运权主编清华大学出版社《运筹学》牛映武主编西安交大出版社《运筹学》钱颂迪主编清华大学出版社河北科技大学教案用纸第页2绪论运筹学（operationsresearch）是用数学方法研究各类系统最优化问题的学科。运筹学通过建立系统的数学模型并求解，为决策者制定最优决策提供科学依据。一、运筹学简史二、运筹学的主要分支1.线性规划（LinearProgramming）2.目标规划（GoalProgramming）3.整数规划（IntegerProgramming）4.非线性规划（NonlinearProgramming）5.动态规划（DynamicProgramming）6.图论与网络分析（GraphTheoryandNetworkAnalysis）7.排队论（QueuingTheory）8.存贮论（InventoryTheory）9.对策论（GameTheory）10.决策论（DecisionTheory）三、运筹学的工作步骤1.提出和形成问题2.收集资料，确定参数3.建立模型4.模型求解和检验5.解的控制第一章线性规划与单纯形法第一节线性规划的基本概念一、线性规划的数学模型特点：（1）每个行动方案可用一组变量（x1，…，xn）的值表示，这些变量一般取非负值；（2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；（3）有一个需要优化的目标，它也是变量的线性函数。具备以上三个特点的数学模型称为线性规划（LinearProgramming，简记为LP），一般形式为：0,,),(),(),(max(min)21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz采用求和符号Σ，可以简写为：njxmibxaxczjinjjijnjjj,,2,10,,2,1),(max(min)11河北科技大学教案用纸第页3二、图解法1.唯一最优例40,12420258252max212212121xxxxxxxxxz图1-12.无穷多最优3.无界解（无最优解）123450612345x2x1Q4Q3Q2Q1l1l2l3x1+2x2=85x1+2x2=204x2=12x2=－2/5x1+z/5河北科技大学教案用纸第页4第2次课2学时注：本页为每次课教案首页上次课复习：线性规划一般形式及特点；线性规划图解法。本次课题（或教材章节题目）：第二节线性规划的标准形式和解的性质教学要求：掌握线性规划的标准形式、基可行解的概念及LP解的性质重点：线性规划的标准形式、特点、基可行解的概念及LP解的性质难点：线性规划的标准形式、基可行解的概念。教学手段及教具：多媒体教学。讲授内容及时间分配：上次课复习5分钟一、LP的标准形式30分钟二、LP的基可行解的概念40分钟三、LP解的性质15分钟课后作业P374、（1）、（2）参考资料《运筹学》于春田李法朝主编科学出版社《运筹学教程》胡运权主编清华大学出版社《运筹学》牛映武主编西安交大出版社《运筹学》钱颂迪主编清华大学出版社河北科技大学教案用纸第页5第二节线性规划的标准形式和解的性质一、LP的标准形式njxmibxaxczjinjjijnjjj,,2,10,,2,1max11变换一般LP为标准形式的方法：（1）如果原问题目标函数求极小值：njjjxcz1min令z1=－z，转化为求njjjxcz11)(max。（2）若某个右端常数bi0，则以－1乘该约束两端。（3）若某约束为“≤”型的不等式约束，则在左端加上一个非负变量，称为松弛变量，使不等式化为等式；若某约束为“≥”型，则在左端减去一个非负变量，称为剩余变量，或者仍然称为松弛变量，使不等式转化为等式。（4）若某个xj的符号约束为xj≤0；那么令xj′=－xj，则xj′≥0；若某个xj无符号限制，则可令xj=xj′－xj″，其中xj′≥0，xj″≥0。二、LP的基可行解的概念0bmaxXAXCXz0,,bmax11njnjjxxxPCXz设系数矩阵A的秩是m，即A的m个行向量是线性无关的。若B是A的m阶满秩子阵，称B为问题的一个基。设B=（1jP，2jP，…，mjP），称对应的变量1jx，2jx，…，mjx为基变量，其它的变量称为非基变量。令非基变量等于0，从方程组可以唯一解出基变量的值，从而得到方程组的一个解，称为基本解；如果它的各个分量非负，即它同时又是可行解，则称之为基可行解，对应的基称为可行基。三、LP解的性质1.凸集和极点2.线性规划解的性质定理1线性规划的可行域R是凸集。定理2X是线性规划基可行解的充分必要条件是X是可行域的极点。定理3线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。（1.4）（1.5）（1.6）河北科技大学教案用纸第页6第3次课2学时注：本页为每次课教案首页上次课复习：线性规划的标准形式、特点；基可行解的概念。本次课题（或教材章节题目）：第三节单纯形法教学要求：掌握单纯形法的解题思路、单纯形法要点和单纯形表重点：单纯形表；单纯形法则难点：初始单纯形表；换基迭代法则教学手段及教具：多媒体教学。讲授内容及时间分配：上次课复习及作业10分钟一、单纯形法的解题思路30分钟二、单纯形法要点和单纯形表40分钟P387、（1）10分钟课后作业P387、（2）参考资料《运筹学》于春田李法朝主编科学出版社《运筹学教程》胡运权主编清华大学出版社《运筹学》牛映武主编西安交大出版社《运筹学》钱颂迪主编清华大学出版社河北科技大学教案用纸第页7第三节单纯形法一、单纯形法的解题思路由具体例题突出相关概念。二、单纯形法要点和单纯形表1.检验数的意义和计算公式njjjxcz1max0,,21121221111nmnmjjmjmnmjjjnmjjjxxxbxaxbxaxbxaxmiijijjacc1（1.19）2.单纯形表表1-5cjc1c2…cmcm+1…ck…cnCBXBbx1x2…xmxm+1…xk…xnc1c2…cmx1x2…xmb1b2…bm10…0a1m+1…a1k…a1n01…0a2m+1…a2k…a2n………………00…1amm+1…amk…amnσj00…0miimimacc111…miikikacc1…miininacc13.单纯形法的基本法则法则1最优性判定法则法则2换入变量确定法则设0maxjjjk，则xk为换入变量。法则3换出变量确定法则lklikikiiabaab0min（1.21）再强调一下，这个法则的目的是，保证下一个基本解的可行性，违背这一法则，下一个基本解一定包含负分量，即不是可行解。河北科技大学教案用纸第页8法则4换基迭代运算法则0,,,,12420258252max543215242132121xxxxxxxxxxxxxxxz表1-6cj25000θ比CBXBbx1x2x3x4x5000x3x4x58201215022[4]1000100018/220/212/4σj25000005x3x4x22143[1]50001100010-1/2-1/21/42/114/5—σj2000-5/4205x1x4x22431000011-50010-1/221/4σj00-20-1/4最优解X*=（2，3，0，4，0）T，z*=2×2+5×3=19。河北科技大学教案用纸第页9第4次课2学时注：本页为每次课教案首页上次课复习：单纯形表；单纯形法则；讲解作业3、（3）与4、（1）存在问题。本次课题（或教材章节题目）：第三节单纯形法三、关于单纯形法的补充说明教学要求：掌握无穷多最优解与唯一最优解的判别法则、无最优解（无界解）的判定法则；掌握求minz的情况。重点：单纯形判别法则难点：单纯形判别法则及证明；求minz的情况。教学手段及教具：多媒体教学。讲授内容及时间分配：上次课复习及作业20分钟1.无穷多最优解与唯一最优解的判别法则20分钟2.无最优解（无界解）的判定20分钟3.求minz的情况15分钟P387、（3）15分钟课后作业P387、（4）参考资料《运筹学》于春田李法朝主编科学出版社《运筹学教程》胡运权主编清华大学出版社《运筹学》牛映武主编西安交大出版社《运筹学》钱颂迪主编清华大学出版社河北科技大学教案用纸第页10三、关于单纯形法的补充说明1.无穷多最优解与唯一最优解的判别法则若对某可行解X1，（1）所有检验数σj≤0，且有一个非基变量xk的检验数等于0，则问题有无穷多最优解；（2）所有非基变量的检验数σj0，则问题有唯一最优解。例13讨论线性规划0,,,0212max43214214314321xxxxxxxxxxxxxxz的最优解的类型。解约束方程组已经是关于x3，x2的解出形式，直接列表求解：表1-8cj112-1CBXBbx1x2x3x421x3x210[1]-10110-12σj000-111x1x211100111-11σj000-12.无最优解（无界解）的判定若对基可行解X1，存在非基变量xk的检验数σk0，但aik≤0，i=1，2，…，m即xk的系数列向量无正分量，则问题无最优解。3.求minz的情况例14求例2中的LP0,,,,82010104020322min54321531421321xxxxxxxxxxxxxxz的最优解。表1-9cj22300CBXBbx1x2x3x4x523x2x31/42/5[1/2]1/21001-1/4000-1/20σj-1/2001/203/2023x1x31/23/20102-101-1/201/400-1/20σj0101/403/20（1.22）（1.23）河北科技大学教案用纸第页11第5次课2学时注：本页为每次课教案首页上次课复习：单纯形判别法则求minz所对应的情况。本次课题（或教材章节题目）：第四节初始可行基的求法——人工变量法教学要求：掌握大M法、两阶段法重点：大M法、两阶段法；各目标函数及价值系数难点：大M法中价值系数的符号；两阶段法的迭代方法教学手段及教具：多媒体教学。讲授内容及时间分配：一、大M法30分钟二、两阶段法30分钟三、关于退化解的说明10分钟P391120分钟课后作业P388、（1）（3）参考资料《运筹学》于春田李法朝主编科学出版社《运筹学教程》胡运权主编清华大学出版社《运筹学》牛映武主编西安交大出版社《运筹学》钱颂迪主编清华大学出版社河北科技大学教案用纸第页12第四节初始可行基的求法——人工变量法一、大M法例15求下列LP问题的最优解0,,123241123max32131321321321xxxxxxxxxxxxxxz解0