提提《《運籌學》名解析及典型題精講精第１專題 線性規劃與單純形~、復習方法與【１】考試題作為整個線性規劃部分（還包括對偶問題與靈敏度分析、問題、目標規劃、整數規劃）的最基礎知識點，該部分考試分值高達３０分以上，且為各校必考知識點！考試題型遍布選擇、填空、簡答、判斷和計算等各類型。【２】復習方法與注意事要很好地理解該部分的知識要點，必須先熟悉線性代數部分關于基、線性方程組的解、極大線性無關組、矩陣的秩、初等行變換等相關內容；該部分以熟練計算為主，由于迭代步驟繁雜，很容易在計算過程中出錯并影響最后的結果【３】與答題方即使不太理解單純形法的原理，也可以按部就班地按照列初始單純形表，牢記表中各已知系數和未知參數的位置即可；迭代是最容易出錯的地方，需牢記換入換出變量的選取規則（注意極大化和極小化），并會用矩陣的初等行變換進行換基；牢記最優解判別準則，題后都要單列最優解和對應的目標函數值二、重難點內容精講重點１）單純形法求解線性規劃問題；２）解的性質；３）線性規劃問題建模。難點：１）單純形法原理的理解；２）線性規劃問題建模。重點 單純形法求解線性規劃問【１】進行標準化，列初始單純形表方１考考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課：４００６８８５初始單純形【２】單純形法計算步驟框交通大學２００５年考研試題［１］：參數線性規劃問題（參數ｔ０）ａｘｚｔ）＝（３＋２ｔ）ｘ１＋（５－ｔ）ｘ２ｘ１≤２ｘ２≤１２３ｘ１＋２ｘ２≤ ｘ，ｘ≥ １）令ｔ＝０用單純形法求解２）考慮ｔ的不同取值對最優解的影響題型解析：該題型屬于參數線性規劃問題，先是了單純形法求解線性規劃問題，再通過對參《《運籌學》名解析及典型題精講精數取值的分析，解的判別原理等內容。總體而言，是一道對基礎的線性規劃求解問題提高加深后的問題，求解該類題型要熟練掌握單純形法計算步驟以及當參數發生何種變化（檢驗數變化）對最優解的影響。難點單純形法原理的理２００４年考研試題［１－２］：設ｘ是線性規劃的一個基可行解，如果其中一個分量ｘｊ＝０，則（ Ａ．只有該解不時，ｘｊ才可能是一個基變量Ｂ．只有該解時，ｘｊ才可能是一個基變量Ｃ．無論該解是否，ｘｊ一定是一個基變量Ｄ．只有該解時，ｘｊ才一定是一個非基變量題型解析：該題型的是解的特殊情況，當某個基變量的檢驗數取值為０時，該解釋退化解。中國科學技術大學２００１年考研試［１－３］：對ＬＰ問題ｍａｘｚ＝ＣＸ，ＡＸ＝ｂ，Ｘ≥０利用單純形法求解時，每作一次換基迭代，都能保證它相應的目標函數值ｚ必為（ ）。Ａ．增大 Ｂ．不減少 Ｃ．減少 Ｄ．不增大中國科學技術大學２００２年考研試題［１］：單純形法迭代過程中，如果不按最小比值規則選取換出變量，則在下一個解中至少一個有基變量的值為負值。題型解析：該題型的單純形法的迭代原理，應熟練掌握換出和換入變量的選擇原理以及解的判別定理，才能應對各種角度的出題形式。中國科學技術大學２００２年考研試［１５］：一旦一個人工變量在迭代中變為非基變量后，該變量及相應列的數字都可以從單純形表中刪除，而不影響計算結果。題型解析：該題型的是人工變量法中的兩階段法，當第一階段中的人工變量均取值為０時，原問題才有可行解，則可去除人工變量后接著第二階段的計算。３考考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課：４００６８８５２００５年考研試題［１－６］：用大Ｍ法求解ＭＡＸ型線性規劃時，人工變量在目標函數中的系數均為 ，若最優解的 中含有人工變量，則原問題無解。題型解析：該題型的是人工變量法中的大Ｍ法，如何用人工變量構造初始可行基，并列出標準型需要理解罰因子“Ｍ的含義。重點２ 解的性質重要結論：【１】可行域若有界則是凸集，也可能是域【２】每個基可行解對應可行域的一個頂點【３】可行域有有限多個頂點【４】如果有最優解，必在某個頂點上得到；線性規劃解之間的關系歸納“箭尾的解一定是箭頭的解，反之不一定成立．當最優解唯一時，最優解也是基最優解當最優解不唯一時，最優解不一定是基最優解．理工大學２００７年考研試題［１－７］：判斷１．線性規劃問題的最優解一定是基可行解２．線性規劃的最優解只在可行域的頂點上達到；３．若線性規劃問題存在最優解，則必有基最優解；４．線性規劃問題的每一個基可行解對應著可行域上的一個頂點；５．當線性規劃的可行解集非空時，該解集一定有界；題型解析：該類題型以考生對線性規劃解的性質及解之間的關系的熟悉程度為主，其實多數都是由上的幾個重要結論反復變化的題型，只需理解重點結論，其他變化均可由其推演得來。理工大學２００６年考研試題［１－８］：對于線性規劃問題，下列說法正確的是 Ａ．線性規劃問題可能沒有可行解；Ｂ．線性規劃問題的可行域都是凸集Ｃ．線性規劃問題如果有最優解，則最優解可以在可行域的頂點上達到；Ｄ．上述說法都正確。４《《運籌學》名解析及典型題精講精中國科學技術大學２００３年考研試［１－９］：若某一線性規劃問題在其可行域Ｄ上的Ｋ個頂點（ ）取得最優解。試證明：該線性規劃問題有無窮多個最優解。題型解析：該題型考生對線性規劃解的性質的靈活應用，以及對凸組合、凸集等概念的理解，需理解凸集的數學描述式，并將其與線性規劃最優解和最優值聯系起來求證。證明題次數少。重點 線性規劃問題建線性規劃數學模型的三要素決策變量：需決策的量，即待求的未知數，一般記為ｘｊｊ＝１，２，…，ｎ目標函數：需優化的量，即欲達到的目標，用決策變量的表達式表示，一般記為ｚ；約束條件：為實現優化目標需受到的限制，用決策變量的等式或不等式表示。建立線性規劃數學模型的步驟：確定問題決策變量確定問題的目標，并表示為決策變量的線性函找出問題的所有約束條件，并表示為決策變量的線性方程組中國科學技術大學２００３年考研試題［１－１０］：某公司擬在下一年度的１－４個月內需租用倉庫堆放物資。各月份所需倉庫面積數如表１所示。倉庫租借費用隨合同期而定，期限越長，折扣越大，具體數字如表２所示。租借倉庫的合同每月初都可辦理，每份合同具體規定租用面積和期限，因此該廠可根據需要，在任何一個月初辦理租借合同，每次辦理時可簽一份，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂最合同的最優決策，目的是使所付租借費用最小。（只建模，不求解）題型解析：建模題通常用來考生是否掌握由實際問題提煉出線性規劃數學模型的能力，這也是實際中更重要的能力。而該題型涉及到了月份數和面積數兩個需要同時確定的數，在假設決策變量時就應該想到雙下標變量。建模題的解題步驟一般都是“決策變量－目標函數－約束條件”。表月１２３４所需倉庫面積（單位：百平米表合同租借期１個２個３個４個合同期內（元／百平米、西安電子科技大學２００４年考研試題［１－１１］：某公司生產家用的清潔產品，為了競爭中增加市場份額，公司決定進行一次大規模的廣告行動。公司準備做的三種產品名稱，估計每做一單位使每種產品的市場份額增加量、公司５考考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課：４００６８８５擬定的后每種產品市場份額增加量的最低目標和兩種可選的方式的單價，如下表所示。其中洗衣粉的市場份額出現負值是由于液體洗滌劑的份額增加會造成洗衣粉份額的減少。現公司需擬定使總費用最少的計劃，即決定電視和印刷的數量。建模，不必求解。題型解析：該類題型其實是最簡單的建模題型，但往往用冗長的背景介紹引起考生的焦慮情緒，只要冷靜下來仔細審題，可以很容易求解。電印刷后市場份額最低增量去污液體洗滌洗衣–單位成本（萬元）哈爾濱工業大學２００５年考研試［１－１２］：某快餐店在確定服務員雇傭計劃。可雇傭全職服務員和服務員，全職服務員每天工作７小時，服務員每天工作４小時，快餐店從上午１１點開始營業到晚上２１點關門，預計每小時需求人數如下表所示。這是滿足服務的必要保證。全職服務員于某整點時刻開始上班，工作４小時，休息１小時，再工作３小時；服務員也于某整點時刻開始上班，工作４小時候下班。全職服務員的費用是每小時１２元（每天８４元），服務員的費用是每小時８元（每天３２元）。建立該問題的數學模型，目標是使快餐店的用工費用最少。不必求解。時所需人１１：００－１２：７１２：００－１３：８１３：００－１４：９１４：００－１５：１５：００－１６：１６：００－１７：８１７：００－１８：１８：００－１９：１９：００－２０：８２０：００－２１：８題型解析：該題型是比較常見的建模題用工計劃，如何安排合適的人力使用工費用最少。而此題又涉及到了兩種不同的變量“全職”和“”，這點處理上比較難想到。比較常見建模題還有投計劃和生產計劃，可多加練習６《《運籌學》名解析及典型題精講精第２專題 對偶問題與靈敏度分~、復習方法與【１】考試題該部分知識點為各校必考知識點！考試題型遍布選擇、填空、簡答、判斷和計算等各類型，常與“線性規劃與單純形法”此章綜合出題。該部分知識點最普遍的內容包括根據原問題寫出對偶問題、用單純形法求原問題最優解并求對偶問題最優解、當模型中的ａ，ｂ，ｃ等系數發生改變時對最優解的影響。【２】復習方法與注意事據原問題寫對偶問題，根據自己的把“原問題與對偶問題的對應關系表”編成口訣以便牢記；對偶問題的性質通常用小題型來，如選擇、判斷和填空等，沖刺復習時，把所有性質羅列出來，注意標注各性質的遞進關系以加深理解，各性質和定理的證明過程留意關鍵步驟，以防萬一出證明題；注意每一張單純形表中都有對應的當前的Ｂ－１，已知每張表的Ｂ－１就可以推斷出每張單純形表其他位置的數值。這個的是對單純形表矩陣描述的掌握程度；價格的經濟意義同樣也是需要的部分，經常簡答題和選擇、判斷等題型，頻率也很高靈敏度分析，無論是哪個參數的變化或是增加約束條件，都是在原最終單純形表中進行分析的【３】與答題方根據線性規劃原問題寫對偶問題，建議先根據原約束條件的個數確定對偶問題變量數，再寫出對偶問題的目標函數和約束條件（留待最后判別約束條件和變量的符號）；該部分出大題的話，通常是幾個小問題疊加的，無論是哪個小題不會，都要盡力把每道題都做一做，數學類考試基本都是按步驟給分的，有時列個表或給出公式就能得分。尤其在靈敏度分析的計算題中要注意。二、重難點內容精講重點１）原問題與對偶問題的關系７考考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課：４００６８８５２）單純形法的矩陣描述；３）價格；４）靈敏度分析難點：對偶問題的性質重點１ 原問題與對偶問題的關系原問題和對偶問題的對應關系口訣大化小，約束讓變量反號，變量讓約束同號；小化大，變量讓約束反號，約束讓變量同號。原問題與對偶問題的對應關系ｍａｘｚ＝ＣＸｍｉｎω＝ｓ．

Ｘ≥０

ｓ．

ＹＡ≥Ｙ≥

標準對稱ｍａｘｚ＝ＣＸｍｉｎω＝ｓ．

Ｘ≥０

ｓ．

ＹＡ≥Ｙ≤ｍａｘｚ＝ＣＸｍｉｎω＝ｓ．

Ｘ≥

ｓ．

ＹＡ≥Ｙ無約２００２年考研試題［２１］：某廠使用甲、乙、丙三種原料生產Ａ、Ｂ兩種產品，每生產一噸Ａ產品需要原料甲０．６噸，原料乙０．２噸，原料丙０．３噸；每生產一噸Ｂ產品需要原料甲０．３噸，原料乙０．６噸，原料丙０．４噸。三種原料的成本分別為１８元／噸、１４元／噸、１２元／噸；可使用的數量分別為３０噸、２０噸、４０噸；每生產一噸Ａ、Ｂ產品的生產成本為５元和３元；他們的市場分別為３７元和４２元，參數如表１所示。構造的求利潤最大的線性規劃模型用ＥＸＣＥＬ表求解后的敏感性分析報告如表２所示８《《運籌學》名解析及典型題精講精表ＡＢ原料成本（萬元／噸可用數量（噸甲０．０．１８．乙０．０．１５．丙０．０．１２．生產成５３表可變單元單元名終遞減成目標函數系允許的增允許的減＄Ｃ＄產品Ａ產０１４．７＄Ｄ＄產品Ｂ產０２２．１５．約單元名終價格約束限制允許的增允許的減＄Ｇ＄原料甲使用＄Ｇ＄原料乙使用＄Ｇ＄原料丙使用０ＩＥ＋題型解析：該題型是針對對偶問題及靈敏度分析的綜合提高性題，其更注重實際應用中的軟件求解，需要把中常見的模型與ＥＸＣＥＬ敏感性分析表中的元素聯系起來。１）請寫出該問題的數學模型及其對偶問題２）如果原料甲和原料乙各增加１０噸，當前基是否仍保持最優，如果各減少１０噸呢？３）Ａ、Ｂ產品的價格在什么范圍內變化時該問題的最優基保持不變？４）請根據敏感性分析報告說明哪種原料最緊缺，哪種原料最不緊缺，并說明你的理由５）該廠正考慮生產一種新產品Ｃ，該產品計劃售價為５０元，生產成本為７元，需要０．４噸原料甲，０．７噸原料乙，０．３噸原料丙，問：是否該生產這種新產品？難 對偶問題的性對稱定理：對偶問題的對偶是原問題－ 弱對偶性：若Ｘ，Ｙ分別是原問題及對偶問題的可行解，則有ＣＸＹｂ性：若原問題（對偶問題）為解，則其對偶問題（原問題）無可行解。最優性：設Ｘ，Ｙ分別是原問題及對偶問題的可行解，當ＣＸ＝Ｙｂ時，Ｘ，Ｙ是最優解。考考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課：４００６８８５對偶定理：若原問題有最優解，那么對偶問題也有最優解，且目標函數值相等互補松弛性：若Ｘ，Ｙ分別是原問題及對偶問題的可行解，則ＹＸＳ＝０，ＹＳＸ＝０當且僅當Ｘ，Ｙ為最優解。中國科學技術大學２００１年考研試［２－２］：若ＬＰ問題的對偶問題無可行解，則原問題必定為 Ａ．無可行解 Ｂ．無基解 Ｃ．無基可行解 Ｄ．無最優解中國科學技術大學２００２年考研試題，判斷［２－３］：若某一線性規劃問題的對偶問題為解，那么該線性規劃問題一定無可行解 題型解析：該類題型基本都是圍繞著原問題與對偶問題解之間的關系來出題，重點ＣＸ≤Ｙｂ和當兩者均有最優解時，ＣＸ＝Ｙｂ。大連理工大學２００４年考研試題，判［２４］：若一線性規劃問題及其對偶問題均具有可行解，則兩者均具有最優解，并且原問題與對偶問題的最優值相等。哈爾濱工業大學１９９７年考研試［２－５］：線性規劃的原問題與其對偶問題之間存在如下關系（ Ａ．對偶問題的對偶問題是原問題；Ｂ．原問題存在可行解，其對偶問題必存在可行解；Ｃ．原問題無可行解，其對偶問題必無可行解；Ｄ．原問題有無窮多最優解，其對偶問題也有無窮多最優解。交通大學２００４年考研試題［２－６］：下列關于線性規劃的原問題與其對偶問題之間關系敘述不正確的是（ Ａ．若原問題有無窮多最優解，則其對偶問題也有無窮多最優解；Ｂ．設ｙ為對偶問題的最優解，若ｙ＝０，說明在最優生產計劃中第ｉ種資源一定消耗完畢 Ｃ．任何線性規劃問題存在唯一的對偶問題Ｄ．如果原問題與對偶問題都有可行解，則他們必有最優解。重點２ 單純形法矩陣描述迭代后單純形《《運籌學》名解析及典型題精講精矩陣描述時的常用公

