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

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

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

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

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