运筹学电子教案重庆交通学院管理系信息与系统教研室一、绪论
§ 1、运筹学的简史
运筹学作为科学名字是出现在 20世纪 30
年代末。当时英、美对付德国的空袭，
雷达作为防空系统的一部分，从技术上是可行的，但实际运用时却并不好用。
为此一些科学家研究如何合理运用雷达等问题而开始进行一类新问题的研究。
因为它与研究技术问题不同，就称之为
,运用研究,（ Operational Research）。
这种,运用研究,就是,运筹学,。运筹学的英语是 Operation Research 。
§ 2、运筹学的性质和特点
运筹学是一门应用科学。至今还没有统一且确切的定义。提出以下几个定义来说明运筹学的性质和特点。一个是,为决策机构在对其控制下的业务活动进行决策时，提供以数量化为基础的科学方法。,它强调的是决策的 数量化 的 科学方法 。
运筹学的另一定义是：,运筹学是一门 应用科学,它广泛应用现有的 科学技术知识和数学方法,解决实际中提出的专门问题,为决策者选择最优决策提供定量依据 。,
它强调的是 应用性和数学方法,其目的是为决策者选择最优决策提供定量依据 。
§ 3、运筹学的工作步骤
运筹学在解决大量实际问题过程中形成了自己的工作步骤 。
（ 1） 提出和形成问题 。 即要弄清问题的目标,可能的约束,问题的可控变量以及有关参数,搜集有关资料 。
（ 2） 建立模型 。 即把问题中可控变量,参数和目标与约束之间的关系用一定的模型表示出来 。
（ 3） 求解 。 用各种手段 （ 主要是数学方法,也可用其它方法 ） 将模型求解 。 解可以是最优解,
次优解,满意解 。 复杂模型的求解需用计算机,
解的精度要求可由决策者提出 。
（ 4） 解的检验 。 首先检查求解步骤和程序有无错误,然后检查解是否反映现实问题 。
（ 5） 解的控制 。 通过控制解的变化过程决定对解是否要做一定的改变 。
（ 6） 解的实施 。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清解的用法，
在实施中可能产生的问题和修改。
以上过程应反复进行。
§ 4、运筹学的模型
运筹学在解决问题时,按研究对象不同可构造各种不同的模型 。 模型是研究者对客观现实经过思维抽象后用文字,图表,
符号,关系式以及实体模样描述所认识到的客观对象 。
模型有三种基本形式,（ 1） 形象模型,
（ 2） 模拟模型,（ 3） 符号或数学模型 。
建立数学模型的方法主要有以下五种：
（ 1） 直接分析法
（ 2） 类比法
（ 3） 数据分析法
（ 4） 试验分析法
（ 5） 想定 （ 构想 ） 法
§ 5、运筹学的应用
运筹学在早期的应用主要在军事领域 。 现已发展到广泛的领域：
（ 1） 市场销售
（ 2） 生产计划
（ 3） 库存管理
（ 4） 运输问题
（ 5） 财政和会计
（ 6） 人事管理
（ 7） 设备维修,更新和可靠性,项目选择和评价
（ 8） 工程的优化设计
（ 9） 计算机和信息系统
（ 10） 城市管理等等二、线性规划与目标规划
线性规划是运筹学的一个重要分支，自从 1947年
G.B.Dantzig提出了一般线性规划问题求解的方法 —
— 单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入。
1.1 问题的提出
在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、
物力、财力等资源，以便得到最好的经济效果。
线性规划主要解决两类问题：
1,资源有限,要求生产的产品 （ 或利润 ） 最多 。
2,任务 （ 或产品 ） 一定,要求消耗的资源 （ 或成本 ） 最少 。
某工厂在计划期内要安排生产 Ⅰ,
Ⅱ 两种产品,已知生产单位产品所需的设备台时及 A,B两种原材料的消耗,如表 1-1所示,问应该如何安排计划才能使该工厂获利最多？
例 1
表 1— 1
Ⅰ Ⅱ
设备原材料 A
原材料 B
1
4
0
2
0
4
8台时
16kg
12kg
单位产品利润（元）
2 3
解 设 x1,x2分别表示计划期内产品 Ⅰ 和产品 Ⅱ
的产量,因为设备的有效台时是 8,这是一个限制产量的条件,所以在确定产品 Ⅰ 和产品 Ⅱ 的产量时,要考虑不超过设备的有效台时数,即可用不等式表示为
x1+2x2≤8
同理,因原材料 A,B的限量,可以得到以下不等式
4x1 ≤16
4x2≤12
由于该工厂的目标是不超过所有资源限量的条件下,如何确定产量 x1,x2以得到最大的利润,若用 z表示利润,这时
z=2x1+3x2,综上所述,该问题可用数学模型表示为：
目标函数 max z=2x1+3x2
满足约束条件 x1+2x2≤8
4x1 ≤16
4x2≤12
x1,x2 ≥0
例 2
靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天 500万立方米，在两个化工厂之间也有一条流量为 200万立方米的支流。第一化工厂每天排放含有某种有害物质的工业污水 2万立方米，第二化工厂每天排放这种工业污水 1.4万立方米。
从第一化工厂排出的工业污水流到第二化工厂以前，有 20%可自然净化。根据环保要求，河流中工业污水应不大于 0.2％。这两个工厂都需要各自处理一部分工业污水。第一化工厂处理工业污水的成本是 1000元 /万立方米，第二化工厂处理工业污水的成本是 800元 /
万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小？
工厂 1（工业污水 2万 m3 ）治污成本
1000元 / m3
500万 m3
20%自然净化
200万 m3
工厂 2
（工业污水 1.4万 m3 ）
治污成本 800元 /m3
要求污水含量不大于 0.2%
解 这个问题可用数学模型描述 。 设两化工厂每天处理工业污水量
分别为 x1,x2万 m3.由于要求从第一化工厂到第二化工厂之间,河流中工业污水含量不大于 0.2%,由此可得近似关系式
（ 2-x1） /500≤2/1000
流经第二化工厂后，河流中的工业污水量不大于 0.2%，
这时有近似关系式
[0.8（ 2-x1） +(1.4-x2)]/700≤2/1000由于每个工厂每天处理的工业污水量不会大于每天的排放量，
故有
x1≤2; x2≤1.4
这问题的目标是要求两厂用于处理工业污水的总费用最小。
即 z=1000x1+800x2.综合上述，这个环保问题可用数学模型表示为：
目标函数 min z=1000x1+800x2
约束条件 x1≥1
0.8x1+x2≥1.6
x1≤2
x2≤1.4
x1,x2≥0
从以上两例可以看出,他们都是属于一类优化问题 。 它们的共同特征：
（ 1 ） 每一个问题都用一组决策变量
（ x1,x2,…,xn） 表示某一方案；这组决策变量的值就有代表一过具体方案 。 一般这些变量取值是非负的 。
（ 2） 存在一定的约束条件,这些约束条件可以用一组线性等式或线性不等式来表示 。
（ 3）都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为线性规划的数学模型 。 其一般形式为：
目标函数
max(min)z=c1x1+c2x2+…+c nxn （ 1.1）
约束条件
a11x1+a12x2+…+a 1nxn≤（ =,≥)b1
a21x1+a22x2+… +a2nxn≤（ =,≥） b2
……………………………… （ 1.2）
am1x1+am2x2+… +amnxn≤（ =,≥） bm
x1,x2,…,x n≥0 （ 1.3）
在线性规划的数学模型中，方程
（ 1.1）称为目标函数；
（ 1.2）、（ 1.3）称为约束条件；
（ 1.3）也称为一变量的非负约束条件。
1.2 图解法
图解法简单直观，有助于了解线性规划问题的有关概念及求解的基本原理。
但它只适用于两个自变量或可转化为两个自变量的问题 。
考虑例 1的数学模型：
max z=2x1+3x2
x1+2x2≤8
4x1 ≤16
4x2≤12
x1,x2≥0
解
由于 x1,x2≥0，因此满足约束条件的解（叫可行解）在第一象限。而每个约束条件都代表了一个半平面。因此可行解集是由几个半平面围成的一个凸多边形。
x2
4x1 =16
3 4x2=12
2
1 x1+2x2=8
0 1 2 3 4 x1
2x1+3x2=0
最优解为 （ 4,2）,最优值为 z=14.
上述问题的最优解是唯一的。
但对一般线性规划问题，求解结果还可能出现以下几种情况：
（ 1） 无穷多最优解（多重解）。
若将例 1中的目标函数变为 z=2x1+4x2,则
x2
4x1 =16
3 4x2=12
2
2x1+4x2=0 1 x1+2x2=8
0 1 2 3 4 x1
（ 2） 无界解例 max z=x1+x2 x2
-2x1+x2≤4 4
x1-x2≤2
x1,x2≥0
0 2 x1
x1+x2=0
(3)无可行解。
例 max z=2x1+3x2
x1+2x2≤8
4x1 ≤16
4x2≤12
-2x1+x2≥4
x1,x2≥0
1.3 线性规划问题的标准形式
由前可知，线性规划问题有各种不同的形式，为了研究线性规划问题的求解方法，
我们要把它们化成标准形式。
这里规定的标准形式为：
maxz=c1x1+c2x2+… +cnxn
s.t a11x1+a12x2+… +a1nxn=b1
a21x1+a22x2+… +a2nxn=b2
………………………
am1x1+am2x2+… +amnxn=bm
x1,x2,…,xn≥0
其中 bi≥0 (i=1,2,…,m)
§ 1、运筹学的简史
运筹学作为科学名字是出现在 20世纪 30
年代末。当时英、美对付德国的空袭，
雷达作为防空系统的一部分，从技术上是可行的，但实际运用时却并不好用。
为此一些科学家研究如何合理运用雷达等问题而开始进行一类新问题的研究。
因为它与研究技术问题不同，就称之为
,运用研究,（ Operational Research）。
这种,运用研究,就是,运筹学,。运筹学的英语是 Operation Research 。
§ 2、运筹学的性质和特点
运筹学是一门应用科学。至今还没有统一且确切的定义。提出以下几个定义来说明运筹学的性质和特点。一个是,为决策机构在对其控制下的业务活动进行决策时，提供以数量化为基础的科学方法。,它强调的是决策的 数量化 的 科学方法 。
运筹学的另一定义是：,运筹学是一门 应用科学,它广泛应用现有的 科学技术知识和数学方法,解决实际中提出的专门问题,为决策者选择最优决策提供定量依据 。,
它强调的是 应用性和数学方法,其目的是为决策者选择最优决策提供定量依据 。
§ 3、运筹学的工作步骤
运筹学在解决大量实际问题过程中形成了自己的工作步骤 。
（ 1） 提出和形成问题 。 即要弄清问题的目标,可能的约束,问题的可控变量以及有关参数,搜集有关资料 。
（ 2） 建立模型 。 即把问题中可控变量,参数和目标与约束之间的关系用一定的模型表示出来 。
（ 3） 求解 。 用各种手段 （ 主要是数学方法,也可用其它方法 ） 将模型求解 。 解可以是最优解,
次优解,满意解 。 复杂模型的求解需用计算机,
解的精度要求可由决策者提出 。
（ 4） 解的检验 。 首先检查求解步骤和程序有无错误,然后检查解是否反映现实问题 。
（ 5） 解的控制 。 通过控制解的变化过程决定对解是否要做一定的改变 。
（ 6） 解的实施 。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清解的用法，
在实施中可能产生的问题和修改。
以上过程应反复进行。
§ 4、运筹学的模型
运筹学在解决问题时,按研究对象不同可构造各种不同的模型 。 模型是研究者对客观现实经过思维抽象后用文字,图表,
符号,关系式以及实体模样描述所认识到的客观对象 。
模型有三种基本形式,（ 1） 形象模型,
（ 2） 模拟模型,（ 3） 符号或数学模型 。
建立数学模型的方法主要有以下五种：
（ 1） 直接分析法
（ 2） 类比法
（ 3） 数据分析法
（ 4） 试验分析法
（ 5） 想定 （ 构想 ） 法
§ 5、运筹学的应用
运筹学在早期的应用主要在军事领域 。 现已发展到广泛的领域：
（ 1） 市场销售
（ 2） 生产计划
（ 3） 库存管理
（ 4） 运输问题
（ 5） 财政和会计
（ 6） 人事管理
（ 7） 设备维修,更新和可靠性,项目选择和评价
（ 8） 工程的优化设计
（ 9） 计算机和信息系统
（ 10） 城市管理等等二、线性规划与目标规划
线性规划是运筹学的一个重要分支，自从 1947年
G.B.Dantzig提出了一般线性规划问题求解的方法 —
— 单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入。
1.1 问题的提出
在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、
物力、财力等资源，以便得到最好的经济效果。
线性规划主要解决两类问题：
1,资源有限,要求生产的产品 （ 或利润 ） 最多 。
2,任务 （ 或产品 ） 一定,要求消耗的资源 （ 或成本 ） 最少 。
某工厂在计划期内要安排生产 Ⅰ,
Ⅱ 两种产品,已知生产单位产品所需的设备台时及 A,B两种原材料的消耗,如表 1-1所示,问应该如何安排计划才能使该工厂获利最多？
例 1
表 1— 1
Ⅰ Ⅱ
设备原材料 A
原材料 B
1
4
0
2
0
4
8台时
16kg
12kg
单位产品利润（元）
2 3
解 设 x1,x2分别表示计划期内产品 Ⅰ 和产品 Ⅱ
的产量,因为设备的有效台时是 8,这是一个限制产量的条件,所以在确定产品 Ⅰ 和产品 Ⅱ 的产量时,要考虑不超过设备的有效台时数,即可用不等式表示为
x1+2x2≤8
同理,因原材料 A,B的限量,可以得到以下不等式
4x1 ≤16
4x2≤12
由于该工厂的目标是不超过所有资源限量的条件下,如何确定产量 x1,x2以得到最大的利润,若用 z表示利润,这时
z=2x1+3x2,综上所述,该问题可用数学模型表示为：
目标函数 max z=2x1+3x2
满足约束条件 x1+2x2≤8
4x1 ≤16
4x2≤12
x1,x2 ≥0
例 2
靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天 500万立方米，在两个化工厂之间也有一条流量为 200万立方米的支流。第一化工厂每天排放含有某种有害物质的工业污水 2万立方米，第二化工厂每天排放这种工业污水 1.4万立方米。
从第一化工厂排出的工业污水流到第二化工厂以前，有 20%可自然净化。根据环保要求，河流中工业污水应不大于 0.2％。这两个工厂都需要各自处理一部分工业污水。第一化工厂处理工业污水的成本是 1000元 /万立方米，第二化工厂处理工业污水的成本是 800元 /
万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小？
工厂 1（工业污水 2万 m3 ）治污成本
1000元 / m3
500万 m3
20%自然净化
200万 m3
工厂 2
（工业污水 1.4万 m3 ）
治污成本 800元 /m3
要求污水含量不大于 0.2%
解 这个问题可用数学模型描述 。 设两化工厂每天处理工业污水量
分别为 x1,x2万 m3.由于要求从第一化工厂到第二化工厂之间,河流中工业污水含量不大于 0.2%,由此可得近似关系式
（ 2-x1） /500≤2/1000
流经第二化工厂后，河流中的工业污水量不大于 0.2%，
这时有近似关系式
[0.8（ 2-x1） +(1.4-x2)]/700≤2/1000由于每个工厂每天处理的工业污水量不会大于每天的排放量，
故有
x1≤2; x2≤1.4
这问题的目标是要求两厂用于处理工业污水的总费用最小。
即 z=1000x1+800x2.综合上述，这个环保问题可用数学模型表示为：
目标函数 min z=1000x1+800x2
约束条件 x1≥1
0.8x1+x2≥1.6
x1≤2
x2≤1.4
x1,x2≥0
从以上两例可以看出,他们都是属于一类优化问题 。 它们的共同特征：
（ 1 ） 每一个问题都用一组决策变量
（ x1,x2,…,xn） 表示某一方案；这组决策变量的值就有代表一过具体方案 。 一般这些变量取值是非负的 。
（ 2） 存在一定的约束条件,这些约束条件可以用一组线性等式或线性不等式来表示 。
（ 3）都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为线性规划的数学模型 。 其一般形式为：
目标函数
max(min)z=c1x1+c2x2+…+c nxn （ 1.1）
约束条件
a11x1+a12x2+…+a 1nxn≤（ =,≥)b1
a21x1+a22x2+… +a2nxn≤（ =,≥） b2
……………………………… （ 1.2）
am1x1+am2x2+… +amnxn≤（ =,≥） bm
x1,x2,…,x n≥0 （ 1.3）
在线性规划的数学模型中，方程
（ 1.1）称为目标函数；
（ 1.2）、（ 1.3）称为约束条件；
（ 1.3）也称为一变量的非负约束条件。
1.2 图解法
图解法简单直观，有助于了解线性规划问题的有关概念及求解的基本原理。
但它只适用于两个自变量或可转化为两个自变量的问题 。
考虑例 1的数学模型：
max z=2x1+3x2
x1+2x2≤8
4x1 ≤16
4x2≤12
x1,x2≥0
解
由于 x1,x2≥0，因此满足约束条件的解（叫可行解）在第一象限。而每个约束条件都代表了一个半平面。因此可行解集是由几个半平面围成的一个凸多边形。
x2
4x1 =16
3 4x2=12
2
1 x1+2x2=8
0 1 2 3 4 x1
2x1+3x2=0
最优解为 （ 4,2）,最优值为 z=14.
上述问题的最优解是唯一的。
但对一般线性规划问题，求解结果还可能出现以下几种情况：
（ 1） 无穷多最优解（多重解）。
若将例 1中的目标函数变为 z=2x1+4x2,则
x2
4x1 =16
3 4x2=12
2
2x1+4x2=0 1 x1+2x2=8
0 1 2 3 4 x1
（ 2） 无界解例 max z=x1+x2 x2
-2x1+x2≤4 4
x1-x2≤2
x1,x2≥0
0 2 x1
x1+x2=0
(3)无可行解。
例 max z=2x1+3x2
x1+2x2≤8
4x1 ≤16
4x2≤12
-2x1+x2≥4
x1,x2≥0
1.3 线性规划问题的标准形式
由前可知，线性规划问题有各种不同的形式，为了研究线性规划问题的求解方法，
我们要把它们化成标准形式。
这里规定的标准形式为：
maxz=c1x1+c2x2+… +cnxn
s.t a11x1+a12x2+… +a1nxn=b1
a21x1+a22x2+… +a2nxn=b2
………………………
am1x1+am2x2+… +amnxn=bm
x1,x2,…,xn≥0
其中 bi≥0 (i=1,2,…,m)
