运筹学
Operational Research
天津大学管理学院
教师简介
张小涛，博士，副教授
研究方向：
计算实验金融，中小企业融资
Email：zxt@
zxttju@
运筹学简介
什么是运筹学?
运筹学的简史
运筹学的分支有哪些?
运筹学研究的一般程序
课程要求
*
古籍中的运筹问题
田忌赛马：田忌与齐王多次赛马，屡战屡败，田忌的一位谋士比较了六种对策后建议……
——《十万个为什么.数学分册》
最早记载的《对策论》范例。
*
古籍中的运筹问题
祥符中,禁火。时丁晋公主营复宫室,患取土远,公乃令凿通衢取土,不日皆成巨堑。乃决汴水入堑中,引诸道竹木排筏及船运杂材,尽自堑中入至宫门。事毕,却以斥弃瓦砾灰壤实于堑中,复为街衢。一举而三役济,计省费以亿万计。
——沈括《梦溪笔谈.补笔谈卷二.权智》
*
“运筹”的出典
据《史记》记载：汉高祖刘邦称赞张良：运筹策帷帐中，决胜千里外，子房功也。
——司马迁《史记·留侯世家》
“筹”是古代比算盘还早的计算工具之一。“运筹”是计划、安排、比较、决策优化的一个过程。
英文名：Operational Research,港台地区译为：《作业研究》、《运作研究》。五十年代末华罗庚等人介绍国外这一门新兴学科时就建议定名为：运筹学。近几十年来随着计算机的普及它的应用越来越广泛。其作用越来越被人们所认识。
大学里为什么要开设《运筹学》呢?请自己考虑。
*
我国当代数学家在《运筹学》中的贡献
1957年起中科院一批数学家作了许多令国际同行称道的工作：如物资调运问题。
20世纪70年代华罗庚先生在中国大力创导推广“统筹学”当时就获得第一代领导人的首肯，在国际数学界被称为是全世界最大而有成果的一次普及数学的创举。
凡是讲图论的优化的教科书，多半有专门的一章名：Chinese Postman Problems,其中无一例外的要提到管梅谷先生的杰出工作：中国邮递员问题(CPP)。
*
运筹学（Operational Research)
运筹学是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设计各种系统的一门学科。运筹学对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。
*
运筹学的应用
经济、工商管理；
计算机算法的设计；
数学理论；
军事；
工业；农、林、牧、渔业;
医学、生物、理化、遗传；
工程计划、安排等“优化”;
学习、日常生活、旅游等。
*
运筹学的发展：三个来源
军 事
管 理
经 济
军事：运筹学的主要发源地
古代军事运筹学思想
中国古代的“孙子兵法”在质的论断中渗透着量的分析（1981年美国军事运筹学会出版了一本书，书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家），中国古代运筹学思想的例子还有：田忌赛马、围魏救赵、行军运粮，等等。
国外历史上的阿基米德、伽利略研究过作战问题；第一次世界大战时，英国的兰彻斯特（Lanchester）提出了战斗方程，指出了数量优势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。
运筹学的正式产生：第二次世界大战
鲍德西（Bawdsey）雷达站的研究
1939年，以Blackett为首的一个研究小组（代号“Blackett 马戏团”），研究如何改进英国的空防系统，提高英国本土防空能力。
Blackett备忘录
1941年12月， Blackett应盟国政府的要求，写了五份题为“Scientists at the Operational Level”的简短备忘录，建议在各大指挥部建立运筹学小组，此建议被迅速采纳。据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。
大西洋反潜战：研究如何打破德国对英吉利海峡的海上封锁
英国战斗机中队援法的决策
管理
泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图”、吉尔布雷思夫妇的动作研究等
爱尔朗（Erlong）的排队论公式
1909－1920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是1909年的论文“概率与电话通话理论”，开创了运筹学的重要分支－－排队论。
经济（数理经济学）
Von Neumann 与对策论
1932年，Von Neumann提出一个广义经济平衡模型；1939年，提出了一个属于宏观经济优化的控制论模型；1944年，与Morgenstern共著的《对策论与经济行为》开创了对策论分支。
康托洛维奇与“生产组织与计划中的数学方法”
30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪称运筹学的先驱著作－－《生产组织与计划中的数学方法》，其思想和模型被归入线性规划范畴。
运筹学的性质和特点
应用科学－“应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”。
运筹学的特点
定量化分析
多学科交叉，如综合利用了心理学、经济学、物理等方法
最优决策
管理运筹学的工作程序
明确问题
问题分类
建立数学模型
求解数学模型
结果分析
实施
运筹学的分支
规划论(分线性、非线性、整数、目标、动态及随机规划等)
图论与网络优化；
排队论、存储论、搜索论；
对策论(博弈论)、；
可靠性理论;
全面质量管理(TQC);
计划评审、维修更新理论等。
课程教材：
胡运权，运筹学教程，北京：清华大学出版社，2007；
主要参考书：
[1] 丁以中主编，管理科学---运用Spreadsheet建模和求解，北京：清华大学出版社，2003；
[2] [美]弗雷德里克·S·希利尔（Frederick S Hillier）,任建标译,数据、模型与决策（原书名 Introduction to Management Science），北京：中国财政经济出版社，2004；
[3]谢金星， 优化建模LINDO/LINGO软件，清华大学出版社
[4] 钱颂迪等，运筹学，北京：清华大学出版社，1990；
[5]吴育华,杜纲. 《管理科学基础》，天津大学出版社。
主要授课内容：
线性规划:模型与图解法，单纯形法，对偶与灵敏度分析，运输问题，线性整数规划
图论与网络分析
网络计划
动态规划
风险型决策
排队论
随机模拟
课程基本要求
掌握好基本概念、主要模型形式及其特点、适当的建模能力，必要的算法原理及简单的计算
具备计算机解题的基本能力
认真听课，勤于思考，多看书
每周一交作业，独立完成
闭卷考试
有问题请Email联系
第一章 线性规划
（Linear Programming，简称LP）
§1 线性规划的模型与图解法
一、LP问题及其数学模型
例1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗数据如表，试拟定使总收入最大的生产计划。
12
7
单价
300
10
3
油
200
5
4
电
360
4
9
煤
资源限制
乙
甲
产品
资源
甲
乙
资源限制
煤
9
4
360
电
4
5
200
油
3
10
300
单价
7
12
产品
资源
线性规划模型三要素：
（1）决策变量
设甲产品生产x1，乙产品生产x2
（2）目标函数
Max Z=7 x1 +12x2
（3）约束条件
9 x1 +4x2≤360
4x1 +5x2 ≤200
3 x1 +10x2 ≤300
x1 , x2≥0
.
返回
Subject To， 意为“使其满足”
Max （Min） Z = c1 x1 + c2 x2 + … + cn xn
a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1
……
am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm
x1 ，x2 ，… ，xn ≥ 0
.
LP模型的一般形式
矩阵表示
Max Z = CX
AX ≤ b
X ≥ 0
.
其中:
X= (x1,x2, …, xn) T 为决策变量 C=(c1,c2, …, cn) 称为价格系数
A=(aij)m×n 称为技术系数
b= (b1,b2, …, bm) T 称为资源系数
线性规划问题隐含的假定：
比例性假定
可加性假定
连续性假定
确定性假定
线性规划问题隐含的假定：
比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。
可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。
连续性假定：线性规划问题中的决策变量应取连续值。
确定性假定：线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。
例2 某市今年要兴建大量住宅,已知有三种住宅体系可以
大量兴建，各体系资源用量及今年供应量见下表：
要求在充分利用各种资源条件下使建造住宅的总面积为最
大(即求安排各住宅多少m2)，求建造方案。
水泥
(公斤/m2)
4000
(千工日)
147000
(千块)
150000
(吨)
20000
(吨)
110000
(千元)
资源限量
——
180
25
120
大模住宅
——
190
30
135
壁板住宅
210
110
12
105
砖混住宅
人工
(工日/m2)
砖
(块/m2)
钢材
(公斤/m2)
造价
(元/m2)
资源
住宅体系
解: 设今年计划修建砖混、壁板、大模住宅各为
x1,x2,x3 m2, z为总面积,则本问题的数学模型为:
前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。
课堂练习
某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）
A
B
C
D
价格
M
0
300
N
200
每头日需
10
5
8
7
养分
饲料
课堂练习
某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）
A
B
C
D
价格
M
0
300
N
200
每头日需
10
5
8
7
养分
饲料
答案：设购买M饲料x1，N饲料x2
x1 +≥10
+ ≥5
+ ≥8
≥7
x1 , x2≥0
.
Min Z=300 x1 +200x2
思考题
二、线性规划的图解法
1. 步骤
（1）作约束的图形——可行域
可行解的集合
①先作非负约束
②再作资源约束
9x1+4x2=360
4x1+5x2=200
3x1+10x2=300
公共部分，即为可行域
例：煤电油例
Max Z=7 x1 +12x2
9 x1 +4x2≤360
4x1 +5x2 ≤200
3 x1 +10x2 ≤300
x1 , x2≥0
.
x1
x2
40
20
60
80
100
20
40
60
80
100
0
（2）作目标函数的等值线
①给z不同的值，作相应直线，判断出z增大时，直线的移动方向
②将直线向增大方向移动，直至可行域边界，交点X*即为最优解。
7x1+12x2=84
7x1+12x2=168
如：令7 x1 +12x2=84
7 x1 +12x2=168
9x1+4x2=360
4x1+5x2=200
3x1+10x2=300
x1
x2
40
20
60
80
100
20
40
60
80
100
0
X*=（20，24），
Z*=428
最优解： x1 = 0， x2 = 1
最优目标值 z = 3
课堂练习
图解法求解线性规划
0
1
2
3
4
1
2
3
4
x
1
x
2
O
-1
-2
(1)
(2)
(3)
2. LP 解的几种情况
（1）唯一解
（2）多重最优解
（3）无可行解
注：出现（3）、（4）情况时，建模有问题
（4）无有限最优解
补充知识：凸集
凸集：在点集中任取两点，则其连线仍在其中。
即没有凹入的部分；没有空洞。
⑴
⑵
⑶
⑷
⑸
⑹
在凸集⑵中，点A，B，C，D称为极点（或顶点）。
A
B
C
D
从图解法中我们了解到以下事实：
①若LP问题的可行域存在，则可行域一定是凸集。
②若LP问题的最优解存在，则最优解或最优解之一（如果有
无穷多最优解的话）一定是可行域凸集的某个极点（顶
点）。
思路：①最优解先在可行域中找。（可行域为空集，则无可
行解，故无最优解。）
②最优解在可行域的极点中找。
③极点是有限个，若两个极点都是最优解，则两个极点所连
线段上的所有点均是最优解）
定义：LP问题的可行域的极点（顶点）称为基本可行解。
三、 线性规划应用举例与软件求解
例1 （下料问题） 某工厂要做100套钢架，每套用长为 m, m, m的圆钢各一根。已知原料每根长 m，问：应如何下料，可使所用原料最省？
例1 （下料问题） 某工厂要做100套钢架，每套用长为 m, m, m的圆钢各一根。已知原料每根长 m，问：应如何下料，可使所用原料最省？
方案
余料
m
m
2
0
1
Ⅰ
1
2
0
Ⅱ
1
1
1
Ⅲ
1
0
3
0
Ⅳ
0
3
0
Ⅴ
0
2
2
Ⅵ
0
1
3
Ⅶ
0
0
4
Ⅷ
50
10
30
2x1 + x2 + x3 + x4 ≥ 100
2x2 + x3 + 3x5 + 2x6 + x7 ≥ 100
x1 + x3+ 3x4 + 2x6 + 3x7 + 4x8 ≥ 100
x1, x2, x3, x4, x5, x6, x7, x8 ≥ 0
设 x1,x2,x3,x4,x5,x6,x7,x8 分别为上述8种方案下料的原材料根数，
建立如下的LP模型：
最优解为： x1=10,x2=50,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0
min Z =x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8
.
余料
方案
2
0
1
Ⅰ
1
2
0
Ⅱ
1
1
1
Ⅲ
1
0
3
0
Ⅳ
0
3
0
Ⅴ
0
2
2
Ⅵ
0
1
3
Ⅶ
0
0
4
Ⅷ
第二节 单纯形法
单纯形法是求解线性规划的主要算法，1947
年由美国斯坦福大学教授丹捷格（）
提出。
尽管在其后的几十年中，又有一些算法问世，
但单纯形法以其简单实用的特色始终保持着绝对
的“市场”占有率。
1.线性规划的标准型
用单纯形法求解线性规划的前提是先将模
型化为标准型：
标准型的特征：Max型、等式约束、非负约束
一、单纯形法的预备知识
非标准形式如何化为标准
1) Min型化为Max型
加负号
因为，求一个函数
的极小点，等价于求该
函数的负函数的极大点。
注意： Min型化为Max型求解后，最优解不变，但最优值差负号。
2) 不等式约束化为等式约束
分析：以例1中煤的约束为例
之所以“不等”是因为左右两边有一个差额，称为“松
弛量”，若在左边加上这个松弛量，则化为等式。而这
个松弛量也是变量，记为X3 ，则有
X3称为松弛变量。问题：它的实际意义是什么？
—— 煤资源的“剩余”。
练习：请将例1的约束化为标准型
解：增加松弛变量
则约束化为
易见，增加的松弛变量的系数恰构成一个单位阵I。
一般地，记松弛变量的向量为 Xs，则
问题：松弛变量在目标中的系数为何？
—— 0。
3) 当模型中有某变量 xk 没有非负要求，称
为自由变量, 则可令
化为标准型。
复习：非齐次线性方程组解
例：解非齐次线性方程组
增广矩阵
（1）
若线性方程组没有现成的基，可利用增广矩阵的行初等变换
法找到一组基。
为基变量。
称
其变量个数=
此方程组的解为
其中
为任意实数。
为非基变量，或自由变量。
称
称非基变量
为0的解（15，24，5，0，0）叫基解。
若对（1）式中的变量再加上非负限制
其解为
由
的非负性知：
（2）
从而
解域为
注意：此时的
已经不是任意实数。
不是自由变量了。
而对于带有非负约束的方程组
解的每个分量都是非负数，就叫做可行解。
如果基解是可行的，就叫基可行解。
基可行解所对应的基称为可行基。
非基
可
行 最优基
基
非
可
行
基
四种形式的基之间的关系为：
基与解的对应关系：
非可行解
可
行 基本
解
可行解
基本解
解与解之间的关系为：
基解
基
可行基
基可行解
最优基
基最优解
所对应的解
例如
是可行解。
所对应的解
是基解。
也是可行解，故而是基本可行解。
2.基本概念
（1）可行解与最优解
直观上，可行解是可行域中的点，是一个可行的方案；
最优解是可行域的角点，是一个最优的方案。
（2）基矩阵与基变量
基矩阵(简称基)：系数阵A中的m阶可逆子阵，记
为B；其余部分称为非基矩阵，记为N。
基向量：基B中的列；其余称非基向量。
基变量：与基向量Pj对应的决策变量xj，记其组成的
向量为XB；与非基向量对应的变量称非基变 量，记其组成的向量为XN。
—— 6个。
一般地，m×n 阶矩阵A中基的个数最多有多少个？
问题：本例的A中一共有几个基？
（3）基本解与基本可行解
可见：一个基本解是由一个基决定的。
注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。
称非负的基本解为基本可行解（简称基可行解）。
例4：在上例中
求相应于基B1和B2的基本解，它们是否基本可行解？
上二组概念间的联系：
系数阵A中可找出若干个基B
每个基B都对应于一个基本解
非负的基本解就是基本可行解
几种解之间的关系：
可行解
基本解
非可行解
基本可行解
问题：基本可行解是可行域中的哪些点？
3.基本定理
（1）线性规划的可行域是一个凸多面体。
（2）线性规划的最优解（若存在的话）必能在可行
域的角点获得。
（3）线性规划可行域的角点与基本可行解一一对应。
二、单纯形法的步骤
确定一个初始基可行解
检验这个基可行解是否最优
寻找一个更好的基可行解
否
是
停止
Dantzig的单纯形法把寻优的目标集中在所有基本可行解
（即可行域顶点）中。
其基本思路是从一个初始的基本可行解出发，寻找一条达到
最优基本可行解的最佳途径。 单纯形法的一般步骤如下：
（1）寻找一个初始的基本可行解。
（2）检查现行的基本可行解是否最优，如果为最优，
则停止迭代，已找到最优解，否则转一步。
（3）移至目标函数值有所改善的另一个基本可行解，
然后转会到步骤（2）。
1.确定初始基可行解
由于基可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个初始可行基B0。
方法：若A中含I，则B0=I；
若A中不含I，则可用人工变量法构
造一个I。
问题：若B0=I，则X0=？
2. 最优性检验
问题：用什么检验？
—— 目标。
问题：非最优的特征为何？
判断现行的基本可行解是否最优
假如已求得一个基本可行解
将这一基本可行解代入目标函数，可求得相应的目标函数值
其中 分别表示基变量和
非基变量所对应的价值系数子向量。
要判定 是否已经达到最大值，只需将
代入目标函数，使目标函数用非基变量
表示，即：
其中 称为非基变量ＸN的检验向量，它的各个分量称为检验数。若σN的每一个检验数均小于等于0，即σN≤0，那么现在的基本可行解就是最优解。
定理1：最优解判别定理
对于线性规划问题
若某个基本可行解所对应的检验向量 ，
则这个基本可行解就是最优解。
定理2：无穷多最优解判别定理
若 是一个基本可行解，所对应的检验向量
，其中存在一个检验数σm+k=0，
则线性规划问题有无穷多最优解。
基本可行解的改进
如果现行的基本可行解Ｘ不是最优解，即在检验向量
中存在正的检验数，则需在原基本可行解Ｘ的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：
先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值），
再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。
由此可得一个新的基本可行解，由
可知，这样的变换一定能使目标函数值有所增加。
换入变量和换出变量的确定：
换入变量的确定— 最大增加原则
假设检验向量 ，
若其中有两个以上的检验数为正，那么为了使目标函数值增加得快些，通常要用“最大增加原则”，即选取最大正检验数所对应的非基变量为换入变量，即若
则选取对应的 为换入变量，
由于 且为最大，
因此当 由零增至正值，
可使目标函数值
最大限度的增加。
换出变量的确定— 最小比值原则
如果确定 为换入变量，方程
其中 为Ａ中与 对应的系数列向量。
现在需在 中确定一个基变量为换出变量。
当 由零慢慢增加到某个值时， 的非负性可能被打破。
为保持解的可行性，可以按最小比值原则确定换出变量：
若
则选取对应的基变量 为换出变量。
定理3：无最优解判别定理
若 是一个基本可行解，有一个检验数 ，
但是 ，则该线性规划问题无最优解。
证：令 ，则得新的可行解
将上式代入
因为 , 故当λ→+∞时，Z→+∞。
寻找更好的基可行解
由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基B0变换为下一个新的基B1，因
此，本步骤也称为基变换。
（基变换）
进基
出基
以例1为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。
（1）先将模型化为标准型
(2) 确定初始基可行解、检验
（3）换基、计算下一个基可行解、再检验，直至最优
问题：当模型规模较大时，计算量很大。
事实上，单纯形法的实现是在单纯形表上完成的。
三、单纯形表
单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。
回顾单纯形法步骤
单纯形表的主要结构：
问题：第一张表的B-1=？
——单位阵I。
检验数的公式是什么？
例5：用单纯形法求解例1
问题：标准模型的A中是否含I？
——松弛变量系数恰好构成I。
σ的计算:
XB
CB
B-1b
x1
x2
x3
x4
x5
θ
σ
四、单纯形法的实现——单纯形表
例：煤电油例
Max Z=7 x1 +12x2
9 x1 +4x2≤360
4x1 +5x2 ≤200
3 x1 +10x2 ≤300
x1 , x2≥0
.
Max Z=7 x1 +12x2
9 x1 +4x2 +x3 =360
4x1 +5x2 +x4 = 200
3 x1 +10x2 +x5 = 300
x1 ,…,x5≥0
.
化为标准型
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
σ
θ
x5
x4
x3
x2
x1
B-1b
CB
XB
四、单纯形法的实现——单纯形表
例：煤电油例
Max Z=7 x1 +12x2
9 x1 +4x2≤360
4x1 +5x2 ≤200
3 x1 +10x2 ≤300
x1 , x2≥0
.
Max Z=7 x1 +12x2
9 x1 +4x2 +x3 =360
4x1 +5x2 +x4 = 200
3 x1 +10x2 +x5 = 300
x1 ,…,x5≥0
.
化为标准型
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
θ的计算:
40
30
σ
θ
x5
x4
x3
x2
x1
B-1b
CB
XB
四、单纯形法的实现——单纯形表
例：煤电油例
Max Z=7 x1 +12x2
9 x1 +4x2≤360
4x1 +5x2 ≤200
3 x1 +10x2 ≤300
x1 , x2≥0
.
Max Z=7 x1 +12x2
9 x1 +4x2 +x3 =360
4x1 +5x2 +x4 = 200
3 x1 +10x2 +x5 = 300
x1 ,…,x5≥0
.
化为标准型
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
[ ]
枢纽元素
σ
θ
x5
x4
x3
x2
x1
B-1b
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
[ ]
x3
x4
x2
0
0
12
30
1
0
0
σ
以10为主元进行初等行变换
50
0
0
1
240
0
1
0
0
0
0
即:
σ
θ
x5
x4
x3
x2
x1
B-1b
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
[ ]
x3
x4
x2
0
0
12
30
1
0
0
σ
以10为主元进行初等行变换
50
0
0
1
240
0
1
0
0
0
0
即:
20
100
σ
θ
x5
x4
x3
x2
x1
B-1b
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
[ ]
x3
x4
x2
0
0
12
30
1
0
0
σ
以10为主元进行初等行变换
50
0
0
1
240
0
1
0
0
0
0
20
100
[ ]
x3
x1
x2
0
7
12
24
0
1
0
σ
20
1
0
0
84
0
0
1
0
0
0
σ
σ
θ
x5
x4
x3
x2
x1
B-1b
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
[ ]
x3
x4
x2
0
0
12
30
1
0
0
50
0
0
1
240
0
1
0
0
0
0
20
100
[ ]
以 为主元进行初等行变换
x3
x1
x2
0
7
12
24
0
1
0
σ
20
1
0
0
84
0
0
1
0
0
0
σ
σ
θ
x5
x4
x3
x2
x1
B-1b
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
[ ]
x3
x4
x2
0
0
12
30
1
0
0
50
0
0
1
240
0
1
0
0
0
0
20
100
[ ]
∴X*=(20,24,84,0,0)T
Z*=428
例：
用单纯形法求解
Min S= - x1 +2x2
x1 - x2 ≥ - 2
x1 +2x2 ≤6
x1 , x2≥0
.
化为标准型
Max S´= x1 -2x2
-x1 + x2 +x3 = 2
x1 +2x2 +x4= 6
x1 , …,x4≥0
.
XB
CB
B-1b
x1
x2
x3
x4
θ
x3
0
2
-1
1
1
0
不考虑
x4
0
6
[1]
2
0
1
6
σ
1
-2
x3
0
8
0
3
1
1
x1
1
6
1
2
0
1
σ
0
-4
0
-1
∴X*=(6,0,8,0)T
Z*= -6
x3
x1
x2
0
7
12
24
0
1
0
σ
20
1
0
0
84
0
0
1
0
0
0
σ
σ
θ
x5
x4
x3
x2
x1
B-1b
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
x3
x4
x2
0
0
12
30
1
0
0
50
0
0
1
240
0
1
0
0
0
0
20
100
注：单纯形表中的信息
⑴每一列的含义：
B-1(b A)=(B-1b, B-1 P1,…， B-1 Pn)
⑵每个表中的B和B-1的查找：
B从初表中找；
B-1从当前表中找，对应于初表中的I的位置。
以第2个表为例：
⑶终表分析——最优基B* 和(B*)-1的查找
x3
x1
x2
0
7
12
24
0
1
0
σ
20
1
0
0
84
0
0
1
0
0
0
σ
σ
θ
x5
x4
x3
x2
x1
B-1b
CB
XB
x3
x4
x5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12
0
0
0
单纯形表:
7
90
40
30
x3
x4
x2
0
0
12
30
1
0
0
50
0
0
1
240
0
1
0
0
0
0
20
100
注：单纯形表中的信息
借助人工变量求初始的基本可行解
若约束方程组含有“≥”不等式，那么在化标准形时除了在方程式左端减去剩余变量，还必须在左端加上一个非负的人工变量。
因为人工变量是在约束方程已为等式的基础上，人为的加上去的一个新变量，因此加入人工变量后的约束方程组与原约束方程组是不等价的。
加上人工变量以后，线性规划的基本可行解不一定是原线性规划的问题的基本可行解。只有当基本可行解中所有人工变量都为取零值的非基变量时，该基本可行解对原线性规划才有意义。因为此时只需去掉基本可行解中的人工变量部分，剩余部分即为原线性规划的一个基本可行解．而这正是我们引入人工变量的主要目的。
考虑线性规划问题：
为了在约束方程组的系数矩阵中得到一个m阶单位矩阵作为
初始可行基，在每个约束方程组的左端加上一个人工变量
可得到：
————————————————————————
添加了m个人工变量以后，在系数矩阵中得到一个m阶单位矩阵，以该单位矩阵对应的人工变量 为基变量，
即可得到一个初始的基本可行解
这样的基本可行解对原线性规划没有意义的。
但是我们可以从X(0)出发进行迭代，一旦所有的人工变量都从基变量迭代出来，变成只能取零值的非基变量，那么我们实际上已经求得了原线性规划问题的一个初始的基本可行解。
此时可以把所有人工变量剔除，开始正式进入求原线性规划最优解的过程。
大M法
大M法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵I，那么已经得到了一个初始可行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。
为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的负系数-Ｍ。这样只要基变量中还存在人工变量，目标函数就不可能实现极大化。
以后的计算与单纯形表解法相同，Ｍ只需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。
例4、用大M法求解下面的线性规划问题:
解：
首先将原问题化为标准型
添加人工变量 ，并在目标函数中分别赋予-Ｍ
-
0 1 -1/2 -1/2 0 1/2 1/2
3/2
X2
2
1 0 -1/2 1/2 0 1/2 -1/2
1/2
X1
-1
-
-1 1 0 -1 0 0 1
1
X2
2
1/2
2 0 -1 1 0 1 -1
1
X6
-M
1/1
-1 1 0 -1 0 0 1
1
X7
-M
2/1
1 1 -1 0 0 1 0
2
X6
-M
0 0 1/2 3/2 0 -1/2-M -3/2-M
5/2
Z
0 0 1/2 1/2 1 -1/2 -1/2
3/2
X5
0
1+2M 0 -M 2+M 0 0 -2-2M
2-M
Z
2/1
1 0 0 1 1 0 -1
2
X5
0
-1 2+2M -M -M 0 0 0
-3M
Z
3/1
0 1 0 0 1 0 0
3
X5
0
X1 x2 x3 x4 x5 x6 x7
b
XB
CB
θ
-1 2 0 0 0 -M -M
C
0 1 0 0 1 0 0
3
X2
2
1 0 0 1 1 0 -1
2
X4
0
1 1 -1 0 0 1 0
2
X2
2
2 0 -1 1 0 1 -1
1
X4
0
-
0 1 -1/2 -1/2 0 1/2 1/2
3/2
X2
2
1/2/1/2
1 0 -1/2 1/2 0 1/2 -1/2
1/2
X1
-1
-1 0 0 0 -2 -M -M
6
Z
-1 0 1 0 1 -1 0
1
X3
0
-3 0 2 0 0 -2-M -M
4
Z
-1 0 1 0 1 -1 0
1
X5
0
0 0 1/2 3/2 0 -1/2-M -3/2-M
5/2
Z
3/2 /1/2
0 0 1/2 1/2 1 -1/2 -1/2
3/2
X5
0
X1 x2 x3 x4 x5 x6 x7
b
XB
CB
θ
-1 2 0 0 0 -M -M
C
最优解 最优值
两阶段法
两阶段法引入人工变量的目的和原则与大M法相同，所不同的是处理人工变量的方法。
两阶段法的步骤：
求解一个辅助线性规划。目标函数取所有人工变量之和，并取极小化；约束条件为原问题中引入人工变量后包含一个单位矩阵的标准型的约束条件。
如果辅助线性规划存在一个基本可行解，使目标函数的最小值等于零，则所有人工变量都已经“离基”。表明原问题已经得了一个初始的基本可行解，可转入第二阶段继续计算；否则说明原问题没有可行解，可停止计算。
求原问题的最优解。在第一阶段已求得原问题的一个初始基本可行解的基础上，继续用单纯形法求原问题的最优解
例5、用两阶段法求解例4中的线性规划问题。
解：首先将问题化为标准型
添加人工变量x6,x7,并建立辅助线性规划如下：
由于辅助线性规划的目标函数是极小化，因此最优解的判别准则应为：
0 1 -1/2 -1/2 0 1/2 1/2
3/2
X2
0
1 0 -1/2 1/2 0 1/2 -1/2
1/2
X1
0
-
-1 1 0 -1 0 0 1
1
X2
0
1/2
2 0 -1 1 0 1 -1
1
X6
1
1/1
-1 1 0 -1 0 0 1
1
X7
1
2/1
1 1 -1 0 0 1 0
2
X6
1
0 0 0 0 0 1 1
0
W
0 0 1/2 1/2 1 -1/2 -1/2
3/2
X5
0
-2 0 1 -1 0 0 2
1
W
2/1
1 0 0 1 1 0 -1
2
X5
0
0 -2 1 1 0 0 0
3
W
3/1
0 1 0 0 1 0 0
3
X5
0
x1 x2 x3 x4 x5 x6 x7
b
XB
CB
θ
0 0 0 0 0 1 1
C
辅助规划所有检验数：
原问题已得一个初始基本可行解，
由上表可知，通过若干次旋转变换，原问题的约束方程组已变换成包含一个单位矩阵的约束方程组
该约束方程组可作为第二阶段初始约束方程组，将目标函数则还原成原问题的目标函数，可继续利用单纯形表求解。
-1 0 0 0 -2
6
Z
1 0 0 1 1
0 1 0 0 1
-1 0 1 0 1
2
3
1
X4
X2
X3
0
2
0
-3 0 2 0 0
4
Z
2 0 -1 1 0
1 1 -1 0 0
-1 0 1 0 1
1
2
1
X4
X2
X5
0
2
0
0 0 1/2 3/2 0
5/2
Z
1/2/1/2
-
3/2/1/2
1 0 -1/2 1/2 0
0 1 -1/2 -1/2 0
0 0 1/2 1/2 1
1/2
3/2
3/2
X1
X2
X5
-1
2
0
x1 x2 x3 x4 x5
b
XB
CB
θ
-1 2 0 0 0
C
可得最优解 ，目标函数值maxZ=6，
与用大M法的结果完全相同。
单纯形表与线性规划问题的讨论
无可行解
通过大Ｍ法或两阶段法求初始的基本可行解。但是如果在大Ｍ法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。
人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。此时线性规划问题的可行域为空集。
例6、求解下列线性规划问题
解：
首先将问题化为标准型
令 ，则
故引入人工变量 ，
并利用大M法求解
C
-3 -2 -1 0 0 0 -M -M
CB
XB
b
x1 x2 x3 x4 x5 x6 x7 x8
θ
0
-M
-M
x4
x7
x8
6
4
3
1 1 1 1 0 0 0 0
1 0 -1 0 -1 0 1 0
0 1 -1 0 0 -1 0 1
6/1
-
3/1
Z’
-7M
-6-4M
-15-M
-3+M -2+M -1-2M 0 -M -M 0 0
0
-M
-2
x4
x7
x2
3
4
3
1 0 2 1 0 1 0 -1
1 0 -1 0 -1 0 1 0
0 1 -1 0 0 -1 0 1
3/1
4/1
-
Z’
Z’
-3+M 0 -3-M 0 -M -2 0 2-M
-3
-M
-2
x1
x7
x2
3
1
3
1 0 2 1 0 1 0 -1
0 0 -3 -1 -1 -1 1 1
0 1 -1 0 0 -1 0 1
0 0 3-3M 3-M -M 1-M 0 -1
在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人工变量x7=1为基变量，所以原线性规划不存在可行解。
无最优解
无最优解与无可行解时两个不同的概念。
无可行解是指原规划不存在可行解，从几何的角度解释是指
线性规划问题的可行域为空集；
无最优解则是指线性规划问题存在可行解，但是可行解的目
标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。
判别方法：无最优解判别定理
在求解极大化的线性规划问题过程中，若某单纯形表的检验
行存在某个大于零的检验数，但是该检验数所对应的非基变量
的系数列向量的全部系数都为负数或零，则该线性规划问题
无最优解，
可以
可以
例7、试用单纯形法求解下列线性规划问题：
解：引入松弛变量x3,x4化为标准型
C
2 2 0 0
θ
C
XB
B
x1
x2
x3
x4
0
X3
1
-1
1
1
0
0
X4
2
-1/2
1
0
1
Z
0
2
2
0
0
因
但
所以原问题
无最优解
退化解
当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解。
产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值θ，那么在下次迭代中就会出现一个甚至多个基变量等于零。
遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换出变量时，目标函数并不能因此得到任何改变（由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可行域的同一个顶点，
解决的办法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一定能避免循环现象的产生（摄动法原理）。
例8、求解下述线性规划问题：
解：引入松弛变量
化标准型
0
0
0
-24
2
-80
3
0
Z
-5
-6
0
-42
0
-8
0
5
Z
1
0
0
0
1
0
0
1
x3
2
1
2
0
6
0
-24
1
1
x1
3
3
2
1
30
0
-8
0
3
x5
0
0
-3
0
-42
5
-8
0
0
Z
1
1
0
0
1
0
0
1
x7
0
0
1
0
6
-1
-24
1
0
x1
3
0
-1
1
30
-3
-8
0
0
x5
0
-
1
1
0
0
1
0
0
1
x7
0
0
0
1
0
6
-1
-24
1
0
x6
0
0
0
0
1
36
-4
-32
1
0
x5
0
x7
x6
x5
x4
x3
x2
x1
b
XB
CB
0
0
0
-24
2
-80
3
C
θ
第一次迭代中使用了摄动法原理，选择下标为6的基变量x6离基。
可得最优解 ，目标函数值maxZ=５，
无穷多最优解
无穷多最优解判别原理：
若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。
例３：最优表：
非基变量检验
数 ， 所以有无穷多
最优解。
最优解集为可行域两个顶点的凸组合：
C
1 2 0 0 0
θ
CB
XB
b
x1 x2 x3 x4 x5
0
2
1
x3
x2
x1
2
3
2
0 0 1 2 -1
0 1 0 1 0
1 0 0 -2 1
2/2
3/1
-
Z’
8
0 0 0 0 -1
改进单纯形法的特点
利用单纯形表求解线性规划时，每一次迭代都把整个单纯形表计算一遍，事实上我们关心的只是以下一些数据：
基本可行解 ，其相应的目标函数值 ，
非基变量检验数 ，及其换入变量 ，
设
主元列元素 ，及其换出变量 ，
设
利用它们可得到一组新的基变量以及新的可行基Ｂ1。
改进单纯形法
为基变量下标
为非基变量下标
对任一基本可行解Ｘ，只要知道 ，上述关键数据都可以从线性规划问题的初始数据直接计算出来。因此如何计算基本可行解Ｘ对应的可行基Ｂ的逆阵 成为改进单纯形法的关键．
改进单纯形法推导出从可行基Ｂ变换到Ｂ1时， 到
的变换公式。当初始可行基为单位矩阵Ι时，变换公式将更具有优越性，因为这样可以避免矩阵求逆的麻烦
以下推导从 到 的变换公式：
假设当前基 ，
基变换中用非基变量 取代基变量
可得新基
前后二个基相比仅相差一列，且
比较以上二式，可得
其中 表示第 个元素为1，其它元素均为零的单位列向量，
为主元列元素。
假设 ，
则
第 列（换出变量 对应列 ）
第 行
所以由
主元素
改进单纯形法的步骤
（1） 根据给出的线性规划问题的标准型，确定初始基变量和初始可行基Ｂ。求初始可行基B的逆阵Ｂ-1，得初始基本可行解
。
（2）计算单纯形乘子 ，得目标函数当前值
（3） 计算非基变量检验数 ，
若σN≤0，则当前解已是最优解，停止计算；否则转下一步。
（4） 根据 ，确定非基变量 为换入变量，计算 ,若 ≤0，则问题没有有限最优解，停止计算，
否则转下一步。
（5） 根据 ，确定基变量
为换出变量。
（6） 用 替代 得新基Ｂ1，由变换公式
计算新基的逆阵Ｂ1-1，求出新的基本可行解
其中 为变换矩阵，构造方法是：
从一个单位矩阵出发，把换出变量 在基B中的对应列的单位
向量，替换成换入变量 对应的系数列向量 ，并做如下变形，
主元素 （应在主对角线上）取倒数，其它元素除以主元素
并取相反数。
重复（2）～（6）直至求得最优解。
换入
无界解
换出
≤０
≤０
①
②
④
③
⑤
最优解
初始基
新基
⑥
例9、试用改进单纯形法求解
解：
（１）观察法确定
， 为基变量 为非基变量
（2）计算单纯行乘子
目标函数当前值
（3）非基变量检验数
(4） 选择换入变量
故 为换入变量。计算
(５)确定换出变量
确定 为换出变量，主元素＝２
(6) 用 代替 得新可行基 为基变量，
为非基变量，
重复以上步骤，进入第二循环
(1)
(2)
(3)
(4) 选择 换入变量
(5)
选择 换出变量,主元素＝
(6) 用 代替 得新可行基
为基变量，
为非基变量，
进入第三循环.
(1)
(2)
(3)
非基变量对应的检验数全部非正，
故当前解 即为最优解，
相应的目标函数最优值 。
六、单纯形法总结
1、Min型单纯形表与Max型的区别仅在于：
令 σk=min{σj ≤0}的xk进基，当σ ≥0时最优。
2、解的几种情况及其在单纯形表上的体现（讨论Max型）
唯一
最优解
σj ≤0,
非基σ<0
多重
最优解
σj ≤0
有非基σk=0
无界解
有σk >0
但B-1Pk ≤ 0
无可行解
用大M法求解，最优基中含有X人
退化解
最优解中某基变量为0
第三节 对偶问题与灵敏度分析
一、对偶问题及其模型
例7：回顾例1
这时有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少。试建立购买者的线性规划模型。
例7称为例1的对偶问题，记为（D），例1称为例7的原问题,记为（P）。
对偶模型的一般式
以例7为例，原问题为
（P）
（D）
这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系：
原问题（P） 对偶问题 （D）
目标max型 目标min型
有n个变量（非负） 有n个约束（大于等于）
有m个约束 （小于等于） 有m个变量（非负）
价格系数 资源向量
资源向量 价格系数
技术系数矩阵 技术系数矩阵的转置
此外，还有一种情形
原问题（P） 对偶问题 （D）
第j个变量为自由变量 第j个约束为等式约束
第i个约束为等式约束 第i个变量为自由变量
例8：写出下面线性规划的对偶规划模型：
例8：写出下面线性规划的对偶规划模型：
min Z’= - CX
- AX≤- b
X ≥0
对称性定理：对偶问题的对偶是原问题。
min W= Y b
YA ≥ C
Y ≤ 0
max Z=C
AX≥b
X ≥0
对偶的定义
对偶的定义
max W’ = -Yb
YA≥ C
Y ≤ 0
二、对偶问题的性质
弱对偶原理：设 和 分别是问题（P）和（D）的可行解，则必有
推论⑴：若 和 分别是问题（P）和（D）的可行解，则 是（D）的目标函数最小值的一个下界； 是（P）的目标函数最大值的一个上界。
对偶问题的性质
关于无界性有如下结论：
问题无界
无可
行解
无可
行解
问题无界
对偶问题
原问题
无界
如：
（原）
无可
行解
（对）
对偶问题的性质
推论⑵：在一对对偶问题(P)和(D)中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。
推论⑶：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行（如D），则该可行的问题无界。
例1
试估计它们目标函数的界，并验证弱对偶性原理。
（P）
对偶问题的性质
解：
（D）
由观察可知： ， ，分别是（P）和（D）的可行解。Z=10 ，W=40，故有 ，弱对偶定理成立。由推论⑴可知，W 的最小值不能小于10，Z 的最大值不能超过40。
对偶问题的性质
（P）
（D）
考虑
4.对偶定理 若（P）有最优解，则（D）也有最优解，
且最优值相同。
证：对（P）增加松弛变量， 化为
设其最优基为B，终表为
其检验数为
问题：(1) 由对偶定理可知，对偶问题最优解的表达式 Y* =？
(2) 求Y*是否有必要重新求解（ D）？
—— CBB-1
—— 不必。可以从原问题（P）的单纯形终表获得。
例如，已知
的终表为
请指出其对偶问题的最优解和最优值。
5.互补松弛定理
y1… yi… ym ym+1 … ym+j … yn+m
x1 … xj … xn xn+1…xn+i…xn+m
对偶问题的变量 对偶问题的松弛变量
原始问题的变量 原始问题的松弛变量
xjym+j=0 yixn+i=0 (i=1,2,…,m; j=1,2,…,n)
在一对变量中，其中一个大于0，另一个一定等于0
直观上
定义：在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi 增加一个单位时，所引起的目标函数最优值Z* 的改变量y*i称为第i个约束条件的影子价格，又称为边际价格。
影子价格
C
CB
CN
0
CB
XB
b
XB
XN
XS
CB
XB
B-1b
I
B-1N
B-1
Z
－CB B-1b
0
CN－CB B-1N
－CB B-1
设：B是问题 P的最优基，由前式可知，
Z*=CB B-1b = Y*b
=y*1b1+ y*2b2+…+y*Ibi+…+y*mbm
当bi 变为bi+1 时（其余右端项不变，也不影响B）
影子价格
目标函数最优值变为：
Z′*= y*1b1+ y*2b2+…+y*I （ bi+1 ）+…+y*mbm
∴ △Z*= Z′*－ Z* = y*i
也可以写成：
即y*i 表示Z*对 bi的变化率。
其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi 就是第 i 个约束条件的影子价格。
也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。
若第 i 种资源的单位市场价格为mi ，当yi > mi 时，企业愿意购进这种资源，单位纯利为yi－mi ，则有利可图；如果yi < mi ，则企业有偿转让这种资源，可获单位纯利为mi－yi ，否则企业无利可图，甚至亏损。
影子价格
影子价格
0
10 20 30 40 50 60
10 2 0 3 0 4 0 50
x2
x1
1
2
3
( 50/7. 200/7 )
多了 32/7
0
10 20 30 40 50 60
10 2 0 3 0 4 0 50
x2
x1
1
2
3
( 50/7. 200/7 )
x1
0
10 20 30 40 50 60
10 2 0 3 0 4 0 50
x2
1
2
3
( 55/7. 199/7 )
影子价格
0
10 20 30 40 50 60
10 2 0 3 0 4 0 50
x2
x1
1
2
3
( 47/7. 202/7 )
多了 6/7
影子价格
6. 对偶问题的经济解释（1）对偶最优解的经济解释——资源的影子价格（Shadow Price）
CBB-1 —— 对偶问题的最优解 —— 买主的最低出价；
—— 原问题资源的影子价格 —— 当该资源增加1单
位时引起的总收入的增量——卖主的内控价格。
例10：例1（煤电油例）的单纯形终表如下：
（1）请指出资源煤电油的影子价格，并解释其经济意义。
（2）由单纯形终表还可得到哪些有用的信息？
例10：例1（煤电油例）的单纯形终表如下：
（1）请指出资源煤、电、油的影子价格，并解释其经济意义。
（2）由单纯形终表还可得到哪些有用的信息？
解：（1）煤、电、油的影子价格分别是0、、；
其经济意义是当煤、电、油分别增加1单位时可使总
收入分别增加0 、、。
（2）由单纯形终表还可得到：原问题的最优生产计划、最大收入、资源剩余，对偶问题的最低购买价格、最少的购买费用等。
y1
y2
ym
（2）对偶约束的经济解释——产品的机会成本 (Opportunity Cost)
机会成本
表示减少一件产品所节省的资源可以增加的利润
增加单位资源可以增加的利润
减少一件产品可以节省的资源
机会成本
利润
差额成本
（3）对偶松弛变量的经济解释——产品的差额成本（Reduced Cost）
差额成本=机会成本 － 利润
在利润最大化的生产计划中
（1）影子价格大于0的资源没有剩余；
（2）有剩余的资源影子价格等于0；
（3）安排生产的产品机会成本等于利润；
（4）机会成本大于利润的产品不安排生产。
（4）互补松弛关系的经济解释
对偶单纯形法
基本思想
若保持对偶问题的解是基可行解，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也就得到了最优解。这种方法的优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。
基本原理
对于原问题
设B是一个基，不失一般性,令 ，它对应的基变量为 。当非基变量都为零时，可以得到 。若在 中至少有一个负分量，设 ，并且在单纯形表的检验数行中的检验数都非正，即对偶问题保持可行解，它的各分量是:
①对应基变量的检验数是
②对应非基变量的检验数是
每次迭代是将基变量中的负分量取出，去替换非基变量中的，经过基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近，当原问题得到可行解时，便得到了最优解。
计算步骤
①列出初始单纯形表，检查b列中的各分量，若都为非负，且检验数都为非正，则已得到最优解。若b列中至少有一个负分量，检验数保持非正，进行以下计算。
②确定换出变量。按照法则
确定对应的基变量为换出变量。
③确定换入变量。 若xj所在行有负系数，计算
所对应的非基变量xk为换入变量。
④以 为主元素，按原单纯形法迭代运算，得新单纯形表。
⑤重复① ～ ④的步骤，直至求得最优解。
例：试用对偶单纯形法求解如下线性规划问题
首先将该问题化为
-2
-3
-4
0
0
CB
XB
b
X1
X2
X3
X4
X5
0
0
X4
X5
-3
-4
-1
[-2]
-2
1
-1
3
1
0
0
1
-2
-3
-4
0
0
初始单纯形表，如表所示
表
b列各行为负，进行迭代计算，确定换出变量
故X3为换出变量 。
故X1为换入变量。换入、换出变量所在列、行的交叉处“2”为主元项。进行迭代运算，得表。
-2
-3
-4
0
0
CB
XB
b
X1
X2
X3
X4
X5
0
-2
X4
X1
-1
2
0
1
[-5/2]
-1/2
1/2
3/2
1
0
-1/2
-1/2
0
-4
-1
0
-1
表
从表可看出，b列中仍有负分量，继续迭代计算，重复上述步骤，得表。 表
-2
-3
-4
0
0
CB
XB
b
X1
X2
X3
X4
X5
-3
-2
X2
X1
-2/5
11/5
0
1
1
0
-1/5
7/5
-2/5
-1/5
1/5
-2/5
0
0
-3/5
-8/5
-1/5
在表中，b列各分量全为非负，检验数全为非正，故问题的最优解为 ，其对偶问题的最优解为 。
三、灵敏度分析
讨论模型的系数或变量发生小的变化时对解的影响
（如它们在何范围内变化时可使原最优解或最优基不变？）
我们主要讨论C、b和变量结构变化时对解的影响。
对解怎样影响？—— 影响解的 - 最优性
- 可行性
1. b变化时的分析
2. C变化时的分析
3.增加新变量时的分析
主要讨论增加新变量xn+1是否有利。经济意义是第n+1种新产品是否应当投产，数学意义是xn+1是否应进基。
经济意义：
市场价
影子价
例11：在例1（煤电油例）中，其单纯形终表如下：
（1）电的影子价格是多少？使最优基仍适用的电的变
化范围为何？
（2）若有人愿以每度1元的价格向该厂供应25度电，是
否值得接受？
（3）甲产品的价格在何范围内变化时，现最优解不变？
（4）若现又考虑一新产品丙，其资源单耗为10，2，5，
售价为，问该产品是否可投产？
例11：在例1（煤电油例）中，其单纯形终表如下：
（1）电的影子价格是多少？使最优基仍适用的电的变
化范围为何？
解：（1）电的影子价格是。
例11：在例1（煤电油例）中，其单纯形终表如下：
（2）若有人愿以每度1元的价格向该厂供应25度电，是
否值得接受？
解：（2）值得。
因25在B的适用范围内（即影子价格适用），且
>0。
例11：在例1（煤电油例）中，其单纯形终表如下：
（3）甲产品的价格在何范围内变化时，现最优解不变？
解：甲产品的价格c1是基变量的价格系数。
例11：在例1（煤电油例）中，其单纯形终表如下：
（4）若现又考虑一新产品丙，其资源单耗为10，2，5，
售价为，问该产品是否可投产？
故丙产品可以投产。
首先将线性规划与经济问题联系起来的是
（库普曼）和
（康脱罗维奇）
二人因此而共同分享了1975年的第7届诺贝尔经
济学奖。
求解线性规划的计算机软件举例——LINDO、EXCEL
LINDO可以从下面的网址下载：
LINDO由美国芝加哥大学开发，可求解线性规划和线性
整数规划等。其可按自然格式输入模型，使用方便。
输入例 ：MAX 2X+3Y
？ST
？4X+9Y<9
？7X+6Y<13
？END
：GO
DO RANGE (SENSITIVITY) ANALYSIS?
？Y
可用HELP命令
得到帮助。
计算结果说明：
REDUCED COST 为使该变量进基，其价格系数至少应
增加的数值；
SLACK OR SUPLUS 松弛或剩余变量；
DUAL PRICES 影子价格;
ALLOWABLE INCREASE 灵敏度分析中可使最优基不
变的系数可增量之上界；
ALLOWABLE DECREASE 灵敏度分析中可使最优基不
变的系数可减量之上界；
使用EXCEL求解线性规划
-进入EXCEL后先在表格的第一列输入变量、约束和目标的名
称，在后面某一列对应位置输入约束和目标的表达式(前加
等号提示符)；
-然后在工具中调用规划求解，按提示操作。
（可参看关于使用EXCEL的书，如谢国锋等，《EXCEL2000中
文版入门与提高》，清华大学出版社，1999）
§5 整数规划
Integer Programming(简称IP)
一、 整数规划的一般模型
LP: max z=CX
AX=b
X≥0
IP: max z=CX
AX=b
X≥0
X为整数
例一、合理下料问题
设用某型号的圆钢下零件A1, A2,…,Am 的毛坯。在一根圆钢上下料的方式有B1,B2, … Bn 种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。怎样安排下料方式，使得即满足需要，所用的原材料又最少？
零件 方 个数 式
零件
零 件
毛坯数
整数规划的模型
设：xj 表示用Bj (j=…n) 种方式下料根数
模型：
整数规划的模型
纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。
全整数规划：除所有决策变量要求取非负整数外，系数aij和常数bi也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）。
混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。
0－1整数规划：所有决策变量只能取 0 或 1 两个整数。
整数规划的数学模型
从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。
整数规划与线性规划的关系
例：设整数规划问题如下
首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。
整数规划与线性规划的关系
且为整数
用图解法求出最优解
x1＝3/2, x2 = 10/3
且有Z = 29/6
x1
x2
⑴
⑵
3
3
(3/2,10/3)
现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3), (2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。
按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。
整数规划与线性规划的关系
因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。
如上例：其中（2，2）（3，1）点为最大值，Z=4。
目前，常用的求解整数规划的方法有：
分支定界法和割平面法；
对于特别的0－1规划问题采用隐枚举法和匈牙利法。
整数规划与线性规划的关系
考虑纯整数问题：
整数问题的松弛问题：
分枝定界法
1、先不考虑整数约束，解( IP )的松弛问题( LP )，可能得到以下情况之一：
⑴.若( LP )没有可行解，则( IP )也没有可行解，停止计算。
⑵.若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。
⑶.若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。为讨论方便，设( LP )的最优解为：
分枝定界法
2、定界：
记( IP )的目标函数最优值为Z* ,以Z(0) 作为Z* 的上界，记为 ＝Z(0) 。再用观察法找的一个整数可行解 X′，并以其相应的目标函数值 Z′作为Z* 的下界，记为Z＝ Z′，也可以令Z＝－∞，则有: Z ≤ Z* ≤
3、分枝：
在( LP )的最优解 X(0)中，任选一个不符合整数条件的变量，例如xr=b’r （不为整数），以[b’r ] 表示不超过b’r 的最大整数。构造两个约束条件
xr≤ [b’r ] 和xr≥ [b’r ] ＋1
分枝定界法
将这两个约束条件分别加入问题( IP ) ，形成两个子问题( IP1)和( IP2 ) ，再解这两个问题的松弛问题( LP1)和( LP2) 。
4、修改上、下界：按照以下两点规则进行。
⑴.在各分枝问题中，找出目标函数值最大者作为新的上界；
⑵.从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。
5、比较与剪枝 ：
各分枝的目标函数值中，若有小于Z 者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。
如此反复进行，直到得到Z＝Z*＝ 为止，即得最优解 X* 。
分枝定界法
例一：用分枝定界法求解整数规划问题
记为（IP）
解：首先去掉整数约束，变成一般线性规划问题
记为（LP）
分枝定界法
用图解法求（LP）的最优解，如图所示。
x1
x2
⑴
⑵
3
3
(18/11,40/11)
⑶
对于x1＝18/11≈，
取值x1 ≤1， x1 ≥2
对于x2 =40/11 ≈，取值x2 ≤3 ，x2 ≥4
先将（LP）划分为（LP1）和（LP2）,取x1 ≤1, x1 ≥2
x1＝18/11, x2 =40/11
Z(0) =－218/11≈(－)
即Z(0) 是（IP）最小值的下限。
分枝定界法
有下式：
现在只要求出（LP1）和（LP2）的最优解即可。
分枝定界法
x1
x2
⑴
⑵
3
3
(18/11,40/11)
⑶
先求（LP1）,如图所示。此时B 在点取得最优解。
x1＝1, x2 =3, Z(1)＝－16
找到整数解，问题已探明，此枝停止计算。
1
1
同理求（LP2） ,如图所示。
在C 点取得最优解。
即x1＝2, x2 =10/3,
Z(2) ＝－56/3≈－ ∵Z2 < Z1＝－16 ∴原问题有比（－16）更小的最优解，但 x2 不是整数，利用 3 ≥ 10/3≥4 加入条件。
B
A
C
分枝定界法
加入条件： x2≤3, x2≥4 有下式：
只要求出（LP3）和（LP4）的最优解即可。
分枝定界法
x1
x2
⑴
⑵
3
3
(18/11,40/11)
⑶
1
1
B
A
C
先求（LP3）,如图所示。此时D 在点取得最优解。
即 x1＝12/5≈, x2 =3,
Z(3)＝-87/5≈<Z≈
但x1＝12/5不是整数，可继续分枝。即 3≤x1≤2。
D
求（LP4），如图所示。
无可行解，不再分枝。
分枝定界法
在（LP3）的基础上继续分枝。加入条件3≤x1≤2有下式：
只要求出（LP5）和（LP6）的最优解即可。
分枝定界法
x1
x2
⑴
⑵
3
3
(18/11,40/11)
⑶
1
1
B
A
C
D
先求（LP5）,如图所示。此时E 在点取得最优解。
即 x1＝2, x2 =3, Z(5)＝－17
找到整数解，问题已探明，此枝停止计算。
E
求（LP6），如图所示。此时 F在点取得最优解。
x1＝3, x2 =,
Z(6)＝－31/2≈－ > Z(5)
F
如对 Z(6) 继续分解，其最小值也不会低于－ ，问题探明,剪枝。
分枝定界法
至此，原问题（IP）的最优解为：
x1=2， x2 =3,
Z* = Z(5) ＝－17
以上的求解过程可以用一个树形图表示如右：
LP1
x1=1, x2=3
Z(1) ＝－16
LP
x1=18/11, x2=40/11
Z(0) ＝－
LP2
x1=2, x2=10/3
Z(2) ＝－
LP3
x1=12/5, x2=3
Z(3) ＝－
LP4
无可
行解
LP5
x1=2, x2=3
Z(5) ＝－17
LP6
x1=3, x2=5/2
Z(6) ＝－
x1≤1
x1≥2
x2≤3
x2≥4
x1≤2
x1≥3
＃
＃
＃
＃
分枝定界法
二、 0-1整数规划
投资场所的选址问题
指派问题
固定费用问题
背包问题
消防队问题
1. 投资场所的选址问题
某城市拟在东、西、南三区设立商业网点，备选位置有A1~A7共7个，如果选Ai，估计投资为bi元，利润为ci元，要求总投资不超过B元，规定
东区：A!、A2、A3中至多选2个
西区：A4、A5中至少选一个
南区：A6、A7中至少选一个
问如何设点使总利润最大？
1， Ai被选中
0， Ai没被选中
解：令
xi=
max z=
xi=0或 1，i=1, … ,7
∑ bixi≤B
i=1
7
x1+x2+x3≤2
x4+x5≥1
x6+x7≥1
.
课堂练习1:
某钻井队要从S1~S10共10个井位中确定五个钻井探油，如果选Si，估计钻探费用为ci元，并且井位选择上要满足下列条件：
（1）或选择S1和S7，或选择S8 ;
（2）选择了S3或S4就不能选择S5，反 过来也一样;
（3）在S5，S6 ，S7，S8中最多只能选两个。
问如何选择井位使总费用最小？
课堂练习1: 某钻井队要从S1~S10共10个井位中确定五个钻井探油，如果选Si，估计钻探费用为ci元，并且井位选择上要满足下列条件：
（1）或选择S1和S7，或选择S8
（2）选择了S3或S4就不能选择S5，反过来也一样
（3）在S5，S6 ，S7，S8中最多只能选两个
问如何选择井位使总费用最小？
1， Si被选中
0， Si没被选中
解：令
xi=
min z=
.
或 1，i=1, … ,10
某篮球队有8名队员，其身高和专长如下表，现要选拔5名球员上场参赛，要求：
（1）中锋只有1人上场
（2）后卫至少有一人上场
（3）只有2号上场，6号才上场
要求平均身高最高，应如何选拔队员？
课堂练习2:
1， 队员i被选中
0，队员i没被选中
解：令
xi=
max z=
或 1，i=1, … ,8
.
某篮球队有8名队员，其身高和专长如下表，现要选拔5名球员上场参赛，要求：
（1）中锋只有1人上场
（2）后卫至少有一人上场
（3）只有2号上场，6号才上场
要求平均身高最高，应如何选拔队员？
2. 指派问题
例： 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作任务E、J、G、R，现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种说明书所需的时间如下表所示，问应指派何人去完成何项任务，使所需总时间最少？
问题描述：n项任务可由n个人完成，由于专长不同，各人完成各任务的时间也不同，求最优安排。
要求：每人只能完成一项任务，每项任务只能由一人完成。
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 ( E任务只能一人干)
x12+ x22+ x32+ x42= 1 ( J任务只能一人干)
x13+ x23+ x33+ x43= 1 ( G任务只能一人干)
x14+ x24+ x34+ x44= 1 ( R任务只能一人干)
xij = 0 或 1，i,j = 1,2,3,4
min z=2x11+15x12+13x13+4x14+10x21+4x22+14x23+15x24
+9x31+14x32+16x33+13x34+7x41 +8x42+11x43+9x44
1， 指派第i人去完成第j项任务
0， 不指派第i人去完成第j项任务
解：令
xij=
（二）、解题步骤：
指派问题是0-1 规划的特例，也是运输问题的特例，当然可用整数规划，0-1 规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。
第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，即
(1) 从（cij）的每行元素都减去该行的最小元素；
(2) 再从所得新系数矩阵的每列元素中减去该列的最小元素。
第二步：进行试指派，以寻求最优解。
在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：
(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎ 。然后划去◎ 所在列(行)的其它0元素，记作Ø ；这表示这列所代表的任务已指派完，不必再考虑别人了。
(2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎ 所在行的0元素，记作Ø ．
(3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。
(4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。
（5）若◎ 元素的数目m 等于矩阵的阶数n，那么这指派问题的最优解已得到。若m < n, 则转入下一步。
第三步：作最少的直线覆盖所有0元素。
(1)对没有◎的行打√号；
(2)对已打√号的行中所有含Ø元素的列打√号；
(3)再对打有√号的列中含◎ 元素的行打√号；
(4)重复(2)，(3)直到得不出新的打√号的行、列为止；
(5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数 l 。l 应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若 l＝m < n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。
第四步：变换矩阵(bij)以增加0元素。
在没有被直线覆盖的所有元素中找出最小元素，然后打√各行都减去这最小元素；打√各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。
例一：
任务
人员
A
B
C
D
甲
2
15
13
4
乙
10
4
14
15
丙
9
14
16
13
丁
7
8
11
9
-2
-4
-9
-7
-4
-2
◎
Ø
◎
Ø
Ø
◎
◎
任务
人员
A
B
C
D
甲
6
7
11
2
乙
4
5
9
8
丙
3
1
10
4
丁
5
9
8
2
例二、
求解过程如下：
第一步，变换系数矩阵：
－5
第二步，试指派：
◎
◎
◎
Ø
Ø
找到 3 个独立零元素
但 m = 3 < n = 4
第三步，作最少的直线覆盖所有0元素：
◎
◎
◎
Ø
Ø
√
√
√
独立零元素的个数m等于最少直线数l，即l＝m=3<n=4；
第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派：
0
0
0
0
0
0
得到4个独立零元素， 所以最优解矩阵为：
◎
◎
◎
Ø
Ø
√
√
√
◎
◎
◎
Ø
Ø
15
◎
◎
◎
Ø
Ø
◎
练习：
11
5
7
6
4
戊
6
9
6
3
7
丁
8
6
4
5
8
丙
9
11
7
12
9
乙
11
8
9
5
7
甲
E
D
C
B
A
费 工作
用
人员
-1
-2
◎
Ø
◎
◎
◎
Ø
Ø
◎
Ø
◎
◎
◎
Ø
Ø
√
√
√
l =m=4 < n=5
◎
Ø
◎
◎
◎
Ø
Ø
◎
Ø
◎
Ø
◎
Ø
◎
Ø
√
√
√
√
√
√
√
◎
Ø
◎
Ø
◎
Ø
◎
Ø
√
√
√
√
√
√
√
l =m=4 < n=5
◎
Ø
◎
Ø
◎
Ø
◎
Ø
√
√
√
√
√
√
√
◎
Ø
Ø
◎
Ø
Ø
◎
Ø
◎
Ø
◎
此问题有多个最优解
28
◎
Ø
Ø
◎
Ø
Ø
◎
Ø
◎
Ø
◎
◎
Ø
Ø
◎
Ø
Ø
◎
Ø
◎
Ø
◎
用匈牙利法求解下列指派问题，已知效率矩阵分别如下：
3. 固定费用问题
例、生产三种型号的防寒服，其消耗资源及单件成本如表。此外，每种防寒服不管生产多少，都要支付一定的固定费用。
型号
资源
小
中
大
资源限制
尼龙绸
1500
尼龙棉
1000
劳动力
4
5
3500
设备
2800
单件成本
13
12
10
固定费用
120
150
180
今要生产500件防寒服，确定总费用最低的生产方式。
一般描述：
已知：生产某产品有m种方式，设第j 种生产方式的固定成本为kj ，可变成本为cj。
问题：应选择哪几种生产方式、分别生产多少产量可使总成本最低？
分析：这是一个混合0-1规划问题：
1， 选择第j 种方式，即xj>0 时
0， 不选择第j 种方式，即xj=0 时
令 yj =
设第j 种生产方式的产量为xj
于是该问题可表示为：
xj ≤M yj
例、生产三种型号的防寒服，其消耗资源及单件成本如表。此外，每种防寒服不管生产多少，都要支付一定的固定费用。
型号
资源
小
中
大
资源限制
尼龙绸
1500
尼龙棉
1000
劳动力
4
5
3500
设备
2800
单件成本
13
12
10
固定费用
120
150
180
今要生产500件防寒服，确定总费用最低的生产方式。
型号
资源
小
中
大
资源限制
尼龙绸
1500
尼龙棉
1000
劳动力
4
5
3500
设备
2800
单件成本
13
12
10
固定费用
120
150
180
1， 选择第j 种方式
0， 不选择第j 种方式
令 yj =
Min Z=13x1+12x2+10x3+120y1+150y2+180y3
st
++≤1500
++≤1000
4x1++5x3≤3500
++≤2800
X1+x2+x3>= 500
xi≤Myi (i=1,2,3)
xi≥0; yi=0或1
4. 背包问题
问题描述
已知：一个背包最大容量为b公斤；有m件物品供选择，每件物品重ai公斤，价值为ci（i=1,…,m）。
问题：携带哪些物品可使总价值最大？
一般模型
.
1， 物品i被选中
0，物品i没被选中
xi=
例：一个徒步旅行者要在背包中选择一些最有价值的物品携带。他最多能带115kg的物品，现有5件物品，分别重54、35、57、46、19kg，其价值依次为7、5、9、6、3。问携带哪些物品可使总价值最大？
解：
模型为：
.
5. 消防队问题
某城市的消防总部将全市划分为11个防火区，设有4个消防救火站。下图①~④表示消防站，1~11表示防火区域，图中连线表示各地区由哪个消防站负责。问题：可否减少消防站的数目，仍能同样负责各地区的防火任务？如果可以，应关闭哪个消防站？
1
2
3
4
5
6
7
8
9
10
11
1
2
3
4
1， 保留第i个消防队
0， 撤消第i个消防队
解：令
xi=
min z= x1+x2+x3+x4
x1+x2 ≥1
x1+x2 ≥1
x1 ≥1
x1 +x3 ≥1
x3 ≥1
x1 +x3+x4≥1
x1 +x4≥1
x1+x2 +x4≥1
x1 +x4≥1
x4≥1
x3+x4≥1
xi=0或 1，i=1, … ,4
则模型为
课堂练习:
某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址代号及其能覆盖的居民小区编号如表所示，问为覆盖所有小区至少应建多少所小学？
备选校址代号
覆盖的居民小区编号
ABCDEF
1、5、7
1、2、5
1、3、5
2、4、5
3、6
4、6
运输问题
1 运输问题
2 运输问题的表上作业法
3 运输问题的进一步讨论
第一节 运输问题
及其数学模型
运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，运输问题的对偶问题及其对偶变量与原问题检验数的关系。
典型背景——单一物资运输调度问题
设某种物品有:
m个产地：
产量：
n个销地：
销量：
从产地 到销地 的单位运价是 。
求总运费最小的调度方案。
决策变量 表示由 到 的物品数量。
销地
产地
销量
产量
产销平衡问题——总产量=总销量
即
产销不平衡问题——总产量=总销量
产销平衡问题的数学模型
运输问题数学模型的特点
运输问题有有限最优解
运输问题约束条件的系数矩阵（下页）
约束条件系数矩阵每一列只有两个1，其余为0；
对产销平衡问题
约束条件均为等式，且产量之和=销量之和；
约束条件的独立方程最多有m+n-1个，即
m
n
i
j
其中
运输问题的对偶问题
——对偶变量与原问题检验数的关系
对产销平衡运输问题，若用
分别表示前m个约束等式相应的对偶变量，
用 分别表示后n个约束等式相应的对偶变量，即对偶变量为
运输问题的对偶问题可写为
运输问题的对偶问题 ——对偶变量与原问题检验数的关系
线性规划问题变量 的检验数为
运输问题的对偶问题 ——对偶变量与原问题检验数的关系
变量 的检验数为
设运输问题的一个基可行解的变量为
由于基变量的检验数为零，故有
运输问题的对偶问题 ——对偶变量与原问题检验数的关系
方程组含有m+n-1个方程，m+n个变量
可证明方程组有解，且不唯一。
求出方程组的解（称为位势）
则变量 的检验数为
运输问题的对偶问题 ——对偶变量与原问题检验数的关系
求运输问题检验数的一种方法
第二节 运输问题的
表上作业法
由上节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性，本节将由此给出运输问题的比单纯形法更为简便的求解方法—表上作业法。
表上作业法是单纯形法在求解运输问题的一种简便方法。
单纯形法与表上作业法的关系：
（1）找出初始基可行解
（2）求各非基变量的检验数
（3）判断是否最优解
计算表中空格检验数
表上给出m+n-1个数字格
判断方法相同
换基：
（4）确定换入变量和换出变量找出新的基可行解。
（5）重复（2）、（3）直至求出最优解。
表上调整（闭回路调整）
（运输问题必有最优解）
停止
最优解
？
是
否
举例说明表上作业法
例1、某部门三个工厂生产同一产品的产量、
四个销售点的销量及单位运价如下表：
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
第一步：确定初始基可行解
——最小元素法、伏格尔法
最小元素法思路：
从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。
最小元素法举例
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
8
2
2
0
10
10
0
6
14
8
6
8
0
0
0
0
6
0
最小元素法举例
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
8
2
10
14
6
8
最小元素法缺点：会出现顾此失彼
（运费差额问题）
考虑运价差
罚数（即差额）=次小运价-最小运价
罚数（或差额）的解释：
差额大，则不按最小运费调运，运费增加大。
差额小，则不按最小运费调运，运费增加不大。
对差额最大处，采用最小运费调运。
伏格尔法思路：
结合例1说明这种方法。
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
行罚数
①
0
4-4=0
第一次
结合例1说明这种方法。
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
行罚数
①
0
1
3-2=1
第一次
结合例1说明这种方法。
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
行罚数
①
0
1
1
第一次
结合例1说明这种方法。
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
行罚数
①
0
1
1
列
罚
数
4-2=2
2
1
5
3
①
第一次
结合例1说明这种方法。
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
行罚数
①
0
1
1
列
罚
数
2
1
5
3
①
14
8
0
优先安排销地
，否则运价会更高
下次不考虑该列
第一次
第二次
结合例1说明这种方法。
行罚数
②
0
1
2
列
罚
数
2
1
3
②
优先安排销地
，否则运价会更高
8
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
14
8
0
0
6
下次不考虑该行
结合例1说明这种方法。
行罚数
③
0
1
列
罚
数
2
1
2
③
8
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
14
8
0
0
6
下次不考虑该列
8
0
2
第三次
结合例1说明这种方法。
行罚数
④
7
6
列
罚
数
1
2
④
8
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
14
8
0
0
6
8
0
2
4
12
0
下次不考虑该列
第四次
结合例1说明这种方法。
行罚数
⑤
0
0
列
罚
数
2
⑤
4
2
8
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
14
8
0
0
6
8
0
2
4
12
0
0
0
0
第五次
例1用伏格尔法得到的初始基可行解
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
4
8
14
8
12
2
目标函数值
用最小元素法
求出的目标函数z=246
一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。
第二步：解的最优性检验
闭回路法
思路：计算空格（非基变量）的检验数
若令
则
如何求检验数？
分析：
——运费的增量
即 增加1个单位
的检验数=相应的运费增量
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
8
2
10
14
6
8
从初始表分析：
要保证产销平衡，则
称为闭回路
+1
-1
+1
-1
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
8
2
10
14
6
8
2
1
检验数表
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
8
2
10
14
6
8
2
1
1
-1
10
12
表中的解不是最优解。
第三步：解的调整
调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
8
2
10
14
6
8
-1
（-2）
（-2）
（+2）
（+2）
调整后的解为：
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
8
2
12
14
4
8
2
2
0
9
1
12
此时的解为最优解。
有无穷多最优解
几点说明：
当检验数为的负的变量超过两个，选择最小者对应的变量换入；
在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解；
迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。
讨论内容：
初始调运方案（初始基可行解）
——西北角法
解的最优性检验——对偶变量法（或称位势法）
还有其它的方法吗
？
根据第一节运输问题对偶问题与原问题的检验数的关系
第三节 运输问题的
进一步讨论
上节给出产销平衡运输问题的表上作业法，本节以下问题进一步讨论：
二、有转运的运输问题
一、产销不平衡的运输问题
并附有运输问题的思考题及练习题
一、产销不平衡的运输问题
（Ⅰ）若总产量大于总销量，即
令假象销地的销量为：
决策变量 表示由 到 的物品数量。
销地
产地
销量
产量
注意：用最小元素法求初始调运方案时，最后一列的零运价最后考虑。
原产大于销平衡问题的数学模型
修改后产大于销平衡问题的数学模型
（Ⅱ）若总产量小于总销量，即
令假象产地的销量为：
一、产销不平衡的运输问题
仿照上述类似处理。
举例说明
某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：
4
12
2
8
5
4
3
9
6
11
11
10
销量
产量
销地
产地
二、有转运的运输问题
中间转运站——产地、销地、中转站。
建模思路：从发送及接受角度考虑。
产地 转运 销地 发送量
产地
转运
销地
接受量
应用问题举例
例1、水泥调运的产销不平衡情况及运价如下表，求最好的调运方案。
2
11
10
7
8
3
5
9
2
1
4
3
销量
产量
销地
产地
最优方案为：
2
11
10
7
8
3
5
9
2
1
4
3
销量
产量
销地
产地
0
0
0
例2、某农场有土地900亩，分为三类，计划种植三种作物，情况如下表，求使作物总产量最多的布局方案。
500
销量
产量
销地
产地
700
700
850
480
600
300
400
500
解：目标函数最大，可用最大元素法，即是按产量高的优先安排的原则。
500
销量
产量
销地
产地
700
700
850
480
600
300
400
500
100
300
100
400
0
50
调整：
500
销量
产量
销地
产地
700
700
850
480
600
300
400
500
100
200
200
400
0
可验证此时为最优解。
运输问题
讨论
一、概念题（判断）
1、运输问题是一种LP问题，其求解结果有四种情况。
2、在运输问题中，只要给出一组含（m+n-1）个非零的 ，且满足
就可以作为一个初始基可行解。
3、按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。
4、当所有产地产量和销地销量均为整数值，运输问题的最优解也为整数值。
5、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。
6、如果…...分别乘上一个常k,…...不会发生变化。
二、运输问题的对偶问题
某一实际的运输问题可以叙述如下：
有n个地区需要某种物资，需要量分别为
，这些物资均由某公司分设在m个地区的工厂供应，各工厂的产量分别为
，已知从 i地区工厂至第j个需要地区单位物资的运价为 ，又
试阐述其对偶问题，并解释对偶变量的经济意义。
三、运输问题的灵敏度分析
已知某运输问题的供需关系及单价表如下表，
销量
产量
销地
产地
2
4
5
3
5
3
3
1
2
要求（1）用表上作业法找出最优调运方案。
（2）分别讨论 使最优方案不变
的变化范围
四、求解线性规划问题
可转化为运输问题来求解
练习：
下表给出一个运输问题及它的一个解，
4
1
1
3
7
4
6
1
1
5
6
2
销量
产量
销地
产地
8
5
3
2
3
1
试问：
（1）表中给出的解是否为最优解？
（2）若 由1变为3，所给的解是否仍为最优解？若不是，求出新的最优解。
（3）若所有价值系数均增加1，最优解是否改变？为什么？
（4）若所有价值系数均增加1，最优解是否改变？为什么？
（5）写出该问题的对偶问题，并给出其对偶问题的最优解。
*
*
*
*
*
*
*
管梅谷先生所在的山东大学是国内最早开展运筹学研究的高校之一。早在上世纪六十年代初期，毛主席来山东听过山大运筹学的汇报。
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
返回单纯性原理
*
*
*
*
*
*
*
*
*
上面的动作按钮是为了后面调用此例时用的。
上面的动作按钮是为了后面调用此例时用的。
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
