數(shù)據(jù)、模型與決策課程解題思路

1、數(shù)據(jù)、模型與決策課程解題思路一、不確定性決策收益矩陣的格式 橫表頭為市場情況，列表頭為方案；樂觀準(zhǔn)則 最大最大：按行找出各方案中最大收益，選擇最大收益最大的方案；悲觀準(zhǔn)則 最大最?。喊葱姓页龈鞣桨钢凶钚∈找妫x擇最小收益最大的方案；等可能準(zhǔn)則 最大平均：按行計(jì)算出各方案的平均收益，選擇平均收益最大的方案；后悔值準(zhǔn)則 最小最大后悔：按列找出各種市場情況下最大收益值，用最大收益值減去本列的各個(gè)收益得其后悔值，按行找出各方案的最大后悔值，選擇后悔值最小的方案；樂觀系數(shù)準(zhǔn)則 最大加權(quán)平均：按行找出各方案中最大和最小收益值，以“樂觀系數(shù)”和“1樂觀系數(shù)”為權(quán)計(jì)算最大和最小收益值的加權(quán)平均值，選擇加權(quán)平均

2、值最大的方案。以課堂作業(yè)1舉例如下：市場需求量樂觀準(zhǔn)則悲觀準(zhǔn)則等可能準(zhǔn)則樂觀系數(shù)準(zhǔn)則大中小失敗最大最大最大最小最大平均最大加權(quán)平均擴(kuò)建502510-1550-1517.530.5新建7030-10-4070-4012.537外包3015-5-1030-107.518市場需求量后悔值準(zhǔn)則大中小失敗后悔值最小最大擴(kuò)建502510-152050520新建7030-10-4000203030外包3015-5-10401515040二、規(guī)劃模型的標(biāo)準(zhǔn)化解題思路：標(biāo)準(zhǔn)形式的約束條件有三個(gè)要件，一是常數(shù)項(xiàng)非負(fù)；二是只能有等式；三是定義域非負(fù)。依照上述要件，分四步操作：A、推斷常數(shù)項(xiàng)是否非負(fù)，如有負(fù)值則兩邊同

3、乘（-1），并相應(yīng)改變不等號(hào)方向；B、推斷是否有不等式，如有則設(shè)松弛或剩余變量xi 0，大于號(hào)減、小于號(hào)加xi變等式；C、推斷各變量的定義域是否非負(fù)，如為負(fù)值，則設(shè)xj=（-xi） 0，代入模型； 如為 - xk ，則設(shè)xk =（xmxn）， xm、xn 0，代入模型；D、整理變量下標(biāo)后，得到標(biāo)準(zhǔn)形式。三、線性規(guī)劃模型的解法及敏感性分析 A、圖解步驟如下：1、以x1為橫軸、x2為縱軸建立直角坐標(biāo)系，標(biāo)出各約束條件和目標(biāo)函數(shù)的直線；2、在第一象限找出可行域；3、目測目標(biāo)函數(shù)平移后最可能與可行域的哪個(gè)頂點(diǎn)相切，則該點(diǎn)為最優(yōu)解點(diǎn)；4、解方程得到該點(diǎn)坐標(biāo)，即得最優(yōu)解，代入目標(biāo)函數(shù)得最優(yōu)值。5、小技巧：

4、(1)作圖時(shí)，對(duì)約束條件，可分不令x1和x2為零，得到其與縱軸和橫軸的交點(diǎn)，連接即可；對(duì)目標(biāo)函數(shù)，令x1為一專門值，得出x2，再與原點(diǎn)相連，可得函數(shù)直線，再沿橫軸平移到合適位置即；(2)各條直線斜率絕對(duì)值越大的，越接近垂直于x1軸；(3)確定可行域時(shí)，要考慮坐標(biāo)軸和原點(diǎn)；(4)目測推斷最優(yōu)點(diǎn)不易時(shí)，可將相鄰數(shù)點(diǎn)的坐標(biāo)解出代入目標(biāo)函數(shù)進(jìn)行比較。B、松弛變量和剩余變量1、約束條件為“”的存在松弛變量，為“”的存在剩余變量； 2、將最優(yōu)解代入各約束條件即得各自的松弛或剩余變量； 3、構(gòu)成最優(yōu)解的約束條件的松弛或剩余變量為零。C、對(duì)偶價(jià)格 1、不構(gòu)成最優(yōu)解的約束條件的對(duì)偶價(jià)格為零； 2、構(gòu)成最優(yōu)解的約

