• Author / Uploaded
• Esperanza Sánchez

Citation preview

UNIVERSIDAD TÉCNICA “LUIS VARGAS TORRES” DE ESMERALDAS, REPÚBLICA DEL ECUADOR. FACULTAD DE INGENIERÍA Y TECNOLOGÍAS

INTRODUCCIÓN A LAINVESTIGACIÓN OPERATIVA

LIBRO Elaborado por: Lic. Ramón Rodríguez Betancourt, Ph D2 Lic. Josué Imbert Tamayo Ph D

Octubre del 2015

ÍNDICE

Páginas

I.

Introducción a la Programación Lineal……………………………..6

II.

Planteamientos de Problemas………………………………………..10

III.

Métodos de solución……………………………………………………67

IV.

Programas Computacionales. Análisis de la Solución Óptima…92

V.

Programación Reticular………………………………………………111

VI.

Bibliografía………………………………………………………………147

2

Sobre los autores Rodríguez Betancourt, Ramón. Graduado de Licenciado en Economía en el año 1966. Tiene 49 años impartiendo docencia de pregrado y postgrado en materia de Matemática para economistas, Técnicas de optimización y Técnicas Econométricas. Doctor en Ciencias Económicas en 1975 en la Universidad de San Petersburgo. Doctor en Ciencias 1985 en la Universidad Estatal de San Petersburgo. Profesor titular. Tiene más de 55 publicaciones nacionales e internacionales, entre ellas, cuatro libros de textos publicados, que incluyen Algebra Lineal, Técnicas Econométricas y Técnicas de optimización, Ha dirigido once tesis de doctorado y más de treinta trabajos de diplomas. Ha participado en numerosos eventos científicos nacionales e internacionales. Ha sido Decano de la Facultad de Ciencias Económicas y Empresariales de la Universidad de Oriente durante 12 años. Ha impartido numerosos cursos de postgrado en Cuba y en el extranjero en materia de optimización, incluyendo una maestría en México. Ha sido nominado tres veces consecutiva al premio nacional de Economía. Actualmente es miembro del Centro de Estudios de Investigaciones Económicas Aplicadas de la Facultad de Ciencias Económicas y Empresariales de la Universidad de Oriente. Miembro del Consejo Científico de la Universidad de Oriente y de la Facultad de Ciencias Económicas y Empresariales. Actualmente es profesor invitado de la Facultad de Ingeniería y Tecnología de la Universidad “Luis Vargas Torres” de la provincia de Esmeraldas, República de Ecuador.

Imbert Tamayo, Josué.Licenciado en Economía graduado en 1968, Tiene 46 años impartiendo docencia de pregrado y postgrado en materia de matemática para economistay, Técnicas de optimización. Doctor en Ciencias Económicas en 1988 en la Universidad de San Petersburgo. Cuenta con numerosas publicaciones de carácter nacional e internacional. Parte de estas publicaciones son orientadas a la gestión empresarial, es miembro del Consejo Científico de la Facultad de Ciencias Económicas de la Universidad de Oriente.Ha sido tutor de una tesis de doctorado, dos tesis de maestría y más de treinta trabajos de diploma. Ha prestado colaboración internacional

3

en México en la Universidad Autónoma de Zacatecas en las Facultades de Economía y Vinculo Universidad dondedirigió cuatro tesis de maestría. Actualmente presta servicios en el Departamento de Métodos Matemáticos y Computación Facultad de Ciencias Económicas y Empresariales de la Universidad de Oriente como profesor titular.

4

INTRODUCCIÓN

Las técnicas de optimización, conjuntamente con los sistemas informáticos, se han convertido en una poderosa herramienta para el diagnóstico y solución de múltiples problemas complejos, presentes en las ciencias de la administración, y las ingenierías convirtiéndose en elemento decisivo para la toma de decisiones. Para la utilización de esta herramienta es necesario conocer su metodología científica, así como poseer conocimientos mínimos de Matemáticas, Estadística Matemática y en especial de Álgebra Lineal. El objetivo fundamental de esta publicación es brindar a los estudiantes de pregrado de las carreras de la Facultad de Ingeniería y Tecnología FIT de la Universidad “Luis Vargas Torres” de la provincia de Esmeraldas, República del Ecuador un material práctico que incida en la creación de habilidades para identificar los diferentes enfoques potenciales donde encuentran campo de aplicación las Técnicas de Optimización, la utilización de la metodología científica,

hasta la introducción de los resultados

obtenidos en la práctica social, los métodos de solución y los sistemas informáticos profesionales asociados a ellos. La Programación Lineal es una de las más importantes técnicas cuantitativas, tanto por los resultados que pueden obtenerse con ella, como por las derivaciones que posteriormente han surgido, tales como la Programación en Enteros, la Programación por Objetivos o las soluciones que pueden implementarse en las técnicas PERT y otras. En este caso el enfoque se ha orientado hacia los estudiantes que reciben esta disciplina, en las ingenierías, con el objetivo de facilitar su estudio y comprensión y que además cuenten con un material de estudio, que permita complementar las clases del profesor y la obtención de buenos resultados finales. Se ha elaborado tomando como base la experiencia del profesor en la impartición de esta asignatura en el 8vo. ciclo de la carrera de ingeniería mecánica, pero puede ser generalizada a otras carreras de la UTL-VT. En la medidasuutilización por los estudiantes se irá perfeccionando hasta lograr que cumplimente tanto sus expectativas como la delprofesor. El folleto comienza con la metodología de la investigación de operaciones posteriormente se enfoca el problema general de la programación lineal, planteamientos

5

de problemas los métodos utilizados para su solución, sistemas informáticos más utilizados. Posteriormente se enfoca la Programación Reticular y por último la bibliografía.

I.INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL Las Técnicas de Investigación de Operaciones aparecen en los años 50, a partir de entonces comienza a desarrollarse la metodología para su utilización.

Sus

antecedentes se localizan en las investigaciones de Isaac Newton, GeorgeDantzing, Charnes y Cooper, Ackoff, Churchman y Zimmerman. Esta metodología se sustenta en los siguientes supuestos:  alternativa en las decisiones;  posibilidades de crear una base informática;  posibilidades mínimas de poder aplicar los resultados. En este proceso existe una secuencia de pasos para llegar a la obtención de los objetivos propuestos:  observación e identificación del problema;  formulación general;  construcción del modelo;  generación de una solución;  prueba y evaluación de la solución;  implantación;  perfeccionamiento y desarrollo. No es conveniente saltar ningún paso.

Observación

Se analiza el fenómeno como tal, las interrelaciones que tiene, las posibles variables, el sistema organizativo bajo el cual se encuentra el fenómeno, se escuchan los criterios de expertos, se analiza el cumplimiento de las premisas fundamentales de las técnicas de optimización, que son: 

Alternativa de decisión. 6



Condiciones de linealidad o no.



Mínimas condiciones organizativas.

Se define conceptualmente cuál es el problema a resolver, se enuncian los objetivos y se establecen hipótesis, se consulta la bibliografía especializada. Se realizan contactos inter-especialistas y por último se elabora una ficha con un pequeño historial, resumen de toda la observación realizada.

Formulación General del Problema

Es un problema secuencial, se empieza con una formulación inicial basado en lo anterior y se perfecciona en la medida en que se plantea el problema y se obtienen las primeras soluciones. Muchas veces el análisis del resultado incide en la formulación. Ésta tiene dos aspectos: general y concreto. La formulación general se utiliza en publicaciones científicas, en ponencias y eventos. Un ejemplo de formulación concreta son los estudios de casos y los informes de tesis, así como los informes ejecutivos que se entregan a los directivos de empresas una vez culminado el trabajo. La formulación del problema consta de los siguientes aspectos: a) Fenómeno que se aborda. b) Lugar y tiempo. c) Pequeña descripción de lo que se quiere lograr. d) Posibilidades de obtener la información y de solucionar el problema. e) Los objetivos principales y secundarios

Planteamiento Matemático

Es una respuesta a la formulación del problema I) Planteamiento Matemático General. El planteamiento matemático general consta de índices, variables, parámetros, restricciones y función objetiva.

7

Este planteamiento se utiliza en publicaciones, eventos o cuando se tiene una idea de cómo se podrá modelar un fenómeno dado. El aspecto de las variables, restricciones y función objetivo se trata bajo los mismos lineamientos del planteamiento concreto de trabajo. Los parámetros se definen con la misma rigurosidad que las variables (cualitativa y cuantitativamente y tiempo). Los índices reflejan las diferentes combinaciones que se pueden dar con las variables. II) Planteamiento Matemático. Se utiliza en el proceso de aplicación y al igual que la formulación es secuencial puede ser corregido o perfeccionado cuándo se tiene la solución del problema. Consta de tres momentos: a) Definición de lasvariables. - Puede hacerse una a una o de forma general (si la cantidad de variables a definir es grande), y a su vez incluye tres aspectos: -

aspecto cualitativo: ¿qué es la variable?

-

aspecto cuantitativo: ¿en qué unidad se mide?

-

definición temporal: ¿qué período de tiempo abarca?

Las variables representan el elemento incógnito en el problema. Este momento es esencial en el planteamiento del problema, pues una mala definición de las variables repercute en la solución y proporciona un disparate. b) Planteamiento de las restricciones. – Lo fundamental de este paso es cuidar la homogeneidad que debe existir entre el término de la derecha y la expresión de la izquierda, la cual está compuesta por varios elementos, los que deben ser homogéneos, para que al sumarse permita una lógica comparación. En este sentido el signo de la restricción es un aspecto clave. Si se desea que la suma de la expresión de la izquierda sea como mínimo el valor de la derecha, el signo será mayor o igual, también se utiliza el menor o igual si se desea que la expresión de la izquierda sea cuando más el valor de la derecha. Si se aspira a que sean exactamente iguales se utilizará el símbolo de igualdad. c) Planteamiento de la función objetiva. – Debe reflejar de una forma clara el objetivo del problema. Si es máximo o si es mínimo en muchos casos su planteamiento es relativamente fácil, en otros se llega a través de una secuencia de expresiones

8

algebraicas que finalmente deben hacerse corresponder con el objetivo deseado. En ocasiones, la función objetiva se plantea en forma ponderada de una variable y haciendo caso omiso del valor numérico encontrado al final.

Solución, análisis y corrección de resultados

Teniendo en cuenta el desarrollo de los sistemas informáticos, es posible acceder fácilmente a softwares profesionales para dar solución a los modelos matemáticos diseñados. De igual manera, diseñar sistemas informáticos especiales es otra práctica común en estos tiempos. En este sentido, este punto se ha ido por encima de la formulación y del planteamiento. Una vez obtenida la solución se requiere hacer determinadas comprobaciones que confirmen los resultados. Estas comprobaciones repercuten en la formulación y planteamiento del problema y en la verificación de los parámetros utilizados, los cuales ya han sido determinados previamente mediante una base informática preestablecida, es decir; mediante la estadística o los criterios de un experto incluso mediante las técnicas borrosas. La solución de un problema no debe ser comentada hasta tanto no se haya verificado la validez y adaptación al campo de aplicación, en caso contrario esto puede ser perjudicial en la introducción de los resultados.

Validación

En la práctica se lleva a cabo mediante los juegos de implementación definidos en la Teoría de

Lewin - Shein1. Estos juegos se desarrollan simulando algunos de los

componentes del sistema bajo estudio, y utilizando como herramienta de simulación los resultados obtenidos (Juego; proceso simulador de resultado).



Teoría expuesta en el libro “Modelos Cuantitativos para la administración” de Roscoe, Davis; Mckeown,

1

Patric. University of Georgia. Grupo Editorial Iberoamericano. 1991

9

Introducción de resultados

La introducción implica la estrategia o acción en el sistema que ha sido modelado y que va a tener en cuenta los resultados obtenidos. Claro que la dinámica productiva muchas veces en muy rápida pero para introducir los resultados en la práctica se hacen necesario su seguimiento de manera que se pueda corregir cualquier alteración que surja en el proceso.

II. PLANTEAMIENTOS DE PROBLEMAS Objetivo Al finalizar el estudio del tema, el estudiante deberá *Ser capaz de formular modelos de programación lineal, es decir, de hacer la traducción del problema del mundo real al modelo cuantitativo, como paso importante en la utilización de la optimización lineal como instrumento en la actividad empresarial. Como se desprende de los objetivos enunciados anteriormente, inicialmente se dará un conjunto de definiciones y conceptos que resultarán muy

útiles no solo para la

asignatura como tal, sino para otras asignaturas de la carrera. Construcción de modelos de programación lineal

En el presente capitulo, se estudiarán algunos aspectos básicos necesarios para familiarizarse con la construcción de los modelos y luego se examinarán numerosos ejemplos representativos de diversas situaciones que pueden darse en diferentes contextos. Un paso importante en la formulación de modelos consistirá en la identificación de las restricciones. Las restricciones pueden considerarse como limitantes del conjunto de decisiones permisibles. Algunos ejemplos específicos de restricciones en problemas de administración pueden ser: 10

 Un gerente de una empresa industrial tiene sus decisiones limitadas por la disponibilidad de recursos materiales y humanos, la capacidad de los equipos, la tecnología disponible, los contratos ya efectuados, etc.  El gerente responsable de las finanzas de una corporación tiene cierta cantidad de capital para inversiones. Sus decisiones están limitadas por el monto de este capital, las normativas de la empresa y la legislación vigente.  La asignación de personal y la programación de los vuelos en una empresa aérea están restringidos por las necesidades de mantenimiento y el número de empleados disponibles.  La administración de una empresa agropecuaria tiene limitadas sus decisiones por la cantidad de tierra, el agua disponible para riego, la cantidad de maquinaria, la calidad de la semilla, así como por

las condiciones de suelo, clima, etc. existentes en el

agroecosubsistema dado. En un ambiente de toma de decisiones, una limitante o restricción sobre las decisiones posibles, es una cuestión que reviste singular importancia. En una gran cantidad de casos, las restricciones pueden considerarse que son de dos tipos: limitaciones o requerimientos. Veamos en que consiste la diferencia entre ellas valiéndonos de los tipos de restricción enunciadas arriba. Las decisiones del gerente industrial están restringidas por las limitaciones en la capacidad de los equipos y la tecnología y por los requerimientos establecidos en los contratos realizados y que deben ser cubiertos. En la primera restricción el gerente de finanzas está restringido en su actuación por las limitaciones de capital y por los requerimientos de la empresa y la legislación. La dirección de la aerolínea está restringida en sus decisiones por el requerimiento de que toda tripulación debe permanecer en tierra, por lo menos 24 horas entre vuelos. 11

La administración de la empresa agropecuaria está restringida en sus decisiones por las limitaciones en la cantidad de tierra, el agua disponible y los demás recursos y por los requerimientos del autoconsumo animal y humano. Todo problema de Programación Lineal tiene dos partes importantes: un conjunto de restricciones y una función objetivo que se desea maximizar o minimizar. Utilizando los ejemplos anteriores se puede decir que el gerente financiero de la empresa puede querer maximizar los ingresos provenientes de la inversión, el gerente de producción de la misma empresa puede desear satisfacer la demanda con un mínimo costo de producción, la dirección de la empresa aérea puede desear encontrar un plan de asignación de personal que le permita un costo mínimo y el empresario agrícola desea producir con costos mínimos o con una ganancia máxima. De lo anterior se infiere que, en estos ejemplos, el responsable (o los responsables) de tomar las decisiones tienen alguna cantidad que desean maximizar (ingresos, rendimiento o la eficiencia) o minimizar (costo, tiempo, distancia). A esta cantidad se le denomina como función objetivoo función criterio. O sea que la PL proporciona un modelo de toma de decisiones restringidas. Este es el tipo de modelo que ha resultado más útil en las aplicaciones prácticas, existiendo miles de problemas de decisión de tipo empresarial, social o militar en los que ha tenido éxito su aplicación. En lo que sigue, se examinará un conjunto de formulaciones de problemas en los que están implicados procesos de toma de decisiones empresariales y el análisis realizado para la construcción del modelo correspondiente. Más adelante se explicarán los métodos para resolver esos modelos y el análisis de los resultados obtenidos. Ejemplo 1. Programación de la producción La empresa constructora de equipos pesados Equipesa tiene programada la producción de dos líneas de equipos: cargadores frontales destinados fundamentalmente a la construcción y equipos zanjeadoras que se destinan principalmente a las empresas 12

agropecuarias. Ambos equipos tienen un amplio mercado, tanto dentro del país como en el exterior y se garantiza la venta de todos los que la empresa pueda producir en el semestre. A diferencia de otros productos que elabora la Empresa, estos dos utilizan las capacidades de los Departamentos y brigadas de operarios. La administración desea conocer cuál es la combinación de productos de cada tipo que debería producir. En el proceso de toma de decisiones, los principales factores a considerar son los siguientes: 1. Equipesa tendrá una utilidad de $ 5000 por cada cargador que se venda y de $4000 por cada zanjeadoras. 2. Cada equipo pasa por operaciones mecánicas tanto en el Departamento A como en el Departamento B.

3.Para la producción del próximo mes, estos dos departamentos tienen disponible 150 y 160 horas, respectivamente. Cada cargador consume 10 horas de operación mecánica en el Departamento A y 14 horas en el Departamento B, mientras que cada zanjeadoras consume 15 horas en el Departamento A y 10 horas en el B. Estos datos se resumen en cuadro siguiente: Datos de la programación mensual Departame Horas/ Horas/ Total horas nto cargador zanjeadoras disponibles A 10 15 150 B 14 10 160 4.

Como la empresa tiene intenciones de incursionar el comercio exterior, por ello quiere cumplir con las normas de calidad vigentes en ese contexto. Con el objetivo de cumplir las disposiciones de control de calidad, el total de horas de trabajo que se dedicarán a la comprobación del acabado de los productos terminados, no puede ser menor de 135. Esta comprobación se realiza en un tercer departamento que no tiene relación con las actividades de los departamentos A y B. Cada cargador requiere 18

13

horas de comprobación y cada zanjeadoras, 10. Estos datos se dan en el cuadro siguiente:

Horas comprobación 5.

Datos de la comprobación de equipos Horas/ Horas/Zanjeadoras Horas Cargador requeridas de 18 10 135

Con el objetivo de mantener su posición actual en el mercado, la dirección de Equipesa ha determinado que la política de producción más conveniente, es construir al menos una zanjeadoraspor cada tres cargadores frontales.

6.

Un Complejo Agroindustrial arrocero ha ordenado un total de por lo menos cinco máquinas (en cualquier combinación de cargadores o zanjeadoras) para el próximo mes, así que por lo menos debe producirse esa cantidad.

Dado el anterior conjunto de factores, el problema de la administración es decidir cuantos cargadores y cuantas zanjeadoras debe producir el próximo mes. En otros términos, busca determinar la combinación óptima de producción, también denominado plan óptimo de producción. El propósito siguiente será mostrar cómo se puede expresar este problema como modelo matemático, en particular como un modelo lineal. Para ello, se deberán identificar las restricciones y la función objetivo. Conjunto de restricciones El paso inicial para la elaboración de las restricciones consiste en realizar la definición de cuáles son las incógnitas cuyo valor debemos encontrar. Podemos definir como X = número de cargadores a producir Y = número de zanjeadoras a producir Total, de horas disponibles en el Departamento A = 10 (No. de cargadores) + 15 (No. de zanjeadoras) Sustituyendo las variables definidas arriba en la igualdad anterior tendremos: 14

Total, de horas disponibles en el Departamento A = 10X + 15Y y como, de acuerdo al cuadro dado en el punto 3 de la formulación del problema, el número máximo de horas disponible en el departamento A es 150, las incógnitas X y Y deben satisfacer la condición (o sea, la restricción) 10 X + 15 Y  150

