产销平衡数学模型ppt课件

1、产销平衡运输问题的数学规划模型线性规划问题）产销平衡运输问题的数学规划模型线性规划问题）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结论：运输问题一组变量的系数线性无关的充要条件是结论：运输问题一组变量的系数线性无关的充要条件是在图或表中不含有回路在图或表中不含有回路1B2B4B1A2A3A00000

6、003B11x21x24x基本可行解的个数基本可行解的个数1nm用最小元素法产生基本可行解用最小元素法产生基本可行解基本思想：优先安排单位运输成本最小的运输方式基本思想：优先安排单位运输成本最小的运输方式产地产地销地销地产量产量销量销量1A3A2A4B1B2B21022164814828104812511963B12431114产地产地销地销地产量产量销量销量1A3A2A4B1B2B222164814828104812511963B10124311142产地产地销地销地产量产量销量销量1A3A2A4B1B2B2226164814828104812511963B10431114210产地产地销地

7、销地产量产量销量销量1A3A2A4B1B2B282264814828104812511963B1043111421014产地产地销地销地产量产量销量销量1A3A2A4B1B2B2864814828104812511963B104311614210148产地产地销地销地产量产量销量销量1A3A2A4B1B2B2864814828104812511963B10431162101486最后删除两个约束最后删除两个约束1nm不会形成回路不会形成回路每次删除一个约束节点）每次删除一个约束节点）变量变量产生基本可行解等价于在运输图中生成一个支撑树产生基本可行解等价于在运输图中生成一个支撑树1B2B4B1A

8、2A3A16102214812143B由流量平衡方程依次可得对应的可行流由流量平衡方程依次可得对应的可行流21231314343282106814xxxxxx计算检验数计算检验数回忆检验数计算公式回忆检验数计算公式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利用对偶变量计算检验数利用对偶变量计算检验数102u63u81v12v73v40v 123123, ,ijijijijijcu u u v v vPcuv121110122448814812414881062（视（视 ）40v 改进基本可行解改进基本可行解产地产地销地销地

11、产量产量销量销量1A3A2A4B1B2B83B2101486102216481481214已知以下基本可行解和负的检验数已知以下基本可行解和负的检验数241 让让 进基取值大于零可改进基本可行解进基取值大于零可改进基本可行解24x由于基本可行解形成一个支撑树，加入任何非基变量一由于基本可行解形成一个支撑树，加入任何非基变量一定和某些基变量形成回路定和某些基变量形成回路1B2B4B1A2A3A16102214812143B参与参与 形成回路形成回路24x13241,A B A BA产地产地销地销地产量产量销量销量1A3A2A4B1B2B83B242x2410 x148246x1022164814

12、8121424x在在 和基变量形成的回路中，让基变量依次减少和基变量形成的回路中，让基变量依次减少或增加或增加 的增加值，可保持等式约束满足的增加值，可保持等式约束满足24x24x产地产地销地销地产量产量销量销量1A3A2A4B1B2B83B1214841022164814812142取取 ，可得下面新的基本可行解，可得下面新的基本可行解24131423min,2xxxx 出基，目标函数等于原目标值加上出基，目标函数等于原目标值加上24242x 242x2410 x246x24x023x算法总结算法总结1用最小元素法确定一个基本可行解用最小元素法确定一个基本可行解2用位势法计算所有非基变量的检

13、验数用位势法计算所有非基变量的检验数3如果所有检验数不小于零，已得最优解，如果所有检验数不小于零，已得最优解， 否则找出最小检验数对应的非基变量以及否则找出最小检验数对应的非基变量以及 与其形成回路的基变量，据此确定相应非与其形成回路的基变量，据此确定相应非 基变量的增加值以及回路基变量的新值，基变量的增加值以及回路基变量的新值， 然后回到上一步继续迭代然后回到上一步继续迭代总产量大于总销量产销不平衡的运输问题总产量大于总销量产销不平衡的运输问题njmixnjbxmiaxxcijjmiijinjijminjijij, 2 , 1, 2 , 1, 0, 2 , 1, 2 , 1, s.t.min1111nj