Ricerca Operativa, domanda teorica su soluzioni ottime
Salve a tutti ragazzi, in un'esercitazione di Ricerca Operativa mi è stato posto questo quesito:
Dire se le seguenti affermazioni sono vere o false, giustificandone la risposta:
-non è possibile che un problema di programmazione lineare abbia esattamente due soluzioni ottime distinte;
-tutte le soluzioni ottime di un problema di programmazione lineare sono soluzioni ammissibili di base;
Ho dei grossi dubbi:
Per quanto riguarda il primo quesito:
In un problema di PL (program. lineare) dobbiamo andare ad individuare il valore delle nostre variabili decisionali affinchè il valore della funzione obbiettivo sia ottimo.
Ora ho pensato per il primo quesito che l'affermazione sia vera: in questa affermazione viene detto esattamente due, se supponiamo effettuare l'analisi grafica di un problema di programmazione lineare si possono presentare questi casi :
-la regione ammissibile è vuota, quindi nessuna soluzione
-regione ammissibile illimitata e problema di max illimitato superiormente (o di minimo illimitato inferiormente) non ho soluzione
-il problema ha soluzione ottima: questa è unica o sono infinite. E proprio su quest'ultima affermazione che si basa la mia risposta.
Fondamentalmente questo ci è detto dal teorema fondamentale della PL. Va bene come risposta?
-Per quanto riguarda il secondo quesito: beh si, una soluzione ottima è ammissibile, lo si vede pure applicando l'algoritmo del simplesso il quale è un algoritmo a direzione ammissibile, quindi l'ottimo da esso trovato è ammissibile, no?
Grazie dell'attenzione e se ho detto fesserie non siate troppo duri, ho da poco iniziato e ci è stato suggerito di studiare da delle slides che non approfondiscono molto gli aspetti teorici
Dire se le seguenti affermazioni sono vere o false, giustificandone la risposta:
-non è possibile che un problema di programmazione lineare abbia esattamente due soluzioni ottime distinte;
-tutte le soluzioni ottime di un problema di programmazione lineare sono soluzioni ammissibili di base;
Ho dei grossi dubbi:
Per quanto riguarda il primo quesito:
In un problema di PL (program. lineare) dobbiamo andare ad individuare il valore delle nostre variabili decisionali affinchè il valore della funzione obbiettivo sia ottimo.
Ora ho pensato per il primo quesito che l'affermazione sia vera: in questa affermazione viene detto esattamente due, se supponiamo effettuare l'analisi grafica di un problema di programmazione lineare si possono presentare questi casi :
-la regione ammissibile è vuota, quindi nessuna soluzione
-regione ammissibile illimitata e problema di max illimitato superiormente (o di minimo illimitato inferiormente) non ho soluzione
-il problema ha soluzione ottima: questa è unica o sono infinite. E proprio su quest'ultima affermazione che si basa la mia risposta.
Fondamentalmente questo ci è detto dal teorema fondamentale della PL. Va bene come risposta?
-Per quanto riguarda il secondo quesito: beh si, una soluzione ottima è ammissibile, lo si vede pure applicando l'algoritmo del simplesso il quale è un algoritmo a direzione ammissibile, quindi l'ottimo da esso trovato è ammissibile, no?
Grazie dell'attenzione e se ho detto fesserie non siate troppo duri, ho da poco iniziato e ci è stato suggerito di studiare da delle slides che non approfondiscono molto gli aspetti teorici
Risposte
Se il problema-tipo di PL cui ti riferisci è il classico[nota]Con il simbolo \(\langle \cdot , \cdot \rangle\) denoto il prodotto scalare di due vettori definito come \( \langle \mathbf{c}, \mathbf{x} \rangle := \sum_{n=1}^N c_nx_n\).[/nota]:
\[
\begin{cases}
\max & f(\mathbf{x}) = \langle \mathbf{c}, \mathbf{x} \rangle \\
\text{s. c.} & A\mathbf{x} \leq \mathbf{0} \\
& B\mathbf{x} = \mathbf{0}
\end{cases}
\]
(obiettivo e vincoli lineari), ciò che dici sul numero di soluzioni è senz’altro vero.
Supponi che $mathbf(x)_0$ ed $mathbf(x)_1$ siano di ottimo per \( f(\mathbf{x} ) = \langle \mathbf{c}, \mathbf{x} \rangle\) con valore ottimo $f^**$; considera i punti $mathbf(x)_lambda := (1-lambda) mathbf(x)_0 + lambda mathbf(x)_1$ (con $0 < lambda < 1$) che descrivono il segmento di estremi $mathbf(x)_0$ ed $mathbf(x)_1$, i quali (per la linearità dei vincoli) appartengono alla regione ammissibile e calcola:
\[
f(\mathbf{x}_\lambda ) = \langle \mathbf{c}, \mathbf{x}_\lambda \rangle = \langle \mathbf{c}, (1-\lambda ) \mathbf{x}_0 + \lambda \mathbf{x_1} \rangle = (1-\lambda) \langle \mathbf{c}, \mathbf{x}_0 \rangle + \lambda \langle \mathbf{c}, \mathbf{x_1} \rangle = (1 -\lambda) f^* + \lambda f^* = f^* \;,
\]
sicché anche ogni $mathbf(x)_lambda$ è di ottimo per $f$.
Per il secondo punto non so, perché non mi ricordo la definizione di s.b.a… Però credo sia sufficientemente vero.
Per il resto, butta le slides nel ces… nel dimenticatoio e prendi un testo decente.
Non si studia mai dalle slides, che servono solo come promemoria degli argomenti toccati durante il corso.
\[
\begin{cases}
\max & f(\mathbf{x}) = \langle \mathbf{c}, \mathbf{x} \rangle \\
\text{s. c.} & A\mathbf{x} \leq \mathbf{0} \\
& B\mathbf{x} = \mathbf{0}
\end{cases}
\]
(obiettivo e vincoli lineari), ciò che dici sul numero di soluzioni è senz’altro vero.
Supponi che $mathbf(x)_0$ ed $mathbf(x)_1$ siano di ottimo per \( f(\mathbf{x} ) = \langle \mathbf{c}, \mathbf{x} \rangle\) con valore ottimo $f^**$; considera i punti $mathbf(x)_lambda := (1-lambda) mathbf(x)_0 + lambda mathbf(x)_1$ (con $0 < lambda < 1$) che descrivono il segmento di estremi $mathbf(x)_0$ ed $mathbf(x)_1$, i quali (per la linearità dei vincoli) appartengono alla regione ammissibile e calcola:
\[
f(\mathbf{x}_\lambda ) = \langle \mathbf{c}, \mathbf{x}_\lambda \rangle = \langle \mathbf{c}, (1-\lambda ) \mathbf{x}_0 + \lambda \mathbf{x_1} \rangle = (1-\lambda) \langle \mathbf{c}, \mathbf{x}_0 \rangle + \lambda \langle \mathbf{c}, \mathbf{x_1} \rangle = (1 -\lambda) f^* + \lambda f^* = f^* \;,
\]
sicché anche ogni $mathbf(x)_lambda$ è di ottimo per $f$.
Per il secondo punto non so, perché non mi ricordo la definizione di s.b.a… Però credo sia sufficientemente vero.
Per il resto, butta le slides nel ces… nel dimenticatoio e prendi un testo decente.
Non si studia mai dalle slides, che servono solo come promemoria degli argomenti toccati durante il corso.
Grazie mille, sei stato gentilissimo!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo