1、 廈廈門門理理工工學學院院 運籌學A,B 某某工工廠廠計計劃劃生生產產甲甲、乙乙兩兩種種產產品品, ,已已知知生生產產單單位位產產品品所所需需的的設設備備臺臺時時及及兩兩種種原原材材料料的的消消 耗耗見見下下表表：甲產品甲產品乙產品乙產品提供量提供量設設 備備128臺時臺時材料材料A4016kg材料材料B0412kg利潤利潤23單位元單位元一一個個問問題題應應如如何何安安排排生生產產，使使得得利利潤潤最最大大？ 12xx解解： 設設生生產產甲甲、乙乙產產品品 、件件。12121212maxZ2328416412,0 xxxxxxx x 目目標標函函數數 約約束束條條件件 思思考考：與與解解方方

2、程程有有何何關關系系？(4,2) ,14TXz 最最優優決決策策：。一一、運運籌籌學學的的起起源源及及研研究究領領域域1939年年前前，蘇蘇聯聯數數學學家家康康托托洛洛維維奇奇得得到到生生產產組組織織與與計計劃劃問問題題的的數數學學模模型型：112211112211211222221122max.0(1,2,., )nnnnnnmmmnnmjZc xc xc xa xa xa xba xa xa xbs taxaxaxbxjn 求求解解問問題題也也稱稱為為解解線線性性規規劃劃問問題題。緒緒 論論因因為為計計算算方方法法沒沒有有得得到到解解決決，未未受受到到人人們們的的重重視視。 第第二二次次世

3、世界界大大戰戰中中，大大量量的的軍軍事事問問題題（布布雷雷、制制空空、護護航航等等）、運運輸輸問問題題、計計劃劃問問題題、后后勤勤問問題題等等的的數數學學模模型型都都是是線線性性規規劃劃問問題題。SCOOP 大大戰戰推推動動線線性性規規劃劃問問題題求求解解方方法法的的研研究究。美美國國空空軍軍研研究究小小組組提提出出了了單單純純形形方方法法，使使得得線線性性規規劃劃問問題題能能在在計計算算機機上上得得到到有有效效地地解解決決。Scientific Computation of Optimum ProgramsOperational ResearchOR 這這就就形形成成了了學學科科“”, ,簡

4、簡記記為為“”，當當時時翻翻譯譯為為“作作戰戰研研究究”。1 19 97 75 5年年，瑞瑞典典皇皇家家科科學學院院授授予予線線性性規規劃劃創創始始人人蘇蘇聯聯數數學學家家康康托托洛洛維維諾諾貝貝爾爾經經濟濟學學獎獎。 隨隨著著計計算算機機的的發發展展，運運籌籌學學得得到到迅迅速速發發展展，它它在在工工程程、運運輸輸、控控制制、教教育育、醫醫療療、衛衛生生、交交通通、管管理理、投投資資、預預測測、城城市市規規劃劃等等領領域域得得到到廣廣泛泛應應用用。 1 19 95 57 7年年，我我國國學學者者受受“運運籌籌于于帷帷幄幄之之中中，決決勝勝于于千千里里之之外外”古古語語啟啟發發，改改名名為為“

5、運運籌籌學學”。1 1 最短路問題最短路問題 . .管道（線）鋪設路線最短管道（線）鋪設路線最短 . .貨物運輸時間（線路）最短貨物運輸時間（線路）最短2. 2. 分配問題分配問題 . .分房問題分房問題 . .有限資源的最佳配置有限資源的最佳配置3 網絡計劃技術網絡計劃技術 .有效組織工程實施有效組織工程實施 .地區交通網絡的建設地區交通網絡的建設4. 4. 決策樹模型決策樹模型 . .市場風險投資決策市場風險投資決策 . .技術引進決策技術引進決策 . .產品推銷策略產品推銷策略5 最小支撐樹問題最小支撐樹問題 .電話通訊網的架設電話通訊網的架設 .地區交通網絡的建設地區交通網絡的建設6.

6、 6. 網絡流問題網絡流問題 . .交通流量最大交通流量最大 . .物流運輸費用最少物流運輸費用最少7 7 網絡圖的其他一些應用問題網絡圖的其他一些應用問題 . .公交汽車線路的最優安排或公交汽車線路的最優安排或鏈接鏈接 . .車輛調度問題車輛調度問題 . .工廠選址問題工廠選址問題平板的最優激光鉛化平板的最優激光鉛化油田的最優勘探油田的最優勘探考古發掘物的順序排列考古發掘物的順序排列基因密碼基因密碼計算機切割的最優安排計算機切割的最優安排消防隊和災情點的調試計劃消防隊和災情點的調試計劃垃圾清除或街道清洗的調度計劃垃圾清除或街道清洗的調度計劃按訂貨以最小角邊料切割紙或鋼按訂貨以最小角邊料切割紙

7、或鋼材等材等運運籌籌學學是是一一門門研研究究系系統統優優化化的的科科學學。二二、運運籌籌學學研研究究所所需需的的基基本本知知識識及及研研究究對對象象 數數學學分分析析、高高等等代代數數、解解析析幾幾何何提提供供了了研研究究原原理理的的基基礎礎，計計算算機機理理論論提提供供了了計計算算手手段段。 運運籌籌學學是是應應用用學學科科，是是近近代代應應用用數數學學的的一一個個最最活活躍躍分分支支，利利用用數數學學方方法法為為決決策策者者提提供供科科學學依依據據的的學學科科。有有限限的的資資源源如如何何滿滿足足無無限限的的需需求求？提提高高經經濟濟效效益益改改進進技技術術，合合理理安安排排資資源源。第第

