最優(yōu)化模型計算

最優(yōu)化模型計算第一頁，共三十頁，編輯于2023年，星期三LINGO的菜單與參數(shù)設置LINGO的主界面上有一個工具條，其上有一些按鈕按鈕的功能自左往右依次為：第二講最優(yōu)化問題的LINGO建模在線幫助、上下文幫助新建、打開、保存、打印剪切、復制、粘貼取消、重做查找、定位、括號匹配求解、顯示解答、模型圖示、選項設置窗口后置、關閉所有窗口、平鋪窗口用戶可以通過3種不同方式執(zhí)行LINGO操作，一是工具條按鈕，二是菜單選擇，三是快捷鍵第二頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模文件（File）菜單新建(New)：創(chuàng)建一個新的“Model”窗口，輸入待求解的模型； 打開(Open)：打開一個已經(jīng)存在的一個模型文件或者文本文件

保存(Save)：將當前窗口中的模型、結果、命令序列等保存為文件； 另存為(SaveAs)：將當前窗口中的內(nèi)容保存為指定格式文件； 關閉(Close)：關閉當前窗口打印(Print)：打印當前窗口的內(nèi)容 打印設置(PrintSetup)：設置打印格式 打印預覽(PrintPreview)：預覽待打印內(nèi)容輸出到日志文件(LogOutput)：將之后在命令窗口輸入的所有命令，保存到一個日志文件TakeCommands：將LINGO命令的腳本文件提交給系統(tǒng)進程運行； ImportLingo：打開一個LINGO格式的模型文件，并轉化為LINGO程序ExportFile：輸出MPS或MPI格式文件，其中MPS是IBM開發(fā)的數(shù)學規(guī)劃格式，MPI是LINGO制定的數(shù)學規(guī)劃格式第三頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模編輯（Edit）菜單粘貼特定(PasteSpecial)：將Windows剪貼板中的內(nèi)容插入到光標所在位置，以方便瀏覽，所插入內(nèi)容不參與LINGO程序的運行GoToLine：將光標移動到指定行粘貼函數(shù)(PasteFunction)：將LINGO的內(nèi)部函數(shù)粘貼到當前插入點匹配括號(MatchParenthesis)：在程序中選擇一個括號，查找與其匹配的另一半括號插入新對象(InsertNewObject)：新建或將一個已存在文件作為鏈接對象插入到當前位置； 連接(Link)：修改插入對象的連接性質；對象性質(ObjectProperties)：選擇一個鏈接或插入對象，查看或修改該對象的屬性SelectFont：控制顯示字體、字形、大小、顏色、效果等第四頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模Lingo菜單求解模型(Slove)：將當前模型送入內(nèi)存求解靈敏性分析(Range)：產(chǎn)生當前模型的靈敏性分析，給出最優(yōu)解不變時，目標函數(shù)系數(shù)的變化范圍；在影子價格和最優(yōu)基不變的條件下，約束右端常數(shù)項的變化范圍。靈敏性分析影響速度，且需要先激活1模型通常形式(Generate)：生成當前LINGO模型的代數(shù)表達式的完整形式，相當于編譯選項(Options)：打開含7個選項卡的對話框，可以設置LINGO界面，以及求解模型的80-90個控制參數(shù)求解結果(Solution)：打開求解結果的對話框，選擇用文本或圖表方式查看內(nèi)存中的求解結果1調(diào)試(Debug)：當求解結果為無可行解或目標函數(shù)無界時，執(zhí)行調(diào)試命令尋找錯誤1模型統(tǒng)計(ModelStatistics)：顯示模型統(tǒng)計資料；查看(Look)：以文本方式顯示模型內(nèi)容第五頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模窗口(Windows)菜單命令行窗口(CommandWindows)：在“：”提示符后可以輸入LINGO的命令行命令狀態(tài)窗口(StatusWindows)：用LINGO求解模型時，它會調(diào)用適當?shù)那蠼馄?，該命令顯示求解器的狀態(tài)，以監(jiān)視求解器的進展和模型大小等Variables：Total總變量數(shù)，Nonlinear非線性變量數(shù)，Integers整數(shù)變量數(shù)Constraints：Total總約束數(shù)，Nonlinear非線性約束數(shù)Total：Total總非零參數(shù)數(shù)，Nonlinear非線性非零參數(shù)數(shù)中斷求解器(InterruptSolver)：讓LINGO在下一次迭代時停止求解第六頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模LINGO的參數(shù)設置Interface(界面)選項GeneralSolver(通用求解器)選項第七頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模LINGO的參數(shù)設置LinearSolver(線性求解器)選項NonlinearSolver(非線性求解器)選項第八頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模LINGO的參數(shù)設置IntegerPre-Solver(整數(shù)預處理求解器)選項IntegerSolver（整數(shù)求解器）選項第九頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模LINGO的參數(shù)設置GlobalSolver(全局最優(yōu)求解器)選項第十頁，共三十頁，編輯于2023年，星期三

