最新清华大学最优化PPT及其作业答案课件PPT.ppt 102页

'清华大学最优化PPT及其作业答案 1.问题与实例问题(problem):需要回答的一种提问，通常包含一些参数和取值未定的自由变量，可以从两个方面加以描述：（1）对所有参数的一般描述；（2）对回答（也称为解）所需要满足的特性的描述。实例(instance)：当对一个问题中的参数赋予特定的数值时，如何寻找相应的回答（解），这种提问称为该问题的一个实例。问题是对许多具体事例构成集合的一种抽象表述，而实例就是相应问题的一种具体表现形式。 例：线性规划问题与实例一个线性规划问题的实例是指矩阵和向量组(A,b,c)的某一特定取值，这些参数按照如下的结构关联在一起，描述了问题（解）所需要满足的特性。线性规划问题是对具有上述结构的所有实例的一种抽象描述。 多项式时间算法与指数时间算法把算法求解输入规模不超过k的实例时最多的运算次数称为该算法关于输入规模k的复杂性。定义: 多项式时间算法与指数时间算法多项式时间算法(polynomial-timealgorithm)或优良算法(goodalgorithm):对于某算法的复杂性函数，其增长速度是输入规模的多项式函数。指数时间算法(exponential-timealgorithm):对于某算法的复杂性函数，其增长速度是输入规模的指数函数。 多项式时间算法的优点：（1）随着问题输入规模的增加，算法的计算量（即算法复杂性）呈多项式增长；（2）一个多项式时间算法利用另一个多项式时间算法作为其“子程序”，构造一个新的复合型算法，则新算法仍是多项式时间算法。 单纯性算法的复杂性单纯性算法需要2n-1次迭代。 定理：当θ>2时，用单纯行算法求解上述问题时需要2n-1次迭代。 椭球法第一个可以在多項式时间內解决一般线性规划问题的解法。根据(P)与(D)的对偶关系,我们可将两者的最优解以一组最优性条件联结起来: 只要能有效的解决最优性条件的线性不等式,就能夠同时的解决一个线性规划问题(P)以及它的对偶问题(D)。椭球法正是一种专门解决线性不等式的方法。介绍如何以椭球法來解一组线性不等式Mu≤vMu≤v的解集合是一个凸集：假设S≠Ø,以原点u1为圆心,足夠大的半径做一圆E1,使得S∩E1≠Ø。 否则,因为S∩E1是一个凸集,所以经过圆心,可以切掉不含S∩E1的半个圆,而只剩下包含S∩E1的半个圆(以1/2E1表示)。对1/2E1而言,可以做出一个最小的椭圆E2,使得1/2E1⊆E2，椭圆的圆心记u2。S∩E1⊆E2,若Mu2≤v成立,则u2∈S∩E1必为其解。否则经过u2又可切去半个E2,而使S∩E1包含在另一半椭圆1/2E2之中。 在p维空间中,每次做出的椭球体积都会逐渐缩小。以V(Ek)及V(Ek+1)来表示前后两个椭球的体积,那么可以证明V(Ek+1)0。可行內点解集合：F0={x∈Rn|Ax=b,x>0}。假设F0非空。 內点法可粗略的分为三个步骤:步骤一:找一个可行內点x1∈F0。置k=1。步骤二:决定现有解xk是否为(P)的最优解。若是,则输出x∗=xk。否则就寻找一个好的移动方向,以及适当的步长>0。 PrimalAffineScaling内点法假想(P)的可行解集合位于第一象限的一个球,而现行解xk落在球心上,此球的半径是r>0。最优解为： 将(P1)变得稍微复杂一些,将球改为第一象限来考虑下列问题: 定义映射： 在上述转化之下,(P2)的近似问题在y空间中就可写成:应用(P1)的解答技巧,在y空间中的近似最优解为：在x空间中(P2)的近似最优解为： 在y空間中(P)变成下列的近似问题: 与(P’2)相比较,(P’)多了一些等式约束条件ADky=b。为了保持这些等式的继续成立,原来在(P’2)中的移动方向−Dkc便需要投影在(ADk)这个矩阵的零空间(nullspace)之中，即经过投影后的方向应是Pk(−Dkc)，其中Pk是一个投影矩阵，定义为：所以(P’)的近似最优解是(P)的近似最优解是 PrimalAffineScaling內点法的重要步骤: Dualaffinescaling内点法 迭代公式 Karmarkar投影尺度算法两个基本事实：（1）如果一个内点居于多面体的中心，那么目标函数的负梯度方向是比较好的可行方向；（2）在不改变问题基本特性的条件下，存在一个适当的变换，能够将可行域中给定的内点置于变换后的可行域的中心。 基本思想：（1）选定一个内点解作为迭代过程的初始点，利用可行域的投影尺度变换，将当前的内点解置于变换后的可行域的中心；（2）在变换后的可行域中沿着目标函数最速下降方向的正交投影移动，获得新的可行内点，并通过投影尺度逆变换将新的可行内点映射到原来的可行域，作为新的迭代点。（3）重复这一过程，直至求出满足一定精度的近优解。X空间Y空间投影尺度变换 Karmarkar标准形基本假设： 单纯形 向量的投影 单纯形S的投影尺度变换 变换T的性质 势函数性质：１．射影变换T把势函数变换成具有相同形式的函数．２．目标函数值所期望的下降量可通过势函数值的充分小来达到．３．优化函数f(x)可用优化线性函数来近似． 求解方法 Karmarkar投影尺度算法 有关定理 一般线性规划问题的处理1．利用对偶定理转化线性规划问题 (P)存在最优解的充要条件是 记于是问题归结为求解： 记 两个特性： 进行如下投影变换： 两个特性： 用Karmarkar投影尺度算法求解如下线性规划：引入松弛变量，化为标准型 化为Karmarkar标准型 路径跟踪法 Karush-Kuhn-Tucker条件松弛KKT条件 定义原始-对偶可行集原始-对偶中心路径 移动方向的计算 步长的确定 计算步骤： 三种解法比较单纯形法最老牌,研究的最为透彻,商业化的软件程序也最成熟．椭球法像昙花一現,虽然在理论上证明了线性规划问题可在多项式时间內求解,但在实际应用上反而不如单纯形法来得有效便捷。內点法是最新的设计,理论上它比椭球法还要有效,实际应用上它也可与单纯形法相抗衡,不少的商业化软件已经上市,前景甚佳。 KAM：通道费用问题现在我们碰到的主要问题：示例名目繁多、费用刚性（每年基本只涨不跌）费用超预算、费用投入与销量不成比例费用比与销量比问题、、、等等 怎么办？换位思考：如果你是零售商，面对竞争激烈毛利极低的零售市场，你会不会通过收费来弥补利润？怎么收你认为是合理的？KAM：通道费用问题 通道费用问题-原因分析：—渠道费用的形成是整个社会供过于求的结果目前在FMCG市场，大部分商品供应过剩，能否使自己的产品获得更大的展示面是获得足够市场占有率的关键，因此零售商在渠道费用的问题上处于主动地地位是很自然的。KAM：通道费用问题 通道费用问题-原因分析：—渠道费用的形成是整个社会供过于求的结果因此我们有理由相信，在可预见的未来，在渠道费用的矛盾上仍然会是零售企业唱主角。既然难以改变环境，我们所能做的是如何适应和利用环境；KAM：通道费用问题 通道费用问题-原因分析：—渠道费用的形成是整个社会供过于求的结果A.供过于求，销售价格处于通缩状态B.零售商的商品毛利率迅速降低C.零售商卖场和网络资源的货币化KAM：通道费用问题 通道费用矛盾-原因分析：许多供应商不了解零售业在当前激烈竞争环境下的赢利模式，被动地适应“终端制胜”时代，总是希望零售商别收费；部分零售商简单地把收费作为主要利润来源，不把主要精力放在商品经营上，导致商品结构、商品质量混乱；KAM：通道费用问题 KMA：通道费用问题通道费用问题-对策思路通过对零售卖场赢利模式的分析，掌握典型零售商赢利模式关键因素，制定应对政策KAM：通道费用问题 KMA：通道费用问题通道费用矛盾-零售洞察：零售卖场赢利模式分析：进销差价通道费用财务利润等VS低价形象（消费者满意）+经营利润（股东满意）KAM：通道费用问题 通道费用矛盾-零售洞察：零售商101零售商102零售商102零售商102商品利润通道利润促销支持负流动资金其他利润KAM：通道费用问题 通道费用矛盾-零售洞察：—零售商在赢造低价效应基础上的赢利模式：整体低价模式（压制供应商）赢利模型Ⅰ：商品毛利，案例分析高低价模式:赢利模型Ⅱ:毛利+费用，案例分析KAM：通道费用问题 通道费用矛盾-零售洞察：—零售商的关注点分析：模式Ⅰ：关注点—毛利率模式Ⅱ：关注点—商业毛利（通道费用）KAM：通道费用问题 通道费用问题-原因分析：—渠道费用的形成是整个社会供过于求的结果：因此我们有理由相信，在可预见的未来，在渠道费用的矛盾上仍然会是零售企业唱主角。既然难以改变环境，我们所能做的是如何适应和利用环境；KAM：通道费用问题 通道费用问题-思路分析：方法一：卖场ABC客户的费用定位方法二：零售商商品利润结构优化法方法三：以退为进的总费用控制模式方法四：通道费用的结构性控制表KAM：通道费用问题 通道费用问题-卖场ABC客户的费用定位：—调整零售卖场对公司的费用定位：零售商聚客毛利+费用费用供应商VS利润广告+利润广告KAM：通道费用问题 通道费用问题-零售商商品利润结构分析法：零售谈判的核心在于通过有效解决买方关注的问题，达到自己销售的目的；如果不帮零售商把做我们产品的整体利润提上去，而一味诉诸于谈判技巧，易出现两败俱伤的局面；KAM：通道费用问题 通道费用问题-零售商商品利润结构分析法：案例零售商在我们身上的总收益=商品利润+通道费用通过有效协助零售商分析和提升商品利润结构，即使通道费用难以满足，零售商在我们这个供应商总收益还是提升的；KAM：通道费用问题 通道费用问题-以退为进的总费用控制模式：背景分析：低价是零售商赢得消费者的核心武器，而通道费则是其抵消低价销售带来的毛利损失的关键，因此在当今零售管理中，低价销售与通道费几乎结伴而行，相互促进；KAM：通道费用问题 通道费用问题-以退为进的总费用控制模式：既然不可避免，以退为进；通道费用的提前设计：对自己产品的销售预测水平+零售商的诚信度及执行力案例分析KAM：通道费用问题 通道费用问题：通道费用的结构性分析法：非生产性条款：主要指年节费；基础生意条款：主要指新品费、新店费等；增量生意条款：主要指DM、TG等促销费。KAM：通道费用问题 通道费用问题：通道费用的结构性分析法：根据渠道生意结构、基础VS增量生意选择投入方式；大卖场渠道：主要靠周段消费拉动，把有限的通道费用聚集于增量生意的投入；案例分析（大卖场的促销）超市渠道：主要依靠工作日消费拉动，把有限的通道费用聚集于基础生意的投入；案例分析（超市的单品）KAM：通道费用问题'