運籌學b-第1章線性規劃課件目錄CONTENTS線性規劃概述線性規劃數學模型圖形解法與幾何意義單純形法原理及步驟對偶理論與靈敏度分析運輸問題與指派問題整數規劃與混合整數規劃01線性規劃概述0102線性規劃定義線性規劃問題可以表示為一系列線性不等式或等式約束下的線性目標函數最大化或最小化問題。線性規劃是一種數學方法，旨在通過優化線性目標函數，在滿足一系列線性約束條件的情況下，找到最優解。線性規劃的起源可以追溯到20世紀30年代，當時經濟學家試圖解決資源分配和生產計劃等問題。1947年，美國數學家丹齊格提出了單純形法，為線性規劃問題的求解提供了有效方法，推動了線性規劃理論的發展和應用。隨著計算機技術的發展，線性規劃在20世紀60年代后得到了廣泛應用，成為運籌學的重要分支。線性規劃發展歷程交通運輸0102030405線性規劃可用于制定生產計劃，確定各種產品的最優生產量，以滿足市場需求并實現成本最小化。在資源有限的情況下，線性規劃可用于優化資源分配，如人力資源、物資資源、資金等。線性規劃在經濟管理領域有廣泛應用，如市場營銷策略、投資決策、財務分析等。線性規劃可用于解決交通運輸問題，如車輛路徑規劃、貨物配送優化等。除了上述領域外，線性規劃還可應用于環境科學、能源工程、生物醫學等多個領域。線性規劃應用領域資源分配生產計劃其他領域經濟管理02線性規劃數學模型線性規劃的目標函數是決策者希望達到的目標，通常表示為決策變量的線性函數，形如Z=c1x1+c2x2+...+cnxn。目標函數約束條件是限制決策變量取值的條件，通常表示為決策變量的線性不等式或等式，形如ax≤b或ax=b。約束條件目標函數與約束條件決策變量是線性規劃中的未知數，表示決策者可以控制的因素，通常用x1,x2,...,xn表示。滿足所有約束條件的決策變量取值稱為可行解，所有可行解構成的集合稱為可行域。決策變量與可行解可行解決策變量標準形式轉化為標準形式線性規劃標準形式對于非標準形式的線性規劃問題，可以通過引入松弛變量、剩余變量和人工變量等方法，將其轉化為標準形式進行求解。線性規劃的標準形式是指目標函數為最大化（或最小化）形式，約束條件為等式形式，且所有決策變量非負的線性規劃問題。03圖形解法與幾何意義在二維平面上，滿足所有約束條件的點集構成的區域。可行域目標函數最優解需要優化的函數，在二維平面上表示為一條直線。目標函數在可行域上的最優值對應的點。030201二維平面圖形解法圖形解法的步驟繪制約束條件對應的直線或曲線，確定可行域。繪制目標函數對應的直線，并平移至與可行域相切的位置。切點即為最優解，對應的函數值即為最優值。01020304二維平面圖形解法

