【正文】 w2=2 w4=1 w1=0 w6=3 w7=3 w5=6 w3=8 w8=10 第六章 動態(tài)規(guī)劃 最短路徑問題 資源分配問題 背包問題 機(jī)器負(fù)荷分配問題 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 一、最短路徑問題 求從 A到 E的最短路徑 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 。 Min z=6 1+3 13+8 2+4 13+2 12+5 19=142 11 5 5 4 8 2 第五章 網(wǎng)絡(luò)優(yōu)化 網(wǎng)絡(luò)的基本概念 網(wǎng)絡(luò)最小費用流問題 網(wǎng)絡(luò)最大流問題 最短路徑問題 網(wǎng)絡(luò)的基本概念 ■ 節(jié)點與（有向）邊 每一條邊和兩個節(jié)點關(guān)聯(lián)，一條邊可以用兩個節(jié)點的標(biāo)號表示（ i， j） j i ■ 路徑（ Path） 前后相繼并且方向相同的邊序列 P={(1,2),(2,3),(3,4)} 4 2 3 1 4 2 3 1 ■ 網(wǎng)絡(luò)由節(jié)點和邊組成 ■ 回路（ Circuit） 起點和終點重合的路徑稱為 回路 μ={(1,2),(2,4),(4,1)} 回路中各條邊方向相同 4 2 3 1 ■ 鏈（ Chain） 前后相繼并且方向不一定相同的邊序列稱為 鏈 C={(1,2),(3,2),(3,4)} 4 2 3 1 ■ 連通圖 任意兩個節(jié)點之間至少有一條鏈的圖稱為 連通圖 2 4 3 5 1 ■ 圈 (Cycle) 起點和終點重合的鏈稱為 圈 ρ ={(1,2),(2,4),(3,4),(1,3)} 圈中各條邊方向不一定相同 4 2 3 1 ■ 樹 (Tree) 無圈的連通圖稱為 樹 樹中只與一條邊關(guān)聯(lián)的節(jié)點稱為 懸掛節(jié)點 樹的性質(zhì) ■ 任何樹至少有一個懸掛節(jié)點 2 4 3 5 1 2 4 3 5 1 2 4 3 5 1 ■ 如果樹的節(jié)點個數(shù)為 m， 則邊的個數(shù)為 m1 ■ 樹中任意兩個節(jié)點之間只有唯一的一條鏈 ■ 在樹的任意兩個不相鄰的節(jié)點之間增加一條邊，則形成唯一的圈 網(wǎng)絡(luò)的生成樹 ■ 由網(wǎng)絡(luò)的所有節(jié)點（ m個）和網(wǎng)絡(luò)的 m1條邊組成的樹稱為網(wǎng)絡(luò)的 生成樹 ，網(wǎng)絡(luò)中不屬于生成樹的邊稱為生成樹的 弦 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 4 2 3 1 網(wǎng)絡(luò)的生成樹的變換 4 2 3 1 ■ 網(wǎng)絡(luò)的一個生成樹，增加一條弦，形成唯一的圈，去掉生成樹的一條邊，得到一個新的網(wǎng)絡(luò)的生成樹 4 2 3 1 4 2 3 1 4 2 3 1 生成樹 2 生成樹 3 生成樹 1 // // 網(wǎng)絡(luò)的生成樹和線性規(guī)劃的關(guān)系 ■ 網(wǎng)絡(luò)的一個生成樹對應(yīng)于線性規(guī)劃的一個基 ■ 生成樹上的邊對應(yīng)于線性規(guī)劃的基變量 ■ 生成樹的弦對應(yīng)于線性規(guī)劃的非基變量 ■ 生成樹的變換對應(yīng)于線性規(guī)劃單純形法的進(jìn)基和離基變換 網(wǎng)絡(luò)最小費用流問題 b2=2 b4=3 b3=5 b5=6 b6=5 b1=5 c24=5 c46=1 c13=3 c35=2 c56=4 c34=4 c12=6 2 3 4 5 6 1 需求節(jié)點 供應(yīng)節(jié)點 cij 單位流量的費用 初始基礎(chǔ)可行解 — 生成樹 b6=5 b2=2 b4=3 b3=5 b5=6 b1=5 x13=3 x46=3 x35=8 x56=2 x12=2 2 3 4 5 6 1 確定非基變量 x24和 x34 b2=2 b6=5 b3=5 b5=6 b1=5 c24=5 c46=1 c13=3 c35=2 c56=4 c34=4 c12=6 2 3 4 5 6 1 b4=3 求 x24的檢驗數(shù) z24c24 閉回路法 z24 c24 =(c46+c56+c35+c13c12)c24=(1+4+2+36)5=3 b2=2 b4=3 b3=5 b5=6 b6=5 b1=5 c24=5 c46=1 c13=3 c35=2 c56=4 c12=6 2 3 4 5 6 1 求 x34的檢驗數(shù) z34 c34 閉回路法 z34 c34 =(c46+c56+c35)c34=(1+4+2)4=+1， x34進(jìn)基 b2=2 b4=3 b3=5 b5=6 b6=5 b1=5 c46=1 c13=3 c35=2 c56=4 c34=4 c12=6 2 3 4 5 6 1 變量 x34進(jìn)基，確定離基變量 min{x56,x35}=min{2,8}=2, x56離基，調(diào)整流量，進(jìn)行基變換 b2=2 b4=3 b3=5 b5=6 b6=5 b1=5 x46=3 x13=3 x35=8 x56=2 x34=0 x12=2 2 3 4 5 6 1 確定非基變量 x24和 x56 b2=2 b4=3 b3=5 b5=6 b6=5 b1=5 x46=5 x13=3 x35=6 x34=2 x12=2 2 3 4 5 6 1 計算 x24和 x56的檢驗數(shù) z24 c24 、 z56c56 z24 c24 =(c34+c13c12)c24=(4+36)5= 4 z56 c56 =(c46+c34c35)c56=(1+42)4= 1， 獲得最優(yōu)解 b2=2 b4=3 b3=5 b5=6 b6=5 b1=5 c24=5 c46=1 c13=3 c35=2 c56=4 c34=4 c12=6 2 3 4 5 6 1 最優(yōu)解 最優(yōu)解的目標(biāo)函數(shù)值為： min z=6?2+3?3+4?2+2?6+1?5=46 b2=2 b4=3 b3=5 b5=6 b6=5 b1=5 x46=5 x13=3 x35=6 x34=2 x12=2 2 3 4 5 6 1 網(wǎng)絡(luò)最大流問題 2 3 5 4 6 7 1 f f u25=6 u42=2 u45=4 u23=3 u13=7 u34=4 u46=3 u36=1 u65=7 u57=9 u67=8 u12=8 ■ 邊的容量和流量 容量 uij， 流量 xij ■ 可行流 滿足以下條件的流稱為可行流： 每一個節(jié)點流量平衡 0≤xij ≤uij 邊的容量和流量、可行流 2 1 xij=5 uij=5 2 1 xij=3 uij=5 飽和邊、不飽和邊、流量的間隙 （ 1， 2）是飽和的 如果 xijuij， 邊從 i到 j的方向是不飽和的； （ 1， 2）是不飽和的 間隙為 ?12=u12x12=53=2 如果 xij=uij， 邊從 i到 j的方向是飽和的； 2 1 xij=0 uij=5 2 1 xij=5 uij=5 如果 xij=0， 邊從 j到 i的方向是飽和的； （ 2， 1）是飽和的 如果 xij0， 邊從 j到 i的方向是不飽和的； （ 2， 1）是不飽和的 間隙為 ?12=x12=5 給出一個初始的可行流 xij=0 2 3 5 4 6 7 1 f=0 f=0 u=6 u=2 u=4 u=3 u=7 u=4 u=3 u=1 u=7 u=9 u=8 u=8 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 找到所有的不飽和邊，以及各邊可以調(diào)整流量的方向 2 3 5 4 6 7 1 f=0 f=0 u=6 u=2 u=4 u=3 u=7 u=4 u=3 u=1 u=7 u=9 u=8 u=8 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 找到一條從 1到 7的不飽和鏈 鏈的間隙為： ? = min{8,3,1,8}=1 調(diào)整鏈的流量： xij’=xij+ ? 2 3 5 4 6 7 1 f=0 f=0 u=6 u=2 u=4 u=3 u=7 u=4 u=3 u=1 u=7 u=9 u=8 u=8 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 ?=3 ?=1 ?=8 ?=8 x=0 調(diào)整流量， f=1。 1 1 0 3 2 0 2 72x 5 0 1/ 2 0 1/ 2 0 1 1/ 2 7x 2 0 1/ 2 1 1/ 2 1 0 1/ 2 180 4 2 2 1 86 0 1 1 0 2 1 1 x1 0 1 1 1 0 14 11 0 1 0 x2 0 得到最優(yōu)解，最優(yōu)解為： （ x1， x2， x3， x4， x5， x6） =（ 14， 11， 0， 0， 0， 0） min z’=86， max z=86 m ax z= 2x 1 +3x 2 +x 3st x 1 +3x 2 +x 3 ? 152x 1 +3x 2 x 3 ? 18x 1 x 2 +x 3 ? 3x 1 , x 2 , x 3 ? 0m in z’= 2x 1 3x 2 x 3st x 1 +3x 2 +x 3 +x 4 =152x 1 +3x 2 x 3 +x 5 =18x 1 x 2 +x 3 +x 6 =3x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ? 0 z’ x 1 x 2 x 3 x 4 x 5 x 6 RH Sz’ 1 2 3 1 0 0 0 0x 4 0 1 3 1 1 0 0 15 15/3x 5 0 2 3 1 0 1 0 18 18/3x 6 0 1 1 1 0 0 1 3 m in z’= 2x 1 3x 2 x 3st x 1 +3x 2 +x 3 +x 4 =152x 1 +3x 2 x 3 +x 5 =18x 1 x 2 +x 3 +x 6 =3x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ? 0 z’ x 1 x 2 x 3 x 4 x 5 x 6 RH Sz’ 1 2 3 1 0 0 0 0x 4 0 1 [3] 1 1 0 0 15 15/3x 5 0 2 3 1 0 1 0 18 18/3x 6 0 1 1 1 0 0 1 3 z’ x 1 x 2 x 3 x 4 x 5 x 6 RH Sz’ 1 1 0 0 1 0 0 15x 2 0 1/3 1 1/3 1/3 0 0 5 5/1/3x 5 0 [1] 0 2 1 1 0 3 3/1x 6 0 4/3 0 4/3 1/3 0 1 8 8/4/3z’ x 1 x 2 x 3 x 4 x 5 x 6 RH Sz’ 1 0 0 2 0 1 0 18x 2 0 0 1 1 2/3 1/3 0 4 4/1x 1 0 1 0 2 1 1 0 3 x 6 0 0 0 [ 4] 5/3 4/3 1 4 4/4 z’ x 1 x 2 x 3 x 4 x 5 x 6 RH Sz’ 1 0 0 2 0 1 0 18x 2 0 0 1 1 2/3 1/3 0 4 4/1x 1 0 1 0 2 1 1 0 3 x 6 0 0 0 [ 4] 5/3 4/3 1 4 4