5、束條件存在對(duì)偶價(jià)格，求解時(shí)令其中一個(gè)約束條件的常數(shù)項(xiàng)增加1，另一個(gè)約束條件不變，重新解出交點(diǎn)坐標(biāo)，代回目標(biāo)函數(shù)計(jì)算目標(biāo)值，再與原最優(yōu)值相差即得； 3、對(duì)偶價(jià)格的討論均在各約束條件常數(shù)項(xiàng)的上、下限范圍內(nèi)進(jìn)行，超范圍時(shí)對(duì)偶價(jià)格可能發(fā)生變化； 4、已知對(duì)偶價(jià)格和最優(yōu)值求常數(shù)項(xiàng)變化時(shí)，目標(biāo)函數(shù)求Max時(shí)，增加目標(biāo)值的，常數(shù)項(xiàng)同向變化，即增大；求Min時(shí)，增加目標(biāo)值的，常數(shù)項(xiàng)反向變化，即減少；反之亦然。D 、目標(biāo)函數(shù)系數(shù)上、下限 1、目標(biāo)函數(shù)系數(shù)的變化，在圖解時(shí)可視為目標(biāo)函數(shù)直線斜率的變動(dòng)，即該直線以最優(yōu)解點(diǎn)為支點(diǎn)旋轉(zhuǎn)；其取值范圍為最優(yōu)解不變的范圍，即不突破構(gòu)成最優(yōu)解的兩條直線斜率kmin 和kmax的

6、范圍。 2、求解時(shí)，將目標(biāo)函數(shù)變換為x2=(-c1/c2)*x1的形式，通過kmin (-c1/c2) kmax，分不代入c1或c2，可得c2或c1的上、下限。E、約束條件常數(shù)項(xiàng)的上、下限 1、約束條件常數(shù)項(xiàng)的變化，在圖解時(shí)可視為約束條件直線在縱軸上截距的變動(dòng)，即該直線沿橫軸平移，可不能與另兩條約束條件直線交點(diǎn)相交的范圍，也確實(shí)是可不能改變可行域的結(jié)構(gòu)、可不能減少可行域邊數(shù)（坐標(biāo)軸不算）的范圍；其取值范圍為對(duì)偶價(jià)格不變的范圍，但有可能會(huì)改變最優(yōu)解和最優(yōu)值。 2、求解時(shí)，找到該約束條件相鄰的兩個(gè)可行域的頂點(diǎn)坐標(biāo)(xa, xb)，依照x2 - xb = k*( x1 - xa) 點(diǎn)斜式方程，分不求

7、出約束條件平移至該兩個(gè)頂點(diǎn)的在橫軸上的截距、即變化后的常數(shù)項(xiàng)上、下限。F、百分之一百法則 1、增加率和減少率之和不超過100%； 2、增加（減少）率增加（減少）值 / 同意增加（減少）值； 增減值以當(dāng)前值為基數(shù)計(jì)算，同意增減值以當(dāng)前值為基數(shù)、各值取值范圍的上、下限計(jì)算； 3、多個(gè)目標(biāo)函數(shù)系數(shù)變動(dòng)時(shí)，其意義為最優(yōu)解不變； 多個(gè)約束條件常數(shù)項(xiàng)變動(dòng)時(shí)，其意義為對(duì)偶價(jià)格不變； 不適用目標(biāo)函數(shù)系數(shù)和約束條件常數(shù)項(xiàng)同時(shí)變動(dòng)的情況，也不適用于相關(guān)系數(shù)和常數(shù)項(xiàng)同步增減（即有增無減、或在減無增）的情況。G、相差值 1、最優(yōu)解中為零的變量，其系數(shù)變化到不為零時(shí)的差值； 2、最優(yōu)解中不為零的變量，其相差值必為零；

