UPVM

UPVM

Ejercicios resueltos de la materia de Investigación de Operaciones

Unidad 1

Problema 1

Una ensambladora de automóviles y camiones, consta de cuatro departamentos que a continuación se enumeran:

1. Estampado de planchas metálicas

1. Armado de motores

1. Montaje de automóviles

1. Montaje de camiones

El departamento 1 puede estampar, por mes, las planchas necesarias para 25000 automóviles o 35000 camiones, o las correspondientes combinaciones de planchas para automóviles y camiones. El departamento 2 puede armar, por mes, 33333 motores de automóvil o 16667 motores de camión, o las correspondientes combinaciones de motores de automóviles y camiones. El departamento 3 puede montar y terminar 22500 automóviles y el departamento 4 puede hacer lo mismo con 15000 camiones. Sí cada automóvil deja una utilidad de 300 Dlls. y cada camión una de 250 Dlls., ¿qué cantidades de automóviles y de camiones se deben producir, de manera que las utilidades totales que se obtengan sean las máximas posibles?

Es claro que en este problema existen dos variables que son la cantidad de automóviles y la cantidad de camiones a fabricar y se designarán como x1 y x2. El primer paso consiste en establecer la función objetivo, o sea, la función de utilidades que se va a maximizar. Como cada automóvil produce una utilidad de 300 Dlls., de x1 automóviles se obtendrán 300x1 Dlls. y en el caso de los camiones, 250x2 Dlls. Por lo tanto, se tendría:

Las restricciones se refieren a la capacidad de cada uno de los departamentos. Si el primero puede estampar planchas metálicas para 25000 automóviles o 35000 camiones o las correspondientes combinaciones de planchas para automóviles y camiones, suponiendo que la capacidad de dicho departamento fuera 1, la producción de, por ejemplo, 12500 automóviles, ocuparía , o sea, la mitad de dicha capacidad, por lo tanto, se puede inferir que la producción de un automóvil, ocuparía de la capacidad y por ende la producción de x1 automóviles ocuparía de la capacidad. Este mismo razonamiento se utiliza para los camiones y de esta manera se tendría:

La utilización del símbolo se justifica porque no necesariamente debe utilizarse toda la capacidad del departamento 1 .La expresión matemática para la restricción del departamento 2 es similar, excepto que en lugar de planchas metálicas se arman motores y por lo tanto, se tendría:

Como los departamentos 3 y 4 no se comparten, para cada uno de ellos se puede establecer una expresión como sigue:

De esta manera el problema quedaría completamente planteado en la forma siguiente:

Problema 2

Para la elaboración de un producto se cuenta con cuatro componentes que contienen un cierto factor F, en las proporciones que se indican en el cuadro que aparece a continuación, donde también se incluyen los costos por kilogramo de cada componente. Se trata de obtener una tonelada de mezcla cuyo contenido de factor F sea por lo menos del 18%, con el mínimo costo posible.

Componente

Contenido de

factor F en %

Costo por Kg.

en centavos

A

51

4.0

B

11

2.0

C

14

2.4

D

36

3.0

En este caso se tienen cuatro variables que son las cantidades da cada uno de los componentes que deben entrar a formar parte de la fórmula óptima, es decir, la de costo mínimo y de esta fórmula se debe preparar una tonelada (1000 kgs.), por lo tanto, el objetivo debe ser minimizar la función de costo. Se simbolizarán como x1, x2, x3 y x4, las cantidades de componentes A, B, C y D que participarán en la mezcla, y de esta manera se tendría:

Unidad 2

Problema 1.

Supóngase que se dispone de dos máquinas para elaborar dos productos y que en la máquina 1, se requieren tres horas para elaborar una unidad del producto 1 y seis horas para elaborar una unidad del producto 2, que en la máquina 2, se requieren seis horas para elaborar una unidad del producto 1 y cinco horas para elaborar una unidad del producto 2. Supóngase también que se tiene una capacidad disponible de 2100 horas-hombre por semana en cada una de las máquinas y que se obtiene una utilidad de cuatro pesos por cada unidad de producto 1 que se venda y de cinco pesos por cada unidad de producto 2 que se venda. ¿Cuántas uni-dades se deberían fabricar de cada uno de los productos para que las utilidades obtenidas sean las máximas?

Debe hacerse notar, que en este problema la primera restricción es una igualdad. Con los mismos datos, supóngase que existiera otra restricción en el sentido de que las cantidades de los componentes B y C no constituyan, en conjunto, más del 20% de la mezcla. Esto significaría que la suma de los kilogramos de componentes B y C no deben exceder de 200 kilogramos. Esta última restricción quedaría como: .

Pero aquí vuelve a surgir una pregunta: ¿Porqué se utilizan desigualdades lineales en lugar de igualdades? Para ello se debe analizar lo que representan estas desigualdades y que precisamente corresponden a las restricciones de capacidad de las dos máquinas, es decir, que a pesar que lo deseable es que se utilicen al máximo las capacidades disponibles, esto no quiere decir, que para maximizar las utilidades tenga que ocurrir esto forzosamente, por lo tanto, en vez de expresar esta restricción como una igualdad, resulta más conveniente utilizar una desigualdad, y de esta manera, dejar la posibilidad de utilizar parcialmente la capacidad disponible de cada máquina.

Utilizando desigualdades lineales, estas estarían representadas, en dos dimensiones, por semiespacios en lugar de rectas y en vez de un punto de intersección se tendría la intersección de esos semiespacios, que da lugar a un polígono convexo con un número infinito de soluciones posibles. El uso de desigualdades obliga a crear dos variables adicionales que representen las capacidades ociosas o no utilizadas de ambas máquinas, a las que se denotará como y , y que al insertarlas en las desigualdades las convierten en igualdades.

Sí ahora se resta , a ambos lados de la función objetivo y ésta se multiplica por () y además se invierten los términos de las otras dos igualdades, se obtiene lo que se conoce como forma estándar o canónica del problema de programación lineal que queda como sigue:

que prácticamente constituye el núcleo de lo que se conoce como Tabla Simplex. Lo que ahora se debe buscar es el valor máximo de la función de tal manera que se satisfagan simultáneamente las otras dos restricciones del problema y esto es precisamente lo que va a hacer el Método Simplex. Sin embargo, analizando la estructura del sistema de ecuaciones lineales que constituye la forma canónica, se puede observar que el problema consta de tres ecuaciones y cinco variables, lo cual sugiere que no se puede resolver para las cinco variables, sino sólo pata tres de ellas. Sí el problema se expresa matricialmente, se tiene:

