MÉTODO DE LOS MLTIPLICADORES

El método de multiplicadores es un procedimiento secuencial que empieza con una solución inicial factible del problema de transporte, para encontrar la solución óptima. En cada paso se intenta en este procedimiento enviar artículos por las rutas que no se hayan usado en la solución factible en curso, en tanto que se elimina una de las rutas que esté siendo usada actualmente. Este cambio de ruta se hace de modo que: la solución se conserve factible, mejore el valor de la función objetivo.

Pasos:
1. Use la solución actual para crear una trayectoria única del paso secuencial. Use estas trayectorias para calcular el costo marginal de introducir a la solución cada ruta no usada.

2. Si todos los costos marginales son iguales o mayores que cero, deténgase; se tendrá la solución óptima. Si no, elija la celdilla que tenga el costo marginal más negativo. (Los epates se resolverán arbitrariamente)

3. Usando la trayectoria del paso secuencial, determine el máximo número de artículos que se pueden asignar a la ruta elegida en el paso 2 y ajuste la distribución adecuadamente.

4. Regrese al paso 1.

MÉTODO VOGEL

MÉTODO VOGEL

El método comienza calculando por cada columna y por cada fila el castigo. El castigo se calcula como la diferencia entre los dos costos menores en la columna o en la fila según corresponda.

A continuación, se determina la fila o columna con un mayor valor de castigo. Luego, se selecciona como variable base la celda con menor costo de la fila o columna, según corresponda, y se le asigna la máxima cantidad posible.

Una vez realizada la asignación, se descarta la fila o columna cuya oferta o demanda haya sido completa. Se recalcula la demanda u oferta disponible en la fila o columna. La primera asignación se ha completado.

Se vuelven a calcular los castigos por fila y por columna y se repite el procedimiento descrito hasta completar las asignaciones posibles en la tabla.

MÉTODO DUAL

MÉTODO DUAL

En el algoritmo dual símplex, el problema empieza optimo y no factible. Las iteraciones sucesivas están diseñadas para avanzar hacía la factibilidad, sin violar la optimalidad. En iteración, cuando se restaura la factibilidad, el algoritmo termina.

El método dual símplex contrasta con el método regular (primal simplex), en el sentido de que las iteraciones empiezan factibles y no optimas y no continúan siendo factibles hasta que se logra la factibilidad.

En el método dual símplex, el cuadro simplex inicial debe tener un renglón objetivo optimo por lo menos con una variable básica no factible (<>

Condición Dual de Factibilidad: La variable de salida, x, es la variable básica que tiene el valor más negativo, con empates que se rompen arbitrariamente. Si todas las variables básicas son no negativas, el algoritmo termina.

Condición Dual de Optimalidad : La variable de entrada esta determinada entre las variables no básicas como la correspondiente a

min {øzj - cj ø, rj <>

no básicas rj

Donde rj es el coeficiente de restricción de la tabla símplex asociada con el renglón de la variable de salida x, y la columna de la variable de entrada Xj. Los empates se rompen arbitrariamente.

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 FORMA DE VECTOR COLUMNA (MATRIZ), PRIMAL.

	4 6 18 10

B= Y ESTOS SE CONVIERTEN EN VECTOR HORIZONTAL O

VERTICAL (MATRIZ FILA) TRASPUESTA ESTO ES:

B^T = 4,6,18,10

HACEMOS LAS RESTRICCIONES DEL PRIMAL EN FORMA DE MATRIZ

	1 0 0 1 3 2 1 4		1 0 0 1 3 2 1 4

A ; POR LO TANTO SU TRANSPUESTA A^T =

DUAL SERA

Y AL MAXIMIZAR

	3 5

C = 3,5 ; SU MATRIZ TRASPUESTA (DUAL) SERA C^T =

ESQUINA NORESTE

ESQUINA NORESTE

Para encontrar una solución inicial se comienza por la esquina superior izquierda (noroeste) del
tabla de transporte

EJEMPLO

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 .

MÓDELO DE ASIGNACIÓN

MÓDELO DE ASIGNACIÓN

Es una forma de representar a un modelo de transporte o una forma de asignar los recursos a las diferentes actividades ,estamos hablando de una matriz cuadrada es decir a una actividad corresponde un recurso

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 demás en el mismo renglón.

3- Para cada columna escogemos el menor valor y restarlos de todos los demás en la misma columna

4- Tachar el mínimo numero de líneas verticales y horizontales de forma que todos los ceros quedan tachados

5- Usar el criterio de optimización

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 interacción de 2 líneas

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 contamos 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.

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.

Nos sirve para resolver situaciones de ORIGEN – DESTINO basándose en el método de la Esquina Noreste.

a) Que la oferta = a la demanda

b) Debe haber linealidad

c) n = filas y m = columnas n + m = 1

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.

Ejemplo

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.

4+3=7-1 = 6

$ 2,200

MÉTODO DE LAS 2 FASES

MÉTODO 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

2x1+x2+2x3=15

x1,x2,x3>0

fase 1 siempre es un problema de minimización

min Z=r1

sujeto a

3x1+6x2+x3<20

2x1+x2+2x3=15

x1,x2,x3>0

EL MÉTODO DE LA GRAN “M” (PENALIZACIÓN)

EL MÉTODO DE LA GRAN “M” (PENALIZACIÓN)

El método de la gran M consiste en modificar el problema original para dar lugar a un nuevo problema agregando una variable W llamada artificial y que se penalizara mediante un costo “M” de valores grandes y positivos, y esto permite que la función objetivo tome valores muy grandes.

Cuando W salga de la base en ese momento W=0 y esto indica haber regresado al problema original, pero si se llega a W>0, entonces el problema no tendrá solución.

MinZ= C_x + M_w

Sujeta a las restricciones y penalizando a Z_w1 - C_w

• Condición de introducción de las variables

Restricción > resta

Restricción < suma

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= 4X₁ + X₂

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= 4X₁ +X₂

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=4X₁ +X₂ + MR₁ + MR₂

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

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 simplex 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

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

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