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

數(shù)學(xué)規(guī)劃模型的建立與求解張興元2009年3月1．優(yōu)化問(wèn)題及其一般模型

優(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ù)生產(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ōu)化模型可以表述如下：

這是一個(gè)多元函數(shù)的條件極值問(wèn)題，其中x=[x1,x2,…,xn]。

許多實(shí)際問(wèn)題歸結(jié)出的這種優(yōu)化模型，但是其決策變量個(gè)數(shù)n和約束條件個(gè)數(shù)m一般較大，并且最優(yōu)解往往在可行域的邊界上取得，這樣就不能簡(jiǎn)單地用微分法求解，數(shù)學(xué)規(guī)劃就是解決這類問(wèn)題的有效方法。2．?dāng)?shù)學(xué)規(guī)劃模型分類“數(shù)學(xué)規(guī)劃是運(yùn)籌學(xué)和管理科學(xué)中應(yīng)用及其廣泛的分支。在許多情況下，應(yīng)用數(shù)學(xué)規(guī)劃取得的如此成功，以致它的用途已超出了運(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)化、假設(shè)，確定變量與參數(shù)，建立適當(dāng)層次上的數(shù)學(xué)模型，并求解。3．建立數(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)。Step1.尋求決策，即回答什么？必須清楚，無(wú)歧義。閱讀完題目的第一步不是尋找答案或者解法，而是……Step2.確定決策變量第一來(lái)源：Step1的結(jié)果，用變量固定需要回答的決策第二來(lái)源：由決策導(dǎo)出的變量（具有派生結(jié)構(gòu)）其它來(lái)源：輔助變量（聯(lián)合完成更清楚的回答）Step3.確定優(yōu)化目標(biāo)用決策變量表示的利潤(rùn)、成本等。Step4.尋找約束條件決策變量之間、決策變量與常量之間的聯(lián)系。第一來(lái)源：需求；第二來(lái)源：供給；其它來(lái)源：輔助以及常識(shí)。Step5.構(gòu)成數(shù)學(xué)模型

將目標(biāo)以及約束放在一起，寫成數(shù)學(xué)表達(dá)式?！緦?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í)兩類服務(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í)兩類服務(wù)員？Step1：需要回答什么？

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,…,53．清楚嗎？漏掉了什么？全時(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)Step4：約束條件需求：服務(wù)員數(shù)量約束(8個(gè))；供方約束：半時(shí)雇員約束：y1+y2+y3+y4+y5≤3；常規(guī)約束：非負(fù)整數(shù)。Step5：數(shù)學(xué)模型

【實(shí)例2】：某電力公司經(jīng)營(yíng)兩座發(fā)電站，發(fā)電站分別位于兩個(gè)水庫(kù)上，位置如右圖所示：已知發(fā)電站可以將水庫(kù)A的1萬(wàn)立方米的水轉(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ù)目前蓄水量1900850Step1.尋求決策，即回答什么？

1.水庫(kù)A、B本月和下月發(fā)電量（可以用水量表示）；

2.電力公司的收益。Step3.確定優(yōu)化目標(biāo)目標(biāo)：利潤(rùn)最大化。利潤(rùn)=高價(jià)電利潤(rùn)+低價(jià)電利潤(rùn)

P=200(u1+u2)+140(v1+v2)Step2.確定決策變量

1.

水庫(kù)A、B本月和下月用于發(fā)電的水量：xA1，xA2，xB1，xB22.收益導(dǎo)出決策變量：本月和下月高價(jià)售電量：u1，u2；本月和下月低價(jià)售電量：v1，v2；

3.輔助決策變量（水庫(kù)安全運(yùn)行）：本月和下月水庫(kù)直接放走的水量：yA1，yA2，yB1，yB2；本月和下月結(jié)束時(shí)水庫(kù)的水量：zA1，zA2，zB1，zB2

Step4.尋找約束條件

1.電量守恒：每月發(fā)電量=每月賣出量（2個(gè)）

2.水量守恒：發(fā)電用水量+直接放走量+庫(kù)存量=原有庫(kù)存量+來(lái)水量（4個(gè)）

3.發(fā)電能力限制：4個(gè)

4.水庫(kù)蓄水量限制：4個(gè)

5.高價(jià)電量限制：2個(gè)Step5.構(gòu)成數(shù)學(xué)模型【實(shí)例3】：有4名同學(xué)到一家公司參加三個(gè)階段的面試：公司要求每個(gè)同學(xué)必須首先到秘書處初試，然后到部門主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊(duì)（即在任何一個(gè)階段4名同學(xué)的順序是一樣的）。由于4名同學(xué)的專業(yè)背景不同，所以每人在三個(gè)階段的面試時(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)公司？Step1.尋求決策，即回答什么？

