Si eres ingeniero o estudiante de ingeniería, quizás sepas lo que significa optimizar.
Para obtener el mejor resultado posible, es importante encontrar la mejor manera de hacer las cosas.
En programación lineal, puede usar una solución básica para encontrar la mejor solución.
Pero, ¿qué es una solución básica y por qué es tan importante que los ingenieros las conozcan? En este artículo, hablaré sobre qué son las soluciones básicas, por qué son importantes en ingeniería y cómo se pueden usar para obtener los mejores resultados en diferentes situaciones.
Así que abróchese el cinturón y prepárese para sumergirse en el mundo de las soluciones básicas, donde desglosaré los misterios y le mostraré lo poderosa que puede ser esta técnica.
Soluciones Básicas en Programación Lineal
Definicion formal:
Se obtiene una solución para un modelo de programa lineal que consta de m ecuaciones en n variables resolviendo m variables en términos de las (nm) variables restantes y estableciendo las (nm) variables iguales a cero.
Una solución básica en programación lineal es una forma de resolver un problema de programación lineal que cumple con ciertos requisitos técnicos.
En particular, un vector x es una solución básica para un poliedro si los vectores {ai : xi = 0} son linealmente independientes.
Esto significa que las columnas de A que tienen variables xi que no son cero son linealmente independientes.
Una solución básica con componentes no negativos se denomina solución factible básica (BFS) (BFS).
Un BFS cumple con todas las reglas que definen un poliedro.
Cada BFS es una esquina del poliedro de soluciones factibles desde un punto de vista geométrico.
Para encontrar una solución básica, debe establecer nm variables que no son básicas en cero y resolver las m variables que son básicas.
Es posible que diferentes bases conduzcan a la misma solución básica, lo que significa que puede haber más de una forma de resolver el mismo problema.
El Método Simplex es un proceso iterativo que pasa de un BFS al siguiente BFS hasta que encuentra el mejor BFS.
Después de usar el método simplex para encontrar un BFS, podemos saber si la solución es la mejor viendo si algún otro BFS cercano da un mejor valor para la función objetivo.
Si no existe tal BFS, entonces el BFS actual es el mejor.
Modelo de programación lineal
Un modelo de programación lineal involucra tres componentes principales: variables de decisión, una función objetivo y restricciones.
Tanto la función objetivo como las restricciones deben ser funciones lineales y las variables de decisión deben ser continuas.
La función objetivo se usa para aumentar o disminuir un número que representa ganancias, costos, cantidad de productos fabricados, etc.
Las restricciones son límites o restricciones sobre la cantidad total de un determinado recurso que se necesita para realizar las tareas que determinarán el nivel de éxito en las variables de decisión.
Además, algunos programas lineales requieren que todas las variables de decisión sean no negativas.
En los modelos de programación lineal, también puede utilizar variables enteras y binarias.
Las variables binarias solo pueden tener un valor de 0 o 1, por lo que solo pueden tener un valor de 0 o 1.
El método símplex
Una de las formas más utilizadas para resolver problemas de programación lineal es el Método Simplex.
Las soluciones básicas son importantes en el método simplex porque corresponden a los puntos de esquina de la región factible, y el método simplex se mueve de una esquina a otra hasta que se encuentra una solución óptima.
El método símplex es una forma rápida de encontrar la mejor respuesta a un problema de programación lineal utilizando las propiedades de las soluciones básicas.
Para usar el método símplex para encontrar el mejor BFS, necesitamos encontrar una base B para la matriz de restricciones A y resolver el sistema Ax = b con todas las variables excepto la base puestas a cero.
Los valores resultantes para las variables básicas forman un BFS.
Si existe una solución óptima, entonces existe un BFS óptimo.
El Método Simplex se mueve de un BFS a un BFS adyacente hasta que alcanza un BFS óptimo mediante el uso de procedimientos de pivote.
Comparación entre Soluciones Básicas y Soluciones Factibles
La diferencia entre una solución básica y una solución factible es que una solución básica no tiene que cumplir ninguna condición.
En particular, debe tener vectores que sean linealmente independientes y que tengan valores distintos de cero para xi, y x debe ser menor que 0.
Por otro lado, una solución factible es cualquier punto que se ajuste a los límites del problema.
Pero no todas las soluciones factibles son soluciones factibles básicas.
Las soluciones factibles básicas (BFS) son solo aquellas que coinciden con las esquinas del poliedro de soluciones factibles.
Volver a lo básico: liberando el poder de las soluciones básicas en ingeniería
¿Todavía es difícil de entender? Déjame cambiar un poco el punto de vista:
¿Estás harto de usar métodos y algoritmos complicados para resolver problemas difíciles? ¿Le gustaría que hubiera una forma más simple y directa de tratar sus problemas de modelo de programa lineal?
Bueno, no se preocupe, porque la respuesta está aquí: resuelva m variables en términos de las variables restantes (nm) y establezca las variables (nm) en cero.
¿Quién necesita algoritmos que suenen elegantes cuando puede volver a lo básico? Así que guarde sus calculadoras y comencemos a aprender sobre soluciones simples.
De acuerdo, solo fue una broma hecha para parecer un anuncio de televisión.
Ahora volvamos a la explicación.
Solución Básica Programación Lineal
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: | La solución básica se puede utilizar en problemas de asignación de recursos, donde el objetivo es dividir los recursos limitados entre necesidades en competencia. Por ejemplo, una empresa puede necesitar dividir su presupuesto entre diferentes departamentos o proyectos. Mediante el uso de soluciones básicas, pueden descubrir la mejor manera de utilizar sus recursos para ganar la mayor cantidad de dinero o gastar lo menos posible. |
| Planificación para la producción: | En la planificación de la producción, la solución básica se puede utilizar para determinar la mejor combinación de productos para hacer la mayor cantidad de dinero. Las empresas pueden encontrar la mejor combinación de producción que genere la mayor cantidad de dinero y cueste menos al usar la solución básica. |
| Planificación: | La solución básica se puede utilizar para descubrir cómo programar tareas o trabajos para que se puedan realizar de la manera más eficiente. Por ejemplo, una empresa puede necesitar planificar las horas de trabajo de sus empleados para asegurarse de que tengan suficientes trabajadores cuando el negocio esté ocupado. Mediante el uso de una solución básica, pueden descubrir la mejor manera de programar las cosas para que haya el menor tiempo de inactividad posible y se realice la mayor cantidad de trabajo posible. |
| Gestión de la Cadena de Suministro: | En la gestión de la cadena de suministro, el objetivo es asegurarse de que los bienes y servicios se muevan de la mejor manera posible desde el proveedor hasta el cliente. Por ejemplo, una empresa puede necesitar averiguar las mejores rutas para el transporte de bienes para que los costos se mantengan al mínimo y los bienes se entreguen a tiempo. Mediante el uso de soluciones básicas, pueden encontrar el mejor plan para administrar la cadena de suministro que mantiene los costos bajos y mantiene contentos a los clientes. |
| Optimización de la cartera: | En la optimización de la cartera, donde el objetivo es encontrar la mejor combinación de inversiones para ganar la mayor cantidad de dinero y asumir el menor riesgo, se pueden utilizar soluciones básicas. Por ejemplo, es posible que una empresa de inversiones deba descubrir la mejor combinación de acciones, bonos y otros valores para ayudar a sus clientes a alcanzar sus objetivos de inversión. Mediante el uso de una solución simple, pueden encontrar la mejor manera de mezclar sus carteras para obtener los mejores rendimientos asumiendo la menor cantidad de riesgo. |
Conclusión
En conclusión, la idea de una solución básica es muy importante en el campo de la ingeniería y se puede utilizar de muchas maneras diferentes.
Al saber qué es una solución básica y qué hace en la programación lineal, podemos mejorar las soluciones, reducir costos y hacerlas más eficientes.
Pero es importante recordar que la solución básica no es una solución única para todos, a pesar de que es una herramienta poderosa.
Para obtener los mejores resultados, cada problema debe analizarse y pensarse cuidadosamente.
Como ingenieros, debemos seguir investigando cómo las soluciones básicas y otras técnicas de optimización pueden ayudarnos a progresar y generar nuevas ideas.
Entonces, reconozcamos el poder de las soluciones simples y sigamos empujando los límites de lo que es posible mediante el uso de nuevas técnicas y estrategias.
Enlaces y referencias
Libros:
- Programación lineal por Vasek Chvatal
- Modelando y Resolviendo Programación Lineal con R por Jose M. Sallan
Compartir en…
