【正文】 ，可使用的金屬板有 500噸，勞動力有 300人 /月，機器有 100臺 /月，若生產(chǎn)，不管每種容器生產(chǎn)多少，都需要支付一筆固定費用：小號為 100萬元，中號為 150萬元，大號為 200萬元。不考慮固定費用，則問題的數(shù)學模型為 ?????????????????0,1 0 0323 0 04325 0 0842..321321321321xxxxxxxxxxxxts321 654m a x xxxz ???若考慮固定費用就必須引入 0—1變量： 則該問題的數(shù)學模型為 3,2,10,0 0,1 ??????? ixixiyiii 種容器時即當不生產(chǎn)第時種容器即當生產(chǎn)第321321 200150100654m a x yyyxxxz ????????????????????????????????????10,0,0001 0 0323 0 04325 0 0842..321321332211321321321oryyyxxxMyxMyxMyxxxxxxxxxxts可以看出，當 xj0時，為使 Z 極大化， 應(yīng)有 Yj=0 （四）布點問題 (Location Problem) 例 某城市消防隊布點問題。 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尚無相應(yīng)完善的敏感性分析理論，因此 REDUCED COST和 DUAL PRICES的結(jié)果在整數(shù)規(guī)劃中意義不大。一個線性規(guī)劃問題，如果要求部分決策變量為整數(shù)，則構(gòu)成一個整數(shù)規(guī)劃問題。 LINKS(WH,VD):C,X。 ENDDATA 注：數(shù)據(jù)初始化部分以語句 DATA:開始，以ENDDATE語句結(jié)束，這兩個語句需單獨成一行，數(shù) 據(jù)之間的逗號和空格可以互換。 為表示數(shù)學模型中從貨棧到客戶的運輸關(guān)系以及與此相關(guān)的運輸單價 和運量 再定義一個表示運輸關(guān)系的集合： LINKS(WH,VD): C,X。 LinGO 建模語言引入集合的概念，為建立大規(guī)模的數(shù)學規(guī)劃模型提供了方便 . 用 LinGO 語言表達一個實際優(yōu)化問題，稱之為 LinGO模型。,1,01,1,1m i n111111njmixnjbxmiaxxcfijmijijnjiijminjijij????二 、 銷大于產(chǎn) (total demand exceeds total supply) ? 銷大于產(chǎn)的運輸問題的特征是 Σ ai Σ bj， 其數(shù)學模型為： ?????????????????????? ???? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。 end min 7x1+3x2 st x1+x2= x1=98 2*x1+x2=600 end gin 2 ?lindo程序 : ?lingo程序 : 實驗作業(yè) 某廠生產(chǎn)甲乙兩種口味的飲料 ,每百箱甲飲料需用原料 6千克 ,工人 10名 ,可獲利 10萬元 。 1）若用 35元可以買到 1桶牛奶，應(yīng)否作這樣的投資？若投資， 每天最多購買多少桶牛奶 2）若可以聘用臨時工人以增加勞動時間，付給臨時工人的 工資最多是每小時幾元？ 3）由于市場需求變化，每公斤 A1的獲利增加到 30元，應(yīng)否 改變生產(chǎn)計劃？ 1桶牛奶 3kgA1 12小時 8小時 4kgA2 或 獲利 24元 /kg 獲利 16元 /kg x1桶牛奶生產(chǎn) A1 x2桶牛奶生產(chǎn) A2 獲利 24 3x1 獲利 16 4 x2 原料供應(yīng) 5021 ?? xx勞動時間 480812 21 ?? xx加工能力 1003 1 ?x決策變量 目標函數(shù) 12M a x 72 64z x x??每天獲利 約束條件 非負約束 0, 21 ?xx線性規(guī)劃模型(LP) 時間 480小時 至多加工 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??目標函數(shù) z=0 z=2400 z=3600 z =c (常數(shù) ) ~等值線 c 在 B(20,30)點得到最優(yōu)解 目標函數(shù)和約束條件是線性函數(shù) 可行域為直線段圍成的凸多邊形 目標函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊形的某個頂點取得。 [x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub) To MATLAB (xxgh3) 結(jié)果 : x = fval =+004 即在甲機床上加工 600個工件 2,在乙機床上加工 400個工件 500個工件 3，可在滿足條件的情況下使總加工費最小為 13800. 例 2 問題二的解答 問題 ? ? ?????????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 問題一的解答 問題 編寫 M文件 : f = [13 9 10 11 12 8]。 vub=[]。 Aeq=[]。 A=[ 。 Karl Marx Galileo : 展現(xiàn)在我們眼前的宇宙像一本用數(shù) 學語言寫成的大書，如不掌握數(shù)學符號語言，就像在黑暗 的迷宮里游蕩，什么也認識不清。 則稱 x*為 (f S)的全局最優(yōu)解 (最優(yōu)解 ), 記 .(global optimum),簡記 opt. ? 最優(yōu)值 : x*為 (f S)的最優(yōu)解 , 則稱 f * = f (x*) 為 (f S)的最優(yōu)值 (最優(yōu)目標函數(shù)值 ) 數(shù)學規(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)銷不平衡的運輸問題 Total Supply not Equal to Total Demand 一、產(chǎn)大于銷 (total supply exceeds total demand) ? 產(chǎn)大于銷的運輸問題的特征是 Σ ai Σ bj， 其數(shù)學模型為： ?????????????????????? ???? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。經(jīng)處理后，問題變成了產(chǎn)銷平衡的運輸問題，其數(shù)學模型為： ?此時，可用表上作業(yè)法求解。 每個集合在使用之前需要預(yù)先給出定義，定義集合時要明確三方面的內(nèi)容 ： 集合 的名稱 ， 集合內(nèi)的成員（元素） 、 集合的屬性（可以看成與該集合有關(guān)的變量 或常量，相當于數(shù)組） . 本例首先定義倉庫集合 ： WH/W1..W6/:AI。 VD/V1..V8/DJ。 注：如果表達式中參與酸的屬性屬于同一個集合，則 語句中索引（相當于矩陣或數(shù)組的下標可以省略）（隱藏），假如表達式中參與運算的屬性屬于不同的集合，則不能省略屬性的索引 .本例的目標函數(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） 使目標函數(shù)達到最大，即 z＝ 14。 2*x1+x2+4*x3+2*x4+5*x510。 若 Ai點投資為 bi萬元，每年可獲利潤為 ci萬元，投資總額為B萬 元，試建立利潤最大化的 0－ 1規(guī)劃模型。 表 4－ 9 消防車在各區(qū)間行駛時間表 單位： 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