LA PROGRAMMAZIONE LINEARE

Franca Rinaldi

Dipartimento di Matematica e Informatica

Universita degli Studi di Udine

A.A. 2005 / 2006

1 Introduzione

In un problema di programmazione lineare (PL) si vuole ottimizzare, cioe

minimizzare o massimizzare, una funzione obiettivo lineare

cx =n∑j=1

cjxj

sotto il vincolo che il vettore di variabili x = (x1, . . . , xn) ∈ IRn soddisfi un

assegnato insieme finito di vincoli lineari

Aix =n∑j=1

Aijxj ≤ (=, ≥) bi i = 1, . . . ,m.

L’importanza della programmazione lineare nell’ambito dell’ottimizzazione

si deve a due aspetti fondamentali. Da un lato la PL offre un modello for-

male per una ampia varieta di problemi che emergono in ambito applicativo,

ed in particolare nel contesto della gestione dei sistemi di produzione, di

distribuzione, di trasporto ecc., dall’altro rappresenta un elemento centrale

nella definizione di approcci risolutivi per problemi di programmazione li-

neare intera, e quindi, in particolare, per una larga varieta di problemi di

ottimizzazione combinatoria NP -hard.

2 Forme canoniche

Un problema di PL puo essere espresso senza perdita di generalita in una

delle due forme

forma canonica : min cx (1)

Ax ≥ b (2)

x ≥ 0 (3)

forma standard min cx (4)

Ax = b (5)

x ≥ 0 (6)

dove A e una matrice m×n detta matrice dei vincoli, c ∈ IRn e il vettore dei

costi e b ∈ IRm il vettore dei termini noti.

La riformulazione di un generico problema di programmazione lineare P in

forma canonica utilizza le seguenti semplici operazioni:

1

- ogni vincolo Aix ≤ bi viene riscritto nella forma −Aix ≥ −bi;

- ogni vincolo di eguaglianza Aix = bi viene sostituito con la coppia di

vincoli Aix ≥ bi e −Aix ≥ −bi;

- per ogni variabile xj libera, cioe non soggetta al vincolo di non negativita,

si introducono due nuove variabili x+j , x

−j ≥ 0 e si opera la sostituzione

xj = x+j − x−j .

E facile riconoscere che al variare di x+j , x

−j in IR+, xj puo assumere qualsiasi

valore reale.

Per esprimere un problema di programmazione lineare P in forma standard

e necessario riformulare eventuali vincoli di diseguaglianza come vincoli di

eguaglianza. A tale scopo, per ogni vincolo di diseguaglianza Aix ≤ bi (Aix ≥bi) viene introdotta una nuova variabile si ≥ 0 di costo nullo, detta variabile

di slack, ed il vincolo viene sostituito con Aix + si = bi (Aix − si = bi).

La variabile di slack si “misura” lo scostamento della soluzione x dal vincolo

corrispondente e la condizione di non negativita su si assicura l’ammissibilita

di x rispetto al vincolo originale. La variabile di slack si annulla se e solo se

tale vincolo e soddisfatto da x come eguaglianza.

Si noti che, sebbene le precedenti operazioni possano modificare il numero

di variabili e/o di vincoli del problema P , il problema P ′ che ne deriva risulta

equivalente a quello iniziale, nel senso che ogni soluzione ammissibile x di Pcorrisponde ad almeno una soluzione x′ di P ′ dello stesso costo e viceversa.

Quindi la soluzione x e ottima per P se e solo se x′ e ottima per P ′ ed i valori

ottimi dei due problemi sono uguali.

Infine, si noti che ogni problema di massimizzazione max{cx : x ∈ X} e

equivalente al problema di minimizzazione −min{−cx : x ∈ X}.

3 Geometria della PL

Ogni vincolo lineare Aix ≥ bi (Aix ≤ bi) definisce un semispazio chiuso di

IRn la cui frontiera e costituita dall’iperpiano Aix = bi. Tale iperpiano e

normale al vettore Ai ed Ai e diretto all’interno (all’esterno) del semispazio.

L’insieme di ammissibilita di un problema di PL, essendo intersezione di un

numero finito di semispazi e, per definizione, un poliedro. Si ricorda che un

punto di un poliedro P si dice un vertice se non puo essere espresso come

combinazione convessa propria di altri punti di P o, equivalentemente, se e

una faccia di dimensione 0 di P . Ancora, d ∈ Rn si dice una direzione di P

se x + αd ∈ P per ogni x ∈ P e α ≥ 0. Una direzione di P e una direzione

2

estrema di P se non puo essere espressa come combinazione conica propria

di altre direzioni di P o, equivalentemente, se esiste uno spigolo S di P tale

che S = {x : x = x+ αd, α ≥ 0} per un opportuno x ∈ P .

Il teorema che segue fornisce una caratterizzazione dei vertici e delle dire-

zioni estreme di un poliedro.

Teorema 1 Sia P = {x ∈ IRn : Ax ≤ b}.i) Un punto x ∈ P e un vertice di P se e solo se la sottomatrice A0 formata

dalle righe Ai di A tali che Aix = bi ha rango n;

ii) d ∈ IRn e una direzione estrema di P se e solo se Ad ≤ 0 e la sottomatrice

formata dalle righe Ai di A tali che Aix = 0 ha rango n− 1.

E’ facile dimostrare che, nel caso piu generale di un poliedro della forma

P ′ = {x : A1x ≤ b1, A2x ≥ b2, A3x = b3}, la parte i) del precedente

teorema rimane invariata, mentre nella parte ii) la condizione Ad ≤ 0 deve

essere sostituita con le condizioni A1d ≤ 0, A2d ≥ 0 e A3d = 0.

Dal Teorema 1 segue che ogni vertice di P giace su almeno n degli iperpiani

che definiscono la frontiera di P . Inoltre, ogni direzione estrema di P e una

direzione di almeno n− 1 delle degli iperpiani che definiscono la frontiera di

P .

Nel caso di un problema scritto in forma standard, il Teorema 1 puo essere

riformulato come segue.

Teorema 2 Sia P = {x : Ax = b, x ≥ 0}. Un punto x di P e un vertice se

e solo se le colonne di A che corrispondono a componenti di x strettamente

maggiori di 0 sono linearmente indipendenti.

Dimostrazione La matrice dei vincoli che definiscono P e A′ =

A

I

,dove I e la matrice identica n×n. Sia J = {j : xj = 0} ed A0 la sottomatrice

formata dalle righe di A e dalle righe Ij, j ∈ J . Per il Teorema 1, x e un

vertice di P se e solo se A0 ha rango n e quindi, contenendo A0 n colonne, se

e solo se le colonne di A0 sono linearmente indipendenti. Sia∑nj=1 αjA

j0 = 0.

Poiche Aj0, j ∈ J , e l’unica colonna di A0 con componente (m + j)–esima

diversa da 0, deve essere αj = 0 per ogni j ∈ J . Quindi le colonne di A0 sono

linearmente indipendenti se e solo se lo sono le colonne Aj0, j /∈ J . Poiche le

componenti di indice maggiore di m di queste colonne sono nulle, esse sono

linearmente indipendenti se e solo se lo sono le corrispondenti colonne di A.

In particolare, per il terorema precedente, se A ha m righe, ci possono

essere al piu m colonne di A linearmente indipendenti. Quindi ogni vertice

3

di P = {x : Ax = b, x ≥ 0} ha al piu m componenti strettamente maggiori

di 0.

Il seguente Teorema enuncia una proprieta fondamentale dei problemi di

PL.

Teorema 3 Teorema fondamentale della PL. Dato un problema di PL de-

finito in forma canonica o in forma standard, si verifica una delle seguenti

condizioni:

1. il problema e inammissibile;

2. il problema e illimitato;

3. esiste almeno un vertice di P ottimo.

Dimostrazione Sia P non vuoto. Poiche P e contenuto nell’ortante positi-

vo, P non contiene rette. In tal caso P = conv(vertex(P )) + cone(dext(P ))

e quindi ogni x in P risulta somma di una combinazione convessa di vertici

di P e di una direzione di P , cioe

x =∑i∈I

αivi + d

dove vi ∈ vertex(P ), αi ≥ 0 per ogni i ∈ I,∑i∈I αi = 1 e d e una direzione di

P . Se esiste una direzione d di P tale che cd < 0 il problema e illimitato. Sia

infatti x ∈ P . Allora x+αd ∈ P per ogni α ≥ 0 e risulta c(x+αd) = cx+αcd.

Per α → +∞ tale valore tende a −∞. In caso contrario cd ≥ 0 per ogni

direzione d di P e quindi cx ≤ c(x + d) per ogni x ∈ P e d direzione di P .

Dunque la ricerca di una soluzione ottima puo essere limitata al sottoinsieme

V = conv(vertex(P )). Poiche V e un insieme chiuso e limitato e la funzione

cx e continua, per il Teorema di Weierstrass il problema ammette ottimo su

V . Sia x =∑i∈I αivi una soluzione ottima. Da

cx =∑i∈I

αicvi ≥∑i∈I

αi mini∈I

cvi = mini∈I

cvi

segue che almeno un vertice vi, i ∈ I, e ottimo.

Per il teorema precedente un problema di PL, pur essendo un problema

continuo, puo essere risolto limitando la ricerca delle soluzioni ottime ad un

numero finito di punti, i vertici del suo insieme di ammissibilita. Ancora,

e necessario individuare eventuali direzioni di P lungo le quali la funzione

obiettivo tende a −∞. E facile riconoscere che una tale direzione esiste

se e solo se esiste una direzione estrema con la stessa proprieta, e quindi

uno spigolo del poliedro lungo il quale la funzione obiettivo assume valori

arbitrariamente bassi.

4

4 Il metodo del simplesso

Il teorema fondamentale della PL e alla base di un metodo classico per la

risoluzione dei problemi di PL, detto Metodo del simplesso, proposto da Dan-

tzig nei primi anni 50. Benche la complessita dell’algoritmo sia esponenziale,

tale metodo e ancora uno dei metodi piu largamente utilizzati.

L’idea base del metodo del simplesso e la seguente. Un problema di PL viene

dapprima espresso in forma standard, cosicche il suo insieme di ammissibilita

P , se non vuoto, contiene almeno un vertice. In una prima fase, il metodo

determina un vertice di P (o che P e vuoto). Nelle iterazioni successive la

procedura visita vertici di P , lasciando ogni vertice lungo uno spigolo su cui

la funzione decresce strettamente. Se tale spigolo e illimitato il problema e

illimitato, in caso contrario lo spostamento termina in un nuovo vertice di P ,

adiacente a quello precedente e di valore strettamente inferiore. Se il vertice

non soddisfa opportune condizioni di ottimalita, l’iterazione viene ripetuta.

Il metodo termina quando individua o un vertice ottimo o una direzione

estrema di P lungo la quale la funzione obiettivo decresce strettamente.

Per realizzare questa idea generale in un algoritmo, e necessario esplicitare

i seguenti aspetti: caratterizzare i vertici di P algebricamente, individuare

delle condizioni di ottimalita e illimitatezza e definire il passaggio da un

vertice ad uno adiacente. Infine, e necessario determinare un vertice iniziale

o dimostrare che il problema e inammissibile.

Vediamo questi diversi aspetti in dettaglio.

4.1 Vertici e soluzioni di base

Il metodo del simplesso opera su problemi di PL scritti in forma standard

cioe della forma

min cx (7)

Ax = b

x ≥ 0.

dove A e una matrice m × n con m < n. Questa assunzione non e restrit-

tiva dato che, se m ≥ n, o il sistema Ax = b e inammissibile (caso rango

A 6= rango (Ab)) o almeno m− n vincoli risultano combinazione lineare dei

rimanenti e possono essere eliminati ottenendo un sistema con m ≤ n. Se

m = n il sistema ammette una unica soluzione che puo essere calcolata per

via elementare. Nel seguito supporremo A di rango m. Questa condizione

5

puo essere sempre garantita eliminando eventuali vincoli linearmente dipen-

denti dagli altri (operazione che, se necessaria, viene effettuata durante la

prima fase del metodo del simplesso descritta in seguito).

Vediamo innanzitutto come i vertici di P vengano caratterizzati algebrica-

mente tramite il concetto di base e soluzione di base.

Si definisce base ogni sottoinsieme β ⊆ {1, . . . ,m}, |β| = m, tale che la

sottomatrice B formata dalle colonne di A con indice in β, detta matrice

di base, sia non singolare (e quindi invertibile). Data una particolare base

β, la matrice A puo essere partizionata in due sottomatrici B ed N dove

B e formata dalle colonne di A con indice in β, dette colonne in base, ed

N dalle colonne con indice in η = {1, . . . ,m} \ β, dette colonne fuori base.

Analogamente i vettori delle variabili e dei costi possono essere decomposti

in x = (xB, xN) e c = (cB, cN) in modo da evidenziare le componenti in base

e quelle fuori base.

Fissata una base, i vincoli Ax = b possono essere riscritti nella forma

BxB +NxN = b

ed ancora, essendo B invertibile, come

xB = B−1(b−NxN).

Di conseguenza il problema (7) puo essere riscritto come

min cBxB + cNxN (8)

xB = B−1(b−NxN) (9)

xB, xN ≥ 0. (10)

Dalla (9) risulta evidente che le variabili in base risultano univocamente

determinate dalle variabili fuori base. Si consideri la particolare la soluzione,

detta soluzione di base,

xB = B−1b, xN = 0

che si ottiene assegnando valore nullo a tutte le variabili fuori base. Tale

soluzione di base si dice ammissibile se xB ≥ 0. Inoltre si dice degenere se

(xB)i = 0 per qualche i = 1, . . . ,m, non degenere altrimenti.

Si noti che il numero di componenti non nulle di ogni soluzione di base e al

piu m ed e minore di m se e solo se la base e degenere.

Proposizione 1 i) Ogni soluzione di base ammissibile x e un vertice di P .

ii) Ogni vertice di P e soluzione di base per almeno una base.

6

Dimostrazione i) L’affermazione segue dal Teorema 2 dato che le colonne

di A corrispondenti a variabili maggiori di zero di x sono colonne di B e

risultano quindi linearmente indipendenti.

ii) Per il Teorema 2, le colonne di A corrispondenti a componenti non nulle

di un vertice di P sono linearmente indipendenti. Poiche A ha rango m, e

sempre possibile integrare l’insieme di queste colonne con altre colonne di A

in modo da ottenere una base di Rm. Gli indici delle colonne finali formano

evidentemente una base.

Si noti che se un vertice ha esattamente n−m componenti uguali a 0, cioe