(1)

Esta es la restricción de horas disponibles en el departamento A. El símbolo  significa menor que o igual a y la condición anterior se llama restricción de desigualdad. El número 150 se llama segundomiembro de la desigualdad. El primer miembro de la desigualdad depende claramente de las incógnitas X y

Yy se llama función de

restricción. Esta desigualdad matemática es una forma simbólica sintética para establecer la restricción de que el número total de horas empleadas en el departamento A para producir X cantidad de cargadores y Y cantidad de zanjeadoras no debe exceder las 150 horas disponibles. En el cuadro del punto 3 vemos que cada cargador producido empleará 14 horas de trabajo en el departamento B y que cada zanjeadoras empleará 10. Como no hay más de 160 horas disponibles en este departamento, los valores de X y Y deben satisfacer también la desigualdad 14 X + 10 Y  160

(2)

Las restricciones (1) y (2) representan dos de las restricciones del problema estudiado. En el conjunto de factores que debían considerarse se indica que se debe utilizar un número mínimo de horas en la verificación de los productos terminados y que este número mínimo de horas total del departamento se determinó como 135. De esta manera tenemos que 18 X + 10 Y  135

(3)

El símbolo  significa mayor que o igual a y la condición (3) se llama también restricción de desigualdad. Nótese que la condición

(3)

es una desigualdad

matemática del tipo  (un requerimiento) que difiere de las condiciones (1) y (2) que son desigualdades matemáticas del tipo  (limitaciones). 15

Otra restricción es que se debe producir al menos una zanjeadoras por cada tres cargadores. Esto se puede escribir como una proporción X Y



3 1

Resolviendo por multiplicación cruzada esta expresión quedará como X  3Y Pasando el término de la derecha para la izquierda se tendrá la restricción que se busca X - 3Y  0

(4)

Obsérvese que se han llevado todas las variables para el primer término. Más adelante se verá que esto es siempre conveniente para poder comenzar el proceso de solución de un problema de optimización. El último factor a tener consideración fue dado como que se deben producir por lo menos 5 unidades en el próximo mes, en cualquier combinación. O sea, se establece que X+ Y5 (5) Se tienen así especificadas en forma matemática las cinco restricciones de desigualdades asociadas al problema de producción de la empresa Equipesa.

Y

finalmente, como carece de sentido producir cantidades negativas de X y Y, se deben incluir las dos condiciones siguientes: X  0, Y  0

(6)

Las condiciones (6) exigenque los valores de X y Y sean no negativos y se denominan como condiciones de no negatividad. En este punto debe recordarse la diferencia entre el término no negativo y positivo. Nótese que “no negativo” admite que el valor pueda ser cero, pero el término “positivo” lo descarta. Como se deduce de la formulación del problema, la elección de valores para el par X y Y se llama decisión; por ello a X y Y se les denomina como variables de decisión (son cantidades que controla la administración). Está claro en este problema que una

16

decisión significará elegir una combinación de valores o sea una producción mixta. Por ejemplo, X = 6 y Y = 5 significa la decisión de producir seis cargadores y 5 zanjeadoras. El problema es que algunas decisiones no negativas pueden cumplir con el conjunto de restricciones (1) a (5) pero otras no. Como se observa, la decisión X = 6 yY = 5 satisface las restricciones (1), (2), (3) y (5) pero viola la restricción (4). Esto puede comprobarse sustituyendo X = 6 y Y = 5 en las restricciones y evaluando los resultados, como sigue:  Restricción 1 10 X + 15 Y  150 10 (6) + 15 (5)  150 135  150 y la restricción se cumple para este par de valores.  Restricción 2 14 X + 10 Y  160 14 (6) + 10 (5)  160 134  160 y la restricción se cumple para este par de valores. Esto mismo puede hacerse para el resto de las restricciones. Se sugiere al lector que compruebe que para el par de valores X = 7

y Y = 2

todas las restricciones se

satisfacen. La decisión X = 6 y Y = 5 no es permisible, puesto que como se vio, no se cumple con la proporción que debe existir entre las variables de 3 a 1. De los infinitos pares de valores de X y Y no negativos, algunos de estos pares o decisiones violan por lo menos una de las restricciones y otros las satisfacen. En un modelo como el que estudiamos solamente son admisibles las decisiones no negativas que satisfagan todas las restricciones. Estas decisiones se denominan como decisiones factibles o posibles y son precisamente estas las que pueden tomarse en cuenta.

17

Función objetivo Ahora la cuestión consiste en decidir, dentro de todas las decisiones factibles o posibles, cual es la mejor, desde el punto de vista del objetivo específico del problema. La gerencia general de Equipesa ha planteado dentro de los factores a considerar en la formulación del problema, que su objetivo específico es maximizar las utilidades totales. Supóngase que la utilidad total está dada por el símbolo Z. De esta manera, el objetivo será maximizar la relación siguiente: Utilidad total = utilidad por producir X cargadores + utilidad por producir Y zanjeadoras Como sabemos, la utilidad por cada cargador es 5000 pesos y 4000 por cada zanjeadoras. Sustituyendo en la igualdad planteada tenemos Z = 5000 X + 4000 Y Y como se quiere maximizar la utilidad total, entonces el objetivo será Maximizar Z = 5000 X + 4000 Y De todas las infinitas decisiones (soluciones posibles) que satisfacen las restricciones, la que dé el mayor valor de Z o sea la mayor utilidad, será lasolución óptima del problema planteado. O sea que la decisión buscada será aquella que maximice la utilidad total relativa al conjunto de todas las decisiones posibles y a tal decisión se le denomina solución óptima. Y como la utilidad total Z es una función de las variables X y Y, se denomina a esta función como función objetivo. Modelo completo del problema Obsérvese como a partir de una descripción verbal de un problema del mundo real se ha llegado a un modelo matemático completo con función objetivo y restricciones. El modelo completo será

18

Max Z = 5000 X + 4000 Y

función objetivo

sujeto a: 10 X + 15 Y  150

Disponibilidad en horas del

departamento A 14 X + 10 Y  160

Disponibilidad en horas del

departamento B 18 X + 10 Y  135

horas de comprobación o chequeo de la

calidad X - 3Y  0

proporción entre productos

X+ Y  5

producción combinada requerida

X , Y  0condición de no negatividad

Nótese que en este problema tanto las restricciones, como la función objetivo son funciones lineales de las variables de decisión. Como se recordará, la gráfica de una función lineal de dos variables es una línea recta. El éxito de la Programación Lineal y su efectividad en las aplicaciones, se deriva de la eficacia de las matemáticas lineales y del hecho evidente de que los modelos matemáticos lineales pueden ser rápidamente comprendidos y utilizados en situaciones reales por los dirigentes administrativos con poco o incluso, sin entrenamiento en matemáticas superiores. Guía para la formulación de modelos En lo que sigue se dará un conjunto de recomendaciones útiles para el aprendizaje del lector en el proceso de desarrollar el planteamiento matemático a partir de la formulación verbal de los modelos. Estas recomendaciones serán útiles por lo menos en una etapa inicial pues, cuando se adquiere la habilidad

necesaria, es posible

realizarlos de manera más directa. Los primeros pasos serán los siguientes:

19

1. Describir verbalmente las variables de decisión. 7.

Expresar cada restricción en palabras; al hacer esto, ponga atención cuidadosa en si la

restricción es un requerimiento de la forma  (al

menos tan grande como), una

limitación (no

mayor que)  , ó

=

(exactamente igual a). 3. Expresar el objetivo en palabras. En el proceso de construcción de un modelo de PL reviste particular importancia la definición clara y precisa de las variables de decisión. Es frecuente que estas puedan ser definidas a partir de una lectura cuidadosa del enunciado del problema. Además, en muchas ocasiones el estudiante tiende a confundir las variables con los parámetros del problema. Es importante que el alumno lea bien cual es el objetivo que se quiere alcanzar y a partir de esto, analice que tipo de solución debe lograrse para que ese objetivo sea cumplido. En el caso del problema cuyo modelo se ejemplificó arriba, el objetivo consistía en alcanzar el máximo posible de utilidad. Para lograr esto, sería necesario determinar el plan de producción que daría lugar a esa utilidad máxima. Y ese plan no es otra cosa que el número de cargadores frontales y zanjeadoras a producir en el periodo señalado. Una vez dados los pasos anteriores, es necesario decidir la notación simbólica de las variables. Habitualmente se utilizan para ello las últimas letras del alfabeto, x, y, z, w, etc. También se utiliza alguna letra con subíndice como x1, x2, etc. Posteriormente siga los pasos siguientes: 4. Represente las restricciones mediante símbolos, es decir, en términos de las variables de decisión y sus correspondientes coeficientes. 5. Represente la función objetivo en símbolos o sea, en términos de las variables de decisión y sus correspondientes coeficientes. En esta etapa es muy importante comprobar el trabajo para ver si las unidades son consistentes, es decir, realizar lo que habitualmente se conoce como análisis dimensional. Por ejemplo, si los coeficientes de la función objetivo están dados en

20

pesos por kilogramo, las variables de decisión que aparezcan en la función objetivo deben estar dadas en kilogramos, no en toneladas o libras. Análogamente,

compruebe que para cada restricción, las unidades del segundo

miembro son las mismas que las del primero. Por ejemplo, si una de las restricciones es una limitante de la forma  y el segundo miembro significa horas de trabajo de los operarios, el primer miembro en su conjunto, debe significar también horas de trabajo de los operarios. Si las variables de decisión son kilogramos, los coeficientes numéricos de cada variable de decisión del primer miembro de la restricción deberán ser horas de trabajo por kilogramo de producto. Dicho de otra forma, no se puede tener horas en un lado de la restricción y minutos o segundos, o libras o toneladas en el otro lado. De lo anterior se desprende que debe ser posible sumar todos los

términos que

aparecen en el miembro izquierdo de la restricción, o sea que deben ser aditivos. Por otra parte, cuando se vaya a proceder a la solución de un problema de PL, no deben aparecer variables en la parte derecha de la restricción, ni variables como denominadores de una fracción. Hay otro aspecto en la formulación que es conveniente esclarecer. Hemos visto que las restricciones de desigualdad son de la forma  ó . El lector debe tener en cuenta que los problemas de programación lineal no admiten signos de desigualdad estricta como < ó >. Los problemas de PL pueden ser divididos en dos grandes grupos: problemas de un solo periodo o problemas de varios periodos. Los primeros son aquellos en los que el modelo se utiliza para describir una situación en un punto o intervalo fijo de tiempo, y en el cual las condiciones del problema permanecen constantes. La decisión o curso de acción óptimo para estos problemas se determina sin tener en cuenta el curso de acción que se siguió o seguirá en periodos anteriores o posteriores. En este caso se buscará una solución óptima para un periodo fijo. Sin embargo, en la práctica real surgen numerosas situaciones en las que la gerencia debe tener en cuenta los cambios que pueden surgir en periodo futuros. Por ejemplo, 21

tendencias en la demanda, variaciones en los precios, variaciones en los costos producto de la inflación, variaciones de tipo estacional, etc. que podrían afectar la forma en que la empresa debe actuar en el presente. Algunos autores plantean que este tipo de problema puede resolverse como una serie de subproblemas que pueden ser considerados como problemas de un solo periodo cada uno de ellos. Sin embargo, por esta vía puede llegarse a una suboptimización, ya que la suma de las soluciones óptimas de cada período, resultaría inferior a la solución óptima que se alcanzaría considerando todos los subperíodos como un todo. Problemas de un solo periodo Analicemos ahora algunos ejemplos del primer tipo de situación, o sea problemas de tipo estático. La aplicación mas corriente de la PL es en los denominados problemas de asignación de recursos o sea, problemas en los que existen recursos limitados y se busca la mejor utilización de ellos. A esta categoría pertenece el ejemplo 2. Nota: En el problema que se expone a continuación se desarrollan restricciones que son típicas de los problemas de PL. Se recomienda que el alumno analice bien los principios seguidos para su construcción. Ejemplo 2. Programación de la producción La empresa fabricante de productos lácteos “La Vaquita” produce un variado surtido de estos. A los fines de simplificar la explicación del problema, consideraremos dos de estos productos: leche condensada y leche evaporada. El proceso de producción de ambos tipos de leche se realiza en cuatro departamentos: A, B, C y D. La dirección de la empresa desea determinar cual debe ser el surtido de producción diario de estos dos productos de manera que se maximice el valor de la producción diaria. Las cantidades a producir de estos dos productos están sujetas a las siguientes consideraciones:

22

Consideraciones 1.

Existen dos departamentos (A y B) en los que se producen ambos productos y las capacidades están medidas de la siguiente forma: en el A, si solo se produce leche condensada la capacidad es de 50 toneladas diarias y si solo se produjera leche evaporada, la capacidad asciende a 75 toneladas diarias.

2.

El departamento B tiene las mismas características que el A y las capacidades son de 60 toneladas de leche condensada o 65 toneladas de leche evaporada.

3.

En el departamento C solo se procesa leche condensada y su capacidad es de 40 toneladas diarias, mientras que en el departamento D solo se procesa leche evaporada y su capacidad asciende a 45 toneladas diarias.

4.

La materia prima fundamental para la fabricación de ambos tipos de leche, es la leche fresca. El consumo de leche fresca en la producción de leche condensada y evaporada es de 0.7 y 1.3 toneladas respectivamente por tonelada de producto terminado. La cantidad de leche disponible en la fábrica diariamente es de 65 toneladas.

5.

A ambos tipos de leche se le adiciona vitamina D. Esta vitamina se les adiciona mediante un granulado que la contiene en una proporción de 5.5 y 7.5 kilogramos de granulado por tonelada de producto terminado, siendo su disponibilidad de 2.475 toneladas diarias.

6. El producto terminado se vende al precio de $ 200 y $ 300 la tonelada. Construcción del modelo Definición de las variables y construcción del sistema de restricciones De acuerdo a los pasos dados en la guía en primer lugar será necesario identificar las variables cuyos valores constituirán la decisión a tomar por la gerencia de la empresa. En este caso esas variables estarándadas por: x1: toneladas de leche condensada a producir diariamente x2: toneladas de leche evaporada a producir diariamente

23

a partir de esta definición pueden construirse las restricciones del problema. 1. Capacidad del departamento A En este punto vemos que esta capacidad esta dada por limites en la producción de uno u otro artículo en este departamento. En este tipo de restricción es necesario considerar que la capacidad total del departamento, en cualquier tipo de producto equivale al 100 %. Una tonelada de leche condensada utilizará

150 de la capacidad total del

departamento y una tonelada de leche evaporada utilizará 175 de la capacidad total del departamento. Esto podría escribirse literalmente así: (Parte de la capacidad total utilizada por una tonelada de leche condensada)(Número de toneladas de leche condensada a producir) + (Parte de la capacidad total utilizada por una tonelada de leche evaporada)( Número de toneladas de leche condensada a producir)  Capacidad total disponible En términos matemáticos se tendrá la restricción x1 50



x2 75

1

2) Capacidad del departamento B La formulación de la situación de este departamento está expresada en forma similar a la del departamento A. Siguiendo el mismo razonamiento aplicado allí, tenemos que la restricción correspondiente será x1 x  2 1 60 65

3) Capacidad del departamento C En este departamento solo se trabaja sobre la leche condensada, teniendo una capacidad límite de 400 toneladas. Literalmente esto se escribiría así Número de toneladas de leche condensada a producir



Capacidad total

disponible

24

En términos matemáticos tenemos: x1 40 4. Capacidad del departamento D Este departamento tiene las mismas características del C, y por el mismo procedimiento se llega a la restricción x2 45 5.Disponibilidad de leche fresca. En este caso se plantea la siguiente desigualdad verbal (Toneladas de leche fresca necesarias

para elaborar una tonelada de leche

condensada) (No. de toneladas a elaborar de leche condensada) + (Toneladas de leche fresca necesarias para elaborar una tonelada de leche evaporada) (No. de toneladas a elaborar de leche evaporada)  Total de leche fresca disponible. Escribiendo en forma simbólica la desigualdad anterior se tiene: 0.7 x1 + 1.3 x2  65 6. Disponibilidad de vitamina D Esta restricción tiene la misma forma que la anterior y puede escribirse como: 5.5 x1 + 7.5 x2 2 4 75 7.

No negatividad: x1, x2 0

Construcción de la función objetivo El objetivo planteado por la gerencia es maximizar el valor de las ventas de la producción conjunta de los dos productos. En este caso podemos plantear que: Valor de las ventas = (Precio de venta de una tonelada de leche condensada)(número de toneladas de leche condensada a elaborar) + (precio de venta de una tonelada de leche evaporada) (número de toneladas de leche evaporada a elaborar). En términos matemáticos se escribirá: 25

Z = 200 x1 + 300 x2 y como lo que se quiere alcanzar es el valor máximo posible de Z , entonces se escribirá: max Z = 200 x1 + 300 x2 El modelo económico matemático planteado de manera completa quedaría

maximizar Z = 200 x1 + 300 x2 sujeto a x1 50 x1 60



x2



x2

75

65

1

1

x1 40 x2 45 0.7 x1 + 1.3 x2 65 5.5 x1 + 7.5 x2  2 4 75 x1, x2 0 Ejemplo 3. Consideración de los costos fijos y los costos variables. En muchos casos de la práctica se dan dos tipos de costos: costos fijos y costos variables. En los problemas de PL, son los costos variables los que tienen importancia. Los costos fijos ya han sido pagados o lo serán independientemente de la alternativa escogida para el programa productivo, lo que significa que ninguna decisión puede afectarlos. Por ejemplo, supóngase una fábrica de puertas y ventanas de aluminio. Supóngase además que la Administración ha comprado 800 y 500 kilogramos de dos clases de aluminio (tipo 1 y tipo 2) han sido comprados para una entrega futura a los precios convenidos de $ 5 y $ 10 el kilogramo, respectivamente, y que se ha firmado un contrato. El problema del administrador, en este caso es decidir el uso óptimo de esos 1300

kilogramos de aluminio, quizá

para maximizar el beneficio obtenido de la

producción de puertas y ventanas de aluminio.

26

Asociados con estos dos productos se esperan ingresos y costos variables producidos durante su elaboración (costos de maquinaria, troquelado, etc.). En la formulación de este tipo de modelos los costos fijos de $9 000 asociados con la compra de aluminio contratada carecen de importancia. Esta cantidad ya ha sido gastada y por lo tanto las cantidades para gastos ya no son variables. Las variables serán, si acaso, cuantos productos se elaborarán y el costo relevante en esta determinación es sólo el costo variable. La construcción del modelo correspondiente a la descripción anterior será de la forma siguiente: Sea x = número de puertas que serán producidas (variable de decisión) y = número de ventanas que se producirán (variable de decisión) 10 = ingreso por cada puerta 30 = ingreso por ventana 4 = costo de producción por puerta (costo variable) 12 = costo de producción por ventana (costo variable) Por cada producto se debe calcular lo que los contadores llaman contribución marginal por unidad, o sea, la diferencia entre el ingreso por unidad y el costo variable por unidad. Las contribuciones marginales por unidad son: para las puertas: 10  4 = 6 para las ventanas: 30  12 = 18 Supongamos que cada puerta utiliza un kilogramo de aluminio de tipo 1 y cuatro kilogramos de aluminio de tipo 2 y que cada ventana utiliza dos kilogramos de aluminio de tipo 1 y dos kilogramos de aluminio de tipo 2. Entonces, el modelo será Maximizar Z = 6 x + 18 y sujeto a: x + 2 y  800 limitación del aluminio de tipo 1 4 x + 2 y  500 limitación del aluminio de tipo 2 x, y  0

27

