工程实际应用中优化问题的三种分析求解方法的比较Word下载.docx
《工程实际应用中优化问题的三种分析求解方法的比较Word下载.docx》由会员分享,可在线阅读,更多相关《工程实际应用中优化问题的三种分析求解方法的比较Word下载.docx(16页珍藏版)》请在冰点文库上搜索。
然后按照传统的几何线性规划方法进行函数的儿何图形分析,找出符合算例条件的最优解,将线性规划单纯形法的计算结果与线性规划几何图形分析结果进行初步比较。
【解算一】设变量Xi、X2分别表示该工厂在计划期间内所生产的产片I和II的产量,可得四种设备的约束条件为:
"
2X1+2X?
<
12
X]+2x2<
8
阿516⑴
4x.<
■
依照算例要求,可以知道该工厂的目标是在不超出所有设备的生产能力前提下,通过计算确定心、X2,使得到的利润最大,若用y表示利润,则可以得到利润表达式为:
y=2xi+3x2
此时,我们便可以利用上面得到的约束条件以及目标函数建立相应的线性规划数学模型:
求设计变量:
X=pix2]r
使目标函数:
y=2xi+3x2
达到最大值,其约束条件为:
2X]+2x2<
Xj+2x3<
8
<
4Xi<
16
•■
为了方便计算求解,将此处的约束条件
(1)转化为单纯形法求解的标准形式
(2):
2X]+2x?
+x3=12
X]+2x.+xd=8
1⑵“4齐+冷=16
4勒+Xg=12
>
即求:
x=(xhx2/x3lx4ix5ix6)t
使得:
niinf(x)=一2xi-3x2满足
(2)。
此时将目标函数转化为约束方程类似形式:
f+2xi+3x2=0
此处解算过程采用单纯形法来求解,建立初始单纯形表如下表2:
表2单纯形法求解图I
f
X1
*2
X3
X4
X5
X6
2
x5
3
按照课程中所学的单纯形表优化方法,先对该表格通过假设初始解求解出一组可行解,因此这里首先假设X1=X2=O,可以同时求出如下一组解向量:
X=(0,0,12,8,16,12)T
随即求出该解向屋下的目标函数值为:
f(x「X2)=0
可以看出,这里求得的可行解并非址优解,因此有必要对其进行优化,具体优化过程如下所示:
1考察f行中除f所在列以外的所有数是古都为非正,占则规划结构尚有改善余地,这里f行中除f所在列以外的数字为2、3、0、0、0、0、0,均为非负数,故尚有改善余地:
2对表2首先寻找其改善变量,调整可行解,从而产生新的单纯形表,进而对表2进行优化。
按照优化过程要求,首先在f行除f列以外的正系数中选一最大数,与该数对应的变量即为改善变量,本算例中所选取的最大数为3,所对应的变量为X2;
再在该改善变量所在列上,将每一个正数(该数除外)除最右边一列,在所得商中找出最小者,此处
min(12/2,8/2,12/4)=3
所对应的行为表2中心所在的行,于是开始选取f行上f列除外的最大正数所在列(此处为X2对应的列)与上述最小值所在的行交义的数为主元(此处为4),然后化主元为1,再化主元所在列的其他元素为0(相当于将改善变量的值代入
除主元所在方程以外的各方程中去),得到下表3:
表3单纯形法求能图口
x丄
X2
Xs
Xfi
-0.5
6
x->
0.25
・3
・9
重复上述过程,观察表3可知f行中除f所在列以外只有一个非负数2,对应的改善变量即为X],然后在该改善变量所在列上,将该数除外的每一个正数除最右边一列,在所得商中找出最小者,此处
min(6/2^/l,16/4)=2
对应的主元为1,对应上述表3中X4所在的行,于是开始选収f行上f列除外的最大正数所在列(此处为X1对应的列)与上述最小值所在的行交叉的数为主元(此处为1),然后化主元为1(此处已无需化简),再化主元所在列的其他元素为0,得到下表4:
表4单纯形法求解图m
:
x2
x6
-2
0.5
Xl
・0.5
•4
•2
-13
此时通过观察可以看到,经过两次优化,表4中的f行中除f列外所有的数均为非正,目标函数值已经不能再改善,于是可以得到本算例线性规划的最优解为:
X]29X23,X329X4089X&
0
f(x)=-13
去掉松弛变S:
x3>
X4.X5、x6,即得到原问题的最优解为:
X=(2,3)t
至此解算方法一通过单纯形法求解该问题的方法演算完毕,卜•面通过线性规划的传统解析几何方法对该问题进行解算,将得到的结果与通过单纯形法解算所得到的结果进行比较,分析二考存在差异的原因。
【解算二】同解算一的己知条件,仅对假设变最作解析几何式变更,将己知条件化为二维x-o-y坐标系下的形式,设变量x、y分别表示该工厂在计划期间内所生产的产片I和n的产量,可得四种设备进行生产的约束条件为:
2x+2y<
x+2y<
4x<
4y<
依照算例要求,可以知道该匸厂的冃标是在不超出所有设备的生产能力前提下,通过计算确定x、y,使得到的利润最大,若用Z表示所得利润,则可以得到利润表达式为:
z=2x+3y
此时可以开始进行解析儿何方法的线性规划问题的求解。
首先在x-o-yY面二维
几何坐标轴上描绘出约束条件(3)所用成的几何区域,如下图所示:
图1解析几何表示约束区域
此处两条曲线
y=6-x
y=4-0.5x
0<
x<
4⑷
0<
y<
均为约束条件(3)所给岀的限制区域所取得的边界值,图中的阴影区域即是约束条件(3)所限定的排查区间,在此区间内通过对函数
z=2x+3y(5)
进行平行曲线推移取值排査,从而可以从图形中得到函数z(x,y)在区域上収得最大值时的位置,从而求得z的最大取值以及此时x、y所对应的函数值。
本算例中的图1是利用数学软件MATLAB的绘图功能所得到的图形,源程序如下:
x=linspace(0,6);
plot(x,6・x,x,4・0.5*xx3・0*x);
此处将x的取值范甬调整为OSX兰6是为了绘图方便。
现带入目标函数(5),将(5)式z=0的图形绘入以上限制区域示意图中,利用平行直线对z进行平行移动,使z分别在阴影区域中取得不同的值,当直线平行移动至刚好离开限制区域时的那一点或那一条边界即是z取得最值的点或边界。
如下图所示:
从图2中目标函数的滑移來看,由于目标函数(5)的曲线斜率«
满足:
21
—coVk]=—1<
kz=——<
k2=——<
o乙
其中ki、k2分别为曲线
y=6-x(6)
和曲线
y=4-0.5x(7)
的斜率,因此目标函数(5)取得域大值时应该落在曲线(6)和曲线(7)的交点上。
此时可求得两条曲线的交点为(x,y)=(4,2),此时目标函数(5)的值为z=14.
最终结果为:
X=(4,2)t
F=zmax=14
【讨论】针对本算例,通过单纯形法求解所得到原问题的最优解为:
X=(2,3)t
F=-f=13
而通过传统解析几何方法所得到的结果为:
F=Zmax=14
二考比较相差7.69%,通过传统解析儿何方法所得到的结果要比使用单纯形法求解所得到的结果更好。
分析來看产生这中结果的原因可能为:
1单纯形法求解过程为数值迭代过程,计算结果为近似结果,【解算一】中求解仅进行了2次迭代,因此结果未能达到迭代所能够达到的极值点,存在一定疑的计算误差:
2由于单纯形法求解考虑了匸程实际条件,同时生产4个台时数的产品I会造成生产设备的闲置,并非经济的做法;
在实际问题中,由丁•求解问题的复杂性,使用传统的解析儿何方法对线性规划问题进行求解的方法无法满足未知数个数大于2的解算要求,因此该方法不具备普遍适用性,如下而的算例:
【算例二】某学生学期末共有5门功课要考试,可用的复习时间为18小时。
假设5门课分别为:
高等数学、计算机文化基础、大学英语、建筑制图和土木工程壬业概论。
如果不复习而直接参加考试的话,这5门功课的预期考试成绩分别为65分、60分、70分、60分和65分,复习以1小时为一个单元,每增加1小时的复习时间,各门功课的考试成绩就有可能提高,每复习1小时各门功课考试成绩提高的分数分别为:
3分、4分、5分、4分・6分。
问:
如何安排各门功课的复习吋间可以使平均成绩不低于80分,并且数学和英语成绩分别不低于75分和75分?
【解析】假设分配在高等数学、计算机文化基础、大学英语、建筑制图和土木工程专业概论这五门课上面的复习时间分别为Xi、X2、X3、X4、X5,则可以写出如下的目标函数和限制条件:
minf(x)=X]+£
+X3+X4+X5
X1+X2+X3+X4+X5S18
(3xi+4x2+5x3+4x4+6x5+320)/5>
80
3xi4-65>
70
4x2+60>
75
此时使用单纯形法求解该问题就先得实用得多,而传统解析儿何方法在这电无法使用,因为未知数个数为5个,超岀了平而二维x-o-y坐标的范围。
对于目前实际生活中遇到的越来越复朵的问题,单•纯采用数值计算的人匸方法己经无法胜任庞大的计算量,因此采用编制计算机程序进行求解的方法逐渐显现出其实用性。
下面将用一个简单算例分别使用单纯形法、解析儿何法以及计算机程序(MATLAB实现)进行求解,将得到的结果进行比较,并分析结果出现差异的原因。
【算例三】某工厂要生产两种规格的电冰箱,分别用I和II来表示,生产电冰箱需要两种原材料A和E,另外需要设备C,生产两种电冰箱所需原材料、设备台时、资源供给董以及两种产品可获得的利润如表5所示,求解:
工厂应当分别生产I和II型电冰箱多少台,能使工厂或得的利润最大。
表5资源需求与限制条件
资源
资源限制
1200台时
原材料A
1800kg
原材料B
1000kg
单位产品获利
¥
220
250
求最大收益
电冰箱I用原材料限制
W800kg
【解析】设生产I和II两种型号的电冰箱的数最分别为X]、X2,则可或得的最大
收益为:
约束条件为:
【解算一】单纯形法求解:
根据目标函数(8)以及约束条件(9)的具体要求,将此处的约束条件(9)添加松
弛变最令其转化为单纯形法求解的标准形式(10):
舌+X?
+%=1200
(10)
2刍+x?
+x4=1800
“\+x5=800
x3+Xg=1000
即求:
x=(x1,x2,x3,x4,x5,x6)t
使得:
minf(x)=—220xi-250x2
满足(10)o此时将目标函数转化为约束方程类似形式:
f+220xi+250x2=°
然后建立初始单纯形表如下表6:
表6
1200
1800
800
1000
第一次优化后得结果如下表7:
200
-1
・250
-250000
在f行中并非所有元素都非正,故可以继续优化,第二次优化结果见表8:
表8
400
600
・220
-30
-294000
f行中除f列以外其他数均为非正,优化结束,此时计算所得的最优结果为:
X]=200,x2=1000,x3=0,x4=400,X5=600,x6=0
f(x)=-294000
去掉松弛变崑X3、X4、X5、X6,即得到原问题的最优解为:
X=(200,1000)T
F=-f=294000
【解算二】传统解析儿何方法求解:
依照本算例的限制条件(9)可绘制出如下图形:
图中阴影部分为限制条件(9)在x-o-y坐标平而内围成的取值区域,由于(9)中各边界曲线的斜率满足:
22
—covk]=—2<
k2=—l<
kz=———<
25
因此冃标函数(8)在图中阴影区域滑行时恰好离开限制区域边界时应为一定点,如图为边界直线X]+X2=1200与直线X2=1000的交点(200,1000),即此处目标函数(8)取得最大值,可得最优解结果为:
【解算三】MATLAB程序求解:
针对本算例编制的MATLAB程字如下:
clc;
closeall;
f=-[220250];
A=[l1;
21;
10;
01];
b=[1200;
1800;
800;
1000];
xl=[00];
[x4val]=linprog(f,A,bJ]4)^l);
xl=[0:
1800];
li
x2=[0:
2000];
[xinlmm2]=meshgiid(xl/2);
x21=1200-xl;
x22=l800-2*xl;
x23=(-fval-220*xl)/250;
plot(xl^c21^1^c22,[0:
1:
1000],1000,800,[0:
1500]?
xl^23,,r,)axis([0,1400,0^000])xlabelfxl1);
ylabelfx2);
holdoil
z=200*xml+250*xm2;
[C,h]=contour(xml,xm2,z);
texthandle=clabel(CJi);
set(text_handle,*BackgrouiidColor\[11Q/Edgecolor*』.?
.7.7]);
holdoffdispr*ctisp(x);
ctispffp;
disp(fval);
程序运行后的输出结果为:
Optimizationteniiinated.
x=
200.0000
1000.0000
-2.9400e+005
图形显示结果如右图所示:
通过比较本算例三种求解方法所得到的计算结果,发现三种方法的计算结果完全相同。