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

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