《管理運(yùn)籌學(xué)》演示(運(yùn)輸問(wèn)題)ppt課件

1、演示制造 & 講授： 施應(yīng)玲 1999年12月1宅)華北電力大學(xué).目錄線性規(guī)劃圖解法單純形表構(gòu)造線性規(guī)劃單純形法(1)最小元素法伏格爾法閉回路法位勢(shì)法閉回路調(diào)整法目的規(guī)劃圖解法(1)目的規(guī)劃圖解法(2)整數(shù)規(guī)劃(分枝定界法)和和線性規(guī)劃單純形法(2)圖解法與單純形法的聯(lián)絡(luò)指派問(wèn)題(匈牙利法)(1)運(yùn)用計(jì)算機(jī)軟件包求解指派問(wèn)題(匈牙利法)(2)0-1規(guī)劃(隱枚舉法)整數(shù)規(guī)劃(割平面法)典型運(yùn)用案例線性規(guī)劃單純形法(3)目的規(guī)劃單純形法線性規(guī)劃求解幾種結(jié)果幾種常用規(guī)劃數(shù)學(xué)軟件比較動(dòng)態(tài)規(guī)劃(1)動(dòng)態(tài)規(guī)劃(2)最小樹問(wèn)題(破圈法/避圈法)最短路問(wèn)題(迪克斯拉法)(1)最大流

2、問(wèn)題(?？诉d法)最小費(fèi)用最大流問(wèn)題(2)對(duì)偶單純形法改良單純形法動(dòng)態(tài)規(guī)劃(逆推法)(順推法)(3).運(yùn)輸問(wèn)題表上作業(yè)法銷地產(chǎn)地B1B2B3B4A1A2A3銷量產(chǎn)量產(chǎn)地A1A2A3銷地B1B2B3B47493656317119432101085最小元素法11223344551010產(chǎn)銷平衡表單位運(yùn)價(jià)表.運(yùn)輸問(wèn)題(表上作業(yè)法)銷地B1B2B3B4產(chǎn)地A1A2A3銷量3656產(chǎn)量749產(chǎn)銷平衡表伏格爾法銷地B1B2B3B4A1A2A3產(chǎn)地單位運(yùn)價(jià)表317119432101085行差額列差額011601213321331212312762521020818855522771010.運(yùn)輸問(wèn)題(表上作業(yè)法

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

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

5、 + 單位運(yùn)價(jià)表.運(yùn)輸問(wèn)題(表上作業(yè)法)產(chǎn)地A1A2A3銷地B1B2B3B4銷量3656產(chǎn)量749閉回路法333146311197432101058檢驗(yàn)數(shù)表 211A1A3產(chǎn)地A2銷地B1B2B3B4(-1)(+1)(-1)(+1)產(chǎn)銷平衡表 + 單位運(yùn)價(jià)表.運(yùn)輸問(wèn)題表上作業(yè)法銷地產(chǎn)地B1B2B3B4A1A2A3銷量產(chǎn)量7493656最小元素法314633產(chǎn)銷平衡表產(chǎn)銷平衡表31645321013銷量產(chǎn)量365674最小元素法位勢(shì)表位勢(shì)法3521920-418列位勢(shì)行位勢(shì)銷地B1B2B3B4檢驗(yàn)數(shù)表產(chǎn)地A1A2A3列位勢(shì)1829行位勢(shì)10-437119108注:浮碉數(shù)字代表運(yùn)價(jià)1102112-

6、1.銷地B1B2B3B4產(chǎn)地A1A2A3銷量3656產(chǎn)量749閉回路調(diào)整法364133(+1)(-1)(+1)(-1)(-1)(-1)(-1)(-1)11運(yùn)輸問(wèn)題表上作業(yè)法調(diào) 整 表調(diào)整后的運(yùn)輸方案銷地B1B2B3B4產(chǎn)地A1A2A3銷量3656產(chǎn)量749365132.從運(yùn)價(jià)表中找出一最小值(稱最小元素)，當(dāng)有兩個(gè)以上最小元素時(shí)，可任選其中的一個(gè)，該元素的位置即為要調(diào)運(yùn)的位置；在產(chǎn)銷平衡表對(duì)應(yīng)最小運(yùn)價(jià)的位置進(jìn)展分配，盡能夠調(diào)運(yùn)；在單位運(yùn)價(jià)表中劃去以被滿足的行或列處的運(yùn)價(jià)，表示該行或列的調(diào)運(yùn)已完成；反復(fù)上述步驟。再在上面運(yùn)價(jià)表中找出沒(méi)有被劃去的最小元素，再在產(chǎn)銷平衡表對(duì)應(yīng)的最小運(yùn)價(jià)位置進(jìn)展調(diào)運(yùn)分

7、配，并劃去相應(yīng)的行或 列。步驟如下：. 從單位運(yùn)價(jià)表中每行和每列上分別找出兩個(gè)最小元素，計(jì)算這兩個(gè)最小元素的差額，最大差額所在的行或列中最小運(yùn)價(jià)所在位置，即優(yōu)先進(jìn)展調(diào)運(yùn)的位置； 在產(chǎn)銷平衡表上相應(yīng)的調(diào)運(yùn)位置上盡最大能夠調(diào)運(yùn)； 在運(yùn)價(jià)表上劃去相應(yīng)的行或列的運(yùn)價(jià)； 反復(fù)上面步驟，再在運(yùn)價(jià)表中計(jì)算各行和各列沒(méi)有劃去的最小運(yùn)價(jià)和次小運(yùn)價(jià)的差額，確定最大差額所在的行或列中最小運(yùn)價(jià)的位置，并進(jìn)展調(diào)運(yùn)，同時(shí)在運(yùn)價(jià)表上劃去相應(yīng)的行或列的運(yùn)價(jià)。 步驟如下：.先做一個(gè)位勢(shì)表，位勢(shì)表構(gòu)造與平衡表類似，將產(chǎn)銷平衡表 數(shù)字格中運(yùn)量換以運(yùn)價(jià)，并在表的右端添加1列行位勢(shì) 和在表的下端添加1行列位勢(shì) ；恣意給定某一行位勢(shì)或列位勢(shì)的值，再按照公式 確定其它的 或 值。這里， 為運(yùn)價(jià)；計(jì)算空格檢驗(yàn)數(shù)。任一空格的檢驗(yàn)數(shù)按下式計(jì)算：式中 為該空格對(duì)應(yīng)的運(yùn)價(jià)， 和 分別為該行和該列的位勢(shì)。步驟如下:.從檢驗(yàn)數(shù)表中找出最小的負(fù)檢驗(yàn)數(shù)。當(dāng)有兩個(gè)或兩個(gè)以上的負(fù)檢驗(yàn)數(shù)時(shí)，選取其中最小的檢驗(yàn)數(shù)；在產(chǎn)銷平衡表中以最小的負(fù)檢驗(yàn)數(shù)所對(duì)應(yīng)的空格為起點(diǎn)，作一閉回路，閉回路上其它頂點(diǎn)必需是數(shù)字格，再?gòu)钠瘘c(diǎn)開場(chǎng)沿閉回路按順時(shí)針或逆時(shí)針添加1個(gè)單位運(yùn)量(標(biāo)注+1),其它頂點(diǎn)相應(yīng)的添加(標(biāo)注+1),或減少(標(biāo)注-1)1個(gè)單位運(yùn)量,以堅(jiān)持供需平衡；確定調(diào)運(yùn)方案的調(diào)整量。一切標(biāo)注(-1)數(shù)字格所對(duì)應(yīng)運(yùn)量的最小