Test Tema 5: Programación lineal, Simplex y dualidad¶

Este test está basado en las 15 preguntas del cuestionario del tema. Tiene una sola respuesta correcta por pregunta. Selecciona tus respuestas y pulsa Comprobar respuestas para conocer tu nota, ver la explicación rápida de cada pregunta y consultar al final las soluciones explicadas paso a paso.

Cómo estudiar

Haz primero el test sin mirar las soluciones. Al corregirlo, lee la explicación rápida de cada pregunta y, si necesitas profundizar, despliega la explicación detallada paso a paso al final de la página.

Soluciones explicadas: aprende pregunta por pregunta¶

1. Respuesta correcta: A — Definición de Programación Lineal

La **programación lineal** es una disciplina fundamental de la investigación operativa encargada de optimizar (maximizar o minimizar) una función objetivo lineal, sujeta a un conjunto de restricciones compuestas por ecuaciones o inecuaciones lineales. Se utiliza ampliamente en la planificación de recursos, logística, optimización de redes, asignación de tareas informáticas y gestión financiera. **Para el examen:** todas las expresiones dentro del modelo (tanto la función objetivo como las restricciones) deben ser estrictamente de primer grado (lineales).

2. Respuesta correcta: B — Objetivo fundamental de la programación lineal

El objetivo básico consiste en encontrar la combinación de valores para las variables de decisión $x_1, x_2, \dots, x_n$ dentro de la **región factible** que consiga el valor óptimo (el máximo beneficio o el mínimo coste) de la función objetivo. No consiste simplemente en resolver un sistema lineal ordinario, sino en **seleccionar la mejor solución entre un conjunto infinito de soluciones posibles**.

3. Respuesta correcta: B — El algoritmo Simplex

El **algoritmo Simplex**, desarrollado por George Dantzig en 1947, es la técnica sistemática para resolver modelos de programación lineal. - Opera geométricamente desplazándose a través de los **vértices (extremos)** del politopo de la región factible. - En cada iteración evalúa si el vértice contiguo mejora el valor de la función objetivo. - Finaliza cuando no existen vértices contiguos con mejor resultado (alcanzando el óptimo) o detecta que la solución no está acotada.

4. Respuesta correcta: C — Óptimos globales en modelos lineales

Gracias a la propiedad matemática de **convexidad** del espacio de soluciones factibles y a la linealidad de la función objetivo: - Si un problema de programación lineal tiene una solución óptima local, esta es **garantizadamente un óptimo global**. - No existen "trampas" de máximos o mínimos locales peores que el óptimo global, a diferencia de lo que sucede en la programación no lineal. **Excepción:** Un modelo puede tener **varios óptimos globales** (infinitos puntos a lo largo de una cara o arista que alcanzan exactamente el mismo valor máximo o mínimo).

5. Respuesta correcta: B — Uso en ciencias de la computación

En el área de los sistemas informáticos, la **programación lineal** se aplica de manera constante para resolver problemas complejos de optimización: - **Sistemas Operativos:** Planificación eficiente de procesos en CPU y asignación de memoria. - **Compiladores:** Asignación óptima de registros del procesador a variables. - **Bases de Datos:** Optimización de consultas y planificación de recursos de almacenamiento/red.

6. Respuesta correcta: B — Representación en forma estándar

Un problema de programación lineal se encuentra en **forma estándar** cuando reúne las siguientes condiciones: 1. La función objetivo busca maximizar o minimizar una combinación lineal de variables. 2. Todas las restricciones se expresan como **igualdades puras** ($A x = b$). 3. Todas las variables de decisión están restringidas a ser **no negativas** ($x_i \ge 0$). 4. Los términos independientes son no negativos ($b_i \ge 0$). Para llevar inecuaciones a la forma estándar se introducen variables de holgura o de exceso.

7. Respuesta correcta: B — Variables de holgura

Una **variable de holgura** ($s \ge 0$) es una variable auxiliar no negativa que se suma al miembro izquierdo de una restricción de menor o igual ($\le$) para transformarla en una igualdad estricta. **Ejemplo:** \[ 2x_1 + 3x_2 \le 12 \implies 2x_1 + 3x_2 + s_1 = 12 \quad \text{con } s_1 \ge 0 \] **Interpretación económica:** La variable $s_1$ representa la cantidad de recurso no consumido o sobrante de esa restricción concreta.

8. Respuesta correcta: A — Estructura de la función objetivo

La función objetivo en programación lineal siempre presenta la forma matemática de una **combinación lineal**: \[ f(x_1, x_2, \dots, x_n) = c_1 x_1 + c_2 x_2 + \dots + c_n x_n \] Donde los coeficientes $c_j$ son constantes conocidas que representan el peso, beneficio o coste unitario de cada variable $x_j$. **Regla clave:** No se admiten exponentes ($x^2$), productos entre variables ($x_1 \cdot x_2$), raíces ni funciones trascendentes ($\log, \sin$).

9. Respuesta correcta: B — Conversión de desigualdades a igualdades

Para pasar de inecuaciones a ecuaciones necesarias en la tabla Simplex: - En restricciones de tipo **$\le$**: Se **suma** una variable de holgura ($s_i \ge 0$). - En restricciones de tipo **$\ge$**: Se **resta** una variable de exceso ($e_i \ge 0$) y, si se requiere iniciar una base factible, se suma una variable artificial ($a_i \ge 0$).

10. Respuesta correcta: C — Forma canónica

En la literatura académica tradicional, un problema de programación lineal está en **forma canónica** de maximización cuando: 1. Se busca **maximizar** la función objetivo. 2. Todas las restricciones funcionales son desigualdades de tipo **menor o igual ($\le$)**. 3. Todas las variables de decisión satisfacen la condición de **no negatividad ($x_i \ge 0$)**. *(Nota: Aunque algunos textos intercambian la denominación entre estándar y canónica, la canónica se identifica de manera general por trabajar con inecuaciones y la estándar por usar ecuaciones reducidas).*

11. Respuesta correcta: C — Definición del problema dual

A cada problema de programación lineal (denominado **Primal**) le corresponde de forma matemática única un problema secundario asociado llamado **Problema Dual**. Las reglas de conversión entre el Primal y el Dual son: - Si el Primal **maximiza**, el Dual **minimiza** (y viceversa). - Los coeficientes $c_j$ de la función objetivo primal pasan a ser los términos independientes $b_j$ del dual. - Los términos independientes $b_i$ del primal pasan a ser los coeficientes $c_i$ de la función objetivo dual. - La matriz de coeficientes del dual es la **traspuesta ($A^T$)** de la matriz del primal.

12. Respuesta correcta: C — Utilidad del problema dual y Precios Sombra

La resolución del problema dual aporta información sobre la estructura y sensibilidad del problema primal: - **Teorema de Dualidad Fuerte:** Si el primal y el dual tienen soluciones óptimas, sus valores objetivos en el óptimo son **exactamente iguales** ($Z_{\text{primal}} = W_{\text{dual}}$). - **Precios Sombra (Shadow Prices):** Los valores óptimos de las variables duales $y_i$ indican cuánto aumenta el valor de la función objetivo por cada unidad adicional que se incremente en la disponibilidad del recurso $b_i$.

13. Respuesta correcta: C — Funcionamiento del algoritmo Simplex

Geométricamente, el conjunto de soluciones factibles define un polihedro o **politopo convexo** multidimensional. El **algoritmo Simplex**: 1. Comienza evaluando un vértice inicial. 2. Comprueba mediante los costes reducidos si moverse a un vértice adyacente mejora la función objetivo. 3. Se desplaza a lo largo de las aristas del politopo hasta llegar a un vértice donde ningún movimiento mejore el resultado, garantizando la solución óptima.

14. Respuesta correcta: C — Solución no acotada

Un problema de programación lineal es **no acotado** cuando la función objetivo puede crecer indefinidamente hacia $+\infty$ (en maximización) o disminuir hacia $-\infty$ (en minimización) sin salir de la región factible. **Causa:** Ocurre cuando la región factible no está cerrada en la dirección de mejora de la función objetivo o falta alguna restricción crítica en el modelo.

15. Respuesta correcta: B — Soluciones óptimas múltiples

Existen **múltiples soluciones óptimas** cuando la pendiente de la función objetivo es exactamente paralela a la pendiente de una de las restricciones activas que delimitan la región factible. Geométricamente: - El valor óptimo no se alcanza solo en un único vértice aisladamente, sino en **todos los puntos pertenecientes a la arista o cara** del politopo que conecta los vértices óptimos. - El problema tiene infinitas soluciones factibles que otorgan exactamente el mismo beneficio o coste máximo/mínimo.

Chuleta final: lo imprescindible para aprobar¶

1. Elementos del modelo de Programación Lineal (PL)¶

Variables de decisión: $x_1, x_2, \dots, x_n \ge 0$.
Función objetivo: $Z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n$ (Maximizar o Minimizar).
Restricciones: $a_{i1} x_1 + a_{i2} x_2 + \dots + a_{in} x_n \ (\le, =, \ge) \ b_i$.

2. Formas del problema¶

Característica	Forma Canónica (Max)	Forma Estándar
Función Objetivo	Maximizar	Maximizar o Minimizar
Restricciones	Inecuaciones ($\le$)	Igualdades estrictas ($Ax = b$)
Variables	$x_i \ge 0$	$x_i \ge 0$ (Añade variables $s_i$ de holgura)

3. Conceptos del Algoritmo Simplex¶

Región factible: Conjunto convexo definido por la intersección de todas las restricciones.
Variables de holgura ($s_i \ge 0$): Se suman en restricciones $\le$ para convertirlas en igualdades.
Variables de exceso ($e_i \ge 0$): Se restan en restricciones $\ge$.
Solución Básica Factible (SBF): Corresponde a un vértice del politopo de la región factible.
Criterio de parada: Cuando no hay costes reducidos que permitan mejorar el valor de $Z$.

4. Relación Primal - Dual¶

Matriz de coeficientes: Se traspone ($A \to A^T$).
Vectores de costes y recursos: Se intercambian ($c \leftrightarrow b$).
Dualidad Fuerte: En el óptimo, $Z_{\text{primal}} = W_{\text{dual}}$.
Precio Sombra ($y_i$): Representa la tasa de cambio del valor óptimo por cada unidad adicional del recurso $i$.

5. Tipos de soluciones en PL¶

Óptimo Único: Se alcanza en un solo vértice del politopo.
Óptimos Múltiples: La función objetivo es paralela a una restricción; infinitos puntos sobre una cara/arista dan el mismo valor.
Infactible: La región factible es vacía (no hay ningún punto que cumpla todas las restricciones a la vez).
No Acotado: La función objetivo puede crecer/decrecer indefinidamente sin violar las restricciones.