Problema del recobriment

De Viquipèdia
Dreceres ràpides: navegació, cerca

Els problemes de recobriment són normalment problemes de minimització i programació lineal, els problemes duals dels quals s'anomenen problemes d'embalatge. Els exemples més prominents de problemes de recobriment són el problema del recobriment d'un conjunt.

Formulació LP general[modifica | modifica el codi]

En el context de programació lineal, es pot pensar en qualsevol programa lineal com a problema de recobriment si els coeficients a la matriu de restriccions, la funció objectiu, i el cantó de la dreta són no negatius.[1] Més precisament, consideris el programa lineal general en variables enteres:

minimitzar \sum_{i=1}^n c_i x_i
subjecte a  \sum_{i=1}^n a_{ij} x_i \geq b_j \text{ for }j=1,\dots,m
x_i \geq 0\text{ for }i=1,\dots,n.

Tal programa lineal en variables enteres s'anomena problema de recobriment si a_{ij}, b_j, c_i \geq 0 per a tot i=1,\dots,n i j=1,\dots,m.

Intuïció: Suposar que es tenen n tipus d'objecte i cada objecte del tipus i té un cost associat de c_i. El nombre x_i diu quants objectes del tipus i es compren. Si les restriccions A\mathbf{x}\geq \mathbf{b} es satisfan, es diu que \mathbf{x} és un recobriment (les estructures que es recobreixen depenen del context combinatori). Finalment, una solució òptima al citat programa lineal és un recoberiment de cost mínim.

Altres usos[modifica | modifica el codi]

Per a xarxes de Petri, per exemple, el problema del recobriment es defineix com la pregunta de si per a un marcatge donat, existeix un camí de la xarxa, tal que es pot arribar amb una marca més gran (o igual). Més gran vol dir aquí que tots els components són com a mínim tan grans com el del marcatge donat i com a mínim un és pròpiament més gran.

Notes[modifica | modifica el codi]

  1. Vazirani (2001, p. 112)

Bibliografia[modifica | modifica el codi]