線性規(guī)劃圖解法經(jīng)典運(yùn)籌學(xué)_第1頁(yè)
線性規(guī)劃圖解法經(jīng)典運(yùn)籌學(xué)_第2頁(yè)
線性規(guī)劃圖解法經(jīng)典運(yùn)籌學(xué)_第3頁(yè)
線性規(guī)劃圖解法經(jīng)典運(yùn)籌學(xué)_第4頁(yè)
線性規(guī)劃圖解法經(jīng)典運(yùn)籌學(xué)_第5頁(yè)
已閱讀5頁(yè),還剩50頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、編輯ppt上堂課主要內(nèi)容:一、線性規(guī)劃模型引例二、線性規(guī)劃模型的建立 編輯ppt 1、建模的一般步驟: 步驟一:確定決策變量 即用變量取不同的值來(lái)表示可供選擇的各種不同方案步驟二:建立目標(biāo)函數(shù) 即找到目標(biāo)值與決策變量的數(shù)量關(guān)系步驟三:確定約束條件即決策變量所受到的外界條件的制約。約束條件一般為決策變量的等式或不等式要求:目標(biāo)函數(shù)與約束條件均是線性的, 且目標(biāo)函數(shù)只能是一個(gè)。編輯ppt2、線性規(guī)劃模型的一般形式:nnxcxcxcz2211minmax)(或mnmnmmnnnnbxaxaxabxaxaxabxaxaxats),或或),或或),或或(.22112222212111212111為已知常

2、數(shù)其中),2, 1;,2, 1(,njmicbajiij0,21nxxx決策變量約束方程非負(fù)約束 目標(biāo)函數(shù)編輯ppt三、線性規(guī)劃求解:四、線性規(guī)劃應(yīng)用舉例nnxcxcxcz2211minmax)(或mnmnmmnnnnbxaxaxabxaxaxabxaxaxat s),或或),或或),或或(.221122222121112121110,21nxxx計(jì)算機(jī)應(yīng)用軟件編輯ppt時(shí)間所需售貨員 人數(shù)星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3 福安商場(chǎng)是個(gè)中型的百貨商場(chǎng),它對(duì)售貨人員的 需求經(jīng)過(guò)統(tǒng)計(jì)分析如下所示:為保證售貨人員充分休息,售貨人員每周工作五天,

3、休息兩天,并要求休息的兩天是連續(xù)的,問(wèn)應(yīng)該如何安排售貨人員的作息,既滿足了工作的需要,又使配備的售貨人員的人數(shù)最少?解,為周二開(kāi)始休息的人數(shù),為周一開(kāi)始休息的人數(shù)設(shè)21xx,為周日開(kāi)始休息的人數(shù),為周六開(kāi)始休息的人數(shù)76xx表示商場(chǎng)的售貨員人數(shù)Z721xxx721minxxxZ求編輯ppt2854321xxxxx時(shí)間所需售貨員人數(shù)星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人約束條件 :星期日 售貨員人數(shù)要求: 1565432xxxxx星期一 售貨員人數(shù)要求: 2476543xxxxx星期二 售貨員人數(shù)要求: 2576541xxxxx星期三 售貨員人數(shù)要求

4、: 1976521xxxxx星期四 售貨員人數(shù)要求: 3176321xxxxx星期五 售貨員人數(shù)要求: 2874321xxxxx星期六 售貨員人數(shù)要求: 數(shù)學(xué)模型:721minxxxZ求ts.非負(fù)約束 :7 , 2 , 1, 0ixi2854321xxxxx1565432xxxxx2476543xxxxx2576541xxxxx1976521xxxxx3176321xxxxx2874321xxxxx7 , 2 , 1, 0ixi7 , 2 , 1,iixi日開(kāi)始休息的人數(shù)為星期編輯ppt數(shù)學(xué)模型:721minxxxZ求ts.2854321xxxxx1565432xxxxx2476543xxxx

5、x2576541xxxxx1976521xxxxx3176321xxxxx2874321xxxxx7 , 2 , 1, 0ixi解得: 36. 0, 8, 0, 5,11, 0,1207654321Zxxxxxxx編輯ppt時(shí)間所需售貨員 人數(shù)星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3 福安商場(chǎng)是個(gè)中型的百貨商場(chǎng),它對(duì)售貨人員的 需求經(jīng)過(guò)統(tǒng)計(jì)分析如下所示:為保證售貨人員充分休息,售貨人員每周工作五天,休息兩天,并要求休息的兩天是連續(xù)的,問(wèn)應(yīng)該如何安排售貨人員的作息,既滿足了工作的需要,又使配備的售貨人員的人數(shù)最少?解,為周二開(kāi)始休息的人數(shù),為周一開(kāi)

6、始休息的人數(shù)設(shè)21xx,為周日開(kāi)始休息的人數(shù),為周六開(kāi)始休息的人數(shù)76xx表示商場(chǎng)的售貨員人數(shù)Z36. 0, 8, 0, 5,11, 0,1207654321Zxxxxxxx解得:編輯ppt方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合計(jì)7.4m7.3m7.2m7.1m6.6下角料0m0.1m0.2m0.3m0.8m方案下料數(shù)(根)長(zhǎng)度例4 某工廠要做100套鋼架,每套用長(zhǎng)為2.9m,2.1m, 和1.5m的圓鋼各一根,已知原料每根長(zhǎng)7.4m, 問(wèn)應(yīng)如何下料,可使所用原料最省.分析:每根原料做一套鋼架, 下角料: 0.9m用套裁方式下料方案:編輯ppt方

7、案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合計(jì)7.4m7.3m7.2m7.1m6.6下角料0m0.1m0.2m0.3m0.8m方案下料數(shù)(根)長(zhǎng)度下料方案:)5 , 4 , 3 , 2 , 1iixi數(shù)(第種方案下料的原料根為按解:設(shè)表示總用料數(shù)Z數(shù)學(xué)模型:54321minxxxxxZ求ts.1002421xxx10022543xxx1003235321xxxx. 0, 0, 0, 0, 054321xxxxx編輯ppt方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合計(jì)7.4m7.3m7.2m7.1m6.6下角料0m

8、0.1m0.2m0.3m0.8m方案下料數(shù)(根)長(zhǎng)度例4 某工廠要做100套鋼架,每套用長(zhǎng)為2.9m,2.1m, 和1.5m的圓鋼各一根,已知原料每根長(zhǎng)7.4m, 問(wèn)應(yīng)如何下料,可使所用原料最省.下料方案:90. 0, 05, 0, 01,30054321Zxxxxx最優(yōu)值最優(yōu)解:)5 , 4 , 3 , 2 , 1iixi數(shù)(第種方案下料的原料根為按總用料數(shù)Z最優(yōu)下料方案: 按方案1下料30根, 方案2下料10根,方案4下料50根,共需原料90根。編輯ppt例5 (產(chǎn)品配套問(wèn)題)假定一個(gè)工廠的甲、乙、丙三個(gè)車間生產(chǎn)同一個(gè)產(chǎn)品,每件產(chǎn)品包括4個(gè)A零件,和3個(gè)B零件。這兩種零件由兩種不同的原材料

9、制成,而這兩種原材料的現(xiàn)有數(shù)額分別為100克和200克。每個(gè)生產(chǎn)班的原材料需要量和零件產(chǎn)量如下表所示。 每班進(jìn)料數(shù)(克)每班產(chǎn)量(個(gè)數(shù))第1種原材料第2種原材料A零件B零件甲8675乙5969丙3884車間問(wèn)這三個(gè)車間各應(yīng)開(kāi)多少班才能使這種產(chǎn)品的配套數(shù)達(dá)到最大車間所開(kāi)的生產(chǎn)班數(shù)分別是甲、乙、丙三個(gè),解:設(shè)321xxx產(chǎn)品的配套數(shù)z約束條件為:100358321xxx200896 ,321xxx000321xxx,編輯ppt三個(gè)車間共生產(chǎn)A零件:321867xxx三個(gè)車間共生產(chǎn)B零件321495xxx4867321xxxminz則3495,321xxx非線性表示生產(chǎn)出的產(chǎn)品數(shù)設(shè)4x要求: 每班進(jìn)

10、料數(shù)(克)每班產(chǎn)量(個(gè)數(shù))第1種原材料第2種原材料A零件B零件甲8675乙5969丙3884車間車間所開(kāi)的生產(chǎn)班數(shù)分別是甲、乙、丙三個(gè),321xxx產(chǎn)品的配套數(shù)z目標(biāo)函數(shù):目標(biāo)函數(shù) Z=x4線性43214867xxxx43213495,xxxx編輯ppt數(shù)學(xué)模型:100358321xxx200896321xxx. 0, 0004321xxxx,4maxxz 線性規(guī)劃問(wèn)題t s.048674321xxxx034954321xxxx編輯ppt例6 (多周期動(dòng)態(tài)生產(chǎn)計(jì)劃問(wèn)題)華津機(jī)器制造廠專為拖拉機(jī)廠配套生產(chǎn)柴油機(jī),今年頭四個(gè)月收到的定單數(shù)量分別為3000臺(tái)、4500臺(tái)、3500臺(tái)、5000臺(tái)。該廠

11、正常生產(chǎn)每月可生產(chǎn)3000臺(tái),利用加班還可生產(chǎn)1500臺(tái),正常生產(chǎn)成本為每臺(tái)5000元,加工生產(chǎn)還要追加1500元,庫(kù)存成本為每臺(tái)每月200元。問(wèn)華津廠如何組織生產(chǎn)才能使生產(chǎn)成本最低?分析:設(shè)C=成本 =四個(gè)月正常生產(chǎn)的成本+四個(gè)月加班生產(chǎn)的成本 +四個(gè)月庫(kù)存成本臺(tái)柴油機(jī)個(gè)月正常生產(chǎn)設(shè)第ixi臺(tái)柴油機(jī)加班生產(chǎn)iy,臺(tái)柴油機(jī)個(gè)月初庫(kù)存第izi4 , 3 , 2 , 1iC則415000iix416500iiy41200iiz41)20065005000(iiiizyx約束條件:編輯ppt臺(tái)柴油機(jī)個(gè)月正常生產(chǎn)設(shè)第ixi臺(tái)柴油機(jī)加班生產(chǎn)iy,臺(tái)柴油機(jī)個(gè)月初庫(kù)存第izi01z其中4 , 3 , 2 ,

12、 1i需求約束:第4個(gè)月5000444zyx第3個(gè)月35004333zzyx第2個(gè)月45003222zzyx第1個(gè)月3000211zyx生產(chǎn)能力約束:4 , 3 , 2 , 13000ixi4 , 3 , 2 , 11500iyi數(shù)學(xué)模型:ts.4 ,3 , 2 , 1,0,izyxiii41)20065005000(miniiiizyxC5000444zyx35004333zzyx45003222zzyx3000211zyx4 , 3 , 2 , 13000ixi4 , 3 , 2 , 11500iyi四個(gè)月定單數(shù)量分別為3000臺(tái)、4500臺(tái)、3500臺(tái)、5000臺(tái)每月可生產(chǎn)3000臺(tái),利

13、用加班還可生產(chǎn)1500臺(tái)庫(kù)存約束:01z01z編輯ppt例7.連續(xù)投資問(wèn)題建模:某投資公司有100萬(wàn)元資金用于投資,投資的方案可以有以下六種,現(xiàn)要做一個(gè)5年期的投資計(jì)劃,具體可選擇的投資方案如下:方案A:5年內(nèi)的每年年初均可投資,且金額不限,投資期限1 年,年投資回報(bào)率7%。方案B:5年內(nèi)的每年年初均可投資,且金額不限,投資期限2 年,年投資回報(bào)率10%(不計(jì)復(fù)利)。方案C:5年內(nèi)的每年年初均可投資,且金額不限,投資期限3 年,年投資回報(bào)率12%(不計(jì)復(fù)利)方案D:只在第一年年初有一次投資機(jī)會(huì),最大投資金額為50 萬(wàn)元,投資期限4年,年投資回報(bào)率20%方案E:在第二年和第四年年初有一次投資機(jī)會(huì)

14、,最大投資金額 均為30萬(wàn)元,投資期限1年,年投資回報(bào)率30%方案F:在第四年年初有一次投資機(jī)會(huì),金額不限,投資期限2 年,年投資回報(bào)率25%假設(shè)當(dāng)年的投資金額及其收益均可用于下一年的投資,問(wèn)公司應(yīng)如何投資才能使第五年末收回的資金最多?編輯ppt假設(shè)當(dāng)年的投資金額及其收益均可用于下一年的投資,問(wèn)公司應(yīng)如何投資才能使第五年末收回的資金最多?所投資的金額,年初按方按分別表示第解:設(shè)FEDCBAiiFEDCBAiiiiii)5 , 4 , 3 , 2 , 1(,年末收回的總資金第5Z第一年初 第二年初 第三年初 第四年初 第五年初 第五年末1A107. 1A207. 1A307. 1A407. 1A

15、5A507. 1A1B12.1B22 . 1B32 . 1B42 . 1B1C136.1C236. 1C3A3B3C336. 1C1D18 .1D2A2B2C2E23 . 1E43 . 1E4A4B4E4F45 . 1E編輯ppt544307. 15 . 12 . 136. 1maxAFBCz求10000001111DCBA007. 112222AECBA03 . 107. 12 . 1211333EABCBA007. 12 . 136. 11214344ABCFEBA03 . 107. 12 . 136. 18 . 1413215EABCDA5000001D3000002E3000004E)