giace su esattamente n degli iperpiani che definiscono la frontiera di P (gli

m piani definiti dai vincoli Aix = bi ed altri n − m piani del tipo xj = 0)

allora e soluzione di base per esattamente una base contenente gli indici delle

variabili ¿ 0. Al contrario, vertici di P che giacciono su piu di n piani della

frontiera possono essere soluzioni di base (degeneri) per basi diverse. Questo

avviene perche al passo ii) della dimostrazione precedente le colonne iniziali

possono essere integrate ad una base di IRm in modi diversi.

4.2 Condizioni di ottimalita

Sia B una matrice di base ammissibile e x = (B−1b,0) la corrispondente

soluzione di base. Il costo di x e pari a cBB−1b + cN0 = cBB

−1b. Dalla (9)

segue che il costo di una qualsiasi soluzione ammissibile puo essere espresso

come

cBxB +cNxN = cBB−1b+(cN−cBB−1N)xN = cx+(cN−cBB−1N)xN (11)

e risulta quindi somma del costo della soluzione di base corrente e del termine

(cN − cBB−1N)xN .

Le componenti

cj = cj − cBB−1Aj

del vettore cN = cN − cBB−1N vengono detti costi ridotti.

Dal fatto che xN ≥ 0 per ogni soluzione ammissibile, si ottiene imme-

diatamente la seguente condizione di ottimalita per la soluzione di base

corrente.

Teorema 4 Se cj ≥ 0 per ogni j ∈ η, la soluzione di base corrente e ottima.

La condizione di non negativita dei costi ridotti e in generale una condizione

sufficiente ma non necessaria per l’ottimalita della soluzione di base. Come

7

verra dimostrato nel paragrafo successivo, e anche necessaria se la soluzione

di base e non degenere.

Per capire il significato del costo ridotto di una variabile fuori base, si

immagini di poter aumentare una sola delle variabili fuori base, diciamo

xp, mantenendo tutte le altre a 0 e rimanendo in ammissibilita. Ponendo

xN = (0, . . . , xp, . . . , 0) nella espressione (9) si ottiene che, al crescere di xp,

la variazione nel valore della funzione obiettivo risulta pari a cpxp. Quin-

di il costo ridotto di una variabile rappresenta la variazione nel valore della

funzione obiettivo che si ottiene aumentando la relativa variabile fuori base

di una unita, mantenendo nulle tutte le altre variabili fuori base e facendo

variare le variabili in base in modo che il sistema Ax = b continui ad essere

soddisfatto.

Se tutti i costi ridotti delle variabili fuori base risultano non negativi, il

metodo termina fornendo in output la soluzione di base corrente che e ottima.

Osservazione Si noti che i costi ridotti possono essere definiti anche per le

variabili xj, j ∈ β. In questo caso si ottiene cB = cB − cBB−1B = 0. Quindi

i costi ridotti delle variabili in base sono sempre nulli.

4.3 Cambiamento di base

Si supponga che la condizione di ottimalita non sia soddisfatta e sia p ∈ ηun indice tale che cp < 0. Si consideri il problema di determinare il massimo

incremento della variabile xp che puo essere ottenuto mantenendo a zero le

altre variabili fuori base e l’ammissibilita della soluzione. Come visto nel

paragrafo precedente, un tale aumento comporta una variazione dei valori

delle variabili in base dato dalla

xB = B−1b−B−1Apxp (12)

ottenuta dalla (9) ponendo xj = 0 per ogni j ∈ η \ {p}. Si noti che una tale

variazione corrisponde ad un movimento lungo l’intersezione di n − 1 piani

della frontiera (i piani Ax = b ed i piani xj = 0, j ∈ η \ {p}), e quindi lungo

uno spigolo del poliedro uscente dalla soluzione di base corrente. Tale spigolo

ha direzione d = (−B−1Ap, 0, . . . , 1, . . .) dove la componente 1 compare in

corrispondenza alla variabile xp. In accordo con la (11), il costo del generico

punto y dello spigolo e dato da

cy = cx+ cpxp (13)

e, poiche cp < 0, il valore cx decresce strettamente lungo lo spigolo. Il punto

y e un punto ammissibile fin tanto che le variabili in base (12) rimangono

8

non negative. Si possono verificare due situazioni: o lo spigolo e illimitato

oppure lo spostamento lungo lo spigolo viene bloccato dal fatto che qualche

variabile in base raggiunge il valore 0 e quindi viene raggiunto un nuovo

vertice di P . Dal punto di vista algebrico, per stabilire qual e il massimo

incremento di xp compatibile con l’ammissibilita della soluzione, e sufficiente

determinare il massimo incremento di xp che mantiene tutte le variabili in

base non negative. Questo e dato dal massimo valore di xp ≥ 0 tale che

risulti xB − B−1Apxp ≥ 0 o, equivalentemente, B−1Apxp ≤ xB o ancora,

posto a = B−1Ap,

aixp ≤ (B−1b)i = (xB)i i = 1, . . .m. (14)

Il problema puo essere risolto in modo elementare. Essendo (xB)i ≥ 0, se

ai ≤ 0 la condizione (14) e soddisfatta da ogni xp ≥ 0. Di conseguenza,

se a ≤ 0, la variabile xp puo crescere indefinitamente. In questo caso in

base alla (13) il problema di PL e illimitato. In caso contrario, il massimo

incremento di xp e dato da

xp = mini:ai>0

{(xB)iai

}=

(xB)qaq

.

Si noti in particolare che risulta xp > 0 se la soluzione di base x e non

degenere. In caso di degenerazione puo anche essere xp = 0.

Sia q un indice tale che risulti xp = (xB)q

aqe si consideri la soluzione x′

ottenuta dalla soluzione di base corrente aumentando xp del valore xp. Le

componenti di x′ sono

x′B = xB − xpa, x′p = xp, x′j = 0 se j ∈ η \ {p}.

Poiche (x′B)q = 0, la soluzione x′ ha almeno n−m componenti nulle. E facile

riconoscere che x′ e la soluzione di base corrispondente alla base β′ che si

ottiene da β eliminando l’indice β(q) e introducendo l’indice p. Per dimo-

strare che la corrispondente matrice di base B′, ottenuta da B sostituendo la

q-esima colonna con Ap, e non singolare e sufficiente dimostrare che B−1B′ e

non singolare. Ora B−1Bi = I i per ogni i 6= q, mentre B−1(Ap) = a. Poiche

aq 6= 0 la matrice B−1B′ e non singolare.

Per poter eseguire una nuova iterazione a partire dalla nuova soluzione di

base e necessario aggiornare l’inversa della matrice di base. Cio puo essere

fatto senza ricalcolare direttamente l’inversa di B′ (calcolo di costo O(m3))

tenendo conto del fatto che B′ differisce da B solo per una colonna. Deno-

tando con W = B−1 e W ′ = B′−1, W ′ puo essere calcolata in O(m2) in base

alla seguente formula di aggiornamento delle righe di W

W ′i =

Wi − ai

aqWq if i 6= q

1aqWq if i = q.

(15)

9

4.4 Criteri per la scelta della variabile che entra in base

Per terminare la descrizione della generica iterazione del simplesso, vengono

elencati alcuni criteri utilizzabili nella scelta della variabile che entra in base

tra quelle che hanno costo ridotto negativo.

1. Si sceglie una variabile fuori base di costo ridotto minimo. Questo crite-

