數(shù)學(xué)規(guī)劃模型的建立與求解

1、數(shù)學(xué)規(guī)劃模型的建立與求解數(shù)學(xué)規(guī)劃模型的建立與求解張興元2009 年 3 月數(shù)學(xué)規(guī)劃模型的建立與求解1優(yōu)化問(wèn)題及其一般模型優(yōu)化問(wèn)題及其一般模型 優(yōu)化問(wèn)題是人們?cè)诠こ碳夹g(shù)、經(jīng)濟(jì)管理和科學(xué)研究等領(lǐng)域中最常遇到的問(wèn)題之一。例如：n 設(shè)計(jì)師要在滿(mǎn)足強(qiáng)度要求等條件下選擇材料的尺寸， 使結(jié)構(gòu)總重量最輕；n 公司經(jīng)理要根據(jù)生產(chǎn)成本和市場(chǎng)需求確定產(chǎn)品價(jià)格， 使所獲利潤(rùn)最高；n 調(diào)度人員要在滿(mǎn)足物質(zhì)需求和裝載條件下安排從各 供應(yīng)點(diǎn)到需求點(diǎn)的運(yùn)量和路線，使運(yùn)輸總費(fèi)用最低；n 投資者要選擇一些股票、債券下注，使收益最大，而風(fēng)險(xiǎn)最小n 數(shù)學(xué)規(guī)劃模型的建立與求解一般地，優(yōu)化模型可以表述如下： min( ). .( )0i

2、zf xs tg x ， i i = =1 1, , 2 2, , , m m 這是一個(gè)多元函數(shù)的條件極值問(wèn)題，其中 x = x 1 , x 2 , , x n 。 許多實(shí)際問(wèn)題歸結(jié)出的這種優(yōu)化模型，但是其決策變量個(gè)數(shù) n 和約束條件個(gè)數(shù) m 一般較大，并且最優(yōu)解往往在可行域的邊界上取得，這樣就不能簡(jiǎn)單地用微分法求解，數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃就是解決這類(lèi)問(wèn)題的有效方法。 數(shù)學(xué)規(guī)劃模型的建立與求解2數(shù)學(xué)規(guī)劃模型分類(lèi)數(shù)學(xué)規(guī)劃模型分類(lèi)“數(shù)學(xué)規(guī)劃是運(yùn)籌學(xué)和管理科學(xué)中應(yīng)用及其廣泛的分支。在許多情況下，應(yīng)用數(shù)學(xué)規(guī)劃取得的如此成功，以致它的用途已超出了運(yùn)籌學(xué)的范疇，成為人們?nèi)粘５囊?guī)劃工具?！盚.P.Williams

3、.數(shù)學(xué)規(guī)劃模型的建立。 數(shù)學(xué)規(guī)劃包括線性規(guī)劃線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃整數(shù)規(guī)劃、幾何規(guī)劃、多目標(biāo)規(guī)劃等，用數(shù)學(xué)規(guī)劃方法解決實(shí)際問(wèn)題，就要將實(shí)際問(wèn)題經(jīng)過(guò)抽象、簡(jiǎn)化、假設(shè)，確定變量與參數(shù)，建立適當(dāng)層次上的數(shù)學(xué)模型，并求解。 數(shù)學(xué)規(guī)劃模型的建立與求解3建立數(shù)學(xué)規(guī)劃模型的步驟建立數(shù)學(xué)規(guī)劃模型的步驟當(dāng)你打算用數(shù)學(xué)建模的方法來(lái)處理一個(gè)優(yōu)化問(wèn)題的時(shí)候，首先要確定尋求的決策是什么，優(yōu)化的目標(biāo)是什么，決策受到那些條件的限制（如果有限制的話），然后用數(shù)學(xué)工具（變量、常數(shù)、函數(shù)等）表示它們，最后用合適的方法求解它們并對(duì)結(jié)果作出一些定性、定量的分析和必要的檢驗(yàn)。 數(shù)學(xué)規(guī)劃模型的建立與求解Step 1. 尋求決策，

4、即回答什么？必須清楚，無(wú)歧義尋求決策，即回答什么？必須清楚，無(wú)歧義。 閱讀完題目的第一步不是尋找答案或者解法，而是Step 2. 確定決策變量確定決策變量 第一來(lái)源：Step 1的結(jié)果，用變量固定需要回答的決策 第二來(lái)源：由決策導(dǎo)出的變量（具有派生結(jié)構(gòu)） 其它來(lái)源：輔助變量（聯(lián)合完成更清楚的回答）Step 3. 確定優(yōu)化目標(biāo)確定優(yōu)化目標(biāo) 用決策變量表示的利潤(rùn)、成本等。Step 4. 尋找約束條件尋找約束條件 決策變量之間、決策變量與常量之間的聯(lián)系。 第一來(lái)源：需求； 第二來(lái)源：供給； 其它來(lái)源：輔助以及常識(shí)。Step 5. 構(gòu)成數(shù)學(xué)模型構(gòu)成數(shù)學(xué)模型 將目標(biāo)以及約束放在一起，寫(xiě)成數(shù)學(xué)表達(dá)式。 數(shù)

5、學(xué)規(guī)劃模型的建立與求解【實(shí)例【實(shí)例 1 】：某儲(chǔ)蓄所每天的營(yíng)業(yè)時(shí)間是上午9:00到下午5:00。 根據(jù)經(jīng)驗(yàn)，每天不同時(shí)間段所需要的服務(wù)員數(shù)量如下：時(shí)間段（時(shí)）9-1010-1111-1212-11-22-33-44-5服務(wù)員數(shù)量43465688儲(chǔ)蓄所可以雇傭全時(shí)和半時(shí)兩類(lèi)服務(wù)員。全時(shí)服務(wù)員每天報(bào)酬100元，從上午9:00到下午5:00工作，但中午12:00到下午2:00之間必須安排1小時(shí)的午餐時(shí)間。儲(chǔ)蓄所每天可以雇傭不超過(guò)3名的半時(shí)服務(wù)員，每個(gè)半時(shí)服務(wù)員必須連續(xù)工作4小時(shí)，報(bào)酬40元。問(wèn)該儲(chǔ)蓄所應(yīng)如何雇傭全時(shí)和半時(shí)兩類(lèi)服務(wù)員？ 數(shù)學(xué)規(guī)劃模型的建立與求解Step 1：需要回答什么？：需要回答什么

6、？ 1. 雇傭的全時(shí)雇員數(shù)量和半時(shí)雇員數(shù)量； 2. 半時(shí)雇員開(kāi)始上班時(shí)間？（最早9:00，最晚1:00） 3費(fèi)用是多少？ Step2：決策變量？：決策變量？ 1全時(shí)雇員數(shù)量：x； 2每個(gè)時(shí)間開(kāi)始時(shí)雇傭的半時(shí)雇員數(shù)量：yi，i=1,2,5 3清楚嗎？漏掉了什么？ 全時(shí)雇員需要午餐。 4全時(shí)雇員數(shù)量分解：12點(diǎn)就餐：x1；1點(diǎn)就餐：x2注意：x1，x2為由決策導(dǎo)出的變量。 Step3Step3：目標(biāo)函數(shù)：目標(biāo)函數(shù) 目標(biāo)：支付報(bào)酬最少 支付報(bào)酬=全時(shí)員工報(bào)酬+半時(shí)員工報(bào)酬 Z=100(x1+x2)+40(y1+y2+y3+y4+y5)數(shù)學(xué)規(guī)劃模型的建立與求解Step4：約束條件：約束條件 需求：服務(wù)

