• Author / Uploaded
• Carlos Conrado

• Categories
• Ecuaciones
• Archivo de computadora
• Conceptos matemáticos
• Física y matemáticas
• Matemáticas

Citation preview

FUNDACION UNIVERSITARIA DEL AREA ANDINA

Actividad Evaluativo 4

Presentado por:

Cristhian Camilo Contreras Rodriguez Jorge Antonio Tarazona Romero Hernán David Conrado Medina

Investigación de Operaciones 2019

Contenido Introducción: ........................................................................................................................... 3 Descripción del taller: ............................................................................................................. 3 Requisitos para el taller: ......................................................................................................... 4 Desarrollar todos los pasos necesarios para hallar la solución básica inicial utilizando el método de aproximación de Russel (se debe incluir los que ya están desarrollados en el referente 4, sin omitir cálculo alguno). Se solicita elaborar estos desarrollos en un archivo de Word haciendo uso del editor de ecuaciones en las situaciones que sea necesario ........... 4 Aplicar la prueba de optimalizad inicial, la cual efectivamente indicará que la solución básica inicial hallada no es óptima. Se solicita elaborar estos desarrollos en un archivo de Word haciendo uso del editor de ecuaciones en las situaciones que sea necesario....... Error! Bookmark not defined. Realizar todos los procesos iterativos requeridos para hallar la solución óptima (se debe incluir los que ya están desarrollados en el referente 4, sin omitir cálculo alguno). Se solicita elaborar estos desarrollos en un archivo de Word haciendo uso del editor de ecuaciones en las situaciones que sea necesario. .................. Error! Bookmark not defined. Referencias: .......................................................................... Error! Bookmark not defined.

Introducción: En el presente documento podemos observar un problema de una compañía que distribuye agua en tanques el cual podemos encontrar una gráfica con los parámetros fundamentales del problema el cual podemos encontrar los pasos necesarios para hallar la solución básica inicial utilizando el método de aproximación de Russel, la Aplicación de las pruebas de optimalizad inicial y los procesos iterativos requeridos para hallar la solución óptima. Descripción del taller: La solución a abordar en el presente Taller se refiere al problema tratado en el referente 4, según el cual una compañía distribuye agua en tanques a sectores que tienen difícil acceso al servicio, para ello compra el agua en unas fuentes reales O1 ,O2 y O3 y las distribuye a los destinos reales D1 ,D2 ,D3 y D4 sometida a un conjunto de limitaciones. En el proceso de modelado como problema de trasporte, luego de realizar algunas consideraciones, en las cuales se debe incorporar un origen ficticio O4f y redefinir los destinos de tal manera que uno de ellos se divide en 2 teniéndose un nuevo modelo con cinco destinos, el modelo resultante es el siguiente.

Se espera que de manera colaborativa se dé la solución completa, presentando explícitamente los cálculos omitidos en el documento del referente 1.

Requisitos para el taller: 

Desarrollar todos los pasos necesarios para hallar la solución básica inicial utilizando el método de aproximación de Russel (se debe incluir los que ya están desarrollados en el referente 4, sin omitir cálculo alguno). Se solicita elaborar estos desarrollos en un archivo de Word haciendo uso del editor de ecuaciones en las situaciones que sea necesario.

Método de aproximación de Russell En este método, para cada fila de origen 𝑂𝑖 que aún se considere se halla el mayor costo unitario 𝑐𝑖𝑗 de los que quedan en esa fila, denotado mediante ᾱ𝑖 . mientras que para la columna de destino 𝐷𝑗 que se está considerando se halla el mayor costo unitario 𝑐𝑖𝑗 de los que están en la columna, denotado por 𝛽𝑖𝑗̇ y para las variables 𝑥𝑖𝑗 aun no se seleccionadas de estas filas o columnas se calcula ∆𝑖𝑗 dado por ∆𝑖𝑗 = 𝑐𝑖𝑗 − ᾱ𝑖 − 𝛽𝑖 . las variables cuyo valor de ∆𝑖𝑗 sea más negativo es seleccionada como variable básica. ∆𝑖𝑗 = 𝑐𝑖𝑗 − 𝛼̅𝑖 − 𝛽𝑖 En la primera iteración de este método, para seleccionar la primera variable básica, encontramos que los correspondientes valores de 𝛼̅𝑖 y 𝛽𝑖 son: 𝛼̅1 22

𝛼̅2 19

𝛼̅3 M

𝛼̅4 M

𝛽1 M

𝛽2 19

