第03章線性規(guī)劃

1、第3章 線性規(guī)劃數(shù)學(xué)規(guī)劃是系統(tǒng)工程中最重要的分析方法之一，是運(yùn)籌學(xué)的主要分支。它包括線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃和動態(tài)規(guī)劃等。30年代初出現(xiàn)的線性規(guī)劃，1947年丹茨基（George BDantzig）發(fā)明單純形法，理論上才得到完善。隨著電子計算機(jī)的發(fā)展，成千上萬個約束條件和變量的大型線性規(guī)劃問題都可以求解。因此，無論從理論的成熟性看，還是從應(yīng)用的廣泛性看，線性規(guī)劃都是運(yùn)籌學(xué)的一個重要分支。它在工業(yè)、農(nóng)業(yè)、交通運(yùn)輸、軍事和計劃管理等各方面都愈來愈得到廣泛地應(yīng)用。l 線性規(guī)劃問題及其數(shù)學(xué)模型在生產(chǎn)過程中，要想提高工作效率和經(jīng)濟(jì)效益，一般有兩條途徑：一是進(jìn)行技術(shù)改造，改進(jìn)生產(chǎn)手段和條件。（比如增

2、添設(shè)備、改進(jìn)工藝、挖掘潛力等）二是在生產(chǎn)手段和條件都不變的情況下，改善生產(chǎn)的組織和計劃管理，作出最優(yōu)安排，使生產(chǎn)手段和條件得到充分的利用。線性規(guī)劃方法就是解決后一類問題的工具。后一類問題又可分為兩個方面：一是在一定限制條件下，使得工作成果盡可能大；二是為完成既定任務(wù)，使資源消耗盡可能小。例3一1 資源利用問題。某工廠計劃生產(chǎn)A、B兩種產(chǎn)品，生產(chǎn)這兩種產(chǎn)品需要煤、電力和勞動力三種資源。已知該廠可利用的煤有360t，電力有200kw，勞動日有300個，生產(chǎn)每千克產(chǎn)品的資源消耗量和能獲得的利潤如表31所示。問該廠應(yīng)生產(chǎn)A，B兩種產(chǎn)品各多少千克才能使總利潤最大？ 解 設(shè)生產(chǎn)A，B兩種產(chǎn)品各為x1，x2

3、 kg，則該問題可歸結(jié)為，求一組變量xl，x2滿足下列條件：使得總利潤f=7x1+12x2取得最大值。例32 下料問題。某工廠制造一種機(jī)床，每臺機(jī)床需A、B、C三種不同長度的軸各一根，其毛坯長度；A為2.9m，B為2.1m，C為1.5m，它們用同一種圓鋼來下料，每根圓鋼長為7.4m。要造100臺機(jī)床，問如何下料最好？試建立其數(shù)學(xué)模型（不考慮下料截口損耗）?！苯?將各種可能的下料方案排列如表32。設(shè)所用圓鋼總數(shù)為f根，第j種下料方案。所用圓鋼數(shù)為xj根，則由題意, 上述模型即為所求模型。通過分析表32，發(fā)現(xiàn)其中的方案3、5、7、8的料頭過長，不經(jīng)濟(jì)，如果把它們舍棄，對剩下的4種方案進(jìn)行搭配，仍然

4、可以滿足題意。為此可以將上述模型簡化為下列模型（保持變量下標(biāo)不變）。例33 運(yùn)輸問題。設(shè)有甲、乙、丙三個倉庫，存有某種貨物分別為7t、4t和9t?，F(xiàn)在要把這些貨物分別送往A、B、C、D四個商店，其需要量分別為3t、6t、5t和6t，各倉庫到各商店的每噸運(yùn)費(fèi)以及收、發(fā)總量如表33所示。 現(xiàn)在要求確定一個運(yùn)輸方案：從哪一個倉庫運(yùn)多少貨到哪一個商店，使得各個商店都能得到貨物需要量，各個倉庫都能發(fā)完存貨，而且總的運(yùn)輸費(fèi)用最低？試建立其數(shù)學(xué)模型。解 記總運(yùn)費(fèi)為Z，設(shè)xij為i倉庫到j(luò)商店的貨物量，其中i=1，2，3分別代表甲、乙、丙倉庫，j=1，2，3，4分別代表A、B、C、D商店，則根據(jù)題意：上述各例

5、，都是要求一組非負(fù)變量，在滿足一組線性等式或線性不等式的前提下，使一個線性函數(shù)取得最大值或最小值，這一類問題就稱為線性規(guī)劃問題。 將上述問題得出的數(shù)學(xué)表達(dá)式加以概括和抽象，就可得到線性規(guī)劃問題的一般數(shù)學(xué)模型：求一組變量xj，j1，2，n，滿足條件使函數(shù)取得最大值或最小值。如果簡寫，則線性規(guī)劃問題的數(shù)學(xué)模型可以表示為 (3-1) (3-2)式（31）稱為目標(biāo)函數(shù)，式（32）稱為約束條件。式中max（min）f目標(biāo)函數(shù)取最大（最?。┲担粁j決策變量，又稱為生產(chǎn)活動或活動方式；cj決策變量在目標(biāo)函數(shù)中的系數(shù)，又稱為利益系數(shù)、價值或效果系數(shù)； aij決策變量在約束條件中的系數(shù)，又稱為投入產(chǎn)出系數(shù)或技術(shù)

6、系數(shù)； bi資源限制量； n決策變量的個數(shù)； m約束條件（不包括非負(fù)約束條件）的個數(shù)。把滿足約束條件式（32）的任意一組解稱為線性規(guī)劃問題的可行解，使得目標(biāo)函數(shù)f取得最優(yōu)值的可行解稱為線性規(guī)劃問題的最優(yōu)解。如何求得線性規(guī)劃問題的最優(yōu)解，就是本章所要討論的中心問題。2 線性規(guī)劃問題的圖解法 在介紹線性規(guī)劃問題的一般解法之前，我們先介紹只含有兩個變量的線性規(guī)劃問題的圖解法。圖解法不僅簡單而且直觀，有助于了解線性規(guī)劃問題求解的基本原理。例34 考慮下列線性規(guī)劃問題解 在該問題的約束條件中，共有五個不等式（包括兩個非負(fù)約束條件）。在以xl，x2為坐標(biāo)軸的直角坐標(biāo)系中，每一個不等式的解的集合均為一個半平

