PROGRAMACION

Investigacin de operaciones 4.1. Teora de la programacin lineal

Elabor: MC. Marcel Ruiz Martnez 1

UNIDAD II. FUNDAMENTOS DE SISTEMAS 4.1. Teora de la programacin lineal

Programacin lineal. Consiste en un algoritmo matemtico mediante el cual se resuelve un problema que pueda ser formulado a travs de ecuaciones lineales, hay dos tipos de ecuaciones en este modelo: la que representa la funcin objetivo y las que representan las restricciones del problema. Dicha programacin se ver en el siguiente tema.

Este mtodo consiste en optimizar (minimizar o maximizar) una funcin lineal, denominada funcin objetivo, de tal forma que las variables de dicha funcin estn sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.

Algunos casos especiales de programacin lineal, tales como los problemas de flujo de redes y problemas de flujo de mercancas se consideraron en el desarrollo de las matemticas lo suficientemente importantes como para generar por si mismos mucha investigacin sobre algoritmos especializados en su solucin. Histricamente, las ideas de programacin lineal han inspirado muchos de los conceptos centrales de la teora de optimizacin. Del mismo modo, la programacin lineal es muy usada en la microeconoma y la administracin de empresas, ya sea para aumentar al mximo los ingresos o reducir al mnimo los costos de un sistema de produccin. Algunos ejemplos son la mezcla de alimentos, la gestin de inventarios, la cartera y la gestin de las finanzas, la asignacin de recursos humanos y recursos de mquinas, la planificacin de campaas de publicidad, etc.

Modelo de transporte. El modelo de transporte es una clase especial de problema de programacin lineal. Su objetivo es determinar las cantidades enviadas de suministro o productos desde cada punto de origen hasta cada punto de destino, que minimice el costo total del envo, al mismo tiempo deben satisfacer los lmites de oferta como los requerimientos de la demanda.

Mtodo de asignacin. Consiste en un caso especial para el modelo de transporte; donde solo se busca asignar un origen a un destino.

Requisitos para formular un problema de programacin lineal

Todos los modelos de programacin lineal deben tener: Variables Funcin objetivo Restricciones No negatividad

A continuacin veremos un problema, el cual se coloca en un taller de EXCEL con su respectivo video explicativo.

Adicionalmente veremos videos del mtodo grfico y del simplex.



Ejemplo 1: Un negocio se dedica a la fabricacin de sillas y mesas; fabricar cada uno consume una determinada cantidad de tiempo (en horas) de los departamentos corte y ensamble.

Los departamentos tienen disponibles una limitada cantidad de horas de trabajo: 120 horas para corte y 90 horas para ensamble.

Cada uno de los productos ofrecen a la empresa la siguiente contribucin: $50 USD para las mesas y $80 USD para las sillas.

La informacin anterior, mas los consumos de tiempo de cada producto se resumen en la siguiente tabla:

Proceso Consumo de tiempo por cada unidad de producto, horas

Tiempo disponible en cada

departamento, horas

Mesas Sillas

Corte 1 2 120 Ensamble 1 1 90 Contribucin del producto

$50 $80

Se pide lo siguiente: Programar la combinacin ptima de productos (cuantas sillas y mesas producir) para obtener la ganancia mxima (o la contribucin mxima)

Solucin: Primero debemos definir el objetivo del problema: MAXIMIZAR LAS GANANCIAS.

A continuacin debemos darnos cuenta que hay dos variables de decisin (cuantas mesas y sillas producir), que podemos manipular para lograr el objetivo de MAXIMIZAR LAS GANANCIAS.

Entonces las variables de decisin son: x1 = mesas a producir x2 = sillas a producir

Ahora debemos encontrar la funcin objetivo, si el objetivo es MAXIMIZAR LAS GANANCIAS, la funcin objetivo debe representar las ganancias.

1 2

Ganancia total (z) = ganancia mesas + ganancia sillasGanancia total (z) = $50x + $80x

Entonces queda la siguiente FUNCIN OBJETIVO: z = $50x1+80x2

Si el dueo del negocio pudiera aumentara las ganancias al infinito y ms all; pero no puede Por qu? Lo detendr algo que se conoce como RESTRICCIONES.

En este problema cules son las restricciones? Hay recursos limitados y es la cantidad de tiempo disponible para cada departamento.

Es decir: Recursos consumidos Recursos TOTALES disponibles

Tiempo consumido en corte Tiempo disponible en corteTiempo consumido en ensamble Tiempo disponible en ensamble

Dado que tenemos los consumos unitarios de cada unidad de producto fabricada x1 = mesas, x2 = sillas.

Si se producen por ejemplo 2 mesas y 1 silla, el departamento de corte habra consumido: Proceso Consumo de tiempo Tiempo

consumido Mesas Sillas Corte 1(2) + 2(1) = 4 horas



Por lo tanto las restricciones son: Departamento Consumido Es menor

o igual Disponible

Corte x1+2x2



Actividad 4.1. Programacin lineal En una empresa que fabrica ensambles mecnicos (tipo A y tipo B) desea aprovechar las unidades sobrantes de materia prima (conectores y tubos) para hacer dichos ensambles. En la tabla siguiente se proporcionan los datos necesarios.

Materia prima Ensamble tipo Unidades Disponibles A B

Conector 5 5 35 Tubo 6 9 56

La empresa gana por el ensamble tipo A $10 USD y por el tipo B $12 USD.

a) Determine cuales son las variables de decisin (x1 y x2) b) Escriba la ecuacin que representa la funcin objetivo (z =?) c) Escriba las restricciones del problema. d) Determine la solucin ptima usando SOLVER de EXCEL

(deber enviar el archivo de EXCEL como evidencia adjunta). e) Resulvalo usando el mtodo grfico (puede ser por PHP o

WINQSB), deber reportar en el archivo en WORD la impresin de pantalla (CTRL + imp pnt) para lograr contestar este inciso.

Entrega tus resultados en forma de PRCTICA DE EJERCICIOS, siguiendo las rbricas indicadas en la direccin: http://marcelrzm.comxa.com/Rubricas/Rubricas.htm

Enviar el documento final por correo electrnico a las siguientes direcciones: [email protected]; [email protected]; [email protected] y [email protected] con copia a usted mismo.

En asunto colocar: ACTIVIDAD 3.2 PROGRAMACION LINEAL

Documents

PROGRAMACION