1、優(yōu)化模型的三要素F優(yōu)化模型的三要素優(yōu)化模型的三要素優(yōu)化模型優(yōu)化模型xf( x)（2 2）目目標標函函數(shù)數(shù)，通通常常是是某某一一問問題題需需要要優(yōu)優(yōu)化化（最最大大或或最最小小）的的那那個個目目標標的的數(shù)數(shù)學學表表達達式式，它它是是決決策策變變量量 的的函函數(shù)數(shù)，可可以以 抽抽象象的的記記作作；12nnxx ,x ,xxT T（1 1）決決策策變變量量，通通常常是是某某一一問問題題需需要要求求解解的的未未知知量量，用用 維維向向量量 = =表表示示，當當對對 賦賦值值后后它它通通常常稱稱為為該該問問題題的的一一個個解解；01 21 2ijxxxh( x)i, ,mg ( x)j, ,n（3 3）約

2、約束束條條件件，由由該該問問題題對對決決策策變變量量的的現(xiàn)現(xiàn)實實條條件件給給出出，即即 允允許許的的取取值值范范圍圍為為， 稱稱為為可可行行域域，常常用用一一組組關關于于 的的等等式式和和（或或）不不等等式式0 0來來界界定定，分分別別稱稱為為等等式式約約束束和和不不等等式式約約束束。優(yōu)化模型的三要素01 201 2optzf( x)s.t.h( x)i, ,mg( x)j, ,n于是，優(yōu)化模型從數(shù)學上可以表述為于是，優(yōu)化模型從數(shù)學上可以表述為 這里opt 最優(yōu)化的意思，可以是min（求極大，即minamize的縮寫）或max （求極小，即minamize的縮寫）的兩者之一；s.t. （即su

3、bject to）“受約束于”之意。（1）（2）（3）優(yōu)化模型的三要素F優(yōu)化模型基本類型優(yōu)化模型基本類型1.1.決策變量決策變量x的所有分量的所有分量xi均為連續(xù)數(shù)值均為連續(xù)數(shù)值 a）f ,hi ,gi都是線性函數(shù)，則為線性規(guī)劃（都是線性函數(shù)，則為線性規(guī)劃（LP） b）f ,hi ,gi至少有一個是非線性，則為非線性規(guī)劃（至少有一個是非線性，則為非線性規(guī)劃（NLP） c） f 是二次函數(shù)是二次函數(shù),hi ,gi 都是線性，則為二次規(guī)劃（都是線性，則為二次規(guī)劃（QP）2.2.決策變量決策變量x的的一個或多個分量的的一個或多個分量xi取離散值取離散值 a） x的至少一個分量只取整數(shù)數(shù)值，則為整數(shù)規(guī)

4、劃（的至少一個分量只取整數(shù)數(shù)值，則為整數(shù)規(guī)劃（IP） b） x的分量限定只取整數(shù)的分量限定只取整數(shù)0或或1，則為，則為0-1規(guī)劃（規(guī)劃（ZOP）3.3.此外，為了解決實際問題的需要，還可以分為：此外，為了解決實際問題的需要，還可以分為：單目標規(guī)劃，多目標規(guī)劃，動態(tài)規(guī)劃，多層規(guī)劃等。單目標規(guī)劃，多目標規(guī)劃，動態(tài)規(guī)劃，多層規(guī)劃等。 111 201 2niiiniiiiiiimin fxc x ,i, ,.,na xb ,b ,b,s.t.x,i, ,.,n（1）線性規(guī)劃（）線性規(guī)劃（LP）的一般形式）的一般形式目標函數(shù)和所有的約束條件都是變量的線性目標函數(shù)和所有的約束條件都是變量的線性函數(shù)。函數(shù)。

5、常用的優(yōu)化模型形式（2）二次規(guī)劃問題）二次規(guī)劃問題目標函數(shù)為二次函數(shù)，約束條件為線性約束。目標函數(shù)為二次函數(shù)，約束條件為線性約束。 1111201 2nniiijijii,jniiiiiiimin fxc xb x xa xb ,b ,b.s.t. x.i, j, ,.,n.常用的優(yōu)化模型形式1456750 xxxxx例-1 某服務部門一周中每天需要不同數(shù)目的雇員：周一到周四每天至少需要50人，周五需要80人，周六和周日需要90人?，F(xiàn)規(guī)定應聘者需連續(xù)工作5天，試確定聘用方案，即周一到周日每天聘用多少人，是5在滿足需要的前況下聘用總人數(shù)最少？優(yōu)化模型 決策變量：記周一到周日每天聘用的人數(shù)分別為X

