Algoritmos Especiales de Programación Lineal

¿QUE ES UN LOGARITMO?
1. la programación lineal “consiste en modelar un problema de optimización utilizando, únicamente, inecuaciones lineales”.
  1. distintos métodos para resolver
  2. solución al problema de transporte
    1. solución
      1. Basica Factible Inicial
      2. USO DE SOFWARE
        es una herramienta mas para resolver este tipo de ejercicios
        mas rapido de trabajar
        existen sistemas de sofware que aplican para el desarrollo de este
        estos son algunos
        software WinQsb
        software INVOP
        existen ventajas
        desventajas
        puede presentar problemas
        fallas en el sistema
        los datos pueden perderse
        perdidas economicas
        mas rapido y preciso
        ahorro de tiempo
        es igual ahorro de dinero
        mas ganancias
        costo beneficio
        aumenta el capital de la empresa
        un trabajo mas presentable
        mas preciso
    2. planteamiento
    3. uso de algoritmos
      1. criterio de optimabilidad
  3. PROGRAMACION LINEAL
    1. sistema de solucion a ejercicios
      1. modelos de optimización
      2. ventajas sobre ingresos
        costo
        mas costo beneficio para aumentar capital de la empresa
        gasto
        minimizar gastos y evitar perdidas grandes a la empresa
MODELOS ESPECIALES
1. resuelven problemas de programación lineal
  1. se enuncian con ecuaciones lineales
  2. con una función objetivo
  3. una o mas funciones de restrincción
    1. para lograr la optimización
EL PROBLEMA DE TRANSPORTE
1. es un caso ESPECIAL de Programación
  1. soluciones factibles
  2. Objetivos
    1. minimizar costos de distribución
      1. de numeros de unidades de fuentes
      2. del origen al destino
  3. modelo elemental
    1. en este caso las fuentes pueden actuar como:
      1. 1.- entidades que ofertan cierto numero de unidades
      2. los origenes reciben cierto numero de unidades
        por lo tanto
        los origenes son proveedores de unidades
        los destinos construyen unidades que demandan
2. se puede identificar mediante:
  1. dos factores importantes
    1. 1.- naturaleza
    2. 2.- estructura
      1. del "hacia alla"
    3. esto va a que el problema debe
      1. tener definido su origen y destino
      2. relacion uno con el otro
    4. mediante estos factores podemos
      1. determinar la solucion y metodo
