ENTENDER ANTES DE CALCULAR

Programación lineal: elegir sin saltarse los límites

Con 12 kg de arroz puedes preparar muchos repartos de paquetes. Primero se descartan los que no caben; después se compara cuál da más beneficio o menos coste.

La idea del bloque y los conocimientos previos
Empieza por esta idea

Cada punto (x,y)(x,y) del dibujo es un reparto de dos cantidades. Las restricciones marcan qué puntos están permitidos y la función objetivo dice cuál de ellos es el mejor.

Casos especiales: un lado entero óptimo o ningún máximo

¿El mejor punto es siempre único? No. Si dos vértices vecinos dan el mismo valor máximo, todos los puntos del segmento que los une también lo dan, y entonces el lado entero es óptimo.

Con F=x+yF=x+y y la restricción x+y≤6,x+y\le6\text{,} ningún punto supera 6. Si (2,4)(2,4) y (4,2)(4,2) son factibles, ambos dan 6, y el segmento entre ellos queda sobre la recta x+y=6:x+y=6\text{:} todos sus puntos dan 6.

El empate también aparece cuando el objetivo es un múltiplo del consumo de un recurso. Sean xx e yy las unidades de dos productos: el primero deja 18 € y gasta 3 horas, el segundo deja 6 € y gasta 1 hora, y hay 54 horas disponibles. Cada hora rinde 6 € con los dos, y F=18x+6y=6(3x+y).F=18x+6y=6(3x+y)\text{.} Con 3x+y≤54,3x+y\le54\text{,} FF no pasa de 6⋅54=324,6\cdot54=324\text{,} y lo alcanzan todos los puntos del lado 3x+y=543x+y=54 que cumplan las demás condiciones.

Una zona puede continuar sin límite en alguna dirección. Por ejemplo, x≥0x\ge0 y 0≤y≤20\le y\le2 permiten dejar y=2y=2 y elegir xx cada vez mayor. Llamamos tt al valor elegido para x:x\text{:} los puntos (t,2)(t,2) cumplen las restricciones para todo t≥0.t\ge0\text{.} En ellos, F=x+y=t+2F=x+y=t+2 crece sin tope: no existe máximo.

Una zona sin límite sí puede tener mínimo cuando los precios son positivos. Con C=2x+3y,C=2x+3y\text{,} x≥1,x\ge1\text{,} y≥1y\ge1 y x+y≥5x+y\ge5 las esquinas son (4,1),(4,1)\text{,} con C=2⋅4+3⋅1=11,C=2\cdot4+3\cdot1=11\text{,} y (1,4),(1,4)\text{,} con C=2⋅1+3⋅4=14.C=2\cdot1+3\cdot4=14\text{.} La zona sigue sin límite hacia arriba y hacia la derecha. Para estar seguros de que ningún otro punto cuesta menos, separamos 3y=2y+y:3y=2y+y\text{:} C=2x+2y+y=2(x+y)+y.C=2x+2y+y=2(x+y)+y\text{.} Como x+y≥5x+y\ge5 e y≥1,y\ge1\text{,} resulta C≥2⋅5+1=11.C\ge2\cdot5+1=11\text{.} Nadie baja de 1111 y (4,1)(4,1) llega a ese coste: el mínimo es 1111 en (4,1).(4,1)\text{.}

Cómo empezar tu ejercicio

Cuándo usar esta idea: Dos vértices empatan en el valor óptimo, o la región factible no queda encerrada.

Mira si los vértices óptimos comparten un lado. Si la región sigue sin límite, calcula cómo cambia el objetivo al avanzar por ella.

Un ejemplo, paso a paso

Hoy la plancha solo tiene 6 huecos, hay ingredientes para 4 bocadillos de cada tipo (xx de un tipo e yy del otro) y cada uno deja 1 €. Maximiza F=x+yF=x+y con 0≤x≤4,0\le x\le4\text{,} 0≤y≤40\le y\le4 y x+y≤6.x+y\le6\text{.} En esta primera parte permitimos cantidades fraccionarias: es el modelo continuo.

Un lado completo alcanza el máximoRegión factible del primer cuadrante con x e y entre cero y cuatro y x más y como máximo seis. El segmento que une dos cuatro con cuatro dos está resaltado: todos sus puntos suman seis.xy022446688(0,0)(4,0)(4,2)(2,4)(0,4)Máximo: todo el lado resaltado
El lado grueso une (2,4)(2,4) y (4,2).(4,2)\text{.} En cada uno de sus puntos se cumple x+y=6:x+y=6\text{:} todo ese segmento alcanza el mismo máximo de F=x+y.F=x+y\text{.}
Tres puntos del segmento: el valor de FF no cambia.
ttPunto (t,6−t)(t,6-t)F=x+yF=x+y
2(2,4)(2,4)6
3(3,3)(3,3)6
4(4,2)(4,2)6
  1. Con la tabla de vértices, que son (0,0),(0,0)\text{,} (4,0),(4,0)\text{,} (4,2),(4,2)\text{,} (2,4)(2,4) y (0,4),(0,4)\text{,} F=x+yF=x+y vale 0, 4, 6, 6, 4.0,\ 4,\ 6,\ 6,\ 4\text{.} El máximo, 6, se repite en dos vértices vecinos, (4,2)(4,2) y (2,4):(2,4)\text{:} todo el lado que los une es óptimo. Lo comprobamos con una letra.
  2. Por la restricción x+y≤6,x+y\le6\text{,} siempre es F=x+y≤6.F=x+y\le6\text{.} Si algún punto factible llega a 6, ese es el máximo.
  3. Los puntos con F=6F=6 están en la recta x+y=6.x+y=6\text{.} Restamos xx en ambos lados: y=6−x.y=6-x\text{.} Llamamos tt al valor elegido para x:x\text{:} un punto de esa recta es (t,6−t).(t,6-t)\text{.}
  4. Imponemos las cotas. De y≤4y\le4 sale 6−t≤4;6-t\le4\text{;} restamos 6 en ambos miembros, −t≤−2,-t\le-2\text{,} y multiplicamos por −1-1 (la desigualdad se invierte): t≥2.t\ge2\text{.} De x≤4x\le4 sale t≤4.t\le4\text{.} Con tt entre 2 y 4, y=6−ty=6-t queda entre 2 y 4 y también cumple y≥0.y\ge0\text{.}
  5. Los extremos del segmento son (2,4)(2,4) y (4,2),(4,2)\text{,} que son vértices de la región.
  6. En cualquier punto del segmento, F=t+(6−t)=6.F=t+(6-t)=6\text{.} Todos empatan en el máximo.
  7. Si los bocadillos deben ser enteros, los puntos del segmento con xx e yy enteros son tres: (2,4),(2,4)\text{,} (3,3)(3,3) y (4,2),(4,2)\text{,} los de la tabla. Los tres dan F=6,F=6\text{,} pero ya no hay infinitos repartos óptimos.

Lo que obtenemos: En el modelo continuo, hay infinitos óptimos: todo el segmento (t,6−t),(t,6-t)\text{,} 2≤t≤4,2\le t\le4\text{,} da F=6.F=6\text{.} Con bocadillos enteros, los tres repartos de la tabla alcanzan ese mismo máximo.

Ojo con este error: Comparar solo los vértices cuando la región no está acotada: el objetivo puede seguir creciendo (o bajando) más allá de ellos. Y si dos vértices empatan, no des solo uno ni digas «hay dos soluciones»: son infinitas, todo el lado que los une.

Para ir más allá

Vocabulario: una restricción es cada condición del enunciado; un tope (o cota) es una restricción que limita una cantidad por arriba, como y≤2.y\le2\text{.} Una región acotada queda encerrada en un polígono; cerrada significa que incluye su borde.

Mínimo en una zona sin límite con precios positivos: al alejarse el coste solo sube, así que el mínimo existe y está en una esquina. Calcula las esquinas, acota el coste como arriba (C=2(x+y)+y)C=2(x+y)+y\text{)} y quédate con la menor. Si piden un máximo y FF crece sin tope, responde «no existe máximo porque FF crece sin tope».

Hacia dónde se alarga la zona. Si ninguna condición limita yy por arriba (como en 2≤x≤8,2\le x\le8\text{,} y≥0),y\ge0\text{),} se alarga hacia arriba; sin cota por la izquierda, hacia la izquierda, y así con cada sentido. Desde una esquina avanza t≥0t\ge0 en ese sentido y mira cómo cambia F:F\text{:} si mejora sin parar, no hay máximo (o mínimo); si empeora, la esquina sigue ganando.

Dos salidas. En x,y≥0,x,y\ge0\text{,} x−y≤1x-y\le1 se puede subir por el eje y,y\text{,} puntos (0,t),(0,t)\text{,} o por la diagonal y=x,y=x\text{,} puntos (t,t);(t,t)\text{;} ir solo a la derecha no vale, porque x−yx-y superaría 1. Hay que mirar las dos: con F=−6x−4yF=-6x-4y vale −4t-4t y −10t,-10t\text{,} baja sin tope y no hay mínimo.

Planes enteros sobre un lado óptimo. Si (1,10)(1,10) y (5,4)(5,4) dan el mismo máximo de F=3x+2yF=3x+2y (F=23),F=23\text{),} de uno a otro xx cambia 44 e yy cambia −6.-6\text{.} El máximo común divisor, 2,2\text{,} es el mayor número de saltos iguales y enteros: cada salto es (2,−3).(2,-3)\text{.} Los planes son (1,10),(1,10)\text{,} (3,7)(3,7) y (5,4):(5,4)\text{:} 2 saltos y 3 planes, porque se cuenta también el de partida.

Valor de kk que da un lado óptimo. Para que F=12x+kyF=12x+ky valga lo mismo en todo el lado 4x+3y=27,4x+3y=27\text{,} sus coeficientes deben ser proporcionales a los de la recta: 12k=43.\dfrac{12}{k}=\dfrac43\text{.} Multiplicamos en cruz: 4k=12⋅3=36,4k=12\cdot3=36\text{,} luego k=9.k=9\text{.} Comprobación: 12x+9y=3 (4x+3y)=3⋅27=8112x+9y=3\,(4x+3y)=3\cdot27=81 en todo el lado.

Ahora prueba la idea

En la misma región (0≤x≤4,0\le x\le4\text{,} 0≤y≤4,0\le y\le4\text{,} x+y≤6),x+y\le6\text{),} ¿alcanza H=2x+2yH=2x+2y su máximo en un solo punto?

Ver la respuesta y el porqué

No: lo alcanza en todo el lado que une (4,2)(4,2) y (2,4).(2,4)\text{.}

H=2(x+y)≤12,H=2(x+y)\le12\text{,} y vale 12 justo cuando x+y=6.x+y=6\text{.} Los vértices (4,2)(4,2) y (2,4)(2,4) dan los dos 12: empatan, y todo el lado que los une es óptimo. Con G=2x+y,G=2x+y\text{,} en cambio, los vértices dan 0, 8, 10, 8, 40,\ 8,\ 10,\ 8,\ 4 y el máximo 10 está solo en (4,2).(4,2)\text{.}

Ver los otros bloques