運(yùn)籌學(xué)課件第3章運(yùn)輸問題-第1，2節(jié)(編輯修改稿)
2024-11-12 13:00 本頁面
【文章內(nèi)容簡介】 ? 第一步 ：在表 33中分別計(jì)算出各行和各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行，見表 310。 ? 銷地 加工廠 B 1 B 2 B 3 B 4 行差額 A 1 A 2 A 3 3 1 7 11 9 4 3 2 10 10 8 5 0 1 1 列差額 2 5 1 3 第二步 ：從行或列差額中選出最大者，選擇它所在行或列中的最小元素。在表 310中 B2列是最大差額所在列。 B2列中最小元素為 4，可確定 A3的產(chǎn)品先供應(yīng) B2的需要。得表 311 銷地 加工廠 B 1 B 2 B 3 B 4 產(chǎn)量 A 1 A 2 A 3 6 7 4 9 銷量 3 6 5 6 同時(shí)將運(yùn)價(jià)表中的 B2列數(shù)字劃去。 如表 312所示。 銷地 加工廠 B 1 B 2 B 3 B 4 行差額 A 1 A 2 A 3 3 1 7 11 9 4 3 2 10 10 8 5 0 1 2 列差額 2 1 3 銷地 加工廠 B 1 B 2 B 3 B 4 產(chǎn)量 A 1 A 2 A 3 3 6 5 2 1 3 7 4 9 銷量 3 6 5 6 第三步：對(duì)表 312中未劃去的元素再分別計(jì)算出各行、各列的最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行。重復(fù)第一、二步。直到給出初始解為止。用此法給出例 1的初始解列于表 313。 ? 由以上可見：伏格爾法同最小元素法除在確定供求關(guān)系的原則上不同外 ， 其余步驟相同 。 伏格爾法給出的初始解比用最小元素法給出的初始解更接近最優(yōu)解 。 ? 本例用伏格爾法給出的初始解就是最優(yōu)解 。 22 最優(yōu)解的判別 ? 判別的方法是計(jì)算空格 (非基變量 )的檢驗(yàn)數(shù) cijCBB1Pij， i,j∈ N。因運(yùn)輸問題的目標(biāo)函數(shù)是要求實(shí)現(xiàn)最小化，故當(dāng)所有的cijCBB1Pij≥0時(shí)，為最優(yōu)解。下面介紹兩種求空格檢驗(yàn)數(shù)的方法。 ? ； ? ? 在給出調(diào)運(yùn)方案的計(jì)算表上，如表 313，從每一空格出發(fā)找一條閉回路。它是以某空格為起點(diǎn)。用水平或垂直線向前劃，當(dāng)碰到一數(shù)字格時(shí)可以轉(zhuǎn) 90176。 后，繼續(xù)前進(jìn)，直到回到起始空格為止。閉回路如圖 31的 (a),(b),(c)等所示。 銷地 加工廠 B 1 B 2 B 3 B 4 產(chǎn)量 A 1 A 2 A 3 3 6 5 2 1 3 7 4 9 銷量 3 6 5 6 從每一空格出發(fā)一定存在和可以找到唯一的閉回路。因 (m+n1)個(gè)數(shù)字格 (基變量 )對(duì)應(yīng)的系數(shù)向量是一個(gè)基。任一空格 (非基變量 )對(duì)應(yīng)的系數(shù)向量是這個(gè)基的線性組合。如 Pij, i,j∈N 可表示為 ujuslslkikjmusmusmlkmlkmijmuusmsmllkmkmijmiijPPPPPeeeeeeeeeeeeeeeeeeeeeeP??????????????????????????????????????)()()()()(其中 Pik,Plk,Pls,Pus,Puj∈B 。而這些向量構(gòu)成了閉回路 (見圖 32)。 閉回路法計(jì)算檢驗(yàn)數(shù)的經(jīng)濟(jì)解釋為：在已給出初始解的表 39中， 可從任一空格出發(fā)，如 (A1， B1)， 若讓 A1的產(chǎn)品調(diào)運(yùn) 1噸給 B1。為了保持產(chǎn)銷平衡，就要依次作調(diào)整： 在 (A1， B3)處減少 1噸， (A2， B3)處增加 1噸，(A2， B1)處減少 1噸，即構(gòu)成了以 (A1， B1)空格為起點(diǎn)，其他為數(shù)字格的閉回路。 ? 如表 314中的虛線所示。在這表中閉回路各頂點(diǎn)所在格的右上角數(shù)字是單位運(yùn)價(jià) 。 銷地 加工廠 B 1 B 2 B 3 B 4 產(chǎn)量 A 1 3 (+1) 11 3 4 ( 1) 10 3 7 A 2 1 3( 1) 9 2 1(+1) 8 4 A 3 7 4 6 10 5 3 9 銷量 3 6 5 6 可見這調(diào)整的方案使運(yùn)費(fèi)增加 (+1) 3+(1) 3+(+1) 2+(1) １ =1(元 ) 這表明若這樣調(diào)整運(yùn)量將增加運(yùn)費(fèi)。將 “ 1”這個(gè)數(shù)填入 (A1， B1)格，這就是檢驗(yàn)數(shù)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1