運籌學考點精講及復習思路

提提 第—章線性規(guī)劃與單純形法（第二章對偶問題與靈敏度分 （第三章運輸問題（第四章目標規(guī)劃（第五章整數(shù)規(guī)劃（第六章動態(tài)規(guī)劃（第七章圖與網(wǎng)絡(luò) （第八章網(wǎng)絡(luò)計劃 （第九章存儲論（第十章排隊論（第十—章決策論（《運籌學》考點精講及復習思第一 線性規(guī)劃與單純形~、本章考情分析?？碱}型：選擇、填空、簡答、判斷和計算分值：必考知識點，分值占３０分以上重要性：作為前五章的基礎(chǔ)鋪墊，非常重要！重要程度：★★★★★二、本章基本內(nèi)容１）掌握線性規(guī)劃的數(shù)學模型的標準型；２）掌握線性規(guī)劃的圖解法及幾何意義；３）了解單純形法原理；４）熟練掌握單純形法的求解步驟５）能運用大Ｍ法與兩階段法求解線性規(guī)劃問題；６）熟練掌握線性規(guī)劃幾種解的性質(zhì)及判定定理．三、本章重難點：重點１）單純形法求解線性規(guī)劃問題；２）解的性質(zhì)；３）線性規(guī)劃問題建模．難點：１）單純形法原理的理解；２）線性規(guī)劃問題建模．四、本章要點精講要點 化標準要點 圖解要點 單純形法的原要點 單純形法的計算步要點５ 單純形法的進一步討論要點１ 化標準型線性規(guī)劃的數(shù)學模１提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５線性規(guī)劃的共同特決策變量１：每個問題都用一組決策變量表示某個方案決策變量２：決策變量的取值一般都是非負且連續(xù)約束條件３：與決策變量不矛盾的條件，用線性等式或不等式表目標函數(shù)４：決策變量與價值系數(shù)組成，一般要求實現(xiàn)最大或最小【建模思路】確定決策變量寫出目標函數(shù)找出約束條線性規(guī)劃的標準型可簡化ｎｍａｘＺ＝∑ｉｓ．ｓ．ｔ．∑ｊ＝ ｉ＝１，２，…，ｊｘｊ≥ ｊ＝１，２，…，經(jīng)典例題［１－１］ 胡運權(quán)，運籌學教程（三）Ｐ１５，例３與南京航空航天大學２００５年，第四題類似，１０分ｍｉｎＺ＝ｘ１＋２ｘ２＋－２ｘ１＋ｘ２＋ｘ３≤－３ｘ１＋ｘ２＋２ｘ３≥４４ｘ１－２ｘ２－３ｘ３＝－ｘ０，ｘ０，ｘ取值無約 ２提《運籌學》考點精講及復習思【１】目標函數(shù)最【２】資源限量（右端項）非【３】約束條件等松弛變量與剩余變量在實際問題中分別表示未被充分利用的資源和超出的資源數(shù)，均未轉(zhuǎn)化為價值和利潤，所以引進模型后它們在目標函數(shù)中的系數(shù)均為零?！荆础繘Q策變量非整理，ｍａｘＺ′＝ｘ１′－２ｘ２－３ｘ３′＋３ｘ３″＋０ｘ４＋目標函數(shù)最大約束條件等式?jīng)Q策變量非資源目標函數(shù)最大約束條件等式?jīng)Q策變量非資源限量非ｘ′＋ｘ＋ｘ′－ｘ″３ｘ１′＋ｘ２＋２ｘ３′ｘ′＋ｘ＋ｘ′－ｘ″４ ２ ３ ３ ｘ′，ｘ，ｘ′，ｘ″，ｘ，ｘ≥ 經(jīng)典例題［１－ 天津大學２００４，二，（１），約５３提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５某公司生產(chǎn)家用的清潔產(chǎn)品，為了在高度的市場競爭中增加市場份額，公司決定進行一次大規(guī)模的廣告行動．表１給出了公司準備做廣告的三種產(chǎn)品名稱、估計每做一單位廣告使每種產(chǎn)品的市場份額增加量、公司擬定的廣告后每種產(chǎn)品市場份額增加量的最低目標和兩種可選的廣告方式的單價現(xiàn)公司需擬定使廣告總費用最少的廣告計劃，即決定電視和印刷媒體的廣告數(shù)量分別為１．請寫出此問題的線性規(guī)劃模型，并將模型化為標準型．其中洗衣粉的市場份額出現(xiàn)負值是由液體洗滌劑的份額增加造成的電印刷媒廣告后市場份額最低增去污液體洗滌洗衣–廣告單位成本（萬元解：設(shè)電視的廣告數(shù)量為ｘ１，印刷媒體的廣告數(shù)量為ｍｉｎＺ＝１００ｘ１＋ｘ２≥３ｘ１＋１２ｘ２≥１８－ｘ１＋４ｘ２≥ 化為標準型 ｍａｘＺ′＝－１００ｘ１－２００ｘ２＋０ｘ３＋０ｘ４＋ｘ２－ｘ３＝３ｘ１＋１２ｘ２－ｘ４＝１８－ｘ１＋４ｘ２－ｘ５＝ｘ，ｘ，ｘ，ｘ，ｘ≥ 復習思路提示初學時，化標準型可按“目標函數(shù) 資源限量 約束條件 決策變量”的順序進行，化完后默念四句口訣驗證；化標準型是用單純形法求解線性規(guī)劃問題的第一步，非常重要！而單純形法求解線性規(guī)劃問題是每年必考大題，此步錯，后面展開步步錯！要點 圖解圖解法求解步驟４提《運籌學》考點精講及復習思經(jīng)典例題［１－３］ 胡運權(quán)，運籌學教程（三）Ｐ１６，例１ｍａｘＺ＝２ｘ１＋ｘ２５ｘ２≤６ｘ１＋２ｘ２≤２４ｘ１＋ｘ２≤ ｘ，ｘ≥ 【詳見課程視頻圖解法的幾點啟示線性規(guī)劃解的情況有：唯一最優(yōu)解、無窮多最優(yōu)解、無界解、無可行解；若線性規(guī)劃的可行域存在，則可行域一定是個凸集；若線性規(guī)劃的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一（無窮多解時）一定是可行域的凸集的某個頂點；解題思路：找出凸集的頂點，計算其目標函數(shù)值，比較即得。圖解法啟示的解題思路經(jīng)典例題［１－４］天津大學２００６，一、選擇（１），２用圖解法解線性規(guī)劃時，以下幾種情況不可能出現(xiàn)的是 Ａ．可行域有界，無有限最優(yōu)解（或稱無界解 Ｂ．可行域無界，有唯一最優(yōu)Ｃ．可行域是空集，無可行解 Ｄ．可行域有界，有多重最優(yōu)解復習思路提示：·要會用圖解法來分析線性規(guī)劃的幾種解的情況，如唯一最優(yōu)解、無窮多解、無界解和無可行解５提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５圖解法容易在確定可行域的范圍和等值線移動方向上犯錯圖解法的知識點通常出現(xiàn)在選擇、填空、判斷等小題型中！大致分值在１０分以內(nèi)．思考題［１－１］ （留待以后課程講解）南京航空航天大學２００４，一、多項選擇２、３，各５２．線性規(guī)劃的最解可在（）Ａ．可行集Ｂ．可行集邊界Ｃ．可行集頂點Ｄ．滿足其約束條件的區(qū)域３．線性規(guī)劃的可集可以（）Ａ．不含有任何可解Ｂ．恰含有一個可行Ｃ．恰含有兩個可行解 Ｄ．含有無數(shù)個可行解思考題［１－２］ （留待以后課程講解）南京航空航天大學２００６，第二題，１０分二、（１０分）用圖解法求解線性規(guī)劃問題．ｍａｘｚ＝４０ｘ１＋ｘ１＋２ｘ２≤３ｘ１＋２ｘ２≤６０２ｘ２≤ ｘ，ｘ≥ 要點 單純形法原解的概念與關(guān)單純形法迭代原［１］解的概念與關(guān)系線性規(guī)劃的標準型ｎｍａｘＺ＝∑ｉｓ．ｓ．ｔ．∑ｊ＝ ｉ＝１，２，…，ｊｘｊ≥ ｊ＝１，２，…，ｎ【向量形式】ｍａｘＺ＝ｎｓ．ｉ∑Ｐｊｘｊ＝ ｉ＝１，２，…ｓ．ｉｘｊ≥ｊ＝２，…，６提《運籌學》考點精講及復習思【矩陣形式】ｍａｘＺ＝ＡＸ＝ｓ．ＡＸ＝Ｘ≥線性規(guī)劃問題解的概ｎｍａｘＺ＝∑ （ｉｓ．

