第五章線性規(guī)劃方法

1、線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法 運(yùn)輸問題的求解方法運(yùn)輸問題的求解方法表上作業(yè)法表上作業(yè)法v線性規(guī)劃是運(yùn)籌學(xué)中發(fā)展較快、應(yīng)用較廣和線性規(guī)劃是運(yùn)籌學(xué)中發(fā)展較快、應(yīng)用較廣和比較成熟的一個(gè)分支。它在實(shí)際應(yīng)用中日益比較成熟的一個(gè)分支。它在實(shí)際應(yīng)用中日益廣泛與深入廣泛與深入,已經(jīng)被廣泛地應(yīng)用到工業(yè)、農(nóng)業(yè)、已經(jīng)被廣泛地應(yīng)用到工業(yè)、農(nóng)業(yè)、商業(yè)與交通運(yùn)輸規(guī)劃，工程技術(shù)的優(yōu)化設(shè)計(jì)，商業(yè)與交通運(yùn)輸規(guī)劃，工程技術(shù)的優(yōu)化設(shè)計(jì)，以及企業(yè)管理等各個(gè)領(lǐng)域。以及企業(yè)管理等各個(gè)領(lǐng)域。 v 在地理學(xué)領(lǐng)域，線性規(guī)劃，作為傳統(tǒng)的計(jì)在地理學(xué)領(lǐng)域，線性規(guī)劃，作為傳統(tǒng)的計(jì)量地理學(xué)方法之一，是解決有關(guān)規(guī)劃、決策量地理學(xué)方

2、法之一，是解決有關(guān)規(guī)劃、決策和系統(tǒng)優(yōu)化問題的重要手段。和系統(tǒng)優(yōu)化問題的重要手段。第一節(jié)第一節(jié) 線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法v線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型v線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式v線性規(guī)劃的解及其性質(zhì)線性規(guī)劃的解及其性質(zhì)v線性規(guī)劃問題的求解方法線性規(guī)劃問題的求解方法單純形法單純形法v應(yīng)用實(shí)例應(yīng)用實(shí)例: 農(nóng)場(chǎng)種植計(jì)劃模型農(nóng)場(chǎng)種植計(jì)劃模型線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法v一、線性規(guī)劃的數(shù)學(xué)模型一、線性規(guī)劃的數(shù)學(xué)模型（一）線性規(guī)劃模型之實(shí)例（一）線性規(guī)劃模型之實(shí)例線性規(guī)劃研究的兩類問題：線性規(guī)劃研究的兩類問題：某項(xiàng)任務(wù)確定后，如何統(tǒng)籌安

3、排，以最少的某項(xiàng)任務(wù)確定后，如何統(tǒng)籌安排，以最少的人力、物力和財(cái)力去完成該項(xiàng)任務(wù)；人力、物力和財(cái)力去完成該項(xiàng)任務(wù)；面對(duì)一定數(shù)量的人力、物力和財(cái)力資源，如面對(duì)一定數(shù)量的人力、物力和財(cái)力資源，如何安排使用，使得完成的任務(wù)最多。何安排使用，使得完成的任務(wù)最多。合理下料問題合理下料問題資源利用問題資源利用問題線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法v已知：已知：某地區(qū)擁有某地區(qū)擁有m種資源。其中，第種資源。其中，第i種資源在規(guī)劃期內(nèi)的種資源在規(guī)劃期內(nèi)的限額為限額為bi(i=1，2，m);這這m種資源可用來生產(chǎn)種資源可用來生產(chǎn)n種產(chǎn)品，其中，生產(chǎn)單位數(shù)量種產(chǎn)品，其中，生產(chǎn)單位數(shù)量的第的第j種