＝Ｂ－１Ｎ＝Ｂ－１σＮ＝

–

Ｂ－１ｚ＝ＣＢ－１ 當已知一個線性規劃的可行基Ｂ時，先求出Ｂ－１，再用這些運算公式可得到單純形法所要求的結果。２００３年考研試題［２］：考慮線性規劃問題ｍｉｎｚ＝－４ｘ１＋ｘ２＋３０ｘ３－１１ｘ４－２ｘ５＋３ｘ６＋－２ｘ１＋６ｘ３＋２ｘ４－３ｘ６＋ｘ７＝－４ｘ１＋ｘ２＋７ｘ３＋ｘ４－ｘ６＝１０－５ｘ３＋３ｘ４＋ｘ５－ｘ６＝ｘｊ ≥０，ｊ＝１，２，…，ｘｊ用單純形法求解，初表及終表如表１和表２所示。表１表題型解析：該題型的是單純形法矩陣描述的相關知識，且給出的是與平時常見的線性規劃不同的模型，其初始可行基不是構造的，而是直接在模型中恰好就有的，這在解答過程中就要注意與平時求解的不同，因為沒有添加松弛變量。１）填完初表和終表各空白，并說明所得最優解是否唯一？為什么–２）考慮當ｂ變為ｂ

１３，對最優解有什么影響考考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課：４００６８８５–當ｂ變為ｂ

