数据模型与决策一运筹学和特殊情况下的投资决策

运筹学

OperationalResearch林齐宁博士，教授北京邮电大学经济管理学院Telmail:linqining66@

绪论一、运筹学的起源与发展二、运筹学的定义和主要研究分支三、运筹学的特点及研究对象四、运筹学解决问题的方法步骤五、运筹学与其他学科的关系一、运筹学的起源与发展起源于二次大战的一门新兴交叉学科与作战问题相关如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等英国称为OperationalResearch美国称为OperationsResearch战后在经济、管理和机关学校及科研单位继续研究1952年，Morse和Kimball出版《运筹学方法》1948年英国首先成立运筹学会1952年美国成立运筹学会1959年成立国际运筹学联合会(IFORS)我国于1982年加入IFORS，并于2023年8月组织了第15届大会一、运筹学的起源与发展1、中国运筹学会简介50年代中期，我国著名科学家钱学森、许国志等教授将运筹学从西方引入国内。1980年4月，中国数学会运筹学分会成立。1991年，中国运筹学会成立。历届学会理事长有，华罗庚、越民义，徐光辉，章祥荪，袁亚湘，2、中国系统工程学会简介1、1979年由钱学森、宋健、关肇直、许国志等21名专家、学者共同倡议并筹备。1980年11月18日在北京正式成立。第一届理事会理事长关肇直，第二、三届理事长许国志。第四、五届理事长顾基发、第六届理事长陈光亚。3、运筹学、系统工程主要研究人员构成1）数学：如华罗庚、越民义，徐光辉，章祥荪，袁亚湘，许国志，顾基发等；2）控制论：张仲俊，刘豹，陈珽，郑维敏，赵纯均，陈剑等3）管理等专业相关教学、科研技术人员567一、运筹学的起源与发展4、相关研究机构和高校1）中国科学院数学与系统科学研究院系统科学研究所2）中国科学院数学与系统科学研究院应用数学研究所3）哈工大：胡运权，黄梯云，钱国明等4）天津大学：刘豹，顾培亮，张维，杜

纲等5）西安交大：汪应洛，席酉民等6）上海交大：张仲俊，王浣尘等7）清华大学：郑维敏，赵纯均，陈剑等；8）大连理工：王众托，胡祥培等9）北航：顾昌耀，黄海军等10）北理工：吴沧浦，吴祈宗，张强等9二、运筹学的定义和主要研究分支运筹学的定义为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法——Morse和Kimball运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策——英国运筹学会运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理——中国百科全书现代运筹学涵盖了一切领域的管理与优化问题，称为ManagementScience10二、运筹学的定义和主要研究分支运筹学的分支数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等图论与网路理论随机服务理论：排队论存储理论网络计划方法决策理论对策论系统仿真：随机模拟技术、系统动力学可靠性理论金融工程11三、运筹学的特点及研究对象运筹学的特点：1)优化以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来协调各部门之间的利害冲突，从而求出问题的最优解。所以运筹学可看成是一门优化技术，为解决各类问题提供优化方法2定量为所研究的问题提供定量的解决方案。如采用运筹学研究资源分配问题时，其求解结果是一个定量的最优资源分配方案。运筹学的研究对象：来自生产管理过程中的具体问题，如资源分配、物资调度，生产计划与控制等。12四、运筹学解决问题的方法步骤1、理清问题、明确目标2、建立模型讨论：什么叫模型3、求解模型。建立模型之后，需要设计相应算法进行求解，实际问题运算量一般都很大，通常需要用计算机求解。4、结果分析讨论：模型计算结果与已有的经验或知识进行比较1）模型计算结果和已有的经验或知识比较一致2）模型计算结果和已有的经验或知识差异较大

你喜欢那一种情况？13五、运筹学与其他学科的关系

