Problema de cobertura (combinatoria)

En el contexto de la programación lineal, se puede pensar en cualquier programa lineal como un problema de cobertura si los coeficientes de la matriz de restricción, la función objetivo y el lado derecho no son negativos.^[1] Más precisamente, considere el siguiente programa lineal de enteros general:

minimizar	${\displaystyle \sum _{i=1}^{n}c_{i}x_{i}}$
sujeto a	${\displaystyle \sum _{i=1}^{n}a_{ji}x_{i}\geq b_{j}{\text{ para }}j=1,\dots ,m}$
	${\displaystyle x_{i}\geq 0{\text{ para }}i=1,\dots ,n}$.

Tal programa lineal de enteros se llama problema de cobertura si ${\displaystyle a_{ji},b_{j},c_{i}\geq 0}$ para todo ${\displaystyle i=1,\dots ,n}$ y ${\displaystyle j=1,\dots ,m}$.

Intuición: suponga tener ${\displaystyle n}$ tipos de objeto y cada objeto de tipo ${\displaystyle i}$ tiene un costo asociado de ${\displaystyle c_{i}}$. El número ${\displaystyle x_{i}}$ indica cuántos objetos de tipo ${\displaystyle i}$ compramos. Si las restricciones ${\displaystyle A\mathbf {x} \geq \mathbf {b} }$ están satisfechos, se dice que ${\displaystyle \mathbf {x} }$ es una cobertura (las estructuras que se cubren dependen del contexto combinatorio). Finalmente, una solución óptima para el programa lineal de enteros anterior es una cobertura de costo mínimo.

Hay varios tipos de problemas de cobertura en teoría de grafos, geometría computacional y más.

En el caso de las redes de Petri, por ejemplo, el problema de la cobertura se define como la cuestión de si para una marca determinada existe un recorrido de la red, de modo que se pueda alcanzar una marca mayor (o igual). Más grande significa aquí que todos los componentes son al menos tan grandes como los de la marca dada y al menos uno es adecuadamente más grande.