結(jié)冰路面鋪沙問題

1、結(jié)冰路面鋪沙問題1問題重述在一個村莊中，應(yīng)對路面結(jié)冰的措施是向路面上鋪沙防滑。鋪沙工作由養(yǎng)路 站負(fù)責(zé)，養(yǎng)路站位于交匯點(diǎn)1處，鋪沙所使用的卡車就在此養(yǎng)路站內(nèi)。 卡車的載 沙量足夠大，能夠不需要中途加沙就完成所有路面的鋪沙任務(wù)。由于有些街道是單行線，因此有時候可能需要多次經(jīng)過一條街道。 請為鋪沙車選擇一條路線，使 得完成所有街道鋪沙所需的路程最短。 對于雙向的街道，需要為每個方向的車道 分別進(jìn)行鋪沙。本文將研究以下問題：（1）卡車由養(yǎng)路站出發(fā)，以最短的路程完成所有街道的鋪沙工作；（2）卡車盡可能少的多次經(jīng)過一條街道；2問題分析本題要求我們通過建立模型和計(jì)算，設(shè)計(jì)出卡車需行走的最短路程，由題可 知卡

2、車為村莊街道都鋪沙，且卡車在養(yǎng)路站內(nèi)，卡車載沙量可一次將村莊的街道 全部鋪沙。卡車鋪沙的基本原則只有一個，成本要低。據(jù)題，題目要求設(shè)計(jì)出最短路線。因此在此模型中我們需要根據(jù)圖中線路確 定路線，并計(jì)算出總路程，進(jìn)行比較，得出最短路程。3. 基本假設(shè)（1）卡車載重量足夠大；（2）沙子量足夠；（3）車子不打滑；（4）村子路面平整；（5）工作期間不用換司機(jī)；（6）卡車在工作期間不會壞；（7）卡車的載重和油耗量無關(guān)。4. 符號說明符號路線距離（m）a1 2150b2 3130c3 2140d3 4100e4 3100f1 5165g5 1165h2 5230i2 6160j6 2170k7 3200l4

3、 8190m8 4180n5 6144o6 5144P6 7128q7 6122r7 8109s9 5194t6 9218u610174v106174w107233x711185y11 7185z811141A812190B910148C11 10135D1211110L周長5. 模型建立與求解假設(shè)卡車不走重復(fù)路線，將每一條路走完并鋪完沙，最短路程為4814m如題所示，要想得出最短路線，首先要得出此次 鋪沙共有多少種鋪沙路線。通過二項(xiàng)式，由出發(fā)，1共有兩條路線，那么就有2- 2種方法；假設(shè)繼續(xù)由出發(fā)，那么就有丄3種選擇方法；由出發(fā)會有亠2種1選擇方法；由出發(fā)，那么就有-二2種選擇方法；由1出發(fā)

4、，那么就有土 2種選擇方法；由出發(fā)，那么就有A5種選擇方法；由出發(fā)，那么就有丄4種選擇方法；1由出發(fā)，那么就有A 3種選擇方法；由出發(fā)，那么 就有土 2種選擇方法；由出發(fā)，那么就有- 2種選擇1方法；由？出發(fā)，那么就有A 2種選擇方法；由？出 發(fā)，那么就有1種選擇方法；通過利用用二項(xiàng)式的方法，將上面所有選擇方法 相乘，得出路面結(jié)冰鋪沙的所有路線共計(jì)多少條。下面是由公式得出的答案：1 * 1 * 丄 1 * 二 1 * 二 1 * aJ * ： 1 * ： 1 * 丄 1 * .-. 1 *2 32225 - 4 - 3221'* 1=23040因?yàn)榭偮肪€為23040條，且理想最短路線長度為4814MT*起點(diǎn)TU230,651601702090122J 28194174185185M1I2110174然而23040條路線中，其中必定有距離與理想距離相差非常大的路線，因此通過排除法，排除掉了 10354條距離大于8000M的路線，