姜啟源_謝金星編《數(shù)學(xué)模型》第四版_第四章__數(shù)學(xué)規(guī)劃模型

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)4.3 汽車生產(chǎn)與原油采購(gòu)汽車生產(chǎn)與原油采購(gòu)4.4 接力隊(duì)選拔和選課策略接力隊(duì)選拔和選課策略4.5 飲料廠的生產(chǎn)與檢修飲料廠的生產(chǎn)與檢修4.6 鋼管和易拉罐下料鋼管和易拉罐下料數(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和和

2、約束條件個(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)在模型的建立和結(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ì)劃用

3、參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)劃.時(shí)間層次時(shí)間層次若短時(shí)間內(nèi)外部需求和內(nèi)部資源等不隨時(shí)間變化，可若短時(shí)間內(nèi)外部需求和內(nèi)部資源等不隨時(shí)間變化，可制訂制訂單階段生產(chǎn)計(jì)劃單階段生產(chǎn)計(jì)劃，否則應(yīng)制訂多階段生產(chǎn)計(jì)劃，否則應(yīng)制訂多階段生產(chǎn)計(jì)劃.本節(jié)課題本節(jié)課題例例1 加工奶制品的生產(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桶牛奶，買嗎？若買，每天最多買多少桶牛奶，

4、買嗎？若買，每天最多買多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到的獲利增加到 30元元/kg，應(yīng)否改變生產(chǎn)計(jì)劃？，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：每天：?jiǎn)枂?wèn)題題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每

5、天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時(shí)間時(shí)間480h 至多加工至多加工100kgA1 50桶牛奶桶牛奶 每天每天基本基本模型模型模型分析與假設(shè)模型分析與假設(shè) 比比例例性性 可可加加性性 連續(xù)性連續(xù)性 xi對(duì)目標(biāo)函數(shù)的對(duì)目標(biāo)函數(shù)的“貢貢獻(xiàn)獻(xiàn)”與與xi取值成正比取值成正比 xi對(duì)約束條件的對(duì)約束條件的“貢貢獻(xiàn)獻(xiàn)”與與xi取值成正比取值成正比 xi對(duì)目標(biāo)函數(shù)的對(duì)目標(biāo)函數(shù)的“貢貢獻(xiàn)獻(xiàn)”與與xj取值無(wú)關(guān)取值無(wú)關(guān) xi對(duì)約束條件的對(duì)約束條件的“貢貢獻(xiàn)獻(xiàn)”與與xj取值無(wú)關(guān)取值無(wú)關(guān) xi取值連續(xù)取值連續(xù) A1,A2每千克的獲利是與各自每千克的獲利是與各自

6、產(chǎn)量無(wú)關(guān)的常數(shù)產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工每桶牛奶加工A1,A2的數(shù)量的數(shù)量, 時(shí)時(shí)間是與各自產(chǎn)量無(wú)關(guān)的常數(shù)間是與各自產(chǎn)量無(wú)關(guān)的常數(shù)A1,A2每千克的獲利是與相互每千克的獲利是與相互產(chǎn)量無(wú)關(guān)的常數(shù)產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工每桶牛奶加工A1,A2的數(shù)量的數(shù)量,時(shí)時(shí)間是與相互產(chǎn)量無(wú)關(guān)的常數(shù)間是與相互產(chǎn)量無(wú)關(guān)的常數(shù)加工加工A1,A2的牛奶桶數(shù)是實(shí)數(shù)的牛奶桶數(shù)是實(shí)數(shù) 線性規(guī)劃模型線性規(guī)劃模型模型求解模型求解 圖解法圖解法 x1x2OABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx約約束束條條件件50:211 xxl480812:212 xxl1003:13xl0:

7、, 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)取得形的某個(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*x11

8、00;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 3360.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

9、桶生產(chǎn)桶生產(chǎn)A2，利潤(rùn)，利潤(rùn)3360元元. 結(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.0

10、00000 model:max = 72*x1+64*x2;milk x1 + x250;time 12*x1+8*x2480;cpct 3*x1100;end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 原料無(wú)剩余原料無(wú)剩余時(shí)間無(wú)剩余時(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.0

11、00000 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最優(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)

12、增長(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 AllowableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable

13、 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ù)允許變化范圍數(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)允許范

14、圍內(nèi) 不變！不變！(約束條件不變約束條件不變)結(jié)果解釋結(jié)果解釋 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable AllowableVariable 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 Decrea

15、se MILK 50.00000 10.00000 6.666667 TIME 480.0000 53.33333 80.00000 CPCT 100.0000 INFINITY 40.00000影子價(jià)格有意義時(shí)約束右端的允許變化范圍影子價(jià)格有意義時(shí)約束右端的允許變化范圍 原料最多增加原料最多增加10 時(shí)間最多增加時(shí)間最多增加53 35元可買到元可買到1桶牛奶桶牛奶, 每天最多買多少每天最多買多少?最多買最多買10桶桶!(目標(biāo)函數(shù)不變目標(biāo)函數(shù)不變)充分條件充分條件 !例例2 奶制品的生產(chǎn)銷售計(jì)劃奶制品的生產(chǎn)銷售計(jì)劃 在例在例1基礎(chǔ)上深加工基礎(chǔ)上深加工1桶桶牛奶牛奶 3kgA1 12h 8h 4

16、kgA2 或或獲利獲利24元元/kg 獲利獲利16元元/kg 0.8kgB1 2h, 3元元1kg獲利獲利44元元/kg 0.75kgB2 2h, 3元元1kg獲利獲利32元元/kg 制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1h時(shí)間，應(yīng)否投資？現(xiàn)投資時(shí)間，應(yīng)否投資？現(xiàn)投資150元，可賺回多少？元，可賺回多少？50桶牛奶桶牛奶, 480h 至多至多100kgA1 B1，B2的獲利經(jīng)常有的獲利經(jīng)常有10%的波動(dòng)，對(duì)計(jì)劃有無(wú)影響？的波動(dòng)，對(duì)計(jì)劃有無(wú)影響？ 每天銷售每天銷售10kgA1的合同必須滿足，對(duì)利潤(rùn)有什么影響？的合同

17、必須滿足，對(duì)利潤(rùn)有什么影響？1桶桶牛奶牛奶 3kg A1 12h 8h 4kg A2 或或獲利獲利24元元/kg 獲利獲利16元元/kg 0.8kg B12h, 3元元1kg獲利獲利44元元/kg 0.75kg B22h, 3元元1kg獲利獲利32元元/kg 出售出售x1 kg A1, x2 kg A2， x3 kg B1, x4 kg B2原料原料供應(yīng)供應(yīng) 勞動(dòng)勞動(dòng)時(shí)間時(shí)間 加工能力加工能力 決策決策變量變量 目標(biāo)目標(biāo)函數(shù)函數(shù) 利潤(rùn)利潤(rùn)約束約束條件條件非負(fù)約束非負(fù)約束 0,61xx x5 kg A1加工加工B1， x6 kg A2加工加工B26543213332441624maxxxxxxx

18、z50436251xxxx48022)(2)(4656251xxxxxx10051 xx附加約束附加約束 5380 x.x64750 x.x 基本模型基本模型模型求解模型求解 軟件實(shí)現(xiàn)軟件實(shí)現(xiàn) LINGO5043) 26251xxxx48022)(2)(4)3656251xxxxxx Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3

19、19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000600334) 26521xxxx44804624) 36521xxxxGlobal optimal solution

20、 found. Objective value: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000

21、000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000結(jié)果解釋結(jié)果解釋每天銷售每天銷售168 kgA2和和19.2 kgB1， 利潤(rùn)利潤(rùn)3460.8（元）（元）8桶牛奶加工成桶牛奶加工成A1，42桶牛奶加工成桶牛奶加工成A2，將得到的將得到的24kgA1全全部加工成部加工成B1 除加工能力外除加工能力外均為緊約束均為緊約束結(jié)果解釋結(jié)果解釋Global optimal solution found. Objective value: 3460.800 Total solver iterations:

22、2 Variable Value Reduced Cost X1 0.000000 1.680000 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0

23、.000000 32.00000增加增加1桶牛奶使利潤(rùn)桶牛奶使利潤(rùn)增長(zhǎng)增長(zhǎng)3.1612=37.925043)26251xxxx600334) 26521xxxx4增加增加1h時(shí)間使利時(shí)間使利潤(rùn)增長(zhǎng)潤(rùn)增長(zhǎng)3.26 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1h時(shí)間，應(yīng)時(shí)間，應(yīng)否投資？現(xiàn)投資否投資？現(xiàn)投資150元，可賺回多少？元，可賺回多少？投資投資150元增加元增加5桶牛奶桶牛奶,可賺回可賺回189.6元元(大于增大于增加時(shí)間的利潤(rùn)增長(zhǎng)加時(shí)間的利潤(rùn)增長(zhǎng)).結(jié)果解釋結(jié)果解釋B1,B2的獲利有的獲利有10%的波動(dòng)，對(duì)計(jì)劃有無(wú)影響的波動(dòng)，對(duì)計(jì)劃有無(wú)影響 Ranges in which t

24、he basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 24.000000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 IN

25、FINITY 敏感性分析敏感性分析 B1獲利下降獲利下降10%，超，超出出X3 系數(shù)允許范圍系數(shù)允許范圍B2獲利上升獲利上升10%，超，超出出X4 系數(shù)允許范圍系數(shù)允許范圍波動(dòng)對(duì)計(jì)劃有影響波動(dòng)對(duì)計(jì)劃有影響生產(chǎn)計(jì)劃應(yīng)重新制訂：如將生產(chǎn)計(jì)劃應(yīng)重新制訂：如將x3的系數(shù)改為的系數(shù)改為39.6計(jì)算，計(jì)算，會(huì)發(fā)現(xiàn)結(jié)果有很大變化會(huì)發(fā)現(xiàn)結(jié)果有很大變化. Global optimal solution found. Objective value: 3460.800 Total solver iterations: 2 Variable Value Reduced Cost X1 0.000000 1.6800

26、00 X2 168.0000 0.000000 X3 19.20000 0.000000 X4 0.000000 0.000000 X5 24.00000 0.000000 X6 0.000000 1.520000 Row Slack or Surplus Dual Price 1 3460.800 1.000000 MILK 0.000000 3.160000 TIME 0.000000 3.260000 CPCT 76.00000 0.000000 5 0.000000 44.00000 6 0.000000 32.00000結(jié)果解釋結(jié)果解釋x1從從0開始增加一個(gè)開始增加一個(gè)單位時(shí)，最優(yōu)目

27、標(biāo)函單位時(shí)，最優(yōu)目標(biāo)函數(shù)值將減少數(shù)值將減少1.68Reduced Cost有意義有意義也是有條件的也是有條件的(LINGO沒(méi)有給出沒(méi)有給出)每天銷售每天銷售10kgA1的合同必須滿足，對(duì)的合同必須滿足，對(duì)利潤(rùn)有什么影響？利潤(rùn)有什么影響？公司利潤(rùn)減少公司利潤(rùn)減少1.6810=16.8（元）（元）最優(yōu)利潤(rùn)為最優(yōu)利潤(rùn)為 3460.8 16.8 = 3444 奶制品的生產(chǎn)與銷售奶制品的生產(chǎn)與銷售 由于產(chǎn)品利潤(rùn)、加工時(shí)間等均為常數(shù)，可由于產(chǎn)品利潤(rùn)、加工時(shí)間等均為常數(shù)，可建立建立線性規(guī)劃線性規(guī)劃模型模型. 線性規(guī)劃模型的三要素：線性規(guī)劃模型的三要素：決策變量、目標(biāo)決策變量、目標(biāo)函數(shù)、約束條件函數(shù)、約束條件

28、. 用用LINGO求解，輸出豐富，利用求解，輸出豐富，利用影子價(jià)格影子價(jià)格和和靈敏性分析靈敏性分析可對(duì)結(jié)果做進(jìn)一步研究可對(duì)結(jié)果做進(jìn)一步研究. 建模時(shí)盡可能利用原始的數(shù)據(jù)信息，把盡量建模時(shí)盡可能利用原始的數(shù)據(jù)信息，把盡量多的計(jì)算留給計(jì)算機(jī)去做（分析例多的計(jì)算留給計(jì)算機(jī)去做（分析例2的建模）的建模）.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)題各種類型的貨物裝箱，由于受體積、重量等限制，各種類型的貨物裝箱，由于受體

29、積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少如何搭配裝載，使獲利最高，或裝箱數(shù)量最少?其他費(fèi)用其他費(fèi)用: :450元元/ 103t 應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？ 若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？ 元元/ 103t甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理費(fèi)引水管理費(fèi)例例1 自來(lái)水輸送自來(lái)水輸送收入：收入：900元元/103t 支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20?。憾?/p>

30、：10；40水庫(kù)供水量水庫(kù)供水量小區(qū)基本用水小區(qū)基本用水量量小區(qū)額外用水量小區(qū)額外用水量（以天計(jì)）（以天計(jì)）(103t)(103t)(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 )甲甲乙乙丙丙丁丁A290320230280B310320260300C26

31、0250220/3332312423222114131211220250260300260320310280230320290maxxxxxxxxxxxxZ供應(yīng)供應(yīng)限制限制B, C 類似處理類似處理50:A14131211xxxx10014131211xxxx問(wèn)題討論問(wèn)題討論 確定送水方案確定送水方案使利潤(rùn)最大使利潤(rùn)最大需求約束可以不變需求約束可以不變求解求解部分結(jié)果：部分結(jié)果：Objective Value: 88700.00 Variable Value Reduced Cost X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.00

32、0000 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)4010050305030供應(yīng)點(diǎn)供應(yīng)點(diǎn)需

33、求點(diǎn)需求點(diǎn)物資物資供需平衡或不平衡供需平衡或不平衡如何如何裝運(yùn)，裝運(yùn)，使本次飛行使本次飛行獲利最大？獲利最大？ 三個(gè)貨艙三個(gè)貨艙最大最大載載重重(t),(t),最大容積最大容積(m(m3 3) ) 例例2 貨機(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；5300飛機(jī)平衡飛機(jī)平衡WET=(10,16,8)

34、, 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)pi貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)決策決策變量變量 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量(t(t）i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉(cāng)分別代表前、中

35、、后倉(cāng))模型假設(shè)模型假設(shè) 每種貨物可以分割到任意小；每種貨物可以分割到任意??；貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；多種貨物可以混裝，并保證不留空隙； 所給出的數(shù)據(jù)都是精確的，沒(méi)有誤差所給出的數(shù)據(jù)都是精確的，沒(méi)有誤差. . 模型建立模型建立 貨艙貨艙容積容積 目標(biāo)目標(biāo)函數(shù)函數(shù)( (利潤(rùn)利潤(rùn))約束約束條件條件貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型建立模型建立 貨艙貨艙重量重量 10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量 max4131ijijixpZjii

36、jWETx 41jiijiVOLxv41約束約束條件條件平衡平衡要求要求 貨物貨物供應(yīng)供應(yīng) 貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型建立模型建立 10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量ijijwx 31kiikjiijWETxWETx/4141j,k=1,2,3; jk !定義集合及變量定義集合及變量;sets: cang/1.3/:WET,VOL; wu/1.4/:w,v,p; link(wu,cang):x;endsets!對(duì)已知變量賦值對(duì)已知變量賦值;data: WET=10,16,8; VOL=6800,8700,5300; w=18

37、,15,23,12; v=480,650, 580,390; p=3100,3800,3500,2850;enddatamax=sum(wu(i):p(i)*sum(cang(j):x(i,j);for(wu(i):sum(cang(j):x(i,j)w(i);for(cang(j):sum(wu(i):x(i,j)WET(j);for(cang(j):sum(wu(i):v(i)*x(i,j)VOL(j);for(cang(j):for(cang(k)|k #GT# j:!#GT#是大于等于的含義是大于等于的含義;sum(wu(i):x(i,j)/WET(j)=sum(wu(i):x(i,k

38、)/WET(k););END貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)LINGO程序程序 Global optimal solution found. Objective value: 121515.8 Total solver iterations: 12Variable Value Reduced Cost X( 1, 1) 0.000000 400.0000 X( 1, 2) 0.000000 57.89474 X( 1, 3) 0.000000 400.0000 X( 2, 1) 7.000000 0.000000 X( 2, 2) 0.000000 239.4737 X( 2, 3) 8.000000 0.0

39、00000 X( 3, 1) 3.000000 0.000000 X( 3, 2) 12.94737 0.000000 X( 3, 3) 0.000000 0.000000 X( 4, 1) 0.000000 650.0000 X( 4, 2) 3.052632 0.000000 X( 4, 3) 0.000000 650.0000貨物貨物2：前倉(cāng)：前倉(cāng)7, ,后倉(cāng)后倉(cāng)8； 貨物貨物3: : 前倉(cāng)前倉(cāng)3, 中倉(cāng)中倉(cāng)1 13；貨物貨物4: : 中倉(cāng)中倉(cāng)3. .貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型求解模型求解 最大利潤(rùn)約最大利潤(rùn)約121516元元貨物貨物供應(yīng)點(diǎn)供應(yīng)點(diǎn)貨艙貨艙需求點(diǎn)需求點(diǎn)裝載平衡要求裝載平衡要求運(yùn)輸

40、運(yùn)輸問(wèn)題問(wèn)題運(yùn)輸問(wèn)題的擴(kuò)展運(yùn)輸問(wèn)題的擴(kuò)展 如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)8080輛，輛， 那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？例例1 汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)計(jì)劃 汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對(duì)汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對(duì)鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠每月的現(xiàn)有量鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠每月的現(xiàn)有量. 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材（鋼材（t） 1.5 3 5 600勞動(dòng)時(shí)間（勞動(dòng)時(shí)間（h） 280 250 400 60000利潤(rùn)（萬(wàn)元）利潤(rùn)（萬(wàn)元） 2 3 4 制訂月生產(chǎn)計(jì)劃

41、，使工廠的利潤(rùn)最大制訂月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大.4.3 汽車生產(chǎn)與原油采購(gòu)汽車生產(chǎn)與原油采購(gòu)設(shè)每月生產(chǎn)小、中、大型設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為汽車的數(shù)量分別為x1, x2, x3321432maxxxxz600535 . 1t.s.321xxx60000400250280321xxx0,321xxx汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)計(jì)劃 模型建立模型建立 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材鋼材 1.5 3 5 600時(shí)間時(shí)間 280 250 400 60000利潤(rùn)利潤(rùn) 2 3 4 線性規(guī)劃線性規(guī)劃模型模型(LP)模型模型求解求解 3）模型中）模型中增加條件增加條件：x1, x2

42、, x3 均為整數(shù)，重新求解均為整數(shù)，重新求解. . Objective Value: 632.2581 Variable Value Reduced Cost X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 Row Slack or Surplus Dual Price 2 0.000000 0.731183 3 0.000000 0.003226結(jié)果為小數(shù)，結(jié)果為小數(shù)，怎么辦？怎么辦？1）舍去小數(shù)舍去小數(shù)：?。喝1=64，x2=167，算出目標(biāo)函數(shù)值，算出目標(biāo)函數(shù)值 z=629，與，與LP最優(yōu)值最優(yōu)值63

43、2.2581相差不大相差不大.2）試探試探：如?。喝缛1=65，x2=167；x1=64，x2=168等，等，計(jì)算函數(shù)值計(jì)算函數(shù)值z(mì)，通過(guò)比較可能得到更優(yōu)的解，通過(guò)比較可能得到更優(yōu)的解. 但但必須檢驗(yàn)必須檢驗(yàn)它們是否滿足約束條件它們是否滿足約束條件. 為什么？為什么？IP可用可用LINGO直接求解直接求解整數(shù)規(guī)劃整數(shù)規(guī)劃( (Integer Programming, ,簡(jiǎn)記簡(jiǎn)記IP) )IP 的最優(yōu)解的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值最優(yōu)值z(mì)=632 max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x36000

44、0;gin(x1);gin(x2);gin(x3); Global optimal solution found. Objective value: 632.0000 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost X1 64.00000 -2.000000 X2 168.0000 -3.000000 X3 0.000000 -4.000000321432maxxxxz600535 . 1t.s.321xxx60000400250280321xxx為非負(fù)整數(shù)321,xxx模型求解模型

45、求解 IP 結(jié)果輸出結(jié)果輸出其中其中3個(gè)個(gè)子模型應(yīng)子模型應(yīng)去掉，然后去掉，然后逐一求解，比較目標(biāo)函數(shù)值，逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：再加上整數(shù)約束，得最優(yōu)解：80, 0, 0321xxx0,80, 0321xxx80,80, 0321xxx0, 0,80321xxx0,80,80321xxx80, 0,80321xxx80,80,80321xxx0,321xxx方法方法1：分解為：分解為8個(gè)個(gè)LP子模型子模型 汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)計(jì)劃 若生產(chǎn)某類汽車，則至少生產(chǎn)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃輛，求生產(chǎn)計(jì)劃. .321432maxxxxz600535

46、 . 1t.s.321xxx60000400250280321xxxx1, ,x2, x3=0 或或 80 x1=80，x2= 150，x3=0，最優(yōu)值，最優(yōu)值z(mì)=610LINGO中對(duì)中對(duì)0-1變量的限定：變量的限定： b i n ( y 1 ) ; b i n ( y 2 ) ; bin(y3);方法方法2：引入引入0-1變量，化為整數(shù)規(guī)劃變量，化為整數(shù)規(guī)劃 M為大的正數(shù)為大的正數(shù), ,本例可取本例可取1000 Objective Value: 610.0000 Variable Value Reduced Cost X1 80.000000 -2.000000 X2 150.000000

47、-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)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃輛，求生產(chǎn)計(jì)劃. .x1=0 或 80 x2=0 或 80 x3=0 或 801 , 0,80,11111yyxMyx1 , 0,80,22222yyxMyx1 , 0,80,33333yyxMyx最優(yōu)解同前最優(yōu)解同前 max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x

48、30;x2*(x2-80)0;x3*(x3-80)0;gin(x1);gin(x2);gin(x3);方法方法3：化為非線性規(guī)劃化為非線性規(guī)劃 非線性規(guī)劃非線性規(guī)劃（Non- Linear Programming，簡(jiǎn)記簡(jiǎn)記NLP） 若生產(chǎn)某類汽車，則至少生產(chǎn)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃輛，求生產(chǎn)計(jì)劃. . x1=0 或 80 x2=0 或 80 x3=0 或 800)80(11xx0)80(22xx0)80(33xx最優(yōu)解同前最優(yōu)解同前.一般地，整數(shù)規(guī)劃和非一般地，整數(shù)規(guī)劃和非線性規(guī)劃的求解比線性線性規(guī)劃的求解比線性規(guī)劃困難得多，特別是規(guī)劃困難得多，特別是問(wèn)題規(guī)模較大或者要

49、求問(wèn)題規(guī)模較大或者要求得到全局最優(yōu)解時(shí)得到全局最優(yōu)解時(shí). 汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)計(jì)劃 決策變量為整數(shù)決策變量為整數(shù), 建立建立整數(shù)規(guī)劃模型整數(shù)規(guī)劃模型. 求解整數(shù)規(guī)劃和非線性規(guī)劃比線性規(guī)劃求解整數(shù)規(guī)劃和非線性規(guī)劃比線性規(guī)劃困難得多困難得多 (即便用數(shù)學(xué)軟件即便用數(shù)學(xué)軟件) . 當(dāng)整數(shù)變量取值很大時(shí)當(dāng)整數(shù)變量取值很大時(shí), 可作為連續(xù)變量可作為連續(xù)變量處理處理, 問(wèn)題問(wèn)題簡(jiǎn)化為線性規(guī)劃簡(jiǎn)化為線性規(guī)劃. 對(duì)于類似于對(duì)于類似于“x=0 或或 80”這樣的條件，通常這樣的條件，通常引入引入0-1變量變量處理，盡量不用非線性規(guī)劃（特處理，盡量不用非線性規(guī)劃（特別是引入的整數(shù)變量個(gè)數(shù)較少時(shí)）別是引入的整數(shù)

50、變量個(gè)數(shù)較少時(shí)）.應(yīng)如何安排原油的采購(gòu)和加工應(yīng)如何安排原油的采購(gòu)和加工 ？ 例例2 原油采購(gòu)與加工原油采購(gòu)與加工 市場(chǎng)上可買到不超過(guò)市場(chǎng)上可買到不超過(guò)1500t t的原油的原油A： 購(gòu)買量不超過(guò)購(gòu)買量不超過(guò)500t t時(shí)的單價(jià)為時(shí)的單價(jià)為10000元元/t/t； 購(gòu)買量超過(guò)購(gòu)買量超過(guò)500t t但不超過(guò)但不超過(guò)1000t t時(shí)，超過(guò)時(shí)，超過(guò)500t t的的 部分部分8000元元/t/t； 購(gòu)買量超過(guò)購(gòu)買量超過(guò)1000t t時(shí)，超過(guò)時(shí)，超過(guò)1000t t的部分的部分6000元元/t. /t. 售價(jià)售價(jià)4800元元/t 售價(jià)售價(jià)5600元元/t庫(kù)存庫(kù)存500t 庫(kù)存庫(kù)存1000t 汽油甲汽油甲(A

51、 50%) 原油原油A 原油原油B 汽油乙汽油乙 (A 60%) 決策決策變量變量 目標(biāo)目標(biāo)函數(shù)函數(shù)問(wèn)題問(wèn)題分析分析 利潤(rùn)：銷售汽油的收入利潤(rùn)：銷售汽油的收入 購(gòu)買原油購(gòu)買原油A的支出的支出. . 難點(diǎn)：原油難點(diǎn)：原油A的購(gòu)價(jià)與購(gòu)買量的關(guān)系較復(fù)雜的購(gòu)價(jià)與購(gòu)買量的關(guān)系較復(fù)雜. .)()(6 . 5)( 8 . 4max22122111xcxxxxz甲甲(A 50%) A B 乙乙(A 60%) 購(gòu)買購(gòu)買xx11x12x21x224.8千元千元/t 5.6千元千元/t原油原油A的購(gòu)買量的購(gòu)買量, ,原油原油A, B生產(chǎn)生產(chǎn)汽油汽油甲甲,乙的數(shù)量乙的數(shù)量c(x) 購(gòu)買原油購(gòu)買原油A的支出的支出利潤(rùn)利

52、潤(rùn)(千元千元)c(x)如何表述？如何表述？原油供應(yīng)原油供應(yīng) 約束約束條件條件xxx500121110002221 xx1500 x500)1(1000 300061000)(500 1000 8500)(0 10)(xxxxxxxc x 500t t單價(jià)為單價(jià)為10千千元元/t/t； 500t t x 1000t t，超過(guò)，超過(guò)500t t的的8千千元元/t/t；1000t t x 1500t t，超過(guò)，超過(guò)1000t t的的6千千元元/t. /t. 目標(biāo)目標(biāo)函數(shù)函數(shù)購(gòu)買購(gòu)買x A B x11x12x21x22庫(kù)存庫(kù)存500t 庫(kù)存庫(kù)存1000t 目標(biāo)函數(shù)中目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非

53、線性規(guī)劃；不是線性函數(shù)，是非線性規(guī)劃； 對(duì)于用分段函數(shù)定義的對(duì)于用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟，一般的非線性規(guī)劃軟件也難以輸入和求解；件也難以輸入和求解； 想辦法將模型化簡(jiǎn)，用現(xiàn)成的軟件求解想辦法將模型化簡(jiǎn)，用現(xiàn)成的軟件求解. . 汽油含原油汽油含原油A的比例限制的比例限制 5 . 0211111 xxx6 . 0221212 xxx2111xx 221232xx 約束約束條件條件甲甲(A 50%) A B 乙乙(A 60%) x11x12x21x22x1 , x2 , x3 以價(jià)格以價(jià)格10, 8, 6(千元千元/ /t)t)采購(gòu)采購(gòu)A的噸數(shù)的噸數(shù)目標(biāo)目標(biāo)函數(shù)函數(shù) 只有當(dāng)以只有

54、當(dāng)以10千元千元/t t的價(jià)格購(gòu)買的價(jià)格購(gòu)買x1=500(t)(t)時(shí)，才能以時(shí)，才能以8千千元元/t t的價(jià)格購(gòu)買的價(jià)格購(gòu)買x2方法方法1 )6810()( 6 . 5)( 8 . 4max32122122111xxxxxxxz500,0321xxx非線性規(guī)劃模型非線性規(guī)劃模型，可以用，可以用LINGO求解求解模型求解模型求解x= x1+x2+x3, c(x) = 10 x1+8x2+6x3 500t t x 1000t t，超過(guò)，超過(guò)500t t的的8千千元元/t/t增加約束增加約束0)500(21xxx= x1+x2+x3, c(x) = 10 x1+8x2+6x3 0)500(32xx

55、類似地有類似地有方法方法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 y=1與方法與方法1（全局最優(yōu)解）的結(jié)果相同（全局最優(yōu)解）的結(jié)果相同引入引入0-1變量變量模型求解模型求解b1 b2 b3 b4方法方法3 b1 x b2，x= z1b1+z2b2，z1+

56、z2=1，z1, z2 0, c(x)= z1c(b1)+z2c(b2).c(x)x1200090005000O50010001500b2 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 直接處理處理分段線性函數(shù)直接處理處理分段線性函數(shù)c(x) IP模型，模型，LINGO求解，得到的結(jié)求解，得到的結(jié)

57、果與方法果與方法2相同相同. .44332211bzbzbzbzx)()()()()(44332211bczbczbczbczxcbk x bk+1yk=1, ,否則否則, ,yk=03432321211,yzyyzyyzyz)4 , 3 , 2 , 1(0, 14321kzzzzzk10, 1321321或yyyyyy方法方法3 bk x bk+1 , ,x= zkbk+z k+1 bk+1zk+zk+1 =1，zk, zk+1 0, c(x)= zkc(bk)+zk+1 c(bk+1 ).c(x)x1200090005000O50010001500b1 b2 b3 b4對(duì)于對(duì)于k=1,2,

58、3 方法方法3: 直接處理分段線性函數(shù)，方法更具一般性直接處理分段線性函數(shù)，方法更具一般性. 分段函數(shù)分段函數(shù)無(wú)法直接用非線性規(guī)劃方法或軟件求無(wú)法直接用非線性規(guī)劃方法或軟件求解解. .原油采購(gòu)與加工原油采購(gòu)與加工 方法方法1: 增加約束化為增加約束化為非線性規(guī)劃非線性規(guī)劃, ,可以用可以用LINGO 求解求解, 但可能但可能得到的是局部最優(yōu)解得到的是局部最優(yōu)解. . 方法方法2: 引入引入0-1變量變量, 化為化為線性規(guī)劃模型線性規(guī)劃模型, 可用可用LINGO求解求解.分派問(wèn)題分派問(wèn)題4.4 接力隊(duì)選拔和選課策略接力隊(duì)選拔和選課策略 若干項(xiàng)任務(wù)分給一些候選人來(lái)完成，每人的專長(zhǎng)不同若干項(xiàng)任務(wù)分給

59、一些候選人來(lái)完成，每人的專長(zhǎng)不同,完成每項(xiàng)任務(wù)取得的效益或需要的資源不同，如何分派完成每項(xiàng)任務(wù)取得的效益或需要的資源不同，如何分派任務(wù)使獲得的總效益最大，或付出的總資源最少任務(wù)使獲得的總效益最大，或付出的總資源最少? 若干種策略供選擇，不同的策略得到的收益或付出若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個(gè)策略之間有相互制約關(guān)系，如何在的成本不同，各個(gè)策略之間有相互制約關(guān)系，如何在滿足一定條件下作出抉擇，使得收益最大或成本最小滿足一定條件下作出抉擇，使得收益最大或成本最小?如何選拔隊(duì)員組成如何選拔隊(duì)員組成4 4 100100m混合泳接力隊(duì)混合泳接力隊(duì)? ?例例1 混合泳接力隊(duì)的選

60、拔混合泳接力隊(duì)的選拔 5名候選人的名候選人的百米成績(jī)百米成績(jī)窮舉法窮舉法：組成接力隊(duì)的方案共有組成接力隊(duì)的方案共有5!=120種種.甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳仰泳仰泳蛙泳蛙泳自由泳自由泳8601 6511 721 685 275 35 495 275 601 4601 811 8701 6421 011 2411 6901 4701 111 8321 4201 討論討論: :丁的蛙泳成績(jī)退步到丁的蛙泳成績(jī)退步到 ；戊的自由泳成；戊的自由泳成績(jī)進(jìn)步到績(jī)進(jìn)步到 , 組成接力隊(duì)的方案是否應(yīng)該調(diào)整組成接力隊(duì)的方案是否應(yīng)該調(diào)整？2511 575 目標(biāo)目標(biāo)函數(shù)函數(shù)若選擇隊(duì)員若選擇隊(duì)員i參加泳姿參加泳姿j