Hoy en día existe una extensa variedad de herramientas que permiten incrementar la probabilidad de tomar mejores decisiones en cualquier organización. Cabe mencionar que entre esta gama de herramientas figuran los sistemas de información, los métodos estadísticos, las técnicas tradicionales de ingeniería industrial, la ingeniería económica, el procesamiento de datos, la investigación de operaciones y otras más.

La actividad llamada investigación de operaciones se desarrolla durante la segunda guerra mundial, pero sus orígenes pueden remontarse a muchos años atrás. Los que la ejercieron en tiempo de guerra estaban demasiados ocupados con los problemas que se presentaban para dedicarse a un análisis conciso de su metodología o escribir libros que pudieran ayudar a futuras generaciones. Los textos comenzaron a aparecer por el año de 1950, que fue cuando se consideró que investigación de operaciones era una materia digna de incluirse en los programas de estudios profesionales, como en las carreras de: economía, administración pública, psicología, trabajo social, matemáticas, estadística y las numerosas ramas de la ingeniería.

El objetivo de la Investigación de Operaciones es proporcionar un método sistemático y racional para los problemas fundamentales del control del sistema, mediante la toma de decisiones, las cuales, de alguna forma, producen los mejores resultados.

DefiniciónInvestigación de Operaciones, es el trabajo desarrollado por especialistas en la solución de problemas, con el fin de que produzcan soluciones que mejor sirvan a los objetivos de toda organización.

OrganizaciónUna organización se puede interpretar como un sistema, todo sistema tiene componentes e interacciones entre los mismos.SistemaTodo sistema es una estructura que funciona. La forma es el elemento que convierte a la estructura en un sistema. Se puede concluir que todo sistema es un sistema de información.

Investigación de operaciones

1

Las investigaciones es la aplicación de la metodología científica a través de los modelos, primero para representar al problema real que se quiere resolver en un sistema y segundo resolverlo (objetivo).

Formulación de modelosEs el proceso de tomar un problema del mundo real y describirlo en términos matemáticos.

Técnicas de solución o algoritmosSon las técnicas matemáticas usadas para encontrar respuestas a partir de los modelos creados.

Soluciones por computadoraEs el manejo de programas estandarizados de cómputo para resolver los modelos.

FilosofíaEs una panorámica de las relaciones entre el mundo real, los modelos, los administradores y las soluciones.

La investigación de operaciones utiliza tres tipos de problemas: determinísticos, con riesgos y bajo incertidumbre:

a) Los problemas determinísticos son aquellos en los que cada alternativa del problema, tiene una y sólo una solución.

b) Los problemas con riesgos son aquellos en los que cada alternativa del problema, tiene varias soluciones.

c) Los problemas de bajo incertidumbre son aquellos en los que cada alternativa del problema, tiene varias soluciones sin embargo, se ignora con que probabilidad o distribución probabilística ocurrirán estas soluciones.

Construcción de modelosEn la investigación de operaciones existen tres clases de modelos: Icónicos, Analógicos y simbólicos:

a) Los modelos icónicos son imágenes a escala del sistema cuyo problema se requiere resolver. Por ejemplo, las fotografías, las maquetas, dibujos y modelos a escala de barcos, automóviles, aviones, canales, etc.

b) Los modelos analógicos se basan en la representación de las propiedades de un sistema cuyos problemas se requieren para resolver utilizando otro sistema cuyas propiedades son equivalentes.

2

Por ejemplo, las propiedades de un sistema hidráulico son equivalentes a un sistema eléctrico o, inclusive, económico.

c) Los modelos simbólicos son conceptualizaciones abstractas del problema real a base de del uso de letras, número, variables y ecuaciones.

FUNDAMENTOS DE LA PROGRAMACIÓN LINEAL

Desde un punto de vista puramente matemático, “La programación lineal es una técnica utilizada para maximizar o minimizar una función sujeta a restricciones lineales”. Ahora bien, hablando en términos económicos, “La programación lineal es una técnica empleada para distribuir un grupo de recursos limitados, entre un número de demandantes competidores, los cuales, toman decisiones sobre el intercambio de productos”, es decir, el papel fundamental que juega esta herramienta matemática dentro de la economía, es el de economizar al máximo los recursos disponibles, determinando el programa óptimo más conveniente para su aplicación en la unidad (centro de producción, empresa, etc.) objeto de estudio.

Conceptos BásicosEl problema general de la programación lineal está representado por una serie de ecuaciones e inecuaciones lineales formadas por un número finito de variables.

Función objetivoEs la función lineal que indica la finalidad que se persigue en el problema, en el caso de la economía, maximizar ganancias o minimizar costos, es de la forma siguiente: Y= a + bX.CostosSe refiere a los coeficientes de las variables de la función objetivo (en el cuadro simplex los representamos con Ci), implica el total de recursos monetarios utilizados en la producción de un producto determinado.

ActividadEs un método específico que conduce a la realización de un fin determinado. Por ejemplo, cultivar ajonjolí, maíz, frijol, etc., en una granja, de tal forma que se obtenga la producción deseada.

AlternativasImplica las diferentes formas de combinación que se pueden hacer para lograr un objetivo. Por ejemplo, las formas de cultivo que se deben combinar los tres productos anteriores, de tal manera que se obtenga una utilidad óptima.

3

RestriccionesEs la condición en que normalmente se presentan los recursos escasos con que se cuentan para producir. Si no hay restricciones prácticamente no hay problema(Se pueden aparecer como ecuaciones o bien como inecuaciones).

Variable de holguraEs la cantidad de recursos no utilizado en el programa, cuya función principal desde un punto de vista matemático es la de romper la inecuación o desigualdad llamada restricción, que se presenta en todo el problema de programación lineal. El coeficiente, o sea el costo de esta variable, será siempre cero.

Variable artificialEs un artificio para poder trabajar con el cuadro simplex pero no interviene en la solución del problema; esta variable artificial cuando se trate de un problema de minimización, su valor será +M, en donde M es un valor tan grande como se desee.

Programa optimoEs la solución básica factible que nos conduce a obtener una utilidad o beneficio mayores, esto es, a maximizar las ganancias o minimizar los costos de un programa.

Variable entranteEs la variable o actividad que entra o se incorpora la solución del problema, ella incrementa la función en cierta cantidad.Variable salienteEs la actividad que deja de intervenir en la producción por resultar in-eficiente en relación con otras actividades.

MinimizarEs la reducción de los costos en la generación de un producto en su optima expresión.

MaximizarEs elevar lo más posible las utilidades en la solución de un problema de programación lineal.

INTERSECCIÓN DE RECTAS

4

Dos rectas no paralelas en el plano deben cortarse y las coordenadas del punto de intersección satisfacen ambas ecuaciones puesto que el punto está en las dos rectas; sí, por ejemplo, las ecuaciones de las rectas son

2X - Y - 7 = 0 y 4X + 3Y - 9 = 0

entonces la solución del sistema da los valores de X e Y que satisfacen ambas ecuaciones y estos valores deben ser las coordenadas del punto de intersección. Un método simple para encontrar la solución es de eliminación; multiplicamos la primer ecuación por tres y sumándosela a la segunda, obtenemos

6X - 3Y - 21 = 04X + 3Y - 9 = 0

10X - 30 = 0 : X = 3

Ahora, reemplazamos X por 3 en cualquiera de las dos ecuaciones iniciales y nos da como resultado Y = -1. El punto de intersección es (3, -1).

Y

3-

2-

1- X

-1 0 1 2 3 4

-1- (3, -1)

-2-

-3-

Dos rectas que se cortan dividen el plano en cuatro regiones. La siguiente figura muestra como las rectas:

2x – y = 4 y 3x + y = 11

5

Dividen el plano en 4 regiones que denotaremos R1 R 2 R 3 R 4. Cada una de las regiones queda descritas por un par de desigualdades; es decir, cada punto en R1 satisface simultáneamente.

2x - y - 4 = 0 y 3x + y - 11 = 0

análogamente, las regiones restantes satisfacen los pares de desigualdades que se indican en la figura:

Considerando el siguiente par de rectas conteste las siguientes preguntas:a) ¿Cuál es la intersección?b) Indique las regiones del dominio de valores.

Recta 1: 2X - Y = 4 Recta 2: 3X + Y = 11

6

Solución:a) 5X = 15 X = 3 Y = 2 (3,2)

b) R1 (3,4) R2 (4,2) R3 (3,0) R4 (2,2) 2 < 4 6 > 4 6 > 4 2 < 4 Ec. 1 13 > 11 14 > 11 9 < 11 8 < 11 Ec. 2

(1) 2X – 3Y + 5 = 0 (2) X – 6Y + 7 = 0

R1 (2,2) R2 (-1,0) R3 (-3,0) R4 (-2,2)1er. Ec. 3 > 0 3 > 0 -1 < 0 -5 < 0 2da. Ec. –3 < 0 7 > 6 6 > 4 -7 < 0

7

EXPRESIÓN MATEMÁTICA DE PROGRAMACIÓN LINEAL

El problema general de la programación lineal en forma matemática, se empleará la variable “Xi” con el objeto de simbolizar las actividades que intervienen en el problema. Después de analizar el concepto del programa general de la programación lineal, es factible expresarlo matemáticamente de la siguiente manera: encontrar X1, X2, X3,...Xn. Cuyos valores optimicen la función lineal llamada función objetivo.Max. Zx = U1X1 + U2X2 + U3X3 + .......... + UnXn

Sujeta a las condiciones:

A11X1 + A12X2 + A13X3 + .......... + A1nXn < B1

A21X1 + A22X2 + A23X3 + ........ + A2nXn < B2

. . . . .

. . . . .

. . . . .Am1X1 + Am2X2 + Am3X3 + .....… + AmnXn < Bn

Con X1, X2, X3, ........, Xn > 0

Donde Aj, Bj, Uj son constantes

También es posible expresar el problema general de la programación lineal de la forma que sigue:

Max. Zx = UX

s.a. Ax < Bx

X > 0

Ambas expresiones tienen el mismo significado, solo que la primera es en forma algebraica y la segunda en forma matricial.

PLANTEAMIENTO DE PROBLEMAS LINEALES

PROBLEMA 1Una ama de casa interesada por satisfacer las necesidades alimenticias de su esposo, empleando para ello el menor gasto posible.

8

Decide comprar solamente leche, carne y huevos. Al llegar al mercado se encuentra con los siguientes costos: un litro de leche cuesta $4.00, un Kg de carne $40.00 y una docena de huevos $4.00Consultando su guía de dietas aprende que el contenido de vitaminas B en las anteriores cantidades de alimento es igual a 20 mgs.; 10 mgs. Y 10 mgs, respectivamente.El contenido de vitamina C es en forma análoga: 10 mgs., 20 mgs, y 10 mgs.¿Qué cantidades de cada uno de los alimentos debe comprar el ama de casa si los requerimientos mínimos diarios para un adulto son de : 60 mgs. de vitamina B y 50 mgs. de vitamina C?

Planteamiento del problema.Para llegar al modelo matemático con mayor facilidad, es conveniente elaborar una tabla presentando las interrelaciones que existen entre los elementos que se dan en el problema

VITAMINAS LITRO KILO DOCENA REQUERIMIENTOS LECHE CARNE HUEVOS MÍNIMOS

B 20 10 10 60C 10 20 10 50

PRECIOS $4.00 $40.00 $4.00

Nuestras variables de decisión serán:X1 = Número de litros de leche a comprarX2 = Número de kgs. de carne a comprarX3 = Número de docenas de huevo a comprar.

Se conoce que el ama de casa quiere cumplir la dieta alimenticia, al mínimo costo posible, es decir, que los $4.00 que le cuesta el litro de leche (4X1), más los $40.00 que vale el kilogramo de carne (40X2), más los $4.00 que le cuesta la docena de huevos (4X3),Signifiquen para ella un gasto mínimo y al mismo tiempo cumpla con la dieta alimenticia. Entonces la función objetivo expresada matemáticamente será:

Minimizar G = 4X1 + 40X2 + 4X3

Esta función objetivo, estará sujeta a ciertas restricciones que corresponden a los requerimientos mínimos de vitaminas que deben tener cada uno de los alimentos comprados.La primera restricción indica que el contenido de vitamina B, de los tres productos no deberá ser menor de 60 mgs., o sea que el contenido de vitamina B del litro de leche (20X1) más el contenido de vitamina B del kg.

9

de carne (10X2), más el contenido de vitamina B de una docena de huevo (10X3) que se compren sea mayor o igual a 60 mgs. que es el requerimiento mínimo de vitamina B, para cumplir la dieta. De esta manera nuestra primera restricción será:

20X1 + 10X2 + 10X3 60

En forma análoga lo que se compre de leche, carne y huevo no deberá ser menor que 50 mgs. de vitamina C, que se requieren en la dieta como mínimo. Entonces la segunda restricción será:

10X1 + 20X2 + 10X3 > 50

Resumiendo el modelo quedará:

Minimizar Z = 4X1 + 40X2 + 4X3

s.a. 20X1 + 10X2 + 10X3 > 60

10X1 + 20X2 + 10X3 > 50

X1, X2, X3 > 0

PROBLEMA 2En una región agrícola un modesto agricultor desea conocer que cantidad de cada producto le conviene cultivar para obtener una utilidad máxima bajo el siguiente programa. Los recursos con que cuenta son: 12 hectáreas de tierra, 48 horas de mano de obra y $360 de capital.

Sus actividades reales, o sea lo que puede cultivar dada la naturaleza del suelo son: maíz, sorgo y avena.Los correspondientes coeficientes técnicos para el cultivo de maíz son: 1 hectárea de tierra, 6 horas hombre y $36 de capital, con lo que espera obtener una utilidad de $40. Los coeficientes para el sorgo de manera similar son: 1 hectárea de tierra, 6 horas hombre y $24 de capital, esperando obtener $30 por la venta del producto. Por ultimo los coeficientes técnicos para el cultivo de avena son: 1 hectárea de tierra, 2 horas hombre y $18 de capital, con lo que espera obtener un ingreso de $20 al vender el producto.Formulación del modelo:

Recursos Maíz Sorgo Avena Disponibilidad total Tierra 1 ha. 1 ha. 1 ha. 12 has. Trabajo 6 hrs 6 hrs. 2 hrs. 48 hrs. Capital $ 36 $ 24 $ 18 $ 360

10

Utilidad $ 40 $ 30 $ 20 ----

Debido a que lo que se desea, es conocer el número de has. que se deben sembrar de cada cultivo, las variables de decisión son:

X1 = Número de has. a sembrar de maízX2 = Número de has, a sembrar de sorgoX3 = Número de has. a sembrar de avena

Una vez elaborado el cuadro y conociendo que el deseo del agricultor es maximizar su utilidad, la función objetivo será: Maximizar los $40 que se espera recibir por la venta de maíz (40X1) más los $30 que espera obtener por la venta de sorgo (30X2), más los $20 que espera obtener por la venta de avena (20X3); matemáticamente.

Maximizar Z = 40X1 + 30X2 + 20X3

s.a. X1 + X2 + X3 < 12

6X1 + 6X2 + 2X3 < 48

36X1 + 24X2 + 18X3 < 360 X1, X2, X3 > 0

PROBLEMA 3Proyecto para el control de avenidas de un río.El gobierno de un país desea construir un sistema de presas para el control de avenidas de un extenso río de cuencas.Por razones topográficas, los técnicos estiman que deben construirse 4 presas a lo largo del río en diferentes lugares; además para el sistema de avenidas y que sea efectivo se estima que las capacidades mínimas de las presas deben ser: 5000, 10000, 12000 y 7000 has./m3 para las presas P1, P2, P3, P4.

El gobierno considera que la realización del proyecto ayudara a un rápido desarrollo agrícola e industrial de la región; para fomentar dicho desarrollo y al mismo tiempo minimizar parte del costo del proyecto, se planea distribuir la capacidad de las presas con el propósito de proveer agua para riego y agua para generar corriente eléctrica.

Además tomando en consideración las posibilidades de desarrollo económico de las diferentes localidades, se ha establecido que la

11

capacidad total del proyecto de agua para irrigación y la capacidad total para generar energía eléctrica se ha distribuido de la siguiente manera:

Presa %Para riego %Para e. Eléctrica

P1 0 40 P2 20 30 P3 30 20 P4 50 10

El costo sobre ha. de riego es de $200 y por ha. de energía eléctrica es de $500. Se desea conocer qué cantidad de has. debe destinar para riego y que cantidad para energía eléctrica.

Minimizar Z = 200X1 + 500X2

s.a. 0.4X2 > 5000

0.2X1 + 0.3X2 > 10000

0.3X1 + 0.2X2 > 12000

0.5X1 + 0.1X2 > 7000

X1, X2 > 0

De la Ec. 1 : (0.40X2 5000 )(10) 4X2 = 50000 X2 = 12500

De la Ec. 2: (0.20X1 + 0.30X2 > 10000)(10) 2X1 + 3X2 = 100000

X1 = 0 X2 = 0X2 = 33.33 X1 = 50000

De la Ec. 3: (0.30X1 + 0.20X2 12000)(10) 3X1 + 2X2 > 120000

X1 = 0 X2 = 0 X2 = 60000 X1 = 40000

De la Ec. 4: (0.50X1 + 0.10X2 > 7000)(10) 5X1 + X2 = 70000 X1 = 0 X2 = 0 X2 = 70000 X1 = 1

12

PLANO DE SOLUCIONESFACTIBLE

1

4 3 2

