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

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

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

----vonNeumann

引言---數(shù)學(xué)之重要

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

----KarlMarxGalileo:

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

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

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

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

數(shù)學(xué)建模將各種知識(shí)綜合應(yīng)用于解決實(shí)際問題中，是培養(yǎng)和提高同學(xué)們應(yīng)用所學(xué)知識(shí)分析問題、解決問題的能力的必備手段之一.數(shù)學(xué)建模參考書1.《數(shù)學(xué)模型》姜啟源、謝金星、葉俊編高等教育出版社2.《數(shù)學(xué)建模方法及其應(yīng)用》解放軍信息工程大學(xué)韓中庚編高教社3.《數(shù)學(xué)模型與數(shù)學(xué)建?！穭砀?、曾文藝編著北師大出版社4.葉其孝等，《大學(xué)生數(shù)學(xué)建模競(jìng)賽輔導(dǎo)教材（一）~（四）》，湖南教育出版社

5.趙靜等，《數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)》，高等教育出版社，施普林格出版社

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

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

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

--------目標(biāo)函數(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)目標(biāo)函數(shù)值)數(shù)學(xué)規(guī)劃模型的一般形式(fS)局部最優(yōu)解:x*

S，

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

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

S

N(x*)

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

x*時(shí)有嚴(yán)格不等式成立，則分別稱x*

為(fS)的嚴(yán)格全局最優(yōu)解和嚴(yán)格局部最優(yōu)解。嚴(yán)格l.opt.嚴(yán)格g.opt.l.opt.數(shù)學(xué)規(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

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

線性規(guī)劃(LP)

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

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

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

二次規(guī)劃(QP)

目標(biāo)為二次函數(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ù)學(xué)規(guī)劃優(yōu)化模型的簡單分類和求解難度優(yōu)化線性規(guī)劃非線性規(guī)劃二次規(guī)劃連續(xù)優(yōu)化整數(shù)規(guī)劃問題求解的難度增加

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

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

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

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

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

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

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

解答返回模型特點(diǎn)：目標(biāo)函數(shù)(Objectivefunction)與約束條件(Constraint)均為線性的；目標(biāo)函數(shù)實(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線性規(guī)劃的基本概念1.可行解(FeasibleSolution)——任一滿足約束條件的一組決策變量的數(shù)值.2.可行域(FeasibleRegion)——所有可行解組成的集合，也稱為可行解集.3.目標(biāo)函數(shù)等值線(Objectivefunctionline)——為于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值.線性規(guī)劃模型的解的幾種情況線性規(guī)劃問題有可行解(Feasible)無可行解（Infeasible）有最優(yōu)解（Optimal）無最優(yōu)解(Unbounded)

數(shù)學(xué)建模中線性規(guī)劃模型的常用解法線性規(guī)劃問題的求解在理在理論上有單純型法，在實(shí)際建模中常用以下解法：1.圖解法2.LINGO軟件包3.Excel中的規(guī)劃求解4.MATLAB軟件包主要介紹線性規(guī)劃模型的MATlAB軟件包和LINGO軟件包解法模型求解方法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用MATLAB優(yōu)化工具箱解線性規(guī)劃minz=cX

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

2.模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式：存在，則令A(yù)=[]，b=[].式中：linprog稱為調(diào)用函數(shù)，C,A,b稱為輸入?yún)?shù)，全部由用戶提供，必須按規(guī)定的位置放置在原括號(hào)內(nèi).3.模型：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]若沒有等式約束:,則令A(yù)eq=[],beq=[].[2]其中X0表示初始點(diǎn),設(shè)置它有些情況下可以減少迭代工作量4.命令：[x,fval]=linprog(…)返回最優(yōu)解ｘ及ｘ處的目標(biāo)函數(shù)值fval.解編寫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解:編寫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)s.t.改寫為：例3問題一的解答

問題編寫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)結(jié)果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004

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

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

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

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

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

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

圖解法

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

z=0z=2400z=3600z

=c(常數(shù))~等值線c在B(20,30)點(diǎn)得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線性函數(shù)可行域?yàn)橹本€段圍成的凸多邊形目標(biāo)函數(shù)的等值線為直線最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。模型求解

