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

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

優(yōu)化問題是人們在工程技術、經(jīng)濟管理和科學研究等領域中最常遇到的問題之一。例如：設計師要在滿足強度要求等條件下選擇材料的尺寸，

使結(jié)構總重量最輕；公司經(jīng)理要根據(jù)生產(chǎn)成本和市場需求確定產(chǎn)品價格，

使所獲利潤最高；調(diào)度人員要在滿足物質(zhì)需求和裝載條件下安排從各

供應點到需求點的運量和路線，使運輸總費用最低；投資者要選擇一些股票、債券下注，使收益最大，而風險最小

…………一般地，優(yōu)化模型可以表述如下：

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

許多實際問題歸結(jié)出的這種優(yōu)化模型，但是其決策變量個數(shù)n和約束條件個數(shù)m一般較大，并且最優(yōu)解往往在可行域的邊界上取得，這樣就不能簡單地用微分法求解，數(shù)學規(guī)劃就是解決這類問題的有效方法。2．數(shù)學規(guī)劃模型分類“數(shù)學規(guī)劃是運籌學和管理科學中應用及其廣泛的分支。在許多情況下，應用數(shù)學規(guī)劃取得的如此成功，以致它的用途已超出了運籌學的范疇，成為人們?nèi)粘５囊?guī)劃工具。”[H.P.Williams.數(shù)學規(guī)劃模型的建立]。數(shù)學規(guī)劃包括線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、幾何規(guī)劃、多目標規(guī)劃等，用數(shù)學規(guī)劃方法解決實際問題，就要將實際問題經(jīng)過抽象、簡化、假設，確定變量與參數(shù)，建立適當層次上的數(shù)學模型，并求解。3．建立數(shù)學規(guī)劃模型的步驟當你打算用數(shù)學建模的方法來處理一個優(yōu)化問題的時候，首先要確定尋求的決策是什么，優(yōu)化的目標是什么，決策受到那些條件的限制（如果有限制的話），然后用數(shù)學工具（變量、常數(shù)、函數(shù)等）表示它們，最后用合適的方法求解它們并對結(jié)果作出一些定性、定量的分析和必要的檢驗。Step1.尋求決策，即回答什么？必須清楚，無歧義。閱讀完題目的第一步不是尋找答案或者解法，而是……Step2.確定決策變量第一來源：Step1的結(jié)果，用變量固定需要回答的決策第二來源：由決策導出的變量（具有派生結(jié)構）其它來源：輔助變量（聯(lián)合完成更清楚的回答）Step3.確定優(yōu)化目標用決策變量表示的利潤、成本等。Step4.尋找約束條件決策變量之間、決策變量與常量之間的聯(lián)系。第一來源：需求；第二來源：供給；其它來源：輔助以及常識。Step5.構成數(shù)學模型

將目標以及約束放在一起，寫成數(shù)學表達式?！緦嵗?】：某儲蓄所每天的營業(yè)時間是上午9:00到下午5:00。根據(jù)經(jīng)驗，每天不同時間段所需要的服務員數(shù)量如下：時間段（時）9-1010-1111-1212-11-22-33-44-5服務員數(shù)量43465688儲蓄所可以雇傭全時和半時兩類服務員。全時服務員每天報酬100元，從上午9:00到下午5:00工作，但中午12:00到下午2:00之間必須安排1小時的午餐時間。儲蓄所每天可以雇傭不超過3名的半時服務員，每個半時服務員必須連續(xù)工作4小時，報酬40元。問該儲蓄所應如何雇傭全時和半時兩類服務員？Step1：需要回答什么？

1.雇傭的全時雇員數(shù)量和半時雇員數(shù)量；

2.半時雇員開始上班時間？（最早9:00，最晚1:00）

3．費用是多少？Step2：決策變量？

1．全時雇員數(shù)量：x；

2．每個時間開始時雇傭的半時雇員數(shù)量：yi，i=1,2,…,53．清楚嗎？漏掉了什么？全時雇員需要午餐。

4．全時雇員數(shù)量分解：12點就餐：x1；1點就餐：x2注意：x1，x2為由決策導出的變量。Step3：目標函數(shù)目標：支付報酬最少支付報酬=全時員工報酬+半時員工報酬

Z=100(x1+x2)+40(y1+y2+y3+y4+y5)Step4：約束條件需求：服務員數(shù)量約束(8個)；供方約束：半時雇員約束：y1+y2+y3+y4+y5≤3；常規(guī)約束：非負整數(shù)。Step5：數(shù)學模型

