【正文】 1(1 5 1 0 2 5 ..2121212211212121或且為整數(shù)yyxxyyyMxxyMxxxxxxts21 4025m a x xxz ??（三）固定成本問題 (Fixed cost problem) 例 某公司制造小、中、大三種尺寸的容器，所需資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如下表所示：不考慮固定費(fèi)用，小、中、大號(hào)容器每售出一個(gè)其利潤(rùn)分別為 4萬(wàn)元、 5萬(wàn)元、 6萬(wàn)元，可使用的金屬板有 500噸，勞動(dòng)力有 300人 /月，機(jī)器有 100臺(tái) /月，若生產(chǎn)，不管每種容器生產(chǎn)多少，都需要支付一筆固定費(fèi)用：小號(hào)為 100萬(wàn)元，中號(hào)為 150萬(wàn)元，大號(hào)為 200萬(wàn)元。據(jù)實(shí)地測(cè)定，各區(qū)之間消防車行駛的時(shí)間見表 4－ 9，請(qǐng)幫助該市制定一個(gè)布點(diǎn)最少的計(jì)劃。不考慮固定費(fèi)用，則問題的數(shù)學(xué)模型為 ?????????????????0,1 0 0323 0 04325 0 0842..321321321321xxxxxxxxxxxxts321 654m a x xxxz ???若考慮固定費(fèi)用就必須引入 0—1變量： 則該問題的數(shù)學(xué)模型為 3,2,10,0 0,1 ??????? ixixiyiii 種容器時(shí)即當(dāng)不生產(chǎn)第時(shí)種容器即當(dāng)生產(chǎn)第321321 200150100654m a x yyyxxxz ????????????????????????????????????10,0,0001 0 0323 0 04325 0 0842..321321332211321321321oryyyxxxMyxMyxMyxxxxxxxxxxts可以看出，當(dāng) xj0時(shí)，為使 Z 極大化， 應(yīng)有 Yj=0 （四）布點(diǎn)問題 (Location Problem) 例 某城市消防隊(duì)布點(diǎn)問題。 解：設(shè)決策變量為 建立 0－ 1規(guī)劃模型如下： 7,2,1,0 ,1 ?????? iAAxiii 點(diǎn)未被選用當(dāng)點(diǎn)被選用當(dāng)772211m a x xcxcxcz ???? ???????????????????????????7,2,1,100112.52765432171?ixxxxxxxxxxBxbtsiiii，或（二） 相互排斥的約束條件 (Mutually exclusive constraints) 例 某產(chǎn)品有 A1和 A2兩種型號(hào)，需要經(jīng)過(guò) B B B3三道工序，單位工時(shí)和利潤(rùn)、各工序每周工時(shí)限制見表所示，問工廠如何安排生產(chǎn)，才能使總利潤(rùn)最大？（ B3工序有兩種加工方式 B31和 B32，產(chǎn)品為整數(shù)）。 bin(x5)。 bin(x1)。 SET X2 TO = 2 AT 1, BND= TWIN= 7 SET X1 TO = 4 AT 2, BND= TWIN= 10 NEW INTEGER SOLUTION OF AT BRANCH 2 PIVOT 10 BOUND ON OPTIMUM: DELETE X1 AT LEVEL 2 DELETE X2 AT LEVEL 1 ENUMERATION COMPLETE. BRANCHES= 2 PIVOTS= 10 LAST INTEGER SOLUTION IS THE BEST FOUND REINSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X1 X2 ROW SLACK OR SURPLUS DUAL PRICES 2) 3) NO. ITERATIONS= 10 BRANCHES= 2 DETERM.= 0 最優(yōu)值 松弛和剩余變量（ SLACK OR SURPLUS）仍然可以表示約束的松緊程度，但目前 IP尚無(wú)相應(yīng)完善的敏感性分析理論，因此 REDUCED COST和 DUAL PRICES的結(jié)果在整數(shù)規(guī)劃中意義不大。 IP可用 LINDO直接求解 max 3x1+2x2 st 2x1+3x214 x1+ end gin 2 ―gin 2‖表示 “ 前 2個(gè)變量為整數(shù) ” ，等價(jià)于： gin x1 gin x2 其中“ GIN 2”表示 2個(gè)變量都是一般整數(shù)變量。一個(gè)線性規(guī)劃問題，如果要求部分決策變量為整數(shù)，則構(gòu)成一個(gè)整數(shù)規(guī)劃問題。 ENDDATA MIN=SUM(LINKS (I,J):C(I,J)*X(I,J))。 LINKS(WH,VD):C,X。 約束條件 用Ｌ INGO 語(yǔ)言描述該約束條件，語(yǔ)句為： FOR(WH(I): SUM(VD(J):X(I,J))=AI(I))。 ENDDATA 注：數(shù)據(jù)初始化部分以語(yǔ)句 DATA:開始，以ENDDATE語(yǔ)句結(jié)束，這兩個(gè)語(yǔ)句需單獨(dú)成一行，數(shù) 據(jù)之間的逗號(hào)和空格可以互換。 LINKS(WH,VD):C,X。 為表示數(shù)學(xué)模型中從貨棧到客戶的運(yùn)輸關(guān)系以及與此相關(guān)的運(yùn)輸單價(jià) 和運(yùn)量 再定義一個(gè)表示運(yùn)輸關(guān)系的集合： LINKS(WH,VD): C,X。 其中 WH是集合的名稱， W1..W6是集合內(nèi)的成員， “ ..” 是特定的省略號(hào) （如果不用該省略號(hào)，也可以把成員一一羅列出來(lái)，成員之間用逗號(hào)或 空格分開 ),表明該集合有 6個(gè)成員，分別對(duì)應(yīng)于 6個(gè)供貨棧， AI是集合的屬性， 它可以看成是一個(gè)數(shù)組，有 6個(gè)分量，分別表示各貨?，F(xiàn)有貨物的總數(shù)。 LinGO 建模語(yǔ)言引入集合的概念，為建立大規(guī)模的數(shù)學(xué)規(guī)劃模型提供了方便 . 用 LinGO 語(yǔ)言表達(dá)一個(gè)實(shí)際優(yōu)化問題，稱之為 LinGO模型。 ???????????????????????? ?????? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。,1,01,1,1m i n111111njmixnjbxmiaxxcfijmijijnjiijminjijij????二 、 銷大于產(chǎn) (total demand exceeds total supply) ? 銷大于產(chǎn)的運(yùn)輸問題的特征是 Σ ai Σ bj， 其數(shù)學(xué)模型為： ?????????????????????? ???? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。,1,0,1,1m i n111 1????– 解此類問題可假想一個(gè)銷地 Bn+1， 其需要量為： bn+1=Σ ai －Σ bj；若用 xi， n+1表示從 Ai到 Bn+1的運(yùn)量 ， 可令 ci， n+1=0或等于第 Ai產(chǎn)地儲(chǔ)存單位物資的費(fèi)用 。 end min 7x1+3x2 st x1+x2= x1=98 2*x1+x2=600 end gin 2 ?lindo程序 : ?lingo程序 : 實(shí)驗(yàn)作業(yè) 某廠生產(chǎn)甲乙兩種口味的飲料 ,每百箱甲飲料需用原料 6千克 ,工人 10名 ,可獲利 10萬(wàn)元 。 x1=98。 1）若用 35元可以買到 1桶牛奶，應(yīng)否作這樣的投資？若投資， 每天最多購(gòu)買多少桶牛奶 2）若可以聘用臨時(shí)工人以增加勞動(dòng)時(shí)間，付給臨時(shí)工人的 工資最多是每小時(shí)幾元？ 3）由于市場(chǎng)需求變化，每公斤 A1的獲利增加到 30元，應(yīng)否 改變生產(chǎn)計(jì)劃？ 1桶牛奶 3kgA1 12小時(shí) 8小時(shí) 4kgA2 或 獲利 24元 /kg 獲利 16元 /kg x1桶牛奶生產(chǎn) A1 x2桶牛奶生產(chǎn) A2 獲利 24 3x1 獲利 16 4 x2 原料供應(yīng) 5021 ?? xx勞動(dòng)時(shí)間 480812 21 ?? xx加工能力 1003 1 ?x決策變量 目標(biāo)函數(shù) 12M a x 72 64z x x??每天獲利 約束條件 非負(fù)約束 0, 21 ?xx線性規(guī)劃模型(LP) 時(shí)間 480小時(shí) 至多加工 100kgA1 50桶牛奶 每天 基本模型 模型求解 圖解法 x1 x2 0 A B C D l1 l2 l3 l4 l5 5021 ?? xx480812 21 ?? xx1003 1 ?x0, 21 ?xx約束條件 50: 211 ?? xxl480812: 212 ?? xxl1003: 13 ?xl0:,0: 2514 ?? xlxl12M a x 72 64z x x??目標(biāo)函數(shù) z=0 z=2400 z=3600 z =c (常數(shù) ) ~等值線 c 在 B(20,30)點(diǎn)得到最優(yōu)解 目標(biāo)函數(shù)和約束條件是線性函數(shù) 可行域?yàn)橹本€段圍成的凸多邊形 目標(biāo)函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。 beq=[]。 [x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub) To MATLAB (xxgh3) 結(jié)果 : x = fval =+004 即在甲機(jī)床上加工 600個(gè)工件 2,在乙機(jī)床上加工 400個(gè)工件 500個(gè)工件 3，可在滿足條件的情況下使總加工費(fèi)最小為 13800. 例 2 問題二的解答 問題 ? ? ?????????213640m i nxxz s . t . ? ? )45(3521????????????xx改寫為： 編寫 M文件 ： c = [40 36]。 Aeq=[1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1]。 [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub) To MATLAB (xxgh2) 123m i n ( 6 3 4 )xzxx????? ???????????????????????32120030xxx1231 1 1 1 2 0s .t . 0 1 0 5 0xxx??? ? ? ????? ? ? ???? ? ? ?????. ? ? Xz 8121110913m i n ? ?????????????????900800 X?????????????????????5 0 06 0 04 0 0100100010010001001X ，0654321??????????????????????xxxxxxX 改寫為： 例 3 問題一的解答 問題 編寫 M文件 : f = [13 9