軟件實(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，利潤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三種資源“資源”剩余為零的約束為緊約束（有效約束）原料無剩余時(shí)間無剩余加工能力剩余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單位,利潤增長48時(shí)間增加1單位,利潤增長2加工能力增長不影響利潤影子價(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í)間模型求解

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

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

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

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

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

或GINname

使用LINDO的一些注意事項(xiàng)2.狀態(tài)窗口（LINDOSolverStatus）當(dāng)前狀態(tài)：已達(dá)最優(yōu)解迭代次數(shù)：18次約束不滿足的“量”(不是“約束個(gè)數(shù)”)：0當(dāng)前的目標(biāo)值：94最好的整數(shù)解：94整數(shù)規(guī)劃的界：93.5分枝數(shù)：1所用時(shí)間：0.00秒（太快了，還不到0.005秒）刷新本界面的間隔:1(秒)二、LINGO軟件包(1)LINGO模型的優(yōu)點(diǎn)1.LINGO軟件簡介(2)對(duì)簡單的LINGO程序LINGO也可以和LINDO一樣編程但LINGO與LINDO語法有差異提供了靈活的編程語言（矩陣生成器）包含了LINDO的全部功能Lindo與簡單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程序:實(shí)驗(yàn)作業(yè)

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

---TransportationProblem運(yùn)輸問題(TransportationProblem)

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

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

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

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

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

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

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

一、集合定義部分

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

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

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

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

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

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

以上集合中屬性X（有48個(gè)分量）是決策變量，是待求的未知數(shù)，屬性AI、DJ和Ｃ（分別有６,8,48個(gè)分量）都是已知數(shù)，LINKS建模語言通過數(shù)據(jù)初始化部分來實(shí)現(xiàn)對(duì)已知屬性賦以初始值，格式為：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語句結(jié)束，這兩個(gè)語句需單獨(dú)成一行，數(shù)據(jù)之間的逗號(hào)和空格可以互換。三、目標(biāo)函數(shù)和約束條件目標(biāo)函數(shù)表達(dá)式

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

式中，@SUM是LINGO提供的內(nèi)部函數(shù)，其作用是對(duì)某個(gè)集合的所有成員求制定表達(dá)式的和，該函數(shù)需要兩個(gè)參數(shù)，第一個(gè)參數(shù)是集合名稱，制定對(duì)該集合的所有成員求和，如果此集合是一個(gè)初始集合，它有m個(gè)成員，則求和運(yùn)算對(duì)m個(gè)成員進(jìn)行，相當(dāng)于求，第二個(gè)參數(shù)是一個(gè)表達(dá)式，表示求和運(yùn)算對(duì)該表達(dá)式進(jìn)行，此處，@SUM的第一個(gè)參數(shù)是LINKS（I，J），表示求和運(yùn)算對(duì)LINKS進(jìn)行，該集合的維數(shù)為2，共有48個(gè)成員，運(yùn)算規(guī)則是：先對(duì)48個(gè)成員分別求表達(dá)式C(I,J)*X(I,J)的值，然后求和，相當(dāng)于求，表達(dá)式中的C和X是集合的兩個(gè)屬性，它們各有48個(gè)分量。注：如果表達(dá)式中參與酸的屬性屬于同一個(gè)集合，則語句中索引（相當(dāng)于矩陣或數(shù)組的下標(biāo)可以省略）（隱藏），假如表達(dá)式中參與運(yùn)算的屬性屬于不同的集合，則不能省略屬性的索引.本例的目標(biāo)函數(shù)可以表示成MIN=@SUM(LINKS:C*X);約束條件用ＬINGO語言描述該約束條件，語句為：@FOR(WH(I):@SUM(VD(J):X(I,J))<=AI(I));語句中的@FOR是LINGO提供的內(nèi)部函數(shù)，它的作用是對(duì)某個(gè)集合的所有成員分別生成一個(gè)約束表達(dá)式，它有兩個(gè)參數(shù)，第一個(gè)參數(shù)是集合名，表示對(duì)該集合的所有成員生成對(duì)應(yīng)的約束表達(dá)式，上式@FOR的第一個(gè)參數(shù)為ＷＨ，它表示貨棧，共有６個(gè)成員，故應(yīng)生成６個(gè)約束表達(dá)式，@FOR的第二個(gè)參數(shù)是約束表達(dá)式的具體內(nèi)容，此處再調(diào)用@SUM函數(shù)，表示該約束的左邊是求和，是對(duì)集合ＶＤ的８?jìng)€(gè)成員，并且對(duì)表達(dá)式Ｘ(I,J)中的第二維J求和，即約束表達(dá)式的右邊是集合ＷＨ的屬性AI，它有6個(gè)分量，與6個(gè)約束表達(dá)式一一對(duì)應(yīng)，本句中的屬性分別屬于不同的集合，所以不能省略I,J.約束條件表示為@FOR(D(J)):@SUM(VD(J):X(I,J))=DJ(J));完整的模型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));!目標(biāo)函數(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”結(jié)束給出優(yōu)化目標(biāo)和約束集合定義部分從(“DATA：”到“ENDDATA”)整數(shù)規(guī)劃

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

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

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

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

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

INTvname

INTn前者只將決策變量vname標(biāo)識(shí)為0/1型,后者將當(dāng)前模型中前n個(gè)變量標(biāo)識(shí)為0/1型（模型中變量順序由模型中輸入時(shí)出現(xiàn)的先后順序決定,該順序可由輸出結(jié)果中的變量順序查證是否一致）。一般的整數(shù)變量可用命令GIN（是GENERALINTEGER的意思）,其使用方式及格式與INT命令相似。。SETX2TO<=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尚無相應(yīng)完善的敏感性分析理論，因此REDUCEDCOST和DUALPRICES的結(jié)果在整數(shù)規(guī)劃中意義不大。

例2、集裝箱運(yùn)貨

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

甲5220

乙4510

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

242X1+5X2

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

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

1書52202攝像機(jī)31303枕頭14104休閑食品23185衣服4515解：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求解Globaloptimalsolutionfound.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.0000000－1整數(shù)規(guī)劃用(Applications)（一）相互排斥的計(jì)劃(Mutuallyexclusiveplanning)例4.6某公司擬在市東、西、南三區(qū)中建立門市部，有7個(gè)點(diǎn)Ai（i＝1，2，…，7）可供選擇，要求滿足以下條件：（1）在東區(qū)，在A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；（2）在西區(qū)，A4，A5兩個(gè)點(diǎn)中至少選一個(gè)；（3）在南區(qū)，A6，A7兩個(gè)點(diǎn)為互斥點(diǎn)。（4）選A2點(diǎn)必選A5點(diǎn)。若Ai點(diǎn)投資為bi萬元，每年可獲利潤為ci萬元，投資總額為B萬元，試建立利潤最大化的0－1規(guī)劃模型。解：設(shè)決策變量為建立0－1規(guī)劃模型如下：（二）相互排斥的約束條件(Mutuallyexclusiveconstraints)例4.7某產(chǎn)品有A1和A2兩種型號(hào)，需要經(jīng)過B1、B2、B3三道工序，單位工時(shí)和利潤、各工序每周工時(shí)限制見表所示，問工廠如何安排生產(chǎn)，才能使總利潤最大？（B3工序有兩種加工方式B31和B32，產(chǎn)品為整數(shù)）。 工時(shí)/件工序

型號(hào)B1B2B3利潤（元/件）B31B32A10.30.20.30.225A20.70.10.50.440每周工時(shí)（小時(shí)/月）250100150120

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

某城市消防隊(duì)布點(diǎn)問題。該城市共有6個(gè)區(qū)，每個(gè)區(qū)都可以建消防站，市政府希望設(shè)置的消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時(shí)，消防車要在15分鐘內(nèi)趕到現(xiàn)場(chǎng)。據(jù)實(shí)地測(cè)定，各區(qū)之間消防車行駛的時(shí)間見表4－9，請(qǐng)幫助該市制定一個(gè)布點(diǎn)最少的計(jì)劃。表4－9消防車在各區(qū)間行駛時(shí)間表單位：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解：引入0－1變量xi作決策變量，令本問題的約束方程是要保證每個(gè)地區(qū)都有一個(gè)消防站在15分鐘行程內(nèi)。如地區(qū)1，由表4－9可知，在地區(qū)1及地區(qū)2內(nèi)設(shè)消防站都能達(dá)到此要求，即x1＋x2≥1因此本問題的數(shù)學(xué)模型為：

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

x1＋x2≥1

x1＋x2

＋x6≥1

x3＋x4≥1

x3＋x4＋x5≥1

x4＋x5＋x6≥1

x2

＋x5＋x6≥1

xi＝1或0（i＝1，…，6）（五）指派問題（Assignmentproblem）指派問題是一種特殊的整數(shù)規(guī)劃問題。在實(shí)踐中經(jīng)常會(huì)遇到一種問題：某單位有m項(xiàng)任務(wù)要m個(gè)人去完成（每人只完成一項(xiàng)工作），在分配過程中要充分考慮各人的知識(shí)、能力、經(jīng)驗(yàn)等，應(yīng)如何分配才能使工作效率最高或消耗的資源最少？這類問題就屬于指派問題。引入0－1變量xij案例：福爾市場(chǎng)營銷調(diào)查指派問題福爾市場(chǎng)營銷調(diào)查公司有3個(gè)新客戶需要進(jìn)行市場(chǎng)調(diào)查，目前正好有3個(gè)人沒有其他工作，由于他們的對(duì)不同市場(chǎng)的經(jīng)驗(yàn)和能力不同，估計(jì)他們完成不同任務(wù)所需時(shí)間如下表。公司面臨的問題是如何給每個(gè)客戶指派一個(gè)項(xiàng)目主管（代理商），使他們完成市場(chǎng)調(diào)查的時(shí)間最短。預(yù)計(jì)完成時(shí)間

客戶項(xiàng)目主管1231231096151814953設(shè)xij=1表示指派主管i完成第j項(xiàng)市場(chǎng)調(diào)查，否則xij=0則問題的數(shù)學(xué)模型為：minf=10x11+15x12+9x13+9x21+18x22+5x23+6x31+14x32+3x33x11+x12+x13=1x21+x22+x23=1x31+x32+x33=1x11+x21+x31=1x12+x22+x32=1x13+x23+x33=1

xij≥0，i=1，2，3；j=1，2，3MODEL:SETS:SUPERVISOR/S1,S2,S3/;CUSTOMER/C1,C2,C3/;LINKS(SUPERVISOR,CUSTOMER):C,X;E