Problema primale standard

Da Wikipedia, l'enciclopedia libera.

Un problema in forma primale standard è un problema matematico tipico della teoria della programmazione lineare, problema dove si vuole massimizzare il valore di una certa funzione rispettando dei vincoli aggiuntivi espressi sotto forma di disequazioni lineari.

Questa schematizzazione per un problema di ottimizzazione è molto utilizzata poiché esiste una versione dell'algoritmo del simplesso che si applica ad un problema di questo tipo per trovarne una soluzione ottima. L'insieme dello spazio delle possibili soluzioni del problema (dominio) prende il nome di poliedro (politopo) primale, mentre la funzione che si massimizza è detta funzione obiettivo.

La scrittura con la quale si è soliti rappresentare un problema in formato primale è

\left ( P \right ) : \begin{cases} \max \quad c^Tx \\
Ax \le \ b \end{cases}

Che può essere scritto in forma scalare come

\max \sum_{i=1}^n c_i x_i (funzione obiettivo)
\sum_{i = 1}^n a_{1,i} x_i \leq b_1
\dots \dots (vincoli)
\sum_{i = 1}^n a_{m,i} x_i \leq b_m

Quindi il problema primale standard è costituito da una certa funzione che va massimizzata, la funzione obiettivo, ed una serie di vincoli (il poliedro primale); il problema nel suo complesso viene indicato con (P) ,il valore ottimo del problema (P) si indica con v(P) mentre P è il simbolo associato al poliedro primale.

La funzione obiettivo[modifica | modifica sorgente]

Il primo elemento importante che viene introdotto parlando di problemi in forma primale è proprio la funzione obiettivo, cioè una funzione che rappresenta il modello matematico di ciò che vogliamo massimizzare. In realtà è possibile trasformare una richiesta di massimizzazione in minimizzazione semplicemente ricordando il concetto che cercare il minimo di una funzione è come cercare l'opposto del massimo della sua opposta, ovvero: min f(x) = - max -f(x) e viceversa.

Dal momento che stiamo trattando problemi di programmazione lineare appare chiaro come la suddetta funzione debba essere necessariamente lineare, ovvero esprimibile semplicemente tramite prodotti scalari tra costanti e variabili (di primo grado). Infatti per scrivere la funzione si utilizza la notazione cx, che in modo più formale è scritta come:

\left \langle c^T,x \right \rangle = \sum_{i=1}^n c_i x_i

Ovvero come il prodotto scalare tra il vettore colonna delle variabili x, di dimensione n \times 1 e il vettore riga (poi trasposto) caratterizzante la funzione obiettivo c, di dimensione 1 \times n.

Il numero n, che ricorre più volte, si riferisce al numero di variabili coinvolte nel problema, cioè alla dimensione dello spazio delle soluzioni: se ad esempio ci sono due variabili allora n sarà 2. In generale si dice che n è la dimensione della variabile vettoriale del problema: x \in \mathbb{R}^n

Ad esempio se consideriamo la funzione obiettivo in 4 variabili
x_1 -5x_2+7x_3
la sua rappresentazione come prodotto scalare sarà \begin{bmatrix} 1&-5&7&0 \end{bmatrix} \cdot \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix}

Il poliedro primale[modifica | modifica sorgente]

L'insieme dei punti (vettori) che sono ammissibili per il problema in formato primale standard, cioè quelli che soddisfano tutti i vincoli del tipo Ax \le \ b prende, come abbiamo detto, il nome di poliedro primale o politopo primale.

Come già visto per la funzione obiettivo la scrittura completa degli m vincoli, in n variabili, che formano il poliedro primale è

\sum_{i = 1}^n a_{1,i} x_i \leq b_1
\vdots
\sum_{i = 1}^n a_{m,i} x_i \leq b_m

Nella scrittura Ax \le \ b A è una matrice, detta matrice tecnologica, che ha dimensione m \times n, dove m è il numero di vincoli di disuguaglianza definiti dal problema.

Analogamente a quanto detto per la funzione obiettivo, la forma in termini di disuguaglianze dei vincoli del problema non è molto restrittiva: essa infatti permette anche di tradurre in questo formato vincoli di uguaglianza o di disuguaglianza ma in verso opposto. Un generico vincolo lineare  g \left ( x \right ) = 0 può essere infatti reso con due vincoli di disuguaglianza:

 \begin{cases} g \left ( x \right )  \le \ 0 \\
-g \left ( x \right )  \le \ 0 
 \end{cases}

A destra del simbolo di minore o uguale troviamo il vettore b, si tratta del cosiddetto vettore dei termini noti, di dimensione m \times 1, come si evince anche dal prodotto matrice-vettore.

Associato al concetto di vincolo del problema primale vi è anche quello delle variabili di scarto: si tratta in pratica di un vettore di numeri che si ottengono facendo la differenza tra il vettore dei termini noti e quello che si ottiene svolgendo il prodotto tra matrice tecnologica e variabili (che devono essere conosciute).

In forma analitica ciò si scrive come:

\bar S = b - A \tilde{x}

Dove con  \tilde{x} si intende la soluzione rispetto alla quale si vuole conoscere gli scarti.

Gli scarti di una soluzione sono un ottimo metodo per riconoscere se una soluzione è ammissibile per il poliedro P o no: se una soluzione genera scarti non negativi è ammissibile, mentre se anche un solo scarto è minore di 0 allora quel punto non appartiene al poliedro. Un punto del poliedro primale si dirà quindi ammissibile per il problema annesso quando sostituendo le sue componenti nei vincoli ognuno di essi viene rispettato, o analogamente quando gli scarti associati sono sempre positivi o nulli.

Interpretazione analitica[modifica | modifica sorgente]

Analiticamente un poliedro si definisce come P = \left \{ x \in  \mathbb{R}^n : 
Ax \le \ b
\right \}, cioè come insieme delle soluzioni di un sistema di m disequazioni lineari in n variabili.

La trattazione analitica dei poliedri è molto utile quando si considerano problemi aventi un grande numero di variabili, tale da non permettere di localizzare nello spazio tridimensionale i vincoli.

Se ad esempio il dominio del nostro problema primale è dato dal sistema


\begin{cases} x_1 - 5x_2 + 4x_3 \le \ -6 \\ -x_1 + 6x_3 - 2x_4 \le \ 0 \\ x_4 \le \ 9  \\  6x_1 - 6x_2  \le \ 17 \\ x_1 + x_2 + x_3 + x_4 \le \  8               \end{cases}

questo si può rappresentare nella forma  Ax \le \ b nel seguente modo:

 \begin{bmatrix} 1 & -5 & 4 & 0 \\ -1 & 0 & 6 & -2 \\ 0 & 0 & 0 & 1 \\ 6 & -6 &0 & 0 \\ 1 & 1 & 1 & 1  \end{bmatrix}   
 \cdot 
\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4     \end{bmatrix}
 
\le 

\begin{bmatrix} -6 \\ 0 \\ 9 \\ 17 \\ 8     \end{bmatrix}

Interpretazione geometrica[modifica | modifica sorgente]

Geometricamente un poliedro primale è l'intersezione di un numero finito di semispazi (detti semipiani, con n=2) chiusi, che però può essere anche l'insieme vuoto.

Questa affermazione appare più ovvia ricordando che la forma analitica ci dice che il poliedro è l'insieme delle soluzioni di un sistema di m disequazioni lineari in n variabili: infatti siccome un semispazio chiuso di  \mathbb{R}^n può essere descritto algebricamente come l'insieme delle soluzioni di una disequazione lineare in n variabili, appare evidente che un poliedro, sua intersezione, sarà l'insieme delle soluzioni di un sistema di disequazioni lineari.

Un poliedro P può essere limitato o illimitato, ma sarà sempre convesso, ovvero se contiene due punti, allora contiene anche tutto il segmento che ha essi come estremi. Infatti se ricordiamo che l'intersezione di due o più insiemi convessi è un insieme convesso allora dal momento che i semispazi chiusi sono insiemi convessi lo è anche il poliedro.

Un poliedro che è anche cono si chiama cono poliedrico (cono poliedrale) e si può interpretare come l'insieme delle soluzioni di un sistema omogeneo di disequazioni lineari.

Occorre fare una piccola precisazione linguistica: nella matematica il poliedro è in realtà un oggetto, intersezione di semispazi (con spazio in 3 dimensioni), appartenente allo spazio vero e proprio, cioè quello tridimensionale. In pratica il poliedro è un'estensione della nozione di poligono nel piano allo spazio usuale.

Per la precisione la famiglia di oggetti matematici che hanno le proprietà descritte poco prima, è quella, come già accennato, dei politopi; nella trattazione successiva continueremo comunque ad utilizzare il termine di poliedro.

Vertici e direzioni[modifica | modifica sorgente]

Se pensiamo ad un poligono, politopo in 2 dimensioni, possiamo vedere con semplicità come esso possieda alcuni elementi geometrici quali i lati-spigoli e i vertici: quando però si deve dare una definizione, non geometrica, di vertice di un poliedro, si incappa in alcune difficoltà.

Supponendo noti i concetti di insieme convesso, combinazione convessa e involucro convesso possiamo definire un vertice di un poliedro P come un punto che non può essere espresso come combinazione convessa propria di altri punti appartenenti a P.

In pratica un vertice di un poliedro è un punto di esso che non sta all'interno di un segmento appartenente al poliedro. L'insieme dei vertici di un poliedro P si indica con vert \left ( P \right )

Il concetto di vertice risulterà molto importante in seguito, quando tratteremo le metodologie di individuazione delle soluzioni ottime di problemi di programmazione lineare per problemi in forma primale standard.

Vediamo ora i concetti di direzione di recessione e linearità, utili per stilare alcune prime caratteristiche di poliedri e vertici.

Una direzione di recessione per un poliedro P è un vettore d tale che

 x + td \in P \quad \forall x \in P, \forall t \ge \ 0

In pratica un vettore d è una direzione di recessione per un poliedro se esso contiene tutte le semirette di direzione d uscenti da punti appartenenti a P.

L'insieme delle direzioni di recessione di P viene denotato con rec \left ( P \right ) .

È facile osservare che un poliedro limitato non ha direzioni (non nulle) di recessione.

Un altro concetto molto utile nello studio dei poliedri è quello della direzione di linearità: una direzione di linearità per un poliedro P è un vettore d tale che

\pm \ d \in rec \left ( P \right ).

Ciò significa che una direzione d è di linearità per un poliedro se esso contiene tutte le rette di direzione d passanti per punti appartenenti ad esso: l'insieme di tutte le direzioni di linearità di P viene denotato con lineal \left ( P \right ) .

Vediamo adesso un teorema che giustifica l'introduzione di questi due concetti: "Per ogni poliedro P non vuoto si ha che  vert \left ( P \right ) \ne \ \varnothing \iff lineal \left ( P \right ) = \left \{ 0 \right \} "

In pratica il teorema equivale a dire che condizione necessaria e sufficiente affinché un poliedro abbia vertici è che non contenga rette.

Il teorema di Weyl[modifica | modifica sorgente]

Vediamo adesso un importantissimo teorema di programmazione lineare, noto anche come teorema di rappresentazione dei poliedri, che ci permetterà di definire un poliedro tramite i concetti di involucro conico e involucro convesso di due sottoinsiemi di punti.

Formalmente:

Sia P un poliedro primale

se P non è vuoto

allora esistono un sottoinsieme finito di punti di P

 \quad \quad  V= \left \{ v^1, v^2, \ldots  , v^k \right \} ed un insieme finito di punti

 \quad \quad E= \left \{ e^1, e^2, \ldots
 , e^z \right \}, eventualmente anche vuoti, tali che

P = conv \left ( V \right ) + cono \left ( E \right )

In pratica quello che fa il teorema è "scaricare" la struttura del poliedro in una combinazione finita di punti appartenenti a due insiemi distinti.

Bisogna prestare molta attenzione alla somma che viene definita tra i due insiemi E e V: si tratta infatti di una somma diretta, cioè una somma in senso insiemistico, che è fatta da tutte le possibili somme di due elementi, uno di V ed uno di E. Quindi graficamente i punti del poliedro saranno quelli risultanti da tutte le possibili somme tra le combinazioni convesse dei punti di V e le combinazioni coniche degli elementi di E.

Esiste inoltre un utilissimo lemma su vertici e poliedri che ci garantisce che se il poliedro P ha vertici, tutti e soli gli elementi di un insieme O, allora V=O. In parole povere il lemma ci garantisce che nel caso in cui si scomponga un poliedro con vertici come garantito dal teorema di Weyl allora l'insieme di partenza per la combinazioni convesse è esattamente quello dei vertici.

Condizioni di ottimalità[modifica | modifica sorgente]

Vedremo adesso una serie di teoremi, definizioni e algoritmi che prima ci presenteranno le caratteristiche delle soluzioni ottime di un problema nel formato primale

\left ( P \right ) = \begin{cases} \max \quad cx \\
Ax \le \ b \end{cases}

e poi legheranno il concetto di punto ottimo al poliedro, accennando a come procedere per risolvere il suddetto problema di ottimizzazione.

Caratterizzazione elementare dell'ottimalità[modifica | modifica sorgente]

Presentiamo adesso un fondamentale teorema che ci presenta alcune caratteristiche fondamentali di una soluzione ottima di un problema di programmazione lineare nel caso primale:

Sia dato un problema in formato primale standard \left ( P \right ) = \begin{cases} \max \quad cx \\
Ax \le \ b \end{cases}

  • se c \ne \ 0 allora allora ogni soluzione ottima non è interna al poliedro
  • se P \ne \ \varnothing allora il problema ha un'unica soluzione ottima oppure ne ha infinite
  • Le soluzione ottime locali sono anche ottime globali

Osservazioni[modifica | modifica sorgente]

Quello che è stato appena enunciato è uno dei teoremi più importanti della programmazione lineare: esso consente infatti, di produrre una serie di semplificare lo studio e la ricerca delle soluzioni ottime di un problema in forma primale standard.

La prima tesi, che ci dice che solo in caso di funzioni costanti (facilissime da studiare), che hanno appunto gradiente nullo, è utilissima perché restringe la ricerca di punti ottimi solo ai bordi del poliedro, anche se vedremo in seguito che si potrà operare, in determinate condizioni, un'ulteriore semplificazione.

La seconda tesi è altrettanto importante, anche se più dal punto di vista concettuale che pratico: grazie ad essa infatti possiamo dire sempre quali sono tutte le soluzioni ottime di un problema primale. Infatti o siamo nel caso in cui c'è una sola soluzione, oppure in quello in cui ve ne sono infinite, cosicché l'eventuale richiesta di trovarle tutte cade nel vuoto.

Per finire osserviamo la terza tesi garantitaci dal teorema di caratterizzazione elementare dell'ottimalità: se una soluzione è un massimo locale, allora è anche una soluzione ottima globale. Ciò significa che se troviamo un punto del poliedro che è maggiore di tutti i punti in un suo intorno all'interno del dominio del problema, allora non è necessario fare altre verifiche, quel punto è ottimo! Analogamente alla prima tesi questa parte del teorema è estremamente utile per ridurre drasticamente la lunghezza del procedimento di ricerca degli ottimi.

Teorema fondamentale della PL[modifica | modifica sorgente]

Enunciato[modifica | modifica sorgente]

Il teorema più importante per risolvere problemi in forma primale standard, che ci dà una solida base teorica per trovare un procedimento di ricerca veloce e corretto per ottimizzare una funzione è il seguente:

Sia dato un problema in formato primale standard \left ( P \right ) = \begin{cases} \max \quad cx \\
Ax \le \ b \end{cases}

se

  • P \ne \ \varnothing
  • \left ( P \right )  < \ + \infty
  • P ha vertici

allora

Esiste almeno un vertice ottimo.

Osservazioni[modifica | modifica sorgente]

Un facile errore di interpretazione del teorema fondamentale della programmazione lineare è quello di considerare la tesi nel senso che tutti gli ottimi sono vertici: è bene ricordare come il teorema ci garantisca che uno dei vertici, anche se potrebbero essere due o più (anche tutti), è ottimo. Tra l'altro questa condizione è sufficiente per risolvere un problema primale, in quanto, ai fini della ricerca operativa non ci interessa trovare tutte le soluzioni ottime, ma una sola, ed inoltre per il teorema di caratterizzazione elementare dell'ottimalità le soluzione ottime locali di (P) sono anche ottime globali.

L'importanza del teorema è notevole, ma bisogna prestare attenzione ai casi nei quali non si può applicare, in pratica quando almeno una delle ipotesi non è rispettata:

  • Il poliedro può essere vuoto, ovvero ci sono troppi vincoli, non in senso solo numerico, ma anche solo perché in teoria bastano due semispazi per generare un'intersezione vuota
  • Il problema può non assumere un valore ottimo, ovvero la funzione può divergere verso valori positivi e infiniti
  • Il poliedro potrebbe non avere vertici, quindi perché quest'ipotesi sia verificata, P non deve contenere rette. Si può facilmente vedere che anche se P non ha vertici non è possibile escludere l'esistenza di un valore ottimo (che in questo caso sarebbe eventualmente raggiunto sull'insieme dei punti appartenenti ad una certa retta).

Basi e soluzioni di base[modifica | modifica sorgente]

Il teorema fondamentale della programmazione lineare indica la strada da seguire per ottimizzare problemi in forma primale standard: analizzare i vertici, dato che nelle condizioni determinate dalle ipotesi del suddetto teorema almeno uno di essi è v(P), cioè un ottimo.

Supponendo che il problema abbia ottimo finito, dominio non vuoto e almeno un vertice se si vuole scrivere un algoritmo che trovi una soluzione ottima è chiaro che per prima cosa è necessario avere a disposizione un procedimento per trovare, dato il poliedro P, i suoi vertici.

Geometricamente si potrebbe pensare che essi siano tutte le intersezioni tra i vincoli (semispazi chiusi) del problema, ma non è così, anche se in questo insieme ci sono anche i vertici: è necessario quindi introdurre il concetto di base.

Considerando un problema di programmazione lineare nella forma primale \left ( P \right ) = \begin{cases} \max \quad cx \\
Ax \le \ b \end{cases} chiameremo base un insieme B di n indici di riga,  B \subseteq \left \{ 1,2, \ldots m \right \}, tale che la sottomatrice quadrata di lato n A_B, ottenuta da A estraendo le righe con indici i \in B, sia invertibile, cioè  det(A_B) \ne \ 0.

La matrice A_B prende il nome di matrice di base, gli i \in B sono detti indici di base mentre si indicherà con N l'insieme degli m-n indici di riga (indici non di base) che non appartengono a B .

In pratica si prende un certo numero, n, di vincoli, e se ne fa l'intersezione costruendo la matrice con le righe corrispondenti agli indici: se la matrice così ottenuta è invertibile allora significa che i vincoli presi non erano paralleli, quindi che si intersecavano.

A questo punto si deve trovare la suddetta intersezione, e per farlo si calcola la soluzione del sistema di n equazioni in n incognite formato dalle righe di B; il sistema produrrà una soluzione, che prenderà il nome di soluzione di base. Questo punto, ottenuto tramite un'intersezione di vincoli, è candidato ad essere vertice: per controllare che lo sia veramente è necessario sostituire le coordinate del punto all'interno degli altri vincoli non utilizzati e vedere se esso risulta ammissibile per essi. Se il punto (la soluzione di base) risulta ammissibile per tutti i vincoli non di base allora il punto trovato prende il nome di soluzione di base ammissibile.

La procedura risulta facilmente intuibile pensando ad un poliedro in due dimensioni: si prendono tutti i vincoli (rette) a due a due (n=2) e si controlla, attraverso il determinante della relativa matrice, se si intersecano (se non sono rette parallele, quindi zero intersezioni, o coincidenti, con infiniti punti di intersezione); in caso affermativo si trova il punto, che è una soluzione di base. Per vedere se quest'ultima è anche ammissibile si guarda se rispetta gli altri vincoli, cioè se il punto appartiene al poligono corrispondente alla regione ammissibile.

La procedura descritta in precedenza permette di individuare tutti e soli i vertici del poliedro primale, infatti esiste un teorema che dice che condizione necessaria e sufficiente affinché un punto sia un vertice è che sia una soluzione di base ammissibile.

Per quanto riguarda i vertici esiste anche un'altra loro possibile classificazione: una soluzione di base (vertice) si dice degenere se soddisfa almeno un vincolo non di base con l'uguaglianza: gli altri vertici che non soddisfano tale proprietà vengono detti non degeneri. Ritornando all'esempio di poliedro in due dimensioni una soluzione di base degenere è un vertice individuato dall'intersezione di tre (n+1) o più rette.

Ecco la procedura analitica per trovare il vertice corrispondente ad una base data (n indici) per un problema del tipo \left ( P \right ) = \begin{cases} \max \quad cx \\
Ax \le \ b \end{cases} :

  1. Si costruisce da A la sottomatrice quadrata  A_B selezionando le n righe di B
  2. Si seleziona da b il vettore  b_B scegliendo le n righe di B
  3. Si suppone che  det(A_B) \ne \ 0
  4. Si calcola  {A_B}^{-1}
  5. La soluzione di base è  x = {A_B}^{-1} b_B
  6. x si dice:
    • Ammissibile se  A_i x \le \ b_i \ \forall i \in N
    • Non ammissibile se  \exist i \in N : A_i  x > \ b_i
  7. x si dice:
    • Degenere se  \exist i \in N : A_i x = b_i
    • Non degenere se  A_i x \ne \ b_i \ \forall i \in N

Algebra della PL[modifica | modifica sorgente]

Una volta trovati i vertici, per utilizzare il teorema fondamentale della programmazione lineare si deve vedere quali di essi sono soluzioni ottime del problema. Per fare questo serve un test di ottimalità, cioè un procedimento di verifica che, applicato ad un vertice, dica se esso può essere considerato un ottimo del problema; fondamento teorico necessario per arrivare a questo punto è quello della teoria delle dualità.

La teoria della dualità[modifica | modifica sorgente]

La dualità nella ricerca operativa può essere interpretata come una corrispondenza tra due problemi formalizzati in un modello di programmazione lineare. La forma di dualità più importante e più conosciuta è quella che associa due problemi di Programmazione Lineare (dualità lineare), ed è quella che serve per stabilire condizioni di ottimalità per problemi in forma primale standard; tuttavia esistono anche altri tipi di dualità: ad esempio, in presenza di problemi di programmazione quadratica si parla di dualità quadratica, mentre in presenza di problemi di Programmazione lineare intera si parla di dualità lagrangiana.

La coppia di problemi che studieremo è la seguente:

Problema primale standard
Problema duale standard
\max \sum_{i=1}^n c_i x_i \min \sum_{j=1}^m y_j b_j (funzione obiettivo)
\sum_{i = 1}^n a_{1,i} x_i \leq b_1 \sum_{j = 1}^m y_j a_{j,1} = c_1
\dots \dots (vincoli)
\sum_{i = 1}^n a_{m,i} x_i \leq b_m \sum_{j = 1}^m y_j a_{j,n} = c_n
y_j \geq 0 \qquad j = 1, \dots, m

Quindi se consideriamo un problema di PL in formato primale standard possiamo associarvi un problema di PL in una forma duale standard; sfruttando i concetti di matrici e vettori possiamo scrivere questa corrispondenza così:

 \begin{cases} \max \quad cx \\
Ax \le \ b \end{cases}
 \begin{cases} \min \quad yb \\
yA = \ c  \\ y \ge \ 0 \end{cases}

Ai fini della creazione di un test di ottimalità introduciamo solamente alcuni brevi elementi teorici a propositi del problema duale standard (rimandando la trattazione alla pagina apposita):

  • mentre il problema in forma primale standard si scriveva con (P), quello in forma duale standard si scrive (D)
  • il valore ottimo del duale è indicato con v(D)
  • il poliedro duale è definito come:  D = \left \{ yA = c  , \ \ y \ge \ 0  \right \}
  • per minimizzare il problema duale si ricercano delle soluzioni di base (avendo una base B),

che saranno quelle trovate risolvendo il sistema prendendo solo le variabili relative agli indici in base (e le altre nulle), o analogamente le componenti del vettore c {A_B}^{-1} e y_N = 0

  • le soluzioni di base, relative ad una base B, possono essere ammissibili, nel caso rispettino \forall i \in B \ y_i \ge \ 0, prendendo il nome di vertici del poliedro duale
  • I vertici duali possono essere degeneri o no, nel caso rispettino o meno la condizione \exist i \in B : \ y_i = 0

Un'importante proprietà dei problemi duali lineari è che il duale del duale è il primale, cioè riconducendo il problema duale alla forma primale e applicando la corrispondenza di cui sopra si riotterrà una formulazione equivalente del problema primale.

Questo significa che l'operazione di associazione primale-duale è un'operazione involutoria, cioè se applicata a se stessa torna la situazione di base.

Ottimalità duale e primale[modifica | modifica sorgente]

Grazie alle conoscenze acquisite in precedenza adesso si è in grado di formulare il procedimento che dice quali vertici del problema primale standard sono soluzioni ottime; esiste infatti un teorema che ci garantisce le condizioni sufficienti di ottimalità per soluzioni di base (non soli del problema primale ma anche di quello duale): date due soluzioni di base \ x \in P, \ \ y \in D si ha che se esse sono ammissibili (sono vertici dei rispettivi poliedri) rispettivamente per (P) e (D) allora sono ottime rispettivamente per (P) e (D).

La dimostrazione di questo fondamentale teorema prevede la conoscenza di un importantissimo teorema della programmazione lineare, molto utile per costruire i fondamenti teorici dell'algoritmo del simplesso, il teorema degli scarti complementari.

Ora siamo in grado di formulare il procedimento che ci dice quali vertici siano soluzioni ottime, ovvero possiamo scrivere il cosiddetto test di ottimalità: dato un problema in forma primale (P) e l'associato problema duale (D) e dato un vertice x \in P si opera così:

  • Si trova la soluzione di base duale con la stessa base usata per x, soluzione che chiameremo y
  • Se y è una soluzione di base ammissibile allora x è ottima per il problema primale (e anche y per il duale)

Come si vede il procedimento semplifica moltissimo le operazioni da fare per massimizzare un problema in forma primale, ma è comunque assai lungo perché richiede, nel peggior caso, tante verifiche di ottimalità quanti sono i vertici, e nel caso medio (per problemi con moltissimi vincoli e variabili) un numero improponibile operativamente di passi.

Se allora ai fini pratici il test di ottimalità, pur essendo molto utile, necessita di conoscere in teoria tutti i vertici del poliedro in questione, o comunque una gran parte, e dal momento che nei problemi di produzione industriale vengono fuori moltissimi vincoli e moltissimi vertici, bisogna trovare un modo intelligente per procedere tra i vertici del poliedro, e questo sarà proprio l'algoritmo del simplesso primale, caso particolare del simplesso generico.

Voci correlate[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica