第1-4章 線性規(guī)劃及對(duì)偶理論2

1、第第1頁頁夫夫 運(yùn)運(yùn) 籌籌 帷帷 幄幄 之之 中中決決 勝勝 于于 千千 里里 之之 外外運(yùn)運(yùn) 籌籌 學(xué)學(xué) 課課 件件線線 性性 規(guī)規(guī) 劃劃Linear ProgrammingLinear Programming第第2頁頁本章內(nèi)容本章內(nèi)容o線性規(guī)劃問題的數(shù)學(xué)建模線性規(guī)劃問題的數(shù)學(xué)建模o圖解法圖解法o單純形法原理單純形法原理o單純形法的計(jì)算步驟單純形法的計(jì)算步驟oWinQSB軟件求解軟件求解第第3頁頁教學(xué)說明教學(xué)說明o教學(xué)目標(biāo)教學(xué)目標(biāo)：掌握：掌握LP的建模方法，熟練地使用的建模方法，熟練地使用單純形法求解模型，借助單純形法求解模型，借助WinQSB軟件求解軟件求解問題問題o重點(diǎn)與難點(diǎn)重點(diǎn)與難點(diǎn)：

2、重點(diǎn)是：重點(diǎn)是LP的建模與解法；難點(diǎn)的建模與解法；難點(diǎn)是單純形法的原理是單純形法的原理o教學(xué)方法教學(xué)方法：配合課件和：配合課件和WinQSB軟件，課堂件，課堂講授為主，案例研討為輔講授為主，案例研討為輔o思考題、討論題、作業(yè)思考題、討論題、作業(yè)：教材第：教材第1-3章習(xí)題章習(xí)題 o學(xué)時(shí)分配學(xué)時(shí)分配：8學(xué)時(shí)學(xué)時(shí) 第第4頁頁線性規(guī)劃的產(chǎn)生與發(fā)展線性規(guī)劃的產(chǎn)生與發(fā)展o1939年蘇聯(lián)的經(jīng)濟(jì)學(xué)家康托洛維奇在年蘇聯(lián)的經(jīng)濟(jì)學(xué)家康托洛維奇在生生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法一書中，首次一書中，首次用線性規(guī)劃方法解決了生產(chǎn)組織與運(yùn)輸問題。用線性規(guī)劃方法解決了生產(chǎn)組織與運(yùn)輸問題。o1947年美國

3、數(shù)學(xué)家年美國數(shù)學(xué)家G.B.Dantzig提出了提出了線性規(guī)劃的數(shù)學(xué)模型，并給出了求解該模型線性規(guī)劃的數(shù)學(xué)模型，并給出了求解該模型的單純形法（的單純形法（Simplex method)。這標(biāo)。這標(biāo)志著線性規(guī)劃這一運(yùn)籌學(xué)的重要分支的誕生。志著線性規(guī)劃這一運(yùn)籌學(xué)的重要分支的誕生。o計(jì)算機(jī)的發(fā)展促進(jìn)了計(jì)算機(jī)的發(fā)展促進(jìn)了LP計(jì)算理論的發(fā)展，計(jì)算理論的發(fā)展，使其應(yīng)用更加廣泛和深入。使其應(yīng)用更加廣泛和深入。第第5頁頁線性規(guī)劃的應(yīng)用范圍線性規(guī)劃的應(yīng)用范圍o生產(chǎn)中的組織與計(jì)劃問題生產(chǎn)中的組織與計(jì)劃問題o運(yùn)輸問題運(yùn)輸問題o合理下料問題合理下料問題o配料問題配料問題o生產(chǎn)布局問題生產(chǎn)布局問題特點(diǎn)：在現(xiàn)有條件下，統(tǒng)籌

4、安排，使總的經(jīng)特點(diǎn)：在現(xiàn)有條件下，統(tǒng)籌安排，使總的經(jīng)濟(jì)效益最好，或者是總成本最省。濟(jì)效益最好，或者是總成本最省。某工廠制造某工廠制造A、B兩種產(chǎn)品，它們的原材料單位消耗、兩種產(chǎn)品，它們的原材料單位消耗、單位利潤以及資源現(xiàn)有量如下表：單位利潤以及資源現(xiàn)有量如下表：問如何組織生產(chǎn)，使工廠獲得最大利潤？問如何組織生產(chǎn)，使工廠獲得最大利潤？例1：生產(chǎn)組織與計(jì)劃問題生產(chǎn)組織與計(jì)劃問題AB資源現(xiàn)有量資源現(xiàn)有量（噸）（噸）鋼材鋼材23600煤煤21400單位利潤單位利潤（萬元）（萬元）205產(chǎn)品產(chǎn)品資源資源資源資源 消耗消耗11 線性規(guī)劃的數(shù)學(xué)建模第第7頁頁建立數(shù)學(xué)模型步驟1.假設(shè)決策變量：設(shè)假設(shè)決策變量：

5、設(shè)A、B兩種產(chǎn)品各生產(chǎn)兩種產(chǎn)品各生產(chǎn)個(gè)單位；個(gè)單位；21,xx2.建立目標(biāo)函數(shù)：利潤函數(shù)是建立目標(biāo)函數(shù)：利潤函數(shù)是 ，求它的最大值，即求它的最大值，即21520 xxS21520maxxxS3.現(xiàn)有資源的限制條件：現(xiàn)有資源的限制條件：4002600322121xxxx4.決策變量必須有非負(fù)限制：決策變量必須有非負(fù)限制：0, 021xx第第8頁頁數(shù)學(xué)模型12121212max20523600. .24000,0Sxxxxstxxxx目標(biāo)函數(shù)系統(tǒng)約束非負(fù)限制 注意：目標(biāo)函數(shù)和約束條件中變量的次數(shù)都是一注意：目標(biāo)函數(shù)和約束條件中變量的次數(shù)都是一次的，這樣的模型稱為線性規(guī)劃數(shù)學(xué)模型。次的，這樣的模型稱

6、為線性規(guī)劃數(shù)學(xué)模型。第第9頁頁生產(chǎn)計(jì)劃安排問題的一般描述nmmnmmmnnnbbbacccAacccAacccABBB21212222212111211121資源資源產(chǎn)品產(chǎn)品消耗消耗資源現(xiàn)有量資源現(xiàn)有量單位產(chǎn)品利潤單位產(chǎn)品利潤求解使工廠獲得最大利潤的生產(chǎn)方案。求解使工廠獲得最大利潤的生產(chǎn)方案。第第10頁頁生產(chǎn)計(jì)劃安排問題的一般數(shù)學(xué)模型解：設(shè)解：設(shè) 表示生產(chǎn)產(chǎn)品表示生產(chǎn)產(chǎn)品的單位數(shù)，則有如下的數(shù)學(xué)模型：的單位數(shù)，則有如下的數(shù)學(xué)模型：(1,2, )jxjn(1,2, )jBjn11max 1,2,s.t.0 1,2,njjjnijjijjSb xc xaimxjn第第11頁頁設(shè)有某種物資從設(shè)有某種

7、物資從A、B、C三個(gè)產(chǎn)地調(diào)出，運(yùn)往甲、三個(gè)產(chǎn)地調(diào)出，運(yùn)往甲、乙、丙三個(gè)需求地，其調(diào)運(yùn)量及運(yùn)價(jià)如下表。求運(yùn)乙、丙三個(gè)需求地，其調(diào)運(yùn)量及運(yùn)價(jià)如下表。求運(yùn)費(fèi)最省的調(diào)運(yùn)方案。費(fèi)最省的調(diào)運(yùn)方案。 甲甲 乙乙 丙丙 調(diào)出量調(diào)出量 A 2 4 5 7 B 1 3 4 4 C 3 2 3 9 調(diào)入量調(diào)入量 6 8 6 （20）調(diào)出調(diào)出調(diào)入調(diào)入運(yùn)價(jià)運(yùn)價(jià)例2：運(yùn)輸問題第第12頁頁設(shè)設(shè) 表示從表示從i 地調(diào)往地調(diào)往j 地的調(diào)運(yùn)量地的調(diào)運(yùn)量ijx111213212223313233111213212223313233112131122232132333min245343237496860 1,2,3; 1,2,3ij

