第2章：線性規(guī)劃專題

第二章：運(yùn)輸問題3.1產(chǎn)銷平衡的運(yùn)輸問題：直接用表作業(yè)法

例：某地有三個(gè)有色金屬礦A1、A2、A3，生產(chǎn)同一種金屬礦石，A1礦的年產(chǎn)量為100萬噸，A2礦為80萬噸，A3礦為50萬噸。礦石全部供應(yīng)四個(gè)冶煉廠，B1廠的全部需求量為50萬噸，B2廠70為萬噸，B3廠為80萬噸，B4廠為30萬噸。產(chǎn)量恰好等于總需求量，礦石由各礦山運(yùn)到冶煉廠的單位運(yùn)價(jià)已知，如下表。問如何安排運(yùn)輸，使各礦山的礦石運(yùn)到冶煉廠，滿足各廠的需要，且運(yùn)輸費(fèi)用最小，試建立該問題的數(shù)學(xué)模型？

1第一步：列出產(chǎn)售平衡表。第二步：給出初始調(diào)運(yùn)方案(相當(dāng)于單純形法的初始基本可行解)。用最小元素法：從運(yùn)價(jià)最小的變量格子開始分配，按盡可能滿足一方取小的原則。50①80②20③20④30⑤30⑥××××××總運(yùn)費(fèi)：Z(1)=1.5×20+0.3×80+7×30+0.8×20+2×30+0.3×50=390

基格：已分配運(yùn)量的格子，對(duì)應(yīng)的變量為基變量，共6個(gè)。空格：未分配運(yùn)量的格子，對(duì)應(yīng)的變量為非基變量(打×)，共6個(gè)。2第三步：判斷當(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)整改進(jìn)。⑴用閉回路法求

ij：508020203030××××××+-+-+-閉回路：起點(diǎn)和終點(diǎn)是同一空格以外，其余頂點(diǎn)均為基格的曲折閉合多邊形。性質(zhì)：凡可行調(diào)運(yùn)方案均只能畫唯一閉回路。下以空格x33為例作閉回路。空格x33的檢驗(yàn)數(shù)：沿閉回路增加1個(gè)單位的運(yùn)輸量，由此帶來的費(fèi)用代數(shù)和，即

33=2-0.3+1.5-7+0.8-0.3=-3.3其余類推。-3.36.76.5-4.41-5.33①確定入基空格：取最小的負(fù)數(shù)-5.3對(duì)應(yīng)的空格(非基變量)x31入基。508020203030××××××-3.36.76.5-4.41-5.3+-+-②確定出基基格：在x31的閉回路中，標(biāo)負(fù)號(hào)的基格運(yùn)輸量最小者M(jìn)in{50，30}=30，對(duì)應(yīng)的基格(基變量)x21出基。③沿閉回路方向調(diào)整運(yùn)輸量：標(biāo)正號(hào)的格子增加30，標(biāo)負(fù)號(hào)的格子減少30，得新調(diào)運(yùn)方案如下。42080502030×30×××××

21.41.20.91

5.3全部空格檢驗(yàn)數(shù)均為非負(fù)，當(dāng)前調(diào)運(yùn)方案最優(yōu)：

X11=20，X13=80，X22=50，X24=30，X31=30，X32=20Z*=1.5×20+0.3×80+0.8×50+2×30+1.2×30+0.3×20=1965⑵用位勢(shì)法求

ij：①利用基格求行列位勢(shì)：令Ui+Vj

=Cij

有

U1+V1=C11=1.5U1+V3=C13=0.3U2+V1=C21=7U2+V2=C22=0.8U2+V4=C24=2U3+V2=C32=0.3508020203030××××××

-3.3

6.7

6.5-4.4

1-5.31.520.3370.81.421.20.322.5令U1=0②計(jì)算空格檢驗(yàn)數(shù)：

ij=Cij

–(Ui+Vj)

有

12=C12–(U1+V2)=2-(0-4.7)=6.7

14=C14–(U1+V4)=3-(0–3.5)=6.5

23=C23–(U2+V3)=1.4-(5.5+0.3)=-4.4

31=C31–(U3+V1)=1.2-(5+1.5)=-5.3

33=C33–(U3+V3)=2-(5+0.3)=-3.3

34=C34–(U3+V4)=2.5-(5–3.5)=1

U1=0U2=5.5U3=5V1=1.5V2=-4.7V3=0.3V4=-3.5

++--6①利用基格求行列位勢(shì)：令Ui+Vj

=Cij

有

U1+V1=C11=1.5U1+V3=C13=0.3U2+V2=C22=0.8U2+V4=C24=2U3+V1=C31=1.2U3+V2=C32=0.32080502030×30×××××

2

1.4

1.20.9

1

5.31.520.3370.81.421.20.322.5令U1=0②計(jì)算空格檢驗(yàn)數(shù)：

ij=Cij

–(Ui+Vj)

有

12=C12–(U1+V2)=2-(0+0.6)=1.4

14=C14–(U1+V4)=3-(0+1.8)=1.2

21=C21–(U2+V1)=7-(0.2+1.5)=5.3

23=C23–(U2+V3)=1.4-(0.2+0.3)=0.9

33=C33–(U3+V3)=2-(-0.3+0.3)=2

34=C34–(U3+V4)=2.5-(-0.3+1.8)=1

U1=0U2=0.2U3=-0.3V1=1.5V2=0.6V3=0.3V4=1.8全部空格檢驗(yàn)數(shù)均為非負(fù)，當(dāng)前調(diào)運(yùn)方案最優(yōu)：

X11=20，X13=80，

X22=50，X24=30，

X31=30，X32=20Z*=1.5×20+0.3×80+0.8×50+2×30+1.2×30+0.3×20=1967

表上作業(yè)法的步驟：第一步：列出產(chǎn)售平衡表和運(yùn)價(jià)表。第二步：用最小元素法給出初始調(diào)運(yùn)方案。第三步：用閉回路法或位勢(shì)法求出所有空格(非基變量)檢驗(yàn)數(shù)

ij。

若

ij≥0，則當(dāng)前方案最優(yōu)；否則轉(zhuǎn)入下一步。第四步：對(duì)當(dāng)前方案調(diào)整改進(jìn)。選負(fù)檢驗(yàn)數(shù)中絕對(duì)值最大的空格入基，并作閉回路，確定