运筹学目标分析、建模、求解和结果分析需要用到很多相关学科的知识，它与如下学科的知识关系比较密切。1、数学：学习、应用运筹学应该具备较广的数学知识，许多运筹学者来自数学专业就是这个原因，有人甚至认为运筹学是一门应用数学；2、管理学：运筹学研究对象是生产管理过程的具体问题，在利用运筹学理论和方法解决具体问题时，需要的涉及管理科学的有关理论；3、计算机：运筹学所研究的实际问题通常都是比较复杂，而且规模比较大，在求解这些问题时，必须借助计算机来完成。14第一章线性规划1.1线性规划模型1.1.1问题的提出一、例1、多产品生产问题（Max,）甲电缆乙电缆资源量铜（吨）2110铅（吨）118价格（万元）64需求无限制7另

问该工厂应如何安排生产才能使工厂的总收入最大？一、例1、多产品生产问题（Max,）设x1,x2

分别代表甲、乙两种电缆的生产量，f(x)为工厂的总收入，则上述问题可用如下数学模型来表示其中，OBJ（Objective）表示目标，S.t.（Subjectto）表示满足于。表示在满足铜、铅资源和需求等约束条件下，使工厂的总收入这一目标达到最大。最优解为二、例2、配料问题（min,)某混合饲料加工厂计划从市场上购买甲、乙两种原料生产一种混合饲料。混合饲料对VA、VB1、VB2和VD的最低含量有一定的要求。已知单位甲、乙两种原料VA、VB1、VB2和VD的含量，单位混合饲料对VA、VB1、VB2和VD的最低含量以及甲、乙两种原料的单位价格如下表所示。问该该加工厂应如何搭配使用甲乙两种原料，才能使混合饲料在满足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）有一个目标函数，该目标函数根据其的具体性质取最大值或最小值。当目标为成本型时取最小，而当目标为效益型时取最大。3）有一组约束方程，包括决策变量的非负约束；4）目标函数和约束方程都是线性的。2、线性规划数学模型的定义定义1.1有一个目标函数和一组约束方程，且目标函数和约束方程都是线性的数学模型称为线性规划数学模型。四、线性规划数学模型的背景模型和思考1、线性规划数学模型的背景模型：例1.1的多产品生产计划问题的数学模型称为线性规划的背景模型。把该背景模型的条件一般化后可叙述如下：用有限量的几种资源生产若干种产品，如何安排生产，才能使工厂的总收入或利润达到最大。2、背景模型的思考1）讨论：什么叫背景模型能够帮助我们理解和记住一些相对抽象和复杂问题的简单问题模型。2）背景模型的思考利用一些相对比较简单的问题来阐述一些相对复杂和抽象的运筹学中的一些基础概念和原理是本课程力求在教学中体现的第一个特点，希望大家用心体会。

1.1.2线性规划数学模型的一般表示方式21

1、和式22

2、向量式23

3、矩阵式24

1.1.3线性规划的图解法f(x)=36线性规划问题的几个特点：1、线性规划的可行域为凸集；讨论：什么叫凸集？集合中任意两点连线上的一切点仍然在该集合中，在平面上为凸多边形，在空间上为凸几何体；讨论：最优解在那里取得？2、线性规划的最优解一定可在其凸集的某一顶点上达到；讨论：什么情况有最优解？最优解的存在性条件？3、线性规划若有可行域且其可行域有界，则一定有最优解。上述3个结论是线性规划的3个基础定理，可以用严格的数学方法进行证明。我们以简单、直观的图解法方式给出，相信大家是可以接受的。1.3线性规划求解的基础原理和单纯形法1.3.1线性规划问题的标准形一、线性规划模型一般形式二、求解思路1、规定一标准型线性的规划问题数学模型；2、如何把非标准形的线性规划问题数学模型转化为标准形线性规划问题数学模型？3、如何求解标准形线性规划问题数学模型。三、线性规划问题的标准形在上述线性规划标准形中，决策变量的个数取n+m个是习惯表示法。我们知道，对于线性规划背景模型，有m个约束方程，且每个约束方程的不等式均为“”号。如果我们在每个约束方程的左边加上一个大于等于0的变量，则可将各个约束方程的“”号转变为“=”。此时，决策变量就有n+m个。28

四、变换的方法1、目标函数为min型，价值系数一律反号。令g(x)=-f(x)=-CX,有minf(x)=-max[-f(x)]=-maxg(x)2、第i个约束的bi

为负值，则该行左右两端系数同时反号，同时不等号也要反向3、第i个约束为型，在不等式左边增加一个非负的变量xn+i

，称为松弛变量；同时令cn+i

=04、第i个约束为型，在不等式左边减去一个非负的变量xn+i

，称为剩余变量；同时令cn+i

=05、若xj0，令

xj=-xj

，代入非标准型，则有xj

06、若xj不限，令

xj=xj-xj，xj

0，xj0，代入非标准型29

五、

变换举例：1.3.2线性规划问题的解和基础定理本章开始到现在已讨论的内容，相信大部分读者都会感到比较容易理解和掌握。这一节我们将要讨论关于线性规划问题解的一些基础概念和定理，与前面讨论的内容相比，线性规划问题解的一些基础概念略显难一些，其中比较难的概念有线性规划问题的基和基础解等相关概念。为了帮助大家比较容易理解这些概念，我们先从大家熟悉的两个变量两个线性方程组这一简单问题入手，然后逐步过渡到我们所要讨论的线性规划问题的基和基础解等相关概念。著名数学家笛卡尔曾说过，他最擅长做的两件事是：1)第一做简单事；2)第二是将复杂事变为简单事。本课程将从大家熟悉的一些简单问题入手，然后逐步过渡到运筹学一些相对比较抽象和难的概念和原理。这是本课程教学力求的另一特点。一、线性方程组的解考虑如下线性方程组的解：再考虑如下线性方程组的解：一、线性方程组的解类似地，如果将方程组（3）中的变量x2或x1当成常数，分别移到其方程的右边后采用消元法进行求解，则也可得到如下两组通解及其特解：一、线性方程组的解仔细观察和思考方程组（3）的三组通解（4）、（6）和（8）或三组特解（5）、（7）和（9）是如何得到的，以及能够得到这些通解或特解的条件是什么？根据求解线性方程组克莱姆条件可知，能够得到方程组（3）的通解（4）或特解（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，都能得到线性规划（10）的一组通解和特解（见式（4）--（9））。变量x1和x2为基变量，变量x3为非基变量，令x3=0，得解（5）为线性规划（10）的基础解，但因该基础解中x1=-1<0，不满足线性规划（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）是线性规划（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)最多有个基二、标准型线性规划解的若干基础概念可行解与非可行解满足约束条件和非负条件的解X称为可行解，不满足约束条件或非负条件的解X称为非可行解基础解对应某一基B且令其非基变量XN=0，求得基变量XB的值。称X=(XB,XN)T为基础解。其中，XB=B1

b，XN=0XB

是基础解必须满足如下条件：1）非0分量的个数m；2、m个基变量所对应的系数矩阵为非奇异的；3、满足m个约束条件。二、标准型线性规划解的若干基础概念

基础可行解与基础非可行解基础解XB的非零分量都0时，称为基础可行解，否则为基础非可行解。退化解基础可行解的非零分量个数<

m

时，称为退化解可行基

对应于基础可行解的基称为可行基最优解

使目标函数达到最优的基础可行解称为最优解无穷多最优解

当最优解的基变量组成不止一个时，线性规划有无穷多最优解39

三、线性规划标准型问题解的关系约束方程的解空间基础解可行解非可行解基础可行解退化解四、线性规划解的判定对于某一线性规划的任意一个解X，我们如何判定X是基础解、或是基础可行解、或是基础非可行解、或是非可行解、或是可行解呢？判定步骤：1、写出给定线性规划问题的标准型线性规划；2、根据基础解的三个条件判定X是否是基础解。当三个条件均满足时，X才是基础解；否则X不是基础解。若X是基础解，转3；否则，转4；3、X是否满足非负约束，即其基变量值是否都大于0？若是，X是基础可行解；否则X是基础非可行解。4、将X代入给定线性规划的所有约束方程，包括非负约束，若X满足所有约束方程，则X为可行解，否则X为非可行解。41五、线性规划解的判定举例六、线性规划问题解的一些基本定理42定理1若线性规划问题存在可行域，则其可行域是凸集。定理2线性规划问题可行域的顶点与其基础可行解一一对应。定理3若线性规划问题存在可行域，则它必有基础可行解。定理4若线性规划问题存在可行域且其可行域有界，则它必有最优解。定理5若线性规划问题存在最优解，则其最优解一定可以在其可行域的某个顶点上取得。43

1.3.3单纯型法的基础原理一、单纯形法的基础思路和步骤（一）基础思路从一个基础可行解出发，设法得到另一个更好的基础可行解，直到目标函数达到最优时，基础可行解即为最优解。（二）基础步骤1、求一个基础可行解，称为初始基础可行解。求初始基础可行解的方法必须简单实用，且具有通用性；2、最优检验。即检验任一基础可行解是否是最优解。若是，则停止计算；否则，转3）；3、确定改善方向，求得另一个更好的基础可行解；转2，直到求得最优解为止。通常把这三个基础步骤称为最优化三步曲。事实上，这三部曲对求解其它最优化问题（如非线性规划等）也是适用的。44

单纯型法的基础步骤二、单纯性法基本原理45为了使大家比较直观容易地理解利用单纯形法求解线性规划问题三个步骤的基础原理，我们先以解线性方程组的方法来求解例1线性规划。解：（一）标准化（二）选择初始基础可行解46从系数矩阵A中可知，x3、x4和x5的系数列向量P3，P4和P5是线性独立，这些向量可构成一个基B0（初始基）对应于基B0的变量x3、x4和x5为基变量，其它两个变量x1和x2为非基变量。即XB0=（x3，x4，x5)T，XN0=（x1，x2)T令非基变量x1=x2=0，可得一初始基础可行解X(0)=(0，0，10，8，7)T此时，对应于X(0)的目标函数f(X(0))=6x1+4x2=0（三）最优检验47将（2）式代入(1)的目标函数后可得f(X)=0+6x1+4x2

（3）从目标函数（3）可知，非基变量x1和x2的系数都是正数，所以X(0)不是最优解。（四）求另一个更好的基础可行解1、确定换入变量及其值从从目标函数（3）可知，非基变量x1的系数大于x2的系数，所以，可确定x1为换入变量由于所以，当另一个非基变量x2仍然为0时，由（4）式可得到换入变量x1的值为x1=Min{10/2，8/1，--}=52、确定换出变量48由于基变量的个数只能等于约束方程的个数m，在本例中，m=3，所以，当有一个非基变量做为换入变量变为基变量时，就必须有一个基变量做为换出变量变为非基变量。即从所有基变量中，将其中一个大于0的基变量变为等于0的非基变量，该非基变量就是换出变量。从（4）式可知，当x1=5时，x3=0，所以x3为换出变量。由此得到线性规划（1）的一个新的基B1和一组新的基变量与非基变量。XB1=（x1，x4，x5)T，XN1=（x3，x2)T3、求另一个更好的基础可行解49将（1)约束方程中对应于基B1的非基变量x3和x2移到方程的右边后可得令非基变量x2=x3=0，可得另一基础可行解X(1)=(5，0，0，3，7)T此时，对应于X(1)的目标函数f(X(1))=6x1+4x2=30>f(X(0))=0（五）最优检验将（5）式代入(1)的目标函数后可得f(X)=30+x2-3x3