∑ｊ＝ ｉ＝１，２，…， （ｊｘｊ≥ ｊ＝１，２，…， （ 可行解：滿足約束條件（２）和（３）的解Ｘ＝（ｘ，…，ｘ）Ｔ全部可行解的集合稱為可行域。最優(yōu)解：使目標函數(shù)（１）達到最大值的可行解 基：設(shè)Ａ是約束方程組（２）的ｍｎ階系數(shù)矩陣（設(shè)ｎ＞ｍ，其秩為ｍＢ是Ａ中的一個ｍｍ階的滿秩子矩陣（Ｂ０的非奇異子矩陣），稱Ｂ是線性規(guī)劃問題的一個基．不失一般性，設(shè)除基變量以外的變量稱為非基變基解：在約束方程組（２）中，令所有的非基變量ｘｍ＋１＝ｘｍ＋２＝… ＝ｘｎ＝０，又因為 Ｂ≠０，據(jù)克萊姆法則，對于ａ１１ｘ１＋ａ１２ｘ２＋…＋ａ１ｍｘｍ＝ａ２１ｘ１＋ａ２２ｘ２＋…＋ａ２ｍｘｍ＝ａｍ１

＋ａｍ２ｘ２＋…＋ａｍｍｘｍ＝可以求出唯一解ＸＢ＝ｘ，ｘ，…，ｘ ｎｍａｘＺ＝∑ （ｉｓ．

∑ｊ＝ ｉ＝１，２，…， （ｊｘｊ≥ ｊ＝１，２，…， （基可行解：滿足變量非負約束條件（３）的基解．可行基：對應(yīng)基可行解的基．經(jīng)典例題［１－ 胡運權(quán)，運籌學教程（三）Ｐ１９，例找出下述線性規(guī)劃問題的全部基解，指出其中的基可行解，并確定最優(yōu)解７提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５ｍａｘＺ＝２ｘ１＋３ｘ２＋ｘ１＋ｘ３＝ ０１０ｓ．ｔ．ｘ１＋２ｘ２＋ｘ４＝ｘ２＋ｘ５＝ｘｊ≥０，ｊ＝１，２，…，【詳見課程視頻凸集、頂點及幾個定

Ａ＝ １２０１ １００設(shè)Ｋ是ｎ維歐氏空間的一點集， Ｘ（１）∈Ｋ，Ｘ（２）∈Ｋ的連線上的所有點Ｘ１）＋（１－αＸ（２）Ｋ，０α１），則稱Ｋ為凸集設(shè)Ｋ是凸集，ＸＫ；若Ｘ不能用不同的兩點Ｘ（１）Ｋ和Ｘ（２）Ｋ的線性組合表示為Ｘ＝Ｘ＋（１－αＸ（２），（０＜α＜１）則稱Ｘ為Ｋ的一個頂點（或極點）定理 若線性規(guī)劃問題存在可行解，則問題的可行域是凸集．（天津大學２００６年第三題證明，分引 線性規(guī)劃問題的可行解為基可行解的充要條件是Ｘ的正分量所對應(yīng)的系數(shù)列向量是線獨立的定理２ 線性規(guī)劃問題的基可行解Ｘ對應(yīng)線性規(guī)劃問題可行域（凸集）的頂點．定理３ 若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解．幾個定理考察的通常是小題型，需要牢記結(jié)論，且理解各個解之間的關(guān)系。幾點結(jié)論：【１】可行域若有界則是凸集，也可能是無界域【２】每個基可行解對應(yīng)可行域的一個頂點【３】可行域有有限多個頂點【４】如果有最優(yōu)解，必在某個頂點上得到．線性規(guī)劃解之間的關(guān)系歸納“箭尾的解一定是箭頭的解，反之不一定成立．當最優(yōu)解唯一時，最優(yōu)解也是基最優(yōu)解當最優(yōu)解不唯一時，最優(yōu)解不一定是基最優(yōu)解經(jīng)典例題［１－６］ 南京航空航天大學，２０１１，一、判斷（１），３分一、判斷下列說法是否正確．８提《運籌學》考點精講及復習思１）若線性規(guī)劃問題的可行解為最優(yōu)解，則該可行解必定是基可行解．（ 經(jīng)典例題［１－７］ 北京交通大學，２０１０，一、判斷（１），２分—、判斷下列說法是否正確１）線性規(guī)劃問題的每一個基解對應(yīng)可行域的一個頂點．（ 單純形法的迭代思路：［２］單純形法的迭代原理ｍａｘＺ＝ＣＸｓ．ｓ．ｔ．∑Ｐｊｘｊ＝ｉｘｊ≥ ｊ＝１，２，…【１】構(gòu)造初始可行Ｂ＝Ｐ，Ｐ，…，

０ ０ １直接觀察一個可行≤約束，加松弛變量

Ｂ≠≥約束，加人工變量（后面會討論（為討論方便，設(shè)均為≤約束【２】基變換：兩個基可行解相鄰，兩者可變換且僅變換一個基變９提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５設(shè)初始基可行解為寫出系數(shù)矩陣的增廣矩陣 ［移項得 可得Ｐｊ＝∑ｊ →Ｐｊ－∑ｊｉ＝ｉ ｉ上式乘以一個正數(shù)θ＞０，ｍθＰｊ－∑Ｐｉ＝ｍｉ ∑ｘ０－θａＰｉ＋Ｐ＝ｍ∑Ｐｘ０＝ｉ

ｉｉｍ由∑ｘ０θａＰｉＰ＝ ｉｎ可找到滿足原約束方程組∑Ｐｊｘｊ＝ｂ的另一個點ｉＸ１＝ｘ０－θａ，…，ｘ０–ａｊ，０，…，θ…，０ ｉ要使是一個基可行解，則應(yīng)對所有ｉ＝１，２，…，ｍ存在ｘ０–ａｊ０（先要使其可行ｉ令這ｍ個不等式至少有一個等號成立，且當ａｉｊ０時，上式顯然成立，故可θ＝ｍｉｎｘ

ａ> ＝ 可確保ｘ０θａ

＝０，ｉ＝≥０，ｉ≠

此時與ｘ

是可行解，ｘ１，…，ｘ１，ｘ１對應(yīng)的向量 ｌ１ ｌ 提《運籌學》考點精講及復習思【３】最優(yōu)性檢驗和解的判ｎ將上述Ｘ（０），Ｘ（１）分別代入目標函數(shù)ｚ＝∑ｘｊ，ｊｊｚ０

＝∑ｃｘｉｉｚ１＝

ｃｘ０－θａ＋θｃ＝ｍｃｘ０＋θｃ

ｍｃａ＝ｚ０＋θｃ

ｍｃａ ｉｍ

ｉｉｍ

ｉ１

ｉ１ｚ

＝∑ｃｘ ｚ１＝ｚ０＋θｃ ｃａｉ ｉ

ｉ１（１）當所有σ０，當前頂點（基可行解）的目標函數(shù)值已是最大，即為最優(yōu)解ｊ（２）當所有σ０，又某個非基變量ｘｊ的檢驗數(shù)為０，則在另一個頂點也使目標函數(shù)達到最大，兩點連線上的所有點都是最優(yōu)解，即無窮多最優(yōu)解．當所有非基變量的σ＜０時，有唯一最優(yōu)解；ｊ（３）若存在某個有無界解ｘ０－θａ≥

>０，而其對應(yīng)的非基向量Ｐ０，則從θ值和ｚ（１）的表達式可看出，線性規(guī) 線性規(guī)劃解的判別定理歸納：最優(yōu)解判別定理若Ｘ（０）＝（ｂ′，ｂ′，…ｂｍ′，０，…，０）Ｔ為基可行解，且全部σ０，ｊ＝ｍ＋１，…，ｎ，則Ｘ（０）為最優(yōu)解唯一最優(yōu)解判別定若Ｘ（０）＝（ｂ１′，ｂ２′，…，ｂｍ′，０，…，０）Ｔ為基可行解，且全部σｊ＜０，ｊ＝ｍ＋１，…，ｎ，則Ｘ（０）為唯一最優(yōu)解無窮多最優(yōu)解判別定若Ｘ（０）＝（ｂ′，ｂ′，…ｂｍ′，０，…，０）Ｔ為基可行解，且全部σ≤０，ｊ＝ｍ＋１，…，ｎ，且存在一個非提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５變量ｘｍ＋ｋ的ｍ＋＝０，則存在無窮多最優(yōu)解無界解判別定若有一個非基變量ｘｍ＋ｋ的ｍ＋＞０，而其對應(yīng)非基變量的所有系數(shù)ａ′ｉ，ｍ＋ｋ０，ｉ＝１，２，…，ｍ則具有無界解。復習思路提示掌握線性規(guī)劃幾個解的概念及幾何意義，會用該知識點求解考研試題中的各類小題型會在簡答題中對單純形法的迭代思路進行描述了解單純形法的迭代原理，牢記解的判別定理．思考題［１－３］ （留待以后課程講解）中山大學２０１２，一、選擇（３）１在標準形式下線性規(guī)劃問題的單純形迭代過程中，若有某個ｃｊ－ｚｊ＞０對應(yīng)的非基變量ｘｊ的系數(shù)列向量（ ）時，則此問題是無界的。Ａ．≥０ Ｂ．＜０ Ｃ．＝０ Ｄ．０北京交通大學２０１０，一、判斷（２）２分單純形法計算中，取最大正檢驗數(shù)對應(yīng)變量換出，所得解上升最快。１）寫出該線性規(guī)劃的標準型（１０分）；２）求原規(guī)劃的最優(yōu)解和最優(yōu)目標函數(shù)值（１５）．要點４ 單純形法的計算步驟為書寫規(guī)范和便于計算，對單純形法的計算設(shè)計了單純形表每一次迭代對應(yīng)一張單純形表，含初始基可行解的單純形表稱為初始單純形表，含最優(yōu)解的單純形表稱為最終單純形表。本節(jié)介紹用單純形表計算線性規(guī)劃問題的步驟【１】求初始基可行解，列出初始單純形ｃｊ………ｂ………１…０……０００…１……ｃｊ－０…０…ｍｃｊ－∑ｉ…ｍｃｎ－∑ｉ提《運籌學》考點精講及復習思【２】最優(yōu)性檢【３】基變１）確定換入基的變只要有檢驗數(shù)大于０，對應(yīng)的變量就可作為換入變量，當有一個以上檢驗數(shù)大于０時，一般從中選取最大的一個：σ＝ｍａｘσｊ｜σ＞０ｊ其對應(yīng)的變量ｘｋ作為換入變量２）確定換出基的變根據(jù)確定θ最小比值規(guī)則，對Ｐｋ列計算可得：θ＝ｍｉｎ

>＝ａ ａ

其對應(yīng)的變量ｘｌ作為換出變量。元素ａｌｋ決定了從一個基可行解到相鄰基可行解的轉(zhuǎn)移去向，稱之為主元素。３）迭代變用換入變量ｘｋ去替換基變量中的換出變量ｘｌ，得到一個新的基（Ｐ…，ＰｌＰｋ，Ｐｌ…，Ｐｍ）。對應(yīng)這個基可以找出一個新的基可行解，并相應(yīng)地可以畫出一張新的單純形表?！驹斠娬n程視頻經(jīng)典例題［１－８］ 南航，２０１２，二、計算題，１．（１）１０分二、１．（２０分）已知線性規(guī)劃問題：ｍａｘｚ＝８ｘ１＋提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５ｘ１＋ｘ２≤２ｘ１＋ｘ２≤１０ｘ１≤ ｘ，ｘ≥ １）用單純形法求解【詳見課程視頻在上面的例題［１８］中，考慮以下兩個問題１）若初始單純形表中，若用檢驗數(shù)６對應(yīng)的ｘ２作為換入變量會帶來什么樣的結(jié)果２）用圖解法求解該題，看每張單純形表對應(yīng)的解與可行域中的頂點如何對應(yīng)？基變換是否是相鄰的頂點間進行變換？最優(yōu)解在哪個頂點取得？復習思路提示正確的標準型是單純形法求解線性規(guī)劃問題的前提會依據(jù)標準型列出初始單純形表（重點是正確找出初始基及對應(yīng)的初始基變量）熟練運用矩陣的初等行變換進行單純形表迭代（最容易犯計算錯誤）牢記最優(yōu)性檢驗的幾個解的判別定理（當遇到無窮多最優(yōu)解和無界解的情況）。思考題［１－４］ （留待以后課程講解）中山大學２０１２，三，１１用單純形表求解以下線性規(guī)劃問題：ｍａｘｚ＝ｘ１－２ｘ２＋ｘ３ｘ１＋ｘ２＋ｘ３≤２ｘ１＋ｘ２－ｘ３≤６－ｘ１＋３ｘ２≤ｘ≥０，ｘ≥０，ｘ≥ 要點 單純形法的進一步討考慮：線性規(guī)劃問題化為標準形時，若約束條件的系數(shù)矩陣中不存在單位矩陣，如何構(gòu)造初始可行基？ＭａｘＺ＝ｃ１ｘ１＋ｃ２ｘ２＋…＋ｃｎａ１１ｘ１＋ａ１２ｘ２＋…＋ａ１ｎｘｎ＝ａ２１ｘ１＋ａ２２ｘ２＋…＋ａ２ｎｘｎ＝ｓ．ｔ．………………ａｍ１ｘ１＋ａｍ２ｘ２＋…＋ａｍｎｘｎ＝ｘ，ｘ，…，ｘ≥

提《運籌學》考點精講及復習思線性規(guī)劃問題化為標準形時，若約束條件的系數(shù)矩陣中不存在單位矩陣，添加人工變量“懲罰”人工變量 大Ｍ法和兩階段【１】大Ｍ人工變量在目標函數(shù)中的系數(shù)為Ｍ其中Ｍ為任意大的正數(shù)經(jīng)典例題［１－ 清華大學運籌學編寫組（三）Ｐ３３例Ｍａｘｚ＝３ｘ１－ｘ２－ｘ１－２ｘ２＋ｘ３≤－４ｘ１＋ｘ２＋２ｘ３≥３－２ｘ１＋ｘ３＝ｘ，ｘ，ｘ≥ 提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５解：１）首先化標準型２）添加人工變量，構(gòu)造初始可行Ｍａｘｚ＝３ｘ１－ｘ２－ｘ３＋０ｘ４＋０ｘ５－Ｍｘ６－ｘ１－２ｘ２＋ｘ３＋ｘ４＝－４ｘ１＋ｘ２＋２ｘ３－ｘ５＋ｘ６＝３－２ｘ１＋ｘ３＋ｘ７＝ｘｊ０，ｊ＝１，２，…，７其中，為任意大的正數(shù)求解結(jié)果出現(xiàn)所有檢驗數(shù)非正σ０，若基變量中含非零的人工變量，則無可行解；否則，有最解３）列初始單純形表如第一步迭代，得表第二步迭代，得表提《運籌學》考點精講及復習思第三步迭代得最終表（所有檢驗數(shù)小于等于【２】兩階段第一階段：加入人工變量后，構(gòu)造僅含人工變量的目標函數(shù)，并要求其實現(xiàn)最小化第二階段：將一階段得到的最終表除去人工變量。將目標函數(shù)行的系數(shù)換成原問題的目標函數(shù)系數(shù)，作為二階段的初始表。同上例Ｍａｘｚ＝３ｘ１－ｘ２－ｘ１－２ｘ２＋ｘ３≤－４ｘ１＋ｘ２＋２ｘ３≥３－２ｘ１＋ｘ３＝ｘ，ｘ，ｘ≥ 解：１）添加人工變量，給出一階段的數(shù)學模型ｎ＝ｘ６＋ｘ７ｘ１－２ｘ２＋ｘ３＋ｘ４＝－４ｘ１＋ｘ２＋２ｘ３－ｘ５＋ｘ６＝３－２ｘ１＋ｘ３＋ｘ７＝ｘｊ≥０，ｊ＝１，２，…，提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５Ｘ＝０，１，１，１２，０Ｔ是原線性規(guī)劃問題的基可行解２）將一階段最終表中的人工變量取消填入原問題的目標函數(shù)的系數(shù)，進行第二階段計算單純形法中的幾個問題：退化基可行解中存在基變量等于０的解（退化解），迭代后目標函數(shù)值不變，即不同的基表示為同一個頂點。勃蘭特（ｂｌａｎｄ）規(guī)則１）當遇到相同檢驗數(shù)時，選取對應(yīng)下標最小的非基變量作為換入變量２）當存在兩個及以上相同的最小比值時，選取下標最小的基變量作為換出變量檢驗數(shù)的幾種判別形提《運籌學》考點精講及復習思復習思路提示人工變量是人為加入的，與決策變量、松弛變量有本質(zhì)的區(qū)別，若線性規(guī)劃有最優(yōu)解，人工變量必為０，以保持原約束條件不變。為了使人工變量為０，就要使人工變量從基變量中換出成非基變量；大和兩階段法通常不會直接出成計算大題在一些小題型中考察這兩種方法的注意事項。大致分值以內(nèi)。思考題［１１．兩階段法中，若第一階段目標函數(shù)最優(yōu)值不為０，則原問題 ?！颈本┛萍即髮W】２．簡述大Ｍ法的算法步驟?！灸暇┖娇蘸教齑髮W】經(jīng)典試題講解與本章小—、經(jīng)典試題講解思考題［１１］２．線性規(guī)劃的最優(yōu)解可在 ）?！灸暇┖娇蘸教齑髮WＡ．可行集 Ｂ．可行集邊界Ｃ．可行集頂點上 Ｄ．滿足其約束條件的區(qū)域上３．線性規(guī)劃的可行集可以（ ）。【南京航空航天大學】Ａ．不含有任何可行 Ｂ．恰含有一個可行Ｃ．恰含有兩個可行 Ｄ．含有無數(shù)個可行４．線性規(guī)劃問題的每一個基解對應(yīng)可行域的一個頂點。【北京交通大學，判斷】５．下面命題正確的是（ ）【昆明理工大學，單選】Ａ．線性規(guī)劃的最優(yōu)解是基可行 Ｂ．基可行解不一定是基本Ｃ．線性規(guī)劃一定有可行解 Ｄ．線性規(guī)劃的最優(yōu)值至多有一個思考題［１－２］１．（１０分）用圖解法求解線性規(guī)劃問題?！灸暇┖娇蘸教齑髮W】ｍａｘｚ＝４０ｘ１＋８０ｘ２ｘ１＋２ｘ２≤３ｘ１＋２ｘ２≤６０２ｘ２≤ ｘ，ｘ≥ ２．若線性規(guī)劃的可行解為最優(yōu)解，則該可行解必定是基可行解?！灸暇┖教旌娇沾髮W，判斷３．若Ｘ１，Ｘ２分別是某一線性規(guī)劃問題的最優(yōu)解，則Ｘ＝λＸ１＋λＸ２也是該線性規(guī)劃問題的最優(yōu)解，其中λ，λ為正實數(shù)?！灸暇┖教旌娇沾髮W，判斷】提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５思考題［１１．在標準形式下線性規(guī)劃問題的單純形迭代過程中，若有某個ｃｊ－ｚｊ＞０對應(yīng)的非基變量ｘｊ的系數(shù)列向量（ ）時，則此問題是無界的?！局猩酱髮W】Ａ．≥ Ｂ．＜ Ｃ．＝ Ｄ．≤２．單純形法計算中，取最大正檢驗數(shù)對應(yīng)變量換出，所得解上升最快?！颈本┙煌ù髮W判斷分析ｘ１＝ｂ１′－ａ′１ｍ＋ｋｘｍ＋ｋｘ２＝ｂ２′－ａ′２ｍ＋ｋ……………

≥∵ａ′ｉｍ＋ｋ０，對任意ｘｍ＋ｋ＞０，即解都可行Ｚ＝Ｚ０＋（ｃｊ－ｚｊ）ｘｍ＋ｋ＝Ｚ０＋ｍ＋ｋ∴當ｘｍ＋ｋ＋，＋．思考題［１１．用單純形表求解以下線性規(guī)劃問題：【中山大學】ｍａｘｚ＝ｘ１－２ｘ２＋ｘ３ｘ１＋ｘ２＋ｘ３≤２ｘ１＋ｘ２－ｘ３≤６－ｘ１＋３ｘ２≤ｘ≥０，ｘ≥０，ｘ≥ 解：化標準型，并列出初始單純形表ｍａｘｚ＝ｘ１－２ｘ２＋ｘ３＋０ｘ４＋０ｘ５＋０ｘ６ｘ１＋ｘ２＋ｘ３＋ｘ４＝２ｘ１＋ｘ２－ｘ３＋ｘ５＝６－ｘ１＋３ｘ２＋ｘ６＝ｘｊ≥０，ｊ＝１，２，…，提《運籌學》考點精講及復習思迭代得表迭代得最終 ＝６，０，６，０，０，１５ ｚ＝思考題［１１．兩階段法中，若第一階段目標函數(shù)最優(yōu)值不為０，則原問題 【北京科技大學】２．簡述大Ｍ法的算法步驟。【南京航空航天大學】二、本章小目標函數(shù)最大約束條件目標函數(shù)最大約束條件等式資源限量非決策變量非ｓ．

ＡＸ＝ｂＸ≥０【２】圖解提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５可行域若有界則是凸集，也可能是無界域；每個基可行解對應(yīng)可行域的一個頂點；可行域有有限多個頂點如果有最優(yōu)解，必在某個頂點上得到…【３】線性規(guī)劃解之間的關(guān)系歸“箭尾的解一定是箭頭的解，反之不一定成立．當最優(yōu)解唯一時，最優(yōu)解也是基最優(yōu)解當最優(yōu)解不唯一時，最優(yōu)解不一定是基最優(yōu)解．進行標準化，列初始單純形表方法【４】單純形法計算步驟框提《運籌學》考點精講及復習思【５】人工變量 大Ｍ【６】人工變量 兩階段—階段目標函數(shù)最優(yōu)值為０，則去掉人工變量轉(zhuǎn)入第二階段；不為０，則原問題無可行解，停止算本章涉及的知識點大部分是每年的必考題，分值約占２０％，其中解的性質(zhì)及判定通常會出現(xiàn)在空、選擇或簡答、判斷等小題型中，而單純形法求解是每年必考的一道大題，常與第二章對偶問題聯(lián)合出題，涉及分值有時高達５０分以上。提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５第二 對偶問題與靈敏度分~、本章考情分析常考題型：選擇、填空、簡答、判斷和計算分值：必考知識點，分值在２０－２５分之重要性：每年必考，影子價格及靈敏度分析實際應(yīng)用很多重要程度：★★★★★二、本章基本內(nèi)容１）熟練掌握原問題與對偶問題的轉(zhuǎn)化關(guān)系（記憶轉(zhuǎn)化關(guān)系表或用對稱形式推導）；２）熟練掌握單純形法的矩陣描述；３）掌握對偶問題的幾條基本性質(zhì)４）熟練掌握影子價格的經(jīng)濟意義５）能運用對偶單純形法求解線性規(guī)劃問題６）熟練掌握靈敏度分析，包括ａ，ｂ，ｃ和增加約束條件的變化三、本章重難點重點１）根據(jù)原問題寫出對偶問題２）能通過單純形法的矩陣描述，從單純形表求原問題和對偶問題的最優(yōu)解３）靈敏度分析中，分析各系數(shù)在什么范圍內(nèi)變化，最優(yōu)解不變，或各系數(shù)變化后，最優(yōu)解是否改變。難點對偶問題的性質(zhì)的理解四、本章要點精講·要１線性規(guī)劃的對偶問題·要２單純形法的矩陣描述·要３線性規(guī)劃的對偶理論·要４影子價格·要５對偶單純形法·要６靈敏度分析提《運籌學》考點精講及復習思要點 線性規(guī)劃的對偶問對偶問題的提原問題與對偶問題的數(shù)學模原問題與對偶問題的對應(yīng)關(guān)系對偶問題的提出經(jīng)典例題［２－１］ 胡運權(quán)主編《運籌學教程》第三版，Ｐ４８，例１美佳公司利用現(xiàn)有資源生產(chǎn)兩種產(chǎn)品，有關(guān)數(shù)據(jù)如下產(chǎn)品產(chǎn)品資源限設(shè)備設(shè)備Ｂ調(diào)試工５時利潤（元２１美佳公司考慮：如何安排生產(chǎn)，使獲利最多？設(shè)：Ⅰ產(chǎn)量 ｘ１；Ⅱ產(chǎn)量 ｍａｘｚ＝２ｘ１＋５ｘ２≤６ｘ１＋２ｘ２≤２４ｘ１＋ｘ２≤收購方：收購美佳公司的資源，付出多少代價才能使美佳公司愿意放棄生產(chǎn)活動出讓自己的資源呢？美佳公司：出讓代價應(yīng)不低于同等數(shù)量的資源自己生產(chǎn)的利潤。設(shè)：設(shè)備 ｙ１元／設(shè)備 ｙ２元／調(diào)試工 ｙ３元／建立如下線性規(guī)劃問題提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５ｍｉｎｗ＝１５ｙ１＋２４ｙ２＋ ｍａｘｚ＝２ｘ１＋ｓ．１２３ｓ．１２３ ≥≥６ｘ１＋２ｘ２≤１ｙ１，ｙ２，ｙ６ｘ１＋２ｘ２≤１

＋ｘ２≤特點１．ｍａｘ２．限定向量ｂ 價值向量（資源向量）Ｃ３．一個約束 一個變量４．ｍａｘｚ的ＬＰ約束“ 的ＬＰ是“≥的約束５．變量都是非負限制原問題與對偶問題的數(shù)學?！荆薄繉ΨQ形式的對原問題和對偶問題只含有不等式約束。情形一：情形二將原問題化成標準對稱ｍａｘｚ＝ｓ．ｔ－ＡＸ≤－ｂＸ≥０根據(jù)標準對稱型寫出對ｍｉｎｗ＝－ Ｙ＝ ｍｉｎｗ＝

提《運籌學》考點精講及復習思ｓ． －Ｙ′Ａ≥Ｙ′≥

ｓ．ｔＹＡ≥Ｙ≤【２】非對稱形式的對偶原問題的約束是等式推導過原問ｍａｘｚ＝ＡＸ≥ＡＸ≤

ｍａｘｚ＝ Ｘ≤ － －Ｘ≥ Ｘ≥ ｍｉｎｗ＝（Ｙ１，Ｙ２）–Ａｓ．

（Ｙ，Ｙ）

≥– Ｙ１≥０，Ｙ２≥ｍｉｎｗ＝（Ｙ１－Ｙ２）·（Ｙ１－Ｙ２）·Ａ≥Ｙ１≥０，Ｙ２≥令Ｙ＝Ｙ１－Ｙ２，得對偶問題為ｉｗ＝Ｙ無約束證畢提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５原問題和對偶問題的對應(yīng)關(guān)經(jīng)典例題［２－２］ 北京交通大學２００９，一、５０分已知線性規(guī)劃問題如下：ｍｉｎｚ＝

＋

＋１２ｘ ＋ｘ

２３ｓ．ｔ．

＋３ｘ３≥ｘ，ｘ，ｘ≥ １．求該問題的最優(yōu)解２．寫出該線性規(guī)劃問題的對偶問題，并求對偶問題的最優(yōu)解３．分別確定ｘｘ３的目標函數(shù)系數(shù)ｃｃ３在什么范圍內(nèi)變化最優(yōu)解不變９４．求約束條件右端值９

