How to prove that solution have at most $m$ fractional coordinates

Question

I started to study a bit of mixed linear programming, and I am facing the following exercise that after quite some time I don't know how to approach:

Let $A\in\mathbb{R}^{m,n}$, $b\in\mathbb{R}^{m}$, $c\in\mathbb{R}^{n}$ and $u\in\mathbb{Z}^{n}$. Prove that if the problem $\max\{c^{T}x|Ax\leq b,\ 0\leq x\leq u\}$ is feasible and bounded, then you have a solution with at most $m$ fractional coordinates.

Could you help me? Greetings!

Answer 1

Assuming you are familiar with the concept of basic feasible solution (BFS), convince yourself that an optimal solution exists, express it as a BFS, and count the basic and nonbasic variables.