运筹学整数分析案例ppt.pptx

运筹学改变肾移植方法 捐献系统中的肾脏交换和配对 黎汉英 惠原君 刘思睿 李锦楠 李椰 关键词：匹配；移植；市场设计；优化；设计；整数规划 摘要 无论从短期效果或长期存活而言，活体肾移植都已经被认为是终末期肾病(ESRD) 的最佳治疗方法。但是对于终末期肾病患者而言，即使有亲戚朋友的自愿捐赠，也仍然要面对供受者之间无法匹配的问题。 事实上，这种不相容性可以通过与另一个不相容的患者交换肾脏供体来克服，这样的肾脏交换在美国的肾移植中已经成为一种标准模式。配对捐赠联盟（APD）就是这样一个运用优化算法和市场设计等运筹学理论去提高配型效率的组织。 CONTANTS 背景 运筹学运用 算法与优化 效果与结论 肾移植背景 问题困境 短链和同时链 长链和异时链 首位循环交易算法 递归算法 在APD的表现 在美国其他移植网络的影响 01 背景 In the United States, about 100,000 sufferers of ESRD are currently on the waiting list for a kidney transplant from a deceased donor. Transplantation is the preferred treatment for this severe disease. 可供移植肾源短缺 可供移植肾脏主要有两个来源： 已故捐赠人 病患亲属朋友捐赠 肾脏严重排异 肾脏配型是一个复杂而审慎的过程，主要需要血型和组织两部分的兼容。 即使想要捐献肾脏的病患家属通过了严苛的身体检查，也有出现严重排异可能。 肾移植的必要性 对于终末期肾病患者（ESRD）而言，肾移植是世界公认的最优治疗方案。 不幸的是,在美国，大约有4000名病人在等待接受移植前就死亡了,还有病人在等待时病情加重以至于无法移植。 随着时间的推移，肾源短缺越来越严重。 背景总结 . 要解决移植的困局，就要为肾脏移植寻找一个最大的相容匹配。 这是一个经典的组合优化问题，涉及到整数规划和优化算法。 由于肾脏的交换是分散的，所以组织肾脏交换既是一个优化问题，也是一个严肃的市场设计和协调问题 02 运筹学运用 The APD initially adopted design and optimization techniques for identifying short cycles and chains. 短链和同时链 双人简单交叉交换 最初，大多数肾脏交换都以简单的双人循环交换的形式完成，如右图所示。 因为要承担失败的风险，这样的交叉交换必须同时进行，而这也成为交换过程中的一个重要的挑战——两个最简单的患者肾脏移植需要四个手术室和四个手术团队同时进行肾脏切除和移植。 因为这个原因，超过三名病人的肾脏循环交换很少进行。 短链和同时链 简单链条交换 另一种形式的交换形式是一个链，这条捐赠短链的实现首先依靠于一位利他捐助者（NDD）(即肾脏捐赠者的捐赠不要求或指定特定接受者)，见右图。 这样的短链所涉及的肾脏循环交换最多不会超过三人，手术时间也不会相隔很远。 长链和异时链 相关优势 有 两个因素始终在促使肾脏配对捐献（KPD） 的模式不断完善，救治更多的终末期肾病（ESRD）患者: ( 1) 如何最大程度的将不匹配供受者人群纳入 KPD中; ( 2) 如何在已纳入 KPD的不匹配供受者之间实现匹配最佳化。 而长链和异时链在实际运用中更好地解决了这两个问题 长链和异时链 首先，长链的编排可以尽可能减少破坏链的成本。一个利他捐助者（NDD）是非常珍贵和难得的，尽可能延长捐赠链条就可以帮助更多的ESRD患者。同时，这样的异时链突破了时间限制，更灵活的手术时间和操作成本可以为医院提供更大的操作空间。 其次，长链的运用可以更好地帮助高致敏ESRD患者。高度敏感的病人通常需要等待异常长的时间才能从捐赠者处找到一个可用的配型肾脏。许多这样的病人，很难进行两人或三人的短链移植。长链移植，为他们提供了除了等待之外的另一条选择。 长链和异时链 NEAD计划 基于这样的考虑，APD执行了第一个异时拓展利他捐赠(NEAD)长链计划，并且在2007年7月完成了第一例非同时传输的长链式肾移植手术。 APD指定在供体接受者完成了移植手术之后，长链中的最后一个捐献者将为链条中下一个部分起到搭建桥梁的作用，这样就能将每一个捐赠者的爱传递下去。 有时移植过程会被分解到长达几个月里完成。截止到2008年3月，第一条NEAD链包含了十场移植和十一位捐赠者，他们把自己的肾无偿捐赠给了陌生人。 长链和异时链 长链和异时链 这种兼容性图是从APD得到的患者供体对数据。这些标注为蓝色的病人大多是高致敏。 因此，他们无法参与循环交换，但可以作为链条终端。 03 算法与优