investigacion de oeraciones

Instituto Tecnológico Superior de Acayucan

Ingeniería en informática
Nombre del Alumno: USCANGA

SANTOS

Apellido Paterno

ENRIQUE
Apellido Materno

I.S.C. JOSE AURELIO RAMIREZ GONZALESAsignatura:

Investigación de operaciones

Matricula: 110B0437

Semestre: cuarto

Grupo: 407-A

Nombre(s)

MODELO DE ASIGNACION
El problema de asignación

Este problema consiste enasignar n
individuos a n tareas de modo que todos los
individuos realicen una tarea y todas las
tareas se realicen. Se exige además que el
costo total sea mínimo.

Ejemplo:
Una empresa tiene 4máquinas y debe completar
cuatro tareas. Cada máquina puede y debe realizar
una y sólo una de las tareas. La tabla siguiente nos
da el tiempo que tarda cada máquina en completar
cada trabajo.Asignar una tarea a cada máquina de modo que
la suma de los tiempos trabajados por las cuatro
máquinas sea mínimo.

Este problema se puede resolver por el algoritmo de
transporte, ya que lasmáquinas pueden ser
interpretadas como orígenes con oferta 1 y las tareas
como destinos con una demanda de 1, puesto que
cada máquina sólo hace una tarea y todas las tareas
han de ser realizadas.

Lassoluciones de este problema sólo pueden tomar
los valores 0 o 1. Un 1 en la celda (i, j) significa que al
individuo i se asigna la tarea j.

Aunque el problema puede resolverse por el
algoritmode transporte, se suele presentar un alto
grado de degeneración.

 Para el problema de asignación es más
eficiente usar el método Húngaro, que
exponemos a continuación.

El algoritmo Húngaro(Forma minimizante)
 Partiendo de la matriz cuadrada de los
tiempos se realizan los pasos siguientes:

 Paso 1: Encontrar el mínimo de cada fila.
Construir una nueva matriz restando de
cadafila el mínimo coste de ésta. Para
esta nueva matriz realizar la misma
operación por columnas. Esta nueva
matriz se llama matriz de coste
reducido.

 procurando comenzar por las filas o...