MODELO PARA LA SELECCIÓN DE RUTAS DE DISTRIBUCIÓN DE …

TRABAJO PROFESIONAL

“MODELO PARA LA SELECCIÓN DE RUTAS DE DISTRIBUCIÓN

DE LA EMPRESA TORTILLERÍA PIMIENTA, APLICANDO

PROGRAMACIÓN LINEAL”

COMO REQUISITO PARA OBTENER EL TÍTULO DE:

INGENIERO INDUSTRIAL

QUE PRESENTA:

JUAN ANTONIO DE JESÚS OSUNA COUTIÑO

MEDIANTE OPCIÓN I

(TESIS PROFESIONAL)

ASESOR:

DR. ELÍAS NEFTALÍ ESCOBAR GÓMEZ

REVISORES:

MC. JORGE ANTONIO MIJANGOS LÓPEZ

MC. JORGE ANTONIO OROZCO TORRES

TUXTLA GUTIÉRREZ, CHIAPAS MAYO 2013

SUBSECRETARÍA DE EDUCACIÓN SUPERIOR DIRECCIÓN GENERAL DE EDUCACIÓN SUPERIOR TECNOLÓGICA INSTITUTO TECNOLÓGICO DE TUXTLA GUTIÉRREZ

AGRADEZCO

A Dios

Por darme la vida, estar siempre a mi lado e iluminar mis metas.

A mis padres

Por el inmenso apoyo y comprensión en todo momento.

A mis familiares y amigos

Por su compañía que ayudo a moldear positivamente mi forma de ser.

iv

Índice

Introducción ................................................................................................................................. 1

Capítulo 1 Caracterización del proyecto............................................................................... 3

1.1 Antecedentes del problema ............................................................................................. 4

1.2 Identificación del problema .............................................................................................. 4

1.3 Objetivos del proyecto ...................................................................................................... 4

1.3.1 Objetivo general ......................................................................................................... 4

1.3.2 Objetivos específicos ................................................................................................. 5

1.4 Justificación del proyecto ................................................................................................. 5

1.6 Impactos ............................................................................................................................ 6

1.6.1 Impacto económico .................................................................................................... 6

1.6.2 Impacto social ............................................................................................................ 7

1.6.3 Impacto ambiental ...................................................................................................... 7

Capítulo 2 Aspectos generales de la empresa .................................................................... 8

2.1 Descripción de la empresa ............................................................................................... 9

2.2 Reseña histórica ............................................................................................................... 9

2.3 Ubicación ......................................................................................................................... 11

2.4 Razón social .................................................................................................................... 12

2.5 Misión ............................................................................................................................... 12

2.6 Visión ............................................................................................................................... 12

2.7 Valores ............................................................................................................................. 12

2.8 Organización ................................................................................................................... 13

2.9 Productos elaborados ..................................................................................................... 14

2.10 Área de producción ....................................................................................................... 16

Capítulo 3 Marco teórico ........................................................................................................ 17

3.1 Optimización de redes .................................................................................................... 18

3.2 Programación Lineal ....................................................................................................... 18

3.2.1 Formulación de programas lineales ....................................................................... 19

v

3.2.2 Estructura de un problema de programación lineal .............................................. 20

3.2.3 Transformación de un programa lineal a su forma estándar ............................... 22

3.2.4 Método de la M o de penalización ......................................................................... 22

3.3 Prueba estadística .......................................................................................................... 26

3.4 Diagrama de flujo ............................................................................................................ 27

Capítulo 4 Método ................................................................................................................... 30

4.1 Descripción del método a utilizar ................................................................................... 31

Capítulo 5 Aplicación ............................................................................................................. 34

5.1 Delimitación de la zona de aplicación ........................................................................... 35

5.2 Diseño del mapa ............................................................................................................. 35

5.3 Recopilación de datos primarios ................................................................................... 37

5.3.1 Distancia ................................................................................................................... 37

5.3.2 Velocidades .............................................................................................................. 38

5.3.3 Tiempo por tipo de esquina..................................................................................... 39

5.4 Cálculo del tiempo que el camión recorre los lados de las cuadras ......................... 40

5.5 Transformar los valores a una forma estándar ............................................................ 41

5.6 Programación de las rutas, aplicando programación lineal ........................................ 46

5.7 Recopilación de datos secundarios ............................................................................... 91

5.8 Programación de datos secundarios ............................................................................. 92

5.9 Monitoreo y control ......................................................................................................... 93

Capítulo 6 Conclusiones y recomendaciones ................................................................... 94

6.1 Conclusiones ................................................................................................................... 95

6.2 Recomendaciones .......................................................................................................... 97

Bibliografía ................................................................................................................................. 99

Anexos ..................................................................................................................................... 100

Anexo A Tabla de tiempos por lado de la cuadra ............................................................ 100

Anexo B Manual técnico .................................................................................................... 145

Anexo C Glosario de términos .......................................................................................... 163

vi

vii

viii

1

Introducción

El reparto del producto es la actividad final para la mayoría de las empresas de

producción, y una tarea esencial es manejar rutas de distribución óptimas, que

permitan obtener beneficios como: ahorro de gasolina, diminución en los tiempos

de reparto y de los tiempos de espera de los clientes.

Tortillería Pimienta es una empresa que se encuentra localizada en la 5° Oriente

Norte, colonia centro, su venta se realiza directamente en las instalaciones de la

empresa, y a través de unidades de reparto se distribuyen a diversos clientes,

como: taquerías, restaurantes, tiendas, tiendas de auto servicio, empresas

dedicadas a la distribución de comida, etc.; por lo cual es muy importante

mantener una producción constante y un reparto eficiente.

Las rutas de distribución son realizadas de manera empírica por el gerente, para

hacerlas más eficientes se utilizará un programa que desarrolla rutas aplicando

programación lineal, el cual tendrá como objetivo determinar las rutas más cortas

de distribución; este programa podrá ser utilizado por cualquier persona que sepa

manejar una computadora y que reciba un curso de capacitación corto.

El éxito de este proyecto depende principalmente de dos aspectos, el primero es

que los tiempos de reparto obtenidos en el programa sean representativos de los

tiempos reales, ya que mientras más cercanos sean estos mayor confiabilidad

podrá ofrecerse al usuario; y el segundo aspecto es la elaboración de una interfaz

sencilla de manipular.

Para cumplir los objetivos planteados el documento se estructura de la siguiente

manera: En el primer capítulo, caracterización del proyecto, se explican los

problemas identificados durante el desarrollo del proyecto, mediante los

antecedentes del problema y la identificación del problema, además de los

objetivos del proyecto, la justificación del problema, las delimitaciones e impactos.

2

En el capítulo 2, aspectos generales de la empresa, se presenta información

general de la empresa, como la descripción de la empresa, reseña histórica,

ubicación, razón social, misión, visión, valores, organización, productos

elaborados y área de producción.

En el tercer capítulo, marco teórico, se expone el fundamento teórico utilizado en

el desarrollo del proyecto, considerando la optimización de redes, terminología,

programación lineal y pruebas estadísticas.

El capítulo 4, método, describe los pasos utilizados para la elaboración del

proyecto; presentando a través de un diagrama la metodología a utilizar, así como

el resumen de cada uno de los pasos.

En el capítulo 5, aplicación, se explica detalladamente e implementa la

metodología propuesta, conformada por delimitación de la zona de aplicación,

diseño del mapa, recopilación de datos primarios, cálculo del tiempo que el camión

recorre los lados de las cuadras, trasformar los valores a una forma estándar,

programación de las rutas aplicando programación lineal, recopilación de datos

secundarios, programación de datos secundarios, y monitoreo y control.

En el sexto capítulo, se presentan las conclusiones observadas en el desarrollo

del proyecto y las recomendaciones pertinentes para la mejora del proyecto.

Capítulo 1

Caracterización del proyecto

4

1.1 Antecedentes del problema

Tortillería Pimienta, empresa con alta experiencia en su ramo, cuenta con un nivel

alto de producción de tortilla, de éste el 85% son pedidos a repartir, por lo que el

menor tiempo en el reparto de su producto es crucial para mantener a sus clientes,

conseguir nuevos clientes e incrementar sus ganancias.

La determinación de rutas de reparto es realizada de manera empírica por el

dueño, invirtiendo un tiempo considerable en su elaboración. Las veces que ha

sido necesario establecer una ruta de distribución cuando no se encuentra el

dueño los tiempos de reparto incrementan, generando molestia en los clientes y

disminuyendo la productividad del reparto.

1.2 Identificación del problema

El principal problema de la empresa es la baja eficiencia en el reparto de su

producto, debido principalmente a que las rutas se establecen empíricamente y a

que el gerente es el único que tiene la experiencia para definirlas.

1.3 Objetivos del proyecto

1.3.1 Objetivo general

Desarrollar un sistema de distribución que permita optimizar las rutas de reparto

del producto que distribuye la empresa Tortillería Pimienta, utilizando

programación lineal.

5

1.3.2 Objetivos específicos

Determinar los tiempos de reparto, obteniendo rutas de distribución

confiables.

Crear rutas que aumenten la productividad del reparto.

Desarrollar un modelo de programación lineal aplicado a las rutas de

reparto.

Realizar un programa dinámico que permita la fácil interacción del operario

con la computadora.

1.4 Justificación del proyecto

En este trabajo se pretende aplicar programación lineal, mediante un sistema

preestablecido a computadora para la creación de rutas de reparto de la empresa

Tortillería Pimienta; de esta manera se obtendrá:

Mayor confiabilidad en las rutas de reparto elaboradas, utilizando un

método científico.

Mayor confiabilidad en los cálculos de los tiempos de las rutas de reparto,

ya que los resultados arrojados por el sistema son sumas de tiempos

promedios evaluados por pruebas estadísticas.

Disminución del tiempo dedicado en la elaboración de las rutas de reparto,

realizando las interacciones de datos a computadora.

Facilidad en la creación de nuevas rutas de reparto, mediante una interfaz

dinámica.

Un programa que se pueda actualizar fácilmente, con una base de datos

esquematizada.

Disminución en los tiempos de reparto, ya que la metodología a utilizar es la

de la ruta más corta.

6

Disminución en los gastos de gasolina, mediante rutas con menor tiempo

de reparto.

Aumento en la productividad de los repartos, obteniendo rutas con la mayor

cantidad de repartos posibles.

1.5 Delimitaciones

Este proyecto se propone a la empresa “Tortillería Pimienta” en el área de reparto,

que se encuentra en la ciudad de Tuxtla Gutiérrez Chiapas; el proyecto se lleva a

cabo en el periodo de Agosto 2012 a Mayo 2013.

Entre las principales limitaciones se observaron las siguientes:

La empresa no proporcionó recursos para obtener las muestras de los

tiempos por lado de la cuadra.

La empresa no proporcionó una unidad (carro de reparto), para obtener las

muestras de los tiempos por lado de la cuadra.

1.6 Impactos

1.6.1 Impacto económico

Se reducirán los gastos de gasolina ya que el programa arroja la ruta más corta en

relación al tiempo, la cual tiende hacer una ruta con una distancia corta, siendo

rutas con una alta probabilidad de tener poca variación de velocidad,

manteniéndose menos tiempo prendido el carro, esto conlleva a un rendimiento de

gasolina, la cual se refleja en un consumo menor de esta; y un desgaste menor en

7

las piezas de los vehículos de reparto, al recorrer rutas más rápidas y con una

tendencia a más cortas.

1.6.2 Impacto social

Se verán beneficiados los clientes a los que se les reparte el producto al recibir

sus pedidos en un menor tiempo, esto mediante la confiabilidad de las rutas

arrojadas por el sistema, las cuales serán lo más cercanas a las rutas reales.

1.6.3 Impacto ambiental

Habrá menos contaminación por parte de los camiones repartidores al recorrer

rutas más rápidas, con menor variación de velocidad, dando como resultado un

consumo más bajo en la gasolina; liberando menor cantidad de dióxido de

carbono, dañando menos al medio ambiente.

Capítulo 2

Aspectos generales de la

empresa

9

2.1 Descripción de la empresa

Tortillería pimienta es una empresa completamente Chiapaneca que comenzó sus

actividades el 20 de febrero de 1970, nace de la identificación del gran mercado

potencial que existe en la zona, puesto que no existe una empresa cercana que

cuente con la capacidad de producción de tortilla para satisfacer la demanda

interna y externa.

Desde su comienzo la empresa tuvo una gran aceptación puesto que su ubicación

le ofrece un gran mercado el cual ha sabido atraer y mantener mediante calidad y

sabor en su producto; a partir de 1990 comenzó a hacer entrega de tortilla a

establecimientos.

Para satisfacer su demanda la empresa dispone de dos líneas de producción,

también ha invertido en vehículos repartidores, contando con 2 motos y 3 carros.

Por lo antes mencionado Tortillería Pimienta es una empresa que busca

implementar prácticas que le ayuden a la mejora continua y encontrar nuevas

maneras de aumentar sus ventas.

2.2 Reseña histórica

Tortillería Pimienta, empresa 100% Mexicana, inicia sus operaciones el 20 de

febrero de 1970, cuando Don Daniel Gómez Chacón y Doña Sara Aguilar

Mandujano deciden invertir el dinero de la venta de un camión de carga en una

tortillería; la producción de tortilla se realizaba con una tortilladora celorio modelo

MA con motor a gasolina, un taque de 20 litros de gas y un molino a mano; su

materia prima (maíz) era comprada en rancherías, el agua se extraía de pozos,

todo transportado en carretas; su producción era de 140 Kilos diarios.

10

Después de cinco años de trabajo la producción de tortilla aumento a 600 Kilos

diarios, por lo que sus propietarios decidieron adquirir un molino eléctrico de 5

caballos de fuerza y una lavadora de maíz; a 1978 su producción se duplico por lo

que se adquirió otra tortilladora celorio modelo BC de gas y luz trifásica, un tanque

estacionario de gas 1,000 litros y un cocedor con capacidad de 140 Kilos.

En 1979 CONASUPO le otorgo una concesión de maíz de 4 toneladas, se realizó

una remodelación del local instalado agua potable, se adquirió un molino eléctrico

de 10 caballos de fuerza, y se vendió la tortilladora celorio modelo M A supliéndola

por una tortilladora celorio modelo BC.

Para 1990 el promedio de producción de tortilla diaria era de 1450 kilos, por lo que

se vendió la tortilladora celorio modelo BC más antigua y se adquirió una

tortilladora celorio modelo dúplex; se empezó a trabajar 7 días de la semana y se

inició el reparto a empresas públicas y privadas; en ese año la empresa fue

heredada a Don Josué Alfredo Gómez Aguilar actual dueño de la empresa.

1994 fue un año de muchos cambios para la empresa, se compró una amasadora,

se empezó a producir tortillas 100% de harina, se añadió el reparto a expendios

de colonias (tienditas) y se cambió la tortilladora celorio modelo BC por otra

tortilladora del mismo modelo; un año después se compró la primera motocicleta y

se realizó una remodelación al local; en 1999 se instalaron filtros de agua.

La creación de nuevas tortillerías en el 2004 creo un incremento en la oferta de

tortilla en el mércalo, lo que disminuyó las venta en mostrador de tortillería

Pimienta, por lo que la empresa se vio obligada a vender la tortilladora celorio

modelo dúplex; para 2005 se comenzó el reparto a la cadena de minisúper OXXO,

y la producción general era de 800 kilos diarios.

En el 2008 la demanda de tortilla en mostrador siguió decreciendo

progresivamente pero el reparto incremento a un 40%, las ventas disminuyeron a

11

500 kilos diarios (generales), aun así se tomó la decisión de adquirir una maquina

tortilladora tortimaq, y se mejoró la presentación del producto con un papel para

envolver tortilla con el logo y datos de la empresa.

Hoy en día en el año 2013 la empresa ha aumentado su producción a 1050 kilos

