《运筹学原理与算法》与现行的其他运筹学教材相比,不涉及非线性规划,但增加了网络*优选址问题,扩充了网络规划和分配问题的内容。对一些经典运筹问题,补充了一些运筹理论,还补充了一些更加简便、实用的运筹算法。《运筹学原理与算法》的另一个特点是,把运筹方法的程序设计纳入教学内容中,详细、完整、规范地给出了各种运筹方法的算法步骤。
《运筹学原理与算法》是针对应用数学专业本科生编写的教材,也可作为经济管理、系统工程、计算机工程等专业的本科生教材,还可供相关专业研究生及科技工作者参考。

第1 章
线性规划
线性规划(linear programming)是运筹学中的一个重要分支,在现代工业、农业、商
业、交通运输、国防军事及经济管理等诸多领域都有着广泛、重要的应用.本章介绍的是
线性规划的基本概念、性质及在可行基或正则基已知的前提下求解线性规划的方法.
1.1 线性规划的模型及概念
一、线性规划及其模型
现实中有许多问题可以表示成,在满足一组线性等式或线性不等式的条件下,寻求
一个能够使某个线性函数的值*大(或*小)的一组变量的取值,这样的问题称为线性
规划问题.其中,被要求值达到*大(或*小)的函数,称为线性规划的目标函数;要求变
量满足的所有条件称为线性规划的约束条件.
例1.1.1 某厂生产产品A1 ,A2 ,… ,An 要用到原料B1 ,B2 ,… ,Bm.已知该厂每种
原料的拥有量、生产中每种单位产品要消耗的各种原料量,以及每种产品的单位价格,
见表1.1.1.
要研究的问题是:在现有条件下,要获得*高产值,每种产品应各生产多少?
设xj 为产品A j 的生产量( j = 1 ,2 ,… ,n) ,则目标函数为总产值
c1 x1 + c2 x2 + … + cn x n
约束条件为原料Bi的拥有量对各种产品A j 的生产量x j 的限制
ai1 x1 + ai 2 x2 + … + ai n xn ≤ bi ( i = 1 ,2 ,… ,m)
以及客观条件xj ≥ 0( j = 1 ,2 ,… ,n).因此,本题的数学模型为
max c1 x1 + c2 x2 + … + cn xn
s.t.
a1 1 x1 + a12 x2 + … + a1 n xn ≤ b1
a2 1 x1 + a22 x2 + … + a2 n xn ≤ b2
… …
am1 x1 + am2 x2 + … + amn xn ≤ bm
xj ≥ 0 ( j = 1 ,2 ,… ,n)
其中max 是英文maximum 的缩写,表示取*大;s.t.是英文subject to 的缩写,表示受
约束于….
例1.1.2 从A1 ,A2 ,… ,An 矿石中均可提炼出B1 ,B2 ,… ,Bm 物质.已知每种矿石
中可以提炼的各种物质量、提炼单位矿石的费用,以及需要提取的各种物质量,见表
1.1.2.
要研究的问题是:要使总的提炼费用*少,这n 种矿石应各选用多少?
设xj 为矿石A j 的选用量( j = 1 ,2 ,… ,n) ,则目标函数为总提炼费用
c1 x1 + c2 x2 + … + cn x n
约束条件为物质Bi的需要量对各种矿石A j 的选用量x j 的*低要求
ai1 x1 + ai 2 x2 + … + ai n xn ≥ bi ( i = 1 ,2 ,… ,m)
以及客观条件xj ≥ 0( j = 1 ,2 ,… ,n).因此,本题的数学模型为
min c1 x1 + c2 x2 + … + cn xn
s.t.
a11 x1 + a12 x2 + … + a1 n xn ≥ b1
a21 x1 + a22 x2 + … + a2 n xn ≥ b2
… …
am1 x1 + am2 x2 + … + amn xn ≥ bm
xj ≥ 0 ( j = 1 ,2 ,… ,n)
其中min 是英文minmum 的缩写,表示取*小;s.t.的含义同上.
例1.1.3 按照供需要求,要从发货点A1 ,A2 ,… ,Am 处将货物运往B1 ,B2 ,… ,Bn
各收货点.已知各发货点提供的货物量、各收货点的货物需求量、从各发货点到各收货
点的单位货物运费,见表1.1.3.
要研究的问题是:按照供需现状,如何安排各发货点到各收货点的货物量,才能使
总运费*少?
设xij 为A i 点运往B j 点的货物量( i = 1 ,2 ,… ,m ;j = 1 ,2 ,… ,n) ,则目标函数为总
运费Σ
m
i = 1 Σ
n
j = 1
cij x ij.但约束条件要分为以下三种情况:
(1) Σ
m
i = 1
ai = Σ
n
j = 1
bj 时,约束条件是:Ai 点运出的货物量应等于A i 点可提供的货物
量,Bj 点收到的货物量应等于B j 点的货物需求量,即Σ
n
j = 1
xij = ai i = 1 ,2 ,… ,m ;
Σ m
i = 1
xij = bj ( j = 1 ,2 ,… ,n) ;以及客观条件xij ≥ 0 i = 1 ,2 ,… ,m ;j = 1 ,2 ,… ,n.此
时,数学模型为
min Σ
m
i = 1 Σ
n
j = 1
cij x ij
s.t.
Σ n
j = 1
xij = ai ( i = 1 ,2 ,… ,m)
Σ m
i = 1
xij = bj ( j = 1 ,2 ,… ,n)
xij ≥ 0 ( i = 1 ,2 ,… ,m ;j = 1 ,2 ,… ,n)
(2) Σ
m
i = 1
ai ≤ Σ
n
j = 1
bj 时,约束条件是:Ai 点运出的货物量应等于A i 点可提供的货物
量,Bj 点收到的货物量应不超过B j 点的货物需求量,即Σ
n
j = 1
xij = ai i = 1 ,2 ,… ,m ,
Σ m
i = 1
xij ≤ bj ( j = 1 ,2 ,… ,n) ;以及客观条件xij ≥ 0 i = 1 ,2 ,… ,m ;j = 1 ,2 ,… ,n.此
时,数学模型为
min Σ
m
i = 1 Σ
n
j = 1
cij x ij
s.t.
Σ n
j = 1
xij = ai ( i = 1 ,2 ,… ,m)
Σ m
i = 1
xij ≤ bj ( j = 1 ,2 ,… ,n)
xij ≥ 0 ( i = 1 ,2 ,… ,m ;j = 1 ,2 ,… ,n)
(3) Σ
m
i = 1
ai ≥ Σ
n
j = 1
bj 时,约束条件是:Ai 点运出的货物量应不超过A i 点可提供的货
物量,Bj 点收到的货物量应等于B j 点的货物需求量,即Σ
n
j = 1
xij ≤ ai ( i = 1 ,2 ,… ,m) ;
Σ m
i = 1
xij = bj ( j = 1 ,2 ,… ,n) ;以及客观条件xij ≥ 0( i = 1 ,2 ,… ,m ;j = 1 ,2 ,… ,n).此时,
数学模型为
min Σ
m
i = 1 Σ
n
j = 1
cij x ij
s.t.
Σ n
j = 1
xij ≤ ai ( i = 1 ,2 ,… ,m)
Σ m
i = 1
xij = bj ( j = 1 ,2 ,… ,n)
xij ≥ 0 ( i = 1 ,2 ,… ,m ;j = 1 ,2 ,… ,n)
例1.1.4 某建筑工地因施工需要,要用12m 长的钢筋,截取5.5m 、3.5m 、2.5m
长的钢筋段各1600 、3500 、2800 根.试问:要使12m 长的钢筋用量*少,应如何下料?
分析 按不同的下料方法可以获得的不同结果,见表1.1.4.
设按第j 种方案用12m 的钢筋xj 根( j = 1 ,2 ,… ,7) ,则目标函数为12m 长的钢筋
总用量x1 + x2 + … + x7.约束条件为截出的5.5m 、3.5m 、2.5m 长的钢筋数量应满足的
需要量2 x1 + x2 + x3 ≥ 1600 ,x2 + 3 x4 + 2 x5 + x6 ≥ 3500 ,x2 + 2 x3 + 2 x5 + 3 x6 + 4 x7 ≥
2800 ,以及客观条件xj ≥ 0( j = 1 ,2 ,… ,7).因此,该问题的数学模型为
min x1 + x2 + … + x7
s.t.
2 x1 + x2 + x3 ≥ 1600
x2 + 3 x4 + 2 x5 + x6 ≥ 3500
x2 + 2 x3 + 2 x5 + 3 x6 + 4 x7 ≥ 2800
xj 为整数≥ 0 ( j = 1 ,2 ,… ,7)
例1.1.5 在每项工作只能由一人承担的要求下,安排m 个人去完成n 项工作.已
知第i 人完成第j 工作的用时为cij ( i = 1 ,2 ,… ,m ;j = 1 ,2 ,… ,n).研究:如何进行工作
分配,才能使完成所有工作的总用时*少?
设xij =
1 , 安排第i 人承担第j 项工作,
0 , 否则
( i = 1 ,2 ,… ,m ;j = 1 ,2 ,… ,n) ,yi 为第i
人承担的工作数( i = 1 ,2 ,… ,m) ,则目标函数为完成所有工作的总用时Σ
m
i = 1 Σ
n
j = 1
cij x ij.
约束条件是:每个人对各项工作是否承担应当与其承担的工作数相吻合,即Σ
n
j = 1
xij =
yi ( i = 1 ,2 ,… ,m) ;每项工作只能由一人承担Σ
m
i = 1
xij = 1( j = 1 ,2 ,… ,n) ;所有工作都必
须完成,即Σ
m
i = 1
yi = n ;以及xij ∈ {0 ,1} (i = 1 ,2 ,… ,m ;j = 1 ,2 ,… ,n) 和yi ∈ {0 ,1 ,… ,n}
( i = 1 ,2 ,… ,m).因此,该问题的数学模型为
min Σ
m
i = 1 Σ
n
j = 1
cij x ij
s.t.
Σ n
j = 1
xij = yi ( i = 1 ,2 ,… ,m)
Σ m
i = 1
xij = 1 ( j = 1 ,2 ,… ,n)
Σ m
i = 1
yi = n
xij ∈ {0 ,1} ,yi ∈ {0 ,1 ,… ,n} ( i = 1 ,2 ,… ,m ;j = 1 ,2 ,… ,n)
以上5 个问题的数学模型,目标函数和约束条件都是线性的,变量都是非负的,因
此,都属于线性规划问题.一般线性规划可分为以下三种形式:
(LP1)
min(或max) CT x
s.t.
A x = b
x ≥ 0
(LP2)
min(或max) CT x
s.t.
A x ≤ b
x ≥ 0
(LP3)
min(或max) CT x
s.t.
A x = b
Ax ≤ d
x ≥ 0
其中C = ( c1 ,c2 ,… ,cn )T ,x = ( x1 ,x2 ,… ,xn )T ,A = ( aij )m × n ,b = ( b1 ,b2 ,… ,bm )T ,A =
( aij )k × n ,d = ( d1 ,d2 ,… ,dk )T.
规定 (LP1)为线性规划的标准形.( LP2)和( LP3)不是标准形,但都可以化成标
准形.
定义1.1.1 如果通过加(或减)非负变量把线性规划的不等式约束变成等式约
束,则称这样的非负变量为该线性规划的松弛变量.
例如,引入松弛变量xn + 1 ,xn + 2 ,… ,xn + m ≥ 0 ,可以把例1.1.1 中给出的非标准形线
性规划转化成标准形线性规划:
max c1 x1 + c2 x2 + … + cn xn
s.t.
a11 x1 + a12 x2 + … + a1 n xn + xn + 1 = b1
a21 x1 + a22 x2 + … + a2 n xn + xn + 2 = b2
… …
am1 x1 + am2 x2 + … + amn x n + xn + m = bm
xj ≥ 0 ( j = 1 ,2 ,… ,n + m)
(1.1.1)
引入松弛变量xn + 1 ,xn + 2 ,… ,xn + m ≥ 0 ,可以把例1.1.2 给出的非标准形线性规划
转化成标准形线性规划:
min c1 x1 + c2 x2 + … + cn xn
s.t.
a11 x1 + a12 x2 + … + a1 n xn - xn + 1 = b1
a21 x1 + a22 x2 + … + a2 n xn - xn + 2 = b2
… …
am1 x1 + am2 x2 + … + amn x n - xn + m = bm
xj ≥ 0 ( j = 1 ,2 ,… ,n + m)
(1.1.2)
不难理解,任何非标准形线性规划都可以转化成标准形线性规划,因此,如何构建
标准形线性规划问题的解法,是构建一般性线性规划问题的解法的关键.
二、线性规划的几何意义
定义1.1.2 称集合x A x = b ,x ≥ 0 为线性规划( LP1)的可行域,该集合中的元
素称为线性规划(LP1)的可行解.
定义1.1.3 如果(LP1)的可行解能够使(LP1)的目标函数达到目标要求,则该可
行解称为(LP1)的*优解,对应的目标函数值称为(LP1)的*优值.
线性规划(LP2)和(LP3)的可行域、可行解、*优解及*优值的定义类似.
我们知道,二元一次方程ai1 x1 + ai2 x2 = bi 在x1 Ox2 直角坐标系中,图像是直线.三
元一次方程ai1 x1 + ai2 x2 + ai3 x3 = bi在Ox1 x2 x3 直角坐标系中,图像为平面.但是在n >
3 时,n 元一次方程ai1 x1 + ai2 x2 + … + ain xn = bi的图像是无法绘制的,为方便起见,称n
元一次方程的图像为超平面.因此,(LP1)的可行域是一系列超平面的公共点构成的集
合;(LP2)的可行域是一系列超平面围成的集合.特别是在n = 2 时,( LP2)的可行域是
由若干条直线围成的凸多边形.在n = 3 时,( LP2)的可行域是由若个平面围成的凸多
面体.

