运输问题线性规划模型 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个顶点 • 转弯只能直角转弯