Elementi di programmazione lineare [1] 8820711338, 9788820711337 [PDF]

Zitiervorschau

F erd.inando Pezzella

ELEMENTI DI PROGRAMMAZIONE LINEARE Volume Primo Per il Corso di R icerea Operativa

Liguori Editore

Tutti i diritti sono riservati. Nessuna parte di questa pubblicazione può essere tradotta, riprodotta, copiata o traSIJlessa senza l'autorizzazione scritta dell'editore. L' AIDRO (Associazione Italiana pel" i Diritti di Riproduzione delle Opere dell'Ingegno), via delle Erbe 2, 20121 Milano, potrà concedere una licenza di riproduzione a pagamento per una porzione non superiore a un decimo del presente volume. Prima edizione italiana Ottobre 1981 Liguori Editore, Srl via Posillipo 394 1 80123 Napoli Copyright © Liguori Editore, S.r.l. 1981

Pezzella, Ferdinando : Elementi di programmazione lineare : Volume l/Ferdinando Pezzella Napoli : Liguori, 1981 ISBN 88 - 207 - 11 33 - 8 Ristampe:

9 8 7 6 5 4

2003 2002 2001 2000 1999 1998

Questo volume è stato stampato in Italia dalle Officine Grafiche Liguori - Napoli su carta inalterabile, priva di acidi. a PH neutro, conforme alle norme Iso 9706 oo.

.. -. PREMESSA.

In questi appunti è raccolta la prima parte delle lezioni del Corso di Ricerca Operativa che

svolgo per gli studenti del Corso di Laurea in

Matemat ica della Facoltà di Scienze Matematiche, Fisiche e Naturali dell'Univ. della Calabria. Scopo principale, nel redi ger~ questi appunti, è stato quello di fornire una introduzione allo studio della programmazione lineare. L'argomento infa tti non è trattato in maniera generale e completa , ma vengono esposti comunque

i conce tti fondamentali che costituiscono la base di questa importante metodologia della Ricerca Operativa . Rende, dicembre, 1980.

Versione provvisoria dei primi cavitoli del testo di "ELEMENTI DI PROGRAMHAZIONE LINEARE" di Ferdinando PEZZELLA

INDICE CAPITOLO l -

ALLA

INTRODUZIO~c

PROG~~ZIONE

LINEARE

1.1 - Il problema della programmazione lineare

pag.

l

grammazione lineare

pag.

l

Esempi di problemi di programmazione lineare

pag.

1.2 - Le ipotesi che stanno alla base della pro1.3

CAPITOLO 2 -

RICHIAMI 01

ALGEB~~

LINEARE E DI ANALISI CONVESSA

2 .l - t-1atrici

pag.

6

2.2- Calcolo dell'inversa

pag.

9

2.3

Insiemi convess1

pag.

11

2.4

Intersezione di insiemi convessi. lnvolucro conves.so di un insieme

pag.

12

Punti estremi di ur insieme convesso

pag.

13

2. 6 - Iperpiani e semispazi

pag.

13

2.7

pag.

15

2.8 - Politopi e coni poliedrici

pag.

17

2.9 - Rappresentazione di politopi

pag.

19

2 . 10--- :unzioni convesse

pag.

22

2. 11- Est remi locali e globali

pag.

23

pag.

25

3.2 - Soluzioni di oase

pag.

26

3.3 - Teoremi fondamentali della programmazione lineare

pag.

31

3.4 - Risoluzione

pag.

34

4 .1 - Introduzione

pag.

36

4.2 - La forma canonica

pag.

36

4.J - La matrice utableau"

pag.

37

pag.

39

pag .

41

4.6 - L'algoritmo del simplesso

pag.

42

4.7- Convergenza del metodo del simplesso

pag.

46

4.8 - Forma matriciale del metodo del simplesso

pag.

47

4.9 - Riduzione alla forma canonica

pag.

50

4.10- Metodo del simplesso revis ionato

pag.

55

2.5

CAPITOLO 3

-~

3.1

CAPITOLO 4 -

4 . 1.

Di rezioni estreme di insiemi convessi e eoni convessi

LA PROGRAMHAZIO}è'"E L1NEAR.E Forma staodard della programmazione lineare

geo~etrica

dellaprog2mmazione lineare

tL METODO DEL SIMPLESSO

L'operazione ài "pivot" e la matrice "pivot"

4.5 - Il teorema fondamentale del

simpless~

CAPITOLO 5 - TEORIA DELLA DUALITA' ED ANALISI DELLA SENSIBILITA'

5.1- Introduzione

pag. 59

5.2

pa~.

La dualità in progr8IIIn4zione lineare

60

5.3 - Fonuulazione dt!l problema duale

pag. 61

5. 4 - Teoremi connessi con i l prob tema duale

pag. 65

5.5 - Proprietà degli scarti

pag. 68

co~lementari

5.6 - Interpretazione economica delle variabili duali 5.7-

fra la risoluzione di un problema di P.L. e la risoluzione di un sistema di equazioni lineari con variabili non negative !q~ ivalenza

5.8 - Metodo duale del simplesso 5.9

pag. 70

Analisi della

pag . 71

sensibilit~

pag. 74

5.10- Esempi numerici

CAPITOLO 6 - PROGRAMMAZIONE

LINE~:

pag. 7l

pag. 77

ALCUNI PROBLEMI DI STRUTTURA PARTICOLARE

6.1 - Formulazione del problema dei trasporti

pag . 85

6.2 - Proprietà della matrice A

pag, 89

6.3 - Determinazione di una

soluzio~e

ammissibile iniziale

91

6.4 - Metodi per la determinazione di una "buona" solu:lione aumissibile iniziale pag. 92

6.5- Ricerca di una soluzione ottima: Dantzig 6.6- Il problema dell'assegnamento

BIBLIOGRAFIA

l'algoritmo di pag. 93 pag. 96 pag. 99

-l-

CAP-1- INTRODUZIONE ALLA PROGRAMMAZIONE LINEARE. 1.1 Il problema della programmazione lineare. Programmazione lineare significa ricerca del massimo o minimo valore (se esiste) che

una funzione di più variabili, lineare in tali variabili, acqui

sta in un insieme di valori di esse definito da "vincòli" espressi colDe equa_ zioni o disequazioni lineari algebriche. Durante e immediatamente dopo la seconda guerra mondiale e fino al 1947, le ricerche sull'impiego della programmazione lineare vennero condotte Lodipendentemente in vari settoriapplicativi. Nel 1947, lo sviluppo delle tecniche di

programmazio~e

lineare permise di unificare le r i cerche in settori

apparentemente diversi, fornendo un modello di riferimento matematico ed un metodo di calrolo, il cosidet:to "algoritmo del simplesso" proposto da George B. Dantzig, per formulare ésplicitamente ques ti

problemi e calcolare effi-

cientemente le soluzioni. La scoperta di questo nuovo metodo di calcolo coinaisè anche con

la éostruzione di elaboratori elettronici digi~al~ che pre-

sto divennero strumenti indispensabili per l'applicazione delle tecniche di programmazione lineare a problemi per cui non sarebbe stato possibile effet" tuare il calcolo manualmente . Inoltre la costat a zione che un congruo numero

di problemi militari, economici o industriali può essere espresso, e sattamente o con una ragionevole approssimazione, per mezzo di sistemi matematici di disequazioni e/o equazioni lineari ha contribuito a llo svi luppo

dell~

tecniche di programmazione lineare. 1.2 - Le ipotesi che struLìO alla base della programmazione lineare. Per meglio chiarire le ipotesi che s tanno alla base di un programma lineare ci serviamo del seguente esempio di programmazione aziendale. Un processo produttivo richiede due tipi di ri sorse: una certa materia prima e mano d'opera. I prodotti sono di due tipi dive rsi, e dalla lor o vendita si ricavano profitti netti

differenti.

La quantità di materia prima e di prodòtti sono misurati in quintali; quello di mano d'opera, in ore. Per ottenere l quintale di prodotto l o del prodotto 2 le risorse sono impegnate come indicato nella tabella seguente. La terza colonna mostra l'ammontare delle ri sorse a d;sposizione, e la ter1.a riga i profitti netti (in migliaia di lire) rela tivi alla quintale dell'uno o dell'altro prodotto .

produ~one

di l

-2-

l

l

materia prima

40

lavoro

l

.

5

profitti netti

l

2

disponibilità

20

2.200

2

320

40

1201

l

l

Su?poniamo sufficientemente aderenti alla realtà le due ipotesi: l ) proporzionelità: per ottenere x

2)

quintali del prodotto l, da solo, oc 1 ccrrono 40 x quintali di materia prima e 8 x ore di lavoro; per o~ 1 1 tenere x quintali del ~adotto 2, da solo, occorrono 20 x quinta li 2 2 di ~teria prima e 2 x ore di lavoro. Il profitto netto relativo al 2 la ?roèuzione di x quintali di l è 120 x ; quello relativo al la pr~ 1 1 duzione di x quintali dt 2 è 40 x . 2 2 additività: per ottenere x quin ta li del prodotto l e x quintali del 1 2 ?roèotto 2 occorrono 40 x + 20 x quintali di_materia pri~ e 8 x + 1 2 1 + 2 x ore cii lavoro. Il profitto netto totale relativo alla produzi~ 2 ne ùi x quintali di.l e x quintali di 2 risulta 120 x +~O x ( ~ 1 gliaia di lire).

1

2

2

Si chiede: quali quantità vanno prodotte, supposto cbe la produzione tale non

poss ~

t~

superare 100 quintali, in modo che il profitto netto tota

le sia mass ime? La

funz.lonc!:

viene detta "funzione obiettivo", :x In base

al~e

ipotesi i l problema

1

pu~

e x

2

"variabili di decisione".

essere formulato come il problema

di determinare le variabili di decisione, sottoposte a vincoli linear i , che massimizzano uòa funzione lineare cioè: 120 x

aax

+

40 x

2 20 x2 < 2.200 320 8 xl + 2 x2 < 100 xl + x2
o -

x2 > o

1.3- Esempi di problemi di programmazione lineare. A) P rob le.ma della dieta.

Formare una mistura alimentare per antmal i a partire da

~

prodotti

-3-

grezzi ( orzo, avena, semi di sesamo, fa rina di arachidi). Le protei ne ed i grassi contenuti per unità nei materiali

gr~i,

insie-

me al costo unitario, sono riportati nella seguente tabella: orzo

avena

semi di se samo

12

12

40

grassi

2

6

12

costi

24

30

40

prote1.ne

'

fari na di arachidi

l

requisiti nutritivi

60

20

2

5

50

Problema: Determinare la composizione della mistura elementare, soddi sfacente le esigenze nutritive, che sia di minimo costo. + 30 x + 40 x + SO :x4 2 1 3 12 xl + 12 x2 + 40 x + 60 x > 20 43 2 xl + 6 x2 + 12 x3 + 2 x4 ~ 5 X.'> o J = l, 2 •.... 4

mio

24 x

J-

B) Problema dei trasporti. Una compagnia ha delle

fabbric~nelle

località A, B, C e dei magazzini

nelle località D, E, F. In A, B, C la compagnia ha a disposizione ri spettivamente 40, 40 , 20 unità di una certa merce, mentre io D, E, F sono richieste rispettivamente 10, 60, 30 unità di tale merce. I costi unitari di trasporto (in guente tabella:

di lire) sono riportate nella se-

migliai~

MAGAZZINI

quantità

D

E

F

lQ

60

30

costi per unità À.

40

6

8

3

B

40

2

3

l

c

20

2

5

6

Problema: Determinare un piano di trasporto dalle fàbbricbe ai .m.agazz!_ 01.

che soddisfi le richieste e che sia di minimo costo.

- xll' x12' xl3 - x2l, x22' x23 x)l' x32' x33

unità di merce che da A va rispettivamente a .D, Il

Il

.. Il

"

..

"

..

~-"

B

"

"

"

"

" c

Il

Il

Il

"

"

F,

.

Il

-4-

40 xll + xl2 + xl3 x21 x22 + x23 .. 40 x31 + x32 + x 33 - 20