rio richiede di calcolare tutti i costi ridotti ed ha un costo computazio-

nale limitato. Si noti che tale criterio non comporta necessariamente il

decremento maggiore nel valore della funzione obiettivo. Infatti questo

e dato da cpxp e quindi dipende non solo dal valore del costo ridotto

ma anche dal massimo incremento possibile di xp.

2. Si sceglie la variabile che produce il piu alto decremento cpxp nella

funzione obiettivo. Questo criterio che sembra teoricamente attraente

e di fatto troppo oneroso dal punto di vista computazionale.

3. si sceglie la prima variabile fuori base il cui costo ridotto e negativo.

4.5 Prima fase del metodo del simplesso

Nei paragrafi precedenti e stata descritta la generica iterazione del metodo

del simplesso, basata sulla conoscenza di una particolare soluzione di base

ammissibile. Per completare la descrizione del metodo e ora necessario defi-

nire come determinare una soluzione di base ammissibile iniziale o stabilire

che il poliedro di ammissibilita e vuoto.

In alcuni casi particolari, una base ammissibile e immediatamente dispo-

nibile. Questo avviene, per esempio, quando si vuole risolvere un problema

P della forma {min cx : Ax ≤ b} con b ≥ 0. In questo caso la base che

contiene gli indici delle variabili di slack della forma standard di P e una

base ammissibile dato che risulta B = I = B−1 e quindi xB = Ib = b ≥ 0.

Quindi il problema artificiale e sempre ammissibile. Quando l’individuazione

di una base ammissibile non sia immediata e necessario eseguire una fase di

inizializzazione del metodo detta Prima fase del simplesso.

La prima fase del simplesso consiste nel risolvere un nuovo problema di

PL. Si riscriva il sistema Ax = b in modo che risulti b ≥ 0 e si consideri il

problema, detto problema artificiale,

PA : minm∑i=1

zi (16)

Ax+ Iz = b (17)

x, z ≥ 0 (18)

10

definito nelle variabili originali x ed in m nuove variabili zi, i = 1, . . . ,m,

associate ai vincoli e dette variabili artificiali. Si noti che, essendo b ≥ 0, la

base che contiene gli indici delle variabili artificiali e una base ammissibile

per il problema artificiale. Inoltre, per i vincoli z ≥ 0, il valore ottimo del

problema artificiale e non negativo.

Proposizione 2 Il problema artificiale ha valore ottimo nullo se e solo se il

problema originale e ammissibile.

Dimostrazione Se x ∈ P , (x,0) e una soluzione ammissibile di PA di valore

0 e quindi ottima. Viceversa, se (x, z) e una soluzione (ammissibile) ottima

di valore 0, allora deve necessariamente essere z = 0. Cio implica Ax = b,

x ≥ 0 e quindi x ∈ P .

Rimane da stabilire come ottenere una base ammissibile del problema ori-

ginale dalla base ottima del problema artificiale. Se la base ottima di PA

non contiene indici di variabili artificiali, allora e una base ammissibile per il

problema originale. In caso di degenerazione, puo pero accadere che qualche

variabile artificiale sia in base (con valore nullo). In questo caso e necessario

sostituirla con una variabile originale fuori base da scegliersi in modo che

la corrispondente matrice di base risulti non singolare. Piu precisamente,

supponiamo che la q–esima colonna della matrice di base BA ottima per il

problema artificiale corrisponda ad una variable artificiale e siano B ed N

le sottomatrici formate dalle colonne di A che sono attualmente in base e

fuori base nella base ottima del problema artificiale. Si vuole sostituire BqA

con una colonna Aj di N sotto la condizione che la matrice risultante B′

sia non singolare. Questa circostanza si verifica se e solo se B−1A B′ e non

singolare. Quest’ultima matrice coincide con la matrice identica su tutte le

colonne tranne la q–esima, data da B−1A Aj, e risulta quindi non singolare se e

solo se (B−1A Aj)q 6= 0. La ricerca della colonna Aj puo quindi essere operata

calcolando il vettore

f = eqB−1A N

Se fj 6= 0 per qualche indice j, l’indice j puo essere sostituito al q-esimo

elemento della base corrente. In caso contrario, poiche B non contiene la

q-esima colonna di BA, valgono le condizioni

eqB−1A B = 0 eqB

−1A N = 0

cioe eqB−1A A = 0 e le righe di A risultano linearmente dipendenti dato che la

loro combinazione lineare con vettore dei coefficienti eqB−1A e il vettore nullo.

Una riga Ai tale che (eqB−1A )i 6= 0, risultando linearmente dipendente dalle

altre, puo allora essere eliminata.

11

4.6 Complessita del metodo del simplesso

La complessita di ogni iterazione del metodo del simplesso e polinomiale ed e