（6）从目标函数（6）可知，非基变量x2的系数是正数，所以X(1)不是最优解。（六）求另一个更好的基础可行解501、确定换入变量及其值从从目标函数（6）可知，只有非基变量x2的系数为正，所以，可确定x2为换入变量。由于所以，当另一个非基变量x3仍然为0时，由（7）式可得到换入变量x1的值为x2=Min{10/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，XN2=（x3，x4)T513、求另一个更好的基础可行解将（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重新编号，则约束方程可化为其中，b’i和a’ij表示经过若干次迭代后，当前的右端系数和技术系数，以便区别于原始的右端系数bi和技术系数aij。将上式代入（2）的目标函数后可得机会成本54在一般情况下，目标函数值OBJ计算公式和机会成本计算公式可写成四、最优检验其中，I为基变量的下标集。最优检验条件为其中，J表示非基变量的下标集。对于基变量的检验数为因为基变量的技术系数满足：aij=1,当i=jaij=0,当ij五、求另一个更好的基础可行解

55若某一基础可行解经过最优检验表明不是最优解，则需要设法求得另一个更好的基础可行解。求另一个更好的基础可行解的主要步骤如下：1、确定换入变量；2、确定换出变量；3、通过基变换或初等变换求得另一个更好的基础可行解。我们已在前面例子中说明了这种初等变换方法的基础思路。下一小节我们将用单纯形表进一步说明这种初等变换方法。56

1.3.4单纯形法表及单纯形法57

例

试列出下面线性规划问题的初始单纯型表单纯形法步骤581、求初始基础可行解

将线性规划模型标准化，建立初始单纯形表，求初始基础可行解。2、最优检验：对任一基础可行解X，若其所有检验数j

=cjzj0，jJ则X为最优解，即X*=X，计算最优解所对应的最优目标函数值f(X*)，算法停止。否则转3。3、求另一个更好的基础可行解1）确定入变量xk

若则xk为换入变量；2）确定换出变量xl*

计算若l为空集，则为无界解，算法停止。否则与右端系数b’l

同一行的基变量xl*为换出变量。转3）3）初等变换，得到另一个更好的基础可行解将入变量xk所在列k，出变量xl*所在行l的主元技术系数a’lk变换为1，主元a’lk所在列的其余元变换为0。更换基变量（用入变量xk替换出变量xl*）及其价值系数，得到另一个更好的基础可行解。转2。几种特殊情况下的投资决策设备更新决策设备更新决策是比较设备更新与否对企业的利弊。通常采用净现值作为投资决策指标。设备更新决策可采用两种决策方法，一种是比较新、旧两种设备各自为企业带来的净现值的大小；另一种是计算使用新、旧两种设备所带来的现金流量差量，考察这一现金流量差量的净现值的正负，进而做出恰当的投资决策。例（教材97－98页）

方法1，新旧设备净现值比较继续使用旧设备:每年经营现金流量为20万元，净现值为：NPV＝20万元×PVIFA（10％，10）＝20万元×6.145＝122.9万元使用新设备：初始投资额＝120－10－16＝94(万元)经营现金流量现值＝40×PVIFA(10%,10)＝40×6.145＝245.8(万元)终结现金流量现值＝20×0.386＝7.72(万元)净现值＝－94＋245.8＋7.72＝159.52(万元)由于使用新设备的净现值大于继续使用旧设备的净现值，故采用新设备。方法2：差量比较法初始投资额＝120－10－16＝94(万元)经营现金流量差量＝40－20＝20(万元)经营现金流量差量现值＝20×6.145＝122.9(万元)终结现金流量现值＝20×0.386＝7.72(万元)现金流量差量净现值＝－94＋122.9＋7.72＝36.62(万元)设备比较决策这一决策比较购置不同设备的效益高低。一般来讲，进行这一决策时应比较不同设备带来的成本与收益，进而比较其各自净现值的高低。但有时我们也假设不同设备带来的收益是相同的，因而只比较其成本高低即可。很多情况下，不同设备的使用期限是不同的，因此我们不能直接比较不同设备在使用期间的净现值大小，而需要进行必要的调整。这种调整有两种：一种是将不同设备的净现值转化为年金。一种是将不同设备转化为相同的使用年限。例