vincoli di disponibilità

21 + x31 • lO • 60 x12 + x22 ·~ xl3 + x23 + x 33 - 30

vincoli di richieste

...

xll +

1

x .. > l,J

o

i. j • l, 2, 3

C) Un problema di investiment o. Una compagnia finanziaria vuole investire L. 100.000.000.000 in titoli, mutui, obbligazioni, libretti di risparmio e beni immobili.

I

tassi di

interesse annuo relativi alle cinque scelte di investimento, sono r1 portati nella seguente tabella. tassi di interesse annuo % titoli

lO

mutui

8

obbligazioni

6

libretti di risparmio

5

beni iliiDObili

9

A

causa del rischio implicato, l'amministrazione decide le seguenti

norme operative: l'investimento nei titoli . non deve superare la somma totale investita nelle obbligazioni, libretti di risparmio e beni immobili. -l'investimento in mutui e beni immobili deve essere almeno uguale a quello relativo alle obbligazioni. !'investimento in

~tui

non deve essere superiore a quello dei librett i

di risparmio. Problema: Determinare il modo ottimo di investire nell'ipotesi che i tassi di interesse correnti restino stabili

per un certo periodo

di tempo. Indicando con x , x , x , x , x i capi t ali rispet tivamente investiti 2 3 4 1 5 in titoli, mutui. obbligazioni, libretti di risparmio e beni iv.mobili il problema può essere così fo rmulato:

-5-

max xl

~

O.lx + 0.08x + 0.06x + 0.0Sx + 0 . 09x 1 2 4 3 5 x3 + x4 + xS

x2 + xS ~ x3 x2 ~ x4 x + x

1

x

>o

j-

2

+

x j

3

+

x

~l,

4

+ x

5 2 . ... 5

= 100.000.000.000

-6-

2 - RICHIAMI DI ALGEBRA LINEARE E DI ANALISI CONVESSA

2. t - Matrici Def.2.l - Data una matrice A m x n e una matrice B n x p si definisce moltiplicazione fra la matrice A e B la nuova matrice C m x p con n

c. . • 1)

per i • l, ... m e j • l, ... p

1: a. k bkJ.

k•l

1

in altre parole l'elemento c .. di C è ricavato dal prodotto 1J

scalare della i-sima riga di A per l'j-sima colonna di B. Es:

-l

A•

-2

o -l

c-

Aa-

-2

o Si noti che se A è una matrice m x n e Buna matrice p x q

51

ha:

l) AB è definito solo se n • p. AB è allora una matrice m x q. 2) BA è definito solo se q • m. BA è una matrice p x n. 3) Se m • n - p - q allora

AB e RA non sono necessariamente

uguali. Def.2.2 - Una matrice quadrata n x n, si dice matrice identità 10 se ha tutti

gli elementi della diagonale principale uguali ad l e tutti . sli altri uguali a zero. Def.2.3 - Una .atrice n x n ai dice triangolare superiore se tutti gli ele.enti al di sotto della diagonale sono nulli. Viceversa per la .atrice triangolare inferiore. Si ricordi che per le matrici trasposte valgono i seguenti risultati:

l) (AT)T • A 2) Se A e B hanno uguali dimensioni (A + B)T • AT + BT 3) Se AB è definito allora (AB)T • BTAT Inoltre data una matrice A, m x n, si può ottenere una sua sottomatrice scegliendo alcune righe e/o colonne di A. Una matrice A può essere paE tizionata in aottomatrici. Si consideri per esempio:

-7-

A•

all

8

12

al3

al4

a21

a22

a23

8

8

31

8

a33

a34

8

41

a42

8

8

dove A

11

32

•

811

8

8

8

[

21

cioè

44 813

12

8

a41

8

8

A12 •

22

31

8

A21 •

43

24

32 A22

42]

-[

23

~1424 8

a33

8

8

8

43

La matrice A si dice partiziooata nelle

l

34 44]

quat~ro

sottomatrici

~l'

A , A , A • 22 12 21

Ora supponiamo di avere due matrici A e B partiziooate come segue: nl A=

ql

n2

F~~ • -A~2-] ml A22 m2 l l

B•

l l

A21

q2 8 12

[~11 T - l l

8 21

l l l

8

q3 l

l ~q]

-~-

22

l

l

8 23

pl

Pz

Allora AB è definito da:

AB• Per essere definito AB deve essere: e Operazioni elementari su matrici Data una matrice A, m x o, sono operazioni elementari su righe: l) Scambiare la riga i con la riga j. 2) Moltiplicare la riga i per

uno

scalare non nullo.

3) Sostituire alla riga i, la riga i più k volte la riga J· Operazioni elementari riga corrispondono a premo ltipl icare A per una opportuna matrice. Operazioni elementari colonna corrispondono a postmol tiplicare A per un'opportuna matrice. Esempio: Sia 2 A•

l

l

10

-1

2

l

8

l

-1

2

2

Di videodo per 2 l a prima

rig~,

aggiungendo la n.ga l ottenuta alla

-8-

seconda riga e sottraendo la riga l ottenuta alla terza riga si ha:

[~

1/2

1/ 2

5/Z

3/2

-3/2

3/2

:3]

-3

Moltiplicando la riga 2 per 2/5, moltiplicando la nuova riga per 3/2 e aggiungendo alla terza riga si ha:

[~

1/2

1/2

l

3/5

o

24/10

Dividendo la riga 3 per 24/10, si ba:

[~

1/2

1/2

l

3/5

o

l

2~:5 J

Risoluzione di sistemi di equazioni lineari con operazioni elementari di matrici

(~todo

Si ricordi

che Ax •

di riduzione· di. Gauss

)

bse e solo se A'x • b'dove (A', b') è ottenuto da

(A, b) mediante an numero finito di operazioni elementari righe. E.sea~pio:

x2 +

~-

lO

-~ + ~ +

x3 -

8

~ + ~-

2

~· ~·

(A,b) •

[-~

l

l

2

l

-l

2

1:]

(A' ,b ') •

[

~

1/2

1/2

5

l

3/5

26/5

o

l

2

J

5 ~ + 1/~ + l/~ •

%2 + 3/5x3 • 26/5 %3 • 2

Si oòti cbe A' ~ una aatrice triangolare superiore per cui per sosti ta.ziooe all 'illdietro si ba:

x3 - 2

~- 4

xl

- 2

Inveraa di una aatrice Sia A wa aatric.e .quadrata o.xnr.se esiste una matrice quadrata B n

li:

n tale che:

AB • I e BA • I allora B ~detta inversa d i A e ei i ndica con A- 1 . L'inYer•a ae eeiste

~unica.

Se A ~a l'inversa,

A~

det ta non singolare.

- Coodizioue di e•istenza dell'inversa. Qoa aatrice A, ns n, ammette

l ' inv~r • a s~ ~

$Ol o 5e le rithe sono

-9-

linearmente indipendenti c , equivalentemente, le colonne sono linearmen te indipendenti. 2. 2- Calcolo dell'inve rsa.

L' inversa di una matrice può essere ot tenuta mediant e un numero finito di operazioni elementari righe. Cioè mediante operazioni elementar i righe è poss ibi le ridurre le matri ce (A , I) alla matrice (I , A- 1 ), il che è equivalente a premoltiplicare per çl. Inoltre se (A , B) è ridotta a (I , F) mediante operazioni elementari ri -l

ghe, allora F • A B. Esempio:

(A-l esiste ) l

A

·[-: :] 2

-l

( A, I) •

[~l

l

l

l

o

2

l

o

l

-l

2

o

o

~]

Si divide per due la prima riga sommandola alla seconda

riga~

sottra

endola alla terza si ha:

1/2 l/2

o

5/ 2

1/2 3/2

-3 / 2

3/2

-1 /2

o

l/2

l

~]

Si moltiplica per 2/ 5 la seconda riga.poi la si moltiplica per -1/2 e li

somma alla prima , la si moltiplica per 3/ 2 e ai aggiunge alla ter%a. -1/5 l /5 2! 5 001 [

:

o

3/5

1/ 5

2/5

12/ 5

-I / 5

3/ 5

Moltiplicando la ter%a riga per 5/ 12 si ba:

[~

o

o

5/i2

-3 / 12

l

o

3/ 12

o

l

-1/12

3/12 3/12

Cio! -3

3 3

-1 / 12] -3/ 12 5/ 12

-lO-l.

Esempio: (A

A

. [~

nop esiste)

~l

l -l

2

,-

è facile verificare che mediante operazioni elementari su righe Sl o t

tiene:

u

o

l

1/3

1/3

l

l

2/3

-l/3

o

o

-S/3

1/3

n

Si noti che in questo caso l'inversa non esiste poichè

~

3 •

~l+ ~

2

Si ricordino inoltre i seguenti risultati: . l are. a l l ora AT e, non s1ngo . l are, (AT) -l , (A- l) T l . Se A è noh s1ngo

2. Se A e 8 sono matr1c1 n x n non singolari, allora AB è non singolare e (AB)-l • 8- lA-l 3. Una matrice triangolare (superiore o inferiore) con elementi non nul li sulla diagonale ammette l'inversa. 4. Se A è partizionata

A

·[-> - -~ -] l

nl

l

n2

come~egue,

e D è non singolare

allora A è non singolare, e

A-1-[~- •_::o=l-J O

l

D-l

- Rango di una matrice Si_co~ideri _ una

matLice A, m x n.

Rango riga della matrice è il massimo numero di righe linearmente indi pendenti. Rango colonna della matrice è il nass1mo numero di colonne linearmente indipendenti. Si può mostrare che il rango riga è uguale al rango colonna e quindi il rango di una matrice è il massimo numero di righe o colonne l inear mente indipendenti rango (A)

~

minimo (m, n)

Se rango (A) • minimo (m, n), A si dice a rango pieno .

-11-

convess~.

2.3- Insiemi Siano ~l' ~

2

due punti di S ~ Rn (spazio euclideo n-dimensionale).

t~ : ~ = ).~ 1

Def.2 .4 ·- L'insieme L= .

~

.,n

~n ~

passante per

Es: In R3 , posto~

c

e

(l-i.)~ 2 },

..-

ÀE

R, si definisce

.!.!!..-r(

__) 2. (Y, y, z), ~n base alla definizion~ si ha: ~l

w= À""' l + (1-À)w.?,

~

y"' Ày

(l-À)y ,

+

1

2

z • Àz 1 ..- (l- À)z. 2

che poste nella fonna w-"-'

y -

----2- c ~ wl

-

z

y2

2.2

-~

z - z2 l

y - y2 l

rappre sentano le equazioni della retta passante per (x ,y ,z ) 1

+

Se À>O l 'insieme L

{~

c

semiretta avente origine

:

~

1

1

À~l +

•

in~~·

..

Per 0< À < l l' ins ieme dei punti costituirà il segmento che congiunge

~l

~ .

2

ed

2

Def.2 . 5 - Il punto~"' À~l + (l-À)~ , O < À ~ l, si chiama comb{nazione convessa di ~l e ~ 2 ._

Se O < À < l il punto x convessa in senso Def .2.6 - Un insieme S

(0>"~6ttr-0. Quindi

-6

(l)

> -2

(2)

o

(3)

l

(4)

>

-

> >

e

o.

y À>

devono essere vere

:~) ~ (~)

1 - 2d

1

2

Oe d ~

~

2 O e d

O 1

-

d

2

~

O

(A

~ ~

Q)

1 ~ O e d 2 ~ O allora d 1 ~ 2d 2 implica d 1 > d2

Quindi(:~)

l una direzione di S se e eolo se:

.

(:~) (:) d

o

> 2-

ve H~ Def.2.14- Due vettori, ~l

e

~l

~

2

sono detti distinti o non equivalenti se

non può essere rappresentato come multiplo positivo di

Def.2.15 - Una

direzione~

l·

~

0

2

~ .

di un insieme si dice combinazione positiva

di due distinte direzioni

~l

e

~

2 dell'insieme

se si puè

esprimere come:

Def.2.16

Una direzione estrema di un insieme convesso è una direzione dell'insieme che non può essere rappresentata come ne positiva di due distinte

cf,

f

combinazi~ ~

direzioni dell'insieme.

j

Def.2.17- Un cono convesso C è un insieme convessò che gode dell'ulteriore proprietà che ~~~e

C e

YÀ >O

Si noti che l'origine (À

~O)

! E C i l raggio { Àx

À

è

~letamente

allora Àx

e C

appartiene al cono conve sso e che per ogni

>O} appartiepe a C, inoltre un cono convesso

caratterizzato dalle sue di rezioni es t reme.

r"'

1 '~" \

J

-17-

Origine

Or igine

Fig. 6 - Alcuni esempi di coni convessi

::. :ol(~~r: i:2 c:n(~~~v:•:o{:::~t::~i:•::o~d::l: 1 d:r::~o::~:t:~de da Fig. 1 cono convesso

~

• IO. 11

{~] Fig. 7 - Caratterizzazioné di coni convessi in termini di direzioni e.st~ Def. 2 .18 · Dato un insieme di vettori .!l ...• , ~ noi chiamiamo cono convesso ( 0 v- o senerato da questi vettori il cono rappresent ato dalle zioni positive di .! .... , 1

c•

). . a . J

J

Àj ~ O

~cioè:

·per _ j • l. . .. k }

2. 8 -~litofÌ e coni 2ol~ici. Def . 2 . 19- L '..in~rs~zione di un.. num.e~c _finil:o di politofo convesso.

co~ina

.

-.

se~spaz~

c

h.

•

~usL

~

h.

J

e c lam&to ;-

Gli iperpiani che danno luogo ai semispazi

tb(, (c,?O Col.o.vQ~:;.~

sono chiamati iperpiani generanti del politopo convesso. Def.2.2o- 1Jn politopo ~nvesso rum vuoto e limitato si dice poliedr~.. Poichè un semispazio è un insieme convesso, ricordando che ogni intersezione di insiemi convessi è un insieme convesso , s i ba che il politopo è un insieme çonvesso.

rPvf. ~

J

._

1 .....

-18Inoltre essendo un semispazio chiuso rappresentato da una diseguaglianza del tipo

a

i

x< b.

ove

l.

a

-

i

• (a. , a. ..• a. ) l. 1 l 2 lO

il politopo è rappresencato dal!'i~sieme (~: A~~~} dove A è una erice m x n la cui i-sima riga è a

1

e b un vettore m x l .

Poichè un'equazione può essere scritta con due disequazioni,

un

può essere rappresentato da un numero tinito di disequazioni e/o

polibdpo equazi~

ni lineari. Es~mpio:

x < 4 2• x < 3 xl 2'1. 2 xl

(l)

o o

( 4)

-2 x

l

+

>

xl x2

....

L ' intersczione

(2)

{3) 1 S)

5 semispazi chiusi

~

mostrata

10

fig . 8.

Fig. 8 -Pdliedro. Gli iperpiani corrispondenti alla 2a, 3

3

'

4a' 5

3

disequazione si dicono \

facce del poliedro. Una speciale classe di insiemi poliedrici è il cono poliedrico . (()'r-

r..:;

~t.Jtt('-.

aç

'?~

spazi chiusi, i cui iperpiani passano per l 'oTigine.

t

In altre parole :.C è un cono poliedrico se può essere rappresentato come: { .! : A !. ~ O } dove A è una matrice m x n.

Osservazione: Il cono ·poliedrico ·è convesso

-19-

Fig. 9 - Cono convesso non poliedrico

Fig. 10 - Cono convesso poliedrico

2. 9 - Rappresentazione di poli topi.

Un politopo convess o può

ess~re

rappresentato in modo alterna tivo mediante

i punti estremi e le direzioni estreme.

•

1n particolare ogni punto èi un poliedro può essere rappre sentato c,,roe comb i

f~cmato

dall ' Lntersezione di c inque

(vedi fig.ll) avente come punti estremi

2

3

convessa di

ze

~

~

estr~i

cioè:

a sua volta può essere

~\ rappresenta~come

comb inazione line re convessa

di ~ e .!z cioè:

o Sosti tuendo si ba:

5

può essere rappresentato come combinazione lineare

x ~

semi spaz~

~l' ~ • ~ , ~ e ~ .

Fig. 11 - Rappresentazione in termini di punti Notiamo che il punto

ot:;.

__)

nazioné convessa dei suoi punti estremi. Consideriamo un poli edro

~

(

< u < l

-zoove e

O
.!3

+

u~2

-21-

Teo. 2.3 - (Teorema della rappresentazione nel caso generale) Sia S •{ x : Ax • b, x > O} un politopo convesso non vuoto.

- - --

-

-

Allora l ' insieme dei punti estremi è non vuoto ed è costituito

1

~ , ~

da un numero fi nito di puEJi

2 ...... ~. Inoltre l'insieme

delle direzioni estreme è vuoto se e solo se $ è limitato. Se S non è limitato, allor a l'insieme delle direzioni estreme è non vuoto ed è costituito da un numero finito di vettori

~

1 .... ~ 1 .

In~ltre ~E

S se e solo se può essere espresso come combinazione

convessa di

~ ,~

1 2 •..• ~

e come combinazione non_negativa di

~

1 . .. ~ 1 ,

cioè:

.. k.t

x

t

>..

x . + l: lJ.d. J -J j•l J-J

j•l k

r

• l

À.

j•l

J

À. >

o

J lJ. > J

j • 1,2, .•.. k

-

j

-o

1,2, •.• . t

Dim. Vedi [l]. Esempio: Si conside r i il politopo . convesso f ormato dalle seguenti diseguaglianze: -3x. + x l

- x - x

l

1

< -2

2+ x


~l,

se-f(~)

.! E S, si ha: 2

è convessa.

E' importante notare che la convessità o la concavità di uca funzione è

{ definita solamente quando il suo dominio è

un insieme convesso.

l

l

l

••

.,

.,. .,

..

Fig. 14 - Esempi di funzioni convesse e c oncave: (a) funzion e convessa. (b) funzione concava, (c) nè convessa nè concava.

-23-

f(~)

Teo.2.4 - Se una fUnzione n

vesso S s R allora f o.~ +

(l -

è lineare ed è definita su un insieme con Y~

1 e .!,2 E S

(

À) ~2) - Àf(~l) + (l - À) f (~2) •

il che dimostra che ogni funzione lineare che è

l

defini~a

insieme convesso è una funzione convessa e concava

su un

contemyor~

\

neamente. Dim. 2.11-

E' lasciata al lettore.

Estremi locali e globali.

-· ( ù

_.,çs,

Def. 2. 2l- f(,!) si dice avere un minimo ·(massimo) globale in x E S se Y.! E

r .,6.~

~

f(~) ~ f(~) (

o

f(x) ~ f(!o)).

Def. 2. 2t,- f(_!) si dice avere un minimo (massimo) locale in x e S &e -o

'(

e.,c.Jt

esiste un intorno T di x tale che f(x) > f(x ) (f(x) < f(x )) -o - -o - -o Y~ES

(') T

La parola "estremi" è usata per indicare sia i massimi che i minimi. Si parlerà di minimi e massimi "forti" se le diseguaglianze sono valide in senso stretto. Teo.2.5 - Se f(~) è una funzione convessa definita su un insieme convesso ( S chiuso e limitato. allora un minimo locale di minimo globale di

f(~).

Inoltre se questo

mi~mo

f(~)

è anche un

si ottiene in __)

più di un punto. l'insieme dei punti di minimo è convesso.

Dim.

~ UR

Sia

minimo locale di f(,!), esiste cioè un intor-

no di xo .l-x - -o x l O

f(.!o) è un mini:oo globale punto per cui si ott iéne il minimo

·M, . ~ -

global~.

,.,. f\

1\ub.t..

f

-24-

Poichè y

o

è un punto di S che è un insieme convesso allora

sarà possibile trovare

~ f (x ) •

-o

f ( (l - À) x

-o

+ Àv )

-'"'()

Il che significa che il minimo è ottenuto per una zione convessa per cui

f(~)

di~

e

Zo

combin~

e cioè che l'insieme dei punti

è minimo è un insieme convesso.

-25-

CAP. 3 - LA PROGRAMMAZIONE LINEARE.

3.1 -Forma standard della programmazione lineare. Un problema di programmazione lineare (P.L .) è caratterizzato da una funzione ooiettivo lineare nelle incognit e ' e . Ba vincoli espressi da uguaglianze e/o di~guagli a nze Jineeri .

La forma di questi vincoli pu0 differire da un problema è mostrato in

se~ui c o ,

ogni

pro~ramma

all ' altr~

ma, come

linea re pu è ess e re trasf ormato nella

setuente forma standa rd; • z (min) d+ c x + c x ....... c x 2 2 0 0 1 1 con i vincoli a x + a x ... . . . . .. a nxn • b 12 2 1 11 1 1

• b

2

- b ID

ove b., c., d,a .. sono costanti r e ali e note, _ XJ·. variabili reali e z una l J lJ . funzione reale detta funzione obiett i vo. l coefficienti c , c 2 ,.~.cn sono dett i coefficienti di costo. In forma matriciale il problema in forma standar d diventa : T d +c x • z (mio)

con

1

vincoli

ove x è un vettore colonna a n dimensioni c è un

~ettore

colonna a n dimen-

sioni, A è una matrice mxn e b è un vet t ore colonna ad m dimensioni. S: noti

inoltre che nei problemi di programmazione lineare in forma standard

m < n e per ipo tesi rango (A,b): rango(A) • m cioè s i fa riferimento a sistemi consisten ti e non ridondanti. Poichè in generale un problema di programmazione lineare non è in forma standard per ottenere la forma standa rd si opera come segue:

":f.!'r

~

;)

~2er

trasforma r e un probl~ di massimizzazione i n un p~obl~ma di m.inimizzaz ione bas t a camb iare il segno alla f unzione ob i ettivo.

'

~ov~

~ '"(

~{~J .S " .f-

- 26-

b) Se l'insieme dei "vincoli è cardtterizzato da disequazioni lineari del tipo all xl + al2x2 + ••... + a 1pxp ~ b 1 a2lxl +

8

22x2 + ••••• + a 2pxp $ b 2

a mlxl + amlx2 + xl~

o

o

••••

x2 ~ o ...

o

+ a

•l't

x $ b mp P m

2:0

p

esso può essere espresso allxl

+

a2lxl +

al2x2+ 8

22x2+

•

o

••••

......

+ a ~

a

~ome

x

+ x

• b

x

+ x

-

1p p

2p p

p+ l

p+2

x

p+ 1

l

b..,

~o

introducendo delle nuove variabili non negative x

...

x

~o

p+m

. dette variabili ausi:iarie

~l

( variabili slack) che tramutanò le disequazioni in equazioni. o)

Se le disequazioni lineari sono del tipo anxl.:. + ai2x2 + ••••••• + a.l.p x p

~b.

i . • l, .... m

l.

queste sono equivalenti a 4

ilxl + ai2x2+ •••••••• aipxp- xp+i ·bi

i . l, .... m.

i•l, .... m ancll'esse dette variabili ausiliarie. ( ~L(f-p!~J ...JI / ;à> Ogni variabile libera xj viene sostituita con la differenza di due varia' · bili non negative ponendo cioè: eon

x. • x! J

J

x'! J

o :ve

x! J

~O ,

x'~~ O

J

3.2 - Soluzioni di base. 3.1 -

Ogni vettore x

che soddisfa Ax • b si dice soluzione del si-

stema di equazioni lineari. Una so l uz~i~o.~o.un.ue;:......~x.......su.i_~ c~ ammi ~sibi l e

...----

-----=

se soddis!a anche

x~

O.

-27-

, Si consideri il sistema Ax • b e x - ~ O ove A è una mat rice mxn

dtVt·Je~(

e t lllXl. Supponiamo che i l rango (A ,_!:) .. rango (A) "' m. Riordi-

niamo le colonne di A in modo che A ~[B:N)ove B è una matrice invertibi le~ ed

N

_:;.[:J r~IJ;;

La so lu>iooe

r

è una matrice mx(n-m), il sistema può es-

B~ + N~ •

sere seri t.to come

r'YV'.r' ~·(

b ed emmett:e

n-m

a)

se ~B) Q x è una soluzione di base ammissibile;

B è detta matrice di base ed N matrice non di base;

~

,

'.

)

soluzioni.

detta soluzione di base;

4

\ç

N_J

~ ~;e..;~O allora x è detta soluzione di base non degenere.

s

Se almeno una delle componenti d i x è uguale a zero la soluzio-B ---...-ne di base si c ice- d-e-gener-e.

Si noti che per un probl ema di programmazione lineare lO forma standard con n variabili ed m equazioni si possono avere al più n! m! (n- m)! soluzioni di base corrispondenti a tutte le possibili scelte di m fra n colonne.

' s~?cl

Def. 3.-3 - Una soluzione A~

c

J

non di base si chiama soluzione di base. Def. 3. k - Una s o luzione di base x si dice amnissibile se verifi ca

-x ) -O. f_.

Def. 3.5- Una soluzione di base x si dice degenere se a lmeno una delle va-

s.;)f &-~ C!U-r>

7

de~. Def. 4 .l

Un problema in forma standard si dice 1n forma canonica rispetto a lla sequenza di base S se: .. I

(_

ò.J\"r;f\'

m

o

8) c

•

Y) b

~Q

-s

~

Le variabili x

, ... .. . xs sono dette variabili di m

sl

\

base~

I l significato delle condizioni a, 8, y, è il seguente.

:=-

La condizione a afferma che il sistema di equazione Ax = h è stato riso lto _!1spetto alle variabili è i base x 5

B afferma

La condizione

tiVi a-I-n!-va-riabi h

dy

--------

~.

x m •

- - - - - -..

che nella funzione obiettivo i coefficien ti rela..aSe-sono ru:ti_L1.~-- - - -

-- -

i termini noti delle equazioni sono .non negativi .

·-

~--------

E' i mportante notare che in corrispondenza ad un problema in forma esiste uta soluzione ammissibile detta soluzione di base data da : x5 •

].

= b. o

x.

=

z

'"' d

J

i e { l ,2, .. .. . m}

].

j EG

4.3 La matrice tableau. Un problema di programmazione lineare s1 presenta come già si è detto, nella forma standard:

d +

cTx .. z Ax

(mi n)

•h

x >o Compiliamo la seguente tabella:

b

A

Questa tAbell a i n detta g l i o v1ene r appre sentata dal la matrice :

.,/

t

-38-

o

o

-d

cl

bl

..

...

all

..

k

J

c.

...

alj

..

J

i

. bi .. .

ai l

. . a 1).. ..

b

l)h

.. .

~l

..

m

b

a

..

H •

m

ml

~j &

mj

.. ..

n

. ..

~ 4

c

D

lk · · · al n

aik • · • a.1n ~k'" ~n

amk ••• a

mn

La matrice H detta matrice tableau, rappresenta simbolicamente

le equazioni del problema di programmazione lineare: così ad e~ sempio la prima riga della matrice M si legge ~

)

l Esempio:

z- d • c x + •••••••• +c x 1 1 nn l . .ma e a r1ga 1 come

bi • ailxl + ...•.•••••. +

3

inxn

Il pro gruma lineare in forma standard

- 120 x

l

- 40 x2

40 xl + 20 x2+ :x) 8 xl +

xl +

2 x2 :x

(mi n)

i

• 2.200 • 320

+ :x4 +

2

• 100

xs

può essere formalmente rappresentato mediante la

segu~nte

matri-

ce tableao

o

-120

-40

2200

40

20

320

8

2

100

l

l

o

o

o

l

o

o o

l

o o

o

l

Si noti che in questo caso la forma standard è anche forma canonica ed in corrispondenza vi è una soluzione ammissibile di base associata alla sequenza di base S = { 3,4,5 1 data da x • o x. ,. 100 x, • 320 x2 - o ) l

..

4.4 L'operazione di: . "pivot, e la matrice

Il

•

PlVOtw

L'operazione fondamen tale dell'algoritmo del simplesso è l'operazione ~O)

pivot. L'operazione di_ pivot in posizione (h ,k)(h,k do

~k

di~

è definita quan-

f O e consiste nelle ope razioni seguenti: a) si

divi~ono

b)

sommano opportuni multipli

s1

tutti gli elementi della riga h per ahk' della riga h a tutte le

righe in modo tale che tutti gli elementi della colonna k, ad eccezione di quello in posizione (h , k), diventino nulli. L'operazione di pivot in posizione (h , k) ha quindi il seguent e significato: si risolve l 'equazione h rispetto nare

~

=

lO

e si usa tale equazi one per elimi-

dalle altre equazioni e dalla funzione obiettivo . per~omodità

Ponendo a.

a~

b.

1.

i

di notazione a

= 1,2 , . .. m la

• - d, a.= c., j • 1,2 , ... n, 00

OJ

J

ma .. rice H, dopo aver fatto l'operazione di pivot

in posizione (h,k) diventa:

k

j (l) i

a!.

o

h

~j

l

l.J

M =

dove

~J·

a . j • O, l. .... n

• _J1]_

~k

a!. •a . . lJ lJ

a l. k.a.h].

Si noti che per J • k e Si

i • O, l. ... p; e i -f. h; j • O, l. ... n

~k 1

r

h si ha aik

=

O e per j "' k e· i"' h si ha ~k =l.

~uò facilmente verificare che la ma trice ti(l) ottenuta dalla matrice ~

con una operazione di pivot in posizione (h,k) è legata alla matrice M dalla relazione

1n cui la matrice Q non è singolare, di dimensioni (m+l) x(m+l), sce dalla matrice identità I

m+ 1

soto nella colonna h e d è data da:

differì-

-40-

o

l

o

l

o.... ~/~k

l

o

l. . .. ·-~ k /~k . . . . o •

Q '"' h

o

O· .

. . 1/ éihk

.o

m

o

O·

·-Qmk,~k.

. l

h

m

ol

La matrice Q si chiama matrice pivot corrispondente all'operazione di pivot in posizione (h,k) e il vettore colonna in cui essa differisce dalla matrice identità corrisponde

alla posizione della riga in cui appare

l'elemento di pivot nella matrice M. Le matrici pivot appartengono alla classe delle mat rici chiamate matrici elementari.

~l~.-, C(

e~~.) f

( De t.

L

Una matrice elementare è una matrice quadrata non singolare che

4.2

è una matrice identità eccetto che per una colonna.

Parimenti si può. verificare che la

.,

~trice _M~~) attenuta da M dopo o opera-

zioni di pivot è legata dalla M dalla relazione M(t) .. Q(t)M dove la matrice non singolare Q(t) è, 1n eenerale, del dpo

dove

O è un vettore colonna di m zeri R(t) è un vettore riga ad m componenti

P (t) è una matrice mxm Si noti che la matrice Q(t) è ottenuta dalla moltiplicazione di t matrici pivot. Ìkf. 4 . 3

Due prograDID.i 'lineAri si dicono equi valenti quando gli insiemi delle soluzioni ammissibili coincidono ed in corrispondenza di ogni soluzione ammis sibile i valori

i"!ti

assu~ t i

dalle fun?.:on) obiet-

tivo coincidono. Teorema

4. l

Sia M(t) una matrice ottenuta da

M

dopo una serie di t operaz i, -

ni di pivot. (t\ I problemi di ? . !.... definiti da M e da ,.1 sono equivalenti

Dim.:

L'operazione di pivot consiste tn una ser 1e di oppor t une nazioni lineari

s~

co~i­

r ighe e quind i lo spaz 1o delle soluzioni non

• I no l tre per ogo1. so l uz1one . · l· l e x s ara~ z ( t ) ( x ). •z ( X J c amb 1a. Gmml· SS lO

infatti:

cioè: (t) T

~(t) l ed eguagliando membro a membro le matrici - d(t) c

= -

d

partiz~nate

si ha :

R(t)b

+

'

(t)T

e sostituendo in z(t)(~) • d(t)+c(t)Tx si ha

z(t)(~) • ·~~(t)~+ (~( t)T+~(t)A)~ 4.5

a

d+cTx + ~(t)(A~- ~)-d+~T~ •z (~).

Il teorema fondamentale del simplesso.

l

Teorema 4.2 Si consideri un programma lineare 1n forrua canontca rispetto gli indici di base S. Vale in tale caso una delle seguenti alternati ve.

s

a) se c. > O Y. rj S, allora la soluzione di base x J -

J

associata

alla forma canonica è ottima; b) se esiste un indice k

f S tale che

~
O, allora si può fare un'operazione pivot su un opportuno elemento della colonna k trasformando il problema in uno equivalente pure in forma canonica in cui, nella soluzione base associata, si ha z Dim. a)

S'

5

S

z .

Questa parte del teorema cos tituisce l a cosidetta prova di ottimalità. ln corrispondenza della forma canonica conside rata 5 si ha la z "' d . lligliorare i l valore de lla fun z ione obie ttivo significa

trovar~

un'altra

soluz~one

di base ammissi bile per

la quale il valore di z diminuisce . Dato che il passaggio da una soluzione base ammissibile alla successiva pu0 essere effettuato solo rendendo basica una variabile non basica (cioè facendole assumere, nell'i potesi posta di non negativit à, un valore positi vo diverso da

zer~)

e

s0stituendola ad una delle variabi li basi che già presenti , ri ducendo ques ta a zero (

cio~

non basica. affi nchè il numero

delle variabili basiche sia lo stesso) si deduce che se tutti i roeffic..ienti di costo sono poslt t vi o nul i si ha:

l

(

'-

zs ' =d+ c.x.>

J J-

cioè non è possibile trovare un'altra soluzione di base per cui la funzione obiettivo assume un val o re inferiore. b)

In corrispondenza ad una nuova soluzione di base ammissibile tale che

~

sia di base si ha:

'\ l

-d + \~

z è

~vidcn t~

che se varia

~

da zero ad un valore positivo senza

cambi are il valore delle altre

-'

vari~bili

non di base che è ugua-

le a zero allora il valore di : diminuisce. Mettendo in evidenza

o

solo le variabili non nulle per ciascuna variabile basica preesistente si ha: :
= ~ se e solo se si noti che si ha 4.6

~

O e / o bh

::

o.

L'algoritmo del simplesso.

Per applicare l'algoritmo del simplesso occorre che i l problema di P . L. s ia io forma canonica il che garantisce di ave r e una soluzione di bas e ammissibile iniziale . La procedura di risoluziooecoo l ' algoritmo del simpless o è la seguente :

-43-

l)

si esamina il segno dei coefficienti c., Y. E G J

J

la) se c. > O Y. E G allora la Si)luzione di base ammissibile ,f è J

J -

Una soluzione ottima ed il procedimento si arresta; .lb) se esiste un qualche j E G tale che c. < O, si sceglie tra questi J

l'indice a cui corrisponde un c. con il massimo valore assoluto, J

sia ck(~), e si procede al passo 2) 2)

si esamini il segno dei coefficienti aik' l 5

24) se aik

~

li~tata

O per l S i

~

i~

m.

m allora non esiste una soluzione ottiaa

ed il procedimento si arresta.

2b) se esiste qualche i tale che a.k > O ai procede al passo 3) l

3)

•

si eseguino i rapporti bi/aik solo in corrisfcnden%a degli aik>O e si dete~ina l'indice cui corrisponde il mini~ di Loli rapporti, sia h

l e stess e variabili di base e ssendo il numero di possibi li i nsiemi di

P~r i l teorema 4. 4 si ott erre bbero

indici di base al più(:) . due matrici

ug\~li rna

poichè per ipot esi d ' O. o X.

J

J

J

-49-

Esempio

Min z z .. xl

+ x2 -

4x

3

xl

+

x2 + 2x3

xl

+

x 2

x3 ~ 2

-xl

+

x2 +

x

,

xl, x2

3

x3

~

9

S

4

~

o

introducendo x ,x , x 4

5

6

come variabili ausiliarie s i ba la se-

guente forma standard Mio z

.. 9 2 4

xl, x2 . x3, x4, xs · x6 >o che è anche in forma canonica r ispe tto agli indici di base mi danno la base iniziale B • [~ ·~s·~ ]=l

S = {4 , S, 6} che

3

e la seguente tabella

o

l

9

l

l

2

2

l

l

-1

4

r-1

l

0

o

o

o

l

o

o

o o

l

o

o

l

applicando il metodo del simplesso si ha l'operazione di pivot

=

in a33 - l (B

16

f-)

1

KD

6

o

4

-1

[24 '~5 '~3])

5

o

o

o

-l

o

l

o -2

2

o

l

l

l

l

o o

o

l

4

e po1.

17

o

1/3

l -1/3

6

13/3

La soluzione o ttima è data da x•

l

2

-

l 3

4

o o x2*

a

o

l

o

2

o

- 2/3

2

o 1/3 o o

l

l

2/3

l 1/3

o

1/3

o x3* - 13/3 z*• - 17

(

_;:- )

\.__-.---

-

la base ottima B~': è data dalle colonne

_!

1

• .!s,

_!J

o l

cioè:

-2/3] l

o 1/3 4. 9 Riduzione alla• forma canonica.

Per applicare il metodo del simplesso è richiesta una soluzione ammissibile di base disponibile a partire da una forma canonica di partenza. Per determinare una soluzione ammissibile di base, quando essa non è disponibile, vi sono dei metodi che si basano sull'uso delle variabili artificiali. Definizione 4.3 Una variabile artificiale è una

vari~bi~e_ che vi~e

aggiunta

in uno o più vincoli del ·problema in forma standard al fine di ottenere una soluzione di base amDUssibile di partenza.

Si noti che nel problema di P.L., cosi come formulato all'origine, compaiono delle disequazioni, la sua strutturazione in forma standard prevede l'intraduzione in esse di variabili

slack, le quali per loro natura sono

caratterizzate dall'avere coefficiente unitario nella disequazione relativa e

coeffici~nte

slack, pur concettualmente

nullo altrove. Tali variabili

diverse dalle variabili artificiali, sono formalmente simili a queste, e pertanto non è necessario introdurre variabili artificiali nelle equazioni in cui compaiono variabili

slack.

ta una soluzione di base ammissibile

Inoltre si può dire che introducendo le variabili artificiali si

,---

iniziale, come richiesto,

~ottenu­

tr~sforman-

do però il problema P.L . originale in un altro non necessariamente colle-

gato in alcun modo al primo. Di conseguenza, utilizzare questa soluzione di base ammissibile iniziale per risolvere il problema P . L. dato

non

è possibile, a meno che non si riesca a rendere il nuovo problema P.L. ot-

tenuto artificialmente equivalente al primo. Se infatti i due sono equivalenti,

risolvere t'uno o l'altro porta agli stessi risultati.

Se tra tutte le soluzioni di base ammissibili del s i stema

aum~n tato

con

le variabili artificiali, ve ne è almeno una per la quale le variabili artificiali assumono valore nullo essa,

oltr~

che

esser~

una soluzione del

sistema aumentato è anche soluzione del sistema originario ed è

~uindi

uti-

lizzabile come soluzione di base ammQssibile iniziale di quest'ultimo. Per risolvere il suddetto problema è

neces s~ rio

dis por re dei

~roceèim~nt i

che permettano di conoscere se i l problema d"i P. L. i n forma standard atmlet-

,( -51-

te ~ no soluzioni ammissibili e, nel primo caso, di calcolare anche una soluzione èi base amuUssibile in modo da poter applicare il metodo del simplesso. Uno dei tal i procedimenti è costituito dal metodo delle due fasi. Si consideri il nuovo problema di P.L. ottenuto introducendo al più m variabili artificiali a. l

min P m

~1v

_,

p

-l:

a.l

i•l n

~"'

l:

' poichè a. l

-

a .. x. + a. • b.

j•l

lJ J

x. >

o

a. >

l

< m e x. J

J

b. l < l

l

l < i < m

l

l

o

-

.. o

l ~ j ~n è una soluzione di base aumis-

sibilc è possibile risolverl.o con l'algoritmo del simplesso. La risoluzione del suddetto problema costituisce la prima fase del metodo del simplesso e la funzione p si chiama

anch~

forma di inammissibilità.

Teorema 4.ì Data la funzione obiettivo da minimizzare m

P -

.I a.

i=l

l

allora il nuovo problema di progracmazione lineare ottenuto introducendo le variabili artificiali ammette semp re una soluzione ottima. Inoltre detto p* obiettivo si ha:

p~-;

il valo re ottimo della funzione

=O -se e solo se il problema di P.L. in for-

ma standard ammette soluzioni ammissibili. Dimostrazione: Il nuovo problema di P.L. ammette sempre soluzione ottima

10

quanto la sua regione di ammissibilità non è vuota ( esiste almeno una soluzione di base amnUssibile) ed inoltre

p~

O essendo

somma di variabili noc negative e quindi la funzione obi ettivo non è illimitata inferiormente. Se il problema di P.L. io forma standard ammette soluzioni ammissibili allo ra esistono soluzioni ammissibili al nuovo problema di P.L. con le variabili artificiali ponendo

~.~o l

i • l,2, ... m e cioè esistono soluzioni amr

missibili per cui p: O e quindi P* Se d'altra

e

~ioè

parte ~ *

~O

a

O.

ciò è possi bile so lo se a. • O i =1,2, .. m l

se il problema di P . L. i n forma standard ammette soluzio-

ni ammissibi li infatti in tal c aso una

s~l~zio ne

di base ammis-

-52-

sibile del nuovo P.L. lo è anche per il P.L. in forma standdrà. lo base al te orema applicando l'algoritmo del simplesso a l nuovo problema di P.L. con le variabili artificiali si possono verificare solo i seguenti casi: a)

o''

>

o

in tal caso il problema di P.L. in forma standard ha ragione di ammissibilità vuota cioè non ammet te soluzioni ammissibili;

b)

ç:':

•

o

in tal caso si possono verificare le seguenti possibilità

bl) tutte le variabili artificiali sono uscitè dalla base e quindi sono uguali a zero. In tal caso s i prende la soluzione di base ammissibi le fi nale della prima fase del metodo per ess ere utilizza-

ta come soluzione di base ammissibile i nizia le cui appli care l'algoritmo del simplesso per l ' e secuzione della seconda fase. b2) alcune variabili artificiali sono rimaste nella base ma sono ugualmente nulle in quanto ci troviamo in un caso degenere. In ta l cas o si fanno uscire dalla base tali variabili arc ifici al i mediante opportune operazioni di "pivot 11 in modo da ricondurci alla possibilità bl). Se ciò non è possibile significa che il p roblema di P . L. in forma standard è ridondante c ioè un'equazione è combinazione lineare delle altre.

Si noti che prima di procedere alla seconda fase del metodo del simplesso occorrerà: l) eliminare la forma di inammis s ibilità 2) eliminare dal sistema di equaz ion i tutte le variabili di base i

~ui

coefficienti di costo nella tabella ottima della pri-

ma fase sono positivi. In ta l modo ci si assi cura che che variabile artificiale rimane nell'insieme delle

s~

qual-

v3~tabili

di base (caso degenere ) il suo valore non ;:>otrà mat ess•!rc di·· verso da zero , come r ichiesto , durante l a todo.

seco~òa

fasè èel

~e ­

-53-

Esempio.

Sia dato il seguente problema di P.L. llllnZ

xl + x2

">

l

xl + x 2 ... 2 xl

-

x2

xl

-

x2 >-l O, x

')

xl

'

l

>

2-

o

La forma standard sarà: minz

z "'

=

l 2 l

+

x

6

x 1 ~ O , x 2 ~ O , x3 ~ O ,

= l

x 4 ~ O,

x5 ~ O , x6 ~ O

Il problema non è in forma canonica per cui per iniziare l a prima fase del metodo del simplesso occorre introdurre in corrispondenza della prima equazione una variabile x ; alle altre equazio7 ni esistono già delle variabili che godono della proprietà della basicità. In questo caso la forma di inammissibilità è p

= x7

ed occorre trovare quella particolare soluzione base ammissibile per il nuovo problema di P . L. che annulli il valore della variabile artificiale . Per applicare la prima fase del metodo del simplesso si noti che l)

= x7

l - xl- x2+ :x3 e s i arriva all a seguente tabella: x,

xs

x

l

o

o

o

o

-l

o

o

o

o

o

l

-l

o

o o o

l

o

l

o o o

l

l

o o

o

o

l

xl

x2

x

-l

-l

-l

o

o

l

2

CDl

l

l

-l

-1

l

l

l

3

...

6

x7

o o o

-54c l e non in a =l 11 31 si ha il vantaggio di fa r e usci.re alla prima i t erazione la va-

effettuando l ' ope r azi one di pivot in a

riabile x

dalla base e s i ottiene la seguente tabella:

7

x., 4

o o

o

o

ù

o

o

l

o o

-l

o

o

o

o

o

l

-l

o

o

l

o

l

l

·o o

-l

-2

l

l

-l

0

-l

o o

o o

o

l

l

l

l

o o o l

2

o

La soluzi one di ba se ammiss i bile t r ovata è ot t ima , ed èSsendo a~ssibili.

il problema originari o ammette soluzioni di base

~:·:

Eli-

minando la colonna r elativa alla variabile artificiale e la forma di inammissibilità s i no t a che la funzione obi et t i vo non è ottima per cui si e ff et tua l'ope r azione di pivot in a 42

l

o

o

-l

o

o

l

o

l

-i

o

l

o o o

o o o

CD

l

o o

-! o

o

o

l

o

l

- j

o

l

!

2 l

D

la cui s o luz ione base ammi ssibile non è ottima per

2 e si ottiene:

CUl

Sl

effet-

tua l' ope r a zione di pivot su a23 .,. l e si ottiene:

3/2

l 2

3/2

x4

x_

xl

x2

X~

o

o

o

o

l

l

o

o

o

o

o o

l

l

o

-l o

o o

o

l

o

l~

l

.>

.)

xé

o

cui corrisponde la soluzione di base ammissibile

...

x:·1

• i

u

x2

. 3/2 x;·- l

•.. ,

x·;...

=

o

>:

x.)

..

2

x6

et ~ D

tti:a:

o z*=

-3!2

O

-555.10

}~todo

del simplesso revisionato.

Dall'illustrazione del metodo del simplesso si osserva che durante ogni iterazione solo una piccola parte delle

inform~zioni

contenute nella ta-

bella M(t) sono necessarie per applicare l'algoritmo e quindi non occorre calcolare tutta la matrice M(t). Si noti infatti che per effettuare il passo a) del metodo

del simplesso

occorre conoscere solo la riga zero di M(t), Se risulta cj ~ O per j E G allora l'algoritmo si arresta e basta calcolare la colonna zero per determinare il valore della soluzione ottima, altrimenti per effettuare il passo 2) occorre calcolare solo la colonna k-ma. Se si verifica il caso 2a) allora l'algoritmo si arresta, se invece si verifica i l caso 2b) allora occorre calcolare la colonna zero io modo da individuare la riga di pivot. Da ciò deriva che può risultare vantaggioso, sia rispetto al tempo di calcolo che

all'occupazione di memoria, evitare di calcolarsi, come fa il

metodo del simplesso, tutti i dati contenuti nella tabella M(t). Per il teorema 4.2 si ha : M(t) .. Q(t)M ove M è la matrice table~ iniziale e Q(t) è ot~eouta dal prodotto di t matrici "pivot 11 cioè: (t)

Q

=Q t . Qt- l .. ..... Ql

che è -facile da calcolarsi essendo le mat:rici "pivot .. matrici elementari. Dal punto di vista del tempo di calcolo, quelle che incidono maggiormente sono le operazioni di divisione e moltiplicazione che supporremo avere temr po di calcolo dello stesso ordine di grandezza. Def.. 4 .4~

Densità di una matrice, a, è il rapporto f ra il numero di elementi non nulli in essa presenti ed il numero totale di elementi.

Per una generica iterazione si avrà: a) metodo del simplesso ricordando la sequenza di operazioni che definisce una operazione di "pivot 11 si avranno in totale - sostituzione della riga Eh con Eh l

~k

; (n-m+l) divisioni

- prodotto -aikEh per tutte le m rimanen t i operazioni Ei ; m(n - m+l) moltiplicazioni - sosti tuzione di ciascuna Ei con Ei addizioni

= Ei

- aikEh

m{n - m)

-56-

Quindi trascurando le addizioni si ha: '~s = (n -

m+ l)( : tll + l)

Si noti che la generica iterazione considerata

è . successiva

ad un numero consistente di iterazioni precedenti per cui anche se all'inizio N contiene elementi nulli al crescere di cioè

t

a~

l,

N te&de a ''riempirsi''.

Dal punto di vista dello spazio di memoria ad ogni iterazione occorre memorizzare le tabelle di dimensioni (m+ l)(n- m+l)(giacchè non occorre memorizzare la matrice identità). b) Metodo del simplesso revisionato. ln questo caso si ragiona sulla tabella H di partenza e si fa l'ipotesi che la distribuzione di elementi nulli nella matrice N originaria sia uniforme, cioè la stessa densità a si ha per le singole colonne di N. Si ha; calcolo della riga O di M(t) richiede a m( n-m) prodotti Il Il a m2 colonna k di M(t) Il Il a m2 - colon.na O di M(t) Il Il (m+l) 2 calcolo di Q(t) Il totale delle operazioni sarà: 'lR • (m+l)

2

+ am(n+m)

Per lo spazio di memoria occorre memorizzare la matrice Q(t)di dimensioni {m+l)m (sennn si tien conto della prima coloana ) . Nel confronto fra i due metodi si ha che conviene la revisione del simplesso; rispetto al

total~

delle operazioni, se

'JR < '~s

da cui risulta che essa è sempre conveniente per

n~ ~3m 2 + 2m.

Rispetto all'occupazione di memori a si ha che conviene la revisione del simplesso se (m+l)m
2m- l.

E' interessante notare che nella generalità dei c asi con cre t i di P.L. si ba molto spess o n / m > 4

e a< Ot S

ed in particolare per problemi P.L. di grosse dimensi oni ( m

>

risulta abbastanza comune una dens ità media in t o rno al 5- lo: .

..

100)

-5 7-

Esempio:

Sia dato il seguente problema di P.L. z =-3x

mi n

-

l

Sx

2 +

xl

+

x2 3x x.

2x

+

1 '>

J

o

j

x

-s

o -3 l

6

o

18

3

02

.

x4

...

..

l . ....

6

xs

18

s

X~

3

)

o

o

o

l

o

o o

l

o o

o

l

o

4

M•

2

= 4

x3

si effettua l 'operazione di pivot in a

22

• l, la matrice pivot

sarà

Ql =

l

o

5

o

o o o

l

o

o o

l

o o

-2

l

la nuova matrice M(l ) sarà:

30 -3 4

l

6

o

o

0

o

o

s.

o

l

si effettua l'operazione di pi vot sarà:

l

o

l

~~ Q2=

o

(l

o

o

. -'--- -

t

quindi

o

l

o

-1/3

o

1/3

o

- -·- --

1n

a

31

= 3 , la mat rice pivot

-58-

Q(2) - Q

o

o

l

= o o

x Q

2

l

l

l

3

2/3 -1/ 3

o l o o -'213 l/3

da cui l

o. l l+

o o

3

l

o

-3

-5

2/3

-v

4

l

o

l

o

6

o

18

3

o o o

-2/3 1/3

da cui la soluzione ottima è

2

o

o

o

36

o

o

2

o

l

o

6

o

o

l

2

x* • 2 l

x* .. 6 x* • 2 2

3

z*• - 36.

L

\

-

---

l)

o o 3

x~'t=x'~

4

5

l

O

-59-

CAP. 5 - l TEORIA DELLA DUALITA ' ED 5.1

~~ALISI

DELLA SENSIBILI TA '

Introduzione .

La teoria della dualità p r oblemi di

gioca un ruclo cent rale nella riso luzione dei

p~ogrammazione

svilu~perà

lineare. In questo capitolo si

la teo ria della dualità a partire dal seguente problema di programmazione (P)

f(~)

min

Q

g(~) ~

n

~E X

n

ove f: R

~

e

R

C R

-. 1

g(~) "' [ g (~) ,

.. • .

sm(x) ) -

n m una funzione daR · a R , e X. '

un insieme non vuot o . D' ora in pòi chiameremo (P) problema primale .

.

I vincoli dE l problema (P) sor.o di due tipi:

v~coli

('JJJ

espliciti g (x) O (pena l ità per _x che vio la il v incolo)

- l

l

-

b) se x soddisfa l 'i-mo vincolo si h a ch e r,.( x ) l

che y. g, l

l

(x)~ -

O (premi o per

~

-

~O

e ci ò implica

ch e soddisfa il vincolo) .

Applicand o gli stess i ragiooamen t i si vede subi t o che se g(!) ) ve es::e r e

~ ~

Q f se

~ (_~)=()

a llo r a v è non vi ncol ato 1.n seroo.

Q a llora de-

-60-

(RL(~))

Per il problema

valgono le seguenti proprietà di immediata di-

lllOStrazione P ) 1

X.2 S

·ove S è l'insieme &rnDUssibile del problema (P) e X l'insieme ammissible del problema (RL(l)); Y~

doè la

fun~ione

obiettivo

E S

d~l

RL(~) è

problema

minore o uguale

alla funzione obiettivo del problema P. Il valore ottimo del problema (RL(l)) varierà al variare di lo si indicherà con

~)Q

problema RL(z) t~(y) ~

ove

z• è

~(y)

(funzione

duale~

y

per cui

In base alla proprietà P del 2

si ha la seguente condizione (dualità debole).

z*

il minimo della funzione obiettivo del problema primale.

Quindi v(z.) t qualunque sia .z._~ _Q , è una stima e.er difettQ_di z*" e tale stima è

(D)

~to

"• = max

più accurata v(z)

q~~o

maggiaxe

=

conduce al problema:

max ( min

-y~O-

1. ~.Q. (D)

è_ y~.Ciò

! EX

viene chiamato il problema duale del pr oblema primale (r). Chiaramente v*\< z* t cioè il valore ottimo del duale è minore o uguale del valore ottimo del primalet e in generale v*< z*; la

differenza 6. = z•- .-si chiama gap di dualità. 5.2

La dualità in programmazione lineare.

Si consideri il seguente problema di programmazione lineare max

c

T

x

/

• X Se pon1amo

=

Rn_={ +

n

~ E R

1 : ~ ~ .Q_ } , f (~) =-c x

allora il problema di programmazione lineare consid e rato è un caso particolare del problema (P).

-61-

.:; . -c..!. -l-)' A:!. -)-t~

'

--- ~-

In questo caso introducendo la funzio~lagrangiana si ha T T / T T T < L(~,y) • - ~ ~ + ~ (~ - ~) • - y ~ + (~ A - ~ )~ y r_~J

dove La

è il vettore dei moltiplicatori.

funzione duale sarà definita come:

.-

• min

T

(y

A

affinchè abbia senso la massimizzazione della funzione duale rispetto a T T y ~O dovrà essere (y A- c)~ O infatti in tal caso, poichè ~~Q,

-- - -

-- -

-

il minimo si otterrà per x • O e

altrimenti in caso contrario se esiste ùn indice j tale che

T

(I

A

T

c ).. .

Si può quindi per il problema

~progra1tlllazione

lineare (l) definire

il suo problema duale come: ma x

v

{-

.. max

y~Q

ò

l.

T

r

~

T

yA - c

T

~Q

•

n altri termini:

.--

- mio

T ~y T Ar~~

J

/

.l~Q

S.3

Formulazione del problema duale.

Ad cgni

problem~

di P.L. può essere associato un altro problema di P.L.

r. iamato problema duale. oa~o

un

pro~lem~

T

max c x

di ?.L. , che

chia~remo ~rimale

nella

f~rma:

-62-

allora il problema

dua~e

è de fini to,in base alle consideraz~oni svolte

nei paragrafi 5.1 e 5.2, da : T

min~y

T A

~el G

1. ~~

c3so Ln cui tutti i vincoli del primate sono del tipo $ il problema

duale si dice simmetrico. le relazioni fra il primale e duale

si~tric0

sono:

l) il duale ha una variabile per ogni vincolo presente nel problema primale. 2)

Il

d~ale

--

ha tanti vincoli quante sono le incçgnite del problema --...

primate. 3)

Il duale di un problema di massimo è un problema di minimo e viceversa.

4) I coefficienti della funzione obiet civo del problema primale sono

i termini noti del duale e i termini noti delle originali disuguaglianze sono i coefficienti della funzione obiettivo del duale. 5) I coefficienti di una singola variabile nei vinco li originali diven-

tana i coefficienti di una singola espressione de i vincoli del duale. 6) Il senso delle disuguaglianze è invertito, la condiz ione di non negatività delle variabili resta. Il problema duale di ogni P. L. può essere trovato ripo rtandos i alla forma del problema primale di P.L. sopra i ndicata ed applicando le relazioni fra il primale e duale

si~trico.

-63-

s~

nel prob lema primale appaionovincoli di uguaglianza cioè: T

max c x Ax = b

-x

•

~o

~-

esso può essere riscritto nella fo rma equiva lente T max c x Ax < b -Ax < -b

al quale possono esse r e applicate le relazioni del duale simmetrico considerando la matrice(.:À·) e il vettore delle variabili dua li parti-

(~·)

z.ionato come

da cui

v ~o

e ponendo Y.... • v - u bT aun _y_ T

Ay_

si ha:

~~

Se il p robl ema

primal~

contiene variabili non vinco late

del tipo T

max c x A~

.S. b

si può por r e x = t - w ma x

(~ :

Qe w > O e

si avrà:

_E_T )(.~·)

(A: -

A) (

òa .:ui ponendo y_ min

con~~

~TY....

-~·)~ ~

=(.~.)

t

s1 ha:

>

o

.....

') o

~n

segno cioè

-04-

Poìchè le precedenti situazioni possono verificarsi contemporaneamente nello stesso problema di P. L. le regole che permettono di 'passare direttamente dal problema primale a quello duale sono :

Prob1ema prima le

Problema duale

ma x

mi n

' o

vincolo

vari ab i le ~ o vincolo

vincolo variabile~

O

vincolo

variab i le~

O

variabile

matrice A (m x n)

matrice AT (n x m)

termini noti b

termini noti c

coefficienti di costo c

coefficienti di costo b

Tabel l a 5.1 Corrispondenze primali- duali Risulta evidente che le corrispondenze fissate in tabella 5.1 si invertono se risultano invertite le caratteristiche del primale ( o del duale) . Se ad esempio il primale si basa su una minimizzazione il duale e un problema di massimizzazione; se i vincoli del primale sono del tipo > le variabili del duale sono del tipo

le Esempio:

sono del tipo

2

2 ;

se le variabili del prima-

i vincoli del duale sono del tipo

~

.

Si consideri il seguente programma lineare max 8x + 3x2 1

xl - 6x2 Sx x

1 + 7x~ 1 x

2

~

2

=

-4

~

O

~

O

il suo duale sarà mio 2y

2yl - 4y 2 ( 8 -6y + 7y ~ 3 l 2 yl

~

o

y2 ~o

l

- 4y

2

sottoposto ai vincoli:

..

- 655. 4 Teoremi connessi con i l problema duale . Teorema 5. l Il duale de l problema duale è i l problema prima le

•

Dimostrazione: Si consideri il seguente prob l ema p rimale T max c x Ax.


b

Q

il suo duale sar à lnl.O

_bi'1.. T Al.

:t.

> c >

o

che si può anche scrivere come:

max - bTY T

-Az.~-;;.

il

c~~

duale sarà

x' > O e ponendo

~· ~

x si ha

T

max c x Ax < b

.!>Q

cioè il problema primale Teorema 5.2 Si consideri una coppia di problemi di P. L. l ' uno duale dell ' alt r o entrambi dotati di soluzioni ammissibili x ' e z(~' )

x'

allora si ha :

< 'II(I_')

ove z è la funzione obiettivo del problema primale (max) e v la funzione obie ttivo del problema duale ( min ) . "'. . . _tmos:raztone: Essenao

~'

. . e y ' so l uz~Onl

l' amro~. ss1. b.l~

s ara~ z '

= ~T~ '

bT ' .

' v=-~

e

~oltiplicando ambo i membri del l a relazi one ~· < ~ per y ' T si ha. ri cordando che t'T> O, r ' T(A~ ') 2 z' I~ · Analogamente molti. T , ?llcando A 'i.

~

s.

per !

, T(

con .!

,T

In base alla relazione trovat a si

O)

2:_ _

ha~ .

. .

s t na

. , T T)y'

(~

A _

~~

,T

.f. ·

-66-

•

z(x ' )•c Tx'=x' Tc o --

il suo duale sarà: T

"'È.Z T

Ay_5:_!:;_ z~Q

in corrispondenza della base ottima B la t abella canonica del metodo del simplesso sarà:

- eT B- l b -B B-l b

-

OT

-

I

T

T

-l

~-!::.aB

-t

B

N

N

I coefficienti di costo in corri spondenza dell'ot t imo saranno

c*

T

"'-T

T -1 B A. -B

• c• - c -

Per il criterio di ottimalità la base è ottima solo s e

lr

*T

T

-l

-c • -c - c B (i! B-l)A _:: f:.T

A > O cioè

~

Dalla tabella si nota che il valore octimo della funzione obiettivo è (~~B -l).Q Se noi definiamo 4vT • ~BT8 -l a .11 ora a bb tamo · · mo d o che TA 2 ~ T o 1n equivalente ATz

1

2~ e ~Tl ·rT~ ={f:.!B- )~ che

z

è uguale o ttimo del

problema primate. Per la sufficienza ~t è una soluzione ottima ~

del problema ~. In generale si ricordi che ognt problema di P.L. si può ricondurre alla forma standard e che i duali di problemi P . L. equivalenti sono equivalenti.

Corollario:

a~s­

Se una coppia di P.L. primali e duali ammettono soluzioni

sibili. allora entr~i hanno soluzioni ammissibili ottime, ed all'ottimo i valori assunti dalle funzioni obiettivo sono uguali. Dimostrazione: E' immediata applicando il teorema 5 . 2 e 5.6. deg~~

5.5 Proprietà Teorema 5.7

scarti complementari.

Condizione neces sar ia e sufficiente affinchè due soluzioni x

·~

e y

che risulti:

y_* T

~)

(È_ -

xitT (ATy* -

~*)

"' O

{l )

• O

(2)

Dimost r azione: (Necessarietà) Si consideri la differenz a z ~ - cTx essa ?uò 1

essere riscritta come 1 I~

-

T

c x +

~T(b -

- -

I

T

~

- I

T

A~ •

1

I

T

(~

-

~) +

o -x -

1. .:_

2

~*,

-::. .' : )

o

u >

è una soluzi one ammissibile del sistema allora

x:': è soluzione ot t ima del priCJale e Viceversa se -

t~ma

~* è

o

x_*T è la soluzione ottima del duale.

una soluzione ottima del primate e y* è una soluzione ot-

d e l d ua l e e v''= .~ b - Ax·'· _ ~, .

...

~ ~ =A

T'i..".·. S. a 11 ora (

., ..

...

.~ ,-::_" ... ) e'

~ ,:t_",~ ..

am-

missibile per il sistema. Quindi ogni algoritmo

~tto

a risolvere un s istema di equazioni l ineari si-

multanee con variabili non negative può essere usato per risolvere un problema di P.L. Viceversa risolvendo la prima fase del metodo del simplesso si ottiene la risoluzione del sistema di equa zioni lineari simultanee. \ 5 . 8 ~etodo duale del simplessp. ~el

metodo del simplesso

espO§ tJLC':.~ l

capitoLo...-4-s-i--p.ar.t;;e- da una sol uzione·

di base ammissib ile e si cerca di imporre l ' o ttimali tà (ammissibilità del duale), il metodo duale del simplesso parte da una so luz i one di base non ammissibile del primale ma d1 base ammissibile per i l duale ed evolve verso la ricerca di una soluzione di base ammis sib ile ottima. Io ~tre _par ole il metodo del simplesso parte da una soluzione di base ammiasibile ma non ottima ( È.

~Q,

_s

~Q

) pe r arrivare ad una spluzione di base ammissibile

-72-

ottima (~*~O, ~*~Q) mentre il metodo duale del simplesso parte àa una soluzione di base ottima ma non ammissibile (~~Q, ~~Q) per arrivare ad una soluzione di base ottima e ammissibile (~*~O,~*~ Q). Il metodo duale del simplesso si usa quando: a)

la determinazione di una soluzione ammissibile di base richiede l'introduzione di un gran numero di variabili artificiali;

-

b) quando alcuni

p~rametri

del modello subiscono delle modifiche

tali che la soluzione ottima non è più 8mnUssibile.

Dato un problema di P.L. in forma canonica debole rispetto alla sequenza di base S tale cioè che:

> o --

c

ai. :b . < l

( condizione di ottimalità )

o

( non ammissibilità )

cioè è inizialmente disponibile una soluzione di base ammissibile per il duale, allora il metodo duale del simplesso evolve secondo i seguenti pas si: l)

si esamina i l segno dei coefficienti b., l < i < m

-

l

la) se b. > l-

~

o, l < i < m, allora

-

è una soluzione anunissibi le

~

ed ottima.

-

lb) Se esiste qualche i, l < i < m, tale che b. < O, si determi-

-

].

= max{lb.l l:b. ù Yj il soluzioni 8mnUssibili infatti

~

• bh

pro~lema

- .~

3 1

sempre minore di zero. ~.

2b) Se qualche coefficiente

~

di p i vot scegliendo

J l&

-ahk

non ammette

ah ;X; risulta J

·'

< O si determina la colonna k c mi n { _j_ : Y. : ah .... O } j -~j J J

Questa scelta del pivot mantiene la condizione di ah· tà cioè c~ a c. - c. :!!..L > O Y. j S da cui .: . > J

-

]

k

]

~k-

o in modo equivalente c. > c ] -

sceglie k in modo che

-

C}
o} j:a*. < O} e a =~n{ -.:::.!. posto dunque a • max{ ~ a*.' · ej 2 1 e) J e) J eJ a

o

o}

b~

{-

mi. n l

--.qih l

affiucbè la soluzione rimanga ammissibile deve risultare

6 < 6 l-

6


o e quindi y > oh -

~ -~ qoh

k ES* la perturbazione y distrugge l a f orma canoni ca della tabella

ottima.

-77-

Introduzione di una nuova variabilP.. L'aggiunta di una variabile x è accompagnata dall'aggiunta alla man+ 1 trice A di una colonna a e alla riga dei ~oef ficienti di costo di c . -n+ 1 n+ 1 La soluzione di base ottima resta una soluzione di base ammissibile ma può non essere ottima. Ricordando che

:!:T

~

T -1 T. = ~BB A ~ ~ ,per la n+l-sima compo-

nente si ha T -l cB B 41+ a l -

a) se c•'~'

n+ l

-c

n+ l

~

O la soluzione originale ottima è

ancora la soluzione ottima del problema modificato dall'aggiunta della variabile. b)

Se c* < O occorrerà introdurre nella base la nuova variabile n+ 1 x mediante il metodo del simplesso. n+ 1

Introduzione di un ulteriore vinco l o. L'introduzione di un

ult~riore

vincolo riduce in gene rale la regione am-

missibile . Detta cioè S la regione ammissibile del problema di P.L. ed S' la regione ammissibile che si ottiene introducendo il nuovo vincolo, sarà 1n generale:

S'~

S

Pertanto il valore della nuova s~luzione ot tima non può essere migliore del precedente. Se allora la soluzione ottima trovata soddisfa anche ·il nuovo vincolo essa sarà una soluzione ottima anche del nuovo probl ema . Se ciò non avviene occorrerà espandere la m~trice W~ con i coefficienti corrispondenti al vincolo aggiunto, ripristinare la prima canonica ed eventualmente applicare i l metodo duale del simp,lesso. 5.loEsempi numerici. a) Si risolvino i seguenti problemi di P . L. duali tra loro. max 120 x 40 x

8 x

1 1 l

+

40x

+ 20x

2 2

~

2. 200

y3 ~ 40

+

x , x 1 2

y 3 ~ 120

~

O

Introducendo le variabili ausili ari e e le variabili artificiali i problemi divengono in forma canoni ca:

-78-

mi" -120x 1 - 40x2 40x + 20x + x3 1 2 8x

1

+

xl +

2x

2200

x2

40y • 8y2+ YJ - y4 l

..

320

20yl + 2y2+ YJ

+x =

100

yl, y2' y3' y4,

+x4

2

2200y l + 320y 2 + 100y2

!IUO

5

= 120

+ y6

- Ys

+ y "'

7

40

Y7 ~o

Ys· Y6'

x , x , x , x , x ";li O 4 1 2 3 5

Risolvendo con il melodo del simplesso

ottengono le seguenti

SL

tabelle

Problema primale

o M

1-120

-40

2200

40

20

= 320

0

2

l

l

100

Problema dual.e

o o o o o o l o M:a o o l l

4800

o

-lO

o

600

@

l -5

l/4

o 1/8

o o

60

o o o

3/4

o o

l

5400

o

o

60

o

l

25

l

o

15

o

o -3/40

40

-2

o

220J

320

100

120

40

8

l

-l

o

40

@)

2

l

o

-l

o

- 40

o

-4

l

l

~

l)

4400

o o

':'

40 2

l

100

-lO

0 1/10

-l

l

l

o o o o

-2

l

o

o

l

o

3

o l/10 o l/10 -l 2 l -2

1/20

o

-1/20 o 1/20

o

o

1/10 -1/2 o k~ 5400 l

o

15

25

60

-25

lO

o

-1/4

-1/4

1/2

1/4

-1/2

-1/40

ed all'ottimo risulta:

CD

-lO

l

l

da cui si nota che

x* ..

15

o o

-60

-160

10

o

1/4

o

1/4 l

zi:=

v*

10

o

l

l

l

o

5 . 400

o

o

o

l

3/40 1/40 -i/W -1/40 1/10

-79-

Dalla tabella

ottima si nota che i valori delle variabili ausiliarie x ,x ,x

3

4 5

uguagliano i coefficienti di costo relativi alle variabili y ,y ,y nel 1 2 3 duale, mentre i coefficienti di costo relativi alle variabili x ,x del 1 2 primale eguagliano i valori delle ausiliarie y4 ,y del duale. 5

Vi è

cio~

una corrispondenza biunivoca fra le variabili del primale e del

duale:

x4

.-.y2

xs-Y3 xl -Y 4 x

2

-

Y

5

e,più 1n generale, se indichiamo con x., i • l .... n le variabili del pri1

male, con x . j•l ... m le variabili ausiliarie del primale, con y., j•l ... m n+J J le variabili del duale e con ym+i , i=l ... n, le variabili ausilarie del duale, vale la corrispondenza: xm+ i - y i

ovvero alla i -ma una vari ab i le di scarto de,l prima le

i=l . .. m

corrisponde la i-ma variabile del duale e viceversa.

x.--y J

.

m+J

j=l ... n

ovvero alla i-ma variabile del primale corrisponde la j -ma variabile di scarto del duale e viceversa.

Ne viene di conseguenza che il problema duale può essere risolto tramite il principale e viceversa, infatti sarà

.~

c·: J

E' inoltre immediato verificare che all'ottimo vale il teorema dello scarto complementare io quanto

.. o

( x'"

l'

~d

x*2 )

...

(

Y4 ) "' o y* 5

inoltre il corollario del teorema dello scarto complementare:

- 8.)-

x* >

~y~~ •

x;

o.:::;>y) • o

O

l 4 x~ > o.::;> y~ .. o .~

>

.t.

>o~~ ·o y* > 0-=0> x* • O

