下载文档原格式
运筹学运输问题,表上作业法运筹学李细霞 2013物流工程1班 2014~2015学年第二学期运筹学运输问题,表上作业法课程主要内容绪论线性规划及单纯形法对偶理论与灵敏度分析目标规划整数规划运输问题动态规划图与网络运筹学运输问题,表上作业法第三章运输问题Transportation problem运筹学运输问题,表上作业法学习目标什么是运输问题？复杂运输问题如何解决运输问题？运筹学运输问题,表上作业法用单纯形法求解线性规划问题的步骤基本可行解基变换初始解最优性检验调整检验数18运筹学运输问题,表上作业法表上作业法单纯形法在求解运输问题时的一种简化方法运筹学运输问题,表上作业法表上作业法步骤1.西北角法 2.最小元素法3.伏格尔法闭回路法初始方案最优性检验方案调整1.闭回路法2.位势法20运筹学运输问题,表上作业法B1 A1 A2 A3 销量B2B3B4 10 8 5 6产量 7 4 9总产=总销31 7 311 94 632 10 5运筹学运输问题,表上作业法最小元素法西北角法初始方案的确定伏格尔法运筹学运输问题,表上作业法西北角法B1 A1 A2 A3 销量3 4有何疑问？B2 4 2B3B4产量32 3 67 4 93656Z cij xij 3 3 11 4 9 2 2 2 10 3 5 6 108i 1 j 123 运筹学运输问题,表上作业法西北角法的优劣？太简单咯！最优解有点望尘莫及呢24。
运筹学运输问题的表上作业1. 引言运输问题是运筹学中的一个重要问题，通过合理的分配资源和规划运输路径，可以最大限度地降低物流成本、提高运输效率。
在实际应用中，我们经常需要将运输问题转化为线性规划模型，并采用表格形式进行求解。
本文将详细介绍运筹学运输问题的表上作业，包括问题背景、模型建立、求解方法以及实际应用。
2. 问题背景假设某公司有m 个供应地点和n 个需求地点，需要将某种物品从供应地点运输到需求地点。
每个供应地点的供应量和每个需求地点的需求量已知，并且每单位物品的运输成本也已知。
我们的目标是确定每个供应地点向每个需求地点运输的数量，使得总运输成本最小。
3. 模型建立为了建立运输问题的数学模型，我们需要引入一些符号和变量。
3.1 符号说明• X ij : 表示从供应地点i 运输到需求地点j 的数量• c ij : 表示从供应地点i 运输到需求地点j 的单位运输成本• s i : 表示供应地点i 的供应量• d j : 表示需求地点j 的需求量3.2 目标函数我们的目标是最小化总运输成本，即最小化Z =∑∑c ij n j=1m i=1X ij 。
3.3 约束条件1. 每个供应地点运输的物品数量不能超过其供应量，即∑X ij n j=1≤s i , ∀i =1,2,…,m 。
2. 每个需求地点运输的物品数量必须满足其需求量，即∑X ij m i=1≥d j , ∀j =1,2,…,n 。
3. 非负约束条件，即X ij ≥0, ∀i =1,2,…,m; ∀j =1,2,…,n 。
4. 求解方法运输问题可以通过线性规划进行求解，常用的方法有西北角法、最小元素法、Vogel 法等。
4.1 西北角法西北角法是一种直观且容易理解的方法。
其步骤如下：1. 从表格的西北角开始，选择供应量最大的供应地点和需求量最大的需求地点交叉处为基本可行解。
2. 根据基本可行解，确定每个供应地点和需求地点的剩余供应量和需求量。
第三讲运输运输问题的表上作业法 1.表上作业法的基本思想第三讲运输运输问题的表上作业法经济管理学院王垚经济管理学院王垚1.表上作业法的基本思想经济管理学院王垚经济管理学院王垚先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。
经济管理学院王垚经济管理学院王垚确定初始方案( 初始基本可行解)改进调整（换基迭代）否判定是否最优？是结束图运输问题求解思路图经济管理学院王垚经济管理学院王垚2.初始方案的确定经济管理学院王垚经济管理学院王垚（1）作业表（产销平衡表）经济管理学院王垚经济管理学院王垚作业表（产销平衡表）初始方案就是初始基本可行解。
将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”（产销平衡表）。
经济管理学院王垚经济管理学院王垚调销地运量产地B1B2产量9><>A1 c11 X11c12 X12c13 X13<>a1<>A2c21 X21c22 X22c23 X23<>a2销量b1b2b3运输问题作业表（产销平衡表）经济管理学院王垚经济管理学院王垚其中：xij是决策变量，表示待确定的从第i个产地到第j个销地的调运量cij为从第i个产地到第j个销地的单位运价或运距。
经济管理学院王垚经济管理学院王垚确定初始方案的步骤：Step1：选择一个xij，令xij= min{ai，bj}=将具体数值填入xij在表中的位置；经济管理学院王垚经济管理学院王垚Step2：调整产销剩余数量从ai和bj中分别减去xij的值：若ai-xij=0，则划去产地Ai所在的行，即该产地产量已全部运出无剩余，而销地Bj尚有需求缺口bj-ai若bj-xij =0，则划去销地Bj所在的列，说明该销地需求已得到满足，而产地Ai尚有存余量ai-bj；经济管理学院王垚经济管理学院王垚Step3：当作业表中所有的行或列均被划去说明所有的产量均已运到各个销地，需求全部满足，xij的取值构成初始方案。
运筹学课程设计报告书---运输问题的表上作业法运筹学课程设计报告书专业班级学号姓名LMZZ日期2011.09.01设计题目：运输问题的表上作业法设计方案：运输问题是一种应用广泛的网络最优化模型，该问题的主要目的是为物资调运、车辆高度选择最经济的运输路线。
有些问题，如m 台机床加工零件问题、工厂合理布局问题，虽要求与提法不同，经适当变化也可以使用本模型求得最佳方案。
运输问题的一般提法：某种物资有m 个产地Ai ，产量是ai （i ＝1，2,…,m ），有m 个销售地Bi ，销量(需求量)是bj(j=1,2,…,m)。
若从Ai 运到Bi 单位运价为dij(i=1,2,…,m;j=1,2,…,m),又假设产销平衡，即∑∑===m i n j j ib a 11问如何安排运输可使总运费最小？若用x ij (i=1,2,…,m;j=1,2,…,n)表示由A i 运到B j 的运输量，则平衡运输问题可写出以下线性规划模型：∑∑===m i n j ij ij x d Z 11min约束条件==≥====∑∑==),...,2,1;...,2,1(0)...,2,1()...,2,1(11n j m i x n j b x m i a x ij m i j ij n j i ij表上作业法原理同于单纯形法，首先给出一个初始的调运方案(实际上是初始基本可行解)，求出各非基变量的检验数去判定当前解是否为最优解，若不是则进行方案调整(即从一个基本可行解转换成另一个基本可行解)，再判定是否为最优解，重复以上步骤，直到获得最优解为止。
这些步骤在表上进行十分方便。
操作过程在表上进行方案实施：通过运输问题在C++程序中的运用，从而实现方案的最优。
程序主要分两部：（1）求解，（2）最优解判断结果与结论：程序运行过程中，依次输入所需要的运价，产量，销量等数据，单击回车可以再次现实所需数据，按任意键可以运行至求出初始可行解并显示，再次按任意键程序进行最优解的判断，并求出最优解，显示在程序页面上，从而可以得到该运输问题的最优方案。
