【大學(xué)】數(shù)學(xué)建模 優(yōu)化模型介紹

1、編輯ppt數(shù)學(xué)建模數(shù)學(xué)建模 優(yōu)化模型介紹編輯ppt引言-數(shù)學(xué)之重要數(shù)學(xué)使人周密數(shù)學(xué)使人周密 - Francis Bacon 數(shù)學(xué)處于人類智能的中心領(lǐng)域數(shù)學(xué)處于人類智能的中心領(lǐng)域數(shù)學(xué)方數(shù)學(xué)方法滲透、支配著一切自然科學(xué)的理論分支法滲透、支配著一切自然科學(xué)的理論分支它已愈來愈成為衡量成就的主要標(biāo)志。它已愈來愈成為衡量成就的主要標(biāo)志。 - von Neumann 編輯ppt引言-數(shù)學(xué)之重要 一門科學(xué)只有當(dāng)它達到能夠成功地運用一門科學(xué)只有當(dāng)它達到能夠成功地運用 數(shù)學(xué)時，才算真正發(fā)展了。數(shù)學(xué)時，才算真正發(fā)展了。 - - Karl MarxGalileo : : 展現(xiàn)在我們眼前的宇宙像一本用數(shù)學(xué)語言寫成的大

2、書，如不掌握數(shù)學(xué)符號語言，就像在黑暗的迷宮里游蕩，什么也認識不清。數(shù)學(xué)是一種語言，是一切科學(xué)的共同語言數(shù)學(xué)是一種語言，是一切科學(xué)的共同語言編輯ppt引言-數(shù)學(xué)之重要數(shù)學(xué)是一種技術(shù)，是高技術(shù)的本質(zhì)數(shù)學(xué)是一種技術(shù)，是高技術(shù)的本質(zhì)數(shù)學(xué)技術(shù)數(shù)學(xué)技術(shù)-數(shù)學(xué)方法與計算技術(shù)的結(jié)合形 成的一種關(guān)鍵性的、可實現(xiàn)的技術(shù)二十世紀最偉大的數(shù)學(xué)家-二十世紀最偉大的物理學(xué)家-Go back諾貝爾諾貝爾獎獎菲爾茲獎菲爾茲獎編輯ppt1. 什么是數(shù)學(xué)模型？什么是數(shù)學(xué)模型？ 數(shù)學(xué)模型數(shù)學(xué)模型是對于現(xiàn)實世界的一個特定對象特定對象，一個特定目的特定目的，根據(jù)特有的內(nèi)在規(guī)律內(nèi)在規(guī)律，做出一些必要的假必要的假設(shè)設(shè)，運用適當(dāng)?shù)臄?shù)學(xué)工具數(shù)

3、學(xué)工具，得到一個數(shù)學(xué)結(jié)構(gòu)數(shù)學(xué)結(jié)構(gòu) 簡單地說：就是系統(tǒng)的某種特征的本質(zhì)的數(shù)學(xué)表達式（或是用數(shù)學(xué)術(shù)語對部分現(xiàn)實世界的描述），即用數(shù)學(xué)式子（如函數(shù)、圖形、代數(shù)方程、微分方程、積分方程、差分方程等）來描述（表述、模擬）所研究的客觀對象或系統(tǒng)在某一方面的存在規(guī)律編輯ppt2. 什么是數(shù)學(xué)建模什么是數(shù)學(xué)建模? 數(shù)學(xué)建模數(shù)學(xué)建模是利用數(shù)學(xué)方法解決實際問題的一種實踐即通過抽象、簡化、假設(shè)、引進變量等處理過程后，將實際問題用數(shù)學(xué)方式表達，建立起數(shù)學(xué)模型，然后運用先進的數(shù)學(xué)方法及計算機技術(shù)進行求解 觀點：觀點：“所謂所謂高科技高科技就是一種就是一種數(shù)學(xué)技術(shù)數(shù)學(xué)技術(shù)”編輯ppt 數(shù)學(xué)建模數(shù)學(xué)建模其實并不是什么新東西

4、，可以說有了數(shù)學(xué)并需要用數(shù)學(xué)去解決實際問題，就一定要用數(shù)學(xué)的語言、方法去近似地刻畫該實際問題，這種刻劃的數(shù)學(xué)表述的就是一個數(shù)學(xué)模型，其過程就是數(shù)學(xué)建模的過程數(shù)學(xué)模型一經(jīng)提出，就要用一定的技術(shù)手段（計算、證明等）來求解并驗證，其中大量的計算往往是必不可少的，高性能的計算機的出現(xiàn)使數(shù)學(xué)建模這一方法如虎添翼似的得到了飛速的發(fā)展，掀起一個高潮 數(shù)學(xué)建模將各種知識綜合應(yīng)用于解決實際問題中，是培養(yǎng)和提高同學(xué)們應(yīng)用所學(xué)知識分析問題、解決問題的能力的必備手段之一.編輯ppt數(shù)學(xué)建模參考書數(shù)學(xué)建模參考書1.數(shù)學(xué)模型 姜啟源、謝金星、葉俊編 高等教育出版社 2.數(shù)學(xué)建模方法及其應(yīng)用 解放軍信息工程大學(xué) 韓中庚編

5、高教社 3.數(shù)學(xué)模型與數(shù)學(xué)建模 劉來福、曾文藝編著 北師大出版社4. 葉其孝等，大學(xué)生數(shù)學(xué)建模競賽輔導(dǎo)教材（一）（四），湖南教育出版社5.趙靜等，數(shù)學(xué)建模與數(shù)學(xué)實驗，高等教育出版社，施普林格出版社編輯ppt 規(guī)劃模型的應(yīng)用極其廣泛，其作用已為越來規(guī)劃模型的應(yīng)用極其廣泛，其作用已為越來來越急速地滲透于工農(nóng)業(yè)生產(chǎn)、商業(yè)活動、軍事來越急速地滲透于工農(nóng)業(yè)生產(chǎn)、商業(yè)活動、軍事行為行為 科學(xué)研究的各個方面，為社會節(jié)省的財富、科學(xué)研究的各個方面，為社會節(jié)省的財富、創(chuàng)造的價值無法估量創(chuàng)造的價值無法估量. 特別是在數(shù)模競賽過程中，規(guī)劃模型是最常特別是在數(shù)模競賽過程中，規(guī)劃模型是最常見的一類數(shù)學(xué)模型見的一類數(shù)學(xué)模

