《(第五、六章 目标规划和整数规划.ppt》由会员分享，可在线阅读，更多相关《(第五、六章 目标规划和整数规划.ppt（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章 目标规划n多目标 的线性规划问题(多目标 决策),而非单目标.n如一个生产经理也许想兼顾满足客户需求、降低生产成本、减少加班时间和提高劳动生产率等多重目标。n目标规划寻找最接近于实现一组目标的满意解n其模型是在线性模型的基础上,利用正负偏差变量(d+,d-)、优先因子(pk,pkpk+1)、权系数,对同等级或不同等级的目标进行设置.n因其模型结构与线性规划的数学模型结构没有本质的区别,所以可用单纯形法求解.某厂生产A、B两种产品，生产过程必须经过两个车间，有关数据见表。决策者在车间1的加工时间受到严格限制的基础上考虑以下目标：首先是产品B的产量不超过10单位；其次是利润额不低于1600
2、元；再次是充分利用车间2的正常生产时间，不加班。提交一个考虑上述目标的生产方案。产品A产品B正常工作时间车间12小时1.5小时50车间21小时2小时40单位利润80100分别在两个车间的加工时间 x1、x2分别为产品A、产品B的生产数量；目标1可能满足也可能不满足，即产品B的产量可以在10左右有所偏差。x2+d1-d1+=10。同样，目标2和目标3也可能满足或不满足，80 x1+100 x2+d2-d2+=1600,x1+2x2+d3-d3+=40。另外，还有一个非弹性约束：2x1+1.5x250。目标函数：使各目标的偏差达到最小。首先追求目标1的偏差最小，P1 min(d1+)；其次追求目标
3、2的偏差最小，P2 min(d2-)；最后追求目标3的偏差最小，P3 min(d3-)+min(d3+)。故目标规划模型为：min z=P1d1+P2d2-+P3(d3-+d3+)s.t.2x1+1.5x250 x2+d1-d1+=10 80 x1+100 x2+d2-d2+=1600 x1+2x2+d3-d3+=40 x1，x2，di-，di+0目标规划的一般模型 min z=Pm(w di-+w di+)s.t.aij xj+di-+di+=bi aij xj(=、)bi xj、di-、di+0其模型是在线性模型的基础上,利用正负偏差变量(d+,d-)表示富有弹性的约束，并用优先因子(pk
4、,pkpk+1)、权系数w,对同等级或不同等级的目标进行设置.目标函数追求偏差的最小。某单位决策者在考虑本单位职工的升级调资方案时，依次遵守以下规定：（1）不超过年工资总额600000元；（2）每级的人数不超过定编规定的人数；（3）、级的升级面尽可能达到现有人数的20%；（4）级不足编制的人数可录用新职工，又I级的职工中有10%要退休。等级工资额（元/年）现有人数编制人数I200001012II150001215100001515决策变量：x1、x2、x3分别表示提升到I、II和录用到级的新职工人数。所有规定都允许突破：20000（10-10*10%+x1)+15000(12-x1+x2)+1
5、0000(15-x2+x3)+d1-d1+=60000010-10*10%+x1+d2-d2+1212-x1+x2+d3-d3+=15 15-x2+x3+d4-d4+=15 x1+d5-d5+=12*20%x2+d6-d6+=15*20%x1、x2、x3、di-、di+0，且x1、x2、x3为整数 目标函数：min z=P1d1+P2(d2+d3+d4+)+P3(d5-+d6-)某国家森林公园有30000公倾林地，可用于散步、其它休闲活动、鹿群的栖息地以及木材砍伐。每公倾林地可供150人/天漫步用，300人/天作其它休闲活动，1只鹿栖息或砍伐出1500立方米木材。为漫步者维护1公倾林地一年的费
6、用为100镑，为其它休闲活动维护1公倾林地一年的费用为400镑，为鹿群使用维护1公倾林地一年的费用为50镑。第一公倾林地砍伐出的木材收入为2000镑，这种收入必须能够补偿所有林地的成本。林地的监护人的目标有多个，按优先次序排列如下：（1）漫步者人数一天至少达到200万；（2）其它休闲活动的人数一天至少达到500万；（3）满足3000只鹿的生活；（4）砍伐出的木材不超过600万立方米。请编写一个目标规划模型 决策变量：x1=留给漫步者使用的面积，x2=留给其它休闲活动者的面积，x3=留给鹿群的面积，x4=留作砍伐的林地面积。有两个硬性约束：1.林地总面积：x1+x2+x3+x430000 2.砍
7、伐收入应补偿全部费用：2000 x4100 x1+400 x2+50 x3同时，有一系列目标约束：3.150 x1+d1-d1+=2000000（漫步者人数）4.300 x2+d2-d2+=5000000（休闲者人数）5.x3+d3-d3+=3000（鹿的数量）6.1500 x4+d4-d4+=6000000 （砍伐限制）目标函数：min z=P1d1-+P2d2-+P3(d3+d3-)+P4d4+目标规划的求解n图解法(两个决策变量)n单纯形法(两个以上决策变量)l 先不考虑正负偏差变量，作相应的直线l找出硬约束所围的可行区域l对于软约束，在相应的直线上标出正负偏差变量的方向l根据目标函数的
8、优先因子和偏差变量分析求解例如：前面第一个目标规划模型图解法单纯形法n由于目标规划的目标函数中含有优先因子，所以在单纯形表中，将检验数行按优先因子的个数分成k行n用单纯形法求解(同前)例如：前面第一个目标规划模型第七章 整数规划n最优解不是分数或小数,而是整数的情形.n整数规划的一种特殊情形是0-1规划,如指派问题.n整数规划的解法有割平面法、分枝定界法。0-1规划的解法有0-1隐枚举法.整数规划纯整数规划混合整数规划割平面法n适用：纯整数规划、混合整数规划n基本思想：对已给的IP问题，先不考虑其整数条件，而解一个相应的LP问题。若此LP问题的最优解满足整数要求，则它也是所求IP问题的最优解；
9、若LP问题的最优解中至少有一个变量取值不满足整数要求，则对该LP问题增加一个线性约束条件(几何上称为割平面)再行求解。分支定界法n适用：纯整数规划、混合整数规划n基本思想：先求相应的线性规划的最优解，如果得到的解不符合整数条件，就将原规划问题分成几支，每支增加约束条件(即缩小可行域)，再求解，进行比较可得最优解。整数规划的软件求解n可用Lindo软件求解整数规划。n约束条件输完以后，输“end”结束，然后定义整数变量类型(一般整数变量用int表示，0-1变量用gin表示)n不能使用灵敏度分析功能n可用专门的整数规划程序求解，需输入：目标函数、约束条件、01变量、整数变量。0-1变量的应用凡是碰
10、到“是与否”、“有与无”、“选与不选”这类决策问题，都要用01变量。用01变量可以成功地解决从n个方案中挑出k个方案、两个方案之间有相互依存(如A为B的前提或选A必定选B)的情形。固定成本问题场所选择问题投资选择资金预算分布系统设计场所选择 某公司拟在市东、西、南三区建立门市部,拟议中有7个位置Ai（i=1,2,7）可供选择,规定:在东区,由A1,A2,A3三个点中至多选两个;在西区,由A4,A5两个点中至少选一个;在南区,由A6,A7两个点中至少选一个.如选用Ai点设备投资估计为bi元,每年可获利润估计为ci元,公司投资总额不能超过B元。如何选择使年利润最大?建立01整数规划模型引入0-1变
11、量,令于是:max z=s.t.Xi=1,当Ai点被选用0,当Ai点没被选用资金预算 某电冰箱公司正在考虑随后4年内有不同资金要求的投资方案。面对每年有限的资金，管理者需要选择最好的方案。每种方案贴现后的净获益、资金需求和4年内拥有的资金见表。项目每年可用资金工厂扩张 仓库扩张新机器新产品研究贴现净收益9万4万1万3.7万第1年资金第2年资金第3年资金第4年资金1.5万2万2万1.5万1万1.5万2万0.5万1万4万1.5 万1万1万1万4万5万4万3.5万 x1=1，若选择工厂扩张方案 =0，若不选此方案 x2=1，若选择仓库扩张方案 =0，若不选此方案 x3=1，若选择机器更新方案 =0，
12、若不选此方案 x4=1，若选择新产品研究方案 =0，若不选此方案 max z=9x1+4x2+x3+3.7x4 s.t.1.5x1+x2+x3+1.5x44 2x1+1.5x2+x45 2x1+2x2+x44 1.5x1+5x2+4x3+x43.5 x1,x2,x3,x4=0/1 如果 工厂扩张方案是仓库扩张的前提条件，则增加一个约束：x2x1如果工厂扩张，仓库就必须扩张，则增加约束：x1=x2分布系统设计 某公司在(A1)圣路易斯经营一家年产量为30千箱的工厂。产品被运输到位于Boston、Atlanta、Houston的地区分销中心。由于预期将有需求增长，该公司计划在底特津(A2)、托莱多
13、(A3)、丹佛(A4)、堪萨斯(A5)中的一个或多个城市建立新工厂以增加生产量。各地建厂的固定成本、年产量及各工厂到三个分销中心的单位运价如 P168所示。请决定建哪一个或哪些工厂？n此问题是(选址问题+运输问题)n决策变量：选址问题的0-1变量 运输问题的变量n目标函数：建厂的固定成本+年运输成本n这一基本模型可以被扩展，解决涉及直接运输和多种产品的分布系统。n利用0-1变量的特性，此模型还可以扩展解决含有多种厂址约束条件的问题。如，若选址A2与A3两城市相距太近，公司也许不愿意同时在这两地建厂。只需在基本模型中增加一个约束：y2+y31 第八章 动态规划n解决多阶段决策过程最优化.只是求解
14、某类问题的一种思维,是考察问题的一种途径,而不是一种特殊算法(如线性规划是一种算法),因而没有一个标准的数学表达式和明确定义的一组规则,必须对具体问题进行具体分析处理.动态规划方法的基本思想n动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件(即基本方程).所以,必须先将问题的过程分成几个相互联系的阶段,恰当地选取状态变量和决策变量及定义最优值函数,从而把一个大问题化成一族同类型的子问题,然后逐个求解.例1：最短路问题AB1B2B3B4C1C2C3D1D2E43322164724837518675161061061211111213141214阶段4阶段3阶段2阶段1基本概念n阶
15、段：根据实际问题所处的时间、空间或其它条件，把所研究的问题恰当地划分为若干个相互联系的阶段n用k=1,2,n 表示阶段序号，如例1，k=1,2,3,4n状态：表示某阶段的初始条件n例1中，第1阶段有2个状态D1、D2nsk:第k阶段的状态，称sk为第k阶段的状态变量n第k阶段的状态集合Sk=sk n例1中，S1=D1、D2 n决策：某阶段的抉择nxk：第k阶段的决策，称xk为第k阶段的决策变量n决策与状态有关，随状态而变，是状态变量的函数n状态转移方程：从一个状态到别一个状态的演变过程nsk+1=f(sk,xk)n策略：由各阶段决策xk(k=1,2,n)构成的决策序列，称为全过程策略，简称为策
16、略，简记为p1=x1,x2,xnn由第k阶段到最终阶段的决策组成的序列，称为第k子过程策略，简称k子策略，简记为pk=xk,xk+1,xnn指标函数：衡量策略功子策略或决策的效果的某种数量指标n不同问题，指标函数不同，可以是费用、成本、产值、利润、产品、距离、时间、效用等n阶段指标：vk(sk,xk)是第k阶段处于sk状态且所做决策为xk时的指标n例1中 v2(B1,C1)=2(表示sk点到xk点的距离)n过程指标函数：fk(sk)是第k子过程的指标函数n例1中fk(sk)表示第k阶段sk状态时，从sk到终点的距离nfk(sk)严格说应写作fk(sk,pk(sk)n上述两者间的关系，常见的形式
17、有：nfk(sk)=vk(sk,xk)nfk(sk)=vk(sk,xk)n最优函数：指标函数的最优值称为最优函数，记为fk*(sk)，表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。即fk*(sk)=opt fk(sk,pk(sk)n基本方程：对于n阶段的动态规划问题，在求子过程上的最优指标函数时，k子过程与k+1子过程有如下递推关系(当过程指标函数为“和”的形式 fk(sk)=vk(sk,xk)时)：fk*(sk)=opt vk(sk,xk)+fk+1(sk+1),k=n,n-1,1 边界条件：fn+1*(sn+1)=0n例1中，k阶段与k+1阶段的递
18、推关系为：fk*(sk)=min vk(sk,xk)+fk+1(sk+1),k=n,n-1,1 边界条件：f5*(s5)=0n当过程指标函数为下述“积”的形式时 fk(sk)=vk(sk,xk)相应的函数基本方程为：fk*(sk)=opt vk(sk,xk)*fk+1(sk+1),k=n,n-1,1 边界条件：fn+1*(sn+1)=0例如：资源分配问题 某厂为扩大生产能力，拟订购某种成套设备46套，发分配给其所辖1，2，3三个分厂使用，预计各分厂分得不同套数的设备后，每年创造的利润(万元)如表所示，该厂应订购几套设备并如何分配，才能使每年预计创利总额最大？套数分厂01234561035676
19、520467891030259887生产与存贮问题 某厂根据市场预测，确认今后四个月访该厂的一种主要产品每月需求量如表。已知每月生产固定费用2千元，产品成本为1千元/万件，贮存费用0.2千元/万件/月，每月最大生产能力为5万件，最大存贮能力4万件。若第1月初无库存，第月月末也不库存，则该厂应怎样安排生产和存贮，才能使今后四个月的总费用最少？月1234需求量(万件)3232定价问题n例:某厂要确定一种新产品在今后五年内的价格,并已拟定只在5,6,7,8元这四种单价中进行选择.据预测,今后五年不同价格下每年盈利(万元)如下表所示,但是各相邻年度价格不得超过1元.问今后五年内每年定价各为多少,可预期五年总利润最大?上表 年价格 1 2 3 4 5 5 9 2 4 5 8 6 7 5 8 6 4 7 6 5 9 7 3 8 8 7 6 6 4