[管理学]第3章 运输问题.pptVIP

* 管理运筹学 马越峰 * 管理运筹学 马越峰 第三章 运输问题 3.1. 运输问题及其数学模型 3.2. 运输问题的表上作业法 3.3. 运输问题的进一步讨论 3.4. 应用举例 3.1 运输问题及其数学模型 运输问题解决把某种产品从若干产地调运 到若干个销地,在每个产地的供应量与每个销地的需求量已知,并知道各地之间的调运单价的前提下,如何确定一个使得总的运输费用最小的方案. 第三章 运输问题 例.某公司从两个产地A1,A2将货物运往三个销地B1,B2 B3,各产地的产量及各销地的销量和各产地运往各销 地的每件物品的运费如下表,问如何调运,使得总运输 费用最小? 200 150 150 销量 300 5 5 6 A2 200 6 4 6 A1 产量 (件) B3 B2 B1 运费 销地 单价 产地 设xij表示从产地Ai调运到Bj的运输量(i=1,2;j=1,2,3) Min f=6x11+ 4x12+ 6x13+ 6x21+5x22+ 5x23 x11+ x12+ x13=200 x21+ x22+ x23=300 x11+ x21=150 x12+ x22=150 x13+ x23=200 xij ≥0 设Xij表示从产地Ai运到销地Bj运输量,则产销平衡 的运输问题的线性规划模型如下: 目标函数: minf=∑∑cijxij ∑xij=ai , i=1,2, …m(关于产量) ∑xij=bj j=1,2, …n(关于销量) xij≥0 3.2. 运输问题的表上作业法 找出初始基本可行解 对于有m个产地n个销地的产销平衡问题,其 系数矩阵的秩为m+n-1,即运输问题有m+n-1个 基变量,找出初始基本可行解就是在(m×n)产销 平衡表上给出m+n-1个数字格,其相应的调运量 就是基变量,格子中所填写的值即为基变量的值. 方法:最小元素法,即对单位运价最小的变量先分 配运输量. 最优解的判别 1.闭回路法 在空格的闭回路上从起点开始计算 σij=奇数角点的运价和-偶数角点的运价和 如果所有代表非基变量的空格的检验数即非基变量 的检验数都大于零,则已求得最优解 2.位势法 令基变量 非基变量 改进运输方案的办法__闭回路调整法 1.入基变量的确定 按min｛ σij＜0｝= σlk确定xlk入基,若有多个σlk 同时最小,则从中选最小运价对应的xlk入基.又若有 多个clk同时最小,则从中任选一个clk对应的xlk入基 2.出基变量的确定 在入基变量xlk的闭回路上,按t=min｛xij-｝=xpq(xij-为 偶点)确定xpq离基.同时也就确定了xpq的值t为调整量. 若有多个偶点xpq的值同时最小,则选其中最大运价所 对应的那个xpq离基,又若有多个cpq的值同时最大,则从 中任选一个cpq所对应的那个xpq离基. 3. 在入基变量xlk的闭回路上,所有偶点的值xij-都减去 调整量t得xij=xij--t,所有奇点的值xij+都加入调整量t 得xij=xij++t得一新方案. 20 20 3 6 5 6 销量 7 4 9 11 3 10 9 2 8 7 4 10 5 A1 A2 A3 产量 B1 B2 B3 B4 运 销地 价 产地 12 x33—x34—x14—x13—x33 x33 10 x31—x34—x14—x13—x23 —x21—x31 x31 -1 x24—x23—x33—x14—x24 x24 1 x22—x23—x13—x14—x34—x32—x22 x22 2 x12—x14—x34—x32—x12 x12 1 x11—x13—x23—x21—x11 x11 检验数 闭 回 路 空格 如何找多个最优方案 若最优解中非基变量的检验数为零，则 表明该问题有无穷多组