Test Tema 5 — Programación lineal, Simplex y dualidad¶
Practica las 15 preguntas del test. Marca una opción en cada pregunta y pulsa Corregir test para obtener tu nota, ver las respuestas correctas y leer las explicaciones.
Puntuación
Las preguntas 1–5 y 11–15 valen 0,70 puntos; las preguntas 6–10 valen 0,60 puntos. Total: 10 puntos.
Chuleta final — Programación lineal¶
1. ¿Qué es?¶
La programación lineal busca maximizar o minimizar una función lineal respetando restricciones lineales.
- Variables de decisión: lo que podemos elegir (por ejemplo, cuántas unidades fabricar).
- Función objetivo: lo que queremos optimizar (beneficio, coste, tiempo…).
- Restricciones: límites de recursos, capacidad, demanda, etc.
- No negatividad: normalmente \(x_i\geq0\).
Forma general:
sujeto a restricciones lineales.
2. Región factible y solución óptima¶
- La región factible contiene todos los puntos que cumplen todas las restricciones.
- Una solución factible cumple las restricciones, pero no tiene por qué ser óptima.
- Una solución óptima es la factible que da el mejor valor de la función objetivo.
- En programación lineal, todo óptimo alcanzado es global.
- Puede haber un óptimo único o varios óptimos.
3. Forma canónica y forma estándar¶
La nomenclatura cambia entre manuales. Una convención frecuente es:
| Forma | Restricciones | No negatividad |
|---|---|---|
| Canónica | Desigualdades (p. ej. \(Ax\leq b\)) | \(x\geq0\) |
| Estándar | Igualdades (\(Ax=b\)) | \(x\geq0\) |
Lo importante es identificar qué representación está usando el temario.
4. Variables de holgura y exceso¶
Para convertir una desigualdad en igualdad:
- Si es ≤, añadimos holgura: \(2x+y\leq8\) pasa a \(2x+y+s=8\), con \(s\geq0\).
- Si es ≥, restamos una variable de exceso: \(2x+y\geq8\) pasa a \(2x+y-e=8\), con \(e\geq0\).
La holgura representa recurso que queda sin utilizar. El exceso representa cuánto se supera un mínimo exigido.
5. Algoritmo Simplex¶
- Se parte de una solución básica factible (un vértice de la región factible).
- Se elige una variable entrante para mejorar la función objetivo.
- Se determina qué variable sale mediante el criterio de razón.
- Se pivota para pasar a otro vértice.
- Se repite hasta que no se puede mejorar el objetivo.
Simplex funciona también con más de dos variables; el dibujo en dos dimensiones es solo una ayuda visual.
6. Dualidad¶
Todo problema lineal (primal) tiene asociado un problema dual.
- Las variables del dual se relacionan con las restricciones del primal.
- Las restricciones del dual se relacionan con las variables del primal.
- La matriz de coeficientes se transpone.
- Bajo las condiciones habituales, los valores óptimos del primal y del dual coinciden (dualidad fuerte).
- Las variables duales suelen interpretarse como precios sombra de los recursos.
7. Situaciones que pueden aparecer¶
| Situación | Significado |
|---|---|
| Óptimo único | Un único punto alcanza el mejor valor |
| Óptimos múltiples | Varios puntos alcanzan el mismo mejor valor |
| Problema infactible | No existe ningún punto que cumpla todas las restricciones |
| Problema no acotado | La función objetivo puede mejorar indefinidamente |
No confundas
- Infactible no es lo mismo que no acotado: en el primero no hay soluciones factibles; en el segundo sí las hay, pero el objetivo puede mejorar sin límite.
- Solución factible no significa necesariamente solución óptima.
- La holgura se añade a restricciones de tipo ≤; para restricciones ≥ se utiliza una variable de exceso.