yf

2

4

b) Si consideti il seguente problema di P.L. max z • 8x x 2x 7x

1 1 1 1

+

9x

+

x

+

3x

+ 6x

x ,x 2 ,x 1 3

2 2 2 2

+

4x

+

2x

+

4x

3 3

2

2

2 3 2x 2 8 3

+

3

~O

il suo duale sarà min

~

• 2y

1

+ 3y

2

8y

+

3

yl + 2y2 + 7y3 ~ 8 yl + 3y2 + 6y3 ~ 9 2yl + 4y2 + 2y3 ~ 4 yl t y2 t y3 ~ o risolvendo il problema primale con il metodo del simplesso si avrà:

M(2) ..

o

-8

-9

-4

o

o

o

2

l

l

l

o

3

2

0

2 4

o

l

o o

8

7

6

2

o

o

l

9

-2

o

8

o

3

o

l

1/3

o

2/3

l -1/3

l

2/3

l

4/3

o 1/3 o

2KD

o

-6

o

-2

o

5/3 2/3

o l

~31/3

o

o

4

7/9

O

o

4/3

l -1/9 -1 / 9

'l

5/9 2/3

o

l

8/3

o

~,

l

o

-2

o -2/3

7/9 -2 / 9 1/ 3

dalla quale è possibile legger dirett amente la s oluzione ot t ima

81-

del duale . T ( ' ,,..,.,

1 :; (0 9 8 )(l l l -) =(0 9 8)(1 -l/9 -1/9)•(0 5/3 2/3)

.)

:f:' = Y'i u '1 ' Y)

o o

o o

3 2 6 7

7/9 - 2/9 1/3

-2/3

che sostituite nel problema duale danno luogo a y2 • O , y; • O

yg ..

4

~)•

Ricordando che v (y'') • 'L'' T È = (O 5/3 2/3) ( z(~()

=

31/) cioè

v((':)

c) Pe r meglio comprendere le relazioni esistenti f r a un problema ed un suo duale risolviamo in parallelo i seguenti problemi duali

fra loro ma x z= 8x +2lx 1

2x

mi n " • Yl"*'Y2

2

+ 3x

l

~

8

~

2yl + y2

2 xl + 7x2~ l

1

3yl +7y2 ~ 21

introducendo le variabili ausiliarie si ha: mi n

-z

-8x

2x

1

+

3x

l

- 2lx

min v

2

=l

-2y

+ x 4-l

-3y

2 + x3

xl + 7x 2 xl, x2' x3, x4

l l

yl + y2 y2 + y3

-

.. - 8

+ >' 4= - 21

- 7y2

o

yl, >'z• y3' y4 >

~o

Risolvendo il primale con il metodo del simplesso ed il duale con il metodo duale del simplesso si hanno.le seguenti tabelle:

M=

o

8

-21

l

2

3

l

l

3

-s

0 o

M(l)= 4/7 11/7 O 1/ì

1/7 l

o o l

o

o

l

o

1/7

l

l

o

o

-8

-2

-l

l

o

o

l

-21 -3

M(l)=

e

•

4/7

o

o

1/7

-5 f-11/7

o

l

-1/7

l

o

-1/7

-3

3

l -3/7

o

M=

o

-- ------------------3

3/7

-6 2-

53/11

o

o

35/!1 18 / 11 1

4/11

l

o

7/11

7/11

o

l

-1 /11

da cui

z r.

•*

~

~

-5 3/11

o

35/11 l

- 3/11 J- 2) 2/11 =

:1..8/11

*T

53 l 11

o Gi ll

o

~

=

o

l

l

1/ll

-7 /11 1/11 3/11-2/ll

(4/11, 7/11, O, O) e

T

y*- ( 35/11,18/11, o, 0). Inoltre si possono notare da questo esempio le seguent i ulteric r i diffe-

-..'\0~

,-

renze fra il metodo del simplesso e il metodo duale del simpless o : l) nelmetodo del simplesso , si sceglie prima la variabile che en-

~

de~mmina

tra nella base e si

poi la variabile che deve uscire

dalla base. L'operazione di pivot si effettua su un element o positivo. Il metodo duale sceglie prima la variabile che esce di base e determina poi la variabile che entra in base . L'operazione di pivot viene eseguita su un elemento negativo . --~

2) Nel metodo del simplesso , in assenza di degenerazione

(~>Q),

il valore della funzione obiettivo diminuis ce ad ogni ite razi o~n

ne; nel metodo duale,

assenza di degenerazione

(~ >

Q) il

valore della funzione obiettivo aumenta ad ogni i terazione. d)

Si consideri il seguente max 4x x

7x 3x

1

l l 1

+

Sx

+

x

+

Sx

+ 5x

9x

+

2

+ x

2

+10x

2

x • x , x , x

1

2

3

3x

+

2

3

3

4

llx

+ +

4

x4

2

15

2x .=:.t2o

+

4

3 3

problema di P.L.

+ 1Sx 2100 4

~O

La tabella iniziale di questo problema è :

o

-4

-5

-9

15

l

l

120 100

7

5

3

5

sviluppando

1

-11

o

o

o

l

l

l

o

3 lO

2

o

l

o o

15

o

o

l

calcol i la tabe lla finale r 1sulta la seguente:

-83-

695/7 50/7

o

3/7

o

ll / 7

13/7

o

5/7

l

5/7

o o

-S/7

10/7

o

-1/7

13/7

-6/7

l

4/7

l

12/7

-3/7

o

1/7

o -6/7 o 2/7

325/7 55/7

Supponiamo di incrementare c , costo relativo ad una variabile non di base 2 di una quantità o (con o>O). Il relativo valore c~ nella tabell a ottima as-

~--o.

sume il valore di

~è c~

c

t- o~O

e cioè 02_

Se invece risultasse o>

f allora la soluzione

trovata resta anche ottima.

t e quindi ci'=< O allora occorrerebbe applicare :nco-

ra alla soluzione trovata il metodo del simplesso per determinare la

n~ova

soluzione ottima. Si consideri ora l'incremento di c

1

relativo a l la variabile di base x ; c

assume quindi il valore c = 4 + a. Nella tabella ottimale avremo cl~ 1 e non si è più nella forma canonica •

.Per

1

1

=-

o

riottenere la forma canonica si procederà sommando alla riga zero la

prima riga moltiplicata per o e si avrà: 695 + so ~· o . l + 10. o 1 7 v, ' 7 7 '

-

11

7

-

s

-::(J.

1 '

13

10

7 +T

a;

o

la 7

5 1

e imponendo la condizione di ottimalità dovrà essere:

a< !!.. a - 13 lO

da cui deriva:

La nuova soluzione ottima sarà

695 + 50 a 1

7 di O 2 la colonna

Consideriamo ora le variazioni sulle bi ed esat tamente incrementiamo b cioè b 2 = 120 + o. Notando che b:' = bf + q~ 6 e che q~ 2 2 zero della tabella finale assumerà la forma 695 1 50

T

+

o6

+

oo

2

a1

6

325 + l 6

1

55

T

+

oo

325 La soluzione trovata rimarrà a.'ll!IÙ ssibile e quind.i o t ti-oa se e solo se - 7- +6>0

-84-

325

cioè é
O cioè-5 < ò < 55 -

~

3

Si consideri ora un incremento Y al coefficiente a

avrà af2 ; af2

+

qt2·Y

a

af2

cioè a)

32

2

5 +; . si

a!7·Y

+

In questo caso essendo la perturbazione effettuata su un coefficente corrispondente nella tabella finale ad una colonna non di base basterà imporre: a * ' 02

=

5

c*'> O cioè l + 2y > O da cui y_ > --~ altrimenti bisognerà riap2 7 7 -

plicare il metodo del simplesso.

~ Nel caso che si consideri l'introduzione di un ulteriore vincolo s i control la se la soluzione ottima soddisfa il nuovo vincolo. Se i l nuovo vincolo è 2 2 10 si nota che la soluzione ottima x

1

+ x

x~

l

50 7

,c

2

O soddi s f a il nuovo vi nco l o

e quindi è anche ottima per il nuovo problema di P . L. Se i l vincolo è

x

+ x < 5 • 1 2 La soluzione ottima non soddisfa il nuovo vincolo per cui lo s i

ag v. iung~

alla tabella finale. Al fine di ripristinare la forma canon1 ca oc co rrcr3 azzerare a

mediante sottrazione della riga l alla 41 tal uvdo come riga 4

5

50 7

• o •

l -

75 • o, 75 •

10 7

, o ,

riga~.

Si otterrà in

l +7 • l

e si otterrà una soluzione di base non amnùssibile 1n quant o 5 per cui bisognerà applicare il metodo dual e del simpl e sso .

50 7

< O

-esCAP. 6 - PROGRAMMA.ZIO'fljt: LINEARE: ALCUNI PROBLEMI DI STRUTTURA PARTICOLARE

6.1 Formulazione del Date

proble~a

dei trasporti.

m origini A.(i= l, 2, .... m) che producono le quantità a,(> O) l

l

ed n destinazioni B.(jc 1,2, .... n ) che consumano le quantità b.(> O) J

J

n iflai=j~lbj,determinare t!l

di una stessa merce,

con

le quantità di merce

da spedire da ogni A. ad ogni B. in modo da soddisfare le domande al J

l

minimo costo totale. Chiamando x .. (i=l , . . . m; j• l, ... n) le quantità incognite di merce da l.J

~d

spedire da ogni A.

l

ogni B. e c .. i costi unitari di spedizione J

lJ

da A. a Bj · il problema si formula analiticamente come: 1 min z .. ~ c .. x .. i•l j•l lJ l.J

t

n

,r

x ..

lJ

]''"l

m

..

a.

i • l, ... . m

l

x .. ,. b. lJ J

. L.

l"'l.

x .. > lJ

j

o

=

l, .... n

Yi ,

Yj

Il problema dei trasporti può essere risolto con i metodi genera l i · di risoluzione visti finora. Tuttavia, data la sua particolare st r uttura, esistono dei metodi specifici che ne semplificano la soluzione. Inoltre nella suddetta formulazione si . possono far rientrare i casi n

in cui i vincoli di origine ( . i

J =1

m

= a. , i

x .. lJ

l

l, .... m) o i vincoli

=

di destinazione(.[ x .. =b., j =l ... . . n) siano espressi come disugua1.= 1 l]

J

glianze. Si supponga infatti ad esempio che sia x .. < b. l.J -

m

j • l, ..... n

J

n

.E

a.< .E b. l•1 l J'"' 1 J

cioè l'ammontare totale dell'offerta è inferiore all ' ammontare totale della domanda, allora int r oducendo nelle disuguaglianze le variabili ausiliarie x

. > O

m+l,J

m+ l

j=l ... n si ottiene .E

l"' 1

x .. • b. J

l.)

j~l,2,

. .. n

n

o in modo equivalente .E

J•l

-~lxm+ l ,J·=-~l J

J•

0

x.

.

l,J

b.-.Pl.El .. -= J= -~lb J. J j= le x lJ

j .. l. .. . n da cu1

. • b.

+x

m+l,J

J

1~1 =

8

a l.. "'

cioè si è introdotta una sorgente fittizia A

m+ l

m+ 1

di capacità a

m+ 1

tale

-86che risulti n

m+l

.[

J.. 1

dove c

. m+ 1 •J

b. •.E

a.

l

o

Si noti inoltre che il problema dell'assegnamento è un problema di trasporto m-1

volte degenere

ta da m componenti uguali

1n quanto ogni soluzione di base sarà costituil e tutte le altre uguali a zero.

a~

L'algoritmo per la determinazione dell'assegnamento ottimo opera unicamente sulla matrice dei costi C={cij}· L'alr,oritmo si articola nei seguenti passi: l) Si sottrae ad ogni riga di C il suo elemento minimo. 2)Si sottrae ad ogni colonna della matrice ottenuta il suo elemento minimo. 3) Si effettua il maggior numero

possibile di assegnamenti k in

corrispondenza agli zeri della matrice C. 3a) Se kcm allora si è determinato l'assegnamento ottimo. 3b) Se k