１４，對最優解是否有影響３）對偶問題最優解？重點３ 價格價格的定義（對偶變量

的意義代表在資源最優利用條件下對單位第ｉ種資源的估價，這種估價不是資源的市場價格，而是根據資源在生產中作出的貢獻而作的估價，為區別起見，稱為價格（ｓｈａｄｏｗｐｒｉｃｅ）。價格的經濟意義１）價格是一種邊際價格 ｚ＝∑ｘ＝∑ｂｙ＝ｊ ｉｊ ｉｚｂ在ｂｉ說明增量

＝ｙｉ中的值相當于在資源得到最優利用的生產條件下，ｂｉ每增加一個單位時目標函數ｚ２）價格就是對偶變量的最優值３）生產過程中如果某種資源ｂｉ未得到充分利用時，該種資源的價格ｙ

＝０；又當資源的子價格

０時，表明該種資源在生產中已耗費完畢４）若第ｉ種資源的單位市場價格為ｍｉ，當ｙｉ＞ｍｉ時，企業愿意購進這種資源，單位純利潤為ｙｉ－ｍｉ，則有利可圖；如果ｙｉ＜ｍｉ，則企業有償轉讓這種資源，可獲單位純利為ｍｉ－ｙｉ，否則企業無利可圖，甚至虧損。２００３年考研試題［２－８］：以下關于對偶解的陳述中正確的是 Ａ．對偶解的經濟含義是它所對應的變量的改變量與目標函數改變量的比值；Ｂ．實際成本大于０的資源的對偶解可能為零；Ｃ．一種資源的對偶解總大于為該資源付出的價格；Ｄ．一種資源的對偶解總小于為該資源付出的價格［２－９］：一種資源的價格的大小可以衡量該資源的稀缺程度題型解析：該類題型基本都是圍繞著前面講過的價格的幾種意義來出題的，需要對價格的經濟意義和數學描述的意義都十分了解。大連理工大學２００５年考研試［２－１０］：若某種資源的價格等于ｋ，在其他條件不變的情況下，當該種資源增加８個單位時，相應的目標函數將增大８ｋ。《《運籌學》名解析及典型題精講精２００３年考研試題［２－１１］：在使用單純形表求解線性規劃時，資源的價格在單純形表的什么位置上？２００３年考研試題［２－１２］：寫出價格的數學表達式并用定義加以驗證重點４ 靈敏度分析ｂ變化，只影響表中ｂ列的值，即最終表中原問題的解相應發生變化；ｃ變化，影響檢驗數行的值；ａ變化，要先求出新的該系數列向量及其對應的檢驗數增加約束條件，不滿足原最優解時，加入松弛變量填入最終表理工大學２００４年考研試題［２１３］：某公司制造三種產品Ａ、Ｂ、Ｃ，需要兩種資源（勞動力與原材料），這些產品對兩種資源的需求、單位利潤以及該公司的資源限制如表１所示，要求確定總利潤最大的最優生產計劃。表產品產品產品該公司的資源限每單位產品的資源需勞動６３５原材３４５每單位產品的利３１５設ｘｘｘ３分別是產品Ａ、Ｂ、Ｃ的產量，可以得到該問題的線性規劃模型如下：ｍａｘｚ＝３ｘ１＋ｘ２＋５ｘ３ｓ．ｔ．３ｘ１＋４ｘ２＋５ｘ３≤ｘ１，ｘ２，ｘ３≥該線性規劃問題的最終單純形表如表２所示考考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課：４００６８８５１）求使最優解不變的產品Ａ的單位利潤變動范圍。問Ｃ１＝２時，最優解變不變？２）從表２中判斷該規劃最優解是否唯一，并說明理由。３）求出使原材料對偶價格不變的ｂ２的變化范圍４）由于技術上的突破，每單位產品Ｂ對原材料的需求量減少為２個單位，這時是否需要改變生產計劃？為什么？５）假如這時，又試制新產品Ｄ，生產一個單位新產品Ｄ需要勞動力４個單位，原材料３個單位，而每單位的新產品Ｄ的利潤為３元。請問這時生產計劃是否需要進行修改？為什么？如果需要修改，怎樣修改？題型解析：該題型靈敏度分析中的ｃ、ｂ、ａ和增加一個變量對最優解影響，需要熟練掌握各個變化影響的元素，并掌握如何利用最終表中的Ｂ－１去求得新的系數列向量和檢驗數等。提提《《運籌學》名解析及典型題精講精第３專題 問~、復習方法與【１】考試題該部分知識點為各校重點知識點！考試題型通常以計算題為主，有時結合建模并求解該部分知識點內容包括最小元素法、伏格爾法求初始解，閉回路法、位勢法求檢驗數，閉回路法迭代原理以及當表格中的某些參數發生改變時對最優解的影響。【２】復習方法與注意事牢記問題必有最優解牢記產銷平衡時問題基變量個數是ｍ＋ｎ－１個若題中未規定用何方法求初始解，建議用伏格爾法，其求得的初始解最接近最優解，可減少后續迭代步驟；通常考試中最多只會出４個產地４個銷地的情況，比較容易計算，可多練習類似習題【３】與答題方計算過程中，一定要分位運價、運量、檢驗數的數值，以防張冠李戴！建議將檢驗數表單獨列出來。產銷不平衡問題要虛擬一個產地或銷地，化成產銷平衡問題求解，此時基變量個數為ｍ＋ｎ；最小元素法求產銷不平衡問題時，虛擬的０運價留到最后再考慮，可以迭代得更快些二、重難點內容精講重點：表上作業法難點：實際應用題建模。重點 表上作業法【１】問題及其數學模型產銷平衡問題的數學模型 ｍｉｎｚ＝∑∑ｃｉｊｉ１ｊｎ∑ｘｉｊ＝ａｉ，ｉ＝１，２，…，ｊ∑ｘ∑ｘ

＝ｂｊ，ｊ＝１，２，…，ｉｘｉｊ≥０，ｉ＝１，２，…，ｊ＝１，２，…考考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課：４００６８８５１）問題是約束方程組具有特殊系數矩陣的線性規劃問題；２）問題必有最優解；３）ｍ個產地ｎ個銷地的產銷平衡問題基變量個數為ｍ＋ｎ－１個；可推出產銷不平衡問題的基變量個數為ｍ＋ｎ個。【２】表上作業法的求解步驟１）列出產銷平衡表；２）確定初始基可行解，即ｍ＋ｎ個數字格，確定初始解的方法有西北角法：從左上角的第一個元素開始選取，優先安排運價表上最小的產地和銷地之間的運輸業務。最小元素法：從運價表中最小的運價開始確定供銷關系，然后次小，直到給出初始基可行解為止。伏格爾法：在運價表中分別計算出各行各列的次小運費和最小運費的差額；從行或列差額中選最大者，選擇它所在行或列中的最小元素，在最小元素格填數，并劃去運價表中相應的行或列；依次，直到給出初始解為止。３）求空格處（非基變量）的檢驗數閉回路法：閉回路是指除起點和終點是同一空格以外，其余頂點均為有數字格的曲折閉合多邊形，凡可行調運方案只能畫唯一閉回路，沿空格的閉回路增加１個單位的量，由此帶來的費用的代數和就是該空格的檢驗數。位勢法：利用ｃｉｊ－（ｕｉ＋ｖｊ）求出所有空格的檢驗數；從基變量的檢驗數為０推出ｕ和ｖ的所有（令ｕ１＝０），再由此推出所有空格的檢驗數【３】問題的特殊情：在確定初始基可行解時，有可能在產銷平衡表上填入一個數字后，在單位運價表中同時劃去一行和一列（不是最后一步），或者是閉回路法調整時出現兩個或兩個以上具有（－１）標記的相等最小值，只能調入一個，這時就出現。用表上作業法求解問題當出現時，在相應的格中一定要填一個０（對應同時劃去的那行或那列的任一空格處），以表示此格為數字格。【４】產銷不平衡問注：此類問題都要轉化成產銷平衡問題才能用表上作業法求解！！！產大于銷：虛擬一個銷地，其單位運價為０，虛擬銷量為 ｂｎ＋１＝∑ａ－∑ｂ＝∑ｎ＋１ｉ１ ｊ１ ｉ１產小于銷：虛擬一個產地，其單位運價為０，虛擬產量 ａｍ＋１＝∑ｂｊ－∑ａｉ＝∑ｍｊｊ１ ｉ１ ｊ１理工大學２００８年考研試題《《運籌學》名解析及典型題精講精［３－１］：多項選擇題。具有ｍ個產地ｎ個銷地的平衡問題模型具有特征（ Ａ．有ｍｎ個變量，ｍ＋ｎ個約束 Ｂ．有ｍ＋ｎ個變量，ｍｎ個約束Ｃ．有ｍｎ個變量，ｍ＋ｎ－１個約束 Ｄ．系數矩陣的秩等于ｍ＋ｎ－１Ｅ．有ｍ＋ｎ－１個基變量，ｍｎ－ｍ－ｎ＋１個非基變量題型解析：該題型的是對問題數學模型的理解：問題是特殊的線性規劃問題，有ｍｎ個變量，ｍ＋ｎ個約束，其系數矩陣的秩小于等于ｍ＋ｎ－１。理工大學２００６年考研試題［３－２］：多項選擇題。在問題中，下列錯誤說法是 Ａ．若變量組Ｂ包含有閉回路，則Ｂ中的變量對應的列向量線性無關Ｂ．問題的對偶問題不一定存在最優解Ｃ．平衡問題的對偶問題的變量非負Ｄ．第ｉ行的位勢Ｕｉ是第ｉ個對偶變量題型解析：該題型的主要是問題及其對偶問題之間的關系，以及位勢法的原理。選項Ａ錯誤是因為既然能畫閉回路，那么各變量之間就存在一線性組合式等于０，即線性相關。交通大學２００３、２００４年考研試題［３－３］：在問題中，能夠作為表上作業法的初始基可行解的調運方案應滿足的條件是（ Ａ．有ｍ＋ｎ－１個基變量Ｂ．基變量不構成閉回Ｃ．有ｍ＋ｎ個基變量且不構成閉回Ｄ．有ｍ＋ｎ個非零的基變量且不構成閉回題型解析：該題型的是問題迭代原理：初始基可行解必須對應線性無關的基向量，即不構成回路，且問題的每一張表上有ｍ＋ｎ－１個數字格（即基變量）。大連理工大學２００５年考研試［３－４］判斷題：當所有產地產量和銷地銷量均為整數值時，問題的最優解也為整數值。理工大學２００８年考研試題［３－５］：問題的檢驗數是其對偶問題的松弛變量。大連理工大學２００５年考研試題［３－６］：用最小元素法給出問題初始調運方案有什么優勢？又有什么缺陷？問題的數學模型為什么不用單純形法用表上作業進行求解？題型解析：該題型的是最小元素法的思路及缺點，以及對問題是特殊線性規劃問題的理解，如其特殊的稀疏的系數矩陣。理工大學２００５年考研試題［３－７］：用表上作業法求解該問題考考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課：４００６８８５ＡＢＣ產甲３６５乙８５７丙４９８銷題型解析：可以看出該題型的是產銷不平衡問題的表上作業法，產大于銷，要虛擬銷地。另外題意未指定求解方法，故推薦用伏格爾法可得到最接近最優解的初始解，從而減少迭代次數。難點 實際應用題建模問題及其數學模型產銷平衡問題的數學模 ｍｉｎｚ＝∑∑ｃｉｊｉ１ｊｎ∑ｘｉｊ＝ａｉ，ｉ＝１，２，…，ｊ∑ｘ∑ｘ

