运筹学第8讲-运输问题讲课教案.ppt

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

1、运筹学第8讲-运输问题运输问题解：产销平衡问题：总产量=总销量设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）运输问题一般运输模型:产销平衡问题:A1、A2、…、Am表示某物资的m个产地；B1、B2、…、Bn表示某物质的n个销地；ai表示产地Ai的产量；bj表示销地Bj的销量；cij表示把物资从产地Ai运往

2、销地Bj的单位运价。设xij为从产地Ai运往销地Bj的运输量，得到一般运输量问题的模型：运输问题运输表：运输问题注：(1)有时目标函数求最大，如求利润最大或营业额最大等；(2)当某些运输线路上的能力有限制时，在模型中直接加入约束条件(等式或不等式约束)；(3)产销不平衡时，可加入假想的产地(销大于产时)或销地(产大于销时)。运输问题运输问题是一类特殊的线性规划问题，具有如下性质：(1)运输问题的模型中包含mn个变量，m+n个约束方程，且在约束系数中各变量的系数或者是1或者是0，变量为双下标变量。(2)运输问题的基本可行解中基变量的个数为m+n-1个。此矩

3、阵的秩为4=2+3-1=m+n-1，而不是m+n,而基变量的个数与秩数相等。运输问题定义：闭回路从运输表的某个格子出发，沿水平或垂直方向前进，在另一个格子处转90度，继续前进，……，重复此过程，直到回到出发时的格子，由此形成一条封闭的折线，称为闭回路，转角处的格子称为闭回路的顶点。运输问题(3)以运输问题的基本可行解的m+n-1个基变量为顶点，不会形成闭回路。(4)运输问题的一个可行解中，如果非零分量的个数为m+n-1个，并且以这些非零分量为顶点，不会形成闭回路。(5)在运输问题的一个可行解中，如果非零分量的个数为m+n-1个，并且以这些非零分量为顶点不

4、会形成闭回路，则这个解为一个基本可行解。(6)若所有ai,bj皆为整数，则基本可行解的各分量值也为整数。表上作业法表上作业法时单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法，但具体计算和术语有所不同。表上作业法的求解过程包含3个阶段：确定初始基本可行解；进行最优性检验，以决定继续求解还是停止；迭代求解新的基本可行解，此方法要求模型是产销平衡的。表上作业法例8.2某食品公司下属A1，A2，A3三个食品厂生产食品，3个厂每个月的生产能力分别为7吨、4吨、9吨，食品运送到B1，B2，B3，B4四个销售点，它们对于食品的月需求量分别为3吨、6吨、5吨、

5、6吨，试制定最优运送方案。解这是一个产销平衡的运输问题。表上作业法1.确定初始的基本可行解由于运输问题的特殊性，在找初始基本可行解时，不用引入人工变量，可以直接在表上给出基本可行解。将所有cij写在格子的左上角，将每个基变量的数值填在表中相应格子的右下角，右下角没有填数字的格子——空格对应非基变量。(1)西北角法从西北角的格子开始填数，给x11尽可能大的值，令x11=min{a1,b1}=min{7,3}=3由于销售点B1已满足要求，故不再向B1运送食品，即表中第1列中其他变量x21，x31皆为非基变量，即为空格。表上作业法将已满足要求的列称为饱和列，将

6、饱和列(第1列)划掉。再对于剩下的西北角的格子中填尽可能大的数，逐渐划去饱和行(列)。除最后一个格子外，每划掉一条线对应一个饱和行(列)；最后一个格子同时使行和列饱和，因此最后一个格子划掉两条线。表上作业法(2)最小元素法从运价取最小值的格子开始，在这个格子中填尽可能大的数，划去饱和行(列)，在剩下的格子中选取运价取最小值的格子，对其赋值，依次划去饱和行(列)。表上作业法比较一下上面两种方法初始基本可行解所对应的目标函数值：西北角法：f1=135最小元素法：f2=86由此可以看出，采用最小元素法，更接近最优目标函数值，收敛速度更快。注:在应用西北角或最小

7、元素法时，应遵循：除最后一个元素外，填一个数只划掉一行(或一列)。当填一个数后，如果所在行和列同时饱和，也只划掉一行(或一列)，只是接着填下一个数时，要在没划掉的饱和行(饱和列)上的某个没划过的空格子中，填上一个数字0之后，再划去该行(该列)。表上作业法这个0不同于其他空格，表明该变量为基变量，是起占位子作用的，表明当前基本可行解是退化的(某个基变量取值为0)。其占位子是为了保证基变量的个数为m+n-1个。如下例所示：可以证明：用西北角法或最小元素法得到的解确为基本可行解，只需证明填数字的格子为m+n-1个，并且这m+n-1个格子不构成闭回路即可。（可由

8、反证法证明）表上作业法(3)Vogel法最小元素法的缺点是：为了节省一处的费用，