Provetta sulla PL

PROBLEMA 1:

$$\begin{array}{l} \max \mbox{\ }4x_1 +5x_2 -3x_3 -8x_4\\ \l... ... x_1, x_2, x_3, x_4 \geq 0 \end{array} \right. \end{array}$$

Considerare la soluzione x₁ = x₂ = 3 e x₃ = x₄ = 0. La soluzione proposta è ammissibile? È di base? È ottima?

PROBLEMA 2: Se un problema di PL in forma standard ha una soluzione ottima non di base allora.

$\Box$

È necessariamente ammissibile.

$\Box$

È necessariamente degenere ossia ha almeno una soluzione di base degenere.

$\Box$

Può essere illimitato.

$\Box$

Il duale è necessariamente ammissibile.

$\Box$

Il duale è necessariamente limitato.

$\Box$

Ha almeno una soluzione di base ottima.

$\Box$

Ha almeno due soluzioni di base ottime.

Argomentare sinteticamente ma efficacemente le risposte.

PROBLEMA 3: Costruire un problema di PL dove nè il primale nè il duale siano ammissibili.

PROBLEMA 4:

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

• Risolvere sia per via grafica che algebricamente.
• 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?
• Di quanto dovremmo alterare ciascun coefficiente nella funzione obiettivo (singolarmente) affinchè la soluzione non sia più ottima?

PROBLEMA 5(FACOLTATIVO): Si cosideri il gioco finito a due giocatori e somma zero Carta, forbice e sasso.

• Dare la matrice dei pagamenti.
• Dare la strategia mista ottima per il giocatore A e dimostrarne l'ottimalità.
• Mostrare che se A adotta la sua strategia mista ottima allora nessuna strategia di B risulta preferibile sulle altre.
• provare o dare un controesempio: la proprietà discussa al punto precedente è valida in generale per tutti i giochi finiti a due giocatori e somma zero.

PROBLEMA 6(FACOLTATIVO): Dato un sistema di diseguaglianze

$$\left\{ \begin{array}{rrrr} a_{1,1}x_1 \;+& \ldots \;+& a_{... ...& \ldots \;+& a_{1,n}x_n \;\leq & b_n \\ \end{array} \right.$$

dirò che esse implicano la diseguaglianza $c_1x_1 + \ldots + c_n x_n \leq z$se ogni $\bar{x}=(x_1,\ldots, x_n)\in {\rm I\!R}^n$che soddisfa l'insieme soddisfa anche la diseguaglianza $c_1x_1 + \ldots + c_n x_n \leq z$. Si consideri il problema di decidere se un dato sistema implichi o meno una data diseguaglianza.

• Impostare come un problema di PL.
• Se l'implicazione vale come posso dimostrarlo succintamente? Se essa non vale come posso dimostrarlo succintamente?
• Derivarne un teorema che caratterizzi (se e solo se) quando un insieme di diseguaglianze implichi una diseguaglianza.

In bocca al lupo.