Métodos Cuantitativos:

Programación Entera

Elaborado por Eva Solís/Justo Ramos

 Programación Entera
ES TAMBIÉN CONOCIDA COMO
PROGRAMACIÓN LINEAN ENTERA
Los modelos de programación entera son una
extensión de los modelos lineales en donde la
totalidad o un subconjunto de las variables de
decisión toman valores enteros.
A diferencia de la Programación Lineal, en
algunos casos se requiere que la solución óptima
se componga de valores enteros para algunas de
las variables.

2
 Programación Entera
Este tipo de modelos permite
representar sistemas mucho más
complejos.
Hay problemas que por su
naturaleza los valores de las
variables de decisión no pueden
contener decimales.
 Por ejemplo: casos de
fabricación de muebles para su
venta, asistencia de personas a
eventos (binario), etc.
3
 Programación Entera
Los creadores e investigadores de esta
técnica fueron Wagner, Manne y
Gomory, quienes desarrollaron varios
métodos de solución.
Uno de los primeros enfoques de
solución al tipo de problemas que plantea
la programación entera, fue el de
evaluación de cada posible solución, es
decir, cada una de las combinaciones de Ralph Gomory
valores enteros para las variables del
problema, conduciendo a una solución
óptima exacta. Alan S. Manne
4
 Programación Entera
Tenemos tres tipos de problemas que son:

Programación Entera Programación Entera Programación Entera

Pura (PEP) Mixta (PEM) Binarios (PEB)
Son aquellos que sus Sus variables son tanto Sus variables solo
variables son enteras como continuas pueden tomar valores
únicamente enteras de 1(exito) o 0(fracaso)

   
 

5
Métodos de Solución
Ramificación Método
y Acotamiento Gráfico

Planos Enumeración
de Corte Implícita

6
Observaciones Generales de Algunos Métodos
de Solución
El método de Branch and El método gráfico es un procedimiento
Bound (o Ramificación y Acotamiento) es de solución de problemas de
un algoritmo diseñado para la resolución programación lineal, muy limitado en
de modelos de Programación Entera. Su cuanto al número de variables (pueden
operatoria consiste en linealizar el modelo ser dos o tres) pero muy rico en materia
de Programación Entera, es decir, resolver de interpretación de resultados e incluso
éste como si fuese un modelo de  análisis de sensibilidad.
Programación Lineal y luego generar
cotas en caso que al menos una variable
de decisión (entera) adopte un valor
fraccionario.

7
Algoritmo de Ramificación y
Acotación (Branch and
Bound)

8
 Algoritmo de Ramificación y Acotación

◎ El método de ramificación y acotación

o también llamado Branch and Bound,
resuelve el problema de tal forma que
si la solución a este verifica
condiciones de integridad, entonces
también es la solución al problema
entero, de lo contrario se comienza
con la ramificación del problema.

9
 Algoritmo de Ramificación y Acotación

◎ La ramificación consiste en dividir cada problema en dos nuevos

subproblemas, obtenidos mediante el uso de restricciones
excluyentes que dividen el conjunto de oportunidades del problema
original en dos partes, pero eliminando en ambas partes la solución
no entera del problema original.

10
 Algoritmo de Ramificación y Acotación

◎ primer
En   lugar no se considera la restricción de que las variables
deben ser enteras y se busca el optimo, este se conoce como problema
relajado.
Con la solución optima (ej, , ), se comienza a realizar la ramificación
del problema.
◎ Se escoge una variable del problema cuya solución no sea entera
(no las de holgura) y se ramifica (agrega una restricción).
◎ Por un lado haciendo que y por la otra rama

11
Algoritmo de Ramificación y Acotación
P(0)
Cada ramificación, significa una
restricción extra al problema
independiente a la otra rama.
Luego de que la variable asume el valor
𝑋
  ≤[ 𝑎 ] 𝑋
  ≥ [ 𝑎 ] +1 de la restricción, se debe recalcular el
