產(chǎn)銷(xiāo)平衡數(shù)學(xué)模型ppt課件

1、產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的數(shù)學(xué)規(guī)劃模型線性規(guī)劃問(wèn)題）產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的數(shù)學(xué)規(guī)劃模型線性規(guī)劃問(wèn)題）1111mins.t. ,1,10,1,1mnijijijnijijmijjiijc xxaimxbjnximjn 產(chǎn)銷(xiāo)平衡假定：產(chǎn)銷(xiāo)平衡假定：Qbanjjmii11jiQbaxjiij,有可行解有可行解1111,nniijjijjmmjijijiiaxbaiQbxabjQ11,1;,11nmijiijjjixaimxbjn 11111111111111111mmnnmnmninijijijijiijjijijmnmniijjnijijxxxxxaxQbb 最后一個(gè)約束多余，等式約束可寫(xiě)成最后一個(gè)約束多余，

2、等式約束可寫(xiě)成共有共有 個(gè)等式約束個(gè)等式約束1nm11,1;,11nmijiijjjixaimxbjn 11111mnmijijijnaaP xbb留意：留意： i其中其中100 1 00 1 00Tm nijPR jm列向量表示模型列向量表示模型1111mins.t. ,1,110,1,11mnijijijnijijmijjiijc xxaimxbjnximjn 100 1 00Tm ninPR i運(yùn)輸問(wèn)題的圖描述運(yùn)輸問(wèn)題的圖描述1B2BnB1A2AmA產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地1a2ama產(chǎn)量產(chǎn)量1b2bnb銷(xiāo)量銷(xiāo)量1mc2mcmnc11c12c1nc11mnijijijc x在流量平衡和非負(fù)約束下

3、極小化總的運(yùn)輸費(fèi)用在流量平衡和非負(fù)約束下極小化總的運(yùn)輸費(fèi)用運(yùn)輸表描述運(yùn)輸表描述產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量銷(xiāo)量銷(xiāo)量1AmA2AnB1B2B2ama1anb2b1b21c12x22c22x11c11x1mc1mx12c12x2mc2mxnc1nx1nc2nx2mncmnx例例產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量銷(xiāo)量銷(xiāo)量1A3A2A4B1B2B10221648148221x1022x411x831x1212x532x1114x924x634x3B12413x323x1133x14圖表示圖表示1B2B4B1A2A3A16102214812143B412114210938561111x12x14x13x21x22x2

4、4x23x31x32x34x33x產(chǎn)生基本可行解產(chǎn)生基本可行解1B2B4B1A2A3A00000003B111x 141x 211x 241x如果一組變量紅線表示形成回路如果一組變量紅線表示形成回路11 11212114 1424240P xP xP xP x在在 中令其他變量等于中令其他變量等于011mnijijijP x1B2B4B1A2A3A00000003B11x21x24x如果一組變量紅線表示不含回路如果一組變量紅線表示不含回路242111000 xxx在在 中令其他變量等于中令其他變量等于011mnijijijP x上述第一種情況的運(yùn)輸表上述第一種情況的運(yùn)輸表產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)

5、量銷(xiāo)量銷(xiāo)量1A3A2A4B1B2B0000002211x 104111x 812511141x 9241x63B04311011 11212114 1424240P xP xP xP x上述第二種情況的運(yùn)輸表上述第二種情況的運(yùn)輸表產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量銷(xiāo)量銷(xiāo)量1A3A2A4B1B2B000000221x10411x812511924x63B043110242111000 xxx11 1121 2124240P xP xP x結(jié)論：運(yùn)輸問(wèn)題一組變量的系數(shù)線性無(wú)關(guān)的充要條件是結(jié)論：運(yùn)輸問(wèn)題一組變量的系數(shù)線性無(wú)關(guān)的充要條件是在圖或表中不含有回路在圖或表中不含有回路1B2B4B1A2A3A00000

6、003B11x21x24x基本可行解的個(gè)數(shù)基本可行解的個(gè)數(shù)1nm用最小元素法產(chǎn)生基本可行解用最小元素法產(chǎn)生基本可行解基本思想：優(yōu)先安排單位運(yùn)輸成本最小的運(yùn)輸方式基本思想：優(yōu)先安排單位運(yùn)輸成本最小的運(yùn)輸方式產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量銷(xiāo)量銷(xiāo)量1A3A2A4B1B2B21022164814828104812511963B12431114產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量銷(xiāo)量銷(xiāo)量1A3A2A4B1B2B222164814828104812511963B10124311142產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量銷(xiāo)量銷(xiāo)量1A3A2A4B1B2B2226164814828104812511963B10431114210產(chǎn)地產(chǎn)地銷(xiāo)地

7、銷(xiāo)地產(chǎn)量產(chǎn)量銷(xiāo)量銷(xiāo)量1A3A2A4B1B2B282264814828104812511963B1043111421014產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量銷(xiāo)量銷(xiāo)量1A3A2A4B1B2B2864814828104812511963B104311614210148產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量銷(xiāo)量銷(xiāo)量1A3A2A4B1B2B2864814828104812511963B10431162101486最后刪除兩個(gè)約束最后刪除兩個(gè)約束1nm不會(huì)形成回路不會(huì)形成回路每次刪除一個(gè)約束節(jié)點(diǎn)）每次刪除一個(gè)約束節(jié)點(diǎn)）變量變量產(chǎn)生基本可行解等價(jià)于在運(yùn)輸圖中生成一個(gè)支撐樹(shù)產(chǎn)生基本可行解等價(jià)于在運(yùn)輸圖中生成一個(gè)支撐樹(shù)1B2B4B1A

