Programación entera

INVESTIGACIÓN DE OPERACIONES I PROGRAMACIÓN ENTERAUNIDAD III

Existen problemas que por su naturaleza solo pueden admitir valores enteros para el valor de sus variables de decisión. Este es el caso de la fabricación de productos que no pueden admitir valores fraccionarios, como la determinación. de la cantidad a producir de llantas, refrescos, mesas, etc. Otro ejemplo, es la cantidad de personas a asignar a diferentes puestos de trabajo.Los problemas que solo contienen variables enteras se llaman programación entera pura. Sin embargo, podemos encontrar problemas en donde se requieran variables enteras y continuas (progrmación entera mixta). Algunos problemas requieren que las variables tomen valores 0_1, estamos hablando de problemas binarios.

Programación entera

Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat. Ut wisi Abordaremos problemas típicos de la programación entera como:-El agente viajero (TSP, Travelling Salesman Problem)-La mochila-Asignación-Financiero

Formulación de problemas enteros

Problema del agente viajero (TSP)

+ INO

El problema del agente viajero (TSP, Travelling Salesman Problem) tiene que ver con la determinación del viaje (cerrado) más corto en un caso con n ciudades, en el que cada ciudad se visita exactamente una vez.En esencia, el problema es un modelo de asignación con restricciones adicionales que garantizan la exclusión de sub-viajes en la solución

Problema del agente viajero (TSP)

Ejemplo 1Un vendedor de seguros desea visitar 3 ciudades ( 1, 2, 3), recorriendo la menor distancia posible. Para cumplir con este objetivo, no debe visitar o pasar más de una vez por la misma ciudad. Las distancias en kilometros se muestran en la tabla.

+ IO

Función objetivoMin Z= 7X12 + 5X13 + 7x21 + 3X23 + 5X31 + 3X32 Restriccionesx12 + x13 =1x21 + x23 =1x31 + x32 =1x21 + x31 =1x12 + x32 =1x13 + x23 =1No negatividadx12,x13,x21,x23,x31,x32 = (0, 1)

Problema del agente viajero (TSP)

Definición de variablesx12= ir de la ciudad 1 a la ciudad 2x13= ir de la ciudad 1 a la ciudad 3x21= ir de la ciudad 2 a la ciudad 1x23= ir de la ciudad 2 a la ciudad 3x31= ir de la ciudad 3 a la ciudad 1x32= ir de la ciudad 3. a la ciudad 2

-Solución del modeloEl sofware arroja las variables x12,x23 y x31 =1, con lo que se pude formar el circuíto de las visitas a las ciudasdes. El resto de las variables son 0, po rlo que no participan en el circuto visitado..

-Código del modeloEl modelo se introduce en el software con sintaxis LINGO

Solución en software LINGO

Ejemplo Una tienda departamental requiere asignarlos turnos de trabajo de su personal para la semana de rebajas anuales. Para poder cubrir toda la demanda que se espera es necesario que al menos la cantidad de empleados indicada en la tabla esten presentes. La empresa esta buscando cubrir esta demanda con la minima cantidad de empleados posibles. Los requerimientos para cada día de la semana se muestran en la tabla.

En los problemas de asignación se pueden asignar proyectos a contratistas, puestos de trabajosa trabajadores, trabajos a máquinas, turnos de trabajo a empleados, etc..

Problema de asignación

FUNCION OBJETIVOMIN Z= X1 + X2 + X3 + X4 + X5 + X6 + X7RESTRICCIONES X1 + X4 + X5 + X6 + X7 ≥29 X1 + X2 + X5 + X6 + X 7 ≥25 X1 +X2 + X3 +. X6 + X7 ≥27 X1 + x2 + x3 + x4 +. x7 ≥31 X1 +x2 + x3 + x4 + x5 ≥26 X2 + x3 + x4 + x5 + x6 ≥28 X3 + x4 + x5 +x6 + x7 ≥23 NO NEGATIVIDAD X1, X2, X3, X4, X5, X6 ,X7 ≥ 0 y enteros

