Systems of Inequalities - Revision history

Khanh at 21:41, 5 November 2021

2021-11-05T21:41:31Z

Khanh at 19:56, 25 September 2021

2021-09-25T19:56:06Z

Khanh at 19:54, 25 September 2021

2021-09-25T19:54:56Z

Khanh at 19:52, 25 September 2021

2021-09-25T19:52:07Z

Khanh: Created page with "In mathematics a '''linear inequality''' is an inequality which involves a linear function. A linear inequality contains one of the symbols of inequality: It shows the data w..."

2021-09-25T19:51:25Z

Created page with "In mathematics a '''linear inequality''' is an inequality which involves a linear function. A linear inequality contains one of the symbols of inequality: It shows the data w..."

New page

In mathematics a '''linear inequality''' is an inequality which involves a linear function. A linear inequality contains one of the symbols of inequality: It shows the data which is not equal in graph form.
* < less than
* > greater than
* ≤ less than or equal to
* ≥ greater than or equal to
* ≠ not equal to
* = equal to
A linear inequality looks exactly like a linear equation, with the inequality sign replacing the equality sign.

==Linear inequalities of real numbers==

===Two-dimensional linear inequalities===
[[File:Linearineq1.svg|thumb|{{center|Graph of linear inequality: x + 3y < 9}}]]

Two-dimensional linear inequalities are expressions in two variables of the form:
:<math>ax + by < c \text{ and } ax + by \geq c,</math>
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. Technically, for this statement to be correct both ''a'' and ''b'' can not simultaneously be zero. In that situation, the solution set is either empty or the entire 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 (''x''0, ''y''0) 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'' < 9, one first draws the line with equation ''x'' + 3''y'' = 9 as a dotted line, to indicate that the line is not included in the solution set since the inequality is strict. Then, pick a convenient point not on the line, such as (0,0). Since 0 + 3(0) = 0 < 9, this point is in the solution set, so the half-plane containing this point (the half-plane "below" the line) is the solution set of this linear inequality.

===Linear inequalities in general dimensions===
In '''R'''n linear inequalities are the expressions that may be written in the form

:<math> f(\bar{x}) or <math> f(\bar{x}) \leq b,</math>
where ''f'' is a linear form (also called a ''linear functional''), <math>\bar{x} = (x_1,x_2,\ldots,x_n)</math> and ''b'' a constant real number.

More concretely, this may be written out as
:<math>a_1 x_1 + a_2 x_2 + \cdots + a_n x_n 
or
:<math>a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq b.</math>

Here <math>x_1, x_2,...,x_n</math> are called the unknowns, and <math>a_{1}, a_{2},..., a_{n}</math> are called the coefficients.

Alternatively, these may be written as

:<math> g(x) < 0 \,</math> or <math> g(x) \leq 0,</math>
where ''g'' is an affine function.
That is
: <math>a_0 + a_1 x_1 + a_2 x_2 + \cdots + a_n x_n < 0</math>
or
: <math>a_0 + a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq 0.</math>

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:

:<math>\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}</math>
Here <math>x_1,\ x_2,...,x_n</math> are the unknowns, <math>a_{11},\ a_{12},...,\ a_{mn}</math> are the coefficients of the system, and <math>b_1,\ b_2,...,b_m</math> are the constant terms.

This can be concisely written as the matrix inequality

:<math>Ax \leq b,</math>

where ''A'' is an ''m''×''n'' matrix, ''x'' is an ''n''×1 column vector of variables, and ''b'' is an ''m''×1 column vector of constants.

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 '''R'''''n''.

====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==

The above definition requires well-defined operations of addition, multiplication and comparison; therefore, the notion of a linear inequality may be extended to ordered rings, and in particular to ordered fields.

==References==
# Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.
# Angel, Allen R.; Porter, Stuart R. (1989), A Survey of Mathematics with Applications (3rd ed.), Addison-Wesley, ISBN 0-201-13696-1
# Miller, Charles D.; Heeren, Vern E. (1986), Mathematical Ideas (5th ed.), Scott, Foresman, ISBN 0-673-18276-2

@@ Line 86: / Line 86: @@
 * [https://www.youtube.com/watch?v=5xQqwgS3O4U System of Linear Inequalities], Khan Academy
-==References==
+== Licensing ==
-# Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.
+Content obtained and/or adapted from:
-# Angel, Allen R.; Porter, Stuart R. (1989), A Survey of Mathematics with Applications (3rd ed.), Addison-Wesley, ISBN 0-201-13696-1
+* [https://en.wikipedia.org/wiki/Linear_inequality Linear inequality, Wikipedia] under a CC BY-SA license

@@ Line 11: / Line 11: @@
 ===Two-dimensional linear inequalities===
-[[File:Linearineq1.svg|thumb|{{center|Graph of linear inequality:<br> x + 3y < 9}}]]
+[[File:Linearineq1.svg|thumb|Graph of linear inequality:<br> x + 3y < 9]]
 Two-dimensional linear inequalities are expressions in two variables of the form:

@@ Line 75: / Line 75: @@
 ====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.
@@ Line 82: / Line 81: @@
 The above definition requires well-defined operations of addition, multiplication and comparison; therefore, the notion of a linear inequality may be extended to ordered rings, and in particular to ordered fields.
 ==References==

@@ Line 36: / Line 36: @@
 :<math> g(x) < 0 \,</math> or <math> g(x) \leq 0,</math>
 where ''g'' is an affine function.
 That is
 : <math>a_0 + a_1 x_1 + a_2 x_2 + \cdots + a_n x_n < 0</math>