8、Sxxxxxxxxxxxxxxxxxxxxxxxxxxxxij第第13頁頁產(chǎn)銷平衡運(yùn)輸問題的一般描述產(chǎn)量產(chǎn)量銷量銷量產(chǎn)地產(chǎn)地銷地銷地運(yùn)價(jià)運(yùn)價(jià)nBBB21mAAA21mnmmnnccccccccc212222111211nbbb21maaa21njjmiiba11求解使運(yùn)輸總成本最低的方案。求解使運(yùn)輸總成本最低的方案。第第14頁頁設(shè)設(shè) 表示從表示從i 地調(diào)往地調(diào)往j 地的調(diào)運(yùn)量地的調(diào)運(yùn)量njmixnjbxmiaxxcSijmijijnjiijijminjij, 2 , 1, 2 , 10, 2 , 1, 2 , 1min1111ijx產(chǎn)銷平衡運(yùn)輸問題的一般模型例例3：合理配載問題：合理配載問題o

9、某貨船的前艙、中艙、后艙的載重分別為某貨船的前艙、中艙、后艙的載重分別為2 000噸、噸、3 000噸、噸、1 000噸，容積分別為噸，容積分別為100 000立方米、立方米、135 000立方米、立方米、30 000立方米；立方米；顧客托運(yùn)的貨物顧客托運(yùn)的貨物A、B、C的重量、體積、運(yùn)費(fèi)等的重量、體積、運(yùn)費(fèi)等資料已知。為了保持貨船的穩(wěn)定，要求三個(gè)貨艙資料已知。為了保持貨船的穩(wěn)定，要求三個(gè)貨艙載貨率必須平衡。問如何裝載，使收入最大？載貨率必須平衡。問如何裝載，使收入最大？111213212223313233+)+800(+x )+500(+ijxijZxxxxxxxxxxxxxxxxxxxxx

10、x1121311222321323331121311222解：設(shè) 為第 種貨物裝入 倉的噸數(shù)max =600()載重約束：+2000 +3000 +1000容積約束：60+50+25100 000 60+50+111213212223313233+x+2000300010000 =1,2,3i jxxxxxxxxxxxxxxxxxxxxxxi3213233311213112223213233325135 000 60+50+2530 000貨物約束：6000 4000 2000+貨船穩(wěn)定約束：非負(fù)約束：; =1,2,3j例例4：連續(xù)投資問題：連續(xù)投資問題o某地區(qū)今后三年內(nèi)可以有某地區(qū)今后三年內(nèi)

11、可以有A、B、C、D四個(gè)項(xiàng)目的四個(gè)項(xiàng)目的投資選擇，總資金量為投資選擇，總資金量為3000萬元。其中項(xiàng)目萬元。其中項(xiàng)目A在在三年內(nèi)每年年初投資，當(dāng)年年底可回收本利和為三年內(nèi)每年年初投資，當(dāng)年年底可回收本利和為120；項(xiàng)目；項(xiàng)目B第一年年初投資，第二年年底可回第一年年初投資，第二年年底可回收本利和為收本利和為150，但投資額不超過，但投資額不超過2000萬元；萬元；項(xiàng)目項(xiàng)目C第二年年初投資，第三年年底可回收本利和第二年年初投資，第三年年底可回收本利和為為160，但投資額不超過，但投資額不超過1500萬元；項(xiàng)目萬元；項(xiàng)目D第第三年年初投資，當(dāng)年年底可收回本利和為三年年初投資，當(dāng)年年底可收回本利和為1

12、40，投資額不超過投資額不超過1000萬元。問如何安排投資，使第萬元。問如何安排投資，使第三年年底本利和的金額最大？三年年底本利和的金額最大？13324311211232111343122121max 1.21.61.43000 1.2 1.21.52000 i jxjiZxxxxxxxxxxxxxx解：設(shè)為第 年初對(duì) 項(xiàng)目的投資額年初投資約束：項(xiàng)目投資約束：32431500 10000 =1,2,3,4; =1,2,3i jxxij非負(fù)約束：第第19頁頁思考題1：配料問題 某化工廠要用三種原料混合配置三種不同規(guī)格的產(chǎn)品，各產(chǎn)品的規(guī)格、單價(jià)見下表：產(chǎn)品規(guī)格單價(jià)（元/公斤）A原料不少于50%原料

13、不超過25%50B原料不少于25%原料不超過50%35C不限25第第20頁頁問如何安排生產(chǎn)使得生產(chǎn)利潤最大？原料日最大供應(yīng)量單價(jià)(元/公斤)10065100256035原料的單價(jià)與每天最大供應(yīng)量見下表：原料的單價(jià)與每天最大供應(yīng)量見下表：3 , 2 , 1, 3 , 2 , 1, 060100100003030. .10401030152515max) 3 , 2 , 1,(33231332221231211123222123222113121113121133312221131211jixxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxZjixjiijij種原料的數(shù)量為種產(chǎn)品的第設(shè)

14、用于生產(chǎn)第第第22頁頁思考題2：人力資源分配問題 某個(gè)中型百貨商場對(duì)售貨人員（周工資400元）的需求經(jīng)統(tǒng)計(jì)如下表 為了保證銷售人員充分休息，銷售人員每周連續(xù)工作5天，休息2天。問應(yīng)如何安排銷售人員的工作時(shí)間，使得人力總成本最小？星期一二三四五六日人數(shù)12151214161819第第24頁頁思考題3：合理下料問題o要制作要制作100套鋼筋架子，每套有長套鋼筋架子，每套有長2.9m、2.1m和和1.5m的鋼筋各一根。已知原材料的鋼筋各一根。已知原材料長長7.4m，應(yīng)如何切割，使用原材料最節(jié)省，應(yīng)如何切割，使用原材料最節(jié)省，試建立線性規(guī)劃模型并求解。試建立線性規(guī)劃模型并求解。課堂練習(xí)：課堂練習(xí)：o三

15、種產(chǎn)品要分別經(jīng)過三種產(chǎn)品要分別經(jīng)過A,B兩道工序。兩道工序。 產(chǎn)品產(chǎn)品可在可在A,B的任何設(shè)備上加工；產(chǎn)品的任何設(shè)備上加工；產(chǎn)品可在可在A的任何設(shè)的任何設(shè)備上加工后，只能在備上加工后，只能在B1設(shè)備上加工；產(chǎn)品設(shè)備上加工；產(chǎn)品只能只能在在A2和和B2設(shè)備上加工。設(shè)備上加工。 試安排最優(yōu)生產(chǎn)計(jì)劃，使該廠獲利最大。試安排最優(yōu)生產(chǎn)計(jì)劃，使該廠獲利最大。第第26頁頁12 線性規(guī)劃問題解的性質(zhì) 兩個(gè)變量的線性規(guī)劃問題的圖解法兩個(gè)變量的線性規(guī)劃問題的圖解法幾個(gè)基本概念：幾個(gè)基本概念： 滿足所有約束條件的解稱為滿足所有約束條件的解稱為LP問題的可行解；所問題的可行解；所有可行解的集合稱為可行解集。有可行解的

16、集合稱為可行解集。 使目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解稱為使目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解稱為LP問題的最優(yōu)問題的最優(yōu)解。解。 問題：線性規(guī)劃是一個(gè)帶有約束條件的極值問問題：線性規(guī)劃是一個(gè)帶有約束條件的極值問題，能否用微積分方法求解題，能否用微積分方法求解?第第27頁頁例例1 1：用圖解法求解下面的：用圖解法求解下面的LPLP問題問題0, 08234.52max21212121xxxxxxtsxxS目標(biāo)函數(shù)等值線1x2x此點(diǎn)為LP的最優(yōu)解o41x4332x8221 xx65221 xx155221 xxD可行域max Smin S第第28頁頁得到這個(gè)最優(yōu)解：得到這個(gè)最優(yōu)解：2112232283LPmax19

17、xxxxxS的目標(biāo)函數(shù)最優(yōu)值為 本問題有唯一最優(yōu)解。本問題有唯一最優(yōu)解。第第29頁頁例例2 2 ：用圖解法解下面的線性規(guī)劃：用圖解法解下面的線性規(guī)劃0, 08234.2max21212121xxxxxxtsxxS AB目標(biāo)函數(shù)等值線1x2xO8221 xx431224xxD可行域max Smin S第第30頁頁得到得到LP的最優(yōu)解及目標(biāo)函數(shù)最優(yōu)值：的最優(yōu)解及目標(biāo)函數(shù)最優(yōu)值：1212212112282:33284:42LPmax8xxxAxxxxxBxxS的最優(yōu)值均為 除除A、B兩個(gè)最優(yōu)解外，兩個(gè)最優(yōu)解外，AB線段上的所有點(diǎn)都是線段上的所有點(diǎn)都是LP的最優(yōu)解。本問題有無窮多最優(yōu)解。的最優(yōu)解。本問

18、題有無窮多最優(yōu)解。第第31頁頁例例3 3：用圖解法解下面的線性規(guī)劃：用圖解法解下面的線性規(guī)劃0, 0331.2min21212121xxxxxxtsxxS1x2xo無界的可行解集1S3S 此題有可行解，此題有可行解，但無最優(yōu)解但無最優(yōu)解112SD可行域max Smin S第第32頁頁例例4 4：用圖解法解下面的線性規(guī)劃：用圖解法解下面的線性規(guī)劃0, 011.3max21212121xxxxxxtsxxS無可行解1x2xo 本題無可行解，更本題無可行解，更無最優(yōu)解無最優(yōu)解第第33頁頁o有唯一最優(yōu)解，這個(gè)最優(yōu)解一定在可行解集有唯一最優(yōu)解，這個(gè)最優(yōu)解一定在可行解集合的某一頂點(diǎn)上達(dá)到合的某一頂點(diǎn)上達(dá)到

19、o有無窮多最優(yōu)解，最優(yōu)解充滿一個(gè)線段，可有無窮多最優(yōu)解，最優(yōu)解充滿一個(gè)線段，可以用它的兩個(gè)端點(diǎn)作為代表以用它的兩個(gè)端點(diǎn)作為代表o有可行解，但無最優(yōu)解（無界解）有可行解，但無最優(yōu)解（無界解）o無可行解無可行解 小結(jié)：小結(jié)：LP圖解法有如下四種情況圖解法有如下四種情況第第34頁頁線性規(guī)劃問題解的關(guān)系線性規(guī)劃問題解的關(guān)系線性規(guī)劃線性規(guī)劃問題的解問題的解無可行解無可行解 有可行解有可行解唯一最優(yōu)解唯一最優(yōu)解無最優(yōu)解無最優(yōu)解有最優(yōu)解有最優(yōu)解無窮多最優(yōu)解無窮多最優(yōu)解第第35頁頁 線性規(guī)劃問題的標(biāo)準(zhǔn)形式1 12211 11221121 1222221 12212LP:min(max)( , )( , )s.

20、t.( , )0,0,0nnnnnnmmmnnmnSc xc xc xa xa xa xba xa xa xba xaxaxbxxx 問題的一般形式為第第36頁頁將一般的將一般的LPLP轉(zhuǎn)化為轉(zhuǎn)化為LPLP標(biāo)準(zhǔn)形：標(biāo)準(zhǔn)形：1 12211 11221121 1222221 12212max.0,0,0nnnnnnmmmnnmnSc xc xc xa xa xa xba xa xa xbsta xaxaxbxxx第第37頁頁規(guī)定: 求目標(biāo)函數(shù)的最大值為標(biāo)準(zhǔn)形，即目標(biāo)函數(shù)為求目標(biāo)函數(shù)的最大值為標(biāo)準(zhǔn)形，即目標(biāo)函數(shù)為maxS 。如果問題是求。如果問題是求 minS 時(shí)，可令時(shí)，可令求求 ，相當(dāng)于求，相當(dāng)

21、于求minS 。SSmaxS第第38頁頁規(guī)定:1 12211 122110kkknnknkkknnnkna xa xa xbxa xa xaxxbx若，則增加一個(gè)變量，使其變?yōu)榈仁剑Q為松弛變量，它在目標(biāo)函數(shù)中的系數(shù)為零。 以等式約束為標(biāo)準(zhǔn)形。設(shè)第以等式約束為標(biāo)準(zhǔn)形。設(shè)第k 個(gè)等式為個(gè)等式為 1 12211 122110rrrnnrnrrrnnnrna xa xa xbxa xa xa xxbx若，則可減去一個(gè)松弛變量，使其變?yōu)榈仁?，即，同樣，在目?biāo)函數(shù)中的系數(shù)也是零。第第39頁頁(3) LP中所有的變量都有非負(fù)限制。如果實(shí)際問題中的LP里某個(gè)變量無非負(fù)限制，可如下處理:(4) 若約束條件為等

22、式，但右端項(xiàng)為負(fù)值，則在等式兩邊同時(shí)乘以-1即可 0,0,jjijiijjjixxxxxxxxxx若 無非負(fù)限制，則引入令代入約束條件中，這時(shí)所有的變量都有了若 為非正限制，則引入0，令 =-,代入約束條件中，這時(shí)所有的變量都有了非非負(fù)限制。負(fù)限制。規(guī)定:第第40頁頁將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形12312312312312min 35262316s.t.510,0Sxxxxxxxxxxxxx x123412345123461234max 352623316s.t.55100 =1,2,6iSxxxxxxxxxxxxxxxxxxxi 第第41頁頁根據(jù)以上的規(guī)定，根據(jù)以

23、上的規(guī)定，LPLP的標(biāo)準(zhǔn)形為：的標(biāo)準(zhǔn)形為：1 12211 11221121 1222221 12212max.0,0,0nnnnnnmmmnnmnSc xc xc xa xa xa xba xa xa xbsta xaxaxbxxx第第42頁頁兩種縮寫形式：兩種縮寫形式：max,1,2,.0,1,2,njjjnijjijjSc xa xb imstxjn第第43頁頁矩陣表示法：矩陣表示法：mnmmnnaaaaaaaaaA212222111211ncccC21設(shè)mbbbb21nxxxx21LPmaxs.t.0SCxAxbx則問題可表為3. LP3. LP問題解的性質(zhì)問題解的性質(zhì) 幾個(gè)概念幾個(gè)概念

