【正文】 1 1 1 6 0 1 2 兩最小元素 之差 ①②③④ ⑤ 2 5 1 3 2 1 3 2 1 2 1 2 2 3 6 5 2 1 3 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 22 13 March 2022 例 某種物資有 3個產(chǎn)地、 4個銷地，各產(chǎn)地的產(chǎn)量、銷地的銷量以及各產(chǎn)銷地之間的運價如表 21，求最優(yōu)的調(diào)運方案。 當(dāng)產(chǎn)地或銷地中有一方數(shù)量上供應(yīng)完畢或得到滿足時，劃去運價表中的行或列，再重復(fù)上述步驟。 西北角法則不考慮運距（或運價），每次都選剩余表格的左上角（即西北角）元素作為基變量，其它過程與最小元素法相同 ； 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 16 13 March 2022 調(diào) 銷地 運 量 產(chǎn)地 B1 B2 B3 產(chǎn) 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 銷 量 100 150 200 450 用最小元素法確定初始調(diào)運方案 150 100 100 100 100 100 100 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 17 13 March 2022 得到初始調(diào)運方案為： x11=100， x13=100， x22=150， x23=100 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 18 13 March 2022 調(diào) 銷地 運 量 產(chǎn)地 B1 B2 B3 產(chǎn) 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 銷 量 100 150 200 450 用西北角法確定初始調(diào)運方案 100 100 100 50 50 200 200 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 19 13 March 2022 得到初始調(diào)運方案為： x11=100， x12=100， x22=50， x23=200 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 20 13 March 2022 基本思路是：從全局考慮。 amp。3,2,1。 求解運輸問題的表上作業(yè)法 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 12 13 March 2022 例 甲 、 乙兩個煤礦供應(yīng) A、 B、 C三個城市用煤 ， 各煤礦產(chǎn)量及各城市需煤量 、各煤礦到各城市的運輸距離見表 ， 求使總運輸量最少的調(diào)運方案 。 167。 運輸問題的數(shù)學(xué)模型 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 10 13 March 2022 表上作業(yè)法是一類比較特殊的單純形法。下面介紹求解運輸問題的表上作業(yè)法。 mnnnn xxxxx , 32111 ??安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 9 13 March 2022 因此，運輸問題的任何一個基含有 個線性無關(guān)的列向量，即任何一個基可行解含有 個基變量，這時對應(yīng)的基可行解就是一個可行的調(diào)運方案。又，取A的前 m+n1行，變量 對應(yīng)的列所構(gòu)成的 A的子式為 由此易知，這個 m+n1階子式的值為 1或 1，所以， A的秩恰為 m+n1。 運輸問題的數(shù)學(xué)模型 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 8 13 March 2022 容易證明，秩 A=m+n1。 167。 運輸問題的數(shù)學(xué)模型 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 6 13 March 2022 ?總有可行解 Xij=ai*bj/Q ?矩陣的元素均為 1或 0； ? 每一列只有兩個元素為 1，其余元素均為 0； ? 列向量 Pij =(0,… ， 0， 1， …,0,1,0,…0)T ，其中兩個元素 1分別處于第 i行和第 m+j行， ei+em+j。,2,10,2,1,2,1.m i n111 1????167。 j=1,2,? ,n)。 運輸問題的應(yīng)用 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 3 13 March 2022 某種物資有 m個產(chǎn)地 A1, A2 , …, A m，聯(lián)合供應(yīng) n個銷地 B1, B2 , …, B n ，各產(chǎn)地產(chǎn)量、各銷地銷量（單位：噸）、各產(chǎn)地到各銷地的單位運價（單位：元 /噸）如表 11，應(yīng)如何組織調(diào)運，才能使得總運費最??？ 表 41一般運輸問題的平衡表與運價表 平衡表 運價表 銷地 產(chǎn)地 B1 B2 … Bn 產(chǎn)量（噸） B1 B2 … Bn A1 a1 c11 c12 … c1n A2 a2 c21 c22 … c2n … … … … … … Am am cm1 cm2 … cmn 銷量 (噸 ) b1 b2 … bn 167。 求解運輸問題的表上作業(yè)法 167。Transportation Problem 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 2 13 March 2022 167。 運輸問題的數(shù)學(xué)模型 167。 表上作業(yè)法的特殊情況 167。 運輸問題的數(shù)學(xué)模型 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 4 13 March 2022 用矩陣形式表示為： 設(shè) xij表示產(chǎn)地 Ai供應(yīng)銷地 Bj的數(shù)量 (i=1,2,? ,m。 ?????njjmii ba11當(dāng)產(chǎn)銷平衡 ( )時，數(shù)學(xué)模型為 (標(biāo)準(zhǔn)形 )： ??????0.m i nXbAXtsCXZ???????????????????? ???? ?njmixnjbxmiaxtsxcZijmijijnjiijminjijij,2,1。 運輸問題的數(shù)學(xué)模型 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 5 13 March 2022 其中： mnnmA?????????????????????????????)(100100100010010010001001001111000000000111000000000111??????????????????????????????????????????????????Tmnmmnn xxxxxxxxxX ),( 212222111211 ?????Tnm bbbaaab ),( 2121 ???),( 212222111211 mnmmnn cccccccccC ?????167。 ? 將該矩陣分塊，特點是： 前 m行構(gòu)成 m個 m n階矩陣 ，而且 第 k個矩陣只有第 k行元素全為 1，其余元素全為 0（ k=1， … ， m） ； 后 n行構(gòu)成 m個 n階單位陣 。 運輸問題的數(shù)學(xué)模型 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 7 13 March 2022 ????????????????????????????????111111111111111111????????????可以看出新組合成的子矩陣為對角矩陣，秩為m+n1，即原矩陣的秩為 m+n1 167。事實上，由于 A的前 m行之和等于后 n行之和，因此，秩 A≤m+n1?？梢娺\輸問題的基可行解中，基變量的個數(shù)應(yīng)為 m+n1個。關(guān)于運輸問題的求解，當(dāng)然可以用單純形方法，但由于它結(jié)構(gòu)的特殊性，用特殊的方法求解比較方便。 1?? nm1?? nm167。它必須首先確定一個初始方案，也就是找出一個基可行解，然后根據(jù)判別準(zhǔn)則來檢查這個初始方案是不是最優(yōu)的，如果不是最優(yōu)的，那么對初始方案加以改進(jìn)，直到找出最優(yōu)方案。 求解運輸問題的表上作業(yè)法 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 11 13 March 2022 確定初始 方案 ( 初 始 基本可行解 ) 改進(jìn)調(diào)整 （ 換基迭代 ） 否 判定是否 最 優(yōu) ？ 是 結(jié) 束 最優(yōu)方案 運輸問題求解思路圖 167。 安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院 page 13 13 March 2022 450 200 150 100 日銷量 （需求量） 250