數(shù)學建模

優(yōu)化模型介紹/sundae_meng引言---數(shù)學之重要……數(shù)學使人周密……----FrancisBacon

數(shù)學處于人類智能的中心領域……數(shù)學方法滲透、支配著一切自然科學的理論分支……它已愈來愈成為衡量成就的主要標志。

----vonNeumann

/sundae_meng引言---數(shù)學之重要

一門科學只有當它達到能夠成功地運用數(shù)學時，才算真正發(fā)展了。

----KarlMarxGalileo:

展現(xiàn)在我們眼前的宇宙像一本用數(shù)學語言寫成的大書，如不掌握數(shù)學符號語言，就像在黑暗的迷宮里游蕩，什么也認識不清。數(shù)學是一種語言，是一切科學的共同語言/sundae_meng引言---數(shù)學之重要數(shù)學是一種技術，是高技術的本質數(shù)學技術----數(shù)學方法與計算技術的結合形成的一種關鍵性的、可實現(xiàn)的技術二十世紀最偉大的數(shù)學家----二十世紀最偉大的物理學家----D.HilbertA.EinsteinGoback諾貝爾獎菲爾茲獎/sundae_meng1.什么是數(shù)學模型？

數(shù)學模型是對于現(xiàn)實世界的一個特定對象，一個特定目的，根據(jù)特有的內在規(guī)律，做出一些必要的假設，運用適當?shù)臄?shù)學工具，得到一個數(shù)學結構．簡單地說：就是系統(tǒng)的某種特征的本質的數(shù)學表達式（或是用數(shù)學術語對部分現(xiàn)實世界的描述），即用數(shù)學式子（如函數(shù)、圖形、代數(shù)方程、微分方程、積分方程、差分方程等）來描述（表述、模擬）所研究的客觀對象或系統(tǒng)在某一方面的存在規(guī)律．/sundae_meng2.什么是數(shù)學建模?

數(shù)學建模是利用數(shù)學方法解決實際問題的一種實踐．即通過抽象、簡化、假設、引進變量等處理過程后，將實際問題用數(shù)學方式表達，建立起數(shù)學模型，然后運用先進的數(shù)學方法及計算機技術進行求解．觀點：“所謂高科技就是一種數(shù)學技術”/sundae_meng

數(shù)學建模其實并不是什么新東西，可以說有了數(shù)學并需要用數(shù)學去解決實際問題，就一定要用數(shù)學的語言、方法去近似地刻畫該實際問題，這種刻劃的數(shù)學表述的就是一個數(shù)學模型，其過程就是數(shù)學建模的過程．數(shù)學模型一經提出，就要用一定的技術手段（計算、證明等）來求解并驗證，其中大量的計算往往是必不可少的，高性能的計算機的出現(xiàn)使數(shù)學建模這一方法如虎添翼似的得到了飛速的發(fā)展，掀起一個高潮．

數(shù)學建模將各種知識綜合應用于解決實際問題中，是培養(yǎng)和提高同學們應用所學知識分析問題、解決問題的能力的必備手段之一./sundae_meng數(shù)學建模參考書1.《數(shù)學模型》姜啟源、謝金星、葉俊編高等教育出版社2.《數(shù)學建模方法及其應用》解放軍信息工程大學韓中庚編高教社3.《數(shù)學模型與數(shù)學建?！穭砀！⒃乃嚲幹睅煷蟪霭嫔?.葉其孝等，《大學生數(shù)學建模競賽輔導教材（一）~（四）》，湖南教育出版社

5.趙靜等，《數(shù)學建模與數(shù)學實驗》，高等教育出版社，施普林格出版社/sundae_meng

規(guī)劃模型的應用極其廣泛，其作用已為越來來越急速地滲透于工農業(yè)生產、商業(yè)活動、軍事行為科學研究的各個方面，為社會節(jié)省的財富、創(chuàng)造的價值無法估量.

特別是在數(shù)模競賽過程中，規(guī)劃模型是最常見的一類數(shù)學模型.從92-06年全國大學生數(shù)模競越多的人所重視.隨著計算機的逐漸普及，它越賽試題的解題方法統(tǒng)計結果來看，規(guī)劃模型共出現(xiàn)了15次，占到了50%，也就是說每兩道競賽題中就有一道涉及到利用規(guī)劃理論來分析、求解.

/sundae_meng

優(yōu)化問題，一般是指用“最好”的方式，使用或分配有限的資源，即勞動力、原材料、機器、資金等，使得費用最小或者利潤最大。優(yōu)化模型/sundae_mengminf(x)

--------目標函數(shù)

s.t.x

S

------約束集合，可行集其中，S

Rn，f:S

R，x

S稱（fS)的可行解最優(yōu)解:x*

S，滿足f(x*)≤f(x),x

S。則稱

x*為(fS)的全局最優(yōu)解(最優(yōu)解),

記g.opt.(globaloptimum),簡記opt.最優(yōu)值:x*為(fS)的最優(yōu)解,則稱f*=f(x*)

為

