第2講數(shù)學(xué)規(guī)劃模型的建立1

數(shù)學(xué)規(guī)劃模型I引言

一個復(fù)雜系統(tǒng)往往要受諸多因素的影響，而這些因素又要受到一定的限制。最優(yōu)化就是在一定約束下，如何選取這些因素的值，使某項（或某些）指標達到最優(yōu)的一門學(xué)科。它包括數(shù)學(xué)規(guī)劃、決策分析、最優(yōu)控制等等。最優(yōu)化方法在經(jīng)濟、軍事、科技等領(lǐng)域內(nèi)都有廣泛的應(yīng)用。例1把一根直徑為d

的圓木鋸成矩形橫梁。已知橫梁強度z與寬度x

成正比，與高度y

的平方成正比。求寬、高各為多少時強度最大？該問題的數(shù)學(xué)模型為：用微分法容易求出其解。數(shù)學(xué)規(guī)劃模型格式：maxs.t.例2施工點j的坐標為對某材料的需求量為第i個料場的容量為求料場的位置及各料場向各施工點的供應(yīng)量，使材料運輸?shù)目倗嵐镒钚?。解設(shè)各料場到各施工點的距離為直線距離，且各施工點可在不同料場取料。則總噸公里數(shù)需求限制容量限制非負限制mins.t.學(xué)習(xí)這一部分需注意的地方：對給定的實際問題，如何作合理的假設(shè)，并建立模型。如何處理分段函數(shù)、矛盾約束等問題。2.怎樣將一類模型化為另一類模型，易于求解。3.同一問題可建立不同模型第二個問題不便用微分法求解，可用數(shù)學(xué)規(guī)劃方法求解。II數(shù)學(xué)規(guī)劃模型的建立數(shù)學(xué)規(guī)劃模型的一般形式：例如：maxs.t.若能寫出描述S的數(shù)學(xué)式子，則可直接寫出。這里目標函數(shù)可行域可行解決策變量描述S的數(shù)學(xué)式子約束條件S問題可行問題不可行最優(yōu)解最優(yōu)目標值幾個概念：特別：(或max)或線性規(guī)劃模型或等約束注：M是常數(shù)與有相同的最優(yōu)解1.2.與有相同的最優(yōu)解另外：1.取整數(shù)，稱模型為整數(shù)規(guī)劃模型2.中部分取整數(shù)，稱模型為混合整數(shù)規(guī)劃模型3.只取0或1兩個值，稱為0—1規(guī)劃模型目標函數(shù)或約束條件是非線性的，稱為非線性規(guī)劃模型若目標函數(shù)只有一個，稱為單目標規(guī)劃模型；若目標函數(shù)不只一個，稱為多目標規(guī)劃模型。產(chǎn)地銷地運價例1求使總運費最少的調(diào)運方案。試建模。產(chǎn)量需求量42一、運輸問題解則產(chǎn)銷平衡注：若產(chǎn)大于銷，則若產(chǎn)小于銷，則線性規(guī)劃模型

重要結(jié)論：當(dāng)供應(yīng)量與需求量均為整數(shù)時，模型的最優(yōu)解是整數(shù)解。例2

自來水輸送問題某市有甲、乙、丙、丁四個居民區(qū)，自來水由A、B、C由三個水庫供應(yīng)。四個區(qū)每天必須的基本生活用水分別為30、70、10、10千噸，但三個水庫每天最多只能分別供應(yīng)50、60、50千噸自來水。由于地理位置的差別，自來水公司從各水庫向各區(qū)送水所付出的引水管理費不同（如表，其中C水庫與丁區(qū)間無輸水管道），其它管理費均為450元/千噸。各區(qū)用戶每千噸收費900元。此外，各區(qū)用戶都向公司申請了額外用水量，分別為每天50、70、20、40千噸。問公司應(yīng)如何分配供水量，才能獲利最多？引水管理費(元/千噸)將有關(guān)數(shù)據(jù)整理列表：水庫居民區(qū)供應(yīng)量生活用水額外用水成水輸本問題分析：…可看成是“產(chǎn)小于銷”的運輸問題。解設(shè)xij

分別表示水庫A,B,C(i=1,2,3)向居民區(qū)甲,乙,丙,丁(j=1,2,3,4)的供水量。其中X34=0.模型建立由題意目標函數(shù)為：可轉(zhuǎn)化為：供給限制需求限制一般問題中：供給限制用“”需求限制用“”“”引水管理費因160千噸水須全部輸出注：為了增加供水，公司考慮改造水庫，使三個水庫的供水能力提高一倍，問模型將作何改動？分析：由于總供水能力為320千噸，總需求量為300千噸，水不能全部賣出，所以不能將獲利最多轉(zhuǎn)化為引水管理費最少。須算出每千噸凈利潤。每千噸凈利潤＝用戶交的900元－其它管理費450元－引水管理費凈利潤(元/千噸)模型改為：其它同前例3最大流問題①②③④⑤⑥⑦圖中弧上的數(shù)字表示每小時兩結(jié)點沿箭頭方向的最大車流量，求①到⑦每小時的最大車流量。二、網(wǎng)絡(luò)（規(guī)劃）問題設(shè)v為從出發(fā)的車流量，

為到的車流量，則流量守恒條件弧容量限制去掉去掉若不設(shè)v,則模型有四處需修改如果源、匯不止一個時，建模方法類似?？稍黾右粋€虛擬源、虛擬匯化成單源單匯的問題。

圖中的結(jié)點稱為源（發(fā)點），結(jié)點稱為匯（收點）。圖是單源單匯的情形。例42求從流出，到的最大流量。解設(shè)為到的流量，

、為流入、的量，

、、為流入、、的量。例5

設(shè)有工作件，人員個，且一人做一件工作，第人作第件工作的時間（或費用）為，問：如何分派可使總時間（或總費用）最少。解本題需確定：第人做或不做第件工作，這是定性變量，首先將其定量化。設(shè)0—1規(guī)劃模型則注：若表示效益，則目標函數(shù)應(yīng)極大化問：各人員類不止1人，各工作類不止1件工作，決策變量為何？若人數(shù)“>”工作件數(shù)三、分派問題四、生產(chǎn)活動問題(分段函數(shù)、矛盾約束等的處理方法)資源產(chǎn)品單耗資源量單位利潤例6問如何安排生產(chǎn)使總利潤最大。解設(shè)表示第種產(chǎn)品的產(chǎn)量，則資源分配問題分段函數(shù)問題例中＝單位收益－單位成本（可變成本）若還要考慮固定成本則第j種產(chǎn)品的利潤為：于是引入0—1變量：設(shè)Lj

是xj的上界，則模型改寫為：混合整數(shù)規(guī)劃模型等價性：（1）由Z的極大化（2）由注：將目標函數(shù)變成則為非線性的。若不考慮固定成本，則不引入0-1變量。

更復(fù)雜的分段函數(shù)的處理方法*設(shè)B1是某種原料（單位：噸），還可以從市場上購買到不超過1500噸的原料。若購買量不超過500噸，其價格為10千元/噸；購買量多于500噸但不超過1000噸時，超過500噸的部分8千元/噸；購買量超過1000噸時，超過1000噸的部分6千元/噸。問怎樣安排生產(chǎn)和采購？增設(shè)x為采購量，則可得采購支出（千元）：這時，目標函數(shù)為:處理法1：設(shè)三種價格的采購量分別為：則目標函數(shù)為：約束條件增加：只有當(dāng)

x1=500時，才能以每噸8千元的價格購買x2(>0)非線性規(guī)劃模型！處理法1：可用端點的凸組合來表示線段上的值，如：為了統(tǒng)一表示，引入0－1變量則且至多兩個相鄰的i取非零值可得混合整數(shù)規(guī)劃模型產(chǎn)品種類限制問題（不考慮固定成本）n種產(chǎn)品中只生產(chǎn)其中k種設(shè)則要求產(chǎn)量不小于80單位80矛盾約束問題設(shè)、為機器1、2的可用工時（資源），

種產(chǎn)品只在一臺機器上加工，則以下兩個約束條件是矛盾的，不能同時出現(xiàn)在一個模型中。若引入0—1變量：設(shè)M是充分大的常數(shù)，則兩個矛盾約束可統(tǒng)一在一個模型中：一般，若m種資源中只用其中k種資源，則令約束條件改為：例7

生產(chǎn)存儲問題（多階段問題）某公司生產(chǎn)一種產(chǎn)品，最大生產(chǎn)能力為100單位，第月的單位存儲費為元，預(yù)定的銷售量和單位成本如表。求使生產(chǎn)成本與存儲費之和最低的生產(chǎn)計劃。解先作合理假設(shè)?1月初無庫存；?4月底賣完；?當(dāng)月生產(chǎn)的不入庫；?庫存量無限制。假設(shè)：月份單位成本(元)銷售量(件)模型一且為整數(shù)，第j+1月初的庫存量整數(shù)規(guī)劃模型設(shè)為第月的產(chǎn)量，為單位存儲費，則模型二若設(shè)為第月初的庫存量，則且為整數(shù)，增加了決策變量，但模型簡潔了。本問題還可建立動態(tài)規(guī)劃模型幾點說明：1.增加投資擴大生產(chǎn)能力若每投資k元可增加一個單位的生產(chǎn)能力。設(shè)表示第月的投資，則第月的產(chǎn)量限制條件變?yōu)椋旱谠虑暗耐顿Y在第月仍起作用，生產(chǎn)投資問題。2.均衡生產(chǎn)問題前例中的最優(yōu)月產(chǎn)量為：月初庫存量為：為使生產(chǎn)盡量均衡，可增加相繼兩個月產(chǎn)量差的限制：同時希望非負變量、越小越好。則目標函數(shù)可提為：其中a

為第月比第月增加一個產(chǎn)品要支付的費用，b

為減少一個產(chǎn)品支付的費用，c

為庫存費。根據(jù)要求還可提為：或不希望減少不希望增加＃例8

（P.7例1.8）求生產(chǎn)、存儲、維修計劃將有關(guān)數(shù)據(jù)整理列表(同例1.6)：機床單耗產(chǎn)品臺數(shù)月臺時單位利潤月臺時＝臺數(shù)小時天數(shù)。1344＝41621如一臺機床維修一次需160(臺時)＝10(天)16(小時)19假定：?沒有輪到維修的和維修后的機床在使用期間能正常工作；?維修一臺機床是在某月內(nèi)完成，不會跨入下一月。設(shè)

—第月初、第種產(chǎn)品的庫存量，

—第月、第種產(chǎn)品的產(chǎn)量，

—第月、第種機床的維修量。需求限制資源限制維修限制?第月維修哪幾臺機床可由人安排，只安排未維修的；例9（下料問題）某廠要做100套鋼架，每套由長為2.9米，2.1米和1.5米的圓鋼各一根組成。已知原料長7.4米。問如何下料使原料最省。試建模。問題分析：“最節(jié)省”可以是“所用原料根數(shù)最少”，也可以是“余料最少”?；谇罢呓！Ｒ桓箱摴苡胁煌那懈罱M合…..。找出每一種組合用去多少根原料鋼管。所以首先列出所有可能組合即“模式”。解將8種下料方案列表:方案根數(shù)長度合計6.06.67.26.37.46.57.17.3余料1.40.80.21.100.90.30.1需求量若希望余料最少，則?余料超過1.5米?約束條件取“＝100”?設(shè)需根原料，第根下第種圓鋼根，n是決策變量，而線性規(guī)劃模型中是定數(shù)！該模型不易計算！以下幾種作法欠妥：五、選址問題客戶擬定的設(shè)施地址（1）離散型選址問題（2）連續(xù)型選址問題設(shè)施的地址未擬定，可選在所論區(qū)域（很大）的任何地方。問題：第個設(shè)施是否需修建？若要修建，應(yīng)為周圍哪些客戶服務(wù)？選址—分配問題例10（離散型）施工點j對某材料的需求量為第i個料場的容量為的單位運費

(元/噸).求使總費用最少的場址。可基于兩種考慮建模：2°施工點只能在某一料場獲取全部所需材料。1°施工點可在任何料場獲取部分材料，以滿足需求；建場費為di

元,解1°假定：?任何施工點到任何料場的道路是通的；?施工點可在任何料場獲取部分材料，以滿足需求；擬定m個地方建料場，為地址到施工點一個大型工程有n個施工點，則總費用需求限制容量限制非負限制mins.t.混合整數(shù)規(guī)劃模型2°假定：?任何施工點到任何料場的道路是通的；?施工點只能在某一料場獲取全部所需材料。設(shè)則總費用需求限制容量限制mins.t.非負限制0—1規(guī)劃模型由于區(qū)域很大，所以施工點到料場間的距離視為直線距離例11（連續(xù)型）設(shè)工程所涉及的區(qū)域很大，第j個施工點的坐標為：單位運費為c(元/噸/公里),欲建的m個料場地址未擬定，其余條件與例11相同。求使總費用最少的場址。解基于第二種考慮建模設(shè)料場的坐標為mins.t.