X11 = 16 − 22 − 𝑀 = −6 − 𝑀 X21 = 14 − 19 − 𝑀 = −5 − 𝑀 X31 = 19 − M − M = 19 − 2𝑀 X41 = M − M − 𝑀 = −𝑀 X12 = 16 − 22 − 19 = −25 X22 = 14 − 19 − 19 = −24 X32 = 19 − M − 19 = −𝑀

𝛽3 M

𝛽4 23

𝛽5 M

X42 = 0 − M − 19 = −19 − 𝑀 X13 = 13 − 22 − 𝑀 = −9 − 𝑀 X23 = 13 − 19 − 𝑀 = −6 − 𝑀 X33 = 20 − M − 𝑀 = 20 − 2𝑀 X43 = M − M − 𝑀 = −𝑀 X14 = 22 − 22 − 23 = −23 X24 = 19 − 19 − 23 = −23 X34 = 23 − M − 23 = −𝑀 X44 = 0 − M − 23 = −23 − 𝑀 X15 = 17 − 22 − 𝑀 = −5 − 𝑀 X25 = 15 − 19 − 𝑀 = −4 − 𝑀 X35 = M − M − 𝑀 = −𝑀 X45 = 0 − M − 𝑀 = −2𝑀 Al calcular todos los valores de ∆𝑖𝑗 = 𝑐𝑖𝑗 − ᾱ𝑖 − 𝛽𝑖 (usando los respectivos valores 𝑐𝑖𝑗 ) encontramos que ∆45 = 2𝑀 es el más negativo de los ∆𝑖𝑗 por tanto se selecciona 𝑋45 como variable básica y se asigna 𝑋45 = 50, con lo cual se agota la disponibilidad del origen 𝑂4 y en la siguiente selección no se considera la fila de este origen. En la segunda iteración los correspondientes valores de 𝛼̅𝑖 y 𝛽𝑖 son: 𝛼̅1 22

𝛼̅2 19

𝛼̅3 M

𝛽1 19

𝛽2 19

𝛽3 20

𝛽4 23

𝛽5 M

X11 = 16 − 22 − 19 = −25 X21 = 14 − 19 − 19 = −24 X31 = 19 − M − 19 = −𝑀 X12 = 16 − 22 − 19 = −25 X22 = 14 − 19 − 19 = −24 X32 = 19 − M − 19 = −𝑀 X13 = 13 − 22 − 20 = −29 X23 = 13 − 19 − 20 = −26 X33 = 20 − M − 20 = −𝑀 X14 = 22 − 22 − 23 = −23 X24 = 19 − 19 − 23 = −23 X34 = 23 − M − 23 = −𝑀 X15 = 17 − 22 − 𝑀 = −5 − 𝑀 X25 = 15 − 19 − 𝑀 = −4 − 𝑀 X35 = M − M − 𝑀 = −𝑀 Al calcular los valores de ∆𝑖𝑗 encontramos que ∆15 = 5 − 𝑀 es el más negativo de los ∆𝑖𝑗 por lo tanto se selecciona X15 como variable básica y se asigna X15 = 10, para completar la demanda de la columna 5 y no volver a considerarla y dejando una disponibilidad de 40 en el origen 𝑂1.

Para la tercera selección tenemos: 𝛼̅1 22

𝛼̅2 19

𝛼̅3 23

𝛽1 19 X11 X21 X31 X12 X22 X32 X13 X23 X33 X14 X24 X34

𝛽2 19

𝛽3 20

𝛽4 23

= 16 − 22 − 19 = −25 = 14 − 19 − 19 = −24 = 19 − 23 − 19 = −23 = 16 − 22 − 19 = −25 = 14 − 19 − 19 = −24 = 19 − 23 − 19 = −23 = 13 − 22 − 20 = −29 = 13 − 19 − 20 = −26 = 20 − 23 − 20 = −23 = 22 − 22 − 23 = −23 = 19 − 19 − 23 = −23 = 23 − 23 − 23 = −23

Al calcular los valores de ∆𝑖𝑗 encontramos que ∆13 = −29 es el más negativo de los ∆𝑖𝑗 por lo tanto se selecciona X13 como variable básica y se asigna X13 = 40, lo que aún no completa la demanda de la columna 3, además se agota la disponibilidad del origen 𝑂1 y en la siguiente selección no se considera la fila de este origen. Para la cuarta selección tenemos: 𝛼̅2 19

𝛼̅3 23

𝛽1 19

𝛽2 19 X21 X31 X22 X32 X23 X33 X24 X34

