运筹学讲义1.docx
《运筹学讲义1.docx》由会员分享，可在线阅读，更多相关《运筹学讲义1.docx（48页珍藏版）》请在冰点文库上搜索。
《运筹学》讲义
运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。
运筹学的核心思想是建立在优化的基础上。
例如，在线性规划中体现为两方面：
（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？
（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？
运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依据。
随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解已有相应的软件。
因此，在实际求解计算时常可借助于软件在计算机上进行，这样可以节省大量的人力和时间。
第一部分 线性规划内容框架
LP问题
-8-
进一步讨论
基本方法
LP问题
实际问题提 出
基本概念 数学模型 可行解、最优解
解的概念 基本解、基可行解
基本最优解
图解法
原始单纯形法
单纯形法 大M法
人工变量法
对偶单纯形法 两阶段法对偶理论
灵敏度分析──参数规划*在经济管理领域内应用
特殊的LP问题
运输问题（转运问题）整数规划
多目标LP问题*
第一部分 线性规划（LinearProgramming）
及其应用
第一章 LP问题的数学模型与求解
§1 LP问题及其数学模型
（一）引例1（生产计划的问题）
某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获的利润如下表所示。
问应如何安排计划使该工厂获利最多？
Ⅰ
Ⅱ
资源限量
设备
1
2
8（台时）
原材料A
4
0
16（kg）
原材料B
0
4
12（kg）
单位产品利润（元）
2
3
该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的生产计划方案。
解：
设x1,x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。
由于资源的限制，所以有：
机器设备的限制条件：
x1+2x2≤8
原材料A的限制条件：
4x1≤16 （称为资源约束条件）原材料B的限制条件：
4x2≤12
同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有
x1≥0，x2≥0 （称为变量的非负约束）
显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。
而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使目标函数
Z=2x1+3x2 的值达到最大。
综上所述，该生产计划安排问题可用以下数学模型表示：
maxz=2x1+3x2
ê
éx1+2x2£8
s.t.
ê 4x1
ê 4x2
ê
£16
£12
1 2
ëx×x ³0
引例2.（营养配餐问题）
序号
食品名称
热量（卡路里）
蛋白质（克）
钙（mg）
价格（元）
1
猪肉
1000
50
400
10
2
鸡蛋
800
60
200
6
3
大米
900
20
300
3
4
白菜
200
10
500
2
假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。
如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。
问如何选择才能满足营养的前提下使购买食品的费用最小？
解:
设xj（j=1,2,3,4）为第j种食品每天的购买量，则配餐问题数学模型为
minz=10x16x23x32x4
é10000x1+800x2+900x3+200x4³3000
ê
x.tê
50x1
+60x2
+20x3
+10x4
³55
ê400x1+200x2+300x3+500x4³800
ê
x
ë j
ê ³0（j=1,2,3,4）
（二）LP问题的模型
上述两例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。
它们具有共同的特征。
（1）每个问题都可用一组决策变量（x1,x2,…xn）表示某一方案，其具体的值就代表一个具体方案。
通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。
（2）存在一组线性等式或不等式的约束条件。
（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为LP的数学模型，其一般形式为：
max（或min）z=c1x1+c2x2+…+cnxn （1.1）
a
ê
éa11x2+a12x2+L+a1nxn£（=,³）b1
s.t
ê 21x2
ê
+a22x2
+L+a2nxn
LL
£（=,³）b2
（1.2）
a
ê
êm1x2
+am2x2
+L+amnxn
£（=,³）bm
（1.3）
ëê x1×x2Lxn³0
n
或紧缩形式
max（或min）z=åcjxj
j=1
å
én
ê
êj=1
ajxj
£（=,³）bi（i=1,2,L,m）
（1.4）
ëê xj³0
或矩阵形式
max（或min）z=cx
éAX£（=,³）b
ê
ë
或向量形式：
X³0
（1.5）
max（或min）z=cx
n
å
é
ê
ê j=1
pjxj
£（=,³）b
（1.6）
êëXj³0
（j=1,2,L,n）
其中C=（c1,c2,…,cn），称为价值系数向量；
éa11,a12,La1nù
a
ê
A=ê
21,a22
,La2n
ú
ú称为技术系数矩阵（并称消耗系数矩阵）
ê LL ú
a
ê
ëm1
,am2
,La
ú
mnû
=（p1,p2,…,pn）
éb1ù
êb
b=ê
ú
2ú称资源限制向量
êMú
b
ê ú
ëmû
X=（x1,x2,…,xn）T称为决策变量向量。
（三）LP问题的标准型
1.为了讨论LP问题解的概念和解的性质以及对LP问题解法方便，必须把LP问题的一般形式化为统一的标准型：
n
maxz=åcjxj；
j=1
maxz=cx
å
én
ê
j=1
ajxj
=bi（i=1,2,L,m）
éAX=b
或ê
ê
ëê xj
³0（j=1,2,L,n）
ëX³0
maxz=cx
n
å
é
ê
或ê j=1
pjxj=b
êëxj
³0（j=1,2,L,n）
标准型的特点：
①目标函数是最大化类型
②约束条件均由等式组成
③决策变量均为非负
④bi（i=1,2,…,n）
2.化一般形式为标准型
①minz®max（-z）=-cx
②“£”®左边+松驰变量；“³”®左边－“松驰变量”
③变量xj£0®-xj³0变量xj无限制®令xj=xj¢－xj²
④bi<0®等式两边同乘以（-1）。
3.模型隐含的假设
①比例性假定：
决策变量变化的改变量与引起目标函数的改变量成比例；决策变量变化的改变量与引起约束方程左端值的改变量成比例。
此假定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。
②可加性假定：
每个决策变量对目标函数和约束方程的影响是独立于其它变量的。
③连续性假定：
决策变量应取连续值。
④确定性假定：
所有的参数（aij,bi,cj）均为确定，所以LP问题是确定型问题，不含随机因素。
以上4个假定均由于线性函数所致。
在现实生活中，完全满足这4个假定的例子并不多见，因此在使用LP时必须注意问题在什么程度上满足这些假定。
若不满足的程度较大时，应考虑使用其它模型和方法。
如非线性规划，整数规划或不确定型分析方法。
对LP标准型，我们还假定r（A）=m（四）LP问题的解的概念
设LP问题
n
maxz=åcjxj
j=1
（1.7）
n
åajxjj=1
=bi（i=1,2,L,n）
（1.8）
xj³0（j=1,2,L,n）
（1.9）
1.从代数的角度看：
可行解和最优解 满足约束条件（1.8）和（1.9）的解X=（x1,x2,…,xn）T称为
可行解。
所有可行解构成可行解集，即可行域S
={XA
=b,x³0}。
x
而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。
求解LP问题就是求其最优解和最优值，但从代数的角度去求是困难的。
2.从LP角度看：
基：
设A为mxn矩阵，r（A）=m，B是A中的mxm阶非奇异子矩阵（即
|B|¹0），则称B是LP问题的一个基。
若B是LP问题的一个基，则B由m个线性独立的列向量组成，即
B=（Pr1,Pr2,…,Prm），其中Prj=（a1rj,a2rj,…,amrj）T，（j=1,2,…,m）称为基向理。
与
其向量Prj相对应的变量xrj称为基变量，其它变量称为非基变量。
显然，对应于每个基总有m个基变量，n－m个非基变量。
基本解与基可行解 设B是LP问题的一个基，令其n－m个非基变量均为零，所得方程的解称为该LP问题的一个基本解。
显然，基B与基本解是一一对应的，基本解的个数≤Cmn。
在基本解中，称满足非负条件的基本解为基可行解，对应的基称为可行基。
退化解 如果基解中非零分量的个数小于m，则称此基本解为退化的，否则是非退化的。
最优基 如果对应于基B的基可行解是LP问题的最优解，则称B为
LP问题的最优基，相应的解又称基本最优解。
W
基本解
基可行解
可行解
3.LP问题解之间的关系如图所示
（五）两个变量LP问题的图解法
1.LP问题解的几何表示。
以引例为例说明maxz=2x1+3x2
ê
éx1+2x2£8 ①
ê 4x1
ê 4x2
ê
£16 ②
£12 ③
2
ëx1
³0,x ³0 ④
按以下顺序进行：
解：
（1）画出直角坐标系；
（2）依次做每条约束线，标出可行域的方向，并找出它们共同的可行域；
（3）任取一目标函数值作一条目标函数线（称等值线），根据目标函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函
-9-
x2 ②
B
Q4
Q3
0
3
2
1
①
x1
0
1
2
3
4
数线接触的最终点即表示最优解。
图1
-48-
其中，将目标函数Z=2x1+3x2改写为x2
2
=-2x
3 1
+1z，因此，它可
3
以表示为：
以z为参数，以-
的点具有相同的值。
解的几种情况：
为斜率的一族平行线。
位于同一条直线上
3
（1）此例有唯一解Q2，即x1=4,x2=2,z=14
（2）有无穷多最优解（多重解），若将目标函数改为z=2x1+4x2则线段Q2，Q3上的点均为最优解。
（3）无界解
x2
0 x1
求max无界
但求min有唯一解
x2
0
x1
（4）无可行解
可行域与最优解间的关系：
可行域 最优解
空 集 无最优解（无可行解）
有界集 唯一最优解多重解
无界集 无有限最优解（无界解）
结论：
（1）LP问题的可行域是凸集（凸多边形，凸多面体，…）；
（2）LP问题最优解若存在，则必可在可行域的顶点上得到；
（3）LP问题的可行域的顶点个数是有限的；
（4）若LP问题有两个最优解，则其连线上的点都是最优解。
因此，求解LP问题可转化为如何在可行域的顶点上求出使目标函数值达到最优的点的问题。
2.基可行解的几何意义
对例1 LP问题标准化为 maxZ=2x1+3x2
3
ê
éx1+2x2+x =8
4
ê 4x1+x =16
5
ê 4x+x
ê 2
=12
ë x1,L,x5³0
可求得所有的基本解：
x
（1）=（0,0,8,16,12）T（0点）,x
（2）=（4,0,4,0,12）T（Q1点）
x（3）=（4,2,0,0,4）T（Q2点）,x（4）=（2,3,0,8,0）T（Q3点）
x（5）=（0,3,2,16,0）T（Q4点）,x（6）=（4,3,-2,0,0）T（C点）
x（7）=（8,0,0,-16,12）T（A点）,x（8）=（0,4,0,16,-4）T（B点）
但A、B、C三点是非可行域上的点，即非可行解。
因此，x
（1），x
（2），
x（3），x（4），x（5）才是基可行解，它们与可行域的顶点相对应。
于是还有
结论：
（5）对于标准型的LP问题，X是基可行解的充要条件是X为可行域的顶点。
（6）LP问题可行域顶点的个数=基可行解的个数≤基的个数≤Cmn
3.图解法只适用于两个变量（最多含三个变量）的LP问题。
4.求解LP问题方法的思考：
①完全枚举法，对m、n较大时，Cmn是一个很大的数，几乎不可能；
②从可行域的一个顶点（基可行解）迭代到另一个顶点（基可行解）。
§2 单纯形法与计算机求解
1.解LP问题单纯形法的基本思路：
求出一个初始基可行解
求出使目标函数值得到改善的基可行解
y
停
判别此基可行解是否最 优 解
N
2.单纯形法的计算步骤（表格形式）
（1）建立初始单纯形表，假定B=I，b≥0设maxZ=c1x1+c2x2+…+cnxn
éx1 +a1m+1xm+1+La1nxn=b1
x
+a
ê
ê 2 2m+1
ê
xm+1
+La2nxn
M
=b2
x
+a
ê
ê m mm+1
xm+1
+Lamnxn
=bm
x
³0
ë j
ê （j=1,2,L,n）
将目标函数改写为：
-Z+c1x1+c2x2+…+cnxn=0
把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组，并写成增广矩阵的形式：
-Zx1 x2 …xmxm+1… xn b
01 0 …0
a1m+1 …
a1n b1
00 1 …0
a2m+1 …
a2n b2
00 0 …1
amm+1 …
amnbm
-1c1 c2 …cmcm+1… cn 0
以非基变量表示基变量形式xi
n
=bi-åaij
j=1
xj代入Z中的基变量,有
å
m
Z= ci（bi-
i=1
n
å
j=m+1
aijXj）+
n
åcjxjj=m+1
m m n n
=åcibi-åå
（ciaij）xj+
åcjxj
m
i=1
i=1j=m+1
j=m+1
å
m
= cibi-
i=1
n
å
j=m+1
（åciaij-cj）xji=1
å
m
令Z0= cibi,
i=1
m
Zj=åciaiji=1
n
于是Z=Zo+
å（Zj-cj）xjj=m+1
因此，上述的增广矩阵就可写成：
Zx1 x2 …xmxm+1… xn b
0 10 …0
0 01 …0
0 00 …1
a1m+1 …
a2m+1 …
amm+1 …
m
a1n b1
a2n b2
amn bm
m m
1 00 …0
åciaim+1-cm+1…åciain－cn
åcibi
i=1
i=1
i=1
再令sj
=cj-Zj
m
=cj-åciaij
i=1
则上述增广矩阵可写成下面表格形式：
即初始单纯形表T（B）
Cj
C1……Cm
cm+1……cn
qi
CB
xB
b
x1……xm
xm+1……xn
C1
x1
b1
1……0
a1m+1……a1n
C2
x2
b2
0……0
a2m+1……a2n
：
：
：
：
：
：
………：
Cm
xm
bm
0……1
amm+1……amn
Z
Z0
0……0
sm+1……sn
¬sj检验数行
上述初始单纯形表可确定初始可行基和初始基可行解：
B=（P1,P2,…,Pm）=I, x=（b1,b2,…,bm,0……0）T
从初始单纯形表建立的过程可以看到以下事实：
（1）凡LP模型中约束条件为“≤”型，在化为标准型后必有B=I，
如果b≥0，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。
目标函数非基变量的系数则以相反数填入检验数行各相应位置。
（2）在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应的检验数均为零。
m
（3）Z0=åcibi,sj
i=1
=Zj-cj
=åciaij-cj（j=m+1,Ln）
m
i=1
更好表现一般规律的在矩阵形式的单纯形表中
L
设MaxX=CX MaxZ=CX+0XL
éAx£b
éAx+Ix =b
ë
ë
L
êx³0
其标准型为
ê x,x ³0
将系数矩阵（A,I）分划为（B,N,I），其中B为可行基，对应于基变量向量
XB,N对应于XN，I对应于XL,（XN,XL）为非基变量向量。
于是（X,L）
T=（XB,XN,XL）T,（C,0）=（CB,CN,0）。
因此，矩阵形式的LP模型改写为：
éXBù
MaxZ=（CB
,CN
,0）
ê ú
X
êNú
MaxZ=CBXB
+CNXN
+0XL
êëXLúû
é éXBù
ê
ê（B,N,I）êX ú=b
éBXB+NXN+IXL=b
ú
ê ê Nú
ê êëXLû
ê
®
ë XB,XN,XL³0
ëXB,XN,XL³0
用非基变量向量表示基变量向量，有
XB=B-1b－B-1NXN－B-1XL
代入目标函数中有
Z=CB（B-1b－B－1NXN－B-1XL）+CNXN+0XL
=CBB-1b－CBB-1NXN－CBB-1XL）+CNXN
=CBB-1b－（CBB-1N－CN）XN－CBB-1XL
将
éZ+（C
N
L
ê B
B-1N-C
）XN
+CB
B-1X
=CB
B-1b
B N L
ëê X +B-1NX +B-1X =B-1b
写成对应于基B的矩阵形式的单纯形表T（B）：
C®
CB
CN
CL
b
XB
XN
XL
XB
B-1b
1
B-1N
B-1
Z
CBB-1b
0
CBB-1N－CN
CBB-1
例如将例1 化成标准型后如下表T（B）：
Cj
2
3
0
0
0
qi
CB
XB
b
x1
x2
x3
x4
x5
0
x3
8
1
2
1
0
0
0
x4
16
4
0
0
1
0
0
x5
12
0
4
0
0
1
-Z
0
-2
-3
0
0
0
¬σj
初始可行基B=（P3,P4,P5）=I,X=（0,0,8,16,12）T
（2）判别最优解
1° 在T（B）中，若所有的检验数σj≥0（j=1,2,…,n）
则B为最优基，相应的基可行解为最优解，停止计算。
2° 在T（B）中，若有σk<0（1£k£n），且xk的系数列向量Pk£0，则该问题无界，停止计算。
否则转入（3）
（3）换基迭代（基变换）
1° 先确定入基变量Xk:
k=min{j|sj<0}
2° 按最小比值原则确定出基变量xL：
q=minébi
ê
a
|aik
>0ù=bL
ú
a
ëik û Lk
3° 以aLK为主元，进行初等行变换（又称旋转变换）即将列向量
PK变换为单位列向量：
返回
（2）。
换基迭代的关键在于将换入变量对应的列向量PK用初等行变换方法
变换成单位列向量。
其中主元aLK变成1。
即
éa1kù é0ù
êa ú ê0ú
ê2kú êú
ê:
ú ê:
ú
Pk=êa ú®ê1ú®第L个分量
ê1kú êú
ê:
ú ê:
ú
êa ú ê0ú
ëmkû ëû
如果在最终表中有非基变量的检验数为0，则该问题有多重最优解。
3.单纯形法的进一步讨论──用人工变量法求初始基可行解
（一）人工变量法
若对LP模型标准化后，不具有B=I时，如何办？
此时可采用人工变量法得到初始基可行解。
所谓人工变量法是在原问题不含有初始可行基B=I的情况下，人为的对约束条件增加虚拟的非负变量（即人工变量），构造出含有B=I的另一个
LP问题后求解。
当增加的人工变量全部取值为0时，才与原问题等价。
这样，新问题将有一
升级会员 