【導(dǎo)讀】數(shù)學(xué)使人周密……數(shù)學(xué)處于人類智能的中心領(lǐng)域……法滲透、支配著一切自然科學(xué)的理論分支……它已愈來愈成為衡量成就的主要標(biāo)志。數(shù)學(xué)時(shí)，才算真正發(fā)展了。的迷宮里游蕩，什么也認(rèn)識(shí)不清。數(shù)學(xué)建模其實(shí)并不是什么新東西，可以說有了數(shù)。數(shù)學(xué)建模將各種知識(shí)綜合應(yīng)用于解決實(shí)際問題中，題的能力的必備手段之一.創(chuàng)造的價(jià)值無法估量.中就有一道涉及到利用規(guī)劃理論來分析、求解.器、資金等，使得費(fèi)用最小或者利潤(rùn)最大。S------約束集合，可行集。x*的鄰域N(x*)，使?jié)M足f. x*時(shí)有嚴(yán)格不等式成立，則分別。稱x*為的嚴(yán)格全局最優(yōu)解和嚴(yán)格局部最優(yōu)解。規(guī)劃；若其中有非線性函數(shù)時(shí)，稱非線性規(guī)劃。線性規(guī)劃目標(biāo)和約束均為線性函數(shù)。非線性規(guī)劃目標(biāo)或約束中存在非線性函數(shù)。二次規(guī)劃目標(biāo)為二次函數(shù)、約束為線性。整數(shù)規(guī)劃決策變量為整數(shù)。整數(shù)線性規(guī)劃，整數(shù)非線性規(guī)劃。解設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，

　　

【正文】 識(shí)， 有以下兩種可能的用法： INT vname INT n 前者只將決策變量 vname標(biāo)識(shí)為 0/1型 , 后者將當(dāng)前模型中前 n 個(gè)變量標(biāo)識(shí)為 0/1型（模型中變量順序由模型中輸入時(shí)出現(xiàn)的先后順序決定 , 該順序可由輸出結(jié)果中的變量順序查證是否一致）。 一般的整數(shù)變量可用命令 GIN （是 GENERAL INTEGER的意思） ,其使用方式及格式與 INT 命令相似。 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ī)劃中意義不大。 例 集裝箱運(yùn)貨 貨物 體積 (米 3/箱 ) 重量 (百公斤 /箱 ) 利潤(rùn) (千元 /箱 ) 甲 5 2 20 乙 4 5 10 裝運(yùn)限制 24 13 解：設(shè) X1 , X2 為甲、乙兩貨物各托運(yùn)箱數(shù) 5X1+4X2 ? 24 2X1+5X2 ? 13 X1 , X2 ?0 X1 , X2為整數(shù) maxZ = 20 X1 + 10 X2 例 背包問題 背包可裝入 8單位重量， 10單位體積物品 物品 名稱 重量 體積 價(jià)值 1 書 5 2 20 2 攝像機(jī) 3 1 30 3 枕頭 1 4 10 4 休閑食品 2 3 18 5 衣服 4 5 15 解： Xi為是否帶第 i 種物品 maxZ=20X1 + 30X2 +10X3+18X4 +15X5 5X1+3X2 +X3 +2X4 +4X5 ? 8 2X1+X2 +4X3 +3X4 +5X5 ? 10 Xi為 0, 1 Model: Min=(20*x1+30*x2+10*x3+18*x4+15*x5)。 5*x1+3*x2+x3+2*x4+4*x58。 2*x1+x2+4*x3+2*x4+5*x510。 @bin(x1)。@bin(x2)。 @bin(x3)。@bin(x4)。 @bin(x5)。 END Model: Lingo求解 Global optimal solution found. Objective value: Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X1 X2 X3 X4 X5 Row Slack or Surplus Dual Price 1 2 3 0－ 1整數(shù)規(guī)劃用 (Applications) （一）相互排斥的計(jì)劃 (Mutually exclusive planning) 例 某公司擬在市東、西、南三區(qū)中建立門市部，有 7個(gè)點(diǎn) Ai （ i＝ 1， 2， … ， 7）可供選擇，要求滿足以下條件： （ 1）在東區(qū)，在 A1， A2， A3三個(gè)點(diǎn)中至多選兩個(gè)； （ 2）在西區(qū)， A4， A5兩個(gè)點(diǎn)中至少選一個(gè)； （ 3）在南區(qū)， A6， A7兩個(gè)點(diǎn)為互斥點(diǎn)。 （ 4）選 A2點(diǎn)必選 A5點(diǎn)。 若 Ai點(diǎn)投資為 bi萬元，每年可獲利潤(rùn)為 ci萬元，投資總額為B萬 元，試建立利潤(rùn)最大化的 0－ 1規(guī)劃模型。 解：設(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)過 B B B3三道工序，單位工時(shí)和利潤(rùn)、各工序每周工時(shí)限制見表所示，問工廠如何安排生產(chǎn)，才能使總利潤(rùn)最大？（ B3工序有兩種加工方式 B31和 B32，產(chǎn)品為整數(shù)）。 工時(shí) /件 工序 型號(hào) B1 B2 B3 利潤(rùn)（元 /件） B31 B32 A1 25 A2 40 每周工時(shí)（小時(shí) /月） 250 100 150 120 解：設(shè) A A2產(chǎn)品的生產(chǎn)數(shù)量分別為 x x2件，在不考慮 B31和B32相互排斥的情況下，問題的數(shù)學(xué)模型為 21 4025m a x xxz ????????????????????且為整數(shù),0,)2(1 2 )1(1 5 1 0 2 5 ..2121212121xxxxxxxxxxts工序 B3只能從兩種加工方式中選擇一種，那么約束條件（ 1）和（ 2）就成為相互排斥的約束條件。為了統(tǒng)一在一個(gè)問題中，引入 01變量 則數(shù)學(xué)模型為 2,1,0 ,13333 ????? iBBBByiii 加工方式不采用加工方式采用???????????????????????????10,0,1)1(1 2 )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萬元、 5萬元、 6萬元，可使用的金屬板有 500噸，勞動(dòng)力有 300人 /月，機(jī)器有 100臺(tái) /月，若生產(chǎn)，不管每種容器生產(chǎn)多少，都需要支付一筆固定費(fèi)用：小號(hào)為 100萬元，中號(hào)為 150萬元，大號(hào)為 200萬元。問如何制定生產(chǎn)計(jì)劃使獲得的利潤(rùn)最大？ 資源 小號(hào)容器 中號(hào)容器 大號(hào)容器 金屬板 （ 噸 ） 2 4 8 勞動(dòng)力 （ 人 /月 ） 2 3 4 機(jī)器設(shè)備 （ 臺(tái) /月 ） 1 2 3 解 ：設(shè) x x x3分別為小號(hào)容器、中號(hào)容器、大號(hào)容器的生產(chǎn)數(shù)量。不考慮固定費(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)問題。該城市共有 6個(gè)區(qū)，每個(gè)區(qū)都可以建消防站，市政府希望設(shè)置的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時(shí)，消防車要在 15 分鐘內(nèi)趕到現(xiàn)場(chǎng)。據(jù)實(shí)地測(cè)定，各區(qū)之間消防車行駛的時(shí)間見表 4－ 9，請(qǐng)幫助該市制定一個(gè)布點(diǎn)最少的計(jì)劃。 表 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 1