《数学规划建模》PPT课件.ppt

《《数学规划建模》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第五章数学规划方法建模§5.1引言§5.2单纯形法及其理论基础§5.3线性规划模型A奶制品生产销售计划B自来水输送计划§5.40-1线性规划模型A混合接力队最优组合B选课的策略§5.1引言线性规划是数学规划学科中研究得最彻底,同时也是应用最广泛的一个分支.本章简要介绍求解线性规划的单纯形法及0-1线性规划的一种解法,以及这些解法在数学软件Matlab中的实现.我们仍然以若干实际问题的整个数学建模过程为主要线索来展开.数学规划广泛用于解优化问题优化问题可以说是人们在科技和经济管理方面最常见的实际问题,而数学规划则是解决优化问题的最基本方法.对优化问题进行数学建模时,先要设定决策变量,通

2、常有多个决策变量,用n维向量x=(x1,…,xn)T表示;其次要确定被优化的目标函数(x的函数):z=f(x).实际问题一般对决策变量有限制,记为xD,D称为可行域,可行域常用一组不等式(包括等式):gi(x)0,i=1,…,m来界定.数学规划,线性规划的一般形式一般数学规划模型可以表述为:Min(或Max)z=f(x)s.t.gi(x)0,i=1,…,m其中,x=(x1,…,xn)T,Min(Max)表示求最大(小)值;s.t.表示”满足条件:”.线性规划模型(限于线性情况)表述为:Min(或Max)z=c1x1+…+cnxns.t.ai1x1+…+ainxn(或)bi,

3、i=1,…,mxj(或)dj,j=1,…,n其中,ai,bi,ci,dj为已知常数.线性规划的标准形式线性规划的特征是:在满足一组线性约束和变量非负的限制条件下,求多变量线性函数的最小值或最大值.这一特征决定了所有线性规划都可以化为唯一的标准形式:Minz=c1x1+…+cnxns.t.ai1x1+…+ainxn=bi,bi0,i=1,…,mxj0(即dj=0),j=1,…,n因此,可以只限于讨论标准型线性规划的求解.思考题5-1:分别论证各种形式的线性规划模型都可以化为标准型.线性规划的可行解与最优解满足全部约束(包括非负约束)条件的向量x=(x1,…,xn)T称为线性规划

4、问题的可行解.所有可行解的集合称为可行域.为了保证可行域非空,一般要求nm.使目标函数达到最优值的可行解称为该线性规划的最优解.或者说,最优值既满足约束条件,并且使目标函数达到最优值.线性规划的一个简例(游戏机问题)游戏机制造商关心的问题是:为了求得最大利润,下一个周期应该生产两种不同型号的游戏机各多少台?有关背景信息是:每台I型机可得利润6个单位,每台Ⅱ型机可得利润4个单位.而生产一台I型和Ⅱ型游戏机需要原料分别为2个单位和3个单位,需工时分别为4个单位和2个单位.计划可用原料为100个单位,可用工时为120个单位.游戏机问题的数学模型令x1,x2分别表示I型和Ⅱ型游戏机的生产台

5、数.不难看到,利润函数为z=6x1+4x2,例润最大的要求就是Maxz=6x1+4x2约束条件是2x1+3x2100(原材料单位)4x1+2x2120(工时单位)x1,x20(非负数限制)由此可见,游戏机问题归结为一个线性规划模型.Fx1x2AEBD10106050图5-1C解游戏机数学模型的几何图解法第①步:第一个和第三个约束条件确定三角形区域ABF.第二个和第三个约束条件确定三角形区域AED.因此,可行域为:D=ABF∩ADE=四边形域ABCD.第②步:对于0+考虑目标函数的等高线(平行直线族):6x1+4x2=.易见,当>200时,直线6x1+4x2=

6、与可性域无交点;而当=200时,则与可性域交点为凸四边形的顶点C,这就证明,目标函数在点C取得最大值,点C的坐标为方程组2x1+3x2=1004x1+2x2=120的解.不难看出这个方程组的解是:x1=x2=20.所以,下一个周期安排生产两种型号的游戏机各20台,便能获取最大利润为z=6(20)+4(20)=200(单位)注:上述图解法说明,线性规划问题的可性域由凸多边形构成,并且最优解在此多边形的顶点达到.线性规划可行解的几何性质定理5.1任一线性规划的可行域都由一个凸集(凸多面体)D={x

7、pi1x1+…+pinxn=hi,hi0,i=1,…,k;x1,…,xn0}构成;

8、如果线性规划存在最优解,则最优解必在可行域的顶点上达到.证明:略.§5.2单纯形法及其理论基础按定理5.1,线性规划最优解只能在一个凸多面体的可行域的顶点上达到.由于顶点数目不超过Cnm个,采用”枚举法”,即通过比较所有顶点处目标函数的值,最终可以找到最优解.但枚举不是好算法.例如,当n=60,m=30时,Cnm大于1017,即使在每秒万亿次浮点运算的超级计算机上也要花上几年才能完成.本节介绍1974年G.M.Dantzig提出的一种非常有效的好算法---