Programación Lineal (2D)

PL de 2 variables: región factible, optimización de vértices

Ejemplo resuelto — Programación Lineal (2D)

Maximizar	3x + 2y

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Una región factible no es la promesa de una respuesta 🖖

La regla de las esquinas tiene una condición previa fácil de saltarse: el óptimo tiene que existir. Carga el ejemplo no acotado —maximizar 2x + y sujeto a x ≥ 0, y ≥ 0, x + y ≥ 2— y la región factible es perfectamente no vacía, pero ninguna esquina es la mejor, porque puedes caminar al noreste indefinidamente y seguir mejorando. Por eso esta herramienta devuelve uno de tres veredictos y no uno solo: óptimo, no factible o no acotado. Llega al tercero comprobando si hay una dirección de recesión que mejore, no por no encontrar un vértice. Cambia ese mismo ejemplo a minimizar y aparece de inmediato una respuesta finita en (0, 2). Factibilidad y resolubilidad son preguntas distintas.

Las mejores respuestas se esconden en las esquinas 🖖

En términos sencillos, estás haciendo malabares con recursos limitados bajo varias reglas a la vez, y cada desigualdad recorta una parte del plano. Donde todas las reglas se solapan está la región factible, y cada punto dentro de ella es un plan válido. Como una función objetivo lineal siempre mejora en una dirección, la mejor solución cae en un vértice donde se cruzan las restricciones. La conclusión: para optimizar nunca pruebas todos los puntos, solo el puñado de vértices.

Cómo un problema de dieta anticipó el símplex 🖖

En 1945 el economista George Stigler estudió la dieta más barata que cubría todas las necesidades nutricionales, un problema lineal con 77 alimentos. Sin un algoritmo, hizo una estimación astuta y obtuvo unos $39.93 al año (precios de 1939). Cuando el método símplex de Dantzig lo resolvió con exactitud en 1947, el mínimo real fue $39.69: la estimación a mano de Stigler solo se desvió unos 24 centavos al año. Así, la economía árida se volvió uno de los casos fundacionales de la programación lineal.

PROGRAMACIÓN LINEAL — POR QUÉ SOLO SE MIRAN LAS ESQUINAS

¿En qué caso de programación lineal está?

Todo programa lineal plantea lo mismo: empujar un objetivo rectilíneo lo más lejos posible dentro de una región vallada por restricciones rectilíneas. Como ambos son rectos, el mejor punto solo puede ser una esquina, y por eso el método consiste en listar las esquinas y compararlas. El caso depende de si esa región encierra al objetivo y de si la esquina que entrega es un número realmente utilizable.

Región acotada: el óptimo cae en una esquina z = 10 → (2, 2)

La mejor esquina es fraccionaria, y eso es otro problema z = 24 → (8/3, 8/3)

Región no acotada con respuesta acotada min z = 13

Sin óptimo finito, y mirar las esquinas no se lo dirá z → ∞

Región acotada: el óptimo cae en una esquina

Lo que sabe: Un objetivo que maximizar y suficientes restricciones ≤ para cerrar la región. El conjunto factible es un polígono.

Qué comprobar: z = 10 → (2, 2)

Ejemplo resuelto: Maximizar 3x + 2y sujeto a x + y ≤ 4, x ≤ 2, y ≤ 3. Las esquinas son (0,0), (2,0), (2,2), (1,3), (0,3), y z = 10 en (2,2) las supera a todas.

Abrir este caso: Problema de la dieta

Región acotada: el óptimo cae en una esquina. La recta objetivo se desliza hacia arriba y a la derecha hasta tocar el polígono en una sola esquina. Un objetivo que maximizar y suficientes restricciones ≤ para cerrar la región. El conjunto factible es un polígono. — La recta objetivo se desliza hacia arriba y a la derecha hasta tocar el polígono en una sola esquina.

La mejor esquina es fraccionaria, y eso es otro problema

Lo que sabe: Otra vez una región acotada, pero la esquina que elige el objetivo no cae en números enteros.

Qué comprobar: z = 24 → (8/3, 8/3)

Ejemplo resuelto: Maximizar 5x + 4y sujeto a 2x + y ≤ 8, x + 2y ≤ 8, x ≤ 4, y ≤ 4. El óptimo es z = 24 en (8/3, 8/3), es decir unos (2,67, 2,67).

Abrir este caso: Producción de fábrica

La mejor esquina es fraccionaria, y eso es otro problema. Las dos restricciones activas se cruzan lejos de las líneas de la cuadrícula, así que la mejor esquina tiene coordenadas fraccionarias. Otra vez una región acotada, pero la esquina que elige el objetivo no cae en números enteros. — Las dos restricciones activas se cruzan lejos de las líneas de la cuadrícula, así que la mejor esquina tiene coordenadas fraccionarias.

Región no acotada con respuesta acotada

Lo que sabe: Minimizar con restricciones ≥. La región factible se va al infinito, pero el objetivo aún tiene un suelo.

Qué comprobar: min z = 13

Ejemplo resuelto: Minimizar 2x + 3y sujeto a x + y ≥ 6, x ≥ 2, y ≥ 1. La región es infinita y aun así el mínimo es z = 13 en (5,1).

Abrir este caso: Costo mínimo

Región no acotada con respuesta acotada. La región se aleja del origen sin límite, pero el objetivo se minimiza en una esquina cercana a él. Minimizar con restricciones ≥. La región factible se va al infinito, pero el objetivo aún tiene un suelo. — La región se aleja del origen sin límite, pero el objetivo se minimiza en una esquina cercana a él.

Sin óptimo finito, y mirar las esquinas no se lo dirá

Lo que sabe: El objetivo mejora en una dirección que las restricciones nunca bloquean. No hay mejor punto.

