優(yōu)化模型及求解.ppt

1、優(yōu)化模型及求解,優(yōu)化問題及 LINGO軟件的應(yīng)用,在工程技術(shù)、經(jīng)濟管理、科學(xué)研究和日常生活中，我們經(jīng)常會遇到的一類決策問題是：在一系列客觀或主觀條件限制下，尋求使所關(guān)注的某個或多個指標(biāo)達到最優(yōu)的決策。這類問題稱為最優(yōu)化問題，研究處理這類問題的數(shù)學(xué)方法稱為最優(yōu)化方法，它也是運籌學(xué)和管理科學(xué)中解決定量問題的基本方法。在決策科學(xué)化、定量化的呼聲日益高漲的今天，用最優(yōu)化方法來解決定量的決策問題無疑是符合時代潮流與要求的，也應(yīng)該是當(dāng)今大學(xué)生必備的知識之一。,通常人們解決優(yōu)化問題的手段大致有以下幾種： （1）依賴過去的經(jīng)驗判斷面臨的問題。這種方法似乎切實可行，但是在處理過程中會融入決策者大量的主觀因素，結(jié)

2、果未必是好的，且存在較大的風(fēng)險。 （2）大量做試驗進行比較。這雖然人為因素減少，比較真實可靠，但是投入費用大且結(jié)果未必是最好的。 （3）用數(shù)學(xué)方法建立優(yōu)化模型求得最優(yōu)決策，稱為優(yōu)化建模方法，所得模型稱為優(yōu)化模型。,用最優(yōu)化方法解決決策問題包括兩個基本步驟：首先，我們需要把實際決策問題翻譯、表述成數(shù)學(xué)最優(yōu)化的形式，即用數(shù)學(xué)建模方法建立決策問題的優(yōu)化模型，簡稱為優(yōu)化建模；其次，建立優(yōu)化模型后，我們需要選擇、利用優(yōu)化方法和工具求解模型。優(yōu)化建模方法自然具有一般的數(shù)學(xué)建模方法的共同特性，但優(yōu)化模型又是一類既重要、又特殊的數(shù)學(xué)模型，因此優(yōu)化建模方法又具有一定的特殊性和專業(yè)性。此外，由于優(yōu)化模型的種類很多

3、，很多模型目前還沒有有效的求解方法，不同的算法用于求解不同模型的效果可能差異很大，如何利用優(yōu)化軟件求解優(yōu)化模型也有一定的專業(yè)性和技巧性。,優(yōu)化模型是一種特殊的數(shù)學(xué)模型，優(yōu)化建模方法是一種特殊的數(shù)學(xué)建模方法，優(yōu)化模型一般由以下三個要素構(gòu)成。,優(yōu)化問題的建模實例,（1）決策變量：是問題要求解的未知 量，一般可用n維向量x來表示。,（2）目標(biāo)函數(shù)：是該問題要優(yōu)化的目 標(biāo)數(shù)學(xué)表達式，是決策變量x的函數(shù)。,（3）約束條件：即決策變量的取值范 圍，由該問題對決策變量的限制條件決定。,例1：某廠用原料A、B、C生產(chǎn)甲乙兩種產(chǎn)品，已知生產(chǎn)單位甲產(chǎn)品需用三種原料為5，300，12個單位，利潤8000元.生產(chǎn)單位

4、乙產(chǎn)品需用三種原料為3，80，4個單位，利潤3000元。現(xiàn)有三種原料為500、20000、900個單位。問在此條件下如何生產(chǎn)獲利最大？,這是一個簡單的二元線性規(guī)劃問題，數(shù)學(xué) 模型為：,這個模型的求解可以用圖解法，也可用單純形方法，我們在LINGO軟件上求解。,例2：某服務(wù)部門一周中每天需要不同數(shù)目的雇員：周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人。規(guī)定應(yīng)聘者需連續(xù)工作5天，試確定聘用方案，即周一到周日每天聘用多少人，可在滿足需要的條件下聘用總?cè)藬?shù)最少。,數(shù)學(xué)模型為：,例3：準(zhǔn)備從5 名游泳運動員中選擇4人參加4100 m混合泳接力賽。5名隊員4種泳姿的百米成績見