7、員數(shù)量約束(8個(gè))； 供方約束：半時(shí)雇員約束：y1+y2+y3+y4+y53； 常規(guī)約束：非負(fù)整數(shù)。 Step5：數(shù)學(xué)模型：數(shù)學(xué)模型 12123451211212121232123412345123451245125123451212345100()40(). .434656883,0Minxxyyyyys txxyxxyyxxyyyxyyyyxyyyyxxyyyxxyyxxyyyyyyxxyyyyyZ 數(shù)學(xué)規(guī)劃模型的建立與求解發(fā)電站 A水庫(kù) B水庫(kù) A發(fā)電站 B水源 A水源B【實(shí)例【實(shí)例2】：某電力公司經(jīng)營(yíng)兩座發(fā)電站，發(fā)電站分別位于兩個(gè)水庫(kù)上，位置如右圖所示： 已知發(fā)電站可以將水庫(kù)A的1萬(wàn)立

8、方米的水轉(zhuǎn)換為400千度電能，發(fā)電站B只能將水庫(kù)B的1萬(wàn)立方米的水轉(zhuǎn)換為200千度電能。發(fā)電站A、B每個(gè)月的最大發(fā)電能力分別是60000千度、35000千度。每個(gè)月最多有50000千度電能夠以200元/千度的價(jià)格售出，多余的電能只能夠以140元/千度的價(jià)格售出。水庫(kù)A、B的其它有關(guān)數(shù)據(jù)如下表（單位：萬(wàn)立方米）。請(qǐng)你為該電力公司制定本月和下月的生產(chǎn)經(jīng)營(yíng)計(jì)劃。 水庫(kù) A水庫(kù) B水庫(kù)最大蓄水量20001500水源流入水量本本月20040下月13015水庫(kù)最小蓄水量1200800水庫(kù)目前蓄水量1900850數(shù)學(xué)規(guī)劃模型的建立與求解Step 1. Step 1. 尋求決策，即回答什么？尋求決策，即回答什

9、么？ 1. 水庫(kù)A、B本月和下月發(fā)電量（可以用水量表示）； 2. 電力公司的收益。 Step 3. Step 3. 確定優(yōu)化目標(biāo)確定優(yōu)化目標(biāo) 目標(biāo)：利潤(rùn)最大化。 利潤(rùn)=高價(jià)電利潤(rùn)+低價(jià)電利潤(rùn) P=200(u1+u2)+140(v1+v2) Step 2. Step 2. 確定決策變量確定決策變量 1.1. 水庫(kù)A、B本月和下月用于發(fā)電的水量：xA1，xA2，xB1，xB2 2. 收益導(dǎo)出決策變量： 本月和下月高價(jià)售電量：u1，u2；本月和下月低價(jià)售電量：v1，v2； 3. 輔助決策變量（水庫(kù)安全運(yùn)行）： 本月和下月水庫(kù)直接放走的水量：yA1，yA2，yB1，yB2； 本月和下月結(jié)束時(shí)水庫(kù)的水量

10、：zA1，zA2，zB1，zB2 數(shù)學(xué)規(guī)劃模型的建立與求解Step 4. 尋找約束條件尋找約束條件 1. 電量守恒：每月發(fā)電量=每月賣(mài)出量（2個(gè)） 2. 水量守恒： 發(fā)電用水量+直接放走量+庫(kù)存量=原有庫(kù)存量+來(lái)水量（4個(gè)） 3. 發(fā)電能力限制：4個(gè) 4. 水庫(kù)蓄水量限制：4個(gè) 5. 高價(jià)電量限制：2個(gè) Step 5. 構(gòu)成數(shù)學(xué)模型構(gòu)成數(shù)學(xué)模型 121211112222111111112221222122112212max 200()140(). . 400200, 4002001900200850401301595000 ,950040060000 , 400ABABAAABBBAAAAAA

11、BBBBAAAAuuvvs txxuvxxuvxyzxyzxyxyzzxyzzxyuvuvxx 1212121212121212121212126000020035000 , 2003500012002000 ,120020008001500 , 800150050000 ,50000,0BBAABBAABBAABBAABBxxzzzzuuxxxxyyyyzzzzu uvv 數(shù)學(xué)規(guī)劃模型的建立與求解【實(shí)例【實(shí)例3】：】：有4名同學(xué)到一家公司參加三個(gè)階段的面試：公司要求每個(gè)同學(xué)必須首先到秘書(shū)處初試，然后到部門(mén)主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊(duì)（即在任何一個(gè)階段4名同學(xué)的順序是一樣的

12、）。由于4名同學(xué)的專(zhuān)業(yè)背景不同，所以每人在三個(gè)階段的面試時(shí)間也不同，如下表所示（單位：分鐘）： 秘書(shū)初試主管復(fù)試經(jīng)理面試同學(xué)甲131520同學(xué)乙102018同學(xué)丙201610同學(xué)丁81015這4名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開(kāi)公司。假定現(xiàn)在時(shí)間是早上8:00，問(wèn)他們最早何時(shí)離開(kāi)公司？ 數(shù)學(xué)規(guī)劃模型的建立與求解Step 1. 尋求決策，即回答什么？尋求決策，即回答什么？ 1. 同學(xué)甲、乙、丙、丁的面試次序 1）同學(xué)甲、乙、丙、丁每個(gè)階段面試的開(kāi)始時(shí)間 2）先后次序 2. 離開(kāi)時(shí)間 Step 2. 確定決策變量確定決策變量 1. 同學(xué)甲、乙、丙、丁參加第j階段面試的開(kāi)始時(shí)間ti,j； 2. 同

13、學(xué)甲、乙、丙、丁面試結(jié)束時(shí)間：T1，T2，T3，T4 3. 離開(kāi)時(shí)間：T=max T1，T2，T3，T4 4. 先后次序：ri,j，01變量 5. 面試時(shí)間（已知）：ci,jStep 3. 確定優(yōu)化目標(biāo)確定優(yōu)化目標(biāo) Min T 數(shù)學(xué)規(guī)劃模型的建立與求解Step 4. 尋找約束條件尋找約束條件 1. 單人面試先后次序約束：ti,j+ci,jti,j+1，i=1,2,3,4；j=1,2 2. 每個(gè)階段j在同一時(shí)間只能由一個(gè)同學(xué)參加面試： ti,j + ci,j - tk,j T ri,k （i,k=1,2,3,4；j=1,2,3；ik） tk,j + ck,j ti,j T(1 - ri,k)（i

14、,k=1,2,3,4；j=1,2,3；ik） Step 5. 構(gòu)成數(shù)學(xué)模型構(gòu)成數(shù)學(xué)模型 123411,31,322,32,333,33,344,34,3,1,.max,. .,1,2,3,4;1,2, ,1,2,3,4;1,2,3;(1) , ,1,2,3,4;1,2,3;i ji ji ji ji jk ji kk jk ji ji kiMin TT T T Ts tTtcTtcTtcTtctctijtctT ri kjiktctTri kjikt ,0,0 ,1,2,3,4;1,2,301jii kTijror 數(shù)學(xué)規(guī)劃模型的建立與求解4模型的理論求解方法模型的理論求解方法線性規(guī)劃問(wèn)題和整

15、數(shù)規(guī)劃問(wèn)題是兩類(lèi)非常重要的數(shù)學(xué)規(guī)劃問(wèn)題，它們的求解方法是很多數(shù)學(xué)規(guī)劃問(wèn)題的求解方法的基礎(chǔ)。 4.1 線性規(guī)劃問(wèn)題的單純形法線性規(guī)劃問(wèn)題的單純形法4.1.1 一般的線性規(guī)劃問(wèn)題模型一般的線性規(guī)劃問(wèn)題模型 1122(1)(1)(2)(2)(3)(3)min (max ). .nnzc xc xc xs tAxbAxbAxb 或或其中 12,TnnxxxxR(1)(2)(3),AAA為矩陣， (1)(2)(3),bbb，為列向量。 數(shù)學(xué)規(guī)劃模型的建立與求解4.1.2 標(biāo)準(zhǔn)的線性規(guī)劃問(wèn)題標(biāo)準(zhǔn)的線性規(guī)劃問(wèn)題min. .0Tzc xs tAxbx 其中： ,0,nmm nx cRbRbARmn （1）數(shù)學(xué)

