數(shù)學(xué)建模《最優(yōu)化問題》

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

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

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

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

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

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

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

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

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

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

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

rT1tT注意:缺貨需補(bǔ)足Q

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

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

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

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

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

w=w(t)p=8-gt

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

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

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

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

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

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

t

t2,

降為

-x

(

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

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

/

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

,

為已知參數(shù)

c1,t1,

x

c3,

x

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

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

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

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

q/2~成本的一半

b~價(jià)格上升1單位時(shí)銷量的下降幅度（需求對(duì)價(jià)格的敏感度）

a~絕對(duì)需求(

p=0的需求)b

p*

a

p*

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

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

U(q1,q2)=c

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

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

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

,分別表示消費(fèi)者對(duì)甲乙兩種商品的偏愛程度.

購(gòu)買兩種商品費(fèi)用之比與二者價(jià)格無(wú)關(guān).

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

,

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

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

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

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

01000>400013500.10.300.150.45

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

105106107135

8.410.512.6

10.813.516.2

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

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

01000>400013500.10.300.150.45

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

105106107135

8.410.512.6

10.813.516.2

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

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

V05105

106107f(V0)4.06.28.0

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

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

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

模型來(lái)自實(shí)際問題的可行性研究.

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

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

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

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

3kgA1

12小時(shí)

8小時(shí)

4kgA2

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

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

1桶牛奶3kgA1

12小時(shí)8小時(shí)4kgA2

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

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

獲利24×3x1

獲利16×4x2

原料供應(yīng)

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

加工能力

決策變量

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

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

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

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

軟件實(shí)現(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，利潤(rùn)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三種資源“資源”剩余為零的約束為緊約束（有效約束）原料無(wú)剩余時(shí)間無(wú)剩余加工能力剩余40結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

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

聘用臨時(shí)工人付出的工資最多每小時(shí)幾元?2元！原料增加1單位,利潤(rùn)增長(zhǎng)48時(shí)間增加1單位,利潤(rùn)增長(zhǎng)2加工能力增長(zhǎng)不影響利潤(rùn)影子價(jià)格RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

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

YesA1獲利增加到30元/kg,應(yīng)否改變生產(chǎn)計(jì)劃?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影子價(jià)格有意義時(shí)約束右端的允許變化范圍35元可買到1桶牛奶,每天最多買多少?最多買10桶!目標(biāo)函數(shù)不變!原料最多增加10時(shí)間最多增加53原料時(shí)間例2奶制品的生產(chǎn)銷售計(jì)劃

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

12小時(shí)8小時(shí)4kgA2

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

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

12小時(shí)8小時(shí)4kgA2

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

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

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

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

加工能力

決策變量

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

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

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

基本模型模型求解

軟件實(shí)現(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每天利潤(rùn)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小時(shí)時(shí)間,應(yīng)否投資？現(xiàn)投資150元,可賺回多少？投資150元增加5桶牛奶,可賺回189.6元。(大于增加時(shí)間的利潤(rùn)增長(zhǎng))增加1桶牛奶使利潤(rùn)增長(zhǎng)3.16×12=37.92增加1小時(shí)時(shí)間使利潤(rùn)增長(zhǎng)3.26結(jié)果解釋B1,B2的獲利有10%的波動(dòng),對(duì)計(jì)劃有無(wú)影響?RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124.0000001.680000INFINITYX216.0000008.1500002.100000

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

……

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

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

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

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

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

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

模型建立確定3個(gè)水庫(kù)向4個(gè)小區(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利潤(rùn)=總收入-其他費(fèi)用-引水管理費(fèi)=144000-72000-24400=47600（元）

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

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

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

確定送水方案使利潤(rùn)最大需求約束可以不變求解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運(yùn)輸問題A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030供應(yīng)點(diǎn)需求點(diǎn)物資供需平衡或不平衡總利潤(rùn)88700(元)如何裝運(yùn)，使本次飛行獲利最大？7.3貨機(jī)裝運(yùn)

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

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

決策變量

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

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

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

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

質(zhì)量（噸）空間(米3/噸）利潤(rùn)（元/噸）貨物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:前倉(cāng)10,后倉(cāng)5；貨物3:中倉(cāng)13,后倉(cāng)3；貨物4:中倉(cāng)3。模型求解最大利潤(rùn)約121516元貨物~供應(yīng)點(diǎn)貨艙~需求點(diǎn)運(yùn)輸問題如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？汽車廠生產(chǎn)三種類型的汽車,已知各類型每輛車對(duì)鋼材、勞動(dòng)時(shí)間的需求,利潤(rùn)及工廠每月的現(xiàn)有量.

小型中型大型

現(xiàn)有量鋼材（噸）1.535600勞動(dòng)時(shí)間（小時(shí)）28025040060000利潤(rùn)（萬(wàn)元）

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

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

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

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

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

80x1=80,x2=150,x3=0,最優(yōu)值z(mì)=610LINDO中對(duì)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)計(jì)劃.x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前

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

80x2=0或

80x3=0或

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

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

100米混合泳接力隊(duì)?7.5混合泳接力隊(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名候選人的百米成績(jī)窮舉法:組成接力隊(duì)的方案共有5!=120種.目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽,記xij=1,否則記xij=00-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人4,1,151L==?=jxiij模型求解

最優(yōu)解:x14=x21=x32=x43=1,其它變量為0;成績(jī)?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,成績(jī)?yōu)?’17”7c43,c54的新數(shù)據(jù)重新輸入模型,用LINDO求解

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

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

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

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

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

為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程？7.6選課策略要求至少選兩門數(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í)哪些課程？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ù)測(cè)理論運(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é)分21.0-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ù)測(cè)理論應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)微積分；線性代數(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)解不唯一！課號(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

LINDO不能告訴優(yōu)化問題的解是否唯一.可將x9=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ù)測(cè)理論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é)果相同——課程最少.

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

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

x2描述.

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

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

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

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

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