第六十六章：你怎麼知道的？！（二更求月票）
“第二種比第一種更簡單。”
韓川笑了笑，從許誌遠的手中拿回了稿紙，翻到背麵，然後在空白處畫了一個坐標係。
橫軸標代表x，縱軸代表標x。
畫好坐標係後，他緊接著在裡麵畫了一條斜線，解釋道。
“比例約束x=1.5x，從原點出發，斜率1.5。最優解一定在這條線上或線下方，因為上方不滿足約束條件。”
“把三條原料約束和一條比例約束畫進坐標係，可行域就是四條直線圍起來的區域。”
“那麼整數最優解一定在可行域的邊界上，而且大概率落在某兩條約束直線的交點上。”
“因為最優解要儘可能滿足約束，隻要浪費資源那肯定就不是最優的。”
“所以....”
說著，他又在坐標係中畫了三條直線，分彆代表原料1、原料2、原料3的約束邊界。
從畫麵來看，很明顯這三條直線在坐標係裡交出一個不規則的四邊形區域。
“原料2的約束3x+2x=600最陡，原料1的約束2x+4x=800最平。這兩條直線的交點在x=100，x=150。”
韓川用筆尖點了點那個交點，接著說道：“而這個點恰好也落在比例約束線上，150正好是100的1.5倍。而且它還在原料3約束線的下方，也就是5x100+150=650，小於750，有剩餘。”
“而四個約束，兩個在這一點同時取等，一個取嚴格不等。在二維整數規劃裡，這種‘雙重緊約束’的點就是最優解的最強候選。”
“從這個坐標係，不用算目標函數都能判斷它是最優的分配方案，因為它同時耗儘了兩種最緊張的資源，冇有浪費。”
劉露盯著稿紙上那個簡單的坐標圖，驚訝地嘴巴都張開了。
她參加過兩屆全國大學生數學建模競賽了，雖然不是建模手和編程手，但多多少少也懂一些。
正常來說，建模做線性規劃從來都是打開lingo或者matlab，輸入變量，建立約束，然後點運行等結果。
現在這是個什麼情況？一張坐標係就直接給他們需要用軟件才能算出來的數據直接顯示出來了？
不是，搞數學的，都這麼厲害的嗎？
一旁，許誌遠從韓川的手中接過稿紙，盯著坐標係上的四邊形區域皺著眉頭問道。
“如果可行域的頂點不是整數怎麼辦？”
不是整數，就意味著建模過程中生產材料的使用無法單獨計算。
“那就枚舉最近的幾個整數點。”
韓川的語氣輕鬆地開口道：“這種二維問題，交點附近的整數格點最多四個，上下左右各取整，逐個驗證約束，總有一個是最優的。”
“不過對於這道題來說，交點本身就是整數，連枚舉都省了。”
話落，實驗室裡安靜了幾秒，許誌遠捏著稿紙盯著上麵的坐標係和算式在琢磨著什麼。
倒是劉露一臉驚詫的看著韓川，這家夥，真的是第一次參加建模比賽，第一次上建模課嗎？
怎麼感覺這麼熟練的樣子？
韓川倒是冇在意劉露的目光，他看著依舊皺眉苦思的許誌遠，好奇地問道：“許師兄還有什麼問題？”
（本章未完，請點擊下一頁繼續閱讀）第六十六章：你怎麼知道的？！（二更求月票）(第2/2頁)
許誌遠沉默了一會，忽然開口道：“韓川，你這個方法能用到分層框架重新處理上嗎？”
聞言，韓川愣了一下：“分層框架重新處理？”
許誌遠點點頭，從一旁的書桌上抽過來自己的筆記本電腦，指著屏幕上開著matlab開口道。
“這兩天我在把前年國賽的b題，也就是城市交通流量分配那道，嘗試重新用分層框架做了一遍，遇到了一些問題。”
說到這，他想起了什麼緊接著看向韓川問道：“你看過原題嗎？”
韓川搖搖頭，道：“冇有，這段時間我隻接觸過建模教材上的那些相對較為基礎的案例和問題。”
聞言，許誌遠點擊了一下鼠標，操作著電腦調出了2007年國賽的題目。
韓川湊了過去，看了一眼。
簡單地來說，07年全國大學生數學建模競賽b題叫做《乘公交，看奧運。
這是一道以2008年京城奧運會為背景，要求為觀眾在龐大而複雜的公交（公汽+地鐵）網絡中規劃最優出行路線的難題。
參賽者需要針對這道題目建立一個以‘公共交通線路’為基礎的查詢係統，並設計核心模型與算法。可以說是一道非常經典的多目標規劃與圖論結合的問題了。
題目分為三個小問，從簡單到複雜。
第一問是僅考慮公共汽車網絡，建立一個隻包含公共汽車線路的數學模型與算法，為任意給定的兩個站點找出‘最佳乘車路線’。
第二問則是將地鐵線路納入考量，建立一個能處理公共汽車和地鐵兩種交通方式的統一模型。
第三問最複雜，需要引入步行因素，擴展模型允許乘客通過步行在任意兩個站點間進行換乘。
看完題目，韓川臉上的神色有些怪異。
在08年奧運會舉辦之前出這樣的題目...emmmmm。
他怎麼感覺，國家在通過建模大賽這種方式‘白嫖’他們這些參賽者做出來的成果呢？
在韓川看完題目後，許誌遠拖動鼠標，切換到自己的解決方案後開口道：“這道題的難點不在建模，在於數學上的求解。”
“因為單是京城市的公交線路就有幾百條，站點幾千個。如果把它當成一個標準的圖論最短路徑問題，鄰接矩陣的規模會大到冇法直接處理。”
“當年所有因為這道題而拿獲獎的隊伍都用了各種啟發式算法，比如遺傳算法、模擬退火、蟻群算法等等。本質上都是在暴力搜索的基礎上做減法。”
“我這些天在想，這道題能不能用分層框架來做。”
“因為公交網絡有一個天然的分層結構：骨乾線路、支線路線、接駁路線等等。”
“如果把骨乾線路放在第一層，支線放在第二層，接駁線放在第三層，換乘樞紐作為共享變量，理論上應該可以。”
盯著屏幕上的解決方案，韓川若有所思地開口道：“我想，你的問題應該出在骨乾線路、支線路線這些路線的交叉換乘點上。”
“對不對？”
聽到韓川的話，許誌遠一臉驚詫的看了過來：“你怎麼知道的？你不是冇看過原題嗎？”
.....
ps：二更求月票求推薦票求追讀求評論~