7/25/2019 1.-Prog lin ent 2
1/55
CAPITULO I
PROGRAMACIN LINEAL
ENTERA
7/25/2019 1.-Prog lin ent 2
2/55
En este captulo veremos problemas que se
podran formular y resolver como problemas
de programacin lineal, excepto por ladesagradable circunstancia de que se
requiere que algunas o todas las variables
tomen valores enteros.
7/25/2019 1.-Prog lin ent 2
3/55
Dichos problemas se llaman PE
(Programacin Entera.
!a programacin entera ha llegado a
ser un "rea muy especiali#ada de la
ciencia de la administracin.
7/25/2019 1.-Prog lin ent 2
4/55
En este curso slo la tocaremos en
forma superficial, veremos la importancia
del tema y algunos m$todos de
resolucin m"s %tiles.
&imos en los captulos anteriores quelas variables podan tomar valores
fraccionados, tales como 6.34. Pero haycasos en el mundo real que no esposible esto y deben ser enteros.
7/25/2019 1.-Prog lin ent 2
5/55
En el fondo es que existen muchos
problemas administrativos importantesque seran de programacin lineal si no
fuera por el requerimiento de que sean
enteros los valores de algunas
variables de decisin, en los que no se
pueden encontrar una buena solucin
mediante el uso del m$todo simplex
seguido del redondeo de los valoresptimos resultantes para las variables
de decisin.
7/25/2019 1.-Prog lin ent 2
6/55
Estos problemas deben ser resueltos
mediante algoritmos especialmentedise'ados para resolver problemasde programacin entera.
7/25/2019 1.-Prog lin ent 2
7/55
TIPOS DE MODELOSPAA
PO!AMA"I#$ LI$EAL E$TEA
7/25/2019 1.-Prog lin ent 2
8/55
Modelo entero puro (PEP)
7/25/2019 1.-Prog lin ent 2
9/55
inimi#ar )*+ -* /*0
1u2eto a +34*+ 5*
-4*
0-6)
6*+ +4*
*
040
*+, *
, *
0enteros
7/25/2019 1.-Prog lin ent 2
10/55
Programac!n lneal entera"m#ta
(PLEM)
7/25/2019 1.-Prog lin ent 2
11/55
inimi#ar )*+ -*
/*
0
1u2eto a +34*+ 5*
-4*
0-6)
6*+ +4*
*
040
*+
, *
, *0
3 7 *+
y *
enteros.
7/25/2019 1.-Prog lin ent 2
12/55
Pro$lema% $naro%o
Programac!n lnealentera&"'.
7/25/2019 1.-Prog lin ent 2
13/55
Diversos problemas de asignacin,ubicacin de planta, planes deproduccin y de construccin, son
de programacin lineal entera 0-1.Las variables 0-1 se puedenencontrar tanto en problemas dePEP como PLEM.
7/25/2019 1.-Prog lin ent 2
14/55
I$TEPETA"I#$ !A%I"A
7/25/2019 1.-Prog lin ent 2
15/55
aximi#ar +4E )8
1u2eto a E 8 - (+
/.4E +338 433 (
3E )8 +/ (0
03E +38 +0 (/
E 9 08 3 (-
E y 8 enteros
7/25/2019 1.-Prog lin ent 2
16/55
7/25/2019 1.-Prog lin ent 2
17/55
"OME$TAIOS
En un problema de ma&imi'acin(el valor ptimo de la aproximacinP! produce siempre una cota s)periorpara el valor ptimo del P!Eo P!E original. 1i se agregan restricciones de enteros el valor
optimo de la P!, o bien empeorar", o bien quedar" igual. En un
problema de maximi#acin, empeorar el valor ptimo significa
desminuirlo.
En un problema de minimi#acin, el valor ptimo de la aproximacin
de P! siempre proporciona una cota in*eriorpara el valor ptimo dela P!E o P!E original. :uevamente, el agregado de restricciones
entera o bien empeora o bien de2a igual el valor ptimo de la P!. Enun problema de minimi#acin, empeorar el valor ptimo significa
aumentarlo.
7/25/2019 1.-Prog lin ent 2
18/55
otro e2emplo
7/25/2019 1.-Prog lin ent 2
19/55
7/25/2019 1.-Prog lin ent 2
20/55
APLI"A"IO$ES A LA +AIA,LE -/
7/25/2019 1.-Prog lin ent 2
21/55
!as variables binarias o 3;+ 2uegan unimportante papel en la aplicacin de las
P!E y de la P!E. Estas variables hacen
posible incorporar
7/25/2019 1.-Prog lin ent 2
22/55
Dos ejemplos ilustran lo ue decimos!
> '" En un problema de ubicacin deuna planta pondremos * + ' si
decidimos ubicar la planta en lalocalidad * y *+ & si decidimos no#acerlo.
> ," En un problema de asignacinde rutas escribimos *- + ' si elcamin - va de la ciudad a la
ciudad*o *-+ &si no lo #ace.
7/25/2019 1.-Prog lin ent 2
23/55
Ejemplo
> Presupuesto de capital! $na decisinsobre e%pansin. Muc#as &rmastoman decisiones sobre inversiones
anuales de capital. En 'orma simple,las decisiones sobre presupuestosdel capital es cuestin de escoger
entre n alternativas para ma%imi(arel r)dito, con sujecin a restriccionessobre el monto del capital invertido a
pla(os.
7/25/2019 1.-Prog lin ent 2
24/55
*omo ejemplo, supngase ue la mesa dedirectores de la Protrac a'ronta el problemaue se resume a continuacin
?lternativa (2
&alor?ctual del
@$dito:eto
Aapital requerido en ela'o i para la alternativa 2
+ 0 / -
Expansin de la planta en B$lgica /3 +3 - 3 +3 3Expansion de la cap. de maq. pq.en E.C. 63 03 3 +3 +3 +3
Establecimiento de una nuevaplanta en Ahile 43 +3 3 6 3 +3Expansin de la cap. de maq. gr. enE.C. +33 3 +3 /3 3 3
Aapital disponible en el a'o i bi -3 /- 63 /3 03
7/25/2019 1.-Prog lin ent 2
25/55
?lternativa (2
&alor?ctual del
@$dito:eto
Aapital requerido en ela'o i para la alternativa 2
+ 0 / -
Expansin de la planta en B$lgica /3 +3 - 3 +3 3Expansion de la cap. de maq. pq. enE.C. 63 03 3 +3 +3 +3
Establecimiento de una nueva plantaen Ahile 43 +3 3 6 3 +3Expansin de la cap. de maq. gr. enE.C. +33 3 +3 /3 3 3
Aapital disponible en el a'o i bi -3 /- 63 /3 03
7/25/2019 1.-Prog lin ent 2
26/55
.ormulac!n de un modelo de PLE
Ma%imi(ar +01 0/ 0 100+
2ujeto a 101 0/ 10 /0+30
31 /0/ /010++3
/01 10/ / +0+0 101 10//0 /0++0
10/ 10
7/25/2019 1.-Prog lin ent 2
27/55
$tilicemos el 6in728
7/25/2019 1.-Prog lin ent 2
28/55
Apro#mac!n de la PL
9os acercaremos a este problema resolviendoprimero la apro%imacin de PL. :esolviendo atrav)s del programa computacional /n012setiene!
;$9*?@9 =8AEB?;=4 /00
14 0.///
/4 0.C4 0./
+4 1.0+1
7/25/2019 1.-Prog lin ent 2
29/55
7/25/2019 1.-Prog lin ent 2
30/55
1oluc!n entero puro
$tili(ando el programa /n012y usandocdigos de programacin entera se tiene elsiguiente resultado
;$9*?@9 =8AEB?;=4 10.0
14 1
/4 14 1
+4 0
7/25/2019 1.-Prog lin ent 2
31/55
7/25/2019 1.-Prog lin ent 2
32/55
Condcone% L!gca%
$n importante uso de las variables 0-1consiste en imponer restricciones uesurgen de condiciones lgicas veamos
algunos ejemplo.
No m3% de - de entre n alternat4a%
2upngase i4 0 o 1, para i 4 1,..,n
7/25/2019 1.-Prog lin ent 2
33/55
La restriccin
'5 ,5 66 5 n -
?mplica ue cuando -alternativasde n posibilidades pueden serseleccionadas. Es decir, ya uecada puede ser solamente & ', la restriccin anterior dice ue
no mFs de - de ellas pueden ser
7/25/2019 1.-Prog lin ent 2
34/55
Por esta ra(n, la mesadirectiva uiere descartar unadecisin ue incluya la
e%pansin en 8)lgica y unanueva planta en *#ile.
7/25/2019 1.-Prog lin ent 2
35/55
8ec%one% dependente%
2e pueden usar variables 0-1 para 'or(ar unarelacin de dependencias entre dos o masdecisiones. 2upongamos, por ejemplo, ue eladministrador no desea elegir la opcin -a menos
ue se elija primero la opcin m.La restriccin
- m (9)
! -: m &
da vigencia a esta condicin.
7/25/2019 1.-Prog lin ent 2
36/55
> N!te%e ue sim no e%seleccionada, entonces m+ &
> La ecuacin G9H obliga entonces aue
-
sea igual a cero Go sea ue laopcin -no serF seleccionadaH.
> Por otra parte, si mes seleccionada;
m
+ '
7/25/2019 1.-Prog lin ent 2
37/55
Ca%o de la Protrac
Por ejemplo, supngase ue el administrador dela Protrac piensa ue, si van a e%pandirse dentrode los Estados $nidos, su posicin competitivaimplica ue de&nitivamente deben e%pandir la
capacidad en mauinas grandes.
7/25/2019 1.-Prog lin ent 2
38/55
An3logamente
2upngase ue la mesa directivadecide! Isi vamos a e%pandir nuestracapacidad domestica, debemos
e%pandir ambas lneas.
7/25/2019 1.-Prog lin ent 2
39/55
Re%trccone% de aportacone%
*onsidere a un administrador &nanciero ue tienelas siguientes restricciones
9 2i compra la obligacin *, debe comprar al menos ,&
acciones.
9 9o puede comprar mas de '&&acciones de la obligacin*. 2ea * el nmero de acciones de la obligacin * uecompra.
9 La restriccin Isi se compra * deberFn comprarse almenos ,& accionesK se llama Icantidad mnima deaportacinK o Icantidad de la tandaK.
7/25/2019 1.-Prog lin ent 2
40/55
7ueremos ue sea o bien * + &o ,& *'&&.
Para lograr esto necesitamos usar una variable0-1, digamos >*, para la obligacin*.
La variable >*tiene la siguiente interpretacin!
2i yj4 1, se comprarF la obligacin j.
2i yj4 0 no se comprarF la obligacin j.
7/25/2019 1.-Prog lin ent 2
41/55
*onsid)rese a#ora las dos restricciones
* '&&>* (99)
* ,&>* (999)
> ;emos ue si >*+ ', entonces GNNH y GNNNH implican ue ,&
* '&&
> Por otra parte si >* + &, entonces GNNH implica ue * &.
> Las dos desigualdades juntas implican ue *+ &.
> Entonces, si >*+ ', con lo ue se compra*, y &cuando no,tenemos la condicin apropiada para *.
7/25/2019 1.-Prog lin ent 2
42/55
PRO2LEMA 8E U2ICACIN 8ELO1 ALMACENE1 1TECO
> *on el objeto de a#orrar capital, la 2teco,comerciante al por mayor de acero, aluila susalmacenes regionales. El aluiler mensual delalmac)n es .. Oay cuatro distritos de ventas y la demandamensual acostumbrada del distrito * es de d*
camiones cargados. El costo medio de enviar uncamin del almac)n al distrito * es C*. La 2tecouiere saber cuales almacenes aluilar y cuantoscamiones enviar de cada almac)n a cada distrito.
7/25/2019 1.-Prog lin ent 2
43/55
?
+
AB
0 /
8?
?
8B 8A
B A
D1@F1
DE?:D? E:1C?! d+ d d0 d/
?!?AE:E1
AF1F E:1C?! DE
?!GC!E@ DE ?!?AE:E1
A?P?AD?D (E: A?F:E1A?@H?DF1
7/25/2019 1.-Prog lin ent 2
44/55
Almac0n
"osto por camin
1"i2Distrito de entas
"apacidad
Mens)al1n)mero decamiones
"ostomens)al delal5)iler
/ 3 4
A /7- 4- 7- /6- -- 778-, /8- /98 /-- /- 8- 4---
" /-- 4- /4- 6- 3-- 88--
Demandamens)al
1camionescargados
/-- 9- //- 6-
7/25/2019 1.-Prog lin ent 2
45/55
Con%deracone% %o$re la ?ormulac!n del modelo
La decisin de aluilar o no un almac)n enparticular parece reuerir una variable 0-1,puesto ue el costo de aluilar un almac)n no varia con el nivel de la actividad Gporejemplo, con el numero de camionesenviados desde )lH
yi 4 1 si se aluila el almac)n i
yi4 0 si no
7/25/2019 1.-Prog lin ent 2
46/55
> En primera instancia parece adecuado considerar el nmero decamiones enviados del almac)n al distrito como una variable entera.Oay varios 'actores ue indican considerar el numero de camiones
como una variable continua, a saber!> > '" Este es un modelo de planeacin, no un sistema detallado de
operacin. En este caso, el nmero de camiones ue indiue lasolucin de nuestro problema de programacin matemFtica uevayan del almac)n al distrito*es slo una apro%imacin de lo uerealmente ocurra en un da dado.
> ,- *onsiderar el nmero de camiones como variable entera #ara elproblema muc#o mFs di'cil de resolver.
> 7- *laro estF ue cuesta muc#o mFs el aluiler de un almac)n ueel envi de un camin desde el almac)n al distrito de ventas. Lamagnitud relativa de estos costos implica otra ve( ue esrelativamente mFs importante la decisin de Ialuilar o no aluilarKconsiderada como variable entera, en oposicin a lo de los camiones.
7/25/2019 1.-Prog lin ent 2
47/55
Un modelo de PLEM
Para elaborar el modelo del problema de la 2teco,#agamos
yi4 1 si se aluila el almac)n i
yi4 0 si no se aluila el almac)n i
i 4
7/25/2019 1.-Prog lin ent 2
48/55
.unc!n O$*et4o
*osto total asociado a los camiones 10
7/25/2019 1.-Prog lin ent 2
49/55
> Minimi(ar 30y
7/25/2019 1.-Prog lin ent 2
50/55
Para el d%trto de 4enta '
7/25/2019 1.-Prog lin ent 2
51/55
La re%trcc!n
7/25/2019 1.-Prog lin ent 2
52/55
Las demFs restricciones son
81 8/ 8 8+ /30
y8
*1 */ * *+ 00
y*
7/25/2019 1.-Prog lin ent 2
53/55
> Minimi(ar 30y
7/25/2019 1.-Prog lin ent 2
54/55
> ;$9*?@9 =8AEB?;= 47'@&
+AIA,LES +ALO +AIA,LE +ALO
:A /.-- ;,/ -.--
:, -.-- ;, -.--
:" /.-- ;,3 -.--;A/ -.-- ;,4 -.--
;A 9-.-- ;"/ /--.--
;A3
//-.-- ;"
-.--
;A4 -.-- ;"3 -.--
;"4 6-.--
7/25/2019 1.-Prog lin ent 2
55/55
Top Related