數(shù)學(xué)建模優(yōu)化模型

1、優(yōu)化模型(mxng)Max min共一百二十三頁優(yōu)化是人類認(rèn)識(rn shi)世界和改善自身的重要內(nèi)容認(rèn)識世界： 我們身邊的許多事物都是大自然優(yōu)勝劣汰的長期演化(ynhu)的產(chǎn)物，在長期的生存競爭中形成了優(yōu)化的結(jié)構(gòu)和運(yùn)動特征。如 魚的體形 鳥和蜜蜂的巢穴 動物的肌肉、植物的葉片的形狀 蝶的飛行線路、魚的游動軌跡等，從能量消耗、結(jié)構(gòu)穩(wěn)定和強(qiáng)度、效率等不同指標(biāo)分析顯現(xiàn)優(yōu)化特征。共一百二十三頁因此，優(yōu)化是深入認(rèn)識世界(shji)的重要手段。自然界本身也在某些方面顯現(xiàn)優(yōu)化特征。最重要的是任意物體在宏觀運(yùn)動中都遵循“作用量最小”的自然規(guī)律。因此，我們觀察到的自然現(xiàn)象如 球的彈起軌跡(guj) 水滴的下落

2、時的形狀改變 . 等一切運(yùn)動現(xiàn)象都是優(yōu)化的結(jié)果。當(dāng)前，“作用量最小”原則是我們描述自然界運(yùn)動的基本工具。共一百二十三頁優(yōu)化是人類改善(gishn)自身的重要手段節(jié)能：對能源使用(shyng)的優(yōu)化；規(guī)劃：對管理效率的優(yōu)化；最優(yōu)控制：對運(yùn)動系統(tǒng)效率、性能等的優(yōu)化；設(shè)計、工藝、結(jié)構(gòu)的優(yōu)化.總之，人類的發(fā)展本身就是一個優(yōu)化的過程。例如，工藝的改善的定量分析歸結(jié)為工藝的優(yōu)化；設(shè)計的改進(jìn)的定量分析歸結(jié)為設(shè)計的優(yōu)化等。共一百二十三頁簡單(jindn)優(yōu)化模型在中學(xué)和大學(xué)微積分中，我們學(xué)習(xí)過求函數(shù)的極值和條件極值問題。這是我們對簡單問題優(yōu)化的基本數(shù)學(xué)工具。下面討論(toln)利用這些工具建模的幾個例子1、存

3、貯模型 在商業(yè)活動中，需要批量訂購商品。訂購費(fèi)用為其中c0是批量訂購的一次性費(fèi)用，c1是商品單價。批量越大，單位商品的費(fèi)用越低。 商品購進(jìn)后，有一個消化過程(銷售或使用)。消化不掉的需要存放，因此形成存貯費(fèi)用。批量越大，每天存貯費(fèi)用越高。共一百二十三頁生產(chǎn)活動有類似的情況。批量生產(chǎn)費(fèi)用為其中c0是批量生產(chǎn)的生產(chǎn)準(zhǔn)備(zhnbi)費(fèi)用，c1是產(chǎn)品單位成本。批量越大，單位產(chǎn)品的費(fèi)用越低。上述問題稱為存貯問題。建立數(shù)學(xué)模型以確定最佳訂貨周期和批量(p lin)，是存貯問題所要解決的問題。兩種問題的數(shù)量關(guān)系完全相同，下面只討論商品的批量訂貨問題。產(chǎn)品生產(chǎn)后，有一個消化過程(銷售或使用)。消化不掉的需要

4、存放，因此形成存貯費(fèi)用。批量越大，每天存貯費(fèi)用越高。共一百二十三頁不允許缺貨的存貯(cn zh)模型模型(mxng)假設(shè)1. 商品每天的需求量為常數(shù) r；2. 一次性購貨費(fèi)為 c0, 每件商品單價c1，每天每件商品貯存費(fèi)為 c2；3. T天訂購一次(周期), 每次購買Q件，當(dāng)貯存量 為零時，Q件商品立即到來(不允許缺貨)；4. 為方便起見，時間和產(chǎn)量都作為連續(xù)量處理。共一百二十三頁問題(wnt)：r, c0,c1, c2 已知，求T, Q 使每天總費(fèi)用的平均值最小。模型(mxng)建立0tqTQrA=QT/2一個周期的總費(fèi)用是購貨費(fèi)用和存貯費(fèi)用的和購貨費(fèi)用: P=c0+c1Q無缺貨假設(shè)： Q=

5、rT平均每天的費(fèi)用： 存貯費(fèi)用 : R=c2A=c2QT/2共一百二十三頁模型(mxng)求解模型(mxng)分析1、最佳周期長度與商品價格無關(guān)；2、共一百二十三頁允許缺貨的存貯(cn zh)模型原模型假設(shè)(jish)：貯存量降到零時Q件立即生產(chǎn)出來(或立即到貨)。若貯存量降到零時仍有需求r,但 不能立即到貨，則出現(xiàn)缺貨而造成損失。如果允許缺貨，模型應(yīng)如何修改？共一百二十三頁補(bǔ)充(bchng)假設(shè)：允許缺貨, 每天每件缺貨損失費(fèi) c3 , 缺貨需補(bǔ)足T0qQrT1tAB一周期貯存費(fèi)一周期缺貨費(fèi)一周期總費(fèi)用共一百二十三頁為與不允許(ynx)缺貨的存貯模型相比，T記作T , Q記作Q每天的費(fèi)用(f

6、i yong)為共一百二十三頁2 . 生豬(shngzh)的出售時機(jī)飼養(yǎng)場每天投入4元資金(zjn)，用于飼料、人力、設(shè)備，估計可使80千克重的生豬體重增加2公斤。市場價格目前為每千克8元，但是預(yù)測每天會降低 0.1元，問生豬應(yīng)何時出售。如果估計和預(yù)測有誤差，對結(jié)果有何影響?共一百二十三頁模型(mxng)分析投入資金使生豬體重隨時間增加，出售單價隨時間減少，尋找最佳出售時機(jī)(決策(juc)變量)，使利潤最大(目標(biāo))。建模及求解生豬體重 w=80+rt出售單價 p=8-gt銷售收入 R=pw資金投入 C=4t設(shè)生豬重量w，單價p，每天增加體重r，每天單價降低g，t天后出售，則屆時利潤：共一百二十

7、三頁求 t 使Q(t)最大得到(d do)敏感性分析(fnx)求出的生豬最佳出售時間t與參數(shù)r和g有關(guān)。而這兩個參數(shù)來源于我們的估計和預(yù)測。參數(shù)的變化對結(jié)果的影響的大小稱為結(jié)果對參數(shù)的敏感性。敏感程度的定義：結(jié)果t對參數(shù)r的敏感度記為其意義是結(jié)果t的增加率和參數(shù)r增加率的比。 共一百二十三頁參數(shù)變化的敏感程度的大小反映出問題(wnt)或模型的穩(wěn)定性。由于在實際問題(wnt)中，所采集的參數(shù)往往有誤差,當(dāng)敏感程度較大時，必須考慮參數(shù)的微小變化帶來的影響。當(dāng)參數(shù)變化較小時，可以(ky)利用微分作為增量的近似。這時，參數(shù)的敏感度計算的近似公式為共一百二十三頁生豬出售(chshu)時機(jī)問題的解 當(dāng)r=

8、2，g=0.1時，即如果(rgu)生豬每天體重增加1%，則出售時間延遲3%。共一百二十三頁例3：森林(snln)救火當(dāng)森林失火時，接到報警的消防隊需要派出消防隊員前去(qin q)救火。派多少人合適呢？模型分析以森林失火造成的損失大小作為目標(biāo)來優(yōu)化救火人數(shù)。損失包括兩部分： 1、因撲火不及，燒掉林木而造成的損失； 2、因派出消防隊員而產(chǎn)生的支出。目標(biāo)：總費(fèi)用最少。由于地形、風(fēng)力等的不確定，需要簡化問題。共一百二十三頁模型(mxng)假設(shè)：1、0tt1, 過火(guhu)面積B(t)的導(dǎo)數(shù)dB/dt 與 t成正比，系數(shù) (火勢蔓延速度)2、t1tt2, 降為-x (為隊員的平均滅火速度)3、過火

9、損失與過火面積B(t2)成正比，系數(shù)c1 (燒毀單位面積損失費(fèi)) 4、每個隊員的單位時間滅火費(fèi)用c2, 一次性費(fèi)用c3森林救火共一百二十三頁假設(shè)1的解釋(jish)：假設(shè)1基于以下簡化假設(shè)：火源向周圍勻速蔓延，這樣，到t時刻，森林過火區(qū)域為B(t)=(vt)2。面積 B與 t2成正比， dB/dt與 t成正比.比例系數(shù)稱為蔓延率。森林(snln)救火共一百二十三頁b0t1t假設(shè)1假設(shè)2t2假設(shè)3、4模型(mxng)建立森林(snln)救火共一百二十三頁目標(biāo)(mbio)函數(shù)總費(fèi)用模型(mxng)求解求 x使 C(x)最小b0t1t2t森林救火共一百二十三頁結(jié)果(ji gu)解釋 / :火勢不繼續(xù)

10、蔓延的最少救火(ji hu)人員數(shù)c1燒毀單位面積損失費(fèi), c2每個隊員單位時間滅火費(fèi), c3每個隊員一次性費(fèi)用, t1開始救火時刻, 火勢蔓延速度, 每個隊員平均滅火速度. c2 x c1, t1, x c3 , x 為什么?森林救火共一百二十三頁例4： 冰山(bngshn)運(yùn)輸背景(bijng) 波斯灣地區(qū)水資源貧乏，淡水主要靠海水淡化，淡化海水的成本為每立方米0.1英鎊。 專家建議從9600千米遠(yuǎn)的南極用拖船運(yùn)送冰山，取代淡化海水。 從經(jīng)濟(jì)角度研究冰山運(yùn)輸?shù)目尚行浴＝?shù)據(jù)準(zhǔn)備1. 日租金和最大運(yùn)量船 型小 中 大日租金(英鎊) 最大運(yùn)量(米3)4.06.28.05105106107 冰

11、山運(yùn)輸共一百二十三頁2. 燃料消耗(英鎊(yn bn)/千米)3. 融化(rnghu)速率(米/天)與南極距離 (千米)船速(千米/小時) 0 1000 4000135 0 0.1 0.3 0 0.15 0.45 0 0.2 0.6冰山體積(米3)船速(千米/小時) 105 106 107135 8.4 10.5 12.6 10.8 13.5 16.2 13.2 16.5 19.8 冰山運(yùn)輸共一百二十三頁建模目的(md)選擇船型和船速，使冰山到達(dá)目的地后每立米水的費(fèi)用(fi yong)最低，并與淡化海水的費(fèi)用(fi yong)比較。模型假設(shè) 航行過程中船速不變，總距離9600千米 冰山呈球形，

