线性规划 Linear Programming(LP) 特殊线性规划——运输问题 运输问题模型分析 般形式 某种物资有m个产地A1,产量(供应量)是a1(i=1,2,…,m),有n 个销地B;销量(需求量)是b;(j=1,2,…,n)。从运到的单位运价为 c;(i=1,2,…,m;j=1,2,…,n),如何安排运输可使总运费最小? 产大于销 ∑a;≥∑b 销大于产 ∑a;≤∑b MinZ=ΣΣC11 Minz=Σ∑C141 ∑x;≤a;(i=1,2, ∑x;=a;(i=1,2, (j=1,2,…,n) Σx1;≤b;(j=1,2,…,n) x;;≥0(1=1,2,…,m; 1≥0(i=1,2,…,m; J=1 n j=1,2, 6
6 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 运输问题模型分析 一般形式： 某种物资有m个产地Ai，产量（供应量）是ai（i=1，2，…，m），有n 个销地Bj，销量（需求量）是bj（j=1，2，…，n）。从运到的单位运价为 cij（i=1，2，…，m；j=1，2，…，n），如何安排运输可使总运费最小？ 产大于销—— ai ≥ bj Min Z= CijXij xij≤ai （i=1，2，…，m） xij =bj （j=1，2，…，n） xij≥0 （i=1，2，…，m； j=1，2，…，n） 销大于产—— ai ≤ bj Min Z= CijXij xij=ai （i=1，2，…，m） xij≤bj （j=1，2，…，n） xij≥0 （i=1，2，…，m； j=1，2，…，n）
线性规划 Linear Programming(LP) 特殊线性规划——运输问题 产销平衡 ∑a;=∑b 注意!这种模型具有特殊的形式:所有决策变量的约束条件, 其系数均等于1;而且,每个决策变量仅出现于两个约束条件之中。 这些特性表明,解这类线性最优化模型的单纯形法中有一种特殊的 方法可用来解这个问题—这是解这类模型的特别有效的一种方法。 而且上述特性还表明,可以给这类线性最优化模型以一种象网络模 型式的形象化的说明。 Minz=2ΣC11 2x1=81(i=1,2,…m) ∑x ij=b;(j=1,2,…,n) xi;≥0(i=1,2,…,m;j1,2,…,n)
7 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 产销平衡—— ai = bj 注意！这种模型具有特殊的形式：所有决策变量的约束条件， 其系数均等于1；而且，每个决策变量仅出现于两个约束条件之中。 这些特性表明，解这类线性最优化模型的单纯形法中有一种特殊的 方法可用来解这个问题——这是解这类模型的特别有效的一种方法。 而且上述特性还表明，可以给这类线性最优化模型以一种象网络模 型式的形象化的说明。 Min Z= CijXij xij =ai （i=1，2，…，m） xij =bj （j=1，2，…，n） xij≥0 （i=1，2，…，m；j=1，2，…，n）
线性规划 Linear Programming(LP) 特殊线性规划——运输问题 模型特点 1、运输问题有有限最优解 2、运输问题约束条件系数矩阵 A (m+n)×(mn) 8
8 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 模型特点 1、运输问题有有限最优解 2、运输问题约束条件系数矩阵 A = 1 1 … 1 1 1 1 … 1 …………………………………………………… 1 1 … 1 1 1 … 1 1 1 1 …………………………………………………… 1 1 1 （m+n）×（mn）
线性规划 Linear Programming(LP) 特殊线性规划——运输问题 产销平衡运输问题的对偶问题 (P)Minz=ΣΣC11; ∑x;;=a;(i=1,2,…,m) Σx1;=b;(j=1,2, x;≥0(i=1,2,…,m;j1,2,…,n) (D) Max w=2a; U;+2b, Vi u1+V≥Cj U,V,自由变量 (i=1,2 =1,2,∴,n) 9
9 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 产销平衡运输问题的对偶问题 （P） Min Z= CijXij xij =ai （i=1，2，…，m） xij =bj （j=1，2，…，n） xij≥0 （i=1，2，…，m；j=1，2，…，n） （D） Max W = ∑ai Ui + ∑bj Vj Ui + Vj ≥ Cij Ui ， Vj ，自由变量 （i = 1，2，… ，m ；j = 1，2，… ，n ）
线性规划 Linear Programming(LP) 特殊线性规划——运输问题 运输问题的求解方法 求解此问题的一个十分有效的方法是表上作业法: (1)产销平衡问题—总产量等于总销量的运输问题 a、建立作业表 b、确定初始调运方案(最小元素法) c、现行方案的最优性检验(位势法) d、现行方案的调整(闭回路法) 10
10 线性规划 Linear Programming（LP） 特殊线性规划——运输问题 运输问题的求解方法 求解此问题的一个十分有效的方法是表上作业法： （1）产销平衡问题——总产量等于总销量的运输问题 a、建立作业表 b、确定初始调运方案（最小元素法） c、现行方案的最优性检验（位势法） d、现行方案的调整（闭回路法）