Problema primale standard

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 è

$\left(P\right):{\begin{cases}\max \quad c^{T}x\\Ax\leq \ 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, 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: $minf(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) dei coefficienti c (in genere "costi") della funzione obiettivo, 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

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\leq \ 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\leq \ 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)\leq \ 0\\-g\left(x\right)\leq \ 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

Analiticamente un poliedro si definisce come $P=\left\{x\in \mathbb {R} ^{n}:Ax\leq \ 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}\leq \ -6\\-x_{1}+6x_{3}-2x_{4}\leq \ 0\\x_{4}\leq \ 9\\6x_{1}-6x_{2}\leq \ 17\\x_{1}+x_{2}+x_{3}+x_{4}\leq \ 8\end{cases}}$

questo si può rappresentare nella forma $Ax\leq \ 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}}\leq {\begin{bmatrix}-6\\0\\9\\17\\8\end{bmatrix}}$

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 $\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 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 $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\geq \ 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 a 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)\neq \ \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

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\}$ e un insieme finito di direzioni di recessione

$\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 e 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à

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\leq \ 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à

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\leq \ b\end{cases}}$

• se $c\neq \ 0$ allora ogni soluzione ottima non è interna al poliedro

• se $P\neq \ \varnothing$ allora il problema ha un'unica soluzione ottima oppure ne ha infinite

• Le soluzioni ottime locali sono anche ottime globali

Dimostrazione

Dal momento che ci sono tre tesi allora dobbiamo fare tre separate dimostrazioni:

• Se una soluzione ottima fosse interna al poliedro allora il gradiente della funzione obiettivo dovrebbe essere nullo per il teorema di Fermat; ma poiché il gradiente della funzione è $\nabla \ cx=c$ , c appunto, allora questo è falso a meno che c sia 0.

• Cerchiamo di arrivare a dire che nel caso in cui ci sia più di una soluzione ottima, ad esempio 2, allora ce ne sono infinite.Chiamiamo le due generiche soluzioni ottime del problema $\left(P\right)$ $x_{1},x_{2}$.
  Poiché il poliedro primale P è convesso, per sua stessa definizione di intersezione di semispazi chiusi(convessi), allora per la definizione di convessità presi due qualsiasi punti appartenenti a questo insieme convesso, l'insieme contiene tutto il segmento che li unisce.
  Scriviamo analiticamente questa condizione per P e i suoi punti $x_{1},x_{2}:\quad tx_{1}+(1-t)x_{2}\in P\quad \forall t\in [0,1]$.
  Adesso scriviamo i valori che la funzione obiettivo cx assume, e deve assumerli in quanto i punti appartengono al poliedro, sui punti di uno dei suddetti segmenti e poi sviluppiamo: $\quad \quad c(tx_{1}+(1-t)x_{2})=tcx_{1}+(1-t)cx_{2}$.
  Essendo però $x_{1}$ e $x_{2}$ due soluzioni ottime, allora la funzione obiettivo su di esse deve assumere gli stessi valori, cioè $\quad \quad cx_{1}=cx_{2}$ , eguaglianza che sfruttiamo nell'espressione di prima: $\quad \quad tcx_{1}+(1-t)cx_{1}=tcx_{1}+cx_{1}-tcx_{1}=cx_{1}$
  Abbiamo quindi trovato che la funzione obiettivo assume gli stessi valori delle soluzioni ottime, cioè valori ottimi, su tutti gli infiniti punti del segmento analizzato, per cui ci sono infinite soluzioni ottime.

• Ragioniamo per assurdo: supponiamo che esista un punto del poliedro che sia soluzione massima locale ma non globale, e chiamiamolo z; allora esso, in quanto massimo locale, oltre un certo intorno sarà minore di almeno un punto appartenente al poliedro, ovvero $\exists \ x\in P:cx>\ cz$.
  Consideriamo adesso il segmento che unisce i due punti di cui sopra, che chiameremo ${\overline {xz}}$: poiché il poliedro primale è sempre convesso e gli estremi del segmento considerato appartengono entrambi a P, allora ${\overline {xz}}\in P$, che equivale a scrivere $tx+(1-t)z\in P\quad \forall t\in [0,1]$.
  A questo punto studiamo il comportamento della funzione obiettivo lungo tutti i punti di questo segmento: $c(tx+(1-t)z)=tcx+(1-t)cz$.
  In precedenza avevamo ricavato $cx>\ cz$, quindi possiamo utilizzarlo in quanto scritto prima: $tcx+(1-t)cz\Rightarrow \ tcx+(1-t)cz>\ tcz+(1-t)cz=tcz+cz-tcz=cz$.
  L'espressione appena ricavata ci dice che in ogni punto del segmento, tranne z, la funzione obiettivo assume un valore maggiore di quanto faccia in z, ovvero: $\forall x\in {\overline {xz}},x\neq \ z\quad cx>\ cz$
  Ma da questa affermazione discende che in ogni intorno di z lungo un certo segmento la funzione obiettivo cresce, quindi z non può essere una soluzione ottima locale: questo contraddice l'ipotesi e quindi, dal momento che abbiamo proceduto per assurdo, la nostra tesi è dimostrata.

