Risposte aperte paniere di ricerca operativa

PL

15. Enunciare e dimostrare il teorema fondamentale della

PL 2

1 =

Ovviamente, se la regione ammissibile è vuota (

Teorema Dato un problema di PL in forma generale ∅) il problema di PL non può essere né illimitato

min inferiormente né può ammettere una soluzione ottima

. . ≥ ≠ ∅,

Se invece distinguiamo due casi

≥ 0 1. La regione ammissibile è un poliedro convesso

= ∅)

la regione ammissibile è vuota ( oppure = {0 })

(

•

< 0 ∈ ()

Se per qualche allora il 2. La regione ammissibile è un troncone convesso

problema è illimitato inferiormente ≠ {0 })

(

•

≥ 0 ∈ ()

Se per ogni allora il problema

∗

∈ ()

ammette una soluzione ottima 4

Dimostrazione

3

Dimostrazione (cont.) (cont.) ∈

Dal momento che e è convesso, allora

= {0 } = 0 = 0

Caso 1. e, quindi, per .

∈( )

Dimostriamo che il problema ammette una soluzione

∗

∈ ()

ottima , … ,

Quindi esistono coefficienti tali

1

che

= { , … , }

Sia l’insieme dei vertici di

1 �

�

∗ 0 ≤ ≤ 1 = 1, . . ,

= 1

=

Vogliamo dimostrare esista una soluzione ottima =1

=1

∗

∈ ()

∈

Sia una soluzione ammissibile del problema di PL

in forma generale. 6

5

Possiamo scrivere ∗

∈ ( )

Sia il vertice del poliedro in cui la funzione

obiettivo assume il valore minimo

� �

( ) ≥

= =

∗

= arg min

=1,..,

=1

= 1 ′

∈

Per ogni soluzione ammissibile risulterà

′ ∗

� ≥

min = min

≥ ∗

=1,..,

= 1,.., ∈ ()

Quindi è una soluzione ottima del

problema di PL

=1 8

7

Dimostrazione (cont.) Dimostrazione (cont.)

≠ {0 }.

Caso 2. Possiamo distinguere due

< 0

Poiché , la funzione

casi

+ = +

< 0 ∈ () ≠ 0 0 0

Caso 2.a per qualche con −∞ → ∞

Tende a per e quindi il problema è illimitato

Vogliamo dimostrare che il problema è illimitato inferiormente

inferiormente

≥ 0 ∈ ≠ { 0 }

Caso 2.b per ogni

∈ ()

Poiché allora è una direzione di e ogni Dimostriamo che il problema ammette una soluzione

= + ∈

punto della semiretta di origine e ∗

∈ ()

ottima in modo analogo al Caso 1.

0 0

direzione appartiene a

+ ∈ ∀ ∈ , ≥ 0

0 0

Lezione 010

24. Enunciare e dimostrare il teorema fondamentale della

PL

Ovviamente, se la regione ammissibile è vuota (=∅) il problema di PL non può essere né illimitato

≠∅,

inferiormente né può ammettere una soluzione ottima; Se invece distinguiamo due casi

={0})

1. La regione ammissibile è un poliedro convesso (ec ≠{0}),

