林齐宁-数据、模型与决策一运筹学ppt课件

1、运筹学Operational Research林齐宁博士，教授北京邮电大学经济管理学院:21281705E_mail: .绪 论一、运筹学的来源与开展二、运筹学的定义和主要研讨分支三、运筹学的特点及研讨对象四、运筹学处理问题的方法步骤五、运筹学与其他学科的关系.一、运筹学的来源与开展来源于二次大战的一门新兴交叉学科与作战问题相关如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等英国称为 Operational Research美国称为 Operations Research战后在经济、管理和机关学校及科研单位继续研讨19

2、52年，Morse 和 Kimball出版1948年英国首先成立运筹学会1952年美国成立运筹学会1959年成立国际运筹学结合会(IFORS)我国于1982年参与IFORS，并于1999年8月组织了第15届大会.一、运筹学的来源与开展1、中国运筹学会简介50年代中期，我国著名科学家钱学森、许国志等教授将运筹学从西方引入国内。1980年4月，中国数学会运筹学分会成立。1991年，中国运筹学会成立。历届学会理事长有，华罗庚、越民义，徐光辉，章祥荪，袁亚湘，2、中国系统工程学会简介 1、1979年由钱学森、宋健、关肇直、许国志等21名专家、学者共同倡议并筹备。1980年11月18日在北京正式成立。

3、第一届理事会理事长关肇直，第二、三届理事长许国志。第四、五届理事长顾基发、第六届理事长陈光亚。3、运筹学、系 统工程 主要研讨人员构成1数学：如华罗庚、越民义，徐光辉，章祥荪，袁亚湘，许国志，顾基发等；2控制论：张仲俊，刘豹，陈珽，郑维敏，赵纯均，陈剑等3管理等专业相关教学、科研技术人员.5.6.7.一、运筹学的来源与开展4、相关研讨机构和高校1中国科学院数学与系统科学研讨院系统科学研讨所2中国科学院数学与系统科学研讨院运用数学研讨所3哈工大：胡运权，黄梯云，钱国明等4天津大学：刘豹，顾培亮，张维，杜 纲等5西安交大：汪应洛，席酉民等6上海交大：张仲俊，王浣尘等7清华大学：郑维敏，赵纯均，陈剑

4、等；8大连理工：王众托，胡祥培等9北航：顾昌耀，黄海军等10北理工 ：吴沧浦，吴祈宗，张强等.9二、运筹学的定义和主要研讨分支运筹学的定义为决策机构对所控制的业务活动作决策时，提供以数量为根底的科学方法Morse 和 Kimball运筹学是把科学方法运用在指点人员、工商企业、政府和国防等方面处理发生的各种问题，其方法是开展一个科学的系统方式，并运用这种方式预测，比较各种决策及其产生的后果，以协助主管人员科学地决议任务方针和政策英国运筹学会运筹学是运用分析、实验、量化的方法对经济管理系统中人力、物力、财力等资源进展统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理中国百科全书现代运筹学涵

5、盖了一切领域的管理与优化问题，称为 Management Science.10二、运筹学的定义和主要研讨分支运筹学的分支数学规划：线性规划、非线性规划、整数规划、动态规划、目的规划等图论与网路实际随机效力实际：排队论存储实际网络方案方法决策实际对策论系统仿真：随机模拟技术、系统动力学可靠性实际金融工程.11三、运筹学的特点及研讨对象运筹学的特点：1)优化以整体最优为目的，从系统的观念出发，力图以整个系统最正确的方式来协调各部门之间的利害冲突，从而求出问题的最优解。所以运筹学可看成是一门优化技术，为处理各类问题提供优化方法2定量为所研讨的问题提供定量的处理方案。如采用运筹学研讨资源分配问题时，其

6、求解结果是一个定量的最优资源分配方案。运筹学的研讨对象：来自消费管理过程中的详细问题，如资源分配、物资调度，消费方案与控制等。.12四、运筹学处理问题的方法步骤1、理清问题、明确目的2、建立模型讨论：什么叫模型 3、求解模型。建立模型之后，需求设计相应算法进展求解，实践问题运算量普通都很大，通常需求用计算机求解。 4、结果分析讨论：模型计算结果与已有的阅历或知识进展比较 1模型计算结果和已有的阅历或知识比较一致 2模型计算结果和已有的阅历或知识差别较大 他喜欢那一种情况？.13五、运筹学与其他学科的关系 运筹学目的分析、建模、求解和结果分析需求用到很多相关学科的知识，它与如下学科的知识关系比较

7、亲密。1、数学：学习、运用运筹学应该具备较广的数学知识，许多运筹学者来自数学专业就是这个缘由，有人甚至以为运筹学是一门运用数学；2、管理学：运筹学研讨对象是消费管理过程的详细问题，在利用运筹学实际和方法处理详细问题时，需求的涉及管文科学的有关实际；3、计算机：运筹学所研讨的实践问题通常都是比较复杂，而且规模比较大，在求解这些问题时，必需借助计算机来完成。.14第一章 线性规划1.1 线性规划模型1.1.1问题的提出一、例1、多产品消费问题Max, 甲电缆乙电缆资源量铜（吨）2110铅（吨）118价格（万元）64需求无限制7另 问该工厂应如何安排消费才干使工厂的总收入最大？.一、例1、多产品消费

8、问题Max, 设x1, x2 分别代表甲、乙两种电缆的消费量，f(x)为工厂的总收入，那么上述问题可用如下数学模型来表示其中，OBJObjective表示目的，S.t.Subject to表示满足于。表示在满足铜、铅资源和需求等约束条件下，使工厂的总收入这一目的到达最大。最优解为.二、例2、配料问题min, )某混合饲料加工厂方案从市场上购买甲、乙两种原料消费一种混合饲料。混合饲料对VA、VB1、VB2和VD的最低含量有一定的要求。知单位甲、乙两种原料VA、VB1、VB2和VD的含量，单位混合饲料对VA、VB1、VB2和VD的最低含量以及甲、乙两种原料的单位价钱如下表所示。问该该加工厂应如何搭

9、配运用甲乙两种原料，才干使混合饲料在满足VA、VB1、VB2和VD的最低含量要求条件下，总本钱最小？.二、例2、配料问题MIN, )设 x1, x2分别代表混合单位饲料对甲、乙两种原料的用量，f(x)表示单位混合饲料所需求的本钱，那么上述问题的线性规划数学模型如下：该数学模型的最优解为该问题的最优解为x1=3.69，x2=0.77，minf(x)=1.49.三、线性规划数学模型的特征和定义1、线性规划数学模型的特征：1有一组决策变量x1，x2，xn表示某一方案。这一组决策变量的详细值就代表一个详细方案；2有一个目的函数，该目的函数根据其的详细性质取最大值或最小值。当目的为本钱型时取最小，而当目

10、的为效益型时取最大。3有一组约束方程，包括决策变量的非负约束；4目的函数和约束方程都是线性的。2、线性规划数学模型的定义定义1.1 有一个目的函数和一组约束方程，且目的函数和约束方程都是线性的数学模型称为线性规划数学模型。.四、线性规划数学模型的背景模型和思索1、线性规划数学模型的背景模型：例1.1的多产品消费方案问题的数学模型称为线性规划的背景模型。把该背景模型的条件普通化后可表达如下：用有限量的几种资源消费假设干种产品，如何安排消费，才干使工厂的总收入或利润到达最大。2、背景模型的思索1讨论：什么叫背景模型可以协助我们了解和记住一些相对笼统和复杂问题的简单问题模型。2背景模型的思索利用一些

11、相对比较简单的问题来论述一些相对复杂和笼统的运筹学中的一些根底概念和原理是本课程力求在教学中表达的第一个特点，希望大家用心领会。. 1.1.2 线性规划数学模型的普通表示方式.21 1、和式.22 2、向量式.23 3、矩阵式.24 1.1.3 线性规划的图解法f(x)=36.线性规划问题的几个特点：1、线性规划的可行域为凸集；讨论：什么叫凸集？集合中恣意两点连线上的一切点依然在该集合中，在平面上为凸多边形，在空间上为凸几何体；讨论：最优解在那里获得？2、线性规划的最优解一定可在其凸集的某一顶点上到达；讨论：什么情况有最优解？最优解的存在性条件？3、线性规划假设有可行域且其可行域有界，那么一定

