UNIVERSIT `A DEGLI STUDI DI FERRARA FACOLT `A DI SCIENZE MATEMATICHE, FISICHE E NATURALI

(1)

UNIVERSIT ` A DEGLI STUDI DI FERRARA

FACOLT `A DI SCIENZE MATEMATICHE, FISICHE E NATURALI

Corso di Laurea Specialistica in MATEMATICA

IL LEMMA DI FARKAS E LE CONDIZIONI DI KARUSH-KUHN-TUCKER

NELL’OTTIMIZZAZIONE LINEARE E NON LINEARE

Relatori:

Chiar.mo Prof.

Josef Eschgf ¨aller

Dott.ssa Silvia Bonettini

Laureanda:

Monica Gazzetta

Anno Accademico 2008-2009

(2)

(3)

Indice

Introduzione 3

I. IL METODO DEL SIMPLESSO

1. Il lemma di Farkas 5

2. Programmi lineari in forma standard 13 3. Programmi lineari in forma normale 18

4. Il metodo del simplesso 26

5. Geometria elementare degli insiemi convessi 31 II. ALCUNE APPLICAZIONI

6. Il separatore di Bennett-Mangasarian 37

7. Grafi 40

8. Flussi in un grafo diretto 44

III. OTTIMIZZAZIONE NON LINEARE

9. Il cono tangente 54

10. Le condizioni di Karush-Kuhn-Tucker 57

11. Il caso generale 60

12. Restrizioni lineari 64

13. Restrizioni convesse 65

Bibliografia 69

(4)

(5)

Introduzione

Lo scopo di questa tesi `e quello di presentare ed approfondire (anche dal punto di vista geometrico ed algebrico) alcuni concetti basilari della programmazione lineare e non lineare che sono il lemma di Farkas e le condizioni di Karush-Kuhn-Tucker (dette anche condizioni di KKT).

In questo lavoro inoltre, `e stato descritto un algoritmo di risoluzione per problemi di programmazione lineare, il metodo del simplesso, e sono state presentate alcune sue possibili applicazioni pratiche.

Il lemma di Farkas è l’argomento del primo capitolo ed è forse il pi ù importante teorema di alternativa per sistemi lineari e viene inoltre utilizzato in numerosi contesti come la programmazione lineare e non lineare, la teoria dei sistemi di disequazioni lineari, i modelli economi- ci multisettoriali e la teoria dei giochi.

Questo lemma afferma che il sistemaAx = b ( dove A `e una matrice m × n e x e b sono vettori rispettivamente appartenenti ad R^m ed Rⁿ) con la condizionex ≥ 0 ammette soluzione se e solo se non la ammette il sistema costituito dalle due condizioniyA ≥ 0 e yb < 0 con y ∈ Rm.

Grazie al lemma di Farkas, si pu`o dimostrare, sotto opportune ipotesi, che se un punto `e soluzione di un problema di programmazione in generale non lineare, allora in tale punto sono soddisfatte le condizioni di KKT.

Le condizioni di Karush-Kuhn-Tucker sono descritte nel capitolo 10 e costituiscono la parte fondamentale della terza sezione della tesi.

Esse sono una generalizzazione del metodo dei moltiplicatori di La- grange applicato a problemi in cui sono presenti anche vincoli di disuguaglianza e rappresentano lo scheletro della programmazione non lineare costituendo condizioni necessarie per la soluzione di un problema di programmazione non lineare in cui i vincoli soddisfano opportune condizioni di regolarit `a dette condizioni di qualificazione dei vincoli. Esempi di queste qualificazioni che vengono trattate nella tesi sono il requisito di indipendenza lineare dei vincoli e il requisito di Mangasarian-Fromovitz. Per problemi di programmazione lineare invece, le condizioni di KKT sono sia necessarie che sufficienti. Queste questioni vengono descritte nei capitoli 11, 12 e 13 dove sono presenti rispettivamente vincoli generici, vincoli lineari e vincoli convessi. Nel capitolo 9 diamo alcune definizioni che caratterizzano le condizioni di KKT dal punto di vista geometrico.

La prima parte della tesi riguarda la teoria e l’implementazione del metodo del simplesso. Questo algoritmo è stato inventato dal matema- tico e statistico statunitense George B. Dantzig nel 1947 e rappresenta ancora oggi uno dei metodi pi ù famosi e pi ù efficaci nella risoluzione di problemi di programmazione lineare, problemi in cui si cerca di mas- simizzare o minimizzare una funzione lineare sotto opportuni vincoli di uguaglianza e disuguaglianza anch’essi lineari.

L’insieme di definizione dei vincoli `e detto insieme ammissibile ed `e un poliedro convesso. Se il problema di programmazione lineare am-

(6)

mette una soluzione ottimale, questa `e anche un vertice del poliedro (teorema fondamentale della programmazione lineare, cap. 3).

Queste considerazioni geometriche sono alla base del metodo inventa- to da Dantzig, la cui idea principale pu`o quindi essere cos`ı descritta:

si determina un vertice iniziale del poliedro e si decide se tale punto

è una soluzione ottima; se non lo è si determina in modo adeguato un nuovo vertice del poliedro e se ne testa l’ottimalit à e cos`ı via.

L’algoritmo del simplesso si applica in una prima formulazione ai programmi lineari nella formaf x = max (risp. min), x ≥ 0, Ax = b (forma normale) oggetto del capitolo 3. Questo tuttavia non è limitativo perchè, come viene descritto nel cap. 2, ogni altro programma lineare può essere ricondotto alla forma normale utilizzando opportune varia- bili di slack o di surplus. Gli aspetti teorici del metodo del simplesso vengono approfonditi nel capitolo 3 mentre l’algoritmo tradotto in Mat- lab (o Octave) è presentato nel quarto capitolo. Nel capitolo 5 vengono invece descritte alcune propriet à degli insiemi convessi.

Nella seconda parte della tesi esponiamo alcuni possibili campi di applicazione del metodo del simplesso: la teoria dei grafi e dei flussi, risp. capitoli 7 e 8, e il separatore di Bennett-Mangasarian nel cap. 6.

In quest’ultimo in particolare si cerca di far vedere come il problema di trovare un iperpiano che separa due insiemi di punti distinti possa essere ricondotto ad un problema di programmazione lineare. `E un risultato che viene ad esempio utilizzato nella ricerca sperimentale riguardante la diagnosi e la prognosi del carcinoma mammario.

E opportuno ricordare che oltre al metodo del simplesso esistono` altri metodi altrettanto efficaci per la risoluzione di problemi di programmazione lineare e non lineare: i metodi a punto interno.

Questi dal punto di vista geometrico si differenziano notevolmente dal metodo del simplesso in quanto la ricerca della soluzione ottimale non viene effettuata esaminando i vertici del poliedro ammissibile ma ri- manendo all’interno dell’insieme di definizione dei vincoli. I metodi a punto interno discendono dalla condizioni di KKT opportunamen- te modificate (in modo da rimanere sempre all’interno della regione ammissibile) a cui viene applicato il metodo di Newton.

(7)

I. IL METODO DEL SIMPLESSO 1. Il lemma di Farkas

Situazione 1.1.n, m ∈ N + 1.

Definizione 1.2. Usiamo le seguenti notazioni:

Rⁿ

m := insieme delle matrici reali con n righe ed m colonne R_m := R¹_m = insieme dei vettori riga reali con m coefficienti Rⁿ

+:= {x ∈ Rⁿ| x ≥ 0}

R⁺_m := {f ∈ Rm | f ≥ 0}

R⁺:= [0, ∞)

Definizione 1.3. SianoA ∈ R^m_n,X ⊂ Rⁿ,U ⊂ Rm,b ∈ R^m, f ∈ Rn. Definiamo allora:

AX := {Ax | x ∈ X}

U A := {uA | u ∈ U }

(AX = b) := {x ∈ X | Ax = b}

(U A = f ) := {u ∈ U | uA = f } (AX ≤ b) := {x ∈ X | Ax ≤ b}

(U A ≥ f ) := {u ∈ U | uA ≥ f }

In modo analogo sono definiti(AX ≥ b), (U A ≤ f ), ecc.

Avremo quindi ad esempio(ARⁿ₊= b) = {x ∈ Rⁿ₊| Ax = b}.

Nota 1.4. Useremo le seguenti notazioni e formule ben note del calcolo matriciale:

(1) PerA ∈ R^m_n denotiamo conAⁱ la i-esima riga, conAj la j-esima colonna diA.

(2) PerA ∈ R^m_n,B ∈ Rⁿ_s abbiamo allora (AB)ⁱ_j = AⁱBj

(AB)ⁱ = AⁱB (AB)_j = AB_j AB =

Xn α=1

AαB^α

Abbiamo quindi in particolare, perx ∈ Rⁿedf ∈ Rm,

(8)

Ax = Xn α=1

Aαx^α

f A = Xm α=1

fαA^α

(3) Conkx, yk = x^ty risp. kf, gk = f g^tdenoteremo il prodotto scalare dix, y ∈ Rⁿrisp.f, g ∈ Rm.

(4) Per vettori v₁, ..., vk in uno spazio vettoriale sia SV(v₁, ..., vk) il sottospazio vettoriale generato da questi vettori. Similmente per un sottoinsiemeX denoteremo con SV(X) il sottospazio vettoriale generato daX.

(5) PerX ⊂ RⁿsiaX^⊥ := {v ∈ Rⁿ| kx, vk = 0 per ogni x ∈ X}.

X^⊥ `e un sottospazio vettoriale di Rⁿ, anche quando X stesso non `e un sottospazio vettoriale.

(6) W sia un sottospazio vettoriale di Rⁿ. Allora:

dim W + dim W^⊥= n W^⊥⊥= W

Rⁿ= WL W^⊥

(7) Per vettoriv₁, ..., vk in uno spazio vettoriale reale sia POS(v₁, ..., vk) := {λ₁v₁+ ... + λkvk| λ1, ..., λk ∈ R⁺}.

Similmente per un sottoinsiemeX sia

POS(X) := {λ₁x₁ + ... + λkxk | k ≥ 1, λi ∈ R⁺, xi ∈ X per i = 1, ..., k}.

Osservazione 1.5. SiaA ∈ R^m_n. Allora:

(1) ARⁿ= SV(A₁, ..., An).

(2) ARⁿ₊= POS(A₁, ..., An).

Dimostrazione. (1) Siax ∈ Rⁿ. AlloraAx = Xn k=1

A_kx^k∈ SV(A1, ..., A_n) e viceversa. Il punto (2) si dimostra in modo analogo considerando x ∈ Rⁿ₊.

Lemma 1.6. SianoA ∈ R^m_n eb ∈ R^m. Allora sono equivalenti:

(1) b ∈ ARⁿ.

(2) (RmA = 0)b = 0.

Dimostrazione.(1) =⇒ (2): Sia f ∈ Rmconf A = 0. Poich´e per ipotesi b ∈ ARⁿ, esistex ∈ Rⁿtale cheb = Ax. Allora f b = f Ax = 0.

(2) =⇒ (1): Sia b /∈ ARⁿ= SV(A₁, ..., An) =: W . Per la nota 1.4b = w + y con w ∈ W e y ∈ W^⊥. Necessariamentey 6= 0 perch´e b 6∈ W . Abbiamo

(9)

kb, yk = kw + y, yk = kw, yk + ky, yk = ky, yk 6= 0

Inoltre kAj, yk = 0 per ogni j perch´e y ∈ W^⊥. Con f := y^t abbiamo alloraf A = 0 ed f b 6= 0.

Definizione 1.7.V sia uno spazio vettoriale reale ed x, y ∈ V . Poniamo allora

[x, y] := x + [0, 1](y − x) = {x + t(y − x) | t ∈ [0, 1]}

Un sottoinsieme X ⊂ V si dice convesso se per ogni x, y ∈ X si ha [x, y] ⊂ X.

Pert ∈ R sia [x, y]t:= x + t(y − x).

Osservazione 1.8.V e W siano spazi vettoriali reali ed x, y ∈ V . ϕ : V → W sia un’applicazione affine. Allora:

(1) ϕ([x, y]t) = [ϕ(x), ϕ(y)]tper ognit ∈ R.

(2) ϕ([x, y]) = [ϕ(x), ϕ(y)].

(3) SeX `e un sottoinsieme convesso di V , allora ϕ(X) `e un sottoinsieme convesso diW .

Dimostrazione. (1) Per ipotesi esistono un’applicazione lineare ϕ₀ : V −→ W e un vettore b ∈ W tali che ϕ = ϕ₀+ b. Abbiamo allora ϕ(x + t(y − x)) = ϕ₀(x + t(y − x)) + b = ϕ₀(x) + tϕ₀(y) − tϕ₀(x) + b = ϕ₀(x) + b + t(ϕ₀(y) + b − ϕ₀(x) − b) = ϕ(x) + t(ϕ(y) − ϕ(x)) = [ϕ(x), ϕ(y)]t.

(2) Dal punto (1) abbiamo direttamenteϕ([x, y]) ⊂ [ϕ(x), ϕ(y)].

Siaz ∈ [ϕ(x), ϕ(y)], ad esempio z = [ϕ(x), ϕ(y)]t cont ∈ [0, 1]. Allora z = ϕ([x, y]t) ∈ ϕ([x, y]).

(3) Sianou = ϕ(x) e v = ϕ(y) con x, y ∈ X. Allora

[u, v] = [ϕ(x), ϕ(y)] = ϕ([x, y]) ⊂ ϕ(X). Nell’ultima inclusione abbiamo sfruttato il fatto che[x, y] ⊂ X perch´e X `e convesso.

Lemma 1.9. v₁, ..., v_k siano vettori linearmente indipendenti di R^m. Allora l’insiemePOS(v₁, ..., vk) `e chiuso.

Dimostrazione. Possiamo trovarev_k+1, ..., vm tali che

v1, ..., vk, v_k+1, ..., vm sia una base di R^m. Per ogni x ∈ R^m esistono λ¹(x), ..., λ^m(x) ∈ R tali che x = λ¹(x)v₁ + ... + λ^m(x)vm. Le funzioni λⁱ : R^m→ R che cos`ı otteniamo sono continue. Perci`o l’insieme

POS(v₁, ..., vk) = (λ¹ ≥ 0, ..., λ^k ≥ 0, λ^k+1 = 0, ..., λ^m = 0) `e chiuso.

Proposizione 1.10 (lemma di Carath ´eodory). SiaX ⊂ R^me SV(X) 6= 0. Sia d := dim SV(X). Allora:

(1) Ogni punto diPOS(X) `e combinazione lineare a coefficienti non negativi di al massimod punti linearmente indipendenti di X.

(2) Sia D la famiglia di tutti gli insiemi che consistono di esatta- mented vettori linearmente indipendenti di X.

AlloraPOS(X) = [

D∈D

POS(D).

(10)

Dimostrazione. (1) Siav ∈ POS(X). Esistono quindi λ₁, ..., λk ≥ 0 ed x₁, ..., x_k ∈ X tali che v = λ1x₁+ ... + λ_kx_k. Scegliamok minimale (ci`o implicaλj > 0 per ogni j) e supponiamo per assurdo che k > d.

Siccome per ipotesidim SV(X) = d, i vettori x₁, ..., x_k devono essere linearmente dipendenti, perci`o esistono α₁, ..., αk ∈ R non tutti nulli tali cheα₁x₁+ ... + α_kx_k = 0.

Possiamo assumere cheα₁ > 0 e cheα₁ λ₁ ≥ αj

λ_j per ognij. Ci`o implica λj ≥ αj

α₁λ₁ per ognij. Abbiamo per`o Xk j=1

(λj− αj

α₁λ₁)xj = v.

In questa rappresentazione tutti i coefficienti sono ≥ 0 e il primo `e nullo, in contraddizione alla minimalit `a dik.

(2) Ci`o implica anche chePOS(X) ⊂ [

D∈D

POS(D) perch´e per il punto (1) per ogni elemento x ∈ POS(X) esistono elementi x₁, ..., x_k ∈ X linearmente indipendenti con x ∈ POS(x1, ..., xk) e k ≤ d; se k < d, allora possiamo trovarex_k+1, ..., xdtali che

{x1, ..., x_k, x_k+1, ..., x_d} =: D ∈ D con naturalmente ancora x ∈ POS(D).

ViceversaPOS(D) ⊂ POS(X) per ogni D ∈ D.

Proposizione 1.11. Sianov1, ..., vk∈ R^m. Allora l’insiemePOS(v1, ..., vk)

`e chiuso.

Dimostrazione. Sia X = {v₁, ..., vk}. D sia definito come nella prop.

1.10. AlloraPOS(X) = [

D∈D

POS(D). Per il lemma 1.9 per ogni

D ∈ D l’insieme POS(D) è chiuso. Nel nostro caso D è un insieme finito e quindi anchePOS(X) è chiuso.

Corollario 1.12. SiaA ∈ R^m_n. Allora l’insiemeARⁿ₊ `e chiuso in R^m. Dimostrazione. Per l’oss. 1.5 abbiamoARⁿ₊= POS(A1, ..., An).

L’enunciato segue dalla proposizione 1.11.

Osservazione 1.13. L’enunciato del cor. 1.12 non è banale, perché in genere un’applicazione lineare Rⁿ−→ R^mnon trasforma chiusi in chiusi. Un esempio è la proiezione sulla prima coordinata R² → R che trasforma l’iperbole{x | x¹x² = 1}, un insieme chiuso, in R \ 0.

Osservazione 1.14. X sia un sottoinsieme chiuso e non vuoto di R^m edy ∈ R^m. Allora esiste un punto p ∈ X che possiede distanza minimale day.

Dimostrazione. Siccome X 6= ∅, possiamo scegliere un punto (arbi- trario)z ∈ X. Allora l’insieme A =: {a ∈ X | |a−y| ≤ |z−y|} `e compatto e non vuoto, per cui la funzione continua

a |a − y| : A −→ R assume un minimo in qualche puntop.

Lemma 1.15 (legge del parallelogramma). Sianox, y ∈ R^m. Allora

(11)

|x + y|²+ |x − y|² = 2|x|²+ 2|y|²

Dimostrazione.|x + y|²+ |x − y|²= |x|²+ |y|²+ 2kx, yk + |x|²+ |y|²− 2kx, yk = 2|x|²+ 2|y|².

Teorema 1.16.X sia un sottoinsieme chiuso, convesso e non vuoto di R^m ed y ∈ R^m. Allora esiste un punto p ∈ X che possiede distanza minimale day. p `e univocamente determinato.

Dimostrazione. (1) L’esistenza `e stata dimostrata nell’oss.1.14.

(2) Dimostriamo l’unicit `a . Siaq ∈ X tale che |p − y| = |q − y|.

Allorar := ^p+q₂ ∈ X perch`e X `e convesso. Inoltre

|r − y|²= |p − y|²−¹₄|p − q|² (*)

Infatti per il lemma 1.15 applicato ax = p − y e y = q − y risulta 4|r − y|²= 4|p + q

2 − y|²

= |(p − y) + (q − y)|²

= 2|p − y|²+ 2|q − y|²− |p − q|²

= 4|p − y|²− |p − q|²

dove abbiamo utilizzato l’ipotesi|p−y| = |q−y|. Ci`o mostra l’uguaglianza (*). Se fosse p 6= q, risulterebbe |r − y| < |p − y| e p non avrebbe pi ´u distanza minimale day.

L’uguaglianza (*) e la relazione|r−y|² < |p−y|²perp 6= q sono anche evidenti dalla figura.

y p

q r

Definizione 1.17. Nella situazione del teorema 1.16 il puntop si chia- ma la proiezione diy su X. `E immediato chey = p se e solo se y ∈ X.

Definizione 1.18. Perp, v ∈ R^m poniamo:

H(p, v) := {x ∈ R^m| kx − p, vk = 0}

O(p, v) := {x ∈ R^m| kx − p, vk ≤ 0}

SO(p, v) := {x ∈ R^m| kx − p, vk < 0}

Se v 6= 0, allora H(p, v) `e l’iperpiano ortogonale a v passante per p, O(p, v) l’insieme dei punti che, riferendoci a p + v, si trovano oltre o su questo iperpiano, O(p, −v) l’insieme dei punti che non si trovano oltre questo iperpiano, cio`e dalla stessa parte di p + v. SO significa strettamente oltre.

(12)

Proposizione 1.19.X sia un sottoinsieme chiuso, convesso e non vuoto di R^medy ∈ R^m. Per un punto p ∈ X sono allora equivalenti:

(1) p `e la proiezione di y su X.

(2) X ⊂ O(p, y − p).

Dimostrazione.(1) =⇒ (2): Siano p la proiezione di y su X ed x ∈ X.

Allora per ognit ∈ [0, 1] il punto p + t(x − p) ∈ X perch`e X `e convesso.

Per la definizione dip abbiamo

|y − p|² ≤|y − (p + t(x − p))|² =

|(y − p) − t(x − p)|² =

|y − p|²+ t²|x − p|²− 2tky − p, x − pk . ovvero

2tky − p, x − pk ≤ t²|x − p|²

Per ognit ∈ (0, 1] abbiamo perciò 2ky − p, x − pk ≤ t|x − p|². Ciò è possibile solo seky − p, x − pk ≤ 0.

(2) =⇒ (1): Siano X ⊂ O(p, y − p) ed x ∈ X. Allora ky − p, p − xk ≥ 0 e quindi

|y − x|² = |y − p + p − x|²= |y − p|²+ |p − x|²+ 2ky − p, p − xk ≥ |y − p|² Lemma 1.20. X sia un sottoinsieme chiuso, convesso e non vuoto di R^medy ∈ R^m.p sia la proiezione di y su X. Allora:

(1) X ⊂ O(p + t(y − p), y − p) per ogni t ≥ 0.

(2) In particolareX ⊂ O(y, y − p).

(3) Sey /∈ X, allora X ⊂ SO(y, y − p).

Dimostrazione. Siax ∈ X. Allora per t ≥ 0 si ha

k(x − p) − t(y − p), y − pk = kx − p, y − pk − t|y − p|² ≤ 0 essendo per la prop 1.19kx − p, y − pk ≤ 0.

Sia oray /∈ X. Allora y 6= p e quindi per t = 1 otteniamo kx − y, y − pk = kx − p, y − pk − |y − p|² < 0.

Lemma 1.21. X sia un sottoinsieme chiuso, convesso e non vuoto di R^medy ∈ R^m\ X. p sia la proiezione di y su X ed y^∗ := ^p+y₂ . Allora:

y ∈ SO(y^∗, p − y) X ⊂ SO(y^∗, y − p)

(13)

Dimostrazione.

(1)2ky − y^∗, p − yk = 2ky −p + y

2 , p − yk = −ky − p, y − pk < 0 (2) Siax ∈ X. Allora

2kx − y^∗, y − pk = 2kx − p + y

2 , y − pk

= kx − p, y − pk + kx − y, y − pk < 0

Infatti per la prop. 1.19 abbiamokx − p, y − pk ≤ 0, mentre dal lemma 1.20 segue chekx − y, y − pk < 0.

y p

X

Corollario 1.22.X sia un sottoinsieme chiuso, convesso e non vuoto di R^m edy ∈ R^m\ X. p sia la proiezione di y su X. Sia ancora y^∗ := ^p+y₂ . Allora

ky, y − pk > ky^∗, y − pk > kx, y − pk per ognix ∈ X.

Dimostrazione. Siax ∈ X. Per il lemma 1.21 abbiamo ky − y^∗, y − pk > 0 > kx − y^∗, y − pk

ovvero

ky, y − pk − ky^∗, y − pk > 0 > kx, y − pk − ky^∗, y − pk e quindi

ky, y − pk > ky^∗, y − pk > kx, y − pk

Corollario 1.23. X sia un sottoinsieme chiuso e convesso di R^m ed y ∈ R^m\ X. Allora esistono α ∈ R ed f ∈ Rm tali chef y > α > f x per ognix ∈ X. Sostituendo f con −f ed α con −α possiamo naturalmente anche otteneref y < α < f x per ogni x ∈ X.

Dimostrazione. L’enunciato `e banale per X = ∅ e segue altrimenti dal corollario 1.22, se poniamof := (y − p)^tedα := ky^∗, y − pk

Osservazione 1.24. SiaX ⊂ R^m. AlloraPOS(X) `e convesso.

Dimostrazione. Sianou, v ∈ POS(X). Allora esistono λ₁, ..., λ_k, µ₁, ..., µ_l∈ R⁺ex₁, ..., x_k, y₁, ..., y_l∈ X tali che

u = λ₁x₁+ ... + λkxk ev = µ₁y₁+ ... + µlyl. Siat ∈ [0, 1]. Allora

(14)

u + t(v − u) = λ₁x₁+ ... + λ_kx_k+ tµ₁y₁+ ... + tµ_ly_l− tλ1x₁− ... − tλkx_k

= (1 − t)λ₁x₁+ ... + (1 − t)λ_kx_k+ tµ₁y₁+ ... + tµ_ly_l

I coefficienti(1 − t)λ_ietµ_j sono tutti non negativi, per cui vediamo che u + t(v − u) ∈ POS(X).

Corollario 1.25. SiaA ∈ R^m_n. AlloraARⁿ₊ `e convesso.

Dimostrazione. Ci`o segue dall’oss. 1.24 perch´eARⁿ₊= POS(A₁, ..., A_n) per l’oss. 1.5.

Teorema 1.26 (lemma di Farkas). Siano A ∈ R^m_n e b ∈ R^m. Allora sono equivalenti:

(1) b ∈ ARⁿ₊.

(2) (RmA ≥ 0)b ≥ 0.

Dimostrazione.(1) =⇒ (2): Siano x ∈ Rⁿ₊ edf ∈ Rm tali cheb = Ax edf A ≥ 0. Allora f b = f Ax ≥ 0.

(2) =⇒ (1): Sia b /∈ ARⁿ₊. Dai corollari 1.12 e 1.25 sappiamo cheARⁿ₊

`e un sottoinsieme convesso, chiuso e non vuoto di R^m; quindi per il corollario 1.23 esistonoα ∈ R e f ∈ Rm tali chef b < α < f Ax per ogni x ∈ Rⁿ₊. Ci`o deve valere in particolare perx = 0 e questo implica α < 0 e quindi anchef b < 0.

D’altra parte peròf A ≥ 0 e ciò è in contraddizione con l’ipotesi (2).

Infatti sia ad esempio f Aj < 0. Siccome x := tAj = Atδj ∈ ARⁿ₊, abbiamo α < f tAj = tf Aj per ogni t ≥ 0, ma ciò non è possibile perché lim

t−→∞tf A_j = −∞.

Osservazione 1.27. Siano A ∈ R^m_n e b ∈ R^m. Denotiamo con δ la matrice identica in Rⁿ_n. Allora:

(1) (A δ)Rⁿ₊= {Ax + u | x ∈ Rⁿ₊, u ∈ R^m₊}.

(2) (ARⁿ₊ ≤ b) 6= ∅ ⇐⇒ b ∈ (A δ)Rⁿ₊.

Proposizione 1.28. SianoA ∈ R^m_n eb ∈ R^m. Allora sono equivalenti:

(1) (ARⁿ₊ ≤ b) 6= ∅.

(2) (R⁺_mA ≥ 0)b ≥ 0.

Dimostrazione.(1) =⇒ (2): Siano x ∈ Rⁿ₊ edf ∈ R⁺_m tali cheAx ≤ b edf A ≥ 0. Allora f b ≥ f Ax ≥ 0.

(2) =⇒ (1): Supponiamo che (ARⁿ₊≤ b) = ∅. Per l’oss. 1.27 ciò significa cheb /∈ (A δ)Rⁿ₊. Per il teorema 1.26 possiamo quindi trovare un f ∈ Rmtale chef (A δ) ≥ 0 ed f b < 0. Ma f (A δ) = (f A f ) ≥ 0 è equivalente alle due condizionif A ≥ 0 ed f ≥ 0, cioè ad f ∈ (R⁺_mA ≥ 0).

Adesso per`of b < 0 `e in contrasto con la nostra ipotesi.

(15)

2. Programmi lineari in forma standard

Situazione 2.1.n, m ∈ N + 1 ed A ∈ R^m_n,f ∈ Rn,b ∈ R^m, quando non indicato diversamente.

Definizione 2.2. Un programma lineare di massimizzazione in forma standard `e un problema di ottimizzazione della forma

f x = max x ≥ 0 Ax ≤ b

conA, f, b come nella situazione 2.1.

Si cercano quindi vettori non negativix ∈ Rⁿper i qualif x `e massi- male sotto il vincoloAx ≤ b.

Denotiamo con (f (ARⁿ₊ ≤ b) = max) l’insieme degli x ∈ Rⁿ₊ (detti soluzionidel problema) con Ax ≤ b in cui f x assume un massimo su (ARⁿ₊≤ b), mentre indichiamo con f (ARⁿ₊≤ b) = max (senza parentesi esterne) il problema stesso.

Gli elementi di(ARⁿ₊≤ b) si chiamano punti ammissibili del proble- ma.

Definizione 2.3. Un programma lineare di minimizzazione in forma standard `e un problema di ottimizzazione della forma

ub = min u ≥ 0 uA ≥ f

conA, f, b come nella situazione 2.1.

Si cercano quindi vettori riga non negativi u ∈ Rm per i quali ub `e minimale sotto il vincolouA ≥ f .

Denotiamo con ((R⁺_mA ≥ f )b = min) l’insieme degli u ∈ R⁺_m (detti soluzioni del problema) con uA ≥ f in cui ub assume un minimo su (R⁺_mA ≥ f ), mentre indichiamo con (R⁺_mA ≥ f )b = min (senza parentesi esterne) il problema stesso.

Gli elementi di (R⁺_mA ≥ f ) si chiamano punti ammissibili del problema duale.

Osservazione 2.4. I problemif (ARⁿ₊ ≤ b) = max e (R⁺_mA ≥ f )b = min si determinano a vicenda e si dicono uno il duale dell’altro.

Lemma 2.5. Siano x una soluzione del problema f (ARⁿ₊ ≤ b) = max edu una soluzione del problema (R⁺_mA ≥ f )b = min.

Alloraf x ≤ uAx ≤ ub.

Dimostrazione. Per ipotesiAx ≤ b e f ≤ uA con x ≥ 0 e f ≥ 0, per cuif x ≤ uAx ≤ ub.

Proposizione 2.6. Siano x ∈ (ARⁿ₊ ≤ b) ed u ∈ (R⁺_mA ≥ f ) tali che f x ≥ ub.

(16)

Allorax `e una soluzione di f (ARⁿ₊ ≤ b) = max ed u una soluzione di (R⁺_mA ≥ f )b = min.

Dimostrazione. Sianoy ∈ (ARⁿ₊ ≤ b) e v ∈ (R⁺_mA ≥ f ). Per il lemma 2.5 abbiamof y ≤ ub ≤ f x ≤ vb.

Proposizione 2.7. (1) Sia (ARⁿ₊ ≤ b) = ∅. Allora o (R⁺_mA ≥ f ) = ∅ oppure l’insieme(R⁺_mA ≥ f )b non `e limitato inferiormente. Il problema (R⁺_mA ≥ f )b = min quindi non possiede soluzione.

(2)Sia (R⁺_mA ≥ f ) = ∅. Allora o (ARⁿ₊ ≤ b) = ∅ oppure l’insieme f (ARⁿ₊≤ b) non `e limitato superiormente.

Il problemaf (ARⁿ₊≤ b) = max quindi non possiede soluzione.

Dimostrazione. Dimostriamo solo il primo enunciato essendo il se- condo il suo duale. Sia(ARⁿ₊ ≤ b) = ∅. Per la prop. 1.28 esiste quindi un elementog ∈ R⁺_m tale chegA ≥ 0 e gb < 0.

Se(R⁺_mA ≥ f ) = ∅ `e chiaro che il problema (R⁺_mA ≥ f )b = min non possiede soluzione.

Assumiamo quindi che (R⁺_mA ≥ f ) 6= ∅. Sia ad esempio u ∈ R⁺_m tale cheuA ≥ f . Allora per ogni λ ≥ 0 si ha che u + λg ≥ 0 e

(u + λg)A = uA + λgA ≥ f , per cui u + λg ∈ (R⁺_mA ≥ f ). Siccome gb < 0, si ha che lim

λ−→∞(u + λg)b = lim

λ−→∞(ub + λgb) = −∞.

Osservazione 2.8. Se il problema f (ARⁿ₊ ≤ b) = max possiede una soluzionex, allora il valore max f (ARⁿ₊≤ b) = f x `e ben definito.

Similmente, se il problema(R⁺_mA ≥ f )b = min possiede una soluzio- neu, allora il valore min(R⁺_mA ≥ f )b = ub `e ben definito.

Teorema 2.9. Gli insiemi(ARⁿ₊≤ b) e (R⁺_mA ≥ f ) siano entrambi non vuoti. Allora i problemif (ARⁿ₊ ≤ b) = max e (R⁺_mA ≥ f )b = min sono entrambi risolubili e si ha

max f (ARⁿ₊≤ b) = min(R⁺_mA ≥ f )b

Dimostrazione. (1) `E sufficiente dimostrare che esistono

x ∈ (ARⁿ₊≤ b) ed u ∈ (R⁺_mA ≥ f ) tali che f x ≥ ub. L’enunciato allora si ottiene applicando la prop. 2.6.

(2) Il nostro scopo quindi è quello di trovare un elementox ∈ Rⁿ₊ed un elementou ∈ R⁺_m tali che Ax ≤ b, uA ≥ f (cioè −A^tu^t ≤ −f^t) ed f x ≥ ub. L’ultima disuguaglianza è equivalente a −f x + b^tu ≤ 0.

(3) Scrivendo il problema in forma matriciale, ponendo B :=



 A 0

0 −A^t

−f b^t



 ∈ R^m+n+1_m+n e c :=



 b

−f^t 0



 ∈ R^m+n+1

dobbiamo dimostrare che(BR^m+n₊ ≤ c) 6= ∅.

(4) Ma per la prop.1.28 in caso contrario esistep ∈ R⁺_m+n+1 tale che pB ≥ 0 e pc < 0.

p `e quindi della forma p = (g h α) con g ∈ R⁺_m,h ∈ R⁺_n edα ∈ R⁺. Inoltre

(17)

pB = (g h α)



 A 0

0 −A^t

−f b^t



 = (gA − αf − hA^t+ αb^t) ≥ 0 e

pc = (g h α)



 b

−f^t 0



 = gb − hf^t< 0

cosicch´e otteniamo (I) gA ≥ αf (II) αb^t≥ hA^t (III) gb < hf^t

Essendoα ∈ R⁺, abbiamoα = 0 oppure α > 0. Dimostriamo che entrambi i casi implicano una contraddizione.

(5) Siaα = 0. Allora gA ≥ 0 ≥ hA^t. Per ipotesi gli insiemi(ARⁿ₊≤ b) e(R⁺_mA ≥ f ) sono entrambi non vuoti. Perci`o esistono x ∈ Rⁿ₊ed u ∈ R⁺_m tali cheAx ≤ b ed uA ≥ f , quindi anche A^tu^t≥ f^t. Ma allora

gb ≥ gAx ≥ 0 ≥ hA^tu^t≥ hf^t

e questo contraddice la disuguaglianza (III).

(6) Rimane il casoα > 0. Le disuguaglianze (I) e (II) significano per`o che g

α ∈ (R⁺_mA ≥ f ) e h^t

α ∈ (ARⁿ₊ ≤ b).

Dal lemma 2.5 segue fh^t α ≤ g

αb ovvero hf^t = f h^t ≤ gb, ancora in contrasto con (III).

Corollario 2.10. Sianox ∈ (ARⁿ₊ ≤ b) ed u ∈ (R⁺_mA ≥ f ). Allora sono equivalenti:

(1) x `e una soluzione di f (ARⁿ₊ ≤ b) = max ed u una soluzione di (R⁺_mA ≥ f )b = min.

(2) f x = ub.

(3) f x = uAx = ub.

(4) f x ≥ ub.

Dimostrazione.(1) =⇒ (2): Teorema 2.9.

(2) =⇒ (3): Per il lemma 2.5 si ha f x ≤ uAx ≤ ub, ma essendo per ipotesif x = ub segue che f x = uAx = ub.

(3) =⇒ (4): Chiaro.

(4) =⇒ (1): Proposizione 2.6.

(18)

Nota 2.11. Come nella dimostrazione del teorema 2.9 siano B :=



 A 0

0 −A^t

−f b^t



 ∈ R^m+n+1_m+n e c :=



 b

−f^t 0



 ∈ R^m+n+1.

(1) Siaz ∈ (BR^m+n₊ ≤ c) con z =

x y

,x ∈ Rⁿ₊edy ∈ R^m₊.

Se poniamou := y^t, allorax `e una soluzione di f (ARⁿ₊≤ b) = max ed u

`e una soluzione di (R⁺_mA ≥ f )b = min.

(2) Siano viceversa x una soluzione di f (ARⁿ₊ ≤ b) = max ed u una soluzione di(R⁺_mA ≥ f )b = min. Allora con y := u^tabbiamo

z :=

x y

∈ (BR^m+n₊ ≤ c).

Dimostrazione. Sianoz, x, y, u come nell’enunciato. Abbiamo quindi le seguenti disuguaglianze:

x ≥ 0, y ≥ 0 Ax ≤ b

−A^tu^t≤ −f^t

−f x + b^tu^t≤ 0

La terza disuguaglianza `e equivalente aduA ≥ f , la quarta, essendo b^tu^t= ub, `e equivalente a f x ≥ ub.

Il punto (1) segue adesso dalla prop. 2.6, il punto (2) combinando il teorema 2.9 con la prop. 2.6.

Osservazione 2.12. Il teorema 2.9 e la nota 2.11 dimostrano l’importanza e l’utilit à del principio di dualit à nella programmazione lineare. Vedia- mo in particolare che la sola ricerca di un punto ammissibile (senza un compito di massimizzazione o minimizzazione) non è pi ù facile della soluzione del problema di ottimizzazione che, come visto nella nota 2.11, può essere ricondotta alla ricerca di un punto ammissibile.

Esempio 2.13. Consideriamo il seguente problema di massimo:

x¹+ 2x² = max 7x¹+ 4x² ≤ 28 4x¹+ 5x² ≤ 20 3x¹+ 10x² ≤ 30

Per la nota 2.11 questo problema di ottimizzazione `e equivalente a quello della ricerca di un punto

z =





 x¹ x² y¹ y² y³







che soddisfa la disuguaglianza

(19)







7 4 0 0 0

4 5 0 0 0

3 10 0 0 0

0 0 −7 −4 −3

0 0 −4 −5 −3

−1 −2 28 20 30











 x¹ x² y¹ y² y³





≤





 28 20 30

−1

−2 0







Corollario 2.14. (1)x sia una soluzione di f (ARⁿ₊≤ b) = max

e 1 ≤ k ≤ m. Se esiste una soluzione u di (R⁺_mA ≥ f )b = min tale che uk6= 0, allora A^kx = b^k.

(2) u sia una soluzione di (R⁺_mA ≥ f )b = min e 1 ≤ k ≤ n. Se esiste una soluzionex di f (ARⁿ₊ ≤ b) = max tale che x^k6= 0, allora uAk= fk.

Dimostrazione. Dimostriamo solo il primo enunciato, essendo il se- condo il suo duale.

Per il corollario 2.10uAx = ub, e quindi u(b − Ax) = 0, cio`e Xm

j=1

uj(b^j − A^jx) = 0. Per ipotesi per`o u ≥ 0 e b − Ax ≥ 0, quindi uj(b^j− A^jx) ≥ 0 per ogni j = 1, ..., m. Ma allora necessariamente uj(b^j − A^jx) = 0 per ogni j = 1, ..., m, per cui l’ipotesi uk 6= 0 implica b^k− A^kx = 0.

(20)

3. Programmi lineari in forma normale

Situazione 3.1.n, m ∈ N + 1 ed A ∈ R^m_n,f ∈ Rn,b ∈ R^m, quando non indicato diversamente.

Definizione 3.2. Un programma lineare di massimizzazione (risp. mi- nimizzazione) in forma normale `e un problema di ottimizzazione della forma

f x = max (risp. min) x ≥ 0

Ax = b

conA, f , b come nella situazione 3.1. Gli elementi di (ARⁿ₊ = b) sono detti punti ammissibili.

Nota 3.3. (1) Sia dato un problemaf (ARⁿ₊ ≤ b) = max in forma standard. Introducendo un vettore variabile ausiliariop otteniamo un problema in forma normale

(f 0)

x p

= max

x p

≥ 0 (A δ)

x p

= b

equivalente al primo, nel senso che da ogni soluzione del problema in forma normale otteniamo una soluzione del problema in forma standard.

(2) Viceversa, dato un problemaf (ARⁿ₊= b) = max in forma normale, considerando

f x = max x ≥ 0 Ax ≤ b

−Ax ≤ −b

otteniamo un problema in forma standard equivalente al primo, nel senso che da ogni soluzione del problema in forma standard otteniamo una soluzione del problema in forma normale.

(3) In modo analogo (usando le matrici trasposte) ogni problema di minimizzazione in forma standard (def. 2.3) `e equivalente ad un problema in forma normale e viceversa.

Osservazione 3.4. V e W siano spazi vettoriali reali, ϕ : V −→ W un’applicazione affine edY sia un sottoinsieme convesso di W .

Alloraϕ⁻¹(Y ) `e convesso.

Dimostrazione. Sianoa, b ∈ ϕ⁻¹(Y ), cio`e ϕ(a), ϕ(b) ∈ Y . Per l’oss. 1.8 per`oϕ([a, b]) = [ϕ(a), ϕ(b)] ⊂ Y e quindi, utilizzando l’ipotesi che Y sia convesso, si ha che[a, b] ⊂ ϕ⁻¹(Y ).

(21)

Corollario 3.5. L’insieme(ARⁿ₊ = b) `e chiuso e convesso.

Dimostrazione. Identificando A con l’applicazione

x Ax possiamo scrivere(ARⁿ₊= b) = A⁻¹(b)∩Rⁿ₊. Poich´eA `e continua, l’insieme A⁻¹(b)

è chiuso. Inoltre, essendo A un’applicazione affine e b un convesso, per l’oss. 3.4 anche A⁻¹(b) è convesso. Infine Rⁿ₊ è un chiuso convesso e, siccome l’intersezione di insiemi chiusi e convessi è ancora chiuso e convesso, otteniamo l’enunciato.

Definizione 3.6.V sia uno spazio vettoriale reale ed X un suo sotto- insieme convesso. Un vertice (o punto estremale) diX `e un punto x ∈ X che soddisfa la seguente condizione:

Seu, v ∈ X ed x ∈ [u, v], allora x ∈ {u, v}

Denotiamo convertici(X) l’insieme dei vertici di X.

Esempio 3.7.

(1) X sia un poligono convesso in R². I vertici di X nel senso della geometria elementare coincidono con i vertici nel senso della definizione 3.6.

(2) vertici(Rⁿ) = ∅.

(3) vertici(Rⁿ₊) = {0}.

(4) X := {z ∈ Rⁿ| |z| ≤ 1} sia la palla unitaria chiusa in Rⁿ. Allora vertici(X) = {z ∈ Rⁿ| |z| = 1}.

(5) X := {z ∈ Rⁿ| |z| < 1} sia la palla unitaria aperta in Rⁿ. Allora vertici(X) = ∅.

Lemma 3.8.V sia uno spazio vettoriale reale, X un sottoinsieme con- vesso diV ed x ∈ X. Allora sono equivalenti:

(1) x ∈ vertici(X).

(2) X \ {x} `e convesso.

(3) x = u + v

2 conu, v ∈ X implica u = v.

Dimostrazione. (1) =⇒ (2): Supponiamo per assurdo che esistano u, v ∈ X \{x} tali che [u, v] 6⊂ X \{x}. Allora x ∈ [u, v], ma per ipotesi ci`o implica chex ∈ {u, v}. Quindi ad esempio u = x, una contraddizione.

(2) =⇒ (1): X \ {x} sia convesso ed u, v ∈ X con x ∈ [u, v]. Dobbiamo dimostrare chex ∈ {u, v}. Se cos`ı non fosse avremmo u, v ∈ X \ {x} e quindi per ipotesi[u, v] ⊂ X \ {x}, una contraddizione.

(1) =⇒ (3): Sia 2x = u + v con u, v ∈ X. Per ipotesi x ∈ {u, v}, ad esempiox = u. Allora x = v e quindi u = v.

(3) =⇒ (1): Siano u, v ∈ X ed x = u + t(v − u) con t ∈ [0, 1].

Pert = 0 e t = 1 si ha rispettivamente x = u e x = v.

(22)

Pert = 1

2 l’ipotesi implicau = v e quindi x = u = v.

Rimangono i casi0 < t < 1 2 e 1

2 < t < 1. Per simmetria `e sufficiente trattare il caso0 < t < 1

2.

Poniamoy := u + 2t(v − u). Allora y ∈ X perch´e 0 < 2t < 1. Inoltre y = u + 2(x − u) = 2x − u, cosicch´e x = u + y

2 . L’ipotesi implicau = y e quindix = u.

u y v

x=u+ y 2

Definizione 3.9. Siaα ⊂ {1, ..., n} un sottoinsieme di cardinalit `a

|α| = s. Poniamo allora:

(1) Aα := matrice in R^m_s che si ottiene da A cancellando tutte le colonneAj per cuij /∈ α.

(2) f_α := vettore in R_s che si ottiene daf cancellando gli elementi fj per cuij /∈ α.

(3) Perx ∈ Rⁿsiax^αil vettore in R^sche si ottiene dax cancellando gli elementix^j per cuij /∈ α.

Poniamo inoltre1 − α := {1, ..., n} \ α.

Pers = 0 abbiamo R^m₀ = R⁰= R₀ = 0, per cui A_∅ = f_∅ = x^∅ = ∅.

Con queste convenzioni possiamo scrivere Ax = Aαx^α+ A1−αx^1−α

f x = f_αx^α+ f_1−αx^1−α

Esempio 3.10. SianoA ∈ R³₅ edx ∈ R⁵. Conα = {1, 4} si ha 1 − α = {2, 3, 5}. Perci`o

Aαx^α+ A_1−αx^1−α=





A¹₁ A¹₄ A²₁ A²₄ A³₁ A³₄





x¹ x⁴

+





A¹₂ A¹₃ A¹₅ A²₂ A²₃ A²₅ A³₂ A³₃ A³₅







 x² x³ x⁵





=





A¹₁x¹+ A¹₄x⁴ A²₁x¹+ A²₄x⁴ A³₁x¹+ A³₄x⁴



 +





A¹₂x²+ A¹₃x³+ A¹₅x⁵ A²₂x²+ A²₃x³+ A²₅x⁵ A³₂x²+ A³₃x³+ A³₅x⁵





= Ax

Definizione 3.11. Perx ∈ Rⁿsia[x] := {i ∈ {1, ..., n} | xⁱ 6= 0}.

Osservazione 3.12.0 ∈ vertici(ARⁿ₊ = 0).

Dimostrazione. Usiamo il lemma 3.8. Sianou, v ∈ (ARⁿ₊ = 0) e tali che0 = u + v

2 . `E chiaro che ci`o implicau = v = 0.

(23)

Teorema 3.13. Perx ∈ (ARⁿ₊ = b) sono equivalenti:

(1) x ∈ vertici(ARⁿ₊ = b).

(2) Le colonne diA_[x] sono linearmente indipendenti.

Dimostrazione. Sex = 0, allora [x] = ∅ e l’enunciato segue dall’oss.

3.9, perch´e l’insieme vuoto `e linearmente indipendente. Possiamo quindi assumere chex 6= 0 e che [x] = {1, ..., s} con 1 ≤ s ≤ n.

(1) =⇒ (2): Sia x ∈ vertici(ARⁿ₊= b) e sia λ₁A₁ + ... + λsAs = 0 una combinazione lineare delle colonne Ai con i ∈ [x] e λi ∈ R per i = 1, ..., s. Supponiamo per assurdo che i λi non siano tutti nulli, ad esempio possiamo supporreλ₁6= 0. Siccome xⁱ > 0 per ogni i = 1, . . . , s, possiamo trovare un elemento ε > 0 tale che xⁱ ± ελi ≥ 0 per ogni i = 1, ..., s. Definiamo i vettori

u :=







x¹+ ελ₁ ... x^s+ ελs

0 ... 0







e v :=







x¹− ελ1

... x^s− ελs

0 ... 0







Allorau, v ∈ Rⁿ₊edx =u + v 2 . Inoltre Au =

Ps k=1

Ak(x^k+ ελk) = Ax + ε Ps k=1

λkAk = Ax = b, e simil- menteAv = b. Perciò u, v ∈ (ARⁿ₊= b). Per ipotesi x ∈ vertici(ARⁿ₊= b) e quindi per il punto (3) della prop. 3.8 risultau = v. Ma ciò non è possibile perchèλ₁6= 0.

(2) =⇒ (1): Le colonne di A_[x]siano linearmente indipendenti. Siano u, v ∈ (ARⁿ₊ = b) tali che x = u + v

2 . Ci`o implicauⁱ+ vⁱ = 0 per ogni i = 1, . . . , s, e quindi uⁱ = vⁱ = 0, essendo u, v ≥ 0. D’altra parte abbia- moAu = Av = b e quindi 0 = A(u − v) =

Ps i=1

(uⁱ− vⁱ)A_i. Per ipotesi ci`o implica uⁱ = vⁱ per ognii = 1, . . . , s, e quindi u = v. Per la prop. 3.8 quindi risulta chex ∈ vertici(ARⁿ₊= b).

Definizione 3.14. Siaα ⊂ {1, ..., n}. A si dice α-invertibile, se

|α| = m ≤ n e la matrice quadratica Aα `e invertibile.

Osservazione 3.15. Un insieme di indiciα tale che A sia α-invertibile esiste se e solo se rango(A) = m. Si noti che rango(A) = m da solo implicam ≤ n.

Lemma 3.16.K sia un campo e V uno spazio vettoriale su K. Siano v₁, . . . , v_n ∈ V e W := SV(v1, . . . , v_n). Siano m := dim W e 1 ≤ s ≤ m tali che i vettoriv₁, . . . , vssiano linearmente indipendenti.

(24)

Allora possiamo trovarem − s indici j₁, . . . , jm−s ∈ {s + 1, . . . , n} in modo tale che gli m vettori v₁, . . . , v_s, v_j1, . . . , v_j_m−s siano linearmente indipendenti.

Dimostrazione.(1) Se s = m non c’`e nulla da dimostrare.

Supponiamo quindi che s < m e dimostriamo che esiste un indice j ∈ {s + 1, . . . , n} tale che gli s + 1 vettori v1, . . . , vs, vjsono linearmente indipendenti.

Infatti, se cos`ı non fosse, avremmovj ∈ SV(v₁, . . . , vs) per ogni j ∈ {1, . . . , n} e quindi W = SV(v₁, . . . , v_s) in contraddizione all’ipotesi dim W = m.

(2) Se adesso s + 1 = m, non c’`e pi `u nulla da dimostrare. Altrimenti ripetiamo il ragionamento cons + 1 al posto di s.

Corollario 3.17.x sia un vertice di (ARⁿ₊ = b).

Serango(A) = m, allora [x] `e contenuto in un insieme di indici α tali cheA sia α-invertibile.

Osservazione 3.18. Siax ∈ (ARⁿ₊= b) ed [x] contenuto in un insieme di indiciα tali che A sia α-invertibile. Allora abbiamo x^1−α= 0 e quindi b = Ax = Aαx^α + A_1−αx^1−α = Aαx^α, per cui x^α = A⁻¹_α b. Perci`o x `e univocamente determinato dalle relazioni

x^α= A⁻¹_α b x^1−α= 0

Definizione 3.19. Siarango(A) = m. Poniamo

J(A) := {α ⊂ {1, ..., n} | |α| = m ed Aα invertibile}

J⁺(A, b) := {α ∈ J(A) | A⁻¹_α b ≥ 0}

Proposizione 3.20. Siarango(A) = m. Allora l’applicazione θ : J⁺(A, b) −→ vertici(ARⁿ₊ = b) definita da θ(α) = x con

x^α= A⁻¹_α b x^1−α= 0

`e suriettiva.

Dimostrazione. Ci`o segue dall’oss. 3.18 e dal cor. 3.17.

Corollario 3.21. Sia rango(A) = m. Allora l’insieme dei vertici di (ARⁿ₊= b) `e finito.

Dimostrazione. J⁺(A, b) è finito e quindi, poichè l’immagine di un insieme finito è finito, anchevertici(ARⁿ₊ = b) è un insieme finito.

Proposizione 3.22. Sia(ARⁿ₊= b) 6= ∅. Allora vertici(ARⁿ₊= b) 6= ∅.

Dimostrazione. Scegliamox ∈ (ARⁿ₊= b) in modo tale che |[x]| sia minimale.

(1) Se x = 0, allora b = 0 ed x ∈ vertici(ARⁿ₊= b) per l’oss. 3.12.

(25)

(2) Sia quindi x 6= 0. Poniamo α := [x]. Dobbiamo dimostrare che le colonne diA_α sono linearmente indipendenti. Supponiamo che non lo siano. Allora possiamo trovare un vettoreλ ∈ R^s\ 0 tale che Aαλ = 0.

Possiamo assumere che almeno uno dei coefficienti diλ sia minore di 0.

Siccomexⁱ> 0 per ogni i ∈ α, esiste ε > 0 tale che xⁱ+ ελⁱ ≥ 0 per ogni i ∈ α ed x^h+ ελ^h = 0 per almeno un h ∈ α. Sia ora y ∈ Rⁿ⁺¹ definito dalle relazioni

y^α= x^α+ ελ y^1−α= 0

Alloray ≥ 0, inoltre

Ay = A_αy^α+ A_1−αy^1−α = A_αy^α = A_α(x^α+ ελ)

= Aαx^α+ εAαλ = Aαx^α= Ax = b

Quindi y ∈ (ARⁿ₊ = b) e |[y]| < |[x]|, una contraddizione al fatto che abbiamo sceltox in modo tale che |[x]| sia minimale.

Osservazione 3.23. Il problemaf (ARⁿ₊= b) = max abbia una soluzione. Se poniamoµ := max f (ARⁿ₊ = b), allora con

B :=

A f

, c :=

b µ

si ha (f (ARⁿ₊= b) = max) = (BRⁿ₊= c).

Per il cor. 3.5 l’insieme(f (ARⁿ₊= b) = max) è perciò chiuso e convesso (ciò è banalmente vero anche quando è vuoto).

Proposizione 3.24.

vertici(f (ARⁿ₊= b) = max) = (f (ARⁿ₊= b) = max) ∩ vertici(ARⁿ₊= b) Dimostrazione. (1) Se il problema f (ARⁿ₊ = b) = max non ha soluzione, l’enunciato `e banalmente vero.

(2) Altrimenti con µ := max f (ARⁿ₊ = b) poniamo P := (ARⁿ₊ = b), R := (f Rⁿ₊= µ). Allora (f (ARⁿ₊= b) = max) = P ∩ R, per cui dobbiamo dimostrare che vertici(P ∩ R) = P ∩ R ∩ vertici(P ). Adesso usiamo il lemma 3.8.

Siax ∈ vertici(P ∩R). Dobbiamo dimostrare che x ∈ vertici(P ). Siano u, v ∈ P tali che x = u + v

2 . Per`o f u ≤ µ, f v ≤ µ, e se ad esempio f u < µ, si avrebbe f x = f u + f v

2 < µ. Perciò f u = f v = µ, cosicché u, v ∈ P ∩ R, e quindi u = v, perché x ∈ vertici(P ∩ R).

Viceversa, siax ∈ P ∩ R ∩ vertici(P ). Siano u, v ∈ P ∩ R tali che x = u + v

2 . Allorau = v perch´e x ∈ vertici(P ). Quindi x ∈ vertici(P ∩ R).

Teorema 3.25 (teorema fondamentale della programmazione lineare). Se il problemaf (ARⁿ₊ = b) = max possiede una soluzione, allora esiste anche una soluzione che `e un vertice di(ARⁿ₊= b).

Dimostrazione. Con le notazioni dell’oss. 3.23, dalla prop. 3.24 abbiamo (f (ARⁿ₊ = b) = max) ∩ vertici(ARⁿ₊ = b) = vertici(BRⁿ₊ = c).

(26)

Siccome per ipotesi l’insieme(BRⁿ₊ = c) = (f (ARⁿ₊ = b) = max) non `e vuoto, dalla prop. 3.22 segue che anchevertici(BRⁿ₊ = c) 6= ∅.

Nota 3.26. Mediante l’algoritmo di eliminazione di Gauss possiamo sempre ottenere la condizionerango(A) = m richiesta nella prop. 3.20 e nel corollario 3.21. L’insieme dei vertici di(ARⁿ₊ = b) allora `e finito e per il teorema 3.25 una soluzione del problema di massimo si trova percorrendo tutti i vertici e calcolandomax {f x | x ∈ vertici(ARⁿ₊ = b)}.

Il numero dei vertici è però molto alto gi à in problemi di modeste di- mensioni, per cui è necessario un algoritmo migliore, il metodo del simplesso, che verr à presentato nel prossimo capitolo.

Esempio 3.27. Consideriamo il problema di massimo 3x¹+ x²− x³+ 2x⁴− 2x⁵+ x⁶ = max

3x¹+ 2x²− 5x³+ 4x⁴− x⁵− x⁶ = 18 x¹− x²− x³+ 4x⁴− 6x⁵+ x⁶ = 15 che possiamo scrivere nella solita forma

f x = max Ax = b x ≥ 0 con

f := 3 1 −1 2 −2 1 A :=

3 2 −5 4 −1 −1

1 −1 −1 4 −6 1

b :=

18 15

Chiaramenterango(A) = 2. Per applicare l’idea della nota 3.26 dobbiamo considerare le

6 2

= 15 sottomatrici 2 × 2 Aα diA e calcolare x^α = A⁻¹_α b ogni volta che Aαsia invertibile. Sex^α≥ 0, calcoliamo fαx^α. Il massimo dei valori cos`ı ottenuti `e il massimo cercato. Alla pagina seguente riportiamo la tabella con i calcoli effettuati. Il valore massimo che si ottiene `e81.