i.s.c. - 4to sem - investigacion de operaciones
TRANSCRIPT
UNIDAD 1: PROGRAMACION LINEAL.
DEFINICION, DESARROLLO Y TIPOS DE MODELOS DE INVESTIGACION DE OPERACIONES
Historia de la Investigación de Operaciones.
La primera actividad de Investigación de Operaciones se dio durante la
Segunda Guerra Mundial en Gran Bretaña, donde la Administración Militar llamó a
un grupo de científicos de distintas áreas del saber para que estudiaran los
problemas tácticos y estratégicos asociados a la defensa del país.
El nombre de Investigación de Operaciones fue dado aparentemente
porque el equipo estaba llevando a cabo la actividad de investigar operaciones
(militares).
Motivados por los resultados alentadores obtenidos por los equipos
británicos, los administradores militares de Estados Unidos comenzaron a realizar
investigaciones similares. Para eso reunieron a un grupo selecto de especialistas,
los cuales empezaron a tener buenos resultados y en sus estudios incluyeron
problemas logísticos complejos, la planeación de minas en el mar y la utilización
efectiva del equipo electrónico.
Al término de la guerra y atraídos por los buenos resultados obtenidos por
los estrategas militares, los administradores industriales empezaron a aplicar las
herramientas de la Investigación de Operaciones a la resolución de sus problemas
que empezaron a originarse debido al crecimiento del tamaño y la complejidad de
las industrias.
Aunque se ha acreditado a Gran Bretaña la iniciación de la Investigación
de Operaciones como una nueva disciplina, los Estados Unidos tomaron pronto el
liderazgo en este campo rápidamente creciente. La primera técnica matemática
ampliamente aceptada en el medio de Investigación de Operaciones fue el Método
Símplex de Programación Lineal, desarrollado en 1947 por el matemático
norteamericano George B. Dantzig. Desde entonces las nuevas técnicas se han
desarrollado gracias al esfuerzo y cooperación de las personas interesadas tanto
en el área académica como en el área industrial.
Un segundo factor en el progreso impresionante de la Investigación de
Operaciones fue el desarrollo de la computadora digital, que con sus tremendas
capacidades de velocidad de cómputo y de almacenamiento y recuperación de
información, permitieron al tomador de decisiones rapidez y precisión.
Si no hubiera sido por la computadora digital, la Investigación de
Operaciones con sus grandes problemas de computación no hubiera crecido al
nivel de hoy en día.
Actualmente la Investigación de Operaciones se está aplicando en muchas
actividades. Estas actividades han ido más allá de las aplicaciones militares e
industriales, para incluir hospitales, instituciones financieras, bibliotecas,
planeación urbana, sistemas de transporte y sistemas de comercialización.
Características de la Investigación de Operaciones.
Es muy notable el rápido crecimiento del tamaño y la complejidad de las
organizaciones (empresas) humanas que se ha dado en estos últimos tiempos.
Tal tamaño y complejidad nos hace pensar que una sola decisión equivocada
puede repercutir grandemente en los intereses y objetivos de la organización y en
ocasiones pueden pasar años para rectificar tal error. También el ritmo de la
empresa de hoy implica que las DECISIONES se tomen más rápidamente que
nunca, pues el hecho de posponer la acción puede dar una decisiva ventaja al
contrario en este mundo de la competencia.
La palpable dificultad de tomar decisiones ha hecho que el hombre se
aboque en la búsqueda de una herramienta o método que le permita tomar las
mejores decisiones de acuerdo a los recursos disponibles y a los objetivos que
persigue. Tal herramienta recibió el nombre de Investigación de Operaciones.
De la definición de Investigación de Operaciones, como veremos en el
siguiente apartado, podemos resaltar los siguientes términos: organización,
sistema, grupos interdisciplinarios, objetivo y metodología científica.
Una organización puede entenderse como un sistema, en el cual existen
componentes; canales que comunican tales componentes e información que fluye
por dichos canales. En todo sistema las componentes interactúan unas con otras y
tales interacciones pueden ser controlables e incontrolables. En un sistema
grande, las componentes se relacionan de muchas maneras, pero no todas son
importantes, o mejor dicho, no todas las interacciones tienen efectos importantes
en las componentes del sistema.
Por lo tanto es necesario que exista un procedimiento sistemático que
identifique a quienes toman decisiones y a las interacciones que tengan
importancia para los objetivos de la organización o sistema. Uno de esos
procedimientos es precisamente la Investigación de Operaciones.
Una estructura por la que no fluye información, no es dinámica, es decir,
no podemos considerarla como un sistema. Por lo tanto podemos decir que la
información es lo que da “vida” a las estructuras u organizaciones humanas.
Los objetivos de toda organización serán siempre alcanzar el liderato en su
rama, controlando la eficiencia y efectividad de todas sus componentes por medio
de métodos que permitan encontrar las relaciones óptimas que mejor operen el
sistema, dado un objetivo específico.
Ante el tremendo avance que se ha dado en casi todas las ciencias en las
últimas décadas, ya no es factible querer saber un poco de todo, sino más bien
especializarse en alguna rama de la ciencia. Los problemas que se presentan en
las organizaciones no fácilmente se pueden resolver por un sólo especialista. Por
el contrario son problemas multidisciplinarios, cuyo análisis y solución requieren de
la participación de varios especialistas. Estos grupos interdisciplinarios
necesariamente requieren de un lenguaje común para poder entenderse y
comunicarse, donde la Investigación de Operaciones viene a ser ese puente de
comunicación.
El enfoque de la Investigación de Operaciones es el mismo del método
científico. En particular, el proceso comienza por la observación cuidadosa y la
formulación del problema y sigue con la construcción de un modelo científico (por
lo general matemático) que intenta abstraer la esencia del problema real. En este
punto se propone la hipótesis de que el modelo es una representación lo
suficientemente precisa de las características esenciales de la situación como
para que las conclusiones (soluciones) obtenidas sean válidas también para el
problema real. Esta hipótesis se verifica y modifica mediante las pruebas
adecuadas. Entonces, en cierto modo, la Investigación de Operaciones incluye la
investigación científica creativa de las propiedades fundamentales de las
operaciones. Sin embargo, existe más que esto. En particular, la Investigación de
Operaciones se ocupa también de la administración práctica de la organización.
Así, para tener éxito, deberá también proporcionar conclusiones positivas y claras
que pueda usar el tomador de decisiones cuando las necesite.
La contribución del enfoque de Investigación de Operaciones proviene
principalmente de:
1. La estructuración de una situación de la vida real como un modelo matemático,
logrando una abstracción de los elementos esenciales para que pueda buscarse
una solución que concuerde con los objetivos del tomador de decisiones. Esto
implica tomar en cuenta el problema dentro del contexto del sistema completo.
2. El análisis de la estructura de tales soluciones y el desarrollo de procedimientos
sistemáticos para obtenerlas.
3. El desarrollo de una solución, incluyendo la teoría matemática si es necesario,
que lleva al valor óptimo de la medida de lo que se espera del sistema (o quizá
que compare los cursos de acción opcionales evaluando esta medida para cada
uno).
Definición.
Investigación de Operaciones o Investigación Operacional. Se puede
definir de la siguiente manera: “La Investigación de Operaciones es la aplicación
por grupos interdisciplinarios del método científico a problemas relacionados con
el control de las organizaciones o sistemas a fin de que se produzcan soluciones
que mejor sirvan a los objetivos de toda la organización”.
Metodología de la Investigación de Operaciones.
El proceso de la Investigación de Operaciones comprende las siguientes
fases:
1. Formulación y definición del problema.
2. Construcción del modelo.
3. Solución del modelo.
4. Validación del modelo.
5. Implementación de resultados.
Demos una explicación de cada una de las fases:
1. Formulación y definición del problema. En esta fase del proceso se
necesita: una descripción de los objetivos del sistema, es decir, qué se desea
optimizar; identificar las variables implicadas, ya sean controlables o no;
determinar las restricciones del sistema. También hay que tener en cuenta
las alternativas posibles de decisión y las restricciones para producir una
solución adecuada.
2. Construcción del modelo. En esta fase, el investigador de operaciones
debe decidir el modelo a utilizar para representar el sistema. Debe ser un
modelo tal que relacione a las variables de decisión con los parámetros y
restricciones del sistema. Los parámetros (o cantidades conocidas) se
pueden obtener ya sea a partir de datos pasados o ser estimados por medio
de algún método estadístico. Es recomendable determinar si el modelo es
probabilístico o determinístico. El modelo puede ser matemático, de
simulación o heurístico, dependiendo de la complejidad de los cálculos
matemáticos que se requieran.
3. Solución del modelo. Una vez que se tiene el modelo, se procede a
derivar una solución matemática empleando las diversas técnicas y métodos
matemáticos para resolver problemas y ecuaciones. Debemos tener en
cuenta que las soluciones que se obtienen en este punto del proceso, son
matemáticas y debemos interpretarlas en el mundo real. Además, para la
solución del modelo, se deben realizar análisis de sensibilidad, es decir, ver
como se comporta el modelo a cambios en las especificaciones y parámetros
del sistema. Esto se hace, debido a que los parámetros no necesariamente
son precisos y las restricciones pueden estar equivocadas.
4. Validación del modelo. La validación de un modelo requiere que se
determine si dicho modelo puede predecir con certeza el comportamiento del
sistema. Un método común para probar la validez del modelo, es someterlo a
datos pasados disponibles del sistema actual y observar si reproduce las
situaciones pasadas del sistema. Pero como no hay seguridad de que el
comportamiento futuro del sistema continúe replicando el comportamiento
pasado, entonces siempre debemos estar atentos de cambios posibles del
sistema con el tiempo, para poder ajustar adecuadamente el modelo.
5. Implementación de resultados. Una vez que hayamos obtenido la
solución o soluciones del modelo, el siguiente y último paso del proceso es
interpretar esos resultados y dar conclusiones y cursos de acción para la
optimización del sistema. Si el modelo utilizado puede servir a otro problema,
es necesario revisar, documentar y actualizar el modelo para sus nuevas
aplicaciones.
Estructura de los modelos empleados en la Investigación de Operaciones.
El enfoque de la Investigación de Operaciones es el modelaje. Un modelo
es una herramienta que nos sirve para lograr una visión bien estructurada de la
realidad. Así, el propósito del modelo es proporcionar un medio para analizar el
comportamiento de las componentes de un sistema con el fin de optimizar su
desempeño. La ventaja que tiene el sacar un modelo que represente una situación
real, es que nos permite analizar tal situación sin interferir en la operación que se
realiza, ya que el modelo es como si fuera “un espejo” de lo que ocurre.
Para aumentar la abstracción del mundo real, los modelos se clasifican
como 1) icónicos, 2) análogos, 3) simbólicos.
Los modelos icónicos son la representación física, a escala reducida o
aumentada de un sistema real.
Los modelos análogos esencialmente requieren la sustitución de una
propiedad por otra con el fin de permitir la manipulación del modelo. Después de
resolver el problema, la solución se reinterpreta de acuerdo al sistema original.
Los modelos más importantes para la investigación de operaciones, son
los modelos simbólicos o matemáticos, que emplean un conjunto de símbolos y
funciones para representar las variables de decisión y sus relaciones para
describir el comportamiento del sistema. El uso de las matemáticas para
representar el modelo, el cual es una representación aproximada de la realidad,
nos permite aprovechar las computadoras de alta velocidad y técnicas de solución
con matemáticas avanzadas.
Un modelo matemático comprende principalmente tres conjuntos básicos
de elementos. Estos son: 1) variables y parámetros de decisión, 2) restricciones y
3) función objetivo.
1. Variables y parámetros de decisión. Las variables de decisión son las
incógnitas (o decisiones) que deben determinarse resolviendo el modelo. Los
parámetros son los valores conocidos que relacionan las variables de
decisión con las restricciones y función objetivo. Los parámetros del modelo
pueden ser determinísticos o probabilísticos.
2. Restricciones. Para tener en cuenta las limitaciones tecnológicas,
económicas y otras del sistema, el modelo debe incluir restricciones
(implícitas o explícitas) que restrinjan las variables de decisión a un rango de
valores factibles.
3. Función objetivo. La función objetivo define la medida de efectividad del
sistema como una función matemática de las variables de decisión.
La solución óptima será aquella que produzca el mejor valor de la función
objetivo, sujeta a las restricciones.
Concepto de optimización.
Una característica adicional, que se mencionó como de pasada, es que la
Investigación de Operaciones intenta encontrar la mejor solución, o la solución
óptima, al problema bajo consideración. En lugar de contentarse con sólo mejorar
el estado de las cosas, la meta es identificar el mejor curso de acción posible. Aún
cuando debe interpretarse con todo cuidado, esta “búsqueda de la optimalidad” es
un aspecto muy importante dentro de la Investigación de Operaciones.
Áreas de aplicación de la Investigación de Operaciones.
Como su nombre lo dice, Investigación de Operaciones significa “hacer investigación sobre las operaciones”. Esto dice algo del enfoque como del área de aplicación. Entonces, la Investigación de Operaciones se aplica a problemas que se refieren a la conducción y coordinación de operaciones o actividades dentro de una organización. La naturaleza de la organización es esencialmente inmaterial y, de hecho, la Investigación de Operaciones se ha aplicado en los negocios, la industria, la milicia, el gobierno, los hospitales, etc. Así, la gama de aplicaciones es extraordinariamente amplia. Casi todas las organizaciones más grandes del mundo (alrededor de una docena) y una buena proporción de las industrias más pequeñas cuentan con grupos bien establecidos de Investigación de Operaciones. Muchas industrias, incluyendo la aérea y de proyectiles, la automotriz, la de comunicaciones, computación, energía eléctrica, electrónica, alimenticia, metalúrgica, minera, del papel, del petróleo y del transporte, han empleado la Investigación de Operaciones. Las instituciones financieras, gubernamentales y de salud están incluyendo cada vez más estas técnicas. Para ser más específicos, se consideran algunos problemas que se han resuelto mediante algunas técnicas de Investigación de Operaciones. La programación lineal se ha usado con éxito en la solución de problemas referentes a la asignación de personal, la mezcla de materiales, la distribución y el transporte y las carteras de inversión. La programación dinámica se ha aplicado con buenos resultados en áreas tales como la planeación de los gastos de comercialización, la estrategia de ventas y la planeación de la producción. La teoría de colas ha tenido aplicaciones en la solución de problemas referentes al congestionamiento del tráfico, al servicio de máquinas sujetas a descomposturas, a la determinación del nivel de la mano de obra, a la programación del tráfico aéreo, al diseño de presas, a la programación de la producción y a la administración de hospitales. Otras técnicas de Investigación de Operaciones, como la teoría de inventarios, la teoría de juegos y la simulación, han tenido exitosas aplicaciones en una gran variedad de contextos.ORÍGENES DE LA INVESTIGACIÓN DE OPERACIONES
La toma de decisiones es un proceso que se inicia cuando una persona observa un
problema y determina que es necesario resolverlo procediendo a definirlo, a formular
un objetivo, reconocer las limitaciones o restricciones, a generar alternativas de
solución y evaluarlas hasta seleccionar la que le parece mejor, este proceso puede
se cualitativo o cuantitativo.
El enfoque cualitativo se basa en la experiencia y el juicio personal, las habilidades
necesarias en este enfoque son inherentes en la persona y aumentan con la
práctica. En muchas ocasiones este proceso basta para tomar buenas decisiones. El
enfoque cuantitativo requiere habilidades que se obtienen del estudio de
herramientas matemáticas que le permitan a la persona mejorar su efectividad en la
toma de decisiones. Este enfoque es útil cuando no se tiene experiencia con
problemas similares o cuando el problema es tan complejo o importante que requiere
de un análisis exhaustivo para tener mayor posibilidad de elegir la mejor solución.
La investigación de operaciones proporciona a los tomadores de decisiones bases
cuantitativas para seleccionar las mejores decisiones y permite elevar su habilidad
para hacer planes a futuro.
En el ambiente socioeconómico actual altamente competitivo y complejo, los
métodos tradicionales de toma de decisiones se han vuelto inoperantes e
inadmisibles ya que los responsables de dirigir las actividades de las empresas e
instituciones se enfrentan a situaciones complicadas y cambiantes con rapidez que
requieren de soluciones creativas y prácticas apoyadas en una base cuantitativa
sólida.
En organizaciones grandes se hace necesario que el tomador de decisiones tenga
un conocimiento básico de las herramientas cuantitativas que utilizan los
especialistas para poder trabajar en forma estrecha con ellos y ser receptivos a las
soluciones y recomendaciones que se le presenten.
En organizaciones pequeñas puede darse que el tomador de decisiones domine las
herramientas cuantitativas y él mismo las aplique para apoyarse en ellas y así tomar
sus decisiones.
Desde al advenimiento de la Revolución Industrial, el mundo ha sido testigo de un
crecimiento sin precedentes en el tamaño y la complejidad de las organizaciones.
Los pequeños talleres artesanales se convirtieron en las corporaciones actuales de
miles de millones de pesos. Una parte integral de este cambio revolucionario fue el
gran aumento en la división del trabajo y en la separación de las responsabilidades
administrativas en estas organizaciones. Los resultados han sido espectaculares. Sin
embargo, junto con los beneficios, el aumento en el grado de especialización creo
nuevos problemas que ocurren hasta la fecha en muchas empresas. Uno de estos
problemas es las tendencia de muchas de las componentes de una organización a
convertirse en imperios relativamente autónomos, con sus propias metas y sistemas
de valores, perdiendo con esto la visión de la forma en que encajan sus actividades y
objetivos con los de toda la organización. Lo que es mejor para una componente,
puede ir en detrimento de otra, de manera que pueden terminar trabajando con
objetivos opuestos. Un problema relacionado con esto es que, conforme la
complejidad y la especialización crecen, se vuelve más difícil asignar los recursos
disponibles a las diferentes actividades de la manera más eficaz para la organización
como un todo. Este tipo de problemas, y la necesidad de encontrar la mejor forma de
resolverlos, proporcionaron el ambiente adecuado para el surgimiento de la
INVESTIGACIÓN DE OPERACIONES (IO).
Las raíces de la investigación de operaciones se remontan a muchas décadas,
cuando se hicieron los primeros intentos para emplear el método científico en la
administración de una empresa. Sin embargo, el inicio de la actividad llamada
investigación de operaciones, casi siempre se atribuye a los servicios militares
prestados a principios de la segunda guerra mundial. Debido a los esfuerzos bélicos,
existía una necesidad urgente de asignar recursos escasos a las distintas
operaciones militares y a las actividades dentro de cada operación, en la forma más
efectiva. Por esto, las administraciones militares americana e inglesa hicieron un
llamado a un gran número de científicos para que aplicaran el método científico a
éste y a otros problemas estratégicos y tácticos. De hecho, se les pidió que hicieran
investigación sobre operaciones (militares). Estos equipos de científicos fueron los
primeros equipos de IO. Con el desarrollo de métodos efectivos para el uso del
nuevo radar, estos equipos contribuyeron al triunfo del combate aéreo inglés. A
través de sus investigaciones para mejorar el manejo de las operaciones
antisubmarinas y de protección, jugaron también un papel importante en la victoria
de la batalla del Atlántico Norte. Esfuerzos similares fueron de gran ayuda en a isla
de campaña en el pacífico.
Al terminar la guerra, el éxito de la investigación de operaciones en las actividades
bélicas generó un gran interés en sus aplicaciones fuera del campo militar. Como la
explosión industrial seguía su curso, los problemas causados por el aumento en la
complejidad y especialización dentro de las organizaciones pasaron de nuevo a
primer plano. Comenzó a ser evidente para un gran número de personas, incluyendo
a los consultores industriales que habían trabajado con o para los equipos de IO
durante la guerra, que estos problemas eran básicamente los mismos que los
enfrentados por la milicia, pero en un contexto diferente. Cuando comenzó la década
de 1950, estos individuos habían introducido el uso de la investigación de
operaciones en la industria, los negocios y el gobierno. Desde entonces, esta
disciplina se ha desarrollado con rapidez.
Se pueden identificar por lo menos otros dos factores que jugaron un papel
importante en el desarrollo de la investigación de operaciones durante este período.
Uno es el gran progreso que ya se había hecho en el mejoramiento de las técnicas
disponibles en esta área. Después de la guerra, muchos científicos que habían
participado en los equipos de IO o que tenían información sobre este trabajo, se
encontraban motivados a buscar resultados sustanciales en este campo; de esto
resultaron avances importantes. Un ejemplo sobresaliente es el método simplex para
resolver problemas de programación lineal, desarrollado en 1947 por George
Dantzing. Muchas de las herramientas características de la investigación de
operaciones, como programación lineal, programación dinámica, líneas de espera y
teoría de inventarios, fueron desarrolladas casi por completo antes del término de la
década de 1950.
Un segundo factor que dio ímpetu al desarrollo de este campo fue el advenimiento
de la computadoras. Para manejar de una manera efectiva los complejos problemas
inherentes a esta disciplina, por lo general se requiere un gran número de cálculos.
Llevarlos a cabo a mano puede resultar casi imposible. Por lo tanto, el desarrollo de
la computadora electrónica digital, con su capacidad para realizar cálculos
aritméticos, miles o tal vez millones de veces más rápido que los seres humanos, fue
una gran ayuda para la investigación de operaciones. Un avance más tuvo lugar en
la década de 1980 con el desarrollo de las computadoras personales cada vez más
rápidas, acompañado de buenos paquetes de software para resolver problemas de
IO, esto puso las técnicas al alcance de un gran número de personas. Hoy en día,
literalmente millones de individuos tiene acceso a estos paquetes. En consecuencia,
por rutina, se usa toda una gama e computadoras, desde las grandes hasta las
portátiles, para resolver problemas de investigación de operaciones.
NATURALEZA DE LA INVESTIGACIÓN DE OPERACIONES
Como su nombre lo dice, la investigación de operaciones significa "hacer
investigación sobre las operaciones". Entonces, la investigación de operaciones se
aplica a problemas que se refieren a la conducción y coordinación de operaciones (o
actividades) dentro de una organización. La naturaleza de la organización es
esencialmente inmaterial y, de hecho, la investigación de operaciones se ha aplicado
de manera extensa en áreas tan diversas como la manufactura, el transporte, la
constitución, las telecomunicaciones, la planeación financiera, el cuidado de la salud,
la milicia y los servicios públicos, por nombrar sólo unas cuantas. Así, la gama de
aplicaciones es extraordinariamente amplia.
La parte de investigación en el nombre significa que la investigación de operaciones
usa un enfoque similar a la manera en que se lleva a cabo la investigación en los
campos científicos establecidos. En gran medida, se usa el método científico para
investigar el problema en cuestión. (De hecho, en ocasiones se usa el término
ciencias de la administración como sinónimo de investigación de operaciones.) En
particular, el proceso comienza por la observación cuidadosa y la formulación del
problema incluyendo la recolección de los datos pertinentes. El siguiente paso es la
construcción de un modelo científico (por lo general matemático) que intenta abstraer
la esencia del problema real. En este punto se propone la hipótesis de que el modelo
es una representación lo suficientemente precisa de las características esenciales de
la situación como para que las conclusiones (soluciones) obtenidas sean válidas
también para el problema real. Después, se llevan a cabo los experimentos
adecuados para probar esta hipótesis, modificarla si es necesario y eventualmente
verificarla. (Con frecuencia este paso se conoce como validación del modelo.)
Entonces, en cierto modo, la investigación e operaciones incluye la investigación
científica creativa de las propiedades fundamentales de las operaciones. Sin
embargo, existe más que esto. En particular, la IO se ocupa también de la
administración práctica de la organización. Así, para tener éxito, deberá también
proporcionar conclusiones claras que pueda usar el tomador de decisiones cuando
las necesite.
Una característica más de la investigación de operaciones es su amplio punto de
vista. Como quedó implícito en la sección anterior, la IO adopta un punto de vista
organizacional. de esta manera, intenta resolver los conflictos de intereses entre las
componentes de la organización de forma que el resultado sea el mejor para la
organización completa. Esto no significa que el estudio de cada problema deba
considerar en forma explícita todos los aspectos de la organización sino que los
objetivos que se buscan deben ser consistentes con los de toda ella.
Una característica adicional es que la investigación de operaciones intenta encontrar
una mejor solución, (llamada solución óptima) para el problema bajo consideración.
(Decimos una mejor solución y no la mejor solución porque pueden existir muchas
soluciones que empaten como la mejor.) En lugar de contentarse con mejorar el
estado de las cosas, la meta es identificar el mejor curso de acción posible. Aun
cuando debe interpretarse con todo cuidado en términos de las necesidades reales
de la administración, esta "búsqueda de la optimidad" es un aspecto importante
dentro de la investigación de operaciones.
Todas estas características llevan de una manera casi natural a otra. Es evidente
que no puede esperarse que un solo individuo sea un experto en todos lo múltiples
aspectos del trabajo de investigación de operaciones o de los problemas que se
estudian; se requiere un grupo de individuos con diversos antecedentes y
habilidades. Entonces, cuando se va a emprender un estudio de investigación de
operaciones completo de un nuevo problema, por lo general es necesario emplear el
empleo de equipo. Este debe incluir individuos con antecedentes firmes en
matemáticas, estadística y teoría de probabilidades, al igual que en economía,
administración de empresas, ciencias de la computación, ingeniería, ciencias físicas,
ciencias del comportamiento y, por supuesto, en las técnicas especiales de
investigación de operaciones. El equipo también necesita tener la experiencia y las
habilidades necesarias para permitir la consideración adecuada de todas las
ramificaciones del problema a través de la organización.
¿QUÉ ES LA INVESTIGACIÓN DE OPERACIONES?
Como toda disciplina en desarrollo, la investigación de operaciones ha ido
evolucionando no sólo en sus técnicas y aplicaciones sino en la forma como la
conceptualizan los diferentes autores, en la actualidad no existe solamente una
definición sino muchas, algunas demasiado generales, otras demasiado engañosas,
aquí seleccionamos dos de las mas aceptadas y representativas.
LA DEFINICIÓN DE CHURCHMAN, ACKOFF Y ARNOFF: LA INVESTIGACIÓN
DE OPERACIONES ES LA APLICACIÓN, POR GRUPOS
INTERDISCIPLINARIOS, DEL MÉTODO CIENTÍFICO A PROBLEMAS
RELACIONADOS CON EL CONTROL DE LAS ORGANIZACIONES O SISTEMAS
(HOMBRE-MÁQUINA), A FIN DE QUE SE PRODUZCAN SOLUCIONES QUE
MEJOR SIRVAN A LOS OBJETIVOS DE LA ORGANIZACIÓN.
De ésta definición se pueden destacar los siguientes conceptos:
1. Una organización es un sistema formado por componentes que se interaccionan,
unas de estas interacciones pueden ser controladas y otras no.
2. En un sistema la información es una parte fundamental, ya que entre las
componentes fluye información que ocasiona la interacción entre ellas. También
dentro de la estructura de los sistemas se encuentran recursos que generan
interacciones. Los objetivos de la organización se refieren a la eficacia y eficiencia
con que las componentes pueden controlarse, el control es un mecanismo de
autocorrección del sistema que permite evaluar los resultados en términos de los
objetivos establecidos.
3. La complejidad de los problemas que se presentan en las organizaciones ya no
encajan en una sola disciplina del conocimiento, se han convertido en
multidisciplinario por lo cual para su análisis y solución se requieren grupos
compuestos por especialistas de diferentes áreas del conocimiento que logran
comunicarse con un lenguaje común.
4. La investigación de operaciones es la aplicación de la metodología científica a
través modelos matemáticos, primero para representar al problema y luego para
resolverlo. La definición de la sociedad de investigación de operaciones de la
Gran Bretaña es la siguiente:
La investigación de operaciones es el ataque de la ciencia moderna a los
complejos problemas que surgen en la dirección y en la administración de
grandes sistemas de hombres, máquinas, materiales y dinero, en la industria, en
los negocios, en el gobierno y en la defensa. Su actitud diferencial consiste en
desarrollar un modelo científico del sistema tal, que incorpore valoraciones de
factores como el azar y el riesgo y mediante el cual se predigan y comparen los
resultados de decisiones, estrategias o controles alternativos. Su propósito es el
de ayudar a la gerencia a determinar científicamente sus políticas y acciones.
EN RELACIÓN A ÉSTA DEFINICIÓN DEBEN DESTACARSE LOS SIGUIENTES
ASPECTOS:
1. Generalmente se asocian los conceptos de dirección y administración a las
empresas de tipo lucrativo, sin embargo, una empresa es un concepto más
amplio, es algo que utiliza hombres, máquinas, materiales y dinero con un
propósito específico; desde éste punto de vista, se considera como empresa
desde una universidad hasta una armadora de automóviles.
2. Para tratar de explicar el comportamiento de un sistema complejo, el científico
debe representarlo en términos de los conceptos que maneja, lo hace expresando
todos los rasgos principales del sistema por medio de relaciones matemáticas. A
esta representación formal se le llama modelo.
3. La esencia de un modelo es que debe ser predictivo, lo cual no significa predecir
el futuro, pero si ser capaz de indicar muchas cosas acerca de la forma en que se
puede esperar que un sistema opere en una variedad de circunstancias, lo que
permite valorar su vulnerabilidad. Si se conocen las debilidades del sistema se
pueden tomar cursos de acción agrupados en tres categorías: A) Efectuar
cambios que lleven a la empresa o parte de ella a una nueva ruta; B) Realizar
un plan de toma de decisiones; C) Instalar estrategias que generen
decisiones. Cuando se aplica alguno de estos remedios, la investigación de
operaciones nos ayuda a determinar la acción menos vulnerable ante un futuro
incierto.
4. El objetivo global de la investigación de operaciones es el de apoyar al tomador
de decisiones, en cuanto ayudarlo a cumplir con su función basado en estudios
científicamente fundamentados.
ENFOQUE DE LA INVESTIGACIÓN DE OPERACIONES:
la parte innovadora de la IO es sin duda alguna su enfoque modelístico, producto de
sus creadores aunado a la presión de supervivencia de la guerra o la sinergía
generada al combinarse diferentes disciplinas, una descripción del enfoque es la
siguiente. (Ver la figura 11).
1. Se define el sistema real en donde se presenta el problema. Dentro del sistema
interactuan normalmente un gran numero de variables.
2. Se seleccionan las variables que norman la conducta o el estado actual del
sistema, llamadas variables relevantes, con las cuales se define un sistema
asumido del sistema real.
3. Se construye un modelo cuantitativo del sistema asumido, identificando y
simplificando las relaciones entre las variables relevantes mediante las utilización
de funciones matemáticas.
4. Se obtiene la solución al modelo cuantitativo mediante la aplicación de una o
mas de las técnicas desarrolladas por la IO.
5. Se adapta e imprime la máxima realidad posible a la solución teórica del
problema real obtenida en el punto 4, mediante la consideración de factores
cualitativos o no cuantificables, los cuales no pudieron incluirse en el modelo.
Además se ajusta los detalles finales vía el juicio y la experiencia del tomador de
decisiones.
6. Se implanta la solución en el sistema real.
LA INVESTIGACIÓN DE OPERACIONES OBTIENE LA SOLUCIÓN DEL
PROBLEMA REAL INDIRECTAMENTE, Y NO COMO NORMALMENTE SE
INTENTARÍA PASANDO DIRECTAMENTE DEL PROBLEMA REAL A LA
SOLUCIÓN REAL.
METODOLOGÍA DE LA INVESTIGACION DE OPERACIONES
DEFINICIÓN DEL PROBLEMA Y RECOLECCIÓN DE DATOS
La mayor parte de los problemas prácticos con los que se enfrenta el equipo IO
están descritos inicialmente de una manera vaga. Por consiguiente, la primera
actividad que se debe realizar es el estudio del sistema relevante y el desarrollo de
un resumen bien definido del problema que se va a analizar. Esto incluye determinar
los objetivos apropiados, las restricciones sobre lo que se puede hacer, las
interrelaciones del área bajo estudio con otras áreas de la organización, los
diferentes cursos de acción posibles, los límites de tiempo para tomar una decisión,
etc. Este proceso de definir el problema es crucial ya que afectará en forma
significativa la relevancia de las conclusiones del estudio. ¡Es difícil extraer una
respuesta "correcta" a partir de un problema "equivocado"!
Por su naturaleza, la investigación de operaciones se encarga del bienestar de toda
la organización, no sólo de algunos de sus componentes. Un estudio de IO busca
soluciones óptimas globales y no soluciones subóptimas aunque sean lo mejor para
uno de los componente. Entonces, idealmente, los objetivos que se formulan debe
coincidir con los de toda la organización. Sin embargo, esto no siempre es
conveniente. Muchos problemas interesan nada más a una parte de la organización,
de manera que el análisis sería innecesariamente besado si los objetivos fueran muy
generales y si se prestara atención especial a todos los efectos secundarios sobre el
resto de la organización. En lugar de ello, los objetivos usados en un estudio deben
ser tan específicos como sea posible, siempre y cuando contemplen las metas
principales del tomador de decisiones y mantengan un nivel razonable de
consistencia con los objetivos de los altos niveles.
Las condiciones fundamentales para que exista un problema es que se establezca
una diferencia entre lo que es (situación actual) y lo que debe ser (situación deseada
u objetivo) y además exista cuando menos una forma de eliminar o disminuir esa
diferencia. Los componentes de un problema son: a) el tomador de decisiones o
ejecutivo; b) los objetivos de la organización; c) el sistema o ambiente en el que se
sitúa el problema; d) Los cursos de acción alternativos que se pueden tomar para
resolverlo.
Para formular un problema se requiere; a) identificar las componentes y variables
controlables y no controlables del sistema; b) identificar los posibles cursos de
acción, determinados por las componentes controlables; c) definir el marco de
referencia dado por las componentes no controlables; d) definir los objetivos que se
busca alcanzar y clasificarlos por orden de importancia; e) identificar las
interpelaciones importantes entre las diferentes partes del sistema y encontrar las
restricciones que existen.
FORMULACIÓN DE UN MODELO MATEMÁTICO
Una vez definido el problema del tomador de decisiones, la siguiente etapa consiste
en reformularlo de manera conveniente para su análisis. La forma convencional en
que la investigación de operaciones realiza esto es construyendo un modelo
matemático que represente la esencia del problema. Antes de analizar como
formular los modelos de este tipo, se explorará la naturaleza general de los modelos
y, en particular, la de los modelos matemáticos.
El modelo matemático está constituido por relaciones matemáticas (ecuaciones y
desigualdades) establecidas en términos de variables, que representa la esencia el
problema que se pretende solucionar.
Para construir un modelo es necesario primero definir las variables en función de las
cuales será establecido. Luego, se procede a determinar matemáticamente cada una
de las dos partes que constituyen un modelo: a) la medida de efectividad que
permite conocer el nivel de logro de los objetivos y generalmente es una función
(ecuación) llamada función objetivo; b) las limitantes del problema llamadas
restricciones que son un conjunto de igualdades o desigualdades que constituyen las
barreras y obstáculos para la consecución del objetivo.
Un modelo siempre debe ser menos complejo que el problema real, es una
aproximación abstracta de la realidad con consideraciones y simplificaciones que
hacen más manejable el problema y permiten evaluar eficientemente las alternativas
de solución.
Los modelos matemáticos tienen muchas ventajas sobre una descripción verbal del
problema. Una ventaja obvia es que el modelo matemático describe un problema en
forma mucho más concisa. Esto tiende a hacer que toda la estructura del problema
sea más comprensible y ayude a revelar las relaciones importantes entre causa y
efecto. De esta manera, indica con más claridad que datos adicionales son
importantes para el análisis. También facilita simultáneamente el manejo del
problema en su totalidad y el estudio de todas sus interpelaciones. Por último, un
modelo matemático forma un puente para poder emplear técnicas matemáticas y
computadoras de alto poder, para analizar el problema. Sin duda, existe una amplia
disponibilidad de paquetes de software para muchos tipos de modelos matemáticos,
para micro y minicomputadoras.
Por otro lado, existen obstáculos que deben evitarse al usar modelos matemáticos.
Un modelo es, necesariamente, una idealización abstracta del problema, por lo que
casi siempre se requieren aproximaciones y suposiciones de simplificación si se
quiere que el modelo sea manejable (susceptible de ser resuelto). Por lo tanto, debe
tenerse cuidado de que el modelo sea siempre una representación válida del
problema. El criterio apropiado para juzgar la validez de un modelo es el hecho de si
predice o no con suficiente exactitud los efectos relativos de los diferentes cursos de
acción, para poder tomar una decisión que tenga sentido. En consecuencia, no es
necesario incluir detalles sin importancia o factores que tienen aproximadamente el
mismo efecto sobre todas las opciones. Ni siquiera es necesario que la magnitud
absoluta de la medida de efectividad sea aproximadamente correcta para las
diferentes alternativas, siempre que sus valores relativos (es decir, las diferencias
entre sus valores) sean bastante preciso. Entonces, todo lo que se requiere es que
exista una alta correlación entre la predicción del modelo y lo que ocurre en la vida
real. Para asegurar que este requisito se cumpla, es importante hacer un número
considerable de pruebas del modelo y las modificaciones consecuentes. Aunque
esta fase de pruebas se haya colocado después en el orden del libro, gran parte del
trabajo de validación del modelo se lleva a cabo durante la etapa de construcción
para que sirva de guía en la obtención del modelo matemático.
OBTENCIÓN DE UNA SOLUCIÓN A PARTIR DEL MODELO
Resolver un modelo consiste en encontrar los valores de las variables dependientes,
asociadas a las componentes controlables del sistema con el propósito de optimizar,
si es posible, o cuando menos mejorar la eficiencia o la efectividad del sistema
dentro del marco de referencia que fijan los objetivos y las restricciones del
problema.
La selección del método de solución depende de las características del modelo. Los
procedimientos de solución pueden ser clasificados en tres tipos: a) analíticos, que
utilizan procesos de deducción matemática; b) numéricos, que son de carácter
inductivo y funcionan en base a operaciones de prueba y error; c) simulación, que
utiliza métodos que imitan o, emulan al sistema real, en base a un modelo.
Muchos de los procedimientos de solución tienen la característica de ser iterativos,
es decir buscan la solución en base a la repetición de la misma regla analítica hasta
llegar a ella, si la hay, o cuando menos a una aproximación.
PRUEBA DEL MODELO
El desarrollo de un modelo matemático grande es análogo en algunos aspectos al
desarrollo de un programa de computadora grande. Cuando se completa la primera
versión, es inevitable que contenga muchas fallas. El programa debe probarse de
manera exhaustiva para tratar de encontrar y corregir tantos problemas como sea
posible. Eventualmente, después de una larga serie de programas mejorados, el
programador (o equipo de programación) concluye que el actual da, en general,
resultados razonablemente válidos. Aunque sin duda quedarán algunas fallas
ocultas en el programa (y quizá nunca se detecten, se habrán eliminado suficientes
problemas importantes como para que sea confiable utilizarlo.
De manera similar, es inevitable que la primera versión de un modelo matemático
grande tenga muchas fallas. Sin duda, algunos factores o interpelaciones relevantes
no se incorporaron al modelo y algunos parámetros no se estimaron correctamente.
Esto no se puede eludir dada la dificultad de la comunicación y la compresión de
todos los aspectos y sutilezas de un problema operacional complejo, así como la
dificultad de recolectar datos confiables. Por lo tanto, antes de usar el modelo debe
probarse exhaustivamente para intentar identificar y corregir todas las fallas que se
pueda. Con el tiempo, después de una larga serie de modelos mejorados, el equipo
de IO concluye que el modelo actual produce resultados
razonablemente válidos. Aunque sin duda quedarán algunos problemas menores
ocultos en el modelo (y quizá nunca se detecten), las fallas importantes se habrán
eliminado de manera que ahora es confiable usar el modelo. Este proceso de prueba
y mejoramiento de un modelo para incrementar su validez se conoce como
validación del modelo.
Debido a que el equipo de IO puede pasar meses desarrollando todas las piezas
detalladas del modelo, es sencillo "no ver el bosque por buscar los árboles".
Entonces, después de completar los detalles ("los árboles") de la versión inicial del
modelo, una buena manera de comenzar las pruebas es observarlo en forma global
("el bosque") para verificar los errores u omisiones obvias. El grupo que hace esta
revisión debe, de preferencia, incluir por lo menos a una persona que no haya
participado en la formulación. Al examinar de nuevo la formulación del problema y
comprarla con el modelo pueden descubrirse este tipo de errores. También es útil
asegurarse de que todas las expresiones matemáticas sean consistentes en las
dimensiones de las unidades que emplean. Además, puede obtenerse un mejor
conocimiento de la validez del modelo variando los valores de los parámetros de
entrada y/o de las variables de decisión, y comprobando que los resultados del
modelo se comporten de una manera factible. Con frecuencia, esto es
especialmente revelador cuando se asignan a los parámetros o a las variables
valores extremos cercanos a su máximo o a su mínimo.
Un enfoque más sistemático para la prueba del modelo es emplear una prueba
retrospectiva. Cuando es aplicable, esta prueba utiliza datos históricos y
reconstruye el pasado para determinar si el modelo y la solución resultante hubieran
tenido un buen desempeño, de haberse usado. La comparación de la efectividad de
este desempeño hipotético con lo que en realidad ocurrió, indica si el uso del modelo
tiende a dar mejoras significativas sobre la práctica actual. Puede también indicar
áreas en las que el modelo tiene fallas y requiere modificaciones. Lo que es más, el
emplear las alternativas de solución y estimar sus desempeños históricos
hipotéticos, se pueden reunir evidencias en cuanto a lo bien que el modelo predice
los efectos relativos de los diferentes cursos de acción.
Cuando se determina que el modelo y la solución no son válidos, es necesario iniciar
nuevamente el proceso revisando cada una de las fases de la metodología de la
investigación de operaciones.
ESTABLECIMIENTO DE CONTROLES SOBRE LA SOLUCION
Una solución establecida como válida para un problema, permanece como tal
siempre y cuando las condiciones del problema tales como: las variables no
controlables, los parámetros, las relaciones, etc., no cambien significativamente.
Esta situación
se vuelve más factible cuando algunos de los parámetros fueron estimados
aproximadamente. Por lo anterior, es necesario generar información adicional sobre
el comportamiento de la solución debido a cambios en los parámetros del modelo.
usualmente esto se conoce como análisis de sensibilidad. En pocas palabras, esta
fase consiste en determinar los rangos de variación de los parámetros dentro de los
cuales no cambia la solución del problema.
IMPLANTACIÓN DE LA SOLUCIÓN
El paso final se inicia con el proceso de "vender" los hallazgos que se hicieron a lo
largo del proceso a los ejecutivos o tomadores de decisiones. Una vez superado
éste obstáculo, se debe traducir la solución encontrada a instrucciones y
operaciones comprensibles para los individuos que intervienen en la operación y
administración del sistema. La etapa de implantación de una solución se simplifica
en gran medida cuando se ha propiciado la participación de todos los involucrados
en el problema en cada fase de la metodología. Preparación para la aplicación del
modelo
Esta etapa es crítica, ya que es aquí, y sólo aquí, donde se cosecharán los
beneficios del estudio. Por lo tanto, es importante que el equipo de IO participe, tanto
para asegurar que las soluciones del modelo se traduzcan con exactitud a un
procedimiento operativo, como para corregir cualquier defecto en la solución que
salga a la luz en este momento.
El éxito de la puesta en práctica depende en gran parte del apoyo que proporcionen
tanto la alta administración como la gerencia operativa. Es más probable que el
equipo de IO obtenga este apoyo si ha mantenido a la administración bien informada
y ha fomentado la guía de la gerencia durante el estudio. La buena comunicación
ayuda a asegurar que el estudio logre lo que la administración quiere y por lo tanto
merezca llevarse a la práctica. También proporciona a la administración el
sentimiento de que el estudio es suyo y esto facilita el apoyo para la implantación.
La etapa de implantación incluye varios pasos. Primero, el equipo de investigación
de operaciones de una cuidadosa explicación a la gerencia operativa sobre el nuevo
sistema que se va a adoptar y su relación con la realidad operativa. En seguida,
estos dos grupos comparten la responsabilidad de desarrollar los procedimientos
requeridos para poner este sistema en operación. La gerencia operativa se encarga
después de dar una capacitación detallada al personal que participa, y se inicia
entonces el nuevo curso de acción. Si tiene éxito, el nuevo sistema se podrá emplear
durante algunos años. Con esto en mente, el equipo de IO supervisa la experiencia
inicial con la acción tomada para identificar cualquier modificación que tenga que
hacerse en el futuro.
A la culminación del estudio, es apropiado que el equipo de investigación de
operaciones documento su metodología con suficiente claridad y detalle para que el
trabajo sea reproducible. Poder obtener una réplica debe ser parte del código de
ética profesional del investigador de operaciones. Esta condición es crucial
especialmente cuando se estudian políticas gubernamentales en controversia.
INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL
Muchas personas clasifican el desarrollo de la programación lineal entre los avances
científicos más importantes de mediados del siglo XX, su impacto desde 1950 ha
sido extraordinario. En la actualidad es una herramienta de uso normal que ha
ahorrado miles o millones de pesos a muchas compañías o negocios, incluyendo
empresas medianas en los distintos países industrializados del mundo; su aplicación
a otros sectores de la sociedad se está ampliando con rapidez. Una proporción muy
grande de los cálculos científicos en computadoras está dedicada al uso de la
programación lineal.
¿Cuál es la naturaleza de esta notable herramienta y qué tipos de problemas puede
manejar. Expresado brevemente, el tipo más común de aplicación abarca el
problema general de asignar recursos limitados entre actividades competitivas de la
mejor manera posible (es decir, en forma óptima). Con más precisión, este problema
incluye elegir el nivel de ciertas actividades que compiten por recursos escasos
necesarios para realizarlas. Después, los niveles de actividad elegidos dictan la
cantidad de cada recurso que consumirá cada una de ellas. La variedad de
situaciones a las que se puede aplicar esta descripción es sin duda muy grande, y va
desde la asignación de instalaciones de producción a los productos, hasta la
asignación de los recursos nacionales a las necesidades de un país; desde la
selección de una cartera de inversiones, hasta la selección de los patrones de envío;
desde la planeación agrícola, hasta el diseño de una terapia de radiación, etc. No
obstante, el ingrediente común de todas estas situaciones es la necesidad de
asignar recursos a las actividades eligiendo los niveles de las mismas.
La programación lineal utiliza un modelo matemático para describir el problema. El
adjetivo lineal significa que todas las funciones matemáticas del modelo deber ser
funciones lineales. En este caso, las palabra programación no se refiere a
programación en computadoras; en esencia es un sinónimo de planeación. Así, la
programación lineal trata la planeación de las actividades para obtener un resultado
óptimo, esto es, el resultado que mejor alcance la meta especificada (según el
modelo matemático) entre todas las alternativas de solución.
Aunque la asignación de recursos a las actividades es la aplicación más frecuente, la
programación lineal tiene muchas otras posibilidades. de hecho, cualquier problema
cuyo modelo matemático se ajuste al formato general del modelo de programación
lineal es un problema de programación lineal. Aún más, se dispone de un
procedimiento de solución extraordinariamente eficiente llamado método simplex,
para resolver estos problemas, incluso los de gran tamaño. Estas son algunas
causas del tremendo auge de la programación lineal en las últimas décadas.
MODELO DE PROGRAMACIÓN LINEAL
Los términos clave son recursos y actividades, en donde m denota el número de
distintos tipos de recursos que se pueden usar y n denota el número de actividades
bajo consideración. Algunos ejemplos de recursos son dinero y tipos especiales de
maquinaria, equipo, vehículos y personal. Los ejemplos de actividades incluyen
inversión en proyectos específicos, publicidad en un medio determinado y el envío
de bienes de cierta fuente a cierto destino. En cualquier aplicación de programación
lineal, puede ser que todas las actividades sean de un tipo general (como cualquiera
de los ejemplos), y entonces cada una correspondería en forma individual a las
alternativas específicas dentro de esta categoría general.
El tipo más usual de aplicación de programación lineal involucra la asignación de
recursos a ciertas actividades. La cantidad disponible de cada recurso está limitada,
de forma que deben asignarse con todo cuidado. La determinación de esta
asignación incluye elegir los niveles de las actividades que lograrán el mejor valor
posible de la medida global de efectividad.
Ciertos símbolos se usan de manera convencional para denotar las distintas
componentes de un modelo de programación lineal. Estos símbolos se enumeran a
continuación, junto con su interpretación para el problema general de asignación de
recursos a actividades.
Z = valor de la medida global de efectividad
xj = nivel de la actividad j (para j = 1,2,...,n)
cj = incremento en Z que resulta al aumentar una unidad en el nivel de la actividad
j
bi = cantidad de recurso i disponible para asignar a las actividades (para i =
1,2,...,m)
aij = cantidad del recurso i consumido por cada unidad de la actividad j
El modelo establece el problema en términos de tomar decisiones sobre los niveles
de las actividades, por lo que x1,x2,....,xn se llaman variables de decisión. Los
valores de cj, bi y aij (para i = 1,2,....,m y j = 1,2,....,n) son las constantes de entrada al
modelo. Las cj, bi y aij también se conocen como parámetros del modelo.
FORMA ESTÁNDAR DEL MODELO
Ahora se puede formular al modelo matemático para este problema general de
asignación de recursos a actividades. En Datos necesarios para un modelo de
programación lineal que maneja la asignación de recursos a actividades particular,
este modelo consiste en elegir valores de x1,x2,....,xn para:
optimizar (maximizar o minimizar) Z = c1x1 + c2x2 +....+ cnxn,
sujeta a las restricciones:
a11x1 + a12x2 +....+ a1nxn < b1
a21x1 + a22x2 +....+ a2nxn < b2
.
.
.
am1x1 + am2x2 +....+ amnxn < bm
X1 ³ 0, X2 ³0, ..., Xn ³0.
SUPOSICIONES DEL MODELO DE PROGRAMACIÓN LINEALSUPOSICIONES DEL MODELO DE PROGRAMACIÓN LINEAL
PROPORCIONALIDAD
La contribución de cada actividad al valor de la función objetivo Z es proporcional al
nivel de actividad xj, como lo representa el término cjxj en la función objetivo. De
manera similar, la contribución de cada actividad al lado izquierdo de cada restricción
funcional es proporcional al nivel de la actividad xj, en la forma en que lo representa
el término aijxj en la restricción. En consecuencia, esta suposición elimina cualquier
exponente diferente a 1 para las variables en cualquier término de las funciones (ya
sea la función objetivo o la función en el lado izquierdo de las restricciones
funcionales) en un modelo de programación lineal.
ACTIVIDAD
Establece que la entrada y salida de un recurso en particular al conjunto de
actividades, deben ser la misma cantidad; o sea, que las actividades transforman
los recursos y no los crean o destruyen. Esta suposición garantiza que la
contribución total tanto a la función objetivo como a las restricciones, es igual a la
suma de las contribuciones individuales. Cuando en un problema dado no se tenga
la aditividad puede recurrirse al empleo de otras técnicas de la programación
matemática, dependiendo de cada caso en particular.
ADITIVIDAD
Cada función en un modelo de programación lineal (ya sea la función objetivo o el
lado izquierdo de las restricciones funcionales) es la suma de las contribuciones
individuales de las actividades respectivas.
DIVISIBILIDAD
Las variables de decisión en un modelo de programación lineal pueden tomar
cualquier valor, incluyendo valores no enteros, que satisfagan las restricciones
funcionales y de no negatividad. Así, estas variables no están restringidas a sólo
valores enteros. Como cada variable de decisión representa el nivel de alguna
actividad, se supondrá que las actividades se pueden realizar a niveles fracciónales.
LIMITACIONES DEL MODELO DE PROGRAMACIÓN LINEALLIMITACIONES DEL MODELO DE PROGRAMACIÓN LINEAL
MODELO DETERMINÍSTICOMODELO DETERMINÍSTICO
El modelo de PL involucra únicamente tres tipos de parámetros: Cj, aij y bi; de ahí su
sencillez y gran aplicación. Sin embargo, el valor de dichos parámetros debe ser
conocido y constante. Cuando el valor de los parámetros tiene un cierto riesgo o
incertidumbre, pude utilizarse la programación paramédica, la programación
estocástica, o realizarse un análisis de sensibilidad.
MODELO ESTÁTICOMODELO ESTÁTICO
En algunos modelos matemáticos se han empleado con éxito las ecuaciones
diferenciales, para inducir la variable tiempo en ellos. En este sentido, puede
decidirse que la PL utiliza un modelo estático, ya que la variable tiempo no se
involucra formalmente. Adquiriendo un poco de experiencia en la formulación de
modelos de PL, puede imbuirse la temporabilidad mencionada, con el uso de
subíndices en las variables.
MODELO QUE NO SUBOPTIMIZAMODELO QUE NO SUBOPTIMIZA
Debido a la forma que se plantea el modelo de PL, o encuentra la solución óptima o
declara que ésta no existe. Cuando no es posible obtener una solución óptima y se
debe obtener alguna, se recurre a otra técnica más avanzada que la PL, la cual se
denomina programación lineal por metas.
IMPACTO DE LA INVESTIGACIÓN DE OPERACIONES
La investigación de operaciones ha tenido un impacto impresionante en el
mejoramiento de la eficiencia de numerosas organizaciones en todo el mundo. En el
proceso, la investigación de operaciones ha hecho contribuciones significativas al
incremento de la productividad dentro de la economía de varios países. Hay ahora
más de 30 países que son miembros de la International Federation of Operational
Research Societies (IFORS), en la que cada país cuenta con una sociedad de
investigación de operaciones.
Sin duda, el impacto de la investigación de operaciones continuará aumentando. Por
ejemplo, al inicio de la década de los 90, el U.S. Bureau of Labor Statistics predijo
que la IO sería el área profesional clasificada como la tercera de más rápido
crecimiento para los estudiantes universitarios en Estados Unidos, graduados entre
1990 y 2005. Pronosticó también que, para el año 2005, habría 100 000 personas
trabajando como analistas de investigación de operaciones.
RIESGO AL APLICAR LA INVESTIGACIÓN DE OPERACIONES
Al aplicar la I de O al estudio de sistemas y a la resolución de problemas se corre el
riesgo de tratar de manipular los problemas para buscar que se ajusten a las
diferentes técnicas, modelos de algoritmos establecidos en lugar de analizar los
problemas y buscar resolverlos obteniendo las soluciones mejores, utilizando los
métodos apropiados, es decir resolver el problema utilizando los métodos que
proporcionan las mejoras soluciones y no buscar ajustar el problema a un método
específico.
Para llegar a hacer un uso apropiado de la I de O, es necesario primero comprender
la metodología para resolver los problemas, así como los fundamentos de las
técnicas de solución para de esta forma saber cuándo utilizarlas o no en las
diferentes circunstancias.
LIMITACIONES DE LA INVESTIGACIÓN DE OPERACIONES
1. Frecuentemente es necesario hacer simplificaciones del problema original para
poder manipularlo y detener una solución.
2. La mayoría de los modelos sólo considera un solo objetivo y frecuentemente en
las organizaciones se tienen objetivos múltiples.
3. Existe la tendencia a no considerar la totalidad de las restricciones en un
problema práctico, debido a que los métodos de enseñanza y entrenamiento dan
la aplicación de esta ciencia centralmente se basan en problemas pequeños para
razones de índole práctico, por lo que se desarrolla en los alumnos una opinión
muy simplista e ingenua sobre la aplicación de estas técnicas a problemas reales.
4. Casi nunca se realizan análisis costo-beneficio de la implantación de soluciones
definidas por medio de la I de O, en ocasiones los beneficios potenciales se van
superados por los costos ocasionados por el desarrollo e implantación de un
modelo.
FUENTE: http://www.investigacion-operaciones.com/Historia.htm
Definición:
La investigación de operaciones (IO) aspira a determinar el mejor curso de acción (óptimo) de un problema de decisión con la restricción de recursos limitados. El termino investigación de operaciones muy a menudo esta asociado casí en exclusiva con la aplicación de técnicas matemáticas para representar por medio de un modelo y analizar problemas de decisión. Aunque las matemáticas y los modelos matemáticos representan una piedra angular de IO, la labor consiste más en resolver un problema que en construir y resolver modelos matemáticos. Los modelos de programacion lineal pueden verse como sigue: Xo = F (X1,X2,...,Xn) Restricciones s.a. gi(X1,X2,...,Xn) BI, I=1,2,...,m Xj 0 , j=1,2,...,n Ejercicio: Diseño de la terapia radiactiva. Sea: X1: dosis de radiación rayo 1 X2: dosis de radiación rayo 2 MINIMIZAR DAÑO (Z)=0.4X1+0.5X2 0.3X1+0.1X2 2.7 (TEJIDO CRITICO) 0.5X1+0.5X2 = 6 (REGION DEL TUMOR) 0.6X1+0.4X2 6 (CENTRO TUMOR) X1 0, X2 0 Ejercicio: planeación de la producción. Sea: X1: unidades diarias producidas del producto 1. X2: unidades diarias producidas del producto 2. X3: unidades diarias producidas del producto 3. Minimizar el beneficio (Z)= 3X1+2X2+5X3 (ganancia por unidad). S.a. 1X1+2X2+1X3 430 3X1+0X2+2X3 460 1X1+4X2+0X3 420 X1 0, X2 0, X3 0 Determinar la produccion diaria optima para los 3 productos. Sea: X1: El número de acres de la granja 1 aplicado al cultivo de remolacha. X2: El número de acres de la granja 2 aplicado al cultivo de remolacha.
X3: El número de acres de la granja 3 aplicado al cultivo de remolacha. X4: El número de acres de la granja 1 aplicado al cultivo de algodón. X5: El número de acres de la granja 2 aplicado al cultivo de algodón. X6: El número de acres de la granja 3 aplicado al cultivo de algodón. X7: El número de acres de la granja 1 aplicado al cultivo de sorgo. X8: El número de acres de la granja 2 aplicado al cultivo de sorgo. X9: El número de acres de la granja 3 aplicado al cultivo de sorgo. Maximizar Z=400 (X1+X2+X3)+300(X4+X5+X6)+100(X7+X8+X9) S.a. las restricciones son disponibilidad de agua y total de acres para cada cosecha. Terreno disponible X1+X4+X7 400 (GRANJA 1) X2+X5+X8 600 (GRANJA 2) X3+X6+X9 300 (GRANJA 3) Disponibilidad de agua 3X1+2X4+X7 600 (GRANJA 1) 3X2+2X5+X8 800 (GRANJA 2) 3X3+2X6+X9 375 (GRANJA 3) Total de acres para cada cosecha X1+X2+X3 600 (REMOLACHA) X4+X5+X6 500 (ALGODON) X7+X8+X9 325 (SORGO) Igual porción de area plantada X1+X4+X7 = X2+X5+X8 (GRANJA 1 Y 2 ) 600(X1+X4+X7) – 400(X2+X5+X8) = 0 400 600 X2+X5+X8 = X3+X6+X9 (GRANJA 2 Y 3 ) 600 300 X3+X6+X9 = X1+X4+X7 (GRANJA 3 Y 1 ) 300 400 Xj 0 , j = 1, 2, ... ,9.
METODO GRAFICO
SOLUCIÓN GRÁFICA DE PROBLEMAS DE PROGRAMACIÓN LINEAL
Muchos problemas de administración y economía están relacionados con la optimización (maximización o minimización) de una función sujeta a un sistema de igualdades o desigualdades. La función por optimizar es la función objetivo. Las funciones de ganancia y de costo son ejemplos de funciones objetivo. El sistema de igualdades o desigualdades a las que está sujeta la función objetivo reflejan las restricciones (por ejemplo, las limitaciones sobre recursos como materiales y mano de obra) impuestas a la solución (o soluciones) del problema. Los problemas de esta naturaleza se llaman problemas de programación matemática. En particular, aquellas donde la función objetivo y las restricciones se expresan como ecuaciones o desigualdades lineales se llaman problemas de programación lineal.
Un problema de programación lineal
Un problema de programación lineal consta de una funci´n objetivo lineal por maximizar o minimizar, sujeta a ciertas restricciones en la forma de igualdades o desigualdades lineales.
Como ejemplo de un problema de programación lineal en que la función objetivo debe maximizarse, considerese el siguiente problema de producción con dos variables
El granjero Lopez tiene 480 hectáreas en la que se puede sembrar ya sea trigo o maíz. El calcula que tiene 800 horas de trabajo disponible durante la estación crucial del verano. Dados márgenes de utilidad y los requerimientos laborales mostrados a la derecha, ¿Cuántas hectáreas de cada uno debe plantar para maximizar su utilidad?¿Cuál es ésta utilidad máxima?
Maiz: Utilidad: $40 por hrs.Trabajo: 2hs por hrs.Trigo: Utilidad: $30 por hrs.Trabajo: 1hs por hrs.
Solución: Como primer paso para la formulación matemática de este problema, se tabula la información dada (Tabla 1). Si llamamos x a las hectáreas de maíz e y a las hectáreas de trigo. Entonces la ganancia total P, en dólares, está dada por:
P=40x+30y
Que es la función objetivo por maximizar.
Maíz TrigoElementos disponibles
Horas 2 1
Hectáreas 1 1 800
Utilidad por unidad $40 $30 480La cantidad total de tiempo par hectáreas para sembrar maíz y trigo está dada por
2x+y horas que no debe exceder las 800 horas disponibles para el trabajo. Así se tiene la desigualdad:
2x+y<800 En forma análoga, la cantidad de hectáreas disponibles está dada por x+y, y ésta no puede exceder las hectáreas disponibles para el trabajo, lo que conduce a la desigualdad. Por último, si no queremos tener pérdidas, x y y no pueden ser negativa, de modo que
x>0 y>0
En resumen, el problema en cuestión consiste en maximizar la función objetivo P=40x+30y sujeta a las desigualdades
2x+y<800 x+y<480
x>0 y>0
Solución GráficaLos problemas de programación lineal en dos variables tienen interpretaciones
geométricas relativamente sencillas; por ejemplo, el sistema de restricciones lineales asociado con un problema de programación lineal bidimensional- si no es inconsistente- define una región plana cuya frontera está formada por segmentos de recta o semirrectas, por lo tanto es posible analizar tales problemas en forma gráfica.
Si consideremos el problema del granjero López, es decir, de maximizar P = 40x+ 30y sujeta a
2x+y<800 x+y<480
x>0, y>0 (7) El sistema de desigualdades (7) define la región plana S que aparece en la figura
5. Cada punto de S es un candidato para resolver este problema y se conoce
como solución factible. El conjunto S se conoce como conjunto factible. El objetivo es encontrar – entre todos los puntos del conjunto S- el punto o los puntos que
optimicen la función objetivo P. Tal solución factible es una solución óptima y constituyen la solución del problema de programación lineal en cuestión.
Como ya se ha observado, cada punto P(x,y) en S es un candidato para la solución óptima del problema en cuestión, por ejemplo, es fácil ver que el punto (200, 150) está en S y, por lo tanto, entra en la competencia. El valor de la función objetivo P en el punto (200,150) está dado por P=40(200)+30(150)=12.500 . Ahora si se pudiera calcular el valor de P correspondiente a cada punto de S, entonces el punto (o los puntos) en S que proporcione el valor máximo de P formará el conjunto solución buscado. Por desgracia, en la mayoría de los problemas, la cantidad de candidatos es demasiado grande o, como en este problema, es infinita. Así este método no es adecuado.
Es mejor cambiar de punto de vista: en vez de buscar el valor de la función objetivo P en un punto factible, se asignará un valor a la función P y se buscarán los puntos factibles que correspondieran a un valor dado de P. Para esto supóngase que se asigna a P el valor 6000. Entonces la función objetivo se convierte en 40x+ 30y = 6.000,una ecuación lineal en x e y; por lo tanto, tiene como gráfica una línea recta L1 en el plano.
Está claro que a cada punto del segmento de recta dado por la intersección de la línea recta L1 y el conjunto factible S corresponde el valor dado 6000 de P. Al repetir el proceso, pero ahora asignando a P el valor de 12.000, se obtiene la ecuación 40x+ 30y =12.000 y la recta L2 lo cual sugiere que existen puntos factibles que corresponden a un valor mayor de P. Obsérvese que la recta L2 es paralela a L1, pues ambas tienen una pendiente igual a –4/3. Esto se comprueba con facilidad escribiendo las ecuaciones en explícita de la recta.
En general, al asignar diversos valores a la función objetivo, se obtiene una familia de rectas paralelas, cada una con pendiente igual a –4/3. Además, una recta correspondiente a un valor mayor de P está más alejada del origen que una recta con un valor menor de P. El significado es claro. Para obtener las soluciones óptimas de este problema, se encuentra la recta perteneciente a esta familia que se encuentra más lejos del origen y que interseque al conjunto factible S. La recta requerida es aquella que pasa por el punto P(320,160) (Fig. 6), de modo que la solución de este problema está dado por x=320, y=160 ( es decir que el granjero López deberá sembrar 320 hectáreas de maíz y 160 hectáreas de trigo), lo que produce el valor máximo P=40(320)+30(160)=17.600.
No es casualidad que la solución óptima de este problema aparezca como vértice del conjunto factible S. De hecho, el resultado es consecuencia del siguiente teorema básico de la programación lineal, que se enuncia sin demostración.
Teorema 1 Si en problema de programación lineal tiene una solución, entonces ésta debe aparecer en un vértice, o esquina, del conjunto factible S asociado con el problema. Además, si la función objetivo dos vértices adyacente de S, entonces se optimiza en todos los puntos del segmento de recta que une estos vértices, en cuyo caso existe una infinidad de soluciones al problema
En nuestro ejemplo los únicos vértice del conjunto factible S son los puntos coordenados: (0,0); (400,0); (320,160); (0,480), llamados también puntos esquinas (Fig. 6).
Un ejemplo en el que tendríamos infinitas soluciones, es:
VERTICE P=40x+40y
(0,0) 0Supóngase que la utilidad por hectáreas es de $40 para ambos, maíz y trigo. La tabla para este caso muestra la misma utilidad total en los vértices(0,480) y (320,160). Esto significa
(0,480) 19.200
(320,160) 19.200
(400,0) 16.000
que la línea de utilidad en movimiento abandona la región sombreada por el lado determinado por esos vértices (adyacentes) , así todo punto en ese lado da una utilidad máxima. Todavía es válido, sin embargo, que la utilidad máxima ocurre en un vértice.
El teorema 1 dice que la búsqueda de las soluciones a un problema de programación lineal se puede restringir al examen del conjunto de vértices del conjunto factible S relacionado con el problema. Como un conjunto factible S tiene un número finito de vértices, el teorema sugiere que las soluciones a un problema de programación lineal se puedan hallar inspeccionando los valores de la función objetivo P en los vértices.
Aunque el teorema 1 arroja un poco de luz acerca de la naturaleza de la solución de un problema de programación lineal, no indica cuándo tiene solución. El siguiente teorema establece ciertas condiciones que garantizan la existencia de la solución de un problema de programación lineal.
Teorema 2: Existencia de una solución
Supóngase un problema de programación lineal con un conjunto factible S y una función objetivo P = ax + by. 1. Si S está acotado, entonces P tiene u valor máximo y n valor mínimo en S. 2. Si S no está acotado y tanto a como b son no negativos, entonces P tiene un valor mínimo en S, si las restricciones que definen a S incluyen las desigualdades x ³ 0 e y ³ 0. 3. Si S es el conjunto vacío, entonces el problema de programación lineal no tiene solución; es decir, P no tiene un valor máximo ni uno mínimo
El método utilizado para resolver el problema del granjero López recibe el nombre de método de las esquinas. Este método sigue un procedimiento muy sencillo para resolver los problemas de programación lineal basado en el teorema1.
Método de las esquinas
1. Se grafica el conjunto factible. 2. Se encuentran las coordenadas de todas las esquinas (vértices) del conjunto factible.3. Se evalúa la función objetivo en cada esquina. 4. Se halla el vértice que proporcione el máximo (mínimo) de la función objetivo. Si sólo existe un vértice con esta propiedad, entonces constituye una solución única del problema. Si la función objetivo se maximiza (minimiza) en dos esquinas adyacentes de S, entonces existe una infinidad de soluciones óptimas dadas por los puntos del segmento de recta determinado por estos dos vértices.
Aplicaremos los conceptos antes emitidos al siguiente problema de nutrición, basado en los requerimientos, en el cual hay que minimizar la función objetivo.
Un nutricionista asesora a un individuo que sufre una deficiencia de hierro y vitamina B, y le indica que debe ingerir al menos 2400 mg de vitamina B-1 (tiamina) y 1500 mg de vitamina B-2 (riboflavina) durante cierto período de tiempo. Existen dos píldoras de vitaminas disponibles, la marca A y la marca B. Cada píldora de la marca A contiene 40 mg de hierro, 10 mg de vitamina B-1, 5 mg de vitamina B-2 y cuesta 6 centavos. Cada píldora de la marca B contiene 10 mg de hierro, 15 mg de vitamina B-1 y de vitamina B-2, y cuesta 8 centavos (tabla 2). ¿Cuáles combinaciones de píldoras debe comprar el paciente para cubrir sus requerimientos de hierro y vitamina al menor costo?
Marca A Marca B
Requerimientos mínimos
Hierro 40 mg 10 mg 2400 mg
Vitamina B-1 10 mg 15 mg 2100 mg
Vitamina B-2 5 mg 15 mg 1500 mg
Costo por píldora (US$)
0,06 0,08
Solución: Sea x el número de píldoras de la marca A e y el número de píldoras de la marca B por comprar. El costo C, medido en centavos, está dado por
C = 6x+ 8y que representa la función objetivo por minimizar.
La cantidad de hierro contenida en x píldoras de la marca A e y el número de píldoras de la marca B está dada por 40x+10y mg, y esto debe ser mayor o igual a 2400 mg. Esto se traduce en la desigualdad.
40x+10y>2400 Consideraciones similares con los requisitos mínimos de vitaminas B-1 y B-2
conducen a las desigualdades: 10x+15y>2100 5x+15y>1500
respectivamente. Así el problema en este caso consiste en minimizar C=6x+8y sujeta a
40x+10y>2400 10x+15y>2100 5x+15y>1500
x>0, y>0 El conjunto factible S definido por el sistema de restricciones aparece en la figura. Los vértices del conjunto factible S son A(0,240); B(30,120); C(120; 60) y D(300,0).
Los valores de la función objetivo C en estos vértices en la tabla que sigue
Vertice C=6x + 8y
A (0,240) 1920
B(30,120) 1140
C(120,60) 1200
D(300,0) 1800La tabla muestra que el mínimo de la función objetivo C=6x+8y ocurre en el vértice
B(30,120) y tiene un valor de 1140. Así el paciente debe adquirir 30 píldoras de la marca A y 120 de la marca B, con un costo mínimo de $11,40.
El método de las esquinas es de particular utilidad para resolver problemas de programación lineal en dos variables con un número pequeño de restricciones, como han demostrado los ejemplos anteriores, sin embargo su efectividad decrece con rapidez cuando el número de variables o de restricciones aumenta. Por ejemplo, se puede mostrar que un ejemplo de programación lineal en tres variables y cinco restricciones puede tener hasta diez esquinas factibles. La determinación de las esquinas factibles requiere resolver 10 sistemas 3x3 de ecuaciones lineales y luego comprobar que cada uno es un punto factible, sustituyendo cada una de estas soluciones en el sistema de restricciones. Cuando el número de variables y de restricciones aumenta a cinco y diez, respectivamente (que aún es un sistema pequeño desde el punto de vista de las aplicaciones en economía), la cantidad de vértice por hallar y comprobar como esquinas factibles aumenta hasta 252, y cada uno de estos vértices se encuentra resolviendo el sistema lineal ...¡de 5x5! Por esta razón, el método de las esquinas se utiliza con poca frecuencia para resolver problemas de programación lineal, su valor reside en que permite tener una mejor idea acerca de la naturaleza de las soluciones a los problemas de programación lineal a través de su uso en la solución de problemas de dos variables.
FUENTE: http://www.investigacion-operaciones.com/Solucion_Grafica.htm
Método gráfico.
Supóngase el usuario, que por un momento es dueño de una planta que produce únicamente dos tipos de cerveza: clara y obscura, Existen tecnologías bastantes
para la elaboración de cada uno de los tipos de cerveza, obviamente cada tecnología a un costo diferente.
El usuario no sabe cuál cual deba ser su producción óptima semanal de cada producto, y por lo tanto se decide a identificar dos variables de decisión.
X1: miles de litros de cerveza clara a producir en una semana.
X2: miles de litros de cerveza obscura a producir en una semana.
El precio al mayoreo de 1 000 litros de cerveza clara es de $ 5 000.00 mientras que el precio al mayoreo de 1 000 litros de cerveza obscura es de $ 3 000.00.
El ingreso semanal de la venta de ambos productos sería:
Z = 5000 X1 +3000 X2
Si el objetivo del usuario, como el de cualquier industrial, es el de maximizar los ingresos semanales, produciría un gran volumen de X1 y X2 Cuán grande? Por ejemplo, si produce y vende 100 000 litros de cerveza clara 100 000 litros de cerveza obscura en un a semana, un ingreso sería de
Z = 5000(100) +3000(100) = 800000.
Recuerde que las unidades son el miles de litros y por eso es necesario dividir la producción semanal entre 1000.
Para maximizar Z se debe incrementar X1 y X2 . Desgraciadamente hay restricciones físicas en el sistema real de producción que le impiden al dueño de la planta incrementar arbitrariamente la producción de X1 y X2. Entre otras restricciones se pueden mencionar las siguientes: espacio de almacenamiento, capacidad de producción, capital, mano de obra, etc.
Para facilidad de explicación, solo se usarán 2 restricciones:
Restricciones de mano de obra.
Restricciones de costos de producción.
Un estudio de tiempos y movimientos ha demostrado que para producir 1000 litros de cerveza clara se requiere un total de 3 obreros en el proceso de producción. En cambio se requieren 5 obreros para producir 1000 litros de cerveza obscura. Se supone que la planta tiene un total de 15 obreros. Esto quiere decir que la producción de X1 y X2 depende del número disponible de obreros. Esto puede representarse por la siguiente desigualdad:
La desigualdad (2.2) dice que la cantidad de obreros utilizados en la producción semanal de X1 y X2 no puede exceder de 15. Producir 100 000 litros de cerveza clara y 100 000 litros de cerveza obscura utilizarían 800 obreros, que exceden al límite disponible.
Se supone que producir 1000 litros de cerveza clara le cuestan al dueño de la plana $500.00, mientras que 1000 litros de cerveza obscura le cuestan solamente $200.00. Su capital no le permite gastar más de $1000.00 semanales en al producción de X1 y X2 . Matemáticamente esta restricción puede expresarse así:
Cuyas dimensiones, son pesos. De nuevo la producción de 100000 litros de X1 y X2 significarían un gasto semanal de $ 70000.00 que excede al límite de 1000.
La pregunta a la que el dueño desea una solución es la siguiente: Cuales deben ser los niveles de producción semanal de cerveza clara X1 y de cerveza obscura X2 que maximicen el ingreso por concepto de venta semanal, sin exceder las restricciones de personal y de capital?
Matemáticamente se trata de resolver el siguiente problema, llamado de programación lineal
Maximizar
Z = 5000X1 +3000X2
Sujeto a
3X1 + 5X2 <= 15500X1 + 200X2 <= 1000
X1 >=0, X2>=0
La última restricción (X1 >= 0, X2 > = 0), se llama condición de no – negatividad, y evita que los resultados den un absurdo negativo, que en este caso podría significar una producción negativa (destrucción).
En un sistema de coordenadas rectangulares se puede describir gráficamente, como el dueño de la planta puede resolver optimamente su programa de producción semanal. Un eje del sistema medirá la cantidad de cerveza clara X1 y X2 deben ser no – negativas, se refiere únicamente al cuadrante derecho del sistema coordenado.
A continuación se interpreta la representación geométrica de las desigualdades
3X1 + 5 X2 < = 15500X1+200X2 <= 1000
Si por el momento se considera a estas desigualdades como igualdades, se tiene
3X1 + 5 X2 = 15500X1+200X2 = 1000
o lo que es lo mismo
X2 = 3 – (3/5)X1
X2 Cerv.Obscura
Img21_1X2 = 5 – (5/2)X1
Si arbitrariamente se le da valores a X1 se obtiene el correspondiente valor de X2 en ambas rectas. Un par de valores arbitrarios de X1 generarían 2 puntos, que unidos dan la recta en cuestión. Se dan a X1 el valor cero en ambas rectas, y los valores cinco y dos a X2 respectivamente. La tabla a continuación da el valor de X2:
Recta X2 = 3 – (3/5) X1 Recta X2 = 5 – (5/2)X2
Valor Arbitrario de X1
Valor Computado de X2
Valor arbitrario de X1
Valor Computado de X2
0 3 0 5
5 0 2 0
Cualquier punto (X1,X2) satisface la restricción 5X1+2X2 < = 10 en las zonas sombreadas, mientras que en la zona blanca de la misma figura viola la restricción.
Los puntos (X1,X2) contenidos dentro del área sombreada, son los únicos que satisfacen las restricciones laborales, de capital y de no – negatividad, simultáneamente. El industrial tiene que buscar dentro de esa infinidad de puntos, cuáles son los que producen la mejor utilidad Z. Por ejemplo un punto A, donde X1=0 y X2=0, satisface todas las restricciones y no – negatividad como se muestra a continuación:
3(0) + 5(0) = 0 <= 15
500(0)+200(0) = 0 <= 1000
pero produce una utilidad de Z = 5000(0) +3000(0) = 0.
El punto B donde se producirían X1 = 1000 litros de cerveza clara y X2= 1000 litros de cerveza obscura, también satisface todas las restricciones
3(1) + 5(1) = 8 <= 15
500(1)+200(1) = 700 <= 1000
1 >= 0, 1>=0
y produce una utilidad de Z = 5000(1) +3000(1) = 8000 pesos, que es una utilidad mucho mejor que la obtenida en el punto A. El punto C donde se producirían X1=3000 litros de cerveza clara y X2=3000 litros de cerveza obscura generarían una utilidad de Z = 5000(3) +3000(3) = 24000 pesos.
Que es una utilidad mucho mejor que la producida por los puntos A y B. Sin embargo, la producción del punto C viola las restricciones de personal y de capital. La primera porque utiliza 24 personas, cuando el máximo permisible son 15,
3(3) +5(3) = 24 no es menor o igual que 15,
mientras que la segunda, porque se están utilizando 2100 pesos, cuando el máximo permisible son 1000,
500(3) +200(3) = 2100 no es menor o igual que 1000.
Esta región sombreada lleva el nombre de región de factibilidad.
A continuación se verá cómo puede obtenerse gráficamente el punto (X1,X2) que da el nivel de la producción, que satisfaciendo ambas restricciones proporciona la utilidad óptima.
La función de utilidad se expresa como
Z = 5000 X1 +3000 X2
Supóngase que Z es igual a 15000. Esto implica
15000 = 5000 X1 +3000 X2 o sea
X2 = 5 – (5/3) X1.
Dándole a X1 valores arbitrarios de 0 y 3, se obtiene respectivamente valores de X2 iguales a 5 y 0. Al unir los puntos (0,5) y (3,0) con una recta, se obtendrá el lugar geométrico de todos los puntos (X1,X2) que satisfacen la recta.
Gráficamente se obtiene:
15000 = 5000 X1 + 3000 X2
Haciendo Z ahora igual a 10000, se obtiene una recta paralela a la anterior pero desplazada un poco hacia abajo. De la misma manera con una Z = 30000 se obtendría otra recta paralela a las dos anteriores, pero desplazada un poco hacia arriba. Gráficamente se tiene
A estas alturas se puede afirmar que si se desplaza la recta hacia abajo, el valor de Z disminuye, mientras que un desplazamiento hacia arriba aumentaría el valor de Z. LA pregunta del usuario que debe responder se cuál es el máximo desplazamiento hacia arriba, que proporciona el mayor valor Z, y cuya correspondiente producción no viole las restricciones de personal y capital. Un momento de reflexión observando la figura se convencerá que el punto 0 de coordenadas (X1
*,X2*) , es el punto buscado.
En este ejemplo, ese punto es el siguiente:
X1* = 1053 litros de cerveza clara
X2* = 2368 litros de cerveza obscura,
Que generan una utilidad óptima de
Z* = 5000(1.053) +3000(2.368) = 12369 pesos.
FORMAS ESTANDAR Y CANONICA
En el desarrollo que a continuación se presenta se usa la siguiente forma de la programación lineal, denominada forma canónica. Máx Z = cX Sujeto a
Cualquier otra forma es equivalente a la anterior. Esta equivalencia se prueba fácilmente por medio del uso de cualquiera de las siguientes 5 reglas. Regla 1
Maximizar cX es equivalente a Minimizar –cX Minimizar cX es equivalente a Maximizar –cX
Ejemplo:
a) es equivalente a
Es equivalente a
Regla 2 a. La desigualdad es equivalente a la desigualdad - .
b. La desigualdad es equivalente a la desigualdad - .
Ejemplo:
es equivalente a
es equivalente a
Regla 3 Toda igualdad de la forma , puede descomponerse como la intersección de dos desigualdades y Ejemplo:
es equivalente a
Regla 4 Toda desigualdad de la forma puede convertirse en igualdad mediante la adición de un vector Y, llamado de holgura. El vector columna Y tiene m componentes, todas ellas no negativas, es decir
Toda desigualdad de la forma puede convertirse en igualdad mediante la resta de un vector Z, llamado superfluo. El vector columna Z, tiene m componentes, todas no – negativas, es decir:
Ejemplo:
a) es equivalente a
Donde el vector de holgura es
b) es equivalente a
Donde el vector de exceso o superfluo es
Regla 5 Una variable no restringida, o sea aquella que puede tomar toda clase de valores positivos, cero y negativos puede escribirse como la diferencia de dos variables no – negativas.
METODO DE LA M
Método de la “M” o de Penalización.
Hasta este momento se han presentado los detalles del método símplex con la
suposición de que el problema se encuentra en nuestra forma estándar (maximizar Z
sujeta a las restricciones funcionales de la forma y restricciones de no negatividad
sobre todas las variables) con bi 0 para toda i = 1, 2, ..., m. En esta sección se
establecerá cómo hacer los ajustes requeridos a otras formas legítimas de modelos de
Programación Lineal. Se verá que todos estos ajustes se pueden hacer en el paso inicial, de
manera que el resto del método símplex se aplica justo como se aprendió.
El único problema serio que introducen las otras formas de restricciones funcionales
(= ó ) es identificar una solución inicial básica factible. Antes, esta solución inicial se
encontraba en forma muy conveniente al hacer que las variables de holgura fueran las
variables básicas iniciales, donde cada una era igual a la constante no negativa del lado
derecho de la ecuación correspondiente. Ahora debe hacerse algo más. El enfoque estándar
que se utiliza es estos casos es la técnica de variables artificiales. Ésta construye un
problema artificial más conveniente introduciendo una variable ficticia (llamada variable
artificial) en cada restricción que lo requiera. Esta nueva variable se introduce sólo con el
fin de que sea la variable básica inicial para esa ecuación. Las restricciones usuales de no
negatividad también se aplican sobre estas variables y la función objetivo se modifica para
que imponga una penalización exorbitante en el caso de que adquieran valores mayores
que cero. Las iteraciones del método símplex automáticamente fuerzan a las variables
artificiales a desaparecer (a volverse cero) una a una, hasta que todas quedan fuera de la
solución; después de esto se resuelve el problema real.
Para ilustrar la técnica de las variables artificiales, primero se considerará el caso en
que la única forma no estándar en el problema es la presencia de una o más restricciones en
forma de igualdad.
Restricciones en forma de igualdad.
En realidad, cualquier restricción en forma de igualdad:
ai1x1 +ai2x2 + . . . + ainxn = bi
es equivalente a dos restricciones de desigualdad:
ai1x1 + ai2x2 + . . . + ainxn bi,
ai1x1 + ai2x2 + . . . + ainxn bi
Sin embargo, en lugar de hacer esta sustitución e incrementar con ello el número de
restricciones, es más conveniente usar la técnica de la variable artificial. Suponga que se
modifica el problema de ejemplo presentado y resuelto en la sección anterior. El único
cambio que sufre el modelo de programación lineal es que la tercera restricción, 3x 1 + 2x2
18, se convierte en una restricción de igualdad:
3x1 + 2x2 = 18
Aplicando la técnica de las variables artificiales se introduce una variable artificial
no negativa (denotada por x5) en la última ecuación, como si fuera una variable de
holgura:
3x1 + 2x2 + x5 =18
En resumen si tenemos una restricción funcional en forma de igualdad y deseamos
“pasarla a su forma de igualdad”, únicamente debemos sumar una variable artificial.
Restricciones funcionales de la forma
Para ilustrar la manera en que la técnica de las variables artificiales maneja las
restricciones de la forma usaremos el siguiente ejemplo:
Minimizar Z = 0.4x1 + 0.5x2 sujeta a 0.3x1 + 0.1x2 2.7 0.5x1 + 0.5x2 = 6 0.6x1 + 0.4x2 6 x1
0, x2 0
Notemos que la tercera restricción es del tipo , por lo que para cambiarla a su
forma de igualdad tendríamos que restar una variable de superávit (o de excedente),
quedando de la siguiente manera:
0.6x1 + 0.4x2 x5 = 6
Se ha restado la variable de excedente x5 (se utilizó x5 porque en la primera
restricción agregamos una variable de holgura que sería x3 y en la segunda restricción
agregamos también una variable artificial que sería x4; todo esto con el fin de convertir las
desigualdades a su forma de igualdades) para que consuma el exceso de 0.6x1 + 0.4x2, o
sea, lo que se pasa de 6. No obstante en este caso debe agregarse otra variable. Esta variable
extra, llamada variable artificial se aumenta como sigue:
0.6x1 + 0.4x2 x5 + x6 = 6
La razón de esto es que, si no se agrega la variable artificial, no se estarían
cumpliendo las restricciones de no negatividad. Para comprenderlo, se dejará sin aumentar.
El método símplex comienza por hacer todas las variables reales (originales) iguales a cero.
Entonces:
0.6x1 + 0.4x2 x5 = 6
Sea x1 = 0 y x2 = 0, entonces:
x5 = 6
ó x5 = 6 (que no cumple la restricción de
no negatividad)
La variable artificial opera para mantener todas las variables no negativas cuando
0.6x1 + 0.4x2 es menor que 6. Si x1 = 0 y x2 = 0, entonces x5 = 0 y
0.6x1 + 0.4x2 x5 + x6 = 6
x6 = 6
En resumen, una restricción de la forma se convierte a su forma de igualdad restando una variable de excedente y sumando una variable artificial.
Consideremos el siguiente problema:
Maximizar Z = 3x1 + 5x2 sujeta a x1 4 2x2 12 3x1 + 2x2 = 18 x1
0, x2 0
Como explicamos anteriormente, para resolver este problema, debemos construir un problema artificial que tiene la misma solución óptima que el problema real, haciendo dos modificaciones a este problema real.
1. Se aplica la técnica de las variables artificiales introduciendo una variable artificial
no negativa (denotada por x5) en la última ecuación, como si fuera una variable de
holgura:
3x1 + 2x2 + x5 =18
2. Se asigna una penalización enorme al hecho de tener x5 0, cambiando la función
objetivo
Z = 3x1 + 5x2 a:
Z = 3x1 + 5x2 Mx5,
donde M simbólicamente representa un número positivo muy grande. Este método que
fuerza a x5 hasta el nivel de x5 = 0 en la solución óptima se llama método de la M.
Nota: Para el caso de minimización, penalizamos a la variable artificial, haciéndola
aparecer en la función objetivo con un coeficiente de +M.
Ahora se encuentra la solución óptima para el problema real aplicando el método símplex al problema artificial.
Como x5 juega el papel de la variable de holgura en la tercera restricción del
problema artificial, esta restricción es equivalente a 3x1 + 2x2 18.
En particular, el sistema de ecuaciones después de aumentar el problema artificial
(en otras palabras, pasarlo a su forma de igualdades) es:
Maximizar Z,
sujeta a
Z 3x1 5x2 + Mx5 = 0 x1 + x3 = 4 2x2 + x4 = 12
3x1 + 2x2 + x5 = 18
xj 0 Para j = 1, 2, …, 5
En este momento estamos preparados para pasar los coeficientes a la tabla símplex:
VariableBásica
Z
x1
x2
x3
x4
x5
Ladoderecho
Cociente
¿Es óptima?
Z 1 –3 –5 0 0 M 0 x3 0 1 0 1 0 0 4 x4 0 0 2 0 1 0 12 x5 0 3 2 0 0 1 18
Esta tabla todavía no está en la forma apropiada porque el coeficiente de x5 es
diferente de cero en la ecuación de Z (es M). Por lo tanto, antes de que el método símplex
pueda aplicar la prueba de optimalidad y encontrar la variable básica entrante, debe pasarse
esta tabla a la forma apropiada para que cumpla la condición símplex. Esta condición que
debe cumplir toda tabla del método símplex para que pueda reportarnos la siguiente
solución básica factible dice que: “Toda variable básica debe tener un 1 en la intersección
de su renglón y columna correspondiente y cero en los demás renglones incluido el renglón
de Z”, en otras palabras, que toda variable que sea básica solamente debe aparecer en el
renglón de la restricción que representa. Para hacer cero el coeficiente M, utilizamos el
renglón de x5 como renglón pivote multiplicándolo por M y sumando el resultado al
renglón de Z. Realizando el procedimiento anterior, la tabla símplex queda de la siguiente
manera:
VariableBásica
Z
x1
x2
x3
x4
x5
Ladoderecho
Cociente
¿Es óptima?
Z 1 -3M-3
-2M-5
0 0 0 18M Mx5 + Z
x3 0 1 0 1 0 0 4 (0, 0, 4, 12, 18)x4 0 0 2 0 1 0 12 Z = 18Mx5 0 3 2 0 0 1 18
Podemos observar que la tabla anterior ya se encuentra en la forma apropiada y
podemos leer la solución básica factible actual, que es (0, 0, 4, 12, 18), la cual aplicando la
prueba de optimalidad vemos que no es óptima ya que todavía tenemos coeficientes
negativos en el renglón de Z (los correspondientes a x1 y x2). Aplicando el método símplex
a la tabla anterior tenemos: el coeficiente negativo con el mayor valor absoluto corresponde
a x1 (3M3), recordemos que M es un número muy grande positivo, por lo tanto, x1 se
convierte en la variable básica entrante, realizando los cocientes correspondientes, vemos
que x3 se convierte en la variable básica saliente. El procedimiento completo para resolver
este ejemplo se muestra en el siguiente conjunto de tablas:
VariableBásica
Z
x1
x2
x3
x4
x5
Ladoderecho
Cociente
¿Es óptima?
Z 1 -3M-3 -2M-5 0 0 0 18M x3 0 1 0 1 0 0 4 4/1 = 4 (0, 0, 4, 12, 18)
x4 0 0 2 0 1 0 12 Z = 18M
x5 0 3 2 0 0 1 18 18/3 = 6
Z 1 0 -2M-5 3M+3 0 0 6M+12 x1 0 1 0 1 0 0 4 (4, 0, 0, 12, 6)
x4 0 0 2 0 1 0 12 12/2 = 6 Z = 6M+12
x5 0 0 2 3 0 1 6 6/2 = 3
Z 1 0 0 9/2 0 M+5/2 27 x1 0 1 0 1 0 0 4 4/1 = 4 (4, 3, 0, 6, 0)
x4 0 0 0 3 1 1 6 6/3 = 2 Z = 27
x2 0 0 1 3/2 0 1/2 3
Z 1 0 0 0 3/2 M+1 36 x1 0 1 0 0 1/3 1/3 2 (2, 6, 2, 0, 0)
x3 0 0 0 1 1/3 1/3 2 Z = 36
x2 0 0 1 0 1/2 0 6 Óptima
MINIMIZACIÓN con el método símplex.
Una manera directa de minimizar Z con el método símplex es cambiar los roles de
los coeficientes negativos y positivos en el renglón de la función objetivo, tanto para la
prueba de optimalidad como para la parte 1 de una iteración. Se determina la variable
básica entrante mediante la elección de la variable con el coeficiente positivo menor en la
ecuación de Z. La solución básica factible actual es óptima si y sólo si todos los
coeficientes de la ecuación de la función objetivo (renglón de Z) son no positivos ( 0 ). Si
es así, el proceso termina; de otra manera, se lleva a cabo otra iteración para obtener la
nueva solución básica factible, lo que significa el cambio de una variable no básica por una
básica (parte 1) y viceversa (parte 2), y después despejar las variables de la nueva solución
(parte 3). Notemos que no se ha dicho nada con respecto a la forma de obtener la variable
básica saliente en una iteración, ya que este paso se realiza de la misma manera que cuando
se está maximizando, es decir, se escoge aquella variable básica con el menor cociente.
Ilustremos la forma de utilizar el método símplex para el caso de minimización.
Consideremos el siguiente ejemplo:
Minimizar Z = 3x1 + 8x2 sujeta a x1 + 4x2 4 x1 + 2x2 2 x1
0, x2 0
Pasando este problema a su forma de igualdades añadiendo las variables necesarias,
obtenemos lo siguiente:
Minimizar Z,
sujeta a
Z 3x1 8x2 Mx5 = 0 x1 + 4x2 + x3 = 4
x1 + 2x2 x4 + x5 = 2 xj 0 para j = 1, 2, …, 5
Utilizando el método de la M para obtener una solución óptima por el método
símplex, obtenemos el siguiente conjunto de tablas:
VariableBásica
Z
x1
x2
x3
x4
x5
Ladoderecho
Cociente
¿Es óptima?
Z 1 3 8 0 0 M 0 x3 0 1 4 1 0 0 4 x5 0 1 2 0 1 1 2
Z 1 M3 2M8 0 M 0 2M (0, 0, 4, 0, 2)x3 0 1 4 1 0 0 4 4/1 = 4 Z = 2Mx5 0 1 2 0 1 1 2 2/1 = 2
Z 1 0 2 0 3 M+3 6 (2, 0, 2, 0, 0)x3 0 0 2 1 1 1 2 Z = 6x1 0 1 2 0 1 1 2 Óptima
Notemos que la primera tabla no se encontraba en la forma apropiada para el
método símplex, ya que el coeficiente de la variable básica x5 era de M en el renglón de Z,
lo cual hacia que no se cumpliera la condición símplex.
Método de las dos Fases.
En el ejemplo presentado en la sección “Restricciones funcionales de la forma “,
recordemos la función objetivo real:
Problema real: Minimizar Z = 0.4x1 + 0.5x2
Sin embargo, el método de la M utiliza la siguiente función objetivo a través de todo
el procedimiento:
Método de la M: Minimizar Z = 0.4x1 + 0.5x2 + Mx4 + Mx6
Como los dos primeros coeficientes (0.4 y 0.5) son despreciables comparados con
M, el método de dos fases puede eliminar la M usando las siguientes dos funciones objetivo
que definen Z de manera completamente diferente:
Método de las dos fases:
Fase 1: Minimizar Z = x4 + x6 (hasta que x4 = 0 y x6 = 0).
Fase 2: Minimizar Z = 0.4x1 + 0.5x2 (con x4 = 0 y x6 = 0).
La función objetivo de la fase 1 se obtiene dividiendo la función objetivo del
método de la M entre M eliminando los términos despreciables, en otras palabras, la fase 1
consiste en la minimización de la suma de todas las variables artificiales que se introduzcan
en el problema. Como la fase 1 concluye al obtener una solución básica factible para el
problema real (aquella en la que x4 = 0 y x6 = 0), esta solución se usa como la solución
básica factible inicial para aplicar el método símplex al problema real (con su función
objetivo) en la fase 2. Antes de resolver el ejemplo de esta manera se hará un resumen de
las características generales.
Resumen del método de dos fases.
Paso inicial: Se revisan las restricciones del problema original introduciendo variables
artificiales según se necesite para obtener una solución básica factible inicial obvia para el
problema artificial.
Fase 1: uso del método símplex para resolver el problema de programación lineal:
Minimizar Z = de todas las variables artificiales, sujeta a las restricciones
revisadas.
La solución óptima que se obtiene para este problema (con Z = 0) será una solución
básica factible para el problema real.
Fase 2: se eliminan las variables artificiales (de todas formas, ahora todas valen
cero). Comenzando con la solución básica factible que se obtuvo al final de la fase 1, se usa
el método símplex para resolver el problema real.
Enseguida se resumen los problemas que deben resolverse por el método símplex en
las fases respectivas para el ejemplo.
Problema para la fase 1:
Minimizar W = x4 + x6,
sujeta a
0.3x1 + 0.1x2 + x3 = 2.70.5x1 + 0.5x2 + x4 = 60.6x1 + 0.4x2 x5 + x6 = 6
y
x10 x20 x3 x40 x50 x60
Problema para la fase 2:
Minimizar Z = 0.4x1 + 0.5x2,
sujeta a
0.3x1 + 0.1x2 + x3 = 2.70.5x1 + 0.5x2 = 60.6x1 + 0.4x2 x5 = 6
y
x10 x20 x3 x50
Las únicas diferencias entre estos dos problemas se encuentran en la función
objetivo y en la inclusión (fase 1) o exclusión (fase 2) de las variables artificiales x4 y x6.
Sin las variables artificiales, el problema para la fase 2 no tiene una solución básica factible
inicial obvia. El único propósito de resolver el problema para la fase 1 es obtener una
solución básica factible con x4 = 0 y x6 = 0 que se pueda usar como la solución básica
factible inicial para la fase 2.
Las siguientes tablas muestran el resultado de aplicar el método símplex a este
problema para la fase 1:
VariableBásica
W
x1
x2
x3
x4
x5
x6
Ladoderecho
Cociente
¿Es óptima?
W 1 0 0 0 1 0 1 0 x3 0 0.3 0.1 1 0 0 0 2.7
x4 0 0.5 0.5 0 1 0 0 6
x6 0 0.6 0.4 0 0 1 1 6
W 1 1.1 0.9 0 0 1 0 12 x3 0 0.3 0.1 1 0 0 0 2.7 2.7/0.3=9 (0,0,2.7,6,0,6)
x4 0 0.5 0.5 0 1 0 0 6 6/0.5=12 W = 12
x6 0 0.6 0.4 0 0 1 1 6 6/0.6=10
W 1 0 0.53 3.66 0 1 0 2.1 x1 0 1 0.33 3.33 0 0 0 9 9/0.33=27.2 (9,0,0,1.5,0,0.6)
x4 0 0 0.33 1.66 1 0 0 1.5 1.5/0.33=4.5 W = 2.1
x6 0 0 0.2 2 0 1 1 0.6 0.6/0.2=3
W 1 0 0 1.64 0 1.65 2.65 0.51 x1 0 1 0 6.63 0 1.65 1.65 8.01 8.01/1.65=4.8 (8.01,3,0,0.51,0,0)
x4 0 0 0 1.64 1 1.65 1.65 0.51 0.51/1.65=0.30 W = 0.51
x2 0 0 1 10 0 5 5 3
W 1 0 0 0 1 0 1 0 x1 0 1 0 5 1 0 0 7.5 (7.5,4.5,0,0,0.3,0)
x5 0 0 0 0.99 0.60 1 1 0.3 W = 0
x2 0 0 1 5.05 3 0 0 4.5 Óptima fase 1
Notemos que ya hemos obtenido una solución óptima para la fase 1 que consistió en
la minimización de la suma de todas las variables artificiales. Observemos también que la
función objetivo W terminó con un valor de cero en la última tabla, lo que indica que las
dos variables artificiales (x4 y x6) valen cero ó tienen valores recíprocos y se cancelan
mutuamente para dar cero. En nuestro caso, las dos variables artificiales valen cero ya que
no se encuentran en la columna de las variables básicas en la última tabla de la primera
fase. La segunda fase consiste en resolver el problema original utilizando como tabla inicial
de esta fase la última tabla de la primera fase pero sin considerar la columna de las
variables artificiales ya que éstas tomaron el valor de cero en la primera fase. El método
símplex aplicado a la segunda fase se muestra en el siguiente conjunto de tablas:
VariableBásica
Z
x1
x2
x3
x4
x5
x6
Ladoderecho
Cociente
¿Es óptima?
Z 1 0.4 0.5 0 0 0 0 0 x1 0 1 0 5 1 0 0 7.5 x5 0 0 0 0.99 0.60 1 1 0.3 x2 0 0 1 5.05 3 0 0 4.5
Z 1 0 0.5 2 0 3 x1 0 1 0 5 0 7.5 x5 0 0 0 0.99 1 0.3 x2 0 0 1 5.05 0 4.5
Z 1 0 0 0.52 0 5.25 x1 0 1 0 5 0 7.5 (7.5,4.5,0,0,0.3,0)x5 0 0 0 0.99 1 0.3 Z = 5.25x2 0 0 1 5.05 0 4.5 Óptima fase 2
Notemos que no fue necesario aplicar propiamente el método símplex a la primera
tabla de la segunda fase, ya que únicamente aplicando operaciones con matrices para tratar
de llevar esta tabla a la forma apropiada para el método símplex fue suficiente para resolver
el problema planteado en la segunda fase. Es necesario aclarar que no siempre ocurrirá de
esta manera, es decir, si después de dejar la tabla en la forma apropiada, es necesario
aplicar el método símplex, se debe aplicar como lo hemos estudiado.
Nota: Independientemente de que el problema original (real) sea de maximización o
minimización, la primera fase siempre consistirá en la minimización de la suma
de todas las variables artificiales.
FUENTE: http://www.investigacion-operaciones.com/Metodo_Minimizacion.htm
METODO DE LAS 2 FASES
En esencia es igual al método de penalización, en que primero se introducen las variables artificiales al problema original
Sujeto a
Quedando como
Sujeto a
Donde W es el vector de variables artificiales con componentes . En la primera fase se resuelve el problema
Sujeto a
La solución óptima de esta fase debe ser . Si al obtener las condiciones de optimalidad en esta fase, , el problema original no tiene solución. Supóngase que la primera fase es óptima, y que la base asociada a la tabla es B. En la segunda fase se aplica el método Simplex para resolver el problema Min cX Sujeto a
La solución óptima a esta segunda fase, es la solución óptima al problema original. Es importante observar que al empezar la segunda fase, todos los vectores de la base óptima correspondientes a la primera fase permanezcan unitarios. Empléense operaciones matriciales elementales para restituir todos aquellos vectores que deben ser unitarios. Ejemplo: Resuélvase por el método de doble fase el siguiente problema inicial
Sujeto a
Primero se reescribe el problema como
Sujeto a
La primera fase consiste en resolver el problema
Sujeto a
Aplicando el método simplex, una vez que se ha cambiado la función objetivo
a se tiene
1 0 0 0 0 0
A3 0 1 0 1 0 0 4
A4 0 0 1 0 1 0 6
Aw1 1 3 2 0 0 -1 18
Para tener el primer punto extremo se requiere que los vectores de la base sean
unitarios. Por lo tanto se convierte , en vector . Esta es la solución óptima de la fase uno, y como el problema original tiene solución. Para empezar la fase dos tómese todo la tabla óptima anterior,
únicamente ignorando la columna ( que ya nos e necesita) y el renglón de
los . Sustitúyase ese renglón por la función objetivo original.
O equivalentemente
Los vectores unitarios e1, e2, e3, que son respectivamente a1, a4, a2, son restaurados por medio de operaciones matriciales elementales.
En este ejemplo no es necesario seguir iterando en la fase dos, pues al restaurar los vectores unitarios correspondientes a la base de la tabla óptima de la fase uno, se obtuvieron por pura coincidencia las condiciones de
optimalidad para toda j en A. Por lo general este no será el caso y será necesario hacer varias iteraciones del método simplex en la segunda fase. La
solución óptima es la misma que la obtenida en el método gráfico y en el método de penalización, es decir :
Y h = -Z = -3 o Z = 3.
UNIDAD 2: ANALISIS DE REDES
PROBLEMA DE TRANSPORTE
La programación lineal es un campo tan amplio que se extiende a subclases de problemas para los
cuales existen métodos de solución especiales. Una de estas subclases se conoce como problemas
de transporte. El método símplex de programación lineal, puede servir para resolver estos
problemas. Pero se han desarrollado métodos más sencillos que aprovechan ciertas características
de los problemas. Entonces, el método del transporte son sólo técnicas especiales para resolver
ciertos tipos de problemas de programación lineal.
El transporte desempeña un papel importante en la economía y en las decisiones
administrativas. Con frecuencia la disponibilidad de transporte económico es crítica para la sobre-
vivencia de una empresa.
¿Qué significa problema de transporte? Supóngase que un fabricante tiene tres plantas que
producen el mismo producto. Estas plantas a su vez mandan el producto a cuatro almacenes. Cada
planta puede mandar productos a todos los almacenes, pero el costo de transporte varía con las
diferentes combinaciones. El problema es determinar la cantidad que cada planta debe mandar a
cada almacén con el fin de minimizar el costo total de transporte.
La manera más fácil de reconocer un problema de transporte es por su naturaleza o
estructura
“de-hacia”: de un origen hacia un destino, de una fuente hacia un usuario, del presente hacia el
futuro, de aquí hacia allá. Al enfrentar este tipo de problemas, la intuición dice que debe haber una
manera de obtener una solución. Se conocen las fuentes y los destinos, las capacidades y demandas
y los costos de cada trayectoria. Debe haber una combinación óptima que minimice el costo (o
maximice la ganancia). La dificultad estriba en el gran número de combinaciones posibles.
Puede formularse un problema de transporte como un problema de programación lineal y
aplicarse el método símplex. Si se hiciera, se encontraría que los problemas de transporte tienen
características matemáticas únicas. Para visualizar esto, considérese el siguiente ejemplo:
Ejemplo prototipo.
Chícharos enlatados es uno de los productos más importantes de la compañía P & T. Los
chícharos se preparan en tres enlatadoras (cercanas a Bellingham, Washington; a Eugene, Oregón y
a Albert Lea, Minnesota) y después se mandan por camión a cuatro almacenes de distribución (en
Sacramento, California; Salt Lake City, Utah; Rapid City, South Dakota y Alburquerque, New
Mexico) en el oeste de Estados Unidos. Puesto que los costos de embarque constituyen un gasto
importante, la gerencia ha iniciado un estudio para reducirlos lo más posible que se pueda. Se ha
hecho una estimación de la producción de cada enlatadora para la próxima temporada y se ha
asignado a cada almacén una cierta cantidad de la producción total de chícharos. En la siguiente
tabla se proporciona esta información (en unidades de carga de camión), junto con el costo de
transporte por camión cargado para cada combinación de enlatadora-almacén. Como se ve hay un
total de 300 cargas de camión que se deben transportar. El problema es determinar el plan de
asignación de estos embarques a las distintas combinaciones de enlatadora-almacén que minimice el
costo total de transporte.
COSTO DE EMBARQUE ($) POR CARGAAlmacén
1 2 3 4 PRODUCCIÓN1 464 513 654 867 75
Enlatadora 2 352 416 690 791 1253 995 682 388 685 100
Asignación 80 65 70 85
Este, de hecho, es un problema de programación lineal del tipo de los problemas de
transporte. Para formularlo, sea Z el costo total de transporte y sea xij (i = 1, 2, 3; j = 1, 2, 3, 4) el
número de cargas de camión que se mandan de la enlatadora i al almacén j. Entonces el objetivo es
seleccionar los valores de estas 12 variables de decisión (las xij) para:
Minimizar Z= 464x11 + 513x12 + 654x13 + 867x14 + 352x21 + 416x22 + 690x23 + 791x24
995x31 + 682x32 + 388x33 + 685x34
sujeta a las restricciones:
x11 + x12 + x13 + x14 = 75
x21 + x22 + x23 + x24 = 125
x31 + x32 + x33 + x34 = 100
x11 + x21 + x31 = 80
x12 + x22 + x32 = 65
x13 + x23 + x33 = 70
x14 + x24 + x34 = 85
xij 0 (i = 1, 2, 3; j = 1, 2, 3, 4)
La siguiente tabla muestra los coeficientes de las restricciones. Como se verá enseguida, lo que distingue a este problema como un problema de transporte es la estructura especial en el patrón de estos coeficientes, no su contexto.
Entre
paréntesis, la solución óptima para este problema es x11 = 0, x12 = 20, x13 = 0, x14 = 55,
x21 = 80, x22 = 45, x23 = 0, x24 = 0, x31 = 0, x32 = 0, x33 = 70, x34 = 30. Cuando se conozca la prueba
de optimalidad se podrá verificar este resultado.
Coeficiente de:x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34
1 1 1 11 1 1 1 Restricciones
1 1 1 1 de enlatadoraA = 1 1 1
1 1 1 Restricciones1 1 1 de almacén
1 1 1
Modelo general del problema de transporte.
Para describir el modelo general del problema de transporte es necesario emplear términos
que sean mucho menos específicos que los que se usaron para los componentes del ejemplo
prototipo. En particular, el problema general de transporte se refiere (literal o en sentido figurado) a
la distribución de cualquier bien desde cualquier grupo de centros de abastecimiento, llamados
orígenes, a cualquier grupo de centros de recepción, llamados destinos, de tal manera que se
minimicen los costos totales de distribución. La correspondencia en terminología entre el ejemplo
prototipo y el problema general se resume en la siguiente tabla:
Ejemplo prototipo Problema generalCargas de chícharos enlatados Unidades de un bienTres enlatadoras m orígenesCuatro almacenes n destinosProducción de la enlatadora i si recursos en el origen iAsignación al almacén j Demanda dj en el destino jCosto de embarque por carga
desde la enlatadora i al almacén jCosto cij por unidad distribuida
desde el origen i al destino j
Así, por lo general, el origen i (i = 1, 2, ..., m) dispone de si unidades para distribuir a los
destinos y el destino j (j = 1, 2, ..., n) tiene una demanda de dj unidades que recibe desde los
orígenes. Una suposición básica es que el costo de distribución de unidades desde el origen i al
destino j es directamente proporcional al número distribuido, donde cij denota el costo por unidad
distribuida. Igual que para el ejemplo prototipo, estos datos de entrada se pueden resumir en forma
muy conveniente en la tabla de costos y requerimientos que se muestra enseguida:
Costo por unidad distribuidaDestino
1 2 . . . n Recursos1 c11 c12 . . . c1n s1
Origen 2 c21 c22 . . . c2n s2. . . . .. . . . . . . .. . . . .
m cm1 cm2 . . . cmn sm
Demanda d1 d2 . . . dn
Sea Z el costo total de distribución y xij (i = 1, 2, ..., m; j = 1, 2,..., n) el número de unidades
que se distribuyen del origen i al destino j, la formulación de programación lineal para este
problema es:
Minimizar Z = sujeta a
yxij 0, para toda i y j
Note que la tabla que resulta de los coeficientes de las restricciones tiene la estructura
especial que se muestra en la siguiente tabla:
Coeficiente de
x11 x12 . . . x1n x21 x22 . . . x2n . . . xm1 xm2 . . . xmn
1 1 . . . 1 Restricciones
1 1 . . . 1 de origen. . .
A = 1 1 . . . 1
1 1 1 Restricciones
1 1 . . . 1 de destino. . . . . . .
. .
1 1 1
Cualquier problema de programación lineal que se ajuste a esta formulación especial es del
tipo de problemas de transporte, sin importar su contexto físico. De hecho, se han realizado
numerosas aplicaciones no relacionadas con el transporte que se ajustan a esta estructura especial.
Ésta es una de las razones por las que el problema de transporte se suele considerar como uno de los
tipos especiales de problemas de programación lineal más importantes.
Una condición necesaria y suficiente para que un problema de transporte tenga soluciones factibles es que:
Esta propiedad se puede verificar observando que las restricciones requieren que:
Esta condición de que los recursos totales deben ser iguales a la demanda total en realidad exige que
el sistema esté balanceado. Si el problema tiene algún significado físico y esta condición no se
cumple, casi siempre significa que, o bien si, o bien dj de hecho representan una cota y no un
requerimiento exacto. Si este es el caso, se puede introducir un “origen” o “destino” imaginario
(llamado origen ficticio o destino ficticio) para captar la holgura, con el fin de convertir las
desigualdades en igualdades y satisfacer la condición de factibilidad.
El problema de transporte es sólo un tipo especial de problemas de programación lineal y
puede resolverse aplicando el método símplex tal y como lo hemos estudiado. Sin embargo,
veremos que si se aprovecha la estructura especial que se muestra en la tabla anterior, se puede
lograr un importante ahorro en los cálculos. Se hará referencia a este procedimiento simplificado
como el método símplex de transporte.
Para hacer hincapié en la simplificación lograda por el método símplex de transporte, se
revisará primero la forma en que el método símplex general (no simplificado) establecería el
problema de transporte en forma tabular. Después de construir la tabla de los coeficientes de
restricción (vea la tabla anterior), de convertir la función objetivo a la forma de maximización y de
usar el método de la M para introducir las variables artificiales z1, z2, ..., zm+n en las m+n ecuaciones
de restricción respectivas, se ve que las columnas de la tabla símplex tendrían la forma que se
muestra en la siguiente tabla:
Variable Ec. Coeficiente de Ladobásica núm. Z . . . xij . . . zi . . . zm+j . . . derecho
Z (0) 1 cij M M 0(1)
.
.
.
zi (i) 0 1 1 si...
zm+j (m+j) 0 1 1 dj...
(m+n)En esta tabla, todos los elementos que no se muestran en estas columnas son ceros. El único
ajuste que queda por hacer antes de la primera iteración es eliminar algebraicamente los coeficientes
distintos de cero de las variables básicas iniciales (artificiales) en el renglón de Z (renglón 0).
Después de cualquier iteración subsecuente, el renglón 0 tendría la forma que se muestra en
la siguiente tabla:
Variable Ec. Coeficiente de Lado
básica núm Z . . . xij . . . zi . . . zm+j . . . derecho
Z (0) 1 cijuivj Mui Mvj
A causa del patrón de ceros y unos que siguen los coeficientes en la tabla anterior, u i y vj
tienen la siguiente interpretación:
ui = múltiplo del renglón i original que se ha restado (directa o indirectamente) del renglón 0
original durante todas las iteraciones del método símplex que llevaron a la tabla actual.
vj = múltiplo del renglón m+j original que se ha restado (directa o indirectamente) del renglón
0 original durante todas las iteraciones del método símplex que llevaron a la tabla actual.
El renglón 0 actual se puede obtener sin usar ningún otro renglón con sólo calcular los
valores de ui y vj directamente. Como cada variable básica debe tener coeficiente cero en el renglón
0, estos valores se pueden obtener resolviendo el sistema de ecuaciones:
cijuivj = 0 para cada i y j tal que xij es variable básica,
lo cual se puede hacer de manera directa.
Además de los datos de entrada (los valores de cij, si y dj), la única información que necesita
el método símplex de transporte es la solución básica factible actual, los valores actuales de u i y vj y
los valores resultantes de cijuivj para las variables no básicas xij. Cuando se resuelve un problema a
mano es conveniente registrar esta información en una tabla símplex de transporte, como la que
se muestra enseguida:
En los casos en que la sumatoria de todo lo que se produce en todos los orígenes es mayor
que la sumatoria de todo lo que se demanda en todos los destino o viceversa, entonces se dice que el
problema no está balanceado. En estos casos lo primero que se debe hacer antes de intentar
resolver el problema es balancearlo.
Para el caso de SOBREPRODUCCIÓN ( )
Si el caso es que se dispone de mayor producción de la que se demanda, entonces para
balancear el problema se agrega un destino imaginario o artificial (llamado también destino ficticio)
el cual tendrá como demanda dicha sobreproducción. En cuanto a los costos asociados a este nuevo
destino los estableceremos a cero (¿por qué?). El siguiente dibujo muestra lo que se debe hacer:
donde
dn+1 = y
ci,n+1 = 0, para i = 1, 2, ..., m
Para el caso de SOBREDEMANDA ( )
Si el caso es que se tiene mayor demanda de lo que se produce, entonces para balancear el
problema se agrega un origen imaginario o artificial (llamado también origen ficticio) el cual tendrá
como recursos (producirá) dicha sobredemanda. En cuanto a los costos asociados a este nuevo
origen los estableceremos a cero (¿por qué?). El siguiente dibujo muestra lo que se debe hacer:
donde
sm+1 = y
cm+1j = 0 para j = 1, 2, ..., n
Como todas las restricciones funcionales en el problema de transporte son igualdades, el
método símplex obtendría una solución inicial básica factible introduciendo variables artificiales y
usándolas como variables básicas iniciales. La solución básica que resulta de hecho sólo es factible
para la versión aumentada del problema, por lo que se necesita un buen número de iteraciones para
hacer que el valor de estas variables artificiales sea cero y se alcancen las soluciones básicas
factibles reales. El método símplex de transporte pasa por alto todo esto, pues usa un procedimiento
más sencillo para construir directamente una solución básica factible real en la tabla de transporte.
Antes de describir este procedimiento, es necesario establecer que el número de variables
básicas en cualquier solución básica de un problema de transporte es una menos de lo que se
espera. Normalmente en los problemas de programación lineal, se tiene una variable básica por cada
restricción funcional. En los problemas de transporte con m recursos y n destinos el número de
restricciones funcionales es m+n. Sin embargo,
el número de variables básicas = m + n 1.
Esto se debe a que se manejan restricciones de igualdad y este conjunto de m + n
ecuaciones tiene una ecuación adicional o (redundante) que se puede eliminar. La razón es que se
sabe que la cantidad total que se manda desde todos los orígenes debe ser igual que la cantidad total
que se recibe en todos los destinos. Por lo tanto, cualquier solución básica factible en una tabla de
transporte debe aparecer con exactamente m + n 1 asignaciones no negativas, en donde la suma de
las asignaciones en cada renglón o columna es igual a su demanda o sus recursos
4.2. Métodos para encontrar soluciones factibles.
Al iniciar, todos los renglones de los orígenes y las columnas de destinos de la tabla
símplex de transporte se toman en cuenta para proporcionar una variable básica (asignación).
1. Se selecciona la siguiente variable básica (asignación) entre los renglones y columnas en
que todavía se puede hacer una asignación de acuerdo a algún criterio.
2. Se hace una asignación lo suficientemente grande como para que use el resto de los
recursos en ese renglón o la demanda restante en esa columna (cualquiera que sea la
cantidad más pequeña).
3. Se elimina ese renglón o columna (la que tenía la cantidad más pequeña en los recursos
odemanda restantes) para las nuevas asignaciones.(Si el renglón y la columna tiene la
misma cantidad de recursos y demanda restante, entonces arbitrariamente se elimina el
renglón. La columna se usará después para proporcionar una variable básica
degenerada, es decir, una asignación con cero unidades.)
4. Si sólo queda un renglón o una columna dentro de las posibilidades, entonces el
procedimiento termina eligiendo como básicas cada una de las variables restantes (es
decir, aquellas variables que no se han elegido ni se han eliminado al quitar su renglón o
columna) asociadas con ese renglón o columna que tiene la única asignación posible. De
otra manera se regresa al paso 1.
4.2.1. Método de la esquina noroeste.
1. Regla de la esquina noroeste: la primera elección es x11 (es decir, se comienza en la
esquina noroeste de la tabla símplex de transporte). De ahí en adelante, si x ij fue la última
variable básica seleccionada, la siguiente elección es x i,j+1 (es decir, se mueve una
columna a la derecha) si quedan recursos en el origen i. De otra manera, se elige xi+1,j (es
decir, se mueve un renglón hacia abajo).
Para hacer más concreta esta descripción, se ilustrará el procedimiento general, utilizando la
regla de la esquina noroeste en el siguiente ejemplo:
Recursos5
2
3
Demanda 3 4 2 1 10 10
Lo primero que debemos hacer al resolver cualquier problema de transporte es comprobar
que esté balanceado, si no lo estuviera, agregamos un origen o un destino artificial según sea el caso
para conseguir que el problema quede balanceado y podamos comenzar a resolverlo. En nuestro
ejemplo, la sumatoria de los recursos de los tres orígenes es de 10 unidades que es igual a la
sumatoria de las demandas de los destinos, por lo que nuestro problema está balanceado y podemos
iniciar con la resolución.
Comenzamos asignando en la esquina noroeste de la tabla, es decir, en la celda
correspondiente a la variable básica x11 (paso 1), podemos observar que en la primera columna se
demandan 3 unidades del bien y en el primer renglón disponemos de 5 unidades, entonces enviamos
las 3 unidades demandadas desde el origen 1 hacia el destino 1 (ya que hay los recursos suficiente
para satisfacer toda la demanda) y decrementamos a 2 los recursos restantes en ese origen (paso 2).
Con esto cubrimos toda la demanda del primer destino (ó almacén) y lo cancelamos para las
próximas asignaciones (paso3):
Recursos
35 2
2
3
Demanda 3 0 4 2 1
La siguiente asignación será en la celda correspondiente a la variable x12 (paso 1) ya que
todavía le quedan recursos al origen 1 (además es la esquina noroeste de la tabla restante después de
haber eliminado la primera columna). Notemos que en el segundo destino se demandan 4 unidades
del bien y ahora solamente se disponen de 2 unidades en el origen 1, entonces se envían las 2
unidades del origen 1 al destino 2 para satisfacer 2 de las 4 unidades demandadas en este destino
quedando 2 por satisfacer (paso 2) y cancelamos el origen 1 ya que no tiene más unidades del bien
473 6
2324
34 8 5
473 6
232 4
34 8 5
para enviar a otro destino
(paso 3):
Recursos
3 25 2 0
2
3
Demanda 3 0 4 2 2 1
La siguiente asignación será en la celda correspondiente a la variable x22 (paso 1) ya que no
le quedan unidades del bien al origen 1 (notemos también que esa celda es la que se encuentra en la
esquina noroeste de la tabla restante después de haber eliminado el primer renglón y la primera
columna y no olvidemos que estamos aplicando la regla de la esquina noroeste). Ya que solamente
faltan 2 unidades para satisfacer por completo la demanda del segundo destino y se disponen
exactamente de 2 unidades en el segundo origen, entonces enviamos 2 unidades del bien del origen
2 al destino 2 (paso 2) y cancelamos el segundo renglón ya que no le quedan más unidades para
enviar a otro destino. Dejamos pendiente la eliminación de la segunda columna ya que nos servirá
más adelante para hacer la asignación de una variable básica degenerada, es decir, una asignación
con cero unidades (paso 3):
Recursos
3 25 2 0
22 0
3
Demanda 3 0 4 2 0 2 1
La siguiente asignación será en la celda correspondiente a la variable x 32 (paso1) ya que no le
quedan más unidades al origen 2. Notemos que “se demandan cero unidades del bien en el segundo
destino”, en este momento es cuando hacemos una asignación de cero unidades convirtiendo así a
la variable x32 en una variable básica degenerada (paso 2) y ahora sí podemos cancelar la segunda
columna para ya no considerarla más en las siguientes asignaciones (paso 3). Notemos que esta
473 6
232 4
34 8 5
473 6
232 4
34 8 5
demanda de cero unidades es satisfecha sin ningún problema por el origen 3 ya que éste dispone
todavía de 3 unidades del bien:
Recursos
3 25 2 0
22 0
03
Demanda 3 0 4 2 0 2 1
Como solamente queda un renglón dentro de las posibilidades (el renglón 3 no ha sido
cancelado), entonces aplicando el paso 4 del procedimiento general para construir una solución
inicial básica factible, la siguiente asignación será en la celda que corresponde a la variable x33
(paso 1). Ya que la demanda del tercer destino (2 unidades) puede ser satisfecha muy bien por el
tercer origen, entonces enviamos 2 unidades del bien del origen 3 al destino 3 quedando solamente
1 unidad en el tercer origen (paso 2) para enviarlo al cuarto destino y con eso cubrir su demanda de
una unidad, cancelando de esta manera tanto el destino 3 como el destino 4 y el tercer renglón ya
que la demanda de todos los destinos ya ha sido satisfecha y no quedan más unidades del bien en
ningún origen:
Recursos
3 25 2 0
22 0
0 2 13 1 0
Demanda 3 0 4 2 0 2 0 1 0Costo = 52
La solución inicial básica factible es x11=3, x12=2, x22=2, x32=0 (variable básica
degenerada), x33=2 y x34=1 y el costo total de transporte asociado a esta primera “Política de
Transporte” factible es de:
x11 c11 x12 c12 x22 c22 x32 c32 x33 c33 x34 c34
Costo = 3 (3) + 2 (7) + 2 (4) + 0 (3) + 2 (8) + 1 (5) = 52 unidades
473 6
232 4
34 8 5
473 6
232 4
34 8 5
Es necesario aclarar que esta no es la solución final del problema, es necesario aplicar a esta
primera solución factible la prueba de optimalidad ya que puede existir una mejor “política de
transporte” que minimice todavía más el costo total.
4.2.2. Método de aproximación de Vogel.
Método de Aproximación de Vogel: para cada renglón y columna que queda bajo
consideración, se calcula su diferencia, que se define como la diferencia aritmética entre el costo
unitario más pequeño (cij) y el que le sigue, de los que quedan en ese renglón o columna. (Si se
tiene un empate para el costo más pequeño de los restantes de un renglón o columna, entonces la
diferencia es 0). En el renglón o columna que tiene la mayor diferencia se elige la variable que tiene
el menor costo unitario que queda. (Los empates para la mayor de estas diferencias se pueden
romper de manera arbitraria).
Para hacer más concreta esta descripción, se ilustrará el procedimiento general, utilizando el método
de aproximación de Vogel
para resolver el ejemplo presentado anteriormente y que fue resuelto por la regla de la esquina
noroeste:
Iniciamos el método calculando las primeras diferencias para cada renglón y columna. De las
diferencias que obtuvimos nos fijamos en la mayor (¿Por qué?), que resulta ser para la tercera
columna. En esa columna encontramos el costo unitario (cij) menor y en esa celda realizamos la
primera asignación:
Recursos DIF.5 1
22 0 0
3 1
Demanda 3 4 2 0 1 10 10
DIF. 1 1 3 1 2
Nota: Marcaremos a la mayor de las diferencias seleccionada encerrándola en un círculo y escribiéndole como superíndice el número que le corresponda en la secuencia de selección.
Observemos en la figura anterior que únicamente eliminamos el segundo renglón ya que la
tercera columna nos servirá después para hacer la asignación de una variable básica degenerada.
3 6 47
2 4
3
23
54 8
Continuando con la aplicación del método, tenemos que calcular nuevamente las diferencias de las
columnas ya que hemos eliminado un renglón y ésto puede ocasionar que las diferencias aritméticas
entre el costo unitario más pequeño y el que le sigue ya no sean las mismas:
Recursos DIF.5 1
22 0 0
33 0 1
Demanda 3 4 1 2 0 1 10 10
DIF. 1 1 3 1 2
1 4 2 2 1
Como siguiente paso deberíamos calcular las nuevas diferencias de columnas, pero ya que solamente queda un renglón dentro de las posibilidades (ésto no significa que solamente un renglón quede bajo consideración ya que podemos observar que ninguna de las cuatro columnas (destinos) ha sido eliminada y todas quedan todavía bajo consideración), no es posible encontrar la diferencia aritmética entre el costo menor y el que le sigue, por lo tanto vamos tomando una a una las celdas que quedan comenzando con la de menor costo unitario hasta que todas hayan sido asignadas.
Recursos DIF.
3 1 0 15 2 1 0 1
22 0 0
33 0 1
Demanda 3 0 4 1 0 2 0 1 0 10 10
DIF. 1 1 3 1 2
1 4 2 2 1
La solución inicial básica factible es x11=3, x12=1, x13=0 (variable básica degenerada),
x14=1, x23=2 y x32=3 y el costo total de transporte asociado a esta primera “Política de Transporte”
factible es de:
x11 c11 x12 c12 x13 c13 x14 c14 x23 c23 x32 c32
Costo = 3 (3) + 1 (7) + 0 (6) + 1 (4) + 2 (3) + 3 (3) = 35 unidades
3 6 47
2 4
3
23
54 8
3 6 47
2 4
3
23
54 8
Es necesario aclarar que ésta puede o no ser la solución final del problema, es necesario
aplicar a esta primera solución factible la prueba de optimalidad ya que puede existir una mejor
“política de transporte” que minimice todavía más el costo total.
Comparación de criterios alternativos para el paso 1.
Se compararán estos dos criterios para elegir la siguiente variable básica. La virtud principal
de la regla de la esquina noroeste es la facilidad y rapidez con que se aplica. Sin embargo, como no
le da importancia a los costos unitarios cij, por lo general la solución que se obtiene distará mucho
de la óptima. Si se realiza un esfuerzo un poco mayor para encontrar la solución inicial básica
factible, es posible que se reduzca mucho el número de iteraciones que después necesita el método
símplex de transporte para encontrar la solución óptima. El objetivo del otro criterio es
precisamente encontrar una solución así.
El método de aproximación de Vogel ha sido el más popular durante muchos años, en parte
porque es relativamente fácil hacerlo a mano. Este criterio toma en cuenta los costos unitarios en
forma efectiva ya que la diferencia representa el mínimo costo adicional en que se incurre por no
hacer una asignación en la celda que tiene el menor costo en esa columna o renglón.
Podemos decir, que el método de aproximación de Vogel proporciona una mejor solución
inicial que el criterio de la esquina noroeste, en otras palabras es más cualitativo.
El siguiente paso después de hallar una solución inicial básica factible (por cualquiera de
los dos criterios expuestos anteriormente) es verificar si esta solución inicial es efectivamente
óptima aplicando la prueba de optimalidad.
La prueba de optimalidad estándar del método símplex para el problema de transporte, se
puede reducir de la siguiente manera:
Una solución básica factible es óptima si y sólo si c ijuivj 0 para toda (i,j) tal que xij es no
básica.
Así, lo único que hay que hacer para realizar esta prueba es obtener los valores de u i y vj
para la solución básica factible actual y después calcular los valores c ijuivj según se describe
enseguida.
Como el valor de cijuivj debe ser cero si xij es una variable básica, ui y vj satisfacen el
conjunto de ecuaciones:
cij = ui + vj para cada (i,j) tal que xij es básica.
Existen m+n1 variables básicas y por tanto hay m+n1 ecuaciones de este tipo. Como el número de
incógnitas (las ui y vj) es m+n, se puede asignar un valor arbitrario a cualquiera de estas variables
sin violar las ecuaciones. La elección de esta variable y su valor no afecta el valor de ningún c ijui
vj, aun cuando xij sea no básica, por lo que la única diferencia (menor) estriba en la facilidad para
resolver estas ecuaciones. Una elección conveniente para lograr esto es seleccionar la u i que tiene el
mayor número de asignaciones en su renglón (los empates se rompen de manera arbitraria) y
asignarle un valor de cero. Gracias a la sencilla estructura de estas ecuaciones, resulta muy fácil
obtener algebraicamente los valores del resto de las variables.
Para ejemplificar la prueba de optimalidad, consideremos la solución inicial básica factible
obtenida por la regla de la esquina noroeste para nuestro ejemplo en cuestión:
v1 v2 v3 v4 Recursos ui
u1
3 25
u2
22
u3
0 2 13
Demanda 3 4 2 1Costo=52
vj
Para este problema, existen m+n1=3+41=6 variables básicas, que dan origen al siguiente conjunto de ecuaciones:
3 = u1+v1
7 = u1+v2
4 = u2+v2
3 = u3+v2
8 = u3+v3
5 = u3+v4
Observemos que resultaron ser 6 ecuaciones que involucran 7 incógnitas (tres de las u i y
cuatro de las vj), por lo que este sistema de ecuaciones no es cuadrado. La forma de resolverlo es
dando un valor arbitrario a una de las incógnitas, para que, a partir de él encontremos el valor de las
demás. La regla para hacer esta asignación arbitraria nos dice que sea para la u i (ó renglón) que
haya tenido el mayor número de asignaciones. En nuestro ejemplo, el renglón 1 tuvo dos
asignaciones, el renglón 2 tuvo una asignación y por último el tercer renglón tuvo tres asignaciones,
por lo que asignamos el valor de cero a la incógnita u3. De esta asignación resulta lo siguiente:
3 = u1+v1
7 = u1+v2
73 6 4
32 4
3
2
8 54
4 = u2+v2
3 = u3+v2 ®v2 = 38 = u3+v3 ®v3 = 85 = u3+v4 ®v4 = 5
Hemos obtenido el valor de tres incógnitas más, v2, v3 y v4, los cuales nos ayudarán para
hallar el valor de las incógnitas restantes:
3 = u1+v1 si u1=4, entonces v1= 17 = u1+v2 si v2=3, entonces u1= 44 = u2+v2 si v2=3, entonces u2= 13 = u3+v2 ®v2 = 38 = u3+v3 ®v3 = 85 = u3+v4 ®v4 = 5
De esta forma hemos obtenido el valor de todas las incógnitas y procedemos a colocarlos en la tabla como sigue:
v1 v2 v3 v4 Recursos ui
u1
3 25 4
u2
22 1
u3
0 2 13 0
Demanda 3 4 2 1Costo=52
vj1 3 8 5
Ahora calculemos los valores cijuivj para las variables no básicas, ya que para las básicas,
este valor es cero (por la forma de las ecuaciones con que se hallaron los valores de las incógnitas u i
y vj), y coloquemos estos valores en la esquina inferior izquierda de cada celda:
Para la celda (1,3): 6 4 8 = 6Para la celda (1,4): 4 4 5 = 5Para la celda (2,1): 2 1 (1) = 2Para la celda (2,3): 3 1 8 = 6Para la celda (2,4): 2 1 5 = 4Para la celda (3,1): 4 0 (1) = 5
v1 v2 v3 v4 Recursos ui
u1
3 25 4
73 6 4
32 4
3
2
8 54
7
5600
3 6 4
u2
22 1
u3
0 2 13 0
Demanda 3 4 2 1Costo=52
vj1 3 8 5
En este momento se puede aplicar la prueba de optimalidad para verificar los valores de c ij
uivj obtenidos. Como cuatro de estos valores (c13u1v3= 6, c14u1v4= 5, c23u2v3= 6, c24u2v4=
4), son negativos, se concluye que la solución básica factible actual no es óptima. Entonces, el
método símplex de transporte debe proceder a hacer una iteración para encontrar una mejor
solución básica factible.
Una iteración.
Igual que para método símplex estándar, una iteración del método símplex de transporte
debe determinar una variable básica entrante (paso 1), una variable básica que sale (paso 2) y
después identificar la nueva solución básica factible que resulta (paso 3).
Paso 1: como cijuivj representa la tasa a la que cambia la función objetivo si se incrementa la
variable no básica xij, la variable que entra debe tener un valor de c ijuivj negativo, para que el costo
total Z disminuya. Entonces, los candidatos en la tabla anterior son x13, x14, x23 y x24 . Entre ellos se
elige el valor negativo más grande (en términos absolutos) de cijuivj como la variable básica
entrante, que en este caso corresponde a x13 y x23. En los casos en que haya empate para la elección
de la variable básica entrante, este empate se rompe de manera arbitraria, ya que tarde o temprano
llegaremos a la misma solución independientemente de la elección de la variable. Pero, observemos
lo siguiente: ya que debemos elegir la variable básica “entrante, es decir, aquella que comenzará a
tener un valor (ya que antes no lo tenía porque era variable no básica), entonces, es conveniente que
elijamos aquella que tenga el costo menor, ya que el valor de la variable entrante multiplicado por
su respectivo costo será la contribución al costo total. En nuestro caso, el costo asociado a x 13 es 6 y
el costo asociado a x23 es 3, por lo que la variable que debemos elegir como entrante es x23.
Paso 2: si se incrementa el valor de la variable básica entrante, se establece una reacción en cadena
de cambios compensatorios en otras variables básicas (asignaciones) para seguir satisfaciendo las
4602
32 4 2
2
0005
3 8 54
restricciones de recursos y demanda. La primera variable básica que disminuya su valor hasta cero
será la variable básica que sale. En general, siempre existe sólo una reacción en cadena (en
cualquier dirección) que se puede completar con éxito para conservar la factibilidad, cuando la
variable básica entrante aumenta su valor. Esta reacción en cadena se puede identificar si se hace
una selección entre las celdas que tienen variables básicas: primero, la celda donadora en la
columna que tiene la variable básica; después, la celda receptora en el renglón que corresponde a
la celda donadora; luego, la celda donadora en la columna en que se encuentra esta celda receptora,
y así sucesivamente, hasta que la reacción en cadena conduce a una celda donadora en el renglón
que tiene a la variable básica entrante. Cuando una columna o renglón tiene más de una celda
adicional con variable básica, puede ser necesario explorar el camino que se va aseguir para
averiguar cuál debe seleccionarse como celda donadora o receptora. (Todas las demás menos la
adecuada llegarán tarde o temprano a un camino sin salida en un renglón o columna que no tiene
otra celda con una variable básica). Después de identificar la reacción en cadena. La celda donadora
que tiene la asignación menor proporciona en forma automática la variable básica que sale. (En caso
de un empate para la celda donadora, se puede elegir cualquiera para proporcionar la variable básica
que sale).
Si x23 es la variable básica entrante, la reacción en cadena de la tabla anterior se resume
enseguida. (Siempre se indicará la variable básica entrante colocando un signo + encuadrado dentro
de su celda):
v1 v2 v3 v4 Recursos ui
u1
3 25 4
u2 2 +
2 1
u3 +0
2 1
3 0
Demanda 3 4 2 1Costo=52
vj1 3 8 5
Al aumentar x23 debe disminuir x33 en la misma cantidad para conservar la demanda de 2 en
la columna 3; esto a su vez requiere que se aumente x32 en esa cantidad para mantener la oferta de 3
en el renglón 3 y esto a su vez exige una disminución en el valor de x22 para conservar la demanda
7
5600
3 6 4
4602
32 4 2
2
0005
3 8 54
de 4 en la columna 2. Esta disminución en x22 completa con éxito la reacción en cadena ya que
también conserva la oferta del renglón 2.
El resultado final es que las celdas (2,3) y (3,2) se convierten en celdas receptoras, cada
una con su asignación adicional proveniente de las celdas donadoras (2,2) y (3,3). Estas celdas
están indicadas en la tabla anterior por medio de los signos + y ). Observe que tuvo que elegirse la
celda (3,2) como celda receptora para el renglón 3 y no la (3,4), ya que esta última no hubiera
tenido celda donadora en la columna 4 para continuar la reacción en cadena. Note además que, a
excepción de la variable básica entrante, todas las celdas receptoras y donadoras en la reacción en
cadena deben corresponder a variables básicas en la solución básica factible actual.
Cada celda donadora disminuye su asignación en una cantidad exactamente igual al
aumento que tiene la variable básica entrante (y las otras celdas receptoras). Entonces, la celda
donadora que comienza con la asignación más pequeña en este caso las celdas (2,2) y (3,3) debe
ser la primera en llegar a una asignación de cero conforme se incrementa la variable entrante x 23.
Así, x22 ó x23 se pueden convertir en la variable básica que sale. Cuando existe empate para la
variable básica que sale, éste puede romperse de manera arbitraria, es decir, eligiendo cualquiera de
las variables donadoras con la asignación más pequeña como variable básica saliente. Como una
regla empírica, podemos seleccionar como variable básica saliente aquélla que tenga asociado el
mayor costo unitario, ya que como esta variable perderá completamente su valor (es decir, se
convertirá de variable básica a variable no básica), esperaríamos que el costo total de transporte
disminuya. Así, escogeríamos a x33 como variable básica saliente.
Paso 3: la nueva solución básica factible se identifica sumando el valor (antes de los cambios) de la
variable básica que sale a las asignaciones de cada celda receptora y restando esta misma cantidad
de las asignaciones de cada celda donadora. En la tabla anterior se observa que el valor de la
variable básica que sale x33 es 2, por lo que esta porción de la tabla símplex de transporte cambia,
como se ilustra en la siguiente tabla para la nueva solución. (Como x33 es no básica en la nueva
solución, su nueva asignación es cero y ya no se muestra en la tabla).
v1 v2 v3 v4 Recursos ui
u1
3 25
u2
0 22
7
5600
3 6 4
460232 4 2
u3
2 13
Demanda 3 4 2 1Costo=40
vj
En este momento se puede señalar una interpretación útil de las cantidades c ijuivj que se
obtienen en la prueba de optimalidad. Debido al cambio de 2 unidades en las asignaciones de las
celdas donadoras a las receptoras, el costo total cambia en:
DZ = 2(38+34) = 2(6) = 12 = 2(c23u2v3)
es decir, el costo total de transporte se decrementa en 12 unidades con respecto al costo anterior que era de 52 unidades. Notemos que hemos obtenido una nueva política de transporte, la cual podemos resumir así:
La nueva solución básica factible es x11=3, x12=2, x22=0 (variable básica degenerada),
x23=2, x32=2 y x34=1 y el costo total de transporte asociado es de:
x11 c11 x12 c12 x22 c22 x23 c23 x32 c32 x34 c34
Costo = 3 (3) + 2 (7) + 0 (4) + 2 (3) + 2 (3) + 1 (5) = 40 unidades
Antes de completar la solución del problema ejemplo, se hará un resumen de las reglas del
método símplex de transporte.
Resumen del método símplex de transporte
Inicialización: Se construye una solución inicial básica factible. Se realiza la prueba de optimalidad.
Prueba de optimalidad: Se obtiene ui y vj eligiendo el renglón con el mayor número de asignaciones
y estableciendo su ui = 0, y después resolviendo el sistema de ecuaciones cij = ui+vj para cada (i,j)
tal que xij es básica. Si cijuivj 0 para toda (i,j) tal que xij es no básica, entonces la solución actual
es óptima por lo que el proceso se detiene. De lo contrario, se regresa a una iteración.
Iteración:
1. Se determina la variable básica entrante: se elige la variable no básica x ij que tiene el valor
negativo más grande (en términos absolutos) para cijuivj.
2
0005
3 8 54
2. Se determina la variable básica que sale identificando la reacción en cadena (encontrar un
circuito) que se necesita para conservar la factibilidad cuando se aumenta el valor de la variable
básica entrante. Entre las celdas donadoras se selecciona la variable básica que tiene el menor
valor.
3. Se determina la nueva solución básica factible: se suma el valor de la variable básica que sale a
las asignaciones de las celdas receptoras y se resta este valor a las asignaciones de las celdas
donadoras.
Continuando con la aplicación de este procedimiento a nuestro problema, tenemos que
calcular los nuevos valores de las ui y vj y después los valores cijuivj correspondientes a las
variables no básicas para determinar si todos cumplen con la prueba de optimalidad: Nuevamente
existen m+n1=3+41=6 variables básicas, que dan origen al siguiente conjunto de ecuaciones:
3 = u1+v1
7 = u1+v2
4 = u2+v2
3 = u2+v3
3 = u3+v2
5 = u3+v4
Observemos que nuevamente resultaron ser 6 ecuaciones que involucran 7 incógnitas (tres
de las ui y cuatro de las vj). Ya que hay empate en el número de asignaciones que tiene cada renglón
(2 asignaciones en cada renglón), asignemos el valor de cero a la incógnita u1. De esta asignación
resulta lo siguiente:
3 = u1+v1 ® v1=37 = u1+v2 ® v2=74 = u2+v2
3 = u2+v3
3 = u3+v2
5 = u3+v4
Hemos obtenido el valor de dos incógnitas más, v1, y v2, los cuales nos ayudarán para hallar
el valor de las incógnitas restantes:
3 = u1+v1 ® v1=37 = u1+v2 ® v2=74 = u2+v2 si v2=7, entonces u2= 33 = u2+v3 si u2= 3, entonces v3=63 = u3+v2 si v2=7, entonces u3= 45 = u3+v4 si u3= 4, entonces v4=9
De esta forma hemos obtenido el valor de todas las incógnitas y procedemos a colocarlos en la tabla como sigue:
v1 v2 v3 v4 Recursos ui
u1
3 25 0
u2
0 22 3
u3
2 13 4
Demanda 3 4 2 1Costo=40
vj3 7 6 9
Ahora calculemos los valores cijuivj para las variables no básicas y coloquemos estos
valores en la esquina inferior izquierda de cada celda:
Para la celda (1,3): 6 0 6 = 0Para la celda (1,4): 4 0 9 = 5Para la celda (2,1): 2 (3) 3 = 2Para la celda (2,4): 2 (3) 9 = 4Para la celda (3,1): 4 (4) 3 = 5Para la celda (3,3): 8 (4) 6 = 6
v1 v2 v3 v4 Recursos ui
u1
3 25 0
u2
0 22 3
u3
2 13 4
Demanda 3 4 2 1Costo=40
vj3 7 6 9
Aplicando la prueba de optimalidad para verificar los valores de c ijuivj obtenidos, vemos
que dos de estos valores ( c14u1v4= 5, c24u2v4= 4) son negativos, se concluye que la solución
básica factible actual no es óptima. Entonces, el método símplex de transporte debe proceder a
hacer una iteración para encontrar una mejor solución básica factible. Aplicando el procedimiento
73 6 4
32 4 2
23 8 54
7
5000
3 6 4
4002
32 4 2
2
0605
3 8 54
descrito anteriormente, se llega al siguiente conjunto de tablas símplex de transporte que se muestra
enseguida y que dan solución al problema planteado:
v1 v2 v3 v4 Recursos ui
u1
3 2 +
5 0
u2
0 22 3
u3 +2
1
3 4
Demanda 3 4 2 1Costo=40
vj3 7 6 9
v1 v2 v3 v4 Recursos ui
u1
3 1 15
u2
0 22
u3
33
Demanda 3 4 2 1Costo=35
vj
La nueva solución básica factible es x11=3, x12=1, x14=1, x22=0 (variable básica degenerada), x23=2
y x32=3 y el costo total de transporte asociado es de:
x11 c11 x12 c12 x14 c14 x22 c22 x23 c23 x32 c32
Costo = 3 (3) + 1 (7) + 1 (4) + 0 (4) + 2 (3) + 3 (3) = 35 unidades
Como en esta última tabla todas las cijuivj son no negativas (¡comprobarlo!), la prueba de
optimalidad identifica este conjunto de asignaciones como óptimo, lo cual concluye el algoritmo.
FUENTE: http://www.investigacion-operaciones.com/material%20didactico/transporte.doc
7
5000
3 6 4
4002
32 4 2
2
0605
3 8 54
7
20 500
3 6 4
4002
32 4 2
0605
3 8 54
PROBLEMA DE FLUJO MAXIMO
Modelo de Flujo Máximo
Se trata de enlazar un nodo fuente y un nodo destino a través de una red de arcos dirigidos. Cada arco tiene una capacidad máxima de flujo admisible. El objetivo es el de obtener la máxima capacidad de flujo entre la fuente y el destino.
Características:
1. Todo flujo a través de una red conexa dirigida se origina en un nodo, llamado fuente, y termina en otro nodo llamado destino.
2. Los nodos restantes son nodos de trasbordo. 3. Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la
cantidad máxima de flujo está dad por la capacidad del arco. En la fuente, todos los arcos señalan hacia fuera. En el destino, todos señalan hacia el nodo.
4. El objetivo es maximizar la cantidad total de flujo de la fuente al destino. Esta cantidad se mide en cualquiera de las dos maneras equivalentes, esto es, la cantidad que sale de la fuente o la cantidad que entra al destino.
El problema de flujo máximo se puede formular como un problema de programación lineal, se puede resolver con el método símplex y usar cualquier software. Sin embargo, se dispone de un algoritmo de trayectorias aumentadas mucho más eficientes. El algoritmo se basa en dos conceptos intuitivos, el de red residual y el de trayectoria aumentada.
Algoritmo de la trayectoria de aumento para el problema de flujo máximo:
1. Se identifica una trayectoria de aumento encontrando alguna trayectoria dirigida del origen al destino en la red residual, tal que cada arco sobre esta trayectoria tiene capacidad residual estrictamente positiva. (Si no existe una, los flujos netos asignados constituyen un patrón del flujo óptimo).
2. Se identifica la capacidad residual c* de esta trayectoria de aumento encontrando el mínimo de las capacidades residuales de los arcos sobre esta trayectoria. Se aumenta en c* el flujo de esta trayectoria.
3. Se disminuye en c* la capacidad residual de cada arco en esta trayectoria de aumento. Se aumenta en c* la capacidad residual de cada arco en la dirección opuesta en esta trayectoria. Se regresa la paso 1.
Modelo de la ruta más corta
Considere una red conexa y no dirigida con dos nodos especiales llamados origen y destino. A cada ligadura (arco no dirigido) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta (la trayectoria con la mínima distancia total) del origen al destino.
Se dispone de un algoritmo bastante sencillo para este problema. La esencia del procedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino.
Algoritmo de la ruta más corta:
1. Objetivo de la n-ésima iteración: encontrar el n-ésimo nodo más cercano al origen. (Este paso se repetirá para n=1,2,… hasta que el n-ésimo nodo más cercano sea el nodo destino.)
2. Datos para la n-ésima iteración: n-1 nodos más cercanos al origen (encontrados en las iteraciones previas), incluida su ruta más corta y la distancia desde el origen. (Estos nodos y el origen se llaman nodos resueltos, el resto son nodos no resueltos.)
3. Candidatos para el n-ésimo nodo más cercano: Cada nodo resuelto que tiene conexión directa por una ligadura con uno o más nodos no resueltos proporciona un candidato, y éste es el nodo no resuelto que tiene la ligadura más corta. (Los empates proporcionan candidatos adicionales.)
4. Cálculo del n-ésimo nodo más cercano : para cada nodo resuelto y sus candidatos, se suma la distancia entre ellos y la distancia de la ruta más corta desde el origen a este nodo resuelto. El candidato con la distancia total más pequeña es el n-ésimo nodo más cercano (los empates proporcionan nodos resueltos adicionales), y su ruta más corta es la que genera esta distancia.
NOTACIÓN Y TERMINOLOGÍA
Red: Una red consiste en un conjunto de puntos y un conjunto de líneas que unen ciertos pares de puntos. Los puntos se llaman nodos (o vértices). Las líneas se llaman arcos (o ligaduras, aristas o ramas).
Los arcos se etiquetan para dar nombres a los nodos en sus puntos terminales, por ejemplo, AB es el arco entre lo nodos A Y B.
En un problema de programación lineal, las redes pueden representar un conjunto de estaciones, campos petrolíferos, almacenes, fabricas, sucursales, ciudades, interconectadas entre si a través de caminos, conductos, tuberías que permiten fluir productos para la comercialización o la distribución.
Arcos Dirigidos: Se dice que un arco es dirigido cuando el arco tiene flujo en una dirección (como en una calle de un sentido). La dirección se indica agregando una cabeza de flecha al final de la línea que representa el arco.
Al etiquetar un arco dirigido con el nombre de los nodos que une, siempre se coloca primero al nodo de donde viene y después el nodo a donde va, esto es, un
arco dirigido del nodo A al nodo B debe etiquetarse como AB y no como BA. Otra Manera es A B.
Arcos No Dirigidos: Si el flujo a través de un arco se permite en ambas direcciones (como una tubería que se puede usar para bombear fluido en ambas direcciones), se dice que es un arco no dirigido.
También se les llama ligadura. Aunque se permita que el flujo a través de un arco no dirigido ocurra en cualquier dirección, se supone que ese flujo será en una dirección, en la seleccionada, y no se tendrá flujos simultáneos en direcciones opuestas.
Trayectoria: Una trayectoria entre dos nodos es una sucesión de arcos distintos que conectan estos nodos. Por ejemplo, una de las trayectorias que conectan los nodos O y T en la figura 1 es la sucesión de arcos OB-BD-DT (O B D T), y viceversa.
Cuando algunos o todos los arcos de una red son arcos dirigidos, se hace la distinción entre trayectorias dirigidas y trayectorias no dirigidas.
Trayectoria Dirigida: Una trayectoria dirigida del nodo i al nodo j, es una sucesión de arcos cuya dirección (si la tienen) es hacia el nodo j, de manera que el flujo del nodo i al nodo j, a través de esta trayectoria es factible.
Trayectoria No Dirigida: Una trayectoria no dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección (si la tienen) pueden ser hacia o desde el nodo j. Con frecuencia alguna trayectoria no dirigida tendrá algunos arcos dirigidos hacia el nodo j y otros desde él (es decir, hacia el nodo i).
Ciclo: Un ciclo es una trayectoria que comienza y termina en el mismo nodo. En la red no dirigida que se muestra en la figura 5 existen muchos ciclos, OA-AB-BC-CO.
Red Conexa: Una red conexa es una red en la que cada par de nodos está conectado. Se dice que dos nodos están conectados si la red contiene al menos una trayectoria no dirigida entre ellos. Se debe resaltar que no es necesario que la trayectoria sea dirigida aun cuando la red sea dirigida. La figura 1 representa una red conexa.
Árbol de Expansión: es una red conexa para los n nodos, que contiene ciclos no dirigidos. Todo árbol de expansión tiene justo n-1 arcos, ya que este es el número mínimo de arcos necesarios para tener una red conexa y el máximo numero posible para que no haya ciclos no dirigidos.
La figura 6 representa una red conexa, la figura 7 muestra los cinco nodos de la red conexa de la figura 6, ahora la figura 8 muestra el proceso para hacer crecer
un árbol colocando una rama a la vez, hasta obtener un árbol de expansión. En cada etapa del proceso se tienen varias alternativas para el nuevo arco, por lo que la figura 8 muestra solo una de las muchas formas de construir un árbol de expansión.
Capacidad de Arco: Es la cantidad máxima de flujo (quizás infinito) que puede circular en un arco dirigido.
Nodo Fuente: (o nodo de origen) tiene la propiedad de que el flujo que sale del nodo excede al flujo que entra a él.
Nodo Demanda: (o nodo destino) es el caso contrario al nodo fuente, donde el flujo que llega excede al que sale de él.
Nodo de Trasbordo: (o nodo intermedio) satisface la conservación del flujo, es decir, el flujo que entra es igual al que sale.
REDES DIRIGIDAS Y NO DIRIGIDAS
Red Dirigida: Es una red que tiene solo arcos dirigidos.
En una red dirigida, un ciclo puede ser dirigido o no dirigido, según si la trayectoria en cuestión es dirigida o no dirigida. (Como una trayectoria dirigida también es no dirigida, un ciclo dirigido es un ciclo no dirigido, pero en general el inverso no es cierto.) Por ejemplo en la figura 9 DE-ED es un ciclo dirigido. Por contrario, AB-BC-CA no es un ciclo dirigido puesto que la dirección del arco AC es opuesta a la de los arcos AB y BC. Por otro lado, AB-BC-AC no es un ciclo dirigido porque ABCA es una trayectoria no dirigida.
Red No Dirigida: Es una red donde todos sus arcos son no dirigidos. La figura 10 representa una red no dirigida.
VISTA GENERAL DE ALGUNAS APLICACIONES PRÁCTICAS DE LA OPTIMIZACIÓN DE REDES
1. Diseño de redes de telecomunicación (redes de fibra óptica, de computadores, telefónicas, de televisión por cable, etc.)
2. Diseño de redes de transporte para minimizar el costo total de proporcionar las ligaduras (vías ferroviarias, carreteras, etc.)
3. Diseño de una red de líneas de transmisión de energía eléctrica de alto voltaje. 4. Diseño de una red de cableado en equipo eléctrico (como sistemas de computo) para
minimizar la longitud total del cable. 5. Diseño de una red de tuberías para conectar varias localidades. 6. Diseño de una red de tuberías de gas natural mar adentro que conecta fuentes del golfo de
México con un punto de entrega en tierra con el objetivo de minimizar el costo de construcción.
7. Determinación de la ruta más corta que une dos ciudades en una red de caminos existentes.
8. Determinar la capacidad anual de máxima en toneladas de una red de conductos de pasta aguada de carbón que enlaza las minas carboneras de Wyoming con las plantas generadoras de electricidad Houston. (Los conductos de pasta aguada de carbón transportan éste bombeando agua a través de tubos adecuadamente diseñados que operan entre las minas de carbón y el destino deseado.)
9. Determinación del programa de costo mínimo de los campos petrolíferos a refinerías y finalmente a los campos de distribución. Se pueden enviar petróleo crudo y productos derivados de la gasolina en buques tanque, oleoductos y/o camiones. Además de la disponibilidad de la oferta máxima en los campos petrolíferos y los requisitos de demanda mínima en los centros de distribución, deben tomarse en cuenta restricciones sobre la capacidad de las refinerías y los modos de transporte.
EJEMPLOS DE TERMINOS
Se tiene la red de distribución para Distribution Unlimited Co.
Nodos A, B, C, D , E
Arcos AB, AC, AD, BC, CE, DE, ED
Arco Dirigido A B, A C, A D, B C, C E, D E, E D
TrayectoriaEntre A y D:
A D
A C E D
A B C E D
Trayectoria DirigidaEntre A y E
A B C E
Trayectoria No DirigidaEntre B y D
B C A D
Ciclo DE-ED (ciclo dirigido)
AB-BC-CA (ciclo no dirigido)
Red Conexa Si es red conexa
Capacidad de Arco 3, 2, 5, 3, 4, 2, 1
Nodo Fuente A
Nodo Demanda C, D
Nodo de Trasbordo B
OTRAS DEFINICIONES
Red Residual: Una red residual muestra las capacidades restantes (llamadas capacidades residuales) para asignar flujos adicionales.
Trayectoria de Aumento: Una trayectoria de aumento es una trayectoria dirigida del nodo fuente al nodo destino en la red residual, tal que todos los arcos en ese trayectoria tienen capacidad residual estrictamente positiva. El mínimo de estas capacidades residuales se llama capacidad residual de la trayectoria de aumento porque representa la cantidad de flujo que es factible agregar en toda la trayectoria. Por lo tanto, cada trayectoria de aumento proporciona una oportunidad de aumento más el flujo a través de la red original.
FUENTE: http://www.monografias.com/trabajos16/flujo-redes/flujo-redes.shtml
RUTA CRITICA (PERT/CPM)
Dos son los orígenes del método del camino crítico: el método PERT (Program Evaluation and Review Technique) desarrollo por la Armada de los Estados Unidos de América, en 1957, para controlar los tiempos de ejecución de las diversas actividades integrantes de los proyectos espaciales, por la necesidad de terminar cada una de ellas dentro de los intervalos de tiempo disponibles. Fue utilizado originalmente por el control de tiempos del proyecto Polaris y actualmente se utiliza en todo el programa espacial.El método CPM (Crítical Path Method), el segundo origen del método actual, fue desarrollado también en 1957 en los Estados Unidos de América, por un centro de investigación de operaciones para la firma Dupont y Remington Rand, buscando el
control y la optimización de los costos de operación mediante la planeación adecuada de las actividades componentes del proyecto.Ambos métodos aportaron los elementos administrativos necesarios para formar el método del camino crítico actual, utilizandoel control de los tiempos de ejecución y los costos de operación, para buscar que el proyecto total sea ejecutado en el menor tiempo y al menor costo posible.
2. Usos
El campo de acción de este método es muy amplio, dada su gran flexibilidad y adaptabilidad a cualquier proyecto grande o pequeño. Para obtener los mejores resultados debe aplicarse a los proyectos que posean las siguientes características:
a. Que el proyecto sea único, no repetitivo, en algunas partes o en su totalidad. b. Que se deba ejecutar todo el proyecto o parte de el, en un tiempo mínimo, sin variaciones,
es decir, en tiempo crítico. c. Que se desee el costo de operación más bajo posible dentro de un tiempo disponible.
Dentro del ámbito aplicación, el método se ha estado usando para la planeación y control de diversas actividades, tales como construcción de presas, apertura de caminos, pavimentación, construcción de casas y edificios, reparación de barcos, investigación de mercados, movimientos de colonización, estudios económicos regionales, auditorias, planeación de carreras universitarias, distribución de tiempos de salas de operaciones, ampliaciones de fábrica, planeación de itinerarios para cobranzas, planes de venta, censos de población, etc.
3. Planeación y control de proyectos con PERT-CPM
La buna administración de proyectos a gran escala requiere planeación, programación y coordinación cuidadosa de muchas actividades interrelacionadas. Al principiar la década de 1950 se desarrollaron procedimientos formales basados en uso de redes y de las técnicas de redes para ayudar en estas tareas. Entre los procedimientos mas sobresalientes se encuentran el PERT (técnica de evaluación y revisión de programas) y el CPM (método de la ruta critica).Aunque originalmente los sistemas tipo PERT se aplicaron para evaluar la programación de un proyecto de investigación y desarrollo, también se usan para controlar el avance de otros tipos de proyecto especiales. Como ejemplos se pueden citar programas de construcción, la programación de computadoras, la preparación de propuestas y presupuestos, la planeación de l mantenimiento y la instalación de sistemas de computo, este tipo de técnica se ha venido aplicando aun a la producción de películas, a las compañas políticas y a operaciones quirúrgicas complejas.El objetivo de los sistemas tipo PERT consiste en ayudar en la planeación y el control, por lo que no implica mucha optimización directa. Algunas veces el objetivo primario es determinar la probabilidad de cumplir con fechas de entrega especificas. También identifica aquellas actividades que son más probables que
se conviertan en cuellos de botella y señala, por e4nde, en que puntos debe hacerse el mayor esfuerzo para no tener retrasos. Un tercer objetivo es evaluar el efecto de los cambios del programa. Por ejemplo, se puede valorar el efecto de un posible cambio en la asignación de recursos de las actividades menos criticas a aquellas que se identificaron con cuellos de botella. Otra aplicación importante es la evaluación del efecto de desviarse de lo programado.Todos los sistemas tipo PERT emplean una red de proyecto para visualizar gráficamente la interrelación entre sus elementos. Esta representación del plan de un proyecto muestra todas las relaciones de procedencia, respecto al orden en que se deben realizar las actividades. En la Fig. 1 sé muestran estas características para la red de proyecto inicial para la construcción de una casa. Esta red indica que la excavación debe hacerse antes de poner los cimientos y después los cimientos deben completarse antes de colocar las paredes. Una vez que se levantan las paredes se pueden realizar tres actividades en paralelo. Al seguirla red hacia delante se ve el orden de las tareas subsecuentes.En la terminología de PERT, cada arco de la red representa una actividad, es decir, una de las tareas que requiere el proyecto, cada nodo representa un evento que por lo general se define con el momento ñeque se terminan todas las actividades que llegan a ese nodo, Las puntas de flecha indican la secuencia en la que3 debe ocurrir cada uno de esos eventos. Lo que es mas, un evento debe preceder a la iniciación de las actividades que llegan a ese nodo. Las puntas de flecha indican la secuencia en la que debe ocurrir cada uno de esos eventos. Lo que es mas, un evento debe preceder a la iniciación de las actividades que salen de ese nodo. (En la realidad, con frecuencia se pueden traslapar etapas sucesivas de un proyecto, por lo que la red puede representar una aproximación idealizada del plan de un proyecto.)El nodo hacia el que todas las actividades se dirigen es el evento que corresponde a la terminación desde su concepción, o bien, si el proyecto ya comenzó, el plan para su terminación. En él ultimo caso, cada nodo de la red sin arcos que llegan representa el evento de continuar una actividad en marcha o el evento de iniciar una nueva actividad que puede comenzar en cualquier momento.Cada arco juega un doble papel, el de representar una actividad y el de ayudar a representar las relaciones de procedencia entre las distintas actividades. En ocasiones, se necesita un arco para definir las relaciones de procedencia aun cuando no haya una actividad real que representar. En este caso, se introduce una actividad ficticia que requiere un tiempo cero, en donde el arco que representa esta actividad ficticia se muestra como una flecha punteada que indica esa relación de procedencia. Por ejemplo, considérese el arco 5 ® 8 que representa una actividad ficticia en la Fig. 1; el único objeto de este arco es indicar que la colocación de la tubería debe estar terminada antes de poder comenzar los exteriores.Una regla común para construir este tipo de redes es que dos nodos no pueden estar conectados directamente por mas de un arco. Las actividades ficticias también se pueden usar para evitar violar esta regla cuando se tienen dos o más actividades concurrentes; en la Fig. 1 se ilustra esto con el arco 11® 12. El único propósito de este arco es indicar que debe terminarse la colocación de pisos antes de instalar los acabados interiores sin tener dos arcos del nodo 9 al nodo 12.
Una vez desarrollada la red la red de un proyecto, el siguiente paso es estimar el tiempo que se requiere para cada actividad. Estas estimaciones para el ejemplo de la construcción de una casa de la figura 1. se muestran en la figura 2 con los números mas oscuros (en unidades de días de trabajo) que aparecen junto a los arcos. Estos tiempos se usan para calcular dos cantidades básicas para cada evento, a saber, su tiempo más próximo y su tiempo más lejano.El tiempo más próximo para un evento es el tiempo (estimado) en el que ocurrirá el evento si las actividades que lo proceden comienzan lo mas pronto posible.Los tiempos más próximos se obtienen al efectuar una pasada hacia delante a través de la red, comenzando con los eventos iniciales y trabajando hacia delante en el tiempo, hasta los eventos finales, para cada evento se hace un calculo del tiempo en el que ocurrirá cada uno, si cada evento procedente inmediato ocurre en su tiempo más próximo y cada actividad que interviene consume exactamente su tiempo estimado. La iniciación del proyecto se debe etiquetar con el tiempo 0. este proceso se muestra en la tabla 1. para el ejemplo considerado en las figuras 1 y 2. los tiempos más próximos que se obtuvieron están registrados en la figura 2, con el primero de los dos números que se dan para cada nodo.El tiempo más lejano para un evento es él ultimo momento (estimado) en el que puede ocurrir sin retrasar la terminación del proyecto mas allá de su tiempo más próximo.
Tabla 1. Calculo de los tiempos más próximos para el ejemplo de la construcción de una casa.
EventoEvento inmediato
Anterior
Tiempo Tiempo
mas + de la
próximo actividad
Tiempo
= máximo más
próximo
1 ___ ___ 0
2 1 0 + 2 2
3 2 2 + 4 6
4 3 6 + 10 16
5 4 16 + 4 20
6 4 16 + 6 22
7 4 16+7 25
5 20+5
8 5 20+0 29
6 22+7
9 7 25+8 33
10 8 29+9 38
11 9 33+4 37
12 9 33+5 38
11 37+0
13 10 38+2 44
En este caso los tiempos más lejanos se obtienen sucesivamente para los eventos al efectuar una pasada hacia atrás a través de la red, comenzando con los eventos finales y trabajando hacia atrás en el tiempo hasta los iniciales. Para cada evento él calculo del tiempo final en el que puede ocurrir un evento de manera que los que le siguen ocurran en su tempo mas lejano, si cada actividad involucrada consume exactamente su tiempo estimado. Este proceso se ilustra en la tabla 2, en donde 44 días es el tiempo más próximo y el tiempo más lejano para la terminación del proyecto de construcción de la casa. Los tiempos más lejanos para la terminación del proyecto de construcción de la casa. Los tiempos mas lejanos que se obtuvieron se encuentran también en la figura 2 como el segundo numero que se da para cada nodo. Sea la actividad ( i , j ) la actividad que va del evento i al evento j en la red del proyecto.La holgura para un evento es la diferencia entre su tiempo más lejano y su tiempo más próximo.
La holgura para una actividad ( i , j ) e3s la diferencia entre [ el tiempo mas lejano del evento] y [el tiempo mas próximo del evento i mas el tiempo estimado para la actividad].Así, si se supone que todo lo demás marcha a tiempo, la holgura para un evento indica cuanto retraso se puede tolerar para llegar a ese evento sin retrasar la terminación del proyecto, y la holgura para una actividad indica lo mismo respecto a un retraso en la terminación de esa actividad. En a tabla 3 se ilustran los calculo de estas holguras para el proyecto de la construcción de una casa.Una ruta critica de un proyecto es una ruta cuyas actividades tienen la holgura cero. (Todas las actividades y eventos que tienen holgura cero deben estar sobre una ruta crítica, pero no otras.)Tabla 2. Calculo de los tiempos más lejanos para el ejemplo de la construcción de una casa
Evento
Evento inmediato
Anterior
Tiempo Tiempo
mas - de la
lejano actividad
Tiempo
= mínimo más
próximo
13 __ ___ 44
12 13 44-6 38
11 12 38-0 38
10 13 44-2 42
9 12 38-5 33
11 38-4
8 10 42-9 33
7 9 33-8 25
6 8 33-7 26
5 8 33-0 20
7 25-5
4 7 25-7 16
6 26-6
5 20-4
3 4 16-10 6
2 3 6-4 2
1 2 2-2 0
Tabla 3. Calculo de las holguras para el ejemplo de la construcción de una casa.
Evento Holgura Actividad Holgura
1
2
3
4
5
6
7
8
9
0 – 0 = 0
2 - 2 = 0
6 – 6 = 0
16 - 16 = 0
20 – 20 = 0
26 - 22 = 4
25 – 25 = 0
33 - 29 = 4
33 – 33 = 0
(1,2)
(2,3)
(3,4)
(4,5)
(4,6)
(4,7)
(5,7)
(6,8)
(7,9)
2 - (0+2) = 0
6 - (2+4) = 0
16 - (6+10) = 0
20 - (16+4) = 0
26 - (16+6) = 4
25 - (16+7) = 2
25 - (20+5) = 0
33 - (22+7) = 4
33 - (25+8) = 0
10
11
12
13
42 - 38 = 4
38 – 37 = 1
38 - 38 = 0
44 – 44 = 0
(8,10)
(9,11)
(9,12)
(10,13)
(12,13)
42 - (29+9) = 4
38 - (33+4) = 1
38 - (33+5) = 0
44 - (38+2) = 4
44 - (38+6) = 0
Si se verifica en la tabla 3 las actividades que tienen holgura cero, se observa que el ejemplo de la construcción de una casa tiene una ruta critica, 1 ® 2 ® 3 ® 4 ® 5 ® 6 ® 7 ® 9 ® 12 ® 13, como se muestra en la figura 2 con las flechas mas oscuras. Esta secuencia de actividades criticas debe mantenerse estrictamente a tiempo, si se quiere evitar retrasos en la terminación del proyecto. Otros proyectos pueden tener mas de una ruta critica; por ejemplo nótese lo que pasaría en la figura 2 si el tiempo estimado de la actividad (4,6) se cambiara de 6 a 19.Resulta interesante observar en la tabla 3 que mientras que todos los eventos sobre la ruta critica (inclusive el 4 y el 7 ) necesariamente tienen holgura cero, no es así para la actividad (4 , 7), ya que su tiempo estimado es menor que la suma de los tiempos estimados para las actividades (4 , 5 ) y (5 , 7). En consecuencia, estas ultimas actividades están en la ruta crítica, pero la actividad (4 , 7) no lo está.Esta información sobre los tiempos más cercanas y más lejanos, las holguras y la ruta crítica, es invaluable para el administrador del proyecto. Entre otras cosas, le permite investigar el efecto de posible mejoras en la planeación para determinar en donde debe hacerse un esfuerzo especial para mantenerse y evaluar el impacto de los retrasos.
Graficas PERTLa gráfica PERT es una gráfica original de redes no medidas que contiene los datos de las actividades representadas por flechas que parten de un evento i y terminan en un evento j.
En la parte superior de la flecha se indica el número de identificación, generalmente los números de los eventos (i-j). En la parte inferior aparece dentro de un rectángulo la duración estándar (t) de la actividad. En la mitad superior del evento se anota el número progresivo, en el cuarto inferior izquierdo la última lectura del proyecto y en el cuarto inferior derecho la primera lectura del proyecto.Esta gráfica tiene como ventaja la de informar las fechas más tempranas y más tardías de iniciación y terminación de cada actividad, sin tener que recurrir a la matriz de holguras.
Veamos cómo se presenta la ampliación de la fábrica por medio de una gráfica PERT.
4. Red de Actividades
Se llama red la representación gráfica de las actividades que muestran sus eventos, secuencias, interrelaciones y el camino critico. No solamente se llama camino critico al método sino también a la serie de actividades contadas desde la iniciación del proyecto hasta su terminación, que no tienen flexibilidad en su tiempo de ejecución, por lo que cualquier retraso que sufriera alguna de las actividades de la serie provocaría un retraso en todo el proyecto.Desde otro punto de vista, camino critico es la serie de actividades que indica la duración total del proyecto. Cada una de las actividades se representa por una flecha que empieza en un evento y termina en otro. Se llama evento al momento de iniciación o terminación de una actividad. Se determina en un tiempo variable entre el más temprano y el más tardío posible, de iniciación o de terminación.
A los eventos se les conoce también con los nombres de nodos.Evento Evento
I j
El evento inicial se llama i y el evento final se denomina j. El evento final de una actividad será el evento inicial de la actividad siguiente.Las flechas no son vectores, escalares ni representan medida alguna. No interesa la forma de las flechas, ya que se dibujarán dé acuerdo con las necesidades y comodidad de presentación de la red. Pueden ser horizontales, verticales, ascendentes, descendentes curvas, rectas, quebradas, etc.En los casos en que haya necesidad de indicar que una actividad tiene una interrelación o continuación con otra se dibujará entre ambas una línea punteada, llamada liga, que tiene una duración de cero.La liga puede representar en algunas ocasiones un tiempo de espera para poder iniciar la actividad siguienteVarias actividades pueden terminar en un evento o partir de un mismo evento.
(a) Incorrecto, (b) Correcto.
Al construir la red, debe evitarse lo siguiente:
1. Dos actividades que parten de un mismo evento y llegan a un mismo evento. Esto produce confusión de tiempo y de continuidad. Debe abrirse el evento inicial o el evento final en dos eventos y unirlos con una liga.
2. Partir una actividad de una parte intermedia de otra actividad. Toda actividad debe empezar invariablemente en un evento y terminar en otro. Cuando se presenta este caso, a la actividad base o inicial se le divide en eventos basándose en porcentajes y se derivan de ellos las actividades secundadas.
(a) Incorrecto; (b) Correcto.
3. Dejar eventos sueltos al terminar la red. Todos ellos deben relacionarse con el evento inicial o con el evento final.
(a) Incorrecto; (b) Correcto
5. Enfoque de tres estimaciones de PERT.
Hasta ahora se ha supuesto implícitamente que se puede obtener estimaciones con una exactitud razonable del tiempo requerido para cada actividad del proyecto. En la realidad, con frecuencia existe bastante incertidumbre sobré cuales serán estos tiempo; de hecho se trata de una variable aleatoria que tiene cierta distribución de probabilidad. La versión original de PERT toma en cuenta esta incertidumbre usando tres tipos diferentes de estimaciones par los tiempos de las actividades, con el fin de obtener información basica sobre su distribución de probabilidad. Esta información para todos los tiempos de las actividades se utiliza para estimas la probabilidad de terminar el proyecto en la fecha programada.
Las tres estimaciones empleadas por PERT para cada actividad son una estimación más probable, una estimación optimista y una estimación pesimista. La estimación mas probable (denotada por m ) intenta ser la estimación mas realista del tiempo que puede consumir una actividad. En términos estadísticos, es una estimación de la moda (el punto mas alto) de la distribución de probabilidad para el tiempo de la actividad. La estimación optimista (denotada por a) procura ser el tiempo poco probable pero posible si todo sale bien; es en esencia una estimación de la cota inferior de la distribución de la probabilidad. Por ultimo, se intenta que la estimación pesimista (denotada por b) sea el tiempo poco probable pero posible si todo sale mal. En términos estadísticos, se trata en esencia de una estimación de la cota superior de la distribución de probabilidad. En la figura 3 se muestra la localización ideal de estas tres estimaciones con respecto a la distribución de probabilidad.
Tiempo transcurridoFigura 3. Modelo de distribución de probabilidad para loas tiempos de las actividades en el enfoque de tres estimaciones de PERT: m = estimación probable, a = estimación optimista y b = estimación pesimista.Se hacen dos suposiciones para convertir m, a y b en estimaciones del valor esperado ( te ) y la variancia ( 2) del tiempo que requiere la actividad. Una suposición es que , la desviación estándar (raíz cuadrada de la variancia), es igual a un sexto del intervalo de los requerimientos de tiempo razonablemente posibles; esto es,
es la estimación deseada de la variancia. El razonamiento para hacer esta suposición es que se considera que las colas de muchas distribuciones de probabilidad (como en la distribución normal) están mas o menos a tres desviaciones estándar de la media, de manera que existe una dispersión de alrededor de seis desviaciones estándar entre las colas, por ejemplo, las cartas de control que se usan normalmente para el control estadístico de la calidad están construidas de manera que la dispersión entre los limites de control se estima en seis desviaciones estándar.Para obtener la estimación del valor esperado ( te ), también es necesaria una suposición sobre la forma de la distribución de probabilidad, se supone que la distribución es ( al menos aproximadamente) una distribución beta. Este tipo de distribución tiene la forma que se muestra en la figura 3, que es razonable para este propósito.Si se usa el modelo ilustrado en la figura 3 el valor esperado del tiempo de una
actividad es aproximadamente
Nótese que el medio del intervalo (a + b)/ 2 se encuentra entre a y b de manera que te es la media aritmética ponderada de la moda y la mitad del intervalo, con un peso de dos tercios para la moda. Aunque la suposición de una distribución beta es arbitraria, sirve para el propósito de localizar el valor esperado a m, a y b de una manera que parece ser razonable.Después de calcular el valor esperado y la variancia estimados para cada una de las actividades, se necesitan tres suposiciones adicionales (o aproximaciones) para poder calcular la probabilidad de terminar el proyecto a tiempo. Una es que los tiempos de las actividades son estadísticamente independientes. Una segunda es que la ruta critica ( en términos de los tiempos esperado) siempre requiere un tiempo total mayor que cualquier otra ruta. Esto implica que el valor esperado y la variancia, es sencillo encontrar la probabilidad de que esta variable aleatoria normal ( tiempo del proyecto) sea menor que el tiempo de terminación programado.
6. Método CPM para trueques entre tiempo y costo
Las versiones originales de CPM y PERT difieren en dos aspectos importantes. Primero, el CPM supone que los tiempos de las actividades son deterministicos ( es decir, se pueden predecir de manera confiable sin incertidumbre significativa), por lo que no necesita las tres estimaciones que se acaban de describir. Segundo, en lugar de dar una importancia primordial al tiempo (explícitamente), el CPM asigna la misma importancia al tiempo y al costo y pon esto de relieve al construir un a curva de tiempo-costo para cada actividad, con la que se muestra en la figura 4. Esta curva representa la relación entre el costo directo presupuestado para la actividad y su tiempo de duración resultante.Figura 4. Curva tiempo-costo para la actividad (i,j).Por lo general la grafica se basa en dos puntos: el normal y el intensivo o de quiebre. El punto normal da el costo y el tiempo necesario cuando la actividad se realiza en la forma normal, sin incurrir en costos adicionales (horas extras de mano de obra, equipo o materiales especiales para ahorrar tiempo, etc.), Para acelerar la actividad. Por el contrario, el punto de quiebre proporciona el tiempo y el costo necesario cuando se realiza la actividad en forma intensiva o de quiebre, esto es se acelera completamente sin reparar en costos, con el fin de reducir su tiempo de duración lo mas que se pueda. Como una aproximación, se supone entonces que todos los trueques intermedios entre tiempo y costos son posibles y que se encuentran sobre el segmento de línea que une a estos dos puntos. (Obsérvese en el segmento de línea oscuro en la Fig. 4). Así, las únicas estimaciones que tienen que obtener el personal del proyecto son el costo y el tiempo para estos dos puntos.El objetivo fundamental del CPM es determinar el trueque entre tiempo y costo que debe emplearse en cada actividad para cumplir con el tiempo de terminación del proyecto que se programo a un costo mínimo. Una forma de determinar lacombinación optima del tiempo y costo es aplicar programación lineal. para descubrir esto, es necesario introducir notación nueva, parte de la cual se resume en la figura 4. SeaDij = tiempo normal para la actividad (i , j)
CDij = costo (directo) normal para la actividad (i , j)dij = tiempo de quiebre para la actividad (i , j)Cdij = costo (directo) de quiebre para la actividad (i , j)Las variables de decisión para el problema son xij dondexij = tiempo de duración de la actividad (i , j)
Entonces existe una varible de decisión xij para cada actividad, pero no lo hay par alos valores de i y j que no tienen una actividad correspondiente.Para expresar el costo directo de la actividad ( i, j) como una función (lineal) de Xjj denótese la pendiente de la línea que pasa por los puntos normal y de quiebre para la actividad (i , j) por
tambien definase Kij como la intersección con el eje del costo directo de esta linea, com se muestra en la fig. 4, por tanto,costo directo de la actividad (i , j) = Kij + Sij xij,en consecuencia,
costo directo total del proyecto = en donde la sumatoria se extiende sobre todas las actividades (i , j). Ahora se puede establecer y formular matemáticamente el problema. El problema: dado un tiempo T (máximo) de terminación del proyecto, selecciónese la xjj que minimice el costo directo total del proyecto.Formulación De Programación Lineal. Para tomar en cuenta el tiempo de terminación del proyecto en la formulación de programación lineal del problema, se necesita una variable más para cada evento. Esta variable adicional esyk = tiempo más próximo (desconocido) para el evento k, el cual es una función determinística de Xij.Cada yk es una variable auxiliar, es decir, una variable que se introduce al modelo por ser conveniente en la formulación y que no representa una decisión. El método simplex trata a las variables auxiliares igual que a las variables de decisión (xij ) normales.Para ver cómo se introducen las yk a la formulación, considérese el evento 7 de la figura 1 Por definición, su tiempo más próximo es:y7 = máx {y4 + x47, y5 + x57},En otras palabras y7 es la cantidad más pequeña tal que las dos restricciones siguientes se cumplen:
y4 + x47 < y7
y5 + x45 < y7,
por lo que estas dos restricciones se pueden incorporar directamente a la formulación de programación lineal (después de pasar y7 al lado izquierdo para obtener la forma apropiada). Aún más, adelante se verá por qué la solución óptima que se obtiene con el método simples para el modelo completo hará de manera automática que el valor de y7 sea la cantidad más pequeña que ,satisface estas restricciones, por lo que no se necesitan más restricciones para incorporar la definición de y7 al modelo.Dentro del proceso e incorporación de estas restricciones para todos los eventos, se tiene que cada variable xij aparecerá en exactamente una restricción de este tipo,
que se puede expresar en la forma apropiada como
Para continuar con los preparativos para escribir el modelo completo de programación lineal, se etiquetan Evento 1 = inicio del proyectoEvento n = terminación del proyecto,con lo que
=0
= tiempo de terminación. .
Nótese también que es una constante fija que puede eliminarse de la función objetivo, de manera que minimizar el costo directo total para el proyecto es
equivalente a maximizar Por tanto, el problema de programación lineal
es encontrar las (y las correspondientes) tales que
Maximizar
Sujeta a:
Para todas las actividades (i , j)
Desde un punto de vista computacional, este modelo se puede mejorar algo al
sustituir todas las por
en todo el modelo, para que el primer conjunto de restricciones funcionales (
) se sustituya por las restricciones de no negatividad
Es conveniente también introducir restricciones de no negatividad para el resto de las variables:
aunque estas variables ya estaban forzadas a ser no negativas al establecer y1 = 0, debido a
las restricciones y
Una propiedad interesante de una solución óptima para este modelo es que (en circunstancias normales) toda trayectoria de la red será una ruta crítica que requiere un tiempo T, La razón es que una solución de este tipo satisface las
restricciones mientras que evita los costos adicionales en que se incurre por acortar el tiempo de cualquier trayectoria.
La clave de esta formulación es la manera en que se introducen las al modelo
mediante las restricciones , con el fin de proporcionar los tiempos
más próximos para los respectivos eventos (dados los valores de las en la solución básica factible actual). Como los tiempos más próximos se tienen que
obtener en orden, todas estas son necesarias nada más para obtener
finalmente el valor correcto de (para los valores actuales de las ), reforzando
así la restricción . Sin embargo, obtener el valor correcto requiere que el
valor de cada (incluso el de ) sea la cantidad más pequeña que satisface
todas las restricciones . Ahora se hará una descripción breve de por qué (en circunstancias normales) esta propiedad se cumple para una solución óptima.
Considérese una solución para las variables tal que toda trayectoria de la red es
crítica y requiere un tiempo T. Si los valores de las satisfacen la propiedad
anterior, entonces las son los verdaderos tiempos más pr6ximos con
exactamente y la solución completa para las y satisface todas las
restricciones. Sin embargo, si alguna se hace un poco más grande, esto crearía
una reacción en cadena en la que alguna se tendría que hacer un poco más
grande para satisfacer todavía las restricciones etc., hasta que en
última instancia, deba hacerse un poco más grande y se viole la restricción
. La única manera de evitar esto con una un poco más grande, es hacer que los tiempos de duración de algunas actividades (posteriores al evento i) sean un poco más pequeñas, aumentando con esto el costo. Por lo tanto, una solución
óptima evitará que las sean más grandes de lo necesario para satisfacer las
restricciones .
El problema, como se estableció aquí, supone que se ha fijado una fecha de entrega específica T (tal vez por contrato) para la terminación del proyecto. En realidad, algunos proyectos no tienen una fecha de entrega, en cuyo caso no está claro el valor que debe asignarse a T en la formulación de programación lineal. En este tipo de situaciones, la decisión sobre T (que resulta ser la duración del proyecto en la solución óptima), de hecho depende de cuál es el mejor trueque entre el costo total y el tiempo total del proyecto. La información básica que se necesita para tomar esta decisión es cómo cambia el costo directo total mínimo al cambiar el valor de T en la formulación anterior, como se muestra en la figura 5. Esta información se puede obtener cuando se usa progranlflci6n lineal parametrica para obtener la solución óptima como una funci6n de T en todo el intervalo. Existen procedimientos aún más eficientes, para obtener esta información, que explotan la estructura especial del problema. La figura 5 proporciona una base útil para la toma de decisiones del administrador
sobre el valor de T (y la solución óptima correspondiente para ) cuando los efectos importantes de la duración del proyecto (distintos a los costos directos) son en esencia intangible. Ahora bien, cuando estos otros efectos que son básicamente financieros (costos indirectos ), es apropiado combinar la curva del costo directo total de la figura 5 con una curva de costo indirecto total mínimo (supervisión, instalaciones, intereses, multas contractuales) contra t, como se muestra en la figura 6. La suma de estas curvas proporcionará la curva del costo
total mínimo del proyecto para distintos valores de T. El valor óptimo de T será entonces aquél que minimice esta curva de costo total.
7. Elección entre PERT y CPM
La elección entre el enfoque de las tres estimaciones de PERTy el método de trueques entre el tiempo y el costo del CPM depende fundamentalmente del tipo de proyecto y de los objetivos gerenciales. El PERT es en particular apropiado cuando se maneja mucha incertidumbre al predecir los tiempos de las actividades y cuando es importante controlar de una manera efectiva la programación del proyecto; por ejemplo, la mayor parte de los proyectos de investigación y desarrollo caen dentro de esta categoría. Por otro lado, el CPM resulta muy apropiado cuando se pueden predecir bien los tiempos de las actividades(quizá con base en la experiencia) y cuando estos tiempos se pueden ajustar con facilidad (por ejemplo, si se cambian tamaños de brigadas), al igual que cuando es importante planear una combinación apropiada entre el tiempo y el costo del proyecto. Este último tipo lo representan muchos proyectos de construcción y mantenimiento. En la actualidad, las diferencias entre las versiones actuales de PERT y CPM no son tan marcadas como se han descrito. Muchas versiones de PERT permiten emplear una sola estimación (la más probable) para cada actividad y omiten así la investigación probabilística. Una versión llamada PERT/Costo considera también combinaciones de tiempo y costo en forma parecida al CPM.
8. Diferencias Entre PERT y CPM
La diferencia entre PERT y CPM es la manera en que se realizan los estimados de tiempo. E1 PERT supone que el tiempo para realizar cada una de las actividades es una variable aleatoria descrita por una distribución de probabilidad. E1 CPM por otra parte, infiere que los tiempos de las actividades se conocen en forma determinísticas y se puede variar cambiando el nivel de recursos utilizados.La distribución de tiempo que supone el PERT para una actividad es una distribución beta. La distribución para cualquier actividad se define por tres estimados:
1. el estimado de tiempo más probable, m; 2. el estimado de tiempo más optimista, a; y 3. el estimado de tiempo más pesimista, b.
La forma de la distribución se muestra en la siguiente Figura. E1 tiempo más probable es el tiempo requerido para completar la actividad bajo condiciones normales. Los tiempos optimistas y pesimistas proporcionan una medida de la incertidumbre inherente en la actividad, incluyendo desperfectos en el equipo, disponibilidad de mano de obra, retardo en los materiales y otros factores.
Con la distribución definida, la media (esperada) y la desviación estándar, respectivamente, del tiempo de la actividad para la actividad Z puede calcularse por medio de las fórmulas de aproximación.
El tiempo esperado de finalización de un proyecto es la suma de todos los tiempos esperados de las actividades sobre la ruta crítica. De modo similar, suponiendo que las distribuciones de los tiempos de las actividades son independientes (realísticamente, una suposición fuertemente cuestionable), la varianza del proyecto es la suma de las varianzas de las actividades en la ruta crítica. Estas propiedades se demostrarán posteriormente.En CPM solamente se requiere un estimado de tiempo. Todos los cálculos se hacen con la suposición de que los tiempos de actividad se conocen. A medida que el proyecto avanza, estos estimados se utilizan para controlar y monitorear el progreso. Si ocurre algún retardo en el proyecto, se hacen esfuerzos por lograr que el proyecto quede de nuevo en programa cambiando la asignación de recursos.
FUENTE: http://www.monografias.com/trabajos13/planeco/planeco.shtml
El PERT/CPM fue diseñado para proporcionar diversos elementos útiles de información para los administradores de proyectos.
Este método expone la ruta crítica de un proyecto; esto es, las actividades que limitan la duración de un proyecto.
Antecedentes
PERT/CPM: Método de la Ruta Crítica
En otras palabras, para lograr que el proyecto se realice pronto, las actividades de la ruta crítica deberán realizarse pronto.
Por otra parte, si una actividad de la ruta crítica se retrasa, el proyecto como un todo se retrasará en la misma cantidad.
Antecedentes
PERT/CPM: Método de la Ruta Crítica
Las actividades que no están en la ruta crítica tienen una cierta cantidad de holgura; es decir, pueden empezar más tarde y permiten que el proyecto como un todo se mantenga conforme a lo programado.
El PERT/CPM identifica estas actividades y la cantidad de tiempo disponible para retardos.
¿Pero qué significa PERT/CPM?
PERT: Program Evaluation and Review Technique
Maneja tiempos inciertos de las actividades del proyecto.
CPM: Critical Path Method
Maneja tiempos conocidos de las actividades del proyecto.
Actualmente se ha tomado lo mejor de ambos métodos y se han vuelto uno solo, conocido como Método de la Ruta Crítica.
Objetivo general del Método de la Ruta Crítica
"Que se desee el costo de operación de un proyecto más bajo posible dentro de un tiempo límite disponible."
¿Cuáles son sus aplicaciones?
Ejemplos:
Investigación y desarrollo de nuevos productos.
Construcción de plantas, edificios y carreteras.
Diseño e instalación de sistemas nuevos.
¿Cuáles son las preguntas que el PERT/CPM contesta a los tomadores de decisiones?
¿Cuál es el tiempo total para terminar el proyecto?.
¿Cuáles son las fechas programadas de inicio y de terminación para cada una de las actividades específicas?.
¿Cuáles son las preguntas que el PERT/CPM contesta a los tomadores de decisiones?
¿Qué actividades son "críticas" y deben terminarse exactamente como se programaron para mantener el proyecto a tiempo?.
¿Cuánto se pueden retardar las actividades "no críticas" antes de incrementar el tiempo de terminación del proyecto?.
Procedimiento para llevar a cabo el PERT/CPM
La trayectoria más larga determina el tiempo total requerido para la finalización del proyecto.
Si se retardan las actividades de la trayectoria más larga, la totalidad del proyecto también se retardará, por lo que la más larga es la "ruta crítica".
Las actividades de la ruta crítica se conocen como "actividades críticas".
Ejemplo de optimización de un proyecto utilizando PERT/CPM
Red del Proyecto
Utilizando el software "Manager" para resolver el modelo...
Utilizando el software "Manager" para resolver el modelo...
Entonces la "ruta crítica" del proyecto está dada por las siguientes actividades:
Actividades críticas del proyecto
Si el tiempo total requerido para terminar el proyecto es demasiado largo...
Deberá tomarse la decisión de dónde y cómo reducir el tiempo de las actividades críticas.
Si se modifica cualquiera de los tiempos de realización de las actividades, los cálculos de la ruta crítica deberán repetirse para determinar el impacto sobre el programa de actividades y sobre el tiempo de terminación del proyecto.
FUENTE: http://www.gestiopolis.com/recursos2/documentos/fulldocs/ger/pertcpmrob.htm
FUENTE: http://www.dexcel.org/espanol/conceptocalidad.htm
UNIDAD 3: PROGRAMACION NO LINEAL.
PLANTEAMIENTO DE PROBLEMAS DE PROGRAMACION NO LINEAL
Una suposición importante de programación lineal es que todas sus funciones (Función objetivo y funciones de restricción) son lineales. Aunque, en esencia, esta suposición se cumple para muchos problemas prácticos, es frecuente que no sea así. De hecho, muchos economistas han encontrado que cierto grado de no linealidad es la regla, y no la excepción, en los problemas de planeación económica, por lo cual, muchas veces es necesario manejar problemas de programación no lineal. De una manera general, el problema de programación no lineal consiste en
encontrar para maximizar , sujeta a
en donde y las son funciones dadas de n variables de decisión. No se dispone de un algoritmo que resuelva todos los problemas específicos que se ajustan a este formato. Sin embargo, se han hecho grandes logros en lo que se refiere a algunos casos especiales , haciendo algunas suposiciones sobre las funciones, y la investigación sigue muy activa.
OPTIMIZACION CLASICA:
PUNTOS DE INFLEXION
DEFINICIÓN
El punto que, en una función continua, separa la parte convexa de la cóncava, se llama punto de inflexión de la función. En ellos la función no es cóncava ni convexa sino que hay cambio de concavidad a convexidad o al revés.
Los puntos de inflexión están caracterizados por:
TEOREMA
Sea la ecuación de una función.
Si no existe, y la derivada cambia de signo al pasar por el valor de x=a, entonces, el punto de la función de abscisa x=a es un punto de inflexión.
Clasificación de los puntos de inflexión
Nota
Los puntos de inflexión donde la función es derivable, tienen la característica de tener una recta tangente que cruza la gráfica de f.
Ejemplo:
El punto x=1 es un punto de inflexión, puesto que antes de x=1 la derivada segunda es negativa (convexa) y después de x=1 es positiva (cóncava).
TABLA DE VALORESX Y
1 -2 P. INFLEXIÓN
FUENTE: http://thales.cica.es/rd/Recursos/rd99/ed99-0295-01/punto7/punto7.html
Puntos de inflexión:
Son puntos en los que la función pasa de ser cóncava a ser convexa o viceversa.
Una condición necesaria para que un punto sea punto de inflexión es que la segunda derivada se anule en él. Por este motivo, para encontrarlos lo que haremos será calcular la segunda derivada de la función e igualarla
a cero. Si las soluciones de la ecuación están en el dominio de nuestra función, dicha solución es punto de inflexión. Es decir, si n
es el punto de inflexión.
FUENTE: http://html.rincondelvago.com/estudio-de-una-funcion.html
MAXIMOS Y MINIMOS
Sea f(x) una función y xo un punto del dominio.
DEFINICIÓN
La función f(x) presenta un máximo relativo en xo , cuando existe un entorno E(xo) tal que:
La función f(x) presenta un mínimo relativo en xo , cuando existe un entorno E(xo) tal que:
Son puntos que se distinguen por ser aquellos cuya imagen es la mayor o la menor (máximo - mínimo) de todas las imágenes “de los alrededores”. No se excluye que haya otros puntos "alejados" de xo cuya imagen sea mayor o menor que f(xo).
A los máximos y mínimos relativos se los llama extremos relativos o simplemente extremos.
TEOREMA (CONDICIÓN NECESARIA PARA LA EXISTENCIA DE EXTREMOS)
Sea una función cuyo dominio es D=Dom(f) y xo un punto del dominio.
Demostración
Nota
La recta tangente en un extremo es paralela al eje OX, luego la derivada (la pendiente de la recta tangente) es cero.
Ejemplo:
Los puntos que anulan la derivada son los candidatos a ser extremos, pero no puede asegurarse que lo sean. A estos puntos se les llama puntos críticos.
TABLA DE VALORESX Y
1/2 -1/4 P. Crítico
FUENTE: http://thales.cica.es/rd/Recursos/rd99/ed99-0295-01/punto5/punto5.html
PROBLEMAS NO RESTRINGIDOS:
MULTIPLICADORES DE LAGRANGE
TEOREMA:
Si un problema de optimización con restricciones de igualdad de la forma:
opt f(x)g1(x)=0.......gm(x)=0
tiene un óptimo local (máximo o mínimo) en el punto x0, donde además las funciones f(x),g1(x),...,gm(x) admiten derivadas parciales de primer orden continuas y los vectores gradientes de las funciones de restricción son linealmente independientes en x0.
Entonces existen unos números reales l1,...,lm, llamados multiplicadores de Lagrange tales que:
Es decir, el vector gradiente de la función objetivo en el óptimo es combinación lineal de los gradientes en el óptimo de las funciones de restricción.
Los multiplicadores de Lagrange también se suelen llamar pesos o variables duales asociadas a las restricciones y tienen importantes aplicaciones prácticas en la Economía, como se verá más adelante.
De nuevo, el teorema anterior establece una condición necesaria de optimalidad pero no suficiente, en el sentido de que todo óptimo verifica la condición anteiror pero podrían existir puntos cumpliendo esta misma condición que no fueran soluciones del problema. Para poder utilizar esta condición en la localización de óptimos de un problema, deberá procederse de la siguiente manera:
El teorema no podrá ser utilizado si no se verifican las hipótesis de regularidad en él impuestas (derivabilidad y independencia lineal de los vectores gradientes de las restricciones). El no verificarse estas hipótesis puede provocar que algún punto óptimo no pueda ser localizado (ejemplo).
En primer lugar, por ser solución factible, todo punto óptimo debe verificar las restricciones (sistema de m ecuaciones).
La relación de dependencia lineal de los vectores gradiente permite obtener n ecuaciones adicionales que todo óptimo debe verificar.
De esta forma se obtiene un sistema de n+m ecuaciones con n+m incógnitas (las n variables de decisión y los m multiplicadores de Lagrange). Las soluciones de este sistema son los candidatos a óptimos del problema, estos puntos se llaman puntos estacionarios. Además de obtenerse las coordenadas de los posibles óptimos, se obtienen los valores de sus multiplicadores de Lagrange asociados. La utilidad de estos valores se verá posteriormente.
Entre las posibles soluciones del problema se haría necesario seleccionar cuales lo son realmente; para ello son necesarias la utilización de condiciones suficientes de optimalidad.
A continuación se muestran unos ejemplos que pueden ayudar a clarificar la forma de proceder para buscar óptimos de problemas con restricciones de igualdad.
EJEMPLO:
Dado el problema de optimización:
max x-y+2zx^2+y^2=4x+y+z=5
En primer lugar, obsérvese que todas las funciones que intervienen en el problema son de tipo polinomial y por tanto no tienen ningún problema de diferenciabilidad. Las funciones que determinan las restricciones (recordar que las restricciones siempre se suponen igualadas a cero) son:
g1(x,y,z)=x^2+y^2-4g2(x,y,z)=x+y+z-5
y sus respectivos vectores gradientes son:
Grad g1(x,y,z)=(2x,2y,0)Grad g2(x,y,z)=(1,1,1)
estos dos vectores son linealmente independientes salvo en el caso (x,y,z)=(0,0,t), sin embargo, estos puntos no verifican las restricciones del problema, de forma que su exclusión no supone ninguna limitación.
El sistema que determinará las posibles soluciones del problema es:
x^2+y^2-4=0x+y+z-5=01+l1*2x+l2=0-1+l1*2y+l2=02+l2=0
Las soluciones de este sistema son:
x=0.632 y=1.897 z=2.470 l1=0.790 l2=-2x=-0.632 y=-1.897 z=7.520 l1=-0.790 l2=-2
Puede asegurarse que si el problema tiene algún óptimo, éste debe ser alguno de los puntos anteriores. Hace falta un criterio que permita decidir si realmente son óptimos.
El teorema de los multiplicadores de Lagrange establece una condición necesaria de optimalidad pero no suficiente. El hecho de que no sea condición suficiente hace que no pueda asegurarse que los puntos que la cumplen sean óptimos. Sin embargo, al ser una condición necesaria, puede utilizarse para demostrar que un punto no es óptimo.
EJEMPLO:
En este ejemplo, se prueba que el punto (0,1,1) no puede ser solución local del problema:
min x*z-1/yx*z+x=0x+y+z=2
En primer lugar, se trata de un problema que se ajusta perfectamente a las condiciones impuestas en el teorema de los multiplicadores y además el punto dado obviamente verifica las restricciones. Sin embargo, si dicho punto fuera mínimo del problema, deberían existir dos números reales l1 y l2 tales que:
Grad f(0,1,1)+l1*Grad g1(0,1,1)+l2 *Grad g2(0,1,1)=0
pero este sistema de ecuaciones no tiene solución; por tanto, el punto (0,1,1) no puede ser solución del problema.
El último ejemplo muestra como el método para localizar óptimos dado por Lagrange no siempre es válido, ya que tiene importantes limitaciones, no solo en lo que a condiciones de diferenciabilidad se refiere.
EJEMPLO:
El programa matemático
min x^2+y^2(x-1)^3-y^2=0
alcanza su mínimo global en el punto (1,0), como puede comprobarse por el método de eliminación de variables. Sin embargo no puede encontrarse un l tal que
Grad f(1,0)+l*Grad g(1,0)= (0,0)
Por tanto el punto óptimo parece que no cumple una condición que necesariamente todo óptimo debe cumplir. La razón de esta aparente contradicción está en el hecho de que este programa no verifica las hipótesis de regularidad exigidas en el teorema de los multiplicadores de Lagrange ya que el vector gradiente Grad g(1,0)= (0,0) no es linealmente independiente.
FUENTE: http://usuarios.lycos.es/royel/principal/13/5/4/
Se pueden utilizar los multiplicadores de Lagrange para resolver los problemas no lineales en los cuales las restricciones son igualdades. Consideramos los del tipo siguiente:
(1) Para resolverlo, asociamos un multiplicador l 1 con la i-ésima restricción y formamos el lagrangiano
(2)
Donde son constantes (desconocidas) denominadas multiplicadores de Lagrange. Después resuélvase el sistema de n + m ecuaciones:
Teorema : Si existe una solución al programa (1), ésta se encuentra contenida
entre las soluciones al sistema anterior, siempre y cuando
y todas tengan primeras derivadas parciales continuas y la matriz jacobina de m x n,
tenga rango m en X = X* El método de los multiplicadores de Lagrange es equivalente a emplear las ecuaciones de restricción para eliminar algunas de las variables x de la función objetivo y resolver después un problema de maximización sin restricciones para las restantes variables x. Ejemplo: Una compañía planea gastar 10,000 dólares en publicidad. Cuesta 3,000 dólares un minuto de publicidad en la televisión y 1,000 dólares un minuto de publicidad en la radio. Si la empresa compra x minutos de comerciales en la televisión y y minutos de comerciales en la radio, su ingreso, en miles de dólares, está dado
por . ¿Cómo puede la empresa maximizar su ingreso? Solución: Se tiene el programa no lineal siguiente
Entonces Hacemos
Obsérvese que 10 - 3x -y = 0 se convierte en la restricción 3x + y = 10. La
ecuación (1) da y la ecuación (2) da
Así, , o
Sustituyendo (4) y (5) en la (3), obtenemos, o . Entonces (4) y (5) nos dan
El hessiano para es
Ya que cada mejor principal de primer orden es negativo, y
, es una función cóncava. La restricción es lineal y, por lo tanto da la solución óptima para el programa no lineal. Así, la empresa tendría que comprar 69/28 minutos de tiempo de televisor y 73/28 minutos de tiempo de radio. Ya que l = ¼ , el gasto de un D extra (en miles) (para un D pequeño) aumentaría los ingresos de la empresa en aproximadamente 0.25 D dólares (en miles). En general, si la empresa tiene a dólares para gastar en la publicidad, se puede
demostrar que . Vemos que si gasta más dinero en la publicidad, el incremento en el ingreso por cada dólar adicional para la publicidad se hace más pequeño.
FUENTE: http://www.itlp.edu.mx/publica/tutoriales/investoper2/tema12.htm
UNIDAD 4: TEORIA DE INVENTARIOS.
SISTEMAS DE ADMINISTRACION Y CONTROL
Cuando las empresas, producto de la globalización de sus negocios, empiezan a tener filiales y representaciones en diferentes partes del orbe, surge la necesidad de implementar y/o adecuar los sistemas de administración por cuanto la forma y los diferentes requerimientos operativos han cambiado significativamente producto de estas nuevas formas de manifestación empresarial.
Las problemáticas que se presentan pasan por problemas de comunicación e información hasta de administración logística de operaciones y estrategias.
En el ámbito de la comunicación e información pareciese que sistemas de redes globalizadas y algunas privadas de las empresas solucionan por sí mismas esta necesidad, ahora extendida a través de casi todo el mundo, pero nos enfrentamos ahora a nuevas situaciones complejas, pues los receptores y encargado de interpretar, aplicar y replicar los mensajes e intenciones de la administración pertenecen y han sido formados en culturas a veces muy diferentes a las nuestras. Es así como por ejemplo la acepción "política agresiva" o "campaña agresiva", entre otras, pueden ser interpretadas de diferentes formas, dependiendo de la formación del receptor, pasando desde la sana incorporación de nuevos y mayores esfuerzos hasta la violencia manifiesta aplicada en un verdadero campo de batalla de compra-venta agresivo.
Sistemas de información administrativos eficientes a disposición de las empresas existen muchos y variados, cumpliendo la gran mayoría de ellos expectativas y necesidades de administración y control de los diferentes flujos de información, pero ahora ante la globalización de los mercados, administradores y expertos tienen el nuevo desafió de orientar, adecuar y anticipar el efecto que estos tendrán en los diferentes usuarios internos, con diferentes formaciones y características técnicas, de una misma empresa.
Respecto a la administración de operaciones y estrategias, ahora se requiere estudios y especificaciones precisas de los diferentes mercados objetivos, adecuando estrategias y productos a estas realidades. El producto único y uniforme es ya una utopía reservada sólo a productos emblemáticos de aceptación mundial representativos generalmente de grandes marcas.
Si bien lo anterior se enmarca dentro de parámetros de la aplicación de estrategias específicas para los diferentes mercados buscando posesionarse de los mismos acertadamente, ejemplos de exageración existen varios, destacándose el de la empresa estadounidense B&D de electrodomésticos que llegó a tener 260 modelos diferentes para una misma herramienta, en un intento de cubrir demandas del auspicioso mercado europeo, cuando en realidad sólo se necesitaban no más de diez.
La comunicación, el manejo de la información y la administración logística de operaciones y estrategias debe adecuarse necesariamente de acuerdo al nivel de actividad y los mercados que las empresas pretenden explotar. La aplicación de políticas, sistemas y estrategias planas no adaptadas es sinónimo de gran riesgo.
Nuestras empresas han incursionado en diferentes mercados, muchas de ellas han comprendido y así lo han materializado, que se debe adecuar ante estos nuevos desafíos no tan sólo los productos, sino que también las estrategias y la administración de las operaciones mismas.
No es lo mismo tratar promocionar, colocar y vender chocolates en México que en China. Costumbres, idiomas, gustos, administración de salarios, formas de hacer negocios y trato comercial difieren gravitantemente de un país a otro, además de condiciones gubernamentales, legales y de distribución física.
Ahora hay que globalizar la administración.
FUENTE: http://www.unap.cl/p4_unap/site/artic/20040825/pags/20040825090949.html
ADMINSTRACION DE INVENTARIOS
Concepto
Es la eficiencia en el manejo adecuado del registro, de la rotación y evaluación del inventario de acuerdo a como se clasifique y que tipo reinventario tenga la empresa, ya que a través de todo esto determinaremos los resultados (utilidades o pérdidas) de una manera razonable, pudiendo establecer la situación financiera de la empresa y las medidas necesarias para mejorar o mantener dicha situación.
Finalidad de la Administración de Inventarios
La administración de inventario implica la determinación de la cantidad de inventario que deberá mantenerse, la fecha en que deberán colocarse los pedidos y las cantidades de unidades a ordenar. Existen dos factores importantes que se toman en cuenta para conocer lo que implica la administración de inventario:
1. Minimización de la inversión en inventarios
El inventario mínimo es cero, a empresa podrá no tener ninguno y producir sobre pedido, esto no resulta posible para la gran mayoría de las empresa, puesto que debe satisfacer de inmediato las demandas de los clientes o en caso contrario el pedido pasara a los competidores que puedan hacerlo, y deben contar con inventarios para asegurar los programas d producción. La empresa procura minimizar el inventario porque su mantenimiento es costoso. Ejemplo: al tener un millón invertido en inventario implica que se ha tenido que obtener ese capital a su costo actual así como pagar los sueldos de los empleados y las cuentas de los proveedores. Si el costo fue del 10% al costo de financiamiento del inventario será de 100.000 al año y la empresa tendrá que soportar los costos inherentes al almacenamiento del inventario.
2. Afrontando la demanda
Si la finalidad de la administración de inventario fuera solo minimizar las ventas satisfaciendo instantáneamente la demanda, la empresa almacenaría cantidades excesivamente grandes del producto y así no incluiría en los costos asociados con una alta satisfacción ni la perdida de un cliente etc. Sin embargo resulta extremadamente costoso tener inventarios estáticos paralizando un capital que se podría emplear con provecho. La empresa debe determinar el nivel apropiado de
inventarios en términos de la opción entre los beneficios que se esperan no incurriendo en faltantes y el costo de mantenimiento del inventario que se requiere.
Importancia
La administración de inventario, en general, se centra en cuatro aspectos básicos:
1. Cuantas unidades deberían ordenarse o producirse en un momento dado. 2. En que momento deberían ordenarse o producirse el inventario. 3. Que artículos del inventario merecen una atención especial. 4. Puede uno protegerse contra los cambios en los costos de los artículos del inventario.
El inventario permite ganar tiempo ya que ni la producción ni la entrega pueden ser instantánea, se debe contar con existencia del producto a las cuales se puede recurrir rápidamente para que la venta real no tenga que esperar hasta que termine el cargo proceso de producción.
Este permite hacer frente a la competencia, si la empresa no satisface la demanda del cliente sé ira con la competencia, esto hace que la empresa no solo almacene inventario suficiente para satisfacer la demanda que se espera, si no una cantidad adicional para satisfacer la demanda inesperada.
El inventario permite reducir los costos a que da lugar a la falta de continuidad en le proceso de producción. Además de ser una protección contra los aumentos de precios y contra la escasez de materia prima.
Si la empresa provee un significativo aumento de precio en las materias primas básicas, tendrá que pensar en almacenar una cantidad suficiente al precio mas bajo que predomine en le mercado, esto tiene como consecuencia una continuación normal de las operaciones y una buena destreza de inventario.
La administración de inventario es primordial dentro de un proceso de producción ya que existen diversos procedimientos que nos va a garantizar como empresa, lograr la satisfacción para llegar a obtener un nivel óptimo de producción. Dicha política consiste en el conjunto de reglas y procedimientos que aseguran la continuidad de la producción de una empresa, permitiendo una seguridad razonable en cuanto a la escasez de materia prima e impidiendo el acceso de inventario, con el objeto de mejorar la tasa de rendimiento. Su éxito va estar enmarcado dentro de la política de la administración de inventario:
1. Establecer relaciones exactas entre las necesidades probables y los abastecimientos de los diferentes productos.
2. Definir categorías para los inventarios y clasificar cada mercancía en la categoría adecuada.
3. Mantener los costos de abastecimiento al mas bajo nivel posible. 4. Mantener un nivel adecuado de inventario. 5. Satisfacer rápidamente la demanda.
6. Recurrir a la informática.
Algunas empresas consideran que no deberían mantener ningún tipo de inventario porque mientras los productos se encuentran en almacenamiento no generan rendimiento y deben ser financiados. Sin embargo es necesario mantener algún tipo de inventario porque:
1. La demanda no se puede pronosticar con certeza. 2. Se requiere de un cierto tiempo para convertir un producto de tal manera que se
pueda vender.
Además de que los inventarios excesivos son costosos también son los inventarios insuficientes, por que los clientes podrían dirigirse a los competidores si los productos no están disponibles cuando los demandan y de esta manera se pierde el negocio. La administración de inventario requiere de una coordinación entre los departamentos de ventas, compras, producción y finanzas; una falta de coordinación nos podría llevar al fracaso financiero.
En conclusión la meta de la administración de inventario es proporcionar los inventarios necesarios para sostener las operaciones en le más bajo costo posible. En tal sentido el primer paso que debe seguirse para determinar el nivel optimo de inventario son, los costos que intervienen en su compra y su mantenimiento, y que posteriormente, en que punto se podrían minimizar estos costos.
Características y Análisis del Inventario
Es necesario realizar un análisis de las partidas que componen el inventario. Debemos identificar cuales son las etapas que se presentaran en le proceso de producción, las comunes o las que se presenta en su mayoría son:
o Materia Prima o Productos en proceso o Productos terminados o Suministros, repuestos
En caso de materia prima, esta es importada o nacional, si es local existen problemas de abastecimiento, si es importada el tiempo de aprovisionamiento. La obsolencia de los inventarios, tanto por nueva tecnología como por desgaste tiempo de rotación, tienen seguro contra incontinencias, deberá realizarse la inspección visual de dicha mercadería. Se debe saber la forma de contabilización de los inventarios. Correcta valorización de la moneda empleada para su contabilización.
Se debe conocer la política de administración de los inventarios: con quienes se abastecen, que tan seguro es, preocupación por tener bajos precios y mejor calidad; cuantos meses de ventas mantienen en materia prima, productos en procesos y productos terminados; cual es la rotación de los inventarios fijada o determinada. Áreas involucradas en la administración ya sea el Gerente de
Producción, Gerente de Marketing, Gerente de Ventas o Finanzas, etc. Como se realiza el control de los inventarios en forma manual o computarizada. Tecnología empleada.
Naturaleza y liquidez de los inventarios, características y naturaleza del producto, características del mercado, canales de distribución, analizar la evolución y la tendencia.
Técnicas de Administración de Inventarios
Los métodos comúnmente empleados en le manejo de inventarios son:
o El sistema ABC. o El modelo básico de cantidad económico de pedido CEP.
El Sistema ABC
Una empresa que emplea esté sistema debe dividir su inventario en tres grupos: A, B, C. en los productos "A" se ha concentrado la máxima inversión. El grupo "B" esta formado por los artículos que siguen a los "A" en cuanto a la magnitud de la inversión. Al grupo"C" lo componen en su mayoría, una gran cantidad de productos que solo requieren de una pequeña inversión. La división de su inventario en productos A, B y C permite a una empresa determinar el nivel y tipos de procedimientos de control de inventario necesarios. El control de los productos "A" debe ser el mas cuidadoso dada la magnitud de la inversión comprendida, en tanto los productos "B" y"C" estarían sujetos a procedimientos de control menos estrictos.
Modelo Básico de Cantidad Económica de Pedidos
Uno de los instrumentos mas elaborados para determinar la cantidad de pedido optimo de una articulo de inventario es le modelo básico de cantidad económica de pedido CEP. Este modelo puede utilizarse para controlar los artículos "A" de las empresas, pues toma en consideración diversos costos operacionales y financieros, determina la cantidad de pedido que minimiza los costos de inventario total. El estudio de este modelo abarca: 1) los costos básicos, 2) Un método grafico, 3) un método analítico.
Costos Básicos. Excluyendo el costo real de la mercancía, los costos que origina el inventario pueden dividirse en tres grandes grupos: costos de pedido, costos de mantenimiento de inventario y costo total. Cada uno de ellos cuenta con algunos elementos y características claves.
Costos de Pedidos. Incluye los gastos administrativos fijos para formular y recibir un pedido, esto es, el costo de elaborar una orden de compra, de efectuar los limites resultantes y de recibir y cortejar un pedido contra su factura. Los costos de
pedidos se formulan normalmente en términos de unidades monetarias por pedido.
Costos de Mantenimiento de Inventario: Estos son los costos variables por unidad resultantes de mantener un artículo de inventario durante un periodo específico.
En estos costos se formulan en términos de unidades monetarias por unidad y por periodo. Los costos de este tipo presentan elementos como los costos de almacenaje, costos de seguro, de deterioro, de obsolescencia y el más importante el costo de oportunidad, que surge al inmovilizar fondos de la empresa en el inventario.
Costos Totales. Se define como la suma del costo del pedido y el costo de inventario. En le modelo (CEP), el costo total es muy importante ya que su objetivo es determinar el monto pedido que lo minimice.
Método Grafico. El objetivo enunciado del sistema CEP consiste en determinar el monto de pedido que reduzca al mínimo el costo total del inventario de la empresa. Esta cantidad económica de pedido puede objetarse en forma gráfica representando los montos de pedido sobre el eje x, y los costos sobre el eje y, el costo total mínimo se representa en el punto señalado como CEP. El CEP se encuentra en el punto en que se cortan la línea de costo de pedido y la línea de costo de mantenimiento en inventario. La función de costo de pedido varía en forma inversa con la cantidad de pedido. Esto significa que a medida que aumenta el monto de pedido su costo de pedido disminuye por pedido. Los costos de mantenimiento de inventario se relacionan directamente con las cantidades de pedido. Cuanto más grande sea el monto del pedido, tanto mayor será el inventario promedio, y por consiguiente, tanto mayor será el costo de mantenimiento de inventario.
La función del costo total presenta forma de U, lo cual significa que existe un valor mínimo para la función. La línea de costo total representa la suma de los costos de pedido y los costos de mantenimiento de inventario en el caso de cada monto de pedido.
Método Analítico: Se puede establecer una formula para determinar la CEP de un articulo determinado del inventario. Es posible formular la ecuación del costo total de la empresa. El primer paso para obtener la ecuación del costo total es desarrollar una expresión para la función de costo de pedido y la de costo de mantenimiento de inventario. El costo de pedido puede expresarse como el producto del costo por pedido y el número de pedidos. Como dichos números es igual al uso durante el periodo dividido entre la cantidad de pedido (U)/(C), el costo de pedido puede expresarse de la manera siguiente. Costo de pedido = PxU/Q El costo de mantenimiento de inventario se define como el costo por pedido de mantener una unidad, multiplicando por el inventario promedio de la empresa
(Q/2). Dicho inventario se define como la cantidad de pedido dividida entre 2. El costo de mantenimiento se expresa. Costo de mantenimiento = MxQ/2
A medida en que aumenta a la cantidad de pedidos, Q, el costo de pedido disminuirá en tanto que el costo de mantenimiento de inventario aumenta proporcionalmente.
La ecuación del costo total resulta de combinar las expresiones de costo de pedido y costo de mantenimiento de inventario como sigue. Costo total = (P x U/Q) mas (MxQ/2).
Dado que la CEP se defina como la cantidad en pedido que minimiza la función de costo total, la CEP debe despejarse y se obtiene la siguiente fórmula. CEP = 2PU/M. Punto de reformulación. Una vez que empresa ha calculado su cantidad económica de pedido debe determinar el momento adecuado para formular un pedido. En el modelo CEP se supone que los pedidos son recibidos inmediatamente cuando el nivel del inventario llega a cero. De hecho se requiere de un punto de reformulación de pedidos que se considere el lapso necesario para formular y recibir pedidos.
Suponiendo una vez más una tasa constante de uso de inventario, el punto de reformulación de pedidos puede determinarse mediante la siguiente fórmula. Punto de reformulación = tiempo de anticipo en días x uso diario.
Control de la Producción
Para obtener un control sobre la existencia de inventario debemos tomar en cuenta tres variables que resultan sumamente importantes que son:
1. El nivel de ventas de la empresa. 2. La longitud y la naturaleza teórica de los procesos de producción. 3. La durabilidad en comparación con la caducaron del producto terminado.
El director de producción debe tomar decisiones concernientes a la manera de distribuir la capacidad productiva, de acuerdo a la demanda y la política de inventarios.
Es necesario determinar el número de cada componente (materia prima, Partes compradas, partes fabricadas) que se necesitan para las cantidades de cada producto que se desean fabricar. El numero de unidades de cada componente que debe fabricarse o comprarse debido a existencia disponible no asignada, ordenes pendientes en producción y de compras y un inventario final deseado en este periodo. Todo inventario representa un costo en cualquier empresa por eso los costos son una parte fundamental de controlar y evaluar dentro del proceso de al administración de inventario.
Control de Inventario
Los diversos aspectos de la responsabilidad sobre los inventarios afectan a muchos departamentos y cada uno de éstos ejerce cierto grado de control sobre los productos, a medida que los mismos se mueven a través de los distintos procesos de inventarios. Todos estos controles que abarcan, desde el procedimiento para desarrollar presupuestos y pronósticos de ventas y producción hasta la operación de un sistema de costo pro el departamento de contabilidad para la determinación de costos de los inventarios, constituye el sistema del control interno de los inventarios, las funciones generales son: Planeamiento, compra u obtención, recepción, almacenaje, producción, embarques y contabilidad.
Planeamiento
La base para planear la producción y estimar las necesidades en cuanto a inventarios, la constituye el presupuesto o pronostico de ventas. Este debe ser desarrollado por el departamento de ventas.
Los programas de producción, presupuestos de inventarios y los detalles de la materia prima y mano de obra necesaria, se preparan o se desarrollan con vista al presupuesto de ventas. Aunque dichos planes se basan en estimados, los mismos tendrán alguna variación con los resultados reales, sin embargo ellos facilitan un control global de las actividades de producción, niveles de inventarios y ofrecen una base para medir la efectividad de las operaciones actuales.
Compra u Obtención
En la función de compra u obtención se distinguen normalmente dos responsabilidades separadas: Control de producción, que consiste en determinar los tipos y cantidades de materiales que se quieren. Compras, que consiste en colocar la orden de compra y mantener la vigilancia necesaria sobre la entrega oportuna del material.
Recepción
Debe ser responsable de lo siguiente:
o La aceptación de los materiales recibidos, después que estos hayan sido debidamente contados, inspeccionados en cuanto a su calidad y comparados con una copia aprobada de la orden de compra.
o La prelación de informes de recepción para registrar y notificar la recepción y aceptación.
o La entrega o envío de las partidas recibidas, a los almacenes (depósitos) u otros lugares determinados. Como precaución contra la apropiación indebida de activos.
Almacenaje
Las materias primas disponibles para ser procesadas o armadas (ensambladas), así como los productos terminados, etc., pueden encontrarse bajo la custodia de un departamento de almacenes. La responsabilidad sobre los inventarios en los almacenes incluye lo siguiente:
a. Comprobación de las cantidades que se reciben para determinar que son correcta.
b. Facilitar almacenaje adecuado, como medida de protección contra los elementos y las extracciones no autorizadas.
c. Extracción de materiales contra la presentación de autorizaciones de salida para producción o embarque.
Producción
Los materiales en proceso se encuentran, generalmente bajo control físico, control interno de los inventarios, incluye lo siguiente:
a. La información adecuada sobre el movimiento de la producción y los inventarios.
b. Notificación rápida sobre desperdicios producidos, materiales dañados, etc., de modo que las cantidades y costos correspondientes de los inventarios. Puedan ser debidamente ajustados en los registros.
La información rápida y precisa de parte de la fábrica, constituye una necesidad para el debido funcionamiento del sistema de costo y los procedimientos de control de producción.
Embarques
Todos los embarques, incluyéndose aquellas partidas que no forman parte de los inventarios, deben efectuarse, preferiblemente, a base de órdenes de embarque, debidamente aprobadas y preparadas independientemente.
Contabilidad
Con respecto a los inventarios, es mantener control contable sobre los costos de los inventarios, a medida que los materiales se mueven a través de los procesos de adquisición, producción y venta. Es decir la administración del inventario se refiere a la determinación de la cantidad de inventario que se debería mantener, la fecha en que se deberán colocar las órdenes y la cantidad de unidades que se deberá ordenar cada vez. Los inventarios son esenciales para las ventas, y las ventas son esenciales para las utilidades.
FUENTE: http://www.monografias.com/trabajos15/inventario/inventario.shtml
MODELOS DETERMINISTICOS
Un modelo de Optimización Matemática consiste en una función objetivo y un conjunto de restricciones en la forma de un sistema de ecuaciones o inecuaciones. Los modelos de optimización son usados en casi todas las áreas de toma de decisiones, como en ingeniería de diseño y selección de carteras financieras de inversión .
Los problemas de toma de decisiones se pueden clasificar en dos categorías: modelos de decisión determinísticos y modelos de decisión probabilísticos. En los modelos deterministicos, las buenas decisiones se basan en sus buenos resultados. Se consigue lo deseado de manera "deterministica", es decir, libre de riesgo. Esto depende de la influencia que puedan tener los factores no controlables, en la determinación de los resultados de una decisión y también en la cantidad de información que el tomador de decisión tiene para controlar dichos factores.
Aquellos que manejan y controlan sistemas de hombres y equipos se enfrentan al problema constante de mejorar (por ejemplo, optimizar) el rendimiento del sistema. El problema puede ser reducir el costo de operación y a la vez mantener un nivel aceptable de servicio, utilidades de las operaciones actuales, proporcionar un mayor nivel de servicio sin aumentar los costos, mantener un funcionamiento rentable cumpliendo a la vez con las reglamentaciones gubernamentales establecidas, o "mejorar" un aspecto de la calidad del producto sin reducir la calidad de otros aspectos. Para identificar la mejora del funcionamiento del sistema, se debe construir una representación sintética o modelo del sistema físico, que puede utilizarse para describir el efecto de una variedad de soluciones propuestas.
Un modelo puede considerarse como una entidad que captura la esencia de la realidad sin la presencia de la misma. Una fotografía es un modelo de la realidad ilustrada en la imagen. La presión arterial puede utilizarse como un modelo de la salud de una persona. Una campaña piloto de ventas puede utilizarse como un modelo de la respuesta de las personas a un nuevo producto. Por último, una ecuación matemática puede utilizarse como un modelo de la energía contenida en un determinado material. En cada caso, el modelo captura algún aspecto de la realidad que intenta representar.
Ya que un modelo sólo captura determinados aspectos de la realidad, su uso puede no ser apropiado en una aplicación en particular porque no captura los elementos correctos de la realidad. La temperatura es un modelo de las condiciones climáticas pero puede ser inapropiado si uno está interesado en la presión barométrica. Una foto de una persona es un modelo de la misma pero brinda poca información acerca de sus logros académicos. Una ecuación que predice las ventas anuales de un producto en particular es un modelo de ese producto pero tiene poca utilidad si lo que nos interesa es el costo de producción por unidad. Por lo tanto, la utilidad del modelo depende del aspecto de la realidad que representa.
Un modelo puede ser inadecuado aun cuando intenta capturar los elementos apropiados de la realidad si lo hace de una manera distorsionada o sesgada. Una ecuación que pronostica el volumen mensual de ventas puede ser exactamente lo que el gerente de ventas quiere pero podría generar grandes pérdidas si arroja constantemente cálculos de ventas altos. Un termómetro que lee de más (o de menos) tendría poca utilidad para realizar un diagnóstico médico. En consecuencia, un modelo útil es aquel que captura los elementos adecuados de la realidad con un grado aceptable de precisión.
Un modelo matemático es una ecuación, desigualdad o sistema de ecuaciones o desigualdades, que representa determinados aspectos del sistema físico representado en el modelo. Los modelos de este tipo se utilizan en gran medida en las ciencias físicas, en el campo de la ingeniería, los negocios y la economía.
Un modelo ofrece al analista una herramienta que puede manipular en su análisis del sistema en estudio, sin afectar al sistema en sí. Por ejemplo, supóngase que se ha desarrollado un modelo matemático para predecir las ventas anuales como una función del precio de venta unitario. Si se conoce el costo de producción por unidad, se pueden calcular con facilidad las utilidades anuales totales para cualquier precio de venta. Para determinar el precio de venta que arrojará las utilidades totales máximas, se pueden introducir en el modelo distintos valores para el precio de venta, uno a la vez, determinando las ventas resultantes y calculando las utilidades anuales totales para cada valor de precio de venta examinado. Mediante un proceso de prueba y error, el analista puede determinar el precio de venta que maximizará las utilidades anuales totales.
Lo ideal sería que si el modelo matemático es una representación válida del rendimiento del sistema, mediante la aplicación de las técnicas analíticas adecuadas, la solución obtenida a partir del modelo debería ser también la solución para el problema del sistema. Así, la efectividad de los resultados de la aplicación de cualquier técnica operativa es en gran medida una función del grado en el cual el modelo representa al sistema en estudio.
A fin de definir las condiciones que nos conducirán a la solución del problema del sistema, el analista primero debe identificar un criterio según el cual se podrá medir el sistema. Este criterio a menudo se denomina medida del rendimiento del sistema o medida de efectividad. En aplicaciones empresariales, la medida de efectividad generalmente son los costos o las utilidades, mientras que en aplicaciones gubernamentales esta medida generalmente se define en términos de un índice costo/beneficio.
El modelo matemático que describe el comportamiento de la medida de efectividad se denomina función objetivo. Si la función objetivo es describir el comportamiento de la medida de efectividad, debe capturar la relación entre esa medida y aquellas variables que hacen que dicha medida fluctúe. Las variables del sistema pueden categorizarse en variables de decisión y parámetros. Una variable de decisión es una variable que puede ser directamente controlada por el decisor. También existen algunos parámetros cuyos valores pueden ser inciertos para el decisor. Esto requiere un análisis de sensibilidad después de descubrir la mejor estrategia. En la práctica, resulta casi imposible capturar la relación precisa entre todas las variables del sistema y la medida de efectividad a través de una ecuación matemática. En cambio, el analista de IO/CA debe tratar de identificar aquellas
variables que afectan en mayor grado la medida de efectividad y luego debe intentar definir de manera lógica la relación matemática entre estas variables y la medida de efectividad. Esta relación matemática es la función objetivo que se emplea para evaluar el rendimiento del sistema en estudio.
La formulación de una función objetivo que tenga sentido normalmente es una tarea tediosa y frustrante. Los intentos de desarrollo de una función objetivo pueden terminar en un fracaso. Esto puede darse porque el analista elige el conjunto incorrecto de variables para incluir en el modelo o bien, si el conjunto es el adecuado, porque no identifica correctamente la relación entre estas variables y la medida de efectividad. En un nuevo intento, el analista trata de descubrir las variables adicionales que podrían mejorar su modelo descartando aquellas que parecen tener poca o ninguna relevancia. No obstante, sólo se puede determinar si estos factores realmente mejoran el modelo una vez realizadas la formulación y prueba de nuevos modelos que incluyan las variables adicionales. Todo el proceso de selección y rechazo de variables puede requerir reiteraciones múltiples hasta desarrollar una función objetivo satisfactoria. En cada iteración, el analista espera lograr alguna mejora en el modelo, aunque no siempre se tiene tanta buena suerte. Por lo general, el éxito final es precedido por una serie de fracasos frustrantes y pequeños progresos.
En cada etapa del proceso de desarrollo, el analista debe evaluar la correspondencia o validez del modelo. Normalmente se emplean dos criterios para realizar esta determinación. El primero implica la experimentación del modelo: someter el modelo a una serie de condiciones y registrar los valores asociados de la medida de efectividad dada por el modelo en cada caso. Si la medida de efectividad varía de manera antinatural con una sucesión de condiciones de entrada, es posible que la función objetivo no sea válida. Por ejemplo, supóngase que se desarrolla un modelo destinado a calcular el valor de mercado de viviendas unifamiliares. El modelo debe expresar el valor de mercado en dólares como una función de la superficie cubierta en pies cuadrados, cantidad de dormitorios, cantidad de baños y tamaño del lote. Después de desarrollar el modelo, el analista lo aplica a la tasación de distintas viviendas, con distintos valores para las características mencionadas y descubre que el valor de mercado desciende a medida que aumenta la superficie cubierta expresada en pies cuadrados. Dado que este resultado no concuerda con la realidad, el analista cuestionaría la validez del modelo. Por otro lado, supóngase que el modelo es tal que el valor de las viviendas es una función creciente de cada una de las cuatro características citadas, como generalmente es de esperar. Si bien este resultado es alentador, no necesariamente implica que el modelo es una representación válida de la realidad, dado que la tasa de aumento de cada variable puede ser excesivamente alta o baja. La segunda etapa de la validación del modelo requiere una comparación de los resultados del modelo con los resultados obtenidos en la realidad.
FUENTE: http://www.investigacion-operaciones.com/Modelos_Deterministicos.htm
o
Determinísticos: “Cantidad fija de pedido”, cuando siempre se pide la misma cantidad al proveedor; o de “pedido fijo”, cuando se solicita un nuevo lote cada cierto período de tiempo, denominado período óptimo entre pedidos.
Parten de la hipótesis de que la demanda como tiempo de suministro se conoce con certeza.
o Probabilísticos: Bien la demanda o el tiempo de suministro, o ambos, son aleatorios.
Modelos de cantidad fija de pedido:
a) Modelo básico: Parte de las siguientes hipótesis:
o Se supone que la demanda es cierta, constante y uniforme en el tiempo, de modo que la demanda diaria se calcula como la demanda total partida T.
o El tiempo de suministro se supone conocido, constante e independiente del tamaño del lote o pedido. El proveedor tardará lo mismo en donarnos 1 unidad que 1000 unidades.
o Siempre se solicita una misma cantidad Q* conocida como “lote económico o lote óptimo”, que es aquella cantidad que suministra los costes de almacenamiento ( emisión, ruptura, etc).
o Se pide el lote cuando el nivel de inventario alcanza una cantidad conocida como punto de pedido.
o El pedido se recibe en una sola entrega, justo en el momento en que el inventario se hace cero.
b) Modelo de consumo y reaprovisionamiento simultáneo: La misma hipótesis que antes, excepto una diferencia con el modelo anterior, y es que el pedido Q* no se recibe en una sola entrega, sino a razón de una tasa constante (p) denominada “ tasa de fabricación o entrega”.
Durante el tiempo en que recibimos unidades, la demanda sigue manteniéndose constante (d = D/ T) durante el tiempo de fabricación o entrega.
FUENTE: http://html.rincondelvago.com/direccion-de-la-produccion.html
El Modelo Clásico OEC: Este es el modelo mas simple construido basándose en el principio de que los bienes obtenidos el mismo día que son ordenados sin permitir escasez. Claramente, se debe ordenar nuevamente cuando el inventario alcanza 0, o considerando el tiempo de reemplazo L
La figura siguiente muestra los cambios en los niveles inventarios con respecto al tiempo:
La figura muestra el tiempo en el eje de las x y el nivel de inventario en el eje de las y. Se comienza en el tiempo cero cuando una orden llega. La cantidad de la orden es el tamaño del lote, Q. El lote completo es enviado al mismo momento por lo que el inventario se dispara instantáneamente desde 0 hasta Q. Los materiales son sustraídos del inventario a una tasa de demanda constante, x, medida en unidades por tiempo. Luego que el inventario es mermado, el tiempo para el arribo de otra orden de tamaño Q llega, y el ciclo se repite de nuevo.
El patrón de inventario mostrado en la figura anterior, es obviamente una abstracción de la realidad porque no se espera que un sistema real opere exactamente como mostramos. La abstracción proporciona una estimación del tamaño de lote óptimo, llamado orden económico de cantidad (OEC), y cantidades relacionadas. Consideraremos posiciones alternativas a esta definición mas adelante.
Ordenes Almacenamiento
Costo Total= C1x/Q + C2/(2Q)
La Cantidad Optima de Ordenes = Q* = (2xC1/C2) 1/2, por lo tanto, el Ciclo Optimo de Re-ordenamiento = T* = [2C1/(xC2)]1/2
Ejemplo Numérico 1: Suponga que su oficina utiliza 1200 cajas al año de papel para maquinas de escribir. Usted debe determinar la cantidad que debe ser ordenada, y con que frecuencia se debe hacer. Los datos a considerar son la tasa de demanda x= 1200 cajas al año, el costo de ordenamiento C1 = $5 por orden, costos de manutención o mantenimiento C2 = $1.20 por caja, por año.
La cantidad óptima de ordenamiento es Q* = 100 cajas, esto nos proporciona el número de ordenes = 1200/100 = 12, es decir, 12 ordenes por año, o una vez por mes.
Note que se debe incorporar el tiempo de reemplazo (L), el cual es el intervalo de tiempo que transcurre desde que una orden es hecha hasta que es repuesto.
FUENTE: http://home.ubalt.edu/ntsbarsh/stat-data/Forecasts.htm
UNIDAD 5: LINEAS DE ESPERA.
DEFINICIONES, CARACTERISTICAS Y SUPOSICIONES
En este capítulo se aplica la teoría de colas. Una Cola es una línea de espera y la teoría de colas es una colección de modelos matemáticos que describen sistemas de líneas de espera particulares o de sistemas de colas. Los modelos sirven para encontrar el comportamiento de estasdo estable, como la longitud promedio de la línea y el tiempo de espera promedio para un sistema dado.
El problema es determinar que capacidad o tasa de servicio proporciona el balance correcto. Esto no es sencillo, ya que el cliente no llega a un horario fijo, es decir, no se sabe con exactitud en que momento llegarán los clientes.También el tiempo de servicio no tiene un horario fijo.
La teoría de las colas es el estudio matemático de las colas o líneas de espera. La formación de colas es, por supuesto, un fenómeno común que ocurre siempre que la demanda efectiva de un servicio excede a la oferta efectiva.
Con frecuencia, las empresas deben tomar decisiones respecto al caudal de servicios que debe estar preparada para ofrecer. Sin embargo, muchas veces es imposible predecir con exactitud cuándo llegarán los clientes que demandan el servicio y/o cuanto tiempo será necesario para dar ese servicio; es por eso que esas decisiones implican dilemas que hay que resolver con información escasa. Estar preparados para ofrecer todo servicio que se nos solicite en cualquier momento puede implicar mantener recursos ociosos y costos excesivos. Pero, por otro lado, carecer de la capacidad de servicio suficiente causa colas excesivamente largas en ciertos momentos. Cuando los clientes tienen que esperar en una cola para recibir nuestros servicios, están pagando un coste, en tiempo, más alto del que esperaban. Las líneas de espera largas también son
costosas por tanto para la empresa ya que producen pérdida de prestigio y pérdida de clientes.
La teoría de las colas en si no resuelve directamente el problema, pero contribuye con la información vital que se requiere para tomar las decisiones concernientes prediciendo algunas características sobre la línea de espera: probabilidad de que se formen, el tiempo de espera promedio.
Pero si utilizamos el concepto de "clientes internos" en la organización de la empresa, asociándolo a la teoría de las colas, nos estaremos aproximando al modelo de organización empresarial "just in time" en el que se trata de minimizar el costo asociado a la ociosidad de recursos en la cadena productiva.
FUENTE: http://www.eumed.net/cursecon/dic/oc/colas.htm
Definición.
Una Cola es una línea de espera y la teoría de colas es una colección de modelos matemáticos que describen sistemas de líneas de espera particulares o sistemas de colas. Los modelos sirven para encontrar el comportamiento de estado estable , como la longitud promedio de la línea y el tiempo de espera promedio para un sistema dado. Esta información, junto con los costos pertinentes, se usa, entonces, para determinar la capacidad de servicio apropiada.
Costos de los sistemas de colas.
Un sistema de colas puede dividirse en sus dos componentes de mayor importancia, la cola y la instalación de servicio . Las llegadas son las unidades que entran en el sistema para recibir el servicio. Siempre se unen primero a la cola ; si no hay línea de espera se dice que la cola esta vacía . De la cola, las llegadas van a la instalación de servicio de acuerdo con la disciplina de la cola, es decir, de acuerdo con la regla para decidir cuál de las llegadas se sirve después. El primero en llegar primero en ser servido es una regla común, pero podría servir con prioridades o siguiendo alguna otra regla. Una vez que se completa el servicio, las llegadas se convierten en salidas.
Ambas componentes del sistema tienen costos asociados que deben de considerarse.
Costo de Espera.
Esperar significa desperdicio de algún recurso activo que bien se puede aprovechar en otra cosa y esta dado por :
Costo total de espera = CwL
Donde Cw = costo de espera por hora (en dólares) por llegada por unidad de tiempo y L= longitud promedio de la línea.
Costo de Servicio.
Este en la mayoría se trata de comprar varias instalaciones de servicio , en estos casos solo se ocupan los costos comparativos o diferenciales.
Sistema de costo mínimo.
Aquí hay que tomar en cuenta que para tasas bajas de servicio, se experimenta largas colas y costos de espera muy altos . Conforme aumenta el servicio disminuyen los costos de espera, pero aumenta el costo de servicio y el costo total disminuye , sin embargo , finalmente se llega a un punto de disminución en el rendimiento. Entonces el propósito es encontrar el balance adecuado para que el costo total sea el mínimo.
Estructuras típicas.
Las llegadas pueden ser personas, cartas, carros, incendios, ensambles intermedios en una fabrica, etc. En la siguiente tabla se muestran algunos ejemplos de varios sistemas de colas .
Ejemplos de sistemas de colas
Situación Llegadas Cola Mecanismo de Servicio
Aeropuerto Aviones Aviones en carreteo Pista
Aeropuerto Pasajeros Sala de espera Avión
Depto de bomberos Alarmas de incendio Incendios Depto. De Bomberos.
Compañía telefónica Números marcados Llamadas Conmutador
Lavado de carros Autos Autos sucios Mecanismo de lavado
La corte Casos Casos atrasados Juez
Panadería Clientes Clientes con números Vendedor
Carga de camiones Camiones Camiones en espera Muelle de carga
Oficina de correos Cartas Buzón Empleados por correos
Crucero Autos Autos en línea Crucero
Fábrica Subensamble Inventario en proceso Estación de trabajo.
Cartas de negocios Notas de dictado Cartas para mecanografiar Secretaria
Reproducción Pedidos Trabajos Copiadoras
Hospital Pacientes Personas enfermas Hospital
Permitiendo que varíen el número de colas y el número de servidores, pueden hacerse los diagramas de los cuatro tipos de sistemas de la siguiente figura. Cada línea de espera individual y cada servidor individual se muestra por separado.
El primer sistema que se muestra en la figura, se llama un sistema de un servidor y una cola o puede describir un lavado de carros automático o un muelle de descarga de un solo lugar.
El segundo, una línea con múltiples servidores, es típico de una peluquería o una panadería en donde los clientes toman un número al entrar y se les sirve cuando llega el turno.
El tercer sistema, aquél en que cada servidor tiene una línea de separada, es característico de los bancos y las tiendas de autoservicio.
El cuarto sistema , es una línea con servidores en serie, puede describir una fábrica.
3. Modelo de un servidor y una cola.
Este modelo puede aplicarse a personas esperando en una cola para comprar boletos para el cine, a mecánicos que esperan obtener herramientas de un expendio o a trabajos de computadora que esperan tiempo de procesador.
Llegadas.
Consiste en la entrada al sistema que se supone es aleatoria. No tienen horario, es impredecible en que momento llegarán . El modelo también supone que las llegadas vienen de una población infinita y llegan una a la vez .
Cola.
En este modelo se considera que el tamaño de la cola es infinito. La disciplina de la cola es primero en llegar, primero en ser servido sin prioridades especiales. También se supone que las llegadas no pueden cambiar lugares en la línea (cola) o dejar la cola antes de ser servidas.
Instalación de Servicio.
Se supone que un solo servidor proporciona el servicio que varía aleatoriamente.
Salidas.
No se permite que las unidades que salgan entren inmediatamente al servicio.
Características de operación .
Un servidor y una cola.
Llegada Poisson.
Cola infinita, primero en llegar primero en ser servido.
Tiempos de servicio exponenciales.
Cola :
Longitud promedio de la línea :
Tiempo de espera promedio :
Sistema:
Longitud promedio de la línea :
Tiempo de espera promedio :
Utilización de la instalación :
Probabilidad de que la línea exceda a n :
Donde:
A = tasa promedio de llegada.
S = tasa promedio de servicio.
Ejemplo : (Un supermercado )
Supóngase un supermercado grande con muchas cajas de salida, en donde los clientes llegan para que les marquen su cuenta con una tasa de 90 por hora y que hay 10 cajas en operación. Si hay poco intercambio entre las líneas, puede tratarse este problema como 10 sistemas separados de una sola línea, cada uno con una llegada de 9 clientes por hora. Para una tasa de servicio de 12 por hora :
Dados:
A = 9 clientes por hora
S = 12 clientes por hora
Entonces :
= 2.25 Clientes
= 0.25 horas o 15 minutos.
= 3 clientes.
= 0.33 horas o 20 minutos.
= 0.75 o 75%
0.32
Entonces, para este ejemplo, el cliente promedio espera 15 minutos antes de ser servido. En promedio, hay un poco más de dos clientes en la línea o tres en el sistema. El proceso completo lleva un promedio de 20 minutos. La caja está ocupada el 75 % del tiempo. Y finalmente, el 32 % del tiempo habrá cuatro personas o más en el sistema ( o tres o más esperando en la cola).
4. Evaluación del sistema cuando se conoce el costo de espera.
Los costos de servicio influyen en el método para encontrar el sistema de menor costo. Si el costo de servicio es un función lineal de la tasa de servicio, puede encontrarse una solución general para la tasa óptima.
Para aplicar una solución general, se necesita una tasa de servicio que pueda variar de manera continua.
Cuando los costos de servicio cambian en forma escalonada, se usa la técnica de prueba y error para encontrar el sistema de menor costo. Se calcula el costo total para una tasa de servicio, después para la siguiente y así sucesivamente. Esto continúa hasta que se encuentra un límite inferior o un mínimo tal, que el aumentar o el disminuir las tasas de servicio da costos totales más altos.
Ejemplo:
Se esta estudiando un muelle de carga y descarga de camiones para aprender cómo debe formarse una brigada. El muelle tiene espacio sólo para un camión, así es un sistema de un servidor. Pero el tiempo de carga o descarga puede reducirse aumentando el tamaño de la brigada.
Supóngase que puede aplicarse el modelo de un servidor y una cola (llegadas Poisson, tiempos de servicio exponenciales) y que la tasa promedio de servicio es un camión por hora para un cargador. Los cargadores adicionales aumentan la tasa de servicio proporcionalmente.
Además, supóngase que los camiones llegan con una tasa de dos por hora en promedio y que el costo de espera es de $ 20 por hora por un camión. Si se le paga $ 5 por hora a cada miembro de la brigada, ¿Cuál es el mejor tamaño de esta?
Datos :
A = 2 camiones por hora.
S = 1 camión por persona.
Cw = costo de espera = $20 por hora por camión.
CS = costo de servicio = $ 5 por hora por persona.
Ahora sea k = número de personas en la brigada. Se busca k tal que la suma de los costos de espera y servicio se minimicen :
Costo total = Cw LS + k CS
Las pruebas deben de empezar con tres miembros de la brigada, ya que uno o dos no podrían compensar la tasa de llegadas de dos camiones por hora. Para una brigada de tres, la tasa de servicio es de tres camiones por hora y puede encontrarse Ls con la siguiente ecuación :
De la misma manera, para una brigada de cuatro :
El costo es menor, por tanto se sigue adelante.
Para una brigada de cinco :
Este todavía es menor :
Como este costo es mayor que el de la brigada de cinco, se rebasó el límite inferior de la curva de costo; el tamaño óptimo de la brigada es cinco personas.
5. Evaluación del sistema con costos de espera desconocidos .
En lugar de estimar el costo de espera, el administrador puede especificar un promedio mínimo de tiempo de espera o de longitud de línea . Esto establece un límite superior para Wq , el tiempo de espera en la cola (o para Lq, la longitud de línea en la cola).
Con este límite superior puede encontrarse la tasa de servicio necesaria para cualquiera tasa de llegadas dadas.
Ejemplo :
Considérese un restaurante de comida rápida con un menú limitado. El restaurante se está diseñando para que todos los clientes se unan a una sola línea para ser servidos. Una persona tomará la orden y la servirá. Con sus limitaciones, la tasa de servicio puede aumentarse agregando más personal para preparar la comida y servir las ordenes.
Esto constituye un sistema de un servidor y una cola. Si las llegadas y salidas son aleatorias, puede aplicarse el modelo de una cola. Supóngase que la administración quiere que el cliente promedio no espere más de dos minutos antes de que se tome su orden . Esto se expresa como :
Wq = 2 minutos
Supóngase también que la tasa máxima de llegadas es de 30 órdenes por hora.
ordenando términos,
Como la tasa de servicio debe ser mayor que la tasa de llegadas, puede descartarse la solución negativa. Entonces :
Para este ejemplo, se supuso :
A = 30 ordenes por hora.
Wq = 2 minutos o 0.033 horas
Entonces :
= 15 + 33.5 = 48.5 órdenes por hora.
Para cumplir los requerimientos, se necesita una tasa de casi 50 órdenes por hora. Si, por ejemplo, una brigada de cinco pueden manejar 45 órdenes por hora y una de seis puede procesar 50 por hora, entonces sería necesario tener la brigada de seis.
6. Modelo de un servidor con tiempos de servicio constantes.
Este modelo es igual que el anterior, excepto que se supone que el tiempo de servicio es exactamente el mismo en cada llegada en lugar de ser aleatorio. Todavía se tiene una sola línea, tamaño de la cola infinito, disciplina de la cola como primero en llegar primero en ser servido y llegadas Poisson.
Las aplicaciones típicas de este modelo pueden incluir un autolavado automático, una estación de trabajo en una pequeña fábrica o una estación de diagnóstico de mantenimiento preventivo. En general, el servicio lo proporciona una máquina.
Las características de operación están dadas por 4 :
En donde:
A = tasa promedio de llegadas (llegadas por unidad de tiempo)
S = tasa constante de servicio (llegadas por unidad de tiempo).
Ejemplo:
Supóngase un lavado automático de autos con una línea de remolque, de manera que los autos se mueven a través de la instalación de lavado como en una línea de ensamble.
Una instalación de este tipo tiene dos tiempos de servicio diferentes : el tiempo entre autos y el tiempo para completar un auto. Desde el punto de vista de teoría de colas, el tiempo entre autos establece el tiempo de servicio del sistema. Un auto cada cinco minutos da una tasa de 12 autos por hora. Sin embargo, el tiempo para procesar un auto es el tiempo que se debe esperar para entregar un auto limpio. La teoría de colas no considera este tiempo.
Supóngase que el lavado de autos puede aceptar un auto cada cinco minutos y que la tasa promedio de llegadas es de nueve autos por hora ( con distribución Poisson). Sustituyendo :
7. Modelo con servidores múltiples.
Supóngase que las llegadas son Poisson, los tiempos de servicio son exponenciales, hay una sola línea, varios servidores y una cola infinita que opera con la disciplina de primero en llegar primero en ser servido. Las ecuaciones para las características de operación se vuelven un poco más complicadas.
Sea :
N = número de servidores.
A = tasa promedio de llegadas (llegadas por unidad de tiempo).
S = tasa promedio de servicio por cada servidor (llegadas por unidad de tiempo).
Entonces:
La cantidad P0, es la probabilidad de que no haya llegadas en una unidad de tiempo, lo cual no lo hace más fácil de calcular.
Para dos o tres servidores pueden combinarse y simplificar las dos ecuaciones para obtener, para N = 2
Nótese que para N = 1 este modelo se reduce al modelo de un servidor.
Ejemplo:
|Considérese la biblioteca de una universidad cuyo personal está tratando de decidir cuántas copiadoras debe de instalar para uso de los estudiantes. Se ha escogido un equipo particular que puede hacer hasta 10 copias por minuto.
No se sabe cuál es el costo de espera para un estudiante, pero se piensa que no deben tener que esperar más de dos minutos en promedio. Si el número promedio de copias que se hacen por usuario es cinco, ¿cuántas copiadoras se deben instalar?.
Se usa prueba y error para resolver este tipo de problemas, no se encuentra una solución general como se hizo para el modelo de un servidor. Se tratará primero con dos copiadoras, después con tres, y así hasta que se satisfaga el criterio del tiempo de espera.
¿Cuál es la tasa de servicio? Si el número promedio de copias es cinco y la copiadora puede hacer hasta 10 copias por minuto, entonces pueden servirse en promedio hasta dos estudiantes por minuto. Pero, en esto no se toma en cuenta el tiempo para insertar la moneda, cambiar originales, para que un estudiante desocupe y otro comience a copiar.
Supóngase que se permite un 70 % del tiempo para estas actividades. Entonces la tasa de servicio neta baja a 0.6 estudiantes por minuto. Además se supone que los periodos pico de copiado tienen una tasa de llegada de 60 estudiantes por hora, o 1 por minuto.
Se comenzará con dos copiadoras, ya que una no sería suficiente.
A = 1 por minuto.
S = 0.6 por minuto.
N = 2
Esto excede el criterio del máximo de 2 minutos de espera para el estudiante promedio. Se tratarán tres copiadoras.
FUENTE: http://html.rincondelvago.com/colas.html
Definición. Una Cola es una línea de espera y la teoría de colas es una colección de modelos matemáticos que describen sistemas de líneas de espera particulares o sistemas de colas. Los modelos sirven para encontrar el comportamiento de estado estable , como la longitud promedio de la línea y el tiempo de espera promedio para un sistema dado. Esta información, junto con los costos pertinentes, se usa, entonces, para determinar la capacidad de servicio apropiada.
Costos de los sistemas de colas. Un sistema de colas puede dividirse en sus dos componentes de mayor importancia , la cola y la instalación de servicio . Las llegadas son las unidades que entran en el sistema para recibir el servicio. Siempre se unen primero a la cola ; si no hay línea de espera se dice que la cola esta vacía . De la cola, las llegadas van a la instalación de servicio de acuerdo con la disciplina de la cola, es decir, de acuerdo con la regla para decidir cuál de las llegadas se sirve después. El primero en llegar primero en ser servido es una regla común, pero podría servir con prioridades o siguiendo alguna otra regla. Una vez que se completa el servicio, las llegadas se convierten en salidas. Ambas componentes del sistema tienen costos asociados que deben de considerarse.
Costo de Espera. Esperar significa desperdicio de algún recurso activo que bien se puede aprovechar en otra cosa y esta dado por :
Costo total de espera = CwL Donde Cw = costo de espera por hora (en dólares) por llegada por unidad de tiempo y L= longitud promedio de la línea. Costo de Servicio. Este en la mayoría se trata de comprar varias instalaciones de servicio , en estos casos solo se ocupan los costos comparativos o diferenciales.
Sistema de costo mínimo. Aquí hay que tomar en cuenta que para tasas bajas de servicio, se experimenta largas colas y costos de espera muy altos . Conforme aumenta el servicio disminuyen los costos de espera, pero aumenta el costo de servicio y el costo total disminuye , sin embargo , finalmente se llega a un punto de disminución en el rendimiento. Entonces el propósito es encontrar el balance adecuado para que el costo total sea el mínimo.
Estructuras típicas. Las llegadas pueden ser personas, cartas, carros, incendios, ensambles intermedios en una fabrica, etc. En la siguiente tabla se muestran algunos ejemplos de varios sistemas de colas . Ejemplos de sistemas de colas
Situación Llegadas Cola Mecanismo de Servicio
Aeropuerto Aviones Aviones en carreteo
Pista
Aeropuerto Pasajeros Sala de espera Avión
Depto de bomberos Alarmas de incendio
Incendios Depto. De Bomberos.
Compañía telefónica
Números marcados
Llamadas Conmutador
Lavado de carros Autos Autos sucios Mecanismo de lavado
La corte Casos Casos atrasados Juez
Panadería Clientes Clientes con Vendedor
números
Carga de camiones Camiones Camiones en espera
Muelle de carga
Oficina de correos Cartas Buzón Empleados por correos
Crucero Autos Autos en línea Crucero
Fábrica Subensamble Inventario en proceso
Estación de trabajo.
Cartas de negocios Notas de dictado Cartas para mecanografiar
Secretaria
Reproducción Pedidos Trabajos Copiadoras
Hospital Pacientes Personas enfermas
Hospital
Permitiendo que varíen el número de colas y el número de servidores, pueden hacerse los diagramas de los cuatro tipos de sistemas de la siguiente figura. Cada línea de espera individual y cada servidor individual se muestra por separado. El primer sistema que se muestra en la figura, se llama un sistema de un servidor y una cola o puede describir un lavado de carros automático o un muelle de descarga de un solo lugar. El segundo, una línea con múltiples servidores, es típico de una peluquería o una panadería en donde los clientes toman un número al entrar y se les sirve cuando llega el turno. El tercer sistema, aquél en que cada servidor tiene una línea de separada, es característico de los bancos y las tiendas de autoservicio. El cuarto sistema , es una línea con servidores en serie, puede describir una fábrica.
MODELOS POISSON
Este modelo puede aplicarse a personas esperando en una cola para comprar boletos para el cine, a mecánicos que esperan obtener herramientas de un expendio o a trabajos de computadora que esperan tiempo de procesador. Llegadas.
Consiste en la entrada al sistema que se supone es aleatoria. No tienen horario, es impredicible en que momento llegarán . El modelo también supone que las llegadas vienen de una población infinita y llegan una a la vez . Cola. En este modelo se considera que el tamaño de la cola es infinito. La disciplina de la cola es primero en llegar, primero en ser servido sin prioridades especiales. También se supone que las llegadas no pueden cambiar lugares en la línea (cola) o dejar la cola antes de ser servidas. Instalación de Servicio. Se supone que un solo servidor proporciona el servicio que varía aleatoriamente. Salidas. No se permite que las unidades que salgan entren inmediatamente al servicio. Características de operación .
Un servidor y una cola. Llegada Poisson. Cola infinita, primero en llegar primero en ser servido. Tiempos de servicio exponenciales.
Cola :
Longitud promedio de la línea :
Tiempo de espera promedio : Sistema:
Longitud promedio de la línea :
Tiempo de espera promedio :
Utilización de la instalación :
Probabilidad de que la línea exceda a n : A = tasa promedio de llegada. S = tasa promedio de servicio. Ejemplo : (Un supermercado ) Supóngase un supermercado grande con muchas cajas de salida, en donde los clientes llegan para que les marquen su cuenta con una tasa de 90 por hora y que
hay 10 cajas en operación. Si hay poco intercambio entre las lìneas, puede tratarse este problema como 10 sistemas separados de una sola lìnea, cada uno con una llegada de 9 clientes por hora. Para una tasa de servicio de 12 por hora : Dados A = 9 clientes por hora S = 12 clientes por hora Entonces :
= 2.25 Clientes
= 0.25 horas o 15 minutos.
= 3 clientes.
= 0.33 horas o 20 minutos.
= 0.75 o 75%
0.32 Entonces, para este ejemplo, el cliente promedio espera 15 minutos antes de ser servido. En promedio, hay un poco más de dos clientes en la línea o tres en el sistema. El proceso completo lleva un promedio de 20 minutos. La caja está ocupada el 75 % del tiempo. Y finalmente, el 32 % del tiempo habrá cuatro personas o más en el sistema ( o tres o más esperando en la cola).
Modelo con servidores múltiples.
Supóngase que las llegadas son Poisson, los tiempos de servicio son exponenciales, hay una sola línea, varios servidores y una cola infinita que opera con la disciplina de primero en llegar primero en ser servido. Las ecuaciones para las características de operación se vuelven un poco más complicadas. Sea : N = número de servidores. A = tasa promedio de llegadas (llegadas por unidad de tiempo). S = tasa promedio de servicio por cada servidor (llegadas por unidad de tiempo).
Entonces :
La cantidad P0 es la probabilidad de que no haya llegadas en una unidad de tiempo, lo cual no lo hace más fácil de calcular. Para dos o tres servidores pueden combinarse y simplificar las dos ecuaciones para obtener, para N=2
Nótese que para N = 1 este modelo se reduce al modelo de un servidor. Ejemplo: |Considérese la biblioteca de una universidad cuyo personal está tratando de decidir cuántas copiadoras debe de instalar para uso de los estudiantes. Se ha escogido un equipo particular que puede hacer hasta 10 copias por minuto. No se sabe cuál es el costo de espera para un estudiante, pero se piensa que no deben tener que esperar más de ods minutos en promedio. Si el número promedio de copias que se hacen por ususario es cinco, ¿ cuántas copiadoras se deben instalar ? .
Se usa prueba y error para resolver este tipo de problemas, no se encuentra una solución general como se hizo para el modelo de un servidor. Se tratará primero con dos copiadoras, después con tres, y así hasta que se satisfaga el criterio del tiempo de espera. ¿Cuál es la tasa de servicio? Si el número promedio de copias es cinco y la copiadora puede hacer hasta 10 copias por minuto, entonces pueden servirse en promedio hasta dos estudiantes por minuto. Pero, en esto no se toma en cuenta el tiempo para insertar la moneda, cambiar originales, para que un estudiante desocupe y otro comience a copiar. Supóngase que se permite un 70 % del tiempo para estas actividades. Entonces la tasa de servicio neta baja a 0.6 estudiantes por minuto. Además se supone que los periodos pico de copiado tienen una tasa de llegada de 60 estudiantes por hora, o 1 por minuto. Se comenzará con dos copiadoras, ya que una no sería suficiente. A = 1 por minuto. S = 0.6 por minuto. N = 2
Esto excede el criterio del máximo de 2 minutos de espera para el estudiante promedio. Se tratarán tres copiadoras.
Se necesitan tres copiadoras. La utilización de cada una será :
ANALISIS DE COSTOS
ANÁLISIS ECONÓMICO DE LOS SISTEMAS DE COLAS
En la sección anterior se vio la ventaja de tener más de un servidor, a saber la reducción del tiempo de espera y el número de clientes que esperan para ser atendidos. Claramente, mientras más servidores se tengan, mejor será el servicio a los clientes. Sin embargo, cada servidor implica costos de operación. ¿De que manera evalúa usted este equilibrio entre el nivel de servicio y el costo?
EJEMPLO 1.1: Problema de colas de American Weavers, Inc.
American Weavers, Inc, tiene una fabrica de manufactura en Georgia. La planta tiene un gran numero de maquinas tejedoras que con frecuencia se atascan. Estas maquinas son reparadas basándose en el procedimiento de la primera en entrar, la primera en ser revisada, por uno de los 7 miembros del personal de reparación. Durante varios recorridos, la gerente de producción ha observado que, en promedio, de 10 a 12 maquinas están fuera de operación en cualquier momento debido a que están atascadas. Ella sabe que contratar personal de reparaciones adicional bajaría el número de máquinas sin funcionar, lo cual traería como consecuencia un aumento en la producción, pero no sabe a cuantas personas más debería contratar. Se desea determinar dicho número.
MODELO Y ANALISIS DEL SISTEMA DE COLA ACTUAL.
El primer paso que se debe dar consiste en analizar las condiciones de operación actuales. Se debe reconocer que las maquinas tejedoras conforman un modelo de colas. Los clientes están constituidos por las maquinas que se atascan de vez en cuando. Existe un gran numero de tales maquinas, de modo que se podría suponer razonablemente, que la población de clientes es infinita. Se tienen 7 servidores independientes e idénticos que reparan las maquinas basándose en una estrategia de primera en entrar, primera en darle servicio. Se puede pensar en estas maquinas formando una sola fila en espera de pasar con el siguiente servidor que este disponible.
Para modelar esta operación, el siguiente paso consiste en reunir y analizar los datos correspondientes a los procesos de llegada y de servicio. Se supone lo siguiente:
1. La aparición de maquinas atascadas puede ser aproximada por un proceso de llegada de Poisson con una tasa promedio de 25 por hora.
2. Cada máquina atascada requiere una cantidad aleatoria de tiempo para su reparación, que puede ser aproximada por una distribución exponencial con un tiempo promedio de servicio de 15 minutos, lo cual, para cada servidor, significa una tasa promedio de cuatro maquinas por hora.
Con estas observaciones, el sistema actual puede modelarse como un sistema de colas M / M / 7, con = 25 maquinas por hora, = 4 maquinas por hora y una población y un área de espera infinita.
TABLA 1:Medidas de rendimiento obtenidas con ‘ Queuing Analysis ‘ en el WinQSB .
02-08-2000
Performance Measure Result
23:12:22
1 System: M/M/7 From Formula
2 Customer arrival rate (lambda) per hour = 25.0000
3 Service rate per server (mu) per hour = 4.0000
4 Overall system effective arrival rate per hour = 25.0000
5 Overall system effective service rate per hour = 25.0000
6 Overall system utilization = 89.2857 %
7 Average number of customers in the system (L) = 12.0973
8 Average number of customers in the queue (Lq) = 5.8473
9 Average number of customers in the queue for a busy system (Lb) =
8.3333
10 Average time customer spends in the system (W) = 0.4839 hours
11 Average time customer spends in the queue (Wq) = 0.2339 hours
12 Average time customer spends in the queue for a busy system (Wb) =
0.3333 hours
13 The probability that all servers are idle (Po) = 0.1017 %
14 The probability an arriving customer waits (Pw or Pb) = 70.1674 %
15 Average number of customers being balked per hour = 0
Como se puede ver, el gerente de producción había estimado con bastante precisión el hecho de que entre 10 y 12 maquinas están atascadas, en promedio; en cualquier momento. De hecho, ese numero en el informe es de 12.09. La línea 10 del reporte indica que las maquinas atascadas están fuera de operación durante un tiempo promedio de 0.4839 horas, aproximadamente 29 minutos.
Es necesario determinar el numero de reparadores adicionales que se necesitarían contratar. Se conocen las medidas de rendimiento de un total de 7 trabajadores.
¿ De que manera cambian las medidas de rendimiento si se aumenta el personal de reparación Las medidas de rendimiento asociadas para un numero entre 7 y 11 reparadores se muestran en la TABLA 2
A medida que aumenta el tamaño del personal de 7 a 11, el numero promedio de maquinas fuera de operación disminuye de aproximadamente 12 a 6.333. Similarmente , la cantidad promedio de tiempo que una maquina esta fuera de operación disminuye de 0.4839 horas ( aproximadamente 29 minutos ) a 0.2533 horas ( aproximadamente 15 minutos ).
Ahora se necesita información sobre los costos para determinar cuantos reparadores adicionales, si se requieren, deben contratarse.
TABLA 2: Medidas de rendimiento con diferentes tamaños de personal de reparación.
Numero de reparadores
7 8 9 10 11
Utilización (%) 89.2857 78.1250 69.4444 62.5000 56.8182
Numero esperado en la cola 5.8473 1.4936 0.5363 0.2094 0.0830
Numero esperado en el sistema 12.0973 7.7436 6.7863 6.4594 6.3330
Probabilidad de que un cliente tenga que esperar
0.7017 0.4182 0.2360 0.1257 0.0630
Tiempo esperado en cola 0.2339 0.0597 0.0215 0.0084 0.0033
Tiempo esperado en el sistema 0.4839 0.3097 0.2715 0.2584 0.2533
ANALISIS DE COSTOS DEL SISTEMA DE COLAS.
Al analizar los méritos de contratar personal de reparación adicional en American Weavers, Inc., se deben identificar dos componentes importantes:
1. Un costo por hora basado en el tamaño del personal. 2. Costo total de = Costo por hora para * Numero de personal por hora cada
reparador reparadores 3. Un costo por hora basado en el numero de maquinas fuera de operación.
Costo total por = Costo por hora para cada * Numero promedio la espera maquina fuera de operación máquina fuera de operación
Para seguir adelante, se necesita ahora conocer el costo por hora de cada miembro del personal de reparación ( denotado con Cs ) y el costo por hora de una maquina fuera de operación ( denotado Ce ), que es el costo de una hora de producción perdida. Suponga que el departamento de contabilidad le informa que cada reparador le cuesta a la compañía $ 50 por hora, incluyendo impuestos, prestaciones, etc. El costo de una hora de producción perdida deberá incluir costos explícitos, como la cantidad de ganancias no obtenidas, y costos implícitos, como la perdida de voluntad del cliente no se cumple con la fecha limite de entrega.
Sin embargo, suponga que el departamento de contabilidad estima que la compañía pierde $ 100 por cada hora que una maquina este fuera de operación.
Ahora se puede calcular un costo total para cada uno de los tamaños de personal. Para un personal de 7 reparadores, el numero esperado de maquinas en el sistema es 12. 0973.
Costo total = Costo del personal + Costo de la espera
Costo por hora por * Numero de + Costo por hora por * Número persona reparadores cada maquina fuera esperado de de operación máquinas fuera de operación = ( 50 * 7 ) + ( 100 * 12.0973 ) = $ 1559.73 por hora.
Realizando cálculos parecidos para cada uno de los tamaños de personal restantes se tiene como resultado los costos por hora de cada alternativa presentada en la TABLA 3.
De los resultados, se puede ver que la alternativa que tiene el menor costo por hora, $ 1128.63, es tener un total de 9 reparadores. En consecuencia, la recomendación a la gerencia de producción, es contratar a dos reparadores adicionales. Estos dos nuevos empleados tendrán un costo de $ 100 por hora, pero este costo adicional esta mas que justificado por los ahorros que se tendrán con menos maquinas fuera de operación. La recomendación reducirá el costo por hora de $1559.73 a $ 1128.63, un ahorro de aproximadamente $ 430 por hora, mayor que la cantidad que cubre sus honorarios.
TABLA 3: Costo por hora para diferentes tamaños de personal de reparación.
Tamaño de personal
Numero esperado en el sistema
Costo por hora ($)
7 12.0973 ( 50 * 7 ) + ( 100 * 12.0973 ) = 1559.73
8 7.7436 ( 50 * 8 ) + ( 100 * 7.7436 ) = 1174.36
9 6.7863 ( 50 * 9 ) + ( 100 * 6.7863 ) = 1128.63
10 6.4594 ( 50 * 10 ) + ( 100 * 6.4594 ) = 1145.94
11 6.3330 ( 50 * 11 ) + ( 100 * 6.3330 ) = 1183.30
Características claves
En resumen, para evaluar un sistema de colas en el que usted controla el número servidores o su tasa de servicio, se necesitan las siguientes estimaciones de costos y medidas de rendimiento:
El costo por servidor por unidad de tiempo (Cs) El costo por unidad de tiempo por cliente esperando en el sistema (Ce) El número promedio de clientes en el sistema (L)
Modelos que caracterizan los diferentes procesos de servicio.
A continuación se analizarán los diferentes modelos que caracterizan los procesos de servicio.
Líneas de espera con salidas y llegadas combinadas.
Se estudiarán a continuación modelos para líneas de espera que combinan procesos de llegadas y salidas. Solo analizaremos líneas de espera donde los clientes son atendidos por c servidores que ofrecen servicios iguales desde el punto de vista del tiempo que requieren para prestar el mismo.
El objetivo final de analizar situaciones de espera consiste en generar medidas de desempeño para evaluar sistemas reales. Se hace necesario para analizar los sistemas de espera decidir con anterioridad si nos interesa analizar el sistema en condiciones transitorias o de estado estable. Las líneas de espera que combinan salidas y llegadas se inician en condiciones transitorias y llegan gradualmente al estado estable después de haber transcurrido un tiempo lo suficientemente grande, siempre que los parámetros permitan se alcance el estado estable.
Utilizando el modelo general de Poisson, obtenemos la ecuación general de equilibrio:
n-1pn-1 + n + 1pn+1 = ( n+ n)pn , n =1,2,...
Las ecuaciones de equilibrio se resuelven en forma recursiva comenzando con p, y procediendo por inducción para determinar pn. En general, podemos demostrar por inducción que la probabilidad de que el sistema alcance el estado estable es:
pn = n-1 n-2 0 n n-1 1 p0 , n = 1,2
donde el valor de p0 se determina con la siguiente ecuación:
pn = 1
Las medidas de desempeño del estado estable se pueden usar para analizar la operación de las líneas de espera con el fin de hacer recomendaciones sobre el diseño del sistema. Se puede decir que existe una íntima relación entre Ls y Ws de manera que cualquier medida
Se determina automáticamente a partir de la otra. Siendo e, f la tasa promedio efectiva de llegadas, entonces:
Ls = e, f * Ws Y Lq = e, f Wq
También existe una relación directa entre Ws y Wq pues por definición:
Ws = Wq + 1/
siendo la tasa de servicio por servidor activo, mientras que el tiempo estimado de servicio es 1/ ..
- Modelos para líneas de espera especializadas de Poisson.
Cada modelo de los que a continuación se analizaran se describe en términos de la notación extendida por Kendall, como la deducción de pn es completamente independiente de la disciplina de la línea de espera, es apropiado usar el símbolo DG (disciplina general) en la notación de Kendall.
Modelo (M/M/1) : (DG/
Este es un modelo de servidor único sin límites en la capacidad del sistema o de la fuente de llamadas, con llegadas y salidas de Poisson con tasa medias y ..
Definiendo = obtenemos la siguiente fórmula general para este modelo:
Pn = (1- n , n = 0,1,2,
que es una distribución geométrica, donde además p0 = 1- .
El requisito matemático de que 1 necesario para garantizar la convergencia de la serie geométrica (1 + + 2 + , conduce a un elemento intuitivo. O sea 1 significa que lo que establece que la tasa de llegadas debe ser estrictamente menor que la tasa de servicio en la instalación, para que el sistema alcance estabilidad.
Para este modelo las medidas de básicas de desempeño se calculan de la siguiente forma :
Ls = E n = ( ) / (1- ) Ws = Ls / = 1 / 1-
Lq = Ls - = 2 /(1- Wq = Lq / = / 1-
Modelo (M/M/1) : (DG/N/
La diferencia de este modelo y el anterior radica en que el número máximo de clientes (para este modelo) permitidos en el sistema es N (longitud máxima de la línea de espera es = N-1). Esto significa cuando haya N clientes en el sistema, se impiden todas las nuevas llegadas o no se les permite unirse a la línea de espera.
En este modelo, haciendo = obtenemos que:
(1- 1- N+1 ; 1
Po = 1 / N+1 ; = 1
entonces las formulas para pn pueden resumirse como:
(1- 1- N+1 n ; 1
pn = n = 0,1,2, ...
1 / (N+1) ; 1
Para este modelo no se hace necesario que 1 pues el número de unidades en el sistema esta controlado por la longitud de la línea de espera (= N-1).
Usando el valor anterior de pn, encontramos que el número esperado de unidades en el sistema se calcula como sigue:
1- N+1) N + N N+1 1- 1- N+1 ; 1
Ls = N / 2 ; 1
Las medidas Lq, Ws y Wq se pueden calcular a partir de Ls, una vez que se determina la tasa efectiva de llegadas ef de la forma siguiente:
e, f = 1-pn
usando Ls y ef obtenemos las formulas para calcular, Lq, Wq y Ws:
Lq = Ls- e, f Ls - 1-pN ) pN = Probabilidad de que una unidad no sea
capaz de unirse al sistema.
Wq = Lq / e, f = Ls / 1-pN
Ws = Wq +1/ = Ls / 1-pN
Modelo (M/M/c) : (DG/ .
En este modelo los clientes llegan con una tasa constante y un máximo de c unidades puede ser atendidos simultáneamente. La tasa de servicio por servidor activo es también constante e igual a y e, f = ..
El efecto último de usar c servidores paralelos es acelerar la tasa de servicio al permitir servicios simultáneos. Si el numero de clientes en el sistema, n, es igual o excede a c, la tasa combinadas de salidas de la instalación es c .. Por otra parte, si n es menor que c, la tasa de servicio es igual a n . Así, en terminos del modelo generalizado, tenemos:
n = n 0
n , n c
n = c , n c
Si hacemos = ; el valor de pn y p0 se calcula de la siguiente forma:
n n! p0 0 n c
Pn = n cn-cc! p0 n c
p0 = n n! + c c! 1- c -1
Los valores de las medidas de desempeño se obtienen como sigue :
Lq = c+1/ (c-1)(c- p0 = c c- 2 pc
Ls = Lq +
Wq = Lq/?
Ws = Wq + 1/
Las operaciones asociadas con este modelo pueden ser tediosas. Morse (1958) da dos aproximaciones útiles para po y Lq. Para mucho menor que 1,
P0 1- y Lq c+1 c2
Y para c muy próxima a 1,
P0 (c- )(c-1) cc y Lq c-
- Modelo (M/M/c) : (DG/N/ , c N.
Esta situación de espera difiere de la anterior pues se impone un límite N sobre la capacidad del sistema (es decir, tamaño máximo de la línea de espera = N-c). En términos del modelo generalizado, n y n para el modelo actual están dadas por :
, 0 n N
n = 0, n N
n , 0 n c
n = c , c n N
Sustituyendo por n y n en la expresión general de pn y observando que = ; se obtiene :
n n! p0, 0 n c
Pn = n c! cn-c p0, c n N
donde :
n n! + c 1- c N-c+1 c!(1- c -1, c 1
p0 =
n n!) + c c! N-c+1) -1 , c 1
La única diferencia entre pn en este modelo y el anterior ocurre en la expresión de p0 y el factor de uso c no necesita ser menor que 1. Las medidas de desempeño se calculan de la siguiente forma :
p0 c+1 c-1)!(c- )2 1- c N c - N-c)( c N-c 1- c , c 1
Lq = P0 c N-c)(N-c+1) 2c! , c = 1
Ls = Lq + (c+ ) = Lq + e,f
donde :
= número estimado de servidores inactivos = (c-n)pn
e, f = 1-pn c- )
e, f = La tasa efectiva de llegada.
Modelo de autoservicio (M/M/ DG/ .
En este modelo el numero de servidores es ilimitado porque el cliente mismo es también el servidor. Este es normalmente el caso en los establecimientos de autoservicio. Una vez más en términos del modelo generalizado se tiene :
n = , para toda n 0
n = n , para toda n 0
La sustitución directa en la expresión de pn produce que :
Pn = n n! n p0 ( n n!)p0
ya que pn = 1 se deduce que :
P0 = 1 / 1+ 2 1 e = e-
Como resultado se obtiene que :
Pn e- n n! , n = 0,1,2, , además pn sigue una distribución de Poisson con media
E n = .
Las medidas de desempeño se pueden obtener mediante la siguientes expresiones :
Ls = E n = .
Ws =1/ .
Lq = Wq = 0.
Nótese que Wq = 0 porque cada cliente se atiende a si mismo. Esta es la razón por la que Ws es igual al tiempo de servicio medio 1/ .
A modo de obtener una conclusión parcial de lo analizado hasta aquí, se puede decir que los resultados del modelo (M/M/ ) : (DG/ se pueden utilizar para determinar aproximadamente los del (M c DG/ esto cuando c crece "lo suficiente". La ventaja que esto ofrece es que las operaciones son mucho más sencillas en el modelo (M/M/ ) : (DG/ . También vale la pena destacar que los cálculos demuestran que cuando se hace chica (es decir), es mucho mayor que , el modelo (M/M/ ) es una aproximación bastante exacta del modelo (M/M/c) aun para c tan chica como 10.
- Modelo de servicio de máquinas (M/M/R) : (DG/K/K), R > k.
En este modelo se supone que se dispone de R técnicos en reparaciones para dar servicio a k máquinas. Como una maquina descompuesta no puede generar nuevas llamadas mientras esta en servicio, el modelo es ejemplo de una fuente de llamadas finita.
Si se define como la tasa de descompostura por máquina, se tiene :
(k-n) , 0 n k
n = 0, n k
n , 0 n R
n = R , R n k
0, n k
Sustituyendo por n y n en la expresión de pn se obtiene :
k np0 , 0 n R n
Pn =k (n! n / R!Rn-R ) p0, R n k n
p0 = k n + k (n! n / R!Rn-R ) n n
las otras medidas de desempeño están dadas por :
Lq = (n-R)pn
Ls = Lq + (R- ) = Lq + ef /
Donde :
= número esperado de técnico s =
ef = (R- ) = (k-Ls)
La segunda expresión de ef se obtiene como sigue. Como la tasa de llegadas dadas n máquinas en el sistema es k-n)(donde es la tasa de descompostura por máquina), en condiciones de estado estable :
ef = E k-n = k-Ls)
Los resultados se aplican al caso de un solo técnico haciendo sencillamente R = 1. En este caso se puede probar que :
Lq = k - 1+ 1 p0
Ls = k - p0
Modelos en líneas de espera que no obedecen la distribución de Poisson.
Los modelos de líneas de espera donde los procesos de llegada y/o salida no siguen las hipótesis de Poisson, conducen a resultados complejos y tal vez poco manejables. En estos modelos el tiempo de servicio se describe por medio de una distribución general de probabilidades con media E t y varianza var t . El análisis de esta situación no proporciona una expresión analítica manejable para las probabilidades pn. En vez de esto, los resultados del modelo sólo proporcionan las medidas básicas de desempeño, Ls, Lq, Ws, y Wq.
Para igual a la tasa de llegadas a una instalación con un solo servidor y dadas E t y var t como la media y la varianza de la distribución del tiempo de servicio, se puede demostrar usando el análisis de cadena de Markov que :
Ls = E t + 2 E2 t +var t 2 (1- E t , (M/G/1) : DG/
donde E t 1 , de esta fórmula se obtienen :
Ws = Ls /
Lq = Ls- E t
Wq = Lq /
Aquí la tasa de servicio está dada por = 1/ E t y e, f = para este modelo. Para el caso cuando el tiempo de servicio es aproximadamente constante, var t = 0 la fórmula de Ls anterior se reduce a :
Ls = + 2 2 (1 , (M/D/1) : (DG/
donde y es la tasa constante de servicio.
Las otras medidas de desempeño permanecen iguales.
Si el tiempo de servicio es tipo Erlang con parámetros m y , con E t = 1 y var t =1/(m 2 , la fórmula de Ls sería :
Ls = + 1+m) / (2m) 1- , (M/Em/1) : (DG/
Modelos de líneas de espera con prioridades en el servicio.
En los modelos de espera con prioridad, se suponen que se forman varias líneas de espera en paralelo, incluyendo los clientes que pertenezcan a cierto orden de prioridad. Si la instalación tiene m, líneas de espera, suponiendo que la línea de espera 1 tiene más alta prioridad de servicio y la línea de espera m incluye a clientes con más baja prioridad. Las tasas de llegadas y servicio pueden variar para las diferentes filas de prioridad.
El servicio de prioridad puede seguir una de estas dos reglas:
1. Regla de prioridad, donde el servicio de un cliente de más baja prioridad puede ser interrumpido para favorecer a un cliente que llegue con más alta prioridad.
2. Regla de no prioridad, donde un cliente, una vez que esta siendo atendido, saldrá del establecimiento sólo después de que acabe ser atendido e independientemente de la prioridad del cliente que llegue.
A continuación se analizaran dos modelos que se rigen por la regla de no prioridad, que se aplican a servidores únicos y múltiples. En el caso de servidor único supone llegadas de Poisson y distribuciones de servicio arbitrarias. En el caso de servidores múltiples, las llegadas y salidas siguen la distribución de Poisson. El símbolo NPRP se utiliza con la notación de Kendall para representar la disciplina de no prioridad, Mi y Gj representan distribuciones de Poisson y arbitraria.
Modelo de no prioridad con un servidor (M/G/1) : (NPRP/ .
Sea Fi (t) la FDA de la distribución de tiempo de servicio arbitraria para la i-ésima línea de espera (i = 1,2, … m) y sea E t y var t la media y la varianza ,además sea i la tasa de llegada en la i-ésima fila por el tiempo unitario. Los valores de las medidas de desempeño se obtendrán de las siguientes expresiones :
Wq(k) = i (E2 t +var t ) 2 1-Sk-1 1-Sk
Lq(k) = kWq(k)
Ws(k) = Wq(k) + Ek t
Ls(k) = Lq(k) + k
donde :
k = kE t
Sk = i , k = 1,2,3 …, m
S0 = 0
y aquí se definen Lq(k), Wq(k), Ls(k) y Ws(k) como las medidas de desempeño para la k-ésima línea de espera. Además el tiempo de espera estimado en la línea de espera para cualquier cliente sin importar su prioridad está dado por :
Wq = k Wq(k)
donde :
= i y k es el peso relativo de Wq(k). Un resultado similar se aplica a Ws.
- Modelo de no prioridad con varios servidores (M/M/c) : (NPRP/ .
Este modelo supone que todos los clientes tienen la misma distribución del tiempo de servicio, los c canales tienen una distribución de servicio exponencial idéntica con tasa de servicio . Las llegadas de K-ésima línea de espera con prioridad ocurren según una distribución de Poisson con una tasa de llegada K, k = 1,2, …,m. Se puede demostrar para la k-ésima línea de espera que:
Wq(k) = E 0 1-Sk-1 1-Sk , k = 1,2, …,m
donde :
S0 = 0
Sk = i c
E 0 = 1/ c -c c- c-1 ! n n! ,
y la espera numérica estimada en la línea de espera para todo el sistema viene dada por :
Lq = Wq.
Líneas de espera sucesivas o en serie. Modelo en serie de dos estaciones con capacidad de líneas de espera cero.
A continuación se analizaran líneas de espera de Poisson con estaciones de servicio dispuestas en serie, de manera que todo cliente debe pasar por las dos estaciones antes de completar el servicio.
Para este modelo que describe esta situación los tiempos de servicio en cada estación están exponencialmente distribuidos con la misma tasa de servicio . Las llegadas ocurren según una distribución de Poisson con tasa y no se permiten colas en ninguna de las dos estaciones.
Para plantear este modelo se requiere de identificar primeramente los estados del sistema. Los símbolos 0, 1, b, representan los estados libres, ocupado y bloqueado respectivamente. Sean i y j los estados en la estación 1 y 2. Entonces los estados del sistema se pueden representar :
i, j = 0, 0 ; 1, 0 ; 0, 1 ; 1, 1 ; b, 1
Definiendo pij(t) como la probabilidad de que el sistema se halle en el estado (i, j) en el tiempo t. Las probabilidades de transición entre los tiempos t y t+h se resumen en la siguiente tabla:
Estados t (0, 0) (0, 1) (1, 0) (1, 1) (b, ¡)
(0, 0) 1- h - h
(0, 1) h 1- h 1- h- h h 1- h
(1, 0) h 1- h 1 - h
(1, 1) h 1- h h 1- h 1- h
h
(b, 1) h 1- h - h
Nota : Los cuadros vacíos indican que las transiciones entre los estados indicados t y t+h son imposibles (=0).
Por esto se pueden plantear las siguientes ecuaciones:
p0, 0(t+h) = p0, 0(t)(1- h + p0, 1(t)( h
p0, 1(t+h) = p0, 1(t) 1- h- h + p1, 0(t)( h) + p b, 1 t h
p1, 0(t+h) = p0, 0(t)( h) + p1, 0(t) 1- h p1, 1(t) h
p1, 1(t+h) = p0, 1(t) h + p1, 1(t) 1-2 h
pb, 1(t+h) = p1, 1(t) h + p b, 1(t) 1- h
Recordando los términos y tomando los límites apropiados, las ecuaciones de estado estable son :
p0, 1 - p0, 0 = 0
p1, 0 + p b, 1- p1,0 = 0
p0, 0 + p1, 1 – p1, 0 = 0
p0, 0 + 2p1, 1 = 0
p1, 1 – p b, 1 = 0
Analizando estas ecuaciones y agregando la siguiente condición :
p0, 0 + p0, 1 + p1, 1 + p b, 1 = 1
se llega a la conclusión de que la solución para pi, j es :
p0, 0 = 2/A
p0, 1 = 2
p1, 0 = 2 + 2
p1, 1 = p b, 1 = 2
donde A = 3 2 + 4 + 2. El número esperado en el sistema puede obtenerse como:
Ls = 0 p0, 0 + 1(p0, 1 + p1, 0) + 2 p1, 1 + p b, 1 = 5 2 + 4 .
- Modelo en serie de K estaciones con capacidad de líneas de espera infinita.
Considere un sistema con k estaciones en serie, supóngase que las llegadas a la estación, provienen de una población infinita de acuerdo a una distribución de Poisson con tasa media de llegadas . Las unidades atendidas pasaran sucesivamente de una estación a la siguiente hasta que salgan por la estación k. La distribución del tiempo de servicio en cada estación i es exponencial con tasa media i para i = 1,2, ... , k.
En estas condiciones, puede probarse que para i, la salida de la estación i sigue una distribución de Poisson con tasa media y que cada estación puede tratarse de forma independiente como un modelo (M/M/1) : (DG/ . Esto significa que para la i-ésima estación las probabilidades de estado estable pn, i están dadas por :
pn, i = (1- i) ini ni = 0, 1, 2 ... para i = 1, 2, 3, ... ,k
donde ni es el número en el sistema que solo consta de la estación i. Los resultados del estado estable solo existirán si :
i = i .
El mismo resultado puede extenderse al caso donde la estación i incluye ci servidores en paralelo, cada uno con la misma tasa de servicio exponencial i por unidad de tiempo. En este caso cada estación puede ser tratada como un modelo (M/M/c) : (DG/ con tasa media de llegadas . De nuevo, los resultados de estado estable prevalecerán únicamente si = ci i para i = 1, 2, ... , k.
FUENTE: http://fmarrerodelgado.galeon.com/colas.html