7、面。所以同時滿足五個不等式的解的集合一定是五個半平面的交集，稱為可行域，即凸五邊形 OABCD。如圖 31所示?？尚杏虻奈鍌€頂點(diǎn)坐標(biāo)分別為O（0，0），A（0，2），B（l，4），C（4，1），D（2，0）。 下面討論如何在可行域上找到使目標(biāo)函數(shù)取得最小值的點(diǎn)，即問題的最優(yōu)解。 對于目標(biāo)函數(shù)f=-x1+x2，若令f=f0為一常數(shù)，則目標(biāo)函數(shù)在坐標(biāo)平面上表現(xiàn)為一條確定的直線，如果f0 取不同的值時，那么目標(biāo)函數(shù)在平面坐標(biāo)上是一組平行直線束，直線的斜率為1。如果知道目標(biāo)函數(shù)沿某一方向移動時函數(shù)值減少（或增大），那么根據(jù)目標(biāo)函數(shù)的優(yōu)化方向，便很容易求得使目標(biāo)函數(shù)取得最大值（或最小值）的解，即問題的最

8、優(yōu)解。 由目標(biāo)函數(shù)f=-x1+x2可知，如果x1增大，x2減小，則f減小。因此為使f取得最小值，目標(biāo)函數(shù)線應(yīng)沿著x1增大，x2減小的方向移動。顯然點(diǎn)C是可行域上使f取得最小值的點(diǎn)，于是得到問題的最優(yōu)解為 x1=4，x2=1對應(yīng)的目標(biāo)函數(shù)的最小值為min f-4+13 同樣，如果目標(biāo)函數(shù)為求最大值，則點(diǎn)B為問題的最優(yōu)解，即 x1=2, x2=4對應(yīng)的目標(biāo)函數(shù)的最大值為 max f-1+4=3。 如果將例 34中的目標(biāo)函數(shù)變?yōu)?min f=-x1+2x2，約束條件不變，由于目標(biāo)函數(shù)的斜率與約束條件x1-2x22對應(yīng)的邊界直線的斜率相同，根據(jù)上述方法可知，線段CD上的任一點(diǎn)都是問題的最優(yōu)解，即問題有

9、無窮多個最優(yōu)解。 如果將例3-4中的目標(biāo)函數(shù)變?yōu)閙ax f=x1+x2，去掉約束條件x1+x25，則問題的可行域無界，目標(biāo)函數(shù)的最大值趨于無窮大。這種情況無最優(yōu)解。 如果在例3-4的約束條件中再增加一個約束條件x1+x26，則可行域是空集，這時無可行解，當(dāng)然也就無最優(yōu)解了。 通過兩個變量線性規(guī)劃問題的圖解法，可以得到如下結(jié)論： 1）線性規(guī)劃問題的所有可行解組成的可行域是一個凸集，即可行域上任意兩點(diǎn)之間的連線都在可行域內(nèi)。 2）若一個線性規(guī)劃問題存在最優(yōu)解，則至少有一個最優(yōu)解在可行域的頂點(diǎn)上達(dá)到；若在兩個頂點(diǎn)上同時達(dá)到最優(yōu)，則這兩頂點(diǎn)連線上的任一點(diǎn)都是最優(yōu)解，這時稱有無窮多個最優(yōu)解。 3）若可行

10、域呈現(xiàn)無界區(qū)域，則可能有最優(yōu)解，也可能出現(xiàn)最優(yōu)解無界的情形，這時稱最優(yōu)解不存在或無最優(yōu)解。 4）若可行域為空集，這時無可行解，當(dāng)然也就無最優(yōu)解。上述結(jié)論對于含有兩個以上變量的線性規(guī)劃問題同樣適用。圖解法雖然直觀、簡便，但只能用于兩個，最多三個變量的線性規(guī)劃問題，當(dāng)變量個數(shù)超過三個時，用圖解法就很難處理了。因此在后面將要介紹線性規(guī)劃問題的一般解法單純形法。3 線性規(guī)劃問題的標(biāo)準(zhǔn)形式及其解的概念由于具體問題的線性規(guī)劃模型是各式各樣的，為了求解的方便，就需要把線性規(guī)劃問題的一般數(shù)學(xué)形式化成如下標(biāo)準(zhǔn)形式 下面討論如何將一般形式的線性規(guī)劃問題化為標(biāo)準(zhǔn)形式。3.1 含有不等式約束條件 分兩種情形討論：1）

11、若原問題的第 i個約束條件為，則可在不等式的左邊加上一個新的變量使其變?yōu)榈仁郊s束，即：稱為松弛變量。2）若原問題的第i個約束條件為，則可在不等式左邊減去一個新的變量，使其變?yōu)榈仁郊s束，即稱為剩余變量，也可稱為松弛變量。 應(yīng)該指出，引人松弛變量和剩余變量后，對目標(biāo)函數(shù)無任何影響，因為它們在目標(biāo)函數(shù)中的系數(shù)全為零。3.2 含有負(fù)的右邊項 若原問題的第i個約束條件的右邊項bi0，則用-1同時乘以約束條件的兩邊，使右邊大于0。3.3 含有自由變量 若原問題中第j個變量xj沒有約束，則xj就叫自由變量。自由變量可用兩非負(fù)變量之差代換，即，令，并代人約束條件和目標(biāo)函數(shù)中，便可消去自由變量。3.4 目標(biāo)函數(shù)

12、為求最小值例35 將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式。解 這個問題可以按以上介紹的標(biāo)準(zhǔn)化方法進(jìn)行。 1）令，或?qū)懗伞?2）在第一個約束條件中引人松弛變量x6，第二個約束條件中引人剩余變量x7。 3）對第三個約束條件兩邊同乘以-1。 4）將引入的變量代入目標(biāo)函數(shù)和約束條件，并令f'=-f,把求 min f變?yōu)榍?max f'，于是得到該問題的標(biāo)準(zhǔn)形式為 解此規(guī)劃問題，得到 x4、x5和 max f的值，則 x3=x4-x5，min f=max f，從而可得到原問題的解。 在討論線性規(guī)劃問題的解法之前，先來介紹一下標(biāo)準(zhǔn)形式線性規(guī)劃問題的解的概念。 與一般形式的線性規(guī)劃問題類似，把滿足約

13、束條件式（33）的解稱為可行解，把滿足目標(biāo)函數(shù)的可行解稱為最優(yōu)解，或者說使目標(biāo)函數(shù)達(dá)到最大值的可行解叫最優(yōu)解。對于標(biāo)準(zhǔn)形式的線性規(guī)問題，其約束條件式（33）為 在此約束條件中，前m個等式構(gòu)成線性方程組，對此方程組，若m=n，且系數(shù)行列式不為零，則方程組有唯一組解，故不存在優(yōu)化問題。若mn，一般來說mn，如果方程組的系數(shù)矩陣的秩為m，則該方程組有無窮多個解。假設(shè)前m個變量的系數(shù)列向量是線性獨(dú)立的，構(gòu)成的系數(shù)矩陣稱為線性問題的一個基；稱P1、P2、Pm為基向量，稱與基向量對應(yīng)的變量x1, x2，xm。為基變量，其它變量稱為非基變量。若令非基變量等于零，則可求得一個解為這樣的解稱為基本解，它的非零變

