1 Investigacion de Operaciones

INVESTIGACIÓN DE OPERACIONES

La investigación operacional está al servicio del hombre de acción. Su propósito es el de

preparar la elección de éste entre diferentes medios o métodos disponibles para realizar todo

objetivo que se proponga, de modo que se optimice el resultado en relación a un cierto

criterio de juicio. Ciertamente, fundándose en la experiencia y la intuición es como cada uno

de nosotros asume las innumerables decisiones que implica la vida profesional o privada. Sin

embargo, algunas de entre ellas merecen un estudio más profundo, en razón de sus

consecuencias y de la complejidad de la situación en la cual se inscriben.

Podría verse uno de los primeros ejemplos históricos de la investigación operacional es la

misión confiada a Arquímedes por Hierón, tirano de Siracusa, de aplicar los mejores medios y

métodos para defender a la ciudad contra los ataques y el sitio de los romanos. Pero la

investigación operacional sólo se ha beneficiado de una aplicación sistemática en ocasión de

la segunda Guerra Mundial, principalmente en la conducción de las grandes operaciones

militares. La investigación operacional utiliza, en gran medida, a los ordenadores, y la

invención y comercialización de estas máquinas fueron la condición primordial de su

desarrollo en el dominio civil y especialmente en la economía de empresa. Por una feliz

coincidencia, sólo en nuestra época los problemas de gestión de las grandes empresas se

han convertido en irremediablemente complejos. Si bien es indispensable, para el técnico en

investigación de operacional, el estudiar los problemas generales que se presentan y los

algoritmos clásicos que permiten resolverlos, debe estar también totalmente persuadido de

que las situaciones prácticas que encontrará serán mucho más complicadas y que deberá

emprender una tarea original para dar satisfacción al encargado de tomar decisiones

ofreciéndole la posibilidad de optimizar según su propio criterio. Es necesario, pues, en

función de las motivaciones del responsable de la decisión que plantea un problema,

identificar los fenómenos a estudiar mediante un análisis profundo de la situación. Este

análisis se funda sobre la observación de la situación real, mediante conversaciones con los

hombres que participan en ella directamente y mediante acopio de datos estadísticos o

provisionales (resultantes de encuestas, de medidas o de estudios técnicos).

La investigación de operaciones puede definirse como un método científico de resolución de

problemas, la cual brinda las herramientas suficientes para que con base en abstracciones de

la realidad se puedan generar y resolver modelos matemáticos con el objetivo de elaborar un

análisis y concluir de los mismos para así poder sustentar cuantitativamente las decisiones

que se tomen respecto a la situación problema.

Bryan Antonio Salazar López

Otra de las muchas definiciones que de la investigación de operaciones se encuentran es la

siguiente:

"La Investigación de Operaciones es la aplicación, por grupos interdisciplinarios, del método

científico a problemas relacionados con el control de las organizaciones o sistemas a fin de

que se produzcan soluciones que mejor sirvan a los objetivos de toda organización."

Ackoff, R. L. y Sasieni M. W. Fundamentals of Operations Research, John Wiley & Sons,1968.

COMO ABORDAR UN PROBLEMA REAL DE OPTIMIZACIÓN?La Optimización puede considerarse como la búsqueda de la mejor solución (solución óptima)

de un problema. El término mejor aquí depende del contexto en el que se trabaje. Por

ejemplo, en un contexto operativo atinente a las utilidades la optimización del sistema

constituye la maximización de los resultados, todo lo contrario a los costos o las distancias,

casos en los cuales la optimización dependerá de la minimización de los resultados


MODELIZACIÓNUn modelo es una abstracción o una representación de la realidad o un concepto o una idea

con el que se pretende aumentar su comprensión, hacer predicciones y/o controlar/analizar

un sistema. Cuando el sistema no existe, sirve para definir la estructura ideal de ese sistema

futuro indicando las relaciones funcionales entre sus elementos. En la actualidad un modelo

se define como un constructo basado en nuestras propias percepciones pasadas y actuales;

la anterior representación puede ser holista o reduccionista.

Los modelos se pueden clasificar según su grado de abstracción en:

- Modelos Abstractos (no físicos)

- Modelos Concretos (físicos)

Y se pueden clasificar igualmente si son matemáticos en:

- Estáticos

- Dinámicos

- Determinísticos

- Estocásticos

Francisco Chediak - Ingeniero Industrial

PROGRAMACIÓN LINEALLa optimización basada en programación lineal corresponde a situaciones reales en las que

se pretende identificar y resolver dificultades para aumentar la productividad respecto a los

recursos (principalmente los limitados y costosos), aumentando así los beneficios.

Los resultados y el proceso de optimización se convierten en un respaldo cuantitativo de las

decisiones frente a las situaciones planteadas. Decisiones en las que sería importante tener

en cuenta diversos criterios administrativos como:

-Los hechos

-La experiencia

-La intuición

-La autoridad


¿COMO RESOLVER UN PROBLEMA MEDIANTE PROGRAMACIÓN LINEAL?EL PROBLEMA

La fábrica de Hilados y Tejidos "SALAZAR" requiere fabricar dos tejidos de calidad diferente T

y T’; se dispone de 500 Kg de hilo a, 300 Kg de hilo b y 108 Kg de hilo c. Para obtener un

metro de T diariamente se necesitan 125 gr de a, 150 gr de b y 72 gr de c; para producir un

metro de T’ por día se necesitan 200 gr de a, 100 gr de b y 27 gr de c.

El T se vende a $4000 el metro y el T’ se vende a $5000 el metro. Si se debe obtener el

máximo beneficio, ¿cuántos metros de T y T’ se deben fabricar?

El problema se recomienda leer en más de una ocasión para facilitar el

reconocimiento de las variables, además es muy recomendable la elaboración de

tablas o matrices que faciliten una mayor comprensión del mismo.PASO 1: "FORMULAR EL PROBLEMA"

Para realizar este paso partimos de la pregunta central del problema.

¿cuántos metros de T y T’ se deben fabricar?

Y la formulación es:

“Determinar la cantidad de metros diarios de tejido tipo T y T’ a fabricar teniendo en cuenta

el óptimo beneficio respecto a la utilidad”.PASO 2: DETERMINAR LAS VARIABLES DE DECISIÓN

Basándonos en la formulación del problema nuestras variables de decisión son:

XT: Cantidad de metros diarios de tejido tipo T a fabricar

XT’: Cantidad de metros diarios de tejido tipo T’ a fabricar PASO 3: DETERMINAR LAS RESTRICCIONES DEL PROBLEMA

En este paso determinamos las funciones que limitan el problema, estas están

dadas por capacidad, disponibilidad, proporción, no negatividad entre otras.

De disponibilidad de materia prima:

0,12XT + 0,2XT’ <= 500 Hilo “a”

0,15XT + 0,1XT’ <= 300 Hilo “b”

0,072XT + 0,027XT’ <= 108 Hilo “c”

De no negatividad

XT,XT’ >= 0PASO 4: DETERMINAR LA FUNCIÓN OBJETIVO

En este paso es de vital importancia establecer el contexto operativo del problema

para de esta forma determinar si es de Maximización o Minimización. En este caso

abordamos el contexto de beneficio por ende lo ideal es Maximizar.

Función Objetivo

ZMAX = 4000XT + 5000XT’PASO 5: RESOLVER EL MODELO UTILIZANDO SOFTWARE O MÉTODOS MANUALES

A menudo los problemas de programación lineal están constituidos por innumerables

variables, lo cual dificulta su resolución manual, es por esto que se recurre a software

especializado, como es el caso de WinQSB (disponible aquí), STORM (disponible aquí) o para

modelos menos complejos se hace útil la herramienta Solver de Excel.

El anterior ejercicio fue resuelto mediante Solver - Excel, y su resultado fue:


http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/descargas-y-mutimedia/


En la zona de descargas podrán encontrar diversos ejercicios de práctica, dado que es esta la

única garantía de aprendizaje. Cada ejercicio de programación lineal trae consigo nuevos

retos que requerirán de destreza matemática para su resolución.

MÉTODO GRÁFICO

El gráfico es un método de solución de problemas de programación lineal muy limitado en

cuanto al número de variables (2 si es un gráfico 2D y 3 si es 3D) pero muy rico en materia

de interpretación de resultados e incluso análisis de sensibilidad. Este consiste en

representar cada una de las restricciones y encontrar en la medida de lo posible el polígono

(poliedro) factible, comúnmente llamado el conjunto solución o región factible, en el cual por

razones trigonométricas en uno de sus vértices se encuentra la mejor respuesta (solución

óptima).

EL PROBLEMALa fábrica de Hilados y Tejidos "SALAZAR" requiere fabricar dos tejidos de calidad diferente T

y T’; se dispone de 500 Kg de hilo a, 300 Kg de hilo b y 108 Kg de hilo c. Para obtener un

metro de T diariamente se necesitan 125 gr de a, 150 gr de b y 72 gr de c; para producir un

metro de T’ por día se necesitan 200 gr de a, 100 gr de b y 27 gr de c.

El T se vende a $4000 el metro y el T’ se vende a $5000 el metro. Si se debe obtener el

máximo beneficio, ¿cuántos metros de T y T’ se deben fabricar?

LA MODELIZACIÓN MEDIANTE PROGRAMACIÓN LINEALVARIABLES

XT: Cantidad de metros diarios de tejido tipo T a fabricar

XT’: Cantidad de metros diarios de tejido tipo T’ a fabricar

RESTRICCIONES

0,12XT + 0,2XT’ <= 500 Hilo “a”

0,15XT + 0,1XT’ <= 300 Hilo “b”

0,072XT + 0,027XT’ <= 108 Hilo “c”

Las restricciones de no negatividad no son necesarias en este ejemplo dado que se trata de

un ejercicio de maximización, cuando el ejercicio sea de minimización lo más recomendado

es incluirlas.

FUNCIÓN OBJETIVO

ZMAX = 4000XT + 5000XT’

LA SOLUCIÓN MEDIANTE MÉTODO GRÁFICO

PASO 1: GRAFICAR LAS RESTRICCIONES

Para iniciar con el trazado de las restricciones es indispensable igualar las restricciones a 0,

de esta manera podemos mediante despeje de ecuaciones iniciar con la tabulación que nos

otorgará las coordenadas para esbozar cada una de las gráficas. Además dado que se

trabajará en el plano cartesiano sería prudente renombrar las variables

XT = x

XT' = y

Igualamos las restricciones,

0,12X + 0,2y = 500

0,15X + 0,1y = 300

0,072X + 0,027y = 108

Acto seguido iniciamos con la primera restricción, hallamos las primeras dos coordenadas.

Para hallar las coordenadas regularmente llevamos una de las variables a cero, para de esta

manera despejar más fácilmente la segunda.

Por ejemplo, para un x = 0

0,12(0) + 0,2y = 500

0,2y = 500

500/0,2 = y

2500 = y

y para un y = 0

0,12x + 0,2(0) = 500

0,12x = 500

x = 500/0,12

x = 4167


Seguimos con la segunda restricción,

0,15X + 0,1y = 300


Tercera restricción,

0,072X + 0,027y = 108


En el siguiente gráfico se muestra el polígono solución de color gris, en este conjunto es

donde cada coordenada cumple con todas las restricciones, las cuales se caracterizan por ser

restricciones de menor o igual y esta característica se representa con una flecha hacía abajo.


Una vez se llega a este punto es indispensable saber que las soluciones óptimas se alojan en

los vértices del polígono solución (color gris) y que identificar a la solución óptima es cuestión

de elegir la mejor alternativa dependiendo de las herramientas disponibles (tecnológicas y

conocimientos matemáticos).

La primera opción es la geométrica, esta depende de trazar la ecuación que representa a la

función objetivo (este paso consiste en realizar el mismo procedimiento de las restricciones).

Función objetivo,

ZMAX = 4000x + 5000y

luego igualamos a 0.

4000x + 5000y = 0

luego tabulamos para obtener las coordenadas necesarias para esbozar la gráfica