Otra manera de advertir la irrelevancia de los costos fijos es observar que la función objetivo del problema es el margen de aportación total. El ingreso neto o utilidad, será: utilidad neta = utilidad variable  costo fijo = 6 x + 18 y  9 000 Sin embargo, si se encuentra un conjunto de valores para las variables, tal que maximice a la función 6x + 18  9 000, esos mismos valores maximizarán 6x + 18 y. El término constante 9000 puede no ser tomado en cuenta. Otros ejemplos de formulación de problemas y su correspondiente modelo económico matemático de optimización lineal. En lo que sigue se dará un conjunto de ejemplos de problemas diversos que le servirán para consolidar la habilidad en construir los modelos económicos matemáticos a partir de su formulación verbal y por tanto, la habilidad de llevar problemas del mundo real a su formulación matemática. La creación de esta habilidad es de primordial importancia para el administrador o el gerente, pues será él quien en última instancia tendrá que juzgar acerca de la validez del modelo y adoptar la decisión correspondiente en la empresa. Ejemplo 4. Búsqueda de una dieta óptima Una empresa productora de piensos debe producir una cierta cantidad de alimento animal. Se conoce que una libra de este alimento debe contener proteínas, carbohidratos y grasas en las siguientes cantidades mínimas: proteínas, 3 onzas; carbohidratos, 5 onzas; grasas, 4 onzas. Se van a mezclar cuatro tipos de alimentos en diversas proporciones para lograr que cada libra del pienso satisfaga los requerimientos planteados. Los contenidos y precios de cada libra (16 onzas) de cada alimento se dan en el cuadro siguiente:

28

Alimento 1 2 3 4

Contenidos y precios por libra de alimento Contenido de Contenido de Contenido proteína carbohidratos de grasa (onzas) (onzas) (onzas) 3 7 5 5 4 6 2 2 6 3 8 2

Precio $ 4 6 3 2

Construcción del modelo matemático: En este problema designaremos por conveniencia, como xi, la proporción del alimento i que habrá en una libra de pienso animal (i = 1, 2, 3, 4). El planteamiento del modelo sería así min Z = 4 x1 + 6 x2 + 3 x3 + 2 x4 sujeto a: 3 x1 + 5 x2 + 2 x3 + 3 x4 3 7 x1 + 4 x2 + 2 x3 + 8 x4 5 5 x1 + 6 x2 + 6 x3 + 2 x4  4 x1 +

x2 + x3 +

x4 = 1

x1, x2, x3,x4  0 La solución del modelo proporcionará el conjunto de valores de las variables x1, x2, x3, x4 tales que al sustituirlos en la función objetivo dan el precio de compra mínimo (Z), para el conjunto de alimentos necesarios para la elaboración de una libra de pienso animal, de manera que cumpla con los requerimientos necesarios en proteína, carbohidratos y grasa. Ejemplo 6. Planeación financiera El grupo financiero Banfin está tratando de determinar su plan de inversiones para los próximos dos años. En estos momentos, el Banfin tiene disponibles $ 2 400000 de pesos para invertir. El Banfin espera recibir en lo próximos 6,12 y 18 meses un flujo de ingresos procedentes de inversiones previas. Estos ingresos se dan en la siguiente tabla:

29

Ingresos del Banfin procedentes de inversiones anteriores (USD) 6 meses 12 meses 18 meses IngresoS 500 000

400 000

180 000

La compañía tiene dos proyectos en los que está considerando participar.  Uno de esos proyectos es una empresa de inversiones turísticas. En el cuadro siguiente se muestra el flujo de caja que se tendría si el Banfin participara a un nivel del 100 % en el proyecto turístico (los números negativos representan inversiones y los positivos ingresos). De esta manera, para participar en este proyecto al nivel del 100 % el Banfin tendría que desembolsar $1 000000 de pesos de inmediato. A los seis meses invertiría otros $ 700 000, etc. Flujo de caja del proyecto turístico (USD) Inicial Ingresos

6 meses 12 meses 18 meses

 1 000000  700 000 1 800 000

400 000

24 meses 600 000

 El otro proyecto consiste en hacerse cargo de la operación de una instalación industrial que produce productos que tienen un amplio consumo en las instalaciones turísticas. Esta instalación requiere realizar un grupo de reparaciones iniciales y modernización de algún equipamiento. En el cuadro siguiente se muestra el flujo de caja del proyecto a un 100 % de participación: Flujo de caja del proyecto industrial (USD) Inicial Ingresos

6 meses

 800 000 500 000

12 meses 18 meses 24 meses  200 000 700 000

2 000000

Debido a las regulaciones vigentes, al Banfin no se le permite pedir dinero prestado. Sin embargo, al comienzo de cada periodo de seis meses todos los fondos excedentes que no hayan sido colocados ni en el proyecto turístico ni en el proyecto industrial, se invierten con un interés del 7 % para ese periodo de seis meses. El Banfin puede 30

participar en cualquiera de los proyectos a un nivel menor del 100 %, pero en este caso todos los flujos en efectivo de ese proyecto se reducirán en forma proporcional. Esto quiere decir, que si el Banfin elige participar en el proyecto turístico a un nivel del 20 %, el flujo de caja asociado con esta decisión sería igual a 0.2 veces los datos de la tabla correspondiente dada arriba. El Banfin debe decidir que parte de los $ 2 400 000 en efectivo debe invertir en cada proyecto y cuánto debe colocarse simplemente por el interés del 7% anual. El objetivo de la gerencia consiste en maximizar el efectivo disponible al final de los 24 meses. Construcción del modelo Las restricciones del modelo deben expresar que al inicio de cada uno de los cuatro periodos considerados dinero invertido = dinero en efectivo Definición de las variables de decisión x : participación fraccionaria en el proyecto turístico y : participación fraccionaria en el proyecto industrial w1 : fondo inicial excedente, no invertido en el proyecto turístico ni en el industrial y que se invertirá al 7 % de interés. w2 : fondo excedente a los 6 meses, a invertir al 7 %. w3 : fondo excedente a los 12 meses, a invertir al 7 % w4 : fondo excedente a los 18 meses a invertir al 7 % Obsérvese que las dos primeras variables esenciales representan porcentajes de participación en los dos proyectos explicados, mientras que las demás representan cantidades de dinero. La primera restricción tendrá en cuenta que inversión inicial = fondo inicial disponible lo que en términos matemáticos se escribiría como 1 000 000 x + 800 000 y + w1 = 2 000 000 31

Tomando en cuenta que, debido a los intereses que se percibirán, w 1 se convertirá en 1.07 w1 después de 6 meses y que lo mismo ocurre con w2, w3,w4, las tres restricciones restantes serán 700 000 x + w2 =

500 000 y + 1.07 w1 + 500 000

200 000 y + w3 = 1 800 000 x + 1.07 w2 + 400 000 700 000 y + w4 =

400 000 x + 1.07 w3 + 380 000

y la función objetivo consistirá en maximizar el efectivo disponible al final de los 24 meses, el cual estaría dado por max Z = 600 000 x + 2 000 000 y + w4 El modelo económico matemático quedaría como se muestra debajo max Z = 600 000 x + 2 000 000 y + w4 sujeto a 1 000 000 x + 800 000 y + w1 = 2 000 000 700 000 x + 500 000y  1.07 w1 + w2  1 800 000 x + 200 000 y  400 000 x + 700 000 y x

 1.07 w2 + w3=

=

500 000

400 000

 1.07 w3 + w4=

380 000

1

y 1 x 0, y  0, wi 0, i = 1,2,3,4

Ejemplo 7. Un caso de análisis restringido del punto de equilibrio La compañía Astilleros del Caribe S.A. produce pequeñas embarcaciones para el turismo nacional y para la venta en el exterior, así como embarcaciones de pesca. Estas embarcaciones son de tres tipos, a los cuales se les denomina genéricamente como Pegaso, Sirena y Tritón. En el cuadro siguiente se dan los datos referidos a las ganancias y costos programados para el periodo considerado:

32

Precio de venta Embarcación unidad ($) Pegasos Sirenas Tritones

$ 10 000 7 500 15 000

por Costo variable

por Costo fijo ($)

unidad ($) $ 5 000 3 600 8 000

$ 5 000 000 3 000 000 10 000 000

De los datos se desprende que el monto de los costos fijos es muy grande. Como vimos anteriormente, esta es una cantidad que se paga, independientemente del número de embarcaciones que se produzca. Por esta razón, el mismo costo fijo de $ 3 000 000 de las embarcaciones tipo Sirena se pagará independientemente de si se producen 5, 10 ó 100 unidades. Este costo incluye incluso, los gastos por modificaciones de diseño, reconstrucción de molduras y viajes de prueba. El gráfico 1 muestra el análisis del punto de equilibrio del tipo Pegaso. Este gráfico muestra que si la compañía fuera a producir solo Pegasos, tendría que producir por lo menos 1000 embarcaciones para llegar al punto de equilibrio. La compañía confronta algunos problemas en la definición del programa de producción. Para el próximo periodo de planeación, la gerencia ha formalizado contratos para la producción de 700 Pegasos. Otro cliente ha solicitado 400 Tritones. Además se han realizado estudios de mercado que indican que la demanda de Sirenas será de por lo menos 300 unidades. Además, la gerencia de la compañía está altamente interesada en vender lo suficiente para alcanzar el punto de equilibrio, pero debe hacerlo tomando en cuenta que hay posibilidades de ventas de los tres productos y que existen compromisos contraídos de antemano. Construcción del modelo En primer lugar, será necesario definir las variables de decisión del problema. Consideremos que son x1 : Número de Pegasos a producir en el periodo considerado. x2 : Número de Sirenas a producir en el periodo considerado. x3 : Número de Tritones a producir en el periodo considerado. 33

En este problema, inicialmente la administración observa que, en el punto de equilibrio Costo total = Ingreso total Utilizando las variables definidas y la ecuación de equilibrio dada arriba, se tendrá:

$

o

ni

c ió

n

Fu 10 000 000

5 000 000

s re ng

osto

nC nció

Fu

Cantidad de punto de equilibrio 1 000

No. de Pegasos

Gráfico 1 10 000 x1 + 7 500 x2 + 15 000 x3 = 5 000 x1 + 3 600 x2 + 8 000 x3 + 18 000 000 o también 5 000 x1 + 3 900 x2 + 7 000 x3 = 18 000 000 Como se observa por el tipo de ecuación, existe un número infinito de conjuntos de valores para las variables x1, x2, x3 que satisfacen esta restricción. Entonces, en el caso de productos múltiples, hay muchos puntos de equilibrio, mientras que en el caso de producto simple hay solo uno, tal como se deduce de la figura que aparece en el enunciado del problema. Por eso, en el caso de producto múltiple, la gerencia debe especificar una restricción adicional para identificar un punto particular de equilibrio que le interese. En este caso, partiendo del hecho de que esta compañía es relativamente nueva y está experimentando problemas de flujo de caja asociados con un rápido crecimiento, a la gerencia le gustaría minimizar la salida de capital. Los costos fijos son inevitables, por

34

lo que la meta consistirá en minimizar los costos totales variables. El monto total de los costos variables, que en este caso será la función objetivo, es 5 000 x1 + 3 600 x2 + 8 000 x3 El modelo completo que refleja las restricciones de ruptura de equilibrio, así como los requerimientos preestablecidos y limitaciones de la demanda, es el siguiente: min Z = 5 000 x1 + 3 600 x2 + 8 000 x3 sujeto a 5 000 x1 + 3 900 x2 x1 x2 x3

+ 7 000 x3 = 18 000 000 700 400 300

x1, x2, x3 0

Ejemplo 8. Un problema de mezcla de ingredientes para elaborar productos terminados La

corporación

Agrisosten

posee una planta

dedicada a la elaboración de

fertilizantes para diferentes tipos de cultivos agrícolas. Estos fertilizantes se elaboran mezclando un conjunto de productos, fundamentalmente nitrógeno, fosfato y potasio, que deben combinarse en diferentes proporciones según sea el cultivo agrícola al cual van destinados y según las características de los suelos en los cuales van a ser utilizados. En este caso, se está planeando la elaboración de tres fertilizantes básicos, los cuales son: 5105 , 51010, 101010. Estos números representan en cada caso el porcentaje de cada uno de los componentes (nitrato, fosfato y potasio) en cada una de las mezclas. Es decir, la empresa esta interesada en mezclar estos ingredientes activos conjuntamente con determinados ingredientes inertes, de los que se dispone en cantidades suficientes para producir las cantidades de las tres mezclas que proporcionen la máxima ganancia. La planta dispondrá en el próximo mes de 1000 toneladas de nitrato, 1800 toneladas de fosfatos y 1200 toneladas de potasa. Estas cantidades han sido adquiridas u ordenadas y se recibirán a comienzos del periodo a planificar.

35

Los costos de mezclado, empaquetado y ventas son idénticos para las tres mezclas y ascienden a $ 15.00 por tonelada. Los costos de cada uno de los ingredientes se muestran en el cuadro siguiente. Costos de los ingredientes por Tonelada(USD) Nitrato 160.00 Fosfato 40.00 Potasio 100.00 Ingredientes 5.00 inertes Los precios de venta de los productos terminados se muestran en el cuadro siguiente. Todo el fertilizante producido puede ser vendido a esos precios, pero hay un compromiso de vender 6000 toneladas de 5105 durante el periodo que se planifica. Precio de los fertilizantes terminados (por tonelada)(USD) 5105

51010

101010

71.50

68.00

75.00

Se necesita plantear el modelo económico matemático lineal que permita calcular la cantidad de cada una de las tres mezclas básicas de modo que se obtenga la ganancia máxima posible. Construcción del modelo No está claro en la formulación cual es la utilidad que se alcanza por cada tipo de fertilizante, hay que deducirla de la información que se brinda. Inicialmente se deberá elaborar un estado de costo por tonelada de

cada tipo de

fertilizante:

36

Tipo 5105 (USD) Costo del nitrato por tonelada 10.00 Costo del fosfato por tonelada 8.00 Costo del potasio por tonelada 8.00 Costo de los ingredientes inertes 8.00 Costo total de los ingredientes Costo de mezclado 15.00 Costo por tonelada$ 49.00

(0.05)(200 )

=

(0.10) ( 80)

=

(0.05) ( 160)

=

( 0.80) ( 10)

=

34.00

Conociendo el precio de venta, se puede calcular la utilidad por tonelada de este tipo de fertilizante: 71.50  49.00 = 22.50 Tipo 51010 (USD) Costo del nitrato por tonelada (0.05)(200 ) = 10.00 Costo del fosfato por tonelada (0.10) ( 80) = 8.00 Costo del potasio por tonelada (0.10) ( 160) = 16.00 Costo de los ingredientes inertes ( 0.75) ( 10) = 7.50 Costo total de los ingredientes 41.50 Costo de mezclado 15.00 Costo por tonelada 56.50 La utilidad será 68.00  56.50 = 11.50 Efectuando un cálculo similar a los anteriores de llega a que la utilidad del fertilizante 101010 será

de

75.00  66.00 = 9.00

Definición de las variables Xj : Toneladas métricas de fertilizante de tipo j a producir para el mes siguiente (j = 1, 2, 3) Planteamiento de las restricciones 1. Disponibilidad de nitrato 0.05 x1 + 0.05 x2 + 0.10 x3 1100

37

2. Disponibilidad de fosfatos 0.10 x1 + 0.10 x2 + 0.10 x3 1800 3. Disponibilidad de potasio 0.05 x1 + 0.10 x2 + 0.10 x3 2000 4. No negatividad x1, x2, x3 0 Función objetivo Max Z = 22.50 x1 + 11.50 x2 + 9.00 x3 Ejemplo 9. Determinación de estructura de siembra en una empresa agrícola La empresa de cultivos varios “Vega Grande” es de tamaño medio, pues dispone de 130 hectáreas en las que habitualmente se producen tres cultivos fundamentales: frijol, maíz y maní (cacahuetes). Los productos que se obtienen en la empresas son para consumo de sus miembros y para vender en el mercado normal. De acuerdo a su organización, en primer lugar deben satisfacer las necesidades de sus miembros y los excedentes de producción son los que se llevan a vender en el mercado. La siguiente tabla resume, para cada producto, el número de quintales (qqs.) que los miembros solicitan, la demanda máxima del mercado (en qqs.) y la utilidad estimada por qq. Cultiv o

Frijol Maíz Maní

Rendimient Demanda de o los miembros ( (Kgs. por kgs.) há) 420 2000 200 5000 70 1000

Demanda del mercado (en kgs)

Utilidad (USD por kg.)

10 000 8 000 3 000

.90 .70 2.50

En este problema es evidente la necesidad de que la empresa maneje su contabilidad de costos de una manera confiable, pues un dato de suma importancia

para la

optimización es el costo por hectárea de cada uno de los cultivos o sea el costo por unidad de área (caballerías, caroes, hectárea, cordeles, rozas, etc. según se acostumbre).

38

Otro aspecto en el que debe existir suficiente claridad es en los estimados de rendimiento por unidad de superficie (quintales por caballería, quintales

por caró,

toneladas por hectárea, etc.) La empresa ha trabajado en la determinación de las fichas de costo de los cultivos y ha llegado a la conclusión de que una hectárea de frijol, maíz y maní le cuesta 900, 700y 550USD respectivamente. De acuerdo a las gestiones realizadas, se cuenta con un crédito del Banco para el desarrollo de los cultivos que asciende a 90 000 USD. Se le pide plantear el modelo de optimización lineal cuya solución permita determinar el área a dedicar a cada uno de los cultivos de modo tal que se maximicen las utilidades. Construcción del modelo Se trata de un modelo de análisis de actividad en la agricultura. Las variables pueden definirse como: xj, que representa el número de hectáreas que se deben sembrar del cultivo j. El sistema de restricciones en este caso sería a) Disponibilidad de tierra: x1 + x2 + x3 130 Esta restricción indica que las tierras a cultivar de los tres cultivos no pueden sobrepasar el total de tierra disponible. b) Demanda de consumo interno 420 x1  2000 200 x25000 70 x3 1000 c) Demanda del mercado 420 x1 10 000 200 x2

8000

70 x1 3000 d) Restricción de presupuesto 900 x1 + 700 x2 + 550 x3 90 000 39

e) no negatividad xj 0, j = 1,2,3 Función Objetivo: max Z = 0.9 (420 x1) + 0.70 (200 x2) + 2.5 (70 x3) Haciendo las operaciones indicadas en las restricciones (c) y en la función objetivo se tendrá el siguiente modelo max Z = 378 x1 +140 x2 + 175 x3 sujeto a: x1 + x2 + x3 130 x1

4.7619

x2 25 x3 14.2857 x1 23.8095 x2 40 x3 42.8571 900 x1 + 700 x2 + 550 x3 90 000 xj 0, j = 1,2,3 Ejemplo 10. Corte de materiales Una fábrica de muebles desea establecer el programa de corte óptimo de planchas de madera prensada para la producción de tres tipos de mesas que por su diseño permiten utilizar esta clase de madera en su fabricación. El ancho de las mesas a construir es de 60, 40 y 30 cms. para cada tipo, mientras que el largo coincide con el ancho de las planchas de madera prensada que se reciben de los almacenes, ya que la fábrica recibe suministros de dos tipos de planchas de madera prensada que se diferencian por su largo y grosor.

40

Las disponibilidades de estas planchas se muestran en la siguiente tabla:

Tipo 1 Tipo 2

Largo

Ancho

Grosor

170 cms. 150 cms.

20 cms. 20 cms.

10 mm 8 mm.

Disponibilidad (unidades) 6 00 5 00

De acuerdo a las especificaciones técnicas para la construcción de las mesas, se conoce que las de 30 cms. solo pueden fabricarse utilizando planchas de 8 mm.de grosor. La gerencia de la empresa está

interesada en

minimizar los desperdicios de