𝛽3 20

𝛽4 23

= 14 − 19 − 19 = −24 = 19 − 23 − 19 = −23 = 14 − 19 − 19 = −24 = 19 − 23 − 19 = −23 = 13 − 19 − 20 = −26 = 20 − 23 − 20 = −23 = 19 − 19 − 23 = −23 = 23 − 23 − 23 = −23

Al calcular los valores de ∆𝑖𝑗 encontramos que ∆23 = −26 es el más negativo de los ∆𝑖𝑗 por lo tanto se selecciona X23 como variable básica y se asigna X23 = 30, para completar la demanda de la columna 3 y no volver a considerarla y dejando una disponibilidad de 30 en el origen 𝑂2. Para la quinta selección tenemos:

𝛼̅2 19

𝛼̅3 23

𝛽1 19

𝛽2 19 X21 X31 X22 X32 X24 X34

𝛽4 23

= 14 − 19 − 19 = −24 = 19 − 23 − 19 = −23 = 14 − 19 − 19 = −24 = 19 − 23 − 19 = −23 = 19 − 19 − 23 = −23 = 23 − 23 − 23 = −23

Al calcular los valores de ∆𝑖𝑗 encontramos que ∆21 = −24 es el más negativo de los ∆𝑖𝑗 por lo tanto se selecciona X21 como variable básica y se asigna X21 = 30, para completar la demanda de la columna 1 y no volver a considerarla además se agota la disponibilidad del origen 𝑂2 y en la siguiente selección no se considera la fila de este origen. Para la sexta selección tenemos: 𝛼̅3 23

𝛽2 19

𝛽4 23 X32 = 19 − 23 − 19 = −23 X34 = 23 − 23 − 23 = −23

Al calcular los valores de ∆𝑖𝑗 encontramos que ∆32 = −23 es el más negativo de los ∆𝑖𝑗 por lo tanto se selecciona X32 como variable básica y se asigna X32 = 20, para completar la demanda de la columna 2 y dejando una disponibilidad de 30 en el origen 𝑂3. Para la séptima selección tenemos: 𝛼̅3 23

𝛽4 23 X34 = 23 − 23 − 23 = −23

Al calcular los valores de ∆𝑖𝑗 encontramos que ∆34 = −23 es el más negativo de los ∆𝑖𝑗 por lo tanto se selecciona X34 como variable básica y se asigna X34 = 30, para completar la demanda de la columna 4 y no volver a considerarla además se agota la disponibilidad del origen 𝑂3 y en la siguiente selección no se considera la fila de este origen. Mientras que el valor de Z es: 𝑍 = 13𝑋13 + 17𝑋15 + 14𝑋21 + 13𝑋23 + 19𝑋31 + 19𝑋32 + 23𝑋34 + 0𝑋45 𝑍 = 13(40) + 17(10) + 14(30) + 13(30) + 19(20) + 23(30) + 0(50)

𝑍 = 520 + 170 + 420 + 390 + 380 + 690 = 2570



Aplicar la prueba de optimalizad inicial, la cual efectivamente indicará que la solución básica inicial hallada no es óptima. Se solicita elaborar estos desarrollos en un archivo de Word haciendo uso del editor de ecuaciones en las situaciones que sea necesario