8、1章章 線性規劃與單純形法線性規劃與單純形法第第1節節 線性規劃問題及其數學模型線性規劃問題及其數學模型A,B 某某工工廠廠計計劃劃生生產產甲甲、乙乙兩兩種種產產品品, ,已已知知生生產產單單例例位位產產品品所所需需的的設設備備臺臺時時及及兩兩種種原原材材料料的的1 1 消消耗耗見見下下表表：甲產品甲產品乙產品乙產品提供量提供量設設 備備128臺時臺時材料材料A4016kg材料材料B0412kg利潤利潤23單位元單位元. 11 11 問問題題的的提提出出應應如如何何安安排排生生產產，使使得得利利潤潤最最大大？ 12xx解解： 設設生生產產甲甲、乙乙產產品品 、件件。12121212maxZ23

9、28416412,0 xxxxxxx x 目目標標函函數數 約約束束條條件件 (4,2) ,14TXz 經經計計算算得得最最優優決決策策：。 如果如果種產品，生產nAAA21種資源mBBB,21產品計劃問題有關信息表產品計劃問題有關信息表 12nAAA111212122212nnmmmnaaaaaaaaa12mBBB 12mbbb 12nccc可可提提供供量量產產品品種種類類單單位位利利潤潤資資源源種種類類ijjia設設單單位位第第 種種產產品品所所需需第第 種種資資源源量量11(1,2,.,)0(1,2,., )njjjnijjijjmaxZc xCXa xbimxjn 目目標標函函數數約約

10、束束方方程程jjAx設設生生產產產產品品件件，此此類類問問題題的的數數學學模模型型為為：112211112211211222221122max.0(1,2,., )nnnnnnmmmnnmjZc xc xc xa xa xa xba xa xa xbs taxaxaxbxjn subject to 例例2 某地區有甲、乙、丙三個食鹽產地，產某地區有甲、乙、丙三個食鹽產地，產量分別為量分別為70、80、100萬噸；有萬噸；有A，B，C，D四個城市需要食鹽，需求量為四個城市需要食鹽，需求量為40，60，90，60萬萬噸。如何安排運輸使費用最低？噸。如何安排運輸使費用最低？ 每噸食鹽運費如表每噸食鹽

11、運費如表運價運價 A城城B城城C城城D城城甲廠甲廠3345乙廠乙廠6431丙廠丙廠2332解：設有解：設有 i 個廠地（個廠地（i1，2，3），），j個銷地個銷地 （j=1,2,3,4)。并設并設Xij-第第i個鹽產地運往第個鹽產地運往第j個鹽銷地的運量。個鹽銷地的運量。111213142122232431323334700100 xxxxxxxxxxxx8 8112131122232132333142434xxxxxxxxxxxx4 40 06 60 09 90 06 60 0運出量等于產量：運出量等于產量：運達量等于需求量：運達量等于需求量：目標函數為：目標函數為：111213142134

12、S=3 3456.2minxxxxxx運輸問題的數學模型為：運輸問題的數學模型為：111213142122232431323334700100 xxxxxxxxxxxx8 8112131122232132333142434xxxxxxxxxxxx4 40 06 60 09 90 06 60 0目標函數為：目標函數為：111213142134S=3 3456.2minxxxxxx 。已知各已知各產地的產地的和各銷地的和各銷地的以及各產地到各銷地的以及各產地到各銷地的 某種物資有若干產地和銷地，現在需要某種物資有若干產地和銷地，現在需要把把這種物資從各個產地運到各個銷地，這種物資從各個產地運到各個

13、銷地，問應如何組織調運，才能使，問應如何組織調運，才能使？根據具體問題組織調運。根據具體問題組織調運。 有關信息表有關信息表單位單位 運價運價 銷銷 或運距或運距 地地產地產地B1 B2 Bn產產 量量A1 A2 Amc11 c12 c1 n c21 c22 c2n cm1 cm2 cm na1 a2 am銷銷 量量 b1 b2 bnnjjmiiba11ijijxAB設設表表示示從從產產地地運運往往銷銷地地的的運運量量。運運輸輸問問題題數數學學模模型型的的建建立立1(1,2,.,)iinijijAaxaim 由由于于從從運運出出量量等等于于產產量量 ：1(1,2,., )jjmijjiBbxb

14、jn 又又由由于于銷銷地地接接收收量量等等于于需需求求量量 ：11mnijijijZc x 總總運運費費為為運運輸輸問問題題的的數數學學模模型型：11(1,2,.,).(1,2,., )0(1,2,.,;1,2,., )nijijmijjiijxajms txbinxim jn 11mnijijijminZc x 目目標標函函數數 minjjiba11產銷平衡條件合理下料問題合理下料問題毛坯，問應如何選取合理的下料方法，使得既滿足毛坯，問應如何選取合理的下料方法，使得既滿足 對截出毛坯的數量要求，又使所用的原材料最少對截出毛坯的數量要求，又使所用的原材料最少（或廢料最少）？（或廢料最少）？ 在

15、加工業中，經常遇到這類問題。在加工業中，經常遇到這類問題。 問題的一般提法是：已知某種尺寸的棒料或板材，問題的一般提法是：已知某種尺寸的棒料或板材，需要將其切割成一定數量既定規格的幾種零件需要將其切割成一定數量既定規格的幾種零件 例例3 3 某廠接受了一批加工定貨，客戶要求加某廠接受了一批加工定貨，客戶要求加工工100100套鋼架，每套由長套鋼架，每套由長2.92.9米、米、2.12.1米和米和1.51.5米的米的圓鋼各一根組成。現在僅有一批長圓鋼各一根組成。現在僅有一批長7.47.4米的鋼管毛米的鋼管毛坯，問應如何下料，使所用的鋼管根數最少？坯，問應如何下料，使所用的鋼管根數最少？ 最簡單的

16、處理方法：從一根鋼管上截取最簡單的處理方法：從一根鋼管上截取2.92.9米、米、2.12.1米和米和1.51.5米的管料各一根時正好配成一套鋼架，米的管料各一根時正好配成一套鋼架，100100套鋼架總共需要套鋼架總共需要100100根鋼管毛坯。每根鋼管毛坯根鋼管毛坯。每根鋼管毛坯剩下剩下0.90.9米的殘料，米的殘料，100100根毛坯總共剩根毛坯總共剩9090米殘料。米殘料。這是最好的辦法嗎？這是最好的辦法嗎？截法12345678單位2.9米21110000根2.1米02103210根1.5米10130234根殘料0.10.30.901.10.20.81.4米 合理套裁肯定會有更好的效果。先

17、設法列出合理套裁肯定會有更好的效果。先設法列出所有的下料方案，思路如下表。所有的下料方案，思路如下表。12345678xxxxxxxx用用量量根根81123456781234567812345678123456781280.10.30.901.10.20.81.42111000010002103210100. .10130234100,0iiMinZxMinZxxxxxxxxxxxxxxxxxxxxxxxxs txxxxxxxxxxx 或或ixi設設 為為按按第第 種種方方案案下下料料所所用用的的鋼鋼管管的的根根數數，則則殘殘料料最最少少 例例4 4 現準備采購甲、乙兩種食品，表中給現準備采購

18、甲、乙兩種食品，表中給出了已知價格及相關的營養成分。問應如何采出了已知價格及相關的營養成分。問應如何采購食品才能在保證營養要求的前提下，花費最購食品才能在保證營養要求的前提下，花費最省？省？ 四、四、 合理配料問題合理配料問題 問題的一般提法：由多種原料配置成含有問題的一般提法：由多種原料配置成含有 m種成分的產品，并種成分的產品，并求成本最低求成本最低的配料方案。的配料方案。營養問題已知數據表營養問題已知數據表 1 公斤食物所公斤食物所 含營養成含營養成 食品食品 分數量分數量 營養營養 成分成分 甲甲 乙乙 每每 天天 的的 最最 低低 需需 要要 量量 （單位）（單位） 維維 生生 素素

19、 淀淀 粉粉 蛋蛋 白白 質質 1 5 3 3 1 2 90 100 120 單單 價（元）價（元） 12 19 最右欄給出了按營養學標準每人每天的最低需要量。最右欄給出了按營養學標準每人每天的最低需要量。依題意可列出下面的線性規劃：依題意可列出下面的線性規劃：12,xx設設分分別別為為甲甲、乙乙兩兩種種食食品品的的采采購購量量，則則12Z = 1.2x + 1.9x購購買買兩兩種種食食品品的的總總費費用用為為： 運動員集訓隊食譜設計；運動員集訓隊食譜設計； 幼兒園、醫院等特殊群體的營養配餐；幼兒園、醫院等特殊群體的營養配餐；機關、學校、企業等企事業單位團體機關、學校、企業等企事業單位團體 伙

20、食設計；伙食設計；家庭食譜設計；家庭食譜設計； 飼料配比及化工產品中的混合問題等。飼料配比及化工產品中的混合問題等。 某配合飼料廠生產某配合飼料廠生產以雞飼料為主的配合飼料，現準備研制一種以雞飼料為主的配合飼料，現準備研制一種新的新的，所用原料的營養成所用原料的營養成分和飼養標準見表，希望這種新飼料分和飼養標準見表，希望這種新飼料能滿足能滿足肉用仔雞的喂養需要肉用仔雞的喂養需要又使又使總成本盡可能低，總成本盡可能低，應如何設計配比方案？應如何設計配比方案？需求量(%) 19.01.00.700.940.360.190.30123456xxxxxx 已 知 各 種 原 料 的 購 進 價已 知

21、各 種 原 料 的 購 進 價 1 公 斤 分 別公 斤 分 別為為:3.14(玉米玉米)、5.40(豆餅豆餅)、2.20（麥麩）、（麥麩）、12.00（魚粉）、（魚粉）、4.00（骨粉）、（骨粉）、5.00（雞促進素）（雞促進素）元。元。 設設每每100100公斤公斤飼料中配給的玉米、豆餅、麥飼料中配給的玉米、豆餅、麥麩、魚粉、骨粉、雞促進素分別為麩、魚粉、骨粉、雞促進素分別為123456,x xxxxx ( (公公斤斤) )數學模型為：數學模型為：3.14 5.40 2.20 12.00 4.00 5.00單單位位價價格格：，元元1234563.145.42.21245minzxxxxxx

22、則則目目標標函函數數為為六、六、 污水處理問題污水處理問題 例例6 靠近某河流有兩個化工廠，流經第一化靠近某河流有兩個化工廠，流經第一化工廠的河流流量為每天工廠的河流流量為每天 500 萬萬m3，兩工廠之間有，兩工廠之間有一條流量為每天一條流量為每天 200 萬萬m3的支流（見圖）：的支流（見圖）： 第一化工廠每天排放污水第一化工廠每天排放污水2萬萬m3 ，第二化工，第二化工廠每天排放污水廠每天排放污水 1.4萬萬 m3 。污水從工廠。污水從工廠1 流到工流到工廠廠2 前會有前會有20%自然凈化。自然凈化。 而工廠而工廠1和工廠和工廠2處理污水的成本分別為處理污水的成本分別為1000元元/萬萬

23、m3和和800元元/萬萬m3。問兩工廠各。問兩工廠各應處理應處理多少污多少污水才能使處理污水的總費用最低？水才能使處理污水的總費用最低？ 解：設工廠解：設工廠1 1和工廠和工廠2 2每天分別處理污水每天分別處理污水x1 1和和x2 2萬萬 m3 3，則有：，則有：Min z=1000 x1+800 x2 (2-x1) / 500 0.0020.8 (2-x1) + 1.4-x2 / 700 0.002 x1 2, x2 1.4 x1, x20根據環保要求，河水中污水的含量應不大于根據環保要求，河水中污水的含量應不大于 0.2%。約束方程約束方程(1,2,., )jxjn 1 12211 112

24、21121 1222221 12212()()( , )( , ). .( , ),0nnnnnnmmmnnmnMaxMin Zc xc xc xa xa xa xba xa xa xbsta xaxa xbx xx 或目標函數（約束條件）10njijiixxcabx ， ， 為決策變量為價值系數，為技術系數為限額系數， 為變量的非負約束條件1.2線線性性規規劃劃問問題題的的幾幾何何解解法法圖圖解解法法幾幾何何解解法法直直觀觀，有有助助于于了了解解線線性性規規劃劃問問題題求求解解原原理理。先先熟熟悉悉如如下下平平面面：1 xy ）2 22 xy）22 yx 22y x yx xy 55x=14

25、y=x+3 5y=25-3x1ABCC: (1, 4.4)A: (5, 2)B: (1, 1.)Oxy問題問題1 1：x 有無最大（小）值？有無最大（小）值？問題問題2 2：y 有無最大（小）值？有無最大（小）值？問題問題3 3：z=2z=2x+y 有無最大（小）值？有無最大（小）值？1255334xyxyx在平面區域內在平面區域內可行解區域可行解區域55x=1x-4y+3=03x+5y-25=01ABCC(1.00, 4.40)A(5.00, 2.00)B(1.00, 1.00)Oxyzxyyxz22由.2軸上的截距在就是直線yzxyzxy2122 xy32 xyn求求z=2x+y的最的最大

26、值和最小值。大值和最小值。n所以所以z最大值最大值12nz最小值為最小值為31255334xyxyx12 解題步驟解題步驟4 將最優解代入目標函數，求出最優值。將最優解代入目標函數，求出最優值。1 在直角平面坐標系中畫出所有的約束等式，并找出在直角平面坐標系中畫出所有的約束等式，并找出所有約束條件的公共部分，稱為可行域，可行域中所有約束條件的公共部分，稱為可行域，可行域中的點稱為可行解。的點稱為可行解。 2 標出目標函數值增加或者減小的方向。標出目標函數值增加或者減小的方向。3 若求最大（小）值，則令目標函數等值線沿（逆）若求最大（小）值，則令目標函數等值線沿（逆）目標函數值增加的方向平行移動

27、，找與可行域最后目標函數值增加的方向平行移動，找與可行域最后相交的點，該點就是最優解。相交的點，該點就是最優解。圖解法umax Z = 2X1 + X2 u X1 + 1.9X2 3.8u X1 - 1.9X2 3.8us.t. X1 + 1.9X2 10.2u X1 - 1.9X2 -3.8u X1 ，X2 0例例 用圖解法求解線性規劃問題用圖解法求解線性規劃問題x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X

28、1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此點是唯一最優解，此點是唯一最優解，且最優目標函數值且最優目標函數值 max Z=17.2可行域可行域max Z = 2X1 + X2max Z=3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）34.2 = 3X1+5.7X2 藍色線段上的所有點都是最藍色線段上的所有點都是最優解這種

29、情形為有無窮多最優解這種情形為有無窮多最優解，但是最優目標函數值優解，但是最優目標函數值max Z=34.2是唯一的。是唯一的。可行域可行域nmin Z=5X1+4X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域可行域此點是唯一最優解此點是唯一最優解 006346321212121xxxxxxxx、246x1x2246無界解無界解( (無最優解無最優解) )maxZ=x1+2x2例例 max Z min

30、Z1236xx124xx1236xxx1x2O10203040102030405050無可行解無可行解(即無最優解即無最優解)0,050305 .140221212121 xxxxxxxxmax Z=3x1+4x2例例 由圖解法得到的幾種情況由圖解法得到的幾種情況 根據以上例題，進一步分析討論可知線性規劃的可行域和根據以上例題，進一步分析討論可知線性規劃的可行域和最優解有以下幾種可能的情況：最優解有以下幾種可能的情況： 1.可行域為封閉的有界區域可行域為封閉的有界區域 (a)有唯一的最優解；有唯一的最優解； (b)有無窮多個最優解；有無窮多個最優解； 2.可行域為封閉的無界區域可行域為封閉的無