Osservazioni

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

La prima tesi ci dice che se la funzione obiettivo non è costante, la soluzione ottima si trova sulla frontiera del poliedro. Infatti, se la funzione è costante, il gradiente c = 0. È 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 a 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

Enunciato

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\leq \ b\end{cases}}$

se

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

allora

Esiste almeno un vertice ottimo.

Dimostrazione

Per iniziare consideriamo un generico punto $x\in P$, che, grazie al teorema di Weyl, possiamo scrivere tramite i concetti di combinazione conica e di combinazione convessa, ovvero

$x=\sum _{i=1}^{k}\lambda _{i}v_{i}\ +\ \sum _{j=1}^{z}\mu _{j}e_{j}$

Ricordiamo anche che per definizione

$\sum _{i=1}^{k}\lambda _{i}=1,\lambda _{i}\in \left[0,1\right]\ \forall i\in \left\{1,2.....k\right\}$

$\mu _{j}\geq \ 0\ \ \forall j\in \left\{1,2.....z\right\}$

Poiché la tesi ci richiede una relazione con una soluzione ottima del problema di PL, scriviamo la funzione obiettivo di esso nel nostro generico punto:

$cx=c\left(\sum _{i=1}^{k}\lambda _{i}v_{i}\ +\ \sum _{j=1}^{z}\mu _{j}e_{j}\right)=$ $c\sum _{i=1}^{k}\lambda _{i}v_{i}\ +\ c\sum _{j=1}^{z}\mu _{j}e_{j}=$ $\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ +\ \sum _{j=1}^{z}\mu _{j}\left(ce_{j}\right)$

Il primo e il secondo passaggio sono stati possibili grazie alla proprietà di linearità del prodotto scalare, e poi grazie a quella distributiva.

Dopo aver "scaricato" la struttura del problema in una combinazione finita di punti analizziamo con precisione questa espressione.

Guardando tutti i prodotti scalari (supponendo che esistano) presenti nelle sommatorie, moltiplicati per coefficienti non negativi qualunque, posso pensare di trovare i secondi, quelli derivati dalla combinazione conica, aventi segno positivo, ovvero $\exists \ \left(ce_{j}\right)>\ 0$.

A questo punto potrei pensare anche di trovare il corrispondente coefficiente $\mu _{j}$: ma siccome esso come unico limite ha quello di essere non negativo, posso immaginarlo talmente grande da mandare la sommatoria a valori infinitamente grandi, ovvero $\mu _{j}\to \ +\infty \ \ \Rightarrow \ \ \ \sum _{j=1}^{z}\mu _{j}\left(ce_{j}\right)\to \ +\infty$.

Adesso osserviamo che la sommatoria $\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)$ non può essere mandata a valori grandissimi (negativi), per "compensare" l'altra: questo si deve al fatto che i suoi coefficienti sono limitati con $\sum _{i=1}^{k}\lambda _{i}=1,\lambda _{i}\in \left[0,1\right]\ \forall i\in \left\{1,2.....k\right\}$.

Questa situazione ci porta a dire che nel caso in cui si mandi a grandi valori la prima sommatoria la funzione obiettivo diventa: $cx=\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ +\ \sum _{j=1}^{z}\mu _{j}\left(ce_{j}\right)=\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ +\infty =+\infty$

Questo però contraddice l'ipotesi $\left(P\right)<\ +\infty$.

Quindi l'unico modo per "uscire" da questo problema è assumere $ce_{j}\leq \ 0\ \ \forall j\in \left\{1,2.....z\right\}$; infatti, come già detto, basterebbe che anche uno solo fosse positivo per poter benissimo agire sul suo relativo $\mu _{j}$ per massimizzarne il valore e far "schizzare" la funzione obiettivo all'infinito.

A questo punto torno a osservare la tesi che dobbiamo dimostrare: dal momento che si cerca di trovare una soluzione ottima, cerchiamo di massimizzare la funzione obiettivo per il problema ${\begin{cases}\max \quad cx\\Ax\leq \ b\end{cases}}$

Avendo quindi da massimizzare $\quad cx=\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ +\ \sum _{j=1}^{z}\mu _{j}\left(ce_{j}\right)$; la seconda sommatoria è fatta da addendi non positivi, poiché i coefficienti sono tutti non negativi per definizione, e i prodotti scalari tutti non positivi per quanto detto in precedenza. Se si massimizza una somma di termini non positivi, il risultato è ovviamente che essa diventa nulla, cioè si assume $\mu _{j}=0\ \ \forall j\in \left\{1,2.....z\right\}$.

Alla luce di questa operazione scriviamo: $max\ \ cx=max\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ +\ max\sum _{j=1}^{z}\mu _{j}\left(ce_{j}\right)=max\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ +0$

Il passo successivo è togliere la sommatoria sviluppandola: $max\ \ cx=max\sum _{i=1}^{k}\lambda _{i}\left(cv_{i}\right)\ =max\ \left\{\lambda _{1}\left(cv_{1}\right)+\lambda _{2}\left(cv_{2}\right)+\ldots \lambda _{k}\left(cv_{k}\right)\right\}$, dove ricordiamo che i k prodotti scalari sono numeri veri e propri.

Di questi k numeri prendiamo il maggiore, che chiamiamo $\quad cv_{\bar {k}}$, ovvero $cv_{\bar {k}}=max\ \left(cv_{i}\right)\forall i\in \left\{1,2.....k\right\}$.

Quindi se sostituiamo questo prodotto scalare al posto di tutti gli altri k, sicuramente otterremo una maggiorazione della sommatoria, cioè $max\ \ cx=max\ \left\{\lambda _{1}\left(cv_{1}\right)+\lambda _{2}\left(cv_{2}\right)+\ldots \lambda _{k}\left(cv_{k}\right)\right\}\leq \ max\ \left\{\lambda _{1}\left(cv_{\bar {k}}\right)+\lambda _{2}\left(cv_{\bar {k}}\right)+\ldots \lambda _{k}\left(cv_{\bar {k}}\right)\right\}$

Adesso sviluppiamo la somma ricordando che $\sum _{i=1}^{k}\lambda _{i}=1$ :

$max\ \left\{\lambda _{1}\left(cv_{\bar {k}}\right)+\lambda _{2}\left(cv_{\bar {k}}\right)+\ldots \lambda _{k}\left(cv_{\bar {k}}\right)\right\}=$

$max\ \left\{\left(cv_{\bar {k}}\right)\cdot \left(\lambda _{1}+\lambda _{2}+\ldots \lambda _{k}\right)\right\}=$

$max\ \left\{\left(cv_{\bar {k}}\right)\cdot 1\right\}=$

$max\ cv_{\bar {k}}$

Ma dal momento che $cv_{\bar {k}}$ è un numero preciso, costante, la sua massimizzazione è se stesso, cioè $\quad max\ cv_{\bar {k}}=cv_{\bar {k}}$

Sfruttando quindi il fatto che questo valore era maggiore del valore in un generico punto della funzione obiettivo si può scrivere che $max\ cx\leq \ cv_{\bar {k}}$.

Possiamo ora sfruttare un lemma associato al teorema di Weyl che ci garantiva che se il poliedro P ha vertici, tutti e soli gli elementi di un insieme O, allora V = O, cioè il sottoinsieme di punti di cui si cerca l'involucro convesso è quello che contiene i vertici. Alla luce di questo si deduce che $V=\left\{v_{1},v_{2}\ldots v_{k}\right\}=\left\{vertici\right\}$; da questo si trova infine: $v_{\bar {k}}\in V\rightarrow \ v_{\bar {k}}\in \left\{vertici\right\}$.

Abbiamo quindi scoperto che $v_{\bar {k}}$ è uno dei vertici del poliedro primale.

Consideriamo adesso la funzione obiettivo: essa, in quanto funzione definita su un certo dominio, segue la regola per cui il valore che assume in un generico punto è sicuramente uguale o minore al massimo dei valori che può assumere, analiticamente $f(x)\leq \ max\ f(x)\ \ \forall x\in D$; questo, considerando che la nostra funzione cx è definita sul poliedro primale P significa che $cx\leq \ max\ cx\ \ \forall x\in P$.

Questa proprietà vale anche per $\quad v_{\bar {k}}$, che in quanto vertice appartiene al poliedro; quindi si ha che $\quad cv_{\bar {k}}\leq \ max\ cx\ \ \forall x\in P$.

Per concludere è sufficiente mettera a sistema le due disuguglianze trovate: $\quad cv_{\bar {k}}\leq \ max\ cx$ e $\quad max\ cx\leq \ cv_{\bar {k}}$. Appare chiaro come affinché esse valgano contemporaneamente deve risultare $\quad max\ cx=cv_{\bar {k}}$.

Abbiamo così provato la nostra tesi, esiste un vertice del poliedro che è soluzione ottima del problema primale standard.

Osservazioni

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, e inoltre per il teorema di caratterizzazione elementare dell'ottimalità le soluzioni 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 a una certa retta).

Basi e soluzioni di base

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\leq \ 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})\neq \ 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 a 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 a 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 a una base data (n indici) per un problema del tipo $\left(P\right)={\begin{cases}\max \quad cx\\Ax\leq \ 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})\neq \ 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\leq \ b_{i}\ \forall i\in N$
   • Non ammissibile se $\exists i\in N:A_{i}x>\ b_{i}$
7. x si dice:
   • Degenere se $\exists i\in N:A_{i}x=b_{i}$
   • Non degenere se $A_{i}x\neq \ b_{i}\ \forall i\in N$

Algebra della PL

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 a 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à

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\leq \ b\end{cases}}$

${\begin{cases}\min \quad yb\\yA=\ c\\y\geq \ 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\geq \ 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 a una base B, possono essere ammissibili, nel caso rispettino $\forall i\in B\ y_{i}\geq \ 0$, prendendo il nome di vertici del poliedro duale
• I vertici duali possono essere degeneri o no, nel caso rispettino o meno la condizione $\exists 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

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.

Dimostrazione

Alla luce del teorema degli scarti complementari, che ci garantisce che se si hanno $\ {\bar {x}}\in P,\ \ {\bar {y}}\in D$, ammissibili rispettivamente per (P) e (D), allora si ha che esse sono ottime se e solo se ${\bar {y}}\left(b-A{\bar {x}}\right)=0$.

Quindi per dimostrare la tesi basta dimostrare che dati due vertici, primale e duale (associati), essi soddisfano sempre ${\bar {y}}\left(b-A{\bar {x}}\right)=0$, e quindi sono ottime.

Prendiamo due generiche soluzioni di base ammissibili, ${\breve {x}}\in P,\quad {\breve {y}}\in D$; sappiamo, per la struttura dei vertici duali, che ${\breve {y}}=\left({\breve {y}}_{B},{\breve {y}}_{N}\right)=\left({\breve {y}}_{B},0\right)$ perché le variabili corrispondenti agli indici non in base sono nulle. Sappiamo inoltre che il vettore di tali soluzioni è un vettore riga di dimensione $1\times m$.

Adesso consideriamo gli scarti della generica soluzione, ammissibile, del problema primale standard: essi saranno del tipo ${S_{B} \choose S_{N}}$, cioè un vettore colonna, di dimensione $m\times 1$, con gli scarti generati dai vincoli in base e da quelli non in base. Ma dal momento che sappiamo che gli scarti di base di una soluzione di base sono nulli (essendo il vertice di P ottenuto proprio dal sistema che annulla la matrice con le righe corrispondenti agli indici di base), allora il vettore degli scarti diventa ${0 \choose S_{N}}$.

A questo punto possiamo vedere se ${\breve {y}}\left(b-A{\breve {x}}\right)=0$: operazione possibile dal momento che il vettore delle soluzioni del primale ha m componenti, n in base e le altre altri no, e analogamente gli scarti del primale $\left(b-A{\breve {x}}\right)={S_{B} \choose S_{N}}$ sono uno per vincolo, m , e n di questi sono scarti di base.

Svolgiamo quindi il prodotto riga-colonna che ci interessa: ${\breve {y}}\left(b-A{\breve {x}}\right)=\left({\breve {y}}_{B},{\breve {y}}_{N}\right)\cdot {S_{B} \choose S_{N}}=\left({\breve {y}}_{B},0\right)\cdot {0 \choose S_{N}}=0$. Abbiamo così dimostrato, per il teorema degli scarti complementari, la tesi.

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

• Ricerca operativa
• Programmazione lineare
• Simplesso
• Simplesso primale