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 a 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 è
Che può essere scritto in forma scalare come
{|cellspacing = 4
|align=right|(funzione obiettivo)
|align=right|(vincoli)
Quindi il problema primale standard è costituito da una certa funzione che va massimizzata, la funzione obiettivo, e 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 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: 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:
Ovvero come il prodotto scalare tra il vettore colonna delle variabili x, di dimensione e il vettore riga (poi trasposto) dei coefficienti c (in genere "costi") della funzione obiettivo, di dimensione .
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:
Ad esempio se consideriamo la funzione obiettivo in 4 variabili
la sua rappresentazione come prodotto scalare sarà
Il poliedro primale L'insieme dei punti (vettori) che sono ammissibili per il problema in formato primale standard, cioè quelli che soddisfano tutti i vincoli del tipo 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 è
{|cellspacing = 4
Nella scrittura A è una matrice, detta matrice tecnologica, che ha dimensione , 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 può essere infatti reso con due vincoli di disuguaglianza:
A destra del simbolo di minore o uguale troviamo il vettore b, si tratta del cosiddetto vettore dei termini noti, di dimensione , 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:
Dove con 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 Analiticamente un poliedro si definisce come , 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
questo si può rappresentare nella forma nel seguente modo:
Interpretazione geometrica 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 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 a utilizzare il termine di poliedro.
Vertici e direzioni Se pensiamo a 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
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
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 .
È 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
.
Ciò significa che una direzione d è di linearità per un poliedro se esso contiene tutte le rette di direzione d passanti per punti appartenenti a esso: l'insieme di tutte le direzioni di linearità di P viene denotato con .
Vediamo adesso un teorema che giustifica l'introduzione di questi due concetti: "Per ogni poliedro P non vuoto si ha che "
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 Vediamo adesso un importante 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 un poliedro primale
se P non è vuoto
allora esistono un sottoinsieme finito di punti di e un insieme finito di direzioni di recessione , eventualmente anche vuoti, tali che
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 : 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 e uno di . Quindi graficamente i punti del poliedro saranno quelli risultanti da tutte le possibili somme tra le combinazioni convesse dei punti di e le combinazioni coniche degli elementi di .
Esiste inoltre un altro lemma molto utile su vertici e poliedri che ci garantisce che se il poliedro ha vertici, tutti e soli gli elementi di un insieme , allora . 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.
Possiamo definire anche il teorema di Minkowski-Weyl, che afferma che ogni poliedro sia finitamente generato ed ogni insieme finitamente generato sia un poliedro. Più precisamente, per due sottoinsiemi denota la somma di Minkowski di
Il teorema afferma che: per un sottoinsieme P \in R^d, le seguenti affermazioni siano equivalenti:
a) è un poliedro, i.e. per qualche matrice reale (finita) ed un vettore reale ,
b) Ci sono vettori reali e tali che
Pertanto, ogni poliedro ha due rappresentazioni del tipo (a) e (b), note rispettivamente come rappresentazione H (semispazio) e rappresentazione V (vertice). Un poliedro dato da una rappresentazione H (rappresentazione V) è detto poliedro H (poliedro V).
Condizioni di ottimalità Vedremo adesso una serie di teoremi, definizioni e algoritmi che prima ci presenteranno le caratteristiche delle soluzioni ottime di un problema nel formato primale
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à 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
se allora ogni soluzione ottima non è interna al poliedro se allora il problema ha un'unica soluzione ottima oppure ne ha infinite Le soluzioni ottime locali sono anche ottime globali
Osservazioni