線性規(guī)劃圖解法經(jīng)典運(yùn)籌學(xué)

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)安