dovuta al calcolo di u = cBB−1 (O(m2)), dei costi ridotti (O(m(n−m)), del-

l’incremento della variabile che entra in base (O(m2)) ed agli aggiornamenti

(O(m2)). Quindi il costo computazionale di queste operazioni e dominato

dal calcolo dei costi ridotti che richiede, nel caso peggiore, O(nm) operazioni

elementari.

La complessita finale dipende dal numero di passi richiesti per raggiungere

una condizione di terminazione. Come primo aspetto, consideriamo il pro-

blema della finitezza del metodo, cioe se sia vero che il metodo termina in

un numero finito di passi per qualsiasi istanza. La risposta e affermativa nel

caso di non degenerazione. Infatti, in questa ipotesi, iterazioni successive

corrispondono a soluzioni di base di costo strettamente decrescente e quindi

il metodo visita al piu una volta ogni soluzione di base. Poiche queste sono

in numero finito, il metodo termina in un numero finito di passi.

In caso di degenerazione, un vertice puo essere soluzione di base per basi

diverse e puo accadere che queste vengano visitate in iterazioni successive e

che il metodo torni su una base gia visitata. Questa circostanza viene detta

ciclaggio del metodo.

Per evitarla e necessario adottare delle opportune regole anticiclaggio. La

piu semplice e nota e la seguente regola di Bland che stabilisce un criterio

particolare per la scelta della variabile che entra in base e per quella della

variabile che esce dalla base.

Teorema 5 Si scelga l’indice p che entra in base con il criterio

p = min{j : cj < 0}

e l’indice β(q) che esce dalla base con il criterio

β(q) = min{β(i) :(xB)iai≤ (xB)k

akper ogni ak > 0}.

Allora il metodo del simplesso termina in un numero finito di passi.

Se vengono adottate regole anticiclaggio, il metodo del simplesso converge

in un numero finito di passi. In generale questo numero non e polinomiale.

Infatti sono state individuate istanze che vengono risolte dal simplesso in un

numero esponenziale di iterazioni.

12

Esempio (Klee and Minty 1972) Si considerino le istanze di PL definite da

min −xkεxj−1 ≤ xj ≤ 1− εxj−1 ∀j = 2, . . . , k

Se ε > 0 l’insieme di ammissibilita e un cubo leggermente deformato (si dise-

gni nel caso m = 2). Si puo dimostrare che le basi della forma standard del

problema sono tutte non degeneri e che esiste una sequenza di base adiacenti

con costo strettamente decrescente che corrisponde ad una sequenza di tutti

i 2m vertici del cubo (che sono esponenenziali rispetto al numero di variabili

n = k e di vincoli m = 2k della forma standard).

A discapito di questo risultato teorico negativo, il metodo e tuttora uno dei

piu frequentemente utilizzati nelle applicazioni. Studi sperimentali hanno

evidenziato che, mediamente, il numero di passi e lineare nel numero m dei

vincoli e sublineare nel numero n delle variabili.

5 Complessita della programmazione lineare

Il problema della polinomialita (o meno) della programmazione lineare e ri-

masto aperto per diversi anni ed ha avuto una risposta definitiva nel 1979

ad opera del matematico russo Leonard Khachiyan. Il metodo proposto da

Khachiyan, detto metodo dell’elissoide, consente di risolvere una istanza di

PL in tempo polinomiale rispetto alla lunghezza della sua codifica. Tale al-

goritmo, benche di fondamentale importanza dal punto di vista teorico, non

risulta pero adottabile nella pratica per l’alto grado del polinomio che defi-

nisce la complessita del metodo. Comunque tale procedura ha avuto anche

un ruolo importante nella definizione di algoritmi approssimati randomizza-

ti basati sulla programmazione semidefinita per problemi di ottimizzazione

combinatorica NP-hard. Il primo algoritmo polinomiale competitivo con il

metodo del simplesso segue un approccio completamente diverso da esso ed e

stato proposto dal matematico indiano Narendra Karmarkar nel 1984. Tale

metodo e le sue varianti sviluppate in seguito vengono dette metodi a pun-

ti interni proprio perche convergono verso un vertice ottimo visitando una

sequenza di soluzioni interne al poliedro.

13

6 Programmazione Lineare e Dualita

La teoria della dualita studia le importanti relazioni esistenti tra un problema

di ottimizzazione, detto problema primale, ed un problema ad esso correlato,

detto problema duale. Le variabili del problema duale hanno una interessante

interpretazione geometrica ed economica. In questo capitolo vengono presen-

tati i risultati di dualita nel caso in cui il problema primale sia un problema

di PL.

Si consideri un problema di PL della forma

P : v = min c1x1 + c2x2 (19)

A11x1 + A12x2 ≥ b1 (20)

A21x1 + A22x2 = b2 (21)

x1 ≥ 0 (22)

dove e stata evidenzata la decomposizione dei vincoli in vincoli di eguaglianza

e di diseguaglianza e delle variabili in variabili libere e non.

Il problema duale di P e il problema

D : d = max u1b1 + u2b2 (23)

u1A11 + u2A21 ≤ c1 (24)

u1A12 + u2A22 = c2 (25)

u1 ≥ 0. (26)

Il problema D e ancora un problema di PL ed ha una variabile per ogni

vincolo del primale ed un vincolo per ogni variabile del primale. Inoltre:

• il vettore dei costi del duale e il vettore dei termini noti del primale;

• il vettore dei termini noti del duale e il vettore dei costi del primale;

• la matrice dei vincoli del duale e la trasposta della matrice dei vincoli

del primale;

• una variabile duale e soggetta al vincolo di non negativita se e solo se

il corrispondente vincolo primale e di diseguaglianza;

• un vincolo duale e di diseguaglianza se e solo se la corrispondente

variabile primale e soggetta al vincolo di non negativita.

E facile verificare che il problema duale di D coincide con P .

14

Nel seguito indicheremo con Ai, i = 1, 2, la sottomatrice (Ai1Ai2) e con Ai,

i = 1, 2, la sottomatrice

A1i

A2i

.Un primo risultato di dualita, noto come dualita debole, stabilisce che il

valore ottimo del problema duale e sempre una limitazione inferiore del valore

ottimo primale.

Teorema 6 Risulta d ≤ v. In particolare, se uno dei due problemi e illimi-

tato, l’altro e inammissibile.

Dimostrazione Dimostrariamo innanzitutto che se x = (x1, x2) e u =

(u1, u2) sono due soluzioni ammissibili per P e D, allora ub ≤ cx. L’ammissi-

bilita di x ed u garantisce le seguenti relazioni: b1 ≤ A1x, u1 ≥ 0, b2 = A2x,

x1 ≥ 0, c1 ≥ uA1 e c2 = uA2. Di conseguenza

ub = u1b1 + u2b2 ≤ u1A1x+ u2A2x = uAx

e

cx = c1x1 + c2x2 ≥ uA1x1 + uA2x2 = uAx

da cui si ottiene

ub ≤ uAx ≤ cx. (27)

Poiche la (27) vale per due generiche soluzioni primale e duale, risulta d ≤ v.

In particolare, se il problema P (il problema D) ammette una soluzione x

(u), il valore cx (ub) rappresenta una limitazione superiore (inferiore) per d

(v) e quindi D (P) non puo essere illimitato.

La differenza v − d viene detta scarto di dualita.

Corollario 7 Siano x e u soluzioni ammissibili, rispettivamente, per P e D.

Se cx = ub, allora x e u sono ottimi.

La dualita debole e una proprieta verificata da ogni coppia primale duale

di problemi di ottimizzazione. Nel caso della PL tale condizione puo essere

rafforzata per il seguente fondamentale risultato che inverte la condizione

espressa nel Corollario 7.

Teorema 8 Il problema P ammette ottimo se e solo se il problema D am-

mette ottimo. In questo caso risulta d = v.

15

Dimostrazione Si consideri la forma standard P ′ del problema P . Il

problema P ammette ottimo se e solo P ′ ammette ottimo e questo avviene se e

solo se esiste una soluzione di base x = (B−1b,0) che soddisfa le condizioni di

ottimalita cN = cN−cBB−1N ≥ 0. Si consideri la soluzione duale u = cBB−1.

Essa e ammissibile per il problema duale D′ di P ′ se e solo se uA ≤ c. Poiche

risulta uB = cBB−1B = cB e uN = cBB

−1N ≤ cN per le condizioni di

ottimalita, u e ammissibile duale. Inoltre ub = cBB−1b = cBxB = cx. E ora

facile verificare che la soluzione u risulta ammissibile e quindi ottima anche

per D.

La non ammissibilita di uno dei due problemi non implica la illimitatezza

dell’altro. Infatti esistono istanze per cui sia il problema primale che il duale

sono non ammissibili e quindi lo scarto di dualita e infinito (si prenda ad

esempio A matrice nulla, b = 1 e c = −1).

Il Lemma di Farkas e la dualita forte

In questo paragrafo si considerano due problemi primale e duale scritti in

forma canonica

min cx (28)

Ax ≥ b (29)

x ≥ 0 (30)

ed il problema duale sia quindi

min ub (31)

uA ≤ c (32)

u ≥ 0. (33)

La dualita forte della PL puo essere dimostrata come conseguenza di un

importante risultato della teoria dei sistemi lineari noto come Lemma di

Farkas. Esistono diverse varianti di questo risultato, noti anche come Teoremi

dell’alternativa.

Teorema 9 Lemma di Farkas Data una matrice A ed un vettore b, esatta-

mente uno degli insiemi

- P = {x : Ax ≥ 0, cx < 0}- Q = {u : uA = c, u ≥ 0}e non vuoto.

16

Dimostrazione Sia Q 6= ∅ e u ≥ 0 tale che uA = c. Allora cx = uAx

per ogni x e quindi, se Ax ≥ 0 risulta necessariamente cx ≥ 0 cioe P = ∅.Viceversa supponiamo Q = ∅ e consideriamo l’insieme Z = {z : z = uA, u ≥0} cioe l’insieme delle combinazioni coniche delle righe di A. Poiche per

ipotesi c /∈ Z e Z e un insieme chiuso e convesso esiste un iperpiano xx = α,

x ∈ Rn e α ∈ R, che separa strettamente Z da c cioe tale che xc < α e

xz ≥ α per ogni z ∈ Z per un opportuno vettore . Poiche lo 0 appartiene

a Z risulta α ≤ 0. Quindi cx < 0. D’altra parte uAx ≥ 0 per ogni u ≥ 0

e questo implica Ax ≥ 0. Infatti, se fosse Aix < 0 per qualche i, ponendo

ui = 1 e uj = 0 se j 6= i si otterrebbe uAx = uiAix < 0. Da questo segue

che x ∈ P .

Il Lemma di Farkas ha la seguente interpretazione geometrica. Il poliedro

definito dai vincoli Ax ≥ 0 e un cono convesso ed ogni sup elemento di-

verso dal vettore nullo e una direzione del cono. La funzione cx e limitata

inferiormente sul cono se e solo se P e vuoto e quindi se e solo se c e una

combinazione conica combinazione conica delle righe di A.

Dimostrazione del Teorema 8. Supponiamo che il problema primale

ammetta soluzione ottima x∗ di valore v∗ (il caso simmetrico puo essere

trattato in modo analogo). Dimostreremo che allora esiste u∗ ammissibile

per il problema duale e tale che u∗b ≥ cx∗ da cui, per la dualita debole,

u∗b = cx∗. Per l’ottimalita di x∗ risulta non ammissibile il sistema

Ax ≥ b (34)

x ≥ 0 (35)

cx < v∗ (36)

Come primo passo dimostriamo che questo sistema e non compatibile se e

solo se e non compatibile il sistema omogeneo

Ax− λb ≥ 0 (37)

cx− λv∗ < 0 (38)

x ≥ 0, λ ≥ 0 (39)

Infatti, se esiste una soluzione x del primo sistema allora (x, 1) e una soluzione

del secondo sistema. Viceversa sia (x, λ) una soluzione del secondo sistema.

Se λ > 0, allora xλ

e una soluzione del primo. Se λ = 0 si ha Ax ≥ 0,

cx < 0 ed e allora facile verificare che la soluzione x = x+x∗ e una soluzione

ammissibile del primo sistema.

Quindi possiamo assumere che il sistema (37) sia non ammissibile. Esso puo

17

essere scritto nella formaA −bIn 0

0 1

x

λ

≥

0m

0n

0

(40)

(cT −v∗

) x

λ

< 0 (41)

Per il Lemma di Farkas esiste quindi un vettore (u, y, w) ≥ 0 tale che

(u, y, w)

A −bIn 0

0 1

=

cT

−v∗

.Questi vincoli possono essere riscritti nella forma

uA+ Iny = cT (42)

−ub+ w = −v∗ (43)

u, y, w ≥ 0 (44)

da cui risulta che u e una soluzione ammissibile duale (uA ≤ cT , u ≥ 0), tale

che ub ≥ v∗. Per la dualita debole deve allora essere ub = v∗.

6.1 Condizioni di complementarita

La dualita forte stabilisce una relazione tra i valori ottimi di P e D. Consi-

deriamo ora un insieme di condizioni, dette condizioni di complementarita,

che stabiliscono delle relazioni tra le soluzioni ottime dei due problemi.

Teorema 10 Due soluzioni x e u ammissibili rispettivamente per i problemi

P e D sono ottime se e solo se soddisfano le condizioni

u(Ax− b) = 0 (45)

(uA− c)x = 0. (46)

Dimostrazione Necessita Per quanto provato nella dimostrazione del Teo-

rema 6 risulta ub ≤ uAx ≤ cx. Dalla dualita forte cx = ub si ottiene

allora

ub = uAx = cx, (47)

18

da cui seguono le (45) e (46).

Sufficienza Le condizioni di complementarieta implicano la (47) e quindi le

due soluzioni sono ottime per il Corollario 7.

In ammissibilita, le condizioni di complementarita esprimono condizioni piu

forti rispetto alla semplice condizione di ortogonalita tra le coppie di vettori

u, Ax− b e uA− c, x. Si noti infatti che, per l’ammissibilita delle soluzioni x

e u, ogni termine della sommatoria u(Ax− b) =∑mi=1 ui(Aix− bi) risulta non

negativo. Infatti (Aix− bi) ≥ 0 e, se la diseguaglianza vale in senso stretto,

deve essere ui ≥ 0 per il vincolo di nonnegativita sulla variabile ui. Quindi

u(Ax − b), essendo una somma di termini non negativi, e nullo se e solo se

tutti i suoi termini sono nulli cioe se e solo se

ui(Aix− bi) = 0 ∀ i = 1, . . . ,m.

Analogamente si puo dimostrare che, in ammissibilita, la condizione (uA −c)x = 0 e equivalente alle n condizioni

(uAj − cj)xj = 0 ∀ j = 1, . . . , n.

In particolare, per il Teorema 10, in ottimalita valgono le seguenti implica-

zioni

Aix− bi > 0 → ui = 0 (48)

xj > 0 → uAj − cj = 0 (49)

uAj − cj < 0 → xj = 0 (50)

ui > 0 → Aix− bi = 0. (51)

Interpretazione geometrica delle variabili duali ottime

Quanto affermato ci consente di interpretare geometricamente le variabili

duali ottime. Si consideri un problema primale nella forma {max cx : Ax ≤ b}(in cui la matrice A comprende tutti i vincoli e i vettori Ai puntano all’e-

sterno del poliedro primale, vedi Fig. 1), il cui problema duale e {maxub :

uA = c, u ≥ 0}. E facile riconoscere che le soluzioni ammissibili duali sono

tutti e soli i vettori dei coefficienti di combinazioni coniche delle righe di A

che danno il vettore c. Sia u una soluzione ottima duale. Per le condizioni

di complementarieta (48) possono essere diverse da zero solo le componenti

ui corrispondenti a vincoli primali soddisfatti come uguaglianza in ogni solu-

zione ottima primale. Quindi x e una soluzione ottima primale se e solo se c

e una combinazione conica delle righe di A che corrispondono a vincoli attivi

in x. Le variabili ottime duali sono proprio i coefficienti di tale combinazione

conica. Inoltre, essendo ub = cx per la dualita forte, l’iperpiano di equazione

cx = cx risulta una combinazione conica dei vincoli attivi in x.

19

A1

A2

A1

A2

cx*

A2

A2

A2

Figura 1: Cono dei vettori c per cui x∗ e soluzione ottima

6.2 Interpretazione economica delle variabili duali

Le variabili duali ottime di un problema di PL hanno anche una interessante

interpretazione economica.

Si consideri un problema in forma standard e siano β e x = (xB, xN) =

(B−1b,0) una base ottima e la corrispondente soluzione di base. Si supponga

ora di variare il q–esimo termine noto di una quantita ε, cioe si consideri un

nuovo vettore di termini della forma b′ = b+εeq, dove eq rappresenta il q-esimo

elemento della base canonica di Rm. Se la base β e non degenere, per valori

di ε sufficientemente piccoli, β e una base ammissibile anche per il problema

modificato e le variabili in base della corrispondente soluzione di base sono

x′B = B−1(b + εeq) ≥ 0. Poiche i costi ridotti non vengono modificati da

variazioni nel vettore b, β e ancora una base ottima. La variazione nel valore

ottimo dei due problemi e data da

cB(x′B − xB) = εcBB−1eq = εueq = εuq

dove u = cBB−1 e una soluzione duale ottima. Quindi uq rappresenta la va-

riazione nel valore ottimo conseguente ad una variazione unitaria del q-esimo

termino noto. Un valore uq < 0 (uq > 0) indica il decremento (aumento) nel

valore ottimo del problema corrispondente ad un incremento unitario del q–

esimo termine noto. Per tale motivo le variabili duali ottime possono essere

interpretate come prezzi connessi alla presenza dei vincoli e vengono anche

dette prezzi ombra.

Esempio Si consideri un problema di pianificazione della produzione. Una

azienda puo produrre n diversi prodotti utilizzando m risorse (materie prime,

ore lavoro ecc). Sia cj il profitto ottenibile da una unita del prodotto j, bi

la quantita di risorsa i e aij la quantita di risorsa i necessaria per produrre

una unita del prodotto j. Allora il problema di massimizzazione del profitto

totale puo essere espresso come

20

max cx (52)

Ax ≤ b (53)

x ≥ 0. (54)

Immaginiamo ora che l’azienda possa investire nell’acquisto di nuove risorse,

e sia ri il costo unitario della risorsa i-esima. Quali sono le risorse che e

conveniente acquistare e in quali quantita?

Se u∗ e la soluzione ottima duale, la generica componente u∗i indica l’aumen-

to nel valore della funzione ottenibile per un incremento unitario del termine

noto bi. Quindi il guadagno netto per aumento unitario della risorsa i e dato

da gi = u∗i − ri. Evidentemente conviene investire in una o piu risorse q

con valore gq massimo. Il ragionamento puo essere applicato purche la base

continui a rimanere ottima. Poiche una variazione dei termini noti non inci-

de sull’ottimalita, e sufficiente che la base continui a rimanere ammissibile e

quindi la quantita ∆bq deve essere tale che

B−1b+B−1∆bqeq ≥ 0,

cioe

∆bqB−1q ≥ −x∗B.

Se B−1q ≥ 0 questo incremento puo essere a priori illimitato e quindi con-

viene investire completamente nella risorsa i, in caso contrario il valore ∆bq

massimo e dato da

mink:B−1

kq<0

−x∗β(k)

B−1kq

.

Ogni altro incremento di bq non porterebbe a nessun vantaggio e conviene

investire su una diversa risorsa.

6.3 Simplesso e dualita

Si consideri un problema di PL espresso in forma standard

min cx (55)

Ax = b (56)

x ≥ 0 (57)

ed il suo problema duale

min ub (58)

uA ≤ c (59)

21

Ad ogni soluzione di base x = (xB,0) e associato il vettore

u = cBB−1

che, avendo dimensione m, puo essere interpretato come un vettore di varia-

bili duali.

Vediamo come si comporta questo particolare vettore u rispetto ai vincoli del

problema duale. Tali vincoli possono essere riscritti come u[BN ] ≤ [cBcN ]T

e quindi scomposti nei due gruppi

uB ≤ cB (60)

uN ≤ cN . (61)

Sostituendo a primo membro il vettore u = cBB−1 otteniamo che il primo

gruppo di vincoli e sempre soddisfatto con l’eguaglianza dato che cBB−1B =

cBI = cB, mentre il seconda gruppo di vincoli e equivalente a

cBB−1N ≤ cN ⇔ cN = cN − cBB−1N ≥ 0.

Quindi u e una soluzione ammissibile duale se e solo se i costi ridotti sono

tutti non negativi, cioe se e solo se e soddisfatta la condizione di ottimalita

richiesta dal simplesso. In generale, una soluzione duale u viene detta una

soluzione di base se risulta u = cBB−1 per una opportuna matrice di base B.

Da quanto detto si puo osservare che il metodo del simplesso lavora consi-

derando ad ogni passo una coppia di soluzioni primale e duale che soddisfano

le condizioni di complementarieta ed hanno lo stesso valore (si verifichi per

esercizio). Mentre la soluzione primale e ammissibile, la soluzione duale in

generale e non ammissibile e diventa ammissibile solo quando la soluzione

primale soddisfa le condizioni di ottimalita ed e quindi ottima.

7 Analisi di sensitivita o di post–ottimalita.

Molto spesso i parametri che intervengono nel modello matematico di un

problema reale contengono un certo grado di approssimazione rispetto ai

valori reali. Ha allora senso chiedersi quanto dell’informazione che si ottiene

risolvendo il modello matematico sia sensibile a possibili inaccuratezze del

modello, o, in altre parole, quanto la soluzione ottenuta sia robusta rispetto

a piccole modifiche dei dati. L’analisi di sensivita e una analisi a posteriori

che cerca di rispondere a queste domande.

I parametri che intervengono in un modello di PL sono: i costi, i termini

noti dei vincoli e gli elementi della matrice dei vincoli.

22

Sia x = (xB, xN) una soluzione di base ottima di un problema in forma

standard.

Consideriamo dapprima una variazione in uno dei termini noti del problema,

assumendo che il vettore b venga modificato in b′ = b+ εeq. Poiche una tale

modifica non altera i costi, la soluzione di base x′ = (x′B = B−1b′, x′N = 0)

soddifa ancora la condizione di ottimalita cN ≥ 0. Quindi, se ammissibile,

essa e anche ottima. Essendo tutte le variabili fuori base nulle, la condizione

di ammissibilita, posto W = B−1, e data da

x′B = Wb′ = W (b+ εeq) = xB + εW q ≥ 0.

L’intervallo di valori di ε per cui tale condizione e soddisfatta e allora

max{−(xB)iWiq

: Wiq > 0} ≤ ε ≤ min{−(xB)iWiq

: Wiq < 0}. (62)

Si noti che, essendo xB ≥ 0, l’intervallo in (62) contiene lo 0, valore corri-

spondente al problema di partenza.

Si consideri ora una variazione nel costo della p-esima variabile, cioe una

variazione nel vettore dei costi del tipo c′ = c + εep. Tale variazione non

modifica l’insieme di ammissibilita del problema e quindi x e una soluzione

di base ammissibile per il problema modificato. Quali sono i valori di ε per

cui verifica ancora le condizioni di ottimalita cN ≥ 0? Si devono distinguere

i due casi p ∈ η e p ∈ β. Nel primo caso una variazione di cp altera il

costo ridotto della sola variabile xp e quindi le condizioni di ottimalita sono

soddisfatte se e solo se

c′p = cp + ε ≥ 0 ⇐⇒ ε ≥ −cp. (63)

Nel secondo caso, sia p = β(q) il q-esimo elemento in base. Le condizioni di

ottimalita richiedono

c′N = cN − (cB + εeq)B−1N = cN − εeqB−1N ≥ 0. (64)

Sia a = eqB−1N. La (64) e equivalente alle condizioni

c′j = cj − εaj ≥ 0 per ogni j ∈ η.

Quindi x soddisfa le condizioni di ottimalita per ogni valore di ε nell’intervallo

max{ cjaj

: j ∈ η, aj < 0} ≤ ε ≤ min{ cjaj

: j ∈ η, aj > 0}. (65)

Si noti che, essendo cN ≥ 0, l’intervallo contiene lo 0.

23

Una analisi analoga puo essere condotta per studiare quali variazioni in un

termine della matrice dei vincoli A sono compatibili con l’ottimalita della

base corrente.

Si noti che modifiche nei termini noti e nei costi compatibili con le condizioni

(62), (63) e (65) , mantengono l’ottimalita della base corrente ma comportano

una variazione dei valori delle variabili ottime (nel primo caso) e del valore

ottimo del problema nel secondo caso. Cio che non varia e la base ottima.

Nel caso di variazioni dei parametri che non soddisfano tali condizioni sara

necessario eseguire una fase di riottimizzazione.

8 Algoritmo del simplesso duale

Si supponga di aver risolto un problema di PL in forma standard

min cx (66)

Ax = b (67)

x ≥ 0 (68)

con il metodo del simplesso determinando una soluzione di base ottima x∗ e

la corrispondente soluzione duale ottima u∗ date da

x∗ = (B−1b,0) u∗ = cBB−1

dove B e la matrice di base ottima.

Si assuma ora di modificare il problema in uno dei seguenti modi

a) variando il vettore dei termini noti b;

b) introducendo un nuovo vincolo;

e che questa variazione renda la soluzione x∗ inammissibile. Per risolvere il

nuovo problema con il metodo del simplesso si dovrebbe a questo punto far

ripartire la prima fase del metodo e quindi si perderebbe tutta l’informazione

precedentemente acquisita. Questo sembra poco sensato dato che una mo-

difica come quelle considerate probabilmente determina un problema la cui

soluzione ottima non e molto “distante” dalla soluzione ottima del problema

originale. Un metodo che consente di risolvere il nuovo problema a partire

dalla base corrente e il metodo del simplesso duale.

Si consideri dapprima una modifica del vettore dei termini noti b che renda

x∗ inammissibile. Tale modifica fa variare l’insieme ammissibile primale e

la funzione obiettivo duale, mentre non varia l’insieme ammissibile duale e

24

la funzione obiettivo primale. In particolare, se anche la soluzione ottima

primale x∗ non e piu ammissibile, la soluzione duale ottima u∗ e ancora

ammissibile. Eventualmente, essendo variata la funzione obiettivo del duale,

u∗ non sara piu ottima.

Nel caso b) in cui venga introdotto un nuovo vincolo primale

gx ≤ h

l’insieme dei vincoli del problema primale diventa

A =

A 0

g 1