4、產(chǎn)品需要消耗的第種產(chǎn)品需要消耗的第i種資源的數(shù)量為種資源的數(shù)量為aij(i=1，2，m；j=1,2, ,n);第第j種產(chǎn)品的單價(jià)為種產(chǎn)品的單價(jià)為cj(j=1，2， ，n)。v求：求：試問如何安排這幾種產(chǎn)品的生產(chǎn)計(jì)劃，才能使規(guī)劃期試問如何安排這幾種產(chǎn)品的生產(chǎn)計(jì)劃，才能使規(guī)劃期內(nèi)資源利用的總產(chǎn)值達(dá)到最大內(nèi)資源利用的總產(chǎn)值達(dá)到最大?資源利用問題資源利用問題 資源利用問題資源利用問題returnv設(shè)第設(shè)第j種產(chǎn)品的生產(chǎn)數(shù)量為種產(chǎn)品的生產(chǎn)數(shù)量為xj(j=1，2，n)njjjxcZ1max消耗資源數(shù)量消耗資源數(shù)量第一種資源第一種資源第二種資源第二種資源第三種資源第三種資源第第m種資源種資源資源利用問題資源

5、利用問題.x1x1x1.x1x2x2x2.x2x3x3x3.x3xnxnxn.xn.return第一種產(chǎn)品第一種產(chǎn)品a11a21a31am1第二種產(chǎn)品第二種產(chǎn)品a12a22a32am2第三種產(chǎn)品第三種產(chǎn)品a13a23a33am3第第n種產(chǎn)品種產(chǎn)品a1na2na3namn消耗資源數(shù)量消耗資源數(shù)量第一種資源第一種資源第二種資源第二種資源第三種資源第三種資源第第m種資源種資源資源利用問題資源利用問題jnjjxa11jnjjxa12jnjjxa13jnjmjxa1 b1 b2 b3 bmnjijijmibxa1), 2 , 1(), 2 , 1(0njxj資源利用問題資源利用問題v設(shè)第設(shè)第j種產(chǎn)品的生

6、產(chǎn)數(shù)量為種產(chǎn)品的生產(chǎn)數(shù)量為xj(j=1，2，n)，則上，則上述資源問題就是：述資源問題就是： 求一組實(shí)數(shù)變量求一組實(shí)數(shù)變量xj (j=1，2，n)，使其滿足，使其滿足), 2 , 1(0), 2 , 1(1njxmibxajnjijijnjjjxcZ1maxreturn約束條件約束條件目標(biāo)函數(shù)目標(biāo)函數(shù)合理下料問題合理下料問題v設(shè)采用設(shè)采用Bj方式下料的原材料數(shù)為方式下料的原材料數(shù)為xj ，則上述問題可，則上述問題可表示為：表示為： 求一組整數(shù)變量求一組整數(shù)變量xj(j=1，2，n)，使得，使得), 2 , 1(0), 2 , 1(1njxmibxajnjijijnjjxZ1min約束條件約束條

7、件目標(biāo)函數(shù)目標(biāo)函數(shù)用某種原材料切割零件用某種原材料切割零件A1，A2, ,Am的毛坯，現(xiàn)已設(shè)的毛坯，現(xiàn)已設(shè)計(jì)出在一塊原材料上有計(jì)出在一塊原材料上有B1，B2，Bn種不同的下料種不同的下料方式，如用方式，如用Bj下料方式可得下料方式可得Ai種零件種零件aij個(gè)，設(shè)個(gè)，設(shè)Ai種零種零件的需要量為件的需要量為bi個(gè)。試問應(yīng)該怎樣組織下料活動(dòng)，才個(gè)。試問應(yīng)該怎樣組織下料活動(dòng)，才能使得既滿足需要，又節(jié)約原材料？能使得既滿足需要，又節(jié)約原材料？ 假設(shè)某種物資（譬如煤炭、鋼鐵、石油等）有假設(shè)某種物資（譬如煤炭、鋼鐵、石油等）有m個(gè)產(chǎn)地，個(gè)產(chǎn)地，n個(gè)銷地。第個(gè)銷地。第i產(chǎn)地的產(chǎn)量為產(chǎn)地的產(chǎn)量為ai（i=1，2

8、，m），第），第j 銷地的需求量為銷地的需求量為bj(j=1, 2，n)，它們滿，它們滿足產(chǎn)銷平衡條件。足產(chǎn)銷平衡條件。 如果產(chǎn)地如果產(chǎn)地i到銷地到銷地j的單位物資的運(yùn)費(fèi)為的單位物資的運(yùn)費(fèi)為Cij，要使，要使總運(yùn)費(fèi)達(dá)到最小，可這樣安排物資的調(diào)運(yùn)計(jì)劃：總運(yùn)費(fèi)達(dá)到最小，可這樣安排物資的調(diào)運(yùn)計(jì)劃：minjjiba11運(yùn)輸問題運(yùn)輸問題 設(shè)設(shè)xij表示由產(chǎn)地表示由產(chǎn)地i供給銷地供給銷地j 的物資數(shù)量，則的物資數(shù)量，則上述問題可以表述為：上述問題可以表述為： 求一組實(shí)值變量求一組實(shí)值變量xij(i=1，2，m；j=1，2，n)，使其滿足，使其滿足 而且使而且使 ), 2 , 1;, 2 , 1(0), 2