前言
第1章 线性规划
1.1 线性规划的模型及概念
一、线性规划及其模型
二、线性规划的几何意义
1.2 单纯形法
一、线性规划的单纯形表
二、可行基与基可行解的概念和性质
三、已知一个可行基的单纯形法
1.3 对偶单纯形法
一、正则基的概念和性质
二、已知一个正则基的对偶单纯形法
习题1
第2章 线性规划全过程算法
2.1 两阶段法
一、求可行基的方法
二、全过程算法一(两阶段法)
2.2 大M单纯形法
一、基本原理
二、全过程算法二(大M单纯形法)
2.3 大M对偶单纯形法
一、基本原理
二、全过程算法三(大M对偶单纯形法)
2.4 亚基迭代算法
一、概念
二、全过程算法四(亚基迭代算法)
习题2
第3章 线性规划的扩展问题
3.1 线性规划的对偶理论
一、对偶线性规划的概念
二、对偶线性规划之间的关系
3.2 线性规划的灵敏度问题
一、灵敏度的概念
二、目标函数中非*优基变量的系数cj的灵敏度
三、目标函数中*优基变量的系数cR(i)的灵敏度
四、约束条件中常数项bi的灵敏度
五、约束条件中非*优基变量的系数asub>ij<的灵敏度
3.3 目标线性规划
一、关于无*优解的多目标线性规划
二、关于无可行解的线性规划
习题3
第4章 整数线性规划
4.1 整数线性规划概念
4.2 一般整数线性规划的解法
一、一般整数线性规划与线性规划的关系
二、分支定界法
三、割平面法
4.3 0-1整数规划的解法
一、隐枚举法
二、特殊0-1整数规划的特殊解法
习题4
第5章 *小支撑树和*优路径问题
5.1 图与网络的概念
一、图的概念
二、子图的概念与几种特殊子图
5.2 *小支撑树问题及其算法
一、破圈法
二、避圈法
三、生长树法
5.3 *短路问题及其算法
一、*短路的概念
二、延伸路径的方法与特点
三、无负权值*短路问题的Dijkstra算法
四、含负权值无回路*短路问题的强Dijkstra算法
五、*短路问题的Floyd算法
5.4 *长路径问题及其算法
一、*长路的概念
二、*长路问题的仿强Dijkstra算法
三、*长路问题的仿Floyd算法
5.5 *大增流路径问题
一、基本概念
二、*大增流路径问题的仿Dijkstra算法
三、*大增流路径问题的仿Floyd算法
习题5
第6章 网络*优选址和网络*优计划问题
6.1 网络*优选址问题
一、网络*优选址的概念
二、单点*优选址问题的算法
三、多点*优选址问题的算法
四、半径有界的*优选址问题的算法
6.2 网络*优计划问题
一、基本概念
二、网络*优计划问题的箭线图
6.3 网络*优计划问题的算法
一、基于单箭线图的网络*优计划问题的算法
二、基于复箭线图的网络*优计划问题的算法
三、关键作业和关键路径的概念与应用
习题6
第7章 *大流和*小费用流问题
7.1 *大流问题及其算法
一、有向网络*大流问题及其数学模型
二、有向网络的割与割量的概念与性质
三、有向网络*大流的Ford-Fulkersen算法
四、无向网络*大流算法
7.2 *小费用流问题及其算法
一、*小费用流的概念
二、调费图与负回路的概念与性质
三、*小费用流问题的算法
习题7
第8章 运输问题
8.1 运输问题及其特征
一、运输问题的数学模型
二、运输问题的特征
8.2 运输问题的解法一(表上回路法)
一、平衡运输问题的基可行解获取方法
二、平衡运输问题的*优解获取方法
三、不平衡运输问题的解法
8.3 运输问题的解法二(仿*小费用流算法)
一、运输问题与*小费用流问题的关系
二、运输问题的仿*小费用流算法
8.4 运输问题的解法三(平衡负回路算法)
一、运输问题的检测矩阵与位置矩阵
二、运输问题的平衡负回路算法
习题8
第9章 分配问题
9.1 分配问题及其特征
一、分配问题及其数学模型
二、几种分配问题之间的关系
三、典则分配问题的性质
9.2 分配问题的解法一(匈牙利算法)
一、典则分配问题的解法
二、一般平衡分配问题的解法
三、不平衡分配问题的解法
9.3 分配问题的解法二(平衡负回路算法)
一、典则分配问题的平衡负回路算法
二、一般平衡分配问题的平衡负回路算法
习题9
第10章 动态规划
10.1 阶段性网络上*优路径的动态规划算法
一、*优路径的延伸算法的共同特点
二、阶段性网络上*优路径的动态规划算法
10.2 适合动态规划的问题与*优性原理
一、动态规划的概念
二、动态规划在一些线性约束规划上的应用
三、动态规划在一些案例中的应用
习题10
第11章 存储论
11.1 存储论的基本概念
11.2 确定性存储模型
一、不允许缺货,即刻到货模型
二、不允许缺货,到货需一定时间模型
三、允许缺货,即刻到货模型
四、允许缺货,生产需一定时间
五、价格有折扣的存储问题
11.3 随机性存储模型
一、需求是随机离散的存储模型
二、需求是连续型随机变量的存储模型
三、(s,S)型存储策略
习题11
第12章 对策论
12.1 对策论概述
一、对策论的基本要素
二、对策的例子
12.2 矩阵对策中的策略
一、矩阵对策的*优纯策略
二、矩阵对策的混合策略
12.3 矩阵对策的基本定理
一、基本定理
二、基本性质
12.4 矩阵对策的求解
一、图解法
二、线性规划法
三、方程组法
12.5 其他对策模型简介
一、二人无限零和对策
二、二人无限非零和对策
三、合作对策
四、多人非合作对策
习题12
第13章 排队论
13.1 随机服务系统与过程
一、排队系统的描述
二、排队系统的符号表示
三、排队系统的主要数量指标和记号
13.2 排队系统的常用分布
一、指数分布
二、泊松分布
三、爱尔朗分布
13.3 单服务台排队模型
一、标准的M/M/1模型
二、系统容量有限的M/M/1/N/∞模型
三、顾客源有限的M/M/1/∞/m模型
13.4 多服务台排队模型
13.5 排队系统的优化问题
一、M/M/1模型的*优平均服务率
二、M/M/c模型的*佳服务台数
习题13
参考文献

运筹学是20世纪30年代逐步发展起来的一门新兴学科,其涉及的内容具有共同的特征:在诸多因素制约下,为了实现既定的目标,如何通过数学方法作出*好的选择。这样的学科,无疑有着非常广泛的应用背景和重要的应用价值。《运筹学原理与算法》是编者在多年从事运筹学教学和研究的基础上,结合运筹学的*新发展,编写的面向应用数学专业的本科教材。本书共13章,第1~10章由郭强编写,第11~13章由孙浩编写。