martes, 17 de octubre de 2017

3.1 Consideraciones generales de los conceptos básicos de problemas de programación no lineal

Programación no lineal (PNL) es el proceso de resolución de un sistema de igualdades y desigualdades sujetas a un conjunto de restricciones sobre un conjunto de variables reales desconocidas, con una función objetivo a maximizar, cuando alguna de las restricciones o la función objetivo no son lineales.

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, con frecuencia no es 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, lo cual vamos a analizar enseguida.

De la manera general el problema de programación no lineal consiste en encontrar:

X=(X₁, X₂, X₃, X₄, X_N) para

Maximizar f(X), sujeta a

G_i(X)<= b_ipara i=1,2…..m,

Y X=>0,

Donde f(X) y g_i(x) son funciones dadas de n variables de decisión.

3.2 Ilustración gráfica de problemas de programación no lineal

Cuando un problema de programación no lineal tiene sólo una o dos variables, se puede representar gráficamente de forma muy parecida a los ejercicios de programación lineal.

Una representación gráfica de este tipo proporciona una visión global de las propiedades de las soluciones óptimas de programación lineal y no lineal.

Para graficar este tipo de problemas haremos uso de el software informático GeoGebra.

Ejemplo 1.

Procedimiento.

1.- Ingresar función objetivo y sus restricciones.

2.- Obtener región factible.

3.- Crear un deslizador.

4.- Igualar función objetivo al deslizador.

5.- Igualar todas las restricciones.

6.- Intersectar la función objetivo con la función.

7.- Mover el deslizador hasta encontrar la intersección.

A continuación se presenta un video de como resolver este tipo de problemas de programación no lineal, en la aplicación GeoGebra.

3.3 Tipos de problemas de programación no lineal

Los problemas de programación no lineal se presentan de muchas formas distintas. Al contrario del método símplex para programación lineal, no se dispone de un algoritmo que resuelva todos estos tipos especiales de problemas. En su lugar, se han desarrollado algoritmos para algunas clases (tipos especiales) de problemas de programación no lineal. Se introducirán las clases más importantes y después se describirá cómo se pueden resolver algunos de estos problemas.

Si la función objetivo f es lineal y el espacio restringido es un politopo, el problema es de Programación lineal y puede resolverse utilizando alguno de los bien conocidos algoritmos de programación lineal.

Si la función objetivo es cóncava (problema de maximización), o convexa (problema de minimización) y el conjunto de restricciones es convexo, entonces se puede utilizar el método general de Optimización convexa

Existe una variedad de métodos para resolver problemas no convexos. Uno de ellos consiste en utilizar formulaciones especiales de problemas de programación lineal. Otro método implica el uso de técnicas de Ramificación y poda, cuando el problema se divide en subdivisiones a resolver mediante aproximaciones que forman un límite inferior del coste total en cada subdivisión. Mediante subdivisiones sucesivas, se obtendrá una solución cuyo coste es igual o inferior que el mejor límite inferior obtenido por alguna de las soluciones aproximadas. Esta solución es óptima, aunque posiblemente no sea única. El algoritmo puede ser parado antes, con la garantía de que la mejor solución será mejor que la solución encontrada en un porcentaje acotado. Ello se utiliza en concreto en problemas importantes y especialmente difíciles y cuando el problema cuenta con costes inciertos o valores donde la incertidumbre puede ser estimada en un grado de fiabilidad apropiado.

Las condiciones de Karush-Kuhn-Tucker proporcionan las condiciones necesarias para que una solución sea óptima.

Los tipos de problemas de programación no lineal son:

Optimización no restringida.
Optimización linealmente restringida.
Programación cuadrática
Programación convexa.
Programación separable.
Programación no convexa.
Programación geométrica.
Programación fraccional.
Problema de complementariedad.

ALGORITMOS SIN RESTRICCIÓN

En esta sección se presentarán dos algoritmos para el problema no restringido: el algoritmo de búsqueda directa y el algoritmo degradiente.

Método de búsqueda directa

