Introducción
Ya hablamos de qué es la forma canónica y la forma estándar de un problema lineal. Como platicamos, esto nos permitirá llevar los problemas que nos interesan a ciertas formas especiales a las que podremos aplicarles algunos métodos más adelante. Lo que haremos ahora es comenzar a pensar en qué quiere decir resolver un problema lineal. Para ello, recordaremos de distintos tipos de soluciones que los problemas lineales pueden tener.
Tipos de soluciones y región de factibilidad
En esta sección recordaremos los conceptos de soluciones factibles, soluciones básicas factibles (degeneradas y no degeneradas) y de región de factibilidad.
Supongamos que tenemos un problema de programación lineal en su forma canónica:
donde usamos la misma notación que en la entrada anterior, pero donde tomaremos
Este problema también tiene una forma estándar, en donde transformamos las desigualdades en igualdades introduciendo variables de sobra y de holgura.
en donde en hemos agregado
Como recordatorio, tenemos las siguientes definiciones para los tipos de soluciones del problema lineal.
Definición. Una solución factible al problema lineal en forma canónica dado anteriormente es un vector columna
Definición. La región de factibilidad del problema lineal en forma canónica es el conjunto de todas las soluciones factibles.
De entre las soluciones factibles, hay algunas que son un poco más sencillas, en el sentido de que varias de sus entradas son iguales a cero pensadas como soluciones del problema en forma estándar. En las siguientes definiciones suponemos que el rango de la matriz
Definición. Una solución básica factible es una solución factible
Definición. Una solución básica factible no degenerada es una solución factible
Definición. Una solución básica factible degenerada es una solución factible
La importancia de las soluciones básicas factibles y no degeneradas es que cumplen las siguientes:
- Se puede mostrar que si un problema de programación lineal tiene óptimo, entonces dicho óptimo se alcanza para alguna solución básica factible y no degenerada.
- Las soluciones básicas factibles y no degeneradas se pueden encontrar resolviendo sistemas de ecuaciones.
- Geométricamente, las soluciones básicas factibles y no degeneradas están en vértices de la región de factibilidad.
A continuación explicaremos algunos de estos puntos con un ejemplo detallado, que te ayudará a entender la intuición detrás de estas definiciones y de su importancia.
Ejemplos de región de factibilidad y tipos de solución
Consideremos el siguiente problema de programación lineal:
Antes de comenzar a estudiar la región de factibilidad, debemos verificar que está en forma canónica. En efecto, todo está en orden: el problema es de maximización, las desigualdades son
La región de factibilidad es el conjunto de todos los
Región 1: La región
Región 2: La región
Región 3: La región
Región 4: La región
Como queremos que
Si gustas, puedes también explorar el interactivo de GeoGebra en donde se han coloreado los complementos de las regiones para más claridad. Puedes usar el cursor para mover la figura y las herramientas de lupa para hacer acercamientos y alejamientos.
La intuición que debemos tener ahora es que el máximo de la función objetivo
Para ello, pensemos al problema en su forma estándar, tomando variables de holgura
La matriz
que tiene solución única
Esta solución corresponde al punto
y tras resolver las dos ecuaciones, la solución básica que se obtiene es
Podemos seguir haciendo esto. Si consideramos todas las posibilidades en las que dos variables son cero y resolvemos las ecuaciones resultantes, eso nos dará puntos
En este ejemplo tenemos
La siguiente tabla muestra todas las soluciones básicas y no básicas de este ejemplo:
Variables no básicas (cero) | Variables básicas | Solución para | Punto de esquina asociado | ¿Factible? | Valor objetivo z |
C | Sí | 0 | |||
E | No | ___ | |||
D | Sí | 7.5 | |||
B | Sí | 4 | |||
F | No | ___ | |||
A | Sí | 8 (óptimo) |
Más adelante…
Notemos que a medida que el tamaño del problema se incrementa, enumerar todos los puntos esquina se volverá una tarea que tomaría mucho tiempo. Por ejemplo, si tuviéramos
Por ello, se vuelve cruciar encontrar un método que atenúe esta carga computacional en forma drástica, que permita investigar sólo un subconjunto de todas las posibles soluciones factibles básicas no degeneradas (vértices de la región de factibilidad), pero que garantice encontrar el óptimo. Una idea intuitiva que debería servir es comenzar en un vértice y «avanzar en una dirección que mejore la función objetivo». Esto precisamente es la intuición detrás del método simplex, que repasaremos a continuación.
Tarea moral
- Considera el siguiente problema lineal en su forma canónica:
Sigue los pasos descritos arriba para encontrar todas sus soluciones básicas factibles y no degeneradas. Usa ello para encontrar el óptimo del problema.
- Actualiza las restricciones en el interactivo de GeoGebra que se compartió en la entrada para visualizar este problema y confirmar tus cuentas del ejercicio anterior. Para ello, deberás ir al apartado «Álgebra» del interactivo y modificar los objetos
y . - Considera un problema de optimización lineal en dos variables
y , en forma canónica y con restricciones (desigualdades), además de las restricciones y . Explica por qué la región de factibilidad siempre es un polígono con a lo más lados, y por qué entonces basta evaluar la función objetivo en a lo más puntos para encontrar su máximo. - ¿Cómo se vería la región de factibilidad de un problema de optimización lineal de maximización que no tenga máximo? Explica todas las posibilidades y da ejemplos.
- Intenta usar las ideas de esta entrada para resolver los problemas de optimización lineal clásicos que hemos descrito en entradas anteriores.
Entradas relacionadas
- Ir a Investigación de Operaciones
- Entrada anterior del curso: Forma canónica y forma estándar de un problema lineal
- Entrada siguiente del curso: