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

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

2、zf xs tg x ， i i = =1 1, , 2 2, , , m m 這是一個多元函數(shù)的條件極值問題，其中 x = x 1 , x 2 , , x n 。 許多實(shí)際問題歸結(jié)出的這種優(yōu)化模型，但是其決策變量個數(shù) n 和約束條件個數(shù) m 一般較大，并且最優(yōu)解往往在可行域的邊界上取得，這樣就不能簡單地用微分法求解，數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃就是解決這類問題的有效方法。 數(shù)學(xué)規(guī)劃模型的建立與求解2數(shù)學(xué)規(guī)劃模型分類數(shù)學(xué)規(guī)劃模型分類“數(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í)際問題，就要將實(shí)際問題經(jīng)過抽象、簡化、假設(shè)，確定變量與參數(shù)，建立適當(dāng)層次上的數(shù)學(xué)模型，并求解。 數(shù)學(xué)規(guī)劃模型的建立與求解3建立數(shù)學(xué)規(guī)劃模型的步驟建立數(shù)學(xué)規(guī)劃模型的步驟當(dāng)你打算用數(shù)學(xué)建模的方法來處理一個優(yōu)化問題的時候，首先要確定尋求的決策是什么，優(yōu)化的目標(biāo)是什么，決策受到那些條件的限制（如果有限制的話），然后用數(shù)學(xué)工具（變量、常數(shù)、函數(shù)等）表示它們，最后用合適的方法求解它們并對結(jié)果作出一些定性、定量的分析和必要的檢驗(yàn)。 數(shù)學(xué)規(guī)劃模型的建立與求解Step 1. 尋求決策，

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

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

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

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

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

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

10、：zA1，zA2，zB1，zB2 數(shù)學(xué)規(guī)劃模型的建立與求解Step 4. 尋找約束條件尋找約束條件 1. 電量守恒：每月發(fā)電量=每月賣出量（2個） 2. 水量守恒： 發(fā)電用水量+直接放走量+庫存量=原有庫存量+來水量（4個） 3. 發(fā)電能力限制：4個 4. 水庫蓄水量限制：4個 5. 高價電量限制：2個 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é)到一家公司參加三個階段的面試：公司要求每個同學(xué)必須首先到秘書處初試，然后到部門主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊(duì)（即在任何一個階段4名同學(xué)的順序是一樣的

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

13、學(xué)甲、乙、丙、丁面試結(jié)束時間：T1，T2，T3，T4 3. 離開時間：T=max T1，T2，T3，T4 4. 先后次序：ri,j，01變量 5. 面試時間（已知）：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. 每個階段j在同一時間只能由一個同學(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ī)劃問題和整

15、數(shù)規(guī)劃問題是兩類非常重要的數(shù)學(xué)規(guī)劃問題，它們的求解方法是很多數(shù)學(xué)規(guī)劃問題的求解方法的基礎(chǔ)。 4.1 線性規(guī)劃問題的單純形法線性規(guī)劃問題的單純形法4.1.1 一般的線性規(guī)劃問題模型一般的線性規(guī)劃問題模型 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ī)劃問題標(biāo)準(zhǔn)的線性規(guī)劃問題min. .0Tzc xs tAxbx 其中： ,0,nmm nx cRbRbARmn （1）數(shù)學(xué)

16、規(guī)劃模型的建立與求解4.1.3 單純形法單純形法G.B.Dantzig的單純形法（Simplex method）是一個頂點(diǎn)迭代算法，即從一個頂點(diǎn)出發(fā)，沿著凸多面體的棱迭代到另一個頂點(diǎn)，使目標(biāo)函數(shù)值下降（至少不升），由頂點(diǎn)個數(shù)的有限性，可以證明經(jīng)過有限次迭代一定可以求得最優(yōu)解或者判定該問題無最優(yōu)解，這就是單純形法的基本思想。而幾何上一個的頂點(diǎn)對應(yīng)在代數(shù)上的一個基可行解，因此，單純形法求解線性規(guī)劃問題只需要關(guān)心基可行解。 數(shù)學(xué)規(guī)劃模型的建立與求解若線性規(guī)劃問題 （1）中： ,AIN ，其中I是一個 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 稱為線性規(guī)劃問題的一個基 ， 而對應(yīng)著基的變量 ,1,2,jxjm 稱為基變量，其余變量 ,1,2 ,jxjmmn 為非基變量。 非基變量均取值零的可行解 12,0,0Tmxbbb 稱為基可行解。 數(shù)學(xué)規(guī)劃模型的建立與求解單純形法的計算步驟如下： 數(shù)學(xué)規(guī)劃模型的建立與求解【示例】【示例】利用單純形法求解線性規(guī)劃問題 1212121212max10001500. .95350452002515

18、0,0wxxs txxxxxxxx 第一步，將原問題化成標(biāo)準(zhǔn)形式，并構(gòu)造初始單純形表第一步，將原問題化成標(biāo)準(zhǔn)形式，并構(gòu)造初始單純形表 【解】：【解】：345,xxx，引入松弛變量將原問題化成標(biāo)準(zhǔn)形式：3453412121212125min(10001500). .953504520025150,0,zxxsxxxxxxtxxxxxxx x 數(shù)學(xué)規(guī)劃模型的建立與求解該問題已經(jīng)滿足（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ī)劃問題的分支定界法整數(shù)規(guī)劃問題的分支定界法求解整數(shù)規(guī)劃問題的算法有分支定界法、割平面法、分解算法、松弛算法、群論算法等。 分支定界算法分支定界算法（Branch and Bound Algorithm）是最常用的一種，它是1965年由 R.J.Dakin 發(fā)現(xiàn)的一種隱式枚舉法。它的基本思想是反復(fù)劃分可行域，定出最優(yōu)值 z*的界限 z1z*z2對于極大化問題來講，下界 z1 即為由計算已求得的所有可行整數(shù)點(diǎn)中的最大目標(biāo)值，上界 z2 可由松弛問題的最優(yōu)值或尚未查清的子問題的最大目標(biāo)值得到

23、，分支定界法就是將一個問題（P)不斷的分支為幾個問題的集合，并確定新的各子問題的界限，直到求得所要求的解為止。 數(shù)學(xué)規(guī)劃模型的建立與求解分支定界法解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問題分支定界法解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問題n 首先忽略整數(shù)約束求解，求得原問題的最優(yōu)解 xn 如果決策變量 xi 本是整數(shù)要求，但是得到的結(jié)果 xi=u（不是整數(shù)），則將原問題歸結(jié)為2個區(qū)域的線性規(guī)劃求解，這個兩個區(qū)域?yàn)榉謩e增加約束條件 xi ceil(u) 和 xi floor(u)n 然后分別都這兩個規(guī)劃模型重復(fù)上面的步驟，直到滿足整數(shù)要求為止。n 再選出最優(yōu)解。 數(shù)學(xué)規(guī)劃模型的建立與求解【示例】利用分支定界算法求解ILP問題： 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