16、規(guī)劃模型的建立與求解4.1.3 單純形法單純形法G.B.Dantzig的單純形法（Simplex method）是一個(gè)頂點(diǎn)迭代算法，即從一個(gè)頂點(diǎn)出發(fā)，沿著凸多面體的棱迭代到另一個(gè)頂點(diǎn)，使目標(biāo)函數(shù)值下降（至少不升），由頂點(diǎn)個(gè)數(shù)的有限性，可以證明經(jīng)過(guò)有限次迭代一定可以求得最優(yōu)解或者判定該問(wèn)題無(wú)最優(yōu)解，這就是單純形法的基本思想。而幾何上一個(gè)的頂點(diǎn)對(duì)應(yīng)在代數(shù)上的一個(gè)基可行解，因此，單純形法求解線性規(guī)劃問(wèn)題只需要關(guān)心基可行解。 數(shù)學(xué)規(guī)劃模型的建立與求解若線性規(guī)劃問(wèn)題 （1）中： ,AIN ，其中I是一個(gè) m 階單位矩陣，且 12,0mbbb ，即為 1122,11111,111,122,112,2,11

17、,min(). .(2)0 ,1,2,nnmnmiijii jjij mimmnnmmnnmm mmm nnmjzc xc xc xc bcc axs txaxaxbxaxaxbxaxaxbxjn 則 I 稱(chēng)為線性規(guī)劃問(wèn)題的一個(gè)基 ， 而對(duì)應(yīng)著基的變量 ,1,2,jxjm 稱(chēng)為基變量，其余變量 ,1,2 ,jxjmmn 為非基變量。 非基變量均取值零的可行解 12,0,0Tmxbbb 稱(chēng)為基可行解。 數(shù)學(xué)規(guī)劃模型的建立與求解單純形法的計(jì)算步驟如下： 數(shù)學(xué)規(guī)劃模型的建立與求解【示例】【示例】利用單純形法求解線性規(guī)劃問(wèn)題 1212121212max10001500. .95350452002515

18、0,0wxxs txxxxxxxx 第一步，將原問(wèn)題化成標(biāo)準(zhǔn)形式，并構(gòu)造初始單純形表第一步，將原問(wèn)題化成標(biāo)準(zhǔn)形式，并構(gòu)造初始單純形表 【解】：【解】：345,xxx，引入松弛變量將原問(wèn)題化成標(biāo)準(zhǔn)形式：3453412121212125min(10001500). .953504520025150,0,zxxsxxxxxxtxxxxxxx x 數(shù)學(xué)規(guī)劃模型的建立與求解該問(wèn)題已經(jīng)滿(mǎn)足（2），基變量為 345,xxx，非基變量為 12,xx基本可行解為 0,0,350,200,150Tx ，目標(biāo)函數(shù)值為，檢驗(yàn)系數(shù)為 1000,1500,0,0,0T ，構(gòu)造初始單純形表如下： 基變量基變量p p1 1p

19、 p2 2p p3 3p p4 4p p5 5b b9 95 51 10 00 03503504 45 50 01 10 02002002 25 50 00 01 1150150檢驗(yàn)數(shù)檢驗(yàn)數(shù)10001000150015000 00 00 00 05x4x3xj 3453412121212125min(10001500). .953504520025150,0,zxxsxxxxxxtxxxxxxx x 1210000 ,15000 因?yàn)?所以當(dāng)前解不是最優(yōu)解不是最優(yōu)解。 數(shù)學(xué)規(guī)劃模型的建立與求解第二步，選擇進(jìn)基變量與離基變量第二步，選擇進(jìn)基變量與離基變量基變量基變量p1p2 p3p4p5bx39