9、 , 1(), 2 , 1(11njmixmiaxnjbxijnjiijmijijminjijijxcz11min線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法v（二）線性規(guī)劃的數(shù)學(xué)模型（二）線性規(guī)劃的數(shù)學(xué)模型 以上例子表明，線性規(guī)劃問題具有以下特征：以上例子表明，線性規(guī)劃問題具有以下特征： 每一個(gè)問題都用一組未知變量（每一個(gè)問題都用一組未知變量（x1，x2，xn）表示某一規(guī)劃方案，其一組定值）表示某一規(guī)劃方案，其一組定值代表一個(gè)具體的方案，而且通常要求這些未知代表一個(gè)具體的方案，而且通常要求這些未知變量的取值是非負(fù)的。變量的取值是非負(fù)的。 每一個(gè)問題的組成部分：一是目標(biāo)函數(shù)，每一個(gè)問題

10、的組成部分：一是目標(biāo)函數(shù)，按照研究問題的不同，常常要求目標(biāo)函數(shù)取最按照研究問題的不同，常常要求目標(biāo)函數(shù)取最大或最小值；二是約束條件，它定義了一種求大或最小值；二是約束條件，它定義了一種求解范圍，使問題的解必須在這一范圍之內(nèi)。解范圍，使問題的解必須在這一范圍之內(nèi)。 每一個(gè)問題的目標(biāo)函數(shù)和約束條件都是線每一個(gè)問題的目標(biāo)函數(shù)和約束條件都是線性的。性的。線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法v（二）線性規(guī)劃的數(shù)學(xué)模型（二）線性規(guī)劃的數(shù)學(xué)模型 由此可以抽象出線性規(guī)劃問題的數(shù)學(xué)模型，一由此可以抽象出線性規(guī)劃問題的數(shù)學(xué)模型，一般形式為：般形式為：在線性約束條件在線性約束條件以及非負(fù)約束條件以及

11、非負(fù)約束條件 xj0（j=1，2，n）下，求一組未知變量下，求一組未知變量xj (j=1，2， ，n)的值，使的值，使njijijmibxa1), 2 , 1(),(njjjxcZ1(min)max線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法在約束條件在約束條件 AX(，)bX0下，求未知向量下，求未知向量 ，使得，使得Z=CXmax(min) TnxxxX,21,2121nTmcccCbbbbmnmmnnaaaaaaaaaA212222111211線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法v二二 線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式（一）（一）線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)

12、準(zhǔn)形式 在討論與計(jì)算時(shí)，需要將線性規(guī)劃問題的數(shù)在討論與計(jì)算時(shí)，需要將線性規(guī)劃問題的數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形式學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形式（二）（二）化為標(biāo)準(zhǔn)形式的方法化為標(biāo)準(zhǔn)形式的方法 mnmnmmnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111xj0（j = 1，2，n） 下，求一組未知變量下，求一組未知變量xj （j = 1，2，n）的值，）的值，使使njjjxcZ1maxnjijijmibxa1), 2 , 1(在約束條件下在約束條件下線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法記為如下更為緊湊的形式：記為如下更為緊湊的形式： ), 2 , 1(0)

13、, 2 , 1(max11njxmibxaxcZjnjijijnjjj或0XbAXCXZmax線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法returnv具體的線性規(guī)劃問題，需要對(duì)目標(biāo)函數(shù)或約束條件進(jìn)行轉(zhuǎn)換，化為標(biāo)準(zhǔn)形式。1.目標(biāo)函數(shù)化為標(biāo)準(zhǔn)形式的方法目標(biāo)函數(shù)化為標(biāo)準(zhǔn)形式的方法 v如果其線性規(guī)劃問題的目標(biāo)函數(shù)為：v min Z = CX v顯然有： minZ = max(-Z)=max Z v則目標(biāo)函數(shù)的標(biāo)準(zhǔn)形式為： max Z= -CX線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法2.2.約束方程化為標(biāo)準(zhǔn)形式的方法約束方程化為標(biāo)準(zhǔn)形式的方法 若第k個(gè)約束方程為不等式，即 引入松弛

14、變量 , K個(gè)方程改寫為：則目標(biāo)函數(shù)標(biāo)準(zhǔn)形式為：knknkkbxaxaxa)(22110knxkknnknkkbxxaxaxa)(2211njnjknjjjjxoxcxcZ11線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法三、線性規(guī)劃的解及其性質(zhì)三、線性規(guī)劃的解及其性質(zhì) v（一）線性規(guī)劃的解（一）線性規(guī)劃的解 可行解與最優(yōu)解可行解與最優(yōu)解滿足約束條件（即滿足線性約束和非負(fù)約束）的一組變量為可行解。所有可行解組成的集合稱為可行域。使目標(biāo)函數(shù)最大或最小化的可行解稱為最優(yōu)解。 基本解與基本可行解基本解與基本可行解 在線性規(guī)劃問題中，將約束方程

15、組的mn階矩陣A寫成由n個(gè)列向量組成的分塊矩陣,21npppA), 2 , 1(,21njaaaPTmjjjj線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法 如果B是A中的一個(gè)階的非奇異子陣，則稱B為該線性規(guī)劃問題的一個(gè)基。不失一般性，不妨設(shè)：則稱 為基向量，與基向量相對(duì)應(yīng)的向量 為基變量，而其余的變量 為非基變量。 ,21212222111211mmmmmmmPPPaaaaaaaaaB),2, 1(mjPj),2, 1(mjxj),2, 1(nmmjxi線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法如果 是方程組 的解，則就是方

16、程組式 的一個(gè)解，它稱之為對(duì)應(yīng)于基B的基本解，簡(jiǎn)稱基解。 滿足非負(fù)約束條件的基本解，稱為基本可行解。對(duì)應(yīng)于基本可行解的基，稱為可行基。TmBxxxX,21bBXBTmxxxX0,0,0,21CXZmax線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法線性規(guī)劃問題的以上幾個(gè)解的關(guān)系，可用下圖來描述：線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法 (二二)線性規(guī)劃解的性質(zhì)線性規(guī)劃解的性質(zhì) 凸集和頂點(diǎn)凸集和頂點(diǎn) 凸集凸集：若連接n維點(diǎn)集S中的任意兩點(diǎn)X(1)和X(2)之間的線段仍在S中，則S為凸集。 頂點(diǎn)頂點(diǎn)：若凸集S中的點(diǎn)X(0)不能成為S中任何線段的內(nèi)點(diǎn)，則稱X(0)為S的頂點(diǎn)或極點(diǎn)。

17、 線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法線性規(guī)劃解的性質(zhì)線性規(guī)劃解的性質(zhì) 線性規(guī)劃問題的可行解集（可行域）為凸集?？尚薪饧疭中的點(diǎn)X是頂點(diǎn)的充要條件是基本可行解。若可行解集有界，則線性規(guī)劃問題的最優(yōu)值一定可以在其頂點(diǎn)上達(dá)到。 因此線性規(guī)劃的最優(yōu)解只需從其可行解集的有限個(gè)頂點(diǎn)中去尋找。線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法四、線性規(guī)劃問題的求解方法四、線性規(guī)劃問題的求解方法單純形法單純形法 （一）單純形表（一）單純形表 根據(jù)以上討論，令 則基變量 ，非基變量 ，則有： 變形得：,21nmmpppN,NBA TmBxxxx,21TnmmNxxxx,21bNXBXNBNB

18、NXBbBX11線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法v相應(yīng)地，記：v目標(biāo)函數(shù)記為：v則對(duì)應(yīng)于基B的基本解為：,21mBcccC,21nmmNcccC,NBCCC NBNBXNBCCbBCZ)(11bBXB10NX線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法最優(yōu)解的判定：當(dāng) 時(shí)， 則由目標(biāo)函數(shù)式可看出：對(duì)應(yīng)于B的基本可行解為最優(yōu)解，這時(shí)，B也被稱為最優(yōu)基。于 與 等價(jià)，故可得最優(yōu)解的判定定理最優(yōu)解的判定定理： 對(duì)于基B ，若 ，且 則對(duì)應(yīng)于基B 的基本解為最優(yōu)解， B為最優(yōu)基。01NBCCBN01NBCCBN01ABCCB01bB01ABCCB線性規(guī)劃及其單純形求解方法線

19、性規(guī)劃及其單純形求解方法bBbBCXZABABCCBB111101在上式中，稱系數(shù)矩陣 為對(duì)應(yīng)于基B的單純形表，記為T(B).ABbBABCCbBCBB111101ABbBABCCbBCBB1111或?qū)δ繕?biāo)函數(shù)與約束不等式運(yùn)用矩陣變形得：線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法001bbBCB,002011nBbbbABCCTmbbbbB,020101如果記：mnmmnnbbbbbbbbbAB2122221112111以及mnmmmnnnbbbbbbbbbbbbbbbbBT210222212011211100020100)(則線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法(二

20、二) 單純形法的計(jì)算步驟單純形法的計(jì)算步驟 v第一步第一步，找出初始可行基，建立初始單純形表。v第二步第二步，判別檢驗(yàn)所有的檢驗(yàn)系數(shù) （1）如果所有的檢驗(yàn)系數(shù) ，則由最優(yōu)性判定定理知，已獲最優(yōu)解，即此時(shí)的基本可行解就是最優(yōu)解。 （2）若檢驗(yàn)系數(shù)中，有些為正數(shù)，但其中某一正的檢驗(yàn)系數(shù)所對(duì)應(yīng)的列向量的各分量均非正，則線性規(guī)劃問題無解。（3）若檢驗(yàn)系數(shù)中，有些為正數(shù)，且它們所對(duì)應(yīng)的列向量中有正的分量，則需要換基、進(jìn)行迭代運(yùn)算。), 2 , 1(0njbj), 2 , 1(00njbj線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法第三步第三步，選主元。 在所有大于零的檢驗(yàn)數(shù)中選取最大的一個(gè)b0s

21、，對(duì)應(yīng)的非基變量為xs,對(duì)應(yīng)的列向量為若則確定brs為主元項(xiàng)。 第四步第四步，在基B中調(diào)進(jìn)Ps，換出Pjr，得到一個(gè)新的基第五步第五步，在單純形表上進(jìn)行初等行變換，使第s列向量變?yōu)閱挝幌蛄?，又得一張新的單純形表。第六步第六步，轉(zhuǎn)入上述第二步。 Tmssssbbbp,21rsrisisibbbbb000min,1121mrrjjsjjjpPPPPPB線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法例例1：用單純形方法求解線性規(guī)劃問題 2121212132max0, 092123xxZxxxxxx解解：首先引入松弛變量 ，把原問題化為標(biāo)準(zhǔn)形式： 43,xx21432142132132max0,