Como se puede observar, si se tienen que seleccionar tres variables del sistema para resolverlo, las que resultan más adecuadas son las tres que conforman una matriz identidad , por la sencilla razón de que la inversa de una matriz identidad es la misma matriz y por lo tanto la solución se obtiene directamente:

La interpretación de esta solución resulta lógica, ya que si se elaboran 0 unidades del producto 1 y 0 unidades del producto 2, es decir que , ya que no forman parte de la matriz identidad, o sea, de la base, no se habrán utilizado las capacidades disponibles de ambas máquinas. Las capacidades no utilizadas u ociosas, serán 2100 horas por semana de la máquina 1 y 2100 horas por semana de la máquina 2, por lo que la utilidad obtenida al vender 0 unidades, será de 0 pesos. Ésta es sólo una solución factible para el sistema, pero no la óptima.

Lo que ahora se buscará, es mejorar la solución introduciendo a la base formada por las variables que conforman la matriz identidad, alguna de las variables que en este momento se encuentran fuera de ella como son . Esta inserción de alguna de las variables que están fuera de la base, hará que la matriz ya no sea una matriz identidad y que, por lo tanto, para restaurarla sea necesario llevar a cabo la inversión de esa columna, dándole la forma que tenía la columna de la variable a la que está sustituyendo. Ahora surge otro problema, y éste es saber ¿cuál de las variables que están fuera de la base es la más conveniente para entrar a la base y cual de las que están en la base actualmente es la que más conviene sustituir?

Afortunadamente este problema lo resuelve el mismo Método Simplex, por medio de dos criterios de optimización que conducen a la realización del menor número de iteraciones para alcanzar la solución óptima. Estos criterios son también bastante apegados a la lógica, ya que el Método Simplex, seleccionará siempre para que entre a la base, a la variable que produzca el mayor incremento unitario para el valor de la función objetivo, y para salir de ella, a la que produzca el menor incremento para la misma. Para ilustrar la situación anterior, se va a operar con la Tabla Simplex, la cual, como ya se mencionó antes, no es otra cosa que la forma estándar o canónica expresada en forma tabular y que quedaría como se muestra a continuación:

Tabla Simplex

Iteración

Variables

en la base

Valores de las variables en la base

0

f

0

2100

2100

4

3

6

5

6

5

1

0

0

0

1

0

0

0

1

1

f

1750

350

350

1½

½

3½

0

1

0

1

0

0

0

0

1

2

f

1900

300

100

0

0

1

0

1

0

1

0

0

El método Simplex es un procedimiento iterativo que consiste, como ya se mencionó con anterioridad, en partir o arrancar de una solución básica admisible no degenerada, lo cual se consigue precisamente, por medio de la adición de las variables de holgura, que además de transformar las desigualdades originales en igualdades, definen las capacidades ociosas o no utilizadas de las dos máquinas. Estas variables podrán tomar valores dentro del rango de 0 hasta 2100, en ambos casos. Debe enfatizarse que las columnas correspondientes a estas variables junto con la de la conforman una matriz identidad, la cual forma la base del sistema, ya que consta de tres columnas unitarias y que entre sus propiedades tiene la de que su inversa es igual a ella misma. En cada iteración, el algoritmo Simplex va a introducir a la base una de las variables que se encuentra fuera de ella y dicha variable va a sustituir a una variable de las que se encuentran en la base. Esto se traduce en que una de las columnas de la matriz identidad pierde su cualidad unitaria y es necesario restaurarla para que siga formando la base del sistema. En la representación geométrica de la solución del problema, esto equivale a saltar de un vértice o punto extremo del polígono convexo a otro adyacente. La restauración de la matriz identidad se consigue por medio de transforma-ciones elementales que es realizan sobre toda la matriz del sistema.

El mecanismo de transformación de una iteración a otra, no es otra cosa que la aplicación de las transformaciones elementales de las matrices, para invertir la columna de la matriz que al entrar a ella sustituyendo a una de las variables originales, rompe la estructura de la matriz identidad.

Este mecanismo se puede traducir a un conjunto de reglas muy objetivas y mecánicas que se van a exponer a continuación.

En este caso que se trata de un problema de maximización se tendría:

1.

Para encontrar la variable que debe entrar a la base, busca en el renglón de la función objetivo, el coeficiente asociado a la variable fuera de la base, cuyo valor sea el más negativo. En este caso será 5, asociado a la variable .

1.

Para encontrar la variable que debe salir de la base, divide los valores de las variables que están en la base, entre los coeficientes que en los mismos renglones tenga la columna de la variable seleccionada para entrar a la base, en el paso anterior, siempre y cuando dichos cocientes sean positivos, ya que sí son indeterminados (división entre cero) o negativos, se descartan. La variable saliente será aquella que esté asociada con el cociente más pequeño. En este caso, el cociente más pequeño es el asociado con la variable .

Vale la pena en este momento, enfatizar que la selección de la variable que debe salir de la base, es decir, el paso 2, siempre será la asociada con el cociente menor, independientemente que el problema sea de maximización o de minimización.

1. Una vez que ya se seleccionaron la variable que debe entrar a la base y la que debe salir de ella, se identifica el elemento de la matriz que va a utilizarse como pivote, en el cruce del renglón de la variable saliente y la columna de la variable entrante, marcándolo por medio de un círculo. En este caso es el ele-mento 6.

1.

El siguiente paso es divide el renglón del elemento pivote entre dicho elemento y el resultado será el nuevo renglón de la varia-ble en la iteración 1.

1.

Con el coeficiente 1 que quedó en el lugar del pivote, es necesario, por medio de transformaciones elementales, convertir en ceros los demás coeficientes de la columna de la variable , de tal manera que dicha columna tome la forma que tenía la columna de la variable que salió de la base en la iteración anterior y que en este caso fue la .

1. Ahora se repite el procedimiento desde el paso 1 tantas veces como sea necesario, hasta que en el renglón de la función objetivo ya no haya coeficientes negativos, lo cual ocurre para este problema en la iteración 2, y que indica que ya se alcanzó el valor máximo de la función objetivo, que en el caso particular de este problema tiene un valor de 1900.