(fS)的最優(yōu)值(最優(yōu)目標函數(shù)值)數(shù)學規(guī)劃模型的一般形式(fS)/sundae_meng局部最優(yōu)解:x*

S，

x*的鄰域N(x*)，使?jié)M足

f(x*)≤f(x),x

S

N(x*)

。則稱x*為(fS)的局部最優(yōu)解,記l.opt.(localoptimum)在上述定義中，當x

x*時有嚴格不等式成立，則分別稱x*

為(fS)的嚴格全局最優(yōu)解和嚴格局部最優(yōu)解。嚴格l.opt.嚴格g.opt.l.opt./sundae_meng數(shù)學規(guī)劃模型的一般形式函數(shù)形式:

f(x),gi(x),hj(x):RnRminf(x)(fgh)s.t.gi(x)

≤0,i=1,2,…,m

hj(x)=0,j=1,2,…,l矩陣形式:minf(x)，f(x)

:Rn

R(fgh)s.t.g(x)

≤0,g(x):Rn

Rm

h(x)=0,h(x):Rn

Rl

當f(x),gi(x),hj(x)均為線性函數(shù)時，稱線性規(guī)劃；若其中有非線性函數(shù)時，稱非線性規(guī)劃。/sundae_meng優(yōu)化模型的簡單分類

線性規(guī)劃(LP)

目標和約束均為線性函數(shù)

非線性規(guī)劃(NLP)

目標或約束中存在非線性函數(shù)

二次規(guī)劃(QP)

目標為二次函數(shù)、約束為線性

整數(shù)規(guī)劃(IP)

決策變量(全部或部分)為整數(shù)整數(shù)線性規(guī)劃(ILP)，整數(shù)非線性規(guī)劃(INLP)

純整數(shù)規(guī)劃(PIP),混合整數(shù)規(guī)劃(MIP)

一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃連續(xù)優(yōu)化離散優(yōu)化數(shù)學規(guī)劃/sundae_meng優(yōu)化模型的簡單分類和求解難度優(yōu)化線性規(guī)劃非線性規(guī)劃二次規(guī)劃連續(xù)優(yōu)化整數(shù)規(guī)劃問題求解的難度增加

/sundae_meng

線性規(guī)劃LinearProgramming/sundae_meng問題一：

任務分配問題：某車間有甲、乙兩臺機床，可用于加工三種工件.假定這兩臺車床的可用臺時數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表.問怎樣分配車床的加工任務，才能既滿足加工工件的要求，又使加工費用最低？

兩個引例/sundae_meng建立線性規(guī)劃模型的基本步驟：（1）設出決策變量

（2）確定目標函數(shù)（3）確定約束條件找出待定的未知變量（決策變量），并用代數(shù)符號表示找到模型的目標或判據(jù)，寫成決策變量的線性函數(shù)，以便求出其最大值或最小值

找出問題的所有的限制或約束，寫出未知變量的線性方程或線性不等式/sundae_meng解

設在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6,可建立以下線性規(guī)劃模型：

解答/sundae_meng問題二：某廠每日8小時的產量不低于1800件.為了進行質量控制，計劃聘請兩種不同水平的檢驗員.一級檢驗員的標準為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標準為：速度15件/小時，正確率95%，計時工資3元/小時.檢驗員每錯檢一次，工廠要損失2元.為使總檢驗費用最省，該工廠應聘一級、二級檢驗員各幾名？解設需要一級和二級檢驗員的人數(shù)分別為x1、x2人,則應付檢驗員的工資為：因檢驗員錯檢而造成的損失為：/sundae_meng故目標函數(shù)為：約束條件為：/sundae_meng線性規(guī)劃模型：

解答返回/sundae_meng模型特點：目標函數(shù)(Objectivefunction)與約束條件(Constraint)均為線性的；目標函數(shù)實現(xiàn)極大化或極小化。線性規(guī)劃問題的一般形式：Max(Min)S=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn

(=,

)b1a21x1+a22x2+….+a2nxn

(=,

)b2

….am1x1+am2x2+….+amnxn

(=,

)bmx1,x2….xn

0/sundae_meng線性規(guī)劃的基本概念1.可行解(FeasibleSolution)——任一滿足約束條件的一組決策變量的數(shù)值.2.可行域(FeasibleRegion)——所有可行解組成的集合，也稱為可行解集.3.目標函數(shù)等值線(Objectivefunctionline)——為于同一直線上的點，具有相同的目標函數(shù)值./sundae_meng線性規(guī)劃模型的解的幾種情況線性規(guī)劃問題有可行解(Feasible)無可行解（Infeasible）有最優(yōu)解（Optimal）無最優(yōu)解(Unbounded)/sundae_meng

數(shù)學建模中線性規(guī)劃模型的常用解法線性規(guī)劃問題的求解在理在理論上有單純型法，在實際建模中常用以下解法：1.圖解法2.LINGO軟件包3.Excel中的規(guī)劃求解4.MATLAB軟件包主要介紹線性規(guī)劃模型的MATlAB軟件包和LINGO軟件包解法/sundae_meng模型求解方法1.圖解法例1max

z=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0

