数学建模优化理论与方法.ppt
《数学建模优化理论与方法.ppt》由会员分享,可在线阅读,更多相关《数学建模优化理论与方法.ppt(179页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、 数学规划的理论与方法数学规划的理论与方法1.线性规划理论与方法线性规划理论与方法2.目标规划的理论与方法目标规划的理论与方法3.整数规划的理论与方法整数规划的理论与方法4.非线性规划的理论与方法非线性规划的理论与方法5.动态规划动态规划6.最优控制理论最优控制理论y一一.线性规划的理论与方法线性规划的理论与方法 线性规划是指目标函数是由线性函数给出,约束条件由线性等式或者不等式给出的优化问题。最早提出线性规划问题并进行专门研究的学者康托洛维奇。康托洛维奇在20世纪30年代就提出了求解线性规划问题的“解乘数法”。自从1947年美国学者丹青格提出求解线性规划问题的一般方法单纯形方法 后,才使线性
2、规划的理论和方法日臻成熟。(1)由决策变量构成,反映决策的目标是线性函数。(2)一组由决策变量的线性等式或不等式构成约束 条件。(3)对决策变量取值范围加以限制的非负约束。1.1线性规划模型的特征线性规划模型的特征 例1:某工厂生产甲、乙两种产品,每件产品的利润、所消耗的材料、工时及每天的材料限额和工时限额,如表1.1所示。试问如何安排生产,使每天所得的利润为最大?表表1.11.1甲乙限额材料2324工时3226利润(元/件)43设每天生产甲、乙两种产品分别为 x1 ,x2 则该问题可描述为由如下数学模型:1.2线性规划问题的标准型线性规划问题的标准型如下形式的线性规划模型被称作标准型:也可用
3、矩阵形式描述:A:资源消耗系数矩阵b:资源限量向量C:价格向量X:决策变量向量同时我们对标准型作如下假定:一般的线性规划问题通过变换可化成标准型,变换方式可以归结为:1.3线性规划问题解的概念线性规划问题解的概念对于线性规划问题可行解基解基可行解1.4线性规划问题的图解法线性规划问题的图解法下面结合例1的求解来说明图解法步骤。例1第一步:在直角坐标系中分别作出各种约束条件,求出可行域(图中阴影部分)。x2Q2(6,4)x13x1+2x2=262x1+3x2=24ZOQ1(26/3,0)Q3(6,4)第二步:作出一条目标函数等值线,并确定 Z 值增大的方向。第三步:沿 Z 值增大方向移动,当移至
4、 Q2(6,4)点时,Z 值为最大,Z*=36.1.5基本定理基本定理 从理论上来讲,采用“枚举法”找出所有基可行解,并1.6求解求解线性规划问题的单纯形方法线性规划问题的单纯形方法 一一比较,一定会找到最优解。但当 m,n 较大时,这种方法是不经济和不可取的。下面介绍求解线性规划问题的有效方法单纯形方法。单纯形法的实质是从一个基可行解向另一个基可行解(极点到极点)的迭代方法。以下通过例1的求解过程说明单纯形方法的基本步骤。例1:第一步:第一步:引进松驰变量 x3,x4 将原问题化为标准型。标标准准型型第二步:第二步:找出初始可行基,建立初始单纯形表。见下表1.2。cj 4 3 0 0 CBX
5、Bb x1 x2 x3 x400 x3x42426 2 3 1 0 3 2 0 1Z0 -4 -3 0 0 表 1.2第三步:第三步:最优性检验。第四步:第四步:换基迭代。cj 4 3 0 0 CBXBb x1 x2 x3 x400 x3x42426 2 3 1 0 3 2 0 11226/3Z0 -4 -3 0 0 04x3x120/326/3 0 5/3 1 -2/3 1 2/3 0 1/3413Z104/3 0 -1/3 0 4/3表1.3同理,确定 x2 换入,x3 换出,继续迭代得表 1.3 cj 4 3 0 0 CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -
6、2/5 1 0 -2/5 3/5Z36 0 0 1/5 6/5 表 1.3 表中最后一行的所有检验数都已是正数或零,从而得到基本最优解 X*=(6,4,0,0)T,Z*=36。由于 x3,x4 是引进的松弛变量,因此原问题的最优解为 x1=6,x2=4,最优值 Z*=36。例2 一奶制品加工厂用牛奶生产 A1,A2 两种奶制品,1 桶牛奶可以在设备甲上用 12 小时加工成 3 公斤 A1,或者在设备乙上用 8 小时加工成 4 公斤 A2。根据市场需求,生产的 A1,A2 全部能售出,且每公斤 A1 获利 24 元,每公斤 A2 获利 16 元。现在加工厂每天能得到 50 桶牛奶的供应,每天正式
7、工人总的劳动时间为 480 小时,并且设备甲每天至多能加工 100 公斤 A1,设备乙的加工能力没有限制。试为该厂制定一个 我们无意过深涉及线性规划的具体计算方法,而着重介绍的是如何建立若干实际的线性规划模型,如何使用现成的数学软件进行求解,以及如何对结果进行深入的分析。下面以奶制品加工生产计划为例,进行详细的讨论。生产计划,使每天获利最大,并进一步讨论以下 3 个附加问题:若用 35 元可买到 1 桶牛奶,买吗?若买,每天最多 买多少?若可以聘用临时工人以增加劳动时间,付给临时工人 的工资最多是每小时几元?由于市场需求的变化,A1 的获利增加到 30元/公斤,应否改变生产计划?1桶牛奶 3公
8、斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶时间480小时 至多加工100公斤A1每天:分析x1 桶牛奶生产 A1 x2 桶牛奶生产 A2获利 243x1获利 164 x2决策变量决策变量 数学模型原料供应原料供应 劳动时间劳动时间 加工能力加工能力 非负约束非负约束 解法1:图解法。x1x20ABCDl1l2l3l4l5约约束束条条件件Z=0Z=2400Z=3360c从图中可以看出,在 B(20,30)点得到最优解。解法2:软件实现。求解线性规划有不少现成的数学软件,比如用 LINDO 软件就可以很方便地实现。在 LINDO6.1版本下打开一个新文件
9、,像书写模型一样。直接输入:max72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100end注:LINDO中已规定所有决策变量均为非负,故变量非负的条件不必输入。输入文件中第1行为目标函数,2),3),4)是为了标示各约束条件,便于从输出结果中查找相应信息;程序最后以end 结束。将文件存储并命名后,选择菜单“Solve”并对提示“DO RANGE(SENSITIVITY)ANALYSIS?”回答“是”,即可得到如下输出:OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000
10、000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2,利润,利润3360元。元。原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40三三种种资资源源“资源资源”剩余剩余为零的约束为为零的约束为紧约束(有效紧约束(有效约束)约束)结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUC
11、EDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增的增量量原料增加原料增加1单位单位,利润增长利润增长48时间增加时间增加1单位单位,利润增长利润增长2加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格35元可买到元可买到1桶牛奶,要买吗?桶牛奶,要买吗?350,并将各个约束条件加到目标函
12、数上,得一新函数如下:可以看出,当 时,有 ;当 时,由于M 很大,将使 很大,从而使很大,这就相当于对非可行点的“惩罚”。而且,X 点离可行域越远惩罚越严厉。可以想见,当 M 变得足够大时,相应于这样的 M 值,(4.12)的无约束极小点 X(M),就会和原来的约束问题的极小点足够接近。而当 时,它就成为原约束问题的极小点。惩罚函数(4.12)也可改写成另外的形式:或者:是阶越函数:假定对某一罚因子,例如说 M1,就加大罚因子的值。随着罚因子数值的增加,惩罚函数中的惩罚项所起的作用随之增大,minP(X,M)的解 X(M)离可行域 R 的“距离”就会越来越近,当趋于无穷大时,点列 X(Mk)
13、就从可行域 R 的外部趋于原非线性规划问题的极小点。和不等式约束问题类似,对于等式约束问题,即:采用以下形式的罚函数:对于既包含等式约束又包含不等式约束的一般非线性规划问题(4.1),其罚函数为或罚函数法的迭代步骤如下:(1)取第一个罚因子 M1 0 (例如M1=1),允许误差 ,并令 k:=1。(2)求下述无约束极值问题的最优解:其中P(X,Mk)可取式(4.15)或(4.16)的形式。设其极小点为 X(k)。(3)若存在某一个 ,有或存在某一个 ,有则取 Mk+1Mk(例如 Mk+1=cMk,c=10),并令 k:=k+1。然后,转回第(2)步。否则,停止迭代,得所要的点 X(k)。4.6
14、.2 4.6.2 障碍函数法障碍函数法(内点法)内点法)罚函数法的一个重要特点,就是函数 P(X,M)可在整个 En 空间内进行优化,可以任意选择初始点,这给计算带来了很大方便。但由于迭代过程常常是在可行域外进行,因而不能以中间结果直接作为近似解使用。如果要求每次的近似解都是可行解,以便观察目标函数值的改善情况;或者,如果目标函数在可行域外的性质比较复杂,甚至没有定义,这时就无法使用上面所述的罚函数法了。障碍函数法与罚函数法不同,它要求迭代过程始终在可行 域内部进行。考虑非线性规划(4.3),当 X 点从可行域 R 内部趋于其边界时,至少有某一个约束函数 趋于零。从而,下述倒数函数和对数函数都
15、将无限增大。如果把式(4.17)或(4.18)加到非线性规划(4.3)的目标函数上,就能构成新的目标函数障碍函数。或 如果从某一点 出发,求下列无约束极小化问题 则随着障碍因子 的逐渐减小,即障碍项所起的作用也越来越小,因而,求出的问题(4.21)的解 就会逐步逼近原约束问题(4.3)的极小解。障碍函数法的迭代步骤如下:(1)取第一个障碍因子 ,允许误差 ,并令 k:=1。(2)构造障碍函数,可采取(4.19)或(4.20)。(3)对障碍函数进行无约束极小化,设所得解为 。(4)检查是否满足收敛准则:或如果满足此准则,则以 X(k)为原约束问题的近似极小解,停止迭代;否则,取 rk+1 rk,
16、令 k:=k+1,转回第(3)步继续进行迭代。五五.动态规动态规划划动态规划是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼等人在 20 世纪 50 年代初提出的。他们针对多阶段决策问题的特点,提出了解决这类问题的最优化原理,并成功地解决了生产管理、工程技术等方面的许多实际问题。多阶段决策问题的特点是整个决策过程可以分为好几个彼此有联系的阶段,而每一个阶段都有多于一个的小方案需要选择确定,决策者需要在可供选择的小方案中选出其中的一个最优方案,使其效果在预定的目标下达到最好。A5BDFCE11121067一个简单的多级决策:有某旅行者从 A 地出发到 F 地,可以选择两条路线
17、,一是途经 B 地,D 地到 F;另一是途经 C 地,E 地到 F(如图),每段路程所需的费用在图中标出。这个问题是以总旅费达到最小作为目标,显然应选择:A C E F。整个规划的目标是使得最终结果达到最优,这就意味着,某一段作出的决策,就这个阶段来说,并不一定是一个最优的选择,甚至要作出某些牺牲(如上例第一段)。但是由于各阶段的相互影响,到最后却会得到一个最优的结果。相反,在这一阶段选择了一个最优的决策,并不等于最后得到最优结果,这就是动态规划的特点。使用动态规划方法解决多阶段决策问题,首先要将实际问题写成动态规划模型,此时要用到以下概念:(1)阶段;(2)状态;(3)决策和策略;(4)状态
18、转移;(5)指标函数。下面我们结合以下例题说明这些概念。例 5.1 最短路线问题。如图所示,给定一个线路网络图,要从 A 地向 F 地铺设一条输油管道,各点间连线上的数字表示距离,问应选择什么线路,可使总距离最短?A468335425B1B2E2FD1E1C1C2C3C4D3D2737835448431265(1)阶段。将所给问题的过程,按时间或空间特征分解成若干互相联系的阶段,以便按次序去求每阶段的解。(2)状态。各阶段开始时的客观条件叫状态。描述各阶段状态的变量称为状态变量,sk 表示第 k 阶段的状态变量,sk 的取值集合称为状态集合,用 Sk 表示。在例5.1中,各阶段的状态集合分别是
19、:当某段的初始状态已选定某个点时,从这个点以后的铺管路线只与该点有关,不受以前铺管路线的影响,这叫状态变量的“无后效性”,如果所选的状态变量不具备“无后效性”就不能用来构造动态规划模型。(3)决策和策略。当各段的状态取定以后,就可以作出不同的决定,从而确定下一阶段的状态,这种决定称为决策。表示决策的变量,称为决策变量,常用 uk(sk)表示第 k 阶段当状态为 sk 时的决策变量,Dk(sk)表示第 k 阶段从状态 sk 出发的允许决策集合。在例5.1中,有 D2(B1)=C1,C2,C3 如我们决定选择 C3,则可表为:u2(B1)=C3 各段决策确定后,整个问题的决策序列就构成一个策略,用
20、 p1,n u1(s1),u2(s2),un(sn)表示,P1,n 表示允许决策的集合,使整个问题达到最优效果的策略就是最优策略。(4)状态转移方程。动态规划中,如果给定了第 k 阶段的状态 sk 和本阶段决策 uk(sk)则第 k+1 段的状态 sk+1 也就完全确定,它们的关系可用下列状态转移方程表示:sk+1=Tk(sk,uk)例5.1中,状态转移方程为:sk+1=uk(sk)(5)指标函数。用于衡量所选定策略优劣的数量指标称为指标函数。它分 为阶段指标函数和过程指标函数两种。阶段指标函数是指第 k段,从状态 sk 出发,采取决策 uk 时的效益,用 d(sk,uk)表示。一个 n 段的
21、决策过程,从 1 到 n 叫做问题的原过程,对任意给定的 ,从第 k 段到第 n 段的过程称为原过程的一个后部子过程。V1,n(s1,p1,n)表示初始状态为s1 采用策略 p1,n 时,后部子过程的指标函数值,而Vk,n(sk,pk,n)表示在第 k 段,状态为 sk 采用策略 pk,n时,后部子过程的指标函数值。最优指标函数记为 fk(sk),它表示从第 k 段状态 sk 采用最优策略 到过程终止时的最佳效益值。即:当 k1 时,就是从初始状态 到全过程结束的整体最优函数。下面用动态规划方法求解例5.1。本方法是从过程的最后一段开始,用逆序递推方法求解,逐步求出各段各点到终点 F 的最短路
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 优化 理论 方法
限制150内