6、1，X2，X3，X4，X5，X6 ，X7，這就是問題的決策變量。 目標函數(shù)：目標函數(shù)即是聘用總人數(shù)，即 約束條件：由每天需要的人數(shù)確定。由于每人連續(xù)工作五天，所以一周的雇員應該是周四到周一聘用的，按照需要至少50人，于是1234567zxxxxxxx125671236712347123452345634567505050809090 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 類似的，有顯然，人數(shù)應該是正整數(shù)，所以01,2,7ixi 問題歸結為在以上約束條件下求解min z的整數(shù)規(guī)劃模型。由于目標函數(shù)和約束條件關于決策變量都是線性函數(shù)，所以這是一個整數(shù)向行規(guī)劃模型。例-2 某

7、班準備從5名游泳隊員中選擇4人組成接力隊，參加學校的4*100混合泳接力比賽。5名隊員4中泳姿的百米平均成績?nèi)缦卤硭?，問應該如何選拔隊員組成接力隊？表一 ：5名隊員4中泳姿百米平均成績隊員甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4問題分析：問題要求從5名隊員中選出4人組成接力隊，每人一種泳姿，且四人的泳姿各不相同，使接力隊成績最好。容易想到窮舉法，組成接力隊的方案有5！=120中，逐一計算并做比較即可找出最優(yōu)方案。顯然這不是解決問

8、題的最好方法，隨著問題規(guī)模的變大，窮舉法的計算量是無法接受的。 可以用0-10-1變量表示一個隊員是否入選接力隊，從而建立這個問題的0-10-1規(guī)劃模型規(guī)劃模型. . 記甲、乙、丙、丁、戊分別為隊員 i=1，2，3，4，5；記蝶泳、仰泳、蛙泳、自由泳分別為泳姿 j=1，2，3，4；記隊員 i 的第 j 種泳姿的百米成績?yōu)?cij（s），），則表一可以表示成為：表二 ：5名隊員4中泳姿百米平均成績隊員甲乙丙丁戊蝶泳66.857.2787067.4仰泳75.66667.874.271蛙泳8766.484.669.683.8自由泳58.65359.457.262.4 目標函數(shù)：當隊員隊員 i 入選泳

9、姿 j 的比賽時， cij xij表示他的成績，否則cij xij=0。于是接力隊的成績可以表示為： 決策變量：引入0-1變量xij 若選擇隊員 i 參加泳姿 j 的比賽，記 xij=1，否則記 xij=0.這就是問題的決策變量，共20個。每人最多只能入選4種泳姿之一，即對于員 i=1，2，3，4，應該有： 約束條件：根據(jù)組成接力隊的要求， xij 應該滿足下面兩個約束條件：4511ijijjifc x411ijjx每種泳姿有且只能有1人入選，即對于員 j=1，2，3，4，5，應該有：511ijix綜上所述，這個問題的優(yōu)化模型可以寫作：45114151min;1,1,2,3,4,5;. .1,

10、1,2,3,4;0,1 ;ijijjiijjijiijc xxistxjx 這是一個線性0-1 規(guī)劃模型，它是一個特殊的線性整數(shù)規(guī)劃。優(yōu)化模型的三要素Lingo/Lindo軟件介紹 這套軟件包由美國芝加哥大學的Linus Scharge教授于1980年前后開發(fā)，專門用于求解最優(yōu)化問題，后經(jīng)不斷完善和擴充，并成立LINDO公司進行商業(yè)化運作，取得了巨大的成功。全球財富雜志500強的企業(yè)中，一半以上使用該公司產(chǎn)品，其中前25強企業(yè)中有23家使用該產(chǎn)品。該軟件包功能強大，版本也很多，而我們 使用的只是演示版（試用版），演示版與正式版功能基本上是 類似的，只是能夠求解問題的規(guī)模受到限制，總變量數(shù)不超過

11、30個，這在我們目前的使用過程中，基本上是足夠。優(yōu)化模型的三要素Lingo/Lindo軟件介紹Lingo/Lindo軟件求解的優(yōu)化模型類型見下圖：優(yōu)化模型優(yōu)化模型連續(xù)模型連續(xù)模型整數(shù)模型整數(shù)模型線性規(guī)劃線性規(guī)劃二次規(guī)劃二次規(guī)劃非線性規(guī)劃非線性規(guī)劃LindoLingo優(yōu)化模型的三要素Lingo/Lindo軟件介紹Lindo是英文Linear Interactive and Discrete Optimizer字首的縮寫，即“交互式的線性和離散優(yōu)化求解器”，可以用來求解線性規(guī)劃（LP）和二次規(guī)劃（QP）；Lingo是英文Linear Interactive and General Optimize

