數(shù)學建模運籌模型1

線性規(guī)劃運輸問題指派問題網(wǎng)絡優(yōu)化動態(tài)規(guī)劃書目例某工廠在支配期內要支配Ⅰ，Ⅱ兩種產品的生產，已知生產單位產品所需的設備臺時及A，B兩種原材料的消耗、資源的限制，如下表。問題：工廠應分別生產多少單位Ⅰ，Ⅱ產品才能使工廠獲利最多？

線性規(guī)劃例下料問題某工廠要做100套鋼架，每套用長為2.9m，2.1m，1.5m的圓鋼各一根，已知原料每根長7.4m。應如何下料，可使所用原料最?。拷猓汗部稍O計下列5種下料方案線性規(guī)劃建模步驟：(1)確定決策變量：我們須要作出決策或者選擇的量，一般狀況下，題目問什么就設什么為決策變量。(2)找出約束條件：即決策變量受到的全部的約束。(3)寫出目標函數(shù)：即問題所要達到的目標，并明確是求max還是min。線性規(guī)劃例混合配料問題某糖果廠用原料1、2、3加工三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果中原料1、2、3的含量、原料每月限用量、三種牌號糖果的加工費及售價，如下表所示。該廠每月如何生產才能獲利最大？線性規(guī)劃解：用i=1,2,3代表原料1,2,3,j=1,2,3代表糖果甲、乙、丙。Xij表示第j中產品中原料i的含量，則對于原料1：x11,x12,x13;對于原料2：x21,x22,x23;對于原料3：x31,x32,x33;對于甲：x11,x21,x31;對于乙：x12,x22,x32;對于丙：x13,x23,x33;目標函數(shù)：利潤最大，利潤=收入-原料成本-加工費約束條件：原料用量限制，含量限制線性規(guī)劃線性規(guī)劃求解方法：1.圖解法適合含有兩個決策變量的模型；

max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8

x1≥0,x2≥0可行域目標函數(shù)等值線最優(yōu)解64-860x1x2線性規(guī)劃2.單純形法(人工變量法、對偶單純形法)軟件求解：lingo，lindo，MatlabMinf=0.4x1+1.5x2+x3+1.3x4S.t.0.3x1+3x2++1.5x4>=3200.5x1++2x3+x4>=2401.4x1++0.7x4>=420線性規(guī)劃將某種物資從m個產地遇到n個銷地，每個產地都有確定的產量ai，i=1,2,……,m，每個銷地都對物資有確定的需求量bj,j=1,2,……,n。已知從第i個產地向第j個銷地運輸單位物資的運價為cij，總產量等于總需求量()。如何調運物資，才能使總運費最??？設xij為從產地Ai運往銷地Bj的運輸量，運輸問題

運輸表：

(產銷平衡的運輸問題)求解方法：1.確定初始基本可行解（西北角法、最小元素法、vogal法）2.最優(yōu)性檢驗；3.迭代求新的基本可行解。運輸問題例某食品公司下屬的三個食品廠A1、A2、A3生產食品，3個廠每月的生產實力分別為7噸、4噸、9噸，食品被運到B1、B2、B3、B4四個銷售點，它們對便利食品的月需求量分別為3噸、6噸、5噸、6噸，運輸表如下表，試制定最優(yōu)運輸方案。運輸問題解：1.確定初始基可行解最小元素法：運輸問題解：1.確定初始基可行解(最小元素法)初始基本可行解對應的目標函數(shù)值：f=3*4+10*3+1*3+2*1+4*6+5*3=86運輸問題解：2.最優(yōu)性檢驗(1)位勢：

ui+vj=cij(i=1,2,……,m,j=1,2,……,n)其中cij為基本可行解中基變量對應的單位運價。注：m+n-1個方程，m+n個變量。(2)利用位勢求非基變量檢驗數(shù)檢驗數(shù)計算公式：

cij-ui-vj

(3)檢驗數(shù)全都大于等于零時對應的解為最優(yōu)解。運輸問題位勢：檢驗數(shù)：運輸問題3.迭代求新基本可行解(1)負檢驗數(shù)中最小者對應的變量進基；(2)在運輸表中找一個包含進基變量的閉回路，這個回路上其他頂點均為基變量。依次對閉回路的四個頂點標號，將頂點分為奇點格和偶點格；(3)偶點格的最小值作為調整量，全部奇點格+調整量；偶點格-調整量，即一次迭代。(4)按位勢方程求新解對應的位勢及檢驗數(shù)，判別最優(yōu)性。運輸問題閉回路：