14、量的個數(shù)不大于秩m?；窘獠灰欢ǘ际强尚械模ㄍ瑫r要滿足非負(fù)性條件）。若基本解同時滿足非負(fù)條件，就稱為基本可行解，對應(yīng)于基本可行解的基稱為可行基。若基本可行解中的非零變量的個數(shù)小于m，即基變量出現(xiàn)零值時，則此基本可行解稱為退化的基本可行解。當(dāng)其非零變量的個數(shù)等于m，即基變量均為正值時，則此基本可行解稱為非退化的基本可行解。顯然，如果基矩陣B為m階單位陣，則問題的一個基本可行解為線性規(guī)劃問題的一個基本可行解，對應(yīng)于可行域上的一個頂點(diǎn)。若線性規(guī)劃問題有最優(yōu)解，則必定在某個頂點(diǎn)處得到。雖然頂點(diǎn)數(shù)目是有限的，它不超過采用枚舉法找出所有基本可行解，然后一比較，最終可以找到最優(yōu)解。但當(dāng)n、m相當(dāng)大時，這種辦

15、法是行不通的。所以下面要介紹一種更好的方法，即單純形法。4 單純形法單純形法（Simplex Method）是美國學(xué)者丹茨基（GBDantzig）于 1947年提出的。這一方法從根本上解決了線性規(guī)劃的求解問題。 單純形法的基本思路是：根據(jù)問題的標(biāo)準(zhǔn)形式，從可行域中一個基本可行解（一個頂點(diǎn)）開始，轉(zhuǎn)換到另一個基本可行解（頂點(diǎn)），并使目標(biāo)函數(shù)的值逐步增大；當(dāng)目標(biāo)函數(shù)達(dá)到最大值時，就得到了問題的最優(yōu)解。4.1 單純形法引例 下面依據(jù)例 31，來引入單純形算法。原線性規(guī)劃問題的模型為第一步：將一般形式的線性規(guī)劃問題標(biāo)準(zhǔn)化。在約束條件中引人松弛變量x3、x4、x5有 第二步：確定初始基本可行解。 為了確

16、定初始基本可行解，首先要找出初始可行基。由3可知，如果在約束方程的系數(shù)矩陣中能找到m個線性無關(guān)的單位向量，就能很容易地得到問題的一個初始基本可行解。若原問題的約束條件（不包括非負(fù)約束條件，下同）為一組“” 不等式，標(biāo)準(zhǔn)化后，可以松弛變量作為基變量，其余的變量為非基變量，令非基變量等于零，便可立即得到一個初始基本可行解。對于本例，x3、x4、x5為基變量，x1、x2為非基變量，則問題的一個初始基本可行解為X0（0 0 360 200 300）T，此時的目標(biāo)函數(shù)值f7x1+12x20，意味著工廠沒有進(jìn)行生產(chǎn)，對應(yīng)的利潤為零。這正是我們生產(chǎn)規(guī)劃的開始。 若原問題的約束條件為一組“”不等式或一組等式或

17、三種約束的混合，標(biāo)準(zhǔn)化后，如果約束方程的系數(shù)矩陣中不存在m個線性無關(guān)的單位向量，就要設(shè)法構(gòu)成m個不同的單位列向量。有關(guān)這個問題將在后面進(jìn)行討論。 為明顯起見，把基變量放在等式左邊，非基變量放在等式右邊，由式（36）得：相應(yīng)的目標(biāo)函數(shù)用非基變量表示為：從目標(biāo)函數(shù)表達(dá)式可以看出：非基變量x1、x2的系數(shù)都是正數(shù)，因此增加x1或x2均可使目標(biāo)函數(shù)f增加。所以只要在目標(biāo)函數(shù)的表達(dá)式中還存在有正系數(shù)的非基變量，就表明目標(biāo)函數(shù)還有增加的可能，就需要將非基變量與基變量進(jìn)行對換。單純形法的實質(zhì)上就是進(jìn)行基變量和非基變量的代換過程。新進(jìn)入左邊的變量叫換入變量，被代換到右邊的變量叫換出變量。每完成一次代換，就是一

18、次選代，而對應(yīng)的目標(biāo)函數(shù)值就相應(yīng)地有所增加，至少也與代換前相同。 第三步：確定換入換出變量，進(jìn)行第一次選代。 在進(jìn)行單純形法迭代時，每次只能代換一個變量。一般選擇正系數(shù)最大的那個非基變量為換入變量，并成為新的基變量，本例中x2為換入變量。同時，還要從原來的基變量中確定出一個為換出變量，成為新的非基變量。換出變量的確定要經(jīng)過計算換入變量的最大步長。x2作為換入變量，由于受到有關(guān)資源的限制，是不能隨意安排調(diào)整的。我們把資源允許的最大調(diào)整量叫最大步長。故當(dāng)x1=0時，要保證x3、x4、x50，有 顯然，為同時滿足以上三個條件，x2的調(diào)整量只能是 x2=min90，40，30=30即x2=30是調(diào)整的

19、最大步長。因為x2的最大步長是由式（3-7）中的第3個約束方程求得的，即當(dāng)x1=0，x2=30時，x50，因此x5就是換出變量，這樣一來就得到了新的基變量x3、x4、x2。，新的非基變量為xl、x5，此時需要把式（3-7）中x2與x5的位置對換。由式（37）中的第3式得將上式代人式（3-7）中的第1，第2兩式，消掉x2，有把目標(biāo)函數(shù)中的基變量用非基變量代替，得到調(diào)整以后的目標(biāo)函數(shù)為當(dāng)非基變量xl=x50時，得到另一個基本可行解是目標(biāo)函數(shù)值f=360。由此可見，調(diào)整x2后，目標(biāo)函數(shù)值增加了360。 從目標(biāo)函數(shù)的表達(dá)式可以看出，非變量x1的系數(shù)為正，說明調(diào)整x1將會使目標(biāo)函數(shù)值繼續(xù)增加，x1不是規(guī)

