2

2. INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL 2.1. Introducción. Muchas personas clasifican el desarrollo de la Programación Lineal (PL) entre los avances científicos más importantes de mediados del siglo XX. En la actualidad es una herramienta común que ha ahorrado miles o millones de dólares a muchas compañías y negocios, incluyendo industrias medianas en distintos países del mundo. ¿Cuál es la naturaleza de esta notable herramienta y qué tipo de problemas puede manejar?Expresado brevemente, el tipo más común de aplicación abarca el problema general de asignar recursos limitados entre actividades competitivas de la mejor manera posible (es decir, en forma óptima). Este problema de asignación puede surgir cuando deba elegirse el nivel de ciertas actividades que compiten por recursos escasos para realizarlas. La variedad de situaciones a las que se puede aplicar esta descripción es sin duda muy grande, y va desde la asignación de instalaciones productivas a los productos, hasta la asignación de los recursos nacionales a las necesidades de un país; desde la planeación agrícola, hasta el diseño de una terapia de radiación; etc. No obstante, el ingrediente común de todas estas situaciones es la necesidad de asignar recursos a las actividades. Con frecuencia, seleccionar una alternativa incluye satisfacer varios criterios al mismo tiempo. Por ejemplo, cuando se compra una pieza de pan se tiene el criterio de frescura, tamaño, tipo (blanco, integral u otro), costo y rebanado o sin rebanar. Se puede ir un paso más adelante y dividir estos criterios en dos categorías: restricciones y el objetivo. Las restricciones son las condiciones que debe satisfacer una solución que está bajo consideración. Si más de una alternativa satisfacen todas las restricciones, el objetivo se usa para seleccionar entre todas las alternativas factibles. Cuando se elige una pieza de pan, pueden quererse 100 gr. de pan blanco rebanado y hecho no antes de ayer. Si varias marcas satisfacen estas restricciones, puede aplicarse el objetivo de un costo mínimo y escoger las más barata. Existen muchos problemas administrativos que se ajustan a este molde de tratar de minimizar o maximizar un objetivo que está sujeto a una lista de restricciones. un corredor de inversiones, por ejemplo, trata de maximizar el rendimiento sobre los fondos invertidos pero las posibles inversiones están restringidas por las leyes y las políticas bancarias. Un hospital debe planear que las comidas para los pacientes satisfagan ciertas restricciones sobre sabor, propiedades nutritivas, tipo y variedad, al mismo tiempo que se trata de minimizar el costo. Un fabricante, al planear la producción futura, busca un costo mínimo al mismo tiempo cómo cumplir restricciones sobre la demanda del producto, la capacidad de producción, los inventarios, el nivel de empleados y la tecnología. La PL se ha aplicado con éxito a estos y otros problemas. La PL es una técnica determinista, no incluye probabilidades y utiliza un modelo matemático para describir el problema. El adjetivo lineal significa que todas las funciones matemáticas del modelo deben ser funciones lineales. En este caso, la palabra programación no se refiere a programación en computadoras; en esencia es un sinónimo de planeación. Así, la PL trata la planeación de las actividades para obtener un resultado óptimo, esto es, el resultado que mejor alcance la meta especificada (según el modelo) entre todas las opciones de solución. Aunque la asignación de recursos a las actividades es la aplicación más frecuente, la PL tiene muchas otras posibilidades. De hecho, cualquier

problema cuyo modelo matemático se ajuste al formato general del modelo de PL es un problema de PL. Supuestos de la programación lineal. Existe un número de suposiciones realizadas en cada modelo. La utilidad de un modelo está directamente relacionada con la realidad de los supuestos. El primer supuesto tiene que ver con la forma lineal de las funciones. Ya que el objetivo es lineal, la contribución al objetivo de cualquier decisión es proporcional al valor de la variable de decisión. Producir dos veces más de producto producirá dos veces más de ganacia, contratando el doble de páginas en las revistas doblará el costo relacionado con las revistas. Es una Suposición de Proporción. Además, la contribución de una variable a la función objetivo es independiente de los valores de las otras variables. La ganancia con una computadora Notebook es de $10,750.00, independientemente de cuantas computadoras Desktop se producen. Este es un Supuesto de Adición. Análogamente, ya que cada restricción es lineal, la contribución de cada variable al lado izquierdo de cada restricción es proporcional al valor de la variable e independiente de los valores de cualquier ora variable. Estas suposiciones son bastante restrictivas. Veremos, sin embargo, que ser claros y precisos en la formulación del modelo puede ayudar a manejar situaciones que parecen en un comienzo como lejanos a estos supuestos. El siguiente supuesto es la Suposición de ser Divisible. Es posible tomar una fracción de cualquier variable. Por ejemplo, en un problema de marketing, qué significa comprar 2.67 avisos en la televisión?. Es posible que la suposición de ser divisible sea insatisfecha en este ejemplo. O puede ser que tales unidades de 2.67 avisos correspondan a 2,666.7 minutos de avisos, en cuyo caso redondeando la solución serían 2,667 minutos con una mínima duda que esté cercana a la solución óptima. Si la suposición de divisible no es válida, entonces se usará la técnica de Programación Lineal Entera. La última suposición es el Supuesto de Certeza. La Programación Lineal no permite incertidumbre en los valores. Será difícil que un problema cumpla con todas las suposiciones de manera exacta. Pero esto no negará la factibilidad de uso del modelo. Un modelo puede ser aún útil aunque difiera de la realidad, si se es consistente con los requerimientos más estrictos dentro del modelo y se tiene claras sus limitaciones al interpretar los resultados. Existen limitaciones prácticas para el uso de la PL. Una se relaciona con los cálculos. En general se necesita una computadora. Desafortunadamente, las calculadoras, aun las programables, son poco útiles, puesto que la PL tiene necesidad de gran cantidad de memoria o almacenamiento. Si no se tiene acceso a una computadora, se estará limitado a problemas muy sencillos. La otra limitación se refiere al costo de formular un problema de PL. En teoría, podría usarse PL, por ejemplo, para hacer las compras semanales de abarrotes. Sin embargo, sería necesario conocer todas las compras posibles que pueden realizarse (éstas serían las variables), además de cada restricción como sabor, número de comidas, vitaminas y proteínas. Es obvio que el costo de obtener todos estos datos excede

lo que se podría ahorrar si se hicieran las compras óptimas. Antes de emprender una aplicación de PL, debe considerarse la disponibilidad y el costo de los datos necesarios. 2.2. Formulación de modelos de Programación Lineal. Aunque se ponga en duda, la parte más difícil de PL es reconocer cuándo ésta puede aplicarse y formular el problema matemáticamente. Una vez hecha esa parte, resolver el problema casi siempre es fácil. Para formular un problema en forma matemática, deben expresarse afirmaciones lógicas en términos matemáticos. Esto se realiza cuando se resuelven “problemas hablados” al estudiar un curso de álgebra. Algo muy parecido sucede aquí al formular las restricciones. Por ejemplo, considérese la siguiente afirmación: A usa 3 horas por unidad y B usa 2 horas por unidad. Si deben usarse todas las 100 horas disponibles, la restricción será:

3A + 2B = 100 Sin embargo, en la mayoría de las situaciones de negocios, no es obligatorio que se usen todos los recursos (en este caso, horas de mano de obra). Más bien la limitación es que se use, cuando mucho, lo que se tiene disponible. Para este caso, la afirmación anterior puede escribirse como una desigualdad:

3A + 2B 100 Para que sea aceptable para PL, cada restricción debe ser una suma de variables con exponente 1. Los cuadrados, las raíces cuadradas, etc. no son aceptables, ni tampoco los productos de variables. Además, la forma estándar para una restricción pone a todas las variables del lado izquierdo y sólo una constante positiva o cero del lado derecho. Esto puede requerir algún reacomodo de los términos. Si, por ejemplo, la restricción es que A debe ser por los menos el doble de B, esto puede escribirse como:

A 2B ó A 2B 0 Nótese que pueden moverse términos de un lado a otro de las desigualdades como si fuera un signo de igualdad. Pero al multiplicar una desigualdad por 1, el sentido de esta desigualdad se invierte. Puede ser necesario hacer esto para que los coeficientes del lado derecho sean positivos. Por ejemplo, si se quiere que A sea por lo menos tan grande como B 2, entonces:

A B 2ó A B 2

por último B A 2 Una nota final sobre desigualdades: es sencillo convertir una desigualdad en una ecuación. Todo lo que se tiene que hacer es agregar (o restar) una variable extra. Por ejemplo:

B A 2 es lo mismo que B A + S = 2

en donde S representa la diferencia, o la holgura, entre B A y 2. S se llama variable de holgura. Por otro lado, se restaría una variable de superávit en el caso siguiente:

A 2B 0 es lo mismo que A 2B S = 0 Algunos métodos de solución (como el Método Símplex) y la mayoría de los programas de computadora (como el MathProg, que viene en el OR Courseware, que acompaña al libro “Introducción a la Investigación de Operaciones” de los autores Hillier y Lieberman) requieren que todas las desigualdades se conviertan en igualdades. La metodología de PL requiere que todas las variables sean positivas o cero, es decir, no negativas. Para la mayoría de los problemas esto es real, no se querría una solución que diga: prodúzcanse menos dos cajas o contrátense menos cuatro personas. Mientras que no existe un límite en el número de restricciones que puede tener un problema de PL, sólo puede haber un objetivo. La forma matemática del objetivo se llama función objetivo. Debe llevar consigo el maximizar o minimizar alguna medida numérica. Podría ser maximizar el rendimiento, la ganancia, la contribución marginal o los contactos con los clientes. Podría ser minimizar el costo, el número de empleados o el material de desperdicio. Con frecuencia el objetivo es evidente al observar el problema. Como el valor de la función objetivo no se conoce hasta que se resuelve el problema, se usa la letra Z para representarlo. La función objetivo tendrá, entonces, la forma:

Maximizar Z = 4A + 6Bó

Minimizar Z = 2x1 + 5x2

Se analiza una aplicación para ilustrar el formato de los problemas de Programación Lineal. Planeación de la fuerza de trabajo. El gerente de personal de “La Tortuga Veloz, S.A. de C.V.”, está analizando la necesidad de mano de obra semi calificada durante los próximos seis meses. Se lleva 1 mes adiestrar a una persona nueva. Durante este período de entrenamiento un trabajador regular, junto con uno en adiestramiento (aprendiz), producen el equivalente a lo que producen 1.2 trabajadores regulares. Se paga $500.00 mensuales a quien está en entrenamiento, mientras que los trabajadores regulares ganan $800.00 mensuales. La rotación de personal entre los trabajadores regulares es bastante alta, del 10% mensual. El gerente de personal debe decidir cuántas personas necesita contratar cada mes para adiestramiento. En seguida se da el número de meses-hombre necesarios. También se desea tener una fuerza de trabajo regular de 110 al principio de julio. En cuanto al 1º de enero, hay 58 empleados regulares.

Mes Meses-hombre requeridos Mes Meses-hombre requeridosEnero 60 Abril 80Febrero 50 Mayo 70Marzo 60 Junio 100

Este problema tiene un aspecto dinámico, ya que la fuerza de trabajo en cualquier mes depende de la fuerza de trabajo regular y en adiestramiento del mes anterior. Para cualquier mes, el número total de meses-hombre disponibles se puede expresar como sigue:

Meses-hombre disponibles: Ri + 0.2Ai

en donde: Ri = número de trabajadores regulares al principio del mes Ai = número de aprendices contratados en el mes. Entonces los requerimientos de cada mes pueden expresarse por las restricciones:

enero R1 + 0.2A1 60febrero R2 + 0.2A2 50marzo R3 + 0.2A3 60abril R4 + 0.2A4 80mayo R5 + 0.2A5 70junio R6 + 0.2A6 100julio (principio) R7 110

Debido a la rotación, el 10% de los trabajadores regulares se van cada mes. Así, el número de trabajadores regulares disponibles, por ejemplo, al principio de febrero sería:

R2 = 0.9R1 + A1

En la misma forma, pueden escribirse las ecuaciones para el número de trabajadores disponibles al principio de cada mes:

enero R1 = 58 (dado)febrero R2 = 0.9R1 + A1

marzo R3 = 0.9R2 + A2

abril R4 = 0.9R3 + A3

mayo R5 = 0.9R4 + A4

junio R6 = 0.9R5 + A5

julio R7 = 0.9R6 + A6

El objetivo global del gerente de personal es minimizar el costo. La función objetivo es:

Minimizar: Z = 800(R1 + R2 + R3 + R4 + R5 + R6) + 500(A1 + A2 + A3 + A4 + A5 + A6)

Ahora se tiene el problema en el formato general de PL con 13 variables y 14 restricciones. Los tomadores de decisiones en las empresas establecen criterios que debe cumplir una solución y, después, buscan esa solución. En PL, los criterios se expresan como restricciones. Se exploran las soluciones posibles y se usa la función objetivo para elegir la mejor de entre aquellas que cumplen con los criterios. La PL se denomina técnica de optimización, pero optimiza sólo dentro de los límites de las restricciones. En realidad es un método de satisfacción de criterios. Forma estándar de los modelos de Programación Lineal. Supóngase que existe cualquier número (digamos m) de recursos limitados de cualquier tipo, que se pueden asignar entre cualquier número (digamos n) de actividades competitivas de cualquier clase. Etiquétense los recursos con números (1, 2, ..., m) al igual que las actividades (1, 2, ..., n). Sea xj (una variable de decisión) el nivel de la actividad j, para j = 1, 2, ..., n, y sea Z la medida de efectividad global seleccionada. Sea c j el incremento que resulta en Z por cada incremento unitario en xj (para j = 1, 2, ..., n). Ahora sea bi la cantidad disponible del recurso i (para i = 1, 2, ..., m). Por último defínase aij como la cantidad de recurso i que consume cada unidad de la actividad j (para i = 1, 2, ..., m y j = 1, 2, ..., n). Se puede formular el modelo matemático para el problema general de asignar recursos a actividades. En particular, este modelo consiste en elegir valores de x1, x2, ..., xn para:

Maximizar Z = c1x1 + c2x2 + ... + cnxn,sujeto a las restricciones:

a11x1 + a12x2 + ... + a1nxn b1

a21x1 + a22x2 + ... + a2nxn b2

am1x1 + am2x2 + ... + amnxn bm

yx1 0, x2 0, ..., xn 0

Ésta se llamará nuestra forma estándar (porque algunos libros de texto adoptan otras formas) para el problema de PL. Cualquier situación cuya formulación matemática se ajuste a este modelo es un problema de PL. En este momento se puede resumir la terminología que usaremos para los modelos de PL. La función que se desea maximizar, c1x1 + c2x2 + ... + cnxn, se llama función objetivo. Por lo general, se hace referencia a las limitaciones como restricciones. Las primeras m restricciones (aquellas con una función del tipo a i1x1 + ai2x2 + ... + ainxn, que representa el consumo total del recurso i) reciben el nombre de restricciones funcionales. De manera parecida, las restricciones xj 0 se llaman restricciones de no negatividad. Las variables xj son las variables de decisión. Las constantes de entrada, aij, bi, cj, reciben el nombre de parámetros del modelo. Otras formas de modelos de Programación Lineal.

Es conveniente agregar que el modelo anterior no se ajusta a la forma natural de algunos problemas de programación lineal. Las otras formas legítimas son las siguientes: 1. Minimizar en lugar de maximizar la función objetivo:

Minimizar Z = c1x1 + c2x2 + ... + cnxn, 2. Algunas restricciones funcionales con desigualdad en el sentido mayor o igual:

ai1x1 + ai2x2 + ... + ainxn, bi, para algunos valores de i, 3. Algunas restricciones funcionales en forma de ecuación:

ai1x1 + ai2x2 + ... + ainxn, = bi, para algunos valores de i,

4. Las variables de decisión sin la restricción de no negatividad:

xj no restringida en signo para algunos valores de j. Cualquier problema que incluya una, varias o todas estas formas del modelo anterior también se clasifica como un problema de PL, siempre y cuando éstas sean las únicas formas nuevas introducidas. Puede ser que la interpretación que se ha dado de asignación de recursos limitados entre actividades que compiten no se aplique, pero independientemente de la interpretación o el contexto, lo único que se necesita es que la formulación matemática del problema se ajuste a las formas permitidas. Se verá que estas otras cuatro formas legales se pueden reescribir en una forma equivalente para que se ajuste al modelo que se presentó. Entonces, todo problema de PL se puede poner en nuestra forma estándar si se desea. 2.3. Solución Gráfica de Modelos Lineales con dos Variables. Para la solución gráfica de programas lineales con dos variables, lo que se tiene que hacer es trazar un eje de coordenadas cartesianas, para graficar las desigualdades dadas por el problema, después encontrar el Área de Soluciones Factibles y proceder a graficar la función objetivo para conocer el valor óptimo (maximizar o minimizar) que será la solución del problema. Ejemplo: Problema de mezcla de productos.Un fabricante está tratando de decidir sobre las cantidades de producción para dos artículos: mesas y sillas. Se cuenta con 96 unidades de material y con 72 horas de mano de obra. Cada mesa requiere 12 unidades de material y 6 horas de mano de obra. Por otra parte, las sillas usan 8 unidades de material cada una y requieren 12 horas de mano de obra por silla. El margen de contribución es el mismo para las mesas que para las sillas: $5.00 por unidad. El fabricante prometió construir por lo menos dos mesas. Paso 1: formulación del problema.

El primer paso para resolver el problema es expresarlo en términos matemáticos en el formato general de PL. ¿Cuál es el objetivo? Es maximizar la contribución a la ganancia. Cada unidad de mesas o sillas producidas contribuirá con $5 en la ganancia. Así las dos alternativas son la producción de mesas y la producción de sillas. Ahora puede escribirse la función objetivo:

Maximizar Z = 5x1 + 5x2

en donde: x1 = número de mesas producidas x2 = número de sillas producidas ¿Cuáles son las restricciones o limitaciones del problema? Existen tres restricciones. Primero, el material está limitado a 96 unidades. Cada mesa se lleva 12 unidades de material y cada silla usa 8 unidades. La primera restricción es, entonces:

12x1 + 8x2 96 La segunda restricción es el total de horas de mano de obra. Una mesa se lleva 6 horas, una silla 12 horas y se dispone de un total de 72 horas. Así:

6x1 + 12x2 72 Existe una limitación más. El fabricante prometió producir por lo menos dos mesas. Esto puede expresarse como:

x1 2 Por último, las restricciones de no negatividad son:

x1 0, x2 0 Poniendo todo junto el modelo se tiene: Maximizar Z = 5x1 + 5x2

Restricciones: 12x1 + 8x2 96 6x1 + 12x2 72 x1 2 x1 0, x2 0 Paso 2: gráfica de las restricciones.El siguiente paso en el método gráfico es dibujar todas las restricciones en una gráfica. Esto puede hacerse en cualquier orden. Por conveniencia se comenzará con las restricciones de no negatividad. Éstas se muestran en la siguiente figura:

En esta gráfica, una solución se representaría por un punto con coordenadas x1 (mesas) y x2 (sillas). Las coordenadas representarían las cantidades de cada artículo que se deben producir. El cuadrante superior derecho se llama Región Factible puesto que es el único cuadrante en que pueden estar las soluciones. Los otros tres cuadrantes no son factibles, ya que requerirían la producción de cantidades negativas de mesas o de sillas o de ambas. La siguiente restricción es x1 2. La manera más sencilla de dibujar las restricciones de recursos es en dos pasos: (1) convertir una desigualdad en una ecuación y graficar la ecuación y (2) sombrear el área apropiada arriba y abajo de la línea que resulta en el paso 1. Convertir una igualdad en una ecuación aquí significa ignorar la parte de “mayor que” o “menor que” de la restricción. Así, en el ejemplo, x1 2 se convierte en x1 = 2. Esta ecuación está trazada en la siguiente figura:

Cualquier punto en la línea x1 = 2 satisface la ecuación. Sin embargo, la restricción es más amplia, ya que cualquier punto x1 > 2 también la cumplirá. Esto incluye todos los puntos que están a la derecha de la línea x1 = 2. Entonces, la región factible incluye todos los valores de x1 que están sobre o a la derecha de la línea x1 = 2. La limitación sobre las horas de mano de obra es la siguiente restricción. Como antes, primero se convierte en una ecuación: 6x1 + 12x2 = 72. Puede graficarse esta línea si se encuentran dos puntos sobre ella. El par de puntos más sencillos de localizar son las intersecciones con los ejes X1 y X2. Para encontrar la intersección con el eje X2 se hace x1 = 0. La ecuación se reduce, entonces, a:

12x2 = 72 x2 = 6

La intersección con el eje X1 se encuentra haciendo x2 = 0. Así:

6x1 = 72 x1 = 12

Estos dos puntos y la línea que los une se muestran en la siguiente figura:

Cualquier punto que está sobre o abajo de esta línea cumplirá con la restricción. Cualquier punto arriba de esta línea requerirá más de 72 horas de mano de obra y no es aceptable. En la siguiente figura se combina esta restricción con la anterior. En la región factible, ambas restricciones se cumplen.

La última restricción es la de material. Siguiendo el procedimiento anterior, primero se encuentran las intersecciones para la igualdad. Éstas son x1 = 0, x2 = 12 y x1 = 8, x2 =0. Se localizan los dos puntos en la gráfica; se traza la línea, y como la restricción es del tipo menor o igual que, se sombrea el área que está abajo de la línea. El resultado se muestra en la siguiente figura:

Cualquier solución que esté en la frontera o dentro del área sombreada cumplirá con todas las restricciones. Ahora se utilizará la función objetivo para seleccionar la solución óptima. Paso 3: obtención de la solución óptima: líneas de indiferencia.Para encontrar la solución óptima, se grafica la función objetivo en la misma gráfica de las restricciones. La función objetivo en este problema es Z = 5x1 + 5x2. Como todavía no se conoce el máximo valor factible de Z, no puede trazarse el óptimo de la función objetivo. No obstante, es posible suponer algunos valores para Z y graficar las líneas resultantes. En la siguiente figura se muestran las líneas para Z = 25 yZ = 50:

Las líneas de este tipo se llaman líneas de indiferencia, porque cualquier punto sobre una línea dada da la misma ganancia total. Nótese que la distancia perpendicular del origen a la línea aumenta al aumentar el valor de Z. También, todas las líneas de indiferencia son paralelas entre sí. Estas propiedades gráficas pueden usarse para resolver el problema. En la siguiente figura, se ilustran todas las restricciones y las dos líneas de indiferencia supuestas. En la gráfica puede observarse que la línea de indiferencia para Z = 50 está completamente fuera de la región factible. Para Z = 25, parte de la línea cae dentro de la región factible. Por tanto, existe alguna combinación de x1 y x2 que satisface todas las restricciones y da una ganancia total de $25. Por inspección, puede observarse que hay ganancias más altas que son factibles.

Imaginando que la línea de indiferencia Z = 25 se mueve hacia la línea Z = 50, de las propiedades de la gráfica que se hicieron notar antes, el punto óptimo estará sobre la línea de indiferencia más lejana al origen pero que todavía toque la región factible. Esto se muestra en la siguiente figura:

Con el punto óptimo localizado gráficamente, la única tarea que queda es encontrar las coordenadas del punto. Nótese que el punto óptimo está en la intersección de las líneas de restricción para materiales y horas de mano de obra. Las coordenadas de este punto se pueden encontrar resolviendo el sistema de ecuaciones que forman estas dos restricciones utilizando cualquiera de los métodos de solución (suma y resta, sustitución o igualación). Las coordenadas de este punto resultan ser (6, 3). La sustitución de este punto en la función objetivo da la ganancia máxima:

Z = 5(6) + 5(3) = $45 Resumen del método gráfico.Para resolver gráficamente problemas de programación lineal:1. Exprésense los datos del problema como una función objetivo y restricciones.2. Grafíquese cada restricción.3. Localícese la solución óptima. Uso del método gráfico para minimización. Consideremos un Problema de PL en el cual el objetivo es minimizar costos. La solución del problema de minimización sigue el mismo procedimiento que la de problemas de maximización. La única diferencia es que ahora se quiere el menor valor posible para la función objetivo. Supóngase que se tiene el siguiente problema: Ejemplo: Problema de dieta. Un comprador está tratando de seleccionar la combinación más barata de dos alimentos, que debe cumplir con ciertas necesidades diarias de vitaminas. Los requerimientos vitamínicos son por lo menos 40 unidades de vitamina W, 50 unidades de vitamina X y 49 unidades de vitamina Y. Cada onza del alimento A proporciona 4 unidades de vitamina W, 10 unidades de vitamina X y 7 unidades de vitamina Y; cada onza del alimento B proporciona 10 unidades de W, 5 unidades de X y 7 unidades de Y. El alimento A cuesta 5 pesos/kilogramo y el alimento B cuesta 8 pesos/kilogramo.

Paso 1: formulación del problema.La meta en este problema es encontrar la manera menos costosa para satisfacer las necesidades vitamínicas. Las dos alternativas disponibles son los alimentos A y B. Matemáticamente la función objetivo es:

Minimizar Z = 5A + 8B Las restricciones son los requerimientos mínimos de las tres vitaminas. Éstas se muestran enseguida:

Restricciones: 4A + 10B 40 vitamina W 10A + 5B 50 vitamina X 7A + 7B 49 vitamina Y A 0, B 0 no negatividad Paso 2: gráfica de las restricciones.El procedimiento para graficar es el mismo que se usó antes: (1) graficar cada ecuación de restricción; (2) graficar el área apropiada. Para la primera restricción la ecuación es 4A + 10B = 40. Las dos intersecciones con los ejes son (0,4) y (10,0). Esta línea se muestra en la siguiente figura:

La restricción pide 40 unidades o más de la vitamina W. Cualquier punto que esté arriba de la línea de restricción será factible y todos los puntos que quedan abajo de esa línea serán aceptables. En la siguiente figura se muestra la región factible:

Después se grafica la restricción para la vitamina X. La ecuación 10A + 5B = 50 tiene intersecciones con los ejes en (0,10) y (5,0). En la siguiente figura se ilustran las restricciones para las vitaminas W y X. Nótese que las soluciones que quedan en las áreas a o b no son factibles, ya que quedarían abajo de las líneas de restricción.

Al agregar la tercera restricción, este segundo paso queda terminado, como se muestra en la siguiente figura:

Paso 3: localización de la solución óptima.

En la siguiente figura se muestra la frontera extrema más dos líneas de indiferencia, las de Z = 40 pesos y Z = 60 pesos. La frontera extrema está formada por los puntos a, b, c y d, puesto que éstos son los puntos de intersección factibles más cercanos al origen.

Gráficamente, el objetivo de minimizar el valor de Z significa ajustar una línea de indiferencia tan cerca del origen como sea posible. En la figura anterior puede observarse que existen muchas soluciones posibles para Z = 60, pero ninguna para Z = 40. Imaginando mover la línea Z = 60 hacia el origen, el último punto de contacto con la frontera extrema será el punto b. Entonces, el punto b es la solución óptima. En la figura anterior se observa que el punto b es la intersección de dos líneas:

(1) 4A + 10B = 40(2) 7A + 7B = 49

Resolviendo el sistema de ecuaciones: Multiplíquese la ecuación (1) por 7: (3) 28A + 70B = 280Multiplíquese la ecuación (2) por – 4: (4) –28A – 28B = –196

42B = 84 B = 2 Sustitúyase en la ecuación (1): 4A + 10(2) = 40 A = 5

La solución menos costosa es 5 kilogramos de alimento A y 2 kilogramos de alimento B. El costo total de esta combinación es:

Z = 5A + 8B = 5(5) + 8(2) = 25 + 16 = 41 pesosSi se usa el método de prueba y error para localizar la solución óptima, se deben encontrar las coordenadas de los puntos a, b, c, y d. Se debe calcular después el valor de la función objetivo para cada punto. A continuación se muestran los resultados de este procedimiento:

Resultados de prueba y error

Punto Coordenadas Z = 5A + 8B

a A = 10, B = 0 50

b A = 5, B = 2 41 menor

c A =3, B = 4 47

d A = 0, B = 10 80

CASOS ESPECIALES. Múltiples soluciones.

Maximizar Z = 3x1 + 2x2 sujeta a x1 4 x2 12 3x1 + 2x2 18 x1 0

, x2 0

Ninguna solución factible.

Maximizar Z = 3x1 + 2x2 sujeta a 1/40x1 + 1/60x2 1 1/50x1 + 1/50x2 1 x1 30 x2 20 x1 0

, x2 0

Área o Región de Soluciones Factibles no Acotada.

Maximizar Z = 2x1 – x2 sujeta a x1 – x2 1 2x1 + x2 6 x1 0

, x2 0

ASPECTOS BÁSICOS DE LA PROGRAMACIÓN LINEAL

Muchas personas clasifican el desarrollo de la programación lineal entre los avances científicos más importantes de mediados del siglo XX, su impacto desde 1950 ha sido extraordinario. En la actualidad es una herramienta de uso normal que ha ahorrado miles o millones de pesos a muchas compañías o negocios, incluyendo empresas medianas en los distintos países industrializados del mundo; su aplicación a otros sectores de la sociedad se está ampliando con rapidez. Una proporción muy grande de los cálculos científicos en computadoras está dedicada al uso de la programación lineal.

¿Cuál es la naturaleza de esta notable herramienta y qué tipos de problemas puede manejar. Expresado brevemente, el tipo más común de aplicación abarca el problema general de asignarrecursos limitados entre actividades competitivas de la mejor manera posible (es decir, en forma óptima). Con más precisión, este problema incluye elegir el nivel de ciertas actividades que compiten por recursos escasos necesarios para realizarlas. Después, los niveles de actividad elegidos dictan la cantidad de cada recurso que consumirá cada una de ellas. La variedad de situaciones a las que se puede aplicar esta descripción es sin duda muy grande, y va desde la asignación de instalaciones de producción a los productos, hasta la asignación de los recursos nacionales a las necesidades de un país; desde la selección de una cartera de inversiones, hasta la selección de los patrones de envío; desde la planeación agrícola, hasta el diseño de una terapia de radiación, etc. No obstante, el ingrediente común de todas estas situaciones es la necesidad de asignar recursos a las actividades eligiendo los niveles de las mismas.

La programación lineal utiliza un modelo matemático para describir el problema. El adjetivo lineal significa que todas las funciones matemáticas del modelo deber ser funciones lineales. En este caso, las palabra programación no se refiere a programación en computadoras; en esencia es un sinónimo de planeación. Así, la programación lineal trata la planeación de las actividades para obtener un resultado óptimo, esto es, el resultado que mejor alcance la meta especificada (según el modelo matemático) entre todas las alternativas de solución.

Aunque la asignación de recursos a las actividades es la aplicación más frecuente, la programación lineal tiene muchas otras posibilidades. de hecho, cualquier problema cuyo modelo matemático se ajuste al formato general del modelo de programación lineal es un problema de programación lineal. Aún más, se dispone de un procedimiento de solución extraordinariamente eficiente llamado método simplex, para resolver estos problemas, incluso los de gran tamaño. Estas son algunas causas del tremendo auge de la programación lineal en las últimas décadas.

MODELO DE PROGRAMACIÓN LINEAL

Los términos clave son recursos y actividades, en donde m denota el número de distintos tipos de recursos que se pueden usar y n denota el número de actividades bajo consideración. Algunos ejemplos de recursos son dinero y tipos especiales de maquinaria, equipo, vehículos y personal. Los ejemplos de actividades incluyen inversión en proyectos específicos, publicidad en un medio determinado y el envío de bienes de cierta fuente a cierto destino. En cualquier aplicación de programación lineal, puede ser que todas las actividades sean de un tipo general (como cualquiera de los ejemplos), y entonces cada una correspondería en forma individual a las alternativas específicas dentro de esta categoría general.

El tipo más usual de aplicación de programación lineal involucra la asignación de recursos a ciertas actividades. La cantidad disponible de cada recurso está limitada, de forma que deben asignarse con todo cuidado. La determinación de esta asignación incluye elegir los niveles de las actividades que lograrán el mejor valor posible de la medida global de efectividad.

Ciertos símbolos se usan de manera convencional para denotar las distintas componentes de un modelo de programación lineal. Estos símbolos se enumeran a continuación, junto con su interpretación para el problema general de asignación de recursos a actividades.

Z = valor de la medida global de efectividad

xj = nivel de la actividad j (para j = 1,2,...,n)

cj = incremento en Z que resulta al aumentar una unidad en el nivel de la actividad j

bi = cantidad de recurso i disponible para asignar a las actividades (para i = 1,2,...,m)

aij = cantidad del recurso i consumido por cada unidad de la actividad j

El modelo establece el problema en términos de tomar decisiones sobre los niveles de las actividades, por lo que x1,x2,....,xn se llaman variables de decisión. Los valores de cj, bi y aij (para i = 1,2,....,m y j = 1,2,....,n) son las constantes de entrada al modelo. Las cj, bi y aij también se conocen como parámetros del modelo.

FORMA ESTÁNDAR DEL MODELO

Ahora se puede formular al modelo matemático para este problema general de asignación de recursos a actividades. En Datos necesarios para un modelo de programación lineal que maneja la asignación de recursos a actividades particular, este modelo consiste en elegir valores de x1,x2,....,xn para:

optimizar (maximizar o minimizar) Z = c1x1 + c2x2 +....+ cnxn,

sujeta a las restricciones:

a11x1 + a12x2 +....+ a1nxn < b1

a21x1 + a22x2 +....+ a2nxn < b2

.

.

.

am1x1 + am2x2 +....+ amnxn < bm

X1 ³ 0, X2 ³0, ..., Xn ³0.

SUPOSICIONES DEL MODELO DE PROGRAMACIÓN LINEAL

PROPORCIONALIDAD

La contribución de cada actividad al valor de la función objetivo Z es proporcional al nivel de actividad xj, como lo representa el término cjxj en la función objetivo. De manera similar, la contribución de cada actividad al lado izquierdo de cada restricción funcional es proporcional al nivel de la

actividad xj, en la forma en que lo representa el término aijxj en la restricción. En consecuencia, esta suposición elimina cualquier exponente diferente a 1 para las variables en cualquier término de las funciones (ya sea la función objetivo o la función en el lado izquierdo de las restricciones funcionales) en un modelo de programación lineal.

ACTIVIDAD

Establece que la entrada y salida de un recurso en particular al conjunto de actividades, deben ser la misma cantidad; o sea, que las actividades transforman los recursos y no los crean o destruyen. Esta suposición garantiza que la contribución total tanto a la función objetivo como a las restricciones, es igual a la suma de las contribuciones individuales. Cuando en un problema dado no se tenga la aditividad puede recurrirse al empleo de otras técnicas de la programación matemática, dependiendo de cada caso en particular.

ADITIVIDAD

Cada función en un modelo de programación lineal (ya sea la función objetivo o el lado izquierdo de las restricciones funcionales) es la suma de las contribuciones individuales de las actividades respectivas.

DIVISIBILIDAD

Las variables de decisión en un modelo de programación lineal pueden tomar cualquier valor, incluyendo valores no enteros, que satisfagan las restricciones funcionales y de no negatividad. Así, estas variables no están restringidas a sólo valores enteros. Como cada variable de decisión representa el nivel de alguna actividad, se supondrá que las actividades se pueden realizar aniveles fracciónales.

LIMITACIONES DEL MODELO DE PROGRAMACIÓN LINEAL

MODELO DETERMINÍSTICO

El modelo de PL involucra únicamente tres tipos de parámetros: Cj, aij y bi; de ahí su sencillez y gran aplicación. Sin embargo, el valor de dichos parámetros debe ser conocido y constante. Cuando el valor de los parámetros tiene un cierto riesgo o incertidumbre, pude utilizarse la programación paramédica, la programación estocástica, o realizarse un análisis de sensibilidad.

MODELO ESTÁTICO

En algunos modelos matemáticos se han empleado con éxito las ecuaciones diferenciales, para inducir la variable tiempo en ellos. En este sentido, puede decidirse que la PL utiliza un modelo estático, ya que la variable tiempo no se involucra formalmente. Adquiriendo un poco de experiencia en la formulación de modelos de PL, puede imbuirse la temporabilidad mencionada, con el uso de subíndices en las variables.

MODELO QUE NO SUB-OPTIMIZA

Debido a la forma que se plantea el modelo de PL, o encuentra la solución óptima o declara que ésta no existe. Cuando no es posible obtener una solución óptima y se debe obtener alguna, se recurre a otra técnica más avanzada que la PL, la cual se denomina programación lineal por metas.

TAREAS ASIGNADAS PARA ENTREGAR EL 05 DE DICIEMBRE DEL 200 3

VALORACIÓN DE LOS EJERCICIOS:

Problemas del 1 al 10 : 1 puntos por cada problema resuelto




Problemas del 41 al 60: 5 puntos por cada problema resuelto

PROBLEMA #1 Dada la región del plano definida por las inecuaciones:x + y - 1 0 ; 0 x 3 ; 0 y 2.¿Para qué valores de la región es máxima la función Z = 5x + 2y?

PROBLEMA #2 Se considera el recinto plano de la figura en el que están incluidos los tres lados y los tres vértices de las rectas asociadas a las desigualdades

a) Hallar las inecuaciones que definen el recinto.

b) Maximizar la función Z = 3x - 6y sujeta a las restricciones del recinto.

PROBLEMA #3 Se considera la región del primer cuadrante determinada por las inecuaciones:x + y 8 ; x + y 4 ; x + 2y 6a) Dibujar la región del plano que definen, y calcular sus vértices.b) Hallar el punto de esa región en el que la función F(x,y) = 3x + 2y alcanza el valor mínimo y calcular dicho valor.

PROBLEMA #4 a) Representar gráficamente el conjunto de puntos que satisfacen las siguientes inecuaciones lineales:x + 2y 10 ; x + y 2 ;x 8; x 0; y 0b) Hallar el máximo y el mínimo de F(x,y) = x - 3y, sujeto a las restricciones representadas por las inecuaciones del apartado anterior.

PROBLEMA #5 Sea el recinto poligonal convexo definido por el sistema de inecuaciones:x - 4y - 4 ; x + 2y - 4 0; x 0 ; y 0 Se pide: a) Dibujarlo y hallar sus vértices.b) Razonar si es posible maximizar en él la función f(x,y)= x + 2y . c) En caso afirmativo, calcular el valor óptimo correspondiente y puntos donde se alcanza.

