运筹学教案 张媛
运筹学教案 张媛
第一章绪论 §1运筹学释义与发展简史 一、书中释义 中国大百科全书：运筹学“用数学方法研究经济、民政和国防等部门在内外环境的约束条 件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测 发展趋势，制定行动规划和优选可行方案。” 管理百科全书 “运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、 财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 命名由来 Operational Research (Operations Research ( OR运用研究作业研究操作研究 运筹：运用筹划，策略取胜，反映这门学科的性质和内涵。 ”运学简史 1.名词正式使用 1938年，英国。空袭的早期预警，为解决来自不同雷达站的信息以及雷达站同整个防空 作战系统的协调配合问题，用“Operational Research"”一词作为这方面研究的描述。 2成立运第学小组 1940-英国，1942-美国、加拿大 3.第二次世界大战后，研究扩展到工业和政府部门。 (1)1945-50年代初，运筹学的创建期。 运筹学研究人数不多，范围小，出版物、学会宴塞无几。 (2)50年代初.50年代末，成长期。 电子计算机技术的迅速发展，运筹学中一些方法用于解决实际管理系统中的优化问题 促进运筹学的推广应用。 (3)60年代以来，运筹学开始普及和迅速发展的时期。 运筹学进一步的细分为各个分支，专业团体增多：期刊、书籍增多：运筹学课程纳入教 学计划之中。 4运筹学在中国的发展 1956年 -成立第一个运筹学小组 1958年 成立运筹学研究室 1962、1978一分别于北京、成都召开全国运筹学专业学术会议。 1980年4月—成立中国运筹学学会。 §2运筹学研究的基本特征与基本方法 一、基本特征 1.系统的整体观念 2.多学科的综合
第一章 绪论 §1 运筹学释义与发展简史 一、书中释义 中国大百科全书：运筹学“用数学方法研究经济、民政和国防等部门在内外环境的约束条 件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测 发展趋势，制定行动规划和优选可行方案。” 管理百科全书：“运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、 财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。” 命名由来 Operational Research（英） Operations Research（美） O.R.运用研究 作业研究 操作研究 运筹：运用筹划，策略取胜，反映这门学科的性质和内涵。 二、运筹学简史 1.名词正式使用 1938 年，英国。空袭的早期预警，为解决来自不同雷达站的信息以及雷达站同整个防空 作战系统的协调配合问题，用“Operational Research”一词作为这方面研究的描述。 2.成立运筹学小组 1940-英国，1942-美国、加拿大 3.第二次世界大战后，研究扩展到工业和政府部门。 （1）1945-50 年代初，运筹学的创建期。 运筹学研究人数不多，范围小，出版物、学会寥寥无几。 （2）50 年代初-50 年代末，成长期。 电子计算机技术的迅速发展，运筹学中一些方法用于解决实际管理系统中的优化问题， 促进运筹学的推广应用。 （3）60 年代以来，运筹学开始普及和迅速发展的时期。 运筹学进一步的细分为各个分支，专业团体增多；期刊、书籍增多；运筹学课程纳入教 学计划之中。 4.运筹学在中国的发展 1956 年——成立第一个运筹学小组 1958 年——成立运筹学研究室 1962、1978——分别于北京、成都召开全国运筹学专业学术会议。 1980 年 4 月——成立中国运筹学学会。 §2 运筹学研究的基本特征与基本方法 一、基本特征 1.系统的整体观念 2.多学科的综合
3.模型方法 二、基本方法（步骤） 1分析和表述问题 2.建立模型 3求解模型和优化方案 4.测试模型及对模型进行必要的修正 5.建立对解的有效控制 6.方案的实施 §3运筹学的主要分支 线性规划(linear programming-LP) 非线性规划(nonlinear programming-NLP) 动态规划(dynamic programming) 图论与网络分析(graph theory and network analysis) 存储论(inventory theory） 排队论(queueing theory,or waiting line) 对策论(game theory) 决策论(decision theory)
3.模型方法 二、基本方法（步骤） 1.分析和表述问题 2.建立模型 3.求解模型和优化方案 4.测试模型及对模型进行必要的修正 5.建立对解的有效控制 6.方案的实施 §3 运筹学的主要分支 线性规划（linear programming-LP） 非线性规划(nonlinear programming-NLP) 动态规划(dynamic programming) 图论与网络分析(graph theory and network analysis) 存储论(inventory theory) 排队论(queueing theory, or waiting line) 对策论(game theory) 决策论(decision theory)
第二章线性规划与单纯形法 §1线性规划问题的提出及其数学模型 一、在管理中一些典型的线性规划应用 合理利用线材问题：如何在保证生产的条件下，下料最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最大 产品生产计划：合理利用人力、物力、财力等，使获利最大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调运方案，使总运费最小 §2图解法及单纯型法解题思路 例1.某工厂在计划期内要安排I、Ⅱ两种产品的生产，已知生产单位产品所 需的设备台时及A、B两种原材料的消耗、资源的限制，如下表： 资源限制 设备 300台时 原料A 2 400千克 原料B 0 1 250千克 单位产品获利50元100元 问题：工厂应分别生产多少单位【、Ⅱ产品才能使工厂获利最多？ 线性规划模型： 决策变量：x:I产品的产量，x2:Ⅱ产品的产量 目标函数：Maxz=50x1+100x2 约束条件：s.tx1+x2≤300 2x1+ x2≤400 x2≤250 x1,x2≥0 例2某公司由于生产需要，共需要A,B两种原料至少350 吨(A,B两种材料有一定替代性)，其中A原料至少购进125
第二章 线性规划与单纯形法 §1 线性规划问题的提出及其数学模型 一、在管理中一些典型的线性规划应用 合理利用线材问题：如何在保证生产的条件下，下料最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最大 产品生产计划：合理利用人力、物力、财力等，使获利最大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调运方案，使总运费最小 §2 图解法及单纯型法解题思路 例 1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所 需的设备台时及 A、B 两种原材料的消耗、资源的限制，如下表： Ⅰ Ⅱ 资源限制 设备 1 1 300 台时 原料 A 2 1 400 千克 原料 B 0 1 250 千克 单位产品获利 50 元 100 元 问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？ 线性规划模型： 决策变量： x1：Ⅰ产品的产量， x2：Ⅱ产品的产量 目标函数：Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 ≤ 300 2 x1 + x2 ≤ 400 x2 ≤ 250 x1 , x2 ≥ 0 例 2 某公司由于生产需要，共需要 A，B 两种原料至少 350 吨（A，B 两种材料有一定替代性），其中 A 原料至少购进 125
吨。但由于A,B两种原料的规格不同，各自所需的加工时间 也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需 要1小时，而公司总共有600个加工小时。又知道每吨A原料的 价格为2万元，每吨B原料的价格为3万元，试问在满足生产需 要的前提下，在公司加工能力的范围内，如何购买A,B两种 原料，使得购进成本最低？ 决策变量：x1:原料A的购买量，x2:原料B购买量 目标函数：Min f=2x1+3x2 约束条件：st x1+x2≥350 xl ≥125 2x1+x2≤600 x1,x2≥0 建模过程 1理解要解决的问题，了解解题的目标和条件： 2定义决策变量(x1,x2，.，xm),每一组值表示一个方案： 3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标： 4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 一般形式 决策变量设置：x1,x2,.,xm 目标函数：Max(Mim)z=clxl+c2x2+.+cmXm 约束条件：st.allxl+al2x2+.+alnxn≤(=，≥)bl a21x1+a22x2+.+a2nxm≤(=，≥)b2 aml xl+am2x2+.+amn xn≤(=，≥)bm xl,x2,.,xm≥0 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示 线性规划问题的有关概念，并求解。 下面通过例1详细讲解其方法： 例1.目标函数：
吨。但由于 A，B 两种原料的规格不同，各自所需的加工时间 也是不同的，加工每吨 A 原料需要 2 个小时，加工每吨 B 原料需 要 1 小时，而公司总共有 600 个加工小时。又知道每吨 A 原料的 价格为 2 万元，每吨 B 原料的价格为 3 万元，试问在满足生产需 要的前提下，在公司加工能力的范围内，如何购买 A，B 两种 原料，使得购进成本最低？ 决策变量： x1：原料 A 的购买量，x2：原料 B 购买量 目标函数： Min f = 2x1 + 3 x2 约束条件： s.t. x1 + x2 ≥ 350 x1 ≥ 125 2 x1 + x2 ≤ 600 x1 , x2 ≥ 0 建模过程 1.理解要解决的问题，了解解题的目标和条件； 2.定义决策变量（ x1 ，x2 ，. ，xn ），每一组值表示一个方案； 3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标； 4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 一般形式 决策变量设置： x1， x2， . ， xn 目标函数： Max （Min） z = c1 x1 + c2 x2 + . + cn xn 约束条件： s.t. a11 x1 + a12 x2 + . + a1n xn ≤（ =, ≥ ）b1 a21 x1 + a22 x2 + . + a2n xn ≤（ =, ≥ ）b2 . . am1 x1 + am2 x2 + . + amn xn ≤（ =, ≥ ）bm x1 ，x2 ，. ，xn ≥ 0 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示 线性规划问题的有关概念，并求解。 下面通过例 1 详细讲解其方法： 例 1.目标函数：
Max z=50x1+100x2 约束条件： s.t.xI+ x2≤300(A) 2x1+ x2≤400 (B) x2≤250 c xl≥0(D) 2 ≥0(E) 得到最优解：xl=50, x2=250 最优目标值z=27500 (1)分别取决策变量X1,X2为坐标向量建立直角坐标系。在直角坐标系里，图上 任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平 面。 X,≥0 X1≥0 X1=0 X2=0 (2)对每个不等式（约束条件），先取其等式在坐标系中作直线，然后确定不等式 所决定的半平面
Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E) 得到最优解： x1 = 50， x2 = 250 最优目标值 z = 27500 (1)分别取决策变量 X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上 任意一点的坐标代表了决策变量的一组值，例 1 的每个约束条件都代表一个半平 面。 （2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式 所决定的半平面。 x2 x1 X1≥0 X1=0 x2 x1 X2≥0 X2=0
=300 2x1+x2=-400 100 100 200 2x1+x2≤400 300 x1+x2≤300 (3)把五个图合并成一个图，取各约束条件的公共部分 x=250 2x1+x2-400 300 x2=250 2≤250 x1+x2-300 100200300 x2-0 (4)目标函数x=50x1+100x2,当z取某一固定值时得到一条直线，直线上的每 点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点 时，z在可行域内实现了最大化。A,B,C,D,E是可行域的顶点，对有限个约 束条件则其可行域的顶点也是有限的
（3）把五个图合并成一个图，取各约束条件的公共部分 （4）目标函数 z=50x1+100x2，当 z 取某一固定值时得到一条直线，直线上的每一 点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到 B 点 时，z 在可行域内实现了最大化。A，B，C，D，E 是可行域的顶点，对有限个约 束条件则其可行域的顶点也是有限的。 100 2x1+x2≤400 100 200 2x1+x2=400 300 200 300 400 100 200 300 100 200 300 x1+x2≤300 x1+x2=300 100 100 x2≤250 x2=250 200 300 200 300 x1 x2 x2=0 x1=0 x2=250 x1+x2=300 2x1+x2=400
x2 Z=10000=50x1+100x2. F27500=50x1+100x2 z20000=50x1+100x2 A.D =0=50x1+100x 、 重要结论： 1如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解： 2.无穷多个最优解。若将例1中的目标函数变为maxz=50x1+50x2,则线段BC上 的所有点都代表了最优解： 3.无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般 来说，这说明模型有错，忽略了一些必要的约束条件： 4.无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行 域为空域，不存在满足约束条件的解，当然也就不存在最优解了。 例2采用图解法。（练习） x21 x1=125 600 2x1+3x2=1200 40m 2x1+x2=600 2x1+3x2=900 20 v1+x7=350 10m 2x1+3x2=800 100200302000600 单纯型法是用来求解线性规划问题的方法
重要结论： 1.如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解； 2.无穷多个最优解。若将例 1 中的目标函数变为 max z=50x1+50x2，则线段 BC 上 的所有点都代表了最优解； 3.无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般 来说，这说明模型有错，忽略了一些必要的约束条件； 4.无可行解。若在例 1 的数学模型中再增加一个约束条件 4x1+3x2≥1200，则可行 域为空域，不存在满足约束条件的解，当然也就不存在最优解了。 例 2 采用图解法。（练习） 单纯型法是用来求解线性规划问题的方法 x1 x2 z=20000=50x1+100x2 z=27500=50x1+100x2 z=0=50x1+100x2 z=10000=50x1+100x2 C A B D E 100 200 300 400 500 600 100 200 300 400 600 500 x1 =125 x1+x2 =350 2x1+3x2 =800 2x1+3x2 =900 2x1+x2 =600 2x1+3x2 =1200 x1 x2 Q
其求解思路」 (1)找到一个可行域上的顶点（初始基可行解）作为待考查的解。 (2)将该解和与其相邻的顶点（基可行解）相比较，若该解优于相邻解，则该解 为整个线性规划问题的最优解：否则将更优的相邻解代替当前考查的解。 (3)重复第(2)步，直至找到解的情况，计算结束。 §3“管理运筹学”软件的操作方法 “管理运筹学2.0版(Window版)，是1.0版(DOS版)的升级版。它包括：线性 规划、运输问题、整数规划(0-1整数规划、纯整数规划和混合整数规划)、目标 规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、 存储论、排队论、决策分析、预测问题和层次分析法，共15个子模块。 1.软件使用演示：（演示例1） 第一步：点击“开始”>“程序”>“管理运筹学 2.0”,弹出主窗口。 例1. 目标函数： Max z=50x1+100x2 约束条件： St xl+ x2≤300(A) 2x1+ 2≤ 400 (B) x2≤250(C) xl ≥0 0 x2 ≥0 (E)
其求解思路: （1）找到一个可行域上的顶点（初始基可行解）作为待考查的解。 （2）将该解和与其相邻的顶点（基可行解）相比较，若该解优于相邻解，则该解 为整个线性规划问题的最优解；否则将更优的相邻解代替当前考查的解。 （3）重复第（2）步，直至找到解的情况，计算结束。 §3 “管理运筹学”软件的操作方法 “管理运筹学”2.0 版（Window 版），是 1.0 版（DOS 版）的升级版。它包括：线性 规划、运输问题、整数规划（0-1 整数规划、纯整数规划和混合整数规划）、目标 规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、 存储论、排队论、决策分析、预测问题和层次分析法，共 15 个子模块。 1.软件使用演示：（演示例 1） 第一步：点击“开始”->“程序”-> “管理运筹学 2.0”，弹出主窗口。 例 1. 目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E)
号营理运等学2可 回回冈 管理运筹学 线性规划 图与网络 其它模型 说明 线性规划 存储论 关于 运输题 最小生成树间题 队论 帮 空助规划 最大流回颗 决第分析桥 退出 目行规划 果小费用大流 预测 对第论 关路径题 层次分析法 第二步：选择所需子模块，点击主窗口中的相应按钮。本题中选用“线性规划方法。 点击按钮弹出如下界面： a 。原。 第三步：点击“新建按钮，输入数据。本题中共有2个变量，4个约束条件，目标 函数取MAX。点击“确定”后，在表中输入Cj,bi和a町等值，并确定变量的正负约 输入数值后的界面如下
第二步：选择所需子模块，点击主窗口中的相应按钮。本题中选用“线性规划”方法。 点击按钮弹出如下界面： 第三步：点击“新建”按钮，输入数据。本题中共有 2 个变量，4 个约束条件，目标 函数取 MAX。点击“确定”后，在表中输入 Cj,bi 和 aij 等值，并确定变量的正负约 束。 输入数值后的界面如下