"Casos especiales: solución única, múltiple, no acotada o infactible"
El kiosco de la escuela quiere ganar lo máximo posible vendiendo alfajores y sándwiches. Hasta ahora, en cada problema había un vértice claramente ganador. Pero a veces dos vértices empatan, o la región se abre sin fin y la ganancia no tiene tope, o las restricciones se contradicen y no se puede hacer nada. En este apartado aprendés a reconocer cada caso y, sobre todo, a explicarlo.
Región acotada y no acotada
Una región factible es acotada si podés encerrarla toda en un círculo (o un rectángulo) lo bastante grande. Es no acotada si se extiende indefinidamente en alguna dirección: contiene una semirrecta entera.
Criterio práctico: si las restricciones son del tipo $\leq$ y todas las variables son $\geq 0$, la región suele ser acotada. Si alguna desigualdad $\geq$ deja "libre" una dirección, la región puede abrirse sin límite.
Una región acotada siempre tiene máximo y mínimo, y se alcanzan en vértices. En una no acotada, tenés que ser más cuidadoso.
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 única o múltiple
En el caso habitual, el valor máximo (o mínimo) de $F$ se alcanza en un solo vértice: es la solución única. Pasa cuando la dirección de las rectas de nivel de $F$ no coincide con la de ningún lado del polígono.
Ahora el caso especial. Las rectas de nivel $ax+by=k$ son todas paralelas. Si al "deslizarlas" hacia el óptimo la última recta coincide con un lado de la región, entonces todo el lado 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.
Reconocerlo por los coeficientes
No hace falta dibujar para sospechar una solución múltiple: si los coeficientes de $F$ son proporcionales a los de una restricción, esa recta es paralela a las de nivel. Si además ese lado es el último que "toca" la región en la dirección óptima, hay infinitas soluciones.
Por ejemplo, $F=3x+6y$ es proporcional a $x+2y\leq 10$ (porque $3x+6y=3(x+2y)$). Si esa restricción forma parte del borde en la dirección donde $F$ crece, el máximo es $30$ en todo ese lado.
Para describir el segmento óptimo, escribí sus extremos (los dos vértices) y, si se pide, dá puntos intermedios: con coordenadas enteras, o el punto medio $\left(\frac{x_1+x_2}{2};\frac{y_1+y_2}{2}\right)$.
Un festival a beneficio vende abonos generales ($x$) y abonos con zona de acampe ($y$). Por el contrato con el predio debe cumplirse $2x + 3y \leq 120$ (unidades de…
Un festival a beneficio vende abonos generales ($x$) y abonos con zona de acampe ($y$). Por el contrato con el predio debe cumplirse $2x + 3y \leq 120$ (unidades de espacio) y $x + y \leq 50$ (capacidad), 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) = 20\,000x + 30\,000y$ pesos.
-
a) Planteá el sistema completo y hallá los vértices de la región factible.
-
b) Calculá la recaudación máxima.
-
c) Comprobá que el máximo se alcanza en dos vértices a la vez y explicá 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.
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
En una región no acotada, $F$ puede crecer (o decrecer) sin parar en la dirección en que la región se abre. Entonces no existe máximo (o mínimo): por lejos que vayas, siempre hay otro punto factible con un valor mayor.
Para justificar que no hay máximo (o mínimo), exhibí una familia de puntos factibles donde $F$ tome valores tan grandes (o tan chicos) como quieras. Por ejemplo, con $F=x-3y$ en $x\geq 0$, $y\geq 0$, $x+y\geq 3$: los puntos $(t; 0)$ con $t\geq 3$ son factibles y dan $F=t$, que crece sin tope (no hay máximo). Los puntos $(0; t)$ con $t\geq 3$ son factibles y dan $F=-3t$, que decrece sin tope (tampoco hay mínimo).
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
Si las restricciones se contradicen, ningún punto las cumple a la vez: la región factible es el conjunto vacío. En programación lineal se dice que el problema es infactible (no tiene solución factible).
En problemas con contexto, la infactibilidad suele aparecer cuando los pedidos mínimos superan los recursos. Por ejemplo, una panadería debe entregar al menos $30$ docenas de facturas ($x$) y al menos $20$ de medialunas ($y$), pero el horno dispone de $50$ horas y cada docena de facturas usa $2$ horas y cada una de medialunas, $1$: la restricción es $2x+y\leq 50$. Con el mínimo exigido se necesitarían $2\cdot 30+20=80>50$ horas: es imposible. Para arreglarlo basta cambiar un dato, por ejemplo subir las horas disponibles a $80$ o bajar el pedido de facturas.
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.
Discutir según un parámetro
A veces un número del problema es una letra. Hay que ver cómo cambia el desenlace según su valor. El método es siempre el mismo: hallar los vértices, evaluar $F$ en ellos y comparar según el parámetro.
Los valores de $a$ donde cambia el vértice óptimo son justo los que producen soluciones múltiples: en ellos la recta de nivel es paralela a un lado.
Con un parámetro en una restricción, el razonamiento es geométrico. Por ejemplo, para $x\geq 0$, $y\geq 0$, $x+y\geq 4$ y $x+2y\leq k$, buscá el menor valor que toma $x+2y$ en la parte que cumple las otras tres condiciones: es $4$, en $(4; 0)$. Entonces la región es vacía si $k<4$, es un único punto si $k=4$ y tiene área positiva si $k>4$.
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.
Volvé al kiosco del principio: ahora sabés qué te puede pasar. Puede haber un vértice ganador, varios puntos que dan la misma ganancia, ninguna ganancia máxima si la región se abre sin tope, o ninguna combinación posible si los pedidos superan los recursos.