數(shù)學(xué)實(shí)驗(yàn)線性規(guī)劃

數(shù)學(xué)實(shí)驗(yàn)課件線性規(guī)劃第1頁，共67頁，2023年，2月20日，星期六22002.5.1．理解優(yōu)化模型的三個(gè)要素:決策變量，目標(biāo)函數(shù)和約束條件；２．掌握用MATLAB優(yōu)化工具箱求解線性規(guī)劃的方法；３．了解線性規(guī)劃模型中的靈敏度分析方法；掌握如何使用軟件來實(shí)現(xiàn)分析；４．體驗(yàn)由實(shí)際問題建立線性規(guī)劃模型的全過程。實(shí)驗(yàn)?zāi)康牡?頁，共67頁，2023年，2月20日，星期六32002.5.應(yīng)用場景___成功的優(yōu)化例子“最優(yōu)人員安排”為美國航空每年節(jié)約兩千萬美元.第3頁，共67頁，2023年，2月20日，星期六42002.5.

“改進(jìn)的出貨流程”每年為YellowFreight公司節(jié)約一千七百多萬美元.應(yīng)用場景___成功的優(yōu)化例子第4頁，共67頁，2023年，2月20日，星期六52002.5.

“改進(jìn)的卡車分派”為Reynolds公司每年節(jié)約七百萬美元.應(yīng)用場景___成功的優(yōu)化例子第5頁，共67頁，2023年，2月20日，星期六62002.5.

“最優(yōu)全局供應(yīng)鏈”為數(shù)字設(shè)備行業(yè)節(jié)約超過三億美元.應(yīng)用場景___成功的優(yōu)化例子第6頁，共67頁，2023年，2月20日，星期六72002.5.

寶潔公司重建北美業(yè)務(wù),減少20%的工廠,每年節(jié)約兩億美元.應(yīng)用場景___成功的優(yōu)化例子第7頁，共67頁，2023年，2月20日，星期六82002.5.成功的優(yōu)化例子

大阪Hanshin高速的“最優(yōu)交通控制”每年節(jié)約一千七百萬人小時(shí),為他們帶來三億二千萬美圓的收益.第8頁，共67頁，2023年，2月20日，星期六92002.5.第9頁，共67頁，2023年，2月20日，星期六102002.5.引例單耗

甲乙丙限額材料工時(shí)工人231321.5325343640利潤(元/件)432在一定的條件下，問生產(chǎn)數(shù)量為多少時(shí),利潤達(dá)到最大？數(shù)據(jù)表生產(chǎn)計(jì)劃問題第10頁，共67頁，2023年，2月20日，星期六引例運(yùn)輸問題A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道鐵路公路S1~S7

鋼管廠火車站450里程(km)目標(biāo)：運(yùn)費(fèi)達(dá)到最小第11頁，共67頁，2023年，2月20日，星期六122002.5.特點(diǎn)：從若干可能的計(jì)劃（方案）中尋求某種意義下的最優(yōu)方案，數(shù)學(xué)上將這種問題稱為最優(yōu)化問題（optimization).1、生產(chǎn)計(jì)劃問題；2、運(yùn)輸問題；最優(yōu)化問題簡介第12頁，共67頁，2023年，2月20日，星期六132002.5.優(yōu)化問題的表述

最優(yōu)化是企業(yè)運(yùn)作、科技研發(fā)和工程設(shè)計(jì)中常見的問題。要表述一個(gè)最優(yōu)化問題（即建立數(shù)學(xué)模型），應(yīng)明

明確三樣?xùn)|西：決策變量、約束條件和目標(biāo)函數(shù)．決策變量：它們是決策者（你）所控制的那些數(shù)量，它們?nèi)∈裁磾?shù)值需要決策者來決策，最優(yōu)化問題的求解就是找出決策變量的最優(yōu)取值。約束條件：它們是決策變量在現(xiàn)實(shí)世界中所受到的限制，或者說決策變量在這些限制范圍之內(nèi)取值才有實(shí)際意義。

