《管理運籌學(xué)》演示運輸問題

《管理運籌學(xué)》演示制作&講授：施應(yīng)玲1999年12月1宅)sylpy@263.net華北電力大學(xué)目錄線性規(guī)劃圖解法單純形表結(jié)構(gòu)線性規(guī)劃單純形法(1)最小元素法伏格爾法閉回路法位勢法閉回路調(diào)整法目標(biāo)規(guī)劃圖解法(1)目標(biāo)規(guī)劃圖解法(2)整數(shù)規(guī)劃(分枝定界法)和和線性規(guī)劃單純形法(2)圖解法與單純形法的聯(lián)系指派問題(匈牙利法)(1)使用計算機軟件包求解指派問題(匈牙利法)(2)0-1規(guī)劃(隱枚舉法)整數(shù)規(guī)劃(割平面法)典型應(yīng)用案例線性規(guī)劃單純形法(3)目標(biāo)規(guī)劃單純形法線性規(guī)劃求解幾種結(jié)果幾種常用規(guī)劃數(shù)學(xué)軟件比較動態(tài)規(guī)劃(1)動態(tài)規(guī)劃(2)最小樹問題(破圈法/避圈法)最短路問題(迪克斯拉法)(1)最大流問題(?？诉d法)最小費用最大流問題(2)對偶單純形法改進單純形法動態(tài)規(guī)劃(逆推法)(順推法)(3)運輸問題（表上作業(yè)法）銷地產(chǎn)地B1B2B3B4A1A2A3銷量產(chǎn)量產(chǎn)地A1A2A3銷地B1B2B3B47493656317119432101085最小元素法11223344551010產(chǎn)銷平衡表單位運價表運輸問題(表上作業(yè)法)銷地B1B2B3B4產(chǎn)地A1A2A3銷量3656產(chǎn)量749產(chǎn)銷平衡表伏格爾法銷地B1B2B3B4A1A2A3產(chǎn)地單位運價表317119432101085行差額列差額011601213321331212312762521020818855522771010運輸問題(表上作業(yè)法)產(chǎn)地A1A2A3銷地B1B2B3B4銷量3656產(chǎn)量749閉回路法333146311197432101058檢驗數(shù)表

(+1)(-1)(+1)(-1)??????1A1A3產(chǎn)地A2銷地B1B2B3B4產(chǎn)銷平衡表+單位運價表運輸問題(表上作業(yè)法)產(chǎn)地A1A2A3銷地B1B2B3B4銷量3656產(chǎn)量749閉回路法333146311197432101058檢驗數(shù)表

(+1)(-1)(+1)(-1)21A1A3產(chǎn)地A2銷地B1B2B3B4產(chǎn)銷平衡表+單位運價表運輸問題(表上作業(yè)法)產(chǎn)地A1A2A3銷地B1B2B3B4銷量3656產(chǎn)量749閉回路法333146311197432101058檢驗數(shù)表

21(+1)(-1)(+1)(-1)(+1)(-1)1A1A3產(chǎn)地A2銷地B1B2B3B4產(chǎn)銷平衡表+單位運價表運輸問題(表上作業(yè)法)產(chǎn)地A1A2A3銷地B1B2B3B4銷量3656產(chǎn)量749閉回路法333146311197432101058檢驗數(shù)表

211(+1)(-1)(+1)(-1)(+1)(-1)A1A3產(chǎn)地A2銷地B1B2B3B4產(chǎn)銷平衡表+單位運價表運輸問題(表上作業(yè)法)產(chǎn)地A1A2A3銷地B1B2B3B4銷量3656產(chǎn)量749閉回路法333146311197432101058檢驗數(shù)表

211A1A3產(chǎn)地A2銷地B1B2B3B4(+1)(-1)(+1)(-1)產(chǎn)銷平衡表+單位運價表運輸問題(表上作業(yè)法)產(chǎn)地A1A2A3銷地B1B2B3B4銷量3656產(chǎn)量749閉回路法333146311197432101058檢驗數(shù)表