24、 凸集：若連接凸集：若連接n維點(diǎn)集維點(diǎn)集S 中任意兩點(diǎn)中任意兩點(diǎn) 的線段的線段仍在仍在S 內(nèi)，則稱內(nèi)，則稱S 為凸集。即為凸集。即)2()1(,xx., 10 ,)1 (|)2()1 ()2()1 (SSxxxxxx凸集凸集不是凸集極點(diǎn) 極點(diǎn)：若凸集極點(diǎn)：若凸集S 中的點(diǎn)中的點(diǎn)x，不能成為，不能成為S 中任何線段中任何線段的內(nèi)點(diǎn)，則稱的內(nèi)點(diǎn)，則稱x為為S 的極點(diǎn)。的極點(diǎn)。 設(shè)設(shè) 為為LP的一個(gè)可行解，若的一個(gè)可行解，若或或 的非零分量對(duì)應(yīng)的的非零分量對(duì)應(yīng)的A中列向量線性無關(guān)，則稱中列向量線性無關(guān)，則稱它為它為基礎(chǔ)可行解基礎(chǔ)可行解。由這些列向量組成的矩陣稱為。由這些列向量組成的矩陣稱為基矩基矩陣

25、陣，與這些列向量對(duì)應(yīng)的變量稱為，與這些列向量對(duì)應(yīng)的變量稱為基變量基變量，其余的變，其余的變量稱為量稱為非基變量非基變量。)0()0(2)0(1)0(nxxxx0)0(x)0(x使目標(biāo)函數(shù)值達(dá)到最優(yōu)值的可行解稱為使目標(biāo)函數(shù)值達(dá)到最優(yōu)值的可行解稱為最優(yōu)解最優(yōu)解；使目標(biāo)函數(shù)達(dá)到最優(yōu)值的使目標(biāo)函數(shù)達(dá)到最優(yōu)值的基礎(chǔ)可行解基礎(chǔ)可行解稱為稱為基礎(chǔ)最基礎(chǔ)最優(yōu)解優(yōu)解?？尚薪饧A(chǔ)可行解最優(yōu)解基礎(chǔ)最優(yōu)解線性規(guī)劃解的關(guān)系線性規(guī)劃解的關(guān)系第第47頁頁目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件行列式行列式0基矩陣基矩陣右邊常數(shù)右邊常數(shù)=10987654321xxxxxxxxxx247xxx 為基變量其余變量為非基變量第第48頁頁

26、 幾個(gè)重要定理（單純形法的理論依據(jù)）幾個(gè)重要定理（單純形法的理論依據(jù)）定理定理1 線性規(guī)劃問題的可行解集為凸集線性規(guī)劃問題的可行解集為凸集，即連，即連接線性規(guī)劃問題任意兩個(gè)可行解的線段上的點(diǎn)接線性規(guī)劃問題任意兩個(gè)可行解的線段上的點(diǎn)仍為可行解。仍為可行解。定理定理2 可行解集可行解集S 中的點(diǎn)中的點(diǎn)x是極點(diǎn)的充要條件是極點(diǎn)的充要條件是是x為基礎(chǔ)可行解（簡單地說，凸多邊形的頂為基礎(chǔ)可行解（簡單地說，凸多邊形的頂點(diǎn)就是基礎(chǔ)可行解）。點(diǎn)就是基礎(chǔ)可行解）。定理定理3 線性規(guī)劃的目標(biāo)函數(shù)的最優(yōu)值，一定線性規(guī)劃的目標(biāo)函數(shù)的最優(yōu)值，一定可在極點(diǎn)上達(dá)到?？稍跇O點(diǎn)上達(dá)到。第第49頁頁1 13 3 單純形方法單純形

27、方法(Simplex method)(Simplex method)x1x2O單純形法的解題思路：單純形法的解題思路： 用消去法解用消去法解LPLP問題問題12121212max2543s.t.280,0Sxxxxxxxx解：引入松弛變量解：引入松弛變量將其化為標(biāo)準(zhǔn)形式將其化為標(biāo)準(zhǔn)形式12132412512345max254328,0Sxxxxxxxxxxxxxx345,x xx 123453134542512121 0 1 0 0 0 1 0 1 0 1 2 0 0 1 341 0 00 1 0 30 0 182 0 0Ap p p p pR AxxBp p pxxxxxxx第一步：求一個(gè)可

28、行解系數(shù)矩陣 顯然（非齊次方程有解條件）， 其中令 001200 4 25038xSxx 第第52頁頁012 25Sxx第二步：判優(yōu)目標(biāo)函數(shù)中非目標(biāo)系數(shù)存在正基變量的系數(shù)可數(shù) 目標(biāo)函數(shù)值未達(dá)到最優(yōu)以用來檢驗(yàn)線性規(guī)劃是否已得由此得出，到最優(yōu)解2312242225122 34301 38208822 minxxxxxxxxxxxxxx2第三步：換基迭代 的目標(biāo)系數(shù)的值較大應(yīng)引入 ，將其轉(zhuǎn)換為基變量，稱其為 原來的基變量中必有一個(gè)要換出，變?yōu)榉腔兞?，稱為3 4取值滿足兩個(gè)不等式的 的換入變值，換個(gè)寫法：變量量換出 43124514141112141443 8,3 , 1 24 382 322030

29、 4 2525 325002 xxxxxxxxxxxxSxxxxxxxS 由此確定換出變量為將基變量用非基變量表示為（ ）令得此時(shí)，（）=15+115 141311124115145354224154 25 4404 3202224 2 =min,2, 1 12223 320220 SxxxxxxxxxxxxxxxxxxxxxxxxS 第四步：判優(yōu)15+， 入基出基45212192192max193 xxSxSx判優(yōu)：目標(biāo)函數(shù)中非基變量的系數(shù)均小于零最優(yōu)解為，第第55頁頁2. 2. 單純形方法理論推導(dǎo)單純形方法理論推導(dǎo)max0SCxAxbx設(shè)設(shè)A是是 的矩陣，且的矩陣，且R(A)=m （m04

30、010換換出出行行將將3化為化為15/311801/301/31011/3303005/304/3乘乘以以3/5后后得得到到103/51/518011/52/540011Z=0Z=40Z=701218,max70.4xSx最優(yōu)解為第第70頁頁單純形法的計(jì)算步驟單純形法的計(jì)算步驟學(xué)習(xí)要點(diǎn)：學(xué)習(xí)要點(diǎn)：1. 線性規(guī)劃解的概念以及線性規(guī)劃解的概念以及3個(gè)基本定理個(gè)基本定理2. 熟練掌握單純形法的解題思路及求解步驟熟練掌握單純形法的解題思路及求解步驟第第71頁頁問題:表1中我們選取了 入基,如果選取 入基結(jié)果又如何呢?2x1x路徑1路徑2結(jié)論：結(jié)論：1.每一個(gè)單純每一個(gè)單純形表對(duì)應(yīng)一個(gè)極點(diǎn)，形表對(duì)應(yīng)一個(gè)

31、極點(diǎn)，表一對(duì)應(yīng)黃點(diǎn)；表二表一對(duì)應(yīng)黃點(diǎn)；表二對(duì)應(yīng)綠點(diǎn)；表三對(duì)應(yīng)對(duì)應(yīng)綠點(diǎn)；表三對(duì)應(yīng)藍(lán)點(diǎn)。藍(lán)點(diǎn)。 2.一般來說，一般來說，路徑不同，迭代次數(shù)路徑不同，迭代次數(shù)可能不同?？赡懿煌?。第第72頁頁(1)如果單純形表中的基變量取值皆為正數(shù)，稱這個(gè)如果單純形表中的基變量取值皆為正數(shù)，稱這個(gè)基可行解為基可行解為非退化解非退化解。若。若LP的所有基可行解都是非退的所有基可行解都是非退化的，則化的，則LP經(jīng)過有限次迭代可達(dá)到最優(yōu)經(jīng)過有限次迭代可達(dá)到最優(yōu).(2)如果單純形表中的基變量取值有的為零時(shí)，稱為如果單純形表中的基變量取值有的為零時(shí)，稱為LP的的退化解退化解，此時(shí)稱，此時(shí)稱LP是退化的，理論上認(rèn)為這種是退化的，

32、理論上認(rèn)為這種線性規(guī)劃在迭代過程中可能產(chǎn)生循環(huán)，從而得不到最線性規(guī)劃在迭代過程中可能產(chǎn)生循環(huán)，從而得不到最優(yōu)解。為避免循環(huán)，常采用優(yōu)解。為避免循環(huán)，常采用1976年年R.G.Bland提出提出Bland法則：法則：a.單純形表中有若干個(gè)檢驗(yàn)數(shù)單純形表中有若干個(gè)檢驗(yàn)數(shù) 時(shí)，時(shí)，取下標(biāo)號(hào)小的非基變量入基；取下標(biāo)號(hào)小的非基變量入基； b. 用用 法則選取出基法則選取出基變量時(shí)，若比值相同，則選取下標(biāo)號(hào)小的基變量出基。變量時(shí)，若比值相同，則選取下標(biāo)號(hào)小的基變量出基。0j說明：說明：第第73頁頁(3) 當(dāng)所有的檢驗(yàn)數(shù)全部小于等于零時(shí)，若有某當(dāng)所有的檢驗(yàn)數(shù)全部小于等于零時(shí)，若有某個(gè)非基變量的檢驗(yàn)數(shù)也是零，

33、則該線性規(guī)劃有個(gè)非基變量的檢驗(yàn)數(shù)也是零，則該線性規(guī)劃有無無窮多組解窮多組解，否則有唯一解。將這個(gè)檢驗(yàn)數(shù)為零的，否則有唯一解。將這個(gè)檢驗(yàn)數(shù)為零的變量入基，得到另一個(gè)基礎(chǔ)最優(yōu)解。（變量入基，得到另一個(gè)基礎(chǔ)最優(yōu)解。（P31）(4) 當(dāng)某非基變量的檢驗(yàn)數(shù)大于零時(shí)，但當(dāng)某非基變量的檢驗(yàn)數(shù)大于零時(shí)，但 中中對(duì)應(yīng)列系數(shù)已無正數(shù)，則表示無論引入該非基變對(duì)應(yīng)列系數(shù)已無正數(shù)，則表示無論引入該非基變量多少，基變量不會(huì)向違反非負(fù)約束的方向發(fā)展，量多少，基變量不會(huì)向違反非負(fù)約束的方向發(fā)展，從而使目標(biāo)函數(shù)可以無限制地增加，因此存在從而使目標(biāo)函數(shù)可以無限制地增加，因此存在無無界解界解（P32）說明：說明：AB1第第74頁頁

34、例例2：解線性規(guī)劃：解線性規(guī)劃0,303310220222min52154152153154321xxxxxxxxxxxxxxxxxS解：注意到解：注意到 對(duì)應(yīng)對(duì)應(yīng)A中的列向量恰好構(gòu)成三階中的列向量恰好構(gòu)成三階單位方陣，可以作為第一個(gè)可行基。單位方陣，可以作為第一個(gè)可行基。423,xxx單純形表單純形表C 2 -1 1 -2 1 1 -1 -220 1030 2 0 1 0 1 1 1 0 0 2 3 0 0 1 3S=-50 7 0 0 0 8 1 2-2 010 0 0 -2 1 0 -3 1 1 0 0 2 0 -3 0 1 -3S=20 0 -7 0 0 -6324xxx54321xx

35、xxxBxBc314xxx1B b1x入基20 10 30min,213 102x 出基最優(yōu)解為最優(yōu)解為 最優(yōu)值最優(yōu)值S=-2012345100000 xxxxx第第76頁頁3. 3. 第一個(gè)可行解的求法（大第一個(gè)可行解的求法（大M M法）法）以上各例的系數(shù)矩陣以上各例的系數(shù)矩陣A 中，都存在一個(gè)中，都存在一個(gè)m 階單位階單位陣，因此很容易用單純行法求解。但是大多數(shù)陣，因此很容易用單純行法求解。但是大多數(shù)LP問題并不是這樣。問題并不是這樣。例例 3 ：12312312313123min3211423210Sxxxxxxxxxxxxxx ， ，解：化為標(biāo)準(zhǔn)形解：化為標(biāo)準(zhǔn)形123456712341

36、23561371234567max30021142321,0SxxxxxMxMxxxxxxxxxxxxxxxxxxxx45676767,(0)0LPx xx xAAx xM MxxM這里的是松弛變量，而是人工變量，它的作用是為了產(chǎn)生 中一個(gè)單位列向量，從而使 中出現(xiàn)一個(gè)三階單位陣。需要注意的是：人工變量在目標(biāo)函數(shù)中的系數(shù)不是零，而是在它們的前邊冠以一個(gè)負(fù)的，對(duì)于求最大化問題，只有當(dāng)時(shí)，才存在最大值，這種處理方法是對(duì)增加人工變量的一種懲罰，稱是罰因子。第第78頁頁填寫單純形表：填寫單純形表：C3 -1 -1 0 0 -M -M0-M-M11 3 1 1 -2 1 1 0 0 0-4 1 2 0

37、-1 1 0-2 0 1 0 0 0 1S=-4M3-6M M-1 3M-1 0 -M 0 0467xxx1234567 xxxxxxxBxBc出基入基73, 111,23,111min,xx1B b第第79頁頁C3 -1 -1 0 0 -M -M0-M-110 1 1 3 -2 0 1 0 0 -10 1 0 0 -1 1 -2-2 0 1 0 0 0 1S=-M-11 M-1 0 0 -M 0 -3M+1463xxx1234567 xxxxxxxBxBc26,xx顯然， 入基出基1B b第第80頁頁C3 -1 -1 0 0 -M -M 0-1-112 1 1 3 0 0 1 -2 2 -5

38、0 1 0 0 -1 1 -2-2 0 1 0 0 0 1S=-21 0 0 0 -1 -M+1 -M-1423xxx1234567 xxxxxxxBxBc14xx顯然， 入基， 出基1B bC3 -1 -1 0 0 -M -M 3-1-1 4 1 9 1 0 0 1/3 -2/3 2/3 -5/30 1 0 0 -1 1 -20 0 1 2/3 -4/3 4/3 -7/3S= 20 0 0 -1/3 -1/3 -M+1/3 -M+2/3123xxx1234567 xxxxxxxBxBc1B b12341, min2.9xxSx 最優(yōu)解最優(yōu)值終止表終止表第第82頁頁說明：關(guān)于大說明：關(guān)于大M法

39、的幾種情況法的幾種情況（1） 上表稱為終止表。在終止表中，如果基變上表稱為終止表。在終止表中，如果基變量里不含有人工變量，或者量里不含有人工變量，或者基變量里含有人工變基變量里含有人工變量，但是人工變量取值為零，量，但是人工變量取值為零，則則LP一定有最優(yōu)解；一定有最優(yōu)解；（2） 在終止表中，如果基變量里含有人工變量，在終止表中，如果基變量里含有人工變量，且人工變量取值大于零，則且人工變量取值大于零，則LP無最優(yōu)解（無最優(yōu)解（P37）第第83頁頁1-4 WinQSB1-4 WinQSB軟件應(yīng)用軟件應(yīng)用第第84頁頁第第2章章 線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論o對(duì)偶問題的提出對(duì)偶問題的提出o原

