Lezione n°4

Lezione n

°

4

- Problemi di Programmazione Matematica - Problemi Lineari e Problemi Lineari Interi - Forma Canonica. Forma Standard

R. Cerulli – F. Carrabs

Lezioni di Ricerca Operativa

Corso di Laurea in Informatica Università di Salerno

Problema di Ottimizzazione

Data una funzione f : Rn_{⟶ R e X⊆R}n _{un problema di}

Ottimizzazione (PO) può essere formulato come:

min f(x) s.t.

x ∈ X

decisionali insieme delle

soluzioni ammissibili

Quindi un problema di Ottimizzazione consiste nel determinare, se esiste, un punto di minimo della funzione f tra i punti dell’insieme X.

Problemi di Programmazione Matematica

Quando l’insieme delle soluzioni ammissibili di un problema di ottimizzazione viene espresso attraverso un sistema di equazioni e disequazioni, tale problema prende il nome di problema di

Programmazione Matematica (PM). min f(x) s.t. g_i(x) ≥ b_i i=1,…,m i-esimo vincolo del sistema i-esima componente del vettore dei

Un problema di PM è lineare quando:

Problemi di Programmazione Lineare

Ø la funzione obiettivo è lineare: f(x) = cT_x

Ø l’insieme X è espresso in termini di relazioni (uguaglianze e disuguaglianze) lineari min f(x) s.t. g_i(x) ≥ b_i i=1,…,m min c₁x₁ + c₂x₂ +...+ c_nx_n s.t. a₁₁x₁ + a₁₂x₂ +...+ a_1nx_n b₁ a₂₁x₁ + a₂₂x₂ +...+ a_2nx_n b₂ a_m1x₁ + a_m2x₂ +...+ a_mnx_n b_m

min

c

x

s.t.

Ax

b

Programmazione Lineare Continua (PL) x ∈ Rn : Ax ≥ b

{

}

x ∈ Zn : Ax ≥ b

Esempio

Un vettore x di Rn _{è soluzione ammissibile per il problema di PL se e solo se}

soddisfa tutti i vincoli del problema.

Problemi di Programmazione Lineare

min f(x)

s.t.

g_i(x) ≥ b_i i=1,…,m

Dato il seguente problema di programmazione lineare

un vettore x’ di Rn_:

• soddisfa il vincolo g_i(x) ≥ b_i se g_i(x’) ≥ b_i

• viola il vincolo g_i(x) ≥ b_i se g_i(x’) < b_i

Soluzioni di un problema di PL

s.t.

g_i(x) ≥ b_i i=1,…,m

Un problema di programmazione lineare risulta:

• Inammissibile se la regione ammissibile è vuota ossia X=

∅

• Illimitato (inferiormente) se scelto un qualsiasi scalare k, esiste sempre un punto x∈X tale che f(x) < k.

• Ammettere soluzione ottima finita se esiste un punto x*_{∈X tale che} f(x*_{) ≤ f(x) ∀x∈X.}

Un’azienda produce tre tipi di elettrodomestici: lavatrici, frigoriferi e forni.

Per produrre una lavatrice occorrono 9 ore di lavorazione sulla macchina M1 e 8 ore di lavorazione sulla macchina M2; mentre per produrre un frigorifero occorrono 11 ore di lavorazione sulla macchina M2; infine per produrre un forno occorrono 4 ore sulla

macchina M1 e 6 sulla macchina M2.

La macchina M1 è disponibile per 137 ore settimanali, mentre la macchina M2 è

disponibile per 149 ore settimanali. Il numero di forni prodotti non può essere superiore alla somma dei frigoriferi e delle lavatrici prodotte. Tuttavia devono essere prodotti

almeno 20 forni. Inoltre il numero di lavatrici prodotte non può essere superiore al numero di frigoriferi prodotti per al più 5 unità.

Il guadagno ottenuto dalla vendita di una lavatrice è di 375 euro, quello ottenuto per un frigorifero è 320 euro e quello per un forno è 170 euro. Si vuole conoscere la quantità di lavatrici, frigoriferi e forni da produrre settimanalmente per massimizzare il guadagno totale nel rispetto dei vincoli di produzione.

a) Si formuli il corrispondente modello di programmazione.

8

9

La prima cosa da fare per poter formulare un problema è individuare le variabili decisionali. Poiché il nostro obiettivo è quello di definire il numero di lavatrici, frigoriferi e forni da produrre, associamo ad ogni tipo di elettrodomestico una variabile distinta:

x₁ = numero di lavatrici da produrre x₂ = numero di frigoriferi da produrre x₃ = numero di forni da produrre

Esempio 1: Piano di produzione aziendale

9x₁ + 4x₃ <= 137 8x₁ + 11x₂ + 6x₃ <= 149 x₃ <= x₁ + x₂ x₃ >= 20 x1 <= 5 + x2 x1, x2, x3 >= 0, intere max 375x₁ + 320x₂ + 170x₃

Problemi di Programmazione Lineare:

Forma Canonica

Consideriamo

un

problema

di

Programmazione

Lineare (PL) con m vincoli ed n variabili in

Forma

Canonica di minimo

:

● x è il vettore nx1 delle variabili decisionali

● c è il vettore nx1 dei coefficienti di costo della funzione

obiettivo

● b è il vettore mx1 dei termini noti dei vincoli

● A è la matrice mxn dei coefficienti dei vincoli; A=[a_ij], i=1,...,n,

j=1,...,m n T

R

b

x

c

z

Î

