Mostriamo ora che possiamo ridurci senza perdita di generalit`a a studiare problemi di pro-grammazione lineare di una forma particolare, detta forma standard:
max cTx (1.4)
s.a Ax = b (1.5)
x ≥0, (1.6)
dove A ∈ Rm×n, c ∈ Rn, b ∈ Rm sono i dati del problema e x ∈ Rn`e il vettore delle variabili. Si noti che la scrittura Ax = b `e un modo compatto di indicare il sistema di m equazioni lineari aTix = bi per i = 1, . . . , m (in altre parole, ai1x1+ ⋅ ⋅ ⋅ + ainxn=bi per i = 1, . . . , m).
Due programmi lineari P1 e P2 sono detti equivalenti quando, per ogni α ∈ R, P1 ha una soluzione ammissibile di costo α se e solo se P2 ha una soluzione ammissibile di costo α. In particolare, se P1 e P2 sono programmi lineari equivalenti, si verifica immediatamente che valgono le seguenti propriet`a:
P1 ha una soluzione ammissibile se e solo se P2 ha una soluzione ammissibile;
per ogni α ∈ R, P1 ha una soluzione ottima di costo α se e solo se P2 ha una soluzione ottima di costo α;
P1 `e illimitato se e solo se P2 `e illimitato.
Proposizione 1.2 Ogni programma lineare `e equivalente ad un programma lineare in forma standard.
Dimostrazione. Consideriamo un generico problema di programmazione lineare, che avr`a dunque la forma (1.1)–(1.3), e mostriamo come esso sia equivalente ad un problema in forma standard.
Si noti anzitutto che se (1.1)–(1.3) `e un problema di minimizzazione (vogliamo cio`e deter-minare min cTx), tale problema `e equivalente al programma lineare in cui la (1.1) `e sostituita da − max −cTx. Pertanto possiamo assumere senza perdita di generalit`a che (1.1)–(1.3) sia un problema di massimizzazione.
1.2. PROBLEMI IN FORMA STANDARD 3 Diciamo che una variabile xj`e una variabile non-negativa se il sistema (1.2)–(1.3) contiene esplicitamente il vincolo xj≥0; altrimenti la variabile `e detta libera. Nel passaggio alla forma standard sar`a utile trattare le variabile non-negative e quelle libere in modo diverso.
Consideriamo una disuguaglianza della forma aTix ≥ bi che non sia un vincolo di non-negativit`a su una variabile. Tale disuguaglianza `e equivalente a −aTix ≤ −bi. Ne segue che possiamo assumere che ciascun vincolo del problema (eccetto quelli che impongono la non-negativit`a di qualche variabile) sia del tipo aTix ≤ bi o aTix = bi.
Consideriamo ora un vincolo della forma aTix ≤ bi. Aggiungiamo al problema una variabile di scarto (o di slack) si, e rimpiazziamo il vincolo precedente con i seguenti:
aTix+ si=bi, si≥0. (1.7)
Si noti che se x soddisfa aTix ≤ bi, allora, ponendo si =bi− aTix, le condizioni (1.7) risultano verificate. Viceversa, se x ed si soddisfano (1.7), allora x soddisfa il vincolo di partenza aTix ≤ bi. Pertanto, poich´e non abbiamo modificato la funzione obiettivo, il problema cos`ı ottenuto `e equivalente a quello di partenza.
Abbiamo finora dimostrato che ogni programma lineare `e equivalente ad un programma lineare di massimizzazione in cui tutti i vincoli (eccetto quelli che impongono la non-negativit`a di qualche variabile) sono equazioni. Per arrivare ad un problema in forma standard, dobbia-mo per`o avere il vincolo di non-negativit`a su tutte le variabili. Resta dunque da capire come gestire le variabili libere.
Supponiamo che la variabile xj sia libera. Basandoci sulla semplice osservazione che ogni numero reale pu`o essere scritto come differenza di due numeri non-negativi, introduciamo due variabili non-negative (x′j e x′′j) ed imponiamo i vincoli
xj =x′j− x′′j, x′j, x′′j ≥0.
Inoltre, sostituiamo xj con x′j− x′′j nella funzione obiettivo e in tutti i vincoli del problema.
Otteniamo cos`ı un programma lineare in cui xj non compare e le nuove variabili introdotte sono non-negative. Il problema che ricaviamo `e equivalente a quello di partenza: data una soluzione ammissibile del nuovo problema, otteniamo una soluzione ammissibile del problema originario con lo stesso costo ponendo xj =x′j− x′′j; viceversa, data una soluzione ammissibile del problema di partenza, otteniamo una soluzione ammissibile del nuovo problema con lo stesso costo scegliendo valori non-negativi per x′j e x′′j tali che xj =x′j − x′′j (possiamo porre, ad esempio, x′j =max{0, xj} e x′′j =max{0, −xj}).
Ci siamo dunque ridotti ad un problema in forma standard equivalente a quello iniziale.
◻ Si noti che, oltre a mostrare che un qualunque programma lineare P1 `e equivalente ad un programma lineare P2 in forma standard, la dimostrazione della proposizione precedente ci dice come da una soluzione di P2 di costo α possiamo ricavare una soluzione di P1 di costo α.
In particolare, da una soluzione ottima di P2 possiamo ricavare una soluzione ottima di P1. Dunque il fatto di restringersi ai soli problemi in forma standard non pone alcuna limitazione alla generalit`a della trattazione.
Capitolo 2
Geometria della Programmazione Lineare
In questo capitolo verranno introdotte alcune nozioni della teoria dei poliedri che permet-teranno di cogliere gli aspetti geometrici della Programmazione Lineare e del suo algoritmo risolutivo pi`u noto, trattato nel capitolo successivo.
2.1 Insiemi convessi e poliedri
Un semispazio chiuso in Rn`e un insieme della forma {x ∈ Rn∶ aTx ≤ β}, dove a ∈ Rn∖ {0} e β ∈ R. Scritto per esteso, un semispazio chiuso `e l’insieme dei punti di Rn che soddisfano una disequazione del tipo a1x1+ ⋅ ⋅ ⋅ + anxn≤β.
Un poliedro in Rn `e l’intersezione di un numero finito di semispazi chiusi. In altre parole, un poliedro `e un insieme che pu`o essere scritto nella forma {x ∈ Rn∶ Ax ≤ b}, dove A ∈ Rm×n e b ∈ Rm. Si noti che la regione ammissibile di un qualunque problema di programmazione lineare `e un poliedro (eventuali vincoli scritti sotto forma di equazioni possono essere sostituiti ciascuno con una coppia di disequazioni opposte).
Un insieme K ⊆ Rn si dice convesso se, per ogni coppia di punti y, z ∈ K, il segmento di retta che congiunge y e z `e contenuto in K, cio`e se λy + (1 − λ)z ∈ K per ogni scelta di y, z ∈ K e λ ∈[0,1].
Proposizione 2.1 Valgono le seguenti propriet`a:
(i) Ogni semispazio chiuso `e convesso.
(ii) L’intersezione di insiemi convessi `e un insieme convesso.
(iii) Ogni poliedro `e convesso.
Dimostrazione. (i) Sia S il semispazio chiuso definito dalla disequazione aTx ≤ β e scegliamo arbitrariamente y, z ∈ S e λ ∈[0,1]. Allora
aT(λy + (1 − λ)z) = λaTy+(1 − λ)aTz ≤ λβ+(1 − λ)β = β,
dove la disuguaglianza vale perch´e y, z ∈ S, λ ≥ 0 e 1 − λ ≥ 0. Dunque λy +(1 − λ)z ∈ S, da cui segue che S `e convesso.
5
(ii) Per semplicit`a di scrittura diamo la dimostrazione per il caso in cui vengono intersecati due insiemi convessi, ma l’argomento `e identico per il caso di pi`u insiemi convessi (anche se non in numero finito). Siano K1e K2due insiemi convessi e definiamo K = K1∩K2. Scegliamo arbitrariamente y, z ∈ K e λ ∈[0,1]. Allora il punto λy + (1 − λ)z appartiene sia a K1 che a K2 (in quanto questi due insiemi sono convessi) e dunque a K. Ne segue che K `e convesso.
(iii) Poich´e un poliedro `e l’intersezione di un numero finito di semispazi chiusi, il risultato
segue dalle propriet`a (i) e (ii). ◻
Chiudiamo questa sezione con una definizione. Un punto x ∈ Rn `e detto combinazione convessa dei punti y, z ∈ Rn se x `e contenuto nel segmento di retta che congiunge y e z, cio`e se esiste λ ∈[0,1] tale che x = λy + (1 − λ)z. Se, inoltre, x ≠ y e x ≠ z, allora si dice che x `e combinazione convessa propria di y e z; si noti che in tal caso si ha necessariamente λ ∈]0,1[.