Los métodos de búsqueda directa se aplican principalmente a funciones estrictamente unimo- dales de una variable. Aunque puede parecer trivial el caso, la sección 21.1.2 muestra que la optimización de funciones de una variable juega un papel clave en el desarrollo de los algoritmos de varias variables, más generales.

La idea de los métodos de búsqueda directa es identificar el intervalo de incertidum- bre que comprenda al punto de solución óptima. El procedimiento localiza el óptimo estrechando en forma progresiva el intervalo de incertidumbre hasta cualquier grado de exactitud que se desee.

En esta sección se presentan dos algoritmos estrechamente relacionados: los métodos de búsqueda dicótomo y de sección dorada (o áurea). Ambos buscan la maximización de una función unimodal/(x) en el intervalo a ^ x < b, que se sabe que incluye el punto óptimo x*.Los dos métodos comienzan con /₀ = (a, b) que representa el intervalo inicial de incertidumbre.

Paso general i. Sea /, _ , = (x_D x_R) el intervalo actual de incertidumbre (en la iteración 0, x_L = a y x_R = b). A continuación se definen x_x y x₂tales que

xj^ ^ ^ x₂ ^ x_r

El siguiente intervalo de incertidumbre, /_z, se define como sigue:

Si f(x_x) > /(x₂), entonces x_L < x* < x₂. Se definen x_R = x₂ e /, = (x_L, x₂) (véase la figura 21.2[a]).
Si f(x_x) < f(x₂\ entonces x_x < x* < x_R. Se definen x_L = x_x e I¡ = (x_h x_R) (véase la figura 21.1 [b]). .
Si f{x\) = /(jc₂), entonces x_x < x* < x₂. Se definen x_L = x₂ e /, = (x_b x₂).

La manera en que se determinan x_x y x₂ garantiza que /, < /,_ _p como se demostrará en breve. El algoritmo termina en la iteración ksil_k< A,donde A es un grado de exactitud definido por el usuario. *

La diferencia entre los métodos dicótomo y de sección dorada estriba en la forma en que se calculan x_x y x₂. La tabla siguiente presenta las fórmulas.

En el método dicótomo los valores jc, y x₂ se encuentran simétricos respecto del punto medio del actual intervalo de incertidumbre. Esto significa que

La aplicación repetida del algoritmo garantiza que la longitud del intervalo de incertidumbre se acercará al nivel de exactitud deseado, A.

En el método de la sección dorada la idea es de mayor involucramiento. Se puede apreciar que cada iteración del método dicótomo requiere calcular los dos valores/(jc,) y f(x₂), P^e” ro termina por descartar alguno de ellos. Lo que propone el método de la sección dorada es ahorrar cálculos mediante el reuso del valor descartado en la iteración inmediata siguiente. Para definir 0 < a < 1

Cuando el intervalo de incertidumbre /, en la iteración i es igual a (jc_¿, x₂) o a (x_u x_R). Considere el caso en que /, = (jc_l, x₂), lo cual significa que x_x está incluido en /,. En la iteración /+1, seleccione x₂ igual a jc, de la iteración /, lo cual lleva a la siguiente ecuación:

x₂(iteración i+l) = x_{(iteración i)

Comparado con el método dicótomo, el método de la sección dorada converge más rápidamente hacia el nivel deseado de exactitud. Adicionalmente, cada iteración en el método de la sección dorada requiere la mitad de los cálculos, en virtud de que recicla siempre un conjunto de los cálculos correspondientes a la iteración inmediata anterior.

EJEMPLO

El máximo valor de f(x) ocurre en x = 2. La siguiente tabla muestra los cálculos para las iteraciones 1 y 2, usando el método dicotomo y el de la sección dorada. Supondremos que A = 0.1.

Al continuar de la misma forma, el intervalo de incertidumbre terminará por estrecharse hasta la tolerancia A deseada.

La plantilla ch21DichotomousGoldenSection.xls de Excel está diseñada para manejar cualquiera de estos dos métodos en forma automática. Los datos son/(*), a,b y A. La función f{x) se captura en la celda E3 como sigue:

= IF(C3< = 2,3*C3, (-C3+20)/3)

OPTIMIZACIÓN NO RESTRINGIDA

Los problemas de optimización no restringida no tienen restricciones, por lo que la función objetivo es sencillamente

Maximizar f(x)

sobre todos los valores x= (x1, x₂,…,x_n). Según el repaso del apéndice 3, la condición necesaria para que una solución específica x = x* sea óptima cuando f(x) es una función diferenciable es

Cuando f (x) es cóncava, esta condición también es suficiente, con lo que la obtención de x* se reduce a resolver el sistema de las necuaciones obtenidas al establecer las n derivadas parciales iguales a cero. Por desgracia, cuando se trata de funciones no lineales f (x), estas ecuaciones suelen ser no lineales también, en cuyo caso es poco probable que se pueda obtener una solución analítica simultánea. ¿Qué se puede hacer en ese caso? Las secciones 13.4 y 13.5 describen procedimientos algorítmicos de búsqueda para encontrar x* primero para n = 1 y luego para n > 1. Estos procedimientos también tienen un papel importante en la solución de varios tipos de problemas con restricciones, que se describirán en seguida. La razón es que muchos algoritmos para problemas restringidos están construidos de forma que se adaptan a versiones no restringidas del problema en una parte de cada iteración.

Cuando una variable Xj tiene una restricción de no negatividad, x- > 0, la condición necesaria (y tal vez) suficiente anterior cambia ligeramente a

para cada j de este tipo. Esta condición se ilustra en la figura 13.11, donde la solución óptima de un problema con una sola variable es x = 0 aun cuando la derivada ahí es negativa y no cero. Como este ejemplo tiene una función cóncava para maximizar sujeta a una restricción de no negatividad, el que su derivada sea menor o igual a 0 en # = 0, es una condición necesaria y suficiente para que x= 0 sea óptima.

Un problema que tiene algunas restricciones de no negatividad y que no tiene restricciones funcionales es un caso especial (m = 0) de la siguiente clase de problemas.

OPTIMIZACIÓN LINEALMENTE RESTRINGIDA

Los problemas de optimización linealmente restringida se caracterizan por restricciones que se ajustan por completo a la programación lineal, de manera que todas las funciones de restricción g¡ (x) son lineales, pero la función objetivo es no lineal. El problema se simplifica mucho si sólo se tiene que tomar en cuenta una función no lineal junto con una región factible de programación lineal. Se han desarrollado varios algoritmos especiales basados en una extensión del método símplex para analizar la función objetivo no lineal.

Un caso especial importante descrito a continuación es la programación cuadrática.

PROGRAMACIÓN CUADRÁTICA

De nuevo los problemas de programación cuadrática tienen restricciones lineales, pero ahora la función objetivo /(x) debe ser cuadrática.Entonces, la única diferencia entre éstos y un

problema de programación lineal es que algunos términos de la función objetivo incluyen el cuadrado de una variable o el producto de dos variables.

PROGRAMACIÓN CONVEXA

La programación convexa abarca una amplia clase de problemas, entre ellos como casos especiales, están todos los tipos anteriores cuando /(x) es cóncava. Las suposiciones son

f(x) es cóncava.
Cada una de las g(x) es convexa.

PROGRAMACIÓN SEPARABLE

La programación separable es un caso especial de programación convexa, en donde la suposición adicional es

Todas las funciones f(x) y g(x) son funciones separables.

Una función separable es una función en la que cada término incluye una sola variable, por lo que la función se puede separar en una suma de funciones de variables individuales. Por ejemplo, si f(x) es una función separable, se puede expresar como

son cada tina funciones de una sola variable x1 y x₂, respectivamente. Usando el mismo razonamiento, se puede verificar que la función considerada en la figura 13.7 también es una función separable.

Es importante distinguir estos problemas de otros de programación convexa, pues cualquier problema de programación separable se puede aproximar muy de cerca mediante uno de programación lineal y, entonces, se puede aplicar el eficiente método símplex.

PROGRAMACIÓN NO CONVEXA

La programación no convexa incluye todos los problemas de programación no lineal que no satisfacen las suposiciones de programación convexa. En este caso, aun cuando se tenga éxito en encontrar un máximo local, no hay garantía de que sea también un máximo global. Por lo tanto, no se tiene un algoritmo que garantice encontrar una solución óptima para todos estos problemas; pero sí existen algunos algoritmos bastante adecuados para encontrar máximos locales, en especial cuando las formas de las funciones no lineales no se desvían demasiado de aquellas que se supusieron para programación convexa. En la sección 13.10 se presenta uno de estos algoritmos.

Ciertos tipos específicos de problemas de programación no convexa se pueden resolver sin mucha dificultad mediante métodos especiales. Dos de ellos, de gran importancia, se presentarán más adelante.

PROGRAMACIÓN GEOMÉTRICA

Cuando se aplica programación no lineal a problemas de diseño de ingeniería, muchas veces la función objetivo y las funciones de restricción toman la forma

En tales casos, las c_i y a _ty representan las constantes físicas y las x_} son las variables de diseño. Estas funciones por lo general no son ni cóncavas ni convexas, por lo que las técnicas de programación convexa no se pueden aplicar directamente a estos problemas deprogramacióngeo- métrica. Sin embargo, existe un caso importante en el que el problema se puede transformar en un problema de programación convexa equivalente. Este caso es aquel en el que todos los coeficientes c¿ en cada función son estrictamente positivos, es decir, las funciones son polinomios positivos generalizados (ahora llamados posinomiales), y la función objetivo se tiene que minimizar. El problema equivalente de programación convexa con variables de decisión y_x, y₂,…, y_n se obtiene entonces al establecer

en todo el modelo original. Ahora se puede aplicar un algoritmo de programación convexa. Se ha desarrollado otro procedimiento de solución para resolver estos problemas de programación posinomial, al igual que para problemas de programación geométrica de otros tipos.¹

PROGRAMACIÓN FRACCIONAL

Suponga que la función objetivo se encuentra en la forma de una fracción, esto es, la razón o cociente de dos funciones,

Estos problemas de programación fraccional surgen, por ejemplo, cuando se maximiza la razón de la producción entre las horas-hombre empleadas (productividad), o la ganancia entre el capital invertido (tasa de rendimiento), o el valor esperado dividido entre la desviación estándar de alguna medida de desempeño para una cartera de inversiones (rendimiento/riesgo). Se han formulado algunos procedimientos de solución especiales¹ para ciertas formas de f1(x) y f2 (x)

Cuando se puede hacer, el enfoque más directo para resolver un problema de programación fraccional es transformarlo en un problema equivalente de algún tipo estándar que disponga de un procedimiento eficiente. Para ilustrar esto, suponga que f(x) es de la forma de programación fraccional lineal

donde c y d son vectores renglón, x es un vector columna y c₀ y d_Q son escalares. También suponga que las funciones de restricción g¡ (x)son lineales, es decir, las restricciones en forma matricial son Ax < b y x > 0.

Con algunas suposiciones débiles adicionales, el problema se puede transformar en un problema equivalente de programación lineal si se establece

3.4 Optimización clásica

La teoría de optimización clásica o programación matemática está constituida por un conjunto de resultados y métodos analíticos y numéricos enfocados a encontrar e identificar al mejor candidato de entre una colección de alternativas, sin tener que enumerar y evaluar explícitamente todas esas alternativas. Un problema de optimización es, en general, un problema de decisión.

Con el fin de ilustrar de forma adecuada la estructura y composición de un problema de optimización, introduciremos a continuación un sencillo ejemplo.

Ejemplo 1(Construcción de una caja con volumen máximo) Supongamos que queremos determinar las dimensiones de una caja rectangular de forma que contenga el mayor volumen posible, pero utilizando para ello una cantidad fija de material. El problema en forma abstracta se podría plantear en los siguientes términos Maximizar Volumen de la caja sujeto a Área lateral fija Con el fin de resolver este problema habrá que modelizarlo matemáticamente, es decir tendremos que expresarlo en términos matemáticos.

El primer paso para modelizar un problema de optimización es identificar y definir las variables que están implicadas en dicho problema, en este caso y puesto que estamos tratando de determinar el tamaño de una caja rectangular, la opción más clara es considerar como variables sus tres dimensiones rectangulares usuales (ancho, largo, alto) y que representamos con x, y, z. Con estas variables, la función para la que tenemos que encontrar el mejor valor será el volumen de la caja que puede expresarse como V (x, y, z) = xyz.

A continuación debemos tener en cuenta las limitaciones existentes sobre el material. Como este material se utiliza para construir las paredes de la caja, necesitaremos considerar el área lateral de la misma, y si la caja tiene tapa, dicha área será A (x, y, z)= 2(xy + yz + zx).

Por último, teniendo en cuenta que las dimensiones de la caja no pueden ser negativas el problema puede expresarse matemáticamente como Maximizar xyz sujeto a 2 (xy + yz + zx) = A x, y, z ≥ 0.

Fundamentos de Optimización

En este ejemplo se distinguen tres elementos fundamentales: las variables del problema, una función de esas variables y un conjunto de relaciones que deben cumplir las variables del problema. Estos elementos se repetirán en todos los problemas de optimización y se definen formalmente a continuación:

1.- Variables de decisión: El primer elemento clave en la formulación de problemas de optimización es la selección de las variables independientes que sean adecuadas para caracterizar los posibles diseños candidatos y las condiciones de funcionamiento del sistema. Como variables independientes se suelen elegir aquellas que tienen un impacto significativo sobre la función objetivo.

Representaremos las variables independientes se representarán mediante vectores columna de Rn x = x1 . . . + xn o vectores fila xt= (x1,...,xn) Aunque para los casos n = 1, 2 y 3 se emplearán las notaciones usuales de x, (x, y) y (x, y, z) respectivamente.

2.- Restricciones: Una vez determinadas las variables independientes, el siguiente paso es establecer, mediante ecuaciones o inecuaciones las relaciones existentes entre las variables de decisión. Estas relaciones son debidas, entre otras razones, a limitaciones en el sistema, a leyes naturales o a limitaciones tecnológicas y son las llamadas restricciones del sistema. Podemos distinguir dos tipos de restricciones:

(a) Restricciones de igualdad: Son ecuaciones entre las variables de la forma h (x) = h (x1,....xn)=0 donde g : A ⊆ Rn → R es una función real de variables reales definida sobre un conjunto A de números reales.

(b) Restricciones de desigualdad: Son inecuaciones entre las variables de la forma g (x) = g(x1,....xn) ≤ 0 donde A : C ⊆ Rn → R es una función real de variables reales definida sobre un conjunto A de números reales.

Observación: Solamente se han considerado restricciones de dos tipos: restricciones de igualdad del forma h (x1,....xn)=0 y restricciones de desigualdad de la forma g(x1,....xn) ≤ 0, debido a que siempre es posible, mediante una simple transformación, expresar el problema en términos de esta clase de restricciones.

Función objetivo: Finalmente, el último ingrediente de un problema de optimización es la función objetivo, también llamado índice de rendimiento o criterio de elección. Este es el elemento utilizado para decidir los valores adecuados de las variables de decisión que resuelven el problema de optimización. La función objetivo permite determinar los mejores valores para las variables de decisión. Independientemente del criterio seleccionado, dentro del contexto de la optimización matemática el adjetivo “mejor” siempre indica los valores de las variables de decisión que producen el mínimo o máximo valor (según el criterio utilizado) de la función objetivo elegida. Algunos de estos criterios pueden ser por ejemplo de tipo económico (coste total, beneficio), de tipo tecnológico (energía mínima, máxima capacidad de carga, máxima tasa de producción) o de tipo temporal (tiempo de producción mínimo) entre otros.

Puntos de Inflexión

Se define un punto de inflexión como el punto en que la función pasa de ser convexa a cóncava o de cóncava a convexa.

En la siguiente gráfica podemos ver que cuando x = 0, la gráfica pasa de ser cóncava a ser convexa, por lo que podemos decir que el punto de inflexión esta en X = 0.

Una característica de los puntos de inflexión es que son los puntos donde la función derivada tiene máximos y mínimos. Si nos fijamos, cuando nos acercamos a un punto de inflexión la función cada vez crece más (o decrece menos), pero al sobrepasar el punto de inflexión la función empieza a crecer menos (o decrecer menos). Esto significa que justamente donde haya un punto de inflexión la derivada tendrá un máximo o un mínimo. Consecuentemente encontraremos los puntos de inflexión buscando ceros de la segunda derivada.

Vamos a ilustrar el proceso con un ejemplo para así dar una explicación simple y clara:

Consideraremos la función F(x) = x³ - 3x (es la función representada en la anterior gráfica).

Sabemos ya calcular los máximos y los mínimos de la función f(x) usando la primera derivada. La expresión de ésta es 3x² - 3 y justamente encontramos máximos y mínimos respectivamente en x = -14 y x = 1 . Si representamos la gráfica de la derivada queda:

Observamos que justamente donde la derivada tiene un mínimo es donde la función tiene el punto de inflexión.

Para saber qué punto es vamos a derivar la función derivada e igualarla a cero: F´´(x) = 6x=0 = x = 0/6 = 0, y por tanto la función original en x = 0 tiene un punto de inflexión.

Máximos y Mínimos

Loas máximos y mínimos de una función son los valores más grandes o más pequeños de ésta, ya sea en una región o en todo el dominio.

Los máximos y mínimos en una función f son los valores más grandes (máximos) o más pequeños (mínimos) que toma la función, ya sea en una región (extremos relativos) o en todo su dominio (extremos absolutos).

A continuación tenemos un vídeo acerca de lo que es optimización clásica

Bibliografía

http://www.sangakoo.com/es/temas/concavidad-y-convexidad-puntos-de-inflexion-de-una-funcion

http://nuyoo.utm.mx/~jjf/rna/guia_foe.pdf

http://www.universoformulas.com/matematicas/analisis/maximos-minimos-funcion/

domingo, 8 de octubre de 2017

Método Vogel

MÉTODO DE APROXIMACIÓN DE VOGEL

El método de aproximación de Vogel es un método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo produce mejores resultados iniciales que los mismos.

miércoles, 4 de octubre de 2017

Programación de proyectos (PERT - CPM)

El PERT/CPM fue diseñado para proporcionar diversos elementos útiles de información para los administradores del proyecto. Primero, el PERT/CPM expone la “ruta crítica” de un proyecto. Estas son las actividades que limitan la duración del proyecto.

La principal 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 pueden variar cambiando el nivel de recursos utilizados.

DEFINICION DEL PROYECTO

En toda actividad a realizar se requieren conocimientos precisos y claros de lo que se va a ejecutar, de su finalidad, viabilidad, elementos disponibles, capacidad financiera, etc. Esta etapa aunque esencial para la ejecución del proyecto no forma parte del método.

CONSTRUCCIÓN DE DIAGRAMAS DE PERT – CPM

Listado de las actividades que constituyen un diagrama.

Lo primero que hay que hacer para constituir un diagrama PERT es organizar una lista, lo más completa posible, de todas las actividades que constituyen la obra o proyecto. Para ello es necesario que la persona que va a hacer el PERT/CPM estudie cuidadosamente el proyecto y se valga de las informaciones de todas las demás personas que estén relacionadas con las mismas, tales como ingenieros, técnicos, fabricantes de materiales, ensambladores, maestros y cualesquiera otros auxiliares que puedan proporcionar una información.

Numeración de los eventos.

Después de realizado un diagrama PERT, debemos numerar los eventos. La manera más correcta de hacerlo es la siguiente: Se numera cada evento, saltando de uno a otro en el sentido de las flechas que representan las actividades, teniendo cuidado de no numerar ninguno, sin que todos los demás que lo precedan en el diagrama hayan sido ya numerados. Así, antes debemos enumerar un evento, verificaremos cuántas flechas llegan a él.

PROGRAMACIÓN DE PROYECTOS

Una vez elaborado el diagrama queda clara la secuencia de actividades y se puede pasar a la programación de las mismas. Para ello, es necesario conocer las duraciones de las distintas actividades. Generalmente, éstas no se pueden fijar con exactitud, ya que son muchos los factores de carácter aleatorio que están relacionados con ellas.

COSTOS Y PENDIENTES

En este paso se solicitarán los costos de cada actividad realizada en tiempo estándar y en tiempo óptimo. Ambos costos deben ser proporcionados por las personas responsables de la ejecución, en concordancia con los presupuestos ya suministrados por ellos. Dichos costos se deben anotar en la matriz de información

GRAFICACIÓN DE UN DIAGRAMA PERT-CPM

Lo mas importante para la creación de un diagrama PERT – CPM es saber concatenar y tomar decisiones con relación a las actividades que determinan un proyecto.

CONTROL DE PROYECTOS CON DIAGRAMAS PERT

Una vez conocido el plazo de ejecución del proyecto, así como las fechas de cada una de las actividades que lo componen, habrá que realizar un seguimiento del mismo. Para ello, la información obtenida en los controles periódicos debe trasladarse al diagrama. Partiendo de un diagrama sin fechas. los pasos a seguir para ver la marcha prevista después del momento de control son los siguientes:

•Se pone como fecha inicial del proyecto la fecha del control.
•Las actividades que hayan finalizado se considerarán con duración nula.
•Las actividades en curso se programarán con una duración igual al tiempo estimado para su terminación.
•Las actividades que no hayan comenzado seguirán con la duración inicial.

Problemas de la ruta más corta

Problemas de la ruta más corta

Este tipo de problemas busca encontrar la ruta más corta entre dos nodos de una red, en la cual la longitud o arco tiene un costo positivo y así minimizar el costo total. Este tipo de problemas es fundamental en áreas como investigación de operaciones, ciencia de la computación e ingeniería. El por qué de su importancia es:

Aplicaciones prácticas como el envío de algún material entre dos puntos específicos de forma eficiente, económica o rápida.
Al ser aplicados a una red con características especificas como acíclica y costos positivos, los resultados que arroja son exactos a un tiempo y costo razonables.
Se puede usar como inicio en un estudio de modelos complejos de redes, que es cuando no se conoce la estructura de la red.
Se utiliza como subproblemas en la solución de problemas combinatorios y redes, resultan auxiliares para encontrar una buena solución.

Tiene aplicaciones prácticas como: encontrar la ruta corta y rápida de un punto a otro, redes eléctricas, telecomunicaciones, transporte, planeación de inventarios, administración de proyectos,diseño de movimiento en robótica, etc.

Ruta más corta en programación lineal: Se puede plantear como el envío de una unidad de flujo del nodo origen al nodo destino al mínimo costo. Se pueden presentar de diferentes formas:

Para que exista solución, debe existir una trayectoria. Además de que no existen circuitos negativos.
Debe existir rutas del nodo origen a los nodos de la red.
Entre cada par de nodos debe existir al menos una trayectoria.

El algoritmo de la ruta más corta consta de los siguientes elementos:

Nodo origen, comienza de la ruta.
Arco, línea que une los nodos.
Nodo adyacente, nodos conectados por un arco.
Nodo destino, finaliza la ruta.
Etiquetas, estas nos van indicando la longitud de un arco otro y de qué nodo viene, se representa entre corchetes [distancia del nodo, nodo del que parte]

A continuación se presenta un vídeo de cómo se resuelve un problema de ruta corta.

Bibliografía
http://www.academia.edu/17257056/PROBLEMA_DE_LA_RUTA_M%C3%81S_CORTA

Esquina noroeste

MÉTODO DE LA ESQUINA NOROESTE

El método de la esquina Noroeste es un algoritmo heurístico capaz de solucionar problemas de transporte o distribución mediante la consecución de una solución básica inicial que satisfaga todas las restricciones existentes sin que esto implique que se alcance el costo óptimo total.

Este método tiene como ventaja frente a sus similares la rapidez de su ejecución, y es utilizado con mayor frecuencia en ejercicios donde el número de fuentes y destinos sea muy elevado.

Su nombre se debe al génesis del algoritmo, el cual inicia en la ruta, celda o esquina Noroeste. Es común encontrar gran variedad de métodos que se basen en la misma metodología de la esquina Noroeste, dado que podemos encontrar de igual manera el método e la esquina Noreste, Sureste o Suroeste.

ALGORITMO DE RESOLUCIÓN DE LA ESQUINA NOROESTE

Se parte por esbozar en forma matricial el problema, es decir, filas que representen fuentes y columnas que representen destinos, luego el algoritmo debe de iniciar en la celda, ruta o esquina Noroeste de la tabla (esquina superior izquierda).

PASO 1:

En la celda seleccionada como esquina Noroeste se debe asignar la máxima cantidad de unidades posibles, cantidad que se ve restringida ya sea por las restricciones de oferta o de demanda. En este mismo paso se procede a ajustar la oferta y demanda de la fila y columna afectada, restándole la cantidad asignada a la celda.

PASO 2:

En este paso se procede a eliminar la fila o destino cuya oferta o demanda sea 0 después del "Paso 1", si dado el caso ambas son cero arbitrariamente se elige cual eliminar y la restante se deja con demanda u oferta cero (0) según sea el caso.

PASO 3:

Una vez en este paso existen dos posibilidades, la primera que quede un solo renglón o columna, si este es el caso se ha llegado al final el método, "detenerse".

La segunda es que quede más de un renglón o columna, si este es el caso iniciar nuevamente el "Paso 1".

EJEMPLO DEL MÉTODO DE LA ESQUINA NOROESTE

Por medio de este método resolveremos el problema de transporte propuesto y resuelto en módulos anteriores mediante programación lineal.

EL PROBLEMA

Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.

Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.

Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.

Formule un modelo de programación lineal que permita satisfacer las necesidades de todas las ciudades al tiempo que minimice los costos asociados al transporte.

SOLUCIÓN PASO A PASO

Ahora la cantidad asignada a la esquina noroeste es restada a la demanda de Cali y a la oferta de la "Planta 1", en un procedimiento muy lógico. Dado que la demanda de Cali una vez restada la cantidad asignada es cero (0), se procede a eliminar la columna. El proceso de asignación nuevamente se repite.

Continuamos con las iteraciones.

En este caso nos encontramos frente a la elección de la fila o columna a eliminar (tachar), sin embargo podemos utilizar un criterio mediante el cual eliminemos la fila o columna que presente los costos más elevados. En este caso la "Planta 2".

Nueva iteración.

Una vez finalizada esta asignación, se elimina la "Planta 3" que ya ha sido satisfecha con la asignación de 60 unidades, por ende nos queda una sola fila a la cual le asignamos las unidades estrictamente requeridas y hemos finalizado el método.

El cuadro de las asignaciones (que debemos desarrollarlo paralelamente) queda así:

Los costos asociados a la distribución son:

El costo total es evidentemente superior al obtenido mediante Programación Lineal y el Método de Aproximación de Vogel, lo cual demuestra lo enunciado en la descripción del algoritmo que cita que no obtiene siempre la mejor solución, sin embargo presenta un cumplimiento de todas las restricciones y una rapidez de elaboración, lo cual es una ventaja en problemas con innumerables fuentes y destinos en los cuales no nos importe más que satisfacer las restricciones.

Vídeo con la solución a este problema.

Obtenido de:

https://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-de-la-esquina-noroeste/