1运输问题模型及有关概A 是 基本可行解 是否最优解 结束 否 换基 图4-1运输问题的求解思路
17 1.运输问题模型及有关概念 基本可行解 是否最优解 结束 换基 是 否 图4-1 运输问题的求解思路
1运输问题模型及有关概A 运输问题求解的有关概念 考慮产销平衡问题。由于我们关心的 量均在表43与表44中,因此考虑把表43 与表4-4合成一个表,如下表4-5 表4-5运输问题求解作业数据表 (下页)
18 运输问题求解的有关概念 考虑产销平衡问题，由于我们关心的 量均在表4-3与表4-4中，因此考虑把表4-3 与表4-4合成一个表, 如下表4-5 表4-5 运输问题求解作业数据表 (下页） 1.运输问题模型及有关概念
1运输问题模型及有关概A 销地 B B2 B 产量 产地 11 In mn 销量 b
19 1.运输问题模型及有关概念 销地 产地 B1 B2 … Bn 产量 A1 c11 x11 c12 x12 … c1n x1n a1 A2 c21 x21 c22 x22 … c2n x2n a2 ┇ ┇ ┇ ┇ ┇ ┇ Am cm1 xm1 cm2 xm2 … cmn xmn am 销量 b1 b2 … bn
1运输问题模型及有关概A 运输冋题基变量的 特点 远输问题的基变量共有m+n-1 个,A的秩为m+n-1。 运输问题的m+n-1个变量构成基 变量的充分必要条件是不含闭回路。 重要概念:闭回路、闭回路的顶点
20 运输问题的基变量共有 m + n -1 个，A的秩为 m + n -1。 运输问题的 m + n -1 个变量构成基 变量的充分必要条件是不含闭回路。 重要概念: 闭回路、闭回路的顶点 运输问题基变量的 特点 1.运输问题模型及有关概念
1运输问题模型及有关概A 为了说明这个特征,我们不加证明的给 出一些概念和结论。下面的讨论建立在表4-5 中决策变量格的基础上。 定义4.1在表4-5的决策变量格中,凡是 能够排列成下列形式的 ab ,ac y 5b(4-7) 式 b b at (4-8) 其中,a,d,,S各不相同;b,C,,t各不 相同。我们称之为变量集合的一个闭回路 并将式(4-7)、式(4-8)中的变量称为这 个闭回路的顶点
21 定义4.1 在表4-5的决策变量格中，凡是 能够排列成下列形式的 xab ,xac ,xdc ,xde ,…,xst ,xsb (4-7) 或 xab ,xcb ,xcd ,xed ,…,xst ,xat (4-8) 其中，a,d,…,s 各不相同；b,c,…,t 各不 相同，我们称之为变量集合的一个闭回路， 并将式（4-7）、式（4-8）中的变量称为这 个闭回路的顶点。 为了说明这个特征，我们不加证明的给 出一些概念和结论。下面的讨论建立在表4-5 中决策变量格的基础上。 1.运输问题模型及有关概念