FECHA ORIGINAL DE PUBLICACIÓN DE MI ANTERIOR BLOG.
VIERNES, 2 DE DICIEMBRE DE 2011
Apuntes de exposición en clase
Algoritmo simplex
Un sistema de desigualdades
lineales define un Politopo como una región factible. El algoritmo simplex
comienza en un vértice y se mueve a lo largo de las aristas del Politopo hasta
que alcanza el vértice de la solución óptima.
En la teoría de optimización, el
algoritmo simplex, descubierto por el matemático norteamericano George Bernard
Dantzig en 1947, es una técnica popular para dar soluciones numéricas del
problema de la programación lineal. Un método sin relación, pero llamado de
manera similar, es el método Nelder-Mead o método simplex cuesta abajo, debido
a Nelder y Mead (1965), que es un método numérico para optimización de
problemas libres multidimensionales, perteneciente a la clase más general de
algoritmos de búsqueda. El que permite encontrar una solución óptima en un
problema de maximización o minimización, buscando en los vértices del polígono.
En ambos casos, el método usa el concepto de un simplex, que es un Politopo de N + 1 vértices en N dimensiones: un segmento de línea sobre una línea, un triángulo sobre un plano, un tetraedro en un espacio de tres dimensiones y así sucesivamente.
• POLITOPO
Una clase especial de politopos son
los politopos convexos, el casco convexo o envoltura convexa de un conjunto
finito de puntos. Los politopos convexos también pueden representarse como la
intersección de hemiespacios. Esta intersección puede escribirse como la
desigualdad matricial , donde A es una matriz de n por m, con n el número de
hemiespacios y m el número de dimensiones del politopo, y b un vector de n por
1 columna. Los coeficientes de cada fila de A y b se corresponden con los
coeficientes de la desigualdad lineal que define al respectivo hemiespacio
(véase hiperplano para una explicación más detallada). En consecuencia, cada
fila de la matriz se corresponde con uno de los hiperplanos que delimitan el
politopo.
Un politopo convexo n-dimensional
está delimitado por un número de facetas (n-1)-dimensionales. Cada par de
facetas se encuentra en una "cresta" de dimensión n-2. Estas, a su
vez, se encuentra en fronteras (n-3)-dimensionales, y así sucesivamente. Estos
sub politopos son llamados caras, si bien el término puede también referirse
específicamente al caso bidimensional). Una cara de dimensión 0 es un vértice;
una cara de dimensión 1 es una arista. Se llama celda a las caras
tridimensionales.
Una cubeta consiste de los puntos
de un Politopo que también satisface la forma de igualdad de una representación
matricial donde sólo está presente una fila en A. De modo similar, una cresta
satisface la forma de igualdad de la representación matricial cuando en A hay
dos filas presentes. En términos generales, una cara (n-j)-dimensional
satisface la relación de igualdad con j filas en A. Estas filas forman la base
de la cara. En términos geométricos, esto significa que la cara es el conjunto
de puntos del politopo que yacen en la la intersección de j de los hiper planos
que limitan el politopo. Las caras de un Politopo convexo forman una retícula
llamada su retícula de cara, donde la relación de subconjuntos está definida
entre los hiperplanos de la base. El Politopo en sí es considerado una
"cara" en la retícula de caras, y es el máximo de la retícula.
Ejemplo de cómo usar "SOLVER"
Andrés Z. Es presidente de una
microempresa de inversiones que se dedica a administrar las carteras de
acciones de varios clientes. Un nuevo cliente ha solicitado que la compañía se
haga cargo de administrar para él una cartera de 100.000$. A ese cliente le
agradaría restringir la cartera a una mezcla de tres tipos de acciones
únicamente, como podemos apreciar en la siguiente tabla. Formule usted un
modelo de Programación Lineal para mostrar cuántas acciones de cada tipo
tendría que comprar Andrés con el fin de maximizar el rendimiento anual total
estimado de esa cartera
En la fila 2 se coloca la variable
de decisión la cual es el número de acciones y sus valores desde la B2 hasta la
D2.
En la fila 3 el rendimiento anual y
sus valores desde B3 hasta D3.
En la celda E3 colocaremos una
formula la cual nos va indicar el rendimiento anual total,
=sumaproducto($B$2:$D$2;B3:D3).
Desde la fila B5 hasta la D8
colocaremos los coeficientes que acompañan a las variables de decisión que
componen las restricciones.
Desde la E5 hasta la E8 se
encuentra la función de restricción (LI) y no es mas que utilizar la siguiente
formula =sumaproducto($B$2:$D$2;B5:D5) la cual se alojaría en la celda E5,
luego daríamos un copy hasta la E8. Desde la F5 hasta F8 se encuentran los
valores de las restricciones.
Desde la G5 hasta G8 se encuentra
la holgura o excedente. Una vez completada la hoja de cálculo con el modelo
respectivo ¡GRABE SU HOJA!, y seleccione "Solver…" en el menú de
"Herramientas", ahí tendrá que especificar dentro del cuadro de
dialogo de Solver:
La celda que va a optimizar
Las celdas cambiantes
Las restricciones
Así tendremos la siguiente
pantalla:
Como se puede observar en la celda objetivo se coloca la celda que se
quiere optimizar, en las celdas cambiantes las variables de decisión y por
último se debe de complementar con las restricciones. Una vez realizado estos
pasos deben pulsar el icono de "Opciones" y debe hacer clic en
"Asumir modelo lineal" y enseguida el botón de "Aceptar".
Luego haga clic en el botón de "Resolver" para realizar la
optimización, lea detenidamente el mensaje de terminación de Solver y ahí
observará si se encontró una solución o hay que modificar el modelo, en caso de
haber encontrado una solución óptima usted podrá aceptar o no dicha solución,
luego tendrá oportunidad de analizar un informe de análisis de
sensibilidad para luego tomar la mejor decisión
En nuestro ejemplo el máximo rendimiento anual fue de 12750$, y la
cantidad de acciones a comprar serían 750, 1000 y 1500 para Navesa,
Telectricidad y Rampa respectivamente. De está forma podemos observar
la potencia que tiene el solver
Si en su Excel no se encuentra en la pestaña de datos lo opción solver
dentro de análisis (al final del lado derecho), active el botón de office y
elija complementos de ahí selección solver y el botón ir a y active las
funciones necesarias.
BIBLIOGRAFIA
http://en.wikipedia.org/wiki/Simplex
http://mathworld.wolfram.com/SimplexMethod.htmlhttp://eom.springer.de/S/s085340.htmhttp://wapedia.mobi/en/Simplex_algorithmhttp://en.wikipedia.org/wiki/Simplex_algorithmhttp://neos.mcs.anl.gov/CaseStudies/simplex/index.htmlhttp://math.fullerton.edu/mathews/n2003/LinearProgrammingMod.html
http://glossary.computing.society.informs.orghttp://www.me.utexas.edu/~jensen/ORMM/frontpage/jensen.lib/index.html
http://www.phpsimplex.com/biografia_Dantzig.htm
No hay comentarios:
Publicar un comentario