Conferencia

Programacin entera bivalente.El problema de Presupuesto. El problema de la mochila.

A continuacin desarrollaremos ejemplos que son modelados a travs de la PEB.

Problema del Presupuesto

Una empresa est pensando en invertir en 4 proyectos diferentes, cada uno se termina a lo sumo en tres aos. Los flujos de caja requeridos en cada ao, el valor presente neto (VPN) de cada proyecto concluido, los aos de ejecucin y la disponibilidad de recursos financieros se resumen en la siguiente tabla:

P1P2P3P4Disp. Recur.

Ao 110861230

Ao 28154015

Ao 318016020

VPN35182416-

Se desea determinar en cules de los proyectos invertir para obtener el mayor VPN posible en la inversin.

Variables de decisin:xj=1 Si se invierte en el proyecto j.xj = 0 Si no se invierte en el proyecto j.

j=1, 2, 3,4

Restricciones:

Funcin objetivo:

Maximizar Z= 35 x1 + 18x2 + 24x3 + 16x4

Si agregamos las siguientes situaciones al ejemplo:-Se debe invertir en al menos uno de los tres primero.-El proyecto 2 no se puede ejecutar a menos que el proyecto 3 sea ejecutado.-Se puede ejecutar el proyecto 3 o el 4 pero no ambos.-No se puede invertir en ms de 2 proyectos.

Entonces se agregaran al modelo las siguientes restricciones:

X1+x2+x3 1X2 x3X3 + x4 1X1 +x2+x3+x4 2

El problema de la mochila

Una firma comercializadora quiere lanzar al mercado una oferta de artculos combinados para hombres, con el objetivo de incrementar las ventas con vista a la conmemoracin del da de los enamorados. Se dispone de un surtido de 6 productos y dos tipos de envases (M y G). Se desea determinar la composicin de los envases de forma tal, que se obtenga el mayor ingreso con la venta de cada uno. A partir de un estudio se ha recopilado la siguiente informacin:

* El peso mximo admisible para los envases es de 5 libras para el tipo G y de 3 libras para el tipo M.* Los pesos en libras, los precios en $ para cada artculo son: Productos123456

Peso lbs0.10.41.21.30.82

Precio $50.753.512215

Se desea determinar qu producto envasar en cada tipo de envase para maximizar los ingresos de la firma comercializadora.

Variables de decisin:

Xij=1 si se envasa el producto i en el envase j

Xij=0 si no se envasa el producto i en el envase j

I= 1,2,3,4,5,6 J= M, G

Restricciones:

0.1x1M + 0.4 x 2M +1.2 x3M +1.3 x4M +0.8 x5M + 2x6M 3 ,

0.1x1G + 0.4 x 2G +1.2 x3G +1.3 x4G +0.8 x5G + 2x6G 5.

Funcin objetivo :

Maximizar Z= 5x1M + 5x1G +0.75 x 2M +0.75 x 2G +3.5 x3M +3.5 x3G +12 x4M +12 x4G + 2x5M +2 x5G +15 x6M + 15x6G

Si agregamos la siguiente situacin al ejemplo:

- Para satisfacer las demandas se desea que en el envase G se empaquen cuando ms tres artculos y en el M no ms de dos.

Entonces se agregaran al modelo las siguientes restricciones:

3. Para finalizar la construccin de una vivienda faltan nicamente unos pequeos trabajos de electricidad, fontanera y pintura

Se han recibido presupuestos de tres empresas para finalizar los trabajos pendientes:

Empresa AEmpresa BEmpresa C

Electricidad$1500 $1400 $1700

Fontanera$1800 $1500 $2000

Pintura$900 $600 $700

Se quieren finalizar las obras en el plazo de una semana, para lo cul cada empresa se podr contratar para un mximo de 2 tareas Variables binarias (0 o 1): por ejemplo AE = 1 si se asignan los trabajos de electricidad a la empresa A

MIN = 1500*AE + 1800*AF + 900*AP + 1400*BE + 1500*BF + 600*BP + 1700*CE + 2000*CF + 700*CP;AE + AF + AP