20、劃問題的最優(yōu)解。 第四步：確定新的換人換出變量，進(jìn)行第二次迭代。由于非基變量x5在目標(biāo)函數(shù)中的系數(shù)為-1.2，調(diào)整x5將使目標(biāo)函數(shù)值減少，又因目標(biāo)函數(shù)中只有x1的系數(shù)為正，于是便知x1是新的換人變量，而新的換出變量還要通過計算最大步長來確定。xl的最大步長為 x1min30.77，20，10020x1的最大步長是由式（38）中的第二個方程確定的，對應(yīng)的基變量x4為新的換出變量，由式（3一8）中的第二式得將上式代人式（38）的第一、第三式，消掉x1，有調(diào)整后的目標(biāo)函數(shù)為 當(dāng)x4=x5=0時，可得到一個新的基本可行解為 X=(20 24 84 0 0）T，目標(biāo)函數(shù)值得 f428。 因為調(diào)整后的目標(biāo)

21、函數(shù)的表達(dá)式中非基變量的系數(shù)全部非正，所以X2為最優(yōu)解。即當(dāng)A產(chǎn)品生產(chǎn)20kg，B產(chǎn)品生產(chǎn)24kg，工廠才能獲得最大利潤428百元。x384代表煤的剩余量為 84t，x4x50表示電力和勞動日完全利用，沒有剩余。42 單純形表解法 上面的引例說明了用單純形法解線性規(guī)劃問題的基本思路和理論依據(jù)。但在實際求解中，用上述方法比較麻煩，而且容易出錯，故多采用單純形表解法，下面仍以上面的例子來說明表上求解的步驟和方法，并引出一般線性規(guī)劃問題的解法。 第一步：標(biāo)準(zhǔn)化（見前解法第一步）。 第二步：找出初始基變量，并將目標(biāo)函數(shù)中的基變量用非基變量代替。 l）檢查約束方程的系數(shù)矩陣是否含有m階單位陣。若沒有，則

22、設(shè)法構(gòu)造。m階單位陣對應(yīng)的變量為基變量，其余變量為非基變量。 上面的問題中3階單位矩陣對應(yīng)的變量x3、x4、x5為基變量，x1、x2為非基變量。 2）檢查目標(biāo)函數(shù)中是否含有基變量，如果有，則用非基變量加以代換。上面問題的目標(biāo)函數(shù)中不含有基變量，故不需代換。 第三步：作初始單純形表。 初始單純形表就是把線性規(guī)劃模型中的變量和相關(guān)的系數(shù)規(guī)則地排成一種表格，它和線性規(guī)劃模型具有一對應(yīng)的關(guān)系。 對于上面的問題，可將目標(biāo)函數(shù)寫成類似于約束方程的形式，即 f7xl12x20其初始單純形表如表34所示。 初始單純形表的最上一行存放全體變量，最左一列存放基變量，最右一列存放約束方程右邊項，中間存放約束方程組中

23、對應(yīng)變量的系數(shù)，最下一行存放目標(biāo)函數(shù)中變量的系數(shù)。注意這里的目標(biāo)函數(shù)中對應(yīng)于基變量的系數(shù)必須為零，右下角存放目標(biāo)函數(shù)中常數(shù)項的相反數(shù)。 初始單純形表的最后一列代表一組初始可行解，每完成一次迭代，就有一個新的單純形表。在單純形表中，目標(biāo)函數(shù)f所在的行叫判別數(shù)或檢驗數(shù)行，記為j，j1，2，n，因為在目標(biāo)函數(shù)中不含基變量，所以基變量所對應(yīng)的判別數(shù)為零，如表34中基變量x3、x4、x5對應(yīng)的判別數(shù)為零。 在得到問題的一個基本可行解后，就需要判斷它是否是最優(yōu)解，為此下面介紹最優(yōu)解的判別準(zhǔn)則。 最優(yōu)解判別準(zhǔn)則：當(dāng)所有判別數(shù)全部非正時，即j0，j1，2，n時，對應(yīng)的基本可行解為最優(yōu)解。 由此準(zhǔn)則可知，經(jīng)有限

24、次迭代后，若所有判別數(shù)全部非正，則得到了問題的最優(yōu)解，否則應(yīng)繼續(xù)迭代。這個準(zhǔn)則和前述引例中判斷最優(yōu)解的方法是一致的。由表34可知，問題的判別數(shù)中含有正的判別數(shù)，故初始基本可行解不一定是最優(yōu)解。 第四步：確定主元。 在所有正判別數(shù)中，最大判別數(shù)所在的列叫主元列，主元列對應(yīng)的變量即為換人變量，若則k所在的列為主元列，對應(yīng)的變量xk為換人變量。若上式中的最大值多于一個時，即原則上可以在k、r、對應(yīng)的變量中任選一個作為換人變量，但為了運(yùn)算過程有規(guī)可循，我們規(guī)定，取下標(biāo)k、r、中最小的判別數(shù)對應(yīng)的變量為換人變量。當(dāng)主元列確定后，就可按下式確定主元。若則alk所在的行叫主元行，對應(yīng)的基變量為換出變量，主元

25、列與主元行的交叉元素alk。就是主元。當(dāng)最小比值不唯一時，任取其中一行作為主元行。顯然，主元所對應(yīng)的非基變量為換人變量，主元所對應(yīng)的基變量為換出變量。對于上例，由知，x2為換人變量。由知，換出變量為x5，主元為10，為清楚起見，主元用方框圈起來。 注意，若有一個判別數(shù)k0，并且對一切 il，2，m有aik0，那么該線性規(guī)劃問題無解，即無有限值最優(yōu)解。這就是無界解的判別準(zhǔn)則。 第五步：開始迭代。 單純形迭代實際上是對單純形表作初等行變換。首先把換人變量放人基底，然后對主元行所有元素除以主元，化主元為1，接著對其它行（包括目標(biāo)函數(shù)行）施行行變換，化主元列其它元素為零，至此第一次迭代結(jié)束。檢查表中的

26、判別數(shù)是否全部非正，若是，則迭代終止，否則繼續(xù)迭代。上面問題的第一次選代結(jié)果如表35所示。根據(jù)表35，可以寫出第一次迭代后線性規(guī)劃問題的約束方程為目標(biāo)函數(shù)為 對以上兩式稍作變換就得到了第一種解法的形式。可見單純形表解法與前述引例方法是一致的。由上表可得到問題的一個基本可行解為X（0 30 240 50 0）T，相應(yīng)的目標(biāo)函數(shù)值為 f 360。因此，單純形表的最右一列表示問題的一個基本可行解中基變量的值，右下角元素的相反數(shù)表示相應(yīng)的目標(biāo)函數(shù)值。因上表中的判別數(shù)不全非正，故需繼續(xù)迭代。 第六步：進(jìn)行第二次迭代。判別數(shù)中只有x1對應(yīng)的判別數(shù)為正，故其為新的換人變量。由知2.5為主元，對應(yīng)的基變量x4

27、為換出變量。其退出基底，x1進(jìn)人基底，化主元為1，主元列其它元素為零，第二次迭代結(jié)束，結(jié)果如表36所示。 由表36可知，全部判別數(shù)非正，于是得到了問題的最優(yōu)解為 X（20 24 84 0 0）T目標(biāo)函數(shù) f 428。可見單純形表迭代結(jié)果與41中迭代結(jié)果完全相同。4.3 單純形表的另兩種常見形式 大多數(shù)線性規(guī)劃問題標(biāo)準(zhǔn)化后，其約束方程組的系數(shù)矩陣中并不含有m階單位陣。為了得到問題的一組初始基變量，通常采用的方法是在每一個約束方程中加人一個非負(fù)的虛擬變量，這種虛擬的變量稱為人工變量。對于一個標(biāo)準(zhǔn)化的線性規(guī)劃問題，其約束方程為在第i個約束方程中加人一個人工變量Xn+1，得到 如果以xn+l，xn+m

28、為基變量，x1，xn為非基變量，便可得到問題的一個初始基本可行解為X0（0 0 0 b1 b2 bm）T。因為人工變量是加人到原約束方程組中的虛擬變量，為了不改變原來問題的性質(zhì)，就應(yīng)將它們從基變量中逐漸替換掉，即使人工變量為零。處理人工變量的方法有兩階段法和大M法，下面我們分別介紹這兩種方法。4.3.l 兩階段法 兩階段法是將加入人工變量后的線性規(guī)劃問題分兩階段來求解。第一階段是借助于以下輔助線性規(guī)劃問題，為原問題求得一個基本可行解。 用單純形法對上述問題求解，若得到W0，即所有的人工變量都為零，表示原問題已得到了一個基本可行解；若W0，即不是所有人工變量都為零，表示原問題無可行解，應(yīng)停止計算

29、。 第二階段是從第一階段得到的基本可行解開始，繼續(xù)用單純形法進(jìn)行迭代，直到找出原問題的最優(yōu)解或判斷無最優(yōu)解。 以上介紹的方法是對每個約束方程中都加人人工變量。如果原問題約束方程的系數(shù)矩陣中存在有一些單位向量，為減少計算工作量，可以只在部分約束方程中加入人工變量。下面通過一個例子說明兩階段問題的求解步驟和方法。例36 用兩階段法求解下列線性規(guī)劃問題。 解 第一步：標(biāo)準(zhǔn)化。在第一個約束條件中引入松弛變量x4，第二個約束條件中引人剩余變量x5，得到原問題的標(biāo)準(zhǔn)形式為第二步：確定初始基變量，并將目標(biāo)函數(shù)中的基變量用非基變量代替。式（310）的約束方程中只有x4的系數(shù)向量為單位向量，為形成3階單位矩陣，

30、在第二和第三個約束方程中分別引入人工變量x6和x7，得第一階段的規(guī)劃問題為x4，x6，x7為初始基變量，把目標(biāo)函數(shù)w中的基變量用非基變量代替，有即 如果原問題的目標(biāo)函數(shù)中也含有基變量時，也必須用非基變量代替。 第三步：作初始單純形表。作初始單純形表的基本要求與前面介紹的完全一樣，唯一的區(qū)別是增加了第一階段問題的目標(biāo)函數(shù)W行，見表37。 第四步：確定主元。 第一階段問題以W為目標(biāo)函數(shù)，主元的確定方法與前面相同。 第五步：進(jìn)行第一階段迭代。 與前述方法相同，即換出變量退出基底，換人變量進(jìn)人基底，化主元為1，主元列其它元素（包括f行的元素）為零，完成一次迭代。若行的判別數(shù)不全非正，則繼續(xù)選代。 該問

31、題經(jīng)過二次迭代后，w行的判別數(shù)全部非正，且有 max w0，故得到了原問題的一組基變量x4、x2、x3，至此第一階段迭代結(jié)束。 第六步：進(jìn)行第二階段迭代。從第一階段的最終單純形表中去掉人工變量x6、x7所對應(yīng)的列及w行，得到第二階段的單純形表，如表38所示。 經(jīng)過一次迭代后，判別數(shù)全部非正，得到原問題的最優(yōu)解為 X（4 1 9 0 0）T相應(yīng)的目標(biāo)函數(shù)值f2。4.3.2 大M法大M法的基本思路是對于標(biāo)準(zhǔn)形式的線性規(guī)劃問題，引人人工變量后將其改造為其中 M為充分大的正數(shù)，記為M1，下面舉例說明大M法的具體迭代過程。例37 求解下列線性規(guī)劃問題。解 引人剩余變量和人工變量將上面的線性規(guī)劃模型化為標(biāo)

32、準(zhǔn)形式如下根據(jù)模型式（313）建立初始單純形表，如表39所示。因為M是充分大的數(shù)，所以判別數(shù)行的全部元素小于等于零，說明此表已達(dá)到最優(yōu)，最優(yōu)解為則 由此可見，凡約束條件為大于或等于型不等式時，均需引入人工變量，在目標(biāo)函數(shù)中，人工變量前面均應(yīng)乘上系數(shù) M，M1，而且，在極大值問題中，M前面為負(fù)號。這樣，可以確保在獲得最優(yōu)解時消去人工變量，如果人工變量不能通過迭代而消去，則說明該問題無最優(yōu)解。 到此為止，對于任何形式的線性規(guī)劃問題，總可以利用單純形法、兩階段法或大M法對其求解。5 改進(jìn)單純形法 對于較簡單的線性規(guī)劃問題，可以用單純形表法求解。但當(dāng)線性規(guī)劃問題的規(guī)模較大時，用單純形表求解是非常困難的

33、，甚至是不可能的。為此就出現(xiàn)了一種新的算法改進(jìn)單純形法。這種方法從實質(zhì)上來說是一種矩陣算法，主要是通過基矩陣求逆來實現(xiàn)單純形迭代。同時，這種方法是用計算機(jī)求解線性規(guī)劃問題的主要算法。對于標(biāo)準(zhǔn)形式的線性規(guī)劃問題如果令則式（314）可用矩陣形式表示為如果用列向量Pj，j1，2，n代表矩陣A的第j列，則有設(shè)前m個列向量是線性獨(dú)立的，則B（P1 P2 Pm）為線性規(guī)劃問題的基矩陣。其余列向量構(gòu)成的矩陣N（Pm+1 Pn）稱為非基子矩陣。A（B N）。基矩陣B對應(yīng)的變量為基變量，用XB表示，XB（xl x2 xm）T，非基子矩陣N對應(yīng)的變量為非基變量，用 XN表示，XN=(xm+1 xn)T，則有 X（

34、XBXN）T。同樣地，C可以表示為C=（CBCN），CB=（c1c2cm），CN=（cm+1cn）。于是式（3一15）可改寫為 如果判別數(shù)，則為問題的最優(yōu)可行解，相應(yīng)的目標(biāo)函數(shù)值，否則，應(yīng)確定新的基矩陣B1繼續(xù)迭代。 我們知道，單純形迭代實際上是由一個基矩陣到另一個基矩陣的過程，而且每次迭代只能是一個變量換入，一個變量換出，即基陣中只有一個列向量發(fā)生變化。設(shè) BO=（P1 P2. Pl Pm）為初始基矩陣。若對應(yīng)的判別數(shù)行向量。不全非正，即基矩陣B0不是最優(yōu)基，根據(jù)前述方法確定的換人變量為xk，換出變量xl，則以列向量Pk代換Pl得到新的基矩陣為。由前面的推導(dǎo)可知，如果求得了，那么就可以求出一

35、組新的基本可行解、相應(yīng)的目標(biāo)函數(shù)值和判別數(shù)等。由此可見，在改進(jìn)單純形法計算中，關(guān)鍵是每次迭代時基矩陣的逆陣B-1。下面討論其求法。 與單純形表解法類似，改進(jìn)單純形法通常也是用m個單位向量構(gòu)成的單位陣作為初始基矩陣，即以列向量Pk代換Pl后，得到的新基矩陣為 因此，基矩陣求逆實際上就是計算形如上式這種矩陣的逆，根據(jù)線性代數(shù)的理論，不難求得 Bl的逆 Bl-1為改進(jìn)單純形法的計算步驟與單純形法類似，下面通過一個具體實例加以說明。例38 用改進(jìn)單純形法求解下列線性規(guī)劃問題。解 第一步：標(biāo)準(zhǔn)化。引人松弛變量x3，x4，x5，得第二步：確定初始可行解。由上式得取x3、x4、x5為初始基變量，初始基為則有

36、由此可得非基變量的列向量為初始基本可行解為相應(yīng)的目標(biāo)函數(shù)值為非基變量判別數(shù)為 以上結(jié)果可列成表311的形式。實際上表311是一種特殊形式的單純形表，它是按表310的格式構(gòu)造的。因N00，故 BO不是最優(yōu)基。第三步：確定新基，進(jìn)行第一次迭代。由max 1，2 12，xl為換入變量，P10為換入列向量。由可知，6為主元，x5為換出變量，新的基變量為x3，x4，x1，故得新基B1為此時有由此可得XB0=b因20，故B1不是最優(yōu)基，以上結(jié)果可用表 312表示。第四步：確定新基，進(jìn)行第二次迭代。20，故x2為換入變量，P21為換人列向量同樣地，按照第二步的方法可知，x3為換出變量，P3l為換出列向量，新

37、的基變量為x2、x4、xl，所得到的新基為此時有由此可得因判別數(shù)N20，所以迭代終止，得到問題的最優(yōu)解為X（114 94 0 l2 0）T相應(yīng)的目標(biāo)函數(shù)值f2314上述結(jié)果可用表313表示。從以上運(yùn)算過程可以看出，作為手算來說，采用改進(jìn)單純形并不方便，而且很容易出錯，但對于計算機(jī)而言，用改進(jìn)單純形法不僅可以節(jié)約內(nèi)存，而且運(yùn)算量較小，所以對求解大型的線性規(guī)劃問題較為有利。6 對偶單純形法6.1 線性規(guī)劃的對偶問題 我們先看一個簡單的例子，然后提出對偶問題。 例39 某廠在計劃期內(nèi)要安排生產(chǎn)A、B兩種產(chǎn)品，這兩種產(chǎn)品分別需要在甲、乙、丙三種不同的設(shè)備上加工，有關(guān)數(shù)據(jù)如表314所示。問應(yīng)如何安排生產(chǎn)

38、計劃才能使利潤最大？解 如果設(shè)A、B兩種產(chǎn)品生產(chǎn)的件數(shù)分別為xl、x2，則這個問題可以歸結(jié)為求解下列線性規(guī)劃問題（LP1）現(xiàn)在從另一個角度來考慮這個問題。假設(shè)該廠的決策者，決定不生產(chǎn)產(chǎn)品A、B而將生產(chǎn)設(shè)備的有效臺時用于接受外加工來收取加工費(fèi)。此時就要考慮給每臺設(shè)備的臺時如何定價。設(shè)y1、y2 、y3分別表示設(shè)備甲、乙、丙每臺時的價格。在定價時必須考慮到，將生產(chǎn)一件產(chǎn)品A的各設(shè)備的臺時用于外加工時，所得加工費(fèi)不得低于生產(chǎn)一件產(chǎn)品A可得的利潤，即否則該廠不會接受外加工，而寧愿自己生產(chǎn)產(chǎn)品A。同理有若把設(shè)備的所有臺時都用于外加工，總的收人為因為在定價時，受市場調(diào)節(jié)的影響不能把價格任意提高，故其定價方

39、案只有使總收人g（即委托加工單位支出的總加工費(fèi)用）盡可能低，才能得到其它單位的委托加工。因此該廠只能得到g的最小值，于是，這個問題可以用下列線性規(guī)劃描述（LP2） 顯然，當(dāng)min g=max f時，工廠決策者認(rèn)為這兩種考慮具有相同的結(jié)果，都是最優(yōu)方案。 比較LP1和LP2，可知它們之間有著密切的聯(lián)系，兩者包含有相同的數(shù)據(jù)，只是位置不同而已。如果稱前者為原問題，則后者就叫前者的對偶問題，反過來也是如此，即兩者互為對偶問題。更一般地，若原問題為則對偶問題為其中yi叫做對偶變量。若表示成矩陣形式，則有其中A是m×n矩陣，C是n維向量，b是m維列向量，X是n維列向量、為原問題的變量，Y是m維

40、行向量、為對偶問題的變量。上式稱為對偶關(guān)系的對稱形式（或叫對偶標(biāo)準(zhǔn)形式），一般情況下，原問題與對偶問題的變換關(guān)系可歸納為表315所列的對應(yīng)關(guān)系。 若原規(guī)劃問題的約束條件中含有約束，可在其兩邊同乘以-1，統(tǒng)一為約束。這里，右邊項沒有符號限制。根據(jù)表3一15，可以寫出下列一對線性規(guī)劃問題：式（325）稱為對偶關(guān)系的非對稱形式。例：求標(biāo)準(zhǔn)線性規(guī)劃問題的對偶問題解：先將標(biāo)準(zhǔn)線性規(guī)劃問題化為等價的LP問題其對偶問題為例310 寫出下列線性規(guī)劃問題的對偶問題。解 用1乘第二個約束條件的兩端，把它變成約束，根據(jù)表315即可寫出其對偶問題為 如果求這個問題的對偶，顯然就得到了原問題的對偶問題。6.2 對偶問題

41、的基本性質(zhì) 下面介紹對偶問題的幾條重要性質(zhì)，以揭示原問題的解與對偶問題的解之間的一些重要關(guān)系，并為后面討論對偶單純形法奠定基礎(chǔ)。 1）若X和Y分別是原問題和對偶問題的任一可行解，則必有 CXYb，即 fg 2）若X*和Y*分別為原問題和對偶問題的可行解，且可行解對應(yīng)的原問題和對偶問題的目標(biāo)函數(shù)值相等，即CX*Y*b，則X*、Y*分別為原問題和對偶問題的最優(yōu)解。 3）若原問題和對偶問題之一的最優(yōu)解無界，則另一個無可行解；若其中之一無可行解，則另一個的最優(yōu)解無界或無可行解。也就是說，原問題和對偶問題之一無最優(yōu)解，則另一個也無最優(yōu)解。 4）若原問題和對偶問題之一有最優(yōu)解，則另一個也有最優(yōu)解，且兩者的

42、最優(yōu)目標(biāo)函數(shù)值相等。 5）若原問題的最優(yōu)解為 XBB-1b，則對偶問題的最優(yōu)解為 YCBB-1。 6）根據(jù)原問題最優(yōu)單純形表中的判別數(shù)可以讀出對偶問題的最優(yōu)解。 對于第6個性質(zhì)下面作一說明。設(shè)原問題和對偶問題為式（324），在原問題的約束條件中分別引人松弛變量Xs和剩余變量Ys，其中Xs為m維列向量，Ys為n維列向量，有設(shè)B為原問題的一個最優(yōu)基，則原問題可改寫為相應(yīng)的對偶問題為這里Ys（Ys1 Ys2），Ys1是對應(yīng)于原問題中基變量XB的剩余變量，Ys2是對應(yīng)于原問題中非基變量XN的剩余變量。原問題的最優(yōu)解為XBB-1b，相應(yīng)的基變量XB的判別數(shù)為0，非基變量XN的判別數(shù)為CNCBB-1N，松

43、弛變量Xs的判別數(shù)為 CBB-1，把對偶問題的最優(yōu)解 YCBB-1代人上式得 由此可見，原問題的最優(yōu)單純形表中的判別數(shù)對應(yīng)于對偶問題的最優(yōu)解的負(fù)值。它們的關(guān)系如表316所示。同樣地若原問題和對偶問題為武（325）所示的非對稱形式，則可得到表317所示的結(jié)果。 根據(jù)表3-17可知，原問題最優(yōu)表中的判別數(shù)對應(yīng)于對偶問題最優(yōu)解中剩余變量的負(fù)值，而對偶決策變量的值YCBB-1看起來還不能直接從表317中讀出。當(dāng)然，如果知道了B-1和CB就可以直接計算出Y來，但下面討論如何從表317中直接讀出對偶變量的值。假定在原問題的約束條件的系數(shù)矩陣中有一個m階單位陣，以此為初始可行基進(jìn)行迭代得到最優(yōu)基 B，則在最

44、優(yōu)表316中，原來為單位陣的地方就變成了B-1，而在初始表中和B-1相對應(yīng)的基矩陣B正好位于和最優(yōu)表316中的單位陣相對應(yīng)的位置，若用CI表示和初始表中單位陣相對應(yīng)變量的價值系數(shù)向量，則在最優(yōu)表 316中 B-1下的判別數(shù)將是CICBB-1。因而若由最優(yōu)表316中B-1下的判別數(shù)減去相應(yīng)的價值系數(shù)，則正好得到其對偶問題最優(yōu)解的負(fù)值，即：YCBB1 ，特別地，當(dāng)初始表中的單位陣是由引人松弛變量后而形成的，則有CI0。在這種情況下，最優(yōu)表316中B1下面的判別數(shù)就正好等于其對偶問題的最優(yōu)解的負(fù)值。下面以例39加以說明。設(shè)式（320）為原問題式（321）為對偶問題，在原問題的約束條件中引人松弛變量x

45、3、x4、x5，按單純形法得原問題的初始表和最優(yōu)表分別為表318和表3一19。 由表319知，原問題的最優(yōu)解為X（35 10 25 0 0）T，最優(yōu)目標(biāo)函數(shù)值為max f 215在表318中，松弛變量x3，x4，x5的系數(shù)矩陣構(gòu)成單位陣，故在最優(yōu)表319中對應(yīng)的系數(shù)矩陣為最優(yōu)基的逆陣且對應(yīng)的判別數(shù)等于它在對偶問題式（321）中的最優(yōu)解的負(fù)值。即：Y（y1 y2 y3）（0 1 3），相應(yīng)的目標(biāo)函數(shù)值為min gmax f 215。另一方面，Y也可按式Y(jié)CBB1計算，由于最優(yōu)表中的單位陣對應(yīng)于基變量x3、x1、x2，所以它們在初始表318中的系數(shù)列向量構(gòu)成最優(yōu)基B，故CB（c3 c1 c2）（0

46、 5 4），則有相應(yīng)的目標(biāo)函數(shù)值為為了驗證按上述方法確定的對偶問題的最優(yōu)解的正確性，按單純形法對對偶問題式（321）進(jìn)行迭代，得對偶問題的最優(yōu)表如表320所列。表中y6，y7為人工變量，g'g。 由表320可知，對偶問題式（3-21）的最優(yōu)解和最優(yōu)目標(biāo)函數(shù)值與上述方法求得的完全相同。由此可見，從表320的判別數(shù)中也可以直接讀出原問題的最優(yōu)解，這一點(diǎn)給我們一個重要的啟示，即在求解線性規(guī)劃問題時，可在原問題和對偶問題中挑選容易求解的進(jìn)行求解計算，只要求出它的最優(yōu)解，另一個的最優(yōu)解也就很容易地得到。一般來說，線性規(guī)劃求解的工作量在很大程度上取決于約束條件數(shù)目的多少，約束條件多，基矩陣的階數(shù)高

47、，計算量大。因此，對于約束條件多，變量少的規(guī)劃問題，其對偶規(guī)劃的約束條件少，變量多，若對對偶規(guī)劃求解，就可減少計算工作量。6.3 對偶問題的經(jīng)濟(jì)意義影子價格我們?nèi)砸岳?9為依據(jù)，其原問題和對偶問題的模型分別為通過求解，原問題和對偶問題的最優(yōu)解分別為為了分析對偶問題的經(jīng)濟(jì)意義，我們對原規(guī)劃及其對偶問題的求解進(jìn)行圖示分析，見圖32。在圖32中，增畫了三條直線（用虛線描述），分別是這三條直線分別代表三種資源（各臺設(shè)備可利用的臺時數(shù)）各增加1個單位后的邊界線。若資源b1，b2保持不變，僅使b345增加 1個單位，則最優(yōu)點(diǎn)變?yōu)镠'（34，12），此時就是說，原模型總利潤的增量剛好等于對偶模型的變

