欧几里德在不加证明而直接采用基本概念和公理的基础上.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