- El método de camino crítico que presentamos es un método polinomial, no resuelve mas que un tipo de problema de ordenamiento, muy sencillo, en el cual sólo se consideran restricciones potenciales. Existen variantes a éste método que permiten introducir otro tipo de restricciones, aunque no asegura optimalidad.
- El método Simplex: El término algoritmo Símplex habitualmente se refiere a un conjunto de métodos muy usados para resolver problemas de programación lineal, en los cuales se busca el máximo de una función lineal sobre un conjunto de variables que satisfaga un conjunto de inecuaciones lineales. El algoritmo Símplex primal fue desarrollado por el matemático norteamericano George Dantzig en 1947, y procede examinando vértices adyacentes del poliedro de soluciones. Un algoritmo Símplex es un algoritmo de pivote.
- El método de asignación: El problema de asignación consiste en encontrar la forma de asignar ciertos recursos disponibles (máquinas o personas) para la realización de determinadas tareas al menor coste, suponiendo que cada recurso se destina a una sola tarea, y que cada tarea es ejecutada por uno solo de los recursos. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación operativa en matemática. El modelo se puede aplicar a la asignación de empleados a tareas, de fábricas a productos, de vendedores a territorios, de postores a contratos, etc. Con una sencilla manipulación, el método también se puede aplicar al caso en el que se pretende maximizar cierta cantidad.
Ejemplo
Existen cuatro operarios que se pueden asignar al trabajo con tres máquinas. Un estudio de tiempos y movimientos ha arrojado los siguientes tiempos por operario para las tres máquinas. Indicar que operario debe trabajar en que máquina y cuál de ellos no será asignado a ninguna.
Ejemplo
Existen cuatro operarios que se pueden asignar al trabajo con tres máquinas. Un estudio de tiempos y movimientos ha arrojado los siguientes tiempos por operario para las tres máquinas. Indicar que operario debe trabajar en que máquina y cuál de ellos no será asignado a ninguna.
Máquina 1
|
Máquina 2
|
Máquina 3
| |
Operario 1
|
10
|
7
|
9
|
Operario 2
|
7
|
5
|
8
|
Operario 3
|
9
|
8
|
10
|
Operario 4
|
8
|
9
|
7
|
Como la matriz no esta balanceada, es necesario incluir una máquina ficticia:(esto es fundamental para asegurar que haya una res
puesta. Si la matriz no está balanceada, el problema no será factible de resolver)
Máquina 1
|
Máquina 2
|
Máquina 3
|
Máquina Ficticia
| ||
Operario 1
|
10
|
7
|
9
|
0
| |
Operario 2
|
7
|
5
|
8
|
0
| |
Operario 3
|
9
|
8
|
10
|
0
| |
Operario 4
|
8
|
9
|
7
|
0
| |
Xij = Se debe asignar el operario i a la máquina j? Sí o no?
En matemáticas existen dos números cuyas propiedades hacen que puedan representar estas respuestas son el 1 y el 0, debido a que todo número multiplicado por 1 da el mismo número entonces el 1 se puede reemplazar por la respuesta Sí y como todo número multiplicado por cero da cero entonces se puede reemplazar por la respuesta No.
Así por ejemplo:
10X11 + 7X12 + 9X13 + 0X14
representa el tiempo sumado que emplearía el operario1 en operar las máquinas, pero solo una variable de las tres anteriores puede tomar el valor de Sí, o sea de 1 las demás tendrán que tomar el valor de 0, y eso es debido a que el operario 1 sólo puede ser asignado a una máquina, lo que significaría que el tiempo que utilice el operario 1 puede ser ya sea de "10" de "7" o de "9". Con base en esto podemos formular la función objetivo:
Min Z =
|
10X11 + 7X12 + 9X13 7X21 + 5X22 + 8X23 9X31 + 8X32 + 10X33 8X41 + 9X42 + 7X43
| |||
Restricciones:
Como cada operario sólo puede estar asignado a una máquina....
X11 + X12 + X13 + X14 = 1X21 + X22 + X23 + X24 = 1X31 + X32 + X33 + X34 = 1X41 + X42 + X43 + X44 = 1
Y como cada máquina solo puede tener un operario asignado...
X11 + X21 + X31 + X41 = 1X12 + X22 + X32 + X42 = 1X13 + X23 + X33 + X43 = 1X14 + X24 + X34 + X44 = 1
Xij = 1 o 0 para toda i,j.
Al resolver utilizando Software, por ejemplo el Solver del Excel, la respuesta que se obtiene es la siguiente:
Máquina 1
|
Máquina 2
|
Máquina 3
|
Máquina Fic.
| |
Operario 1
|
0
|
0
|
0
|
1
|
Operario 2
|
0
|
1
|
0
|
0
|
Operario 3
|
1
|
0
|
0
|
0
|
Operario 4
|
0
|
0
|
1
|
0
|
Esto significa que el Operario 1 queda asignado a la Máquina Ficticia (es decir, es el que sobra), el operario 2 se asigna a la máquina 2, el operario 3 se asigna a la máquina 1 y el operario 4 se asigna a la máquina 3
Método de Flood: Este método es utilizado en aquellos casos donde no se ha podido hacer una asignación óptima después de haber realiza el método húngaro. El método consta de los siguientes pasos:
Paso 1: Señalar todas las filas que no tienen una asignación. (Cuando se dice señalar puede ser una pequeña X a la izquierda de la fila o arriba de la columna)
Paso 2: Señalar todas las columnas que tengan un cero en la columna señalada.
Paso 3: Señalar todas las filas que tienen una asignación en las columnas indicadas.
Paso 4: Repetir estos pasos hasta que no pueda señalarse más columnas o filas. (No hay más filas que no tengan asignación) Dibujar una línea por cada fila NO señalada y por cada columna SI señalada.
Paso 5: Encontrar el mínimo valor de los elementos no cubiertos y restarlo a todos los elementos no cubiertos, y sumar este valor a cada elemento que se encuentre en la intersección de una línea horizontal con una línea vertical.
Paso 6: Realizar la asignación como en el método húngaro.
En la gráfica se muestra un ejemplo de como implementar este método siguiendo el siguiente enunciado:
Una empresa de logística cuenta con 4 máquinas para realizar 3 tareas, cada máquina realiza la tarea según el tiempo en que esta pueda ejecutarla. En la siguiente tabla se muestran los tiempos en horas para dichas tareas.
Se plantea la red de la siguiente forma:
- Teoría de Juegos: la teoría de los juegos es una rama de la matemática con aplicaciones a la economía, sociología, biología y psicología, que analiza las interacciones entre individuos que toman decisiones en una marco de incentivos formalizados (juegos). En un juego, varios agentes buscan maximizar su utilidad eligiendo determinados cursos de acción. La utilidad final obtenida por cada individuo depende de los cursos de acción escogidos por el resto de los individuos.
La teoría de juegos es una herramienta que ayuda a analizar problemas de optimización interactiva. La teoría de juegos tiene muchas aplicaciones en las ciencias sociales. La mayoría de las situaciones estudiadas por la teoría de juegos implican conflictos de intereses, estrategias y trampas. De particular interés son las situaciones en las que se puede obtener un resultado mejor cuando los agentes cooperan entre sí, que cuando los agentes intentan maximizar sólo su utilidad.
La teoría de juegos fue ideada en primer lugar por John von Neumann. Luego, John Nash, A.W. Tucker y otros hicieron grandes contribuciones a la teoría de juegos.
Juego
Se denomina juego a la situación interactiva especificada por el conjunto de participantes, los posibles cursos de acción que puede seguir cada participante, y el conjunto de utilidades.
Estrategia
Cuando un jugador tiene en cuenta las reacciones de otros jugadores para realizar su elección, se dice que el jugador tiene una estrategia. Una estrategia es un plan de acciones completo que se lleva a cabo cuando se juega el juego. Se explicita antes de que comience el juego, y prescribe cada decisión que los agentes deben tomar durante el transcurso del juego, dada la información disponible para el agente. La estrategia puede incluir movimientos aleatorios.
Resultados de los Juegos
El resultado de un juego es una cierta asignación de utilidades finales. Se denomina resultado de equilibrio si ningún jugador puede mejorar su utilidad unilateralmente dado que los otros jugadores se mantienen en sus estrategias. Un equilibrio estratégico es aquel que se obtiene cuando, dado que cada jugador se mantiene en su estrategia, ningún jugador puede mejorar su utilidad cambiando de estrategia. Alternativamente, un perfil de estrategias conforma un equilibrio si las estrategias conforman la mejor respuesta a las otras.
Ejemplo
Juegos de suma cero para dos jugadores con estrategias aleatorizadas
Se analizarán ahora aquellos juegos que no tienen punto silla, que de hecho son mucho más frecuentes en la práctica. Para ello supongamos que dos personas van a jugar a pares o impares solamente con la posibilidad de sacar uno o dos dedos cada uno. Si la suma de ambos es par el jugador A pagará un euro al jugador B. En caso contrario será B el que pague a A. Por tanto la matriz de beneficios se puede expresar de la forma siguiente:
No hay punto silla. Eso significa que para cualquier decisión de estrategias hay un jugador que puede beneficiarse cambiando de estrategia unilateralmente. Si por ejemplo los dos sacan dos dedos el resultado sería par y ganaría B. Pero al cambiar A de estrategia pasaría a ganar A y por tanto a perder B.
Se determinarán ahora estrategias óptimas y el valor de este juego. Para ello se amplía
el conjunto de estrategias posibles. Hasta ahora se ha supuesto que cada vez que un jugador participa en un juego utilizará la misma estrategia. Ahora se permitirá que un jugador opte por una estrategia concreta en una proporción determinada de casos, que llamaremos probabilidad. Este tipo de estrategias se denominan estrategias aleatorizadas o mixturas. En general podríamos representar una estrategia aleatorizada de A de la forma (x1, x2) y una de B de la forma (y1, y2). Esto quiere decir que si el jugador A utiliza la estrategia (x1, x2) sacará un dedo en el 100x1 % de las veces que juegue y dos en el resto (100x2 %). Por supuesto ha de verificarse que
No hay comentarios:
Publicar un comentario