Ahora se requiere interpretar los resultados de la iteración 2 que resulta ser la solución óptima para el problema.

Si se analiza la columna de valores de las variables en la base se puede observar que para alcanzar la utilidad máxima que es igual a 1900 pesos, es necesario fabricar 100 unidades del producto 1 y 300 unidades del producto 2, lo que se puede verificar sustituyendo estos valores en las expresiones del modelo matemático que se planteó, como se puede ver a continuación:

Aquí hay que hacer notar que sí las dos restricciones de capacidad se satisfacen exactamente en la igualdad, esto debe interpretarse como que las capacidades se utilizaron totalmente, es decir no hubo capacidad ociosa o no utilizada en alguna de las máquinas, o lo que es lo mismo, tanto como tienen un valor igual a cero, lo cual se debe a que dichas variables de holgura están fuera de la base en la solución óptima. De hecho se puede inferir que en los problemas de programación lineal, el que una variable, ya sea real o de holgura, quede fuera de la base en una solución, ya sea intermedia o en la óptima, significa que esa variable tiene un valor igual a cero.

Pero aquí no acaba la interpretación de la solución óptima, pues es necesario interpretar también los valores que aparecen en las demás casillas de la iteración óptima de la Tabla Simplex.

Como se puede observar, las variables que forman la base en la iteración óptima, son y , que en la tabla, junto con la función objetivo, f, conforman una matriz identidad de 3 x 3 y que en la columna de valores de las variables en la base tienen valores de 1900, 100 y 300, respectivamente. Sin embargo las otras dos columnas que corresponden a las variables de holgura que están fuera de la base y que son y , no son unitarias, es decir, tienen valores numéricos, generalmente fraccionarios, que tienen un significado netamente económico y que se van a interpretara continuación.

Para guardar algún orden, se comenzará por la columna correspondiente a la variable de holgura , que como ya se mencionó anteriormente tiene un valor de cero por estar fuera de la base, pero en el renglón de la función objetivo que está formada por coeficientes de utilidad, en este caso, en la iteración 2 que es la óptima se tiene un coeficiente con valor de , que forzosamente tiene que ser también un coeficiente de utilidad, pero que se debe interpretar como el incremento unitario del valor de la función objetivo, si se pudiera disponer de una hora más de capacidad en la máquina 1, ya que las 2100 horas que se tenían disponibles se agotaron totalmente, es decir, por cada hora de capacidad adicional a las 2100 que se tenían al comenzar el problema, el valor de la función obje-tivo se incrementará en de peso. Sin embargo, hay que tomar en cuen-ta que al disponer de una mayor capacidad en la máquina 1, las canti-dades elaboradas de los productos 1 y 2, no serán las mismas que cuan-do sólo se disponía de 2100 horas, sino que tendrán que ser diferentes. Aquí es donde entran los coeficientes que aparecen en la misma columna de , y que son y . Esto quiere decir que si se dispusiera de una hora más de capacidad en la máquina 1, se podrían fabricar del producto 2, 300+ y del producto 1, 100 y que la utilidad total sería 1900+. De manera similar se interpretaría la columna correspondien-te a la otra variable de holgura fuera de la base que es .

De esta manera se tiene una interpretación completa de la iteración 2, que es la óptima para este problema.

Sin embargo, se había mencionado que el mayor problema al que se enfrentan los estudiantes, es precisamente la construcción del modelo matemático a partir del problema textual, y con esta idea en mente, ahora se procederá hacer el planteamiento de una serie de problemas cuyo grado de dificultad se irá incrementando gradualmente, con el fin de ir adquiriendo experiencia en la construcción de sus correspondientes modelos.

Unidad 3

Problema 1.

Se considerará el caso en el que debe determinarse la dieta para la alimentación diaria de un animal, de tal manera que se satisfagan los requerimientos nutricionales y que los costos sean mínimos. Para mantener el ejemplo lo más simple posible, se considerarán sólo cuatro posibles componentes, que serán cebada, avena, hojuelas de ajonjolí y harina de cacahuate. Los requerimientos nutricionales se limitarán a dos, siendo el primero que el alimento debe contener cuando menos 20 unidades de proteína y el segundo, que debe contener cuando menos 5 unidades de grasa. Los contenidos de proteína y de grasa de cada uno de los componentes así como sus costos unitarios aparecen en la Tabla 1. En la mayoría de los casos se utilizan unidades de peso como toneladas, libras o gramos, para expresar las contribuciones de los componentes a la fórmula óptima, y en el caso de que se expresaran en otro tipo de medida, será necesario convertirlas a unidades de peso para su adecuado manejo.

Tabla 1Contenido de Proteína y de Grasa y Costo Unitario de los ComponentesEspecificaciónComponente

Contenido de

Proteína

Contenido de

Grasa

Costo

Unitario

Cebada

12

2

24

Avena

12

6

30

Hojuelas de Ajonjolí

40

12

40

Harina de Cacahuate

60

2

50

Las dos restricciones del problema se podrían establecer como sigue:

Después de introducir las variables de holgura no negativas correspondientes y1 y y2, que representan excedentes de proteína y de grasa sobre la especificación, las desigualdades se pueden expresar como sigue:

La función objetivo es minimizar los costos de preparación del alimento, de tal ma-nera que para la ecuación de la función objetivo se podría establecer la siguiente expresión:

...........................................................................(5)

Las ecuaciones (3), (4) y (5) se pueden convertir a la forma estándar o canónica con f, y1 y y2 como variables básicas, multiplicando (3) y (4) por1 y pasando los términos de las variables x´s de (5) al otro lado del signo de igualdad. De esta manera, se obtiene el siguiente sistema:

..............................................(6)

Este sistema se puede vaciar al formato de la Tabla Simplex, como se puede observar en la Iteración 0 de la Tabla 2. Ahora la dificultad estriba en que la solución de la Iteración 0 no es factible puesto que las variables básicas y1 y y2 son negativas. Ya que el Método Simplex requiere de una solución factible no degenerada para arrancar, se debe construir dicha solución. Existe un método general para encontrar una solución factible para cualquier problema de programación lineal que se desarrollará posteriormente. Ahora se demostrará que si se conoce una solución básica factible para el problema, dicha solución se puede generar utilizando iteraciones Simplex introduciendo sus variables a la base una por una. Una vez que ya se ha generado esta solución, se puede aplicar el Método Simplex tal como ya se indicó antes.

Para este ejemplo resulta muy sencillo encontrar una solución básica factible, ya que media unidad de hojuelas de ajonjolí satisface en forma precisa el requerimiento de proteína y contiene 6 unidades de grasa que rebasa en uno el requerimiento mínimo que es de 5 unidades. La correspondiente solución básica es aquella en la que la cantidad de hojuelas de ajonjolí x3, es positiva y por lo tanto, deja de ser una variable no básica, y la variable de holgura para el contenido de proteína y1, se hace cero y por lo tanto, deja de ser variable básica. Esta solución se genera a partir de la iteración 0 pivoteando sobre el elemento que se encuentra en el cruce del renglón de y1 y la columna de x3. El resultado es la iteración 1, que contiene la solución factible deseada. Ahora se puede aplicar el Método Sim-plex, pero no debe olvidarse que se está minimizando la función objetivo. Por lo tanto, se debe seleccionar como nueva variable básica, la asociada con el coeficiente mayor positivo del renglón de la función objetivo. Esto se ve claramente si se escribe la ecuación correspondiente al primer renglón de la iteración 1 de la Tabla 2 como:

es decir, se introduce x4 a la base y y2 sale de ella. El resultado es la iteración 2, cuyo primer renglón no contiene elementos positivos, por lo que se considera que se ha alcanzado la solución óptima (de costo mínimo), en la que y y el costo de esta solución es .

En el problema de planeación de la producción, fue posible hacer una interpretación económica de la solución, en la que la rentabilidad de todos los productos se

evaluó utilizando los costos inputados calculados a partir de los productos que estaban en el programa de producción. Para este problema se puede hacer una interpretación similar. Considérese la solución que aparece en la iteración 2 de la Tabla 2, donde se utilizan el tercero y el cuarto componentes en la preparación del alimento. Se puede asignar u1 a la unidad de proteína y u2 a la unidad de grasa. A estos valores son los costos inputados a la proteína y a la grasa y se pueden derivar a partir de los costos de los componentes. Puesto que una unidad de hojuelas de ajonjolí contiene 40 unidades de proteína y 12 unidades de grasa y cuesta $40/unidad, se puede establecer la siguiente ecuación:

...............................................................................................(7)

De manera semejante se puede derivar la ecuación para la harina de cacahuate:

.................................................................................................(8)

Al resolver este sistema se obtiene:

Por lo tanto, los costos inputados son 13/16 por unidad de proteína y 5/8 por unidad de grasa. Nótese que en la tabla, estas cifras aparecen con signo negativo en el renglón de , en las columnas correspondientes a y1 y y2 de la iteración 2. Los costos totales de esta solución, también se pueden evaluar en términos de los inputados.

............................................................................................(9)

Los costos inputados se pueden utilizar para determinar los beneficios reducidos de los componentes que no entraron en la mezcla para la obtención del alimento, restándole a los costos de dichos componentes su valor en términos de proteína y de grasa. En el caso del primer componente (la cebada) se tiene:

y para el segundo (la avena):

Puesto que estos beneficios reducidos son positivos, ni la cebada ni la avena deben utilizarse en la preparación del alimento. Nótese que dichos beneficios reducidos aparecen con signo negativo en el renglón de la f en las columnas correspondientes a las variables x1 y x2 de la iteración 2.

El problema de la composición de costo mínimo del alimento para ganado, es un problema típico o clásico de minimización en programación lineal. Estos problemas generalmente implican la mezcla de ingredientes, de tal manera que el producto obtenido satisfaga ciertos requerimientos mínimos a costos también mínimos, o la mezcla de materiales para la manufactura de un producto que satisfaga especificaciones dadas a costos mínimos.

Tabla 2Tabla Simplex para el problema de la preparación del alimento para ganado

Iter.

Variables

Básicas

Valores

De las VB

x1

x2

x3

x4

f

y1

y2

0

f

y1

y2

0

20

5

24

12

2

30

12

6

40

40

12

50

60

2

1

0

0

0

1

0

0

0

1

1

f

x3

y2

20

½

1

12

3/10

1 3/5

18

3/10

22/5

0

1

0

10

1½

16

1

0

0

1

1/40

3/10

0

0

1

2

F

x3

x4

193/8

13/32

1/16

13

3/20

1/10

16½

21/40

3/20

0

1

0

0

0

1

1

0

0

13/16

1/320

3/160

5/8

3/32

1/16

Unidad 4

Existen varios métodos para resolver el Modelo General de Transporte. En este capítulo se va a discutir uno de los algoritmos que se utilizan para este fin y que se conoce como “Método del Cruce del Arroyo” (Stepping Stone Method) el cual requiere arrancar de una solución básica factible no degenerada, la cual se puede obtener por diferentes procedimientos, siendo uno de ellos la llamada “Regla de la Esquina Noroeste”.

Regla de la Esquina Noroeste

Esta regla consiste en colocar la información en una tabla que tiene en los renglones los datos correspondientes a los orígenes (generalmente disponibilidades de algún producto) y en las columnas los de los destinos (generalmente requerimientos del producto). Una vez que se ha vaciado la información, utilizando la notación común para cualquier plano o mapa, se considera que el norte siempre se localiza en la parte superior, y a continuación se identifica la esquina noroeste, que es la que se encuentra en la parte superior izquierda y en ella se comienzan a realizar las asignaciones hasta saturar el renglón y/o la columna, correspondientes para después pasar a la siguiente esquina noroeste y repetir el procedimiento las veces que sea necesario hasta satisfacer totalmente los requerimientos de los desti-nos sin violar las disponibilidades de los orígenes.

Después es necesario comprobar que se trata de una solución básica factible no degenerada, la cual debe contener exactamente casillas con asignación igual a cero. Si la solución pasa la prueba, se procede a mejorarla iterativamente, utilizando para ello cualquiera de los algoritmos disponibles. En este caso se utilizará, como se dijo antes, el Método del Cruce del Arroyo, ilustrando la aplicación de este algoritmo, con un ejemplo numérico.

Problema 1.(Transporte)

Supóngase que se tienen tres plantas para fabricar un producto y que cada una de ellas tiene una capacidad de 100, 120 y 120 toneladas por semana. Dicho producto se tiene que enviar a cinco almacenes o bodegas cuyos requerimientos son respectivamente de 40, 50, 70, 90 y 90 toneladas por semana. La siguiente figura muestra el esquema del problema. En ella aparecen todas las posibilidades para enviar el producto desde cada una de las plantas hasta cada uno de los almace-nes, a los correspondientes costos de transporte.

Los costos de transportar una unidad del producto desde la planta “i” hasta el almacén “j” aparecen en la siguiente tabla:

Tabla de costos de transporte

1

2

3

4

5

DISP.

A

4

1

2

6

9

100

B

6

4

3

5

7

120

C

5

2

6

4

8

120

REQ.

40

50

70

90

90

340

El problema es entonces minimizar el costo total de transportar las 340 toneladas por semana desde las tres plantas hasta las cinco bodegas o almacenes, en otras palabras, se debe encontrar el plan de transporte que haga mínimo el costo total.

Aplicando la Regla de la Esquina Noroeste a este problema se obtendría una solución básica admisible no degenerada, lo que se puede verificar determinando el número de casillas con asignación cero (como y , se tendría una solución con 8 casillas con asignación igual a cero).

ITER0

1

2

3

4

5

DISP.

1

4

40

50

1 2

10

+1 6

0

9

0

100

2

6

0

4

0

+1 3

60

1 5

60

+1 7

0

120

3

5

0

2

0

6

0

+1 4

30

1 8

90

120

REQ

40

50

70

90

90

340

El costo de esta solución es:

A continuación, utilizando el método del Cruce del Arroyo, se va a tratar de obtener una solución mejor que ésta, es decir con un costo menor. Este método consiste en determinar la variación del costo de una casilla con asignación igual a 0 al hacer en ella una asignación de una unidad.

Por ejemplo si se asigna una unidad a la casilla (1, 4), se tiene que restar una unidad a la casilla (1, 3) luego sumarle una unidad a la casilla (2, 3) y finalmente restarle una unidad a la casilla (2, 4), todo esto para restablecer el equilibrio, y el costo marginal de estos cambios es:

Luego, haciendo este mismo análisis para las otras 7 casillas con asignación igual a cero, se tendría:

Como se puede observar, el único costo marginal negativo es el correspondiente a la casilla ( 2, 5 ), el cual es igual a . Esto quiere decir que por cada unidad de producto que se introduzca a la casilla ( 2, 5 ) el costo total disminuirá en 2. El haber encontrado la mejor casilla para desplazar el producto es equivalente en el Método Simplex, a la selección de la variable que debe entrar a la base, por lo tanto, ahora es necesario determinar la variable que debe salir de la base y por consiguiente cual debe ser la cantidad del producto que se puede desplazar a la nueva casilla.

Para ello se deben observar las casillas en donde aparecieron los 1 al llevar a cabo el análisis marginal de la casilla ( 2, 5 ) y que son la ( 2, 4 ) y la ( 3, 5 ), cuyas asignaciones son 60 y 90 respectivamente. De ellas se debe seleccionar la que tenga la asignación menor o sea 60, que será la máxima cantidad de producto que podría desplazarse a la casilla ( 2, 5 ). Una vez hecho esto, la casilla ( 2, 4 ), que está asociada con la variable que debe salir de la base en el Simplex, alcanzará un valor de 0. De esta manera se llega a la siguiente solución o iteración, la cual tendrá un costo de .

ITER1

1

2

3

4

5

DISP.

1

4

40

1

50

2

10

6

0

9

0

100

2

6

0

4

0

3

60

5

0

7

60

120

3

5

0

2

0

6

0

4

90

8

30

120

REQ

40

50

70

90

90

340

Si se verifica el número de casillas con asignación igual a cero, se observará que sigue siendo igual a 8, por lo que la solución sigue siendo básica factible no degenerada. El procedimiento se repite y al hacerlo se encuentra que hay dos casillas con costo marginal negativo y además igual que son la ( 3, 1 ) y la ( 3, 2 ) cuyo costo es de . Cuando ocurre esto, es decir que hay un empate entre los costos marginales de las variables, en este caso casillas que resultaron las mejores, se debe seleccionar la primera de ellas. Esto es equivalente en el Método Simplex, a que haya un empate entre los cocientes mínimos asociados a las variables dentro de la base que sean candidatas a salir de ella. Selecciónese pues la casilla ( 3, 1 ) y analícense las casillas donde aparecieron los al llevar a cabo el análisis marginal y que son la ( 1, 1 ), la ( 2, 3 ) y la ( 3, 5 ), resultando que ésta última es la que tiene la menor asignación con un valor de 30.

Por lo tanto, el costo total de esta solución será de y la nueva iteración quedará como sigue:

ITER2

1

2

3

4

5

DISP.

1

4

10

1

50

2

40

6

0

9

0

100

2

6

0

4

0

3

30

5

0

7

90

120

3

5

30

2

0

6

0

4

90

8

0

120

REQ

40

50

70

90

90

340

Nuevamente el número de casillas con asignación igual a cero es 8, por lo que la solución que se ha obtenido sigue siendo básica factible no degenerada. Al repetir nuevamente el análisis marginal de las casillas con asignación igual a cero, ya no se encuentra alguna casilla con costo marginal negativo, lo cual indica que se ha alcanzado la solución óptima y que ésta es la correspondiente a la iteración 2. Sin embargo, en este último análisis la casilla ( 3, 2 ) queda con un costo marginal igual a 0, lo cual debe interpretarse como la existencia de, en principio, un número infinito de soluciones, puesto que se podría desplazar a dicha casilla cualquier cantidad de producto entre 0 y 30 y el costo permanecería sin alteración. El límite superior resulta 30, por ser ésta la menor asignación de las casillas en donde aparecieron los al llevar a cabo el análisis marginal sobre la casilla ( 3, 2 ). Como en éste problema se están manejando cantidades discretas, el número de opciones de solución posibles sería cualquier cantidad entera entre 0 y 30.

La interpretación de la solución óptima es la siguiente:

El costo total mínimo de transporte es 1400.

Desde la planta A es necesario enviar 10, 50 y 40 unidades del producto a los almacenes 1, 2 y 3 respectivamente.

Desde la planta B es necesario enviar 30 y 90 unidades del producto a los almacenes 3 y 5 respectivamente.

Desde la planta C es necesario enviar 30 y 90 unidades producto a los almacenes 1 y 4 respectivamente.

Problema 2.(asignación)

El jefe de un departamento tiene cuatro empleados y cuatro tareas que se deben llevar a cabo. Los empleados difieren en eficiencia, y las tareas en su grado de dificultad intrínseca. Las estimaciones que hace el jefe del tiempo que se lleva cada empleado en realizar cada tarea, se dan en la matriz de efectividad que aparece a continuación. ¿Cómo deben asignarse las tareas, una a cada empleado, para hacer mínimo el tiempo total utilizado?

EMPLEADOS

T

I

II

III

IV

AA

8

26

17

11

R

B

13

28

4

26

E

C

38

19

18

15

A

D

19

26

24

10

Solución:

Existen conjuntos de asociaciones posibles que satisfacen estas condiciones. Se pueden escribir todos los conjuntos posibles, junto con el total correspondiente de horas-hombre, pero un procedimiento más sistemático es el que se muestra a continuación que se conoce como “Método Húngaro”.

Escójase el coeficiente más pequeño del renglón A y réstese de cada uno de los otros coeficientes del mismo. El resultado es:

0

18

9

3

13

28

4

26

38

19

18

15

19

26

24

10

Supóngase ahora que se ha asignado una tarea a cada empleado. Cualquiera que sea la asignación que se haya hecho, el total de horas hombre para la nueva matriz será menor en 8 que el de la matriz anterior. Por lo tanto, una asignación que haga mínimo el total de una matriz, también minimizará el total de la otra.

Este enunciado generalmente es cierto, y se apoya en el siguiente teorema, que es la base de la solución que se está proponiendo.

Teorema

Sí en un problema de asignación se suma una constante a cada elemento de un renglón (o columna) de la matriz de efectividad, entonces una asignación que hace mínima la efectividad de una matriz, también minimizará la efectividad total de la otra matriz.

Ahora se procederá a restar el elemento menor de cada renglón, de los demás e-lementos del mismo, para obtener:

0

18

9

3

9

24

0

22

23

4

3

0

9

16

14

0

A continuación se debe restar el elemento más pequeño de cada columna del resto de los elementos de la misma y se obtiene:

0

14

9

3

9

20

0

22

23

0

3

0

9

12

14

0

El paso final dependerá del hecho, por demás obvio, de que la matriz consista de elementos positivos o cero, la efectividad total no puede ser negativa para ninguna asignación. En consecuencia, sí se puede seleccionar una asignación que tenga un total de cero, no puede haber asignación alguna con un total menor. En otras palabras, es seguro que el total es mínimo sí todas las asignaciones se pueden hacer en las posiciones en donde los elementos son cero.

Por lo tanto se hacen las siguientes asignaciones:

0

14

9

3

9

20

0

22

23

0

3

0

9

12

14

0

A I , B III , C II , D IV

En virtud del teorema anterior, estas asignaciones también hacen mínimo el número total de horas-hombre de la matriz original.

En el ejemplo anterior, la reducción de la matriz de efectividad por substracción produjo una solución óptima del problema original. No siempre se tiene la misma fortuna; de lo único que se puede estar seguro, después de llevar a cabo la reducción. es que se terminará con una matriz que posee cuando menos un cero en cada renglón y cuando menos un cero en cada columna. Puede que una asignación completa no esté presente entre los ceros en esta etapa; o si lo está, puede ser difícil reconocerla cuando la matriz es de una dimensión considerable, por lo tanto, se pueden plantear dos preguntas:

1. Dada una matriz con algunos ceros y todos sus elementos no negativos, ¿Cómo se busca la asignación máxima existente entre los ceros?

2. Sí no existe una asignación completa entre los ceros, ¿Cómo se puede modificar aún más la matriz mediante sumas, (o restas) a renglones y columnas para obtener más ceros?

Aunque existen algoritmos que dan una respuesta completa a la primera pregunta, generalmente son demasiado complejos como para que se incluyan en un curso introductorio como es este. Para matrices de dimensiones no muy grandes, la asignación máxima existente se puede encontrar por inspección visual o por tanteos. En matrices más grandes se puede requerir algo de ingenio (o de suerte) para encontrarla en ausencia de un algoritmo formal. En todos los casos se tiene que partir del uso de las siguientes reglas:

( 0 0 0 0 0 0 0 0 0 0 0 0)

a)Examina los renglones sucesivamente hasta que encuentres uno de ellos que tenga exactamente un cero no marcado. Encierra este cero en un ( ), ya que allí se hará una asignación. Tacha los de-más ceros que haya en la misma columna con una ( X ) para indicar que no se pueden hacer más asignaciones en ella. Repite este tratamiento con los demás renglones.

b)Examina a continuación las columnas para encontrar ceros no marcados y enciérralos también en un cuadro ( ), y tacha ahora con una ( X ), los demás ceros que haya en el mismo renglón.

c)Repite los pasos (a) y (b) sucesivamente hasta que ocurra una de las dos siguientes cosas: Que ya no haya ceros que se puedan encerrar en un cuadro o que los ceros que quedan sin encerrar sean cuando menos dos en cada renglón o columna

Si lo que ocurrió fue lo primero, entonces se tiene una asignación máxima. Si ocurrió lo segundo, habrá que encontrar la asignación máxima por tanteos. Sin importar como se obtuvo la asignación máxima, se puede decir que, si tiene una sola asignación en cada renglón, esta asignación máxima es una solución completa del problema original. Si no contiene una sola asignación en cada renglón, será nece-sario modificar la matriz de efectividad mediante más sumas o restas. Antes de discutir esto, se dan ahora unos ejemplos de cómo obtener asignaciones máximas.

Ejemplo 2:Supóngase que se tiene la siguiente matriz:

( 0 0 0 0 0 0 0 0 0 0 0 0)

Solución:

El renglón 1 tiene un solo cero en la segunda columna, por lo que se hace una asignación y se elimina el segundo cero de esa misma columna.

( 0 0 0 0 0 0 0 0 0 0 0 0)

( 0 0 0 0 0 0 0 0 0 0 0 0)El renglón 2 tiene ahora un solo cero en la primera columna, por lo que se hace una asignación en ese lugar y se eliminan los ceros que quedan en esa columna.

En todos los renglones que quedan se observa que cuando menos hay dos ceros, por lo que ahora se precede a examinar las columnas. La cuarta columna tiene un solo ce-ro en el quinto renglón, por lo que en ese lugar se hace una asignación y se eliminan los ceros restantes en ese renglón.

(0)

(0) (0)