³

³

=

x

0

x

x

A

min

Problemi di Programmazione Lineare:

Forma Standard di minimo

T n

min z c x

Ax b

(1)

x 0 (2)

x R

=

=

³

Î

Condizione: b ≥ 0

●

I valori di x che soddisfano i vincoli (1) sono detti

soluzioni

del problema di PL.

●

Inoltre, i valori di x che soddisfano anche i vincoli (2)

L’ipotesi

m<n

(più

variabili

che

vincoli)

non

rappresenta una perdita di generalità.

E’ noto infatti che il sistema di equazioni lineari (1):

❏

può ammettere una soluzione unica se m=n

può ammettere

¥

soluzioni se m<n

Solo il secondo caso è significativo dal punto di vista

dei problemi di ottimizzazione.

Si assumono soddisfatte le seguenti ipotesi:

Ø

m<n

Definizione 1 (Problemi equivalenti)

Due problemi di programmazione lineare di minimo (massimo) (P) e (P') sono equivalenti se, per ogni soluzione ammissibile di (P), possiamo costruire una soluzione ammissibile di (P') con lo stesso valore e, per ogni soluzione ammissibile di (P'), possiamo costruire una soluzione ammissibile di (P) con lo stesso valore.

Osservazione 2

Qualunque problema di PL può essere trasformato in un problema equivalente in forma canonica o standard.

Osservazione 1

Se due problemi di programmazione lineare sono equivalenti allora i valori delle rispettive soluzioni ottime coincidono.

Formulazioni equivalenti:

max z c x

=

Û -

min

- = -

z

c x

max z

=

3x +5x

Û -

min z

- = -

3x

-

5x

Funzione Obiettivo

Formulazioni equivalenti:

Vincoli

î

í

ì

³

£

Û

=

-£

-Û

³

b

x

A

b

x

A

b

x

A

b

x

A

b

x

A

La nuova variabile x

introdotta prende il

nome di

variabile di slack (scarto)

n

n 1

i

ij j

j 1

x

₊

b

a x

=

= -

å

a

_ij

x

_j

j=1

n

∑

≤ b

_i

⇔

a

_ij

x

_j

j=1

n

∑

+ x

_n+1

= b

_i

0

³

x

4x

₁

_{+ 6x}

₂

_{≤ 15 ⇔ 4x}

₁

_{+ 6x}

₂

_{+ x}

₃

_{= 15}

Variabile di slack: esempio

• x₁=1, x₂=1 è un assegnamento di valori che soddisfa il vincolo di disuguaglianza (4+6≤15).

In corrispondenza di tale soluzione, è possibile soddisfare il vincolo di uguaglianza assegnando i medesimi valori ad x₁ e x₂ ed un valore non negativo ad x₃: x₃=5 è 4+6+5=15

• x₁=1, x₂=2 è un assegnamento di valori che non soddisfa il vincolo di disuguaglianza (4+12>15).

Non è possibile soddisfare il vincolo di uguaglianza utilizzando lo stesso assegnamento di valori per x₁ e x₂ ed assegnando un valore non negativo ad x₃.

La nuova variabile x

introdotta prende il

nome di

variabile di surplus (eccedenza)

x

_n+1

₌

a

_ij

j=1

n

∑

x

j

− b

i

a

_ij

x

_j

j=1

n

∑

≥ b

_i

⇔

a

_ij

x

_j

j=1

n

∑

− x

_n+1

= b

_i

0

³

x

x

_{≤ 0 ⇔ −x}

_{≥ 0 ⇒ x '}

_{= −x}

, x '

_{≥ 0}

Formulazioni equivalenti: variabili ≤ 0

Esempio:

7x

_{+ 2x}

_{= 5 x}

_{≥ 0, x}

_{≤ 0}

Sostituiamo x_j con -x’_j ovunque appaia nel modello (vincoli e funzione obiettivo).

7x

_{− 2x '}

_{= 5 x}

_{≥ 0, x '}

_{≥ 0, x '}

_{= −x}

x₁=1, x₂=-1 è un assegnamento di valori che soddisfa il vincolo.

x₁=1, x’₂=-x₂=1 è un assegnamento di valori che soddisfa il vincolo.

x

_{n.v. ⇒ x}

_{= (x '}

_{− x ''}

) x '

_{≥ 0,x ''}

_{≥ 0}

Formulazioni equivalenti: variabili non vincolate

Esempio:

Sostituiamo x_j con la differenza tra x’_j e x’’_j ovunque appaia nel modello (vincoli e funzione obiettivo).

Il valore (positivo, negativo oppure 0) assunto da x_j in ogni soluzione ammissibile sarà ottenuto come differenza tra due numeri non negativi.

7x

− 2(x '

− x ''

) = 7⋅1− 2(−3) = 13 > 5 x

≥ 0, x '

≥ 0, x ''

≥ 0

x₁=1, x₂=-3 è un assegnamento di valori che soddisfa il vincolo. Infatti 7∙1 - 2(-3) = 13 > 5. Ora fissati due valori per x₂’ e x₂’’ tali che x₂’-x₂’’=-3 (ad esempio x₂’=6 e x₂’’= 9) si ha:

3x₁ x₂ + x₃ <= 3 2x1 3x₂ 2x₃ >= 4 x₁ x₃ = 2 x₁ > = 0 x₂ <= 0 x₃ n.v. max z = x₁ x₂ x₃

Esercizio

Scrivere la forma canonica e la forma standard per il seguente problema di programmazione lineare.