6、型. 從從92-06年全國大學(xué)生數(shù)模競年全國大學(xué)生數(shù)模競越多的人所重視越多的人所重視. 隨著計算機的逐漸普及，它越隨著計算機的逐漸普及，它越賽試題的解題方法統(tǒng)計結(jié)果來看，規(guī)劃模型共出賽試題的解題方法統(tǒng)計結(jié)果來看，規(guī)劃模型共出現(xiàn)了現(xiàn)了15次，占到了次，占到了50%，也就是說每兩道競賽題，也就是說每兩道競賽題中就有一道涉及到利用規(guī)劃理論來分析、求解中就有一道涉及到利用規(guī)劃理論來分析、求解. 編輯ppt 優(yōu)化問題，一般是指用“最好”的方式，使用或分配有限的資源，即勞動力、原材料、機器、資金等，使得費用最小或者利潤最大。優(yōu)化模型優(yōu)化模型編輯pptmin min f(x) -目標(biāo)函數(shù)目標(biāo)函數(shù) s.t.

7、s.t. x S -約束集合，可行集約束集合，可行集其中，其中，S R Rn n，f : :S R R，x S稱（稱（f S ) )的可行解的可行解n最優(yōu)解最優(yōu)解: : x* S，滿足滿足f (x*) f (x), x S。則稱則稱 x*為為( (f S) )的全局最優(yōu)解的全局最優(yōu)解( (最優(yōu)解最優(yōu)解),), 記記 g.opt.( (global optimum),),簡記簡記 opt.n最優(yōu)值最優(yōu)值: : x*為為( (f S) )的最優(yōu)解的最優(yōu)解, , 則稱則稱 f * = f (x*) 為為 ( (f S) )的最優(yōu)值的最優(yōu)值( (最優(yōu)目標(biāo)函數(shù)值最優(yōu)目標(biāo)函數(shù)值) )數(shù)學(xué)規(guī)劃模型的一般形式

8、數(shù)學(xué)規(guī)劃模型的一般形式(f S)編輯pptn局部最優(yōu)解局部最優(yōu)解: : x* S， x* 的鄰域的鄰域 N(x*) ，使?jié)M足，使?jié)M足 f (x*) f (x), x S N(x*) 。則稱則稱 x*為為( (f S) )的局部最的局部最優(yōu)解優(yōu)解, ,記記 l .opt.( (local optimum) )n在上述定義中，當(dāng)在上述定義中，當(dāng)x x* 時有嚴格不等式成立，時有嚴格不等式成立，則分別則分別稱稱 x* 為為( (f S) )的嚴格全局最優(yōu)解和嚴格局部最優(yōu)解的嚴格全局最優(yōu)解和嚴格局部最優(yōu)解。嚴格嚴格l .opt .嚴格嚴格g .opt .l .opt .編輯ppt數(shù)學(xué)規(guī)劃模型的一般形式

9、數(shù)學(xué)規(guī)劃模型的一般形式 函數(shù)形式函數(shù)形式: f(x), gi(x) , hj(x) : RnR min f(x)(fgh) s.t. gi(x) 0 , i = 1,2,m hj(x) = 0 , j = 1,2,l 矩陣形式矩陣形式: : min f(x) ，f(x) : RnR(fgh) s.t. g(x) 0 , g(x) : RnRm h(x) = 0 , h(x) : RnRl 當(dāng)當(dāng) f(x), gi(x) , hj(x)均為線性函數(shù)時，稱線性均為線性函數(shù)時，稱線性規(guī)劃；若其中有非線性函數(shù)時，稱非線性規(guī)劃規(guī)劃；若其中有非線性函數(shù)時，稱非線性規(guī)劃。編輯ppt優(yōu)化模型的優(yōu)化模型的簡單分類