(0)

0 0

(0 )

0 0

(0) (0) (0)

Los dos renglones y las dos columnas que quedan tienen dos ceros. Aquí se puede proceder de dos formas, una sería haciendo una asignación en la posición (3, 3) y eliminando el otro cero del mismo renglón, con lo que en la quinta columna solo quedaría un cero, precisamente en la posición (4, 5), en donde se haría la última asignación obteniéndose de esta manera la asignación máxima. La otra opción sería hacer primero una asignación en la posición (4, 3), eliminando el cero de la posición (3, 3) y luego hacer la asignación en la posición (3, 5) y eliminar el cero de la posición (4, 5), que sería totalmente equivalente a la opción analizada con anterioridad.

( 0 0 0 0 0 0 0 0 0 0 0 0 )

0

Se observa que ya no quedan ceros, y que cada renglón tiene una sola asignación al igual que cada columna, por lo que se concluye que la asignación máxima es una solución completa. Sin embargo es pertinente hacer algunos comentarios en este punto, con respecto a la operación de este procedimiento en la práctica. Primero, puede haber más de una asignación máxima. Segundo, no es necesario en la práctica escribir repetidamente la matriz, aquí se hizo solo para dar claridad a la exposición.

Ahora se regresará a la otra pregunta: si la asignación máxima no constituye una solución completa, ¿cómo se podrían agregar más ceros a la matriz? A continuación se darán unas reglas de carácter empírico, pero que se puede probar que sí se aplican bien y repetidamente deben llevar a una solución completa en un número finito de iteraciones.

Se parte de la base de que ya se tiene una asignación máxima, y:

a)Se marcan con una paloma todos aquellos renglones en los que no se haya hecho asignación alguna.

b)Se marcan también con una paloma las columnas que tengan ce-ros tachados en el renglón o los renglones marcados en el pa-so (a).

c)Se marcan ahora los renglones que no estén marcados y que tengan asignaciones en columnas ya marcadas anteriormente.

d) Se repiten los pasos (b) y (c) hasta que se termine la cadena de marcaje, es decir, hasta que ya no haya ni renglones ni columnas que se puedan marcar.

e) Se trazan líneas rectas a través de todos los renglones no mar-cados y de todas las columnas marcadas.

Si el procedimiento se ha llevado a cabo correctamente, debe haber tantas líneas rectas como asignaciones había en la asignación máxima de la que se partió y cada cero tendrá cuando menos una línea que pase sobre él. Más aún, este procedimiento produce el número mínimo de líneas que se requieren para pasar por to-dos los ceros.

f) Una vez que se han trazado las líneas rectas, se examinan los elementos por los que no pasa línea alguna y se selecciona el menor de ellos. Ese elemento se resta de todos los demás elementos que están en las mismas condiciones que el seleccionado, se suma a cada elemento que se encuentre en la intersección de dos líneas, dejando los elementos restantes de la matriz sin alterar.

Con este último paso es posible obtener ceros adicionales, con los que se vuelve a intentar la obtención de una asignación máxima que constituya una solución completa. En caso que esto no ocurra, será necesario repetir el procedimiento de marcaje descrito en los pasos del (a) al (f), hasta obtener la asignación óptima, es decir la solución completa al problema.

No es indispensable seguir los procedimientos anteriores al pie de la letra para trazar las líneas, ya que en realidad mientras se puedan cubrir todos los ceros en una matriz de nxn con menos de n líneas rectas (horizontales o verticales), se puede demostrar que la asignación máxima no es aún una solución completa. La disposición de ceros siempre se puede mejorar mediante la aplicación del paso (f) a cualquier conjunto de menos de n líneas que cubran todos los ceros. Sin embargo, sí es posible obtener un conjunto con menos líneas, el resultado final se puede obtener en un número menor de iteraciones. Se puede también demostrar que si se pueden cubrir todos los ceros con un conjunto de menos de n líneas, entonces es posible que se obtenga una solución completa en esa etapa.

Ejemplo 3:

Indica cómo construir el número mínimo de líneas rectas que pasen a través de todos los ceros de la siguiente matriz.

(00000000)

Solución:

(000000000)Se hace primero la asignación máxima

1

3

3

2 2

Se marca el segundo renglón que no tiene asignación, (1) luego las columnas primera y cuarta que tienen ceros tachados en ese segundo renglón, (2) enseguida se marcan los renglones cuarto y quinto que tienen asignaciones en las columnas primera y cuarta marcadas en el paso anterior (3). Como los últimos dos renglones marcados ya no tienen ceros tachados en columna alguna, aquí se termina el proceso de marcaje.

Ejemplo 4:

Modifica la siguiente matriz para obtener una mejor asignación máxima:

5

0

8

10

11

0

6

15

0

3

8

5

0

0

0

0

6

4

2

7

3

5

6

0

8

Solución:

Como los ceros son los mismos que en el ejemplo anterior, se tiene ya la asignación máxima y las líneas rectas que atraviesan todos los ceros de la matriz.

5

0

8

10

11

0

6

15

0

3

8

5

0

0

0

0

6

4

2

7

3

5

6

0

8

Selecciona el elemento más pequeño que no esté atravesado por alguna recta, en este caso es el 3 que se encuentra en la posición (2, 5), réstalo de cada uno de los elementos que no tengan línea que pase sobre ellos y súmaselo a todos aquellos elementos que se encuentren en la intersección de dos líneas. La nueva matriz es:

8

0

8

13

11

0

3

12

0

0

11

5

0

3

0

0

3

1

2

4

3

2

3

0

5

De esta manera se encuentra una asignación máxima que constituye una solución completa al problema en los elementos que se encuentran en las posiciones (1, 2), (2, 5), (3, 3), (4, 1) y (5, 4). Si la asignación máxima no hubiera producido una solución completa al problema original, se hubiera procedido a trazar nuevamente líneas rectas sobre los ceros y a continuar con las iteraciones hasta encontrar una solución completa.

Unidad 5

Revisar apuntes y bibliografía.

No hay ejemplos digitales

Ejercicios resueltos Investigación de Operaciones

21

5

)

2

.........(

..........

..........

..........

..........

..........

..........

5

2

12

6

2

)

1

.......(

..........

..........

..........

..........

..........

..........

20

60

40

12

12

4

3

2

1

4

3

2

1

³

+

+

+

³

+

+

+

x

x

x

x

x

x

x

x

1

25000

)