12、有最优解。上述3个结论是线性规划的3个根底定理，可以用严厉的数学方法进展证明。我们以简单、直观的图解法方式给出，置信大家是可以接受的。.1.3 线性规划求解的根底原理和单纯形法1.3.1 线性规划问题的规范形一、线性规划模型普通方式二、求解思绪1、规定一规范型线性的规划问题数学模型；2、如何把非规范形的线性规划问题数学模型转化为规范形线性规划问题数学模型？3、如何求解规范形线性规划问题数学模型。.三、线性规划问题的规范形在上述线性规划规范形中，决策变量的个数取n+m个是习惯表示法。我们知道，对于线性规划背景模型，有m个约束方程，且每个约束方程的不等式均为“号。假设我们在每个约束方程的左边加上一

13、个大于等于0的变量，那么可将各个约束方程的“号转变为“=。此时，决策变量就有n+m个。.28 四、变换的方法1、目的函数为min型，价值系数一概反号。令 g(x) = -f(x) = -CX, 有 min f(x) = - max - f(x) = - max g(x)2、第i 个约束的bi 为负值，那么该行左右两端系数同时反号，同时不等号也要反向3、第i 个约束为 型，在不等式左边添加一个非负的变量xn+i ，称为松弛变量；同时令 cn+i = 04、第i 个约束为 型，在不等式左边减去一个非负的变量xn+i ，称为剩余变量；同时令 cn+i = 05、假设xj 0，令 xj= -xj ，代

14、入非规范型，那么有xj 06、假设xj 不限，令 xj= xj - xj， xj 0，xj 0，代入非规范型.29 五、 变换举例：.1.3.2 线性规划问题的解和根底定理本章开场到如今已讨论的内容，置信大部分读者都会感到比较容易了解和掌握。这一节我们将要讨论关于线性规划问题解的一些根底概念和定理，与前面讨论的内容相比，线性规划问题解的一些根底概念略显难一些，其中比较难的概念有线性规划问题的基和根底解等相关概念。为了协助大家比较容易了解这些概念，我们先从大家熟习的两个变量两个线性方程组这一简单问题入手，然后逐渐过渡到我们所要讨论的线性规划问题的基和根底解等相关概念。著名数学家笛卡尔曾说过，他最

15、擅长做的两件事是：1)第一做简单事；2)第二是将复杂事变为简单事。本课程将从大家熟习的一些简单问题入手，然后逐渐过渡到运筹学一些相对比较笼统和难的概念和原理。这是本课程教学力求的另一特点。.一、线性方程组的解思索如下线性方程组的解：再思索如下线性方程组的解：.一、线性方程组的解类似地，假设将方程组3中的变量x2或x1当成常数，分别移到其方程的右边后采用消元法进展求解，那么也可得到如下两组通解及其特解：.一、线性方程组的解仔细察看和思索方程组3的三组通解4、6和8或三组特解5、7和9是如何得到的，以及可以得到这些通解或特解的条件是什么？根据求解线性方程组克莱姆条件可知，可以得到方程组3的通解4或

16、特解5的条件是方程组3中的变量x1和x2的系数矩阵行列式不等于0，即或变量x1和x2的系数矩阵B1是非奇特矩阵或变量x1和x2的系数列向量是线性无关。显然，这三个条件是等价的。.一、线性方程组的解同样，由于方程组组3中的变量x1和x3的系数矩阵行列式|B2|不等于0与变量x2和x3的系数矩阵行列式|B3|不等于0，即才干得到方程组3的通解或特解6或7与通解或特解8或9。将上面讨论的方程组3加上一目的函数和变量非负约束条件后就变成一规范型线性规划。如：.一、线性方程组的解对于上述规范型线性规划10,称 B1 、B2和B3为线性规划10的基。因利用其中任何一个基B1 或B2或B3，都能得到线性规划

