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

1、數(shù)學建模課程綜合設計數(shù)學建模課程綜合設計 王 丹 2016 例1 設某工廠有甲、乙、丙、丁四個車間，生產A、B、C、D、E、F六種產品，根據(jù)機車性能和以前的生產情況，得知生產每單位產品所需各車間的工作時數(shù)、每個車間在一個季度工作時數(shù)的上限以及產品的價格，如下表所示。問：每種產品每季度各應生產多少，才能使這個工廠每季度生產總值達到最大？ 第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實現(xiàn)實現(xiàn)3. 產品產品車間車間A AB BC CD DE EF F 每個車間每季度每個車間每季度 工作時數(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 單價（元）單價（元）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實現(xiàn)實現(xiàn) 解 以 x1 x6 分別表示每季度生產產品A、B、C、D、E、F的單位數(shù)，于是它們需滿足目標函數(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實現(xiàn)實現(xiàn)LINGO實現(xiàn)實現(xiàn)第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實現(xiàn)實現(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：直接轉換第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實現(xiàn)實現(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實現(xiàn)實現(xiàn)目標函數(shù)約束條件整數(shù)約束第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實現(xiàn)實現(xiàn)方法2：使用集合變量（1）車間集合：Factory/1.4/: ftotal;（2）產品集合：Productor/A.F/: pvalue,x;車間工時數(shù)產品價值待求變量（3）加工時數(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實現(xiàn)實現(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實現(xiàn)實現(xiàn)集合段目標函數(shù)約束條件 例2 （MCM-88B）要把七種不同規(guī)格的包裝箱裝到兩輛鐵路平板車上去，各包裝箱寬、高均相同，但厚度（厘米）與重量（公斤）不同。下表給出各

6、包裝箱的厚度、重量及數(shù)量。 每輛平板車有10.2米長的地方可用來裝包裝箱，載重40噸。由于當?shù)刎涍\限制，對C5 , C6 , C7 類包裝箱總數(shù)有一個特別限制：該類箱子總厚度不超過302.7（厘米）。試把包裝箱裝到平板車上去使得浪費空間最小。 第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實現(xiàn)實現(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. 問題分析 題中所有的包裝箱共重89噸，而兩輛平板車只能載80噸，因此不能都裝下，問題是裝哪些箱子，使剩余空間最小。 第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實現(xiàn)實現(xiàn) 2. 模型建立 設xij =第i 輛車裝 Cj 類箱子的個數(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實現(xiàn)實現(xiàn) 目標函數(shù) 212345671max0.4870.5200.6130.7200.4870.5200.640iiiiiiiizxxxxxxx第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實現(xiàn)實現(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實現(xiàn)實現(xiàn)板車集合箱子集合派生集合：分配變量集合段第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實現(xiàn)實現(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實現(xiàn)實現(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實現(xiàn)實現(xiàn)for(Box(j):x(1,j)+x(2,j)=0

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

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

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

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

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

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

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

18、至各點Aj, i=1,7; j=1, 15 ），鋪設管道Aj Aj+1 （j=1, 14)由Si至Aj的最小購運費用路線及最小費用cij 由Si至Aj的最優(yōu)運量xij由Aj向Aj Aj-1段鋪設的長度yj及向Aj Aj+1段鋪設的長度zj最優(yōu)購運計劃約束條件鋼廠產量約束：上限和下限（如果生產的話）運量約束：xij對i求和等于zj 加yj； zj與 yj+1之和等于Aj Aj+1段的長度ljyj zjAj-1 Aj Aj+1第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實現(xiàn)實現(xiàn)由Aj向Aj Aj-1段鋪設的運量為 1+ +yj= yj( yj+1)/2由Aj向Aj Aj+1段鋪設的運量為 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實現(xiàn)實現(xiàn)的處理約束條件)7 , 2 , 1(,5000151isxijij問問題題求求解解。，分分解解為為上上述述形形式式的的子子的的那那些些求求解解，再再對對解解中中滿滿足足先先松

20、松弛弛為為ixisxbjijijij5000)7, 1(0)151151 個個子子問問題題共共和和分分解解為為71511512)7, 1(5000) isxxaijijjij第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實現(xiàn)實現(xiàn)fi表示鋼廠表示鋼廠i是否使用；是否使用；xij是從鋼廠是從鋼廠i運到節(jié)點運到節(jié)點j的鋼管量的鋼管量yj是從節(jié)點是從節(jié)點j向左鋪設的鋼管量；向左鋪設的鋼管量；zj是向右鋪設的鋼管量是向右鋪設的鋼管量 引入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實現(xiàn)實現(xiàn)第第4講講 優(yōu)化模型的優(yōu)化模型的Lingo實現(xiàn)實現(xiàn)定義集合段：生產上限