22、92123xxZxxxxxxxxxx線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法第一步，確定初始單純形表 如下：x1x2x3x4-z02300 x3121310 x492101第二步，判別。在初始單純形表中b01=2, b02=3，所以B1不是最優(yōu)基，進(jìn)行換基迭代。第三步，選主元。 根據(jù)選主元法則，確定主元項(xiàng) 。第四步 ，換基，得一新基 。312b,422ppB 線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法第五步，進(jìn)行初等行變換， 得B2下的新單純形表x1x2x3x4-z-1210-10 x241/311/30 x455/30-1/31第六步，因檢驗(yàn)系數(shù)有正數(shù)b01=1，重復(fù)以

23、上步驟可得對(duì)應(yīng)于 B3=p2,p3的單純形表，檢驗(yàn)各檢驗(yàn)數(shù)可知得最優(yōu)解X1=3,X2=3, X3=0, X4=0:目標(biāo)函數(shù)最大值為 Z=15。x1x2x3x4-z-1500-4/5-3/5x23012/5-1/5x1 310-1/53/5線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法產(chǎn)銷平衡表與單位運(yùn)價(jià)表產(chǎn)銷平衡表與單位運(yùn)價(jià)表 表上作業(yè)法表上作業(yè)法 產(chǎn)銷不平衡的運(yùn)輸問題的求解方法產(chǎn)銷不平衡的運(yùn)輸問題的求解方法線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法一、產(chǎn)銷平衡表與單位運(yùn)價(jià)表一、產(chǎn)銷平衡表與單位運(yùn)價(jià)表 v運(yùn)輸問題還可用產(chǎn)銷平衡表與單位運(yùn)價(jià)表進(jìn)行描述。v假設(shè)某種物資有m個(gè)生產(chǎn)地點(diǎn)

24、Ai（i=1，2，m），其產(chǎn)量（供應(yīng)量）分別為ai（i=1，2，m），有n個(gè)銷地Bj（j=1，2，n），其銷量（需求量）分別為bj（j=1，2，n）。從Ai到Bj運(yùn)輸單位物資的運(yùn)價(jià)（單價(jià)）為Cij。將這些數(shù)據(jù)匯總可以得到產(chǎn)銷平衡表和單位運(yùn)價(jià)表4.3.1。線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法銷地產(chǎn)地產(chǎn)量銷量n21表表4.3.1 產(chǎn)銷平衡表與單位運(yùn)價(jià)表產(chǎn)銷平衡表與單位運(yùn)價(jià)表mnmmnnccccccccc212222111211m21maaa21線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法二、表上作業(yè)法二、表上作業(yè)法 v運(yùn)輸這一類特殊問題可用更加簡(jiǎn)便的求解方法表上作業(yè)法求解，

25、實(shí)質(zhì)仍是單純形法，步驟如下：v（一）（一）找出初始基可行解，即在產(chǎn)銷平衡表上給出m+n-1個(gè)數(shù)字格。v1 確定初始可行基的方法確定初始可行基的方法：最小元素法最小元素法：從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定供銷關(guān)系，然后考慮運(yùn)價(jià)次小的，一直到給出初始基可行解為止。線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法伏格爾法伏格爾法采用最小元素法可能造成其他處的更多浪費(fèi)，伏格爾法考慮最小運(yùn)費(fèi)與次小運(yùn)費(fèi)之間的差額，差額越大，就按次小運(yùn)費(fèi)調(diào)運(yùn)。（二）（二）求各非基變量的檢驗(yàn)數(shù)，即在表上計(jì)算空格的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。若已是最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)入下一步。線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單

26、純形求解方法v計(jì)算非基變量（空格）的檢驗(yàn)數(shù) 時(shí)為最優(yōu)解。v求空格檢驗(yàn)數(shù)的方法有：閉回路法：閉回路法：以某一空格為起點(diǎn)找一條閉回路，用水平或垂直線向前劃，每碰到一數(shù)字格轉(zhuǎn)900后，繼續(xù)前進(jìn)，直到回到起始空格為止。01ijBijPBCc線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法閉回路如圖（a）、（b）、（c）等所示。從每一個(gè)空格出發(fā)一定存在并且可以找到唯一的閉回路。因?yàn)?，m+n-1個(gè)數(shù)字格（基變量）對(duì)應(yīng)的系數(shù)向量是一個(gè)基，任一空格（非基變量）對(duì)應(yīng)的系數(shù)向量是這個(gè)基的線性組合。線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法例1：假設(shè)某種物資共有三個(gè)產(chǎn)地，其日產(chǎn)量分別是：A1為7噸，

27、A2為4噸， A3為9噸；該種物質(zhì)的四個(gè)銷售地，其日銷量分別： B1為3噸， B2為6噸， B3為5噸， B4為6噸；各產(chǎn)地到銷售地的單位物資的運(yùn)價(jià)如表4.3.2所示。在滿足各銷售點(diǎn)需要量的前提下，如何調(diào)運(yùn)該種物資，才能使總運(yùn)費(fèi)達(dá)到最??？銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4A1A2A3317119432101085線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法解：首先列出這一問題的產(chǎn)銷平衡表，見表4.3.5。 表表4.3.5 某物資運(yùn)輸?shù)漠a(chǎn)銷平衡表某物資運(yùn)輸?shù)漠a(chǎn)銷平衡表 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1A2A3749銷量銷量3656線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解

28、方法用最小元素法求解用最小元素法求解第一步，從表4.3.4中找出最小運(yùn)價(jià)為1，將A2 的產(chǎn)品供應(yīng) B1 。在表4.3.5中（ A2 B1 ）的交叉格處填上3，得表4.3.6。將表4.3.4中的B1 列運(yùn)價(jià)劃去，得表4.3.7。銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1A2A33749銷量銷量3656表表4.3.6線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4A1A2A3119432101085表表4.3.7第二步，在表4.3.7未劃去的元素中再找出最小運(yùn)價(jià)為2，確定A2多余的1噸物資供應(yīng)B3 。得表4.3.8。將表4.3.7的行運(yùn)價(jià)劃去，得表4.3.9。

29、線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1A2A331749銷量銷量3656表表4.3.8銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4A1A2A3114310105表表4.3.9線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法第三步 ，按照上述方法直到單位運(yùn)價(jià)表上的所有元素被劃去為止。最后在產(chǎn)銷平衡表上得到一個(gè)調(diào)運(yùn)方案，即初始基可行解，見表4.3.8。銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1 A2A3341749銷量銷量3656表表4.3.10線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4A1A2A3114

30、105銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1 A2A33641749銷量銷量3656線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4A1A2A3105銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1 A2A336413749銷量銷量3656線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4A1A2A310銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1 A2A3364133749銷量銷量3656線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法伏格爾法的步驟是：伏格爾法的步驟是：第一步：在表4.3.4中分別計(jì)算出各行、各列的

31、最小運(yùn)費(fèi)和次最小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行，見表4.3.11。銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4行差額行差額 A1A2A3317119432101085011列差額列差額 2513表表4.3.11線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法第二步：從行或列差額中選出最大者，選擇它所在行或列中的最小元素。在表4.3.11中，可確定A3的產(chǎn)品應(yīng)首先供應(yīng)B2，得表4.3.12。將單位運(yùn)價(jià)表中的列的數(shù)字劃去，得表4.3.13。線性規(guī)劃及其單純形求解方法線性規(guī)劃及其單純形求解方法表表4.3.12銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1A2A36749銷量銷量3656銷地產(chǎn)地B1B2B3B4A1A2A331732101085表表4.3.13