Programación de las operaciones, problema planteado y desarrollado en el software GAMS
Enviado por Christopher • 7 de Noviembre de 2018 • 2.722 Palabras (11 Páginas) • 499 Visitas
...
Es requerido que sea así (un recurso para cada tarea), sino será necesario modelarlo como un LP (Lineal Programming) o MIP (Mixed-Integer Programming).
Ejemplos de asignaciones: Operarios a Tareas, Máquinas a Operarios, Nadadores a Estilos, Ayudantes a Cátedras. Etc., etc., etc.
EL problema de la Asignación se basa en una información comparativa para tomar la decisión de que asignar a que (Una matriz de costos, Una matriz de tiempos, una matriz de ingresos, etc.). Cuando la matriz no está balanceada, es decir, cuando no es cuadrada, (sobran filas o columnas), se debe balancear mediante la inclusión de filas o columnas ficticias, con valores de cero en dicha matriz.
ALGORITMO DE HÚNGARO- MÉTODO DE KONING
El algoritmo húngaro sirve para reemplazar los métodos tradicionales de la programación binaria, que implican muchos cálculos, aprovechando la forma especial que tienen los problemas de asignación.
El algoritmo que se presenta a continuación sirve para minimizar, pero con algunas modificaciones se puede emplear también para maximizar.
Si la matriz no está balanceada, balancearla incluyendo las filas o columnas ficticias necesarias.
Algoritmo:
- De cada elemento de la matriz restar el mínimo valor de cada fila
- De cada elemento de la matriz restar el mínimo valor de cada columna
- Cubrir todos los ceros existentes con el mínimo número de líneas posibles (solo Horizontales y/o Verticales)
- Si el menor número de líneas es igual al número de asignaciones a realizar. Detener el proceso pues se ha encontrado la solución óptima, procediendo a asignar por filas o columnas con ceros únicos. SI el menor número de líneas es menor que el número de asignaciones a realizar ir al paso 5.
- Ubicar el mínimo valor de todos los elementos no cubiertos, restar ese valor a todos los elementos no cubiertos y sumarlos a las intersecciones. Volver al paso 3. (Método de Flood, también se llama condición de Koning)
Ejemplo de asignación mediante el algoritmo húngaro:
[pic 1]
[pic 2]
[pic 3]
[pic 4]
[pic 5]
[pic 6]
[pic 7]
[pic 8]
EL ENTORNO DE GAMS
GAMS (General Algebraic Modeling System) es un entorno para definir, analizar y resolver problemas de optimización. Los elementos más importantes de GAMS son:
- Su capacidad para resolver problemas pequeños (docenas de variables y restricciones) y grandes problemas (miles de variables y restricciones) escribiendo básicamente el mismo programa. Dispone de una forma compacta y eficiente para escribir bloques de ecuaciones similares sin más que escribir “una de ellas”.
- Se separa la definición del modelo de la técnica de resolución. El usuario de GAMS formula el modelo consistentemente, y una vez expresado en notación GAMS, uno de los programas disponibles se encarga de generar la solución. Como resultado, el usuario se centra en el modelado, sin ser perturbado por los problemas técnicos de los algoritmos de resolución. Esto hace posible un proceso de modelado muy sencillo y agradable.
- GAMS prácticamente reproduce la descripción del problema de programación matemática. Como resultado, el código GAMS es casi auto explicativo para los lectores que tengan una mínima formación en optimización.
- GAMS suministra también mecanismos que permiten resolver colecciones de problemas de optimización estructurados, tales como los de técnicas de descomposición.
Algunos comandos de GAMS
Comando
Proposito
Set(s)
Dar nombre a los ´índices
y definir sus posibles valores
Scalar(s)
Dar nombre a los escalares
y asignarles valores
Parameter(s)
Dar nombre a los vectores
y asignarles valores
Table(s)
Dar nombre a las matrices
y asignarles valores
Variable(s)
Declarar variables,
asignarles un tipo (opcional)
y darles cotas inferior y superior
Equation(s)
Definir la función a optimizar
y las restricciones
Model
Dar nombre a los modelos
y asignarles la lista de restricciones
Solve
Indicar a GAMS el programa
que debe resolverlo
Display
Decir a GAMS los elementos
a listar en el informe de salida
Reglas de GAMS
- GAMS no diferencia entre letras mayúsculas y minúsculas.
- Todo comando debe terminar en punto y coma.
- Los comandos pueden definirse en cualquier orden, con la única restricción de que un elemento debe haber sido definido antes de usarlo.
- GAMS tiene palabras reservadas, que no pueden usarse para otro fin que el suyo propio.
- Algunos comandos se identifican por sus primeras letras, por lo que puede añadirse una ‘s’ para facilitar
...