運(yùn)籌學(xué)完整版本

1、污水處理問(wèn)題200萬(wàn)m3500萬(wàn)m32萬(wàn)m31.4萬(wàn)m3200萬(wàn)m3500萬(wàn)m32萬(wàn)m31.4萬(wàn)m3化工廠1化工廠21000元/萬(wàn)m3800元/萬(wàn)m3分析：化工廠1處理污水x1萬(wàn)m3,化工廠2處理污水x2萬(wàn)m3。minz=1000x1+800x2(2-x1)/500≤2/1000[(1-0.2)(2-x1)+1.4-x2]/(500+200)≤2/1000x1≤2x2≤1.4x1，x2≥0這里minz:表示求z的最小值。松弛變量:在線性規(guī)劃中，一個(gè)“≤”約束條件中沒有使用的資源或能力稱之為松弛變量位于直線①、②的交點(diǎn)上，故可知設(shè)備臺(tái)時(shí)和材料A的松弛變量都為0；交點(diǎn)不在直線③上，材料B的松弛變量大于0.剩余變量:在線性規(guī)劃中，對(duì)于“≥”約束條件，可以增加一些代表最低限約束的超過(guò)量，稱之為剩余變量?；癁闃?biāo)準(zhǔn)型minz=-x1+2x2-3x3x1+x2+x3≤7① x1-x2+x3≥2② -3x1+x2+2x3=5③ x1,x2≥0，x3無(wú)約束令x3=x3’-x3”，x3’,x3”≥0；①式加上一個(gè)松弛變量x4；②式減去一個(gè)剩余變量x5；令z’=-zmaxz’=x1-2x2+3(x3’-x3”)+0x4+0x5x1+x2+(x3’-x3”)+x4=7 x1-x2+(x3’-x3”)-x5=2 -3x1+x2+2(x3’-x3”)=5 x1,x2,x3’,x3”,x4,x5≥0在約束條件常數(shù)項(xiàng)中增加一個(gè)單位而使最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)的數(shù)量稱之為這個(gè)約束條件的對(duì)偶價(jià)格。當(dāng)某約束條件中的松弛變量（或剩余變量）不為零時(shí)，這個(gè)約束條件的對(duì)偶價(jià)格就為0.2、人力資源分配的問(wèn)題例1．某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開始時(shí)上班，并連續(xù)工作八小時(shí)，問(wèn)該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員?解：設(shè)xi表示第i班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5+x6約束條件：s.t.x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1,x2,x3,x4,x5,x6≥0例2．一家中型的百貨商場(chǎng)，它對(duì)售貨員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如下表所示。為了保證售貨人員充分休息，售貨人員每周工作5天，休息兩天，并要求休息的兩天是連續(xù)的。問(wèn)應(yīng)該如何安排售貨人員的作息，既滿足工作需要，又使配備的售貨人員的人數(shù)最少？解：設(shè)xi(i=1,2,…,7)表示星期一至日開始休息的人數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5+x6+x7約束條件：s.t.x1+x2+x3+x4+x5≥28x2+x3+x4+x5+x6≥15x3+x4+x5+x6+x7≥24x4+x5+x6+x7+x1≥25x5+x6+x7+x1+x2≥19x6+x7+x1+x2+x3≥31x7+x1+x2+x3+x4≥28x1,x2,x3,x4,x5,x6,x7≥03、生產(chǎn)計(jì)劃的問(wèn)題例3．某公司面臨一個(gè)是外包協(xié)作還是自行生產(chǎn)的問(wèn)題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過(guò)鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如表。問(wèn)：公司為了獲得最大利潤(rùn)，甲、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？解：設(shè)x1,x2,x3分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，x4,x5分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。求xi的利潤(rùn)：利潤(rùn)=售價(jià)-各成本之和產(chǎn)品甲全部自制的利潤(rùn)=23-(3+2+3)=15產(chǎn)品甲鑄造外協(xié)，其余自制的利潤(rùn)=23-(5+2+3)=13產(chǎn)品乙全部自制的利潤(rùn)=18-(5+1+2)=10產(chǎn)品乙鑄造外協(xié)，其余自制的利潤(rùn)=18-(6+1+2)=9產(chǎn)品丙的利潤(rùn)=16-(4+3+2)=7可得到xi的利潤(rùn)分別為15、10、7、13、9元。通過(guò)以上分析,可建立如下的數(shù)學(xué)模型:目標(biāo)函數(shù)：Max15x1+10x2+7x3+13x4+9x5約束條件：5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0例4．永久機(jī)械廠生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，均要經(jīng)過(guò)A、B兩道工序加工。設(shè)有兩種規(guī)格的設(shè)備A1、A2能完成A工序；有三種規(guī)格的設(shè)備B1、B2、B3能完成B工序。Ⅰ可在A、B的任何規(guī)格的設(shè)備上加工；Ⅱ可在任意規(guī)格的A設(shè)備上加工，但對(duì)B工序，只能在B1設(shè)備上加工；Ⅲ只能在A2與B2設(shè)備上加工。數(shù)據(jù)如表。問(wèn)：為使該廠獲得最大利潤(rùn)，應(yīng)如何制定產(chǎn)品加工方案？解：設(shè)xijk表示第i種產(chǎn)品，在第j種工序上的第k種設(shè)備上加工的數(shù)量。建立如下的數(shù)學(xué)模型:s.t.5x111+10x211≤6000（設(shè)備A1）7x112+9x212+12x312≤10000（設(shè)備A2）6x121+8x221≤4000（設(shè)備B1）4x122+11x322≤7000（設(shè)備B2）7x123≤4000（設(shè)備B3）x111+x112-x121-x122-x123=0（Ⅰ產(chǎn)品在A、B工序加工的數(shù)量相等）x211+x212-x221=0（Ⅱ產(chǎn)品在A、B工序加工的數(shù)量相等）x312-x322=0（Ⅲ產(chǎn)品在A、B工序加工的數(shù)量相等）xijk≥0,i=1,2,3;j=1,2;k=1,2,3目標(biāo)函數(shù)為計(jì)算利潤(rùn)最大化，利潤(rùn)的計(jì)算公式為：利潤(rùn)=[（銷售單價(jià)-原料單價(jià)）*產(chǎn)品件數(shù)]之和-（每臺(tái)時(shí)的設(shè)備費(fèi)用*設(shè)備實(shí)際使用的總臺(tái)時(shí)數(shù)）之和。這樣得到目標(biāo)函數(shù)：Max(1.25-0.25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312–300/6000(5x111+10x211)-321/10000(7x112+9x212+12x312)-250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).經(jīng)整理可得：Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x1234、套裁下料問(wèn)題例5．某工廠要做100套鋼架，每套用長(zhǎng)為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長(zhǎng)7.4m，問(wèn)：應(yīng)如何下料，可使所用原料最??？解：共可設(shè)計(jì)下列5種下料方案，見下表設(shè)x1,x2,x3,x4,x5分別為上面5種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5約束條件：s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0用“管理運(yùn)籌學(xué)”軟件計(jì)算得出最優(yōu)下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=30;x2=10；x3=0；x4=50；x5=0；只需90根原材料就可制造出100套鋼架。注意：在建立此類型數(shù)學(xué)模型時(shí)，約束條件用大于等于號(hào)比用等于號(hào)要好。因?yàn)橛袝r(shí)在套用一些下料方案時(shí)可能會(huì)多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用等于號(hào)，這一方案就不是可行解了。配料問(wèn)題例6．某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問(wèn)：該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為最大？解：設(shè)xij表示第i種（甲、乙、丙）產(chǎn)品中原料j的含量。這樣我們建立數(shù)學(xué)模型時(shí)，要考慮：對(duì)于甲：x11，x12，x13；對(duì)于乙：x21，x22，x23；對(duì)于丙：x31，x32，x33；對(duì)于原料1：x11，x21，x31；對(duì)于原料2：x12，x22，x32；對(duì)于原料3：x13，x23，x33；目標(biāo)函數(shù)：利潤(rùn)最大，利潤(rùn)=收入-原料支出約束條件：規(guī)格要求4個(gè)；供應(yīng)量限制3個(gè)。利潤(rùn)=總收入-總成本=甲乙丙三種產(chǎn)品的銷售單價(jià)*產(chǎn)品數(shù)量-甲乙丙使用的原料單價(jià)*原料數(shù)量目標(biāo)函數(shù)Max50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）=-15x11+25x12+15x13-30x21+10x22-40x31-10x33約束條件：從規(guī)格要求可知：x11≥0.5(x11+x12+x13)x12≤0.25(x11+x12+x13)x21≥0.25(x21+x22+x23)x22≤0.5(x21+x22+x23)從第2個(gè)表中，生產(chǎn)甲乙丙的原材料不能超過(guò)原材料的供應(yīng)限額，(x11+x21+x31)≤100(x12+x22+x32)≤100(x13+x23+x33)≤60目標(biāo)函數(shù)：Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33約束條件：s.t.0.5x11-0.5x12-0.5x13≥0（原材料1不少于50%）-0.25x11+0.75x12-0.25x13≤0（原材料2不超過(guò)25%）0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）-0.5x21+0.5x22-0.5x23≤0（原材料2不超過(guò)50%）x11+x21+x31≤100(供應(yīng)量限制）x12+x22+x32≤100(供應(yīng)量限制）x13+x23+x33≤60(供應(yīng)量限制）xij≥0,i=1,2,3;j=1,2,35、投資問(wèn)題例7．某部門現(xiàn)有資金200萬(wàn)元，今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第五年每年年初都可投資，當(dāng)年末能收回本利110%；項(xiàng)目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過(guò)30萬(wàn)元；項(xiàng)目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過(guò)80萬(wàn)元；項(xiàng)目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過(guò)100萬(wàn)元。據(jù)測(cè)定每萬(wàn)元每次投資的風(fēng)險(xiǎn)指數(shù)如下表，問(wèn)：a）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利金額為最大？b）應(yīng)如何確定這些項(xiàng)目的每年投資額，使得第五年年末擁有資金的本利在330萬(wàn)元的基礎(chǔ)上使得其投資總的風(fēng)險(xiǎn)系數(shù)為最?。拷猓?）確定決策變量：連續(xù)投資問(wèn)題設(shè)xij(i=1～5，j=1～4)表示第i年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項(xiàng)目的金額。這樣我們建立如下的決策變量：Ax11x21x31x41x51Bx12x22x32x42Cx33Dx242）約束條件：第一年：A當(dāng)年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是x11+x12=200；第二年：B次年末才可收回投資，故第二年年初有資金1.1x11，于是x21+x22+x24=1.1x11；第三年：年初有資金1.1x21+1.25x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初有資金1.1x31+1.25x22，于是x41+x42=1.1x31+1.25x22；第五年：年初有資金1.1x41+1.25x32，于是x51=1.1x41+1.25x32；B、C、D的投資限制：xi2≤30(i=1、2、3、4)，x33≤80，x24≤1003）目標(biāo)函數(shù)及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi2≤30(i=1、2、3、4)，x33≤80，x24≤100xij≥0(i=1、2、3、4、5；j=1、2、3、4）b)所設(shè)變量與問(wèn)題a相同，目標(biāo)函數(shù)為風(fēng)險(xiǎn)最小，有

Minf=x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24在問(wèn)題a的約束條件中加上“第五年末擁有資金本利在330萬(wàn)元”的條件，于是模型如下：Minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.x11+x12=200x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi2≤30(i=1、2、3、4)，x33≤80，x24≤1001.1x51+1.25x42+1.4x33+1.55x24≥330xij≥0(i=1、2、3、4、5；j=1、2、3、4）單純形法幾種特殊情況：求線性規(guī)劃的最優(yōu)解里有人工變量大于零，則此線性規(guī)劃無(wú)可行解。存在著一個(gè)大于零的檢驗(yàn)數(shù)，并且該列的系數(shù)向量的每個(gè)元素aij(i=1,2,…,m)都小于或等于零，則此線性規(guī)劃問(wèn)題是無(wú)界的，一般地說(shuō)此類問(wèn)題的出現(xiàn)是由于建模的錯(cuò)誤所引起的。如果存在某個(gè)非基變量的檢驗(yàn)數(shù)為零，則此線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。6、運(yùn)輸問(wèn)題解決把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地，在每個(gè)產(chǎn)地的供應(yīng)量與每個(gè)銷地的需求量已知，各地之間的運(yùn)輸單價(jià)已知的前提下，如何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案的問(wèn)題。例某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？解：產(chǎn)銷平衡問(wèn)題：總產(chǎn)量=總銷量設(shè)xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：使運(yùn)費(fèi)最小，即所以此線性規(guī)劃問(wèn)題的線性規(guī)劃模型如下：表上作業(yè)法：最小元素法（西北角法）—>勢(shì)差法（閉合回路法）7、產(chǎn)銷不平衡的運(yùn)輸問(wèn)題例石家莊北方研究院有一、二、三三個(gè)區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價(jià)格、質(zhì)量相同。供應(yīng)能力分別為1500、4000噸，運(yùn)價(jià)為：由于需大于供，經(jīng)院研究決定一區(qū)供應(yīng)量可減少0--300噸，二區(qū)必須滿足需求量，三區(qū)供應(yīng)量不少于1500噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。解：根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價(jià)表：例設(shè)有A、B、C三個(gè)化肥廠供應(yīng)1、2、3、4四個(gè)地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表，試求總費(fèi)用為最低的化肥調(diào)撥方案。解：根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價(jià)表：最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為M，而最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為0。對(duì)應(yīng)4”的銷量50是考慮問(wèn)題本身適當(dāng)取的數(shù)據(jù)，根據(jù)產(chǎn)銷平衡要求確定D的產(chǎn)量為50。8、生產(chǎn)與儲(chǔ)存問(wèn)題例某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表。如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用0.15萬(wàn)元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。解：設(shè)xij為第i季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足：交貨：x11=10生產(chǎn)：x11+x12+x13+x14≤25x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i個(gè)生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)目看作第j個(gè)銷售點(diǎn)的銷量；成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)?？蓸?gòu)造下列產(chǎn)銷平衡問(wèn)題：目標(biāo)函數(shù)：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44例光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷的。已知1至6月份各月的生產(chǎn)能力、合同銷量和單臺(tái)電腦繡花機(jī)平均生產(chǎn)費(fèi)用見下表：已知上年末庫(kù)存103臺(tái)繡花機(jī)，如果當(dāng)月生產(chǎn)出來(lái)的機(jī)器當(dāng)月不交貨，則需要運(yùn)到分廠庫(kù)房，每臺(tái)增加運(yùn)輸成本0.1萬(wàn)元,每臺(tái)機(jī)器每月的平均倉(cāng)儲(chǔ)費(fèi)、維護(hù)費(fèi)為0.2萬(wàn)元。在7--8月份銷售淡季，全廠停產(chǎn)1個(gè)月，因此在6月份完成銷售合同后還要留出庫(kù)存80臺(tái)。加班生產(chǎn)機(jī)器每臺(tái)增加成本1萬(wàn)元。問(wèn)應(yīng)如何安排1--6月份的生產(chǎn)，可使總的生產(chǎn)費(fèi)用（包括運(yùn)輸、倉(cāng)儲(chǔ)、維護(hù)）最少？解：這個(gè)生產(chǎn)存儲(chǔ)問(wèn)題可化為運(yùn)輸問(wèn)題來(lái)做?？紤]：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷地1）1--6月份合計(jì)生產(chǎn)能力（包括上年末儲(chǔ)存量）為743臺(tái)，銷量為707臺(tái)。設(shè)一假想銷地銷量為36；2）上年末庫(kù)存103臺(tái)，只有倉(cāng)儲(chǔ)費(fèi)和運(yùn)輸費(fèi)，把它列為第0行；3）6月份的需求除70臺(tái)銷量外，還要80臺(tái)庫(kù)存，其需求應(yīng)為70+80=150臺(tái)；4）1--6表示1--6月份正常生產(chǎn)情況，1’--6’表示1--6月份加班生產(chǎn)情況。產(chǎn)銷平衡與運(yùn)價(jià)表：9、轉(zhuǎn)運(yùn)問(wèn)題在原運(yùn)輸問(wèn)題上增加若干轉(zhuǎn)運(yùn)站。運(yùn)輸方式有：產(chǎn)地轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)站銷地、產(chǎn)地產(chǎn)地、產(chǎn)地銷地、銷地轉(zhuǎn)運(yùn)站、銷地產(chǎn)地等例騰飛電子儀器公司在大連和廣州有兩個(gè)分廠生產(chǎn)同一種儀器，大連分廠每月生產(chǎn)400臺(tái)，廣州分廠每月生產(chǎn)600臺(tái)。該公司在上海和天津有兩個(gè)銷售公司負(fù)責(zé)對(duì)南京、濟(jì)南、南昌、青島四個(gè)城市的儀器供應(yīng)。另外因?yàn)榇筮B距離青島較近，公司同意大連分廠向青島直接供貨，運(yùn)輸費(fèi)用如圖，單位是百元。問(wèn)應(yīng)該如何調(diào)運(yùn)儀器，可使總運(yùn)輸費(fèi)用最低？1-廣州2-大連3-上海4-天津5-南京6-濟(jì)南7-南昌8-青島解：設(shè)xij為從i到j(luò)的運(yùn)輸量，可得到有下列特點(diǎn)的線性規(guī)劃模型：目標(biāo)函數(shù)：Minf=所有可能的運(yùn)輸費(fèi)用（運(yùn)輸單價(jià)與運(yùn)輸量乘積之和）約束條件：對(duì)產(chǎn)地（發(fā)點(diǎn)）i：輸出量-輸入量=產(chǎn)量對(duì)轉(zhuǎn)運(yùn)站（中轉(zhuǎn)點(diǎn)）：輸入量-輸出量=0對(duì)銷地（收點(diǎn)）j：輸入量-輸出量=銷量Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48s.t.x13+x14≤600(廣州分廠供應(yīng)量限制）x23+x24+x28≤400(大連分廠供應(yīng)量限制）-x13-x23+x35+x36+x37+x38=0（上海銷售公司，轉(zhuǎn)運(yùn)站）-x14-x24+x45+x46+x47+x48=0（天津銷售公司，轉(zhuǎn)運(yùn)站）x35+x45=200（南京的銷量）x36+x46=150（濟(jì)南的銷量）x37+x47=350（南昌的銷量）x38+x48+x28=300（青島的銷量）xij≥0,i,j=1,2,3,4,5,6,7,810、投資場(chǎng)所的選擇例4、京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個(gè)位置Aj(j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集度，規(guī)定：在東區(qū)由A1，A2，A3三個(gè)點(diǎn)至多選擇兩個(gè)；在西區(qū)由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)；在北區(qū)由A8，A9，A10三個(gè)點(diǎn)中至少選兩個(gè)。投資總額不能超過(guò)720萬(wàn)元，問(wèn)應(yīng)選擇哪幾個(gè)銷售點(diǎn)，可使年利潤(rùn)為最大?解：設(shè)0--1變量xi=1(Ai點(diǎn)被選用）或0(Ai點(diǎn)沒被選用）。Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720x1+x2+x3≤2x4+x5≥1x6+x7≥1x8+x9+x10≥2xj≥0且xj為0--1變量，i=1,2,3,……,1011、固定成本問(wèn)題例5．高壓容器公司制造小、中、大三種尺寸的金屬容器，現(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利潤(rùn)為最大。解：設(shè)x1，x2，x3分別為小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)數(shù)量。各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才投入，為了說(shuō)明固定費(fèi)用的這種性質(zhì)，設(shè)yi=引入約束xi≤Myi，i=1，2，3，M充分大，以保證當(dāng)yi=0時(shí)，xi=0。這樣我們可建立如下的數(shù)學(xué)模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大xj≥0yj為0--1變量，i=1,2,312、指派問(wèn)題有n項(xiàng)不同的任務(wù)，恰好n個(gè)人可分別承擔(dān)這些任務(wù)，但由于每人特長(zhǎng)不同，完成各項(xiàng)任務(wù)的效率等情況也不同。現(xiàn)假設(shè)必須指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把n項(xiàng)任務(wù)指派給n個(gè)人，使得完成n項(xiàng)任務(wù)的總的效率最高。例6．問(wèn)應(yīng)如何指派工作，才能使總的消耗時(shí)間為最少？解：引入0—1變量xij，并令xij=這可以表示為一個(gè)0--1整數(shù)規(guī)劃問(wèn)題：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(甲只能干一項(xiàng)工作)x21+x22+x23+x24=1(乙只能干一項(xiàng)工作)x31+x32+x33+x34=1(丙只能干一項(xiàng)工作)x41+x42+x43+x44=1(丁只能干一項(xiàng)工作)x11+x21+x31+x41=1(A工作只能一人干)x12+x22+x32+x42=1(B工作只能一人干)x13+x23+x33+x43=1(C工作只能一人干)x14+x24+x34+x44=1(D工作只能一人干)xij為0--1變量，i,j=1,2,3,413、分布系統(tǒng)設(shè)計(jì)例7．某企業(yè)在A1地已有一個(gè)工廠，其產(chǎn)品的生產(chǎn)能力為30千箱，為了擴(kuò)大生產(chǎn)，打算在A2，A3，A4，A5地中再選擇幾個(gè)地方建廠。已知在A2，A3，A4，A5地建廠的固定成本分別為175千元、300千元、375千元、500千元，另外，A1產(chǎn)量及A2，A3，A4，A5建成廠的產(chǎn)量，那時(shí)銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(jià)(每千箱運(yùn)費(fèi))如下表所示。a)問(wèn)應(yīng)該在哪幾個(gè)地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運(yùn)輸費(fèi)用之和最小?b)如果由于政策要求必須在A2，A3地建一個(gè)廠，應(yīng)在哪幾個(gè)地方建廠?解：a)設(shè)xij為從Ai運(yùn)往Bj的運(yùn)輸量(單位千箱)，yk=1(當(dāng)Ak被選中時(shí))或0（當(dāng)Ak沒被選中時(shí)),k=2,3,4,5．這可以表示為一個(gè)整數(shù)規(guī)劃問(wèn)題：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4項(xiàng)為固定投資額，后面的項(xiàng)為運(yùn)輸費(fèi)用。s.t.x11+x12+x13≤30(A1廠的產(chǎn)量限制)x21+x22+x23≤10y2(A2廠的產(chǎn)量限制)x31+x32+x33≤20y3(A3廠的產(chǎn)量限制)x41+x42+x43≤30y4(A4廠的產(chǎn)量限制)x51+x52+x53≤40y5(A5廠的產(chǎn)量限制)x11+x21+x31+x41+x51=30(B1銷地的限制)x12+x22+x32+x42+x52=20(B2銷地的限制)x13+x23+x33+x43+x53=20(B3銷地的限制)xij≥0，i=1,2,3,4,5；j=1,2,3，yk為0--1變量，k=2,3,4,514、投資問(wèn)題例8．某公司在今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%，但要求第一年投資最低金額為4萬(wàn)元，第二、三、四年不限；項(xiàng)目B：第三年初需要投資，到第五年末能回收本利128％，但規(guī)定最低投資金額為3萬(wàn)元，最高金額為5萬(wàn)元；項(xiàng)目C：第二年初需要投資，到第五年末能回收本利140%，但規(guī)定其投資額或?yàn)?萬(wàn)元或?yàn)?萬(wàn)元或?yàn)?萬(wàn)元或?yàn)?萬(wàn)元。項(xiàng)目D：五年內(nèi)每年初可購(gòu)買公債，于當(dāng)年末歸還，并加利息6%，此項(xiàng)投資金額不限。該部門現(xiàn)有資金10萬(wàn)元，問(wèn)它應(yīng)如何確定給這些項(xiàng)目的每年投資額，使到