10、簡單分類 線性規(guī)劃線性規(guī)劃(LP) 目標(biāo)和約束均為線性函數(shù)目標(biāo)和約束均為線性函數(shù) 非線性規(guī)劃非線性規(guī)劃(NLP) 目標(biāo)或約束中存在非線性函數(shù)目標(biāo)或約束中存在非線性函數(shù) 二次規(guī)劃二次規(guī)劃(QP) 目標(biāo)為二次函數(shù)、約束為線性目標(biāo)為二次函數(shù)、約束為線性 整數(shù)規(guī)劃整數(shù)規(guī)劃(IP) 決策變量決策變量(全部或部分全部或部分)為整數(shù)為整數(shù) 整數(shù)整數(shù)線性線性規(guī)劃規(guī)劃(ILP)，整數(shù)，整數(shù)非線性非線性規(guī)劃規(guī)劃(INLP) 純整數(shù)規(guī)劃純整數(shù)規(guī)劃(PIP), 混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃(MIP) 一般整數(shù)規(guī)劃，一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃（整數(shù)）規(guī)劃njiDxljxgmixhtsxf,.,1, 0)(,.,1,

11、0)(. .)(min連連續(xù)續(xù)優(yōu)優(yōu)化化離離散散優(yōu)優(yōu)化化數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃編輯ppt優(yōu)化模型的簡單分類和求解難度優(yōu)化模型的簡單分類和求解難度 優(yōu)化優(yōu)化線性規(guī)劃線性規(guī)劃非線性規(guī)劃非線性規(guī)劃二次規(guī)劃二次規(guī)劃連續(xù)優(yōu)化連續(xù)優(yōu)化整數(shù)規(guī)劃整數(shù)規(guī)劃 問題求解的難度增加 編輯ppt 線性規(guī)劃線性規(guī)劃Linear Programming編輯ppt問題一問題一 ： 任務(wù)分配問題任務(wù)分配問題：某車間有甲、乙兩臺機床，可用某車間有甲、乙兩臺機床，可用于加工三種工件于加工三種工件.假定這兩臺車床的可用臺時數(shù)分別為假定這兩臺車床的可用臺時數(shù)分別為800和和900，三種工件的數(shù)量分別為，三種工件的數(shù)量分別為400、600和和5

12、00，且已知用三種，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表下表.問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費用最低？求，又使加工費用最低？ 兩個引例兩個引例編輯ppt建立線性規(guī)劃模型的基本步驟建立線性規(guī)劃模型的基本步驟：（1）設(shè)出決策變量設(shè)出決策變量 （2）確定目標(biāo)函數(shù)確定目標(biāo)函數(shù)（3）確定約束條件確定約束條件找出待定的未知變量（決策變量），并用代數(shù)符號表示找到模型的目標(biāo)或判據(jù)，寫成決策變量的線性函數(shù)，以便求出其最大值或最小值 找出問題的所有的限制

13、或約束，寫出未知變量的線性方程或 線性不等式編輯ppt解解 設(shè)在甲車床上加工工件設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為的數(shù)量分別為x1、x2、x3，在乙車床上加工工件在乙車床上加工工件1、2、3的數(shù)量分別為的數(shù)量分別為x4、x5、x6,可建立以可建立以下線性規(guī)劃模型：下線性規(guī)劃模型： 解答編輯ppt問題二：問題二： 某廠每日某廠每日8小時的產(chǎn)量不低于小時的產(chǎn)量不低于1800件件.為了進行質(zhì)量為了進行質(zhì)量控制，計劃聘請兩種不同水平的檢驗員控制，計劃聘請兩種不同水平的檢驗員.一級檢驗員的標(biāo)準為：一級檢驗員的標(biāo)準為：速度速度25件件/小時，正確率小時，正確率98%，計時工資，計時工資4元元/小時

14、；二級檢驗員小時；二級檢驗員的標(biāo)準為：速度的標(biāo)準為：速度15件件/小時，正確率小時，正確率95%，計時工資，計時工資3元元/小時小時.檢檢驗員每錯檢一次，工廠要損失驗員每錯檢一次，工廠要損失2元元.為使總檢驗費用最省，該工為使總檢驗費用最省，該工廠應(yīng)聘一級、二級檢驗員各幾名？廠應(yīng)聘一級、二級檢驗員各幾名？解解 設(shè)需要一級和二級檢驗員的人數(shù)分別為設(shè)需要一級和二級檢驗員的人數(shù)分別為x1、x2人人,則應(yīng)付檢驗員的工資為：則應(yīng)付檢驗員的工資為：212124323848xxxx因檢驗員錯檢而造成的損失為因檢驗員錯檢而造成的損失為：21211282)%5158%2258(xxxx編輯ppt故目標(biāo)函數(shù)為：故

15、目標(biāo)函數(shù)為：2121213640)128()2432(minxxxxxxz約束條件為：0, 0180015818002581800158258212121xxxxxx編輯ppt線性規(guī)劃模型：線性規(guī)劃模型：213640minxxz12121253459s.t. 150,0 xxxxxx 解答返 回編輯ppt模型特點：目標(biāo)函數(shù)模型特點：目標(biāo)函數(shù)(Objective function)與約束條件與約束條件(Constraint)均為線性的；均為線性的；目標(biāo)函數(shù)實現(xiàn)極大化或極小化。目標(biāo)函數(shù)實現(xiàn)極大化或極小化。編輯pptmin( ). (max) s.tucxAxbvlbxvub矩矩陣陣形形式式：線性規(guī)

16、劃的線性規(guī)劃的基本概念基本概念1.可行解可行解(Feasible Solution)任一滿足約束條件的任一滿足約束條件的一組決策變量的數(shù)值一組決策變量的數(shù)值.2.可行域可行域(Feasible Region)所有可行解組成的集合，所有可行解組成的集合，也稱為可行解集也稱為可行解集. 3. 目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線(Objective function line)為于同一直線上的點，具有相同的目標(biāo)函數(shù)值為于同一直線上的點，具有相同的目標(biāo)函數(shù)值.編輯ppt線性規(guī)劃模型的解的幾種情況線性規(guī)劃模型的解的幾種情況 線性規(guī)劃問題線性規(guī)劃問題有可行解有可行解(Feasible)無可行解無可行解（Infe

17、asible）有最優(yōu)解（有最優(yōu)解（Optimal）無最優(yōu)解無最優(yōu)解(Unbounded)編輯ppt 數(shù)學(xué)建模中線性規(guī)劃模型的常用解法數(shù)學(xué)建模中線性規(guī)劃模型的常用解法 線性規(guī)劃問題的求解在理在理論上有單純型法，在實際建模線性規(guī)劃問題的求解在理在理論上有單純型法，在實際建模中常用以下解法：中常用以下解法：1.圖解法圖解法軟件包軟件包中的規(guī)劃求解中的規(guī)劃求解4. MATLAB 軟件包軟件包主要介紹線性規(guī)劃模型的主要介紹線性規(guī)劃模型的MATlAB軟件包和軟件包和LINGO軟件包解法軟件包解法編輯ppt模型求解方法模型求解方法1. 圖解法圖解法例1 max z=50 x1+100 x2 x1 + x23

18、00 2x1 + x2400 x2250 x1、x20 該問題的最優(yōu)解為該問題的最優(yōu)解為x1=50=50；x2=250=250 x2z*=50 x1+100 x2=27500 x1 + x2300 x1x22502x1 + x2400z1=50 x1+100 x2=0BOACDz2=14000編輯ppt用用MATLAB優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃min z=cX s.t.AXb1. 模型：命令：x=linprog（c, A, b） 2. 模型：min z=cX s.t.AXbbeqXAeq命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式： 存在，則令A(yù)= ，

19、b= .bAX 式中：linprog 稱為調(diào)用函數(shù)，C, A, b 稱為輸入?yún)?shù)，全部由用戶提供，必須按規(guī)定的位置放置在原括號內(nèi).編輯ppt3. 模型：min z=cX s.t.AXbbeqXAeqVLBXVUB命令：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表示初始點 ,設(shè)置它有些情況下可以減少迭代工作量beqXAeq4. 命令：x,fval=linprog()返回最優(yōu)解及處的目標(biāo)函數(shù)值fval.編輯ppt

20、解解 編寫編寫M文件如下：文件如下：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.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) )編輯ppt解解: 編寫編寫M文件如下：文件如下： c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=12

