教案1绪论与图解法改

管理运筹学(OR)(美Operations

Research)(英Operational

Research)学时数：64学时教材：《管理运筹学教程》北京交通大学参考书：其它版本的《管理运筹学》；运筹学教材编写组编《运筹学》，清华大学出版社胡运权主编《运筹学教程》清华大学出版社；牛映武主编《运筹学》西安交通大学出版社；要求：1、上课认真听讲，不翘课2、按时完成作业3、多沟通、多交流成绩评定：

作业：10分；考勤：10分；期中考试：10分上机作业：10分期末考试：60分§1

运筹学的产生和发展运筹学是运用筹划的科学，原意“作战研究”或“运用研究”。一、 绪论§1.1

运筹学产生运筹学的三个来源是军事、管理和经济军事特点是：定量化、系统化方法迅速发展；采集真实的实际数据；多学科密切协作；解决方法渗透物理学的思想。（1）波得塞（Bawdsey)雷达站的研究1939年任务：如何最好地运用空军及新发明的雷达保卫国家Morse小组领导的运筹学小组目标：打破德军对英吉利海峡的封锁建议：用飞机代替舰艇投掷水雷，起爆深度由100米改为25米，当敌舰刚下潜时攻击；运送物资的船队及护卫舰的编队由小规模、多批次改为大规模、少批次。丘吉尔采纳了建议英国战斗机援法德军突破马奇诺防线，法军节节败退，英军参与抗德。英军的战机均在法国上空与德军作战，指挥维护在法国。法国请求增援10中队，邱吉尔同意。但运筹学小组认为：按现在的方式，英军的援法战机两周内会全军覆灭；不增加战机，而应以英国本土为基地与德军战斗，使局面大为改观。管理康托洛维齐（Kantorovich)生产配置问题、原材料的合理利用、运输问题等《生产组织与计划中的数学方法》经济冯·诺意曼（Von.neumann)《对策论与经济行为》§1.1

运筹学的发展运筹学的发展大概分三个阶段第一个阶段——蓬勃生长期·39年英国成立了世界上第一个运筹学工作小组，从事防空预警系统的研制（研究如何合理运用雷达）·1939年前苏联的康托洛维奇提出类似线性规划模型

1960年《最佳资源利用的经济计算》，获诺贝尔奖··1947年美国数学家，提出线性规划模型及单纯形算法·42年美国成立运筹学工作小组，研究战斗行动效能，行动方式·战争结束，Mores和Kimball合著第一部运筹学专著“运筹学的方法”·战后，运筹学的应用领域从军事扩展到其它各领域·1948年英国成立运筹学学会·1952年美国成立运筹学学会·1956年法国成立运筹学学会·1959年英、美、法成立运筹学联合会第二阶段——危机期六、七十年代第三阶段——运筹学发展的正确之路理念更新、实践为本、学科交融我国运筹学的发展§2

运筹学的释义运筹学具有如下的性质特点运筹学是一门应用科学运筹学的目的是寻找最佳解决问题的方案， 为决策者的最优决策提供依据以数学为基础提供定量分析以计算机为手段以软科学研究软系统多学科专家集体协作研究运筹学的定义由一支综合性的队伍，采用科学的方法，为一些涉及到有机系统（人-机）的控制系统问题提供解答，为该系统的总目标服务的学科。——钱学森执行部门对所控制的业务作出决策提供数量上的科学或利用所应用科学，执行部门对其所属业务作出决策提供数量上依据的一门科学。——Morse运用科学方法来解决工业、商业、政府、国防等部门里有关人力、机器、物资、金钱等大型系统的指挥或管理中所出现的复杂问题的一门学科。其目的是“帮助管理者以科学方法确定其方针和行动”——英国运筹学会运筹学是应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型而获得最优决策的科学。——近代运筹学工作者·规划论——线性规划、目标规划、非线性规划、整数规划、动态规划、组合规划等·图与网络

·存储论

·排队论·对策论

·决策论

·仿真·马尔科夫过程

·可靠性 多目标规划……§3

运筹学的分支§3

运筹学的工作步骤提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数；建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来；求解。用各种手段(主要是数学方法，也可用其他方法)将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出；解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反应现实问题；解的控制。通过控制解的变化过程决定对解是否要作一定的改变；解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清楚用法、在实施中可能产生的问题和修改。§4

本课程的要求本课程的授课对象是管理科学与工程类及交通运输类专业本科生，属管理类专业技术基础必修课。学生通过学习该课程，应了解管理运筹学对优化决策问题进

行定量研究的特点，理解线性规划、整数规划、动态规划、图与网络、排队论和库存论等分支的基本优化原理，掌握其中常用的模型和算法，具有一定的建模能力。先修课程主要为线性代数和概率统计，学生对它们的掌握程度直接影响本课程的学习，所以要求学生课前要做必要的复习。学习方法：理解、掌握基本理论和方法的基础上，适当作些习题。二.线性规划(LP)(

Linear

Programming)第一章线性规划与单纯形法1947年由美国空军G.B.Dantzig提出。本部分是课程的最重要部分本节重点：线性规划模型的特点

线性规划解的存在情况线性规划标准型线性规划解的基本概念（特别是基解和基可行解）§1

线性规划问题及其数学模型1．1

问题的提出例1．某工厂计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时和A、B

两种原材料的消耗、以及可获利润如表所示，问应如何安排计划使该工厂获利最多？ⅠⅡ可利用资源设备128台时原材料A4016kg原材料B0412kg利润23？元设x1、x2分别表示计划期内产品Ⅰ、Ⅱ的产量，建立数学模型：约束条件

s.t.

x1

+

2x2

£

8(Subject

to)

4x1£164

x2

£12设备台时原材料A原材料B产品产量x1，x2‡0ⅠⅡ可利用资源设备128台时原材料A4016kg原材料B0412kg利润23？元利润最大 目标函数 max

z

=

2x1+

3x2例2

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

z=40x1+45x2+24x3约束条件2

x1

+ 3x2

+ x3

≤1003x1

+ 3x2

+ 2x3

≤120x1≥0，x2≥0，x3≥0称x1，x2

，x3≥0为决策变量例3．靠近某河流有两个化工厂（见图），流经第一化工厂的河流流量为每天500

万m3，在两个工厂之间有一条流量为每天200万m3

的支流。第一化工厂每天排放含有某种有害物质的工业污水2

万m3，第二化工厂每天排放这种工业污水1.4

万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。根据环保要求，河流中工业污水的含量不应大于0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万m3，第二化工厂处理工业污水的成本是800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。2万m31.4万m3设

x1、x2

分别为第一、第二化工厂每天处理的工业污水量。约束条件：第一化工厂到第二化工厂之间的污水含量要不大于0.2%(2

-

x1)

/500

£

2

/1000流经第二化工厂后，河流中的污水含量仍不大于0.2%[0.

8(2

-

x1)

+

(1.4-

x2)]

/

700

£

2

/

1000污水处理量限制x1

£

2，x2

£

1.4，x1

‡

0，x2

‡

0目标函数：要求两厂用于处理工业污水的费用最小min

z=

1000

x1+800

x22万m31.4万m3整理得数学模型：目标函数约束条件min

z

=

1000x1+

800x2s.t.

x1

‡

10.8

x1

+

x2

‡

1.6x1

£

2x2

£

1.4x1

‡

0，x2

‡

0线性规划问题的共同特征（模型的三要素）⑴每一个问题都用一组决策变量(x1，x2，…，xn)表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负的。⑵存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。⑶都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。线性规划模型的一般形式为：(1.1)max(min)s.t.z

=c1x1

+

c2x2

+…+

cnxna11x1

+

a12x2

+…+

a1nxn

£

(

=

,

‡)

b1a21x1

+a22x2

+…+

a2nxn

£

(=

,

‡)b2(1.2)…

…am1x1

+

am2x2

+…+amnxn

£

(

=

,

‡)

bmx1，x2，…，xn

‡

0(1.3)求解线性规划问题的任务是：在满足(1.2)、(1.3)

的所有(x1，x2，…，xn)（可行解）中求出使(1.1)达到最大(小)z

值的决策变量值*(x1*，x2*，…，xn

)（最优解）。1．2

图解法只有两个决策变量的问题可用图解法。图解法有助于理解线性规划问题的求解原理。例

1

max

z

=

2x1

+

3x2s.t.

x1

+2x2

£

84

x1£164

x2

£12x1，x2

‡0max

z

=

2x1+

3x2s.t.

x

+2

x

£

814

x12£164

x2

£12x1，x2

‡0x14x1=1624x

=12x1+2x2=8Q302x1+3x2=0Q43Q2(4,2)Q14解法：1o.建立平面直角坐标系；2o.找出表示每个约束的半平面，所有半平面的交集是可行域（全体可行解的集合）；3o.画出目标函数的等值线；4o.向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。x2线性规划问题解的存在情况：(1)存在唯一最优解max

z

=

2x1+

3x2s.t.

x1

+

2

x2

£

814

x

£164

x2

£12x1，x2

‡0x1x204x1=164x2=12x1+