产销不平衡的运输问题--运筹学

1、运筹学-产销不平衡运输问题1 运输问题2 运输问题的表上作业法3 运输问题的进一步讨论运输问题的进一步讨论运输问题 njmixnjbxmiaxxczijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111产销平衡问题的数学模型运输问题n表上作业法是单纯形法在求解运输问题表上作业法是单纯形法在求解运输问题的一种简便方法。的一种简便方法。n单纯形法与表上作业法的关系：单纯形法与表上作业法的关系：（1）找出初始基可行解）找出初始基可行解 （2）求各非基变量的检验数）求各非基变量的检验数（3）判断是否最优解）判断是否最优解计算表中空格检验数计算表中空格检验数表上给出

2、表上给出m+n-1个数字格个数字格检验是否所有检验数非负检验是否所有检验数非负运输问题换基：（4 4）确定换入变量和换出变量找出新）确定换入变量和换出变量找出新的基可行解。的基可行解。（5 5）重复（）重复（2 2）、（）、（3 3）直至求出最优）直至求出最优解。解。表上调整（闭回路调整）表上调整（闭回路调整）（运输问题必有最优解）（运输问题必有最优解）停止最优解？是否运输问题举例说明表上作业法例1、某部门三个工厂生产同一产品的产量、 四个销售点的销量及单位运价如下表：41228543961111104814121482210163214321AAABBBB销量产量销地产地运输问题第一步：确定

3、初始基可行解 最小元素法、伏格尔法n最小元素法思路： 从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。运输问题最小元素法举例41228543961111104814121482210163214321AAABBBB销量产量销地产地822010100614868000060运输问题n例1用伏格尔法得到的初始基可行解4814121482210163214321AAABBBB4122854396111110销量产量销地销地产地产地48148122244685149228114412 z目标函数值目标函数值用最小元素法求出的目标函数z=246运输问题第三步：解的调整 调整位置（2，4

4、）非空，回路角上的格至少为空，且保证数字的非负性。41228543961111104814121482210163214321AAABBBB销量产量销地产地82101468-1（-2）（-2）（+2）（+2）运输问题n调整后的解为：41228543961111104814121482210163214321AAABBBB销量产量销地产地8212144822091122246244689211441251428, 0zij此时的解为最优解。有无穷多最优解运输问题几点说明：n当检验数为的负的变量超过两个，选择最小者对应的变量换入；n在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解；n迭代

5、过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。运输问题产销不平衡的运输问题产销不平衡的运输问题实际问题中产销往往是不平衡的，实际问题中产销往往是不平衡的，就需要把产销不平衡的问题转化成就需要把产销不平衡的问题转化成产销平衡问题。产销平衡问题。产大于销产大于销销大于产销大于产运输问题一、产销不平衡的运输问题n（）若总产量大于总销量，即）若总产量大于总销量，即njjmiiba11minjjinbab111令假象销地的销量为：令假象销地的销量为：运输问题这里，松弛变量这里，松弛变量xi n+1可以视为从可以视为从产地产地A i运往销

6、地运往销地Bn+1的运输量，由的运输量，由于实际并不运送，它们的运费为于实际并不运送，它们的运费为 ci n+1=0i=1,2,m。于是，这个运输问题就转化成了一个于是，这个运输问题就转化成了一个产销平衡的问题。产销平衡的问题。运输问题 njmixnjbxmiaxxczijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111原产大于销平衡问题的数学模型运输问题修改后产大于销平衡问题的数学模型 1,2,1,2,1,01,2,1,2,1,min111111nnjmixnnjbxmiaxxczijjmiijinjijminjijij运输问题决策变量 表示由 到 的

7、物品数量。iAiBijx1211211222221211112111121nnmnmnmmmnnnnnnbbbbxxxxAxxxxAxxxxABBBB销地产地销量产量maaa2112c11cnc121c22cnc21mc2mcmnc000注意：用最小元素法求初始调运方案时，最后一列的零运价最后考虑。运输问题 例:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？B1B2B3产产量量A1646300A2655300销销量量150150200 运输问题 解：增加一个虚设的销地运输费用

8、为解：增加一个虚设的销地运输费用为0 0 B1 B2 B3 B4 产量 A1 6 4 6 0 300 A2 6 5 5 0 300 销量 150 150 200 100 运输问题n（）若总产量小于总销量，即njjmiiba11miinjjmaba111令假象产地的销量为：一、产销不平衡的运输问题仿照上述类似处理。运输问题这里，松弛变量这里，松弛变量x m+1,j可以视为从可以视为从产地产地A m+1运往销地运往销地Bj的运输量，的运输量，由于实际并不运送，它们的运费为由于实际并不运送，它们的运费为c m+1,j=0j=1,2,n。于是，这个运于是，这个运输问题就转化成了一个产销平衡的输问题就转

9、化成了一个产销平衡的问题。问题。运输问题 例例: :某公司从两个产地某公司从两个产地A A1 1、A A2 2将物品将物品运往三个销地运往三个销地B B1 1、B B2 2、B B3 3，各产地的产各产地的产量、各销地的销量和各产地运往各销地量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？何调运可使总运输费用最小？ B1 B2 B3 产量 A1 6 4 6 200 A2 6 5 5 300 销量 250 200 200 运输问题 解：增加一个虚设的产地运输费用为解：增加一个虚设的产地运输费用为0 0 B1 B2 B

10、3 产量 A1 6 4 6 200 A2 6 5 5 300 A3 0 0 0 150 销量 250 200 200 运输问题 产销不平衡运输问题举例产销不平衡运输问题举例 设有设有A、B、C三个化肥厂供应三个化肥厂供应1、2、3、4四个地四个地区的农用化肥。假设效果相同，有关数据如下表区的农用化肥。假设效果相同，有关数据如下表 举例举例1234产量产量A1613221750B1413191560C19202350最低需要最低需要量量3070010最高需要最高需要量量507030不限不限运输问题 根据题意，作出产销平衡运价表：根据题意，作出产销平衡运价表： 运输问题最低要求必须满足，因此把相应

11、的虚设产最低要求必须满足，因此把相应的虚设产地运费取地运费取M ，而最高要求与最低要求的差，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地允许按需要安排，因此把相应的虚设产地运费取为运费取为 0 。对应。对应 4”的销量的销量50 是考虑问题是考虑问题本身适当取的数据，根据产销平衡要求确本身适当取的数据，根据产销平衡要求确定定 D的产量为的产量为 50。运输问题Ex.2 已知运输问题由表给出，试建立运输模型已知运输问题由表给出，试建立运输模型 . Bj Ai B1 B2 B3 ai A142510 A263815 bj8714解解: Bj Ai B1 B2 B3 ai A142510 A263815 A3000 4 bj8714本题产量为本题产量为25，销量为，销量为29，是销大于产问题，是销大于产问题 虚设一个产地虚设一个产地 A3，由于并没有生产，所以，由于并没有生产，所以运价为零，得运输模型运价为零，得运输模型. . 如果各销地不满足时，单位缺货费为如果各销地不满足时，单位缺货费为 4，3，7，则运输模型为则运输模型为437运输问题讨论运输问题一、概念题（判断）1、运输问题是一种LP问题，其求解结果有四种情况。2、在运输问题中，只要给出一组含（m+n-1）个非零的 ，且满足 就可以作为一