＝ｂｊ，ｊ＝１，２，…，ｉｘｉｊ≥０，ｉ＝１，２，…，ｊ＝１，２，…ｎ建模步驟：１）決策變量；２）目標函數；３）約束條件。問題在實際生活中有許多應用實例，如船只調度、生產安排、貨物中轉等問題。所以有時有的高校也會考到這個知識點的建模題。華技大學２００４年考研試［３８］：某廠根據合同要在未來三個月月末提供不同數量的同種產品，該廠正常時間和加班時間生產能力和單位生產成本如下表所示。月需求量（件最大產量（件單位生產成本（元正常時加班時正常時加班時１２３提提《《運籌學》名解析及典型題精講精又已知生產的產品若當月不交貨，則存入庫存，每月的單位成本為２元，倉庫容量限制為５００件，１月初和３月末無存貨。問如何安排生產計劃，使總費用最小？（要求建立問題的數學模型，不必求解）題型解析：該題型的是生產計劃安排問題，生產與交貨等同于產地和銷地的問題，該題又添加了可以的條件，因此要多考慮費用。哈爾濱工業大學２００７年考研試［３－９］：如圖３－１所示，某公司有兩個工廠Ａ１、Ａ２和兩個零售部Ｂ１、Ｂ２，工廠的生產能力與零售部的需求量如圖中各點線上數字所示（單位：噸）。兩點間箭線上的數字為單位運價（萬元／噸）。公司還有一個倉儲地Ｗ其倉儲能力為６００噸。產品既可以直接從工廠運到零售部，也可以先運到倉儲地再運到零售部，但受到倉儲能力限制。試確定使總的費用最少的生產計劃和方案，建立問題的數學模型并求解。題型解析：該題型的是中轉問題，兩個產地，兩個銷地，加上一個中轉點，故而除了假設從產地到銷地的運量外，還要假設從產地到中轉點，從中轉點到銷地的運量。此為產銷不平衡問題，要注意模型中約束的處理。交通大學２００６年考研試題［３－１０］：某工廠安排某種生活必需品在以后四個月的生產計劃。該產品可以在以后四個月的任一個月生產，不過受用工和原料價格的影響，不同的月份其生產成本不同，該產品在以后四個月的生產成本分別是１２、１０、１５、１８元／件。該產品以后四個月需要量分別是４００、７００、９００和８００件，考慮到生活必需品的要求，產品需要量必須加以滿足。該工廠平常每月最多能生產７００件，但在第二個月農閑時期工廠可以聘用臨時工加班，加班后可增產３００件，但生產成本每件增加３元。過剩產品每件存儲費用是每月３元。試完成：（１）仿照問題建立使總成本最小的生產計劃線性規劃數學模型。（１０分（２）用問題表上作業法求解。（１０分題型解析：該題型同樣的是生產計劃問題，該題要注意生產成本遞增（費用），下個月不能給上個月交貨的約束處理以及聘用臨時工加班的處理方式（增加額外的一個月）。考考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課：４００６８８５第４專題 目標規~、復習方法與【１】考試題該部分知識點所占分值較少！若是該部分知識點的話，以建模題最常見，計算題次之，有時也會出一些小題型。該部分計算題以圖解法和單純形法求解目標規劃為主，但圖解法更常見些；小題型則通常圍繞著目標規劃數學模型的幾個要素和目標函數的幾種取值形式出題。【２】復習方法與注意事牢記目標規劃數學模型的各特點，如偏差變量、硬約束、軟約束、目標函數的三種取值方式且僅為極小化問題；圖解法求解目標規劃問題時，掌握各目標約束的繪制方法，重點是正確判斷正負偏差變量增大的方向，并能依次按優先級判斷得到最后的最優解或滿意解；目標規劃的單純形法其實與線性規劃的單純形法沒有什么不同，區別在于目標規劃單純形表中把檢驗數的表達形式換了換，但仍是按“當所有檢驗數都大于等于０”時得到最優解（極小化）的判別定理。目標規劃的靈敏度分析頻率較低，需記住無論優先級如何變化，只在最終單純形表中進行分析。【３】與答題方圖解法先畫絕對約束（硬約束）確定可行域，再畫出各目標約束（軟約束）后按優先級確定最終（按步驟給分）目標規劃的單純形表中“０”元素可以不標出，節省制表時間；注意優先因子“Ｐ１＞＞Ｐ２”的含義；建模順序：確定硬約束（不一定有） 寫出目標約束（通常幾個優先級別就幾個軟約束） 最后判斷目標，確定目標函數中偏差變量的取值。二、重難點內容精講重點１）目標規劃的數學模型《《運籌學》名解析及典型題精講精２）圖解法３）單純形法難點：實際應用題建模重點 目標規劃的數學模目標規劃中的約絕對約束：必須滿足的等式約束和不等式約束，對應于線性規劃中的約束條件，稱之為硬約束。目標約束：當確定了目標值，進行決策時，允許存在正或負的偏差，因此在這些約束中加入正、負偏差變量，稱之為軟約束。優先因子：也稱為優先等級，目標規劃中用Ｐｋ表示，且Ｐｋ＞＞Ｐｋｋ＝１，２，…，Ｋ權系數：用于區分具有相同優先因子的兩個目標的差別。目標規劃的目標函數：ｍｉｎｚ＝ｆｄ＋，ｄ－要求恰好達到目標值：ｍｉｎｚ＝ｆｄ＋＋ｄ－要求不超過目標值：ｍｉｎｚ＝ｆｄ＋要求超過目標值：ｍｉｎｚ＝ｆｄ－目標規劃的一般數學模 目標函數：ｍｉｎｚ

∑Ｐ

ω－ｄ－＋ω＋ｄ＋ｌ ｋｎ

ｌｋ ｌｋ＋ｄ－–ｄ＋＝ｇ，ｋ＝１，…，目標約束：ｓ．ｔ．∑ ｊｎ絕對約束：∑ｊ≤＝，ｊ非負約束：ｘｊ≥０，ｊ＝１，…，ｄ－，ｄ＋≥０，ｋ＝１，…， 理工大學２００８年考研試題

ｂｉ，ｉ＝１，…，［４－１］：目標規劃的目標函數為ｍｉｎｚ＝Ｐｄ＋＋Ｐｄ－＋２ｄ＋其含義是 １ Ａ．第一目標要求不超過目標值、第二目標是求ｄ－與ｄ＋和最小 Ｂ．第一目標要求不超過目標值、第二目標是先求ｄ＋最小再求ｄ－最小，等價于ｍｉｎｚ＝Ｐｄ＋ １考考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課：４００６８８５Ｐｄ＋＋Ｐｄ－２ ３Ｃ．第一目標要求不超過目標值、第二目標要求不低于目標值，第三目標要求不超過目標值；Ｄ．第一目標要求不低于目標值、第二目標要求不超過目標值，第三目標要求不低于目標值題型解析：該題型的是目標規劃數學模型中的兩個要素 優先因子與權系數，側重于權系數的含義。理工大學２００８年考研試題［４２］判斷題：目標規劃的正偏差變量大于等于０，負偏差變量小于等于０。理工大學２００７年考研試題［４］判斷題：目標規劃中，一個約束的兩個正、負偏差變量至少一個等于０ｄ＋×ｄ－＝０理工大學２００８年考研試題［４］：目標規劃中要求不低于第一目標值、不超過第二目標值、恰好完成第三目標值，其目標數是 ）Ａ．ｍｉｎｚ＝Ｐｄ＋＋Ｐｄ＋＋Ｐｄ－＋ｄ＋ Ｂ．ｍｉｎｚ＝Ｐｄ－＋Ｐｄ＋＋Ｐｄ－＋ｄ＋１ ２ １ ２ Ｃ．ｍｉｎｚ＝Ｐｄ＋＋Ｐｄ－＋Ｐｄ－＋ｄ＋ Ｄ．ｍｉｎｚ＝Ｐｄ－＋Ｐｄ－＋Ｐｄ－＋ｄ＋１ ２ １ ２ 題型解析：該題型的是目標規劃數學模型中的目標函數的三種取值方式：不超過：ｆ＝ｍｉｄ＋）不低于：ｆ＝ｉｎ（ｄ－恰好達到：ｆ＝ｍｎｄ＋＋ｄ－重 表上作業大連理工大學２００４年考研試［４］：目標規劃模型與一般的線性規劃模型相比有哪些優點題型解析：該題型的是目標規劃與線性規劃的異同，重點要回答到“滿意解”和“多目標”兩個。重點２ 圖解法步驟１．在第一象限畫出絕對約束和目標約束，絕對約束確定可行域，目標約束上用箭頭標出正負偏差變量增大的方向；２．在可行域內，求滿足最高優先等級目標的解３．轉到下一個優先等級的目標，在滿足上一優先等級目標的前提下，求出滿足該等級目標的解；４．重復（３），直到所有優先等級目標都完畢；５．確定最優解或滿意解《《運籌學》名解析及典型題精講精哈爾濱工業大學２００５年考研試［４６］：目標規劃模型圖如圖所示ｍｉｎｚ＝ｐｄ－＋ｐｄ＋＋ｐｄ－１ ２ ３２ｘ１＋３ｘ２≤ ｘ１－ｘ２＋２２

—ｄ１＝２ｓ．ｔ．ｘ１＋２

–ｄ＋＝３３

＋

３–ｄ＋＝３ｘ，ｘ≥０，ｄ－，ｄ＋≥０，（ｉ＝１，２， 則其滿意解應為 Ａ．點 Ｂ．Ｂ點 Ｃ．Ｃ點 Ｄ．都不對哈爾濱工業大學２００５年考研試題［４］：用圖解法求以下目標規劃的滿意解ｍｉｎｚ＝ｐｄ＋＋ｐｄ－＋ｐ（ｄ＋＋ｄ－１ ２

＋２ｘ２＋ｄ– ＝ ｓ．ｔ．

＋ｘ２＋ｄ－–ｄ＋＝ ＋ｄ－–ｄ＋ ｘ，ｘ，ｄ－，ｄ＋≥０（ｉ＝１，…， 重點 單純形解目標規劃問題的單純形法的特 以所有檢驗數ｃｊ－ｚｊ０ｊ＝１，２，…，ｎ為最優準則；非基變量的檢驗數中含有不同等級的優先因子， ｊ＝１，２，…，ｃｊ－ｚｊ＝∑Ｐｋｋ＝１，２，…，σ１＝Ｐ１－σ２＝－Ｐ１＋理工大學２００７年考研試題考考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課：４００６８８５［４］：已知目標規劃的數學模型為：ｍｉｎｚ＝ｐ（ｄ－＋ｄ＋）＋ｐｄ－＋ｐｄ－ ２ ３ｘ＋ｘ＋ｄ－–

＝ ２２ｘ１＋２２

＋

–ｄ＋＝３ｓ．ｔ．ｘ１＋３

３–３

＝４４

＋

４–４

＝ｘ，ｘ，ｄ－，ｄ＋≥０（ｉ＝１，…， （１）求該目標規劃的滿意解（注：求解方法不限，要求寫出必要的求解過程（２）將目標函數改為ｍｉｎｚ＝Ｐ（ｄ－＋ｄ＋）＋Ｐ（ｄ－＋ｄ＋ 題型解析：該題型用圖解法和單純形法都可以求解，可以看自己對兩種方法的熟練程度來選擇求解方法。圖解法的靈敏度分析上未講解，其實也沒什么難度，只要更改最后一步目標函數優先因子的判別即可。難點實際應用題建建立目標規劃模型的步１．根據問題所各目標與條件，確定目標值，列出目標約束與絕對約束；２．根據決策者的需要將某些或全部絕對約束轉換為目標約束；３．給各級目標賦予相應的優先因子４．對同一優先級的各目標，再按其重要程度不同，賦予相應的權系數；５．據決策者的要求，目標函數按三種情況取值。大連理工大學２００５年考研試［９］Ⅰ和Ⅱ這經過工序工序道工序加工序的加工工作生產效率不一樣。序也有可完成相應的加工工作。因此每一種產品每道工序只用一種設備加工即可。單位產品在各設備需要的加工臺時，設備的計劃期有效臺時和單位產品利潤如下表所示。該企業計劃期的經營目標如下：Ｐ１：力爭使利潤超過５００元。Ｐ２：產品Ⅰ和產品Ⅱ的產量盡量保持平衡《《運籌學》名解析及典型題精講精Ｐ３：設備Ａ１的臺時要充分利用，Ａ２的臺時既要充分利用，又要盡量少加班，且Ａ２的重要性是Ａ１的３倍。問如何安排生產計劃使得達到上述目標的差距最小？建立該問題的數學模型，不要求求解題型解析：該題型的是目標規劃數學模型的建立，該題難點在于如何設置決策變量，使能清楚地分清產品１和２分別用Ａ１＼Ｂ１＼Ａ２＼Ｂ２設備來完成的Ａ和Ｂ的工時。通常這里常假設雙下標變量，因又涉及兩種產品，故還要設兩種不同的變量。提提考考試點（ｗｗｗ．ｋａｏｓｈｉｄｉａｎ．ｃｏｍ）名師精品課：４００６８８５第５專題 整數規~、復習方法與【１】考試題該部分知識點幾乎是各校必考知識點，其中分支定界法與割平面法計算量較大，通常小題型，如簡答題、填空題等，但偶爾也考簡單的計算。而０－１整數規劃中以指派問題的最常見！【２】復習方法與注意事分支定界法中，必須掌握如何分支，任選一非整數解的基變量，去除非整數解的區域；如何定界，必須保證下界一直為整數解。要注意松弛問題分支成兩個子問題后，原有目標函數值不再參與定界。割平面法中最關鍵是如何取得割平面方程，任選一個為分數值的基變量，寫出對應方程，將其變換成只含整數與非負真分數，將分數項移項即得隱枚舉法中過濾條件的設置，先要注意的是目標函數的極大化或極小化，確定了過濾條件的不等式符號；求解指派問題的匈牙利法看似復雜，其實求解步驟固定容易掌握，要注意特殊指派問題的處理，如任務數與人數不匹配時如何處理等。【３】與答題方分支定界法計算量大，大題的幾率較小，重點掌握分支定界原理；若計算題，其實除了分支定界外，求解過程與專題１單純形法求解線性規劃問題沒什么區別；割平面法的求解過程也仍然是單純形法求解線性規劃問題，只是每次在最終單純形表中要分析分數值基變量對應的方程，求得割平面后，繼續在單純形表中進行計算；隱枚舉法其實就是窮舉法的改進，在此專題中應為最簡單的方法，若的話，應拿下全部分數！指派問題最常見的方式是計算題，如何寫出效率矩陣，對效率矩陣進行變換，如何用匈牙法找出獨立０元素，只需按照步驟依次求解，難度并不大該部分知識點較難的是建模題，從實際