8、3、目標(biāo)函數(shù)求Max時(shí)，其相差值為其上限值減去當(dāng)前值，且該系數(shù)無下限； 目標(biāo)函數(shù)求Min時(shí)，其相差值為其下限值減去當(dāng)前值，且該系數(shù)無上限；四、線性規(guī)劃模型的建立 A、問題的實(shí)質(zhì) 在某些資源限制下，求利潤最大或成本最小。這些資源限制包括資金、物料、工時(shí)的最高或最低要求等，關(guān)鍵是找到合適的變量，將目標(biāo)和限制聯(lián)系起來。B、人力資源問題 按循環(huán)周期計(jì)算當(dāng)天（單位時(shí)刻）內(nèi)上班或休息的人數(shù)并與限制條件相比較 xi為每天（單位時(shí)刻）上班或休息的人數(shù)； Min 配備的總?cè)藬?shù)、上班或休息的人員（成本最低） S.T. 滿足每天（單位時(shí)刻）上班或休息人數(shù)的限制 xi 0C、生產(chǎn)打算問題 按不同生產(chǎn)車間或工序生產(chǎn)產(chǎn)品

9、的件數(shù)及其所需的物料、設(shè)備或工時(shí)與限制相比較 xi為每個(gè)車間或工序生產(chǎn)產(chǎn)品的件數(shù)； Max 利潤 或 Min 成本 S.T. 1、滿足物料、設(shè)備或工時(shí)的限制 2、各工序生產(chǎn)的產(chǎn)品數(shù)量應(yīng)相等 xi 0D、套裁下料問題 列出一根整料所有可行的裁料方案，不同裁料方案運(yùn)用的次數(shù)及其所得不同規(guī)格工件的總數(shù)與總需求量相比較 xi為每種裁料方案的運(yùn)用次數(shù)，最終整料的使用量為xi之和； Min 裁料方案運(yùn)用次數(shù)之和； S.T. 各種裁料方案裁得的不同規(guī)格的工件必須許多于其總需求量； xi 0E、配料問題 每種產(chǎn)品中各原料的比例應(yīng)滿足要求，且各原料的總使用量不得超過限制 xi為每種產(chǎn)品中各原料的使用量； Max

10、 利潤 或 Min 成本； S.T. 1、每種產(chǎn)品中各原料的比例； 2、各原料的使用量少于限制量； xi 0F、連續(xù)投資問題 依照項(xiàng)目回收期不同列出各年各種方案可能的投資表，總收益為各項(xiàng)目最后一期投資的和，各期的投資應(yīng)等于期初資金（也確實(shí)是上一期投資的收入） xi為每項(xiàng)目在各年的投資額； Max 總收益 或 Min 總風(fēng)險(xiǎn)； S.T. 1、各期的投資等于期初資金（也確實(shí)是上一期投資的收入）； 2、滿足各期投資限制 xi 0五、運(yùn)輸模型A、產(chǎn)銷表的差不多形式 銷地產(chǎn)地銷地1銷地2銷地產(chǎn)量產(chǎn)地1產(chǎn)地2產(chǎn)地銷量 總產(chǎn)量總銷量B、差不多運(yùn)輸問題的線性規(guī)劃求解令各產(chǎn)地運(yùn)往各銷地的物資量為xi，則：Min

11、 運(yùn)費(fèi)（xi乘以運(yùn)價(jià)）S.T. 每個(gè)產(chǎn)地的產(chǎn)量等于運(yùn)往各銷地的物資量 每個(gè)銷地的銷量等于運(yùn)往該地的物資量xi 0C、產(chǎn)銷不平衡問題 轉(zhuǎn)化為產(chǎn)銷平衡問題產(chǎn)大于銷時(shí)，增加虛擬銷地，即增加一列，該列的運(yùn)費(fèi)為“0”，銷量為差額；銷大于產(chǎn)時(shí)，增加虛擬產(chǎn)地，即增加一行，該行的運(yùn)費(fèi)為“0”，產(chǎn)量為差額；D、有條件的產(chǎn)銷不平衡問題 轉(zhuǎn)化為產(chǎn)銷平衡問題當(dāng)銷大于產(chǎn)，且部分銷地的產(chǎn)銷量可在一定范圍內(nèi)變化時(shí)：1、將該銷地的銷售拆分為兩地，即一列變兩列，其中一列的銷量為該銷地的基數(shù)，另一列的銷量為其可變數(shù)，各產(chǎn)地至該兩個(gè)銷地的運(yùn)費(fèi)不變；2、增加虛擬產(chǎn)地，即增加一行，該行中到基數(shù)銷地的運(yùn)費(fèi)為M （意為足夠大），到可變數(shù)銷

12、地的運(yùn)費(fèi)為“0”，該行的產(chǎn)量為產(chǎn)銷的差額；3、當(dāng)存在銷量不限的銷地時(shí)，各真實(shí)產(chǎn)地到該銷地的運(yùn)費(fèi)為M，虛擬產(chǎn)地到該銷地的運(yùn)費(fèi)為“0”，虛擬產(chǎn)地的產(chǎn)量為各銷地可變數(shù)之和。E、生產(chǎn)存儲(chǔ)問題 將各期視為產(chǎn)銷地，各期的生產(chǎn)量和交貨量分不視為產(chǎn)量和銷費(fèi)，各期生產(chǎn)的產(chǎn)品其生產(chǎn)成本與至交貨期的存儲(chǔ)成本之和視為運(yùn)費(fèi)，其中按時(shí)刻順序不存在交貨的運(yùn)費(fèi)為M，轉(zhuǎn)化運(yùn)輸問題。 銷地產(chǎn)地第一季度第二季度第三季度第四季度生產(chǎn)量（產(chǎn)量）第一季度生產(chǎn)成本1生產(chǎn)成本1 + 存儲(chǔ)成本生產(chǎn)成本1 + 存儲(chǔ)成本2生產(chǎn)成本1 + 存儲(chǔ)成本3第二季度M生產(chǎn)成本2生產(chǎn)成本2 + 存儲(chǔ)成本生產(chǎn)成本2+ 存儲(chǔ)成本2第三季度MM第四季度MMM交付量

13、（銷量） 總產(chǎn)量總銷量F、轉(zhuǎn)運(yùn)問題 將中轉(zhuǎn)站既視為銷地、也視為產(chǎn)地，轉(zhuǎn)化為運(yùn)輸問題 運(yùn)輸模型表中產(chǎn)地由原產(chǎn)地加中轉(zhuǎn)地構(gòu)成，銷地為最終銷地加中轉(zhuǎn)地構(gòu)成，直接相連的路線運(yùn)費(fèi)按各地間運(yùn)費(fèi)填列，不直接相連的路線運(yùn)費(fèi)為M（意為足夠大），本地到本地的運(yùn)費(fèi)為“0”。六、整數(shù)規(guī)劃模型整數(shù)規(guī)劃 可行解為非負(fù)整數(shù)的集合，可行域表現(xiàn)為某一區(qū)域內(nèi)的可行點(diǎn)A、圖解法1、按常規(guī)方法標(biāo)出該模型的可行域，并在可行域中標(biāo)出橫、縱坐標(biāo)為整數(shù)的可行點(diǎn)；2、標(biāo)出目標(biāo)函數(shù)直線，按求Max 或 Min分不從可行域的右邊或左邊沿x1軸平移，最先接觸的可行點(diǎn)即為最優(yōu)解，代入目標(biāo)函數(shù)得最優(yōu)值；3、標(biāo)定可行點(diǎn)時(shí)應(yīng)充分注意坐標(biāo)軸上的整數(shù)點(diǎn)（包括原

