數(shù)學(xué)建模第四講

1、第四講第四講 數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型( (一一) ) 4.1 奶制品的生產(chǎn)奶制品的生產(chǎn)4.2 自來水輸送與貨機裝運自來水輸送與貨機裝運數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 實際問題中實際問題中的優(yōu)化模型的優(yōu)化模型T1min(max)( ),(,)s.t.( )0,1,2,nizf xxxxg xim或x決策變量決策變量f(x)目標(biāo)函數(shù)目標(biāo)函數(shù)gi(x) 0約束條件約束條件多元函數(shù)多元函數(shù)條件極值條件極值 決策變量個數(shù)決策變量個數(shù)n和和約束條件個數(shù)約束條件個數(shù)m較大較大 最優(yōu)解在可行域最優(yōu)解在可行域的邊界上取得的邊界上取得 數(shù)數(shù)學(xué)學(xué)規(guī)規(guī)劃劃線性規(guī)劃線性規(guī)劃非線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃重點在模型的建

2、立和結(jié)果的分析重點在模型的建立和結(jié)果的分析企業(yè)生產(chǎn)計劃企業(yè)生產(chǎn)計劃4.1 奶制品的生產(chǎn)與銷售奶制品的生產(chǎn)與銷售 空間層次空間層次工廠級：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等工廠級：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤為目標(biāo)制訂產(chǎn)品生產(chǎn)計劃；條件，以最大利潤為目標(biāo)制訂產(chǎn)品生產(chǎn)計劃；車間級：根據(jù)生產(chǎn)計劃、工藝流程、資源約束及費車間級：根據(jù)生產(chǎn)計劃、工藝流程、資源約束及費用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計劃用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計劃.時間層次時間層次若短時間內(nèi)外部需求和內(nèi)部資源等不隨時間變化，可若短時間內(nèi)外部需求和內(nèi)部資源等不隨時間變化，可制訂制訂單階段生產(chǎn)計劃

3、單階段生產(chǎn)計劃，否則應(yīng)制訂多階段生產(chǎn)計劃，否則應(yīng)制訂多階段生產(chǎn)計劃.本節(jié)課題本節(jié)課題一、加工奶制品的生產(chǎn)計劃一、加工奶制品的生產(chǎn)計劃1桶桶牛奶牛奶 3kgA1 12h 8h 4kgA2 或或獲利獲利24元元/kg 獲利獲利16元元/kg 50桶牛奶桶牛奶 時間時間480h 至多加工至多加工100kgA1 制訂生產(chǎn)計劃，使每天獲利最大制訂生產(chǎn)計劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到的獲利增加到 30元元/kg，應(yīng)否改變

4、生產(chǎn)計劃？，應(yīng)否改變生產(chǎn)計劃？ 每天：每天：問問題題模型假設(shè)模型假設(shè)1. A1、A2兩種產(chǎn)品每千克的獲利是與它們的各自產(chǎn)兩種產(chǎn)品每千克的獲利是與它們的各自產(chǎn)量無關(guān)的常數(shù)，每桶牛奶加工出量無關(guān)的常數(shù)，每桶牛奶加工出A1、A2的數(shù)量和所的數(shù)量和所需時間是與它們各自產(chǎn)量無關(guān)的常數(shù)；需時間是與它們各自產(chǎn)量無關(guān)的常數(shù)；2. A1、A2兩種產(chǎn)品每千克的獲利是與它們相互間產(chǎn)兩種產(chǎn)品每千克的獲利是與它們相互間產(chǎn)量無關(guān)的常數(shù)，每桶牛奶加工出量無關(guān)的常數(shù)，每桶牛奶加工出A1、A2的數(shù)量和所的數(shù)量和所需時間是與它們相互間產(chǎn)量無關(guān)的常數(shù)；需時間是與它們相互間產(chǎn)量無關(guān)的常數(shù)；3. 加工加工A1、A2的牛奶桶數(shù)可以是任意

5、實數(shù)。的牛奶桶數(shù)可以是任意實數(shù)。1桶桶牛奶牛奶 3kgA1 12h 8h 4kgA2 或或獲利獲利24元元/kg 獲利獲利16元元/kg x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動時間勞動時間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472maxxxz每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時間時間480h 至多加工至多加工100kgA1 50桶牛奶桶牛奶 每天每天基本基本模型模型模型求解

6、模型求解 圖解法圖解法 x1x2OABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx約約束束條條件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472maxxxz目標(biāo)目標(biāo)函數(shù)函數(shù) z=0z=2400z=3360z=c (常數(shù)常數(shù)) 等值線等值線c在在B(20,30)點得到最優(yōu)解點得到最優(yōu)解.目標(biāo)函數(shù)和約束條件是線性函數(shù)目標(biāo)函數(shù)和約束條件是線性函數(shù) 可行域為直線段圍成的凸多邊形可行域為直線段圍成的凸多邊形 目標(biāo)函數(shù)的等值線為直線目標(biāo)函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊最優(yōu)解一定在凸多邊形的某個頂點取得

7、形的某個頂點取得. . 模型求解模型求解 軟件實現(xiàn)軟件實現(xiàn) LINGO model:max = 72*x1+64*x2;milk x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3

8、360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤，利潤3360元元. 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元可聘用臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到的獲利增加到 30元元/kg，應(yīng)否改變生產(chǎn)計劃？，應(yīng)否改變生產(chǎn)計劃？ 附加問題的求解附加問題的求解5021 xx48081221 xx10031x21

9、6472maxxxz0,21xx問題問題1,2等價于分析模型中約束等價于分析模型中約束條件右端資源項增加一個單位條件右端資源項增加一個單位會給目標(biāo)函數(shù)增加多少效益。會給目標(biāo)函數(shù)增加多少效益。 問題問題3等價于分析模型中等價于分析模型中目標(biāo)函數(shù)價值系數(shù)的改目標(biāo)函數(shù)價值系數(shù)的改變是否改變最優(yōu)解。變是否改變最優(yōu)解。 線性規(guī)劃的靈敏度分析！線性規(guī)劃的靈敏度分析！結(jié)果解釋結(jié)果解釋 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X

10、1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 model:max = 72*x1+64*x2;milk x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 原料無剩余原料無剩余時間無剩

11、余時間無剩余加工能力剩余加工能力剩余40結(jié)果解釋結(jié)果解釋 Global optimal solution found. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000

12、000最優(yōu)解下最優(yōu)解下“資源資源”增加增加1單位時單位時“效益效益”的增的增量量 影子價格影子價格 35元可買到元可買到1桶牛奶，要買嗎桶牛奶，要買嗎?35 48, 應(yīng)該買！應(yīng)該買！ 聘用臨時工人付出的工資最多每小時幾元聘用臨時工人付出的工資最多每小時幾元? 2元！元！原料增加原料增加1單位單位, 利潤增長利潤增長48 時間增加時間增加1單位單位, 利潤增長利潤增長2 加工能力增長不影響利潤加工能力增長不影響利潤Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allow

13、ableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000 最優(yōu)解不變時目標(biāo)函最優(yōu)解不變時目標(biāo)函數(shù)系數(shù)允許變化

14、范圍數(shù)系數(shù)允許變化范圍 敏感性分析敏感性分析 (“LINGO|Ranges” ) x1系數(shù)范圍系數(shù)范圍(64,96) x2系數(shù)范圍系數(shù)范圍(48,72) A1獲利增加到獲利增加到 30元元/kg，應(yīng)否改變生產(chǎn)計劃，應(yīng)否改變生產(chǎn)計劃? x1系數(shù)由系數(shù)由24 3=72增加增加為為30 3=90，在在允許范圍內(nèi)允許范圍內(nèi) 不變！不變！(約束條件不變約束條件不變)結(jié)果解釋結(jié)果解釋 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable AllowableVariable Coeffic

15、ient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000影子價格有意義時約束右端的允許變化范圍影子價格有意義時約束右端的允許變化范圍 原料最多增加原

16、料最多增加10 時間最多增加時間最多增加53 35元可買到元可買到1桶牛奶桶牛奶, 每天最多買多少每天最多買多少?最多買最多買10桶桶!(目標(biāo)函數(shù)不變目標(biāo)函數(shù)不變)4.2 自來水輸送與貨機裝運自來水輸送與貨機裝運生產(chǎn)、生活物資從若干供應(yīng)點運送到一些需求點，生產(chǎn)、生活物資從若干供應(yīng)點運送到一些需求點，怎樣安排輸送方案使運費最小，或利潤最大怎樣安排輸送方案使運費最小，或利潤最大?運輸問題運輸問題各種類型的貨物裝箱，由于受體積、重量等限制，各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少如何搭配裝載，使獲利最高，或裝箱數(shù)量最少?其他費用其他費用: :450元元/

17、103t 應(yīng)如何分配水庫供水量，公司才能獲利最多？應(yīng)如何分配水庫供水量，公司才能獲利最多？ 若水庫供水量都提高一倍，公司利潤可增加到多少？若水庫供水量都提高一倍，公司利潤可增加到多少？ 元元/ 103t甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理費引水管理費一、一、 自來水輸送自來水輸送收入：收入：900元元/103t 支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20?。憾。?0；40水庫供水量水庫供水量小區(qū)基本用水小區(qū)基本用水量量小區(qū)額外用水量小區(qū)額外用水量（以天計）（以天計）(103t)(103t)

18、(103t)總供水量：總供水量：160確定送水方案確定送水方案使利潤最大使利潤最大問題問題分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20?。憾。?0；40 總需求量總需求量(300)每個水庫最大供水量都提高一倍每個水庫最大供水量都提高一倍利潤利潤 = 收入收入(900) 其他費用其他費用( (450) 引水管理費引水管理費利潤利潤(元元/ 103t )甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/問題二問題二 確定送水方案確定送水方案使利潤最大使利潤最大供應(yīng)供應(yīng)限制限制約束約束條件條件需求需求限制限制 線性線性

19、規(guī)劃規(guī)劃模型模型(LP)10014131211xxxx10012033323124232221xxxxxxx8030312111xxxx3010332313xxx50102414xx目標(biāo)目標(biāo)函數(shù)函數(shù) 3332312423222114131211220250260300260320310280230320290maxxxxxxxxxxxxZ模型建立模型建立 求解求解部分結(jié)果：部分結(jié)果：Objective Value: 88700.00 Variable Value Reduced Cost X11 0.000000 20.000000 X12 100.000000 0.

20、000000 X13 0.000000 40.000000 X14 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000 運輸問題運輸問題總利潤總利潤 88700（元）（元） A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)40100

21、50305030供應(yīng)點供應(yīng)點需求點需求點物資物資供需平衡或不平衡供需平衡或不平衡LINGOLINGO如何如何裝運，裝運，使本次飛行使本次飛行獲利最大？獲利最大？ 三個貨艙三個貨艙最大最大載載重重(t),(t),最大最大容積容積(m(m3 3) ) 二、二、 貨機裝運貨機裝運 重量重量（t）空間空間( m3/t）利潤利潤（元（元/t）貨物貨物1184803100貨物貨物2156503800貨物貨物3235803500貨物貨物4123902850三個貨艙中實際載重必須與其最大三個貨艙中實際載重必須與其最大載載重成比例重成比例. . 前倉：前倉：10；6800中倉：中倉：16；8700后倉：后倉：8

22、；5300飛機平衡飛機平衡模型假設(shè)模型假設(shè) 1. 1. 每種貨物可以分割到任意?。幻糠N貨物可以分割到任意??；2. 2. 每種貨物可以在一個或多個貨艙中任每種貨物可以在一個或多個貨艙中任意分布；意分布；3. 3. 多種貨物可以混裝，并保證不留空隙；多種貨物可以混裝，并保證不留空隙； 4.4.所給出的數(shù)據(jù)都是精確的，沒有誤差所給出的數(shù)據(jù)都是精確的，沒有誤差。 決策決策變量變量 xij-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量(t(t）i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉分別代表前、中、后倉)模型建立模型建立 WET=(10,16,8), VOL=(6800,8700,5300); w=(18,15,23,12), v=(480,650, 580,390), p=(3100,3800,3500,2850).已知參數(shù)已知參數(shù) i=1,2,3,4（貨物），（貨物），j=1,2,3 (分別代表前、中、后倉分別代表前、中、后倉)貨艙貨艙j的重量限制的重量限制WETj ，體積限制體積限制VOLj第第i種貨物的重量種貨物的重量wi，體積，體積vi，利潤，利潤