12、球面各點融化速率相同到達(dá)目的地后，每立方米冰可融化0.85立方米水 冰山運(yùn)輸共一百二十三頁建模分析(fnx)目的地水體積(tj)運(yùn)輸過程融化規(guī)律總費(fèi)用目的地冰體積初始冰山體積燃料消耗租金船型, 船速船型船型, 船速船型,船速決策變量：船速，船型目標(biāo)：每立方水的費(fèi)用如何從離散數(shù)據(jù)中挖掘出有用的信息？ 冰山運(yùn)輸共一百二十三頁模型(mxng)建立1. 冰山融化(rnghu)規(guī)律 船速u (千米/小時)與南極距離d(千米)融化速率r(米/天）r是 u 的線性函數(shù)；d4000時u與d無關(guān).航行 t 天第t天融化速率 0 1000 4000135 0 0.1 0.3 0 0.15 0.45 0 0.2 0

13、.6urd 冰山運(yùn)輸共一百二十三頁模型(mxng)建立冰山(bngshn)體積變化規(guī)律 冰山初始半徑R0，航行t天時半徑冰山初始體積t天時體積總航行天數(shù)選定u,V0, 航行t天時冰山體積到達(dá)目的地時冰山體積 冰山運(yùn)輸共一百二十三頁2. 燃料(rnlio)消耗 105 106 107135 8.4 10.5 12.6 10.8 13.5 16.2 13.2 16.5 19.8Vuq1燃料(rnlio)消耗數(shù)據(jù) q1(英鎊/千米)q1對u線性, 對log10V線性選定u,V0, 航行第t天燃料消耗 q (英鎊/天)燃料消耗總費(fèi)用模型建立 冰山運(yùn)輸共一百二十三頁3. 運(yùn)送(yn sn)每立方米水費(fèi)用

14、 冰山初始體積V0的日租金(zjn) f(V0)(英鎊)航行天數(shù)總?cè)剂舷馁M(fèi)用拖船租金費(fèi)用冰山運(yùn)輸總費(fèi)用模型建立 冰山運(yùn)輸共一百二十三頁模型(mxng)求解選擇船型和船速，使冰山(bngshn)到達(dá)目的地后每立方米水的費(fèi)用最低求 u,V0使Y(u,V0)最小u=45(千米/小時), V0= 107 (米3)， Y(u,V0)最小V0只能取離散值經(jīng)驗公式很粗糙33.544.551070.07230.06830.06490.06630.06580.22510.20130.18340.18420.179010678.90329.82206.21385.46474.5102V0u5106取幾組(V0,

15、u)用枚舉法計算 冰山運(yùn)輸共一百二十三頁結(jié)果(ji gu)分析由于未考慮影響航行(hngxng)的種種不利因素，冰山到達(dá)目的地后實際體積會顯著小于V(u,V0)。有關(guān)部門認(rèn)為，只有當(dāng)計算出的Y(u,V0)顯著低于淡化海水的成本時，才考慮其可行性。大型拖船V0= 107 (米3)，船速 u=45(千米/小時), 冰山到達(dá)目的地后每立米水的費(fèi)用 Y(u,V0)約0.065(英鎊)雖然0.065英鎊略低于淡化海水的成本0.1英鎊，但是模型假設(shè)和構(gòu)造非常簡化與粗糙。 冰山運(yùn)輸共一百二十三頁 數(shù)學(xué)(shxu)規(guī)劃模型共一百二十三頁有約束的優(yōu)化問題(wnt)的一般數(shù)學(xué)描述為 共一百二十三頁當(dāng)變量個數(shù)和約束

16、條件的個數(shù)較多時，像處理簡單優(yōu)化模型那樣隨意建模很難把問題處理好。因此需要新的建模和求解(qi ji)思路。這種規(guī)模較大的優(yōu)化問題稱為規(guī)劃問題。規(guī)劃(guhu)問題的建模特點分類研究規(guī)范化建模和計算分離共一百二十三頁優(yōu)化模型(mxng)的分類數(shù)學(xué)(shxu)規(guī)劃模型線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃和混合規(guī)劃動態(tài)規(guī)劃網(wǎng)絡(luò)優(yōu)化變分模型連續(xù)動態(tài)優(yōu)化共一百二十三頁線性規(guī)劃(xin xn u hu)模型共一百二十三頁線性規(guī)劃模型(mxng)的數(shù)學(xué)結(jié)構(gòu)線性規(guī)劃(xin xn u hu)模型的一般形式為matlab中的線性規(guī)劃函數(shù)只處理上述形式的模型，其他形式要先化為上述形式。共一百二十三頁求解線性規(guī)劃(xin

17、xn u hu)問題的基本思路求解線性規(guī)劃問題的基本方法是單純形法?？紤]一個(y )簡單的問題：滿足約束條件的點集稱為可行域，規(guī)劃問題就是從可行域中尋找目標(biāo)函數(shù)的最優(yōu)解。共一百二十三頁約束條件l1l2l3l4l5Z=0Z=-2400Z=-3600ABCD目標(biāo)(mbio)函數(shù) z=c (常數(shù)(chngsh) 等值線在B(20,30)點得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線性函數(shù) 可行域為線段圍成的凸多邊形 目標(biāo)函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊形的某個頂點取得。 可行域共一百二十三頁奶制品廠用牛奶生產(chǎn)A1,A2兩種奶制品。一桶牛奶可在甲類設(shè)備上用12小時加工成3公斤A1，或在乙類設(shè)備上用8小時加工

18、成4公斤A2。生產(chǎn)的A1,A2全部都能售出，且每公斤A1獲利24元，每公斤A2獲利16元。加工廠每天能得到50桶牛奶，每天正式工人(gng rn)總的勞動時間為480小時，甲類設(shè)備每天至多加工100公斤A1，乙類設(shè)備的加工能力沒有限制。試為該廠制定一個生產(chǎn)計劃，使每天獲利最大。例1：加工(ji gng)奶制品的生產(chǎn)計劃1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 共一百二十三頁1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶(ni ni) 480小時(xiosh) 至多加工100公斤A1 每天：制訂

19、生產(chǎn)計劃，使每天獲利最大 35元可買到1桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到 30元/公斤，應(yīng)否改變生產(chǎn)計劃？ 共一百二十三頁1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶(ni ni)生產(chǎn)A1 x2桶牛奶(ni ni)生產(chǎn)A2 獲利 243x1 獲利 164 x2 原料供應(yīng) 勞動時間 加工能力 決策變量 目標(biāo)函數(shù) 每天獲利約束條件非負(fù)約束 線性規(guī)劃模型(LP)共一百二十三頁模型(mxng)求解 軟件(run jin)實現(xiàn) LINDOmax 72x1+64x2st2）x1+x2

20、503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? 20桶牛奶生產(chǎn)A1, 30桶生產(chǎn)

21、A2，利潤3360元。 no共一百二十三頁結(jié)果(ji gu)解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2原料(yunlio)無剩余時間無剩余加工能力剩余40max 72x1+64x2st2）

22、x1+x2503）12x1+8x24804）3x1100end三種資源“資源” 剩余為零的約束為緊約束(有效約束) 共一百二十三頁結(jié)果(ji gu)解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS=

23、2最優(yōu)解下“資源”增加(zngji)1單位時“效益”的增量 原料增加1單位, 利潤增長48 時間增加1單位, 利潤增長2 加工能力增長不影響利潤影子價格 35元可買到1桶牛奶，要買嗎？35 48, 應(yīng)該買！ 聘用臨時工人付出的工資最多每小時幾元？ 2元！共一百二十三頁RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.00000

24、0 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000最優(yōu)解不變時目標(biāo)函數(shù)(hnsh)系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? x1系數(shù)(xsh)范圍(64,96) x2系數(shù)范圍(48,72) A1獲利增加到 30元/千克，應(yīng)否改

25、變生產(chǎn)計劃 x1系數(shù)由24 3=72增加為303=90，在允許范圍內(nèi) 不變！(約束條件不變)共一百二十三頁結(jié)果(ji gu)解釋 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLO

26、WABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子價格有意義時約束右端的允許變化(binhu)范圍 原料最多增加10 時間最多增加53 35元可買到1桶牛奶，每天最多買多少？最多買10桶!(目標(biāo)函數(shù)不變)共一百二十三頁例2 奶制品的生產(chǎn)銷售(xioshu)計劃 在例1條件下，為增加工廠的利潤，開發(fā)奶制品深加工技術(shù)：用2小時和3元加工費(fèi)，可將1公斤A1加工成0.8公斤高級奶制品B1,也可以將1公斤A

27、2加工成0.75公斤高級奶制品B2。1公斤B1可獲利44元， 1公斤B2可獲利32元。試為該廠制定生產(chǎn)銷售計劃(jhu)，使每天的凈利潤最大，并討論以下問題：若投資30元可增加供應(yīng)1桶牛奶，投資3元可增加一小時工作時間，應(yīng)否作這些投資？若每天投資150元，可賺回多少？每公斤高級奶制品的獲利經(jīng)常有10%的波動，這對制定的生產(chǎn)銷售計劃有沒有影響？若每公斤B1的獲利下降10%，計劃應(yīng)該變化嗎？共一百二十三頁在例1基礎(chǔ)(jch)上深加工1 桶牛奶 3千克A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 0.8千克B12小時,3元1千克獲利44元/千克 0.75千克B22小時,3

28、元1千克獲利32元/千克 制訂生產(chǎn)(shngchn)計劃，使每天凈利潤最大 30元可增加1桶牛奶，3元可增加1小時時間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？50桶牛奶, 480小時 至多100公斤A1 B1，B2的獲利經(jīng)常有10%的波動，對計劃有無影響？共一百二十三頁1 桶牛奶 3千克A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 0.8千克B12小時,3元1千克獲利44元/千克 0.75千克B22小時,3元1千克獲利32元/千克 出售(chshu)x1 千克 A1, x2 千克 A2， x3千克(qink) B1, x4千克 B2原料供應(yīng) 加工能力 決策變量 目標(biāo)

29、函數(shù) 利潤約束條件非負(fù)約束 x5千克 A1加工B1， x6千克 A2加工B2附加約束 勞動時間 共一百二十三頁運(yùn)輸(ynsh)問題生產(chǎn)、生活物資從若干供應(yīng)點運(yùn)送到一些需求點，怎樣安排輸送方案使運(yùn)費(fèi)(yn fi)最小，或利潤最大？各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少？共一百二十三頁例1 自來水輸送(sh sn)某城市有甲、乙、丙、丁四個居民區(qū)，自來水由A,B,C三個水庫供應(yīng)。四個區(qū)每天必須得到的基本生活用水量分別為30，70，10，10千噸，此外 ，四個區(qū)都向公司申請了額外用水量，分別為每天50，70，20，40千噸。由于水源緊張，三個水庫每天最多

30、只能分別供應(yīng)50，60，50千噸。由于地理位置(d l wi zh)的差別，自來水公司從各水庫向各區(qū)送水付出的引水管理費(fèi)不同（見表），其他管理費(fèi)都是450元/千噸。各區(qū)用戶按統(tǒng)一標(biāo)準(zhǔn)900元/千噸收費(fèi)。如何分配用水量能獲利最多？ 引水管理費(fèi)甲乙丙丁A160130220170B140130190150C190200230/共一百二十三頁其他費(fèi)用:450元/千噸(qin dn) 應(yīng)如何(rh)分配水庫供水量，公司才能獲利最多？ 若水庫供水量都提高一倍，公司利潤可增加到多少？ 元/千噸甲乙丙丁A160130220170B140130190150C190200230/引水管理費(fèi)收入：900元/千噸 支

31、出A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40水庫供水量(千噸)小區(qū)基本用水量(千噸)小區(qū)額外用水量(千噸)(以天計)共一百二十三頁總供水量：160確定(qudng)送水方案使利潤最大問題(wnt)分析A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40 總需求量(300)每個水庫(shuk)最大供水量都提高一倍利潤 = 收入(900) 其它費(fèi)用(450) 引水管理費(fèi)利潤(元/千噸)甲乙丙丁A290320230280B310320260300C260250220/供應(yīng)限制B, C 類似處理問題2 確定送水方案使利潤最大需求約束可以

32、不變共一百二十三頁例2 貨機(jī)(hu j)裝運(yùn)某架飛機(jī)有三個貨艙：前艙、中艙和后艙。三個貨艙所能裝載貨物的最大重量和最大體積都有限制(如表1)。并且為了保持飛機(jī)的平衡，三個貨艙中實際裝載貨物的重量必須與其最大容許重量成比例?，F(xiàn)有四類貨物供該貨機(jī)本次(bn c)飛行裝運(yùn)，有關(guān)信息見表2.應(yīng)如何安排裝機(jī)使本次飛行獲利最大？前艙 中艙 后艙重量限制10 16 8體積限制6800 8700 5300 重量(T) 空間(m3/T) 利潤(元/T)貨物1 18 480 3100貨物2 15 650 3800貨物3 23 580 3500貨物4 12 390 2850表 1表 2共一百二十三頁如何裝運(yùn)，使本次

33、(bn c)飛行獲利最大？ 三個貨艙最大載重(zizhng)(噸),最大容積(米3) 例2 貨機(jī)裝運(yùn)重量(噸)空間( 米3/噸)利潤(元/噸)貨物1184803100貨物2156503800貨物3235803500貨物4123902850三個貨艙中實際載重必須與其最大載重成比例 前倉：10；6800中倉：16；8700后倉：8；5300飛機(jī)平衡共一百二十三頁決策(juc)變量 xij-第i 種貨物裝入第j 個貨艙(hucng)的重量(噸)i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉)模型假設(shè) 每種貨物可以分割到任意??；每種貨物可以在一個或多個貨艙中任意分布；多種貨物可以混裝，并

34、保證不留空隙； 模型建立 共一百二十三頁貨艙(hucng)容積 目標(biāo)(mbio)函數(shù)(利潤)約束條件貨機(jī)裝運(yùn)模型建立 貨物重量 10；680016；87008；5300 xij-第i 種貨物裝入第j 個貨艙的重量決策變量共一百二十三頁約束條件平衡(pnghng)要求 貨物(huw)供應(yīng) 模型建立 10；680016；87008；5300 xij-第i 種貨物裝入第j 個貨艙的重量共一百二十三頁 OBJECTIVE FUNCTION VALUE 1) 121515.8 VARIABLE VALUE REDUCED COST X11 0.000000 400.000000 X12 0.000000

35、 57.894737 X13 0.000000 400.000000 X21 10.000000 0.000000 X22 0.000000 239.473679 X23 5.000000 0.000000 X31 0.000000 0.000000 X32 12.947369 0.000000 X33 3.000000 0.000000 X41 0.000000 650.000000 X42 3.052632 0.000000 X43 0.000000 650.000000 貨物(huw)2：前倉10,后倉5； 貨物3: 中倉13, 后倉3；貨物4: 中倉3。模型(mxng)求解 最大利潤約

36、121516元貨物供應(yīng)點貨艙需求點平衡要求運(yùn)輸問題運(yùn)輸問題的擴(kuò)展共一百二十三頁 如果生產(chǎn)某一類型(lixng)汽車，則至少要生產(chǎn)80輛， 那么最優(yōu)的生產(chǎn)計劃應(yīng)作何改變？例1 汽車廠生產(chǎn)(shngchn)計劃 汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量。 小型 中型 大型 現(xiàn)有量鋼材(噸) 1.5 3 5 600勞動時間(小時) 280 250 400 60000利潤(萬元) 2 3 4 制訂月生產(chǎn)計劃，使工廠的利潤最大。汽車生產(chǎn)與原油采購共一百二十三頁決策變量(binling)：每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1, x2, x3汽車廠生產(chǎn)(s

37、hngchn)計劃 模型建立 小型 中型 大型 現(xiàn)有量鋼材 1.5 3 5 600時間 280 250 400 60000利潤 2 3 4 線性規(guī)劃模型(LP)共一百二十三頁模型(mxng)求解 3、 模型(mxng)中增加條件：x1, x2, x3 均為整數(shù)，重新求解。 OBJECTIVE FUNCTION VALUE 1) 632.2581VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES

38、2) 0.000000 0.731183 3) 0.000000 0.003226結(jié)果為小數(shù)，怎么辦？1、舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z=629，與LP最優(yōu)值632.2581相差不大。2、試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數(shù)值z，通過比較可能得到更優(yōu)的解。 但必須檢驗它們是否滿足約束條件。為什么？共一百二十三頁LINDO程序(chngx)整數(shù)規(guī)劃(guhu)(Integer Programming,簡記IP)“gin 3”表示“前3個變量為整數(shù)”，等價于：gin x1gin x2gin x3 IP 的最優(yōu)解x1=64，x2=168，x

39、3=0，最優(yōu)值z=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3 OBJECTIVE FUNCTION VALUE 1) 632.0000VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000 模型求解 IP 結(jié)果輸出共一百二十三頁其中3個子模型應(yīng)去掉，然后逐一求解，比較(bjio)目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法(fngf)1：分解為8個LP子模型 汽車

40、廠生產(chǎn)計劃 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。x1,x2, x3=0 或 80 x1=80，x2= 150，x3=0，最優(yōu)值z=610共一百二十三頁LINDO中對0-1變量(binling)的限定：int y1int y2int y3 方法2：引入0-1變量(binling)，化為整數(shù)規(guī)劃 M為大的正數(shù)，可取1000 OBJECTIVE FUNCTION VALUE 1) 610.0000VARIABLE VALUE REDUCED COST X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.000000 Y

41、1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。x1=0 或 80 x2=0 或 80 x3=0 或 80最優(yōu)解同前 共一百二十三頁NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件(run jin)求解(如LINGO, MATLAB)，但是其結(jié)果常依賴于初值的選擇。 方法(fngf)3：化為非線性規(guī)劃 非線性規(guī)劃(Non- Linear Programming，簡記NLP) 實踐表明，本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時，才能得到正確的結(jié)果。 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃

42、。 x1=0 或 80 x2=0 或 80 x3=0 或 80共一百二十三頁例2 原油(yunyu)采購與加工 某公司用兩種原油(A和B)混合加工兩種汽油(甲和乙)。甲、乙兩種汽油含原油A的最低比例分別為50%和60%，每噸售價分別為4800元和5600元。該公司現(xiàn)有原油A和B的庫存量分別為500噸和1000噸，還可以從市場上買到不超過1500噸的原油A。原油A的市場價為：購買量不超過500噸時的單價為10000元/噸；購買量超過500噸但不超過1000噸時，超過500噸部分(b fen)8000元/噸；購買量超過1000噸時，超過1000噸部分6000元/噸。該公司應(yīng)該如何安排原油的采購和加

43、工？共一百二十三頁應(yīng)如何(rh)安排原油的采購和加工 ？ 問題(wnt)分析市場上可買到不超過1500噸的原油A： 購買量不超過500噸時的單價為10000元/噸； 購買量超過500噸但不超過1000噸時，超過500噸的 部分8000元/噸； 購買量超過1000噸時，超過1000噸的部分6000元/噸。 售價4800元/噸 售價5600元/噸庫存500噸 庫存1000噸 汽油甲(A50%) 原油A 原油B 汽油乙 (A60%) 共一百二十三頁決策(juc)變量 目標(biāo)(mbio)函數(shù)問題分析 利潤：銷售汽油的收入 - 購買原油A的支出 難點：原油A的購價與購買量的關(guān)系較復(fù)雜甲(A50%) A B

44、 乙(A60%) 購買xx11x12x21x224.8千元/噸 5.6千元/噸原油A的購買量,原油A, B生產(chǎn)汽油甲,乙的數(shù)量c(x) 購買原油A的支出利潤(千元)c(x)如何表述？共一百二十三頁原油(yunyu)供應(yīng) 約束條件 x 500噸單價(dnji)為10千元/噸； 500噸 x 1000噸，超過500噸的8千元/噸；1000噸 x 1500噸，超過1000噸的6千元/噸。 目標(biāo)函數(shù)購買xx11x12x21x22A B 庫存500噸 庫存1000噸 共一百二十三頁 目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃； 對于用分段函數(shù)定義(dngy)的c(x)，一般的非線性規(guī)劃軟件也難以輸入和

45、求解； 想辦法將模型化簡，用現(xiàn)成的軟件求解。 汽油含原油A的比例(bl)限制 約束條件甲(A50%) A B 乙(A60%) x11x12x21x22共一百二十三頁x1 , x2 , x3 以價格(jig)10, 8, 6(千元/噸)采購A的噸數(shù)目標(biāo)(mbio)函數(shù) 只有當(dāng)以10千元/噸的價格購買x1=500(噸)時，才能以8千元/噸的價格購買x2方法1 非線性規(guī)劃模型，可以用LINGO求解模型求解 500噸 x 1000噸，超過500噸的8千元/噸增加約束x= x1+x2+x3, c(x) = 10 x1+8x2+6x3 共一百二十三頁方法(fngf)1：LINGO求解Model:Max=

46、4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*x2 - 6*x3;x11+x12 x + 500;x21+x22 0; 2*x12 - 3*x22 0;x=x1+x2+x3; (x1 - 500) * x2=0; (x2 - 500) * x3=0; x1 500;x2 500;x3 0;x11 0;x12 0;x21 0;x22 0;x1 0;x2 0;x3 0;end Objective value: 4800.000Variable Value Reduced CostX11 500.0000 0.0000000E+00X21 500

47、.0000 0.0000000E+00X12 0.0000000E+00 0.0000000E+00X22 0.0000000E+00 0.0000000E+00 X1 0.1021405E-13 10.00000 X2 0.0000000E+00 8.000000 X3 0.0000000E+00 6.000000 X 0.0000000E+00 0.0000000E+00 LINGO得到(d do)的是局部最優(yōu)解，還能得到(d do)更好的解嗎？ 用庫存的500噸原油A、500噸原油B生產(chǎn)汽油甲，不購買新的原油A，利潤為4,800千元。 共一百二十三頁y1, y2 , y3=1 以價格(j

48、ig)10, 8, 6(千元/噸)采購A增加(zngji)約束方法2 0-1線性規(guī)劃模型，可用LINDO求解y1,y2,y3 =0或1 OBJECTIVE FUNCTION VALUE 1) 5000.000 VARIABLE VALUE REDUCED COST Y1 1.000000 0.000000 Y2 1.000000 2200.000000 Y3 1.000000 1200.000000 X11 0.000000 0.800000 X21 0.000000 0.800000 X12 1500.000000 0.000000 X22 1000.000000 0.000000 X1 5

49、00.000000 0.000000 X2 500.000000 0.000000 X3 0.000000 0.400000 X 1000.000000 0.000000 購買1000噸原油A，與庫存的500噸原油A和1000噸原油B一起，生產(chǎn)汽油乙，利潤為5,000千元 。x1 , x2 , x3 以價格10, 8, 6(千元/噸)采購A的噸數(shù)y=0 x=0 x0 y=1優(yōu)于方法1的結(jié)果共一百二十三頁方法(fngf)3 b1 xb2，x= z1b1+z2b2，z1+z2=1，z1, z20, c(x)= z1c(b1)+z2c(b2).c(x)x12000900050000500100015

50、00b2 x b3，x= z2b2+z3b3， z2+z3=1，z2, z3 0, c(x)= z2c(b2)+z3c(b3). b3 x b4，x= z3b3+z4b4，z3+z4=1，z3, z4 0, c(x)= z3c(b3)+z4c(b4). 直接處理(chl)處理(chl)分段線性函數(shù)c(x) 共一百二十三頁IP模型，LINDO求解，得到(d do)的結(jié)果與方法2相同.處理分段(fn dun)線性函數(shù)，方法3更具一般性bkxbk+1yk=1,否則,yk=0方法3 bkxbk+1 ,x= zkbk+z k+1 bk+1zk+zk+1 =1，zk, zk+1 0, c(x)= zkc(

51、bk)+zk+1 c(bk+1 ).c(x)x1200090005000050010001500b1 b2 b3 b4對于k=1,2,3共一百二十三頁分派(fnpi)問題接力隊選拔(xunb)和選課策略若干項任務(wù)分給一些候選人來完成，每人的專長不同，完成每項任務(wù)取得的效益或需要的資源就不同，如何分派任務(wù)使獲得的總效益最大，或付出的總資源最少。若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個策略之間有相互制約關(guān)系，如何在滿足一定條件下作出決擇，使得收益最大或成本最小。共一百二十三頁丁的蛙泳成績退步到115”2；戊的自由泳成績進(jìn)步(jnb)到57”5, 組成接力隊的方案是否應(yīng)該調(diào)整？如

52、何(rh)選拔隊員組成4100米混合泳接力隊?例1 混合泳接力隊的選拔 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”45名候選人的百米成績窮舉法：組成接力隊的方案共有5!=120種。共一百二十三頁ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4目標(biāo)(mbio)函數(shù)隊員(du yun)i參加泳

53、姿j ，則記xij=1, 否則記xij=0 0-1規(guī)劃模型 cij(秒)隊員i 第j 種泳姿的百米成績約束條件每人最多入選泳姿之一 每種泳姿有且只有1人 決策變量共一百二十三頁模型(mxng)求解 MIN 66.8x11+75.6x12+87x13+58.6x14 + +67.4x51+71 x52+83.8x53+62.4x54SUBJECT TO x11+x12+x13+x14 =1 x41+x42+x43+x44 =1 x11+x21+x31+x41+x51 =1 x14+x24+x34+x44+x54 =1END INT 20 最優(yōu)解：x14 = x21 = x32 = x43 = 1

54、, 其它(qt)變量為0;成績?yōu)?53.2(秒)=413”2 輸入LINDO求解 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.共一百二十三頁丁蛙泳c43 =69.675.2，戊自由泳c54=62.4 57.5, 方案是否(sh fu)調(diào)整？ 乙 蝶泳、丙 仰泳(yngyng)、丁 蛙泳、戊 自由泳IP規(guī)劃一般沒有與LP規(guī)劃相類似的理論，LINDO輸出的敏感性分析結(jié)果通常是沒有意義的。最優(yōu)解：x

55、21 = x32 = x43 = x51 = 1, 成績?yōu)?17”7 c43, c54 的新數(shù)據(jù)重新輸入模型，用LINDO求解 指派(Assignment)問題：每項任務(wù)有且只有一人承擔(dān)，每人只能承擔(dān)一項，效益不同，怎樣分派使總效益最大. 討論甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.原方案共一百二十三頁為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)(xux)哪些課程 ？ 例2 選課策略：某學(xué)校規(guī)定(gudng)：運(yùn)籌學(xué)專業(yè)學(xué)生必須至少學(xué)習(xí)兩門數(shù)學(xué)、三門運(yùn)籌學(xué)和兩門計算機(jī)。這些課的名稱、學(xué)分、類別和先修課程如下表。課號課名學(xué)分所屬類別先修課要求1微積分5數(shù)學(xué)2線性代數(shù)4數(shù)學(xué)3最優(yōu)化4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線代4數(shù)