3. contexto en el que se apica es amplio
  1. genera soluciones atinentes
    1. area de operaciones
    2. inventario
    3. asignacion de elementos
  2. Los problemas de transporte o distribución son uno de los más aplicados en la economía actual
    1. un ejemplo base puede ser:
      1. Los sitemas logisticos de una empresa pueden ser los origenes que tiene de produccion dicha planta
        tomando en cuenta
        capacidad instalada de produccion del producto base
        destinos y almacenes que generan demanda del mismo
      2. pero hay pasos que se deben tomar en cuenta a la hora de resolver un problema de este tipo
        PLANTEAMIENTO DEL PROBLEMA
        el problema del transporte en general se especifica mediante la siguiente información
        2.- una lista de capacidades de suministro maximo de cada sitio de oferta si para i=1, 2, 3,...m
        4.- una lista de demandas de utilidades o bienes de J cada punto de demanda J las cuales deben satisfacerse minimamente
        1.- un conjunto de m puntos de oferta desde los cuales se envian utilidades o bienes
        5.- una matriz de valores que indica el costo fijo en el que se incurre al enviar una unidad producida en el punto de oferta i y enviada al punto de demanda j, cij
        3.- un conjunto de n puntos de demanda hacia los cuales se envia una utilidad o bien
        DETERMINACION DE LA SOLUCION BASICA FACTIBLE INICIAL
        la utilizacion del metodo SIMPLEX no resulta eficiente para resolver el problema de transporte
        se utilizan otros metodos como:
        a) Metodo de la esquina Nor.Oeste (N-O)
        CARACTERISTICAS
        sencillo y facil de hacer
        no tiene en cuenta los costos para hacer las asignaciones
        generalmente nos deja lejos del optimo
        NOTA
        no elimine fila y columna al mismo tiempo, a no ser que sea la ultima casilla., el romper esta regla ocasionara una solucion en donde el numero de variables basicas es menor a m+n-1, produciendo una solucion basica factible degenerada
        ALGORITMO
        1.- construya una tabla de ofertas (disponibilidades) y demandas (requerimientos)
        2.- empiece por la esquina nor-oeste
        3.- asigne lo maximo posible (lo menor entre la oferta y la demanda, respectivamente)
        4.- actualice la oferta y la demanda y rellene con ceros el resto de casillas (filas o columnas) en donde la oferta o la demanda halla quedado satisfecha
        5.- muevase a la derecha o hacia abajo, segun halla quedado la disponibilidad para asignar
        6.- repita los pasos del 3 al 5 sucesivamente hasta llegar a la esquina inferior derecha en la que se eliminan fila y columna al mismo tiempo
        b) Metodo de la matriz de Costo Minimo
        CARACTERISTICAS
        tiene en cuenta los costos para hacer las asignaciones
        generalmente nos deja alejados del optimo
        es mas elaborado que el metodo de la esquina Nor-Oeste
        NOTA
        recuerde que no debe eliminar o satisfacer fila y columna al mismo tiempo, caso en que la oferta sea igual a la demanda, en tal caso recuerde usar Epsilon
        ALGORITMO
        1.- construya una tabla de disponibilidades, requerimientos y costos
        2.- empiece en la casilla que tenga el menor costo de toda la tabla, si hay empate escoja arbitrariamente cualquiera
        3.- asigne lo maximo posible entre la disponibilidad y el requerimiento el menor de los dos
        4.- rellene con ceros la fila o columna satisfecha y actualice la disponibilidad y el requerimiento, restandoles lo asignado
        5.- muevase a la casilla con el costo minimo de la tabla resultante
        6.- regrese a los puntos 3, 4, 5 sucesivamente hasta que todas las casillas queden asignadas
        c) Metodo de Vogel
        CARACTERISTICAS
        tiene en cuenta los costos, las ofertas y las demandas para hacer las asignaciones
        generalmente nos deja cerca al optimo
        es mas elaborado que los anteriores, mas tecnico y dispendioso
        NOTA
        recuerde que no debe satisfacer filas y columnas al mismo tiempo: caso en que la disponibilidad sea igual al requerimiento en tal caso use el epsilon
        ALGORITMO
        1.- construir una tabla de disponibilidades ofertas y requerimientos la demanda, y costos
        2.- calcular la diferencia entre el costo mas pequeño y el segundo costo mas pequeño para cada fila y columna
        3.- escoger entre las filas y columnas la que tenga la mayor diferencia en caso de empate decida arbitrariamente
        4.- asigne lo maximo posible en la casilla con menor costo en la fila o columna escogida en el punto 3
        5.- asigne cero a las otras casillas de la fila o columna donde la disponibilidad o el requerimiento queda satisfecho
        repita los pasos del 2 al 5 sin tener en cuenta las filas y/o columnas satisfechas hasta que todas las casillas queden asignadas
4. CRITERIO DE OPTIMALIDAD
  1. determinar la eficacia de los metodos y saber el optimo resultado
  2. ahi se encuentran las variables de entrada y salida
    1. maximizacion
      1. coeficiente mas negativo
    2. minimizacion
      1. coeficiente mas positivo
    3. variable no basica en el renglo Z
    4. en la variable de salida esta la condicion de factibilidad
      1. maximizacion
        coeficiente mas negativo
      2. minimizacion
        coeficiente mas positivo
ALGORITMO DE MEJORAMIENTO DE SOLUCION
1. los metodos analizados no garantizan
  1. es necesario verificar
  2. puede haber una ruta no utilizada
  3. por eso se usan dos metodos para el mejoramiento de la solucion factible inicial
    1. a) Metodo de la Distribucion Modificada
    2. b) Metodo del Paso Secuencial
PROBLEMA DE ASIGNACION
1. dos respuestas exactas
  1. si
    1. 1
  2. no
    1. 0
2. solucion de problemas basicos
  1. mejor conocido como metodo binario
    1. metodo de asignacion
      1. PA
        usa herramientas basicas pero que dan resultados optimos
        es usual usarla
        esta ligada a temas de orden
        es usado en personas para administrar turnos
        PLANTEAMIENTO DEL PROBLEMA
        minimizar el costo total de operacion de modo que
        cada tarea se asigne a una y solo una maquina
        cada maquina realice una y solo una tarea
  2. registra tareas
    1. asigna nuemro para tareas determinadas
    2. con base en algun tipo de valoracion para cada suceso

Next up

Algoritmos Especiales de Programación Lineal

Description

Resource summary

Media attachments

Similar

	Created by Pėrikith0 Azūl almost 4 years ago