40、問題與對(duì)偶問題原問題與對(duì)偶問題o對(duì)偶問題的基本性質(zhì)對(duì)偶問題的基本性質(zhì)o影子價(jià)格影子價(jià)格o對(duì)偶單純形法對(duì)偶單純形法o靈敏度分析靈敏度分析第第85頁頁線性規(guī)劃的對(duì)偶理論線性規(guī)劃的對(duì)偶理論o教學(xué)目的與要求：了解對(duì)偶問題產(chǎn)生的經(jīng)濟(jì)背景，教學(xué)目的與要求：了解對(duì)偶問題產(chǎn)生的經(jīng)濟(jì)背景，熟練掌握對(duì)偶單純形法和影子價(jià)格概念，熟練掌握熟練掌握對(duì)偶單純形法和影子價(jià)格概念，熟練掌握靈敏度分析方法。靈敏度分析方法。o重點(diǎn)與難點(diǎn)：重點(diǎn)同上，難點(diǎn)是對(duì)偶理論。重點(diǎn)與難點(diǎn)：重點(diǎn)同上，難點(diǎn)是對(duì)偶理論。o教學(xué)方法：課堂講授為主并配合課件和教學(xué)方法：課堂講授為主并配合課件和WinQSB軟軟件。件。o思考題、討論題、作業(yè)：教材第思考題

41、、討論題、作業(yè)：教材第4章習(xí)題章習(xí)題 o參考資料：見緒論參考資料：見緒論o學(xué)時(shí)分配：學(xué)時(shí)分配：8學(xué)時(shí)學(xué)時(shí) 第第86頁頁2 21 1 對(duì)偶線性規(guī)劃問題對(duì)偶線性規(guī)劃問題 對(duì)偶問題的提出對(duì)偶問題的提出 內(nèi)容一致，而從相反的角度提出的一對(duì)問題，稱內(nèi)容一致，而從相反的角度提出的一對(duì)問題，稱為一對(duì)對(duì)偶問題。為一對(duì)對(duì)偶問題。第第87頁頁例例1：某工廠在計(jì)劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品，：某工廠在計(jì)劃期內(nèi)安排生產(chǎn)甲、乙兩種產(chǎn)品，這些產(chǎn)品分別需要在這些產(chǎn)品分別需要在A、B、C、D四種不同的設(shè)備上四種不同的設(shè)備上加工。產(chǎn)品在各臺(tái)設(shè)備上需要加工的臺(tái)時(shí)數(shù)如下表：加工。產(chǎn)品在各臺(tái)設(shè)備上需要加工的臺(tái)時(shí)數(shù)如下表：A B C

42、D甲甲 2 1 4 0乙乙 2 2 0 4產(chǎn)品產(chǎn)品設(shè)備設(shè)備已知已知A、B、C、D設(shè)備的有效臺(tái)時(shí)數(shù)分別是設(shè)備的有效臺(tái)時(shí)數(shù)分別是12、8、16、12。售出一單位甲產(chǎn)品獲利。售出一單位甲產(chǎn)品獲利2萬元，一單位乙萬元，一單位乙產(chǎn)品獲利產(chǎn)品獲利3萬元。如何安排生產(chǎn)使工廠獲利最大？萬元。如何安排生產(chǎn)使工廠獲利最大？122212121214,LP max23221228 4164120 x xZxxxxxxxxxx解：設(shè)分別為計(jì)劃期內(nèi)生產(chǎn)甲、乙產(chǎn)品的數(shù)量模型為從相反的角度提出問題：工廠決策者決定不生產(chǎn)甲、從相反的角度提出問題：工廠決策者決定不生產(chǎn)甲、乙兩種產(chǎn)品，而對(duì)設(shè)備的有效臺(tái)時(shí)數(shù)進(jìn)行出租，用租乙兩種產(chǎn)品，

43、而對(duì)設(shè)備的有效臺(tái)時(shí)數(shù)進(jìn)行出租，用租金的方法獲得最大利潤。應(yīng)如何考慮？金的方法獲得最大利潤。應(yīng)如何考慮？決策者要考慮給每一種設(shè)備出租一個(gè)臺(tái)時(shí)的定價(jià)。決策者要考慮給每一種設(shè)備出租一個(gè)臺(tái)時(shí)的定價(jià)。在何種價(jià)格下，決策者接受出租設(shè)備呢？在何種價(jià)格下，決策者接受出租設(shè)備呢？1234, ,y yyyA B C D設(shè)分別表示出租四種設(shè)備一個(gè)首先臺(tái)時(shí)的價(jià)格。12341234,2402,22043.yyyyyyyy用生產(chǎn)單位甲產(chǎn)品的臺(tái)時(shí)數(shù)出租，收取的租金應(yīng)不低于生產(chǎn)單位甲產(chǎn)品所獲得的利潤，即同理其次1234,1281612Wyyyy四種設(shè)備的有效臺(tái)時(shí)數(shù)全部出租后 獲得的總租金是建立建立LP數(shù)學(xué)模型數(shù)學(xué)模型1234

44、1234123412341281612240222043,min ,0Wyyyyyyyyyyyyyyyy1212121212max 232212284164120Zxxxxxxxxxx，顯然，當(dāng)顯然，當(dāng)maxZ=minW時(shí)，時(shí)，對(duì)于決策者來說這兩種方對(duì)于決策者來說這兩種方案都是最優(yōu)的。案都是最優(yōu)的。第第91頁頁2.2.對(duì)偶線性規(guī)劃的模型對(duì)偶線性規(guī)劃的模型max 0ZCXAXbXmin 0WYbYACY第第92頁頁對(duì)偶線性規(guī)劃的特點(diǎn)：對(duì)偶線性規(guī)劃的特點(diǎn)：o一個(gè)規(guī)劃中的每一個(gè)約束，對(duì)應(yīng)對(duì)偶規(guī)劃中的一個(gè)規(guī)劃中的每一個(gè)約束，對(duì)應(yīng)對(duì)偶規(guī)劃中的一個(gè)決策變量；一個(gè)決策變量；o一個(gè)規(guī)劃中目標(biāo)函數(shù)系數(shù)恰為對(duì)偶規(guī)

45、劃約束條一個(gè)規(guī)劃中目標(biāo)函數(shù)系數(shù)恰為對(duì)偶規(guī)劃約束條件右端常數(shù)項(xiàng)；件右端常數(shù)項(xiàng)；o一個(gè)規(guī)劃求最小化，而對(duì)偶規(guī)劃求最大化；一個(gè)規(guī)劃求最小化，而對(duì)偶規(guī)劃求最大化； o目標(biāo)函數(shù)求最小化搭配目標(biāo)函數(shù)求最小化搭配 約束；目標(biāo)函數(shù)約束；目標(biāo)函數(shù)求最大化搭配求最大化搭配 約束；約束；o兩個(gè)規(guī)劃都有非負(fù)限制。兩個(gè)規(guī)劃都有非負(fù)限制?！?”“ ”第第93頁頁例例1 1：寫出下面原規(guī)劃的對(duì)偶規(guī)劃：寫出下面原規(guī)劃的對(duì)偶規(guī)劃123123123123LP:max 222 423,0gyyyyyyyyyyyy1212121212LP:min 2324121 21,0Sxxxxxxxxxx第第94頁頁定理定理1 如果線性規(guī)劃中第