變

時的最優(yōu)解５．求增加新的約束條件ｘ１＋２ｘ２＋ｘ３５時的最優(yōu)解ｉｎｚ＝２ｘ１＋５ｘ２＋２ｘ３

ｍａｘω＝３ｙ１＋ｙ１≤ｘ＋２ｘ＋ｓ．ｔ．１

１ｘ≥３２３

ｓ．ｔ．２ｙ１＋ｙ２≤ ｘ ＋３ｘ≥ｘ

＋３ｙ２≤ｘ，ｘ，ｘ≥ ｙ，ｙ≥ 復習思路提示一定要掌握根據(jù)線性規(guī)劃原問題寫對偶問題，建議先根據(jù)原約束條件的個數(shù)確定對偶問題變量數(shù)，再寫出對偶問題的目標函數(shù)和約束條件（留待最后判別約束條件和變量的符號）；寫對偶問題方式一是通過標準對稱形式進行推導，方式二則可通過記憶對應(yīng)關(guān)系表來直接寫出。提《運籌學》考點精講及復習思一定要記住數(shù)學題多是按步驟給分的，能寫多少是多少。思考題［２－１］ （留待以后課程講解）北京科技大學２０１１，三，１８分對于線性規(guī)劃問題：ｍａｘＳ＝１０ｘ１＋ｓ．ｔ．５ｘ１＋２ｘ２≤８ｘ１≥０，ｘ２≥０１．用單純形法求解最優(yōu)解，最優(yōu)值；２．寫出最優(yōu)基，最優(yōu)基的逆陣；３．寫出對偶規(guī)劃，對偶規(guī)劃的最優(yōu)解。要點２ 單純形法的矩陣描述單純形法的矩陣描單純形法計算的矩陣描述單純形法的矩陣描述ｓ．設(shè)線性規(guī)劃問題ｍａｘｚｓ．ＡＸ＝０不妨設(shè)基Ｂ＝Ｐ１Ｐ２ Ｐｍ則Ａ＝（ Ｐｎ）＝（ 約束方程

ＸＢＡＸ＝ｂ（ Ｎ） ＸＮ＝ＢＸＢ＋ＮＸＮ＝ ＝Ｂ－１（ｂ－ＮＸ）＝Ｂ－１ｂ－Ｂ 令ＸＮ＝０目標函提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５令ＸＮ＝０檢驗線性規(guī)劃問題可以等價寫成此形式為線性規(guī)劃對應(yīng)于基Ｂ的典則形式（典式）。矩陣描述時的常用公式ＸＢ＝Ｂ－１Ｎ＝Ｂ－１ｚｚ０

＝ＣＮ–ＣＢＢ－１＝ＣＢＢ－１當已知一個線性規(guī)劃的可行基Ｂ時，先求出Ｂ－１，再用這些運算公式可得到單純形法所要求的結(jié)果。單純形法計算的矩陣描述線性規(guī)劃問題ｍａｘｚ＝ＡＸ≤ｓ．Ｘ≥化為標準型，引入松弛變量提《運籌學》考點精講及復習思ｍａｘｚ＝ＣＸ＋ＡＸ＋ＡＸ＋ＩＸｓ＝Ｘ≥０，Ｘｓ≥標準ｍａｘｚ＝ＣＢＸＢ＋ＣＮＸＮ＋ＢＸＢＢＸＢ＋ＮＸＮ＋ＩＸＳ＝ＸＢ，ＸＮ，ＸＳ≥列初始單純形→初始單純形ｍａｘｚ＝ＣＢＸＢ＋ＣＮＸＮ＋ＢＸＢＢＸＢ＋ＮＸＮ＋ＩＸＳ＝ＸＢ，ＸＮ，ＸＳ≥初始單純形表迭代后單純形提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５檢驗數(shù)應(yīng)都小于等于０， Ｃ－ＣＢ－１Ｎ≤ Ｂ–ＣＢ－１≤ＢＢＢ又因為基變量的檢驗數(shù)可寫成ＣＢ·Ｉ＝０則可將檢驗數(shù)統(tǒng)一ＢＢＢＣ－ＣＢ－１ＡＢ００

令Ｙ＝Ｃ

Ｃ－ＹＡ≤ ＹＡ≥→–ＣＢＢ－１≤ｉｎω＝ ｚ＝ＣＢ－１ｂ＝ ｓ．ｔ．ＹＡ≥

–Ｙ≤ Ｙ≥Ｙ≥從上述推導可看出，檢驗數(shù)行的相反數(shù)恰好是其對偶問題的一個可行解。經(jīng)典例題［２－３］ 胡運權(quán)主編《運籌學教程》第三版，Ｐ５４，例３兩個互為對偶的線性規(guī)劃問題，分別再加上了松弛變量和剩余變量后ｍａｘｚ＝

＋

＋

＋

＋

ｍｉｎｗ＝１５ｙ１＋２４ｙ２＋５ｙ３＋０ｙ４＋６６ｙ２＋ｙ３－ｙ４５５ｘ２＋ｘ３＝１１

＋２ｘ＋

＝

＋２ｙ

＋

–ｙ５＝ｓ．ｔ．

ｉ ｘ１＋ｘ２＋ｘ５＝ ｘｊ≥０，ｊ＝１，２，３，４，

ｉ≥

１，２，３，４，用單純形法和兩階段法求得兩個問題的最終單純形表如下：原問題的最終單純形表提《運籌學》考點精講及復習思對偶問題的最終單純形經(jīng)典例題［２－２］ 北京交通大學２００９，一、５０分已知線性規(guī)劃問題如下：ｍｉｎｚ＝

＋

＋１２ｘ＋２ｘ＋１ｘ≥ ２ｓ．ｔ．

＋３ｘ３≥ｘ，ｘ，ｘ≥ １．求該問題的最優(yōu)解２．寫出該線性規(guī)劃問題的對偶問題，并求對偶問題的最優(yōu)解３．分別確定ｘｘ３的目標函數(shù)系數(shù)ｃｃ３在什么范圍內(nèi)變化最優(yōu)解不變９４．求約束條件右端值９

變

時的最優(yōu)解５．求增加新的約束條件ｘ１＋２ｘ２＋ｘ３５時的最優(yōu)解ｍｉｎｚ＝２ｘ＋５ｘ＋１ ２ ｍａｘω＝３ｙ１＋ｘ＋

＋１ｘ≥

ｙ１≤ｓ．ｔ．

２

２ｙ１＋ｙ２≤ｘ２＋３ｘ３≥ ｓ．ｔ． ｘ，ｘ，ｘ≥ ２ｙ１＋３ｙ２≤

單純形法求解原問題的最終表如下提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５ ＝０，０，６，０，９ Ｚ＝ Ｙ＝１，０，１，３， ω＝復習思路提示從上表中可以清楚地看出兩個問題變量之間的對應(yīng)關(guān)系。只需求解其中一個問題，從最優(yōu)解的單純形表中即可同時得到另一個問題的最優(yōu)解；注意單純形乘子為Ｙ＝ＣＢＢ－１，其與對偶變量之間的關(guān)系，經(jīng)常會考察“相差一個負號”的理解；單純形法的矩陣描述將廣泛地應(yīng)用到靈敏度分析部分中，要學會用Ｂ－１來求解每張表中的未知數(shù)值思考題［２－２］ （留待以后課程講解）昆明理工大學２０１２，二，２５分對于線性規(guī)劃問題：ｍａｘＳ＝１０ｘ１＋５ｘ２３ｘ１＋４ｘ２≤ｘ１≥０，ｘ２≥１．寫出此問題的對偶問題２．求出此問題和它的對偶問題的最優(yōu)解和最優(yōu)值。要點３ 線性規(guī)劃的對偶理論對稱弱對偶最優(yōu)對偶定理（強對偶性互補松弛經(jīng)典例題［２－ 清華大學教材編寫組《運籌學》第三版Ｐ５４，例原問ｍａｘｚ＝２ｘ１＋ｘ１＋２ｘ２≤

