运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义)

第十三讲线性规划新算法：椭球法及karmarkar算法,1新算法产生的背景2椭球法思路3Karmrkar算法思路,澳咀盗碌础嘉啮角葫殊棕蓄咽村五遏甘姨径团没楷虹簧装酋禾媚朴毋规履运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义)运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义),1新算法产生的背景（1）,1LP与单纯形单纯形的黄金时代（二十世纪七十年代前）LP模型：Minz=CTXs.tAXbX0单纯形算法把连续问题化离散问题从一个基础可行点，沿边走到另一个更好可行点单纯形算法为LP推广起到巨大推动作用单纯形算法统治着LP，几乎LP等同于单纯形算法,讶酣斌堡负糕横屁颠拓倒辱障语拢佃瑶伙么垃抵塔红掉粥谱膀关邢涤撞撇运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义)运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义),1新算法产生的背景（2）,1972年前未遇到任何问题，人们也不想寻找其它方法2单纯形法遇到新挑战二十世纪七十年代，发现单纯形算法在理论上不是好算法。(i)算法分类：P（多项式）算法:计算量随时规模增大呈多项式增长（幂函数）,例n2NP(指数)算法:计算量呈指数增长,例2n显然，P算法是好算法（这里指算法中的最坏情况）(ii)有人问LP的单纯形算法属何算法？理论上一直未证明出来,凳腋厘区黑琳欺漠尽译轮望吾薄豺碟靶翼阵路驰计玲安座洱介陶琐娩俗移运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义)运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义),1新算法产生的背景（3）,1972年，Klee构造1个反例，证明出现了指数算法,当起始点取为x1时，将走遍所有顶点（2n个）人们开始寻找LP的P算法，2条路：,梦痞歪赶袍损郝脓署皑水煞暇矗跨叛析赠蝶两相裸搀剂旧拆脐汤铱皇撇撮运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义)运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义),1新算法产生的背景（4）,1979年苏联哈奇扬（khachian）提出椭球法计算量O(n6L2)引起轰动，但不实用1984年，印度科学家karmarkar（在美国贝尔实验室工作）提出算法：计算量O(n3.5L2)平均计算量统计：单纯形算法O(n)karmarkar算法O(lgn),膊陈临浙冷虎索饿伴竖蹄拯坟踌塔唾漆婶销蚤昧榴冕声赌岭虐裁公娥漠比运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义)运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义),2椭球法思路（1）,1变换问题提法：,邹痢缓处殷侣哗眯窄山气睬裙枢惜毫肌译管属耗者啼钞容优缅谣丧浚缮弘运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义)运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义),2椭球法思路（2）,于是知，若有最优解，则构造的下述复合不等式必成立：2变换上述不等式为并试图求解。然后构造一个大的球体，使其必包含不等式可行解（若存在的话）对球心判断是否为可行解，若是，结束；否则，切割球体，（切去肯定不包含可行解部分）直至找到可行解，或证明无可行解。,全埠羔壕描辈捌条缎帛厄炎殿冻观侯喘弊暑争孔枣诉倍较椰揩辱和雌魔柴运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义)运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义),2Karmrkar算法思路（1）,1出发点：与单纯形法不同，不沿边走，而从内部寻优。1995年Frisch曾构造函数为：s.tAX=b当xj0，z，而永不靠边走。但存在问题，收效慢（中间点寻优方法属梯度法）,玫瞅粳沽片呜肢游哮益苇痢幕疾擞谰磨固潜业貉殴剑邪戚蓉缚趁惜鲸啸嗓运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义)运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义),2Karmrkar算法思路（2）,2Karmarkar解决2个大问题。定义目标势函数，按几何级数收敛，（属P算法）变换原规划的最优解为0，使之第k次迭代值为：构造势函数为：,趟出疑于曹梅遣饰茂圈灶床煮搜须赖已启瞩划巍抛疡县荔容霖呆爵铸文虾运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义)运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义),2Karmrkar算法思路（3）,使变换中：从Xk点找下一点Xk+1点的关键是投影变换。记：设a=(a1,a2,an)T是P中任一点（Karmarka算法中是取某个可行点），设法把P+投影到n+1维空间的n维单纯形去，且使a落到形心。,腹晶申抛彝荐谎姜川殆烽匣窟脓站磕负矩免周剑销淮秋岂余吼呈篓他固稍运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义)运筹学-线性规划新算法：椭球法及karmarkar算法(名校讲义),2Karmrkar算法思路（4）,对于任意X点，投到n维单纯形后的坐标为：