METODO DE ASIGNACION ( HUNGARO )

Un problema de asignación es un problema de transporte balanceado, en el cual todas las ofertas y todas las demandas son iguales a uno. Se puede resolver eficientemente un problema de asignación m x m mediante el método Húngaro:

Paso 1.- Empiece por encontrar el elemento mas pequeño en cada renglón de la matriz de costos. Construya una nueva matriz, al restar de cada costo, el costo mínimo de su renglón. Encuentre, para esta nueva matriz el costo mínimo en cada columna. Construya una nueva matriz ( la matriz de costos reducidos ) al restar de cada costo el costo mínimo de su columna.

Paso 2.- Dibuje el mínimo numero de líneas (horizontales o verticales ) que se necesitan para cubrir todos los ceros en la matriz de costos reducidos. Si se requieren m líneas para cubrir todos los ceros, siga con el paso 3.

Paso 3.- Encuentre el menor elemento no cero (llame su valor k en la matriz de costos reducidos, que no esta cubiertos por las líneas dibujadas en el paso 2. Ahora reste k de cada elemento no cubierto de la matriz de costos reducidos y sume k a cada elemento de la matriz de costos reducidos cubierto por dos líneas. Regrese al paso 2.

Un problema de asignación es un problema de transporte balanceado en el que todas las ofertas y demandas son iguales a 1; así se caracteriza por el conocimiento del costo de asignación de cada punto de oferta a cada punto de demanda. La matriz de costos del problema de asignación se llama: matriz de costos.

Como todas las ofertas y demandas para el problema de asignación son números enteros, todas las variables en la solución óptima deben ser valores enteros.

EJEMPLOS DE PROBLEMAS DE ASIGNACION

1. Una empresa ha contratado a 4 individuos para 4 trabajos, los 4 individuos y 4 trabajos pueden mostrarse en una tabla que indique las clasificaciones obtenidas, analizando al individuo para cada trabajo. Los renglones se refieren a los hombres, mientras que las columnas se refieren a los trabajos; el problema consiste en maximizar las calificaciones para asignar los 4 trabajos.
Se supone que las calificaciones de un individuo es directamente proporcional a la ganancia que obtendría la compañía si ese individuo se encargara del trabajo.

2. Otro problema que utiliza la misma estructura del modelo de transporte, es la asignación de camiones para reducir al mínimo los costos de un problema de asignación.

3. Una empresa cubre el territorio nacional con dos camiones especialmente equipados para funcionar en condiciones climatológicas específicas. La empresa ha dividido en cinco regiones geográficas. Se compra el camión A y se modifica para que funcione eficientemente en las regiones uno y dos, y para que funcione bastante bien en las regiones tres y cuatro. El mismo camión no funciona bien en la región cinco. Los gastos de gasolina, mantenimiento y otros costos directos de operación, serían mínimos en las regiones uno y dos, promedio en las regiones tres y cuatro, y altos en la región cinco. Se tiene esa misma información con respecto a los demás camiones de la compañía, o sea, los tipos B, C y D.

METODO DE APROXIMACION DE VOGEL ( VAM )

Este metodo es heuristico y suele producir una mejor solucion inicial que los dos metodos antes descritos. De hecho, VAM suele producir una solucion inicial optima, o proxima al nivel optimo.
Los pasos del procedimiento son los siguientes:

Paso1: Evaluese una penalizacion para cada renglon restando el menor elemento del costo del renglon del elemento de costo menor siguiente en el mismo renglon.

Paso2: Identifiqueze el renglon o columna con la mayor penalizacion, rompiendo empates en forma arbitraria. Asignese el valor mayor posible a la variable con el costo mas bajo del renglon o columna seleccionado. Ajustese la oferta y la demanda y tachese el renglon o columna satisfecho. Si un renglon o columna se satisfacen al mismo tiempo, solo uno de ellos se tacha y al renglon restante se le asigna una oferta cero.Cualquier renglon o columna con oferta o demanda cero no debe utilizarce para calcular penalizaciones futuras.

Paso 3:
a.-si solo hay un renglon o columna sin tachar, detengase.
b.-si solo hay un renglon conoferta positiva sin tachar, determinense las variables basicas del renglon a travez del metodo del costo minimo.
c.-si todos los renglones y columnas sin tachar tienen oferta o demanda cero asignadas, determinese las variables basicas cero a travez del metodo del costo minimo. Detengase.
d.-de lo contrario, calculense las penalizaciones de las renglones y columnas no tachados y despues dirijase al paso 2.

PR = Penalización de Renglón
PC = Penalización de Columna

MODELO DEL COSTO MINIMO

Asignese el mas grande valor posible a la variable con el menor costo unitario de toda la tabla. Tachese el renglon o columna satisfecho.Despues de ajustar la oferta y la demanda de todos los renglones y columnas no tachados, repitase el proceso asignando el valor mas grande posible a la variable con el costo unitario no tachado mas pequeño. El procedimiento esta completo cuando queda exactamente un rebglon o bien una columna sin tachar.

METODO DE MULTIPLICADORES

EXPLICACION DEL METODO DE MULPIPLICADORES CON UN METODO SIMPLEX

La relecion que existe entre el metodo multiplicadores y el metodo simplex se puede establecer demostrando que cpq según se define, es igual directamente a los coeficientes de la funcion objetivo de la tabla simplex asociada con la iteracion actual.

Para mostrar como se obtiene el problema dual para el metodo de transporte, considerese primero el caso especial de ,=2 y n=3 que se indica en la tabla 6-15. Sean las variables duales u1 y u2 para las restricciones de las fuentes y v1,v2, y v3 para las restricciones de los destinos. El problema dual se convierte en:

Maximizar w = (a1u1+a2u2) + (b1v1+b2v2+b3v3)

Sujeto a:

U1 +v1 <= c11
U1 +v2 <=c12
U1 +v3 <=c13
U2+v1 <=c21
U2+v1 <=c22
U2 +v3 <=c23
Ui, U2, v1, v2, v3, irrestrictas

El problema dual correspondiente esta dado por:

Maximizar w = åm i-1 a1 u1 + ån bi vj

sujeto a:

ui + vj <=cij para todas las i y j
ui y vj irrestrictas

La evaluacion de las variables no basicas se determinan mediante la sustitucion de los valores actuales de las variables duales en las restricciones duales y despues tomando la diferencia entre sus miembros primero y segundo. Los valores de las variables duales se pueden determinar observando que las restricciones deuales correspondientes a una variable basica se deben satisfacer como ecuaciones escritas.
En realidad en la iteracion optima los multiplicadores producen los valores duales optimos directamente.

En lo antes expuesto se asigna un valor arbitrario a una de las variables duales que indica que los multiplicadores simplex asociados con una solucion basica dada no son unicos. Esto puede parecer inconsistente con los resultados donde los multiplicadores deben ser unicos.

METODO DE LA "M"

Este método empieza con la PL en la forma estándar Para cualquier ecuación i que no tiene una holgura, aumentamos una variable artificial R. Entonces esta variable se convierte en parte de la solución básica inicial. Debido a que es una variable artificial al modelo de PL se le asigna una penalidad en la función objetivo, para obligarlas aun nivel cero en una iteración del algoritmo SIMPLEX

Debido a que M es un valor positivo suficientemente grande, la variable R1 se penaliza en la función objetivo utilizando —MR, en el caso de la maximización, y +RM, en la minimización. Debido a esta penalidad El proceso de optimización lógicamente tratara de impulsar R1, al nivel cero
Minimice Z= 4X1 + X2

La forma estándar se obtiene restando un superávit X3 en la segunda restricción y añadiendo una holgura X en la tercera restricción. Por tanto obtenemos

Minimice Z= 4X1 +X2

La primera y segunda ecuación no tiene variables que desempeñen el papel de holguras. Por consiguiente, utilizamos las variables R1 y R2 en estas dos ecuaciones y las penalizamos en la función objetivo con MR1 + MR2. La PL resultante se da como
Minimice Z=4X1 +X2 + MR1 + MR2

En el modelo modificado, ahora podemos utilizar R1, R2 y X4 como la solución básica factible inicial como lo demuestra la siguiente tabla simplex

Antes de proceder con los cálculos del método simplex, necesitamos hacer que el renglón -Z sea consistente con el resto de la tabla simplex. De manera específica, el valor de z asociado con la solución básica inicial R1 = 5, R2 6, y X4 = 4 debe ser 3M + 6M + O = 9M en vez de O, como se muestra en el lado derecho del renglón -Z. Esta inconsistencia se debe al hecho de que R, y R2 tienen coeficientes no cero (-M, -M) en e! renglón -Z Estas inconsistencias se eliminan sustituyendo R1 y R2 en el renglón -Z, utilizando las ecuaciones apropiadas de restricción.

En particular, observe los elementos “1” realzados en el renglón -R1 y en el renglón -R2. Multiplicando cada uno de los renglones –R1 y de los renglones -R2 por M y añadiendo la suma al renglón -Z, efectivamente se sustituirá a R1 y R2 en el renglón objetivo. Podemos resumir este paso como

Nuevo renglón Z= Antiguo renglón Z + M x (Renglón R1) + M x (Renglón R2)
Esto se aplica como

Por lo tanto la nueva tabla simplex se convierte en

METODO DUAL

Como sabemos, el método simplex es un algoritmo iterativo que iniciando en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejores hasta encontrar la solución óptima la base de su lógica es mantener la factibilidad, mientras busca la optimalizad.
Pero surge la posibilidad de usar otro esquema igualmente iterativo, que como contraparte del simplex, comienza en una solución básica óptima, pero no factible y mantiene la inmejorabilidad mientras busca la factibilidad. Con este procedimiento se llega igualmente a la recurso óptima.

Primero se debe expresar el modelo en formato estándar, agregando las variables de holgura y de exceso que se requieran.
Enseguida, en las ecuaciones que tengan variables de exceso (resultantes de restricciones de tipo >), se debe multiplicar por (-1) en ambos lados, para hacer positivo el coeficiente de la variable de exceso, y formar así un vector unitario que nos permita tomar esta variable de exceso como una variable básica inicial.
Sin necesidad de agregar una variable artificial en esa restricción.

Como se muestra en el siguiente ejemplo:


Considerando el sig. Problema calcular su modelo

(DUAL) MINIMIZAR

P=4Z1+6Z2+18Z3+10Z4
Z1+3Z3+Z4≥3
Z2+2Z3+4Z4≥5
Z1, Z2, Z3, Z4 ≥0
Sea Max Z=3X+5Y

RESTRICCIONES X ≤ 4
Y ≤ 6
3X+2Y≤18
X+4Y≤10
DONDE X, Y≥0

PONEMOS LOS COEFICIENTES DISPONIBILIDAD EN FOMA DE VECTOR COLUMNA (MATRIZ), PRIMAL.

Considerando el sig. Problema calcular su modelo


MAX: Z= 3X1+8X2+2X3-4X4

RESTRICCIONES:

X1 + X2 + 2X3 +3X4≤5
X1 – X2 =-1
X3 + X4≥46

DONDE: X1,X2,X3,X4≥0

POR LO TANTO (DUAL) MIN G = 5Y1 – Y2 + 46Y3
LAS RESTRICCIONES QUEDAN:


Y1 + Y2 ≥3
Y1 – Y2 ≥8
2Y1 + Y3 ≥2
3Y1 - Y3 ≥-4

DONDE: Y1,Y2,Y3 ≥ 0

METODO DE LAS 2 FASES

La desventaja de la técnica de la gran M es el posible error de computo que podría resultar de asignar un valor muy grande a la constante M. Esta situación podría presentar errores de redondeo en las operaciones de la computadora digital. Para evitar esta dificultad el problema se puede resolver en 2 fases


FASE 1 Formula un nuevo problema reemplazando la función objetivo por la suma de las variables artificiales .

La nueva función objetivo se minimiza sujeta a las restricciones del problema original. Si el problema tiene un espacio factible el valor MINIMO de la F:O optima será cero , lo cual indica que todas las variables artificiales son cero. En este momento se hace la fase 2

Si el valor mínimo de la fo optima es mayor que cero el problema no tiene solución y termina anotándose que no existe función factible.


FASE
Utilice la solución optima de la fase1como solución de inicio para el problema original. En este caso la fo original se expresa en términos de las variables no básicas utilizando las eliminaciones de gauss-jordán

Problema



Maximizar Z= 6x1 +6x2+4x3

Sujeto a : 3x1+6x2+x3<20 2x3="15">0



fase 1 siempre es un problema de minimización


min Z=r1

sujeto a

3x1+6x2+x3<20 2x3="15">0

FASE 2

MIN Z=6X1+4X2+4X3+0S1

Z –6X1-4X2-4X3-0S1=0

METODO SIMPLEX POR MINIMIZACION

Método SIMPLEX por minimización

Minimizar Z= 3m + 4n - 8ñ

3m – 4n ≤ 12
M + 2n + ñ ≥ 4
4m – 2n +5ñ ≤ 20

M ≥ 0, n ≥ 0, ñ ≥ 0

Como es un problema de minimización recordemos que tenemos que maximizar la función objetivo quedando así

-3m – 4n + 8ñ + Z = 0

Las inecuaciones las hacemos igualdades

3m – 4n = 12
m + 2n + ñ = 4
4m – 2n +5ñ = 20

Ahora tenemos que hacer nuestra tabla 1 y aplicaremos el mismo procedimiento del método SIMPLEX para maximizarlo.

Ahora de la tabla tomaremos el MAYOR POSITIVO en este caso es el 8 y ya encontramos nuestra columna pivote.

Posteriormente dividimos 28/5 = 4 4/1 = 4 12/0 = 0, y tenemos que tomar el numero menor de estas divisiones en este caso tenemos dos, cuatros podemos tomar cualquiera

Y ya encontramos nuestro pivote operacional en este caso es 1, ahora tenemos que dividir toda esa fila entre este 1 para poder resolver la siguiente tabla

Ahora la ñ ya paso a la base

El problema se termina aquí porque ya nos quedaron puros negativos y ceros en nuestra PO que era nuestro objetivo

3m – 4n ≤ 12
3(0) – 4 (0) ≤ 12
0 ≤ 12 Si cumple

m + 2n + ñ ≥ 4
0 + 2(0) + ¼ ≥ 4
¼ ≥ 4 No cumple

4m – 2n + 5ñ ≤ 20
4 (0) – 2 (0) + 5 (1/4) ≤ 20
1.25 ≤= 20 Si cumple

3m + 4n – 8ñ
Z = 3 (0) + 4(0) – 8 (1/4)
Z = 2

Método simplez para problemas de minimización

Min Z = 2x + 3y Función objetivo

Sujeto a 2x + y ≥ 4
X – y ≤ 1 Restricciones

Condiciòn de no negatividad x, y ≥ 0

1. Convertir el problema en un problema de maximización haciéndolo negativo la función objetivo, esto se hace multiplicando por -1

Min Z= 2x + 3y (-1) Max –Z= -2x – 3Y

2. Convertir las inecuaciones (restricciones) en ecuaciones
2x + y ≥ 4 2x + y = 4
x – y ≤ 1 x – y = 1

2 Elaborar la tabla inicial SIMPLEX

Observamos que nuestra FO tenemos en las variables de decisión valores negativos, lo cual produce que nuestro problema no tenga solución, ya que para resolver SIMPLEX por minimización es necesario tomar el valor positivo mayor y en esta tabla no se encuentra numero alguno

Ya no tiene solución

ESQUINA NOROESTE

4 AGENCIAS ORDENAN AUTOS NUEVOS QUE DEBEN LLEGAR DESDE 3 PLAZAS, LA AGENCIA A NECESITA 6 AUTOS, LA AGENCIA B REQUIERE DE 5 LA AGENCIA C 4 Y LA D REQUIERE 4

LA PLANTA 1TIENE 7 AUTOS EN STOCK, LA PLANTA 2 TIENE 13 Y LA PLANTA 3 TIENE 3 . EL COSO DE ENVIARA UN AUTO DE LA PLANTA A LA AGENCIA SE PUEDE VER EN LA TABLA .

MODELO DE ASIGNACION


Es una forma de representar a un modelo de transporte o una forma de asignar los recuersos a las diferentes actividades ,estamos hablando de una matriz cuadrada es decir A UNA ACTIVIDAS CORRESPONDE UN RECUERSO

MINIMIZAR METODO HÚNGARO


REVISAR QUE TODAS LAS CASILLAS TENGAN SU COSTO Y BENEFICIO


1- BALANCEAR EL MODELO (filas columnas)

2- PARA TODO RENGLÓN ESCOGEMOS EL MENOR VALOR Y RESTARLOS A TODOS LOS DEMAS EN EL MISMO RENGLÓN.

3- PARA CADA COLUMNA ESCOGEMOS EL MENOR VALOR Y RESTARLOS DE TODOS LOS DEMAS EN LA MISMA COLUMNA


4- TACLAR EL MINIMO NUMERO DE LINEAS VERTICALES Y HORIZONTALES DE FORMA QUE TODOS LOS CEROS QUEDAN
TACHADOS

5- USAR EL CRITERIO DE OPTIMIZACION

6- SELECCIONAR EL MENOR VALOR NO TACHADO DE TODA LA MATRIZ

El valor restarlo de todo elemento no tachado y sumarlo a los elementos en la interaccion de 2 lineas

7- HACER LOS PASOS EN FORMA SUCESIVA BUSCANDO TACHAR TODOS LOS CEROS , REGRESAR AL PASO 4 HASTA QUE CADA RENGLÓN Y CADA COLUMNA TENGAN UNA SOLA ASIGNACIÓN
CASO PARA MAXIMIZAR

Seleccionamos el mayor elemento de toda la matriz , este valor restarlo de todos los elementos , los valores negativos representan los costos de oportunidad , lo que indica que se deja de ganar o producir .

EJEMPLO


NECESITAMOS PROCESAR 4 TAREAS PARA LA CUAL CINTAMOS CON 4 MAQUINAS.

EL DESPERDICIO QUE PRODUCIMOS DE LAS TAREAS POR MAQUINA DADA UNA MATRIZ EXPRESEMOS ESTO EN PESOS Y NECESITAMOS DEFINIR LA ASIGNACIÓN OPTIMA.

COMO SE TRATA DE DESPERDICIOS SE TRATA DE MINIMIZARLOS
Primero vemos que todas las casillas tengan un costo
Observamos que

M: renglones
N : columnas

Es igual a 4

Elegimos el menor valor del renglón y restarlo a los demas en este caso es 49 45 46 38

EN ESTA TABLA SOLO TENEMOS 3 LINEAS PARCIALES POR LO QUE TODAVIA NO HAYAMOS LO OPTIMO POR LO QUE TENEMOS QUE HACER OTRA TABLA

LOS VALORES MAS PEQUEÑOS DE LAS 3 FILAS ES 12 LO RESTAMOS A LOS DEMAS RESPETANDO LOS VALORES QUE ESTAN EN LA INTERSECCIÓN

PODEMOS OBSERVAR QUE LAS LINEAS INDICAN QUE 3= 4 NO ES OPTIMO SEGUIMOS BUSCANDO ASIGNAR RECURSOS A LAS ACT.

AHORA EL MENOR NUMERO ES 3 Y SE LO RESTAMOS A LOS DEMAS RESPETANDO LOS ASIGNADOS O INTERSECTADOS

OBSERVAMOS QUE M=N 4=4 ES LO OPTIMO PERO DEBEMOS CHECAR QUE LAS ASIGNACIONES SEAN 1A 1

LOS 0 SE PUEDEN ESCOGER PERO LOS 0 SE PUEDEN DESHABILITAR

INTERPRETACIÓN

REALIZAR LA TAREA A EN LA MAQUINA 3 CON UN COSTO DE 54
REALIZAR LA TAREA B EN LA MAQUINA 3 CON UN COSTO DE 81 $ 219
REALIZAR LA TAREA C EN LA MAQUINA 3 CON UN COSTO DE 46
REALIZAR LA TAREA D EN LA MAQUINA 3 CON UN COSTO DE 38


EL COSTO TOTAL MINIMO SERA DE 219 POR LA ASIGNACIÓN DE LAS TAREAS EN LA MAQUINA DE LA FORMA MAS OPTIMA.

PROBLEMAS DE TRANSPORTE

PROBLEMAS DE TRANSPORTE



PROBLEMA 1

Tres plantas de producción P1, P2 y P3 con capacidades de 100000, 100000, y 150000, respectivamente, tienen que abastecer cuatro ciudades C1 ,C2, C3 y C4, que demandan 50000, 70000, 60000 y 80000 unidades, respectivamente. Los costes de producción por unidad de cada planta son de 1 u. m., y los costes asociados al transporte por unidad se reflejan en la siguiente tabla:

Desarrollar un programa lineal que permita determinar el número de unidades que deberá producir cada planta y cuál será el plan de transporte que minimice los costes totales de la operación.

MODELO DE TRANSPORTE

MODELO DE TRANSPORTE

Este modelo trata, básicamente, de encontrar las mejores formas o rutas para el traslado de las mercancías, desde “n” orígenes hasta “m” destinos, para sus diferentes de almacenamiento, buscando la forma de minimizar los costos de transporte.

CONDICIONES:

1.-Tanto la función objetivo como las restricciones deben ser lineales
2.-Las mercancías a distribuir deben ser uniformes, así como los coeficientes de las variables en las restricciones deben ser 0 o 1.
3.-La suma de la capacidad de todos los orígenes debe ser igual a la suma de la capacidad de los destinos. En otras palabras, la demanda total tiene que ser igual a la oferta total.

m: Es el centro de la oferta
n: Es el centro de demanda
( i ): Renglón por cada origen
( j ): Cada destino una columna
Ai: No. De unidades disponibles en cada centro de oferta
bi: No. Requerido de unidades de mercancía en el centro de demanda
Cij: Costo unitario de transporte en la ruta de un centro de oferta a un centro de demanda.
Xij: Cantidad transportada del centro de oferta al centro de demanda.

CASO PRÁCTICO
Supongamos que a una empresa trasnacional que tiene 3 plantas W, X, e Y, y estas surten de un producto a 7 almacenes: A,B,C,D,E,F,G que forman parte del grupo empresarial, debemos considerar lo relacionado al costo de transporte desde cada planta a cada almacen. También, sabemos que cada almacén tiene ciertos requerimientos de ventas, mismas que dependen de la capacidad de cada planta.
Veamos en la siguiente tabla las capacidades de producción mensuales, los requerimientos de ventas por mes y los costos de transporte de cada planta hacia cada almacén.
Queremos determinar la ruta de distribución menos costosa y el costo total mínimo.