46、如果線性規(guī)劃中第k個(gè)約束條件是等式，則個(gè)約束條件是等式，則它的對(duì)偶規(guī)劃中的第它的對(duì)偶規(guī)劃中的第k個(gè)變量無非負(fù)限制，反個(gè)變量無非負(fù)限制，反之亦然。之亦然。第第95頁頁例例2 2：寫出下面原規(guī)劃的對(duì)偶規(guī)劃：寫出下面原規(guī)劃的對(duì)偶規(guī)劃12121212min 4553 25,0Sxxxxxxxx12121212 max 354 5250,gyyyyyyyy解：無非負(fù)限制第第96頁頁例例3 3：寫出下面原規(guī)劃的對(duì)偶規(guī)劃：寫出下面原規(guī)劃的對(duì)偶規(guī)劃12121212min 5625530,Sxxxxxxxx無限制12121212 max 535 2560gyyyyyyyy解：無限制，原規(guī)劃與對(duì)偶規(guī)劃的對(duì)應(yīng)關(guān)系原

47、規(guī)劃與對(duì)偶規(guī)劃的對(duì)應(yīng)關(guān)系1maxnjjjZc x1minmiiiWb y(1,2, )00jjjjxjnnxxx有 個(gè)變量自由（無約束）變量變量約束約束條件條件目標(biāo)目標(biāo)函數(shù)函數(shù)LP原問題原問題LP對(duì)偶問題對(duì)偶問題約束約束條件條件變量變量目標(biāo)目標(biāo)函數(shù)函數(shù)(1,2,)00iiiimy imyyy有 個(gè)變量自由（無約束）(1,2,)ijjiijjiijjima xb ima xba xb有 個(gè)約束(1,2, )ijiiijiiijiinjna yca yca yc有 個(gè)約束第第98頁頁練習(xí)：寫出下列練習(xí)：寫出下列LP問題的對(duì)偶問題模型問題的對(duì)偶問題模型1231231223123min842202 8

48、0 + 30,0,Zxxxxxxxxxxxxx自由變量1231212313123LPmax208032 8 4 + 20,0Wyyyyyyyyyyyyy 模型：自由變量,第第99頁頁3.3.對(duì)偶線性規(guī)劃的性質(zhì)對(duì)偶線性規(guī)劃的性質(zhì)LP max (1)0SCXAXbX：LP min (2)0gYbYACY：定理定理2(弱對(duì)偶定理弱對(duì)偶定理) 對(duì)偶規(guī)劃對(duì)偶規(guī)劃(1)，(2)有最優(yōu)解的有最優(yōu)解的充分必要條件是它們同時(shí)有可行解。充分必要條件是它們同時(shí)有可行解。 定理定理3(最優(yōu)性定理最優(yōu)性定理) 如果如果 分別是分別是(1)，(2)的的可行解，且可行解，且 則則 分別是分別是(1)，(2)的最的最優(yōu)解。優(yōu)

49、解。00,YXbYCX0000,YX第第100頁頁定理定理4 如果對(duì)偶規(guī)劃如果對(duì)偶規(guī)劃(1)，(2)中，有一個(gè)存在最優(yōu)中，有一個(gè)存在最優(yōu)解，那么另一個(gè)也一定有最優(yōu)解。并且兩個(gè)規(guī)劃的解，那么另一個(gè)也一定有最優(yōu)解。并且兩個(gè)規(guī)劃的目標(biāo)函數(shù)的最優(yōu)值相等。目標(biāo)函數(shù)的最優(yōu)值相等。注意：重點(diǎn)研究兩個(gè)規(guī)劃的最優(yōu)解之間的關(guān)系注意：重點(diǎn)研究兩個(gè)規(guī)劃的最優(yōu)解之間的關(guān)系122121212 LP max25156224 5,0Sxxxxxxxxx給定：12323123123 LP min1524562 521,0gyyyyyyyyyyy則對(duì)偶規(guī)劃為：分別化為標(biāo)準(zhǔn)形分別化為標(biāo)準(zhǔn)形1234523124125max20005

50、156224501,2,5jSxxxxxxxxxxxxxxj123452341235max15245006252101,2,5igyyyyyyyyyyyyyi 2327217max21xxS12317min201412gyyy原問題的最優(yōu)單純形表原問題的最優(yōu)單純形表C2 1 0 0 002115/2 7/2 3/2 0 0 1 5/4 -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2S=17/2 0 0 0 -1/4 -1/2312xxx12345 xxxxxBxBc*b對(duì)偶問題的最優(yōu)單純形表對(duì)偶問題的最優(yōu)單純形表b-15 -24 -5 0 0-24-5 1/4 1/2

51、-5/4 1 0 -1/4 1/4 15/2 0 1 1/2 -3/2g=-17/2-15/2 0 0 -7/2 -3/223yy12345 yyyyyByBb*C第第104頁頁重要結(jié)論：重要結(jié)論：給出一對(duì)對(duì)偶線性規(guī)劃，只需解其中一給出一對(duì)對(duì)偶線性規(guī)劃，只需解其中一個(gè)線性規(guī)劃得出最優(yōu)解和目標(biāo)函數(shù)最優(yōu)值。它的對(duì)個(gè)線性規(guī)劃得出最優(yōu)解和目標(biāo)函數(shù)最優(yōu)值。它的對(duì)偶規(guī)劃的目標(biāo)函數(shù)最優(yōu)值與原規(guī)劃的目標(biāo)函數(shù)值相偶規(guī)劃的目標(biāo)函數(shù)最優(yōu)值與原規(guī)劃的目標(biāo)函數(shù)值相同，而最優(yōu)解可用原規(guī)劃最優(yōu)表中的松弛變量的檢同，而最優(yōu)解可用原規(guī)劃最優(yōu)表中的松弛變量的檢驗(yàn)數(shù)乘以驗(yàn)數(shù)乘以“-1”得到。得到。第第105頁頁o例：線性規(guī)劃問題例

52、：線性規(guī)劃問題 其對(duì)偶問題的最優(yōu)解為其對(duì)偶問題的最優(yōu)解為 求原問題的求原問題的最優(yōu)解。最優(yōu)解。提示：運(yùn)用對(duì)偶模型最優(yōu)解之間的關(guān)系，分析松弛變提示：運(yùn)用對(duì)偶模型最優(yōu)解之間的關(guān)系，分析松弛變量取值，決定對(duì)應(yīng)變量的值。量取值，決定對(duì)應(yīng)變量的值。123413412341234max2562 822212,0Zxxxxxxxxxxxx x x x12*=4=1 yy，4.4.影子價(jià)格影子價(jià)格( Shadow price)( Shadow price)0,max11122121111112211nmnmnmnnnnnnxxbxaxabxaxabxaxaxcxcxcS根據(jù)最優(yōu)性定理，根據(jù)最優(yōu)性定理， 是原規(guī)

53、劃約束條是原規(guī)劃約束條件右端項(xiàng)，它代表件右端項(xiàng)，它代表第第i種資源的擁有量，種資源的擁有量，對(duì)偶變量對(duì)偶變量 表示對(duì)表示對(duì)一個(gè)單位第一個(gè)單位第i種資源種資源的估價(jià)。它不是該的估價(jià)。它不是該資源的市場價(jià)格，資源的市場價(jià)格，而是根據(jù)該資源在而是根據(jù)該資源在生產(chǎn)中做出的貢獻(xiàn)生產(chǎn)中做出的貢獻(xiàn)而作的估價(jià)，稱為而作的估價(jià)，稱為影子價(jià)格。影子價(jià)格。miiinjjjgybxcS11ibiy11221111112122111min,0mmmmmmnmnmnmgb yb yb ya ya yca yayca yaycyy 第第107頁頁關(guān)于影子價(jià)格的幾個(gè)重要結(jié)論關(guān)于影子價(jià)格的幾個(gè)重要結(jié)論: :（1）影子價(jià)格的求法

