Desigualdad lineal

Representación gráfica de una desigualdad lineal:
x + 3y < 9

Las desigualdades lineales bidimensionales son expresiones en dos variables de la forma:

${\displaystyle ax+by<c{\text{ o }}ax+by\geq c,}$

donde las desigualdades pueden ser estrictas o no. El conjunto de soluciones de tal desigualdad se puede representar gráficamente en un semiplano (todos los puntos de un "lado" de una línea fija) en el plano euclidiano.[nota 1] La línea que determina los semiplanos (ax + by = c) no se incluye en el conjunto de soluciones cuando la desigualdad es estricta. Un procedimiento sencillo para determinar qué semiplano está en la solución ajustada es calcular el valor ax + by en un punto (x₀, y₀) que no está en la línea y observar si se cumple o no la desigualdad.

Por ejemplo,[2] para representar el conjunto de soluciones de x + 3y < 9, primero se dibuja la línea con la ecuación x + 3y = 9 como una línea de puntos, para indicar que la línea no está incluida en el conjunto de soluciones ya que la desigualdad es estricta. Luego, se elige un punto conveniente que no esté en la línea, como (0,0). Puesto que 0 + 3 (0) = 0 < 9, este punto se encuentra en el conjunto de soluciones, por lo que el semiplano que contiene este punto (el semiplano por "debajo" de la línea) es el conjunto de soluciones de esta desigualdad lineal.

En Rⁿ las desigualdades lineales son las expresiones que se pueden escribir en la forma

${\displaystyle f({\bar {x}})<b}$ o ${\displaystyle f({\bar {x}})\leq b,}$

donde f es una forma lineal, ${\displaystyle {\bar {x}}=(x_{1},x_{2},\ldots ,x_{n})}$ y b un número real constante.

Más concretamente, esto puede expresarse como:

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}<b}$

o

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}\leq b.}$

Donde ${\displaystyle x_{1},x_{2},...,x_{n}}$ son las incógnitas y ${\displaystyle a_{1},a_{2},...,a_{n}}$ son los coeficientes.

Alternativamente, también pueden expresarse como:

${\displaystyle g(x)<0\,}$ o ${\displaystyle g(x)\leq 0,}$

donde g es una función afín.[nota 2]

Esto es

${\displaystyle a_{0}+a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}<0}$

o

${\displaystyle a_{0}+a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}\leq 0.}$

Nótese que cualquier desigualdad que contenga un signo "mayor que" o "mayor o igual que" puede expresarse también con un signo "menor que" o "menor o igual que", por lo que no es necesario definir desigualdades lineales utilizando esos signos.

Un sistema de desigualdades lineales es un conjunto de desigualdades lineales en las mismas variables:

${\displaystyle {\begin{alignedat}{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{alignedat}}}$

Donde ${\displaystyle x_{1},\ x_{2},...,x_{n}}$ son las incógnitas, ${\displaystyle a_{11},\ a_{12},...,\ a_{mn}}$ los coeficientes del sistema y ${\displaystyle b_{1},\ b_{2},...,b_{m}}$ los términos constantes.

Esto puede expresarse como una desigualdad en forma de matriz:

${\displaystyle Ax\leq b,}$

donde A es una matriz m×n, x es un vector columna de n×1 variables, y b es un vector columna de m×1 constantes.

En los sistemas anteriores pueden utilizarse tanto desigualdades estrictas como no estrictas.

• No todos los sistemas de desigualdades lineales tienen soluciones.

El conjunto de soluciones de una desigualdad lineal real constituye un semiespacio del espacio real 'n'-dimensional, uno de los dos definidos por la correspondiente ecuación lineal.

El conjunto de soluciones de un sistema de desigualdades lineales corresponde a la intersección de los semiespacios definidos por las desigualdades individuales. Es un conjunto convexo, ya que los semiespacios son conjuntos convexos, y la intersección de un conjunto de conjuntos convexos también es convexa. En los casos no degenerados, este conjunto convexo es un poliedro convexo (posiblemente sin límites, por ejemplo, un semiespacio, una porción entre dos semiespacios paralelos o un cono poliédrico). También puede estar vacío o ser un poliedro convexo de dimensión inferior confinado a un subespacio afín del espacio 'n'-dimensional Rⁿ.

Un problema de programación lineal busca optimizar (encontrar un valor máximo o mínimo) de una función (llamada función objetiva) sujeta a una serie de restricciones sobre las variables que, en general, son desigualdades lineales.[3] La lista de restricciones es un sistema de desigualdades lineales.