≤ b

h

dove l’ultima riga si riferisce al nuovo vincolo ed e stata introdotta una nuova

variabile (di slack) e quindi una colonna della matrice identica. In questo

caso, poiche B e non singolare, anche

B =

B 0

gB 1

e non singolare. Si puo allora considerare la soluzione di base (B−1(b, h)T , 0)

e la corrispondente soluzione duale di base (cB, 0)B−1 = (u∗, 0)T . E facile

verificare che (u∗, 0) risulta ammissibile per il nuovo problema duale.

Vediamo ora come, a partire da una soluzione di base duale ammissibile, sia

possibile risolvere il nuovo problema primale.

L’algoritmo del simplesso duale

Si e gia visto come il metodo del simplesso lavori mantenendo ad ogni passo

una coppia di soluzioni primale-duale x, u con le seguenti proprieta: 1) x e u

soddisfano le condizioni di complementarita, 2) x e ammissibile, 3) uB = cB

e 4) la condizione uN − cN ≤ 0, equivalente alla condizione di ottimalita

cN ≥ 0, risulta soddisfatta solo in ottimalita.

Il metodo del simplesso duale opera in modo simmetrico, cioe ad ogni passo

considera una coppia di soluzioni primale e duale che soddisfano le condizioni

di complementarita e di cui solo la soluzione duale e ammissibile. L’obiettivo

