新用軟件編程求解規(guī)劃問題

新用軟件編程求解規(guī)劃問題第1頁，共65頁，2023年，2月20日，星期六什么是規(guī)劃問題？求目標函數在約束條件下的最大值或最小值的問題，統(tǒng)稱為規(guī)劃問題。決策變量、約束條件、目標函數是線性規(guī)劃的三要素.主要解決最優(yōu)生產計劃、最優(yōu)分配、最優(yōu)設計、最優(yōu)決策、最佳管理等最優(yōu)化問題。線性規(guī)劃非線性規(guī)劃實數規(guī)劃整數規(guī)劃0-1規(guī)劃第2頁，共65頁，2023年，2月20日，星期六例1——加工奶制品的生產計劃獲利24元/公斤獲利16元/公斤1桶牛奶3公斤A1

12小時8小時4公斤A2

或50桶牛奶時間480小時至多加工100公斤A1

每天：一奶制品加工廠用牛奶生產A1,A2兩種奶制品，1桶牛奶可以在甲車間用12小時加工成3公斤A1，或者在乙車間用8小時加工成4公斤A2。根據市場需求，生產的A1,A2全部能售出，且每公斤A1獲利24元，每公斤A2獲利16元?，F(xiàn)在加工廠每天能得到50桶牛奶的供應，每天正式工人總的勞動時間480小時，并且甲車間每天至多能加工100公斤A1，乙車間的加工能力沒有限制。試為該廠制訂一個生產計劃，使每天獲利最大.并進一步討論以下3個附加問題：1）若用35元可以買到1桶牛奶，應否作這項投資？若投資，每天最多購買多少桶牛奶？2）若可以聘用臨時工人以增加勞動時間，付給臨時工人的工資最多是每小時幾元？3）由于市場需求變化，每公斤A1的獲利增加到30元，應否改變生產計劃？第3頁，共65頁，2023年，2月20日，星期六例1——加工奶制品的生產計劃獲利24元/公斤獲利16元/公斤1桶牛奶3公斤A1

12小時8小時4公斤A2

或50桶牛奶時間480小時至多加工100公斤A1

每天：x1桶牛奶生產A1

x2桶牛奶生產A2

獲利24×3x1

獲利16×4x2

原料供應

勞動時間

加工能力

決策變量

目標函數

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

線性規(guī)劃模型(LP)第4頁，共65頁，2023年，2月20日，星期六例1——加工奶制品的生產計劃求的最大值？第5頁，共65頁，2023年，2月20日，星期六求的最大值？用Lingo軟件求解Lingo結果中其它項的意思！更多信息例1——加工奶制品的生產計劃第6頁，共65頁，2023年，2月20日，星期六max=@sin(x)*2*@exp(-x);x<8;x>0;第7頁，共65頁，2023年，2月20日，星期六Lingo軟件LINGOHelp:LINGOisasimpletoolforutilizingthepoweroflinearandnonlinearoptimizationtoformulatelargeproblemsconcisely,solvethem,andanalyzethesolution.Optimizationhelpsyoufindtheanswerthatyieldsthebestresult;attainsthehighestprofit,output,orhappiness;ortheonethatachievesthelowestcost,waste,ordiscomfort.Oftentheseproblemsinvolvemakingthemostefficientuseofyourresources——includingmoney,time,machinery,staff,inventory,andmore.Lingo是一個可以簡潔地闡述、解決和分析復雜問題的簡便工具。其特點是程序執(zhí)行速度很快，易于輸入、修改、求解和分析一個數學規(guī)劃問題。第8頁，共65頁，2023年，2月20日，星期六lingo軟件擅長于解決運籌問題，即最有問題，常見的是線性規(guī)劃。而matlab則功能比較多，主要是以矩陣為基礎的運算，也能解決運籌問題。

matlab的功能更強大一些，也比較難學，東西多l(xiāng)ingo主要用于優(yōu)化問題，matlab功能強大，幾乎什么都能做，但是碰到循環(huán)時速度較慢，而且對機器要求較高，lingo主要用以解線性規(guī)劃，方程之類，使用比matlab簡單，解決線性問題速度也不錯，有些東西不能做。不過現(xiàn)在國外有將2者結合的。matlab都能解，就是麻煩點LINGO是使建立和求解線性、非線性和整數最佳化模型更快更簡單更有效率的綜合工具。LINGO提供強大的語言和快速的求解引擎來闡述和求解最佳化模型。第9頁，共65頁，2023年，2月20日，星期六原則上還是lingo要快，特別是變量較多的時候，但是這里面不能比較非線性規(guī)劃，因為非線性規(guī)劃的求解速度不僅取決于問題的規(guī)模，還要看非線性程度以及初始...■簡單的模型表示LINGO可以將線性、非線性和整數問題迅速得予以公式表示，并且容易閱讀、了解和修改?！龇奖愕臄祿斎牒洼敵鲞x擇LINGO建立的模型可以直接從數據庫或工作表獲取資料。同樣地，LINGO可以將求解結果直接輸出到數據庫或工作表。■強大的求解引擎LINGO內建的求解引擎有線性、非線性(convexandnonconvex)、二次、二次限制和整數最佳化?！鯩odelInteractivelyorCreateTurn-keyApplicationsLINGO提供完全互動的環(huán)境供您建立、求解和分析模型。LINGO也提供DLL和OLE界面可供使用者由撰寫的程序中呼叫。第10頁，共65頁，2023年，2月20日，星期六第11頁，共65頁，2023年，2月20日，星期六第12頁，共65頁，2023年，2月20日，星期六第13頁，共65頁，2023年，2月20日，星期六0GlobalOptimum（全局最優(yōu)）1Infeasible（不可行）2Unbounded（無界）3Undetermined（不確定）4Feasible（可行）5InfeasibleorUnbounded（通常需要關閉“預處理”選項后重新求解模型，以確定模型究竟是不可行還是無界）6LocalOptimum（局部最優(yōu)）7LocallyInfeasible（局部不可行，盡管可行解可能存在，但是LINGO并沒有找到一個）8Cutoff（目標函數的截斷值被達到）9NumericError（求解器因在某約束中遇到無定義的算術運算而停止）第14頁，共65頁，2023年，2月20日，星期六第15頁，共65頁，2023年，2月20日，星期六LP:線性規(guī)劃linearprogrammingQP二次規(guī)劃NLP—NON—LINEARPROGRAMMINGILP線性整數IQP二次整數PILP線性純整數PIQP二次純整數NLP非線性NLP—NON—LINEARPROGRAMMINGINLP整數非線性PINLP純整數非線性第16頁，共65頁，2023年，2月20日，星期六例2——軍隊供給問題corps

需求量3537223241324338擁有量

B1B2B3B4B5B6B7B8depot60A16267425955A24953858251A35219743343A47673927141A52395726552A655228143軍隊有某種先進武器302臺分別放在6個補給站(depot)中，現(xiàn)由于戰(zhàn)爭需要，8個軍團(corps)分別需要此種武器數目如表中所示，并且給出了從各補給站送一臺武器到任一軍團的費用，問如何運輸可使成本最??？capacity(i)V(i)demand(j)d(j)cost(i,j)c(i,j)number(i,j)n(i,j)第17頁，共65頁，2023年，2月20日，星期六例2——軍隊供給問題corps

需求量3537223241324338擁有量

B1B2B3B4B5B6B7B8depot60A16267425955A24953858251A35219743343A47673927141A52395726552A655228143capacity(i)V(i)demand(j)d(j)cost(i,j)c(i,j)number(i,j)n(i,j)第18頁，共65頁，2023年，2月20日，星期六例2——軍隊供給問題用Lingo軟件求解結果第19頁，共65頁，2023年，2月20日，星期六Lingo軟件集合段（SETSENDSETS）目標與約束段數據段（DATAENDDATA）初始段（INITENDINIT）LINGO模型的構成：4個段Lingo是一個可以簡潔地闡述、解決和分析復雜問題的簡便工具。其特點是程序執(zhí)行速度很快，易于輸入、修改、求解和分析一個數學規(guī)劃問題。第20頁，共65頁，2023年，2月20日，星期六第21頁，共65頁，2023年，2月20日，星期六Lingo軟件——集合概念集是相聯(lián)系的對象的集合，比如工廠、消費者群體、交通工具和雇工等等；集是LINGO建模語言的基礎，是程序設計最強有力的基本構件目標與約束段；借助于集，能夠用一個單一的、長的、簡明的復合公式表示一系列相似的約束，從而可以快速方便地表達規(guī)模較大的模型；集有成員和屬性。第22頁，共65頁，2023年，2月20日，星期六集部分是LINGO模型的一個可選部分。在LINGO模型中使用集之前，必須在集部分事先定義。集部分以關鍵字“sets:”開始，以“endsets”結束。一個模型可以沒有集部分，或有一個簡單的集部分，或有多個集部分。一個集部分可以放置于模型的任何地方，但是一個集及其屬性在模型約束中被引用之前必須定義了它們。第23頁，共65頁，2023年，2月20日，星期六Lingo軟件——基本集合元素的列舉setname[/member_list/][:attribute_list];sets:students/JohnJill,RoseMike/:sex,age;endsets一個原始集是由一些最基本的對象組成的。集、集成員和集屬性第24頁，共65頁，2023年，2月20日，星期六集成員無論用何種字符標記,它的索引都是從1開始連續(xù)計數。在attribute_list可以指定一個或多個集成員的屬性，屬性之間必須用逗號隔開。第25頁，共65頁，2023年，2月20日，星期六定義一個原始集，用下面的語法：setname[/member_list/][:attribute_list];注意：用“[]”表示該部分內容可選。下同，不再贅述。Setname是你選擇的來標記集的名字，最好具有較強的可讀性。集名字必須嚴格符合標準命名規(guī)則：以拉丁字母或下劃線（_）為首字符，其后由拉丁字母（A—Z）、下劃線、阿拉伯數字（0，1，…，9）組成的總長度不超過32個字符的字符串，且不區(qū)分大小寫。注意：該命名規(guī)則同樣適用于集成員名和屬性名等的命名。Member_list是集成員列表。采取顯式羅列和隱式羅列兩種方式。第26頁，共65頁，2023年，2月20日，星期六類型隱式列舉格式示例示例集合的元素數字型1..n1..51,2,3,4,5字符-數字型stringM..stringNCar101..car208Car101,car102,…,car208星期型dayM..dayNMON..FRIMON,TUE,WED,THU,FRI月份型monthM..monthNOCT..JANOCT,NOV,DEC,JAN年份-月份型monthYearM..monthYearNOCT2001..JAN2002OCT2001,NOV2001,DEC2001,JAN2002Lingo軟件——基本集合元素的隱式列舉第27頁，共65頁，2023年，2月20日，星期六集成員不放在集定義中，而在隨后的數據部分來定義。sets:students:sex,age;endsetsdata:students,sex,age=John116Jill014 Rose017 Mike113;enddata第28頁，共65頁，2023年，2月20日，星期六注意：開頭用感嘆號（!），末尾用分號（;）表示注釋，可跨多行。第29頁，共65頁，2023年，2月20日，星期六Lingo軟件——派生集setname(parent_set_list)[/member_list/][:attribute_list];一個派生集是用一個或多個其它集來定義的。也就是說，它的成員來自于其它已存在的集。稠密集：派生集成員由父集成員所有組合構成；稀疏集：其成員為父集成員所有組合構成的集合的一個子集。顯式：links(depot,corps)/d1c2,d2c3,d3c6,d4c3,d5c1,d6c8/:cost,number;過濾：links(depot,corps)|capacity(&1)#ge#demand(&2):cost;派生集的成員列表有兩種方式生成：①顯式羅列；②設置成員資格過濾器。第30頁，共65頁，2023年，2月20日，星期六sets:product/AB/;machine/MN/;week/1..2/;allowed(product,machine,week):x;endsetsLINGO生成了三個父集的所有組合共八組作為allowed集的成員。列表如下：編號成員1(A,M,1)2