valor de las demás variables de a cuerdo
a las restricciones, considerando las
P(1) P(2)
originales del problema y las que se han
Y
ido agregando a lo largo del desarrollo.

12
Algoritmo de Ramificación y Acotación
P(0) Si el problema no es infactible se
debe ramificar ahora considerando
otra variable, hasta que se llegue a
una solución con variables enteras
cuya función objetivo es mayor (o
𝑋
  ≤[ 𝑎 ] 𝑋
  ≥ [ 𝑎 ] +1 menor dependiendo del caso) al
valor de las funciones objetivos de
todas las demás ramas.
P(1) P(2)
Al ir ramificando, el valor de la
Y función objetivo siempre ira
disminuyendo (si es Max) o
aumentando (si es Min).

13
 Ejemplo:
◎ La compañía General Electric fabrica dos productos que son
populares con los restauradores de casas: candelabros y
ventiladores de techo de estilo antiguo. Tanto los candelabros
como los ventiladores requieren un proceso de producción de dos
pasos, que implica cableado y ensamble. Se requieren 2 horas
para cablear cada candelabro y 1 para cablear un ventilador de
techo. El ensamble final de los candelabros y los ventiladores
requiere de 2 y 3 horas, respectivamente. La capacidad de
producción es tal que solamente están disponibles 6 horas de
cableado y 9 horas de ensamble. Si cada candelabro producido
reditúa a la empresa $3 y cada ventilador $4. ¿Cuál es la solución
óptima para este problema?

14
Ejemplo:
  Función Objetivo

  = # de candelabros producidos
  = # de ventiladores producidos

  Sujeta a:
(horas de cableado)
(horas de ensamble)
, enteras

  9 3
Solución relajada: 𝑥1 = 4 , 𝑥 2= 2

15
Ejemplo:
  Sujeta a: 9 3
(horas de cableado) Solución relajada: 𝑥  1 = , 𝑥 2=
4 2
(horas de ensamble)
, enteras
Demostración
  + =6 Despejar   + =6 Reemplazar
 
 
= 
  =6
  + =9 Reemplazar
 = 6 -
  + =9
 =
  2=9
 =
 2 = 9 - 6
= 
16
 Algoritmo de Ramificación y Acotación
P(0)
Nota: Cuando todas son decimales, se
puede escoger cualquier variable.

   
s.a.  𝑥1 ≤ 2  𝑥1 ≥3 s.a.

P(1) P(2)

𝑥  1 =2 𝑥  1 =3

   
Solución Entera
17
 Algoritmo de Ramificación y Acotación
P(1)

   
s.a. s.a.
 𝑥2 ≤1  𝑥2 ≥ 2

P(3) P(4)

𝑥  2 =1 𝑥  2 =2

   

Solución Entera
18
 Algoritmo de Ramificación y Acotación
P(4)

   
s.a. s.a.

 𝑥1 ≤1  𝑥1 ≥ 2

P(5) P(6)

𝑥  1 =1 𝑥  1 =2

   

19
 Algoritmo de Ramificación y Acotación
P(5)
   
s.a. s.a.

 𝑥2 ≤ 2  𝑥2 ≥3

P(7) P(8)

𝑥  2 =2 𝑥  2 =3

   

Solución Entera Solución Final

20
Ejemplo:
  Función Objetivo
  = 0 candelabros producidos
  = 3 ventiladores producidos

  Función Objetivo

Según este modelo cuantitativo se ha determinado que

se deben producir 3 ventiladores y 0 candelabros bajo
estas condiciones para obtener una ganancia de $12

21
 😉
Gracias por
su atención

22
 Infografía
 [Link]
_ii/unidad_5/[Link]
 [Link]
 [Link]
f
 [Link]
 [Link]
 [Link]

23
 Big concept
Bring the attention of your
audience over a key concept
using icons or illustrations

24
You can also split your content

White Black
Is the color of milk and fresh Is the color of ebony and of outer
snow, the color produced by the space. It has been the symbolic
combination of all the colors of color of elegance, solemnity and
the visible spectrum. authority.

25
In two or three columns

Yellow Blue Red

Is the color of gold, Is the colour of the Is the color of blood,
butter and ripe lemons. clear sky and the deep and because of this it
In the spectrum of sea. It is located has historically been
visible light, yellow is between violet and associated with
found between green green on the optical sacrifice, danger and
and orange. spectrum. courage.

26
 Want big
impact?
Use big image.

27
Use charts to explain your ideas

White Gray Black

28
Or diagrams to explain complex ideas

Example text. Example text.

Lorem ipsum dolor sit amet, Lorem ipsum dolor sit amet,
consectetur adipiscing elit. consectetur adipiscing elit.
Nam venenatis nisi at nisl Nam venenatis nisi at nisl
tempor, et luctus diam lobortis. tempor, et luctus diam lobortis.
Nulla sit amet metus consequat Nulla sit amet metus consequat
velit iaculis tempor. velit iaculis tempor.

29
And tables to compare data

A B C

Yellow 10 20 7

Blue 30 15 10

Orange 5 24 16

30
Maps

our office

31
 89,526,124
Whoa! That’s a big number, aren’t you proud?

32
89,526,124$
That’s a lot of money

185,244 users
And a lot of users

100%
Total success!

33
Our process is easy

last

first

second

34
Let’s review some concepts

Yellow Blue Red

Is the color of gold, butter and ripe Is the colour of the clear sky and the Is the color of blood, and because of
lemons. In the spectrum of visible deep sea. It is located between violet this it has historically been
light, yellow is found between green and green on the optical spectrum. associated with sacrifice, danger and
and orange. courage.

Yellow Blue Red

Is the color of gold, butter and ripe Is the colour of the clear sky and the Is the color of blood, and because of
lemons. In the spectrum of visible deep sea. It is located between violet this it has historically been
light, yellow is found between green and green on the optical spectrum. associated with sacrifice, danger and
and orange. courage.

35
You can copy&paste graphs from Google Sheets

36
 Place your screenshot here
Tablet project
Show and explain your web,
app or software projects using
these gadget templates.

37
 Place your screenshot here

Desktop project
Show and explain your web, app or software projects using these gadget templates.
38
Thanks!
Any questions?
You can find me at:
@username & user@[Link]

39
Credits

Special thanks to all the people who made and released

these awesome resources for free:
◎ Presentation template by SlidesCarnival
◎ Photographs by Unsplash

40
Presentation design

This presentations uses the following typographies and colors:

◎ Titles: Roboto Slab
◎ Body copy: Source Sans Pro
You can download the fonts on these pages:
[Link]
[Link]

◎ Blue #0091ea
◎ Dark gray #263238
◎ Medium gray #607d8b
◎ Light gray #cfd8dc

You don’t need to keep this slide in your presentation. It’s only here to serve you
as a design guide if you need to create new slides or download the fonts to edit
the presentation in PowerPoint®
41
SlidesCarnival icons are editable shapes.

This means that you can:

● Resize them without losing quality.
● Change line color, width and style.

Isn’t that nice? :)

Examples:

42
Diagrams and infographics

43
� Now you can use any emoji as an icon!
And of course it resizes without losing quality and you can change the color.

�
How? Follow Google instructions
[Link]

✋👆👉👍👤👦👧👨👩👪💃🏃💑❤😂😉😋
😒😭😸💣
👶😸 🐟🍒🍔💣 📌📖🔨🎃🎈🎨🏈🏰🌏🔌🔑
and many more...

44
 Free templates for all your presentation needs

For PowerPoint and 100% free for personal or Ready to use, professional Blow your audience away
Google Slides commercial use and customizable with attractive visuals