14、點(diǎn)）和約束函數(shù)直線上的整數(shù)點(diǎn)；B、01規(guī)劃問題1、0或1為某一現(xiàn)象的狀態(tài)，0表示非、即不發(fā)生、不指派、不分配、不選用等，1則相反；2、通過設(shè)定01變量與某一現(xiàn)象的后果相乘，表示該現(xiàn)象發(fā)生或不發(fā)生帶來的后果，同時(shí)，01變量的和能夠限制某類現(xiàn)象共同發(fā)生或不發(fā)生的次數(shù)；3、投資場所選擇問題 令各投資場所被選擇的情況xi (i 1,2n)為01變量，0表示不被選擇，1表示被選擇，則：Max 利潤 或 Min 成本（xi乘以各投資場所的利潤或成本）S.T. 必須選擇或能夠同時(shí)選擇的投資場的xi值之和與限制相比較xi 為01變量3、固定成本問題 令各產(chǎn)品的產(chǎn)量xi (i 1,2m)為非負(fù)整數(shù)變量，生產(chǎn)該產(chǎn)

15、品所需投入固定資產(chǎn)發(fā)生狀態(tài)xm+j(j 1,2n)為01變量，0表示某產(chǎn)品不被選擇，1表示被選擇，則：Max 利潤（各產(chǎn)品的營業(yè)利潤之和減去為生產(chǎn)其所投入的固定資產(chǎn)之和）S.T. (1)生產(chǎn)產(chǎn)品所需的物料、設(shè)備和工時(shí)與限制條件相比較(2)xi Mxm+j （M為足夠大的數(shù)，應(yīng)遠(yuǎn)大于該組產(chǎn)品可能的最大產(chǎn)量，此約束條件是為排除不投入生產(chǎn)某產(chǎn)品所需的固定資產(chǎn)、但卻有xi存在的情況 當(dāng)xm+j為零時(shí)，現(xiàn)在xi必為零；當(dāng)xm+j為1時(shí)，現(xiàn)在xi可為實(shí)際值且不受M的限制）xi (i 1,2m)為非負(fù)整數(shù)變量， xm+j(j 1,2n)為01變量4、指派問題 令指派某人從事某項(xiàng)工作的狀態(tài)xi (i 1,2n

16、)為01變量，0表示不指派某人從事某項(xiàng)工作，1表示指派，則：Min 成本、費(fèi)用或工時(shí) （某人從事某項(xiàng)工作的成本、費(fèi)用或工時(shí)乘以xi后之和）S.T. (1)各人被指派從事某項(xiàng)工作的狀態(tài)之和為1(2)各項(xiàng)工作有人被指派的狀態(tài)之和也為1 xi (i 1,2n)為01變量 指派問題可用運(yùn)輸模型解決，其差不多形式為： 工作人員工作1工作2工作被指派人員數(shù)量人員11人員21人員1工作量111 總?cè)肆靠偣ぷ髁?運(yùn)輸模型中有關(guān)產(chǎn)銷不平衡的處理也可用于指派問題。5、分布系統(tǒng)設(shè)計(jì)問題該問題涉及不同生產(chǎn)地到銷售地的運(yùn)費(fèi)和不同生產(chǎn)地的建設(shè)費(fèi)用（固定成本）。令各生產(chǎn)地的產(chǎn)量xi（i=1,2,m）為非負(fù)整數(shù)，選擇某一生產(chǎn)

17、地的可能xm+j（j=1,2n）為01變量，0表示不選擇、1表示選擇，則： Min 成本 （成本為各生產(chǎn)地產(chǎn)量xi乘以成本與各生產(chǎn)地建設(shè)費(fèi)用乘以xm+j之和） S.T. (1)各生產(chǎn)地銷往各銷售地的銷量與產(chǎn)量限制相比較（其中已建成生產(chǎn)地的限制條件直接用當(dāng)前產(chǎn)量，待建生產(chǎn)地的限制條件用可能產(chǎn)量乘xm+j） (2)各銷售地中各生產(chǎn)地的產(chǎn)量與銷量限制相比較xi（i=1,2,m）為非負(fù)整數(shù)， xm+j（j=1,2n）為01變量分布系統(tǒng)設(shè)計(jì)問題可用運(yùn)輸模型解決。6、投資問題與線性規(guī)劃中連續(xù)投資問題相類似，只是各期的投資量存在限制、投資與否也不確定。因此，用變量表示投資的可能性，依照項(xiàng)目回收期不同列出各年

