Casos especiales: solución única, múltiple, no acotada o infactible
Camila vende polos y casacas en Gamarra y quiere saber cuánto producir para ganar lo máximo posible. Resuelve el problema tres veces con datos distintos. La primera le sale una sola respuesta, la segunda le salen dos vértices «empatados» y la tercera no le sale ninguna. ¿Se equivocó en las cuentas? Quizá no: en programación lineal estos desenlaces son normales y en la pre se pregunta justo por ellos. Al final de la página vuelves a Camila.
Solución única: el caso habitual
Cuando la región factible es acotada (cerrada, sin «escaparse» hacia el infinito), la función objetivo $F$ siempre alcanza un máximo y un mínimo, y lo hace en algún vértice. Lo más frecuente es que solo un vértice dé el mejor valor.
¿Cómo reconocer si una región es acotada? Pregúntate si cabe dentro de una circunferencia lo bastante grande. Un polígono cerrado, con todos sus lados, sí cabe. Una región con un «borde abierto» que sigue sin límite, no.
La figura muestra dos regiones factibles: la del panel A y la del panel B, como se muestra en la figura. Indica cuál de ellas es acotada y cuál no, explicando el…
La figura muestra dos regiones factibles: la del panel A y la del panel B, como se muestra en la figura.
Indica cuál de ellas es acotada y cuál no, explicando el criterio que has usado para decidirlo.
Solución múltiple: un lado entero es óptimo
En la figura se ha representado una región factible y una recta de nivel de la función objetivo $F(x, y) = 2x + y$ correspondiente al valor $8$, como se muestra en la…
En la figura se ha representado una región factible y una recta de nivel de la función objetivo $F(x, y) = 2x + y$ correspondiente al valor $8$, como se muestra en la figura.
-
a) Explica qué particularidad presenta la posición de esa recta respecto de la región.
-
b) Indica el valor máximo de $F$ y da dos soluciones óptimas distintas.
Maximiza la función objetivo $F(x, y) = 2x + 4y$ sujeta a $x \geq 0$, $y \geq 0$, $x + 2y \leq 8$ y $x + y \leq 5$. a) Halla los vértices de la región factible y evalúa…
Maximiza la función objetivo $F(x, y) = 2x + 4y$ sujeta a $x \geq 0$, $y \geq 0$, $x + 2y \leq 8$ y $x + y \leq 5$.
-
a) Halla los vértices de la región factible y evalúa $F$ en ellos.
-
b) Observarás que el valor máximo se repite en dos vértices: explica qué significa esto y escribe la expresión de todos los puntos óptimos como segmento.
-
c) Da dos soluciones óptimas de coordenadas enteras.
Demuestra que con las restricciones $x \geq 0$, $y \geq 0$, $x + y \leq 4$ y $x + 2y \leq 5$, la función objetivo $F(x, y) = x + 2y$ alcanza su valor máximo en infinitos…
Demuestra que con las restricciones $x \geq 0$, $y \geq 0$, $x + y \leq 4$ y $x + 2y \leq 5$, la función objetivo $F(x, y) = x + 2y$ alcanza su valor máximo en infinitos puntos de la región factible.
-
a) Halla los vértices de la región y el valor máximo de $F$.
-
b) Identifica el segmento de puntos óptimos escribiendo sus extremos.
-
c) Da tres soluciones óptimas distintas, dos de ellas de coordenadas enteras.
Región no acotada: puede no haber óptimo
Verdadero o falso, razonando la respuesta: «Si la región factible de un problema de programación lineal no es acotada, el problema nunca tiene solución óptima». Ilustra…
Verdadero o falso, razonando la respuesta: «Si la región factible de un problema de programación lineal no es acotada, el problema nunca tiene solución óptima». Ilustra tu razonamiento con el ejemplo de $F(x, y) = x + y$ en la región $x \geq 0$, $y \geq 0$, $x + y \geq 2$.
Sea la región definida por $x \geq 0$, $y \geq 0$, $x + y \geq 3$ y $3x + y \geq 5$. a) Comprueba que no es acotada y halla sus vértices. b) Estudia si la función…
Sea la región definida por $x \geq 0$, $y \geq 0$, $x + y \geq 3$ y $3x + y \geq 5$.
-
a) Comprueba que no es acotada y halla sus vértices.
-
b) Estudia si la función objetivo $F(x, y) = 3x + 2y$ alcanza un máximo en la región.
-
c) Estudia si alcanza un mínimo y, en caso afirmativo, calcúlalo.
Sea la región no acotada definida por $x \geq 0$, $y \geq 0$, $x + y \geq 2$ y $2x + y \geq 2$, y la función objetivo $F(x, y) = x - 2y$. a) Halla los vértices de la…
Sea la región no acotada definida por $x \geq 0$, $y \geq 0$, $x + y \geq 2$ y $2x + y \geq 2$, y la función objetivo $F(x, y) = x - 2y$.
-
a) Halla los vértices de la región.
-
b) Exhibe una familia de puntos factibles que demuestre que $F$ no alcanza ningún máximo.
-
c) Exhibe otra familia de puntos factibles que demuestre que $F$ tampoco alcanza ningún mínimo.
-
d) ¿Qué condición sobre los coeficientes de la función objetivo y la dirección en que crece la región explica este comportamiento?
Región infactible: el sistema no tiene solución
Representa las rectas $x + y = 2$ y $x + y = 5$ y justifica, a partir del dibujo, que el sistema formado por $x \geq 0$, $y \geq 0$, $x + y \leq 2$ y $x + y \geq 5$ no…
Representa las rectas $x + y = 2$ y $x + y = 5$ y justifica, a partir del dibujo, que el sistema formado por $x \geq 0$, $y \geq 0$, $x + y \leq 2$ y $x + y \geq 5$ no tiene ninguna solución. ¿Cómo se dice en programación lineal que la región factible es vacía?
Una pastelería recibe un encargo de al menos $50$ tartas y $40$ brazos de gitano para una semana. Cada tarta requiere $2$ horas de obrador y cada brazo, $1$ hora, y el…
Una pastelería recibe un encargo de al menos $50$ tartas y $40$ brazos de gitano para una semana. Cada tarta requiere $2$ horas de obrador y cada brazo, $1$ hora, y el obrador solo dispone de $60$ horas semanales.
-
a) Plantea el sistema de restricciones y demuestra que la región factible es vacía.
-
b) Propón una modificación de un único dato del enunciado que haga el problema factible, y compruébalo.
Problemas completos y con parámetro
En un problema completo recorres todos los pasos: planteas el sistema, hallas los vértices, evalúas $F$ y concluyes qué tipo de caso es. Cuando hay un parámetro, el caso depende de su valor y debes discutirlo.
Sea la región no acotada definida por $x \geq 0$, $y \geq 0$, $x + 2y \geq 4$ y $2x + y \geq 4$, y la función objetivo $F(x, y) = ax + 2y$ con $a > 0$. a) Halla los…
Sea la región no acotada definida por $x \geq 0$, $y \geq 0$, $x + 2y \geq 4$ y $2x + y \geq 4$, y la función objetivo $F(x, y) = ax + 2y$ con $a > 0$.
-
a) Halla los vértices de la región.
-
b) Evalúa $F$ en cada vértice.
-
c) Discute, según los valores de $a$, en qué punto se alcanza el mínimo de $F$, señalando los casos con solución múltiple.
Considera el sistema formado por $x \geq 0$, $y \geq 0$, $x + y \geq 6$ y $x + 2y \leq k$, donde $k$ es un parámetro real. a) Representa la situación para $k = 4$,…
Considera el sistema formado por $x \geq 0$, $y \geq 0$, $x + y \geq 6$ y $x + 2y \leq k$, donde $k$ es un parámetro real.
-
a) Representa la situación para $k = 4$, $k = 6$ y $k = 10$.
-
b) Determina para qué valores de $k$ la región factible es vacía, para cuáles consta de un único punto y para cuáles tiene área positiva.
Un festival benéfico vende abonos generales ($x$) y abonos con zona de campamento ($y$). Por el contrato con el recinto debe cumplirse $2x + 3y \leq 120$ (unidades de…
Un festival benéfico vende abonos generales ($x$) y abonos con zona de campamento ($y$). Por el contrato con el recinto debe cumplirse $2x + 3y \leq 120$ (unidades de espacio) y $x + y \leq 50$ (aforo), y la organización se compromete con el patrocinador a vender al menos $12$ abonos generales: $x \geq 12$. La recaudación es $F(x, y) = 80x + 120y$ soles.
-
a) Plantea el sistema completo y halla los vértices de la región factible.
-
b) Calcula la recaudación máxima.
-
c) Comprueba que el máximo se alcanza en dos vértices a la vez y explica qué particularidad tiene la función objetivo respecto de una de las restricciones.
-
d) Da tres combinaciones enteras distintas de abonos que produzcan la recaudación máxima.
Resumen
Vuelve al principio: Camila no se equivocó. Su primer problema tenía un único vértice óptimo, el segundo empataba dos vértices (todo un lado era óptimo) y el tercero tenía restricciones contradictorias (región vacía).