LPQPNLPIP

ILPIQPINLP

LINGO軟件的求解過程

LINGO預處理程序線性優(yōu)化求解程序非線性優(yōu)化求解程序分枝定界管理程序1.確定常數(shù)2.識別類型1.單純形算法2.內(nèi)點算法(選)1、順序線性規(guī)劃法(SLP)2、廣義既約梯度法(GRG)(選)

3、多點搜索(Multistart)(選)

第二講最優(yōu)化問題的LINGO建模全局優(yōu)化(選)第十一頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模LINGO的集合定義與應用在建模過程中，總會遇到一群或多群相聯(lián)系的對象，LINGO允許把這些相聯(lián)系的對象聚合成集(sets)。借助于集，可以將諸多相似的約束僅用一個簡明的復合公式來表示，從而快速方便地建立規(guī)模較大的模型，發(fā)揮LINGO建模語言的優(yōu)勢。LINGO有兩種集：原始集(primitiveset)由一些最基本的對象組成；派生集(derivedset)是由一個或多個其它集生成得到的集合段是LINGO模型的一個可選部分；集合段以關鍵字“sets:”開始，以“endsets”結束；一個模型可以沒有集合段、一個簡單的集合段或者多個集合段；集合段可以在模型的任何地方，但是集合及其屬性在模型約束中被引用前必須先定義。

第十二頁，共三十頁，編輯于2023年，星期三SETS：setname[/member_list/][:attribute_list];ENDSETS

原始集在定義時必須聲明·集的名字·集的成員(可選)·集的屬性(可選)

Setname是集的名字，具備較好可讀性。命名規(guī)則：以拉丁字母或下劃線（_）為首字符，其后由拉丁字母（A—Z）、下劃線、阿拉伯數(shù)字（0，1，…，9）組成的總長度不超過32個字符的字符串，不區(qū)分大小寫第二講最優(yōu)化問題的LINGO建模其中“[]”表示該部分內(nèi)容可選

Member_list是集成員列表。可以在集定義中，用顯式或隱式列舉2種方式給出；也可以在隨后的數(shù)據(jù)部分定義它們例2.1定義一個名為students的原始集，它具有成員John、Jill、Rose和Mike，屬性有sex（0表示女生、1表示男生）和age。第十三頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模SETS：STUDENTS/JOHN，JILL，ROSE，MIKE/:SEX，AGE;ENDSETS

法1顯式列舉：輸入每個成員名字，中間用空格或逗號擱開，允許混合使用

SETS：

setname/member1..memberN/[:attribute_list];ENDSETS

法2隱式列舉：不列舉每個成員，采用如下格式

其中member1是集的第一個成員名，memberN是集的最末一個成員名，LINGO自動產(chǎn)生中間的所有成員名。LINGO也接受一些特定的首成員名和末成員名，用于創(chuàng)建一些特殊的集。

