刁在筠 运筹学.docx

该【刁在筠 运筹学 】是由【guoxiachuanyue007】上传分享，文档一共【64】页，该文档可以免费在线阅读，需要了解更多关于【刁在筠 运筹学 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。刁在筠运筹学
第二章线性规划
教学重点:线性规划可行区域的几何结构,基本可行解及可行区域的基本定理,单纯形方法,两阶段法,对偶和对偶理论,灵敏度分析。
教学难点:线性规划可行区域的几何结构,基本可行解及可行区域的基本定理,单纯形方法,两阶段法,对偶性,灵敏度分析。
教学课时:24学时主要教学环节的组织:首先通过各种形式的例子归纳出线性数学规划的一般形式,然后在详细讲解主要内容的基础上,尽可能以图形和例题的形式给以形象的说明,使学生对知识点有更直观、具体的认识。再通过大量****题巩固知识,也可以应用软件包解决一些实际问题。
第一节线性规划问题教学重点:线性规划问题的实例,线性规划的一般形式、规范形式和标准形式
教学难点:线性规划一般形式转换成标准形式。
教学课时:2学时主要教学环节的组织:首先通过几个实例总结出线性规划问题的一般形式,再介绍如何将一般形式转换成标准形式。
1、线性规划问题举例
生产计划问题某工厂用三种原料生产三种产品,已知的条件如下表所示,试制订总利润最大的生产计划
单位产品所需原料数量(公斤)
产品Q1
产品
Q2
产品
Q3
原料可用量
(公斤/日)
原料P1
2
3
0
1500
原料P2
0
2
4
800
原料P3
3
2
5
2000
单位产品的利润
(千元)
3
5
4
可控因素(所求变量):设每天生产3种产品的数量分别为兀,x,x.
123目标:使得每天的生产利润最大,就是使得利润函数:
3x+5x+4x