5、下表，問應(yīng)如何選拔隊員？,5名隊員4種泳姿的百米平均成績,引入0-1變量xij表示隊員i參加泳姿j的比賽，則有,這是一個線性0-1規(guī)劃模型,也是一個指派問題，我們可以用如下的方法來計算：,總用時為253.2秒,例4：某公司需要決定一年中四個季度的生 產(chǎn)量，已知每個季度的產(chǎn)品需求量分別是 40，60 ，25 ，75個單位，需求必須按時滿 足。每個季度的正常常生產(chǎn)能力是40個單 位，單位產(chǎn)品的生產(chǎn)費用為400，若加班生 產(chǎn)，單位產(chǎn)品的生產(chǎn)費用為450，每個季度 末，單位產(chǎn)品的庫存費用為20，假定生產(chǎn) 提前期為0，初始庫存為10，如何安排生產(chǎn) 可使總費用最少？,我們用x,z,j,k分別表示需求量、正

6、常生產(chǎn)量、加班生產(chǎn)量和庫存量，則有下面的數(shù)學(xué)模型：,一般來說，LINGO中建立的優(yōu)化模型由以下三部分組成,1、集合段：這部分以“SETS:”開始，以”endsets”結(jié)束， 作用是定義必要的集合變量（set)及其元素（類似于 數(shù)組下標(biāo)）和屬性（類似于數(shù)組），如在例題模型中， 定義了集合季節(jié)，它包含四個季節(jié)指標(biāo)，每個季節(jié) 有需求、正常生產(chǎn)量、加班生產(chǎn)量和庫存量等屬性；一 旦這樣的定義建立起來，指標(biāo)可任意確定。,2、目標(biāo)與約束段：這部分沒有段的開始和結(jié)束標(biāo)記， 但是一般要用到LINGO的內(nèi)部函數(shù)，尤其是與集合相 關(guān)的函數(shù),3、數(shù)據(jù)段：這部分以“data:”開始，以”enddata”結(jié)束， 作用在于

7、對集合的屬性輸入必要的常數(shù)數(shù)據(jù)。,LINGO的運算符和函數(shù),算術(shù)運算符有加、減、乘、除、乘冪,1）#AND#（與）、#OR#（或）、#NOT#（非） 2）#EQ#（等于）、#NE#（不等于）、 #GT#（大于）、#GE#（大于等于）、 #LT#（小于）、#LE#（小于等于）,邏輯運算符有以下九種,關(guān)系運算符表示數(shù)與數(shù)之間的大小關(guān)系，有三種 （大于等于）,基本的數(shù)學(xué)函數(shù) abs(x)、 exp(x)、 log(x)、 sin(x)、 cos(x)、tan(x)、mod(x,y)、floor(x)、sign(x)、smax(list) 、 smin(list),集合循環(huán)函數(shù) 集合函數(shù)是指對集合上的

8、元素（下標(biāo)）進行循環(huán)操作的函數(shù)。一般用法如下：,function(setname(set_index_list) | condition: expression _list);其中 function是集合函數(shù)名，是 for，max,min,prod, sum五種之一,setname是集合名；,set_index_list是集合索引列表(不需用時可省略),condition是用邏輯表達式描述的過濾條件，（通常含有索引，無條件時可以省略 ）,expression_list是一個表達式，（對for函數(shù)可以是一組表達式）,for(集合元素的循環(huán)函數(shù))：對集合setname的每個元素獨立的生成表達式，表

9、達式由expression_list描述（通常是優(yōu)化問題的描述）,max（集合屬性的最大值函數(shù)）； min （集合屬性的最小值函數(shù)）；,prod（集合屬性的乘積函數(shù)）； sum （集合屬性的求和函數(shù)）；,集合操作函數(shù) 集合操作函數(shù)是指對集合進行操作的函數(shù)，主要有IN,INDEX,WRAP,SIZE四種,變量定界函數(shù) 變量定界函數(shù)是對變量的取值范圍附加限制的函數(shù)，共有四種： BND(L,X,U):限制L=X=U BIN(X):限制X為0或1 FREE(X):取消對X的符號限制 GIN(X):限制X為整數(shù),常見LINGO出錯信息 LINGO錯誤編號及含義對照表,例5：某公司用兩種原油A與B加工甲乙

10、 兩種標(biāo)號的汽油，甲乙兩種汽油含原油 A的最低比例分別為50%和60%，每噸 售價分別為4.8千元和5.6千元。公司現(xiàn)有 原油A和B分別為500t和1000t，還可以 在市場上買到不超過1500t的原油A，其 市場價為購買量不超過500t時單價為每 噸10千元，超過500不到1000噸時，超 過部分每噸8千元，若購買超過1000噸， 超過部分每噸6千元。該公司應(yīng)該如何 安排生產(chǎn)？,LINGO的進一步應(yīng)用,問題分析,這是一個優(yōu)化問題，需要安排原油的采購量和產(chǎn)品的生 產(chǎn)量。這個問題的難點是原油的采購價格比較復(fù)雜，是 一個分段函數(shù)關(guān)系，給利用優(yōu)化模型造成一定困難。,模型建立,設(shè)原油A的購買量為x（噸