La solución básica factible hallada en la fase de iniciación es: 𝑋45 = 50, 𝑋15 = 10, 𝑋13 = 40, 𝑋23 = 30, 𝑋21 = 30, 𝑋31 = 0, 𝑋32 = 20, 𝑋34 = 30 Los respectivos valores de 𝑐𝑖𝑗 a utilizar son los respectivos costos: 𝑐45 = 0, 𝑐15 = 17, 𝑐13 = 40, 𝑐23 = 13, 𝑐21 = 14, 𝑐31 = 19, 𝑐32 = 19, 𝑐34 = 23 𝑃𝑎𝑟𝑎 𝑥𝑖𝑗 : 𝑐𝑖𝑗 = 𝑢𝑖 + 𝑣𝑗 La tercera fila es la de mayor asignación, por tanto tomamos 𝑢3 = 0, entonces: 𝑃𝑎𝑟𝑎 𝑥31 : 𝑐31 = 19 = 𝑢3 + 𝑣1 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 19 = 0 + 𝑣1 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣1 = 19 𝑃𝑎𝑟𝑎 𝑥32 : 𝑐32 = 19 = 𝑢3 + 𝑣2 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 19 = 0 + 𝑣2 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣2 = 19 𝑃𝑎𝑟𝑎 𝑥34 : 𝑐34 = 23 = 𝑢3 + 𝑣4 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 23 = 0 + 𝑣4 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣4 = 23 𝑃𝑎𝑟𝑎 𝑥21 : 𝑐21 = 14 = 𝑢2 + 𝑣1 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 14 = 𝑢2 + 19, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑢2 = −5 𝑃𝑎𝑟𝑎 𝑥23 : 𝑐23 = 13 = 𝑢2 + 𝑣3 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 13 = −5 + 𝑣4 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣3 = 18 𝑃𝑎𝑟𝑎 𝑥13 : 𝑐13 = 13 = 𝑢1 + 𝑣3 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 13 = 𝑢1 + 18, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑢2 = −5 𝑃𝑎𝑟𝑎 𝑥15 : 𝑐15 = 17 = 𝑢1 + 𝑣5 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 17 = −5 + 𝑣5 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣5 = 22 𝑃𝑎𝑟𝑎 𝑥45 : 𝑐45 = 0 = 𝑢4 + 𝑣5 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 0 = 𝑢4 + 22, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑢4 = −22 Ahora se puede hallar los valores 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗 para las variables no básicas: 𝑃𝑎𝑟𝑎 𝑥11 : 𝑐11 − 𝑢1 − 𝑣1 = 16 + 5 − 19 = 2 ≥ 0 𝑃𝑎𝑟𝑎 𝑥12 : 𝑐12 − 𝑢1 − 𝑣2 = 16 + 5 − 19 = 2 ≥ 0 𝑃𝑎𝑟𝑎 𝑥14 : 𝑐14 − 𝑢1 − 𝑣4 = 22 + 5 − 23 = 4 ≥ 0 𝑃𝑎𝑟𝑎 𝑥22 : 𝑐22 − 𝑢2 − 𝑣2 = 14 + 5 − 19 = 0 ≥ 0 𝑃𝑎𝑟𝑎 𝑥24 : 𝑐24 − 𝑢2 − 𝑣4 = 19 + 5 − 23 = 1 ≥ 0 𝑃𝑎𝑟𝑎 𝑥25 : 𝑐25 − 𝑢2 − 𝑣5 = 15 + 5 − 22 = −2 ≥ 0 𝑃𝑎𝑟𝑎 𝑥33 : 𝑐33 − 𝑢3 − 𝑣3 = 20 − 0 − 18 = 2 ≥ 0 𝑃𝑎𝑟𝑎 𝑥35 : 𝑐35 − 𝑢3 − 𝑣5 = 𝑀 − 0 − 22 = 𝑀 − 22 ≥ 0

𝑃𝑎𝑟𝑎 𝑥41 : 𝑐41 − 𝑢4 − 𝑣1 = 𝑀 + 22 − 19 = 𝑀 + 3 ≥ 0 𝑃𝑎𝑟𝑎 𝑥42 : 𝑐42 − 𝑢4 − 𝑣2 = 0 + 22 − 19 = 3 ≥ 0 𝑃𝑎𝑟𝑎 𝑥43 : 𝑐43 − 𝑢4 − 𝑣3 = 𝑀 + 22 − 18 = 𝑀 + 4 ≥ 0 𝑃𝑎𝑟𝑎 𝑥44 : 𝑐44 − 𝑢4 − 𝑣4 = 0 + 22 − 23 = −1 ≥ 0

Al obtener valores negativos como lo vemos en las ecuaciones que están resaltadas en rojo, podemos decir que la solución básica actual no es óptima, por consiguiente, obliga a ingresar al procedimiento iterativo. 

Realizar todos los procesos iterativos requeridos para hallar la solución óptima (se debe incluir los que ya están desarrollados en el referente 4, sin omitir cálculo alguno). Se solicita elaborar estos desarrollos en un archivo de Word haciendo uso del editor de ecuaciones en las situaciones que sea necesario

Escogemos a 𝑋25 como variables básica de entrada debido a que es el 𝑐𝑖𝑗 más negativo. En la tabla anterior observamos que tenemos dos posibles recorridos, si se toma el que va de V.E a 𝑋23, un aumento de 30 en 𝑋13 y finalmente una disminución de 30 en 𝑋15, vemos que esto último no es posible debido a que la asignación de 𝑋15 es de 1o y no puede disminuir en 30. En cambio, si se toma la otra posibilidad, 𝑋25 aumenta en 10, 𝑋15 disminuye en 10, 𝑋13

aumenta en 10 y 𝑋23 disminuye en 10, lo cual si tiene sentido. En conclusión la variable básica saliente es 𝑋15 porque fue la que llego a cero en el recorrido. 𝑋13 = 40 + 10 = 50 𝑋23 = 30 − 10 = 20 𝑋45 = 50, 𝑋25 = 10, 𝑋13 = 50, 𝑋23 = 20, 𝑋21 = 30, 𝑋31 = 0, 𝑋32 = 20, 𝑋34 = 30 El nuevo valor de Z será: 𝑍 = 13𝑋13 + 14𝑋21 + 13𝑋23 + 15𝑋25 + 19𝑋31 + 19𝑋32 + 23𝑋34 + 0𝑋45 𝑍 = 13(50) + 14(30) + 13(20) + 15(10) + 19(20) + 23(30) + 0(50) 𝑍 = 650 + 420 + 260 + 150 + 380 + 690 = 2550 Prueba de optimalidad 𝑋45 = 50, 𝑋25 = 10, 𝑋13 = 50, 𝑋23 = 20, 𝑋21 = 30, 𝑋31 = 0, 𝑋32 = 20, 𝑋34 = 30 Los respectivos valores de 𝑐𝑖𝑗 a utilizar son los respectivos costos: 𝑐45 = 0, 𝑐25 = 15, 𝑐13 = 40, 𝑐23 = 13, 𝑐21 = 14, 𝑐31 = 19, 𝑐32 = 19, 𝑐34 = 23 𝑃𝑎𝑟𝑎 𝑥𝑖𝑗 : 𝑐𝑖𝑗 = 𝑢𝑖 + 𝑣𝑗 La tercera fila es la de mayor asignación, por tanto tomamos 𝑢3 = 0, entonces: 𝑃𝑎𝑟𝑎 𝑥31 : 𝑐31 = 19 = 𝑢3 + 𝑣1 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 19 = 0 + 𝑣1 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣1 = 19 𝑃𝑎𝑟𝑎 𝑥32 : 𝑐32 = 19 = 𝑢3 + 𝑣2 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 19 = 0 + 𝑣2 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣2 = 19 𝑃𝑎𝑟𝑎 𝑥34 : 𝑐34 = 23 = 𝑢3 + 𝑣4 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 23 = 0 + 𝑣4 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣4 = 23 𝑃𝑎𝑟𝑎 𝑥21 : 𝑐21 = 14 = 𝑢2 + 𝑣1 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 14 = 𝑢2 + 19, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑢2 = −5 𝑃𝑎𝑟𝑎 𝑥23 : 𝑐23 = 13 = 𝑢2 + 𝑣3 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 13 = −5 + 𝑣4 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣3 = 18 𝑃𝑎𝑟𝑎 𝑥13 : 𝑐13 = 13 = 𝑢1 + 𝑣3 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 13 = 𝑢1 + 18, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑢1 = −5 𝑃𝑎𝑟𝑎 𝑥25 : 𝑐15 = 15 = 𝑢1 + 𝑣5 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 15 = −5 + 𝑣5 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣5 = 20 𝑃𝑎𝑟𝑎 𝑥45 : 𝑐45 = 0 = 𝑢4 + 𝑣5 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 0 = 𝑢4 + 20, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑢4 = −20 Ahora se puede hallar los valores 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗 para las variables no básicas: 𝑃𝑎𝑟𝑎 𝑥11 : 𝑐11 − 𝑢1 − 𝑣1 = 16 + 5 − 19 = 2 ≥ 0 𝑃𝑎𝑟𝑎 𝑥12 : 𝑐12 − 𝑢1 − 𝑣2 = 16 + 5 − 19 = 2 ≥ 0 𝑃𝑎𝑟𝑎 𝑥14 : 𝑐14 − 𝑢1 − 𝑣4 = 22 + 5 − 23 = 4 ≥ 0 𝑃𝑎𝑟𝑎 𝑥22 : 𝑐22 − 𝑢2 − 𝑣2 = 14 + 5 − 19 = 0 ≥ 0