Definición de variablesX1= Número de empleados que trabajan de lunes a viernes X2= Número de empleados que trabajan de martes a sabado X3=Número de empleados que trabajan de miercoles domingo X4= Número de empleados que trabajan de jueves a lunes X5= Número de empleados que trabajan de viernes a martes X6=Número de empleados que trabajan de sabado a miercoles X7=Número de empleados que trabajan de domingo a jueves

Problema de asignación

X1= Número de empleados que trabajan de lunes a viernes = 6X2= Número de empleados que trabajan de martes a sabado= 9X3=Número de empleados que trabajan de miercoles domingo=0X4= Número de empleados que trabajan de jueves a lunes=11X5= Número de empleados que trabajan de viernes a martes=0X6=Número de empleados que trabajan de sabado a miercoles=8X7=Número de empleados que trabajan de domingo a jueves=5

MODELO EN LINGO

SOLUCION

Solución al problema de asignación

La empresa Inverxus evalúa la posibilidad de realizar un conjunto de proyectos a través del tiempo. Ella ha estipulado un periodo de 4 años.Partiendo de la información del gasto de inversión de los proyectos y el rendiemiento que se espera para cada uno a través del tiempo. Esta quiere determinar que proyectos deben ser realizados durante el horizonte de planeación de los 4 años.La tabla muestra esta información así como los fondos disponibles, costos y rendimiento expresao en millones de pesos.

Problema de inversión

FUNCIÓN OBJETIVOMax Z= 25X1 + 32X2 + 25X3 + 28X4 + 20X5 RESTRICCIONES 8X1 + 7X2 + 6X3 + 10X4 + 12X5 ≤ 37 5X1 + 8X2 + 7X3 + 9X4 + 6X5 ≤ 37 10X1 + 12X2 + 13X3 + 11X4 + 7X5 ≤ 37 7X1 + 10X2 + 8X3 + 9X4 + 5X5 ≤ 37 NO NEGATIVIDAD X1, X2, X3, X4, X5 = (0,1)

DEFINICIÓN DE VARIABLESX1= Invertir en el proyecto 1 X2= Invertir en el proyecto 2 X3= Invertir en el proyecto 3 X4= Invertir en el proyecto 4 X5= Invertir en el proyecto 5

Modelo de programación entera

El mayor rendimiento se obtiene al invertir en losl proyectos 1, 2 y 4, el rendimiento esperado es 85.

SOLUCION EN LINGO

MODELO EN LINGO

Uso de software

Sphere tienda departamental desea aumentar las contribuciones de los pisos de exhibición. Esta tiene propuestas para exhibir en sus anaqueles 5 productos principales que ocuparían espacios diferentes. Sin embargo, la selección de los productos a exhibir deben de maximizar sus ganancias. Cada producto tiene necesidades diferentes de espacio por el que deberá pagar una renta. Actualmente, se cuenta con 10 metros cuadrados para la exhibición.La tabla despliega las necesidades de espacio y los precios a pagar por ellos.

EL PROBLEMA DE LA MOCHILA

Función objetivo Max Z= 3000X1 + 2500X2 + 4000X3 + 3000X4 + 3500X5 Restricciones 3.5X1 + 2.3X2 + 4.7X3 + 3.8X4 + 4.2X5 ≤ 10 No negatividad X1, X2, X3, X4, X5 = (0,1)

Las variables de decisión se definen como :X1= Exhibir el producto de la empresa 1X2=Exhibir el producto de la empresa 2X3=Exhibir el producto de la empresa 3x4=Exhibir el producto de la empresa 4x5=Exhibir el producto de la empresa 5

El problema de la mochila

SOLUCION EN LINGOLa solución es exhibir el producto de las empresas 1, 2 y 5. La ganancia maxima es de 9000.

MODELO EN LINGO

Gracias !!