讲课教案1绪论及线模

《管理运筹学》赵鹏电话：51686763邮箱管理运筹学

(OR)(美OperationsResearch)(英OperationalResearch)§1运筹学的产生和发展运筹学是运用筹划的科学，原意“作战研究”或“运用研究”。一、绪论

运筹学的活动是从二次世界大战初期的军事任务开始的。当时迫切需要把各项稀少的资源以有效的方式分配给各种不同的军事经营及在每一经营内的各项活动。鲍德西（Bawdsey）研究（1935年）将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。“Blackett马戏团”在秘密报告中使用了“OperationalResearch”，即“运筹学”。0.运筹学的三个主要来源

特点是：定量化、系统化方法迅速发展；采集真实的实际数据；多学科密切协作；解决方法渗透物理学的思想。管理

计划评审技术（PERT）；决策论经济资源的优化利用问题、生产计划问题《对策论与经济行为》奠定了对策论的基础1.Morse小组领导的运筹学小组目标：打破德军对英吉利海峡的封锁建议：用飞机代替舰艇投掷水雷，起爆深度由100米改为25米，当敌舰刚下潜时攻击；运送物资的船队及护卫舰的编队由小规模、多批次改为大规模、少批次。丘吉尔采纳了建议英国战斗机援法德军突破马奇诺防线，法军节节败退，英军参与抗德。英军的战机均在法国上空与德军作战，指挥维护在法国。法国请求增援10中队，邱吉尔同意。但运筹学小组认为：按现在的方式，英军的援法战机两周内会全军覆灭；不增加战机，而应以英国本土为基地与德军战斗，使局面大为改观。军事

生产了雷达、火炮、深水炸弹等，但如何有效使用这些武器落后于制造。1939年8月成立11人跨学科小组。1.基本思想

田忌赛马

齐王田忌齐王田忌

上上上上

中中中中

下下下下

实力结果

“史记·高祖本纪”中刘邦语：“夫运筹帷幄之中，决胜于千里之外”。·1917年爱尔朗的排队论公式。

·1939年英国成立第一个运筹学工作小组，从事防空预警系统的研制（研究如何合理运用雷达），使原先平均击落一架敌机要发2万发炮弹改善为只要发4千发炮弹。

·1939年前苏联的康托洛维奇提出类似线性规划模型，

1960年《最佳资源利用的经济计算》，获诺贝尔奖。

·1942年美国成立运筹学工作小组，研究战斗行动效能，行动方式。

·1947年美国数学家，提出线性规划模型及单纯形算法

·战争结束，Mores和Kimball合著第一部运筹学专著“运筹学的方法”。

·战后，运筹学的应用领域从军事扩展到其它各领域。2.重要事件·1948年英国成立运筹学学会

·1952年美国成立运筹学学会

·1956年法国成立运筹学学会

·1959年英、美、法成立运筹学联合会

·我国50年代引入运筹学，1982年加入世界运筹学联合会(1956年时曾使用“运用学”，57年定名为“运筹学”)

3.学会组织§2运筹学的性质和内容

由一支综合性的队伍，采用科学的方法，为一些涉及到有机系统（人-机）的控制系统问题提供解答，为该系统的总目标服务的学科。——钱学森

运用科学方法来解决工业、商业、政府、国防等部门里有关人力、机器、物资、资金等大型系统的指挥或管理中所出现的复杂问题的一门学科。其目的是“帮助管理者以科学方法确定其方针和行动”——英国运筹学会

运筹学是应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型而获得最优决策的科学。——近代运筹学工作者1.运筹学的定义“运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学。”——P.M.Morse与G.E.Kimball2.性质追求的目标是整个组织或系统的最佳行动路线强调定量的手法以软科学研究软系统，定性与定量相结合，多学科交叉由于计算机的发展和大系统的要求，越来越重视定性、定量相结合以及人机交互算法。3.分支

·规划论——线性规划、目标规划、非线性规划、整数规划、动态规划、组合规划等

·图与网络

·存储论

·排队论

·对策论·决策论·仿真

·马尔科夫过程·可靠性多目标规划

……

§3运筹学的工作步骤

1.提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数；

2.建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来；

3.求解。用各种手段(主要是数学方法，也可用其他方法)将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出；

4.解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反应现实问题；

5.解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清楚用法、在实施中可能产生的问题和修改。§4本课程的要求

本课程的授课对象是管理科学与工程类及交通运输类专业本科生，属管理类专业技术基础必修课。

学生通过学习该课程，应了解管理运筹学对优化决策问题进行定量研究的特点，理解线性规划、整数规划、动态规划、图与网络、排队论和库存论等分支的基本优化原理，掌握其中常用的模型和算法，具有一定的建模能力。

先修课程主要为线性代数和概率统计，学生对它们的掌握程度直接影响本课程的学习，所以要求学生课前要做必要的复习。

学习方法：理解、掌握基本理论和方法的基础上，适当作些习题。

参考书：其他版本的《管理运筹学》

二.线性规划(LP)

(LinearProgramming)

本部分是课程的最重要部分§1线性规划问题及其数学模型第一章线性规划与单纯形法1．1问题的提出

利润最大目标函数maxz=2x1+3x2例2某工厂用钢与橡胶生产3种产品A、B、C，有关资料如下表404524332231ABC单位产品利润单位产品橡胶量单位产品钢消耗量产品已知每天可获得100单位的钢和120单位橡胶，问每天生产A、B、C各多少使总利润最大？解：设x1，x2，x3分别为A、B、C日产量，则有

约束条件

2x1+3x2+x3≤100

3x1+3x2+2x3≤120

x1≥0，x2≥0，x3≥0称x1，x2，x3≥0为决策变量

目标函数：maxz=40x1+45x2+24x32万m31.4万m32万m31.4万m3x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q24o.向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。

线性规划问题解的存在情况：(1)存在唯一最优解x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2如例1（2）有无穷多最优解

若将例1目标函数变为maxz=2x1+4x2，则问题变得存在无穷多最优解。如图x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+4x2=03Q2（3）有无界解(无有限最优解或无最优解)

z（4）无可行解（可行域为空集）注意：没有存在有限多个解的情况可行域有界时必有最优解，无界时不一定无最优解

用图解法求下面问题的解12无界不可行1．3线性规划问题的标准形式为了求解LP问题，必须统一其模型，本课程选用标准型式为maxz=c1x1+c2x2+···+cnxn (1.1)s.t.a11x1+a12x2+···+a1nxn=b1

a21x1+a22x2+···+a2nxn=b2

···

···

(1.2)

am1x1+am2x2+···+amnxn=bm

x1，x2，···，xn

0(1.3)其中bi

0，（i=1，2，···，m）一般m<n；m，n>0。标准型的简写形式:maxz=c1x1+c2x2+···+cnxn (1.1)s.t.a11x1+a12x2+···+a1nxn=b1

a21x1+a22x2+···+a2nxn=b2

···

···

(1.2)

am1x1+am2x2+···+amnxn=bm

x1，x2，···，xn

0(1.3)用求和符号表示用矩阵描述为：

maxz=CXAX=b X

0=(P1，P2，···，Pn)；a11…a12…

a1na21…a22…

a2n

…

…am1…am2…amnA=称A

为约束条件的m

×n阶系数矩阵，一般A的秩为m。0=00…0用向量表示：X=x1x2…xnPj=a1ja2j…amjb=b1b2…bm向量Pj对应的决策变量为xj

。b1

b2

bm

(p1,p2,…,pn)ΣPjxj=b

a11a12…a1n

a21a22…a2n

…

…

…

am1am2…amn

x1

x2

xn

=xj≥0j=1,…,nx1

x2

xn

Maxz=x1

x2

xn

(c1,c2,…,cn)=Σcjxj=CX=Σaijxj=bi

i=1,…,mAX=bX

≥0

b

x1+2x2

84x1

164x2

12x1，x2

0

maxz=2x1+3x2+0x3+0x4+0x5标准型：例3．将例1的数学模型化为标准型。

maxz=2x1+3x2

所加松弛变量x3，x4，x5表示没有被利用的资源，当然也没有利润，在目标函数中其系数应为零；即c3，c4，c5=0。

x1+2x2+x3=84x1+x4=164x2+x5

=12x1，x2，x3，x4，x5

0

x1+x2+x3

7x1

–

x2+x3

2–3x1+x2+2x3=5x1，x20，x3为无符号约束例4．将下述线性规划问题化为标准型

minz=–x1+2x2–3x3解：用x4-x5

替换x3

，令z’=-z

x1+x2+(x4-x5)+x6=7x1

–

x2+(x4-x5)-x7=2–3x1

+x2+2(x4-x5)=5x1，x2，x4，x5，x6，x7

0maxz’=x1–2x2+

3(x4-x5)+0x6+0x7用标准型求最优解后，再回到原变量。复习线性代数内容:列向量x=(x1，x2，…，xn）T为n维列向量。xRn行向量x=(x1，x2，…，xn）为n维列向量。xRn矩阵(向量)运算规则加减乘、求逆运算

结合律分配律交换律乘法无交换律线性相关一组向量v1,…,vn,如果有一组不全为零的系数α1,…,αn,使得: