Two-dimensional linear inequalities Two-dimensional linear inequalities, are expressions in two variables of the form: :ax + by where the inequalities may either be strict or not. The solution set of such an inequality can be graphically represented by a half-plane (all the points on one "side" of a fixed line) in the Euclidean plane. The line that determines the half-planes (
ax +
by =
c) is not included in the solution set when the inequality is strict. A simple procedure to determine which half-plane is in the solution set is to calculate the value of
ax +
by at a point (
x0,
y0) which is not on the line and observe whether or not the inequality is satisfied. For example, to draw the solution set of
x + 3
y n linear inequalities are the expressions that may be written in the form : f(\bar{x}) or f(\bar{x}) \leq b, where
f is a
linear form (also called a
linear functional), \bar{x} = (x_1,x_2,\ldots,x_n) and
b a constant real number. More concretely, this may be written out as :a_1 x_1 + a_2 x_2 + \cdots + a_n x_n or :a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq b. Here x_1, x_2,...,x_n are called the unknowns, and a_{1}, a_{2},..., a_{n} are called the coefficients. Alternatively, these may be written as : g(x) or g(x) \leq 0, where
g is an
affine function. That is : a_0 + a_1 x_1 + a_2 x_2 + \cdots + a_n x_n or : a_0 + a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq 0. Note that any inequality containing a "greater than" or a "greater than or equal" sign can be rewritten with a "less than" or "less than or equal" sign, so there is no need to define linear inequalities using those signs.
Systems of linear inequalities A system of linear inequalities is a set of linear inequalities in the same variables: :\begin{alignat}{7} a_{11} x_1 &&\; + \;&& a_{12} x_2 &&\; + \cdots + \;&& a_{1n} x_n &&\; \leq \;&&& b_1 \\ a_{21} x_1 &&\; + \;&& a_{22} x_2 &&\; + \cdots + \;&& a_{2n} x_n &&\; \leq \;&&& b_2 \\ \vdots\;\;\; && && \vdots\;\;\; && && \vdots\;\;\; && &&& \;\vdots \\ a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \cdots + \;&& a_{mn} x_n &&\; \leq \;&&& b_m \\ \end{alignat} Here x_1,\ x_2,...,x_n are the unknowns, a_{11},\ a_{12},...,\ a_{mn} are the coefficients of the system, and b_1,\ b_2,...,b_m are the constant terms. This can be concisely written as the
matrix inequality :Ax \leq b, where
A is an
m×
n matrix of constants,
x is an
n×1
column vector of variables,
b is an
m×1 column vector of constants and the inequality relation is understood row-by-row. In the above systems both strict and non-strict inequalities may be used. • Not all systems of linear inequalities have solutions. Variables can be eliminated from systems of linear inequalities using
Fourier–Motzkin elimination.
Applications Polyhedra The set of solutions of a real linear inequality constitutes a
half-space of the 'n'-dimensional real space, one of the two defined by the corresponding linear equation. The set of solutions of a system of linear inequalities corresponds to the intersection of the half-spaces defined by individual inequalities. It is a
convex set, since the half-spaces are convex sets, and the intersection of a set of convex sets is also convex. In the non-
degenerate cases this convex set is a
convex polyhedron (possibly unbounded, e.g., a half-space, a slab between two parallel half-spaces or a
polyhedral cone). It may also be empty or a convex polyhedron of lower dimension confined to an
affine subspace of the
n-dimensional space
Rn.
Linear programming A linear programming problem seeks to optimize (find a maximum or minimum value) a function (called the
objective function) subject to a number of constraints on the variables which, in general, are linear inequalities. The list of constraints is a system of linear inequalities. ==Generalization==