31、界區域 (c)有唯一的最優解；有唯一的最優解； (d)有無窮多個最優解；有無窮多個最優解； (e)目標函數無界目標函數無界(即雖有可行解，但在可行域中，目標函數即雖有可行解，但在可行域中，目標函數可以無限增大或無限減少可以無限增大或無限減少)，因而沒有有限最優解。，因而沒有有限最優解。 3.可行域為空集可行域為空集 (f)沒有可行解，原問題無最優解沒有可行解，原問題無最優解幾個結論：幾個結論：1. 線性目標函數的最大（小）值一般在可行區域線性目標函數的最大（小）值一般在可行區域 的頂點處取得，也可能在邊界處取得。的頂點處取得，也可能在邊界處取得。2. 求線性目標函數的最優解，要注意分析求線性目

32、標函數的最優解，要注意分析 線性目標函數所表示的幾何意義線性目標函數所表示的幾何意義 在在 y 軸上的截距（兩維）。軸上的截距（兩維）。3. 圖解法只能解決平面問題，三維的線性規劃問題圖解法只能解決平面問題，三維的線性規劃問題圖解，困難就很大。圖解，困難就很大。1.3線線性性規規劃劃問問題題的的標標準準形形式式一一、線線性性規規劃劃問問題題的的數數學學模模型型（1 1）一般形式）一般形式 0,),(),(),(. .)(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax或11()( , )

33、1,2,. .01,2,njjjnijjijjMaxMin Zc xa xbims txjn 或或（）（）10njijiixxcabx ， ， 為決策變量為價值系數，為技術系數為限額系數， 為變量的非負約束條件（3 3）矩陣形式）矩陣形式0)(.)(XbAXtsCXZMinMax或其中其中 : 111212122212.nnmmmnaaaaaaAaaa 12,nxxXx 12,mbbbb 12,TnccCc 二二、線線性性規規劃劃問問題題的的標標準準型型maxZ = CXAX = bb0X0 （） 三三、線線性性規規劃劃問問題題標標準準化化 21kkkxxx12121212maxZ232841

34、6s.t412,0 xxxxxxx x 1 1） 12123142512345maxZ2328416s.t412,0 xxxxxxxxxx xxxx 解解： 1231231231231232310328. .31,0,m inZxxxxxxxxxs txxxxxx 符符 號號 不不 受受 限限 制制126712674126751267124567m ax2310328. .31,0Zxxxxxxxxxxxxxxs txxxxxxxxxx ., 12階子式階子式的的稱為矩陣稱為矩陣階行列式，階行列式，的的中所處的位置次序而得中所處的位置次序而得變它們在變它們在不改不改元素元素處的個處的個），位于

35、這些行列交叉），位于這些行列交叉列（列（行行中任取中任取矩陣矩陣在在定義定義kAkAknkmkkkAnm 回回顧顧矩矩陣陣、向向量量、解解線線性性方方程程組組方方面面的的知知識識1. ( )R A矩矩陣陣的的秩秩的的概概念念及及其其求求法法132202132015A 如如:已知已知A矩陣矩陣,研究其研究其k階子式階子式13202 12303 12101 13620 1220130215 二階子式二階子式: :共有共有 二階子式二階子式223418CC1320210201 1320230205 1220130215 共有共有 個三階子式個三階子式33344CC 132202132015A 201

36、0( ).ArDrDArAR A定義設在矩陣中有一個不等于的階子式，且所有階子式（如果存在的話）全等于 ，那末稱為矩陣 的最高階非零子式，數稱為矩陣的秩，記作并規定零矩陣的秩等于零.)( 子子式式的的最最高高階階數數中中不不等等于于零零的的是是的的秩秩矩矩陣陣AARAnm . 個個階階子子式式共共有有的的矩矩陣陣knkmCCkAnm 或說：或說：例例1.174532321的秩的秩求矩陣求矩陣 A解：解：中，中，在在 A，階子式只有一個階子式只有一個的的又又AA3. 03221 ，且且0 A. 2)( AR. , 數數是是唯唯一一確確定定的的梯梯形形矩矩陣陣中中非非零零行行的的行行梯梯形形，行行

37、階階把把它它變變為為行行階階變變換換總總可可經經過過有有限限次次初初等等行行任任何何矩矩陣陣nmA 這就是矩陣的秩。這就是矩陣的秩。還可用矩陣的初等變換方法求秩：還可用矩陣的初等變換方法求秩：例例2.00000340005213023012的的秩秩求求矩矩陣陣 B解解行，行，其非零行有其非零行有是一個行階梯形矩陣，是一個行階梯形矩陣，3B.4階子式全為零階子式全為零的所有的所有B, 0400230312 而而. 3)( BR向量的線性相關性向量的線性相關性2. 可可逆逆矩矩陣陣AA若若矩矩陣陣 可可逆逆，則則為為非非奇奇異異矩矩陣陣；1ABBAEAAB 若若，則則 可可逆逆，且且 。-1A E

38、E A 行行初初等等變變換換求求逆逆矩矩陣陣：（）( () )mAR(A )m則則為為滿滿秩秩陣陣，即即 ；A 則則0 0；A則則中中列列（行行）向向量量線線性性無無關關。例例3 3 求方陣求方陣 的逆矩陣的逆矩陣. . 343122321A解解343122321 A, 2.1存在存在 A, 2341211 A, 3331212 AijAaij為為元元素素的的代代數數余余子子式式（1）伴隨矩陣求逆矩陣法）伴隨矩陣求逆矩陣法 AAA11同理可得同理可得, 2, 6, 6, 223222113 AAAA, 2, 5, 4333231 AAA,222563462 A得得故故 AAA11 222563

39、46221.11125323231 ()jiAA abAcd 0adbc0AadbcdbAca 11AAadbc 1dbadbcca 例例4 4 已知已知且，求解如：如：1234A 2A 4231A 1421231A 1A 322rr 2131rrrr 解解的逆矩陣。的逆矩陣。 求矩陣求矩陣例例5=441431321A123100()134010144001AI 101011001120110321 121011001100110321（2）初等行變換求逆矩陣法）初等行變換求逆矩陣法23133rrrr 1211103641000100211232rrr 1 0 04410 1 00110 0

40、1121所以，所以，A的逆矩陣為的逆矩陣為4410111210 ,: 22112121 mmmmkkkkkkA 使使全全為為零零的的數數如如果果存存在在不不給給定定向向量量組組注意注意1211122 1. ,0, 0.nnnnkkkkk 若若線線性性無無關關 則則只只有有當當時時 才才有有成成立立., 2. 線線性性相相關關性性無無關關就就是是不不是是線線對對于于任任一一向向量量組組定義定義3 3則稱向量組則稱向量組 是線性相關的，否則稱它線性無關是線性相關的，否則稱它線性無關A3. 線線性性相相關關與與線線性性無無關關( (線線性性獨獨立立) )., 0, 0, 3. 線線性性無無關關則則說

41、說若若線線性性相相關關則則說說若若時時向向量量組組只只包包含含一一個個向向量量 .4. 組組是是線線性性相相關關的的包包含含零零向向量量的的任任何何向向量量.,. 5 量量共共面面向向量量相相關關的的幾幾何何意意義義是是三三是是兩兩向向量量共共線線；三三個個向向義義量量對對應應成成比比例例，幾幾何何意意充充要要條條件件是是兩兩向向量量的的分分它它線線性性相相關關的的量量組組對對于于含含有有兩兩個個向向量量的的向向維維向向量量組組n TnTTeee1 , 0 , 0,0 , 1 , 0,0 , 0 , 121 ，解解.),( 21階單位矩陣階單位矩陣是是的矩陣的矩陣維單位坐標向量組構成維單位坐標

42、向量組構成neeeEnn .)(01 nERE ，知知由由()R E 即即等等于于向向量量組組中中向向量量個個數數，故故向向量量組組線線性性無無關關。例例6線性無關。線性無關。， 742520111321 .21321的的線線性性相相關關性性，及及，試試討討論論向向量量組組 解解已知已知例例7設設1 122330kkk 問題轉為求解齊次方程組：問題轉為求解齊次方程組： 751421201),(321 2325rr ， 000220201., 2),(,2),(2121321321線性無關線性無關向量組向量組線性相關；線性相關；，向量組，向量組可見可見 RR 75122020112rr 1312

43、rrrr 5502202012132 事實上，有事實上，有的解的解討論線性方程組討論線性方程組的秩，的秩，和增廣矩陣和增廣矩陣如何利用系數矩陣如何利用系數矩陣bAxBA .,2的的秩秩陣陣的的秩秩等等于于增增廣廣矩矩矩矩陣陣的的充充分分必必要要條條件件是是系系數數有有解解元元非非齊齊次次線線性性方方程程組組定定理理bABAbxAnnm nrrBRAR 4. 方方程程組組解解的的判判別別0AX 齊齊次次方方程程組組 解解的的判判別別（總總是是有有解解）AXb 非非齊齊次次方方程程組組解解的的判判別別小結小結有唯一解有唯一解bAx nBRAR nBRAR 有無窮多解有無窮多解. .bAx )()(

44、BRAR 無解無解變量的個數變量的個數例例8 8 求解齊次線性方程組求解齊次線性方程組解解 4630463012211234123412342202220430 xxxxxxxxxxxx 施行初等行變換：施行初等行變換：對系數矩陣對系數矩陣 A13122rrrr 122121221143A 0000342101221)3(223 rrr212rr 00003421035201即得與原方程組同解的方程組即得與原方程組同解的方程組 , 0342, 0352432431xxxxxx34(,)xx 可可任任意意取取值值 ,342,352432431xxxxxx ,342,3522413222221cx

45、cxccxccx形形式式，把把它它寫寫成成通通常常的的參參數數令令2413,cxcx .1034350122214321 ccxxxx例例9 9 求解非齊次線性方程組求解非齊次線性方程組 . 3222, 2353, 132432143214321xxxxxxxxxxxx解解對增廣矩陣對增廣矩陣B進行初等變換進行初等變換 322122351311321B13122rrrr 10450104501132123rr 200001045011321, 3)(, 2)( BRAR顯顯然然，故方程組無解故方程組無解例例10 求解非齊次方程組的通解求解非齊次方程組的通解.213213043214321432

46、1 xxxxxxxxxxxx解解 對增廣矩陣對增廣矩陣B進行初等變換進行初等變換 2132111311101111B 2121001420001111.00000212100211011 , 2 BRAR由由于于故方程組有解，且有故方程組有解，且有 2122143421xxxxx 42442342242102120021xxxxxxxxxxxx.02102112000011424321 xxxxxx.,42任任意意其其中中xx所以方程組的通解為所以方程組的通解為1.4線線性性規規劃劃問問題題解解的的概概念念(1)2m nmaxZ = CXAX = bb0X0A （）（ ）其其中中1.解解，可可

47、行行解解，最最優優解解LP1LPX滿滿足足約約束束條條件件（ ）的的稱稱為為的的解解；LP1LPX滿滿足足約約束束條條件件（ ）, ,( (2 2) )的的稱稱為為的的可可行行解解；LP使使目目標標函函數數達達到到最最大大值值的的可可行行解解稱稱為為的的最最優優解解。LP()m nR(A)m,Am,BAmB0Bmn 設設即即矩矩陣陣 的的秩秩為為且且是是矩矩陣陣的的一一個個 階階非非奇奇異異子子式式（），則則稱稱 為為的的一一個個基基。 一一般般而而言言12(),LP(,.,mAB NBBP PP 為為方方便便起起見見，設設矩矩陣陣其其中中為為的的一一個個基基, ,則則) )。稱稱: :121