PROBLEMA #6 La compañía ESPECIAS INDIAN C.A., tiene un stock limitado de dos hierbas que se utilizan en la producción de aderezos. INDIAN usa los dos ingredientes, HB1 y HB2, para producir ya sea curry o pimentón. El departamento de mercadotecnia informa que aunque la empresa puede vender todo el pimentón que pueda producir, sólo puede vender hasta un máximo de 1500 botellas de curry. Las

hierbas no utilizadas se pueden vender a $375 la onza de HB1 y a $167 la onza de HB2. Utilizando el método gráfico, determine él consumo de especias que maximice el ingreso de la Empresa.

Aderezo Ingredientes (Onzas/Bot) Demanda Precio de Venta

HB1 HB2 (Botellas) por botella ($)

Curry 5 3 1500 2750

Pimentón 2 3 Ilimitada 1300

Disponibilidad (Onzas) 10000 8500

PROBLEMA #7 Un estudiante dedica parte de su tiempo al reparto de propaganda publicitaria. La empresa A le paga 5 Bs. por cada impreso repartido y la empresa B, con folletos más grandes, le paga 7 bolívares por impreso. El estudiante lleva dos bolsas: una para los impresos A, en la que caben 120, y otra para los impresos B, en la que caben 100. Ha calculado que cada día es capaz de repartir 150 impresos como máximo. Lo que se pregunta el estudiante es: ¿Aplicando el método gráfico, cuantos impresos habrá de repartir de cada clase para que su beneficio diario sea máximo?

PROBLEMA #8 Un fabricante de cemento produce dos tipos de cemento, a saber en gránulos y polvo. Él no puede hacer más de 1600 bolsas un día debido a una escasez de vehículos para transportar el cemento fuera de la planta. Un contrato de ventas establece que él debe producir 500 bolsas al dia de cemento en polvo. Debido a restricciones del proceso, se requiere el doble del tiempo para producir una bolsa de cemento granulado en relación al tiempo requerido por el cemento en polvo. Una bolsa de cemento en polvo consume para su fabricación 0.24 minutos/bolsa y la planta opera un 8 día de la hora. Su ganancia es £4 por la bolsa para el cemento granulado y £3 por la bolsa para el cemento en polvo. Formule el problema de decidir cuánto se debe producir de cada tipo de cemento para maximizar las ganancias de la Empresa, utilizando el Método Gráfico.

PROBLEMA #9 SONY fabrica dos productos: (1) el Walkman un radiocasete portátil y (2) el Shader TV, un televisor en blanco y negro del tamaño de un reloj de pulsera. El proceso de producción de ambos productos se asemeja en que los dos necesitan un número de horas de trabajo en el departamento de electrónica, y

un cierto número de horas de mano de obra en el departamento de montaje. Cada Walkman necesita cuatro horas de trabajo de electrónica y dos en el taller de montaje. Cada televisor necesita tres horas de electrónica y una en montaje. Durante el actual período de producción se dispone de doscientas cuarenta horas en el departamento de electrónica y de cien horas en el de montaje. Cada Walkman vendido supone un beneficio de 7 dólares, mientras que para un televisor el beneficio unitario es de cinco dólares. El problema de SONY es determinar utilizando el Método Gráfico, la mejor combinación posible de Walkman y televisores que debe producir para alcanzar el máximo beneficio.

PROBLEMA #10 Un agricultor posee un campo de 70 hectáreas y puede cultivar ya sea trigo o cebada.

Si siembra trigo gasta US$ 30 por cada hectárea plantada. En cambio si siembra cebada, su gasto es de US$ 40 por hectárea.

El capital total disponible es de US$ 2.500. Por otra parte, también existen restricciones en la disponibilidad de agua para los meses de octubre y noviembre, según se indica:

Mes Consumo m3 /Hcta Consumo m3 / Hcta

Disponibilidad

Trigo Cebada m3

Octubre 900 650 57.900

Noviembre 1.200 850 115.200

Una hectárea cultivada rinde 30 Tm de trigo o 25 Tm de cebada según sea el caso.

los precios vigentes por Tm son de US$ 4,5 para el trigo y US$ 6,0 para la cebada.

Utilizando el método gráfico, determinar la cantidad de hectáreas de trigo y de cebada que debe sembrar el agricultor para que maximice su beneficio.

PROBLEMA #11 Una compañía de transportes posee 2 tipos de camiones. El camión tipo A tiene 20 m3 de espacio refrigerado y 40 m3 no refrigerado. El camión tipo B tiene 30 m3 refrigerados y 30 m3 no refrigerados. Una fábrica de productos alimenticios debe embarcar 900 m3 de productos refrigerados y 1200 no refrigerados. ¿Utilizando el Método Gráfico, cuántos camiones de cada tipo debe alquilar la fábrica

par minimizar costos si el tipo A se alquila a 30 Bs/Km y el B a 40 Bs/Km?

PROBLEMA #12 Una compañía de transportes tiene 10 camiones con capacidad 40.000 libras, y 5 camiones de 30.000 libras. Los camiones grandes tienen un costo de 0,30 US$/Km y los pequeños de 0,25 US$/Km. En una semana debe transportar la empresa 400.000 libras en un recorrido de 800 millas. La posibilidad de otros compromisos recomienda que por cada dos camiones pequeños mantenidos en reserva debe quedarse por lo menos uno de los grandes.

Utilizando el Método Gráfico, ¿Cuál es el número de camiones de ambas clases que deben movilizarse para ese transporte de forma óptima y teniendo en cuenta las restricciones descritas?

PROBLEMA #13 La empresa CHANNEL produce el perfume Versay. Este perfume requiere de químicos y trabajo para su producción. Dos procesos están disponibles. El proceso A transforma 1 unidad de trabajo y 2 unidades de químico en 3 onzas de perfume. El proceso B transforma 2 unidades de trabajo y 3 unidades de químico en 5 onzas de perfume. Cada unidad de trabajo le cuesta a CHANNEL Bs. 1.000 y cada unidad de químico le cuesta Bs. 1.500. Se tiene una disponibilidad máxima de 20.000 unidades de trabajo y un máximo de 35.000 unidades de químico para este período de planificación. En ausencia de publicidad CHANNEL cree que puede vender 1.000 onzas de perfume. Para estimular la demanda de ese perfume CHANNELpuede contratar una modelo famosa a quien se le pagará Bs. 50.000 la hora, hasta por un máximo de 25 horas. Cada hora que la modelo trabaje para la empresa se estima que incrementará la demanda de Versay en 200 onzas. Cada onza de Versay se vende a Bs. 60.500. Utilizando el método Gráfico, determine el volumen óptimo de la producción y venta del perfume.

PROBLEMA #14 Cada mes una empresa puede gastar. Como máximo, 1.000.000 Bs. en salarios y 1.800.000 Bs. en energía (electricidad y gasoil). La empresa sólo elabora dos tipos de productos A y B. Por cada unidad de A que elabora gana 80 Bs. y 50 Bs. por cada unidad de B. El costo salarial, y energético que acarrea la elaboración de una unidad del producto A y una del B aparece en la siguiente tabla:

A B

Costo 200 100

Costo energético 100 300

Utilizando el método gráfico, se desea determinar cuántas unidades de cada uno de los productos A y B debe producir la empresa para que el beneficio sea máximo.

PROBLEMA #15 La empresa de computadoras COMPAQ toma las decisiones trimestral sobre la fabricación de su mezcla de productos. Mientras toda sus líneas productivas incluyen una gran variedad de artículos de computación, solamente se considerará un problema más simple con sólo dos productos: las computadoras portátiles y las computadoras del escritorio. A COMPAQ les gustaría saber cuántos de dichos productos deben fabricar para obtener máximas ganancias en el primer trimestre del 2003. Hay varios límites del proceso que definen la capacidad productiva tanto de la computadora portátil como la de escritorio:

1.- Cada computadora (portátil o escritorio) requiere un microprocesador. Debido a la escasez de estos productos en el mercado, INTEL les ha asignado solamente 10,000 unidades trimestrales..

2.- Cada computadora requiere de memoria RAM. La memoria viene en 16MB por tarjeta. Una computadora portátil requiere 16MB de memoria instalada (es decir, necesita 1 tarjeta RAM) mientras una computadora de escritorio tiene 32MB (ó sea, requiere 2 tarjetas RAM). COMPAQ dispone en inventario 15.000 tarjetas RAM para el próximo trimestre.

3.- Cada computadora requiere un tiempo de ensamblaje. Debido a las estrechas tolerancias para ensamblar una computadora portátil, esta tarda un tiempo de 4 minutos contra 3 minutos para una computadora de escritorio. Hay 25,000 minutos disponibles de tiempo de ensamblaje para el próximo trimestre

Bajo las actuales condiciones del mercado, costos de los materiales y sistema productivo, la venta de cada computadora portátil genera US$ 750 de ganancia y cada computadora de escritorio produce $1000 ganancia.

Hay muchas preguntas que COMPAQ podría hacer. Por ello, aplicando el método Gráfico, determinar la respuesta desde la más obvia que es ¿Cuántos computadoras de cada tipo debefabricar COMPAQ en el próximo trimestre para maximizar sus beneficios?, hasta las otras preguntas, menos obvias, pero de interés para la Gerencia de la Empresa, entre ellas, ¿Cuánto estaría dispuesta a pagar COMPAQ por una memoria RAM adicional? ¿Qué efecto tiene sobre la ganancia , la perdida de 1,000 minutos de tiempo de ensamblaje por fallas en una de sus máquinas? ¿Que ganancia se requiere para justificar la fabricación de una computadora portátil con 32 MB de RAM?

PROBLEMA #16 Podemos comprar paquetes de abono A o B. Cada paquete contiene las unidades de potasio (K), fósforo (P) y nitrógeno (N) indicadas en la tabla, donde se da el precio del paquete.

Marca K P N Precio

A 4 6 1 15

B 1 10 6 24

¿Utilizando el método gráfico, en qué proporción hay que mezclar ambos tipos de abono para obtener al mínimo precio un abono que contenga 4 unidades de K, 23 de P y 6 de N?

PROBLEMA #17 Un ejecutivo de una empresa tiene $100.000 para invertir. Tiene dos inversiones: A y B. El Plan A garantiza que por cada dólar invertido, se obtendrán $0,70 al final de un año (se entiende que no puede fraccionarse este lapso de tiempo). El Plan B garantiza que por cada dólar invertido, se obtendrán $2,00 al final de un período de dos años (se entiende que no puede fraccionarse este lapso de tiempo). Aplicando el método SIMPLEX, asesore al ejecutivo para obtener el mejor rendimiento por su dinero durante un período de tres años.

PROBLEMA #18 La empresa McDonald’s vende hamburguesas de un cuarto de libra y hamburguesas con queso. La hamburguesa de un cuarto de libra obviamente utiliza ¼ de libra de carne y la hamburguesa con queso sólo utiliza 0,2 libras. El restaurante empieza cada día con 200

libras de carne. La utilidad neta es la siguiente: 0,20$ por cada hamburguesa de cuarto de libra y $0,15 por cada hamburguesa con queso. El gerente estima además que no venderá más de 900 hamburguesas en total. Aplicando el método SIMPLEX, determine la máxima utilidad que obtiene McDonald's.

PROBLEMA #19 Los 400 alumnos de un colegio van a ir de excursión. Para ello se contrata el viaje a una empresa que dispone de 8 autobuses con 40 plazas y 10 con 50 plazas, pero sólo de 9 conductores para ese día. Dada la diferente capacidad y calidad, el alquiler de cada autobús de los grandes cuesta 8000 Bs. y el de cada uno de los pequeños, 6000 Bs. ¿Utilizando el Método SIMPLEX, cuantos autobuses de cada clase convendrá alquilar para que el viaje resulte lo más económico posible?

PROBLEMA #20 A una persona que quiere adelgazar se le ofrecen dos productos A y B para que tome una mezcla de ambos con las siguientes recomendaciones:No de be tomar más de 150 g de la mezcla ni menos de 50 g.La cantidad de A debe ser igual o superior a la de B.No debe incluir más de 100 g de ASi 100g de A contiene 30 mg de vitaminas y 450 calorías y 100 g de B contienen 20 mg de vitaminas y 150 calorías, utilizando el método SIMPLEX:a) ¿Cuántos gramos de cada producto debe mezclar para obtener el preparado más rico en vitaminas?b) ¿Y el más pobre en calorías?

PROBLEMA #21 Los precios de venta de dos productos A y B están en la misma relación que 7 y 6. La producción de estos está definida por las siguientes condiciones:La producción de A es mayor o igual que la mitad de B y menor o igual que el doble de B.La producción total es tal que si sólo se produce A, se producen 10 kg, y si sólo se produce B, se producen 15 kg. Y si se producen conjuntamente, la producción máxima se encuentra en la recta que une los puntos anteriores.Dar la función objetivo de la venta de ambos productos.Expresar mediante inecuaciones el recinto definido.Utilizando el Método SIMPLEX, determinar los kilos que se han de producir de cada producto para obtener el máximo beneficio.

PROBLEMA #22 Una compañía petrolífera requiere diariamente 9 Tm, 12 Tm y 24 Tm de petróleo de calidad alta, media y baja respectivamente. La compañía tiene dos refinerías. La refinería A produce diariamente 1 Tm, 3 Tm y 4 Tm de calidades alta, media y baja respectivamente. La refinería B produce 2 Tm de cada una de las tres calidades. El coste diario de cada una de las refinerías es de 20.000.000 de Bs. ¿Utilizando el método SIMPLEX, cuántos días debe de trabajar cada refinería para que el costo sea mínimo?.

PROBLEMA #23 Un laboratorio farmacéutico desea elaborar un reconstituyente de manera que cada frasco contenga al menos 4 unidades de vitamina A, 23 unidades de vitamina B y 6 de vitamina C. Para suministrar estas vitaminas se emplea un aditivo M que cuesta 100 Bs. el gramo, el cual contiene 4 unidades de vitamina A, 6 de B y 1 de C y un aditivo H a un costo de 160 Bs. por gramo que contiene 1 unidad de vitamina A, 10 de B y 6 de C. ¿Utilizando el Método SIMPLEX, cuántos gramos de cada aditivo se deben incluir en cada frasco para minimizar el costo?

PROBLEMA #24 Un expendio de carnes acostumbra a preparar la carne para hamburguesas con una combinación de carne molida de res y carne molida de cerdo. La carne de res contiene 80% de carne y 20% de grasa, y le cuesta a la tienda Bs. 800 por kilo. La carne de cerdo contiene 68% de carne y 32% de grasa, y le cuesta Bs. 600 el kilo. El expendio no desea que el contenido de grasa de un kilo de hamburguesa preparada sea superior al 25%. Aplicando el métdo SIMPLEX, ¿Qué cantidad de cada tipo de carne debe emplear la tienda para preparar un kilo de hamburguesas a fin de minimizar los costos?.

PROBLEMA # 25 Una empresa láctea plantea la producción de dos

nuevas bebidas. producir un litro del primer tipo de bebida cuesta 2$, mientras que un litro del segundo tipo de bebida cuesta 5$. Para realizar el lanzamiento comercial se necesitan más de 6.000.000 litros de bebida, aunque del segundo tipo no podrán producirse (por limitaciones técnicas) más de 5.000.000. Además, se desea producir más cantidad de bebida del segundo tipo que del primero. ¿Cuántos litros habrá que producir de cada tipo de bebida para que el costo de producción sea mínimo?

PROBLEMA # 26 Usted tiene 60 hectáreas de tierra que aún no ha cultivado, y piensa trabajarlas para la próxima temporada junto a sus dos hijos, Pedro y Javier. Pedro insiste en sembrar ajo, pues tiene una ganancia neta mayor: sacarían $300 por ha., una vez descontados los

gastos, que son de $10 por ha. Javier quiere sembrar tomate, que tiene una ganancia neta de $200 por hectárea, pues están escasos de agua, y el tomate necesita menos agua que el ajo: 1 m3 por ha., contra 2 m3 por ha. para el ajo. (Disponen para la época crítica de sólo 100 m3 de agua).Su administrador, por su parte, hace notar que sólo tienen $1200 para comprar semillas, contratar obreros y otros gastos, así que no les alcanza el dinero para sembrar tomate, ya que los gastos son de $30 por hectárea.

a.- Formule y resuelva gráficamente el modelo matemático de Programación Lineal para maximizar la ganancia.

b.- Evalúe las sugerencias de sus hijos Pedro y Javier. ¿Puede usted mejorar estas sugerencias?

PROBLEMA #27 Una compañía petrolera produce un tipo de gasolina a partir de petróleo. Puede comprar cuatro tipos de petróleo y dispone de los siguientes datos:

Crudo A B CPrecio (Bs/lit)

1 0,8 0,1 0,1 43

2 0,3 0,3 0,4 31

3 0,7 0,1 0,2 47

4 0,4 0,5 0,1 37

A, B y C denotan los elementos a partir de los cuales se puede producir cada tipo de crudo. La tabla muestra los porcentajes de cada elemento en cada crudo producido. Las exigencias del mercado imponen que el crudo de base para la obtención de gasolina debe tener al menos el 60% del elemento A y no más del 30% de C. Obtenga el crudo base mezclando los cuatro tipos anteriores de forma tal que el coste sea mínimo.

PROBLEMA # 28 Usted dispone de 2.200 euros para invertirlos durante los próximos cinco años. Al inicio de cada año puede invertir parte del dinero en depósitos a un año o a dos años. Los depósitos a un año pagan un interés del 5 %, mientras que los depósitos a dos años pagan

un 11% al final de los dos años. Además, al inicio del segundo año es posible invertir dinero en obligaciones a tres años de la empresa Kola.C.A., que tienen un rendimiento (total) del 17 %. Plantea y resuelva el problema lineal correspondiente a fin de lograr que al cabo de los cinco años tu capital sea lo mayor posible.

PROBLEMA # 29 La Alcaldía tiene comprometido gastar en proyectos de infraestructura en los próximos cuatro años, 2000, 4000, 8000 y 5000 millones de Bolívares. Este dinero tiene que estar disponible el día 1 de enero del año en que se va a gastar. Para financiar estos gastos el ayuntamiento planea emitir unos bonos a largo plazo (20 años) con un interés remunerativo del 7% para la deuda emitida el primer año, del 6% para la emitida el segundo año, 6.5% para la del tercer año y del 7.5% para la emitida el cuarto año. Los intereses se empiezan a pagarinmediatamente. Si parte del dinero recaudado se depositase en cuantas a plazo fijo, el ayuntamiento es capaz de obtener el 6% de interés el segundo año, el 5.5% el tercer año y el 4.5% el cuarto año. El problema que se plantea el ayuntamiento es el de determinar la estrategia o plan óptimo de financiamiento de las obras de infraestructura.

PROBLEMA #30 Una pequeña empresa de cortinas tiene contratados tres profesionales: Ana, Claudia y Susana. La producción de una cortina consta de tres procesos: corte, en la que a partir de unas medidas se corta la tela necesaria, confección, en la que se cose la cortina, y acabado, en la que se colocan el forro, los remates y se pule el acabado. Cada una de las modistas emplea un tiempo distinto en cada uno de estos procesos, tiempos que vienen dados en la siguiente tabla (en minutos):

CORTE CONFECCIO

N ACABADO

ANA 15 20 30

CLAUDIA 20 25 20

SUSANA 30 20 10

Utilizando el método SOLVER, determinar qué persona debe encargarse de cada proceso de forma que el tiempo de producción sea mínimo.

