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

1、Max min優(yōu)化是人類認識世界和改善自身的重要內容認識世界： 我們身邊的許多事物都是大自然優(yōu)勝劣汰的長期演化的產(chǎn)物，在長期的生存競爭中形成了優(yōu)化的結構和運動特征。如 魚的體形 鳥和蜜蜂的巢穴 動物的肌肉、植物的葉片的形狀 蝶的飛行線路、魚的游動軌跡等，從能量消耗、結構穩(wěn)定和強度、效率等不同指標分析顯現(xiàn)優(yōu)化特征。因此，優(yōu)化是深入認識世界的重要手段。自然界本身也在某些方面顯現(xiàn)優(yōu)化特征。最重要的是任意物體在宏觀運動中都遵循“作用量最小”的自然規(guī)律。因此，我們觀察到的自然現(xiàn)象如 球的彈起軌跡 水滴的下落時的形狀改變 . 等一切運動現(xiàn)象都是優(yōu)化的結果。當前，“作用量最小”原則是我們描述自然界運動的基本

2、工具。優(yōu)化是人類改善自身的重要手段節(jié)能：對能源使用的優(yōu)化；規(guī)劃：對管理效率的優(yōu)化；最優(yōu)控制：對運動系統(tǒng)效率、性能等的優(yōu)化；設計、工藝、結構的優(yōu)化.總之，人類的發(fā)展本身就是一個優(yōu)化的過程。例如，工藝的改善的定量分析歸結為工藝的優(yōu)化；設計的改進的定量分析歸結為設計的優(yōu)化等。在中學和大學微積分中，我們學習過求函數(shù)的極值和條件極值問題。這是我們對簡單問題優(yōu)化的基本數(shù)學工具。下面討論利用這些工具建模的幾個例子1 1、存貯、存貯模型模型 在商業(yè)活動中，需要批量訂購商品。訂購費用為其中c0是批量訂購的一次性費用，c1是商品單價。批量越大，單位商品的費用越低。 01Pcc x商品購進后，有一個消化過程(銷售或

3、使用)。消化不掉的需要存放，因此形成存貯費用。批量越大，每天存貯費用越高。生產(chǎn)活動有類似的情況。批量生產(chǎn)費用為其中c0是批量生產(chǎn)的生產(chǎn)準備費用，c1是產(chǎn)品單位成本。批量越大，單位產(chǎn)品的費用越低。01Pccx上述問題稱為存貯問題。建立數(shù)學模型以確定最佳訂貨周期和批量，是存貯問題所要解決的問題。兩種問題的數(shù)量關系完全相同，下面只討論商品的批量訂貨問題。產(chǎn)品生產(chǎn)后，有一個消化過程(銷售或使用)。消化不掉的需要存放，因此形成存貯費用。批量越大，每天存貯費用越高。不允許缺貨的存貯模型模型假設1. 商品每天的需求量為常數(shù) r；2. 一次性購貨費為 c0, 每件商品單價c1，每天每件商品貯存費為 c2；3.

4、 T天訂購一次(周期), 每次購買Q件，當貯存量 為零時，Q件商品立即到來(不允許缺貨)；4. 為方便起見，時間和產(chǎn)量都作為連續(xù)量處理。問題：r, c0,c1, c2 已知，求T, Q 使每天總費用的平均值最小。模型建立0tqTQrA=QT/2一個周期的總費用是購貨費用和存貯費用的和購貨費用: P=c0+c1Q無缺貨假設： Q=rT平均每天的費用： 0212ccPRCc rrTTT存貯費用 : R=c2A=c2QT/2模型求解0dTdC022cTrc022c rQrTc模型分析1、最佳周期長度與商品價格無關；2、0,cT QQTc,2QTr,允許缺貨的存貯模型原模型假設：貯存量降到零時Q件立即

