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 $P$ e un vettore $\mathbf {x} ^{*}\in \mathbb {R} ^{n}$ , $\mathbf {x} ^{*}$ è una soluzione di base se:

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

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

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

Riferimenti

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

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

[1]