搜索
课程名称：运筹学姓名：赵希学号：14120201261运输问题摘要：运输问题（transportationproblem）一般是研究把某种商品从若干个产地运至若干个销地而使总运费最小的一类问题。然而从更广义上讲，运输问题是具有一定模型特征的线性规划问题。它不仅可以用来求解商品的调运问题，还可以解决诸多非商品调运问题。运输问题是一种特殊的线性规划问题，由于其技术系数矩阵具有特殊的结构，这就有可能找到比一般单纯形法更简便高效的求解方法，这正是单独研究运输问题的目的所在。引言：物流的运输则专指“物”的载运及输送。它是在不同地域范围间（如两个城市.两个工厂之间，或一大企业内相距较远的两车之间），以改变“物”的空间位置为目的的活动，是对“物”进行的空间位移。运输一般分为运输和配送。关于运输和配送的区分，有许多不同的观点，可以这样来说，所有物品的移动都是运输，而配送则专指短距离、小批量的运输。因此，可以说运输是指整体，配送则是指其中的一部分，而且配送的侧重点在于一个''配''字，它的主要意义也体现在''配''字上；而''送''是为最终实现资源配置的''配''而服务的。运输功能要素。包括供应及销售物流中的车、船、飞机等方式的运输，生产物流中的管道、传送带等方式的运输。运输是指把人.财.物由一个地方转移到另外一个地方的过程.运输又被认为是国民经济的根本．运输的主要工具有自行车.板车.三轮车.摩托车.汽车.火车.飞机.轮船.宇宙飞船.火箭.等等运输按服务对象不同分为客运和货运公共运输,泛指所有收费提供交通服务的运输方式。轿车托运:(轿车运输)是指将汽车做为商品出厂后,通过大型汽车运输工具,到达指定地方的运输方式/CN课程名称：运筹学姓名：赵希学号：14120201262运输运价的构成发到基价，运行基价构成，货物运输杂费零担货物年车运价=每吨运价×计费重量整车货物每吨运价=发到基价+运行基价×运价里程集装箱货物每箱运价=发到基价+运行基价×运价里程运输问题的数学模型某公司经营某种产品，该公司下设A、B、C三个生产厂，甲、乙、丙、丁四个销售点。公司每天把三个工厂生产的产品分别运往四个销售点，由于各工厂到各销售点的路程不同，所以单位产品的运费也就不同案。各工厂每日的产量、各销售点每日的销量，以及从各工厂到各销售点单位产品的运价如表4-1所示。问该公司应如何调运产品，在满足各销售点需要的前提下，使总运费最小。表4-1甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656设代表从第个产地到第个销地的运输量（；），用代表从第个产地到第个销地的运价，于是可构造如下数学模型：（；运出的商品总量等于其产量）（；运来的商品总量等于其销量）通过该引例的数学模型，我们可以得出运输问题是一种特殊的线性规划问题的结论，其特殊性就在于技术系数矩阵是由“1”和“0”两个元素构成的。课程名称：运筹学姓名：赵希学号：14120201263将该引例的数学模型做一般性推广，即可得到有个产地、个销地的运输问题的一般模型。注意：在此仅限于探讨总产量等于总销量的产销平衡运输问题，而产销不平衡运输问题将在本章的后续内容中探讨。（；运出的商品总量等于其产量）（；运来的商品总量等于其销量）供应约束确保从任何一个产地运出的商品等于其产量，需求约束保证运至任何一个销地的商品等于其需求。除非负约束外，运输问题约束条件的个数是产地与销地的数量和，即；而决策变量个数是二者的积，即。由于在这个约束条件中，隐含着一个总产量等于总销量的关系式，所以相互独立的约束条件的个数是个。运输问题的求解：运输问题的求解采用表上作业法，该方法是单纯形法求解运输问题的一种特定形式，其实质是单纯形法。既然表上作业法是一种特定形式的单纯形法，它自然与单纯形法有着完全相同的解题步骤，所不同的只是完成各步采用的具体形式。表上作业法的基本步骤可参照单纯形法归纳如下：1．找出初始基可行解：即要在阶产销平衡表上给出“”个数字格（基变量）；2．求各非基变量（空格）的检验数，判断当前的基可行解是否是最优解，如已得到最优解，则停止计算，否则转到下一步；3．确定入基变量，若，那么选取为入基变量；4．确定出基变量，找出入基变量的闭合回路，在闭合回路上最大限度地增加入基变量的值，那么闭合回路上首先减少为“0”的基变量即为出基变量；5．在表上用闭合回路法调整运输方案；6．重复2、3、4、5步骤，直到得到最优解。课程名称：运筹学姓名：赵希学号：14120201264确定初始基可行解与一般的线性规划不同，产销平衡的运输问题一定具有可行解（同时也一定存在最优解），这一点是显然的。确定初始基可行解的方法有很多，下面是最小元素法。最小元素法最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止。下面就用例4-1说明最小元素法的应用。第一步：从表4-1中找出最小运价“1”，这表示先将B生产的产品供应给甲。由于B每天生产4个单位产品，甲每天需求3个单位产品，即B每天生产的产品除满足甲的全部需求外，还可多余1个单位产品。在（B，甲）的交叉格处填上“3”，形成表4-2；将运价表的甲列运价划去得表4-3，划去甲列表明甲的需求已经得到满足。表4-2甲乙丙丁产量（ai）A7B34C9销量（bj）3656表4-3甲乙丙丁A311310B1928C74105第二步：在表4-3的未被划掉的元素中再找出最小运价“2”，最小运价所确定的供应关系为（B，丙），即将B余下的1个单位产品供应给丙，表4-2转换成表4-4。划去B行的运价，划去B行表明B所生产的产品已全部运出，表4-3转换成表4-5。表4-4甲乙丙丁产量（ai）A7B314C9销量（bj）3656课程名称：运筹学姓名：赵希学号：14120201265第三步：在表4-5中再找出最小运价“3”，这样一步步地进行下去，直到单位运价表上的所有元素均被划去为止。最后在产销平衡表上得到一个调运方案，见表4-6。这一方案的总运费为86个单位。表4-5甲乙丙丁A311310B1928C74105表4-6甲乙丙丁产量（ai）A437B314C639销量（bj）3656最小元素法各步在运价表中划掉的行或列是需求得到满足的列或产品被调空的行。一般情况下，每填入一个数相应地划掉一行或一列，这样最终将得到一个具有“”个数字格（基变量）的初始基可行解。然而，问题并非总是如此，有时也会出现这样的情况：在供需关系格（）处填入一数字，刚好使第个产地的产品调空，同时也使第个销地的需求得到满足。按照前述的处理方法，此时需要在运价表上相应地划去第行和第列。填入一数字同时划去了一行和一列，如果不加入任何补救措施的话，那么最终必然无法得到一个具有“”个数字格（基变量）的初始基可行解。为了使在产销平衡表上有“”个数字格，这时需要在第行或第列此前未被划掉的任意一个空格上填一个“0”。填“0”格虽然所反映的运输量同空格没有什么不同；但它所对应的变量却是基变量，而空格所对应的变量是非基变量。表4-7甲乙丙丁产量（ai）课程名称：运筹学姓名：赵希学号：14120201266A3113104B19284C7410512销量（bj）3656将例4-1的各工厂的产量做适当调整（调整结果见表4-7），就会出现此类特殊情况。第一步在（B，甲）处填入“3”，划去甲列运价；第二步在（B，丙）处填入“1”，划去B行运价，此二步的结果见表4-8和表4-9。表4-8甲乙丙丁产量（ai）A4B314C12销量（bj）3656表4-9甲乙丙丁产量（ai）A3113104B19284C7410512销量（bj）3656表4-10甲乙丙丁产量（ai）A044B314C12销量（bj）3656表4-11甲乙丙丁产量（ai）课程名称：运筹学姓名：赵希学号：14120201267A3113104B19284C7410512销量（bj）3656表4-9中剩下的最小元素为“3”，其对应产地A的产量是4，销地丙的剩余需要量也是4，在格（A，丙）中填入“4”，需同时划去A行和丙列。在填入“4”之前A行和丙列中除了（A，丙）之外，还有（A，乙）、（A，丁）和（C，丙）三个空格未被划去；因此，可以在（A，乙）、（A，丁）和（C，丙）任选一格填加一个“0”，不妨选择（A，乙），结果可见表4-10和表4-11。注意这个“0”是不能填入（A，甲）或（B，丙）的，因为在填入“4”之前它们已经被划去了。实例分析：有三个化肥厂供应四个地区的化肥需求，假定等量化肥在这些地区的使用效果相同。各化肥厂年产量、各地区年需要量及从各化肥厂到各地区运送单位化肥的单位运价如表38所示，试求出总的运费最节省的化肥调拨方案。表38（单位：万吨）地区1地区2地区3地区4年产量化肥厂A1613221750化肥厂B1413191560化肥厂C192023M50年需要量最低需求3070010最高需求507030不限这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，除满足地区1、地区2和地区3的最低需求外，地区4每年最多能分配到60（）万吨，这样其不限的最高需求可等价认为是60万吨。按最高需求分析，总需求为210万吨，大于总产量160万吨，将此问题定义为销大于产的运输问题。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，令其年产量为50（）万吨。各地区的需要量包含最低和最高两部分：如地区1，其中30万吨是最低需求，故这部分需求不能由假想的化肥厂D来供给，因此相应的运价定义为任意大正数M；而另一部分20万吨满足与否都是可以的，因此可以由假想化肥厂D来供给，课程名称：运筹学姓名：赵希学号：14120201268按前面讲的，令相应运价为“0”。凡是需求分两种情况的地区，实际上可按照两个地区来看待，这样可以将表4-38所示的运输问题转换为表39所示的运输问题。表39（单位：万吨）地区1地区1地区2地区3地区4地区4年产量化肥厂A16161322171750化肥厂B14141319151560化肥厂C19192023MM50化肥厂DM0M0M050年需要量302070301050这个问题的最优方案，如表40所示。表40（单位：万吨）地区1地区1地区2地区3地区4地区4年产量化肥厂A5050化肥厂B20103060化肥厂C3020050化肥厂D302050年需要量302070301050结论：运输问题（transportationproblem）一般是研究把某种商品从若干个产地运至若干个销地而使总运费最小的一类问题。然而从更广义上讲，运输问题是具有一定模型特征的线性规划问题。它不仅可以用来求解商品的调运问题，还可以解决诸多非商品调运问题。运输问题是一种特殊的线性规划问题，由于其技术系数矩阵具有特殊的结构，这就有可能找到比一般单纯形法更简便高效的求解方法，这正是单独研究运输问题的目的所在，运用此类方法，可以大大减少成本，提高运输效率。