該問題的最優(yōu)解為x1=50；x2=250x2z*=50x1+100x2=27500x1+x2≤300x1x2≤2502x1+x2≤400z1=50x1+100x2=0BOACDz2=14000/sundae_meng用MATLAB優(yōu)化工具箱解線性規(guī)劃minz=cX

1.模型：命令：x=linprog（c,A,b）

2.模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式：存在，則令A=[]，b=[].式中：linprog稱為調用函數(shù)，C,A,b稱為輸入參數(shù)，全部由用戶提供，必須按規(guī)定的位置放置在原括號內./sundae_meng3.模型：minz=cX

VLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）

[2]

x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）

注意：[1]若沒有等式約束:,則令Aeq=[],beq=[].[2]其中X0表示初始點,設置它有些情況下可以減少迭代工作量4.命令：[x,fval]=linprog(…)返回最優(yōu)解ｘ及ｘ處的目標函數(shù)值fval./sundae_meng解編寫M文件xxgh1.m如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];

A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];

b=[850;700;100;900];

Aeq=[];beq=[];

vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)

C:/Documents%20and%20Settings/Administrator/%E6%A1%8C%E9%9D%A2/%E6%95%B0%E5%AD%A6%E6%A8%A1%E5%9E%8B/%E6%95%B0%E5%AD%A6%E5%BB%BA%E6%A8%A1%E4%B8%8E%E6%95%B0%E5%AD%A6%E5%AE%9E%E9%AA%8C%EF%BC%88%E7%AC%AC3%E7%89%88%EF%BC%89/%E7%AC%AC4%E8%AE%B2%20%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92/xxgh1.m/sundae_meng解:編寫M文件xxgh2.m如下：

c=[634];A=[010];b=[50];Aeq=[111];beq=[120];vlb=[30,0,20];vub=[];

[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh2)/sundae_mengs.t.改寫為：例3問題一的解答

問題/sundae_meng編寫M文件xxgh3.m如下:f=[1391011128];A=[0.41.110000000.51.21.3];b=[800;900];Aeq=[100100010010001001];beq=[400600500];vlb=zeros(6,1);vub=[];[x,fval]=linprog(f,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh3)/sundae_meng結果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004

即在甲機床上加工600個工件2,在乙機床上加工400個工件1、500個工件3，可在滿足條件的情況下使總加工費最小為13800./sundae_meng例2問題二的解答

問題改寫為：/sundae_meng編寫M文件xxgh4.m如下：c=[4036];A=[-5-3];b=[-45];Aeq=[];beq=[];vlb=zeros(2,1);vub=[915];%調用linprog函數(shù)：[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh4)/sundae_meng結果為：x=9.00000.0000fval=360即只需聘用9個一級檢驗員.

注：本問題應還有一個約束條件：x1、x2取整數(shù).故它是一個整數(shù)線性規(guī)劃問題.這里把它當成一個線性規(guī)劃來解，求得其最優(yōu)解剛好是整數(shù)：x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解.若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應用專門的方法求解.返回/sundae_meng用LINDO、LINGO優(yōu)化工具箱解線性規(guī)劃LINDO公司軟件產品簡要介紹

美國芝加哥(Chicago)大學的LinusSchrage教授于1980年前后開發(fā),后來成立LINDO系統(tǒng)公司（LINDOSystemsInc.），網址：

LINDO:LinearINteractiveandDiscreteOptimizer(V6.1)LINGO:LinearINteractiveGeneralOptimizer(V8.0)LINDOAPI:LINDOApplicationProgrammingInterface(V2.0)What’sBest!:(SpreadSheete.g.EXCEL)(V7.0)演示(試用)版、學生版、高級版、超級版、工業(yè)版、擴展版…（求解問題規(guī)模和選件不同）/sundae_mengLINDO和LINGO軟件能求解的優(yōu)化模型LINGOLINDO優(yōu)化模型線性規(guī)劃(LP)非線性規(guī)劃(NLP)二次規(guī)劃(QP)連續(xù)優(yōu)化整數(shù)規(guī)劃(IP)/sundae_meng一、LINDO軟件包

下面我們通過一個例題來說明LINDO軟件包的使用方法./sundae_meng問題：一奶制品加工廠用牛奶生產A1,A2兩種奶制品，一桶牛奶可以在甲類設備上用12小時生產成3公斤A1，或者在乙類設備上用8小時加工成4公斤A2.據(jù)市場要求，生產的兩種奶制品全部能售出，且每公斤A1獲利24元，每公斤A2獲利16元，現(xiàn)在每天加工廠每天能得到50桶牛奶的供應，每天正式工人總的勞動時間為480小時，并且甲類設備每天至多能加工100公斤A1，乙類設備的加工能力沒有限制.試為該廠制定一個生產計劃，使每天獲利最大，并進一步討論以下3個附加問題。1）若用35元可以買到1桶牛奶，應否作這樣的投資？若投資，每天最多購買多少桶牛奶2）若可以聘用臨時工人以增加勞動時間，付給臨時工人的工資最多是每小時幾元？3）由于市場需求變化，每公斤A1的獲利增加到30元，應否改變生產計劃？/sundae_meng1桶牛奶3kgA1

12小時8小時4kgA2

或獲利24元/kg獲利16元/kgx1桶牛奶生產A1

x2桶牛奶生產A2

獲利24×3x1

獲利16×4x2

原料供應

勞動時間

加工能力

決策變量

目標函數(shù)

每天獲利約束條件非負約束

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

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

圖解法

x1x20ABCDl1l2l3l4l5約束條件目標函數(shù)

z=0z=2400z=3600z

=c(常數(shù))~等值線c在B(20,30)點得到最優(yōu)解目標函數(shù)和約束條件是線性函數(shù)可行域為直線段圍成的凸多邊形目標函數(shù)的等值線為直線最優(yōu)解一定在凸多邊形的某個頂點取得。/sundae_meng模型求解

軟件實現(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桶牛奶生產A1,30桶生產A2，利潤3360元。/sundae_meng結果解釋

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/sundae_meng結果解釋

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,應該買！

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

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

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

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

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

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價格有意義時約束右端的允許變化范圍35元可買到1桶牛奶,每天最多買多少?最多買10桶!目標函數(shù)不變!原料最多增加10時間最多增加53原料時間/sundae_meng模型求解

reducedcost值表示當該非基變量增加一個單位時（其他非基變量保持不變）,目標函數(shù)減少的量(對max型問題).OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解為：為了使該非基變量變成基變量，目標函數(shù)中對應系數(shù)應增加的量/sundae_meng1.使用LINDO的一些注意事項？“>”（或“<”）號與“>=”（或“<=”）功能相同變量與系數(shù)間可有空格(甚至回車),但無運算符變量名以字母開頭，不能超過8個字符變量名不區(qū)分大小寫（包括LINDO中的關鍵字）目標函數(shù)所在行是第一行，第二行起為約束條件行號(行名)自動產生或人為定義.行名以“）”結束行中注有“!”符號的后面部分為注釋.如:

!It’sComment.在模型的任何地方都可以用“TITLE”對模型命名（最多72個字符），如：

TITLEThisModelisonlyanExample/sundae_meng變量不能出現(xiàn)在一個約束條件的右端表達式中不接受括號“()”和逗號“,”等任何符號,例:400(X1+X2)需寫為400X1+400X2表達式應化簡，如2X1+3X2-4X1應寫成-2X1+3X2缺省假定所有變量非負；可在模型的“END”語句后用“FREEname”將變量name的非負假定取消可在“END”后用“SUB”或“SLB”設定變量上下界例如：“subx110”的作用等價于“x1<=10”

但用“SUB”和“SLB”表示的上下界約束不計入模型的約束，也不能給出其松緊判斷和敏感性分析.14.“END”后對0-1變量說明：INTn

或INTname15.“END”后對整數(shù)變量說明：GINn

或GINname

使用LINDO的一些注意事項/sundae_meng2.狀態(tài)窗口（LINDOSolverStatus）當前狀態(tài)：已達最優(yōu)解迭代次數(shù)：18次約束不滿足的“量”(不是“約束個數(shù)”)：0當前的目標值：94最好的整數(shù)解：94整數(shù)規(guī)劃的界：93.5分枝數(shù)：1所用時間：0.00秒（太快了，還不到0.005秒）刷新本界面的間隔:1(秒)/sundae_meng二、LINGO軟件包/sundae_meng(1)LINGO模型的優(yōu)點1.LINGO軟件簡介(2)對簡單的LINGO程序LINGO也可以和LINDO一樣編程但LINGO與LINDO語法有差異提供了靈活的編程語言（矩陣生成器）包含了LINDO的全部功能/sundae_mengLindo與簡單Lingo程序的比較Model:

min=7*x1+3*x2;

x1+x2>=345.5;

x1>=98;

2*x1+x2<=600;

@gin(x1);

@gin(x2);

endmin7x1+3x2stx1+x2>=345.5x1>=982*x1+x2<=600endgin2lindo程序:lingo程序:/sundae_meng實驗作業(yè)

某廠生產甲乙兩種口味的飲料,每百箱甲飲料需用原料6千克,工人10名,可獲利10萬元;每百箱乙飲料需用原料5千克,工人20名,可獲利9萬元.今工廠共有原料60千克,工人150名,又由于其他條件所限甲飲料產量不超過800箱.問如何安排生產計劃,即兩種飲料各生產多少使獲利最大.進一步討論:1)若投資0.8萬元可增加原料1千克,問應否作這項投資.2)若每100箱甲飲料獲利可增加1萬元,問應否改變生產計劃.返回/sundae_meng運輸問題

---TransportationProblem運輸問題(TransportationProblem)

以知有m個生產地點(source)Ai，i=1，…，m，可供應某種物資，其供應量（產量）(supply)為ai，i=1，…，m；有n個銷售地點(destination)Bj，j=1，…，n，需要該種物資，其需要量（產量）(demand)為bj，j=1，…，n；從Ai到Bj運輸單位物資的運價（單價）為cij；設Σai=Σbj，這些數(shù)據(jù)可匯總于如下產銷平衡表，現(xiàn)要制定一個使總運費最小的調運方案。/sundae_meng

銷地產地B1B2…Bn產量A1c11c12…c1na1A2c21c22…c2na2………………Amcm1cm2…cmnam銷量b1b2…bnΣaiΣbj產銷平衡表(costandrequirementtable)/sundae_meng若用xij表示從Ai到Bj的運量，在產銷平衡的條件下，要求得總運費最小的調運方案，其數(shù)學模型如下（模型Y）/sundae_meng產銷不平衡的運輸問題

----TotalSupplynotEqualtoTotalDemand一、產大于銷(totalsupplyexceedstotaldemand)產大于銷的運輸問題的特征是Σai>Σbj，其數(shù)學模型為：/sundae_meng解此類問題可假想一個銷地Bn+1，其需要量為：bn+1=Σai－Σbj；若用xi，n+1表示從Ai到Bn+1的運量，可令ci，n+1=0或等于第Ai產地儲存單位物資的費用。因為xi，n+1實際上表示Ai產地沒有運出去而庫存的物資數(shù)量。經處理后，問題變成了產銷平衡的運輸問題，其數(shù)學模型為：這樣，m個產地、n個銷地的不平衡運輸問題，轉化成了m個產地、n+1個銷地的平衡運輸問題，此時可用表上作業(yè)法求解。/sundae_meng二、銷大于產(totaldemandexceedstotalsupply)銷大于產的運輸問題的特征是Σai<Σbj，其數(shù)學模型為：/sundae_meng解此問題可假想一個產地Am+1，其產量為：am+1=

Σbj－Σai；若用xm+1，j表示從Am+1到Bj的運量，可令cm+1，j=0或等于第Bj產地每缺單位物資的損失。因為xm+1，j實際上表示Bj銷地所缺的物資數(shù)量。經處理后，問題變成了產銷平衡的運輸問題，其數(shù)學模型為：此時，可用表上作業(yè)法求解。/sundae_meng例某公司有6個供貨棧（倉庫），庫存貨物總數(shù)分別為60，55，51，43，41，52，現(xiàn)有8個客戶各要一批貨數(shù)量分別為35，37，22，32，41，32，43，38，各供貨棧道8個客戶的單位貨物運輸價見表供貨棧到客戶的單位貨物運價客戶貨棧V1V2V3V4V5V6V7V8W162674259W249538582W352197433W476739271W523957265W655228143試確定各貨棧到各客戶處的貨物調運數(shù)量，使總的運輸費用最小。/sundae_meng解引入決策變量代表從第個貨棧到第個客戶的貨物運量.設表示從第個貨棧到第個客戶的單位貨物運價表示第個貨棧的最大供貨量,表示第個客戶的訂貨量.目標函數(shù)是總運輸費用最少.約束條件有三條：1.各貨棧運出的貨物總量不超過其庫存數(shù)

2.各客戶收到的貨物總量等于其訂貨數(shù)量3.決策變量非負數(shù)學模型為/sundae_meng

前面介紹的LinGO的基本用法，其優(yōu)點是輸入模型較直觀，一般的數(shù)學表達式無需作大的變換即可直接輸入.對于規(guī)模較小的的規(guī)劃模型，用直接輸入的方法是有利的，如果模型的變量和約束的條件個數(shù)比較多，若仍然用直接的輸入方式，雖然也能求解并得到結果，但這種做法有明顯的不足之處。模型的篇幅很長，不便于分析修改和擴展。

LinGO建模語言引入集合的概念，為建立大規(guī)模的數(shù)學規(guī)劃模型提供了方便.用LinGO語言表達一個實際優(yōu)化問題，稱之為LinGO模型。

一、集合定義部分

集合是一組相關對象構成的組合，代表模型中的實際事物，并與數(shù)學變量與常量聯(lián)系起來，是實際問題到數(shù)學的抽象。例中的6個倉庫可以看成一個集合，8個客戶可以看成另一個集合。/sundae_meng

每個集合在使用之前需要預先給出定義，定義集合時要明確三方面的內容：集合的名稱，集合內的成員（元素）、集合的屬性（可以看成與該集合有關的變量或常量，相當于數(shù)組）.本例首先定義倉庫集合：WH/W1..W6/:AI;

其中WH是集合的名稱，W1..W6是集合內的成員，“..”是特定的省略號（如果不用該省略號，也可以把成員一一羅列出來，成員之間用逗號或空格分開),表明該集合有6個成員，分別對應于6個供貨棧，AI是集合的屬性，它可以看成是一個數(shù)組，有6個分量，分別表示各貨棧現(xiàn)有貨物的總數(shù)。集合、成員、屬性的命名規(guī)則與變量相同，可按自己的意愿，用有一定意義的字母數(shù)串來表示，式中“/”和“/:”是規(guī)定的語法規(guī)則。本例再定義客戶集合：VD/V1..V8/:DJ;該集合有8個成員，DJ是集合的屬性（有8個分量）表示各客戶的需求量.以上兩個集合稱為初始集合（或稱基本集合、原始集合）初始集合的屬性都相當于一維數(shù)組。/sundae_meng為表示數(shù)學模型中從貨棧到客戶的運輸關系以及與此相關的運輸單價和運量再定義一個表示運輸關系的集合：LINKS(WH,VD):C,X;該集合以初始集合WH和VD為基礎，稱為衍生集合（或稱派生集合）.C和X是該衍生集合的兩個屬性，衍生集合的定義語句有如下要素組成：1）集合的名稱；

