線性規(guī)劃上課課件

線性規(guī)劃概述線性規(guī)劃是運籌學中的重要分支，用于解決資源優(yōu)化配置問題。本課程將深入探討線性規(guī)劃的基本概念、求解方法及應用。線性規(guī)劃的概念定義線性規(guī)劃是在線性約束條件下，求解線性目標函數(shù)最優(yōu)值的數(shù)學方法。特點包括決策變量、目標函數(shù)和約束條件，所有關(guān)系都是線性的。目的在滿足所有約束條件的前提下，找到使目標函數(shù)達到最大或最小值的解。線性規(guī)劃的應用領(lǐng)域生產(chǎn)計劃優(yōu)化產(chǎn)品組合，最大化利潤。物流運輸最小化運輸成本，優(yōu)化路徑選擇。投資組合在風險約束下，最大化投資回報。資源分配合理分配有限資源，提高使用效率。線性規(guī)劃的基本假設(shè)比例性決策變量與其貢獻成正比。可加性總貢獻等于各變量貢獻之和。確定性所有參數(shù)都是已知且固定的。連續(xù)性決策變量可取任意非負實數(shù)。線性規(guī)劃的標準形式目標函數(shù)最大化或最小化線性函數(shù)：Z=c1x1+c2x2+...+cnxn約束條件m個線性不等式或等式：a11x1+a12x2+...+a1nxn≤b1非負約束所有決策變量非負：x1≥0,x2≥0,...,xn≥0線性規(guī)劃的幾何解釋1可行域滿足所有約束條件的點集。2邊界可行域的邊界線或面。3極點可行域的頂點，常包含最優(yōu)解。4等值線目標函數(shù)值相等的點構(gòu)成的直線。圖解法求解線性規(guī)劃繪制約束條件在坐標系中畫出約束直線。確定可行域找出滿足所有約束的區(qū)域。繪制目標函數(shù)等值線畫出目標函數(shù)的等值線。找出最優(yōu)解移動等值線，找到最優(yōu)點。圖解法的局限性1維度限制僅適用于兩個決策變量的問題。2精確度問題圖形解讀可能存在誤差。3復雜性約束條件過多時，圖形變得復雜難辨。4效率低下對于大規(guī)模問題，求解速度慢。單純形法求解線性規(guī)劃1代數(shù)方法2迭代優(yōu)化3基本可行解4最優(yōu)解單純形法是一種代數(shù)方法，通過迭代優(yōu)化基本可行解，最終達到最優(yōu)解。單純形法的基本思想初始基本可行解從可行域的一個頂點開始。移動方向選擇能改善目標函數(shù)值的方向。迭代過程不斷移動到相鄰的更優(yōu)頂點。終止條件當無法找到更優(yōu)解時停止。單純形表的構(gòu)建基變量x1x2s1s2bs1a11a1210b1s2a21a2201b2Z-c1-c2000單純形表的行變換選擇入基變量檢查Z行，選擇最負的系數(shù)對應的變量。確定出基變量計算最小比值，確定離基變量。主元素確定主元素所在行列。高斯-約當消元對單純形表進行行變換。單純形法的解法步驟1構(gòu)建初始單純形表將線性規(guī)劃問題轉(zhuǎn)化為標準形式。2判斷最優(yōu)性檢查Z行是否存在負系數(shù)。3選擇入基和出基變量確定旋轉(zhuǎn)元素。4更新單純形表進行高斯-約當消元。5重復迭代重復步驟2-4直到達到最優(yōu)解。單純形法的終止條件最優(yōu)解Z行所有系數(shù)非負，表示達到最優(yōu)解。無界解入基列全為非正，目標函數(shù)無上界。循環(huán)解在有限個基本可行解間循環(huán)。多重最優(yōu)解Z行存在零系數(shù)，表示有多個最優(yōu)解。雙重單純形法適用情況初始解不可行但目標行系數(shù)非負時使用?；舅枷霃牟豢尚薪忾_始，通過迭代使解可行并最優(yōu)。優(yōu)勢對某些問題比普通單純形法更高效。大M法和兩階段法大M法引入人工變量并賦予極大懲罰系數(shù)M。兩階段法第一階段消除人工變量，第二階段求解原問題。適用情況處理初始基本可行解不易獲得的問題。選擇根據(jù)問題特點和計算效率選擇合適方法。靈敏度分析1參數(shù)變化2影響評估3穩(wěn)定性分析4決策支持靈敏度分析研究參數(shù)變化對最優(yōu)解的影響，為決策提供重要支持。靈敏度分析的概念定義研究線性規(guī)劃參數(shù)變化對最優(yōu)解的影響。目的評估解的穩(wěn)定性和模型的適應性。方法分析目標系數(shù)、約束右端和技術(shù)系數(shù)的變化。意義為決策者提供更全面的信息支持。基變量敏感性分析允許區(qū)間基變量系數(shù)變化不改變最優(yōu)基的范圍。影響分析基變量系數(shù)變化對最優(yōu)解的影響。計算方法利用最終單純形表計算允許區(qū)間。右端常數(shù)敏感性分析1定義分析約束條件右端常數(shù)變化對最優(yōu)解的影響。2影子價格右端常數(shù)變化一個單位引起的目標函數(shù)值變化。3計算利用對偶單純形法或最終單純形表進行分析。4應用評估資源增減對總體效益的影響。目標函數(shù)系數(shù)敏感性分析范圍確定確定目標函數(shù)系數(shù)的允許變化范圍。平衡點分析系數(shù)變化導致最優(yōu)解改變的臨界點。趨勢分析研究系數(shù)變化對最優(yōu)解的影響趨勢。決策支持為產(chǎn)品定價和資源配置提供決策依據(jù)。整數(shù)規(guī)劃概述定義要求部分或全部決策變量為整數(shù)的線性規(guī)劃。分類純整數(shù)規(guī)劃、混合整數(shù)規(guī)劃和0-1整數(shù)規(guī)劃。特點解空間離散，求解復雜度高。意義更貼近現(xiàn)實中的離散決策問題。整數(shù)規(guī)劃的應用領(lǐng)域整數(shù)規(guī)劃廣泛應用于生產(chǎn)計劃、運輸調(diào)度、庫存管理、項目規(guī)劃和投資決策等領(lǐng)域。整數(shù)規(guī)劃求解方法1枚舉法2分支定界法3割平面法4隱枚舉法5啟發(fā)式算法整數(shù)規(guī)劃的求解方法從簡單到復雜，適用于不同規(guī)模和特點的問題。枚舉法原理遍歷所有可能的整數(shù)解，找出最優(yōu)解。優(yōu)點簡單直觀，保證找到全局最優(yōu)解。缺點計算量大，僅適用于小規(guī)模問題。改進可結(jié)合其他方法進行剪枝，提高效率。分支定界法松弛問題求解線性規(guī)劃松弛問題。分支選擇非整數(shù)變量進行分支。定界計算各子問題的界限。剪枝剪去不可能包含最優(yōu)解的分支。切平面法基本思想通過添加切平面約束，逐步逼近整數(shù)解。Gomory割最常用的切平面生成方法。優(yōu)缺點理