Este temario corresponde en exclusiva a la especialidad de Matemáticas del Cuerpo de Profesores de Enseñanza Secundaria (código 590/512) — una de las aproximadamente 50 especialidades oficiales de este cuerpo. No cubre ninguna otra especialidad de Secundaria (Lengua Castellana y Literatura, Geografía e Historia, Física y Química, Biología y Geología, Inglés, Filosofía, Tecnología, Dibujo, Música...) ni los cuerpos de Maestros o de Profesores Técnicos de Formación Profesional, que tienen temarios propios y distintos, todavía no publicados en OpositaGratis. El cuestionario específico (Parte A) que se reproduce aquí es el fijado con carácter estatal por el entonces Ministerio de Educación y Ciencia, y sigue siendo, más de tres décadas después, el temario base que las distintas Administraciones educativas —las 17 comunidades autónomas más Ceuta y Melilla, cada una competente para convocar su propia oposición— citan y desarrollan en sus resoluciones de convocatoria anual, al no existir una versión posterior que lo haya derogado o sustituido con carácter general para esta especialidad. Cada convocatoria autonómica concreta puede añadir particularidades propias (requisitos lingüísticos en comunidades con lengua cooficial, la prueba de programación y unidad didáctica, u otras variaciones menores de redacción), que no están reflejadas en este índice.
El Tema 17 estudia la programación lineal, la rama de la optimización matemática que busca maximizar o minimizar una función objetivo lineal sujeta a restricciones expresadas mediante inecuaciones o ecuaciones lineales. El tema arranca del contenido tradicional de segundo de Bachillerato de Ciencias Sociales (su concreción depende del currículo vigente de cada comunidad) —resolución de sistemas de inecuaciones lineales con dos incógnitas, representación gráfica de la región factible y localización del óptimo en un vértice— y se completa con el fundamento teórico que justifica ese procedimiento (el teorema fundamental de la programación lineal, que garantiza que el óptimo se alcanza en un vértice del polígono o poliedro de soluciones), con el método símplex como generalización algorítmica a más de dos variables, y con las aplicaciones clásicas del problema del transporte y del problema de la mezcla o dieta.
Es un tema con una vertiente aplicada muy marcada: la programación lineal nació históricamente ligada a problemas logísticos y económicos reales (Dantzig desarrolló el método símplex para la planificación de recursos militares durante la Segunda Guerra Mundial) y sigue siendo hoy una herramienta de gestión de recursos escasos de uso universal en economía, ingeniería e investigación operativa. El candidato debe manejar con soltura tanto el procedimiento gráfico de resolución en dos variables (contenido de examen directo, replicable en el aula de Bachillerato) como los fundamentos geométricos y algorítmicos (convexidad, vértices, símplex, dualidad) que explican por qué ese procedimiento funciona y cómo se generaliza.
Una inecuación lineal con dos incógnitas x e y tiene la forma general ax+by≤c (o con cualquiera de los otros signos de desigualdad ≥, <, >), con a,b,c números reales y a,b no ambos nulos. A diferencia de una ecuación lineal, cuyo conjunto solución en el plano es una recta (objeto de dimensión 1), el conjunto solución de una inecuación lineal es un semiplano (región de dimensión 2), delimitado precisamente por la recta ax+by=c asociada, llamada recta frontera. Para determinar cuál de los dos semiplanos en que la recta frontera divide al plano es la solución de la inecuación, el procedimiento estándar consiste en tomar un punto de prueba que no pertenezca a la recta (habitualmente el origen (0,0), si la recta no pasa por él, por la sencillez de sustituir ceros) y comprobar si sus coordenadas satisfacen la desigualdad; si la satisfacen, el semiplano solución es el que contiene a ese punto, y en caso contrario es el opuesto. La recta frontera pertenece al conjunto solución cuando la desigualdad es no estricta (≤ o ≥), representándose entonces con trazo continuo, y queda excluida cuando es estricta (< o >), representándose con trazo discontinuo; esta distinción, de apariencia menor, es relevante en la práctica docente porque determina si los puntos exactamente sobre la frontera son o no soluciones admisibles del problema, cuestión que puede tener consecuencias de interpretación en un problema real de optimización.
Semiplanos y su representación gráfica
Cada inecuación lineal con dos incógnitas se representa gráficamente trazando primero su recta frontera asociada (igualando la inecuación a una ecuación) y sombreando después el semiplano correspondiente según el resultado del punto de prueba descrito en el apartado anterior. Cuando el problema plantea varias inecuaciones simultáneas, como ocurre en todo problema de programación lineal, cada una de ellas recorta un semiplano del plano, y el procedimiento gráfico consiste en representar todas las rectas frontera y sombrear, para cada inecuación, el semiplano solución correspondiente, de modo que la región del plano que queda sombreada por todas las inecuaciones a la vez (la intersección de todos los semiplanos) es el conjunto solución del sistema conjunto, denominado región o zona factible. Esta técnica de representación mediante superposición sucesiva de semiplanos es el procedimiento estándar en el Bachillerato de Ciencias Sociales, y su dominio operativo —trazar correctamente cada recta a partir de sus puntos de corte con los ejes, decidir el semiplano correcto y superponer con precisión gráfica todas las restricciones— es la habilidad instrumental de base sobre la que se construye todo el resto del procedimiento de resolución de un problema de programación lineal por el método gráfico.
Región factible como conjunto convexo
La región factible de un problema de programación lineal, definida como la intersección de un número finito de semiplanos (cada uno determinado por una restricción lineal), es siempre un conjunto convexo: un conjunto C es convexo si para cualesquiera dos puntos P,Q∈C, todo el segmento que los une está también contenido en C. La demostración de que la intersección de conjuntos convexos es convexa es inmediata: si P y Q pertenecen a la intersección, pertenecen a cada uno de los semiplanos por separado, y como cada semiplano es convexo (el segmento entre dos puntos que satisfacen una misma desigualdad lineal también la satisface, por la propia linealidad de la expresión ax+by), el segmento completo pertenece a cada semiplano y, por tanto, a la intersección de todos ellos. Esta propiedad de convexidad no es un detalle técnico accesorio, sino la razón geométrica profunda por la que el método gráfico de resolución funciona: es precisamente la convexidad de la región factible la que garantiza que la función objetivo lineal, al desplazarse paralelamente a sí misma, alcanza su valor óptimo en un vértice y no en un punto interior, resultado que se formaliza en el teorema fundamental de la programación lineal. Cuando la región factible es acotada (contenida en algún círculo de radio finito), se denomina polígono de soluciones (en dos variables) o poliedro de soluciones (en más variables); cuando no lo es, se dice que la región factible es no acotada, lo que puede dar lugar, según la orientación de la función objetivo, a problemas sin solución óptima finita.
Restricciones lineales del problema
Las restricciones de un problema de programación lineal son el conjunto de inecuaciones (y, en algunos casos, ecuaciones) lineales que expresan las limitaciones del problema real que se modela: disponibilidad limitada de recursos (materias primas, horas de trabajo, capital), requisitos mínimos de producción, capacidades máximas de almacenamiento o transporte, o cualquier otra condición que las variables de decisión deban satisfacer simultáneamente. El primer paso, y con frecuencia el más delicado, en la resolución de un problema real de programación lineal es precisamente la modelización: identificar correctamente cuáles son las variables de decisión (las incógnitas del problema, habitualmente cantidades a producir, comprar o transportar), traducir cada limitación del enunciado verbal a una inecuación lineal en esas variables, y comprobar que el conjunto de restricciones recoge fielmente todas las condiciones relevantes del problema, sin añadir restricciones espurias ni omitir ninguna relevante. Las restricciones deben ser, por definición del problema, lineales (de primer grado en las variables); si alguna relación del problema real fuera de naturaleza no lineal, el problema dejaría de pertenecer al ámbito de la programación lineal propiamente dicha y requeriría técnicas de programación no lineal, fuera del alcance de este tema. Cada restricción, geométricamente, recorta la región factible mediante el semiplano correspondiente, y el conjunto completo de restricciones (incluidas las de no negatividad de las variables) determina por completo la forma poligonal o poliédrica de esa región.
Función objetivo lineal
La función objetivo de un problema de programación lineal es la expresión lineal z=f(x,y)=px+qy (en el caso de dos variables de decisión) que se desea maximizar o minimizar, y cuyos coeficientes p y q representan típicamente un beneficio, un coste, un tiempo o cualquier otra magnitud que el problema busca optimizar por cada unidad de las variables de decisión. Geométricamente, para cada valor constante k que pueda tomar z, la ecuación px+qy=k representa una recta, llamada recta de nivel o isobeneficio (o isocoste, según el contexto), y todas las rectas de nivel correspondientes a distintos valores de k son paralelas entre sí, con la misma pendiente −p/q, variando únicamente en su ordenada en el origen; esta familia de rectas paralelas es la clave geométrica del método gráfico de resolución, que consiste en desplazar la recta de nivel en la dirección en la que z crece (para maximizar) o decrece (para minimizar) hasta el último punto en que sigue teniendo intersección no vacía con la región factible. El sentido de crecimiento de z se determina a partir del vector gradiente de la función objetivo, (p,q), que apunta en la dirección de máximo crecimiento de z, perpendicular a todas las rectas de nivel; comprender esta relación entre el gradiente y la dirección de desplazamiento óptimo de las rectas de nivel es lo que da fundamento geométrico riguroso al método gráfico más allá de su ejecución puramente mecánica.
Teorema fundamental de la programación lineal (óptimo en un vértice)
El teorema fundamental de la programación lineal establece que, si la región factible de un problema de programación lineal es un conjunto convexo y acotado no vacío, el valor óptimo (máximo o mínimo) de la función objetivo lineal se alcanza necesariamente en al menos uno de los vértices de esa región; si el óptimo se alcanza en dos vértices distintos, entonces se alcanza también en todo el segmento que los une (y en ese caso el problema tiene infinitas soluciones óptimas). La demostración se apoya en la convexidad: todo punto interior de la región factible puede expresarse como combinación convexa de los vértices (teorema de representación de Minkowski-Weyl para poliedros acotados), y como la función objetivo es lineal, su valor en cualquier combinación convexa de puntos es la misma combinación convexa de los valores en esos puntos, de modo que no puede superar (para un máximo) ni ser inferior (para un mínimo) al mayor o menor de los valores en los vértices; en consecuencia, ningún punto interior o del interior de un lado puede mejorar estrictamente el valor óptimo alcanzado en algún vértice. Este teorema es el que justifica de forma rigurosa el procedimiento práctico habitual en Bachillerato de evaluar la función objetivo únicamente en los vértices de la región factible (en lugar de estudiarla en todo el continuo de puntos de la región) para determinar la solución óptima, reduciendo un problema de optimización sobre un conjunto infinito a un simple cálculo aritmético sobre un número finito de puntos.
Método gráfico de resolución
El método gráfico de resolución de un problema de programación lineal con dos variables de decisión sigue un procedimiento sistemático de cuatro etapas: primero, plantear el problema identificando las variables de decisión, la función objetivo y el conjunto completo de restricciones (incluidas las de no negatividad); segundo, representar gráficamente cada restricción como un semiplano y obtener la región factible como su intersección; tercero, determinar los vértices de la región factible, calculando las coordenadas de cada uno como intersección de las rectas frontera correspondientes (resolviendo el sistema de dos ecuaciones lineales asociado a cada par de restricciones que se cortan en ese vértice); y cuarto, evaluar la función objetivo en cada uno de los vértices obtenidos y seleccionar el que da el valor máximo o mínimo según pida el problema, amparado este último paso por el teorema fundamental de la programación lineal. Una vía alternativa y equivalente al cuarto paso, de mayor valor geométrico, consiste en trazar una recta de nivel de la función objetivo para un valor arbitrario de referencia y desplazarla paralelamente en la dirección de crecimiento (dada por el vector gradiente) hasta identificar visualmente el último vértice de contacto con la región factible antes de abandonarla, lo que evita el cálculo numérico en todos los vértices cuando estos son muchos. El método gráfico es, por su carácter visual e inmediato, la vía de introducción estándar a la programación lineal en Bachillerato, y su dominio completo, incluyendo la correcta interpretación del resultado en el contexto del problema, es un contenido de examen de primer orden en este tema.
Vértices de la región factible
Los vértices de la región factible son los puntos de intersección de dos o más rectas frontera de las restricciones que, además, pertenecen efectivamente a la región factible (satisfacen todas las demás restricciones del problema); un punto de intersección de dos rectas frontera que no cumpla alguna otra restricción no es un vértice de la región factible, aunque sea un vértice del sistema de rectas considerado aisladamente, precisión que conviene remarcar porque es fuente frecuente de errores en el cálculo manual. El cálculo de las coordenadas de cada vértice se reduce a resolver el sistema de dos ecuaciones lineales formado por las dos rectas frontera que se cortan en él, mediante cualquiera de los métodos algebraicos habituales (sustitución, igualación, reducción) o mediante la regla de Cramer si se prefiere el enfoque matricial del tema 19. El número de vértices de la región factible depende del número de restricciones activas del problema y de su disposición geométrica relativa, y puede oscilar desde un mínimo de tres (un triángulo, la región acotada más simple posible con restricciones de no negatividad) hasta un número mayor cuantas más restricciones intervengan de forma efectiva; en un problema no acotado en alguna dirección, la región factible puede carecer de algunos vértices en el sentido habitual, y el análisis del comportamiento en el infinito de la función objetivo pasa a ser necesario para determinar si existe o no solución óptima.
Poliedro de soluciones factibles
Cuando el problema de programación lineal involucra tres o más variables de decisión, la región factible deja de ser un polígono plano y se convierte en un poliedro convexo en el espacio de dimensión igual al número de variables, definido igualmente como intersección de un número finito de semiespacios (la generalización natural de un semiplano a dimensiones superiores), cada uno asociado a una restricción lineal. El teorema fundamental de la programación lineal se generaliza sin cambios esenciales a este caso: el óptimo de la función objetivo lineal se alcanza en al menos un vértice del poliedro, entendiendo por vértice un punto extremo que no puede expresarse como combinación convexa propia de otros dos puntos distintos del poliedro. La dificultad práctica de este caso general es que el método gráfico deja de ser viable a partir de tres variables (la representación visual directa es inmanejable o imposible más allá de tres dimensiones, y ya en tres resulta poco operativa para el cálculo manual de vértices), lo que motiva la necesidad de un método algebraico sistemático capaz de recorrer los vértices del poliedro sin necesidad de visualizarlo geométricamente: precisamente el método símplex, desarrollado en un apartado posterior, que explora los vértices del poliedro de forma algorítmica, moviéndose en cada iteración a un vértice adyacente que mejora (o al menos no empeora) el valor de la función objetivo, hasta alcanzar la certeza de optimalidad mediante un criterio algebraico explícito.
Maximización y minimización de la función objetivo
Un mismo problema de programación lineal puede plantearse como maximización o como minimización de la función objetivo, según el contexto: se maximiza típicamente un beneficio, una producción o una utilidad, y se minimiza típicamente un coste, un tiempo o una distancia; ambos tipos de problema comparten exactamente la misma estructura matemática y el mismo procedimiento de resolución, y de hecho un problema de maximización de z se puede convertir siempre en uno de minimización equivalente sin más que cambiar el signo de la función objetivo (maximizar z equivale a minimizar −z, y viceversa), transformación que se usa con frecuencia para unificar el tratamiento algorítmico de ambos casos, en particular en las formulaciones estándar del método símplex, que suele presentarse convencionalmente solo para problemas de maximización. En el método gráfico, la diferencia entre maximizar y minimizar se traduce únicamente en el sentido en que se desplaza la recta de nivel de la función objetivo: hacia donde apunta el gradiente para maximizar, y en sentido contrario para minimizar, de modo que el vértice óptimo seleccionado en cada caso puede ser distinto aunque la región factible y las rectas de nivel sean idénticas. Es importante para el examen distinguir con precisión, en el enunciado de cada problema aplicado, cuál es la magnitud que se está optimizando y en qué sentido, porque un error en esta identificación conduce a seleccionar el vértice opuesto al correcto aunque todo el resto del procedimiento se haya ejecutado sin fallos.
Problema del transporte
El problema del transporte es una aplicación clásica de la programación lineal que busca determinar la forma más económica de distribuir un bien desde un conjunto de orígenes (fábricas, almacenes), cada uno con una oferta o capacidad de producción limitada, hasta un conjunto de destinos (tiendas, clientes), cada uno con una demanda que debe satisfacerse, minimizando el coste total de transporte, conocido el coste unitario de enviar una unidad desde cada origen a cada destino. Las variables de decisión son las cantidades xᵢⱼ enviadas desde cada origen i a cada destino j, la función objetivo es la suma de todos los costes cᵢⱼ·xᵢⱼ, y las restricciones expresan que la suma de lo enviado desde cada origen no puede superar su oferta disponible, y que la suma de lo recibido en cada destino debe cubrir al menos su demanda (o igualarla exactamente, en el caso equilibrado en que la oferta total coincide con la demanda total), además de la habitual restricción de no negatividad de todas las variables. Es el ejemplo histórico y pedagógico por excelencia de aplicación de la programación lineal a la logística y la investigación operativa, y aunque su resolución completa para un número elevado de orígenes y destinos requiere el método símplex o algoritmos especializados de transporte (como el método de la esquina noroeste o el método de costes mínimos para obtener una solución básica inicial, refinada después mediante el método de distribución modificada), en el aula de Secundaria y Bachillerato se plantean versiones simplificadas con dos orígenes y dos destinos, resolubles íntegramente por el método gráfico.
Problema de la mezcla o dieta
El problema de la mezcla (o problema de la dieta, en su formulación histórica original) busca determinar las cantidades óptimas de distintos componentes o alimentos que deben combinarse para satisfacer un conjunto de requisitos mínimos (o máximos) sobre determinadas propiedades —contenido nutricional mínimo de proteínas, vitaminas o calorías en el caso de la dieta; octanaje, pureza o composición química en el caso de mezclas industriales— minimizando el coste total de la mezcla resultante. Las variables de decisión son las cantidades de cada componente a utilizar, la función objetivo es el coste total (suma de precio unitario por cantidad de cada componente), y las restricciones expresan, para cada propiedad exigida, que la combinación resultante de esa propiedad en la mezcla debe superar (o no superar) un umbral dado, además de la restricción de no negatividad de las cantidades. Es, junto con el problema del transporte, uno de los dos ejemplos aplicados de referencia con los que tradicionalmente se ilustra la programación lineal en la enseñanza, y tiene un origen histórico ligado a la planificación de recursos económicos y militares durante la Segunda Guerra Mundial, cuando George Stigler planteó por primera vez de forma sistemática el problema de encontrar la dieta de coste mínimo que satisficiera las necesidades nutricionales diarias recomendadas, problema que resolvió aproximadamente por métodos heurísticos años antes de que el método símplex de Dantzig permitiera resolverlo de forma exacta y sistemática.
Método símplex
El método símplex, desarrollado por George Dantzig en 1947, es un algoritmo sistemático para resolver problemas de programación lineal con un número arbitrario de variables y restricciones, superando la limitación práctica del método gráfico (viable solo hasta dos, como mucho tres, variables). El algoritmo parte de un vértice inicial factible del poliedro de soluciones (obtenido habitualmente introduciendo variables de holgura que convierten las inecuaciones en ecuaciones, y tomando como solución inicial aquella en que las variables de decisión originales valen cero), y en cada iteración se desplaza a un vértice adyacente del poliedro que mejora estrictamente (o al menos no empeora) el valor de la función objetivo, seleccionando la dirección de mejora mediante un criterio algebraico basado en los llamados costes reducidos de las variables no básicas; el algoritmo concluye, con la certeza matemática de haber alcanzado el óptimo global (no solo local, gracias precisamente a la convexidad del poliedro), cuando ningún vértice adyacente mejora ya el valor actual. El método símplex se organiza habitualmente mediante tablas (tableaux) que registran de forma sistemática los coeficientes de las restricciones y de la función objetivo en cada iteración, facilitando su ejecución manual para problemas de tamaño moderado y, sobre todo, su implementación computacional eficiente para problemas de gran escala con miles de variables, que es el uso real y masivo que tiene hoy este método en la industria, la logística y la planificación económica.
Dualidad en programación lineal
A todo problema de programación lineal, llamado problema primal, se le puede asociar de forma sistemática otro problema de programación lineal, llamado problema dual, construido a partir de los mismos datos (coeficientes de la función objetivo, de las restricciones y de los términos independientes) pero intercambiando los papeles: los coeficientes de la función objetivo del primal pasan a ser los términos independientes de las restricciones del dual, y viceversa; una maximización del primal se convierte en una minimización del dual (o al revés); y cada restricción del primal da lugar a una variable del dual, mientras que cada variable del primal da lugar a una restricción del dual. El teorema de dualidad débil establece que el valor de la función objetivo de cualquier solución factible del dual es siempre una cota (superior o inferior, según el sentido de optimización) del valor óptimo del primal, y el teorema de dualidad fuerte, más profundo, garantiza que si ambos problemas tienen solución óptima finita, los valores óptimos del primal y del dual coinciden exactamente. La dualidad tiene una interpretación económica de gran valor práctico: las variables del problema dual se interpretan como los precios sombra o precios de equilibrio de los recursos limitados del problema primal, es decir, el valor marginal que tendría disponer de una unidad adicional de cada recurso escaso, información de enorme utilidad en la toma de decisiones económicas más allá de la simple obtención del óptimo numérico.
Restricciones de no negatividad
Las restricciones de no negatividad, x≥0 e y≥0 (o, en general, xᵢ≥0 para cada variable de decisión), exigen que las variables del problema de programación lineal no tomen valores negativos, condición casi siempre justificada por el propio significado físico o económico de las variables (cantidades producidas, transportadas o consumidas, que no pueden ser negativas en la práctica real). Estas restricciones se incorporan al sistema exactamente igual que cualquier otra restricción lineal, recortando la región factible a los semiplanos x≥0 e y≥0 (el primer cuadrante del plano, en el caso de dos variables), lo que garantiza que la región factible, si es no vacía, esté acotada al menos en las direcciones negativas de los ejes, aunque pueda seguir siendo no acotada en las direcciones positivas si el resto de restricciones no la limitan. Omitir las restricciones de no negatividad al plantear el problema es un error de modelización frecuente que puede dar lugar a un óptimo matemáticamente correcto pero sin sentido en el contexto real del problema (por ejemplo, una solución que recomiende producir una cantidad negativa de un artículo), por lo que su inclusión explícita, aunque parezca un formalismo menor, es una parte imprescindible del planteamiento riguroso de cualquier problema aplicado y debe figurar siempre, en el examen, en el listado completo de restricciones junto con las propias del enunciado.
Solución óptima única, múltiple o problema no acotado
Un problema de programación lineal puede presentar, según la relación entre la orientación de las rectas de nivel de la función objetivo y la forma de la región factible, tres situaciones cualitativamente distintas respecto de la solución óptima. La situación habitual es la de solución óptima única, en la que el valor óptimo se alcanza en un único vértice de la región factible, identificable sin ambigüedad. Puede ocurrir también que la solución óptima sea múltiple (o el problema tenga infinitas soluciones óptimas): esto sucede cuando la recta de nivel de la función objetivo, en el momento de alcanzar el valor óptimo, resulta ser paralela a uno de los lados de la región factible, de modo que todos los puntos de ese lado (no solo sus dos vértices extremos) dan el mismo valor óptimo de z, un caso que conviene detectar comparando la pendiente de la función objetivo con la de cada restricción activa en el óptimo. Finalmente, un problema puede no tener solución óptima finita cuando la región factible es no acotada en la dirección de crecimiento (o decrecimiento) de la función objetivo, de modo que z puede hacerse arbitrariamente grande (o pequeña) sin abandonar la región factible; este caso, llamado problema no acotado, se distingue del caso en que la región factible es directamente vacía (problema infactible, cuando las restricciones son incompatibles entre sí), y ambas situaciones deben saberse identificar y justificar con precisión en el examen, más allá del caso habitual de solución única.
Programación lineal entera
La programación lineal entera es la variante de la programación lineal en la que se exige, además de las restricciones habituales, que algunas o todas las variables de decisión tomen valores enteros, restricción adicional que responde a la naturaleza indivisible de muchas magnitudes reales (número de trabajadores, de vehículos, de unidades de un producto no fraccionable). Esta exigencia adicional cambia radicalmente la dificultad y la naturaleza del problema: mientras que la programación lineal continua se resuelve de forma eficiente y exacta mediante el método símplex (que siempre encuentra el óptimo global en un número finito, y en la práctica reducido, de iteraciones), la programación lineal entera es, en general, un problema computacionalmente mucho más difícil (perteneciente a la clase de problemas NP-difíciles), sin garantía de un algoritmo eficiente para instancias grandes. El procedimiento habitual de resolución práctica combina la relajación lineal del problema (resolverlo primero ignorando la restricción de integridad, mediante el símplex ordinario) con técnicas como el método de ramificación y acotación (branch and bound), que explora sistemáticamente las soluciones enteras próximas al óptimo continuo, descartando ramas del árbol de búsqueda que no puedan mejorar la mejor solución entera encontrada hasta el momento. En el contexto de Secundaria y Bachillerato, la programación lineal entera se trata de forma elemental, redondeando o ajustando manualmente la solución continua obtenida por el método gráfico a los valores enteros factibles más próximos, y comprobando cuál de ellos, dentro de la región factible, da el mejor valor de la función objetivo.
Modelización de problemas reales mediante sistemas de inecuaciones
La modelización de un problema real de programación lineal —el paso de un enunciado verbal a un modelo matemático resoluble— es, con frecuencia, la etapa de mayor dificultad conceptual del tema, por encima incluso del procedimiento algorítmico de resolución. Requiere, en primer lugar, identificar con precisión cuáles son las verdaderas variables de decisión del problema (las cantidades que se pueden elegir libremente, no las que vienen dadas como datos); en segundo lugar, traducir cada condición o limitación del enunciado a una inecuación lineal en esas variables, prestando especial atención a las unidades y a si la desigualdad debe ser estricta o no; y en tercer lugar, identificar correctamente la magnitud a optimizar y expresarla como combinación lineal de las variables de decisión, determinando si el problema pide maximizar o minimizar. Un error frecuente en esta fase es confundir una restricción con la función objetivo, o plantear como variable de decisión una cantidad que en realidad es un dato fijo del problema; otro error habitual es omitir restricciones implícitas en el enunciado que no se mencionan de forma explícita pero se deducen del contexto (como la propia no negatividad de las variables, o límites de capacidad que se dan por supuestos). La correcta modelización es la habilidad que el tribunal evalúa con mayor exigencia en este tema, porque es la que demuestra la capacidad real de aplicar la teoría matemática a un contexto genuinamente nuevo, más allá de la ejecución mecánica de un procedimiento ya entrenado sobre un enunciado tipo.
George Dantzig y el origen del método símplex
George Bernard Dantzig (1914-2005), matemático estadounidense, desarrolló el método símplex en 1947 mientras trabajaba para la fuerza aérea de los Estados Unidos en problemas de planificación logística y de asignación óptima de recursos militares durante y después de la Segunda Guerra Mundial, contexto histórico que explica el nombre alternativo de «programación» (en el sentido de planificación de un programa de actividades, y no de programación informática) con el que se bautizó a toda esta rama de la optimización matemática. Es célebre la anécdota, relatada por el propio Dantzig, según la cual Dantzig, siendo estudiante de doctorado, llegó tarde a una clase y copió del encerado dos problemas que creyó que eran ejercicios de tarea, resolviéndolos en unos días; en realidad eran dos problemas estadísticos abiertos sin solución conocida hasta ese momento, episodio que, aunque anterior y no directamente relacionado con la programación lineal, ilustra su perfil de matemático aplicado orientado a la resolución práctica de problemas concretos, rasgo que definió toda su carrera posterior. El método símplex de Dantzig, formulado en 1947 y difundido ampliamente a partir de finales de esa década y en la de 1950, es considerado uno de los algoritmos de mayor impacto práctico del siglo XX, con aplicación directa y masiva en logística, planificación de la producción, gestión financiera, telecomunicaciones y prácticamente cualquier sector económico que deba asignar recursos limitados de forma óptima, lo que ha llevado a incluirlo de forma recurrente entre los algoritmos más influyentes de la historia de la computación aplicada.
Interpretación geométrica del gradiente de la función objetivo
El vector gradiente de la función objetivo lineal z=px+qy es el vector constante (p,q) formado por los coeficientes de las variables, y su interpretación geométrica es la de indicar, en todo punto del plano, la dirección en la que la función z crece más rápidamente (dirección de máximo crecimiento), siendo además perpendicular en todo punto a las rectas de nivel px+qy=k, ya que estas rectas son precisamente los conjuntos donde z permanece constante y el gradiente de una función es siempre ortogonal a sus curvas (o rectas) de nivel. En el método gráfico de resolución de un problema de programación lineal, dibujar el vector gradiente junto a la región factible proporciona una vía visual directa e intuitiva para determinar, sin necesidad de evaluar la función objetivo en cada vértice, cuál es el vértice donde se alcanza el máximo (el más alejado en la dirección del gradiente) y cuál el mínimo (el más alejado en la dirección opuesta), simplemente desplazando mentalmente una recta perpendicular al gradiente desde el infinito hacia la región factible hasta el primer y el último punto de contacto. Esta interpretación geométrica conecta explícitamente el contenido de programación lineal con el concepto de gradiente y derivadas direccionales estudiado en el bloque de Análisis del temario, y ofrece al futuro docente un recurso didáctico visual de gran valor para que el alumnado de Bachillerato comprenda el fundamento del método gráfico más allá de su ejecución mecánica mediante evaluación numérica en los vértices.
Programación lineal aplicada a la gestión de recursos escasos
La programación lineal es, en su sentido más amplio, la formalización matemática del problema económico fundamental de asignar recursos limitados (tiempo, materias primas, capital, mano de obra) entre usos alternativos de la forma más eficiente posible según un criterio de optimización dado, lo que explica su presencia transversal en la economía, la ingeniería industrial, la logística, la agricultura (planificación de cultivos), la sanidad (asignación de camas y personal) y prácticamente cualquier sector que deba tomar decisiones cuantitativas bajo restricciones. Su relevancia curricular en Bachillerato responde precisamente a esta capacidad de conectar el contenido matemático abstracto (sistemas de inecuaciones, funciones lineales, convexidad) con problemas de toma de decisiones genuinamente presentes en la actividad económica y social, lo que la convierte en uno de los bloques del temario de matemáticas con mayor proyección hacia la alfabetización matemática funcional y hacia la comprensión crítica de decisiones económicas y de gestión pública. Más allá del caso lineal estudiado en este tema, la programación lineal es la puerta de entrada conceptual a la investigación operativa, una disciplina más amplia que incluye la programación no lineal, la programación entera, la programación dinámica y la teoría de grafos aplicada a la optimización de redes (contenido este último desarrollado en el tema 2 del temario), disciplinas todas ellas que comparten el mismo objetivo general de modelizar y resolver problemas de decisión óptima bajo restricciones, con herramientas matemáticas cada vez más sofisticadas a medida que se abandona la hipótesis de linealidad.
Forma general y forma estándar del problema; soluciones básicas
La forma canónica de un problema de maximización es: maximizar z=cᵀx sujeto a Ax≤b, x≥0, con c el vector de coeficientes de la función objetivo, A la matriz de restricciones y b el vector de recursos. Una restricción de tipo ≥ se multiplica por −1 y una igualdad equivale a dos desigualdades; una variable libre se escribe como diferencia de dos no negativas. En la forma estándar se añade a cada restricción ≤ una variable de holgura sᵢ≥0 que mide el recurso no utilizado (y se resta una variable de exceso en las ≥), de modo que Ax+s=b. Con n variables de decisión y m restricciones, el sistema tiene m ecuaciones y n+m incógnitas; una solución básica se obtiene fijando n variables a 0 (variables no básicas) y resolviendo para las m restantes (variables básicas); es factible si todas son no negativas. El resultado central es que las soluciones básicas factibles coinciden con los vértices del poliedro de soluciones, de modo que explorar vértices equivale a explorar bases. Una solución básica es degenerada si alguna variable básica vale 0, lo que ocurre cuando más de n restricciones pasan por un mismo vértice, y puede provocar que el símplex realice iteraciones sin mejorar z. Si el problema es de minimización, se maximiza −z.
Ejemplos resueltos por el método gráfico
Ejemplo 1 (maximizar). Maximizar z=3x+2y sujeto a x+y≤4, x+3y≤6, x≥0, y≥0. Los vértices de la región factible son (0,0), (4,0), (0,2) y la intersección de x+y=4 con x+3y=6, que es (3,1). Valores de z: 0, 12, 4 y 11. El máximo es 12 en (4,0). Ejemplo 2 (producción). Una carpintería fabrica mesas (x) y sillas (y). Cada mesa necesita 3 h de carpintería y 1 h de acabado y deja 40 € de beneficio; cada silla, 2 h y 2 h y 30 €. Hay 120 h de carpintería y 80 h de acabado. Maximizar 40x+30y sujeto a 3x+2y≤120, x+2y≤80, x,y≥0. Vértices: (0,0), (40,0), (0,40) y (20,30), intersección de las dos rectas (restando, 2x=40). Beneficios: 0, 1600, 1200 y 800+900=1700. Óptimo: 20 mesas y 30 sillas, con 1700 €. Ejemplo 3 (minimizar, región no acotada). Minimizar z=2x+3y sujeto a x+y≥4, x+3y≥6, x,y≥0. Vértices: (0,4), (3,1) y (6,0), con z=12, 9 y 12. El mínimo es 9 en (3,1); en cambio el problema de maximizar z no tiene solución, pues la región es no acotada. Al evaluar vértices en regiones no acotadas hay que justificar además que la función objetivo no puede mejorar en la dirección no acotada.
Casos especiales con ejemplos: solución múltiple, no acotado e infactible
Solución múltiple: maximizar z=x+y sujeto a x+y≤4, x≤3, x,y≥0. Los vértices (0,0), (3,0), (3,1) y (0,4) dan z=0, 3, 4 y 4. El máximo 4 se alcanza en los vértices (3,1) y (0,4) y en todo el segmento que los une, porque la recta de nivel x+y=4 es paralela a la restricción x+y≤4. Problema no acotado: maximizar z=x+y sujeto a x−y≤1, x,y≥0; la región contiene la semirrecta (t+1,t) para t≥0, sobre la que z=2t+1 crece sin límite. Un problema de minimización sobre esa misma región sí tiene solución (en (0,0), con z=0). Problema infactible: x+y≤1 junto con x+y≥3 no tiene ninguna solución, la región factible es vacía. Para el examen conviene recordar el diagnóstico en el símplex: si en una columna con coste reducido favorable todos los elementos son menores o iguales que 0, el problema es no acotado; si al terminar la fase de variables artificiales alguna sigue siendo positiva, es infactible; si un coste reducido de una variable no básica vale 0 en el óptimo, hay soluciones óptimas múltiples.
El método símplex en la práctica: tabla y ejemplo
Aplicado al problema de producción (maximizar 40x+30y con 3x+2y+s₁=120, x+2y+s₂=80), la solución inicial es x=y=0, s₁=120, s₂=80, con z=0. Primera iteración: la variable de entrada es x (coste reducido 40, el mayor); el cociente mínimo entre recursos y coeficientes positivos es mín{120/3, 80/1}=40, luego sale s₁. Tras el pivote, x=40−(2/3)y−(1/3)s₁, s₂=40−(4/3)y+(1/3)s₁ y z=1600+(10/3)y−(40/3)s₁. Segunda iteración: entra y (coste reducido 10/3>0); los cocientes son 40/(2/3)=60 y 40/(4/3)=30, luego sale s₂. Resulta y=30, x=20, z=1700 y z=1700−(25/2)s₁−(5/2)s₂. Como todos los costes reducidos son no positivos, es el óptimo: x=20, y=30, z=1700 (el mismo vértice hallado gráficamente). Lectura de la tabla final: los coeficientes −25/2 y −5/2 son los precios sombra de las horas de carpintería y de acabado: una hora más de carpintería aumenta el beneficio óptimo en 12,5 € y una hora más de acabado en 2,5 € (mientras no cambie la base óptima). La regla del cociente mínimo asegura que se mantiene la factibilidad; la regla del coste reducido más favorable (regla de Dantzig) es la habitual, y la regla de Bland evita los ciclos en casos degenerados.
Dualidad: ejemplo, holguras complementarias y precios sombra
El dual del problema de maximizar cᵀx sujeto a Ax≤b, x≥0 es el de minimizar bᵀy sujeto a Aᵀy≥c, y≥0. Para el problema de producción, el dual es: minimizar 120u+80v sujeto a 3u+v≥40, 2u+2v≥30, u,v≥0. La solución u=12,5 y v=2,5 cumple 37,5+2,5=40 y 25+5=30 y da 120·12,5+80·2,5=1500+200=1700, que coincide con el óptimo del primal, como asegura el teorema de dualidad fuerte; u y v son los precios sombra de las horas de carpintería y de acabado. Teorema de las holguras complementarias: x* e y* son óptimas si y solo si, para cada restricción del primal, o bien se cumple con igualdad o bien la variable dual correspondiente es 0, y análogamente para las restricciones del dual y las variables del primal. Interpretación: si un recurso sobra (holgura positiva), su precio sombra es 0. Con dualidad débil, bᵀy≥cᵀx para toda pareja factible, lo que permite certificar la optimalidad de una solución sin recorrer todos los vértices. Casos: si el primal es no acotado, el dual es infactible; si ambos son factibles, ambos tienen óptimo y coinciden. El dual de un problema de transporte tiene la interpretación de precios en los orígenes y destinos.
Problema del transporte: ejemplo numérico y problema de asignación
Ejemplo: dos fábricas A y B con ofertas 30 y 20 unidades abastecen a dos tiendas con demandas 25 y 25 (oferta total igual a demanda total, problema equilibrado). Costes unitarios: A→1: 2, A→2: 3, B→1: 4, B→2: 1. Sea x lo enviado de A a 1. Entonces A→2 es 30−x, B→1 es 25−x y B→2 es 20−(25−x)=x−5; todas deben ser no negativas, luego 5≤x≤25. El coste total es 2x+3(30−x)+4(25−x)+1(x−5)=185−4x, que se minimiza en x=25: A envía 25 a la tienda 1 y 5 a la 2, y B envía 20 a la 2, con coste mínimo 85. Aprovechando que un problema equilibrado de m orígenes y n destinos tiene m+n−1 variables básicas, la solución inicial por esquina noroeste o por costes mínimos se mejora con el método MODI (distribución modificada) comprobando los costes reducidos. Si la oferta total supera a la demanda se añade un destino ficticio con costes 0. El problema de asignación (cada origen se asigna a exactamente un destino, como asignar tareas a trabajadores) es un transporte con ofertas y demandas unitarias, que resuelve el algoritmo húngaro de Kuhn (1955); su matriz de restricciones es totalmente unimodular, por lo que el símplex da soluciones enteras sin imponer integridad.
Problema de la dieta y la mezcla: ejemplo y origen de Stigler
Ejemplo de dieta con dos alimentos: A cuesta 2 € por unidad y aporta 1 unidad de vitaminas y 1 de proteínas, y B cuesta 3 € y aporta 1 de vitaminas y 3 de proteínas; se exige al menos 4 de vitaminas y 6 de proteínas. Minimizar 2x+3y con x+y≥4, x+3y≥6. Es exactamente el ejemplo de región no acotada visto antes, con óptimo en (3,1) y coste 9: 3 unidades de A y 1 de B. El problema clásico de la dieta fue planteado por George Stigler en 1945 con 77 alimentos y 9 nutrientes; Stigler halló una solución aproximada por tanteo razonado, y la resolución exacta mediante el símplex fue una de las primeras pruebas del algoritmo de Dantzig, a finales de los años cuarenta, con un esfuerzo de cálculo manual considerable. En las versiones industriales (piensos, mezclas de combustibles, aleaciones), cada ingrediente aporta cantidades de varias propiedades y se minimiza el coste cumpliendo mínimos y máximos. Una dificultad práctica es que la solución óptima puede ser poco apetecible o poco realista (los modelos de dieta no recogen sabor o variedad), por lo que se añaden restricciones de límite superior por alimento. Se trata de un modelo de mezcla con restricciones de composición, y es el paradigma de programación lineal con restricciones ≥.
Análisis de sensibilidad en el método gráfico
El análisis de sensibilidad estudia cuánto pueden variar los datos sin que cambie la solución óptima. En el problema de producción (óptimo en (20,30), con las rectas 3x+2y=120 y x+2y=80 activas), si el beneficio de una mesa es p y el de una silla es 30, la recta de nivel px+30y=k tiene pendiente −p/30; el vértice (20,30) sigue siendo óptimo mientras esa pendiente esté entre las de las dos restricciones activas, −3/2 y −1/2, es decir, 15≤p≤45. Con p=40, el óptimo no cambia; con p=50, el óptimo pasa a (40,0) con z=2000, ya que p>45. Respecto a los recursos, si las horas de carpintería son b, el vértice definido por las dos restricciones activas es x=(b−80)/2, y=(240−b)/4, que es factible mientras x≥0 e y≥0, es decir, para 80≤b≤240; en ese intervalo el beneficio óptimo crece 12,5 € por cada hora adicional (el precio sombra) y fuera de él cambia la base óptima y, con ella, el precio sombra. Desde el punto de vista didáctico, este análisis conecta las pendientes de las rectas de nivel con las de las restricciones, y justifica la interpretación económica de la solución más allá del número óptimo.
Programación lineal entera: ejemplo y redondeo
Redondear la solución continua puede dar un resultado no óptimo o incluso no factible. Ejemplo: maximizar z=5x+4y sujeto a 6x+4y≤24, x+2y≤6, x,y≥0 enteros. La solución de la relajación lineal es (3; 1,5) con z=21. Si se redondea a (3,1) se obtiene z=19; pero entre los puntos enteros factibles, (4,0) cumple 24≤24 y 4≤6 y da z=20, mejor que (3,1) y que (2,2) (z=18), de modo que el óptimo entero es (4,0) con z=20. El redondeo hacia arriba, (3,2), no es factible porque 6·3+4·2=26>24. El método de ramificación y acotación resolvería esto dividiendo según y≤1 o y≥2, resolviendo las relajaciones y podando por cotas. Otras técnicas son los planos de corte de Gomory y la formulación de variables binarias, que modelan decisiones sí/no (abrir o cerrar una fábrica, asignaciones). La relajación lineal da siempre una cota superior (en maximización) del óptimo entero, y si la relajación ya es entera, es óptima para el problema entero. En las matrices totalmente unimodulares (transporte, asignación, flujos), la relajación lineal tiene siempre soluciones básicas enteras.
Demostración del teorema fundamental y puntos extremos
Un punto P de un conjunto convexo C es un punto extremo (vértice) si no puede escribirse como P=λQ+(1−λ)R con Q≠R en C y 0<λ<1. Un poliedro convexo acotado es la envolvente convexa de sus vértices (teorema de Minkowski-Weyl en su versión acotada): todo punto es combinación convexa X=Σλᵢ Vᵢ con λᵢ≥0 y Σλᵢ=1. Como f(X)=Σλᵢ f(Vᵢ) es lineal, f(X) es un promedio ponderado de valores en los vértices, por lo que no puede superar el máximo de f(Vᵢ) ni quedar por debajo del mínimo. De ahí que el óptimo se alcance en un vértice; y si se alcanza en dos vértices, entonces también en el segmento que los une, y si se alcanza en un punto interior, f es constante en todo el conjunto. Versión no acotada: si la región factible no es vacía, no contiene rectas completas (hay vértices) y f está acotada en la dirección de optimización sobre ella, el óptimo también se alcanza en un vértice, pues la región es suma de la envolvente convexa de sus vértices y un cono de direcciones, y f no puede mejorar a lo largo de las direcciones. Esta es la demostración que respalda el recorrido de vértices del símplex y es base del criterio de optimalidad.
Historia de la programación lineal
Joseph Fourier (1827) ya consideró sistemas de desigualdades lineales y un método para eliminar variables. En 1939 el matemático soviético Leonid Kantorovich formuló problemas de planificación de la producción como problemas de programación lineal y propuso un método de resolución (multiplicadores de resolución), que no se conoció en Occidente hasta años después. En 1941 Frank Hitchcock planteó el problema del transporte. Durante la Segunda Guerra Mundial, la investigación operativa se aplicó a la logística militar. En 1947 Dantzig formuló el problema general de programación lineal y el método símplex; ese mismo año, John von Neumann identificó la dualidad con la teoría de juegos de suma cero. Kantorovich y Tjalling Koopmans recibieron en 1975 el Premio Nobel de Economía por sus contribuciones a la teoría de la asignación óptima de recursos. En 1972, Klee y Minty construyeron problemas en los que el símplex recorre un número exponencial de vértices, aunque en la práctica es muy eficiente; Leonid Khachiyan (1979, método del elipsoide) demostró que la programación lineal es resoluble en tiempo polinómico, y Narendra Karmarkar (1984) propuso un método de punto interior eficiente en la práctica. Estos hitos muestran la distinción entre complejidad en el peor caso y eficiencia práctica.
Programación lineal en el currículo y errores típicos
La programación lineal ha formado parte tradicionalmente de las Matemáticas aplicadas a las Ciencias Sociales de 2.º de Bachillerato, y su presencia concreta en cada comunidad debe contrastarse con el currículo vigente derivado del Real Decreto 243/2022. En cualquier caso, es un contenido de gran valor competencial: modelización, interpretación gráfica de inecuaciones, uso de herramientas digitales (GeoGebra, hojas de cálculo con Solver) y toma de decisiones. Errores frecuentes: olvidar las restricciones de no negatividad; trazar mal el semiplano (probar siempre con un punto); evaluar la función objetivo en puntos de corte que no pertenecen a la región factible; confundir el máximo con el mínimo o evaluar solo uno de los vértices; no comprobar que la solución es entera cuando el contexto lo exige; creer que el óptimo se alcanza en el centro de la región; y no interpretar el resultado (por ejemplo, olvidar las unidades o no contestar la pregunta formulada). Es recomendable que la resolución incluya: definición de variables con unidades, tabla de datos, restricciones, dibujo con la región señalada, vértices con su cálculo, tabla de valores de z, conclusión contextualizada, y comprobación en las restricciones.
Ideas clave para el examen — memoriza esto
Una inecuación lineal ax+by≤c define un semiplano; el punto de prueba (habitualmente el origen) determina cuál de los dos semiplanos es la solución.
La región factible, intersección de semiplanos, es siempre un conjunto convexo; esta convexidad es la razón geométrica de que el óptimo se alcance en un vértice.
Teorema fundamental de la programación lineal: si la región factible es convexa y acotada, el óptimo de la función objetivo lineal se alcanza en un vértice (o en un lado completo si hay solución múltiple).
Método gráfico: representar restricciones, hallar vértices resolviendo sistemas 2x2, evaluar la función objetivo en cada vértice y elegir el óptimo.
La función objetivo z=px+qy define rectas de nivel paralelas; el vector gradiente (p,q) es perpendicular a ellas y marca la dirección de máximo crecimiento.
Problema del transporte: minimizar coste de envío desde orígenes con oferta limitada a destinos con demanda fija; problema de la mezcla/dieta: minimizar coste cumpliendo requisitos mínimos de componentes.
Método símplex (Dantzig, 1947): algoritmo que recorre vértices adyacentes del poliedro mejorando la función objetivo en cada iteración, válido para cualquier número de variables.
Dualidad: a todo problema primal se asocia un dual con papeles intercambiados; el teorema de dualidad fuerte iguala los óptimos de ambos si son finitos; las variables duales son precios sombra.
Restricciones de no negatividad (x≥0, y≥0) son casi siempre imprescindibles por el significado físico de las variables; omitirlas es un error de modelización frecuente.
Un problema puede tener solución óptima única, solución múltiple (recta de nivel paralela a un lado de la región factible) o ser no acotado (región factible ilimitada en la dirección de optimización).
Programación lineal entera: exige valores enteros en las variables; es NP-difícil en general, se aborda con relajación lineal + ramificación y acotación.
La modelización correcta (identificar variables de decisión, traducir restricciones, definir la función objetivo) es la fase más exigente y más evaluada del problema.
El poliedro de soluciones generaliza el polígono factible a 3 o más variables; el método gráfico deja de ser viable y se necesita el símplex.
George Dantzig desarrolló el símplex en un contexto de planificación logística militar; de ahí el nombre 'programación' (planificación), no relacionado con programación informática.
La programación lineal es la base de la investigación operativa: gestión de recursos escasos en economía, logística, sanidad y planificación de la producción.
Forma canónica: max cᵀx s.a. Ax≤b, x≥0. Se añade una variable de holgura por cada restricción ≤; soluciones básicas factibles = vértices.
Ejemplo de referencia: max 40x+30y con 3x+2y≤120, x+2y≤80 tiene óptimo en (20,30) con z=1700 (vértices (0,0),(40,0),(0,40),(20,30)).
Región no acotada: se puede minimizar y no maximizar (o al revés) según la orientación de la función objetivo; evaluar solo los vértices no basta sin justificar el comportamiento no acotado.
Solución múltiple: la recta de nivel es paralela a un lado de la región; el óptimo se alcanza en dos vértices y en todo el segmento entre ellos.
Símplex: variable de entrada = mayor coste reducido; variable de salida = cociente mínimo; la regla de Bland evita ciclos; degeneración = variable básica nula.
Dualidad fuerte: si ambos problemas son factibles, sus óptimos coinciden (en el ejemplo, 1700 en primal y dual); los precios sombra son 12,5 y 2,5.
Holguras complementarias: si una restricción no está saturada, su precio sombra es 0; si una variable es positiva, su restricción dual se cumple con igualdad.
Transporte equilibrado m×n: m+n−1 variables básicas; el algoritmo húngaro (Kuhn, 1955) resuelve la asignación; la unimodularidad total garantiza soluciones enteras.
Redondear la solución continua no garantiza optimalidad ni factibilidad: en max 5x+4y s.a. 6x+4y≤24, x+2y≤6, el óptimo entero es (4,0) y no el redondeo (3,1).
Historia: Kantorovich (1939) y Koopmans (Nobel 1975), Hitchcock (1941), Dantzig (1947), Klee-Minty (1972, símplex exponencial en el peor caso), Khachiyan (1979, polinómico), Karmarkar (1984).
Sensibilidad gráfica: el vértice óptimo se mantiene mientras la pendiente de las rectas de nivel esté entre las de las restricciones activas.
Un problema de programación lineal puede ser infactible (región vacía), no acotado o tener óptimo único o múltiple; el diagnóstico se razona con la región y la función objetivo.
10 preguntas sobre este tema, en orden aleatorio. Sin registro, sin límite de intentos.
Pregunta 1 de 100 aciertos
En el problema de transporte equilibrado con 2 orígenes (ofertas 30 y 20) y 2 destinos (demandas 25 y 25), con costes A→1: 2, A→2: 3, B→1: 4, B→2: 1, ¿cuál es el coste mínimo?
Preguntas frecuentes
¿De qué trata el Tema 17 de Secundaria?
El Tema 17 estudia la programación lineal, la rama de la optimización matemática que busca maximizar o minimizar una función objetivo lineal sujeta a restricciones expresadas mediante inecuaciones o ecuaciones lineales. El tema arranca del contenido tradicional de segundo de Bachillerato de Ciencias Sociales (su concreción depende del currículo vigente de cada comunidad) —resolución de sistemas de inecuaciones lineales con dos incógnitas, representación gráfica de la región factible y localización del óptimo en un vértice— y se completa con el fundamento teórico que justifica ese procedimiento (el teorema fundamental de la programación lineal, que garantiza que el óptimo se alcanza en un vértice del polígono o poliedro de soluciones), con el método símplex como generalización algorítmica a más de dos variables, y con las aplicaciones clásicas del problema del transporte y del problema de la mezcla o dieta.
Es un tema con una vertiente aplicada muy marcada: la programación lineal nació históricamente ligada a problemas logísticos y económicos reales (Dantzig desarrolló el método símplex para la planificación de recursos militares durante la Segunda Guerra Mundial) y sigue siendo hoy una herramienta de gestión de recursos escasos de uso universal en economía, ingeniería e investigación operativa. El candidato debe manejar con soltura tanto el procedimiento gráfico de resolución en dos variables (contenido de examen directo, replicable en el aula de Bachillerato) como los fundamentos geométricos y algorítmicos (convexidad, vértices, símplex, dualidad) que explican por qué ese procedimiento funciona y cómo se generaliza.
¿Qué hay que memorizar del Tema 17 para el examen?
Una inecuación lineal ax+by≤c define un semiplano; el punto de prueba (habitualmente el origen) determina cuál de los dos semiplanos es la solución. La región factible, intersección de semiplanos, es siempre un conjunto convexo; esta convexidad es la razón geométrica de que el óptimo se alcance en un vértice. Teorema fundamental de la programación lineal: si la región factible es convexa y acotada, el óptimo de la función objetivo lineal se alcanza en un vértice (o en un lado completo si hay solución múltiple). Método gráfico: representar restricciones, hallar vértices resolviendo sistemas 2x2, evaluar la función objetivo en cada vértice y elegir el óptimo. La función objetivo z=px+qy define rectas de nivel paralelas; el vector gradiente (p,q) es perpendicular a ellas y marca la dirección de máximo crecimiento. Problema del transporte: minimizar coste de envío desde orígenes con oferta limitada a destinos con demanda fija; problema de la mezcla/dieta: minimizar coste cumpliendo requisitos mínimos de componentes. Método símplex (Dantzig, 1947): algoritmo que recorre vértices adyacentes del poliedro mejorando la función objetivo en cada iteración, válido para cualquier número de variables. Dualidad: a todo problema primal se asocia un dual con papeles intercambiados; el teorema de dualidad fuerte iguala los óptimos de ambos si son finitos; las variables duales son precios sombra. Restricciones de no negatividad (x≥0, y≥0) son casi siempre imprescindibles por el significado físico de las variables; omitirlas es un error de modelización frecuente. Un problema puede tener solución óptima única, solución múltiple (recta de nivel paralela a un lado de la región factible) o ser no acotado (región factible ilimitada en la dirección de optimización). Programación lineal entera: exige valores enteros en las variables; es NP-difícil en general, se aborda con relajación lineal + ramificación y acotación. La modelización correcta (identificar variables de decisión, traducir restricciones, definir la función objetivo) es la fase más exigente y más evaluada del problema. El poliedro de soluciones generaliza el polígono factible a 3 o más variables; el método gráfico deja de ser viable y se necesita el símplex. George Dantzig desarrolló el símplex en un contexto de planificación logística militar; de ahí el nombre 'programación' (planificación), no relacionado con programación informática. La programación lineal es la base de la investigación operativa: gestión de recursos escasos en economía, logística, sanidad y planificación de la producción. Forma canónica: max cᵀx s.a. Ax≤b, x≥0. Se añade una variable de holgura por cada restricción ≤; soluciones básicas factibles = vértices. Ejemplo de referencia: max 40x+30y con 3x+2y≤120, x+2y≤80 tiene óptimo en (20,30) con z=1700 (vértices (0,0),(40,0),(0,40),(20,30)). Región no acotada: se puede minimizar y no maximizar (o al revés) según la orientación de la función objetivo; evaluar solo los vértices no basta sin justificar el comportamiento no acotado. Solución múltiple: la recta de nivel es paralela a un lado de la región; el óptimo se alcanza en dos vértices y en todo el segmento entre ellos. Símplex: variable de entrada = mayor coste reducido; variable de salida = cociente mínimo; la regla de Bland evita ciclos; degeneración = variable básica nula. Dualidad fuerte: si ambos problemas son factibles, sus óptimos coinciden (en el ejemplo, 1700 en primal y dual); los precios sombra son 12,5 y 2,5. Holguras complementarias: si una restricción no está saturada, su precio sombra es 0; si una variable es positiva, su restricción dual se cumple con igualdad. Transporte equilibrado m×n: m+n−1 variables básicas; el algoritmo húngaro (Kuhn, 1955) resuelve la asignación; la unimodularidad total garantiza soluciones enteras. Redondear la solución continua no garantiza optimalidad ni factibilidad: en max 5x+4y s.a. 6x+4y≤24, x+2y≤6, el óptimo entero es (4,0) y no el redondeo (3,1). Historia: Kantorovich (1939) y Koopmans (Nobel 1975), Hitchcock (1941), Dantzig (1947), Klee-Minty (1972, símplex exponencial en el peor caso), Khachiyan (1979, polinómico), Karmarkar (1984). Sensibilidad gráfica: el vértice óptimo se mantiene mientras la pendiente de las rectas de nivel esté entre las de las restricciones activas. Un problema de programación lineal puede ser infactible (región vacía), no acotado o tener óptimo único o múltiple; el diagnóstico se razona con la región y la función objetivo.
¿Hay preguntas de test de este tema exacto?
Sí, 10 preguntas tipo test sobre este tema, en el apartado "Ponte a prueba" de esta misma página. Sin registro y sin límite de intentos.
¿De dónde sale el temario de este tema?
Del índice oficial de BOE núm. 226, de 21 de septiembre de 1993, páginas 27400 a 27438 (Orden de 9 de septiembre de 1993, del Ministerio de Educación y Ciencia, BOE-A-1993-23257), Anexo III — cuestionario específico (Parte A) de la especialidad Matemáticas del Cuerpo de Profesores de Enseñanza Secundaria (Temario oficial estatal de referencia — especialidad Matemáticas (Cuerpo de Profesores de Enseñanza Secundaria)).
Fuentes de este desarrollo
G. B. Dantzig, Linear Programming and Extensions (1963); formulación del símplex (1947)
L. V. Kantorovich (1939), métodos matemáticos de organización y planificación de la producción; Premio Nobel de Economía 1975 (con T. C. Koopmans)
G. J. Stigler (1945), The Cost of Subsistence, Journal of Farm Economics (problema de la dieta)
F. S. Hillier y G. J. Lieberman, Introducción a la investigación de operaciones; H. A. Taha, Investigación de operaciones
Real Decreto 243/2022, de 5 de abril, por el que se establecen la ordenación y las enseñanzas mínimas del Bachillerato — Matemáticas aplicadas a las Ciencias Sociales (contrastar su concreción con el currículo autonómico)
Mientras tanto, practica con tests gratis de Secundaria.