資源描述：
《線 性 規(guī) 劃》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、線性規(guī)劃LinearPrograming運籌學基本內容線性規(guī)劃的基本性質及其圖解法單純形法對偶問題靈敏度分析第一章線性規(guī)劃的基本性質線性規(guī)劃問題及模型二維線性規(guī)劃的求解：圖解法線性規(guī)劃的標準形式線性規(guī)劃問題解及其性質線性規(guī)劃研究問題主要研究解決有限資源的最佳分配問題，即如何對有限資源作出最佳方式的調配和最有力地使用，以便最充分地發(fā)揮資源的效能，以獲取最佳的經濟效益。生產計劃問題運輸問題配料問題下料問題食譜問題產品配套問題(1)生產計劃問題應如何安排生產這兩種產品才能獲利最多？產品車間單耗（工時/件）生產能力（工時/天）甲乙A108B0212C3436利潤（百元/件）3
2、5問題分析數學模型為(2)運輸問題設兩個糧庫供應三個糧店，供應量、需求量和運費如下表所示，問如何安排運輸計劃，可使總運費最少？建立數學模型糧店單價（百元）糧庫B1B2B3供應量（噸）A118252028A221222429需求量（噸）121530問題分析數學模型(3)配料問題某化工廠根據一項合同要為用戶生產一種用甲、乙兩種原料混合配制而成的特殊產品。甲、乙兩種原料都含有A、B、C三種化學成分，其含量以及產品中各成分含量的最低量如下表所示。甲、乙兩種原料成本見下表。廠方希望總成本大到最小，則應如何配制該產品。原料成分成份含量（%）產品成分最低含量（%）甲乙A1234B2
3、32C3155成本(元/千克)32問題分析數學模型線性規(guī)劃問題的特點1、（非負的）決策變量2、求極值的目標函數3、線性的約束條件一般模型線性規(guī)劃的圖解maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目標函數等值線最優(yōu)點（最優(yōu)解）64-860x1x2圖解法的步驟可行域圖形地確定所有約束條件共同構成的圖形成為可行域可行域所有點（包括邊界）均是可行解目標函數的等值線與最優(yōu)點的確定令Z取不同值，得到一組平行的等值線沿目標函數值增大的方向移動等值線，當韓淑芝最大時與可行域的交點即為最優(yōu)點。最優(yōu)點的求解在圖上觀測最優(yōu)點的坐標通過解方程組得出最
4、優(yōu)點坐標值可行域的幾種情況無界域x1+2x2?4s.t.x1-2x2?5x1,x2?014235123x1x2x1+2x2?4x1-2x2?5可行域的幾種情況有界域2846102410x13x1+4x2?36x1≤812682x2?12可行域的幾種情況空集s.t.x1+2x2≤4x1-2x2≥5x1,x2≥014235123x1x2x1+2x2≤4x1-2x2≥5最優(yōu)點的幾種情況唯一解多重解無界解無可行解線性規(guī)劃的多重解maxz=x1+x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目標函數等值線最優(yōu)點（最優(yōu)解）64-860x1x2maxz=2x1
5、+x2s.t.x1+x2?2x1-2x2?0x1,x2?0線性規(guī)劃無界解14235123x1x2x1+x2?2z=2x1+x2x1-2x2?0無可行解Maxz=x1+x2s.t.x1+2x2≤4x1-2x2≥5x1,x2≥014235123x1x2x1+2x2≤4x1-2x2≥5Z=x1+x2線性規(guī)劃的標準形式線性規(guī)劃標準型的簡寫形式求和符號形式線性規(guī)劃標準型的簡寫形式向量形式線性規(guī)劃標準型的簡寫形式矩陣形式線性規(guī)劃標準型的簡寫形式集合形式線性規(guī)劃的模型線性規(guī)劃模型的結構目標函數：max，min約束條件：≥,=,≤變量符號：：≥0,unr,≤0線性規(guī)劃的標準形式目標函
6、數：max約束條件：=變量符號：≥0非標準形LP問題的標準化例題非標準形LP問題的標準化目標函數最小化最大化：z’=-z不等式約束等式約束變量為負約束、無符號約束非負約束右端常數小于零非負等式兩邊均乘-1松弛變量剩余變量練習:將下列線性規(guī)劃問題化成標準型1、minZ=5x1+x2+x33x1+x2-x3≤7-3x1+x2≤6s.tx1+2x2≤4x2≥-3,x1無限制,x3≤02、maxZ=-x1+4x2s.tx1-2x2+4x3≥-6x2+3x3=3x1,x2≥0,x3無限制線性規(guī)劃問題的解及其性質1.線性規(guī)劃的解2.線性規(guī)劃的基與基本可行解3.線性規(guī)劃的基本定理線
7、性規(guī)劃解的定義(1)滿足線性規(guī)劃問題所有約束條件的解是該問題的可行解。X=(X1,X2,…,XN)T(2)線性規(guī)劃問題全部可行解的集合構成線性規(guī)劃問題的可行域（或稱可行解集）。R={x?Ax=b,x?0}(3)使目標函數達到極值的可行解稱為線性規(guī)劃問題的最優(yōu)解。(4)若對任意大的M?0，都存在可行解使得該線性規(guī)劃的目標函數值?z?=?cx??M,則該線性規(guī)劃問題無界。線性規(guī)劃的基與基本可行解基的定義：給定線性規(guī)劃問題P：max{cx
8、Ax=b,x?0}A是m?n滿秩矩陣,n>m，如果B是其中任一個m?m滿秩子矩陣，則稱B是P的一個基?；兞颗c非基變量