第十四頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模sets:students:sex,age;endsetsdata: !數(shù)據(jù)段;students,sex,age=John116Jill014Rose017Mike113;enddata法3數(shù)據(jù)段列舉：集成員不放在集定義中，而在隨后的數(shù)據(jù)段來定義

SETS：STUDENTS/1..4/:SEX，AGE;ENDSETS

方法1和方法2在數(shù)據(jù)段，才對集合屬性進行賦值DATA：

SEX=1001；AGE=16141713;ENDDATA

在集合段只定義了一個集students，并未指定成員。在數(shù)據(jù)段定義了集成員John、Jill、Rose和Mike，并對屬性sex和age分別賦值第十五頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模派生集在定義時必須聲明·集的名字

·父集的名字

·集的成員(可選)·集的屬性(可選)SETS：setname(parent_set_list)[/member_list/][:attribute_list];ENDSETS

parent_set_list是已定義的集的列表，多個時須用逗號隔開；派生集的父集既可以是原始集，也可以是其它的派生集。member_list如果沒有指定集合成員列表，那么LINGO會自動創(chuàng)建父集成員的所有組合作為派生集成員。這樣的派生集稱為稠密集

如果限制派生集的成員，使它成為父集成員所有組合的一個子集，這樣的派生集稱為稀疏集稀疏集可以用兩種方式來定義：直接列舉法和元素過濾法。下面各舉一例加以說明。第十六頁，共三十頁，編輯于2023年，星期三設給定的7項工作構成集合TASK，4個屬性TIME、ES、LS、SLACK分別表示工作持續(xù)時間、最早開始時間、最晚開始時間、時間差LS減ES第二講最優(yōu)化問題的LINGO建模例2.2某投資公司正在準備開發(fā)一個新項目，需要完成方案設計(Design)、需求預測(Forecast)、競爭力評估(Survey)、價格設置(Price)、流水線規(guī)劃(Schedule)、成本支出(CostOut)、銷售培訓(Train)等7項工作。完成各項工作所需時間和工作間順序如下請根據(jù)項目的PERT計劃網(wǎng)絡，確定關鍵路徑。第十七頁，共三十頁，編輯于2023年，星期三派生集PRED是由2個基本集TASKS為父集構成的第二講最優(yōu)化問題的LINGO建模SETS：

TASKS:TIME,ES,LS,SLACK;PRED(TASKS,TASKS);ENDSETSDATATASKS=DESIGN,FORECAST,SURVEY,PRICE,SCHEDULE,COSTOUT,TRAIN;TIME=10,14,3,3,7,4,10;PRED=DESIGN,FORECASTDESIGN,SURVEY,FORECAST,PRICE,FORECAST,SCHEDULE,SURVEY,PRICE,SCHEDULE,COSTOUT,PRICE,TRAIN,COSTOUT,TRAIN;ENDDATA模型的集合段和數(shù)據(jù)段如下基本集TASK的成員不在定義中列出，而在隨后的數(shù)據(jù)段進行定義稀疏派生集PRED的成員，可以在集合段中通過元素列舉法定義，也可以在數(shù)據(jù)段中用元素列舉法定義第十八頁，共三十頁，編輯于2023年，星期三設8名調(diào)查員構成基本集ANALYSTS；派生集PAIRS是由2個ANALYSTS為父集構成的稀疏集，其屬性RATING為效率矩陣，MATCH(i，j)=1表示調(diào)查員i和j組成一隊，0表示不組隊。例2.3匹配問題：8名調(diào)查員準備分成4個調(diào)查隊（每隊兩人）前往4個地區(qū)進行社會調(diào)查。設兩兩之間組隊的效率如表所示（由于對稱性只列出了上三角部分），問如何組隊可以使總效率最高？則模型的集合段和數(shù)據(jù)段可以表示為第二講最優(yōu)化問題的LINGO建模第十九頁，共三十頁，編輯于2023年，星期三基本集ANALYSTS只規(guī)定了集合成員，而沒有集合屬性SETS：

ANALYSTS/1..8/;PAIRS(ANALYSTS,ANALYSTS)|&2#GT#&1:RATING,MATCH;ENDSETSDATARATING=9342156173521442921552876234;ENDDATA派生集是稀疏集時，可以用豎線“|”來標記一個元素過濾器的開始?！?1”、“&2”分別表示派生集的第1、2個父集的索引，它可以取遍該父集的所有成員；“#GT#”是邏輯運算符，用來判斷是否“大于”SETS：

setname(parent_set_list)[|邏輯表達式][/member_list/][:attribute_list];ENDSETS左邊是用元素過濾器定義稀疏派生集的一般形式，元素過濾器是一個邏輯表達式，將不滿足邏輯表達式的元素排除在派生集成員之外第二講最優(yōu)化問題的LINGO建模第二十頁，共三十頁，編輯于2023年，星期三集操作函數(shù)包括@in()、@index()、@wrap()、@size()四個第二講最優(yōu)化問題的LINGO建模LINGO的集合函數(shù)LINGO的集合函數(shù)分為兩類：集操作函數(shù)與集循環(huán)函數(shù)@in(set_name,primitive_index_1[,primitive_index_2,…])如果集合set_name中包含成員primitive_index_1[,primitive_index_2,…]所對應的元素，則返回1；否則返回0。@index([set_name,]primitive_set_element))返回在集set_name中的成員primitive_set_element的索引@wrap(index,limit)返回index模limit再加1。該函數(shù)常用于循環(huán)、多階段計劃@size(set_name)返回集set_name的成員個數(shù),即確定集的大小第二十一頁，共三十頁，編輯于2023年，星期三集循環(huán)函數(shù)包括@for()、@sum()、@min()、@max()第二講最優(yōu)化問題的LINGO建模集循環(huán)函數(shù)遍歷整個集進行操作。其語法為@function(set_name[(set_index_list)[|conditional_qualifier]]:expression);@for(set_name[(set_index_list)[|conditional_qualifier]]:expression_list);

表示對集合set_name中的每個滿足conditional_qualifier的成員構造一個由expression確定的約束條件表達式其中@function為上面的四個集循環(huán)函數(shù)之一；set_name是要遍歷的集合；set_index_list是集索引列表；conditional_qualifier是用來限制集循環(huán)函數(shù)的范圍，當集循環(huán)函數(shù)遍歷集的每個成員時，LINGO都要對conditional_qualifier進行評價，若結果為真，則對該成員執(zhí)行@function操作，否則跳過，繼續(xù)執(zhí)行下一次循環(huán)；expression是被應用到每個集成員的表達式set_index_list是可選項，如果不用，表達式expression將被應用到集的每個成員@for()函數(shù)的expression可以包含多個表達式，它們之間用分號隔開，這些表達式都將作為模型中的約束第二十二頁，共三十頁，編輯于2023年，星期三接下來，我們將通過一系列實際問題的建模過程，逐步學習、掌握集合與集合函數(shù)的應用方法和技巧第二講最優(yōu)化問題的LINGO建模@sum(set_name[(set_index_list)[|conditional_qualifier]]:expression);

表示對集合set_name中每個滿足conditional_qualifier的成員,分別得到一個由表達式expression確定的值，返回所有這些值的和@min(set_name[(set_index_list)[|conditional_qualifier]]:expression);

表示對集合set_name中每個滿足conditional_qualifier的成員,分別得到一個由表達式expression確定的值，返回所有這些值的最小值@max(set_name[(set_index_list)[|conditional_qualifier]]:expression);

