运 筹 学

1.运筹学定义：用数学的方法研究各问题的变化。

2.线性规划：数学模型的目标函数为变量的线性函数，约束条件也为变量的线性等式或不等式，故此模型称之为线性规划3.可行解：把满足所有约束条件的解称为该线性规划的可行解。

4.最优解：把目标函数值最大（即利润最大）的可行解称为该线性规划的最优解。

5.最优值：在最优解条件下的目标函数值为最优目标函数值，简称最优值。

6.松弛量：在线性规划中，一个“≤”约束条件中没使用的资源或能力称之为松弛量7.松弛变量：为了把一个线性规划标准化，需要有代表没使用的资源或能力的变量，诚挚为松弛变量。

8.标准化: 把所有约束条件都写成等式，称为线性规划模型的标准化。

所得结果称为线性规划的标准形式。

9.剩余变量：对于“≥”约束条件，可以增加一些代表最低限约束的超过量，称之为剩余变量。

10.灵敏度分析：建立数学模型和求得最优解之后，研究线性规划的一些系数Ci,Gij,bj的变化对最优解产生的影响。

11.对偶价格：在约束条件常数项中增加一个单位而使最优目标函数值得到改进的数量称之为这个约束条件的对偶价格12.单纯形法的基本思路：一，找出一个初始基本可行解二，最优性检验三，基变换13.线性规划的基本解：由线性规划的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解，这个解称之为线性规划的基本解。

14.基本可行解：一个基本解可以是可行解，也可以是非可行解，他们之间的主要区别在于其所有变量的解是否满足非负的条件，我们把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。

15.初始可行基：在第一次找可行基时，所找到的基或为单位矩阵或由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。

16.最优性检验：判断已求得的基本可行解是否是最优解。

17.最优性检验的依据-----检验数σj:目标函数中所有变量的系数即为各变量的检验数，把变量xi的检验数记为σi,显然所有基变量的检验数必为零。

运筹学知识点要求运筹学知识点要求第一部分结论1、运筹学的特点（1）以最优性或合理性为核心。

（2）以数量化、模型化为基本方法。

（3）具有强烈的系统性、交叉性特征。

（4）以计算机为重要的技术支持。

2、运筹学模型求解方法：知道迭代算法的原理步骤。

3、运筹学模型（1）运筹学模型：使用较多的是符号或数学模型，大多数为优化模型。

（2）模型的一般结构（3）模型的三大要素决策变量、目标函数及优化方向、约束条件。

（4）了解模型的分类4、建立优化模型解决实际问题（1）要求能对较简单的实际问题建立优化模型。

主要涉及：一般线性规划模型，整数（特别是0－1规划）规划模型。

5、了解运筹学运用领域。

第二部分线性规划1、线性规划模型的几种表示形式及特点2、线性规划模型的标准形式及如何标准化3、线性规划问题各种解的概念及关系（关系图示）（可行解、非可行解、基本解、基本可行解、最优解，基本可行解的个数小于等于）4、线性问题有关解的基本定理（主要是概念理解）（1）不一定都有最优解（2）若有，一定会在基本可行解上达到（3）基本可行解的个数有限小于等于（4）并非所有最优解都是基本可行解（5）了解凸集与凸组合的概念，理解两个最优解的凸组合都是最优解。

（6）可行解为基本可行解的充要条件5、线性规划单纯形法（1）制作初始单纯表（注意非基变量检验系数的求法，特别注意求有待定系数时的检验系数）（2）各种解的判别条件，对于最大化目标函数问题，包括：唯一最优解：有最优解无穷多最优解存在一个k 有：（或称之为线性规划问题存在可择最优解）无界解，存在k 有：（3）线性规划问题求解结果中解的情况有最优解（唯一最优解、无穷多最优解），无界解，无可行解（4）基变换中入基变量的确定A 、入基变量的必要条件（）B 、最速上升准则的理解，不是使目标函数改进最大，而是使目标函数改进速度最大。

m nC m nC 0<j σ0≤j σ0≤j σ0=j σ0,0'≤>k k p 且σ0≥j σ（5）最小比值确定出基变量的目的：保证基变换后新的基本解是可行的。

运筹学-学习指南一、名词解释1松弛变量为将线性规划问题的数学模型化为标准型而加入的变量。

2可行域满足线性约束条件的解（x,y）叫做可行解，由所有可行解组成的集合叫做可行域。

3人工变量亦称人造变量.求解线性规划问题时人为加入的变量。

用单纯形法求解线性规划问题，都是在具有初始可行基的条件下进行的,但约束方程组的系数矩阵A中所含的单位向量常常不足m个，此时可加入若干(至多m)个新变量，称这些新变量为人工变量。

4对偶理论每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题解的同时，也给出了另一个问题的解。