11、），則采購支出函數(shù)為,設(shè)原油A用于生產(chǎn)甲乙兩種汽油的數(shù)量分別為x11和x12 原油B用于生產(chǎn)甲乙兩種汽油的數(shù)量分別為x21和x22， 則目標(biāo)函數(shù)為總利潤函數(shù)最大：,約束條件包括加工兩種汽油用的原油A、B的庫存限制、原油A的購買量的限制以及兩種汽油含原油的比例限制，它們可表示為：,模型求解,下面給出三種求解方法,第一種解法：將原油A的采購量分解為三個量，用x1,x2和x3分別表示以三種價格采購原油A的噸數(shù)，則有,這時目標(biāo)函數(shù)為,這時應(yīng)該注意到僅當(dāng)以10千元/t的價格購買x1=500時 才能以8千元/t的價格購買x2，這個條件可表為,同樣有,于是我們將模型輸入LINGO如下：,得到最優(yōu)解是用庫存的

12、原油各500t生產(chǎn) 1000t汽油甲，利潤為4800（千元）,這時LINGO得到的結(jié)果只是一個局部最 優(yōu)解，我們用菜單命令LINGO|Options在 Global Solver上啟動全局優(yōu)化選項use global solver，重新執(zhí)行求解，可得全局 最優(yōu)解：購買1000t原油A，與庫存的原 油A和B一起生產(chǎn)2500t汽油乙，利潤為 5000（千元）,第二種解法：引入0-1變量將第一種解法中的非線性約束轉(zhuǎn)化為線性約束。,令Y1=1, Y2=1, Y3=1分別表示以10（8，6）千 元/t的價格采購原油A，則第一種解法中的非 線性約束變?yōu)?這組約束隱含著變量Y1, Y2， Y3是遞減的。,于

13、是我們將模型輸入LINGO如下：,第三種解法：直接處理分段線性函數(shù)c(x),記x軸上的分點依次為b1, b2, b3, b4，當(dāng) x 屬于 b1, b2時，記x= z1 b1+ z2 b2，z1+z2 =1, z1, z2 0， 同樣，當(dāng) x 屬于 b2, b3 時，記x= z2 b2+ z3 b3， z2+z3 =1, z2, z3 0，等等。,因為c(x)在每個小區(qū)間上是線性的，所以這時x 和c(x)可以統(tǒng)一的表示為：,為了表示x在那個小區(qū)間，引入0-1變量yk, (k=1,2,3)，當(dāng)x在第 k個小區(qū)間時，yk=1，否則 yk=0，這樣，z1, z2, z3, z4 , y1, y2,

14、y3 應(yīng)滿足,LINGO軟件與外部數(shù)據(jù)的傳遞,（1）通過Windows剪貼板傳遞數(shù)據(jù) （2）通過文本文件傳遞數(shù)據(jù) （3）通過電子表格傳遞數(shù)據(jù),例6：假設(shè)有多個市政府都需要一定的公款消費，每個城市只允許消費自身的財政收入，城市(i)的最低需求量為NEED(i)，最大供應(yīng)量是SUPPLY(i)，消費成本是COST(i)，問如何消費可使總成本最??？,可以看出，這是一個簡單的線性規(guī)劃問題， 設(shè)消費量為ORD，則其數(shù)學(xué)模型為,只要給出合適的數(shù)據(jù)，這個問題的最優(yōu)解是一目了然的。,（注意：LINGO對集合的屬性是按列賦值的）,1、數(shù)據(jù)在WORD文件中給出,LINGO模型如下：,Sets: myset/|/:

15、cost,need,supply,ord; Endsets Min=sum(myset(i):ord(i)*cost(i); for(myset(i):ord(i)need(i); ord(i)supply(i); Data: Cost,need,supply=, Enddata,粘貼命令的方法,1、在Word中將城市名所在單元格復(fù)制(Ctrl+c)到剪貼板 2、回到LINGO窗口，利用菜單命令“EditPaste”或(Ctrl+V)將其粘貼到集合的元素列表位置 3、重復(fù)這個過程粘貼相應(yīng)數(shù)據(jù) 4、注意LINGO對集合的屬性是按列賦值的,2、數(shù)據(jù)在文本文件中給出,sets: myset/file

16、(my.ldt)/:file(my.ldt); endsets min=sum(myset(i):ord(i)*cos(i); for(myset(i): ord(i)nee(i); ord(i)sup(i); data: cos=file(my.ldt); nee=file(my.ldt); sup=file(my.ldt); enddata,通過文本文件輸入數(shù)據(jù)的方法,1、通過文本文件輸入數(shù)據(jù)使用的是FILE函數(shù)，這個 函數(shù)的一般用法是FILE(filename)filename是存放數(shù)據(jù) 的文件名，文件記錄之間用 分開 2、模型集合段對集合的定義要兩次用到FILE函數(shù)， 對應(yīng)文本文件的前

17、兩行 2、在程序的數(shù)據(jù)段用到三個FILE函數(shù)，對應(yīng)文本文件 的后面三行,3、數(shù)據(jù)在電子表格文件中給出,sets: myset/ole(mydata,citi)/:cost,eed,supply,ordered; endsets min=sum(myset(i):ordered(i)*cost(i); for(myset(i): con1ordered(i)eed(i); con2ordered(i)supply(i); DATA: cost,eed,supply=ole(mydata.xls); ole(mydata,sulut)=ordered; enddata,3、數(shù)據(jù)在電子表格文件中給出

18、,通過Excel文件與LINGO系統(tǒng)傳遞數(shù)據(jù)是通過OLE函數(shù)。該函數(shù)只能在模型的集合段、數(shù)據(jù)段和初始段使用。這個函數(shù)的使用格式是ole(spreadsheet_filerange_name_list) 其中spreadsheet_file是電子表格文件的名稱， range_name_list是指文件中包含數(shù)據(jù)的單元范圍。,通過Excel文件向LINGO輸入數(shù)據(jù)的方法如下： （以下面數(shù)據(jù)為例）,（1）：首先用excel建立一個名為mydata的數(shù)據(jù)文件，（見圖）。 （2）選定表格的B2:B5單元，然后選擇Excel的菜單命令“插入名稱定義”，這時會彈出一個對話框，請你輸入名稱，你可以輸入一個適當(dāng)

19、的名稱，例如citi。同樣的方法，對C2:C5,F2:F5輸入相應(yīng)的名稱如cost,eed,supply,ordered; 。這些單元取什么名稱可以隨意，最好取有一定提示意義的名字。 （3）在Excel中你對單元格取的是什么名字，在Lingo中調(diào)用時就必須用什么名字，二者必須一致。,sets: myset/ole(mydata,citi)/:cost,eed,supply,ordered; endsets min=sum(myset(i):ordered(i)*cost(i); for(myset(i): con1ordered(i)eed(i); con2ordered(i)supply(i

20、); DATA: cost,eed,supply=ole(mydata.xls); ole(mydata,sulut)=ordered; enddata,這個程序中有三個OLE函數(shù)調(diào)用，其作用說明如下：,1、ole(mydata,citi)：從文件mydata的citi所指示的 單元中取出數(shù)據(jù)，作為集合的元素,2、cost,eed,supply=ole(mydata.xls);從mydata.xls的Cost（eed,supply）指定的單元給cost（eed,supply） 賦值,3、ole(mydata,sulut)=ordered：將ordered的值輸 出賦給mydata.xls文件中

21、由sulut指定的單元格,例7：“武漢國際搶渡長江挑戰(zhàn)賽”于每年月日進行，由于水情、水性的不可預(yù)測性，這種競賽更富有挑戰(zhàn)性和觀賞性。2002年5月1日，搶渡的起點設(shè)在武昌漢陽門碼頭，終點設(shè)在漢陽南岸咀 ，假設(shè)在競渡區(qū)域兩岸為平行直線，它們的垂直距離為1160米，從武昌漢陽門的正對岸到漢陽南岸咀的距離為1000米 ，流速沿離岸邊距離的分布為 (設(shè)從武昌漢陽門垂直向上為 y軸正向),游泳者的速度大?。?.5米/秒）仍全程保持不變，試為他選擇游泳方向和路線，估計他的成績。,模型建立與求解 若游泳者的游泳速度為v，則垂直于對岸的分速度為v1=vcos,平行于兩岸方向的分速度v=-vsin。于是游泳者尚平行于水流方向的合速度V=