21、0; vlb=30,0,20; vub=; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh2)123m in( 634 )xzxx32120030 xxx1231111 2 0s .t. 0105 0 xxx編輯ppts.t.Xz8121110913min 9008003 . 12 . 15 . 000000011 . 14 . 0X改寫為：例例3 問題一的解答 問題問題編輯ppt編寫編寫M文件如下文件如下:f = 13 9 10 11 12 8;A = 0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3;b = 800

22、; 900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=400 600 500;vlb = zeros(6,1);vub=;x,fval = linprog(f,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh3)編輯ppt結(jié)果結(jié)果:x =fval =1.3800e+004 即在甲機床上加工600個工件2,在乙機床上加工400個工件1、500個工件3，可在滿足條件的情況下使總加工費最小為13800.編輯ppt例例2 問題二的解答 問題問題 213640minxxz s.t. )45(3521xx改寫為：編輯ppt編寫編寫M文件如

23、下：文件如下：c = 40 36;A=-5 -3;b=-45;Aeq=;beq=;vlb = zeros(2,1);vub=9 15; %調(diào)用linprog函數(shù)：x,fval = linprog(c,A,b,Aeq,beq,vlb,vub)To MATLAB (xxgh4)編輯ppt結(jié)果為：結(jié)果為：x =fval =360即只需聘用9個一級檢驗員. 注：注：本問題應(yīng)還有一個約束條件：本問題應(yīng)還有一個約束條件：x1、x2取整數(shù)取整數(shù).故它是一個整數(shù)故它是一個整數(shù)線性規(guī)劃問題線性規(guī)劃問題.這里把它當(dāng)成一個線性規(guī)劃來解，求得其最優(yōu)解剛好這里把它當(dāng)成一個線性規(guī)劃來解，求得其最優(yōu)解剛好是整數(shù)：是整數(shù)：x

24、1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解，故它就是該整數(shù)規(guī)劃的最優(yōu)解.若用線性規(guī)劃若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門的方法求解最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門的方法求解.返 回編輯ppt用用LINDO、LINGO優(yōu)化工具箱解線性規(guī)劃優(yōu)化工具箱解線性規(guī)劃LINDO 公司軟件產(chǎn)品簡要介紹公司軟件產(chǎn)品簡要介紹 美國芝加哥美國芝加哥(Chicago)大學(xué)的大學(xué)的Linus Schrage教授于教授于1980年前后開發(fā)年前后開發(fā), 后來成立后來成立 LINDO系統(tǒng)公司（系統(tǒng)公司（

25、LINDO Systems Inc.），）， 網(wǎng)址：網(wǎng)址： LINDO: Linear INteractive and Discrete Optimizer (V6.1)LINGO: Linear INteractive General Optimizer (V8.0)LINDO API: LINDO Application Programming Interface (V2.0)Whats Best!: (SpreadSheet e.g. EXCEL) (V7.0)演演示示(試用試用)版、學(xué)生版、高級版、超級版、工業(yè)版、版、學(xué)生版、高級版、超級版、工業(yè)版、擴展版擴展版 （求解（求解問題規(guī)模問

26、題規(guī)模和和選件選件不同）不同）編輯pptLINDOLINDO和和LINGOLINGO軟件能求解的優(yōu)化模型軟件能求解的優(yōu)化模型 LINGO LINDO優(yōu)化模型優(yōu)化模型線性規(guī)劃線性規(guī)劃(LP)非線性規(guī)劃非線性規(guī)劃(NLP)二次規(guī)劃二次規(guī)劃(QP)連續(xù)優(yōu)化連續(xù)優(yōu)化整數(shù)規(guī)劃整數(shù)規(guī)劃(IP)編輯ppt一、一、LINDO軟件包軟件包 下面我們通過一個例題來說明下面我們通過一個例題來說明LINDO軟件包的使用方法軟件包的使用方法.編輯ppt問題：一奶制品加工廠用牛奶生產(chǎn)一奶制品加工廠用牛奶生產(chǎn)A1, A2 兩種奶制品，一桶兩種奶制品，一桶牛奶可以在甲類設(shè)備上用牛奶可以在甲類設(shè)備上用12小時生產(chǎn)成小時生產(chǎn)成3

27、公斤公斤A1，或者在乙類設(shè)備，或者在乙類設(shè)備上用上用8小時加工成小時加工成4公斤公斤A2.據(jù)市場要求，生產(chǎn)的兩種奶制品全部據(jù)市場要求，生產(chǎn)的兩種奶制品全部能售出，且每公斤能售出，且每公斤 A1獲利獲利24元，每公斤元，每公斤A2獲利獲利16元，現(xiàn)在每天加元，現(xiàn)在每天加工廠每天能得到工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞動時間為桶牛奶的供應(yīng)，每天正式工人總的勞動時間為480小時，并且甲類設(shè)備每天至多能加工小時，并且甲類設(shè)備每天至多能加工100公斤公斤A1，乙類設(shè)備的，乙類設(shè)備的加工能力沒有限制加工能力沒有限制.試為該廠制定一個生產(chǎn)計劃，使每天獲利最大，試為該廠制定一個生產(chǎn)計劃，使每天

28、獲利最大，并進一步討論以下并進一步討論以下3個附加問題。個附加問題。1）若用）若用35元可以買到元可以買到1桶牛奶，應(yīng)否作這樣的投資？若投資，桶牛奶，應(yīng)否作這樣的投資？若投資，每天最多購買多少桶牛奶每天最多購買多少桶牛奶2）若可以聘用臨時工人以增加勞動時間，付給臨時工人的）若可以聘用臨時工人以增加勞動時間，付給臨時工人的工資最多是每小時幾元？工資最多是每小時幾元？3）由于市場需求變化，每公斤）由于市場需求變化，每公斤A1的獲利增加到的獲利增加到30元，應(yīng)否元，應(yīng)否改變生產(chǎn)計劃？改變生產(chǎn)計劃？編輯ppt1桶桶牛奶牛奶 3kgA1 12小時小時 8小時小時 4kgA2 或或獲利獲利24元元/kg

29、獲利獲利16元元/kg x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動時間勞動時間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 12Max7264zxx每天獲利每天獲利約束條件約束條件非負約束非負約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時間時間480小時小時 至多加工至多加工100kgA1 50桶牛奶桶牛奶 每天每天基本基本模型模型編輯ppt模型求解模型求解 圖解法圖解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx

30、10031x0,21xx約約束束條條件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl12Max7264zxx目標(biāo)目標(biāo)函數(shù)函數(shù) z=0z=2400z=3600z =c (常數(shù)常數(shù)) 等值線等值線c在在B(20,30)點得到最優(yōu)解點得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線性函數(shù)目標(biāo)函數(shù)和約束條件是線性函數(shù) 可行域為直線段圍成的凸多邊形可行域為直線段圍成的凸多邊形 目標(biāo)函數(shù)的等值線為直線目標(biāo)函數(shù)的等值線為直線 最優(yōu)解一定在凸多邊最優(yōu)解一定在凸多邊形的某個頂點取得。形的某個頂點取得。 編輯ppt模型求解模型求解 軟件實現(xiàn)軟件實現(xiàn) LINDOmax 72x1+6

31、4x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICESDO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤，利潤3360元。元。 編輯ppt結(jié)果解釋結(jié)果解釋 OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES

32、max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 原料無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40編輯ppt結(jié)果解釋結(jié)果解釋 OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3) 0.000000 4) 40.000000 最優(yōu)解下最優(yōu)解下“資源資源”增增加加1單位時單位時“效益效益”

33、的的增量增量 35元可買到元可買到1桶牛奶，要買嗎桶牛奶，要買嗎?35 48, 應(yīng)該買！應(yīng)該買！ 聘用臨時工人付出的工資最多每小時幾元聘用臨時工人付出的工資最多每小時幾元? 2元！元！原料增加原料增加1單位單位,利潤增長利潤增長48時間增加時間增加1單位單位, 利潤增長利潤增長2 加工能力增長加工能力增長不不影響利潤影響利潤影子價格影子價格編輯pptRANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE R

34、IGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE最優(yōu)解不變時目標(biāo)函最優(yōu)解不變時目標(biāo)函數(shù)系數(shù)允許變化范圍數(shù)系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? Yes A1獲利增加到獲利增加到 30元元/kg，應(yīng)否改變生產(chǎn)計劃，應(yīng)否改變生產(chǎn)計劃? x1系數(shù)由系數(shù)由24 3=72增至增至30 3=90”（或（或“=”（或（或“=”）功能相同）功能相同變量與系數(shù)間可有空格變量與系數(shù)間可有空格(甚至回車甚至回車), 但無運算符但無運算符變量名以字母開頭，不能超過變量名以字母開

35、頭，不能超過8個字符個字符變量名不區(qū)分大小寫（包括變量名不區(qū)分大小寫（包括LINDO中的關(guān)鍵字）中的關(guān)鍵字）目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件行號行號(行名行名)自動產(chǎn)生或人為定義自動產(chǎn)生或人為定義.行名以行名以“）”結(jié)束結(jié)束行中注有行中注有“!”符號的后面部分為注釋符號的后面部分為注釋.如如: ! Its Comment.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE” 對模型命名對模型命名（最多（最多72個字符），如：個字符），如： TITLE This Model is only an Example編輯ppt變量不能出現(xiàn)在

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

37、98; x1=98; 2 2* *x1+x2=600 x1+x2=98 x1=98 2 2* *x1+x2=600 x1+x2bj，其數(shù)學(xué)模型為： njmixnjbxmiaxxcfijmijijnjiijminjijij, 1;, 1,0, 1, 1min1111編輯ppt 解此類問題可假想一個銷地解此類問題可假想一個銷地Bn+1，其需要量為：，其需要量為：bn+1=aai i bbj j；若用；若用xi，n+1表示從表示從Ai到到Bn+1的運量，的運量， 可令可令ci，n+1=0或等于第或等于第Ai產(chǎn)地儲存單位物資的費用。產(chǎn)地儲存單位物資的費用。 因為因為xi，n+1實際上表示實際上表示Ai

38、產(chǎn)地沒有產(chǎn)地沒有運出去而庫存的物資數(shù)量。經(jīng)處理后，問題變成了產(chǎn)銷平衡的運出去而庫存的物資數(shù)量。經(jīng)處理后，問題變成了產(chǎn)銷平衡的運輸問題，其數(shù)學(xué)模型為：運輸問題，其數(shù)學(xué)模型為：這樣，這樣，m個產(chǎn)地、個產(chǎn)地、n個銷地的不平衡運輸問題，轉(zhuǎn)化成了個銷地的不平衡運輸問題，轉(zhuǎn)化成了m個產(chǎn)地、個產(chǎn)地、n+1個銷地的平衡運輸問題，此時可用表上作業(yè)法求解。個銷地的平衡運輸問題，此時可用表上作業(yè)法求解。1, 1;, 1, 01, 1, 1min111111njmixnjbxmiaxxcfijmijijnjiijminjijij編輯ppt二、銷大于產(chǎn)二、銷大于產(chǎn)(total demand exceeds total

39、supply) 銷大于產(chǎn)的運輸問題的特征是ai bj，其數(shù)學(xué)模型為： njmixnjbxmiaxxcfijmijijnjiijminjijij, 1;, 1,0, 1, 1min1111編輯ppt 解此問題可假想一個產(chǎn)地Am+1，其產(chǎn)量為：am+1 = bjai； 若用xm+1，j表示從Am+1到Bj的運量，可令cm+1，j=0或等于第Bj產(chǎn)地每缺單位物資的損失。因為xm+1，j實際上表示Bj銷地所缺的物資數(shù)量。經(jīng)處理后，問題變成了產(chǎn)銷平衡的運輸問題，其數(shù)學(xué)模型為：此時，可用表上作業(yè)法求解。此時，可用表上作業(yè)法求解。njmixnjbxmiaxxcfijmijijnjiijminjijij, 1

