Programación Entera
Los modelos de Programación Entera son aquellos donde la totalidad o un subconjunto de las variables de decisión toman valores enteros. En este sentido la forma estandar de un modelo de Programación Entera queda definido de la siguiente forma:
Existen múltiples aplicaciones de modelos de Programación Entera como apoyo a la toma de decisiones. Algunas aplicaciones típicas son problemas de localización de instalaciones, inclusión de costos fijos, problemas de asignación, problemas de ruteo vehicular, etc.
Modelos de Programación Entera
Problema Asignación: Una universidad está programando las clases para el próximo semestre académico y requiere buscar la mejor asignación posible de profesores a los distintos cursos que se deben dictar. Considere que existen 5 profesores: A, B, C, D, E y 5 cursos (asignaturas): C1, C2, C3, C4, C5. Adicionalmente, los profesores han manifestado sus preferencias por dictar los distintos cursos en una escala de 1 a 10, donde 10 es la máxima puntuación y 1 la mínima puntuación o preferencia. Se asume que cada profesor es apto para dictar cualquier curso, independiente del puntaje de su preferencia. La siguiente tabla resume las puntuaciones que asigna cada profesor a cada curso:
PROFESORES |
|||||
CURSOS |
A |
B |
C |
D |
E |
C1 |
5 |
8 |
5 |
9 |
7 |
C2 |
7 |
2 |
3 |
6 |
8 |
C3 |
9 |
10 |
8 |
9 |
8 |
C4 |
8 |
7 |
9 |
7 |
8 |
C5 |
6 |
9 |
9 |
10 |
5 |
Se ha establecido como criterio que cada profesor debe dictar sólo un curso y a la vez que cada curso obviamente debe tener un profesor. En base a lo anterior se desea encontrar la asignación de profesores que maximize el total de las preferencias.
Variables de Decisión:
Función Objetivo: Maximizar el total de las preferencias de los profesores
Donde P(i,j) corresponde a una forma sintética de resumir los parámetros del modelo, es decir, P(i,j) es la preferencia del profesor i (en una escala de 1 a 10) por dictar el curso j. Por ejemplo, P(D,C3)=9.
Restricciones:
Verifique utilizando Solver de Excel que la solución óptima de este problema es asignar el profesor A a C3, B a C5, C a C4, D a C1 y E a C2. Valor Óptimo = 44.
Problema Inclusión Costos Fijos: Usted ha sido designado por el gerente de su empresa para decidir cómo distribuirá su tráfico telefónico en el próximo mes, seleccionando entre 3 proveedores posibles y asignando la cantidad de tráfico (minutos) que desee en cada caso, es decir, puede repartir el tráfico en 1, 2 o 3 proveedores a su antojo y su decisión sólo dependerá de los costos de cada alternativa.
El proveedor 1 cobra un cargo fijo mensual de US$50 y el costo por minuto a red fija es de US$0,02 y a celular de US$0,12. El proveedor 2 tiene un cargo fijo mensual de US$60, con un costo por minuto de US$0,015 y US$0,15 a red fija y celular respectivamente. Finalmente el proveedor 3 tiene un cargo fijo mensual de US$40 con un costo por minuto a red fija de US$0,03 y a celular de US$0,14. Si usted llama por uno de estos proveedores (aunque hable sólo un minuto) deberá pagar el cargo fijo. Asuma que la cantidad de minutos que la empresa consume mensualmente es de 30.000 para red fija y 18.000 para celular. Formule y resuelva un modelo de Programación Entera que permita decidir cómo distribuir el tráfico telefónico mensual de la forma más económica para la empresa.
