第4講優(yōu)化模型的Lingo實(shí)現(xiàn)

1、數(shù)學(xué)建模課程綜合設(shè)計(jì)數(shù)學(xué)建模課程綜合設(shè)計(jì) 王 丹 2016 例1 設(shè)某工廠有甲、乙、丙、丁四個(gè)車(chē)間，生產(chǎn)A、B、C、D、E、F六種產(chǎn)品，根據(jù)機(jī)車(chē)性能和以前的生產(chǎn)情況，得知生產(chǎn)每單位產(chǎn)品所需各車(chē)間的工作時(shí)數(shù)、每個(gè)車(chē)間在一個(gè)季度工作時(shí)數(shù)的上限以及產(chǎn)品的價(jià)格，如下表所示。問(wèn)：每種產(chǎn)品每季度各應(yīng)生產(chǎn)多少，才能使這個(gè)工廠每季度生產(chǎn)總值達(dá)到最大？ 第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)3. 產(chǎn)品產(chǎn)品車(chē)間車(chē)間A AB BC CD DE EF F 每個(gè)車(chē)間每季度每個(gè)車(chē)間每季度 工作時(shí)數(shù)上限工作時(shí)數(shù)上限 甲甲乙乙丙丙丁丁0.010.010.02 0.02 0.010.010.02 0.02 0.01

2、0.010.03 0.03 0.030.030.050.050.030.030.05 0.05 0.030.030.08 0.08 850850700700100100900 900 單價(jià)（元）單價(jià)（元）0.40 0.40 0.280.280.32 0.32 0.72 0.72 0.64 0.64 0.600.60第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn) 解 以 x1 x6 分別表示每季度生產(chǎn)產(chǎn)品A、B、C、D、E、F的單位數(shù)，于是它們需滿(mǎn)足目標(biāo)函數(shù)為1234560.01 0.01 0.01 0.03 0.03 0.038500.020.057000.020.051000.030.0

3、8900 xxxxxx126,0,ixxxxZ123456max0.400.280.320.720.640.60fxxxxxx第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)LINGO實(shí)現(xiàn)實(shí)現(xiàn)第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)123456max0.400.280.320.720.640.60fxxxxxx模型：Max = 0.4*x1+0.28*x2+0.32*x3+0.72*x4+0.64*x5+0.6*x6代碼：方法1：直接轉(zhuǎn)換第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)1234560.01 0.01 0.01 0.03 0.03 0.038500.020.0570

4、00.020.051000.030.08900 xxxxxx約束：126,0,ixxxxZ代碼：第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)目標(biāo)函數(shù)約束條件整數(shù)約束第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)方法2：使用集合變量（1）車(chē)間集合：Factory/1.4/: ftotal;（2）產(chǎn)品集合：Productor/A.F/: pvalue,x;車(chē)間工時(shí)數(shù)產(chǎn)品價(jià)值待求變量（3）加工時(shí)數(shù)矩陣：Pro_Fact(Factory, Productor): pf;0.010.010.010.030.030.030.020.050.020.050.030.08數(shù)據(jù)段：數(shù)據(jù)段： 第第4講講

5、 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)123456max0.400.280.320.720.640.60fxxxxxx模型：Min = -sum(Productor(i):pvalue(i)*x(i);代碼：約束代碼：for(Factory(i):sum(Productor(j):pf(i,j)*x(j) ftotal(i););for(Factory(i): gin(x(i););第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)集合段目標(biāo)函數(shù)約束條件 例2 （MCM-88B）要把七種不同規(guī)格的包裝箱裝到兩輛鐵路平板車(chē)上去，各包裝箱寬、高均相同，但厚度（厘米）與重量（公斤）不同。下表給出各

6、包裝箱的厚度、重量及數(shù)量。 每輛平板車(chē)有10.2米長(zhǎng)的地方可用來(lái)裝包裝箱，載重40噸。由于當(dāng)?shù)刎涍\(yùn)限制，對(duì)C5 , C6 , C7 類(lèi)包裝箱總數(shù)有一個(gè)特別限制：該類(lèi)箱子總厚度不超過(guò)302.7（厘米）。試把包裝箱裝到平板車(chē)上去使得浪費(fèi)空間最小。 第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)12.C1C2C3C4C5C6C7厚度厚度t t 48.7 48.7 52.0 52.0 61.3 61.3 72.0 72.0 48.7 48.7 52.0 52.0 64.0 64.0 重量重量w w 2000 2000 3000 3000 1000 1000 500 500 4000 4000 20