同前例

對可不作非負限制，稱為自由變量非線性規(guī)劃模型注：(1)若m個料場都要修建，則不設(shè)0—1變量（3）若區(qū)域小，且道路呈網(wǎng)狀，則使用矩形距離（2）指標不一定是“費用”，可以是“客戶”到“設(shè)施”的最大距離最小等。相當(dāng)于將取成1。目標函數(shù)中的常數(shù)項應(yīng)去掉。若希望用戶到中心的最大距離越小越好，則???也可以是用戶到中心的距離之和最小建模。均在第一象限內(nèi)，例12

設(shè)某城市的街道成縱橫交叉的網(wǎng)狀，今欲建一物資供應(yīng)中心，供n個用戶。問該中心建在什么位置合適。試建模。),,(yx處，坐標為供應(yīng)中心建在街道拐角問題！以下幾種作法不妥：?用直線距離?沒設(shè)“中心”建在街道拐角處?將“中心”取在坐標原點，決策變量？?設(shè)第個用戶的需求量為，單位運費為，…得（總運費）例13某公司有工廠A1,A2生產(chǎn)某種產(chǎn)品，生產(chǎn)能力分別為Q1,Q2,有四個容量為Mk的倉庫Bk(k=1,2,3,4)存放該產(chǎn)品，工廠和倉庫均可向n個客戶Cj(j=6,7,…n+5)供貨，客戶需求量為qj(j=6,7,…n+5).現(xiàn)公司打算：擴建倉庫B1,其月費用為e1，庫容量增加M；新建倉庫B5,月費用為e5，庫容量為M5;關(guān)閉倉庫B2或B3,關(guān)閉后可節(jié)約費用e2或e3;并要求總的倉庫數(shù)不得超過4個。已知工廠Ai向倉庫或客戶供貨的運費每單位為cij(i=1,2;j=1,2,3,4,5為向倉庫供貨的運費，j=6,7,…,n+5為向客戶供貨的運費)。第k個倉庫向第j個客戶供貨的單位運費dkj(k=1,2,3,4,5;j=6,7,…,n+5)。以上費用均由公司負擔(dān)。問公司該作何選擇可使總費用最少。解為便于理解，先作網(wǎng)絡(luò)圖。工廠倉庫客戶可仿運輸問題，將有關(guān)數(shù)據(jù)列表。產(chǎn)地銷地運價總量設(shè)9

產(chǎn)量限制客戶需求限制倉庫數(shù)量限制六、曲線擬合問題（去絕對值符號、化極大極小化模型為線性規(guī)劃模型）已知變量y（隨機變量）隨x（非隨機變量）變化。并已知一組樣本觀測值：求近似表示y與x之關(guān)系的經(jīng)驗方程—回歸方程。^對觀測值作散點圖，若點子沿一直線變化，則可用直線方程^作為經(jīng)驗方程。（回歸方程）所給的準則不同，求出的a,b也不同。常用方法—最小二乘法：^求使最小的a,b.由可解得a,b。求回歸直線這一過程，稱為擬合一條回歸直線。于是得到回歸方程^^稱函數(shù)值：為回歸值。所求回歸方程能否用于預(yù)測和控制，還需作假設(shè)檢驗。類似可擬合回歸曲線和回歸平面。例14（1）擬合一條回歸直線，使回歸值與觀測值的絕對偏差之和最小；（2）擬合一條回歸直線，使回歸值與觀測值的最大偏差最小。解設(shè)回歸方程為：^（1）依題意，求解這是一個無約束的非線性規(guī)劃模型，不便用微分法處理。已知變量y隨變量x變化，并已知一組觀察值去掉絕對值符號，化為線性規(guī)劃模型令則模型化為：是2n+2個決策變量，n個約束方程的線性規(guī)劃模型。（2）依題意，得一極大極小化模型：mina,b令因?qū)θ魏蝘都有：于是得非線性規(guī)劃模型：又因?qū)θ魏蝘都有：化線性規(guī)劃模型則得線性規(guī)劃模型：該模型中只有三個決策變量。＃七、人員時間安排問題例15某公司上午8點到21點各時段需要的服務(wù)人員數(shù)量如表1，四個班次的作息時間及月工資如表2。求既滿足需求又使公司所付工資總額最少的人員安排。序號時間區(qū)間需求人數(shù)表1班次工作時間休息時間月工資表2解利用表1、表2的各時間區(qū)間端點，將營業(yè)時間區(qū)間細分，并用“1”表示工作，“0”表示休息，得一關(guān)聯(lián)表（表3）。班次時段需求人數(shù)表3列給出了各班在哪幾個時段工作，行給出了各時段有哪幾個班在工作。設(shè)為第班安排的人數(shù)則得整數(shù)規(guī)劃模型：

