UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales.

Nombre del alumno: _______________________________ Grupo o modalidad:_________

II.

Programacin lineal.

En este captulo se da una introduccin del tema de la programacin lineal. La programacin lineal es una tcnica de modelado (construccin de modelos) potente y de gran aplicacin en matemticas. Por otra parte, ofrece adems un importante marco de referencia que se relaciona con un rea ms general de las tcnicas de modelado denominada programacin matemtica. La programacin lineal estudia el problema de minimizar o maximizar una funcin lineal en la presencia de desigualdades lineales. Desde que George B. Dantzig desarroll el mtodo simplex en 1947, la programacin lineal se ha utilizado extensamente en el rea militar, industrial, gubernamental y de planificacin urbana, entre otras. La popularidad de la programacin lineal se puede atribuir a muchos factores, incluyendo su habilidad para modelar problemas grandes y complejos, y la habilidad de los usuarios para resolver problemas a gran escala en un intervalo razonable de tiempo mediante el uso del mtodo simplex y de computadoras. A partir de la Segunda Guerra Mundial se hizo evidente que era esencial la planificacin y coordinacin entre varios proyectos, as como el uso eficaz de los recursos disponibles. En junio de 1947 se inici un trabajo intensivo del equipo de la Fuerza Area de los [Link]. conocido como SCOOP (Scientific Computation of Optimum Programs). Como resultado, George B. Dantzig desarroll el mtodo simplex para el final del verano de 1947. El inters en la programacin lineal se difundi rpidamente entre economistas, matemticos, estadsticos e instituciones gubernamentales. En el verano de 1949 se dict una conferencia sobre programacin lineal bajo el patrocinio de la Comisin Cowles para la Investigacin en Economa. Posteriormente, los trabajos presentados en esa conferencia fueron recopilados por T.C. Koopmans, en 1951, en el libro Activity Analysis of Production and Allocation. Desde la creacin del mtodo simplex mucha gente ha contribuido al crecimiento de la programacin lineal, ya sea desarrollando su teora matemtica, diseando cdigos y mtodos computacionales eficientes, experimentando nuevas aplicaciones, y tambin utilizando la programacin lineal como una herramienta auxiliar para resolver problemas ms complejos como son programas discretos, programas no lineales, problemas combinatorios, problemas de programacin estocstica y problemas de control ptimo. En este libro se estudian las reas de programacin lineal y de redes de optimizacin. El mtodo simplex representa la mdula de la mayora de las tcnicas que se utilizaran. Siempre que es posible, el mtodo-simplex se particulariza para tomar ventaja de la estructura de los problemas. Siempre se ha intentado presentar primero las tcnicas, ilustrarlas mediante ejemplos numricos, y despus, proporcionar un anlisis matemtico detallado y un argumento que demuestre la convergencia a una solucin ptima. Aunque esto puede molestar a algunos lectores, se piensa que el formato y el nivel matemtico adoptados proporcionarn un estudio adecuado y fluido a aqullos que deseen aprender las tcnicas y los trucos para utilizadas, y tambin a aqullos que deseen estudiar los algoritmos a un nivel ms riguroso. Diseo: Lic. Enrique Corona Alarcn. Unidad II Pgina 17

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

El texto es para estudiantes avanzados de licenciatura, ingeniera industrial, administracin, investigacin de operaciones, ciencias de la computacin, matemticas, y otras reas de ingeniera que utilizan la programacin lineal y las redes de optimizacin. Aunque el material requiere algunos conocimientos de matemticas, el nico prerrequisito es lgebra lineal. Tambin se expondrn la naturaleza y estructura de los problemas de la programacin lineal; se estudiarn algunas aplicaciones y algunos procedimientos de solucin grfica en el caso, de dos variables. Adems, como la mayor parte de los problemas de este tipo se resuelven mediante programas de computadora, se describirn esos procedimientos de solucin. II.1.- El mtodo de programacin lineal. La programacin lineal (PL) es una tcnica matemtica de optimizacin. Por tcnica de "optimizacin" se entiende un mtodo que trata de maximizar o minimizar un objetivo; por ejemplo, maximizar las utilidades o minimizar los costos. La programacin lineal es un subconjunto de un rea ms extensa de procedimientos de optimizacin matemtica llamada programacin matemtica. Aunque la aplicacin de estos mtodos de programacin matemtica suele exigir el empleo de computadoras, ninguno de ellos se ocupa directamente de la "programacin" por computadora. Su inters principal es tomar decisiones ptimas. La programacin lineal es una tcnica muy potente y con multitud de aplicaciones. Se usa mucho en la industria militar y en la petrolera. Si bien esos sectores han sido quiz los principales usuarios de ella, el sector de servicios y el sector pblico de la economa tambin la han aprovechado ampliamente. En todo problema de programacin lineal hay que tomar ciertas decisiones. stas se representan con variables de decisin xi que se utilizan en el modelo de programacin lineal. La estructura bsica de un problema de este tipo es maximizar o minimizar la funcin objetivo, satisfaciendo al mismo tiempo un grupo de condiciones restrictivas o restricciones. Dicha funcin es una representacin matemtica de la meta global formulada en funcin de las variables de decisin xi Puede representar metas como el nivel de utilidades, los ingresos totales, el costo total, los niveles de contaminacin y el rendimiento porcentual sobre la inversin. El conjunto de restricciones, tambin formulado en funcin de xi representa condiciones que es preciso satisfacer cuando se determinan los niveles de las variables de decisin. As, al procurar maximizar las utilidades obtenidas de la produccin y venta de un grupo de productos, las restricciones muestra podran reflejar los escasos recursos de mano de obra, las pocas materias primas y la limitada demanda de los productos. Las restricciones de un problema de programacin lineal pueden representarse con ecuaciones o con desigualdades (de tipo S y/o ~). A estos problemas se les da el nombre de problemas de programacin lineal porque la funcin objetivo y las restricciones son lineales. A continuacin se plantea un problema simple escrito ya como un modelo matemtico de este tipo:

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 18

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

Maximice Sujeta a:

z = 4 x1 + 2 x2 x1 + 2 x2 24

4 x1 + 3 x2 30 El objetivo es maximizar z, que se formula como funcin lineal de las dos variables de decisin x1 y x2. Al escoger los valores de esas dos variables, hay que satisfacer dos restricciones. Estas se representan con dos desigualdades lineales escritas donde dice Sujeta a:. Los problemas concernientes a la mezcla de productos constituyen un grupo importante de aplicaciones de los modelos matemticos. A continuacin se ilustrar con un ejemplo simplificado el tratamiento que en la programacin lineal se da a este tipo de problemas. Una empresa fabrica dos productos, los cuales deben procesarse en los departamentos 1 y 2. En la tabla se resumen las necesidades de horas de trabajo por unidad de cada producto en uno y otro departamento. Producto A Departamento 1 Departamento 2 Margen de utilidad 3 h por unidad 4 h por unidad $5 por unidad Producto B 2 h por unidad 6 h por unidad $6 por unidad Capacidad de trabajo semanal 120 h 260 h

Tambin se incluyen las capacidades de horas de trabajo semanales en ambos departamentos y los mrgenes respectivos de utilidad que se obtienen con los dos productos. El problema consiste en determinar el nmero de unidades que hay que fabricar de cada producto, con objeto de maximizar la aportacin total a los costos fijos y a las utilidades. Si se supone que x1 y x2 son el nmero de unidades fabricadas y vendidas, respectivamente, de los productos A y B, entonces puede calcularse la aportacin a las utilidades totales sumando las contribuciones de ambos productos. La que hace cada uno se obtiene al multiplicar el margen de utilidad por unidad por el nmero de unidades producidas y vendidas. Si z se define como la aportacin a los costos y utilidades totales, se tendr: z = 5 x1 + 6 x2 Segn la informacin suministrada en el planteamiento del problema, las nicas restricciones al decidir el nmero de unidades que deben fabricarse son las capacidades de trabajo semanal en los dos departamentos. De lo sealado en captulos precedentes se deduce que el lector estar en condiciones de verificar si estas restricciones son representables por las desigualdades: 3 x1 + 2 x2 120 departamento 1 4 x1 + 6 x2 260 departamento 2 Diseo: Lic. Enrique Corona Alarcn. Unidad II Pgina 19

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

Si bien no hay una expresin formal de tal restriccin, se sabe implcitamente que x1 y x2 no pueden ser negativas. Hay que explicar esta clase de restriccin en la formulacin del modelo.

Al combinar la funcin objetivo y las restricciones, el modelo de programacin lineal que representa el problema se formula as: Maximice sujeta a:

z = 5 x1 + 6 x2 3 x1 + 2 x2 120 4 x1 + 6 x2 260 x1 0 x2 0

Restricciones estructurales y restricciones de no negatividad. El modelo de programacin lineal se ocupa de maximizar o minimizar una funcin objetivo lineal sujeta a dos tipos de restricciones: 1) restricciones estructurales y 2) restricciones de no negatividad, una para cada variable de decisin. Las restricciones estructurales reflejan factores como la limitacin de recursos y otras condiciones que impone la situacin del problema. Las dos primeras desigualdades en la formulacin anterior son restricciones estructurales. Las restricciones de no negatividad garantizan que ninguna variable de decisin sea negativa. Las restricciones escritas por ltimo son restricciones de no negatividad. En casi todos los problemas esa restriccin resulta lgica. Se dispone de tcnicas para manejar casos raros donde se permite a una variable asumir valores negativos. Problema: Una empresa produce dos juguetes: los osos Bobby y Teddy. Cada juguete requiere ser procesado en dos mquinas diferentes. La primer mquina tiene 12 horas de capacidad disponible y la otra tiene 8 horas de capacidad disponible por da. Cada Bobby requiere 2 horas en cada mquina. Cada Teddy requiere 3 hrs. en la 1er mquina y 1 hr. en la otra. La ganancia incremental es de 6 por cada Bobby y de 7 por cada Teddy. Si puede vender toda su produccin, Cuntas unidades diarias de cada uno debe producir?

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 20

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

II.2.- Mtodo grfico.

En un problema de programacin lineal se requiere encontrar el valor mximo o mnimo de alguna expresin algebraica cuando las variables de esta expresin estn sujetas a un nmero de desigualdades lineales. El ejemplo simple siguiente es tpico de tales problemas. EJEMPLO 1 (Utilidad mxima) Una compaia fabrica dos productos, X y Y. Cada uno de estos productos requiere cierto tiempo en la lnea de ensamblado y otro tiempo ms en el departamento de acabado. Cada artculo del tipo X necesita 5 horas de ensamblado y 2 horas de acabado, mientras que cada artculo del tipo Y requiere 3 horas en ensamblado y 4 horas de acabado. En cualquier semana, la empresa dispone de 105 horas en la lnea de ensamblado y 70 horas en el departamento de acabado. La empresa puede vender todos los artculos que produce y obtener una utilidad de $200 por cada artculo de X y $160 por cada artculo de Y. Calcule el nmero de artculo de cada tipo que deberan fabricarse a la semana con objeto de maximizar la utilidad total. Solucin Por lo regular es conveniente al manejar problemas de este tipo resumir la informacin en una tabla. En la tabla aparece la informacin del ejemplo 1.

Suponga que la empresa produce x artculos de tipo X a la semana y y artculos del tipo Y a la semana. Entonces el tiempo necesario en la lnea de ensamblado ser de 5x horas en el caso del producto X y 3y horas para el producto Y, o (5x + 3y) horas en total. Dado que slo se pueden disponer de 105 horas, debemos tener que 5x + 3y 105. De manera similar, se requieren de 2x horas en el departamento de acabado por cada x artculos del producto X y 4y por cada y artculos del producto Y. El nmero total de horas, 2x + 4y, no pueden exceder las 70 de que se dispone, de modo que tenemos la segunda condicin, 2x + 4y 70. Cada artculo del tipo X genera una utilidad de $200, de modo que x artculos producen 200x dlares de utilidad. En forma anloga, y artculos de tipo Y producen 160y dlares de utilidad. As, la utilidad semanal total P (en dlares) est dada por P = 200x + 160y. Por consiguiente, podemos reestablecer el problema en los trminos siguientes: encuentre los valores de x y y que maximizan la cantidad P = 200x + 160y cuando x y y estn sujetas a las condiciones 5x + 3y 105, 2x + 4y 70, x 0, Y Y 0. Diseo: Lic. Enrique Corona Alarcn. Unidad II Pgina 21

(Observe las condiciones de que x y y no deben ser negativas. stas se agregan por razones de delimitar los valores.) Este ejemplo es un problema caracterstico de programacin lineal. Tenemos una expresin P = 200x+ 160y, que es lineal en las variables x y y, y deseamos encontrar el valor mximo de P cuando x y y satisfacen las desigualdades. Un problema ms general podra incluir ms de dos variables y un nmero mayor de desigualdades que las cuatro de este ejemplo, pero de cualquier manera este ejemplo es bastante representativo de los problemas del rea de programacin lineal. Al analizar cualquier problema de programacin lineal, en especial cuando slo intervienen dos variables, con frecuencia es til un enfoque geomtrico. Consideremos las desigualdades. El conjunto de puntos (x, y) que satisfacen todas las desigualdades aparece sombreado en la figura. Esta regin sombreada representa el conjunto de soluciones factibles, esto es, el conjunto de valores de x y y que la empresa puede adoptar. No se puede tomar, cualquier punto (x, y) situado afuera de esta regin sombreada.

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

Por ejemplo, consideremos el punto x = 12,Y = 14, el cual est fuera de la regin factible. A fin de producir 12 artculos del tipo X y 14 artculos del tipo Y se requeriran 12(5) + 14(3) = 102horas en la lnea de ensamblado y 12(2) + 14(4)= 80 horas en el departamento de acabado. Si bien esto no excedera las horas disponibles en la lnea de ensamblado, s sobrepasa aquellas disponibles en el departamento de acabado; de modo que no est dentro del programa de produccin posible. Consideremos ahora el conjunto de valores de x y y que conducen a alguna utilidad fija. Por ejemplo, dado a P el valor 4000, advertimos que x y y deben satisfacer la ecuacin 200x + 160y = 4000.

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 22

Todos los valores de x y y que satisfacen esta ecuacin producen una utilidad de $4000 a la semana. Esta es la ecuacin de una lnea recta que corta al eje x en el punto (20, 0) Y al eje y en el punto (0, 25), como se aprecia en la figura. Parte de esta lnea pasa por la regin de soluciones factibles. Debido a esto, concluimos que le es posible a la empresa lograr una utilidad de 4000 dlares a la semana. Puede realizar esto eligiendo cualquier valor de (x, y) situado sobre el segmento AB que aparece en la figura

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

Por otra parte, consideremos P = 6000. Los valores correspondientes de x y y deben satisfacer 200x + 160y = 6000, que otra vez es la ecuacin de una lnea recta, esta vez corta a los ejes de coordenadas en los puntos (30, 0) Y (0, 37.5). Esta lnea recta no pasa por la regin sombreada de soluciones factibles (vase la Fig.) Y por ello no le es posible a la empresa obtener una utilidad tan grande como $6000 a la semana. La utilidad mxima posible debe estar en algn lugar entre $4000 y $6000 a la semana. El conjunto de puntos (x, y) que conducen a una utilidad dada P satisfacen la ecuacin 200x + 160y = P. Esta ecuacin, para P fija, tiene como grfica una lnea recta en el plano xy llamada lnea de utilidad constante o curva de indiferencia. Las dos lneas que aparecen en la figura 8 son lneas de utilidad constante que corresponden a los valores P = 4000 Y P = 6000. La ecuacin de una lnea de utilidad constante puede escribirse en la forma 160y = P - 200x o bien

5 y ordenada al origen PI160. Es una propiedad 4 importante que la pendiente de cualquier lnea de utilidad constante es la misma sin importar el valor de P. Esto significa que todas las lneas de utilidad constante son paralelas entre s. A medida que el valor de P se incrementa; la lnea de utilidad mxima

Por tanto, la lnea tiene pendiente

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 23

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

correspondiente se aparta del origen (la ordenada al origen aumenta), siempre con la misma pendiente.

A fin de obtener la utilidad mxima, debemos alejar la lnea de utilidad constante del origen hasta que slo toque el extremo de la regin de soluciones factibles. Es claro por la figura que la lnea de utilidad mxima es la que pasa por la esquina C situada en la frontera de la solucin factible. Los valores de x y y en C dan los volmenes de produccin de los dos productos X y Y que conducen a la utilidad mxima.

El punto e es la interseccin de las dos lneas rectas que acotan la regin factible. Sus coordenadas se obtienen resolviendo las ecuaciones de estas dos lneas, 5x + 3y = 105 Y 2x + 4y = 70. Resolviendo estas ecuaciones, encontramos que x = 15 Y Y =10. Por consiguiente, la utilidad es mxima cuando la empresa produce 15 artculos del tipo X y 10 artculos del tipo Y a la semana. La utilidad semanal mxima est dada por Pmax = 200x + 160y = 200(15) + 160(10) = 4600, La utilidad mxima es por tanto $4600. El procedimiento usado en la resolucin de este-problema tambin puede emplearse cuando ocurre un nmero mayor de desigualdades. Definicin Las desigualdades que deben satisfacer las variables de un problema de programacin lineal se denominan restricciones. La funcin lineal al ser maximizada o minimizada se conoce como funcin objetivo. En las aplicaciones a anlisis de negocios, la funcin objetivo a menudo es una funcin de utilidad (que debe ser maximizada) o una funcin de costo (que debe minimizarse). Por lo regular, denotamos a la funcin objetivo con la letra Z, y lo haremos as de ahora en adelante.

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 24

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

EJERCICIOS: 1. Una empresa de productos qumicos produce dos tipos de fertilizantes. Su marca regular contiene nitratos, fosfatos y potasio en la razn 3 : 6 : 1 (en peso) y su marca super contiene estos tres ingredientes en la razn 4 : 3 : 3. Cada mes la empresa puede confiar en un suministro de 9 toneladas de nitratos, 13.5 toneladas de fosfatos y 6 toneladas de potasio. Su planta productora puede elaborar a lo ms 25 toneladas de fertilizantes al mes. Si la empresa obtiene una utilidad de $300 por cada tonelada de fertilizante regular y $480 por cada tonelada del super, qu cantidades de cada tipo deber producir a fin de obtener la mxima utilidad?

2. (Mezcla de whisky) Una compaa destiladora tiene dos grados de whisky en bruto (sin mezclar), I y II de los cuales produce dos marcas diferentes. La marca regular contiene un 50% de cada uno de los grados I y II, mientras que la marca super consta de dos terceras partes del grado I y una tercera parte del grado II. La compaa dispone de 3000 galones del grado I y 2000 galones del grado II para mezcla. Cada galn de la marca regular produce una utilidad de $5, mientras que cada galn del super produce una utilidad de $6. Cuntos galones de cada marca debera producir la compaa a fin de maximizar sus utilidades? 3. (Mezclas) Una compaa vende dos mezclas diferentes de nueces. La mezcla ms barata contiene un 80% de cacahuates y un 20% de nueces, mientras que la ms cara contiene el 50% de cada tipo. Cada semana la compaa obtiene 1800 kilos de cacahuates Y, 1200 kilos de nueces de sus fuentes de suministros. Cuntos kilos de cada mezcla deberan producir a fin de maximizar las utilidades si las ganancias son de $10 por cada kilo de la mezcla ms barata y de $15,.porcada kilo de la mezcla ms cara? 4. (Decisiones sobre produccin) Una compaa produce dos productos, A y B. Cada unidad de A requiere 2 horas en cada mquina y 5 horas en una segunda mquina. Cada unidad de B demanda 4 horas en la primera, mquina, y 3 horas, en la segunda mquina. Se dispone de l00 horas a la semana en la primera l maquina y de 110 horas en la segunda. Si la compaa obtiene una utilidad de $70 por cada unidad de A y $50 por cada unidad de B, cunto deber de producirse de cada unidad con objeto de maximizar la utilidad total? 5. (Decisiones sobre produccin) Un fabricante produce dos productos, A y B, cada uno de los cuales requiere tiempo en tres mquinas. Cada unidad de A demanda 2 horas en la primera mquina, 4 horas en la segunda y tres horas en la tercera. Los nmeros correspondientes a cada unidad de B son 5, 1 Y 2, respectivamente. La compaa obtiene utilidades de $250 y $300 por cada unidad de A y B, en ese orden. Si los nmeros de horas disponibles en las mquinas al mes son 200, 240 y 190 en el caso de la primera, segunda y tercera mquinas, respectivamente, determine cuntas unidades de cada producto deben producirse a fin de maximizar la utilidad total. 6. (Decisiones sobre produccin) En el ejercicio 17, suponga que una repentina baja en la demanda del mercado del producto A obliga a la compaa a incrementar su precio. Si la utilidad por cada unidad de A se incrementa a $600, determine el nuevo programa de produccin que maximiza la utilidad total. Diseo: Lic. Enrique Corona Alarcn. Unidad II Pgina 25

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

II.3.- Mtodo simplex.

EL METODO SIMPLEX PARA SOLUCIN DE PROBLEMAS DE PROGRAMACIN LINEAL. Es un procedimiento iterativo que permite ir mejorando la solucin a cada paso. El proceso concluye cuando no es posible seguir mejorando ms dicha solucin. Partiendo del valor de la funcin objetivo en un vrtice cualquiera, el mtodo consiste en buscar sucesivamente otro vrtice que mejore al anterior. La bsqueda se hace siempre a travs de los lados del polgono (o de las aristas del poliedro, si el nmero de variables es mayor). Cmo el nmero de vrtices (y de aristas) es finito, siempre se podr encontrar la solucin. El mtodo del simplex se basa en la siguiente propiedad: si la funcin objetivo, Z, no toma su valor mximo en el vrtice A, entonces hay una arista que parte de A, a lo largo de la cual Z aumenta.

El mtodo del simplex fue creado en 1947 por el matemtico George Dantzig. El mtodo del simplex se utiliza, sobre todo, para resolver problemas de programacin lineal en los que intervienen tres o ms variables. El lgebra matricial y el proceso de eliminacin de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del mtodo simplex. Restriccin frontera: Es una recta que marca el lmite de lo que permite la restriccin correspondiente. Soluciones en el vrtice: Todos los puntos donde se interceptan las restricciones fronteras. Soluciones factibles en el vrtice (FEV): Puntos que se encuentran en los vrtices de la regin factible. Arista: Segmento de recta que conecta 2 soluciones FEV.

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 26

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

Cuatro Teoremas claves de P.L.

1. Cuando hay solucin ptima, siempre existe una en un vrtice. 2. Si una solucin en un vrtice, no tiene soluciones adyacentes mejores, esa es la solucin ptima (ptimo local es global). 3. Solucin bsica (en un vrtice aumentada) es equivalente a hacer (n-m) variables iguales a cero y resolver para las restantes. 4. Soluciones adyacentes tienen iguales todas las variables bsicas menos una (y por supuesto las no bsicas). Ejercicio de ejemplo 1: Maximice: Z = 5 x1 + 6 x2
3 x1 + 2 x2 120 4 x1 + 6 x2 260

x1 , x2 0 1 Convertir las ecuaciones, objetivo y restricciones en ecuaciones aumentadas, aumentando las variables de holgura S: Z 5 x1 6 x2 0 S1 0 S 2 = 0
3 x1 + 2 x2 + S1 + 0 S 2 = 120 4 x1 + 6 x2 + 0 S1 + S 2 = 260

2 Escribir la tabla simplex: Rengln Z X1 X2 R0 R1 R2 S1 S2 1 0 0 -5 3 4 -6 2 6

S1 0 1 0

S2 0 0 1

bi 0 120 260

bi / aik

3 Buscar la columna clave (ser la de mayor utilidad en la funcin objetivo R0), elegir la de mayor valor negativo. Rengln Z X1 X2 S1 S2 bi bi / aik R0 R1 R2 S1 S2 1 0 0 -5 3 4 -6 2 6 0 1 0 0 0 1 0 120 260

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 27

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

4 Calcular las variables bsicas de salida, la ltima columna para aik > 0 , Positivo: b mn i Se tomar aik Rengln Z X1 X2 S1 S2 bi bi / aik R0 R1 R2 S1 S2 1 0 0 -5 3 4 -6 2 6 0 1 0 0 0 1 0 0/(-6) = 0 120 120/2 = 60 260 260/6 = 43 1/3

mn

bi aik

5 Hacer 1 el pivote o interseccin de la mayor utilidad y la mnima variable bsica. Cambiando S2 de Rengln por X2 Rengln Z X1 X2 S1 S2 bi Operaciones bi / aik R0 R1 R2

X2

4/6

1/6 260/6

R2 =R2/6

6 Con operaciones de rengln hacer cero los dems valores de columna. Rengln Z X1 X2 S1 S2 bi Operaciones bi / aik R0 R1 R2 S1 X2 1 0 0 -1 5/3 2/3 0 0 1 0 1 0 1 260 -1/3 33 1/3 1/6 43 1/3 R0 = R2 + R0 R1 = R1-R2/3 R2 =R2/6

7 Si no todos los valores de R0 son positivos la solucin no es optima y habr que repetir los pasos del 3 al 6 . Esto ser hasta que todos los valores den positivos. Pasos 3 y 4 Rengln Z R0 R1 R2 Paso 5 Rengln R0 R1 R2 Paso 6 Rengln R0 R1 R2 X1 X2 X1 S1 X2 Z 0 1 0 0 X1 -1 5/3 2/3 X1 1 X2 0 0 1 X2 0 S1 0 1 0 S1 S2 bi Operaciones

bi / aik

1 260 260/(-1) = 260 -1/3 33 1/3 100/3 / 5/3 = 20 1/6 43 1/3 130/3 / 2/3 = 65 S2 bi 20 Operaciones R1= 3/5R1

bi / aik

3/5 -1/5

Z 1 0 0

X1 0 1 0

X2 0 0 1

S1

S2

bi 280 20 30

bi / aik

Operaciones R0 = R1 + R0 R1= 3/5R1 R2 =R2-2/3R1

3/5 4/5 3/5 -1/5 -2/5 3/10

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 28

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

Como los valores de R0 todos son positivos por lo cual los resultados sern X1 =20 y X2 =30 Calcular el valor mximo de la funcin objetivo. Ejercicio de ejemplo 2: Maximice: Z = 2 x1 + 12 x2 + 8 x3
2 x1 + 2 x2 + x3 100

x1 2 x2 + 5 x3 80
10 x1 + 5 x2 + 4 x3 300

x1 , x2 , x3 0

1 Convertir las ecuaciones, objetivo y restricciones en ecuaciones aumentadas, aumentando las variables de holgura S: Z 2 x1 12 x2 8 x3 0 S1 0 S 2 S3 = 0
2 x1 + 2 x2 + x3 + S1 + 0 S 2 + 0 S3 = 100

x1 2 x2 + 5 x3 + 0 S1 + S 2 + 0 S3 = 80
10 x1 + 5 x2 + 4 x3 + 0 S1 + 0 S 2 + S3 = 300

2 Escribir la tabla simplex: Rengln Z X1 X2 R0 R1 R2 S1 S2 1 0 0 -5 3 4 -6 2 6

S1 0 1 0

S2 0 0 1

bi 0 120 260

bi / aik

3 Buscar la columna clave (ser la de mayor utilidad en la funcin objetivo R0), elegir la de mayor valor negativo. Rengln Z X1 X2 S1 S2 bi bi / aik R0 R1 R2 S1 S2 1 0 0 -5 3 4 -6 2 6 0 1 0 0 0 1 0 120 260

4 Calcular las variables bsicas de salida, la ltima columna para aik > 0 , Positivo: b Se tomar mn i aik Rengln Z X1 X2 S1 S2 bi bi / aik R0 R1 R2 S1 S2 1 0 0 -5 3 4 -6 2 6 0 1 0 0 0 1 0 0/(-6) = 0 120 120/2 = 60 260 260/6 = 43 1/3

mn

bi aik

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 29

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

5 Hacer 1 el pivote o interseccin de la mayor utilidad y la mnima variable bsica. Cambiando S2 de Rengln por X2 Rengln Z X1 X2 S1 S2 bi Operaciones bi / aik R0 R1 R2

X2

4/6

1/6 260/6

R2 =R2/6

6 Con operaciones de rengln hacer cero los dems valores de columna. Rengln Z X1 X2 S1 S2 bi Operaciones bi / aik R0 R1 R2 S1 X2 1 0 0 -1 5/3 2/3 0 0 1 0 1 0 1 260 -1/3 33 1/3 1/6 43 1/3 R0 = R2 + R0 R1 = R1-R2/3 R2 =R2/6

7 Si no todos los valores de R0 son positivos la solucin no es optima y habr que repetir los pasos del 3 al 6 . Esto ser hasta que todos los valores den positivos. Pasos 3 y 4 Rengln Z R0 R1 R2 Paso 5 Rengln R0 R1 R2 Paso 6 Rengln R0 R1 R2 X1 X2 X1 S1 X2 Z 0 1 0 0 X1 -1 5/3 2/3 X1 1 X2 0 0 1 X2 0 S1 0 1 0 S1 S2 bi Operaciones

bi / aik

1 260 260/(-1) = 260 -1/3 33 1/3 100/3 / 5/3 = 20 1/6 43 1/3 130/3 / 2/3 = 65 S2 bi 20 Operaciones R1= 3/5R1

bi / aik

3/5 -1/5

Z 1 0 0

X1 0 1 0

X2 0 0 1

S1

S2

bi 280 20 30

bi / aik

Operaciones R0 = R1 + R0 R1= 3/5R1 R2 =R2-2/3R1

3/5 4/5 3/5 -1/5 -2/5 3/10

Como los valores de R0 todos son positivos por lo cual los resultados sern X1 =20 y X2 =30 Calcular el valor mximo de la funcin objetivo.

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 30

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

Ejercicios, Resuelva por el mtodo simplex:

1. Una empresa de productos qumicos produce dos tipos de fertilizantes. Su marca regular contiene nitratos, fosfatos y potasio en la razn 3 : 6 : 1 (en peso) y su marca super contiene estos tres ingredientes en la razn 4 : 3 : 3. Cada mes la empresa puede confiar en un suministro de 9 toneladas de nitratos, 13.5 toneladas de fosfatos y 6 toneladas de potasio. Su planta productora puede elaborar a lo ms 25 toneladas de fertilizantes al mes. Si la empresa obtiene una utilidad de $300 por cada tonelada de fertilizante regular y $480 por cada tonelada del super, qu cantidades de cada tipo deber producir a fin de obtener la mxima utilidad? 2. (Mezcla de whisky) Una compaa destiladora tiene dos grados de whisky en bruto (sin mezclar), I y II de los cuales produce dos marcas diferentes. La marca regular contiene un 50% de cada uno de los grados I y II, mientras que la marca super consta de dos terceras partes del grado I y una tercera parte del grado II. La compaa dispone de 3000 galones del grado I y 2000 galones del grado II para mezcla. Cada galn de la marca regular produce una utilidad de $5, mientras que cada galn del super produce una utilidad de $6. Cuntos galones de cada marca debera producir la compaa a fin de maximizar sus utilidades? 3. (Mezclas) Una compaa vende dos mezclas diferentes de nueces. La mezcla ms barata contiene un 80% de cacahuates y un 20% de nueces, mientras que la ms cara contiene el 50% de cada tipo. Cada semana la compaa obtiene 1800 kilos de cacahuates Y, 1200 kilos de nueces de sus fuentes de suministros. Cuntos kilos de cada mezcla deberan producir a fin de maximizar las utilidades si las ganancias son de $10 por cada kilo de la mezcla ms barata y de $15,.porcada kilo de la mezcla ms cara? 4. (Decisiones sobre produccin) Una compaa produce dos productos, A y B. Cada unidad de A requiere 2 horas en cada mquina y 5 horas en una segunda mquina. Cada unidad de B demanda 4 horas en la primera, mquina, y 3 horas, en la segunda mquina. Se dispone de l00 horas a la semana en la primera l maquina y de 110 horas en la segunda. Si la compaa obtiene una utilidad de $70 por cada unidad de A y $50 por cada unidad de B, cunto deber de producirse de cada unidad con objeto de maximizar la utilidad total? 5. (Decisiones sobre produccin) Un fabricante produce dos productos, A y B, cada uno de los cuales requiere tiempo en tres mquinas. Cada unidad de A demanda 2 horas en la primera mquina, 4 horas en la segunda y tres horas en la tercera. Los nmeros correspondientes a cada unidad de B son 5, 1 Y 2, respectivamente. La compaa obtiene utilidades de $250 y $300 por cada unidad de A y B, en ese orden. Si los nmeros de horas disponibles en las mquinas al mes son 200, 240 y 190 en el caso de la primera, segunda y tercera mquinas, respectivamente, determine cuntas unidades de cada producto deben producirse a fin de maximizar la utilidad total.

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 31

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

Ejercicio de ejemplo 3: Minimice: Z = 5 x1 + 6 x2

x1 , x2 0

1 Convertir las ecuaciones, objetivo y restricciones en ecuaciones aumentadas, aumentando las variables de holgura S, exceso E y artificiales A, segn corresponda: Z 5 x1 6 x2 0 E1 0 E2 + MA1 + MA2 = 0
x1 + x2 E1 0 E2 + A1 + 0 A2 = 10
2 x1 + 4 x2 0 E1 E2 + 0 A1 + A2 = 24 2 Escribir la tabla simplex: Rengln Z X1 X2 E1 E2 A1

A2

bi

bi / aik

R0 1 -5 -6 0 0 -M -M 0 R1 A1 0 1 1 -1 0 1 0 10 R2 A2 0 2 4 0 -1 0 1 24 3 Volver cero los coeficientes de las variables artificiales. 4 Buscar la columna clave (ser la de menor utilidad en la funcin objetivo R0), elegir la de mayor valor positivo. 5 Calcular las variables bsicas de salida, la ltima columna para aik > 0 , Positivo: b Se tomar mn i aik Rengln Z X1 X2 E1 E2 A1 A2 bi Operaciones bi / aik R0 R1 R2 A1 A2 1 -5+3M -6+5M -M 0 1 1 -1 0 2 4 0 -M 0 -1 0 1 0 0 0 1 34M R0=MR1+MR2 +R0 10 10/1=10 24 24/4=6*

5 Hacer 1 el pivote o interseccin de la mayor utilidad y la mnima variable bsica. Cambiando A2 de Rengln por X2
Rengln

X1

X2

E1

E2

A1

A2

bi

bi / aik

Operaciones

R0 R1 R2

1 -2+M/2 0 -M -3/2+M/4 0 3/2-5/4M 36+4M R0=R0+(6-5M)R2 A1 0 1/2 0 -1 1/4 1 -1/4 4 4/1/2=8* R1=R1-R2 6/1/2=12 x2 0 1/2 1 0 -1/4 0 1/4 6 R2=R2/4 6 Repetir el quinto paso hasta que no haya positivos en el primer rengln.

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 32

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

II.4.- Representacin de problemas mediante el modelo de programacin lineal.

Resuelva los siguientes problemas por el mtodo simplex: 1. Una compaa tiene 100 toneladas de lmina de aluminio en cierta localidad y 120 toneladas de una segunda en otro lugar. Parte de este material debe enviarse a dos obras en construccin. La primera obra requiere 70 toneladas y la segunda 90. Los costos de enviar cada tonelada de aluminio de la primera bodega a la primera y segunda obra son $10 y $15 y de la segunda bodega a las obras respectivas son $15 y $25. Adems se requiere que el costo de envo no exceda de $[Link] el costo. 2.

3.

4.

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 33

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

PROBLEMA #1 Un estudiante dedica parte de su tiempo al reparto de propaganda publicitaria. La empresa A le paga $0.5. por cada impreso repartido y la empresa B, con folletos ms grandes, le paga $0.7 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 da es capaz de repartir 150 impresos como mximo. Lo que se pregunta el estudiante es: Aplicando el mtodo Simplex, cuantos impresos habr de repartir de cada clase para que su beneficio diario sea mximo? PROBLEMA #2 Un fabricante de cemento produce dos tipos de cemento, a saber en grnulos y polvo. l no puede hacer ms de 1600 bolsas un da debido a una escasez de vehculos para transportar el cemento fuera de la planta. Un contrato de ventas establece que l debe producir 500 bolsas al da de cemento en polvo. Debido a restricciones del proceso, se requiere el doble del tiempo para producir una bolsa de cemento granulado en relacin al tiempo requerido por el cemento en polvo. Una bolsa de cemento en polvo consume para su fabricacin 0.24 minutos/bolsa y la planta opera un 8 da 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 cunto se debe producir de cada tipo de cemento para maximizar las ganancias de la Empresa, utilizando el Mtodo Simplex. PROBLEMA #3 SONY fabrica dos productos: (1) el Walkman un radiocasete porttil y (2) el Shader TV, un televisor en blanco y negro del tamao de un reloj de pulsera. El proceso de produccin de ambos productos se asemeja en que los dos necesitan un nmero de horas de trabajo en el departamento de electrnica, y un cierto nmero de horas de mano de obra en el departamento de montaje. Cada Walkman necesita cuatro horas de trabajo de electrnica y dos en el taller de montaje. Cada televisor necesita tres horas de electrnica y una en montaje. Durante el actual perodo de produccin se dispone de doscientas cuarenta horas en el departamento de electrnica y de cien horas en el de montaje. Cada Walkman vendido supone un beneficio de 7 dlares, mientras que para un televisor el beneficio unitario es de cinco dlares. El problema de SONY es determinar utilizando el Mtodo Grfico, la mejor combinacin posible de Walkman y televisores que debe producir para alcanzar el mximo beneficio. PROBLEMA #4 Un agricultor posee un campo de 70 hectreas y puede cultivar ya sea trigo o cebada. Si siembra trigo gasta $ 300 por cada hectrea plantada. En cambio si siembra cebada, su gasto es de $ 400 por hectrea. El capital total disponible es de $ 25 000. Por otra parte, tambin existen restricciones en la disponibilidad de agua para los meses de octubre y noviembre, segn se indica: Mes Consumo m3/ Hcta Trigo Octubre Noviembre 900 1.200 Consumo m3 / Hcta Cebada 650 850 Disponibilidad m3 57.900 115.200