PROBLEMA # 31 Un importador dispone de financiamiento para introducir mercaderías por $ 20.000.000. De acuerdo con las reglamentaciones, está autorizado para importar hasta $ 16.000.000 en repuestos para maquinarias agrícolas y hasta $ 8.000.000 en sustancias químicas. Puede obtener un beneficio del 6% sobre las sustancias químicas y del 2% sobre los repuestos. Por razones de mercado, decide que la suma a importar en repuestos debe ser al menos el doble de la dedicada a sustancias químicas. Determinar el programa de importaciones que le brinde el máximo beneficio.

PROBLEMA # 32 Un intermediario debe adquirir mercaderías para la próxima temporada, para lo cual dispone de un capital de $ 13.000.000. La mercadería A cuesta $ 80 por unidad y requiere un espacio de almacenamiento de 80 dm3, la mercadería B cuesta 70 $ y requiere un espacio de almacenamiento de 20 dm3. La mercadería C cuesta 100 $ y el espacio necesario es de 70 dm 3. El espacio disponible de almacenamiento es de 4.000 m 3. Los beneficios esperados son de 20 $ por unidad de A, 20 $ por unidad de B y 25 $ por unidad de C. Utilizando el método SOLVER, hallar el programa de compra que maximice el beneficio del importador

PROBLEMA #33 Un comerciante compra azúcar a granel y vende al detalle. Para venderla tiene dos alternativas: envases de 1 kg y envases de 5 kg. El precio de venta es $300 y $250 por kg respectivamente, y en el mercado del azúcar al detalle se pueden vender 20.000 kg en encases de 1 kg y 17.000 en envases de 5 kg. Debido a un contrato anterior se deben entregar 5.000 kg en envases de 5 kg a un determinado cliente. El comerciante se puede abastecer de azúcar desde dos proveedores. El primero le puede vender hasta 15.000 kg a un precio de $90 por kg, y el segundo le ofrece la cantidad de azúcar que el comerciante desee, pero a un precio de $110 por kg y debido a requerimientos de sus distribuidores el comerciante debe vender menos del tercio del azúcar en envases de 1 kg.

Además, suponga que el precio de los envases y el proceso de envasado son nulos, y que el comerciante no tiene azúcar almacenada y vende toda el azúcar que compra.

Formule y resuelva el problema de programación lineal utilizando el método SIMPLEX, que permita al comerciante decidir cual es el plan de abastecimiento y ventas de modo de obtener el mayor beneficio en su negocio

PROBLEMA #34 La oficina técnica coordinadora de cultivos (OTCC), tiene a su cargo la administración de 3 parcelas. El rendimiento agrícola de cada parcela está limitado por la cantidad de tierra cultivable como por la cantidad de agua asignada para regadío de la parcela por la comisión de aguas. Los datos proporcionados por este organismo son los siguientes:

Parcela Tierra Cultivable [ha] Asignación de agua [m3]

1 400 6002 600 8003 300 375

Las especies disponibles para el cultivo son la remolacha, trigo y soya, pero el ministerio de agricultura ha establecido un número máximo de hectáreas que pueden dedicarse a cada uno de estos cultivos en las tres parcelas en conjunto, como lo muestra la siguiente tabla:

Especie Consumo de Agua [m3 / ha]

Cuota Máxima[ha]

Ganancia Neta [$ / ha]

Remolacha 3 600 400

Trigo 2 500 300

Soya 1 325 100

Los dueños de las parcelas, en un acto de solidaridad social, han convenido que en cada parcela se sembrará la misma fracción de su tierra cultivable. Sin embargo, puede cultivarse cualquier combinación en cualquiera de las parcelas. Usted como Administrador, asesore a la OTCC utilizando el método SOLVER, para determinar cuantas hectáreas se deben dedicar al cultivo de las distintas especies en cada parcela, de modo de maximizar la ganancia neta total para todas las parcelas a cargo de la OTCC.

PROBLEMA #35 Una industria que fabrica papel y lo distribuye en rollos, debe determinar la mejor forma de realizar el proceso de corte. Los rollos

de papel que se producen tienen un ancho de 100 cm; sin embargo, los clientes demanda rollos de 30 cm, 45 cm y 50 cm de ancho. Por lo tanto, al cortar los rollos de 100 cm se incurre en una perdida de material que depende de la forma en que se corten los rollos originales. Se desea determinar utilizando el método SOLVER de Excel, la forma de efectuar el corte de manera que se satisfaga la demanda y se minimice la perdida total del material.

Se tiene un pedido de 800 rollos de 30 cm, 500 de 45 cm y 1000 de 50 cm.

Nota: Dadas las características de los rollos demandados por los clientes, existen seis alternativas diferentes de cortar un rollo de 100 cm. Para comenzar analizando las distintas alternativas de corte que se pueden realizar, pueden hacerse un dibujo para esquematizar mejor la situación (como nos muestra la indicación).

Alternativa Cortes Pérdidas

1 3 cortes de 30 cm 10 cm

2 1 corte de 30 cm y otros de 45 cm 25 cm


4 1 corte de 45 cm y otro de 50 cm 5 cm


6 1 corte de 30 cm y otro de 50 cm 20 cm

Con estas alternativas podemos definir nuestras variable de decisión, ya que de todas formas alguna de estas opciones usaremos para cortar los rollos:

PROBLEMA #36 Una empresa produce dos tipos de sillas (S1,S2) . El proceso de fabricación consta de dos tareas básicas: ensamblaje y terminado. Una silla S1 requiere de 1½ hora de ensamblaje y 1 hora de terminado dejando un beneficio de 20$. Una silla S2 requiere de ½ hora de ensamblaje y ½ hora de terminado dejando un beneficio de 12$. Actualmente se dispone de 100 horas de ensamblado y 80 horas de terminado. La compañía se encuentra realizando negociaciones salariales. Si usted fuera consultado, ¿qué aconsejaría respecto al aumento en el valor de la hora hombre de ensamblaje y de terminado ? Utilice el método SIMPLEX

PROBLEMA #37 La empresa americana COMPUTER produce dos tipos de computadoras: PC y VAX. Las computadoras se fabrican en dos lugares: Nueva York y Los Angeles. La sucursal de Nueva York puede producir hasta 800 computadoras y la de Los Angeles hasta 1000 computadoras. COMPUTER vende no más de 900 PC y 900 VAX. El beneficio de venta (sin contar la mano de obra) y el tiempo de fabricación asociado a cada sucursal y a cada producto es el siguiente:

Nueva York Los Angeles

PC $600 - 2 horas $1000 - 3 horas

VAX $800 - 2 horas $1300 - 4 horas

Un total de 4000 horas de trabajo se encuentran disponibles. La mano de obra se paga a $20 por hora. COMPUTER quiere maximizar los beneficios.

a) Si hubiera disponibles 3000 horas de trabajo, ¿cuál sería el beneficio total de COMPUTER?

b) Suponga que un contratista externo ofrece de aumentar la capacidad de producción de Nueva York a 850 computadoras, a un costo de $800. ¿Le conviene a COMPUTER aceptar la oferta?

c) ¿Cuánto debería aumentar el beneficio de una VAX producida en Los Angeles, para que a COMPUTER le convenga producir VAX en Los Angeles?

d) ¿Cuánto es lo máximo que COMPUTER estaría dispuesto a pagar por cada hora extra de trabajo?

PROBLEMA #38 En la empresa Explosivos, Inc. se mezclan azufre, carbón y salitre para producir pólvora. El producto final debe contener al menos 10%, pero no más de 20%, de carbón por unidad de peso. La cantidad de salitre no puede exceder el 50% de la cantidad de carbón usado. Para evitar una explosión accidental, la suma de 50% del azufre más 60% del carbón más 30% del salitre usados no puede exceder el 35% del producto final. El azufre es con mucho el componente más caro.

Formule y resuelva por SIMPLEX, el modelo para determinar la cantidad de cada ingrediente que debe utilizarse para producir cada libra de pólvora que satisfaga las restricciones y, a la vez, que requiera la menor cantidad de azufre.

PROBLEMA #39 Una compañía maderera desea utilizar la madera de uno de sus bosques en su aserradero o en su planta de celulosa. Esto significa que la madera puede convertirse en cualquier combinación de tablas de madera aserrada y celulosa. Para producir 1.000 mts de tablas de madera hace falta 1.000 mts de Pino tipo A o 3.000 mts de Pino tipo B. Para producir 1.000 Kg. de celulosa hace falta 2.000 mts de Pino tipo A o 4.000 mts de Pino tipo B. Este bosque cuenta con 32.000 mts de Pino tipo A y 72.000 mts de Pino tipo B. Compromisos de venta nos obligan a producir al menos 4.000 mts de tablas de madera y 12.000 Kg. de celulosa. Los beneficios son $40 por cada 1.000 mts de tablas de madera y $60 por cada 1.000 Kg. de celulosa.

(a) Plantear el problema lineal y resolverlo mediante el método SIMPLEX Expresar en términos económicos la solución.

(b) Verificar gráficamente la solución.

(c) Expresar el problema dual asociado e interpretarlo económicamente.

(d) Suponga que es posible adquirir un bosque adyacente con 10000 pies de Pino tipo A. ¿Debemos adquirirlo?¿Hasta cuánto estaremos dispuesto a pagar por este bosque?

PROBLEMA #40 Una compañía de seguros está introduciendo dos nuevas líneas de productos: seguros de riesgos especiales e hipotecas. La ganancia esperada es 5 USD. por unidad sobre el seguro de riesgos especiales y 2 USD. por unidad sobre hipotecas. La administración quiere establecer las cuotas de venta para las nuevas líneas de productos con el fin de maximizar la ganancia esperada. Los requerimientos de trabajo son los siguientes:

Horas de trabajo por Unidad

Departamento Riesgos Especiales Hipotecas Horas Disponibles

Procesamiento 3 2 2400

Administración 0 1 800

Reclamos 2 0 1200

a)- Plantear el modelo de programación lineal.

b)- Resolver el problema utilizando el método SIMPLEX

c)- Hallar la solución gráfica. Exprese los resultados en términos económicos.

PROBLEMA #41 Una compañía minera produce lignito y antracita. Por el momento es capaz de vender todo el carbón producido. La ganancia por tonelada de lignito y antracita vendida es de 4 y 3 unidades monetarias, respectivamente. El proceso de cada tonelada de lignito requiere 3 horas de trabajo en la máquina de cortar carbón y otras 4 horas en la de lavado. Para la antracita se requieren en cada fase 4 y 2 horas, respectivamente. Las horas diarias disponibles para cada una de las máquinas son 35 y 30, respectivamente. Además se supone que al menos se deben producir diariamente 4 Tm. de carbón. Plantea un modelo de programación lineal con el fin de hacer máxima la ganancia y resuélvelo utilizando el Método SIMPLEX.

PROBLEMA # 42 Un agricultor dispone de 500 hectáreas de tierra de cultivo, y desea determinar el número de hectáreas que asignará a cada una de sus cosechas: trigo, maíz y soja. En la tabla siguiente se resumen los días necesarios, costo de preparación y ganancia por hectárea de los tres cultivos:

CULTIVO DIAS COSTO GANANCIATrigo 6 100 60

Maíz 8 150 100

Soya 10 120 80

El número máximo de días disponibles es 5.000, y el agricultor tiene un presupuesto de 60.000 USD

a) Encuentra la solución óptima utilizando el método SIMPLEX

b) Suponiendo que el día laboral es de ocho horas ¿le convendría al agricultor

contratar ayuda adicional a 3 USD por hora? ¿Por qué?

c) Supone que el agricultor tiene un contrato para entregar al menos el equivalente a 100 hectáreas de trigo, ¿cuál será entonces la solución?

PROBLEMA #43 Una compañía de inversiones tiene actualmente 10 millones de dólares disponibles para la inversión. La meta que se ha trazado consiste en maximizar la retribución esperada durante el siguiente año. Sus cuatro posibilidades de inversión se encuentran resumidas en la siguiente tabla. Además, la compañía ha especificado que al menos un 30% de los fondos tendrán que colocarse en acciones ordinarias y bonos de la Tesoro, y que no más del 40% del dinero deberá invertirse en fondos de bolsa y títulos municipales. Se invertirá la totalidad del capital. ¿Cuánto debe invertir la empresa en cada activo? ¿mejoraría el rendimiento si se pudieran invertir hasta 6 millones en bonos del Tesoro?

Inversión Retribución Inversión Máxima Esperada (%) (Millones de $)

Bonos del Tesoro 8 5

Acciones ordinarias 6 7

Fondos de Bolsa 12 2

Títulos Municipales 9 4

PROBLEMA #44 Para producir 2 toneladas de trigo se requieren 4 hectáreas, 2 bolsas de semillas de trigo por hectárea y 5 meses/hombre.

Para producir 3 toneladas de centeno se requieren 2 hectáreas, 1.5 bolsas de semillas de centeno por hectárea y 9 meses/hombre.

El precio del trigo y del centeno por tonelada asciende a 300 y 230 pesos respectivamente. El costo de la bolsa de semillas de cada uno de estos productos es $20 la de trigo y $30 la de centeno.

El empresario que espera maximizar sus beneficios dispone de 120 hectáreas y de 270 meses/hombre. Asimismo cuenta de un contrato que le otorga la opción de arrendar un campo lindero de 80 hectáreas a razón de $30 la hectárea utilizada. La ley laboral, por otra parte, le brinda el beneficio de contratar mano de obra adicional a un costo de $50 por meses/hombre, sin limitación.

a) Formule el problema en términos de programación lineal.

b) Utilizando el Método SIMPLEX, determine cuál será la solución óptima del empresario y el correspondiente nivel que adoptará cada una de las actividades.

c) Formule el programa dual correspondiente y luego, haciendo uso del programa de factibilidad, establezca la primera solución básica.

PROBLEMA #45 Una ama de casa, típico ejemplo de la economía informal, hace en sus ratos domésticos libres dos tipos de salsa de tomate que vende en jarras de barro al supermercadode la zona. La primera salsa, requiere utilizar 3 Kg de tomates y 4 tazas de vinagre por jarra de salsa. La segunda requiere 5 Kg de tomates y 2 tazas de vinagre. La primera salsa le produce un beneficio de 40 Bolívares por jarra y la segunda 50 bolívares. El supermercado que remite su producción casera hacia los circuitos comerciales (no sabemos con qué beneficio relativo) le impone a la ama de casa las siguientes condiciones:

• Que produzca como mínimo 3 jarras de salsa a la semana.

• Que le compre como máximo 24 kg de tomate y 3 botellas de vinagre a la semana.

Sabiendo que una botella de vinagre equivale a 16 tazas y que el supermercado monopoliza la venta de tomate y vinagre en la región, Utilizando el método SIMPLEX, determinar los precios a los que estaría dispuesta a pagar el tomate y el vinagre la ama de casa a otro comerciante de la economía informal, para minimizar sus costos.

PROBLEMA #46 La compañía Minas Universal opera tres minas en Puerto Ordaz, el mineral de cada una se separa, antes de embarcarse, en dos grados. La capacidad diaria de producción de las minas así como sus costos diarios de operación son los siguientes:

Mineral de Grado alto

ton/día

Mineral de grado bajo

Ton/día

Costo de operación

miles/día

Mina I 4 4 20

Mina II 6 4 22

Mina III 1 6 18

La Universal se comprometió a entregar 54 toneladas de mineral de grado alto y 65 toneladas de mineral de grado bajo para fines de la siguiente semana. Además, tiene contratos que garantizan a los trabajadores de ambas minas el pago del día completo por

cada día o fracción de día que la mina esté abierta. Utilizando el método SIMPLEX, determínar el número de días que cada mina debería operar durante la siguiente semana, si Minas Universal ha de cumplir su compromiso a un costo total mínimo.

PROBLEMA #47 La Refineria Isla C.A., produce gasolina tipos regular y primera. La refinería fabrica los productos mezclando 3 componentes de petróleo. La empresa utilizando el programa SOLVER, quiere determinar cómo mezclar los 3 componentes en los 2 productos de gasolina para alcanzar el máximo de ganancias. La gasolina regular se vende a $0.50 por el galón y la de primera se vende a $0.54 por el galón. Cinco mil galones están disponibles de Componente 1 cuyo costo es de $0.25 por el galón, 10,000 galones están disponibles de Componente 2 con costo de $0.30 por el galón, y 10,000 galones están disponibles de Componente 3 que cuesta $0.42 por el galón. Los compromisos actuales a distribuidores exigen a la compañía producir 10,000 galones de gasolina regular por lo menos. Además, las especificaciones del producto requieren a lo siguiente: regular - a lo sumo 30% de Componente 1, por lo menos 40% de Componente 2, y a lo sumo 20% de Componente 3; la de primera - por lo menos 25% de Componente 1, a lo sumo 40% de Componente 2, y por lo menos 30% de Componente 3.

PROBLEMA #48 Una empresa proveedora de alimentos balanceados generadora de beneficios ha obtenido una orden de compra para producir un compuesto con, por lo menos, 100 gramos de fibras, 300 gramos de proteínas y 70 gramos de minerales.

En el mercado puede obtener los siguientes productos con las siguientes características:

CONTENIDO PRODUCTO

DE: 1 2 3

FIBRAS20% 30% 5%

PROTEÍNAS60% 50% 38%

MINERALES9% 8% 8%

PRECIO POR KG.$10 $15 $8

Utilizando el programa SIMPLEX, determine:

a) ¿ Cuál será la proporción de cada producto en el compuesto óptimo ?

b) ¿ A cuánto ascenderá el precio sombra (por gramo) de: Fibras, Proteínas y Minerales

PROBLEMA #49 La empresa MADERAS C,.A. es un fabricante de muebles independiente. Hace tres estilos diferentes de mesas, A, B, C. Cada modelo de mesa requiere de una cierta cantidad de tiempo para el corte de las piezas, su montaje y pintura. MADERAS C.A., puede vender todas las unidades que fabrica. Es más, el modelo B se puede vender sin pintar. Utilizando los datos indicados, aplicando SOLVER de Excel, determine la máxima utilidad mensual que puede obtener la Empresa.

Requerimiento de Horas Hombre por mesa

Modelo Utilidad por mesa Corte Ensamblado PinturaA $ 17.500 1 2 4B $ 20.000 2 4 4B sin pintar $ 10.000 2 4 0C $ 25.000 3 7 5 Disponibilidad mensual de HH 200 298 148

PROBLEMA #50 Una Empresa metalmecánica, puede fabricar cuatro productos diferentes (A, B, C, D) en cualquier combinación. La producción da cada producto requiere emplear las cuatro máquinas. El tiempo que cada producto requiere en cada una de las cuatro máquinas, se muestra en la tabla anexa Cada máquina está disponible 80 horas a la

semana. Los productos A, B, C y D se pueden vender a $8, $6, $5 y $4 por kilogramo, respectivamente. Los costos variables de trabajo son de $3 por hora para las máquinas 1 y 2 y de $1 por hora para las máquinas 3 y 4. El costo del material para cada kilogramo de producto A es de $3. El costo de material es de $1 para cada kilogramo de los productos B, C y D. Aplicando el método SOLVER de Excel, la máxima utilidad que puede obtener la empresa.

Tiempo de máquina (Minutos por kilogramo de producto)

Producto Máquina Demanda

1 2 3 4 Máxima

A 10 5 3 6 100

B 6 3 8 4 400

