運(yùn)籌學(xué)整數(shù)分析案例ppt

運(yùn)籌學(xué)改變腎移植方法捐獻(xiàn)系統(tǒng)中的腎臟交換和配對(duì)黎漢英惠原君劉思睿李錦楠李椰關(guān)鍵詞：匹配；移植；市場(chǎng)設(shè)計(jì)；優(yōu)化；設(shè)計(jì)；整數(shù)規(guī)劃摘要

無論從短期效果或長期存活而言，活體腎移植都已經(jīng)被認(rèn)為是終末期腎病(ESRD)的最佳治療方法。但是對(duì)于終末期腎病患者而言，即使有親戚朋友的自愿捐贈(zèng)，也仍然要面對(duì)供受者之間無法匹配的問題。事實(shí)上，這種不相容性可以通過與另一個(gè)不相容的患者交換腎臟供體來克服，這樣的腎臟交換在美國的腎移植中已經(jīng)成為一種標(biāo)準(zhǔn)模式。配對(duì)捐贈(zèng)聯(lián)盟（APD）就是這樣一個(gè)運(yùn)用優(yōu)化算法和市場(chǎng)設(shè)計(jì)等運(yùn)籌學(xué)理論去提高配型效率的組織。CONTANTS背景運(yùn)籌學(xué)運(yùn)用算法與優(yōu)化效果與結(jié)論腎移植背景問題困境短鏈和同時(shí)鏈長鏈和異時(shí)鏈?zhǔn)孜谎h(huán)交易算法遞歸算法在APD的表現(xiàn)在美國其他移植網(wǎng)絡(luò)的影響01背景IntheUnitedStates,about100,000sufferersofESRDarecurrentlyonthewaitinglistforakidneytransplantfromadeceaseddonor.Transplantationisthepreferredtreatmentforthisseveredisease.可供移植腎源短缺可供移植腎臟主要有兩個(gè)來源：已故捐贈(zèng)人病患親屬朋友捐贈(zèng)腎臟嚴(yán)重排異腎臟配型是一個(gè)復(fù)雜而審慎的過程，主要需要血型和組織兩部分的兼容。即使想要捐獻(xiàn)腎臟的病患家屬通過了嚴(yán)苛的身體檢查，也有出現(xiàn)嚴(yán)重排異可能。腎移植的必要性對(duì)于終末期腎病患者（ESRD）而言，腎移植是世界公認(rèn)的最優(yōu)治療方案。不幸的是,在美國，大約有4000名病人在等待接受移植前就死亡了,還有病人在等待時(shí)病情加重以至于無法移植。隨著時(shí)間的推移，腎源短缺越來越嚴(yán)重。背景總結(jié).要解決移植的困局，就要為腎臟移植尋找一個(gè)最大的相容匹配。這是一個(gè)經(jīng)典的組合優(yōu)化問題，涉及到整數(shù)規(guī)劃和優(yōu)化算法。由于腎臟的交換是分散的，所以組織腎臟交換既是一個(gè)優(yōu)化問題，也是一個(gè)嚴(yán)肅的市場(chǎng)設(shè)計(jì)和協(xié)調(diào)問題02運(yùn)籌學(xué)運(yùn)用TheAPDinitiallyadopteddesignandoptimizationtechniquesforidentifyingshortcyclesandchains.短鏈和同時(shí)鏈雙人簡(jiǎn)單交叉交換最初，大多數(shù)腎臟交換都以簡(jiǎn)單的雙人循環(huán)交換的形式完成，如右圖所示。因?yàn)橐袚?dān)失敗的風(fēng)險(xiǎn)，這樣的交叉交換必須同時(shí)進(jìn)行，而這也成為交換過程中的一個(gè)重要的挑戰(zhàn)——兩個(gè)最簡(jiǎn)單的患者腎臟移植需要四個(gè)手術(shù)室和四個(gè)手術(shù)團(tuán)隊(duì)同時(shí)進(jìn)行腎臟切除和移植。因?yàn)檫@個(gè)原因，超過三名病人的腎臟循環(huán)交換很少進(jìn)行。短鏈和同時(shí)鏈簡(jiǎn)單鏈條交換另一種形式的交換形式是一個(gè)鏈，這條捐贈(zèng)短鏈的實(shí)現(xiàn)首先依靠于一位利他捐助者（NDD）(即腎臟捐贈(zèng)者的捐贈(zèng)不要求或指定特定接受者)，見右圖。這樣的短鏈所涉及的腎臟循環(huán)交換最多不會(huì)超過三人，手術(shù)時(shí)間也不會(huì)相隔很遠(yuǎn)。長鏈和異時(shí)鏈相關(guān)優(yōu)勢(shì)有兩個(gè)因素始終在促使腎臟配對(duì)捐獻(xiàn)（KPD）

的模式不斷完善，救治更多的終末期腎?。‥SRD）患者:(1)如何最大程度的將不匹配供受者人群納入KPD中;(2)如何在已納入KPD的不匹配供受者之間實(shí)現(xiàn)匹配最佳化。而長鏈和異時(shí)鏈在實(shí)際運(yùn)用中更好地解決了這兩個(gè)問題長鏈和異時(shí)鏈?zhǔn)紫?，長鏈的編排可以盡可能減少破壞鏈的成本。一個(gè)利他捐助者（NDD）是非常珍貴和難得的，盡可能延長捐贈(zèng)鏈條就可以幫助更多的ESRD患者。同時(shí)，這樣的異時(shí)鏈突破了時(shí)間限制，更靈活的手術(shù)時(shí)間和操作成本可以為醫(yī)院提供更大的操作空間。其次，長鏈的運(yùn)用可以更好地幫助高致敏ESRD患者。高度敏感的病人通常需要等待異常長的時(shí)間才能從捐贈(zèng)者處找到一個(gè)可用的配型腎臟。許多這樣的病人，很難進(jìn)行兩人或三人的短鏈移植。長鏈移植，為他們提供了除了等待之外的另一條選擇。長鏈和異時(shí)鏈NEAD計(jì)劃基于這樣的考慮，APD執(zhí)行了第一個(gè)異時(shí)拓展利他捐贈(zèng)(NEAD)長鏈計(jì)劃，并且在2007年7月完成了第一例非同時(shí)傳輸?shù)拈L鏈?zhǔn)侥I移植手術(shù)。APD指定在供體接受者完成了移植手術(shù)之后，長鏈中的最后一個(gè)捐獻(xiàn)者將為鏈條中下一個(gè)部分起到搭建橋梁的作用，這樣就能將每一個(gè)捐贈(zèng)者的愛傳遞下去。有時(shí)移植過程會(huì)被分解到長達(dá)幾個(gè)月里完成。截止到2008年3月，第一條NEAD鏈包含了十場(chǎng)移植和十一位捐贈(zèng)者，他們把自己的腎無償捐贈(zèng)給了陌生人。長鏈和異時(shí)鏈長鏈和異時(shí)鏈這種兼容性圖是從APD得到的患者供體對(duì)數(shù)據(jù)。這些標(biāo)注為藍(lán)色的病人大多是高致敏。因此，他們無法參與循環(huán)交換，但可以作為鏈條終端。03算法與優(yōu)化TheAPDandotherkidneyexchangeprogramsorganizetransplantsbyregularlysearchingthecompatibilitygraphgeneratedbythecurrentpoolofpatientsanddonorsforthemaximumweightednumberoftransplantsthatcanbeachievedthroughcyclesandchains.ItisconvenienttothinkofthepoolasacompatibilitynetworkdescribedbyadirectedgraphG（V,E）.TTC算法首位交易循環(huán)（TTC）TTC算法是單邊匹配理論的基石。以腎交換為例，具體步驟如下：每組捐贈(zèng)配對(duì)捐獻(xiàn)組包括2人，即患者和定向?yàn)槠渚枘I的捐獻(xiàn)者，表示為（ki，ti），其中ki是捐贈(zèng)者的腎臟，ti是作為病人的接受者。由腎臟與病人排序列單必定組成一個(gè)循環(huán)為（k1，t1，k2，t2，…km，tm，k1），即腎臟k1指向病人t1、病人t1指向腎臟k2……腎臟km指向病人tm、病人tm又指向腎臟k1形成的循環(huán)。TTC算法首位交易循環(huán)（TTC）TTC算法是單邊匹配理論的基石。然后將腎臟k2安排給病人t1，腎臟k3安排給病人t2……腎臟k1安排給病人tm。這些配對(duì)的腎臟與病人從市場(chǎng)中移除，然后繼續(xù)排序，形成循環(huán)，循環(huán)內(nèi)的所有被指向的病人得到腎臟，重復(fù)以上步驟，直到每個(gè)病人得到腎臟為止。TTC算法產(chǎn)生的匹配結(jié)果滿足帕累托有效性、穩(wěn)定性及激勵(lì)相容性。TTC機(jī)制等價(jià)于嚴(yán)格“核”機(jī)制，當(dāng)偏好是嚴(yán)格，它是唯一滿足個(gè)體理性、帕累托有效、抗策略性的一種機(jī)制。遞歸算法用這個(gè)算法解決使用約束生成的優(yōu)化問題，無需為每一個(gè)鏈條的變量賦值，只需引入流守恒約束。要了解這個(gè)算法首先要解釋一下隨機(jī)圖的概念：隨機(jī)圖(randomgraph)，它是伴隨有不確定性的圖，是按某種隨機(jī)方式刪去一個(gè)圖G的某些節(jié)點(diǎn)或邊而保留下來的圖，又稱為隨機(jī)子圖.G稱為隨機(jī)圖的原始圖。隨機(jī)圖的性質(zhì)與原始圖，以及隨機(jī)刪除原始圖點(diǎn)或邊的方式有關(guān).隨機(jī)刪除方式包括只刪點(diǎn)、只刪邊和既刪點(diǎn)又刪邊三種.遞歸算法所以一個(gè)隨機(jī)圖實(shí)際上就是將給定的頂點(diǎn)之間隨機(jī)地連上邊（邊是沒有方向性的）。假設(shè)將一些紐扣散落在地上，并且不斷隨機(jī)地將兩個(gè)紐扣之間系上一條線，這樣就得到一個(gè)隨機(jī)圖的例子。

