【導讀】基礎解、基礎可行解。線性規(guī)劃的矩陣表示。線性規(guī)劃模型的結構。變量符號：：≥0,unr,≤0. x1≥0,x2≥0可行域。凸集凸集不是凸集?；兞縳1、x2、x4，非基變量x3、x5、x6. 目標函數(shù)值為：z=18. 進基變量、離基變量、基變換。幾何概念代數(shù)概念。約束直線滿足一個等式約束的解。約束半平面的交集：。目標函數(shù)等值線：。目標函數(shù)值等于一個常。x5離基，x1進基，

　　

【正文】 {1， 4， 7， 5， 8}，長度為 10。 w2=2 w4=1 w1=0 w6=3 w7=3 w5=6 w3=8 w8=10 網絡最大流問題 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 找到所有的不飽和邊，以及各邊可以調整流量的方向 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 調整鏈的流量： 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 調整流量， f=1。 繼續(xù)求出網絡的不飽和邊 2 3 5 4 6 7 1 f=1 f=1 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=1 x=1 x=1 x=1 求出一條從 1到 7的不飽和鏈 2 3 5 4 6 7 1 f=1 f=1 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=1 x=1 x=1 x=1 ?=1 ?=6 ?=9 ?=7 ?=min {7,1,6,9}=1, 調整流量 xij’=xij+1, f’=f+1=2 調整流量，繼續(xù)求出網絡的不飽和邊 2 3 5 4 6 7 1 f=2 f=2 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=1 x=0 x=0 x=1 x=0 x=0 x=0 x=1 x=1 x=1 x=1 x=0 求出一條從 1到 7的不飽和鏈 2 3 5 4 6 7 1 f=2 f=2 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=1 x=0 x=0 x=1 x=0 x=0 x=0 x=1 x=1 x=1 x=1 x=0 ? ?=5 ?=8 ?=7 ?=min {7,5,8}=5, 調整流量 xij’=xij+5, f’=f+5=2+5=7 調整流量，繼續(xù)求出網絡的不飽和邊 2 3 5 4 6 7 1 f=7 f=7 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=6 x=0 x=0 x=1 x=0 x=0 x=0 x=6 x=1 x=1 x=6 x=0 2 3 5 4 6 7 1 f=7 f=7 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=6 x=0 x=0 x=1 x=0 x=0 x=0 x=6 x=1 x=1 x=6 x=0 求出一條從 1到 7的不飽和鏈 ?=min {6,7,4,3}=3, 調整流量 xij’=xij+3, f’=f+3=7+3=10 ?=4 ?=4 ?=3 ?=6 調整流量，繼續(xù)求出網絡的不飽和邊 2 3 5 4 6 7 1 f=10 f=10 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=6 x=0 x=3 x=4 x=3 x=0 x=0 x=9 x=1 x=1 x=6 x=0 求出一條從 1到 7的不飽和鏈 2 3 5 4 6 7 1 f=10 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=6 x=0 x=3 x=4 x=3 x=0 x=0 x=9 x=1 x=1 x=6 x=0 f=10 ?=1 ?=3 ?=7 ?=3 ?=min {3,1,3,7}=1, 調整流量 xij’=xij+1, f’=f+1=10+1=11 調整流量，繼續(xù)求出網絡的不飽和邊 2 3 5 4 6 7 1 f=11 f=11 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=6 x=0 x=4 x=5 x=3 x=1 x=0 x=9 x=2 x=1 x=6 x=0 已找不到一條從 1到 7的不飽和鏈，從 1開始可以到達的節(jié)點為 1， 2， 3 已求得最大流 2 3 5 4 6 7 1 f=11 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=6 x=0 x=4 x=5 x=3 x=1 x=0 x=9 x=2 x=1 x=6 x=0 f=11 最大流 f=11， 最小割集為（ 2,5）（ 3,4）（ 3,5） u25+u34+u35=6+4+1=11 第六章 動態(tài)規(guī)劃 最短路徑問題 資源分配問題 背包問題 機器負荷分配問題 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 D2 E C2 f5(E)=0 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 f4(D1)=5 f5(E)=0 505)E(f)ED(d)D(f 5114 ??????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 f4(D2)=2 f5(E)=0 f4(D1)=5 202)E(f)ED(d)D(f 5224 ??????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 f4(D2)=2 f5(E)=0 f3(C1)=8 f4(D1)=5 112421141113DC8118m i n2953m i n)D(f)D,C()D(f)D,C(m i n)C(f???????????????????????????最優(yōu)決策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 f4(D2)=2 f5(E)=0 f3(C2)=7 f4(D1)=5 f3(C1)=8 222422141223DC7711m i n2556m i n)D(f)D,C()D(f)D,C(m i n)C(f???????????????????????????最優(yōu)決策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 f4(D2)=2 f5(E)=0 f3(C3)=12 f4(D1)=5 f3(C1)=8 f3(C2)=7 232423141333DC121213m i n21058m i n)D(f)D,C()D(f)D,C(m i n)C(f???????????????????????????最優(yōu)決策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 f4(D2)=2 f5(E)=0 f3(C3)=12 f4(D1)=5 f2(B1)=20 f3(C2)=7 f3(C1)=8 1133312321131112CB20222120m i n1210714812m i n)C(f)C,B()C(f)C,B()C(f)C,B(m i n)B(f?????????????????????????????????????????最優(yōu)決策2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5