In the transportation problem, we have a set of $ k $ warehouses with a supply of $ a_{i} > 0 $ for $ i \in\{1, \ldots, k\} $, and $ \ell $ customers with a demand of $ b_{j} > 0 $ for $ j \in\{1, \ldots, \ell\} $. The goal is to satisfy the demand of all customers from the warehouses at the lowest possible cost. Essentially, each warehouse can supply any customer (within its supply limit), but there are costs $ c_{ij} $ associated with each unit that customer $ j $ receives from warehouse $ i $.
The transportation problem can also be formulated as a linear program:
\begin{array}{c} \min \sum \limits_{ij} c_{ij} x_{ij} \\ \text{subject to} \sum \limits_{j=1}^{\ell} x_{ij} = a_{i} \quad \forall i \in\{1, \ldots, k\} \\ \sum \limits_{i=1}^{k} x_{ij} = b_{j} \quad \forall j \in\{1, \ldots, \ell\} \\ x_{ij} \geq 0 \quad \forall i \in\{1, \ldots, k\}, j \in\{1, \ldots, \ell\} \end{array}
Let $ P $ be the polytope defined by the above LP.
For the following tasks, let's assume that the given instance is balanced, meaning that $ \sum \limits_{i} a_{i} = \sum \limits_{j} b_{j} $.
Show that:
(a) there exists $ x^* \in P $ such that $ x_{ij}^* > 0 $ for all $ i \in\{1, \ldots, k\} $ and $ j \in\{1, \ldots, \ell\} $, and
(b) $ \operatorname{dim} P = k \cdot \ell - k - \ell + 1 $.
Question:
I'm trying to solve this task somehow, but it just won't get into my head how to do it. I would be open to any hints or ideas on how to solve this.
For b) the following lemma would probably be useful, but as I said, it doesn't add up for me how to adapt the given situation to it.