𝑃𝑎𝑟𝑎 𝑥24 : 𝑐24 − 𝑢2 − 𝑣4 = 19 + 5 − 23 = 1 ≥ 0 𝑃𝑎𝑟𝑎 𝑥25 : 𝑐25 − 𝑢2 − 𝑣5 = 15 + 5 − 20 = 0 ≥ 0 𝑃𝑎𝑟𝑎 𝑥33 : 𝑐33 − 𝑢3 − 𝑣3 = 20 − 0 − 18 = 2 ≥ 0 𝑃𝑎𝑟𝑎 𝑥35 : 𝑐35 − 𝑢3 − 𝑣5 = 𝑀 − 0 − 20 = 𝑀 − 20 ≥ 0 𝑃𝑎𝑟𝑎 𝑥41 : 𝑐41 − 𝑢4 − 𝑣1 = 𝑀 + 20 − 19 = 𝑀 + 1 ≥ 0 𝑃𝑎𝑟𝑎 𝑥42 : 𝑐42 − 𝑢4 − 𝑣2 = 0 + 20 − 19 = 1 ≥ 0 𝑃𝑎𝑟𝑎 𝑥43 : 𝑐43 − 𝑢4 − 𝑣3 = 𝑀 + 20 − 18 = 𝑀 + 2 ≥ 0 𝑃𝑎𝑟𝑎 𝑥44 : 𝑐44 − 𝑢4 − 𝑣4 = 0 + 20 − 23 = −3 ≥ 0 Como hay valores negativos de 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗 , la actual solución no es óptima y se requiere realizar una nueva iteración. Segunda iteración

En esta tabla se puede observar que el valor más negativo de los 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗 de variable no básicas es el correspondiente a 𝑋44, por tanto esta es la variable entrante. El ciclo señalado en el tabla indica que ahora la variable básica saliente es 𝑋34 con lo cual, al hacerse cero, el conjunto de nuevas asignaciones, que define la nueva solución básica factible es: 𝑋45 = 50 − 30 = 20 𝑋25 = 10 + 30 = 40 𝑋31 = 0 + 30 = 30 𝑋34 = 30 − 30 = 0 𝑋45 = 20, 𝑋25 = 40, 𝑋13 = 50, 𝑋23 = 20, 𝑋44 = 30, 𝑋31 = 30, 𝑋32 = 20, 𝑋34 = 0

Y el nuevo valor de Z es: 𝑍 = 13𝑋13 + 0𝑋44 + 13𝑋23 + 15𝑋25 + 19𝑋31 + 19𝑋32 + 23𝑋34 + 20𝑋45 𝑍 = 13(50) + 13(20) + 15(40) + 19(30) + 19(20) + 23(0) + 0(20) 𝑍 = 650 + 600 + 260 + 570 + 380 = 2460 Prueba de optimalidad 𝑋45 = 20, 𝑋25 = 40, 𝑋13 = 50, 𝑋23 = 20, 𝑋44 = 30, 𝑋31 = 30, 𝑋32 = 20, 𝑋34 = 0 Los respectivos valores de 𝑐𝑖𝑗 a utilizar son los respectivos costos: 𝑐45 = 0, 𝑐25 = 15, 𝑐13 = 40, 𝑐23 = 13, 𝑐44 = 0, 𝑐31 = 19, 𝑐32 = 19, 𝑐34 = 23 𝑃𝑎𝑟𝑎 𝑥𝑖𝑗 : 𝑐𝑖𝑗 = 𝑢𝑖 + 𝑣𝑗 La tercera fila es la de mayor asignación, por tanto tomamos 𝑢3 = 0, entonces: 𝑃𝑎𝑟𝑎 𝑥31 : 𝑐31 = 19 = 𝑢3 + 𝑣1 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 19 = 0 + 𝑣1 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣1 = 19 𝑃𝑎𝑟𝑎 𝑥32 : 𝑐32 = 19 = 𝑢3 + 𝑣2 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 19 = 0 + 𝑣2 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣2 = 19 𝑃𝑎𝑟𝑎 𝑥34 : 𝑐34 = 23 = 𝑢3 + 𝑣4 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 23 = 0 + 𝑣4 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣4 = 23 𝑃𝑎𝑟𝑎 𝑥44 : 𝑐44 = 0 = 𝑢4 + 𝑣4 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 0 = 𝑢4 + 23, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑢4 = −23 𝑃𝑎𝑟𝑎 𝑥45 : 𝑐45 = 0 = 𝑢4 + 𝑣5 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 0 = −23 + 𝑣5 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣5 = 23 𝑃𝑎𝑟𝑎 𝑥25 : 𝑐25 = 15 = 𝑢2 + 𝑣5 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 15 = 𝑢2 + 23, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑢2 = −8 𝑃𝑎𝑟𝑎 𝑥23 : 𝑐23 = 13 = 𝑢2 + 𝑣3 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 13 = −8 + 𝑣3 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣3 = 21 𝑃𝑎𝑟𝑎 𝑥13 : 𝑐13 = 13 = 𝑢1 + 𝑣3 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 13 = 𝑢1 + 21, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑢1 = −8