C 5 4 3 3 500

D 2 4 2 1 150

PROBLEMA #51 DELL COMPUTER necesita satisfacer la demanda de computadoras portátiles de su Cliente Corporativo (PDVSA), así como de sus Clientes del Sector Educativo (USM), para los próximos cuatro trimestres. DELL COMPUTER dispone en inventario de 5,000 computadoras portátiles. La demanda esperada de computadoras portátiles para cada uno de los trimestres es la siguiente, 7,000; 15,000; 10,000; y 8,000 respectivamente. DELL COMPUTER tiene la capacidad productiva y los componentes requeridos para fabricar 10,000 computadoras portátiles en cada trimestre, a un costo unitario de $2000 por el computadora ensamblada. Usando horas extras de sobretiempo, DELL COMPUTER , pudiera fabricar adicionalmente hasta 2,500 computadoras portátiles trimestrales pero a un costo de $2200 cada una ó también pueden disponerse de computadoras fabricadas en un trimestre para satisfacer la demanda de otro trimestre , manteniendo las mismas en inventario . Cada computadora portátil en inventario genera un sobre costo de almacenamiento y despacho de $100 la unidad almacenada.

Aplicando el programa SOLVER, indicar como puede DELL COMPUTER satisfacer la demanda de sus clientes al mínimo costo.

2 PROBLEMA #52 Una institución bancaria se encuentra en proceso de formular su política de préstamos para el próximo mes. Para este fin, se asigna un máximo de $12.000.000. Siendo una institución de servicios integrales, debe otorgar préstamos a todos los tipos de clientes. La tabla que sigue señala los tipos de préstamos, la tasa de interés que cobra el banco y la cantidad porcentual de pagos no cubiertos estimado por experiencia.

TIPO DE PRÉSTAMO TASA DE INTERÉS PORCENTAJE DE PAGOS NO CUBIERTOS

Personal 14% 10%

Automóvil 13% 7%

Casa 12% 3%

Agrícola 12,5% 5%

Comercial 10% 2%

Se supone que los pagos no cubiertos son irrecuperables y por lo tanto no producen ingresos por concepto de interés. La competencia con otras instituciones bancarias exige que cuando menos el 40% de la asignación de fondos sea para préstamos agrícolas y comerciales. El banco tiene, así mismo, una política que especifica que el porcentaje total de pagos irrecuperables no debe exceder el 4%. Aplicando el método WinQSB determine las condiciones para las cuales se optimizan las ganancias netas de la institución bancaria.

PROBLEMA #53 Un restaurante de autoservicio, está abierto los siete días de la semana. Basado en la experiencia del pasado, el número de empleados requeridos en un día particular se da como sigue:

DIA LUN. MAR. MIE. JUE. VIE. SAB. DOM.

No. OBREROS 14 13 15 16 19 18 11

De acuerdo a la norma laboral, cada obrero trabaja cinco días consecutivos, con dos días de descanso, repitiéndose este proceso para todos los obreros. Aplicando el programa SOLVER indicar como se puede minimizar el número de obreros requeridos por el restaurante?

PROBLEMA #54 Una firma financiera tiene $500,000 disponible para invertir y aplicando el programa SOLVER, busca determinar cuánto de esa cantidad debe ser invertida en cada una de las cuatro siguientes posibilidades: bolsa X, bolsa Y, bonos X y bonos Y, en el lapso de un año. Un máximo de $105,000 puede ser invertido en bonos de tipo X y un máximo de $100,000 puede ser invertido en bonos del tipo Y. La inversora sabe que existe un riesgo considerable asociado con la inversión en la bolsa X. Por lo tanto, ha determinado que no invertirá más de un cuarto de su inversión total en la bolsa X. También la cantidad total invertida en la bolsa Y debe ser al menos tres veces la cantidad invertida en la bolsa X. Además, la inversora requiere que la inversión en bonos sea al menos tan grande como la mitad de sus inversiones en las bolsas. Los retornos netos anuales son:

Bolsa X 20% Bolsa Y 10% Bonos X 9% Bonos Y 11%

PROBLEMA #55 En la empresa PROLINEAL C.A., el departamento de ingeniería señala que cuando se produce el bien 1 solamente, se obtiene como máximo una producción de 200 unidades del mismo; utilizando a pleno la capacidad instalada de máquinas del tipo A, no utilizando un 25% de la capacidad de las máquinas B y usando el 50% de las máquinas C. En cambio, cuando sólo se produce el bien 2 se utiliza el 100% de la capacidad instalada de máquinas C y sólo el 12.5% de la capacidad instalada de las A y el 75% de las B; obteniéndose un máximo de 100 unidades del bien en cuestión.

El beneficio neto por unidad del bien 1 y del 2 es, respectivamente, $1 y $3.

En base a los datos aportados por el departamento de ingeniería, el gerente de producción argumenta que como sobraría capacidad instalada del parque de maquinarias B, convendrá ofrecerlas en alquiler. El gerente técnico opina, en cambio, que bajo las circunstancias, lo que realmente conviene es introducir un nuevo producto, el bien 3, que requiere 2% de capacidad de A, 10% de B y 0.5% de C, para obtener

una unidad de este bien; que puede venderse en el mercado con un beneficio neto unitario de $14.

Como el presidente de la empresa sabe que usted tiene buenos conocimientos de programación lineal y que las condiciones en las que opera Prolineal son aptas a tal planteo, le pide que, aplicando la herramienta WINQSB, dé su opinión acerca del mejor curso de acción a seguir, respondiendo críticamente a los planteos de los dos gerentes.

2. PROBLEMA #56 Al gerente de cartera de un fondo de pensiones se le ha pedido invertir $1.000.000 en un gran fondo de pensiones. El Departamento de Investigación de Inversiones ha identificado seis fondos mutuales con estrategias de inversión variables, resultando en diferentes rendimientos potenciales y riesgos asociados, como se resume en la tabla siguiente.

FONDOS

1 2 3 4 5 6Retorno

(%)30 20 15 12 10 7

Categoría de riesgo

Alto Alto Alto Mediano Mediano Bajo

La administración ha especificado las siguientes pautas:

· La cantidad total invertida en fondos de alto riesgo debe estar entre el 50% y el 75% de la cartera.

· La cantidad total invertida en fondos de mediano riesgo debe estar entre el 20% y el 30% de la cartera.

· La cantidad total invertida en fondos de bajo riesgo debe ser de al menos el 5% de la cartera.

· La cantidad invertida en los fondos de alto riesgo 1,2 debe estar en relación proporcional de 1:2.

· La cantidad invertida en los fondos de mediano riesgo 4 y 5 debe estar en la proporción 1:2.

Aplicando el método WinQSB, determine los fondos mutuales que maximicen el beneficio al final del período

PROBLEMA #57 Un industrial agrícola fabrica alimentos para vacas, ovejas y pollos. Esto se hace mezclando los siguientes ingredientes: maíz, piedra caliza, soja y harina de pescado. Estos ingredientes contienen los siguientes nutrientes: vitaminas, proteína, calcio y grasa. Los contenidos de los nutrientes en cada kg de los ingredientes se resumen en la tabla:

Nutriente

Ingrediente Vitamina Proteína Calcio Grasa

Maíz 8 10 6 8

Piedra caliza 6 5 10 6

Soja 10 12 6 6

Harina de Pescado

4 8 6 9

El industrial es contratado para producir 10,6 y 8 tons métricas de los tres tipos de alimentos. Debido a escasez, una cantidad limitada de los ingredientes está disponoble, concretamente: 6 tons de maíz, 10 tons de piedra caliza, 4 tons de soja y 5 tons de harina de pescado. El precio por kilogramo de estos ingredientes es, respectivamente, $0,20, $0,12, $0,24 y $0,12. Las unidades máximas y mínimas de nutrientes permitidas por kg de alimento se detallan en la siguiente tabla:

Nutriente

VITAMINA PROTEÍNA CALCIO GRASA

PRODUCTO min max min max min max min max

Al. vaca 6 6 7 4 8

Al. oveja 6 6 6 4 6

Al. pollo 4 6 6 6 4 6

Utilizando el programa WinQSB, determinar la composición del alimento que minimice su costo total.

PROBLEMA #58 La empresa PARMALAT tiene dos máquinas distintas para procesar leche pura y producir leche descremada, mantequilla o queso. La cantidad de tiempo requerido en cada máquina para producir cada unidad de producto resultante y las ganancias netas se proporcionan en la siguiente tabla:

LECHE MANTEQUILLA QUESO

DESCREMADA

MAQUINA #1 (min/galón) 0,2 0,5 1,5

MAQUINA #2 (min/galón) 0,3 0,7 1.2

GANANCIA NETA (US$/Galon) 0,22 0,38 0,72

Suponiendo que se dispone de 8 horas en cada máquina diariamente, como Gerente del Departamento de Administración , utilizando el programa WINQSB, formule un modelo para determinar un plan de producción diaria que maximice las ganancias corporativas netas y produzca un mínimo de 300 galones de leche descremada, 200 libras de mantequilla y 100 libras de queso.

PROBLEMA #59 Considere un presupuesto de publicidad de $30,000 para un nuevo producto ligeramente caro. Por lo menos deben usarse 10 anuncios de la televisión, y por lo menos deben localizarse 50,000 compradores potenciales durante la campaña. También, un máximo de $18,000 pueden gastarse los anuncios en la televisión. ¿Dado los datos incluidos en la Tabla anexa, utilizando el programa WINQSB, determinar el plan de medios de comunicación de publicidad óptimo que aumentará al máximo las compras esperadas?

Tipo de

medio

Familias

Encuestadas

Costo

Por aviso

Maximo

disponible

Expectativa

de compra

TV-de dia(1 min.)

1,000 $1,500 15 65

TV-tarde.

(30 sec.)

2,000 $3,000 10 90

periodico

semanal

1,500 $400 25 40

periodico

domingo

2,500 $1,000 4 60

Radio

(30 sec.)

300 $100 30 20

PROBLEMA #60 Una firma productora de detergentes cuenta con dos procesos productivos para fabricarlos. Cada actividad utiliza enzimas, capacidad de planta de producción y capacidad de planta de envasado. Las enzimas se pueden comprar en el mercado en cantidades ilimitadas a $100 por unidad. Las plantas de envasado y producción tienen una capacidad máxima de procesado fija. El precio del detergente es de $4 por unidad y se puede vender toda la cantidad que se pueda fabricar.

El primero de los procesos utiliza dos unidades de enzimas, 4% de la capacidad de la planta de producción y 8% de la de envasado, por cada 100 unidades de detergente. El segundo proceso requiere dos unidades de enzimas, 2% de la capacidad de la planta de producción y 12% de la de envasado, por cada 100 unidades de detergente.

Utilizando el programa WINQSB, determine:

a) ¿ Cuál es el programa óptimo de producción y a cuánto ascenderá el beneficio esperado?

b) ¿ Cuál planta aconsejará usted ampliar, si ello fuera posible y de muy bajo costo, en qué porcentaje ?

PROBLEMAS DE TAREA A ENTREGAR EL 01 DE AGOSTO DEL 200 3

Problema #1) Dos mataderos, P y Q, se encargan de suministrar la carne consumida semanalmente en tres ciudades, R, S y T: 20, 22 y 14 toneladas, respectivamente. El matadero P produce cada semana 26 toneladas de carne, y el Q, 30. Sabiendo que los costes de transporte, por tonelada de carne, desde cada matadero de a cada ciudad, son los reflejados en la siguiente tabla:

R S T

P 1 3 1

Q 2 1 1

Utilizando el método SIMPLEX analítico, determinar cuál es la distribución de transporte que supone un coste mínimo.

Problema #2) Desde dos almacenes A y B, se tiene que distribuir fruta a tres mercados de la ciudad. El almacén A dispone de 10 toneladas de fruta diarias y el B de 15 toneladas, que se reparten en su totalidad. Los dos primeros mercados necesitan, diariamente, 8 toneladas de fruta, mientras que el tercero necesita 9 toneladas diarias.El coste del transporte desde cada almacén a cada mercado viene dado por el siguiente cuadro:

Almacén Mercado 1 Mercado 2 Mercado 3

A 10 15 20

B 15 10 10

Utilizando el método SIMPLEX analítico, planificar el transporte para que el coste sea mínimo.

Problema #3) Una fabrica de jamones tiene dos secaderos A y B que producen 50 y 80 jamones por mes. Se distribuyen a tres tiendas de las ciudades M, N y O cuya demanda es 35, 50 y 45 respectivamente. El coste del transporte por jamón en euros se ve en la tabla siguiente:

M N O

A 5 6 8

B 7 4 2

Utilizando el método SIMPLEX analítico, averígue cuántos jamones deben enviarse desde cada secadero a cada tienda para hacer mínimo el gasto en transporte.

Problema #4) La Empresa transportista ABC posee varios camiones usados para acarrear piedra molida para proyectos de carreteras en el municipio. El contratista de carreteras para quien trabaja le ha dado el programa de la semana siguiente. Utilizando el SIMPLEX analítico, calcule el costo óptimo del transporte

Proyecto

Necesidades Semanales, Cargas de

Camión

Planta

Disponibilidad Semanal, Cargas de

Camión

A 50 W 45

B 75 X 60

C 50 Y 40

Información de Costos:

De Al proyecto A Al proyecto B Al proyecto C

Planta W $ 4 $ 3 $ 3

Planta X 6 7 6

Planta Y 4 2 5

Problema #5) Una compañía tiene tres fábricas (A, B y C) para ensamblar computadoras, y dispone de tres tiendas habilitados para la venta (D, E y F). Las cantidades producidas por A, B y C son 1.000, 5.000 y 4.000 unidades por día respectivamente. La máxima cantidad que puede vender el almacén D es 3000 unidades/día, E es 6000 unidades/día y F es 7000 unidades/día. Los costos de transporte de cada fábrica a cada almacén están dados en la siguiente tabla:

Suministro Demanda

D E F

A 1 4 2

B 3 1 2

C 4 5 2

A) Obtener una solución básica factible por el método de la esquina del noroeste.

B) Resolver por el método de los multiplicadores.

Problema #6) Tres centrales de distribución tienen que dar electricidad a tres ciudades. La tabla de costos de transporte de electricidad es la siguiente:

CIUDAD SUMINISTRO

CENTRAL A B C (MKwh)

I 8 6 10 35

II 9 12 13 50

III 14 9 16 40

DEMANDA (MKwh) 45 20 30

Determine las variables de decisión y plantee el problema de minimización, determinando la distribución eléctrica para cada ciudad, utilizando el método SIMPLEX analítico.

Problema #7) Hay que distribuir el agua de tres pozos entre tres ciudades. La tabla de costos de distribución es la siguiente:

CIUDADES OFERTA

POZO A B C (M lts/dia)

I 7 8 10 40

II 5 12 4 30

III 9 7 8 45

DEMANDA (M lts/dia) 55 40 60

Plantear el problema del transporte dado por dicha tabla. ¿está equilibrado? ¿Como puede equilibrarlo? Utilizando el método SIMPLEX analítico, determine la distribución del Agua para cada una de las ciudades.

Problema #8) Una Empresa dispone de 3 plantas (Pli) para hacer 3 tipos de productos (Pri). Los costos y tiempos de producción aparecen en la tabla. Si se necesitan 100 unidades de cada producto y hay disponibles

40 horas de trabajo, formular un modelo de transporte para minimizar costos y resolverlo por el método SIMPLEX analítico.

Pr1 Pr2 Pr3 tiempo (minutos)

Pl1 60 40 28 20

Pl2 50 30 30 16

Pl3 43 20 20 15

Problema #9) Una compañía abastece a 3 clientes (Ci) cuyas demandas son de 30 unidades cada uno. Existen dos depósitos con 40 y 30 unidades disponibles respectivamente. El costo unitario de envío aparece en la tabla. Por cada unidad no enviada , existe un costo de ‘no cumplimiento’. Formular un modelo de transporte para minimizar costos y resuelva por el método SIMPLEX analítico.

C1 C2 C3

depósito 1 15 35 25

depósito 2 10 50 40

costo no cumplimiento 90 80 110

Problema #10) Dos compañías farmacéuticas tienen inventario de dosis de 1.1 y 0.9 millones de cierta vacuna contra la gripe y se considera inminente una epidemia de gripe en tres ciudades. Ya que la gripe podría ser fatal para los ciudadanos de edad avanzada, a ellos se les debe vacunar primero; a los demás se los vacunará según se presenten, mientras duren los suministros de vacuna.

Las cantidades de vacuna (en millones de dosis) que cada ciudad estima poder administrar son las siguientes:

Ciudad 1 Ciudad 2 Ciudad 3

Ancianos 0.325 0.26 0.195

Otros 0.75 0.80 0.65

Los costos de embarque (en centavos por dosis) entre las compañías y las ciudades son:

Ciudad 1 Ciudad 2 Ciudad 3

Compañía 1 3 3 6

Compañía 2 1 4 7

Utilizando el método SIMPLEX analítico, determinar un programa de embarque de costo mínimo que provea a cada ciudad de vacuna suficiente para atender al menos a los ancianos.

Problema #11) Una compañía panificadora puede producir un pan especial en cualquiera de sus plantas, en la siguiente forma:

Planta Capacidad de producción(unidad pan)

Costo de producción ($/unidad pan)

A 2500 23

B 2100 25

Cuatro cadenas de restaurantes desean adquirir este pan, sus demandas y precios que desean pagar son los siguientes:

Cadena Demanda Máxima (unidad pan) Precio ofrecido ($/ unidad pan)

1 1800 39

2 2300 37

3 550 40

4 1750 36

El costo ($) de embarcar una unidad de pan de una planta a un restaurante es:

Cadena 1 Cadena 2 Cadena 3 Cadena 4

Planta A 6 8 11 9

Planta B 12 6 8 5

Utilizando el método SIMPLEX analítico, determinar un programa de entregas para la compañía panificadora maximizando su ganancia total.

Problema #12) Un fabricante tiene tres plantas P1, P2, P3 y cinco bodegas B1,...,B5, el problema es establecer la planta Pi que debe producir el suministro para cada bodega. La capacidad de las plantas es limitada. En la tabla aparecen la capacidad de producción de las plantas y los requerimientos de ventas de las bodegas en miles de cajas:

Planta Producción Bodega Venta

P1 100 B1 50

P2 60 B2 10

P3 50 B3 60

B4 30

B5 20

Total 210 Total 170

El costo de despacho de 1000 cajas desde cada planta a cada bodega aparece en la siguiente tabla:

Destino Origen US$ B1 B2 B3 B4 B5

P1240 300 160 500 360

P1420 440 300 200 220

P3300 340 300 480 400

La compañía desea determinar un programa de embarques que minimice los costos generales de transporte de la empresa, utilice el método SIMPLEX analítico.

Problema #13) Considere el problema de transporte que se originan debido a un accidente. Existen tres ambulancias con distintas capacidades para trasladar heridos hacia cuatro Servicios de Urgencia. La siguiente tabla presenta la capacidad de las Ambulancias y los Servicios de Urgencia.

Ambulancia Capacidad Servicio de

UrgenciaDemanda

1 3 1 4

2 7 2 3

3 5 3 4

4 4

Los costos generados por el transporte se muestran en la siguiente tabla.

SU 1 SU 2 SU 3 SU 4

Ambulancia 1 2 2 2 1



a) Utilizando el Método de Vogel, encuentre la solución inicial. ¿ Es óptima? ¿ Existe solución alternativa?