Qué comprobar: z → ∞

Ejemplo resuelto: Maximizar 2x + y sujeto a x + y ≥ 2, x ≥ 0, y ≥ 0. Avance por x creciente indefinidamente y el objetivo crece sin fin; la respuesta es no acotada.

Abrir este caso: No acotado

Sin óptimo finito, y mirar las esquinas no se lo dirá. La región sombreada está abierta hacia arriba y a la derecha, y el objetivo sigue mejorando por ahí sin fin. El objetivo mejora en una dirección que las restricciones nunca bloquean. No hay mejor punto. — La región sombreada está abierta hacia arriba y a la derecha, y el objetivo sigue mejorando por ahí sin fin.

Referencias (3)

The diet problem in the history block: Stigler, G. J. (1945). "The Cost of Subsistence." Journal of Farm Economics 27(2), 303.
Simplex, and the vertex theorem it relies on: Dantzig, G. B. Linear Programming and Extensions. Princeton University Press, 1963.
Unboundedness and recession directions, the tool’s third verdict: Boyd, S. & Vandenberghe, L. Convex Optimization. Cambridge University Press, 2004, §2.5. ISBN 978-0-521-83378-3.

Problema resuelto al detalle

El problema de la dieta para maximizar Z = 3x + 2y 5 pasos
¿Qué vértice gana y cuánto vale el vértice adyacente? Este es Problema de la dieta: maximizar Z = 3x + 2y sujeto a x + y ≤ 4, x ≤ 2 e y ≤ 3, con x e y ambos al menos 0.
1. Tome dos puntos factibles cualesquiera y recorra el segmento rectilíneo que los une. La función objetivo lineal a lo largo de ese recorrido es una media ponderada de los valores de sus dos extremos, y una media ponderada nunca supera al extremo mayor. Así pues, ningún punto situado estrictamente entre otros dos puede ser el óptimo único, y al aplicar este razonamiento en todas las direcciones, el óptimo queda relegado a un vértice.
  
  $Z (λ A + (1 - λ) B) = λ Z (A) + (1 - λ) Z (B) \leq max {Z (A), Z (B)}, 0 \leq λ \leq 1$
2. Un vértice es el punto de intersección de dos rectas frontera, de modo que los candidatos se obtienen tomando las cinco rectas de dos en dos. Hay diez pares, dos de ellos paralelos, y solo cinco de los ocho restantes satisfacen las restricciones de las que no proceden: x + y = 4 se corta con x = 0 en (0, 4), lo cual incumple y ≤ 3.
  
  ${x + y = 4, x = 2} \Rightarrow (2, 2); {x + y = 4, y = 3} \Rightarrow (1, 3); (0, 0), (2, 0), (0, 3)$
3. Cinco evaluaciones aritméticas y una comparación bastan para concluir la búsqueda. No queda ningún interior que probar ni ninguna arista por recorrer.
  
  $Z = 3 x + 2 y : 0, 6, 10, 9, 6 ⟹ (x^{*}, y^{*}) = (2, 2), Z^{*} = 10$
4. En el vértice ganador, x + y = 4 y x = 2 son ambas restricciones activas, mientras que y = 2 se sitúa a una unidad entera por debajo de su límite de 3. Una restricción con holgura no limita nada, de modo que relajarla no cambia nada; vale la pena volver a resolver las otras dos añadiendo una unidad a cada una.
  
  $b_{1} : 4 \to 5 \Rightarrow (2, 3), Z = 12, y_{1} = 2; b_{2} : 2 \to 3 \Rightarrow (3, 1), Z = 11, y_{2} = 1; y^{*} = 2 < 3 \Rightarrow y_{3} = 0$
5. Pondere cada uno de esos tres precios por la cantidad de recurso con la que contaba el problema.
  
  $b_{1} y_{1} + b_{2} y_{2} + b_{3} y_{3} = 4 (2) + 2 (1) + 3 (0) = 10 = Z^{*}$
Respuesta

La herramienta muestra x* = 2, y* = 2 y Z* = 10, el tercero de los cinco valores en los vértices. Los números del paso 4 —2, 1 y 0— son los precios sombra, y responden a una pregunta que el gráfico no puede contestar: una unidad adicional del presupuesto de x + y vale el doble que una unidad adicional de x, y una unidad adicional de y no vale absolutamente nada. El paso 5 es la dualidad fuerte, y no es una casualidad de estos datos; los precios ponderados por las disponibilidades siempre reproducen el óptimo, que es precisamente lo que los convierte en precios. Un precio sombra también tiene fecha de caducidad. El presupuesto de x + y paga 2 por unidad solo hasta llegar a 5, donde el vértice alcanza (2, 3), las otras dos restricciones se vuelven activas y Z se estanca en 12; más allá de ese punto, el precio es 0 y cada unidad extra que se adquiera se desperdicia.

$max {c^{⊤} x : A x \leq b, x \geq 0} = min {b^{⊤} y : A^{⊤} y \geq c, y \geq 0} = 10$

Por el equipo de 42Math · Actualizado 2026-08-17

Contrastado con fuentes publicadas. Se agradecen correcciones. Política editorial · Correcciones

Todas las lecciones de Estadística y Finanzas →

Problemas de ejemplo

Problema de la dieta - Maximización acotada clásica: el óptimo se alcanza en un vértice factible.
Producción de fábrica - Las restricciones de capacidad que se cruzan crean una región factible poligonal.
Costo mínimo - La minimización con restricciones acotadas inferiormente elige el vértice factible más cercano al origen en la dirección de la función objetivo.
No acotado - La región factible puede ser no acotada, por lo que el objetivo puede no tener un óptimo finito.