運(yùn)籌與優(yōu)化 (四)

1、收集數(shù)學(xué)規(guī)劃實(shí)用軟件Maple Mosek Xpress 1st opt SAS Mathematica Gurobi CPLEX GLPK，網(wǎng)絡(luò)優(yōu)化模型，問題：網(wǎng)絡(luò)最小成本流問題，網(wǎng)絡(luò)最大流問題，最短路徑問題，運(yùn)輸問題的重要性：運(yùn)輸是物流系統(tǒng)中不可缺少的重要環(huán)節(jié)，物流系統(tǒng)有效節(jié)約的來(lái)源之一是合理的物料運(yùn)輸，即物料應(yīng)以最佳方案運(yùn)輸。許多實(shí)際問題可以轉(zhuǎn)化為運(yùn)輸問題模型。運(yùn)輸問題案例1:材料調(diào)度問題、線性規(guī)劃模型、決策變量、其他運(yùn)輸問題案例、能源運(yùn)輸問題：電力調(diào)度問題由于一個(gè)地區(qū)或一個(gè)工廠中有幾個(gè)能源供應(yīng)基地(發(fā)電廠)，如何有效和優(yōu)化地將這些能源分配給各個(gè)用能單位，從而最大限度地發(fā)揮其自身的生產(chǎn)潛

2、力和功能，已逐漸成為企業(yè)非常重視的一個(gè)關(guān)鍵環(huán)節(jié)。人員分配問題，人員分配問題，在一個(gè)鋼鐵公司的發(fā)電廠的供電車間中有13個(gè)變電站，它們分布在公司的工廠區(qū)域中幾十英里?？偣灿?04名工人需要通勤，分散在城市各處。每天都有許多工人去上班，或離家，或甲乙雙方之間的對(duì)流.不僅浪費(fèi)了寶貴的時(shí)間，增加了負(fù)擔(dān)，還加劇了交通堵塞，工廠不得不為員工花費(fèi)更多的通勤費(fèi)用。如果這個(gè)問題能得到很好的解決，將對(duì)國(guó)家、單位和個(gè)人都有好處。根據(jù)運(yùn)輸問題的原理，工廠提出了新的員工分配方案，解決了員工就近工作的問題。對(duì)員工分配問題建模的思想，按以下步驟建立模型(1)起點(diǎn)及其能力約束：根據(jù)就近旅游的原則，將分散的員工住所合并為十八個(gè)點(diǎn)

3、，并逐點(diǎn)計(jì)算每個(gè)住所的員工人數(shù)。因此，獲得了第I住宅ai(i=1，218)中的雇員數(shù)量，并建立了受住宅中雇員數(shù)量約束的條件方程。(2)接收點(diǎn)和容量限制：根據(jù)工作結(jié)束和到達(dá)情況，13個(gè)變電站將合并為8個(gè)工作場(chǎng)所，每個(gè)工作場(chǎng)所所需的員工人數(shù)將根據(jù)配額確定。因此，獲得了第j工作場(chǎng)所所需的員工人數(shù)bj(j=1，28)，并建立了工作場(chǎng)所員工定額所同意的條件方程。(3)運(yùn)費(fèi)價(jià)格：逐個(gè)計(jì)算單人從第六住所到第六工作地點(diǎn)的每日通勤費(fèi)用。(4)決策變量：設(shè)xij為第二居住地第三工作場(chǎng)所應(yīng)去工作的人數(shù)。(5)優(yōu)化目標(biāo)：總通勤成本最小。食品公司銷售的主要產(chǎn)品之一是糖果。下設(shè)三個(gè)加工廠，日生產(chǎn)能力分別為：-125噸、S

4、210噸和S315噸。計(jì)劃將這些糖果運(yùn)送到四個(gè)銷售點(diǎn)，日銷量分別為d113噸、d221噸、d39噸和d47噸。貨運(yùn)時(shí)間表如下。如何最小化總運(yùn)費(fèi)？運(yùn)輸問題案例2:貨物運(yùn)輸問題，表1:單價(jià)表，商店，加工廠，2，3，2，1，3，4，1，運(yùn)輸問題網(wǎng)絡(luò)圖，S2=10，S3=15，D1=13，D2運(yùn)輸問題的數(shù)學(xué)規(guī)劃模型是線性規(guī)劃，運(yùn)輸問題的線性規(guī)劃模型，供應(yīng)地的約束，需求地的約束， 運(yùn)輸問題的關(guān)鍵點(diǎn)：出發(fā)地點(diǎn)(出發(fā)地點(diǎn))及其容量約束接收地點(diǎn)(接收地點(diǎn))及其容量約束知道從每個(gè)出發(fā)地點(diǎn)到不同接收地點(diǎn)的運(yùn)輸?shù)膬r(jià)格決策變量(運(yùn)輸方案):從每個(gè)出發(fā)地點(diǎn)到每個(gè)接收地點(diǎn)的運(yùn)輸量。 目標(biāo)：總運(yùn)輸成本最小，運(yùn)輸問題是一個(gè)特

5、殊的最小成本流問題。引入虛擬出發(fā)點(diǎn)和虛擬收貨點(diǎn)后，多點(diǎn)多點(diǎn)運(yùn)輸問題可以轉(zhuǎn)化為單點(diǎn)和單點(diǎn)的最小成本流問題。，運(yùn)輸問題的最小成本流網(wǎng)絡(luò)圖，2，3，2，1，3，4，1，S2=10，S3=15，D1=13，D2=21，D3=9，D4=7，S125，供應(yīng)地B4=3，B3=5，b5=-6，B6=-5，B1=5，c24=5，c46=1，c13=3，c35=2，c56=4，c34=4，c12=6， cij單位流程成本從V1和V2兩個(gè)郵局發(fā)送到T1、T2和T3的郵件需要通過(guò)V3和V4傳輸，其中“o”中的數(shù)字是該郵局的最大處理能力，弧線上標(biāo)記的重量是該線路的最大運(yùn)輸能力。 現(xiàn)在我們要計(jì)算這個(gè)郵政網(wǎng)絡(luò)的最大傳輸容量

6、，并對(duì)結(jié)果進(jìn)行分析，以改善薄弱環(huán)節(jié)，提高這個(gè)網(wǎng)絡(luò)的最大傳輸容量，如圖1所示。從V1和V2兩個(gè)郵局發(fā)往T1、T2和T3的郵件需要通過(guò)V3和V4轉(zhuǎn)送，其中“o”表示該郵局的最大處理能力，弧線上標(biāo)注的重量表示該線路的最大運(yùn)輸能力?，F(xiàn)在我們要計(jì)算這個(gè)郵政網(wǎng)絡(luò)的最大傳輸容量，并對(duì)結(jié)果進(jìn)行分析，以改善薄弱環(huán)節(jié)，提高這個(gè)網(wǎng)絡(luò)的最大傳輸容量，如圖1所示。該問題屬于具有多個(gè)接收點(diǎn)和多個(gè)發(fā)送點(diǎn)的網(wǎng)絡(luò)最大流問題。首先，問題通過(guò)虛擬起點(diǎn)Vs和Vt轉(zhuǎn)化為接收點(diǎn)和接收點(diǎn)，如圖2所示：最大流量問題的其他情況，高速公路網(wǎng)絡(luò)中交通流量的最大化，供電網(wǎng)絡(luò)中電流流量的最大化，物流配送網(wǎng)絡(luò)中交通流量的最大化，互聯(lián)網(wǎng)信息流的最大化，最

7、短路徑問題，2，3，7，1，8，4，5，6，10，5，2，7，5，9，3，4，6，8，2，找到從1到8的最短路徑。最短路徑問題案例：船舶航線問題，船舶的最佳航線選擇問題可以描述為：一艘船舶從出發(fā)港S出發(fā)到目的港E，船舶在S和E之間航行的路線有很多，這些路線和船舶在路線上稱之為港口。那么，從起始端口S到目的端口E，哪條路由最好？最短路徑問題案例：郵局(商店、基站)選址問題，它是郵政通信網(wǎng)絡(luò)的重要組成部分，是聯(lián)系用戶和郵政企業(yè)的樞紐。它的設(shè)置是直接影響郵件能否在網(wǎng)絡(luò)中順利進(jìn)出和運(yùn)行的重要因素之一。作為一個(gè)外部“窗口”，它關(guān)系到郵政行業(yè)的聲譽(yù)，是用戶使用郵政服務(wù)的物質(zhì)和技術(shù)條件，直接影響到社會(huì)和企業(yè)

8、的效益。因此，其優(yōu)化設(shè)置已成為郵政通信網(wǎng)絡(luò)合理規(guī)劃的重要組成部分?，F(xiàn)有區(qū)域(可分為六個(gè)服務(wù)區(qū)域)。應(yīng)在六個(gè)服務(wù)區(qū)中心中的一個(gè)設(shè)立郵局，郵局的服務(wù)區(qū)是六個(gè)區(qū)。根據(jù)實(shí)際調(diào)查分析，發(fā)現(xiàn)該地區(qū)交通地理?xiàng)l件差異不大。為了方便這六個(gè)服務(wù)區(qū)域的用戶使用郵件，從圖論的角度來(lái)看，建立辦公室時(shí)主要考慮的是使這六個(gè)區(qū)域的用戶使用郵件的最大行程最短。這將問題轉(zhuǎn)化為從每個(gè)服務(wù)區(qū)中心到郵局的最短路徑。表1六個(gè)區(qū)域的中心距離和可達(dá)性表單位：公里，旅行商問題：TSP，城市數(shù)：100，旅行商問題是一個(gè)特殊的最短路徑問題，旅行商問題：“旅行商問題”通常被稱為“旅行商問題”，它指的是如何找出當(dāng)一個(gè)推銷員想訪問多個(gè)地方。雖然規(guī)則很簡(jiǎn)單，但是當(dāng)位置數(shù)量增加時(shí)，解決它們就變得非常復(fù)雜了。許多實(shí)際問題可以轉(zhuǎn)化為TSP問題：物流配送問題：一個(gè)物流配送公司想沿著最短的路線運(yùn)送來(lái)自N個(gè)客戶的所有訂單。如何確定最短路線？TSP問題是一個(gè)NP完全問題。精確算法可以得到最優(yōu)解，但它只能解決中小型問題。分枝定界算法動(dòng)態(tài)規(guī)劃啟發(fā)式算法能夠以放棄最優(yōu)解為代價(jià)解決大規(guī)模問題。有許多種算法。課后作業(yè)。首先，找到一個(gè)可以轉(zhuǎn)化為運(yùn)輸問題的實(shí)際案例，并將其轉(zhuǎn)化為運(yùn)輸問題模型(即給出運(yùn)輸問題的幾個(gè)關(guān)鍵點(diǎn))