幾個“簡單”問題數(shù)學(xué)模型

1、鈔票問題（Cash Problem）背包問題（Knapsack problem） 裝箱問題（Bin Packing）城市公交查詢系統(tǒng)的數(shù)學(xué)模型電梯問題的數(shù)學(xué)模型流水線設(shè)計問題幾個“簡單”的問題1背包問題（Knapsack problem-一般情形） 有一個容量為b的背包和數(shù)量足夠多的價值和體積分別為c1, c2,.,cn和a1, a2,.,an的物品，問如何裝這些物品使得價值最大？數(shù)學(xué)模型：由鈔票問題想起的： 現(xiàn)需要數(shù)量為C的鈔票,鈔票規(guī)格有1分、5分；1角、2角、5角； 1元、5元、10元、50元和100元。問最少需要多少張這些規(guī)格的鈔票能夠支付數(shù)量為C的鈔票？數(shù)學(xué)模型：2裝箱問題（Bin

2、Packing）： 有一批容量為1的箱子和體積分別為a1, a2,.,an的物品，問最少需要多少箱子能夠裝下這些物品？數(shù)學(xué)模型：0-1背包問題（Knapsack problem-特殊情形） 有一個容量為b的背包和n個價值和體積分別為c1, c2,.,cn和a1, a2,.,an的物品，問如何裝這些物品使得價值最大？數(shù)學(xué)模型：3Greedy Algorithm價值大的物品優(yōu)先裝，不妨假設(shè)：4四、城市公交查詢系統(tǒng)的數(shù)學(xué)模型問題： 第29屆奧運會明年8月將在北京舉行，北京的公交將面臨更大的挑戰(zhàn)。這些年來，公共交通工具（簡稱公交，包括公汽、地鐵等）發(fā)展迅速。目前北京市的公交線路已達800條以上，使得公

3、眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。針對市場需求，某公司準備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統(tǒng)。為了設(shè)計這樣一個系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實際情況出發(fā)考慮，滿足查詢者的各種不同需求。請你們解決如下問題：1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對起始站終到站之間的最佳路線（要有清晰的評價說明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485 (4)、S0008S0073 (5)、S0148S0485 (6)、S008

4、7S36762、同時考慮公汽與地鐵線路，解決以上問題。3、假設(shè)又知道所有站點之間的步行時間，請你給出任意兩站點之間線路選擇問題的數(shù)學(xué)模型?！靖戒?】基本參數(shù)設(shè)定:相鄰公汽站平均行駛時間(包括停站時間)： 3分鐘相鄰地鐵站平均行駛時間(包括停站時間)： 2.5分鐘公汽換乘公汽平均耗時： 5分鐘(其中步行時間2分鐘)地鐵換乘地鐵平均耗時： 4分鐘(其中步行時間2分鐘)地鐵換乘公汽平均耗時： 7分鐘(其中步行時間4分鐘)公汽換乘地鐵平均耗時： 6分鐘(其中步行時間4分鐘)公汽票價：分為單一票價與分段計價兩種，標記于線路后；其中分段計價的票價為：020站：1元；2140站：2元；40站以上：3元地鐵票

5、價：3元（無論地鐵線路間是否換乘）注：以上參數(shù)均為簡化問題而作的假設(shè)，未必與實際數(shù)據(jù)完全吻合?！靖戒?】公交線路及相關(guān)信息 （見數(shù)據(jù)文件B2007data.rar）5五、電梯問題的數(shù)學(xué)模型 在日常生活中,我們大家經(jīng)常要乘電梯。但是在當前電梯運行系統(tǒng)中, 乘客是在線到達的，也就是事先不知道他們的有關(guān)信息。不知道有多少乘客要乘電梯，他們何時到達.在乘客到達并且未進入電梯前，也僅僅只知道他們所處的位置和要乘的方向，并不知道他們要到達什么地方。目前,電梯的主要按鈕是在電梯內(nèi), 乘客到達僅僅只告訴電梯要上或下，電梯并不知道更多的信息。請您分析這種信息不完全對電梯運行帶來的損失,并據(jù)此提出電梯按鈕設(shè)計的改

6、進意見,分析改進效果.我們是否能夠?qū)粹o設(shè)計在電梯外，使得電梯的運行效率得到提高呢？在乘電梯時,由于乘客都是在線到達,我們是否能夠基于這一特征來建立電梯在線運行的數(shù)學(xué)模型呢? 在乘電梯時，等待常常是不可避免的，我們自然要問:通常情況下，我們需要等待多長時間才能到達目的地呢?有沒有一種好的電梯運行方案使得乘客能夠盡可能快到達呢? 為此,我們需要建立電梯運行的數(shù)學(xué)模型,并回答如下問題:(1)在當前電梯運行系統(tǒng)中, 乘客是在線到達的.請分析乘客在線到達的特征， 建立電梯在線運行的數(shù)學(xué)模型,研究電梯的最優(yōu)運行方案,探討乘客的滿意情況.(2)研究電梯的按鈕設(shè)計,對電梯的按鈕提出改進建議,并分析改進效果. (3)在離線情形(所有信息已知的情形)下, 建立電梯運行的數(shù)學(xué)模型，并比較離線和在線兩種情形下電梯運行的優(yōu)化方案和電梯的運行效率.(4)由于電梯是一個系統(tǒng)，請先研究單臺電梯的情形，再對多臺電梯系統(tǒng)進行全面研究,分析,討論.并請你采集電梯數(shù)據(jù)驗證你的模型.6六、流水線設(shè)計問題某縫紉機廠要設(shè)計一條生產(chǎn)流水線，流水線有兩條