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

1、第四講第四講 數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型( (一一) ) 4.1 奶制品的生產(chǎn)奶制品的生產(chǎn)4.2 自來(lái)水輸送與貨機(jī)裝運(yùn)自來(lái)水輸送與貨機(jī)裝運(yùn)數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型 實(shí)際問(wèn)題中實(shí)際問(wèn)題中的優(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ù)條件極值條件極值 決策變量個(gè)數(shù)決策變量個(gè)數(shù)n和和約束條件個(gè)數(shù)約束條件個(gè)數(shù)m較大較大 最優(yōu)解在可行域最優(yōu)解在可行域的邊界上取得的邊界上取得 數(shù)數(shù)學(xué)學(xué)規(guī)規(guī)劃劃線性規(guī)劃線性規(guī)劃非線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃重點(diǎn)在模型的建

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

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

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

5、實(shí)數(shù)。的牛奶桶數(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勞動(dòng)時(shí)間勞動(dòng)時(shí)間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472maxxxz每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時(shí)間時(shí)間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)點(diǎn)得到最優(yōu)解點(diǎn)得到最優(yōu)解.目標(biāo)函數(shù)和約束條件是線性函數(shù)目標(biāo)函數(shù)和約束條件是線性函數(shù) 可行域?yàn)橹本€段圍成的凸多邊形可行域?yàn)橹本€段圍成的凸多邊形 目標(biāo)函數(shù)的等值線為直線目標(biāo)函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得

7、形的某個(gè)頂點(diǎn)取得. . 模型求解模型求解 軟件實(shí)現(xiàn)軟件實(shí)現(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，利潤(rùn)，利潤(rùn)3360元元. 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到的獲利增加到 30元元/kg，應(yīng)否改變生產(chǎn)計(jì)劃？，應(yīng)否改變生產(chǎn)計(jì)劃？ 附加問(wèn)題的求解附加問(wèn)題的求解5021 xx48081221 xx10031x21

9、6472maxxxz0,21xx問(wèn)題問(wèn)題1,2等價(jià)于分析模型中約束等價(jià)于分析模型中約束條件右端資源項(xiàng)增加一個(gè)單位條件右端資源項(xiàng)增加一個(gè)單位會(huì)給目標(biāo)函數(shù)增加多少效益。會(huì)給目標(biāo)函數(shù)增加多少效益。 問(wèn)題問(wèn)題3等價(jià)于分析模型中等價(jià)于分析模型中目標(biāo)函數(shù)價(jià)值系數(shù)的改目標(biāo)函數(shù)價(jià)值系數(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三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 原料無(wú)剩余原料無(wú)剩余時(shí)間無(wú)剩

11、余時(shí)間無(wú)剩余加工能力剩余加工能力剩余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單位時(shí)單位時(shí)“效益效益”的增的增量量 影子價(jià)格影子價(jià)格 35元可買到元可買到1桶牛奶，要買嗎桶牛奶，要買嗎?35 48, 應(yīng)該買！應(yīng)該買！ 聘用臨時(shí)工人付出的工資最多每小時(shí)幾元聘用臨時(shí)工人付出的工資最多每小時(shí)幾元? 2元！元！原料增加原料增加1單位單位, 利潤(rùn)增長(zhǎng)利潤(rùn)增長(zhǎng)48 時(shí)間增加時(shí)間增加1單位單位, 利潤(rùn)增長(zhǎng)利潤(rùn)增長(zhǎng)2 加工能力增長(zhǎng)不影響利潤(rùn)加工能力增長(zhǎng)不影響利潤(rùn)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)解不變時(shí)目標(biāo)函最優(yōu)解不變時(shí)目標(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)計(jì)劃，應(yīng)否改變生產(chǎn)計(jì)劃? 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影子價(jià)格有意義時(shí)約束右端的允許變化范圍影子價(jià)格有意義時(shí)約束右端的允許變化范圍 原料最多增加原

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

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

18、(103t)總供水量：總供水量：160確定送水方案確定送水方案使利潤(rùn)最大使利潤(rùn)最大問(wèn)題問(wèn)題分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：?。?0；40 總需求量總需求量(300)每個(gè)水庫(kù)最大供水量都提高一倍每個(gè)水庫(kù)最大供水量都提高一倍利潤(rùn)利潤(rùn) = 收入收入(900) 其他費(fèi)用其他費(fèi)用( (450) 引水管理費(fèi)引水管理費(fèi)利潤(rùn)利潤(rùn)(元元/ 103t )甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/問(wèn)題二問(wèn)題二 確定送水方案確定送水方案使利潤(rùn)最大使利潤(rùn)最大供應(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 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題總利潤(rùn)總利潤(rùn) 88700（元）（元） A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)40100

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

22、；5300飛機(jī)平衡飛機(jī)平衡模型假設(shè)模型假設(shè) 1. 1. 每種貨物可以分割到任意??；每種貨物可以分割到任意??；2. 2. 每種貨物可以在一個(gè)或多個(gè)貨艙中任每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；意分布；3. 3. 多種貨物可以混裝，并保證不留空隙；多種貨物可以混裝，并保證不留空隙； 4.4.所給出的數(shù)據(jù)都是精確的，沒有誤差所給出的數(shù)據(jù)都是精確的，沒有誤差。 決策決策變量變量 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量(t(t）i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉(cāng)分別代表前、中、后倉(cāng))模型建立模型建立 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 (分別代表前、中、后倉(cāng)分別代表前、中、后倉(cāng))貨艙貨艙j的重量限制的重量限制WETj ，體積限制體積限制VOLj第第i種貨物的重量種貨物的重量wi，體積，體積vi，利潤(rùn)，利潤(rùn)