materiales. Se conoce que el desperdicio máximo admisible por plancha es de 15 cms. y que en el periodo deben ser garantizadas las demandas mínimas para cada uno de los tipos de mesas, las cuales se indican en el siguiente cuadro: Tipo de mesas Mesa de tipo 1 Mesa de tipo 2 Mesa de tipo 3

Demanda mínima 80 unidades 95 unidades 105 unidades

Se le pide construir el modelo económico matemático que permita encontrar el número de planchas a cortar de cada tipo y al mismo tiempo, cumplir con el objetivo planteado. Solución En primer lugar es necesario establecer cuales son las combinaciones de corte posibles con los distintos tipos de planchas para los tres tipos de mesas que se desea fabricar. Estas combinaciones, para las planchas de madera de 170 cms. de largo serán Combinaciones de corte posibles Planchas de 170 cm es de largo Número de piezas de: 60 cms40 cms. Desperdicio Variante 1 2 1 10 Variante 2 4 10 

41

Combinaciones de corte posibles Planchas de 150 cms. de largo Número de piezas de:60 cms. 40 cms. Desperdicio Variante 1 2 1  Variante 2 1 2  Variante 3 1 3  Variante 4 3 1  Variante 5 2 2  Variante 6 5  

30 cms 0 10 0 0 10 0

Definición de las variables de decisión Las variables de decisión serán: x1 : cantidad de planchas a cortar de 170 cms según la variante de corte 1. x2 : cantidad de planchas a cortar de 170 cms según la variante de corte 2. x3 : cantidad de planchas a cortar de 150 cms según la variante de corte 1. x4 : cantidad de planchas a cortar de 150 cms según la variante de corte 2 x5 : cantidad de planchas a cortar de 150 cms según la variante de corte 3 x6 : cantidad de planchas a cortar de 150 cms según la variante de corte 4. x7 : cantidad de planchas a cortar de 150 cms según la variante de corte 5. x8 : cantidad de planchas a cortar de 150 cms según la variante de corte 6 Construcción de sistema de restricciones x1 + x2 600 planchas de 170 cms. x3 + x4 + x5 + x6 + x7 + x8 500 planchas de 150 cms. 2x1

+

x1 + 4x2 x3

2x3 + x4 + x5 800 mesas de 60 cms. + 2x4

+ 3x5 +

+ 3x6 + 2x7 950 mesas de 40 cms. x6 + 2x7 + 5x8

 105 mesas de 30 cms.

La función objetivo será: Min Z = 10x1 + 10x2 + 0x3 + 10x4 + 0x5 + 0x6 + 10x7 + 0x8 desperdicio

42

Ejemplo 11. Distribución de inversiones o asignación de capital El

grupo

corporativo

Electrodom

dedicado

a

la

producción

de

artículos

electrodomésticos enfrenta el problema de determinar cuáles proyectos de crecimiento debe emprender en los próximos cuatro años. La gerencia está consciente de que tiene una cantidad limitada de fondos para inversiones de capital y por tanto no puede financiar todos los proyectos que necesita acometer. A cada uno de estos proyectos se le ha caracterizado determinando su valor presente y el requerimiento (costo) asociado de capital.

Cada proyecto tiene diferentes

requerimientos de capital par los próximos cuatro años. En la tabla siguiente

se

muestran el valor presente estimado, los requerimientos de capital y el capital disponible proyectado para cada uno de ellos. Valor actual, requerimientos de capital y capital disponible ($) Valor presente Estimado(USD)

Tipo de proyecto

Expansión

de

la

180 000

Requerimientos de capital Año 1 Año 2 Año 3 Año 4 (USD) 30000 40000 40000 30000

planta Nueva maquinaria Investigación nuevos mercados Ampliación

20 000

12000

8000

0

4000

30000

20000

20000

20000

20000

30000

40000

10000

65000

80000

80000

50000

sobre 72 000 del

80 000

almacén Fondos disponibles de capital

La dirección de la empresa necesita preparar programar las asignaciones de capital que debe hacer para cada uno de los próximos cuatro años y cuales proyectos se deben financiar bajo este plan.

43

Construcción del modelo En este problema se necesita seleccionar cuales proyectos deben financiarse completos, es decir, no pueden financiarse fracciones de proyecto. Además si se financia un proyecto el primer año, deberá continuarse su financiamiento todos los años en que está previsto su desarrollo. La solución consistirá por tanto, en aceptar o rechazar un proyecto dado. Utilizando el enfoque de la Programación Lineal existe la posibilidad de que aparezcan en la solución valores fraccionarios. Estos valores pueden interpretarse como que no existen suficientes fondos para financiar el proyecto completo, y en este caso el proyecto se rechazaría. Obviamente, una solución de esta índole puede dar como resultado una solución no factible o que no pueda ser puesta en práctica. Si un valor fraccionario en la solución fuera cercano a 1 y otro fuera cercano a cero, pudiera realizarse el análisis para determinar si es posible pasar los recursos del segundo proyecto

al primero y si esto generaría una solución posible, aunque no

necesariamente óptima. A pesar de esto, la solución de este problema mediante Programación Lineal puede proporcionar información suficiente para analizar la situación existente. Este problema será analizado más adelante en el capítulo dedicado a la Programación en Enteros. Teniendo en cuenta las características especiales de este problema, es importante tener en cuenta las siguientes consideraciones al iniciar la construcción del modelo: 1.

Los requerimientos (costos) totales de capital en un año dado, no pueden exceder los fondos de capital disponibles en ese año.

2.

Un proyecto que se financie en alguno de los años, debe ser financiado en todos los años.

3.

En principio, un valor fraccionario de financiamiento para un proyecto es una solución aceptable pero se interpreta como que el proyecto no se emprende.

Definición de las variables La variable podría definirse como 44

xj: proporción que indica el porcentaje en que se financia el proyecto j. Si x j = 1, el proyecto se financia completo, si xj< 1, no se financia ( j = 1, 2, 3, 4). Construcción del sistema de restricciones 1. Requerimientos de capital en el primer año 30 000 x1 + 12 000 x2 + 30 000 x3 + 20 000 x4 65 000 2. Requerimientos de capital en el segundo año 40 000 x1 + 8 000 x2 + 20 000 x3 + 30 000 x4 80 000 3. Requerimientos de capital en el tercer año 40 000 x1 + 0 x2 + 20 000 x3 + 40 000 x4 80 000 4. Requerimientos de capital en el cuarto año 30 000 x1 + 4 000 x2 + 20 000 x3 + 10 000 x4 50 000 5. Restricción sobre el valor de la variable para obligar al financiamiento fraccionario del proyecto. x1 1, x2 1, x3 1, x4 1 6- Condición de no negatividad x1 0, x2 0, x3 0, x4 0 7.Una condición indispensable es que el proyecto que se financia un año deba ser financiado en todos los años. Esto se garantiza por la propia definición de la variable al ser ella una proporción que se mantiene en todos los años. Construcción de la función objetivo maximizar Z = 180 000 x1 + 20 000 x2 + 72 000 x3 + 80 000 x4 Si este problema es resuelto mediante alguno de los métodos conocidos y que se estudiarán más adelante se tendrá que x1 = 1, x2 = 1, x3 =0.15 y x4 = 0.92. De acuerdo a la condición existente de que solo se aceptarán los valores enteros de la variable, solo se financiarán los proyectos 1 (expansión de la planta) y 2 (nueva maquinaria). Podría analizarse la posibilidad de pasar los fondos (0.15) asignados en la solución al

45

proyecto 3 al proyecto 4 y determinar si es la solución así obtenida es factible y/o aceptable aunque no sea óptima. Ejemplo 14. El problema de asignación El

grupo hotelero Cubamar tiene tres

proyectos turísticos

para

cuyo desarrollo

necesita entrar en asociación con algunas empresas extranjeras. Con este objetivo, ha sacado a licitación los proyectos y ha recibido un conjunto de propuestas y ahora confronta el problema de determinar con cuales empresas entrará en asociación. Los posibles socios han realizado propuestas contentivas de las diferentes sumas con que están dispuestos a participar. En la siguiente tabla se denotan por c 1, c2 y c3 y por p1, p2 y p3 a los proyectos. Las cantidades ofrecidas se expresan en cientos de miles de dólares.

Contratistas c1 C2 c3

Proyectos(100 000USD) p1 p2 p3 28 32 36 36 28 30 38 34 40

El problema consiste en determinar cómo asignar los proyectos para maximizar el aporte total de capital que se tendrá. Se asume que a cada inversionista se le asignará un solo proyecto. Construcción del modelo Si se toma consideración la magnitud del problema presentado, la determinación de las asignaciones se podrá realizar muy fácilmente, pues aquí solo existen 3( 321) o sea 6 maneras posibles de realizar las asignaciones. Esto puede verse en la tabla siguiente:

46

Asignacione s c1 c2 c3 C1 c3 c2 c2 c3 c1 C2 c1 c3 c3 c1 c2 c3 c2 c1

Aportes totales (en cientos de miles de dólares) 96 92 106 108 100 102

En esta tabla se observa, que la mejor manera de realizar la asignación es aquella que proporciona 10 800 000 (USD) asignando el proyecto 1 al contratista 2, el proyecto 2 al contratista 1 y el proyecto 3 al contratista 3. La cuestión cambia cuando el número de asignaciones posibles aumenta. Si se tuvieran 8 proyectos y ocho posibles asociados, entonces habría

8 = 40320 posibles formas de realizar las asignaciones. Esto es posible

resolverlo mediante un problema de Programación Lineal como el siguiente: Definición de las variables Las variables en este caso serán de dos subíndices. xij : variables que representan la relación entre el contratista i y el proyecto j, en donde xij = 0 indica que el proyecto no se asignó; xij = 1 indica que el proyecto si se asignó, (i= 1, 2, 3 ; j = 1, 2, 3). Sistema de restricciones 1) Restricción referida al posible asociado 1. x11 + x12 + x13 = 1 2. Restricción referida al posible asociado 2: x21 + x22 + x23 = 1 3. Restricción referida al posible asociado 3: x31 + x32 + x33 = 1 Estas restricciones indican que a cada contratista solo se le podrá asignar un proyecto. 4. Restricción del proyecto 1: x11 + x21 + x31 = 1

47

5. Restricción del proyecto 2 x12 + x22 + x32 = 1 6. Restricción del proyecto 3 x13 + x23 + x33 = 1 Las restricciones 4, 5 y 6 garantizan que cada proyecto deberá ser asignado solo una vez. Nótese que no existe ninguna unidad de medida asociada con las restricciones. Las variables xij solo pueden tomar los valores 1 ó 0, por tanto solo juegan el papel de vínculo entre los proyectos con los contratistas. Construcción de la función objetivo Los coeficientes de la función objetivo serán las contribuciones que hará cada posible socio al serle asignado alguno de los proyectos. O sea c11 = 2 800 000, c12 = 3 200 000, . . . , c33 = 4 000 000 Por tanto, la función objetivo se podrá escribir de la manera siguiente: Max Z = 28 x11 + 32 x12 + 36 x13 + 36 x21 + 28 x22 + 30 x23 + 38 x31 + 34 x32 + 40 x33 Si la función objetivo de este problema tuviera como coeficientes los costos de los proyectos, la forma del modelo sería la misma que la del problema de transporte el cual se estudia en otro capítulo del libro.

La

diferencia esencial con el

problema de

transporte es que en este caso, cada recurso o asignación (es decir, un obrero, una máquina o un espacio de tiempo) debe asignarse en forma total o única a una actividad o asignación específica (por ejemplo, un trabajo, un lugar o un evento). Algunos problemas de asignación incluyen

la asignación de n personas o máquinas a m

trabajos diferentes, la asignación de tripulaciones a vuelos, la asignación de personas a puestos de trabajo, etc. El objetivo de un problema de asignación bien puede ser maximizar

utilidades, aunque puede ocurrir que se presenten otros objetivos.

Por

ejemplo, el objetivo de una asignación de trabajos de producción podría ser maximizar esta; el objetivo de una asignación de tripulaciones de vuelos podría ser minimizar los costos, etc. El problema de asignación no es sólo un tipo especial de problema de Programación Lineal sino también un tipo especial de problema de transporte.

Específicamente, 48

pueden interpretarse los recursos o lo que se asigna como los orígenes con una oferta igual a 1 y las unidades a donde se asigna pueden interpretarse como destinos de un problema de transporte, cada uno de estos con una demanda 1. De manera similar a un problema de transporte, el problema de asignación tiene una estructura única, y debido a esto se han desarrollado métodos simplificados de solución (de hecho, el método húngaro para la solución del problema de transporte surgió como un método para la solución del problema de asignación) que tienen un alto grado de eficiencia computacional.

Este problema puede ser resuelto por los métodos de

solución normales de la PL, sin embargo, mediante los métodos específicos la solución se alcanza mucho más rápidamente. Problemas con periodos múltiples A continuación se analizan algunos ejemplos de este tipo que no abarcan todas las posibilidades sino que dan una idea acerca de la índole de las situaciones en que puede surgir la necesidad de considerar más de un periodo para resolver un problema dado. Caso 1. Modelo de produccióninventario Un Complejo Agroindustrial Azucarero fabrica un producto derivado de la caña de azúcar que se exporta y tiene una demanda variable. Por ejemplo, la demanda que se ha pronosticado para los próximos cuatro meses es 1800, 2200, 3400 y 2800 kilogramos, respectivamente. Debido a las variaciones en la demanda, la dirección del complejo han encontrado que en algunos meses existe producción en exceso, lo cual ocasiona grandes costos de manejo y almacenamiento;

en tanto que en otros meses la empresa

no está en

posibilidades de cubrir la demanda. La empresa puede fabricar 2400 kilogramos por mes en sus turnos normales. Utilizando tiempo extra puede elaborar 800 kilogramos adicionales por mes. Debido a los mayores costos de mano de obra en tiempo extra, se produce un aumento de $ 7.00 por cada kilogramo que no se fabrique en el turno

normal. La Gerencia 49

Económica del complejo ha estimado que se incurre en un costo de almacenamiento de $ 3.00 por cada kilogramo que se fabrique en un mes determinado y que no se venda durante el mismo. A la dirección de la empresa

le interesa determinar

programa óptimo de producción que minimice los costos totales

un

de producción y

almacenamiento. El programa debe satisfacer todas las demandas de ventas. Construcción del modelo. Este problema busca determinar la cantidad de kilogramos del producto que deben fabricarse durante el turno normal y durante el turno extra para los siguientes cuatro meses, con el objetivo de minimizar los costos totales. La

dirección del complejo

agroindustrial debe tomar en consideración el costo unitario de producción durante los dos turnos, la demanda existente del producto en kilogramos durante un mes determinado, así como también la demanda en los meses subsiguientes y finalmente, el costo de almacenamiento de los kilogramos de producto que no se consumen durante el mes en que se fabrican. Definición de las variables En el problema será necesario considerar varios tipos de variables de decisión. En primer lugar, variables que representan los kilogramos de producto a fabricar en tiempo extra, en segundo lugar las que representan los kilogramos a fabricar en tiempo normal y finalmente, las variables de decisión que representan los inventarios en los meses 1, 2 y 3. En el cuarto mes no se considerará inventario porque el problema, tal como se ha formulado, termina después de cuatro meses. Este periodo bien puede ser el periodo de duración de la zafra azucarera. Por tanto se tendrá xj: número de kilogramos a fabricar en tiempo normal en el mes j. yj: número de kilogramos a fabricar en tiempo extra en el mes j. wj: número de kilogramos a almacenar al final del mes j. Aquí j = 1, 2, 3, 4 (z4 no existe porque no se permiten inventarios en el cuarto mes) Construcción del sistema de restricciones Las restricciones en el problema serán las siguientes: 50

1. Restricción de la demanda en el mes 1: (x1 kilogramos fabricados en el tiempo normal en el mes 1) + (y1 unidades fabricadas en el tiempo extra en el mes 1) = (1800 kilogramos que se demandan en el mes 1) + (w1 kilogramos que se almacenarán al final del mes 1) La restricción quedaría así x1 + y1 w1 = 1800 De la misma forma se razonaría para los siguientes periodos (en este caso meses). 2.Restricción en la demanda en el mes 2 x2 + y2 + w1 w2 = 2200 3.Restricción en la demanda en el mes 3 x3 + y3 + w2 w3 = 3400 4. Restricción en la demanda en el mes 4 x4 + y4 + w3 = 2800 5. 8. Restricciones de la capacidad de producción normal xj 2 400

j = 1,2,3,4

9.12. Restricciones de la capacidad de producción en tiempo extra yj 800

j = 1, 2, 3, 4

13. No negatividad xj 0, yj 0; j = 1,2,3,4; wj 0; j = 1,2,3 Construcción de la función objetivo Al elaborar la función objetivo no es necesario considerar los costos de fabricación en tiempo normal ya que se trata del mismo producto en todos los meses. Los costos a considerar en este problema serían los costos de elaboración en tiempo extra y los costos de almacenamiento. La función objetivo quedará así minimizar Z = 7 y1 + 7 y2 + 7 y3 + 7 y4 + 3 w1 + 3 w2 + 3 w3 Consideraciones adicionales en el problema

51

En una situación real pueden surgir cuestiones relacionadas con la existencia de limitaciones en el almacenamiento. Para considerar la existencia de limitaciones en el máximo de almacenamiento en este problema, serían necesarias restricciones adicionales. Otra cuestión que pudo ser considerada es que definir las variables de inventario solamente con un subíndice, no permite identificar el periodo en que se utilizarán los inventarios.

Se hubieran podido dividir aún más estas variables (al

definirlas) de manera que la solución obtenida reflejara no solo el inventario en un periodo dado, sino también que mostrara el periodo futuro en que se espera que se consuma el producto. Por último, es necesario tener en cuenta que la solución del problema considera solo los costos de almacenamiento y de producir en tiempo extra. Por ello, al final será necesario añadir los costos de producir en tiempo normal para obtener los costos reales. Caso 2. Distribución de inversiones en el tiempo. El Banintur se encuentra elaborando un programa tentativo de desarrollo para los próximos seis años. De acuerdo a los análisis realizados en ese periodo dispondrá de 100 millones para colocarlos en un conjunto de alternativas de inversión sobre las cuales ha realizado cuidadosos estudios y ha determinado los posibles rendimientos de cada una. La inversión tipo I está disponible en cada uno de los próximos seis años y se espera que produzca un rendimiento de 28 % por cada dólar invertido, al momento de su vencimiento al final de tres años. La inversión tipo II también está disponible en cada uno de los próximos seis años. Se prevé que esta inversión rinda 1.16 por cada dólar invertido y vence al final de dos años. La inversión tipo III está disponible sólo al principio del segundo año y rinde 1.50 al final del cuarto año por cada dólar invertido. La inversión tipo IV está disponible en cualquier momento después del tercer año y produce un rendimiento del 40 % al final de dos años. La otra oportunidad de inversión, la de tipo V, está disponible

solo una vez, al principio del año 1 y se espera un

52

rendimiento de 1.45 por cada dólar invertido, pero no vence sino a principios del año 5. Cuando las inversiones vencen están disponibles para reinversión. A la presidencia del Banintur

le gustaría determinar la cartera de inversiones que

maximice el rendimiento de la inversión total para un periodo de seis años, es decir, al final del sexto año. Construcción del modelo. La diferencia fundamental entre este problema y el problema del ejemplo 6 sobre planeación financiera es que en este caso el objetivo es que el paquete completo de inversiones se termine al final de seis años. Para plantear el problema es necesario elaborar un gráfico como el que aparece debajo, que muestra las inversiones disponibles en cada uno de los diferentes años, el año en que vencen las inversiones y el rendimiento asociado con la inversión. El sexto tipo de inversión que se ha añadido al número de inversiones disponibles cumple la función de recoger la parte de los fondos totales que no será utilizada, o sea fondos que no se invirtieron durante el año. La necesidad de esta categoría esta dada porque puede ser más ventajoso