研究线性规划中原始问题与对偶问题之间关系的理论5灵敏度分析研究与分析一个系统（或模型）的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。

在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。

通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。

6影子价格反映资源配置状况的价格。

影子价格是指在其他资源投入不变的情况下,每增加一单位的某种资源的投入所带来的追加收益。

即影子价格等于资源投入的边际收益。

只有在资源短缺的情况下,每增加一单位的投入才能带来收益的增加7产销平衡运输一种特殊的线性规划问题。

产品的销售过程中，产销平衡是指工厂产品的产量等于市场上的销售量。

8西北角法是运筹学中制定运输问题的初始调运方案（即初始基可行解）的基本方法之一。

也就是从运价表的西北角位置开始，依次安排m个产地和n个销地之间的运输业务，从而得到一个初始调运方案的方法。

9最优性检验检验当前调运方案是不是最优方案的过程。

10动态规划解决多阶段决策过程优化问题的方法：把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解11状态转移方程从阶段K到K+1的状态转移规律的表达式12逆序求解法在求解时，首先逆序求出各阶段的条件最优目标函数和条件最优决策，然后反向追踪，顺序地求出改多阶段决策问题的最优策略和最优路线。

运筹学的主要内容运筹学一般应包括线性规划、非线性规划、整数规划、动态规划、多目标规划、网络分析、排队论、对策论、决策论、存储论、可靠性理论、模型论、投入产出分析等等。

线性规划、非线性规划、整数规划、动态规划、多目标规划这五个部分统称为规划论，它们主要是解决两个方面的问题。

一个方面的问题是对于给定的人力、物力和财力，怎样才能发挥它们的最大效益；另一个方面的问题是对于给定的任务，怎样才能用最少的人力、物力和财力去完成它。

网络分析主要是研究解决生产组织、计划管理中诸如最短路径问题、最小连接问题、最小费用流问题、以及最优分派问题等。

特别在设计和安排大型复杂工程时，网络技术时重要的工具。

排队现象在日常生活中屡见不鲜，如机器等待修理，船舶等待装卸，顾客等待服务等。

它们有一个共同的问题，就是等待时间长了，会影响生产任务的完成，或者顾客会自动离去而影响经济效益；如果增加修理工、装卸码头和服务台，固然能解决等待时间过长的问题，但又会蒙受修理工、码头和服务台空闲的损失。

这类问题的妥善解决是排对论的任务。

对策论是研究具有厉害冲突的各方，如何制定出对自己有利从而战胜对手的斗争策略。

例如，战国时代田忌赛马的故事便是对策论的一个绝妙的例子。

决策问题是普遍存在的，凡属“举棋不定”的事情都必须做出决策。

人们之所以举棋不定，是因为人们在着手实现某个预期目标时，面前出现了多种情况，又有多种行动方案可供选择。

决策者如何从中选择一个最优方案，才能达到他的预期目标，这是决策论的研究任务。

人们在生产和消费过程中，都必须储备一定数量的原材料、半成品或商品。

存储少了会因停工待料或失去销售机会而遭受损失，存储多了又会造成资金积压、原材料及商品的损耗。

因此，如何确定合理的存储量、购货批量和购货周期至关重要，这便是存储论要解决的问题。

对于一个复杂的系统和设备，往往是由成千上万个工作单元或零件组成的，这些单元或零件的质量如何，将直接影响到系统或设备的工作性能是否稳定可靠。

运筹学：应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。

第一章、线性规划的图解法1.基本概念线性规划：是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。

线性规划的三要素：变量或决策变量、目标函数、约束条件。

目标函数：是变量的线性函数。

约束条件：变量的线性等式或不等式。

可行解：满足所有约束条件的解称为该线性规划的可行解。

可行域：可行解的集合称为可行域。

最优解：使得目标函数值最大的可行解称为该线性规划的最优解。

唯一最优解、无穷最优解、无界解（可行域无界）或无可行解（可行域为空域）。

凸集：要求集合中任意两点的连线段落在这个集合中。

等值线：目标函数z，对于z的某一取值所得的直线上的每一点都具有相同的目标函数值，故称之为等值线。

松弛变量：对于“≤”约束条件，可增加一些代表没使用的资源或能力的变量，称之为松弛变量。

剩余变量：对于“≥”约束条件，可增加一些代表最低限约束的超过量的变量，称之为剩余变量。

2.线性规划的标准形式约束条件为等式（=）约束条件的常数项非负（b j≥0）决策变量非负（x j≥0）3.灵敏度分析：是在建立数学模型和求得最优解之后，研究线性规划的一些系数的变化对最优解产生什么影响。

4.目标函数中的系数c i的灵敏度分析目标函数的斜率在形成最优解顶点的两条直线的斜率之间变化时，最优解不变。

5.约束条件中常数项b i的灵敏度分析对偶价格：约束条件常数项中增加一个单位而使最优目标函数值得到改进的数量。

