欧几里德在不加证明而直接采用基本概念和公理的基础上.ppt
简单优化模型,欧几里德在不加证明而直接采用基本概念和公理的基础上,运用逻辑推理方法得出了一系列定理、推论,从而建立了完整的欧几理德几何学,这一辉煌的成果至今仍然是人类宝贵财富.,逻辑推理建模方法是一种重要的建模方法,一.合作对策模型,从事某一项活动若能多方合作,往往可以获得更大的总收益(或受到更小的损失).合作中应该如何分配收益(或分摊损失),?,合作对策模型基本思想：采用公理化方法，从问题应当具有的基本属性出发，运用逻辑推理方法导出满足这些基本属性的解.,例1(p13)有三个位于一条河流同一侧的城镇，三城镇的污水必须经过处理才能排入河中.三方商议共建一座污水处理厂.,城1,城2,城3,20公里,38公里,污水厂筹建处,问题：(1)三个城镇怎样 建厂可使总开支最少？(2)每一个城镇的费用各分摊多少？,分析：有五种方案可供选择,(1)三城各建一个处理厂；,(2)城1与城2合建一个厂,城3单独建一个；,(3)城2与城3合建一个厂,城1单独建一个；,(4)城1与城3合建一个厂,城2单独建一个；,(5)三城合作建一个处理厂；,条件：,建设污水处理厂的费用有公式：,管道费用：,Q污水排放量；L管道长度(公里).,三个城镇的污水排放量分别为,Q1=5米3/秒，Q2=3米3/秒，Q3=5米3/秒.,对各个方案进行费用测算，得,解：污水处理费用与投资 一镇单建：PA=73050.712=2300，PB=1600，PC=2300 二镇合建：PAB=73080.712+6.650.5120=3500 PAC=4630，PBC=3650 三镇合建：PABC=5560 投资：I.单独建厂：PI=PA+PB+PC=6200 II A、B合建：PII=PAB+PC=5800 III B、C合建：PIV=PBC+PA=5950 IV A、C合建：PIII=PAC+PB=6230 V 三镇合建：PV=PABC=5560 三镇合建总投资最少，较单独建厂节省640(万元),方案(5):三个城市合作建厂总投资最少.,问题：三个城市如何分摊费用？,经商讨定下几条原则：,1.建厂费用按3个城市的污水量之比5:3:5 分摊；,2.城2到城3的管道费按5:3由城1和城2分摊；,3.城1到城2的费用由城1自行解决.,思考：他们的原则是否有道理？,城1市长的“可行性论证”:,1.建厂总费用为 730(5+3+5)0.712=4530(万元),城1负担费用为 45305/131742(万元);,2.城1至城2的管道费用为 6.650.5120300(万元)；,3.城2至城3的管道费用为 6.6(5+3)0.5138724(万元)城1负担 7245/8=425.5(万元);,城1总共负担：1742+300+425.5=2467(元).,市长的结论：不能接受这样的合作.,n人合作对策模型,设I=1,2,n,“i”代表第i个可能参加的合作者.,费用分担建厂费 PABC=5560，分摊 CPA=55605/13=1740,CPB=1050,CPC=1740.管道费GFAB=6.650.5120=300,GFBC=730.分摊 CGA=300+7305/8=760,CGB=7303/8=270总合分担 CA=CPA+CGA=1740+760=2500 CB=CPB+CGB=1050+270=1320 CC=CPC=1740,-2300=200,-1600=-280,-2300=-560,分摊方案中 A 镇吃亏,C镇占便宜,方案不公平!,定义1 I 每一个子集S,对应一个确定的实数V(S),V(S)满足：,(1)V(S)0,对所有的I 的子集S；(2)V()=0；(3)V(S1S2)V(S1)+V(S2),对一切满足S1S2=的S1、S2成立.称V(S)为 I 上的特征函数.,本例中特征函数V(S)的实际意义是若S中的人参加一种合作,这一合作的总获利数.,例 将三个城市记为I=1,2,3,则1、1,2、1,3、1,2,3都是I的子集,分别对应有城市1参加的各种合作方式.用V(S)表示以单干为基准的合作获利值,有,V(1)=0；V(1,2)=(2300+1600)(58002300)=400(万元)；V(1,3)=0(因为(23002300)(62301600)=30(万元)；V(1,2,3)=(2300+1600+2300)5560=640(万元).,三城市合作能产生效益640万元,如何分配？,定义2 定义合作V(S)(SI)的分配为(V)=(1(v),2(v),n(v)其中i(v)表示第i个人在这种合作下分配到的获利,称(V)为合作对策.,不同的合作应有不同的分配,问题归结为寻求一个合理的分配原则.,Shapley 公理,公理1.合作获利者对每个人的分配与此人的标号无关；,公理2 每人分配数的总和等于总获利数：,公理3 若对所有包含i 的子集S,有V(Si)=V(S),则i(v)=0；,公理4 若n个人同时进行两项互不影响的合作,则两项合作的分配也应互不影响.,Shapley定理 满足公理14 的(V)存在并且唯一，由下式给出：,Ti 是I 中包含i 的一切子集构成的集族,表示集合S中的元素个数.,注 在(1)式中 V(S)V(Si)可视为第i人在合作S中所 做的贡献；,可看成第i人的贡献在总贡献中所占的权重.,续例1 计算城市1应承担的费用,T1=1,1,2,1,3,1,2,3，,根据公式(1),从而城市1应承担投资额为 2300197=2103(万元).,=67+130=197(万元)，,2 存贮模型,问 题,配件厂为装配线生产若干种产品，轮换产品时因更换设备要付生产准备费，产量大于需求时要付贮存费。该厂生产能力非常大，即所需数量可在很短时间内产出。,已知某产品日需求量100件，生产准备费5000元，贮存费每日每件1元。试安排该产品的生产计划，即多少天生产一次(生产周期)，每次产量多少，使总费用最小。,要求,不只是回答问题，而且要建立生产周期、产量与需求量、准备费、贮存费之间的关系。,问题分析与思考,每天生产一次，每次100件，无贮存费，准备费5000元。,日需求100件，准备费5000元，贮存费每日每件1元。,10天生产一次，每次1000件，贮存费900+800+100=4500元，准备费5000元，总计9500元。,50天生产一次，每次5000件，贮存费4900+4800+100=122500元，准备费5000元，总计127500元。,平均每天费用950元,平均每天费用2550元,10天生产一次平均每天费用最小吗?,每天费用5000元,这是一个优化问题，关键在建立目标函数。,显然不能用一个周期的总费用作为目标函数,目标函数每天总费用的平均值,周期短，产量小,周期长，产量大,问题分析与思考,模 型 假 设,1.产品每天的需求量为常数 r；,2.每次生产准备费为 c1,每天每件产品贮存费为 c2；,3.T天生产一次(周期),每次生产Q件，当贮存量 为零时，Q件产品立即到来(生产时间不计)；,建 模 目 的,设 r,c1,c2 已知，求T,Q 使每天总费用的平均值最小。,4.为方便起见，时间和产量都作为连续量处理。,模 型 建 立,贮存量表示为时间的函数 q(t),t=0 生产Q件，q(0)=Q,q(t)以需求速率r递减，q(T)=0.,一周期总费用,每天总费用平均值(目标函数),离散问题连续化,一周期贮存费为,A=QT/2,模型求解,求 T 使,模型分析,模型应用,c1=5000,c2=1，r=100,回答问题,经济批量订货公式(EOQ公式),每天需求量 r，每次订货费 c1,每天每件贮存费 c2，,用于订货、供应、存贮情形,不允许缺货的存贮模型,问：为什么不考虑生产费用？在什么条件下才不考虑？,T天订货一次(周期),每次订货Q件，当贮存量降到零时，Q件立即到货。,允许缺货的存贮模型,A,B,当贮存量降到零时仍有需求r,出现缺货，造成损失,原模型假设：贮存量降到零时Q件立即生产出来(或立即到货),现假设：允许缺货,每天每件缺货损失费 c3,缺货需补足,一周期贮存费,一周期缺货费,周期T,t=T1贮存量降到零,一周期总费用,每天总费用平均值(目标函数),一周期总费用,求 T,Q 使,为与不允许缺货的存贮模型相比，T记作T,Q记作Q,不允许缺货模型,记,允许缺货模型,允许缺货模型,注意：缺货需补足,Q每周期初的存贮量,每周期的生产量R(或订货量),Q不允许缺货时的产量(或订货量),