correspondientes a la ecuación (en esta ocasión es recomendable más de dos coordenadas,

incluyendo la coordenada (x = 0, y = 0).


Una vez se ha esbozado la función objetivo (línea negra) sacamos replicas perpendiculares a

esta que se encuentren con cada vértice, y solo en el caso en que la línea imaginaria

perpendicular a la función objetivo no corte el polígono solución se ha encontrado la solución

óptima. En otras palabras trasladamos la función objetivo por todo el polígono conservando

la perpendicularidad con la original, la detenemos en los vértices y evaluamos si esta corta o

no el conjunto solución.


Claramente solo en el punto "B", es decir en el vértice formado por la intersección de las

ecuaciones 1 y 2, la línea imaginaria no corta el polígono solución, entonces es este punto el

correspondiente a la coordenada óptima.

Para hallar el valor de esta coordenada es indispensable recurrir a la resolución de

ecuaciones lineales 2x2, y se pueden considerar varios métodos de solución entre ellos:

- Método por sustitución

- Método por igualación

- Método por reducción o Eliminación

- Método por eliminación Gauss

- Método por eliminación Gauss - Jordán

- Método por determinantes

La riqueza de las matemáticas nos deja suficientes alternativas, para mi gusto el método de

reducción o eliminación es muy sencillo de aplicar.

El método por reducción o eliminación consiste en igualar los coeficientes de una de las

variables multiplicando una o las dos ecuaciones, teniendo en cuenta que estos coeficientes

queden iguales pero con signos contrarios.

Ecuación 1 0,12x + 0,2y = 500

Ecuación 2 0,15x + 0,1y = 300 multiplicamos por (-2)

Ecuación 3 (2*(-2)) -0,30x - 0,2y = -600

Sumamos 1 y 3 -0,18x = -100

Despejamos "x" x = -100 / (-0,18)

x = 555,55

luego reemplazamos x = 555,55 en cualquiera de las dos ecuaciones originales con el

objetivo de despejar "y".

Ecuación 1 0,12x + 0,2y = 500

Reemplazamos "x" 0,12(555,55) + 0,2y = 500

Despejamos "y" 66,666 + 0,2y = 500

0,2y = 500 - 66,666

0,2y = 433,334

y = 433,334 / 0,2

y = 2166,67

De esta forma hemos obtenido los valores para "x" y "y".

Recordemos que x y y fueron los nombres que recibieron las variables originales XT y XT'

x = XT

y = XT'

XT = 555,55

XT' = 2166,67

y la contribución obtenida (reemplazando las variables en la función objetivo) es de:

Zmax = 4000XT + 5000XT'

Zmax = 4000(555,55) + 5000(2166,67)

Zmax = 13.055.550

Ahora podemos cotejar los resultados con los obtenidos mediante resolución porSolver -

Excel, sin embargo recuerden que el método de búsqueda de la solución óptima en el

método gráfico que utilizamos es el geométrico y que existe una posibilidad mucho más

engorrosa pero igualmente efectiva, este es el método de iteración por vértice, y que

consiste en hallar todas las coordenadas de los vértices y luego en cada coordenada se

evalúa la función objetivo, (cada coordenada nos proporciona un valor en "x" y otro en "y",

luego reemplazamos estos valores en la función objetivo "4000x + 5000y = ?" y luego

evaluamos los resultados seleccionando la mayor cantidad).

Una herramienta muy útil al momento de resolver ejercicios mediante el método gráfico es

una calculadora graficadora, como es el caso de la calculadora de encarta (disponible aquí).

VARIANTES EN EL MÉTODO GRÁFICOComo en la mayoría de los casos el ejemplo con el que aquí se explicó el método gráfico es el

ideal, es decir un ejercicio de conjunto acotado con solución óptima única, sin embargo

existen una variedad de problemas diferentes a los ideales y que vale la pena analizar:SOLUCIÓN ÓPTIMA MÚLTIPLE

Una de las variantes que puede presentar un ejercicio de programación lineal consiste en la

cantidad de soluciones óptimas, gran cantidad de ellos presenta más de una solución óptima,

es decir una solución en la cual la función objetivo es exactamente igual en una combinación

cuantitativa de variables diferente.

Estos problemas deben de afrontarse de tal manera que prime el análisis de sensibilidad, es

decir una vez encontradas múltiples soluciones iguales se debe proceder al comportamiento

del consumo de los recursos y restricciones, evidentemente prevaleciendo el concepto de

productividad de los recursos más limitados y costosos.

Un ejemplo de este caso es el siguiente:

La ebanistería "SALAZAR LTDA" ha recibido una gran cantidad de partes prefabricadas para

la elaboración de mesas, sin embargo no ha podido iniciar un plan de producción enfocado a

estas por la alta demanda que tiene de sus productos restantes. Las mesas que pueden

elaborarse de las partes prefabricadas son de dos modelos, modelo A y B, y estas no

requieren más que ser ensambladas y pintadas. Esta semana se ha determinado dedicar 10

horas de ensamble y 8 de pintura para elaborar la mayor cantidad de mesas posibles

teniendo en cuenta que cada mesa modelo A requiere de 2 horas de ensamble y 1 de pintura

respectivamente, y que cada mesa modelo B requiere de 1 hora de ensamble y 2 de pintura

respectivamente. Si el margen de utilidad es de $20000 por cada mesa modelo A y $10000

por cada mesa modelo B. Determine el modelo adecuado de producción para esta semana.

X = Cantidad de mesas modelo A a fabricar esta semana

Y = Cantidad de mesas modelo B a fabricar esta semana


http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/programaci%C3%B3n-lineal/

http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/programaci%C3%B3n-lineal/

Restricciones

2X + Y <= 10 "Horas de ensamble"

X + 2Y <= 8 "Horas de pintura"

X, Y => 0 "De no negatividad"

Función objetivo

Zmax = 20000X + 10000Y

La gráfica resultante sería:


Como nos podemos dar cuenta mediante la geometría en dos vértices la línea imaginaria

perpendicular a la función objetivo no atraviesa el conjunto solución, por ende en dos puntos

se presentan soluciones óptimas, que son los puntos B y C.

Observemos la solución óptima múltiple

Z(0) = 20000(0) + 10000(0) = 0

Z(A) = 20000(0) + 10000(4) = $40000

Z(B) = 20000(4) + 10000(2) = $100000

Z(C) = 20000(5) + 10000(0) = $100000

Existen entonces dos soluciones óptimas

Solución óptima 1

X = 4 Y = 2

Solución óptima 2

X = 5 Y = 0

La pregunta siguiente es ¿cual decisión tomar?, pues depende de factores tales como una

análisis de sensibilidad donde se tenga en cuenta el consumo distinto de determinados

recursos (horas ensamble vs. horas pintura) y factores extras al modelo como lo puede llegar

a ser en este caso una necesidad de espacio de almacenamiento, dado que existe una

alternativa en la que se elaboran más mesas que en la otra, de todas formas es interesante

el paso posterior a esbozar los resultados pues requerirá de la capacidad de quien toma las

decisiones.SOLUCIÓN ÓPTIMA NO ACOTADA

Otra de las variantes que presentan los modelos de programación lineal corresponde a los

modelos de solución óptima no acotada, es decir problemas con infinitas soluciones óptimas.

Hay que reconocer que en la vida real gran parte de estos problemas se deben a un mal

planteamiento de las restricciones, sin embargo es común que este tipo de problemas sean

evaluados en la vida académica.

Un ejemplo:

La compañía comercializadora de bebidas energéticas "CILANTRO SALVAJE" se encuentra

promocionando dos nuevas bebidas, la tipo A y la tipo B, dado que se encuentran en

promoción se puede asegurar el cubrimiento de cualquier cantidad de demanda, sin embargo

existen 2 políticas que la empresa debe tener en cuenta. Una de ellas es que la cantidad de

bebidas tipo A que se vendan no puede ser menor que las de tipo B, y la segunda es que se

deben de vender por lo menos 1500 bebidas de cualquier tipo.

Dado que se encuentran en promoción el precio de venta de ambas bebidas equivale a

$1800 pesos.

Determine la cantidad de unidades que deben venderse!!

X = Cantidad de bebidas tipo A a vender

Y = Cantidad de bebidas tipo B a vender

Restricciones

X => Y

X + Y => 1500

Función Objetivo

Zmax = 1800X + 1800Y

La gráfica resultante sería:


Es claro que en este ejercicio las variables pueden aumentar mejorando indefinidamente la

función objetivo, en estos casos se dice que la solución óptima no es acotada, por lo cual las

posibles soluciones son infinitas.SOLUCIÓN INFACTIBLE

El caso de la solución infactible es más típico de lo pensado, y corresponde a los casos en los

cuales no existen soluciones que cumplen con todas las restricciones. Es muy común ver este

fenómeno producto de inviables proporciones de oferta y demanda.

Un ejemplo:

La compañía de galletas "CAROLA" desea planificar la producción de galletas que tendrá que

entregar a su cliente en dos semanas, el contrato indica que la compañía "CAROLA" se

compromete a entregar por lo menos 300 cajas de galletas cualquiera sea su tipo

(presentación D, presentación N o una combinación de ambas presentaciones), cada caja de

galletas presentación D tiene un tiempo de elaboración de 2 horas, y un tiempo de horneado

de 3 horas, mientras cada caja de presentación N tiene un tiempo de elaboración de 3 horas

y un tiempo de horneado de 1 hora. La compañía cuenta estas dos semanas con 550 horas

para elaboración y con 480 horas de horneado.

Teniendo en cuenta que el margen de utilidad de cada caja de galletas presentación D y N es

de $8500 y $8100 respectivamente, determine mediante un modelo de programación lineal

el plan de producción que maximice las utilidades.

Variables

X = Cantidad de cajas de galletas presentación D a producir en 2 semanas

Y = Cantidad de cajas de galletas presentación N a producir en 2 semanas

Restricciones

2X + 3Y <= 550

3X + Y <= 480

X + Y => 300

Función Objetivo

Zmax = 8500X + 8100Y

La gráfica resultante es la siguiente:


Evidentemente no existe forma alguna de satisfacer todas las restricciones, por ende se

concluye que no existe solución factible.REDUNDANTES O SOBRANTES

Existen en los modelos de programación lineal un tipo de restricciones que no juegan rol

alguno en la determinación del conjunto solución (de igual manera en la solución óptima), lo

que lleva a deducir que estas son redundantes.

Por ejemplo:

La compañía "CONGELADORES MAJO" pretende fabricar dos tipos de congeladores

denominados A y B. Cada uno de ellos debe pasar por tres operaciones antes de su

comercialización: Ensamblaje, pintura y control de calidad. Los congeladores tipo A requieren

2 horas de ensamblaje, 3 kg de pintura y 4 horas de control de calidad; los congeladores tipo

B requieren 3 horas de ensamblaje, 6 kg de pintura y 5 horas de control de calidad. El

margen contributivo por cada congelador tipo A y B es de $102000 y $98000

respectivamente.

La compañía dispone como máximo semanalmente 300 horas de ensamblaje, 840 kg de

pintura y 450 horas de control de calidad. Con base en la información suministrada

determine las unidades a producir semanalmente de cada referencia para maximizar las

utilidades.

Las variables:

X = Cantidad de congeladores tipo A a producir semanalmente

Y = Cantidad de congeladores tipo B a producir semanalmente

Las restricciones:

2X + 3Y <= 300

3X + 5Y <= 840

4X + 5Y <= 450

Función Objetivo:

Zmax = 102000X + 98000Y

La gráfica resultante es la siguiente,


La solución óptima corresponde a:

X = 150

Y = 0

y la función objetivo quedaría.

Zmax = $15300000

Claramente podemos observar como la restricción 1 y la restricción 2 no determinan el

conjunto solución, por ende se denominan restricciones redundantes o sobrantes.

MÉTODO SIMPLEX

El Método Simplex es un método analítico de solución de problemas de programación lineal

capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin

restricción en el número de variables.

El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso.

La razón matemática de esta mejora radica en que el método consiste en caminar del vértice

de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto

de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que

presenta un poliedro solución es finito siempre se hallará solución.

Este famosísimo método fue creado en el año de 1947 por el estadounidense George Bernard

Dantzig y el ruso Leonid Vitalievich Kantorovich, con el ánimo de crear un algoritmo capaz de

solucionar problemas de m restricciones y n variables.

¿QUE ES UNA MATRIZ IDENTIDAD?Una matriz puede definirse como una ordenación rectangular de elementos, (o listado finito

de elementos), los cuales pueden ser números reales o complejos, dispuestos en forma de

filas y de columnas.

La matriz idéntica o identidad es una matriz cuadrada (que posee el mismo número tanto de

columnas como de filas) de orden n que tiene todos los elementos diagonales iguales a uno

(1) y todos los demás componentes iguales a cero (0), se denomina matriz idéntica o

identidad de orden n, y se denota por:

La importancia de la teoría de matrices en el Método Simplex es fundamental, dado que el

algoritmo se basa en dicha teoría para la resolución de sus problemas.

OBSERVACIONES IMPORTANTES AL UTILIZAR MÉTODO SIMPLEXVARIABLES DE HOLGURA Y EXCESO

El Método Simplex trabaja basándose en ecuaciones y las restricciones iniciales que se

modelan mediante programación lineal no lo son, para ello hay que convertir estas

inecuaciones en ecuaciones utilizando unas variables denominadas de holgura y exceso

relacionadas con el recurso al cual hace referencia la restricción y que en el tabulado final

representa el "Slack or surplus" al que hacen referencia los famosos programas de resolución

de investigación de operaciones, estas variables adquieren un gran valor en el análisis de

sensibilidad y juegan un rol fundamental en la creación de la matriz identidad base del

Simplex.

Estas variables suelen estar representadas por la letra "S", se suman si la restricción es de

signo "<= " y se restan si la restricción es de signo ">=".

Por ejemplo:



VARIABLE ARTIFICIAL / MÉTODO DE LA "M"

Una variable artificial es un truco matemático para convertir inecuaciones ">=" en

ecuaciones, o cuando aparecen igualdades en el problema original, la característica principal

de estas variables es que no deben formar parte de la solución, dado que no representan

recursos. El objetivo fundamental de estas variables es la formación de la matriz identidad.

Estas variables se representa por la letra "A", siempre se suman a las restricciones, su

coeficiente es M (por esto se le denomina Método de la M grande, donde M significa un

número demasiado grande muy poco atractivo para la función objetivo), y el signo en la

función objetivo va en contra del sentido de la misma, es decir, en problemas de

Maximización su signo es menos (-) y en problemas de Minimización su signo es (+),

repetimos con el objetivo de que su valor en la solución sea cero (0).

MÉTODO SIMPLEX PASO A PASOEL PROBLEMA

La empresa el SAMÁN Ltda. Dedicada a la fabricación de muebles, ha ampliado su producción

en dos líneas más. Por lo tanto actualmente fabrica mesas, sillas, camas y bibliotecas. Cada

mesa requiere de 2 piezas rectangulares de 8 pines, y 2 piezas cuadradas de 4 pines. Cada

silla requiere de 1 pieza rectangular de 8 pines y 2 piezas cuadradas de 4 pines, cada cama

requiere de 1 pieza rectangular de 8 pines, 1 cuadrada de 4 pines y 2 bases trapezoidales de

2 pines y finalmente cada biblioteca requiere de 2 piezas rectangulares de 8 pines, 2 bases

trapezoidales de 2 pines y 4 piezas rectangulares de 2 pines. Cada mesa cuesta producirla

$10000 y se vende en $ 30000, cada silla cuesta producirla $ 8000 y se vende en $ 28000,

cada cama cuesta producirla $ 20000 y se vende en $ 40000, cada biblioteca cuesta

producirla $ 40000 y se vende en $ 60000. El objetivo de la fábrica es maximizar las

utilidades.

Problema planteado por Héctor Angulo - Ingeniero Industrial

PASO 1: MODELACIÓN MEDIANTE PROGRAMACIÓN LINEAL

Las variables:

X1 = Cantidad de mesas a producir (unidades)

X2 = Cantidad de sillas a producir (unidades)

X3 = Cantidad de camas a producir (unidades)

X4 = Cantidad de bibliotecas a producir (unidades)

Las restricciones:

2X1 + 1X2 + 1X3 + 2X4 <= 24

2X1 + 2X2 + 1X3 <= 20

2X3 + 2X4 <= 20

4X4 <= 16

La función Objetivo:

ZMAX = 20000X1 + 20000X2 + 20000X3 + 20000X4

PASO 2: CONVERTIR LAS INECUACIONES EN ECUACIONES

En este paso el objetivo es asignar a cada recurso una variable de Holgura, dado que todas

las restricciones son "<=".

2X1 + 1X2 + 1X3 + 2X4 + 1S1 + 0S2 + 0S3 + 0S4 = 24

2X1 + 2X2 + 1X3 + 0X4 + 0S1 + 1S2 + 0S3 + 0S4 = 20

0X1 + 0X2 + 2X3 + 2X4 + 0S1 + 0S2 + 1S3 + 0S4 = 20

0X1 + 0X2 + 0X3 + 4X4 + 0S1 + 0S2 + 0S3 + 1S4 = 16

De esta manera podemos apreciar una matriz identidad (n = 4), formado por las variables de

holgura las cuales solo tienen coeficiente 1 en su respectivo recurso, por el ejemplo la

variable de holgura "S1" solo tiene coeficiente 1 en la restricción correspondiente a el recurso

1.

La función objetivo no sufre variaciones:

ZMAX = 20000X1 + 20000X2 + 20000X3 + 20000X4

PASO 3: DEFINIR LA SOLUCIÓN BÁSICA INICIAL

El Método Simplex parte de una solución básica inicial para realizar todas sus

iteraciones, esta solución básica inicial se forma con las variables de coeficiente diferente de

cero (0) en la matriz identidad.

1S1 = 24

1S2 = 20

1S3 = 20

1S4 = 16PASO 4: DEFINIR LA TABLA SIMPLEX INICIAL


Solución: (segundo término)= En esta fila se consigna el segundo término de la solución, es

decir las variables, lo más adecuado es que estas se consignen de manera ordenada, tal cual

como se escribieron en la definición de restricciones.

Cj = La fila "Cj" hace referencia al coeficiente que tiene cada una de las variables de la fila

"solución" en la función objetivo.

Variable Solución = En esta columna se consigna la solución básica inicial, y a partir de

esta en cada iteración se van incluyendo las variables que formarán parte de la solución final.

Cb = En esta fila se consigna el valor que tiene la variable que se encuentra a su derecha

"Variable solución" en la función objetivo.

Zj = En esta fila se consigna la contribución total, es decir la suma de los productos entre

término y Cb.

Cj - Zj = En esta fila se realiza la diferencia entre la fila Cj y la fila Zj, su significado es un

"Shadow price", es decir, la utilidad que se deja de recibir por cada unidad de la variable

correspondiente que no forme parte de la solución.

Solución inicial:


PASO 5: REALIZAR LAS ITERACIONES NECESARIAS

Este es el paso definitivo en la resolución por medio del Método Simplex, consiste en realizar

intentos mientras el modelo va de un vértice del poliedro objetivo a otro.

El procedimiento a seguir es el siguiente:

1. Evaluar que variable entrará y cual saldrá de la solución óptima:

Maximizar Minimizar

Variable que

entraLa más positiva de los Cj - Zj La más negativa de los Cj - Zj

Variable que sale

Siendo b los valores bajo la celda solución

y a el valor correspondiente a la intersección

entre b y la variable que entra. La menos

positiva de los b/a.

Siendo b los valores bajo la celda solución

y a el valor correspondiente a la intersección

entre b y la variable que entra. La más

positiva de los b/a.


2. El hecho de que una variable distinta forme parte de las variables solución implica una

serie de cambios en el tabulado Simplex, cambios que se explicarán a continuación.

- Lo primero es no olvidar el valor del "a" correspondiente a la variables a entrar, en este

caso el "a = 4".


- Lo siguiente es comenzar a rellenar el resto de la tabla, fila x fila.


- Se repite este procedimiento con las dos filas restantes, ahora se harán los cálculos

correspondientes en el resto de las celdas.


De esta manera se culmina la primera iteración, este paso se repetirá cuantas veces sea

necesario y solo se dará por terminado el método según los siguientes criterios.

Maximizar Minimizar

Solución Óptima Cuando todos los Cj - Zj sean <= 0 Cuando todos los Cj - Zj sean >= 0

- Continuamos con las iteraciones para lo cual tenemos que repetir los pasos anteriores.


En esta última iteración podemos observar que se cumple con la consigna Cj - Zj <= 0, para

ejercicios cuya función objetivo sea "Maximizar", por ende hemos llegado a la respuesta

óptima.

X1 = 3

X2 = 4

X3 = 6

X4 = 4

Con una utilidad de: $ 340000

Sin embargo una vez finalizado el Método Simplex se debe observar una matriz identidad en

el rectángulo determinado por las variables de decisión, el hecho de que en este caso no se

muestre la matriz identidad significa que existe una solución óptima alterna.


La manera de llegar a la otra solución consiste en alterar el orden en que cada una de las

variables entro a la solución básica, recordemos que el proceso fue decidido al azar debido a

la igualdad en el Cj - Zj del tabulado inicial. Aquí les presentamos una de las maneras de

llegar a la otra solución.


Podemos observar como existe una solución óptima alternativa en la cual la combinación de

variables es distinta y existe un menor consumo de recursos, dado que el hecho de que se

encuentre la variable "S1" en la solución óptima con un coeficiente de "3" significa que se

presenta una holgura de 3 unidades del recurso (pieza rectangular de 8 pines).

X1 = 0 (Cantidad de mesas a producir = 0)

X2 = 7 (Cantidad de sillas a producir = 7)

X3 = 6 (Cantidad de camas a producir = 6)

X4 = 4 (Cantidad de bibliotecas a producir = 4)

S1 = 3 (Cantidad de piezas rectangulares de 8 pines sin utilizar =3)

Con una utilidad de: $ 340000

PROBLEMAS DE MINIMIZACIÓN CON EL MÉTODO SIMPLEX

Para resolver problemas de minimización mediante el algoritmo simplex existen dos

procedimientos que se emplean con regularidad.

- El primero, que a mi juicio es el más recomendable se basa en un artificio aplicable al

algoritmo fundamentado en la lógica matemática que dicta que "para cualquier función f(x),

todo punto que minimice a f(x) maximizará también a - f(x)". Por lo tanto el procedimiento a

aplicar es multiplicar por el factor negativo (-1) a toda la función objetivo.

a continuación se resuelve el algoritmo como un problema de maximización.

- El segundo procedimiento, el cual pretende conservar la minimización consiste en aplicar

los criterios de decisión que hemos esbozado con anterioridad, en los casos de la variable

que entra, que sale y el caso en el que la solución óptima es encontrada. Aquí recordamos

los procedimientos según el criterio dado el caso "minimizar".

Minimizar

Variable que entra La más negativa de los (Cj - Zj)

Variable que saleSiendo "b" los valores bajo la celda solución y "a" el valor correspondiente a la intersección

entre "b" y la variable que entra. La más positiva de los "b/a".

Solución Óptima Cuando todos los (Cj - Zj) sean >= 0.

DUALIDAD EN PROGRAMACIÓN LINEALCada uno de los problemas abordados hasta entonces en los módulos anteriores se

consideran problemas primales dado que tienen una relación directa con la necesidad del

planteamiento, y sus resultados responden a la formulación del problema original; sin

embargo cada vez que se plantea y resuelve un problema lineal, existe otro problema

ínsitamente planteado y que puede ser resuelto, es el considerado problema dual, el cual

tiene unas importantes relaciones y propiedades respecto al problema primal que pueden ser

de gran beneficio para la toma de decisiones.

Relaciones entre problemas primales y duales

- El número de variables que presenta el problema dual se ve determinado por el número de

restricciones que presenta el problema primal.

- El número de restricciones que presenta el problema dual se ve determinado por el número

de variables que presenta el problema primal.

- Los coeficientes de la función objetivo en el problema dual corresponden a los términos

independientes de las restricciones (RHS), que se ubican del otro lado de las variables.

- Los términos independientes de las restricciones (RHS) en el problema dual corresponden a

los coeficientes de la función objetivo en el problema primal.

- La matriz que determina los coeficientes técnicos de cada variable en cada restricción

corresponde a la transpuesta de la matriz de coeficientes técnicos del problema primal.

El sentido de las igualdades y desigualdades se comporta según la tabla de TUCKER,

presentada a continuación.

Tabla de TUCKER

IMPORTANCIA DE LA DUALIDAD EN PROGRAMACIÓN LINEALLa resolución de los problemas duales respecto a los primales se justifica dada la facilidad

que se presenta dados problemas donde el número de restricciones supere al número de

variables. Además de tener gran aplicación en el análisis económico del problema.

Otra de las ventajas que presenta es que dado a que el número de restricciones y variables

entre problema dual y primal es inverso, se pueden resolver gráficamente problemas que

presenten dos restricciones sin importar el número de variables.

RESOLUCIÓN DEL PROBLEMA DUAL, PASO A PASOEl siguiente problema a resolver es hasta el momento el modelo más completo de los

resueltos en los módulos anteriores, dado que trataremos de resolver un problema primal y

su dual mediante Método Simplex utilizando variables de holgura, exceso y artificiales;

además resolveremos el primal utilizando Simplex maximizando y el dual minimizando.

Dado el siguiente modelo primal,

ZMAX = 40X1 + 18X2

16X1 + 2X2 ≤ 700

6X1 + 3X2 ≤ 612

X1 ≤ 80

X2 ≤ 120


Cuya respuesta es

X1 = 28,75

X2 = 120

S1 = 79.5

S3 = 51.25

Función objetivo = 3310

Procedemos a resolver el problema dual

PASO 1: Definimos el problema dual


Este paso se lleva a cabo teniendo en cuenta las relaciones que se expusieron en la

definición de la dualidad. Ahora las variables en el dual las representaremos por "ʎ" y

corresponden a cada restricción.

El modelo queda de la siguiente forma:

ZMIN = 700ʎ1 + 612ʎ2 + 80ʎ3 + 120ʎ4

16ʎ1 + 6ʎ2 + ʎ3 ≥ 40

2ʎ1 + 3ʎ2 + ʎ4 ≥ 18

ʎ1;ʎ4 ≥ 0

Ahora preparamos el modelo para ser resuelto mediante Método Simplex, utilizaremos el

procedimiento en el cual la función objetivo es multiplicada por (-1) y resolveremos el modelo

mediante maximización.

ZMIN = 700ʎ1 + 612ʎ2 + 80ʎ3 + 120ʎ4

lo que es igual

(-Z)MAX = -700ʎ1 - 612ʎ2 - 80ʎ3 - 120ʎ4

Ahora dado que los signos de las inecuaciones son mayor o igual procedemos a volverlas

ecuaciones agregando variables de exceso, recordemos que en este caso las variables de

exceso se restan del lado izquierdo de la igualdad, por ende.

16ʎ1 + 6ʎ2 + ʎ3 + 0ʎ4 - 1S1 + 0S2 = 40

21ʎ1 + 3ʎ2 + 0ʎ3 + ʎ4 + 0S1 - 1S2 = 18

ʎ1;ʎ4 ≥ 0

Recordemos que el Método Simplex solo es posible por la formación de la matriz identidad,

sin embargo en una matriz identidad no pueden ir coeficientes negativos, el cual es el caso,

por ende recurriremos al artificio denominado "Método de la M grande" utilizando variables

artificiales, las cuales siempre se suman.

16ʎ1 + 6ʎ2 + ʎ3 + 0ʎ4 - 1S1 + 0S2 + 1A1 + 0A2 ≥ 40

21ʎ1 + 3ʎ2 + 0ʎ3 + ʎ4 + 0S1 - 1S2 + 0A1 + 1A2 ≥ 18

ʎ1;ʎ4 ≥ 0

Ahora si observamos la matriz identidad formada por las variables artificiales, nuestra

función objetivo es la siguiente (varía dada la incorporación de las nuevas variables).

(-Z)MAX = -700ʎ1 - 612ʎ2 - 80ʎ3 - 120ʎ4 + 0S1 + 0S2 - MA1 - MA2

Recordemos que el coeficiente de las variables de holgura y exceso es 0, además que los

coeficientes de las variables artificiales es M, donde M corresponde a un número grande poco

atractivo cuyo signo en la función objetivo depende del criterio de la misma, dado que la

función es maximizar el signo es negativo. Dado que utilizaremos el Método Simplex y no un

software para la resolución del modelo es necesario que M adquiera valor, en este caso será

"-10000" un número bastante grande en el problema.

Las iteraciones que utiliza el Método Simplex son las siguientes:


Podemos observar que todos los Cj - Zj son menores o iguales a 0, por ende hemos llegado a

la solución óptima del problema, sin embargo recordemos que la función objetivo fue

alterada en su signo al principio, por ende se hace necesario regresarle su signo original a Zj

y a la fila Cj - Zj.

(-Z)max = -3310 * (-1)

Zmax = 3310

Podemos cotejar con la función objetivo del modelo primal y encontraremos que hallamos el

mismo resultado.

Ahora se hace necesario interpretar los resultados de la tabla dual respecto al modelo primal,

y esta interpretación se realiza siguiendo los siguientes principios.


La interpretación del tabulado final del modelo dual es la siguiente:


TEOREMAS DE LA DUALIDAD EN PROGRAMACIÓN LINEAL1. Si el modelo primal o dual tiene solución óptima finita entonces su respectivo dual o primal

tendrán solución óptima finita.

2. Si el modelo primal o dual tiene solución óptima no acotada, entonces su respectivo dual o

primal no tendrán solución, será un modelo infactible.

3. Si el modelo primal o dual no tiene solución entonces su respectivo dual o primal no

tendrán solución.

4. Sea "A" un modelo primal cuyo modelo dual es "B", el modelo dual de "B" es igual a "A", es

decir "El modelo dual de un dual es un modelo primal".

PROBLEMA DEL TRANSPORTE O DISTRIBUCIÓN

El problema del transporte o distribución es un problema de redes especial en programación

lineal que se funda en la necesidad de llevar unidades de un punto específico

llamado Fuenteu Origen hacía otro punto específico llamado Destino. Los principales

objetivos de un modelo de transporte son la satisfacción de todos los requerimientos

establecidos por los destinos y claro está la minimización de los costos relacionados con el

plan determinado por las rutas escogidas.

El contexto en el que se aplica el modelo de transporte es amplio y puede generar soluciones

atinentes al área de operaciones, inventario y asignación de elementos.

El procedimiento de resolución de un modelo de transporte se puede llevar a cabo mediante

programación lineal común, sin embargo su estructura permite la creación de múltiples

alternativas de solución tales como la estructura de asignación o los métodos heurísticos más

populares como Vogel, esquina noroeste o mínimos costos.


Los problemas de transporte o distribución son uno de los más aplicados en la economía

actual, dejando como es de prever múltiples casos de éxito a escala global que estimulan la

aprehensión de los mismos.

PROBLEMA DE TRANSPORTE MEDIANTE PROGRAMACIÓN LINEALComo se mencionó anteriormente la programación lineal puede ser utilizada para la

resolución de modelos de transporte, aunque no sea sensato resolver los modelos mediante

el Método Simplex si puede ser de gran utilidad la fase de modelización, la programación

carece de la practicidad de los métodos de asignación, pero puede ser de gran importancia

dependiendo de la complejidad de las restricciones adicionales que puede presentar un

problema particular.EL PROBLEMA

Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer

la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las

plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente.

Las necesidades de las ciudades de Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y

35 millones de Kw al día respectivamente.

Los costos asociados al envío de suministro energético por cada millón de KW entre cada

planta y cada ciudad son los registrados en la siguiente tabla.


Formule un modelo de programación lineal que permita satisfacer las necesidades de todas

las ciudades al tiempo que minimice los costos asociados al transporte.SOLUCIÓN MEDIANTE PL

El modelo básico de transporte es el modelo en el cual la cantidad ofertada es igual a la

cantidad demandada, como es el caso de este ejercicio, sin embargo trasladar esta

suposición a la realidad es casi imposible por lo cual hace falta crear orígenes y/o destinos

ficticios con el excedente de oferta y/o demanda.

Como ya lo hemos planteado en módulos anteriores el primer paso corresponde a la

definición de las variables, regularmente se le denomina a las variables de manera

algebraica Xi,j donde i simboliza a la fuente y j simboliza al destino. En este caso i define el

conjunto {Planta 1, Planta 2, Planta 3 y Planta 4}, y j define el conjunto {Cali, Bogotá,

Medellín y Barranquilla}. Sin embargo es práctico renombrar cada fuente y destino por un

número respectivo, por ende la variable X1,2corresponde a la cantidad de millones de KW

enviados diariamente de la Planta 1 a la ciudad de Bogotá.


El segundo paso corresponde a la formulación de las restricciones de oferta y demanda, cuya

cantidad se encuentra determinada por el factor entre fuentes y destinos, en este caso 16

restricciones.

Restricciones de oferta o disponibilidad, las cuales son de signo ≤:

X1,1 + X1,2 + X1,3 + X1,4 ≤ 80

X2,1 + X2,2 + X2,3 + X2,4 ≤ 30

X3,1 + X3,2 + X3,3 + X3,4 ≤ 60

X4,1 + X4,2 + X4,3 + X4,4 ≤ 45

Restricciones de demanda, las cuales son de signo ≥:

X1,1 + X2,1 + X3,1 + X4,1 ≥ 70

X1,2 + X2,2 + X3,2 + X4,2 ≥ 40

X1,3 + X2,3 + X3,3 + X4,3 ≥ 70

X1,4 + X2,4 + X3,4 + X4,4 ≥ 35

Luego se procede a formular la función objetivo, en la cual se relaciona el costo

correspondiente a cada ruta.

ZMIN = 5X1,1 + 2X1,2 + 7X1,3 + 3X1,4 + 3X2,1 + 6X2,2 + 6X2,3 + 1X2,4 + 6X3,1 + 1X3,2 + 2X3,3 +

4X3,4 + 4X4,1 + 3X4,2 + 6X4,3 + 6X4,4

Luego se puede proceder al uso de la herramienta WinQSB para resolver el modelo realizado,

aquí están los resultados.



Este problema presenta una solución óptima alternativa, aquí los resultados.



Los análisis de dualidad y sensibilidad en los modelos de transporte resultan ser bastante

interesantes, pues pueden llegar a determinar aumentos de capacidad en las fuentes si el

precio sombra de las rutas en relación a ellas lo justifica.

MÉTODO DE APROXIMACIÓN DE VOGEL

El método de aproximación de Vogel es un método heurístico de resolución de problemas de

transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere

de la realización de un número generalmente mayor de iteraciones que los demás métodos

heurísticos existentes con este fin, sin embargo produce mejores resultados iniciales que los

mismos.

ALGORITMO DE RESOLUCIÓN DE VOGELEl método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y

1 más que asegura el ciclo hasta la culminación del método.PASO 1

Determinar para cada fila y columna una medida de penalización restando los dos costos

menores en filas y columnas.PASO 2

Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el

"Paso 1" se debe escoger el número mayor. En caso de haber empate, se debe escoger

arbitrariamente (a juicio personal).

PASO 3

De la fila o columna de mayor penalización determinada en el paso anterior debemos de

escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de

unidades. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se

tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con

oferta o demanda igual a cero (0).PASO 4: DE CICLO Y EXCEPCIONES

- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.

- Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las

variables básicas en la fila o columna con el método de costos mínimos, detenerse.

- Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda, determine

las variables básicas cero por el método del costo mínimo, detenerse.

- Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las ofertas y

las demandas se hayan agotado.

EJEMPLO DEL MÉTODO DE APROXIMACIÓN DE VOGELPor medio de este método resolveremos el ejercicio de transporte resuelto en módulos

anteriores mediante programación lineal.EL PROBLEMA










las ciudades al tiempo que minimice los costos asociados al transporte.SOLUCIÓN PASO A PASO

El primer paso es determinar las medidas de penalización y consignarlas en el tabulado de

costos, tal como se muestra a continuación.


El paso siguiente es escoger la mayor penalización, de esta manera:


El paso siguiente es escoger de esta columna el menor valor, y en una tabla paralela se le

asigna la mayor cantidad posible de unidades, podemos observar como el menor costo es "2"

y que a esa celda se le pueden asignar como máximo 60 unidades "que es la capacidad de la

planta 3".


Dado que la fila de la "Planta 3" ya ha asignado toda su capacidad (60 unidades) esta debe

desaparecer.


Se ha llegado al final del ciclo, por ende se repite el proceso


Iniciamos una nueva iteración


Continuamos con las iteraciones,


Iniciamos otra iteración


Al finalizar esta iteración podemos observar como el tabulado queda una fila sin tachar y con

valores positivos, por ende asignamos las variables básicas y hemos concluido el método.


Los costos asociados a la distribución son:



De esta manera hemos llegado a la solución a la cual también llegamos mediante

programación lineal, definitivamente desarrollar la capacidad para modelar mediante

programación lineal y apoyarse de una buena herramienta como WinQSB, STORM, LINGO,

TORA etc.. termina siendo mucho más eficiente que la utilización de los métodos heurísticos

para problemas determinísticos; sin embargo cabe recordar que uno de los errores más

frecuentes en los que caen los ingenieros industriales es en tratar de adaptar a sus

organizaciones a los modelos establecidos, cabe recordar que son los modelos los que deben

adaptarse a las organizaciones lo cual requiere de determinada habilidad para realizar de

forma inmediata innovaciones positivas para sus fines, en pocas palabras un ingeniero

industrial requiere de un buen toque de HEURÍSTICA en su proceder.

MÉTODO DEL COSTO MÍNIMO

El método del costo mínimo o de los mínimos costos es un algoritmo desarrollado con el

objetivo de resolver problemas de transporte o distribución, arrojando mejores resultados

que métodos como el de la esquina noroeste, dado que se enfoca en las rutas que presentan

menores costos. El diagrama de flujo de este algortimo es mucho más sencillo que los

anteriores dado que se trata simplememente de la asignación de la mayor cantidad de

unidades posibles (sujeta a las restricciones de oferta y/o demanda) a la celda menos costosa

de toda la matriz hasta finalizar el método.

ALGORITMO DE RESOLUCIÓN DEL COSTO MÍNIMOPASO 1:

De la matriz se elige la ruta (celda) menos costosa (en caso de un empate, este se rompe

arbitrariamente) y se le asigna la mayor cantidad de unidades posible, cantidad que se ve

restringida ya sea por las restricciones de oferta o de demanda. En este mismo paso se

procede a ajustar la oferta y demanda de la fila y columna afectada, restandole la cantidad

asignada a la celda.PASO 2:

En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del

"Paso 1", si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante

se deja con demanda u oferta cero (0) según sea el caso.PASO 3:

Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o

columna, si este es el caso se ha llegado al final el método, "detenerse".

La segunda es que quede más de un renglón o columna, si este es el caso iniciar

nuevamente el "Paso 1".

EJEMPLO DEL MÉTODO DEL COSTO MÍNIMOPor medio de este método resolveremos el problema de transporte propuesto y resuelto en

módulos anteriores mediante programación lineal.EL PROBLEMA










las ciudades al tiempo que minimice los costos asociados al transporte.

SOLUCIÓN PASO A PASO


Luego esa cantidad asignada se resta a la demanda de Bogotá y a la oferta de la "Planta 3",

en un proceso muy lógico. Dado que Bogotá se queda sin demanda esta columna

desaparece, y se repite el primer proceso.


Nuevo proceso de asignación






Una vez finalizado el cuadro anterior nos daremos cuenta que solo quedará una fila, por ende

asignamos las unidades y se ha terminado el método.


El cuadro de las asignaciones (que debemos desarrollarlo paralelamente) queda así:




En este caso el método del costo mínimo presenta un costo total superior al obtenido

mediante Programación Lineal y el Método de Aproximación Vogel, sin embargo comunmente

http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-de-aproximaci%C3%B3n-de-vogel/

http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/problema-del-transporte-o-distribuci%C3%B3n/

no es así, además es simple de desarrollar y tiene un mejor rendimiento en cuanto a

resultados respecto al Método de la Esquina Noroeste.

MÉTODO DE LA ESQUINA NOROESTE

El método de la esquina Noroeste es un algoritmo heurístico capaz de solucionar problemas

de transporte o distribución mediante la consecución de una solución básica inicial que

satisfaga todas las restricciones existentes sin que esto implique que se alcance el costo

óptimo total.

Este método tiene como ventaja frente a sus similares la rapidez de su ejecución, y es

utilizado con mayor frecuencia en ejercicios donde el número de fuentes y destinos sea muy

elevado. Su nombre se debe al génesis del algoritmo, el cual inicia en la ruta, celda o esquina

Noroeste. Es común encontrar gran variedad de métodos que se basen en la misma

metodología de la esquina Noroeste, dado que podemos encontrar de igual manera el

método e la esquina Noreste, Sureste o Suroeste.

ALGORITMO DE RESOLUCIÓN DE LA ESQUINA NOROESTESe parte por esbozar en forma matricial el problema, es decir, filas que representen fuentes y

columnas que representen destinos, luego el algoritmo debe de iniciar en la celda, ruta o

esquina Noroeste de la tabla (esquina superior izquierda).


PASO 1:

En la celda seleccionada como esquina Noroeste se debe asignar la máxima cantidad de

unidades posibles, cantidad que se ve restringida ya sea por las restricciones de oferta o de

http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-de-la-esquina-noroeste/

demanda. En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna

afectada, restandole la cantidad asignada a la celda.PASO 2:

En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del

"Paso 1", si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante

se deja con demanda u oferta cero (0) según sea el caso.PASO 3:

Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o

columna, si este es el caso se ha llegado al final el método, "detenerse".

La segunda es que quede más de un renglón o columna, si este es el caso iniciar

nuevamente el "Paso 1".

EJEMPLO DEL MÉTODO DE LA ESQUINA NOROESTEPor medio de este método resolveremos el problema de transporte propuesto y resuelto en

módulos anteriores mediante programación lineal.EL PROBLEMA










las ciudades al tiempo que minimice los costos asociados al transporte.

SOLUCIÓN PASO A PASO


Ahora la cantidad asignada a la esquina noroeste es restada a la demanda de Cali y a la

oferta de la "Planta 1", en un procedimiento muy lógico. Dado que la demanda de Cali una

vez restada la cantidad asignada es cero (0), se procede a eliminar la columna. El proceso de

asignación nuevamente se repite.


Continuamos con las iteraciones.


En este caso nos encontramos frente a la elección de la fila o columna a eliminar (tachar), sin

embargo podemos utilizar un criterio mediante el cual eliminemos la fila o columna que

presente los costos más elevados. En este caso la "Planta 2".

Nueva iteración.


Una vez finalizada esta asignación, se elimina la "Planta 3" que ya ha sido satisfecha con la

asignación de 60 unidades, por ende nos queda una sola fila a la cual le asignamos las

unidades estrictamente requeridas y hemos finalizado el método.


El cuadro de las asignaciones (que debemos desarrollarlo paralelamente) queda así:




El costo total es evidentemente superior al obtenido mediante Programación Linealy

el Método de Aproximación de Vogel, lo cual demuestra lo enunciado en la descripción del

algoritmo que cita que no obtiene siempre la mejor solución, sin embargo presenta un

cumplimiento de todas las restricciones y una rapidez de elaboración, lo cual es una ventaja

en problemas con innumerables fuentes y destinos en los cuales no nos importe más que

satisfacer las restricciones.

PROBLEMA DEL TRANSPORTE EN WINQSB


http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/problema-del-transporte-o-distribuci%C3%B3n/

El problema del transporte como un modelo especial dentro de la programación lineal

presenta una metodología de resolución que resulta ser muchos más sencilla que los

problemas de programación tradicionales. La herramienta de resolución de problemas

atinentes a la investigación de operaciones por excelencia "WinQSB" también distingue el

problema de transporte como un caso especial y desarrolla un módulo dedicado de manera

exclusiva al trabajo con este tipo de modelos en el llamado Network Modeling módulo que

estudiaremos a continuación.

ACERCA DE NETWORK MODELING (NET)Este programa resuelve los problemas de red, incluyendo flujo de red capacitados

(transbordo), transporte, asignación, la ruta más corta, flujo máximo, árbol de expansión

mínima, y problemas del vendedor viajero. Una red incluye nodos y conexiones (arcos /

enlaces) Cada nodo tiene una capacidad para el flujo de red y los problemas de transporte. Si

hay una conexión entre dos nodos, puede haber un costo, un beneficio, una distancia o la

capacidad de flujo asociado a la conexión. Con base en el tipo de problema específico, NET

resuelve la conexión o el envío satisfaciendo las restricciones con el ánimo de optimizar la

función objetivo especificada.

RESOLVIENDO UN PROBLEMA DE TRANSPORTE MEDIANTE WINQSBEl primer paso para resolver un problema de transporte mediante WinQSB es ingresar al

módulo Network Modeling.EL PROBLEMA










las ciudades al tiempo que minimice los costos asociados al transporte.INGRESANDO A NETWORK MODELING

Una vez se haya ingresado al módulo Network Modeling, se abrirá una ventana de inicio del

módulo, tal como se muestra a continuación.

Bryan Antonio Salazar López - WinQSB

Aquí podemos crear un nuevo problema o cargar uno que ya nos encontremos desarrollando,

en este caso abriremos un nuevo problema. Una vez demos click en "Nuevo Problema" se

abrirá un menú emergente que nos pedirá ingresar la información básica del problema.


En este menú debemos completar la información concerniente al tipo de problema, criterio

de la función objetivo y el número de fuentes y destinos que tenga nuestro problema, en este

caso tenemos 4 fuentes y 4 destinos. Una vez completado el proceso damos click en "OK" y

observaremos la siguiente ventana. En esta ventana podemos observar la matriz en la que

ingresaremos los datos.


El proceso de reconocimiento de la ventana matriz es rápido, además de las ya explicadas

herramientas se encuentran funciones de edición bastante conocidas y de formato

alfanumérico. Antes de ingresar los datos podemos modificar los nombres de las fuentes y

destinos en el menú "Edición (Edit / Node Names)". Nosotros renombraremos en este caso los

nodos por los indicados en el problema.


Ahora se consignan los costos asociados al modelo, igualmente se consignan la respectiva

oferta de cada una de las plantas y las demandas de las ciudades.


Ahora que se ha completado de suministrar toda la información se procede a resolver el

modelo (click en resolver), la ventana que se abrirá tendrá la información respecto a las

unidades enviadas de cada Planta hacia cada ciudad y el costo total óptimo.


De esta manera se obtiene la solución óptima del modelo de transporte, sin embargo no es

todo lo que WinQSB tiene para ofrecer respecto al modelo de transporte, dado que este

software posee herramientas que entregan el resultado gráficamente y presenta los

resultados que se obtienen mediante los métodos heurísticos que hemos visto en módulos

anteriores como Método de Aproximación de Vogel, Método de Costos Mínimos y el Método

de la Esquina Noroeste, que una vez se ha obtenido la solución mediante el programa sirven

para entornos netamente académicos.



http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-del-costo-m%C3%ADnimo/



MÉTODOS HEURÍSTICOS EN WINQSB (NETWORK MODELING)Para poder visualizar (recordamos que esto es regularmente requerido con fines académicos)

los tabulados finales obtenidos mediante los métodos heurísticos en Network

Modeling tenemos que acceder a la pestaña llamada "Solve and Analyze" una vez ahí

debemos seleccionar la opción "Select Initial Soluction Method", Tal como lo mostramos a

continuación.


Una vez cumplido este procedimiento se abrirá un menú en el cual podremos seleccionar el

método heurístico cuyo tabulado final queremos observar.


Una vez hemos seleccionado el método damos click en "OK" y procedemos a acceder a la

opción "Solve and Display Steps - Tableu" que se encuentra en la pestaña "Solve and

Analyze" tal como lo mostramos a continuación.


Ahora veremos el tabulado final del método heurístico escogido.

Método de Aproximación de Vogel


Método del Costo Mínimo


Método de la Esquina Noroeste


Podemos cotejar los resultados con los obtenidos mediante los mismos métodos en los

módulos anteriormente explicados, observaremos que son exactamente iguales

preponderando la función de este software que puedes descargar gratuitamente desde aquí.

PROBLEMA DE TRANSBORDOEl Problema de Transbordo, Intertransporte o Reembarque es una variación del modelo

original de transporte que se ajusta a la posibilidad común de transportar unidades mediante

nodos fuentes, destinos y transitorios, mientras el modelo tradicional solo permite envíos

directos desde nodos fuentes hacia nodos destinos.

Existe la posibilidad de resolver un modelo de transbordo mediante las técnicas tradicionales

de resolución de modelos de transporte y este procedimiento se basa en la preparación del

tabulado inicial haciendo uso de artificios conocidos con el nombre de amortiguadores, los

cuales deben ser iguales a la sumatoria de las ofertas de los nodos de oferta pura y de

coeficiente cero (0) en materia de costos.


Sin embargo la resolución de un problema de transbordo haciendo uso de los algoritmos de

resolución de modelos de transporte es una idea anacrónica, teniendo en cuenta la

posibilidad de acceso a herramientas de cómputo capaces de resolver problemas complejos

una vez modelados mediante las técnicas de programación lineal.

La importancia de los modelos de transbordo aumenta con las nuevas tendencias globales de

gestión de cadenas de abastecimiento, en las cuales se deben de optimizar los flujos

logísticos de productos teniendo en cuenta la importancia de minimizar los costos, asegurar

disponibilidad de unidades y reconociendo la importancia de los centros de distribución en la

búsqueda del equilibrio entre las proyecciones y la realidad de la demanda.


RESOLUCIÓN DE UN PROBLEMA DE TRANSBORDO MEDIANTE PROGRAMACIÓN LINEALPara poder resolver un problema de transbordo mediante programación lineal basta con

conocer una nueva familia de restricciones, las llamadas restricciones de balanceo. En un

problema de transbordo existen 3 clases de nodos, los nodos de oferta pura, los de demanda

pura y los nodos transitorios que posibilitan el transbordo y que deben de balancearse para

hacer que el sistema sea viable, es decir, que todas las unidades que ingresen a un nodo

sean iguales a las que salgan del mismo (unidades que salen + unidades que conserve el

nodo).EL PROBLEMA

Modelar mediante programación lineal el problema de transbordo esbozado en la siguiente

figura (dar click para ampliar).

TAHA - Investigación de Operaciones

La figura muestra una serie de nodos y sus respectivas rutas mediante las cuales se supone

distribuir las unidades de un producto, el número que lleva cada arco (flecha) representa el

costo unitario asociado a esa ruta (arco), y las cantidades que se ubican en los nodos

iniciales representan la oferta de cada planta, así como las cantidades de los nodos finales

representa la demanda de cada distribuidor.LAS VARIABLES DE DECISIÓN

En este caso como en la mayoría las variables de decisión deben representar la cantidad de

unidades enviadas por medio de cada ruta. Es muy aconsejable denotar cada nodo con un

número para simplificar la definición nominal de las variables.

Una vez renombrado cada nodo definiremos las variables:

XA,C = Cantidad de unidades enviadas desde P1 hacia T1

XA,D = Cantidad de unidades enviadas desde P1 hacia T2

XB,C = Cantidad de unidades enviadas desde P2 hacia T1

XB,D = Cantidad de unidades enviadas desde P2 hacia T2

XC,D = Cantidad de unidades enviadas desde T1 hacia T2

XC,E = Cantidad de unidades enviadas desde T1 hacia D1

XC,F = Cantidad de unidades enviadas desde T1 hacia D2

XD,F = Cantidad de unidades enviadas desde T2 hacia D2

XD,G = Cantidad de unidades enviadas desde T2 hacia D3

XE,F = Cantidad de unidades enviadas desde D1 hacia D2

XF,G = Cantidad de unidades enviadas desde D2 hacia D3RESTRICCIONES

Existen en este modelo 3 tipos de restricciones y están estrechamente relacionadas con los

tipos de nodos existentes, para un nodo oferta pura existe la restricción de oferta; para un

nodo demanda pura existe la restricción de demanda, y para un nodo transitorio y/o

transitorio de demanda existe la restricción de balance. Recordemos que los nodos

transitorios son aquellos que tienen rutas (arcos o flechas) de entrad y salida, y si además

este presenta un requerimiento de unidades se denomina transitorio de demanda.

Restricciones de Oferta:

XA,C + XA,D = 1000

XB,C + XB,D = 1200

Restricciones de demanda:

XD,G + XF,G = 500

Restricciones de balanceo para nodos únicamente transitorios:

Con estas restricciones aseguramos que todas las unidades que lleguen sean iguales a las

unidades que salgan.

XA,C + XB,C - XC,D - XC,E - XC,F = 0

XA,D + XB,D + XC,D - XD,F - XD,G = 0

Restricciones de balanceo para nodos transitorios con requerimientos:

Con estas restricciones aseguramos que todas las unidades que lleguen sean iguales a la

sumatoria de las unidades que salen más los requerimientos del nodo (demanda).

XC,E - XE,F = 800

XC,F + XD,F + XE,F - XF,G = 900FUNCIÓN OBJETIVO

En este caso la definición de la función objetivo se limita a la consignación de cada ruta con

su respectivo costo bajo el criterio "minimizar".

ZMIN = 3XA,C + 4XA,D + 2XB,C + 5XB,D + 7XC,D + 8XC,E + 6XC,F + 4XD,F + 9XD,G + 5XE,F + 3XF,G

INGRESANDO EL MODELO A WINQSB


SOLUCIÓN OBTENIDA MEDIANTE WINQSB


Esta es la representación grafica de la solución cuyo costo óptimo es de 20.700 unidades

monetarias


RESOLUCIÓN DE UN PROBLEMA DE REDES DE SUMINISTRO

EL PROBLEMA

Este es un problema propuesto en el texto "Investigación de Operaciones de TAHA" que hace

referencia a una red de gasoductos en la que los distintos nodos representan estaciones de

bombeo y recepción, los costos se encuentran en las rutas de la siguiente figura.

Investigación de Operaciones - TAHA

VARIABLES DE DECISIÓN

X12 = Cantidad de galones enviados desde la estación 1, hacia la estación 2











RESTRICCIONES

Restricciones de oferta y demanda:

X12 + X17 = 50000

X37 + X34 = 60000

X12 + X72 + X62 = 90000

X34 + X54 =20000

Restricciones de balance

X17 + X37 + X57 - X72 - X75 = 0

X56 - X65 - X62 = 0

X75 + X65 - X56 - X54 = 0FUNCIÓN OBJETIVO

ZMIN = 20X12 + 3X17 + 9X37 + 30X34 + 40X72 + 10X75 + 10X57 + 8X62 + 4X65 + 4X56 + 2X54

INGRESANDO EL MODELO A WINQSB




Esta es la representación grafica de la solución cuyo costo óptimo es de 2'660.000 unidades

monetarias


PROBLEMA DE LA RUTA MÁS CORTAYa el nombre de este tipo de problemas es bastante sugestivo, se trata si es necesario

decirlo de una modalidad de problemas de redes en el cual se debe determinar el plan de

rutas que genere la trayectoria con la mínima distancia total que una un nodo fuente con un

nodo destino, sin importar el número de nodos que existan entre estos.

Esta modalidad de problemas puede solucionarse como un modelo de transbordo normal, sin

embargo la principal sugerencia es la de establecer una oferta en el nodo fuente igual a una

unidad (1) y establecer una demanda en el arco destino igual a una unidad (1).EL PROBLEMA

Un minero ha quedado atrapado en una mina, la entrada a la mina se encuentra ubicada en

el nodo 1, se conoce de antemano que el minero permanece atrapado en el nodo 9, para

llegar a dicho nodo hay que atravesar una red de túneles que van conectados entre sí. El

tiempo de vida que le queda al minero sin recibir auxilio es cada vez menor y se hace

indispensable hallar la ruta de acceso al nodo 9 más corta. Las distancias entre nodos de la

mina se encuentran en la siguiente gráfica dadas en cientos de metros. Formule un modelo

de transbordo y resuelva mediante cualquier paquete de herramientas de investigación

operativa que permita establecer la ruta más corta para poder así auxiliar al minero.



El nombre de las variables en este caso poco importa, dado que de ser escogida para la

solución básica eso significa simplemente que será empleada como ruta para ir a rescatar al

minero, sin embargo nada tiene de malo el que se le pueda asociar con el envío de unidades

desde la entrada de la mina hacia el minero, por ende puede sugerirse este como nombre de

las variables. "Cantidad de unidades enviadas desde el nodo i hacia el nodo j".

X12 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 2




















RESTRICCIONES

Restricciones de Oferta y Demanda

Hay que recordar que el objetivo de este modelo es la consecución de un plan de ruta que

nos permita encontrar al minero lo más pronto posible al recorrer la distancia mínima

posible, por ende la clave para plantear el modelo como si fuese de transbordo es establecer

una demanda y oferta igual a la unidad (1).

X12 + X13 = 1

X69 + X79 + X89 = 1

Restricciones de Balance

X12 + X32 - X23 - X24 = 0

X13 + X23 - X32 - X34 - X35 = 0

X24 + X34 + X54 - X46 - X47 = 0

X35 - X54 - X56 – X57 – X58 = 0

X46 + X56 + X57 - X67 – X69 = 0

X67 + X47 + X57 + X87 – X76 – X78 – X79 = 0

X78 + X58 – X89 = 0

En palabras sencillas: "Todo lo que entra a cada nodo es igual a lo que sale de él"FUNCIÓN OBJETIVO

ZMIN = 4X12 + 2X13 + 2X23 + 7X24 + 4X32 + 9X34 + 6X35 + 1X46 + 5X47 + 2X54+ 4X56 +

3X57 + 2X58 + 1X67 + 5X69 + 4X76 + 3X78 + 5X79 + 2X87 + 7X89

INGRESANDO LOS DATOS A WINQSB




La ruta más corta para rescatar al minero tiene como distancia total 1600 metros (dado que

las distancias estaban dadas en cientos de metros) y es tal como se muestra en la siguiente

gráfica.

Bryan Antonio Salazar Lopez

Sin embargo WinQSB cuenta con una metodología mucho más sencilla de resolución de

algoritmos de ruta más corta, metodología que explicaremos más adelante, de todas formas

hemos encontrado como aplicando debidamente la razón y un algoritmo conocido como el de

transbordo podemos solucionar problemas distintos en teoría.

VARIABLES BINARIAS - EL CASO DE LA BAUXITA

Las variables binarias son un artificio matemático que permiten que modelos de

programación no lineal se resuelvan como tal. El buen uso de las variables binarias se

convierten en una poderosa herramienta matemática para plantear problemas más

complejos que los que habitualmente se resuelven acudiendo a las variables continuas.

Como su nombre lo indica una variable binaria es aquella que puede tomar valores ya sea de

cero (0) ó uno (1), esta idea tan simple puede convertirse en una ayuda fundamental tanto

para la modelación como para la resolución de los problemas. Un ejemplo de ello puede ser

el caso en el que determinado producto puede producirse ó no, también un centro de

distribución que puede abrirse ó no.

El fundamento económico que más se presta para ser resuelto mediante el uso de variables

binarias es el de Costo Fijo , el cual es fijo por cantidad y variable por unidad pero depende

si el recurso relacionado al costo se usa ó no, por ejemplo el costo de arrendamiento de una

bodega el cual se cobrará a partir de la producción de cualquier unidad, pero no se cobrará si

no se produce (no se hace uso de la bodega) unidad alguna.

Otra aplicación de las variables binarias es cuando en el sistema existen restricciones

excluyentes (condicionadas la una de la otra), es decir, que a partir de la satisfacción de una

condición no se hace necesario el cumplimiento de la otra condición. Por ejemplo si se desea

lanzar una producción de calzado en el cual se tenga que decidir alquilar un equipo de

inyección y en el mercado existen dos alternativas de maquinarias pero solo una es

contratable, en este caso se planeará la producción con las capacidades y costos asociados a

cada equipo, sin embargo ambas restricciones son excluyentes, es decir solo se aplicará una

de las dos.

EL CASO DE LA BAUXITAEl caso de la BAUXITA es un ejemplo preparado por el Pr. Carlos Julio Vidal Holguín en el cual

se plantea un ejercicio aplicable a la cadena de abastecimiento en el cual hay que resolver

un modelo de transbordo para lograr producir aluminio. Los resultados del problema deben

de determinar las rutas que se emplearán para realizar la distribución de materias primas y

producto terminado, además de determinar que plantas de procesamiento operan o no (para

lo cual hay que hacer uso de las variables binarias) con el objetivo de satisfacer todas los

requerimientos de los clientes al menor costo total posible.EL PROBLEMA

Una compañía multinacional de aluminio tiene depósitos de bauxita (materia prima) en tres

lugares del mundo A, B y C. Tiene además cuatro plantas donde la bauxita se convierte en

alúmina (un producto intermedio), en lugares B, C, D y E. También tiene plantas de

esmaltado en los lugares D y E. El proceso de conversión de la bauxita en alúmina es

relativamente poco costoso. El esmaltado, sin embargo, es costoso puesto que se requiere

de un equipo electrónico especial. Una tonelada de alúmina produce 0.4 toneladas de

aluminio terminado. Los datos siguientes están disponibles.

Conversión de Bauxita en alúmina

Proceso de esmaltado

Las ventas anuales de aluminio terminado son de 1000 toneladas (ton) en la planta D y 1200

ton en la planta E.

Costos de transporte en $/ton de Bauxita

Los números que aparecen ordinalmente enseguida de cada fuente y destino serán utilizados

para definir las variables.

Costos de transporte de alúmina, en $/ton de alúmina

Los lingotes de producto terminado no se transportan entre D y E y viceversa. Formule y

resuelva un modelo de optimización para determinar la mejor red - configuración y diseño de

la cadena de abastecimiento presentada.

Note que existe un problema de determinar cuáles plantas de alúmina deben ser abiertas.


Las variables de decisión se plantearán mayoritariamente en relación a las unidades a

transportar desde un nodo hacia el otro.

Una muy buena manera de llamar a las variables es sugerido en la anterior gráfica (X(ij) -

Y(jk) - W(j)). Por ende las variables de decisión serán:

Xij = Cantidad de toneladas de bauxita a transportar desde la mina i hacia la planta de

alúmina j por año; donde i {A,B,C} y j {B,C,D,E}.

Yjk = Cantidad de toneladas de alúmina a transportar desde la planta de alúmina jhacia la

planta de esmaltado k por año; donde j {B,C,D,E} y k {D,E}.

Hasta este punto todo es normal, sin embargo es necesario determinar una serie de variables

binarias que indicarán que plantas de alúmina se abrirán o no, además estas estarán

asociadas a los costos fijos generados por la apertura de cada planta en la función objetivo.

Wj = 1, si la planta j se abre, de lo contrario 0; donde j {B,C,D,E}. (Variable Binaria).RESTRICCIONES

Restricciones por capacidad anual de cada mina de Bauxita

Mina A: XAB + XAC + XAD + XAE ≤ 36000

Mina B: XBB + XBC + XBD + XBE ≤ 52000

Mina C: XCB + XCC + XCD + XCE ≤ 28000

Es decir que todos los envíos efectuados desde cada mina hacia cualquiera de los cuatro

destinos no puede exceder la capacidad de cada mina.

Restricciones por capacidad anual de procesamiento de Bauxita en cada planta de

alúmina

Planta B: XAB + XBB + XCB ≤ 40000WB

Planta C: XAC + XBC + XCC ≤ 20000WC

Planta D: XAD + XBD + XCD ≤ 30000WD

Planta E: XAE + XBE + XCE ≤ 80000WE

Estas restricciones aseguran que los enviados realizados desde cualquiera de las minas hacia

cada planta específica sean menores o iguales a los que cada planta pueda procesar,

además la capacidad de cada planta va acompañada de la variable binaria que le

corresponde, es decir que como el valor que puede adquirir cada variable binaria es 1 o 0,

cuando esta sea 1 (la planta se abre) la capacidad se multiplicará por uno (1) es decir que no

se altera, pero cuando esta variable adquiera el valor de 0 (la planta no se abre) la capacidad

se multiplicará por cero (0) es decir que la capacidad quedará reducida a 0 por ende no se

podrán enviar unidades a esa planta.

Restricciones por capacidad anual de procesamiento de alúmina en cada planta de

esmaltado

En este conjunto de restricciones no se utilizarán las variables correspondientes a las de

envío de Bauxita (X) sino las correspondientes al envío de Alúmina (Y), en las restricciones de

balanceo representaremos la equivalencia dado el rendimiento que tiene la Bauxita de cada

mina para convertirse en alúmina.

Planta D: YBD + YCD + YDD + YED ≤ 4000

Planta E: YBE + YCE + YDE + YEE ≤ 7000

Es decir que todos los envíos de alúmina hacia las plantas de esmaltado no superen cada una

de las capacidades de procesamiento de las mismas.

Restricciones por las ventas anuales de aluminio terminado en cada planta de

esmaltado

En este caso se debe recordar que existe una equivalencia entre la alúmina y el aluminio

terminado (equivalencia determinada por el rendimiento de la alúmina para fabricar aluminio

que es del 40%, "una tonelada de alúmina produce 0.4 toneladas de aluminio terminado").

Entonces podemos usar las variables de toneladas de alúmina con su debida equivalencia

para elaborar las restricciones de demanda.

Planta D: 0,4(YBD + YCD + YDD + YED) = 1000

Planta E: 0,4(YBE + YCE + YDE + YEE) = 1200

Restricciones de balance

Como lo mencionamos en módulos anteriores las restricciones de balance tienen lugar en los

nodos de transbordo, es decir, en los nodos que no son de oferta o demanda pura. Como en

este nodo entran variables que representan toneladas de Bauxita y salen variables que

representan alúmina se debe de aplicar el rendimiento correspondiente para realizar la

conversión.

0.060XAB + 0.080XBB + 0.062XCB = YBD + YBE

0.060XAC + 0.080XBC + 0.062XCC = YCD + YCE

0.060XAD + 0.080XBD + 0.062XCD = YDD + YDE

0.060XAE + 0.080XBE + 0.062XCE = YED + YEE

Al introducir estos datos en software como WinQSB debemos saber que al lado derecho del

signo igual o el signo de la inecuación no deben ir variables, por ende estas pasan a restar al

lado izquierdo, igualando la ecuación a cero (0).

Restricciones obvias

Las cuales determinan la naturaleza de las variables

Xij ≥ 0 ∀ i,j

Xjk ≥ 0 ∀ j,k

Wj ∈ {1,0} ∀ jFUNCIÓN OBJETIVO

Para elaborar la función objetivo hay que tener en cuenta los costos de explotación en cada

mina, los costos de procesamiento de bauxita en las plantas de alúmina, los costos

procesamiento en cada planta de esmaltado, así como los costos de envío asociados a cada

ruta y determinantemente los costos relacionados con las variables binarias los cuales son

los costos fijos condicionados a si la planta se abre o no.

ZMIN = 820XAB + 2430XAC + 930XAD + 2340XAE + 370XBB + 990XBC + 580XBD + 1870XBE +

2170XCB + 550XCC + 1160XCD + 1480XCE + 9050YBD + 7040YBE + 9440YCD + 6460YCE +

8880YDD + 7195YDE + 10205YED +

5440YEE + 3000000WB+ 2500000WC + 4800000WD + 6000000WE


Dar click a la imagen para ver más grande

RESULTADOS ARROJADOS POR WINQSB

Con un costo asociado de $ 87'455.600

El anterior problema resuelto es un ejemplo introductorio a la modelación a gran escala y a la

aplicación que tienen la investigación de operaciones dentro de las nuevas tendencias

de Cadena de Abastecimiento.

PROBLEMAS DE ASIGNACIÓN

El problema de asignación es una variación del problema original de transporte, variación en

la cual las variables de decisión X(i,j) solo pueden tomar valores binarios, es decir ser cero (0)

o uno (1) en la solución óptima, lo que supone que la oferta y la demanda estan

perfectamente alineadas, de hecho ambas son iguales a uno (1).

http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/log%C3%ADstica/

Múltiples son los casos en los que como ingenieros industriales podemos hacer uso del

problema de asignación para resolver diversas situaciones, entre los que cabe mencionar se

encuentran la asignación de personal a maquinas, herramientas o puestos de trabajos,

horarios a maestros, candidatos a vacantes, huéspedes a habitaciones, comensales a mesas,

vendedores a zonas territoriales etc...

En el modelo de asignación la idea fundamental de resolución es ¿qué fuente satisface mejor

el destino?, y dado que hemos asociado el modelo a una gran diversidad de circunstancias

esta pregunta puede plantearse en múltiples contextos, como ¿qué candidato es el idóneo

para la vacante?, o ¿qué personal es el indicado para la línea productiva?, o ¿qué personal es

el mejor para ejecutar determinada tarea?. Una característica particular del modelo de

asignación es que para su resolución no se hace necesario que el número de fuentes sea

igual al número de destinos, lo cual es muy común en la vida real teniendo en cuenta su

aplicación, pues generalmente la cantidad de aspirantes es exageradamente superior al

número de vacantes (lógicamente haciendo referencia a la aplicación del modelo al contexto

de oferta y demanda laboral).

MÉTODO HÚNGAROApartándonos un poco de la idea expresada en módulos anteriores respecto a la facilidad de

resolver problemas atinentes a la investigación operativa en especial aquellos de transporte

mediante el uso de herramientas tecnológicas como lo son WinQSB, LINGO, TORA, STORM,

Excel etc.. vale la pena ya sea para fines académicos o de cultura ingenieril realizar la

resolución del problema de asignación mediante el algoritmo que se creó para tal fin, como

lo es el Método Húngaro.

El método Húngaro es un método de optimización de problemas de asignación, conocido

como tal gracias a que los primeros aportes al método clásico definitivo fueron de Dénes

König y Jenő Egerváry dos matemáticos húngaros.ALGORITMO HÚNGARO, PASO 1

Antes que nada cabe recordar que el método húngaro trabaja en una matriz de costos n*m

(en este caso conocida como matriz m*m, dado que el número de filas es igual al número de

columnas n = m), una vez construida esta se debe encontrar el elemento más pequeño en

cada fila de la matriz.ALGORTIMO HÚNGARO, PASO 2

Una vez se cumple el procedimiento anterior se debe construir una nueva matriz n*m, en la

cual se consignarán los valores resultantes de la diferencia entre cada costo y el valor

mínimo de la fila a la cual cada costo corresponde (valor mínimo hallado en el primer paso).ALGORTIMO HÚNGARO, PASO 3

Este paso consiste en realizar el mismo procedimiento de los dos pasos anteriores referidos

ahora a las columnas, es decir, se halla el valor mínimo de cada columna, con la diferencia

que este se halla de la matriz resultante en el segundo paso, luego se construirá una nueva

matriz en la cual se consignarán los valores resultantes de la diferencia entre cada costo y el

valor mínimo de la columna a la cual cada costo corresponde, matriz llamada "Matriz de

Costos Reducidos".ALGORITMO HÚNGARO, PASO 4

A continuación se deben de trazar lineas horizontales o verticales o ambas (unicamente de

esos tipos) con el objetivo de cubrir todos los ceros de la matriz de costos reducidos con el

menor número de lineas posibles, si el número de lineas es igual al número de filas o

columnas se ha logrado obtener la solución óptima (la mejor asignación según el contexto de

optimización), si el número de lineas es inferior al número de filas o columnas se debe de

proceder con el paso 5.

ALGORITMO HÚNGARO, PASO 5

Este paso consiste en encontrar el menor elemento de aquellos valores que no se encuentran

cubiertos por las lineas del paso 4, ahora se restará del restante de elementos que no se

encuentran cubiertos por las lineas; acontinuación este mismo valor se sumará a los valores

que se encuentren en las intersecciones de las lineas horizontales y verticales, una vez

finalizado este paso se debe volver al paso 4.

RESOLUCIÓN DE UN PROBLEMA DE ASIGNACIÓN MEDIANTE EL MÉTODO HÚNGAROEL PROBLEMA

La compañía de manufactura "Jimenez y Asociados" desea realizar una jornada de

mantenimiento preventivo a sus tres máquinas principales A, B y C. El tiempo que demanda

realizar el mantenimiento de cada máquina es de 1 día, sin embargo la jornada de

mantenimiento no puede durar más de un día, teniendo en cuenta que la compañía cuenta

con tres proveedores de servicios de mantenimiento debe de asignarse un equipo de

mantenimiento a cada máquina para poder cumplir con la realización del mantenimiento

preventivo. Teniendo en cuenta que según el grado de especialización de cada equipo

prestador de servicios de mantenimiento el costo de la tarea varía para cada máquina en

particular, debe de asignarse el equipo correcto a la máquina indicada con el objetivo de

minimizar el costo total de la jornada. Los costos asociados se pueden observar en la

siguiente tabla:

Bryan Antonio Salazar Lopez

PASO 1

Encontramos el menor elemento de cada fila


PASO 2

Construimos una nueva matriz con las diferencias entre los valores de la matriz original y el

elemento menor de la fila a la cual corresponde.


PASO 3

En la matriz construida en el paso anterior se procede a efectuar el paso 1 esta vez en

relación a las columnas, por ende escogemos el elemento menor de cada columna.

Igualmente construimos una nueva matriz con la diferencia entre los valores de la matriz 2 y

ele elemento menor de la columna a la cual corresponde cada valor.


PASO 4

En este paso trazaremos la menor cantidad de combinaciones de lineas horizontales y

verticales con el objetivo de cubrir todos los ceros de la matriz de costos reducidos.


Como se puede observar el menor número de lineas horizontales y/o verticales necesarias

para cubrir los ceros de las matriz de costos reducidos es igual a 2, por ende al ser menor

que el número de filas o columnas es necesario recurrir al paso 5.PASO 5

En este paso seleccionamos el menor elemento de los elementos no subrayados.

Luego se procede a restarse de los elementos no subrayados y a adicionarse a los elementos

ubicados en las intersecciones de las lineas, en este caso existe una única intersección (3).


Ahora ya efectuado este paso pasamos al paso 4.


Ahora observamos como se hace necesario trazar tres lineas (la misma cantidad de filas o

columnas de la matriz) por ende se ha llegado al tabulado final, en el que por simple

observación se determina las asignaciones óptimas.


Por ende la asignación que representa el menor costo para la jornada de mantenimiento

preventivo determina que el Equipo 1 realice el mantenimiento de la Máquina 1, el Equipo 2

realice el mantenimiento de la Máquina 3 y el Equipo 3 realice el mantenimiento de la

Máquina 2, jornada que tendrá un costo total de 17 unidades monetarias.

RESOLUCIÓN DE UN PROBLEMA DE ASIGNACIÓN MEDIANTE PROGRAMACIÓN LINEALEL PROBLEMA

La compañía de manufactura "Jimenez y Asociados" desea realizar una jornada de

mantenimiento preventivo a sus tres máquinas principales A, B y C. El tiempo que demanda

realizar el mantenimiento de cada máquina es de 1 día, sin embargo la jornada de

mantenimiento no puede durar más de un día, teniendo en cuenta que la compañía cuenta

con tres proveedores de servicios de mantenimiento debe de asignarse un equipo de

mantenimiento a cada máquina para poder cumplir con la realización del mantenimiento

preventivo. Teniendo en cuenta que según el grado de especialización de cada equipo

prestador de servicios de mantenimiento el costo de la tarea varía para cada máquina en

particular, debe de asignarse el equipo correcto a la máquina indicada con el objetivo de

minimizar el costo total de la jornada. Los costos asociados se pueden observar en la

siguiente tabla:


Las variables de decisión de este tipo de problemas es igual a las variables de cualquier

modelo de transporte tradicional, es decir variables X i,j donde i {Equipo de mantenimiento

1,2,3} y j {Máquina 1,2,3}, y corresponden a variables binarias en las cuales el valor 1

significa la asignación de un equipo de mantenimiento a una máquina en particular.RESTRICCIONES

Dado que un equipo de mantenimiento no puede ser asignado a más de una maquinaria,

esta caracteristica debe de restringirse mediante las siguientes inecuaciones.

X1,1 + X1,2 + X1,3 = 1

X2,1 + X2,2 + X2,3 = 1

X3,1 + X3,2 + X3,3 = 1

Además debe restringirse el hecho de que cada máquina solo requiere de un equipo de

mantenimiento, por ende

X1,1 + X2,1 + X3,1 = 1

X1,2 + X2,2 + X3,2 = 1

X1,3 + X2,3 + X3,3 = 1

Además se hace necesario que para efectos de resolución en cualquier paquete de

herramientas se especifique que esta variables corresponden al conjunto de los enteros (por

obvias razones) y que deben ser mayores que cero (dado que es un problema de

minimización esta restricción se hace muy necesario).

Xi,j ≥ 0

Xi,j ∈ {Z}FUNCIÓN OBJETIVO

ZMIN = 10X1,1 + 9X1,2 + 5X1,3 + 9X2,1 + 8X2,2 + 3X2,3 + 6X3,1 + 4X3,2 + 7X3,3


RESULTADOS OBTENIDO MEDIANTE EL WINQSB





RESOLUCIÓN DE UN PROBLEMA DE ASIGNACIÓN MEDIANTE WINQSB - NETWORK MODELINGLa facilidad de resolver un problema de asignación mediante WinQSB es aún mayor a la que

se incurre mediante programación lineal, y esta metodología justifica el pensar en que el

método húngaro es sumamente anacrónico unicamente contemplado para fines históricos y

académicos. En el módulo NETWORK MODELING del paquete de herramientas WinQSB se

puede resolver el modelo tan solo traspasando los costos de una matriz n*m a otra que

brinda el módulo n*m.INGRESANDO LOS DATOS A WINQSB - NETWORK MODELING

RESULTADOS OBTENIDOS MEDIANTE WINQSB - NETWORK MODELING





De esta manera se hace evidente cual es la alternativa predilecta para resolver problemas de

asignación.

TEORÍA DE REDESLa modelación de redes permite la resolución de múltiples problemas de programación

matemática mediante la implementación de algoritmos especiales creados para tal fin,

conocidos como Algoritmos de optimización de redes. Dentro de los problemas más

comunmente resueltos mediante la modelación de redes se encuentran los ya vistos modelos

de transporte, transbordo además de los muy conocidos modelos de determinación de

cronograma de actividades para proyectos como lo son el PERT y el CPM.

CONCEPTOS BÁSICOS EN TEORÍA DE REDESGráfica: Una gráfica es una serie de puntos llamados nodos que van unidos por unas lineas

llamadas ramales o arcos.

Red: Una red es una gráfica que presenta algún tipo de flujo en sus ramales. Por ejemplo

una gráfica cuyo flujo en sus ramales sea la electricidad es una red eléctrica. En las redes se

usa una simbología específica para denotar su tamaño y elementos que la constituyen, dicha

notación es la (N, A) donde N representa el número de nodos que contiene la red y A

representa el número de arcos o ramales.


Cadena: Una cadena corresponde a una serie de elementos ramales que van de un nodo a

otro. En el siguiente caso se resalta una cadena que va desde el nodo 1 hasta el nodo 7 y

que se compone por los elementos [1-4, 4-7].

Ruta: Una ruta corresponde a los nodos que constituyen una cadena, en el siguiente caso [1,

4, 7].


Ciclo: Un ciclo corresponde a la cadena que une a un nodo con sigo mismo, en el siguiente

ejemplo el ciclo esta compuesto por la cadena [4-2, 2-5, 5-7, 7-4].


Ramal orientado: Un ramal o arco orientado es aquel que tiene un sentido determinado, es

decir que posee un nodo fuente y un nodo destino.


Gráfica orientada: Una gráfica orientada es aquella en la cual todos sus ramales se

encuentran orientados.


Árbol: Un árbol es una gráfica en la cual no existen ciclos, como el siguiente ejemplo.

Árbol de expansión: Un árbol de expansión es aquel árbol que enlaza todos los nodos de la

red, de igual manera no permite la existencia de ciclos.


Nodo fuente: El nodo fuente es aquel nodo en el cual todos sus ramales se encuentran

orientados hacia afuera.

Nodo destino: El nodo destino es aquel nodo en el cual todos sus ramales se encuentran

orientados hacia él.


ALGORITMO DEL ÁRBOL DE EXPANSIÓN MÍNIMAEl algoritmo del árbol de expansión mínima es un modelo de optimización de redes que

consiste en enlazar todos los nodos de la red de forma directa y/o indirecta con el objetivo de

que la longitud total de los arcos o ramales sea mínima (entiéndase por longitud del arco una

cantidad variable según el contexto operacional de minimización, y que puede bien

representar una distancia o unidad de medida).

Sean

N = {1,2,3,...,n} el conjunto de nodos de la red.

Ck= Conjunto de nodos que se han enlazado de forma permanente en la iteración k

Čk= Conjunto de nodos que hacen falta por enlazarse de forma permanente.

PASO CERO (0): CONCEPTUALIZACIÓN DEL ALGORITMO

Definir los conjuntos C0 = {ø} y Č0 = {N}, es decir que antes del paso 1 no se han enlazado

de forma permanente nodo alguno, y por ende el conjunto que representa a los nodos que

hacen falta por enlazarse de forma permanente es igual a la cantidad de nodos que existen

en la red.PASO 1:

Se debe de escoger de manera arbitraria un nodo en el conjunto Č0 llamado i el cual será el

primer nodo permanente, a continuación se debe de actualizar el conjunto C1 = {i}, que

significa que al tiempo en que el conjunto C1 gana el elemento i el conjunto Č0 pierde el

elemento i por ende ahora será igual a Č1 = N - {i}, además se debe actualizar el subíndice

de los conjuntos k, el cual ahora será igual a 2.PASO 2: PASO GENERAL "K"

Se debe de seleccionar un nodo j del conjunto ČK-1 ("k-1" es el subíndice que indica que se

está haciendo referencia al conjunto de la iteración inmediatamente anterior) el cual tenga el

arco o ramal con menor longitud con uno de los nodos que se encuentran en el conjunto de

nodos de enlace permanente CK-1. Una vez seleccionado se debe de enlazar de forma

permanente lo cual representa que pasa a formar parte del conjunto de enlaces permanentes

y deja de formar parte del conjunto que todavía se debe conectar para lograr la expansión. Al

actualizar el algoritmo en este paso los conjuntos deben de quedar de la siguiente forma.

CK = CK-1 + {j} mientras que ČK = ČK-1 - {j}

El paso general que define k que al mismo tiempo representa a las iteraciones debe de

ejecutarse toda vez que el conjunto ČK no sea vacío, cuando este conjunto sea igual a vacío

se tendrá el arbol de expansión mínima.

El entendimiento del algoritmo desde el punto de vista algebraico no es quizá el más simple,

sin embargo mediante el ejemplo gráfico se verá que es un algoritmo muy sencillo de

elaborar.RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE EXPANSIÓN MÍNIMA

EL PROBLEMA

La ciudad de Cali cuenta con un nuevo plan parcial de vivienda el cual contará con la

urbanización de más de 7 proyectos habitacionales que se ubicarán a las afueras de la

ciudad. Dado que el terreno en el que se construirá no se encontraba hasta ahora dentro de

las zonas urbanizables de la ciudad, el acueducto municipal no cuenta con la infraestructura

necesaria para satisfacer las necesidades de servicios públicos en materia de suministro de

agua. Cada uno de los proyectos de vivienda inició la construcción de un nodo de acueducto

madre, el cual cuenta con las conexiones de las unidades de vivienda propias de cada

proyecto (es decir que cada nodo madre solo necesita estar conectado con un ducto madre

del acueducto municipal para contar con su suministro). El acueducto municipal al ver la

situación del plan parcial debe de realizar las obras correspondientes a la instalación de

ductos madres que enlacen todos los nodos del plan con el nodo Meléndez (nodo que se

encuentra con suministro de agua y que no pertenece al plan parcial de vivienda, además es

el más cercano al mismo), la instalación de los ductos implica obras de excavación, mano de

obra y costos de los ductos mismos, por lo cual optimizar la longitud total de los enlaces es

fundamental. Las distancias existentes (dadas en kilometros) correspondientes a las rutas

factibles capaces de enlazar los nodos del plan parcial se presentan a continuación. Además

la capacidad de bombeo del nodo Meléndez es más que suficiente para satisfacer las

necesidades de presión que necesita la red madre.

Problema planteado por, Bryan Antonio Salazar López

El acueducto municipal le contacta a usted para que mediante sus conocimientos en teoría

de redes construya una red de expansión que minimice la longitud total de ductos y que

enlace todos los nodos del plan parcial de vivienda.

PASO 0:

Se definen los conjuntos iniciales C0 = {ø} que corresponde al conjunto de nodos enlazados

de forma permanente en la iteración indicada en el subíndice y Č0 = {N = 1,2,3,4,5,6,7,8}

que corresponde al conjunto de nodos pendientes por enlazar de manera permanente en la

iteración indicada en el subíndice.

PASO 1:

Se debe definir de manera arbitraria el primer nodo permanente del conjunto Č0, en este

caso escogeremos el nodo 1 (puede ser cualquier otro), que algebraicamente se representa

con la letra i, se procede a actualizar los conjuntos iniciales, por ende C1 = {i} = {1} y Č0 =

{N - i} = {2,3,4,5,6,7,8}, actualizamos k por ende ahora será igual a 2.

PASO 2:

Ahora se debe seleccionar el nodo j del conjunto ČK-1 (es decir del conjunto del paso 1) el cual

presente el arco con la menor longitud y que se encuentre enlazado con uno de los nodos de

enlace permanente del conjunto Ck-1 en el cual ahora solo se encuentra el nodo 1 (es decir

que se debe de encontrar un nodo que tenga el arco de menor longitud enlazado al nodo 1).


Los arcos o ramales de color naranja representan los arcos que enlazan el conjunto ČK-1 (es

decir del conjunto del paso 1, recordemos que K en este paso es igual a 2, por ende ČK-1= Č1)

con los nodos de enlace permanente del conjunto Ck-1 en el cual ahora solo se encuentra el

nodo 1, por ende ahora solo falta escoger el de menor longitud, que en este caso es el arco

cuya longitud es 2, que enlaza de forma permanente ahora el nodo 2.

Al actualizar los conjuntos quedan así:

C2 = {1,2} y Č2 = {3,4,5,6,7,8}

Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración. Ahora se

seleccionará un nuevo nodo j del conjunto Č2que presente el enlace (ramal o arco) de menor

longitud con los nodos que se encuentran en el conjunto C2.


Los arcos de color naranja representan los enlaces posibles y dado que existe empates entre

las menores longitudes se elige de manera arbitraria, en este caso se representa nuestra

elección con un arco de color verde, enlazando de forma permanente ahora el nodo 4.


C3 = {1,2,4} y Č3 = {3,5,6,7,8}

Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración.


Lo que representan los arcos naranja y verde es ya conocido, ahora la linea azul interrumpida

irá trazando nuestro árbol de expansión final. Dado a que el arco menor es el de longitud 3,

ahora se enlazará de manera permanente el nodo 5.


C4 = {1,2,4,5} y Č4 = {3,6,7,8}



Ahora se enlazará de manera permanente el nodo 7.


C5 = {1,2,4,5,7} y Č5 = {3,6,8}



Ahora se enlazará de manera permanente el nodo 6.


C6 = {1,2,4,5,7,6} y Č6 = {3,8}



Se rompen los empates de forma arbitraria, ahora se enlazará de manera permanente el

nodo 3.


C7 = {1,2,4,5,7,6,3} y Č7 = {8}

Ahora se procede a actualizar k ya que se procede a efectuar la última iteración.


ahora se enlazará de manera permanente el nodo 8.


C8 = {1,2,4,5,7,6,3,8} = {N} y Č8 = {ø}

Por ende se ha llegado al árbol de expansión mínima


Árbol que presenta una longitud total minimizada de 21 kilometros de ductos.RESOLUCIÓN DEL PROBLEMA DEL ÁRBOL EXPANSIÓN MÍNIMA MEDIANTE WINQSB

Como hemos mencionado en módulos anteriores la existencia de herramientas de resolución

de problemas de programación matemática como WinQSB dejan que el aprendizaje de la

resolución manual de los algoritmos de redes se justifique solo para fines académicos o de

profundización. Por ende una vez vista la metodología manual de resolución del algoritmo

atinente al árbol de expansión mínima se hace necesario en aras de eficiencia mostrar la

resolución de este tipo de problemas mediante WinQSB.

El primer paso para resolver un problema de transporte mediante WinQSB es ingresar al

módulo Network Modeling.

EL PROBLEMA

La ciudad de Cali cuenta con un nuevo plan parcial de vivienda el cual contará con la

urbanización de más de 7 proyectos habitacionales que se ubicarán a las afueras de la

ciudad. Dado que el terreno en el que se construirá no se encontraba hasta ahora dentro de

las zonas urbanizables de la ciudad, el acueducto municipal no cuenta con la infraestructura

necesaria para satisfacer las necesidades de servicios públicos en materia de suministro de

agua. Cada uno de los proyectos de vivienda inició la construcción de un nodo de acueducto

madre, el cual cuenta con las conexiones de las unidades de vivienda propias de cada

proyecto (es decir que cada nodo madre solo necesita estar conectado con un ducto madre

del acueducto municipal para contar con su suministro). El acueducto municipal al ver la

situación del plan parcial debe de realizar las obras correspondientes a la instalación de

ductos madres que enlacen todos los nodos del plan con el nodo Meléndez (nodo que se

encuentra con suministro de agua y que no pertenece al plan parcial de vivienda, además es

el más cercano al mismo), la instalación de los ductos implica obras de excavación, mano de

obra y costos de los ductos mismos, por lo cual optimizar la longitud total de los enlaces es

fundamental. Las distancias existentes (dadas en kilometros) correspondientes a las rutas

factibles capaces de enlazar los nodos del plan parcial se presentan a continuación. Además

la capacidad de bombeo del nodo Meléndez es más que suficiente para satisfacer las

necesidades de presión que necesita la red madre.

Problema planteado por Bryan Antonio Salazar López

INGRESANDO A WINQSB

El primer paso para resolver un problema de transporte mediante WinQSB es ingresar al

módulo Network Modeling.

WinQSB - Bryan Antonio Salazar López

Luego debemos seleccionar la opción Minimal Spanning Tree (Árbol de Expansión Mínima).

Además en este submenú debemos de especificar el nombre del problema y el número de

nodos. En nuestro caso el número de nodos es igual a 8, luego click en OK.

Una vez se realiza el paso anterior se abrirá una ventana en la cual aparecerá la siguiente

matriz:


En esta matriz se deben de consignar los valores de los ramales que unen las conexiones

entre los nodos correspondientes, según el contexto de nuestro problema se deben de

consignar las distancias entre los nodos si es que dichas conexiones existen de lo contrario

en caso que la conexión no exista se debe dejar la celda en blanco. Hay que tener en cuenta

que las distancias entre los nodos en este caso son exactamente conmutativas, es decir que

si el nodo fuente es 2 y el destino es 4 la distancia existente entre estos es exactamente

igual a la distancia existente entre un nodo fuente 4 y un nodo destino 2, sin embargo esta

propiedad debe de especificarse en la matriz consignando los valores correspondientes a una

conexión dos veces, es decir en la celda [From 1 - To 4] se debe de consignar la distancia 6,

además debe de consignarse la misma distancia en la celda [From 4 - To 1].


Luego damos click en Solve and Analize y tendremos la siguiente ventana solución

inmediatamente.


Podemos cotejar los resultados con los obtenidos de manera manual, 21 kilometros de

ductos es la distancia total una vez ejecutado el algoritmo del Árbol de Expansión Mínima.

ALGORTIMO DE LA RUTA MÁS CORTAEl nombre que distingue este conjunto de problemas de por sí es bastante sugestivo, existen

de forma manual algoritmos capaces de resolver tanto problemas de redes que presentan

ciclos como de redes que no, entre los más conocidos se encuentran los algoritmos de

Dijkstra y Floyd siendo el segundo más general que el primero. Sin embargo la complejidad

de los algoritmos, en la práctica la complejidad que alcanzan las redes a ser resueltas

mediante el algoritmo de la ruta más corta, y las herramientas de resolución de problemas

de programación matemática hacen que la enseñanza de dichos algoritmos manuales sea

muy ineficiente.

Ya en un módulo anterior Problema de Transbordo se ha planteado la resolución del

algoritmo de la ruta más corta mediante programación lineal, por esta razón en este espacio

nos enfocaremos en efectuar la solución mediante WinQSB con la facilidad que caracteriza al

software.

http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/problema-de-transbordo/

RESOLUCIÓN DEL ALGORITMO DE LA RUTA MÁS CORTA MEDIANTE WINQSB

El módulo del WinQSB que permite la resolución del algoritmo de la ruta más corta es el

Network Modeling, el cual utiliza una interfaz muy sencilla en forma de matriz en la cual hay

que ingresar el valor de los ramales (dependiendo del contexto este valor puede representar

distancias, tiempo, costos etc...) correspondiente a cada relación de un nodo con otro.

EL PROBLEMA

Un minero ha quedado atrapado en una mina, la entrada a la mina se encuentra ubicada en

el nodo 1, se conoce de antemano que el minero permanece atrapado en el nodo 9, para

llegar a dicho nodo hay que atravesar una red de túneles que van conectados entre sí. El

tiempo de vida que le queda al minero sin recibir auxilio es cada vez menor y se hace

indispensable hallar la ruta de acceso al nodo 9 más corta. Las distancias entre nodos de la

mina se encuentran en la siguiente gráfica dadas en cientos de metros. Resuelva mediante

cualquier paquete de herramientas de investigación operativa que permita establecer la ruta

más corta para poder así auxiliar al minero.

Problema planteado por Bryan Antonio Salazar López

PASO A PASO

Primero se debe ingresar al módulo Network Modeling del paquete WinQSB, una vez nos

encontremos en este aparecerá el menú que se muestra en la siguiente gráfica, menú en el

cual tendremos que seleccionar la opción Shortest Path Problem(Problema de la ruta más

corta).


Además en este menú emergente debemos de ingresar la cantidad de nodos que conforman

la red del problema y tenemos la posibilidad de asignarle un nombre al mismo, en nuestro

caso la cantidad de nodos de la red es igual a 9; click en OK y aparecerá la siguiente

ventana.


En esta ventana se debe ingresar la magnitud de cada ramal correspondiente a cada relación

entre los nodos, tal como veremos a continuación.


Damos click en Solve and Analize y tendremos un menú emergente en el cual tendremos que

seleccionar el nodo fuente y el nodo destino, tal como se muestra en la siguiente gráfica.


Una vez efectuada la selección tendremos la opción de ver el tabulado final y la opción de

ver un paso a paso gráfico; para el tabulado final click en SOLVE y para el paso a paso click

en SOLVE AND DISPLAY STEPS.


Podemos cotejar la solución que obtuvimos al plantear este problema como un modelo de

transbordo con esta solución. La eficiencia se encuentra determinada en escoger la

herramienta adecuada para resolver el problema planteado.

Documents

1 Investigacion de Operaciones