且為整數(shù)，建該模型的關(guān)鍵是：找出各班次工作的關(guān)聯(lián)表，根據(jù)關(guān)聯(lián)表寫出約束條件。有多余的約束條件！例16

（選課策略）某校規(guī)定，運籌學(xué)專業(yè)的學(xué)生畢業(yè)時必須至少學(xué)習(xí)過兩門數(shù)學(xué)課、三門運籌學(xué)課和兩門計算機課。這些課程的編號、名稱、學(xué)分、所屬類別和先修課要求如表。問：畢業(yè)時，學(xué)生最少可以學(xué)習(xí)哪些課程？編號名稱學(xué)分所屬類別先修課要求微積分5數(shù)學(xué)線性代數(shù)4數(shù)學(xué)最優(yōu)化4數(shù)學(xué)；運籌學(xué)微積分；線代數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計算機計算機編程應(yīng)用統(tǒng)計4數(shù)學(xué)；運籌學(xué)微積分；線代計算機模擬3計算機；運籌學(xué)計算機編程7計算機編程2計算機預(yù)測理論2運籌學(xué)應(yīng)用統(tǒng)計9數(shù)學(xué)實驗3運籌學(xué)；計算機微積分；線代課程情況表建立課程與課程類別的關(guān)聯(lián)表：類別數(shù)學(xué)計算機運籌學(xué)課程微積分線代優(yōu)化結(jié)構(gòu)統(tǒng)計模擬編程預(yù)測實驗需求量則得0－1規(guī)劃模型：是前例中需求量為2，3，2的特別情形。解編號名稱

先修課要求微積分

線性代數(shù)

最優(yōu)化

微積分；線代

數(shù)據(jù)結(jié)構(gòu)

計算機編程

應(yīng)用統(tǒng)計

微積分；線代

計算機模擬

計算機編程7計算機編程

預(yù)測理論

應(yīng)用統(tǒng)計9數(shù)學(xué)實驗

微積分；線代課程情況表課程總數(shù)類別（需求）限制先修要求注意表述方法！例17

一個生產(chǎn)問題，有關(guān)數(shù)據(jù)如表。問如何安排生產(chǎn)可使總利潤最大，產(chǎn)量之和最小。要求第二種原料用完。單位利潤產(chǎn)品原料單耗甲乙總量解設(shè)為甲，乙的產(chǎn)量則雙目標規(guī)劃模型一般形式：矛盾的八、線性多目標規(guī)劃模型化成單目標規(guī)劃模型化法一或化法二

為目標權(quán)重或偏好系數(shù)。

均可看成參數(shù)，對不同的參數(shù)值求出最優(yōu)解，然后加以討論，選出滿意解。例17中，要求利潤最大，同時產(chǎn)量之和最小，這種目標稱為理想目標。這些目標往往是相互矛盾的，不可能同時達到最優(yōu)。更現(xiàn)實的做法是：給出目標值，將理想目標轉(zhuǎn)化為現(xiàn)實目標，求出盡量達到目標值的生產(chǎn)方案。如要求：總利潤產(chǎn)量之和把目標函數(shù)轉(zhuǎn)化成了約束條件引入正負偏差變量、，將多目標規(guī)劃模型轉(zhuǎn)化為目標規(guī)劃模型。九、線性目標規(guī)劃模型Min

要“”成立，只需min要“＝”成立，需min目標規(guī)劃模型達成函數(shù)一般方法：目標類型目標規(guī)劃格式極小化注：1.對于硬約束“”,可不設(shè)正偏差變量，即直接取。對于“”，可直接取。2.關(guān)于優(yōu)先級問題例如：上例中，目標的重要性依次為：1°A,B