【正文】 ，可使用的金屬板有 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)元。不考慮固定費(fèi)用，則問(wèn)題的數(shù)學(xué)模型為 ?????????????????0,1 0 0323 0 04325 0 0842..321321321321xxxxxxxxxxxxts321 654m a x xxxz ???若考慮固定費(fèi)用就必須引入 0—1變量： 則該問(wèn)題的數(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)問(wèn)題 (Location Problem) 例 某城市消防隊(duì)布點(diǎn)問(wèn)題。 bin(x5)。 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ī)劃中意義不大。一個(gè)線性規(guī)劃問(wèn)題，如果要求部分決策變量為整數(shù)，則構(gòu)成一個(gè)整數(shù)規(guī)劃問(wèn)題。 LINKS(WH,VD):C,X。 ENDDATA 注：數(shù)據(jù)初始化部分以語(yǔ)句 DATA:開(kāi)始，以ENDDATE語(yǔ)句結(jié)束，這兩個(gè)語(yǔ)句需單獨(dú)成一行，數(shù) 據(jù)之間的逗號(hào)和空格可以互換。 為表示數(shù)學(xué)模型中從貨棧到客戶的運(yùn)輸關(guān)系以及與此相關(guān)的運(yùn)輸單價(jià) 和運(yùn)量 再定義一個(gè)表示運(yùn)輸關(guān)系的集合： LINKS(WH,VD): C,X。 LinGO 建模語(yǔ)言引入集合的概念，為建立大規(guī)模的數(shù)學(xué)規(guī)劃模型提供了方便 . 用 LinGO 語(yǔ)言表達(dá)一個(gè)實(shí)際優(yōu)化問(wèn)題，稱之為 LinGO模型。,1,01,1,1m i n111111njmixnjbxmiaxxcfijmijijnjiijminjijij????二 、 銷大于產(chǎn) (total demand exceeds total supply) ? 銷大于產(chǎn)的運(yùn)輸問(wèn)題的特征是 Σ ai Σ bj， 其數(shù)學(xué)模型為： ?????????????????????? ???? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。 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)元 。 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)取得。 [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 問(wèn)題二的解答 問(wèn)題 ? ? ?????????213640m i nxxz s . t . ? ? )45(3521????????????xx改寫為： 編寫 M文件 ： c = [40 36]。 [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 問(wèn)題一的解答 問(wèn)題 編寫 M文件 : f = [13 9 10 11 12 8]。 vub=[]。 Aeq=[]。 A=[ 。 Karl Marx Galileo : 展現(xiàn)在我們眼前的宇宙像一本用數(shù) 學(xué)語(yǔ)言寫成的大書(shū)，如不掌握數(shù)學(xué)符號(hào)語(yǔ)言，就像在黑暗 的迷宮里游蕩，什么也認(rèn)識(shí)不清。 則稱 x*為 (f S)的全局最優(yōu)解 (最優(yōu)解 ), 記 .(global optimum),簡(jiǎn)記 opt. ? 最優(yōu)值 : x*為 (f S)的最優(yōu)解 , 則稱 f * = f (x*) 為 (f S)的最優(yōu)值 (最優(yōu)目標(biāo)函數(shù)值 ) 數(shù)學(xué)規(guī)劃模型的一般形式 (f S) ? 局部最優(yōu)解 : x*?S， ? x* 的鄰域 N(x*) ，使?jié)M足 f (x*)≤ f (x), ? x ?S ? N(x*) 。0 0 0 0 ]。0。 b=[50]。 900]。 Aeq=[]。 x1+x2=。,1,0,1,1m i n111 1????產(chǎn)銷不平衡的運(yùn)輸問(wèn)題 Total Supply not Equal to Total Demand 一、產(chǎn)大于銷 (total supply exceeds total demand) ? 產(chǎn)大于銷的運(yùn)輸問(wèn)題的特征是 Σ ai Σ bj， 其數(shù)學(xué)模型為： ?????????????????????? ???? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。經(jīng)處理后，問(wèn)題變成了產(chǎn)銷平衡的運(yùn)輸問(wèn)題，其數(shù)學(xué)模型為： ?此時(shí)，可用表上作業(yè)法求解。 每個(gè)集合在使用之前需要預(yù)先給出定義，定義集合時(shí)要明確三方面的內(nèi)容 ： 集合 的名稱 ， 集合內(nèi)的成員（元素） 、 集合的屬性（可以看成與該集合有關(guān)的變量 或常量，相當(dāng)于數(shù)組） . 本例首先定義倉(cāng)庫(kù)集合 ： WH/W1..W6/:AI。 VD/V1..V8/DJ。 注：如果表達(dá)式中參與酸的屬性屬于同一個(gè)集合，則 語(yǔ)句中索引（相當(dāng)于矩陣或數(shù)組的下標(biāo)可以省略）（隱藏），假如表達(dá)式中參與運(yùn)算的屬性屬于不同的集合，則不能省略屬性的索引 .本例的目標(biāo)函數(shù)可以表示成 MIN=SUM(LINKS:C*X)。 C=6,2,6,7,4,2,5,9 4,9,5,3,8,5,8,2 5,2,1,9,7,4,3,3 7,6,7,3,9,2,7,1 2,3,9,5,7,2,6,5 5,5,2,2,8,1,4,3。 （ 4， 1） 使目標(biāo)函數(shù)達(dá)到最大，即 z＝ 14。 2*x1+x2+4*x3+2*x4+5*x510。 若 Ai點(diǎn)投資為 bi萬(wàn)元，每年可獲利潤(rùn)為 ci萬(wàn)元，投資總額為B萬(wàn) 元，試建立利潤(rùn)最大化的 0－ 1規(guī)劃模型。 表 4－ 9 消防車在各區(qū)間行駛時(shí)間表 單位： min 地區(qū) 1 地區(qū) 2 地區(qū) 3 地區(qū) 4 地區(qū) 5 地區(qū) 6 地區(qū) 1 0 10 16 28 27 20 地區(qū) 2 10 0 24 32 17 10 地區(qū) 3 16 24 0 12 27 21 地區(qū) 4 28 32