表示對集合set_name中每個滿足conditional_qualifier的成員,分別得到一個由表達式expression確定的值，返回所有這些值的最大值例2.2的LINGO模型程序如下第二十三頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模SETS:TASKS:TIME,ES,LS,SLACK;PRED(TASKS,TASKS);ENDSETSDATA:TASKS=DESIGN,FORECAST,SURVEY,PRICE,SCHEDULE,COSTOUT,TRAIN;TIME=10,14,3,3,7,4,10;PRED=DESIGN,FORECAST, DESIGN,SURVEY, FORECAST,PRICE,FORECAST,SCHEDULE, SURVEY,PRICE, SCHEDULE,COSTOUT,PRICE,TRAIN,COSTOUT,TRAIN;ENDDATA@FOR(TASKS(J)|J#GT#1:ES(J)=@MAX(PRED(I,J):ES(I)+TIME(I)));@FOR(TASKS(I)|I#LT#LTASK:LS(I)=@MIN(PRED(I,J):LS(J)-TIME(I)));@FOR(TASKS(I):SLACK(I)=LS(I)-ES(I));ES(1)=0;LTASK=@SIZE(TASKS);LS(LTASK)=ES(LTASK);第1個@FOR函數(shù)計算工作j的最早開始時間第2個@FOR函數(shù)計算工作i的最遲開始時間第3個@FOR函數(shù)計算工作i的最遲-最早開始時間差本模型沒有目標函數(shù)，只有一些約束條件，程序執(zhí)行時僅僅需要進行簡單計算第二十四頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模例2.3的LINGO模型程序如下MODEL:SETS:

ANALYSTS/1..8/;PAIRS(ANALYSTS,ANALYSTS)|&2#GT#&1:RATING,MATCH;ENDSETSDATA:RATING=9342156,173521,442921552,876,23,4;ENDDATAMIN=

@SUM(PAIRS(I,J):RATING(I,J)*MATCH(I,J));@FOR(ANALYSTS(I):@SUM(PAIRS(J,K)|J#EQ#I#OR#K#EQ#I:MATCH(J,K))=1);@FOR(PAIRS(I,J):@BIN(MATCH(I,J)));END第2個父集元素的索引(用&2表示)大于第1個父集元素的索引(用&1表示)時，作為派生集的成員第1個@FOR函數(shù)保證每個調(diào)查員I在而且只能在一個調(diào)查組。第2個@FOR函數(shù)確定集合MATCH的元素只能取0或1。第二十五頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模例2.4選址問題：某公司有6個建筑工地，位置坐標為(ai,bi)(單位：公里),水泥日用量di

(單位：噸）由下表給出，假設：料場和工地之間有直線道路公司目前有2個臨時存放水泥的場地(簡稱料場)，分別位于A(5,1)和B(2,7)，記為(xi,yi)(i=1,2)，日儲量ei

各有20噸。（1）制定每天的供應計劃，即從A,B兩料場分別向各工地運送多少噸水泥，可以使總的噸公里數(shù)最小。

（2）為進一步減少噸公里數(shù)，打算舍棄目前的2個臨時料場，改建2個新料場，日儲量仍各為20噸，問建在何處最好？（1）設決策變量cij表示料場j到工地i的運量，這是一個12維的變量第二十六頁，共三十頁，編輯于2023年，星期三第二講最優(yōu)化問題的LINGO建模因為料場到各工地的距離是常數(shù)，目標函數(shù)和約束條件也都是常數(shù)，所以該模型是線性規(guī)劃模型MODEL:SETS:

gd/1..6/:a,b,d;!定義6個工地;

lch/A,B/:x,y,e;!定義2個料場;

links(gd,lch):c;!c為運量;

ENDSETSDATA:a=1.258.750.55.7537.25;b=1.250.754.7556.57.75;!工地位置;

d=3547611;!工地水泥需求;

x=52;y=17;!料場位置;

e=2020;!料場日存儲量;

ENDDATAMIN=@SUM(links(i