Ahora se puede hallar los valores 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗 para las variables no básicas: 𝑃𝑎𝑟𝑎 𝑥11 : 𝑐11 − 𝑢1 − 𝑣1 = 16 + 8 − 19 = 5 ≥ 0 𝑃𝑎𝑟𝑎 𝑥12 : 𝑐12 − 𝑢1 − 𝑣2 = 16 + 8 − 19 = 5 ≥ 0 𝑃𝑎𝑟𝑎 𝑥14 : 𝑐14 − 𝑢1 − 𝑣4 = 22 + 8 − 23 = 7 ≥ 0 𝑃𝑎𝑟𝑎 𝑥15 : 𝑐15 − 𝑢1 − 𝑣5 = 15 + 8 − 23 = 3 ≥ 0 𝑃𝑎𝑟𝑎 𝑥22 : 𝑐22 − 𝑢2 − 𝑣2 = 14 + 8 − 19 = 3 ≥ 0 𝑃𝑎𝑟𝑎 𝑥24 : 𝑐24 − 𝑢2 − 𝑣4 = 19 + 8 − 23 = 4 ≥ 0 𝑃𝑎𝑟𝑎 𝑥33 : 𝑐33 − 𝑢3 − 𝑣3 = 20 − 0 − 21 = −1 ≥ 0 𝑃𝑎𝑟𝑎 𝑥35 : 𝑐35 − 𝑢3 − 𝑣5 = 𝑀 − 0 − 23 = 𝑀 − 23 ≥ 0

𝑃𝑎𝑟𝑎 𝑥41 : 𝑐41 − 𝑢4 − 𝑣1 = 𝑀 + 23 − 19 = 𝑀 + 4 ≥ 0 𝑃𝑎𝑟𝑎 𝑥42 : 𝑐42 − 𝑢4 − 𝑣2 = 0 + 23 − 19 = 4 ≥ 0 𝑃𝑎𝑟𝑎 𝑥43 : 𝑐43 − 𝑢4 − 𝑣3 = 𝑀 + 23 − 21 = 𝑀 + 2 ≥ 0 𝑃𝑎𝑟𝑎 𝑥44 : 𝑐44 − 𝑢4 − 𝑣4 = 0 + 23 − 23 = 0 ≥ 0 Como hay valores negativos de 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗 , la actual solución no es óptima y se requiere realizar una nueva iteración.

Tercera iteración De la última tabla tenemos que 𝑋33 es la variable básica de entrada. La tabla también muestra el ciclo de las modificaciones en las asignaciones de las variables básicas, comenzando con el “aumento” en la variable entrante. Escribimos aumento entre comillas debido a que no es posible un aumento real en 𝑋33 puesto que 𝑋34 no puede disminuir a partir de su actual valor cero, en este casi se considera que el aumento es cero, pero de todas formas 𝑋33 se convierte en variable básica y 𝑋34 en no básica. El nuevo conjunto de variables básicas es ahora: 𝑋44 = 30, 𝑋45 = 20, 𝑋25 = 40, 𝑋13 = 50, 𝑋23 = 20, 𝑋33 = 0, 𝑋31 = 30, 𝑋32 = 20 El valor de Z es: 𝑍 = 13𝑋13 + 13𝑋23 + 15𝑋25 + 19𝑋31 + 19𝑋32 + 20𝑋33 + 0𝑋44 + 20𝑋45 𝑍 = 13(50) + 13(20) + 15(40) + 19(30) + 19(20) + 20(0) + 0(30) + 0(20) 𝑍 = 650 + 600 + 260 + 570 + 380 = 2460 Prueba de optimalidad 𝑋44 = 30, 𝑋45 = 20, 𝑋25 = 40, 𝑋13 = 50, 𝑋23 = 20, 𝑋33 = 0, 𝑋31 = 30, 𝑋32 = 20

