运筹学教学课件(全)

第一章第一章 绪论绪论运运 筹筹 学学（Operations Research）运筹学的产生和发展运筹学的产生和发展 p运筹学作为一门数学学科，用纯数学的方法来解决最优方法的选择安排，却是在二十世纪四十年代才开始兴起。p运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。随着客观实际的发展，运筹学的许多内容不但研究经济和军事活动，有些已经深入到我们的日常生活当中去了。p运筹学的研究方法有：（1）从现实生活中抽出本质的要素来构造数学模型，因而可寻求一个跟决策者的目标有关的解；（2）探索求解的结构并导出系统的求解过程；（3）从可行方案中寻求系统的最优解法。运筹学的主要内容运筹学的主要内容 p数学规划数学规划n线性规划线性规划n非线性规划非线性规划n整数规划整数规划n参数规划参数规划n动态规划动态规划n目标规划目标规划 p排队论排队论p库存论库存论p图论图论p博弈论博弈论运筹学的主要内容运筹学的主要内容 p数学规划数学规划n线性规划线性规划 约束条件和目标函数都是线性函数的数学规划；约束条件和目标函数都是线性函数的数学规划；主要解法是：主要解法是：单纯形单纯形法；法；主要应用于企业规划和工农业的管理决策等方面。主要应用于企业规划和工农业的管理决策等方面。n非线性规划非线性规划 它是线性规划的进一步发展和继续。许多实际问题如设它是线性规划的进一步发展和继续。许多实际问题如设计问题、经济平衡问题都属于非线性规划的范畴。计问题、经济平衡问题都属于非线性规划的范畴。n整数规划整数规划 整数规划是研究决策变量取正整数或部分取整数的一类整数规划是研究决策变量取正整数或部分取整数的一类规划问题规划问题。运筹学的主要内容运筹学的主要内容 p数学规划数学规划n参数规划参数规划 参数规划是系数或常数项中带有参数的规划问题，主要研究问参数规划是系数或常数项中带有参数的规划问题，主要研究问题的解法：当参数在什么范围变化时问题有解以及参数的变题的解法：当参数在什么范围变化时问题有解以及参数的变化对最优解的影响。化对最优解的影响。n动态规划动态规划 它是与时间有关的规划问题，它是研究多阶段决策过程最优化它是与时间有关的规划问题，它是研究多阶段决策过程最优化问题。问题。n目标规划目标规划 目标规划就是在给定的决策环境中，使决策结果与预定目标的目标规划就是在给定的决策环境中，使决策结果与预定目标的偏差达到最小的数学模型。偏差达到最小的数学模型。与线性规划有很大的区别，主要表现在：在线性规划中，要与线性规划有很大的区别，主要表现在：在线性规划中，要求单个目标的优化，而目标规划则强调使多个目标得到满意求单个目标的优化，而目标规划则强调使多个目标得到满意的解答。另一方面，线性规划中，为得到一个可行解，必须的解答。另一方面，线性规划中，为得到一个可行解，必须满足所有的约束条件。满足所有的约束条件。运筹学的主要内容运筹学的主要内容 p排队论排队论 它是运筹学的又一个分支，它也叫做随机服务系统理论。它它是运筹学的又一个分支，它也叫做随机服务系统理论。它的研究目的是要回答如何改进服务机构或组织被服务的对的研究目的是要回答如何改进服务机构或组织被服务的对象，使得某种指标达到最优的问题。象，使得某种指标达到最优的问题。因为排队现象是一个随机现象，因此在研究排队现象的时因为排队现象是一个随机现象，因此在研究排队现象的时候，主要采用研究随机现象的概率论作为主要工具。候，主要采用研究随机现象的概率论作为主要工具。p库存论库存论 它是一种研究物资最优存储及存储控制的理论。它是一种研究物资最优存储及存储控制的理论。p图论图论 图论是研究由节点和边所组成的图形的数学理论和方法图论是研究由节点和边所组成的图形的数学理论和方法 p博弈论博弈论 博弈论是使用严谨的数学模型研究冲突对抗条件下最优决博弈论是使用严谨的数学模型研究冲突对抗条件下最优决策问题的理论。策问题的理论。运筹学在管理中的应用运筹学在管理中的应用 p工程管理与优化设计工程管理与优化设计 p生产计划与管理生产计划与管理 p市场营销管理市场营销管理 p库存管理库存管理 p会计与财务分析及管理会计与财务分析及管理 p人力资源管理人力资源管理 p设备维修、更新和可靠性、项目选择和评价等设备维修、更新和可靠性、项目选择和评价等 p物流管理与交通运输问题物流管理与交通运输问题 教学要求教学要求：第二章第二章 线性规划和单纯形法线性规划和单纯形法 掌握掌握线性规划的基本建模法和单纯形法基本原理会会在不同条件下运用单纯形法求解线性规划问题了解了解线性规划在经济和管理中的基本应用方法目目 录录p线性规划实例与模型线性规划实例与模型p线性规划的图解法与基本性质线性规划的图解法与基本性质p单纯形法原理单纯形法原理p线性规划的初始解解法线性规划的初始解解法目目 录录p线性规划实例与模型线性规划实例与模型p线性规划的图解法与基本性质线性规划的图解法与基本性质p单纯形法原理单纯形法原理p线性规划的初始解解法线性规划的初始解解法实用举例实用举例 某公司通过市场调研，决定生产高中档新型拉杆箱。某分销商决定买进该公司3个月内的全部产品。拉杆箱生产需经过原材料剪裁、缝合、定型、检验和包装4过程。通过分析生产过程，得出：生产中档拉杆箱需要用7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公司生产能力有限，3月内各部的最大生产时间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。通过市场调研部和会计部的调查核算得出结论：生产中档拉杆箱的利润是10元，高档拉杆箱的利润是9元。公司应各生产多少中档和高档拉杆箱才能使公司利润最大？实用举例实用举例 某公司通过市场调研，决定生产高中档新型拉杆箱。某分销商决定买进该公司3个月内的全部产品。拉杆箱生产需经过原材料剪裁、缝合、定型、检验和包装4过程。通过分析生产过程，得出：生产中档拉杆箱需要用7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公司生产能力有限，3月内各部的最大生产时间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。通过市场调研部和会计部的调查核算得出结论：生产中档拉杆箱的利润是10元，高档拉杆箱的利润是9元。公司应各生产多少中档和高档拉杆箱才能使公司利润最大？可以通过线性规划求解可以通过线性规划求解！线性规划模型的建立线性规划模型的建立 建立相应的线性规划模型：其中的 称为决策变量。目标函数目标函数约束条件约束条件一般线性规划模型Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn=b1(0)a21x1+a22x2+a2nxn=b2(0):am1x1+am2x2+amnxn=bm(0)x1,x2,xn 0s.t.为约束限制（Subject to）的缩写(LP)x1.xnb1.bma11 a1nam1 amnx=b=A=c=其中c=(c1,c2,cn)，称为价值系数向量；称为资源限制向量 X=(x1,x2,xn)T 称为决策变量向量称为技术系数矩阵(也称消耗系数矩阵)一般线性规划模型线性规划模型的标准形式线性规划模型的标准形式MaxZ=c1x1+c2x2+cnxnSubjectto(s.t.)a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx x1 1 0,0,x x2 2 0,0,x xn n 0为了讨论方便，把最大化、等式约束型的线性规划称为线为了讨论方便，把最大化、等式约束型的线性规划称为线性规划的标准型，即性规划的标准型，即标准化标准化原问题原问题标准化方法标准化方法目标函数目标函数Max f(x)Max f(x)Min f(x)Max f(x)约束条件约束条件引入松弛变量和人工变量引入松弛变量,不变变量变量 不变对某个对某个是任意的 线性规划模型的标准化例例:将如下线性规划模型标准化：将如下线性规划模型标准化：min z=x1+5 x2-8 x3-x4s.t.2 x1-3 x2+x3+x4 20 x1+2 x2+3 x3-x4 30 2x2+2 x3+3 x4-50 x1,x3,x4 0，x2取值无约束。取值无约束。max z1=-x1-5 x2+8 x3+x4s.t.2 x1-3 x2+x3+x4 20 x1+2 x2+3 x3-x4 30 2x2+2 x3+3 x4-50 x1,x3,x4 0，x2取值无约束。取值无约束。目标优化标准化目标优化标准化线性规划模型的标准化Maxz2=-x1-5y2+5y3+8x3+x4s.t.2 x1-3 y2+3y3+x3+x4 20 -x1-2 y2+2y3-3 x3+x4 -30 -2y2+2y3-2 x3-3 x4 50 x1,x3,x4,y2,y3 0 决策变量的标准化决策变量的标准化:y2-y3=x2max z1=-x1-5 x2+8 x3+x4s.t.2 x1-3 x2+x3+x4 20 x1+2 x2+3 x3-x4 30 2x2+2 x3+3 x4-50 x1,x3,x4 0，x2取值无约束取值无约束 线性规划模型的标准化Max z2=-x1-5y2+5y3+8x3+x4 s.t.2 x1-3 y2+3y3+x3 +x4+x5 =20 -x1-2 y2+2y3-3 x3+x4 +x6 =-30 -2y2+2y3-2 x3-3 x4 +x7 =50 x1,x3,x4,x5,x6,x7,y2,y3 0约束关系标准化约束关系标准化Max z2=-x1-5y2+5y3+8x3+x4 s.t.2 x1-3 y2+3y3+x3+x4 20 -x1-2 y2+2y3-3 x3+x4 -30 -2y2+2y3-2 x3-3 x4 50 x1,x3,x4,y2,y3 0 p可行解可行解:满足所有约束条件的解x=（x1，x2，.，xn），称为线性规划问题的可行解可行解。所有可行解的集合称为可行域可行域。p基基：设A是约束方程组的mn阶系数矩阵，秩为m，是A中阶非奇异子矩阵（即 ），则称是线性规划问题的一个基矩阵基矩阵，简称基基。B中的列向量称为基向量基向量，与基向量对应的变量x称为基变量基变量，其它变量称为非基变量非基变量。p基本解基本解：令非基变量=0，则由Ax=b可求出一个解，这个解x称为基本解基本解。p基本可行解基本可行解：满足非负条件的基本解称为基本可行解基本可行解。p最优解最优解：使目标函数达到最优值的可行解称为最优解最优解。线性规划的解线性规划的解 可行解、基本解、基本可行解的关系可行解可行解基本解基本解基本可行解基本可行解目目 录录p线性规划实例与模型线性规划实例与模型p线性规划的图解法与基本性质线性规划的图解法与基本性质p单纯形法原理单纯形法原理p线性规划的初始解解法线性规划的初始解解法线性规划的图解法线性规划的图解法 当只有两个决策变量当只有两个决策变量时，可用图解法求解！时，可用图解法求解！例例：用图解法求解以下线形规划问题。max z=4x1+3x2 s.t.x16 2x28 2x1+3x218 x10，x20 x1 x2 L3：2x1+3x2=18可行域可行域L1：x1=6L2：x2=4最优解B4x1+3x2解的特殊情况解的特殊情况多个最优解多个最优解解的特殊情况解的特殊情况无可行解无可行解解的特殊情况解的特殊情况无界解无界解线性规划的基本性质线性规划的基本性质 X可行域内部的点 可行解?是是 最优解?不不 若线性规划有最若线性规划有最优解，则最优解必在可行优解，则最优解必在可行域的顶点上达到。域的顶点上达到。凸集的概念凸集的概念 p凸集是线性规划中一个很重要的概念，凸集的一般定义为：凸集是线性规划中一个很重要的概念，凸集的一般定义为：如果在集合如