Ya sabes lo que significa optimizar un sistema para obtener el mejor resultado posible si eres estudiante de ingeniería o ingeniero.
La optimización de una solución es la clave del éxito en todo, desde la construcción de puentes hasta la creación de software.
La idea de una solución factible básica surge en este punto.
Es una idea básica en la programación lineal que le permite averiguar cuál de un conjunto de posibles soluciones es la mejor.
Pero ¿por qué importa tanto? En este artículo, hablaré sobre soluciones factibles básicas y cómo se pueden usar para resolver problemas de ingeniería en el mundo real.
Hablaré sobre cómo encontrarlos, de qué están hechos y por qué son importantes.
Entonces, ya sea que sea un ingeniero experimentado o un estudiante que recién comienza, acompáñenos mientras me sumerjo en el mundo de las soluciones factibles básicas y le mostraré cómo usar el poder de la programación lineal.
Comprender la solución factible básica
Definicion formal:
Una solución básica para un modelo de programa lineal en el que todas las variables son no negativas.
Una solución factible básica (BFS) es una idea clave en la programación lineal que ayuda a encontrar las mejores soluciones.
Un BFS es una solución con el menor número posible de variables distintas de cero.
Es una esquina del poliedro de soluciones factibles.
En otras palabras, un BFS es una solución básica que cumple con las restricciones no negativas y se encuentra en la región factible o área del problema.
Encontrar una solución factible básica óptima
Para encontrar el mejor BFS, debemos hacer lo siguiente:
- Escriba el programa en forma estándar para una secuencia lineal.
- Convierte el sistema de desigualdades en una matriz aumentada.
- Averigua qué variables son básicas y cuáles no.
- Averigüe cuáles son las variables básicas en términos de las otras variables.
- Coloque estas expresiones en la función objetivo para obtener una función de solo las variables que no son básicas.
- Encuentre una variable no básica que se pueda aumentar sin romper ninguna restricción y que mejore la función objetivo.
Esta variable ahora es una variable básica, y una de las otras variables básicas ya no es una variable básica.
Si hay una solución óptima, debe estar en uno de los extremos, o vértices, de la región donde las soluciones son posibles.
Entonces, si un PL tiene una solución óptima, tiene una solución óptima en un punto extremo del conjunto factible.
Además, siempre hay un BFS óptimo si hay una solución óptima.
Uso del método Simplex para encontrar un BFS óptimo
El Método Simplex es un algoritmo para resolver problemas de programación lineal.
Se mueve de un BFS a un BFS "adyacente" mediante el procedimiento de pivote.
En el procedimiento de pivote, se elige una variable no básica para que se convierta en una variable básica y luego se usa el BFS actual para resolver las nuevas variables básicas.
Cuando no se puede cambiar ninguna variable no básica para mejorar la función objetivo, el algoritmo está listo.
Por qué las soluciones factibles básicas son cruciales para resolver problemas de ingeniería complejos
¿Todavía es difícil de entender? Déjame cambiar un poco el punto de vista:
¿Quién necesita respuestas simples y viables de todos modos? Solo junta todo y espera lo mejor.
Después de todo, ¿quién necesita optimización cuando el caos es mucho más divertido? Bienvenido al mundo de las variables no negativas, donde todo es solo una sugerencia y el fracaso es casi seguro.
¿O es eso?
Exploremos por qué el concepto aparentemente básico de soluciones factibles básicas es todo menos básico y por qué podrían ser la clave para resolver incluso los problemas de ingeniería más complejos.
De acuerdo, solo fue una broma hecha para parecer un anuncio de televisión.
Ahora volvamos a la explicación.
Encontrar una solución factible básica
Una solución factible básica (BFS) es una solución a un problema de optimización lineal que cumple con todas las restricciones y tiene la menor cantidad de variables distintas de cero.
Cada BFS es una esquina del poliedro de soluciones factibles desde un punto de vista geométrico.
Si hay una mejor solución, también debe haber un mejor primer paso.
En este artículo, hablaremos sobre cómo encontrar una solución factible básica inicial, cómo encontrar todas las soluciones factibles básicas y cómo encontrar una solución factible básica sin variables de holgura.
Encontrar una solución factible básica inicial
Podemos usar diferentes métodos, dependiendo de cómo esté planteado el problema, para encontrar una solución básica inicial que funcione para un problema de optimización lineal.
Una forma es agregar variables de holgura a las restricciones sobre las desigualdades y establecer todas las demás variables en cero.
Las variables de holgura se convierten en las variables básicas, y el resto son variables no básicas.
El Método Simplex de dos fases es otra forma de resolver el problema.
Este método implica resolver un problema de programación lineal adicional para encontrar una solución básica inicial que sea factible.
Una vez que se ha encontrado una solución factible básica inicial, se puede usar el Método Simplex para pasar de una solución factible básica a la siguiente y luego a la mejor solución.
Encontrar todas las soluciones factibles básicas
Puede haber más de una solución básica que funcione para un programa lineal.
Podemos cambiar el sistema agregando variables de holgura y luego usar el nuevo sistema para encontrar todas las soluciones factibles básicas para un programa lineal.
Luego, estas soluciones factibles básicas se utilizan para encontrar las soluciones factibles básicas para el problema original.
Encontrar una solución factible básica sin variables de holgura
Necesitamos usar variables de holgura para deshacernos de las restricciones menores que para que podamos encontrar una solución básica que funcione sin variables de holgura.
Una variable de holgura es solo la diferencia entre el lado derecho de una restricción y el lado izquierdo.
Por ejemplo, para la primera restricción, definimos una variable de holgura x4 = 14 - 2x1 - x2 - x3. En términos de esta nueva variable, la primera restricción es equivalente simplemente a x4 ≥ 0, que es una restricción de positividad para x4.
Cuando agregamos estas variables de holgura, obtenemos un programa lineal que es igual al original, excepto que todas las restricciones son ecuaciones o restricciones que dicen que algo es positivo.
El conjunto de variables básicas, que tienen valores distintos de cero en la solución básica, se denomina base.
Las variables que tienen un valor de cero en la solución básica no son variables básicas.
Para encontrar la mejor solución, necesitamos encontrar un vector x que cumpla con todas las reglas y obtenga el valor más grande o más pequeño para el objetivo.
Pero encontrar la mejor solución requiere más pasos que solo encontrar una solución que funcione y no tenga variables de holgura.
No siempre es posible encontrar una solución básica sin variables de holgura, especialmente para problemas con restricciones menores.
Para encontrar una solución factible básica, debe usar el método simplex u otro algoritmo de programación lineal para buscar una solución que cumpla con todas las restricciones y tenga la menor cantidad de variables distintas de cero.
Propiedades y significado de la solución factible básica
Propiedades de la solución factible básica
Una solución factible básica tiene como máximo m variables que no son cero y al menos nm variables que son cero, donde n es el número de variables de decisión y m es el número de restricciones.
Un BFS es una esquina del poliedro de posibles soluciones, y cada BFS tiene n restricciones activas que son linealmente independientes.
Si hay una mejor solución, también debe haber un mejor primer paso.
Lo más importante de las soluciones factibles básicas es que son los extremos del conjunto de soluciones convexas para un problema de programación lineal.
Para encontrar la mejor respuesta, el algoritmo símplex pasa por una serie de BFS.
El Algoritmo Simplex busca a través de todas las posibles soluciones básicas de forma organizada para encontrar la mejor.
Importancia de la solución factible básica
Encontrar una solución básica que sea posible es importante porque ayuda a encontrar la mejor respuesta a los problemas de programación lineal.
También le da a los algoritmos complejos un lugar para comenzar y puede usarse para determinar si un programa lineal es posible o no.
Para encontrar todas las soluciones factibles básicas para un programa lineal, puede cambiar el sistema agregando variables de holgura y luego usar el sistema modificado para encontrar todas las soluciones factibles básicas.
Luego, estas soluciones factibles básicas se utilizan para encontrar las soluciones factibles básicas para el problema original.
Video: Soluciones factibles básicas
Sugerencia: Active el botón de subtítulos si lo necesita. Elija "traducción automática" en el botón de configuración, si no está familiarizado con el idioma hablado. Es posible que primero deba hacer clic en el idioma del video antes de que su idioma favorito esté disponible para la traducción.
casos de uso
| Utilizada en: | Descripción: |
|---|---|
| Asignación de recursos: | BFS se puede utilizar para dividir recursos limitados entre varios proyectos para que se pueda hacer lo máximo con lo mínimo. Este método se puede utilizar en muchos campos diferentes, como el transporte, la agricultura y las finanzas. |
| Optimización de la Red: | BFS se puede utilizar para mejorar el funcionamiento de las redes de comunicación, transporte y logística. BFS puede ayudar a encontrar las mejores rutas para bienes y servicios, reducir el tiempo y el dinero gastado en transporte, y acelerar y realizar entregas más precisas. |
| Planificación para la producción: | BFS se puede utilizar para planificar la producción de modo que los recursos como la mano de obra, las materias primas y los equipos se utilicen de la mejor manera posible para aprovecharlos al máximo. BFS puede ayudar a reducir los costos de producción, reducir los desechos y mejorar la eficiencia. |
| Planificacion Financiera: | En la planificación financiera, BFS se puede utilizar para optimizar carteras de inversión, reducir el riesgo y recuperar la mayor cantidad de dinero. BFS puede ayudar a encontrar la mejor manera de dividir los activos, reducir los costos de transacción y ganar más dinero. |
| Gestión de la Cadena de Suministro: | BFS se puede utilizar para mejorar el flujo de bienes y servicios de los proveedores a los clientes como parte de la gestión de la cadena de suministro. BFS puede ayudar a determinar la mejor cantidad de existencias para tener disponible, acortar los plazos de entrega y mejorar el servicio al cliente. |
Conclusión
A medida que esta mirada a las soluciones factibles básicas llega a su fin, está claro que son una herramienta importante para cualquier ingeniero o estudiante de ingeniería.
Desde descubrir la mejor manera de construir un sistema complicado hasta aprovechar al máximo los recursos disponibles, las soluciones factibles básicas proporcionan un marco para obtener el mejor resultado posible.
Pero más que ser útiles, muestran lo elegantes y hermosas que pueden ser las matemáticas.
Es sorprendente que puedas reducir problemas complicados a un conjunto simple de ecuaciones y luego usar esas ecuaciones para resolver problemas en el mundo real.
Es un buen recordatorio de que la ingeniería se trata de resolver problemas y que, al usar el poder de las matemáticas, podemos encontrar respuestas que antes se creían imposibles.
Por lo tanto, a medida que aprenda más sobre ingeniería, tenga en cuenta lo que ha aprendido sobre soluciones simples que funcionan y utilícelas para hacer del mundo un lugar mejor y más eficiente.
Enlaces y referencias
Libros:
- Programación Lineal: Fundamentos y Extensiones
- Programación Lineal: Teoría y Aplicaciones
Compartir en…