12、r字首的縮寫，即“交互式的線性和通用優(yōu)化求解器”，它除了具有Lindo的全部功能外，還可以用來求解非線性規(guī)劃。Lingo和Lindo的最大特色在于可以允許決策變量是整數(shù)，而且執(zhí)行速度很快；Lingo實際上還是一種建模語言，即使對優(yōu)化方面的專業(yè)知識了解不多的用戶，也能方便的進行輸入、求解，并能快速的得到復雜優(yōu)化問題的高質(zhì)量的解。優(yōu)化模型的三要素解決一個簡單的線性規(guī)劃（解決一個簡單的線性規(guī)劃（LP）問題）問題23431035120maxzxyxys.t.xyx,yLingo/Lindo軟件介紹 -Lindo其Lindo程序為：例-3優(yōu)化模型的三要素Lingo/Lindo軟件介紹 -LindoLin

13、do程序以“MAX”（ 或“MIN”）表示目標是求最大化（最小化）問題，后面直接寫目標函數(shù)的表達式和約束的表達式條件，目標函數(shù)和約束之間以“ST”分開；程序以“END” （也可以省略）結束；輸入格式與數(shù)學模型表達式幾乎完全一樣，連系數(shù)之間的乘號都一樣省略了，而且必須省略；在Lindo模型中的書寫是相當靈活的；并且Lindo中已假定所有變量非負，也不區(qū)分大小寫；約束條件中的“=”及“”“”代替；輸入的多于空格和回車也會被忽略；一行中“！”后面的文字將被認為是說明語句，不參與模型的建立，主要目的是增加程序的可讀性。我們從這段程序可以看出我們從這段程序可以看出Lindo模型有以下特點：模型有以下特點

14、：優(yōu)化模型的三要素現(xiàn)在我們用Lindo軟件來求解這個模型，單擊工具欄中的 圖標，便得到以下運行狀態(tài)窗口：Lindo求解器運行狀態(tài)窗口各項的含義名稱含義Status顯示當前求解狀態(tài)：Optimal表示已經(jīng)達到最優(yōu)解；其他可能的顯示：Feasible，Infeasible，UnboundedIterations顯示迭代次數(shù)Infeasibility 約束不滿足的量；0表示這個解是可行的Objective顯示當前解的目標函數(shù)值Best IP顯示整數(shù)規(guī)劃當前解的最佳標函數(shù)值：N/A表示無答案或無意義IP Bound顯示整數(shù)規(guī)劃的界Branches顯示分支定界算法已經(jīng)計算的分支數(shù)： N/A表示無答案或無

15、意義Elapsed Time顯示計算所用時間：0：00說明計算太快，用時還不到0.05SUpdate Time顯示控制和刷新本界面的時間間隔Interrupt Solver中斷求解程序Close關閉該窗口優(yōu)化模型的三要素顯示結果如下單純行法迭代兩次得到最優(yōu)解最優(yōu)目 標值最優(yōu)解各變量 的值對偶價格影子價格：表示該非基變量增加一個單位而其他變量不變時目標函數(shù)減少的量（對max型問題）松弛變量的值【緊約束】單純行法進行兩次迭代優(yōu)化模型的三要素Lingo/Lindo軟件介紹 -Lindo變量以字母開頭、不區(qū)分大小寫，變量名可不超過8個字符；變量不能出現(xiàn)在約束條件的右端，右端只能是常數(shù)；變量與系數(shù)之間可

16、以有空格，但絕對不能有任何運算符；Lindo中不接受”（）“和逗號 ”，“等任何運算符號（除非在注釋語句中）；模型中的表達式應當經(jīng)過化，如不能出現(xiàn) （X+1）2 + 2X2 + 3Y，而應該寫成3X2+2X+3Y+1；模型中已假定所有變量非負，可在模型的 ”end“語句后面用命令”free“取消變量的非負假定，其用法是在”free“后面跟變量名；在模型的 ”end“語句后面可以用命令”SUB“設定變量的上界，用命令”SLB“設定變量的下界；Lindo中以“！”開始的是說明語句，說明語句也以“ ;” 結束。使用使用Lindo軟件的一些注意事項：軟件的一些注意事項：優(yōu)化模型的三要素Lingo/Li