對偶問ｍｉｎｗ＝８ｙ１＋１６ｙ２＋ ≤

ｙ１＋４ｙ２≥ｓ．ｔ．４ｘ２≤ｘ，ｘ≥

ｙ１，ｙ２，ｙ３≥ 原問題化為極小問題，初始單純形表迭代至最終單純形表

提《運籌學》考點精講及復習思對偶問題用兩階段法求解的最終單純形表原問題化為極小化的最終單純形表兩個問題作一比較１．兩者的最優(yōu)值相同ｚ＝ｗ＝２．變量的解在兩個單純形表中互相包含原問題最優(yōu)解（決策變量）ｘ１＝４，ｘ２＝２←→對偶問題的剩余變量的檢驗對偶問題最優(yōu)解（決策變量提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５ｙ＝３，

＝１／８，

從引例中可見原問題與對偶問題在某種意義上來說，實質(zhì)上是一樣的，因為第二個問題僅僅在第一個問題的另一種表達而已。理論證明原問題與對偶問題解的關(guān)系對偶問題的基本性質(zhì)設(shè)原問題（１）ｍａｘｚ＝ＣＸＡＸ≤ｓ．Ｘ≥

對偶問題（２）ｗ＝ＹＡ≥ｓ．Ｙ≥—、對稱定定理：對偶問題的對偶是原問題。證對稱性原問

對偶問ｍａｘｚ＝ＡＸ≤ｓ．Ｘ≥

對 ｉｎω＝ ＹＡ≥ＣＹ≥將對偶問題兩邊同時取負號，ａｘ－ω＝－據(jù)對稱標準ｓ．ａｘ＝ｍａｘｚｓ．ａｘ＝ｍａｘｚ＝

ｉｎ（－ω＝－ｓ．–ＡＸ≥－ｓ．Ｙ≥

ｓ．

ＡＸ≤ｂＸ≥０

Ｘ≥二、弱對偶性定 若Ｘ和 分別是原問題（１）及對偶問題（２）的可行解，則有ＣＸ≤ － 證明：ＡＸｂＹＡＸ – ＹＡ≥ ＹＡＸ≥ － →ＣＸ≤ＹＡＸ≤ 從弱對偶性ＣＸＹｂ可得到以下重要結(jié)論（１）極大化問題（原問題）的任一可行解所對應(yīng)的目標函數(shù)值是對偶問題最優(yōu)目標函數(shù)值的下界。提《運籌學》考點精講及復習思（２）極小化問題（對偶問題）的任一可行解所對應(yīng)的目標函數(shù)值是原問題最優(yōu)目標函數(shù)值的上界。（３）若原問題可行，但其目標函數(shù)值無界，則對偶問題無可行解（４）若對偶問題可行，但其目標函數(shù)值無界，則原問題無可行解（５）若原問題有可行解而其對偶問題無可行解，則原問題目標函數(shù)值無界（６）若原問題無可行解，則其對偶問題具有無界解或無可行解三、最優(yōu)性定若Ｘ和Ｙ分別是（１）和（２）的可行解，且有ＣＸ＝Ｙｂ，則Ｘ，Ｙ分別是（１）和（２）的最優(yōu)解 證明：因為（１）的任一可行解Ｘ均滿足ＣＸＹ–∵ＣＸ＝Ｙ ∴ＣＸ≤則Ｘ為（１）的最優(yōu)解反過來可知：Ｙ也是（２）的最優(yōu)解。四、對偶定理（強對偶性）Ｂ若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，且兩者的目標函數(shù)值相等。證明：設(shè)Ｘ是原問題的最優(yōu)解，則其對應(yīng)的基Ｂ必存在ＣＣＢ－１Ａ≤０．Ｂ∵Ｙ＝ ∴ＹＡ≥即Ｙ使對偶問題的可行解，Ｂω＝Ｙｂ＝ＣＢ－１ＢＢＸ＝Ｂ－１ｂｚ＝ＣＸ＝ＣＢ－１ＢＢ∴ＣＸ＝ＣＢ－１ｂ＝ＹＢ∴據(jù)最優(yōu)性定理可知，Ｙ是對偶問題的最優(yōu)解。原問題與對偶問題的解，一般有三種情況：一個有有限最優(yōu) →另一個有有限最優(yōu)解一個有無界 →另一個無可行解兩個均無可行解。五、互補松弛性＾ 若Ｘ，Ｙ分別是原問題（１）與對偶問題（２）的可行解，，ＹＳ分別為（１）、（２）的松弛變量，則： ＾＝０，＝０Ｘ，Ｙ為最優(yōu)提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５證：設(shè)原問題和對偶問題的標準型原問題ＹＡ－ＹＳ＝ｓ．Ｘ，ＸＳ≥

對偶問題ｉｎω＝ＹｂＡＸ＋ＸＳ＝ｓ．Ｙ，ＹＳ≥ｚ＝ＹＡ－ＹＳＸ＝ＹＡＸ－ＹＳω＝ＹＡＸ＋ＸＳ＝ＹＡＸ＋ ∧ 若＝０，ＹＸＳ＝０；則ω＝Ｙｂ＝ＹＡＸ＝ＣＸ＝∧由最優(yōu)性質(zhì)，可知Ｘ，Ｙ是最優(yōu)解∧ 又若Ｘ，Ｙ分別是原問題和對偶問題的最優(yōu)解，根據(jù)最優(yōu)性質(zhì)有，ＣＸ＝ ∧ ｚ＝ＣＸ＝ＹＡ－ＹＳＸ＝ＹＡＸ－ＹＳ ∧ ω＝Ｙｂ＝ＹＡＸ＋ＸＳ＝ＹＡＸ＋∧→ＹＳ

＝ＹＸＳ＝經(jīng)典例題［２南京航天航空大學２０１０，一、簡答，５分１．簡述互補松弛性的內(nèi)涵。南京航天航空大學２０１１，一、簡答，５分２．簡述對偶問題的互補松弛性南京航天航空大學２０１２，一、簡答，５分４．何謂互補松弛性。經(jīng)典例題［２］：清華大學教材編寫組《運籌學》第三版Ｐ５９，例５已知線性規(guī)劃問題ｉｎ＝２ｘ１＋３ｘ２＋５ｘ３＋２ｘ４＋ｓ．ｔ．ｘ１＋ｘ２＋２ｘ３＋ｘ４＋３ｘ５≥４２ｘ１－ｘ２＋３ｘ３＋ｘ４＋ｘ５≥３ｘｊ≥０，ｊ＝１，２，…，已知其對偶問題的最優(yōu)解為 ＝４， ＝３；ｚ＝５。試用對偶理論找出原問題的最優(yōu)解 解：先寫出其對偶問題ｍａｘｚ＝４ｙ１＋３ｙ２ｙ１＋２ｙ２≤ｙ１–ｙ２≤ｓ．

