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

2、 , x 2 , , x n 。 許多實(shí)際問(wèn)題歸結(jié)出的這種優(yōu)化模型，但是其決策變量個(gè)數(shù) n 和約束條件個(gè)數(shù) m 一般較大，并且最優(yōu)解往往在可行域的邊界上取得，這樣就不能簡(jiǎn)單地用微分法求解，數(shù)學(xué)規(guī)劃就是解決這類問(wèn)題的有效方法。 共三十三頁(yè)2數(shù)學(xué)規(guī)劃模型(mxng)分類“數(shù)學(xué)規(guī)劃是運(yùn)籌學(xué)和管理科學(xué)中應(yīng)用及其廣泛的分支。在許多情況下，應(yīng)用數(shù)學(xué)規(guī)劃取得的如此(rc)成功，以致它的用途已超出了運(yùn)籌學(xué)的范疇，成為人們?nèi)粘５囊?guī)劃工具。”H.P.Williams.數(shù)學(xué)規(guī)劃模型的建立。 數(shù)學(xué)規(guī)劃包括線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、幾何規(guī)劃、多目標(biāo)規(guī)劃等，用數(shù)學(xué)規(guī)劃方法解決實(shí)際問(wèn)題，就要將實(shí)際問(wèn)題經(jīng)過(guò)抽象、簡(jiǎn)化、

3、假設(shè)，確定變量與參數(shù)，建立適當(dāng)層次上的數(shù)學(xué)模型，并求解。 共三十三頁(yè)3建立數(shù)學(xué)(shxu)規(guī)劃模型的步驟當(dāng)你打算(d sun)用數(shù)學(xué)建模的方法來(lái)處理一個(gè)優(yōu)化問(wèn)題的時(shí)候，首先要確定尋求的決策是什么，優(yōu)化的目標(biāo)是什么，決策受到那些條件的限制（如果有限制的話），然后用數(shù)學(xué)工具（變量、常數(shù)、函數(shù)等）表示它們，最后用合適的方法求解它們并對(duì)結(jié)果作出一些定性、定量的分析和必要的檢驗(yàn)。 共三十三頁(yè)Step 1. 尋求決策，即回答什么？必須清楚，無(wú)歧義。 閱讀完題目的第一步不是尋找答案或者解法，而是Step 2. 確定決策變量 第一來(lái)源：Step 1的結(jié)果(ji gu)，用變量固定需要回答的決策 第二來(lái)源：由決

4、策導(dǎo)出的變量（具有派生結(jié)構(gòu)） 其它來(lái)源：輔助變量（聯(lián)合完成更清楚的回答）Step 3. 確定優(yōu)化目標(biāo) 用決策變量表示的利潤(rùn)、成本等。Step 4. 尋找約束條件 決策變量之間、決策變量與常量之間的聯(lián)系。 第一來(lái)源：需求； 第二來(lái)源：供給； 其它來(lái)源：輔助以及常識(shí)。Step 5. 構(gòu)成數(shù)學(xué)模型 將目標(biāo)以及約束放在一起，寫成數(shù)學(xué)表達(dá)式。 共三十三頁(yè)【實(shí)例 1 】：某儲(chǔ)蓄所每天的營(yíng)業(yè)時(shí)間是上午9:00到下午5:00。 根據(jù)經(jīng)驗(yàn)，每天不同時(shí)間段所需要的服務(wù)員數(shù)量(shling)如下：時(shí)間段（時(shí)）9-1010-1111-1212-11-22-33-44-5服務(wù)員數(shù)量43465688儲(chǔ)蓄所可以雇傭全時(shí)和半

5、時(shí)兩類服務(wù)員。全時(shí)服務(wù)員每天報(bào)酬100元，從上午9:00到下午(xiw)5:00工作，但中午12:00到下午(xiw)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í)兩類服務(wù)員？ 共三十三頁(yè)Step 1：需要回答什么？ 1. 雇傭(gyng)的全時(shí)雇員數(shù)量和半時(shí)雇員數(shù)量； 2. 半時(shí)雇員開(kāi)始上班時(shí)間？（最早9:00，最晚1:00） 3費(fèi)用是多少？ Step2：決策變量？ 1全時(shí)雇員數(shù)量(shling)：x； 2每個(gè)時(shí)間開(kāi)始時(shí)雇傭的半時(shí)雇員數(shù)量：yi，i=1,2,5 3清楚嗎？漏掉了什么？

6、 全時(shí)雇員需要午餐。 4全時(shí)雇員數(shù)量分解：12點(diǎn)就餐：x1；1點(diǎn)就餐：x2注意：x1，x2為由決策導(dǎo)出的變量。 Step3：目標(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)共三十三頁(yè)Step4：約束條件 需求：服務(wù)員數(shù)量(shling)約束(8個(gè))； 供方約束：半時(shí)雇員約束：y1+y2+y3+y4+y53； 常規(guī)約束：非負(fù)整數(shù)。 Step5：數(shù)學(xué)模型 共三十三頁(yè)【實(shí)例2】：某電力公司經(jīng)營(yíng)兩座發(fā)電站，發(fā)電站分別位于兩個(gè)水庫(kù)(shuk)上，位置如右圖所示： 已知發(fā)電站可以將水庫(kù)A的1萬(wàn)立方米的水轉(zhuǎn)換為400千度電能，