4

....(

..........

..........

..........

..........

..........

5

0

2

12

6

2

)

3

..(

..........

..........

..........

..........

..........

20

0

60

40

12

12

2

1

4

3

2

1

2

1

4

3

2

1

=

-

+

+

+

+

=

+

-

+

+

+

y

y

x

x

x

x

y

y

x

x

x

x

4

3

2

1

50

40

30

24

x

x

x

x

f

+

+

+

=

2

1

4

3

2

1

2

1

4

3

2

1

2

1

4

3

2

1

0

0

2

12

6

2

5

0

0

60

40

12

12

20

0

0

50

40

30

24

0

y

y

f

x

x

x

x

y

y

f

x

x

x

x

y

y

f

x

x

x

+

+

+

-

-

-

-

=

-

+

+

+

-

-

-

-

=

-

+

+

+

-

-

-

-

=

f

x

y

x

x

=

-

+

+

+

4

1

2

1

10

18

12

20

32

13

3

=

x

16

1

4

=

x

8

3

19

40

12

40

2

1

=

+

u

u

50

2

60

2

1

=

+

u

u

8

5

2

16

13

1

u

y

u

=

x

1

25000

(

)

(

)

8

5

16

13

8

3

5

20

19

+

=

(

)

(

)

13

2

12

2

8

5

16

13

=

-

-

(

)

(

)

2

1

8

5

16

13

16

6

12

30

=

-

-

(

)

(

)

1

1

-

-

n

m

A

B

C

1

3

2

4

5

2

1

=

-

n

4

1

=

-

m

1550

)

8

)(

90

(

)

4

)(

30

(

)

5

)(

60

(

)

3

)(

60

(

)

2

)(

10

(

)

1

)(

50

(

)

4

)(

40

(

0

=

+

+

+

+

+

+

=

C

2

5

3

2

6

14

=

-

+

-

=

d

4

4

5

3

6

1

4

5

3

2

1

2

1

4

5

3

2

4

5

2

5

4

8

7

2

3

2

1

4

1

2

3

5

4

8

9

33

32

31

25

22

15

=

-

+

-

=

=

-

+

-

+

-

=

=

-

+

-

+

-

=

-

=

-

+

-

=

=

-

+

-

=

=

-

+

-

+

-

=

d

d

d

d

d

d

2

-

175000

5

7

875000

25

35

1

875000000

25000

35000

1

35000

25000

2

1

2

1

2

1

2

1

£

+

Þ

£

+

£

+

£

+

x

x

x

x

x

x

x

x

(

)

(

)

1430

2

60

1550

=

-

1

-

2

8

7

3

6

1

8

7

3

2

1

2

1

8

7

3

2

4

5

2

3

2

1

4

1

3

2

4

6

3

7

3

2

9

4

4

8

7

3

2

6

33

32

31

22

21

15

14

=

-

+

-

=

-

=

-

+

-

+

-

=

-

=

-

+

-

+

-

=

=

-

+

-

=

=

-

+

-

=

=

-

+

-

=

=

-

+

-

+

-

=

d

d

d

d

d

d

d

(

)

(

)

1400

1

30

1430

=

-

3

2

4

5

6

0

5

4

1

2

1

3

2

4

5

4

5

2

3

2

1

4

1

3

2

4

6

3

7

3

2

9

3

4

5

4

6

33

32

24

22

21

15

14

=

-

+

-

=

=

-

+

-

=

=

-

+

-

+

-

=

=

-

+

-

=

=

-

+

-

=

=

-

+

-

=

=

-

+

-

=

d

d

d

d

d

d

d

24

!

4

=

33333

2

111

.

555561

333

.

33

667

.

16

1

555561111

33333

16667

1

16667

33333

2

1

2

1

2

1

2

1

£

+

Þ

£

+

£

+

£

+

x

x

x

x

x

x

x

x

15000

,

22500

2

1

£

£

x

x

0

,

15000

22500

33333

2

175000

5

7x

:

a

sujeto

250

300

Maximizar

2

1

2

1

2

1

2

1

2

1

³

£

£

£

+

£

+

+

=

x

x

x

x

x

x

x

x

x

f

180

0.36

+

14

.

0

+

0.11

+

0.51

1000

=

+

+

+

:

a

sujeto

3x

+

4

.

2

+

2

+

4

=

Minimizar

4

3

2

1

4

3

2

1

4

3

2

1

³

x

x

x

x

x

x

x

x

x

x

x

f

200

3

2

£

+

x

x

0

,

,

,

2100

0

5

6

2100

0

6

3

:

a

sujeto

0

0

5

4

Maximizar

2

1

2

1

2

1

2

1

2

1

2

1

2

1

2

1

³

=

+

+

+

=

+

+

+

+

+

+

=

y

y

x

x

y

y

x

x

y

y

x

x

y

y

x

x

f

1

y

2

y

f

1

-

2

1

2

1

2

1

2

1

2

1

2

1

0

0

5

6

2100

0

0

6

3

2100

0

0

5

4

0

y

y

f

x

x

y

y

f

x

x

y

y

f

x

x

+

+

+

+

=

+

+

+

+

=

+

+

+

-

-

=

ï

þ

ï

ý

ü

ï

î

ï

í

ì

=

ï

ï

ï

þ

ï

ï

ï

ý

ü

ï

ï

ï

î

ï

ï

ï

í

ì

ú

ú

ú

û

ù

ê

ê

ê

ë

é

-

-

2100

2100

0

1

0

0

5

6

0

1

0

6

3

0

0

1

5

4

2

1

2

1

y

y

f

x

x

(

)

2

1

,

,

y

y

f

2100

,

2100

,

0

2

1

=

=

=

y

y

f

0

0

2

1

=

=

x

y

x

2

1

x

y

x

1

x

2

x

1

y

6

5

6

1

6

5

-

1

x

2

1

250

300

Maximizar

x

x

f

+

=

21

10

7

2

21

5

-

7

3

7

1

-

420

5

2100

,

350

6

2100

,

2

1

=

=

y

Para

y

Para

2100

1500

600

)

300

)(

5

(

)

100

)(

6

(

2100

1800

300

)

300

)(

6

(

)

100

)(

3

(

1500

400

)

300

)(

5

(

)

100

)(

4

(

1900

=

+

=

+

=

+

=

+

+

=

+

=

12500

25000