运筹学电子教案（1）
- 1. *非常荣幸第二次来到仪征化纤 股份公司上课谨祝同志们： 身体健康 万事如意
- 2. *欢迎同学们进入运筹学课程的学习！教学相长 合作愉快
- 3. *情况介绍 本课程设置的有关问题 教学要求
- 4. *第一讲 绪 论本讲的主要内容： 一、运筹学的发展与展望 二、运筹学的学科体系 三、运筹学的定义与研究特点 四、运筹学在管理科学中的地位 五、运筹学在经济管理中应用的主要课题
- 5. *一、运筹学的发展及展望1、运筹学的产生与发展 科学意义上的运筹学公认为产生于第二次世界大战期间。以英国为代表的科学家做了奠基性的工作。 四十年代之后，运筹学取得全面的发展。表现在：1）数学理论得到加强，2）分支学科大量涌现，3）应用领域不断拓宽等。
- 6. *一、运筹学的发展与展望2、运筹学的展望 1）运筹学发展过程中面临的一些问题：抽象化风气日盛、大范围问题、高维问题、体系厐杂等。 2）运筹学发展展望 运筹学应该在三个方面都应有所发展：运筹学的学科体系、运筹学的应用及运筹学的数学理论。
- 7. *二、运筹学的学科体系运筹学发展到今天已经形成了一个庞大的学科体系： 1、Mathematical programming : Linear programming ,Nonlinear programming , Integer programming ,Objective programming , Dynamic programming ,Stochastic programming,Geometric programming等。
- 8. *二、运筹学的学科体系2、Graph theory 3、Network analysis 4、Queueing theory 5、Game theory 6、Decision theory 7、Quality control 8、Reliability theory
- 9. *二、运筹学的学科体系9、Storage theory 10、Search theory 11、Maintenance theory 12、Computer simulation 13、Scheduling method 14、Value theory 15、Renewal theory 16、Control theory 17、Military operations research等。
- 10. *三、运筹学的定义与研究特点 1、运筹学认识上的一些分歧 1）学科的归属问题：数学学科、边缘学科、管理科学。 2）方法特征：优化技术、决策方法、一般的数量分析方法。 3）与相关学科的关系：控制论、系统论、技术经济方法、管理科学等。 4）研究的侧重点方面：理论方法、侧重于应用等。
- 11. *三、运筹学的定义与研究特点 2、运筹学的定义 美国人的定义：运筹学是研究用科学的方法来解决在资源不充分的情况下如何最好地设计人-机系统，并使之最好地运行的一门学科。 英国人的定义：运筹学是运用科学方法（特别是数学方法）来解决那些在工业、商业等大型系统的指挥和管理方面出现的问题，目的是帮助管理者科学地决定其策略和行动。
- 12. *三、运筹学的定义与研究特点3、运筹学研究问题的特征： 1）科学性 2）实践性 3）系统性 4）综合性
- 13. *四、运筹学在管理科学中的地位管理科学的学科构架 1、基础理论部分 1）管理理论：企业理论、决策理论、运筹学、组织理论、行为理论、企业经营学、生产管理与运作理论、人-机工程等。 2）管理发展史：管理思想史、管理方法史、管理科学发展史、比较管理学等。 3）交叉知识：数学、系统论、哲学、经济学、人类学、心理学、社会学、计算机科学、思维科学等。
- 14. *四、运筹学在管理科学中的地位管理科学的学科构架 1、基础理论部分 4）管理学派：经营学派、决策学派、“管理科学”学派、经验学派、经理角色学派、群体行为学派、合作社会系统学派、权变学派等。
- 15. *四、运筹学在管理科学中的地位管理科学的学科构架 2、技术方法部分： 决策方法、决策支持系统、计划与规划技术、库存控制、技术经济、预测技术、管理信息系统、管理系统工程、目标管理、质量管理与保证、管理数学方法、项目评估和可行性研究、价值工程、预算与成本控制、时间-动作研究等。
- 16. *四、运筹学在管理科学中的地位3、应用研究部分 1）宏观管理领域：国民经济管理、社会发展管理、管理体制研究等。 2）部门管理领域：行政管理、人事管理、工业管理、农业管理、财政管理等。 3）企业管理领域：设备管理、物资管理、质量管理、财务管理、人力资源管理、生产管理、计划管理、市场营销管理、技术开发管理等。 4）专项管理活动：环境管理、能源利用与开发等。
- 17. *五、运筹学在经济管理中应用的主要课题 1、市场营销：广告预算、竞争性定价、新产品开发、销售方案等。 2、生产计划：生产作业计划、配料、物料管理等。 3、库存管理：合适的库存水平、进货方案等。 4、运输管理：运输方式的组合、运输计划等。
- 18. *五、运筹学在经济管理中运用的主要课题 5、财务管理：预算、筹资、成本分析等。 6、人事管理：人员需求、人力资源开发、人员的合理利用、人才评价、工资标准等。 7、设备维修与更新 8、可靠性分析 9、质量控制 10、项目评估 11、城市公用事业和服务
- 19. *参考书目 1、管理科学(Management Science )（当代最有代表性的杂志之一） 2、管理科学基础（美国希利尔等人编写的，中国财政经济出版社） 3、管理科学事务教程（加拿大敖特斯编写的，华夏出版社）
- 20. *第二讲 线性规划与单纯形方法本讲的主要内容： 一、线性规划模型及标准化 二、二维线性规划的图解法 三、线性规划的基本理论 四、单纯形方法 五、DSS、LINDO软件介绍
- 21. * 第一节 情况介绍一、线性规划的地位与研究进程 作为一门科学的线性规划，最早可以追溯到20世纪30年代末，前苏联数学家康德洛维奇等人关于生产组织和运输问题研究所作的开拓性工作。1947年，美国数学家G.B.Dantzig以及美国空军的SCOOP研究小组提出了线性规划问题的一般性解法即单纯形法,奠定了线性规划的理论基础。50年代后，随着电子计算机的介入，线性规划的应用越来越普遍，在生产、管理、军事等方面发挥着重要的作用。 线性规划目前仍然还在发展，主要是：大型线性规划问题，线性规划解法研究等。
- 22. *二、线性规划研究的内容1、在现有的资源条件下，如何充分利用资源，使任务或目标完成得最好（求极大化问题）。 2、在给定目标下，如何以最少的资源消耗，实现这个目标（求极小化问题）。
- 23. *第二节 线性规划模型一、线性规划模型的一般形式 根据实际问题的要求，可建立线性规划问题数学模型。线性规划问题的数学模型，由目标函数和约束条件两部分组成。下面我们举例说明线性规划问题的数学模型。 例一：生产计划问题 某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：
- 24. *例一、生产计划问题 试用线性规划方法制订使利润最大的生产计划。 产品甲产品乙产品丁产品 丙设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18
- 25. *例一的数学模型解：设变量xi为第i种产品的生产件数（i＝1，2，3，4），目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型： Max z=5.24x1+7.30x2+8.34x3+4.18x4 s.t. 1.5x1+1.0x2+2.4x3+1.0x4≤2000 1.0x1+5.0x2+1.0x3+3.5x4≤8000 1.0x1+3.0x2+3.5x3+1.0x4≤5000 x1，x2，x3，x4≥ 0
- 26. *例二：配料问题 某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），这四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：
- 27. *例二：配料问题 T1T2 T3 T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30115978276
- 28. *例二：配料问题假设熔炼时重量没有损耗，要熔炼成100千克不锈钢G，应选用各种原料各多少才能使成本达到最小。 解：设选用原料T1，T2，T3和T4分别为x1，x2，x3，x4千克，根据条件，可建立相应的线性规划模型如下：
- 29. *例二的数学模型 Min Z=115x1+97x2+82x3+76x4 s.t. 0.0321x1+0.0453x2+0.0219x3+0.0176x4≥3.20 0.0204x1+0.0112x2+0.0357x3+0.0433x4≥2.10 0.0204x1+0.0112x2+0.0357x3+0.0433x4≥4.30 x1 + x2 + x3 + x4=100 x1 , x2 , x3 , x4≥0
- 30. *线性规划模型的一般形式：通过上面的例子，可以写出线性规划模型的一般形式： Max(Min) z=c1x1+c2x2+……+cnxn s.t. a11x1+a12x2+……+a1nxn≥(=、≤)b1 a21x1+a22x2+……+a2nxn≥(=、≤)b2 …… am1x1+am2x2+……+amnxn≥(=、≤)bm x1,x2, ……,xn ≥(≤) 0，或者没有限制
- 31. *二、线性规划的标准化方法1、标准化形式 Max z=c1x1+c2x2+……+cnxn s.t. a11x1+a12x2+……+a1nxn=b1 a21x1+a22x2+……+a2nxn=b2 …… am1x1+am2x2+……+amnxn=bm x1,x2, ……,xn ≥ 0
- 32. *2、线性规划的标准化方法2、标准化方法 （1）把最小化目标函数转化为求最大化问题。 （2）把约束方程中的不等式转化为等式。具体做法是：对于不大于情况的，引进松弛变量，对于不小于情况的，引进剩余变量。 （3）将变量中的非正限制或无限制转化为非负限制。其中，对于无限制变量的处理：一是同时引进两个非负变量，然后用它们的差代替无限制变量，二是从约束方程中任取一个包含无限制变量的等式约束，解出该变量，并把它代如目标函数和其他约束方程中去，以消除该无限制变量。
- 33. *三、定理定理：线性规划模型的一般形式与它的标准形是等价的。 根据这一定理，由标准形求出的最优解，也一定是原问题的最优解。
- 34. *四、线性规划的向量和矩阵表示1、用“∑” 表示 2、用向量表示 3、用向量和矩阵表示
- 35. *第二节 二维线性规划的图解法一、图解法的含义 在直角坐标系中，描绘出约束条件和变量限制的公共区域，然后通过观察确定符合目标要求的变量的取值。 二、图解法举例 教材第9页例1.1
- 36. *二、图解法举例作图
- 37. *三、几个概念1、法向量 正法向量和负法向量。由目标函数系数组成的与等值线垂直的向量，称为正法向量。正法向量的反号称为负法向量。 2、等值线 使目标函数取相等值的所有点的集合，称为目标函数的等值线。
- 38. *三、几个概念3、可行解 由约束条件和变量取值限制围成的公共区域中的每一个点都称为线性规划问题的可行解。 4、可行域 所有可行解的集合，构成线性规划问题的可行域。
- 39. *四、二维线性规划解的形式1、唯一解 2、无穷多个最优解 Min –x1-2x2 s.t. -x1 + x2≤2 x1+2x2≤10 3x1+x2≤15 x1,x2≥0
- 40. *四、二维线性规划解的形式3、有可行解但无最优解 Min –x1-2x2 s.t. -x1 + x2≤2 -x1+2x2≤6 x1 , x2≥0 4、无可行解也即问题无解 Min x1+2x2 s.t. x1+x2≤1 2x1+x2≥4 x1,x2≥0
- 41. *二维线性规划问题解的小节 无可行解 线性规划问题 唯一最优解 有可行解 无穷最优解 无最优解
- 42. *第四节 线性规划的基本理论一、线性规划解的概念 1、解：满足线性规划主约束条件的点，称为线性规划问题的解。 2、可行解：满足线性规划所有约束条件的点，称为线性规划问题的可行解。 3、最优解：使目标函数得到极值的可行解，称为线性规划问题的最优解。最优解包括：唯一最优解和无穷最优解，有界最优解和无界最优解。
- 43. *二、基、标准基与基变量1、基：约束系数矩阵A中，m个线性无关的列向量，称为m维实空间中的一个基。其中，每个列向量称为基向量，全部基向量构成基矩阵（也可简称为基），剩下的n-m个列向量称为非基向量，所有的非基向量构成非基矩阵。 2、标准基：单位阵的基矩阵，成为标准基。 3、基变量：与基向量对应的变量称为基变量。同理，与非基向量对应的变量称为非基变量。
- 44. *三、基本解、基本可行解与可行基1、基本解 假设约束系数矩阵A中的前m个列向量A1、A2、…Am线性无关，令B=（A1，A2，…，Am ）， N=（Am+1，Am+2，…，An），XB=（x1，x2，…，xm），XN=(xm+1xm+2…xn)，于是：A=（B，N）， X=（ XB ， XN ），则由AX=b 得： （B，N）（ XB ， XN ）-1= b ，解出XB： XB =B-1 b - B-1 B-1N XN ，令 XN =0，称X =（ B-1 b ，0）为对 应基B的基本解。
- 45. *三、基本解、基本可行解与可行基 2、基本可行解：符合非负性要求的基本解，称为基本可行解。 3、可行基：基本可行解对应的基，称为可行基。
- 46. *四、基本最优解与最优基 1、基本最优解：满足目标函数要求的基本解，称为基本最优解。 2、最优基：基本最优解对应的基，称为最优基。
- 47. *线性规划解之间的关系线性规划解之间的关系： 可行解基本解非可行解基本可行解基本可行解最优解
- 48. *五、退化基本可行解与退化基 1、退化基本可行解：基本可行解中存在取零值的基变量，则称该基本可行解为退化的基本可行解。 2、退化基：退化的基本可行解对应的基，称为退化基。
- 49. *六、线性规划的几何意义1、凸集：集合C∈En，从C中任取两点X、Y，当0<λ<1时，仍有λX+（1-λ）Y∈C，则称C为凸集。 凸集：
- 50. *六、线性规划的几何意义1、凸集： 不是凸集：
- 51. *六、线性规划的几何意义2、凸组合 设X1，X2，…，Xk是n维欧氏空间中的 k个点 ， 若存在非负数λ1,λ2,…,λk, 且λ1+λ2+…+λk=1，使得X=λ1X1+λ2X2+…+λKXK成立，则称X是X1，X2，…，Xk的凸组合。如果0＜λ1,λ2,…,λk＜1，则称X是X1，X2，…，Xk的严格凸组合。
- 52. *六、线性规划的几何意义3、极点 假设C是凸集，若C中不存在两个不同的点X1、X2 ，使得C中的点X可以表示为X1、X2凸组合，则称X是C中的极点。
- 53. *七、线性规划的基本定理1、线性规划问题所有可行解组成的集合S= {X|AX=b,X≥0}是凸集。 2、线性规划问题的可行解X是基本可行解的充要条件是X的正分量对应的约束系数矩阵的列向量是线性无关的。 3、X是线性规划问题的基本可行解的充要条件是X为可行域S = {X|AX=b,X≥0} 的极点。
- 54. *七、线性规划的基本定理4、如果一个线性规划问题存在可行解，则一定有基本可行解。 5、若线性规划问题存在最优解，则一定存在最优基本可行解。 6、若线性规划问题可行域有界，则最优解一定在极点上取得到。 7、线性规划可行域的极点的个数是有限的。
- 55. *# 线性规划理论的小结1、一般意义上说： （1）如果线性规划问题有可行解，则一定有基本可行解。 （2）线性规划问题如果有最优解，则最优解一定可以从基本可行解中找得到。 （3）由于基本可行解的个数有限，所以经过有限次迭代，就一定能找到最优解。
- 56. *# 线性规划理论的小结2、从几何意义上说： （1）线性规划问题可行域中的每一个极点都对应着一个基本可行解。 （2）由于最优解必定要从基本可行解中寻找，所以所谓求解线性规划问题，实际上就是比较极点处的目标函数值的大小。 （3）极点的个数是有限的，那么只要经过有限次寻找就一定能够找到基本最优解。
该用户的其他文档
相关PPT