數(shù)據(jù)、模型與決策（原書第16版）課件 第5章、線性規(guī)劃高級應(yīng)用

數(shù)據(jù)、模型與決策,第16版第5章、線性規(guī)劃高級應(yīng)用章節(jié)內(nèi)容5-1 數(shù)據(jù)包絡(luò)分析5-2 收益管理5-3 投資組合模型和資產(chǎn)分配5-4 博弈論

本章小結(jié)學(xué)習(xí)目標(biāo)完成本章后，你將能夠：LO5.1 運用數(shù)據(jù)包絡(luò)分析，建立衡量效率的線性規(guī)劃模型并求解。LO5.2 建立收益管理的線性規(guī)劃模型并求解。LO5.3 建立投資組合的線性規(guī)劃模型并求解。LO5.4 建立博弈論的線性規(guī)劃模型并求解。LO5.5 能夠從線性規(guī)劃解決方案中識別兩人零和博弈的純策略。LO5.6 利用線性規(guī)劃確定混合策略并計算混合策略博弈的最優(yōu)概率。引言本章將繼續(xù)線性規(guī)劃的應(yīng)用研究，并介紹四種線性規(guī)劃的新應(yīng)用。

5.1節(jié)介紹數(shù)據(jù)包絡(luò)分析（DEA），它采用線性規(guī)劃方法來衡量有相同目標(biāo)的運營單元的相對效率，我們將以醫(yī)院績效測評來講述該方法的應(yīng)用。

5.2節(jié)將介紹收益管理，收益管理是對不能保存或者不易保存的一類產(chǎn)品，在已知固定庫存容量條件下，管理短期需求，以最大化可能取得的收益。收益管理在航空行業(yè)尤其重要，我們將通過確定五個城市間航班的全價票與折扣票價的最優(yōu)分配來闡明這個概念。5.3節(jié)將說明線性規(guī)劃如何用于優(yōu)化與客戶的風(fēng)險偏好相一致的投資組合。5.4節(jié)將介紹博弈論，這是對兩個或更多的決策制定者（參與者）如何能以最優(yōu)方式參與競爭的研究。這里，我們用兩家公司互相競爭市場份額的一個線性規(guī)劃模型來說明。5-1數(shù)據(jù)包絡(luò)分析(DEA)DEA的應(yīng)用數(shù)據(jù)包絡(luò)分析（DEA）是用線性規(guī)劃技術(shù)衡量具有相同目標(biāo)和目的的運營單元的相對效率的方法。例如，用DEA衡量連鎖快餐店中每個店面的效率，找出低效率店面，并為低效率店面的效率提升提供初步的對策建議。.DEA還用于衡量醫(yī)院、銀行、法院、學(xué)校等組織的相對效率。在這些應(yīng)用中，每個機構(gòu)或組織的績效是相對于同系統(tǒng)中所有工作單元的績效來衡量的。醫(yī)院績效衡量總醫(yī)院、大學(xué)醫(yī)院、縣醫(yī)院和州醫(yī)院的管理者聚在一起討論如何幫助彼此共同改進醫(yī)院績效。一個顧問建議他們考慮采用DEA衡量這四家醫(yī)院中每所醫(yī)院的相對績效。在討論如何完成這種衡量時，我們首先確定出下面三種輸入指標(biāo)和四種輸出指標(biāo)。輸入指標(biāo)全日制（FTE）非醫(yī)務(wù)人員數(shù)目物資花費可使用病床總天數(shù)輸出指標(biāo)醫(yī)療保險患者服務(wù)天數(shù)無醫(yī)療保險患者服務(wù)天數(shù)培訓(xùn)過的護士人數(shù)培訓(xùn)過的實習(xí)醫(yī)生人數(shù)5-1DEA方法概述下面我們將以縣醫(yī)院相對效率衡量為例來說明線性規(guī)劃模型是怎樣構(gòu)建的。首先，基于有相同目標(biāo)的所有運營單元的輸入和輸出，構(gòu)建一個虛擬合成單元，在這個例子中是一家虛擬醫(yī)院。

對這四家醫(yī)院的每個輸出指標(biāo)，虛擬醫(yī)院的輸出由全部四家醫(yī)院的相應(yīng)輸出加權(quán)平均計算而得。