(A,M,2)3

(A,N,1)4

(A,N,2)5

(B,M,1)6

(B,M,2)7

(B,N,1)8

(B,N,2)第31頁，共65頁，2023年，2月20日，星期六例sets:!學生集：性別屬性sex，1表示男性，0表示女性；年齡屬性age.;students/John,Jill,Rose,Mike/:sex,age;!男學生和女學生的聯(lián)系集：友好程度屬性friend，[0，1]之間的數。;linkmf(students,students)|sex(&1)#eq#1#and#sex(&2)#eq#0:friend;!男學生和女學生的友好程度大于0.5的集;linkmf2(linkmf)|friend(&1,&2)#ge#0.5:x;endsetsdata:sex,age=116014017013;friend=0.30.50.6;enddata用豎線（|）來標記一個成員資格過濾器的開始。#eq#是邏輯運算符，用來判斷是否“相等”，可參考§4.&1可看作派生集的第1個原始父集的索引，它取遍該原始父集的所有成員；&2可看作派生集的第2個原始父集的索引，它取遍該原始父集的所有成員；&3，&4，……，以此類推。第32頁，共65頁，2023年，2月20日，星期六集合派生集合基本集合稀疏集合稠密集合元素列表法元素過濾法直接列舉法隱式列舉法Lingo軟件——集合setname[/member_list/][:attribute_list];setname(parent_set_list)[/member_list/][:attribute_list];第33頁，共65頁，2023年，2月20日，星期六Lingo軟件——數據段與初始段數據段：輸入集成員和數據，提供了模型相對靜止部分和數據分離的可能性。object_list=value_list;對象列＝數值列；初始段：為決策變量設置初始值。在初始部分輸入的值僅被LINGO求解器當作初始點來用，并且僅僅對非線性模型有用。和數據部分指定變量的值不同，LINGO求解器可以自由改變初始部分初始化的變量的值。以“init:”開始，以“endinit”結束。初始部分的初始聲明規(guī)則和數據部分的數據聲明規(guī)則相同。第34頁，共65頁，2023年，2月20日，星期六sets:set1/A,B,C/:X,Y;endsetsdata:X,Y=142536;enddatadata:X=1,2,3;Y=4,5,6;enddata第35頁，共65頁，2023年，2月20日，星期六和數據部分指定變量的值不同，LINGO求解器可以自由改變初始部分初始化的變量的值。例init:X,Y=0,.1;endinitY=@log(X);X^2+Y^2<=1;第36頁，共65頁，2023年，2月20日，星期六優(yōu)先級運算符最高#NOT#—（負號）^*/+—（減法）#EQ##NE##GT##GE##LT##LE##AND##OR#最低<(=)=>(=)三類運算符：算術運算符邏輯運算符關系運算符Lingo軟件——運算符與優(yōu)先級主要用于集循環(huán)函數的條件表達式中形成模型的一個約束條件，指定一個表達式的左邊是否等于、小于等于、或者大于等于右邊。針對數值進行操作第37頁，共65頁，2023年，2月20日，星期六#not#否定該操作數的邏輯值，＃not＃是一個一元運算符#eq#若兩個運算數相等，則為true；否則為flase#ne#若兩個運算符不相等，則為true；否則為flase#gt#若左邊的運算符嚴格大于右邊的運算符，則為true；否則為flase#ge#若左邊的運算符大于或等于右邊的運算符，則為true；否則為flase#lt#若左邊的運算符嚴格小于右邊的運算符，則為true；否則為flase#le#若左邊的運算符小于或等于右邊的運算符，則為true；否則為flase#and#僅當兩個參數都為true時，結果為true；否則為flase#or#僅當兩個參數都為false時，結果為false；否則為true第38頁，共65頁，2023年，2月20日，星期六Lingo軟件——函數@abs(x)返回x的絕對值@sin(x)返回x的正弦值，x采用弧度制@cos(x)返回x的余弦值@tan(x)返回x的正切值@exp(x)返回常數e的x次方@log(x)返回x的自然對數@lgm(x)返回x的gamma函數的自然對數@sign(x)如果x<0返回-1；否則，返回1@floor(x)返回x的整數部分。當x>=0時，返回不超過x的最大整數；當x<0時，返回不低于x的最大整數。@smax(x1,x2,…,xn)返回x1，x2，…，xn中的最大值@smin(x1,x2,…,xn)返回x1，x2，…，xn中的最小值數學函數第39頁，共65頁，2023年，2月20日，星期六Lingo軟件——函數變量定界函數@bin(x)限制x為0或1@bnd(L,x,U)限制L≤x≤U@free(x)取消對變量x的默認下界為0的限制，即x可以取任意實數@gin(x)限制x為整數@min和@max返回指定的集成員的一個表達式的最小值或最大值。第40頁，共65頁，2023年，2月20日，星期六第41頁，共65頁，2023年，2月20日，星期六@qrand(seed)產生服從(0,1)區(qū)間的擬隨機數。@qrand只允許在模型的數據部分使用，它將用擬隨機數填滿集屬性。通常，聲明一個m×n的二維表，m表示運行實驗的次數，n表示每次實驗所需的隨機數的個數。在行內，隨機數是獨立分布的；在行間，隨機數是非常均勻的。這些隨機數是用“分層取樣”的方法產生的。例4.5model:data:M=4;N=2;seed=1234567;enddatasets:rows/1..M/;cols/1..N/;table(rows,cols):x;endsetsdata:X=@qrand(seed);enddataend如果沒有為函數指定種子，那么LINGO將用系統(tǒng)時間構造種子。第42頁，共65頁，2023年，2月20日，星期六第43頁，共65頁，2023年，2月20日，星期六data:N=6;enddatasets:number/1..N/:x;endsetsdata:x=5134610;enddataminv=@min(number(I)|I#le#5:x);end第44頁，共65頁，2023年，2月20日，星期六第45頁，共65頁，2023年，2月20日，星期六

輸入和輸出函數

1．@file函數該函數用從外部文件中輸入數據，可以放在模型中任何地方。該函數的語法格式為@file(’filename’)。這里filename是文件名，可以采用相對路徑和絕對路徑兩種表示方式。第46頁，共65頁，2023年，2月20日，星期六例以例1.2來講解@file函數的用法。注意到在例1.2的編碼中有兩處涉及到數據。第一個地方是集部分的6個warehouses集成員和8個vendors集成員；第二個地方是數據部分的capacity，demand和cost數據。為了使數據和我們的模型完全分開，我們把它們移到外部的文本文件中。修改模型代碼以便于用@file函數把數據從文本文件中拖到模型中來。修改后（修改處代碼黑體加粗）的模型代碼如下：model:!6發(fā)點8收點運輸問題;sets:warehouses/@file('1_2.txt')/:capacity;vendors/@file('1_2.txt')

/:demand;links(warehouses,vendors):cost,volume;endsets!目標函數;min=@sum(links:cost*volume);!需求約束;@for(vendors(J):@sum(warehouses(I):volume(I,J))=demand(J));!產量約束;@for(warehouses(I):@sum(vendors(J):volume(I,J))<=capacity(I));

!這里是數據;data:capacity=@file('1_2.txt')

;demand=@file('1_2.txt');cost=@file('1_2.txt');enddataend第47頁，共65頁，2023年，2月20日，星期六模型的所有數據來自于1_2.txt文件。其內容如下：!warehouses成員;WH1WH2WH3WH4WH5WH6~

!vendors成員;V1V2V3V4V5V6V7V8~

!產量;605551434152~

!銷量;3537223241324338~