e quello di portare la soluzione primale verso l’ammissibilita dato che questa

condizione implica l’ottimalita per il Teorema 10.

Alla generica iterazione la soluzione di base duale u = cBB−1 e ammissibile

mentre la soluzione di base primale (B−1b,0) e non ammissibile. Poiche

tutte le variabili fuori base sono nulle, questo implica che una variabile in

25

base deve avere un valore strettamente negativo. Sia essa la variabile di

indice β(q), cioe la q-esima variabile in base. Un modo per rendere questa

variabile non negativa e quello di portarla fuori base, sotto la condizione di

mantenere l’ammissibilita duale. Attualmente il vincolo duale corrispondente

alla colonna Bq risulta soddisfatto come uguaglianza. Portare la variabile

fuori base significa consentire che questo vincolo possa essere soddisfatto con

il ≤. L’obiettivo e allora quello di determinare una nuova soluzione duale u′

tale che risulti

u′B = cB − αeq (69)

u′N ≤ cN (70)

per un opportuno α ≥ 0. Inoltre, per ottenenere una nuova base, e necessario

individuare un valore di α per cui almeno uno dei vincoli corrispondenti alle

variabili fuori base risulti soddisfatto con l’eguaglianza. Per determinare un

tale valore si esplicitino le condizioni (70) sostituendo u′ = (cB − αeq)B−1

nel secondo blocco di disequazioni. Si ottiene

(cB − αeq)B−1N = cBB−1N − αeqB−1N ≤ cN .

Posto a = eqB−1N , il valore massimo di α e dato dalle condizioni

−αa ≤ cN − cBB−1N = cN .

Si noti che, essendo u = cBB−1 ammissibile, i costi ridotti cj, j ∈ η, sono

tutti ≥ 0. Ne segue che componenti aj ≥ 0 non pongono alcun impedimento

all’aumento di α. Quindi il valore massimo per α e dato da

α∗ = min{−cjaj

: j ∈ η, aj < 0}.

In particolare, se a ≥ 0, α∗ = +∞, cioe α puo tendere all’infinito mantenendo

la soluzione duale ammissibile. Il costo della nuova soluzione duale u′ e dato

da

u′b = cBB−1b− αeqB−1b = cBB

−1b− α∗xβq . (71)

Poiche xβq < 0, se α∗ = +∞ il valore della soluzione duale tende ad infinito

ed il problema duale e illimitato. Per il Teorema 6 si puo concludere che il

primale e inammissibile. In caso contrario, sia p una variabile fuori base per

cui risulta

α∗ =−cpap

.

Allora il vincolo u′Ap e soddisfatto con l’uguaglianza e la variabile p entra

in base. Considerando nuovamente la (71), si puo notare che, se α∗ > 0, il

valore duale e aumentato.

26

Analogamente a quanto fatto per il simplesso primale, si puo dimostrare

che la matrice di base ottenuta sostituendo la q–esima colonna di B con la

colonna Ap e non singolare, e che quindi u′ e una nuova soluzione di base.

Se le componenti della corrispondente soluzione di base primale sono tutte

non negative, allora la soluzioni di base primale corrente e ottima. In caso

contrario, si esegue una nuova iterazione.

Anche in questo caso, se vengono utilizzate regole anticiclaggio, il metodo

termina in un numero finito di passi o producendo una soluzione ottima o

determinando che il problema primale e inammissibile.

Bibliografia

Il materiale contenuto nella dispensa e ampiamente e liberamente tratto dal

testo: P. Serafini, Ottimizzazione, Zanichelli, 2000, (cap. 6 e 7).

Altri riferimenti bibliografici:

D. Goldfarb e M.J. Todd, Linear Programming, in Optimization, Handbooks

of Operations Research and Management Science, Vol. 1, North–Holland.

27