54、：對(duì)偶問題的最優(yōu)解，即為原）影子價(jià)格的求法：對(duì)偶問題的最優(yōu)解，即為原問題約束條件右端常數(shù)項(xiàng)的影子價(jià)格。問題約束條件右端常數(shù)項(xiàng)的影子價(jià)格。 具體做法：將原規(guī)劃最優(yōu)表中的松弛變量的檢驗(yàn)具體做法：將原規(guī)劃最優(yōu)表中的松弛變量的檢驗(yàn)數(shù)乘以數(shù)乘以-1，就得到了對(duì)應(yīng)于原規(guī)劃約束條件右端，就得到了對(duì)應(yīng)于原規(guī)劃約束條件右端常數(shù)項(xiàng)（即資源限制量）的影子價(jià)格。常數(shù)項(xiàng)（即資源限制量）的影子價(jià)格。第第108頁頁（2） 影子價(jià)格是一種邊際價(jià)格（影子價(jià)格是一種邊際價(jià)格（Boundary price）miiinjjjgybxcS11在上式中，對(duì)在上式中，對(duì) 求偏導(dǎo)數(shù)，得求偏導(dǎo)數(shù)，得ib., 2 , 1,miybSii這說明，

55、這說明， 的值相當(dāng)于在給定的生產(chǎn)條件下，的值相當(dāng)于在給定的生產(chǎn)條件下， 每增加一個(gè)單位時(shí)，目標(biāo)函數(shù)每增加一個(gè)單位時(shí)，目標(biāo)函數(shù)S 的增加量，即總的增加量，即總收入的變化率（總收入增加一個(gè)影子價(jià)格值）。收入的變化率（總收入增加一個(gè)影子價(jià)格值）。ibiy第第109頁頁（3） 影子價(jià)格是一種機(jī)會(huì)成本（影子價(jià)格是一種機(jī)會(huì)成本（Opportunity cost） 在純市場經(jīng)濟(jì)條件下，當(dāng)某種資源的市場價(jià)格在純市場經(jīng)濟(jì)條件下，當(dāng)某種資源的市場價(jià)格低于影子價(jià)格時(shí)，可以買進(jìn)這種資源擴(kuò)大生產(chǎn)；低于影子價(jià)格時(shí)，可以買進(jìn)這種資源擴(kuò)大生產(chǎn)；相反當(dāng)市場價(jià)格高于影子價(jià)格，可賣出這種資源相反當(dāng)市場價(jià)格高于影子價(jià)格，可賣出這種資

56、源獲取更大的利潤。獲取更大的利潤。注意：由于影子價(jià)格可為決策者提供決策依據(jù)，注意：由于影子價(jià)格可為決策者提供決策依據(jù)，因此各種資源的影子價(jià)格應(yīng)當(dāng)保密。因此各種資源的影子價(jià)格應(yīng)當(dāng)保密。第第110頁頁（4）影子價(jià)格大于零時(shí)，對(duì)應(yīng)的松弛變量為非基）影子價(jià)格大于零時(shí)，對(duì)應(yīng)的松弛變量為非基變量，其取值為零，則該約束條件為等式，這說變量，其取值為零，則該約束條件為等式，這說明此種資源已被充分利用。明此種資源已被充分利用。影子價(jià)格等于零時(shí)，對(duì)應(yīng)的松弛變量為基變量，一影子價(jià)格等于零時(shí)，對(duì)應(yīng)的松弛變量為基變量，一般地說，其取值大于零，則該約束條件不等式是成般地說，其取值大于零，則該約束條件不等式是成立的（立的（

57、“”關(guān)系）。這說明此資源是過剩資源，沒關(guān)系）。這說明此資源是過剩資源，沒有被充分利用。有被充分利用。影子價(jià)格等于零，不是說該資源沒有價(jià)格，而是表影子價(jià)格等于零，不是說該資源沒有價(jià)格，而是表明該資源是過剩資源，再買進(jìn)此資源不會(huì)增加總收明該資源是過剩資源，再買進(jìn)此資源不會(huì)增加總收入。入。第第111頁頁檢驗(yàn)數(shù)的含義：檢驗(yàn)數(shù)的含義：111jjBjBjjBjjjcC BpC BpxC Bpxc檢驗(yàn)數(shù)，是影子價(jià)格，列向量為生產(chǎn)一個(gè)單位產(chǎn)品消耗每種資源的數(shù)量，因此就是按影子價(jià)格計(jì)算、生產(chǎn)一個(gè)單位產(chǎn)品所消耗的費(fèi)用，稱為隱含成本。是該產(chǎn)品的產(chǎn)值，于是檢驗(yàn)數(shù)就是該產(chǎn)品產(chǎn)值與生產(chǎn)一個(gè)單位產(chǎn)品消耗的成本與之差。顯然，

58、當(dāng)產(chǎn)品的產(chǎn)值大于隱含成本時(shí)，安排生產(chǎn)此產(chǎn)品有利，否則應(yīng)安排其他產(chǎn)品的生產(chǎn)。第第112頁頁4. 4. 對(duì)偶單純形法對(duì)偶單純形法定義定義1：將線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)形式后，對(duì)某：將線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)形式后，對(duì)某一確定的基矩陣一確定的基矩陣B，令非基變量等于零，根據(jù)系，令非基變量等于零，根據(jù)系統(tǒng)約束條件解出基變量，則這組解稱為基矩陣統(tǒng)約束條件解出基變量，則這組解稱為基矩陣B的的基解基解。滿足非負(fù)約束條件的基解，稱為。滿足非負(fù)約束條件的基解，稱為基可行基可行解解。 第第113頁頁12121212max2543s.t.280,0Sxxxxxxxx12132412512345max254328,0Sx

59、xxxxxxxxxxxxx試找出下列線性規(guī)劃模型的基解，并判斷是否可行？是否最優(yōu)？第第114頁頁定義定義2：設(shè)：設(shè) 是線性規(guī)劃是線性規(guī)劃的一組基變量，其對(duì)應(yīng)的基矩陣是的一組基變量，其對(duì)應(yīng)的基矩陣是B，對(duì)應(yīng)的基解，對(duì)應(yīng)的基解為為 ，如果這組基對(duì)應(yīng)的檢驗(yàn)數(shù)全部小于等于零，如果這組基對(duì)應(yīng)的檢驗(yàn)數(shù)全部小于等于零，即即 ，則稱這組基為該線性，則稱這組基為該線性規(guī)劃的一組規(guī)劃的一組正則基正則基。 為為正則解正則解。 12,mx xxmax0SCXAXbX0X10BCC B A0X線性規(guī)劃的對(duì)偶單純形法是從第一個(gè)正則解開始線性規(guī)劃的對(duì)偶單純形法是從第一個(gè)正則解開始迭代的。迭代的。第第115頁頁對(duì)偶單純形法的

60、迭代步驟對(duì)偶單純形法的迭代步驟: :（1）從一個(gè)正則解開始，列出對(duì)偶單純形表；）從一個(gè)正則解開始，列出對(duì)偶單純形表；（2）如基變量的取值全部大于等于零，則線性規(guī)劃）如基變量的取值全部大于等于零，則線性規(guī)劃已取得最優(yōu)解，計(jì)算結(jié)束；否則轉(zhuǎn)（已取得最優(yōu)解，計(jì)算結(jié)束；否則轉(zhuǎn)（3）；）；（3）在基變量中，挑選取負(fù)值中最小的一個(gè)，作為）在基變量中，挑選取負(fù)值中最小的一個(gè)，作為出基變量（若最小負(fù)值相同，可由出基變量（若最小負(fù)值相同，可由Bland法則確法則確定）；定）；（4）在出基變量行中，如果非基變量的約束系數(shù)全）在出基變量行中，如果非基變量的約束系數(shù)全部非負(fù)，則原問題不存在可行解；否則轉(zhuǎn)（部非負(fù)，則原問