17、ndo軟件介紹 -Lindo下面我們用一個例子來說明下面我們用一個例子來說明Lindo中三個變量范圍限制命令（中三個變量范圍限制命令（FREE、SBU、SLB）的作用和使用方法：）的作用和使用方法：例-4 max 234. .4321035125852020,30 xyzS Txyzyyzxyzxyzyz 在這個模型中，對變量x沒有非負限制，對y有上限限制，對z有下限限制；分別用FREE、SBU、SLB三個命令可以實現(xiàn)這些功能。具體輸入如下：優(yōu)化模型的三要素圖a：例4的輸入模型圖b：例4的輸出結果優(yōu)化模型的三要素Lingo/Lindo軟件介紹 -Lingo Lingo9.0軟件比以前的版本有了

18、很大的改進，功能大大增強，性能更加穩(wěn)定，結果更加可靠；從基本更能上看，與Lindo相比，Lingo軟件主要具備以下優(yōu)點：除具備Lindo餓全部功能外，還可以用于求解非線性規(guī)劃問題；Lingo包含了內(nèi)置的建模語言，允許以簡練、直觀的方式描述較大規(guī)模的優(yōu)化問題，模型中所需的數(shù)據(jù)可以以一定的格式保存在獨立的文件中。 事實上，Lindo公司目前已經(jīng)將Lindo軟件從其產(chǎn)品目錄中刪除，而將Lindo軟件的所有功能都在Lingo中得到了支持，所以在不久的將來總有一天人們會廢棄Lindo軟件不再使用，但Lingo的生命力應該還是很頑強的！優(yōu)化模型的三要素Lingo/Lindo軟件介紹 -Lingo對前面的線

19、性規(guī)劃模型，編寫對前面的線性規(guī)劃模型，編寫Lingo程序如下：程序如下：優(yōu)化模型的三要素點擊圖標 運行，屏幕上顯示運行狀態(tài)窗口如下：對于Lingo運行狀態(tài)窗口，我們給于以下解釋：u變量數(shù)目：變量總數(shù)（Total）、非線型變量數(shù)（Nonlinear）、整數(shù)變量數(shù)（Integer）u約束變量：約束總數(shù)（ Total ）、非線性約束個數(shù)（Nonlinear）u非線性系數(shù)數(shù)量：總數(shù)（ Total ）、非線性項的系數(shù)個數(shù)（Nonlinear）u內(nèi)存使用量：單位為千字節(jié)u求解花費時間：顯示格式“時:分:秒:”優(yōu)化模型的三要素Lingo狀態(tài)窗口中關于求解器各項的含義域名含義可能顯示的值Model Class

20、 當前模型類型LP、QP、ILP、IQP、PILP、PIQP、NLP、INLP、PINLPState當前解的狀態(tài)Global Optimum、Local Optimum、Feasible、Infeasible（不可行）、Unbounded（無界）、Interrupted（中斷）、undetermined（未確定）Objective當前解的目標函數(shù)值實數(shù)Infeasibility當前約束不滿足的量實數(shù)Iterations目前為止迭代的次數(shù)非負實數(shù)Lingo狀態(tài)窗口中關于擴展的求解器各項的含義域名含義可能顯示的值Solver Type使用的特殊求解程序B-and-B（分支定界法）Global（全局

21、最優(yōu)求解程序）Multistart（用多個初始點求解的程序）Best Obj到目前為止找到的可行解最佳目標函數(shù)實數(shù)Steps特殊求解程序當前運行步數(shù)非負實數(shù)Active有效步數(shù)非負實數(shù)優(yōu)化模型的三要素Lingo/Lindo軟件介紹 -Lingo關閉求解狀態(tài)窗口，得到結果如下：關閉求解狀態(tài)窗口，得到結果如下：優(yōu)化模型的三要素Lingo/Lindo軟件介紹 -LingoLingo中變量不區(qū)分大小寫，變量名可以超過8個，不能超過32個，需以字母開頭；用Lingo解優(yōu)化模型時已假定所有變量非負（除非用限定變量范圍的函數(shù)free或bnd另行說明）；變量可以放在約束條件右端，同時數(shù)字也可以放在約束條件左邊；Lingo模型語句由一系列語句組成，每一個語句都必須以“;”結尾；Lingo中以“！”開始的是說明語句，說明語句也以“ ;” 結束。關于關于Lingo的基本用法的幾點注意事項：的基本用法的幾點注意事項：優(yōu)化模型的三要素Lingo/Lindo軟件介紹 -LingoABS（X）：絕對值函數(shù)，返回X的絕對值；EXP（X）：指數(shù)函數(shù)（以自然對數(shù)e為底），返回eX的值； LOG（X）：自然對數(shù)函數(shù)，返回X的自然對數(shù)值；POW（X，Y）：指數(shù)函數(shù)，返回XY的值；SQR（X）：平方函數(shù)，返回X的值；SQRT（ X ）：平方根函數(shù)，返回X