Programacion Entera

FACULTAD DE INGENIERIA INDUSTRIAL Y DE SISTEMAS

“Año de la Integración Nacional y el Reconocimiento de Nuestra Diversidad”

Curso : Optimización de Sistemas I
Titulo : Programación Lineal Entera
Docente : Zamora Córdova John
Alumna :

Fecha de entrega: Sábado 4 Agosto del 2012.

Sección :173 Aula : C601
CicloAcadémico : 2012-I








1.Marco teórico


Con el término Programación lineal entera, (PLE), nos referiremos al siguiente tipo
De problemas: problemas que formalmente son problemas de programación lineal, m´ax /
min Z = Ax = b, x ≥ 0 pero en los que algunas variables están restringidas a tomar
valores enteros.
Por ejemplo, x1≥ 0, x2≥ 0 y entera, X3∈ {0, 1}, x1unavariable como las que hemos
manejado hasta ahora, x2una variable entera no negativa y x3una variable binaria, que
toma ´únicamente dos valores, 0 ´o 1.
Como veremos en los apartado siguientes los problemas de programación lineal entera
nos van a permitir modelar muchas más situaciones que la programación lineal, pero a
cambio la resolución de los problemas sera mucho mas costosa, presenteran, engeneral,
un costo computacional mucho mas elevado que el de la programacion lineal.
La causa de este incremento de costo computacional se debe a que se pierde la deseable
propiedad existente en los problemas de programacion lineal de que al menos una solución
´ya no tienen que ser conexos (pueden estar definidos a trozos) y mucho menos convexos
con lo que la idea de punto extremo tal y comola hemos definido desaparece. De todos
modos, para su resolución a ‘un podremos utilizar técnicas basadas en el simplex.
En el apartado 2 presentaremos diversas situaciones generales que pueden ser modo-
ladas mediante PLE y después en el apartado 3 mostraremos dos técnicas de resolución,
una para el caso en que todas las variables del problema son binarias (Problemas de pro-
grabación linealbinaria) y otro para problemas con solo variables enteras (PLE puros)
o con variables continuas y enteras (PLE mixto).




2. Aplicaciones de la programación lineal entera (PLE)



Variables 0-1. Problema de inversiones

Las variables binarias xj∈ {0, 1} pueden utilizarse para modelar situaciones en las
que se decide si una acción se realiza, xj= 1, o si no se realiza, xj= 0.Un ejemplo típico
de utilización de este tipo de variables es el problema de inversiones, a continuación se
muestra una de sus versiones más implicadas.
Un inversor dispone de una cantidad b para invertir en n posibles proyectos/acciones.
Cada posible acción tiene un costo de ajunidades monetarias y un beneficio posterior
de cjunidades monetarias. El inversor debe decidir queinversiones realizar con objeto
de maximizar el beneficio total.
Para este problema se definen variables xjque toman valor 1 cuando se invierte en el
proyecto j y valor 0 cuando no se invierte, con estas variables el problema queda en la
forma siguiente:
Max Z = c1x1+ c2x2+ . . . + cnxn

s. a:

a1x1+ a2x2+ . . . + anxn≤ b
xj∈ {0, 1}, j = 1, . . . , n



Este problemabásico puede modificarse incorporando el hecho de que las inversiones
no sean de un solo periodo de tiempo sino que deban realizarse durante varios periodos de
tiempo, en cada uno de los cuales se dispone de una cantidad bide unidades monetarias.
También puede modificarse mediante la incorporación de condiciones y restricciones en
las inversiones, por ejemplo:


Si invierto en elproyecto i entonces debo invertir en el proyecto j. Dicha condición
responde a la ecuación
xi≤ xj
puede observarse que si xi= 1 entonces queda 1 ≤ xjcon lo que xjdebe tomar
valor 1 y si xi= 0 entonces queda 0 ≤ xjcon lo que xjno esta restringida y puede
tomar cualquiera de los dos posibles valores 0 ´o 1.


Si invierto en el proyecto i y...