Compito del 29 Ottobre - Programmazione Matematica

Compito di Programmazione Matematica
29 Ottobre 1998

PROBLEMA 1:

$\begin{figure}% \begin{center} \leavevmode \psfig{figure=digraph.eps, height=4 true cm}\par\end{center}\end{figure}$

1.: Fornire un flusso massimo da s a t.
2.: Fornire un'argomentazione per l'ottimalità.
3.: Di quali archi posso ridurre la capacità senza ridurre il valore del flusso massimo?
4.: Formulare come un problema di PL dove le variabili di decisione definiscano una circolazione.
5.: Scrivere il duale.
6.: Fornire una soluzione primale ottima ed una soluzione duale ottima.

PROBLEMA 2:

$\begin{displaymath}\begin{array}{l} \max \mbox{\ }x_1 +x_2\\ \left\{ \begin{... ...{array} \\ x_1, x_2 \geq 0 \end{array} \right. \end{array}\end{displaymath}$

1.: Risolvere sia per via grafica che algebricamente.
2.: Se la funzione obiettivo è il profitto di un'attività, quanto saremmo disposti a pagare per incrementare di un'unità il termine noto nel primo o secondo vincolo? E fino a dove saremmo disposti a pagare tale prezzo?
3.: Di quanto dovremmo alterare ciascun coefficiente nella funzione obiettivo (singolarmente) affinchè la soluzione non sia più ottima?

PROBLEMA 3:

$\begin{displaymath}\begin{array}{l} \max \mbox{\ }x_1 +x_2 +x_3 + x_4 +x_5 + x_... ...2, x_3, x_4, x_5, x_6 \geq 0 \end{array} \right. \end{array}\end{displaymath}$

Si consideri la soluzione: $x_1=\frac{3}{2}, \; x_2=\frac{2}{3}, \; x_5=\frac{5}{6}, \; x_6=\frac{2}{3}, \; x_3 = x_4 = 0$ .

1.: È ammissibile?
2.: È ottima?
3.: È di base?
4.: Trovare le soluzioni ottime di base. (Avvalersi del lavoro svolto al punto 2.).

PROBLEMA 4:

$\begin{figure}% \begin{center} \leavevmode \psfig{figure=oddTetra.eps, height=5.7 true cm}\par\end{center}\end{figure}$

1.: Fornire un accoppiamento perfetto di peso minimo.
2.: Fornire un certificato di ottimalità.
3.: Indicare quali accoppiamenti perfetti siano ottimi, motivando la risposta con riferimento al certificato di ottimalità fornito al punto 2.).

PROBLEMA 5(COINCISIONE, CHIAREZZA E SEMPLICITÀ):

1.: Dimostrare la formula di Eulero per grafi planari
2.: Utilizzare la formula di Eulero per dimostrare che K₅ e K_3,3 non sono planari.

29 ottobre 1998