48、量y3的最優(yōu)解。而變量y3是對應(yīng)于原模型的第3個約束條件即資源b3的。所以，y3的取值反映了資源b3的單位增量所帶來的利潤的增加量。換言之，y33反映了資源b3的一種單位價格，稱為“影子價格”。由此可見，某一約束條件的影子價格表示為當(dāng)它所對應(yīng)的約束條件右端的常數(shù)增加一個單位時（假設(shè)原問題的最優(yōu)基不變），原問題目標(biāo)函數(shù)最優(yōu)值增加的數(shù)值。如果花費(fèi)某種代價（3）去獲得b3，即當(dāng)b3這種資源的市場價格低于影子價格時，企業(yè)就應(yīng)買進(jìn)這種資源。但這樣做是有限度的，因為由圖32可知，直線x1x245或xlx246如果過分右移是沒有意義的。如果資源b190，b345保持不變，僅使 b280增加一個單位，則最優(yōu)點(diǎn)

49、變?yōu)?H"（36，9），此時就是說，資源b2的影子價格為y21，其余討論同上。 如果資源b280，b345，保持不變，僅使b190增加一個單位，則最優(yōu)點(diǎn)仍為H（35，10），fmax215，其增量fmax0y1。就是說，資源b1的影子價格為y10，這說明用設(shè)備的臺時數(shù)沒有充分利用，還有剩余，當(dāng)其用于外加工時，只有收取加工費(fèi)，且不管為多少，對該廠來說都是有利的。但是這種對外加工是有限度的，否則，直線x13x290下移過多將影響最優(yōu)解。 例311 一個大學(xué)教授用部分時間從事于咨詢工作。通過這項工作，他的總收人將有所提高，該教授掌握了咨詢補(bǔ)償?shù)幕疽?guī)律：“一個專家的價值正比于廠商和專家之間

50、的距離”。也就是說，要求咨詢的單位愈遠(yuǎn)，他得到的報酬愈多。遺憾的是，旅行時間也將增加。目前他有較多的咨詢機(jī)會，但可用時間有限，他希望詳細(xì)分析這種情況，他是否要雇助手？如果這樣，他應(yīng)付多少工資？ 解 設(shè)：x1每月為A企業(yè)咨詢的小時數(shù)（利潤：10元h） x2每月為B企業(yè)咨詢的小時數(shù)（利潤：12元h） x3每月為C企業(yè)咨詢的小時數(shù)（利潤：16元h）進(jìn)一步假定該教授每月有40h用于咨詢工作，并且希望他的旅行時間每月在24h以內(nèi)。每小時咨詢工作所要求的旅行時間對于企業(yè)A、B、C來說分別為0.1h、0.2h、0.2h。教授估計三個企業(yè)每月要求最大的咨詢時間分別是80h、60h、20h。據(jù)此，我們可以很快建

51、立該問題的線性規(guī)劃模型。式中 f從事咨詢工作每月可得的利潤總和（元月）。對偶問題的模型為式中 g各種資源全部利用后的收益總和；y1資源 1的單位貢獻(xiàn)（咨詢時間的價值）；y2資源2的單位貢獻(xiàn)（旅行時間的價值）；y3資源3的單位貢獻(xiàn)（為A咨詢的價值）；y4資源4的單位貢獻(xiàn)（為B咨詢的價值）；y5資源5的單位貢獻(xiàn)（為C咨詢的價值）。用單純形法求解該問題，得到原問題和對偶問題的最優(yōu)解為注意到：每月增加教授咨詢時間lh，每月可多得酬金12元。這就確定了為助手提供的支付金，雇請薪金每月小于12元的助手將增加教授的月收人。 此外，還看到公司C的咨詢價值，超過每月20h后，是每小時4元。由于假定只能給它每月2

