輸送問題

$x\in T(a,b)$ なら、すべての成分を足して $\sum_ia_i=\sum_{i,j}x_{ij}=\sum_jb_j$ である。逆に $S:=\sum_ia_i=\sum_jb_j$ とおく。$S=0$ なら $a=b=0$ で $x=0$ が実行可能である。$S>0$ なら $x_{ij}:=a_ib_j/S\ge0$ とおくと $\sum_jx_{ij}=a_iS/S=a_i$、$\sum_ix_{ij}=b_j$ なので実行可能である。
実行可能なとき、$x\in T(a,b)$ の各成分は $0\le x_{ij}\le a_i$ を満たすので、$T(a,b)$ は $\mathbb{R}^{mn}$ の有界な集合である。有限個の等式と不等式 $x_{ij}\ge0$ で定まるので閉集合でもあり、空でない。連続関数 $x\mapsto c\cdot x$ は空でない有界閉集合の上で最小値をとるので、最適解が存在する。$\square$

行の和と列の和の条件から $\sum_{i,j}u_ix_{ij}=\sum_iu_ia_i$、$\sum_{i,j}v_jx_{ij}=\sum_jv_jb_j$ である。これを右辺に代入すれば左辺になる。$(u,v)$ が双対実行可能なら $c_{ij}-u_i-v_j\ge0$ で $x_{ij}\ge0$ なので、右辺の各項は $0$ 以上である。$\square$

1：輸送問題を 線形計画法 の不等式標準形 (P) に書き直す。変数 $x\in\mathbb{R}^{mn}$ について
$$ \text{(P${}'$)}\qquad\text{最大化 }(-c)\cdot x\quad\text{条件 }\sum_jx_{ij}\le a_i\ (i),\quad-\sum_ix_{ij}\le-b_j\ (j),\quad x\ge0 $$
を考える。(P$'$) の実行可能解 $x$ について、$S:=\sum_ia_i=\sum_jb_j$ とおくと
$$ S=\sum_jb_j\le\sum_j\sum_ix_{ij}=\sum_i\sum_jx_{ij}\le\sum_ia_i=S $$
なので途中の不等号はすべて等号であり、各 $i$ で $\sum_jx_{ij}\le a_i$、各 $j$ で $\sum_ix_{ij}\ge b_j$ の不等式もすべて等号になる。したがって (P$'$) の実行可能解の全体はちょうど $T(a,b)$ であり、(P$'$) の最大値は輸送問題の最小値の符号を変えたものである。
(P$'$) の係数行列の列 $(i,j)$ は第 $i$ 成分が $1$、第 $m+j$ 成分が $-1$ で他が $0$ なので、線形計画法 の定義「双対問題」による (P$'$) の双対問題は、変数 $p\in\mathbb{R}^m$、$q\in\mathbb{R}^n$ について
$$ \text{(D${}'$)}\qquad\text{最小化 }\sum_ia_ip_i-\sum_jb_jq_j\quad\text{条件 }p_i-q_j\ge-c_{ij}\ (i,j),\quad p\ge0,\ q\ge0 $$
である。(P$'$) は prop-tp-feasible により実行可能であり、(D$'$) も $q=0$、$p_i:=\max\bigl(0,\max_j(-c_{ij})\bigr)$ で実行可能である。線形計画法 の定理「線形計画法の双対定理」により、(P$'$) と (D$'$) はどちらも最適解をもち、最適値は等しい。
$u:=-p$、$v:=q$ とおくと、(D$'$) の条件は $u_i+v_j\le c_{ij}$、$u\le0$、$v\ge0$ になり、目的関数は $-\bigl(\sum a_iu_i+\sum b_jv_j\bigr)$ になる。したがって、輸送問題の最小値 $\mu$ は、双対問題に符号の条件 $u\le0$、$v\ge0$ を加えた問題の最大値に等しく、その最大値は (D$'$) の最適解から得られる $(u^*,v^*)$ で達成される。一方、符号の条件のない双対実行可能な $(u,v)$ はどれも、lem-tp-gap により $\sum a_iu_i+\sum b_jv_j\le\mu$ を満たす。よって双対問題の最大値も $\mu$ で、$(u^*,v^*)$ で達成される。
2：条件を満たす $(u,v)$ があれば、lem-tp-gap の右辺は $x_{ij}>0$ の項で $c_{ij}-u_i-v_j=0$、$x_{ij}=0$ の項で $0$ なので、$c\cdot x=\sum a_iu_i+\sum b_jv_j$ である。任意の $x'\in T(a,b)$ について、弱双対性から $c\cdot x'\ge\sum a_iu_i+\sum b_jv_j=c\cdot x$ なので $x$ は最適であり、同様に $(u,v)$ も双対問題の最適解である。逆に $x$ が最適なら、1 の双対問題の最適解 $(u,v)$ について lem-tp-gap の左辺は $0$ である。右辺の各項は $0$ 以上なので、どの項も $0$ であり、$x_{ij}>0$ なら $c_{ij}=u_i+v_j$ である。$\square$

要点：森には葉があり、葉の行（または列）の成分は供給量（需要量）で決まる。その辺を除いた小さい問題に帰納法を当てる。

必要性：$\operatorname{supp}x$ が閉路 $r_{i_1}s_{j_1}r_{i_2}s_{j_2}\cdots r_{i_k}s_{j_k}r_{i_1}$（$k\ge2$、頂点は相異なる）を含むとする。$i_{k+1}:=i_1$ とし、行列 $d$ を、$(i_l,j_l)$ で $1$、$(i_{l+1},j_l)$ で $-1$（$l=1,\dots,k$）、ほかで $0$ と定める。閉路上の各行 $i_l$ には $+1$ の成分 $(i_l,j_l)$ と $-1$ の成分 $(i_l,j_{l-1})$（$j_0:=j_k$）がちょうど 1 つずつあり、各列 $j_l$ にも $+1$ の $(i_l,j_l)$ と $-1$ の $(i_{l+1},j_l)$ が 1 つずつあるので、$d$ の各行・各列の和は $0$ である。閉路の辺での $x$ の成分の最小値を $\varepsilon>0$ とすると、$x\pm\varepsilon d\ge0$ で、行と列の和は $x$ と同じなので $x\pm\varepsilon d\in T(a,b)$ である。$x=\frac12(x+\varepsilon d)+\frac12(x-\varepsilon d)$ で $d\ne0$ なので、$x$ は端点でなく、頂点でない。
十分性：$\operatorname{supp}x$ が森であるとし、$x=(1-t)y+tz$（$y,z\in T(a,b)$、$0< t< 1$）とする。$x_{ij}=0$ なら、$y_{ij},z_{ij}\ge0$ と $(1-t)y_{ij}+tz_{ij}=0$ から $y_{ij}=z_{ij}=0$ である。よって $y,z$ の支えも森 $\operatorname{supp}x$ に含まれ、lem-tp-forest により $y=x=z$ である。したがって $x$ は端点であり、頂点である。$\square$

1：頂点 $x$ の支えは $m+n$ 個の頂点の上の森なので、森 の定理「森の同値条件」の 4 により辺の本数は $m+n-(\text{連結成分の個数})\le m+n-1$ である。2：thm-tp-vertex により支えは森なので、lem-tp-forest を $F=\operatorname{supp}x$ に当てる。3：prop-tp-feasible により最適解がある。$T(a,b)$ は条件 $x\ge0$ を含むので直線を含まず、線形計画法 の定理「最適解は頂点でとれる」（最大化 $(-c)\cdot x$ として当てる）により頂点の最適解がある。それは 2 により整数である。$\square$

要点：右へ進むのは $b'_j$ が $0$ になったとき、下へ進むのは $a'_i$ が $0$ になったときで、位置は $(1,1)$ から $(m,n)$ への階段状の道をなす。

1 の要点：符号の行列 $d$ の各行・各列の和は $0$ で、$T'$ は閉路の辺を 1 本除いた連結グラフである。

1：頂点 $x$ は cor-tp-integral の 2 により整数で、$0\le x_{ij}\le1$ なので成分は $0$ か $1$ であり、各行・各列の和が $1$ なので置換行列である。逆に置換行列の支えは、共通の端点をもたない $n$ 本の辺なので閉路を含まず、thm-tp-vertex により頂点である。2：二重確率行列の全体は空でない有界な多面体なので、多面体 の定理「凸多面体は頂点の凸包」と 1 による。3：置換 $\sigma$ に対応する置換行列の費用は $\sum_ic_{i\sigma(i)}$ である。cor-tp-integral の 3 により輸送問題には頂点の最適解があり、1 によりそれは置換行列である。$\square$