【正文】 1(1 5 1 0 2 5 ..2121212211212121或且為整數(shù)yyxxyyyMxxyMxxxxxxts21 4025m a x xxz ??（三）固定成本問題 (Fixed cost problem) 例 某公司制造小、中、大三種尺寸的容器，所需資源為金屬板、勞動力和機器設備，制造一個容器所需的各種資源的數(shù)量如下表所示：不考慮固定費用，小、中、大號容器每售出一個其利潤分別為 4萬元、 5萬元、 6萬元，可使用的金屬板有 500噸，勞動力有 300人 /月，機器有 100臺 /月，若生產(chǎn)，不管每種容器生產(chǎn)多少，都需要支付一筆固定費用：小號為 100萬元，中號為 150萬元，大號為 200萬元。據(jù)實地測定，各區(qū)之間消防車行駛的時間見表 4－ 9，請幫助該市制定一個布點最少的計劃。不考慮固定費用，則問題的數(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 極大化， 應有 Yj=0 （四）布點問題 (Location Problem) 例 某城市消防隊布點問題。 解：設決策變量為 建立 0－ 1規(guī)劃模型如下： 7,2,1,0 ,1 ?????? iAAxiii 點未被選用當點被選用當772211m a x xcxcxcz ???? ???????????????????????????7,2,1,100112.52765432171?ixxxxxxxxxxBxbtsiiii，或（二） 相互排斥的約束條件 (Mutually exclusive constraints) 例 某產(chǎn)品有 A1和 A2兩種型號，需要經(jīng)過 B B B3三道工序，單位工時和利潤、各工序每周工時限制見表所示，問工廠如何安排生產(chǎ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尚無相應完善的敏感性分析理論，因此 REDUCED COST和 DUAL PRICES的結(jié)果在整數(shù)規(guī)劃中意義不大。 IP可用 LINDO直接求解 max 3x1+2x2 st 2x1+3x214 x1+ end gin 2 ―gin 2‖表示 “ 前 2個變量為整數(shù) ” ，等價于： gin x1 gin x2 其中“ GIN 2”表示 2個變量都是一般整數(shù)變量。一個線性規(guī)劃問題，如果要求部分決策變量為整數(shù)，則構成一個整數(shù)規(guī)劃問題。 ENDDATA MIN=SUM(LINKS (I,J):C(I,J)*X(I,J))。 LINKS(WH,VD):C,X。 約束條件 用Ｌ INGO 語言描述該約束條件，語句為： FOR(WH(I): SUM(VD(J):X(I,J))=AI(I))。 ENDDATA 注：數(shù)據(jù)初始化部分以語句 DATA:開始，以ENDDATE語句結(jié)束，這兩個語句需單獨成一行，數(shù) 據(jù)之間的逗號和空格可以互換。 LINKS(WH,VD):C,X。 為表示數(shù)學模型中從貨棧到客戶的運輸關系以及與此相關的運輸單價 和運量 再定義一個表示運輸關系的集合： LINKS(WH,VD): C,X。 其中 WH是集合的名稱， W1..W6是集合內(nèi)的成員， “ ..” 是特定的省略號 （如果不用該省略號，也可以把成員一一羅列出來，成員之間用逗號或 空格分開 ),表明該集合有 6個成員，分別對應于 6個供貨棧， AI是集合的屬性， 它可以看成是一個數(shù)組，有 6個分量，分別表示各貨?，F(xiàn)有貨物的總數(shù)。 LinGO 建模語言引入集合的概念，為建立大規(guī)模的數(shù)學規(guī)劃模型提供了方便 . 用 LinGO 語言表達一個實際優(yōu)化問題，稱之為 LinGO模型。 ???????????????????????? ?????? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。,1,01,1,1m i n111111njmixnjbxmiaxxcfijmijijnjiijminjijij????二 、 銷大于產(chǎn) (total demand exceeds total supply) ? 銷大于產(chǎn)的運輸問題的特征是 Σ ai Σ bj， 其數(shù)學模型為： ?????????????????????? ???? ?njmixnjbxmiaxxcfijmijijnjiijminjijij,1。,1,0,1,1m i n111 1????– 解此類問題可假想一個銷地 Bn+1， 其需要量為： bn+1=Σ ai －Σ bj；若用 xi， n+1表示從 Ai到 Bn+1的運量 ， 可令 ci， n+1=0或等于第 Ai產(chǎn)地儲存單位物資的費用 。 end min 7x1+3x2 st x1+x2= x1=98 2*x1+x2=600 end gin 2 ?lindo程序 : ?lingo程序 : 實驗作業(yè) 某廠生產(chǎn)甲乙兩種口味的飲料 ,每百箱甲飲料需用原料 6千克 ,工人 10名 ,可獲利 10萬元 。 x1=98。 1）若用 35元可以買到 1桶牛奶，應否作這樣的投資？若投資， 每天最多購買多少桶牛奶 2）若可以聘用臨時工人以增加勞動時間，付給臨時工人的 工資最多是每小時幾元？ 3）由于市場需求變化，每公斤 A1的獲利增加到 30元，應否 改變生產(chǎn)計劃？ 1桶牛奶 3kgA1 12小時 8小時 4kgA2 或 獲利 24元 /kg 獲利 16元 /kg x1桶牛奶生產(chǎn) A1 x2桶牛奶生產(chǎn) A2 獲利 24 3x1 獲利 16 4 x2 原料供應 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)解一定在凸多邊形的某個頂點取得。 beq=[]。 [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]。 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