1.同學(xué)甲、乙、丙、丁的面試次序

1）同學(xué)甲、乙、丙、丁每個(gè)階段面試的開(kāi)始時(shí)間

2）先后次序

2.離開(kāi)時(shí)間Step2.確定決策變量

1.同學(xué)甲、乙、丙、丁參加第j階段面試的開(kāi)始時(shí)間ti,j；

2.同學(xué)甲、乙、丙、丁面試結(jié)束時(shí)間：T1，T2，T3，T43.離開(kāi)時(shí)間：T=max{T1，T2，T3，T4}4.先后次序：ri,j，0—1變量

5.面試時(shí)間（已知）：ci,jStep3.確定優(yōu)化目標(biāo)

MinTStep4.尋找約束條件

1.單人面試先后次序約束：ti,j+ci,j≤ti,j+1，i=1,2,3,4；j=1,22.每個(gè)階段j在同一時(shí)間只能由一個(gè)同學(xué)參加面試：

ti,j+ci,j-tk,j≤Tri,k

（i,k=1,2,3,4；j=1,2,3；i<k）

tk,j+ck,j–ti,j≤T(1-ri,k)

（i,k=1,2,3,4；j=1,2,3；i<k）Step5.構(gòu)成數(shù)學(xué)模型4．模型的理論求解方法線性規(guī)劃問(wèn)題和整數(shù)規(guī)劃問(wèn)題是兩類非常重要的數(shù)學(xué)規(guī)劃問(wèn)題，它們的求解方法是很多數(shù)學(xué)規(guī)劃問(wèn)題的求解方法的基礎(chǔ)。4.1線性規(guī)劃問(wèn)題的單純形法4.1.1一般的線性規(guī)劃問(wèn)題模型

其中為矩陣，為列向量。4.1.2標(biāo)準(zhǔn)的線性規(guī)劃問(wèn)題其中：（1）4.1.3單純形法G.B.Dantzig的單純形法（Simplexmethod）是一個(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)心基可行解。若線性規(guī)劃問(wèn)題（1）中：，其中I是一個(gè)m階單位矩陣，且，即為則I稱為線性規(guī)劃問(wèn)題的一個(gè)基，而對(duì)應(yīng)著基的變量稱為基變量，其余變量為非基變量。非基變量均取值零的可行解稱為基可行解。單純形法的計(jì)算步驟如下：【示例】利用單純形法求解線性規(guī)劃問(wèn)題第一步，將原問(wèn)題化成標(biāo)準(zhǔn)形式，并構(gòu)造初始單純形表

【解】：引入松弛變量將原問(wèn)題化成標(biāo)準(zhǔn)形式：該問(wèn)題已經(jīng)滿足（2），基變量為，非基變量為基本可行解為，目標(biāo)函數(shù)值為０，檢驗(yàn)系數(shù)為，構(gòu)造初始單純形表如下：基變量p1p2p3p4p5b951003504501020025001150檢驗(yàn)數(shù)100015000000因?yàn)樗援?dāng)前解不是最優(yōu)解。第二步，選擇進(jìn)基變量與離基變量基變量p1p2

↓p3p4p5bx395100350x445010200←x52⑤001150檢驗(yàn)數(shù)100015000000第三步，以為主元進(jìn)行迭代，得新的單純形表如下

基變量p1p2p3p4p5bx37010-1200x42001-150x20.41000.230檢驗(yàn)數(shù)400000-300-45000新的基本可行解為新的最優(yōu)值為

-45000；，當(dāng)前解不是最優(yōu)解。檢驗(yàn)數(shù)

第四步，重復(fù)前面的第二步，選擇進(jìn)基變量和離基變量基變量↓p1p2p3p4p5bx37010-1200←x4②001-150x20.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)值：550004.2整數(shù)規(guī)劃問(wèn)題的分支定界法求解整數(shù)規(guī)劃問(wèn)題的算法有分支定界法、割平面法、分解算法、松弛算法、群論算法等。分支定界算法（BranchandBoundAlgorithm）是最常用的一種，它是1965年由R.J.Dakin

發(fā)現(xiàn)的一種隱式枚舉法。它的基本思想是反復(fù)劃分可行域，定出最優(yōu)值z(mì)*的界限

z1≤z*≤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)題的界限，直到求得所要求的解為止。分支定界法解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問(wèn)題首先忽略整數(shù)約束求解，求得原問(wèn)題的最優(yōu)解x

如果決策變量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)

然后分別都這兩個(gè)規(guī)劃模型重復(fù)上面的步驟，直到滿足整數(shù)要求為止。再選出最優(yōu)解?！臼纠坷梅种Фń缢惴ㄇ蠼釯LP問(wèn)題：