《优化方法运筹学》PPT课件.ppt

第四章 最优化方法(运筹学),第一节 线性(Linear Programing )规划 第二节 运输问题和指派问题 第三节 动态规划,问题？,怎样才是最漂亮的最帅？ 金字塔、巴特农神殿、巴黎铁塔等,在文艺复兴时期也更有许多以黄金比例创造出来旳作品 人从肚脐开始分,上半身到头,下半身到脚,这个比例符合 1:1.168 是最美旳。 鼻子以及嘴巴旳宽度 = 1:1.618。 鼻子侧面字型,鼻梁旳长度以及鼻尖高度旳比 = 1:1.618。 从正面看来嘴巴长度以及嘴角到脸部轮廓边旳长度比 = 1:1.618。 脸宽以及脸长各为眼睛长度旳 5 倍以及 8 倍,比 = 5:8。也相近于 1:1.618 欧洲的古代城堡为什么建成圆形？,案例：生产计划问题,例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：,问题：工厂应分别生产多少单位、产品才能使工厂获利最多？,第一节 线性规划,一、在管理中一些典型的线性规划应用 二、线性规划的一般模型 三、线性规划问题的计算机求解（Excel，lingo）,第一节 线性规划,一、在管理中一些典型的线性规划应用 1、合理利用线材问题：如何在保证生产的条件下，下料最少 2、配料问题：在原料供应量的限制下如何获取最大利润 3、投资问题：从投资项目中选取方案，使投资回报最大 4、产品生产计划：合理利用人力、物力、财力等，使获利最大 5、劳动力安排：用最少的劳动力来满足工作的需要 6、运输问题：如何制定调运方案，使总运费最小,小知识,茅于轼择优分配原理 茅于轼通过引进帕累托最优理论和帕累托改进理论，提出他的择优分配原理 帕累托最优（Pareto Optimality）是指资源分配的一种理想状态：如果固有的一群人和可分配的资源，从一种分配状态到另一种分配状态的变化中，在没有使任何人境况变坏的前提下，不会使任何一个人变得更好。帕累托改进（Pareto improvement）是指资源分配的一种改进状态：如果固有的一群人和可分配的资源，从一种分配状态到另一种分配状态的变化中，在没有使任何人境况变坏的前提下，可以使其中至少一个人变得更好。帕累托改进是达到帕累托最优的路径和方法。由于从帕累托改进到帕累托最优的核心精神是资源优化配置，而西方经济学的本质是配置经济学，“帕累托最优”、“帕累托改进”成了100多年来西方经济学的核心概念。,第一节 线性规划,二、线性规划的一般模型 （一）线性规划的组成： 目标函数 Max F 或 Min F 约束条件 s.t. (subject to) 满足于 决策变量 用符号来表示可控制的因素,第一节 线性规划,（二）建模过程 1.理解要解决的问题，了解解题的目标和条件； 2.定义决策变量（ x1 ，x2 ， ，xn ），每一组值表示一个方案； 3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标； 4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件,第一节 线性规划,（三）线性规划模型的一般形式 目标函数： Max （Min） z = c1 x1 + c2 x2 + + cn xn 约束条件：s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0,例题分析1：生产计划问题,例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：,问：工厂应分别生产多少单位、产品才能使工厂获利最多？,例题分析1：生产计划问题,解：工厂应分别生产、产品x1、x2单位，则所求的线性规划模型为： Max z = 50 x1 + 100 x2 s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0,例题分析2：食谱问题,例1 已知某人每周所需的营养成分、所食用的食品及单位食品所含营养如下表所示：,问这个人每周应食用大米、白菜、鸡蛋和猪肉各多少，能使生活费用最省？,例题分析2：食谱问题,解：设这个人每周应食用大米、白菜、鸡蛋、猪肉各为x1、x2、x3、x4，则所求的线性规划模型为： minZ = c1x1+c2x2+c3x3+c4x4 s.t. a11x1+a12x2 +a13x3+a14x4b1 a21x1+a22x2+a23x3+a24x4 b2 a31x1+a32x2+a33x3+a34x4 b3 x1,x2,x3,x4 0,小知识,明尼苏达大学建立食物营养价值评估数据库，可对每天需要的营养与食物作最优化选择 作业：建立自己的小营养优化选择,例题分析3：人力资源分配问题,例2某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：,设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时(注意每班次才4小时)，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?,例题分析3：人力资源分配问题,解：设 xi 表示从第i班次开始上班的司机和乘务人员数(i=1,2,3,4,5,6),这样我们建立如下的数学模型。 Min Z = x1 + x2 + x3 + x4 + x5 + x6 s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0,例题分析4：合理下料问题,例4 假定现有一批某种型号的圆钢长8米，需要裁取长2.5米的毛坯100根、长1.3米的毛坯200根，问应该怎样选择下料方式才能既满足需要，又使总的用料最省？ 解：各种可能的裁剪方案如下表所示：,例题分析4：合理下料问题,设 x1,x2,x3,x4 分别为上面4种方案下料的原材料根数。这样我们建立如下的数学模型。 Min f = x1 + x2 + x3 + x4 s.t. 3x1 + 2x2 + x3 100 2x2 + 4x3 + 6x4 200 x1,x2,x3,x4 0,例题分析5：投资问题,例5 某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知： 项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%； 项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元； 项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元； 项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。 问应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？,例题分析4：投资问题,解：设 xij ( i = 15，j = 14)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量： 1 2 3 4 5 A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24,例题分析5：投资问题,Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11(第二年的投资与第一年投资回收的本利金相等) x31 + x32+ x33 = 1.1x21+ 1.25x12 x41 + x42 = 1.1x31+ 1.25x22 x51 = 1.1x41+ 1.25x32 xi2 30 ( i =1、2、3、4 ) x33 80 x24 100 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4）,线性规划解法（图解法）,变量：x表示A的台数，y表示B的台数 目标函数：利润最大 max f(x,y)=x6y7 约束条件：2x+3y=0,图作业法,0 5 10 x,Y 10 5 0,2x+y=16,2x+3y=24,A(0,0) 0,B(8,0) 48,C(6,4) 64,D(0,8) 56,E,表达式,Min S(x,y)=1.5x+0.7y S.T. 5x+2y=60 3x+2y=40 5x+y=35 x=0 y=0,线性规划的图解法,P97 例4： Max S(x,y)=7x+12y 9x+4y=360 4x+5y=200 3x+10y=300,F (0,90),G( 0,40),A (0,30),D( 40,0),H (50,0),E (100,0),B,C,O(0,0),9x+4y=360,4x+5y=200,3x+10y=300,A(0,30) B(20,24) C(1000/29,360/29) D(40,0) O(0,0),最优解在直线围成的多边形的顶点取得。,作出各约束条件表示的直线,直线的画法,用两点式：9x+4y=360，x=0,y=90 y=0,x=40 4x+5y=200，x=0,y=40 y=0,x=50 3x+10y=300，x=0,y=30 y=0,x=100 所以在分别在两点之间连线就画成了。,交点的求法,A，D，O容易求出，对于B、C,4x+5y=200,3x+10y=300,9x+4y=360,4x+5y=200,x=(200-5y)/4代入3x+10y=300，(600-15y)/4+10y=300， 600-15y+40y=1200，y=24，代入3x+10y=300，有3x=60， x=20，所以B为（20，24）,x=(200-5y)/4代入9x+4y=360，(1800-45y)/4+4y=360， 7200-180y+16y=1440，y=(7200-1440)/(180-16)=1000/29，代入4x+5y=200，有x=360/29，所以C为(1000/29,360/29),另一个例子： Min S(x,y)=200x+160y 6x+2y=12 2x+2y=8 4x+12y=24 0=x=7，0=y=7,2 4 6 7,7 6 4 2,6x+2y=12,2x+2y=8,4x+12y=24,y=7,x=7,E(0,7) D(0,6) (0,4) (0,2) (0,0),(2,0) (4,0) A(6,0)G(7,0),F(7,7),C(1,3),B(3,1),圆圈表示可行域的边界,最优解在圆圈所在的点取得,把这些点分别代入目标函数，求得S值分别为： A1200，B760，C680，D960，E1120，F2520，G1400，所以C为最优点。,例:求以下最优解,Max Z(x,y)=2x+3y S.T. x+y=4 x=0 y=0,线性规划求解结论,若线性规划有可行解，则可行域是个凸多边形，或是凸集（集中任两点线段仍在集中） 若线性规划有最优解，则最优解可能是唯一，也可能是无穷。如唯一一定在凸多边形的某顶点上；如是无穷则一定充满凸多边形的一条边界上 如有可行解，但没有有限最优解，这时凸多边形是无界的，反之不一定成立（如上例） 没有可行解，即可行解集是空集,用Excel进行线性规划,例：学校准备为学生添加营养餐，每个学生每月至少要补充60单位碳水倾到物，40单位蛋白质和35单位脂肪。已知A、B两种营养品的含量价格如下表， 问A、B分别 要多少单位既满足学生需要又价格最省？,第一步：描述问题并建立问题模型 Min S(x,y)=1.5x+0.7y S.T. 5x+2y=60 3x+2y=40 5x+y=35 X,y=0,第二步 利用规划求解工具（注意如没有，需要另外加载）,目标单元格是必须可计算公式 注意是求解最大还是最小值 可变单元格是最优解 约束条件根据需要添加,操作实验 ：,对课堂上的线性规划例子用Excel求解,实例1,某企业生产混合饲料，规定：蛋白质至少有15%，脂肪至少4.5%，淀粉至少30%，纤维素不得超过10%。所提供的原材料有： 花生饼，每吨单价500元，含25%蛋白质、2%脂肪、10%淀粉、2%纤维素 花生秧，每吨50元，含 8%蛋白质、1%脂肪、5%淀粉、40%纤维素 骨粉，每吨350元，20%蛋白质、8%脂肪、1%淀粉、0.5%纤维素 玉米，每吨450元，7%蛋白质、5%脂肪、40%淀粉、6%纤维素 满足营养成分前提下，配合费用最低,建模,决策变量：四种原料，各自需要为X1、X2、X3、X4 目标函数：max=500X1+50X2+350X3+450X4 约束条件：25%x1+8%x2+20%x3+7%x415% 2%x1+1%x2+8%x3+5%x44.5% 10%x1+5%x2+1%x3+40%x430% 2%x1+40%x2+0.5%x3+6%x410% X1,X2,X3,X4 0 X1+X2+X3+X4=1(归一条件),发现问题,总量没有为1而是1.17 所以要增加约束条件，决策总量单元格G6=1 计算后发现无解,需要重新调整原料和降低营养成份,对偶问题与影子价格,在经济活动中可以追求最大利润，也可以追求最低成本，这是一个问题两种不同表现形式。反映在数学上，就是互为对偶的线性规划问题表达，而且这两个问题可以同时实现。 对偶问题变换规则,例题分析1：生产计划问题对偶问题,例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：,问：工厂应分别生产多少单位、产品才能使工厂获利最多？,对偶问题,设备x1,原料Ax2，原料Bx3 目标函数minZ=300*x1+400*x2+250*x3 S.T X1+2*x2=50 X1+x2+x3=100 X1、X2、X3=0,习题：食品营养例中的对偶问题,Min S(x,y)=1.5x+0.7y S.T. 5x+2y=60 3x+2y=40 5x+y=35 X,y=0,对偶,Max S(Z1,Z2,Z)=60*Z1+40*z2+35*z3 S.T. 5*z1+3*z2+5*z3=0,敏感性分析,注意线性模型与假定非负勾选上,敏感性分析作用,低于阴影价格购买或应用该约束条件是好的决策 可以分析哪个约束条件比较敏感，对此部分条件因素要变化时要慎重决策,第二节 运输问题和指派问题（特殊的线性规划问题）,一、运输问题 二、指派问题,案例：产销平衡问题,例1 某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,案例：产销平衡问题,解：产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：,Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）,Excel求解过程,1.建立决策变量区域 2.用函数 sumproduct建立决策目标公式 3.决策区域中，分别对供销，用sum函数进行合计计算 4.点击目标公式区域，用线性规划 选择目标和变量区域 约束条件设置很重要（变量区域0，sum函数统计的区域要与常数区域数值相等） 求解完成 注意：如某产销条件不平衡时，只需要在条件上根据情况修改,第二节 运输问题和指派问题,一、运输问题及其模型 A1、 A2、 Am 表示某物资的m个产地； B1、B2、Bn 表示某物质的n个销地；si 表示产地Ai的产量； dj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价 设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型： （一）产销平衡问题 m n Min f = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m xij = dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n),第二节 运输问题和指派问题,（二）产大于销问题 m n Min f = cij xij i = 1 j = 1 n s.t. xij si i = 1,2,m j = 1 m xij = dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n),第二节 运输问题和指派问题,（三）销大于产问题 m n Min f = cij xij i = 1 j = 1 n s.t. xij = si i = 1,2,m j = 1 m xij dj j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n),注：产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时），把它化为产销平衡问题。,例题分析2：产大于销问题,（四）运输问题的计算机求解 例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,例题分析2：产大于销问题,解：增加一个虚设的销地运输费用为0,例题分析3：销大于产问题,例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,例题分析3：销大于产问题,解：增加一个虚设的产地运输费用为0,习题,第二节 运输问题和指派问题,二、指派问题（特殊的运输问题） （一）任务数=人数（产销平衡的运输问题） 任务数与人数相等的指派问题实质上就是产销平衡的运输问题，且每行、每列的产量或销量都等于1。 m n Min f = cij xij i = 1 j = 1 n s.t. xij = 1 i = 1,2,m j = 1 m xij = 1 j = 1,2,n i = 1 xij 0 (i = 1,2,m ; j = 1,2,n),例题分析4：指派问题,例13 有一份说明书，要分别译成英、日、德、俄四种文字，因各人专长不同，他们完成翻译不同文字所需的时间见下表：,解法：匈牙利法,匈牙利法是求解及小型（优化方向为极小）指派问题的一种方法，这种方法最初由w.w.kuhn提出，后经改进而形成，解法基于匈牙利数学家D.Knig给出的一个定理而得名。 理论基础: （1）若从效率矩阵(cij)的行（或列）的各元素中分别减去该行（或列）的最小元素后得到一个新矩阵（bij）,则以（bij）为效率矩阵的指派问题与原问题有相同的最优解。经过上述变换后，（bij）中的每行和每列都至少含有一个0元素，称位于不同行不同列的0元素为独立的0元素。 （2）若（bij）有n个独立的0元素，由此可得一个解矩阵，方法为在X中令对应于（bij）的0元素位置的元素为1，其它位置的元素为0，则X为指派问题的最优解。 （3）D.Knig定理：矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。,匈牙利法步骤,第一步 变换效率矩阵（Cij），使变换后效率矩阵（bij）的每行每列至少出现一个0元素，同时不出现负元素。（对效率矩阵每行每列减去该行该列最小元素）,Cij,-2 -4 -11 -4,-5,第二步 画出包含所有0的直线，并使画出直线条数最少。如果直线条数与表中的行或列相等，则获最优解。否则第三步（注意不能画斜线）（例中3条直线4，要第三步）,第三步 在没有被直线覆盖的元素中找出最小元素，并对没画直线的行上各元素减去最小元素，对画直线列的各元素都加上这个最小元素，变换成新效率矩阵,-2,-2,+2,第四步 对上一步结果重新画直线，如果直线条数等于矩阵行或列数，完成求解。否则重复上一步 第五步 先找某行某列中唯一的0，没有从任意0开始，把这一列的工作分配给这一行的人，从表中去这行这列。然后从剩下表中重复分配。例中乙日文，甲俄文，丙英文，丁德文，总时间9+4+11+4=28小时,例题分析4：指派问题,解：该指派问题实质上就是产销平衡的运输问题，且每行、每列的产量或销量都等于1，把它化为产销平衡的运输问题如下表所示：,Excel求解,过程与运输问题一样，目标函数sumproduct 约束条件通过sum求和，产销相等，变量0，特别注意要在选项中，将“线性模型”和“假定非负钩”选上,第二节 运输问题和指派问题,（二）任务数人数（产销不平衡的运输问题） 1、若任务数人数，就增加假想人，就可以化为产销平衡问题。 2、若任务数 人数，就增加假想工作，就可以化为产销平衡问题。,习题,第三节 动态规划,一、动态规划的基本概念和方法 二、动态规划模型的建立与求解步骤 三、动态规划的应用,案例：最短路问题,例16 位于城市A的某公司要把一批货物送到位于城市E的销售门市部，途中可能经过的城市有B1,B2,B3;C1,C2,C3;D1,D2等8个城市，问如何走，能使路线最短？,第三节 动态规划,一、基本概念和方法： （一）基本概念 1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。 2、状态sk：在各阶段开始时的客观条件称为各阶段的状态。状态可以是数量，也可以是字符。 3、决策uk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为uk(sk)。 决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。 4、状态转移方程 sk+1=Tk(sk, uk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。 5、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。,第三节 动态规划,6、阶段指标函数dk(sk, uk)：从状态sk出发，选择决策uk所产生的第k阶段指标。 过程指标函数Vk,n(sk, uk, uk+1, un)：从状态sk出发，选择决策uk,uk+1, , un所产生的过程指标。动态规划要求过程指标具有可分离性，即 Vk,n(sk, uk, uk+1, , un) = vk(sk, uk)+Vk+1(sk+1, uk+1, , un)称指标具有可加性，或 Vk,n(sk, uk, uk+1, , un) = vk(sk, uk)Vk+1(sk+1,uk+1, , un)称指标具有可乘性。 最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即,第三节 动态规划,（二）基本方法 1、最优化原理 不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。 2、基本方法 从最后一个阶段的优化开始，按逆向顺序逐步向前一阶段扩展，并将后一阶段的优化结果带到扩展后的阶段中去，以此逐步向前推进，直到得到全过程的优化结果。 3、递推方程,第三节 动态规划,二、动态规划模型的建立与求解步骤 （一）建立动态规划模型的基本要求 1.所研究的问题必须能够分成几个相互联系的阶段，而且在每一个都具有需要决策的问题. 2.在每一阶段都必须有若干个与该阶段相关的状态。 （二）动态规划的求解步骤 1.列出本阶段的所有可能状态变量sk。 2.对每一状态sk列出所有可能的决策变量uk(sk)。,第三节 动态规划,3.对每一阶段sk,uk(sk)计算本阶段的指标值dk(sk,uk)。 4.确定状态转移方程sk+1=T(sk,uk)，对于每对sk,uk求出sk+1的值。 5.对于每一对sk,uk，计算相应的指标值dk(sk,uk)+fk+1(sk+1)。 6.比较各个指标值，取最优者（最大值或最小值）作为本阶段sk状态开始的后部子过程的最优指标值fk(sk),相应的决策uk即是本阶段以sk为起始状态的最优决策u*k。 7.在第一阶段的最优策略确定后，再从第一阶段开始，根据状态转移方程确定各阶段的最优策略u*k。,例题分析1：定价问题,例17 考虑为某新产品定价，该产品的单价从5元、6元、7元、8元这四种价格中选取其中之一来定价，每年年初允许价格变动，但幅度不能超过1元。该公司预计该产品畅销只有5年，5年后将被淘汰，另据销售情况预测，在价格不同的情况下年度的预计利润入下表所示，问如何定价，能使利润最大？,例题分析1：定价问题,解：（1）该问题按年度分为5个阶段进行，即k=5。 （2）状态变量sk:第k年初的价