52、0h，就不能利用這個結(jié)果。所以教授應(yīng)該為助手支付每小時小于12元的工資。助手每工作lh，教授每月額外收人（12元助手小時工資）。顯然，這個結(jié)果存在上限；否則，附加酬金沒有限制。在靈敏度分析中將對如何確定這種限制進(jìn)行詳細(xì)的分析。6.4 對偶單純形法 在用單純形進(jìn)行迭代時，在bi列中得到問題的基本可行解，而在判別數(shù)行得到的是對偶問題的非可行解。這是因為在達(dá)到最優(yōu)解之前，判別數(shù)即 YAC，顯然 YCBB-1不滿足對偶問題的約束條件 YAC。通過逐步迭代，當(dāng)判別數(shù)行得到的對偶問題的解也是可行解時，即 CYA0或 YAC時，CBXBYb，由性質(zhì)2知，此時原問題和對偶問題同時達(dá)到了最優(yōu)解。 根據(jù)對偶問題的

53、對稱性，也可以這樣來考慮：若保持對偶問題的解是可行解，即CYA0，而原問題在非可行解的基礎(chǔ)上，即B-1b中至少有一個負(fù)分量，通過迭代逐步達(dá)到基本可行解，這樣也得到了原問題和對偶問題的最優(yōu)解。因為這種方法是從對偶問題的可行性出發(fā)來求解原問題的最優(yōu)解，故把它稱做對偶單純形法。這種方法的優(yōu)點(diǎn)是原問題的初始解不一定是基本可行解，即可以從非可行解開始迭代。下面通過一個例題來介紹對偶單純形法的計算步驟。 例312 用對偶單純形法求解下列線性規(guī)劃問題解 第一步：標(biāo)準(zhǔn)化。引人剩余變量x3，x4，x5，并令f'f， 則有 顯然，如果要用單純形法求解，則需引人三個人工變量，再用兩階段法或大M法進(jìn)行求解，若用下面介紹的對偶單純形法就簡單多了。 第二步：找初始基變量，并將目標(biāo)函數(shù)中的基變量用非基變量代替。為了找出基變量，先在約束方程的系數(shù)矩陣中形成m階單位陣，為此用1乘式（327）約束方程兩端，得 顯然，x3，