物流網(wǎng)絡(luò)配送問(wèn)題

1、線性規(guī)劃,線性規(guī)劃是一種幫助管理者制定決策的方法; 在許多領(lǐng)域都有成功的應(yīng)用案例, 它在模型上表現(xiàn)為一個(gè)線性的函數(shù)在一組線性約束條件下的求極大值或求極小值問(wèn)題; 最常見(jiàn)的三類問(wèn)題是: 資源分配問(wèn)題; 成本效益平衡問(wèn)題和物流網(wǎng)絡(luò)配送問(wèn)題.,資源分配問(wèn)題,紅星重型機(jī)械廠的產(chǎn)品組合問(wèn)題 產(chǎn)品甲: 需要原料A,原料B,設(shè)備工時(shí); 產(chǎn)品乙: 也需要原料A,原料B,設(shè)備工時(shí);由于原料A,原料B,設(shè)備工時(shí)的數(shù)量有限,如何安排生產(chǎn),使獲利最大

2、?問(wèn)題 1.公司是否該生產(chǎn)這兩個(gè)產(chǎn)品? 2如果生產(chǎn), 產(chǎn)品生產(chǎn)組合如何?(各生產(chǎn)多少?),資源分配問(wèn)題,這是一個(gè)定量問(wèn)題決策目標(biāo)---利潤(rùn)最大化步驟1---收集相關(guān)數(shù)據(jù)如下:(見(jiàn)P10),資源分配問(wèn)題,步驟2--- 建立數(shù)學(xué)模型 1) 決策變量—決策量化的手段 x1=產(chǎn)品甲 的生產(chǎn)數(shù)量 x2 =產(chǎn)品乙 的生產(chǎn)數(shù)量

3、 2) 目標(biāo)函數(shù)---衡量決策效果(優(yōu)劣)的指標(biāo) Z= 4x1 + 3x2 求最大值 3) 約束條件 x1 ≤ 6 (原料A數(shù)量約束) 2 x2 ≤8 (原料B數(shù)量約束) 2x1 + 3x2 ≤18 (設(shè)備工時(shí)約束)

4、 x1, x2 ≥ 0 (非負(fù)約束),建立數(shù)學(xué)規(guī)劃模型的四個(gè)步驟 明確問(wèn)題，確定決策變量； 決策變量是構(gòu)成解決方案的要素或單元，決策變量的組合構(gòu)成一個(gè)可行解決方案。 明確約束條件并用決策變量的等式或不等式表示； 盡可能分類描述，防止差錯(cuò)和遺漏 用決策變量的函數(shù)表示目標(biāo)，并確定是求極大（Max）、極小（Min）還是特定值； 根據(jù)決策變量的物理性質(zhì)研究變量是否有非負(fù)性或上下界。,資源分

5、配問(wèn)題,資源分配（resource-allocation）問(wèn)題是將有限的資源 分配到各種活動(dòng)中去的線性規(guī)劃問(wèn)題。這一類問(wèn)題的 共性是在線性規(guī)劃模型中每一個(gè)函數(shù)限制均為資源限 制(resource constraint) , 并且每一種有限資源都可以表 現(xiàn)為如下的形式：  使用的資源數(shù)量 ? 可用的資源數(shù)量,資源分配問(wèn)題,例1的數(shù)學(xué)模型可以用代數(shù)形式描述如下：這實(shí)際上是求一個(gè)線性函數(shù)在一組線性約束條件

6、下的最大值問(wèn)題，我們稱之為線性規(guī)劃問(wèn)題模型。,資源分配問(wèn)題,我們稱x1、x2為決策變量，Z = 4 x1 + 3 x2為目標(biāo)函數(shù)，約束（1.1）-（1.3）為函數(shù)約束，約束（1.4）為非負(fù)約束。決策變量的任何一個(gè)取值稱為模型的一個(gè)解，若解滿足所有約束條件，則稱為可行解，反之（至少違反一個(gè)約束條件），稱其為非可行解，使目標(biāo)函數(shù)值最大化的可行解稱為最優(yōu)解。,成本收益平衡問(wèn)題,成本收益平衡問(wèn)題（ Cost-benefit-trade-o

7、ff Problem ） 是一類線性規(guī)劃問(wèn)題，這類問(wèn)題中，通過(guò)選擇各種 活動(dòng)水平的組合，從而以最小的成本來(lái)實(shí)現(xiàn)最低可 接受的各種收益的水平。這類問(wèn)題的共性是，所有 的函數(shù)約束均為收益約束，并具有如下的形式：  完成的水平 ? 最低可接受的水平,成本效益平衡問(wèn)題,某飼料公司希望用玉米、紅薯兩種原料配制一種混合飼料，各種原料包含的營(yíng)養(yǎng)成份和采購(gòu)成本都不相同，公司管理層希望能夠確定混合飼料中各種原料的數(shù)量，使得飼料