18、各種方案可能的投資表，其中總收益為各項(xiàng)目最后一期投資的和，各期的投資應(yīng)等于期初資金（也確實(shí)是上一期投資的收入）。目標(biāo)為求總收益最大，約束條件包括各期的投資應(yīng)等于期初資金（也確實(shí)是上一期投資的收入），以及各期投資的限制。七、目標(biāo)規(guī)劃模型目標(biāo)規(guī)劃問題 指不能同時(shí)滿足所有約束條件的情況下，求最大限度滿足各級(jí)目標(biāo)的最優(yōu)解A、目標(biāo)規(guī)劃問題不存在滿足所有約束條件的解 在圖形上表現(xiàn)為至少有一個(gè)限制條件的可行區(qū)域與其它不相交、不存在滿足所有約束條件的共同可行域；B、目標(biāo)規(guī)劃問題存在分級(jí)目標(biāo)，即優(yōu)先保證目標(biāo)實(shí)現(xiàn)的等級(jí)，優(yōu)先滿足等級(jí)高的目標(biāo) 在圖形上表現(xiàn)為從第一級(jí)目標(biāo)的可行域中找滿足第二級(jí)目標(biāo)偏差值最小的點(diǎn)、即到

19、第二級(jí)限制條件直線距離最短的點(diǎn)；并依此類推；C、目標(biāo)規(guī)劃問題引入了偏差變量di+、di-，分不表示超過或少于約束條件常數(shù)項(xiàng)的值 在圖形上表現(xiàn)為約束條件直線（k0）上di+0、di-0（無偏差），右上方區(qū)域?yàn)闉閐i+0、di-0（超過常數(shù)項(xiàng)），左下方區(qū)域?yàn)閐i+0、di-0（少于常數(shù)項(xiàng)）；D、列出分級(jí)目標(biāo)規(guī)劃模型的步驟：（1）選定各目標(biāo)的優(yōu)先等級(jí)，按優(yōu)先次序排列各約束條件 必須予以滿足的條件為絕對(duì)約束，其等級(jí)最高，有一定浮動(dòng)空間的條件為條件約束，分優(yōu)先等級(jí)；（2）條件約束為“”的，求min di+（方向相后、表示超出的最少），條件約束為“”的，求min di-（同樣方向相后、表示低于的最少） （

20、3）在條件約束中參考引入松弛、剩余變量化標(biāo)準(zhǔn)規(guī)劃模型的做法，在式子左邊加上“-di+di-”，將不等號(hào)轉(zhuǎn)換為等號(hào)，現(xiàn)在不用考慮正負(fù)符號(hào)，直接加上即可； （4）第一級(jí)目標(biāo)規(guī)劃模型為： Min d1+ / d1- + d2+ / d2- + （不一定唯一，多個(gè)照排） S.T. 絕對(duì)約束 第一級(jí)條件約束（不一定唯一，多個(gè)照排） xi, di 0第二級(jí)及以下各級(jí)目標(biāo)規(guī)劃模型為： Min d3+ / d3- + d4+ / d4- + （不一定唯一，多個(gè)照排） S.T. 絕對(duì)約束 第一級(jí)條件約束（不一定唯一，多個(gè)照排） 第二級(jí)條件約束（不一定唯一，多個(gè)照排） 第級(jí)條件約束（不一定唯一，多個(gè)照排） 增加上

21、一級(jí)條件約束的計(jì)算結(jié)果 增加上級(jí)條件約束的計(jì)算結(jié)果 xi, di 0E、列出總目標(biāo)規(guī)劃模型 min z = P1（d1+ / d1- + d2+ / d2- + ）+ P2（d3+ / d3- + d4+ / d4- + ）+ （P1、P2代表優(yōu)先等級(jí)，同一優(yōu)先級(jí)目標(biāo)列在一起，具體是di+或di-依照約束條件確定） S.T. 絕對(duì)約束 第一級(jí)條件約束 第二級(jí)條件約束 第級(jí)條件約束 xi, di 0F、總目標(biāo)規(guī)劃模型與分級(jí)目標(biāo)模型之間的相互轉(zhuǎn)換 參考兩類模型的做法即可。G、加權(quán)目標(biāo)規(guī)劃 當(dāng)目標(biāo)存在權(quán)重時(shí)，在目標(biāo)函數(shù)的di+或di-上直接加上權(quán)重即可，約束條件不變。 H、目標(biāo)規(guī)劃模型的圖解 找兩條

22、約束條件直線劃定的可行域中距離最短的點(diǎn)1、建立坐標(biāo)系，做出各約束條件的可行域，并將絕對(duì)約束視為第零級(jí)約束，首先予以保證； 2、兩級(jí)約束條件的最優(yōu)解 如兩條直線相交，則可同時(shí)滿足，最優(yōu)解為交點(diǎn)；如不相交，則本級(jí)約束條件可行域中距下一級(jí)約束條件直線距離最近的點(diǎn)為最優(yōu)解； 3、找到最優(yōu)解后，代入目標(biāo)函數(shù)，即得最優(yōu)值，再分不計(jì)算各約束條件距要求的差值； 4、一般情況下，圖解法不便于解超過兩級(jí)的目標(biāo)規(guī)劃。八、網(wǎng)絡(luò)最優(yōu)化模型網(wǎng)絡(luò)最優(yōu)化問題 選擇最優(yōu)路線 A、有方向的問題 有明確的起點(diǎn)和終點(diǎn)，求從起點(diǎn)到終點(diǎn)費(fèi)用最省、流量最大的問題，包括最短路問題、最小費(fèi)用問題、最大流問題、最小費(fèi)用最大流問題 1、狹克斯屈拉

23、法解最短路問題 從起點(diǎn)開始，依次計(jì)算路程中各節(jié)點(diǎn)之前的費(fèi)用和步數(shù)，最終計(jì)算出到終點(diǎn)所有可能路徑所需的費(fèi)用和步數(shù)，選擇費(fèi)用最低的路徑； 2、搬箱子理念 設(shè)想運(yùn)送一個(gè)箱子從起點(diǎn)到終點(diǎn)，除起點(diǎn)和終點(diǎn)外，不管路徑中哪一個(gè)中間節(jié)點(diǎn)，只有一個(gè)箱子進(jìn)、一個(gè)箱子出，各節(jié)點(diǎn)進(jìn)出平衡，而起點(diǎn)只有一個(gè)箱子出，終點(diǎn)只有一個(gè)箱子進(jìn)； 通過某節(jié)點(diǎn)的流入量和流出量相等，保證了路徑內(nèi)各節(jié)點(diǎn)流量平衡、前后銜接，也建立了線性規(guī)劃模型的約束條件； 實(shí)際使用時(shí)，起點(diǎn)各條路徑的流出量合計(jì)為1，終點(diǎn)各條路徑的流入量合計(jì)為1，中間節(jié)點(diǎn)各流入路徑合計(jì)量減去流出路徑合計(jì)量為零； 3、線性規(guī)劃模型的建立 令各條路徑的選擇可能性為xi（最短路問題），或流量為xi（費(fèi)用和流量問題） Min 路程 / 成本（各路徑距離或成本乘以xi） 或 max 流量（起點(diǎn)各路徑流出量之和） S.T. 起 點(diǎn)：流出量之和（最大流量問題不計(jì)算此點(diǎn)） 中間點(diǎn)：1、各點(diǎn)流入量減流出量為零2、各路