Una hectrea cultivada rinde 30 Tm de trigo o 25 Tm de cebada segn sea el caso. Diseo: Lic. Enrique Corona Alarcn. Unidad II Pgina 34

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

Los precios vigentes por Tm son de $ 45 para el trigo y $ 60 para la cebada. Utilizando el mtodo Simplex, determinar la cantidad de hectreas de trigo y de cebada que debe sembrar el agricultor para que maximice su beneficio. PROBLEMA #5 Una compaa de transportes posee 2 tipos de camiones. El camin tipo A tiene 20 m3 de espacio refrigerado y 40 m3 no refrigerado. El camin tipo B tiene 30 m3 refrigerados y 30 m3 no refrigerados. Una fbrica de productos alimenticios debe embarcar 900 m3 de productos refrigerados y 1200 no refrigerados. Utilizando el Mtodo Simplex, cuntos camiones de cada tipo debe alquilar la fbrica para minimizar costos si el tipo A se alquila a 300 $/Km y el B a 400 $/Km? PROBLEMA #6 Una compaa de transportes tiene 10 camiones con capacidad 20 000 Kilos, y 5 camiones de 15 000 Kg. Los camiones grandes tienen un costo de 3.0 $/Km y los pequeos de 2.5 $/Km. En una semana debe transportar la empresa 200 000 Kg en un recorrido de 800 km. La posibilidad de otros compromisos recomienda que por cada dos camiones pequeos mantenidos en reserva deba quedarse por lo menos uno de los grandes. Utilizando el Mtodo Simplex, Cul es el nmero de camiones de ambas clases que deben movilizarse para ese transporte de forma ptima y teniendo en cuenta las restricciones descritas? PROBLEMA #7 Cada mes una empresa puede gastar. Como mximo, 10 000 000. en salarios y 18 000 000. en energa (electricidad y gasoil). La empresa slo elabora dos tipos de productos A y B. Por cada unidad de A que elabora gana 800. y 500. por cada unidad de B. El costo salarial, y energtico que acarrea la elaboracin de una unidad del producto A y una del B aparece en la siguiente tabla: A Costo B

200 100

Costo energtico 100 300 Utilizando el mtodo Simplex, se desea determinar cuntas unidades de cada uno de los productos A y B debe producir la empresa para que el beneficio sea mximo. PROBLEMA #8 La empresa de computadoras COMPAQ toma las decisiones trimestral sobre la fabricacin de su mezcla de productos. Mientras todas sus lneas productivas incluyen una gran variedad de artculos de computacin, solamente se considerar un problema ms simple con slo dos productos: las computadoras porttiles y las computadoras del escritorio. A COMPAQ les gustara saber cuntos de dichos productos deben fabricar para obtener mximas ganancias en el primer trimestre del 2006. Hay varios lmites del proceso que definen la capacidad productiva tanto de la computadora porttil como la de escritorio:

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 35

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

1.- Cada computadora (porttil 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 256MB por tarjeta. Una computadora porttil requiere 256MB de memoria instalada (es decir, necesita 1 tarjeta RAM) mientras una computadora de escritorio tiene 512MB ( sea, requiere 2 tarjetas RAM). COMPAQ dispone en inventario 15.000 tarjetas RAM para el prximo trimestre. 3.- Cada computadora requiere un tiempo de ensamblaje. Debido a las estrechas tolerancias para ensamblar una computadora porttil, 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 prximo trimestre Bajo las actuales condiciones del mercado, costos de los materiales y sistema productivo, la venta de cada computadora porttil genera $ 3500 de ganancia y cada computadora de escritorio produce $ 2500 ganancia. Hay muchas preguntas que COMPAQ podra hacer. Por ello, aplicando el mtodo Simplex, determinar la respuesta Cuntos computadoras de cada tipo debe fabricar COMPAQ en el prximo trimestre para maximizar sus beneficios?. PROBLEMA #9 Podemos comprar paquetes de abono A o B. Cada paquete contiene las unidades de potasio (K), fsforo (P) y nitrgeno (N) indicadas en la tabla, donde se da el precio del paquete. Marca K P A B 4 6 N Precio 1 15

1 10 6 24

Utilizando el mtodo Simplex, en qu proporcin hay que mezclar ambos tipos de abono para obtener al mnimo precio un abono que contenga 4 unidades de K, 23 de P y 6 de N? PROBLEMA #10 Un ejecutivo de una empresa tiene $100.000 para invertir. Tiene dos inversiones: A y B. El Plan A garantiza que por cada peso invertido, se obtendrn $0,70 al final de un ao (se entiende que no puede fraccionarse este lapso de tiempo). El Plan B garantiza que por cada peso invertido, se obtendrn $2,00 al final de un perodo de dos aos (se entiende que no puede fraccionarse este lapso de tiempo). Aplicando el mtodo SIMPLEX, asesore al ejecutivo para obtener el mejor rendimiento por su dinero durante un perodo de tres aos. PROBLEMA #11 La empresa McDonalds 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 slo utiliza 0,2 libras. El restaurante empieza Diseo: Lic. Enrique Corona Alarcn. Unidad II Pgina 36

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

cada da con 200 libras de carne. La utilidad neta es la siguiente: $6.0 por cada hamburguesa de cuarto de libra y $4.5 por cada hamburguesa con queso. El gerente estima adems que no vender ms de 900 hamburguesas en total. Aplicando el mtodo SIMPLEX, determine la mxima utilidad que obtiene McDonald's.

PROBLEMA #12 Los 400 alumnos de un colegio van a ir de excursin. Para ello se contrata el viaje a una empresa que dispone de 8 autobuses con 40 plazas y 10 con 50 plazas, pero slo de 9 conductores para ese da. Dada la diferente capacidad y calidad, el alquiler de cada autobs de los grandes cuesta 8000. y el de cada uno de los pequeos, 6000. Utilizando el Mtodo SIMPLEX, cuantos autobuses de cada clase convendr alquilar para que el viaje resulte lo ms econmico posible? PROBLEMA #13 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 ms 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 ms de 100g de A si 100g de A contiene 30 mg de vitaminas y 450 caloras y 100 g de B contienen 20 mg de vitaminas y 150 caloras, utilizando el mtodo SIMPLEX: a) Cuntos gramos de cada producto debe mezclar para obtener el preparado ms rico en vitaminas? b) Y el ms pobre en caloras? PROBLEMA #14 Los precios de venta de dos productos A y B estn en la misma relacin que 7 y 6. La produccin de estos est definida por las siguientes condiciones: La produccin de A es mayor o igual que la mitad de B y menor o igual que el doble de B. La produccin total es tal que si slo se produce A, se producen 10 kg, y si slo se produce B, se producen 15 kg. Y si se producen conjuntamente, la produccin mxima se encuentra en la recta que une los puntos anteriores. Dar la funcin objetivo de la venta de ambos productos. Expresar mediante inecuaciones el recinto definido. Utilizando el Mtodo SIMPLEX, determinar los kilos que se han de producir de cada producto para obtener el mximo beneficio. PROBLEMA #15 Una compaa petrolfera requiere diariamente 9 Tm, 12 Tm y 24 Tm de petrleo de calidad alta, media y baja respectivamente. La compaa tiene dos refineras. La refinera A produce diariamente 1 Tm, 3 Tm y 4 Tm de calidades alta, media y baja respectivamente. La refinera B produce 2 Tm de cada una de las tres calidades. El coste diario de cada una de las refineras es de 20.000.000 de Bs. Utilizando el mtodo SIMPLEX, cuntos das debe de trabajar cada refinera para que el costo sea mnimo?. PROBLEMA #16 Un laboratorio farmacutico 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 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 por gramo que contiene 1 unidad de vitamina A, 10 de B y 6 Diseo: Lic. Enrique Corona Alarcn. Unidad II Pgina 37

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

de C. Utilizando el Mtodo SIMPLEX, cuntos gramos de cada aditivo se deben incluir en cada frasco para minimizar el costo?

PROBLEMA #1|7 Un expendio de carnes acostumbra a preparar la carne para hamburguesas con una combinacin 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 mtodo 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 # 18 Una empresa lctea plantea la produccin de dos nuevas bebidas. producir un litro del primer tipo de bebida cuesta 20$, mientras que un litro del segundo tipo de bebida cuesta 50$. Para realizar el lanzamiento comercial se necesitan ms de 6.000.000 litros de bebida, aunque del segundo tipo no podrn producirse (por limitaciones tcnicas) ms de 5.000.000. Adems, se desea producir ms cantidad de bebida del segundo tipo que del primero. Cuntos litros habr que producir de cada tipo de bebida para que el costo de produccin sea mnimo? PROBLEMA # 19 Usted tiene 60 hectreas de tierra que an no ha cultivado, y piensa trabajarlas para la prxima temporada junto a sus dos hijos, Pedro y Javier. Pedro insiste en sembrar ajo, pues tiene una ganancia neta mayor: sacaran $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 hectrea, pues estn 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 crtica de slo 100 m3 de agua). Su administrador, por su parte, hace notar que slo 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 hectrea. a.- Formule y resuelva el modelo matemtico de Programacin Lineal para maximizar la ganancia. b.- Evale las sugerencias de sus hijos Pedro y Javier. Puede usted mejorar estas sugerencias? PROBLEMA #20 Una compaa petrolera produce un tipo de gasolina a partir de petrleo. Puede comprar cuatro tipos de petrleo y dispone de los siguientes datos:
Crudo A
1 2 3 4 0,8 0,3 0,7 0,4

B
0,1 0,3 0,1 0,5

C
0,1 0,4 0,2 0,1

Precio (Bs/lit)
43 31 47 37

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 38

UNIVERSIDAD METROPOLITANA DE XALAPA. U.M.X. Clase nmero: _________ Fecha: ______________ Materia: Modelos Operacionales. Nombre del alumno: _______________________________ Grupo o modalidad:_________

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 obtencin de gasolina debe tener al menos el 60% del elemento A y no ms del 30% de C. Obtenga el crudo base mezclando los cuatro tipos anteriores de forma tal que el coste sea mnimo. PROBLEMA # 21 Usted dispone de 2.200 euros para invertirlos durante los prximos cinco aos. Al inicio de cada ao puede invertir parte del dinero en depsitos a un ao o a dos aos. Los depsitos a un ao pagan un inters del 5 %, mientras que los depsitos a dos aos pagan un 11% al final de los dos aos. Adems, al inicio del segundo ao es posible invertir dinero en obligaciones a tres aos 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 aos tu capital sea lo mayor posible. PROBLEMA # 22 La Alcalda tiene comprometido gastar en proyectos de infraestructura en los prximos cuatro aos, 2000, 4000, 8000 y 5000 millones de Pesos. Este dinero tiene que estar disponible el da 1 de enero del ao en que se va a gastar. Para financiar estos gastos el ayuntamiento planea emitir unos bonos a largo plazo (20 aos) con un inters remunerativo del 7% para la deuda emitida el primer ao, del 6% para la emitida el segundo ao, 6.5% para la del tercer ao y del 7.5% para la emitida el cuarto ao. Los intereses se empiezan a pagar inmediatamente. Si parte del dinero recaudado se depositase en cuantas a plazo fijo, el ayuntamiento es capaz de obtener el 6% de inters el segundo ao, el 5.5% el tercer ao y el 4.5% el cuarto ao. El problema que se plantea el ayuntamiento es el de determinar la estrategia o plan ptimo de financiamiento de las obras de infraestructura

Diseo: Lic. Enrique Corona Alarcn.

Unidad II

Pgina 39