Minimizing the number of strictly negative variables, $x_j$, subject to the set of linear constraints, $Ax \leq b$, can be formulated as
$$
\begin{array}{ll}
\min & \| \; [x]_- \; \|_0\\
& A x \leq b.
\end{array}
$$

where $\| \cdot \|_0$ is the [zero "norm"](https://en.wikipedia.org/wiki/Lp_space#When_p_=_0) and $[ \cdot ]_-$ is the projection to the nonpositive orthant, $\mathbb{R}^n_-$.

##### Complexity
This problem is NP-hard and thus you unfortunately wont find anyone able to solve it in polynomial time. This can be proven by its ability to solve the NP-complete binary satisfiability problem
$$
A y \leq b,\;
y \in \{0, 1\},
$$
equivalent to
$$
A y \leq b,\;
y \in \{0, -1\},
$$
representable by
$$
\begin{array}{ll}
\min & \| \; [ \substack{y\\z} ]_- \; \|_0\\
& A y \leq b,\; -1 \leq y \leq 0,\; y + z = -1,
\end{array}
$$

which is easily cast to the problem type considered.

##### Solution approaches
You can solve it exactly using mixed-integer linear programming as suggested by @RobPratt, or you can solve it approximately in polynomial time by using the one-norm yielding
$$
\begin{array}{ll}
\min & \| \; [x]_- \; \|_1\\
& A x \leq b.
\end{array}
$$

which can be linearized as
$$
\begin{array}{ll}
\min & \mathbf{1}^T x^-\\
& A x \leq b, \\
& x = x^+ + x^-, \\
& x^+, x^- \geq 0.
\end{array}
$$

where $\mathbf{1}$ is a vector of ones.