48、,.,mP PP）為為基基向向量量；12122,.,.,mmBP PPx xxX）對對應應的的變變量量為為基基 變變量量, ,記記為為；12,.,mmnNnmxxxX 3 3）其其余余個個變變量量為為非非基基 變變量量, ,記記為為。2.基基，基基向向量量，基基變變量量，非非基基變變量量3.基基解解，基基可可行行解解，可可行行基基(),LPAB NB 設設矩矩陣陣其其中中 為為的的一一個個基基, ,滿滿足足非非負負約約束束的的基基解解，稱稱為為基基可可行行解解；1212(,.,.,mNmmnBP PPXxxx在在這這個個基基) )下下，非非基基變變量量（）取取零零值值的的解解稱稱為為基基解解；

49、與與基基可可行行解解對對應應的的基基稱稱為為可可行行基基。12(0)(0)(0)(0)12(,.,.,mTBmBP PPXxxx 此此時時，在在基基) )下下，基基解解為為（, ,0 0, ,0 0, ,. . . ., ,0 0）。)BBXb 對對應應于于基基 下下的的基基解解是是唯唯一一的的（；mnC 為為此此基基解解的的數數目目基基的的數數目目； 基基可可行行解解數數目目基基解解。甲產品乙產品可利用資源原材料23100 噸加工時間42120時單位利潤64百元 例例11某企業生產甲、乙兩種產品，數據見下表。某企業生產甲、乙兩種產品，數據見下表。問：如何安排生產使利潤達最大？問：如何安排生產

