【正文】 練習(xí)題 銷(xiāo)地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 6 7 5 3 14 A2 8 4 2 7 27 A3 5 9 10 6 19 銷(xiāo)量 22 13 12 13 12 13 13 19 1 2 初始基可行解－－西北角法 ?在滿(mǎn)足約束條件下盡可能的給最左上角的變量最大值 . 銷(xiāo)地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 12 4 11 16 A2 2 10 3 9 10 A3 8 5 11 6 22 銷(xiāo)量 8 14 12 14 48 8 8 6 4 8 14 所以，初始基可行解為： …… 目標(biāo)函數(shù)值 Z＝ 372 練習(xí)題 銷(xiāo)地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 6 7 5 3 14 A2 8 4 2 7 27 A3 5 9 10 6 19 銷(xiāo)量 22 13 12 13 8 13 13 14 6 6 初始基可行解－－沃格爾法 ? 最小元素法，有時(shí)按某一最小單位運(yùn)價(jià)優(yōu)先安排物品調(diào)運(yùn)時(shí)，卻可能導(dǎo)致不得不采用運(yùn)費(fèi)很高的其他供銷(xiāo)點(diǎn)，從而使整個(gè)運(yùn)輸費(fèi)用增加。返回 1)、 2)。 B1 B2 B3 B4 A1 A2 A3 ?特征 : ?1. 每個(gè)頂點(diǎn)都是轉(zhuǎn)角點(diǎn) . ?2. 每一邊都是水平或垂直的 . ?3. 每一行 (或列 )若有閉回路的頂點(diǎn) ,則必有兩個(gè) . 某空格的檢驗(yàn)數(shù)是以該空格為第一個(gè)頂點(diǎn)，某回路的奇數(shù)頂點(diǎn)運(yùn)價(jià)和減去其偶數(shù)頂點(diǎn)運(yùn)價(jià)和。 解改進(jìn)的具體步驟為 (1)以 xij為換入變量，找出它在運(yùn)輸表中的閉回路； (2)以空格 (Ai,Bj)為第一個(gè)奇數(shù)頂點(diǎn)，沿閉回路的順 (或逆 )時(shí)針?lè)较蚯斑M(jìn)，對(duì)閉回路上的頂點(diǎn)依次編號(hào)； (3)在閉回路上的所有偶數(shù)頂點(diǎn)中，找出運(yùn)輸量最小的頂點(diǎn) (格子 )，以該格中的變量為換出變量； (4)以換出變量的運(yùn)輸量為調(diào)整量，將該閉回路上所有奇數(shù)頂點(diǎn)處的運(yùn)輸量都增加這一數(shù)值，所有偶數(shù)頂點(diǎn)處的運(yùn)輸量都減去這一數(shù)值，從而得出一新的運(yùn)輸方案。 3．（二 ）退化 某一基變量 的值為 0 ?初始解 在確定初始解的供需關(guān)系時(shí)，若在確定（ i,j ） 的數(shù)字時(shí)，要?jiǎng)澣サ?i行 ,第 j列。有時(shí)，經(jīng)轉(zhuǎn)運(yùn)比直接運(yùn)到目的地更為經(jīng)濟(jì)。?????????? ???????ijmijijnjiijminjijijxnjbxmiaxxCz模型： 運(yùn)價(jià)表為： ?例： 某市有三個(gè)造紙廠(chǎng) A1， A2， A3，其紙的產(chǎn)量分別為 8， 5和 9個(gè)單位，有 4個(gè)集中用戶(hù) B1， B2， B3， B4，其需用量分別為 4， 3， 5和 6個(gè)單位。可以列出其運(yùn)價(jià)表，用表上作業(yè)法求解。為了不誤合同規(guī)定的交貨期，第一 .二 .三 .四月必須安裝發(fā)動(dòng)機(jī)的臺(tái)數(shù)分別為：10 .15 .25 .20。 ? 解： 1）設(shè) xi表示第 i個(gè)月生產(chǎn)發(fā)動(dòng)機(jī)的臺(tái)數(shù)， yi表示第個(gè)月的存儲(chǔ)臺(tái)數(shù)，則一般 LP模型為： ??????????????????????????????????????????0,1030352570502510)(113110111108m i n43214432133212211143214321iiyxxxxxyxxxxyxxxyxxyxyyyyxxxx?個(gè)月發(fā)動(dòng)機(jī)的安裝。 ? 2）每天載貨航程所需的船只數(shù)： 1591057137317BDFACBDE? ??? ??? ??? ?? 只。已知煤礦年產(chǎn)量分別 A為 400萬(wàn)噸， B為 450萬(wàn)噸，從兩煤礦至各城市煤炭運(yùn)價(jià) (萬(wàn)元／萬(wàn)噸 )如表 3— 23所示。試求將甲、乙兩礦煤炭全部分配出去，滿(mǎn)足上述條件又使總運(yùn)費(fèi)為最低的調(diào)運(yùn)方案。 增加一個(gè)假想需求部門(mén)丁。 ? ？該航運(yùn)公司至少應(yīng)配備多少條船，才能滿(mǎn)足所有航線(xiàn)的運(yùn)貨需求。 ? 2）把此問(wèn)題作為運(yùn)輸問(wèn)題來(lái)處理，試建立相應(yīng)的運(yùn)輸表格。 判斷下列說(shuō)法是否正確 (1)運(yùn)輸問(wèn)題是一種特殊的線(xiàn)性規(guī)劃模型，因而求解結(jié)果也可能出現(xiàn)下列四種情況之一：有唯一最優(yōu)解，有無(wú)窮多最優(yōu)解，無(wú)界解，無(wú)可行解； (2)在運(yùn)輸問(wèn)題中，只要給出一組合 (m+n1)個(gè)非零的 {xij}，且滿(mǎn)足 Σxij=ai， Σ xij=bj，就可以作為一個(gè)初始基可行解； (3)表上作業(yè)法實(shí)質(zhì)上就是求解運(yùn)輸問(wèn)題的單純形法； (4)按最小元素法 (或伏格爾法 )給出的初始基可行解，從每一空格出發(fā)可以找出而且僅能找出唯一的閉回路； (5)如果運(yùn)輸問(wèn)題單位運(yùn)價(jià)表的某一行 (或某一列 )元素分別加上一個(gè)常數(shù) k，最優(yōu)調(diào)運(yùn)方案將不會(huì)發(fā)生變化； (6)如果運(yùn)輸問(wèn)題單位運(yùn)價(jià)表的某一行 (或某一列 )元素分別乘上一個(gè)常數(shù) k，最優(yōu)調(diào)運(yùn)方案將不會(huì)發(fā)生變化； (7)當(dāng)所有產(chǎn)地產(chǎn)量和銷(xiāo)地的銷(xiāo)量均為整數(shù)值時(shí)，運(yùn)輸問(wèn)題的最優(yōu)解也為整數(shù)值 1， 2， 6不對(duì) 練習(xí)：用位勢(shì)法（對(duì)偶變量法）求其檢驗(yàn)數(shù)。 銷(xiāo)地 產(chǎn)地 B1 B2 B3 B4 B5(貯存 ) 產(chǎn)量 A1 3 12 3 4 0 8 4 18 6 3 4 A2 11 2 5 9 0 5 0 3 0 2 8 A3 6 7 1 5 0 9 2 9 5 4 4 銷(xiāo)量 4 3 5 6 4 貯存 產(chǎn)量銷(xiāo)量有轉(zhuǎn)運(yùn)的運(yùn)輸問(wèn)題 轉(zhuǎn)運(yùn)量 t1 t2 t3 t4 t5 t6 t7 A2 A3 A1 a2=27 a3=19 a1=14 供應(yīng)量 需求量 B2 B3 B4 B1 a5=0 a6=0 a4=0 a7=0 A2 A3 A1 b4=22 b5=13 b6=12 b7=13 B2 B3 B4 B1 b1=0 b2=0 b3=0 xij 轉(zhuǎn)運(yùn)量 t1 t2 t3 t4 t5 t6 t7 假設(shè)單位運(yùn)轉(zhuǎn)費(fèi)用為 ti，則線(xiàn)性規(guī)劃模型為： 7711767623232121171713131212.........m intctcxcxcxcxcxcxcz????????????? ????????717171 iiijiiijjijij tcxc7,.. .,2,1,022144746454342414171615141312144746454342411171615141312????????????????????????????jixtxxxxxxtxxxxxxtxxxxxxtxxxxxxij????7711767623232121171713131212.........m intctcxcxcxcxcxcxcz????????????? ????????717171 iiijiiijjijij tcxc7,.. .,2,1,022144746454342414171615141312144746454342411171615141312????????????????????????????jixtxxxxxxtxxxxxxtxxxxxxtxxxxxxij????141716151413121 ???????? xxxxxxt141716151413121 ????????? QxxxxxxtQ1417161514131211 ???????? QxxxxxxxQxxxxxxxQxxxxxxxQxxxxxxx??????????????????????22746454443424147161514131211147464544434241?? ??? ???7171