目標(biāo)函數(shù)：它代表決策者希望對其進(jìn)行優(yōu)化的那個(gè)指標(biāo)。目標(biāo)函數(shù)是決策變量的函數(shù)。第13頁，共67頁，2023年，2月20日，星期六142002.5.規(guī)劃模型利潤材料工時(shí)人力單耗

甲乙丙

x1x2x3限額材料工時(shí)工人231321.5325343640利潤(元/件)432生產(chǎn)計(jì)劃問題max目標(biāo)函數(shù)約束條件決策變量x1,x2,x3第14頁，共67頁，2023年，2月20日，星期六152002.5.單耗

甲乙丙

x1x2x3限額材料工時(shí)工人231321.5325343640利潤(元/件)432生產(chǎn)計(jì)劃問題規(guī)劃模型利潤材料工時(shí)人力第15頁，共67頁，2023年，2月20日，星期六最優(yōu)化問題運(yùn)輸問題A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道鐵路公路S1~S7

鋼管廠火車站450里程(km)目標(biāo)：運(yùn)費(fèi)達(dá)到最小第16頁，共67頁，2023年，2月20日，星期六172002.5.cij—單位運(yùn)費(fèi)；ai

—在第i廠提供的量；bj—第j地需要量；求從si運(yùn)多少鋼管到Aj,可使總運(yùn)費(fèi)最少.決策變量:xij—從si運(yùn)到Aj的鋼管數(shù)量s1s2sis7……A1A2AjA15……C11C12C1jC1,15Ci,jaia1a2a7b15b1b2bj第17頁，共67頁，2023年，2月20日，星期六182002.5.s1s2sis7……A1A2AjA15……C11C12C1jC1,15Ci,jaia1a2a7b15b1b2bj第18頁，共67頁，2023年，2月20日，星期六192002.5.三個(gè)基本要素1、決策變量（decisionvariables);2、約束條件（constraints);3、目標(biāo)函數(shù)（objectivefunction)最優(yōu)化問題分類①線性、非線性②靜態(tài)、動(dòng)態(tài)③整數(shù)、非整數(shù)④隨機(jī)、非隨機(jī)等

最優(yōu)化問題第19頁，共67頁，2023年，2月20日，星期六202002.5.最優(yōu)化數(shù)學(xué)模型的分類

線性規(guī)劃(LP)

非線性規(guī)劃(NLP)

二次規(guī)劃(QP)

整數(shù)規(guī)劃(IP)多目標(biāo)規(guī)劃動(dòng)態(tài)規(guī)劃

最優(yōu)化問題第20頁，共67頁，2023年，2月20日，星期六212002.5.生產(chǎn)計(jì)劃問題該模型的目標(biāo)函數(shù)和約束條件均為線性函數(shù),

滿足線性規(guī)劃的要求,故該問題為一線性規(guī)劃問題,其模型為線性規(guī)劃模型.利潤材料工時(shí)人力線性規(guī)劃第21頁，共67頁，2023年，2月20日，星期六222002.5.生產(chǎn)計(jì)劃問題maxcTxs.t.Ax≤b

x≥0矩陣形式：利潤材料工時(shí)人力線性規(guī)劃模型第22頁，共67頁，2023年，2月20日，星期六232002.5.mincTxs.t.Ax

=b

x≥0(或a≤x≤b)標(biāo)準(zhǔn)形式其中：x∈Rn，A∈Rm×n，b∈Rm，c∈Rn線性規(guī)劃第23頁，共67頁，2023年，2月20日，星期六242002.5.Ⅰ2X1+X2=40X1+2X2=50

X1

X2abcd可行點(diǎn)可行域凸多面體v內(nèi)點(diǎn)邊界點(diǎn)頂點(diǎn)vB線性規(guī)劃解的若干概念線性規(guī)劃模型maxz=5x1+3x2s.t.2x1+x2≤40

x1+2x2≤50x1，x2≥0第24頁，共67頁，2023年，2月20日，星期六252002.5.線性規(guī)劃解的圖示線性規(guī)劃模型maxz=5x1+3x2s.t.2x1+x2≤40

x1+2x2≤50x1，x2≥02X1+X2=40X1+2X2=50

X1

