產銷平衡數(shù)學模型ppt課件

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

2、等式約束可寫成共有共有 個等式約束個等式約束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運輸問題的圖描述運輸問題的圖描述1B2BnB1A2AmA產地產地銷地銷地1a2ama產量產量1b2bnb銷量銷量1mc2mcmnc11c12c1nc11mnijijijc x在流量平衡和非負約束下

3、極小化總的運輸費用在流量平衡和非負約束下極小化總的運輸費用運輸表描述運輸表描述產地產地銷地銷地產量產量銷量銷量1AmA2AnB1B2B2ama1anb2b1b21c12x22c22x11c11x1mc1mx12c12x2mc2mxnc1nx1nc2nx2mncmnx例例產地產地銷地銷地產量產量銷量銷量1A3A2A4B1B2B10221648148221x1022x411x831x1212x532x1114x924x634x3B12413x323x1133x14圖表示圖表示1B2B4B1A2A3A16102214812143B412114210938561111x12x14x13x21x22x2

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

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

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

7、銷地產量產量銷量銷量1A3A2A4B1B2B282264814828104812511963B1043111421014產地產地銷地銷地產量產量銷量銷量1A3A2A4B1B2B2864814828104812511963B104311614210148產地產地銷地銷地產量產量銷量銷量1A3A2A4B1B2B2864814828104812511963B10431162101486最后刪除兩個約束最后刪除兩個約束1nm不會形成回路不會形成回路每次刪除一個約束節(jié)點）每次刪除一個約束節(jié)點）變量變量產生基本可行解等價于在運輸圖中生成一個支撐樹產生基本可行解等價于在運輸圖中生成一個支撐樹1B2B4B1A

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

9、uv 1413131100000cuu vvu 212123233232343cuvcuvcuvcu1142323223312123343133ucvcuucvvcuucvcu產地產地銷地銷地產量產量位勢行位勢行1A3A2A4B1B2B24482104812511963B4311位勢列位勢列銷量銷量1481241488810111u622u63u1v2v3v0利用運輸表解對偶變量位勢法）利用運輸表解對偶變量位勢法）產地產地銷地銷地產量產量位勢行位勢行1A3A2A4B1B2B24482104812511963B4311位勢列位勢列銷量銷量1481241488810111u622u63u1v12v

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

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

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

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