第一章 绪论
§1 运筹学的释义和发展简史
§2 运筹学的特征和方法
§3 运筹学的分支
§4 运筹学应用与管理科学
运筹学（Operations Research)释义
运筹学是应用数学方法对经济、民政、国防等部门在内外环境的约束条件下合理分配安排人力、物力、财力等资源,使实际系统有效运行的技术科学。它可以用来预测发展趋势,制定行动规划或优选可行方案。
运筹学的产生和发展
运筹学产生于第二次世界大战，主要用于解决如何在与德军的对抗中最大限度地杀伤敌人，减少损失。
二战以后，运筹学得到了快速的发展，成立了国际运筹学联合会（IFORS），形成了许多分支.
运筹学有广泛应用
运筹学在军事，生产、决策、运输、存储、排队等经济管理领域有着广泛的应用。
§1 运筹学的释义和发展简史
运筹学的特征
（1）系统的整体观念，
（2）多学科交叉，
（3）模型方法应用
决策步骤：
1）分析、表述问题；
2）建立模型；
3）求解和优化方案；
4）测试模型，修正模型；
5）解的检验、灵敏性分析等；
6）实施方案；
§2 运筹学的特征和步骤
线性规划
非线性规划
动态规划
整数线性规划
图与网络分析
存储论
排队论
对策论
决策分析
§3 运筹学的分支
生产计划：生产作业的计划、日程表的编排、合理下料、
配料问题、物料管理等，追求利润最大化和成
本最小化
库存管理：多种物资库存量的管理，库存方式、库存量等
运输问题：确定最小成本的运输线路、物资的调拨、运输
工具的调度以及建厂地址的选择等
人事管理：对人员的需求和使用的预测，确定人员编制、
人员合理分配，建立人才评价体系等
市场营销：广告预算、媒介选择、定价、产品开发与销售
计划制定等
财务和会计：预测、贷款、成本分析、定价、证券管理、
现金管理等
§4 运筹学的应用和管理科学
由国际运筹与管理科学协会（INFORMS）和它的管理科学实践学会（College for the Practice of the Management Sciences）主持评奖的负有盛名的弗兰茨·厄德曼（Frany Edlman）奖，就是为奖励优秀的运筹学在管理中的应用的成就设立的，该奖每年举行一次，在对大量富有竞争力的入闱者进行艰苦的评审后，一般有六位优胜者获奖。关于这些获奖项目的文章都在第二年发表在著名刊物Interface的第一期上，下面列表就是发表在Interface期刊的一些获奖项目。
更优的服务
1-2/1993
安装统计销售预测和成品库存管理系统，改进客户服务
Merit青铜制品公司
第一年亿
1-2/2000
重组全球供应链，保持最小库存的同时满足客户需求
IBM
1亿
1-2/1994
进行上千个国内航线的飞机优化配置来最大化利润
Delta航空公司
1500万更多年收入
1-2/1998
制定最优铁路时刻表并调整铁路日运营量
法国国家铁路
2亿
1-2/1997
重新设计北美生产和分销系统以降低成本并加快了市场进入速度
宝洁公司
生产率提高50%以上
11/1975
第二部分
通过战略调整，缩短维修机器的反应时间和改进维修人员的生产率
施乐公司
380万
12/1981
控制成品库存（制定最优再订购点和订购量，确保安全库存）
标准品牌公司
亿 ，更多销售
1-2/1990
优化商业用户的电话销售中心选址
AT&T
4000万
1-2/1987
优化商业区和办公楼销售程序
荷马特发展公司
（Homart Development Co.）
7000万
1-2/1987
优化炼油程序及产品供应、配送及营销
Citgo石油
600万
1-2/1986
满足乘客需求前提下,以最低成本进行订票及安排机场工作班次
联合航空公司
每年节支
（美元）
Interface
期刊号
应用
组织
第二章 线性规划及单纯形法
§1 线性规划问题及模型
§2 图解法
§3 单纯形方法及大M法
§4 线性规划应用举例分析
§1 问题的提出
例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：
问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？
线性规划模型：
目标函数：Max z = 50 x1 + 100 x2
约束条件：. x1 + x2 ≤ 300
2 x1 + x2 ≤ 400
x2 ≤ 250
x1 , x2 ≥ 0
线性规划的组成要素：
目标函数 Max F 或 Min F
约束条件 . (subject to) 满足于
决策变量 用符号来表示可控制的因素
建模步骤
1.理解要解决的问题，了解解题的目标和条件；
2.定义决策变量（ x1 ，x2 ，… ，xn ），每一组值表示一个方案；
3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；
4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件
一般形式
目标函数： Max （Min） z = c1 x1 + c2 x2 + … + cn xn
约束条件： . a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1
a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2
…… ……
am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm
x1 ，x2 ，… ，xn ≥ 0
对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法。
例1.目标函数：
Max z = 50 x1 + 100 x2
约束条件：
.
x1 + x2 ≤ 300 (A)
2 x1 + x2 ≤ 400 (B)
x2 ≤ 250 (C)
x1 ≥ 0 (D)
x2 ≥ 0 (E)
§2 图 解 法
（1）画出线性规划问题的可行域，如图所示。
x1
x2
x2=0
x1=0
x2=250
x1+x2=300
2x1+x2=400
图1
（2）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。得到最优解： x1 = 50， x2 = 250， 最优目标值 z = 27500
x1
x2
z=20000=50x1+100x2
图2
z=27500=50x1+100x2
z=0=50x1+100x2
z=10000=50x1+100x2
C
B
A
D
E
例2 某公司由于生产需要，共需要A，B两种原料至少350
吨（A，B两种材料有一定替代性），其中A原料至少购进125
吨。但由于A，B两种原料的规格不同，各自所需的加工时间
也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需
要1小时，而公司总共有600个加工小时。又知道每吨A原料的
价格为2万元，每吨B原料的价格为3万元，试问在满足生产需
要的前提下，在公司加工能力的范围内，如何购买A，B两种
原料，使得购进成本最低？
解：目标函数： Min f = 2x1 + 3 x2
约束条件：
. x1 + x2 ≥ 350
x1 ≥ 125
2 x1 + x2 ≤ 600
x1 , x2 ≥ 0
采用图解法。如下图：得Q点坐标（250，100）为最优解。
100
200
300
400
500
600
100
200
300
400
600
500
x1 =125
x1+x2 =350
2x1+3x2 =800
2x1+3x2 =900
2x1+x2 =600
2x1+3x2 =1200
x1
x2
Q
重要结论：
如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；
无穷多个最优解。若将例1中的目标函数变为max z=50x1+50x2，则线段BC上的所有点都代表了最优解；
无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；
无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。
线性规划的标准化——引入松驰变量（含义是资源的剩余量）
例1 中引入 s1， s2， s3 模型化为
目标函数：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3
约束条件：. x1 + x2 + s1 = 300
2 x1 + x2 + s2 = 400
x2 + s3 = 250
x1 , x2 , s1 , s2 , s3 ≥ 0
对于最优解 x1 =50 x2 = 250 ， s1 = 0 s2 =50 s3 = 0
说明：生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有
可能的设备台时数及原料B，但对原料A则还剩余50千克。
线性规划的标准化
线性规划标准形式
目标函数： Max z = c1 x1 + c2 x2 + … + cn xn
约束条件： . a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1 ，x2 ，… ，xn ≥ 0，bi ≥0
可以看出，线性规划的标准形式有如下四个特
点：
目标最大化；
约束为等式；
决策变量均非负；
右端项非负。
对于各种非标准形式的线性规划问题，我们总可
以通过以下变换，将其转化为标准形式:
1.极小化目标函数的问题：
设目标函数为
Min f = c1x1 + c2x2 + … + cnxn
(可以)令 z ＝ -f ，
则该极小化问题与下面的极大化问题有相同的最优解，
即 Max z = - c1x1 - c2x2 - … - cnxn
但必须注意，尽管以上两个问题的最优解相同，但它们
最优解的目标函数值却相差一个符号，即
Min f ＝ - Max z
2、约束条件不是等式的问题：
设约束条件为
ai1 x1+ai2 x2+ … +ain xn ≤ bi
可以引进一个新的变量s ，使它等于约束右边与左
边之差
s=bi–(ai1 x1 + ai2 x2 + … + ain xn )
显然，s 也具有非负约束，即s≥0，
这时新的约束条件成为
ai1 x1+ai2 x2+ … +ain xn+s = bi
当约束条件为
ai1 x1+ai2 x2+ … +ain xn ≥ bi 时，
类似地令
s=(ai1 x1+ai2 x2+ … +ain xn)- bi
显然，s 也具有非负约束，即s≥0，这时新的约
束条件成为
ai1 x1+ai2 x2+ … +ain xn-s = bi
为了使约束由不等式成为等式而引进的变量s,当
不等式为“小于等于”时称为“松弛变量”；当不等式
为“大于等于”时称为“剩余变量”。如果原问题中有
若干个非等式约束，则将其转化为标准形式时，必须
对各个约束引进不同的松弛变量。
3.右端项有负值的问题：
在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi<0，则把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2- … -ain xn = -bi。
例：将以下线性规划问题转化为标准形式
Min f = 2 x1 -3x2 + 4 x3
. 3 x1 + 4x2 - 5 x3 ≤6
2 x1 + x3 ≥8
x1 + x2 + x3 = -9
x1 , x2 , x3 ≥ 0
解：首先,将目标函数转换成极大化：
令 z= -f = -2x1+3x2-4x3
其次考虑约束，有2个不等式约束，引进松弛变量
x4，x5 ≥0。
第三个约束条件的右端值为负，在等式两边同时乘-1。
通过以上变换，可以得到以下标准形式的线性规划问题：
Max z = - 2x1 + 3 x2 - 4x3
. 3x1+4x2-5x3 +x4 = 6
2x1 +x3 -x5= 8
-x1 -x2 -x3 = 9
x1 ,x2 ,x3 ,x4 ,x5 ≥ 0
在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没
有非负约束时，可以令
xj = xj’- xj”
其中
xj’≥0，xj”≥0
即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号
取决于xj’和xj”的大小。
§3 单纯形方法及大M法
单纯形法的基本思路和原理
单纯形法的表格形式
求目标函数值最小的线性规划的问题的
单纯形表解法
几种特殊情况
1 单纯形法的基本思路和原理
单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优
解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此
点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的
解，或者能判断出线性规划问题无最优解为止。
通过第二章例1的求解来介绍单纯形法:
在加上松弛变量之后我们可得到标准型如下：
目标函数： max 50x1+100x2
约束条件：x1+x2+s1=300，
2x1+x2+s2=400，
x2+s3=250.
xj≥0 （j=1，2）,sj≥0 （j=1，2,3）
它的系数矩阵 ,
其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变
量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的
基本概念。
基： 已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非
奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。
基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。
非基向量：在A中除了基B之外的一列则称之为基B的非基向量。
基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。
非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n－m个。
由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个
基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一
的解了，这个解我们称之为线性规划的基本解。
在此例中我们不妨找到了 为A的一个基，令这个基的
非基变量x１，s2为零。这时约束方程就变为基变量的约束方程：
x2+s1＝300，
x2=400，
x2+s3=250.
求解得到此线性规划的一个基本解：
x1=0，x2=400，s1=－100，s2=0，s3=－150
由于在这个基本解中s1=－100，s3=－150，不满足该线性规划s1≥0，
s3≥0的约束条件，显然不是此线性规划的可行解，一个基本解可以是
可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解
是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行
解，并把这样的基叫做可行基。
一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解
所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行
基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个
基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中
要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位
矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如，
那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向
量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj或等
于零。
在本例题中我们就找到了一个基是单位矩阵。
在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各
列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行
解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行
基，我们将构造初始可行基，具体做法在以后详细讲述。
二、 最优性检验
所谓最优性检验就是判断已求得的基本可行解是否是最优解。
1. 最优性检验的依据——检验数σj
一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求
只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可
以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基
变量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系
数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变
量xi的检验数记为σi。显然所有基变量的检验数必为零。在本例题中目标
函数为50x1+100x2。由于初始可行解中x1，x2为非基变量，所以此目标函
数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知
σ1=50，σ2=100，σ3=0，σ4=0，σ5=0。
2.最优解判别定理
对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数 ≤0，则这个基本可行解是最优解。下面我们用通俗的说法来解释最优解判别定理。设用非基变量表示的目标函数为如下形式
由于所有的xj的取值范围为大于等于零，当所有的 都小
于等于零时，可知 是一个小于等于零的数，要使z
的值最大，显然 只有为零。我们把这些xj取为非基
变量(即令这些xj的值为零)，所求得的基本可行解就使目标函数值最大为z0。
**对于求目标函数最小值的情况，只需把 ≤0改为 ≥0
三、 基变换
通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进
行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得
到一个新的可行基，使得求解得到的新的基本可行解，其目标函数值更优。
为了换基就要确定换入变量与换出变量。
1. 入基变量的确定
从最优解判别定理知道，当某个σj＞0时，非基变量xj变为基变量不取
零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基
变量中去（称之为入基变量）。若有两个以上的σj＞0，则为了使目标函数
增加得更大些，一般选其中的σj最大者的非基变量为入基变量，在本例题
中σ2=100是检验数中最大的正数，故选x2为入基变量。
2. 出基变量的确定
在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确
定一个出基变量，也就是确定哪一个基变量变成非基变量呢？
如果把s3作为出基变量，则新的基变量为x2，s1，s2，因为非基变量x1=s3=0，
我们也可以从下式：
x2 +s1=300，
x2+s2=400，
x2=250，
求出基本解：x1=0，x2=250，s1=50，s2=150，s3=0。因为此解满足非负
条件，是基本可行解，故s3可以确定为出基变量。
能否在求出基本解以前来确定出基变量呢？
以下就来看在找出了初始基本可行解和确定了入基变量之后，怎么样的
基变量可以确定为出基变量呢？或者说出基变量要具有什么条件呢？
我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方
程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所
在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变
换中可以确保新得到的bj值都大于等于零。
在本例题中约束方程为
在第二步中已经知道x2为入基变量，我们把各约束方程中x2的为正的系数除
对应的常量，得
其中 的值最小，所以可以知道在原基变量中系数向量为
的基变量s3为出基变量，这样可知x2，s1，s2为基变量，x1，s3为非基变量。
令非基变量为零，得
x2+s1=300,
x2+s2=400,
x2=250.
求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150.
这时目标函数值为
50x1+100x2=50×0+100×250=25000。
显然比初始基本可行解x1=0,x2=0,s1=300,s3=250时的目标函数值为0要好
得多。
下面我们再进行检验其最优性，如果不是最优解还要继续进行基变
换，直至找到最优解，或者能够判断出线性规划无最优解为止。
在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验
数 的表达式。
可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m
列是单位矩阵）：
以下用 表示基变量，用
表示非基变量。
把第i个约束方程移项，就可以用非基变量来表示基变量xi，
把以上的表达式带入目标函数，就有
其中：
上面假设x1,x2,…xm是基变量，即第i行约束方程的基变量正好是xi，而
经过迭代后，基将发生变化，计算zj的式子也会发生变化。如果迭代后的
第i行约束方程中的基变量为xBi，与xBi相应的目标函数系数为cBi，系数列
向量为 则
其中，(cB)是由第1列第m行各约束方程中的基变量相应的目标函数依
次组成的有序行向量。
单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、
迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，
而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来
求解第二章的例1。
max 50x1+100x2+0·s1+0·s2+0·s3.
x1+x2+s1=300，
2x1+x2+s2=400，
x2+s3=250，
x1, x2, s1, s2, s3≥0. 把上面的数据填入如下的单纯形表格
按照线性规划模型在表中填入相对应的值，如上表所示；
在上表中有一个m*m的单位矩阵，对应的基变量为s1,s2,s3；
在zj行中填入第j列与cB列中对应的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位数填入0；
在 行中填入cj-zj所得的值，如 ；
z表示把初始基本可行解代入目标函数求得的目标函数值，即b列*cB列；
初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0;
由于250/1最小，因此确定s3为出基变量；
由于 ，因此确定x2为入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是a32=1，在表中画圈以示区别。
50 100 0 0 0
300/1
400/1
250/1
比值
Bi/ai2
z=0
300
400
250
b
0
0
0
cB
50 100 0 0 0
1 1 1 0 0
2 1 0 1 0
0 1 0 0 1
x1 x2 s3 s4 s5
s1
s2
s3
基变量
0
迭代次数
以下进行第一次迭代，其变量为x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得x2的系数向量p2变换成单位向量，由于主元在p2的第3 分量上，所以这个单位向量是
也就是主元素变成1。这样我们又得到的第1次迭代的单纯表如下所示。
在上表中第3个基变量s1已被x2代替，故基变量列中的第3个基变量应变为x2。由于第0次迭代表中的主元a32已经为1，因此第3行不变。为了使第1行的a12为0，只需把第3行*(-1)加到第1行即可。同样可以求得第2行。
求得第1次迭代的基本可行解为s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.
50 100 0 0 0
50/1
150/2
—
比值
bi/aij
25000
50
150
250
b
0
0
100
cB
50 0 0 0 -100
1 0 1 0 -1
2 0 0 1 -1
0 1 0 0 1
x1 x2 s3 s4 s5
s1
s2
x2
基变量
1
迭代次数
从上表可以看出，第一次迭代的 ，因此不是最优解。设x1为入基变量，从此值可知b1/a11=50为最小正数，因此，s1为出基变量，a11为主元，继续迭代如下表所示。
从上表中可知第二次迭代得到的基本可行解为x1=50,x2=250,s1=0,s2=50, s3=0,这时z=27500。
由于检验数都<0，因此所求得的基本可行解为最优解， z=27500为最优目标函数值。
实际上，我们可以连续地使用一个单纯形表，不必一次迭代重画一个表头。
50 100 0 0 0
比值
bi/aij
27500
50
50
250
b
50
0
100
cB
0 0 -50 0 -50
1 0 1 0 -1
0 0 -2 1 1
0 1 0 0 1
x1 x2 s3 s4 s5
x1
s2
x2
基变量
2
迭代次数
大M法
以例2来讲解如何用单纯形表的方法求解目标函数值最小的线性规划问题。
目标函数：
约束条件：
加入松弛变量和剩余变量变为标准型，得到新的约束条件如下：
至于目标函数，在标准型中并不一定要求求最大值或最小值，但是为
了使单纯形表解法有一个统一的解法，我们把所有求目标函数最小值的问
题化成求目标函数最大值的问题。具体做法只要把目标函数乘以（－1）。
要注意到人工变量是与松弛、剩余变量不同的。松弛变量、剩余变量它
们可以取零值，也可以取正值，而人工变量只能取零值。一旦人工变量取
正值，那么有人工变量的约束方程和原始的约束方程就不等价了，这样所
求得的解就不是原线性规划的解了。为了竭尽全力地要求人工变量为零，
我们规定人工变量在目标函数中的系数为－M，这里M为任意大的数。这样
只要人工变量M＞0，所求的目标函数最大值就是一个任意小的数。这样
为了使目标函数实现最大就必须把人工变量从基变量中换出。如果一直到
最后，人工变量仍不能从基变量中换出，也就是说人工变量仍不为零，则
该问题无可行解。
此例的数学模型如下所示：
目标函数： max z=－2x1－3x2－Ma1－Ma2.
约束条件：x1+x2－s1+a1=350，
x1－s2+a2=125，
2x1+x2+s3=600，
x1，x2，s1，s2，s3，a1，a2≥0.
像这样，为了构造初始可行基得到初始可行解，把人工变量“强行”地
加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最大值的目标函数里的系数为－M，这个方法叫做大M法，M叫做罚因子。
下面我们就用大M法来求解此题:
-M
-2
0
-50M-600
-2 -1/2M-1 M 0 1/2M-1 -M 0
0 1/2M-2 -M 0 - 1/2M+1 0 -M
zj
-M
-2
0
-225M-250
-2 -M M -M+2 0 -M -M-2
0 -3+M -M M-2 0 0 2-2M
zj
50/1/2
300/1/2
175/1/2
50
300
175
0 1/2 -1 0 -1/2 1 0
1 1/2 0 0 1/2 0 0
0 1/2 0 1 1/2 0 -1
a1
x1
s2
2
-2 -3 0 0 0 -M -M
-M
-M
0
cB
-475M
-2M -M M M 0 -M -M
-2+2M -3+M -M -M 0 0 0
zj
225
-----
350/2
225
125
350
0 1 -1 0 0 1 -1
1 0 0 -1 0 0 1
0 1 0 2 1 0 -2
a1
x2
s3
1
350
125
600
b
350/1
125/1
600/2
比值
1 1 -1 0 0 1 0
1 0 0 -1 0 0 1
2 1 0 0 1 0 0
x1 x2 s1 s2 s3 a1 a2
a1
a2
a3
基变量
0
迭代次数
从上表中可知检验数都小于零。已求得最优解为： x1=250,x2=100,s1=0, s2=125,s3=0,a1=0,a2=0，其最优值为
f=-z=-(-800)=800。
-2 -3 0 0 0 -M -M
比值
-800
100
250
125
b
-3
-2
0
cB
-2 -3 4 0 1 -4 0
0 0 -4 0 -1 -M+4 -M
0 1 -2 0 -1 2 0
1 0 1 0 1 -1 0
0 0 1 1 1 -1 -1
x1 x2 s1 s2 s3 a1 a2
zj
x2
x1
s2
基变量
3
迭代次数
二、两阶段法
两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划划分两阶段求解，仍以上面的例题为例，阐述两阶段法的求解过程。
第一阶段：要判断原线性规划是否有基可行解，方法是先求解下列线性规划问题：
目标函数：
约束条件：
注意：此线性规划的约束条件与原线性规划一样，而目标函数是求人工变量的相反数之和的最大值。如果此值大于零，则不存在使所有人工变量都为零的可行解，停止计算。如果此值为零，即说明存在一个可行解，使得所有的人工变量都为零。
第二阶段：将第一阶段的最终单纯形表中的人工变量取消，将目标函数换成原问题的目标函数，把此可行解作为初始可行解进行计算。
0
0
0
0
0 0 0 0 0 0 0
0 0 0 0 0 -1 -1
zj
-1
0
0
225
0 -1 1 -1 0 -1 1
0 1 -1 1 0 0 2
zj
225
125
125
0 1 -1 1 0 1 0
1 0 0 -1 0 0 1
0 0 1 1 1 -1 -1
x2
x1
s3
2
-2 -3 0 0 0 -1 -1
-1
-1
0
cB
-470
-2 -1 1 1 0 -1 -1
-2 1 -1 -1 0 0 0
zj
225
125
350
0 1 -1 1 0 1 -1
1 0 0 -1 0 0 1
0 1 0 2 1 0 -2
a1
x1
s3
1
350
125
600
b
350/1
125/1
600/2
比值
1 1 -1 0 0 1 0
1 0 0 -1 0 0 1
2 1 0 0 1 0 0
x1 x2 s1 s2 s3 a1 a2
a1
a2
s3
基变量
0
迭代次数
-3
-2
0
-800
-2 -3 4 0 1
0 0 -4 0 -1
zj
-2 -3 0 0 0
-3
-2
0
cB
-925
-2 -3 3 -1 0
0 0 -3 1 0
zj
100
250
125
0 1 -2 0 -1
1 0 1 0 1
0 0 1 1 1
x2
x1
s2
1
225
125
125
b
225/1
125/2
比值
0 1 -1 1 0
1 0 0 -1 0
0 1 0 2 1
x1 x2 s1 s2 s3
x2
x1
s3
基变量
0
迭代次数
从表中可知其基本可行解x1=250,x2=100,s1=0,s2=125,s3=0是本例的最优解，其最优值为z=-(-800)=800。
一、无可行解
例1、用单纯形表求解下列线性规划问题
解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：
填入单纯形表计算得：
zj
cj-zj
x2
x1
a1
zj
cj-zj
x2
s2
a1
zj
cj-zj
s1
s2
a1
基变量
780-4M
20 30 3+M/10 11+7M/10 M -M
0 0 -3-M/10 -11-7M/10 -M 0
6
30
4
0 1 1/10 -3/10 0 0
1 0 0 1 0 0
0 0 -1/10 -7/10 -1 1
30
20
-M
2
450-25M
9-7/10M 30 3+M/10 0 M -M
11+7/10M 0 -3-M/10 0 -M 0
15/(3/10)
30/1
25/(7/10)
15
30
25
3/10 1 1/10 0 0 0
1 0 0 1 0 0
7/10 0 -1/10 0 -1 1
30
0
-M
1
-40M
-M -M 0 0 M -M
20+M 30+M 0 0 -M 0
150/10
—
40/1
150
30
40
3 10 1 0 0 0
1 0 0 1 0 0
1 1 0 0 -1 1
0
0
-M
0
20 30 0 0 0 -M
比值
b
x1 x2 s1 s2 s3 a1
CB
迭代次数
从第二次迭代的检验数都小于零来看，可知第2次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为780-4M。我们把最优解x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个约束方程得x1+x2-0+4=40,即有：x1+x2=36≤40.
并不满足原来的约束条件3，可知原线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。
像这样只要求线性规划的最优解里有人工变量大于零，则此线性规划无可行解。
二、无界解
在求目标函数最大值的问题中，所谓无
界解是指在约束条件下目标函数值可以取
任意的大。下面我们用单纯形表来求第二
章中的例子。
例2、用单纯形表求解下面线性
规划问题。
zj
cj-zj
x1
s2
zj
cj-zj
s1
s2
基变量
1
1 -1 1 0
0 2 -1 0
1
9
1 -1 1 0 0 -1 3 1
1
0
1
0
0 0 0 0 1 1 0 0
1
—
1
6
1 -1 1 0
-3 2 0 1
0
0
0
1 1 0 0
比值
b
x1 x2 s1 s2
CB
迭代次数
填入单纯形表计算得：
解：在上述问题的约束条件中加入松驰变量，得标准型如下：
从单纯形表中，从第一次迭代的检验数等于2，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进行第2次迭代，那么就选x2为入基变量，但是在选择出基变量时遇到了问题： =-1, =-1,找不到大于零的 来确定出基变量。事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从1次迭代的单纯形表中，得到约束方程：
移项可得：
由于M可以是任意大的正数，可知此目标函数值无界。
上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：在某次迭代的单纯形表中，如果存在着一个大于零的检验数 ，并且该列的系数向量的每个元素aij(i=1,2,…,m)都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错误所引起的。
三、无穷多最优解
例3、用单纯形法表求解下面的线性规划问题。
解：此题我们用图解法已求了解，现在用单纯形表来求解。
填入单纯形表计算得：
zj
cj-zj
x1
s2
x2
zj
cj-zj
s1
s2
x2
zj
cj-zj
s1
s2
s3
基变量
15000
50 50 50 0 0
0 0 -50 0 0
—
50/1
250/1
50
50
250
1 0 1 0 -1
0 0 -2 1 1
0 1 0 0 1
50
0
50
2
12500
0 50 0 0 50
50 0 0 0 0
50/1
150/2
—
50
150
250
1 0 1 0 -1
2 0 0 1 -1
0 1 0 0 1
0
0
50
1
0
0 0 0 0 0
50 50 0 0 0
300/1
400/1
250/1
300
400
250
1 1 1 0 0
2 1 0 1 0
0 1 0 0 1
0
0
0
0
50 50 0 0 0
比值
b
x1 x2 s1 s2 s3
CB
迭代次数
这样我们求得了最优解为x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的最优值为15000。这个最优解是否是惟一的呢？由于在第2次迭代的检验数中除了基变量的检验数 等于零外，非基变量s3的检验数也等于零，这样我们可以断定此线性规划问题有无穷多最优解。不妨我们把检验数也为零的非基变量选为入基变量进行第3次迭代。可求得另一个基本可行解，如下表所示：
cj-zj
x1
s3
x2
基变量
15000
0 0 -50 0 0
100
50
200
1 0 -1 1 0
0 0 -2 1 1
0 1 2 -1 0
50
0
50
3
50 50 0 0 0
b
x1 x2 s1 s2 s3
CB
迭代次数
从检验数可知此基本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最优解，从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解，不妨用向量Z1，Z2表示上述两个最优解即Z1 =（50，250，0，50，0）， Z2 =（100，200，0，0，50），则此线段上的任一点，即可表示为αZ1+（1- α ）Z2，其中0≤α≤1。如图5-1所示：
100
200
300
100
200
300
250
Z1
Z2
图5-1
在一个已得到最优解的单纯形表中，如果存在一个非基变量的检验数 为零，为什么我们把这个非基变量xs作为入基变量进行迭代时，得到的最优解仍为最优解呢？
不妨设出基变量为xk，则原最优单纯形表可表示如下：
通过迭代，我们得到了新的单纯形表，其中xs为基变量了，而xk为非基变量了。我们可得到下表。
又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可证明其他的非基变量的检验数不变，仍然小于零，这样就证明了新得到的基本可行解仍然是最优解。
这样我们得到了判断线性规划有无穷多最优解的方法：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解。
四、退化问题
在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。
例4.用单纯形表，求解下列线性规划问题。
解：加上松驰变量s1,s2,s3化为标准形式后，
填入单纯形表计算得：
zj
cj-zj
x1
x2
s3
zj
cj-zj
x1
s2
s3
zj
cj-zj
s1
s2
s3
基
变
量
4
2 0 1 0 1 0
0 0 1/2 0 -1 0
2/(1/2)
0/(1/2)
—
2
0
1
1 0 1/2 0 1/2 0
0 1 1/2 - 1 1/2 0
0 0 0 1 -1 1
2
0
0
2
4
2 -2 0 0 0 0
0 2 3/2 -2 0 0
—
0/2
1/2
2
0
1
1 -1 0 1 0 0
0 2 1 -2 1 0
0 2 1 -1 0 1
2
0
0
1
0
0 0 0 0 0 0
2 0 3/2 0 0 0
2/1
4/2
3/1
2
4
3
1 -1 0 1 0 0
2 0 1 0 1 0
1 1 1 0 0 1
0
0
0
0
2 0 3/2 0 0 0
比值
b
x1 x2 x3 s1 s2 s3
CB
迭代次数
在以上的计算中可以看出在0次迭代中，由于比值b1/a11=b2/a21=2为最小比值，导致在第1次迭代中出现了退化，基变量s2=0。又由于在第1次迭代出现了退化，基变量s2=0，又导致第2次迭代所取得的目标函数值并没有得到改善，仍然与第1次迭代的一样都等于4。像这样继续迭代而得不到目标函数的改善，当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。像本题继续计算如下：
2/1
—
1/1
2
0
1
1 -1 0 1 0 0
0 2 1 - 2 1 0
0 0 0 1 -1 1
2
3/2
0
x1
x3
s3
3
4
2 1 3/2 -1 3/2 0
0 -1 0 1 -3/2 0
zj
cj-zj
zj
cj-zj
x1
x3
s1
基
变
量
5
2 1 3/2 0 1/2 1
0 -1 0 0 -1/2 -1
2
2
1
1 -1 0 0 1 -1
0 2 1 0 -1 2
0 0 0 1 -1 1
2
3/2
0
4
2 0 3/2 0 0 0
比值
b
x1 x2 x3 s1 s2 s3
CB
迭代次数
得到了最优解x1=1，x2=0，x3=2，s1=1，s2=0，s3=0，其最优值为5。
但有时候当出现退化时，即使存在最优解，而迭代过程总是重复解的
某一部分迭代过程，出现了计算过程的循环，目标函数值总是不变，永远
达不到最优解。
下面一个是由给出的循环的例子。
例5
目标函数 ：min f =－（3/4）x4+20x5－（1／2）x6+6x7.
约束条件：x1+（1／4）x4－8x5－x6+9x7=0，
x2+（1／2）x4－12x5－（1／2）x6+3x7=0，
x3+x6=1，
x1，x2，x3，x4，x5，x6，x7≥0.
这个例题的确存在最优解，但用一般单纯形表法，经过6次迭代后得到的单纯形表与第0次单纯形表一样，而目标函数都是零，没有任何变化，这样迭代下去，永远达不到最优解。为了避免这种现象，我们介绍勃兰特法则。
首先我们把松弛变量（剩余变量）、人工变量都用xj表示，一般松弛变量（剩余变量）的下标号列在决策变量之后，人工变量的下标号列在松弛变量（剩余变量）之后，在计算中，遵守以下两个规则：
（1）在所有检验数大于零的非基变量中，选一个下标最小的作为入基变量。
（2）在存在两个和两个以上最小比值时，选一个下标最小的基变量为出基变量。
这样就一定能避免出现循环。
§4 线性规划应用举例分析
例1．某昼夜服务的公交线路每天各时间段内所需司机
和乘务人员数如下：
设司机和乘务人员分别在各时间段一开始时上班，并
连续工作八小时，问该公交线路怎样安排司机和乘务人员，
既能满足工作需要，又配备最少司机和乘务人员?
解：设 xi 表示第i班次时开始上班的司机和乘务人员数,
这样我们建立如下的数学模型。
目标函数： Min x1 + x2 + x3 + x4 + x5 + x6
约束条件：. x1 + x6 ≥ 60
x1 + x2 ≥ 70
x2 + x3 ≥ 60
x3 + x4 ≥ 50
x4 + x5 ≥ 20
x5 + x6 ≥ 30
x1,x2,x3,x4,x5,x6 ≥ 0
例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？
解：设 xi ( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。
目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 + x7
约束条件：. x1 + x2 + x3 + x4 + x5 ≥ 28
x2 + x3 + x4 + x5 + x6 ≥ 15
x3 + x4 + x5 + x6 + x7 ≥ 24
x4 + x5 + x6 + x7 + x1 ≥ 25
x5 + x6 + x7 + x1 + x2 ≥ 19
x6 + x7 + x1 + x2 + x3 ≥ 31
x7 + x1 + x2 + x3 + x4 ≥ 28
x1,x2,x3,x4,x5,x6,x7 ≥ 0
例3．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？
解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种
产品的件数，x4,x5 分别为由外协铸造再由本公司加工和装配的甲、乙两
种产品的件数。
求 xi 的利润：利润 = 售价 - 各成本之和
产品甲全部自制的利润 =23-(3+2+3)=15
产品甲铸造外协，其余自制的利润 =23-(5+2+3)=13
产品乙全部自制的利润 =18-(5+1+2)=10
产品乙铸造外协，其余自制的利润 =18-(6+1+2)=9
产品丙的利润 =16-(4+3+2)=7
可得到 xi （i = 1,2,3,4,5） 的利润分别为 15、10、7、13、9
元。
通过以上分析,可建立如下的数学模型:
目标函数： Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5
约束条件： 5x1 + 10x2 + 7x3 ≤ 8000
6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000
3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000
x1,x2,x3,x4,x5 ≥ 0
例4．永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两
道工序加工。设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、B2、B3能完成 B 工序。Ⅰ可在A、B的任何规格的设备上加工；Ⅱ 可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？
解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数量。建立如下的数学模型:
. 5x111 + 10x211 ≤ 6000 （ 设备 A1 ）
7x112 + 9x212 + 12x312 ≤ 10000 （ 设备 A2 ）
6x121 + 8x221 ≤ 4000 （ 设备 B1 ）
4x122 + 11x322 ≤ 7000 （ 设备 B2 ）
7x123 ≤ 4000 （ 设备 B3 ）
x111+ x112- x121- x122- x123 = 0 （Ⅰ产品在A、B工序加工的数量相等）
x211+ x212- x221 = 0 （Ⅱ产品在A、B工序加工的数量相等）
x312 - x322 = 0 （Ⅲ产品在A、B工序加工的数量相等）
xijk ≥ 0 , i = 1,2,3; j = 1,2; k = 1,2,3
目标函数为计算利润最大化，利润的计算公式为：
利润 = [（销售单价 - 原料单价）* 产品件数]之和 -（每台时的设备费用*设备实际使用的总台时数）之和。
这样得到目标函数：
Max()(x111+x112)+()x221+()x312 –
300/6000(5x111+10x211)-321/10000(7x112+9x212+12x312)-
250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).
经整理可得：
++++
例5．某工厂要做100套钢架，每套用长为 m, m, m的圆钢各
一根。已知原料每根长 m，问：应如何下料，可使所用原料最省？
解： 共可设计下列5 种下料方案，见下表
设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的原材料根数。这样我们建立如下的数学模型。
目标函数： Min x1 + x2 + x3 + x4 + x5
约束条件： . x1 + 2x2 + x4 ≥ 100
2x3 + 2x4 + x5 ≥ 100
3x1 + x2 + 2x3 + 3x5 ≥ 100
x1,x2,x3,x4,x5 ≥ 0
用“运筹学”软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。
即 x1=30;
x2=10；
x3=0；
x4=50；
x5=0；
只需90根原材料就可制造出100套钢架。
注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。
例6．某工厂要用三种原料1、
2、3混合调配出三种不同规格的
产品甲、乙、丙，数据如右表。
问：该厂应如何安排生产，使利
润收入为最大？
解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑：
对于甲： x11，x12，x13；
对于乙： x21，x22，x23；
对于丙： x31，x32，x33；
对于原料1： x11，x21，x31；
对于原料2： x12，x22，x32；
对于原料3： x13，x23，x33；
目标函数： 利润最大，利润 = 收入 - 原料支出
约束条件： 规格要求 4 个；
供应量限制 3 个。
利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数量-甲乙丙使用的原料单价*原料数量，故有
目标函数
Max 50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）
= -15x11+25x12+15x13-30x21+10x22-40x31-10x33
约束条件：
从第1个表中有：
x11≥(x11+x12+x13)
x12≤(x11+x12+x13)
x21≥(x21+x22+x23)
x22≤(x21+x22+x23)
从第2个表中，生产甲乙丙的原材料不能超过原
材料的供应限额，故有
(x11+x21+x31)≤100
(x12+x22+x32)≤100
(x13+x23+x33)≤60
通过整理，得到以下模型：
例6．（续）
目标函数：Max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33
约束条件：
. x12 x13 ≥ 0 （原材料1不少于50%）
+ ≤ 0 （原材料2不超过25%）
≥ 0 （原材料1不少于25%）
x21+ x22 x23 ≤ 0 （原材料2不超过50%）
x11+ x21 + x31 ≤ 100 (供应量限制）
x12+ x22 + x32 ≤ 100 (供应量限制）
x13+ x23 + x33 ≤ 60 (供应量限制）
xij ≥ 0 , i = 1,2,3; j = 1,2,3
130100
×10-2
4
408100
×10-2
3
265200
×10-2
2
380000
×10-2
1
库存量(L)
蒸汽压力(g/cm2)
辛烷数
标准汽油
例7.汽油混合问题。一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1、2、3、4种标准汽油，其特性和库存量列于表4-6中，将这四种标准汽油混合，可得到标号为1，2的两种飞机汽油，这两种汽油的性能指标及产量需求列于表4-7中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？
不少于250000
不大于 ×10-2
不小于100
2
越多越好
不大于 ×10-2
不小于91
1
产量需求
蒸汽压力(g/cm2)
辛烷数
飞机汽油
表4---6
表4---7
解：设xij为飞机汽油i中所用标准汽油j的数量(L)。
目标函数为飞机汽油1的总产量：
库存量约束为：
产量约束为飞机汽油2的产量：
由物理中的分压定律， 可得有关蒸汽压力的约束条件：
同样可得有关辛烷数的约束条件为：
综上所述，得该问题的数学模型为：
2）约束条件：
第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是 x11+ x12 = 200；
第二年：B次年末才可收回投资，故第二年年初有资金 x11，于是 x21 + x22+ x24 = ；
第三年：年初有资金 + ，于是 x31 + x32+ x33 = + ；
第四年：年初有资金 + ，于是 x41 + x42 = + ；
第五年：年初有资金 + ，于是 x51 = + ；
B、C、D的投资限制： xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100
3）目标函数及模型：
a) Max z = + + +
. x11+ x12 = 200
x21 + x22+ x24 = ；
x31 + x32+ x33 = + ；
x41 + x42 = + ；
x51 = + ；
xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100
xij ≥ 0 ( i = 1、2、3、4、5；j = 1、2、3、4）
由运筹学软件求解得：
例8．某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项
目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第
一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额
不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规
定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本
利155%，但规定最大投资额不能超过100万元。
据测定每万元每次投资的风险指数如右表：
问：
a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？
b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？
解： 1）确定决策变量：连续投资问题
设 xij ( i = 1～5，j = 1～4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：
A x11 x21 x31 x41 x51
B x12 x22 x32 x42
C x33
D x24
b)所设变量与问题a相同，目标函数为风险最小，有 Min f =x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+
在问题a的约束条件中加上“第五年末拥有资金本利在330万元”的条件，
于是模型如下：
Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+
. x11+ x12 = 200
x21 + x22+ x24 = ；
x31 + x32+ x33 = + ；
x41 + x42 = + ；
x51 = + ；
xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100
+ + + ≥ 330
xij ≥ 0 ( i = 1、2、3、4、5；j = 1、2、3、4）
第三章 线性规划的对偶理论与灵敏度分析
§1 线性规划的对偶问题
§2 对偶规划的基本性质
§3 对偶单纯形法
§4 线性规划的灵敏度分析
每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。
例题1 某工厂在计划期内安排Ⅰ、Ⅱ两种产品，生产单位产品所需设备A、B、C台时如表所示
该工厂每生产一单位产品 可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少 产品和Ⅱ产品，才能使工厂获利最多？
解：设 为产品 的计划产量， 为产品Ⅱ的计划产量，则有
目标函数： Max z=50 +100
约束条件：
，
§1 线性规划的对偶问题
现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢？
设 分别为设备A、B、C的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。作为出租者来说，把生产单位 产品所需各设备的台时各总租金不应低于原利润50元，即 ，否则就不出租还是用于生产 产品以获利50元；同样把
生产一单位 产品所需各设备的台时的总租金也不应当低于原利润100元， 即
，否则这些设备台时就不出租，还是用于生产 产品以获利100元。但对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即min ，这样我们得到了该问题的数学模型：
目标函数：
约束条件：
这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。
如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。
1 求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。
2 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。
3 原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i个约束条件的右边常数项就等于零对偶问题的目标函数中的第i个变量的系数。
4 对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。
设
A=
则
如果我们用矩阵形式来表示，则有原问题：
其中A是 矩阵m*n，该问题有m个约束条件n个变量，x= ,b= ,
c=
对偶问题：
其中 是A的转置， 是b的转置, 是c的转置, y=
现在我们用单纯形法求对偶问题的解。
加上剩余变量 和人工变量 ，把此问题化成标准型如下：
把上述数据填入单纯形表计算。
-300
-250
-300
-250
-400
-250
-M
50
-1
-1
1
1
-1
0
-27500
-50
250
50
-250
-350
-300
-M+50
-250
-50
0
-50
0
75
-1/2
-1
1/2
1
0
1/2
-M+75
-250
-75
0
0
25
-28750
-75
250
75
-250
-400
-325
100/1
100
0
-1
0
1
1
1
0
-250
-M
0
2M-150
M-250
-50M-25000
-M
250
M
-250
-2M-250
-M-250
-M
0
0
-250
-400
50
1
0
-1
0
2
1
3
25
1/2
0
-1/2
0
1
1/2
2
50/2
50
1
0
-1
0
②
1
1
b
基变量
迭代变量
由上表，最优解： =50，
-f 的最大值为-27500，即目标函数f的最大值为f=27500元。
从上面可知租金：A设备为50元，B设备为0元，C设备为50元。这样把工
厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出
租设备的最小费用，因为这是目 标函数的最小值。
通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种
设备的对偶价格，这在道理上也能讲得通。 对于两个有对偶关系的线性规划
的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而
求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最
优值，因为这两个最优值相等。
下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问题。
.
这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以（-1），使不等号方向改变即可，得
这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有
显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的
两边都乘以（-1），得
通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题：
.
这个求最大值的线性规划问题的约束条件都取小于等于号，我们马
上可以写出其对偶问题：
.
这里 和 一样都是不同的决策变量，为了表示这两个
决策变量都来源于原问题的第三个约束条件，记为 。
因为在该对偶问题中 和 的系数只相差一个符号，我们可以把
上面的对偶问题化为：
.
进一步，我们可以令 ，这时当 时， ，当
时， 。这也就是说，尽管 但 的取值可以为正，可以为0，
可以为负，即 没有非负限制。
这样我们把原规划的对偶问题化为
.
没有限制。
对照原线性规划问题，我们可以知道：
当原线性规划问题的第i个约束条件取等号时，则其对偶问题的 i个决策变量没有非
负限制。
如果当原线性规划问题中的第 i个决策变量 没有非负限制时，我们也可以用
进行替换，这里 ， ，用类似的方法知道其对偶问题中第 i个
约束条件取等号。
另外，用大于等于0的两个决策变量之差来代替无非负限制的决策变
量也是求解含有无非负限制的决策变量的线性规划问题的一种方法。
原线性规划问题为：
.
无非负限制。
§2 对偶规划的基本性质
对偶规划的基本性质
1．对称性。即对偶问题的对偶是原问题。
2．弱对偶性。即对于原问题（Ⅰ）和对偶问题（Ⅱ）的可行解 都有C ≤bT 。
由弱对偶性，可得出以下推论：
（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。
（2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。
（3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。
3．最优性。如果 是原问题(Ⅰ)的可行解， 是对偶问题(Ⅱ)的可行解，并且 C = bT ，则 和 分别为原问题(Ⅰ)和对偶问题(Ⅱ)的最优解。
4．强对偶性。即若原问题(Ⅰ)及其对偶问题(Ⅱ)都有可行解，则两者都有最优解；且它们的最优解的目标函数都相等。
5．互补松弛性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零也即
若yi*>0,则有
若 ，则有yi*=0
§3 对偶单纯形法
对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原
有问题的所有检验数都小于0的情况下，通过迭代使得所有的约束都大于等于0，
最后求得最优解。
简化计算是对偶单纯形法的优点，但是它在使用上有很大的局限，这主要是
大多数线性规划问题很难找到初始解使得其所有检验数都小于0。但是在灵敏度
分析中，有时需要对偶单纯形法，这样可以简化处理。下面以第二节例一为例。 上节分析中已知当250≤b’1≤325时第一个约束条件的对偶价格不变，现在
b’1=300变成b’1=350，请问这时第一个约束方程的对偶价格应为多少呢？
解：求出在第二次迭代表上的常数列
0 0 -50 0 -50
CJ -ZJ
50 100 0 50 50
ZJ
250
0 1 0 0 1
100
X2
-50
0 0 -2 1 1
0
S2
100
1 0 1 0 -1
50
X1
2
50 100 0 0 0
b
X1 X2 S1 S2 S3
CB
基变量
迭代次数
1.确定出基变量，在常数列中找一个最小的负常量，把这个常量所在行作为出基变量
4.检查常数列值，若已经都非负结束迭代，即为最优，如果还有负数重复1-4步。
0 0 0 -25 -75
CJ -ZJ
28750
50 100 0 25 75
ZJ
250
0 1 0 0 1
100
X2
25
0 0 -2 -1/2 -1/2
0
S2
75
1 0 1 1/2 -1/2
50
X1
2
50 100 0 0 0
b
X1 X2 S1 S2 S3
CB
基变量
迭代次数
§4 线性规划的灵敏度分析
一、目标函数中变量Ck系数灵敏度分析
1.在最终的单纯形表里，X k是非基变量
由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系，
所以当Ck变成Ck+ Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非
基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变
成了Ck+ Ck。这时 K= Ck-Zk就变成了Ck+ Ck- Zk= K+ Ck。要使原来的最优解
仍为最优解，只要 K+ Ck≤0即可，也就是Ck的增量 Ck≤- K。
2.在最终的单纯形表中， X k是基变量
当Ck变成Ck+ Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目
标函数的系数CB变了，则ZJ(J=1,2,…..,N)一般也变了，不妨设CB=(CB1, CB2。。。, Ck,
…， CBm),当CB变成=(CB1, CB2。。。,Ck+ Ck,…,CBm),则：
ZJ=(CB1, CB2。。。, Ck,…，CBm)(a’1j , a’2j ,…, a’Kj ,…, a’mj)
Z’J=(CB1, CB2。。。, Ck+ Ck,…，CBm)(a’1j , a’2j ,…, a’Kj ,…, a’mj) = ZJ + Ck a’Kj
根据上式可知
检验数 J (J=1,2,…..,M)变成了 ’J,有
’ J=CJ-Z’J= J+ CK a’Kj 。要使最优解不变，只要当J K时， ’J <=0
例：
目标函数：Max z=50X1+100X2
约束条件：X1+X2≤300
2X1+X2≤400
X2≤250
X1，X2≥0
最优单纯形表如下
0 0 -50 0 -50
CJ -ZJ
27500
50 100 50 0 50
ZJ
250
0 1 0 0 1
100
X2
50
0 0 -2 1 1
0
S2
50
1 0 1 0 -1
50
X1
2
50 100 0 0 0
b
X1 X2 S1 S2 S3
CB
基变量
迭代次数
我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。
这里δ3=-50，所以当c3的增量Δc3≤50，最优解不变。
再对基变量x1的目标函数的系数c1进行灵敏度分析。
在a11’,a12’,a13’,a14’,a15’中，除了知道a11’和 a13’大于
0， a15’小于0，可知 ，有 。同样有
。这样可以知道当-50≤Δc1≤50时，也就是x1的
目标函数c1’在0≤c1’≤100时最优解不变。
在最终的单纯形表中，用C’1代替原来的C1=50,计算得表
0 0 - C’1 0 C’1-100
CJ -ZJ
C’1 100 C’1 0 -C’1+100
ZJ
250
0 1 0 0 1
100
X2
50
0 0 -2 1 1
0
S2
50
1 0 1 0 -1
C’1
X1
2
50 100 0 0 0
b
X1 X2 S1 S2 S3
CB
基变量
迭代次数
从δ3≤0，得到-c1’≤0,即c1’≥0，并且从δ5≤0，得到c1’≤100。
那么如果c1’取值超出这个范围，必然存在一个检验数大于0，我们可以通过迭代来得到新的最优解。
二、约束方程中常数项的灵敏度分析
从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最
优解中S2 =50是基变量，即为，原料A有50千克没用完，再增加A原料是不会增
加利润的， A的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的
对偶价格为0。
0 0 -50 0 -50
CJ -ZJ
27500
50 100 50 0 50
ZJ
250
0 1 0 0 1
100
X2
50
0 0 -2 1 1
0
S2
50
1 0 1 0 -1
50
X1
2
50 100 0 0 0
b
X1 X2 S1 S2 S3
CB
基变量
迭代次数
可以看出，上题中对于设备台时数约束来说，当其松弛变量在目标函数
中从0变到Z3=50时，也就是只要当前余下一台时数设备从不能获利变成获利
50元时，譬如有人愿意出50元买一个设备时，我们就不必为生产Ι、П产品
而使用完所有的设备台时了，这说明了设备台时数的对偶价格就是Z3=50元。
对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时
这个约束条件的对偶价格就和这个剩余变量的 有关了。这将使得最优目
标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取 值的相反
数- 。
对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方
程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变
量的 值。
下表给出了一个由最终单纯形表对于不同约束类型的对偶价格的取值。
从对偶价格的定义,可以知道当对偶价格为正时它将改进目标函数的值，当对
偶价格为负时它将使得目标函数朝着与最优化相反的方向前进。
下面我们研究当右端项bj发生变化时，在什么范围内其对偶价格不变。由于bj
的变化并不影响系数矩阵的迭代，故其最终单纯形表中的系数矩阵没有变化。由
此可见当bj变化时，要使原来的基不变得到的基本可行解仍然是可行解，也就是所
求的基变量的值一定要大于0。所谓使其对偶价格不变的bj的变化范围，也就是使
其最优解的所有基变量不变，且所得的最优解仍然是可行的bj的变化范围。
等于这个约束条件对应的人工变量的 值,即为 的相反数
=
等于这个约束条件对应的剩余变量的 值,即为 的相反数
≥
等于这个约束条件对应的松弛变量的 值,即为 的相反数
≤
影子价格的取值
约束条件
当bj中的第k项bK 变成 时，也就是原来的初始单
纯形表中的b向量变成了b’向量
这样在最终单纯形表中基变量XB的解就变成了
如要使XB成为可行解，只要使上述等式的右边>0，就可求出
的取值范围，也就是使得第K个约束条件的对偶价格不变的
bk的变化范围。
，
下面我们仍以第二章例1在最终单纯形表上对bj 进行灵敏度分析。
最终单纯形表如下所示：
0 0 -50 0 -50
CJ -ZJ
27500
50 100 50 0 50
ZJ
250
0 1 0 0 1
100
X2
50
0 0 -2 1 1
0
S2
50
1 0 1 0 -1
50
X1
2
50 100 0 0 0
b
X1 X2 S1 S2 S3
CB
基变量
迭代次数
我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1,
实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台
时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备
台时50元。
三、约束方程系数矩阵A灵敏度分析
下面分两种情况讨论
1.在初始单纯形表上的变量Xk的系数列Pk改变为P’k经过迭代后，在最终单纯形表上Xk是非基变量。由于单纯形表的迭代是约束方程的增广矩阵的行变换，Pk变成Pk’仅仅影响最终单纯形表上第k列数据，包括Xk的系数列、Zk以及 k，这时最终单纯形表上的Xk的系数列就变成了B-1Pj’,而Zk就变成CBB-1Pk’，新的检验数 k=Ck-CBB-1Pk’。若 k≤0，则原最优解仍然为最优解。若 k 〉0，则继续进行迭代以求出最优。
例 以第二章例1为基础，设该厂除了生产Ι，Ⅱ种产品外，现在试制成一个新产品Ⅲ，已知生产产品Ⅲ,每件需要设备2台时，并消耗A原料公斤。B原料公斤，获利150元，问该厂应该生产该产品多少？
解：这是一个增加新变量的问题。我们可以把它认为是一个改变变量X3在初始表上的系数列的问题，
0 0 -50 0 -50 -25
CJ -ZJ
27500
50 100 50 0 50 175
ZJ
250
0 1 0 0 1
100
X2
50
0 0 -2 1 1 -2
0
S2
50
1 0 1 0 -1
50
X1
50 100 0 0 0 150
b
X1 X2 S1 S2 S3 X3
CB
基变量
迭代次数
例 假设上例题中产品Ш的工艺结构有了改进，这时生产1件Ш产品需要使用台设备 ，消耗原料A为2千克，原料B为1千克，每件Ш产品的利润为160元，问该厂的生产计划是否要修改。
解：首先求出X3在最终表上的系数列
27500
250
50
50
b
0 0 -50 0 -50 35
CJ -ZJ
50 100 50 0 50 125
ZJ
250/1
0 1 0 0 1 1
100
X2
0 0 -2 1 1 0
0
S2
50/
1 0 1 0 -1
50
X1
2
50 100 0 0 0 150
X1 X2 S1 S2 S3 X3
CB
基变量
迭代次数
接下来又可以有新的迭代S3进基，
31000
150
50
100
b
-70 0 -120 0 20 0
CJ -ZJ
120 100 120 0 -20 160
ZJ
250/3
-20 1 -2 0 3 0
100
X2
50/1
0 0 -2 1 1 0
0
S2
---
2 0 2 0 -2 1
160
X3
3
50 100 0 0 0 150
X1 X2 S1 S2 S3 X3
CB
基变量
迭代次数
接上页
可知此规模的最优解X1=0, X2=0, S1=0, S2=0, S3=50, X3=200,此时，最大目标函数为32000元。也就是说，该厂的新的生产计划为不生产Ι、П产品，生产Ш产品200件, 可获得最大利润32000元。
32000
0
50
200
b
-70 0 -80 -20 0 0
CJ -ZJ
120 100 80 20 0 160
ZJ
250/3
-2 1 4 -3 0 0
100
X2
50/1
0 0 -2 1 1 0
0
S3
---
2 0 2 0 -2 1
160
X3
4
50 100 0 0 0 150
X1 X2 S1 S2 S3 X3
CB
基变量
迭代次数
2.在初始表上的变量XK的系数PK改变为P’K，经过迭代后，在最终表上XK是基变量，在这种情况下原最优解的可行性和最优解都可能被破坏，问题十分复杂，一般不去修改原表而是直接计算。
四、增加一个约束条件的灵敏度分析
在原线性规划中增加一个约束条件时,先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，否则将新增的约束添入原最终单纯形表上进一步求解。
下面仍以第三章例1为例来加以说明。
例：假如该工厂除了在设备台时，原材料A、B上对该厂的生产有限制外，还有电力供应上的限制。最高供应电量为5000度，而生产一个Ⅰ产品需要用电10度，而生产一个Ⅱ产品需要用电30度。试分析此时该厂获得最大利润的生产计划？
解：先将原问题的最优解
=50，
=250代入用电量的约束条件
得：10×50+30×250=500+7500>5000,所以原题的最优解不是本题的最优解。
在用电量的约束条件中加入松驰变量S4后得：
把这个约束条件加入到原最终单纯形表上，其中S4为基变量，得表如下：
0
-50
0
-50
0
0
27500
0
50
0
50
100
50
5000
1
0
0
0
30
10
0
250
0
1
0
0
1
0
100
50
0
1
1
-2
0
0
0
50
0
-1
0
1
0
1
50
0
0
0
0
100
50
比值
b
基变量
迭代次数
在上表中的X1，X2不是单位向量，故进行行的线性变换，得
0
-50
0
-50
0
0
27500
0
50
0
50
100
50
zj
-3000
1
-20
0
-10
0
0
0
s4
250
0
1
0
0
1
0
100
x2
50
0
1
1
-2
0
0
0
s2
50
0
-1
0
1
0
1
50
x1
0
0
0
0
100
50
比值
b
s4
s3
s2
s1
x2
x1
CB
基变量
迭代
次数
把上表中的S4行的约束可以写为：
上式两边乘以（-1），再加上人工变量a1得：
用上式替换上表中的S4行，得下表：
-M+3
-3
0
-10
0
0
-3
3
0
10
0
100
50
zj
40
1/50
-1/50
0
-2/5
1
0
0
0
s4
120
-2/50
2/50
0
-1/5
0
1
0
100
x2
130
2/50
-2/50
1
1/5
0
0
0
0
s3
140
1/50
-1/50
0
3/5
0
0
1
50
x1
0
-M
0
50-20M
50M-150
0
-M
M
0
20M-50
150-50M
100
50
zj
2000
1
-1
0
-20
50
0
0
-M
s4
200
0
0
0
-1
2
1
0
100
x2
50
0
0
1
1
-2
0
0
0
s3
100
0
0
0
1
-1
0
1
50
x1
0
0
20M-50
0
10M-50
0
0
-M
0
50-20M
0
50-10M
100
50
zj
3000
1
1
-20
0
-10
0
0
-M
s4
250
0
0
1
0
0
1
0
100
x2
50
0
0
(1)
1
-2
0
0
0
s2
50
0
0
-1
0
1
0
1
50
x1
-M
0
0
0
0
100
50
比值
b
a1
s4
s3
s2
s1
x2
x1
基变量
迭代次数
由上表可知，最优解为：
即该工厂在添加了用电限量以后的最优生产计划为Ⅰ产品生产140件，Ⅱ产品生产120件。
第四章 运 输 问 题
§1 运 输 模 型
§2 运输问题的表上作业法
§3 运输问题的进一步讨论
§4 运输问题的应用
例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
解： 产销平衡问题： 总产量 = 总销量
设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：
Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23
. x11+ x12 + x13 = 200
x21 + x22+ x23 = 300
x11 + x21 = 150
x12 + x22 = 150
x13 + x23 = 200
xij ≥ 0 ( i = 1、2；j = 1、2、3）
§1 运 输 模 型
一般运输模型：产销平衡
A1、 A2、…、 Am 表示某物资的m个产地； B1、B2、…、Bn 表示某物质的n个销地；si 表示产地Ai的产量； dj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价。
设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：
m n
Min f = cij xij
i = 1 j = 1
n
. xij = si i = 1,2,…,m
j = 1
m
xij = dj j = 1,2,…,n
i = 1
xij ≥ 0 (i = 1,2,…,m ; j = 1,2,…,n)
§2 运输问题的表上作业法
表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。
运输问题都存在最优解。
计算过程（假设产销平衡）：
1.找出初始基本可行解。对于有m个产地n个销地的产销平衡问题，则有m个关于产量的约束方程和n个关于销量的约束方程。由于产销平衡，其模型最多只有m+n-1个独立的约束方程，即运输问题有m+n-1个基变量。在m×n的产销平衡表上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。
2.求各非基变量的检验数，即检验除了上述m+n-1个基变量以外的空格的检验数判别是否达到最优解，如果已是最优，停止计算，否则转到下一步。
3.确定入基变量和出基变量，找出新的基本可行解。在表上用闭回路法调整。
4.重复2、3直到得到最优解。
一、确定初始基本可行解
为了把初始基本可行解与运价区分开，我们把运价放在每一栏的右上角，每
一栏的中间写上初始基本可行解（调运量）。
1.西北角法：先从表的左上角（即西北角）的变量x11开始分配运输量，并使
x11取尽可能大的值，即x11=min(7,3)=3,则x21与x31必为零。同时把B1的销量与A1的
产量都减去3填入销量和产量处，划去原来的销量和产量。同理可得余下的初始基
本可行解。
20
20
6
0
5
3
0
6
2
0
3
0
销量
9 6 0
6
3
A3
4 2 0
2
2
A2
7 4 0
4
3
A1
产量
B4
B3
B2
B1
销地
产地
3
11
3
10
8
5
10
2
9
4
7
1
2.最小元素法
西北角法是对西北角的变量分配运输量，而最小元素法是就近供应，即对单位运价最小的变量分配运输量。在表上找到单位运价最小的x21，并使x21取尽可能大的值，即x21=min(4,3)=3,把A1的产量改为1，B1的销量改为0，并把B1列划去。在剩下的3×3矩阵中再找最小运价，同理可得其他的基本可行解。
一般来说用最小元素法求得的初始基本可行解比西北角法求得的总运价要少。这样从用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些。
20
20
6
3
0
5
4
0
6
0
3
0
销量
9 3 0
3
6
A3
4 1 0
1
3
A2
7 3 0
3
4
A1
产量
B4
B3
B2
B1
销地
产地
3
11
3
10
8
5
10
2
9
4
7
1
在求初始基本可行解时要注意的两个问题：
1.当我们取定xij的值之后，会出现Ai的产量与Bj的销量都改为零的情况，这时只能划去Ai行或Bj列，但不能同时划去Ai行与Bj列。
2.用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格为m+n-1个，即保证基变量的个数为m+n-1个。
二、最优解的判别
1.闭回路法
所谓闭回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。
所谓闭回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为1，由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量加上或减少1。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。
从非基变量x11出发，找到一个闭回路如上表所示。回路有四个顶点，除x11外，其余都为基变量。现在把x11的调运量从零增加为1吨，运费也增加了3元，为了使A1产量平衡，x13必须减少1吨，运费减少3元。为了B3的销量平衡，x23必须增加1吨，运费增加2元。同理把x21减少1吨，运费减少1元。调整后，总运费增加了3-3+2-1=1元。说明如果让x11为基变量，运费就会增加，其增加值1作为x11的检验数，为了区别调整量，我们把1加圈。
用同样的方法可以找出所有空格（即非基变量）的检验数。
20
20
6
5
6
3
销量
9
A3
4
1
3
A2
7
4
1
A1
产量
B4
B3
B2
B1
销地
产地
3
11
3
10
8
5
10
2
9
4
7
1
2.位势法
所谓位势法，我们对运输表上的每一行赋予一个数值ui，对每一列赋
予一个数值vj，它们的数值是由基变量xij的检验数 所决
定的，则非基变量xij的检验数就可以用公式 求出。
我们先给u1赋个任意数值，不妨设u1=0，则从基变量x13的检验数求得v3=c13-u1=3-0=3。同理可以求得v4=10，u2=-1等等见上表。检验值的求法即用公式 ，如 。
20
20
10
3
9
2
vj
-5
3
12
6
10
A3
-1
-1
1
1
3
A2
0
3
4
2
1
A1
ui
B4
B3
B2
B1
销地
产地
3
11
3
10
8
5
10
2
9
4
7
1
三、改进运输方案的办法——闭回路调整法
当表中的某个检验数小于零时，方案不为最优，需要调整。方法是：选取所有
负检验数最小的非基变量作为入基变量，以求尽快实现最优。本例中取 ，
表明增加一个单位的x24运输量，可使得总运费减少1。在以x24为出发点的闭回路
中，找出所有偶数的顶点的调运量：x14=3，x23=1，x24=min(3,1)=1。把所有闭回
路上为偶数顶点的运输量都减少这个值，奇数顶点的运输量都增加这个值(见下
表)。
20
20
10
3
9
2
vj
-5
3
6
A3
-1
+1
1 (-1)
3
A2
0
3(-1)
4(+1)
A1
ui
B4
B3
B2
B1
销地
产地
3
11
3
10
8
5
10
2
9
4
7
1
对上表用位势法进行检验如下表
20
20
6
5
6
3
销量
9
3
6
A3
4
1
3
A2
7
2
5
A1
产量
B4
B3
B2
B1
销地
产地
20
20
10
3
9
2
vj
-5
3
12
6
9
A3
-1
1
1
2
3
A2
0
2
5
2
0
A1
ui
B4
B3
B2
B1
销地
产地
3
11
3
10
8
5
10
2
9
4
7
1
四、如何找多个最优方案
识别是否有多个最优解的方法和单纯形表法一样，只需看最优方案中是否存在非基变量的检验数为零。如在本题中给出的最优运输方案中x11的检验数为0，可知此运输问题有多个最优解。只要把x11作为入基变量，调整运输方案，就可得到另一个最优方案。
3
6
A3
1(+2)
3(-2)
A2
2(-2)
5
(+2)
A1
B4
B3
B2
B1
销地
产地
3
6
A3
3
1
A2
5
2
A1
B4
B3
B2
B1
销地
产地
§3 运输问题的进一步讨论
1.供需不平衡问题
例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
解：增加一个
虚设的销地
运输费用为0
例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
解：增加一个
虚设的产地
运输费用为0
2.转运问题：
在原运输问题上增加若干转运站。运输方式有：产地 转运站、转
运站 销地、产地 产地、产地 销地、销地 转运站、销地 产
地等。
例3、腾飞电子仪器公司在大连和广州
有两个分厂生产同一种仪器，大连分厂
每月生产400台，广州分厂每月生产600
台。该公司在上海和天津有两个销售公
司负责对南京、济南、南昌、青岛四个
城市的仪器供应。另外因为大连距离青
岛较近，公司同意大连分厂向青岛直接
供货，运输费用如图，单位是百元。问应该如何调运仪器，
可使总运输费用最低？图中 1- 广州、2 - 大连、
3 - 上海、4 - 天津、5 - 南京、6 - 济南、7 - 南昌、8 - 青岛
解：设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型：
目标函数：Min f = 所有可能的运输费用（运输单价与运输量乘积之和）
约束条件：
对产地（发点） i ：输出量 - 输入量 = 产量
对转运站（中转点）：输入量 - 输出量 = 0
对销地（收点） j ：输入量 - 输出量 = 销量
目标函数： Min f = 2x13+ 3x14+ 3x23+ x24+ 4x28 + 2x35+ 6x36+ 3x37+ 6x38+ 4x45+ 4x46+ 6x47+ 5x48
约束条件：
. x13+ x14 ≤ 600 (广州分厂供应量限制）
x23+ x24+ x28 ≤ 400 (大连分厂供应量限制）
-x13- x23 + x35 + x36+ x37 + x38 = 0 （上海销售公司，转运站）
-x14- x24 + x45 + x46+ x47 + x48 = 0 （天津销售公司，转运站）
x35+ x45 = 200 （南京的销量）
x36+ x46 = 150 （济南的销量）
x37+ x47 = 350 （南昌的销量）
x38+ x48 + x28 = 300 （青岛的销量）
xij ≥ 0 , i,j = 1,2,3,4,5,6,7,8
用“运筹学”软件求得结果：
x13 = 550 x14 =50 ；
x23 = 0 x24 = 100 x28 = 300 ；
x35 = 200 x36 = 0 x37 = 350 x38 = 0 ；
x45 = 0 x46 = 150 x47 = 0 x48 = 0 。
最小运输费用为：4600百元
例4、某公司有A1、 A2、 A3三个分厂生产某种物资，分别供应B1、 B2、 B3、 B4四个地区的销售公司销售。假设质量相同，有关数据如下表：
试求总费用为最少的调运方案。
假设：
1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；
2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地；
3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。
运价如下表：
解：把此转运问题转化为一般运输问题：
1、把所有产地、销地、转运站都同时看作产地和销地；
2、运输表中不可能方案的运费取作M，自身对自身的运费为0；
3、Ai： 产量为 20+原产量， 销量为 20； Ti ： 产量、销量均为 20； Bi： 产量为 20， 销量为 20 +原销量，其中20为各点可能变化的最大流量；
4、对于最优方案，其中 xi i 为自身对自身的运量，实际上不进行运作。
扩大的运输问题产销平衡与运价表：
§4 运输问题的应用
一、产销不平衡的运输问题
例1、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为：
由于需大于供，经院研究决定一区供应量可减少0--300吨，二区必须满
足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。
解： 根据题意，作出产销平衡与运价表：
这里 M 代表一个很大的正数，其作用是强迫相应的 x31、 x33、 x34取值为0。
一、产销不平衡的运输问题
例2、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表：
试求总费用为最低的化肥调拨方案。
解： 根据题意，作出产销平衡与运价表：
最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低
要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应 4”的销量
50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为 50。
二、生产与储存问题
例3、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。
解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足：
交货：x11 = 10 生产：x11 + x12 + x13 + x14 ≤ 25
x12 + x22 = 15 x22 + x23 + x24 ≤ 35
x13 + x23 + x33 = 25 x33 + x34 ≤ 30
x14 + x24 + x34 + x44 = 20 x44 ≤ 10
把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交
货的柴油机数目看作第 j 个销售点的销量；成本加储存、维护等费用看作
运费。可构造下列产销平衡问题：
目标函数：Min f = x11 + x12 + x13 + x14 + x22 + x23 + x24 + x33 + x34 + x44
二、生产与储存问题
例4、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：
已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，
则需要运到分厂库房，每台增加运输成本万元,每台机器每月的平均仓
储费、维护费为万元。在7--8月份销售淡季，全厂停产1个月，因此在6
月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万
元。问应如何安排1--6月份的生产，可使总的生产费用（包括运输、仓
储、维护）最少？
解： 这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地
1）1--6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设一假想销地销量为36；
2）上年末库存103台，只有仓储费和运输费，把它列为第0行；
3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台；
4）1--6表示1--6月份正常生产情况， 1’--6’表示1--6月份加班生产情况。
产销平衡与运价表：
用“运筹学”软件解得的结果是：1-6月最低生产费用为万元，每月的销售安排如下表所示
第五章 目标规划
§1 目标规划问题及模型
§2 目标规划的图解法
§3 目标规划的应用举例
例1．一位投资商有一笔资金准备购买股票。资金总额为90000元，目前可选的股票有A和B两种（可以同时投资于两种股票）。其价格以及年收益率和风险系数如表1：
从上表可知，A股票的收益率为（3／20）×100％＝15％，股票B的收益率为4／50×100％＝8％，A的收益率比B大，但同时A的风险也比B大。这也符合高风险高收益的规律。
试求一种投资方案，使得一年的总投资风险不高于700，且投资收益不低于10000元。
股票
价格（元）
年收益（元）／年
风险系数
A
20
3
B
50
4
§1 目标规划问题及模型
显然，此问题属于目标规划问题。它有两个目标变量：一是限制风险，一是确保收益。在求解之前，应首先考虑两个目标的优先权。
假设第一个目标（即限制风险）的优先权比第二个目标（确保收益）大，这意味着求解过程中必须首先满足第一个目标，然后在此基础上再尽量满足第二个目标。
建立模型：
设x1、x2分别表示投资商所购买的A股票和B股票的数量。
首先考虑资金总额的约束：总投资额不能高于90000元。即
20x1＋50x2≤90000。
一、约束条件
再来考虑风险约束：总风险不能超过700。投资的总风险为
＋。引入两个变量d1+和d1-,建立等式如下：
+=700+d1+-d1-
其中，d1+表示总风险高于700的部分，d1-表示总风险少于700的
部分，d1+≥0。
目标规划中把d1+、d1-这样的变量称为偏差变量。偏差变量的作
用是允许约束条件不被精确满足。
把等式转换，可得到
+-d1++d1-=700。
再来考虑年收入:
年收入=3x1+4x2
引入变量d2+和d2-，分别表示年收入超过与低于10000的数量。
于是，第2个目标可以表示为
3x1+4x2-d2++d2-=10000。
二、有优先权的目标函数
本问题中第一个目标的优先权比第二个目标大。即最重要的目标是满足风险不超过700。分配给第一个目标较高的优先权P1,分配给第二个目标较低的优先权P2。
针对每一个优先权，应当建立一个单一目标的线性规划模型。首先建立具有最高优先权的目标的线性规划模型，求解；然后再按照优先权逐渐降低的顺序分别建立单一目标的线性规划模型，方法是在原来模型的基础上修改目标函数，并把原来模型求解所得的目标最优值作为一个新的约束条件加入到当前模型中，并求解。
§2 目标规划的图解法
1．针对优先权最高的目标建立线性规划
建立线性规划模型如下：
Min d1+
.
20x1＋50x2≤90000
+-d1++d1-=700
3x1+4x2-d2++d2-=10000
x1,x2,d1+,d1-≥0
图1 图解法步骤2
0
1000
2000
3000
4000
5000
2000
3000
4000
x1
x2
20x1＋50x2≤90000
1000
+=700
2．针对优先权次高的目标建立线性规划
优先权次高（P2）的目标是总收益超过10000。
建立线性规划如下：
Min d2-
.
20x1＋50x2≤90000
+-d1++d1-=700
3x1+4x2-d2++d2-=10000
d1+＝0
x1,x2,d1+,d1-,d2+,d2-≥0
3x1+4x2=10000
图2 图解法步骤3
0
1000
2000
3000
4000
5000
2000
3000
4000
x1
x2
20x1＋50x2≤90000
1000
+=700
d1+>0
d1+＝0
d2-=0
d2->0
(810,1476)
目标规划的这种求解方法可以表述如下：
1．确定解的可行区域。
2．对优先权最高的目标求解，如果找不到能满足该目标的解，则寻找最接近该目标的解。
3．对优先权次之的目标进行求解。注意：必须保证优先权高的目标不变。
4. 重复第3步，直至所有优先权的目标求解完。
四、目标规划模型的标准化
例1中对两个不同优先权的目标单独建立线性规划进行求解。为简
便，把它们用一个模型来表达，如下：
Min P1（d1+）+P2（d2-）
.
20x1＋50x2≤90000
+-d1++d1-=700
3x1+4x2-d2++d2-=10000
x1,x2,d1+,d1-,d2+,d2-≥0
§3 目标规划的应用举例
例1．一工艺品厂商手工生产某两种工艺品A、B，已知生产一件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3工时。A、B产品的单位利润分别为250元和125元。为了最大效率地利用人力资源，确定生产的首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于600工时，但也不能超过680工时的极限；次要任务是要求每周的利润超过70000元；在前两个任务的前提下，为了保证库存需要，要求每周产品A和B的产量分别不低于200和120件，因为B产品比A产品更重要，不妨假设B完成最低产量120件的重要性是A完成200件的重要性的1倍。
试求如何安排生产？
解：
本问题中有3个不同优先权的目标，不妨用P1、P2、P3表示从高至低的优先权。
对应P1有两个目标：每周总耗费人力资源不能低于600工时,也不能超过680工时；
对应P2有一个目标：每周的利润超过70000元；
对应P3有两个目标：每周产品A和B的产量分别不低于200和120件。
采用简化模式，最终得到目标线性规划如下：
Min P1(d1+)+ P1(d2－)+P2(d3-)+ P3(d4-)+ P3(2d5-)
.
2x1+3x2-d1++d1-=680 对应第1个目标
2x1+3x2-d2++d2-=600 对应第2个目标
250x1+125x2-d3-+d3+＝70000 对应第3个目标
x1-d4++d4-=200 对应第4个目标
x2-d5++d5-=120 对应第5个目标
x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-≥0
使用运筹学软件求解可得：
x1=250；x2=60；d1+=0；d1-=0；d2+=80；d2-=0；d3+=0；d3-=0；
d4+=50；d4-=0；d5+=0；d5-=60，目标函数d4-+2d5- =120。
可见，目标1、目标3和目标4达到了，但目标2、目标5都有一些偏差。
加权目标规划是另一种解决多目标决策问题的方法，其基本方法是通过量化的方法分配给每个目标的偏离的严重程度一个罚数权重，然后建立总的目标函数，该目标函数表示的目标是要使每个目标函数与各自目标的加权偏差之和最小，假设所有单个的目标函数及约束条件都符合线性规划的要求，那么，整个问题都可以描述为一个线性规划的问题。
如果在例1中我们对每周总耗费的人力资源超过680工时或低于600工时的每工时罚数权重定为7；每周利润低于70000元时，每元的罚数权重为5；每周产品A产量低于200件时每件罚数权重为2，而每周产品B产量低于120件时每件罚数权重为4。
则其目标函数化为：
min7d1++7d2-+5d3-+2d4-+4d5-
这就变成了一个普通的单一目标的线性规划问题
min7d1++7d2-+5d3-+2d4-+4d5-
. 2x1+3x2-d1++d1-=680
2x1+3x2-d2-+d2+=680
250x1+125x2-d3-+d3+=70000
x1-d4++d4-=200
x2-d5++d5-=120
x1,x2,d1+,d1-,d2-,d2+, d3+,d3-,d4+,d4-,d5+,d5-≥0 。
第六章 整数规划
§1 整数规划的数学模型及其解的特点
§2 整数规划的应用
§3 整数规划的分枝定界法
§4 指派问题
§1 整数规划的数学模型及其解的特点
例1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。
甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。
解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型
目标函数： Max z = 2x1 +3 x2
约束条件：
195 x1 + 273 x2 ≤1365
4 x1 + 40 x2 ≤140
x1 ≤4
x1，x2 ≥ 0 为整数。
货物
每件体积
（立方英尺）
每件重量
（百千克）
每件利润
（百元）
甲
乙
195
273
4
40
2
3
托运限制
1365
140
如果去掉最后一个约束，就是一个线性规划问题。利用图解法，如果去掉最后一个约束，就是一个线性规划问题。利用图解法，得到线性规划的最优解为x1=, x2=,目标函数值为。由图表可看出，整数规划的最优解为x1=4, x2=2,目标函数值为14。
一般求整数解的线性规划问题，不可用四舍五入法或去尾法对线性规划的非整数解加以处理来解决整数规划。在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问题；
如果有一部分变量为负整数，则称之为混合整数规划问题。在整数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1变量。在纯整数规划和混合整数规划问题中，如果所有的变量都为0-1变量，则称之为0-1规划。
性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。
§2 整数规划的应用
一、投资场所的选择
例1、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：
在东区由A1 ， A2 ，A3 三个点至多选择两个；
在西区由A4 ， A5 两个点中至少选一个；
在南区由A6 ， A7 两个点中至少选一个；
在北区由A8 ， A9 ， A10 三个点中至少选两个。
Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?
解：设：0--1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。
这样我们可建立如下的数学模型：
Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10
. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤ 720
x1 + x2 + x3 ≤ 2
x4 + x5 ≥ 1
x6 + x7 ≥ 1
x8 + x9 + x10 ≥ 2
xj ≥ 0 且xj 为0--1变量，i = 1,2,3,……,10
二、固定成本问题
例2．高压容器公司制造小、中、大三种尺寸的金属容器，
所用资源为金属板、劳动力和机器设备，制造一个容器所需
的各种资源的数量如表所示。不考虑固定费用，每种容器
售出一只所得的利润分别为 4万元、5万元、6万元，可使用的
金属板有500吨，劳动力有300人/月，机器有100台/月，此外
不管每种容器制造的数量是多少，都要支付一笔固定的费用：
小号是l00万元，中号为 150 万元，大号为200万元。现在要制
定一个生产计划，使获得的利润为最大。
解：这是一个整数规划的问题。
设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。各
种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这
种性质，设 yi = 1(当生产第 i种容器, 即 xi ＞ 0 时) 或0（当不生产第 i种容
器即 xi = 0 时）。
引入约束 xi ≤ M yi ，i =1，2，3，M充分大，以保证当 yi = 0 时，xi
= 0 。
这样我们可建立如下的数学模型：
Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3
. 2x1 + 4x2 + 8x3 ≤ 500
2x1 + 3x2 + 4x3 ≤ 300
x1 + 2x2 + 3x3 ≤ 100
xi ≤ M yi ，i =1，2，3，M充分大
xj ≥ 0 yj 为0--1变量，i = 1,2,3
三、分布系统设计
例3．某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知在 A2 ， A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外， A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。
问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?
解： 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yk = 1(当Ak 被选中时)或0（当Ak 没被选中时),k =2,3,4,5．这可以表示为一个整数规划问题：
Min z = 175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+
3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53
其中前4项为固定投资额，后面的项为运输费用。
. x11+ x12+ x13 ≤ 30 ( A1 厂的产量限制)
x21+ x22+ x23 ≤ 10y2 ( A2 厂的产量限制)
x31+ x32+ x33 ≤ 20y3 ( A3 厂的产量限制)
x41+ x42+ x43 ≤ 30y4 ( A4 厂的产量限制)
x51+ x52+ x53 ≤ 40y5 ( A5 厂的产量限制)
x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制)
x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制)
x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制)
xij ≥0，i = 1,2,3,4,5； j = 1,2,3， yk 为0--1变量，k =2,3,4,5。 * * * 求解可用《运筹学》软件中整数规划方法。
四、投资问题
例4．某公司在今后五年内考虑给以下的项目投资。已知：
项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%， 但要求第一年投资最低金额为4万元，第二、三、四年不限；
项目B：第三年初需要投资，到第五年末能回收本利128％，但规定最低投资金额为3万元，最高金额为5万元；
项目 C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。
项目 D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。
该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，
使到第五年末拥有的资金本利总额为最大?
解：1) 设xiA、xiB、xiC、xiD ( i ＝1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额；
设yiA， yiB，是0—1变量，并规定取 1 时分别表示第 i 年给A、B投资，
否则取 0（ i = 1, 2, 3, 4, 5）。
设yiC 是非负整数变量，并规定：第2年投资C项目8万元时，取值为4；
第 2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2；
第2年投资C项目2万元时，取值1；第2年不投资C项目时，取值0；
这样我们建立如下的决策变量：
第1年 第2年 第3年 第4年 第5年
A x1A x2A x3A x4A
B x3B
C x2C=20000y2C
D x1D x2D x3D x4D x5D
2）约束条件：
第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是 x1A+ x1D = 100000；
第二年：A的投资第二年末才可收回，故第二年年初的资金为，于是x2A+x2C+x2D = ；
第三年：年初的资金为 +，于是 x3A+x3B+x3D = + ；
第四年：年初的资金为 +，于是 x4A + x4D = + ；
第五年：年初的资金为 +，于是 x5D = + 。
关于项目A的投资额规定: x1A ≥ 40000y1A ，x1A ≤ 200000y1A ，200000是足
够大的数；保证当 y1A = 0时， x1A = 0 ；当y1A = 1时，x1A ≥ 40000 。
关于项目B的投资额规定: x3B ≥ 30000y3B ，x3B ≤ 50000y3B ；
保证当 y3B = 0时， x3B = 0 ；当y3B = 1时，50000 ≥ x3B ≥ 30000 。
关于项目C的投资额规定: x2C = 20000y2C ，y2C = 0，1，2，3，4。
3）目标函数及模型：
Max z = + + +
. x1A+ x1D = 100000；
x2A+x2C+x2D = ；
x3A+x3B+x3D = + ；
x4A+x4D = + ；
x5D = + ；
x1A ≥ 40000y1A ，
x1A ≤ 200000y1A ，
x3B ≥ 30000y3B ，
x3B ≤ 50000y3B ；
x2C = 20000y2C ，
yiA， yiB = 0 或 1，i = 1,2,3,4,5
y2C = 0，1，2，3，4
xiA ，xiB ，xiC ，xiD ≥ 0 ( i = 1、2、3、4、5）
§3 整数规划的分枝定界法
分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。
分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。
下面以例1予以说明。
例1 用分枝定界法求解整数规划
Max 2x1+3x2
. 195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1,x2≥ 0且x1,x2为整数
解:
(一)先求出以下线性规划的解：
Max 2x1+3x2
. 195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1,x2≥ 0
得z1=,x1=,x2=
(二)确定整数规划的最优目标函数值z*初始上界 和下界z。
分析后，知道 =，由观察法得下界z=13（当x1=2,x2=3时）。
(三)将一个线性规划问题分为两枝，并求解。
可由x1≤2或x1≥3中取值。将线性规划1分解为两支，如下：
线性规划2：
Max 2x1+3x2
. 195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1 ≤2
x1,x2≥ 0
解得z2=,x1=2,x2=
线性规划3：
Max 2x1+3x2
. 195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1≥ 3
x1,x2≥ 0
解得z3=,x1=3,x2=
(四)修改整数规划的最优目标函数的上下界。
经分析，将上界 =修改为 =，z=13。
(五)在线性规划2和线性规划3中选择一个上界最大的线性规划，即线性规划3，进
行分枝。
线性规划3分解为线性规划4和线性规划5，如下：
线性规划4： Max 2x1+3x2
. 195x1+273x2≤1365
4x1+ 40x2≤140
x1 ≤4
x1≥ 3
x2 ≤2
x1,x2≥ 0
解得z4=14,x1=4,x2=2
线性规划5： Max 2x1+3x2
. 195x1+273x2≤1365
4x1+ 40x2≤140
x1≥ 3
x2≥ 3
x1,x2≥ 0 无可行解
(六)进一步修改整数规划最优目标函数值z*的上下界。
从线性规划2，4，5中修改上下界。分析后，可得 =14， z=14。都
取线性规划2，4，5中的整数可行解的目标函数值的最大值。
性质2：
当整数规划的最优目标函数值z*的上界 等于其下界z时，该整数规划的最优解已经被求出。这个整数的最优解即为其目标函数值取此下界的对应线性规划的整数可行解。
用图8-2表示例9的求解过程与求解结果
线性规划1
Z1=
X1=
X2=
z=13, =
线性规划2
Z2=
X1=2
X2=
线性规划3
Z3=
X1=3
X2=
线性规划4
Z4=
X1=4
X2=2
线性规划5
无可行解
X1≤2
X1≥3
X2≤2
X2≥3
z=13, =
z=14, =14
图8-2
从以上解题过程可得用分枝定界法求解目标函数值最大的整数规划的步骤，我们将求解的整数规划问题称为A，将与其相对应的线性规划问题称为B：
第一步：求解问题B，可得以下情况之一：
没有可行解，则A也没有可行解，求解过程停止。
有最优解，且符合问题A的整数条件，则B的最优解即为A的最优解，求解过程停止。
有最优解，但不符合A的整数条件，记其目标函数值为z1。
第二步：确定A的最优目标函数值z*的上下界，其上界即为z1, =z1,再用观察法找到A的一个整数可行解，求其目标函数值作为z*的下界，记为z 。
第三步：判断 是否等于z 。若相等，则整数规划最优解即为其目标函数值等于z的A的那个整数可行解；否则进行第四步。
第四步：在B的最优解中选一个最远离整数要求的变量，不妨设此变量为xj，以[bj]表示小于bj的最大整数，构造以下两个约束条件，并加入问题B，得到B的两个分枝B1和B2。
xj ≤[bj]和xj ≥ [bj]+1
第五步：求解B1和B2 。修改A问题的最优目标函数值z*的上下界， 和z 。
第六步：比较和剪枝。各分枝的最优目标函数值中若有小于z者，则剪掉这枝（用打Х表示），即以后不再考虑了。若大于 ，则不符合整数条件，则重复第三步至第六步，直至 =z，求出最优解为止。
对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。
§4 指派问题
有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由
于每人特长不同，完成各项任务的效率等情况也不同。现假设必须
指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使
得完成 n 项任务的总的效率最高，这就是指派问题。
例1．有四个工人，要分别指派他们完成四项不同的工作，每
人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能
使总的消耗时间为最少。
解：引入0—1变量 xij，并令
xij = 1(当指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时)．这可以表示为一个0--1整数规划问题：
Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33
+19x34+19x41 +21x42+23x43+17x44
. x11+ x12+ x13+ x14= 1 (甲只能干一项工作)
x21+ x22+ x23+ x24= 1 (乙只能干一项工作)
x31+ x32+ x33+ x34= 1 (丙只能干一项工作)
x41+ x42+ x43+ x44= 1 (丁只能干一项工作)
x11+ x21+ x31+ x41= 1 ( A工作只能一人干)
x12+ x22+ x32+ x42= 1 ( B工作只能一人干)
x13+ x23+ x33+ x43= 1 ( C工作只能一人干)
x14+ x24+ x34+ x44= 1 ( D工作只能一人干)
xij 为0--1变量，i,j = 1,2,3,4
§1 基本概念
§2 一维搜索
§3 无约束极值问题
§4 约束极值问题
第七章 非线性规划
§1 基本概念
非线性规划问题
非线性规划方法概述
例1 曲线的最优拟合问题
§1 基本概念
例2 构件容积问题
数学规划
约束集或可行域
MP的可行解或可行点
向量化表示
当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。
否则，称为约束非线性规划或者约束最优化问题。
最优解和极小点
非线性规划方法概述
非线性规划基本迭代格式
凸函数和凸规划
凸函数及其性质
凸规划及其性质
凸函数及其性质
凸规划及其性质
约束集
如果(MP)的约束集X是凸集，目标函数f是X上的凸函数，则(MP)叫做非线性凸规划，或简称为凸规划。
定理 凸规划的任一局部最优解都是它的整体最优解。
§2 一维搜索
精确一维搜索方法
法
Newton法
非精确一维搜索方法
Goldstein法
Armijo法
法（近似黄金分割法）
Newton法
§3 无约束最优化方法
无约束问题的最优性条件
最速下降法
共轭方向法
无约束问题的最优化条件
最速下降法
共轭方向法
二次严格凸函数的无约束最优化问题
F-R法步骤
§4 约束最优化方法
约束最优化问题的最优化条件
简约梯度法
惩罚函数法
其中
(MP)
约束最优化问题的最优化条件
令
K-T条件
简约梯度法
()
Wolfe法步骤
惩罚函数法
思想：利用问题中的约束函数做出适当的带有参数的惩罚函数，然后在原来的目标函数上加上惩罚函数构造出带参数的增广目标函数，把(MP)问题的求解转换为求解一系列无约束非线性规划问题。
罚函数法
障碍函数法
罚函数法
设法适当地加大不可行点处对应的目标函数值，使不可行点不能成为相应无约束极小化问题的最优解。
罚函数
实际应用中，选取一个递增且趋于无穷的正罚函数参数列
其中
***
**
罚函数法计算步骤
障碍函数法
在可行区域的边界上筑起一道“墙”，当迭代点靠近边界时，所构造的增广目标函数值陡然增大，于是最优点就被“挡”在可行区域内部了。
构造障碍函数
障碍函数法步骤
第八章 动态规划
§1 多阶段决策过程最优化问题举例
§2 基本概念、基本方程与最优化原理
§3 动态规划的应用
§1 多阶段决策过程最优化问题举例
例1 最短路径问题
下图表示从起点A到终点E之间各点的距离。求A到E的最
短路径。
B
A
C
B
D
B
C
D
E
C
4
1
2
3
1
2
3
1
2
3
2
2
1
6
4
7
2
4
8
3
8
6
7
5
6
1
10
6
3
7
5
1
讨论：
1、以上求从A到E的最短路径问题，可以转化为四个性质完全相
同，但规模较小的子问题，即分别从Di 、Ci、Bi、A到E的最短路
径问题。
第四阶段：两个始点D1和D2，终点只有一个；
表10-1
分析得知：从D1和D2到E的最短路径唯一。
E
E
E
本阶段最优终点
（最优决策)
10*
6
本阶段各终点（决策）
10
6
到E的最短距离
D1
D2
本阶段始点
（状态）
阶段4
第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点
和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路
径问题：
表10-2
分析得知：如果经过C1，则最短路为C1-D2-E；
如果经过C2，则最短路为C2-D2-E；
如果经过C3，则最短路为C3-D1-E。
6+6=12
5+6=11
6+6=12
D2
D1
D2
D2
D1
本阶段最优终点
（最优决策)
8+10=18
7+10=17
1+10=11
本阶段各终点（决策）
12
11
11
到E的最短距离
C1
C2
C3
本阶段始点
（状态）
阶段3
第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分
析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题：
表10-3
分析得知：如果经过B1，则走B1-C2-D2-E；
如果经过B2，则走B2-C3-D1-E；
如果经过B3，则走B3-C3-D1-E；
如果经过B4，则走B4-C3-D1-E。
6+11=17
2+11=13
3+11=14
1+11=12
C3
1+11=12
7+11=18
8+11=19
5+11=16
C2
C1
C2
C3
C3
C3
本阶段最优终点（最优决策)
2+12=14
4+12=16
4+12=16
7+12=19
本阶段各终点（决策）
12
13
14
12
到E的最短距离
B1
B2
B3
B4
本阶段始点
（状态）
阶段2
第一阶段：只有1个始点A，终点有B1,B2,B3,B4 。对始点和终
点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：
表10-4
最后，可以得到：从A到E的最短路径为A B4 C3 D1 E
2+12=14
B4
3+14=17
B3
3+13=16
B2
B1
C2
本阶段最优终点(最优决策)
4+12=16
本阶段各终点（决策）
12
到E的最短距离
A
本阶段始点(状态)
阶段1
以上计算过程及结果，可用图2表示，可以看到，以上方法不仅
得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最
短路径。
以上过程，仅用了22次加法，计算效率远高于穷举法。
B
A
C
B
D
B
C
D
E
C
4
1
2
3
1
2
3
1
2
3
3
2
1
6
4
7
2
4
8
3
8
6
7
5
1
6
10
6
0
10
6
12
11
11
12
13
14
14
12
7
5
1
2
一、基本概念：
1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。
2、状态sk：能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。
3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。
决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。
4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。
5、状态转移方程 sk+1=Tk(sk, xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。
§2 基本概念、基本方程与最优化原理
6、阶段指标函数vk(sk, xk)：从状态sk出发，选择决策xk所产生的第k阶段指标。
过程指标函数Vk,n(sk, xk, xk+1,…, xn)：从状态sk出发，选择决策xk,
xk+1, …, xn所产生的过程指标。动态规划要求过程指标具有可分离
性，即 Vk,n(sk, xk, xk+1, …, xn) = vk(sk, xk)+Vk+1(sk+1, xk+1, …, xn)
称指标具有可加性，或 Vk,n(sk, xk, xk+1, …, xn) = vk(sk, xk)×Vk+1(sk+1,
xk+1, …, xn)称指标具有可乘性。
二、基本方程：
最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指
标Vk,n的最优值，即
对于可加性指标函数，上式可以写为
上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以
写为
以上式子称为动态规划最优指标的递推方程，是动态规划的基本
方程。
终端条件：为了使以上的递推方程有递推的起点，必须要设定最
优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1) = 0。
三、最优化原理
作为整个过程的最优策略具有如下性质：
不管在此最优策略上的某个状态以前的状
态和决策如何，对该状态来说，以后的所有决
策必定构成最优子策略。就是说，最优策略的
任意子策略都是最优的。
一、资源分配问题
例2. 某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工
厂。各工厂获得此设备后，预测可创造的利润如表10-5所示，问这
5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？
表10-5
12
11
13
5
12
11
12
4
11
11
9
3
6
10
7
2
4
5
3
1
0
0
0
0
丙 厂
乙 厂
甲 厂
盈利 工厂
设备台数
§3 动态规划的应用
解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设
sk= 分配给第k个厂至第3个厂的设备台数（k=1、2、
3）。
xk=分配给第k个设备台数。
已知s1=5,
并有
从 与 的定义，可知
以下我们从第三阶段开始计算。
第三阶段:
显然将 台设备都分配给第3工厂时，
也就是 时，第3阶段的指标值（即第3厂的盈利）
为最大，即
由于第3阶段是最后的阶段，故有
其中 可取值为0,1,2,3,4,5。其数值计算见表10－6。
表10－6
5
12
－ － － － － 12
5
4
12
－ － － － 12 －
4
3
11
－ － － 11 － －
3
2
6
－ － 6 － － －
2
1
4
－ 4 － － － －
1
0
0
0 － － － － －
0
0 1 2 3 4 5
其中 表示取3子过程上最优指标值 时的
决策，例如在表10-6中可知当 =4时，有 有
此时 ，即当 时，此时取
（把4台设备分配给第3厂）是最优决策，此时阶段指标值
（盈利）为12，最优3子过程最优指标值也为12。
第二阶段：
当把 台设备分配给第2工厂和第3工
厂时，则对每个 值，有一种最优分配方案，使最大盈利
即最优2子过程最优指标函数值为
因为 上式也可写成
其数值计算如表10－7所示。
表10－7
2
21
0＋12 5＋12 11＋6 11＋4 11＋0
5
1,2
16
0＋12 11＋4 11＋0 －
4
2
14
0＋11 5＋6 11＋0 － －
3
2
10
0＋6 5＋4 － － －
2
1
5
0＋4 － － － －
1
0
0
－ － － － －
0
0 1 2 3 4 5
其中在 的这一行里，当 时，
这里 从表10－5中可知，把1台设备交给乙厂所得盈
利数即可，知 ，这里 从表10－6查
即可知 =11。同样可知当 时，可知
;
当 时， ；当 时，
；当 时，
；由于 ，不可能分2厂5
台设备，故 时， 栏空着不填。从
这些数值中取得最大即得 ，即有 =16。在此行中
我们在取最大值的 上面加一横以示
区别，也可知这时 的最优决策为1或2。
第一阶段：
把 台设备分配给第1，第2，第3厂时，最大
盈利为 其中 可取值0,1,2,3,4,5.
数值计算见表10－8
表10-8
然后按计算表格的顺序推算，可知最优分配方案有两个：
1.由于 ，根据 ，查表10－7可
知 ，再由 ，求得 。即分配
给甲厂0台，乙厂2台，丙厂3台。
2.由于 ，根据 ，查表10－7可
21 0,2
3＋16 9+10 12+5 13+0
5
0 1 2 3 4 5
知 ，再由 ,求得 ，
即分配给甲厂2台，乙厂2台，丙厂1台。
这两种分配方案都能得到最高的总盈利21万元。
二、背包问题
设有n种物品，每一种物品数量无限。第i种物品每件
重量为wi公斤，每件价值ci元。现有一只可装载重量为W
公斤的背包，求各种物品应各取多少件放入背包，使背
包中物品的价值最高。
这个问题可以用整数规划模型来描述。设xi为第i种
物品装入背包的件数（i =1, 2, …, n），背包中物品的总
价值为z，则
Max z = c1x1+c2x2+ … +cnxn
. w1x1+w2x2+…+wnxn≤W
x1, x2, …, xn0 且为整数。
下面用动态规划逆序解法求解它。设
阶段变量k：第k次装载第k种物品（k=1, 2, …, n）
状态变量sk：第k次装载时背包还可以装载的重量；
决策变量uk = xk：第k次装载第k种物品的件数；
决策允许集合：Dk(sk) = { xk | 0 xksk/wk，xk为整数}；
状态转移方程： sk+1 = sk wkxk；
阶段指标： vk = ckxk；
最优过程指标函数fk(sk)：第k到n阶段容许装入物品的最大使
用价值；
递推方程： fk(sk) = max {ckxk+fk+1(sk+1)}
= max {ckxk+fk+1(sk wkxk)}；
xDk(sk)
终端条件： fn+1(sn+1) = 0。
例3. 某咨询公司有10个工作日可以去处理四种类型的咨
询项目，每种类型的咨询项目中待处理的客户数量、处理每个
客户所需工作日数以及所获得的利润如表10－9所示。显然该公
司在10天内不能处理完所有的客户，它可以自己挑选一些客
户，其余的请其他咨询公司去做，应如何选择客户使得在这10
个工作日中获利最大？
表10－9
2
8
11
20
1
3
4
7
4
3
2
2
1
2
3
4
处理每个客户所获利润
处理每个客户所需工作日数
待处理客户数
咨询项目类型
解：用动态规划来求解此题。
我们把此问题分成四个阶段，第一阶段我们决策将
处理多少个第一种咨询项目类型中的客户，第二阶段决
策将处理多少个第二种咨询项目类型中的客户，第三阶
段、第四阶段我们也将作出类似的决策。我们设
＝分配给第k种咨询项目到第四种咨询项目的所
有客户的总工作日（第k阶段的状态变量）。
=在第k种咨询项目中处理客户的数量（第k阶段
的决策变量）。
已知 ＝10
并有
并从 与 的定义可知
从第四阶段开始计算：
显然将 个工作日 尽可能分配给第四
类咨询项目，即 时，第四阶段的指标值为最大，
其中， 表示取不大于 的最大整数，符号 为
取整符号，故有
由于第四阶段是最后的阶段，故有
因为 至多为10，其数值计算见表10－10。
表10－10
1 1
0
10
20 1
0
9
20 1
0
8
20 1
0
7
0 0
－
6
0 0
－
5
0 0
－
4
0 0
－
3
0 0
－
2
0 0
－
1
0 0
－
0
0 1
第三阶段：
当把 个工作日分配给第四类和第
三类咨询项目时，则对每个 值，都有一种最优分配方
案，使其最大盈利即最优3子过程最优指标函数值为
因为
因为 至多为10，所以 的取值可为0,1,2。其数值计算
见表10－11。
表10－11
0
0
－ －
0
2
22
0＋20 11+0
10
2
22
0＋20 11+0
9
2
22
0＋20 11+0
8
0
20
11+0 －
7
1
11
0＋0 －
6
1
11
0＋0 －
5
1
11
0＋0 －
4
0
0
－ －
3
0
0
－ －
2
0
0
－ －
1
0 1 2
第二阶段：
同样以每个 值都有一种最优分配方案，使其最大盈利即
最优2子过程最优指标函数值为：
因为 ，故有
因为 至多为10，所以 的取值为0,1,2,3。其数值计算
见表10－12。
表10-12
第一阶段：
我们已知 ，又因为 ，同样有
因为 ,故 可取值为0,1,2, … ,10。其数值计算
见表10－13。 表10－13
从表10－13可知 ， 从而得 ＝10
－0＝10，在表10－12的 的这一行可知 ，由
，查表10－11的 的这一行可知
，最后由 ，查表10-10的 的这
一行得 ，综上所述得最优解为：
此时最大盈利为28。
现在我们不妨假设该咨询公司的工作计划有所改变，只有
8个工作日来处理这四类咨询项目，那么该咨询公司如何选择
客户使得获利最大呢？我们不必从头开始重做这个问题，而只
要在第一阶段上把 改成8，重新计算就可得到结果，如表10－
14所示，这是动态规划的一个好处。
表10－14
如上一样可从表10－14,10－12,10－11,10－10得到两组最优解
如下：
它们的最优解（即最大盈利）都为22。
一旦咨询的工作日不是减少而是增加，那么我们不仅要重新计
算第一阶段，而且要在第二、第三、第四阶段的计算表上补上增加
的工作日的新的信息，也可得到新的结果。
实际上，背包问题我们也可以用整数规划来求解，如果背包携带物品重量的限制为W公斤，这N种物品中第i种物品的重量为 ，价值为 ，第i种物品的总数量的 ，我们可以设 表示携带第i种物品的数量，则其数学模型为：
.
且为整数。
我们不妨用此模型去求解例3，也一定得出同样的结果。
三、生产与存贮问题
例4. 某公司为主要电力公司生产大型变压器，由于电力
采取预订方式购买，所以该公司可以预测未来几个月的需求
量。为确保需求，该公司为新的一年前四个月制定一项生产
计划，这四个月的需求如表10－15所示。
生产成本随着生产数量而变化。调试费为4，除了调度费
用外，每月生产的头两台各花费为2，后两台花费为1。最大
生产能力每月为4台，生产成本如表10－16所示。
表10－15
表10－16
每台变压器在仓库中由这个月存到下个月的储存费为1，
仓库的最大储存能力为3台，另外，知道在1月1日时仓库里存
有一台变压器，要求在4月30日仓库的库存量为零。试问该公
司应如何制定生产计划，使得四个月的生产成本和储存总费
用最少？
解：我们按月份来划分阶段，第i个月为第i阶段：（i=1,2,3,4).
设 为第k阶段期初库存量； k=1,2,3,4
为第k阶段生产量； k=1,2,3,4
为第k阶段需求量； k=1,2,3,4，这已在表10-15
中告诉我们。
因为下个月的库存量等于上个月的库存量加上上个月的
产量减去上个月的需求量，我们就得到了如下状态转移方
程：
因为 ，故有
因为 ，故有
由于必须要满足需求，则有
通过移项得到
另一方面，第k阶段的生产量 必不大于同期的生产能力
（4台），也不大于第k阶段至第四阶段的需求之和与第k阶段
期初库存量之差，否则第k阶段的生产量就要超过从第k阶段
至第四阶段的总需求，故有
以下我们从第四阶段开始计算：
从以上的状态转移方程 可知
这样就有
这里的阶段指标 可以分成两部分，即生产成本与
储存费，即为
由于第四阶段末要求库存为零，即有 ，
这样可得
对于每个 的可行值， 的值列于表10－17。
表10－17
表中当 时，可知第四阶段要生产
台，从表10－16可知总成本为9，同样可以算出当 为1,2,3时
的情况，结果已列于表10－17中。
第三阶段：
此时有：
因为 以及 所以有
例如，当第三阶段初库存量 时，生产量 为2时，
则 所以生产成本为8，第三阶段末库存
为2时，储存费为 ，而
查10－17表可知 ，这样可知，
填入表10－18中 的栏内，其他结果如表10－18所
示 ： 表10－18
第二阶段：
因为 所以有
计算结果如表10－19所示。
表10－19
第一阶段：
因为 故有
计算结果见表10－20。
表10－20
利用递推关系可以从表10－20，表10－19，表10－18和表10－
17得到两组最优解：
这时有最低总成本29。
四、系统可靠性问题
例5.某科研项目组由三个小组用不同的手段分别研究，它们失败的概率各为，，。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：
问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？
2
1
0
3
2
1
小组
高级科学家
解：用逆序算法。设
阶段：每个研究小组为一个阶段，且
3
2
1
小组
3
2
1
阶段
计算
当n=3时，
当n=2时，
2
0．30
2
1
0．50
1
0
0．80
0
x3*
f3*(s3)
s3
2
0．16
0．16
0．20
0．18
2
0
0．30
0．32
0．30
1
0
0．48
0．48
0
2
1
0
x2*
f2*(s2)
f2(s2,x2)=P2(x2) ·f3*(s2-x2)
x2
s2
当n=1时，
最优解为 x1*=1，x2*=0，x3*=1；科研项目最终失败的概率为。
0．072
2
0．060
1
0
0．060
f2*(s2)
1
x2*
0．064
f1(s1,x1)=P1(x1) ·f2*(s1-x1)
2
x1
s1
一、连续确定性动态规划
对于状态变量和决策变量只取连续值，过程的演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。
机器负荷分配问题
例1 一种机器能在高低两种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为P1=8u1，其中u1为在高负荷状态下生产的机器数目，年完好率为a=，即到年底有70％的机器保持完好。在低负荷下生产时，产量函数为P2=5u2，其中u2为在低负荷状态下生产的机器数目，年完好率为b=。设开始生产时共有1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得5年内生产的产品总产量最高。
解 建立动态规划模型：
分为5个阶段，每个阶段为1年。设状态变量sk表示在第k阶段初拥有的完好机器数目；k=1,2,3,4,5。
决策变量xk表示第k阶段中分配给高负荷状态下生产的机器数目；k=1,2,3,4,5。显然sk-xk为分配给低负荷状态下生产的机器数目。
状态转移方程为 sk+1=+(sk-xk)
阶段指标 rk(sk,xk)=8xk+5(sk-xk)
最优指标函数 ，其
中k=1,2,3,4,5。
f6(s6)=0。
第5阶段：
因为f5(s5)是x5的线性单调增函数，故有x5* =s5，
于是有f5(s5)=8s5。
第4阶段：
同样的，f4(s4)是x4的线性单调增函数，有x4*=s4 ，
f4(s4)=。
对前几个阶段依次类推，可得
f3(s3)=，
f2(s2)=，
f1(s1)=。
因为期初共有完好机器1000台，故s1=1000。有f1(s1)=
＝23720，即5年最大的产量为23720台。得最优解为 ，
， ， 。
这意味着前两年应把年初完好机器完全投入低负荷生产，
后三年应把年初完好机器完全投入高负荷生产。
下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已知s1=1000,根据状态转移方程，有:
上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点状态s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。
如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第5年度结束时仍要保持500台机器完好（而不是278台），应如何安排生产才能使得总产量最大？
下面来分析：
根据终点条件有
可得
显然，由于固定了终点的状态，x5的取值受到了
约束。因此有
类似的，
容易解得 ，f4(s4)=-7500。
依次类推，得
f3(s3)=-7500
f2(s2)=-7500
f1(s1)=-7500
再采用顺序方法递推计算各年的状态，有
s1=1000，
可见，为了使终点完好的机器数量增加到500台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第5年，也只能全部投入高负荷。
相应的最优指标为
f1(s1)=-7500＝21900。
可以看到，因为增加了附加条件，总产量f1(s1)要比终点自由情况下的产量要低。
二、离散随机性动态规划
随机型的动态规划是指状态的转移律是不确定的，即
对给定的状态和决策，下一阶段的到达状态是具有确定概率
分布的随机变量，这个概率分布由本阶段的状态和决策完全
确定。随机型动态规划的基本结构如下图：
sk
状态
xk
决策
概率
k阶段的收益
p1
p2
pN
….
k+1阶段的状态sk+1
c1
c2
cN
1
2
N
图中N表示第k+1阶段可能的状态数，p1、p2、…pN为给定状态sk和决策xk的前提下，可能达到下一个状态的概率。ci为从k阶段状态sk转移到k+1 阶段状态为i时的指标函数值。
在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望效益值进行优化。
例2 某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔2000元。根据有经验的技术人员估计，试制品合格的概率为，每次试制一批的装配费为200元，每件产品的制造成本为100元。每次试制的周期为1个月。问该如何安排试制，每次生产多少件，才能使得期望费用最小？
解：把三次试制当作三个阶段（k=1,2,3）,决策变量xk表示第k次生产的产品的件数；状态变量sk表示第k次试制前是否已经生产出合格品，如果有合格品，则sk=0；如果没有合格品，记sk=1。最优函数fk(sk)表示从状态sk、决策xk出发的第k阶段以后的最小期望费用。故有fk(0)＝0。
生产出一件合格品的概率为，所以生产xk件产品都不合格的概率为 ，至少有一件合格品的概率为1- ，故有状态转移方程为
用C(xk)表示第k阶段的费用，第k阶段的费用包
括制造成本和装配费用，故有
根据状态转移方程以及C(xk)，可得到
如果3个月后没有试制出一件合格品，则要承担
2000元的罚金，因此有f4(1)=20。
当k=3时，计算如下表：
5
15
20
1
0
0
—
—
—
—
—
—
0
0
6
5
4
3
2
1
0
x3*
f3(s3)
C(x3)+20×
x3
s3
当k=2时，计算如下表：
3
1
0
0
—
—
—
—
0
0
4
3
2
1
0
x2*
f2(s2)
C(x2)+×
x2
s2
当k=1时，有
2
1
0
0
—
—
—
0
0
3
2
1
0
x1*
f1(s1)
C(x1)+×
x1
s1
上面三个表中并没有列出xk取更大数值的情况，因为可以证明以后的C(xk)+ fk+1(1)的值是对xk单调增加的。
因此得到的最优策略是，在第1个阶段试制2件产品；如果都不合格，在第2阶段试制3件产品；如果仍都不合格，则在第3个阶段试制5件产品。该策略得到的最小的期望费用。
随机采购问题
例3 某公司打算在5周内采购一批原料，未来5周内的原料的价格有三种，这些价格的出现概率可以估计，如下表。该部分由于生产需要，必须在5周内采购这批原料。如果第一周价格很高，可以等到第2周；同样的，第2周如果仍对价格不满意，可以等到第3周；类似地，未来几周都可能选择购买或者等待，但必须保证第5周时采购了该原料。试问该选择哪种采购方案，才能使得采购费用最小？
500
470
450
概率
价格
解：建立动态规划。按照采购周期分为5个阶段，将每周的价格看作该阶段的状态。假设状态变量sk表示第k周的实际价格，决策变量xk表示第k周是否采购的0-1变量。如决定采购，则xk=1；如选择等待，则xk=0。用skE表示第k周等待，而在以后采取最优决策时采购价格的期望值。
根据定义，
动态规划基本方程如下：
第五阶段：
因为如果前4周都没有买，那第5周必须购买，因
此有f5(s5)=s5，即f5(450)=450；f5(470)=470；
f5(500)=500。
第四阶段：
下面考虑第4周的情况。
如第4周购买，则需花费s4；如果不买，则必须
在第5周购买。在第5周采购的费用的期望值为
于是 ，有
故第4周的最优决策为
同理，考虑第3周的最优决策。
第三阶段：
如果第3周采购，则需花费s3；也要和第3周后再
采购的费用的期望值作比较。
于是 ，有
故第3周的最优决策为
第二阶段：
同理可得
故第2周的最优决策为
第一阶段：
同理可得
第1周的最优决策为
由上可知，最优的采购策略为：在第1、2、3周的市场价格为450时，应该立即采购，否则等待；在第4周时，若市场价格为450或470时，应该采购，否则等待。若等到第五周，只能采购。