X2a20x1=10,x2=2025問:什么樣的問題可以使用圖解法?你從圖中得到什么啟示?P=0P=50P=110第25頁，共67頁，2023年，2月20日，星期六求解LP的特殊情形Maxz=3x1+x2s.t.-x1+x2≤2----L1

x1-2x2≤2----L23x1+2x2≤14----L3

x1，x2≥0x1x2L2L1L30x1x2L2L1L30x1x2L2L10x1x2L2L1L30z=c②無最優(yōu)解①無可行解③最優(yōu)解不唯一第26頁，共67頁，2023年，2月20日，星期六線性規(guī)劃的基本性質(zhì)可行域線段組成的凸多邊形目標(biāo)函數(shù)等值線為直線最優(yōu)解凸多邊形的某個(gè)頂點(diǎn)LP的基本性質(zhì)：可行域存在時(shí)，必是凸多面體；可行解對應(yīng)于可行域中的點(diǎn)；最優(yōu)解存在時(shí)，必在可行域的頂點(diǎn)取得。LP的通常解法是單純形法。超平面組成的凸多面體等值線是超平面凸多面體的某個(gè)頂點(diǎn)2維n維第27頁，共67頁，2023年，2月20日，星期六282002.5.

Matlab中求解線性規(guī)劃的命令為:linprog,解決的線性規(guī)劃的標(biāo)準(zhǔn)格式為：

mincTx

x∈Rns.t.A·x<=b

Aeq·x=beqVLB≤x≤VUB

其中，A,b,c,x,Aeq,beq,VLB,VUB等均表示矩陣,特別b,c,x,beq,VLB,VUB為列矩陣。

MATLAB軟件求解第28頁，共67頁，2023年，2月20日，星期六292002.5.命令linprog的基本調(diào)用格式

如果沒有等式約束,就在相應(yīng)位置輸入空數(shù)組[],不等式約束和上下界也類似.最后的輸入項(xiàng)若沒有,則可省略.

x=linprog(c,A,b,Aeq,beq,VLB,VUB)等式約束決策變量上下界不等式約束目標(biāo)函數(shù)最優(yōu)解MATLAB軟件求解第29頁，共67頁，2023年，2月20日，星期六302002.5.還可以增加輸出

[x,fval,exitflag,output]=linprog(c,A,b,…）最優(yōu)值>0：收斂=0:到最大迭代次數(shù)時(shí)都還未收斂<0：infeasible或方法失敗迭代次數(shù)和算法類型MATLAB軟件求解第30頁，共67頁，2023年，2月20日，星期六312002.5.

看一個(gè)小例子

程序:c=-[5,3]’;A=[2,1;1,2];b=[40,50]’;L=[0,0];[x,fmin]=linprog(c,A,b,[],[],L);Pmax=-fminx1=x(1),x2=x(2)

輸出結(jié)果:

Pmax=110,x1=10,x2=20.

模型:

maxP=5X1+3X2s.t.2X1+X2≤40X1+2X2≤50X1≥0,X2≥0

MATLAB軟件求解第31頁，共67頁，2023年，2月20日，星期六322002.5.加工奶制品的生產(chǎn)計(jì)劃1桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時(shí)間480小時(shí)至多加工100公斤A1

制訂生產(chǎn)計(jì)劃，使每天獲利最大每天：范例第32頁，共67頁，2023年，2月20日，星期六x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應(yīng)勞動(dòng)時(shí)間加工能力決策變量目標(biāo)函數(shù)每天獲利約束條件非負(fù)約束1桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤加工奶制品的生產(chǎn)計(jì)劃第33頁，共67頁，2023年，2月20日，星期六342002.5.LINDO6.1程序

max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100endDORANGE(SENSITIVITY)ANALYSIS?No加工奶制品的生產(chǎn)計(jì)劃范例第34頁，共67頁，2023年，2月20日，星期六352002.5.

OBJECTIVEFUNCTIONVALUE1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元。范例第35頁，共67頁，2023年，2月20日，星期六362002.5.OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2原料無剩余時(shí)間無剩余加工能力剩余40三種資源“資源”剩余為零的約束為緊約束（有效約束）第36頁，共67頁，2023年，2月20日，星期六372002.5.OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量原料增加1單位,利潤增長48時(shí)間增加1單位,利潤增長2加工能力增長不影響利潤影子價(jià)格結(jié)果解釋第37頁，共67頁，2023年，2月20日，星期六382002.5.35元可買到1桶牛奶，要買嗎？35<48,應(yīng)該買！

聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？2元！加工奶制品的生產(chǎn)計(jì)劃范例第38頁，共67頁，2023年，2月20日，星期六392002.5.RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000DORANGE(SENSITIVITY)ANALYSIS?

Yes最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍(約束條件不變)x1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)A1獲利增加到30元/千克，應(yīng)否改變生產(chǎn)計(jì)劃不變！第39頁，共67頁，2023年，2月20日，星期六402002.5.RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價(jià)格有意義時(shí)約束右端的允許變化范圍(目標(biāo)函數(shù)不變)原料最多增加10時(shí)間最多增加5335元可買到1桶牛奶，每天最多買多少？最多買10桶!范例第40頁，共67頁，2023年，2月20日，星期六412002.5.背景聚焦重要事件重要人物第41頁，共67頁，2023年，2月20日，星期六422002.5.重要事件

