Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Programación Entera

No description
by

Mariel Rabago

on 23 April 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Programación Entera

Programación Entera
Introducción
Casos de Aplicación
A continuacion se presenta la variedad de problemas que caen dentro de la programacion entera y binaria:
Se divide en tres tipos de modelos:


Programacion entera pura: Todas las variables de decisión tienen valores enteros.
Programacion Entera Mixta (PEM): Algunas de las varibles de decisión tienen valores enteros. Las demas cumplen con la suposicion de divisivilidad.
Programacion Entera Binaria (PEB): Utiliza variables binarias.
DEFINICIÓN Y MODELOS DE PROGRAMACION ENTERA Y BINARIA
El modelo de programacion entera es sencillamente la programacion lineal solo que con las caracteriasticas que con la programacion entera tiene una restriccion de que todas las variables sean valores enteros a este tipo de modelos se les llama programacion entera pura.


Es frecuente al tener que resolver problemas en los cuales las soluciones tienen que ser valores enteros como por ejemplo: números de unidades a producir por máquina, número de máquinas necesarias, etc. Parte del problema de la programación entera radica en la diferencia esencial que existe la programación lineal y la entera, en la programación lineal se maximiza o minimiza una función sobre una región de factibilidad convexa, mientras que al usar los métodos de programación entera se maximiza una función sobre una región de factibilidad que generalmente no es convexa. De tal manera que la programación entera tiene más complicaciones que la programación lineal.


En este tema se presenta un tipo de problemas formalmente similares a los Problemas de programación lineal, ya que en su descripción solo se establecen expresiones lineales. Sin embargo no responden a problemas lineales ya que algunas (o todas) las variables del problema toman valores que no están en un conjunto continuo. Por ejemplo, pueden ser variables que toman valores 0 o 1(binarias), o variables que toman valores enteros no negativos (0, 1,2,...), etc. Tras introducir el tipo de problemas se dedica un importante apartado para presentar las posibilidades de modelado que esta herramienta proporciona: problemas binarios, problemas de carga, problemas con restricciones condicionales o con dicotomías, etc.

En algunos casos se requiere que la solución optima se componga de valores enteros para algunas de las variables. La resolución de este problema se obtiene analizando las posibles alternativas de valores enteros de esas variables en un entorno alrededor de la solución obtenida considerando las variables reales. Muchas veces la solución del programa lineal truncado esta lejos de ser el optimo entero, por lo que se hace necesario usar algún algoritmo para hallar esta solución de forma exacta. El mas famoso es el método de “Ramificacion y Acotacion” o “Branch and Bound“ por su nombre en ingles. El método de ramificación y acotación, parte de la adicion de nuevas restricciones para cada variable de decisión (acotar) que al ser evaluado independientemente (ramificar) lleva al optimo entero.
Todos los problemas de programacion lineal, donde las actividades, por su estructura deben ser no-divisibles, son programas enteros. Por ejemplo problemas de produccion de automoviles, prendas de vestir etc.
Todos los problemas de transporte, asigncion y redes de optimisacion. Este tipo de problemas son enteros y dada la estructura tan especial de estos problemas, tienen metodos de solucion propios.
A.
B.
C.
Problemas de secuenciacion. Este tipo de problemas aunque son faciles de formular, resultan bastante dificiles de resolver. Se supone por ejemplo en el caso de un taller que puede efectuar un solo tipo de trabajo a la vez (orden ί), el que se tiene contratado a entregar en gı días, a partir de una cierta fecha base, y que ademas tiene una gran duracion de trabajo de dı (dı > 0) dias y al cuales ocaciona una multa de pı pesos por día de retraso despues de los gı dias estipulados. Se supone que el taller resive n ordenes de trabajo en la fecha base. ¿Cuál debe ser el orden de secuenciasion de trabajos que minimice el costo penal total?
D.
El problema del agente viajero. Este problema concierne en un agente viajero que saliendo de una terminal de ciudad debe visitar una sola vez п -1 cuidades diferentes , y regresar al punto de partida. Si el costo de dirigirse a la ciudad ј desde la ciudad ί es cί
(cί ≠ cί ), se debe terminar la secuencia de visita de cuidades, tal que el costo total asociado sea el minimo. Este problema se presento por primera vez en 1960, en el articulo de Miller, Tucker, Zemling, pero hay una variedad de metodos que resuelven el problema dependiendo del tamaño de п, el numero de ciudades.
E.
Problema tipo mochila. Este tipo de problemas de optimizacion de carácter entero puede darse en dos versiones. En la primera se proporciona un cierto espacio con determinado volumen o capacidad, y este debe ser llenado con objetos de valor y volumen o capacidades especificados. El problema consiste en llenar ese espacio con el conjunto de objetos mas valiosos, sin exceder los limites fisicos de dicho espacio. La segunda version consiste en dividir a un objeto en varias porciones de diferente valor, el problema consiste en encontrar la division de mayor valor.
F.
Problemas de Inversion. Se supone por ejemplo que el organizmo Nacional Financiera S.A., tiene que escoger una alternativa en cada uno de los tres proyectos de inversion. El primero proyecto esta relacionado con la contruccion de partes de generadores electricos. El segundo proyecto con el ensamblado de esas partes de generadores electricos y el tercer proyecto con la distribucion y venta de los generadores electricos incluyendo su posible exportacion. Cada proyecto tiene una serie de alternativas. Asociadas a cada alternativa se tiene calculado el valor presente del retorno total de la inversion (en millones de pesos), el numero de empleados que se generan y el flujo de inversion (en millones de pesos) que se necesitan para los proximos 5 años. Las restricciones del sistema son que no hay capacidad economica para generar mas de 10 mil empleados y que los flujos maximos de capital son de 700 millones en el año uno, 300 millones en el año dos, 150 millones respectivamente en los años tres, cuatro y cinco. ¿Qué alternativas conviene seleccionar de los proyectos I, II y III al fin de maximizar el ingreso total neto anual?
G.
Problemas con costos fijos. Todos los problemas que en su funcion de costo incluye un costo fijo del siguiente tipo
Costo total para la variable

pertenece al grupo de problemas enteros. Este tipo de costos aparecen frecuentemente en problemas de transportes, inventarios, localizacion de plantas, distribucion geografica de electores, etc.
H.
Problemas de cubrimiento y particion de un conjunto. Este tipo de modelos de carácter entero se ha utilizado en problemas de acceso de informacion, programacion de entega de paqueteria por transporte terrestre, distribucion politica electoral, problemas matematicos de coloracion y programacion de horarios de tripulacion aereos, ferrocarrileros, terrestres y maritimos.
Tras dedicar una parte importante del tema a presentar estas herramientas de modelado y a plantear numerosos problemas con ellas se procede a mostrar dos métodos de resolución. Uno de ellos dedicado a problemas en los que todas las variables son binarias y otro para problemas generales. Ambos métodos tienen en común que desarrollan un proceso de enumeración que permite comprobar explícita o implícitamente todas las soluciones del problema hasta encontrar la óptima, y entran dentro del tipo de métodos de ramificación y acotación.

Esto nos quiere decir que la metodologia para resolver los problemas de programacion entera es practicamente el mismo que para hacer la programacion lineal.
La programacion entera mixta (PEM) se ocupa solo cuando algunas de las variables deben ser enteros y las suposicion de divisibilidaad se cumple para el resto.

Esto se da cuando algunos datos deben ser enteros como la cantidad de personal dentro de una empresa ya que no se pueden asignar 2.5 empleados se deben redondear a 3 pero dentro del mismo modelo se asigna el mismo salario ya que puede ser $2,000.50 a estos modelos se les reconoce por (PEM).

Las programaciones enteras binarias son aquellas donde incluyen desiciones de si o no que estan interrelacionadas. En las desiciones de este tipo solo hay dos posibles respuestas a este tipo de desiciones se les puede representar mediante variables de decisión restringidas a dos valores, por ejemplo 0 y 1, a si la ј-esima decision si o nose puede representar por χј tal que:
χј 1 si la decision ј es si o 0 si la decision ј es no.
A este tipo de problemas de programacion entera binaria tambien se le conoce como problemas 0-1 de programacion entera.
METODO DE GOMORY
Se pretende mostrar una de las versiones de Gomory (Fraccional), existen otros, como son el entero y el mixto.
Paso 1: Resolver el problema primal, si la solución es entera, corresponde a la óptima para el problema de Programación Lineal Entera.
Paso 2: Seleccionar decimales y escoger aquel que tenga la mayor parte fraccionaria tomando las ecuaciones completas.
 Paso 3: Se separan la parte entera, es decir, quedarse solamente con la parte fraccionaria.
Nota: Luego de encontrar una solución óptima para el primal, por Simplex y después de agregarle la primera nueva ecuación al sistema se pasa a Dual – Simplex, para quitarle la infactibilidad al sistema.
A partir del siguiente ejemplo, vamos a mostrar la manera de aplicar el algoritmo de Gómory para solucionar un problema de Programación Lineal Entera:
MAX Z = 8 X1+ 5 X2

Solución Óptima Única para el problema primal:
X*1 = 15/4; X*2 = 9/4; S*1= 0; S*2 =0; Z*= 165/4, pero para el problema de Programación Lineal Entera no nos sirve la respuesta, ya que las variables de decisión tienen valores fraccionarios.Para resolver este problema, aplicamos un refinamiento de la Programación Lineal, el cual corresponde al algoritmo de Gomory:
X1- 5/4 S1+ 1/4 S2= 15/4
(1 + 0) X1 + (– 2 + 3/4) S1 + (0 + 1/4) S2 = (3 + 3/4)
3/4 S1 + 1/4 S2 = 3/4 Nueva ecuación
3/4 S1 + 1/4S2 3/4 Nueva restricción
– 3/4 S1– 1/4 S2 + S3 = – 3/4 Ecuación a introducir al sistema
A continuación se aplica el dual - simplex, con el objetivo de quitarle la infactibilidad al sistema.
Full transcript