[proofplan]
We prove existence by the direct method in finite dimensions. First we show that the feasible set is nonempty by constructing the product transport plan. Then we show that the transport polytope is a closed and bounded subset of the Euclidean space $\mathbb{R}^{m \times n}$, hence compact. Finally, the finite Kantorovich cost is a continuous linear functional, so the Weierstrass extreme value theorem gives a minimizer on the compact feasible set.
[/proofplan]
[step:Construct a feasible product plan]
Define $P^0 = (P^0_{ij}) \in \mathbb{R}^{m \times n}$ by
\begin{align*}
P^0_{ij} := a_i b_j
\end{align*}
for every $i \in \{1,\dots,m\}$ and every $j \in \{1,\dots,n\}$. Since $a_i \geq 0$ and $b_j \geq 0$, each entry satisfies $P^0_{ij} \geq 0$.
For each $i \in \{1,\dots,m\}$, using $\sum_{j=1}^{n} b_j = 1$, we compute
\begin{align*}
\sum_{j=1}^{n} P^0_{ij} = \sum_{j=1}^{n} a_i b_j = a_i \sum_{j=1}^{n} b_j = a_i.
\end{align*}
For each $j \in \{1,\dots,n\}$, using $\sum_{i=1}^{m} a_i = 1$, we compute
\begin{align*}
\sum_{i=1}^{m} P^0_{ij} = \sum_{i=1}^{m} a_i b_j = b_j \sum_{i=1}^{m} a_i = b_j.
\end{align*}
Therefore $P^0 \in \Pi(a,b)$, so $\Pi(a,b)$ is nonempty.
[/step]
[step:Realize the feasible set as a closed bounded subset of Euclidean space]
We view $\mathbb{R}^{m \times n}$ as the finite-dimensional Euclidean space of real $m \times n$ matrices, equipped with its usual topology. For each $i \in \{1,\dots,m\}$, define the row-sum map $R_i: \mathbb{R}^{m \times n} \to \mathbb{R}$ by
\begin{align*}
R_i(P) := \sum_{j=1}^{n} P_{ij}.
\end{align*}
For each $j \in \{1,\dots,n\}$, define the column-sum map $S_j: \mathbb{R}^{m \times n} \to \mathbb{R}$ by
\begin{align*}
S_j(P) := \sum_{i=1}^{m} P_{ij}.
\end{align*}
Each map $R_i$ and $S_j$ is linear, hence continuous. For each pair $(i,j)$, define the coordinate map $E_{ij}: \mathbb{R}^{m \times n} \to \mathbb{R}$ by
\begin{align*}
E_{ij}(P) := P_{ij}.
\end{align*}
Each $E_{ij}$ is also linear, hence continuous.
With these maps, the feasible set can be written as
\begin{align*}
\Pi(a,b)
=
\left(\bigcap_{i=1}^{m} R_i^{-1}(\{a_i\})\right)
\cap
\left(\bigcap_{j=1}^{n} S_j^{-1}(\{b_j\})\right)
\cap
\left(\bigcap_{i=1}^{m}\bigcap_{j=1}^{n} E_{ij}^{-1}([0,\infty))\right).
\end{align*}
The sets $\{a_i\}$, $\{b_j\}$, and $[0,\infty)$ are closed subsets of $\mathbb{R}$. Since inverse images of closed sets under continuous maps are closed, and since finite intersections of closed sets are closed, $\Pi(a,b)$ is closed in $\mathbb{R}^{m \times n}$.
Moreover, if $P \in \Pi(a,b)$, then $P_{ij} \geq 0$ and
\begin{align*}
P_{ij} \leq \sum_{k=1}^{n} P_{ik} = a_i \leq 1
\end{align*}
for every $i \in \{1,\dots,m\}$ and every $j \in \{1,\dots,n\}$. Hence $\Pi(a,b) \subset [0,1]^{m \times n}$, so $\Pi(a,b)$ is bounded.
[guided]
The goal of this step is to justify compactness later. In finite-dimensional Euclidean space, compactness follows from being closed and bounded, so we verify those two properties directly from the constraints defining $\Pi(a,b)$.
First, we name the constraint maps. For each row index $i \in \{1,\dots,m\}$, define $R_i: \mathbb{R}^{m \times n} \to \mathbb{R}$ by
\begin{align*}
R_i(P) := \sum_{j=1}^{n} P_{ij}.
\end{align*}
This is the map that records the total mass in row $i$. For each column index $j \in \{1,\dots,n\}$, define $S_j: \mathbb{R}^{m \times n} \to \mathbb{R}$ by
\begin{align*}
S_j(P) := \sum_{i=1}^{m} P_{ij}.
\end{align*}
This records the total mass in column $j$. Finally, for each pair $(i,j)$, define $E_{ij}: \mathbb{R}^{m \times n} \to \mathbb{R}$ by
\begin{align*}
E_{ij}(P) := P_{ij}.
\end{align*}
The maps $R_i$, $S_j$, and $E_{ij}$ are linear maps on the Euclidean [vector space](/page/Vector%20Space) $\mathbb{R}^{m \times n}$, hence they are continuous.
Now rewrite the feasible set using these maps:
\begin{align*}
\Pi(a,b)
=
\left(\bigcap_{i=1}^{m} R_i^{-1}(\{a_i\})\right)
\cap
\left(\bigcap_{j=1}^{n} S_j^{-1}(\{b_j\})\right)
\cap
\left(\bigcap_{i=1}^{m}\bigcap_{j=1}^{n} E_{ij}^{-1}([0,\infty))\right).
\end{align*}
This formula says exactly that every row sum is prescribed by $a$, every column sum is prescribed by $b$, and every entry is nonnegative. The singleton sets $\{a_i\}$ and $\{b_j\}$ are closed in $\mathbb{R}$, and the interval $[0,\infty)$ is closed in $\mathbb{R}$. Because continuous preimages of closed sets are closed, every set appearing in the finite intersection above is closed. A finite intersection of closed sets is closed, so $\Pi(a,b)$ is closed in $\mathbb{R}^{m \times n}$.
Next we prove boundedness. Let $P \in \Pi(a,b)$ and fix $i \in \{1,\dots,m\}$ and $j \in \{1,\dots,n\}$. Since $P$ is feasible, all its entries are nonnegative. Therefore a single entry is bounded above by its full row sum:
\begin{align*}
P_{ij} \leq \sum_{k=1}^{n} P_{ik}.
\end{align*}
The row-sum constraint gives
\begin{align*}
\sum_{k=1}^{n} P_{ik} = a_i.
\end{align*}
Since $a \in [0,1]^m$, we have $a_i \leq 1$. Combining these facts gives
\begin{align*}
0 \leq P_{ij} \leq 1.
\end{align*}
Because this holds for every entry, $P \in [0,1]^{m \times n}$. Thus $\Pi(a,b) \subset [0,1]^{m \times n}$, and consequently $\Pi(a,b)$ is bounded.
[/guided]
[/step]
[step:Conclude that the transport polytope is compact]
The set $\Pi(a,b)$ is closed and bounded in the finite-dimensional Euclidean space $\mathbb{R}^{m \times n}$. By the finite-dimensional [Heine-Borel theorem](/theorems/309), $\Pi(a,b)$ is compact. Together with the first step, $\Pi(a,b)$ is a nonempty compact subset of $\mathbb{R}^{m \times n}$.
[/step]
[step:Apply the extreme value theorem to the finite Kantorovich cost]
Define the cost functional $\Phi_C: \mathbb{R}^{m \times n} \to \mathbb{R}$ by
\begin{align*}
\Phi_C(P) := \sum_{i=1}^{m}\sum_{j=1}^{n} C_{ij}P_{ij}.
\end{align*}
The map $\Phi_C$ is linear, hence continuous. Since $\Pi(a,b)$ is nonempty and compact, the Weierstrass Extreme Value Theorem applies to the [continuous function](/page/Continuous%20Function) $\Phi_C|_{\Pi(a,b)}: \Pi(a,b) \to \mathbb{R}$ (citing a result not yet in the wiki: Weierstrass Extreme Value Theorem). Therefore there exists $P^* \in \Pi(a,b)$ such that
\begin{align*}
\Phi_C(P^*) = \min_{P \in \Pi(a,b)} \Phi_C(P).
\end{align*}
By the definition of $\Phi_C$, this means
\begin{align*}
\sum_{i=1}^{m}\sum_{j=1}^{n} C_{ij}P^*_{ij}
=
\min_{P \in \Pi(a,b)}
\sum_{i=1}^{m}\sum_{j=1}^{n} C_{ij}P_{ij}.
\end{align*}
Thus $P^*$ is an optimal plan for the finite Kantorovich primal problem.
[/step]
