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