123
每天原料的需求量不超过可用量:
原料P:2x+3x<1500
12
原料P:2x+4x<800
23
原料P:3x+2x+5x<2000
123
蕴含约束:产量为非负数x,x,x>0
123
模型max3x+5x+4x
123
2x+3x<1500
+4x<800
23
3x+2x+5x<2000
123
x,x,x>0
123
运输问题
一个制造厂要把若干单位的产品从两个仓库A;i=1,2发送到零售点
i
B;j=1,2,3,4,仓库A能供应的产品数量为ai=1,2,零售点B所需的产品jiij
的数量为b;j=1,2,3,4。假设供给总量和需求总量相等,且已知从仓库A运一ji个单位产品往B的运价为c。问应如何组织运输才能使总运费最小?
jij
求解
设x(i=1,2,j=1,2,3,4)表示从仓库A运往零售点B的产品数量。
ijij
模型:
y2^4
mm乙乙cx
ijij
i=1j=1
-x+x+x+x=a;i=1,2
i1i2i3i4i
+x=b;j=1,2,3,4
1j2jj
Lx>0;i=1,2,j=1,2,3,4
2、线性规划模型
minz二cx+cx+...+cx
1122nn
ax+ax+...ax二b;i二1,2,..・,p
i11i22inni
ax+ax+...ax>b;i二p+1,..・,mStvi11i22inni
•卜>0;j=1,2,...,q
x无限制;j=q+1,..・,n
1j
x;j=1,2,・・・,n为待定的决策变量c=(c,c,,c)为价值向量,
12n
c;j=1,2,・・・,n为价值系数,b=(b,b,・・・,b)为右端向量,
12m
q•••a
111n
矩阵A二::为系数矩阵
a…a’
mlmn/
线性规划模型的概念
可行解(或可行点):满足所有约束条件的向量x=(x,x,…x)T
12n
可行集(或可行域):所有的可行解的全体D={x\Ax=b,x>0}
最优解:在可行域中目标函数值最大(或最小)的可行解,最优解的全体称为最
优解集合0={xgD\ctx<cty,VygD}
最优值:最优解的目标函数值v=cTx,xgO
线性规划解的情况:
无解或不可行©D={x\Ax=b,x>0}
无界D*0但目标函数在可行域上无界有最优解D丰0且目标函数在D上有有限的
现象规划模型的规范形式和标准形式:
规范形式:
mincTx
Ax>b
.<
x>0
标准形式:
mincTx
Ax=b
<
x>0
形式转换一般形式转换成规范式:等式化成不等式:
ax+ax+x=b
i11i22inni
{
ax+ax+…ax<b
i11i22inni
ax+ax+…ax>b
i11i22inni
自由变量化成非负变量:
令自由变量x=x+-x-,其中x+,x-为非负变量jjjjj
ax+ax+•-ax<b
i11i22inni
ax+ax+•-ax+s=b,s>0
i11i22inniii
或
ax+ax+…ax>b
i11i22inni
ax+ax+…ax一s=b,s>0i11i22inniii
目标函数的最大问题向最小问题的转换
maxctxTmin-ctx
例:将下述问题转换成标准形式
maxz=一x1+x2
2x一xn—2
12
一2xW2
2
+x<5
2
x
.<1
x
1
x
1解:
minz=x一(x一x)
134
”2x—(x一x)一x=-21345
x一2(x一x)+x=2
1346
x+(x一x)+x=5
1347
x>0;i=1,3,4,5,6,7
i
n0
第二节可行域与基本可行解
教学重点:线性规划问题的图解法,可行区域的几何结构和线性规划基本定理。
教学难点:线性规划的基本定理。
教学课时:4学时主要教学环节的组织:首先通过图解法求出两个变量时可行区域的结构和最有点的位置,再进行一般情况下可行区域的结构进行讨论,得到线性规划的基本定理。
1、图解法对于只有两个变量的线性规划问题可以用图解法求解:变量用直角坐标系中的点表示,约束条件用坐标系中的半空间或直线的交表示,可行区域是一个凸多面体,目标函数用一组等值线表示,沿着增加或减少的方向移动,与可行域最后的交点就是最优解。
例1、
maxz=-x+x
12
=4x一2x的最小值
12
当目标函数改变后,等值线的方向会发生改变,如果等值线与某个约束对应的函数直线平行,则该函数值线上的所有可行解都是最优解
最优解(1,4)
目标函数值可能出现的情况:
1、可行域是空集;
2、可行域无界无最优解
3、最优解存在且唯一,则一定在顶点上达到;
4、最优解存在且不唯一,一定存在顶点是最优解。
从图解法的几何直观易得:
线性规划的可行域是若干个半平面的交集,它形成了一个有界或无界的凸多边形。对于给定的线性规划问题,如果它有最优解,最优解总可以在可行域的某个顶点上达到。
2、可行区域的结构
:设SeRn是n维欧氏空间的点集,若对任意
xeS,yeS的和任意九e[0,1]都有九x+(1一九)yeS就称S是一个凸集
:线性规划的可行域°={^AX=X-0}是凸集
证明:略。
:任意多个凸集的交还是凸集
:超平面H={xeRnatx=b}
半空间H+={xeRn|atx>b};H-={xeRn^tx<b}
:多面凸集
S={xeRn”tx=b;i=1,2,・・・,pyatx>b;i=p+1,p+2,・・・,p+q}
iiii
:设S为凸集xeS,如果对任意y,zeS和0V九V1,
都有xh勿+(1-入)z,则称x为S的顶点
基本可行解
令A=(B,N),其中B为A的一个满秩子方阵,
x=(x,x)。
BN
j=1
.^Lx—b
分块Bx+Nx—b
■BN
左乘B-ix+B-iNx—B-ib

即x—B-1b-B-1Nx
BN
0(B-ib
x=0x—
Nw丿
定义2・2・5:设B是秩为m的约束矩阵A的一个m阶满秩子方阵,则称B为一个基(或基阵);B中m个线性无关的列向量称为基向量,变量x中与之对应的m个分量称为基变量,其余的变量为非基变量,令所有的非基变量取值厂B-ib、
为0,得到的解x—称为相应于B的基本解。当B-ib>0则称基本解为基
W丿
本可行解,这时对应的基阵B为可行基。
如果B-1b>0则称该基可行解为非退化的,如果一个线性规划的所有基可行解都是非退化的则称该规划为非退化的。
。
证明:不妨设x=(x,…,x,…,0…,0)t,x>0,j=1,…,k.
1kj
若x是基本可行解,则取正值的变量对应的列向量A,…,A,为基向量,
1K
故线性无关.
反之,若A,…,A线性无关,则有工xA=b,k<m・
1kjj
j—1
若k=m,则有B=(A,…,A);
1K
若k<m,则可从其余n-k个列向量中再挑选m-k列向量与A,…,A组成
1K
基,易知,x为基可行解.
定理2・2・4x是基本可行解的充要条件是元是可行域D的顶点。
,则至少有一个基本可行解
证明:,则有
Ax0=b,x0>0・
不妨设x0>0,j=1,…,k;后n—k个向量为0•若A,…,A线性无关,则由
j1k
j=1
定理2・2・3知x0是基本可行解;否则存在不全为零的6,使得送5A=0,补充
jii
5=0,l=k+1,…,n得8,满足A§=0.
i
定理2・2・6—个标准的LP问题如果有有限的最优值,则一定存在一个基本可行解是最优解。
证明:设xo是一个最优解,如果xo是基本可行解,则问题得证;+e5和xo-e5,由ctxo+8ct5>ctxo和CTXo-8CT5>CTxo知CT5=o,故有CT(xo+85)=CTxo・按照定理2・2・5的证明方法迭代,最终可得到基本可行解x,满足ctx=ctxo・
第三节单纯型方法教学重点:单纯形算法和单纯形表。教学难点:单纯形算法,单纯形表。教学课时:4学时主要教学环节的组织:首先给出单纯形算法,然后给出单纯形算法的一种实现手段,单纯形表。
1、单纯型方法
考虑标准形式的线性规划问题
mincTx
.
Ax=b
x>0
j=1
j=1
其中x,cgRn,bgRm,AgRmxn,并且假定m<n且可行域
D={xgRn\Ax=b,x>0}HQ,系数矩阵A是行满秩的,即r(A)=m。
给定一个非退化的基本可行解X,对应的可行基为B,则等式约束AX=b
可以变为:
x+B-iNx=B-ib>0典式
BN
j=1
j=1
或
此时令x=0,则x=B-ib.
NB
目标函数ctx=ctx+ctx
BBNN

x=B-1b-B-1Nx
B
N
rx)
rB-ib'
所以x=
B
=
>0.
IxJ
N
<0丿
=ct(B-ib一B-iNx)+ctx
BNNN
j=1
j=1
=cTB-1b-(cTB-1N-cT)x
BBNN
g=0,贝Uctx=ctB-ib-gtx
BB
mincTB-ib-gTx
规划等价于
B
[x+B-iNx=B-ib
s』«BN
x>0
X.
(最优性准则)如果g<0,则基可行解元为原问题的最优解。
证:设x为原问题的任一可行解。由于x>0,而g<0,所以gtx<
CTx=z一匚Tx>z=CTx・
00
j=1
>0,而向量B-1A<0,则原问题无界。kk
(—A\
证明:令d二k+e,其中e是第k个分量为1,其余分量为0的n维向
「0丿kk
<0,所以有d>0,而
k
(-A)
Ad二(B,N)k+Ae二0
「0丿k
对于充分大的正数0,观察向量X+0d,此时有
A(X+0d)=b
x+0d>0
它所对应的目标函数值为
ct(X+0d)=ctx+0cTd=ctx-0(ctA—c)=ctx一
Bkkk
由于匚>0,而0>0可任意的大,故原问题目标函数无下
k
,若向量g的第k个分量g>0,而向量
k
B-1A•至少有一个正分量,则可以找到一个新的基本可行解x使得ctx<ct元。k
证明:只需将X具体的找出来.
令
(-A)
d=k+e
「0丿k
满足Ad=0
令
(b-0A\
X=X+0d=k+0e
「0丿k
F面证明,当适当选取0>0后,X即为所求.
显然,
AX=AX+0Ad=b,为使X>0,贝V要求b-0A>0,所以令
k
b
—r-
a
rk
b_
-i-1a>0,i=1,•…,m>aik
ik
:
1、检验数向量::t=ctB-iA-ct,它的每个分量称为检验数
B
2、第k列称为进入基列,第k个变量称为进基变量;第i列称为退出基列,第i个变量称为离基变量。
j=1