当某约束条件中的松弛变量（或剩余变量）不为零时，这个约束条件的对偶价格为零。

第二章、线性规划问题在工商管理中的应用1.人力资源分配问题（P41）设x i为第i班次开始上班的人数。

2.生产计划问题（P44）3.套材下料问题（P48）下料方案表（P48）设x i为按各下料方式下料的原材料数量。

4.配料问题（P49）设x ij为第i种产品需要第j种原料的量。

运筹学第2章单纯形法 2.1 单纯形法的基本思想该方法简捷、规范，是举世公认的解决LP问，题行之有效单纯形法（Simplex Method）是美国著名运筹学家丹捷格（Dantzig）1947年首先提出的通用方法。

单纯形法不仅是解决LP问题的最基本的算法之一，而且成为解决整数规划和非线性规划某些算法的基础。

2、单纯形法的3种形式——方程组形式（代数形式）、表格形式、矩阵形式3、单纯形法的基本思路——基于LP问题的标准形，先设法找到某个基本可行解（称为初始基本可行解）；开始实施从这个基本可行解向另一个基本可行解的转换，要求这种转换不仅容易实现，而且能改善（至少保持）目标函数值；继续寻找更优的基本可行解，进一步改进目标函数值。

当某一个基本可行解不能再改善时，该解就是最优解。

（或者是出现无可行解、无最优解、无穷多最优解的情况）2.1.1 方程组形式的单纯形法例1 一个企业需要同一种原材料生产甲、乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，获得的利润也不相同（如下表）。

请问，该企业应如何安排生产计划，才能使获得的利润达到最大？解：该问题的LP模型为：将该问题的LP模型化为标准形⎪⎩⎪⎨⎧≥≤+≤++=,1202410032..4621212121xxxxxxt sxxzm ax函数约束的增广矩阵为：很显然 R （A ） = R （A ，b ）= 2 < 5，即该方程组有无穷多组解。

系数矩阵为：决策变量向量为：选取 为基，则 为基变量， 为非基变量令非基变量 ，则可以得到一基本 可行解为： 下面的计算都是以它为初始点逐次实施转换，故将其称为初始基本可行解。

此时，Z=0，其经济含义为：该企业没 有安排甲、乙两种产品的生产，当然也就没有利润可言。

条典☐ 初始基本可行解所对应的可行基是一个m 阶的单位阵； ☐ 目标函数表达式中所有的基变量的系数全部为0。

☐ 这是单纯形法所必需的！！！ ☐ 分析目标函数表达式☐ 非基变量的系数都是正数，若将它们转换为基变量，目标函数值则就会可能增加。

运筹学的概念运筹学是一门关于决策与优化的学科，通过运用数学方法、计算机技术以及经济管理原理，研究如何在资源有限的情况下，进行有效的决策与规划，以最大化效益或最小化成本。

它是一门交叉学科，融合了数学、信息技术、经济学、管理学等多个领域的知识。

运筹学的概念最早产生于二战期间的美国和英国，当时由于战争的需求，决策者们需要通过科学的方法来解决各种复杂的军事问题，于是运筹学应运而生。

运筹学的中文名称“运筹学”直接翻译自英文的Operations Research，Operations 代表“运营”或“操作”，Research则表示“研究”。

可以说，运筹学主要研究如何在运营过程中进行决策与规划，以达到最优化的目标。

运筹学的核心思想是通过数学模型来描述复杂决策问题，并应用数学方法来解决这些问题。

它主要包括问题建模、数学方法、模型求解和决策评价等步骤。

运筹学的研究对象包括生产计划、物流调度、供应链管理、投资决策、风险管理等各种决策问题。

通过建立数学模型，运筹学可以帮助决策者在不同的约束条件下，进行决策方案的制定，以达到最优化的效果。

在运筹学中，最重要的概念之一是优化。

优化是指在资源有限的情况下，寻求最优解的过程。

运筹学通过数学模型的建立和求解，使决策者能够找到最佳的决策方案。

优化方法可以基于不同的目标函数，例如最大化利润、最小化成本、最大化效率等。

运筹学的优化方法包括线性规划、整数规划、动态规划、网络优化、多目标规划等。

此外，运筹学还重视风险管理和决策分析。

在实际决策过程中，决策者需要考虑不确定因素和风险，并制定相应的风险控制措施。

运筹学通过建立风险模型和决策分析模型，帮助决策者进行风险评估和决策分析，以实现决策的科学化和合理化。

随着信息技术的发展，运筹学与计算机科学的结合越来越紧密。

运筹学利用计算机技术进行大规模数据的处理和复杂问题的求解，提高了决策效率和准确性。

特别是在供应链管理、物流调度等领域，运筹学在实践中发挥了重要的作用。