PL intera

juvedelpiero
Salve ragazzi, sto preparandomi per un esame ma non riesco a capire questo esercizio qualcuno di buon cuore potrebbe aiutarmi? L'esercizio è:

"Si consideri il seguente problema di programmazione intera, P:
\(\displaystyle max(1,0)\vec x \)
\(\displaystyle sbj \)
\(\displaystyle \begin{bmatrix}-1 & 1\\1 & -1\\1 & 0\end{bmatrix} \vec x <= \begin{bmatrix}\frac 12\\ \frac 12\\ 2+ \frac 12\end{bmatrix}\)
\(\displaystyle \vec x >= \vec 0, \vec x\) intero

Si dia una formulazione del problema PL che cattura l'inviluppo convesso di P." :?

Risposte
Riky19931
Sei per caso riuscito a risolvere? Anche io avrei bisogno di capire come svolgere questo tipo di esercizi

Riky19931
Nessuno sa risolverlo? Io ho svolto il simplesso sul problema corrispondente di programmazione lineare ma poi non sò più come procedere

juvedelpiero
Che risultati ottieni con il simplesso?

Riky19931
\(\displaystyle max Z = 5/2 - x_5 \)
sbj \(\displaystyle x_1 + x_5 <= 5/2 \)
\(\displaystyle x_2 - x_4 +x_5 <= 2 \)
\(\displaystyle x_3 + x_4 <= 1 \)

Da qui dovremmo trovare un nuovo vincolo da aggiungere al problema di programmazione lineare iniziale, ma non riesco a capire come aggiungere il vincolo. Prendendo ad esempio quello della prima riga e ponendo \(\displaystyle x_1 + x_5 <= 2 \) (2 perché bisogna prendere la parte intera), ora bisognerebbe eliminare x5 in modo da avere x1 ed x2. Per eliminarli prendo il vincolo iniziale che è 5/2 - x1 ma così facendo si annullano tutte le variabili, quindi non capisco come procedere

juvedelpiero
Prima di iniziare togli le frazioni al problema originale moltiplicando i vincoli per una costante in questo caso 2

Riky19931
Ma dici prima o dopo aver svolto il simplesso??

juvedelpiero
Prima di portare nella forma standard e quindi prima del simplesso

Riky19931
ok ora come vincolo da aggiungere mi viene x1 - 2x2 = -3. Nel secondo simplesso quali vincoli devo usare?

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.