METODO DE LA ESQUINA NOROESTE.
Este método comienza asignando la cantidad máxima permisible para la oferta y la demanda a la variable X11 (la que está en la esquina noroeste de la tabla).
La columna o renglón satisfechos se tacha indicando que las variables restantes en la columna o renglón tachado son igual a cero. Si la columna y el renglón se satisfacen simultáneamente, únicamente uno (cualquiera de los dos) debe tacharse. Esta condición garantiza localizar las variables básicas cero si es que existen. Después de ajustar las cantidades de oferta y demanda para todos los renglones y columnas no tachados, la cantidad máxima factible se asigna al primer elemento no tachado en la nueva columna o renglón. El procedimiento termina cuando exactamente un renglón o una columna se dejan sin tachar.
Ejemplo 1:
Una compañía tiene 3 almacenes con 15, 25 y 5 artículos disponibles respectivamente. Con estos productos disponibles desea satisfacer la demanda de 4 clientes que requieren 5, 15, 15 y 10 unidades respectivamente. Los costos asociados con el envío de mercancía del almacén al cliente por unidad se dan en la siguiente tabla.
Clientes
Almacén....1....2....3....4
......1..........10...0..20..11
......2..........12...7...9...20
......3...........0...14..16..18
Construya la solución básica inicial por el método de la esquina noroeste.
Una compañía tiene 3 almacenes con 15, 25 y 5 artículos disponibles respectivamente. Con estos productos disponibles desea satisfacer la demanda de 4 clientes que requieren 5, 15, 15 y 10 unidades respectivamente. Los costos asociados con el envío de mercancía del almacén al cliente por unidad se dan en la siguiente tabla.
Clientes
Almacén....1....2....3....4
......1..........10...0..20..11
......2..........12...7...9...20
......3...........0...14..16..18
Construya la solución básica inicial por el método de la esquina noroeste.
______________________________________________________
MÉTODO DE ASIGNACION
El modelo de asignación es un caso especial del modelo de transporte, en el que los recursos se asignan a las actividades en términos de uno a uno, haciendo notar que la matriz correspondiente debe ser cuadrada. Así entonces cada recurso debe asignarse, de modo único a una actividad particular o asignación.
El modelo de asignación es un caso especial del modelo de transporte, en el que los recursos se asignan a las actividades en términos de uno a uno, haciendo notar que la matriz correspondiente debe ser cuadrada. Así entonces cada recurso debe asignarse, de modo único a una actividad particular o asignación.
Se tiene un costo Cij asociado con el recurso que es asignado, de modo que el objetivo es determinar en que forma deben realizarse todas las asignaciones para minimizar los costos totales.
El modelo de asignación es un caso especial del modelo de transporte, en el que los recursos se asignan a las actividades en términos de uno a uno, haciendo notar que la matriz correspondiente debe ser cuadrada. Así entonces cada recurso debe asignarse, de modo único a una actividad particular o asignación.
Se tiene un costo Cij asociado con el recurso que es asignado, de modo que el objetivo es determinar en que forma deben realizarse todas las asignaciones para minimizar los costos totales.
Ejemplo de un modelo de asignación general de tres orígenes y tres destinos es:
Ejemplos:
Se necesita procesar 4 diferentes tareas para lo cual se cuenta con 4 máquinas. Por diferencias tecnológicas el desperdicio que se produce depende del tipo de tarea y la máquina en la cual se ejecuta, dada la matriz de Desperdicios expresada en pesos definir la asignación óptima.
Se necesita procesar 4 diferentes tareas para lo cual se cuenta con 4 máquinas. Por diferencias tecnológicas el desperdicio que se produce depende del tipo de tarea y la máquina en la cual se ejecuta, dada la matriz de Desperdicios expresada en pesos definir la asignación óptima.
Como se trata de Desperdicios, buscaremos MINIMIZARLOS.
Checamos que todas las casillas tengan su costo unitario, en este caso se cumple sin ningún problema.
Balanceamos la tabla M= renglones = 4 N= columnas= 4
Por lo que M=N, quedando balanceada.
Checamos que todas las casillas tengan su costo unitario, en este caso se cumple sin ningún problema.
Balanceamos la tabla M= renglones = 4 N= columnas= 4
Por lo que M=N, quedando balanceada.
POR RENGLÓN
Elegir el menor valor de renglón y restarlo a los demás. En este caso es son : 49,45,46,38.
Restamos ese valor a cada uno de los demás del renglón.
Elegir el menor valor de renglón y restarlo a los demás. En este caso es son : 49,45,46,38.
Restamos ese valor a cada uno de los demás del renglón.
Formamos la nueva tabla
POR COLUMNA.
Elegimos los menores valores de cada columna en este caso son : 0,0,5,21
Restamos esos valores a los demás números de las columnas
Elegimos los menores valores de cada columna en este caso son : 0,0,5,21
Restamos esos valores a los demás números de las columnas
Trazamos las líneas.
Contamos el número de líneas y observamos que son 3 líneas y el número de la matriz es de 4 por lo que NO ES ÓPTIMO.
Buscamos dentro de la tabla el menor valor no tachado en este caso es 12
Lo restamos a todos los demás, respetando los valores de los ya tachados y adicionándolos a los que están intersectados.
Buscamos dentro de la tabla el menor valor no tachado en este caso es 12
Lo restamos a todos los demás, respetando los valores de los ya tachados y adicionándolos a los que están intersectados.
Nos queda:
Trazamos las líneas.
3 ≠ 4 NO ES ÓPTIMO
Volvemos a buscar el menor número de los no tachados.
3 ≠ 4 NO ES ÓPTIMO
Volvemos a buscar el menor número de los no tachados.
En este caso es 3 y se lo restamos a los demás no tachados y respetamos a los tachados y se los sumamos a los intersectados. Y volvemos a trazar líneas.
4=4 ES ÓPTIMO
Ahora checamos las asignaciones, sean 1 a 1.
Ahora checamos las asignaciones, sean 1 a 1.
Solución:
Realizar la tarea A en la máquina 3 con un costo de $54
Realizar la tarea B con la máquina 4 con un costo $81.
Realizar la tarea C en la máquina 1 con un costo $46.
Realizar la tarea D en la máquina 2 con un costo $38.COSTO TOTAL MÍNIMO= $219
Realizar la tarea A en la máquina 3 con un costo de $54
Realizar la tarea B con la máquina 4 con un costo $81.
Realizar la tarea C en la máquina 1 con un costo $46.
Realizar la tarea D en la máquina 2 con un costo $38.COSTO TOTAL MÍNIMO= $219
_____________________________________________________
MÉTODOLOGIA Y DEFINICION DE VOGEL
Método de Aproximación de Vogel: para cada renglón y columna que queda bajo consideración, se calcula su diferencia, que se define como la diferencia aritmética entre el costo unitario más pequeño (cij) y el que le sigue, de los que quedan en ese renglón o columna. (Si se tiene un empate para el costo más pequeño de los restantes de un renglón o columna, entonces la diferencia es 0). En el renglón o columna que tiene la mayor diferencia se elige la variable que tiene el menor costo unitario que queda. (Los empates para la mayor de estas diferencias se pueden romper de manera arbitraria).
Para hacer más concreta esta descripción, se ilustrará el procedimiento general, utilizando el método de aproximación de Vogel
para resolver el ejemplo presentado anteriormente y que fue resuelto por la regla de la esquina noroeste:
Iniciamos el método calculando las primeras diferencias para cada renglón y columna. De las diferencias que obtuvimos nos fijamos en la mayor (¿Por qué?), que resulta ser para la tercera columna. En esa columna encontramos el costo unitario (cij) menor y en esa celda realizamos la primera asignación:
Método de Aproximación de Vogel: para cada renglón y columna que queda bajo consideración, se calcula su diferencia, que se define como la diferencia aritmética entre el costo unitario más pequeño (cij) y el que le sigue, de los que quedan en ese renglón o columna. (Si se tiene un empate para el costo más pequeño de los restantes de un renglón o columna, entonces la diferencia es 0). En el renglón o columna que tiene la mayor diferencia se elige la variable que tiene el menor costo unitario que queda. (Los empates para la mayor de estas diferencias se pueden romper de manera arbitraria).
Para hacer más concreta esta descripción, se ilustrará el procedimiento general, utilizando el método de aproximación de Vogel
para resolver el ejemplo presentado anteriormente y que fue resuelto por la regla de la esquina noroeste:
Iniciamos el método calculando las primeras diferencias para cada renglón y columna. De las diferencias que obtuvimos nos fijamos en la mayor (¿Por qué?), que resulta ser para la tercera columna. En esa columna encontramos el costo unitario (cij) menor y en esa celda realizamos la primera asignación:
Nota: Marcaremos a la mayor de las diferencias seleccionada encerrándola en un círculo y escribiéndole como superíndice el número que le corresponda en la secuencia de selección.
Observemos en la figura anterior que únicamente eliminamos el segundo renglón ya que la tercera columna nos servirá después para hacer la asignación de una variable básica degenerada. Continuando con la aplicación del método, tenemos que calcular nuevamente las diferencias de las columnas ya que hemos eliminado un renglón y ésto puede ocasionar que las diferencias aritméticas entre el costo unitario más pequeño y el que le sigue ya no sean las mismas:
Observemos en la figura anterior que únicamente eliminamos el segundo renglón ya que la tercera columna nos servirá después para hacer la asignación de una variable básica degenerada. Continuando con la aplicación del método, tenemos que calcular nuevamente las diferencias de las columnas ya que hemos eliminado un renglón y ésto puede ocasionar que las diferencias aritméticas entre el costo unitario más pequeño y el que le sigue ya no sean las mismas:
Como siguiente paso deberíamos calcular las nuevas diferencias de columnas, pero ya que solamente queda un renglón dentro de las posibilidades (ésto no significa que solamente un renglón quede bajo consideración ya que podemos observar que ninguna de las cuatro columnas (destinos) ha sido eliminada y todas quedan todavía bajo consideración), no es posible encontrar la diferencia aritmética entre el costo menor y el que le sigue, por lo tanto vamos tomando una a una las celdas que quedan comenzando con la de menor costo unitario hasta que todas hayan sido asignadas.
La solución inicial básica factible es x11=3, x12=1, x13=0 (variable básica degenerada), x14=1, x23=2 y x32=3 y el costo total de transporte asociado a esta primera “Política de Transporte” factible es de:
Es necesario aclarar que ésta puede o no ser la solución final del problema, es necesario aplicar a esta primera solución factible la prueba de optimalidad ya que puede existir una mejor “política de transporte” que minimice todavía más el costo total.
_____________________________________________________
METODO DE LAS DOS FASES
FASE 1.
Formule 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 mínimo de la función objetivo óptimo será cero, lo cual indica que todas las variables artificiales son cero. En este momento pasamos a la fase 2.
* Si el valor mínimo de la función objetivo óptima es mayor que cero, el problema no tiene solución y termina anotándose que no existen soluciones factibles
FASE 2.
Utilice la solución óptima de la fase 1 como solución de inicio para el problema original. En este caso, la función objetivo original se expresa en términos de las variables no básicas utilizando las eliminaciones usuales Gauss-Jordan.
FASE 1.
Formule 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 mínimo de la función objetivo óptimo será cero, lo cual indica que todas las variables artificiales son cero. En este momento pasamos a la fase 2.
* Si el valor mínimo de la función objetivo óptima es mayor que cero, el problema no tiene solución y termina anotándose que no existen soluciones factibles
FASE 2.
Utilice la solución óptima de la fase 1 como solución de inicio para el problema original. En este caso, la función objetivo original se expresa en términos de las variables no básicas utilizando las eliminaciones usuales Gauss-Jordan.
PROBLEMA # 1
Minimizar Z = 2000X1 + 500X2
Sujeto a:
2X1 + 3X2 > 36
3X1 + 6X2 > 60
X1, X2 > 0
Minimizar Z = 2000X1 + 500X2
Sujeto a:
2X1 + 3X2 > 36
3X1 + 6X2 > 60
X1, X2 > 0
Minimizar Z = 2000X1 + 500X2
Sujeto a:
2X1 + 3X2 + R1 = 36 + S1
3X1 + 6X2 + R2 = 60 +S2
X1, X2 > 0
Sujeto a:
2X1 + 3X2 + R1 = 36 + S1
3X1 + 6X2 + R2 = 60 +S2
X1, X2 > 0
FASE I
Minimizar Z = R1 + R2
Sujeto a:
2X1 + 3X2 - S1 + R1 = 36
3X1 + 6X2 - S2 + R2 = 60
X1, X2 > 0
Minimizar Z – 0X1 – 0X2 – 0S1 – 02 – R1 – R2 = 0
Sujeto a:
2X1 + 3X2 - S1 + R1 = 36
3X1 + 6X2 - S2 + R2 = 60
X1, X2 > 0
Minimizar Z = R1 + R2
Sujeto a:
2X1 + 3X2 - S1 + R1 = 36
3X1 + 6X2 - S2 + R2 = 60
X1, X2 > 0
Minimizar Z – 0X1 – 0X2 – 0S1 – 02 – R1 – R2 = 0
Sujeto a:
2X1 + 3X2 - S1 + R1 = 36
3X1 + 6X2 - S2 + R2 = 60
X1, X2 > 0
FASE II.
Minimizar
Z = 2000X1 + 5000X2 + OS1 + OS2
Z - 2000X1 - 5000X2 - OS1 - OS2 = 0
Minimizar
Z = 2000X1 + 5000X2 + OS1 + OS2
Z - 2000X1 - 5000X2 - OS1 - OS2 = 0
FASE II.
Minimizar
Z = 2000X1 + 5000X2 + OS1 + OS2
Z - 2000X1 - 5000X2 - OS1 - OS2 = 0
Minimizar
Z = 2000X1 + 5000X2 + OS1 + OS2
Z - 2000X1 - 5000X2 - OS1 - OS2 = 0
Solución Óptima:
X1 = 0
X2 = 12
Z = 6000
__________________________________________________________
X1 = 0
X2 = 12
Z = 6000
__________________________________________________________
DEFINICIÓN Y APLICACIÓN DEL MODELO DE TRANSPORTE
El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Los datos del modelo son:
1. Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.
2. El costo de transporte unitario de la mercancía a cada destino.
Como solo hay una mercancía un destino puede recibir su demanda de una o más fuentes. El objetivo del modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino, tal que se minimice el costo del transporte total.
La suposición básica del modelo es que el costo del transporte en una ruta es directamente proporcional al número de unidades transportadas. La definición de “unidad de transporte” variará dependiendo de la “mercancía” que se transporte.
El esquema siguiente representa el modelo de transporte como una red con m fuentes y n destinos. Una fuente o un destino esta representado por un nodo, el arco que une fuente y un destino representan la ruta por la cual se transporta la mercancía. La cantidad de la oferta en la fuente i es ai, y la demanda en el destino j es bj. El costo de transporte unitario entre la fuente i y el destino j es Cij.
Si Xi j representa la cantidad transportada desde la fuente i al destino j, entonces, el modelo general de PL que representa el modelo de transporte es:
Si Xi j representa la cantidad transportada desde la fuente i al destino j, entonces, el modelo general de PL que representa el modelo de transporte es:
Minimizar Z= S i=1 m S j=1 n C i j X i j
Sujeta a:
S j=1 n X i j <= ai , i=1,2,…, m S i=1 m X I j >= bj , j=1,2,…, n
X i j >=0 para todas las i y j
Sujeta a:
S j=1 n X i j <= ai , i=1,2,…, m S i=1 m X I j >= bj , j=1,2,…, n
X i j >=0 para todas las i y j
El primer conjunto de restricciones estipula que la suma de los envíos desde una fuente no puede ser mayor que su oferta; en forma análoga, el segundo conjunto requiere que la suma de los envíos a un destino satisfaga su demanda.
El modelo que se acaba de escribir implica que la oferta total Si=1 m ai debe ser cuando menos igual a la demanda total Sj=1 n bj. Cuando la oferta total es igual a la demanda total, la formulación resultante recibe el nombre de modelo de transporte equilibrado. Este difiere del modelo solo en el hecho de que todas las restricciones son ecuaciones, es decir:
El modelo que se acaba de escribir implica que la oferta total Si=1 m ai debe ser cuando menos igual a la demanda total Sj=1 n bj. Cuando la oferta total es igual a la demanda total, la formulación resultante recibe el nombre de modelo de transporte equilibrado. Este difiere del modelo solo en el hecho de que todas las restricciones son ecuaciones, es decir:
SX i j = ai, i=1,2,..., m
SX i j = bj, j=1,2,..., n
En el mundo real, no necesariamente la oferta debe ser igual a la demanda o mayor que ella. Sin embargo, un modelo de transporte siempre puede equilibrarse. El equilibrio, además de su utilidad en la representación a través de modelos de ciertas situaciones prácticas, es importante para el desarrollo del método de solución que explote completamente la estructura especial del modelo de transporte. Los dos ejemplos que siguen presentan la idea del equilibrio y también sus implicaciones prácticas.
SX i j = bj, j=1,2,..., n
En el mundo real, no necesariamente la oferta debe ser igual a la demanda o mayor que ella. Sin embargo, un modelo de transporte siempre puede equilibrarse. El equilibrio, además de su utilidad en la representación a través de modelos de ciertas situaciones prácticas, es importante para el desarrollo del método de solución que explote completamente la estructura especial del modelo de transporte. Los dos ejemplos que siguen presentan la idea del equilibrio y también sus implicaciones prácticas.
Ejemplo 1
MG Auto Company tiene plantas en Los Ángeles, Detroit y Nueva Orleáns. Sus centros de distribución principales son Denver y Miami. Las capacidades de las plantas durante el trimestre próximo son 1 000, 1 500, y 1 200 automóviles. Las demandas trimestrales en los dos centros de distribución son de 2 300 y 1 400 vehículos. El costo del transporte de un automóvil por tren es de 8 centavos por milla. El diagrama de las distancias recorridas entre las plantas y los centros de distribución son:
MG Auto Company tiene plantas en Los Ángeles, Detroit y Nueva Orleáns. Sus centros de distribución principales son Denver y Miami. Las capacidades de las plantas durante el trimestre próximo son 1 000, 1 500, y 1 200 automóviles. Las demandas trimestrales en los dos centros de distribución son de 2 300 y 1 400 vehículos. El costo del transporte de un automóvil por tren es de 8 centavos por milla. El diagrama de las distancias recorridas entre las plantas y los centros de distribución son:
Mediante el uso de códigos numéricos que representan las plantas y centros de distribución, hacemos que X i j represente el número de automóviles transportados de la fuente i al destino j. Como la oferta total (= 1 000 + 1 500 + 1 200 = 3 700) es igual a la demanda ( = 2 300 + 1 400 = 3 700), el modelo de transporte resultante esta equilibrado. Por lo tanto, el siguiente modelo de PL que representa el problema tiene todas las restricciones de igualdad.
Minimizar Z = 80X 11 + 215X 12 + 100X 21 + 108X 22 + 102X 31 + 68X 32
Minimizar Z = 80X 11 + 215X 12 + 100X 21 + 108X 22 + 102X 31 + 68X 32
Sujeto a:
X 11 X 12 = 1 000
X 21 X 22 = 1 500
X 31 X 32 = 1 200
X 11 X 21 X 31 = 2 300
X 12 X 22 X 32 = 1 400
X i j para todas las i y j
X 11 X 12 = 1 000
X 21 X 22 = 1 500
X 31 X 32 = 1 200
X 11 X 21 X 31 = 2 300
X 12 X 22 X 32 = 1 400
X i j para todas las i y j
_______________________________________________________
EL MÉTODO DUAL SIMPLEX
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 (sí esta existe). Nótese que la base de su lógica es mantener la factibilidad, mientras busca la optimalidad. 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 solución óptima.
El nuevo algoritmo fue desarrollo en 1954 por C. E. Lemke y se conoce con el nombre de Método Dual-Simplex. A continuación se presenta su estructura y un ejemplo para ilustrar su aplicación.
Algoritmo Dual-Simplex para un modelo de maximización
Introducción
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.Al hacer lo anterior se logra que debajo de las variables básicas aparezca una matriz identidad, que es la que el simplex siempre toma como base inicial.
Obtendremos que los términos del lado derecho de las ecuaciones multiplicadas por (-1) quedan con signo negativo, lo cual hace que la solución inicial sea infactible.
Es importante destacar que este proceso es muy útil ya que en muchos modelos evita la inclusión de variables artificiales en el momento de transformar un modelo a formato estándar.
El algoritmo para resolver un modelo de maximización es el siguiente:
Paso 1: Hallar una solución básica inicial infactible e inmejorable
Escribir el tablero inicial tomando a las variables de holgura y de exceso como variables básicas iniciales Paso 2: Prueba de factibilidad
a. Si todas las variables básicas son no negatívas, la actual solución es la óptima.
b. Si hay al menos una variable básica negativa, seleccionar como variable de salida,( llamémosla (XB)s ), a aquella con el valor mas negativo. Los empates se pueden romper arbitrariamente.
Paso 3: Prueba de inmejorabilidad
a. Sí en el renglón de la variable básica de salida (XB)s todos los coeficientes de reemplazo con las variables no básicas son no negativos, la solución del modelo es óptima ¡limitada. Se termina el proceso.
Si en el renglón de la variable básica de salida (XB)s, hay al menos un coeficiente de intercambio negativo , se efectúan los cocientes entre el efecto neto de cada variable no básicas y su correspondientel coeficiente de intercambio negativo.
Es decir, siendo (XB)s la variable de salida se calculan todos los cocientes
Se toma como variable de entrada ( llamémosla Xe ) a aquella que corresponda al mínimo de los cocientes del anterior conjuntoSi la variable de entrada es Xe el elemento pivote será el elemento (Se)s
El empate se puede romper arbitrariamente.
b. Aplicar la operación de pivoteo para generar la nueva tabla, en la cual aparezca Xe como variable básica en lugar de la variable de salida (XB)s
c. Repetir el algoritmo a partir del paso 2.
Ejemplo de aplicación del Método Dual Simplex
Sea el siguiente modelo:
El empate se puede romper arbitrariamente.
b. Aplicar la operación de pivoteo para generar la nueva tabla, en la cual aparezca Xe como variable básica en lugar de la variable de salida (XB)s
c. Repetir el algoritmo a partir del paso 2.
Ejemplo de aplicación del Método Dual Simplex
Sea el siguiente modelo:
'
Expresemos el modelo en formato estándar
multipliquemos por (-1) en ambos lados de las ecuaciones, para formar los vectores unitarios, requeridos para contar con una base inicial unitaria
paso 1.
Tomando las variables básicas iniciales hacemos lo siguiente:
Tomando las variables básicas iniciales hacemos lo siguiente:
Paso 2
Sale E2 = (XB)2 o sea s = 2
Paso 3
a. Calculando los cocientes para todo (Sj)2 < id="BLOGGER_PHOTO_ID_5191415677997158930" style="CURSOR: hand" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiMLn2WQYMp70QOp0ixvwuZT1Aix3I-70QV3BOQQME-ReZ6WZig2Y1rWgsbaqCR-ahVYOcXFt59GawM97ngrWGgpft1jaFHq_M5o9-unp_3zh9Wnz45p1d3EcaNCNa3RgBbJWCxGn8Rzhyphenhyphend/s400/5-6.jpg" border="0">
Sale E2 = (XB)2 o sea s = 2
Paso 3
a. Calculando los cocientes para todo (Sj)2 < id="BLOGGER_PHOTO_ID_5191415677997158930" style="CURSOR: hand" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiMLn2WQYMp70QOp0ixvwuZT1Aix3I-70QV3BOQQME-ReZ6WZig2Y1rWgsbaqCR-ahVYOcXFt59GawM97ngrWGgpft1jaFHq_M5o9-unp_3zh9Wnz45p1d3EcaNCNa3RgBbJWCxGn8Rzhyphenhyphend/s400/5-6.jpg" border="0">
o sea que X3 es la variable de entrada( entonces e = 3) y el elemento pivote es el (Se)s = (S3)2 = -9
b. Efectuando el pivoteo obtenemos la tabla siguiente:
Tabla 1 (maximizar)
b. Efectuando el pivoteo obtenemos la tabla siguiente:
Tabla 1 (maximizar)
c. Repitiendo el algoritmo desde el paso 1, obtenemos:
sale E1 = (XB)1 y entra X2 por lo cual obtenemos la siguiente tabla
sale E1 = (XB)1 y entra X2 por lo cual obtenemos la siguiente tabla
Tabla 2
Como se observa, ahora estamos en el óptimo.En definitiva:
X2* = 11/7
X2* = 11/7
X3* = 13/7
Z* = - 61/7
__________________________________________________________
METODO DE MULTIPLICADORES
Este método reproduce exactamente las mismas iteraciones del método de banquillo. La principal diferencia ocurre en la forma en que las variables no básicas se evalúan en cada iteración. Asociados a cada renglón i de la tabla existen multiplicadores Ui similarmente se asocia un multiplicador Vj a cada columna de la tabla j. Para cada variable básica Xij de la solución actual, se escribe la ecuación Ui +Vj = Cij. Esas ecuaciones proporcionan m+n-1 relaciones con m+n incógnitas.
Los valores de los multiplicadores pueden ser determinados a partir de las ecuaciones suponiendo un valor arbitrario para cualquiera de los multiplicadores (usualmente se establece U1=0) y resolviendo el sistema de ecuaciones para encontrar los multiplicadores desconocidos. Una vez que se hace esto, la evaluación de cada variable no básica X pq está dada como:
El criterio que se utiliza para seleccionar la variable que entra es el mismo que el método de banquillo (la mayor negativa).
Ejemplo:
Una compañía está considerando una demanda de 5 clientes utilizando artículos que tienen disponibles en 2 almacenes. Los almacenes cuentan con 800 y 1000 unidades respectivamente. Los clientes necesitan 200, 150, 200, 180 y 500 unidades respectivamente. Los costos de embarque por artículo de los almacenes de los clientes son:
Los valores de los multiplicadores pueden ser determinados a partir de las ecuaciones suponiendo un valor arbitrario para cualquiera de los multiplicadores (usualmente se establece U1=0) y resolviendo el sistema de ecuaciones para encontrar los multiplicadores desconocidos. Una vez que se hace esto, la evaluación de cada variable no básica X pq está dada como:
El criterio que se utiliza para seleccionar la variable que entra es el mismo que el método de banquillo (la mayor negativa).
Ejemplo:
Una compañía está considerando una demanda de 5 clientes utilizando artículos que tienen disponibles en 2 almacenes. Los almacenes cuentan con 800 y 1000 unidades respectivamente. Los clientes necesitan 200, 150, 200, 180 y 500 unidades respectivamente. Los costos de embarque por artículo de los almacenes de los clientes son:
Resuelva el modelo de transporte empleando.
a) Una solución inicial por el método de aproximación de vogel.
b) La solución óptima por el método de multiplicadores.
a) Una solución inicial por el método de aproximación de vogel.
b) La solución óptima por el método de multiplicadores.
DESTINO FICTICIO = 570 ARTÍCULOS
Z = (15)(200) + (23)(200) +(18)(180) + (40)(220) + (22)(150) + (44)(280) + (0)(570) = $35,260
