Efficiently solve a system of strict linear inequalities with all coefficients equal to 1 without using a general LP solver?
For your first question, without the total order, the answer to your question is that it's essentially as hard as linear programming. Here's an outline of a proof.

First, let's establish a variable $x_1&gt;0$, which we call $\epsilon$. Now, let's choose another variable $x_i$, which we will call $1$. We want to make sure that $$\epsilon \ll 1\, .$$
To do this, consider the inequalities
$$x_1 &lt; x_2,$$ 
$$x_1 + x_2 &lt; x_3,$$
$$x_2+x_3 &lt; x_4,$$
and so on. With a long enough chain, this will tell us that $Nx_1 &lt; x_i$, or $\epsilon &lt; 1/N$, for some very large $N$ ($N$ is a Fibonacci number, and so grows exponentially in $i$). 

We can now manufacture a linear program with integer coefficients. If we want a coefficient of 3 on $x_t$, we add the inequalities
$$x_t &lt; x_{t&#39;} &lt; x_{t&#39;&#39;} &lt; x_t + \epsilon$$ and let $x_t + x_{t&#39;} + x_{t&#39;&#39;}$ stand in for 3$x_t$. If you want larger coefficients, you can get them by expressing the coefficients in binary notation, and making inequalities that guarantee that $x_u \approx 2x_t$, $x_v \approx 2x_u$, and so on. To get the right-hand-side, we do the same with the variable $x_i = 1$. This technique will let us use linear programs of the OP's form to approximately check feasibility for arbitrary linear programs with integer coefficients, a task which is essentially as hard as linear programming.

I don't know how to analyze the second question, asking about the case where there's a total order on all subsets.