數學規劃模型I引言

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

的圓木鋸成矩形橫梁？該問題的數學模型為：用微分法容易求出其解。數學規劃模型格式：maxs.t.已知橫梁強度z與寬度x

成正比，與高度y

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

重要結論：當供應量與需求量均為整數時，模型的最優解是整數解。例2

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

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

為到的車流量，則流量守恒條件弧容量限制去掉去掉若不設v,則模型有四處需修改如果源、匯不止一個時，建模方法類似。可增加一個虛擬源、虛擬匯化成單源單匯的問題。

圖中的結點稱為源（發點），結點稱為匯（收點）。圖是單源單匯的情形。例42求從流出，到的最大流量。解設為到的流量，

、為流入、的量，

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

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

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

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

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

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

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

為第月比第月增加一個產品要支付的費用，b

為減少一個產品支付的費用，c

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

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

—第月初、第種產品的庫存量，

—第月、第種產品的產量，

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

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

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

同前例

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

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

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

且為整數，建該模型的關鍵是：找出各班次工作的關聯表，根據關聯表寫出約束條件。有多余的約束條件！例16

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

先修課要求微積分

線性代數

最優化

微積分；線代

數據結構

計算機編程

應用統計

微積分；線代

計算機模擬

計算機編程7計算機編程

預測理論

應用統計9數學實驗

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

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

為目標權重或偏好系數。

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

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