diarios, obteniendo el 85% de sus ganancias de la venta a reparto, teniendo como

consumidores vía pedidos a minisúper, hoteles, empresas de comida y expendios

en colonias (tienditas); siendo solo un 15% su venta a mostrador.

2.3 Ubicación

Tortillería pimienta se encuentra ubicada en la dirección 5° Oriente Norte, colonia

centro número 730, como se puede ver en la figura 2.1, en esta figura se aprecia a

la empresa con un rectángulo color azul, que se encuentra en la calle 5° Oriente

rectángulo color Rojo y 9°Norte rectángulo color verde.

Figura 2.1 Ubicación de la empresa

(Fuente: elaboración propia)

12

2.4 Razón social

Nombre de la empresa: Tortillería pimienta. Razón social: JOSUE ALFREDO

GOMEZ AGUILAR. Actividad, elaboración de tortilla de maíz.

2.5 Misión

Ofrecer al consumidor de tortilla un producto con la mayor higiene, calidad y

precio justo posible.

2.6 Visión

Ser líder en el municipio de Tuxtla Gutiérrez en la producción de tortilla.

2.7 Valores

Tortillería Pimienta, es una empresa que se esfuerza día con día, para ofrecer un

mejor servicio de calidad y confianza a sus clientes, mediante los valores que a

continuación se presentan:

1.- CALIDAD: En todos los ámbitos de cada una de las actividades que se realizan

en la empresa.

2.- JUSTICIA: Hacia nuestro personal, clientes y proveedores.

3.- INNOVACIÓN: Continua de nuestras estrategias y de nuestros métodos

de trabajo.

http://www.grupoiesc.com/[email protected]/Paginas/Valores%20de%20la%20empresa.html

13

4.- PUNTUALIDAD: En la entrega del producto solicitado por nuestros clientes.

5.- COHERENCIA: Entre lo que nos comprometemos con nuestro cliente y lo que

efectuamos como trabajo.

6.- COMUNICACIÓN: Constante y efectiva, entre todos los miembros que

formamos parte de la empresa, así como con nuestros proveedores y clientes.

7.- CONFIANZA: En que realizaremos nuestras labores de la mejor manera, con la

finalidad de satisfacer a nuestros clientes.

8.- COMPROMISO: Con nuestro clientes, al brindarles un servicio de calidad; con

la sociedad, al brindar estabilidad a las familias de nuestro personal; y con el

medio ambiente, al respetar y cumplir todas las normas establecidas para el

cuidado de éste.

2.8 Organización

La empresa es dirigida por su propietario el Señor Josué Alfredo Gómez Aguilar,

quien hace la labor de gerente, teniendo como responsabilidades la selección de

proveedores, supervisión, creación de rutas de reparto, entre otras; su subgerente

Maribel Gordillo Hernández quien es la encargada de supervisar a los empleados

y tomar las decisiones del gerente cuando este no se encuentra.

También cuenta con un jefe de operaciones Miguel Pérez Pérez, tres

maquinistas para el área de producción, un despachador y tres repartidores; la

empresa tiene un contador externo a ella, el C. P. Fidel Zabala Aguilar. La

estructura de esta organización se puede ver en la figura 2.2.

http://www.grupoiesc.com/[email protected]/Paginas/Valores%20de%20la%20empresa.html

14

Figura 2.2 Organigrama de Tortillería Pimienta.


2.9 Productos elaborados

La empresa Tortillería Pimienta se dedica a la fabricación de tortilla en medida

estándar, y ovaladas (Taqueras); también cuenta con la elaboración de tostada

fritas en presentación totopo y redonda, estas son elaboradas de las tortillas que

se devuelven.

Figura 2.3 Tortilla estándar


15

Figura 2.4 Tortilla ovalada


Figura 2.5 Tostadas presentación totopo


Figura 2.6 Tostadas presentación redonda


16

2.10 Área de producción

Tortillería Pimienta cuenta con dos máquinas para hacer tortilla, dos áreas de

almacén de harina, tarja, revolvedora, mesa de trabajo, almacén de herramientas,

baños, una zona de despacho y dos accesos; como se muestra en la figura 2.3.

Figura 2.7 Áreas de la empresa.


Capítulo 3

Marco teórico

18

3.1 Optimización de redes

Taha (2003), menciona que hay una multitud de situaciones en investigación de

operaciones, que se puede modelar y resolver como redes (nodos conectados por

ramas). Algunas encuestas recientes informan que hasta el 70% de los problemas

de programación matemática en el mundo real se puede resolver como modelos

relacionados con redes; la solución de estas situaciones se logra mediante la

optimización de redes

Las técnicas de flujo de redes están orientadas a optimizar situaciones vinculadas

a la red de transporte, redes de comunicación, sistemas de vuelos de los

aeropuertos, rutas de navegación de los cruceros, estaciones de bomberos que

transportan fluidos a través de tuberías, rutas entre ciudades, redes de conductos

y todas aquellas situaciones que pueden representarse mediante una red, donde

los nodos representen las estaciones o ciudades.

Cuando se trata de encontrar el camino más corto entre un origen y un destino, la

técnica, algoritmo o el modelo adecuado es el de la ruta más corta; aunque existen

otros modelos de redes como el árbol de expansión mínima, flujo máximo y flujo

de costo mínimo cada uno abarca un problema en particular.

3.2 Programación Lineal

Según Arreola (2003), la programación lineal es una técnica que se utiliza para la

solución de diferentes tipos de problemas, tanto teóricos como prácticos, en

diversas áreas del conocimiento; el éxito en su aplicación a problemas reales,

sofisticados y complejos es avalado por una gran cantidad de instituciones

productos de bienes y servicios en muchos países del mundo.

19

La programación lineal cosiste básicamente en la construcción, solución y análisis

del modelo lineal de un problema dado. Entendiéndose por modelo lineal aquél

que está integrado única y exclusivamente por funciones lineales.

3.2.1 Formulación de programas lineales

Eppen (2000) menciona que los modelos de optimización restringida son

importantes porque captan la esencia de muchas situaciones de administración

decisivas; como en un modelo de optimización restringida toma la forma de una

medida de desempeño que se optimizara a través de una gama de valores

factibles de las variables de decisión, dichos valores se determinan mediante un

conjunto de restricciones de desigualdad.

Es decir, se debe escoger los valores de las variables de decisión de tal manera

que se satisfaga la restricciones de desigualdad, mientras se consigue que la

medida de desempeño sea tan grande (modelo de maximización) o tan pequeña

(modelo de minimización), como sea posible.

Para formular un problema de programación lineal hay que tomar en cuenta los

siguientes puntos:

Objetivo: Maximizar o minimizar el problema.

Que se puede maximizar en un problema: utilidades, producción, valor

presente, medios publicitarios, rutas de reparto, etc.

Que se pude minimizar en un problema: costos, desperdicios, tiempo, etc.

Restricciones: estas se pueden representar mediante dinero, materia prima

(mano de obra, máquina y equipo), tiempo, espacio, insumos, trasporte, etc.

20

Requerimiento: especificaciones, contenido, demanda, contrato con clientes, etc.

3.2.2 Estructura de un problema de programación lineal

Para estructurar un problema de programación lineal hay que tomar en cuenta los

siguientes términos; su representación física se expresa en la ecuación 1:

Función objetivo (que es lo que se quiere lograr): La función objetivo es una

relación matemática entre las variables de decisión, parámetros y una magnitud

que representa el objetivo o producto del sistema. Por ejemplo si el objetivo del

sistema es minimizar los costos de operación, la función objetivo deba de expresar

la relación entre el costo y las variables de decisión. La solución óptima se obtiene

cuando el valor del costo sea mínimo para un conjunto de valores factibles de las

variables.

Es decir hay que determinar las variables X1, X2,…, Xn que optimicen el valor de

Z=f (X1, X2,.., Xn) sujeto a restricciones de la forma g(X1, X2,…, Xn) ≤ b. Donde X1,

X2,…, Xn son las variables de decisión, Z es la función objetivo y f es una función

matemática.

Variables de decisión y parámetro (que es lo que va a decidir): las variables

de decisión son incógnitas que deben ser determinadas a partir de la solución del

modelo. Los parámetros representan los valores conocidos del sistema o bien que

se pueden controlar.

Restricciones (que es lo que nos limita lograr el objetivo principal): las

restricciones son relaciones entre las variables de decisión y magnitudes que dan

sentido a la solución del problema y las acotan a valores factibles. Por ejemplo si

21

una de las variables de decisión representa el número de empleados de un taller,

es evidente que el valor de estas variables no puede ser negativo.

El la ecuación 1 se muestra la estructura del modelo de programación lineal.

La forma simplificada de la estructura del modelo se puede expresar de la

siguiente manera en la ecuación 2

Dónde:

Representan las variables de decisión a determinar el problema: X1, X2,…,

Xn.

Representa la contribución a la función objetivo por cada unidad de X1,

X2,…, Xn: C1, C2,…, Cn.

Los coeficientes tecnológicos (uso de recursos i por cada unidad de

variables Xj): aij.

Son los recursos o requerimientos del problema: b1, b2,…, bm.

22

3.2.3 Transformación de un programa lineal a su forma estándar

Todo programa lineal, independientemente de la forma en la que esté dado, puede

plantease en la forma estándar.

Las características de la forma estándar son:

Todas las restricciones son ecuaciones, excepto las restricciones de no

negatividad que permanecen como desigualdades (≥0)

Los elementos del lado derecho de cada ecuación son no negativos

Todas las variables son no negativas

La función objetivo es del tipo maximización o minimización

Las restricciones de desigualdad pueden cambiarse a ecuaciones introduciendo

(sumando o restando) en el lado izquierdo de cada una de las restricciones una

variable no negativa.

Si la restricción de forma (≤) la variable que se introduce se llama variable de

holgura y se suma a la restricción.

Si la restricción de forma (≥) la variable que se introduce se llama variable de

exceso y se resta a la restricción.

3.2.4 Método de la M o de penalización

Arreola (2003) expresa que el método de la M se considera un método de

penalización por que obliga a la Variables artificiales salgan de la base, lo cual

provoca un castigo al valor de la función objetivo si estas toman un valor positivo;

donde M, es un número positivo muy grande, de ahí el nombre del modelo.

23

Este método es equivalente al método de dos fases, la diferencia es que se usa un

coeficiente en la función objetivo de M. En los problemas de maximización a las

variables artificiales se les debe asignar coeficientes en la función objetivo de –M y

los problemas de minimización se les debe asignar coeficientes de +M, en donde

se supone que M es un numeró muy grande, por eso se le dice de penalización.

En la figura 3.1 se puede ver un problema planteado en su forma estándar.

Figura 3.1 Ejemplo forma estándar.


En la figura 3.2 se escribe el problema en forma estándar, donde se agrega

variables artificiales y se acomodan dependiendo si son variables básicas, de

holgura o de exceso; formando la matriz identidad con las variables básicas

iniciales.

Figura 3.2 Ejemplo matriz identidad. (Fuente: elaboración propia)

24

En la Tablas 3.1 se agregan la restricción Maximizar Z-4X1,-6X2-1/2X3+MA1=0,

construyendo la tabla siguiente.

Tabla 3.1 Ejemplo matriz inicial


X1 X2 X3 S1 A1 S2 S3 Solución

Z -4 -6 -1/2 0 M 0 0 0

A1 4 -2 3 -1 1 0 0 40

S2 2 4 1 0 0 1 0 60

S3 3 1 2 0 0 0 1 30

En la tabla 3.2 se restablece el vector unitario de A1 mediante eliminación de

Gauss. En la primera iteración entra la variable X1 que corresponde a la más

negativa, porque M es un número muy grande, en este caso 100 y sale la de

menor cociente que es A1, desempatando arbitrariamente.

Tabla 3.2 Ejemplo matriz interacción 1



Z -4M-4=-404 2M-6=194 -3M-1/2=-300.5 0 M 0 0 -40M=-4000

A1 4 -2 3 -1 1 0 0 40

S2 2 4 1 0 0 1 0 60

S3 3 1 2 0 0 0 1 30

En la tabla 3.3 se realiza en la segunda iteración, donde entra la variable X2 que

corresponde a la más negativa, porque M es un número muy grande y sale la de

menor cociente que es S3.

25




Z 0 8 5/2 -1 M+1 0 0 40

X1 1 -1/2 ¾ -1/4 1/4 0 0 10

S2 0 5 -1/2 ½ -½ 1 0 40

S3 0 5/2 -17/4 ¾ -¾ 0 1 0

La tercera iteración se realiza en la tabla 3.4, donde entra la variable X3 que es la

única negativa, y sale la única que puede salir que es S2.




Z 0 0 -111/10 7/5 M-7/5 0 16/5 40

X1 1 0 -1/10 -1/10 1/10 0 1/5 10

S2 0 0 8 -1 1 1 -2 40

X2 0 1 -17/10 3/10 -3/10 0 2/5 0

Después de haber realizado la tercera iteración se obtiene la solución óptima del

problema. Esta solución también se puede representar como: Z= 19/2, X1=21/12,

X2=17/2, X3=5, como se observa en la tabla 3.5.

Tabla 3.5 Ejemplo matriz solución óptima



Z 0 0 0 1/80 M-1/80 111/80 17/40 191/2

X1 1 0 0 -9/80 9/80 1/80 7/40 21/2

X3 0 0 1 -1/8 1/8 1/8 -1/4 5

X2 0 1 0 7/80 -7/80 17/80 -1/40 17/2

26

3.3 Prueba estadística

Según Wackerly (2010), los objetivos de la estadística es hacer inferencias acerca

de parámetros poblacionales desconocidos con base en información contenida en

datos muéstrales.

En muchos aspectos, el procedimiento formal para pruebas de hipótesis es

semejante al método científico. Éste observa la naturaleza, formula una teoría y la

confronta con lo observado. En nuestro contexto, el científico plantea una hipótesis

respecto a uno o más parámetros poblacionales: de que son iguales a valores

especificados. En seguida toma una muestra de la población y compara sus

observaciones con la hipótesis.

Si las observaciones no concuerdan con la hipótesis, las rechaza. De lo contrario,

que la hipótesis es verdadera o que la muestra no detecto la diferencia entre los

valores real e hipotético de los parámetros poblacionales.

Muchas veces, el objetivo de una prueba estadística es probar una hipótesis

concerniente a los valores de uno o más parámetros poblacionales. Por lo general

tenemos una teoría, es decir una hipótesis de investigación, acerca del o los

parámetros que deseamos apoyar.

Por ejemplo, suponga que un candidato, Jones dice que él ganará más de 50% de

los votos en una elección urbana y por tanto saldrá como ganador. Si no creemos

en lo dicho por Jones, podríamos buscar apoyar la hipótesis de investigación de

que Jone no ésta siendo favorecido por más de 50% del electorado. El apoyo para

esta hipótesis de investigación, también llamada hipótesis alternativa, se obtiene

mostrando que lo contrario de la hipótesis alternativa, llamada Hipótesis nula, es

falso.

27

Entonces, una teoría se comprueba demostrando que no hay evidencia que

sustente la teoría opuesta: en cierto sentido una prueba por contradicción. Como

buscamos apoyo para la hipótesis alternativa de que lo dicho por Jones es falso,

nuestra hipótesis alternativa es que “p”, la probabilidad de seleccionar un votante

que esté a favor de jones, es menor que 0.5.

Si se comprueba que los datos que apoyan el rechazo de la hipótesis nula p=0.5,

a favor de la hipótesis alternativa p<0.5, hemos alcanzado nuestro objetivo de

investigación. Aun cuando es común hablar de probar una hipótesis nula, el

objetivo de investigación puede ser demostrar apoyo para la hipótesis alternativa,

si dicho apoyo se justifica.

3.4 Diagrama de flujo

Según Corona (2011), los diagramas de flujo son representaciones que nos

demuestran gráficamente un algoritmo, el cual se compone de diferentes figuras

que representan determinados procesos, los cuales se ordenan y conectan con

líneas que indican el orden de ejecución; estas formas pueden variar dependiendo

el programador, por lo cual en este trabajo se utilizara los reglamentados por el

Instituto Nacional de Normalización Estadounidense (ANSI, American National

Standards Institute), y se pueden observar en la tabla 3.6.

Tabla 3.6 Figuras diagrama

(Fuente: recopilación propia)

Figura Explicación

Inicio y fin del diagrama de flujo

Símbolo de proceso, indica la asignación de un valor en

la memoria y/o la ejecución de una operación aritmética

28

Impresión

Líneas de flujo o dirección, indican la secuencia en que se

realizan las operaciones

Símbolo de decisión, indica la realización de una

comparación de valores

Comando que cicla condiciones

Conectores

Entrada de datos

Las características que debe tener todo diagrama de flujo son las expresadas a

continuación:

Debe tener un inicio y un final

No se declaran variables

Las líneas de flujo se deben acomodarse en posición horizontal o vertical

Se bebe evitar el cruce de líneas utilizando los conectores

Los conectores solo se utilizan cuando se necesitan

No deben quedar líneas de flujo libres

La construcción de los símbolos debe facilitar su lectura de arriba hacia

abajo, y de izquierda a derecha

La escritura debe ser con la menor cantidad de términos de programación o

leguaje de maquina

29

Los comentarios deben de ser al margen o mediante el símbolo grafico

comentario

Los diagramas con tamaño superior a una hoja, son recomendables

enumerarlos e identificarlos

Los símbolos de decisión son las únicas figuras con más de una línea de

flujo de salida

Un diagrama de flujo se recomienda realizarlo antes de crear el código del

programa; la cual es una de las dos técnicas más utilizadas para la etapa de

diseño junto con el pseudocódigo para poder representar un algoritmo.

Capítulo 4

Método

31

4.1 Descripción del método a utilizar

A continuación se muestra la figura 4.1, se puede ver una descripción breve de los

pasos a realizar para la elaboración del sistema y su secuencia.

Figura 4.1 Diagrama del método a utiliza 1

Figura 4.1 Diagrama del método a utilizar


Delimitación de la zona de

aplicación

Diseño del

mapa

Recopilación de datos primarios

Distancia

Velocidades

Tiempo por tipo de esquina

Cálculo del tiempo que el

camión recorre los lados de las

cuadras

Transformar los valores a

una forma estandar

Programación de las rutas, aplicando

programación lineal

Recopilación de datos

secundarios

Programación de datos

secundarios

Monitoreo y control

32

Delimitación de la zona de aplicación: Al desarrollar un proyecto nuevo es

conveniente realizarlo en una parte del sistema de manera que se valide para su

futura aplicación a todo el sistema. La empresa divide en 6 zonas la ciudad, en

este proyecto se analizará la zona más cercana a la empresa; se decidió delimitar

la zona de aplicación a un área que permitiera realizar el proyecto en el periodo

que abarca la delimitación temporal.

Diseño del mapa: Se realiza un mapa de la delimitación de la zona de aplicación,

este mapa podrá intercambiar información con la programación, de esta manera

se realiza una interfaz dinámica y fácil de manejar para el usuario.

Recopilación de datos primarios: Con los datos primarios se determina el

tiempo aproximado que un camión repartidor se tarda en recorrer la distancia que

debe transitar para llegar a su destino. Los datos primarios a recolectar son la

distancia, la velocidad y el tiempo por tipo de esquina; la descripción de estos

datos se presenta a continuación.

Distancia: Estos datos están conformados por los Kilómetros de cada una

de las cuadras.

Velocidades: Estos datos representan las diferentes velocidades (Km/h)

por zona del camión.

Tiempo por tipo de esquina: Es el tiempo que tarda el carro repartidor en

pasar la intersección de un lado de una cuadra al lado de la cuadra

siguiente, determinándose un tiempo en segundos por tipo de esquina,

como son semáforo, 1x1 ó preferencia.

Cálculo del tiempo que el camión recorre los lados de las cuadras: Con la

ecuación 3, presentada en la sección 5.4, se pude obtener el tiempo en el que el

camión repartidor recorre un lado de la cuadra; en esta ecuación se divide la

33

distancia del lado de la cuadra entre la velocidad promedio del camión repartidor,

al resultado de este cálculo se le suma el tiempo por tipo de esquina.

Transformar los valores a una forma estándar: después de calcular los

tiempos, estos valores se tienen que transformar a una forma estándar de

programación lineal, el cual es el primer paso para poder resolver un problema de

programación lineal

Programación de las rutas aplicando programación lineal: Para no realizar a

mano las interacciones de un problema de programación lineal con 268 nodos, se

programan estos cálculos para que la computadora los realice.

Recopilación de datos secundarios: Los datos secundarios están compuestos

por el tiempo para estacionarse del camión de reparto y el tiempo de entrega del

pedido.

Programación de datos secundarios: En el mapa a computadora se pueden ver

cuadros externos a las cuadras y los nodos, éstas representan las tiendas; las

cuales tienen los valores del tiempo para estacionarse del camión de reparto y el

tiempo de entrega del pedido.

Monitoreo y control: Se monitoreará cada 3 meses el sistema desarrollado,

modificando los tiempos de la tabla, que tengan altas variaciones con los tiempos

reales, para que los tiempos arrojados por el sistema sean más confiables.

Capítulo 5

Aplicación

35

5.1 Delimitación de la zona de aplicación

En la figura 5.1 se muestra la zona a la que se le aplicará programación lineal, en

esta se encuentra la ruta de reparto más cercana a tortillería Pimienta, conocida

como ruta 3 ó ruta centro, esta figura está conformada por toda la parte interior de

la 9 Norte, 4 Sur, 5 Poniente y 15 Oriente del municipio de Tuxtla Gutiérrez

Chiapas; representando 1/52 parte del municipio de Tuxtla Gutiérrez.

Figura 5.1 Zona de aplicación


5.2 Diseño del mapa

El mapa que se normalizó se obtuvo de google maps1, figura 5.1, los beneficios de

la normalización del mapa es facilitar la asignación de un valor aproximado en

Kilómetros por lado de la cuadra; también se le asignó un nodo por cada esquina

de la cuadra, la dirección y el sentido de los carros.

1 Google maps es un servidor de aplicaciones de mapas en la Web. Ofrece imágenes de mapas desplazables, así como fotos satelitales del mundo e incluso la ruta entre diferentes ubicaciones o imágenes a pie de calle Google Street View.

http://maps.google.com/

http://es.wikipedia.org/wiki/Fotograf%C3%ADa

http://es.wikipedia.org/wiki/Sat%C3%A9lite_artificial

http://es.wikipedia.org/wiki/Tierra

http://es.wikipedia.org/wiki/Google_Street_View

36

La figura 5.2, es un fragmento del mapa, en él se le da un valor de 0.05 Km por

cuadrícula que ocupe la cuadra, se puede ver que el cuadro color rojo es una

cuadra la cual está conformada por cuatro cuadros ó 0.1Km por lado; los cuadros

color verde son los nodos de la cuadra y las flechas color amarillo es la dirección

de los carros.

Figura 5.2 Mapa valores


Se establecen los nodos para saber la relación de las cuadras, para esto se debe

saber que nodos están conectados, esta información se obtiene conociendo el

sentido de los carros; en la figura 5.2, se puede ver que el nodo 5 cuadro verde

inferior derecho está conectado con el nodo 6 y a su vez con el nodo 24; esta

información se recopiló para todos los nodos.

La figura 5.3, está compuesto por 217 cuadras y 268 nodos; cuenta con el sentido

de los carros y las direcciones de las calles y avenidas; el diseño a computadora

se elaboró en el mismo programa que se realizó la programación de los cálculos

de las rutas por programación lineal; de esta manera la programación de la tabla

de tiempos y la figura 5.3, pueden intercambiar información entre sí.

37

Figura 5.3 Mapa


5.3 Recopilación de datos primarios

Estos datos están conformados por la distancia (Km) de cada una de las cuadras,

las diferentes velocidades (Km/h) por zona, los tipos de esquinas (semáforos, 1x1

ó preferencia) por zona y el tiempo obtenido en segundos de las cuadras.

5.3.1 Distancia

La asignación de la distancia (Km) por lado de la cuadra se asigna mediante la

cantidad de cuadrículas que ocupe una cuadra; por ejemplo, en la figura 5.5, la

cuadra con cuadros rojos tiene una medida de 0.05Km x 0.15Km, la cuadra color

38

verde tiene una medida de 0.05 Km x 0.05 Km y la cuadra color amarillo tiene una

medida de 0.1 Km x 0.1 Km.

Figura 5.4 Mapa de Km


5.3.2 Velocidades

Para poder obtener el valor de las velocidades de los lados de las cuadras, de la

figura 5.1, se realizó una inspección manejando un carro en el horario de reparto

que abarca de 7 de la mañana a 4 de la tarde, por lo que se le dio un valor

aproximado dividiéndolo en zonas.

Se dividió el mapa en 3 zonas como se puede apreciar en la figura 5.6, la zona

centro que está coloreada con el color rojo está conformada por toda el bloque

interior que abarca la 3 Norte, 4 Sur, 2 Poniente y 5 Oriente; la zona intermedia

color verde está formada por toda la bloque interior que abarca la 9 Norte, 9 Sur, 9

Poniente y 9 Oriente, sin tomar en cuenta la Zona centro; y la zona superior color

azul es todo el mapa restante a las dos zonas antes mencionadas.

39

Figura 5.5 Velocidad por zona


Las diferentes velocidades por zona se pueden apreciar en la tabla 5.1.

Tabla 5.1 Velocidad por zona


Tipo de zona Velocidad

Zona Centro 15Km/h

Zona intermedia 35Km/h

Zona superior 45Km/h

Tabla 5.1 Velocidad por zona 1

5.3.3 Tiempo por tipo de esquina

Tomando en cuenta que por lado del semáforo que se espera son 40 segundos, y

que se le agrega al total de la espera del semáforo 10 segundos de arranque, los

valores de los tiempos de los semáforos son los mostrados en la tabla 5.2,

40

también en esta tabla se puede ver los valores de los 1x1 y los valores de las

preferencias de las calles que no tienen semáforo ó 1x1.

Tabla 5.2 Valor de las esquinas


Tipo de esquina Tiempo en segundos

Semáforo tipo 4 130 Segundos



1x1 centro 20 Segundos

1x1 7.5 Segundos

No tiene semáforo centro calle 30 Segundos

No tiene semáforo centro avenida 10 Segundos

No tiene semáforo calle 10 Segundos

No tiene semáforo avenida 5 Segundos

5.4 Cálculo del tiempo que el camión recorre los lados de las cuadras

Sabiendo que la distancia que recorre un objeto es una relación entre velocidad de

movimiento y el tiempo, esta puede expresarse en la ecuación 3.

Con la fórmula anterior se pude obtener el tiempo del camión repartidor en que

recorre un lado de la cuadra si se calcula la distancia del lado de la cuadra entre

un promedio de la velocidad del camión repartidor, y al resultado de este cálculo

se le suma el tiempo por tipo de esquina, dando como resultado el tiempo total.

41

Lo antes mencionado se puede ver en la figura 5.7, la cual es un fragmento del

Anexo 1 (Tiempo total), por lado de la cuadra, en esta figura se puede observar 3

columnas color verde, las cuales representan los nodos, se toma como ejemplo el

Nodo 2, en el rectángulo color rojo se encuentran los nodos a los que tiene

conexión el Nodo 2, que son los nodos 1, 3 y 21.

En el rectángulo azul se puede ver la distancia entre el Nodo 2 y 1, que son 0.1

Km; al lado se puede ver la velocidad entre el Nodo 2 y 1, la cual es zona superior,

que corresponde a 45Km/h, como se muestra en la tabla 5.1 Velocidad por zona;

el tiempo parcial es la división de 0.1Km entre 45Km/h la cual da un resultado de 8

segundos; el tipo de esquina es, no tiene semáforo avenida como se muestra en la

tabla 5.2, con un valor de 5 Segundos.

El tiempo total representado por el cuadro naranja es el valor obtenido de la suma

del tiempo parcial y el tipo de esquina dando como resultado 13 segundos, el cual

representa el tiempo en el que el camión repartidor recorre del Nodo 2 al nodo 1.

Figura 5.6 Tiempo total por lado de la cuadra


5.5 Transformar los valores a una forma estándar

Nuestro siguiente paso es plantear el ejercicio en un problema de programación

lineal, por lo cual en este subtema explicaremos la creación de la forma estándar.

42

Para realizar la forma estándar el primer paso es obtener la forma canónica,

donde el ancho de la matriz es igual al número de nodos, más dos casillas extras

por la función objetivo, más la restricción de no negatividad de las variables; su

larga está conformado por las variables (X), más el signo de la las restricciones y

el valor de las restricción que se encuentran en la última columna derecha.

En la parte superior de la figura 5.7 encerradas en color rojo se encuentra la

función objetivo minimizar, la cual está constituida de los tiempos obtenidos de la

tabla 1 Anexo y sus respectivas variables (X), las cuales contienen la relación de

sus nodos, donde el primer número de cada variable después de X es el nodo

fuente y el segundo es el nodo destino; donde la minimización de Z es igual a la

sumatoria de las variables, con sus valores respectivos de tiempos al inicio de

cada variable.

Ya que cada fila después de la función objetivo representa un nodo ordenado del

nodo 1 al nodo 268 en orden ascendente, se pueden notar las relaciones, por

ejemplo se encuentran dos variables X1, 2, en las restricciones donde la variable

negativa es la variable inicial y la positiva es la variable fina, esto se aplica para

todas las demás relaciones de nodos representadas en variables (X); esto se

puede observar en la figura 5.7, donde las variables antes mencionadas están

encerradas en color azul.

En la figura 5.7, todas las restricciones son de igualdad, estás se encuentran

encerradas en color morado, en este ejemplo se quiere representar el tiempo

mínimo y su trayectoria del nodo 1 al nodo 268, por lo cual se tiene que asignar los

valores correspondiente a estos nodos en los datos del lado derecho, donde el

primer elemento se le asigna el valor -1 asignando el nodo fuente, nodo número 1,

(encerrado color verde), y con el valor de 1 el nodo destino, nodo número 268 que

se encuentra al final de los valores (encerrado color naranja).

43

Por último se agrega la restricción de no negatividad, esta se encuentra en la parte inferior, lo cual nos indican que ninguna variable del problema puede ser

negativa, esta se puede ver encerrada en color rosa en la figura 5.7; ya que no se puede transcribir toda la forma canónica con los 268, de tal forma que entre en

una hoja; se muestra su representación simplificada en la figura 5.7.

Figura 5.7 Forma canónica 268 nodos simplificada (Fuente: elaboración propia)

44

En este ejercicio se tiene que restablecer la fila de nodo fuente, ya que todos los valores de lado derecho de las restricciones deben de ser no negativas por lo

cual toda la fila encerrada en color rojo en la figura 5.8 fue multiplicada por -1.

Figura 5.8 Forma canónica (Fuente: elaboración propia)

El siguiente paso es transformar el problema en forma estándar esto se hace agregando variables de igualdad denominadas “A”, las cuales corresponden al

número de restricciones de este ejemplo, conformando la matriz identidad, estas se agregan entre las variables (X) y los valores de la derecha como se puede ver

45

encerrado en rojo en la figura 5.9, estas conforman una diagonal positiva; las variables de igualdad se restan a la función objetivo, y se unen a la restricción de no

negatividad, encerradas en color verde; por último se puede observar en la parte inferior de la función objetivo, la función objetivo igualada a cero.

Figura 5.9 Forma estándar (Fuente: elaboración propia)

46

5.6 Programación de las rutas, aplicando programación lineal

Los datos para realizar las iteraciones utilizando programación son los valores

obtenidos en la tabla 1 Anexos, la cual está conformada por el tiempo total de los

lados de las cuadra; como resultado de estas iteraciones la computadora arrojara

el recorrido y el tiempo del recorrido.

De esta manera si se quisiera modificar los tiempos de los nodos por algún cambio

en los tiempos de los lados de las cuadras, lo único que se necesita hacer es,

actualizar los datos de la tabla del programa; para poder comprender más la

programación de las rutas, aplicando programación lineal se dará un ejemplo, este

será de 9 nodos y se explicara las interacciones de una manera detallada y clara.

En la figura 5.10, se presenta la red que se utilizara para realizar el ejemplo de

programación lineal, cada cuadro gris con número representa los nodos, las

flechas indican la dirección de recorrido; como se observa en la figua 5.9, todos

los nodos excepto (1,2) y (2,3) son unidirecionales.

Figura 5.10 Red


47

Los datos de la figura 5.9, se expresan en la tabla 5.3, en donde la segunda celda

de las filas verdes se expresa el nodo fuente, en la tercera celda de las filas

blancas aparece el nodo destino y en la última celda de las filas blancas aparece

el tiempo de los lados de las cuadras, con respecto a la relación nodo fuente, nodo

destino.

Tabla 5.3 Tabla tiempos ejemplo


De Nodo 1

A Nodo

2 = 0.0361

A Nodo

4 = 0.04

De Nodo 2

A Nodo

1 = 0.0361

A Nodo

3 = 0.0361

De Nodo 3

A Nodo

2 = 0.0361

A Nodo

6 = 0.015

De Nodo 4

A Nodo

7 = 0.015

De Nodo 5

A Nodo

2 = 0.015

A Nodo

4 = 0.015

De Nodo 6

A Nodo

5 = 0.015

A Nodo

9 = 0.015

De Nodo 7

A Nodo

8 = 0.015

De Nodo 8

A Nodo

5 = 0.015

A Nodo

9 = 0.015

De Nodo 9

48

Después pasamos los valores de la tabla a un problema de programación lineal, como se puede apreciar en la figura 5.11, este problema se representa en forma

matricial denominada forma canónica, donde el ancho de la matriz es igual al número de nodos, más dos casillas extras por la función objetivo, más la restricción

de no negatividad de las variables; su larga está conformado por las variables (X), más el signo de la las restricciones y el valor de las restricción que se

encuentran en la última columna derecha.

Figura 5.11 Forma canónica


En la figura 5.12 se puede observar en la parte superior encerradas en color rojo la función objetivo minimizar la cual es igual a la sumatoria de los tiempos

obtenidos de la tabla 5.3 y sus respectivas variables (X), las cuales contienen la relación de sus nodos, donde el primer número de cada variable después de X es

el nodo fuente y el segundo es el nodo destino.

49

Figura 5.12 Forma canónica función objetivo


Ya que cada fila después de la función objetivo representa un nodo ordenado del nodo 1 al nodo 9 en orden ascendente, se pueden notar las relaciones, por

ejemplo se encuentran dos variables X 1,2, que representa el sentido de los nodos, donde la variable negativa es el nodo fuente y la positiva es el nodo destino,

esto se aplica para todas las demás relaciones de nodos representadas en variables; esto se puede observar en la figura 5.13, donde las variables antes

mencionadas están encerradas en color rojo.

50

Figura 5.13 Forma canónica relación de variables


En la figura 5.14, todas las restricciones son de igualdad, estás se encuentran encerradas en color azul, en este ejemplo se quiere representar el tiempo mínimo y

su trayectoria del nodo 1 al nodo 9, por lo cual se tiene que asignar estos nodos en los datos del lado derecho, donde el primer elemento se le asigna el valor -1

asignando el nodo 1, (rectángulo color rojo), y con 1 el nodo final 9 que se encuentra al final de los valores (rectángulo color verde).

51

Figura 5.14 Forma canónica restricciones


La última parte que integra la forma canónica es la restricción de no negatividad; como se aprecia en el recuadro de color rojo en la figura 5.15, esta restricción se

ubica en la parte inferior del modelo, indicando que ninguna variable del problema puede ser negativa.

52

Figura 5.15 Forma canónica restricción de no negatividad


De manera general en los métodos de solución de problemas lineales se aplica el criterio de factibilidad que indica que ningún valor del lado derecho puede ser

negativo, esto no se cumple en el modelo planteado, ya que el valor de la primera restricción es negativo (ver figura 5.15). Para volver factible esta restricción se

multiplicará por -1, el resultado obtenido se muestra encerrado en color rojo en la figura 5.16.

El siguiente paso es transformar el problema en forma estándar esto se hace agregando variables artificiales representadas con la letra “A”, las cuales

corresponden al número de restricciones de este ejemplo, conformando la matriz identidad, estas se agregan entre las variables (X) y los valores de la derecha

como se puede ver encerrado en rojo en la figura 5.17, estas crean una diagonal positiva; por último las variables se suman cuando Z es igual a las variables (X) y

a las variables artificiales (A), y se restan cuando la función objetivo es igual a cero, encerradas en color verde.

53

Figura 5.16 Restablecer la fila de nodo fuente (Fuente: recopilación propia)

Figura 5.17 Forma estándar (Fuente: recopilación propia)

54

El siguiente paso es tomar los valores de la forma estándar para plantear la tabla inicial; para lograr esto primero se colocara la función objetivo igualándola a cero

come se puede apreciar a continuación: Minimizar Z -0.0361X1,2 -0.04X1,4 -0.0361X2,1 -0.0361X2,3 -0.0361X3,2 -0.015X3,6 -0.015X4,7 -0.015X5,2 -0.015X5,4 -0.015X6,5

-0.015X6,9 -0.015X7,8 -0.015X8,5 -0.015X8,9 -MA1 -MA2 -MA3 -MA4 -MA5 -MA6 -MA7 -MA8 -MA9 = 0; esta se encuentra encerrado en color rojo en la figura 5.18: el

método de programación lineal que se utilizara es el de la M o de penalización, M es un número muy grande en este ejemplo M=1,000; en la parte interior de la

matriz solo se transcriben los valores de las “X” y “A”, para poderlos identificar en la parte superior de la matriz se crea otra fila en la cual se detalla a que variable

“X” o “A” corresponden esos valores, y en la parte izquierda se crea otra columna con las variables básicas “A”, estas se encuentran enceradas en color verde

figura 5.18; por último los espacios vacíos se rellenan de ceros y la restricción de no negatividad se elimina.

Figura 5.18 Planteamiento de la tabla inicial con la técnica de la M


El siguiente paso es restablecer los vectores unitarios de las variables básicas mediante eliminación de Gauss, para esto se transcriben casi todos los valores de

la matriz anterior a la matriz nueva excepto la función objetivo, las nuevas celdas de la función objetivo estarán compuestas del valor de la celda de la función

55

objetivo de la matriz anterior, más la suma de cada uno de los valores inversos de las variables básicas de la columna por sus correspondientes valores de las

variables básicas ubicadas en la función objetivo de la matriz anterior, estas interacciones se explican detalladamente en la tabla 5.4; y se expresan en la figura

5.18 encerradas en color rojo.

Tabla 5.4 Interacciones para restablecer las variables básicas


Matriz Interacciones celdas Interacciones cantidades

Restableciendo variables básicas celda(X 1,2;Z) + [ - ( celda(X 1,2;A 9) ) * celda(A 9;Z) ] + [ - ( celda(X 1,2;A 8) ) * celda(A 8;Z) ] + [ - ( celda(X 1,2;A 7) ) * celda(A 7;Z) ] + [

- ( celda(X 1,2;A 6) ) * celda(A 6;Z) ] + [ - ( celda(X 1,2;A 5) ) * celda(A 5;Z) ] + [ - ( celda(X 1,2;A 4) ) * celda(A 4;Z) ] + [ - ( celda(X 1,2;A

3) ) * celda(A 3;Z) ] + [ - ( celda(X 1,2;A 2) ) * celda(A 2;Z) ] + [ - ( celda(X 1,2;A 1) ) * celda(A 1;Z) ] = nueva celda(X 1,2;Z)

-0.0361 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-

(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-

(0)*(-1000)]+ [-(1)*(-1000)]+ [-(1)*(-1000)]=

1999.9639




-0.04 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(1)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(1)*(-1000)]= 1999.96




-0.0361 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-

(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-

(0)*(-1000)]+ [-(-1)*(-1000)]+ [-(-1)*(-1000)]= -

2000.0361




-0.0361 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-

(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-

(1)*(-1000)]+ [-(-1)*(-1000)]+ [-(0)*(-1000)]= -

0.0361

56

Tabla 5.4 Interacciones para restablecer las variables básicas (Continuación)





-0.0361 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-

(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(-

1)*(-1000)]+ [-(1)*(-1000)]+ [-(0)*(-1000)]= -

0.0361




-0.015 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(1)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(-1)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= -0.015




-0.015 + [-(0)*(-1000)]+ [-(1)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(-1)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= -0.015




-0.015 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(-1)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(1)*(-1000)]+ [-(0)*(-1000)]= -0.015




-0.015 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(-1)*(-1000)]+ [-(1)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= -0.015




-0.015 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(-1)*(-

1000)]+ [-(1)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= -0.015




-0.015 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(-1)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= -0.015

57






-0.015 + [-(1)*(-1000)]+ [-(-1)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= -0.015




-0.015 + [-(-1)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(1)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= -0.015




-0.015 + [-(-1)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= -0.015

Restableciendo variables básicas celda(A 1;Z) + [ - ( celda(A 1;A 9) ) * celda(A 9;Z) ] + [ - ( celda(A 1;A 8) ) * celda(A 8;Z) ] + [ - ( celda(A 1;A 7) ) * celda(A 7;Z) ] + [ - (

celda(A 1;A 6) ) * celda(A 6;Z) ] + [ - ( celda(A 1;A 5) ) * celda(A 5;Z) ] + [ - ( celda(A 1;A 4) ) * celda(A 4;Z) ] + [ - ( celda(A 1;A 3) ) *

celda(A 3;Z) ] + [ - ( celda(A 1;A 2) ) * celda(A 2;Z) ] + [ - ( celda(A 1;A 1) ) * celda(A 1;Z) ] = nueva celda(A 1;Z)

-1000 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(1)*(-1000)]= 0




-1000 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(1)*(-1000)]+ [-(0)*(-1000)]= 0




-1000 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(1)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= 0




-1000 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(1)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= 0

58






-1000 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(1)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= 0




-1000 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(1)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= 0




-1000 + [-(0)*(-1000)]+ [-(1)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= 0




-1000 + [-(1)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= 0




-1000 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]= 0

Restableciendo variables básicas celda(Solución) + [ - ( celda(Solución ;A 9) ) * celda(A 9;Z) ] + [ - ( celda(Solución ;A 8) ) * celda(A 8;Z) ] + [ - ( celda(Solución ;A 7) ) *

celda(A 7;Z) ] + [ - ( celda(Solución ;A 6) ) * celda(A 6;Z) ] + [ - ( celda(Solución ;A 5) ) * celda(A 5;Z) ] + [ - ( celda(Solución ;A 4) ) *

celda(A 4;Z) ] + [ - ( celda(Solución ;A 3) ) * celda(A 3;Z) ] + [ - ( celda(Solución ;A 2) ) * celda(A 2;Z) ] + [ - ( celda(Solución ;A 1) ) *

celda(A 1;Z) ] = nueva celda(Solución ;Z)

0 + [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(0)*(-1000)]+ [-(0)*(-

1000)]+ [-(0)*(-1000)]+ [-(1)*(-1000)]= 2000

59

Los resultados de las interacciones de la tabla 5.4 se expresan en la fila de Z figura 5.19, encerradas en color rojo; cabe mencionar que existen valores que pasan

con la misma cantidad aun después de realizarle las interacciones..

Figura 5.19 Restableciendo variables básicas


El siguiente paso es encontrar la variable de entrada y la variable de salida; la variable de entrada es el número mayor de la función objetivo respecto a los

valores de “X” en este caso es X1,2 con la cantidad de: 1999.9639; la variable de salida es el menor valor de la relación de la columna de solución, entre (/) la

columna de la variable de entrada, en este caso corresponde a la fila A2, siendo la operación (0)/(1)=0; la nueva matriz se crea del resultado de eliminación

Gaussiana, estas operaciones se muestran detalladamente en la tabla 5.5.

60

Tabla 5.5 Cálculos para la primera iteración



Variable de entrada=X 1,2; Variable de salida=A 2

Primera iteración celda(X 1,2;A 1)+ (- celda(X 1,2;A 1))* celda(X 1,2;X 1,2)= nueva celda(X 1,2;A 1) (1)+ (- (1))* (1)= nueva celda(0)

Primera iteración fila pivote=A 2 1








Primera iteración celda(X 1,2;Z)+ (- celda(X 1,2;Z))* celda(X 1,2;X 1,2)= nueva celda(X 1,2;Z) (1999.9639)+ (- (1999.9639))* (1)= nueva celda(0)

Primera iteración celda(X 2,1;A 1)+ (- celda(X 1,2;A 1))* celda(X 2,1;X 1,2)= nueva celda(X 2,1;A 1) (-1)+ (- (1))* (-1)= nueva celda(0)

Primera iteración fila pivote=A 2 -1

Primera iteración celda(X 2,1;A 3)+ (- celda(X 1,2;A 3))* celda(X 2,1;X 1,2)= nueva celda(X 2,1;A 3) (0)+ (- (0))* (-1)= nueva celda(0)



61

Tabla 5.5 Cálculos para la primera iteración (Continuación)






Primera iteración celda(X 2,1;Z)+ (- celda(X 1,2;Z))* celda(X 2,1;X 1,2)= nueva celda(X 2,1;Z) (-2000.0361)+ (- (1999.9639))* (-1)= nueva celda(-0.0722)


Primera iteración fila pivote=A 2 -1








Primera iteración celda(X 2,3;Z)+ (- celda(X 1,2;Z))* celda(X 2,3;X 1,2)= nueva celda(X 2,3;Z) (-0.0361)+ (- (1999.9639))* (-1)= nueva celda(1999.9278)

Primera iteración celda(X 3,2;A 1)+ (- celda(X 1,2;A 1))* celda(X 3,2;X 1,2)= nueva celda(X 3,2;A 1) (0)+ (- (1))* (1)= nueva celda(-1)


62



Primera iteración celda(X 3,2;A 3)+ (- celda(X 1,2;A 3))* celda(X 3,2;X 1,2)= nueva celda(X 3,2;A 3) (-1)+ (- (0))* (1)= nueva celda(-1)







Primera iteración celda(X 3,2;Z)+ (- celda(X 1,2;Z))* celda(X 3,2;X 1,2)= nueva celda(X 3,2;Z) (-0.0361)+ (- (1999.9639))* (1)= nueva celda(-2000)

Primera iteración celda(X 5,2;A 1)+ (- celda(X 1,2;A 1))* celda(X 5,2;X 1,2)= nueva celda(X 5,2;A 1) (0)+ (- (1))* (1)= nueva celda(-1)




Primera iteración celda(X 5,2;A 5)+ (- celda(X 1,2;A 5))* celda(X 5,2;X 1,2)= nueva celda(X 5,2;A 5) (-1)+ (- (0))* (1)= nueva celda(-1)





Primera iteración celda(X 5,2;Z)+ (- celda(X 1,2;Z))* celda(X 5,2;X 1,2)= nueva celda(X 5,2;Z) (-0.015)+ (- (1999.9639))* (1)= nueva celda(-1999.9789)

63



Primera iteración celda(A 2;A 1)+ (- celda(X 1,2;A 1))* celda(A 2;X 1,2)= nueva celda(A 2;A 1) (0)+ (- (1))* (1)= nueva celda(-1)


Primera iteración celda(A 2;A 3)+ (- celda(X 1,2;A 3))* celda(A 2;X 1,2)= nueva celda(A 2;A 3) (0)+ (- (0))* (1)= nueva celda(0)







Primera iteración celda(A 2;Z)+ (- celda(X 1,2;Z))* celda(A 2;X 1,2)= nueva celda(A 2;Z) (0)+ (- (1999.9639))* (1)= nueva celda(-1999.9639)

Los resultados de las interacciones de la tabla 5.5 se expresan en las columnas encerradas en color rojo de la figura 5.20; cabe mencionar que los valores a los

que no se les realiza interacciones pasan iguales a la nueva matriz.

64

Figura 5.20 Primera iteración (Fuente: recopilación propia)




Gaussiana, estas operaciones se muestran en la tabla 5.6.

Tabla 5.6 Cálculos para la segunda iteración




Segunda iteración celda(X 1,4; A 1)+ (- celda(X 1,4; A 1))* celda(X 1,4; X 1,4)= nueva celda(X 1,4; A 1) (1)+ (- (1))* (1)= nueva celda(0)

65

Tabla 5.6 Cálculos para la segunda iteración (Continuación)


Segunda iteración celda(X 1,4; X 1,2)+ (- celda(X 1,4; X 1,2))* celda(X 1,4; X 1,4)= nueva celda(X 1,4; X 1,2) (0)+ (- (0))* (1)= nueva celda(0)


Segunda iteración fila pivote= A 4 1






Segunda iteración celda(X 1,4; Z)+ (- celda(X 1,4; Z))* celda(X 1,4; X 1,4)= nueva celda(X 1,4; Z) (1999.96)+ (- (1999.96))* (1)= nueva celda(0)

Segunda iteración celda(X 4,7; A 1)+ (- celda(X 1,4; A 1))* celda(X 4,7; X 1,4)= nueva celda(X 4,7; A 1) (0)+ (- (1))* (-1)= nueva celda(1)

Segunda iteración celda(X 4,7; X 1,2)+ (- celda(X 1,4; X 1,2))* celda(X 4,7; X 1,4)= nueva celda(X 4,7; X 1,2) (0)+ (- (0))* (-1)= nueva celda(0)


Segunda iteración fila pivote= A 4 -1






66



Segunda iteración celda(X 4,7; Z)+ (- celda(X 1,4; Z))* celda(X 4,7; X 1,4)= nueva celda(X 4,7; Z) (-0.015)+ (- (1999.96))* (-1)= nueva celda(1999.945)

Segunda iteración celda(X 5,4; A 1)+ (- celda(X 1,4; A 1))* celda(X 5,4; X 1,4)= nueva celda(X 5,4; A 1) (0)+ (- (1))* (1)= nueva celda(-1)

Segunda iteración celda(X 5,4; X 1,2)+ (- celda(X 1,4; X 1,2))* celda(X 5,4; X 1,4)= nueva celda(X 5,4; X 1,2) (0)+ (- (0))* (1)= nueva celda(0)



Segunda iteración celda(X 5,4; A 5)+ (- celda(X 1,4; A 5))* celda(X 5,4; X 1,4)= nueva celda(X 5,4; A 5) (-1)+ (- (0))* (1)= nueva celda(-1)





Segunda iteración celda(X 5,4; Z)+ (- celda(X 1,4; Z))* celda(X 5,4; X 1,4)= nueva celda(X 5,4; Z) (-0.015)+ (- (1999.96))* (1)= nueva celda(-1999.975)

Segunda iteración celda(A 4; A 1)+ (- celda(X 1,4; A 1))* celda(A 4; X 1,4)= nueva celda(A 4; A 1) (0)+ (- (1))* (1)= nueva celda(-1)

Segunda iteración celda(A 4; X 1,2)+ (- celda(X 1,4; X 1,2))* celda(A 4; X 1,4)= nueva celda(A 4; X 1,2) (0)+ (- (0))* (1)= nueva celda(0)

Segunda iteración celda(A 4; A 3)+ (- celda(X 1,4; A 3))* celda(A 4; X 1,4)= nueva celda(A 4; A 3) (0)+ (- (0))* (1)= nueva celda(0)




67






Segunda iteración celda(A 4; Z)+ (- celda(X 1,4; Z))* celda(A 4; X 1,4)= nueva celda(A 4; Z) (0)+ (- (1999.96))* (1)= nueva celda(-1999.96)



Figura 5.20 Segunda iteración (Fuente: recopilación propia)

68





Tabla 5.7 Cálculos para la tercera iteración




Tercera iteración celda(X 4,7; A 1)+ (- celda(X 4,7; A 1))* celda(X 4,7; X 4,7)= nueva celda(X 4,7; A 1) (1)+ (- (1))* (1)= nueva celda(0)

Tercera iteración celda(X 4,7; X 1,2)+ (- celda(X 4,7; X 1,2))* celda(X 4,7; X 4,7)= nueva celda(X 4,7; X 1,2) (0)+ (- (0))* (1)= nueva celda(0)


Tercera iteración celda(X 4,7; X 1,4)+ (- celda(X 4,7; X 1,4))* celda(X 4,7; X 4,7)= nueva celda(X 4,7; X 1,4) (-1)+ (- (-1))* (1)= nueva celda(0)



Tercera iteración fila pivote= A 7 1



69

Tabla 5.7 Cálculos para la tercera iteración (Continuación)


Tercera iteración celda(X 4,7; Z)+ (- celda(X 4,7; Z))* celda(X 4,7; X 4,7)= nueva celda(X 4,7; Z) (1999.945)+ (- (1999.945))* (1)= nueva celda(0)

Tercera iteración celda(X 7,8; A 1)+ (- celda(X 4,7; A 1))* celda(X 7,8; X 4,7)= nueva celda(X 7,8; A 1) (0)+ (- (1))* (-1)= nueva celda(1)

Tercera iteración celda(X 7,8; X 1,2)+ (- celda(X 4,7; X 1,2))* celda(X 7,8; X 4,7)= nueva celda(X 7,8; X 1,2) (0)+ (- (0))* (-1)= nueva celda(0)


Tercera iteración celda(X 7,8; X 1,4)+ (- celda(X 4,7; X 1,4))* celda(X 7,8; X 4,7)= nueva celda(X 7,8; X 1,4) (0)+ (- (-1))* (-1)= nueva celda(-1)



Tercera iteración fila pivote= A 7 -1



Tercera iteración celda(X 7,8; Z)+ (- celda(X 4,7; Z))* celda(X 7,8; X 4,7)= nueva celda(X 7,8; Z) (-0.015)+ (- (1999.945))* (-1)= nueva celda(1999.93)

Tercera iteración celda(A 7; A 1)+ (- celda(X 4,7; A 1))* celda(A 7; X 4,7)= nueva celda(A 7; A 1) (0)+ (- (1))* (1)= nueva celda(-1)

Tercera iteración celda(A 7; X 1,2)+ (- celda(X 4,7; X 1,2))* celda(A 7; X 4,7)= nueva celda(A 7; X 1,2) (0)+ (- (0))* (1)= nueva celda(0)

Tercera iteración celda(A 7; A 3)+ (- celda(X 4,7; A 3))* celda(A 7; X 4,7)= nueva celda(A 7; A 3) (0)+ (- (0))* (1)= nueva celda(0)

Tercera iteración celda(A 7; X 1,4)+ (- celda(X 4,7; X 1,4))* celda(A 7; X 4,7)= nueva celda(A 7; X 1,4) (0)+ (- (-1))* (1)= nueva celda(1)



70

Tabla 5.7 Cálculos para la tercera iteración (Continuación)


Tercera iteración fila pivote= A 7 1



Tercera iteración celda(A 7; Z)+ (- celda(X 4,7; Z))* celda(A 7; X 4,7)= nueva celda(A 7; Z) (0)+ (- (1999.945))* (1)= nueva celda(-1999.945)



Figura 5.22 Tercera iteración


71





Tabla 5.8 Cálculos para la cuarta iteración




Cuarta iteración celda(X 7,8; A 1)+ (- celda(X 7,8; A 1))* celda(X 7,8; X 7,8)= nueva celda(X 7,8; A 1) (1)+ (- (1))* (1)= nueva celda(0)

Cuarta iteración celda(X 7,8; X 1,2)+ (- celda(X 7,8; X 1,2))* celda(X 7,8; X 7,8)= nueva celda(X 7,8; X 1,2) (0)+ (- (0))* (1)= nueva celda(0)


Cuarta iteración celda(X 7,8; X 1,4)+ (- celda(X 7,8; X 1,4))* celda(X 7,8; X 7,8)= nueva celda(X 7,8; X 1,4) (-1)+ (- (-1))* (1)= nueva celda(0)



Cuarta iteración celda(X 7,8; X 4,7)+ (- celda(X 7,8; X 4,7))* celda(X 7,8; X 7,8)= nueva celda(X 7,8; X 4,7) (-1)+ (- (-1))* (1)= nueva celda(0)

Cuarta iteración fila pivote= A 8 1


Cuarta iteración celda(X 7,8; Z)+ (- celda(X 7,8; Z))* celda(X 7,8; X 7,8)= nueva celda(X 7,8; Z) (1999.93)+ (- (1999.93))* (1)= nueva celda(0)

72

Tabla 5.8 Cálculos para la cuarta iteración (Continuación)


Cuarta iteración celda(X 8,5; A 1)+ (- celda(X 7,8; A 1))* celda(X 8,5; X 7,8)= nueva celda(X 8,5; A 1) (0)+ (- (1))* (-1)= nueva celda(1)

Cuarta iteración celda(X 8,5; X 1,2)+ (- celda(X 7,8; X 1,2))* celda(X 8,5; X 7,8)= nueva celda(X 8,5; X 1,2) (0)+ (- (0))* (-1)= nueva celda(0)


Cuarta iteración celda(X 8,5; X 1,4)+ (- celda(X 7,8; X 1,4))* celda(X 8,5; X 7,8)= nueva celda(X 8,5; X 1,4) (0)+ (- (-1))* (-1)= nueva celda(-1)




Cuarta iteración fila pivote= A 8 -1


Cuarta iteración celda(X 8,5; Z)+ (- celda(X 7,8; Z))* celda(X 8,5; X 7,8)= nueva celda(X 8,5; Z) (-0.015)+ (- (1999.93))* (-1)= nueva celda(1999.915)


Cuarta iteración celda(X 8,9; X 1,2)+ (- celda(X 7,8; X 1,2))* celda(X 8,9; X 7,8)= nueva celda(X 8,9; X 1,2) (0)+ (- (0))* (-1)= nueva celda(0)






Cuarta iteración fila pivote= A 8 -1

73

Tabla 5.8 Cálculos para la cuarta iteración (Continuación)



Cuarta iteración celda(X 8,9; Z)+ (- celda(X 7,8; Z))* celda(X 8,9; X 7,8)= nueva celda(X 8,9; Z) (-0.015)+ (- (1999.93))* (-1)= nueva celda(1999.915)

Cuarta iteración celda(A 8; A 1)+ (- celda(X 7,8; A 1))* celda(A 8; X 7,8)= nueva celda(A 8; A 1) (0)+ (- (1))* (1)= nueva celda(-1)

Cuarta iteración celda(A 8; X 1,2)+ (- celda(X 7,8; X 1,2))* celda(A 8; X 7,8)= nueva celda(A 8; X 1,2) (0)+ (- (0))* (1)= nueva celda(0)

Cuarta iteración celda(A 8; A 3)+ (- celda(X 7,8; A 3))* celda(A 8; X 7,8)= nueva celda(A 8; A 3) (0)+ (- (0))* (1)= nueva celda(0)

Cuarta iteración celda(A 8; X 1,4)+ (- celda(X 7,8; X 1,4))* celda(A 8; X 7,8)= nueva celda(A 8; X 1,4) (0)+ (- (-1))* (1)= nueva celda(1)



Cuarta iteración celda(A 8; X 4,7)+ (- celda(X 7,8; X 4,7))* celda(A 8; X 7,8)= nueva celda(A 8; X 4,7) (0)+ (- (-1))* (1)= nueva celda(1)

Cuarta iteración fila pivote= A 8 1


Cuarta iteración celda(A 8; Z)+ (- celda(X 7,8; Z))* celda(A 8; X 7,8)= nueva celda(A 8; Z) (0)+ (- (1999.93))* (1)= nueva celda(-1999.93)



74

Figura 5.23 Cuarta iteración (Fuente: recopilación propia)





Tabla 5.9 Cálculos para la quinta iteración




Quinta iteración celda(X 2,3; A 1)+ (- celda(X 2,3; A 1))* celda(X 2,3; X 2,3)= nueva celda(X 2,3; A 1) (1)+ (- (1))* (1)= nueva celda(0)

75

Tabla 5.9 Cálculos para la quinta iteración (Continuación)


Quinta iteración celda(X 2,3; X 1,2)+ (- celda(X 2,3; X 1,2))* celda(X 2,3; X 2,3)= nueva celda(X 2,3; X 1,2) (-1)+ (- (-1))* (1)= nueva celda(0)

Quinta iteración fila pivote= A 3 1

Quinta iteración celda(X 2,3; X 1,4)+ (- celda(X 2,3; X 1,4))* celda(X 2,3; X 2,3)= nueva celda(X 2,3; X 1,4) (0)+ (- (0))* (1)= nueva celda(0)






Quinta iteración celda(X 2,3; Z)+ (- celda(X 2,3; Z))* celda(X 2,3; X 2,3)= nueva celda(X 2,3; Z) (1999.9278)+ (- (1999.9278))* (1)= nueva celda(0)

Quinta iteración celda(X 3,2; A 1)+ (- celda(X 2,3; A 1))* celda(X 3,2; X 2,3)= nueva celda(X 3,2; A 1) (-1)+ (- (1))* (-1)= nueva celda(0)

Quinta iteración celda(X 3,2; X 1,2)+ (- celda(X 2,3; X 1,2))* celda(X 3,2; X 2,3)= nueva celda(X 3,2; X 1,2) (1)+ (- (-1))* (-1)= nueva celda(0)

Quinta iteración fila pivote= A 3 -1

Quinta iteración celda(X 3,2; X 1,4)+ (- celda(X 2,3; X 1,4))* celda(X 3,2; X 2,3)= nueva celda(X 3,2; X 1,4) (0)+ (- (0))* (-1)= nueva celda(0)

Quinta iteración celda(X 3,2; A 5)+ (- celda(X 2,3; A 5))* celda(X 3,2; X 2,3)= nueva celda(X 3,2; A 5) (0)+ (- (0))* (-1)= nueva celda(0)





76



Quinta iteración celda(X 3,2; Z)+ (- celda(X 2,3; Z))* celda(X 3,2; X 2,3)= nueva celda(X 3,2; Z) (-2000)+ (- (1999.9278))* (-1)= nueva celda(-0.0722)


Quinta iteración celda(X 3,6; X 1,2)+ (- celda(X 2,3; X 1,2))* celda(X 3,6; X 2,3)= nueva celda(X 3,6; X 1,2) (0)+ (- (-1))* (-1)= nueva celda(-1)

Quinta iteración fila pivote= A 3 -1







Quinta iteración celda(X 3,6; Z)+ (- celda(X 2,3; Z))* celda(X 3,6; X 2,3)= nueva celda(X 3,6; Z) (-0.015)+ (- (1999.9278))* (-1)= nueva celda(1999.9128)

Quinta iteración celda(A 3; A 1)+ (- celda(X 2,3; A 1))* celda(A 3; X 2,3)= nueva celda(A 3; A 1) (0)+ (- (1))* (1)= nueva celda(-1)

Quinta iteración celda(A 3; X 1,2)+ (- celda(X 2,3; X 1,2))* celda(A 3; X 2,3)= nueva celda(A 3; X 1,2) (0)+ (- (-1))* (1)= nueva celda(1)

Quinta iteración fila pivote= A 3 1

Quinta iteración celda(A 3; X 1,4)+ (- celda(X 2,3; X 1,4))* celda(A 3; X 2,3)= nueva celda(A 3; X 1,4) (0)+ (- (0))* (1)= nueva celda(0)

Quinta iteración celda(A 3; A 5)+ (- celda(X 2,3; A 5))* celda(A 3; X 2,3)= nueva celda(A 3; A 5) (0)+ (- (0))* (1)= nueva celda(0)


77






Quinta iteración celda(A 3; Z)+ (- celda(X 2,3; Z))* celda(A 3; X 2,3)= nueva celda(A 3; Z) (0)+ (- (1999.9278))* (1)= nueva celda(-1999.9278)



Figura 5.24 Quinta iteración


78





Tabla 5.10 Cálculos para la sexta iteración




Sexta iteración celda(X 5,2; A 1)+ (- celda(X 8,5; A 1))* celda(X 5,2; X 8,5)= nueva celda(X 5,2; A 1) (-1)+ (- (1))* (-1)= nueva celda(0)

Sexta iteración celda(X 5,2; X 1,2)+ (- celda(X 8,5; X 1,2))* celda(X 5,2; X 8,5)= nueva celda(X 5,2; X 1,2) (1)+ (- (0))* (-1)= nueva celda(1)


Sexta iteración celda(X 5,2; X 1,4)+ (- celda(X 8,5; X 1,4))* celda(X 5,2; X 8,5)= nueva celda(X 5,2; X 1,4) (0)+ (- (-1))* (-1)= nueva celda(-1)

Sexta iteración fila pivote= A 5 -1

Sexta iteración celda(X 5,2; A 6)+ (- celda(X 8,5; A 6))* celda(X 5,2; X 8,5)= nueva celda(X 5,2; A 6) (0)+ (- (0))* (-1)= nueva celda(0)




Sexta iteración celda(X 5,2; Z)+ (- celda(X 8,5; Z))* celda(X 5,2; X 8,5)= nueva celda(X 5,2; Z) (-1999.9789)+ (- (1999.915))* (-1)= nueva celda(-0.0639)

79

Tabla 5.10 Cálculos para la sexta iteración (Continuación)


Sexta iteración celda(X 5,4; A 1)+ (- celda(X 8,5; A 1))* celda(X 5,4; X 8,5)= nueva celda(X 5,4; A 1) (-1)+ (- (1))* (-1)= nueva celda(0)



Sexta iteración celda(X 5,4; X 1,4)+ (- celda(X 8,5; X 1,4))* celda(X 5,4; X 8,5)= nueva celda(X 5,4; X 1,4) (1)+ (- (-1))* (-1)= nueva celda(0)

Sexta iteración fila pivote= A 5 -1





Sexta iteración celda(X 5,4; Z)+ (- celda(X 8,5; Z))* celda(X 5,4; X 8,5)= nueva celda(X 5,4; Z) (-1999.975)+ (- (1999.915))* (-1)= nueva celda(-0.06)

Sexta iteración celda(X 6,5; A 1)+ (- celda(X 8,5; A 1))* celda(X 6,5; X 8,5)= nueva celda(X 6,5; A 1) (0)+ (- (1))* (1)= nueva celda(-1)

Sexta iteración celda(X 6,5; X 1,2)+ (- celda(X 8,5; X 1,2))* celda(X 6,5; X 8,5)= nueva celda(X 6,5; X 1,2) (0)+ (- (0))* (1)= nueva celda(0)


Sexta iteración celda(X 6,5; X 1,4)+ (- celda(X 8,5; X 1,4))* celda(X 6,5; X 8,5)= nueva celda(X 6,5; X 1,4) (0)+ (- (-1))* (1)= nueva celda(1)

Sexta iteración fila pivote= A 5 1

Sexta iteración celda(X 6,5; A 6)+ (- celda(X 8,5; A 6))* celda(X 6,5; X 8,5)= nueva celda(X 6,5; A 6) (-1)+ (- (0))* (1)= nueva celda(-1)



80



Sexta iteración celda(X 6,5; A 9)+ (- celda(X 8,5; A 9))* celda(X 6,5; X 8,5)= nueva celda(X 6,5; A 9) (0)+ (- (0))* (1)= nueva celda(0)

Sexta iteración celda(X 6,5; Z)+ (- celda(X 8,5; Z))* celda(X 6,5; X 8,5)= nueva celda(X 6,5; Z) (-0.015)+ (- (1999.915))* (1)= nueva celda(-1999.93)




Sexta iteración celda(X 8,5; X 1,4)+ (- celda(X 8,5; X 1,4))* celda(X 8,5; X 8,5)= nueva celda(X 8,5; X 1,4) (-1)+ (- (-1))* (1)= nueva celda(0)






Sexta iteración celda(X 8,5; Z)+ (- celda(X 8,5; Z))* celda(X 8,5; X 8,5)= nueva celda(X 8,5; Z) (1999.915)+ (- (1999.915))* (1)= nueva celda(0)

Sexta iteración celda(A 5; A 1)+ (- celda(X 8,5; A 1))* celda(A 5; X 8,5)= nueva celda(A 5; A 1) (0)+ (- (1))* (1)= nueva celda(-1)

Sexta iteración celda(A 5; X 1,2)+ (- celda(X 8,5; X 1,2))* celda(A 5; X 8,5)= nueva celda(A 5; X 1,2) (0)+ (- (0))* (1)= nueva celda(0)

Sexta iteración celda(A 5; X 2,3)+ (- celda(X 8,5; X 2,3))* celda(A 5; X 8,5)= nueva celda(A 5; X 2,3) (0)+ (- (0))* (1)= nueva celda(0)

Sexta iteración celda(A 5; X 1,4)+ (- celda(X 8,5; X 1,4))* celda(A 5; X 8,5)= nueva celda(A 5; X 1,4) (0)+ (- (-1))* (1)= nueva celda(1)


81



Sexta iteración celda(A 5; A 6)+ (- celda(X 8,5; A 6))* celda(A 5; X 8,5)= nueva celda(A 5; A 6) (0)+ (- (0))* (1)= nueva celda(0)



Sexta iteración celda(A 5; A 9)+ (- celda(X 8,5; A 9))* celda(A 5; X 8,5)= nueva celda(A 5; A 9) (0)+ (- (0))* (1)= nueva celda(0)

Sexta iteración celda(A 5; Z)+ (- celda(X 8,5; Z))* celda(A 5; X 8,5)= nueva celda(A 5; Z) (0)+ (- (1999.915))* (1)= nueva celda(-1999.915)



Figura 5.25 Sexta iteración (Fuente: recopilación propia)

82





Tabla 5.11 Cálculos para la séptima iteración




Séptima iteración celda(X 6,9; A 1)+ (- celda(X 8,9; A 1))* celda(X 6,9; X 8,9)= nueva celda(X 6,9; A 1) (0)+ (- (1))* (1)= nueva celda(-1)

Séptima iteración celda(X 6,9; X 1,2)+ (- celda(X 8,9; X 1,2))* celda(X 6,9; X 8,9)= nueva celda(X 6,9; X 1,2) (0)+ (- (0))* (1)= nueva celda(0)


Séptima iteración celda(X 6,9; X 1,4)+ (- celda(X 8,9; X 1,4))* celda(X 6,9; X 8,9)= nueva celda(X 6,9; X 1,4) (0)+ (- (-1))* (1)= nueva celda(1)


Séptima iteración celda(X 6,9; A 6)+ (- celda(X 8,9; A 6))* celda(X 6,9; X 8,9)= nueva celda(X 6,9; A 6) (-1)+ (- (0))* (1)= nueva celda(-1)



Séptima iteración fila pivote= A 9 1

Séptima iteración celda(X 6,9; Z)+ (- celda(X 8,9; Z))* celda(X 6,9; X 8,9)= nueva celda(X 6,9; Z) (-0.015)+ (- (1999.915))* (1)= nueva celda(-1999.93)

83

Tabla 5.11 Cálculos para la séptima iteración (Continuación)


Séptima iteración celda(X 8,9; A 1)+ (- celda(X 8,9; A 1))* celda(X 8,9; X 8,9)= nueva celda(X 8,9; A 1) (1)+ (- (1))* (1)= nueva celda(0)



Séptima iteración celda(X 8,9; X 1,4)+ (- celda(X 8,9; X 1,4))* celda(X 8,9; X 8,9)= nueva celda(X 8,9; X 1,4) (-1)+ (- (-1))* (1)= nueva celda(0)


Séptima iteración celda(X 8,9; A 6)+ (- celda(X 8,9; A 6))* celda(X 8,9; X 8,9)= nueva celda(X 8,9; A 6) (0)+ (- (0))* (1)= nueva celda(0)




Séptima iteración celda(X 8,9; Z)+ (- celda(X 8,9; Z))* celda(X 8,9; X 8,9)= nueva celda(X 8,9; Z) (1999.915)+ (- (1999.915))* (1)= nueva celda(0)

Séptima iteración celda(A 9; A 1)+ (- celda(X 8,9; A 1))* celda(A 9; X 8,9)= nueva celda(A 9; A 1) (0)+ (- (1))* (1)= nueva celda(-1)

Séptima iteración celda(A 9; X 1,2)+ (- celda(X 8,9; X 1,2))* celda(A 9; X 8,9)= nueva celda(A 9; X 1,2) (0)+ (- (0))* (1)= nueva celda(0)


Séptima iteración celda(A 9; X 1,4)+ (- celda(X 8,9; X 1,4))* celda(A 9; X 8,9)= nueva celda(A 9; X 1,4) (0)+ (- (-1))* (1)= nueva celda(1)


Séptima iteración celda(A 9; A 6)+ (- celda(X 8,9; A 6))* celda(A 9; X 8,9)= nueva celda(A 9; A 6) (0)+ (- (0))* (1)= nueva celda(0)



84

Tabla 5.11 Cálculos para la séptima iteración (Continuación)



Séptima iteración celda(A 9; Z)+ (- celda(X 8,9; Z))* celda(A 9; X 8,9)= nueva celda(A 9; Z) (0)+ (- (1999.915))* (1)= nueva celda(-1999.915)

Séptima iteración celda(Solución; A 1)+ (- celda(X 8,9; A 1))* celda(Solución; X 8,9)= nueva celda(Solución; A 1) (1)+ (- (1))* (1)= nueva celda(0)

Séptima iteración celda(Solución; X 1,2)+ (- celda(X 8,9; X 1,2))* celda(Solución; X 8,9)= nueva celda(Solución; X 1,2) (0)+ (- (0))* (1)= nueva celda(0)


Séptima iteración celda(Solución; X 1,4)+ (- celda(X 8,9; X 1,4))* celda(Solución; X 8,9)= nueva celda(Solución; X 1,4) (0)+ (- (-1))* (1)= nueva celda(1)


Séptima iteración celda(Solución; A 6)+ (- celda(X 8,9; A 6))* celda(Solución; X 8,9)= nueva celda(Solución; A 6) (0)+ (- (0))* (1)= nueva celda(0)




Séptima iteración celda(Solución; Z)+ (- celda(X 8,9; Z))* celda(Solución; X 8,9)= nueva celda(Solución; Z) (2000)+ (- (1999.915))* (1)= nueva celda(0.085)



85

Figura 5.26 Séptima iteración






Tabla 5.12 Cálculos para la octava iteración




Octava iteración celda(X 3,6; A 1)+ (- celda(X 3,6; A 1))* celda(X 3,6; X 3,6)= nueva celda(X 3,6; A 1) (1)+ (- (1))* (1)= nueva celda(0)

86

Tabla 5.12 Cálculos para la octava iteración (Continuación)


Octava iteración celda(X 3,6; X 1,2)+ (- celda(X 3,6; X 1,2))* celda(X 3,6; X 3,6)= nueva celda(X 3,6; X 1,2) (-1)+ (- (-1))* (1)= nueva celda(0)

Octava iteración celda(X 3,6; X 2,3)+ (- celda(X 3,6; X 2,3))* celda(X 3,6; X 3,6)= nueva celda(X 3,6; X 2,3) (-1)+ (- (-1))* (1)= nueva celda(0)

Octava iteración celda(X 3,6; X 1,4)+ (- celda(X 3,6; X 1,4))* celda(X 3,6; X 3,6)= nueva celda(X 3,6; X 1,4) (0)+ (- (0))* (1)= nueva celda(0)


Octava iteración fila pivote= A 6 1




Octava iteración celda(X 3,6; Z)+ (- celda(X 3,6; Z))* celda(X 3,6; X 3,6)= nueva celda(X 3,6; Z) (1999.9128)+ (- (1999.9128))* (1)= nueva celda(0)

Octava iteración celda(X 6,5; A 1)+ (- celda(X 3,6; A 1))* celda(X 6,5; X 3,6)= nueva celda(X 6,5; A 1) (-1)+ (- (1))* (-1)= nueva celda(0)

Octava iteración celda(X 6,5; X 1,2)+ (- celda(X 3,6; X 1,2))* celda(X 6,5; X 3,6)= nueva celda(X 6,5; X 1,2) (0)+ (- (-1))* (-1)= nueva celda(-1)


Octava iteración celda(X 6,5; X 1,4)+ (- celda(X 3,6; X 1,4))* celda(X 6,5; X 3,6)= nueva celda(X 6,5; X 1,4) (1)+ (- (0))* (-1)= nueva celda(1)


Octava iteración fila pivote= A 6 -1




87



Octava iteración celda(X 6,5; Z)+ (- celda(X 3,6; Z))* celda(X 6,5; X 3,6)= nueva celda(X 6,5; Z) (-1999.93)+ (- (1999.9128))* (-1)= nueva celda(-0.0172)

Octava iteración celda(X 6,9; A 1)+ (- celda(X 3,6; A 1))* celda(X 6,9; X 3,6)= nueva celda(X 6,9; A 1) (-1)+ (- (1))* (-1)= nueva celda(0)





Octava iteración fila pivote= A 6 -1




Octava iteración celda(X 6,9; Z)+ (- celda(X 3,6; Z))* celda(X 6,9; X 3,6)= nueva celda(X 6,9; Z) (-1999.93)+ (- (1999.9128))* (-1)= nueva celda(-0.0172)

Octava iteración celda(A 6; A 1)+ (- celda(X 3,6; A 1))* celda(A 6; X 3,6)= nueva celda(A 6; A 1) (0)+ (- (1))* (1)= nueva celda(-1)

Octava iteración celda(A 6; X 1,2)+ (- celda(X 3,6; X 1,2))* celda(A 6; X 3,6)= nueva celda(A 6; X 1,2) (0)+ (- (-1))* (1)= nueva celda(1)

Octava iteración celda(A 6; X 2,3)+ (- celda(X 3,6; X 2,3))* celda(A 6; X 3,6)= nueva celda(A 6; X 2,3) (0)+ (- (-1))* (1)= nueva celda(1)

Octava iteración celda(A 6; X 1,4)+ (- celda(X 3,6; X 1,4))* celda(A 6; X 3,6)= nueva celda(A 6; X 1,4) (0)+ (- (0))* (1)= nueva celda(0)


Octava iteración fila pivote= A 6 1

88






Octava iteración celda(A 6; Z)+ (- celda(X 3,6; Z))* celda(A 6; X 3,6)= nueva celda(A 6; Z) (0)+ (- (1999.9128))* (1)= nueva celda(-1999.9128)



Figura 5.27 Octava iteración


89

Ya que la fila de la función objetivo no tiene valores positivos en la parte de las variables “X” se dice que se obtiene la matriz con solución óptima, encerradas en

color azul figura 5.28; donde la solución óptima del problema corresponde a la celda solución de la función objetivo encerrado en color verde, la cual también

corresponde al tiempo de distribución; la ruta de distribución se encuentra en la relación de los números unos de la columna de solución y la columna de la letra Z

encerrados en color rojo.

Figura 5.28 Matriz solución óptima del problema


Con los valores encerrados en rojo obtenidos en la figura 5.28 se puede trazar la ruta más corta del nodo 1 al nodo 9, donde X1,4, nos indica que hay que ir del

nodo 1 al nodo 4, X4,7, nos indica que después iremos del nodo 4 al nodo 7, X7,8 que iremos del nodo 7, al nodo 8, y por ultimo X8,9, nos indica que iremos del

nodo 8, al nodo 9, esta ruta se representa gráficamente, con flechas color azul en la figura 5.29.

90

Figura 5.29 ruta óptima


El tiempo en cruzar del nodo 1 al nodo 4 (X1,4) es de 0.04, el tiempo en cruzar del nodo 4 al nodo 7 (X4,7) es de 0.015, el tiempo en cruzar del nodo 7 al nodo 8

(X7,8) es de 0.015, el tiempo en cruzar del nodo 8 al nodo 9 (X8,9) es de 0.015; dando un tiempo total de 0.085, esta operación se expresa en la tabla 5.13.

91

Tabla 5.13 Tiempo de ruta optima


Variables X Nodo inicial Nodo final Tiempos

X1,4 Nodo 1 Nodo 4 0.04

X4,7 Nodo 4 Nodo 7 0.015

X7,8 Nodo 7 Nodo 8 0.015

X8,9 Nodo 8 Nodo 9 0.015

Tiempo total: 0.085

5.7 Recopilación de datos secundarios

Para poder obtener el valor del tiempo para estacionarse del camión repartidor, en

la figura 5.1, se realizó una inspección estacionando un carro en el horario de

reparto que abarca de 7 de la mañana a 4 de la tarde, por lo que se le asignó un

valor aproximado dividiéndolo en zonas; los diferentes tiempos para estacionar

del camión repartidor se pueden apreciar, en la tabla 5.14.

Tabla 5.14 Tiempos para estacionarse por zona.


Tipo de zona Tiempo

Zona Centro 5 minutos

Zona intermedia 2.5 minutos

Zona superior 1 minutos

El mapa se divide en 3 zonas como se puede apreciar en la figura 5.30, la zona

centro que esta coloreada con el color rojo está conformada por todo el bloque

interior que abarca la 3 Norte, 4 Sur, 2 Poniente y 5 Oriente; la zona intermedia

color verde está formada por toda el bloque interior que abarca la 9 Norte, 9 Sur, 9

Poniente y 9 Oriente, sin tomar en cuenta la Zona centro; y la zona superior color

azul es todo el mapa restante a las dos zonas antes mencionadas.

92

Figura 5.30 Tiempo para estacionarse por zona


El tiempo de entrega del pedido, es el tiempo en que el repartidor tarda en surtir el

pedido por tienda, este tiempo incluye el tiempo de entrega del producto a la

tienda, el tiempo que puede esperar el repartidor en lo que el empleado de la

tienda lo atiende y el tiempo de cobro del repartidor; estos tiempos para todas las

tiendas son muy aproximados por lo que se manejó un tiempo estándar, el cual es

de 7.5 minutos.

5.8 Programación de datos secundarios

Al darle clic al nodo inicial y la tienda, la computadora suma el tiempo para

estacionarse del camión de reparto, más el tiempo de entrega del pedido, más el

tiempo mínimo del nodo inicial al nodo que se encuentre antes de la tienda, a esta

suma de tiempos se le llama tiempo de reparto a tienda.

93

5.9 Monitoreo y control

Tomando en cuenta que solo se realizó una muestra de 3 observaciones dentro de

un carro, y que estas se realizaron en todo lo conformado por la figura 5.1,

obteniendo un tiempo promedio por zona; la variación ente el tiempo arrojado por

el sistema y el tiempo real puede ser alta.

Por lo cual se monitoreara cada 3 meses el sistema dado a la empresa,

modificando los tiempos de la tabla principal a la cual la computadora le realiza las

interacciones e iteraciones de programación lineal que tengan altas variaciones

con los tiempos reales, para que los tiempos arrojados por el sistema sean más

confiables.

Capítulo 6

Conclusiones y

recomendaciones

95

6.1 Conclusiones

Un sistema a computadora que utilice programación lineal ayudará a la creación

de rutas de distribución de una manera científica, arrojando tiempos de reparto a

tiendas, los cuales se conforman de la suma del tiempo para estacionarse del

camión de reparto, más el tiempo de entrega del pedido y el tiempo de recorrido

del nodo origen al nodo que se encuentre antes de la tienda (nodo destino).

Imprimiendo en forma de lista y en celdas la ruta de reparto, el tiempo total, el

tiempo de cada uno de los lados de las cuadras, y la dirección de estas.

Obteniendo como beneficios, una mayor confiabilidad en las rutas de reparto

elaboradas, ya que se está implementando un método estadístico y no empírico

como el que normalmente se utiliza; se manejara mayor confiabilidad en los

cálculos de los tiempos de las rutas de reparto, donde los cálculos son realizados

por la computadora mediante programación, disminuyendo errores al momento de

obtener los resultados.

Se observa una disminución del tiempo dedicado en la elaboración de las rutas de

reparto, teniendo un tiempo promedio de 30 segundos para obtener los datos

impresos por la computadora del nodo fuente al nodo destino; cualquier persona

que sepa manejar una computadora y que reciba una capacitación mínima del

programa podrá crear las rutas de distribución, esto se logra mediante una interfaz

dinámica y fácil de utilizar.

Se tendrá un programa que se pueda actualizar fácilmente, ya que si el usuario

quiere modificar los tiempos, incrementar los nodos o calcular los valores de otra

zona, solo tiene que interactuar con una tabla de tiempo la cual es fácil de

interpretar, crear y modificar; una disminución en los tiempos de reparto, esto se

obtiene mediante el método de investigación de operaciones utilizado en este

96

proyecto (programación lineal) la cual es orientada a obtener la ruta más corta

entre dos nodos del grafo valorado.

Disminución en los gastos de gasolina; este proyecto obtiene la ruta con el tiempo

menor de recorrido, donde este recorrido tiende a ser una distancia corta, por lo

que el carro también tiende a utilizar menor gasolina que en las rutas normalmente

utilizadas.

Por último, programación lineal se puede utilizar para resolver diversos problemas

matemáticos, en este caso se implementa para obtener la ruta más corta, pero

existen algoritmos enfocados en rutas (algoritmo de Floyd, algoritmo de Dijkstra,

etc.), los cuales son más especializados en la creación de rutas optimas; pero

programación lineal es el primer paso para poder aplicar lógica difusa en un

problema; donde los valores difusos dan mayor certeza al resultado de

programación lineal.

Ya que este proyecto se retomará aplicando lógica difusa para la creación de

tiempos difusos de los lados de las cuadras; es fundamental que este problema se

haya abordado utilizado el método de programación lineal; brindando como

beneficio en el futuro mayor confiabilidad en los tiempos.

Como conclusión este proyecto no solo brinda múltiples beneficios y comodidades

a la empresa, como mayor control en los repartos, disminución en los tiempos de

capacitación, ahorro de dinero, etc., si no que también da margen a una mejora

tanto en el software como en los datos, lo cual lo hace un proyecto atractivo para

las empresas, como para los investigadores.

97

6.2 Recomendaciones

Ya que los tiempos calculados que se procesan en las iteraciones e interacciones

de programación lineal se obtuvieron mediante muestras de 3 observaciones, que

se realizaron en todo lo conformado por la figura 5.1, la variación entre el tiempo

arrojado por el sistema y el tiempo real pueden ser altas, por los cual se

recomienda que se tomen los valores arrojados como tiempos aproximados,

dando un tiempo de 10 minutos más menos de holgura.

Para poder disminuir este tiempo de holgura y brindar mayor confiabilidad en los

tiempos arrojados por el sistema, se monitoreara cada 3 meses el software dado a

la empresa, modificando los tiempos de la tabla principal a la cual la computadora

le realiza las iteraciones e interacciones de programación lineal que tenga alta

variaciones con los tiempos reales, y de esta manera los tiempos arrojados por el

sistema se volverán más confiables.

Para una mejora en el proyecto se recomienda:

Aumentar la zona de aplicación de programación lineal para que las rutas

tengan más opciones alternas y de tiempos más cortos, también de esta

manera le será más útil a la empresa al tener más rango en la zona de

trabajo del software

Creación de rutas conformadas de tiempos dinámicos; como antes se

mencionó el tiempo de las rutas es un tiempo promedio lo cual maneja una

baja confiabilidad, esto se puede resolver mediante la creación de tablas de

tiempos según la hora

Mejorar la interfaz creando el software mediante un compilador profesional,

ya que la programación de este software se creó sobre el compilador de un

programa matemático lo cual consume más memoria y maneja una

presentación con opciones que no utiliza el programa

98

Creación de librerías las cuales solo contengan las ecuaciones y requisitos

que necesite el programa, esto disminuirá el peso de software causado por

las librerías generales

Manejar un sistema operativo más seguro, ya que el utilizado es propenso a

jaquear (Microsoft), teniendo como recomendación Linux

Encontrar una forma más productiva de realizar la recolección de datos,

dando como propuestas la implementación de un micro-controlador el cual

obtenga el tiempo de los lados de las cuadras y lo almacene en la tabla de

tiempos mediante un puerto serial, o la recolección de datos utilizando

GPS.

Implementar métodos estadísticos para la creación de nuevos tiempos sin

necesidad de la recolección de datos, mediante el análisis de tiempos

existentes, proponiendo lógica difusa como una opción; esto brindara mayor

confiabilidad en los tiempos de reparto.

99

Bibliografía

[01] Areola Jesús S. (2003). Programación lineal: una introducción a la toma de

decisiones. Serie Thomson, México.

[02] Bronson Richard. (1983). Investigación de operaciones. Serie schaum-

Mcgraw hill, México.

[03] Eppen G.D. (2000). Investigación de operaciones en la ciencia administrativa.

Prentice may, México.

[04] Hillier Frederick S. (2006). Introducción a la investigación de operaciones.

McGraw-Hill, México.

[05] Ríos Insua Sixto. (1998). Programación lineal y aplicaciones. Alfaomega

Grupo Editor, Colombia.

[06] Taha Hamdy A. (2003). Investigación de operaciones. Pearson educación,

México.

[07] Wackerly Denis. (2010). Estadística matemáticas con aplicaciones. Cengage

learning, México.

[08] Winston Wayne L. (2005). Investigación de operaciones aplicaciones y

algoritmos. Thomson Editores, México.

[09] Corona Nakamura María A. (2011). Diseño de algoritmos y su codificación en

c. Mc Graw Hill, México.

100

Anexos

Anexo A Tabla de tiempos por lado de la cuadra

A continuación se muestran todos los cálculos del tiempo es el que el camión repartidos recorre los lados de las cuadras

de nodo a dodo, en la tabla A.1.

Tabla A.1 Tiempo total por lado de la cuadra


Nodo 1 A nodo Km Zona Tiempo parcial Tipo de esquina Tiempo total

nodo 2 0.1Km 45Km/h 8 Segundos 50 Segundos 58 Segundos


Nodo 1 0.1Km 45Km/h 8 Segundos 5 Segundos 13 Segundos








101





















102



















Nodo 18 0.1Km 35Km/h 10 Segundos 7.5 Segundos 17.5 Segundos


103




/// /// /// /// /// ///

















104





















105





















106





















107





















108





















109





















110





















111





















112





















113





















114





















115





















116





















117





















118





















119





















120






Nodo 121 0.1Km 45Km/h 8 Segundos 5 Segundos 13Segundos















121





















122





















123





















124





















125





















126


Nodo 165 0.025Km 35Km/h 2.5 Segundos 10 Segundos 12.5 Segundos



















127





















128





















129





















130





















131





















132





















133





















134





















135





















136





















137





















138





















139





















140





















141





















142





















143





















144





















145




Anexo B Manual técnico

El manual técnico es la explicación de la programación del software de distribución, el cual aplica programación lineal,

esta programación se explicará mediante un diagrama de flujo el cual se dividió para facilitar su explicación, para poder

comprender con mayor facilidad este diagrama de flujo en su contenido se mostrará los términos y sus explicaciones, las

cuales se utilizan en la programación, tabla B.1.

Tabla B.1 Terminología


Términos Explicación

s Ancho de la matriz más uno

f Numero de variables x más uno

g Numero de variables básicas "A"

h Ancho de la matriz

v Largo de la matriz

q Largo de la tabla inicial

146

ni Nodo fuente

nf Nodo destino

Hoja1 Hoja donde se imprime las interacciones,

controladas por iteraciones y decisiones

de programación lineal

Hoja2 Hoja donde se encuentran los valores de

la tabla de tiempos

Celda() Casilla que es parte de una tabla o

matriz

También para facilitar la comprensión de las figuras que componen al diagrama de

flujo, se puede consultar la tabla 3.6, donde se explica la función de las figuras en

el diagrama de flujo; a continuación se explica cada una de las figuras que

componen al diagrama de flujo.

En la figura B.1, primero se realiza dos iteraciones (for) las cuales tienen el

tamaño de los valores de la matriz, dentro de estas iteraciones se imprime cero, lo

cual hace que se imprima ceros en toda la matriz 1.

Después se realizan 6 acciones la primera es imprimir la letra M en su celda

correspondiente, después se imprime la letra Z en su celda correspondiente, en el

siguiente paso la variable “ni” toma el valor del nodo fuente, a continuación se

imprime un “-1” en la celda correspondiente del nodo fuente, como penúltima

acción “nf” toma el valor del nodo destino y por último se imprime 1 en la celda del

nodo destino.

En la figura B.2 se realiza el escaneo de la tabla de tiempos que se encuentran en

la hoja 2 e impresión de estos valores en la matriz 1, las primeras dos iteraciones

(for) corresponden al tamaño de la tabla de tiempos, donde el primer comando

decisión (if) encuentra el número de i que son iguales a celda (j,2) de Hoja2,

147

dentro de esta decisión primero se realizan tres acciones, la primera en la celda

(i+1, 1) de Hoja1, imprime el encabezado de las variables básica “A” con el

número de la celda (j,2) de Hoja2, correspondiente a la columna de variables

básicas “A” de la matriz1.

En la segunda acción, en la celda (1, 1+f) de Hoja1, imprime el encabezado de las

variables básica “A” con el número de la celda (j,2) de Hoja2, correspondiente a la

fila de variables básicas “A” de la matriz1; en la última acción de la celda (2+g, i+f)

de Hoja1, imprime el valor de -1, el cual corresponde a la relación de las variables

básicas “A” en la fila de M de la matriz1; después el programa entra a otra

iteración (for), la cual se cicla según la cantidad de celdas que conforme el tamaño

de la tabla de tiempos.

Adentro de la iteración se encuentra un comando decisión (if) que encuentra un

cero en la celda (k, 2) de Hoja2, realiza 5 acciones, la primera acción imprime el

encabezado de las variables “X” con sus correspondientes nodo fuente y nodo

destino, separados por una coma (,); después imprime los valores de los tiempos

en la fila de la función objetivo multiplicados por menos (-); como siguiente acción

el valor del nodo destino de las variables “X” es guardado en la variable “m”.

Como penúltima acción se imprime -1 en cada celda correspondiente a la variable

“X” en relación al nodo fuente y por último se imprime 1 en cada celda

correspondiente a la variable “X” en relación al nodo destino; después de estas

acciones se encuentra un comando decisión (if) el cual identifica si hay algún

número diferente a cero en la celda (k, 2) de Hoja2, al encontrar algún cero se

ejecuta la acción k=q la cual para la iteración (for), que a su vez regresa a la

iteración (for) que le antecede y esta entra a la acción j=9 la cual también detiene

esta iteración y regresa a la primera iteración (for) de esta figura.

En la figura B.3 comienza con dos iteraciones (for) las cuales tienen el tamaño de

los valores de la matriz, esta iteraciones tienen dos acciones, la primera almacena

148

los valores de la matriz 1 en la variable a (i, j) y la segunda imprime estos valores

en la siguiente matriz que denominaremos matriz2.

Al terminar los ciclos el programa entra a otra iteración (for) la cual tiene la

duración según las celdas que compongan el ancho de las matrices, dentro de

esta se encuentra un comando de decisión (if) examina si se encuentra un menos

uno (-1) en la celda (i, v) de hoja1 correspondiente a los valores de la derecha o

última columna del lado derecho de la matriz2, esto nos sirve para identificar la fila

correspondiente al nodo fuente, esta se guarda en una acción donde el valor de la

variable “i” se guara en la variable “o” (o= i).

Al finalizar este ciclo el programa entra a otra iteración (for) la cual tiene la

duración según las celdas que compongan el largo de las matrices, dentro de esta

se encuentra la acción que imprime la multiplicación de la fila del nodo fuente por

el valor menos uno (-1), eso se realiza para restablecer la fila ya que no pueden

haber valores negativos en los valores de la derecha o última columna del lado

derecho de la matriz2.

Por ultimo al finalizar este ciclo el programa entra a otra iteración (for) la cual tiene

la duración según las celdas que compongan el número de variables básicas “A”,

dentro de esta se encuentra la acción que imprime el número uno (1), estos

conforman una diagonal o matriz identidad.

La figura B.4 comienza con dos iteraciones (for) las cuales tienen el tamaño de

los valores de la matriz, esta iteraciones tienen dos acciones, la primera almacena

los valores de la matriz2 en la variable a (i, j) y la segunda imprime estos valores

en la siguiente matriz que denominaremos matriz3.

Al terminar los ciclos el programa realiza una acción para darle a la variable “x” el

valor de cero (0), después ingresa a otras dos iteración (for) las cuales tienen el

149

tamaño de los valores de las matrices, dentro de estas se realizan cuatro

acciones.

Las primeras dos acciones corresponden a la primera iteración, donde en la

primera acción se suman todos los valores de cada columna correspondientes a

las variables básicas “A”, y se guardan en la segunda acción con la variable “x”, al

salir de esta primera iteración la acción siguiente imprime la suma en cada celda

correspondiente a la fila de “M”, por último x toma el valor de cero para volver a

realizar la sumatoria de la siguiente columna.

En la figura B.5 comienza con una iteración (for) la cual tiene la duración según las

celdas de los valores que compongan el largo de las matrices, dentro de esta se

encuentra la acción que almacena la fila de “M” de la matriz3.

Al finalizar este ciclo el programa entra a otra iteración (for) la cual tiene la

duración según las celdas de los valores que compongan el largo de las matrices,

dentro de esta se encuentra la acción que almacena la función objetivo o fila de

“Z” de la matriz3.

Por ultimo al finalizar este ciclo el programa entra a otra iteración (for) la cual tiene

la duración según las celdas de los valores que compongan el largo de las

matrices, dentro de esta se encuentra la acción que imprime a(2, j)+ a(1, j)* 1000

en cada una de las celdas de los valores de la fila “Z” o función objetico, esta

acción realiza el restablecimiento de las variables básicas “A” de la técnica de la

“M” de programación lineal.

En la figura B.6 se empezara a realizarlos procesos de iteraciones, decisiones e

acciones de la técnica de la M, los cuales denominaremos matrices de iteraciones,

para realizar la matriz de iteración 1 primero el programa entra a una iteración

general (for) la cual tiene el número de 70 ciclos, y cada iteración que realiza crea

150

una nueva matriz de iteración, mediante sus iteraciones, decisiones y acciones

internas.

Estas comienzan con una iteración (for) la cual tiene la duración según la cantidad

de variables “X” más uno, y j= 2 para solo tomar valores, dentro de esta se

encuentra la acción que almacena la fila de “M” de la matriz3; al finalizar este ciclo

el programa entra a otra iteración (for) la cual tiene la duración según la cantidad

de variables “X” más uno, y j= 2 para solo tomar valores, dentro de esta se

encuentra la acción que almacena la función objetivo o fila de “Z” de la matriz3.

Después en programa entra a una acción donde m= 2 esto nos sirve para poder

comparar dos valores diferentes más adelante; terminando esta acción el

programa entra a otra iteración (for) la cual tiene la duración según la cantidad de

variables “X” más uno, y j= 2 para solo tomar valores.

Dentro de esta se encuentra un comando decisión (if) el cual se compara si a(1,

m) es menor que (<) a(1, j), esto nos sirve para encontrar el valor más grande las

variables de “X” de la fila “M” y al encontrarlo almacenarlo en la acción m= j; a

continuación se ejecuta un comando decisión (if) donde se compara si a(1, m) es

igual (=) a a(1, j), y si se llegara a encontrar algún valor igual se realiza otro

comando decisión (if) el cual compara si a(2, m) es menor que (<) a(2, j), y al

encontrarlo almacenarlo en la acción m= j.

Esto nos sirve para que en dado caso si se llegara a encontrar alguna variable “X”

igual a otra en la fila de “M”, se pueda romper la decisión verificando cual el la

variable menor de la fila “Z” correspondiente, de esta manera sabremos cual

variable “X” en la fila de “Z” es mayor, y de esta manera identificar nuestra

columna pivote mediante la variable “m”.

A continuación el programa entra a una iteración (for) la cual tiene la duración

según la cantidad de variables básicas “A”, dentro de esta se encuentra la acción

151

que almacena la columna de la variable “m” antes encontrada en el iteración

anterior, esta se guarda mediante la acción a(i, m) es igual (=) a celda (s+s+s-2-i,

m) de hoja 1.

Como siguiente paso se realiza una acción donde a la variable c(w, y) se le asigna

el valor de 1,000,000, esto nos servirá más adelante ya que necesitamos comprar

un valor con otro valor más grande, en este caso será c(w, y).

Como última parte de este pedazo del diagrama del flujo el programa ingresa a

una iteración (for) la cual tiene la duración según la cantidad de variables básicas

“A”, dentro de esta se encuentra un comando decisión (if) el cual encuentra que

números de las variables a(i, m) son mayores (>) que cero, ya que en el siguiente

paso dividiremos entre los valores de a(i, m) por lo cual necesitamos que no sean

ceros para no causar un error en el momento de realizar la ecuación.

Después se realiza la acción donde la variable c(i, m) es igual (=) a la división de

la celda (s+s+s-2-i, v) de hoja 1 (columna de solución de variables básicas “A”),

entre (/) la variable a(i, m); a continuación se realiza un comando decisión (if) el

cual encuentra si alguna variable c(i, m) es menor (<) que la variable c(w, y), en

dado caso de encontrarla se ejecuta la acción y=m y w=i, donde las variables “y” o

“m” corresponde a nuestra columna pivote y las variables “w” o “i” corresponde a

nuestra fila pivote.

En la figura B.7 comienza con una iteración (for) la cual tiene la duración según las

celdas que componen el ancho de la matriz, después entra a otra iteración (for) la

cual tiene la duración según las celdas que componen el largo de la matriz, estas

dos iteraciones tienen el tamaño de la matriz, dentro de esta se encuentra dos

acciones, la primera almacena los datos de la matriz3 en la variable a(i, j), y la

segunda acción imprime los valores de a(i, j) para crear la matriz de iteración 1,

esto nos sirve para imprimir los valores que se modifican por las interacciones del

método de la M sobre la vieja matriz.

152

A continuación se realizan tres acciones, la primera guarda en la variable c(1,1) la

celda (s+s+1, m) de Hoja 1, esta celda es nuestra variable “X” que entra; la

siguiente acción imprime en la ceda (s+s+s+s-2-w,1) de hoja 1 la variable c(1, 1),

esta celda donde se imprime es la celda correspondiente a la variable básica “A”

de salida; la tercera acción guarda en la variable “r” la interacción donde se suma

el número de variables básicas “A” más (+) el número 1, menos (-) w (valor de la

fila pivote), esto nos sirve para poder convertir el valor de nuestra fila pivote a un

valor que pueda interpretar las iteraciones.

Después el programa entra a una iteración (for) la cual tiene la duración de la

variable “r”, después entra a otra iteración (for) la cual tiene la duración según las

celdas que componen el largo de la matriz, esta dos iteraciones comienzan en la

parte superior horizontal de la matriz hasta una fila antes de la fila pivote.

Dentro de esta se encuentra una accione en la que la celda (s+s+s+i, j) de hoja 1

toma el valor de a(i, j) (cela vieja a modificar) más (+) el valor inverso de a(i, m)

(valor de la columna pivote) multiplicado (*) por a(s-2-w, j) (valor de la fila pivote),

estas interacciones crean los valor de la matriz de iteración 1, mediante el método

de la M.

Como siguiente paso el programa entra a una iteración (for) la cual comienza con

el valor de “r+2” hasta la cantidad de las celdas que componen el ancho de la

matriz, después entra a otra iteración (for) la cual tiene la duración según las

celdas que componen el largo de la matriz, esta dos iteraciones comienzan una

celda debajo de la fila pivote hasta la fila final de la matriz.

Dentro de esta se encuentra una accione en la que la celda (s+s+s+i, j) de hoja 1

toma el valor de a(i, j) (cela vieja a modificar) más (+) el valor inverso de a(i, m)

(valor de la columna pivote) multiplicado (*) por a(s-2-w, j) (valor de la fila pivote),

153

estas interacciones crean los valor de la matriz de iteración 1, mediante el método

de la M.

Al terminar este ciclo el programa regresa al ciclo general el cual se puede

ejecutar 70 veces; al repetir las iteraciones, comparaciones y acciones dentro de

este ciclo general se crean cada una de las matrices de iteración.

En la figura B.8 comienza con una iteración (for) la cual tiene la duración según el

número de valores “X” más (+) el número 1, dentro de esta se encuentra una

acción donde en la variable a(3, j) se almacena los valores que contienes la fila de

“M”, en la parte correspondiente a las variables “X”.

A continuación el programa entra a una acción donde la variable x toma el valor de

cero, enseguida pasa a una iteración (for) la cual tiene la duración según el

número de valores “X” más (+) el número 1; dentro de esta se encuentra un

comando decisión (if) el cual identifica si la variable a(3, j) es igual (=) a cero (0),

de serlo la variable a(3, j) se vuelve uno (1); después hay otro comando decisión

(if) el cual identifica si la variable a(3, j) es igual (=) a menos dos (-2), de serlo la

variable a(3, j) se vuelve uno (1).

Como siguiente paso se realiza dos acciones, en la primera la variable b(j) toma

el valor de la variable x más (+) la variable a(3, j), y en la segunda la variable x

toma el valor de la variable b(j); estas dos acciones en combinación con la

iteración (for) crean un sumador donde se van sumando las veces que la variable

a(3, j) toma el valor de cero (0) y de menos dos (-2).

Después la programación ingresa a un comando decisión (if) el cual identifica si la

variable x es igual (=) al número de variables “X”; si este comando decisión es

verdad el programa accede a una iteración (for) la cual tiene la duración según la

cantidad de celdas que componga el ancho de la matriz, seguido de otra iteración

154

(for) la cual tiene la duración según la cantidad de celdas que componga el largo

de la matriz, estas dos iteraciones tienen el tamaño de la matriz.

Dentro de estas dos iteraciones se encuentran dos acciones la primera selecciona

toda la última matriz de iteración creada y la segunda acción la borra, esto se

realiza ya que la decisión anterior al ser verdad nos indica que ya se encontró la

solución del método de la “M”, en la matriz anterior a la última matriz de iteración,

por lo cual borramos la última matriz de iteración.

Al terminar las iteraciones, se realiza la última acción de programa, donde la

variable t toma el valor de 71, esto se realiza para detener la iteración (for)

general, ya que se encontró la solución del método de la “M” ya no se necesita

seguir creando más matrices de iteración; con esto se da por terminado el

programa y el diagrama de flujo.

155

Figura B.1 Relleno de ceros en la matriz 1


156

Figura B.2 Valores de la matriz 1


157

Figura B.3 Restableciendo fila de nodo fuente


158

Figura B.4 Restableciendo fila M


159

Figura B.5 Restableciendo variables básicas


160

Figura B.6 Encontrando los valores de la fila y columna pivote


161

Figura B.7 Interacciones e iteraciones de programación lineal


162

Figura B.8 Detener iteraciones


163

Anexo C Glosario de términos

Red: Una red consiste en el conjunto de puntos y un conjunto de líneas que unen

ciertos pares de puntos. Los puntos se llaman nodos (o vértices). Las líneas se

llaman arcos (o linda duras, aristas o ramas). Los arcos se etiquetan para dar

nombres a los nodos en sus puntos terminales, por ejemplo, AB es el arco entre el

nodo A y B.

Arco dirigido: Se dice que un arco es dirigido cuando el arco tiene flujo en una

dirección (como en una calle de un sentido). La dirección se indica agregando una

cabeza de flecha al final de línea que representa el arco. Al etiquetar un arco

dirigido con el nombre de los nodos que une, siempre se coloca primero el nodo

de donde viene y después el nodo a donde va, esto es un arco dirigido del nodo A

al nodo B debe etiquetarse como AB y no como BA.

Arco no dirigido: Si el flujo a través de un arco se permite en ambas direcciones

(como una tubería que se puede usar para bombear fluido en ambas direcciones),

se tiene que es un arco no dirigido. Para ayudar a distinguir entre los dos tipos de

arcos, con frecuencia se hará referencia a los arcos no dirigidos con el nombre de

ligadura. Aunque se permita que el flujo sea en ambas direcciones, se supone que

ese flujo será en una dirección y no se tendrán flujos simultáneos.

Trayectoria: Una trayectoria entre dos nodos es una sucesión de arcos distintos

que conectan esta sucesión de arcos OB-BD-DT. Cuando algunos o todos los

arcos de la red son arcos dirigidos, se hace la distinción entre trayectorias dirigidas

y trayectorias no dirigidas.

Trayectoria dirigida: Una trayectoria dirigida del nodo i al nodo j, es una sucesión

de arcos cuya dirección (si la tienen) es hacia el nodo j, de manera que el flujo del

nodo i al nodo j, a través de esta trayectoria es factible.

164

Trayectoria no dirigida: Una trayectoria no dirigida del nodo i al nodo j es una

sucesión de arcos cuya dirección (si la tienen) pueden ser hacia o desde el nodo j.

Con frecuencia alguna trayectoria no dirigida tendrá algunos arcos dirigidos hacia

el nodo j y otros desde él (es decir, hacia el nodo i).

Ciclo: Un ciclo es una trayectoria que comienza y termina en el mismo nodo.

Puede ser dirigida o no dirigida según si la trayectoria es dirigida o no dirigida.

Red conexa: Una red conexa es una red en la que cada par de nodos está

conectada.

Capacidad de arco: Es la cantidad máxima de flujo (quizás infinito) que pueda

circular en el arco dirigido.

Nodo fuente (nodo origen): tiene la propiedad de que el flujo que sale de los

nodos excede al flujo que entra al él.

Nodo demanda (nodo destino): es el caso contrario al nodo fuente, donde el flujo

que llega excede al que sale de él.

Nodo transbordo (nodo intermedio): satisface la conservación de flujo, es decir,

el flujo que entra es igual al nodo que sale.

Red dirigida: Es una red que solo tiene arcos dirigidos.

Red no dirigida: Es la red donde todos sus arcos son no dirigidos.

Documents

MODELO PARA LA SELECCIÓN DE RUTAS DE DISTRIBUCIÓN DE …