高維空間圖形解法高維空間中的可行域滿足所有約束條件的點集構成的高維空間區域。高維空間中的目標函數需要優化的函數，在高維空間中表示為一個超平面。高維空間中的最優解目標函數在可行域上的最優值對應的點。圖形解法的步驟繪制目標函數對應的超平面，并平移至與可行域相切的位置。繪制約束條件對應的高維空間圖形，確定可行域。切點即為最優解，對應的函數值即為最優值。高維空間圖形解法1234線性規劃問題的幾何意義最優解在可行域的頂點上達到可行域是凸集對偶性幾何意義及性質在幾何上，線性規劃問題可以看作是在高維空間中尋找一個點，使得該點到某個超平面的距離最大或最小。這個超平面由目標函數確定，而約束條件則限定了尋找點的范圍。線性規劃問題的可行域是由一系列線性不等式圍成的區域，因此是一個凸集。這意味著如果兩個點在可行域內，則它們之間的任何點也在可行域內。由于可行域是凸集，目標函數在可行域上的最優值一定在可行域的某個頂點上達到。因此，在求解線性規劃問題時，只需要考慮可行域的頂點即可。每一個線性規劃問題都有一個與之對應的對偶問題。對偶問題的解與原問題的解密切相關，可以通過求解對偶問題來間接求解原問題。04單純形法原理及步驟可行解與基本解在標準形式下，滿足所有約束條件的解稱為可行解；基本解則是對應基變量的取值。最優性條件通過比較目標函數值，確定最優解的存在性和唯一性。線性規劃問題的標準形式通過引入松弛變量和剩余變量，將一般形式的線性規劃問題轉化為標準形式。單純形法基本原理初始基可行解的確定迭代過程終止條件單純形法計算步驟通過構造初始單純形表，找到一組基可行解作為起點。根據最優性檢驗和入基變量的選擇，進行迭代計算，逐步改進基可行解。當迭代過程中無法找到新的入基變量或已達到最優解時，算法終止。優點單純形法是一種成熟且高效的求解線性規劃問題的方法，具有嚴格的數學理論基礎和廣泛的應用范圍。缺點對于大規模問題，單純形法可能面臨計算量大、內存占用高等挑戰；此外，對于某些特殊結構的問題，單純形法可能不是最優的求解方法。單純形法優缺點分析05對偶理論與靈敏度分析對偶問題定義01對于原線性規劃問題，可以構造一個與之對應的新問題，使得原問題的任一可行解對應新問題的一個可行解，且兩者目標函數值相等。這個新問題稱為原問題的對偶問題。弱對偶性02原問題的任一可行解的目標函數值不小于對偶問題的任一可行解的目標函數值。強對偶性03若原問題有最優解，則對偶問題也有最優解，且兩者目標函數最優值相等。對偶問題定義及性質通過構造原問題的對偶單純形表，利用迭代方法求解對偶問題的最優解。單純形法通過引入對數障礙函數，將原問題轉化為一個無約束優化問題，然后利用牛頓法等迭代方法求解。內點法基于橢球體的幾何性質，通過不斷縮小包含可行域的橢球體來逼近最優解。橢球法對偶問題求解方法01020304靈敏度分析概念生產計劃調整資源分配優化投資決策支持靈敏度分析概念及應用研究線性規劃問題中參數變化對最優解的影響程度。通過靈敏度分析，可以了解哪些參數的變化會導致最優解的改變以及變化范圍。當生產成本、市場需求等參數發生變化時，通過靈敏度分析可以及時調整生產計劃，保持最優生產狀態。在投資決策中，通過靈敏度分析可以評估不同投資方案的風險和收益，為決策者提供科學依據。在資源有限的條件下，通過靈敏度分析可以合理分配資源，使得目標函數達到最優。06運輸問題與指派問題運輸問題模型建立根據實際問題背景，確定供應地、需求地以及各自的供應量與需求量，構建運輸問題的數學模型。求解方法采用表上作業法，通過尋找初始基可行解、最優性檢驗和調整運輸方案等步驟，求得運輸問題的最優解。運輸問題模型及求解方法根據實際問題背景，確定工作人數、任務數以及每個人完成各項任務所需的時間或成本，構建指派問題的數學模型。指派問題模型建立采用匈牙利算法，通過變換系數矩陣、試指派和調整等步驟，求得指派問題的最優解。求解方法指派問題模型及求解方法03某項工作一定由某人完成的指派問題將該工作只能由該人完成的限制條件加入到模型中，然后進行求解。01人數和工作數不等的指派問題通過添加虛擬的工作或人，將問題轉化為人數和工作數相等的標準指派問題進行處理。02一個人可做多項工作的指派問題將該人的多項工作看作不同的工作，分別計算時間和成本，然后按照標準指派問題進行求解。特殊類型指派問題處理技巧07整數規劃與混合整數規劃整數規劃是要求決策變量取整數值的線性規劃問題。根據問題要求的不同，可分為純整數規劃、混合整數規劃和0-1整數規劃。整數規劃模型整數規劃的求解方法主要有分支定界法、割平面法和隱枚舉法等。其中，分支定界法是一種常用的求解方法，通過不斷將問題分解為子問題并求解，逐步縮小問題的范圍，最終找到最優解。求解方法整數規劃模型及求解方法混合整數規劃模型及求解方法混合整數規劃模型混合整數規劃是指部分決策變量取整數值，部分決策變量取連續值的線性規劃問題。在實際問題中，混合整數規劃的應用非常廣泛。求解方法混合整數規劃的求解方法類似于整數規劃，主要采用分支定界法、割平面法和隱枚舉法等。其中，分支定界法在處理混合整數規劃問題時同樣有效。分支定界法割平面法分支定界法和割平面法介紹分支定界法是一種求解整數規劃和混合整數規劃的常用方法。該方法通過不斷將問題分解為子問題并求解，逐步縮小問題的范圍，最終找到最優解。在分支過程中，根據問題的特點選擇合適的分支策略，如二分法、最