universidad tÉcnica “luis vargas torres” de …
TRANSCRIPT
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
2
Í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
3
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
4
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.
5
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
6
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.
7
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.
8
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
9
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).
1Teoría expuesta en el libro “Modelos Cuantitativos para la administración” de Roscoe, Davis; Mckeown,
Patric. University of Georgia. Grupo Editorial Iberoamericano. 1991
10
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á
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:
*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.
11
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.
12
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.
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
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.
13
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
Departamento
Horas/ cargador
Horas/ zanjeadoras
Total horas 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
14
horas de comprobación y cada zanjeadoras, 10. Estos datos se dan en el cuadro
siguiente:
Datos de la comprobación de equipos
Horas/ Cargador
Horas/Zanjeadoras Horas requeridas
Horas de comprobación
18 10 135
5. 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:
15
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).
16
Otra restricción es que se debe producir al menos una zanjeadoras por cada tres
cargadores. Esto se puede escribir como una proporción
1
3
Y
X
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
17
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.
18
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á
19
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.
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:
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
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.
20
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:
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
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.
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.
21
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,
22
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:
23
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
24
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á 150 de la capacidad total del
departamento y una tonelada de leche evaporada utilizará 175 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
1 75
2x
50
1x
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á
1 652x
601x
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
25
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á:
26
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
1 752x
501x
1 652x
601x
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.
27
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
28
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:
29
Contenidos y precios por libra de alimento
Alimento Contenido de
proteína (onzas)
Contenido de carbohidratos
(onzas)
Contenido de grasa (onzas)
Precio
$
1 3 7 5 4
2 5 4 6 6
3 2 2 6 3
4 3 8 2 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:
30
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 6 meses 12 meses 18 meses 24 meses
Ingresos 1 000000 700 000 1 800 000 400 000 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 6 meses 12 meses 18 meses 24 meses
Ingresos 800 000 500 000 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
31
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
32
Tomando en cuenta que, debido a los intereses que se percibirán, w1 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
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:
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 = 500 000
1 800 000 x + 200 000 y 1.07 w2 + w3= 400 000
400 000 x + 700 000 y 1.07 w3 + w4= 380 000
x 1
y 1
x 0, y 0, wi 0, i = 1,2,3,4
33
Embarcación
Precio de venta por
unidad ($)
Costo variable por
unidad ($)
Costo fijo ($)
Pegasos $ 10 000 $ 5 000 $ 5 000 000
Sirenas 7 500 3 600 3 000 000
Tritones 15 000 8 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.
34
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á:
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
5 000 000
1 000
$
No. de Pegasos
Función in
greso
Función Costo
10 000 000
Cantidad de punto
de equilibrio
35
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:
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: 5105 , 51010, 101010. 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.
min Z = 5 000 x1 + 3 600 x2 + 8 000 x3
sujeto a
5 000 x1 + 3 900 x2 + 7 000 x3 = 18 000 000
x1 700
x2 400
x3 300
x1, x2, x3 0
36
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 inertes
5.00
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 5105 durante el periodo que se planifica.
Precio de los fertilizantes terminados (por
tonelada)(USD)
5105 51010 101010
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:
37
Tipo 5105 (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.05) ( 160) = 8.00
Costo de los ingredientes inertes ( 0.80) ( 10) = 8.00
Costo total de los ingredientes 34.00
Costo de mezclado 15.00
Costo por tonelada$ 49.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 51010 (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
101010 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
38
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.
Cultivo
Rendimiento
(Kgs. por há)
Demanda de los miembros (
kgs.)
Demanda del mercado (en
kgs)
Utilidad (USD por
kg.)
Frijol 420 2000 10 000 .90
Maíz 200 5000 8 000 .70
Maní 70 1000 3 000 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).
39
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 x25000
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
40
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
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.
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
41
Las disponibilidades de estas planchas se muestran en la siguiente tabla:
Largo Ancho Grosor Disponibilidad (unidades)
Tipo 1 170 cms. 20 cms. 10 mm 6 00
Tipo 2 150 cms. 20 cms. 8 mm. 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 Demanda mínima
Mesa de tipo 1 80 unidades
Mesa de tipo 2 95 unidades
Mesa de tipo 3 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 cms- 40 cms. Desperdicio
Variante 1 2 1 10
Variante 2 4 10
42
Combinaciones de corte posibles Planchas de 150 cms. de largo
Número de piezas de:60 cms. 40 cms. 30 cms Desperdicio
Variante 1 2 1 0
Variante 2 1 2 10
Variante 3 1 3 0
Variante 4 3 1 0
Variante 5 2 2 10
Variante 6 5 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 + 2x3 + x4 + x5 800 mesas de 60 cms.
x1 + 4x2 + 2x4 + 3x6 + 2x7 950 mesas de 40 cms.
x3 + 3x5 + x6 + 2x7 + 5x8 105 mesas de 30 cms. La función objetivo será:
Min Z = 10x1 + 10x2 + 0x3 + 10x4 + 0x5 + 0x6 + 10x7 + 0x8 desperdicio
43
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 ($)
Tipo de proyecto Valor presente Estimado(USD)
Requerimientos de capital Año 1 Año 2 Año 3 Año 4
(USD)
Expansión de la
planta
180 000 30000 40000 40000 30000
Nueva maquinaria 20 000 12000 8000 0 4000
Investigación sobre nuevos mercados
72 000
30000
20000
20000
20000
Ampliación del
almacén
80 000 20000 30000 40000 10000
Fondos disponibles de
capital
65000 80000 80000 50000
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.
44
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
45
xj: proporción que indica el porcentaje en que se financia el proyecto j. Si xj = 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
46
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 c1, c2 y c3 y por
p1, p2 y p3 a los proyectos. Las cantidades ofrecidas se expresan en cientos de miles
de dólares.
Proyectos(100 000USD)
Contratistas p1 p2 p3
c1 28 32 36
C2 36 28 30
c3 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( 321) o
sea 6 maneras posibles de realizar las asignaciones. Esto puede verse en la tabla
siguiente:
47
Asignaciones
Aportes totales (en cientos de miles de dólares)
c1 c2 c3 96
C1 c3 c2 92
c2 c3 c1 106
C2 c1 c3 108
c3 c1 c2 100
c3 c2 c1 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
48
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,
49
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óninventario
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
50
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 un
programa óptimo de producción que minimice los costos totales 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:
51
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
52
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
53
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.
54
Patrón de inversiones del Banintur:
Inversión
DisponibleAño
1
Año
2
Año
3Año
4
Año
5Año
6
Año
1
Tipo 1
Tipo 2
Tipo 5
Tipo 6
Año
2
Tipo 1
Tipo 2
Tipo 3
Tipo 6
Año
3
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
6Tipo 6
28 %
16 % 45 %
0 %
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
55
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
56
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
57
:
Ingrediente
Producto Alfa Beta Gamma
Levisol 4 7 8
Lindosol 3 9 7
Solar 2 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
Contribución a las
utilidades(USD)
Disquete 2,00
Cassette 1,00
Paquete de limpieza
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:
58
Horas por unidad
Producto Centro 1 Centro 2 Centro 3
Disquete 3 2 1
Cassette 4 1 3
Paquete de Limpieza
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 Gastos fijos
(USD)
Centro 1 60 horas 1000
Centro 2 40 horas 2000
Centro 3 80 horas 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
59
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 de las dos plantas
difieren, sus costos variables también son diferentes. 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:
Productos
Precio de venta y demanda
No. 1 No. 2 No. 3 No. 4
Precio de venta(USD) 200 300 250 280
Costos variable : planta 1
160 270 240 270
Costos variables: planta 2
220 300 200 220
Demanda ( unidades) 1000 3000 4000 6000
60
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).
Producto
Número 1
Número 2
Número 3
Número 4
Planta 1
Operación A 6.0 7.2 4.0 7.0
Operación B 18.0 20.0 16.0 18.0
Operación C 2.0 2.0 1.0 1.0
Planta 2
Operación X 8.0 8.0 4.0 8.0
Operación Y 10.0 16.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
61
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 Rendimientos (qq. por há)
Demanda de los miembros (qq)
Demanda del mercado( qq)
Utilidad ( USD / qq)
Frijol 420 2000 10 000 1.50
Plátano 200 5000 8000 1.80
Maíz 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.
62
Número del puesto de trabajo
No. del candidato al puesto
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
63
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
Fertilizante
Contenido de
nitrógeno (libras)
Contenido de fósforo
(libras)
Contenido de potasio
(libras)
Precio
($)
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
64
acondicionado: el R1500 y el R2500. 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 unidad ($)
Costo variable por unidad ($)
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 Inversión
USD
Réditos estimados
USD
Centros comerciales
400 000 575 000
Aceite de esquistos
500 000 750 000
Casas de bajos ingresos
350 000 425 000
Low-incomeHousing
450 000 510 000
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.
65
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
66
III. MÉTODOS DE SOLUCIÓN
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
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.
67
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
nn xc . . . xc xcxc Z 332211 (1)
sujeto a:
(2)
b , ,xa . . . xa xa xa
.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
b , ,xa . . . xa xa xa
b , ,xa . . . xa xa xa
mnmn3132m21m1
2n2n323222121
1n1n313212111
x1, x2, x3, . . . , xn 0 (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
68
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:
Maxó min Z = j
xn
1j jc
sujeto a:
m:1i ;i
)b,,(j
xn
1j ija
xj 0; 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.
69
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.
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.
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.
70
Ejemplo 1 Sea el siguiente problema de PL:
Max Z = 4x1 + 5x2 sujeto a:
1) 8x1 + 3x2 24
2) 2x1 + 6x2 12
3) x1 + x2 6
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
71
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):
1) 8x1 + 3x2 24
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
3) x1 + x2 6
(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
(1)
(2)
(3)
A
B
C
X2
X1
R
72
73
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
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.
(1)
(2)
(3)
A
B
C
X2
X1
Z1 = 20
Z2 = 40
74
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.
75
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
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
R
X1Z1 = 6
Z1 = 24
X* = (1.6, 4,8)
76
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:
77
Cj C1 C2 . . . Ck . . . Cn
CB i XBi XB* P1 P2 . . . Pk . . . Pn
CB1 XB2 XB1* p11 p12 . . . P1 k . . . p1n
CB2 XB2 XB2* p21 p22 . . . p2k . . . p2n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . .
. . .
CBm XBm XBm* pm1 pm2 . . . pmk . . . pmn
Zj Z0 Z1 Z2 . . . Zk . . . Zn
ZjCj ZjCj ZjCj ZjCj ZjCj
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.
78
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:
8x1 + 3x2 x324
2x1 + 6x2x412
x1 + x2+ x5 6
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:
79
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 = 12
4x1 + 3x2 + 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.
A=2 4 1 0
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 = 12
4(0) + 3(0) + x4 = 24
En este caso se dice que estas variables constituyen una solución básica.
80
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 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:
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
variables de holgura.
81
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 3 2 0 0 0
CBi XBi XB* P1 P2 P3 P4 P5
0 x3 9 3 3 1 0 0
0 x4 20 4 5 0 1 0
0 x5 21 3 7 0 0 1
Zj 0 0 0 0 0 0
ZjCj 3 2 0 0 0
Como se explicó arriba, los valores de Zj se calculan multiplicando la columna de los CBi
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 ZjCj. 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 ZjCj correspondientes a los
vectores que están en la base, son exactamente iguales a cero. Aunque si los ZjCj
son iguales a cero, esto no quiere decir que el j-ésimo vector sea básico.
82
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:
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:
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 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 optimalidad que permitirá conocer, después de
hacer las correspondientes sustituciones, si se ha llegado o
no a la solución óptima.
83
Caso de un problema de maximizar
Caso de un problema de minimizar
Criterio de entrada en
la base: Seleccionar
aquel vector ak tal que:
ZkCk = min (ZjCj) para
todo aj cuyo ZjCj< 0
ZkCk = max (ZjCj) para
todo aj cuyo ZjCj> 0
Criterio de salida de la
base: Seleccionar aquel
vector al cual
corresponda , siendo
0p ;p
x
ip
x
ijij
*Bi
rj
*Bi
min
Criterio de optimalidad: Cuando se cumple que
ZjCj 0 para todo aj de A
ZjCj 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 ZjCj 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
ZkCk = min (ZjCj) para todo aj cuyo ZjCj< 0 o lo que es igual
ZkCk = min ZjCj / ZjCj< 0
= min 3, 2 = 3 = Z1 C1
Esto indica que entrará en la base el vector P1 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:
84
0 ;
*i
*i
ijp
ijp
xmin
rjp
xBB
i
= 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 P1 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á:
85
Iteración 1
Cj 3 2 0 0 0
CBi XBi XB* P1 P2 P3 P4 P5
3 x1 3 1 1 1/3 0 0
0 x4 8 0 9 4/3 1 0
0 x5 12 0 10 1 0 1
Zj
ZjCj
A partir de estos resultados se tendrá que aplicar el criterio de optimalidad. Es decir,
verificar si todos los ZjCj son mayores o iguales que cero. Calculando los ZjCj 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 ZjCj. La tabla completa quedaría así
Iteración 1
Cj 3 2 0 0 0
CBi XBi XB* P1 P2 P3 P4 P5
3 x1 3 1 1 1/3 0 0
0 x4 8 0 9 4/3 1 0
0 x5 12 0 10 1 0 1
Zj 9 3 3 1 0 0
ZjCj 0 5 1 0 0
Como se observa, aún no se ha llegado al óptimo ya que no todos los ZjCj 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.
86
Iteración 2
Cj 3 2 0 0 0
CBi XBi XB* P1 P2 P3 P4 P5
3 X1 35/9 1 0 5/27 1/9 0
2 X2 8/9 0 1 4/27 1/9 0
0 x5 28/9 0 0 13/27 10/9
1
Zj 121/9 3 2 7/27 5/9 0
ZjCj 0 0 7/27 5/9 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:
87
maximizar Z = 3x1 + 2x2 + 0x3 + 0x4
sujeto a: 2x1 + 4x2 = 8
4x1 + 3x2 + x3 12
4x1 + x2 x44
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á
88
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 3 2 0 0 M M
CBi XBi XBi* P1 P2 P3 P4 P5 P6
M X5 8 2 4 0 0 1 0
0 X3 12 4 3 1 0 0 0
M x6 4 4 1 0 1 0 1
Zj 12M
6 M 5M 0 M M M
ZjCj 6
M3
5M2 0 M 0 0
Aplicando el criterio de optimalidad se observa que aún no todos los ZjCj 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 ZjCj / ZjCj< 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 x6 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 P1 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 P1 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)
89
y el resultado se escribe en la cuarta fila de la tabla, o sea la fila correspondiente a x3.
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 3 2 0 0 M M
CBi XBi XBi* P1 P2 P3 P4 P5 P6
M X5 6 0 7/2 0 1/2 1 1/2
0 X3 8 0 2 1 1 0 1
3 x1 1 1 1/4 0 1/4 0 ¼
Zj 6M + 3
6 (7/2)M + 3/4
0 (1/2)M 1/4 M (1/2)M + 3/4
ZjCj 0 (7/2)M
5/4
0 (1/2)M ¾ 0 ½ M + ¾
Nótese que ahora 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 ZjCj 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 ZjCj 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
ZjCj< 0.
Se elige el min Z2 C2, Z3C3 = 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 P2 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
90
= min
1/4
1 ,
2
8 ,
7/2
6 = min 12/7, 4, 4 = 12/7
lo cual indica que saldrá de la base el vector P5. 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 3 2 0 0 M M
CBi XBi XB* P1 P2 P3 P4 P5 P6
2 x2 12/7 0 1 0 1/7 2/7 1/7
0 x3 32/7 0 0 1 5/7 4/7 5/7
3 x1 4/7 1 0 0 2/7 1/4 2/7
Zj 36/7 3 2 0 4/7 1/7 4/7
ZjCj 0 0 0 4/7 M+1/7 M+4/7
Nótese que no todos los ZjCj 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 P3. 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 3 2 0 0 M M
CBi XBi XB* P1 P2 P3 P4 P5 P6
2 x2 28/35 0 1 1/5 0 6/35 0
0 x4 32/5 0 0 7/5 1 4/5 1
3 x1 84/35 1 0 2/5 0 9/5 0
Zj 308/35
3 2 4/5 0 159/70 0
ZjCj 0 0 4/5 0 M 159/70
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)
91
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:
92
Iteración 0
Cj 4 7 0 0 0 M M M
CBi XBi XB* P1 P2 P3 P4 P5 P6 P7 P8
M x6 60 8 12 1 0 0 1 0 0
M x7 30 2 6 0 1 0 0 1 0
M x8 15 3 2 0 0 1 0 0 1
Zj 13M 16M M M M M M M
ZjCj 13M4 16M
7 M M M 0 0 0
Iteración 1
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 0 1/6 0 1 0 1
Zj 7/3M+14/3
7 1/3M7/12
M M M M
ZjCj 7/3M+2/3 0 1/3M1/1
2
M M 0 0
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 7 0 0 0
CBi XBi XB* P1 P2 P3 P4 P5
7 X2 4680/1716 0 1 0 3/22 9/143
0 X3 300/11 0 0 1 12/11 12/11
4 X1 975/143 1 0 0 3/11 3/11
ZjCj 79560/1716 0 0 0 29/22 219/143
93
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
94
IV. PROGRAMAS COMPUTACIONALES. ANÁLISIS DE 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:
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.
95
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 se deben fabricar 4.5
cargadores 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
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 requerimiento mixto
X + Y 5 producción combinada
requerida
X , Y 0condición de no negatividad
96
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:
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
maximizar Z = 200 x1 + 300 x2 sujeto a
1 75
x
50
x 21
1 65
x
x 21
60
X1 400
x2 450
0.3 x1 + 1.3 x2 650
55 x1 + 21 x2 24 750
x1, x2≥ 0
97
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 ZjCj correspondientes a un vector no básico, tienen valor cero.
Recuérdese que en la solución óptima, los ZjCj correspondientes a los vectores
98
básicos están obligados a ser iguales a cero, pero los demás pueden ser iguales a cero
o diferentes.
Cuando el ZjCj 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) 6x1 + 8x2 24
(2) 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.
99
2
1
x1
x2
z1=12
A
BZ2 =20
C
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.
100
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 3 9 0 0
CBI XBi Po P1 P2 P3 P4
0 X3 8 1 4 1 0
0 X4 4 1 2 0 1
ZjCj 3 9 0 0
9 X2 2 ¼ 1 ¼ 0
0 X4 0 ½ 0 1/2 1
ZjCj 18 ¾ 0 9/4 0
9 X2 2 0 1 ½ 1/2
3 x1 0 1 0 1 2
ZjCj 18 0 0 3/2 3/2
La solución óptima es degenerada pues tiene una variable básica a nivel cero (x1). Si se
resuelve el problema gráficamente se observa que la restricción (1) es redundante.
Gráfico 4
Z 1
2
x2
x1
101
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.
Z1
Z2
x2
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.
102
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
Cj 2 1 0 0
CBi XBi P0 P1 P2 P3 P4
0 X3 10 1 1 1 0
0 X4 40 2 0 0 1
ZjCj 0 2 1 0 0
De acuerdo a la tabla anterior, al aplicar el criterio de entrada, el vector P2 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
103
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:
A
B
Cx1
x2
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.
104
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:
Cj 1 3 3 4 M
CBi XBi Po P1 P2 P3 P4 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
ZjCj Z0 = 1800 0 1 0 3 0
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.
105
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:
Cj 3 2 0 0 M
CBi XBi P0 P1 P2 P3 P4 P5
0 X3 2 2 1 1 0 0
M X5 12 3 4 0 1 1
ZjCj 12M 5M3 4M2 0 M 0
2 X1 1 1 1/2 1/2 0 0
M X5 9 0 5/2 1/2 1 1
ZjCj 9M +2 0 5/2M 1 1/2M+1 M 0
2 X2 2 2 1 1 0 0
M X5 4 5 0 3 1 1
ZjCj 4M +4 5M +1 0 3M+2 M 0
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.
106
Z1
2
x1
x2
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.
107
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 <= 150
3) 14 X + 10 Y <= 160
4) 18 X + 10 Y >= 135
5) X - 3 Y >= 0
6) X + Y >= 5
END
y la solución correspondiente mediante el comando GO aparecería en la siguiente
forma:
108
LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1) 58461.540 VARIABLE VALUE REDUCED COST X 9.230769 .000000
Y 3.076923 .000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 11.538460 .000000
3) .000000 365.384600
4) 61.923080 .000000
5) .000000 -115.384600
6) 7.307693 .000000 NO. ITERATIONS= 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.
109
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 <= 1
4 3) 0.001666 X1 + 0.0015384 X2 <= 1
5 4) X1 <= 400
6 5) X2 <= 450
7 6) 0.3 X1 + 1.3 X2 <= 650
8 7) 55 X1 + 21 X2 <= 24750
9 END
La solución obtenida a partir del programa aparecería en pantalla de la siguiente forma: LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 171937.90 VARIABLE VALUE REDUCED COST
X1 184.689700 .000000
X2 450.000000 .000000 ROW SLACK OR SURPLUS DUAL PRICES
2) .030771 .000000
3) .000000 120048.000000
4) 215.310300 .000000
5) .000000 115.310900
6) 7.746223 .000000
7) 5142.068000 .000000
110
NO. ITERATIONS= 2 Esta solución indica que se obtendrá un máximo de $ 171200.00 de ganancia si se
fabrican 184.7 TM de leche condensada y 450 TM de leche evaporada. Con esta
solución se tendrá un 3 % de capacidad ociosa en el departamento A, se utilizará el 100
% de la capacidad del Departamento B, se dejará de aprovechar capacidad suficiente
en el Departamento C para elaborar 215.3 TM de leche condensada y se aprovechará
toda la capacidad disponible en el departamento D. En cuanto a la disponibilidad de
materia prima (leche fresca) solo se dejarán de utilizar 7.75 TM. En este caso, la
dirección de la planta debería de analizar si deja de comprar esta cantidad de leche
fresca pues no sería necesaria. Lo mismo ocurre con los 5142 kilogramos de vitaminas
que no serán necesarios si se toma la decisión de fabricar leche condensada y
elaborada de acuerdo a la solución óptima encontrada en el problema.
Preguntas de comprobación:
1. ¿Cuál es la diferencia entre una solución, solución posible y solución óptima?
2. ¿Puede estar la solución óptima en cualquier parte del conjunto de soluciones
posibles?
1. ¿Cuál es la ventaja para el empresario, cuando llega a una solución alterna?
2. ¿En que se diferencia el criterio de salida de la base para un problema de
maximización y uno de minimización?
3. ¿Puede una variable artificial aparecer en la base cuando se ha llegado a la solución
óptima? ¿ A cuales soluciones especiales se habría llegado?
111
Ejercicios propuestos
1. Resuelva los siguientes problemas de PL por el método gráfico a) Min Z = 6x1 + 8x2 sujeto a
x1 – 2x2 0
6x1 + 8x2 48
x1 2
3x1 + 4x2 12
x1, x2 0 b) min Z = 4x1 + 2x2 sujeto a
4x1 + 4x2 20
-2x1 + 3x2 6
3x1 + 2x2 6
x1, x2 0
2. Dado el siguiente problema de Programación Lineal y la tabla que contiene la
solución óptima
Se le pide determinar el vector solución utilizando el método Simplex.
.
Max Z = 10x1 + 12x2 + 8x3 ingreso Sujeto a
3x1 + 2x3 15 TM de materia prima principal
x1 + 5x2 12 TM de combustible 2x1 + x3 = 9 Horas en el horno de secado
x1 0, x2 0, x3 0
Respuesta:
La tabla final del Simplex es la siguiente:
Cj 10 12 8 0 0 -M -M
Cj Xj P0 P1 P2 P3 P4 P5 P6 P7
8 X3 9 2 0 1 0 0 0 1
12 X2 12/5 1/5 1 0 0 1/5 0 0
0 X4 3 1 0 0 1 0 -1 2
Zj - Cj 92/5 0 0 0 12/5 M M+8
112
El vector solución es: X* = (x1*, x2*, x3*, x4*, x5*) = ( 0, 12/5, 9, 3, 0, 0) 3. Dado el siguiente problema de PL, se le pide:
a) Determine el vector solución del problema mediante el método Simplex.
b) Explique qué tipo de solución especial puede ser detectado en la tabla final
max Z = 30x1 + 10x2 + 48x3 + 12x4 Sujeto a
x1 + x2 + x3 + x4 90 Horas máquina disponibles
x2 1/2x4 70 Kgs. de combustible x1 + 2x3 = 60 Kgs. aditivo especial disponibles Respuesta:
La tabla final del simplex es:
Cj 30 10 48 12 0 0 - M
Cb Xb Po P1 P2 P3 P4 P5 P6 P7
12 x4 30 0 1 -1 1 1 0 -2
0 x6 70 0 ½ ½ 0 ½ 1 -3/4
30 x1 60 1 0 2 0 0 0 1
Zj – Cj 2160 0 2 0 0 12 0 M+6
Se deja el vector solución para que el alumno lo escriba.
113
V. PROGRAMACIÓN RETICULAR Objetivo:
Recomendaciones previas al inicio del estudio de este capítulo:
Es necesario que el lector esté familiarizado con el planteamiento del
problema de Programación Lineal.
Debe tener conocimientos sobre el manejo de alguno de los programas
utilizados para resolver el problema de PL.
Debe conocer el concepto de probabilidad.
En primer lugar sería necesario definir a que se denomina proyecto, ya que esta palabra
envuelve asuntos que van desde cuestiones personales hasta obras de gran
envergadura que requieren el concurso de miles de personas.
Las actividades que lo componen están interrelacionadas en una secuencia lógica en el
sentido que algunas de ellas no pueden comenzar hasta que otras se hayan terminado.
Una actividad en un proyecto, usualmente se ve como un trabajo que requiere tiempo y
recursos para su terminación.
Al término del estudio del capítulo, el estudiante conocerá las
particularidades fundamentales de los métodos PERT y CPM y las
herramientas que pueden usarse para planear, programar y controlar
proyectos grandes, pudiendo utilizarlas tanto para la elaboración de redes,
cálculo de la ruta crítica, determinación de holguras, etc. como para
disminuir los costos del proyecto o disminuir el tiempo de realización al
mínimo costo, teniendo en cuenta las posibilidades de utilización de la
computación.
En lo adelante se considerará que un proyecto define una
combinación de actividades interrelacionadas que deben ejecutarse
en un cierto orden antes que el trabajo completo pueda terminarse.
114
En general, un proyecto es un esfuerzo de un solo periodo; o sea, la misma sucesión de
actividades puede no repetirse en el futuro.
Cuando la realización de un proyecto envuelve un número limitado de acciones a
realizar, en muchas ocasiones basta para dirigir su realización con la experiencia del
dirigente del mismo, sin embargo, con el avance tecnológico contemporáneo han
surgido diversos métodos para dirigir de manera científica la realización de obras de
mediana y gran complejidad.
Décadas atrás, la programación de un proyecto (en el tiempo) se realizaba con poca
planeación. La mejor herramienta conocida de planeación entonces era el llamado
diagrama de barras de Gantt, el cual especifica los tiempos de inicio y terminación de
cada actividad en una escala de tiempo horizontal. Su desventaja es que la
interdependencia entre las diferentes actividades, no puede determinarse a partir del
diagrama de barras, siendo esta la función principal de control para el progreso del
proyecto. La creciente complejidad de los proyectos actuales ha demandado técnicas
de planeación más sistemáticas y efectivas con el objetivo de optimizar la eficiencia en
el proceso de su ejecución. La eficiencia en este caso implica efectuar la mayor
reducción en el tiempo requerido para terminar el proyecto mientras se toma en cuenta
la factibilidad económica de la utilización de los recursos disponibles.
En 1958, en los Estados Unidos de comenzó la realización del proyecto del cohete
Polaris. Este artefacto poseía una gran cantidad de componentes y partes que debían
producirse por diferentes empresas e irse ensamblando hasta finalizar con la
construcción del cohete. La complejidad de este proceso hizo necesario emplear un
método más adecuado que los existentes para controlar el desarrollo del proyecto y de
esta forma surgió el método denominado como PERT (ProgramEvaluation and
ReviewTechnique) o en español Evaluación de Programa y Técnica de Revisión. En lo
fundamenteal, este método fue desarrollado por Booz Allen, Hamilton y otros.
Por la misma época, un equipo de investigación de la transnacional de la química la
DuPont y de la división UNIVAC de la Remington Rand, desarrolló otra técnica
115
denominada como CPM (CriticalPathMethod) o Método del Camino Crítico. Este
método tenía como objetivo controlar el proceso de mantenimiento de plantas químicas
de la DuPont.
Estos dos métodos se popularizaron muy pronto y actualmente ambos están muy
difundidos, utilizándose por muchas empresas para controlar el desarrollo de obras de
diferente envergadura, desarrollo de proyectos de investigación, control de programas a
corto y mediano plazos, etc.
La diferencia esencial entre estos dos métodos radica, como se verá más adelante en
que el método CPM utiliza tiempos determinísticos para las actividades, mientras que
en el método PERT, los tiempos se consideran aleatorios y se calculan mediante una
distribución de probabilidad que utiliza los tiempos pesimista, optimista y más probable.
Esta diferencia ha provocado diferentes discusiones entre los seguidores de uno u otros
métodos.
En este capítulo se darán las particularidades fundamentales de ambos métodos y las
herramientas que pueden usarse para planear, programar y controlar proyectos
grandes.
La planeación de proyectos requiere desglosar el proyecto en actividades, estimar los
recursos y el tiempo para cada actividad y describir las interrelaciones de las
actividades.
La fase de planeación comienza con la descomposición del proyecto en las distintas
actividades que lo componen. Posteriormente se determinan las estimaciones de
tiempo para estas actividades y se elabora un diagrama de red (o de flechas) donde
cada uno de sus arcos (flechas) representa una actividad. El diagrama de flechas
completo da una representación gráfica de las interdependencias entre las actividades
del proyecto. La construcción del diagrama de flechas como una fase de planeación,
tiene la ventaja de estudiar los diferentes trabajos en detalle, permitiendo que surjan
posibles mejoras antes de que el proyecto se ejecute.
116
La programación requiere detallar las fechas de inicio y terminación para cada actividad.
El objetivo de la etapa de programación es construir un diagrama de tiempo que
muestre los tiempos de inicio y terminación de cada actividad y su relación con otras
actividades del proyecto. Además, el programa debe señalar las actividades críticas (en
función del tiempo) que demandarán atención especial de la dirección si el proyecto se
debe terminar en la fecha necesaria. Para las actividades no críticas el programa debe
mostrar los tiempos de holgura disponibles para su utilización cuando tales actividades
se demoran o cuando se deben usar eficientemente recursos limitados.
Esta es la fase final en la administración de proyectos. El control incluye el uso del
diagrama de flechas y la gráfica de tiempo para hacer reportes periódicos del progreso
del proyecto. La red puede, por consiguiente, actualizarse y analizarse y si es
necesario, determinar un nuevo programa para la porción restante del proyecto.
Por supuesto, una buena planeación minimiza el número de problemas que pueden
encontrarse más adelante, pero como la vida es mucho más rica que la imaginación
humana y sobre todo porque ninguna obra humana es perfecta, siempre existe la
posibilidad de que existan contratiempos.
Diferencias básicas entre el PERT y el CPM En un párrafo anterior se indicó que la diferencia fundamental entre estos dos métodos
radica en la manera en que se realizan los estimados de tiempo para las actividades. El
PERT supone que el tiempo para realizar cada una de las actividades es una variable
aleatoria descrita por una distribución de probabilidad, mientras que el CPM parte del
supuesto de que los tiempos de las actividades se conocen en forma determinística y se
pueden variar cambiando el nivel de los recursos utilizados.
El control del proyecto requiere disponer de información sobre el
estado actual del proyecto y analizar los posibles cambios cuando
surgen dificultades.
117
El método PERT supone que el tiempo de las actividades se distribuye de acuerdo a
una distribución Beta. La distribución para cualquier actividad se define por tres
estimados:
(a) estimado de tiempo más optimista
(b) estimado de tiempo más pesimista
(c) estimado de tiempo más probable. Esta distribución tiene la forma que aparece en el gráfico 1.
El tiempo más probable (m) es el tiempo requerido para realizar la actividad bajo
condiciones normales. Los tiempos optimistas (a) y pesimistas (b) proporcionan una
medida de la incertidumbre inherente a la actividad, incluyendo desperfectos en el
equipo, disponibilidad de mano de obra, retardo en la llegada de los materiales y otros
factores.
Gráfico 1. Distribución Beta
A partir de la distribución definida, la media (esperada) y la desviación estándar,
respectivamente del tiempo de la actividad Z pueden estimarse por medio de las
fórmulas de aproximación:
6
a-b(Z)
6
bm4aeT
El tiempo esperado de finalización de un proyecto es la suma de todos los tiempos
esperados de las actividades que componen la ruta crítica. De modo similar,
118
suponiendo que las distribuciones de los tiempos de las actividades son independientes
(lo cual es una suposición muy discutible), la varianza del proyecto es la suma de las
varianzas de las actividades en la ruta crítica.
En CPM solamente se requiere realizar un estimado de tiempo. Todos los cálculos se
hacen con la suposición de que los tiempos de las actividades se conocen. A medida
que el proyecto avanza, estos estimados se utilizan para controlar y monitorear su
progreso. Si ocurre algún retraso en el proyecto, es necesario realizar esfuerzos por
lograr que el proyecto vuelva de nuevo al programa, variando la asignación de recursos.
De lo anterior se deduce que en la práctica, el método CPM es cómodo de utilizar
cuando se desea controlar un proyecto en el cual se tiene experiencia anterior, y por lo
tanto, cuando los tiempos de duración de las actividades pueden pronosticarse con un
alto grado de aproximación. Por el contrario, el método PERT es más útil cuando se
trata de un proyecto que es acometido por primera vez, es decir, cuando existe un alto
grado de incertidumbre acerca de la duración de las actividades que lo componen.
Desarrollo de un proyecto mediante redes. Como se señaló anteriormente, el diagrama de flechas representa la interdependencia y
las relaciones de precedencia entre las actividades del proyecto.
Para desarrollar este apartado se comenzará mediante un ejemplo basado en un
proyecto de construcción.
Ejemplo 1
La empresa Golondrina S.A. se encuentra en un periodo de expansión y ha encargado
a una empresa constructora un edificio para su oficina regional.
Al comenzar las negociaciones para el contrato de la edificación, la empresa
constructora advierte que la contraparte será muy exigente en cuanto a los plazos de
entrega de la obra. Por ello, llega a la conclusión de que necesita en primer lugar
organizar los pasos del proyecto a fin de ver clara la precedencia entre las distintas
actividades a desarrollar en el proceso constructivo.
119
En primer lugar se elabora un listado contentivo de las diferentes actividades a
desarrollar, el cual de manera simplificada sería el siguiente:
Actividad Descripción Predecesor Duración
A Elaboración del proyecto constructivo
ninguno 3
B Preparación del terreno ninguno 2
C Cimentación A,B 3
D Levantar paredes y columnas C 3
E Fundir techos D 3
F Red de electricidad y plomería D 4
G Carpintería y cristalería D 2
H Pintura interior E,F 3
I Pintura exterior G 1
Para elaborar la red correspondiente a este proyecto, la dirección de la empresa
constructora tiene dos vías que se utilizan normalmente:
1. Considerar que las flechas (saetas) constituyen las actividades.
2. Considerar que las actividades están dadas por los nodos o vértices de la red. Con el primer método una flecha representa una actividad y la punta indica el sentido de
avance del proyecto. La relación de precedencia entre las actividades se especifica
utilizando eventos. Un evento representa un punto en el tiempo y significa la
terminación de algunas actividades y el comienzo de otras. Los puntos inicial y final de
una actividad, por consiguiente, están descritos por dos eventos usualmente conocidos
como evento de inicio o inicial yevento de terminación o terminal. Las actividades que
originan un cierto evento no pueden comenzar hasta que las actividades que concluyen
en el mismo evento hayan terminado. En la terminología de la teoría de las redes cada
actividad esta representada por un arco orientado y cada evento simbolizado por un
nodo o vértice. La longitud del arco no necesita ser proporcional a la duración de la
actividad ni tiene que dibujarse como una línea recta.
En la figura siguiente se muestran dos casos. La figura (a) muestra un ejemplo de
representación típica de una actividad (i,j) con su evento de inicio i y su evento de
terminación j. La figura (b) muestra otro ejemplo donde las actividades (1,3) y (2,3)
120
deben terminarse antes de que pueda comenzar la (3,4). La dirección del avance de
cada actividad se especifica asignando un número más pequeño al evento inicial que el
asignado al evento terminal. Esto facilita los cálculos por computadora y para
desarrollar una formulación de programación matemática para estos problemas.
i j
1
2
3 4
Gráfico (a) Gráfico (b) Gráfico 2 Se pueden considerar algunas reglas que sirvan de orientación en el proceso de
construcción de un diagrama de flechas. Estas pueden resumirse como sigue:
1. Cada actividad debe estar representada en la red por una y solo una flecha.
2. Dos actividades diferentes no pueden identificarse por los mismos eventos terminal y
de inicio.
3. Deben responderse las siguientes preguntas para asegurar una relación de
precedencia correcta en el diagrama de flechas en el momento de situar cada
actividad en la red;
a) ¿Cuáles actividades deben terminarse inmediatamente antes de que esta
actividad pueda comenzar?
b) ¿Cuáles actividades deben estar a continuación de esta actividad?
c) ¿Cuáles actividades deben y pueden efectuarse simultáneamente con esta
actividad?
La primera regla indica que ninguna actividad puede estar dos veces en una misma red.
Sin embargo, una actividad puede descomponerse en partes. Pero en este caso, cada
parte debe representarse como una actividad separada. Por ejemplo, al hacer la
instalación eléctrica de una obra, este trabajo puede descomponerse en partes y no
considerarse como una sola actividad.
121
La segunda se refiere al caso en que dos actividades deben ejecutarse en forma
simultánea. En ese caso no pueden identificarse como en el gráfico 4(c) sino como en
el gráfico 4(d) siguientes:
A
B
A
B
C
1
2
3
Gráfico (c) Gráfico (d)
Gráfico 4
Obsérvese que para evitar que las actividades A y B tengan los mismos eventos inicial y
terminal se ha introducido una nueva actividad C la cual se denomina como actividad
ficticia. Las actividades ficticias no consumen tiempo ni recursos, solo cumplen la
función de separar los eventos a fin de evitar confusiones.
La tercera regla es un medio útil para verificar las relaciones de precedencia cuando se
esta desarrollando
el proceso de construcción de la red. Si se considera que las actividades enunciadas en el listado están simbolizadas por
flechas, el gráfico del proyecto quedaría en la siguiente forma:
1
2
3
4 5
6
8
7
9
A
B
C
D
G
E
F
H
I
Gráfico 5: Representación por flechas Si se considera que las actividades están simbolizadas por los nodos o vértices de la
red, entonces el gráfico quedaría de la siguiente forma:
122
1
A
B
C D
G
E
F
H
I
N
Gráfico 6: Representación por nodos
Nótese que en la red planteada por nodos aparecen dos vértices (inicial y final) que
cumplen la función de poder organizar la red.
El utilizar uno u otro método para elaborar los gráficos depende del encargado del
proyecto, aunque los partidarios de la elaboración por nodos, plantean que la ventaja
fundamental es que en este método se eliminan las actividades ficticias.
Cálculo de la Ruta Crítica
Una vez desarrollada la red completa, se desea determinar la ruta crítica del proyecto.
La ruta crítica es aquella que limita el tiempo de terminación del mismo. Para el cálculo
de la ruta crítica se utiliza siguiente formulación:
Se parte de una red orientada. En el vértice inicial se supone que f(ti) = f(t1) = 0, es decir
se parte de que
el tiempo en el vértice inicial es cero. En realidad se puede partir de cualquier valor
arbitrario, pero para comodidad en los cálculos se toma el valor cero.
Para calcular la fecha más temprana de ocurrencia de cada uno de los eventos
siguientes se utiliza la fórmula
f(tj) = maxf(ti) + tij ; j 2:n ; ij X(1)
donde X es el subconjunto de los arcos que llegan al vértice j; f(ti) es la fecha de
ocurrencia más temprana del evento i y tijla duración de la actividad i,j. Esta fórmula
indica que se tomará como la fecha más temprana de ocurrencia del evento j, el
123
máximo de los tiempos resultantes de sumar las fechas de ocurrencia de cada uno de
los eventos iniciales de los arcos que llegan a j más sus correspondientes duraciones.
En el caso del ejemplo 1 los cálculos de los tiempos correspondientes son los siguientes: f(t1) = 0
f(t2) = f(t1) + t12 = 0 + 2 = 2
f (t3) = maxf(t1) + t13; f(t2)+ t23 = max (0 + 3), (2 + 0) = max (3,2) = 3 Obsérvese que la actividad (2,3) es una actividad ficticia por tanto su duración es cero. f(t4) = f(t3) + t34 = 3 + 3 = 6
f(t5) = f(t4) + t45= 6+3= 9
f(t6) = f(t5) + t56 = 9 + 2 = 11
f(t7) = f(t5) + t57 = 9 + 4 = 13
f(t8) = max f(t7)+ t78; f(t5) + t58 = max 13 + 0, 9 + 3 = max (13,12) = 13
f(t9) = max f(t6) + t69; f(t8) + t89 = max 11 + 1; 13 + 2 = max 12, 15 = 15
De acuerdo a lo anterior el tiempo de duración del proyecto es de 15 semanas y las
actividades que componen la ruta crítica o camino más largo, son aquellas que dan
lugar a esta duración total: A, C, D, F y H. Esto puede comprobarse en el gráfico 7 por
simple inspección.
1
2
3
4 5
6
8
7
9
A
B
C
D
G
E
F
H
I
3
2
3
3
2
3
4
2
1
Gráfico 7: Representación de la Ruta Crítica Sin embargo, en proyectos complejos es importante tener un procedimiento general que
además de permitir el cálculo de la ruta crítica proporcione un conjunto de
124
informaciones adicionales que juegan un rol fundamental en el control del proyecto y en
las tareas relacionadas con su posible optimización.
Para obtener estas informaciones adicionales se darán a continuación algunas
definiciones importantes.
Para el cálculo de las holguras libres y las totales, es conveniente establecer las
siguientes notaciones:
Ei y Ej Eventos i y j.
Las fechas más tardía de inicio y de terminación (f(ti*) y f(tj*)) se obtienen mediante la
siguiente fórmula:
f(ti*) = min f(tj*) tij ; i 2: n1; i,jεX+ (2)
donde X+ representa el subconjunto de los arcos que salen del vértice i. Las holguras libres se calculan mediante la fórmula
Holgura libre se denomina al retraso que puede sufrir el inicio de una
actividad sin peligro de atrasar la puesta en marcha de la actividad que viene
a continuación. Se denotará por HijL.
Holgura total se denomina al tiempo máximo que puede retrasarse una
actividad cualquiera sin afectar la duración total del proyecto. Se denotará
por HijT.
tiy tj fecha más temprana de inicio y más temprana de terminación de
la actividad (i,j).
ti* y tj* fecha más tardía de inicio y más tardía de terminación de la
actividad (i,j).
f(tn*) = f(tn) fecha correspondiente al final del proyecto.
125
HijL = f(tj) f(ti) tij(3)
Las holguras totales se calculan mediante la fórmula
HijT = f(tj*) f(ti) tij (4)
La disposición de las diferentes fechas en una actividad cualquiera se hará en la forma
que muestra el gráfico 8.
Gráfico 8 Una vez determinado f(tn) = f(t9) = 15, se procede calculando las fechas más tardías de
ocurrencia de los eventos utilizando la fórmula (2), a partir del último evento de la red.
Disponiendo en cada evento de las fechas más tempranas y de las más tardías de
ocurrencia de los mismos, y mediante las fórmulas (3) y (4) se procede al cálculo de las
holguras libres y totales, las cuales se colocan en los cuadros que aparecen debajo de
cada uno de los arcos correspondientes de la red.
A partir de las fórmulas dadas los valores de las holguras libres de cada una de las
actividades, son los
siguientes:
H69L = f(t9) f(t6) t69 = 15 11 1 = 3
H56L = f(t6) f(t5) t56 = 11 9 2 = 0
H57L = f(t7) f(t5) t57 = 13 9 4 = 0
H89L = f(t9) f(t8) t89 = 15 13 2 = 0
H58L = f(t8) f(t5) t58 = 13 9 3 = 1
y así sucesivamente. Nótese que la actividad (6,9) tiene una holgura de 3 semanas.
Esto quiere decir que el comienzo de esta actividad puede ocurrir en lugar de la
semana 11, en la 12, 13 o 14. Esto sin afectar para nada la terminación en fecha del
proyecto en su conjunto. También puede pensarse que la duración de la actividad
if(ti)f(tj) )t(f *
jj
LijH T
ijH)*
it(f
tijti tj
126
puede alargarse, de ser conveniente, durante 3 semanas más, con el mismo efecto en
la duración del proyecto.
De manera similar, la actividad (5, 8) puede retrasarse en su comienzo en una semana,
es decir, en lugar de la semana 9 podría comenzar en la semana 10 sin retrasar el
comienzo de la actividad que le sigue, la (8, 9). Si ocurriera un retraso mayor y la
actividad (8,9) es una actividad crítica (como efectivamente sucede) entonces se
retrasaría el proyecto en su conjunto. Si la actividad (8, 9) tuviera holgura libre,
entonces el retraso de la actividad (5, 8) por encima de 1 semana, consumiría la
holgura libre disponible por la (8, 9).
En cuanto a las holguras totales se tiene que
H69T= f(t9*) f(t6) t69 = 15 11 1= 3
H56T = f(t6*) f(t5) t59 = 14 9 2 = 3
H57T = f(t7*) f(t5) t57 = 13 9 4 = 0
H89T = f(t9*) f(t8) t89 = 15 14 1 = 0
H58T = f(t8) f(t5) t58 = 13 9 3 = 1
y así sucesivamente. De acuerdo a la definición de holgura total, el efecto que tiene en
las actividades un retraso en su comienzo o terminación superior a la holgura total
disponible, afectará no solo a la actividad que le sigue, sino también a toda la sucesión
de actividades hasta el evento final, retrasando así
la terminación del proyecto en su conjunto. Nótese que en las actividades críticas, tanto
la holgura libre como la holgura total son iguales a cero.
Como se observa, disponer de las holguras libres y totales de cada una de las
actividades que componen un proyecto, es de singular importancia para la dirección del
mismo. Es evidente que la dirección tendrá que mantener una vigilancia estricta sobre
el cumplimiento de todas las actividades que componen la ruta crítica si desea que el
proyecto termine en tiempo, asegurando las condiciones para que las mismas se
realicen en el tiempo que se estipuló al comienzo de la programación. En las demás
127
actividades tiene la posibilidad de admitir retrasos en la misma medida en que existan
holguras totales, siendo estas últimas las determinantes para el análisis.
Ahora bien, una vez en posesión de toda esta información es posible pasar a otras
etapas en el proyecto, relacionadas con la utilización de los recursos limitados, con el
posible ahorro que puede reportar alargar la duración de algunas actividades o resolver
el gran problema que representa acelerar la ejecución del proyecto cuando esto es
imprescindible por alguna razón.
Indicaciones sobre la construcción de la Red
La información disponible sobre el tiempo de duración de las actividades, la fecha de
ocurrencia de los eventos de inicio y terminación, las holguras libres y totales, debe
disponerse dentro de la red de manera que sea fácilmente visible. Por ello, se
recomienda construir la red de manera que en la misma figuren todos estos datos. Una
manera cómoda de hacer esto se da en el siguiente ejemplo:
Ejemplo 2
Dada la información contenida en la siguiente tabla, determinar las holguras libres y
totales y la ruta crítica.
1 2
( i, j ) tij
1,2 8
1,3 7
1,4 6
2,5 12
3,5 7
3,6 9
4,6 14
6,7 4
5,7 6
128
Gráfico 9
Solución:
Inicialmente es necesario construir una red similar a la que se elaboró en el primer
ejemplo, utilizando las precedencias dadas en la tabla y colocando en cada una de las
actividades los tiempos correspondientes. Esta red quedaría como se indica en el
gráfico 9.
Ahora bien, para efectuar el cálculo de la Ruta Crítica y las holguras, se construirá una
red ampliada, que tenga el formato necesario para que en ella figure toda la información
obtenida. Esta nueva red aparece en el gráfico 10. Esta nueva red tiene la siguiente
forma:
1
4
2
3
5
6
7
8
12
7
6
9 4
7
14
6
1
8
3
2
4
5
6
3
6
9
7
6
14
12
20
7
129
Gráfico 10
Realizando los cálculos, tal como se hizo en el ejemplo 1, la red ampliada conteniendo
toda la información sobre las holguras y la Ruta Crítica, aparecen el gráfico 11
Se deja al lector la realización de la red ampliada correspondiente al ejemplo 1.
Gráfico 11: Red completa con las holguras libres y totales
Utilización de la Programación Lineal para el cálculo de la Ruta Crítica
Las redes PERTCPM pueden ser modeladas fácilmente como problemas de PL. Esta
formulación proporciona una gran ayuda para comprender la estructura del proyecto y
las técnicas de modelación en si mismas. Desde un punto de vista práctico el
inconveniente que tiene este enfoque para proyectos grandes es el gran número de
restricciones y variables involucradas.
1
14
8
3
2
16
4
5
6
3
0
0
2
0
00
00
6
6
6
6
9
44
0
0
7
2
22
0
8
8
7 713
20
6
6
6
14
20
12
2020
26
20
24
26 26
20
88
6
2
0 0
8 8
13
2222
22
13
7
130
Si definimos TC(i) como el tiempo esperado en el cual se alcanza el vértice i, entonces
la función objetivo, que consiste en encontrar la ruta crítica de una red PERTCPM,
será
minimizar Z = TE(n) TE(0)
donde el vértice 0 es el comienzo del proyecto y el vértice n es la terminación del
proyecto. Esta expresión precisamente significa que deseamos minimizar el tiempo
necesario para ir del comienzo al final de la red.
Las restricciones se construyen a partir del hecho de que para cualquier actividad Tij,
que comienza en el vértice i y termina el j, el tiempo necesario para ir del vértice i al
vértice j es al menos el tiempo de la actividad Tij (en realidad, el tiempo necesario es el
tiempo de duración de la actividad más la holgura total). Por tanto, las restricciones
tendrán la forma
TE(j) TE(i) TE(Tij)
TE(j) TE(i) TE(Tij) + HijT
La formulación en la computadora por programación lineal del proyecto para la
construcción del edificio de oficinas de la Empresa Golondrina, sería como sigue:
1 MIN TE9 - TE1
SUBJECT TO
2) TE1 + TE3 3
3) TE1 + TE2 2
4) TE3 TE2 0
5) TE3 + TE4 3
6) TE4 + TE5 3
7) TE5 + TE8 3
8) TE5 + TE7 4
9) TE5 + TE6 2
10) TE9 TE8 2
131
11) TE8 TE7 0
12) TE9 TE6 1
13) TE1 = 0
END La solución encontrada utilizando el programa Lindo es la siguiente: LP OPTIMUM FOUND AT STEP 9
OBJECTIVE FUNCTION VALUE
1) 15.000000 = Z0
VARIABLE VALUE REDUCED COST
TE9 15.000000 0.000000
TE1 0.000000 0.000000
TE3 3.000000 0.000000
TE2 3.000000 0.000000
TE4 6.000000 0.000000
TE5 9.000000 0.000000
TE8 13.000000 0.000000
TE7 13.000000 0.000000
TE6 14.000000 0.000000
ROW SLACK OR
SURPLUS
DUAL PRICES
2) 0.000000 -1.000000
3) 1.000000 0.000000
4) 0.000000 0.000000
5) 0.000000 -1.000000
6) 0.000000 -1.000000
7) 1.000000 0.000000
8) 0.000000 -1.000000
9) 3.000000 0.000000
10) 0.000000 -1.000000
132
11) 0.000000 -1.000000
12) 0.000000 0.000000
13) 0.000000 0.000000
NO. ITERATIONS = 9 La ruta crítica puede encontrarse a través de aquellas restricciones que no tienen
holgura; estas corresponderán a las actividades de la ruta crítica. También las variables
duales que no son cero, especificarán las restricciones que denotan las actividades de
la ruta crítica.
En el ejemplo resuelto mediante PL, nótese que la duración total del proyecto coincide
con la anteriormente calculada de forma manual.
Para encontrar la ruta crítica, se necesita encontrar aquellas restricciones que no
tengan variable de holgura positiva, es decir, que sean igualdades estrictas en la
solución. Por el teorema complementario de holgura de la PL, aquellas ecuaciones
cuyas variables duales correspondientes no sean iguales a cero, deben ser igualdades
estrictas; por tanto, las variables de holgura son iguales a cero.
Pendiente de costo Un instrumento utilizado para analizar los posibles cambios en los costos cuando existe
una variación en
los tiempos de ejecución de las actividades que componen un proyecto, es la
denominada pendiente de costos, la cual se denota por ijC .
Este concepto está estrechamente relacionado con el hecho comprobado de que el
acelerar la terminación de una actividad requiere de una cantidad de fuerza de trabajo
y equipo adicional al normalmente utilizado.
Para calcular la pendiente de costo se parte de la estimación de cuatro elementos. En
primer lugar será necesario estimar el tiempo de más larga duración (dentro de los
limites razonables) y el costo de la actividad para este tiempo. Se estima también el
133
tiempo mínimo (tiempo colisionado) en que puede ser realizada la actividad y el costo
asociado de la misma.
Partiendo de estos datos se podrá calcular
ijd ijD
CC
mínimaDuración -máxima Duración
ocolisionad Costo-máximo CostoijC minmax
Si por ejemplo, se tiene que el tiempo máximo de ejecución de una actividad dada, es
de 40 días y con esta duración el costo de la actividad es de $ 2500 y por otro lado, si
la ejecución de la actividad se acelera, puede llegarse a una duración mínima de 20
días con un costo de $ 3500, entonces la pendiente de costo correspondiente a esta
actividad será de
50$20
1000
2040
25003500ijC
De lo anterior se concluye que
Es decir, si el tiempo de duración de una actividad aumenta en una unidad, su costo de
ejecución
disminuirá en el valor que tiene la pendiente de costo y viceversa. A la pendiente de
costo también se le denomina como costo de colisión y a la red del proyecto elaborada
con los tiempos acelerados, se le denomina como red colisionada.
Disminución de costos utilizando las holguras libres Disponer de las pendientes de costo de las actividades que componen el proyecto
permite realizar ahorros que a veces pueden ser substanciales aprovechando la
posibilidad de disminuir el ritmo de terminación de las actividades que tienen holgura
libre. Como se sabe, cuando una actividad que tiene holgura libre se retrasa, es decir,
se planifica para que dure el tiempo normal más la holgura libre o una parte de ella, esto
La pendiente de costo es el cambio que sufren los costos de una actividad
cuando el tiempo de ejecución varía inversamente en una unidad de tiempo.
134
significa que se le podrán destinar menos recursos laborales y de equipo, y por ende
costará menos su realización.
El cálculo del tiempo que en puede ser alargada la duración de una actividad, se realiza
mediante la fórmula:
LijH;ijtijD[min ijt
donde ijt representa el incremento posible de la actividad (i, j), es decir, que el tiempo
que podrá aumentarse a la duración normal de una actividad será igual al mínimo entre
la duración máxima posible menos la duración normal y el tiempo de holgura libre
disponible.
Ejemplo 3 Supongamos que se tiene la red correspondiente a un proyecto determinada en el
ejemplo 2. En ella se han calculado las holguras de todas las actividades así como la
ruta crítica del mismo. Además se tiene la información dada en la tabla , la cual
contiene la duración máxima permisible de las actividades, los costos de todas las
actividades y las pendientes de costo. La información disponible inicial es la
comprendida en las columnas de la 1 a la 5.
Utilizando la fórmula dada para calcular los incrementos posibles de cada una de las
actividades y los datos que aparecen en la tabla se calculan los datos que aparecen en
la columna 7. Posteriormente se multiplican estos resultados por las correspondientes
pendientes de costo y se obtiene la columna 8. Por tanto, en la columna 7 están los
tiempos que es posible alargar en las actividades que poseen holgura libre y en la
columna 8, el incremento en el tiempo multiplicado por la pendiente de costo. En el
ejemplo, como resultado de esta operación se obtiene un ahorro total de $ 290, que
representa un 10.58 % del valor total del proyecto, lo cual en muchos casos no es un
porcentaje de ahorro desdeñable.
135
1 2 3 4 5 6 7 8
(i,j) Dij tij HijL Cij ijC ijt )C(t ijij
1,2 10 8 0 450 0 0 0
1,3 8 7 0 320 80 0 0
1,4 6 6 0 300 20 0 0
2,5 14 12 0 240 35 0 0
3,5 10 7 6 400 40 3 120
3,6 12 9 4 250 40 3 120
4,6 15 14 0 300 15 0 0
6,7 8 4 2 280 2 2 50
5,7 7 6 0 200 20 0 0
$ 2740 $ 290
Compresión de tiempos o Colisión
En algunas ocasiones después de haber realizado la planeación y programación
completa del proyecto y aún incluso después de haber iniciado su ejecución, pueden
surgir razones para finalizar un proyecto antes de lo planeado. Esto puede significar
que se tenga que contratar personal adicional, que se deba trabajar en tiempo extra o
comprar más equipo para ayudar a los trabajadores a terminar más pronto. Al proceso
de reducir el tiempo de terminación del proyecto por estos medios se denomina
compresión de tiemposo colisión.
Ejemplo 3 La tabla siguiente muestra un proyecto con tiempos de actividad normales y los costos
de aceleración o costos de colisión.
La red correspondiente a este proyecto se da en el gráfico 12. Obsérvese que adjunto a
la letra que denota la actividad se da la pendiente de costo de la misma y junto al
tiempo de duración normal se dan los tiempos acelerados.
136
Tiempos normales, tiempos de actividad y costos colisionados correspondientes al proyecto
Actividad
Predecesores
tij (tiempo normal)
Tiempo colisionado en semanas ( dij)
Costos de colisión
por semana ( ijC )
A ninguno 14 6 100
B ninguno 12 8 200
C B 4 2 100
D A 6 4 200
E A 18 14 200
F C,D 8 6 100
G E,F 12 8 100
Gráfico 12
Para aplicar el método de disminución de tiempos, resulta conveniente construir la red
ampliada explicada arriba. En el caso particular de ejemplo dado, podría resolverse por
simple inspección, sin embargo, cuando la red tiene más actividades y vértices, el
método de la simple inspección no es adecuado. Por ello, a continuación se brinda la
red que aparece en el gráfico 13, que tiene las características mencionadas y en la cual
se brindan los datos que aparecen en la red del gráfico 12.
1
2
3 4
5 6
A($100)
14 (6
)
E ($200)18 (14)D( $200)B($200)12(8) C($100)
4(2)
F($100)
8(6)
G(100)
12(8)
137
Gráfico 13
Si se aplica el método de cálculo de la Ruta crítica dado en páginas anteriores, se
obtiene que estará formada por el camino AEG. De esta forma se llega al gráfico 14
donde aparecen determinadas las holguras libres y totales. Recuerde que el camino
desde el vértice 1 al vértice 6, con holguras libres iguales a cero, es el que determina la
RC.
Gráfico 14
1
2
3
0 05 6
A ($
100)
14
(6)
E ($200)18 (14)
G ($100)
12 (8)
B ($200)
12 (8)
C ($100)
4(2)
F ($
100)
8 (6
)
D ($
200)
6(4
)
14
14
32
20
12
12
16 420
28
4432 44 443232
14
00
000
0
0
24
24
18
14
2020
0
4
4 8
44
08
1
2
3
5 6
A ($
100)
14
(6)
E ($200)18 (14)
G ($100)
12 (8)
B ($200)
12 (8)
C ($100)
4(2)
F ($
100)
8 (6
)D
($200)
6(4
)
4
138
La duración del proyecto en tiempo normal es de 44 semanas y se le supone un costo
de $ 6400. Si se consideran los tiempos de colisión la duración total del proyecto es de
28 semanas con un costo de $ 10 000.
Esta información resumida se da en la siguiente tabla:
Ruta crítica Tiempo del proyecto
Costo del proyecto
Tiempos normales
AEG 44 semanas $ 6 400
Tiempos en colisión
AEG 28 semanas $ 10 000
Si todos los tiempos de duración de las actividades se aceleran, es decir, si se
consideran todos los tiempos colisionados la ruta crítica puede variar o pueden surgir
nuevas rutas críticas además de la original, ya que si una actividad no crítica se acelera
más allá de su holgura total, se convierte en crítica.
El análisis de las posibilidades de colisionar actividades, teniendo en cuenta la relación
tiempo-costo, permite al que dirige un proyecto saber cual sería el programa de menor
costo cuando se requiere reducir el tiempo total del proyecto por debajo del que marca
la ruta crítica, en el ejemplo, si se quisiera reducir la duración del proyecto por debajo
de las 44 semanas. Es obvio que la reducción tendrá que ocurrir en las actividades que
componen la ruta crítica ya que ellas son las que determinan la duración total. Si se
quiere que la disminución del tiempo del proyecto ocurra al menor costo posible,
también es obvio que deberán elegirse para disminuir el tiempo, aquellas que tengan
la menor pendiente de costo o costo de colisión.
Utilizando este criterio se observa que en el proyecto de la red del gráfico 12, las
actividades A y G tienen la misma pendiente de costo. En caso de empate, el criterio
será disminuir en la que permita una mayor disminución del costo total. En este caso, se
elegirá la actividad A.
La actividad A se puede disminuir de 14 a 6 semanas si se colisiona completamente. El
costo por semana es de $ 100, luego una disminución de 8 semanas implica un
139
aumento del costo de la actividad de $ 800. Ahora la ruta crítica ha disminuido de 44 a
36 semanas. Nótese entonces que ahora se tiene una ruta crítica adicional compuesta
por las actividades BCFG con una duración de 36 semanas igual.
Gráfico 15 En estas condiciones, se podría disminuir el tiempo, colisionando la actividad G
llevándola hasta 8 semanas, esto representa una disminución de 4 semanas y un
aumento en el costo del proyecto de $400 (4 semanas a $ 100/semana). La duración
total del proyecto ha disminuido ahora a 32 semanas. El costo total del proyecto será
1
2
3
0 05 6
A
6
E ($200)18 (14)
G ($100)
12 (8)
B ($200)
12 (8)
C ($100)
4(2)
F ($
100)
8 (6
)
D ($
200)
6(4
)
6
6
24
12
12
12
16 416
24
3624 36 362424
6
00
000
0
0
16
16
10
6
1212
0
4
0 0
00
00
0
1
2
3
0 05 6
A
6
E ($200)18 (14)
G
8
B ($200)
12 (8)
C ($100)
4(2)
F ($
100)
8 (6
)D
($200)
6(4
)
6
6
24
12
12
12
16 416
24
3224 32 322424
6
00
000
0
0
16
16
10
6
1212
0
4
0 0
00
00
0
140
ahora de $ 7 600.
Gráfico 16 Si se quiere disminuir por debajo de las 32 semanas, entonces se tendrán que
considerar las actividades situadas en las dos rutas críticas conjuntamente, pues
obviamente si se disminuye en una sola de ellas, la
duración del proyecto no disminuirá. La actividad F puede disminuir en dos semanas con un costo de colisión total de $ 200
(2 $100). En la otra ruta a considerar queda con posibilidades de disminución la
actividad E. Disminuyendo dos semanas en ella, el costo será de $ 400 (2$200). El
incremento total en el costo por disminuir estas dos semanas será de $ 600 (costo de
disminución en E más costo de disminución en F). El costo total ahora será de $ 8 200.
1
2
3
0 05 6
A
6
E ($200)16 (14)
G
8
B ($200)
12 (8)
C ($100)
4(2)
F
6
D ($
200)
6(4
)
6
6
22
12
12
12
16 416
22
3022 30 302422
6
00
000
0
0
16
16
10
6
1212
4
4
0 0
0
00
0
0
141
La red quedará como aparece en el gráfico 17.
Gráfico 17
Gráfico 18 En esta situación, si se quiere seguir disminuyendo el tiempo total de duración del
proyecto, se tendrá que disminuir en la actividad E (que aún admite una disminución de
dos semanas) y simultáneamente en alguna de las dos actividades ( Bó C) de la otra
ruta. Lógicamente se elegirá la actividad C por tener la menor pendiente de costo. Así
disminuyendo E en dos semanas y C en dos semanas el aumento en el costo total del
proyecto será de $ 600 ($ 400 por la disminución en E más $ 200 por la disminución en
C). El costo total del proyecto ascenderá ahora a $ 8 800. La red del proyecto quedará
como aparece en el gráfico 18:
Resumiendo, la duración total del proyecto es ahora de 28 semanas con un costo total
de $ 8 800. El costo total alcanzado utilizando el criterio de disminuir el tiempo en las
actividades que tienen la pendiente de costo más pequeña, es $ 1 200 menos que el
costo que se hubiera alcanzado si se hubieran disminuido todas las actividades del
proyecto de manera simultánea a su tiempo mínimo.
1
2
3
0 05 6
A
6
E 14
G
8
B ($200)
12 (8)
C
2
F
6
D ($
200)
6(4
)
6
6
20
12
12
12
14 414
20
2820 28 282420
6
00
000
0
0
14
14
10
6
1212
2
2
0 0
0
00
0
0
142
28 30 32 34 36 38 40 42 446000
7000
8000
9000
Gráfico 16 (19) El gráfico anterior muestra el comportamiento del costo a medida que se disminuyen los
tiempos de ejecución del proyecto, desde el costo mínimo alcanzado para tiempos de
ejecución normales, hasta el tiempo de ejecución mínimo encontrado mediante la
aceleración de las actividades que componen la ruta crítica.
Aplicación de la PL a la compresión de tiempos o colisión
Además del procedimiento utilizado arriba para la determinación de las actividades que
deben ser comprimidas y en cuanto pueden serlo cuando se tiene que realizar la
disminución del tiempo programado para la ejecución de un proyecto, es posible utilizar
el método de la PL.
Para formular el problema de compresión de tiempo o colisión, mediante la PL se utiliza
la siguiente notación:
T(M): tiempo estimado de duración normal de la actividad M
T’(M): tiempo de duración estimada de la actividad M totalmente acelerada (duración
mínima)
K(M): pendiente de costos de la actividad M
T(i): tiempo estimado para alcanzar el vértice i
C(M): cantidad de tiempo de colisión (aceleración) utilizado en la actividad M
D: fecha límite para completar el proyecto.
A partir de estas notaciones el planteamiento general del problema del cálculo de la
colisión será:
143
min Z = K(M)C(M) costo total de la aceleración
sujeto a 1. Cumplimiento de la fecha límite de terminación del proyecto
T(n) T(0) D 2. Cumplimiento del tiempo de duración de la actividad menos el que descuente por aceleración
T(j) T(i) T(M) C(M) 3. Limitación en la disminución del tiempo de cada actividad
C(M) T(M) T’(M) Como T(M), T’(M), K(M) y D son conocidos, las variables serían solamente T(i) y C(M). Ejemplo 4
Supongamos el siguiente proyecto cuyos datos se dan a continuación:
Actividad
Duración Máxima (Dij)
Duración normal (tij)
Duración acelerada
(dij)
Pendiente de
costos
A 1,2 6 4 3 3.3
C 1,3 8 5 5 1.33
D 1,4 6 3 2 1.00
B 1,5 6 3 2 0.50
E 2,5 8 2 2 1.33
F 3,5 8 6 5 1.33
G 4,5 10 6 2 1.00
H 3,6 11 9 7 0.75
J 4,6 8 6 6 1.00
I 5,7 6 4 2 0.50
K 6,7 8 4 2 0.33
L 7,8 10 8 6 1.25
La red inicial para este proyecto sería la del gráfico 20.
144
Gráfico 20 El planteamiento del problema para comprimir los tiempos y llevar la duración del
proyecto desde 26 semanas a 20, sería como sigue:
MIN 3.3 CA + 1.33 CC + CD + 0.5 CB + 1.33 CE + 1.33 CF + CG
+ 0.75 CH + CJ + 0.5 CI + 0.33 CK + 1.25 CL
SUBJECT TO
1) T8 20
2) CA + T2 T1 4
3) CC T1 + T3 5
4) CD T1 + T4 3
5) CB T1 + T5 3
6) CE T2 + T5 2
7) CF T3 + T5 6
8) CG T4 + T5 6
9) CH T3 + T6 9
10) CJ T4 + T6 6
11) CI T5 + T7 4
12) CK T6 + T7 4
13) CL + T8 T7 8
14) CA 1
1
2
3
4
5
6
7
8
4
2
4
3
56
6
9
3
6
4
826
145
15) CC 0
16) CD 1
17) CB 1
18) CE 0
19) CF 1
20) CG 4
21) CH 2
22) CJ 0
23) CI 2
24) CK 2
25) CL 2
26) T1 = 0
END
Una vez planteado el problema, si se utiliza el programa LINDO se tendría la siguiente
solución:
LP OPTIMUM FOUND AT STEP 21
OBJECTIVE FUNCTION VALUE
1) 5.1600000
VARIABLE VALUE REDUCED
COST
CA 0.00000 3.300000
CC 0.00000 0.080000
CD 0.00000 1.000000
CB 0.00000 0.500000
CF 0.00000 0.830000
CG 0.00000 1.000000
CH 2.00000 0.000000
CJ 0.00000 1.000000
146
CI 1.00000 0.000000
CK 2.00000 0.000000
CL 2.00000 0.000000
T8 20.0000 0.000000
T2 9.00000 0.000000
T1 0.00000 1.250000
T3 5.00000 0.000000
T4 5.00000 0.000000
T5 11.0000 0.000000
T6 12.0000 0.000000
T7 14.0000 0.000000
T1 0.00000 0.000000
En este caso, la función objetivo proporciona la cantidad en que se incrementa el costo
total al comprimir el tiempo de duración del proyecto. Al mismo tiempo obsérvese que
los valores de las variables proporcionan también en cuales actividades se realizará la
compresión y cuanto tiempo será el que se disminuirá cada una de ellas. Recuérdese
que este procedimiento se aplicaría después de haber programado el proyecto en
tiempo normal, teniendo su ruta crítica y su costo total ya calculado. Esto es importante,
pues es a partir de esas condiciones que se procede a comprimir el tiempo y esto
permite conocer luego cuales actividades que no eran criticas, pasan a serlo luego de la
compresión de tiempo y si han surgido nuevas rutas críticas en el proyecto.
Teóricamente es posible que todas las actividades del proyecto se vuelvan críticas al
comprimir el proyecto a su mínima duración posible.
La red correspondiente al proyecto colisionado utilizando las pendientes de costo sería
la siguiente:
147
Gráfico 21
Nótese que en la red, además de la ruta crítica (1,3)(3,6)(6,7)(7,9), se tiene ahora
otra ruta por (1,3) (3,5)(5,7)(7,8) que también es crítica, surgida al consumirse las
holguras totales de algunas actividades no críticas.
Ejercicios propuestos
1. Explique: a) ¿Para cual tipo de proyecto es más apropiado utilizar el PERT y para cual el CPM?
b) Explique porqué si se tienen dos rutas críticas y se disminuye el tiempo de duración
de una de ellas, es imprescindible disminuir también el tiempo de duración de una
actividad de la otra, para que el tiempo de duración de proyecto disminuya también.
2.Construya la red del ejemplo 2 tomando los nodos como actividades.
3. Dada la siguiente red y los datos correspondientes a la duración máxima de las
actividades, la duración mínima, las pendientes de costo y los costos totales, se le
pide:
a) Elabore la red ampliada y calcule las holguras libres y totales.
b) Determine la Ruta crítica.
c) Determine en que porcentaje puede ser disminuido el costo total del proyecto,
utilizando las holguras libres existentes.
d) Disminuya el proyecto en cuatro unidades de tiempo.
1
2
3
4
5
6
7
8
4
2
3
3
56
6
7
3
6
2
62014
148
e) Disminuya la duración del proyecto hasta el mínimo posible, teniendo en cuenta
los tiempos de duración de las actividades que componen la o las Rutas Críticas
existentes.
(ij) Dij dij Cij ijC
(1,2) 10 6 400 2
(1,3) 14 8 500 1.5
(1,4) 17 10 750 10
(2,5) 15 9 425 8
(3,5) 16 14 355 5
(3,7) 8 3 845 12
(3,6) 13 7 250 10
(4,6) 8 4 300 8
(5,7) 7 3 425 2
(6,7) 11 5 800 12
8
1
2
3
4
5
6
7
12
4
10
15
5
10 812
6
149
VI: BIBLIOGRAFÍA
1. Camacho, A.(2009): Principios de Investigación de Operaciones para contaduría y
administración. Madrid. España. Editorial ECFSA.
2.Eppen, G.D; Gould, F. J.: “Investigación de operaciones en la ciencia administrativa”,
Prentice-Hall Hispanoamericana, S.A, México, 2003.
3.Gallagher, W. (2002): Métodos Cuantitativos para la toma de decisiones. México.
Editorial McGraw Hill.
4 Hiller, F,S; Lieberman, G.J. (2010): Introducción a la Investigación de Operaciones. México.
Editorial McGraw Hill. 9na. Edición
5 Kamlesh, M,;Solow D. (2008): Investigación de Operaciones. El arte de la toma de decisiones.
España. Editorial Prentice Hall
6 Mkeow,D (2012): Métodos Cuantitativos para la Administración. México. Grupo editorial
Iberoamericana
7. Moskowitz, Herbert; Wright, Gordon: “Investigación de operaciones”, Prentice-Hall
Hispanoamericana, México, 1992.
8. Roscoe, Davis; Mckeown, Patric. Modelos Cuantitativos para la Administración
. University of Georgia, Grupo Editora Iberoamericano, 1999.