第3章数学规划基础.docx
- 文档编号:18004468
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:42
- 大小:432.72KB
第3章数学规划基础.docx
《第3章数学规划基础.docx》由会员分享,可在线阅读,更多相关《第3章数学规划基础.docx(42页珍藏版)》请在冰点文库上搜索。
第3章数学规划基础
第3章数学规划基础
所谓数学规划,是指系统在一定约束条件下使某一评价目标达到最优(极值)的一种决策方法。
数学规划的关键是从系统思想出发,在定性分析的基础上建立其数学模型。
数学规划模型的一般形式为:
系统在满足条件
(1)
的情况下,使评价目标达到最优(最大或最小值),即
(2)
其中,式
(1)是系统必须满足的限制条件的数学描述,通常由等式或不等式组成,称为约束条件,简记为s.t.(subjectto,意为“受…的限制”);式
(2)是系统评价目标的数学描述,称为目标函数。
一、线性规划
所谓线性规划,是指约束条件和目标函数均为线性的数学规划方法。
根据系统评价目标是单个还是多个,可将线性规划分为单目标线性规划和多目标线性规划。
(一)单目标线性规划
1.问题的提出
例1(生产管理问题)某工厂计划期内要安排生产Ⅰ、Ⅱ两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗,如表所示。
该工厂每生产一件产品Ⅰ可获利2元,每生产一件产品Ⅱ可获利3元,问如何安排生产计划才能使工厂获利最多?
产品Ⅰ
产品Ⅱ
限制
设备(台时/件)
1
2
8台时
原材料A(kg/件)
4
0
16kg
原材料B(kg/件)
0
4
12kg
利润(元/件)
2
3
解上述所谓的“安排生产计划”问题,其实质就是要寻求一个满足设备和原材料资源约束的可行的生产方案,以确保工厂能获得最大的利润值。
假设产品Ⅰ、Ⅱ的产量分别为x1、x2,则该工厂的获利值f=2x1+3x2。
由于可行的生产方案需要考虑不能超出设备的有效台时数限制,即x1+2x2≤8;同时,还要考虑满足A、B原材料资源的约束条件,即4x1≤16,4x2≤12。
因此,工厂的目标是在满足设备和原材料资源限制的条件下,如何确定两种产品的产量x1、x2,使工厂的获利最大。
综上所述,上述安排生产计划问题的数学模型为
目标
满足约束条件(s.t.)
由此可见,将这类实际问题转换为数学模型的基本步骤可归纳如下:
(1)确定决策变量;
(2)确定所要追求的目标(目的);
(3)确定约束条件;
例2(环保问题)靠近某河流有两个化工厂,流经工厂1的河水流量是5×106m3/天,在两个工厂之间有一条流量为2×106m3/天的支流,如图所示。
工厂1每天排放工业污水2×104m3,工厂2每天排放工业污水1.4×104m3。
从工厂1排出的污水流到工厂2之前,有20%可自然净化。
根据环保要求,河流中工业污水的含量不应超过0.2%。
若这两个工厂都各自处理一部分污水,工厂1处理污水的成本是1000元/104m3,工厂2处理污水的成本是800元/104m3,试问在满足环保要求的条件下,各工厂应分别处理多少污水,才能使两个工厂处理污水的总费用最小?
解假设工厂1和工厂2每天处理污水量分别为x1·104m3、x2·104m3,则两个工厂处理污水的总费用f=1000x1+800x2。
根据环保要求,从工厂1到工厂2之间的河流中污水含量不超过0.2%,则可得
由于从工厂1排出的污水流到工厂2之前有20%会自然净化,且流经工厂2后河流中污水含量仍要不超过0.2%,故有
此外,各工厂每天的污水处理量不应超过其污水排放量,则有x1≤2,x2≤1.4。
因此,问题的目标是要求两个工厂处理污水的总费用最小。
综上所述,上述环保问题的数学模型为
目标
满足约束条件(s.t.)
2.数学模型的建立
应用单目标线性规划来解决实际的最优化问题时,必须符合以下特征(参见P34):
(1)所求问题都有一个目标要求,且相应的目标函数可以用最大或最小值的形式来表达;
(2)要达到最优目标,必须有多种方案可供选择;
注意:
每一组决策变量(x1,x2,…,xn)的取值就是一个具体方案。
(3)所寻求的目标必然有条件约束;
(4)目标函数和约束条件都是线性方程式,且决策变量具有非负性。
因此,单目标线性规划问题的数学模型可归纳如下:
目标函数
满足约束条件(s.t.)
其中,aij,bi,cj为已知常数。
3.数学模型的标准化
将单目标线性规划的数学模型规定为以下标准形式:
(1)目标函数是求最大值
当目标函数是求最小值时,即
由于
令f'=-f,可得
(2)约束条件均用线性等式方程来表示,且右边常数项均为非负值
当表达式中含“≤”时,可在约束条件左边加上一个非负的变量——松弛变量,使原来的“≤”变为“=”;当表达式中含“≥”时,可在约束条件左边减去一个非负的变量——剩余变量,使原来的“≥”变为“=”。
另外,在标准型中要求约束条件右边的常数项bi≥0,若存在bi<0的情形,则可在方程式两边各乘以-1,使所有bi≥0得到满足。
(3)所有变量要求非负
当xi≤0时,则可令xi'=-xi且xi'≥0;当xi为无约束的自由变量时,则可令xi'-xi"=xi且xi'、xi"≥0。
综上所述,可得单目标线性规划模型的标准形式:
目标函数
满足约束条件(s.t.)
例3将例1(生产管理问题)的数学模型化为标准形式。
解例1的目标函数是求最大值,各不等式均为“≤”形式的不等式,故需要在各不等式的左边加上非负的松弛变量x3,x4,x5,使不等式化为等式。
由于所加变量x3,x4,x5表示未被利用的资源,则也就没有被转化为价值,所以在目标函数中x3,x4,x5的系数应为零。
因此,其标准形式为
例4(思考题)将例2(环保问题)的数学模型化为标准形式。
例5将下列数学模型化为标准型。
解令x1=-x1'且x1'≥0
x3=x3'-x3"且x3'、x3"≥0
将第一个约束条件两端乘以-1并加入松弛变量x4,第二个约束条件减去剩余变量x5,第三个约束条件加上松弛变量x6,同时将目标函数变为求最大值,整理可得
4.图解法
对于一般单目标线性规划问题
满足
(2)式的点称为该问题的解;而同时又满足(3)式的点则称为可行解。
所有可行解组成的集合称为可行域或可行解集。
可行域上满足
(1)式的点称为最优解,最优解对应的目标函数值称为最优值。
当单目标线性规划问题中只有两个决策变量(即二维线性规划)时,可以用图解法来求解,以便直观地理解该问题解的几何意义。
例6用图解法求例1(生产管理问题)的解。
解
(1)由约束条件画出可行域
-2x1+x2=4
因为x1,x2≥0,可行域在第一象限。
第一个约束条件x1+2x2≤8表示以直线x1+2x2=8为边界的右下方平面;第二个约束条件4x1≤16表示以x1=4为边界的左半平面;第三个约束条件4x2≤12表示以x2=3为边界的下半平面,因此,OABCD所围成的凸多边形即为可行域,如图中的阴影部分所示。
-2x1+x2≥4
(2)考虑目标函数的等值线和梯度方向
对目标函数f=2x1+3x2,令c为参数,则2x1+3x2=c表示目标函数的取值为c的一簇平行线,如图中的虚线所示,且位于同一直线上的点具有相同的目标函数值,故称其为“等值线”。
当c值由小变大时,直线2x1+3x2=c沿着其梯度方向,向右上方平行移动。
(3)求问题的最优解
当目标函数沿其梯度方向平移至B点时,切点B即为最优解。
则求出B点的坐标
得最优解x1*=4,x2*=2;相应的最优值fmax=2x1*+3x2*=8+6=14。
讨论:
若例1是求最小值,则在O点处达到最优解x1*=x2*=0,且相应的最优值fmin=0;
若例1中的目标函数变为f=2x1+4x2,则等值线2x1+4x2=c与约束条件x1+2x2≤8的边界线相平行。
当c值由小变大并与线段CB重合时,目标函数值达到最大,则表示线段CB上的任意一点都是最优解,即该问题有无穷多个最优解;
若在例1的数学模型中再加一个约束条件-2x1+x2≥4,则可行域是空集,此时无可行解,当然也就无最优解。
通过上述的图解法可见,单目标线性规划问题中,所有可行解构成的可行域一般是凸多边形或是无界的,其最优解具有以下重要特点:
若问题存在最优解,则一定在可行域的某个顶点上得到;
若两个顶点上同时得到最优解,则这两个顶点连线上的任何一点都是最优解;
若可行解无界,则可能发生无最优解的情况;
若无可行域,则问题既无可行解也无最优解。
5.单纯形法
单纯形法是由美国数学家G.B.Dantzing于1947年首先提出的。
它是借助于计算机,用于求解多变量(多维)线性规划的有效方法。
(1)基本概念及其相关定理
对于线性规划问题的标准型
用矩阵形式表示,则可以写成
式中
其中,C是由价值系数cj构成的价值向量,X是由决策变量xj构成的决策向量,A是由技术系数aij构成的m×n阶约束系数矩阵,b是由资源系数bi构成的资源向量。
若矩阵A的秩为m,B是A阵中m×m阶非奇异矩阵(|B|≠0),则称B是线性规划问题的一个基。
也就是说,矩阵B是由m个线性独立的列向量Pj组成,即
则称Pj(j=1,2,…,m)为基向量,与基向量Pj相对应的非零变量xj(j=1,2,…,m)为基(基础)变量;其余的零变量xj(j=m+1,m+2,…,n)为非基(基础)变量。
与基B对应的线性规划问题的解
则称为线性规划问题的基解。
由于满足非负约束条件X≥0的解为线性规划问题的可行解,则满足非负条件的基解就称为基可行解,而对应于基可行解的基就称为可行基。
定理1:
线性规划的可行解X=[x1x2…xn]T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。
因此,为了简单起见,通常在单纯形法中要求基础变量对应的矩阵为单位矩阵。
假设在线性规划问题的标准型中,与基B对应的基变量XB=[x1x2…xm]T,非基变量XN=[xm+1xm+2…xn]T,且相应的矩阵C=[CBCN],其中CB=[c1c2…cm],CN=[cm+1cm+2…cn],则可以证明以下判别线性规划问题最优解的依据(参见P40)。
定理2(最优解判别定理):
在标准形式的线性规划问题中,对于基B,若B-1b≥0,且C-CBB-1A≤0(即检验系数矩阵σ=C-CBB-1A),则对应于基B的基解就是最优解,基B就是最优基。
尤其是,当最优解判别定理中基矩阵B=I(m×m阶单位阵)时,则对应的基可行解为XB=b且XN=0,其最优解的判别式变为C-CBA≤0。
不失一般性,设XB=[x1x2…xm]T,CB=[c1c2…cm],系数矩阵A为
对于基变量xj(j=1,2,…,m)来说,其检验系数σj为零;对于非基变量xj(j=m+1,…,n)来说,其检验系数
(j=m+1,…,n),当σj≤0时,则目前的基本可行解为最优解。
否则,若存在某个检验系数σj>0,则目前的基本可行解不是最优解。
特别要指出的是,若存在某个σm+k=0,而其它任何σj<0(j=m+1,…,n且j≠m+k),则线性规划问题有无穷多个最优解;若存在某个σm+k>0,且A的列向量Pm+k中的所有元素均不大于0,则线性规划问题无最优解。
(2)基本思路
单纯形法的基本思路是:
根据线性规划问题的标准型,从可行域中的一个顶点(基可行解)开始,转换到另一个顶点(基可行解),并且使目标函数的值逐步增大。
当目标函数达到最大值时,就得到了问题的最优解。
以例1的生产管理问题为例,说明单纯形法逐步迭代寻优的原理和思路。
该问题的数学标准型为
(1)
第一轮:
约束方程系数矩阵
显然
是线性独立的,这些列向量构成一个初始可行基B
对应于初始可行基B,x3、x4和x5为初始基变量,x1和x2为非基变量。
由方程组
(1)可得
(2)
令非基变量x1、x2为零,得到初始的基可行解为
将方程组
(2)代入目标函数,得
(3)
将初始的基本可行解代入式(3),得f(0)=0。
这个基本可行解表示:
工厂没有安排生产产品Ⅰ、Ⅱ;设备的有效台时和原材料A、B没有被利用,所以工厂的利润指标f(0)=0。
从式(3)目标函数可以看到,x1、x2(即没有安排生产的产品Ⅰ,Ⅱ)的系数都是正数,显然将非基变量换成基变量,目标函数的值就可能增大。
从经济意义上讲,安排生产产品Ⅰ或Ⅱ就可以使工厂的利润指标增加,所以只要式(3)目标函数中还存在有正系数的非基变量,则目标函数值(利润)还有增加的可能,就需要将非基变量与基变量进行对换。
一般选择正系数最大的那个非基变量x2为换入变量(即引入变量),将它换入到基变量中去,同时还要确定基变量中有一个要换出来成为非基变量。
可按下列方法来确定换出变量(即退出变量)。
现在分析方程组
(2),当将x2定为换入变量后,必须要从x3、x4和x5中换出一个,并要保证其余的都是非负,即x3,x4,x5≥0。
当x1=0时,由方程组
(2)可得
(4)
从方程组(4)可见,只有选择x2=min{8/2,-,12/4}=3时,才能使式(4)成立。
当x2=3时,x5=0,这就决定了x5为换出变量,用x2去替换x5。
以上数学描述说明:
每生产一件产品Ⅱ,需要用掉设备台时及原材料为(2,0,4)。
这些资源能力中的薄弱环节就确定了产品Ⅱ的产量,也就是由原料B的生产能力,确定了产品Ⅱ的产量x2=12/4=3件。
第二轮:
x2与x5互换,即x2为基变量,x5为非基变量。
则互换后,x3、x4和x2为基变量,x1和x5为非基变量。
为了求得新的基可行解,并将目标函数f用非基变量x1、x5表示,以判别所求的基可行解是否为最优解,则需要用高斯消元法,将方程组
(2)中第一个方程的x2消去,将第三个方程的x2移至左边,并将系数化为1,于是有
(5)
令非基变量x1、x5为零,得基可行解为
将方程组(5)代入目标函数中,得
(6)
将x1=0,x5=0代入方程组(6),可得目前基可行解的目标值为9。
由式(6)可知,非基变量x1的系数大于0,则目前的基可行解不是最优解,x1应为换入变量。
在方程组(5)中,用各方程负的x1的系数(如果x1在方程的左边,则用正的x1系数)去除对应的常数项,选最小者,即
x1=min{2/1,16/4,-}=2
于是,方程组(5)中的第一个方程对应的原基变量x3为换出变量。
第三轮:
x1与x3互换,则互换后,x1、x4和x2为基变量,x3和x5为非基变量。
将方程组(5)进行初等变换,使得由基变量x1、x4和x2所构成的基为单位矩阵,即
(7)
令非基变量x3、x5为零,得基可行解
将方程组(7)代入目标函数中,得
(8)
由式(8)可知,非基变量x5的系数大于0,则目前的基可行解不是最优解,x5为换入变量,因为min{-,8/2,3/(1/4)}=4,故取x4为换出变量。
第四轮:
x5与x4互换,则互换后,x1、x5和x2为基变量,x3和x4为非基变量。
用高斯消元法对方程组(7)进行初等变换,使得每个约束方程中只含有一个基变量且基变量的系数为1,即
(9)
令非基变量x3、x4为零,得基可行解为
将方程组(9)代入目标函数中,得
(10)
由式(10)可见,x3与x4的系数均为负数,说明若想使用剩余的设备台时和原材料A,就必须支付附加费用。
所以当x3=x4=0时,即不再利用这些设备能力和原材料时,目标函数达到最大fmax=14,于是基可行解
为最优解。
(3)单纯形表
对于标准化的线性规划模型
式中,x1,x2,…,xm为基变量,且对应的基为B=I(m×m阶单位阵)。
所设计的初始单纯形表如表1所示。
表1初始单纯形表
C
c1
…
cm
cm+1
…
cn
θi
CB
XB
b
x1
…
xm
xm+1
…
xn
c1
x1
b1
1
…
0
a1,m+1
…
a1n
θ1
c2
x2
b2
0
…
0
a2,m+1
…
a2n
θ2
…
…
cm
xm
bm
0
…
1
am,m+1
…
amn
θm
0
…
0
…
σj
表中,XB列中填入基变量,这里是x1,x2,…,xm;
CB列中填入基变量的价值系数,这里是c1,c2,…,cm,它们随基变量改变而改变,并与基变量相对应;
b列中填入约束方程组右端的常数;
X行填入决策变量名;
在X行上面的C行,相应填入各决策变量的价值系数;
最后一行是检验数行,对应各非基变量xj的检验数是
θi列的数字是在确定换入变量后,按θ规则计算后填入表中的。
单纯形表要求初始可行基B=I,这时可以从表上直接得到基可行解,即
且该基可行解的目标值为
。
单纯形法就是以上述形式的初始单纯形表为起点进行迭代,每迭代一次后,得到使新的基B'=I的另一个单纯形表;从表上得到新的基可行解和目标值,并进行最优判别,直到找到最优解为止。
(4)单纯形法小结
下面将单纯形法的计算步骤归纳如下:
第一步,建立线性规划的数学模型,并使其标准化。
标准化的要求为:
目标函数化成求最大值问题;
约束条件均表达为等式关系(必要时引入松弛变量和剩余变量);
模型存在一个初始可行基——单位矩阵(必要时引入人工变量)。
第二步,建立初始单纯形表,如表1所示。
第三步,检验各非基变量xj的检验数
若所有σj≤0(j=m+1,…,n),则已得到最优解,可停止计算,否则转入下一步。
第四步,在σj>0,j=m+1,…,n中,若有某个σk>0对应的xk的系数列向量Pk≤0,则此问题无最优解,停止计算,否则转入下一步。
第五步,根据max{σj>0}=σk,在单纯形表中σk所在的列为主元列(即关键列),主元列所对应的变量xk为换入变量(入基变量)。
再根据θ规则计算,有θi=bi/aik(aik>0,i=1,2,…,m),θl=min(θi)=bl/alk,确定θl所在的行为主元行(即关键行),主元行在单纯形表中所对应的基变量xl为换出变量(出基变量)。
主元行与主元列相交的元素alk为主元素(即关键元素),用方括号[]标明,转入下一步。
第六步,以alk为主元素,用高斯消元法进行约束方程组的初等变换,将主元列中主元素alk变为1,其它元素变为0,即把xk所对应的列向量
将XB列中的xl转换为xk,CB列中的cl换成ck,得到新的单纯形表。
重复第三步~第六步,直到算法终止。
例6用单纯形法计算例1(生产管理问题)的最优解。
解第一步,将模型标准化后,即为
模型中已存在一个初始可行基,对应的基变量为x3、x4和x5,则令非基变量x1、x2为零,可得初始基可行解为
且相应的目标函数值f(0)=0。
第二步,将有关内容填入表中,得到如表2所示的初始单纯形表。
表2初始单纯形表
cj
2
3
0
0
0
θi
CB
XB
b
x1
x2
x3
x4
x5
0
x3
8
1
2
1
0
0
4
0
x4
16
4
0
0
1
0
—
0
x5
12
0
[4]
0
0
1
3
σj
2
3
0
0
0
第三步,计算各非基变量的检验数,σ1=2,σ2=3,故存在σj>0,目前的解不是最优解,转入下一步。
第四步,P1,P2均有正分量存在,转入下一步。
第五步,经比较max{σj>0}=σ2,确定x2为换入变量,x2所在列为主元列;计算θ1=8/2=4,θ3=12/4=3,取最小值者为θ3,于是θ3所在的行为主元行,主元行所对应的基变量x5为换出变量,主元行与主元列相交的元素[4]为主元素。
第六步,以[4]为主元素,用高斯消元法进行初等行变换,使对应主元列的列向量P2变换为[001]T,在XB列中将x5替换为x2,于是得到表3。
表3x5替换为x2后的单纯形表
cj
2
3
0
0
0
θi
CB
XB
b
x1
x2
x3
x4
x5
0
x3
2
[1]
0
1
0
-1/2
2
0
x4
16
4
0
0
1
0
4
3
x2
3
0
1
0
0
1/4
—
σj
2
0
0
0
-3/4
这样,得到新的基本可行解
且相应的目标函数值f
(1)=9。
第七步,重复第三步~第六步的计算步骤,由于表3中检验数σ1=2>0,则目前的解不是最优解。
同理可以确定x1为换入变量,x3为换出变量,于是得到表4。
表4x3替换为x1后的单纯形表
cj
2
3
0
0
0
θi
CB
XB
b
x1
x2
x3
x4
x5
2
x1
2
1
0
1
0
-1/2
—
0
x4
8
0
0
-4
1
[2]
4
3
x2
3
0
1
0
0
1/4
12
σj
0
0
-2
0
1/4
则其新的基本可行解
且相应的目标函数值f
(2)=13。
第八步,再次重复第三步~第六步的计算步骤,由于表4中检验数σ5=1/4>0,则目前的解还不是最优解。
同理可以确定x5为换入变量,x4为换出变量,于是得到表5。
表5x4替换为x5后的单纯形表(最优单纯形表)
cj
2
3
0
0
0
θi
CB
XB
b
x1
x2
x3
x4
x5
2
x1
4
1
0
0
1/4
0
—
0
x5
4
0
0
-2
1/2
1
—
3
x2
2
0
1
1/2
-1/8
0
—
σj
0
0
-3/2
-1/8
0
第九步,表5最后一行的所有检验数σj都已为负或零,这表示目标函数值已不可能再增大,于是得到最优解
且相应的最优值(即工厂的最大获利)f*=f(3)=14。
6.对偶问题
在线性规划问题中,任何一个求最大值的规划问题必有一个求最小值的规划问题与之相对应,二者含有相同的数据,且它们的解也有密切联系,反之亦然。
若两个问题中,其中一个称为原问题,则另一个就称为对偶问题。
(1)对偶问题的关系
已知下列两个线性规划问题Ⅰ、Ⅱ是互为对偶的,其中
问题Ⅰ:
问题Ⅱ:
不难发现,互为对偶的两个问题之间具有以下关系:
一个问题目标函数的系数是另一个问题约束条件右端的常数;
一个问题第i个约束条件的各系数是另一个问题第i个变量的约束条件系数;
一个问题是求目标函数的最大值,其约束条件均为“≤”形式,而另一个问题则是求目标函数的最小值,其约束条件均为“≥”形式;
两个问题的变量均是非负的。
(2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 规划 基础