第二讲最优化模型.ppt

《第二讲最优化模型.ppt》由会员分享，可在线阅读，更多相关《第二讲最优化模型.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 爱因斯坦的一句名言爱因斯坦的一句名言：想象力比知识更重要！因为知识是有限的，而想象力包括世界的一切，是知识的源泉。要 点华北电力大学数理学院华北电力大学数理学院School of mathematics&physics School of mathematics&physics最优优化模型最优优化模型最优化模型概述最大值或最小值数学规划：线性规划（整数规划、0-1规划、目 标规划等），非线性规划动态规划华北电力大学数理学院华北电力大学数理学院School of mathematics&physics一、简单优化问题案例案例1：产销平衡下的某种产品的最优价格,即使工厂利润最大的价格。（1）售量

2、为x，并与产量相等；（2）每件产品售价为p。在竞争市场的环境中售量x依赖于 价格p,即（3）每件产品成本为q，产量x与成本q无关。，f 称为需求函数；1、模型假设、模型假设华北电力大学数理学院华北电力大学数理学院School of mathematics&physics一、简单优化问题2、模型建立、模型建立总收入：I(p)=px总支出：C(p)=qx利 润：U=I(p)-C(p)=(p-q)x=(p-q)f(p)数学模型为：华北电力大学数理学院华北电力大学数理学院School of mathematics&physics3、模型求解及其结果分析、模型求解及其结果分析 需求函数是售价的减函数，通

3、常是根据实际销售情况定出。现在，假设它是线性函数，即一、简单优化问题其中，a-代表这种产品免费供应（p=0）时的社会需求量，也称为绝对需求量；表示价格上涨一个单位时销售量下降的幅度。它反映市场需求对价格的敏感程度。华北电力大学数理学院华北电力大学数理学院School of mathematics&physics一、简单优化问题 利润U(p)达到最大值的最优价格 满足：得到：最优价格最优价格一部分是成本的一半，另一部分与“绝对需求”成正比，与市场需求对价格的敏感系数成反比。华北电力大学数理学院华北电力大学数理学院School of mathematics&physics边界收入：边界支出：当边界

4、支出等于边界收入时利润最大-经济学著名定理！最大利润：一、简单优化问题华北电力大学数理学院华北电力大学数理学院School of mathematics&physics二、数学规划模型案例案例2：奶制品的生产计划奶制品的生产计划 A1 A2资源原料奶(桶)劳动时间（h）设备甲能力（kg）设备乙能力(kg)1 1 12 8 3 0 0 4 50480100inf一奶制品加工厂用牛奶生产A1,A2两种奶制品，参数见表：根据市场需求，生产的A1,A2产品全部能售出，且每千克A1产品获利24元，每千克A2产品获利16元。试为该厂订一个生产计划，使每天获利最大。并进一步讨论以下问题：一、问题的提出一、问

5、题的提出华北电力大学数理学院华北电力大学数理学院School of mathematics&physics（1）若用35元可以买到1桶牛奶，是否应作这项投资？若投资，每天最多购买多少桶牛奶？（2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？（3）由于市场需求变化，每千克A1产品的获利增加到30元，是否应改变生产计划？二、模型分析生产计划就是每天生产多少A1和多少A2，获利润最大。或者是每天用多少桶牛奶生产A1和用多少桶牛奶生产A2，获利润最大。当技术参数、价值系数为常数时，此为线性规划模型。二、数学规划模型华北电力大学数理学院华北电力大学数理学院School of m

6、athematics&physics三、模型的假设1、每天用 桶牛奶生产A1，桶牛奶生产A2；可以是任意的实数。2、劳动时间、设备能力、利润均为与产量无关常数。即技术参数、价值系数为常数二、数学规划模型3、生产的产品全能售出。华北电力大学数理学院华北电力大学数理学院School of mathematics&physics约束条件：原料限制劳动时间限制设备能力限制决策变量的非负性四、模型的建立目标：设每天收入z元。则二、数学规划模型华北电力大学数理学院华北电力大学数理学院School of mathematics&physics二、数学规划模型综上可得：华北电力大学数理学院华北电力大学数理学院