8、能夠以最低的成本達(dá)到一定的營(yíng)養(yǎng)要求。研究者根據(jù)這一目標(biāo)收集到的有關(guān)數(shù)據(jù)如下：,成本效益平衡問(wèn)題,為建立線性規(guī)劃模型，我們引入變量如下：x1 = 混合飼料中玉米的數(shù)量x2 = 混合飼料中紅薯的數(shù)量,成本效益平衡問(wèn)題,目標(biāo)函數(shù)是Z = 0.8 x1 + 0.5 x2，表示飼料的成本函數(shù)，即如何確定x1、x2使得成本Z = 0.8 x1 + 0.5 x2最低且滿足最低營(yíng)養(yǎng)要求的約束，這些約束條件是：碳水化合物需求： 8 x1 + 4

9、 x2 ≥20蛋白質(zhì)需求： 3 x1 + 6 x2 ≥18維他命需求： x1 + 5 x2 ≥16另有非負(fù)約束：x1 ≥0， x2 ≥0,成本效益平衡問(wèn)題,因此，這個(gè)問(wèn)題的線性規(guī)劃模型為：,物流網(wǎng)絡(luò)配送問(wèn)題,偉達(dá)物流公司需將甲、乙、丙三個(gè)工廠生產(chǎn)的一種新產(chǎn)品運(yùn)送到A、B兩個(gè)倉(cāng)庫(kù)，甲、乙兩個(gè)工廠的產(chǎn)品可以通過(guò)鐵路運(yùn)送到倉(cāng)庫(kù)A，數(shù)量不限；丙工廠的產(chǎn)品可以通過(guò)鐵路運(yùn)送到倉(cāng)庫(kù)B，同樣，產(chǎn)品數(shù)量不限。由于鐵路運(yùn)輸

10、成本較高，公司也可考慮由獨(dú)立的卡車來(lái)運(yùn)輸，可將多達(dá)80個(gè)單位的產(chǎn)品由甲、乙、丙三個(gè)工廠運(yùn)到一個(gè)配送中心，再?gòu)呐渌椭行囊宰疃?0單位的載貨量運(yùn)到各個(gè)倉(cāng)庫(kù)。公司管理層希望以最小的成本來(lái)運(yùn)送所需的貨物。,物流網(wǎng)絡(luò)配送問(wèn)題,需要收集每條線路上的單位運(yùn)輸成本和各工廠產(chǎn)品的產(chǎn)量以及各倉(cāng)庫(kù)分配量等數(shù)據(jù)：,物流網(wǎng)絡(luò)配送問(wèn)題,為了更清楚地說(shuō)明這個(gè)問(wèn)題，我們用一個(gè)網(wǎng)絡(luò)圖來(lái)表示該網(wǎng)絡(luò)配送問(wèn)題（見(jiàn)圖2-1）。圖中節(jié)點(diǎn)v1、v2、v3表示甲、乙、丙三個(gè)工廠，節(jié)點(diǎn)

11、v4表示配送中心，節(jié)點(diǎn)v5、v6表示兩個(gè)倉(cāng)庫(kù)；每一條箭線表示一條可能的運(yùn)輸路線，并給出了相應(yīng)的單位運(yùn)輸成本，對(duì)運(yùn)輸量有限制的路線的最大運(yùn)輸能力也同時(shí)給出。,物流網(wǎng)絡(luò)配送問(wèn)題,物流網(wǎng)絡(luò)配送問(wèn)題,我們要解決的是各條路線最優(yōu)運(yùn)輸量，引入變量fij表示由 vi經(jīng)過(guò)路線(vi,vj)運(yùn)輸?shù)絭j的產(chǎn)品數(shù)。問(wèn)題的目標(biāo)是總運(yùn)輸成本最小化，總運(yùn)輸成本可表示為：總運(yùn)輸成本 = 7.5 f15+ 3 f14 + 8.2 f25 + 3.5 f24 + 2.

12、3 f45 + 3.4 f34 + 2.3 f46 + 9.2 f36,物流網(wǎng)絡(luò)配送問(wèn)題,相應(yīng)的約束條件包括對(duì)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的供求平衡約束。對(duì)生產(chǎn)節(jié)點(diǎn)v1、v2、v3來(lái)說(shuō)，由某一節(jié)點(diǎn)運(yùn)出的產(chǎn)品數(shù)量等于其產(chǎn)量，即： f15 + f14 = 100 f25 + f24 = 80 f34 + f36 = 70,物流網(wǎng)絡(luò)配送問(wèn)題,對(duì)配送中心v4，運(yùn)進(jìn)的產(chǎn)品數(shù)量等于運(yùn)出的產(chǎn)品數(shù)量： f14 + f24 + f34 = f45 + f46

