Lezioni e esercizi, Ricerca operativa

Name: Lezioni e esercizi, Ricerca operativa
Brand: Skuola.net
Price: 4.99 EUR
Availability: InStock
Rating: 4.0 (3 reviews)
Author: saimonlebone

Revisionato il 16/04/2026

di saimonlebone

Publisher

Vota 4,0/5 (3)

Contenuto verificato e approvato dal Team di Esperti di Skuola.net

Appunti di Ricerca operativa per l'esame della professoressa Nicosia. Gli argomenti trattati sono i seguenti: la Programmazione lineare intera, i grafici, i teoremi, gli esercizi e le soluzioni …

Esame Ricerca operativa

Facoltà Ingegneria

Dal corso del Prof. Nicosia Gaia

Università Università degli Studi Roma Tre

A.A. 2014-2015

72 pagine

1 download

Appunto

Scarica

Estratto del documento

Problemi di programmazione lineare

Min c^Tx

Ax ≥ b

x ≥ 0

Problemi di programmazione lineare intera

Min c^Tx

Ax ≥ b

x ≥ 0

x intero

Riga

Tutte le variabili intere

Un sottoinsieme delle variabili intere

x ∈ {0,1}

Analizziamo

A, b interi

P = {x ≥ 0 / Ax ≥ b} limitato, non vuoto

Quindi iniziamo con

X insieme soluzioni ammissibili del problema intero formato da tutti i punti interi del poliedro P:

X = P ∩ Zⁿ

Osservazione: |X| limitato, a differenza del numero di soluzioni di un problema di programmazione lineare normale in cui le soluzioni sono in numero infinito.

Problemi di programmazione lineare

Min c^Tx

Ax ≥ b

x ≥ 0

Problemi di programmazione lineare intera

Min c^Tx

Ax ≥ b

x ≥ 0

x intero

Pluri

Tutte le variabili intere

Mista un sottoinsieme delle variabili intere

x ∈ [0,1]ⁿ

P = {x₀/Ax ≥ b} limitato, non vuoto

Quindi indichiamo con

X insieme soluzioni ammissibili del problema intero formato da tutti i punti interi del poliedro P:

X = P ∩ Z^m

Osservazione: |X| limitato, a differenza del numero di soluzioni di un problema di programmazione lineare normale in cui le soluzioni sono un numero infinito.

Esempio P.L. 1. muta

Un'azienda di trasporti dispone di φ veicoli V₁, ..., Vₚ. Devo minimizzare il costo delle ore di consumazione... queste possono essere modellate con variabili non necessariamente intere. Ma le risorse umane? Gli autisti non possono essere modellati con variabili intere. Questo è un esempio di P.L. 1. muta.

Esempio P.L. 1. pura

Produzione autovetture, devo produrre tenda potenze quote... variabili intere

Esempio PLO₁ (o binaria)

Devo decidere dove posizionare i poliziotti per la sorveglianza delle strade. Ma i grafi, con le righe rappresentano le strade, non hanno già incroci... è fatto che i poliziotti _all'incrocio basta. Xᵢ = {1 se il poliziotto è all'incrocio i min ∑ Xᵢ}

Enumerazione totale (per un problema PLO₁)

Quanto potrebbe impiegare un algoritmo di enum. tot. (brute-force) a trovare le soluzioni? Si enumerano tutti n vettori:

x₁ = [0, 0, ..., 0]
x_n = [1, 0, ..., 0]

Dipendendo di un computer che in 1 secondo verifica 10¹⁰ vettori ≈ 2¹³ vite. A livello algoritmico di potenza di calcolo di un fattore 1024 (2¹⁰) relative sono rispettivamente 1 modello 1 sec ≈ 2 giorni; 3743.5 miliardi di anni.

A Roma quanti incroci ci sono? ... è impraticabile.

Connessioni tra programmazione lineare e programmazione lineare intera

P.L.I. min C^Tx

Ax ≥ b

x ≥ 0 intero

P.L. min e^Tx

Ax ≥ b

x ≥ 0

Rilassamento lineare o continuo

X insieme delle soluzioni del problema di P.L.I.

P insieme della soluzione del problema di rilassamento lineare

X ⊆ P

Indichiamo con

Z_PL val. f.o. del rilassamento lineare

Z_PLI val. f.o. del problema intero

Z_PL ≤ Z_PLI la soluzione del rilassamento lineare è migliore di quella del problema intero

Proprietà in generale

(P) min f(x)

x ∈ A

Il rilassamento di (P)

(R) min g(x) tale che

x ∈ B

A ⊆ B

f(x) ≥ g(x) ∀ x ∈ A

Teorema

Se la soluzione ottima X^*_PL del rilassamento lineare è intera allora è ottima anche per il problema intero.

Z^*_PL = C^TX^*_PL ≤ Z_PLI

X^*_PL ∈ X = C^TX^*_PL ≥ Z_PLI

Z^*_PL = Z_PLI

Teorema

Se x^* B è soluzione ottima del rilassamento (R) di (P) allora se x^* A e f(x^*) = g(x^*) allora x^* è ottima anche per (P).

Osservazione

Possiamo pensare di trovare la sol. ottima del problema di PLI risolvendo il rilassamento e arrotondando la soluzione? No, e ora vediamo perché.

Esempi

P₁ min –x – y
2x – 5y ≥ –5
–2x + 2y ≥ 1
x, y ≥ 0 interi
soluzione ottima
Ril. LN (⁵/₂, 2)
z_RL = –⁹/₂ ≠ –5
Non arrotondabile in nessun modo a –2.
P₂ min x – y
2x – ⁵/₂y ≥ 5
–2x + 2y ≥ 1
x ≥ 1
x, y ≥ 0 interi
Stesse soluzioni di prima
Le sol. ottime di PLI (integre e arrotondabili)
P₃ min –x–y
y ≥ –1
–x+y ≥ 0
x, y ≥ 0 intero
Ancora un problema equivalente che ha stesso OSS I vincoli

Anteprima

Vedrai una selezione di 16 pagine su 72