2. La regione ammissibile è un troncone convesso (ec possiamo distinguere due casi:

CONTINUA…→

Il teorema fondamentale della PL ha notevoli implicazioni dal punto di vista algoritmo nella risoluzione dei

problemi di PL.

Si noti come il teorema non implica che tutte le soluzioni ottime di un problema di PL siano vertici di (e,

xt xt

quindi, appartengano a (), ma che se esiste una soluzione ottima allora esiste un vertice in ()

ottimo;

In generale, l’insieme delle soluzioni ottime di un problema di PL non è composto da un solo vettore

Lezione 011

25. Enunciare e dimostrare il criterio di illimitatezza.

Dato un problema di PL in forma generale

min

.. ≥

≥0 ={∈ℝ

dal teorema fondamentale della PL sappiamo che il problema se :≥,≥0} è non vuoto, se

<0 ∈ ec ≥0

per qualche () allora il problema è illimitato inferiormente. Se invece per ogni

∈ec ≥0 ∈ec

() per ogni () il problema ammette soluzione ottima e non è illimitato.

Il criterio di illimitatezza fornito dal teorema fondamentale della PL richiede di determinare, se

esita, una direzione ∈ec() per cui <0

Richiede infatti di risolvere il problema di PL min

.. ≥0

≥0

e verificare che all’ottimo ∗<0; Quindi questo criterio non è di immediato impiego pratico e si

preferisce impiegare un altro risultato noto.

Teorema Il problema di PL in forma standard min

.. =

≥0

è illimitato inferiormente se per qualche ∈ {1,.., −} si verifica che

1. l’ –esima componente del vettore dei costi ridotti è negativa <0

2. l’ –esima colonna della matrice − sia non positiva (− ≤0)

Dimostrazione Il problema di PL in forma standard è illimitato se e solo se è illimitato il problema

ridotto rispetto a una qualsiasi la relativa base

Min (−−−)+

.. −−−≥0 ≥0−

Consideriamo il poliedro delle soluzioni ammissibili

′={ ∈ ℝ :−−− ≥0 , ≥0 }

−

−

Il cono di recessione ec (′) del poliedro ′ è dato dalle soluzioni del sistema

− ≤0

≥0

−

Per l’ipotesi, ̅=

è una soluzione ammissibile, in quanto − ≤0 e ≥0 .

−

Quindi ∈ec (′). Il valore della funzione obiettivo ̅ = <0

Per il teorema fondamentale della PL, il problema ridotto è illimitato.

26. Enunciare e dimostrare il criterio di ottimalità di una soluzione di base ammissibile.

ESMPI SULLE SLIDE LEZIONE 12 DALLA N4.

10. Dato il seguente problema di

PL

determinare analiticamente le soluzioni di base e, per ognuna di esse, si determini se sia ammissibile o meno

11. Dato il seguente problema di

PL

determinare analiticamente le soluzioni di

base e, per ognuna di esse, si determini se sia

ammissibile o meno

Lezione 012

27. Data una soluzione di base ammissibile non necessariamente ottima, illustrare come sia possibile

determinare una nuova soluzione di base ammissibile di costo non superiore.

Determiniamo quindi una nuova soluzione di base ammissibile a partire da ; Dobbiamo individuare

1

• una colonna fuori base da far entrare nella nuova base

• una colonna in base da far uscire dalla nuova base

1 2

Per passare dalla soluzione di base alla soluzione di base semplicemente selezionando

•la colonna entrante in base cui corrisponderà, nella nuova soluzione di base ammissibile, una componente

ℎ

non nulla, Ricordiamo che è stata scelta una colonna con costo ridotto negativo come candidata a

ℎ

entrare in base che quindi darà luogo ad una soluzione di base ammissibile di costo sicuramente non

superiore alla precedente.

•la colonna uscente di base cui corrisponderà, nella nuova soluzione di base ammissibile, una componente

nulla, Ricordiamo che è stata scelta una colonna corrispondente a una riga con il minimo rapporto tra

)

componente ( e coefficiente non negativo come candidata a uscire in base.

−1 ℎ

,̅

Data una soluzione di base ammissibile loscambiodicolonnepuò esseresvoltoanaliticamenteoppure possiamo

adottare un procedimento per lo scambio di colonne in base detto pivot.

Lezione 013

28. Illustrare il diagramma di flusso del metodo del simplesso per un generico problema di PL.

29. Illustrare le assunzioni e le operazioni previste dalla Fase 2 del medoto del simplesso.

ank ,

Una volta assunto che il problema non è vuoto, il rango della matrice dei coefficienti sia =

determinata una prima base ammissibile e determinata la forma canonica secondo quest’ultima:

1.verificare il criterio di ottimalità osservando gli elementi della seconda riga: i costi ridotti se sono

negativi non possiamo dire che la soluzione è ottima.

verificare il criterio di illimitatezza osservando gli elementi delle colonne relative alle variabili con

2.

costo ridotto negativo: se ogni colonna ha almeno un elemento positivo e non possiamo concludere che

il problema sia illimitato.

Determinare le due colonne per lo scambio di base per determinare una nuova soluzione di base

3.

ammissibile;

a)

viene candidata a entrare in base la colonna relativa alla variabile avente il costo ridotto più

n

negativo.

b) si individua la riga della colonna candidata a entrare in base che corrisponde al valore minimo tra i

rapporti fra i coefficienti della colonna ed corrispondenti termini noti (quelli sulla stessa riga).

4. Effettuare l’operazione pivot scambiando la colonna fuori base con la colonna in base applicando

individuato precedentemente.

l’operazione pivot sull’elemento

Lezione 014

30. Illustrare le assunzioni e le operazioni previste dalla Fase 1 del medoto del simplesso.

Dato il problema di PL in forma standard mi