7、00 2000 1000 1000 件數(shù)件數(shù)n n8 87 79 96 66 64 48 8 1. 問(wèn)題分析 題中所有的包裝箱共重89噸，而兩輛平板車(chē)只能載80噸，因此不能都裝下，問(wèn)題是裝哪些箱子，使剩余空間最小。 第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn) 2. 模型建立 設(shè)xij =第i 輛車(chē)裝 Cj 類(lèi)箱子的個(gè)數(shù)，i =1,2 j =1, ,7自然約束：箱數(shù)約束：重量約束：厚度約束：特別約束： ijxZ12,1,2,7jjjxxnj1234567230.54240,1,2iiiiiiixxxxxxxi12345670.4870.5200.6130.7200.4870.5200.6

8、4010.2,1,2iiiiiiixxxxxxxi5670.4870.5200.643.0271,2iiixxxi第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn) 目標(biāo)函數(shù) 212345671max0.4870.5200.6130.7200.4870.5200.640iiiiiiiizxxxxxxx第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn) 約束條件：約束條件： 1234567230.54240,1,2iiiiiiixxxxxxxi12345670.4870.5200.6130.7200.4870.5200.64010.2,1,2iiiiiiixxxxxxxi5670.4870.52

9、00.643.0271,2iiixxxiijxZ12,1,2,7jjjxxnj定義集合段：第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)板車(chē)集合箱子集合派生集合：分配變量集合段第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)模型：212345671max0.4870.5200.6130.7200.4870.5200.640iiiiiiiizxxxxxxxMAX = sum(Car(i):sum(Box(j):hd(j)/100*x(i,j);代碼：1234567230.54240,1,2iiiiiiixxxxxxxi約束：代碼：for(Car(i):sum(Box(j):zl(j)/10

10、00*x(i,j)=40;);第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)for(Car(i):sum(Box(j):hd(j)/100*x(i,j)=10.2;);代碼：代碼：for(Car(i):sum(Box(j)|j#GE#5:hd(j)/100*x(i,j)=3.027;);約束：12345670.4870.5200.6130.7200.4870.5200.64010.2,1,2iiiiiiixxxxxxxi約束：5670.4870.5200.643.0271,2iiixxxi第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)for(Box(j):x(1,j)+x(2,j)=0

11、;);約束：12,1,2,7jjjxxnj約束：ijxZ第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn) 例3 （MCM-89B）機(jī)場(chǎng)通常按“先來(lái)先走”的原則分配飛機(jī)跑道，即當(dāng)飛機(jī)準(zhǔn)備好離開(kāi)登機(jī)口時(shí)，駕駛員電告地面控制中心，加入等候跑道隊(duì)伍。假設(shè)控制中心可以從快速聯(lián)機(jī)數(shù)據(jù)庫(kù)中得到每架飛機(jī)的如下信息：（1）預(yù)定離開(kāi)登機(jī)口的時(shí)間；（2）實(shí)際離開(kāi)登機(jī)口的時(shí)間；（3）機(jī)上乘客人數(shù)；（4）預(yù)定在下一站轉(zhuǎn)機(jī)的人數(shù)和時(shí)間；（5）到達(dá)下一站的預(yù)定時(shí)間。 又設(shè)飛機(jī)有7種型號(hào)，載客量從100人起以50人遞增，乘客最多400人。設(shè)計(jì)一種能使乘客和航空公司雙方滿(mǎn)意的數(shù)學(xué)模型。第第4講講 優(yōu)化模型的優(yōu)化模型的Ling

12、o實(shí)現(xiàn)實(shí)現(xiàn)假設(shè)機(jī)場(chǎng)只有一條跑道供起飛使用，且每架飛機(jī)起飛占用的跑道時(shí)間為d，則n架飛機(jī)起飛時(shí)間可分為時(shí)間窗口：乘客不滿(mǎn)意主要由飛機(jī)晚點(diǎn)而耽誤行程，而航空公司不滿(mǎn)意主要由于飛機(jī)晚點(diǎn)而受到大的損失，定義 為第i架飛機(jī)在第j個(gè)時(shí)間窗口起飛而導(dǎo)致的乘客和航空公司損失費(fèi)用之和0,), 2),(1),dddnd ndijc第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)定義定義目標(biāo)函數(shù) ：約束條件：（1）一個(gè)時(shí)間窗口只能有一架飛機(jī)起飛11,1, 2,nijixjn1,0,ijx第i架飛機(jī)在第(j-1)d，jd)窗口起飛其他11minnnijijjizc x 第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)