運輸問題迭代及新基本可行解的檢驗數(shù)計算：

運輸問題產銷不平衡運輸問題：1.供大于求，引入虛擬銷售點，并假設它的需求量為供不應求，引入虛擬的產地，并假設它的產量為由于虛擬銷地是不存在的，事實上這個差值是在產地貯存的，故從產地到虛擬銷地的單位運價為0；同理，由于虛擬產地是不存在的，所以虛設的產地到各個銷地的單位運價也為0.運輸問題例2個化肥廠供應3個地區(qū)的化肥，試確定運費最小的調運方案。解：增加虛設的銷地B4，銷量為10，構造產銷平衡的運輸表。運輸問題初始基可行解及其檢驗數(shù)：迭代求新基本可行解：運輸問題n項任務，恰好有n個人擔當，由于每個人的專長不同，完成各工作的效率不同，于是產生了應指派哪個人去完成哪項，使得完成n項任務的總效率最高的問題，這類問題稱為指派問題。例有一份說明書，須要譯成英、日、德、俄四種文字，現(xiàn)有甲乙丙丁四個人，他們將說明書譯成不同文字所須要的時間如下表所示，問應指派哪個人完成哪項工作，耗用的總時間最少？指派問題

一般地，有n項任務、n個完成人，第i人完成第j項任務的代價為cij(i,j=1,2,……,n),為了求得總代價最小的指派方案，引入0-1型變量xij,令

數(shù)學模型為

注：指派問題是0-1整數(shù)規(guī)劃的特例，也是運輸問題的特例，其產地和銷地數(shù)均為1，各產地產量和各銷地銷量均為1.指派問題指派問題的求解方法：匈牙利法。匈牙利法基于下面的事實：假如系數(shù)矩陣的全部元素滿足：cij>=0，而其中有n個位于不同行不同列的一組0元素，則只要令對應于這些0元素位置的xij=1，其余的xij=0，就得到最優(yōu)解。

如則

指派問題求解上例：

行變換得列變換得

畫出最少覆蓋0元素的直線，r=4=矩陣階數(shù)，則可以找到最優(yōu)解,所需最少時間=4+4+9+11=28

甲-俄語從而得到最優(yōu)指派：乙-日語丙-英語丁-德語指派問題例支配甲、乙、丙、丁四個人去完成A、B、C、D、E五項任務，每人完成各項任務的時間如下表所示，由于任務重，人手少，考慮以下兩種狀況下的最優(yōu)支配方案，使得完成任務的總時間最少。(1)任務E必需完成，其他4項任務可選3項完成，但甲不能做A項工作；(2)其中有一人完成2項，其他人每人完成1項。解：這是一人數(shù)與任務數(shù)不等的指派問題，若用匈牙利法求解，需作以下處理。指派問題(1)由于任務數(shù)大于人數(shù)，所以須要有一個虛擬的人，設為戊。因為工作E必需完成，故設戊完成E的時間為M(M為特殊大的正數(shù))，即戊不能做工作E，其余的假想時間為0，建立的效率矩陣為：接受匈牙利解法求解過程如下：

指派問題(1)由于r=4<矩陣階數(shù)=5，須要調整0元素的分布。從該矩陣可看出，r=5=矩陣階數(shù)，因此能找到最優(yōu)指派方案。甲-B乙-D丙-E丁-A戊-C（戊為虛擬人，即任務C無人完成）最少的耗時數(shù)z=29+20+32+24=105指派問題(2)思路：方案1：甲，【甲】，乙，丙，丁方案2：甲，乙，【乙】，丙，丁方案3：甲，乙，丙，【丙】，丁方案4：甲，乙，丙，丁，【丁】方案5：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作A，B，C，D，E，虛擬工作F，G，H。這些方案較煩瑣，接受以下思路更為簡便。設有虛擬人戊，他集五人的優(yōu)勢為一身，即戊的費用是每人的最低，戊所做的工作即為此項工作的費用最低者的工作，效率矩陣支配表為：指派問題接受匈牙利解法求解：對C3做0元素的最小直線覆蓋，得r=5=n。結果為甲-B乙-D丙-E丁-A戊-C但戊為虛擬人，不能真做，它做C工作是借乙(此列最小時數(shù)26是C所創(chuàng)業(yè)績)的優(yōu)勢，應由乙來做，即乙做兩件工作：D、C。指派問題例最大收益的最優(yōu)支配問題：有5名工人完成5項不同的任務收益如表所示：

