第三講 數(shù)學(xué)規(guī)劃模型

第三講數(shù)學(xué)規(guī)劃模型

3.1奶制品的生產(chǎn)計(jì)劃3.2一般優(yōu)化模型簡介3.3接力隊(duì)選拔和選課策略3.4鋼管的截?cái)嗲懈顔栴}3.5投資的風(fēng)險(xiǎn)與收益問題3.6進(jìn)一步的學(xué)習(xí)y3.1奶制品的生產(chǎn)計(jì)劃第三講數(shù)學(xué)規(guī)劃模型

1桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時(shí)間480小時(shí)至多加工100公斤A1

制訂生產(chǎn)計(jì)劃，使每天獲利最大每天：35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？問題3.1奶制品的生產(chǎn)計(jì)劃第三講數(shù)學(xué)規(guī)劃模型

x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動(dòng)時(shí)間

加工能力

決策變量

目標(biāo)函數(shù)

每天獲利約束條件非負(fù)約束

線性規(guī)劃模型(LP)模型的建立與求解（LINGO軟件）第三講數(shù)學(xué)規(guī)劃模型

一、優(yōu)化模型的三要素：決策變量（decisionvariable）目標(biāo)函數(shù)（objectivefunction）約束條件（constraints）→feasibleregion:3.2一般優(yōu)化模型（數(shù)學(xué)規(guī)劃）簡介第三講數(shù)學(xué)規(guī)劃模型

二、優(yōu)化模型的一般形式generalmodel3.2一般優(yōu)化模型（數(shù)學(xué)規(guī)劃）簡介三、局部最優(yōu)解與全局最優(yōu)解第三講數(shù)學(xué)規(guī)劃模型

3.2一般優(yōu)化模型（數(shù)學(xué)規(guī)劃）簡介四、優(yōu)化模型的基本類型（2）離散優(yōu)化/組合優(yōu)化（discreteopt/combinatorialopt）（2）無約束優(yōu)化（unconstrainedopt）1、按照有無約束（1）約束優(yōu)化（constrainedoptimization）2、按照決策變量x的分量取值（1）連續(xù)優(yōu)化/數(shù)學(xué)規(guī)劃（continuousopt/mathematicalprogramming）第三講數(shù)學(xué)規(guī)劃模型

3.2一般優(yōu)化模型（數(shù)學(xué)規(guī)劃）簡介3、按照目標(biāo)函數(shù)的個(gè)數(shù)單目標(biāo)規(guī)劃與多目標(biāo)規(guī)劃4、按照參數(shù)或者決策變量是否具有不確定性確定性規(guī)劃與不確定性規(guī)劃（如隨機(jī)規(guī)劃、模糊規(guī)劃等）5、按照目標(biāo)函數(shù)f，約束條件g、h是否連續(xù)可微光滑優(yōu)化與非光滑優(yōu)化第三講數(shù)學(xué)規(guī)劃模型

四、優(yōu)化模型的基本類型3.2一般優(yōu)化模型（數(shù)學(xué)規(guī)劃）簡介五、常見的優(yōu)化問題類型第三講數(shù)學(xué)規(guī)劃模型

3.2一般優(yōu)化模型（數(shù)學(xué)規(guī)劃）簡介五、常見的優(yōu)化問題類型第三講數(shù)學(xué)規(guī)劃模型

3.2一般優(yōu)化模型（數(shù)學(xué)規(guī)劃）簡介六、優(yōu)化模型的求解難度優(yōu)化連續(xù)優(yōu)化整數(shù)規(guī)劃LPQPNLP問題求解的難度增加第三講數(shù)學(xué)規(guī)劃模型

3.2一般優(yōu)化模型（數(shù)學(xué)規(guī)劃）簡介建立優(yōu)化模型時(shí)需要注意的幾個(gè)基本問題

1、盡量使用實(shí)數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個(gè)數(shù)如：盡量少使用絕對(duì)值、符號(hào)函數(shù)、多個(gè)變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個(gè)數(shù)（如x/y<5改為x<5y）4、合理設(shè)定變量上下界，盡可能給出變量初始值5、模型中使用的參數(shù)數(shù)量級(jí)要適當(dāng)(如小于103)第三講數(shù)學(xué)規(guī)劃模型

3.3.1指派問題3.3接力隊(duì)選拔和選課策略若干項(xiàng)任務(wù)分給一些候選人來完成，每人的專長不同，完成每項(xiàng)任務(wù)取得的效益或需要的資源就不同，如何分派任務(wù)使獲得的總效益最大，或付出的總資源最少。若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個(gè)策略之間有相互制約關(guān)系，如何在滿足一定條件下作出決擇，使得收益最大或成本最小。第三講數(shù)學(xué)規(guī)劃模型

丁的蛙泳成績退步到1’15”2；戊的自由泳成績進(jìn)步到57”5,組成接力隊(duì)的方案是否應(yīng)該調(diào)整？如何選拔隊(duì)員組成4100米混合泳接力隊(duì)?3.3.2混合泳接力隊(duì)的選拔

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候選人的百米成績窮舉法：組成接力隊(duì)的方案共有5!=120種。目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則記xij=0

0-1規(guī)劃模型

cij(秒)~隊(duì)員i第j種泳姿的百米成績約束條件每人最多入選泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每種泳姿有且只有1人模型求解

最優(yōu)解：x14=x21=x32=x43=1,其它變量為0;成績?yōu)?53.2(秒)=4’13”2MIN66.8x11+75.6x12+87x13+58.6x14+……+67.4x51+71x52+83.8x53+62.4x54SUBJECTTOx11+x12+x13+x14<=1

……x41+x42+x43+x44<=1x11+x21+x31+x41+x51=1

……x14+x24+x34+x44+x54=1ENDINT20

輸入LINDO求解

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”4甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.丁蛙泳c43

=69.675.2，戊自由泳c54=62.4

57.5,方案是否調(diào)整？敏感性分析？乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP規(guī)劃一般沒有與LP規(guī)劃相類似的理論，LINDO輸出的敏感性分析結(jié)果通常是沒有意義的。最優(yōu)解：x21=x32=x43=x51=1,成績?yōu)?’17”7c43,c54的新數(shù)據(jù)重新輸入模型，用LINDO求解指派(Assignment)問題：每項(xiàng)任務(wù)有且只有一人承擔(dān)，每人只能承擔(dān)一項(xiàng)，效益不同，怎樣分派使總效益最大.討論甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.原方案為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程？

3.3.3選課策略要求至少選兩門數(shù)學(xué)課、三門運(yùn)籌學(xué)課和兩門計(jì)算機(jī)課課號(hào)課名學(xué)分所屬類別先修課要求1微積分5數(shù)學(xué)

2線性代數(shù)4數(shù)學(xué)

3最優(yōu)化方法4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計(jì)算機(jī)計(jì)算機(jī)編程5應(yīng)用統(tǒng)計(jì)4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線性代數(shù)6計(jì)算機(jī)模擬3計(jì)算機(jī)；運(yùn)籌學(xué)計(jì)算機(jī)編程7計(jì)算機(jī)編程2計(jì)算機(jī)

8預(yù)測理論2運(yùn)籌學(xué)應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)3運(yùn)籌學(xué)；計(jì)算機(jī)微積分；線性代數(shù)選修課程最少，且學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？

0-1規(guī)劃模型

決策變量

目標(biāo)函數(shù)

xi=1~選修課號(hào)i的課程（xi=0~不選）

選修課程總數(shù)最少約束條件最少2門數(shù)學(xué)課，3門運(yùn)籌學(xué)課，2門計(jì)算機(jī)課。

課號(hào)課名所屬類別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ì)算機(jī)5應(yīng)用統(tǒng)計(jì)數(shù)學(xué)；運(yùn)籌學(xué)6計(jì)算機(jī)模擬計(jì)算機(jī)；運(yùn)籌學(xué)7計(jì)算機(jī)編程計(jì)算機(jī)8預(yù)測理論運(yùn)籌學(xué)9數(shù)學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)；計(jì)算機(jī)先修課程要求最優(yōu)解：

x1=x2=x3=x6=x7=x9=1,其它為0；6門課程，總學(xué)分210-1規(guī)劃模型

約束條件x3=1必有x1=x2=1模型求解（LINDO）課號(hào)課名先修課要求1微積分

2線性代數(shù)

3最優(yōu)化方法微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)編程5應(yīng)用統(tǒng)計(jì)微積分；線性代數(shù)6計(jì)算機(jī)模擬計(jì)算機(jī)編程7計(jì)算機(jī)編程

8預(yù)測理論應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)微積分；線性代數(shù)多目標(biāo)規(guī)劃

在課程最少的前提下以學(xué)分最多為目標(biāo)。最優(yōu)解：

x1=x2=x3=x5=x7=x9=1,其它為0；總學(xué)分由21增至22。注意：最優(yōu)解不唯一！課號(hào)課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計(jì)46計(jì)算機(jī)模擬37計(jì)算機(jī)編程28預(yù)測理論29數(shù)學(xué)實(shí)驗(yàn)3LINDO無法告訴優(yōu)化問題的解是否唯一?？蓪9=1易為x6=1增加約束，以學(xué)分最多為目標(biāo)求解。多目標(biāo)規(guī)劃

對(duì)學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開。最優(yōu)解：

x1=x2=x3=x4=x5=x6=x7=x9=1，其它為0；總學(xué)分28。課號(hào)課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計(jì)46計(jì)算機(jī)模擬37計(jì)算機(jī)編程28預(yù)測理論29數(shù)學(xué)實(shí)驗(yàn)3討論與思考最優(yōu)解與1=0，2=1的結(jié)果相同——學(xué)分最多多目標(biāo)規(guī)劃

最優(yōu)解與1=1，2=0的結(jié)果相同——課程最少生產(chǎn)中通過切割、剪裁、沖壓等手段，將原材料加工成所需大小3.4鋼管和易拉罐下料原料下料問題按照工藝要求，確定下料方案，使所用材料最省，或利潤最大第三講數(shù)學(xué)規(guī)劃模型

問題1.如何下料最節(jié)省?3.4.1鋼管下料問題2.客戶增加需求：原料鋼管:每根19米4米50根6米20根8米15根客戶需求節(jié)省的標(biāo)準(zhǔn)是什么？由于采用不同切割模式太多，會(huì)增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過3種。如何下料最節(jié)?。?米10根按照客戶需要在一根原料鋼管上安排切割的一種組合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根鋼管下料為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。亢侠砬懈钅Ｊ?.所用原料鋼管總根數(shù)最少模式

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023鋼管下料問題1兩種標(biāo)準(zhǔn)1.原料鋼管剩余總余量最小xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7)約束滿足需求決策變量

目標(biāo)1（總余量）按模式2切割12根,按模式5切割15根，余料27米

模式4米根數(shù)6米根數(shù)8米根數(shù)余料14003231013201341203511116030170023需求502015最優(yōu)解：x2=12,x5=15,其余為0；最優(yōu)值：27。整數(shù)約束：xi為整數(shù)當(dāng)余料沒有用處時(shí)，通常以總根數(shù)最少為目標(biāo)目標(biāo)2（總根數(shù)）鋼管下料問題1約束條件不變最優(yōu)解：x2=15,x5=5,x7=5,其余為0；最優(yōu)值：25。xi為整數(shù)按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米雖余料增加8米，但減少了2根與目標(biāo)1的結(jié)果“共切割27根，余料27米”相比鋼管下料問題2對(duì)大規(guī)模問題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過3種?，F(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過于復(fù)雜。決策變量

xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,3)r1i,r2i,r3i,r4i~第i種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長的鋼管的數(shù)量滿足需求模式合理：每根余料不超過3米整數(shù)非線性規(guī)劃模型鋼管下料問題2目標(biāo)函數(shù)（總根數(shù)）約束條件整數(shù)約束：xi,r1i,r2i,r3i,r4i(i=1,2,3)為整數(shù)增加約束，縮小可行域，便于求解原料鋼管總根數(shù)下界：

特殊生產(chǎn)計(jì)劃：對(duì)每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數(shù)上界：13+10+8=31模式排列順序可任定

鋼管下料問題2需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長19米LINGO求解整數(shù)非線性規(guī)劃模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式1：每根原料鋼管切割成3根4米和1根6米鋼管，共10根；模式2：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根；模式3：每根原料鋼管切割成2根8米鋼管，共8根。原料鋼管總根數(shù)為28根。第三講數(shù)學(xué)規(guī)劃模型

3.5投資的風(fēng)險(xiǎn)與收益問題見word文檔第三講數(shù)學(xué)規(guī)劃模型

3.6進(jìn)一步的學(xué)習(xí)一、運(yùn)輸問題假設(shè)WirelessWidget（WW）公司有6個(gè)倉庫（warehouse）向8個(gè)銷售商（vendor）供應(yīng)小裝飾品，每個(gè)倉庫的供應(yīng)量是有限的，而每個(gè)銷售商的需求又必須得到滿足。因此WW公司要決定每個(gè)倉庫出多少貨能滿足每個(gè)銷售商而運(yùn)輸成本又最低。相關(guān)數(shù)據(jù)如下列表格所示。請(qǐng)引入合適的變量，建立求解該問題的數(shù)學(xué)模型。表1-1存貨數(shù)據(jù)倉庫號(hào)（WH）WH1WH2WH3WH4WH5WH6貨物量CAPACITY605551434152表1-2銷售商需求銷售商號(hào)（W）V1V2V3V4V5V6V7V8需求量DEMAND3537223241324338表1-3單位運(yùn)輸成本($)COSTV1V2V3V4V5V6V7V8WH162674259WH249538582WH352197433WH476739271WH532957265WH655228143第三講數(shù)學(xué)規(guī)劃模型

3.6進(jìn)一步的學(xué)習(xí)二、易拉罐下料問題：某公司采用一套沖壓設(shè)備生產(chǎn)一種罐裝飲料的易拉罐，這種易拉罐是用鍍錫板沖壓制成的。易拉罐為圓柱形，包括罐身、上蓋和下底，罐身高10cm，上蓋和下底直徑均為5cm。該公司使用兩種不同規(guī)格的鍍錫板原料：規(guī)格1的鍍錫板是邊長為24cm的正方形，規(guī)格2的鍍錫板是長方形，長、寬分別為32cm和28cm。由于生產(chǎn)工藝的限制，對(duì)于規(guī)格1的鍍錫板原料只能按照模式1、2、3進(jìn)行沖壓；對(duì)于規(guī)格2的鍍錫板原料只能按照模式4進(jìn)行沖壓。使用模式1、2、3、4進(jìn)行每次沖壓所需要的時(shí)間分別為1.5s、2s、1s、3s。該工廠每周工作40小時(shí)，每周可供使用的規(guī)格1、規(guī)格2的鍍錫板原料分別為5萬張和2萬張。目前每只易拉罐的利潤為0.10元，原料余料損失為0.001元/厘米2（如果周末有罐身、上蓋或下底不能配套組裝成易拉罐出售，也看作原料余料損失）。問工廠應(yīng)如何安排每周生產(chǎn)計(jì)劃？板材規(guī)格2：長方形，3228cm，2萬張。易拉罐下料每周工作40小時(shí)，每只易拉罐利潤0.10元，原料余料損失0.001元/cm2（不能裝配的罐身、蓋、底也是余料）模式1：1.5秒模式2：2秒模式3：1秒模式4：3秒上蓋下底罐身罐身高10cm，上蓋、下底直徑均5cm。

板材規(guī)格1：正方形，邊長24cm，5萬張。如何安排每周生產(chǎn)？

罐身個(gè)數(shù)底、蓋個(gè)數(shù)余料損失（cm2）沖壓時(shí)間（秒）模式1110222.61.5模式224183.32模式3016261.81模式445169.53模式1:正方形邊長24cm問題分析計(jì)算各種模式下的余料損失上、下底直徑d=5cm，罐身高h(yuǎn)=10cm。模式1余料損失242-10d2/4-dh=222.6cm2問題分析目標(biāo):易拉罐利潤扣除原料余料損失后的凈利潤最大

約束：每周工作時(shí)間不超過40小時(shí)；原料數(shù)量：規(guī)格1（模式1~3）5萬張，規(guī)格2（模式4）2萬張；罐身和底、蓋的配套組裝。注意：不能裝配的罐身、上下底也是余料決策變量

xi~按照第i種模式的生產(chǎn)張數(shù)(i=1,2,3,4)；y1~一周生產(chǎn)的易拉罐個(gè)數(shù)；y2~不配套的罐身個(gè)數(shù)；y3~不配套的底、蓋個(gè)數(shù)。模型建立目標(biāo)

約束條件

時(shí)間約束原料約束產(chǎn)量余料時(shí)間x1222.61.5x2183.32x3261.81x4169.53模型建立y1~易拉罐個(gè)數(shù)；y2~不配套的罐身；y3~不配套的底、蓋。每只易拉罐利潤0.10元，余料損失0.001元/cm2罐身面積dh=157.1cm2

底蓋面積d2/4=19.6cm2(40小時(shí))約束條件

配套約束y1~易拉罐個(gè)數(shù)；y2~不配套的罐身；y3~不配套的底、蓋。罐身底、蓋1102401645產(chǎn)量x1x2x3x4雖然xi和y1，y2，y3應(yīng)是整數(shù)，但是因生產(chǎn)量很大，可以把它們看成實(shí)數(shù)，從而用線性規(guī)劃模型處理。將所有決策變量擴(kuò)大10000倍（xi~萬張，yi~萬件）

LINDO發(fā)出警告信息：“數(shù)據(jù)之間的數(shù)量級(jí)差別太大，建議進(jìn)行預(yù)處理，縮小數(shù)據(jù)之間的差別”模式2生產(chǎn)40125張，模式3生產(chǎn)3750張，模式4生產(chǎn)20000張，共產(chǎn)易拉罐160250個(gè)(罐身和底、蓋無剩余)，凈利潤為4298元

模型求解OBJECTIVEFUNC