版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第04章線性規(guī)劃:網(wǎng)絡(luò)流及整數(shù)規(guī)劃
LinearProgramming:NetworkFlowandintegerprogramming第04章線性規(guī)劃:網(wǎng)絡(luò)流及整數(shù)規(guī)劃
LinearProg最小費(fèi)用流問題網(wǎng)絡(luò)單純形法
-生成樹與基-原始網(wǎng)絡(luò)單純形法-對(duì)偶網(wǎng)絡(luò)單純形法網(wǎng)絡(luò)流問題的應(yīng)用
-運(yùn)輸問題和指派問題-最短路問題-最大流問題最小費(fèi)用流問題最小費(fèi)用流問題最小費(fèi)用流問題網(wǎng)絡(luò)基本元素:節(jié)點(diǎn)集(nodes),設(shè)頂點(diǎn)的個(gè)數(shù)為m
有向弧集(directedarcs)
是所有可能弧集的子集弧是有方向的:網(wǎng)絡(luò)基本元素:是所有可能弧集網(wǎng)絡(luò)流的數(shù)據(jù)注:將供給重新表示為負(fù)需求,節(jié)點(diǎn)i
的需求量
,沿著弧(i,j)運(yùn)輸1單位物品的費(fèi)用假定I:供需平衡問題網(wǎng)絡(luò)流的數(shù)據(jù)注:將供給重新表示為負(fù)需求網(wǎng)絡(luò)流問題決策變量:目標(biāo):,沿著弧(i,j)運(yùn)輸?shù)臄?shù)量網(wǎng)絡(luò)流問題決策變量:目標(biāo):網(wǎng)絡(luò)流問題-續(xù)約束:
質(zhì)量守恒(massconservation)inflow(k)–outflow(k)=demand(k)=-supply(k),
非負(fù)性假定II:弧沒有容量限制網(wǎng)絡(luò)流問題-續(xù)約束:質(zhì)量守恒(massconservat矩陣記號(hào)A是點(diǎn)弧關(guān)聯(lián)矩陣(node-arcincidencematrix)
通常A的維數(shù)很大,并且是稀疏的注其中:矩陣記號(hào)A是點(diǎn)弧關(guān)聯(lián)矩陣(node-arcinciden對(duì)偶問題對(duì)偶變量對(duì)偶松弛變量用網(wǎng)絡(luò)記號(hào):對(duì)偶問題對(duì)偶變量對(duì)偶松弛變量用網(wǎng)絡(luò)記號(hào):互補(bǔ)松弛關(guān)系(ComplementarityRelations)
原變量必須是非負(fù)的因此與之相聯(lián)系的對(duì)偶約束是不等式對(duì)偶松弛變量與原變量是互補(bǔ)的:
原始約束是等式因此他們沒有松弛變量對(duì)應(yīng)的對(duì)偶變量,,是自由變量對(duì)于他們互補(bǔ)條件是自然成立的互補(bǔ)松弛關(guān)系(ComplementarityRelatio網(wǎng)絡(luò)單純形法網(wǎng)絡(luò)單純形法定義:子網(wǎng)絡(luò)(Subnetwork)網(wǎng)絡(luò)子網(wǎng)絡(luò)定義:子網(wǎng)絡(luò)(Subnetwork)網(wǎng)絡(luò)子網(wǎng)絡(luò)定義:連通vs.不連通(Connectedvs.Disconnected)連通不連通定義:連通vs.不連通(Connectedvs.Di定義:圈vs.非圈(Cyclicvs.Acyclic)圈非圈定義:圈vs.非圈(Cyclicvs.Acyclic定義:樹(Trees)樹=連通的+非圈非樹定義:樹(Trees)樹=連通的+非圈非樹定義:生成樹(SpanningTrees)生成樹-觸及到每個(gè)頂點(diǎn)的樹樹解的計(jì)算?樹解(treesolution)滿足流平衡約束給定生成樹且對(duì),定義:生成樹(SpanningTrees)生成樹-觸及到每樹解-原始流
固定一個(gè)根節(jié)點(diǎn),比如e樹解的計(jì)算:從葉子節(jié)點(diǎn)開始,逆向依次解流平衡方程葉子節(jié)點(diǎn):僅有一條弧相連接的節(jié)點(diǎn)樹解-原始流固定一個(gè)根節(jié)點(diǎn),比如e樹解的計(jì)算:從葉子節(jié)樹解-對(duì)偶變量與對(duì)偶松弛變量
利用計(jì)算非樹弧上的對(duì)偶松弛變量
從根節(jié)點(diǎn)開始,沿著樹弧利用向外遞歸計(jì)算,可得到頂點(diǎn)處的對(duì)偶變量樹解-對(duì)偶變量與對(duì)偶松弛變量利用樹解與基本可行解的關(guān)系引理.
A的秩是m-1;
在生成樹中,選擇一個(gè)節(jié)點(diǎn),刪除與之對(duì)應(yīng)的流平衡約束,并稱之為根節(jié)點(diǎn)(rootnode);對(duì)應(yīng)的關(guān)聯(lián)矩陣和供需向量定理
的m-1階子方陣是最小費(fèi)用流問題的基當(dāng)且僅當(dāng)其列對(duì)應(yīng)的弧恰好搭建成網(wǎng)絡(luò)的一個(gè)生成樹.定理’一個(gè)流向量是基本解當(dāng)且僅當(dāng)它是一個(gè)樹解.
樹解基本解;對(duì)偶變量單純形乘子;對(duì)偶松弛變量相對(duì)費(fèi)用系數(shù).樹解與基本可行解的關(guān)系引理.A的秩是m-1;原始網(wǎng)絡(luò)單純形法假設(shè)樹解是原始可行的,即滿足非負(fù)條件:入弧選取規(guī)則:選取弧(i,j)使得對(duì)偶松弛變量zij<0出弧選取規(guī)則:
在圈中,與入弧的方向相反;且在所有這樣可能的弧中流最小.原始流的更新(*****):與出弧同方向的減去出弧上的流;與出弧反方向的加上出弧上的流.入弧為(d,e);出弧為(d,c).原始網(wǎng)絡(luò)單純形法假設(shè)樹解是原始可行的,即滿足非負(fù)條件:入弧選(用于無容量限制網(wǎng)絡(luò)的)網(wǎng)絡(luò)單純形法:Step1.從一個(gè)可行的樹解開始,假設(shè)第n
個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn).Step2.計(jì)算對(duì)偶向量(單純形乘子):從根節(jié)點(diǎn)向葉子節(jié)點(diǎn),依次求解方程組Step3.計(jì)算對(duì)偶松弛向量(相對(duì)費(fèi)用系數(shù)/既約費(fèi)用系數(shù)):(i,j)使得,稱之為入弧.如果他們?nèi)秦?fù),當(dāng)前樹解是最優(yōu)的;否則,選取弧Step4.確定出?。喝牖『蜆浠”匦纬梢粋€(gè)圈.如果圈中的所有弧和入弧同向,則最優(yōu)費(fèi)用是-∞,終止算法.否則,在與入弧反向的樹弧中選一個(gè)最小的流作為出弧.Step5.轉(zhuǎn)軸:在當(dāng)前樹解中用入弧代替出弧,更新原始流,得新的樹解.轉(zhuǎn)Step2.(用于無容量限制網(wǎng)絡(luò)的)網(wǎng)絡(luò)單純形法:Step1.從一個(gè)對(duì)偶變量的更新
從新的生成樹中刪除入弧,得到網(wǎng)絡(luò)的兩個(gè)子樹;一個(gè)子樹含根節(jié)點(diǎn)(T0),另一個(gè)不含根節(jié)點(diǎn)(T1).子樹T0上的節(jié)點(diǎn)對(duì)應(yīng)的對(duì)偶變量不變;子樹T1上的節(jié)點(diǎn)對(duì)應(yīng)的對(duì)偶變量的更新準(zhǔn)則:入弧由T0指向T1時(shí),對(duì)偶變量統(tǒng)一加上入弧的對(duì)偶松弛變量入弧由T1指向T0時(shí),對(duì)偶變量統(tǒng)一減去入弧的對(duì)偶松弛變量對(duì)偶變量的更新從新的生成樹中刪除入弧,得到網(wǎng)絡(luò)對(duì)偶松弛變量的更新對(duì)偶松弛變量的更新策略:非橋接弧保持不變;與入弧同向橋接兩個(gè)子樹,對(duì)偶松弛變量
減去入弧上的原有對(duì)偶松弛變量;與入弧反向橋接兩個(gè)子樹,對(duì)偶松弛變量
加上入弧上的原有對(duì)偶松弛變量;對(duì)偶松弛變量的更新對(duì)偶松弛變量的更新策略:對(duì)偶網(wǎng)絡(luò)單純形法假設(shè)樹解是對(duì)偶可行的,即確定的對(duì)偶變量和對(duì)偶松弛變量滿足對(duì)偶問題的約束條件(即基本解是對(duì)偶可行的):出弧選取規(guī)則:選取樹弧(i,j)使得對(duì)應(yīng)流xij<0去掉出弧,生成樹變成兩個(gè)子樹;入弧必須橋接兩個(gè)子樹!出弧(c,a)入弧選取規(guī)則:
必須是橋接兩個(gè)子樹的非樹弧,
且與出弧反方向;在可選的中間選取對(duì)偶松弛最小的.入弧(d,e)對(duì)偶網(wǎng)絡(luò)單純形法假設(shè)樹解是對(duì)偶可行的,即確定的對(duì)偶變量和對(duì)偶出弧(c,a)入弧(d,e)最優(yōu)解!出弧(c,a)入弧(d,e)最優(yōu)解!
找一個(gè)樹解
法1
改變?cè)瓎栴}的費(fèi)用向量使得所給樹解是對(duì)偶可行的;利用對(duì)偶網(wǎng)絡(luò)單純形法求解新問題,得到最優(yōu)解;新問題的最優(yōu)解是原問題的可行樹解;從此樹解出發(fā),利用原始網(wǎng)絡(luò)單純形法求解所給問題.
法2
改變?cè)瓎栴}的供給向量使得所給樹解是原始可行的;利用原始網(wǎng)絡(luò)單純形法求解新問題,得到最優(yōu)解;新問題的最優(yōu)解是原問題的對(duì)偶可行樹解;從此樹解出發(fā),利用對(duì)偶網(wǎng)絡(luò)單純形法求解所給問題.求解一般的最小費(fèi)用流問題:找一個(gè)樹解法2求解一般的最小費(fèi)用流問題:整性定理(IntegralityTheorem)整性定理.考慮無容量限制的網(wǎng)絡(luò)流問題.i)如果供給量bi是整數(shù),則每個(gè)基本可行解的分量是整數(shù).ii)如果費(fèi)用系數(shù)
cij
是整數(shù),則每個(gè)對(duì)偶基本解的分量是整數(shù).整數(shù)線性規(guī)劃通常不易求解;但是具有整性數(shù)據(jù)的最小費(fèi)用流問題可用網(wǎng)絡(luò)單純形法求解!整性定理(IntegralityTheorem)整性定理.網(wǎng)絡(luò)流:應(yīng)用網(wǎng)絡(luò)流:應(yīng)用運(yùn)輸問題(TransportationProblem)每個(gè)頂點(diǎn)是兩種類型之一:
發(fā)(源/供給)點(diǎn)收(目的/需求)點(diǎn)每條弧滿足:
起點(diǎn)在發(fā)點(diǎn)終點(diǎn)在收點(diǎn)二部/分圖(bipartite)供給節(jié)點(diǎn)需求節(jié)點(diǎn)運(yùn)輸問題(TransportationProblem)每個(gè)運(yùn)輸問題的表上作業(yè)法數(shù)據(jù)表運(yùn)輸表7個(gè)頂點(diǎn)8條弧!有6個(gè)基變量,2個(gè)非基變量對(duì)偶變量
需求量供給量102315756*1184318*9*12*36運(yùn)輸問題的表上作業(yè)法數(shù)據(jù)表運(yùn)輸表7個(gè)頂點(diǎn)8條?。∮?指派問題(AssignmentProblem)
給定m個(gè)人和m項(xiàng)任務(wù),第i個(gè)人完成任務(wù)j的費(fèi)用是cij
指派每個(gè)人去做且只做一項(xiàng)任務(wù)每項(xiàng)任務(wù)只由一個(gè)人去完成
忽略整數(shù)要求,由整性定理,利用網(wǎng)絡(luò)單純形法可得到指派問題的解!問題是嚴(yán)重退化的,有2m個(gè)約束,但基本解只有m個(gè)非零元素!相對(duì)于二次指派問題,稱這里的問題為線性指派問題!指派問題(AssignmentProblem)給定m最短路問題(ShortestPathsProblem)給定:
網(wǎng)絡(luò):
費(fèi)用=旅行時(shí)間:根節(jié)點(diǎn)(homeorroot):?jiǎn)栴}:找從N中每一個(gè)節(jié)點(diǎn)出發(fā)到根節(jié)點(diǎn)的最短路(有向的)根節(jié)點(diǎn)5:
1→3→5:5
2→5:53→5:14→3→5:3
1
4
2
3
5
7
4
5
1
2
5
1
4
最短路問題(ShortestPathsProblem)給網(wǎng)絡(luò)流表述
令vi=從節(jié)點(diǎn)i
到根節(jié)點(diǎn)r
的最短時(shí)間
在網(wǎng)絡(luò)文獻(xiàn)中稱為標(biāo)號(hào)(label);
在動(dòng)態(tài)規(guī)劃的文獻(xiàn)中稱為值(value).以下算法中使用的記號(hào):
令
求解最小費(fèi)用網(wǎng)絡(luò)流問題從i
到r
的最短路:由最優(yōu)樹弧得到最短路的長度(時(shí)間)=網(wǎng)絡(luò)流表述令vi=從節(jié)點(diǎn)i到根節(jié)點(diǎn)r的最短時(shí)間標(biāo)號(hào)校正算法(LabelCorrectingAlgorithm)動(dòng)態(tài)規(guī)劃(DynamicProgramming)Bellman方程組、動(dòng)態(tài)規(guī)劃原理不必是一個(gè)樹!
逐次逼近法(MethodofsuccessiveApproximation)-初始化:-迭代:-終止:當(dāng)某次迭代沒有一個(gè)vi改變時(shí),終止算法.標(biāo)號(hào)校正算法(LabelCorrectingAlgori標(biāo)號(hào)校正算法的復(fù)雜度
vi(k)=從節(jié)點(diǎn)i
到根節(jié)點(diǎn)
r
且有k
條弧或者更少的最短路的長度
最多要求m-1次迭代每次迭代作n
次加/比較運(yùn)算總共需要mn次運(yùn)算標(biāo)號(hào)校正算法的復(fù)雜度vi(k)=從節(jié)點(diǎn)i到根節(jié)點(diǎn)r標(biāo)號(hào)設(shè)置算法(LabelSettingAlgorithm)Dijkstra算法,1959年記號(hào):
F=已完成的節(jié)點(diǎn)集(標(biāo)號(hào)被設(shè)定)
=在i
之后要訪問的節(jié)點(diǎn)(終點(diǎn))Dijkstra算法:
初始化:
迭代:-當(dāng)還有未完成的節(jié)點(diǎn)時(shí),選擇vi
最小的節(jié)點(diǎn),記為j.
將j
添加到已完成節(jié)點(diǎn)集-對(duì)每個(gè)未完成的節(jié)點(diǎn)i
,且有弧(i,j)將i
和j
連接起來:標(biāo)號(hào)設(shè)置算法(LabelSettingAlgorithmDijkstra最短路算法的流程根節(jié)點(diǎn)5:
1→3→5:5
2→5:53→5:14→3→5:3Dijkstra最短路算法的流程根節(jié)點(diǎn)5:Dijkstra算法的復(fù)雜度
每次迭代完成一個(gè)節(jié)點(diǎn):m
次迭代
每次迭代的計(jì)算量:-選擇一個(gè)未完成的節(jié)點(diǎn):*普通的需要m
次比較*使用合適的數(shù)據(jù)結(jié)構(gòu),需要logm次比較-更新鄰接弧總共:mlogm+nDijkstra算法的復(fù)雜度每次迭代完成一個(gè)節(jié)點(diǎn):m次迭最大流問題(MaximumFlowProblem)給定:?jiǎn)栴}:求從s
到t
的最大流量(將盡可能多的流從s
推向t)
網(wǎng)絡(luò):,A
是點(diǎn)弧關(guān)聯(lián)矩陣
弧上流量的上界:發(fā)點(diǎn),收點(diǎn)Ford-Fulkerson算法最大流-最小割定理最大流問題(MaximumFlowProblem)給定:網(wǎng)絡(luò)流表述
令
添加人工弧(t,s):網(wǎng)絡(luò)流表述令割及割的容量
s-t
割(cut):包含發(fā)點(diǎn)s
但不包含收點(diǎn)t
的節(jié)點(diǎn)集合C
割的容量(capacity):流平衡方程:割及割的容量s-t割(cut):包含發(fā)點(diǎn)s但不包含收最大流-最小割定理(Max-FlowMin-CutTheorem)定理.在任一網(wǎng)絡(luò)中,最大流的流量等于最小割的容量.
由Ford與Fulkerson于1956年提出來的,是圖論和網(wǎng)絡(luò)流中的最重要結(jié)論之一!設(shè)是最大流問題的解xts
*設(shè)是對(duì)偶問題的解證明最大流-最小割定理(Max-FlowMin-CutThe線性整數(shù)規(guī)劃線性整數(shù)規(guī)劃
整數(shù)線性規(guī)劃
-調(diào)度問題-旅行商問題-實(shí)用的建模技術(shù)分支定界法
整數(shù)線性規(guī)劃調(diào)度問題(SchedulingProblems)
設(shè)備調(diào)度(equipmentscheduling)
人員調(diào)度(crewscheduling)Airlinescheduling:
Route-identificationRouteOptimization(√)調(diào)度問題(SchedulingProblems)設(shè)備調(diào)度設(shè)備調(diào)度問題
可能的航線(route)集{1,2,……,n}
,對(duì)應(yīng)的費(fèi)用cjm
個(gè)航段(leg)集{1,2,……,m}
航線和航段的關(guān)系:?jiǎn)栴}:選取航線使得每個(gè)航段恰被覆蓋一次,且總費(fèi)用最小把航段合理的安排到不同的航線上!設(shè)備調(diào)度問題可能的航線(route)集{1,2,……機(jī)組人員調(diào)度問題
可能的航線(route)集{1,2,……,n}
,對(duì)應(yīng)的費(fèi)用cjm
組人員(flightcrews){1,2,……,m}
-可以理解為每組為一個(gè)航段服務(wù)航線和機(jī)組人員的關(guān)系:?jiǎn)栴}:選取航線使每組人員至少為一個(gè)航線服務(wù),且總費(fèi)用最小把機(jī)組人員合理地安排到航線上!機(jī)組人員調(diào)度問題可能的航線(route)集{1,2,
旅行商問題(TravelingSalesmanProblem,TSP)旅行商從城市0出發(fā),周游城市1,2,……,n-1;每個(gè)城市只經(jīng)過一次,最后回到城市0;城市兩兩之間的距離為cij問題:安排周游使總路程最短.周游=所有城市的排列可能的周游數(shù)目:(n-1)!旅行商問題(TravelingSalesmanProb
頂點(diǎn)約束原有問題的松弛該問題的解可能會(huì)含幾個(gè)有向子圈,也稱子周游.指派約束!想辦法排除子圈!頂點(diǎn)約束原有問題的松弛該問題的解可能會(huì)含幾個(gè)有向子圈,也稱
子周游表述(SubtourFormulation)添加一族子周游(消去)約束一開始不必把所有的子周游消去約束都放進(jìn)去;可以邊算邊放!有指數(shù)多個(gè)約束!NN子周游表述(SubtourFormulation)添加一0,ti∈{1,2,…,n-1},i≥1MTZ(Miller-Tucker-Zemlin)表述引入新變量ti
-表示進(jìn)入城市i
之前經(jīng)過的城市數(shù)目弧約束0規(guī)模小!可處理有偏好的周游!0,ti∈{1,2,…,n-1},i≥1MTZ
實(shí)用建模技術(shù)或約束:引入0-1變量y其中M是充分大的正數(shù)帶固定成本的目標(biāo)函數(shù):進(jìn)一步假設(shè)+實(shí)用建模技術(shù)或約束:引入0-1變量y其中M是充分大的非線性目標(biāo)函數(shù)-二次多項(xiàng)式
其中yij
滿足
其中zij
滿足非線性目標(biāo)函數(shù)-二次多項(xiàng)式其中yij滿足其中zij假設(shè)分成3段,即k=3非線性目標(biāo)函數(shù)-連續(xù)的逐段線性函數(shù)假設(shè)分成3段,即k=3非線性目標(biāo)函數(shù)-連續(xù)的逐段線性函數(shù)非線性目標(biāo)函數(shù)-連續(xù)的非線性函數(shù)連續(xù)非線性函數(shù)的逐段線性函數(shù)近似!非線性目標(biāo)函數(shù)-連續(xù)的非線性函數(shù)連續(xù)非線性函數(shù)的逐段線性函數(shù)整數(shù)線性規(guī)劃的線性規(guī)劃松弛(LP-relaxation)x*=(0,1),z*=1.9舍入到最近的整數(shù)(1,0)不可行!(2,0),(1,1),(2,2)可行但非最優(yōu)!線性規(guī)劃松弛:x=(1.5,0),=1.5整數(shù)線性規(guī)劃的線性規(guī)劃松弛(LP-relaxation)x*分支定界法分支定界法分支第一次分支當(dāng)前最好解(best-so-far)第二次分支枚舉樹(enumerationtree)線性規(guī)劃松弛:x=(1.5,0),=1.5分支第一次分支當(dāng)前最好解(best-so-far)第二次分支剪枝、廣探法與深探法剪枝(pruning)廣探法(breadth-first-search)深探法(depth-firstsearch)假如P1的最優(yōu)值為2.1剪枝、廣探法與深探法剪枝(pruning)廣探法(bread深探法與線性整數(shù)規(guī)劃探測(cè)到整數(shù)解的好處:一個(gè)可行解對(duì)應(yīng)一種可行設(shè)計(jì)或者可行決策!找到可行解就有可能更新當(dāng)前最好解,這可以幫助剪枝深探法的優(yōu)勢(shì):整數(shù)解通常位于枚舉樹的底層深探法的程序編寫較容易可應(yīng)用對(duì)偶單純形法求解下一層的子問題深探法與線性整數(shù)規(guī)劃探測(cè)到整數(shù)解的好處:深探法的優(yōu)勢(shì):應(yīng)用對(duì)偶單純形法求解子問題P1=P0+“x1≤1”P2=P0+“x1≥2”用單純形法求解P0,之后用對(duì)偶單純形法求解
P1和P2應(yīng)用對(duì)偶單純形法求解子問題P1=P0+“x1≤1”分支定界法的原理節(jié)點(diǎn)對(duì)應(yīng)著一個(gè)連續(xù)優(yōu)化問題,其中根節(jié)點(diǎn)對(duì)應(yīng)的是松弛問題P0;節(jié)點(diǎn)分三類:父節(jié)點(diǎn)、無可行解的葉子節(jié)點(diǎn)和解是整數(shù)的葉子節(jié)點(diǎn);節(jié)點(diǎn)之間由分支連接起來分支定界法中枚舉樹的結(jié)構(gòu)分支定界法的動(dòng)機(jī):通過探測(cè)枚舉樹來尋找解是整數(shù)的葉子節(jié)點(diǎn),從而找到目標(biāo)值最小的一個(gè)。在一個(gè)父節(jié)點(diǎn),連續(xù)優(yōu)化問題的解可能有多個(gè)分量違反整性約束。因此有多種方式來選取分支變量。從而枚舉樹不是惟一確定的。分支定界法的原理節(jié)點(diǎn)對(duì)應(yīng)著一個(gè)連續(xù)優(yōu)化問題,其中根節(jié)點(diǎn)對(duì)應(yīng)的分支定界法的原理II下一次應(yīng)該求解哪個(gè)節(jié)點(diǎn)對(duì)應(yīng)的問題
;應(yīng)該對(duì)哪個(gè)變量進(jìn)行分支;為當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的子問題確定一個(gè)下界.2.從已經(jīng)探測(cè)到的整性葉子節(jié)點(diǎn)中,找到目前最好的整數(shù)可行解及目標(biāo)值;部分搜索策略中需要確定:1.保持一個(gè)未解決問題棧,且每個(gè)問題有一個(gè)最優(yōu)值的下界;棧(stack)方法:分支定界法的原理II下一次應(yīng)該求解哪個(gè)節(jié)點(diǎn)對(duì)應(yīng)的問題;2.63分支定界法IIIInitially,thecontinuousproblemisputinthestackwith,and算法4.3.1Branchandboundmethodforintegerprogrammingproblemthealgorithmproceedsasfollowing:(i)Ifnoproblemisinthestack,finishwithasx*andf*;Otherwisetakethetopproblemfromthestack.(ii)Ifrejecttheproblemandgoto(i).(iii)Trytosolvetheproblem:ifnofeasiblepointexistsrejecttheproblemandgoto(i).(iv)Letthesolutionbex`withf`:ifrejecttheproblemandgoto(i).(v)Ifx`isintegerfeasiablethensetandgoto(i).Selectanintegervariableisuchthat,creattwonewproblemsbybranchingonxi,placetheseonthestackwithlowerbound(orahigherlowerboundderivedfromf
`),andgoto(i).分支定界法IIIInitially,64第04章線性規(guī)劃:網(wǎng)絡(luò)流及整數(shù)規(guī)劃
LinearProgramming:NetworkFlowandintegerprogramming第04章線性規(guī)劃:網(wǎng)絡(luò)流及整數(shù)規(guī)劃
LinearProg最小費(fèi)用流問題網(wǎng)絡(luò)單純形法
-生成樹與基-原始網(wǎng)絡(luò)單純形法-對(duì)偶網(wǎng)絡(luò)單純形法網(wǎng)絡(luò)流問題的應(yīng)用
-運(yùn)輸問題和指派問題-最短路問題-最大流問題最小費(fèi)用流問題最小費(fèi)用流問題最小費(fèi)用流問題網(wǎng)絡(luò)基本元素:節(jié)點(diǎn)集(nodes),設(shè)頂點(diǎn)的個(gè)數(shù)為m
有向弧集(directedarcs)
是所有可能弧集的子集弧是有方向的:網(wǎng)絡(luò)基本元素:是所有可能弧集網(wǎng)絡(luò)流的數(shù)據(jù)注:將供給重新表示為負(fù)需求,節(jié)點(diǎn)i
的需求量
,沿著弧(i,j)運(yùn)輸1單位物品的費(fèi)用假定I:供需平衡問題網(wǎng)絡(luò)流的數(shù)據(jù)注:將供給重新表示為負(fù)需求網(wǎng)絡(luò)流問題決策變量:目標(biāo):,沿著弧(i,j)運(yùn)輸?shù)臄?shù)量網(wǎng)絡(luò)流問題決策變量:目標(biāo):網(wǎng)絡(luò)流問題-續(xù)約束:
質(zhì)量守恒(massconservation)inflow(k)–outflow(k)=demand(k)=-supply(k),
非負(fù)性假定II:弧沒有容量限制網(wǎng)絡(luò)流問題-續(xù)約束:質(zhì)量守恒(massconservat矩陣記號(hào)A是點(diǎn)弧關(guān)聯(lián)矩陣(node-arcincidencematrix)
通常A的維數(shù)很大,并且是稀疏的注其中:矩陣記號(hào)A是點(diǎn)弧關(guān)聯(lián)矩陣(node-arcinciden對(duì)偶問題對(duì)偶變量對(duì)偶松弛變量用網(wǎng)絡(luò)記號(hào):對(duì)偶問題對(duì)偶變量對(duì)偶松弛變量用網(wǎng)絡(luò)記號(hào):互補(bǔ)松弛關(guān)系(ComplementarityRelations)
原變量必須是非負(fù)的因此與之相聯(lián)系的對(duì)偶約束是不等式對(duì)偶松弛變量與原變量是互補(bǔ)的:
原始約束是等式因此他們沒有松弛變量對(duì)應(yīng)的對(duì)偶變量,,是自由變量對(duì)于他們互補(bǔ)條件是自然成立的互補(bǔ)松弛關(guān)系(ComplementarityRelatio網(wǎng)絡(luò)單純形法網(wǎng)絡(luò)單純形法定義:子網(wǎng)絡(luò)(Subnetwork)網(wǎng)絡(luò)子網(wǎng)絡(luò)定義:子網(wǎng)絡(luò)(Subnetwork)網(wǎng)絡(luò)子網(wǎng)絡(luò)定義:連通vs.不連通(Connectedvs.Disconnected)連通不連通定義:連通vs.不連通(Connectedvs.Di定義:圈vs.非圈(Cyclicvs.Acyclic)圈非圈定義:圈vs.非圈(Cyclicvs.Acyclic定義:樹(Trees)樹=連通的+非圈非樹定義:樹(Trees)樹=連通的+非圈非樹定義:生成樹(SpanningTrees)生成樹-觸及到每個(gè)頂點(diǎn)的樹樹解的計(jì)算?樹解(treesolution)滿足流平衡約束給定生成樹且對(duì),定義:生成樹(SpanningTrees)生成樹-觸及到每樹解-原始流
固定一個(gè)根節(jié)點(diǎn),比如e樹解的計(jì)算:從葉子節(jié)點(diǎn)開始,逆向依次解流平衡方程葉子節(jié)點(diǎn):僅有一條弧相連接的節(jié)點(diǎn)樹解-原始流固定一個(gè)根節(jié)點(diǎn),比如e樹解的計(jì)算:從葉子節(jié)樹解-對(duì)偶變量與對(duì)偶松弛變量
利用計(jì)算非樹弧上的對(duì)偶松弛變量
從根節(jié)點(diǎn)開始,沿著樹弧利用向外遞歸計(jì)算,可得到頂點(diǎn)處的對(duì)偶變量樹解-對(duì)偶變量與對(duì)偶松弛變量利用樹解與基本可行解的關(guān)系引理.
A的秩是m-1;
在生成樹中,選擇一個(gè)節(jié)點(diǎn),刪除與之對(duì)應(yīng)的流平衡約束,并稱之為根節(jié)點(diǎn)(rootnode);對(duì)應(yīng)的關(guān)聯(lián)矩陣和供需向量定理
的m-1階子方陣是最小費(fèi)用流問題的基當(dāng)且僅當(dāng)其列對(duì)應(yīng)的弧恰好搭建成網(wǎng)絡(luò)的一個(gè)生成樹.定理’一個(gè)流向量是基本解當(dāng)且僅當(dāng)它是一個(gè)樹解.
樹解基本解;對(duì)偶變量單純形乘子;對(duì)偶松弛變量相對(duì)費(fèi)用系數(shù).樹解與基本可行解的關(guān)系引理.A的秩是m-1;原始網(wǎng)絡(luò)單純形法假設(shè)樹解是原始可行的,即滿足非負(fù)條件:入弧選取規(guī)則:選取弧(i,j)使得對(duì)偶松弛變量zij<0出弧選取規(guī)則:
在圈中,與入弧的方向相反;且在所有這樣可能的弧中流最小.原始流的更新(*****):與出弧同方向的減去出弧上的流;與出弧反方向的加上出弧上的流.入弧為(d,e);出弧為(d,c).原始網(wǎng)絡(luò)單純形法假設(shè)樹解是原始可行的,即滿足非負(fù)條件:入弧選(用于無容量限制網(wǎng)絡(luò)的)網(wǎng)絡(luò)單純形法:Step1.從一個(gè)可行的樹解開始,假設(shè)第n
個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn).Step2.計(jì)算對(duì)偶向量(單純形乘子):從根節(jié)點(diǎn)向葉子節(jié)點(diǎn),依次求解方程組Step3.計(jì)算對(duì)偶松弛向量(相對(duì)費(fèi)用系數(shù)/既約費(fèi)用系數(shù)):(i,j)使得,稱之為入弧.如果他們?nèi)秦?fù),當(dāng)前樹解是最優(yōu)的;否則,選取弧Step4.確定出?。喝牖『蜆浠”匦纬梢粋€(gè)圈.如果圈中的所有弧和入弧同向,則最優(yōu)費(fèi)用是-∞,終止算法.否則,在與入弧反向的樹弧中選一個(gè)最小的流作為出弧.Step5.轉(zhuǎn)軸:在當(dāng)前樹解中用入弧代替出弧,更新原始流,得新的樹解.轉(zhuǎn)Step2.(用于無容量限制網(wǎng)絡(luò)的)網(wǎng)絡(luò)單純形法:Step1.從一個(gè)對(duì)偶變量的更新
從新的生成樹中刪除入弧,得到網(wǎng)絡(luò)的兩個(gè)子樹;一個(gè)子樹含根節(jié)點(diǎn)(T0),另一個(gè)不含根節(jié)點(diǎn)(T1).子樹T0上的節(jié)點(diǎn)對(duì)應(yīng)的對(duì)偶變量不變;子樹T1上的節(jié)點(diǎn)對(duì)應(yīng)的對(duì)偶變量的更新準(zhǔn)則:入弧由T0指向T1時(shí),對(duì)偶變量統(tǒng)一加上入弧的對(duì)偶松弛變量入弧由T1指向T0時(shí),對(duì)偶變量統(tǒng)一減去入弧的對(duì)偶松弛變量對(duì)偶變量的更新從新的生成樹中刪除入弧,得到網(wǎng)絡(luò)對(duì)偶松弛變量的更新對(duì)偶松弛變量的更新策略:非橋接弧保持不變;與入弧同向橋接兩個(gè)子樹,對(duì)偶松弛變量
減去入弧上的原有對(duì)偶松弛變量;與入弧反向橋接兩個(gè)子樹,對(duì)偶松弛變量
加上入弧上的原有對(duì)偶松弛變量;對(duì)偶松弛變量的更新對(duì)偶松弛變量的更新策略:對(duì)偶網(wǎng)絡(luò)單純形法假設(shè)樹解是對(duì)偶可行的,即確定的對(duì)偶變量和對(duì)偶松弛變量滿足對(duì)偶問題的約束條件(即基本解是對(duì)偶可行的):出弧選取規(guī)則:選取樹弧(i,j)使得對(duì)應(yīng)流xij<0去掉出弧,生成樹變成兩個(gè)子樹;入弧必須橋接兩個(gè)子樹!出弧(c,a)入弧選取規(guī)則:
必須是橋接兩個(gè)子樹的非樹弧,
且與出弧反方向;在可選的中間選取對(duì)偶松弛最小的.入弧(d,e)對(duì)偶網(wǎng)絡(luò)單純形法假設(shè)樹解是對(duì)偶可行的,即確定的對(duì)偶變量和對(duì)偶出弧(c,a)入弧(d,e)最優(yōu)解!出弧(c,a)入弧(d,e)最優(yōu)解!
找一個(gè)樹解
法1
改變?cè)瓎栴}的費(fèi)用向量使得所給樹解是對(duì)偶可行的;利用對(duì)偶網(wǎng)絡(luò)單純形法求解新問題,得到最優(yōu)解;新問題的最優(yōu)解是原問題的可行樹解;從此樹解出發(fā),利用原始網(wǎng)絡(luò)單純形法求解所給問題.
法2
改變?cè)瓎栴}的供給向量使得所給樹解是原始可行的;利用原始網(wǎng)絡(luò)單純形法求解新問題,得到最優(yōu)解;新問題的最優(yōu)解是原問題的對(duì)偶可行樹解;從此樹解出發(fā),利用對(duì)偶網(wǎng)絡(luò)單純形法求解所給問題.求解一般的最小費(fèi)用流問題:找一個(gè)樹解法2求解一般的最小費(fèi)用流問題:整性定理(IntegralityTheorem)整性定理.考慮無容量限制的網(wǎng)絡(luò)流問題.i)如果供給量bi是整數(shù),則每個(gè)基本可行解的分量是整數(shù).ii)如果費(fèi)用系數(shù)
cij
是整數(shù),則每個(gè)對(duì)偶基本解的分量是整數(shù).整數(shù)線性規(guī)劃通常不易求解;但是具有整性數(shù)據(jù)的最小費(fèi)用流問題可用網(wǎng)絡(luò)單純形法求解!整性定理(IntegralityTheorem)整性定理.網(wǎng)絡(luò)流:應(yīng)用網(wǎng)絡(luò)流:應(yīng)用運(yùn)輸問題(TransportationProblem)每個(gè)頂點(diǎn)是兩種類型之一:
發(fā)(源/供給)點(diǎn)收(目的/需求)點(diǎn)每條弧滿足:
起點(diǎn)在發(fā)點(diǎn)終點(diǎn)在收點(diǎn)二部/分圖(bipartite)供給節(jié)點(diǎn)需求節(jié)點(diǎn)運(yùn)輸問題(TransportationProblem)每個(gè)運(yùn)輸問題的表上作業(yè)法數(shù)據(jù)表運(yùn)輸表7個(gè)頂點(diǎn)8條??!有6個(gè)基變量,2個(gè)非基變量對(duì)偶變量
需求量供給量102315756*1184318*9*12*36運(yùn)輸問題的表上作業(yè)法數(shù)據(jù)表運(yùn)輸表7個(gè)頂點(diǎn)8條??!有6指派問題(AssignmentProblem)
給定m個(gè)人和m項(xiàng)任務(wù),第i個(gè)人完成任務(wù)j的費(fèi)用是cij
指派每個(gè)人去做且只做一項(xiàng)任務(wù)每項(xiàng)任務(wù)只由一個(gè)人去完成
忽略整數(shù)要求,由整性定理,利用網(wǎng)絡(luò)單純形法可得到指派問題的解!問題是嚴(yán)重退化的,有2m個(gè)約束,但基本解只有m個(gè)非零元素!相對(duì)于二次指派問題,稱這里的問題為線性指派問題!指派問題(AssignmentProblem)給定m最短路問題(ShortestPathsProblem)給定:
網(wǎng)絡(luò):
費(fèi)用=旅行時(shí)間:根節(jié)點(diǎn)(homeorroot):?jiǎn)栴}:找從N中每一個(gè)節(jié)點(diǎn)出發(fā)到根節(jié)點(diǎn)的最短路(有向的)根節(jié)點(diǎn)5:
1→3→5:5
2→5:53→5:14→3→5:3
1
4
2
3
5
7
4
5
1
2
5
1
4
最短路問題(ShortestPathsProblem)給網(wǎng)絡(luò)流表述
令vi=從節(jié)點(diǎn)i
到根節(jié)點(diǎn)r
的最短時(shí)間
在網(wǎng)絡(luò)文獻(xiàn)中稱為標(biāo)號(hào)(label);
在動(dòng)態(tài)規(guī)劃的文獻(xiàn)中稱為值(value).以下算法中使用的記號(hào):
令
求解最小費(fèi)用網(wǎng)絡(luò)流問題從i
到r
的最短路:由最優(yōu)樹弧得到最短路的長度(時(shí)間)=網(wǎng)絡(luò)流表述令vi=從節(jié)點(diǎn)i到根節(jié)點(diǎn)r的最短時(shí)間標(biāo)號(hào)校正算法(LabelCorrectingAlgorithm)動(dòng)態(tài)規(guī)劃(DynamicProgramming)Bellman方程組、動(dòng)態(tài)規(guī)劃原理不必是一個(gè)樹!
逐次逼近法(MethodofsuccessiveApproximation)-初始化:-迭代:-終止:當(dāng)某次迭代沒有一個(gè)vi改變時(shí),終止算法.標(biāo)號(hào)校正算法(LabelCorrectingAlgori標(biāo)號(hào)校正算法的復(fù)雜度
vi(k)=從節(jié)點(diǎn)i
到根節(jié)點(diǎn)
r
且有k
條弧或者更少的最短路的長度
最多要求m-1次迭代每次迭代作n
次加/比較運(yùn)算總共需要mn次運(yùn)算標(biāo)號(hào)校正算法的復(fù)雜度vi(k)=從節(jié)點(diǎn)i到根節(jié)點(diǎn)r標(biāo)號(hào)設(shè)置算法(LabelSettingAlgorithm)Dijkstra算法,1959年記號(hào):
F=已完成的節(jié)點(diǎn)集(標(biāo)號(hào)被設(shè)定)
=在i
之后要訪問的節(jié)點(diǎn)(終點(diǎn))Dijkstra算法:
初始化:
迭代:-當(dāng)還有未完成的節(jié)點(diǎn)時(shí),選擇vi
最小的節(jié)點(diǎn),記為j.
將j
添加到已完成節(jié)點(diǎn)集-對(duì)每個(gè)未完成的節(jié)點(diǎn)i
,且有弧(i,j)將i
和j
連接起來:標(biāo)號(hào)設(shè)置算法(LabelSettingAlgorithmDijkstra最短路算法的流程根節(jié)點(diǎn)5:
1→3→5:5
2→5:53→5:14→3→5:3Dijkstra最短路算法的流程根節(jié)點(diǎn)5:Dijkstra算法的復(fù)雜度
每次迭代完成一個(gè)節(jié)點(diǎn):m
次迭代
每次迭代的計(jì)算量:-選擇一個(gè)未完成的節(jié)點(diǎn):*普通的需要m
次比較*使用合適的數(shù)據(jù)結(jié)構(gòu),需要logm次比較-更新鄰接弧總共:mlogm+nDijkstra算法的復(fù)雜度每次迭代完成一個(gè)節(jié)點(diǎn):m次迭最大流問題(MaximumFlowProblem)給定:?jiǎn)栴}:求從s
到t
的最大流量(將盡可能多的流從s
推向t)
網(wǎng)絡(luò):,A
是點(diǎn)弧關(guān)聯(lián)矩陣
弧上流量的上界:發(fā)點(diǎn),收點(diǎn)Ford-Fulkerson算法最大流-最小割定理最大流問題(MaximumFlowProblem)給定:網(wǎng)絡(luò)流表述
令
添加人工弧(t,s):網(wǎng)絡(luò)流表述令割及割的容量
s-t
割(cut):包含發(fā)點(diǎn)s
但不包含收點(diǎn)t
的節(jié)點(diǎn)集合C
割的容量(capacity):流平衡方程:割及割的容量s-t割(cut):包含發(fā)點(diǎn)s但不包含收最大流-最小割定理(Max-FlowMin-CutTheorem)定理.在任一網(wǎng)絡(luò)中,最大流的流量等于最小割的容量.
由Ford與Fulkerson于1956年提出來的,是圖論和網(wǎng)絡(luò)流中的最重要結(jié)論之一!設(shè)是最大流問題的解xts
*設(shè)是對(duì)偶問題的解證明最大流-最小割定理(Max-FlowMin-CutThe線性整數(shù)規(guī)劃線性整數(shù)規(guī)劃
整數(shù)線性規(guī)劃
-調(diào)度問題-旅行商問題-實(shí)用的建模技術(shù)分支定界法
整數(shù)線性規(guī)劃調(diào)度問題(SchedulingProblems)
設(shè)備調(diào)度(equipmentscheduling)
人員調(diào)度(crewscheduling)Airlinescheduling:
Route-identificationRouteOptimization(√)調(diào)度問題(SchedulingProblems)設(shè)備調(diào)度設(shè)備調(diào)度問題
可能的航線(route)集{1,2,……,n}
,對(duì)應(yīng)的費(fèi)用cjm
個(gè)航段(leg)集{1,2,……,m}
航線和航段的關(guān)系:?jiǎn)栴}:選取航線使得每個(gè)航段恰被覆蓋一次,且總費(fèi)用最小把航段合理的安排到不同的航線上!設(shè)備調(diào)度問題可能的航線(route)集{1,2,……機(jī)組人員調(diào)度問題
可能的航線(route)集{1,2,……,n}
,對(duì)應(yīng)的費(fèi)用cjm
組人員(flightcrews){1,2,……,m}
-可以理解為每組為一個(gè)航段服務(wù)航線和機(jī)組人員的關(guān)系:?jiǎn)栴}:選取航線使每組人員至少為一個(gè)航線服務(wù),且總費(fèi)用最小把機(jī)組人員合理地安排到航線上!機(jī)組人員調(diào)度問題可能的航線(route)集{1,2,
旅行商問題(TravelingSalesmanProblem,TSP)旅行商從城市0出發(fā),周游城市1,2,……,n-1;每個(gè)城市只經(jīng)過一次,最后回到城市0;城市兩兩之間的距離為cij問題:安排周游使總路程最短.周游=所有城市的排列可能的周游數(shù)目:(n-1)!旅行商問題(TravelingSalesmanProb
頂點(diǎn)約束原有問題的松弛該問題的解可能會(huì)含幾個(gè)有向子圈,也稱子周游.指派約束!想辦法排除子圈!頂點(diǎn)約束原有問題的松弛該問題的解可能會(huì)含幾個(gè)有向子圈,也稱
子周游表述(SubtourFormulation)添加一族子周游(消去)約束一開始不必把所有的子周游消去約束都放進(jìn)去;可以邊算邊放!有指數(shù)多個(gè)約束!NN子周游表述(SubtourFormulation)添加一0,ti∈{1,2,…,n-1},i≥1MTZ(Miller-Tucker-Zemlin)表述引入新變量ti
-表示進(jìn)入城市i
之前經(jīng)過的城市數(shù)目弧約束0規(guī)模小!可處理有偏好的周游!0,ti∈{1,2,…,n-1},i≥1MTZ
實(shí)用建模技術(shù)或約束:引入0-1變量y其中M是充分大的正數(shù)帶固定成本的目標(biāo)函數(shù):進(jìn)一步假設(shè)+實(shí)用建模技術(shù)或約束:引入0-1變量y其中M是充分大的非線性目標(biāo)函數(shù)-二次多項(xiàng)式
其中yij
滿足
其中zij
滿足非線性目標(biāo)函數(shù)-二次多項(xiàng)式其中yij滿足其中zij假設(shè)分成3段,即k=3非線性目標(biāo)函數(shù)-連續(xù)的逐段線性函數(shù)假設(shè)分成3段,即k=3非線性目標(biāo)函數(shù)-連續(xù)的逐段線性函數(shù)非線性目標(biāo)函數(shù)-連續(xù)的非線性函數(shù)連續(xù)非線性函數(shù)的逐段線性函數(shù)近似!非線性目標(biāo)函數(shù)-連續(xù)的非線性函數(shù)連續(xù)非線性函數(shù)的逐段線性函數(shù)整數(shù)線性規(guī)劃的線性規(guī)劃松弛(LP-relaxation)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 廢紙?jiān)旒垙U水課程設(shè)計(jì)
- 餐飲門面長期租賃合同模板
- 店鋪直播投放策略研究報(bào)告
- 店名的諧音的研究報(bào)告
- 底板沖裁模課程設(shè)計(jì)
- 底下建筑結(jié)構(gòu)課程設(shè)計(jì)
- 貨柜安裝服務(wù)合同模板
- 公司電工聘用合同模板
- 床架清倉處理方案
- 床單場(chǎng)景課程設(shè)計(jì)
- 中學(xué)生追星好不好辯論賽正方(5篇)
- 吉林省吉林市2023-2024學(xué)年高三上學(xué)期第一次模擬考試 物答案
- 專題2檢驗(yàn)食品中的鐵元素(教學(xué)設(shè)計(jì))高一化學(xué)
- 西藏自治區(qū)山南市貢嘎縣森布日小學(xué)2023-2024學(xué)年五年級(jí)上學(xué)期期中數(shù)學(xué)試卷
- 5.1國內(nèi)外頂管技術(shù)的發(fā)展
- 2023-2024學(xué)年高中政治統(tǒng)編版必修二3-2 推動(dòng)高質(zhì)量發(fā)展 第2課時(shí) 教案
- 兒童生理藥代動(dòng)力學(xué)模型及其在兒科藥物研究中的應(yīng)用
- 自考《獸醫(yī)法規(guī)14239》考試復(fù)習(xí)題庫(必備版)
- 混凝土隨機(jī)損傷力學(xué)
- 《5、4、3、2加幾》(說課課件)-一年上冊(cè)數(shù)學(xué)人教版
- 子女不承擔(dān)父母?jìng)鶆?wù)協(xié)議書
評(píng)論
0/150
提交評(píng)論