Ec. 1 y 2 Ec. 1 y 3 Ec. 2 y 3X2 = 12500 X2 = 12500 (2X1 + 3X2 = 100000)(3)2X1 + 3X2 = 100000 3X1 + 2X2 = 120000 (3X1 + 2X2 = 120000)(2)X1 = 31250 X1 = 31666.66 X1 = 32000X2 = 12500 X2 = 12500 X2 = 12000Z = 12500000 Z = 12583332 Z = 12400000

MÉTODO SIMPLEX

CONCEPTOS BÁSICOS

Variables de HolguraEl método simplex requiere que las restricciones sean ecuaciones en vez de inecuaciones. Cualquier inecuación puede ser convertida en una ecuación agregando una cantidad no negativa en el lado de menor valor de la inecuación.

Considere la siguiente restricción, agregando una variable no negativa, llamada variable de holgura.

13

10 20 30 40 50 60 70 80 90 100

70

60

50

40

30

20X1 (miles)

X2 (miles)

10

6X1 + 12X2 + X3 = 120 (a*)

En (a*) X3 es el número de horas en construcción que faltan a (6X1+ 12X2) para aprovechar las 120 horas.

X3 = cantidad de tiempo no utilizado en construcción.

(Tiempo utilizado en construcción) + (Tiempo no utilizado en construcción) =120 ( 6X1 + 12X2 ) + ( X3 ) =120

Similarmente, sea X4 la variable de holgura que representa el número de horas no utilizadas en pintura para la restricción de capacidad de pintura dada.

8X1 + 4X2 + X4 = 64 (b*) Es importante observar que las variables de holgura nunca pueden ser

negativas.

VARIABLE BÁSICAS Y SOLUCIONES BÁSICAS FACTIBLES

El conjunto de soluciones básicas en el nuevo problema dado en (a*) y (b*) no puede ser graficado ya que ahora tenemos cuatro variables. Por lo tanto, debemos buscar otra alternativa, para encontrar las soluciones factibles (a*) y (b*) tienen dos ecuaciones y cuatro variables. Si tenemos más variables que ecuaciones, podemos tener un conjunto extra de variables iguales a 0, obteniendo así un sistema con igual numero de variables y restricciones. Una solución así llamada “solución básica” y por tanto, estamos interesados en encontrar soluciones básicas de tal manera que todas las variables tengan valores no negativos. Las variables que tienen valores positivos en la solución básica factible son llamadas variables básicas, las otras variables que tienen valor cero, son llamadas variables no básicas. Esto es la solución básica factible. X3 y X4 son las variables básicas. X1 y X2 son las variables no básicas.

RESUMEN SOBRE EL MÉTODO SIMPLEX

14

1. El método simplex encuentra una solución óptima (o una solución básica óptima factible).

2. El método simplex es un método de cambio de bases. Una variable entra a la base, la variable básica entrante, y una variable sale de la base, la variable básica saliente.

3. El método de cambio implica el reemplazo de un sistema de restricciones – inecuaciones por un sistema equivalente de restricciones – ecuaciones.

4. En un sistema de restricciones – ecuaciones, una ecuación puede ser remplazada por una ecuación equivalente aplicando las operaciones siguientes:

a) Remplazar una ecuación por sí misma, tantas veces una constante diferente de cero.

b) Remplazar una ecuación por sí misma, sumada a tantas veces una constante diferente de cero otra ecuación restricción.

5. El método simplex requiere que la función objetivo sea expresada de tal forma que cada variable básica, tenga coeficiente 0.

6. El método simplex requiere que cada variable básica aparezca en una y solamente una ecuación-restricción.

Columna pivote. Es la columna de coeficientes que están asociados con la variable no básica que ha sido escogida para convertirse en la variable básica entrante.

Fila pivote. Es la fila de coeficientes que contiene la variable básica actual y que contiene coeficiente + 1, es la que se ha escogido como la variable básica saliente.

Número pivote. Es el coeficiente que está en la intersección entre la columna y la fila pivote.

Considerando el problema de la Fabrica de Muebles Tennessee (FMT).

Maximizar Z = 200X1 + 240X2

s.a. 6X1 + 12X2 < 120 (1) 8X1 + 4X2 < 64 (2)

X1, X2 > 0

Solución:

Z - 200X1 - 240X2 = 0 (0) 6X1 + 12X2 + X3 = 120 (1) 8X1 + 4X2 + X4 = 64 (2)

15

Variablebásica

No. deecuación Z X1 X2 X3 X4

Ladoderecho

Z 0 1 -200 -240 0 0 0X3 1 0 6 12 1 0 120X4 2 0 8 4 0 1 64

Variablebásica

No. deEcuación Z X1 X2 X3 X4

Ladoderecho

Z 0 1 -80 0 20 0 2400X2 1 0 ½ 1 1/12 0 10X4 2 0 6 0 -1/3 1 24

Variablebásica

No. deecuación Z X1 X2 X3 X4

Lado derecho

Z 0 1 0 0 280/18 40/3 2720X2 1 0 0 1 1/9 -1/12 8X1 2 0 1 0 -1/18 1/6 4

Z = 2720X1 = 4X2 = 8

COMPROBACIÓN GRÁFICA

6X1 + 12X2 = 120 (1) 8X1 + 4x2 = 64 (2) De la Ec. (1) De la Ec. (2)X1 = 0 X2 = 0 X1 = 0 X2 = 0X2 = 10 X1 = 20 X2 X2 = 16 X1

= 8

18

16

Solución: 14

12 2X1 = 4X2 = 8 10

8

16

Z = $2720 Plano 6 de

Soluciones 1 X1

6 8 10 12 14 16 18 20

Maximizar Z = 12X1 + 4X2 (Cuaderno Pág. 63-A) s.a. X1 + 2X2 < 800 X1 + 3X2 < 600 2X1 + 3X2 < 2000

X1, X2 > 0

Variablebásica

No. deecuación

Z X1 X2 X3 X4 X5 Ladoderecho

Z 0 1 -12 -4 0 0 0 0X3 1 0 1 2 1 0 0 800X4 2 0 1 3 0 1 0 600X5 3 0 2 3 0 0 1 2000

Variablebásica

No. deecuación

Z X1 X2 X3 X4 X5 Ladoderecho

Z 0 1 0 32 0 12 0 7200X3 1 0 0 -1 1 -1 0 200X1 2 0 1 3 0 1 0 600X5 3 0 0 -3 0 -2 1 800

X1 = 600X2 = 0Z = 7200

Comprobación:

0 12 0 800 72001 -1 0 600 = 200 0 1 0 2000 600 0 -2 1 800

Max. Z = 2X1 + X2 + 3X3 (Libro del Politécnico Pág. 91 s.a. X1 + X2 + X3 < 6 cuaderno Pág. 78-A)

17

2X1 + 3X2 + x3 9 4X1 + 2X2 + x3 = 10 X1, X2, X3 0

X1 + X2 + X3 + X4 = 6 (1)

2X1 + 3X2 + X3 + X5 = 9 (2)

4X1 + 2X2 + X3 + X*6 = 10 (3)

Max Z = 2X1 + X2 + 3X3 - MX*6

Z - 2X1 - X2 - 3X3 + MX*6 = 0 (0)-M(4X1 + 2X2 + X3 + X*6 = 10)Z + X1 (-2 –4M) + X2 (-1 –2M) + X3 (-3 –M) = -10M

Variablebásica

No. deecuación

Z X1 X2 X3 X4 X5 X*6 LadoDerecho

Z 0 1 -2-4M -1-2M -3-M 0 0 0 -10MX4 1 0 1 1 1 1 0 0 6X5 2 0 2 3 1 0 1 0 9X*6 3 0 4 2 1 0 0 1 10

Variablebásica

No. deecuación

Z X1 X2 X3 X4 X5 X*6 LadoDerecho

Z 0 1 0 0 -5/2 0 0 1/2+M 5X4 1 0 0 ½ ¾ 1 0 -1/4 7/2X5 2 0 0 2 ½ 0 1 -1/2 4X1 3 0 1 1/2 1/4 0 0 1/4 5/2

Variablebásica

No. de ecuación

Z X1 X2 X3 X4 X5 X*6 Lado derecho

z 0 1 0 5/3 0 10/3 0 -1/3+M 50/3X3 1 0 0 2/3 1 4/3 0 -1/3 14/3X5 2 0 0 5/3 0 -2/3 1 -1/3 5/3X1 3 0 1 1/3 0 -1/3 0 1/3 4/3

Z = 50/3X1 = 4/3X2 = 0X3 = 14/3

18

Minimizar Z = 3X1 + 5X2

s.a. 2X1 – 5X2 > 8 (1) X1 + X2 < 5 (2) X1 - 3X2 = 7 (3)

X1 , X2 > 0 De la Inecuación (1)(2X1 – 5X2 > 8) (-1)-2X1 + 5X2 < -8(-2X1 + 5X2 + X3 = -8) (-1)2X1 –5X2 – X3 + X*4 = 8 (1)