13、對(duì)倉(cāng)庫(kù)v5、v6，運(yùn)進(jìn)的產(chǎn)品數(shù)量等于其需求量 f15 + f25+ f45 = 120 f46+ f36 = 130,物流網(wǎng)絡(luò)配送問(wèn)題,此外，對(duì)網(wǎng)絡(luò)中有運(yùn)輸容量限制的路線的約束是：該路線上的運(yùn)輸產(chǎn)品數(shù)量不超過(guò)該線路的運(yùn)輸能力，即：f14≤80， f24 ≤80， f34≤80， f45 ≤90， f46 ≤90。并且，所有fij ≥0（非負(fù)約束）。,物流網(wǎng)絡(luò)配送問(wèn)題,共同的特征,從以上幾個(gè)例子可以看出，線性規(guī)劃問(wèn)題有如

14、下共同的特征：每個(gè)問(wèn)題都用一組決策變量（x1, x2, . . . , xn ），這組決策變量的值都代表一個(gè)具體方案；有一個(gè)衡量決策方案優(yōu)劣的函數(shù)，它是決策變量的線性函數(shù)，稱為目標(biāo)函數(shù)。按問(wèn)題不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化；存在一些約束條件，這些約束條件包括①函數(shù)約束，可以用一組決策變量的線性函數(shù)（稱為約束函數(shù)）大于等于“≥”、小于等于“≤”或等于“=”一個(gè)給定常數(shù)（稱為右端項(xiàng)）；②決策變量的非負(fù)約束。,一般形式,線性規(guī)劃的

15、一般形式為：,資源分配問(wèn)題一般形式,資源分配問(wèn)題是將有限的資源分配從事各種活動(dòng)的線性規(guī)劃問(wèn)題，其一般形式可以描述為：管理層計(jì)劃用m種資源去從事n種活動(dòng)，通過(guò)收集每種資源的總量和每種活動(dòng)單位資源使用量以及單位貢獻(xiàn)等數(shù)據(jù)如下表所示，來(lái)確定活動(dòng)的數(shù)量使得在資源許可的條件下貢獻(xiàn)最大。,資源分配問(wèn)題一般形式,資源分配問(wèn)題一般形式,我們用表示xj第j種活動(dòng)的數(shù)量(水平)，則目標(biāo)函數(shù) 最大化。對(duì)于第i種資源， 我們有約束條件：

16、 即資源消耗量不超過(guò)的資源總量,資源分配問(wèn)題一般形式,因此，這類問(wèn)題的數(shù)學(xué)模型為：,成本效益平衡問(wèn)題一般形式,以上所討論的成本效益平衡問(wèn)題是通過(guò)選擇各種活動(dòng)水平的組合，從而以最小的成本實(shí)現(xiàn)最低可接受的各種效益水平。該問(wèn)題的一般形式可描述為：管理層計(jì)劃用n種活動(dòng)去提高m種效益的水平，通過(guò)調(diào)查得知每種活動(dòng)對(duì)各種效益的單位貢獻(xiàn)、每種活動(dòng)的單位成本以及每種效益的最低可接受水平如表,成本效益平衡問(wèn)題一般形式,成本效益平衡問(wèn)題一般形式,

17、我們用表示xj第j種活動(dòng)的數(shù)量(水平)，則目標(biāo)函數(shù) 最小化。對(duì)于第i種效益，我們有,成本效益平衡問(wèn)題一般形式,因此，這類問(wèn)題的數(shù)學(xué)模型為：,物流網(wǎng)絡(luò)配送問(wèn)題一般形式,物流網(wǎng)絡(luò)配送問(wèn)題一般形式可描述為：假定在一n個(gè)頂點(diǎn)m條?。ň€路）的運(yùn)輸網(wǎng)絡(luò)中，有若干發(fā)點(diǎn)發(fā)送一定數(shù)量的物資流，同時(shí)又有若干收點(diǎn)接收這些物資流。由于每條弧運(yùn)輸費(fèi)用不同，運(yùn)輸能力也有一定限制，管理者希望以最小的運(yùn)輸成本完成由發(fā)點(diǎn)到收點(diǎn)的運(yùn)輸配送。,物流網(wǎng)絡(luò)配送問(wèn)題一般形式,