顯而易見，本文中的腎移植案例的腎源匹配就是一個(gè)天然的隨機(jī)圖模型，同時(shí)也是一個(gè)整數(shù)規(guī)劃模型。所以，將移植數(shù)據(jù)庫視作原始圖G(V,E)，使用遞歸算法在計(jì)算機(jī)上進(jìn)行運(yùn)算。遞歸算法遞歸：最大化加權(quán)流S.T.

Totalflowoutofapairisatmostthetotalflowthatgoesintoapair總輸出量不能大于總輸入量Totalflowoutofanaltruisticdonorisatmost1一例利他捐助最大輸出為1Totalflowthatgoesintoapairisatmost1每次輸入量最大為1Flowoneachedgeisbinary在每個(gè)邊以二進(jìn)制輸入04效果與結(jié)論KidneyexchangehasbecomeastandardpartoftransplantationintheUnitedStates,andtheinnovativeideasofmanyresearchersandpractitionershaveplayedanimportantroleinthissuccess.在APD的表現(xiàn)肝臟配對(duì)捐贈(zèng)聯(lián)盟（APD）為了擴(kuò)大活體供者池，APD聯(lián)合了83家移植中心參與，眾多中心將供受者資源整合至APD中，使得供受者群體大大增加.在異時(shí)鏈被引入以來，超過220例的ESRD患者通過NEAD長鏈進(jìn)行了腎移植，不僅自己重獲健康，而且累積為美國醫(yī)療保健系統(tǒng)節(jié)約了450萬美元的透析費(fèi)用。對(duì)于美國其他移植網(wǎng)絡(luò)全美有超過200家移植中心，而自從NEAD鏈條實(shí)施以來，260