在1762年,Lagrange解僅含等式約束的最優(yōu)化問題在1820年,Gauss利用消去法解線性方程組.在1945年,計(jì)算機(jī)出現(xiàn).在1947年,Dantzig發(fā)明單純形法.在1968年,FiaccoandMcCormick引進(jìn)內(nèi)點(diǎn)法.在1984年,Karmarkar提出了解線性規(guī)劃的有效算法.背景聚焦第42頁，共67頁，2023年，2月20日，星期六432002.5.重要人物

JohnVonNeumannGeorgeB.Dantzig

LeonidVitalyevichKantorovichNarendraKarmarkarHarryMaxMarkowitz背景聚焦第43頁，共67頁，2023年，2月20日，星期六442002.5.重要人物

JohnVonNeumann

約翰·馮·諾依曼(1903－1957),美藉匈牙利人.20世紀(jì)最杰出的數(shù)學(xué)家之一,被譽(yù)為”計(jì)算機(jī)之父”,”博弈論之父”.被認(rèn)為是數(shù)學(xué)規(guī)劃的三大創(chuàng)始人之一.背景聚焦第44頁，共67頁，2023年，2月20日，星期六452002.5.GeorgeB.DantzigGeorgeB.Dantzig(1914-2005),美國人,線性規(guī)劃單純形法的創(chuàng)始人,被譽(yù)為”線性規(guī)劃之父”.美國科學(xué)院三院院士,美國軍方數(shù)學(xué)顧問,教授.并以其名字設(shè)立Dantzig獎(jiǎng).數(shù)學(xué)規(guī)劃的三大創(chuàng)始人之一.發(fā)現(xiàn)算法時(shí)非常年輕,以至到日本時(shí),人們以為”線性規(guī)劃之父”是個(gè)老人,而對他無人問津.背景聚焦第45頁，共67頁，2023年，2月20日，星期六462002.5.LeonidVitalyevichKantorovich

Kantorovich(1912-1986)蘇聯(lián)人,著名數(shù)學(xué)家和經(jīng)濟(jì)學(xué)家,教授,年僅18歲獲博士學(xué)位.因在經(jīng)濟(jì)學(xué)上提出稀缺資源的最優(yōu)配置獲諾貝爾獎(jiǎng).線性規(guī)劃對偶理論的提出者,數(shù)學(xué)規(guī)劃的三大創(chuàng)始人之一.背景聚焦第46頁，共67頁，2023年，2月20日，星期六472002.5.背景聚焦第47頁，共67頁，2023年，2月20日，星期六482002.5.

在1990年,Markowitz因?yàn)榻鹑诮?jīng)濟(jì)學(xué)方面的貢獻(xiàn)和另外兩位學(xué)者分獲諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng).左邊的文字說明了他獲獎(jiǎng)的原因以及關(guān)于他的理論的簡介.背景聚焦第48頁，共67頁，2023年，2月20日，星期六492002.5.拓展