7、School of mathematics&physics五、模型求解及结果分析f=-72;-64;A=1 1;12 8;3 0;b=50;480;100;x,z=linprog(f,A,b,0;0,)x=20.0000,30.0000;z=-3.3600e+003X,z=LINPROG(f,A,b,Aeq,beq,LB,UB)用于解：min f*x subject to:A*x=b Aeq*x=beq.LB=X=UB.二、数学规划模型即按每天用20桶牛奶生产A1，用30桶牛奶生产A2，获最大收益：z=3360元。华北电力大学数理学院华北电力大学数理学院School of mathematic

8、s&physics 附加问题（1）和（2）是要不要扩大生产？这取决于对第i种资源的估价影子价格（）。在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。附加问题的讨论：附加问题（3）是考虑当费用系数c变化时对最优解和最优值有没有影响?找出使最优解不变的区间。二、数学规划模型华北电力大学数理学院华北电力大学数理学院School of mathematics&physics影子价格y，它由模型（1）的对偶问题决定：其中，分别为出租（出售）单位资源 的附加值.二、数学规划模型y,s=linpr

9、og(b,-A,-c,0;0;0,)y=48.0000 2.0000 0.0000;s=3.3600e+003华北电力大学数理学院华北电力大学数理学院School of mathematics&physics二、数学规划模型 解附加问题（解附加问题（1 1）:由于每桶牛奶的市场价35元低于影子价格 ，所以企业应买进牛奶用于扩大生产。设再增加x桶，其他条件不变，则有相应生产计划：x=0.0000,60.0000,10.0000;z=-3.4900e+003收入：3840。即最多每天再多买进10桶！华北电力大学数理学院华北电力大学数理学院School of mathematics&physics解

10、附加问题（解附加问题（2）：）：在每位临时工人的工资不超过每小时2元的条件下，可以聘用临时工人以增加劳动时间。设小时工资为s（0=s=2）元，其他条件不变的条件下，再增加x小时，则有相应生产计划：华北电力大学数理学院华北电力大学数理学院School of mathematics&physics f=-72-64 2;a=1 1 0;12 8-1;3 0 0;b=50,480,100;x,z=linprog(f,a,b,0;0;0,)；x=21.1790，28.8210，4.7160z=-3.3600e+003。收入:s=2时，3369.53f=-72-64 0;a=1 1 0;12 8-1;3

11、 0 0;b=50,480,100;x,z=linprog(f,a,b,0;0;0,)x=33.3333，16.6667，104.3896z=-3.4667e+003。收入：s=0时，3466.70s2时，f=-72-64 s;a=1 1 0;12 8-1;3 0 0;b=50,480,100;x,z=linprog(f,a,b,0;0;0,)x=33.3333，16.6667，53.3333z=-3.4133e+003。收入：3466.7华北电力大学数理学院华北电力大学数理学院School of mathematics&physics解附加问题（解附加问题（3）：求使最优解不变的）：求使最优

12、解不变的c的变化范围。由f=0时的最终表:华北电力大学数理学院华北电力大学数理学院School of mathematics&physics建立此问题的初始单纯性表:显然，当-48+2f=0,-2-(1/4)f=0时，最优解不变！即时，最优解不变！现在 ，所以不用改变生产计划！华北电力大学数理学院华北电力大学数理学院School of mathematics&physics案例案例3：奶制品的生产销售计划奶制品的生产销售计划一、问题的提出一、问题的提出 案例2的A1,A2的生产条件、利润、资源都不变条件下，提高奶制品深加工技术，增加工厂获利。用2小时和3元加工费，可将1千克A1加工成0.8千克

13、高级奶制品B1，也可将1千克A2加工成0.75千克高级奶制品B2，每千克B1可获利44元，每千克B2可获利32元。生产的产品全能售出，试着为该厂订制一个生产销售计划，使每天获利最大。并进一步讨论以下问题：（1 1）若投资30元可增加供应1桶牛奶，投资3元可增加1小时劳动时间，是否应作这项投资？若每天投资150元，可赚回多少？（2 2）每千克高级奶制品B1,B2的获利经常有10%的波动，对制订的生产销售计划有无影响？若每千克B1的获利下降10%，计划是否应作调整？华北电力大学数理学院华北电力大学数理学院School of mathematics&physics二、模型分析对本案例来讲，决策变量取

14、为A1、A2、B1、B2每天的销售量讨论更方便！当技术参数、价值系数为常数时，此为线性规划模型。三、模型的假设2、劳动时间、设备能力、利润均为与产量无关常数。即技术参数、价值系数为常数3、生产的产品全能售出。1、每天销售产品A1、A2、B1、B2分别为 公斤，且用 公斤A1加工B1，用 公斤A2加工B2。华北电力大学数理学院华北电力大学数理学院School of mathematics&physics四、模型的建立目标：设每天净利润z元。则约束条件：原料限制劳动时间限制设备能力限制决策变量之间的关系决策变量的非负性华北电力大学数理学院华北电力大学数理学院School of mathematic

15、s&physics综上可得：华北电力大学数理学院华北电力大学数理学院School of mathematics&physics五、模型求解及结果分析利用LINDO6.1max 24x1+16x2+44x3+32x4-3x5-3x6st2)4x1+3x2+4x5+3x6=6003)4x1+2x2+6x5+4x6=4804)x1+x5=1005)x3-0.8x5=06)x4-0.75x6=0end得到如下结果：华北电力大学数理学院华北电力大学数理学院School of mathematics&physicsLP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION

16、VALUE(最优值)1)3460.800 VARIABLE VALUE（最优解）REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUAL PRICES（影子价格）2)0.000000 3.160000 3)0.000000 3.260000 4)76.000000 0.000000 5)0.000000 44.0000

17、00 6)0.000000 32.000000华北电力大学数理学院华北电力大学数理学院School of mathematics&physicsNO.ITERATIONS=2 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES（使最优解不变的费用系数的取值范围）VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.00000

18、0 19.750002 3.166668 X4 32.000000 2.026667 INFINITY X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY RIGHTHAND SIDE RANGES（资源系数的取值范围）ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 600.000000 120.000000 280.000000 3 480.000000 253.333328 80.000000 4 100.000000 INFINITY 76.00000

19、0 5 0.000000 INFINITY 19.200001 6 0.000000 INFINITY 0.000000华北电力大学数理学院华北电力大学数理学院School of mathematics&physics现在的生产与销售计划现在的生产与销售计划：生产24公斤A1并全部用于深加工B1，生产168公斤A2并全部用于销售，获利最大为3460.8元。附加问题（1）：因为增加一桶牛奶可使净利润增长3.16*12=37.92元，增加一小时劳动力使净利润增长3.26元；所以应该投资30元增加供应1桶牛奶或投资3元增加1小时劳动时间。投资150元（5桶奶）可赚回37.92*5=189.6元。附加

20、问题（2）：最优解不变的x3、x4的费用系数变化范围分别是：(44-3.17,44+19.75),(32-inf,32+2.03).因此，B1、B2的获利10%的波动对销售计划有影响！华北电力大学数理学院华北电力大学数理学院School of mathematics&physics若每千克B1的获利下降10%，计划应作调整：华北电力大学数理学院华北电力大学数理学院School of mathematics&physicsmax 24x1+16x2+39.6x3+32x4-3x5-3x6st2)4x1+3x2+0 x3+0 x4+4x5+3x6=6003)4x1+2x2+0 x3+0 x4+6x

21、5+4x6=4804)x1+0 x2+0 x3+0 x4+x5+0 x6=1005)0 x1+0 x2+x3+0 x4-0.8x5+0 x6=06)0 x1+0 x2+0 x3+x4+0 x5-0.75x6=0end执行：得到：华北电力大学数理学院华北电力大学数理学院School of mathematics&physics LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1)3400.000 VARIABLE VALUE REDUCED COST X1 0.000000 0.666667 X2 160.000000 0.000000 X

22、3 0.000000 0.000000 X4 30.000000 0.000000 X5 0.000000 0.986666 X6 40.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 3.666667 3)0.000000 2.500000 4)100.000000 0.000000 5)0.000000 39.599998 6)0.000000 32.000000 华北电力大学数理学院华北电力大学数理学院School of mathematics&physics案例4：露天矿生产的车辆安排（2003B）许多现代化铁矿是

23、露天开采的，它的生产主要是由电动铲车（电铲电铲）装车、电动轮自卸卡车（卡车卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。露天矿里有若干个爆破生成的石料堆(铲位铲位)和和卸货地点（以下简称卸点）。每个铲位已预先根据铁含量分成矿石和岩石(低于25%)，且矿石、岩石数量以及矿石的平均铁含量（称为品位）都是已知的；卸点有卸矿石的矿石漏、铁路倒装场（简称倒装场），有卸岩石的岩石漏、岩场，每个卸点都有各自的产量要求。一、问题的提出华北电力大学数理学院华北电力大学数理学院School of mathematics&physics 现某露天矿有铲位某露天矿有铲位10个，卸点个，卸点

24、5个，现有电铲个，现有电铲7台，卡车台，卡车20辆辆。各卸各卸点点一个班次一个班次的产量要求：矿石漏的产量要求：矿石漏1.2万吨、倒装场万吨、倒装场1.3万吨、倒装场万吨、倒装场1.3万吨、岩石漏万吨、岩石漏1.9万吨、岩场万吨、岩场1.3万吨。万吨。铲位和卸点位置的二维示意图如下:华北电力大学数理学院华北电力大学数理学院School of mathematics&physics铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏5.265.194.214.002.952.742.461.900.641.27倒装场1.900.991.901.131.272.251.482.04

25、3.093.51岩场5.895.615.614.563.513.652.462.461.060.57岩石漏0.641.761.271.832.742.604.213.725.056.10倒装场4.423.863.723.162.252.810.781.621.270.50各铲位矿石、岩石数量(万吨)和矿石的平均铁含量如下表：铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石量095105100105110125105130135125岩石量125110135105115135105115135125铁含量30%28%29%32%31%33%32%31%33%31%各铲位和各卸点

26、之间的距离（公里）如下表：华北电力大学数理学院华北电力大学数理学院School of mathematics&physics 一个班次的生产计划一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上?出动几辆卡车，分别在哪些路线上各运输多少次?注意：因为随机因素影响，装车、卸车时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可。一个合格的生产一个合格的生产计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划一个好的计划还应该考虑下面两条原则之一：（1）总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；（2）利用现有车辆运输，获得最大

27、的产量（岩石产量优先，在产量相同的情况下，取总运量最小的解）。请你就两条原则两条原则分别建立数学模型，并给出具体的生产计划、相应的总运量及岩石和矿石产量。华北电力大学数理学院华北电力大学数理学院School of mathematics&physics补充条件：补充条件：1、一般来说，平均铁含量大于等于25%的为矿石，否则为岩石；2、每个铲位至多能安置一台电铲，电铲的平均装车时间为平均装车时间为5 5分钟分钟；3、应该尽量把矿石按矿石卸点需要的铁含量（品位品位）搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。假设每个矿石卸点矿石卸点品位要求都为29.5%1%；卡车的平均卸车时

28、间为3分钟；4、所用卡车载重量为154吨，平均时速28，卡车每次都是满载运输；5、电铲和卸点都不能同时为两辆及两辆以上卡车服务；6、每个铲位到每个卸点的道路都是专用的宽60m的双向车道，不会出现堵车现象，每段道路的里程都是已知的；7、卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况；8、发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次；9、卡车的耗油量很大，每个班次每台车消耗近1吨柴油。华北电力大学数理学院华北电力大学数理学院School of mathematics&physics二、模型分析 属于运输问题，但与典型的运输问题（某种物资由某

29、种物资由m m个产地运往个产地运往n n个销个销地，在满足各产地的供应和各销地的需求的条件下，使总运量（吨公里）最地，在满足各产地的供应和各销地的需求的条件下，使总运量（吨公里）最小，制订运输计划小，制订运输计划）相比，还有以下特点：1、车辆满载运输（154吨/车次）；2、运输矿石与岩石两种物资，矿石卸点有品位约束，各铲位的矿石需搭配运输；3、电铲和卸点都不能同时为两辆及两辆以上卡车服务，即各个铲位、卸点还有一个班次内运输车次的限制；4、每条路线上有一个班次内运输车次的限制；5、铲位数10大于电铲数7，要从10个中选择不大于7个铲位；6、用最少的车辆（不超过20）给出各条路线上的车辆安排（几辆

30、车，跑几次）。如何处理以上不同之处？华北电力大学数理学院华北电力大学数理学院School of mathematics&physics三三 模型的假设模型的假设华北电力大学数理学院华北电力大学数理学院School of mathematics&physics四四 模型的建立模型的建立1、基本模型 现将m（=10）个铲位（产地）上的石料运往n（=5）个卸点（销地），在满足各产地的供应和各销地的需求的条件下，使总运量（吨公里）最小，制订运输计划。设 cij 产地（铲位）i到销地（卸点）j的距离（公里），xij 产地i到销地j的车次（154 xij吨），ai 产地i的供应量（吨），bj 销地j的需求

31、量（吨），这里：i=1,2,10,j=1,2,5；j=1,2,5为矿石卸点，j=3,4为岩石卸点。华北电力大学数理学院华北电力大学数理学院School of mathematics&physics模型：是一个整数线性规划问题，有成熟的算法和方便的软件求解！华北电力大学数理学院华北电力大学数理学院School of mathematics&physics2、其他约束条件（1）记铲位i的矿石铁含量为pi，矿石的品位约束：（2）车次的约束：各个铲位至多一台电铲，5分钟装一车。所以一个铲位一个班次（8小时）内的最大运输车次为860/5=96，即 华北电力大学数理学院华北电力大学数理学院School o

32、f mathematics&physics 3分钟卸一车，一个卸点一个班次中的最大运输车次为860/3=160，即（3）各铲位、卸点一个班次内运输车次的限制：记平均车速v=28(公里/时)=0.47(公里/分)。从铲位i到卸点j车辆运行一个周期的平均时间为tij=2cij/v+5+3（分），这条路线上在卡车不等待条件下最多能运行的卡车数为rij=tij/5,每辆卡车一个班次中在这条路线上最多可以运行的次数sij=860/tij（这里假定若有两辆车在同一路线上，则上一班晚装车的那辆也晚下班）。于是各铲位、卸点一个班次内运输车次的限制为华北电力大学数理学院华北电力大学数理学院School of mathematics&physics （4）铲位数10大于电铲数7，要从10个中选择不大于7个铲位。如何处理？a）用枚举法从 个整数规划中取最优的一个；b）先不考虑电铲数量7的约束，运行整数线性规划，再逐步去掉解中运量最少的几个铲位，直到不超过7个铲位；c）增加10个0-1变量来标志电铲放在哪个铲位，问题为50个整数变量和10个0-1变量的线性规划。华北电力大学数理学院华北电力大学数理学院School of mathematics&physics(5)不超过20辆车的约束 华北电力大学数理学院华北电力大学数理学院School of mathematics&physics