Un método más rápido para resolver los problemas de l.p.p.

Question

La siguiente pregunta se formuló en un examen:
Considera el problema:
Maximizar $2y_1+3y_2+5y_3+4y_4$
con sujeción a
$y_1+y_2\leq 1,$ $y_2+y_3\leq 1,$
$y_4+y_1\leq 1,$ $y_3+y_4\leq 1$ y $y_i\geq 0$ para i=1,2,3,4.
Entonces el valor óptimo es
1. igual a 8
2. entre 8 y 9
3. mayor o igual a 7
4. menor o igual a 7
He resuelto el problema anterior por el método simplex habitual y he obtenido que el valor óptimo es 7. Ahora, sólo tengo curiosidad por saber si hay algún otro método más sencillo y rápido para resolver este tipo de problemas en las oposiciones en las que el tiempo es una limitación.
Gracias de antemano.

Answer 1

Podrías dejar que $z_1=y_1+y_2$ , $z_2=y_2+y_3$ y $z_3=y_3+y_4$ . Entonces el problema se convierte en:

Minimizar $2z_1+z_2+4z_3$ con sujeción a $z_1\leq 1$ , $z_2\leq 1$ , $z_3\leq 1$ , $z_1-z_2+z_3\leq 1$ ,

Entonces, por la inspección $z_1=z_2=z_3=1$ satisface las restricciones y alcanza el máximo.

Answer 2

La respuesta es $D$ .

Exprésalo como: $$2y_1+3y_2+5y_3+4y_4=2(\underbrace{y_1+y_2}_{\le 1})+(\underbrace{y_2+y_3}_{\le 1})+4(\underbrace{y_3+y_4}_{\le 1})\le7.$$ La igualdad se produce cuando $(y_1,y_2,y_3,y_4)=(1,0,1,0); (\frac12,\frac12,\frac12,\frac12);(0,1,0,1); etc.$