40、; 1, 1, 0, 11, 1min111111編輯ppt例例 某公司有某公司有6個供貨棧（倉庫），庫存貨物總數(shù)分別為個供貨棧（倉庫），庫存貨物總數(shù)分別為60，55，51，43，41，52，現(xiàn)有，現(xiàn)有8個客戶各要一批貨數(shù)量分別為個客戶各要一批貨數(shù)量分別為35，37，22，32，41，32，43，38，各供貨棧道，各供貨棧道8個客戶的單位貨物運輸價見表個客戶的單位貨物運輸價見表供貨棧到客戶的單位貨物運價供貨棧到客戶的單位貨物運價客戶客戶 貨棧貨棧V1V2V3V4V5V6V7V8W162674259W249538582W352197433W476739271W523957265W65522814

41、3試確定各貨棧到各客戶處的貨物調(diào)運數(shù)量，使總的運輸費用最小。試確定各貨棧到各客戶處的貨物調(diào)運數(shù)量，使總的運輸費用最小。編輯ppt解解 引入決策變量引入決策變量代表從第代表從第個貨棧到第個貨棧到第個個客戶的貨物運量客戶的貨物運量. 設(shè)設(shè)表示從第表示從第 個貨棧個貨棧到第 個客戶的單位貨物運價表示第表示第 個貨棧的最大供貨量個貨棧的最大供貨量,表示第表示第個客戶的訂貨量個客戶的訂貨量.目標(biāo)函數(shù)是總運輸費用最少目標(biāo)函數(shù)是總運輸費用最少.約束條件有三條：約束條件有三條：1. 各貨棧運出的貨物總量不超過其庫存數(shù)各貨棧運出的貨物總量不超過其庫存數(shù) 2.各客戶收到的貨物總量等于其訂貨數(shù)量各客戶收到的貨物總量

42、等于其訂貨數(shù)量3. 決策變量決策變量 非負非負數(shù)學(xué)模型為數(shù)學(xué)模型為編輯ppt 前面介紹的前面介紹的LinGO的基本用法，其優(yōu)點是輸入模型較直觀，的基本用法，其優(yōu)點是輸入模型較直觀，一般的數(shù)學(xué)表達式無需作大的變換即可直接輸入一般的數(shù)學(xué)表達式無需作大的變換即可直接輸入.對于規(guī)模較對于規(guī)模較小的的規(guī)劃模型，用直接輸入的方法是有利的，如果模型的小的的規(guī)劃模型，用直接輸入的方法是有利的，如果模型的變量和約束的條件個數(shù)比較多，若仍然用直接的輸入方式，變量和約束的條件個數(shù)比較多，若仍然用直接的輸入方式，雖然也能求解并得到結(jié)果，但這種做法有明顯的不足之處。雖然也能求解并得到結(jié)果，但這種做法有明顯的不足之處。模

43、型的篇幅很長，不便于分析修改和擴展。模型的篇幅很長，不便于分析修改和擴展。 LinGO 建模語言引入集合的概念，為建立大規(guī)模的數(shù)學(xué)規(guī)建模語言引入集合的概念，為建立大規(guī)模的數(shù)學(xué)規(guī)劃模型提供了方便劃模型提供了方便. 用用LinGO 語言表達一個實際優(yōu)化問題，語言表達一個實際優(yōu)化問題，稱之為稱之為 LinGO模型。模型。 一、集合定義部分一、集合定義部分 集合是一組相關(guān)對象構(gòu)成的組合，代表模型中的實際事物，并與數(shù)學(xué)變量與集合是一組相關(guān)對象構(gòu)成的組合，代表模型中的實際事物，并與數(shù)學(xué)變量與常量聯(lián)系起來，是實際問題到數(shù)學(xué)的抽象。例中的常量聯(lián)系起來，是實際問題到數(shù)學(xué)的抽象。例中的6個倉庫可以看成一個集合，個

44、倉庫可以看成一個集合，8個客戶可以看成另一個集合。個客戶可以看成另一個集合。編輯ppt 每個集合在使用之前需要預(yù)先給出定義，定義集合時要明確三方面的內(nèi)容每個集合在使用之前需要預(yù)先給出定義，定義集合時要明確三方面的內(nèi)容：集合集合的名稱的名稱，集合內(nèi)的成員（元素）集合內(nèi)的成員（元素）、集合的屬性（可以看成與該集合有關(guān)的變量集合的屬性（可以看成與該集合有關(guān)的變量或常量，相當(dāng)于數(shù)組）或常量，相當(dāng)于數(shù)組）.本例首先定義倉庫集合本例首先定義倉庫集合：WH/W1.W6/:AI; 其中其中WH是集合的名稱，是集合的名稱，W1.W6是集合內(nèi)的成員，是集合內(nèi)的成員， “.” 是特定的省略號是特定的省略號（如果不用

45、該省略號，也可以把成員一一羅列出來，成員之間用逗號或（如果不用該省略號，也可以把成員一一羅列出來，成員之間用逗號或空格分開空格分開),表明該集合有表明該集合有6個成員，分別對應(yīng)于個成員，分別對應(yīng)于6個供貨棧，個供貨棧，AI是集合的屬性，是集合的屬性，它可以看成是一個數(shù)組，有它可以看成是一個數(shù)組，有6個分量，分別表示各貨?，F(xiàn)有貨物的總數(shù)。個分量，分別表示各貨?，F(xiàn)有貨物的總數(shù)。集合、成員、屬性的命名規(guī)則與變量相同，可按自己的意愿，用有一定意義集合、成員、屬性的命名規(guī)則與變量相同，可按自己的意愿，用有一定意義的字母數(shù)串來表示，式中的字母數(shù)串來表示，式中“/ ”和和“/:” 是規(guī)定的語法規(guī)則是規(guī)定的語

46、法規(guī)則。本例再定義客戶集合本例再定義客戶集合：VD/V1.V8/:DJ;該集合有該集合有8個成員，個成員，DJ 是集合的屬性（有是集合的屬性（有8個分量）表示各客戶的需求量個分量）表示各客戶的需求量.以上兩個集合稱為初始集合（或稱基本集合、原始集合）初始集合的屬性都初始集合（或稱基本集合、原始集合）初始集合的屬性都相當(dāng)于一維數(shù)組。相當(dāng)于一維數(shù)組。編輯ppt為表示數(shù)學(xué)模型中從貨棧到客戶的運輸關(guān)系以及與此相關(guān)的運輸單價 和運量再定義一個表示運輸關(guān)系的集合：LINKS(WH,VD): C,X;該集合以初始集合WH 和 VD 為基礎(chǔ)，稱為衍生集合（或稱派生集合）. C 和X 是該衍生集合的兩個屬性，衍