211A1A3產(chǎn)地A2銷地B1B2B3B4(-1)(+1)(-1)(+1)產(chǎn)銷平衡表+單位運價表運輸問問題（（表上上作業(yè)業(yè)法））銷地產(chǎn)地B1B2B3B4A1A2A3銷量產(chǎn)量7493656最小元元素法法314633產(chǎn)銷平平衡表表產(chǎn)銷平平衡表表31645321013銷量產(chǎn)量365674最小元元素法法位勢表表位勢法法3521920-418列位勢行位勢銷地B1B2B3B4檢驗數(shù)數(shù)表產(chǎn)地A1A2A3列位勢1829行位勢10-437119108注:浮碉數(shù)字代表運價1102112-1銷地B1B2B3B4產(chǎn)地A1A2A3銷量3656產(chǎn)量749閉回路路調(diào)整整法364133(+1)(-1)(+1)(-1)(-1)(-1)(-1)(-1)11運輸問問題（（表上上作業(yè)業(yè)法））調(diào)整整表調(diào)整后后的運運輸方方案銷地B1B2B3B4產(chǎn)地A1A2A3銷量3656產(chǎn)量749365132從運價價表中中找出出一最最小值值(稱稱最小小元素素)，，當(dāng)有有兩個個以上上最小小元素素時，，可任任選其其中的的一個個，該該元素素的位位置即即為要要調(diào)運運的位位置；；在產(chǎn)銷銷平衡衡表對對應(yīng)最最小運運價的的位置置進行行分配配，盡盡可能能調(diào)運運；在單位位運價價表中中劃去去以被被滿足足的行行或列列處的的運價價，表表示該該行或或列的的調(diào)運運已完完成；；重復(fù)上上述步步驟。。再在在上面面運價價表中中找出出沒有有被劃劃去的的最小小元素素，再再在產(chǎn)產(chǎn)銷平平衡表表對應(yīng)應(yīng)的最最小運運價位位置進進行調(diào)調(diào)運分分配，，并劃劃去相相應(yīng)的的行或或列列。步驟如下下：從單位運運價表中中每行和和每列上上分別找找出兩個個最小元元素，計計算這兩兩個最小小元素的的差額，，最大差差額所在在的行或或列中最最小運價價所在位位置，即即優(yōu)先進進行調(diào)運運的位置置；在產(chǎn)銷平平衡表上上相應(yīng)的的調(diào)運位位置上盡盡最大可可能調(diào)運運；在運價表表上劃去去相應(yīng)的的行或列列的運價價；重復(fù)上面面步驟，，再在運運價表中中計算各各行和各各列沒有有劃去的的最小運運價和次次小運價價的差額額，確定定最大差差額所在在的行或或列中最最小運價價的位置置，并進進行調(diào)運運，同時時在運價價表上劃劃去相應(yīng)應(yīng)的行或或列的運運價。步驟如下下：先做一個位勢表，位勢表結(jié)構(gòu)與平衡表類似，將產(chǎn)銷平衡表數(shù)字格中運量換以運價，并在表的右端增加1列行位勢和在表的下端增加1行列位勢；任意給定某一行位勢或列位勢的值，再按照公式確定其它的或值。這里，為運價；計算空格檢驗數(shù)。任一空格的檢驗數(shù)按下式計算：式中為該空格對應(yīng)的運價，和分別為該行和該列的位勢。步驟如下:從檢驗數(shù)數(shù)表中找找出最小小的負檢檢驗數(shù)。。當(dāng)有兩兩個或兩兩個以上上的負檢檢驗數(shù)時時，選取取其中最最小的檢檢驗數(shù)；；在產(chǎn)銷平平衡表中中以最小小的負檢檢驗數(shù)所所對應(yīng)的的空格為為起點，，作一閉閉回路，，閉回路路上其它它頂點必必須是數(shù)數(shù)字格，，再從起起點開始始沿閉回回路按順順時針或或逆時針針增加1個單位位運量(標(biāo)注+1),其它頂頂點相應(yīng)應(yīng)的增加加(標(biāo)注注+1),或減減少(標(biāo)標(biāo)注-1)1個個單位運運量,以以保持供供需平衡衡；確定調(diào)運運方案的的調(diào)整量量。所有有標(biāo)注(-1)數(shù)字格格所對應(yīng)應(yīng)運量的的最小值值，為調(diào)調(diào)運方案案的調(diào)整整量。給所有標(biāo)標(biāo)注(+1)數(shù)數(shù)字格運運量增加加一個調(diào)調(diào)整量，，所有標(biāo)標(biāo)注(-1)數(shù)數(shù)字格運運量減少少一個調(diào)調(diào)整量，，閉回路路之外的的其它運運量保持持不變,這樣得得到一個個新的調(diào)調(diào)