13、實(shí)現(xiàn)（2）一架飛機(jī)只選擇一個(gè)時(shí)間窗口起飛（3）下面來(lái)討論損失費(fèi)用損失費(fèi)用由三部分構(gòu)成：晚點(diǎn)導(dǎo)致的燃油附加費(fèi)+轉(zhuǎn)乘乘客由于誤機(jī)的賠償+乘客的不滿(mǎn)意度11,1, 2,nijjxin0,1, ,1, 2,ijxijnijc第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)晚點(diǎn)導(dǎo)致的燃油附加費(fèi)：轉(zhuǎn)乘乘客由于誤機(jī)的賠償：乘客的不滿(mǎn)意度：總的費(fèi)用即為：0,0,0,iiiiiitFk ttkt( )()iiiRtwQ H t(1)()tiiiiDa ePbQ H t( )( )( )ijiiicFtRtDt第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)賠償費(fèi)轉(zhuǎn)機(jī)人數(shù)0-1函數(shù)飛機(jī)人數(shù)折算系數(shù) 假設(shè)早上6

14、點(diǎn)有三架飛機(jī)同時(shí)起飛，其型號(hào)相同，飛行距離相同，到達(dá)終點(diǎn)時(shí)間均為7:20，三架飛機(jī)上乘客數(shù)為350,100,400，每架飛機(jī)上有100人要求轉(zhuǎn)機(jī)，設(shè)起飛時(shí)間窗口長(zhǎng)度為1分鐘，同時(shí)為簡(jiǎn)單起見(jiàn)，將上述費(fèi)用中用到的參數(shù)均設(shè)為1，可得到費(fèi)用矩陣：相應(yīng)的0-1規(guī)劃問(wèn)題最優(yōu)解為：05.898911.896601.69733.422806.739213.5914C010001100第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)26飛機(jī)集合派生集合：飛機(jī)與起飛窗口構(gòu)成的二維矩陣費(fèi)用矩陣一個(gè)時(shí)間窗口只能安排一架飛機(jī)一架飛機(jī)只能在一個(gè)時(shí)間窗口起飛0-1變量第第

15、4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)由鋼管廠訂購(gòu)鋼管，經(jīng)鐵路、公路運(yùn)輸，鋪設(shè)一條鋼管管道1521AAAA1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道鐵路公路S1S7 鋼管廠火車(chē)站450 里程（km)（

