• Non ci sono risultati.

Il problema artificiale

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Il problema artificiale"

Copied!
12
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 12 pagine )

Testo completo

(1)

Metodo delle due fasi

I

Il problema artificiale

I

la fase I del Simplesso

I

esempi

rif. Fi 3.2.5;

(2)

Problema artificiale

Dato un problema in forma standard min{c

T

x : Ax = 0, x ≥ 0}, con b ≥ 0, definiamo problema artificiale:

w = min

m

X

i=1

y

i

s.t.

Ax + Iy = b

x, y ≥ 0

le variabili y sono dette artificiali.

(3)

Esempio

min 3x

1

+ 4x

2

+ 6x

3

s.t.

x

1

+ 3x

2

+ 4x

3

= 1 2x

1

+ x

2

+ 3x

3

= 2 x

1

, x

2

, x

3

≥ 0

min y

1

+ y

2

s.t.

x

1

+ 3x

2

+ 4x

3

+ y

1

= 1 2x

1

+ x

2

+ 3x

3

+ y

2

= 2 x

1

, x

2

, x

3

, y

1

, y

2

≥ 0 da cui il tableau:

0 0 0 1 1 0 1 3 4 1 0 1 2 1 3 0 1 2

sottraendo alla riga 0 le altre:

-3 -4 -7 0 0 -3 1 3 4 1 0 1 y

1

2 1 3 0 1 2 y

2

forma canonica

(4)

Fase I

Possiamo quindi risolvere il problema artificiale col Metodo del Simplesso, ottenendo la soluzione (x

∗

, y

∗

) di valore w

∗

. Sono possibili 2 casi:

I

w

∗

> 0 non esiste una soluzione del prob. artificiale con y

i

= 0, i = 1, . . . , m, quindi il sistema Ax = b, x ≥ 0 non ammette soluzione: il problema originale ` e inammissibile

I

w

∗

= 0 quindi y = 0 e x

∗

` e sol. ammissibile del problema originale.

2 sottocasi per il tableau ottimo:

(a) tutte le variabili artificiali sono fuori base

(b) esiste una variabile y

h

in base

(5)

Caso 2a: variabili artificiali fuori base

I

eliminando le colonne corrispondenti alle var. artificiali il tableau in forma canonica risp. a una base

I

sostituire la f.o. artificiale con quella originaria, portare la riga 0 in forma canonica

I

applicare il Metodo del Simplesso (Fase II)

(6)

Esempio (continua)

scegliamo la var. entrante x

3

e t = arg min{1/4, 2/3} = 1 =⇒ var.

uscente y

1

-3 -4 -7 0 0 -3 1 3 4 1 0 1 y

1

2 1 3 0 1 2 y

2

P IV OT (t = 1, 3)

=⇒

-5/4 5/4 0 7/4 0 -5/4 1/4 3/4 1 1/4 0 1/4 x

3

5/4 -5/4 0 -3/4 1 5/4 y

2

scegliamo la var. entrante x

1

e t = arg min{1, 1} = 2 =⇒ var. uscente y

2

P IV OT (t = 2, 1)

=⇒

0 0 0 1 1 0

0 1 1 2/5 -1/4 0 x

3

1 -1 0 -3/5 4/5 1 x

1

soluzione ottima

(1, 0, 0, 0, 0) di valore 0

(7)

Esempio (continua)

le variabili y

1

, y

2

sono fuori base, quindi eliminiamo le corrisp.

colonne e ripristiniamo la f.o. originaria

3 4 6 0

0 1 1 0 x

3

1 -1 0 1 x

1

mettiamo in forma canonica sommando alla riga 0 le righe 1 e 2 moltiplicate per −6 e −3 risp.

0 1 0 -3

0 1 1 0 x

3

1 -1 0 1 x

1

eseguiamo quindi la FASE II: c ≥ 0 =⇒ (1, 0, 0) ` e soluzione

ottima

(8)

Caso 2b: variabile y h in base

essendo w

∗

= 0 deve essere y

h∗

= 0, quindi abbiamo un caso degenere. Se h = B(i), si ha:

x

1

· · · x

j

· · · x

n

y

1

· · · y

h

· · · y

n

0 0 −w

.. . .. .

0

¯

a

i1

¯ a

ih

¯ a

in

1 0 y

h

0

.. . .. .

0

(9)

Caso 2b: variabile y h in base

• se esiste un ¯ a

ij

6= 0, eseguiamo P IV OT (i, j) in modo da far uscire y

h

dalla base.

I

possiamo farlo anche se ¯ a

ij

< 0 in quanto ¯ b

i

= 0, quindi rimane ¯ b ≥ 0

I

il valore w = w

∗

non cambia

ripetendo il procedimento per tutte le var artificiali in base ci si riconduce al caso (2a).

• se invece tutti i valori ¯ a

i1

, . . . , ¯ a

in

sono nulli, eliminando le var.

arificiali si ottiene una riga del tableau tutta nulla, cio` e la

corrispondente equazione era ottenibile come combinazione lineare

delle altre e pu` o essere eliminata (≡ A non ha rango m)

(10)

Esempio

min 7x

1

− 3x

2

− 6x

3

s.t.

3x

1

− 4x

2

− 2x

3

= 3 x

1

+ x

2

+ x

3

= 1 x

1

, x

2

, x

3

≥ 0

min y

1

+ y

2

s.t.

3x

1

− 4x

2

− 2x

3

+ y

1

= 3 x

1

+ x

2

+ x

3

+ y

2

= 1 x

1

, x

2

, x

3

, y

1

, y

2

≥ 0 da cui il tableau:

0 0 0 1 1 0

3 -4 -2 1 0 3

1 1 1 0 1 1

sottraendo alla riga 0 le altre:

-4 3 1 0 0 -4 3 -4 -2 1 0 3 y

1

1 1 1 0 1 1 y

2

forma canonica

(11)

Esempio

scegliamo la var. entrante x

1

e t = arg min{1, 1} = 2 =⇒ var. uscente y

2

-4 3 1 0 0 -4 3 -4 -2 1 0 3 y

1

1 1 1 0 1 1 y

2

P IV OT (t = 2, 1)

=⇒

0 7 5 0 4 0

0 -7 -5 1 -3 0 y

1

1 1 1 0 1 1 x

1

OSS. la var artificiale y

1

rimane in base nel tableau ottimo del problema artificiale. Eseguiamo quindi un nuovo pivot:

P IV OT (t = 1, 3)

=⇒

0 0 0 1 1 0

0 7/5 1 -1/5 3/5 0 x

3

1 -2/5 0 1/5 -2/5 1 x

1

tutte le var. artificiali sono fuori base

(12)

Esempio

eliminiamo le var. artificiali e ripristiniamo la funzione obiettivo originaria:

7 -3 -6 0

0 7/5 1 0

1 -2/5 0 1

in forma canonica

=⇒

0 41/5 0 -7

0 7/5 1 0

1 -2/5 0 1

Inizia FASE II:

STOP: (1, 0, 0) soluzione ottima

Riferimenti

Scarica adesso ( PDF - 12 pagine - 179.41 KB )

Documenti correlati

Siano X ∼ B 1,14 e Y ∼ B 1,34 due variabili casuali indipendenti

 la taglia del campione `e molto grande (≥ 1000) ma la distribuzione della variabile in esame non ` e normale.  la varianza della variabile in esame `e

Variabili Aleatorie Variabili Aleatorie

• si ha un fading alla Rice in presenza di un termine dominante (in genere cammino LOS, o cammino LOS + cammino riflesso sul terreno) e numerosi cammini che &#34;perturbano&#34;

Lezione n° 13

il simplesso utilizzando come base iniziale le colonne della matrice (A,I) associate alle variabili artificiali y. y sono in base mentre tutte le variabili x sono

Algoritmo del Simplesso

 Se nessuna variabile artificiale è ancora in base, ho una base fatta da sole colonne del problema originario e posso partire con Fase 2 su esso.  Se ho ancora variabili

L I sistemi olfattivi artificiali

L’aroma di un alimento indica la percezione dell’in- sieme delle molecole volatili che si sprigionano dall’alimento stesso: il problema dell’identificazione e del controllo

SISTEMI OLFATTIVI ARTIFICIALI

La matrice di sensori è costituita da un insieme di sensori con caratteristiche diver- se, in modo che l’insieme delle loro rispo- I nasi elettronici sono sistemi

Stato dell’Arte su Microvascolarizzazione dei Tessuti Artificiali e Microvasi Artificiali

secondo alcuni non sarà mai possibile sostituire gli animali nelle sperimentazioni a causa della complessità insita in tutti i sistemi biologici; secondo altri, solo

“aperto” a tutte le variabili di apprendimento linguistico. Nel

Alla fine della sperimentazione, i risultati positivi degli alunni hanno rivelato non solo una maggiore disinvoltura nella lingua straniera, ma anche la proposta