(2)集合的初始集合；（3）集合的成員（可以省略不寫）；（4）集合的屬性（可以沒有）

定義衍生集合時可以用羅列的方式將衍生集合成員一一列舉出來，如果省略不寫，則默認衍生集合的成員取它所對應初始集合的所有可能組合，上述衍生集合LINKS的定以中沒有指明成員，則它對應的初始集合WH有6個成員，VD有8個成員，因此LINKS成員取WH和VD的所有可能組合，即有48個成員，48個成員可以排列成一個矩陣。其行數(shù)與集合WH的成員個數(shù)相等，列數(shù)與集合VD成員的個數(shù)相等.相應地，集合LINKS的屬性Ｃ和Ｘ都相當于二維數(shù)組，各有48個分量，Ｃ表示貨棧Ｗi到客戶Vj的單位貨物運價

X表示貨棧Wi到客戶Vj的貨物運量./sundae_meng本模型完整的集合定義為：SETS:WH/W1..W6/:AI;VD/V1..V8/DJ;LINKS(WH,VD):C,X;ENDSETS注：集合定義部分以語句SETS:開始，以ENDSETS語句結束，這兩個語句需單獨成一行，ENDSETS后面不加標點符號.二、數(shù)據(jù)初始化（數(shù)據(jù)段）

以上集合中屬性X（有48個分量）是決策變量，是待求的未知數(shù)，屬性AI、DJ和Ｃ（分別有６,8,48個分量）都是已知數(shù)，LINKS建模語言通過數(shù)據(jù)初始化部分來實現(xiàn)對已知屬性賦以初始值，格式為：DATA:AI=60,55,51,43,41,52;DJ=35,37,22,32,41,32,43,38;C=6,2,6,7,4,2,5,94,9,5,3,8,5,8,25,2,1,9,7,4,3,37,6,7,3,9,2,7,12,3,9,5,7,2,6,55,5,2,2,8,1,4,3;ENDDATA注：數(shù)據(jù)初始化部分以語句DATA:開始，以ENDDATE語句結束，這兩個語句需單獨成一行，數(shù)據(jù)之間的逗號和空格可以互換。/sundae_meng三、目標函數(shù)和約束條件目標函數(shù)表達式

用LINGO語句表示為MIN=@SUM(LINKS(I,J):C(I,J)*X(I,J));

式中，@SUM是LINGO提供的內部函數(shù)，其作用是對某個集合的所有成員求制定表達式的和，該函數(shù)需要兩個參數(shù)，第一個參數(shù)是集合名稱，制定對該集合的所有成員求和，如果此集合是一個初始集合，它有m個成員，則求和運算對m個成員進行，相當于求，第二個參數(shù)是一個表達式，表示求和運算對該表達式進行，此處，@SUM的第一個參數(shù)是LINKS（I，J），表示求和運算對LINKS進行，該集合的維數(shù)為2，共有48個成員，運算規(guī)則是：先對48個成員分別求表達式C(I,J)*X(I,J)的值，然后求和，相當于求，表達式中的C和X是集合的兩個屬性，它們各有48個分量。注：如果表達式中參與酸的屬性屬于同一個集合，則語句中索引（相當于矩陣或數(shù)組的下標可以省略）（隱藏），假如表達式中參與運算的屬性屬于不同的集合，則不能省略屬性的索引.本例的目標函數(shù)可以表示成MIN=@SUM(LINKS:C*X);/sundae_meng約束條件用ＬINGO語言描述該約束條件，語句為：@FOR(WH(I):@SUM(VD(J):X(I,J))<=AI(I));語句中的@FOR是LINGO提供的內部函數(shù)，它的作用是對某個集合的所有成員分別生成一個約束表達式，它有兩個參數(shù)，第一個參數(shù)是集合名，表示對該集合的所有成員生成對應的約束表達式，上式@FOR的第一個參數(shù)為ＷＨ，它表示貨棧，共有６個成員，故應生成６個約束表達式，@FOR的第二個參數(shù)是約束表達式的具體內容，此處再調用@SUM函數(shù)，表示該約束的左邊是求和，是對集合ＶＤ的８個成員，并且對表達式Ｘ(I,J)中的第二維J求和，即約束表達式的右邊是集合ＷＨ的屬性AI，它有6個分量，與6個約束表達式一一對應，本句中的屬性分別屬于不同的集合，所以不能省略I,J.約束條件表示為@FOR(D(J)):@SUM(VD(J):X(I,J))=DJ(J));/sundae_meng完整的模型MODEL:SETS:WH/W1..W6/:AI;VD/V1..V8/:DJ;LINKS(WH,VD):C,X;ENDSETSDATA:AI=60,55,51,43,41,52;DJ=35,37,22,32,41,32,43,38;C=6,2,6,7,4,2,5,94,9,5,3,8,5,8,25,2,1,9,7,4,3,37,6,7,3,9,2,7,12,3,9,5,7,2,6,55,5,2,2,8,1,4,3;ENDDATAMIN=@SUM(LINKS(I,J):C(I,J)*X(I,J));!目標函數(shù)@FOR(WH(I):@SUM(VD(J):X(I,J))<=AI(I));!約束條件@FOR(VD(J):@SUM(VD(J):X(I,J))=DJ(J));END以“MODEL：”開始集合定義部分從(“SETS：”到“ENDSETS”)：定義集合及其屬性以“END”結束給出優(yōu)化目標和約束集合定義部分從(“DATA：”到“ENDDATA”)/sundae_meng整數(shù)規(guī)劃

-----IntegerProgramming,IP整數(shù)規(guī)劃（IntegerProgramming）主要是指整數(shù)線性規(guī)劃。一個線性規(guī)劃問題，如果要求部分決策變量為整數(shù)，則構成一個整數(shù)規(guī)劃問題。所有變量都要求為整數(shù)的稱為純整數(shù)規(guī)劃（PureInteger

Programming）或稱全整數(shù)規(guī)劃（AllintegerProgramming）；僅有一部分變量要求為整數(shù)的稱為混合整數(shù)規(guī)劃（MixedIntegerProgramming）；有的變量限制其取值只能為0或1，這類特殊的整數(shù)規(guī)劃稱為0－1規(guī)劃(0-1

IntegerProgramming)/sundae_meng整數(shù)規(guī)劃問題及其數(shù)學模型例某工廠生產甲、乙兩種設備，已知生產這兩種設備需要消耗材料A、材料B，有關數(shù)據(jù)如下，問這兩種設備各生產多少使工廠利潤最大？設備材料甲乙資源限量材料A（kg）2314材料B（kg）10.54.5利潤（元/件）32

/sundae_meng解：設生產甲、乙這兩種設備的數(shù)量分別為x1、x2，由于是設備臺數(shù)，則其變量都要求為整數(shù)，建立模型如下：Maxz=3x1+2x22x1+3x2≤14x1+0.5x2≤4.5x1、x2≥0,且為整數(shù)圖4－1/sundae_meng要求該模型的解，不考慮整數(shù)約束條件，用圖解法對相應線性規(guī)劃求解，其最優(yōu)解為：x1＝3.25x2＝2.5maxz＝14.75----湊整得到的（4，2）不在可行域范圍內。--（3，2）點盡管在可行域內，但沒有使目標達到極大化。--（4，1）使目標函數(shù)達到最大，即z＝14。IP可用LINDO直接求解max3x1+2x2st2x1+3x2<14x1+0.5x2<4.5endgin2“gin2”表示“前2個變量為整數(shù)”，等價于：ginx1ginx2其中“GIN2”表示2個變量都是一般整數(shù)變量。

（仍然默認為取值是非負的）/sundae_mengLINDO可用于求解線性純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃(IP)，模型的輸入與LP問題類似,但需在END標志后定義整型變量。0/1型的變量可由INTEGER（可簡寫為INT）命令來標識，有以下兩種可能的用法：

INTvname

INTn前者只將決策變量vname標識為0/1型,后者將當前模型中前n個變量標識為0/1型（模型中變量順序由模型中輸入時出現(xiàn)的先后順序決定,該順序可由輸出結果中的變量順序查證是否一致）。一般的整數(shù)變量可用命令GIN（是GENERALINTEGER的意思）,其使用方式及格式與INT命令相似。。/sundae_mengSETX2TO<=2AT1,BND=14.50TWIN=13.507SETX1TO>=4AT2,BND=14.00TWIN=13.0010NEWINTEGERSOLUTIONOF14.0000000ATBRANCH2PIVOT10BOUNDONOPTIMUM:14.00000DELETEX1ATLEVEL2DELETEX2ATLEVEL1ENUMERATIONCOMPLETE.BRANCHES=2PIVOTS=10LASTINTEGERSOLUTIONISTHEBESTFOUNDRE-INSTALLINGBESTSOLUTION...OBJECTIVEFUNCTIONVALUE1)14.00000VARIABLEVALUEREDUCEDCOSTX14.000000-3.000000X21.000000-2.000000ROWSLACKORSURPLUSDUALPRICES2)3.0000000.0000003)0.0000000.000000NO.ITERATIONS=10BRANCHES=2DETERM.=1.000E0最優(yōu)值松弛和剩余變量（SLACKORSURPLUS）仍然可以表示約束的松緊程度，但目前IP尚無相應完善的敏感性分析理論，因此REDUCEDCOST和DUALPRICES的結果在整數(shù)規(guī)劃中意義不大。

/sundae_meng例2、集裝箱運貨

貨物體積(米3/箱)重量(百公斤/箱)利潤(千元/箱)

甲5220

乙4510

裝運限制2413/sundae_meng解：設X1,X2為甲、乙兩貨物各托運箱數(shù)5X1+4X2

242X1+5X2

13X1,X20X1,X2為整數(shù)maxZ=20X1+

10X2/sundae_meng例3、背包問題背包可裝入8單位重量，10單位體積物品物品名稱重量體積價值

1書52202攝像機31303枕頭14104休閑食品23185衣服4515/sundae_meng解：Xi為是否帶第i種物品maxZ=20X1+

30X2+10X3+18X4+15X55X1+3X2+X3+2X4+4X5

82X1+X2+4X3+3X4+5X510Xi為0,1Model:Min=-(20*x1+30*x2+10*x3+18*x4+15*x5);5*x1+3*x2+x3+2*x4+4*x5<8;2*x1+x2+4*x3+2*x4+5*x5<10;@bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);ENDModel:Lingo求解/sundae_mengGlobaloptimalsolutionfound.Objectivevalue:-58.00000Extendedsolversteps:0Totalsolveriterations:0VariableValueReducedCostX10.000000-20.00000X21.000000-30.00000X31.000000-10.00000X41.000000-18.00000X50.000000-15.00000RowSlackorSurplusDualPrice1-58.00000-1.00000022.0000000.00000033.0000000.000000/sundae_meng0－1整數(shù)規(guī)劃用(Applications)（一）相互排斥的計劃(Mutuallyexclusiveplanning)例4.6某公司擬在市東、西、南三區(qū)中建立門市部，有7個點Ai（i＝1，2，…，7）可供選擇，要求滿足以下條件：（1）在東區(qū)，在A1，A2，A3三個點中至多選兩個；（2）在西區(qū)，A4，A5兩個點中至少選一個；（3）在南區(qū)，A6，A7兩個點為互斥點。（4）選A2點必選A5點。若Ai點投資為bi萬元，每年可獲利潤為ci萬元，投資總額為B萬元，試建立利潤最大化的0－1規(guī)劃模型。/sundae_meng解：設決策變量為建立0－1規(guī)劃模型如下：/sundae_meng（二）相互排斥的約束條件(Mutuallyexclusiveconstraints)例4.7某產品有A1和A2兩種型號，需要經過B1、B2、B3三道工序，單位工時和利潤、各工序每周工時限制見表所示，問工廠如何安排生產，才能使總利潤最大？（B3工序有兩種加工方式B31和B32，產品為整數(shù)）。 工時/件工序

型號B1B2B3利潤（元/件）B31B32A10.30.20.30.225A20.70.10.50.440每周工時（小時/月）250100150120

/sundae_meng解：設A1、A2產品的生產數(shù)量分別為x1、x2件，在不考慮B31和B32相互排斥的情況下，問題的數(shù)學模型為/sundae_meng工序B3只能從兩種加工方式中選擇一種，那么約束條件（1）和（2）就成為相互排斥的約束條件。為了統(tǒng)一在一個問題中，引入0-1變量則數(shù)學模型為/sundae_meng（三）固定成本問題(Fixedcostproblem)例4.8某公司制造小、中、大三種尺寸的容器，所需資源為金屬板、勞動力和機器設備，制造一個容器所需的各種資源的數(shù)量如下表所示：不考慮固定費用，小、中、大號容器每售出一個其利潤分別為4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動力有300人/月，機器有100臺/月，若生產，不管每種容器生產多少，都需要支付一筆固定費用：小號為100萬元，中號為150萬元，大號為200萬元。問如何制定生產計劃使獲得的利潤最大？資源小號容器中號容器大號容器金屬板（噸）248勞動力（人/月）234機器設備（臺/月）123/sundae_meng解：設x1、x2、x3分別為小號容器、中號容器、大號容器的生產數(shù)量。不考慮固定費用，則問題的數(shù)學模型為/sundae_meng若考慮固定費用就必須引入0—1變量：則該問題的數(shù)學模型為可以看出，當xj>0時，為使Z極大化，應有Yj=0/sundae_meng（四）布點問題(LocationProblem)例4.9

某城市消防隊布點問題。該城市共有6個區(qū)，每個區(qū)都可以建消防站，市政府希望設置的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時，消防車要在15分鐘內趕到現(xiàn)場。據(jù)實地測定，各區(qū)之間消防車行駛的時間見表4－9，請幫助該市制定一個布點最少的計劃。表4－9消防車在各區(qū)間行駛時間表單位：min

地區(qū)1地區(qū)2地區(qū)3地區(qū)4地區(qū)5地區(qū)6地區(qū)101016282720地區(qū)210024321710地區(qū)316240122721地區(qū)428321201525地區(qū)527172715014地區(qū)620102125140/sundae_meng解：引入0－1變量xi作決策變量，令本問題的約束方程是要保證每個地區(qū)都有一個消防站在15分鐘行程內。如地區(qū)1，由表4－9可知，在地區(qū)1及地區(qū)2內設消防站都能達到此要求，即x1＋x2≥1因此本問題的數(shù)學模型為：

minz＝x1＋x2＋x3＋x4＋x5＋x6

x1＋x2≥1