Para buscar en este sitio, trate Edit | Find in page [Ctrl + f]. Escriba la palabra o frase, ej. "parámetro " o "lineal " Si la primera palabra o frase encontrada no es lo que busca, trate Find Next.
MENU
- Introducción
- Problema de PL Solucionado con el solver (solucionista) para Sistema de Ecuaciones.
- Solución de Sistemas de Ecuaciones con el solver (solucionista) para PL
- Solucionar el Inverso de una Matriz usando el solver (solucionista) para PL
- Solucionar un problema de PL usando un Solver (solucionista) para una Matriz Inversa
- Solucione un Sistema de Ecuaciones usando un Solver (solucionista) para el Inverso de la Matriz
- Encontrar el Inverso de una Matriz utilizando un Solver (solucionista) para Sistema de Ecuaciones
- Inversión de la Matriz: Un enfoque del Álgebra Computacional
- Objetos de Aprendizaje: El Solver Interactivo en Línea
- Redondeando Errores y Análisis de Estabilidad
- Comentarios de Conclusión
- Referencias y Lecturas Adicionales
Introducción
La programación lineal (PL), los sistemas Lineales de ecuaciones, e inversión de la Matriz son a menudo temas favoritos tanto para instructores como para estudiantes. La capacidad de solucionar estos problemas por el método de pivotaje de Gauss-Jordan (GJP, Gauss-Jordan pivoting), la disponibilidad extendida de paquetes de software, y su amplia variedad de aplicaciones hacen estos temas accesibles hasta para estudiantes con conocimientos matemáticos relativamente limitados. Los libros tradicionales de texto de PL por lo general dedican secciones separadas para cada tema. Sin embargo, las relaciones tan estrechas entre estos temas a menudo no son presentadas o discutidas a fondo. Este artículo amplía las relaciones unidireccionales existentes entre estos temas para construir una relación bi-direccional completa como en la figura siguiente. Para cada tema es mostrado como el problema puede ser modelado y solucionado por cualquiera de las metodologías asociadas.
Los enlaces adicionales introducidos aquí, le permiten al usuario entender, modelar y solucionar un problema modelado como cualquiera de estos mencionados, teniendo acceso a un paquete de computadora Solver (solucionista). Los objetivos son la unificación teórica así como también los avances en las aplicaciones. Las siguientes seis secciones desarrollan los enlaces que son ilustrados con pequeños ejemplos numéricos. Aunque algunos de estos ejemplos son completamente conocidos, los incluimos aquí para su entendimiento.
Problema de PL Solucionado con el solver (solucionista) para Sistema de Ecuaciones.
Esta sección es probablemente una de las más conocidas debido a que muchas introducciones al Método del Simplex Simplex Method de la programación lineal (PL) son desarrolladas utilizando un enfoque de sistema de ecuaciones lineales.
Las coordenadas de los vértices son la solución básica factible de los sistemas de ecuaciones obtenidas poniendo algunas restricciones en la situación límite (es decir, igualdad). Para una región factible limitada, el número de vértices es a lo mas el valor combinatorial Cpq donde p es el número de restricciones y q es el número de variables. Por lo tanto, tomando cualquier ecuación q, y solucionando simultáneamente, uno obtiene una solución básica (si ésta existe). Sustituyendo esta solución básica en las restricciones de otras ecuaciones, uno puede comprobar la viabilidad de la solución básica. Si es factible, entonces esta solución es una solución factible básica que proporciona las coordenadas de un punto de esquina de la región factible.
Cada solución de cualquier sistema de ecuaciones es llamada una Solución Básica (SB). Aquellas Soluciones Básicas que son factibles son llamadas Soluciones Básicas Factibles (SBF). Los vértices de conjunto S son el SBF.
Supongamos que tenemos el siguiente problema de PL con todas las variables sin restricciones en el signo:
Max X1 + X2
Sujeto a:
X1 + X2 ³ 10
X1 £ 8
X2 £ 12
Para ilustrar el procedimiento, coloque todas las restricciones en su situación límite (es decir, igualdad). El resultado es el siguiente conjunto de 3 ecuaciones con 2 incógnitas:
X1 + X2 = 10
X1 = 8
X2 = 12
Aquí tenemos p=3 número de ecuaciones con q=2 número de incógnitas. ¡En términos de “coeficiente binomial", hay como máximo C32 = 3! / [2! (3-2)!] = 3 soluciones básicas. Solucionando los tres sistemas de ecuaciones resultantes, tenemos:
| X1 | X2 | X1 + X2 |
| 8 | 2 | 10 |
| 8 | 12 | 20* |
| -2 | 12 | 10 |
La solución óptima es X1 = 8, X2 = 12, con el valor óptimo de 20.
Para más detalles y ejemplos numéricos visite la pagina de Internet Solution Algorithms for LP Models .
Solución de Sistemas de Ecuaciones con el solver (solucionista) para PL
Supongamos que tenemos un sistema de ecuaciones que nos gustaría solucionar y un Solver de PL, pero no tenemos un Solver para el sistema de ecuaciones disponibles. Para solucionar como un problema de PL añada una función objetiva independiente (dummy), y para generalizar asumimos que las variables no tienen restricción en su signo. Entonces sustituimos Xi = yi - z, en todas partes. Esta substitución debe ser hecha ya que muchos paquetes de PL como LINDO, y QSB asumen que las variables son no negativas.
Por ejemplo, para solucionar el siguiente sistema de ecuaciones
2X1 + X2 = 3
X1 -X2 = 3
Convierta al problema de LP siguiente:
Max (or min) Dummy, por ejemplo Max (o min) z,,
sujeto a: 2y1 + y2 - 3z = 3, y y1 - y2 = 3
Usando cualquier Solver de PL como LINDO encontramos que la solución óptima es y1 = 3, y2 = 0, z = 1. Por lo tanto, la solución con el sistema original de la ecuación es X1 = 3-1 = 2, X2 = 0 - 1 =-1.
Solucionando el Inverso de una Matriz Usando el solver (solucionista) para PL
Para encontrar el inverso de la matriz AnXn solucionamos una serie de n problemas de PL para encontrar la inversa columna por columna. Por ejemplo, para encontrar la primera columna de la matriz inversa solucione
Max Dummy
sujeto a: AX - z [SA1j , SA2j ,.... , SAnj] T = (1, 0, 0, .....0)T
La primera columna de A-1 es entonces (X1*- z*, X2*- z*, ...Xn*- z* )T
Suponga que deseamos encontrar la inversa de la siguiente matriz (si ésta existe)
| 2 | 1 | ||
| A | = | ||
| 1 |
|
Para encontrar la primera columna de A -1 use el Solver de PL para solucionar
Max Dummy
Sujeto a: 2X1 + X2 - 3z =1, and X1 - X2 = 0
La solución óptima es X1 = 1/3, X2 = 1/3, and z = 0. Por lo tanto la primera columna de A -1 is [1/3 - 0, 1/3 - 0]T = [1/3, 1/3]T. Para calcular la segunda columna solucione
Max Dummy
Sujeto a: 2X1 + X2 - 3z =0, and X1 - X2 = 1
La solución óptima es X1 = 1, X2 = 0, and z = 2/3. Por lo tanto la segunda columna de A -1 es [1 - 2/3, 0 - 2/3]T = [1/3, -2/3]T. Por lo tanto la matriz inversa es:
| 1/3 | 1/3 | ||
| A-1 | = | ||
| 1/3 |
|
Nota: La matriz que posee un inverso es llamada no singular, o invertible. La matriz se llama singular si ésta no tiene un inverso. Por ejemplo, la matriz siguiente es singular:
1 6 4
2 4 -1
-1 2 5
Por lo tanto, en la aplicación del procedimiento previo para invertir una matriz, si la matriz es singular, entonces no existe una solución óptima.
Solucionar un problema de PL usando un Solver(solucionista) para una Matriz Inversa
Para solucionar un problema de PL encontramos la inversa de cada matriz base con el número apropiado de variables de holgura/excedente igual a cero. Entonces X = B-1 b, y ahora usamos la función objetivo para encontrar el valor óptimo y la solución óptima. Suponga que deseamos solucionar el siguiente problema de PL usando el Solver para la inversa.
Max X1 + X2
Sujeto a:
X1 + X2 ³ 10
X1 £ 8
X2 £ 12
El primer paso debe ser convertir todas las restricciones de desigualdad en igualdades introduciendo variables de holgura/excedente (las restricciones de igualdad, si hay alguna, permanecen sin alterar), tenemos:
X1 + X2 - S1 = 10
X1 + S2 = 8
X2 + S3 = 12
Entonces, al encontrar el inverso de las tres matrices siguientes, obtenemos las soluciones básicas:
S2 = S3= 0
| 1 | 1 | -1 | ||
| B | = | 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 1 | 0 | ||
| B-1 | = | 0 | 0 | 1 |
| -1 | 1 | 1 |
| X1 | 8 | |||
| X2 | = | B-1.b | = | 12 |
| S1 | 10 |
| 1 | 1 | 0 | ||
| B | = | 1 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | -1 | ||
| B-1 | = | 0 | 0 | 1 |
| -1 | 1 | 1 |
| X1 | -2 | |||
| X2 | = | B-1.b | = | 12 |
| S2 | 10 |
S1 = S2 = 0
| 1 | 1 | 0 | ||
| B | = | 1 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 1 | 0 | ||
| B-1 | = | 1 | -1 | 0 |
| -1 | 1 | 1 |
| X1 | 8 | |||
| X2 | = | B-1.b | = | 12 |
| S3 | 10 |
Evaluando la función objetiva para la solución básica factible, obtenemos que la solución óptima es (X1 = 8, X2 = 12), con valor óptimo =20
Solucione un Sistema de Ecuaciones usando un Solver (solucionista) para el Inverso de la Matriz
Para su entendimiento, incluimos el bien conocido método de la inversa de la matriz para solucionar sistema de ecuaciones. Para solucionar el siguiente sistema de ecuaciones,
2X1 + X2 = 3
X1 -X2 = 3
el cual puede ser escrito como la ecuación de la matriz AX = b, entonces X= A-1.b, si la inversa existe
| 2 | 1 | ||
| A | = | ||
| 1 |
|
| 1/3 | 1/3 | ||
| A-1 | = | ||
| 1/3 |
|
| X1 | 2 | |||
| = | A-1b | = | ||
|
X 2
|
|
Por lo tanto X1 = 2, and X2 = -1 es la solución única.
Encontrar el Inverso de una Matriz utilizando un Solver (solucionista) para Sistema de Ecuaciones
Para encontrar el inverso de una matriz cuadrada de tamaño n, solucione n sistemas de ecuaciones con un vector unitario como su lado de mano derecha. La siguiente proposición justifica esta reclamación:
Proposición 2: Considerando que la matriz AnXn tiene un inverso, entonces la columna j-ésimo del inverso denotado por A-1.j es la solución única de AX = Ij, donde Ij es un vector unitario donde el elemento "1" localizado en la fila j-ésimo, j =1, 2.., n.
Suponga que deseamos encontrar la inversa de la matriz siguiente (si ésta existe)
| 2 | 1 | ||
| A | = | ||
| 1 |
|
2X1 + X1 = 1
X1 - X2 = 0
Esto da como resultado X1 = 1/3 , X2 = 1/3. Para encontrar la segunda columna de A -1 solucione:
2X1 + X1 = 0
X1 - X2 = 1
Esto da como resultado X1 = 1/3 , X2 = -2/3. Por lo tanto, A -1 es
| 1/3 | 1/3 | ||
| A-1 | = | ||
| 1/3 |
|
Nota: Una matriz que posee una inversa se llama no singular, o invertible. Una matriz se llama singular si ésta no tiene un inverso. Por ejemplo, la matriz siguiente es singular:
1 6 4
2 4 -1
-1 2 5
Por lo tanto, al aplicar el procedimiento anterior para invertir una matriz, si la matriz es singular, entonces al menos uno de los sistemas de ecuaciones no tiene ninguna solución.
Inversión de la Matriz: Un enfoque de Álgebra Computacional
Un método estándar para calcular A-1 para una matriz r x n A es usar operaciones de fila de Gauss-Jordan para reducir el n x 2n de la matriz aumentada [A | I] a [I | C], donde A-1 = C.
En cambio, proponemos reducir la [n por (n + 1)] matriz aumentada [A | R], donde R es un vector de columna [n por 1] de la variable no especificada r. La reducción simbólica G-J de [A | R] a [I | D] convierte A-1 en la matriz de coeficientes del ri's en D.
Esta comprobado que, este método provee ahorros sustanciales tanto de espacio como de tiempo de computación comparado con otros métodos usados en sistemas de computación de álgebra existentes. Un análisis de complejidad computacional del número requerido de operaciones muestra que, para un n grande, el método propuesto ahorra aproximadamente el 25 % comparado con el método convencional [Arsham 1993]. Esta reducción proviene de comenzar cada fila de R con sólo un término (simbólico), en vez de n términos (numéricos) en cada fila de I. Claramente, este método tiene ventajas pedagógicas sobre otros métodos. Una ventaja consiste en que el sistema lineal genérico con la matriz de coeficiente A es solucionado y simultáneamente A-1 es encontrado, como mencionamos anteriormente.
Suponga que deseamos encontrar la inversa de la siguiente matriz (si ésta existe):
| 2 | 1 | ||
| A | = | ||
| 1 |
|
| 2 | 1 | r1 | ||||||
| 1 | -1 | r2 |
| 1 | 1/2 | r1 / 2 | ||
| 0 | -3/2 | -r1 / 2 + r2 |
| 1 | 0 | r1 / 3 + r2 / 3 | ||||||
| 0 | 1 | r1 / 3 - 2r2 / 3 |
Por lo tanto la matriz inversa es:
| 1/3 | 1/3 | ||
| A-1 | = | ||
| 1/3 |
|
Nota: Una matriz que posee una inversa se llama no singular, o invertible. Una matriz se llama singular si ésta no tiene una inversa. Por ejemplo, la matriz siguiente es singular:
1 6 4
2 4 -1
-1 2 5
Por lo tanto, en la aplicación del procedimiento anterior para invertir una matriz, si la matriz es singular, entonces al menos una fila tendrá Todos los Elementos Cero durante las operaciones G-J.
Objetos de Aprendizaje: El Solver (solucionista) Interactivo en Línea
Aprendizaje Asistido por el Computador: realmente recomiendo los siguientes sitios de Solvers (solucionistas) interactivos en línea para entender los conceptos presentados en este sitio realizando un poco de experimentación numérica:
System of Equations and Matrix Inversion.
Linear Optimization.
Redondeando Errores y Análisis de Estabilidad
El redondeo de los errores es debido a la limitación de hardware de cualquier paquete de computadora. Por lo tanto, usted debe concentrarse en el análisis de estabilidad de la solución con respecto a los parámetros de entrada. A continuación le presento tres ejemplos numéricos de programación Lineal, inversión de la matriz, y solución del sistema de ecuaciones lineales, respectivamente:
Programación Lineal: Considere el problema siguiente:
Max 6X1 + 4X2
sujeto a:
3.01X1 + 2X2 £ 24
X1 + 2X2 £ 16
todas las variables de decisión. ³ 0.
La solución óptima es (X1 = 3.9801, X2 = 6.0100). Sin embargo, la solución óptima para el mismo problema pero con un cambio leve en los coeficientes de la matriz de las restricciones puede resultar en una solución óptima completamente diferente. Por ejemplo, si cambiamos 3.01 a 2.99, entonces la solución óptima es (X1 = 8.0268, X2 = 0). ¡Es decir disminuyendo un elemento de la matriz de tecnología en 0.66 %, la solución cambia drásticamente! Por lo tanto, la solución óptima es inestable con respecto a este parámetro de entrada.
Inversión de la Matriz: Considere la siguiente matriz:
| 1.9998 | 0.9999 | ||
| A | = | ||
| 5.9994 |
|
Esta matriz tiene un inverso apropiado, sin embargo redondeando los elementos de la matriz A,
| 2 | 1 | ||
| Ar | = | ||
| 6 |
|
se convierte en una matriz singular, es decir, no tiene inversa.
Solución de Sistema de Ecuaciones: Considere el siguiente sistema de ecuaciones:
2.04X1 + 2.49X2 = 0.45
2.49X1 + 3.04X2 = 0.55
que tiene una solución única (X1 = -1, X2 = 1). Sin embargo, redondeando la matriz de coeficiente a:
2.0X1 + 2.5X2 = 0.45
2.5X1 + 3.0X2 = 0.55
ahora la solución se convierte en (X1 = 0.1, X2 = 0.1) un cambio impresionante.
Comentarios de Conclusión
Este sitio amplía la discusión de las interrelaciones entre el sistema lineal de ecuaciones, inversión de matrices y programación lineal, por lo tanto cada uno puede ser modelado y solucionado por cualquiera de las otras dos metodologías. Aunque pocos de estos enlaces sean conocidos, este sitio complementa los enlaces restantes.
Arsham H., Links Among a Linear System of Equations, Matrix Inversion, and Linear Program Solver Routines, Journal of Mathematical Education in Science and Technology, 29(5), 764-769, 1998.
Arsham H., Matrix Inversion: A Computational Algebra Approach, Journal of Mathematical Education in Science and Technology, 27(4), 599-605, 1996.
Arsham H., A Linear Symbolic-Based Approach to Matrix Inversion, Journal of Mathematics and Computers in Simulation, 35(6), 493-500, 1993.
Arsham H., The Gauss-Jordan matrix inversion is not optimal: A symbolic adaptation, The 5th SIAM Conference on Applied Linear Algebra, Ed. J. Lewis, 528-532, 1994.
Bellman R., Introduction to Matrix Analysis, SIAM: Society for Industrial & Applied Mathematics, 1997.
Declaración de derechos de propiedad intelectual: El uso legítimo, según las pautas de 1996 guías de consulta justas del uso para los multimedia educativos, de los materiales presentados en este sitio Web está permitido para propósitos educativos no comerciales.
Este sitio puede duplicarse, intacto con esta declaración, en cualquier servidor de acceso público y puede vincularse a cualquier otra página Web. Todos los archivos se encuentran disponibles en
http://home.ubalt.edu/ntsbarsh/Business-stat para el duplicado.
Agradecería recibir comentarios, sugerencias e inquietudes por e-mail Gracias.
Este sitio fue lanzado en el 25/02/1994, y sus materiales intelectuales han sido revisados a fondo anualmente. La versión actual es la 8 va Edición. Todos los enlaces externos son revisados una vez al mes.
Ciencia de la Administración Aplicada para Gerentes y Lideres Gerenciales
Modelos Deterministas: Optimización lineal
Optimización de Enteros y Modelos de Redes
Introducción a la Teoría de Juegos
Modelos Probabilísticos: Del análisis de la decisión
Toma de Decisiones con Periodos de Tiempo Crítico en Economía y Finanzas
Razonamiento Estadístico para la Toma de Decisiones Gerenciales
Una Clasificación de JavaScript Estadíticos
El Aprendizaje con la Asistencia del Computador
Construcción de Regiones de Sensibilidad General de Programación Lineal