數(shù)學(xué)建模講義線性規(guī)劃模型2-運(yùn)輸問(wèn)題等課件

數(shù)學(xué)建模講義

第4章線性規(guī)劃模型--運(yùn)輸問(wèn)題等數(shù)學(xué)建模講義

第4章線性規(guī)劃模型--運(yùn)輸問(wèn)題等1其他費(fèi)用:450元/千噸

應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？

若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？元/千噸甲乙丙丁A160130220170B140130190150C190200230/引水管理費(fèi)1運(yùn)輸問(wèn)題：自來(lái)水輸送(§4.2)收入：900元/千噸

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水庫(kù)供水量(千噸)小區(qū)基本用水量(千噸)小區(qū)額外用水量(千噸)（以天計(jì)）其他費(fèi)用:450元/千噸應(yīng)如何分配水庫(kù)供水量，公司才能獲2總供水量：160確定送水方案使利潤(rùn)最大問(wèn)題分析A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40<總需求量：120+180=300總收入900160=144,000(元)收入：900元/千噸

其他費(fèi)用:450元/千噸

支出引水管理費(fèi)其他支出450160=72,000(元)使引水管理費(fèi)最小總供水量：160確定送水方案使利潤(rùn)最大問(wèn)題分析A：50B：63供應(yīng)限制約束條件需求限制

線性規(guī)劃模型(LP)目標(biāo)函數(shù)

水庫(kù)i向j區(qū)的日供水量為xij（x34=0）決策變量

模型建立確定3個(gè)水庫(kù)向4個(gè)小區(qū)的供水量供應(yīng)限制約束條件需求限制線性規(guī)劃模型(LP)目標(biāo)函數(shù)水庫(kù)4模型求解

OBJECTIVEFUNCTIONVALUE1)24400.00VARIABLEVALUEREDUCEDCOSTX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000

X22

50.0000000.000000X230.00000020.000000X24

10.0000000.000000X31

40.0000000.000000X320.00000010.000000X33

10.0000000.000000利潤(rùn)=總收入-其它費(fèi)用-引水管理費(fèi)=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理費(fèi)24400(元)模型求解OBJECTIVEFUNCTIONVALUE利5設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x320-1規(guī)劃：汽車廠生產(chǎn)計(jì)劃(§4.3)模型建立

小型中型大型現(xiàn)有量鋼材1.535600時(shí)間28025040060000利潤(rùn)234線性規(guī)劃模型(LP)設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x326模型求解

3）

模型中增加條件：x1,x2,x3

均為整數(shù)，重新求解。

OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOST

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226結(jié)果為小數(shù)，怎么辦？1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z(mì)=629，與LP最優(yōu)值632.2581相差不大。2）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)值z(mì)，通過(guò)比較可能得到更優(yōu)的解。但必須檢驗(yàn)它們是否滿足約束條件。為什么？模型求解3）模型中增加條件：x1,x2,x3均為7IP可用LINGO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡(jiǎn)記IP)IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=632Max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;@gin(x1);@gin(x2);@gin(x3);OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解

IP結(jié)果輸出IP可用LINGO直接求解整數(shù)規(guī)劃(IntegerProg8其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個(gè)LP子模型汽車廠生產(chǎn)計(jì)劃若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1,x2,,x3=0或80x1=80，x2=150，x3=0，最優(yōu)值z(mì)=610其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整9LINGO中對(duì)0-1變量的限定：@bin(y1);@bin(y2);@bin(y3);方法2：引入0-1變量，化為整數(shù)規(guī)劃

M為大的正數(shù)，可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOST

X180.000000-2.000000

X2150.000000-3.000000

X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前

LINGO中對(duì)0-1變量的限定：方法2：引入0-1變量，化為10NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO,MATLAB)，但是其結(jié)果常依賴于初值的選擇。方法3：化為非線性規(guī)劃

非線性規(guī)劃（Non-LinearProgramming，簡(jiǎn)記NLP）

實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時(shí)，才能得到正確的結(jié)果。

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1=0或

80x2=0或

80x3=0或

80NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO,MATLA11丁的蛙泳成績(jī)退步到1’15”2；戊的自由泳成績(jī)進(jìn)步到57”5,組成接力隊(duì)的方案是否應(yīng)該調(diào)整？如何選拔隊(duì)員組成4100米混合泳接力隊(duì)?3分配問(wèn)題：混合泳接力隊(duì)的選拔(§4.4)

甲乙丙丁戊蝶泳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名候選人的百米成績(jī)窮舉法：組成接力隊(duì)的方案共有5!=120種。丁的蛙泳成績(jī)退步到1’15”2；戊的自由泳成績(jī)進(jìn)步到57”512目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則記xij=0

0-1規(guī)劃模型

cij(秒)~隊(duì)員i第j種泳姿的百米成績(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人目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則13模型求解

最優(yōu)解：x14=x21=x32=x43=1,其它變量為0;成績(jī)?yōu)?53.2(秒)=4’13”2MIN=66.8*x11+75.6*x12+87*x13+58.6*x14+……+62.4*x54;x11+x12+x13+x14<=1;……x41+x42+x43+x44<=1;x11+x21+x31+x41+x51=1;……x14+x24+x34+x44+x54=1;@bin(x11);…….;@bin(x54);輸入LINGO求解

甲乙丙丁戊蝶泳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甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.模型求解最優(yōu)解：x14=x21=x32=x4314丁蛙泳c43

=69.675.2，戊自由泳c54=62.4

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

4多目標(biāo)規(guī)劃：選課策略(§4.4)要求至少選兩門數(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ù)測(cè)理論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í)哪些課程？

為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程？4多目標(biāo)規(guī)劃：160-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ù)測(cè)理論運(yùn)籌學(xué)9數(shù)學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)；計(jì)算機(jī)0-1規(guī)劃模型決策變量目標(biāo)函數(shù)xi=1~選修課號(hào)i17先修課程要求最優(yōu)解：

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

約束條件x3=1必有x1=x2=1模型求解（LINGO）課號(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ù)測(cè)理論應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)微積分；線性代數(shù)先修課程要求最優(yōu)解：x1=x2=x3=x6=18學(xué)分最多多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化。兩目標(biāo)(多目標(biāo))規(guī)劃

討論：選修課程最少，學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？課程最少以學(xué)分最多為目標(biāo)，不管課程多少。以課程最少為目標(biāo)，不管學(xué)分多少。最優(yōu)解如上，6門課程，總學(xué)分21。最優(yōu)解顯然是選修所有9門課程。學(xué)分最多多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化。兩目標(biāo)(多目標(biāo)19多目標(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ù)測(cè)理論29數(shù)學(xué)實(shí)驗(yàn)3LINGO無(wú)法告訴優(yōu)化問(wèn)題的解是否唯一?？蓪9=1易為x6=1增加約束，以學(xué)分最多為目標(biāo)求解。多目標(biāo)規(guī)劃在課程最少的前提下以學(xué)分最多為目標(biāo)。最優(yōu)解：20多目標(biāo)規(guī)劃

對(duì)學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開(kāi)。最優(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ù)測(cè)理論29數(shù)學(xué)實(shí)驗(yàn)3多目標(biāo)規(guī)劃對(duì)學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開(kāi)。21討論與思考最優(yōu)解與1=0，2=1的結(jié)果相同——學(xué)分最多多目標(biāo)規(guī)劃

最優(yōu)解與1=1，2=0的結(jié)果相同——課程最少討論與思考最優(yōu)解與1=0，2=1的結(jié)果相同——學(xué)分最多多22問(wèn)題1.如何下料最節(jié)省?5下料問(wèn)題：鋼管下料(§4.6)問(wèn)題2.客戶增加需求：原料鋼管:每根19米4米50根6米20根8米15根客戶需求節(jié)省的標(biāo)準(zhǔn)是什么？由于采用不同切割模式太多，會(huì)增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過(guò)3種。如何下料最節(jié)??？5米10根問(wèn)題1.如何下料最節(jié)省?5下料問(wèn)題：鋼管下料(§423按照客戶需要在一根原料鋼管上安排切割的一種組合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根鋼管下料按照客戶需要在一根原料鋼管上安排切割的一種組合。切割模式余24為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)??？合理切割模式2.所用原料鋼管總根數(shù)最少模式

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023鋼管下料問(wèn)題1兩種標(biāo)準(zhǔn)1.原料鋼管剩余總余量最小為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼25xi~按第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ù)xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7)26當(dāng)余料沒(méi)有用處時(shí)，通常以總根數(shù)最少為目標(biāo)目標(biāo)2（總根數(shù)）鋼管下料問(wèn)題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米”相比當(dāng)余料沒(méi)有用處時(shí)，通常以總根數(shù)最少為目標(biāo)目標(biāo)2（總根數(shù)）鋼27鋼管下料問(wèn)題2對(duì)大規(guī)模問(wèn)題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過(guò)3種。現(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過(guò)于復(fù)雜。決策變量

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

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

鋼管下料問(wèn)題2需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長(zhǎng)19米增加約束，縮小可行域，便于求解原料鋼管總根數(shù)下界：特殊生產(chǎn)30LINGO求解整數(shù)非線性規(guī)劃模型（代碼見(jiàn)P125

）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根。▌LINGO求解整數(shù)非線性規(guī)劃模型（代碼見(jiàn)P125）Loca31板材規(guī)格2：長(zhǎng)方形，3228cm，2萬(wàn)張。例

易拉罐下料每周工作40小時(shí)，每只易拉罐利潤(rùn)0.10元，原料余料損失0.001元/cm2（不能裝配的罐身、蓋、底也是余料）模式1：1.5秒模式2：2秒模式3：1秒模式4：3秒上蓋下底罐身罐身高10cm，上蓋、下底直徑均5cm。

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

板材規(guī)格2：例易拉罐下料每周工作40小時(shí)，每只易拉罐利潤(rùn)032

罐身個(gè)數(shù)底、蓋個(gè)數(shù)余料損失（cm2）沖壓時(shí)間（秒）模式1110222.61.5模式224183.32模式3016261.81模式445169.53模式1:正方形邊長(zhǎng)24cm問(wèn)題分析計(jì)算各種模式下的余料損失上、下底直徑d=5cm，罐身高h(yuǎn)=10cm。模式1余料損失242-10d2/4-dh=222.6cm2

罐身個(gè)數(shù)底、蓋余料損失沖壓時(shí)間（秒）模式1110222.633問(wèn)題分析目標(biāo):易拉罐利潤(rùn)扣除原料余料損失后的凈利潤(rùn)最大

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

xi~按照第i種模式的生產(chǎn)張數(shù)(i=1,2,3,4)；y1~一周生產(chǎn)的易拉罐個(gè)數(shù)；y2~不配套的罐身個(gè)數(shù)；y3~不配套的底、蓋個(gè)數(shù)。模型建立問(wèn)題分析目標(biāo):易拉罐利潤(rùn)扣除原料余料損失后的凈利潤(rùn)最大約34目標(biāo)

約束條件

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

底蓋面積d2/4=19.6cm2(40小時(shí))目標(biāo)約束條件時(shí)間約束原料約束產(chǎn)量余料時(shí)間x1222.35約束條件

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

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è)(罐身和底、蓋無(wú)剩余)，凈利潤(rùn)為4298元

模型求解OBJECTIVEFUNCTIONVALUE1)0.4298337VARIABLEVALUEREDUCEDCOSTY116.0250000.000000X10.0000000.000050X24.0125000.000000X30.3750000.000000X42.0000000.000000Y20.0000000.223331Y30.0000000.036484將所有決策變量擴(kuò)大10000倍（xi~萬(wàn)張，yi~萬(wàn)件）37下料問(wèn)題的建模確定下料模式構(gòu)造優(yōu)化模型規(guī)格不太多，可枚舉下料模式，建立整數(shù)線性規(guī)劃模型，否則要構(gòu)造整數(shù)非線性規(guī)劃模型，求解困難，可用縮小可行域的方法進(jìn)行化簡(jiǎn)，但要保證最優(yōu)解的存在。一維問(wèn)題（如鋼管下料）二維問(wèn)題（如易拉罐下料）具體問(wèn)題具體分析（比較復(fù)雜）下料問(wèn)題的建模確定下料模式構(gòu)造優(yōu)化模型規(guī)格不太多，38數(shù)學(xué)建模講義

第4章線性規(guī)劃模型--運(yùn)輸問(wèn)題等數(shù)學(xué)建模講義

第4章線性規(guī)劃模型--運(yùn)輸問(wèn)題等39其他費(fèi)用:450元/千噸

應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？

若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？元/千噸甲乙丙丁A160130220170B140130190150C190200230/引水管理費(fèi)1運(yùn)輸問(wèn)題：自來(lái)水輸送(§4.2)收入：900元/千噸

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40水庫(kù)供水量(千噸)小區(qū)基本用水量(千噸)小區(qū)額外用水量(千噸)（以天計(jì)）其他費(fèi)用:450元/千噸應(yīng)如何分配水庫(kù)供水量，公司才能獲40總供水量：160確定送水方案使利潤(rùn)最大問(wèn)題分析A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40<總需求量：120+180=300總收入900160=144,000(元)收入：900元/千噸

其他費(fèi)用:450元/千噸

支出引水管理費(fèi)其他支出450160=72,000(元)使引水管理費(fèi)最小總供水量：160確定送水方案使利潤(rùn)最大問(wèn)題分析A：50B：641供應(yīng)限制約束條件需求限制

線性規(guī)劃模型(LP)目標(biāo)函數(shù)

水庫(kù)i向j區(qū)的日供水量為xij（x34=0）決策變量

模型建立確定3個(gè)水庫(kù)向4個(gè)小區(qū)的供水量供應(yīng)限制約束條件需求限制線性規(guī)劃模型(LP)目標(biāo)函數(shù)水庫(kù)42模型求解

OBJECTIVEFUNCTIONVALUE1)24400.00VARIABLEVALUEREDUCEDCOSTX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000

X22

50.0000000.000000X230.00000020.000000X24

10.0000000.000000X31

40.0000000.000000X320.00000010.000000X33

10.0000000.000000利潤(rùn)=總收入-其它費(fèi)用-引水管理費(fèi)=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010引水管理費(fèi)24400(元)模型求解OBJECTIVEFUNCTIONVALUE利43設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x320-1規(guī)劃：汽車廠生產(chǎn)計(jì)劃(§4.3)模型建立

小型中型大型現(xiàn)有量鋼材1.535600時(shí)間28025040060000利潤(rùn)234線性規(guī)劃模型(LP)設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3244模型求解

3）

模型中增加條件：x1,x2,x3

均為整數(shù)，重新求解。

OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOST

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226結(jié)果為小數(shù)，怎么辦？1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z(mì)=629，與LP最優(yōu)值632.2581相差不大。2）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)值z(mì)，通過(guò)比較可能得到更優(yōu)的解。但必須檢驗(yàn)它們是否滿足約束條件。為什么？模型求解3）模型中增加條件：x1,x2,x3均為45IP可用LINGO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡(jiǎn)記IP)IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=632Max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;@gin(x1);@gin(x2);@gin(x3);OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解

IP結(jié)果輸出IP可用LINGO直接求解整數(shù)規(guī)劃(IntegerProg46其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個(gè)LP子模型汽車廠生產(chǎn)計(jì)劃若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1,x2,,x3=0或80x1=80，x2=150，x3=0，最優(yōu)值z(mì)=610其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整47LINGO中對(duì)0-1變量的限定：@bin(y1);@bin(y2);@bin(y3);方法2：引入0-1變量，化為整數(shù)規(guī)劃

M為大的正數(shù)，可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOST

X180.000000-2.000000

X2150.000000-3.000000

X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前

LINGO中對(duì)0-1變量的限定：方法2：引入0-1變量，化為48NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO,MATLAB)，但是其結(jié)果常依賴于初值的選擇。方法3：化為非線性規(guī)劃

非線性規(guī)劃（Non-LinearProgramming，簡(jiǎn)記NLP）

實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時(shí)，才能得到正確的結(jié)果。

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃。x1=0或

80x2=0或

80x3=0或

80NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO,MATLA49丁的蛙泳成績(jī)退步到1’15”2；戊的自由泳成績(jī)進(jìn)步到57”5,組成接力隊(duì)的方案是否應(yīng)該調(diào)整？如何選拔隊(duì)員組成4100米混合泳接力隊(duì)?3分配問(wèn)題：混合泳接力隊(duì)的選拔(§4.4)

甲乙丙丁戊蝶泳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名候選人的百米成績(jī)窮舉法：組成接力隊(duì)的方案共有5!=120種。丁的蛙泳成績(jī)退步到1’15”2；戊的自由泳成績(jī)進(jìn)步到57”550目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則記xij=0

0-1規(guī)劃模型

cij(秒)~隊(duì)員i第j種泳姿的百米成績(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人目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則51模型求解

最優(yōu)解：x14=x21=x32=x43=1,其它變量為0;成績(jī)?yōu)?53.2(秒)=4’13”2MIN=66.8*x11+75.6*x12+87*x13+58.6*x14+……+62.4*x54;x11+x12+x13+x14<=1;……x41+x42+x43+x44<=1;x11+x21+x31+x41+x51=1;……x14+x24+x34+x44+x54=1;@bin(x11);…….;@bin(x54);輸入LINGO求解

甲乙丙丁戊蝶泳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甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.模型求解最優(yōu)解：x14=x21=x32=x4352丁蛙泳c43

=69.675.2，戊自由泳c54=62.4

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

4多目標(biāo)規(guī)劃：選課策略(§4.4)要求至少選兩門數(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ù)測(cè)理論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í)哪些課程？

為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程？4多目標(biāo)規(guī)劃：540-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ù)測(cè)理論運(yùn)籌學(xué)9數(shù)學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)；計(jì)算機(jī)0-1規(guī)劃模型決策變量目標(biāo)函數(shù)xi=1~選修課號(hào)i55先修課程要求最優(yōu)解：

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

約束條件x3=1必有x1=x2=1模型求解（LINGO）課號(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ù)測(cè)理論應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)微積分；線性代數(shù)先修課程要求最優(yōu)解：x1=x2=x3=x6=56學(xué)分最多多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化。兩目標(biāo)(多目標(biāo))規(guī)劃

討論：選修課程最少，學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？課程最少以學(xué)分最多為目標(biāo)，不管課程多少。以課程最少為目標(biāo)，不管學(xué)分多少。最優(yōu)解如上，6門課程，總學(xué)分21。最優(yōu)解顯然是選修所有9門課程。學(xué)分最多多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化。兩目標(biāo)(多目標(biāo)57多目標(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ù)測(cè)理論29數(shù)學(xué)實(shí)驗(yàn)3LINGO無(wú)法告訴優(yōu)化問(wèn)題的解是否唯一。可將x9=1易為x6=1增加約束，以學(xué)分最多為目標(biāo)求解。多目標(biāo)規(guī)劃在課程最少的前提下以學(xué)分最多為目標(biāo)。最優(yōu)解：58多目標(biāo)規(guī)劃

對(duì)學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開(kāi)。最優(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ù)測(cè)理論29數(shù)學(xué)實(shí)驗(yàn)3多目標(biāo)規(guī)劃對(duì)學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開(kāi)。59討論與思考最優(yōu)解與1=0，2=1的結(jié)果相同——學(xué)分最多多目標(biāo)規(guī)劃

最優(yōu)解與1=1，2=0的結(jié)果相同——課程最少討論與思考最優(yōu)解與1=0，2=1的結(jié)果相同——學(xué)分最多多60問(wèn)題1.如何下料最節(jié)省?5下料問(wèn)題：鋼管下料(§4.6)問(wèn)題2.客戶增加需求：原料鋼管:每根19米4米50根6米20根8米15根客戶需求節(jié)省的標(biāo)準(zhǔn)是什么？由于采用不同切割模式太多，會(huì)增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過(guò)3種。如何下料最節(jié)??？5米10根問(wèn)題1.如何下料最節(jié)省?5下料問(wèn)題：鋼管下料(§461按照客戶需要在一根原料鋼管上安排切割的一種組合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根鋼管下料按照客戶需要在一根原料鋼管上安排切割的一種組合。切割模式余62為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)??？合理切割模式2.所用原料鋼管總根數(shù)最少模式

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023鋼管下料問(wèn)題1兩種標(biāo)準(zhǔn)1.原料鋼管剩余總余量最小為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼63xi~按第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ù)xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7)64當(dāng)余料沒(méi)有用處時(shí)，通常以總根數(shù)最少為目標(biāo)目標(biāo)2（總根數(shù)）鋼管下料問(wèn)題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米”相比當(dāng)余料沒(méi)有用處時(shí)，通常以總根數(shù)最少為目標(biāo)目標(biāo)2（總根數(shù)）鋼65鋼管下料問(wèn)題2對(duì)大規(guī)模問(wèn)題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過(guò)3種?，F(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過(guò)于復(fù)雜。決策變量

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

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

鋼管下料問(wèn)題2需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長(zhǎng)19米增加約束，縮小可行域，便于求解原料鋼管總根數(shù)下界：特殊生產(chǎn)68LINGO求解整數(shù)非線性規(guī)劃模型（代碼見(jiàn)P125

）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.000000