線性代數(shù)課件：線性規(guī)劃

——線性規(guī)劃線性代數(shù)引

言如何以最低成本（如人力、物力、資金和時間等）去完成這一任務；1如何在現(xiàn)有資源條件下進行組織和安排，以產(chǎn)生最大收益。2線性規(guī)劃作為運籌學的一個重要分支，是研究在一組線性約束條件下，某一個線性函數(shù)的最大值或最小值問題。主要包括兩個方面：產(chǎn)品\資源ABC每噸經(jīng)濟價產(chǎn)品甲3407產(chǎn)品乙2675資源總量90200210線性規(guī)劃模型引例1生產(chǎn)決策問題某廠生產(chǎn)甲乙兩種產(chǎn)品，已知制成一噸產(chǎn)品甲需要用資源A3噸，資源B4m3;制成一噸產(chǎn)品乙需要用資源A2噸，資源B6m3，C資源7個單位。若一噸甲和一噸乙的經(jīng)濟價值分別為7萬元和5萬元，三種資源分別為90噸、200m3和210個單位，試決定應生產(chǎn)這兩種產(chǎn)品各多少噸才能創(chuàng)造總經(jīng)濟價值最高？線性規(guī)劃模型解確定決策變量（假設自變量）生產(chǎn)產(chǎn)品甲的數(shù)量

（噸）生產(chǎn)產(chǎn)品乙的數(shù)量（噸）1確定目標函數(shù)以Z表示生產(chǎn)甲和乙兩種產(chǎn)品各為和時產(chǎn)生的經(jīng)濟價值，則有：2max線性規(guī)劃模型解尋找約束條件資源A限制：資源B限制：資源C限制：非負條件：3建立數(shù)學模型4線性規(guī)劃模型引例2加工任務分配問題某車間有兩臺機床甲和乙，可用于加工三種工件。假定這兩臺機床的可用臺時數(shù)分別為700和800，三種工件的數(shù)量分別為300、500和400，且已知用不同機床加工單位數(shù)量的不同工件所需的臺時數(shù)和加工費用（見表），問怎樣分配機床的加工任務才能既滿足加工工件的要求，又使總加工費用最低？車床類型單位工件所需加工臺時數(shù)單位工件的加工費用可用臺時數(shù)工件1工件2工件3工件1工件2工件3甲0.41.11.013910700乙0.51.21.311128800線性規(guī)劃模型解確定決策變量設甲車床上加工工件1、2、3的數(shù)量分別為在乙車床上加工工件1、2、3的數(shù)量分別為1確定目標函數(shù)以Z表示加工的費用，則有：2線性規(guī)劃模型解尋找約束條件加工1中的數(shù)量：加工2中的數(shù)量：加工3中的數(shù)量：用到甲的臺數(shù)：用到乙的臺數(shù)：非負條件：3線性規(guī)劃模型解建立數(shù)學模型4線性規(guī)劃模型線性規(guī)劃模型的步：確定目標函數(shù)決策變量的線性函數(shù)確定決策變量尋找約束條件線性關系式（等式或不等式）決策變量的非負寫出線性規(guī)劃模型1234線性規(guī)劃模型LP模型的一般形式：線性規(guī)劃模型LP模型的一般形式：目標函數(shù)為最小值形式；約束條件用等式表示；約束條件等式右側(cè)非負；決策變量非負．特點LP模型的標準型線性規(guī)劃模型約束矩陣:則矩陣形式為：記

線性規(guī)劃模型LP模型的標準型化標準型如果目標函數(shù)是極大值問題則令目標函數(shù)的轉(zhuǎn)換1線性規(guī)劃模型約束條件的轉(zhuǎn)換2(iii)原問題：無非負約束，則令(i)原問題條件：稱為松弛變量。(ii)原問題條件：稱為剩余變量。線性規(guī)劃模型例將下述線性規(guī)劃模型化為標準型。線性規(guī)劃