幾個(gè)“簡(jiǎn)單”問題數(shù)學(xué)模型

1、鈔票問題（Cash Problem）背包問題（Knapsack problem） 裝箱問題（Bin Packing）城市公交查詢系統(tǒng)的數(shù)學(xué)模型電梯問題的數(shù)學(xué)模型流水線設(shè)計(jì)問題幾個(gè)“簡(jiǎn)單”的問題1背包問題（Knapsack problem-一般情形） 有一個(gè)容量為b的背包和數(shù)量足夠多的價(jià)值和體積分別為c1, c2,.,cn和a1, a2,.,an的物品，問如何裝這些物品使得價(jià)值最大？數(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-特殊情形） 有一個(gè)容量為b的背包和n個(gè)價(jià)值和體積分別為c1, c2,.,cn和a1, a2,.,an的物品，問如何裝這些物品使得價(jià)值最大？數(shù)學(xué)模型：3Greedy Algorithm價(jià)值大的物品優(yōu)先裝，不妨假設(shè)：4四、城市公交查詢系統(tǒng)的數(shù)學(xué)模型問題： 第29屆奧運(yùn)會(huì)明年8月將在北京舉行，北京的公交將面臨更大的挑戰(zhàn)。這些年來，公共交通工具（簡(jiǎn)稱公交，包括公汽、地鐵等）發(fā)展迅速。目前北京市的公交線路已達(dá)800條以上，使得公

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

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

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

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