____優(yōu)化技術(shù)成功應(yīng)用的故事

美國電話電報(bào)公司網(wǎng)絡(luò)的快速恢復(fù)及優(yōu)化

大陸航空公司乘務(wù)組快速補(bǔ)救計(jì)劃香港國際貨柜碼頭裝卸的優(yōu)化決策第49頁，共67頁，2023年，2月20日，星期六502002.5.問題：甚至在九一一恐怖襲擊事件之前,美國大陸航空公司總裁就考慮到對大型航空公司,應(yīng)該制定一個(gè)危機(jī)計(jì)劃,以應(yīng)對緊急情況。突發(fā)事件,包括惡劣的天氣,飛機(jī)機(jī)械故障大陸航空公司乘務(wù)組快速補(bǔ)救計(jì)劃

乘務(wù)組缺班，航空公司會(huì)面臨航班中斷,航班延誤,取消等情況。由于乘務(wù)組未必能夠保證剩余的定期航班的正常飛行.航空公司必須盡快讓乘務(wù)組完成補(bǔ)償飛行計(jì)劃，并返回自己的原時(shí)刻表。這個(gè)決策要滿足成本最小、政府規(guī)定、合同約定以及對生活品質(zhì)的要求。解決這些問題需要專門的能進(jìn)行復(fù)雜建模并平衡多種因素的運(yùn)籌研究技術(shù)。拓展

____優(yōu)化技術(shù)成功應(yīng)用的故事

第50頁，共67頁，2023年，2月20日，星期六512002.5.

運(yùn)籌學(xué)解決方案：

大陸航空公司采用Caleb技術(shù),研發(fā)了CrewSolver決策支持系統(tǒng)，生成全局最優(yōu)或接近最優(yōu)的乘務(wù)組補(bǔ)救方案.大陸航空公司乘務(wù)組快速補(bǔ)救計(jì)劃

效果：大陸航空公司自實(shí)施此計(jì)劃以來，在每一次嚴(yán)重的突發(fā)事件中,都能實(shí)現(xiàn)乘務(wù)組快速補(bǔ)救,取得價(jià)值數(shù)百萬美元的效益。公司估計(jì),在2001年CrewSolver系統(tǒng)幫助它節(jié)省約了4000萬美元。由于該系統(tǒng),使美國航空業(yè)自2001年9月11日后開始復(fù)蘇,從那時(shí)起,五家航空公司已采用了類似的基于運(yùn)籌學(xué)的軟件用于突發(fā)事件后航班時(shí)刻表、飛行員安排等的補(bǔ)救計(jì)劃。拓展

____優(yōu)化技術(shù)成功應(yīng)用的故事

第51頁，共67頁，2023年，2月20日，星期六522002.5.背后的故事：

1995年，美國大陸航空公司邀請于剛教授為他們編寫決策支持系統(tǒng)。于剛領(lǐng)導(dǎo)他的研究人員克服了重重困難，取得了一個(gè)又一個(gè)的突破性成果，為大陸航空公司編寫了三個(gè)決策支持系

統(tǒng)，解決了當(dāng)航空系統(tǒng)遭遇惡劣天氣、飛機(jī)故障等干擾后，飛機(jī)航班的最優(yōu)恢復(fù)問題、機(jī)組人員的調(diào)度問題和機(jī)組人員的計(jì)劃、培訓(xùn)、休假等總體決策的最優(yōu)方案。2001年9月11日，震驚世界的“9.11”恐怖事件不幸發(fā)生了。這次事件給美國航空業(yè)帶來了災(zāi)難性的打擊。但是，就是通過這次突發(fā)的災(zāi)難性事件，于剛的實(shí)時(shí)決策系統(tǒng)的優(yōu)越性得到了充分體現(xiàn)。大陸航空公司由于采用了他的優(yōu)化實(shí)時(shí)決策系統(tǒng)，比其他航空公司提前兩天開始正常運(yùn)營，為公司挽回3000多萬美元的損失。由于有了于剛的完備的決策支持系統(tǒng)，大陸航空公司在整個(gè)“9.11”事件中避免了上億美元的損失。拓展