求使總收益達到最高的任務支配方案。解：這是一個尋求總收益為最大值的極大化問題，須要轉化為微小化問題才能用匈牙利解法。收益矩陣B=（bij），設b=max{bij}，令cij=b-bij，C=（cij），以C為效率矩陣的微小化問題即是原最大收益的極大化問題轉化而來。指派問題b=max{bij}=19，令cij=19-bij，C=（cij），接著對C矩陣接受匈牙利法求解，得到C的最優(yōu)支配方案為即甲-D乙-B丙-E丁-A戊-C，求得的最大總收益為74.指派問題237184566134105275934682網(wǎng)絡優(yōu)化最短路徑問題：有一批貨物要從節(jié)點1運輸?shù)焦?jié)點8，這兩點間的通路如下圖，每條弧旁邊的數(shù)字表明該弧的長度?？偮窂皆蕉蹋\費越低，為節(jié)約運輸費用，應當選擇怎樣的運輸路途？求從1到8的最短路徑。237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},w4=1w1=0w1=0237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},w2=2w1=0w4=1w2=2237184566134105275934682X={1,2,4}min{c16,c23,c25,c47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},w6=3w2=2w4=1w1=0w6=3237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},w7=3w2=2w4=1w1=0w6=3w7=3237184566134105275934682X={1,2,4,6,7}min{c23,c25,c75,c78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},w5=6w2=2w4=1w1=0w6=3w7=3w5=6237184566134105275934682X={1,2,4,6,7}min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},w3=8w2=2w4=1w1=0w6=3w7=3w5=6w3=8237184566134105275934682X={1,2,3,4,6,7}min{c38,c58,c78}=min{8+6,6+4,3+8}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},w8=10w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10237184566134105275934682X={1,2,3,4,6,7,8}1到10的最短路徑為{1，4，7，5，8}，長度為10。w2=2w4=1w1=0w6=3w7=3w5=6w3=8w8=10網(wǎng)絡優(yōu)化最大流問題：給出一個帶收發(fā)點的網(wǎng)絡，其每條弧的賦權稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點到收點的最大流量。2354671ffu25=6u42=2u45=4u23=3u13=7u34=4u46=3u36=1u65=7u57=9u67=8u12=8邊的容量和流量：容量uij，流量xij可行流： 滿足以下條件的流稱為可行流： 1、每一個節(jié)點流量平衡 2、0≤xij≤uij假如xij=uij，邊從i到j的方向是飽和的；假如xij<uij，邊從i到j的方向是不飽和的；網(wǎng)絡優(yōu)化21xij=5uij=5（1，2）是飽和的21xij=3uij=5（1，2）是不飽和的間隙為12=u12-x12=5-3=2假如xij=0，邊從j到i的方向是飽和的（2，1）是飽和的假如xij>0，邊從j到i的方向是不飽和的網(wǎng)絡優(yōu)化21xij=0uij=521xij=5uij=5（2，1）是不飽和的間隙為12=x12=5給出一個初始的可行流xij=02354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0網(wǎng)絡優(yōu)化2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0找到全部的不飽和邊，以及各邊可以調整流量的方向2354671f=0f=0u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0x=0=3=1=8=8x=0找到一條從1到7的不飽和鏈鏈的間隙為：=min{8,3,1,8}=1調整鏈的流量：xij’=xij+2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=1x=1x=1x=1調整流量，f=1。接著求出網(wǎng)絡的不飽和邊2354671f=1f=1u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=0x=0x=0x=0x=0x=0x=0x=0x=1x=1x=1x=1=1=6=9=7求出一條從1到7的不飽和鏈=min{7,1,6,9}=1,調整流量xij’=xij+1,f’=f+1=22354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0x=0x=1x=0x=0x=0x=1x=1x=1x=1x=0調整流量，接著求出網(wǎng)絡的不飽和邊2354671f=2f=2u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=1x=0x=0x=1x=0x=0x=0x=1x=1x=1x=1x=0=5=8=7求出一條從1到7的不飽和鏈=min{7,5,8}=5,調整流量xij’=xij+5,f’=f+5=2+5=72354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=0x=1x=0x=0x=0x=6x=1x=1x=6x=0調整流量，接著求出網(wǎng)絡的不飽和邊2354671f=7f=7u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=0x=1x=0x=0x=0x=6x=1x=1x=6x=0=4=4=3=6求出一條從1到7的不飽和鏈=min{6,7,4,3}=3,調整流量xij’=xij+3,f’=f+3=7+3=102354671f=10f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=3x=4x=3x=0x=0x=9x=1x=1x=6x=0調整流量，接著求出網(wǎng)絡的不飽和邊2354671f=10u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=3x=4x=3x=0x=0x=9x=1x=1x=6x=0f=10=1=3=7=3求出一條從1到7的不飽和鏈=min{3,1,3,7}=1,調整流量xij’=xij+1,f’=f+1=10+1=112354671f=11f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=4x=5x=3x=1x=0x=9x=2x=1x=6x=0調整流量，接著求出網(wǎng)絡的不飽和邊已找不到一條從1到7的不飽和鏈，從1起先可以到達的節(jié)點為1，2，32354671f=11u=6u=2u=4u=3u=7u=4u=3u=1u=7u=9u=8u=8x=6x=0x=4x=5x=3x=1x=0x=9x=2x=1x=6x=0f=11已求得最大流最大流f=11，最小割集為（2,5）（3,4）（3,5）u25+u34+u35=6+4+1=11最短路問題：給定一個運輸網(wǎng)絡，兩點之間連線上的數(shù)字表示兩點之間的距離，試求一條從A到B的運輸路途，使總距離最短?？蓪栴}分為四個階段：第一階段，從A到B；其次階段，從B到C；第三階段，從C到D；第四階段，從D到E。完全枚舉：3*3*2*1=24條。最優(yōu)解：A→B3→C2→D2→E動態(tài)規(guī)劃階段：將所給問題的過程，按時間或空間特征分解成相互聯(lián)系的階段，以便按次序求每階段的解k——描述階段的變量狀態(tài)：表示每個階段起先時所處的自然狀況或條件，描述了探討問題的狀況。sk——狀態(tài)變量Sk——狀態(tài)集合S1={A},S2={B1,B2,B3},S3={C1,C2,C3},S4={D1,D2}動態(tài)規(guī)劃中狀態(tài)的性質：無后效性，即假如某個階段狀態(tài)給定之后，則在這階段以后過程的發(fā)展不受這階段以前各階段狀態(tài)的影響。決策：指在某階段對可供選擇狀態(tài)的選擇，描述的變量稱為決策變量。dk(sk)——決策變量Dk(sk)——允許決策集合D2(B1)={C1,C2,C3}動態(tài)規(guī)劃全過程策略：由全部各階段組成的決策函數(shù)序列,簡稱策略。記為：P1,n(s1)或P1,n(s1)={d1(s1),d2(s2),……,dn(sn)}k子過程策略(后部子策略)：由k階段起先到最終階段結束，組成的決策函數(shù)序列。Pk,n(sk)={dk(sk),dk+1(sk+1),……,dn(sn)}最優(yōu)策略：使整個問題達到最優(yōu)效果的策略。P*1,n(A)={B3,C2,D2,E}A→B3→C2→D2→E允許策略集：可供選擇策略的范圍，用P表示。動態(tài)規(guī)劃方法就是要從允許策略集P中找出最優(yōu)策略P*k,n動態(tài)規(guī)劃狀態(tài)轉移方程：本階段狀態(tài)與上一階段狀態(tài)和上一階段決策的關系，用狀態(tài)轉移方程來表示。

