Soluzione di base (programmazione lineare)

Nella programmazione lineare, un campo della matematica applicata, una soluzione di base è qualsiasi soluzione di un problema di programmazione lineare che soddisfa determinate condizioni tecniche specifiche.

Per un poliedro ${\displaystyle P}$ e un vettore ${\displaystyle \mathbf {x} ^{*}\in \mathbb {R} ^{n}}$, ${\displaystyle \mathbf {x} ^{*}}$ è una soluzione di base se:

1. Tutti i vincoli di uguaglianza che definiscono ${\displaystyle P}$ sono attivi a ${\displaystyle \mathbf {x} ^{*}}$.
2. Tra tutti i vincoli attivi in quel punto, almeno ${\displaystyle n}$ di essi devono essere linearmente indipendenti. Ciò implica che almeno che almeno ${\displaystyle n}$ i vincoli devono essere attivi su quel vettore.^[1]

Un vincolo è attivo per una particolare soluzione ${\displaystyle \mathbf {x} }$ se è soddisfatta l'uguaglianza per quella soluzione.

Una soluzione di base che soddisfa tutti i vincoli che definiscono ${\displaystyle P}$ (o, in altre parole, uno che si trova all'interno ${\displaystyle P}$ ) è chiamata soluzione di base ammissibile.

Riferimenti

1. Dimitris Bertsimas e John N. Tsitsiklis, Introduction to linear optimization, Athena Scientific, 1997, pp. 50, ISBN 978-1-886529-19-9.