50、使利潤達最大？解：設生產甲、乙產品各解：設生產甲、乙產品各12,xx 件件，1）建立模型：）建立模型：121212122310064.42120,0 xxMaxZxxs txxx x ，2）標準化：）標準化：1212312412346423100.42120,0MaxZxxxxxs txxxx x x x 12342 3 1 0,4 2 0 1APPPP 100,6 4 0 0120bC 1234(,)TXxxxx 1x2x3Q (20,20)1223100 xx1242120 xx2Q (50,0)5100Q (0,)31Q (30,0)4Q (0,60)120,0 xx (0,0)O(20

51、,20,0,0)200()TXZ 最最優優解解為為最最優優值值為為百百元元 。12640 xx 12400643xx 1264200 xx 3 3）圖圖解解4）基基，基基向向量量，基基變變量量，非非基基變變量量12342310,4201AP P P P （）112213314423524634(,),(,),(,)LPBP PBP PBP PBP PBP PBP PE 可可以以驗驗證證：) ), ,= =( () ), ,= =( (= =( () ), ,都都為為此此的的基基；12380.42B 比比如如334414232314BNBNXxxXxxXxxXxx=(,)=(,)，=(,)=(,

52、)；=(,)=(,)，=(,)=(,)；112212341324BNBNXxxXxxXxxXxx=(,)=(,)，=(,)=(,)；=(,)=(,)，=(,)=(,)；556624133412BNBNXxxXxxXxxXxx= =( (, ,) )，= =( (, ,) )；= =( (, ,) )，= =( (, ,) )。對對應應的的基基變變量量、非非基基變變量量分分別別為為5)基基解解，基基可可行行解解，可可行行基基1123456T,20 20 0 0BB B B B B BX對對應應基基下下的的基基解解為為：= =( (, , ， ，) )；12342310,4201AP P P P

53、（）100,120b 2T30 0 40 0BX= =( (， ， ，) )；350,0,0, 80BX T T=()=()；5616003BBXX100100=(0=(0， ，) )；3 3=(0,0,100,120)=(0,0,100,120)。31254,Q Q Q Q Q O基基解解分分別別對對應應圖圖解解上上的的點點。135,Q Q Q O其其中中點點為為基基可可行行解解。4T(0,60,80,0)BX= =；1256,B B B B對對應應的的為為可可行行基基。6） 基基最最優優解解，最最優優基基若若基基解解又又是是最最優優解解，則則稱稱之之為為基基最最優優解解，與與之之相相對對應

54、應的的基基稱稱為為最最優優基基。1(20,20,0,0)TB*1XXB = B 最最優優解解為為幾幾何何方方法法得得到到最最優優基基為為。620420200()z 最最優優值值百百元元將以上結論列表如下：將以上結論列表如下：基基基向基向量量基變量基變量基解基解可行基可行基 最優解最優解243121402041312030211001 121314232434,PPPPPPPPPPPP121314232434,xxxxxxxxxxxx(50,0,0,80)(0,60,20,0(20,20,0,0)(30,0,40,0)100160(0,0,)33(0,0,100,120)TTTTTT 2 0 0

55、1 8 04 0 030最優解最優解基最優解基最優解mnC 基基只只有有 （有有限限個個）；BX = b且且對對應應一一個個基基的的基基可可行行解解是是唯唯一一的的（）；一一個個線線性性規規劃劃問問題題的的基基可可行行解解只只有有有有限限個個。解解區區域域第第2節節 線性規劃問題解的理論線性規劃問題解的理論2.1基基本本概概念念(1)(2)(1)(2)1.,(01)nnnnKnXXKXXKK 凸凸集集設設是是 維維歐歐氏氏空空間間的的一一個個點點集集，若若任任意意兩兩點點（1 1有有則則稱稱: :）為為凸凸集集。實實心心圓圓，實實心心球球體體，實實心心立立方方體體等等都都為為凸凸集集，圓圓環環

56、不不是是凸凸集集。直直觀觀上上，凸凸集集沒沒有有凹凹入入部部分分，內內部部沒沒有有空空洞洞 線段線段 (1)(2)XX向向量量與與的的線線性性組組合合(1)(2)()2.,.,.,(01,1,2,.,;1)mnmimii=1XXXnKmim 1 12 2凸凸組組合合設設是是 維維歐歐氏氏空空間間的的 個個點點，若若存存在在使使得得：(1)(2(1)(2)()().,.,mmmXXXXXXXX 1 12 2則則稱稱 為為的的凸凸組組合合。線線性性組組合合(1)(2)(3)3XXXX 1 12 2(1)(2)3.,KXKXXXK 頂頂點點（極極點點）設設 是是凸凸集集，；若若不不能能用用不不同同的

57、的兩兩點點的的線線性性組組合合表表示示為為如如圓圓周周上上的的點點，球球體體表表面面上上的的點點，都都不不能能成成為為任任意意兩兩內內點點連連線線上上的的點點，它它們們是是頂頂點點。(1)(2),(01)XXXKXK（1 1 ）則則稱稱 為為 的的一一個個頂頂點點（極極點點）。頂點頂點不不能能成成為為兩兩內內點點連連線線上上的的點點，稱稱為為頂頂點點。2.2LP幾幾個個定定理理（解解的的性性質質）LPDD定定理理1 1 若若存存在在可可行行域域 ，則則 是是凸凸集集。 ,0DX AXb X 證證設設線線性性規規劃劃問問題題的的可可行行域域為為：(1)(2),DXX對對中中任任意意兩兩個個解解，

58、(1)(2)(1)(2)(1),(01)AXAXXAXAXbbb 有有（1 1 ）= =（1 1 ）(1)(2)AXAXb （）D則則 為為凸凸集集。 證證畢畢。( )R Am 一一般般設設AX = bX0 為方便起見，為方便起見，XD 則則LPXX正正分分量量( (非非零零分分定定理理2 2 量量) )的的可可行行解解 為為基基可可行行解解的的充充要要條條件件是是：的的所所對對應應的的系系數數列列向向量量線線性性無無關關（獨獨立立）。121,.,nXx xx T T證證（） 設設（） 為為基基可可行行解解。X中中非非基基變變量量取取零零值值（由由定定義義知知）X中中非非零零分分量量對對應應的

59、的變變量量為為基基變變量量又又基基變變量量對對應應的的系系數數列列向向量量為為基基向向量量基基可可行行解解非非零零分分量量對對應應的的列列向向量量線線性性無無關關12X,.,kx xx T T設設基基可可行行解解為為 （, , 0 0, ,0 0, ,. . . ., ,0 0 ） 基基變變量量 非非基基變變量量 的的取取值值X 中中非非零零分分量量對對應應的的系系數數列列向向量量線線性性無無關關也許含有零也許含有零( ),R Amkm 又又且且 122X,.,0kc cc T T （ ） 為為方方便便起起見見，設設可可行行解解為為（, ,0 0, ,0 0, ,. . . ., ,0 0）1

60、212,.,.,kkx xxP PP對對應應的的系系數數列列向向量量線線性性無無關關12,.,kmkP PP可可從從其其余余列列向向量量中中取取到到 個個列列向向量量與與構構成成一一個個基基km 當當 時時：X 則則可可行行解解 是是基基可可行行解解可可行行解解的的非非零零分分量量對對應應的的列列向向量量線線性性無無關關基基可可行行解解km 當當時時：12,.,kP PP列列向向量量組組恰恰好好構構成成一一個個基基XX則則：對對應應的的基基解解仍仍為為 ，即即可可行行解解 為為基基可可行行解解。正常數正常數LPX定定理理3 3 的的基基可可行行解解 對對應應于于可可行行域域的的頂頂點點。Xm證