5、生產(chǎn)出來(或立即到貨)。若貯存量降到零時仍有需求r,但 不能立即到貨，則出現(xiàn)缺貨而造成損失。如果允許缺貨，模型應如何修改？補充假設：允許缺貨, 每天每件缺貨損失費 c3 , 缺貨需補足T1rTQ 0qQrT1tAB一周期貯存費AcdttqcT2021)(一周期缺貨費BcdttqcTT331)(2110123()22QTr T TCccQ cc一周期總費用rTQrTcrTQcTcTCQTC2)(2),(232210,0QCTC332212cccrccT323212ccccrcQ為與不允許缺貨的存貯模型相比，T記作T , Q記作Q每天的費用為2 . 生豬的出售時機生豬的出售時機飼養(yǎng)場每天投入4元資

6、金，用于飼料、人力、設備，估計可使80千克重的生豬體重增加2公斤。市場價格目前為每千克8元，但是預測每天會降低 0.1元，問生豬應何時出售。如果估計和預測有誤差，對結果有何影響?模型分析投入資金使生豬體重隨時間增加，出售單價隨時間減少，尋找最佳最佳出售出售時機時機( (決策變量決策變量) )，使利潤利潤最大最大(目標)。建模及求解生豬體重 w=80+rt出售單價 p=8-gt銷售收入 R=pw資金投入 C=4t設生豬重量w，單價p，每天增加體重r，每天單價降低g，t天后出售，則屆時利潤：trtgttQ4)80)(8()(求 t 使Q(t)最大得到rggrt2404敏感性分析求出的生豬最佳出售時

7、間t與參數(shù)r和g有關。而這兩個參數(shù)來源于我們的估計和預測。參數(shù)的變化對結果的影響的大小稱為結果對參數(shù)的敏感性。敏感程度的定義：結果t對參數(shù)r的敏感度記為其意義是結果t的增加率和參數(shù)r增加率的比。 /( , )/t tS t rr r參數(shù)變化的敏感程度的大小反映出問題或模型的穩(wěn)定性。由于在實際問題中，所采集的參數(shù)往往有誤差,當敏感程度較大時，必須考慮參數(shù)的微小變化帶來的影響。當參數(shù)變化較小時，可以利用微分作為增量的近似。這時，參數(shù)的敏感度計算的近似公式為/( , )/t tdt rS t rr rdr t生豬出售時機問題的解 rggrt2404當r=2，g=0.1時，( , )3dt rS t

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

9、失費) 4、每個隊員的單位時間滅火費用c2, 一次性費用c3森林救火假設1的解釋：假設1基于以下簡化假設：火源向周圍勻速蔓延，這樣，到t時刻，森林過火區(qū)域為B(t)=(vt)2。面積 B與 t2成正比， dB/dt與 t成正比.比例系數(shù)稱為蔓延率。森林救火dtdBb0t1t假設1假設2t2xxbtt12,1tbxttt112220( )tdBB tdtdt)(222212212xttbtxcttxcxftBcxf31222211)()(),()(假設3、4模型建立森林救火目標函數(shù)總費用)()()(21xfxfxC222111121322()ctctct xc xxx模型求解求 x使 C(x)最

10、小0dxdC231221122ctctcxdtdBb0t1t2tx森林救火231221122ctctcx結果解釋 / :火勢不繼續(xù)蔓延的最少救火人員數(shù)c1燒毀單位面積損失費, c2每個隊員單位時間滅火費, c3每個隊員一次性費用, t1開始救火時刻, 火勢蔓延速度, 每個隊員平均滅火速度. c2 x c1, t1, x c3 , x 為什么?森林救火例4： 冰山運輸背景 波斯灣地區(qū)水資源貧乏，淡水主要靠海水淡化，淡化海水的成本為每立方米0.1英鎊。 專家建議從9600千米遠的南極用拖船運送冰山，取代淡化海水。 從經(jīng)濟角度研究冰山運輸?shù)目尚行浴＝?shù)據(jù)準備1. 日租金和最大運量船 型小 中 大日

11、租金(英鎊) 最大運量(米3)4.06.28.05 105106107 冰山運輸2. 燃料消耗(英鎊/千米)3. 融化速率(米/天)與南極距離 (千米)船速(千米/小時) 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 冰山運輸建模目的選擇船型和船速，使冰山到達目的地后每立米水的費用最低，并與淡化海水的費用比較。模型假設 航行過程中船速不變，總距離9600千米 冰山呈球形，球面各點融化速率相同到達目

12、的地后，每立方米冰可融化0.85立方米水 冰山運輸建模分析目的地水體積運輸過程融化規(guī)律總費用目的地冰體積初始冰山體積燃料消耗租金船型, 船速船型船型, 船速船型,船速決策變量：船速，船型目標：每立方水的費用如何從離散數(shù)據(jù)中挖掘出有用的信息？ 冰山運輸4000),1 (40000),1 (21dbuadbudar4 . 0, 2 . 0,105 . 6251baa模型建立1. 冰山融化規(guī)律 船速u (千米/小時)與南極距離d(千米)融化速率r(米/天）r是 u 的線性函數(shù)；d4000時u與d無關.utd24航行航行 t 天天utuuttuurt61000),4 . 01 (2 . 0610000

13、,)4 . 01 (1056. 13第t天融化速率 0 1000 4000135 0 0.1 0.3 0 0.15 0.45 0 0.2 0.6urd 冰山運輸模型建立冰山體積變化規(guī)律 tkktrRR10冰山初始半徑R0，航行t天時半徑冰山初始體積30034RV334ttRVt天時體積總航行天數(shù)313004334),(tkkrVtVuV選定u,V0, 航行t天時冰山體積313004334),(TttrVVuV到達目的地時冰山體積uuT400249600 冰山運輸1, 6, 3 . 0321ccc14334log)6(2 . 7),()log(24),(3130103010210tkkrVuuc

14、tVuVcucutVuq),)(log(310211cVcucq2. 燃料消耗 105 106 107135 8.4 10.5 12.6 10.8 13.5 16.2 13.2 16.5 19.8Vuq1燃料消耗數(shù)據(jù) q1(英鎊/千米)q1對u線性, 對log10V線性選定u,V0, 航行第t天燃料消耗 q (英鎊/天)燃料消耗總費用TttVuqVuQ100),(),(模型建立 冰山運輸3. 運送每立方米水費用 冰山初始體積V0的日租金 f(V0)(英鎊)uT400航行天數(shù)總燃料消耗費用拖船租金費用uVfVuR400)(),(00冰山運輸總費用),(),(),(000VuQVuRVuS1433

15、4log)6(2 . 7),(31301010tkkTtrVuuVuQ模型建立 冰山運輸模型求解選擇船型和船速，使冰山到達目的地后每立方米水的費用最低求 u,V0使Y(u,V0)最小u=45( (千米千米/ /小時小時), ), V0= 10 107 7 ( (米米3 3) )， Y(u,V0)最小最小V0只能取離散值經(jīng)驗公式很粗糙33.544.551070.07230.06830.06490.06630.06580.22510.20130.18340.18420.179010678.90329.82206.21385.46474.5102V0u5 106取幾組(V0,u)用枚舉法計算0000

16、( ,)( ,)( ,)0.85 ( ,)R u VQ u VY u VV u V 冰山運輸結果分析由于未考慮影響航行的種種不利因素，冰山到達目的地后實際體積會顯著小于V(u,V0)。有關部門認為，只有當計算出的Y(u,V0)顯著低于淡化海水的成本時，才考慮其可行性。大型拖船V0= 107 (米3)，船速 u=45(千米/小時), 冰山到達目的地后每立米水的費用 Y(u,V0)約0.065(英鎊)雖然0.065英鎊略低于淡化海水的成本0.1英鎊，但是模型假設和構造非常簡化與粗糙。 冰山運輸有約束的優(yōu)化問題的一般數(shù)學描述為 11min( ). .( )0.( )0( )0.( )0 xmlnfs

17、tgghhxRxxxxx當變量個數(shù)和約束條件的個數(shù)較多時，像處理簡單優(yōu)化模型那樣隨意建模很難把問題處理好。因此需要新的建模和求解思路。這種規(guī)模較大的優(yōu)化問題稱為規(guī)劃問題。規(guī)劃問題的建模特點分類研究規(guī)范化建模和計算分離優(yōu)化模型的分類數(shù)學規(guī)劃模型線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃和混合規(guī)劃動態(tài)規(guī)劃網(wǎng)絡優(yōu)化變分模型連續(xù)動態(tài)優(yōu)化線性規(guī)劃模型的數(shù)學結構線性規(guī)劃模型的一般形式為11min. .Txc xstAxbAxbLxUmatlab中的線性規(guī)劃函數(shù)只處理上述形式的模型，其他形式要先化為上述形式。求解線性規(guī)劃問題的基本思路求解線性規(guī)劃問題的基本方法是單純形法。考慮一個簡單的問題：127264Min zxx 50

18、21 xx48081221 xx10031x0,21xx滿足約束條件的點集稱為可行域，規(guī)劃問題就是從可行域中尋找目標函數(shù)的最優(yōu)解。約束條件5021 xx48081221 xx10031x0,21xxl1l2l3l4l5Z=0Z=-2400Z=-3600ABCD127264Min zxx 目標函數(shù) z=c (常數(shù)) 等值線在B(20,30)點得到最優(yōu)解目標函數(shù)和約束條件是線性函數(shù) 可行域為線段圍成的凸多邊形 目標函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊形的某個頂點取得。 可行域奶制品廠用牛奶生產(chǎn)A1,A2兩種奶制品。一桶牛奶可在甲類設備上用12小時加工成3公斤A1，或在乙類設備上用8小時加工成4公

19、斤A2。生產(chǎn)的A1,A2全部都能售出，且每公斤A1獲利24元，每公斤A2獲利16元。加工廠每天能得到50桶牛奶，每天正式工人總的勞動時間為480小時，甲類設備每天至多加工100公斤A1，乙類設備的加工能力沒有限制。試為該廠制定一個生產(chǎn)計劃，使每天獲利最大。例1：加工奶制品的生產(chǎn)計劃1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶 480小時 至多加工100公斤A1 每天：制訂生產(chǎn)計劃，使每天獲利最大 35元可買到1桶牛奶，買嗎？若買，每天最多買多少? 可

20、聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到 30元/公斤，應否改變生產(chǎn)計劃？ 1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)A2 獲利 243x1 獲利 164 x2 原料供應 5021 xx勞動時間 48081221 xx加工能力 10031x決策變量 目標函數(shù) 216472xxzMax每天獲利約束條件非負約束 0,21xx線性規(guī)劃模型(LP)模型求解模型求解 軟件實現(xiàn)軟件實現(xiàn) LINDOmax 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECT

21、IVE 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)A2，利潤3360元。 no結果解釋結果解釋 OBJECTIVE

22、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原料無剩余時間無剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三種資源“資源” 剩余為零的約束為緊約束

23、(有效約束) 結果解釋 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最優(yōu)解下“資源”增加1單位時“效益”的增量 原料增加1單位, 利潤增長48 時間增加1單位, 利潤增長2 加工能力增長不影響利潤

24、影子價格影子價格 35元可買到1桶牛奶，要買嗎？35 48, 應該買！ 聘用臨時工人付出的工資最多每小時幾元？ 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.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE

25、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)解不變時目標函數(shù)系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? x1系數(shù)范圍(64,96) x2系數(shù)范圍(48,72) A1獲利增加到 30元/千克，應否改變生產(chǎn)計劃 x1系數(shù)由由24 3=72增加為30 3=90，在允許范圍內 不變！(約束條件不變)結果解釋 RANGES IN WHICH THE BASIS IS UNCH

26、ANGED: 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 ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.

27、000000 INFINITY 40.000000影子價格有意義時約束右端的允許變化范圍 原料最多增加10 時間最多增加53 35元可買到1桶牛奶，每天最多買多少？最多買10桶!(目標函數(shù)不變)例2 奶制品的生產(chǎn)銷售計劃 在例1條件下，為增加工廠的利潤，開發(fā)奶制品深加工技術：用2小時和3元加工費，可將1公斤A1加工成0.8公斤高級奶制品B1,也可以將1公斤A2加工成0.75公斤高級奶制品B2。1公斤B1可獲利44元， 1公斤B2可獲利32元。試為該廠制定生產(chǎn)銷售計劃，使每天的凈利潤最大，并討論以下問題：(1)若投資30元可增加供應1桶牛奶，投資3元可增加一小時工作時間，應否作這些投資？若每天投

28、資150元，可賺回多少？(2)每公斤高級奶制品的獲利經(jīng)常有10%的波動，這對制定的生產(chǎn)銷售計劃有沒有影響？若每公斤B1的獲利下降10%，計劃應該變化嗎？在例1基礎上深加工1 桶牛奶 3千克千克A1 12小時小時 8小時小時 4公斤公斤A2 或或獲利獲利24元元/公斤公斤 獲利獲利16元元/公斤公斤 0.8千克千克B12小時小時,3元元1千克千克獲利獲利44元元/千克千克 0.75千克千克B22小時小時,3元元1千克千克獲利獲利32元元/千克千克 制訂生產(chǎn)計劃，使每天凈利潤最大 30元可增加1桶牛奶，3元可增加1小時時間，應否投資？現(xiàn)投資150元，可賺回多少？50桶牛奶, 480小時 至多100

29、公斤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元元/千克千克 出售x1 千克 A1, x2 千克 A2， x3千克 B1, x4千克 B2原料原料供應供應 加工能力加工能力 決策變量 目標函數(shù) 利潤利潤約束條件非負約束非負約束 16,0 xx Lx5千克 A1加工B1， x6千克 A2加工B26543213332441

30、624xxxxxxzMax50436251xxxx48022)(2)(4656251xxxxxx10051 xx附加約束附加約束 5380 x.x64750 x.x 勞動勞動時間時間 運輸問題生產(chǎn)、生活物資從若干供應點運送到一些需求點，怎樣安排輸送方案使運費最小，或利潤最大？各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少？例1 自來水輸送某城市有甲、乙、丙、丁四個居民區(qū)，自來水由A,B,C三個水庫供應。四個區(qū)每天必須得到的基本生活用水量分別為30，70，10，10千噸，此外 ，四個區(qū)都向公司申請了額外用水量，分別為每天50，70，20，40千噸。由于水源緊

31、張，三個水庫每天最多只能分別供應50，60，50千噸。由于地理位置的差別，自來水公司從各水庫向各區(qū)送水付出的引水管理費不同（見表），其他管理費都是450元/千噸。各區(qū)用戶按統(tǒng)一標準900元/千噸收費。如何分配用水量能獲利最多？ 引水管理費引水管理費甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/其他費用:450元/千噸 應如何分配水庫供水量，公司才能獲利最多？ 若水庫供水量都提高一倍，公司利潤可增加到多少？ 元元/千噸千噸甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理費收入：900元/千噸 支出A：5

32、0B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水庫供水量(千噸)小區(qū)基本用水量(千噸)小區(qū)額外用水量(千噸)(以天計)總供水量：160確定送水方案使利潤最大問題分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20?。憾。?0；40 總需求量(300)每個水庫最大供水量都提高一倍每個水庫最大供水量都提高一倍利潤 = 收入(900) 其它費用(450) 引水管理費利潤利潤(元元/千噸千噸)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/33323124232221141312112202502603

33、00260320310280230320290 xxxxxxxxxxxZMax供應限制B, C 類似處理50:A14131211xxxx10014131211xxxx問題2 確定送水方案使利潤最大需求約束可以不變例2 貨機裝運某架飛機有三個貨艙：前艙、中艙和后艙。三個貨艙所能裝載貨物的最大重量和最大體積都有限制(如表1)。并且為了保持飛機的平衡，三個貨艙中實際裝載貨物的重量必須與其最大容許重量成比例。現(xiàn)有四類貨物供該貨機本次飛行裝運，有關信息見表2.應如何安排裝機使本次飛行獲利最大？前艙前艙 中艙中艙 后艙后艙重量限制10 16 8體積限制6800 8700 5300 重量重量(T) 空間空間

34、(m3/T) 利潤利潤(元元/T)貨物1 18 480 3100貨物2 15 650 3800貨物3 23 580 3500貨物4 12 390 2850表 1表 2如何裝運，使本次飛行獲利最大？ 三個貨艙最大載重(噸),最大容積(米3) 重量(噸)空間( 米3/噸) 利潤(元/噸)貨物1184803100貨物2156503800貨物3235803500貨物4123902850三個貨艙中實際載重必須與其最大載重成比例 前倉：前倉：10；6800中倉：中倉：16；8700后倉：后倉：8；5300飛機平衡決策變量 xij-第i 種貨物裝入第j 個貨艙的重量(噸)i=1,2,3,4, j=1,2,3

35、 (分別代表前、中、后倉)模型假設 每種貨物可以分割到任意小；每種貨物可以在一個或多個貨艙中任意分布；多種貨物可以混裝，并保證不留空隙； 模型建立 貨艙容積 目標函數(shù)(利潤)約束條件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxZMax680039058065048041312111xxxx870039058065048042322212xxxx530039058065048043332313xxxx貨機裝運模型建立 貨物重量 1041312111xxxx1642322212xxxx843332313xxxx10；68

36、0016；87008；5300 xij-第i 種貨物裝入第j 個貨艙的重量決策變量約束條件平衡要求 81610433323134232221241312111xxxxxxxxxxxx貨物供應 18131211xxx15232221xxx23333231xxx12434241xxx模型建立 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 57.894737

37、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 貨物2：前倉10,后倉5； 貨物3: 中倉13, 后倉3；貨物4: 中倉3。模型求解 最大利潤約121516元貨物供應點貨艙需求點平衡要求運

38、輸問題運輸問題的擴展 如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛， 那么最優(yōu)的生產(chǎn)計劃應作何改變？汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現(xiàn)有量。 小型 中型 大型 現(xiàn)有量鋼材(噸) 1.5 3 5 600勞動時間(小時) 280 250 400 60000利潤(萬元) 2 3 4 制訂月生產(chǎn)計劃，使工廠的利潤最大。汽車生產(chǎn)與原油采購決策變量：每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1, x2, x3321432xxxzMax600535.1.321xxxts60000400250280321xxx0,321xxx汽車廠生產(chǎn)計劃 模型建立 小型小型 中型中

39、型 大型大型 現(xiàn)有量現(xiàn)有量鋼材鋼材 1.5 3 5 600時間時間 280 250 400 60000利潤利潤 2 3 4 線性線性規(guī)劃規(guī)劃模型模型(LP)模型求解 3、 模型中增加條件：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 2 ) 0 . 0 0 0 0 0 0 0

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

41、x3=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 321432xxxzMax600535 . 1.321xxxts60000400250280321xxx為非負整數(shù)321,xxx模型求解 IP 結果輸出其中3個子模型應去掉

42、，然后逐一求解，比較目標函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：80, 0, 0321xxx0,80, 0321xxx80,80, 0321xxx0, 0,80321xxx0,80,80321xxx80, 0,80321xxx80,80,80321xxx0,321xxx方法1：分解為8個LP子模型 汽車廠生產(chǎn)計劃 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。321432xxxzMax600535 . 1.321xxxts60000400250280321xxxx1, ,x2, x3=0 或或 80 x1=80，x2= 150，x3=0，最優(yōu)值z=610LINDO中對中對0-1變量的限定：變量的限定

43、：int y1int y2int y3 方法2：引入0-1變量，化為整數(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 Y1 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 或 8

44、01 , 0,80,11111yyxMyx1 , 0,80,22222yyxMyx1 , 0,80,33333yyxMyx最優(yōu)解同前 NLP雖然可用現(xiàn)成的數(shù)學軟件求解(如LINGO, MATLAB)，但是其結果常依賴于初值的選擇。 方法3：化為非線性規(guī)劃 非線性規(guī)劃(Non- Linear Programming，簡記NLP) 實踐表明，本例僅當初值非常接近上面方法算出的最優(yōu)解時，才能得到正確的結果。 若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計劃。 x1=0 或 80 x2=0 或 80 x3=0 或 800)80(11xx0)80(22xx0)80(33xx例2 原油采購與加工 某公司用兩種

45、原油(A和B)混合加工兩種汽油(甲和乙)。甲、乙兩種汽油含原油A的最低比例分別為50%和60%，每噸售價分別為4800元和5600元。該公司現(xiàn)有原油A和B的庫存量分別為500噸和1000噸，還可以從市場上買到不超過1500噸的原油A。原油A的市場價為：購買量不超過500噸時的單價為10000元/噸；購買量超過500噸但不超過1000噸時，超過500噸部分8000元/噸；購買量超過1000噸時，超過1000噸部分6000元/噸。該公司應該如何安排原油的采購和加工？應如何安排原油的采購和加工 ？ 市場上可買到不超過1500噸的原油A： 購買量不超過500噸時的單價為10000元/噸； 購買量超過5

46、00噸但不超過1000噸時，超過500噸的 部分8000元/噸； 購買量超過1000噸時，超過1000噸的部分6000元/噸。 售價4800元/噸 售價5600元/噸庫存500噸 庫存1000噸 汽油甲(A 50%) 原油A 原油B 汽油乙 (A 60%) 決策變量 目標函數(shù)問題分析 利潤：銷售汽油的收入 - 購買原油A的支出 難點：原油A的購價與購買量的關系較復雜)()(6 . 5)( 8 . 422122111xcxxxxzMax甲(A 50%) A B 乙(A 60%) 購買購買xx11x12x21x224.8千元/噸 5.6千元/噸原油A的購買量,原油A, B生產(chǎn)汽油甲,乙的數(shù)量c(x

47、) 購買原油A的支出利潤(千元)c(x)如何表述？原油供應 約束條件xxx500121110002221 xx1500 x500)1(1000 300061000)(500 1000 8500)(0 10)(xxxxxxxc x 500噸單價為10千元/噸； 500噸 x 1000噸，超過500噸的8千元/噸；1000噸 x 1500噸，超過1000噸的6千元/噸。 目標函數(shù)購買x x11x12x21x22A B 庫存500噸 庫存1000噸 目標函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃； 對于用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟件也難以輸入和求解； 想辦法將模型化簡，用現(xiàn)成的軟件求解

48、。 汽油含原油A的比例限制 5 . 0211111 xxx6 . 0221212 xxx2111xx 221232xx 約束條件甲甲(A 50%) A B 乙乙(A 60%) x11x12x21x22x1 , x2 , x3 以價格10, 8, 6(千元/噸)采購A的噸數(shù)目標函數(shù) 只有當以10千元/噸的價格購買x1=500(噸)時，才能以8千元/噸的價格購買x2方法1 )6810()( 6 . 5)( 8 . 432122122111xxxxxxxzMax0)500(32xx500,0321xxx非線性規(guī)劃模型，可以用LINGO求解模型求解 500噸 x 1000噸，超過500噸的8千元/噸增

49、加約束增加約束x= x1+x2+x3, c(x) = 10 x1+8x2+6x3 方法1：LINGO求解Model:Max= 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.

50、000Variable Value Reduced CostX 1 1 5 0 0 . 0 0 0 0 0.0000000E+00X 2 1 5 0 0 . 0 0 0 0 0.0000000E+00X 1 2 0 . 0 0 0 0 0 0 0 E + 0 0 0.0000000E+00X 2 2 0 . 0 0 0 0 0 0 0 E + 0 0 0.0000000E+00 X1 0.1021405E-13 10.00000 X2 0.0000000E+00 8.000000 X3 0.0000000E+00 6.000000 X 0 . 0 0 0 0 0 0 0 E + 0 0 0.0

51、000000E+00 LINGO得到的是局部最優(yōu)解，還能得到更好的解嗎？ 用庫存的500噸原油A、500噸原油B生產(chǎn)汽油甲，不購買新的原油A，利潤為4,800千元。 y1, y2 , y3=1 以價格10, 8, 6(千元/噸)采購A增增加加約約束束方法2 0-1線性規(guī)劃模型，可用LINDO求解112500500yxy223500500yxy33500yx y1,y2,y3 =0或1 OBJECTIVE FUNCTION VALUE 1) 5000.000 VARIABLE VALUE REDUCED COST Y1 1.000000 0.000000 Y2 1.000000 2200.000

52、000 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 500.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ù)

53、y=0 x=0 x0 y=1優(yōu)于方法1的結果方法方法3 b1 x b2，x= z1b1+z2b2，z1+z2=1，z1, z2 0, c(x)= z1c(b1)+z2c(b2).c(x)x1200090005000050010001500b2 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). 500)1(1000 300061000)(500 1000 8500)(0 10)(xxxxxxxc 直接處理

54、處理分段線性函數(shù)直接處理處理分段線性函數(shù)c(x) IP模型，模型，LINDO求求解，得到的結果與解，得到的結果與方法方法2相同相同. .處理分段線性函數(shù)，方法3更具一般性44332211bzbzbzbzx)()()()()(44332211bczbczbczbczxcbkxbk+1yk=1,否則,yk=03432321211,yzyyzyyzyz)4 , 3 , 2 , 1(0, 14321kzzzzzk10, 1321321或yyyyyy方法3 bkxbk+1 ,x= zkbk+z k+1 bk+1zk+zk+1 =1，zk, zk+1 0, c(x)= zkc(bk)+zk+1 c(bk+

55、1 ).c(x)x1200090005000050010001500b1 b2 b3 b4對于對于k=1,2,3分派問題接力隊選拔和選課策略若干項任務分給一些候選人來完成，每人的專長不同，完成每項任務取得的效益或需要的資源就不同，如何分派任務使獲得的總效益最大，或付出的總資源最少。若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個策略之間有相互制約關系，如何在滿足一定條件下作出決擇，使得收益最大或成本最小。丁的蛙泳成績退步到115”2；戊的自由泳成績進步到57”5, 組成接力隊的方案是否應該調整？如何選拔隊員組成4100米混合泳接力隊? 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2

56、118”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目標函數(shù)隊員i參加泳姿j ，則記xij=1, 否則記xij=0 cij(秒)隊員i 第j 種泳姿的百米成績約束條件每人最多入選泳姿之一 4151jiij

57、ijxcZMin每種泳姿有且只有1人 411,1,5ijjxiL511,1,4ijixjL決策變量決策變量模型求解 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)解：最優(yōu)解：x14 = x21 = x32 = x43 = 1, 其它變量為其它變量為0;成績?yōu)槌煽優(yōu)?53.2( (秒秒) )=413

58、”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, , 方案是否調整？方案是否調整？ 乙乙 蝶泳、丙蝶泳、丙 仰泳、丁仰泳、丁 蛙泳、戊蛙泳、戊 自由泳自由泳IP規(guī)劃一般沒有與LP規(guī)劃相類似的理論，LINDO輸出的敏感

59、性分析結果通常是沒有意義的。最優(yōu)解：最優(yōu)解：x21 = x32 = x43 = x51 = 1, 成績?yōu)槌煽優(yōu)?17”7 c43, c54 的新數(shù)據(jù)重新輸入模型，用的新數(shù)據(jù)重新輸入模型，用LINDO求解求解 指派指派( (Assignment) )問題問題：每項任務有且只有一人承擔，每人只能每項任務有且只有一人承擔，每人只能承擔一項承擔一項，效益不同，怎樣分派使總效益最大，效益不同，怎樣分派使總效益最大. 討論討論甲甲 自由泳、乙自由泳、乙 蝶泳、丙蝶泳、丙 仰泳、丁仰泳、丁 蛙泳蛙泳. .原原方方案案為了選修課程門數(shù)最少，應學習哪些課程 ？ 課號課號課名課名學分學分所屬類別所屬類別先修課要求

60、先修課要求1微積分微積分5數(shù)學數(shù)學2線性代數(shù)線性代數(shù)4數(shù)學數(shù)學3最優(yōu)化最優(yōu)化4數(shù)學；運籌學數(shù)學；運籌學微積分；微積分；線代線代4數(shù)據(jù)結構數(shù)據(jù)結構3數(shù)學；計算機數(shù)學；計算機計算機編程計算機編程5應用統(tǒng)計應用統(tǒng)計4數(shù)學；運籌學數(shù)學；運籌學微積分；微積分；線代線代6計算機模擬計算機模擬3計算機；計算機；運籌運籌計算機編程計算機編程7計算機編程計算機編程2計算機計算機8預測理論預測理論2運籌學運籌學應用統(tǒng)計應用統(tǒng)計9數(shù)學實驗數(shù)學實驗3運籌；運籌；計算機計算機微積分；微積分；線代線代選修課程最少，且學分盡量多，應學習哪些課程 ？ 0-1規(guī)劃模型 決策變量 目標函數(shù) xi=1 選修課號i 的課程（xi=0