Programación de las operaciones, problema planteado y desarrollado en el software GAMS

...

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