Álgebra y programación lineal
Estopy estudiando ingeniería industrial y debo realizar un trabajo de programación lineal por el método simplex y gráfico que contenga 2 variables y 5 restricciones.
En lo posible si te encuentras conectado te agradezco que me ayudes es urgente
En lo posible si te encuentras conectado te agradezco que me ayudes es urgente
2 Respuestas
Respuesta de mianmole
1
Respuesta de chilajito
Unificación de Sistema de Ecuaciones Lineales,
Inversión de Matrices, y Programación Lineal
Esto amplía las relaciones unidireccionales existentes entre los sistemas lineales que solucionan ecuaciones, inversión de matrices, y programación lineal. Los enlaces adicionales permiten al usuario entender el todo y las partes de estos temas. Estos también ayudan al usuario a modelar y solucionar un problema modelado de cualquiera de los temas mencionados teniendo acceso a un paquete de computadora Solver (Solucionista). Los objetivos son tanto la unificación teórica así como también los progresos en aplicaciones. Ejemplos numéricos ilustrativos son presentados a continuación.
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 más el valor combinatorial Cpq donde p es el número de restricciones y que es el número de variables. Por lo tanto, tomando cualquier ecuación que, 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 ES 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 página 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 -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 -2/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 POR = 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
Su inversa es:
0 1 0
B-1 = 0 0 1
-1 1 1
Por lo tanto:
X1 8
X2 = B-1.b = 12
S1 10
S1 = S3 = 0
1 1 0
B = 1 0 1
0 1 0
Su inversa es:
1 0 -1
B-1 = 0 0 1
-1 1 1
Por lo tanto:
X1 -2
X2 = B-1.b = 12
S2 10
S1 = S2 = 0
1 1 0
B = 1 0 0
0 1 1
Su inversa es:
1 1 0
B-1 = 1 -1 0
-1 1 1
Por lo tanto:
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
Su inversa es:
1/3 1/3
A-1 =
1/3 -2/3
Por lo tanto:
X1 2
= A-1b =
X 2 -1
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 -1
Para encontrar la primera columna de A -1 solucione:
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 -2/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 por n A es usar operaciones de fila de Gauss-Jordan para reducir el n por 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 -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 -2/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 3.0009
Esta matriz tiene un inverso apropiado, sin embargo redondeando los elementos de la matriz A,
2 1
Ar =
6 3
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
Inversión de Matrices, y Programación Lineal
Esto amplía las relaciones unidireccionales existentes entre los sistemas lineales que solucionan ecuaciones, inversión de matrices, y programación lineal. Los enlaces adicionales permiten al usuario entender el todo y las partes de estos temas. Estos también ayudan al usuario a modelar y solucionar un problema modelado de cualquiera de los temas mencionados teniendo acceso a un paquete de computadora Solver (Solucionista). Los objetivos son tanto la unificación teórica así como también los progresos en aplicaciones. Ejemplos numéricos ilustrativos son presentados a continuación.
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 más el valor combinatorial Cpq donde p es el número de restricciones y que es el número de variables. Por lo tanto, tomando cualquier ecuación que, 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 ES 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 página 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 -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 -2/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 POR = 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
Su inversa es:
0 1 0
B-1 = 0 0 1
-1 1 1
Por lo tanto:
X1 8
X2 = B-1.b = 12
S1 10
S1 = S3 = 0
1 1 0
B = 1 0 1
0 1 0
Su inversa es:
1 0 -1
B-1 = 0 0 1
-1 1 1
Por lo tanto:
X1 -2
X2 = B-1.b = 12
S2 10
S1 = S2 = 0
1 1 0
B = 1 0 0
0 1 1
Su inversa es:
1 1 0
B-1 = 1 -1 0
-1 1 1
Por lo tanto:
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
Su inversa es:
1/3 1/3
A-1 =
1/3 -2/3
Por lo tanto:
X1 2
= A-1b =
X 2 -1
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 -1
Para encontrar la primera columna de A -1 solucione:
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 -2/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 por n A es usar operaciones de fila de Gauss-Jordan para reducir el n por 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 -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 -2/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 3.0009
Esta matriz tiene un inverso apropiado, sin embargo redondeando los elementos de la matriz A,
2 1
Ar =
6 3
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