56、據(jù)結(jié)構(gòu)3數(shù)學(xué)；計算機(jī)計算機(jī)編程5應(yīng)用統(tǒng)計4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線代6計算機(jī)模擬3計算機(jī)；運(yùn)籌計算機(jī)編程7計算機(jī)編程2計算機(jī)8預(yù)測理論2運(yùn)籌學(xué)應(yīng)用統(tǒng)計9數(shù)學(xué)實驗3運(yùn)籌；計算機(jī)微積分；線代選修課程最少，且學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程 ？ 共一百二十三頁0-1規(guī)劃(guhu)模型 決策(juc)變量 目標(biāo)函數(shù) xi=1 選修課號i 的課程（xi=0 不選） 選修課程總數(shù)最少 約束條件2門計算機(jī)課。 課號課名所屬類別1微積分?jǐn)?shù)學(xué)2線性代數(shù)數(shù)學(xué)3最優(yōu)化方法數(shù)學(xué)；運(yùn)籌學(xué)4數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué)；計算機(jī)5應(yīng)用統(tǒng)計數(shù)學(xué)；運(yùn)籌學(xué)6計算機(jī)模擬計算機(jī)；運(yùn)籌學(xué)7計算機(jī)編程計算機(jī)8預(yù)測理論運(yùn)籌學(xué)9數(shù)學(xué)實驗運(yùn)籌學(xué)；計算機(jī)最少2門數(shù)學(xué)

57、課三門運(yùn)籌學(xué)課共一百二十三頁先修課程(kchng)要求最優(yōu)解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它(qt)為0；6門課程，總學(xué)分21 0-1規(guī)劃模型 約束條件x3=1必有x1 = x2 =1模型求解(LINDO)課號課名先修課要求1微積分2線性代數(shù)3最優(yōu)化方法微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)計算機(jī)編程5應(yīng)用統(tǒng)計微積分；線性代數(shù)6計算機(jī)模擬計算機(jī)編程7計算機(jī)編程8預(yù)測理論應(yīng)用統(tǒng)計9數(shù)學(xué)實驗微積分；線性代數(shù)共一百二十三頁學(xué)分最多多目標(biāo)優(yōu)化的處理方法(fngf)：化成單目標(biāo)優(yōu)化。兩目標(biāo)(mbio)(多目標(biāo))規(guī)劃 討論：選修課程最少，學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？ 課程最少

58、以學(xué)分最多為目標(biāo)，不管課程多少。 以課程最少為目標(biāo)，不管學(xué)分多少。最優(yōu)解如上，6門課程，總學(xué)分21 。最優(yōu)解顯然是選修所有9門課程 。共一百二十三頁多目標(biāo)(mbio)規(guī)劃 在課程最少的前提(qint)下以學(xué)分最多為目標(biāo)。最優(yōu)解： x1 = x2 = x3 = x5 = x7 = x9 =1, 其它為0；總學(xué)分由21增至22。注意：最優(yōu)解不唯一！課號課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計46計算機(jī)模擬37計算機(jī)編程28預(yù)測理論29數(shù)學(xué)實驗3 LINDO無法告訴優(yōu)化問題的解是否唯一?？蓪9 =1 易為x6 =1增加約束 ，以學(xué)分最多為目標(biāo)求解。共一百二十三頁多目標(biāo)(m

59、bio)規(guī)劃 對學(xué)分?jǐn)?shù)(fnsh)和課程數(shù)加權(quán)形成一個目標(biāo)，如三七開。 最優(yōu)解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1，其它為0；總學(xué)分28。課號課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計46計算機(jī)模擬37計算機(jī)編程28預(yù)測理論29數(shù)學(xué)實驗3共一百二十三頁討論(toln)與思考最優(yōu)解與1=0，2=1的結(jié)果(ji gu)相同學(xué)分最多多目標(biāo)規(guī)劃 最優(yōu)解與1=1，2=0的結(jié)果相同課程最少共一百二十三頁 飲料廠的生產(chǎn)(shngchn)與檢修單階段生產(chǎn)(shngchn)計劃多階段生產(chǎn)計劃 生產(chǎn)批量問題 企業(yè)生產(chǎn)計劃考慮與產(chǎn)量無關(guān)的固定費(fèi)

60、用給優(yōu)化模型求解帶來新的困難外部需求和內(nèi)部資源隨時間變化共一百二十三頁 如何安排生產(chǎn)(shngchn)計劃, 滿足每周的需求, 使4周總費(fèi)用最??？每周有剩余(shngy)時，要支付存貯費(fèi):每周每千箱飲料 0.2千元。 例1 飲料廠的生產(chǎn)與檢修計劃 在4周內(nèi)安排一次設(shè)備檢修，占用當(dāng)周15千箱生產(chǎn)能力，能使檢修后每周增產(chǎn)5千箱，檢修應(yīng)排在哪一周? 周次需求量(千箱)生產(chǎn)能力(千箱)成本(千元/千箱)115305.0225405.1335455.4425205.5合計100135生產(chǎn)某種飲料4周的需求量、生產(chǎn)能力和成本如下表。共一百二十三頁問題(wnt)分析 除第4周外每周的生產(chǎn)能力超過每周的需求(