en uno o más periodos reservar dinero para su

inversión en periodos posteriores en vez de comprometer en este momento los fondos en inversiones a largo plazo. Otra cuestión que se observa en el cuadro es que en los años 4 y 5 no se considera la inversión tipo II, aún cuando es una alternativa disponible. Esto se explica porque este tipo de inversión tiene la misma cantidad de años que la inversión tipo IV y que la tipo II produce el 16 %

para un periodo de dos años,

mientras que la tipo IV produce un 40 %. Esto implica que

se preferirá en forma

automática la inversión tipo IV. El mismo razonamiento se utiliza

para eliminar la

inversión tipo I en el periodo 2, en el cual la inversión tipo III es preferible, pues tiene un rendimiento del 50 %. No se considera ninguna oportunidad de inversión más allá de comienzos del año 5, ya que ninguna de las inversiones vence en un año.

53

Patrón de inversiones del Banintur: Inversión Disponible

Año 1 Año 2

Año 1 Tipo 1 Tipo 2 Tipo 5 Tipo 6

Tipo 1 Tipo 2 Tipo 6

Año 4

Tipo 1 Tipo 2 Tipo 4 Tipo 6

Año 5

Tipo 4 Tipo 2 Tipo 6

Año 6

Tipo 6

Año 3

Año 4

Año 5

Año 6

28 % 45 %

16 %

0%

Tipo 1 Tipo 2 Tipo 3 Tipo 6

Año 3

Año 2

28 % 16 %

50 %

0% 28 % 16 %

0% 28 % 16 %

40 % 0% 40 % 16 % 0% 0%

Definición de las variables Si todos los tipos (categorías) de inversión estuvieran disponibles en cada uno de los seis años considerados, entonces se requerirían 36 variables. Sin embargo, de acuerdo a la estructura del problema solo se necesitan 16 variables, ya que muchas de las inversiones no están disponibles

en más de un año.

Las variables tendrán

dos

subíndices donde i denota el tipo de inversión y j denota el año en el que se invierte. Así xij: dinero invertido en el tipo de inversión i en el año j. Construcción de las restricciones del modelo 1. Restricción sobre las inversiones posibles en el año 1 x11 + x21 + x31 + x61 = 60 000 000 2. Restricción sobre las inversiones posibles en el año 2 54

x22 + x32 + x62 = 1.0 x61 3. Restricción sobre las inversiones posibles en el año 3 x13 + x23 + x63 = x62 + 1.16 x21 4. Restricción sobre las inversiones posibles en el año 4 x14 + x44 + x64 = 1.0x63 + 1.28x11 + 1.16x22 5. Restricción sobre las inversiones posibles en el año 5 x45 + x65 = 1.0 x64 + 1.45x51 + 1.5x32 + 1.16x23 6. Restricción sobre las inversiones posibles en el año 6 x66 = 1.0x65 + 1.28x13 + 1.40x44 En todas las restricciones se ha tenido en cuenta que en el término de la izquierda se encuentran las alternativas de inversión que están disponibles al principio de cada periodo y las variables que están en

el miembro de la derecha son los fondos

disponibles para la inversión, todas medidas en dólares. Construcción de la función objetivo El objetivo general del problema es maximizar el total de dinero que se tendrá al final del sexto año. Cada dólar que se coloca en la inversión tipo I en el año 4 rinde 28 % al final del año 6; la inversión neta es la inversión original más 0.28, es decir, 1.28. Cada dólar que se coloca en la inversión tipo IV en el año 5 produce 40 % al final del año 6; por ello, la inversión neta resultante es 1.4. El tipo VI de inversión produce 0 % al final de cada año por cada dólar invertido; por ello, el resultado neto es 1.00. Puesto que estas tres inversiones son las únicas que vencen en el año 6, la función objetivo incluye solo estas variables. La función objetivo quedaría de la siguiente manera: Maximizar Z = 1.28 x14 + 1.40 x45 + 1.0 x66 El modelo en su conjunto quedaría en la siguiente forma: Maximizar Z = 1.28 x14 + 1.40 x45 + 1.0 x66 sujeto a: x11 + x21 + x31 + x61 = 60 000 000 55

x22 + x32 + x62 1.0 x61 = 0 x13 + x23 + x63 x62  1.16 x21 = 0 x14 + x44 + x64 1.0x63  1.28x11 1.16x22 = 0 x45 + x65 1.0 x64 1.45x51  1.5x32  1.16x23 = 0 x66 1.0x65 1.28x13 1.40x44 = 0 xij 0  i, j Ejercicios con formulaciones de problemas destinados a su construcción por el estudiante. 1. La empresa Latinmotor vende automóviles de bajo cilindraje y de tamaño mediano. En la venta de cada automóvil pequeño obtiene 300 y 400 USD por cada automóvil mediano. Debido a limitaciones con la transportación, la empresa no puede suministrar más de 300 automóviles pequeños ni más de 200 de los medianos al mes. El tiempo de preparación de los automóviles pequeños es de 2 horas para cada uno y de 1 hora para los medianos. El taller cuenta con 900 horas de tiempo disponible mensuales para la preparación de los automóviles nuevos que venda. Plantee un modelo de PL para determinar cuantos automóviles de cada tipo deben ordenarse de manera que se maximicen las utilidades de la empresa. Observe que se trata de automóviles pequeños y medianos que serían nuestras variables 2 Una empresa fabricante de cosméticos elabora tres productos de reciente lanzamiento al mercado. Estos productos se denominan Levisol, Lindosol y Solar. En la elaboración de estos productos se emplean tres ingredientes los cuales, por razones de secreto comercial, se han designado por los nombres de Alfa, Beta y Gamma. Para fabricar un kilogramo de producto se utilizan los kilogramos de cada ingrediente que se señalan en el siguiente cuadro

56

:

Producto Levisol Lindosol Solar

Alfa 4 3 2

Ingrediente Beta Gamma 7 8 9 7 2 12

La industria cuenta con 400, 800 y 1000 kilogramos de los ingredientes Alfa, Beta y Gamma respectivamente. De acuerdo a estudios de mercado realizados, las contribuciones a las utilidades para los productos son : 15 USD para el Levisol, 10 para el Lindosol y 12 para el Solar. Se le pide plantear un modelo de PL con el objetivo de determinar la cantidad de cada uno de los productos que debenfabricarse Revisr los problemas de dieta este problema es una generalización. 3. La empresa electrónica

Pinar S.A. es una sociedad mixta que se dedica a la

fabricación de productos para el mercado de las computadoras. Esta empresa fabrica 3 artículos: disquetes, casetes de cinta y cartuchos para limpiar unidades de disco. La contribución unitaria a las utilidades de cada uno de estos productos se muestra en el siguiente cuadro: Producto

Disquete Cassette Paquete limpieza

Contribución a las utilidades(US D) 2,00 1,00 de 3.50

Cada uno de esos productos pasa a través de tres centros de manufactura y prueba como parte del proceso de producción. Los tiempos que se requieren en cada uno de los centros para fabricar una unidad de cada uno de los tres productos se muestran en el cuadro siguiente:

57

Producto Disquete Cassette Paquete Limpieza

Horas por unidad Centro 1 Centro 2 Centro 3 3 2 1 4 1 3 de 2 2 2

Y finalmente, en el cuadro siguiente se muestran el tiempo disponible para la próxima semana y los costos fijos para cada uno de los centros: Tiempo

Centro 1 Centro 2 Centro 3

60 horas 40 horas 80 horas

Gastos fijos (USD) 1000 2000 1500

Plantee el correspondiente modelo de PL que permita programar la producción de manera que se maximice la contribución total a las utilidades. Las variables son los productos que producen la empresa, recordar la condición de homogeneidad de las restricciones. 4. En la refinería de petróleo Malpaso, la subdirección de producción desarrolla la tarea de programar dos procesos de mezclado. Las características de los dos procesos son las siguientes: Cuando se efectúa el proceso 1 durante una hora se consumen 100 barriles de petróleo nacional y 300 barriles de petróleo importado. Cuando se efectúa el proceso 2 durante una hora, se consumen 100 barriles de petróleo nacional y 200 barriles de petróleo importado. Los resultados de estas operaciones son los siguientes: en el proceso 1 se obtienen 4000 galones de gasolina

y 1750 galones de combustible doméstico

(kerosene) por cada hora de operación; en el proceso 2 se obtienen 3500 galones de gasolina y 2 250 galones de combustible doméstico por hora. Para la siguiente corrida de producción, existen disponibles 1200 barriles de petróleo nacional y 1800 barriles de petróleo importado. Los contratos de venta exigen que se 58

fabriquen 28 000 galones de gasolina y 12 000 galones de combustible doméstico. Las contribuciones a las utilidades por hora de operación son $ 1000 y $ 1100 para los proceso 1 y 2, respectivamente. a) Plantee un modelo de PL para determinar el programa de producción que maximice la contribución total a la ganancia. Asegúrese de indicar las unidades de medición para sus variables de decisión y las unidades en que se mide cada restricción. b) El Ministerio correspondiente puede emitir un dictamen que limite la producción total de gasolina a no más de la mitad del combustible doméstico que se fabrique. ¿Cual restricción añadiría Ud. para tomar en cuenta esta condición? Fijarse que las variables tienen dos subíndices, proceso y producto final 5 La dirección de una empresa fabricante de televisores situada en la localidad de Raspadura, está considerando la posibilidad de comenzar a fabricar una nueva línea de equipos. Esta nueva línea incluirá 4 nuevos modelos. Esta empresa cuenta con dos fábricas en las que pueden elaborarse estos equipos. La línea de producción en la fábrica No. 1 tiene una estructura diferente a la de la fábrica No. 2. En la fábrica 1 se requieren tres procesos de manufactura mientras que en la fábrica 2 solo se requieren dos procesos. Debido a que las operaciones de manufactura difieren, sus costos variables también

son diferentes.

de las dos plantas

Por tanto, tal vez sea más

conveniente elaborar un artículo de la nueva línea en una de las plantas y uno o más de los restantes en la otra. El precio de venta y los costos variables, así como también la demanda máxima para los nuevos productos se muestran en la tabla siguiente:

Precio de venta y demanda Precio de venta(USD) Costos variable : planta 1 Costos variables: planta 2 Demanda ( unidades)

No. 1

Productos No. 2 No. 3

No. 4

200 160

300 270

250 240

280 270

220

300

200

220

1000

3000

4000

6000

59

En la tabla siguiente se describen las operaciones de elaboración para las dos plantas (los números de la tabla expresan horas de tiempo de fabricación).

Número 1 Planta 1 Operación A Operación B Operación C Planta 2 Operación X Operación Y

Producto Número Número 2 3

Número 4

6.0 18.0 2.0

7.2 20.0 2.0

4.0 16.0 1.0

7.0 18.0 1.0

8.0 10.0

8.0 16.0

4.0 8.0

8.0 6.0

El gerente de la planta 1 ha señalado que pueden dedicarse las siguientes horas de capacidad mensual de producción para la nueva línea de productos: operación A, 30 000 horas; operación B, 100 000 horas; operación C, 16 000 horas. En cada una de las dos operaciones de la planta 2 existen disponibles 20 000 horas

de tiempo de

producción. A la dirección de la empresa le gustaría determinar la cantidad de cada uno de los 4 tipos de productos que deben fabricarse cada mes en las dos plantas, de manera que se maximice la contribución de las utilidades de la empresa. a) Plantee el correspondiente modelo de PL b) Suponga que la gerencia de la compañía a la cual pertenece esta empresa ha decidido que cada planta fabrique el 50 % de la demanda para cada producto. Plantee dos modelos que pudieran representar esta política.

¿Que podría Ud. hacer para

convencer a la gerencia de que esa no es una política óptima para la compañía? Fijarse que existen cuatro modelos de televisores que pueden fabricarse en dos plantas, por tanto los subíndices de las variables deben reflejar esta situación. Tener en cuenta que el aspecto b) implica una restricción de proporcionalidad, 6. La Cooperativa de Producción Agropecuaria (CPA) “ElMaizal” cuenta con 300 hectáreas de tierra en las que produce fundamentalmente tres productos: frijol, plátano y maíz. Los productos de la cooperativa son para consumo de sus miembros y para venderlos. Esta CPA está organizada de tal manera que deben satisfacerse primero las 60

demandas de sus miembros antes de vender en el exterior cualquiera de los artículos que producen. Todos los excedentes de producción se venden al precio de mercado.

La tabla

siguiente resume para cada producto, durante la temporada de cultivo, el rendimiento proyectado por hectárea, el número de quintales previsto para el autoconsumo de los miembros, la demanda máxima del mercado y la utilidad estimada por quintal. Cultivo Frijol Plátano Maíz

Rendimientos Demanda de los Demanda del Utilidad ( USD / (qq. por há) miembros (qq) mercado( qq) qq) 420 2000 10 000 1.50 200 5000 8000 1.80 70 1000 3000 2.5

Plantee un modelo de PL para el problema que permita a la cooperativa determinar el número de hectáreas que deben sembrarse de cada producto para que se maximicen las utilidades. Darse cuenta que existen tres productos, luego habrá tres variables, definir las variables teniendo en cuenta los aspectos esenciales que implican la definición de las variables. 7. El gerente de una empresa de contratación de personal para hoteles debe asignar personal para cinco puestos. Existen cinco personas disponibles para ser asignados a estas tareas. El gerente mencionado tiene a su disposición datos de prueba

que

reflejan una calificación numérica de idoneidad para cada uno de los cinco trabajadores en cada uno de los trabajos. Estos datos aparecen en la tabla siguiente y se obtuvieron a través de un examen de operación y prueba realizado por el Grupo de Sicología del trabajo. Suponiendo que una persona puede ser asignada a un solo puesto de trabajo, plantee un modelo que conduzca a la asignación óptima de los candidatos a los puestos de trabajo.

61

No. del puesto

candidato

al

Número del puesto de trabajo 1 2 3 4 5

1

12

16

24

8

2

2

6

8

20

14

6

3

10

6

16

18

12

4

2

4

2

24

20

5

7

10

6

6

18

8. Un problema de producción. Una empresa fabricante de condimentos tiene una línea de producción dedicada a dos condimentos: Salsa Zunzún y Salsa Picante. Existe una oferta limitada de algunos de los ingredientes de estas salsas. El ingrediente A1 se pueden obtener 8000 onzas y 7000 del ingrediente A2. Cada botella de Salsas Zunzún requiere una onza de A1 y 2 onzas de A2. El departamento de Ventas afirma que si bien pueden venderse todos los frascos de Salsa Zunzún que se produzcan, solo se venderá un máximo de 6000 botellas de Salsa Picante. Si la empresa obtiene una ganancia de $ 0.05 por botella de Salsa Picante y de 0.02 por botella de Salsa Zunzún ¿Que combinación de esos dos productos maximizará las utilidades de su empresa? Existen trabajadores y puestos de trabajos, luego las variables tendrán dos subíndices. 9. La empresa del ejemplo anterior ha decidido realizar cambios en la forma de elaborar sus salsas. De hecho serán dos nuevos productos con los nombres de los antiguos. Los ingredientes serán los mismos, pero cambiarán las proporciones obedeciendo a las siguientes recomendaciones: La salsa Zunzún debe contener un máximo de 75% del ingrediente A1; la salsa Picante debe contener por lo menos el 25% de A1 y por lo menos 50% de A2. Se pueden vender más de 4000 botellas de Zunzún y más de 3000 botellas de Picante. La empresa puede vender toda la salsa que produzca al precio de $ 3.35 por botella de Zunzún y

2.85 USD por botella de Picante. Los

ingredientes A1 y A2 le cuestan a 1.60 la botella y 2.95 por cuarto respectivamente. La empresa desea maximizar el ingreso neto por venta de las salsas. Formule el modelo de PL correspondiente. Solo se debe añadir las restricciones adicionales correspondientes 62

10. Un problema de mezcla. El ingeniero Pedro Pérez, jefe de producción de Unidad Básica de Producción Cooperativa dedicada a la producción de leche está planeando poner fertilizante en algunas áreas de pasto artificial. El pasto necesita nitrógeno, fósforo y potasa al menos en las cantidades dadas en la tabla que sigue: Requerimientos totales del pasto Elemento Peso mínimo kg por ha. Nitrógeno 10 Fósforo 7 Potasio 5 Existe la posibilidad de comprar tres clases de fertilizantes comerciales y en el cuadro que sigue se dan las características de cada uno de ellos.

Características de los fertilizantes Fertilizant Contenido Contenido Contenido Precio e de de fósforo de potasio ($) nitrógeno (libras) (libras) (libras) I

25

10

5

10

II

10

5

10

8

III

5

10

5

7

El ingeniero Pérez puede comprar de los tres tipos en las cantidades que quiera y luego mezclarlos en la forma más conveniente y aplicar la mezcla al pasto. Si el área a fertilizar de pasto son tres hectáreas, formule el correspondiente modelo de PL que le permita realizar la fertilización al mínimo costo. Ver el planteamiento matemático en los ejemplos desarrollados en los ejercicios de la página 37. 11. Punto de equilibrio. La

dirección de la empresa productora de equipos de

refrigeración Electrónica del Oriente S.A. está preparando el programa de producción para el próximo periodo. Esta empresa fabrica dos tipos de equipos de aire 63

acondicionado: el R1500

y el R2500. En

el cuadro siguiente se dan los datos

relativos a precios de venta y costos. La Electrónica del Oriente ya tiene contratados 500 equipos R-1500 y desearía calcular el punto de equilibrio para ambos modelos.

Precios de venta y costos Producto Precio de Venta por Costo variable unidad ($) unidad ($)

por Costo fijo ($)

R-1500

450

240

150 000

R-2500

700

360

240 000

Se le pide a Ud. que formule el modelo de PL que permita minimizar los costos. Ver ejemplo página 34 12.Presupuesto de capital. Una compañía de inversiones debe escoger entre cuatro proyectos que están compitiendo por una bolsa fija de inversiones de $ 1 200 000. La inversión neta y los réditos estimados de cada proyecto se dan en la tabla siguiente: Proyectos de inversión Proyecto Centros comerciales

Réditos estimados

USD

USD

400 000

Aceite esquistos Casas de ingresos

Inversión

575 000

de

500 000

750 000

bajos

350 000

425 000

450 000

510 000

LowincomeHousing

Cada uno de los proyectos se puede consolidar a cualquier nivel fraccionario menor del 100 %. Formule un modelo de PL que diga que fracción de cada proyecto contratar para maximizar los réditos esperados.

64

Los proyectos conforman las variables Ver ejemplo similar en los ejercicios desarrollados en las páginas 30 13. El restaurante El Ajiaco opera 7 días a la semana. Las meseras son contratadas para trabajar 8 horas diarias efectivas.

El contrato colectivo especifica

que cada

mesera debe trabajar 5 días consecutivos y descansar 2. Todas las meseras reciben el mismo salario semanal. El restaurante requiere como mínimo los siguientes números de horas de servicio: lunes, 150; martes, 200; miércoles, 400; jueves, 300; viernes, 700; sábado, 800 y domingo 300. Suponga que ese ciclo de exigencias se repite siempre y pasa por alto el hecho de que el número de meseras contratadas debe ser un número entero. El administrador desea encontrar un plan de programación de empleos que satisfaga estos requerimientos a un costo mínimo. Este ejemplo ha sido desarrollado en los ejercicios de la página 30

65

III. MÉTODOS DE SOLUCIÓN Objetivo: Preparar al estudiante para que pueda resolver los problemas de Programación Lineal, incluyendo la aplicación de los métodos gráfico, algorítmico manual y por computadora, así como realizar el análisis de la solución encontrada en el contexto del problema resuelto. Recomendaciones previas al inicio del estudio de este capítulo: Es necesario haber estudiado el capítulo dedicado a planteamientos de problemas.

Debe tener conocimientos sobre las operaciones con matrices, inversión de matrices, operaciones elementales con las filas y columnas de las matrices y procedimiento de cambio de base. En el capítulo anterior se ha realizado una exposición acerca de diferentes formulaciones de problemas de PL y los correspondientes modelos económicos matemáticos aplicados en diferentes situaciones económicas corrientes en el ámbito empresarial. Para resolver estos problemas y otros que pueden ser más sencillos o mucho más complejos se emplean diferentes procedimientos de solución: Procedimiento gráfico

 Procedimiento algorítmico manual.  Procedimiento por computadoras electrónicas. En este capítulo se dará una visión acerca de estos tres procedimientos de solución, algunos de los cuales implican la posibilidad de emplear diferentes métodos. En la actualidad los problemas de PL se resuelven fundamentalmente por medio de programas de computadoras, varios de los cuales tienen la posibilidad de resolver modelos con una gran cantidad de variables y restricciones. Sin embargo, el estudio de algunos de los métodos comprendidos en los procedimientos gráfico y algorítmico 66

manual, es imprescindible para poder comprender los aspectos básicos de la PL, su fundamentación matemática e incluso para poder realizar la interpretación económica de los resultados que brindan los programas de computadoras. Antes de comenzar el estudio de los procedimientos de solución del problema de PL es conveniente explicar varios conceptos y definiciones que serán útiles para comprenderlos.

Tal como se observó en los planteamientos de problemas expuestos en el capítulo anterior, un problema de PL consta de tres partes importantes: 1. Un conjunto de variables de decisión 2. Un conjunto de restricciones 3. Una función objetivo o función criterio. En forma algebraica desarrollada este problema se puede describir como: Encontrar el conjunto de valores de las variables x1, x2, x3,... ,xn, que maximiza o minimiza la función Z  c1 x1  c 2 x 2  c 3 x 3  . . .  c n x n (1)

sujeto a:

a 11x 1  a 12 x 2  a 21x 1  a 22 x 2 

a 13 x 3  . . .  a 1n x n , ,  b1   a 23 x 3  . . .  a x n , ,  b 2  2n



. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..  a m1 x 1  a m2 x 2  a 13 x 3  . . .  a mn x n , ,  b m  

x1, x2, x3, . . . , xn 0

(2)

(3)

Obsérvese que (1) es la función objetivo y puede ser de maximizar o minimizar. Cada una de las restricciones que compone el conjunto (2) puede ser de mayor o igual, de igual a o de menor o igual, pudiendo tener solo uno de tales signos. Los coeficientes de las variables en la función objetivo se denominan como coeficientes económicos. Los coeficientes de las variables en las restricciones se denominan como coeficientes tecnológicos y son las normas de insumo (consumo productivo) unitarias de cada uno de los recursos, en otras palabras, cuanto se consume de un recurso 67

dado, para la elaboración de una unidad de producto. Los términos de la derecha se conocen como términos independientes y constituyen en general, la disponibilidad de recursos o las limitaciones existentes en capacidad de producción, de demanda, de almacenamiento, etc. tal como se vio en los problemas cuya formulación se estudió en el capitulo anterior. Las variables que componen el problema se denominan como variables de decisióno variables esenciales y de acuerdo con

(3) están sujetas a ser no negativas. La

expresión (3) se denomina habitualmente como condición de no negatividad. El problema general de la PL puede ser escrito también de manera más sintética de la siguiente forma: n

Maxó min Z =  c j x j j1 sujeto a:

n  a ij x j (, , )bi ; j1 xj 0;

i 1 : m

j  1: n

También se puede expresar en forma matricial como sigue: Maxó min Z = CX/ AX (,=,) b; X  0 Ahora es necesario tener en cuenta un conjunto de definiciones importantes. Solución: Se denomina solución a cualquier conjunto de valores de las variables de decisión X que satisfaga el conjunto de restricciones (2). Solución

posible:

Es

cualquier

solución

que

satisfaga

simultáneamente los conjuntos de restricciones (2) y (3). Solución posible

óptima: Es una

solución

posible que maximiza o

minimiza a (1), o sea que al ser sustituida en (1) proporciona el valor máximo o mínimo de Z.

68

Solución básica no degenerada: Es una solución que tiene exactamente m componentes positivos.

Solución degenerada: Es una solución básica que tiene menos de m componentes positivos. En un problema de PL, el conjunto de soluciones posibles conforma un conjunto convexo. Se denomina como punto extremo o vértices del conjunto convexo a los puntos en que se interceptan los lados del conjunto. La solución óptima de un problema de PL se encuentra siempre en al menos uno, de los puntos extremos del conjunto convexo formado por las soluciones posibles del problema.

Procedimiento gráfico de solución Resolver por métodos gráficos un problema de PL es relativamente fácil. El inconveniente que tiene este método es que solo es aplicable en problemas de dos variables esenciales. Sólo si se es un buen dibujante, podría aplicarse a la solución de un problema de tres variables, pues ya con este número de variables el método es extremadamente complejo y por supuesto, no es posible aplicarlo en el caso de más de tres variables esenciales. La importancia de este método es más bien metodológica, ya que permite comprender el mecanismo de solución que desarrollan los algoritmos que se emplean en el proceso de solución de problemas mayores, dando una idea además, de las posibles situaciones de tipo especial que pueden ocurrir y que se verán más adelante, tales como la existencia de soluciones alternas, soluciones no acotadas, etc. Veamos el método a través de un ejemplo.

69

Ejemplo 1 Sea el siguiente problema de PL: Max Z = 4x1 + 5x2 sujeto a:

3) x1 + x2  6

1) 8x1 + 3x2 24 2) 2x1 + 6x2 12

4) x1  0, x2  0 Obsérvese que todas las soluciones posibles de este problema deberán estar en el primer cuadrante debido a que las dos variables están sujetas a ser no negativas. El primer paso para resolver un problema de PL mediante este método es considerar las inecuaciones como ecuaciones. Esto se debe a que cada una de las inecuaciones que componen el conjunto de restricciones de este problema tiene un conjunto de soluciones posibles situado entre los ejes de coordenadas x1 y x2 y la recta que resulta al considerar la inecuación como ecuación. 1)

8x1 + 3x2 = 24

2)

2x1 + 6x2 = 12

3)

x1 +

x2 = 6

El segundo paso será hallar el gráfico de estas rectas y determinar la región de soluciones posibles para todas las inecuaciones que componen el sistema de restricciones del problema. Es decir, se establece un sistema de coordenadas donde las abscisas están dadas en el eje x1 y las ordenadas en el eje x2. Para hallar el gráfico de estas rectas simplemente es necesario hallar sus intersecciones con los ejes coordenados. Por ejemplo, en la ecuación 1) si se supone a x1= 0, entonces x2 = 8; si se supone a x2 = 0, entonces x1 = 3. Luego la recta corta a los ejes coordenados en los puntos (0,8) y (3,0). A partir de estos dos puntos se traza el segmento de recta que los une y se obtiene la recta 1) del gráfico. De la misma forma se procede con las rectas 2) y 3). Para buscar la región de soluciones simultáneas para todas las restricciones, será necesario buscar cual es la región de solución de cada una de ellas. En el caso de la 70

primera restricción se toma un punto situado a uno de los lados de la recta 1) y se sustituye en la inecuación 1). Si el resultado satisface la inecuación entonces la región de solución estará constituida por todos los puntos que se encuentren al mismo lado que el punto seleccionado. Si el resultado de la sustitución no satisface la inecuación entonces, la región de solución será el conjunto de todos los puntos que se encuentran en el lado contrario de la recta. Por comodidad generalmente se escoge el punto (0,0). Sustituyendo (0,0) en 1): 8x1 + 3x2 24

1)

8(0) + 3(0)  24 0  24 lo cual no es cierto, o sea que el punto (0,0) no satisface la inecuación. Eso indica que la región de solución está en el lado contrario de la recta. Esto se indica mediante una flecha como aparece en el gráfico 1. Un procedimiento similar se realiza con las demás inecuaciones. Por ejemplo, con la inecuación 3), si se sustituye en ella el punto (0,0), se llega a x1 + x2 6

3)

(0)+ (0)  6, lo cual es cierto. En este caso la región de solución está al mismo lado que el punto (0,0), como lo indica la flecha en el gráfico 1. Recordando que todos los puntos de la región de solución deberán estar en el primer cuadrante por la condición de no

X2

(1)

B (3) (2)

R A

C X1 71

72

negatividad, entonces la región de solución R del sistema de restricciones de este problema estará constituido por los puntos dentro del triángulo ABC. Gráfico 1

X2

(1)

B Z2 = 40

(3) (2) A

C

X1

Z1 = 20

Para buscar la solución del problema será necesario graficar la función objetivo. Para ello, se le adjudica aZ un valor arbitrario conveniente. Generalmente se busca un valor que sea mínimo común múltiplo de los coeficientes de las variables. Podemos trazar entonces dos rectas: una para Z1 = 20 y Z2 = 40. O sea graficando las rectas Z = 4x1 + 5x2 Z1= 4x1 + 5x2 = 20 y

Z2 = 4x1 + 5x2 = 40

Buscando las intersecciones con los ejes de estas dos rectas, se llega al gráfico 2. Recordando que se trata de un problema de maximizar, se observa que el valor de Z aumenta a medida que la recta se desplaza en la dirección indicada por las flechas perpendiculares a las rectas Z1 y Z2. Ahora bien, desplazando Z1 paralela a si misma, el último punto de la región de solución que toca es el punto B.

73

Si la recta se continua desplazando, dejará de tener contacto con el conjunto de soluciones posibles. Y es precisamente en ese punto donde se encuentran las coordenadas del valor máximo de Z. Para encontrar las coordenadas de este punto, se resuelve el sistema de ecuaciones formado por las dos rectas que se cortan en él. La solución será por tanto (x1, x2) = ( 1.2, 4.8). Sustituyendo en Z, se llega a max Z = 4x1 + 5x2 max Z = 4(1.2) + 5(4.8) = 28.8 max Z = Z* = 28.8 Ejemplo 2 Resuelva el siguiente problema de PL por el método gráfico Max Z = 3x1 + 2x2 Sujeto a: 4x1 + 5x2 20 6x1 + 3x2 24 -3x1 + x2 0 x1, x2 0 El proceso de solución de este ejemplo es similar al anterior. L única diferencia es con la restricción 3, debido a que la misma pasa por el origen de coordenadas y para trazarla es necesario despejar una de las variables en términos de la otra x2 = 3x1 Evaluando la variable x1 = 1, se tendrá x2 = 3. Se obtiene así el punto (1, 3) y se puede trazar la recta que pasa por este punto y por el origen. Una vez que se han trazado las rectas, para conocer cuál es el conjunto de soluciones posibles de la tercera restricción, no es posible utilizar, como en las demás, el punto (0, 0). En este caso, se toman las coordenadas de un punto cualquiera y se sustituyen en dicha restricción. Si la desigualdad o igualdad se satisface, entonces la región de solución de inecuación estará formada por todos los puntos que se encuentran en el mismo lado en que se encuentra el punto tomado como referencia. Si no se satisface, entonces la región de solución será la del lado contrario. 74

Por ejemplo, si se sustituye el punto (2, 1) en la tercera restricción, se tendrá -3(2) + (1)  0 -5 < 0 entonces, la región de solución de esta inecuación estará formada por todos los puntos

X* = (1.6, 4,8)

R

Z1 = 6

X1 Z1 = 24

Gráfico 2 que se encuentran en la región de la derecha. La situación se representa por el gráfico (3). El resto de los pasos para la determinación del óptimo es similar a la del ejemplo 1. Procedimientos algorítmicos de solución Debido a que el procedimiento de solución gráfico solo es fácilmente aplicable en caso de que el problema contenga

hasta dos variables esenciales, se necesita un

procedimiento eficaz mediante el cual se pueda dar solución a problemas de mayores dimensiones. Aunque en 1938, Kantorovich resolvió un modelo utilizando una variante del método de los multiplicadores de Lagrange, en realidad el primer algoritmo que resolvió con éxito el problema de PL fue el denominado Método Simplex elaborado por Dantzig (1947/48) y a partir del cual se han elaborado diferentes algoritmos con más o menos complejidad

75

tales como: método Simplex Revisado, Simplex modificado, Simplex-Dual, método de entrada y salida de la base de dos vectores simultáneamente, etc. Estos métodos de solución están fuera del objetivo de este libro, no dedicado a especialistas en Investigación de Operaciones, sino a estudiantes de las carreras económicas y empresarios interesados en los métodos cuantitativos. Dado que en la actualidad los modelos de PL se resuelven fácilmente mediante paquetes de programas para computadoras electrónicas, tanto el procedimiento gráfico, como el procedimiento algorítmico manual, se explican para poder realizar el análisis del problema y de su solución, de manera que se puedan hacer las correcciones necesarias, tanto en el primero como en la segunda. Teniendo en cuenta los fines declarados arriba, en este capitulo se estudiará solamente el llamado método Simplex estándar o clásico. El método Simplex es un procedimiento iterativo que en un número finito de pasos, permite llegar a la solución óptima del problema de PL. Comienza el proceso a partir de una solución básica, o sea a partir de una solución de punto extremo y va moviéndose de solución básica en solución básica, aumentando (disminuyendo) el valor de la función objetivo en cada paso, hasta llegar a la solución que proporciona el máximo (mínimo) valor de Z. Desde el punto de vista del procedimiento de cálculo, este método se basa en la construcción y modificación, paso a paso, de los componentes de una tabla que tiene la siguiente forma:

76

Cj

C1

C2

...

Ck

...

Cn

CB i

XBi

XB*

P1

P2

...

Pk

...

Pn

CB1 CB2 . . . CBm

XB2 XB2 . . . XBm

XB1* XB2* . . . XBm*

p11 p21 . . . pm1

p12 p22 . . . pm2

... ...

... ...

...

P1 k p2k . . . pmk

...

p1n p2n . . . pmn

Z0

Z1

Z2

...

Zk

...

Zn

ZjCj

ZjCj

Zj ZjCj

ZjCj

ZjCj

La composición de los elementos de la tabla es la siguiente: En la primera fila se encuentran los coeficientes económicos (cj) de las variables, tal como aparecen en la función objetivo. La primera columna está encabezada por CBi, es decir, los elementos que la componen son los coeficientes económicos de las variables básicas. Recuérdese que se tiene una variable básica por cada restricción del problema. En la segunda columna se escriben las variables que son básicas en el problema concreto que se va a resolver, y en la tercera columna se escriben los valores de esas variables básicas. Las columnas encabezadas por P1, P2, . . . ,Pn están compuestas por los coeficientes de las variables que componen la matriz A del conjunto de restricciones del problema. La tercera columna en ocasiones se denomina como P0. La penúltima fila de la tabla esta formada por los Zj. Estos valores se obtienen multiplicando los elementos de la columna de los CBi por los elementos de la columna Pj y sumando los resultados de estos productos. Una vez calculados los elementos de la fila de los Zj, se les resta a cada uno de ellos el elemento Cj correspondiente que se encuentra en la primera fila de la tabla y se obtendrán los elementos de la última fila.

77

Antes de aplicar el método simplex se necesita que el conjunto de inecuaciones que componen las restricciones se escriban como ecuaciones. Para explicar los diferentes aspectos del algoritmo Simplex estándar, tomaremos como ejemplo el problema planteado en el ejemplo 1. Ejemplo 2

Convertir en igualdades las inecuaciones presentes en el siguiente

problema: max Z = 4x1 + 5x2 sujeto a: 8x1 + 3x2 24 2x1 + 6x2 12

x1 + x2 6 x1 0, x2 0

Para convertir el conjunto de restricciones en igualdades, nótese que en la primera restricción el miembro izquierdo es mayor o igual que el miembro derecho. Para lograr que sean iguales es posible restar del miembro izquierdo una variable no negativa, denominada como variable de holgura cuyo valor será igual a la posible diferencia entre el miembro izquierdo y el derecho de la restricción. Esa misma operación se podrá realizar con la segunda restricción. En el caso de la tercera restricción, el miembro de la izquierda es menor que el de la derecha, en ese caso será necesario sumar una variable de holgura cuyo valor será la diferencia entre los dos miembros originales de la restricción. De ese modo el conjunto de restricciones quedaría como sigue:

x1 + x2+ x5 6

8x1 + 3x2 x324 2x1 + 6x2x412

x1 0, x2 0, x3 0, x4 0, x5 0 Las variables de holgura deberán formar parte de la función objetivo y pueden aparecer con un valor positivo en la solución óptima. Por ello para que su valor no afecte el valor de Z óptimo, se le impondrá un coeficiente cero. De este modo la función objetivo quedaría como: 78

max Z = 4x1 + 5x2 + 0x3 + 0x4 + 0x5 Ejemplo 3: Convertir en igualdades las restricciones del siguiente problema Min Z = 6x1 + 12x2 sujeto a: 2x1 + 4x2 12 4x1 + 3x2 24 x1, x2 0 Si se añaden las variables de holgura se tendrá que el problema quedaría como sigue: min Z = 6x1 + 12x2 + 0x3 + 0x4 sujeto a: 2x1 + 4x2 + x3 4x1 + 3x2

= 12

+ x4 = 24

x1, x2, x3, x4 0 Entre los problemas de los ejemplos 2 y 3 existe una diferencia cuando se convierten los sistemas de restricciones en igualdades. En el segundo, cuando se realiza esta operación, las variables de holgura que se añaden, aparecen sumando y

los

coeficientes de estas variables forman una matriz identidad , es decir forman una base. Esto se puede observar en la matriz del sistema A cuyas dos últimas filas y columnas forman una matriz unitaria. 2 4 1 0 A=   4 3 0 1

En este caso, si se supone a las variables esenciales con valor cero, entonces los valores de las variables de holgura están determinados, son los

términos

independientes. El sistema de restricciones quedaría como sigue: 2(0) + 4(0) + x3 4(0) + 3(0)

= 12 + x4 = 24

En este caso se dice que estas variables constituyen una solución básica.

79

En el primer caso, cuando se añaden las variables de holgura, los coeficientes de estas variables no conforman una matriz identidad, pues algunos de ellos son iguales a 1. Por tanto las variables de holgura no conforman una solución básica. Al aplicar el método Simplex para resolver estos dos problemas, se observan algunas diferencias derivadas del hecho de que exista o no una solución básica al añadir las variables de holgura. Por consiguiente, para aplicar el procedimiento Simplex estándar a la solución de un problema de PL, hay que distinguir dos situaciones:  Caso I: el problema contiene una base al añadir las variables de holgura

 Caso II: el problema no contiene una base al añadir las Caso I: El problema contiene una base al añadir las variables de holgura variables de holgura. Este caso se verá a través del siguiente: Ejemplo 4: Resolver el siguiente problema de Programación Lineal mediante el método Simplex max Z = 3x1 + 2x2 sujeto a 3x1 3x2 9 4x1 + 5x2 20 3x1 + 7x2 21 x1 0, x2 0 Se tiene la tarea de resolverlo utilizando el método Simplex. Solución El primer paso para resolver este problema será convertir el conjunto de restricciones de inecuaciones a ecuaciones. Para ello se agregarán variables de holgura a cada una de ellas quedando el problema en la siguiente forma:

80

max Z = 3x1 + 2x2 + 0x3 + 0x4 + 0x5 sujeto a 3x1 3x2 + x3 = 9 4x1 + 5x2 + x4 = 20 3x1 + 7x2 + x5 = 21 x1 0, x2 0, x3 0, x4 0, x5 0 Como se observa en el conjunto de restricciones, al añadir las variables de holgura, estas variables configuran una matriz identidad o unitaria. Por ello, si se considera que las demás variables del problema son iguales a cero, el valor de cada una de las variables de holgura queda determinado y es igual al término independiente de cada restricción. Como existe una de tales variables en cada una de las restricciones, se dice que ellas forman una base o sea, serán las variables básicas del problema y se estará en condiciones de llevar el mismo a la tabla Simplex. Vaciando los coeficientes del problema en la tabla Simplex explicada arriba se tendrá Iteración 0 Cj  CBi XBi 0 x3 0 x4 0 x5 Zj ZjCj

XB* 9 20 21 0

3 P1 3 4 3 0 3

2 P2 3 5 7 0 2

0 P3 1 0 0 0 0

0 P4 0 1 0 0 0

0 P5 0 0 1 0 0

Como se explicó arriba, los valores de Zj se calculan multiplicando la columna de los C Bi por las columnas de los Pj: 0(9) + 0(20) + 0(21) = 0 = Z0 ; 0 (3) + 0(4) + 0(3) = 0 = Z1 y así sucesivamente. Luego se resta cada elemento de la fila Zj de los elementos correspondientes que están en la primera fila de la tabla o sea de la fila de los Cj y de esta manera se obtendrán los ZjCj. Se tendrá así Z1 C1 = 0 3 = 3, Z2 C2 = 0  2 =  2 y así sucesivamente. Nótese como un aspecto importante que todos los ZjCj correspondientes a los vectores que están en la base, son exactamente iguales a cero. Aunque si los ZjCj son iguales a cero, esto no quiere decir que el j-ésimo vector sea básico.

81

Una vez que se ha elaborado esta primera tabla entonces habrá que comprobar si la solución encontrada compuesta por (x3, x4, x5) es la solución óptima del problema, es decir habrá que aplicar un criterio de optimalidad de la solución. Si esta solución no es la óptima, entonces habrá que transformar la tabla, buscando otra. Para ello habrá que tener un criterio que permita seleccionar e introducir en la solución básica una nueva variable. Sin embargo, como la solución no puede tener más de m componentes, será necesario disponer de un criterio que permita seleccionar cual variable deberá salir de la solución. Es decir, habrá que disponer de tres criterios:  Criterio de entrada a la base, que permitirá seleccionar cual de las variables que no están en la base será la mejor para introducirla en lugar de otra.

 Criterio de salida, que permitirá seleccionar dentro de las variables que están en la base, cual será la mejor para ser sustituida.  Criterio de optimalidad que permitirá conocer, después de hacer las correspondientes sustituciones, si se ha llegado o no a la solución óptima. El proceso de obtención de estos criterios requiere de una fundamentación algebraica de regular complejidad. En el caso de este libro no se deducirán, sino que se darán directamente y son los que aparecen en la siguiente tabla resumen:

82

Caso de un problema Caso de un problema de maximizar de minimizar Criterio de entrada en ZkCk = min (ZjCj) para ZkCk = max (ZjCj) para la

base:

Seleccionar

todo aj cuyo ZjCj< 0

todo aj cuyo ZjCj> 0

aquel vector ak tal que: Criterio de salida de la base: Seleccionar aquel vector

al



x *Bi p rj

x *Bi

 min ; p ij  0 i p ij

cual

corresponda , siendo Criterio de optimalidad: ZjCj 0 para todo aj de Cuando se cumple A que

ZjCj 0 para todo aj de A

Si en la tabla correspondiente a la iteración 0 se aplica el criterio de optimalidad, se verá que los valores de los ZjCj no son todos mayores o iguales que cero, que sería la condición para el problema estudiado que es de maximizar. Luego no se ha llegado a la solución óptima. Habrá que cambiar esta solución introduciendo un nuevo vector en la base. Según el criterio de entrada que aparece en la tabla, se introducirá el vector al cual corresponda ZkCk = min (ZjCj) para todo aj cuyo ZjCj< 0 o lo que es igual ZkCk = min ZjCj / ZjCj< 0 = min  3,  2  =  3 = Z1 C1 Esto indica que entrará en la base el vector P 1 o sea que la variable x1 se convertirá en básica. Ahora bien, para introducir este vector en la base, es necesario sacar alguno de los que ya está en ella. Recuérdese que por cada restricción existirá solo una variable básica y en el problema se tienen 3 restricciones. Para seleccionar la variable básica que dejará de serlo se aplica el criterio dado arriba:

83

x* x*   Bi  min Bi ; p rj i p ij

p ij  0

 = min  9/3, 20/4, 21/3 = min 3, 5, 7 = 3 El valor de  = 3 indica que saldrá de la base el vector al cual corresponde el cociente calculado, o sea el P3.

La cuestión ahora es realizar las operaciones necesarias para realizar el proceso de cambio de base, introduciendo P1 y sacando a P3. Esencialmente, el problema consiste en transformar el vector columna P1 en un vector unitario igual al vector columna P3.Para realizar esa transformación, el elemento de la tabla que se encuentra en la intersección de la fila que corresponde a la variable x3 con la columna P1 se transforma en un uno y los demás elementos de esa columna se deberán transformar en cero. Para ello se divide toda la fila entre este elemento y se tendrá toda la fila transformada y se obtendrá el elemento uno. En el problema que se está resolviendo los elementos transformados de esa fila serían  XB1*

P1

P2

P3

P4

P5

3

1

1

1/3

0

0

Para lograr la transformación de los demás elementos de la columna P 1 en ceros se aplicarán las demás operaciones elementales conocidas del Algebra Lineal. Para lograr esto, se multiplica la fila transformada por el inverso aditivo del elemento que deberá transformarse en cero y se suma a la fila que deberá transformarse. Esto sería 4 (3, 1, 1, 1/3, 0, 0) + (20, 4, 5, 0, 1, 0) = (8, 0, 4, 1/3, 1, 0) y el resultado es la fila transformada correspondiente a la variable x4. Para transformar la fila correspondiente a x5 se realiza la misma operación  3(3, 1, 1, 1/3, 0, 0) + (21, 3, 7, 0, 0, 1) = (12, 0, 10, 1, 0, 1) Escribiendo estos dos resultados en la nueva tabla se tendrá:

84

Iteración 1 CBi 3 0 0

Cj XBi x1 x4 x5 Zj ZjCj

XB* 3 8 12

3 P1 1 0 0

2 P2 1 9 10

0 P3 1/3 4/3 1

0 P4 0 1 0

0 P5 0 0 1

A partir de estos resultados se tendrá que aplicar el criterio de optimalidad. Es decir, verificar si todos los ZjCj son mayores o iguales que cero. Calculando los ZjCj en la misma forma que se explicó arriba, se tiene Z0 = 3(3) + 0(8) + 0(12) = 9 Z1 = 3(1) + 0(0) + 0(0) = 3 Z2 = 3(1) + 0(9) + 0(10) = 3 y así sucesivamente. Una vez escritos estos resultados en la fila correspondiente de la tabla, se le restan los valores de la primera fila correspondiente a los Cj, obteniéndose los ZjCj. La tabla completa quedaría así Iteración 1 Cj CBi XBi 3 x1 0 x4 0 x5 Zj ZjCj

XB* 3 8 12 9

3 P1 1 0 0 3 0

2 P2 1 9 10 3 5

0 P3 1/3 4/3 1 1 1

0 P4 0 1 0 0 0

0 P5 0 0 1 0 0

Como se observa, aún no se ha llegado al óptimo ya que no todos los ZjCj 0. Aplicando los criterios de entrada y salida y realizando las operaciones necesarias para el cambio de base, se llega a la tabla correspondiente a la iteración 2.

85

Iteración 2 CBi 3 2 0

Cj XBi X1 X2 x5

XB* 35/9 8/9 28/9

3 P1 1 0 0

2 P2 0 1 0

3 0

2 0

121/9

Zj ZjCj

0 0 P3 P4 5/27 1/9 4/27 1/9 13/27 10/ 9 7/27 5/9 7/27 5/9

0 P5 0 0 1 0 0

En esta iteración el criterio de optimalidad se cumple. La solución óptima encontrada será: X*= (x1*, x2*, x3*, x4*, x5*) = (35/9, 8/9, 0, 0, 28/9) y el valor máximo de la función objetivo es Z* = 121/9 = 13.44 Caso II: El problema no contiene una base al añadir las variables de holgura. Se tomará para ejemplificar el proceso de solución el siguiente problema: Ejemplo 5 Sea el siguiente problema de PL: maximizar Z = 3x1 + 2x2 sujeto a 2x1 + 4x2 = 8 4x1 + 3x2 12 4x1 + x2 4 x1 0, x2 0 Igual que en el ejemplo anterior se añadirán las variables de holgura para transformar las inecuaciones en ecuaciones y el problema quedará en la siguiente forma:

86

maximizar Z = 3x1 + 2x2 + 0x3 + 0x4 sujeto a: 2x1 + 4x2 = 8 4x1 + 3x2 + x3 12 4x1 + x2 x44 x1 0, x2 0, x3 0, x4 0 Al convertir las inecuaciones en ecuaciones no se logra que en el sistema exista el número necesario de vectores unitarios (3) para formar una base. Obsérvese que en la primera ecuación no existe ninguna variable para formar un vector unitario (1, 0, 0). La segunda si contiene una variable (x3) con la cual se forma el vector (0, 1, 0) pero en la tercera la variable de holgura da lugar a la existencia de un vector (0, 0, 1) el cual no es unitario. Para lograr que aparezca la base unitaria necesaria se utiliza un tipo de variable denominada variable artificial. Estas variables no tienen ningún significado económico y por tanto solo cumplen la función de servir de base inicial para comenzar el proceso de solución del problema de PL. No deberán aparecer nunca en la solución óptima. En el problema considerado será necesario añadir una variable artificial en la primera restricción y una en la tercera. En ese caso el problema quedaría en la siguiente forma: maximizar Z = 3x1 + 2x2 + 0x3 + 0x4 Mx5 Mx6 sujeto a 2x1 + 4x2 + x5 = 8 4x1 + 3x2 + x3 12 4x1 + x2 x4 + x6 4 x1 0, x2 0, x3 0, x4 0, x5 0, x6 0 Aquí se observan dos cuestiones. En la función objetivo se han añadido las variables artificiales x5 y x6 asociadas a coeficientes  M. La letra M se utiliza para designar un número cuyo valor absoluto es muy grande. Como el problema es de maximizar, se le impone el signo menos para garantizar que el algoritmo de solución saque de la base a la variable asociada a este coeficiente. Si en este problema la M tuviera signo positivo, al ser este coeficiente un valor muy grande, siempre se mantendría en la base y no será 87

posible determinar la solución en términos de las variables esenciales y de holgura. Llevando el problema así planteado a la tabla Simplex se tendrá Iteración 0 Cj CBi XBi X5 M 0 X3 x6 M Zj ZjCj

*

XBi 8 12 4  12M

3 P1 2 4 4 6M

2 P2 4 3 1  5M

0 P3 0 1 0 0

0 P4 0 0 1 M

M P5 1 0 0 M

M P6 0 0 1 M

6 M3

 5M2

0

M

0

0

Aplicando el criterio de optimalidad se observa que aún no todos los ZjCj son mayores o iguales a cero. Esto indica que la solución básica no es óptima. Aplicando el criterio de entrada se determina que el min ZjCj / ZjCj< 0  = min  6M  6,  5M  5 =  6M  6 el cual corresponde a la columna P1. Luego la variable que deberá convertirse en básica es la variable x1. Aplicando el criterio de salida  = min  8/2, 12/4, 4/4 = min  4, 3, 1 = 1 y se determina que la variable que deberá dejar de ser básica es la variable x 6 a la cual corresponde el cociente más pequeño. Siguiendo el mismo procedimiento aplicado en el ejemplo anterior, el elemento que está en la intersección de la fila donde está x6 y la columna P1 , que es un 4 deberá convertirse en un 1, para comenzar el proceso de transformación de P 1 en P6, o sea para transformar P1 en un vector unitario igual P6. Para ello, se divide toda la fila entre 4 y el resultado se coloca en la quinta fila donde ahora en lugar de x6, estará x1. Posteriormente será necesario transformar los demás elementos de la columna P 1 en ceros. Comenzando por la fila que corresponde a x3, el elemento que deberá transformarse en cero es pij= p13 = 4. Entonces multiplicando la fila 5 por  4 y sumándola a la cuarta fila se tendrá:  4 (1,1,1/4, 0,1/4,0, 1/4) + (12, 4, 3, 1, 0, 0, 0) = (8, 0, 2, 1, 1, 0, 1) 88

y el resultado se escribe en la cuarta fila de la tabla, o sea la fila correspondiente a x 3. La otra fila (tercera) transformada que deberá contener un cero en su segundo elemento se consigue multiplicando la quinta fila por  2 y sumándola a la tercera fila de la tabla anterior, del siguiente modo:  2 ( 1, 1, ¼, 0, 1/4, 0, ¼) + (8, 2, 4, 0, 0, 1, 0) = (6, 0, 7/2, 0, ½, 1, 1/2) y los valores resultantes se colocan en la tercera fila de la nueva tabla, que ahora se denomina como la tabla correspondiente a la iteración 1 y aparece a continuación: Iteración 1 Cj CBi XBi XBi* 6  M X5 0 X3 8 3 x1 1 6M + Zj 3 ZjCj

Nótese que ahora

3 P1 0 0 1 6 0

2 P2 7/2 2 1/4 (7/2)M + 3/4 (7/2)M 5/4

0 P3 0 1 0 0

0 P4 1/2 1 1/4 (1/2)M 1/4

M P5 1 0 0 M

0

(1/2)M ¾

0

M P6 1/2 1 ¼ (1/2)M + 3/4 ½M+¾

la columna P1 es igual a la columna P6 de la tabla anterior.

Finalmente se calculan las filas correspondientes a las Zj y a las ZjCj tal como se indicó arriba. Para terminar la iteración 1 se aplica el criterio de optimalidad. Para que la solución encontrada sea óptima todos los ZjCj deberán ser no negativos. Como esto no es así, entonces se aplica de nuevo el criterio de entrada para seleccionar el vector que entrará en la base, o sea seleccionar el vector al cual corresponda el mínimo de ZjCj< 0. Se elige el min  Z2  C2, Z3C3 = min (7/2)M 5/4, (1/2)M 3/4 =  (7/2)M 5/4. Este valor corresponde a Z2 C2, lo cual indica que a la base entrará el vector P 2 y la variable x2 será básica. Se aplica nuevamente el criterio de salida, para determinar cual de los vectores que están en la base será sustituido por P2. Aplicando el criterio de salida se tiene

89

 6 8 1   = min  , , = min  12/7, 4, 4 = 12/7  7/2 2 1/4 

lo cual indica que saldrá de la base el vector P 5. Se procede ahora a construir la tabla correspondiente a la iteración 2 siguiendo los mismos pasos que para la iteración 1. El primer paso es dividir toda la fila por el elemento que se encuentra en la intersección de la columna P2 y la fila correspondiente a x5. Este elemento es 7/2. Se escribe una nueva tabla donde

en lugar de x5 estará x2 que es la nueva variable básica y mediante

transformaciones elementales se calculan los demás elementos de la tabla transformada en la misma forma que en los casos anteriores, llegando a Iteración 2 Cj CBi XBi XB* 2 x2 12/7 0 x3 32/7 3 x1 4/7 36/7 Zj ZjCj

3 P1 0 0 1 3 0

2 P2 1 0 0 2 0

0 P3 0 1 0 0 0

0 P4 1/7 5/7 2/7 4/7  4/7

M P5 2/7 4/7 1/4 1/7 M+1/7

M P6 1/7 5/7 2/7 4/7 M+4/7

Nótese que no todos los ZjCj 0. Aplicando los criterios de entrada y salida a la base se deberá seleccionar el vector P4 para entrar en la base y sustituirá al vector P 3. La base ahora contendrá a las variables x2, x4 y x1. Realizando las operaciones conocidas se llega a siguiente tabla que contendrá la solución óptima: Iteración 3 Cj CBi XBi 2 x2 0 x4 3 x1 Zj

XB* 28/35 32/5 84/35 308/3 5 ZjCj

3 P1 0 0 1 3

2 P2 1 0 0 2

0 P3 1/5 7/5 2/5 4/5

0 P4 0 1 0 0

0

0

4/5

0

M P5 6/35 4/5 9/5 159/70 M 159/70

M P6 0 1 0 0 M

De acuerdo a este resultado la solución óptima será X* = (x1*, x2*, x3*, x4*, x5*) = (84/35, 28/35, 0, 32/35, 0) 90

y el valor máximo de la función objetivo es Z* = 308/35 = 8.8 Ejemplo 6 Resolver el siguiente problema de PL: min Z = 4x1+ 7x2 sujeto a: 8x1 + 12x2 60 2x1 + 6x2 30 3x1 2x2 15 x1 0, x2 0 Transformando el conjunto de restricciones en igualdades mediante la adición de variables de holgura y tomando en consideración las variables artificiales necesarias para completar la base de partida para comenzar los cálculos el problema quedaría en la siguiente forma: min Z = 4x1 + 7x2 + 0x3 + 0x4 + 0x5 + Mx6 + Mx7 + Mx8 sujeto a 8x1 + 12x2 x3 + x6 60 2x1 + 6x2 x4 + x7 30 3x1 2x2 x5+ x8  15 Xj 0, j = 1, 2, ... , 8 Nótese que como todas las restricciones son de mayor o igual, será necesario considerar tres variables artificiales para poder formar la base. Como el problema es de minimizar entonces el signo del coeficiente M en la función objetivo deberá ser positivo para que el algoritmo Simplex las elimine de la solución básica. Las iteraciones cero y uno se dan a continuación:

91

Iteración 0 Cj CBi XBi

XB

M

x6

M M

4 P1

7 P2

0 P3

0 P4

0 P5

M P6

M P7

M P8

60

8

12

1

0

0

1

0

0

x7

30

2

6

0

1

0

0

1

0

x8

15

3 13M 13M4

1 0 M M M 0

0 M 0

1 M 0

*

Zj ZjCj

0 2 16M M 16M M 7 Iteración 1

0 M M

7

x2

5

2/3

1

1/12

0

0

0

0

M

x7

0

2

0

½

1

0

1

0

M

x8

25

13/3 7/3M+14/ 3 7/3M+2/3

0 7

1/6 1/3M7/1 2 1/3M1/1

0 M

1 M

0 M

1 M

M

M

0

0

Zj ZjCj

0

2 Y finalmente se llega a la tabla contentiva de la iteración óptima. Nótese que las columnas correspondientes a las variables artificiales se han eliminado de la tabla. En realidad, en el proceso de cálculo, a medida que los vectores artificiales salen de la base, las columnas correspondientes se pueden eliminar, pues las variables correspondientes no deben aparecer en la misma. Cj *

4 P1

7 P2

0 P3

0 P4

0 P5

CBi

XBi

XB

7

X2

4680/1716

0

1

0

3/22

9/143

0

X3

300/11

0

0

1

12/11

12/11

0

3/11 3/11 29/22 219/14 3

4 X1 975/143 1 79560/1716 0 ZjCj

0 0

0

92

La solución óptima será X* = (x1, x2, x3, x4, x5) = ( 975/1716, 4680/1716, 300/143, 0, 0) X* = (6.8181, 2.7272, 27.2727, 0, 0) y el valor mínimo de la función objetivo es Z* = 79560/1716 = 46.3636

93

IV. PROGRAMAS COMPUTACIONALES. ANÁLISIS DE LA SOLUCIÓN ÓPTIMA

