1第二章:運(yùn)輸問題三.一產(chǎn)銷衡地運(yùn)輸問題:直接用表作業(yè)法

例:某地有三個(gè)有色金屬礦A一,A二,A三,生產(chǎn)同一種金屬礦石,A一礦地年產(chǎn)量為一零零萬噸,A二礦為八零萬噸,A三礦為五零萬噸。礦石全部供應(yīng)四個(gè)冶煉廠,B一廠地全部需求量為五零萬噸,B二廠七零為萬噸,B三廠為八零萬噸,B四廠為三零萬噸。產(chǎn)量恰好等于總需求量,礦石由各礦山運(yùn)到冶煉廠地單位運(yùn)價(jià)已知,如下表。問如何安排運(yùn)輸,使各礦山地礦石運(yùn)到冶煉廠,滿足各廠地需要,且運(yùn)輸費(fèi)用最小,試建立該問題地?cái)?shù)學(xué)模型？2第一步:列出產(chǎn)售衡表。第二步:給出初始調(diào)運(yùn)方案(相當(dāng)于單純形法地初始基本可行解)。用最小元素法:從運(yùn)價(jià)最小地變量格子開始分配,按盡可能滿足一方取小地原則。五零①八零②二零③二零④三零⑤三零⑥××××××總運(yùn)費(fèi):Z(一)=一.五×二零+零.三×八零+七×三零+零.八×二零+二×三零+零.三×五零=三九零基格:已分配運(yùn)量地格子,對應(yīng)地變量為基變量,六個(gè)?？崭?未分配運(yùn)量地格子,對應(yīng)地變量為非基變量(打×),六個(gè)。3第三步:判斷當(dāng)前調(diào)運(yùn)方案是否最優(yōu)。若表上所有空格地檢驗(yàn)數(shù)ij均為非負(fù),則當(dāng)前調(diào)運(yùn)方案最優(yōu)。否則,當(dāng)前調(diào)運(yùn)方案非最優(yōu),須調(diào)整改。⑴用閉回路法求ij:五零八零二零二零三零三零××××××+-+-+-閉回路:起點(diǎn)與終點(diǎn)是同一空格以外,其余頂點(diǎn)均為基格地曲折閉合多邊形。質(zhì):凡可行調(diào)運(yùn)方案均只能畫唯一閉回路。下以空格x三三為例作閉回路?？崭駒三三地檢驗(yàn)數(shù):沿閉回路增加一個(gè)單位地運(yùn)輸量,由此帶來地費(fèi)用代數(shù)與,即三三=二-零.三+一.五-七+零.八-零.三=-三.三其余類推。-三.三六.七六.五-四.四一-五.三4①確定入基空格:取最小地負(fù)數(shù)-五.三對應(yīng)地空格(非基變量)x三一入基。五零八零二零二零三零三零××××××-三.三六.七六.五-四.四一-五.三+-+-②確定出基基格:在x三一地閉回路,標(biāo)負(fù)號地基格運(yùn)輸量最小者M(jìn)in{五零,三零}=三零,對應(yīng)地基格(基變量)x二一出基。③沿閉回路方向調(diào)整運(yùn)輸量:標(biāo)正號地格子增加三零,標(biāo)負(fù)號地格子減少三零,得新調(diào)運(yùn)方案如下。5二零八零五零二零三零×三零×××××二一.四一.二零.九一五.三全部空格檢驗(yàn)數(shù)均為非負(fù),當(dāng)前調(diào)運(yùn)方案最優(yōu):X一一=二零,X一三=八零,X二二=五零,X二四=三零,X三一=三零,X三二=二零Z*=一.五×二零+零.三×八零+零.八×五零+二×三零+一.二×三零+零.三×二零=一九六6⑵用位勢法求ij:①利用基格求行列位勢:令Ui+Vj=Cij有U一+V一=C一一=一.五U一+V三=C一三=零.三U二+V一=C二一=七U二+V二=C二二=零.八U二+V四=C二四=二U三+V二=C三二=零.三五零八零二零二零三零三零××××××-三.三六.七六.五-四.四一-五.三一.五二零.三三七零.八一.四二一.二零.三二二.五令U一=零②計(jì)算空格檢驗(yàn)數(shù):ij=Cij–(Ui+Vj)有一二=C一二–(U一+V二)=二-(零-四.七)=六.七一四=C一四–(U一+V四)=三-(零–三.五)=六.五二三=C二三–(U二+V三)=一.四-(五.五+零.三)=-四.四三一=C三一–(U三+V一)=一.二-(五+一.五)=-五.三三三=C三三–(U三+V三)=二-(五+零.三)=-三.三三四=C三四–(U三+V四)=二.五-(五–三.五)=一U一=零U二=五.五U三=五V一=一.五V二=-四.七V三=零.三V四=-三.五

++--7①利用基格求行列位勢:令Ui+Vj=Cij有U一+V一=C一一=一.五U一+V三=C一三=零.三U二+V二=C二二=零.八U二+V四=C二四=二U三+V一=C三一=一.二U三+V二=C三二=零.三二零八零五零二零三零×三零×××××二一.四一.二零.九一五.三一.五二零.三三七零.八一.四二一.二零.三二二.五令U一=零②計(jì)算空格檢驗(yàn)數(shù):ij=Cij–(Ui+Vj)有一二=C一二–(U一+V二)=二-(零+零.六)=一.四一四=C一四–(U一+V四)=三-(零+一.八)=一.二二一=C二一–(U二+V一)=七-(零.二+一.五)=五.三二三=C二三–(U二+V三)=一.四-(零.二+零.三)=零.九三三=C三三–(U三+V三)=二-(-零.三+零.三)=二三四=C三四–(U三+V四)=二.五-(-零.三+一.八)=一U一=零U二=零.二U三=-零.三V一=一.五V二=零.六V三=零.三V四=一.八全部空格檢驗(yàn)數(shù)均為非負(fù),當(dāng)前調(diào)運(yùn)方案最優(yōu):X一一=二零,X一三=八零,X二二=五零,X二四=三零,X三一=三零,X三二=二零Z*=一.五×二零+零.三×八零+零.八×五零+二×三零+一.二×三零+零.三×二零=一九六8表上作業(yè)法地步驟:第一步:列出產(chǎn)售衡表與運(yùn)價(jià)表。第二步:用最小元素法給出初始調(diào)運(yùn)方案。第三步:用閉回路法或位勢法求出所有空格(非基變量)檢驗(yàn)數(shù)ij。若ij≥零,則當(dāng)前方案最優(yōu);否則轉(zhuǎn)入下一步。第四步:對當(dāng)前方案調(diào)整改。選負(fù)檢驗(yàn)數(shù)絕對值最大地空格入基,并作閉回路,確定