17、10的一组通解和特解见式4-9。变量x1和x2为基变量，变量x3为非基变量，令x3=0，得解5为线性规划10的根底解，但因该根底解中x1= -10，不满足线性规划10的变量非负约束条件，因此，该根底解5是线性规划10的根底非可行解。变量x1和x3为基变量，变量x2为非基变量，令x2=0，得解7为线性规划10的根底解。该根底解中x1和x3均大于0，满足线性规划10的变量非负约束条件，因此，该根底解7是线性规划10的根底可行解。变量x2和x3为基变量，变量x1为非基变量，令x1=0，得解9为线性规划10的根底解.该根底解中x2和x3均大于0，满足线性规划10的变量非负约束条件，因此，该根底解9是线

18、性规划10的根底可行解。.二、规范型线性规划解的假设干根底概念规范型有 n+m 个变量， m 个约束行“基的概念在规范型中，技术系数矩阵有 n+m 列，即 A = ( P1, P2 , , Pn+m )A中线性独立的 m 列，构成该规范型的一个基，即 B = ( P1 , P2 , , Pm )， | B | 0 P1 , P2 , , Pm 称为基向量与基向量对应的变量称为基变量，记为 XB = ( x1 , x2 , , xm )T，其他的变量称为非基变量，记为 XN = ( xm+1 , xm+2 , , xm+n ) T ， 故有 X = XB ， XN ) 最多有 个基.二、规范型线

19、性规划解的假设干根底概念可行解与非可行解满足约束条件和非负条件的解 X 称为可行解，不满足约束条件或非负条件的解 X 称为非可行解根底解对应某一基B且令其非基变量 XN = 0，求得基变量 XB的值。称X = (XB , XN)T为根底解。 其中，XB = B1 b， XN = 0XB 是根底解必需满足如下条件： 1非0分量的个数 m； 2、m个基变量所对应的系数矩阵为非奇特的； 3、满足m个约束条件。.二、规范型线性规划解的假设干根底概念 根底可行解与根底非可行解根底解 XB 的非零分量都 0 时，称为根底可行解，否那么为根底非可行解。退化解 根底可行解的非零分量个数 f (X(0) )=0

20、五最优检验将5式代入(1)的目的函数后可得 f (X)=30+x2-3x3 6从目的函数6可知，非基变量x2的系数是正数，所以X(1)不是最优解。.六求另一个更好的根底可行解501、确定换入变量及其值从从目的函数6可知，只需非基变量x2的系数为正，所以，可确定x2为换入变量。由于所以，当另一个非基变量x3依然为0时，由7式可得到换入变量x1的值为 x2=Min10/0.5，3/0.5，7/1=62、确定换出变量从7式可知，当x2=6时，x4=0，所以x4为换出变量。由此得到线性规划1的一个新的基B2和一组新的基变量与非基变量。B2=(P1 ,P2 ,P5 ), XB2=x1，x2，x5)T，X

21、N2=x3，x4)T.513、求另一个更好的根底可行解将1)约束方程中对应于基B2的非基变量x3和x4移到方程的右边后可得令非基变量x3=x4=0，可得另一根底可行解 X(2) = (2，6，0，0，1)T此时，对应于X(2)的目的函数f (X(2) )=6x1+4x2=36 f (X(1) )=30七最优检验将8式代入(1)的目的函数后可得 f (X)=36-2x3-2x4 9从目的函数9可知，非基变量x3和x4的系数都是负数，所以X(2)是最优解。即X*= X(2) = (2，6，0，0，1)T ,f (X*)=36.三、求初始根底可行解背景模型，MAX, )52设线性规划问题为另设bi0 (i=1,2,m)。规范化后，假设对xj和aij重新编号，那么约束方程可化为变量x1，x2，xm作为初始基变量，其他变量作为初始非基变量，并令xm+1=xm+1=xn+m=0，那么得初始本可行解.四、最优检验53对于规范化线性规划问题(2)，经过假设干次迭代后，假设对xj及aij重新编号，那么约束方程可化为其中，bi和aij表示经过假设干次迭代后，当前的右端系数和技术系数，以便区别于原始的右端系