b) Realice un análisis de sensibilidad y determine los costos que permitan a las ambulancias estar indiferentes con respecto a los Servicios de Urgencia.

c) Realice un modelo de programación lineal que permita resolver el problema.

Problema #14) Una empresa de electricidad tiene 4 plantas termoeléctricas que son abastecidas por 3 minas de carbón. La oferta total de carbón de las minas es igual a los requerimientos totales de las plantas termoeléctricas. Existe un costo de transporte de una unidad desde cada mina a cada planta. En la tabla que se muestra a continuación se indican la oferta disponible, los requerimientos y los costos de transporte por unidad.

MinaPlanta

Oferta1 2 3 4

1 2 3 4 5 14

2 5 4 3 1 15

3 1 3 3 2 17

Demanda 6 11 17 12

a) La empresa de electricidad quiere determinar cuántas unidades debe transportar desde la mina a cada planta para minimizar el costo de transporte.

b) Resolver el problema utilizando el método SIMPLEX analítico.

Problema #15) Una empresa industrial produce 1000 unidades al mes de un cierto artículo, P1. Cada unidad de producto terminado lleva incorporados 1.5kgs. de una determinada materia prima, MP. El coste de adquisición, ca, de MP es de 11 $/kg., pero el proveedor hace un descuento de 3 $/kg. cuando el lote de pedido es mayor o igual que 50000 kilogramos. Se sabe, además, que el coste unitario diario de posesión, cp, supone un 1% del de adquisición y que el coste de emisión de un pedido, ce, es de 10000 $. Sabiendo que la empresa emplea un modelo de cantidad fija de pedido, que el período de gestión es un mes y que se suponen condiciones de certeza, se desea conocer el lote económico, Q*, que minimiza los costes mensuales de gestión de inventarios, y el valor de éstos.

Problema #16) Un gran distribuidor de equipo de perforación de pozos petroleros ha operado los últimos dos años con políticas EOQ con base

en una tasa costo anual de posesión del inventario del 22 %. Bajo la política EOQ, se ha pedido un producto específico con un Q* = 80 Una evaluación reciente de los costos de posesión del inventario muestra que debido a un incremento en la tasa de interés asociada con los prestamos bancarios, la tasa del costo anual de posesión debería ser del 27% ¿Cuál es la nueva cantidad económica a pedir para el producto?

Problema #1 7 ) Una empresa A consume mensualmente 30 unidades de un producto

P,

que puede fabricar en sus propios talleres a razón de 50 unidades mensuales. Cada vez que

se fabrica P en la empresa A, se gastan $100 para el lanzamiento de la producción. Por otra parte, almacenar en A una unidad de P durante un mes cuesta $0,05. a) Hallar el lote óptimo de fabricación y la repercusión, en el coste de cada unidad de P, de los gastos de lanzamiento y de almacenaje. b) Si un proveedor B ofrece suministrar el producto P en las fechas y cantidades preestablecidas por A. El costo de almacenaje sigue siendo $0,05 por unidad de P almacenada durante un mes, pero el costo de cursar un pedido a B es tan sólo de $10. Hallar el pedido óptimo y la correspondiente repercusión en el coste de cada unidad de P, de los gastos de pedido a B y almacenaje en A. c) Calcular para la política óptima de A hallada en la pregunta anterior, cuál será para el proveedor B, la repercusión en sus propios costes por unidad de P, de los gastos de lanzamiento y almacenaje. Se sabe que el ritmo de producción de P en B es de 100 unidades al mes, que el coste de lanzamiento es de $75 y que almacenar en B una unidad de P durante un mes cuesta $0,1. Dicho cálculo se hará para los casos en que la cantidad de P producida por B en cada lote de fabricación es: a) Igual a la solicitada por A en cada pedido. b) Doble de la solicitada por A en cada pedido. Se supondrá también que, en ambos casos, el lanzamiento se hace en el momento más conveniente.

Problema # 18 ) ELECTROAUTO C.A. adquiere directamente de su proveedor un componente que se utiliza en la manufactura de generadores para automóvil. La operación de producción de generadores de ELECTROAUTO C.A. que funciona a una tasa constante, requerirá de 1000 componentes mensuales durante todo el año (12.000 unidades anualmente). Suponga que los costos de elaborar un pedido son 25 dólares por pedido, el costo unitario es de 2.50 $ por componente y los costos anuales de posesión son 20 % del valor del inventario. ELECTROAUTO C.A., labora 250 días al año y el plazo de entrega es de 5 días. Responda a las siguientes preguntas de políticas (de inventarios de la Empresa:

a. Cual es el EOQ de este componente?

b. ¿Cual es el punto de pedido?

e. ¿Cual es el tiempo del ciclo?

d. Cuales son los costos totales anuales de posición y de pedir, asociados con su EOQ recomendado.

Problema # 19 ) Suponga que ELECTROAUTO, que tiene una demanda anual de 12.000 generadores por año, con un costo de almacenamiento de 0,50 dólares la unidad año y costo de preparación de un pedido por 25 dólares cada pedido, ha decidido operar con una política de inventarios de pedidos pendientes por surtir, que le acarrea un costo anual de 5 dólares la unidad. Determine los siguientes parámetros:

a) Cantidad a pedir a costo mínimo

b) Número máximo de pedidos pendientes por surtir

c) Nivel máximo de inventarios

d) Tiempo del ciclo

e) Costo total anual

P roblema # 20 ) TELE-RECORD es una nueva tienda de especialidades que vende televisores, grabadoras de cinta, juegos de video y otros productos relacionados con la televisión. Una nueva grabadora de video fabricada en Japón, le cuesta a TELE-RECORD unos 600 dólares por

unidad. La tasa del costo anual de posesión del inventario de TELE-RECORD es del 22% del mismo. Los costos de elaborar un pedido se estiman en 70 dólares por pedido.

a.) Si la demanda de la nueva grabadora de videocinta se estima constante a una tasa de 20 unidades por mes, ¿cual es la cantidad recomendada de pedido para la grabadora de cinta?

b) ¿Cuales son los costos estimados anuales del inventario y de realizar un pedido asociado a este producto?

c) ¿Cuántos pedidos se colocaran al año

d) Con 250 días laborables por año. ¿cuál es el tiempo del ciclo de este producto?

Problema #21) Usted como Administrador del Sistema de Inventarios de una Empresa,

considera que los modelos de Inventarios son de importante ayuda para la toma de decisiones y que el modelo de pedidos pendientes por surtir debe evitarse. Sin embargo, debido a la presión de la Gerencia de reducir sus costos, se le ha pedido al Administrador que analice la economía de una política de pedidos pendientes por entregar, para algunos productos que pueden quedar en espera. Un producto especifico tiene una demanda anual de 800 unidades, costo de preparación del pedido de 150 dólares y costo anual de almacenamiento de cada unidad es de 3 dólares y el costo de mantener pedidos pendientes es de 20 dólares la unidad por año. ¿Cuál es la diferencia en el costo total anual entre el modelo EOQ y el de faltante planificado? Si el administrador agrega como restricción la de que no más del 25% de las unidades puedan quedar en la lista de unidades pendientes por surtir y que ninguno de sus clientes deba espera más de 15 días para satisfacer su pedido ¿deberá adoptarse la política de inventarios de pedidos pendientes por surtir, considerando que la operación es continua durante 250 días del año?

Problema # 22 ) La empresa TRANSPORTE S.A., está orgullosa de su programa de capacitación de seis semanas para todos sus nuevos conductores de camiones. Siempre que el tamaño de la clase, sea inferior ó igual 35 choferes, el programa de capacitación de seis semanas, le cuesta a TRANSPORTE S.A. unos 22.000 dólares por lo que se refiere a Instructores, Equipos, Etc. El programa de capacitación de TRANSPORTE S.A. debe darle a la empresa aproximadamente cinco nuevos conductores al mes. Después de finalizar el programa de capacitación, se les paga a los nuevos choferes 1.600 dólares

mensuales pero no trabajan hasta que quede disponible una posición de tiempo completo de chofer. TRANSPORTE S.A., considera los 1.600 dólares mensuales cancelados a cada conductor ocioso como un costo de posesión necesario para mantener esa fuente de nuevos choferes de camiones capacitados disponibles para servicio inmediato. Considerando los nuevos choferes como unidades del tipo de inventario, ¿de que tamaño debería ser la clase de capacitación para minimizar los costos totales anuales de capacitación y de tiempo ocioso de los nuevos choferes? ¿Cuantas clases de capacitación deberá impartir la Empresa cada año? ¿Cuál es el costo total anual asociado con su recomendación?

Problema # 23 ) Una empresa que se dedica a la fabricación de transformados metálicos debe comprar en el exterior una pieza de plástico que incorpora a sus productos, siendo su coste de adquisición de 0.125um/unidad. El consumo diario de dicha pieza es prácticamente constante y asciende a 178 unidades. Cada vez que se hace un pedido, éste tarda en llegar 7 días y se generan unos costes por emisión iguales a 500um. Un estudio realizado sobre los costes, cp, originados por el almacenamiento de las piezas de plástico en la empresas, revela que éstas suponen 1.25um/unidad y año. La empresa no viene practicando ningún método científico de gestión de stocks y parece ser que esto provoca unos gastos demasiado elevados en el departamento de aprovisionamiento. Debido a ello, el gerente solicita del mismo un estudio adecuado para la gestión de las diferentes materias primas y productos de fabricación ajena que son adquiridos por la empresa, entre los cuales se encuentra la pieza de plástico a la que venimos haciendo referencia. Para ellos, y dentro del estudio general encomendado, se desea conocer, para un período , de 360 días laborables:

- El tamaño del lote de pedido, Q*, que minimiza los costes totales de la gestión de inventarios de este producto.

- El número de pedidos a realizar.

- El período de reaprovisionamiento óptimo.

- El punto de pedido.

- El coste total de gestión, CT.

Problema # 24 ) Suponga que usted esta revisando la decisión del tamaño del lote asociado con una operación de producción de 8000 unidades por año, con una demanda del producto de 2000 unidades por año, el costo de efectuar un pedido es de 300 dólares por pedido y el costo de almacenamiento es de 1.60 dólares la unidad por año. Considere además que la practica actual incluye corridas de producción de 500 unidades cada tres meses ¿recomendaría usted cambiar el tamaño del lote de producción actual? ¿porqué si y porqué no? ¿Cuánto se podrá ahorrar al convertir la producción a su recomendación del tamaño del lote de producción?

Problema # 25 ) PUBLICACIONES C.A. produce libros para el mercado infantil cuya demanda anual constante se estima en 7.200 ejemplares. El costo de cada libro infantil es de 14,50 dólares. El costo de posesión se basa en una tasa anual del 18% y los costos de puesta en marcha de la producción es de 150 dólares por cada puesta en marcha de la producción. La imprenta tiene una capacidad de producción de 25.000 libros infantiles por año, con una operación de 250 días al año y plazo de entrega de una corrida de producción de de 15 días. Utilizando el modelo de tamaño de lote de producción determine lo siguiente:

a) Tamaño del lote de producción con costo mínimo

b) Número de corridas de producción al año

c) Tiempo del ciclo

d) Duración de una corrida de producción

e) Nivel máximo de inventario

f) Costo total anual

g) Punto de pedido

Problema # 26 ) COLGATE-PALMOLIVE, fabricante de pastas dentales, utiliza un modelo de tamaño de lote de producción para determinar la cantidad de producción de sus diferentes presentaciones del producto. El producto CREST actualmente se está produciendo en tamaño de lotes de 5.000 unidades, con una corrida de producción que dura 10 días. Debido a la escasez de una materia prima, su proveedor le ha anunciado un incremento en su precio que afectará el costo de producción de la pasta de dientes CREST. Las estimaciones indican que por esa razón, el costo de manufactura de CREST, se incrementa un 23% por unidad. ¿Cuál es el efecto de este incremento en costo sobre el tamaño del lote de producción de CREST?

Problema # 27 ) Una empresa distribuidora de rollos de cables quiere adoptar una política de inventarios que le permita minimizar el costo total esperado. La política a utilizar será la de comprar lotes de artículos utilizando una frecuencia entera óptima.

La demanda de rollos prevista para el período se calcula que será de 400 unidades. Un proveedor ofrece un modelo de ese rollo a un precio unitario de $ 12 cuando la cantidad a comprar sea menor a 19 unidades, $ 10 cuando compre entre 20 y 79 unidades y $ 9.50 cuando compre mas de 79 unidades. El costo administrativo por realizar cada compra se calcula en $ 15. Para averiguar el costo de almacenaje se determino que tener un rollo almacenado en el deposito cuesta un 55% de su precio unitario, este porcentaje incluye seguros, custodia, valor de recuperación (valor de desecho del producto para la empresa, como por ejemplo una venta con descuento) y la tasa de descuento (el costo por tener invertido dinero en artículos almacenados y no por ejemplo en un plazo fijo). Determinar el lote óptimo de compra

Problema # 28 ) La empresa de calzado deportivo ADDIDAS, tiene un modelo que se vende a razón de 500 pares cada tres meses. La política actual de pedidos a fábrica es de pedir 500 pares cada vez que se elabora un pedido a un costo de 30 dólares para elaborar cada pedido. La tasa del costo de posesión del inventario es del 20%. Con la cantidad a pedir igual a 500 pares, ADDIDAS, obtiene el costo más bajo para

cada par de zapatos, es decir 28 dólares el par. Con la tabla de descuentos por volumen de compra anexa, ¿Cuál es la cantidad a pedir con un costo mínimo para los zapatos? ¿Cuáles son los ahorros anuales de su política de inventarios en comparación a la utilizada actualmente por ADDIDAS?

Clase de Descuento Tamaño del pedido Descuento (%) Costo Unitario (US$)

A 0 - 499 0 30,00

B 500 ó más 20 24.00

Problema # 29 ) Una Empresa puede producir un artículo ó comprarlo a un comerciante. Si lo fabrica, a una tasa de 100 unidades por día, le costará 20 dólares cada vez que se preparan las maquinas. Si se lo compra al comerciante le costará 15 dólares cada vez que hace un pedido. El costo de mantener un articulo en existencia ya sea fabricado ó comprado es de 0.02 dólares la unidad por día. El uso que la Empresa hace del artículo se estima en 260.000 unidades al año. Suponiendo que no se permite ningún faltante, ¿Debe la compañía comprar el artículo ó producirlo?

Problema # 3 0 ) Un proveedor les ofrece un producto a descuento, si la demanda anual del producto es de 500 unidades, el costo de preparar un pedido es de 40 dólares y la tasa anual por posesión del inventario es del 20%, ¿basado en la tabla de descuento anexa, que cantidad recomendaría usted pedir?

Clase de Descuento Tamaño del pedido Descuento (%) Costo Unitario (US$)

A 0 - 99 0 10,00

B 100 ó más 3 9.70

Problema # 3 1 ) Una empresa automotriz desea implementar una nueva línea de montaje para su nuevo modelo de lujo, con el fin de disminuir ciertos costos innecesarios que se han estado incurriendo. Luego de realizar los análisis correspondientes, la empresa decidió proceder de la siguiente manera:

Se comenzará con la tarea A, la que durará 7 días. Luego de realizar esta actividad, seguirán las actividades B y D. Por su parte, la tarea F (la que durará 48 horas) se iniciará una vez que se termine con la actividad C, para posteriormente seguir con la tarea H (cuya duración es de 24 horas) siempre y cuando se hayan terminado las tareas E y F. Además, se comenzará con la tarea G al mismo tiempo que empiece C, ocurriendo esto cuando termine la actividad D. Por otro lado, se iniciará la tarea I luego que se termine con la actividad G. Por último, la tarea E tendrá que esperar el término de B para comenzar. Los análisis realizados entregaron los siguientes tiempos de duración para cada tarea:

Actividad B= 3 días

Actividad C= 2 días

Actividad D= 4 días

Actividad E= 2 días

Actividad G= 6 días

Actividad I= 5 días

Se pide:

Construir una Carta Gantt que muestre el análisis descrito.

(a) ¿Cuántos días durará el montaje del modelo de lujo como mínimo?

Problema # 3 2 ) La empresa INELECTRA, que presta asesoría de ingeniería, obtuvo un contrato para el diseño de una pieza mecánica de alta sofisticación. Para realizar este diseño, la empresa se dividió en tres equipos de trabajo. El equipo I tiene a su cargo las actividades A, B y E.

El equipo II por su parte, tiene a su cargo las actividades C y D. El equipo III tiene que estar preocupado de las actividades F y G.

En la etapa de planificación del diseño, los equipos acordaron lo siguiente:

- El equipo I empezará con la tarea A. Una vez terminada ésta, se empezará con la actividad B. Se continuará con la actividad E solamente cuando el equipo II termine con la actividad C. A su vez, el equipo III empezará la actividad G una vez que el equipo I termine con la actividad E.

- El equipo III tendrá que terminar con la actividad F para así iniciar la actividad G. Para iniciar la actividad F, se deberá esperar que se termine con la actividad D.

- El equipo II empezará la actividad C una vez que el equipo I termine con la actividad A. Una vez finalizada la actividad C, el equipo II podrá iniciar la actividad D.

Se pide:

(a) Construya la Carta Gantt con la información dada. ¿ Cuántos días durará todo el proyecto?

(b) Construya la Malla Pert que represente el plan descrito.

(c)¿Qué equipo puede retrasarse en la duración de lo planeado, sin comprometer la duración total del proyecto? ¿Cuántos días puede retrasarse este equipo?

Se entrega la siguiente información a continuación acerca de la duración de las actividades:

Problema #3 3 ) Una Empresa de fibra óptica esta instalando una linea para televisión por cable desde el punto más a la izquierda hasta el punto más a la derecha, determinar el camino óptimo para minimizar el costo del cable cuyo precio es de 250 $ el kilometro siendo las distencias entre los diferentes estaciones de retransmisión los indicados en el diagrama

Equipo Actividades Duración (días)

I A 3

I B 3

I E 3

II C 5

II D 4

III F 3

III G 3

anexo.

Problema #3 4 ) La empresa ENRON desea determinar el máximo flujo de Gas que puede ser transportado a través de su red de tuberías desde Austin (Texas) hasta Denver (Colorado). La red de tuberías y las distancias entre los nodos en Kilómetros es la siguiente:

Problema #3 5 ) La empresa de granos CARGILL, envia por tren sus productos desde San Luis hasta el Puerto de Houston. Durante el Invierno, la capacidad de envio por tren es limitada, por ello, considerando el número de trenes diarios en las distintas redes de ferrocarril indicadas en el diagrama anexo, determinar la cantidad diaria que puede enviar CARGILL por tren, si la capacidad de cada tren es de 300.000 kgs.

Problema #3 6 ) Considere que un proyecto de fabricación de una maquina termoeléctrica tiene las siguientes actividades:

Actividad Predecesora Duración (meses)

ANinguna

5B Ninguna 1

C B 2

D A, C 4

E A 6

F D, E 3

A) Dibuje el diagrama de red de las actividades de este proyecto..

B) Identifique el camino crítico y la duración del proyecto

C) Cual es el mínimo tiempo para finalizar la actividad D sin retardar el proyecto completo.

Problema #37) Un agricultor de Portuguesa, es dueño de un campo en el cual tiene