16、沿管道建有公路）例4：第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)鋼 廠 i1234567產(chǎn) 量 上 限 is80080010002000200020003000銷(xiāo) 價(jià)ip（ 萬(wàn) 元 ）160155155160155150160鋼廠的產(chǎn)量和銷(xiāo)價(jià)（1單位鋼管=1km管道鋼管）鋼廠產(chǎn)量的下限：500單位鋼管里程(km)300301350351400401450451500運(yùn)價(jià)(萬(wàn)元)2023262932里程(km)5016006017007018008019009011000運(yùn)價(jià)(萬(wàn)元)37445055601單位鋼管的鐵路運(yùn)價(jià)1000km以上每增加1至100km運(yùn)價(jià)增加5萬(wàn)元1單位鋼管的公路

17、運(yùn)價(jià)：0.1萬(wàn)元/km（不足整公里部分按整公里計(jì)）第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)（1）制定鋼管的訂購(gòu)和運(yùn)輸計(jì)劃，使總費(fèi)用最小.A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7基本模型：總費(fèi)用最小的優(yōu)化問(wèn)題總費(fèi)用：訂購(gòu)，運(yùn)輸（由各廠Si經(jīng)鐵路、公路

18、至各點(diǎn)Aj, i=1,7; j=1, 15 ），鋪設(shè)管道Aj Aj+1 （j=1, 14)由Si至Aj的最小購(gòu)運(yùn)費(fèi)用路線(xiàn)及最小費(fèi)用cij 由Si至Aj的最優(yōu)運(yùn)量xij由Aj向Aj Aj-1段鋪設(shè)的長(zhǎng)度yj及向Aj Aj+1段鋪設(shè)的長(zhǎng)度zj最優(yōu)購(gòu)運(yùn)計(jì)劃約束條件鋼廠產(chǎn)量約束：上限和下限（如果生產(chǎn)的話(huà)）運(yùn)量約束：xij對(duì)i求和等于zj 加yj； zj與 yj+1之和等于Aj Aj+1段的長(zhǎng)度ljyj zjAj-1 Aj Aj+1第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)由Aj向Aj Aj-1段鋪設(shè)的運(yùn)量為 1+ +yj= yj( yj+1)/2由Aj向Aj Aj+1段鋪設(shè)的運(yùn)量為 1+ +z

19、j= zj( zj+1)/2)6(0, 0) 5(15, 2 , 1, 7 , 2 , 10, 0, 0)4(14, 2 , 1) 3(15, 2 , 1)2(7 , 2 , 1,5000. .) 1 ()1() 1(21 . 0min15117115171151151zyjiyzxjlyzjyzxisxtsyyzzxcjjijjjjjjiijijijijjjjjjijij第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)的處理約束條件)7 , 2 , 1(,5000151isxijij問(wèn)問(wèn)題題求求解解。，分分解解為為上上述述形形式式的的子子的的那那些些求求解解，再再對(duì)對(duì)解解中中滿(mǎn)滿(mǎn)足足先先松

20、松弛弛為為ixisxbjijijij5000)7, 1(0)151151 個(gè)個(gè)子子問(wèn)問(wèn)題題共共和和分分解解為為71511512)7, 1(5000) isxxaijijjij第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)fi表示鋼廠表示鋼廠i是否使用；是否使用；xij是從鋼廠是從鋼廠i運(yùn)到節(jié)點(diǎn)運(yùn)到節(jié)點(diǎn)j的鋼管量的鋼管量yj是從節(jié)點(diǎn)是從節(jié)點(diǎn)j向左鋪設(shè)的鋼管量；向左鋪設(shè)的鋼管量；zj是向右鋪設(shè)的鋼管量是向右鋪設(shè)的鋼管量 引入0-1變量. 7,.,1, 1 , 0, 0.14,.,1.15,.,1,. 7,.,1,500. .)1 ()1(21 . 0)(151171151151,ifzyjbzyjzyxifsxftszzyyxcpMinijjjjjiijiijijijjjjjjiijijiyj zjAj第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實(shí)現(xiàn)實(shí)現(xiàn)定義集合段：生產(chǎn)上限