＋３ｙ２≤ｙ１＋ｙ２≤３ｙ１＋ｙ２≤ ｙ，ｙ≥ 提《運籌學》考點精講及復習思由互補松弛性，可ＹＳＸ＝０ ＝∵ｙｓ２，ｙｓ３，ｙｓ４＞ ５∴ ＝ ＝ ５ ∴由題可

>０， ＞ｙ＝

>０， ＝３＞ 由互補松弛性Ｙ

＝０

ｓｉ∴ｘｓ１＝ｘｓ２＝０原問題ｎ＝２ｘ１＋３ｘ２＋５ｘ３＋２ｘ４＋ｓ．ｔ．ｘ１＋ｘ２＋２ｘ３＋ｘ４＋３ｘ５≥４２ｘ１－ｘ２＋３ｘ３＋ｘ４＋ｘ５≥３ｘｊ≥０，ｊ＝１，２，…，ｘ１＋ｘ２＋２ｘ３＋ｘ４＋３ｘ５＝４２ｘ１－ｘ２＋３ｘ３＋ｘ４＋ｘ５＝３因此，得到１＋ １４ ＋ ３

＝ ＝ 原問題的最優(yōu)解為Ｘ＝１，０，０，０，１ ＝說明：在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件為嚴格等式；反之如果約束條件取嚴格不等式，則其對應(yīng)的對偶變量一定為零。復習思路提示（１）對偶問題的性質(zhì)通常用小題型來考察，如選擇、判斷和填空等，分值大致在５分左右提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５（２）若考察大題，則通常也只作為大題中的一個小題，考察內(nèi)容可能是從已知的對偶問題的最優(yōu)解，求原問題最優(yōu)解，反之亦然證實原問題可行解是否為最優(yōu)解（３）牢記定理，證明過程略懂即可，以防萬一出相關(guān)證明題。思考題［２－３］ （留待以后課程講解）北京科技大學２０１１，一、（１）填空，２若對偶問題為無界解，則原問題 中山大學２００９，一、（３）多項選擇，５分２．下列說法正確的有 Ａ．若原問題及其對偶問題均具有可行解，則他們的目標函數(shù)值相等Ｂ．若原問題有無界解，則其對偶問題無可行解；若對偶問題無可行解時，其原問題具有無界解；Ｃ．已知ｙ為線性規(guī)劃對偶問題的最優(yōu)解，若ｙ >０則說明在最優(yōu)生產(chǎn)計劃中第ｉ種資源已完全耗盡； Ｄ．若某種資源的影子價格為ｋ，在其他條件不變時，該種資源增長１個單位，相應(yīng)目標函數(shù)值增大ｋ；Ｅ．任何線性規(guī)劃問題具有唯一的對偶問題。要點 影子價 在單純形法的每步迭代中，目標函數(shù)取值ｚ＝ＣＢ－ｂ，和檢驗數(shù)Ｃ－ＣＢ－Ｎ中都有乘子Ｙ＝ＣＢ－１，那么 經(jīng)濟意義是什么Ｂ影子價當線性規(guī)劃原問題求得最優(yōu)解ｘ（ｊ＝１，…，ｎ）時，其對偶問題也得到最優(yōu)解ｙ（ｉ＝１，…，ｍ 且代入各自的目標函數(shù)后有ｎｚ＝ｊ

＝ ＝ｉ 是線性規(guī)劃原問題約束條件的右端項，它代表第ｉ種資源的擁有量影子價格的定義（對偶變量

的意義代表在資源最優(yōu)利用條件下對單位第ｉ種資源的估價，這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻而作的估價，為區(qū)別起見，稱為影子價格（ｓｈａｄｏｗｐｒｉｃｅ）。經(jīng)典例題［２深圳大學２０１１，一、填空（１），２線性規(guī)劃最優(yōu)生產(chǎn)計劃中第ｉ種資源有剩余，則該資源的影子價格為 。北京交通大學２０１０，一、判斷（３），２分３．影子價格大于０，表示其對應(yīng)資源已完全消耗完。南京航天航空大學２０１１，二、簡答（１），５分１．簡述影子價格及其經(jīng)濟意義南京航天航空大學２０１２，一、簡答（１），５提《運籌學》考點精講及復習思１．簡述影子價格的含義原問題化為極小化的最終單純形表影子價格的經(jīng)濟意∑【１】影子價格是一種邊際價格∑在ｚ

∑ｃ

＝ｍｂ ＝ｗ中 ＝ｉｂｊ ｉｉｂｊ ｉ 說明增量

的值相當于在資源得到最優(yōu)利用的生產(chǎn)條件下，ｂｉ每增加一個單位時目標函數(shù)ｚ幾何解釋：圖解法分析ｍａｘｚ＝２ｘ１＋３ｘ２ｘ１＋２ｘ２≤４ｘ１≤１６４ｘ２≤【詳見課程視頻【２】影子價格又是一種機會成本ｙ＝３，ｙ＝１，ｙ＝ 在純市場經(jīng)濟條件下，當?shù)冢卜N資源的市場價格低于１／８時，可以買進這種資源當市場價格高于影子價格時，就會賣出這種資源隨著資源的買進賣出，它的影子價格也將隨之發(fā)生變化，一直到影子價格與市場價格保持同水平時，才處于平衡狀態(tài)【３】在對偶問題的互補松弛性質(zhì)中提考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課 電話：４００６８８５ 當∑ｊ＜ｂｉ時，ｙｉ＝ｊ 當ｙ＾ｉ＞０時，∑ｊ＝ｊ這表明生產(chǎn)過程中如果某種資源ｂｉ未得到充分利用時，該種資源的影子價格為零；又當資源的影子價格不為零時，表明該種資源在生產(chǎn)中已耗費完畢。復習思路提示（１）影子價格考察的內(nèi)容通常就兩部分影子價格大于或等于０所代表的資源消耗情況簡述影子價格的經(jīng)濟意義（２）考察分值在５分以內(nèi)，以選擇和判斷多見。思考題［２－３］ （留待以后課程講解）中山大學２００９，一、（３）多項選擇，５分３．下列說法正確的有（ Ａ．若原問題及其對偶問題均具有可行解，則他們的目標函數(shù)值相等Ｂ．若原問題有無界解，則其對偶問題無可行解；若對偶問題無可行解時，其原問題具有無界解；Ｃ．已知ｙ為線性規(guī)劃對偶問題的最優(yōu)解，若ｙ >０則說明在最優(yōu)生產(chǎn)計劃中第ｉ種資源已完全 耗盡Ｄ．若某種資源的影子價格為ｋ，在其他條件不變時，該種資源增長１個單位，相應(yīng)目標函數(shù)值增ｋＥ．任何線性規(guī)劃問題具有唯一的對偶問題。要點５ 對偶單純形法對偶單純形法的基本思對偶單純形法的計算步原問題每次迭代的單純形表的檢驗數(shù)行對應(yīng)其對偶問題的一個基解。設(shè)原問題和對偶問題的標準型是原問 對偶問ｍａｘｚ＝ ｍｉω＝ｓ．

ＡＸ＋ＸＳ＝ｂＸ，ＸＳ≥０

ｓ．

ＹＡ－