Los respectivos valores de 𝑐𝑖𝑗 a utilizar son los respectivos costos: 𝑐44 = 0, 𝑐45 = 0, 𝑐25 = 15, 𝑐13 = 13, 𝑐23 = 13, 𝑐33 = 20, 𝑐31 = 19, 𝑐32 = 19 𝑃𝑎𝑟𝑎 𝑥𝑖𝑗 : 𝑐𝑖𝑗 = 𝑢𝑖 + 𝑣𝑗 La tercera fila es la de mayor asignación, por tanto tomamos 𝑢3 = 0, entonces: 𝑃𝑎𝑟𝑎 𝑥31 : 𝑐31 = 19 = 𝑢3 + 𝑣1 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 19 = 0 + 𝑣1 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣1 = 19 𝑃𝑎𝑟𝑎 𝑥32 : 𝑐32 = 19 = 𝑢3 + 𝑣2 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 19 = 0 + 𝑣2 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣2 = 19 𝑃𝑎𝑟𝑎 𝑥33 : 𝑐33 = 20 = 𝑢3 + 𝑣3 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 20 = 0 + 𝑣3 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣3 = 20 𝑃𝑎𝑟𝑎 𝑥13 : 𝑐13 = 13 = 𝑢1 + 𝑣3 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 13 = 𝑢1 + 20, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑢1 = −7 𝑃𝑎𝑟𝑎 𝑥23 : 𝑐23 = 13 = 𝑢1 + 𝑣3 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 13 = 𝑢2 + 20, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑢2 = −7 𝑃𝑎𝑟𝑎 𝑥25 : 𝑐25 = 15 = 𝑢2 + 𝑣5 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 15 = −7 + 𝑣5 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣5 = 22 𝑃𝑎𝑟𝑎 𝑥45 : 𝑐45 = 0 = 𝑢4 + 𝑣5 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 0 = 𝑢4 + 22, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑢4 = −22 𝑃𝑎𝑟𝑎 𝑥44 : 𝑐44 = 0 = 𝑢4 + 𝑣4 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 0 = −22 + 𝑣4 , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣4 = 22 Ahora se puede hallar los valores 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗 para las variables no básicas: 𝑃𝑎𝑟𝑎 𝑥11 : 𝑐11 − 𝑢1 − 𝑣1 = 16 + 7 − 19 = 4 ≥ 0 𝑃𝑎𝑟𝑎 𝑥12 : 𝑐12 − 𝑢1 − 𝑣2 = 16 + 7 − 19 = 4 ≥ 0 𝑃𝑎𝑟𝑎 𝑥14 : 𝑐14 − 𝑢1 − 𝑣4 = 22 + 7 − 22 = 7 ≥ 0 𝑃𝑎𝑟𝑎 𝑥15 : 𝑐15 − 𝑢1 − 𝑣5 = 15 + 7 − 22 = 0 ≥ 0 𝑃𝑎𝑟𝑎 𝑥22 : 𝑐22 − 𝑢2 − 𝑣2 = 14 + 7 − 19 = 2 ≥ 0 𝑃𝑎𝑟𝑎 𝑥24 : 𝑐24 − 𝑢2 − 𝑣4 = 19 + 7 − 22 = 4 ≥ 0 𝑃𝑎𝑟𝑎 𝑥33 : 𝑐33 − 𝑢3 − 𝑣3 = 20 − 0 − 20 = 0 ≥ 0 𝑃𝑎𝑟𝑎 𝑥35 : 𝑐35 − 𝑢3 − 𝑣5 = 𝑀 − 0 − 22 = 𝑀 − 22 ≥ 0 𝑃𝑎𝑟𝑎 𝑥41 : 𝑐41 − 𝑢4 − 𝑣1 = 𝑀 + 22 − 19 = 𝑀 + 3 ≥ 0 𝑃𝑎𝑟𝑎 𝑥42 : 𝑐42 − 𝑢4 − 𝑣2 = 0 + 22 − 19 = 3 ≥ 0 𝑃𝑎𝑟𝑎 𝑥43 : 𝑐43 − 𝑢4 − 𝑣3 = 𝑀 + 20 − 19 = 𝑀 + 1 ≥ 0 𝑃𝑎𝑟𝑎 𝑥44 : 𝑐44 − 𝑢4 − 𝑣4 = 0 + 22 − 22 = 0 ≥ 0

Con la nueva solución básica, se calcula los valores de 𝑢𝑖 , 𝑣𝑗 𝑦 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗 de las variables no básicas. Aquí se deduce que la actual solución es óptima debido a que todos los valores de 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗 asociados con variables no básicas son no negativos Se tiene entonces que la mejor solución es: Enviar 50 tanques del origen 𝑂1 al destino 𝐷1 , con lo cual se agota la oferta del origen 𝑂1. Enviar desde 𝑂2 20 tanques a 𝐷3 y 40 𝐷5 con lo cual se agota la oferta del origen 𝑂2 . Enviar desde 𝑂3 30 tanques a 𝐷1 y 20 a 𝐷2 con lo cual se agota la oferta del origen 𝑂3 .