!單位運輸費用矩陣;626742594953858252197433767392712395726555228143把記錄結束標記（~）之間的數據文件部分稱為記錄。如果數據文件中沒有記錄結束標記，那么整個文件被看作單個記錄。第48頁，共65頁，2023年，2月20日，星期六2@text函數該函數被用在數據部分用來把解輸出至文本文件中。它可以輸出集成員和集屬性值。其語法為@text([’filename’])這里filename是文件名，可以采用相對路徑和絕對路徑兩種表示方式。如果忽略filename，那么數據就被輸出到標準輸出設備（大多數情形都是屏幕）。@text函數僅能出現(xiàn)在模型數據部分的一條語句的左邊，右邊是集名（用來輸出該集的所有成員名）或集屬性名（用來輸出該集屬性的值）。我們把用接口函數產生輸出的數據聲明稱為輸出操作。輸出操作僅當求解器求解完模型后才執(zhí)行，執(zhí)行次序取決于其在模型中出現(xiàn)的先后。第49頁，共65頁，2023年，2月20日，星期六例借用例4.12，說明@text的用法。model:sets:days/mon..sun/:required,start;endsetsdata:!每天所需的最少職員數;required=20161316191412;@text('d:\out.txt')=days'至少需要的職員數為'start;enddata!最小化每周所需職員數;min=@sum(days:start);@for(days(J):@sum(days(I)|I#le#5:start(@wrap(J+I+2,7)))>=required(J));end第50頁，共65頁，2023年，2月20日，星期六例——Lingo與Excel的連接corps

需求量3537223241324338擁有量

B1B2B3B4B5B6B7B8depot60A16267425955A24953858251A35219743343A47673927141A52395726552A655228143capacity(i)V(i)demand(j)d(j)cost(i,j)c(i,j)number(i,j)n(i,j)第51頁，共65頁，2023年，2月20日，星期六3、@ole函數是從EXCEL中引入或輸出數據的接口函數，它是基于傳輸的OLE技術。OLE傳輸直接在內存中傳輸數據，并不借助于中間文件。例3——Lingo與Excel的連接@OLE可以同時讀集成員和集屬性（讀寫）@OLE只能讀一維或二維的Ranges絕對路徑@ole(‘data.xls’);相對路徑@ole(‘D:\data.xls’);例題第52頁，共65頁，2023年，2月20日，星期六求的最大值？用Lingo軟件求解Lingo結果中其它項的意思！更多信息例1——加工奶制品的生產計劃第53頁，共65頁，2023年，2月20日，星期六第54頁，共65頁，2023年，2月20日，星期六第55頁，共65頁，2023年，2月20日，星期六第56頁，共65頁，2023年，2月20日，星期六Globaloptimalsolutionfoundatiteration:3Objectivevalue:280.0000

VariableValueReducedCostDESKS2.0000000.000000TABLES0.0000005.000000CHAIRS8.0000000.000000

RowSlackorSurplusDualPrice1280.00001.000000224.000000.00000030.00000010.0000040.00000010.0000055.0000000.000000

“ReducedCost”列出最優(yōu)單純形表中判別數所在行的變量的系數，表示當變量有微小變動時,目標函數的變化率。其中基變量的reducedcost值應為0，對于非基變量Xj,相應的reducedcost值表示當某個變量Xj增加一個單位時目標函數減少的量(max型問題)。本例中：變量tables對應的reducedcost值為5，表示當非基變量tables的值從0變?yōu)?時（此時假定其他非基變量保持不變,但為了滿足約束條件，基變量顯然會發(fā)生變化），最優(yōu)的目標函數值=280-5=275?！癡alue”給出最優(yōu)解中各變量的值：造2個書桌（desks）,0個餐桌（tables）,8個椅子（chairs）。所以desks、chairs是基變量（非0），tables是非基變量（0）。第57頁，共65頁，2023年，2月20日，星期六第58頁，共65頁，2023年，2月20日，星期六靈敏度的分析第59頁，共65頁，2023年，2月20日，星期六第60頁，共65頁，2023年，2月20日，星期六靈敏度分析的結果是Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseDESKS60.0000020.000004.000000