De la inecuación (2) X1 + X2 < 5X1

+ X2 + X5 = 5 (2)

De la inecuación (3)X1 – 3X2 = 7X1 – 3X2 + X*6 = 7 (3)

De la inecuación (0)Min Z = 3X1 + 5X2

(Min Z = 3X1 + 5X2) (-1)Max -Z = -3X1 - 5X2 + 0X3 + 0X5 – MX*4 – MX*6 Max -Z + 3X1

+ 5X2 + MX*4 + MX*6 = 0Max -Z + 3X1 + 5X2 + MX*4 + MX*6 = 0 (2X1 – 5X2 – X3 + X*4 = 8) (-M)

-Z + (3 –2M)X1 + (5 +5M)X2 + MX3 + MX*6 = -8M

(X1 – 3X2 + X*6 = 7) (-M)

-Z + (3 –3M)X1 + (5 + 8M)X2 + MX3 = -15M (0)

Variablebásica

No. deecuación

Z X1 X2 X3 X*4 X5 X*6 Ladoderecho

Z 0 -1 3-3M 5+8M M 0 0 0 -15X*4 1 0 2 -5 -1 1 0 0 8X5 2 0 1 1 0 0 1 0 5X*6 3 0 1 -3 0 0 0 1 7

19

NOTA: Este problema no tiene solución, se checo con el programa Tora.

Minimizar Z = 0.4X1 + 0.5X2 Z = 4X1 + 5X2

s.a. 0.3X1 + 0.1X2 < 2.7 3X1 + X2 < 27 0.5X1 + 0.5X2 = 6 5X1 + 5X2 = 60 0.6X1 + 0.4X2 > 6 6X1 + 4X2 > 60 X1, X2 > 0 X1, X2 > 0

De la inecuación (1)3X1 + X2 + X3 = 27 (1)

De la inecuación (2)5X1 + 5X2 + X*4 = 60 (2)

De la inecuación (3)6X1 + 4X2 – X5 + X*6 = 60 (3)(Min Z = 4X1 + 5X2) (-1)Max -Z = - 4X1 – 5X2 – MX*4 – MX*6

-Z + 4X1 + 5X2 + MX*4 + MX*6 = 0-M(5X1+ 5X2 + X*4 = 60)

-Z + X1(4 – 5M) + X2(5 – 5M) + MX*6 = - 60M-M(6X1 + 4X2 – X5 + X*6 = 60) -Z + X1(4 – 11M) + X2(5 – 9M) + MX5 = -120M (0)

Variablebásica

No. deecuación Z X1

X2 X5 X3

X*4

X*6 Ladoderecho

Z 0 -1 4-11M 5–9 M M 0 0 0 -120MX3 1 0 3 1 0 1 0 0 27X*4 2 0 5 5 0 0 1 0 60X*6 3 0 6 4 -1 0 0 1 60

Variablebásica

No. deecuación Z X1 X2

X5 X3

X*4 X*6

Ladoderecho

Z 0 -1 0 11/3 – 16/3M

M -4/3 + 11/3M

0 0 -36-21M

X1 1 0 1 1/3 0 1/3 0 0 9X*4 2 0 0 10/3 0 -5/3 1 0 15

20

X*6 3 0 0 2 -1 -2 0 1 6

Variablebásica

No. deecuación Z X1 X2 X5 X3 X*4 X*6

Ladoderecho

Z 0 -1 0 0 11/6 – 10/6M

7/3 – 5/3M

0 -11/6+ 16/6M

- 47 – 5M

X1 1 0 1 0 1/6 2/3 0 -1/6 8

X*4 2 0 0 0 10/6 5/3 1 -5/3 5

X2 3 0 0 1 -1/2 -1 0 1/2 3

Variablebásica

No. deecuación Z X1 X2 X5 X3 X*4 X*6

Ladoderecho

Z 0 -1 0 0 0 1/2 -11/10+M M 315/6

X1 1 0 1 0 0 1/2 -1/10 0 15/2

X5 2 0 0 0 1 1 3/5 -1 3

X2 3 0 0 1 0 -1/2 3/10 0 9/2

Min. Z = 32X1 + 8X2

s.a. X1 > 200 2X1 + X2 > 300

X1, X2 > 0

De la inecuación (1):X1 – X3 + X*4 = 200 (1)

De la inecuación (2):2X1 + X2 – X5 + X*6 = 300 (2) (Min. Z = 32X1 + 8X2) (-1)Max. –Z = -32X1 – 8X2 – X*4 – X*6

-Z + 32X1 + 8X2 + MX*4 + MX*6 = 0-M(X1 – X3 + X*4 = 200)

-Z + X1(32 – M) + 8X2 + MX3 + MX*6 = -200M

X1 = 15/2X2 = 9/2Z = 5.25

21

-M(2X1 + X2 –X5 + X*6 = 300) -Z + X1(32 – 3M) + X2(8 – M) + MX3 + MX5 = -500M (0)

Variablebásica

No. deecuación

Z X1 X2 X3 X5 x*4 x*6 Ladoderecho

Z 0 -1 32-3M 8-M M M 0 0 -500MX*4 1 0 1 0 -1 0 1 0 200X*6 2 0 2 1 0 -1 0 1 300

Variablebásica

No. deecuación

Z X1 X2 X3 X5 x*4 x*6 Ladoderecho

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

M 16 – 1/2M

0 -16+3/2M -4800 – 50M

X*4 1 0 0 -1/2 -1 1/2 1 -1/2 50X1 2 0 1 1/2 0 -1/2 0 1/2 150

Variablebásica

No. deecuación

Z X1 X2 X3 X5 X*4 X*6 Ladoderecho

Z 0 -1 0 8 32 0 -32+M M -6400X5 1 0 0 -1 -2 1 2 -1 100X1 2 0 1 0 -1 0 1 0 200

Comprobación:

-32 + M M 200 -6400 + 500M 2 -1 300 = 100 1 0 200

X1 = 200 X2 = 0 Z = 6400

DUALIDAD

Dado un conjunto cualquiera de datos para un modelo de programación lineal, podemos usar los mismos datos para formar un modelo de programación lineal diferente. El problema resultante se llamará Dual del origen. El Dual tiene importancia teórica, económica y computacional que vamos a analizar. Primero, vamos a ver como se forma exactamente el problema dual.

22

Reglas de transformación.

Para examinar la teoría de la dualidad en una forma satisfactoria tenemos que desechar la restricción de que las variables de un modelo de programación lineal sean no negativas. Por ejemplo, consideremos el siguiente problema.

Problema (E1)

Max 3X1 + 4X2 – 2X3 s.a. 4X1 –12X2 + 3X3 12 - 2X1 + 3X2 + X3 6 - 5X1 + X2 – 6X3 -40 3X1 + 4X2 – 2X3 10 X1 0, X2 0, X3 no restringida en signo.Vemos en este problema la presencia de todos tipos de restricciones (<, > y =), Además, hemos desechado, el requerimiento de que todas las variables deban ser no negativas. En este ejemplo, sólo hemos requerido que X1 sea no negativa. Se ha requerido que la variable X2 sea no positiva y X3 carece de restricción de signo. (Es decir, el valor óptimo de X3 podrá ser positivo, negativo o cero). El dual de este problema (El) se formula aplicando las siguientes reglas. REGLA 1.- El número de Variables del problema dual es igual al número de restricciones del problema original.El número de restricciones del problema dual es igual al número de variables del problema original. REGLA 2.- Los coeficientes de la función objetivo en el problema dual serán el vector de recursos del problema original. La función objetivo del problema dual será:

Z = 12Y1 + 6Y2 – 40Y3 + 10Y4

REGLA 3.- Si el problema original es un modelo de maximización, el dual será uno de minimización. Si el problema original es uno de minimización, el dual será uno de maximización.

Min Z = 12Y1 + 6Y2 – 40Y3 + 10Y4

REGLA 4.- Los coeficientes de la primera función de restricción de los problemas dual son los coeficientes de la primera variable en las restricciones del problema original, y en forma análoga para las otras restricciones.

23

s.a. 4Y1 – 2Y2 – 5Y3 + 3Y4

-12Y1 + 3Y2 + Y3 + 4Y4 3Y1 + Y2 – 6Y3 – 2Y4 REGLA 5.- Los lados derechos de las restricciones duales son los coeficientes de la función objetivo del problema original.

Función de restricción LD 4Y1 – 2Y2 – 5Y3 + 3Y4 3 -12Y1 + 3Y2 + Y3 + 4Y4 4 3Y1 + Y2 – 6Y3 – 2Y4 -2

REGLA 6.- El sentido de iésima restricción dual es = si y solo si la iésima variable del problema original no tiene restricción de signo.

3Y1 + Y2 – 6Y3 – 2Y4 = -2

REGLA 7.- Si el problema original es un modelo de maximización (minimización), entonces, después de aplicar la regla 6, asigne a las restricciones duales el mismo (opuesto) sentido a la variable correspondiente del problema original.

Y1 – 2Y2 – 5Y3 + 3Y4 > 3-12Y1 + 3Y2 + Y3 + 4Y4

< 4 REGLA 8.- La i-ésima variable del problema dual no tendrá restricción del signo si y solo si la i-ésima restricción del problema original es una igualdad.

REGLA 9.- Si el problema original es un problema de maximización(minimización), entonces, después de aplicar la regla 8 asigne a las demás variables duales el signo contrario (el mismo signo) que las restricciones correspondientes en el problema original.

Y1 0 Y2 0 Y3 0 Y4 no restringida en signo

Ejemplos:

PRIMAL:Min –2X1 – X2 – 4X3 – 5X4

s.a. X1 + 3X2 + 2X3 + 5X4 20 2X1 + 16X2 + X3 + X4 4 3X1 – X2 – 5X3 + 10X4 -10 X1, X2, X3, X4 0

24

DUAL:Max 20y1 + 4y2 – 10y3s.a y1 + 2y2 + 3y3 -2 3y1 + 16y2 – y3 -1 2y1 + y2 – 5y3 -4 5y1 + y2 + 10y3 -5 y1 0, y2 0, y3 0 PRIMAL:Min. Z = X1 + 12X2 – 2X3

s.a 4X1 + 2X2 + 12X2 10 2X1 – X2 + 11X3 -2 X1 0, X2 no restringida en signo, X3 0

DUAL:Max Z = 10Y1 – 2Y2

s.a. 4Y1 + 2Y2 1 2Y1 – Y2 = 12

12Y1 + 11Y2 -2 Y1 0, Y2 0

INTERPRETACIÓN ECONÓMICA DEL PROBLEMA DUAL

Por ejemplo, a menudo, el problema primal tiene la interpretación de encontrar niveles de maximización de utilidad de la producción sujeta a restricciones sobre escasez de recursos. ¿Cómo se interpretaría el dual de este problema? Puesto que el dual sería un problema de minimización, diríamos que es un modelo de minimización de costos. Pero ¿minimizar el costo de hacer qué? El siguiente panorama dará la respuesta a esta pregunta. Supóngase que una firma posee dos fábricas en dos diferentes distritos mercantiles. Por simplicidad, supóngase que cada fábrica usa las mismas tres materias primas, escasas. La fábrica 1 elabora dos productos, tales como segadoras de pasto y esparcidoras, en las cantidades X1 y X2. La fábrica 2 elabora tres diferentes productos, perillas para puertas, manijas para refrigerador y cencerros para el ganado, en las cantidades Z1, Z2, y Z3, y la fábrica 2 usa precisamente las mismas materias primas que la fábrica 1. Los datos de la fábrica 1 se dan en la figura siguiente.

25

Datos de la fábrica 1

Materia prima

Insumo por segadora de

pasto

Insumo por

aspersora

Disponibilidadtotal

123

6110

437

383444

Redituabilidad

por unidad

4 3

Modelo de producción de la fábrica 1

Max 4X1 + 3X2

s.a. 6X1 + 4X2 < 38 X1 + 3X2 < 34 10X1 + 7X2 < 44

X1 , X2 > 0

Modelo de producción de la fábrica 2

Max 6Z1 + 2Z2 + Z3

s.a. 4Z1 + 2Z2 + 7Z3 < 54 3Z1 + 9Z2 + 8Z3 < 126 6Z1 + 5Z2 + 2Z3 < 33

Z1, Z2, Z3 > 0

Datos de la fábrica 2Materia prima Insumo por Insumo por manija Insumo

porperilla de refrigerador cencero

Disponibilidad

total

123

4 2 7 3 9 8 6 5 2

54126 33

26

Redituabilidadpor unidad 6 2 1

¿QUÉ ES UN PRECIO JUSTO?

Recordemos ahora nuestros supuestos de que la misma empresa posee ambas fábricas y que éstas están situadas en diferentes distritos mercantiles. Supongamos también que las tres materias primas son escasas porque transcurren largos plazos para su reparto. Supongamos ahora que el administrador obtiene información de que por diversas razones económicas, los precios (es decir, las utilidades) en el distrito de la fábrica 2 van a subir en forma drástica. No se sabe exactamente cuánto van a aumentar, pero el administrador confía en que el aumento será tan grande que conviene que la fábrica 2 se haga cargo de toda la producción. Así, todas las existencias de la fábrica 1 de materias primas deberán transferirse a la fábrica 2. Sin embargo el administrador decide que la fábrica 2 deberá pagar un “precio justo” a la fábrica 1 por las transferencias de esas materias primas. ¿Cuál será ese precio?.

Intuitivamente parece claro que, al menos desde el punto de vista de la fábrica 1, el precio justo sería aquel que igualase la máxima utilidad posible que ésta obtendría si retuviese el uso de sus recursos, que ahora se van a pasar a la fábrica 2. Este es el V.O. de la fábrica 1 y sería un justo “pago por paquete” por las tres materias primas. La firma, sin embargo, necesita saber más que el pago en paquete. Debe tener precios por unidad de cada material. Estos precios se necesitan para el informe financiero (es decir, para el impuesto).

Toda la contabilidad para productos individuales se formula sobre una base por artículo. La firma debe encontrar precios “justos” por unidad que puedan aceptar el escrutinio de una revisión cuidadosa. Para obtener precios “justos” por unidad haremos las siguientes observaciones. Si la fábrica 2 paga por unidad precios de Y1, Y2, y Y3 por las materias primas, puesto que la fábrica 1 posee 38, 34 y 44 unidades, respectivamente, de cada materia prima.

Cantidad que paga la fábrica 2 = 38y1 + 34Y2 + 44Y3

La fábrica 2 quiere obtener la máxima utilidad posible, por lo que su meta es

Min 38Y1 + 34Y2 + 44Y3

27

Sin embargo, la fábrica 1 quiere asegurarse de que obtendría tanta utilidad como si permaneciese en el negocio por si misma. En los datos que muestra la tabla de datos de la fábrica 1, vemos que si la fábrica 1 tuviese 6 unidades de la materia prima1, 1 unidad de ka materia prima 2 y 10 unidades de ka materia prima 3, podría producir una segadora de pasto para obtener una utilidad de $4. Recuerde que Y1 es el precio de venta de la materia i . Así, la fábrica 1 insistirá en que

6Y1 + Y2 + 10Y3 > 4

Si esta condición no se sostiene, la fábrica 1 preferirá no vender sus materias primas a la fábrica 2. Usando las materias primas para producir segadoras de pasto producirá más utilidades. De igual manera, la fábrica 1 insistirá en que

4Y1 + 3Y2 + 7Y3 > 3

De otro modo, resulta más provechosos fabricar aspersoras que vender las materias primas a la fábrica 2. En síntesis, entonces, el problema de determinar precios justos consiste en

Min 38Y1 + 34Y2 + 44Y3

s.a. 6y1 + y2 + 10y3 > 4 4Y1 + 3Y2 + 7Y3 > 3 Y1, Y2 > 0

Y este problema es el dual de (F1). Con esto hemos demostrado que el dual del problema de producción tiene la siguiente interpretación.

Proporciona “precios justos” en el sentido de que producen el pago mínimo aceptable de liquidación.

INTERPRETACIÓN COMPUTACIONAL DEL PROBLEMA DUAL

Cuando se usa el algoritmo simples para resolver un problema de programación lineal, resulta que se obtienen las soluciones óptimas tanto del problema original, que puede ser de maximización o de minimización, como de su dual Ya hemos visto este hecho sobre el listado de resultados por computadora (sujeta a un posible cambio de signo) y será demostrado matemáticamente en el capítulo 6. Así es que se requiere resolver un problema particular puede continuar con la resolución directa del problema. En forma alterna, se puede tomar el problema dual del original y resolverlo en la computadora. Esto producirá una solución del dual del dual, que es el problema original. Puesto que cada una de estas rutas

28

posibles conduce al mismo resultado, será interesante, desde el punto de vista de la computación, inquirir cuál es el procedimiento más eficiente.

Para ilustrar esta cuestión, debe tomarse nota del hecho empírico de que el tiempo requerido para resolver un programa lineal depende críticamente más del número de restricciones que el número de variables. Si el problema original tiene m restricciones y n variables, el problema dual tendrá n restricciones y m variables. Es entonces evidente que, siendo igual todo lo demás, se debe escoger resolver el problema que tenga menos restricciones.

Aunque la regla práctica anterior es una prescripción general razonablemente buena, cuando hay que habérselas con modelos bastante grandes y estructurados puede fallar, por que en tales casos los demás factores pueden no ser iguales. Las posibles razones para apartarse de esta regla práctica tienden a ser de naturaleza demasiado técnica. En algunos casos, sin tomar en cuenta el número de restricciones, uno de los dos problemas, debido a su forma, puede ser resuelto mediante un código especial, como el que llamamos código de redes, en oposición al código PL de índole general. Sin embargo, el otro problema puede no tener la estructura especial requerida y, por lo tanto, quizá deba ser resuelto con el código de índole general. Puesto que los códigos de estructuras especiales tienden a ser más eficientes en el cómputo que los de índole general, ésta es una consideración importante. Otras consideraciones técnicas se refieren al hecho de que, aun con un código general de programación lineal, puede ser mas fácil “arrancar” con un problema que con el otro.

La elección entre resolver el problema original o su dual no tiene demasiada importancia para el cómputo cuando se trata de problemas pequeños, digamos cuando ambos modelos tienen unos cuántos cientos de restricciones, ya que dichos problemas pueden ser manejados a gran velocidad por los equipos de computación modernos. Cuando los problemas se complican, en el rango de varios miles de restricciones, la elección entre el problema original y su dual llega a ser muy importante. En estos casos, la consulta técnica con un profesional de la programación lineal bien puede ser valiosa.

SENSIBILIDAD

El análisis de sensibilidad constituye una parte muy esencial en casi todos los estudios de programación lineal. Dado que algunos o todos los valores de los parámetros que se emplean en el modelo original son sólo

29

estimaciones de las condiciones futuras, es necesario investigar el efecto que se tendría sobre la solución óptima en caso de que prevalecieran otras condiciones. Aún más, ciertos valores de estos parámetros (como la cantidad de recursos) pueden representar decisiones de la gerencia, en cuyo caso de su elección debe ser el punto más importante de la investigación y, por supuesto, se puede estudiar a través del análisis de sensibilidad.

El análisis de sensibilidad se basa en la proporción de que todos los datos con excepción de una parte en el problema, se conservan fijos y que pedimos información sobre el efecto del cambio en esta parte de los datos a la que se permite variar. La información en la que podríamos estar interesados incluye: (1) el efecto sobre el VO (es decir, la máxima utilidad posible) y (2) el efecto sobre la política óptima E*, F*

PROBLEMA

PROTRAC, Inc, produce dos líneas de equipo pesado. Una de estas líneas de productos (llamada equipo para remoción de escombros) se destina esencialmente a aplicaciones de construcción. La otra línea (llamada equipos forestales) está destinada a ala industria maderera. El miembro más grande de la línea de equipos para remover escombro (el E-9) y el miembro mayor de la línea de equipos forestales (el F-9) se producen en el mismo departamento y con el mismo equipo. Haciendo uso de las predicciones económicas para el próximo mes, el gerente de mercadotecnia de PROTRAC juzga que durante ese periodo será posible vender todos los E-9 y F-9 que la empresa pueda producir. La administración debe ahora recomendar una meta de producción para el próximo mes. Es decir, ¿cuántos E-9s y F-9s deben producirse?

En la toma de decisión , los principales factores a considerar son los siguientes:PROTRAC tendrá una utilidad de $5000 por cada E-9 que se venda y $4000 por cada F-9. Cada producto pasa por operaciones mecánicas tanto en el departamento A como en el departamento B.

Para la producción del próximo mes, estos dos departamentos tienen disponibles 150 y 160 horas, respectivamente. Cada E-9 consume 10 horas de operación mecánica en el departamento A y 20 horas en el departamento B, mientras que cada F-9 consume 15 horas en el departamento A y 10 horas en el departamento B. Estos datos se resumen en la figura siguiente.

30

Departamento

Horas E-9 F-9 Total disponible

AB

10 15 15020 10 160

Con el objeto de cumplir un compromiso un compromiso con el sindicato, el total de horas de trabajo que se dedicarán a la verificación de los productos terminados del próximo mes no puede ser menos en 10% a una meta establecida de 150 horas. Esta verificación se realiza en un tercer departamento que no tiene relación con las actividades de los departamentos A y B. cada E-9 requiere de 30 horas de comprobación y cada F-9, 10. puesto que el 10% de 150 es 15, el total de horas de trabajo destinadas a la verificación no puede ser menos de 135. estos datos se concentran en la figura .

Formulación completa del problema de la PROTRAC, Inc.

Max 5000E + 4000F (función objetivo)

s.a. 10E + 15F < 150 (horas en el departamento A) (1) F 20E + 10F < 160 (horas en el departamento B) (2)

30E + 10F > 135 (horas de comprobación) (3)

E - 3F < 0 (restricción de mezcla) (4)

Requerimientos en1 E-9 1 F-9 total de horas

Horaspara verificación 30 10 135

31

11 E + F > 5 (total de unidades requeridas) (5)

E,F > 0 (condiciones de no negatividad)

9Plano de soluciones factibles

7 3 Línea de la función objetivo

5 Plano5

3 4 1

1 2

E 1 3 5 7 9 11 13 15 17

SENSIBILIDAD DE COEFICIENTES DE LA FUNCIÓN OBJETIVO

Consideremos incrementos en el coeficiente de F en la función objetivo, es decir, en su redituabilidad por unidad, en tanto que el coeficiente de E se mantiene fijo. Hemos visto en la figura, que los contornos de la función objetivo tenderán a ser más horizontales (tiene una pendiente menos negativa) cuando este coeficiente aumenta. Refiriéndonos a la figura anterior vemos que la solución óptima permanece en el vértice E* = 4.5, F*= 7.0 hasta que el coeficiente de F aumenta lo suficiente como para que los contornos de la función objetivo sean paralelos a la restricción (3). Cuando esto ocurra, habrá soluciones óptimas alternativas, el vértice actual (E* = 4.5, F* = 7.0) y el vértice determinado por la intersección de las restricciones (3 y 5).

Si el coeficiente de F continua creciendo, la solución actual (E* = 4.5, F* = 7.0) ya no será óptima y el punto determinado por la intersección de las restricciones (3 y 5) será el único óptimo. El aumento permisible para el coeficiente de F es así determinado por el aumento en el coeficiente que hace que los contornos de la función objetivo sean paralelos a la restricción (3). Podemos preguntar, ¿Cuándo sucede esto?.

Los contornos de la función objetivos serán paralelos a la restricción (3) cuando ambas rectas tengan la misma pendiente, lo que significa que los coeficientes deberán satisfacer la siguiente igualdad.

Coeficiente de E en (3) = coeficiente de E en objetivoCoeficiente de F en (3) = coeficiente de F en objetivo

32

Lo cual implica que 10 = 5000 15 coeficiente de F en objetivo

de lo cual se obtiene el coeficiente de F en el objetivo = (5000)(15/10) = 7500

En la función objetivo, el coeficiente actual de F en la función objetivo es 4000. Esta llega a ser paralela a (3), es decir, ocurren óptimos alternativos si este valor aumenta a 7500. Entonces la solución óptima actual permanece vigente en tanto que el incremento de F sea < 3500. Esto es lo que se llama aumento permisible del coeficiente de F. Es el valor que se muestra en la figura 5.6 bajo el rubro “ALLOWABLE INCREASE” para F. Esta combinación de álgebra y geometría explica tanto el significado como el valor de este dato en el resultado computacional. Mas aún, mediante la observación de cómo afecta el cambio de los coeficientes a la pendiente de la función objetivo, podemos hacer las siguientes generalizaciones importantes.

EFECTO SOBRE LOS CONTORNOS DE LA FUNCIÓN OBJETIVO

El cambio de los coeficientes de la función objetivo altera la pendiente de los contornos de ésta. Esto puede afectar o no a la solución óptima y al valor óptimo de la función objetivo

Recordamos ahora que cuando el coeficiente de F aumenta (conservándose fijo el coeficiente de E) obtendremos finalmente una nueva solución en la que el valor óptimo de F habrá aumentado. Esto concuerda con la intuición, ya que un aumento en la redituabilidad de F no motivará que produzcamos F a un nivel más bajo. Esto ilustra el concepto general de que

EFECTO SOBRE LA ACTIVIDAD EN UN MODELO DE MAXIMIZACIÓN

Es un modelo de maximización el aumento en la redituabilidad de una actividad, conservando invariables los demás datos, no puede reducir el nivel óptimo de esa actividad.

La situación para un modelo de minimización de costos es precisamente lo inverso. Puesto que se quiere minimizar el costo total, no se esperará que

33

cuándo se aumenten los costos de una actividad, mientras se mantienen constantes los demás datos, se puede llegar aun nivel óptimo mayor de esa actividad. Eso ilustra el concepto general de que

EFECTOS SOBRE LA ACTIVIDAD EN UN MODELO DE MINIMIZACIÓN

En un modelo de minimización el aumento en el costo de una actividad, conservando invariables los demás datos, no puede aumentar el nivel óptimo de dicha actividad.

Considere el siguiente PL.

Maximizar 20X1 + 10X2 s.a. X1 + 2X2 < 120 X1 + X2 < 90

X1 < 70X2 < 50

X1 > 0; X2 > 0

Tabla final

Variable

básica

No. de ecuaci