diversos tipos de siembra características de la zona. El único inconveniente tiene relación con la ubicación de las siembras con la casa de la persona que las cuida, además, de la ubicación entre ellas mismas. Un cuadro resumen de distancias entre las distintas siembras se presenta a continuación:

Casa S1 S2 S3 S4 S5 S6

Casa - 8 3 6 - - -

S1 8 - 7 3 5 - -

S2 3 7 - 4 - 6 -

S3 6 3 4 - 6 4 1

S4 - 5 - 6 - 3 3

S5 - - 6 4 3 - 2

S6 - - - 1 3 2 -

La persona que cuida las siembras realiza dos labores específicas: abonar y regar la tierra. Para la primera, cada siembra necesita de un saco de abono y dispone de una carretilla para transportarlo desde su casa a la siembra respectiva, mientras que la segunda labor la realiza mediante una manguera que está conectada a una llave en su casa.

A partir de la información anterior, se le pide responder las siguientes preguntas:

1. Determine la distancia total que deberá caminar el cuidador para que todas las siembras dispongan de su respectivo saco de abono. Aplique un modelo de grafos y justifique su respuesta.

2. Suponga que ahora el dueño del campo compró una carretilla con capacidad para el traslado de cuatro sacos de abono al mismo tiempo. Determine la distancia total que caminará con esta nueva carretilla.

3. Gracias al programa Tierra Adentro, el dueño del campo obtuvo un premio que consiste en la instalación de una red de cañerías para el riego de las siembras. Si la llave de paso está ubicada en la casa del cuidador, determine la mínima cantidad de cañerías a instalar para asegurar riego a todas las siembras. Aplique un modelo de grafos y justifique su respuesta.

Problema #3 8 ) La ventanilla de un banco realiza las transacciones en un tiempo medio de 2 minutos. Los clientes llegan con una tasa media de 20 clientes a la hora. Si se supone que las llegadas siguen un proceso de Poisson y el tiempo de servicio es exponencial, determinar:

(a) Porcentaje de tiempo ocioso del cajero.(b) Tiempo medio de estancia de los clientes en la cola.(c) Fracción de clientes que deben esperar en cola. Problema #3 9 ) Una tienda de alimentación es atendida por una persona. Aparentemente, el patrón de llegadas de clientes durante los sábados se comporta siguiendo un proceso de Poisson con una tasa de llegada de 10 personas por hora. A los clientes se les atiende siguiendo un orden tipo FIFO y debido al prestigio de la tienda, una vez que llegan están dispuestos a esperar el servicio. Se estima que el tiempo que se tarda en atender a un cliente se distribuye exponencialmente, con un tiempo medio de 4 minutos. Determinar:(a) La probabilidad de que haya línea de espera.(b) La longitud media de la línea de espera.(c) El tiempo medio que un cliente permanece en cola Problema # 40 ) INPARQUES ha decidido limitar el acceso al parque del ESTE. No se permitirán vehículos particulares y se utilizarán únicamente minibases conducidos por guardias forestales. Las carreteras existentes (de una “única dirección” y siendo O la estación de entrada, y A, B, C, D, E, los lugares de interés) y sus distancias son las siguientes: O A = 2 O B = 5 O C = 4 A B = 2 C B = 1A D = 8 B D = 4 C D = 3 C E = 4 E D = 1 (a) Encontrar los caminos más cortos de la entrada al resto de las estaciones.

(b) Si se desea comunicar con terminales de ordenador las estaciones, tendiendo líneas que sigan la carretera, resolver el problema de minimizar el número de kilómetros de línea tendida.

C ADENAS DE M ARKOV

INTRODUCCIÓN

El análisis de Markov tuvo su origen en los estudios de A.A.Markov(1906-1907) sobre la secuencia de los experimentos conectados en cadena y los intentos de descubrir matemáticamente los fenómenos físicos conocidos como movimiento browiano. La teoría general de los procesos de Markov se desarrollo en las décadas de 1930 y 1940 por A.N.Kolmagoron, W.Feller, W.Doeblin, P.Levy, J.L.Doob y otros.

El análisis de Markov es una forma de analizar el movimiento actual de alguna variable, a fin de pronosticar un movimiento futuro de la misma.

ANÁLISIS DE MARKOV

Afin de ilustrar el proceso de Markov presentamos un problema en el que los estados de resultados de actividades son marcas, y las probabilidades de transición expresan la probabilidad de que los consumidores vayan de una marca a otra. Supongamos que la muestra inicial de consumidores se compone de 1 000 participantes distribuidos entre cuatro marcas(A, B, C, D). Una suposición adicional es que la muestra representa a todo el grupo.

En la siguiente tabla la mayor parte de los clientes que compraron inicialmente la marca A, siguieron con ella en el segundo periodo. No obstante la marca A ganó 50 clientes y perdió 45 con otras marcas.

Marca Periodo 1 Ganancias Perdidas Periodo 2

Numero de Clientes

Numero de Clientes

A 220 50 45 225

B 300 60 70 290

C 230 25 25 230

D 250 40 35 255

1 000 175 175 1 000

Esta tabla no muestra la historia completa, sino que necesita un análisis detallado con respecto a la proporción de ganancias y perdidas netas entre las cuatro marcas. Es necesario calcular las probabilidades de transición para las cuatro marcas. Las probabilidades de transición se definen como la probabilidad de que determinada marca, conserve sus clientes. Para determinar lo anterior dividimos se divide el numero de clientes retenidos entre en numero de clientes en el periodo inicial, por ejemplo para la marca A (220- 45=175) se divide 175/220 lo que nos da 0.796, al igual para las otras marcas, obteniendo 0.767(B),0.891(C),0.860(D).

Para aquellos clientes que cambiaron de marcas , es necesario mostrar las perdidas y ganancias entre las marcas a fin de completar las matriz de probabilidades de transición. De acuerdo con los datos desarrollados, el paso siguiente consiste en convertir el cambio de marcas de los clientes de modo que todas las perdidas y ganancias tomen forma de probabilidades de transición, obteniendo la matriz de probabilidad de transición.

La siguiente tabla nos muestra la matriz de transición final.

A B C D

A 175/220=0.796 40/300=0.133 0/230=0 10/250=0.040

B 20/220=0.091 230/300=0.767 25/230=0.109 15/250=0.060

C 10/220=0.046 5/300=0.017 205/230=0.891 10/250=0.040

D 15/220=0.067 25/300=0.083 0/230=0 215/250=0.860

La lectura de esta información sería la siguiente:

La marca A retiene 0.796 de sus clientes, mientras que gana 0.133 de los clientes de B, 0.40 de los clientes de D y 0 de los clientes de C.

La administración de mercadotecnia puede tener un gran ventaja de toda esta información que nos pueda arrojar el desarrollo de técnicas como estas, ayudando a la promoción de algunos productos que los necesiten para tener una mejor aceptación entre los consumidores.

Aspectos Generales de la Programación Lineal

En los siglos XVII y XVIII, grandes matemáticos como Newton, Leibnitz, Bernouilli y, sobre todo, Lagrange, que tanto habían contribuido al desarrollo del cálculo infinitesimal, se ocuparon de

obtener máximos y mínimos condicionados de determinadas funciones.

Posteriormente el matemático fránces Jean Baptiste-Joseph Fourier (1768-1830) fue el primero en intuir, aunque de forma imprecisa, los métodos de lo que actualmente llamamos programación lineal y la potencialidad que de ellos se deriva.

Si exceptuamos al matemático Gaspar Monge (1746-1818), quien en 1776 se interesó por problemas de este género, debemos remontarnos al año 1939 para encontrar nuevos estudios relacionados con los métodos de la actual programación lineal. En este año, el matemático ruso Leonodas Vitalyevich Kantarovitch publica una extensa monografía titulada Métodos matemáticos de organización y planificación de la producción en la que por primera vez se hace corresponder a una extensa gama de problemas una teoría matemática precisa y bien definida llamada, hoy en día, programación lineal .

En 1941-1942 se formula por primera vez el problema de transporte, estudiado independientemente por Koopmans y Kantarovitch, razón por la cual se suele conocer con el nombre de problema de Koopmans-Kantarovitch.

Tres años más tarde, G. Stigler plantea otro problema particular conocido con el nombre de régimen alimenticio optimal.

En estos años posteriores a la Segunda Guerra Mundial, en Estados Unidos se asumió que la eficaz coordinación de todas las energías y recursos de la nación era un problema de tal complejidad, que su resolución y simplificación pasaba necesariamente por los modelos de optimización que resuelve la programación lineal.

Paralelamente a los hechos descritos se desarrollan las técnicas de computación y los ordenadores, instrumentos que harían posible la resolución y simplificación de los problemas que se estaban gestando.

En 1947, G.B. Dantzig formula, en términos matemáticos muy precisos, el enunciado estándar al que cabe reducir todo problema de programación lineal. Dantzig, junto con una serie de investigadores del United States Departament of Air Force, formarían el grupo que dio en denominarse SCOOP (Scientific Computation of Optimum Programs).

Una de las primeras aplicaciones de los estudios del grupo SCOOP fue el puente aéreo de Berlín. Se continuó con infinidad de aplicaciones de tipo preferentemente militar.

Hacia 1950 se constituyen, fundamentalmente en Estados Unidos, distintos grupos de estudio para ir desarrollando las diferentes ramificaciones de la programación lineal. Cabe citar, entre otros, Rand Corporation, con Dantzig, Orchard-Hays, Ford, Fulkerson y Gale, el departamento de Matemáticas de la Universidad de Princenton, con Tucker y Kuhn, así como la Escuela Graduada de Administración Industrial, dependiente del Carnegie Institute of Technology , con Charnes y Cooper.

Respecto al método del simplex, que estudiaremos después, señalaremos que su estudio comenzó en el año 1951 y fue desarrollado por Dantzig en el United States Bureau of Standards SEAC COMPUTER, ayudándose de

varios modelos de ordenador de la firma IBM.

Los fundamentos matemáticos de la programación lineal se deben al matemático norteamericano de origen húngaro Janos von Neuman (1903-1957), quie en 1928 publicó su famoso trabajo Teoría de Juegos. En 1947 conjetura la equivalencia de los problemas de programación lineal y la teoría de matrices desarrollada en sus trabajos. La influencia de este respetado matemático, discípulo de David Hilbert en Gotinga y, desde 1930, catedrático de la Universidad de Princenton de Estados Unidos, hace que otros investigadores se interesaran paulatinamente por el desarrollo riguroso de esta disciplina.

En 1858 se aplicaron los métodos de la programación lineal a un problema concreto: el cálculo del plan óptimo de transporte de arena de construcción a las obras de edificación de la ciudad de Moscú. En este problema había 10 puntos de partida y 230 de llegada. El plan óptimo de transporte, calculado con el ordenador Strena en 10 días del mes de junio, rebajó un 11% los gastos respecto a los costes previstos.

Se ha estimado, de una manera general, que si un país subdesarrollado utilizase los métodos de la programación lineal, su producto interior bruto (PIB) aumentaría entre un 10 y un 15% en tan sólo un año.

La programación lineal hace historia: El puente aéreo de Berlín

En 1946 comienza el largo período de la guerra fría entre la antigua Unión Soviética (URSS) y las potencias aliadas (principalmente , Inglaterra y Estados Unidos). Uno de los episodios más llamativos de esa guerra fría se produjo a mediados de 1948, cuando la URSS bloqueó las comunicaciones terrestres desde las zonas alemanas en poder de los

http://www.investigacion-operaciones.com/Aspectos_Generales_PL.htm#puente

http://www.investigacion-operaciones.com/Aspectos_Generales_PL.htm#puente

aliados con la ciudad de Berlín, iniciando el bloqueo de Berlín. A los aliados se les plantearon dos posiblidades: o romper el bloqueo terrestre por la fuerza, o llegar a Berlín por el aire. Se adoptó la decisión de programar una demostración técnica del poder aéreo norteamericano; a tal efecto, se organizó un gigantesco puente aéreo para abastecer la ciudad: en diciembre de 1948 se estaban transportando 4500 toneladas diarias; en marzo de 1949, se llegó a las 8000 toneladas, tanto como se transportaba por carretera y ferrocarril antes del corte de las comunicaciones. En la planificación de los suministros se utilizó la programación lineal. (El 12 de mayo de 1949, los soviéticos levantaron el bloqueo)

¿Qué es la programación lineal ?

En infinidad de aplicaciones de la industria, la economía, la estrategia militar, etc.. se presentan situaciones en las que se exige maximizar o minimizar algunas fucniones que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones.

Para hacernos una idea más clara de estos supuestos, veamos dos ejemplos:

Ejemplo 1: Problema de máximos.En una granja se preparan dos clases de fertilizantes, P y Q, mezclando dos productos A y B. Un saco de P contiene 8 kg de A y 2 de B, y un saco de Q contiene 10 kg de A y 5 de B. Cada saco de P se vende a 300 Bs. y cada saco de Q a 800 Bs. Si en la granja hay almacenados 80 kg de A y 25 de B, ¿cuántos sacos de cada tipo de pienso deben preparar para obtener los máximos ingresos?

Ejemplo 2: Problema de mínimos.Una campaña para promocionar una marca de productos lácteos se basa en el reparto gratuito de yogures con sabor a limón o a fresa. Se decide repartir al menos 30000 yogures.Cada yogur de limón necesita para su elaboración 0.5 gramos de un producto de fermentación y cada yogur de fresa necesita 0.2 gramos de este mismo producto. Se dispone de 9 kilogramos de este producto para fermentación.El costo de producción de un yogur de limón es de 30 Bs. y 20 Bs. uno de fresa.

En los dos ejemplos descritos está claro que tanto la cantidad que deseamos maximizar como la cantidad que deseamos minimizar podemos expresarlas en forma de ecuaciones lineales. Por otra parte, las restricciones que imponen las condiciones de ambos problemas se pueden expresar en forma de inecuaciones lineales.

Tratemos de plantear en términos matemáticos los dos ejemplos anteriores:

1) Si designamos por x al número de sacos de fertilizante de clase P y por y el número de sacos de fertilizante de clase Q que se han de vender, la función : Z = 300x + 800y representará la cantidad de bolívares obtenidas por la venta de los sacos, y por tanto es la que debemos maximizar.Podemos hacer un pequeño cuadro que nos ayude a obtener las restricciones:

Nº kg de A kg de B

P x 8x 2x

Q y 10y 5y

80 25

Por otra parte, las variables x e y, lógicamente, han de ser no negativas, por tanto : x 0, y 0Conjunto de restricciones:

8x + 10y 80

2x + 5y 25

x 0, y 0

2) Si representamos por x el número de yogures de limón e y al número de yogures de fresa, se tiene que la función de costos es Z = 30x + 20y.Por otra parte, las condiciones del problema imponen las siguientes restricciones:

De número : x + y 80 De fermentación: 0.5x + 0.2y 9000

Las variables x e y han de ser, lógicamente, no negativas; es decir: x 0, y 0

Conjunto de restricciones:

x + y 80

0.5x + 0.2y 9000

x 0, y 0

En definitiva:

Se llama programación lineal al conjunto de técnicas matemáticas que pretenden resolver la situación siguiente:Optimizar (maximizar o minimizar) una función objetivo, función lineal de varias variables, sujeta a:una serie de restricciones, expresadas por inecuaciones lineales.

Un problema de programación lineal en dos variables, tiene la siguiente formulación estándar:

puediendo cambiarse maximizar por minimizar, y el sentido de las desigualdades.

En un problema de programación lineal intervienen:

La función f(x,y) = ax + by + c llamada función objetivo y que es necesario optimizar. En esa expresión x e y son las variables de decisión, mientras que a, b y c son constantes.

Las restricciones que deben ser inecuaciones lineales. Su número depende del problema en cuestión. El carácter de desigualdad viene impuesto por las limitaciones, disponibilidades o necesidades, que son: inferiores a ... ( menores: < o ); como mínimo de ... (mayores: > o ) . Tanto si se trata de maximizar como de minimizar, las desigualdades pueden darse en cualquiera de los dos sentidos.

Al conjunto de valores de x e y que verifican todas y cada una de las restricciones se lo denomina conjunto (o región ) factible. Todo punto de ese conjunto puede ser solución del problema; todo punto no perteneciente a ese conjunto no puede ser solución. En el apartado siguiente veremos como se determina la región factible.

La solución óptima del problema será un par de valores (x0, y0) del conjunto factible que haga que f(x,y) tome el valor máximo o mínimo.

En ocasiones utilizaremos las siglas PPL para indicar problema de programación lineal.

Determinación de la región factible La solución de un problema de programación lineal, en el supuesto de que exista, debe estar en la región determinada por las distintas desigualdades. Esta recibe el nombre de región factible, y puede estar o no acotada.

Región factible acotada Región factible no acotada

La región factible incluye o no los lados y los vértices, según que las desigualdades sean en sentido amplio ( o ) o en sentido estricto (< o >).

Si la región factible está acotada, su representación gráfica es un polígono convexo con un número de lados menor o igual que el número de restricciones.

El procedimiento para determinar la región factible es el siguiente:

1) Se resuelve cada inecuación por separado, es decir, se encuentra el semiplano de soluciones de cada una de las inecuaciones.

Se dibuja la recta asociada a la inecuación. Esta recta divide al plano en dos regiones o semiplanos

Para averiguar cuál es la región válida, el procedimiento práctico consiste en elegir un punto, por ejemplo, el (0,0) si la recta no pasa por el origen, y comprobar si las coordenadas satisfacen o no la inecuación. Si lo hacen, la región en la que está ese punto es aquella cuyos puntos verifican la inecuación; en caso contrario, la región válida es la otra.

2) La región factible está formada por la intersección o región común de las soluciones de todas las inecuaciones.

Como sucede con los sistemas de ecuaciones lineales, los sistemas de inecuaciones lineales pueden presentar varias opciones respecto a sus soluciones: puede no existir solución, en el caso de que exista el conjunto solución puede ser acotado o no.

Veámoslo con un ejemplo:

Dibuja la región factible asociada a las restricciones:

x + y 4

y 4

y x

Las rectas asociadas son : r : x + y = 4 ; s : y = 4 , t: y = x

Elegimos el punto O(0,0), que se encuentra en el semiplano situado por debajo de la recta. Introduciendo las coordenadas (0,0) en la inecuación x + y 4, vemos que no la satisface: 0 + 0 = 0 < 4 . Por tanto, el conjunto de soluciones de la inecuación es el semiplano situado por encima de la recta r : x + y = 4 .

Procedemos como en el paso anterior. Las coordenadas (0,0) satisfacen la inecuación y 4 ( 0 4) . Por tanto, el conjunto de soluciones de la inecuación es el semiplano que incluye al punto O.

La recta t asociada a la restricción pasa por el origen, lo cual significa que si probásemos con el punto O(0,0) no llegaríamos a ninguna conclusión. Elegimos el punto (1,0) y vemos que no satisface la inecuación y x ( y= 0 < 1 = x ). Por tanto, el conjunto solución de esta inecuación es el semiplano determinado por la

La región factible está formada por los puntos que cumplen las tres restricciones, es decir, se encuentran en los tres semiplanos anteriores.

recta t que no incluye al punto (1,0).

Método gráfico o Método de las rectas de nivel

Las rectas de nivel dan los puntos del plano en los que la función objetivo toma el mismo valor.

Si la función objetivo es f(x,y) = ax + by + c, la ecuación de las rectas de nivel es de la forma:

ax + by + c = 0 ax + by = k