8、2A3A16102214812143B由流量平衡方程依次可得對(duì)應(yīng)的可行流由流量平衡方程依次可得對(duì)應(yīng)的可行流21231314343282106814xxxxxx計(jì)算檢驗(yàn)數(shù)計(jì)算檢驗(yàn)數(shù)回憶檢驗(yàn)數(shù)計(jì)算公式回憶檢驗(yàn)數(shù)計(jì)算公式1,TijijBijcC B Pi j1TTBYC BTTBCY B令令 （對(duì)偶變量）（對(duì)偶變量）TTBCY B,TijijijcY Pi j11,1,11nijijmijjixaimxbjn ,1,11ijuimvjn 111mnuuYvv111,0ijmnijijcuu vvPx13142123323410,6,8,2,14,8xxxxxx13131313100001cuu vv

9、uv 1413131100000cuu vvu 212123233232343cuvcuvcuvcu1142323223312123343133ucvcuucvvcuucvcu產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量位勢(shì)行位勢(shì)行1A3A2A4B1B2B24482104812511963B4311位勢(shì)列位勢(shì)列銷(xiāo)量銷(xiāo)量1481241488810111u622u63u1v2v3v0利用運(yùn)輸表解對(duì)偶變量位勢(shì)法）利用運(yùn)輸表解對(duì)偶變量位勢(shì)法）產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量位勢(shì)行位勢(shì)行1A3A2A4B1B2B24482104812511963B4311位勢(shì)列位勢(shì)列銷(xiāo)量銷(xiāo)量1481241488810111u622u63u1v12v

10、73v0產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量位勢(shì)行位勢(shì)行1A3A2A4B1B2B24482104812511963B4311位勢(shì)列位勢(shì)列銷(xiāo)量銷(xiāo)量1481241488810111u62102u63u81v12v73v0產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量位勢(shì)行位勢(shì)行1A3A2A4B1B2B210412511963B4311位勢(shì)列位勢(shì)列銷(xiāo)量銷(xiāo)量8111u利用對(duì)偶變量計(jì)算檢驗(yàn)數(shù)利用對(duì)偶變量計(jì)算檢驗(yàn)數(shù)102u63u81v12v73v40v 123123, ,ijijijijijcu u u v v vPcuv121110122448814812414881062（視（視 ）40v 改進(jìn)基本可行解改進(jìn)基本可行解產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地

11、產(chǎn)量產(chǎn)量銷(xiāo)量銷(xiāo)量1A3A2A4B1B2B83B2101486102216481481214已知以下基本可行解和負(fù)的檢驗(yàn)數(shù)已知以下基本可行解和負(fù)的檢驗(yàn)數(shù)241 讓讓 進(jìn)基取值大于零可改進(jìn)基本可行解進(jìn)基取值大于零可改進(jìn)基本可行解24x由于基本可行解形成一個(gè)支撐樹(shù)，加入任何非基變量一由于基本可行解形成一個(gè)支撐樹(shù)，加入任何非基變量一定和某些基變量形成回路定和某些基變量形成回路1B2B4B1A2A3A16102214812143B參與參與 形成回路形成回路24x13241,A B A BA產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量銷(xiāo)量銷(xiāo)量1A3A2A4B1B2B83B242x2410 x148246x1022164814

12、8121424x在在 和基變量形成的回路中，讓基變量依次減少和基變量形成的回路中，讓基變量依次減少或增加或增加 的增加值，可保持等式約束滿足的增加值，可保持等式約束滿足24x24x產(chǎn)地產(chǎn)地銷(xiāo)地銷(xiāo)地產(chǎn)量產(chǎn)量銷(xiāo)量銷(xiāo)量1A3A2A4B1B2B83B1214841022164814812142取取 ，可得下面新的基本可行解，可得下面新的基本可行解24131423min,2xxxx 出基，目標(biāo)函數(shù)等于原目標(biāo)值加上出基，目標(biāo)函數(shù)等于原目標(biāo)值加上24242x 242x2410 x246x24x023x算法總結(jié)算法總結(jié)1用最小元素法確定一個(gè)基本可行解用最小元素法確定一個(gè)基本可行解2用位勢(shì)法計(jì)算所有非基變量的檢

13、驗(yàn)數(shù)用位勢(shì)法計(jì)算所有非基變量的檢驗(yàn)數(shù)3如果所有檢驗(yàn)數(shù)不小于零，已得最優(yōu)解，如果所有檢驗(yàn)數(shù)不小于零，已得最優(yōu)解， 否則找出最小檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量以及否則找出最小檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量以及 與其形成回路的基變量，據(jù)此確定相應(yīng)非與其形成回路的基變量，據(jù)此確定相應(yīng)非 基變量的增加值以及回路基變量的新值，基變量的增加值以及回路基變量的新值， 然后回到上一步繼續(xù)迭代然后回到上一步繼續(xù)迭代總產(chǎn)量大于總銷(xiāo)量產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題總產(chǎn)量大于總銷(xiāo)量產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題njmixnjbxmiaxxcijjmiijinjijminjijij, 2 , 1, 2 , 1, 0, 2 , 1, 2 , 1, s.t.min1111nj