20、5100350 x445010200 x52001150檢驗(yàn)數(shù)檢驗(yàn)數(shù)100015000000j 第三步，以第三步，以3,2a為主元進(jìn)行迭代，得新的單純形表如下為主元進(jìn)行迭代，得新的單純形表如下 基變量基變量p1p2p3p4p5bx37010-1200 x42001-150 x20.41000.230檢驗(yàn)數(shù)400000-300-45000j 新的基本可行解為 0,30,200,50,0Tx 新的最優(yōu)值為 -45000；14000 ，當(dāng)前解不是最優(yōu)解不是最優(yōu)解。 檢驗(yàn)數(shù)數(shù)學(xué)規(guī)劃模型的建立與求解 第四步，重復(fù)前面的第二步，選擇進(jìn)基變量和離基變量第四步，重復(fù)前面的第二步，選擇進(jìn)基變量和離基變量基變量基

21、變量p1p2p3p4p5bx37010-1200 x4001-150 x20.41000.230檢驗(yàn)數(shù)檢驗(yàn)數(shù)400000-300-45000j 第五步，以第五步，以 為主元進(jìn)行迭代，得新的單純形表如下：為主元進(jìn)行迭代，得新的單純形表如下： 2,1a基變量基變量p p1 1p p2 2p p3 3p p4 4p p5 5b bx x3 30 00 01 1-3.5-3.52.52.52525x x1 11 10 00 00.50.5-0.5-0.52525x x2 20 010 0-0.2-0.20.40.42020檢驗(yàn)數(shù)檢驗(yàn)數(shù)0 00 00 0-200-200-100-100-55000-55

22、000j 最優(yōu)解： 25,20,25,0,0Tx 最優(yōu)值： 55000 數(shù)學(xué)規(guī)劃模型的建立與求解4.2 整數(shù)規(guī)劃問(wèn)題的分支定界法整數(shù)規(guī)劃問(wèn)題的分支定界法求解整數(shù)規(guī)劃問(wèn)題的算法有分支定界法、割平面法、分解算法、松弛算法、群論算法等。 分支定界算法分支定界算法（Branch and Bound Algorithm）是最常用的一種，它是1965年由 R.J.Dakin 發(fā)現(xiàn)的一種隱式枚舉法。它的基本思想是反復(fù)劃分可行域，定出最優(yōu)值 z*的界限 z1z*z2對(duì)于極大化問(wèn)題來(lái)講，下界 z1 即為由計(jì)算已求得的所有可行整數(shù)點(diǎn)中的最大目標(biāo)值，上界 z2 可由松弛問(wèn)題的最優(yōu)值或尚未查清的子問(wèn)題的最大目標(biāo)值得到

23、，分支定界法就是將一個(gè)問(wèn)題（P)不斷的分支為幾個(gè)問(wèn)題的集合，并確定新的各子問(wèn)題的界限，直到求得所要求的解為止。 數(shù)學(xué)規(guī)劃模型的建立與求解分支定界法解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問(wèn)題分支定界法解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問(wèn)題n 首先忽略整數(shù)約束求解，求得原問(wèn)題的最優(yōu)解 xn 如果決策變量 xi 本是整數(shù)要求，但是得到的結(jié)果 xi=u（不是整數(shù)），則將原問(wèn)題歸結(jié)為2個(gè)區(qū)域的線性規(guī)劃求解，這個(gè)兩個(gè)區(qū)域?yàn)榉謩e增加約束條件 xi ceil(u) 和 xi floor(u)n 然后分別都這兩個(gè)規(guī)劃模型重復(fù)上面的步驟，直到滿(mǎn)足整數(shù)要求為止。n 再選出最優(yōu)解。 數(shù)學(xué)規(guī)劃模型的建立與求解【示例】利用分支定界算法求解ILP問(wèn)題： 1212012max58. .6()59450,1,2.iizxxs txxPxxxxI i P0 x1=2.25x2=3.75z=41.25x1=1.8x2=4z=41x1=3x2=3z=390z*4141P1x24P2x233121211212max58. .6()59450,4zxx