Variando k (o p) se obtienen distintos niveles para esas rectas y, en consecuencia, distintos valores para f(x,y).

En un problema todas las rectas de nivel son paralelas, pues los coeficientes a y b de la recta ax + by = k son los que determinan su pendiente. Por tanto, si k1 es distinto de k2 , las rectas ax + by = k1 y ax + by = k2 son paralelas. Luego, trazada una cualquiera de esas rectas, las demás de obtienen por desplazamientos paralelos a ella.

Si lo que se pretende es resolver un problema de programación lineal, los únicos puntos que interesan son los de la región factible, y las únicas rectas de nivel que importan son aquellas que están en contacto con dicha región. Como el nivel aumenta (o disminuye) desplazando las rectas, el máximo (o el mínimo) de f(x,y) se alcanzará en el último (o en el primer) punto de contacto de esas rectas con la región factible.

Veamos ahora como se aplica todo esto a la resolución de un problema de programación lineal :

Maximizar Z = f(x,y) = x + y

sujeto a: 0 x 4

0 y 4

y x /2

1) Representamos la región factible:

La recta s : x = 4 pasa por el punto (4,0) y es paralela al eje Y. Las soluciones de 0 x 4 son los puntos entre el eje Y y la recta x = 4

La recta r : y = 4 pasa por el punto (0,4) y es paralela al eje X. Las soluciones de 0 y 4 son los puntos entre el eje X y la recta y = 4

La recta t : y = x/2 pasa por los puntos (0,0) y (2,1) . Las soluciones de y x /2 son los puntos de su izquierda.

Resolviendo los sistemas correspondientes calculamos los vértices de la región factible:

{ y = x/2 , x = 0 } nos da el vértice O(0,0) { x = 4, y = x/2 } nos da el vértice A(4,2)

{ x = 4 , y = 4} nos da el vértice B(4,4) { y = 4 , x = 0 } nos da el vértice C(0,4)

2) Representamos las rectas de nivel :

En nuestro caso son rectas de la forma x + y = k . Inicialmente representamos Z = x + y = 0 . Trasladándola hacia la derecha, obtenemos las rectas : x + y = 2, x + y = 4, x + y = 8 , es decir aumenta el nivel.

3) Obtenemos la solución óptima:

Se obtiene en el punto de la región factible que hace máximo k. En nuestro caso esto ocurre en el punto B; es el último punto de contacto de esas rectas con la región factible , para el que k = 8.

Si hay dos vértices, P y Q, que se encuentran en la misma recta de nivel ,de ecuación ax + by = k .Es evidente que todos los puntos del segmento PQ son de esa recta; por tanto, en todos ellos f(x,y) vale k. Así pues, la solución óptima es cualquier punto de esa recta; en particular los vértices P y Q.

Método analítico o Método de los vértices

El siguiente resultado, denominado teorema fundamental de la programación lineal, nos permite conocer otro método de solucionar un programa con dos variables.

En un programa lineal con dos variables, si existe una solución única que optimice la función objetivo, ésta se encuentra en un punto extremo (vértice) de la región factible acotada, nunca en el interior de dicha región.

Si la función objetivo toma el mismo valor óptimo en dos vértices, también toma idéntico valor en los puntos del segmento que determinan.

En el caso de que la región factible no es acotada, la función lineal objetivo no alcanza necesariamente un valor óptimo concreto, pero, si lo hace, éste se encuentra en uno de los vértices de la región

La evaluación de la función objetivo en los vértices de la región factible nos va a permitir encontrar el valor óptimo (máximo o mínimo) en alguno de ellos.

Veámoslo con un ejemplo:

Maximizar Z = f(x,y) = 3x + 8y

sujeto a: 4x + 5y 40

2x + 5y 30

x 0 , y 0

1) Hallar los puntos de corte de las rectas asociadas a las restricciones:

Calculamos las soluciones de cada uno de los seis sistemas de dos ecuaciones con dos incógnitas que se pueden formar con las cuatro restricciones:

{ 4x + 5y = 40 , 2x + 5y = 30}. Solución A(5,4) { 4x + 5y = 40 , x = 0 } Solución:B (0,8)

{ 4x + 5y = 40 , y = 0}. Solución: C(10,0) { 2x + 5y = 30 , x = 0} Solución: D(0,6)

{ 2x + 5y = 30 , y = 0}. Solución : E(15,0) { x = 0, y = 0} Solución: O(0,0)

2) Determinar los vértices de la región factible:

Los vértices de la región factible son aquellos puntos que cumplen todas las restricciones.

Si sustituimos los puntos en cada una de las desigualdades tenemos que:

B no cumple la segunda restricción 2x + 5y 30 , ya que 2·0 + 5·8 = 40 . Por tanto, el punto B no es un vértice de la región factible.

E no cumple la primera restricción 4x + 5y 40 , ya que 4·15 + 5·0 = 60 . Por tanto, el punto E no es un vértice de la región factible.

Los puntos A, C, D y O verifican todas las desigualdades, son los vértices de la región factible.

3) Calcular los valores de la función objetivo en los vértices:

f(A) = f(5,4) = 3·5 + 8·4 = 47 f(C) = f(10,0) = 3·10 + 8· 0 = 30

f(D) = f(0,6) = 3·0 + 8·6 = 48 f(O) = f(0,0) = 3·0 + 8·0 = 0

La solución óptima corresponde al vértice para el que la función objetivo toma el valor máximo. En este caso es el vértice D(0,6).

Este método es el menos utilizado de los tres que veremos

Esquema práctico

Los problemas de programación lineal pueden presentarse en la forma estándar, dando la función objetivo y las restricciones, o bien plantearlos mediante un enunciado. Si éste es el caso, puede seguirse el camino que indicamos a continuación, ejemplificado con el siguiente problema:

En un almacén se guarda aceite de girasol y de oliva. Para atender a los clientes se han de tener almacenados un mínimo de 20 bidones de aceite de girasol y 40 de aceite de oliva y, además, el número de bidones de aceite de oliva no debe ser inferior a la mitad del número de bidones de aceite de girasol. La capacidad total del almacén es de 150 bidones. Sabiendo que el gasto de almacenaje es el mismo para los dos tipos de aceite (1 unidad monetaria) . ¿Cuántos bidones de cada tipo habrá que almacenar para que el gasto sea máximo?

Obs: Puede parecer algo absurdo maximizar los gastos , pero se ha enunciado de esta forma para que el ejemplo sea lo más completo posible

Paso 1º: Leer detenidamente el enunciado: determinar el objetivo, definir las variables y escribir la función objetivo.

El objetivo es: halla cuántos bidones de cada tipo hay que almacenar para maximizar los gastos

Suponemos que tal objetivo se consigue almacenado x bidones de aceite de girasol e y de aceite de oliva

Cómo cada bidón de aceite de girasol cuesta almacenarlo 1 unidad monetaria y lo mismo para uno de aceite, los gastos serán x + y

Luego, la función objetivo es:

Maximizar la función Z = f(x,y) = x + y

Paso 2º: Reordenar los datos del problema y a partir de las cantidades decididas, x e y, escribir el sistema de inecuaciones que determinan las restricciones.

Un mínimo de 20 bidones de aceite de girasol: x 20 Un mínimo de 40 bidones de aceite de oliva: y 40

El número de bidones de aceite de oliva no debe ser inferior a la mitad del número de bidones de aceite de girasol: y x/2

La capacidad total del almacén es de 150 bidones: x + y 150

Además, los números de bidones deben ser cantidades positivas: x 0 ; y 0

Obs.: Como veremos en ejemplos posteriores en algunas ocasiones puede interesar utilizar una tabla para recopilar toda la información y hacer los dos primeros apartados

Paso 3º: Expresar el problema en la forma estándar.

Siguiendo con el ejemplo, sería:

Maximizar: Z = f(x,y) = x + ysujeto a: x + y 150 y x/2 x 20 ; y 40

Aquí termina el planteamiento del problema. Para su resolución hay que continuar con :

Paso 4º: Representar gráficamente las restricciones y marcar claramente la región factible.

Para las restricciones anteriores debemos representar las rectas: x + y = 150 , y = x/2 , x = 20 e y = 40, obteniéndose la región factible que en la figura se encuentra coloreada.

Paso 5º: Hallar las coordenadas de los vértices del polígono obtenido.

Resolviendo los sistemas : { x = 20, y = 40 } , { y = x/2 , y = 40 } , { y = x/2 , x + y = 150} , { x + y = 150, x = 20}; se obtienen los vértices: A(20,40) , B(80,40) , C(100, 50) , D(20,130)

Paso 6º: Sustituir las coordenadas de esos puntos en la función objetivo y hallar el valor máximo o mínimo.

Sustituyendo en f(x,y) = x + y, se tiene:

f(20,40) = 60 , f(80,40) = 120 , f(100, 50) = 150 , f(20,130) = 150

Como el valor máximo se obtiene en los puntos C y D, puede optarse por cualquiera de los dos, o por cualquier punto perteneciente al segmento que los une. Así, por ejemplo, se obtendría el mismo gasto con 40 bidones de aceite girasol y 110 bidones de aceite de oliva; o 90 y 60 respectivamente.

Paso 7º: También es conveniente representar las rectas de nivel para comprobar que la solución gráfica coincide con la encontrada. Esta conveniencia se convierte en necesidad cunado la región factible es no acotada.

En nuestro caso, puede comprobarse que las rectas de nivel tienen la misma pendiente que la

recta límite de la restricción x + y 150 ; por tanto, hay múltiples soluciones.

Paso 8º: Por último, como en la resolución de todo problema es necesario criticar la solución: cerciorarse de que la solución hallada es lógica y correcta.

En este ejemplo, no todos los puntos del segmento CD son soluciones válidas, ya que no podemos admitir valores de x e y no enteros , como ocurriría en el punto (90.5,59.5) .

Obs.: Si un problema en la forma estándar no indica que se debe realizar por el método analítico o gráfico , seguiremos para su resolución los pasos del 4º al 8º

Tipos de soluciones

Los programas lineales con dos variables suelen clasificarse atendiendo al tipo de solución que presentan. Éstos pueden ser:

Factibles Si existe el conjunto de soluciones o valores que satisfacen las restricciones. A su vez, pueden ser:

Con solución única

En una urbanización se van a construir casas de dos tipos: A y B. La empresa constructora dispone para ello de un máximo de 1800 millones de pesetas, siendo el coste de cada tipo de casa de 30 y 20 millones, respectivamente. El Ayuntamiento exige que el número total de casas no sea superior a 80.Sabiendo que el beneficio obtenido por la venta de una casa de tipo A es 4 millones y de 3 millones por una de tipo B, ¿cuántas casas deben construirse de cada tipo para obtener el máximo beneficio?

Variables: x = nº de casas tipo A ; y = nº de casas tipo B

Función objetivo: Maximizar Z = f(x,y) = 4x + 3y

Conjunto de restricciones: El coste total 30x + 20y 1800 . El Ayuntamiento impone x + y 80 . De no negatividad: x 0 , y 0.

Tiene por región factible la región coloreada.Si hallamos los valores de la función objetivo en cada uno de los vértices :f(O) = f(0,0) = 0 ; f(C)=f(60,0) = 240 ;f(D) = f(20,60) = 260 ; f(E) = f(0,80) = 240La solución es única, y corresponde al vértice para el que la función objetivo toma el valor máximo. En este caso es el vértice D(20,60). Por tanto se deben construir 20 casas de tipo A y 60 de tipo B con un coste de 260 millones de pesetas.

Con solución múltiple

Si existe más de una solución.......................................................................................

Maximizar la función Z = f(x,y) = 4x + 2y sujeta a las restricciones 2x + y 4 , x - y 1 , x 0 , y 0.

Los valores de la fucnión objetivo en cada uno de los vértices son:f(O)=f(0,0) = 0 , f(A) = f(1,0) = 4 ; f(B)=f(5/3,2/3) = 8 , f(C) = f(0,4) = 8La función objetivo alcanza el valor máximo en los vértices B y C, por tanto, en todos los puntos del segmento BC.Hay infinitas soluciones, solución múltiple, que corresponden a los puntos del segmento situado entre dos vértices de la región factible.En estos casos, como ya vimos en el capítulo anterior, la función objetivo es paralela a una de las restricciones.

Con solución no acotada

Cuando no existe límite para la función objetivo

Maximizar la función Z = f(x,y) = x + y sujeta a las restricciones y 2x , y x/2 .

Tiene por región factible la zona coloreada que aparece en la figura, que es una región no acotada.La función crece indefinidamente para valores crecientes de x e y.En este caso no existe un valor extremo para la función objetivo, por lo que puede decirse que el problema carece de solución.Para que suceda esta situación la región factible debe estar no acotada.

No factibles

Cuando no existe el conjunto de soluciones que cumplen las restricciones, es decir, las restricciones son inconsistentes.

Maximizar la función Z = f(x,y) = 3x + 8y sujeta a las restricciones x + y 6 , x + y 2 , x 0 , y 0.No existe la región factible, ya que las zonas coloreadas que aparecen en la figura son únicamente soluciones de alguna de las inecuaciones .Por tanto, el conjunto de soluciones del sistema de desigualdades no determina ninguna región factible.Este tipo de problemas carece de solución.

Método del SimplexEs un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.

El método del simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.

El método del simplex fue creado en 1947 por el matemático George Dantzig .

El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables.

El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones

lineales constituyen la base del método simplex.

Vamos a resolver mediante el método del simplex el siguiente problema:

Maximizar Z= f(x,y)= 3x + 2y

sujeto a: 2x + y 18

2x + 3y 42

3x + y 24

x 0 , y 0

http://www.investigacion-operaciones.com/Aspectos_Generales_PL.htm#geo

http://www.investigacion-operaciones.com/Aspectos_Generales_PL.htm#geo

Se consideran las siguientes fases:

1. Convertir las desigualdades en igualdades

Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:

2x + y + h = 182x + 3y + s = 423x +y + d = 24

2. Igualar la función objetivo a cero

- 3x - 2y + Z = 0

3. Escribir la tabla inicial simplex

En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo:

Tabla I . Iteración nº 1 Base Variable de decisión Variable de holgura Valores solución

x y h s d h 2 1 1 0 0 18

s 2 3 0 1 0 42

d 3 1 0 0 1 24

Z -3 -2 0 0 0 0

4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base

A. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto). En nuestro caso, la variable x de coeficiente - 3.

Si existiesen dos o más coeficientes iguales que cumplan la condición anterior, entonces se elige uno cualquiera de ellos.

Si en la última fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la última fila no haya elementos negativos.

La columna de la variable que entra en la base se llama columna pivote (En color verde).

B. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero. En nuestro caso: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]

Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir.

El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya 8 es el menor, indica la fila de la variable de holgura que sale de la base, d. Esta fila se llama fila pivote (En colorverde).

Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables

correspondientes pueden salir de la base.

C. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional, 3.

5. Encontrar los coeficientes de la nueva tabla.

Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de la fila d por el pivote operacional, 3, que es el que hay que convertir en 1.

A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la

función objetivo Z.

También se puede hacer utilizando el siguiente esquema:

Fila del pivote:

Nueva fila del pivote= (Vieja fila del pivote) : (Pivote)

Resto de las filas:

Nueva fila= (Vieja fila) - (Coeficiente de la vieja fila en la columna de la variable entrante) X (Nueva fila del pivote)

Veámoslo con un ejemplo una vez calculada la fila del pivote (fila de x en la Tabla II):

Vieja fila de s 2 3 0 1 0 42 - - - - - -Coeficiente 2 2 2 2 2 2 x x x x x xNueva fila pivote 1 1/3 0 0 1/3 8 = = = = = =

Nueva fila de s 0 7/3 0 1 -2/3 26

Tabla II . Iteración nº 2Base Variable de decisión Variable de holgura Valores solución

x y h s d h 0 1/3 1 0 -2/3 2

s 0 7/3 0 1 -2/3 26

x 1 1/3 0 0 1/3 8

Z 0 -1 0 0 1 24

Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:

A. La variable que entra en la base es y, por ser la variable que corresponde al coeficiente -1

B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:

2:1/3 [=6] , 26:7/3 [=78/7] y 8:1/3 [=8] y como el menor cociente positivo es 6, tenemos que la variable de holgura que sale es h.

C. El elemento pivote, que ahora hay que hacer 1, es 1/3.

Operando de forma análoga a la anterior obtenemos la tabla:

Tabla III . Iteración nº 3Base Variable de decisión Variable de holgura Valores solución

x y h s d y 0 1 3 0 -2 6

s 0 0 -7 0 4 12

x 1 0 -1 0 1 6

Z 0 0 3 0 -1 30

Como en los elementos de la última fila hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:

A. La variable que entra en la base es d, por ser la variable que corresponde al coeficiente -1

B. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote:

6/(-2) [=-3] , 12/4 [=3], y 6:1 [=6] y como el menor cociente positivo es 3, tenemos que la variable de holgura que sale es s.

C. El elemento pivote, que ahora hay que hacer 1, es 4.

Obtenemos la tabla:

Tabla IV . Final del procesoBase Variable de decisión Variable de holgura Valores solución

x y h s d y 0 1 -1/2 0 0 12

d 0 0 -7/4 0 1 3

x 1 0 -3/4 0 0 3

Z 0 0 5/4 0 0 33

Como todos los coeficientes de la fila de la función objetivo son positivos, hemos llegado a la solución óptima.

Los solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. En la misma columna se puede observar el vértice donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: D(3,12)

* Si en el problema de maximizar apareciesen como restricciones inecuaciones de la forma: ax + by c; multiplicándolas por - 1 se transforman en inecuaciones de la forma - ax - by - c y

estamos en el caso anterior* Si en lugar de maximizar se trata de un problema de minimizar se sigue el mismo proceso, pero cambiando el sentido del criterio, es decir, para entrar en la base se elige la variable cuyo valor, en la fila de la función objetivo, sea el mayor de los positivos y se finalizan las iteraciones cuando todos los coeficientes de la fila de la función objetivo son negativos

Interpretación geométrica del método del simplex

Las sucesivas tablas que hemos construido van proporcionando el valor de la función objetivo en los distintos vértices, ajustándose, a la vez, los coeficientes de las variables iniciales y de holgura.

En la primera iteración (Tabla I) han permanecido todos los coeficientes iguales, se ha calculado el valor de la función objetivo en el vértice A(0,0), siendo este 0.

A continuación se desplaza por la arista AB, calculando el valor de f , hasta llegar a B. Este paso aporta la Tabla II.

En esta segunda iteración se ha calculado el valor que corresponde al vértice B(8,0): Z=f(8,0) = 24

Sigue por la arista BC, hasta llegar a C, donde se para y despliega los

datos de la Tabla III. En esta tercera iteración se ha calculado el valor que corresponde al vértice C(6,6) : Z=f(6,6)=30.

Continua haciendo cálculos a través de la arista CD, hasta llegar al vértice

D. Los datos que se reflejan son los de la Tabla IV. Concluye con esta tabla, advirtiendo que ha terminado (antes ha

comprobado que la solución no mejora al desplazarse por la arista DE) El valor máximo de la función objetivo es 33, y corresponde a x = 3 e y = 12 (vértice D).

http://www.investigacion-operaciones.com/Aspectos_Generales_PL.htm#tabla4




Si calculas el valor de la función objetivo en el vértice E(0,14), su valor no supera el valor 33.

2

Documents

Transcript of 2