____優(yōu)化技術(shù)成功應(yīng)用的故事

第52頁，共67頁，2023年，2月20日，星期六532002.5.大陸航空公司乘務(wù)組快速補(bǔ)救計(jì)劃

該案例使旅美華裔著名運(yùn)籌學(xué)家于剛教授榮獲2002年度運(yùn)籌與管理科學(xué)應(yīng)用FranzEdelman獎(jiǎng)，F(xiàn)ranzEdelman獎(jiǎng)是由世界著名的運(yùn)籌和管理科學(xué)家FranzEdelman于1971年創(chuàng)立的。它作為運(yùn)籌和管理科學(xué)在國際上的一項(xiàng)最高榮譽(yù)，一年一度地頒發(fā)給在這一領(lǐng)域取得了最突出成就的科學(xué)家和企業(yè)家。拓展

____優(yōu)化技術(shù)成功應(yīng)用的故事

第53頁，共67頁，2023年，2月20日，星期六542002.5.問題：AT&T是一個(gè)全球性電信公司，提供多種服務(wù),如遠(yuǎn)程語音數(shù)據(jù)、視頻、無線通訊、衛(wèi)星及互聯(lián)網(wǎng)服務(wù)。AT&T面對的問題是防止網(wǎng)絡(luò)出錯(cuò),并提供應(yīng)對失誤發(fā)生時(shí)的快速反應(yīng)。AT&T在發(fā)生網(wǎng)絡(luò)

故障時(shí)，要快速改換通訊通道,這要求網(wǎng)絡(luò)有足夠的恢復(fù)能力來傳送相應(yīng)需求。這個(gè)問題很重要,因?yàn)榉?wù)的失敗,直接影響到公司的核心服務(wù)和客戶忠誠度。解決它需要運(yùn)籌學(xué)研究專門技術(shù),因?yàn)檫@個(gè)問題涉及到全系統(tǒng)而運(yùn)籌學(xué)有強(qiáng)大的能力來處理眾多的參數(shù)。AT&T網(wǎng)絡(luò)的快速恢復(fù)及優(yōu)化拓展

____優(yōu)化技術(shù)成功應(yīng)用的故事

第54頁，共67頁，2023年，2月20日，星期六552002.5.運(yùn)籌學(xué)解決方案：

一個(gè)由運(yùn)籌學(xué)專家、網(wǎng)絡(luò)設(shè)計(jì)師、管理者組成的AT&T團(tuán)隊(duì)提出了一種方法，在任何單一鏈接出現(xiàn)故障時(shí)，通過確定修復(fù)能力要求的適當(dāng)?shù)臄?shù)量和位置,來恢復(fù)需求。該辦法使網(wǎng)絡(luò)恢復(fù)成本最小化,并產(chǎn)生新的恢復(fù)路徑。價(jià)值：

在約10個(gè)月內(nèi)，AT&T團(tuán)隊(duì)以此方法為工具,優(yōu)化恢復(fù)能力的配置.這一工具被擴(kuò)展到交換中心出現(xiàn)故障時(shí)的恢復(fù)，并用于重新優(yōu)化整個(gè)修復(fù)網(wǎng)絡(luò)。該項(xiàng)目有助于AT&T實(shí)現(xiàn)高質(zhì)量的服務(wù),同時(shí)節(jié)省寶貴的資源,節(jié)約成本數(shù)億美元，增加了收入。AT&T網(wǎng)絡(luò)的快速恢復(fù)及優(yōu)化拓展

____優(yōu)化技術(shù)成功應(yīng)用的故事

第55頁，共67頁，2023年，2月20日，星期六562002.5.問題：在90年代,擁有世界上最繁忙的港口貨物處理設(shè)施的香港國際貨柜碼頭（HIT）,在更有效率的華南沿海新興港口的沖擊下，面臨著丟失市場份額的嚴(yán)重威脅。

香港地區(qū)蓬勃的出口制造業(yè)為主的經(jīng)濟(jì),加上大幅度上升的進(jìn)口貨物，港口要處理每一天成千上萬通過碼頭的海運(yùn)集裝箱貨物顯得捉襟見肘。香港國際貨柜碼頭存在的嚴(yán)重及持續(xù)的物理空間上的制約，并不是新的港口競爭的問題,它的原因在于在存儲(chǔ)和調(diào)度航運(yùn)貨柜中的低效率.運(yùn)籌學(xué)解決方案：在1995，HIT認(rèn)識(shí)到必須采用一個(gè)新的,基于運(yùn)籌學(xué)的決策支持工具,大大提高碼頭操作工作效率,,以容納和處理每星期約125停靠港口船只的貨物。香港國際貨柜碼頭裝卸的優(yōu)化決策拓展

____優(yōu)化技術(shù)成功應(yīng)用的故事

第56頁，共67頁，2023年，2月20日，星期六572002.5.

機(jī)來卸貨,一個(gè)起重機(jī)需要安排多少車來接貨，何時(shí)安排卡車依次搬運(yùn)走船上的集裝箱出碼頭.使用定制算法,即智能業(yè)務(wù)規(guī)則，3P對基本的終端業(yè)務(wù)提供優(yōu)化決策支持.價(jià)值：HIT應(yīng)用3P使得其集裝箱處理能力在不增加人員,設(shè)備或地產(chǎn)情形下，增加50%。3P的基本收益,從港口客戶的角度而言,是體現(xiàn)在船舶周轉(zhuǎn)時(shí)間和裝卸費(fèi)用上。3P系統(tǒng)減少了30%的船舶周轉(zhuǎn)時(shí)間,降低了35%每個(gè)集裝箱的平均處理成本.3P也有一定的環(huán)境效益:更有效率的碼頭作業(yè)減少了一半在港口設(shè)施中利用柴油車往來搬運(yùn)集裝箱的污染。香港國際貨柜碼頭裝卸的優(yōu)化決策運(yùn)籌學(xué)解決方案：尤其是“3P”(即生產(chǎn)力+程序),將有助改善及加速基本決策，如何規(guī)劃在院子里的集裝箱貨車路徑,抵港集裝箱應(yīng)在設(shè)施那里貯存，每艘船舶應(yīng)該用多少起重拓展

____優(yōu)化技術(shù)成功應(yīng)用的故事

第57頁，共67頁，2023年，2月20日，星期六582002.5.獎(jiǎng)項(xiàng)：香港國際貨柜碼頭在發(fā)展及應(yīng)用創(chuàng)新科技方面精益求精，多次獲得業(yè)界大獎(jiǎng)。2006年11月5日，憑借自行開發(fā)的「新一代碼頭管理系統(tǒng)」（NextGenerationTerminalManagementSystem，nGen），（3p的前身）香港國際貨柜碼頭成功擊敗十個(gè)優(yōu)秀競爭對手，奪得了「亞太資訊及通訊科技大獎(jiǎng)2006」(APICTA)──工業(yè)應(yīng)用項(xiàng)目大獎(jiǎng)；另外，在「2006香港資訊及通訊科技獎(jiǎng)」中，香港國際貨柜碼頭再接再厲，獲頒「電子商務(wù)大獎(jiǎng)」；其「新一代碼頭管理系統(tǒng)」獲得了電子商務(wù)（應(yīng)用）組別的金獎(jiǎng)。

葉承智（左）從唐英年手中接過電子商務(wù)大獎(jiǎng)拓展

____優(yōu)化技術(shù)成功應(yīng)用的故事

第58頁，共67頁，2023年，2月20日，星期六592002.5.問題：作為世界上最大的包裹公司，聯(lián)合包裹服務(wù)公司（UPS）依靠高效率的規(guī)劃和樞紐航線與支線航線網(wǎng)絡(luò)的運(yùn)作，包括七個(gè)樞紐中心和聯(lián)合包裹服務(wù)公司優(yōu)化空中與地面運(yùn)輸計(jì)劃

美國國內(nèi)近100個(gè)機(jī)場，每晚運(yùn)送次日到達(dá)戶主的物品超過100萬個(gè)。要使這樣一個(gè)龐大的系統(tǒng)具有更大的效率是一個(gè)挑戰(zhàn)。目前已知的求解大型網(wǎng)絡(luò)設(shè)計(jì)問題的算法對規(guī)劃UPS的航空網(wǎng)絡(luò)是不夠的,主要的障礙是復(fù)雜而龐大的空中運(yùn)輸,涉及超過17000從始點(diǎn)到終點(diǎn)的流量，9種不同類型超過160架的飛機(jī)。解決這些問題需要在大規(guī)模優(yōu)化、整數(shù)規(guī)劃等運(yùn)籌學(xué)研究專門技術(shù)。拓展

____優(yōu)化技術(shù)成功應(yīng)用的故事

第59頁，共67頁，2023年，2月20日，星期六602002.5.聯(lián)合包裹服務(wù)公司優(yōu)化空中與地面運(yùn)輸計(jì)劃運(yùn)籌學(xué)解決方案：UPS航空工作組與美國麻省理工學(xué)院的專家在運(yùn)輸系統(tǒng)方面進(jìn)行了合作,聯(lián)合研究和開發(fā)出基于最優(yōu)化設(shè)計(jì)的UPS航空網(wǎng)絡(luò)計(jì)劃系統(tǒng)。為確保隔夜交貨,此方案能同時(shí)確定具有最小成本的飛機(jī)航線,車隊(duì)作業(yè)計(jì)劃以及配套的路線。項(xiàng)目組建立的整數(shù)規(guī)劃模型,與常規(guī)網(wǎng)絡(luò)設(shè)計(jì)類似,但卻能極大改善基于線性規(guī)劃的解的范圍.此方案對原有規(guī)劃要解決的實(shí)際問題的求解時(shí)間,一般不超過6小時(shí),在許多情況下,不超過一小時(shí),大幅度節(jié)省了時(shí)間。價(jià)值:

UPS規(guī)劃者現(xiàn)在利用此系統(tǒng)產(chǎn)生的方案和見解來實(shí)現(xiàn)計(jì)劃的優(yōu)化。UPS的管理者確信,此系統(tǒng)及伴隨的業(yè)務(wù)變化，已給公司節(jié)省超過870萬美元,并預(yù)計(jì)在未來十年可再節(jié)省1.89億美元。此方案帶來的其他的好處包括：減少了網(wǎng)絡(luò)規(guī)劃時(shí)間,減少了高峰和非高峰期的成本,減少了飛機(jī)隊(duì)需求量并改進(jìn)了計(jì)劃。拓展

____優(yōu)化技術(shù)成功應(yīng)用的故事

第60頁，共67頁，2023年，2月20日，星期六612002.5.問題：醫(yī)療保健行業(yè)經(jīng)濟(jì)的急劇變化使得克薩斯兒童醫(yī)院面臨著風(fēng)險(xiǎn)，成本不斷上漲的醫(yī)療服務(wù)和設(shè)備,來自私人保險(xiǎn)和公共醫(yī)療融資方案,如得克薩斯兒童醫(yī)院最小化金融風(fēng)險(xiǎn)

醫(yī)療補(bǔ)助對吸納這些較高的成本的阻力，使得這個(gè)全國最大的兒科醫(yī)療保健機(jī)構(gòu)面臨艱難決策。此外,新合同償還結(jié)構(gòu),其中包括“診斷相關(guān)組”

(DRG)和“固定門診費(fèi)用”(預(yù)付)的安排,可能會(huì)轉(zhuǎn)移巨額財(cái)務(wù)風(fēng)險(xiǎn)到得克薩斯兒童醫(yī)院,因此醫(yī)院要有合同談判的更有效方法。運(yùn)籌學(xué)解決方案：與航空公司,酒店或租車公司不同，得克薩斯兒童醫(yī)院不追求"利潤最大化",它的使命是拯救生命并培訓(xùn)醫(yī)師。與生存于其他產(chǎn)業(yè)的公司一樣,得克薩斯兒童醫(yī)院得益于一些有力的基于運(yùn)籌技術(shù)的收入管理分析支持系統(tǒng),來處理其獨(dú)特的金融情況。拓展

____優(yōu)化技術(shù)成功應(yīng)用的故事

第61頁，共