ónZ X1

X2

X3 X4

X5 X6 Lado derecho

ZX3

X2

X1

X6

01234

10000

00010

00100

01000

10 -2 1 0 -1

101-111

00001

1600 10 20 70 30

Resuelva el problema haciendo los siguientes cambios.Cambios bi: (b1, b2, b3, b4) = (100, 70, 70, 40)Cambios Ci: (C1, C2) = (15, 20)

34

Comprobación:

0 10 10 0 120 16001 -2 1 0 90 10 0 1 -1 0 70 = 200 0 1 0 50 70

0 -1 1 1 30

0 10 10 0 100 14001 -2 1 0 70 30 0 1 -1 0 70 = 00 0 1 0 40 70

0 -1 1 1 40

Variable

básica

No. de ecuaci

ónZ X1

X2

X3 X4

X5 X6 Lado derecho

ZX3

X2

X1

X6

01234

10000

50010

00100

01000

10-2 1 0-1

101

-111

00001

1400 30 0 70 40

0 10 10 0 1 20 20 – 15 = 51 -2 1 0 1 0 0 1 -1 0 1 = 00 0 1 0 0 1

0 -1 1 1 0

Variable

básica

No. de ecuaci

ónZ X1

X2

X3 X4

X5 X6 Lado derecho

ZX3

X2

012

100

000

001

010

10-2 1

51

-1

000

1050 30 0

35

X1

X6

34

00

10

00

00

0-1

11

01

70 40

0 10 10 0 2 10 10 – 20 = -101 -2 1 0 1 0 0 1 -1 0 0 = 10 0 1 0 1 0

0 -1 1 1 0

Variable

básica

No. de ecuaci

ónZ X1

X2

X3 X4

X5 X6 Lado derecho

ZX3

X2

X1

X6

01234

10000

00010

-10 0 1 0 0

01000

10-2 1 0-1

51

-111

00001

1050 30 0 70 40

Variable

básica

No. de ecuaci

ónz X1

X2

X3 X4

X5 X6 Lado derecho

ZX3

X2

X1

X6

01234

10000

00010

00100

01000

20 -2

1 0-1

-5 1-1 1 1

00001

1050 30 0 70 40

Variable

básica

No. de ecuaci

ónZ X1

X2

X3 X4

X5 X6 Lado derecho

ZX5

X2

X1

X6

01234

10000

00010

00100

511-1-1

10-2-1 2 1

01000

00001

1200 30 30 40 10

Para este problema, la solución es:X1 = 40X2 = 30Z = 1200

36

Si comprobamos todos los cambios, resolviendo el modelo como uno original, el resultado sería el mismo.

PROBLEMAS DE TRANSPORTE

La programación lineal es el caballito de batalla de los modelos cuantitativos. La aptitud para manejar cientos de restricciones, miles de variables de decisión, y la increíble cantidad de iteraciones que esos números implican, hacen que la programación lineal (PL) sea un instrumento para una gran variedad de problemas.

En los problemas de transporte, el administrador debe determinar como hacer llegar los productos de sus diversos almacenes a sus consumidores con el objeto de satisfacer la demanda a un costo mínimo. Este modelo es importante debido a sus exitosas aplicaciones y por que se puede resolver en forma rápida y eficiente mediante algoritmos especiales.

EJEMPLO 1La PROTRAC tiene cuatro plantas ensambladoras en Europa. Están ubicadas en:(1) Leipzig Alemania Oriental(2) Nancy Francia(3) Lieja Bélgica(4) Tilburgo HolandaLas máquinas ensambladoras usadas en esas plantas se producen en E.U. y se embarcan a Europa, llegan a los puertos de Amsterdam (A), Amberes (B), El Havre (C).Los planes de producción del tercer trimestre (julio-septiembre) ya han sido formulados. Los requerimientos (La demanda en destinos) de motores diesel E-4 son las siguientes:

PLANTA CANTIDAD DE MOTORES

(1) LEIPZIG 400

(2) NANCY 900

(3) LIEJA 200

(4) TILBURGO 500

2000

37

La cantidad disponible de máquinas E-4 en los puertos (la oferta en orígenes) a tiempo para usarse en el tercer trimestre, se muestra enseguida:

PUERTO CANTIDAD D’ MOTORES

(A) AMSTERDAM 500

(B) AMBERES 700

(C) EL HAVRE 800

2000

PROTRAC debe decidir cuántas máquinas enviará de cada puerto a cada planta. Las máquinas se envían a través de los transportes comunes y se paga un cargo por máquina. Los costos pertinentes se muestran enseguida.

Costo del transporte de un motor desde un origen hasta un destino.

DESDE ÉL AL DESTINO

ORIGEN 1 2 3 4

A 12 13 4 6

B 6 4 10 11

C 10 9 12 4

Amsterdam (A) . . Tilburgo (4)

. Leipzig (1) Amberes (B) .

. Lieja (3)

38

.El Havre (C)

. Nancy (2)

Las variables de decisión son:Xij = Número de motores enviados del puerto i a la planta j.i = A, B, Cj = 1, 2, 3, 4

El objetivo. 12XA1 + 13XA2 + ........ + 4XC4

El problema tiene dos tipos de restricciones:

1.- El número de artículos embarcados desde un puerto no puede exceder el número disponible. Por ejemplo,

XA1 + XA2 + XA3 + XA4

Es el número total de motores embarcados desde A. Puesto que sólo hay 500 motores disponibles en A, la restricción es

XA1 + XA2 + XA3 + XA4 < 500

Se requiere una restricción similar para cada origen

2.- Debe ser satisfecha la demanda de cada planta. Por ejemplo,

XA1 + XB1 + XC1

Es el número total de motores enviados a la planta 1. Puesto que la demanda

de la planta 1 es de 400 motores, la restricción será

XA1 + XB1 + XC1 = 400

Se requiere una restricción similar para cada planta.

MIN 12XA1 + 13XA2 + 4XA3 + 6XA4 + 6XB1 + 4XB2 + 10XB3 + 11XB4 + 10XC1 +

9XC2 + 12XC3 + 4XC4

Sujeto a 1) XA1 + XA2 + XA3 + XA4 < 5002) XB1 + XB2 + XB3 + XB4 < 700

39

3) XC1 + XC2 + XC3 + XC4 < 800 4) XA1 + XB1 + XC1 = 400 5) XA2 + XB2 + XC2 = 900

6) XA3 + XB3 + XC3 = 2007) XA4 + XB4 + XC4 = 500

Valor de la función objetivo = 12 000

SOLUCIÓN DEL PROBLEMA DE TRANSPORTE

REGLA DE LA ESQUINA NOROESTE

1. Comience en la esquina superior izquierda (origen A, destino 1) y asigne a esa celdilla tantas unidades como sea posible. Esto es, use toda la oferta del origen A que se pueda, para satisfacer la demanda del destino 1. Esto significa que la cantidad asignada será el mínimo entre la oferta en A y la demanda en 1.

2. Reduzca la oferta actual disponible del origen y la demanda actual insatisfecha del destino en la cantidad asignada.

3. Identifique el primer origen con oferta disponible. Este es o bien el origen actual o el que está directamente abajo.

4. Identifique el primer destino con demanda insatisfecha. Este es o bien el destino actual o el que está inmediatamente a la derecha de él.

5. Asigne, como en el paso 1, tantos artículos como sea posible a la ruta asociada con la combinación de origen-destino identificados en los pasos 3 y 4.

6. Regrese al paso 2.

1

40

ORIGE 1 2 3 4 OFERTA

12 13 4 6

A 400 100 500 100

0

6 4 10 11 B

700 700 0

10 9 12 4 800 700

C 100 200 500 500 0

DEMANDA 400 900 200 500 0 0 0 0

Función objetivo Z = 12XA1 + 13XA2 + 4XB2 + 9XC2 + 12XC3 + 4XC4 Z = 12(400) + 13(100) + 4(700) + 9(100) + 12(200) + 4(500) Z = 14200.00

MÉTODO DE APROXIMACIÓN DE VOGEL

1. Para cada renglón con una oferta disponible y cada columna con una demanda insatisfecha, calcule un costo de penalidad restando el dato menor del que le sigue en valor.

2. Identifique el renglón o columna que tengan el mayor costo de penalidad.

(Los empates se resuelven arbitrariamente).3. Asigne la máxima cantidad posible a la ruta disponible que tenga el

costo más bajo en el renglón o columna elegido en el paso 2.4. Reduzca la oferta y la demanda adecuados en la cantidad asignada

en el paso tres.5. Descarte cualquier renglones con oferta disponible cero y columnas

con demanda insatisfecha cero, para consideraciones posteriores.

6. Regrese al paso uno.

Penalidades de renglones y columnas.

Mínimo del Segundo mínimo del renglón A renglón A

Origen 1 2 3 4 0fertaPenalidadesde renglón

A12 13 4 6 500 2

B6 4 10 11 700 2

