優(yōu)化模型的三要素

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

2、約束束條條件件，由由該該問問題題對(duì)對(duì)決決策策變變量量的的現(xiàn)現(xiàn)實(shí)實(shí)條條件件給給出出，即即 允允許許的的取取值值范范圍圍為為， 稱稱為為可可行行域域，常常用用一一組組關(guān)關(guān)于于 的的等等式式和和（或或）不不等等式式0 0來來界界定定，分分別別稱稱為為等等式式約約束束和和不不等等式式約約束束。優(yōu)化模型的三要素01 201 2optzf( x)s.t.h( x)i, ,mg( x)j, ,n于是，優(yōu)化模型從數(shù)學(xué)上可以表述為于是，優(yōu)化模型從數(shù)學(xué)上可以表述為 這里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至少有一個(gè)是非線性，則為非線性規(guī)劃（至少有一個(gè)是非線性，則為非線性規(guī)劃（NLP） c） f 是二次函數(shù)是二次函數(shù),hi ,gi 都是線性，則為二次規(guī)劃（都是線性，則為二次規(guī)劃（QP）2.2.決策變量決策變量x的的一個(gè)或多個(gè)分量的的一個(gè)或多個(gè)分量xi取離散值取離散值 a） x的至少一個(gè)分量只取整數(shù)數(shù)值，則為整數(shù)規(guī)

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

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

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

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

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

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

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

11、30個(gè)，這在我們目前的使用過程中，基本上是足夠。優(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實(shí)際上還是一種建模語言，即使對(duì)優(yōu)化方面的專業(yè)知識(shí)了解不多的用戶，也能方便的進(jìn)行輸入、求解，并能快速的得到復(fù)雜優(yōu)化問題的高質(zhì)量的解。優(yōu)化模型的三要素解決一個(gè)簡(jiǎn)單的線性規(guī)劃（解決一個(gè)簡(jiǎn)單的線性規(guī)劃（LP）問題）問題23431035120maxzxyxys.t.xyx,yLingo/Lindo軟件介紹 -Lindo其Lindo程序?yàn)椋豪?3優(yōu)化模型的三要素Lingo/Lindo軟件介紹 -LindoLin

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

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

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

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

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

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

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

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

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