【文章內(nèi)容簡(jiǎn)介】 1 1 2 4 3 5 3 2 4 1 2 3 2 1 3 4 2 3 4 5 1 2 3 1 4 5 3 2 1 3 4 3 2 4 2 3 1 3 2 1 最優(yōu)化在數(shù)學(xué)建模中的應(yīng)用 11 4 2 3 4 4 3 2 3 2 4 1 5 2 3 5 2 3 2 3 2 3 4 1 4 2 2 3 1 6 2 3 1 4 1 4 2 3 4 2 3 4 1 7 2 1 2 1 3 4 2 1 4 3 3 2 2 8 2 3 4 3 2 2 2 3 3 2 3 2 4 9 2 3 4 2 3 4 2 3 4 2 3 4 1 10 1 2 3 4 1 2 3 4 2 3 3 2 1 11 3 4 5 2 3 4 4 3 2 3 4 3 2 12 2 3 3 4 3 4 3 4 2 2 4 2 4 13 3 3 4 1 3 2 4 2 3 3 3 2 1 模型的建立 土方調(diào)配問(wèn)題是指從不同的挖方區(qū)向不同的填方區(qū)運(yùn)送土方，每個(gè)填方區(qū)需要特定數(shù)量的土方。問(wèn)題是如何分配每個(gè)挖方區(qū)的土方供給，以便在滿足每個(gè)填方區(qū)需求的條件下，優(yōu)化某個(gè)目標(biāo)，如最小全部費(fèi)用或最小總運(yùn)輸量。設(shè)有 m 個(gè)挖方區(qū) ( 1 , 2 , , )iW i m? ，設(shè)計(jì)的待挖土方量分別為 ( 1 , 2 , , )is i m? ；有 n 個(gè)填方區(qū) ( 1, 2 , , )jT j n? ，設(shè)計(jì)需要填方量分別為 ( 1, 2 , , )jd j n? ；從 i 到 j 平均運(yùn)輸距離為 ijc 。若用 ijX 表示從挖方區(qū) i 運(yùn)往填方區(qū) j 的土方量，則在挖填平衡的條件下，土方的總運(yùn)輸量最小 (若 ijc 為從 i 到 j 運(yùn)輸單位土方的單價(jià)，則為總運(yùn)費(fèi)最小 )的調(diào)運(yùn)方案的數(shù)學(xué)模型為： 目標(biāo)函數(shù)：11m innmij ijijZ c x????? 1 1 , 2 , ,nij ij x s i m? ??? 1 1 , 2 , ,mij ji x d j n? ??? 0 , 1 , 2 , , 。 1 , 2 , ,ijx i m j n? ? ? 其中，式 (1)為目標(biāo)函數(shù)，即使土方總運(yùn)輸量最??；式 (2)為挖方區(qū)的供給約束；式 (3)為填方區(qū)的需求約束；式 (4)為變量非負(fù)約束。上述表達(dá)式為挖填平衡時(shí)的數(shù)學(xué)模型。當(dāng)挖填不平衡時(shí)，依據(jù)挖、填方量的大小關(guān)系，土方調(diào)配問(wèn)題的線性規(guī)劃模型可分別表示如下。 1)挖方量大于填方量 11m innmij ijijZ c x????? 1 1 , 2 , ,nij ij x s i m? ??? 最優(yōu)化在數(shù)學(xué)建模中的應(yīng)用 12 1 1 , 2 , ,mij ji x d j n? ??? 0 , 1 , 2 , , 。 1 , 2 , ,ijx i m j n? ? ? 2)挖方量小于填方量 11m innmij ijijZ c x????? 1 1 , 2 , ,nij ij x s i m? ??? 1 1 , 2 , ,mij ji x d j n? ??? 0 , 1 , 2 , , 。 1 , 2 , ,ijx i m j n? ? ? 數(shù)據(jù)的處理 為了將問(wèn)題簡(jiǎn)化，對(duì)每個(gè)工地的挖土量和填土量進(jìn)行相減，得到每個(gè)工地的絕對(duì)挖土量和填土量。最后將這些工地進(jìn)行分區(qū)，分為挖土區(qū)和填土區(qū)。即挖土量減去填土量為正值，則為挖土區(qū)。反之則為填土區(qū)。并且把郊區(qū)的挖土和填土的指 定地點(diǎn)分別命名為 A、 B 地區(qū)。通過(guò)對(duì)原表進(jìn)行修改，可以得到下表。 表 3 工地作業(yè)表 更改工地編號(hào) 需要填入土方 (T) 需要挖出土方 (W) TW 1? T1 20 10 10 2? W1 15 25 10 3? T2 18 12 6 4? T3 30 20 10 5? W2 15 18 3 6? T4 25 13 12 7? T5 35 14 21 8? T6 40 20 20 9? W3 20 28 8 10? W4 22 32 10 11? T7 42 24 18 12? T8 40 0 40 表 4 工地間的道路運(yùn)費(fèi) T1 T2 T3 T4 T5 T6 T7 T8 A W1 1 4 2 4 5 1 4 5 9 W2 2 2 3 3 4 1 3 1 12 W3 2 4 2 4 2 3 4 1 12 W4 1 3 4 2 3 4 2 1 12 B 9 12 12 12 15 12 12 15 1000 最優(yōu)化在數(shù)學(xué)建模中的應(yīng)用 13 運(yùn)用 Excel 求解的具體操作步驟 Excel 表具有強(qiáng)大的規(guī)劃求解功能，具體操作步驟如下： (1) 建立表 4 的單元格。其中，單元格 B9： J13 與線性規(guī)劃模型中變量ijX相對(duì)應(yīng)，為可變單元格，保持原始值 0 空置不填；單元格 B14： J14 和 K9： K13為約束條件的部分表達(dá)式，在 K9 單元格中輸入公式 “=SUM (B9： J9)”，在K10 單元格中輸入公式 “=SUM(B10： J10)”，在 K11 單元格中輸入公式 “=SUM (B11： J11)”，在 K12 單元格中輸入公式 “=SUM(B12： J12)”，在 K13 單元格中輸入公式 “=SUM(B13： J13)”，在 B14單元格中輸入公式 “= SUM (B9： BI3)”，在 C13 單元格中輸入公式 “=SUM (C9： C13)”，一直到 J13 單元格中輸入公式 “=SUM (J9： J13)”；單元格 L2 與線性規(guī)劃模型中目標(biāo)函數(shù)的表達(dá)式相對(duì)應(yīng)，是目標(biāo)單元格，輸入公式 “=SUMPRODUCT(B2： J6， $B$9： $J$13)”，數(shù)學(xué)含義為 “ 11 12 13 14 57 581 4 2 4 1 2 1 5 1 0 0 0X X X X X X? ? ? ? ? ? ? ? ? ? ? ? ? 59X? ”，實(shí)際含義為 “土方總運(yùn)輸量 ”。計(jì)算式中 $B $9： $J $13 為絕對(duì)地址，這樣做是為了方便計(jì)算式的復(fù)制。 (2) 加載 “規(guī)劃求解 ”程序。一般情況下， Microsoft Excel 軟件中規(guī)劃 求解的功能都尚未安裝，需要加載。單擊 “工具 ”菜單，然后點(diǎn)擊 “加載宏 ”，然后在彈出菜單中選中 “規(guī)劃求解 ”項(xiàng)，最后單擊 “確定 ”即可 ，見(jiàn)圖 2。 (3) 設(shè)置 “規(guī)劃求解參數(shù) ”。點(diǎn)擊 “工具 ”中的 “規(guī)劃求解 ”選項(xiàng)打開(kāi)規(guī)劃求解參數(shù)設(shè)置頁(yè)面。在 “設(shè)置目標(biāo)單元格中 ”填入 “$L$2”，在 “等于 ”選項(xiàng)中選擇 “最小值 ”，在 “可變單元格 ”選項(xiàng)中填人 “$B$9： $J$13”。在 “約束 ”選項(xiàng)中點(diǎn)擊 “添加 ”按紐，添加約束條件 “$B$14： $J$14= $B$7： $J$ $K$9： $K$13= $K $2： $K$6 和$B$9： $J$13 ? 0”。點(diǎn)擊 “選項(xiàng) ”按鈕出現(xiàn) “規(guī)劃求解選項(xiàng) ”對(duì)話框，選定 “采用線性模型 ”和 “假定非負(fù) ”復(fù)選項(xiàng)，其中的 “迭代次數(shù) ”選項(xiàng)參數(shù)可以隨著精度的要求決定。 (4) 求解。規(guī)劃求解參數(shù)全部設(shè)置好之后，即可點(diǎn)擊 “求解 ”按鈕進(jìn)行計(jì)算，彈出“規(guī)劃求解結(jié)果 ”對(duì)話框后，點(diǎn)擊 “確定 ”后便得到求解結(jié)果 (見(jiàn)表 4 所示 )。 最優(yōu)化在數(shù)學(xué)建模中的應(yīng)用 14 圖 2 Excel規(guī)劃求解功能 模型的求解 根據(jù)本題的要求，并結(jié)合上述理論模型?？梢越o出適合本題的具體線性規(guī)劃數(shù)學(xué)模型。 (1)模型一： 目標(biāo)函數(shù)： 11 12 13 14 46 47 48m in 1 4 2 4 4 2 1Z X X X X X X X? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 約束條件： 11 12 13 17 1821 22 23 27 2831 32 33 37 3841 42 43 47 4811 21 31 4112 22 32 4218 28 38 4810381010640X X X X XX X X X XX X X X XX X X X XX X X XX X X XX X X X? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ?? ? ? ?? ? ? ? () 0( 1 , 2 , 3 , 4 。 1 , 2 , , 8 )ijX i j? ? ? 通過(guò) Excel 的規(guī)劃求解步驟 對(duì)其進(jìn)行求解，得到下表。 最優(yōu)化在數(shù)學(xué)建模中的應(yīng)用 15 表 5 模型一的求解結(jié)果 填土區(qū) 挖土區(qū) T1 T2 T3 T4 T5 T6 T7 T8 挖方量 總運(yùn)費(fèi) W1 1 4 2 4 5 1 4 5 10 62 W2 2 2 3 3 4 1 3 1 3 W3 2 4 2 4 2 3 4 1 8 W4 1 3 4 2 3 4 2 1 10 填方量 10 6 10 12 21 20 18 40 調(diào)配方案 W1 0 5 5 0 0 0 0 0 10 W2 2 1 0 0 0 0 0 0 3 W3 8 0 0 0 0 0 0 0 8 W4 0 0 0 0 0 0 0 10 10 填方量 10 6 5 0 0 0 0 10 顯然不是題目所要求的結(jié)果。因?yàn)樘钔亮亢屯谕亮坎⒉幌嗟?，不能通過(guò)各工地之間的運(yùn)輸完成土方的周轉(zhuǎn)。因此必須要在郊區(qū) A、 B 地區(qū)運(yùn)輸土方，以保證各工地如期 完成任務(wù)。將模型一進(jìn)行改進(jìn)。 (2)模型二： 目標(biāo)函數(shù)： 11 12 13 14 57 58 59m in 1 4 2 4 1 2 1 5 1 0 0 0Z X X X X X X X? ? ? ? ? ? ? ? ? ? ? ? ? ? ?約束條件： 1 1 1 2 1 3 1 8 1 92 1 2 2 2 3 2 8 2 93 1 3 2 3 3 3 8 3 94 1 4 2 4 3 4 8 4 95 1 5 2 5 3 5 8 5 91 1 2 1 3 1 4 11 2 2 2 3 2 4 21 8 2 8 3 8 4 81 9 2 9 3 9 4 9103810106106400X X X X XX X X X XX X X X XX X X X XX X X X XX X X XX X X XX X X XX X X X? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ? () 0( 1 , 2 , 3 , 4 , 5 。 1 , 2 , , 9 )ijX i j? ? ? 再次運(yùn)用 Excel 對(duì)其進(jìn)行求解，得到下表。 表 6 模型二的求解結(jié)果 最優(yōu)化在數(shù)學(xué)建模中的應(yīng)用 16 填土區(qū) 挖土區(qū) T1 T2 T3 T4 T5 T6 T7 T8 A 挖方量 總運(yùn)費(fèi) W1 1 4 2 4 5 1 4 5 9 10 1393 W2 2 2 3 3 4 1 3 1 12 3 W3 2 4 2 4 2 3 4 1 12 8 W4 1 3 4 2 3 4 2 1 12 10 B 9 12 12 12 15 12 12 15 1000 106 填方量 10 6 10 12 21 20 18 40 0 137 調(diào)配方案 W1 0 0 0 0 0 10 0 0 0 10 W2 0 0 0 0 0 0 0 3 0 3 W3 0 0 0