16、5 , 4 , 3 , 2 , 1(0,iFEDCBAiiiiiit s.連續(xù)投資問(wèn)題模型:編輯ppt1.1.2、線性規(guī)劃的標(biāo)準(zhǔn)形式和矩陣表達(dá)式線性規(guī)劃問(wèn)題的一般形式:nnxcxcxcz2211minmax)(或mnmnmmnnnnbxaxaxabxaxaxabxaxaxat s),或或),或或),或或(.22112222212111212111為已知常數(shù)其中),2, 1;,2, 1(,njmicbajiij0,21nxxx編輯ppt1、線性規(guī)劃的標(biāo)準(zhǔn)形式nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxats22112222212111212111.

17、0,21nxxx0,21mbbbniiixcz1maxnijijibxa1mj, 2 , 1nixi, 2 , 10mjbj, 2 , 10niiixcz1max即nijijibxats1.mjbj, 2 , 10nixi, 2 , 10編輯pptnnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxats22112222212111212111.0,21nxxx0,21mbbb標(biāo)準(zhǔn)型式的特征:1、求目標(biāo)函數(shù)的最大值2、約束方程為等式方程3、約束方程的右邊非負(fù)4、決策變量均非負(fù)非標(biāo)準(zhǔn)型式有以下幾種可能:1、求目標(biāo)函數(shù)的最小值4、決策變量0,都存在可行解使得

18、該線性規(guī)劃的目標(biāo) 函數(shù)值MZ ,則稱該線性規(guī)劃問(wèn)題無(wú)界編輯ppt二、兩個(gè)變量的線性規(guī)劃的圖解法0,3482.52max121212121xxxxxxtsxxz劃用圖解法解以下線性規(guī)例解: (1)在直角坐標(biāo)系上畫(huà)出可行域(2)做目標(biāo)函數(shù)的等值線3*,2*)4(21xx最優(yōu)解為193522*z最優(yōu)值01x2x.8221xx41x32x可行域kxx2152105221 xx求交點(diǎn):) 3(382221xxx)3 , 2(),(21xx凸多邊形頂點(diǎn).編輯ppt0,3482.2max221212121xxxxxxtsxxz劃用圖解法解以下線性規(guī)例解: (1)在直角坐標(biāo)系上畫(huà)出可行域(2)做目標(biāo)函數(shù)的等值

19、線8*)3(z最優(yōu)值01x2x.8221xx41x32x2221xx求交點(diǎn):382221xxx)3 , 2(),(21xx2221xx482121xxx) 2 , 4(),(21xx)之間的所有點(diǎn)。,)與點(diǎn)(,上界于點(diǎn)(最優(yōu)解:直線24328221xx無(wú)窮多.編輯ppt0,4422.32max321212121xxxxxxtsxxz劃用圖解法解以下線性規(guī)例解: (1)在直角坐標(biāo)系上畫(huà)出可行域(2)做目標(biāo)函數(shù)的等值線01x2x.2221 xx63221xx4421xx目標(biāo)函數(shù)無(wú)上界,該問(wèn)題無(wú)界無(wú)最優(yōu)解編輯ppt0,43222.32max4212212121xxxxxxxtsxxz劃用圖解法解以下

20、線性規(guī)例解: (1)在直角坐標(biāo)系上畫(huà)出可行域01x2x.3221 xx42x2221xx可行域?yàn)榭占療o(wú)可行解該問(wèn)題無(wú)最優(yōu)解編輯ppt圖解法的基本步驟:的圖形上做出可行域、在直角坐標(biāo)系Soxx211(一般是一個(gè)凸多邊形),2k給定的常數(shù)、令目標(biāo)函數(shù)值取一個(gè)kxcxcZ2211做等值線,max3由小變大問(wèn)題,令目標(biāo)函數(shù)值、對(duì)k即讓等值線向上平移,點(diǎn)邊界線上的點(diǎn)均是最優(yōu)的一條邊界重合,此時(shí)若與點(diǎn),則該點(diǎn)就是所求的最優(yōu)的一個(gè)頂點(diǎn)),是最后交于一個(gè)點(diǎn)(一般若它與可行域SSS,即得最優(yōu)解立求解,邊界線所代表的方程聯(lián)、將最優(yōu)點(diǎn)所在的兩條*4X*CXZX值帶入目標(biāo)函數(shù),得最優(yōu)把最優(yōu)解注意:若是求目標(biāo)函數(shù)的最小

21、值, 目標(biāo)函數(shù)直線向下移動(dòng)編輯ppt關(guān)于線性規(guī)劃解的結(jié)論:1、若(LP)問(wèn)題有可行解,則可行域是一個(gè)凸多邊形(或凸多面體)。它可能是有界的;也可能是無(wú)界的。2、若(LP)問(wèn)題有最優(yōu)解,則最優(yōu)解可能是唯一的;也可能 是無(wú)窮多個(gè)。如果是唯一的,這個(gè)解一定在該凸多邊形的某 個(gè)頂點(diǎn)上;如果是無(wú)窮多個(gè),則這些最優(yōu)解一定充滿凸多邊 形的一條邊界(包括此邊界的兩個(gè)頂點(diǎn))總之,若(LP)問(wèn)題有最優(yōu)解,則最優(yōu)解一定可以在凸多邊形的某個(gè)頂點(diǎn)達(dá)到3、若(LP)問(wèn)題有可行解,但沒(méi)有有限最優(yōu)解,此時(shí)凸多邊形 是無(wú)界的(反之不成立)4、若(LP)問(wèn)題沒(méi)有可行解,則該問(wèn)題沒(méi)有最優(yōu)解編輯ppt三、基與基本可行解nxxxX21

22、ncccC21mnmmnnaaaaaaaaaA212222111211其中mbbbb210,0.max)(bXbAXtsCXzLP 問(wèn)題對(duì)不妨設(shè)AX=b有解,且mn,解的結(jié)構(gòu):對(duì)bAX ,唯一解若nrArAr)()(有無(wú)窮多解bAX 利用線性代數(shù)的方法求出無(wú)窮多解? 只討論rn, 此時(shí)nrArAr)()(有解的充要條件是編輯ppt且r(A)=r=m(若rm,必有多余方程,可去掉)0,0.max)(bXbAXtsCXzLP問(wèn)題對(duì)由線性代數(shù)結(jié)論知: 若r(A)=m,則A 中至少存在一個(gè)m階子式 |B|0即A中存在滿秩的m階矩陣B ,稱B為(LP)問(wèn)題的一個(gè)基32532322243214321432

23、1xxxxxxxxxxxx例如:321115323221121A110100000021121,對(duì)bAX nrArAr)()(且不妨設(shè)mn321110000021121mArAr2)()(編輯ppt定義1.3 在(LP)問(wèn)題中,A的任意一個(gè)mm階 的非奇異子方陣B(即|B|0)稱為 (LP)問(wèn)題的一個(gè)基一個(gè)線性規(guī)劃問(wèn)題最多有 基mnC0,0.max)(bXbAXtsCXzLP問(wèn)題對(duì)設(shè)r(Amxn)=r=m編輯ppt0,2162.7max211212121xxxxxxxtsxxz對(duì)線性規(guī)劃問(wèn)題例0,2162.7max543215142132121xxxxxxxxxxxxxt sxxz其標(biāo)準(zhǔn)型為100010101100121A系數(shù)矩陣54321PPPPP5432PPPB 3211PPPB 基基4323PPPB 不是基編輯ppt設(shè)r(A)=m0基本可行解非退化基本可行解退化基本可行解退化基本可行解:基本可行解中,存在取0值的基變量非退化基本可行解:基本可行解中,基變量的取值均0對(duì)應(yīng)的基稱為退化基對(duì)應(yīng)的基稱為非退化基,即001bBX01bB線性規(guī)劃問(wèn)題非退化的線性規(guī)劃問(wèn)題退化的線性規(guī)劃問(wèn)題:存在退化基:所有基均非退化mBxxxX21得, bAX 即對(duì)01nmNxxX令m編輯ppt1.運(yùn)輸問(wèn)題建模:運(yùn)輸問(wèn)題要解決的問(wèn)題是:如何利用現(xiàn)有的交通條件,以最低的運(yùn)費(fèi)安

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論