【正文】 8 1A2A1B 2B 3B 4B3A表 32 1341192313142424 ?????????? cccc?1?121 銷地 產(chǎn)地 產(chǎn) 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 10611432834141323213131 ????????????? cccccc?102111? 銷地 產(chǎn)地 產(chǎn) 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 124116111314343333 ????????? cccc?12101?121 銷地 產(chǎn)地 產(chǎn) 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 1 21 1?10 12檢驗(yàn)數(shù)中有負(fù)數(shù)，說(shuō)明原方案不是最優(yōu)解。當(dāng)運(yùn)輸問(wèn)題的產(chǎn)地和銷地很多時(shí)，空格的數(shù)目很大，計(jì)算檢驗(yàn)數(shù)的工作量很大，而用對(duì)偶變量法就簡(jiǎn)便得多。 ji vu ,有基變量所對(duì)應(yīng)的檢驗(yàn)數(shù)為零，可從 m+n1個(gè)等式 0)( ??? jiij vuc （ ） 解出所有的行位勢(shì)、列位勢(shì)。 avi ? )( ji vu ?即 將不會(huì)隨 的取值而改變。 銷地 產(chǎn)地 產(chǎn) 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 iujv104?10392jiij vuc ??行位勢(shì) 列位勢(shì) 設(shè) u1=1 當(dāng)然，也可用采用解方程組的辦法來(lái)求位勢(shì)： 1314212332344112356uvuvuvuvuvuv???????? ???????? ???????兩種方法任選一種 銷地 產(chǎn)地 產(chǎn) 量 4 12 10 4 6 11 16 8 2 10 2 3 9 10 8 14 5 11 8 6 22 銷 量 8 14 12 14 48 1A2A1B 2B 3B 4B3A表 32 iujv104?103921 21 1?10 12)( jiijij vuc ????三。 在進(jìn)基格點(diǎn)所對(duì)應(yīng)的閉回路上，定義頂點(diǎn)的序號(hào)：自進(jìn)基 格點(diǎn)起選定一個(gè)方向（比如順時(shí)針?lè)较颍?，依次為第? 格、第二格、 … 在奇數(shù)格點(diǎn)上減少調(diào)整量 ，在偶數(shù)格點(diǎn)上增加調(diào)整量 。表上作業(yè)法計(jì)算中的兩個(gè)問(wèn)題 ⒈ 無(wú)窮多個(gè)最優(yōu)解 若在最優(yōu)解中，某個(gè)非基變量的檢驗(yàn)數(shù)為零，則該問(wèn)題有 無(wú)窮多個(gè)最優(yōu)解 此時(shí)得到一個(gè)最優(yōu)解： ,1213 ?x ,414 ?x ,821 ?x ,224 ?x,1432 ?x ,834 ?x 其余變量全等于零。 總運(yùn)費(fèi)為（目標(biāo)函數(shù)值） ? ?? ??3141i jijij xcz2 4 468514962441244 ?????????????⒉ 退化情況 與一般 LP問(wèn)題類似，運(yùn)輸問(wèn)題也可能出現(xiàn)退化了的基本可 行解。即發(fā)點(diǎn)的當(dāng)前發(fā)送量已全部用完，而收 點(diǎn)的需求量已全部滿足。為了使調(diào)運(yùn)表上確保有 (m+n1)個(gè)基變量的值，就需要在 所劃掉的行（或列）的任一空格添上調(diào)運(yùn)量 0。 ijx例如：下表給出一個(gè) 3 4運(yùn)輸?shù)倪\(yùn)價(jià)及發(fā)送量與需求量。 銷地 產(chǎn)地 產(chǎn) 量 3 11 4 5 7 7 7 3 8 1 2 10 6 9 銷 量 3 6 5 6 48 1A2A1B 2B 3B 4B3A表 42 6011634此時(shí)得到一個(gè)退化了的初始基本可行解： ,012 ?x,113 ?x ,614 ?x ,423 ?x ,331 ?x ,632 ?x其余變量全等于零。此時(shí)只能取一個(gè)離基，其余的仍作為 基格。試用閉回路法對(duì)其做出 調(diào)整。 3 運(yùn)輸問(wèn)題的進(jìn)一步討論 一、產(chǎn)銷不平衡運(yùn)輸問(wèn)題 對(duì)產(chǎn)銷不平衡問(wèn)題，可轉(zhuǎn)化為平衡問(wèn)題，然后按表上作業(yè) 法求解。 ⒉ 若銷大于產(chǎn)，增加一個(gè)虛擬的產(chǎn)地，其產(chǎn)量設(shè)定為不足 量，相應(yīng)的運(yùn)價(jià)也設(shè)為 0。 由此可以看出閉回路的幾何特點(diǎn)： 1. 閉回路都是一條封閉折線，每個(gè)頂點(diǎn)格子都是轉(zhuǎn)角點(diǎn) 2. 每一行或每一列只有且僅有兩個(gè)頂點(diǎn)格子 3. 每?jī)蓚€(gè)頂點(diǎn)格子的連線都是水平的或垂直的。實(shí)質(zhì)上比較現(xiàn)實(shí)的最高需求 210萬(wàn)噸 ? 產(chǎn)量大于最小需求；小于最大需求。 ? 處理辦法：設(shè)想一個(gè)虛擬煤礦 D，生產(chǎn) 50萬(wàn)噸，但這個(gè)產(chǎn)量只能供應(yīng)可有可無(wú)的最高需求部分，于是各地的需求也應(yīng)分為兩個(gè)部分：基本需求、機(jī)動(dòng)需求 ? 虛擬產(chǎn)量的運(yùn)輸費(fèi)用為零，但它對(duì)于基本需求來(lái)講，運(yùn)費(fèi)為無(wú)窮大。已知各季度生產(chǎn)成本不同，允許存貨，存儲(chǔ)費(fèi) /臺(tái)季，三、四季度可以加班生產(chǎn)，加班生產(chǎn)能力 8臺(tái) /季，加班費(fèi)用 3萬(wàn)元 /臺(tái) 季度 正常生產(chǎn)能力 單位成本（萬(wàn)元） 交貨臺(tái)數(shù) 1 2 3 4 30 32 20 28 11 25 30 15 45 分析： ?可用線性規(guī)劃，但用運(yùn)輸問(wèn)題更簡(jiǎn)單 ?要決策的問(wèn)題是各季度生產(chǎn)量和交貨量設(shè) xij表示第 i季度生產(chǎn)第 j季度交貨的臺(tái)數(shù) ?因加班時(shí)間生產(chǎn)成本不同，故要區(qū)別開(kāi)來(lái)，三四季度可加班，視同增加兩個(gè)季度 ?需求量合計(jì) 115臺(tái)，生產(chǎn)能力合計(jì) 126臺(tái)，供需不平衡，因此，增加一項(xiàng)閑置能力。又知各城市之間的航行天數(shù)，假定船只型號(hào)相同，裝卸貨時(shí)間各一天，問(wèn)該公司至少要配備多少條船才能滿足需要？ 航線 起點(diǎn) 終點(diǎn) 每天航班數(shù) 1 2 3 4 E B A D D C F B 3 2 1 1 城市之間航行天數(shù)表 Cij A B C D E F A B C D E F 0 1 2 14 7 7 1 0 3 13 8 8 2 3 0 15 5 5 14 13 15 0 17 20 7 8 5 17 0 3 7 8 5 20 3 0 問(wèn)題分析 問(wèn)題要求的是在保證需要的前提下，至少需多少船只。 航線 航行天數(shù) 裝卸天數(shù) 合計(jì) 航班數(shù) 載貨船數(shù) 1 2 3 4 17 3 7 13 2 2 2 2 19 5 9 15 3 2 1 1 57 10 9 15 問(wèn)題分析（續(xù) 1） ? 上表顯示：載貨船共需 91條，此船何來(lái)？ A B C D E F 1 2 1 3 調(diào)度中心 港口 到達(dá) 開(kāi)出 余缺 A B C D E F 0 1 2 3 0 1 1 2 0 1 3 0 1 1 2 2 3 1 若無(wú)空駛，則 91條船剛好夠用，但虛線箭頭都是空駛 問(wèn)題分析（續(xù) 2） ?所需 91條貨船要經(jīng)調(diào)度而來(lái)，有的可在一個(gè)港口卸貨后裝運(yùn)（如一條船從 E到 D后再起程赴 B）。（規(guī)模效益） ?由上表可知： C、 D、 F港口有多余船只可供調(diào)出，而 A、 B、 E港口則需要調(diào)入空船。設(shè) xij表示每天從 i港口調(diào)往 j港口的空船數(shù)，則 cijxij就表示 i j航線上周轉(zhuǎn)的船只數(shù)， ∑cijxij表示各條線上周轉(zhuǎn)的船只總數(shù) A B E 每天多余船只 C D F 2 14 7 3 13 8 5 17 3 2 2 1 每天缺少船只 1 1 3 解題結(jié)果 A B E 每天多余船只 C D F 1 1 1 1 1 2 2 1 每天缺少船只 1 1 3 空船總需求量 2+5+13+17+3=40條 空駛船 40條 +載重船 91條 =131條