對每個輸入指標(biāo)，虛擬醫(yī)院的輸入由全部四家醫(yī)院的相應(yīng)輸入采用相同的權(quán)重加權(quán)平均計算而得。四家醫(yī)院年消耗的資源四家醫(yī)院提供的年服務(wù)5-1DEA:決策變量

5-1DEA:輸出指標(biāo)

5-1DEA:輸出的約束條件

5-1DEA:輸入指標(biāo)

5-1DEA:輸入的約束條件為了完成輸入的約束條件方程，我們必須寫出每個約束條件的右端值的表達式。首先，要注意到右端值是虛擬醫(yī)院的可用資源。在DEA方法中，這些右端值是縣醫(yī)院輸入值的一個百分比。因此，我們必須引入下面的決策變量：E:

縣醫(yī)院輸入可用于虛擬醫(yī)院的百分比如果E=1，虛擬醫(yī)院可用的FTE非醫(yī)務(wù)人員數(shù)目就為275.70，與縣醫(yī)院使用的FTE非醫(yī)務(wù)人員數(shù)目相同。

5-1DEA:完整的線性規(guī)劃（LP）模型完整的模型如下所示：MinE

s.t.wg+wu+wc+ws=1權(quán)重的總和48.14wg+34.62wu+36.72wc+33.16ws≥36.72醫(yī)療保險43.10wg+27.11wu+45.98wc+56.46ws≥45.98非醫(yī)療保險253wg+148wu+175wc+160ws≥175護士41wg+27wu+23wc+84ws≥23實習(xí)醫(yī)生285.20wg+

162.30wu+275.70wc+210.40ws?275.70E≤0FTE非醫(yī)務(wù)人員123.80wg+

128.70wu+348.50wc+154.10ws?348.50E≤0物資106.72wg+64.21wu+104.10wc+104.04ws?104.10E≤0可使用病床總天數(shù)E,wg,wu,wc,ws≥0非負(fù)5-1DEA:模型求解縣醫(yī)院效率評價的DEA線性規(guī)劃模型有5個決策變量和8個約束條件，最優(yōu)解如下：5-1DEA:結(jié)果解讀我們首先注意到目標(biāo)函數(shù)值顯示縣醫(yī)院的效率得分為0.905。這個分?jǐn)?shù)告訴我們虛擬醫(yī)院通過使用不超過縣醫(yī)院需要輸入資源的90.5%，可以達到至少縣醫(yī)院能達到的每個輸出的水平。我們看出虛擬醫(yī)院是由總醫(yī)院（wg=0.212）、大學(xué)醫(yī)院（wu=0.260）、和州醫(yī)院（ws=0.527）加權(quán)平均形成的。剩余變量(約束2-5)虛擬醫(yī)院的每個輸出至少與縣醫(yī)院一樣多，相比縣醫(yī)院，它多出1.6個培訓(xùn)過的護士和37個培訓(xùn)過的實習(xí)醫(yī)生松弛變量(約束6-8)約束條件6和7的松弛值說明虛擬醫(yī)院使用的FTE非醫(yī)務(wù)人員和物資花費資源比縣醫(yī)院使用資源的90.5%還少。由此，我們得出結(jié)論，縣醫(yī)院與同組其他醫(yī)院相比是相對低效率的。鑒于DEA分析的結(jié)果，醫(yī)院管理者應(yīng)該檢查縣醫(yī)院的運營作業(yè)以確定應(yīng)該如何更有效地利用相關(guān)資源。5-1DEA方法總結(jié)下面的分步步驟能幫助你為其他類型的DEA應(yīng)用構(gòu)建線性規(guī)劃模型。注意，我們要衡量其相對效率的運營單元被記作第j個運營單元。步驟1. 定義決策變量，也就是權(quán)重（每個運營單元都有一個），用于確定虛擬運營單元的輸入和輸出。步驟2. 寫出要求權(quán)重總和等于1的一個約束條件。步驟3. 對每個輸出指標(biāo)，寫出一個要求虛擬運營單元的輸出大于或等于第j個運營單元對應(yīng)輸出的約束條件。步驟4. 定義一個決策變量E，它用于確定第j個運營單元的輸入可用于虛擬運營單元的比例。步驟5. 對每個輸入指標(biāo)，寫出一個要求虛擬運營單元的輸入小于或等于虛擬運營單元可用資源的約束條件。步驟6. 寫出目標(biāo)函數(shù)，即MinE。收益管理休閑航空公司收益管理是在庫存水平一定的情況下，通過對不易保存產(chǎn)品的短期需求管理，以取得潛在收益的最大化。這個方法最早由美國航空公司提出，最初是用于確定航班中折扣價座位和全價座位的數(shù)量。現(xiàn)在的應(yīng)用領(lǐng)域包括旅館、公寓出租、汽車出租、郵輪以及高爾夫球場。為了說明收益管理的基本原理，我們將用一個線性規(guī)劃模型為休閑航空公司（LeisureAir）建立一個收益管理計劃，這是一家為匹茲堡、紐瓦克、夏洛特、默特爾比奇和奧蘭多提供航空服務(wù)的地區(qū)航空公司。5-2休閑航空公司:問題描述休閑航空公司有兩架波音737-400飛機，一架的駐場在匹茲堡出，另一架的駐場在紐瓦克。

兩架飛機都有一個容量為132個座位的經(jīng)濟艙。每天早上駐場在匹茲堡的飛機在夏洛特中途停留后飛往奧蘭多，駐場在紐瓦克的飛機在夏洛特中途停留后飛往默特爾比奇。每天結(jié)束前，兩架飛機再回到其出發(fā)地。為了把問題的規(guī)模控制在一個合理的范圍內(nèi)，我們只考慮早上匹茲堡到夏洛特、夏洛特到奧蘭多、紐瓦克到夏洛特，以及夏洛特到默特爾比奇的航程。休閑航空公司的機票有兩個價位等級：折扣票Q等級以及全價票Y等級。預(yù)訂折扣票Q等級必須提前14天并且要在目的地城市停留一晚（周六）。使用全價票Y等級可以在任何時間預(yù)訂，而且日后改簽也沒有任何損失。

為了確定休閑航空能為其顧客提供航線和費用選擇，我們不僅須考慮每個航班的起飛地和目的地，還得考慮費用等級。5-2休閑航空公司:模型建立休閑航空16個起飛地—目的地—旅程費5月5日，休閑航空為其16個ODIF確定費用并對顧客需求進行預(yù)測。決策變量為了建立一個線性規(guī)劃模型來確定休閑航空應(yīng)為每種費用等級分配多少個座位，我們需要定義16個決策變量，即為每個起飛地—目的地—旅程費定義一個變量。我們用P代表匹茲堡，N代表紐瓦克，C代表夏洛特，M代表默特爾比奇，O代表奧蘭多，決策變量采用下面的形式：PCQ:

分配給匹茲堡—夏洛特Q等級的座位數(shù)PMQ:分配給匹茲堡—默特爾比奇Q等級的座位數(shù)POQ:分配給匹茲堡—奧蘭多Q等級的座位數(shù)PCY:

分配給匹茲堡—夏洛特Y等級的座位數(shù) ?NCQ:分配給紐瓦克—夏洛特Q等級的座位數(shù) ?COY:分配給夏洛特—奧蘭多Y等級的座位數(shù)5-2休閑航空公司:約束條件容量的約束條件

需求的約束條件5-2休閑航空公司:完整的線性規(guī)劃（LP）模型

5-2休閑航空公司:模型求解休閑航空收益管理問題的最優(yōu)解如圖所示：5-2休閑航空公司:結(jié)果解讀最優(yōu)解的值是103103美元。最優(yōu)解顯示PCQ=33，PMQ=44，POQ=22，PCY=16，等等。我們看到約束條件6的對偶值為85美元。對偶值告訴我們?nèi)绻俣嘣黾右粋€Q等級座位給匹茲堡—默特爾比奇，收益將增加85美元。收益的這個增量被稱作這個起飛地—目的地—旅程費的出價。一般來說，一個ODIF的出價會告訴休閑航空預(yù)訂代理，當(dāng)這個ODIF售空后再增加一個額外預(yù)訂的價值。通過觀察圖中需求的約束條件的對偶值，我們看到最高的對偶值（出價）為約束條件8（PCY≤16）的376美元。給定這個收益貢獻，預(yù)訂代理將最可能接受此額外預(yù)訂，盡管這樣會導(dǎo)致航班的超量預(yù)訂。然而，當(dāng)前解中的出價信息和一些簡單的決策規(guī)則也能使預(yù)訂代理做出改進公司收益的決策。理論上，每次在一個起飛地—目的地—旅程費的容量內(nèi)接受一個預(yù)訂，線性規(guī)劃模型就應(yīng)該被更新，進行重新求解以得到新的座位分配和出價信息。在實踐中，因為涉及大量航班，所以實時更新分配是不實際的。5-3投資組合模型和資產(chǎn)分配共同基金的投資組合資產(chǎn)分配是關(guān)于決定如何分配投資資金到多種資產(chǎn)種類的過程，如股票、債券、共同基金、房地產(chǎn)和現(xiàn)金等。

投資組合模型用于確定應(yīng)該在每種資產(chǎn)種類上分配的投資資金的比例。它的目標(biāo)是建立一個投資組合，使風(fēng)險和回報達到最佳平衡。Hauck投資服務(wù)公司希望建立一個投資組合模型，用于確定一個由6種共同基金構(gòu)成的最佳投資組合。共同基金的年回報率Hauck投資服務(wù)公司的投資組合管理者認(rèn)為下表可以代表這6種共同基金下一年回報的所有可能性。第1年所有共同基金的年回報都是好的，第2年大部分共同基金的回報也是好的，但是第3年小市值價值基金的回報不好，第4年中期債券基金的回報不好，第5年6種共同基金中有4種的回報都不好。5-3保守的投資組合決策變量Hauck投資服務(wù)公司的一個投資組合管理者被要求為公司的保守客戶建立一個投資組合，這類客戶對風(fēng)險有很強烈的規(guī)避傾向。.經(jīng)理的任務(wù)是決定投資在這6種共同基金上的各個比例，以使投資組合能以最小的風(fēng)險提供最大可能的回報。

為了確定每種共同基金的投資比例，我們使用下面的決策變量：FS=外國股票基金的投資比例IB=中期債券基金的投資比例LG=大市值成長基金的投資比例LV=大市值價值基金的投資比例SG=小市值成長基金的投資比例SV=小市值價值基金的投資比例約束條件和目標(biāo)函數(shù)

5-3保守的投資組合：完整的線性規(guī)劃（LP）模型完整的模型如下所示：MaxM

s.t.10.06FS+17.64IB+32.41LG+32.36LV+33.44SG+24.56SV≥M13.12FS+

3.25IB+18.71LG+20.61LV+19.40SG+25.32SV≥M13.47FS+7.51IB+33.28LG+12.93LV+3.85SG?

6.70SV≥M45.42FS+1.33IB+41.46LG+7.06LV+58.68SG+5.43SV≥M?21.93FS+7.36IB?23.26LG?5.37LV?9.02SG+17.31SV≥MFS+IB+LG+LV+SG+SV=1M,FS,IB,LG,LV,SG,SV≥05-3保守的投資組合:模型求解和結(jié)果解釋Hauck投資服務(wù)公司最大最小模型的最優(yōu)解如圖所示：目標(biāo)函數(shù)的最優(yōu)值是6.445，因此，最優(yōu)投資組合在情形最差的方案下能得到6.445%的回報率。最優(yōu)解要求55.4%的資金投資于中期債券基金，13.2%的資金投資于大市值成長基金，以及31.4%的資金投資于小市值價值基金。約束條件3、4和5對應(yīng)方案3、4和5（表5-4中的第3年、第4年和第5年）。這些約束條件的剩余變量為0表示：如果這3個方案中任意一個發(fā)生，投資組合的回報率將是M=6.445%。約束條件1的剩余變量為15.321，表示如果方案1發(fā)生，投資組合的回報率將比M=6.445%多15.321%。因此，如果方案1發(fā)生，投資組合回報率將是6.445%+15.321%=21.766%。至于約束條件2的剩余變量，我們看到如果方案2發(fā)生，投資組合回報率將是6.445%+5.785%=12.230%。5-3中等風(fēng)險的投資組合決策變量投資服務(wù)公司的投資組合經(jīng)理愿意為這樣一類客戶建立一個投資組合，這類客戶為了獲得更好的回報而愿意接受中等程度的風(fēng)險。

假定這類客戶愿意接受一些風(fēng)險，但是不愿意投資組合的年回報率低于2%。通過設(shè)定最大最小模型中的最低回報約束條件M=2，我們能使模型提供一個年回報率至少為2%的解。約束條件和目標(biāo)函數(shù)

5-3中等風(fēng)險的投資組合：完整的線性規(guī)劃（LP）模型完整的模型如下所示：Max0.2R1+0.2R2+0.2R3+0.2R4+0.2R5

