一、运输规划问题

---

运输规划问题 :

二、找初始基可行解

---

使用最小元素法求得的初始基可行解 :

	${\mathrm{B}}_1$	${\mathrm{B}}_2$	${\mathrm{B}}_3$	${\mathrm{B}}_4$	产量
${\mathrm{A}}_1$	$3$	$11$	$3$ , $4$	$10$ , $3$	$7$
${\mathrm{A}}_2$	$1$ , $3$	$9$	$2$ , $1$	$8$	$4$
${\mathrm{A}}_3$	$7$	$4$ , $6$	$10$	$5$ , $3$	$9$
销量	$3$	$6$	$5$	$6$

使用 最小元素法, 得到初始基可行解 : $\{\begin{array}{l}{\mathrm{x}}_{13}=4\\ \\ {\mathrm{x}}_{14}=3\\ \\ {\mathrm{x}}_{21}=3\\ \\ {\mathrm{x}}_{23}=1\\ \\ {\mathrm{x}}_{32}=6\\ \\ {\mathrm{x}}_{34}=3\end{array}$

三、计算检验数

---

计算检验数 :

使用闭回路法 , 逐个计算每个非基变量的检验数 ,

以非基变量为起点 , 出发的格子使用加号 $+$ , 第二个格子使用减号 $-$ , 之后的歌词依次使用 加号减号交替 $+-$ 符号 ;

计算上述闭回路的运费代数和 ,

如果代数和 大于等于 $0$ , 说明当前的非基变量格子取 $0$ 就是 最优选择 ;

如果代数和 小于 $0$ , 说明当前的非基变量格子取 $0$ 不是最优选择 ;

这里以计算 ${\sigma }_{24}$ 检验数为例 :

${\mathrm{A}}_{24}+$ , ${\mathrm{A}}_{23}-$ , ${\mathrm{A}}_{13}+$ , ${\mathrm{A}}_{14}-$

${\sigma }_{24}=(1\times 8)-(1\times 2)+(1\times 3)-(1\times 10)=-1$

检验数小于 $0$ ;

计算出的 非基变量 检验数使用 蓝色括号字体 写在表格中 :

	${\mathrm{B}}_1$	${\mathrm{B}}_2$	${\mathrm{B}}_3$	${\mathrm{B}}_4$	产量
${\mathrm{A}}_1$	$3$ , $(1)$	$11$ , $(2)$	$3$ , $4$	$10$ , $3$	$7$
${\mathrm{A}}_2$	$1$ , $3$	$9$ , $(1)$	$2$ , $1$	$8$ , $(-1)$	$4$
${\mathrm{A}}_3$	$7$ , $(10)$	$4$ , $6$	$10$ , $(12)$	$5$ , $3$	$9$
销量	$3$	$6$	$5$	$6$

四、调整运量 ( 换基 )

---

上述检验数中 , ${\sigma }_{24}$ 为负数 , 需要进行换基 , 该非基变量就是入基变量 ;

该检验数的闭合回路如下 : ${\mathrm{A}}_{24}+$ , ${\mathrm{A}}_{23}-$ , ${\mathrm{A}}_{13}+$ , ${\mathrm{A}}_{14}-$ ;

在 $-$ 符号的基变量中挑选一个最小的 , 作为出基变量 ;

换基之后的结果如下 :

经过上述计算后的运费表格如下 :

	${\mathrm{B}}_1$	${\mathrm{B}}_2$	${\mathrm{B}}_3$	${\mathrm{B}}_4$	产量
${\mathrm{A}}_1$	$3$	$11$	$3$ , $5$	$10$ , $2$	$7$
${\mathrm{A}}_2$	$1$ , $3$	$9$	$2$	$8$ , $1$	$4$
${\mathrm{A}}_3$	$7$	$4$ , $6$	$10$	$5$ , $3$	$9$
销量	$3$	$6$	$5$	$6$

计算当前的总运费 :

$(3\times 5)+(10\times 2)+(1\times 3)+(8\times 1)+(4\times 6)+(3\times 5)=85$

计算检验数验证 , 是最优解 ;