物流系統(tǒng)規(guī)劃課件-展示頁
2025-03-07 09:33本頁面
【正文】 一些矩陣元素變?yōu)?0，在 Cij為 0的元素上進(jìn)行分解，就可得到原問題的最優(yōu)解。q本書采用匈牙利法求解任務(wù)分配問題。q任務(wù)分配問題可以用一般的整數(shù)規(guī)劃求解方法進(jìn)行求解。q當(dāng)其值為 1時表示第 i個司機(jī)被分配去完成第 j項任務(wù)；q其值為 0時，表示第 i個司機(jī)不被分配去完成第 j項任務(wù)。2一 . 任務(wù)分配問題的數(shù)學(xué)模型q 以運(yùn)輸問題的 n項任務(wù)由 n個司機(jī)去完成的情況為例，有 n個司機(jī)被分配完成 n項運(yùn)輸任務(wù)，不同的司機(jī)完成任務(wù)某一項任務(wù)的費(fèi)用都不一樣。要求每條船完成一條航線，并且一條航線只能由一條船去完成。問：如何安排，才能使總的上課費(fèi)用最低？v又如：運(yùn)輸任務(wù)的分配問題。 物流分配 規(guī) 劃?任 務(wù) 分配 問題 的數(shù)學(xué)模型?用匈牙利法求解分配 問題1一 . 任務(wù)分配問題的數(shù)學(xué)模型q 在物流系統(tǒng)中或其它的管理工作中，管理人員經(jīng)常面臨的一個問題是：如何根據(jù)有限的資源 (人力、物力、財力等 )，進(jìn)行工作任務(wù)分配，以達(dá)到降低成本或提高經(jīng)濟(jì)效益的目的。如：v有 A、 B、 C、 D四門課程，上課的老師可以從甲、乙、丙、丁四名老師中選擇，不同的老師上不同的課程，其費(fèi)用是不同的，并且規(guī)定，每人只講一門課程，每門課程只需要一人講授。有 n條航線的運(yùn)輸任務(wù)指派給 n艘船去完成，不同的船完成不同的航線其運(yùn)輸成本不同。如何分配任務(wù)，才能使總的費(fèi)用最??？q 這類問題是常見的任務(wù)分配問題，也叫指派問題，它的任務(wù)是如何進(jìn)行合理的任務(wù)分配，使總的費(fèi)用最小。要求每個司機(jī)完成其中一項任務(wù)，每個任務(wù)只能由一名司機(jī)完成，如何分配任務(wù)，才能使總的費(fèi)用最??？ 令： cij表示第 i個司機(jī)完成第 j項任務(wù)的運(yùn)輸成本（工作成本或工作時間等價值系數(shù)）； xij表示第 i個司機(jī)去完成第 j項任務(wù)，其值為 1或 0。 3一 . 任務(wù)分配問題的數(shù)學(xué)模型q任務(wù)分配問題屬于整數(shù)規(guī)劃問題，其變量 xij的取值為整數(shù)，（本例為 0或 1）。但是，整數(shù)規(guī)劃問題的求解也是非常困難的，到目前為止，還缺乏統(tǒng)一的求解方法。4二 . 匈牙利法求解分配問題q 可以證明，對于分配問題，在其費(fèi)用矩陣 Cij中，各行、各列均減去一個常數(shù)， Cij改變以后的最優(yōu)解，仍為原問題的最優(yōu)解。q 該方法應(yīng)用了匈牙利數(shù)學(xué)家 Konig矩陣性質(zhì)定理，因此這種方法被稱為匈牙利法。q還有一類運(yùn)輸問題，他的收貨點和發(fā)貨點是待定的，這就是選址問題。q選址問題要考慮多種因素，本節(jié)只討論選址問題中的物流問題。71. 單一地址選址方法 建立一個新工廠（或倉庫），應(yīng)合理選擇廠址（或庫址）。 問題描述 ：假設(shè)廠址候選地點有 s個，分別用 D1,D2,…,Ds表示；原材料、燃料、零配件的供應(yīng)地有 m個，分別用A1,A2,…,Am表示，其供應(yīng)量分別用 P1,P2,…,Pm表示；產(chǎn)品銷售地有 n個，分別用 B1,B2,…,Bn表示，其銷售量分別為Q1,Q2,…,Qn表示。910q單一選址問題是一種線性規(guī)劃問題 ,并且變量的取值為 0或 1，屬于整數(shù)規(guī)劃問題。q當(dāng)要選定的地址不是單一的，而是多個時，問題不再屬于線性規(guī)劃問題。 下面以一個實際例子來說明圖上作業(yè)法的選址問題： 例題 8 假定有六個礦井．產(chǎn)量分別為 5000噸、 6000噸、 7000噸、2023噸、 4000噸和 3000噸，運(yùn)輸路線如圖所示，這些礦石要經(jīng)過加工后才能轉(zhuǎn)運(yùn)到其他地方。 為了便于分析，用一個新的圖來代替原圖，新圖圈內(nèi)數(shù)字表示礦井編號，產(chǎn)量記在圈的旁邊，道路交叉點看作產(chǎn)量為零的礦井
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1