第四章运输问题 教学目的与要求:要求学生掌握运输问题 模型的建立及求解运输问题最优解的表上 作业法 教学重点:表上作业法包括伏格尔法求基 可行解,位势法进行最优性检验,闭路法 进行基变换
第四章 运输问题 • 教学目的与要求：要求学生掌握运输问题 模型的建立及求解运输问题最优解的表上 作业法。 • 教学重点：表上作业法包括伏格尔法求基 可行解，位势法进行最优性检验，闭路法 进行基变换
例:某种物资从两个供应地A1,A2运往三个需求地B1 B2,B3。各供应地的供应量、各需求地的需求量、每 个供应地到每个需求地每吨物资的运输价格如下表: 运价(元吨)B1 B 供应量(吨) 2 3 B58 35 7 25 需求量(吨) 10 30 20 60 求总运费最低的运输方案
例：某种物资从两个供应地A1，A2运往三个需求地B1， B2，B3。各供应地的供应量、各需求地的需求量、每 个供应地到每个需求地每吨物资的运输价格如下表： 运价（元/吨） B1 B2 B3 供应量（吨） A1 2 3 5 35 A2 4 7 8 25 需求量（吨） 10 30 20 60 求总运费最低的运输方案
口运输问题的表示 网络图、线性规划模型、运输表 口初始基可行解 西北角法、最小元素法、伏格尔法 口非基变量的检验数 闭回路法、对偶变量法 口确定进基变量和离基变量
p运输问题的表示 网络图、线性规划模型、运输表 p初始基可行解 西北角法、最小元素法、伏格尔法 p非基变量的检验数 闭回路法、对偶变量法 p确定进基变量和离基变量
运输问题的网络图表个供地、n个需求地 小 供应量供应地运价需求地需求量 10吨 35吨 A 3 5 30吨 25吨 A 20吨 返回 总供应量60吨供求平衡的运输问题总需求量60吨
运输问题的网络图表 示 供应量 供应地 运价 需求地 需求量 总供应量60吨 供求平衡的运输问题 总需求量60吨 返回 A1 A2 B3 B2 B1 35吨 25吨 10吨 30吨 20吨 2 3 5 4 7 8 m个供地、n个需求地
设从两个供应地到三个需求地的运量(吨)如下表: B B B A X X 3 A X minz=2x11+3X12+5X13+4X21+7X2+8X2 23 st.x11+x12+x13 =35供应地A1 21^2223 =25供应地A2 X x21 10需求地B1 X 12 X22 =30需求地B2 13 +x23=20需求地B3 X132X1232X13,X21,X22x2320
设从两个供应地到三个需求地的运量（吨）如下表： B1 B2 B3 A1 x11 x12 x13 A2 x21 x22 x23 • min z=2x11+3x12+5x13+4x21+7x22+8x23 • s.t. x11+x12+x13 =35 供应地A1 • x21+x22+x23 =25 供应地A2 • x11 +x21 =10 需求地B1 • x12 +x22 =30 需求地B2 • x13 +x23 =20 需求地B3 • x11 , x12 , x13 , x21 , x22 , x23≥0
运输问题线性规划模型 minz=2X1+3x12+5X13+4x21+7x2+8x23 s.t. Xu+X12+X 35 x21+x22+X23=25 供应地约束 10 2 +x22 30 需求地约束 +x23=20 12X12,X13,X21,X2X23≥0 由于前m个供应地约束和后n个需求地约束是线性相关的 ,因此运输问题系数矩阵的秩<m+η。可以证明,运输问题系 数矩阵的秩为m+n-1。即运输问题有m+n-1个基变量,mn (m+n-1)个非基变量。例如以上问题m=2,n=3,基变量为2 3-1=4个,非基变量为6-4=2个。 返回
x , x , x , x , x , x 0 x x 20 x x 30 x x 10 x x x 25 s.t. x x x 35 min z 2x 3x 5x 4x 7x 8x 11 12 13 21 22 23 13 23 12 22 11 21 21 22 23 11 12 13 11 12 13 21 22 23 运输问题线性规划模型 供 应 地 约 束 需 求 地 约 束 由于前m个供应地约束和后n个需求地约束是线性相关的 ，因此运输问题系数矩阵的秩<m+n。可以证明，运输问题系 数矩阵的秩为m+n-1。即运输问题有m+n-1个基变量，mn- (m+n-1)个非基变量。例如以上问题m=2，n=3，基变量为2 ＋3－1＝4个，非基变量为6－4＝2个。 返回
m行 n亻 大型稀疏矩阵 第i行运输问题的基可行解包 含m+n-1个基变量 第m+j行 返回
1 1 1 ... ... ... 1 1 1 1 ... 1 ... 1 ... 1 1 1 ... 1 m行 n行 大型稀疏矩阵 0 ...1 ...0 1 ...0 ij p 第i行 第m+j行 运输问题的基可行解包 含m+n-1个基变量 返回
运输问题的表格表示 销地|B1 B2 B3 B4 产地 A1 3 3 107 A2 9 2 84 A3 14 10 59 销量3 6 5 6 返回
运输问题的表格表示 返回 销地 产地 B1 B2 B3 B4 产量 A1 7 A2 4 A3 9 销量 3 6 5 6 3 11 3 10 8 10 5 1 9 2 7 4
运输问题基的表示 ·m个供应地、n个需求地的运输问题,任何 个基要满足以下三个条件: 基变量的个数为m+n-1 ·基变量不能形成闭回路 ·运输表的每一行和每一列中至少有一个基 变量
• m个供应地、n个需求地的运输问题，任何 一个基要满足以下三个条件： • 基变量的个数为m+n-1； • 基变量不能形成闭回路； • 运输表的每一行和每一列中至少有一个基 变量
·闭回路:凡是能排列成 Xi1x×i2,X12,Xi3,Xijs,Xis1或 Xi1X121×122X2is,×is的变量 集合,若用一条封闭折线将它们连接起形 成的图形。 ·各变量成为闭回路的顶点。两相邻顶点及 最后顶点与第一个顶点的连线称为边 每一边只包含2个顶点 ·转弯只能直角转弯
• 闭回路：凡是能排列成 Xi1 j1 ,Xi1 j2 ,Xi2 j2 ,Xi2 j3 ,……Xis js ,Xis j1 ,或 Xi1 j1 ,Xi2 j1 ,Xi2 j2 ,Xi3 j2……Xis js ,Xi1 js 的变量 集合，若用一条封闭折线将它们连接起形 成的图形。 • 各变量成为闭回路的顶点。两相邻顶点及 最后顶点与第一个顶点的连线称为边。 • 每一边只包含2个顶点 • 转弯只能直角转弯