建模需要思想也需要數(shù)學(xué)訓(xùn)練和手上功夫B題綜合評述

第1 9 卷 建模 專輯 工 程 數(shù)學(xué) 學(xué)報 1 9 s p p 加 月 J OURNAL OF ENGI NEERI NG M ATHEM ATI C S F e b 2 0 0 2 文章編號 1 0 0 5 3 0 8 5 2 0 0 2 0 5 0 1 0 7 0 6 建模需 要 思想 也需要數(shù) 學(xué)訓(xùn) 練和 手 上功 夫 B題綜合評 述 劉 寶 光 北 京理 工 大學(xué) 北京 1 0 0 0 8 1 摘要 本 文對 于 2 O O 1年 全 國太學(xué) 生教 學(xué) 建橫 競賽 B題 的解答 從模 型框 架 模型 建立 和 模型 求解 等 三千 方面 鯖出評 述 美 鍵 詞 公 交車 調(diào)度 敦 學(xué)規(guī) 劃模 型 目標規(guī) 劃 分 糞 號 A MS 2 0 0 0 9 0 C 0 8 中舶 分類 號 Tb l 1 4 1 文獻標 識 碼 A 1 模型框架 正 如題 目的標題所 示 這是一個 公交車調(diào) 度問題 題 目給定 了限制條件 和 目標 要求在 一 定統(tǒng)計數(shù) 據(jù)資料 的基礎(chǔ) 上 構(gòu)建 理論模 型并據(jù) 以實現(xiàn) 調(diào)度 應(yīng) 當指 出 構(gòu)建 明確 完整 的數(shù) 學(xué)模型 是本題懈案要求 的一個本質(zhì)性的方面 事實上 每一天 在全國各地 都有無數(shù)的車 隊調(diào) 度在作 這 類 問題 他 們遵 守各 自的約束 追 求各 自的 目標 用 他們 習(xí)慣 了的方 法調(diào)度 車 輛 指揮 著 全國各地 公交車 的運行 他們 不見得都有 多高深 的數(shù)學(xué)修養(yǎng) 所 給 出的調(diào) 度方案也 不見 得都是合 理 的優(yōu) 良的 本題 的意義 并 非要參賽者 習(xí)作普通 的車 隊調(diào)度 而是 要求對這 一 問題用數(shù)學(xué)方法作更深一層次的探討 這次有 占相當比例的答 卷沒有完成明確 完整的模型 的建立 只從數(shù) 據(jù) 出發(fā) 憑某 種直 觀方法給 出一個可行 的調(diào)度 方案 應(yīng) 當說 這是不符 合題 目要 求 的 因而都不在 得獎 者之列 考察題 意最 直接 的想法 會是 建立 數(shù)學(xué)規(guī)劃模 型 在培 出 了數(shù)學(xué) 模 型 的答卷 中 恐 怕有 七 成 以上是用 的各種 不同 的數(shù)學(xué)規(guī)劃模 型 模 型的變量 既然題 目要求 設(shè)計 調(diào)度方案 最 自然 的 就是 發(fā) 車 時 刻 系列 T 1 T2 但 這一 變量 其 維數(shù) m 很高 而且是不定 的 這 會 為使 用某 些成 熟 的優(yōu) 化數(shù) 值 方法 求解帶來 麻煩 一種適 當?shù)暮?化方法是 將 全天 分作若干 時段 在 每一類時 段中等 間距發(fā)車 這 時 模型 的變量可取 作各 類時段 的發(fā) 車 時問間距 從 而可建立有 確定 的低 維數(shù) 的數(shù)學(xué)規(guī)劃模 型 例如 將 全天分為 平峰 時段和 高峰時段 分別 間距 f 1 和 t 2 分 鐘發(fā)一班 車 則 可得 到 以 f 2 為變量 的 2維 模 型 題 目稱 調(diào)度 方案應(yīng) 滿足 四項要 求 若 記 i為乘 客候車時 間 為早 高峰 時乘客候 車時 間 為 車輛載 客人數(shù) 則要 求為 a 1 O分 鐘 b 5分 鐘 c 5 0 d P 1 2 0 維普資訊 更多數(shù)學(xué)建模資料請關(guān)注微店店鋪 數(shù)學(xué)建模學(xué)習(xí)交流 1 0 8 工程教學(xué)學(xué)報 第 1 9卷 按照題 目所列 的乘 車人數(shù) 統(tǒng)計數(shù)據(jù) 嚴格 滿足這 四項要 求 的調(diào) 度方 案 是不 存 在 的 而題 目只 是 限定 為 硬性 約 束 不 應(yīng) 違反 其他 三條 使用 一 般 不要 措 詞 即是 說 可 以違反 但應(yīng) 使 違反程度 盡可能低 這很 自然 導(dǎo) 向使 用 目標 規(guī) 劃 g o a l p r o g r a mmi n g 而且粗 看 起來 如 下模 型是合理 的 rai n 1 f 5 1 0 2 r 5 3 p 5 0 4 1 2 0 5 1 z 6 n t 2 s s 0 7 然而 由于約 束 2 和 3 要對 每個乘 客成立 約 束 4 和 5 要 對 每輛 車 每個路 段 指相鄰 二車 站 間 的道路 區(qū)段 成立 這 一模 型只有觀 賞意 義 是難 以處 理 的 將 和 r換 作 所有乘 客 的最 大候車 時間 換作各 車各路 段的最小 載客數(shù) 便 真 的是作成 了三個 約束 但 此時 f和 作 為 1 2 的函數(shù)難 以給 出表 達 不僅 如此 因為 和 r是 以分鐘為單 位 的等候時 間數(shù) 是車 上的人數(shù) 二者 是不可 比較的 所 以會 給權(quán) 因子 的設(shè) 置帶 來 困難 這樣 的模型 在答 卷 中有 為 數(shù)極少 如上述 這 一模型 實際上 是不 能操作 的 必 須另外想 變通 的方 法 一 種作法 是計算 兩種 時段 中超 時候 車 1 0 r 5 的乘 客數(shù) 在各 段乘 客總數(shù) 中所 占的百 分 比 作為 l t 2 的 函數(shù) 計算 載 客人 數(shù) p 2 t2左側(cè)相鄰 T 值 為 Tf 則 規(guī)定 T 1 L 1 等等 或按其他 規(guī)則 此處 不贅述 設(shè) 以 1 2 標 記車站 從 J一1站到 J站 的站 問行車 時間 包 括 J站 的停車時 間 記 為 J 2 3 n 第 班車駛 離 站 的時 刻記 作 T 則有 i 1 J 2 3 1 1 2 2 這便 給 出了每一班 車 的行 車時 刻表 為了求 g 2 和 p 2 需 要計 算 每 班 車駛 離各 站 時 車上 的乘 客 數(shù) 1 2 m J 1 2 一1 而為 了計算 g 1 1 2 和 g 2 l 2 需要 計算 每個乘 客的候 車時間 這 些都要 從乘 客流 的統(tǒng)計數(shù) 據(jù)出發(fā) 首先 對 每一 車站 J引人 乘客來站 的時 間密度 即單位 時 間來 站乘 客數(shù) 記 以函數(shù) J 1 2 一1 統(tǒng) 計數(shù) 據(jù)恰 好 給出每隔 6 0分鐘一個 點上 的平 均密度 值 據(jù)此 或用插 值或用 擬臺 總可 以得 出 f 的一 個近似 表示 這里最 簡單 的是用 階梯 函數(shù) 作分 段線性 插 值得一 折線 函數(shù)也很 簡單好用 答 卷上 對此一細 節(jié)的處理花樣 繁 多 有 的甚 至作 了長篇 幅 的討論 其 實 這 在整個 解案 中不過是 一個 細節(jié) 下 功夫過大則 勢必 舍本 逐 末 類 似 可建 立乘 客離 站的時 間密 度函數(shù) c f 2 3 雖說乘 客來 站是 分散 的 離站 是成批 的 但 統(tǒng)計數(shù) 據(jù)中并未 反映這一 區(qū)別 因而在計算 中也就作 完全一樣 的處 理 乘 客等 候 時間 的計 算較 為 曲折 這里使用將乘 客 按等 候 時間長 短 分類 統(tǒng) 計 的方 法 為 此 設(shè)第 班車 到 達 站 時 站 上 已 等 候 過 h輛 車 而 仍 未 能 上 車 的 乘 客 數(shù) 為 以下 將 和 1 2 一1 k 1 2 m 用 對 k和 二 重遞推 的方式表述 出來 注 意 對 任 意 的 當 0 因 為 j 0 為 時 間 段 0 J 出 1 其 中的 T D 1 理解 作 題 目所討 論 的全天 的開始 時間 即 To To 5 6 0 j 1 2 一 l 的來 客數(shù) 所 以有 1 3 1 4 維普資訊 1 1 0 工程數(shù)學(xué)學(xué)報 第 1 9卷 對 于 k 1 根據(jù) 1 3 式 對 任意 的 J l 0 為 已知 以下證 明 對 于任 意 k 若 對任意 k一1 任意 J h 為 已知 則 可 以導(dǎo) 出 1 2 n 一1和 1 h 1 2 n 一1 h k 我 們 假 設(shè) 乘 客 按 先 到 先 上 車 的 隊 列 原則 乘 車 記 h 為 站 上等待最 久 的乘 客 的候車趟數(shù) 即 h ma xI h l 0 我們規(guī) 定 0 0 L 0 O o 依 次對 于 1 2 一1 記 n 目 m a x I 1 一l 吐 t d t 0 1 5 一l 即第 k班車 到達j站 乘 客下車后 車 上仍 留下 的乘 客數(shù) 這 里 的 仍如 1 4 式 此 時 可容 納的乘 客上車數(shù) 上 界 1 2 0一 1 6 這 時有 m i n 1 2 0 n w j h 1 7 0 h l J m a x h l h 0 或使 w k j r l 1 8 1 8 式 的意思是按候車趟數(shù)從多到少依次累加 h k j 一1 直到苜次出現(xiàn)大 于 6 則停 止 累加 以累加 到的最后 的 最 小的 一個 h作為 l 如果 直加至 目 0 仍不 大于 則 h l O o 然后 若 h l J 0 則 l 1 0 否則 h 1 一 1 h 1 2 l j一1 1 9 十 1 H 一1 一 一 2 0 1 0 則如 1 3 式 現(xiàn) 在可 以建 立模 型 8 一 1 0 中的各個 函數(shù) 了 利用 P 有 1 l 5 0 g 3 t l t 2 且 廠 2 注意 P L 的構(gòu) 造過程 已保證 了約束條件 9 式 的成立 因而無須再 求 函數(shù) 1 2 該約 束 在建 成 的模 型 中也不再 出現(xiàn) 為求 g l 和 g 2 注意 到至 時刻 站上 已候 輛車 而仍 未能上 車 的乘 客 的等候 時間滿足 一 L 一 f或 一 L 一 一 I j 以保守 的原則取其 下限 則有 l 一L一 5 1 2 2 2 2 3 維普資訊 建 模專 輯 建模 需 要 思想 也需 要數(shù) 學(xué)訓(xùn) 練 和手 上 功 夫 三個 函數(shù) 都是百 分率 數(shù) 值 上有 良好 的可 比性 可 以簡 單地 取 其 加 權(quán) 和作 為單 一 目標 函 數(shù) 題 目中沒有關(guān) 于優(yōu)先權(quán) 及權(quán)重 的規(guī)定 可 以認為公交 公 司利 益與乘 客利益等 權(quán) 并且 表現(xiàn) 乘 客利益的二 函數(shù) g 和 g 2等權(quán) 這樣便有 2 1 g 3 1 2 2 4 2 5 可 以以此作為求 解 2的規(guī) 劃模型 三個 函數(shù) 的 表述 是該 題 目的最 具 難度 之點 構(gòu) 想 一個 如上一 段 所述 的模 型框架 并不很 難 要 表述 出這 些 函數(shù)從 而完成 模型 的建 立 卻是 對參賽 者 的數(shù) 學(xué)訓(xùn) 練 和手 上功 夫 的考驗 這 次 的答卷 中有 表現(xiàn)極好 的 但 是不 多 從這一 現(xiàn)象是否可 以提 出一個 問題 近一些年來 在教學(xué) 中很注意 思想性 的方面 學(xué)生 在這一方 面也確 實有很大提 高 但 對于 實際的手上 功夫 的訓(xùn)練卻 漸趨弱化 固然技術(shù) 的進步代 替了許 多手上的操作 但同時卻 派生 出許 多新 的需 要人工操作 的 事 情 即如本題 不 是計算技 術(shù) 如今 天的進步 也就不會 提 出這樣 的題 目 在教學(xué)上 應(yīng) 當如何 適 應(yīng)情況 的這 種變化 呢 3 模 型求解 此次 的答 卷 中 模 型建立與其 后的求解計算 兩相 脫節(jié) 者所 在 多有 這 是 不好 的 建立 了模 型 而 又不用 它 去尋解案 那 么建 模 又是 為了什么呢 所 建 的模 型難 解 不 會解 那 就 應(yīng) 當再 進 一 步抽 象 再引 入新 的假設(shè) 以簡 化模 型 直到你能夠 處理 它 為止 包 括 引 出理 論結(jié)果 或數(shù)值 求 解 前面兩段 中 我們先是 作等 間隔發(fā)車 的假設(shè) 以便將 一個有不確 定 的高維數(shù) 的問題 變?yōu)橐?個 2維問題 然后 又將本 應(yīng)是面 向各單個乘客 和單 個車路段 的 目標要 求 集總化為 三個百分率 函數(shù) 這些 都是 為了使得做 成 的模型 能夠作求解處 理 模 型 2 4 一 2 5 是 容 易求解 的 作 為一 個非線性規(guī)劃 問題 只有 2 維 且 約束 極為簡單 除 非 目標 函數(shù) 的求值 不 能實現(xiàn) 總 可 以用 某種直 接方法 不 涉及求 導(dǎo) 數(shù) 求得 近 似解 上 段 中函 數(shù) 和 h 的二 重遞推式 的表述 實際上就 給 出了對 給定 的 I 2 值求 這些 函數(shù) 值 的算法 2 1 2 2 和 2 3 式則表示 如何用這些 函數(shù) 值完 成 目標 函數(shù)求 值 運算 而實 際上 2 1 式 的分子是 臺條 件的 的個數(shù) 的計 數(shù)器 2 2 和 2 3 式 的分 子是 臺條件 f h 值 的累加 因此 g 1 g 2 和 g 3 的計算 可以放人到為產(chǎn)生 P 和 的對 k和J的 2 重循 環(huán) 中 隨產(chǎn)生 隨累加 以免去對這些 不再有用 的 和 h 的存儲 使用 參賽 者熟 知的 Ma t t a b語言 容易 作成給 定 f 2 值 后產(chǎn)生 目標 函數(shù)值 的程序段 再 使用 Ma t t a b的優(yōu)化工 具 箱 的程 序即可 完成求解 這 當 中或許 要為 t 2 設(shè) 一個合理 的上界 或 許要 通 過 隨機 搜索選一 個好 一點 的初 始點 都是容 易做到 的事情 有的答卷 中選用 遺 傳算 法求 解 此模 型 單從 其 目標 函數(shù)構(gòu) 成復(fù) 雜 可 以求值而 難于求導(dǎo) 或作其他處理 等特點 這 一選擇 就是 正確 的 另外要 指 出一點 如果 將 函數(shù) g 3和 g 進一 步分拆成兩 項 即分 別單 獨計算平 峰時段 和高 峰 時段的載 客數(shù)不 到 5 0的車路段百 分率和候 車超 時乘客的百分 率 并且對 兩種時段 的交接 點 處 的情況作適 當處理 目標 函數(shù)就 可 以化 為可 分離 的形式 即 f 2 f l 1 2 2 這 時就 可 以分 別求解兩 個一維 問題 f 1 t 1 1 0 2 2 0 1 4 0 知 維普資訊 1 1 2 工程數(shù)學(xué)學(xué)報 第 1 9卷 比如分 別為 f 1 和 2 設(shè) 定合理 的上 界 就可 以用 0 6 1 8 方 法求 解 其 關(guān)鍵 的運算還是 目標 函數(shù) 和 的求 值 設(shè) 得解為 和 f 如果 f 則 f 就是所 求之解 4結(jié)束語 作 者認為 這個 題 目的難 點在 于 目標 函數(shù) 的具體 表述 如 本 文第 2段 如 果 判定建 立此 表述 的難度是適 當?shù)?那 么這個題 目是選得很 好 的 事實 上 盡 管漂 亮 的答 卷不 多 怛眾 多答 卷上對 于這樣一 個活 生生 的相 當復(fù)雜 的實 際 問題 表 現(xiàn) 出分 析的 思 路是舍 理 的 也很 有深 度 為解決 問題 表現(xiàn) 的思路 也很 廣 不足 之處 從總體上說 相對 于完成表 述 顯得數(shù) 學(xué)訓(xùn)練和手 上功 夫欠 缺些 或難 度太 了些 相 對于 三天集 中時間 或 的確 是訓(xùn) 練 差 了些 或二 者兼有 以供 討論 建模 是重要 的 在各 類 信息 系統(tǒng)平 臺 日趨完善 的今 天 如何從 中發(fā)現(xiàn) 知識 如何優(yōu) 化決策 人們 祈求建模 而建 模不光要 有思想 也 要 靠人 工完成 表 述 這要 求 數(shù) 學(xué)訓(xùn) 練和 手上 功 夫 致謝 本文參 考 了大量 的參 賽者 的答 卷 和 全 國及 北 京眷 區(qū)兩級 閱卷組 的評 論 意見 并特 別 引用 了供題 者所提供 的參考答 案 謹在 此一井致