47、生集合的定義語句有如下要素組成是該衍生集合的兩個屬性，衍生集合的定義語句有如下要素組成：1）集合的名稱；）集合的名稱； (2) 集合的初始集合；集合的初始集合； （3）集合的成員（可以省略不寫）；）集合的成員（可以省略不寫）；（4）集合的屬性（可以沒有）集合的屬性（可以沒有） 定義衍生集合時可以用羅列的方式將衍生集合成員一一列舉出來，如果省略不寫，則定義衍生集合時可以用羅列的方式將衍生集合成員一一列舉出來，如果省略不寫，則默認衍生集合的成員取它所對應(yīng)初始集合的所有可能組合，上述衍生集合默認衍生集合的成員取它所對應(yīng)初始集合的所有可能組合，上述衍生集合LINKS的定的定以中沒有指明成員，則它對應(yīng)的

48、初始集合以中沒有指明成員，則它對應(yīng)的初始集合WH 有有6個成員，個成員，VD 有有8 個成員，因此個成員，因此 LINKS成員取成員取WH和和VD的所有可能組合，即有的所有可能組合，即有48個成員，個成員，48個成員可以排列成一個矩陣。其個成員可以排列成一個矩陣。其行數(shù)與集合行數(shù)與集合WH的成員個數(shù)相等，列數(shù)與集合的成員個數(shù)相等，列數(shù)與集合VD成員的個數(shù)相等成員的個數(shù)相等. 相應(yīng)地，集合相應(yīng)地，集合LINKS的的屬性和都相當(dāng)于二維數(shù)組，各有屬性和都相當(dāng)于二維數(shù)組，各有48個分量，表示貨棧個分量，表示貨棧i 到客戶到客戶Vj的單位貨物運價的單位貨物運價 X 表示貨棧表示貨棧Wi到客戶到客戶Vj的

49、貨物運量的貨物運量.編輯ppt本模型完整的集合定義為：SETS:WH/W1.W6/:AI;VD/V1.V8/DJ;LINKS(WH,VD):C,X;ENDSETS注：集合定義部分以語句注：集合定義部分以語句 SETS: 開始，開始，以以ENDSETS語句結(jié)束，這兩個語句需單獨成一行，語句結(jié)束，這兩個語句需單獨成一行，ENDSETS后面不加標(biāo)點符號后面不加標(biāo)點符號.二、數(shù)據(jù)初始化（數(shù)據(jù)段）二、數(shù)據(jù)初始化（數(shù)據(jù)段） 以上集合中屬性以上集合中屬性X（有（有48個分量）是決策變量，是待求的未知數(shù)，個分量）是決策變量，是待求的未知數(shù)，屬性屬性AI、DJ和（分別有和（分別有,8,48個分量）都是已知數(shù)，個

50、分量）都是已知數(shù)，LINKS 建模建模語言通過數(shù)據(jù)初始化部分來實現(xiàn)對已知屬性賦以初始值，格式為：語言通過數(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,9 4,9,5,3,8,5,8,2 5,2,1,9,7,4,3,3 7,6,7,3,9,2,7,1 2,3,9,5,7,2,6,5 5,5,2,2,8,1,4,3;ENDDATA注：數(shù)據(jù)初始化部分以語句注：數(shù)據(jù)初始化部分以語句 DATA:開始，以開始，以ENDDATE語句結(jié)束，這兩個語句需單獨成一行，數(shù)語句

51、結(jié)束，這兩個語句需單獨成一行，數(shù)據(jù)之間的逗號和空格可以互換。據(jù)之間的逗號和空格可以互換。編輯ppt三、目標(biāo)函數(shù)和約束條件三、目標(biāo)函數(shù)和約束條件目標(biāo)函數(shù)表達式目標(biāo)函數(shù)表達式 用用LINGO語句表示為語句表示為MIN=SUM(LINKS(I,J):C(I,J)*X(I,J); 式中，式中，SUM 是是LINGO提供的內(nèi)部函數(shù)，其作用是對某個集合的所有成員提供的內(nèi)部函數(shù)，其作用是對某個集合的所有成員求制定表達式的和，該函數(shù)需要兩個參數(shù)，第一個參數(shù)是求制定表達式的和，該函數(shù)需要兩個參數(shù)，第一個參數(shù)是集合名稱集合名稱，制定對該，制定對該集合的所有成員求和，如果此集合是一個初始集合，它有集合的所有成員求和

52、，如果此集合是一個初始集合，它有m 個成員，則求和運算個成員，則求和運算對對m 個成員進行，相當(dāng)于求個成員進行，相當(dāng)于求 ，第二個參數(shù)是一個表達式，表示求和運算對該，第二個參數(shù)是一個表達式，表示求和運算對該表達式進行，此處，表達式進行，此處， SUM的第一個參數(shù)是的第一個參數(shù)是 LINKS（I，J），表示求和運算），表示求和運算對對 LINKS進行，進行， 該集合的維數(shù)為該集合的維數(shù)為2，共有，共有48個成員，運算規(guī)則是：先對個成員，運算規(guī)則是：先對48個成員個成員分別求表達式分別求表達式 C(I,J) *X(I,J) 的值，然后求和，相當(dāng)于求的值，然后求和，相當(dāng)于求 ，表達式中的，表達式中的

53、 C和和 X是集合的兩個屬性，它們各有是集合的兩個屬性，它們各有48個分量。個分量。注：如果表達式中參與酸的屬性屬于同一個集合，則 語句中索引（相當(dāng)于矩陣或數(shù)組的下標(biāo)可以省略）（隱藏），假如表達式中參與運算的屬性屬于不同的集合，則不能省略屬性的索引.本例的目標(biāo)函數(shù)可以表示成MIN=SUM(LINKS:C*X);編輯ppt約束條件約束條件用INGO 語言描述該約束條件，語句為：FOR(WH(I): SUM(VD(J):X(I,J)=AI(I);語句中的FOR是LINGO提供的內(nèi)部函數(shù)，它的作用是對某個集合的所有成員分別生成一個約束表達式，它有兩個參數(shù)，第一個參數(shù)是集合名，表示對該集合的所有成員生

54、成對應(yīng)的約束表達式，上式 FOR 的第一個參數(shù)為，它表示貨棧，共有個成員，故應(yīng)生成個約束表達式，F(xiàn)OR 的第二個參數(shù)是約束表達式的具體內(nèi)容，此處再調(diào)用SUM 函數(shù)，表示該約束的左邊是求和，是對集合的個成員，并且對表達式(I,J) 中的第二維 J 求和，即約束表達式的右邊是集合的屬性AI，它有6個分量，與6個約束表達式一一對應(yīng)，本句中的屬性分別屬于不同的集合，所以不能省略 I,J.約束條件 表示為 FOR(D(J): SUM(VD(J):X(I,J)=DJ(J);編輯ppt完整的模型MODEL: SETS: WH/W1.W6/:AI; VD/V1.V8/:DJ; LINKS(WH,VD):C,X

55、; 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,9 4,9,5,3,8,5,8,2 5,2,1,9,7,4,3,3 7,6,7,3,9,2,7,1 2,3,9,5,7,2,6,5 5,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：”開開始始 集合

56、定義部分從集合定義部分從(“SETS：”到到“ENDSETS” )：定義集合及其屬性定義集合及其屬性以以“END”結(jié)結(jié)束束給出優(yōu)化目標(biāo)給出優(yōu)化目標(biāo)和約束和約束 集合定義部分從集合定義部分從(“DATA：”到到“ENDDATA” )編輯ppt整數(shù)規(guī)劃整數(shù)規(guī)劃 -Integer Programming, IP整數(shù)規(guī)劃整數(shù)規(guī)劃（Integer Programming）主要是指整數(shù)線）主要是指整數(shù)線性規(guī)劃。一個線性規(guī)劃問題，如果要求部分決策變量性規(guī)劃。一個線性規(guī)劃問題，如果要求部分決策變量為整數(shù)，則構(gòu)成一個整數(shù)規(guī)劃問題。為整數(shù)，則構(gòu)成一個整數(shù)規(guī)劃問題。所有變量都要求為整數(shù)的稱為所有變量都要求為整數(shù)的稱

57、為純整數(shù)規(guī)劃純整數(shù)規(guī)劃（Pure Integer Programming）或稱）或稱全整數(shù)規(guī)劃全整數(shù)規(guī)劃（All integer Programming）；）；僅有一部分變量要求為整數(shù)的稱為僅有一部分變量要求為整數(shù)的稱為混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃（Mixed Integer Programming）；）；有的變量限制其取值只能為有的變量限制其取值只能為0或或1，這類特殊的整數(shù)規(guī)，這類特殊的整數(shù)規(guī)劃稱為劃稱為01規(guī)劃規(guī)劃(0-1 Integer Programming )編輯ppt整數(shù)規(guī)劃問題及其數(shù)學(xué)模型整數(shù)規(guī)劃問題及其數(shù)學(xué)模型例 某工廠生產(chǎn)甲、乙兩種設(shè)備，已知生產(chǎn)這兩種設(shè)備需要消耗材料A、材料B

58、，有關(guān)數(shù)據(jù)如下，問這兩種設(shè)備各生產(chǎn)多少使工廠利潤最大？設(shè)備設(shè)備材材 料料甲甲乙乙資源限量資源限量材料材料A（kg）2314材料材料B（kg）10.54.5利潤（元利潤（元/件）件）32 編輯ppt解：設(shè)生產(chǎn)甲、乙這兩種設(shè)備的數(shù)量分別為x1、x2，由于是設(shè)備臺數(shù)，則其變量都要求為整數(shù)，建立模型如下：Maxz=3x1+2x22x1+3x214x1x2x1、x20,且為整數(shù)且為整數(shù)圖41編輯ppt要求該模型的解，不考慮整數(shù)約束條件，用圖解法要求該模型的解，不考慮整數(shù)約束條件，用圖解法對相應(yīng)線性規(guī)劃求解，其最優(yōu)解為：對相應(yīng)線性規(guī)劃求解，其最優(yōu)解為：x13.25 x22.5 max z-湊整得到的湊整得

59、到的（4，2）不在可行域范圍內(nèi)。不在可行域范圍內(nèi)。-（3，2）點盡管在可行域內(nèi)，但沒有使目標(biāo)達到極大化。點盡管在可行域內(nèi)，但沒有使目標(biāo)達到極大化。-（4，1）使目標(biāo)函數(shù)達到最大，即使目標(biāo)函數(shù)達到最大，即z14。IP可用可用LINDO直接求解直接求解max 3x1+2x2st2x1+3x214endgin 2 “gin 2”表示表示“前前2個變量為個變量為整數(shù)整數(shù)”，等價于：，等價于：gin x1gin x2其中其中“GIN 2”表示表示2個變量都是一般整數(shù)變量。個變量都是一般整數(shù)變量。 （仍然默認為取值是非負的）（仍然默認為取值是非負的）編輯pptLINDO可用于求解線性純整數(shù)規(guī)劃或混合整數(shù)規(guī)

60、劃可用于求解線性純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃(IP)，模型的輸入與模型的輸入與LP問題類似問題類似, 但需但需在在END標(biāo)志后定義整型變量標(biāo)志后定義整型變量。 0/1型的變量可由型的變量可由INTEGER（可簡寫為（可簡寫為INT）命令來標(biāo)識，）命令來標(biāo)識，有以下兩種可能的用法：有以下兩種可能的用法： INT vname INT n前者只將決策變量前者只將決策變量vname標(biāo)識為標(biāo)識為0/1型型, 后者將當(dāng)前模型中前后者將當(dāng)前模型中前n 個變量標(biāo)識為個變量標(biāo)識為0/1型（模型中變量順序由型（模型中變量順序由模型中輸入時出現(xiàn)的先后順序決定模型中輸入時出現(xiàn)的先后順序決定, 該順序可由輸出結(jié)果中的該順序