Home » Intelligenza Artificiale » 📋 URL
Programmazione lineare (LP)
Un problema di programmazione lineare consiste nel minimizzare una funzione lineare soggetta a un numero finito di vincoli lineari, assume la forma di
\begin{cases}
\min\{cx\}\\
x\,a_i\,\,\theta\,\,b_i & i=1,\,\dots,\,m\\
\ell_j\leq x_j \leq u_j & j=1,\,\dots,\,n
\end{cases}Dove:
- \theta\in\{\leq,\,\geq,\,=\}
- \ell\in\R\cup\{-\infty\}
- u_j\in\R\cup\{+\infty\}
- x_j sono degli intervalli di \R
Nota: i domini di un problema di programmazione lineare sono continui, dunque non rientrano nell’ottimizzazione discreta ma vanno trasformati in problemi discreti per poter essere trattati.
Programmazione lineare intera (MIP)
Anche un problema di programmazione lineare intera consiste nel minimizzare una funzione lineare soggetta a un numero finito di vincoli lineari, assume la forma di
\begin{cases}
\min\{cx\}\\
x\,a_i\,\,\theta\,\,b_i&i=1,\,\dots,\,m\\
\ell_j\leq x_j\leq u_j & j=1,\,\dots,\,n=N\\
x_j\in\Z&\forall\,\,j\in J\subseteq N=\{1,\,\dots,\,n\}
\end{cases}Nota: se J=N si ha un problema di programmazione lineare intera pura. Se invece J=\emptyset si ha un semplice problema di programmazione lineare.
Programmazione con vincoli (CP)
Un problema di programmazione con vincoli è definito da una terna
(X,\,D,\,C)
Dove:
- X: un insieme di variabili con dominio finito
- D,\,C: un insieme finito di vincoli di natura arbitraria
Nella sua forma classica un problema CP non ha una funzione obiettivo, ma mira alla mera ricerca di una soluzione ammissibile, dunque parliamo di problema di ammissibilità.
Soddisfacibilità booleana (SAT)
Un problema si soddisfacibilità booleana rappresenta un caso particolare di problema di ammissibilità nel quale le variabili sono tutte booleane.
Problemi di ottimizzazione comuni
- Problema del trasporto
- Problema della dieta
- Problema (binario) dello zaino
- Vertex coloring
- Set covering