數(shù)學(xué)建?！蹲顑?yōu)化問題》

現(xiàn)實生活中普遍存在著優(yōu)化問題.

例：一根長為L的鐵絲圍成長方形，問：怎樣圍才能使長方形的面積最大？第七章最優(yōu)化問題數(shù)學(xué)模型變量個數(shù)

一元最優(yōu)化多元最優(yōu)化約束條件無約束最優(yōu)化有約束最優(yōu)化

目標(biāo)函數(shù)函數(shù)特點單目標(biāo)最優(yōu)化多目標(biāo)最優(yōu)化線性規(guī)劃非線性規(guī)劃最優(yōu)化分類

建立優(yōu)化模型的關(guān)鍵之一是根據(jù)建模目的確定恰當(dāng)?shù)哪繕?biāo)函數(shù).

求解簡單的無約束優(yōu)化模型（一元或二元）一般用微分法.無約束最優(yōu)化7.1

存貯模型配件廠為裝配線生產(chǎn)若干種產(chǎn)品,輪換產(chǎn)品時因更換設(shè)備要付生產(chǎn)準(zhǔn)備費,產(chǎn)量大于需求時要付貯存費.該廠生產(chǎn)能力非常大,即所需數(shù)量可在很短時間內(nèi)產(chǎn)出.已知某產(chǎn)品日需求量100件,生產(chǎn)準(zhǔn)備費5000元,貯存費每日每件1元.試安排該產(chǎn)品的生產(chǎn)計劃,即多少天生產(chǎn)一次（生產(chǎn)周期）,每次產(chǎn)量多少,使總費用最小.問題分析

每天生產(chǎn)一次,每次100件,無貯存費,準(zhǔn)備費5000元.日需求100件,準(zhǔn)備費5000元,貯存費每日每件1元.10天生產(chǎn)一次,每次1000件,貯存費900+800+…+100=4500元,準(zhǔn)備費5000元,總計9500元.50天生產(chǎn)一次,每次5000件,貯存費4900+4800+…+100=122500元,準(zhǔn)備費5000元,總計127500元.平均每天費用950元平均每天費用2550元10天生產(chǎn)一次,平均每天費用最小嗎?每天費用5000元這是一個優(yōu)化問題,關(guān)鍵在建立目標(biāo)函數(shù).顯然不能用一個周期的總費用作為目標(biāo)函數(shù).目標(biāo)函數(shù)——每天總費用的平均值.周期短,產(chǎn)量小周期長,產(chǎn)量大問題分析貯存費少，準(zhǔn)備費多準(zhǔn)備費少，貯存費多存在最佳的周期和產(chǎn)量，使總費用（二者之和）最小.模型假設(shè)1.產(chǎn)品每天的需求量為常數(shù)r；2.每次生產(chǎn)準(zhǔn)備費為c1,每天每件產(chǎn)品貯存費為c2；3.T天生產(chǎn)一次（周期）,每次生產(chǎn)Q件,當(dāng)貯存量為零時,Q件產(chǎn)品立即到來（生產(chǎn)時間不計）；建模目的設(shè)r,c1,c2已知,求T,Q使每天總費用的平均值最小.4.為方便起見,時間和產(chǎn)量都作為連續(xù)量處理.模型建立0tq貯存量表示為時間的函數(shù)q(t)TQrt=0生產(chǎn)Q件,q(0)=Q,q(t)以需求速率r遞減,q(T)=0.一周期總費用每天總費用平均值（目標(biāo)函數(shù)）離散問題連續(xù)化一周期貯存費為A=QT/2模型求解求T使模型解釋定性分析敏感性分析參數(shù)c1,c2,r的微小變化對T,Q的影響T對c1的(相對)敏感度c1增加1%,T增加0.5%S(T,c2)=-1/2,S(T,r)=-1/2c2或r增加1%,T減少0.5%準(zhǔn)備費c1

貯存費為c2日需求量r經(jīng)濟批量訂貨公式（EOQ公式）

用于訂貨供應(yīng)情況:不允許缺貨的存貯模型模型應(yīng)用T=10(天),Q=1000(件),C=1000(元)

回答原問題c1=5000,c2=1,r=100每天需求量r,每次訂貨費c1,每天每件貯存費c2,T天訂貨一次(周期),每次訂貨Q件,當(dāng)貯存量降到零時,Q件立即到貨.?允許缺貨的存貯模型AB0qQrT1t當(dāng)貯存量降到零時仍有需求r,出現(xiàn)缺貨,造成損失.原模型假設(shè)3:貯存量降到零時Q件立即生產(chǎn)出來(或立即到貨).現(xiàn)假設(shè)3:允許缺貨,每天每件缺貨損失費c3,缺貨需補足.T一周期總費用一周期貯存費一周期缺貨費每天總費用平均值（目標(biāo)函數(shù)）一周期總費用求T,Q使為與不允許缺貨的存貯模型相比,T記作T',Q記作Q'.允許缺貨的存貯模型不允許缺貨模型記允許缺貨模型不允許缺貨允許缺貨模型0qQ

rT1tT注意:缺貨需補足Q

~每周期初的存貯量R每周期的生產(chǎn)量R

（或訂貨量）Q~不允許缺貨時的產(chǎn)量(或訂貨量)7.2

生豬的出售時機飼養(yǎng)場每天投入4元資金,用于飼料、人力、設(shè)備,估計可使80千克重的生豬體重增加2公斤。問題市場價格目前為每千克8元，但是預(yù)測每天會降低0.1元，問生豬應(yīng)何時出售？如果估計和預(yù)測有誤差，對結(jié)果有何影響？分析投入資金使生豬體重隨時間增加,出售單價隨時間減少,故存在最佳出售時機,使利潤最大求t使Q(t)最大10天后出售,可多得利潤20元建模及求解生豬體重w=80+rt出售價格p=8-gt銷售收入R=pw資金投入C=4t利潤Q=R-C=pw-C估計r=2,若當(dāng)前出售,利潤為80×8=640（元）t天出售=10Q(10)=660>640g=0.1敏感性分析研究r,g變化時對模型結(jié)果的影響估計r=2，g=0.1

設(shè)g=0.1不變t對r的（相對）敏感度生豬每天體重增加量r增加1%,出售時間推遲3%。rt敏感性分析估計r=2，g=0.1研究r,g變化時對模型結(jié)果的影響

設(shè)r=2不變t對g的（相對）敏感度生豬價格每天的降低量g增加1%,出售時間提前3%。gt強健性分析保留生豬直到利潤的增值等于每天的費用時出售研究r,g不是常數(shù)時對模型結(jié)果的影響w=80+rt

w=w(t)p=8-gt

p=p(t)每天利潤的增值每天投入的資金7.3

森林救火森林失火后,要確定派出消防隊員的數(shù)量.隊員多,森林損失小,救援費用大；隊員少,森林損失大,救援費用小.綜合考慮損失費和救援費,確定隊員數(shù)量.問題分析問題記隊員人數(shù)x,失火時刻t=0,開始救火時刻t1,滅火時刻t2,時刻t森林燒毀面積B(t).

損失費f1(x)是x的減函數(shù),由燒毀面積B(t2)決定.

救援費f2(x)是x的增函數(shù),由隊員人數(shù)和救火時間決定.存在恰當(dāng)?shù)膞,使f1(x),f2(x)之和最小.

關(guān)鍵是對B(t)作出合理的簡化假設(shè).問題分析失火時刻t=0,開始救火時刻t1,滅火時刻t2,畫出時刻t森林燒毀面積B(t)的大致圖形.t1t20tBB(t2)分析B(t)比較困難,轉(zhuǎn)而討論單位時間燒毀面積dB/dt

(森林燒毀的速度).模型假設(shè)3）f1(x)與B(t2)成正比,系數(shù)c1(燒毀單位面積損失費）1）0tt1,dB/dt與t成正比,系數(shù)(火勢蔓延速度).2）t1

t

t2,

降為

-x

(

為隊員的平均滅火速度).4）每個隊員的單位時間滅火費用c2,一次性費用c3.假設(shè)1）的解釋

rB火勢以失火點為中心,均勻向四周呈圓形蔓延,半徑r與t成正比.面積B與t2成正比dB/dt與t成正比模型建立b0t1tt2假設(shè)1）目標(biāo)函數(shù)——總費用假設(shè)3）4）假設(shè)2）模型建立目標(biāo)函數(shù)——總費用模型求解求x使C(x)最小結(jié)果解釋

/

是火勢不繼續(xù)蔓延的最少隊員數(shù)b0t1t2t其中c1,c2,c3,t1,

,

為已知參數(shù)

c1,t1,

x

c3,

x

結(jié)果解釋c1~燒毀單位面積損失費,c2~每個隊員單位時間滅火費,c3~每個隊員一次性費用,t1~開始救火時刻,~火勢蔓延速度,~每個隊員平均滅火速度.7.4

最優(yōu)價格問題根據(jù)產(chǎn)品成本和市場需求,在產(chǎn)銷平衡條件下確定商品價格,使利潤最大.假設(shè)1）產(chǎn)量等于銷量,記作x.2）收入與銷量x成正比,系數(shù)p即價格.3）支出與產(chǎn)量x成正比,系數(shù)q即成本.4）銷量x依于價格p,x(p)是減函數(shù).

建模與求解收入支出利潤進一步設(shè)求p使U(p)最大使利潤U(p)最大的最優(yōu)價格p*滿足最大利潤在邊際收入等于邊際支出時達到

建模與求解邊際收入邊際支出結(jié)果解釋

q/2~成本的一半

b~價格上升1單位時銷量的下降幅度（需求對價格的敏感度）

a~絕對需求(

p=0的需求)b

p*

a

p*

銷量p~價格q~成本最優(yōu)價格q2U(q1,q2)=cq107.5

消費者的選擇問題消費者對甲乙兩種商品的偏愛程度用無差別曲線族表示,問他如何分配一定數(shù)量的錢,購買這兩種商品,以達到最大的滿意度.設(shè)甲乙數(shù)量為q1,q2,消費者的無差別曲線族(單調(diào)減、下凸、不相交）,記作U(q1,q2)=cU(q1,q2)~效用函數(shù)已知甲乙價格p1,p2,有錢s,試分配s,購買甲乙數(shù)量q1,q2,使U(q1,q2)最大.s/p2s/p1q2U(q1,q2)=cq10模型及求解已知價格p1,p2,錢s,求q1,q2,或p1q1/p2q2,使U(q1,q2)最大.幾何解釋直線MN:最優(yōu)解Q:MN與l2切點斜率·MQN··結(jié)果解釋——邊際效用消費者均衡狀態(tài)在兩種商品的邊際效用之比恰等于它們價格之比時達到.效用函數(shù)U(q1,q2)應(yīng)滿足的條件條件A

U(q1,q2)=c

所確定的函數(shù)q2=q2(q1)單調(diào)減、下凸條件B條件B條件A效用函數(shù)U(q1,q2)幾種常用的形式

消費者均衡狀態(tài)下購買兩種商品費用之比與二者價格之比的平方根成正比.

U(q1,q2)中參數(shù)

,分別表示消費者對甲乙兩種商品的偏愛程度.

購買兩種商品費用之比與二者價格無關(guān).

U(q1,q2)中參數(shù)

,

分別表示對甲乙的偏愛程度.效用函數(shù)U(q1,q2)幾種常用的形式7.6

冰山運輸背景波斯灣地區(qū)水資源貧乏,淡化海水的成本為每立方米0.1英鎊.專家建議從9600千米遠的南極用拖船運送冰山,取代淡化海水.

從經(jīng)濟角度研究冰山運輸?shù)目尚行?建模準(zhǔn)備1.日租金和最大運量船型小中大日租金（英鎊）

最大運量（米3）4.06.28.051051061072.燃料消耗（英鎊/千米）3.融化速率（米/天）與南極距離(千米)船速(千米/小時)

01000>400013500.10.300.150.45

00.20.6冰山體積(米3)船速(千米/小時)

105106107135

8.410.512.6

10.813.516.2

13.216.519.8建模準(zhǔn)備建模目的選擇船型和船速,使冰山到達目的地后每立方米水的費用最低,并與淡化海水的費用比較.模型假設(shè)航行過程中船速不變,總距離9600千米.冰山呈球形,球面各點融化速率相同.到達目的地后,每立方米冰可融化0.85立方米水.建模分析目的地水體積運輸過程融化規(guī)律總費用目的地冰體積初始冰山體積燃料消耗租金船型,船速船型船型,船速船型第t天融化速率模型建立1.冰山融化規(guī)律船速u(千米/小時)與南極距離d(千米)融化速率r(米/天）r是u

的線性函數(shù)d<4000時r與d成正比d>4000時r與d無關(guān)航行t天,d=24ut

01000>400013500.10.300.150.45

00.20.6urd1.冰山融化規(guī)律冰山初始半徑R0，航行t天時半徑冰山初始體積t天時體積總航行天數(shù)選定u,V0,航行t天時冰山體積到達目的地時冰山體積2.燃料消耗

105106107135

8.410.512.6

10.813.516.2

13.216.519.8Vuq1燃料消耗q1(英鎊/千米)q1對u線性,對lgV

線性選定u,V0,航行第t天燃料消耗q(英鎊/天)燃料消耗總費用

V05105

106107f(V0)4.06.28.0

3.運送每立方米水費用冰山初始體積V0的日租金f(V0)（英鎊）航行天數(shù)總?cè)剂舷馁M用拖船租金費用冰山運輸總費用冰山到達目的地后得到的水體積3.運送每立方米水費用冰山運輸總費用運送每立方米水費用

到達目的地時冰山體積模型求解選擇船型和船速,使冰山到達目的地后每立方米水的費用最低求u,V0使Y(u,V0)最小u=4~5(千米/小時),V0=107(米3)，Y(u,V0)最小V0只能取離散值經(jīng)驗公式很粗糙33.544.551070.07230.06830.06490.06630.06580.22510.20130.18340.18420.179010678.90329.82206.21385.46474.5102V0u5

106取幾組（V0，u）用枚舉法計算結(jié)果分析由于未考慮影響航行的種種不利因素,冰山到達目的地后實際體積會顯著小于V(u,V0).有關(guān)部門認(rèn)為,只有當(dāng)計算出的Y(u,V0)顯著低于淡化海水的成本時,才考慮其可行性.大型拖船V0=107(米3),船速u=4~5(千米/小時),冰山到達目的地后每立方米水的費用Y(u,V0)約0.065(英鎊).雖然0.065英鎊略低于淡化海水的成本0.1英鎊,但是模型假設(shè)和構(gòu)造非常簡化與粗糙.冰山運輸

模型來自實際問題的可行性研究.

收集數(shù)據(jù)是建模的重要準(zhǔn)備工作.

根據(jù)數(shù)據(jù)得到的經(jīng)驗公式是建模的基礎(chǔ).

冰山形狀的球形假設(shè)簡化了計算,這個假設(shè)的合理性如何?如果改變它呢?數(shù)學(xué)規(guī)劃模型

實際問題中的優(yōu)化模型x~決策變量f(x)~目標(biāo)函數(shù)gi(x)0~約束條件多元函數(shù)條件極值決策變量個數(shù)n和約束條件個數(shù)m較大數(shù)學(xué)規(guī)劃線性規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃重點在模型的建立、軟件求解和結(jié)果的分析1桶牛奶

3kgA1

12小時

8小時

4kgA2

或獲利24元/kg獲利16元/kg50桶牛奶時間480小時至多加工100kgA1

制訂生產(chǎn)計劃,使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時工人,付出的工資最多是每小時幾元?A1的獲利增加到30元/kg，應(yīng)否改變生產(chǎn)計劃？每天:問題7.1奶制品的生產(chǎn)與銷售

1桶牛奶3kgA1

12小時8小時4kgA2

或獲利24元/kg獲利16元/kgx1桶牛奶生產(chǎn)A1

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

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動時間

加工能力

決策變量

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

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

線性規(guī)劃模型(LP)時間480小時至多加工100kgA1

50桶牛奶每天基本模型模型求解

軟件實現(xiàn)

LINDOmax72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元。結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三種資源“資源”剩余為零的約束為緊約束（有效約束）原料無剩余時間無剩余加工能力剩余40結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000最優(yōu)解下“資源”增加1單位時“效益”的增量35元可買到1桶牛奶,要買嗎?35<48,應(yīng)該買！

聘用臨時工人付出的工資最多每小時幾元?2元！原料增加1單位,利潤增長48時間增加1單位,利潤增長2加工能力增長不影響利潤影子價格RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最優(yōu)解不變時目標(biāo)函數(shù)系數(shù)允許變化范圍DORANGE(SENSITIVITY)ANALYSIS?

YesA1獲利增加到30元/kg,應(yīng)否改變生產(chǎn)計劃?x1系數(shù)由243=72增至303=90<96,在允許范圍內(nèi)不變！約束條件不變!x1系數(shù)范圍:(72-8,72+24)=(64,96)

x2系數(shù)范圍:(48,72)結(jié)果解釋

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價格有意義時約束右端的允許變化范圍35元可買到1桶牛奶,每天最多買多少?最多買10桶!目標(biāo)函數(shù)不變!原料最多增加10時間最多增加53原料時間例2奶制品的生產(chǎn)銷售計劃

在例1基礎(chǔ)上深加工1桶牛奶3kgA1

12小時8小時4kgA2

或獲利24元/kg獲利16元/kg0.8kgB12小時,3元1kg獲利44元/kg0.75kgB22小時,3元1kg獲利32元/kg制訂生產(chǎn)計劃,使每天凈利潤最大30元可增加1桶牛奶,3元可增加1小時時間,應(yīng)否投資?現(xiàn)投資150元，可賺回多少？50桶牛奶,480小時至多100kgA1

B1，B2的獲利經(jīng)常有10%的波動，對計劃有無影響？1桶牛奶3kgA1

12小時8小時4kgA2

或獲利24元/kg獲利16元/kg

0.8kgB12小時,3元1kg獲利44元/kg0.75kg

B22小時,3元1kg獲利32元/kg出售x1kgA1,x2kgA2,x3kgB1,x4kgB2原料供應(yīng)

勞動時間

加工能力

決策變量

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

利潤約束條件非負(fù)約束

x5kgA1加工B1,x6kgA2加工B2附加約束

基本模型模型求解

軟件實現(xiàn)

LINDOOBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000DORANGE(SENSITIVITY)ANALYSIS?No

OBJECTIVEFUNCTIONVALUE1)3460.800

VARIABLEVALUEREDUCEDCOST

X10.0000001.680000

X2168.0000000.000000

X319.2000010.000000

X40.0000000.000000

X524.0000000.000000

X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000結(jié)果解釋8桶牛奶加工成A1,42桶牛奶加工成A2每天利潤3460.8(元)銷售168kgA2銷售19.2kgB124kgA1加工成B1

除加工能力外其余約束均為緊約束結(jié)果解釋OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.00000030元可增加1桶牛奶,3元可增加1小時時間,應(yīng)否投資？現(xiàn)投資150元,可賺回多少？投資150元增加5桶牛奶,可賺回189.6元。(大于增加時間的利潤增長)增加1桶牛奶使利潤增長3.16×12=37.92增加1小時時間使利潤增長3.26結(jié)果解釋B1,B2的獲利有10%的波動,對計劃有無影響?RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124.0000001.680000INFINITYX216.0000008.1500002.100000

X344.00000019.7500023.166667X432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.520000INFINITY

……

……DORANGE(SENSITIVITY)ANALYSIS?Yes波動對計劃有影響生產(chǎn)計劃應(yīng)重新制訂:如將x3的系數(shù)改為39.6計算，會發(fā)現(xiàn)結(jié)果有很大變化。B1獲利下降10%,超出X3系數(shù)允許范圍B2獲利上升10%,超出X4系數(shù)允許范圍奶制品的生產(chǎn)與銷售

線性規(guī)劃模型的三要素:決策變量、目標(biāo)函數(shù)、約束條件.用LINDO求解,輸出豐富,利用影子價格和靈敏性分析可對結(jié)果做進一步研究.建模時盡可能利用原始的數(shù)據(jù)信息,把盡量多的計算留給計算機去做.其他費用:450元/千噸

應(yīng)如何分配水庫供水量，公司才能獲利最多？若水庫供水量都提高一倍，公司利潤可增加到多少？元/千噸甲乙丙丁A160130220170B140130190150C190200230/引水管理費7.2自來水輸送收入:900元/千噸支出A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40水庫供水量(千噸)小區(qū)基本用水量(千噸)小區(qū)額外用水量(千噸)（以天計）總供水量:160確定送水方案使利潤最大問題分析A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40<總需求量:120+180=300總收入900160=144000(元)收入:900元/千噸其他費用:450元/千噸

支出引水管理費其他支出450160=72000(元)使引水管理費最小供應(yīng)限制約束條件需求限制

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

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

模型建立確定3個水庫向4個小區(qū)的供水量模型求解

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利潤=總收入-其他費用-引水管理費=144000-72000-24400=47600（元）

A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5040105010引水管理費24400(元)目標(biāo)函數(shù)

總供水量(320)>總需求量(300)每個水庫供水量提高一倍,利潤增加多少？利潤=收入(900)–其他費用(450)

–引水管理費利潤(元/千噸)甲乙丙丁A290320230280B310320260300C260250220/供應(yīng)限制B,C類似處理問題討論

確定送水方案使利潤最大需求約束可以不變求解OBJECTIVEFUNCTIONVALUE1)88700.00VARIABLEVALUEREDUCEDCOSTX110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000

X21

30.0000000.000000X2240.0000000.000000

X230.00000010.000000X2450.0000000.000000

X3150.0000000.000000X320.00000020.000000X3330.0000000.000000運輸問題A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030供應(yīng)點需求點物資供需平衡或不平衡總利潤88700(元)如何裝運，使本次飛行獲利最大？7.3貨機裝運

質(zhì)量（噸）空間(米3/噸）利潤（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850三個貨艙中實際載重必須與其最大載重成比例.前倉：10；6800中倉：16；8700后倉：8；5300飛機平衡貨艙最大載重(噸)貨艙最大容積(米3)目標(biāo)函數(shù)(利潤)約束條件貨艙質(zhì)量

10；680016；87008；5300xij--第i種貨物裝入第j個貨艙的質(zhì)量平衡要求

決策變量

約束條件xij--第i種貨物裝入第j個貨艙的質(zhì)量

質(zhì)量（噸）空間(米3/噸）利潤（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850貨艙容積

10；680016；87008；5300約束條件貨物供應(yīng)

xij--第i種貨物裝入第j個貨艙的質(zhì)量

質(zhì)量（噸）空間(米3/噸）利潤（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850

OBJECTIVEFUNCTIONVALUE1)121515.8VARIABLEVALUEREDUCEDCOSTX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000

X32

12.9473690.000000X33

3.0000000.000000X410.000000650.000000

X423.0526320.000000X430.000000650.000000貨物2:前倉10,后倉5；貨物3:中倉13,后倉3；貨物4:中倉3。模型求解最大利潤約121516元貨物~供應(yīng)點貨艙~需求點運輸問題如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計劃應(yīng)作何改變？汽車廠生產(chǎn)三種類型的汽車,已知各類型每輛車對鋼材、勞動時間的需求,利潤及工廠每月的現(xiàn)有量.

小型中型大型

現(xiàn)有量鋼材（噸）1.535600勞動時間（小時）28025040060000利潤（萬元）

234制訂月生產(chǎn)計劃,使工廠的利潤最大.7.4

汽車生產(chǎn)計劃設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3模型建立

小型中型大型現(xiàn)有量鋼材1.535600時間28025040060000利潤

234整數(shù)規(guī)劃模型(IP)IP可用LINDO直接求解“gin3”表示“前3個變量為整數(shù)”，等價于:ginx1ginx2ginx3IP的最優(yōu)解x1=64,x2=168,x3=0,最優(yōu)值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3<600280x1+250x2+400x3<60000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解

IP結(jié)果輸出對8個子模型逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解:方法1:分解為8個LP子模型若生產(chǎn)某類汽車,則至少生產(chǎn)80輛,求生產(chǎn)計劃.x1,x2,,x3=0或

80x1=80,x2=150,x3=0,最優(yōu)值z=610LINDO中對0-1變量的限定:inty1inty2inty3方法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)計劃.x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前

NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(如LINGO,MATLAB),但是其結(jié)果常依賴于初值的選擇.方法3:化為非線性規(guī)劃非線性規(guī)劃（Non-LinearProgramming,簡記NLP）若生產(chǎn)某類汽車,則至少生產(chǎn)80輛,求生產(chǎn)計劃.x1=0或

80x2=0或

80x3=0或

80汽車廠生產(chǎn)計劃

決策變量為整數(shù),建立整數(shù)規(guī)劃模型.對于類似于“x=0或80”這樣的條件,通常引入0-1變量處理,盡量不用非線性規(guī)劃.討論:丁的蛙泳成績退步到1’15”2；戊的自由泳成績進步到57”5,組成接力隊的方案是否應(yīng)該調(diào)整？如何選拔隊員組成4

100米混合泳接力隊?7.5混合泳接力隊的選拔

甲乙丙丁戊蝶泳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名候選人的百米成績窮舉法:組成接力隊的方案共有5!=120種.目標(biāo)函數(shù)若選擇隊員i參加泳姿j的比賽,記xij=1,否則記xij=00-1規(guī)劃模型

cij(秒)~隊員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人4,1,151L==?=jxiij模型求解

最優(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.457.5(秒),方案是否調(diào)整？敏感性分析新方案:乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP一般沒有與LP相類似的理論,LINDO輸出的敏感性分析結(jié)果通常是沒有意義的.最優(yōu)解:x21=x32=x43=x51=1,成績?yōu)?’17”7c43,c54的新數(shù)據(jù)重新輸入模型,用LINDO求解

原分配方案:甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.討論混合泳接力隊的選拔指派(Assignment)問題:有若干項任務(wù),每項任務(wù)必有且只能有一人承擔(dān)，每人只能承擔(dān)一項，不同人員承擔(dān)不同任務(wù)的效益(或成本)不同，怎樣分派各項任務(wù)使總效益最大(或總成本最小)?

人員數(shù)量與任務(wù)數(shù)量相等

人員數(shù)量大于任務(wù)數(shù)量(本例)

人員數(shù)量小于任務(wù)數(shù)量

?建立0-1規(guī)劃模型是常用方法

為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程？7.6選課策略要求至少選兩門數(shù)學(xué)課、三門運籌學(xué)課和兩門計算機課課號課名學(xué)分所屬類別先修課要求1微積分5數(shù)學(xué)

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

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

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

決策變量

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

xi=1~選修課號i的課程（xi=0~不選）

選修課程總數(shù)最少約束條件最少2門數(shù)學(xué)課,3門運籌學(xué)課,2門計算機課.課號課名所屬類別1微積分?jǐn)?shù)學(xué)2線性代數(shù)數(shù)學(xué)3最優(yōu)化方法數(shù)學(xué)；運籌學(xué)4數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué)；計算機5應(yīng)用統(tǒng)計數(shù)學(xué)；運籌學(xué)6計算機模擬計算機；運籌學(xué)7計算機編程計算機8預(yù)測理論運籌學(xué)9數(shù)學(xué)實驗運籌學(xué)；計算機先修課程要求最優(yōu)解:x1=x2=x3=x6=x7=x9=1,其他為0；6門課程，總學(xué)分21.0-1規(guī)劃模型

約束條件x3=1必有x1=x2=1模型求解（LINDO）

課號課名先修課要求1微積分

2線性代數(shù)

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

8預(yù)測理論應(yīng)用統(tǒng)計9數(shù)學(xué)實驗微積分；線性代數(shù)學(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門課程

.},{WZMin-多目標(biāo)規(guī)劃

在課程最少的前提下以學(xué)分最多為目標(biāo).最優(yōu)解:x1=x2=x3=x5=x7=x9=1,其他為0；總學(xué)分由21增至22.注意：最優(yōu)解不唯一！課號課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計46計算機模擬37計算機編程28預(yù)測理論29數(shù)學(xué)實驗3

LINDO不能告訴優(yōu)化問題的解是否唯一.可將x9=1易為x6=1增加約束，以學(xué)分最多為目標(biāo)求解.多目標(biāo)規(guī)劃

對學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個目標(biāo),如三七開.最優(yōu)解:x1=x2=x3=x4=x5=x6=x7=x9=1，其它為0；總學(xué)分28.課號課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計46計算機模擬37計算機編程28預(yù)測理論29數(shù)學(xué)實驗3

討論與思考最優(yōu)解與1=0,2=1的結(jié)果相同——學(xué)分最多.多目標(biāo)規(guī)劃

最優(yōu)解與1=1,2=0的結(jié)果相同——課程最少.

選課策略用0-1變量表示策略選擇是常用的方法

“要選甲(x1)必選乙(x2)”可用x1

x2描述.

“要選甲(x1)必不選乙(x2)”怎樣描述?

“甲乙二人至多選一人”怎樣描述?

“甲乙二人至少選一人”怎樣描述?雙(多)目標(biāo)規(guī)劃的處理方法

加權(quán)組合成一個新目標(biāo),化為單目標(biāo)規(guī)劃.

一個目標(biāo)作為約束,解另一個目標(biāo)的規(guī)劃.問題1.如何下料最節(jié)省?7.7鋼管下料問題2.客戶增加需求:原料鋼管:每根19米4米50根