sk+1=Tk(sk,dk)該方程描述了由第k階段到第k+1階段的狀態(tài)轉移規(guī)律，又稱為狀態(tài)轉移函數(shù)。sk+1=dk(sk)階段指標：衡量某階段決策效益優(yōu)劣的策略指標，如距離，成本，利潤等。vk(sk,dk)指標函數(shù)：衡量所選定策略優(yōu)劣的數(shù)量指標。Vk,n(sk,Pk,n)=Vk,n(sk,dk,sk+1,……,sn+1)動態(tài)規(guī)劃常見指標函數(shù)形式(分別性，遞推關系)Vk,n(sk,Pk,n)=Vk,n(sk,dk,sk+1,……,sn+1)=Vk(sk,dk)+Vk+1(sk+1,Pk,n)Vk,n(sk,Pk,n)=Vk,n(sk,dk,sk+1,……,sn+1)=Vk(sk,dk)*Vk+1(sk+1,Pk,n)最優(yōu)指標函數(shù):指標函數(shù)的最優(yōu)值，fk(sk)表示從第k階段狀態(tài)sk起先接受最優(yōu)策略P*k,n到過程終止時的最佳效益值。fk(sk)=optVk,n(sk,dk,sk+1,……,sn+1)f1(s1)表示從第1階段狀態(tài)s1接受最優(yōu)策略P*1,n到過程終止時的最佳效益值。動態(tài)規(guī)劃動態(tài)規(guī)劃的基本思想：1.多階段決策過程劃分階段，恰當?shù)倪x取狀態(tài)變量、決策變量和定義最優(yōu)指標函數(shù)，從而將問題化為一族同類型的子問題逐個求解。2.求解時從邊界條件起先，逆（或順）過程行進方向，逐段遞推尋優(yōu)。3.既將當前一段與將來各段分開，又將當前效益與將來效益結合起來考慮的一種最優(yōu)化方法。如何建立動態(tài)規(guī)劃模型：1.分析識別問題的多階段特性，按時間或空間的先后依次適當?shù)貏澐譂M足遞推關系的若干階段。2.確定狀態(tài)變量，滿足可知性和無后效性。一般為累計量和隨遞推過程變更的量。3.找到狀態(tài)轉移方程。4.正確確定基本方程?；A：最優(yōu)化定理作為整個過程的最優(yōu)策略具有如下性質：不管在此最優(yōu)策略上的某個狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)而言，以后全部的決策必定構成最優(yōu)子策略。對最短路問題而言,從最短路上任一點到終點的部分道路（最短路上的子路）也確定是從該點到終點的最短路。動態(tài)規(guī)劃從最終一段起先計算，由后向前逐步推移至A點。第四階段，由D1到E只有一條線路，其長度f4(D1)=3，同理f4(D2)=4；第三階段，由Cj到Di均有兩種選擇，即其次階段，由Bj到Ci均有三種選擇，即動態(tài)規(guī)劃第一階段，由A到B，有三種選擇，即f1(A)=12，說明從A到E的最短距離為12，最短路途的確定可按計算依次反推而得，即A-B3-C2-D2-E動態(tài)規(guī)劃一個著名的命題：一個串村走戶的賣貨郎，他從某個村莊動身，通過若干個村莊一次且僅一次，最終仍回到原動身的村莊，問：應如何選擇行走路途，能使得總的行程最短。設有n個城市，1,2,…,n。Dij表示從i城到j城的距離。規(guī)定推銷員是從城市1起先的，設推銷員走到i城，記Ni＝{2,3,…,i-1,i+1,…,n}表示由1城到i城的中間城市集合。S表示到達i城中途所經過的城市的集合，則有SNi1）選?。╥,S）作為狀態(tài)變量，表示推銷員從城市1起先走到i城，經過若干個城市，構成集合S。2）最優(yōu)值函數(shù)fk(i,S)為從城市1起先經過k個中間城市的S集到達i城的最短路途的距離。貨郎擔問題（TSP問題——travelingsalespersonproblem）3）遞推關系式：fk(i,S)=min[fk-1(j,S\{j})+Dji](k=1,2,…,n-1.i=2,3…,n.SNi)邊界條件：f0(i,?)=D1i4）Pk(i,S)為最優(yōu)決策函數(shù)，表示從1城起先經k個中間城市到i城的最短路途上緊挨著i城前面的那個城市。例：當推銷員從1城動身，經過每個城市一次且僅一次，最終回到1城，問按怎樣的路途走，使總的行程距離最短。（四個城市，其距離矩陣如下表）5）由邊界條件可知：f0(i,?)=D1if0(2,?)=D12＝8，f0(3,?)=D13＝5，f0(4,?)=D14＝6當k=1時，即從1城起先，中間經過一個城市到達i城的最短距離是：f1(2,{3})=f0(3,?)+D32＝5+9=14f1(2,{4})=f0(4,?)+D42＝6+7=13f1(3,{2})=f0(2,?)+D23＝8+8=16f1(3,{4})=f0(4,?)+D43＝6+8=14f1(4,{2})=f0(2,?)+D24＝8+5=13f1(4,{3})=f0(3,?)+D34＝5+5=101i1i當k=2時，即從1城起先，中間經過兩個城市到達i城的最短距離是：f2(2,{3,4})=min[f1(3,{4})+D32f1(4,{3})+D42]=min[14+9,10+7]=17P2(2,{3,4})=41if2(3,{2,4})=min[f1(2,{4})+D23f1(4,{2})+D43]=min