運(yùn)籌學(xué)考點(diǎn)精講及復(fù)習(xí)思路

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

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

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

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

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

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

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

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

ａ> ＝ 可確保ｘ０θａ

＝０，ｉ＝≥０，ｉ≠

此時(shí)與ｘ

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

＝∑ｃｘｉｉｚ１＝

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

ｍｃａ＝ｚ０＋θｃ

ｍｃａ ｉｍ

ｉｉｍ

ｉ１

ｉ１ｚ

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

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

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

>＝ａ ａ

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

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

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

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

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

提《運(yùn)籌學(xué)》考點(diǎn)精講及復(fù)習(xí)思ｓ． －Ｙ′Ａ≥Ｙ′≥

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

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

（Ｙ，Ｙ）

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

＋

＋１２ｘ ＋ｘ

２３ｓ．ｔ．

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

變

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

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

１ｘ≥３２３

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

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

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

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

令Ｙ＝Ｃ

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

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

＋

＋

＋

＋

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

＋２ｘ＋

＝

＋２ｙ

＋

–ｙ５＝ｓ．ｔ．

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

ｉ≥

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

＋

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

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

變

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

＋１ｘ≥

ｙ１≤ｓ．ｔ．

２

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

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

對(duì)偶問ｍｉｎｗ＝８ｙ１＋１６ｙ２＋ ≤

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

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

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

＝１／８，

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

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

對(duì)偶問ｍａｘｚ＝ＡＸ≤ｓ．Ｘ≥

對(duì) ｉｎω＝ ＹＡ≥ＣＹ≥將對(duì)偶問題兩邊同時(shí)取負(fù)號(hào)，ａｘ－ω＝－據(jù)對(duì)稱標(biāo)準(zhǔn)ｓ．ａｘ＝ｍａｘｚｓ．ａｘ＝ｍａｘｚ＝

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

ｓ．

ＡＸ≤ｂＸ≥０

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

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

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

＋３ｙ２≤ｙ１＋ｙ２≤３ｙ１＋ｙ２≤ ｙ，ｙ≥ 提《運(yùn)籌學(xué)》考點(diǎn)精講及復(fù)習(xí)思由互補(bǔ)松弛性，可ＹＳＸ＝０ ＝∵ｙｓ２，ｙｓ３，ｙｓ４＞ ５∴ ＝ ＝ ５ ∴由題可

>０， ＞ｙ＝

>０， ＝３＞ 由互補(bǔ)松弛性Ｙ

＝０

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

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

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

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

∑ｃ

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

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

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

ｓ．

ＹＡ－