【正文】 (,})3{,2(m i n [})3,2{,4( 3412412 ??????? dfdff決策函數(shù)： )33(3})3,2{,4(2 ?p43]3225,934m i n []})3{,4(,})4{,3(m i n [})4,3{,2( 4213212 ??????? dfdff當 K=3時，即從城市 1開始，中間經(jīng)過 3個城市到達城市 1的最短距離為： j:1 2 3 4 i： 1 0 10 20 30 2 12 0 18 30 3 23 9 0 5 4 34 32 4 0 55]3433,2344,1243m i n []})3,2{,4(,})4,2{,3(,})4,3{,2(m i n [}4,3,2{,1( 413122123????????? dfdfdff決策函數(shù)： )55(2})4,3,2{,1(3 ?p故，推銷員的最短旅行路線： 1—4—3—2—1， 最短總距離為 55。 ? ?? ??m1in1jijij xcM in Z二、圖上作業(yè)法 ? 在交通圖上，用□表示生產(chǎn)地 /供應地，供應量用＋表示，用○表示銷售地 /需求地，需求量用－表示。 確定初始 方案 （ 初始基本可行解 ） 判定是否最優(yōu) ？ 改進調整 （ 換基迭代 ） 結束 否 是 圖 71 運輸問題求解思路圖 例某公司有三個工廠 B B B3，生產(chǎn)中需要同一種原料，另有三個倉庫 A A A3可供應這種原料，由于供需雙方兩兩間的相對位置不同因而運價不同，有關數(shù)據(jù)如下表： B1 B2 B3 B4 產(chǎn)量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 6 5 9 銷 量 3 6 5 6 20 問應如何安排運輸才能使總運費為最??？ ? 應用表上作業(yè)法通?？煞譃樗膫€步驟： 運用最小元素法確定初始方案 檢驗（位勢法），若所有空格檢驗數(shù)均大于等于 0，則初始方案為最優(yōu)方案 調整 再檢驗 例 某車間有四項產(chǎn)品加工任務 B B B B4，該車間有三種設備 A A A3可用于加工這些產(chǎn)品，由于每種設備的性能不同因而加工每一種產(chǎn)品的效率不同，有關數(shù)據(jù)如下表： B1 B2 B3 B4 可利用工時 A1 6 7 5 3 14 A2 8 4 2 7 27 A3 5 9 10 6 19 需要工時 22 13 12 13 運價為單位時間加工的產(chǎn)品數(shù)量（ kg/h） ,問應如何安排加工才能使總效率最高 (加工的產(chǎn)品最多 )？ 運輸問題實際上也可以看作是一個 m n分派問題。 ? 由于各港口每天到達的船只數(shù)與所需要的船只數(shù)不等，必須對各港口的供需進行平衡。因此可建立如下的運輸問題，運價是 各港口間的航程天數(shù) ，其產(chǎn)銷平衡表為： ? A B E 每天多余船只 C 2 1 3 5 1 2 D 14 13 17 2 2 F 7 8 1 3 1 每天缺少船只 1 1 3 ? 因 λ13=12，故需將方案調整為： ? A B E 每天多余船只 ? C 2 1 3 5 1 2 ? D 14 13 1 17 1 2 ? F 7 8 3 1 1 每天缺少船只 1 1 3 ? 所有檢驗數(shù)已全部非正，故得到最優(yōu)方案。 三、 最大元素法 A2 A3 B2 A1 B3 B4 B1 運輸問題網(wǎng)絡圖 s2=27 s3=19 d1=22 d2=13 d3=12 d4=13 s1=14 供應量 供應地 運價 需求量 需求地 6 7 5 3 8 4 2 7 5