C10 9 12 4 800 5

Demanda 400 900 200 500

Penalidadesde columna

4 5 6 2

Penalidad máxima Calculado como 6-4

41

Costo total según el método por aproximación de Vogel.

RutaCantidad de

motoresCosto ($)por motor Costo ($)

A3

A4

B2

C1

C2

C4

200300700400200200

4641094

8001800280040001800 800

Costo total $12,000

PROBLEMA 1Una compañía construye una planta maestra para la producción de un articulo en un periodo de cuatro meses. Las demandas en los cuatro meses son 100, 200, 180 y 300 unidades respectivamente. El costo de producción variable por unidad en un mes cualquiera es de cuatro pesos. Una unidad producida para consumo posterior incurrirá en un costo de almacenamiento a razón de 50 centavos por unidad por mes. Por otra parte, los artículos ordenados en meses anteriores incurren en un costo de penalización de 2 pesos por unidad y por mes. La capacidad de producción para elaborar el producto varia cada mes. Los cálculos de los cuatro meses siguientes son 50, 180, 280 y 270 unidades respectivamente.El objetivo es el de formular el plan de inventario de producción al costo mínimo.

Origen 1 2 3 4 0ferta

A12 13

2004

3006

500 3000

B6

7004 10 11

7000

C400

10

200

9 12

200

4800 600

0

Demanda 4000

900 2000

2000

500 2000

42

DestinosOrigen 1 2 3 4 Capacidad

1 4 4.5 5 5.5 502 6 4 4.5 5 1803 8 6 4 4.5 2804 10 8 6 4 270

Demanda 100 200 180 300

Costo total según el método por aproximación de Vogel.

Costo total según el método por aproximación de Vogel.

RutaCantidad de

UnidadesCosto

por unidad Costo ($)A1

B1

B2

C2

C3

C4

50 50130 70180 30

46464

4.5

200300520420720135

Origen 1 2 3 4 Capacidad

A

B

C

D

4 4.5 5 5.5500 50

50

6

130

4 4.5 5180 130

0

8 70

6

180

4

30

4.5280 210

30 0

10 8 6

270

4270 0

Demanda 100 500

200 700

1800

300 0

.5

.5 .5

.5

.5 .5

.5 .5 .5

2 2 2 2 2

2 .5 .5 .52 2 .5 .5

2 ,5 .52 2 .5

2 .5

43

D4 270 4 1080 Costo total $3,375

ADMINISTRACIÓN DE PROYECTOS (PERT Y CPM)

Los proyectos modernos, arrancan desde la construcción de un centro comercial suburbano hasta poner un hombre en la luna; son impresionantes grandes, complejos y costosos. Completar dichos proyectos a tiempo, y dentro del presupuesto, no es tarea fácil. En particular, veremos que los problemas complicados surgen al programar dichos proyectos con frecuencia dichos, son estructurados mediante la interdependencia de las actividades. Normalmente, algunas de las actividades no pueden realizarse antes de que se hayan terminado otras.

Algunas de las preguntas que se contestarán con estos métodos son las siguientes:

1. ¿Cuál es la fecha de terminación del proyecto?2. ¿Cuál es la variabilidad probable de ese dato?3. ¿Cuáles son las fechas programadas del principio y terminación de

cada actividad especifica?4. ¿Cuáles actividades son críticas en el sentido de que deban terminar

con exactitud como fueron programadas para llegar a la meta de la terminación del proyecto total?

5. ¿Cuánto se pueden demorar las actividades no criticas, antes de provocar un retraso en la fecha de conclusión del proyecto total?

6. ¿Cómo puedo concentrar en forma efectiva los recursos y actividades, con el objeto de acelerar la terminación del proyecto?

7. ¿Qué controles se deben ejercer en el flujo de recursos financieros para las diversas actividades durante el proyecto, para poder apegarse al proyecto total?

PERT: Program Evaluation Review Technique (Técnica de revisión y evaluación de programas).CPM: Critical Path Method (Método de la ruta crítica).

44

PERT

Fue desarrollado, a fines de la década de 1950 por la Navy Special Proyects Office. En colaboración con la empresa de consultoría administrativa de Booz, Allen y Hamilton. La técnica recibió una considerable publicidad, favorable para su uso, en el programa de ingeniería y desarrollo del misil Polaris, un complicado proyecto que tenía 250 contratistas primarios y 9000 sub. contratistas. Desde esa fecha, ha sido ampliamente recibido en otras ramas del gobierno y de la industria y se ha aplicado en proyectos tan diferentes como la construcción de fábricas, edificios y carreteras, investigación administrativa, desarrollo de productos, instalación de nuevos sistemas de computadoras, etc.

CPM

Fue desarrollado en 1957, por J.E. Kelly, de Remingtón Rand, y M.R. Walker, de Dupont. Se diferencia del PERT en principio por los detalles de como se manejan el tiempo y el costo. En realidad, las diferencias entre PERT y CPM en la instrumentación efectiva se han ido borrando en cuanto las empresas han integrado las mejores características de ambos sistemas en sus esfuerzos propios por manejas con eficacia sus proyectos.

Por lo general se emplea el CPM. en los proyectos, en donde se ha tenido más experiencia y los tiempos de cada actividad ya están bastante definidos.

El método PERT se emplea en aquellos proyectos, en donde no se conoce con certeza la duración de cada actividad y por lo tanto hay que hacer una estimación con cierto nivel de seguridad.

MÉTODO DE LA RUTA CRITICA (CPM)

Es necesario definir algunos términos antes de desarrollar una red.

Actividad. Es la parte individual de trabajo, que hay que efectuar en un proyecto. Es un trabajo único con una duración determinada. La actividad se representa por medio de una flecha.

Evento. Es el punto de partida de una actividad y sucede solo cuando todas las actividades que le preceden han llegado a su término.

45

Red. Es el conjunto de actividades y eventos que reflejan, de una manera fiel el proyecto.

Actividad virtual. Es una actividad que dura un tiempo igual a cero. Como cada actividad debe estar precedida por un evento y debe concluir con otro evento, a veces es necesario usar una actividad virtual para satisfacer la regla anterior. Esta actividad se indica mediante una flecha punteada.

Tiempos libre u holgura. Es el tiempo que existe entre el final de una actividad y el principio de la siguiente.

Ruta Critica. Es la secuencia de actividades y de eventos en donde el tiempo libre es mínimo. La duración de la ruta critica es el tiempo mínimo requerido para terminar el proyecto.

EJERCICIO 1

Las actividades implicadas en un servicio coral vespertino se dan en la tabla siguiente. Elabore el modelo de la red y realice los cálculos de ruta crítica.

No.

Actividad Actividad antecesor

a

Duración (días)

A Selección de la música -- 21B Aprendizaje de la música A 14C Elaboración de copias y compra de libros A 14D Pruebas B,C 3E Ensayos D 70

46

F Ensayos individuales D 70G Renta de candelabros D 14H Compra de velas G 1I Instalación y decoración de candelabros H 1J Compra de artículos decorativos D 1K Instalación de artículos decorativos J 1L Solicitud de estolas para el coro D 7M Planchado de estolas L 7N Revisión del sistema de sonido D 7O Selección de pistas musicales N 14P Instalación del sistema de sonido O 1

Q Ensayo final E,F.P 1R Grupo de coro Q,I,K 1S Programa final M,R 1

ELABORACIÓN DE LA RUTA CRÍTICA

94 59 108 60 N 14 O 1 P 45 94 49 59 108 49 60 109

45 109 49 0

49 7 108 1 0 109 60 B 0 0 E Q 109 1 38 108 0 35 38 3 108 108 1 0 108 109 109 35 70 14 3 8

24 35 7 38 109 110 O 0 21 A D 39 108 F I 110 54 R 21 70 0

0 21 21 38 38 1 108 109 54 110 56 110 110 21 38 94 54 40 110

9 1 14 0 0 7 0 56 1 56

8 35 109

47

C 35 3 14 52 G 108 1 53 H 70 0

35 35 59 70 52 108 56 53 1097

1 39 J 109 1 40 K 110

70 39 109 70 40 110 45 L 104 7 52 M 111 0 52 S 111 1

45 104 52 111 111 11159 59 0

(A, B, D, E, Q, R, S) = 111 días (A, B, D, F, Q, R, S) = 111 días(A, C, D, E, Q, R, S) = 111 días(A, C, D, F, Q, R, S) = 111 días

BIBLIOGRAFÍA

1. INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONESFrederick S. Hillier, Gerald J. LiebermanMc Graw Hill

2. INVESTIGACION DE OPERACIONES.Hamdy A. TahaAlfa Omega

3. INVESTIGACIÓN DE OPERACIONES EN LA CIENCIA ADMINISTRATIVA Eppen, Gould y SchmidtPrentice Hall

4. INVESTIGACIÓN DE OPERACIONESMoskowitz y Wright

Prentice-hall

48

49