18、我們用fij表示由 vi經(jīng)過(guò)路線(vi,vj)運(yùn)輸?shù)絭j的流量， Cij表示線路(vi,vj)的最大運(yùn)輸能力（容量限制）， wij表示由頂點(diǎn)vi沿線路(vi,vj)流向vj的單位流量成本。,物流網(wǎng)絡(luò)配送問(wèn)題一般形式,物流網(wǎng)絡(luò)配送問(wèn)題模型為 :,線性規(guī)劃問(wèn)題的圖解法,當(dāng)決策變量只有兩個(gè)時(shí)，線性規(guī)劃問(wèn)題可以用在平面上作圖的方法求解，這種方法稱為圖解法。由于這種方法簡(jiǎn)單、直觀、容易理解，所以有助于了解線性規(guī)劃問(wèn)題的實(shí)質(zhì)和求解的原理?，F(xiàn)用

19、紅星重型機(jī)械廠的產(chǎn)品組合問(wèn)題中的線性規(guī)劃來(lái)說(shuō)明圖解法,線性規(guī)劃問(wèn)題的圖解法,紅星重型機(jī)械廠的產(chǎn)品組合問(wèn)題的線性規(guī)劃問(wèn)題：,線性規(guī)劃問(wèn)題的圖解法,我們首先建立x1O x2坐標(biāo)平面（見(jiàn)圖2-2），坐標(biāo)系上橫軸是x1軸，縱軸是x2軸。由非負(fù)約束x1 ≥0， x2 ≥0可知，所有可行解的集合（稱為可行域）應(yīng)在第一象限。然后，我們要逐個(gè)地查看每個(gè)函數(shù)約束都允許的非負(fù)解，再考慮所有的約束條件。第一個(gè)函數(shù)約束x1 ≤6，截取x1軸的直線x1 = 6

20、的線上或線左邊的解是滿足這個(gè)約束條件的；第二個(gè)約束2x2 ≤8，有相似的結(jié)果，即x2 = 4線及下方的解滿足這個(gè)約束。我們將函數(shù)約束條件的邊界直線稱為約束邊界，相應(yīng)的方程稱為約束邊界方程,線性規(guī)劃問(wèn)題的圖解法,線性規(guī)劃問(wèn)題的圖解法例1,確定了可行域以后，我們希望找出哪些解是最優(yōu)解，即使目標(biāo)函數(shù)Z = 4x1 + 3x2盡可能大的可行解。我們給目標(biāo)函數(shù)一個(gè)值，例如給定Z =12，可以在圖上畫(huà)出一條直線4x1 + 3x2 = 12（見(jiàn)圖1-

21、3），在直線上的任一點(diǎn)處，對(duì)應(yīng)的目標(biāo)函數(shù)值均為12，故稱該直線為目標(biāo)函數(shù)的等值線。Z =12只是目標(biāo)函數(shù)的一個(gè)給定值，對(duì)于其它Z的給定值，如Z = 15也可在圖上畫(huà)出一條直線4x1 + 3x2 = 15，顯然，對(duì)于Z的不同給定值k，4x1 + 3x2 = k是一組平行的直線族，當(dāng)k的值由小變大時(shí)，目標(biāo)函數(shù)的等值線平等移動(dòng)，它與可行域的最后一個(gè)交點(diǎn)（一般是可行域的一個(gè)頂點(diǎn)）就是所求的最優(yōu)點(diǎn)，即圖2-3中的B點(diǎn),線性規(guī)劃問(wèn)題的圖解法,線性規(guī)

22、劃問(wèn)題的圖解法,由上可以看出，線性規(guī)劃問(wèn)題的最優(yōu)解出現(xiàn)在可行域的一個(gè)頂點(diǎn)上，此時(shí)線性規(guī)劃問(wèn)題有唯一最優(yōu)解。但有時(shí)線性規(guī)劃問(wèn)題還可能出現(xiàn)有無(wú)窮多個(gè)最優(yōu)解、無(wú)有限最優(yōu)解、甚至沒(méi)有可行解的情況，我們?nèi)酝ㄟ^(guò)例子說(shuō)明。,線性規(guī)劃問(wèn)題的圖解法,（1）無(wú)窮多最優(yōu)解。若將上例中的目標(biāo)函數(shù)變?yōu)榍驧ax Z = 4x1 + 6x2，則目標(biāo)函數(shù)的等值線與邊界線2x1 + 3x2 = 18平行，線段BC上的任意一點(diǎn)都使Z取得相同的最大值，此時(shí)線性規(guī)劃問(wèn)題有無(wú)窮