Objetivo: Preparar al estudiante para que pueda resolver los problemas de Programación Lineal, mediante programas informáticos profesionales y que sea capaz de interpretar desde el punto de vista físico y económico la solución óptima.

En este apartado se realizará un primer análisis económico de la solución óptima, aunque para un análisis más amplio son necesarias algunas cuestiones que se verán en capítulos posteriores como son el análisis de las variables duales y el análisis de sensibilidad. Para realizar el análisis económico de la solución se retomará el ejemplo 1 sobre programación de la producción, visto en el capítulo 1. Ejemplo 7 En ese problema se deseaba hallar un programa de producción de cargadores y zanjeadoras que proporcionará el máximo valor de las utilidades totales. El modelo matemático correspondiente es el siguiente:

94

Max Z = 5000 X + 4000 Y

función objetivo

sujeto a 10 X + 15 Y  150

horas en el departamento A

20 X + 10 Y  160

horas en el departamento B

30 X + 10 Y  135

horas de comprobación o

chequeo X - 3Y  0 X +

requerimiento mixto

Y  5

producción combinada

requerida X , Y  0condición de no negatividad Las variables del problema son: X = x1 = número de cargadores a producir Y = x2 = número de zanjeadoras a producir Si el problema se resuelve por el método Simplex la solución que se obtiene es la siguiente: X* = (x1*, x2*, x3*, x4*,x5*, x6*, x7) = ( 4.5, 7.0, 0, 70, 2.5, 6.5) Z* = $ 50 500.00 Para realizar el análisis de la solución es importante distinguir entre las variables esenciales y las de holgura. Las esenciales proporcionan el programa de producción mientras que las variables de holgura dan una idea de la utilización que se requiere de los recursos en caso de producir de acuerdo a la solución hallada, es decir, se interpretan como recursos que quedan sin utilizar de los disponibles (en caso de corresponder a restricciones de menor o igual) y recursos que se emplean por encima de los mínimos establecidos. Los valores de las variables esenciales X y Y indican que cargadores

se deben fabricar 4.5

y 7 zanjeadoras. Con este programa de producción se alcanzará una

ganancia total ascendente a $ 50 500.00 pesos. Con esta solución se utilizará todo el tiempo disponible de los departamentos A y B. Se utilizarán 70 horas por encima del mínimo obligatorio para comprobación o chequeo. Las restricciones de requerimiento 95

mixto y de producción combinada se cumplirán exactamente. Esta información puede comprobarse sustituyendo los valores de las variables esenciales en las restricciones. Ejemplo 8 Considérese el problema del ejercicio 2 del capítulo 1 que trata sobre un programa productivo para una planta elaboradora de productos lácteos. Las variables de decisión en este problema son: x1 y x2 = TM de leche condensada y TM de leche evaporada respectivamente a elaborar por día. El modelo matemático completo es el siguiente: maximizar Z = 200 x1 + 300 x2 sujeto a x1 50 x1

60



x2



x2

75

65

X1

1 1

 400

x2 450 0.3 x1 + 1.3 x2 650 55 x1 + 21 x2 24 750 x1, x2≥ 0

Si se resuelve este modelo a través de cualquier método conocido, se llega a la siguiente solución óptima: X *= (x1*, x2*, x3*, x4*, x5*, x6*, x7*, x8*) = (121,66; 450, 0, 0,11; 278,3; 0, 28,5; 8 608,33) Z* = 159 333.30 Esta solución indica que se deberán elaborar 121.66 t de leche condensada, 450 t de leche evaporada para conseguir una posible ganancia óptima ascendente a 159 333.3 USD. En cuanto a las variables de holgura, se tiene que con un programa de producción como el anterior, se aprovechará toda la capacidad existente en el Departamento A, se

96

dejará de aprovechar un 11 % de la capacidad del Departamento B. Esto en lo referente a los departamentos en que se elabora conjuntamente ambos productos. En el caso del Departamento C que solo elabora leche condensada, se dejará de aprovechar capacidad como para producir 278,3 t de leche condensada, o lo que es lo mismo, este departamento se utilizará solo a un 69,58 % de sus posibilidades. El Departamento D se aprovechara al 100 % de su capacidad. En cuanto a la materia prima fundamental o sea la leche fresca disponible diariamente, se dejarán de utilizar 28.5 t diariamente, las cuales se podrían utilizar en otro tipo de producto. Además, en cuanto a la Vitamina que se le agrega a la leche, se utilizarían 8 608,33 kilogramos menos de los disponibles. Observación El análisis de la iteración óptima en realidad es mucho más amplio que el que se ha realizado en estos

ejemplos anteriores, pero se requieren algunos conocimientos

acerca de la teoría de la dualidad y del análisis de sensibilidad que se verán en capítulos posteriores. El análisis completo de la iteración óptima se realizará después de haber estudiado estos temas en estudios de casos. Tipos especiales de solución Una cuestión importante para el lector, es conocer que durante el proceso de solución o al terminar de resolver un problema de PL, pueden aparecer soluciones que difieren de lo estudiado hasta aquí y que deben conocerse para poder llegar a una conclusión acertada acerca de la naturaleza del problema cuya solución se desea encontrar. Estas soluciones pueden ser las siguientes: Solución alterna: Es una solución alternativa que en ocasiones se presenta una vez resuelto el problema de PL. Este tipo de solución se identifica en la tabla que contiene a la solución óptima, cuando uno o más de los ZjCj correspondientes a un vector no básico, tienen valor cero. Recuérdese que en la solución óptima, los ZjCj correspondientes a los vectores

97

básicos están obligados a ser iguales a cero, pero los demás pueden ser iguales a cero o diferentes. Cuando el ZjCj de un vector no básico es igual a cero en la tabla final, entonces este vector puede introducirse en la base y luego de realizar las operaciones necesarias, se encontrará una nueva solución que también será óptima. Gráficamente esto ocurre cuando la función objetivo es paralela a alguna de las restricciones y al desplazarse en el sentido del objetivo (maximizar o minimizar) en vez de tocar un último punto extremo del conjunto convexo de soluciones posibles, toca a una recta y por tanto a dos puntos extremos. En ese caso, todos los puntos situados encima de la recta que une a esos dos puntos extremos proporcionan el mismo valor de la función objetivo que los puntos correspondientes a las soluciones óptimas. Ejemplo 9 Un ejemplo sería el siguiente problema min Z = 3x1 + 4x2 sujeto a; (1) (2)

6x1 + 8x2 24 6x1 + 3x2 18

x1, x2 0 Si se resuelve gráficamente este problema, se verá que cuando la función objetivo alcanza su valor mínimo, se superpone a la restricción (1). Esto indica que existirán dos puntos extremos que son óptimos: X’ = (0, 3) y X’’ = (2.4, 1.2) que en este caso coinciden con los puntos A y B. Si se sustituyen las coordenadas de estos dos puntos dará el mismo valor de la función objetivo Z* = 12. Pero además cualquier punto que se encuentre sobre el segmento de recta que une a los puntos A y B, también proporcionará el mismo valor de Z. Por ejemplo, el punto (1,2, 2,1) está sobre ese segmento de recta. Si se sustituyen las coordenadas de este punto en la función objetivo se comprueba que también proporciona el valor Z* = 12.

98

x2 C 2

A B 1

Z2 =20

z1=12

x1

Grafico 3 La importancia de que aparezcan soluciones alternas en el proceso de solución de un problema de PL es evidente. En este caso, la dirección de la empresa tiene en sus manos un conjunto mayor de alternativas para utilizar sus recursos y cualquiera de ellas le proporciona un cumplimiento óptimo del objetivo trazado. Solución degenerada: Tal como se definió al principio de este capítulo, una solución degenerada es una solución que tiene menos de m componentes positivos, donde m es el número de restricciones. En el transcurso del proceso de solución mediante el Simplex, este tipo de solución aparece cuando al aplicar el criterio de salida, el valor de  es el mismo para más de un vector. En este caso, al realizar las operaciones necesarias para el cambio de base, una o más variables básicas serán iguales a cero en la siguiente iteración y se llegará a la situación definida arriba. Al mismo tiempo se ve claro, que una solución de este tipo puede aparecer en una iteración y desaparecer en la siguiente, o mantenerse hasta llegar a ser la solución óptima. Una solución de este tipo no tiene la mayor importancia, excepto en el sentido teórico, ya que desde el punto de vista del modelo, la degeneración en la solución óptima refleja que hay al menos una restricción redundante.

99

Ejemplo 10 Sea el siguiente problema de PL maximizar Z = 3x1 + 9x2 sujeto a:: x1 + 4x2 8 x1 + 2x2 4 x1, x2 0 Resolviendo el problema a través del método Simplex, se llega a

una solución

degenerada, tal como aparece al final de la tabla siguiente: Cj CBI 0 0

XBi

Po

X3 8 X4 4 ZjCj

9 X2 0 X4 ZjCj 9 X2 3 x1 ZjCj

2 0 18 2 0 18

3

9

0

0

P1

P2

P3

P4

1 1 3

4 2 9

1 0 0

0 1 0

¼ ½ ¾ 0 1 0

1 0 0 1 0 0

¼ 1/2 9/4 ½ 1 3/2

0 1 0 1/2 2 3/2

La solución óptima es degenerada pues tiene una variable básica a nivel cero (x 1). Si se resuelve el problema gráficamente se observa que la restricción (1) es redundante. x2

1

Z

2

x1

Gráfico 4

100

Solución no acotada: Ocurre cuando el valor de la función objetivo puede crecer (en un problema de máximo) o disminuir (en un problema de mínimo) sin límites. Es decir, resulta imposible hallar un valor finito para la función objetivo. Gráficamente esto se puede ver cuando el conjunto de soluciones posibles no está acotado en la dirección en que la función objetivo tiende hacia su cumplimiento. x2

Z2 Z1 x1

Gráfico 5 En el gráfico (5) se observa una situación en que la función objetivo Z crece en una dirección en la cual el conjunto convexo de soluciones posibles del problema no está limitado. Es posible reconocer cuando en el proceso de solución se llega a una situación de este tipo, en la tabla final del Simplex, cuando en la columna Pk correspondiente al vector entrante ak, todas las pik 0. Esto indica que no puede determinarse el vector que debe salir de la base. En la práctica, la solución no acotada se presenta solo cuando se han cometido errores en la elaboración del modelo matemático. Se recomienda entonces, revisar el modelo en su totalidad para verificar si está correctamente construido.

101

Ejemplo 11 Sea el siguiente problema de PL maximizar Z = 2x1 + x2 sujeto a: x1 x2 10 2x1 40 x1, x2 0 Aplicando el procedimiento del simplex a la solución de este problema, se tiene la siguiente tabla inicial

P0

2 P1

1 P2

0 P3

0 P4

X3

10

1

1

1

0

X4 ZjCj

40 0

2 2

0 1

0 0

1 0

CBi 0

Cj XBi

0

De acuerdo a la tabla anterior, al aplicar el criterio de entrada, el vector P 2 entraría en la base. Sin embargo, al aplicar el criterio de salida, no se puede seleccionar ningún vector, pues todos los pij 0. Esto quiere decir que x2 se puede hacer crecer en forma indefinida sin que se infrinja ninguna de las restricciones. Como cada incremento unitario en x2 aumentará a Z en uno, un incremento infinito de x2 provocará un incremento infinito en Z. Por esta razón se dice que el problema tiene solución no acotada. Se deja al lector como ejercicio resolver el problema gráficamente y demostrar que el conjunto convexo de soluciones posibles es no acotado. Restricción redundante: Este caso se presenta, como su nombre lo indica, cuando se incluyen en el sistema de restricciones una o más de estas, que son innecesarias por no acotar realmente al conjunto convexo de soluciones posibles. Esto se produce porque otras restricciones

102

son más limitantes que la considerada como redundante. Las restricciones que tienen esta característica se pueden eliminar del problema sin afectar la solución óptima. De manera esquemática se puede graficar la situación en la siguiente forma: x2

A B C

x1 Gráfico 6

Obsérvese que la región de solución está limitada por las restricciones A, C y los ejes coordenados. La región de soluciones de la restricción B abarca puntos que están dentro de la región general de soluciones posibles y puntos que están fuera. La restricción C es más restrictiva que la B. Por tanto, la B puede ser eliminada sin causar ningún perjuicio. Cuando las restricciones redundantes son del tipo  resulta muy difícil identificarlas. Sin embargo, cuando son de otro tipo ( = ó  ) entonces es posible identificarlas en el proceso de solución mediante el método Simplex. En esta última situación, cuando el problema se resuelve utilizando el método Simplex, es posible detectar si el problema tiene restricciones redundantes cuando en la columna relativa a la base, en la iteración óptima aparecen una o más variables artificiales con valor cero, teniendo esta fila todos los pij =0. La variable artificial

que tiene esta

característica identifica la restricción redundante y que puede ser eliminada.

103

Ejemplo 12 Sea el siguiente problema de PL min Z = x1 + 3x2 + 3x3 sujeto a: x1 + 2x2 + 3x3 + x4 = 1800 x1+ 2x2 =1000 3x3 + x4 = 800 x1, x2, x3, x4 0 Resolviendo el problema a través del método Simplex se llega a la siguiente iteración óptima:

CBi

Cj XBi

Po

1 P1

3 P2

3 P3

4 P4

M P5

M

x5

0

0

0

0

0

1

1

x1

1000

1

2

0

0

0

3

x3

800/3

0

0

1

1/3

0

Z0 = 1800

0

1

0

3

0

ZjCj

En la tabla anterior la variable artificial x5 aparece en la solución óptima a nivel cero y el resto de los elementos de la fila (excepto claro está, el 1 correspondiente al vector columna P5) son ceros. Esto indica que la restricción en la cual se encuentra la variable artificial x5 es redundante, en este caso la primera. Solución no posible. Este tipo de situación aparece cuando el conjunto de restricciones del problema de PL no tiene un conjunto de soluciones posibles que sea común a todas. Una situación así no puede ocurrir cuando todas las restricciones son del tipo , ya que la variable de holgura produce siempre una solución factible. Sin embargo, cuando se emplean otros tipos de restricciones, se deberán usar variables artificiales, y esto puede dar lugar a la aparición de la solución no posible. Esto se refleja en la tabla cuando una variable artificial aparece en la solución óptima con valor positivo.

104

Cuando en la práctica aparece una situación de este tipo, esto indica que el modelo no fue formulado correctamente y por ello, aparecen restricciones que están en conflicto. También puede ser que la naturaleza de las variables no fue tomada correctamente. Ejemplo 12 Sea el siguiente problema de PL maximizar Z = 3x1 + 2x2 sujeto a 2x1 + x2  2 3x1 + 4x2 12 x1, x2 0 Aplicando las técnicas del método Simplex a la solución del problema anterior se tiene:

CBi 0

Cj XBi

P0

3 P1

2 P2

0 P3

0 P4

M P5

X3

2

2

1

1

0

0

12  12M

3  5M3

4  4M2

0 0

1 M

1 0

1

1

1/2

1/2

0

0

9 9M +2

0 0

5/2 5/2M 1

1/2 1/2M+1

1 M

1 0

2

2

1

1

0

0

4 4M +4

5 5M +1

0 0

3 3M+2

1 M

1 0

X5 M ZjCj 2

X1

X5 M ZjCj 2

X2

X5 M ZjCj

Se ha llegado a la solución óptima y como se observa entre las variables básicas positivas, se encuentra x5 que es una variable artificial. Esto indica que el problema es imposible o sea que el espacio de soluciones seainfactable. A esta solución también se le denomina como seudoóptima. Si este problema se resuelve de manera gráfica se tiene la siguiente figura en la cual se nota claramente que las regiones de solución de las restricciones no tienen puntos comunes y por tanto el problema no tiene solución posible. 105

x2

2

1

Z

x1 Gráfico 8

Solución por computadora Hasta el momento se han estudiado dos procedimientos de solución: el gráfico y a través del método Simplex estándar. Sin embargo, en la actualidad el procedimiento más común para resolver un problema de PL en la actualidad, es mediante el uso de computadoras. La difusión que han alcanzado las computadoras personales, sus posibilidades de almacenamiento de datos, así como el perfeccionamiento de paquetes de programas adecuados para diferentes tipos de situaciones enmarcadas dentro de los métodos cuantitativos aplicados a la esfera económica, hacen que hoy sea cada vez más fácil su utilización por la dirección de la mayoría de las empresas. Las computadoras constituyen un formidable instrumento para el trabajo con los sistemas contables y financieros de las empresas, y con una adecuada preparación pueden servir también para resolver muchos problemas en los cuales sea necesario utilizar métodos cuantitativos para disponer de elementos suficientes en problemas de toma de decisiones en la actividad gerencial. Este apartado se presentan los resultados obtenidos al aplicar uno de los múltiples programas de computadora existentes, que pueden ser utilizados para la solución de problemas de PL. Algunos de los programas más utilizados en nuestro país son: OL, Micromanager, QM, MS, LINDO, LINGO, LO, etc. En particular, aquí se verán los resultados de la aplicación del LINDO. Este programa puede resolver no solo problemas de PL, sino también problemas de Programación en Enteros y Programación no Lineal.

106

Ejemplo 13 Supongamos el siguiente problema de PL, donde x: número de cargadores frontales, y: zanjeadoras. El planteamiento matemático quedaría editado en la siguiente forma en el programa LINDO. El planteamiento matemático de trabajo es el siguiente: Max Z = 5000 x + 4000 y Sujeto a 10x + 15 y  150 14x + 10y  160 18x + 10y  135 x – 3y  0 x + y5

x 0, y  0

Este problema escrito en la pantalla de edición del programa quedaría así: MAX

5000 X + 4000 Y SUBJECT TO 2) 10 X + 15 Y = 0 6) X + Y >= 5 END y la solución correspondiente mediante el comando GO aparecería en la siguiente forma:

107

LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1)

58461.540

VARIABLE X

VALUE REDUCED COST 9.230769 .000000

Y

2)

3.076923

.000000

ROW SLACK OR SURPLUS DUAL PRICES 11.538460 .000000 3)

.000000

365.384600

4)

61.923080

.000000

5)

.000000

-115.384600

6)

7.307693

NO. ITERATIONS=

.000000 3

La solución se encuentra después de tres iteraciones. Una vez obtenida la solución, o sea los valores de las variables básicas y de holgura, el programa tiene la opción de pedir el análisis de sensibilidad lo cual será objeto de estudio en otro capitulo de este libro. En la solución anterior aparecen otros datos que constituyen los valores de las variables esenciales y de holgura del problema dual que también serán estudiados en el capítulo correspondiente. La solución obtenida refleja que deberán fabricarse 9.23 cargadores frontales y aproximadamente 3 zanjeadoras, para obtener un valor máximo de Z ascendente a $ 58 461.54 de ganancias. Existe una holgura de 11.54 horas en el departamento A, es decir, son horas que no serán utilizadas, mientras que en el departamento B, no hay holgura pues se utilizarán todas las horas disponibles. Se utilizará exactamente el tiempo mínimo señalado para la comprobación de los equipos y la producción conjunta mínima de los dos tipos de equipo se excederá en 4.23 unidades. Con la solución obtenida se satisface la restricción que plantea que al menos deben fabricarse una zanjeadoras por cada tres cargadores.

108

Ejemplo 14 En este caso se aplicará el método de solución por computadora al problema 2 del capítulo 2, en el cual de desea encontrar una combinación óptima de fabricación de toneladas de leche condensada y de leche evaporada a partir de leche fresca y cumpliendo un conjunto de condiciones limitantes. El planteamiento matemático editado en el programa LINDO quedaría como sigue: 1 MAX

200 X1 + 300 X2

2 SUBJECT TO 3

2) 0.0033 X1 + 0.00133 X2