最新运筹学第8讲-运输问题幻灯片.ppt

《最新运筹学第8讲-运输问题幻灯片.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学第8讲-运输问题运输问题例8.1某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？运输问题解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，建立如下的模型：Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1、2；j=1、2、3）运输问题运输问题是一类特殊的线性规划

2、问题，具有如下性质：(1)运输问题的模型中包含mn个变量，m+n个约束方程，且在约束系数中各变量的系数或者是1或者是0，变量为双下标变量。(2)运输问题的基本可行解中基变量的个数为m+n-1个。此矩阵的秩为4=2+3-1=m+n-1，而不是m+n,而基变量的个数与秩数相等。运输问题定义：闭回路从运输表的某个格子出发，沿水平或垂直方向前进，在另一个格子处转90度，继续前进，……，重复此过程，直到回到出发时的格子，由此形成一条封闭的折线，称为闭回路，转角处的格子称为闭回路的顶点。运输问题(3)以运输问题的基本可行解的m+n-1个基变量为顶点，不会形成闭回路。(4)运输问题的一个

3、可行解中，如果非零分量的个数为m+n-1个，并且以这些非零分量为顶点，不会形成闭回路。(5)在运输问题的一个可行解中，如果非零分量的个数为m+n-1个，并且以这些非零分量为顶点不会形成闭回路，则这个解为一个基本可行解。(6)若所有ai,bj皆为整数，则基本可行解的各分量值也为整数。表上作业法表上作业法时单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法，但具体计算和术语有所不同。表上作业法的求解过程包含3个阶段：确定初始基本可行解；进行最优性检验，以决定继续求解还是停止；迭代求解新的基本可行解，此方法要求模型是产销平衡的。表上作业法例8.2某食品公司下属A1，A2，A

4、3三个食品厂生产食品，3个厂每个月的生产能力分别为7吨、4吨、9吨，食品运送到B1，B2，B3，B4四个销售点，它们对于食品的月需求量分别为3吨、6吨、5吨、6吨，试制定最优运送方案。解这是一个产销平衡的运输问题。表上作业法1.确定初始的基本可行解由于运输问题的特殊性，在找初始基本可行解时，不用引入人工变量，可以直接在表上给出基本可行解。将所有cij写在格子的左上角，将每个基变量的数值填在表中相应格子的右下角，右下角没有填数字的格子——空格对应非基变量。(1)西北角法从西北角的格子开始填数，给x11尽可能大的值，令x11=min{a1,b1}=min{7,3}=3由于销售点

5、B1已满足要求，故不再向B1运送食品，即表中第1列中其他变量x21，x31皆为非基变量，即为空格。表上作业法将已满足要求的列称为饱和列，将饱和列(第1列)划掉。再对于剩下的西北角的格子中填尽可能大的数，逐渐划去饱和行(列)。除最后一个格子外，每划掉一条线对应一个饱和行(列)；最后一个格子同时使行和列饱和，因此最后一个格子划掉两条线。表上作业法(2)最小元素法从运价取最小值的格子开始，在这个格子中填尽可能大的数，划去饱和行(列)，在剩下的格子中选取运价取最小值的格子，对其赋值，依次划去饱和行(列)。表上作业法比较一下上面两种方法初始基本可行解所对应的目标函数值：西北角法：f1

6、=135最小元素法：f2=86由此可以看出，采用最小元素法，更接近最优目标函数值，收敛速度更快。注:在应用西北角或最小元素法时，应遵循：除最后一个元素外，填一个数只划掉一行(或一列)。当填一个数后，如果所在行和列同时饱和，也只划掉一行(或一列)，只是接着填下一个数时，要在没划掉的饱和行(饱和列)上的某个没划过的空格子中，填上一个数字0之后，再划去该行(该列)。表上作业法这个0不同于其他空格，表明该变量为基变量，是起占位子作用的，表明当前基本可行解是退化的(某个基变量取值为0)。其占位子是为了保证基变量的个数为m+n-1个。如下例所示：可以证明：用西北角法或最小元素法得到的解

7、确为基本可行解，只需证明填数字的格子为m+n-1个，并且这m+n-1个格子不构成闭回路即可。（可由反证法证明）表上作业法(3)Vogel法最小元素法的缺点是：为了节省一处的费用，有时造成其他处要花费更多的运费。Vogel法考虑到：如果一产地的产品加入不能按最小运费就近供应，就考虑减少运费，这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多，因此，对差额最大处，就应当采用最小费用调运。表上作业法第一步，计算各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。表上作业法第二步，从行或列差额