1.表1中的數字表示5個村莊之間線路的長度（裡），現要求沿線路架設有線廣播電視線網，不僅使得各村都能收看廣播電視節目，而且使廣播線總長度最短。請先建立圖論模型並採取適當方法求解。
表1解：設vj(j=1,2,3,4,5)表示村莊j，邊（vi,vj）表示村莊i和村莊j之間廣播電視可以鋪線，其對應的權數cij表示村莊i和村莊j之間線路的長度。依據題目資料，可作出如圖1.
1：方法一：破圈法
從圖1.1中任取乙個圈，比如（v1,v4,v5,v1），去掉權為4的最大邊[v4,v5]（或[v1,v4]）;再取圈（v1,v2,v5,v1），去掉邊[v2,v5]；取圈（v1,v2,v3,v1），去掉[v1,v3];取圈（v1,v2,v3,v4,v1），去掉[v3,v4]。這時得到乙個不含圈的聯通圖，如圖1.
2所示，即為最小生成樹。總權重為w(t*)=3+4
+2+2=11。
方法二：避圈法
從圖1.1中選出權數最小為1的邊[v1,v2]（或[v2,v3]）;再在剩餘的圖中選取最小邊[v2,v3]（或[v1,v2]），它與[v1,v2]不構成圈；再依次選出不構成圈的最小邊[v1,v5]、 [v1,v4]（或[v4,v5]） 。這時得到乙個不含圈的聯通圖，如圖1.
2所示，即為最小生成樹。總權重為w(t*)=3+4+2
+2=11。
（複習參考題）2.用dijkstra標號法求圖1從v1到v6的最短路。如果有不可達點，請指出來。
解：給起點v1標號（0,v1）；
1. i= j= 弧集合
s12=l1+c12=0+1=1 s13=l1+c13=0+4=4
∵min=min=1= s12=l2 ∴給v2標號（1,v1）
2. i= j= 弧集合
s23=l2+c23=1+2=3 s24=l2+c24=1+3=4
∵min=min=3= s23=l3 ∴給v3標號（3, v2）
3. i= j= 弧集合
s36=l3+c36=3+2=5 ∵min=min=4= s24=l4 ∴給v4標號（4,v2）
4. i= j= 弧集合
s46=l4+c46=4+2=6 ∵min=min=5= s36=l6 ∴給v6標號（5,v3）
5. i= j= 計算終止。
由終點v6標號反向追蹤，可得到v1到v6的最短路：v1→v2→v3→v6,長度為l6=5。圖中
v5未標號，因為從v1到v5沒有可達路。
（複習參考題）3.試用ford－fulkerson標號法求圖2所示的網路最大流。圖中數字為每條弧的容量cij，括號中的數字為可行流fij。
圖2解：用ford－fulkerson標號法求解
1.給vs標號（vs,+）
檢查vs: v1不標（∵正向弧（vs,v1）的可行流fs1=容量cs1=9），v2標（vs,+）(∵正向弧（vs,v2）的可行流fs2=7《容量cs2=13)。檢查完畢,vs標號（vs,⊕）；
檢查v2: v1標（v2,-）（∵逆向弧（v1,v2）的可行流f12=4>0），v3不標，v5不標。檢查完畢，v2標（vs,⊕）；
檢查v1:v3標（v1,+），v4不標。檢查完畢，v1標（v2,）；
檢查v3: v4標（v3,+），v5標（v3,+）。檢查完畢，v3標（v1,⊕）；
檢查v4:vt標（v4,+）。檢查完畢，v4標（v3,⊕）；
因為終點vt已經標號，所以得到一條流量增廣路p(1):vs→v2←v1→v3→v4→vt。
流量調整量ε(1)=min=4
調整後增廣路p(1)上各弧[vs,v2]、[v2,v1]、[v1,v3]、[v3,v4]、[v4,vt]可行流為：7+4=11、4-4=0、0+4=4、0+4=4、5＋4=9。下面進行第二次迭代。
2.給vs標號（vs,+）
檢查vs: v1不標，v2標（vs,+）。檢查完畢，vs標號（vs,⊕）；
檢查v2: v1不標（∵逆向弧（v1,v2）的可行流為f12=0），v3不標，v5不標。檢查完畢，v2標（vs,⊕）；
標號過程沒有進行到終點vt，不能再進行下去。所以第一次迭代後已經得到網路最大流。最小割集｛[vs,v1]、[v2,v3]、[v2,v5]｝(如圖所示)
結論：該網路最大流max f=11+9=9+6+5=7+4+9=20。
4.試用對偶法求圖3所示的最小費用最大流。圖中數字（cij,bij, xij）分別代表弧（i,j）容量、單位流量費用（元）和當前可行流。
圖3解：用對偶法求解（費用路a、c、e中標記「∥」的為最短路）。
因為圖e中找不到從vs到vt的費用增廣路，所以f(2)為
最小費用最大流。 max f=13，最小總費用=4×7＋1×7＋1
×6＋3×6＋2×6=71。圖（d）中最小割集｛[v1,vt],[v3,vt]｝,
用ford－fulkerson法標號如（d）圖所示。
運籌學習題
二 某工廠接到a b兩種產品的訂單，a的需求量為1500，b的需求量為1800。工廠的1 2 3三條生產線均可加工這兩個產品，但加工成本和加工能力各不相同，具體資料見下表，列出使總加 一 單項選擇題 工成本最低的 0 1規劃 生產安排模型。提示 設第i i 1,2 種產品在第j j 1,2,3 條生...
運籌學習題四答案
4.1 工廠生產甲 乙兩種產品，由 二組人員來生產。組人員熟練工人比較多，工作效率高，成本也高 組人員新手較多工作效率比較低，成本也較低。例如，a組只生產甲產品時每小時生產10件，成本是50元有關資料如表4.21所示。表4.21 二組人員每天正常工作時間都是8小時，每週5天。一周內每組最多可以加班1...
運籌學 5複習 1
第5章整數規劃 有一類線性規劃問題的變數只能取整數，比如人或機器裝置不可分割，因此必需取整數。這時線性規劃問題稱為整數規劃。如果有的變數要求必需是整數，有的變數不要求必需是整數，則線性規劃問題稱為混合整數規劃問題。5.2 分枝定界法 求整數規劃較好的方法是分支定界法。下面介紹常用的分枝定界法。1.分...