7、發(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)(yugun)數(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共三十三頁(yè)Step 1. 尋求決策，即回答什么？ 1. 水庫(kù)A、B本月和下月發(fā)電量（可以(ky)用水量表示）； 2

8、. 電力公司的收益。 Step 3. 確定優(yōu)化目標(biāo)(mbio) 目標(biāo)：利潤(rùn)最大化。 利潤(rùn)=高價(jià)電利潤(rùn)+低價(jià)電利潤(rùn) P=200(u1+u2)+140(v1+v2) Step 2. 確定決策變量 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ù)的水量：zA1，zA2，zB1，zB2 共三十三頁(yè)Step 4. 尋找約束條件 1. 電量守恒：每月發(fā)電量=每月賣出

9、量（2個(gè)） 2. 水量守恒： 發(fā)電用水量+直接放走量+庫(kù)存量=原有庫(kù)存量+來(lái)水量（4個(gè)） 3. 發(fā)電能力限制：4個(gè) 4. 水庫(kù)(shuk)蓄水量限制：4個(gè) 5. 高價(jià)電量限制：2個(gè) Step 5. 構(gòu)成(guchng)數(shù)學(xué)模型 共三十三頁(yè)【實(shí)例3】：有4名同學(xué)到一家公司參加三個(gè)階段的面試：公司要求每個(gè)同學(xué)必須首先到秘書處初試，然后到部門(bmn)主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊(duì)（即在任何一個(gè)階段4名同學(xué)的順序是一樣的）。由于4名同學(xué)的專業(yè)背景不同，所以每人在三個(gè)階段的面試時(shí)間也不同，如下表所示（單位：分鐘）： 秘書初試主管復(fù)試經(jīng)理面試同學(xué)甲131520同學(xué)乙102018同學(xué)丙2

10、01610同學(xué)丁81015這4名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄?yq)離開(kāi)公司。假定現(xiàn)在時(shí)間是早上8:00，問(wèn)他們最早何時(shí)離開(kāi)公司？ 共三十三頁(yè)Step 1. 尋求(xnqi)決策，即回答什么？ 1. 同學(xué)甲、乙、丙、丁的面試次序 1）同學(xué)甲、乙、丙、丁每個(gè)階段面試的開(kāi)始時(shí)間 2）先后次序 2. 離開(kāi)時(shí)間 Step 2. 確定決策(juc)變量 1. 同學(xué)甲、乙、丙、丁參加第j階段面試的開(kāi)始時(shí)間ti,j； 2. 同學(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

11、 3. 確定優(yōu)化目標(biāo) Min T 共三十三頁(yè)Step 4. 尋找約束條件 1. 單人面試先后次序約束：ti,j+ci,jti,j+1，i=1,2,3,4；j=1,2 2. 每個(gè)階段(jidun)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,k=1,2,3,4；j=1,2,3；ik） Step 5. 構(gòu)成(guchng)數(shù)學(xué)模型 共三十三頁(yè)4模型的理論求解(qi ji)方法線性規(guī)劃(guhu)問(wèn)題和整數(shù)規(guī)劃(guhu)問(wèn)題是兩類非常重要的數(shù)學(xué)

12、規(guī)劃(guhu)問(wèn)題，它們的求解方法是很多數(shù)學(xué)規(guī)劃(guhu)問(wèn)題的求解方法的基礎(chǔ)。 4.1 線性規(guī)劃問(wèn)題的單純形法4.1.1 一般的線性規(guī)劃問(wèn)題模型 其中 為矩陣， 為列向量。 共三十三頁(yè)4.1.2 標(biāo)準(zhǔn)(biozhn)的線性規(guī)劃問(wèn)題其中： （1）共三十三頁(yè)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)解，這就是單純形法的基本思想。而幾何(j h)上一個(gè)的頂點(diǎn)對(duì)應(yīng)在代數(shù)上的一

13、個(gè)基可行解，因此，單純形法求解線性規(guī)劃問(wèn)題只需要關(guān)心基可行解。 共三十三頁(yè)若線性規(guī)劃問(wèn)題 （1）中：，其中I是一個(gè) m 階單位矩陣，且 ，即為 則 I 稱為線性規(guī)劃問(wèn)題的一個(gè)基 ， 而對(duì)應(yīng)著基的變量 稱為基變量，其余變量 為非基變量。 非基變量均取值零的可行解 稱為基可行解。 共三十三頁(yè)單純形法的計(jì)算步驟(bzhu)如下： 共三十三頁(yè)【示例】利用單純形法求解線性規(guī)劃問(wèn)題 第一步，將原問(wèn)題化成標(biāo)準(zhǔn)形式(xngsh)，并構(gòu)造初始單純形表 【解】：引入松弛變量將原問(wèn)題化成標(biāo)準(zhǔn)形式：共三十三頁(yè)該問(wèn)題已經(jīng)滿足（2），基變量為 ，非基變量為 基本可行解為 ，目標(biāo)函數(shù)值為，檢驗(yàn)系數(shù)為 ，構(gòu)造初始單純形表如下

14、： 基變量p1p2p3p4p5b951003504501020025001150檢驗(yàn)數(shù)100015000000因?yàn)?所以當(dāng)前解不是最優(yōu)解。 共三十三頁(yè)第二步，選擇(xunz)進(jìn)基變量與離基變量基變量p1p2 p3p4p5bx395100350 x445010200 x52001150檢驗(yàn)數(shù)100015000000第三步，以為主元進(jìn)行迭代，得新的單純形表如下 基變量p1p2p3p4p5bx37010-1200 x42001-150 x20.41000.230檢驗(yàn)數(shù)400000-300-45000新的基本可行解為 新的最優(yōu)值為 -45000；，當(dāng)前解不是最優(yōu)解。 檢驗(yàn)數(shù)共三十三頁(yè) 第四步，重復(fù)(c

15、hngf)前面的第二步，選擇進(jìn)基變量和離基變量基變量p1p2p3p4p5bx37010-1200 x4001-150 x20.41000.230檢驗(yàn)數(shù)400000-300-45000第五步，以 為主元進(jìn)行迭代，得新的單純形表如下： 基變量p1p2p3p4p5bx3001-3.52.525x11000.5-0.525x2010-0.20.420檢驗(yàn)數(shù)000-200-100-55000最優(yōu)解： 最優(yōu)值： 55000 共三十三頁(yè)4.2 整數(shù)規(guī)劃(guhu)問(wèn)題的分支定界法求解整數(shù)(zhngsh)規(guī)劃問(wèn)題的算法有分支定界法、割平面法、分解算法、松弛算法、群論算法等。 分支定界算法（Branch and

16、 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)值得到，分支定界法就是將一個(gè)問(wèn)題（P)不斷的分支為幾個(gè)問(wèn)題的集合，并確定新的各子問(wèn)題的界限，直到求得所要求的解為止。 共三十三頁(yè)分支定界法解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問(wèn)題 首先忽略整數(shù)約束(yush)求解，求得原問(wèn)題的最優(yōu)解 x 如果決策變量 xi 本是整數(shù)要求，但是得到的結(jié)果 xi=

17、u（不是整數(shù)），則將原問(wèn)題歸結(jié)為2個(gè)區(qū)域的線性規(guī)劃求解，這個(gè)兩個(gè)區(qū)域?yàn)榉謩e增加約束條件 xi ceil(u) 和 xi floor(u) 然后分別都這兩個(gè)規(guī)劃模型重復(fù)上面的步驟，直到滿足整數(shù)要求為止。 再選出最優(yōu)解。 共三十三頁(yè)【示例】利用分支定界算法求解ILP問(wèn)題： P0 x1=2.25x2=3.75z=41.25x1=1.8x2=4z=41x1=3x2=3z=390z*41P1x24P2x23共三十三頁(yè)x1=1.8x2=4z=41P1不可行(kxng)x1=1x2=40/9z=365/9P3x12P4x11共三十三頁(yè)x1=1x2=40/9z=365/9P4P5x24P6x25x1=1x2=

18、4z=37z*37x1=0 x2=5z=40z*40共三十三頁(yè)P(yáng)1x24P2x24P3x12P4x11P5x24P6x25P0最優(yōu)解為： x*=(0,5)T最優(yōu)值為： z*=40.已是整數(shù)(zhngsh)解不可行(kxng)已是整數(shù)解共三十三頁(yè)5軟件求解方法5.1 Lindo軟件求解 范圍：線性規(guī)劃問(wèn)題、整數(shù)規(guī)劃問(wèn)題、二次規(guī)劃問(wèn)題。 特點(diǎn)：編程簡(jiǎn)單但使用范圍小。 演示(ynsh)實(shí)例： 【實(shí)例1】 服務(wù)員聘用(pn yn)問(wèn)題 【實(shí)例2】水電站生產(chǎn)計(jì)劃 共三十三頁(yè)5.2 Lingo軟件求解 范圍：一般數(shù)學(xué)(shxu)優(yōu)化問(wèn)題。 特點(diǎn)：使用范圍廣但編程比Lindo復(fù)雜。 演示實(shí)例： 【實(shí)例3】 面試次序(cx)安排【實(shí)例4】黑白球三維排列游戲共三十三頁(yè)內(nèi)容摘要數(shù)學(xué)規(guī)劃模型的建立與求解。優(yōu)化問(wèn)題是人們?cè)诠こ碳夹g(shù)、經(jīng)濟(jì)管理和科學(xué)研究等領(lǐng)