【實例2】：某電力公司經(jīng)營兩座發(fā)電站，發(fā)電站分別位于兩個水庫上，位置如右圖所示：已知發(fā)電站可以將水庫A的1萬立方米的水轉(zhuǎn)換為400千度電能，發(fā)電站B只能將水庫B的1萬立方米的水轉(zhuǎn)換為200千度電能。發(fā)電站A、B每個月的最大發(fā)電能力分別是60000千度、35000千度。每個月最多有50000千度電能夠以200元/千度的價格售出，多余的電能只能夠以140元/千度的價格售出。水庫A、B的其它有關數(shù)據(jù)如下表（單位：萬立方米）。請你為該電力公司制定本月和下月的生產(chǎn)經(jīng)營計劃。水庫

A水庫

B水庫最大蓄水量20001500水源流入水量本月20040下月13015水庫最小蓄水量1200800水庫目前蓄水量1900850Step1.尋求決策，即回答什么？

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

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

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

1.

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

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

Step4.尋找約束條件

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

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

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

4.水庫蓄水量限制：4個

5.高價電量限制：2個Step5.構成數(shù)學模型【實例3】：有4名同學到一家公司參加三個階段的面試：公司要求每個同學必須首先到秘書處初試，然后到部門主管處復試，最后到經(jīng)理處參加面試，并且不允許插隊（即在任何一個階段4名同學的順序是一樣的）。由于4名同學的專業(yè)背景不同，所以每人在三個階段的面試時間也不同，如下表所示（單位：分鐘）：秘書初試主管復試經(jīng)理面試同學甲131520同學乙102018同學丙201610同學丁81015這4名同學約定他們?nèi)棵嬖囃暌院笠黄痣x開公司。假定現(xiàn)在時間是早上8:00，問他們最早何時離開公司？Step1.尋求決策，即回答什么？

1.同學甲、乙、丙、丁的面試次序

1）同學甲、乙、丙、丁每個階段面試的開始時間

2）先后次序

2.離開時間Step2.確定決策變量

1.同學甲、乙、丙、丁參加第j階段面試的開始時間ti,j；

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

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

MinTStep4.尋找約束條件

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

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.構成數(shù)學模型4．模型的理論求解方法線性規(guī)劃問題和整數(shù)規(guī)劃問題是兩類非常重要的數(shù)學規(guī)劃問題，它們的求解方法是很多數(shù)學規(guī)劃問題的求解方法的基礎。4.1線性規(guī)劃問題的單純形法4.1.1一般的線性規(guī)劃問題模型

其中為矩陣，為列向量。4.1.2標準的線性規(guī)劃問題其中：（1）4.1.3單純形法G.B.Dantzig的單純形法（Simplexmethod）是一個頂點迭代算法，即從一個頂點出發(fā)，沿著凸多面體的棱迭代到另一個頂點，使目標函數(shù)值下降（至少不升），由頂點個數(shù)的有限性，可以證明經(jīng)過有限次迭代一定可以求得最優(yōu)解或者判定該問題無最優(yōu)解，這就是單純形法的基本思想。而幾何上一個的頂點對應在代數(shù)上的一個基可行解，因此，單純形法求解線性規(guī)劃問題只需要關心基可行解。若線性規(guī)劃問題（1）中：，其中I是一個m階單位矩陣，且，即為則I稱為線性規(guī)劃問題的一個基，而對應著基的變量稱為基變量，其余變量為非基變量。非基變量均取值零的可行解稱為基可行解。單純形法的計算步驟如下：【示例】利用單純形法求解線性規(guī)劃問題第一步，將原問題化成標準形式，并構造初始單純形表

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

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

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

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

第四步，重復前面的第二步，選擇進基變量和離基變量基變量↓p1p2p3p4p5bx37010-1200←x4②001-150x20.41000.230檢驗數(shù)400000-300-45000第五步，以為主元進行迭代，得新的單純形表如下：

基變量p1p2p3p4p5bx3001-3.52.525x11000.5-0.525x2010-0.20.420檢驗數(shù)000-200-100-55000最優(yōu)解：最優(yōu)值：550004.2整數(shù)規(guī)劃問題的分支定界法求解整數(shù)規(guī)劃問題的算法有分支定界法、割平面法、分解算法、松弛算法、群論算法等。分支定界算法（BranchandBoundAlgorithm）是最常用的一種，它是1965年由R.J.Dakin

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

z1≤z*≤z2

對于極大化問題來講，下界z1即為由計算已求得的所有可行整數(shù)點中的最大目標值，上界z2可由松弛問題的最優(yōu)值或尚未查清的子問題的最大目標值得到，分支定界法就是將一個問題（P)不斷的分支為幾個問題的集合，并確定新的各子問題的界限，直到求得所要求的解為止。分支定界法解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃問題首先忽略整數(shù)約束求解，求得原問題的最優(yōu)解x

如果決策變量xi本是整數(shù)要求，但是得到的結(jié)果xi=u（不是整數(shù)），則將原問題歸結(jié)為2個區(qū)域的線性規(guī)劃求解，這個兩個區(qū)域為分別增加約束條件

xi≥ceil(u)和xi≤floor(u)

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