Problema de cobertura (combinatòria)

En combinatòria i ciències de la computació, els problemes de cobertura són problemes computacionals que pregunten si una determinada estructura combinatòria 'cobrix' a una atra, o quina tan gran deu ser l'estructura per a fer això. Els problemes de cobertura són problemes de minimisació i, per lo general, programes llineals, els problemes duals dels quals es denominen problemes de empaque.

Els eixemples més destacats de problemes de cobertura són el problema de cobertura de conjunts, que és equivalent al problema d'encert de conjunts, i els seus casos especials, el problema de cobertura de vèrtiços i el problema de cobertura de vores.

Formulació de programació llineal general

En el context de la programació llineal, es pot pensar en qualsevol programa llineal com un problema de cobertura si els coeficients de la matriu de restricció, la funció objectiu i el costat dret no són negatius.^[1] Més precisament, considere el següent programa llineal de sancers general:

minimisar	$\sum_{i = 1}^{n} c_{i} x_{i}$
$\sum_{i = 1}^{n} a_{j i} x_{i} \geq b_{j} para j = 1, \dots, m$
	$x_{i} \geq 0 para i = 1, \dots, n$ .

Tal programa llineal de sancers es diu problema de cobertura si $a_{j i}, b_{j}, c_{i} \geq 0$ para tot $i = 1, \dots, n$ i $j = 1, \dots, m$ .

Intuïció: suponga tindre $n$ tipos d'objecte i cada objecte de tipo $i$ té un cost associat de $c_{i}$ . El número $x_{i}$ indica quants objectes de tipo $i$ comprem. Si les restriccions $A 𝐱 \geq 𝐛$ estan satisfets, es diu que $𝐱$ és una cobertura (les estructures que es cobrixen depenen del context combinatori). Finalment, una solució òptima per al programa llineal de sancers anterior és una cobertura de cost mínim.

Tipos de problemes de cobertura

Hi ha varis tipos de problemes de cobertura en teoria de grafos, geometria computacional i més.

En el cas de les rets de Petri, per eixemple, el problema de la cobertura es definix com la qüestió de si per a una marca determinada existix un recorregut de la ret, de modo que es puga alcançar una marca major (o igual). Més gran significa ací que tots els components són a lo manco tan grans com els de la marca donada i a lo manco un és adequadament més gran.

Vore també

Referències

↑ Vazirani, Vijay V. (2001). Approximation Algorithms, Springer-Verlag. ISBN 3-540-65367-8.^{<span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: Plantilla:R/where}

Referències

Este artícul conté una traducció derivada de «Problema de cobertura (combinatoria)» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Vazirani, Vijay V. (2001). Approximation Algorithms, Springer-Verlag. ISBN 3-540-65367-8.^{<span title="Erro en la seqüencia d'órdens: no existix el mòdul «DecodeEncode».">: Plantilla:R/where}

[1]

Plantilla:R/where