• Non ci sono risultati.

Ottimizzazione Combinatoria 2005/2006 Homework 1

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Ottimizzazione Combinatoria 2005/2006 Homework 1"

Copied!
1
0
0

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

Scarica adesso ( 1 pagine )

Testo completo

(1)

Ottimizzazione Combinatoria 2005/2006 Homework 1

Cognome __________________

Nome __________________

Matricola __________________

Domanda 1

Disegnare un grafo G = (V, E), connesso, tale che 1. α(G) + τ(G) = 10.

2. µ(G) = τ(G) = 4

Domanda 2

Dato il grafo G di figura:

1. Formulare come problema di PL-{0, 1} il problema del massimo insieme stabile su G.

2. Sia D il duale del rilassamento lineare del problema precedente. Scrivere esplicitamente D e calcolarne la soluzione ottima.

3. Calcolare il massimo matching e il minimo vertex cover di G

Riferimenti

Scarica adesso ( PDF - 1 pagine - 26.16 KB )

Documenti correlati

Problema 1. Data g (x) ∈ C ([0,∞))) , tale che g (x) = 0 per x ≥ 2, trovare una soluzione del problema

Prima di inviare la soluzione TRAMITE CELLULARE lo studente contatta il docente, il docente controlla il foglio della soluzione, se neces- sario fará una foto.. Solo dopo lo

Il problema dello zaino 0-1 ‘intero’

• Sia B[k, w] il massimo valore della soluzione ottima S k con peso w (quindi, per i primi k elementi). • L’obiettivo è determinare B[n, W], con n il numero totale di elementi, e

1 Definizione del problema duale

Allora la soluzione ottima duale non cambia e, per la dualit` a forte, neanche la soluzione ottima del primale, cio` e l’aggiunta di due nuove alternative non inficia l’ottimalit`

1. Dato il seguente problema di PL max x1

Dato il grafo orientato con i pesi associati agli archi rappresentato in figura 1, determinare il peso dei cammini minimi (massimi) dal nodo s a tutti i nodi del grafo6.

Problema 1: Risolvere il Problema di Cauchy

Tema 2: Classificazione delle singolarit`a e residui di una funzione analitica in un intorno bucato di un punto. Si completi la trattazione fornendo

Ottimizzazione Combinatoria 2006/2007 Homework 1

L’azienda effettua il giro con un automezzo condotto da un unico autista che può guidare consecutivamente per un massimo di 1200 km;.. Il giro di consegna parte da Roma e termina

Ottimizzazione Combinatoria 2005/2006 Homework 2

L’azienda effettua il giro con un automezzo condotto da un unico autista che può guidare consecutivamente per un massimo di 1200 km;3. Il giro di consegna parte da Roma e termina

Ottimizzazione Combinatoria 2005/2006 Homework 4

Formulare come PL-{0, 1} il problema di massimizzare la redditività senza violare il vincolo di budget trimestrale.. Rafforzare il rilassamento lineare della formulazione di cui