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, consideri's el programa lineal general en variables enteres:

minimitzar
subjecte a
.

Tal programa lineal en variables enteres s'anomena problema de recobriment si per a tot i .

Intuïció: Suposar que es tenen tipus d'objecte i cada objecte del tipus té un cost associat de . El nombre diu quants objectes del tipus es compren. Si les restriccions es satisfan, es diu que é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]