s.t.10.06FS+17.64IB+32.41LG+32.36LV+33.44SG+24.56SV=R113.12FS+

3.25IB+18.71LG+20.61LV+19.40SG+25.32SV=R213.47FS+7.51IB+33.28LG+12.93LV+3.85SG?

6.70SV=R345.42FS+1.33IB+41.46LG+7.06LV+58.68SG+5.43SV=R4?21.93FS+7.36IB?23.26LG?5.37LV?9.02SG+17.31SV=R5R1≥2R2≥2R3≥2R4≥2R5≥2FS+IB+LG+LV+SG+SV=1M,FS,IB,LG,LV,SG,SV≥0這個包含11個變量和11個約束條件的投資組合最優(yōu)化問題完整的線性規(guī)劃結(jié)果如圖所示：目標(biāo)函數(shù)值表明這樣分配提供了17.33%的最大預(yù)期回報率。最優(yōu)解如圖所示。最優(yōu)分配是投資10.8%在大市值成長基金、41.5%在小市值成長基金、47.7%在小市值價值基金。從剩余變量中，我們看到如果方案3或5發(fā)生（約束條件8和10是有效的），投資組合的回報率將只是2%。如果方案1、2或4發(fā)生，回報率將非常好：如果方案1發(fā)生，投資組合回報率將是29.093%；如果方案2發(fā)生，則為22.149%；如果方案4發(fā)生，則為31.417%。5-3中等風(fēng)險的投資組合:模型求解和結(jié)果解釋5-4博弈論導(dǎo)入在博弈論中，互相競爭的兩個或更多的決策制定者被稱作參與者。

每個參與者在預(yù)先不知道其他參與者所選策略的情況下，選擇多個策略中的一個。

競爭策略組合為參與者提供了博弈的價值。這一節(jié)描述兩人零和博弈?！皟扇恕币馕吨袃蓚€參與者參與博弈“零和”意味著一個參與者的獲益（損失）等于另一個參與者的損失（獲益）。市場份額的競爭假定兩家公司是一種特殊產(chǎn)品僅有的制造商，它們互相競爭市場份額。在設(shè)計來年營銷策略時，每家公司將選擇設(shè)計好的三個策略之一來從對方公司中爭奪市場份額。假定這三個策略對兩家公司都是一樣的，如下所示：策略1: 增加廣告策略2: 提供數(shù)量折扣策略3: 延長保修效益表顯示了在每個策略組合下，公司A市場份額的百分比收益。因為這是一個零和博弈，所以公司A在市場份額的任意收益是公司B市場份額的損失。5-4零和博弈效益表例如，如果公司A增加廣告（a1），公司B延長保修期（b3），公司A的市場份額將領(lǐng)先，增加2%，而公司B的市場份額將相應(yīng)減少2%。公司A想要最大化其收益，即增加市場份額；公司B想要最小化收益，因為公司A市場份額的增加是公司B市場份額的減少。兩家公司的最佳策略公司A的最大最小策略：公司A選擇提供最大的行最小值的策略。公司B的最小最大策略:公司B選擇能提供最小的列最大值的策略。5-4純策略解的確定如果選擇一個策略對兩個參與者都是最優(yōu)的，并且無論對方做什么都會堅持這個策略，這種博弈就有純策略解。純策略解的條件如下所示：如果行最小值=列最大值，則一個博弈有純策略解這種博弈被稱作有一個鞍點或一個均衡點。如果純策略解存在，它就是博弈的最優(yōu)解即使一家公司提前發(fā)現(xiàn)其對手的純策略，公司也不能從改變它自身純策略中獲得任何優(yōu)勢因為在我們的例子中這個等式成立，所以博弈的解就是公司A增加廣告（策略a1）和公司B延長保修（策略b3）。公司A的市場份額將增加2%，公司B的市場份額將減少2%。如果行最小值的最大值不等于列最大值的最小值，純策略解不存在。

在這種情形下，混合策略解變成最優(yōu)解。.在后面的討論中，我們定義混合策略解，并說明如何用線性規(guī)劃來確定每個參與者的最優(yōu)混合策略。5-4混合策略解的確定修改后的的效益表讓我們繼續(xù)兩家公司市場份額的博弈，并考慮稍微修改后的效益表。如果公司A和公司B都選擇延長保修策略，公司A現(xiàn)在的收益是市場份額增加5%而不是之前的0。預(yù)期收益

5-4混合